Main

HomePage

Sun, 24 Aug 2008 16:46:45 Z

Scott Lembcke’s Wiki

Current Projects:

ScribBall – Puzzle game I’ve worked on with a friend under the Howling Moon Software moniker.
Chipmunk – A high-performance 2D rigid body physics library.
Aerosol – A 2D game prototyping and development environment.
Gimp-Ruby – A Ruby language binding for the GIMP. Started for the Google Summer of Code 2006 program.

Past Projects:

Academic Research Projects:

Optimization of Java Generic Types – Researching possible optimizations of Java programs.

School Projects:

XPTracker – Final group project for my software engineering course.
Lossy Image Bisection – Final project for my data compression class.
Realtime Rigid Body Simulation Using Impulses – My senior seminar paper.
Atrium Modeling Project – Class project for a computer graphics course I took. Our task was to model the atrium in the science building of our university.
JCool Text Editor – Final group project for my software design course.

Game Projects:

The X-Fish – My entry for the iDevGames 21 Days Later: Predator contest.
Antimatter – A 2D puzzle/action game similar to Super Transball. Created for the iDevGames Original Mac Games contest.
Smile Delivery – A one button platformer. Written for an informal 24 hour game contest.
Squirrel Physics Kit? – An old implementation of Jakobsen Physics.

Random Stuff:

Frankenstein – Have I created a monster?
Example Code – Random bits of code.
Ruby Snippets

Chipmunk

Wed, 28 May 2008 02:21:08 Z

Screenshots:

Go to the screenshot gallery.

Videos:

Sketches – An amazing work in progress made by a forum member. (forum thread)
The Machine (youtube)
Domino pyramid (youtube)
Domino smash (youtube)
More

Features:

Designed for 2D video games.
Circle, convex polygon, and line segment collision primitives.
Multiple collision primitives can be attached to the same rigid body.
Fast collision detection by using a spatial hash for the broad phase.
Extremely fast impulse solving by utilizing Erin Catto’s contact persistence algorithm.
Support for collision callbacks based on object types.
Impulses applied to contact points can be retrieved after the impulse solver has finished.
Several kinds of joints available.
C99 implementation, no external dependencies.
Ruby extension available.
Simple, read the documentation.
Unrestrictive MIT license.

Download:

Source + Demos

Tutorials:

Moon buggy tutorial (XCode project)
- Create a simple side scrolling vehicle game. (Complete with soft suspension!)
- Shows basic Chipmunk usage including initialization and usage of joints.
More to come

Community:

Chipmunk Forums at Slembcke.net

Testimonials

”I had been working on my own physics code for months, trying to make it as fast as possible – then I took 3 days to change out my setup for chipmunk and things improved considerably. Chipmunk is fast and easy, I recommend it.” – Derek Arndt (Biofilm)

Logos

Want to throw a logo on your splash screen to show how much you appreciate Chipmunk? Frank Condello was gracious enough to make a logo for me. A couple variations are available here.

SVN:

Chipmunk is currently hosted as a Google Code Project. Go there now.

Acknowledgments:

Box2D:
- Erin Catto’s Box2D code was the most useful reference that I used when creating Chipmunk. His contact persistence algorithm is the main reason why Chipmunk is so fast.
Optimized Spatial Hashing for Collision Detection of Deformable Objects
- The best article I could find on spatial hashing. Their hash function seems to perform very well.
Nonconvex Rigid Bodies with Stacking
- My previous implementation was based on this paper. I only implemented part of the algorithm before deciding that something simpler would be better suited for real time.
Physics for Game Developers
- This book is a good reference for a lot of the math you’ll need, but is far from a good reference on implementing a physics engine.

Logo by Frank Condello, Chipmunk sillouette by Kelvin Nishikawa

Realtime Rigid Body Simulation Using Impulses

Sat, 24 Nov 2007 08:55:39 Z

Short Introduction:

Read the paper

Our senior seminar papers didn’t have to include any original work or research (lam I know). They were in fact supposed to be entirely a literature review. I was hard at work writing Chipmunk from scratch at the same time. I originally was going to work in a bit about my own implementation, but as I would get no credit for doing so, I decided to focus my efforts on developing Chipmunk to the point were I could generate some animations that would knock people’s socks off at the presentation. I think I did that fairly well as I certainly had the coolest media of all of the presentations that semester, and most of it made by me. :)

Other than that, I’ll let the paper speak for itself.

Frankenstein

Sat, 24 Nov 2007 08:39:40 Z

My freakish/hideous laptop.

The Story:

It’s made from parts of three different iBooks!

My sister used to have an orange iBook that she stopped using when my dad gave her his key-lime colored iBook. She’s a big orange fan though, so she asked if I could switch the cases for her. I knew the display case would be pretty trivial to switch, so I did that, but told her that I couldn’t do the bottom. She was happy enough with just the top, so that was that.

Some time later, my white iBook died of the dreaded logic board problem for the second time. My warranty was out and they hadn’t yet announced the extended support plan, so I tore it apart.

I figured I might as well put the good parts like the brand now 40GB HD, combo drive, 512MB dimm, and wireless card to use. So I pulled my sister’s old iBook out and threw the extra parts in there.

Bottom case, processor and screen from an orange iBook, display case from a key-lime iBook, and everything else from a white iBook. Runs great as a couch machine. Couldn’t ask for more.

Frankenstein lives on:

After spending a weekend trying out ways to revive Frank’s usefulness, I came to the conclusion that he’s still kicking. I was going to try to install Ubuntu Linux on it to see if that would make the system faster. That was a definite no. I also used XPostFacto to install 10.4 which certainly gave Ubuntu a run for it’s money. With speed seeming like a choice between 6 and a half dozen. I obviously picked OSX. The GNOME desktop environment is simply too pokey to be realistically usable on Frank, and certainly can’t stand it’s own against OSX anyway. I certainly was impressed with Ubuntu as far as distro’s go though. It certainly gets my recommendation.

So with a fresh system on it, I began fiddling with settings and was convinced enough that it was still very usable for anything but graphics. It has plenty of disk space, it plays EyeTV recorded MPEGs just fine and can play older games and emulators well enough. The only thing holding me back from using it on a regular basis is that the battery is shot. So I decided to bite the bullet and buy one for it.

Only time will tell if it is worth the money.

Yes, it was worth the money

Even though it’s as slow as molasses, and doesn’t have hardware accelerated OpenGL to run most of my programs, it’s still very useful. There’s still a lot of code that I can use it to write, and works just fine for wirelessly surfing the web. It also gets great battery life, 5-7 hours. I find it very likely that the next computer I get will be a new laptop. We’ll see what Apple does with the Intel iBooks (or whatever they decide to call them). Maybe if I get a good internship this summer I could splurge for a MacBook.

Update for the Curious:

I did in fact get a good internship that summer. See: Gimp-Ruby I ended up buying a MacBook to do my development work on, and have been very happy with it. Frankenstein still gets a fair bit of use for playing network Starcraft and playing old OS 9 games (such as the old Ambrosia Games).

Lossy Image Bisection

Sat, 24 Nov 2007 08:33:28 Z

Overview:

For my project, I applied using image bisection in a lossy manner for image and video compression. The basic idea is that each channel in the image is recursively split in half along its longest axis. If two child nodes in the tree differ by less than a certain tolerance, then they are pruned from the tree and their average is stored in the parent node. The result of this process is a binary tree with the image information stored in the leaves. This can be easily serialized to disk and further compressed using a general data compression algorithm such as huffman coding or deflate.

My data compression textbook only briefly mentioned image bisection before moving onto quadrisection for losslessly compressing b/w bitmaps. I’m not exactly certain why that is, as bisection is less complicated to implement, allows you to process non-square images, and uses the same amount of space to store the tree data. Originally I was going to use quadrisection, but the restriction that the image would have to be square made me realize the superiority of bisection.

My implementation consisted of a series of commands that I could chain together. I had commands for reading/writing raw RGB data from PNG files, splitting/merging channels, compressing/decompressing a single channel, transforming to YCbCr from RGB and vise versa, and performing frame differencing. By rearranging the commands in the pipeline, I could easily try out new possibilities. This ultimately proved quite handy once I tried video compression, as I only had to add commands for handling frame differencing. Lastly, I would always compress the resulting data with gzip (deflate).

For the impatient, my algorithm performed mildly well on image little high frequency noise. When used losslessly, it seemed to perform better than PNG compression. I assume that it had to do with a better entropy coding, but I don’t have enough data to back up either claim. It’s also fair to think of it as RLE on steroids. While image bisection is better in most cases than RLE for animation images, it is no match for DCT or wavelet based methods for photo data.

Results:

Get the full paper here.
Browse the result images at different tolerances here. All of the images were compressed, decompressed, and re-encoded as PNG files. If you want to see the particulars of the compression ratios, see the paper above.
Download the C source code here.

Ruby Snippets

Mon, 30 Jul 2007 05:39:33 Z

Significant digits.


def sig_digits(n)
    exp = (n == 0) ? 0 : Math.log10(n.abs).to_i
    mag = exp/3

    mant = n.to_f/10**(mag*3)
    post = ['', 'K', 'M', 'B'][mag]
    sig = 2 - (exp%3)

    sprintf("%.#{sig}f%s", mant, post)
end

[0, 3, 10, 999, 1000, 9990, -1, -1000].each{|n| puts "#{n} -> #{sig_digits(n)}"}

#0 -> 0.00
#3 -> 3.00
#10 -> 10.0
#999 -> 999
#1000 -> 1.00K
#9990 -> 9.99K
#-1 -> -1.00
#-1000 -> -1.00K

Recursive composition using blocks.


module RecursiveBuilder
    def self.append_features(mod)
        puts "adding to #{mod}" 
        def mod.new(*args)
            args << yield if block_given?
            return super(*args)
        end

        super
    end
end

class ListNode
    include RecursiveBuilder

    def initialize(obj, child)
        @obj = obj
        @child = child
    end

    def to_s
        "#{@obj} #{@child}" 
    end
end

# pass object in place
# this makes you build it backwards
a = ListNode.new('lincoln', nil)
puts ListNode.new('abraham', a)

# you could do this...
puts ListNode.new('abraham',
    ListNode.new('lincoln', nil)
)

# but using a block lets you do calculations in the same scope
puts ListNode.new('abraham') {
    str = ['l', 'i', 'n', 'c', 'o', 'l', 'n'].join
    ListNode.new(str, nil)
}

Template.


# code...

Resume

Mon, 23 Apr 2007 06:59:04 Z

Scott Daniel Lembcke

1822 S. Mill St.

Fergus Falls, MN 56537

Email: lemb0029(at)morris(dot)umn(dot)edu

Education:

University of Minnesota Morris

Pursuing B.A. in Computer Science (Mathematics Minor)
GPA in Computer Science 3.91
Overall GPA 3.71
Graduation expected May 2007

High School

Graduated Summa Cum Laude from Hillcrest Lutheran Academy

Awards:

One of 34 students to receive the Scholar of the College status from the UMM Campus Assembly in 2007.
Recipient of the UMM Chancellor’s Scholarship.
1st at the ACM International Collegiate Programming Competition in our subregion in 2005, and 3rd in 2004 and 2006.
1st at the Digi-Key Computing Competition in 2006, 3rd in 2005.
1st at the MICS programming contest in 2006 and 2007.
Made the Dean’s List several semesters.
Recipient of the Helen and Carl Iverson Memorial Scholarship.
3rd at the Odyssey of the Mind World Competition in 1999.

Work Experience:

Google Summer of Code (May – August ‘06)

One of the 630 students selected worldwide for Google’s Summer of Code 2006.
Created a Ruby language binding for the GIMP, a popular open source image editor. See Gimp-Ruby for more information.

Photo Retouching (May – August ‘05)

Dawn’s Photography, Dalton MN

Responsible for general maintenance of office computers.
Retouched portraits with Adobe Photoshop.

Service Technician (October ‘02 – August ‘03)

Integrity Computer Systems, Fergus Falls, MN

Helped set up and create small Mac networks, wired and wireless.
Repaired Apple computer systems.
Worked with both hardware and software problems.

Computer Maintenance (June – August ‘00)

Fergus Falls High School, Fergus Falls, MN

Ran yearly software and hardware maintenance on school’s computers.
Ran network cabling, tested current network, and set up networking software on the school’s network.

Programming Experience:

Experience working on small to medium sized teams.
Extensive knowledge: C/C++, Ruby, Java.
Experience with: Python, C#, Objective-C, Scheme, PHP, JavaScript, and OCaml.
Experience with environments: Unix/Linux, Java, and to a lesser extent Mac OS X.
Experience with relational databases and SQL.
Experience with web technologies: XHTML, CSS, AJAX, Ruby on Rails.
Experience with OpenGL.
Experience with GUI libraries: GTK+, Cocoa, Swing.

Research:

Involved in a research project along with another student, which was advised by Dr. Elena Machkasova. We were researching the optimization of Java programs using generic types. This research produced the paper Specialization of Java Generic Types, which was presented at MICS 2006, and also the Undergraduate Research Symposium at my university. See Optimization of Java Generic Types for more information.

Projects:

Chipmunk, a rigid body physics library for 2D game development. Chipmunk has attracted attention from award winning independent Mac game developers such as Nathan Lamont and Ivan Milles, both of whom have expressed their interest in using Chipmunk for their upcoming projects.
Gimp-Ruby, a Ruby language binding for the GIMP image editor. Created for the Google Summer of Code program in 2006.
XPTracker, an Extreme Programming style project tracker, created as a team for the software design class to use a project tracker. Recently migrated to SourceForge and released under the BSD license.

See the wiki HomePage for a list of all my projects

References:

Dr. Elena Machkasova (Professor, Research adviser)
Dr. Nicolas McPhee (Professor, academic adviser)
Kevin Cozens (Google Summer of Code mentor)

Contact information is available upon request.

Interests:

Photography and digital photography
Simulation and graphics programming
Programming languages
Mathematics

Antimatter

Tue, 17 Apr 2007 08:00:19 Z

Introduction:

Antimatter was written for the iDevGames Original Mac Games 2005 contest. Unfortunately, I never had the time to polish it as much as I wanted, and it didn’t do very well. I still like the game however, and think it’s worth a try.

Story:

For years the anti-verse, the opposite dimension of ours, has been stealing energy. Now it’s time to get it back. You are the pilot of an inter-dimensional fighter ship capable of punching a hole though dimensions for a short time. Get in, get the anti-matter containment vessels, and get out fast!

Controls:

Arrow keys fly the ship.
Space bar dumps all of your momentum into the ball, stopping you and flinging it away.
The balls are picked up automatically by proximity.

Objectives:

In each level, you must get all of the antimatter containers back to the warp rift as quickly as possible.

Several obstacles await you, doors, switches, containment fields, and glass.

Requirements:

OS X 10.2 or better
A 16MB Radeon, GeForce2 or better.
Has been tested as low as a 1.25GHz G4/Radeon 8500 running 10.3.

Play:

OS X binary (PPC)

Acknowledgments:

The ‘Anklepants’ font is from 1001 fonts.
The Ruby OpenGL Extension was originally written by Yoshiyuki Kusano, and edited by Keith Bauer.
The Ruby OpenAL Extension was written by Keith Bauer.
The sound effects and ship sprite are from the iDevGames asset library.

Example Code

Tue, 17 Apr 2007 07:59:31 Z

Random bits of code that I’ve mashed together for various purposes.

PNGTexture

Shows the simplest way to load a .png file and load it as an OpenGL texture.

Waves

A simple and fast 2D wave idea that I came up with. Could easily be extended to generate a 3D mesh. I’m sure I’m not the first one to try this.

JCool Text Editor

Wed, 11 Apr 2007 04:52:10 Z

JCool Text Editor

Introduction:

This was the final group project for my software design class that I took as a sophomore. It was written in Java using the Swing GUI toolkit.

To be perfectly blunt, the class was a bit of a disaster. It was taught by an interim professor who didn’t really seem to care, the CSci lab was hit by some major problems part way through the semester which broke several of our testing tools, and we used a wiki-based project tracker that lost a bunch of our tracking data.

All was not lost however, we were able to finish the project on time, and even implement a lot of the extra features that we wanted. It had a directory tree in a side panel so that you could easily open and browse files, tabbed editing, and syntax highlighting for several languages. We had thought it would be cool to allow collaborative editing, but we only got as far as allowing documents to be shared over the network and implementing integrated IM functionality.

You can see what’s left of our project’s tracker here.

Download:

Not currently available.

Lessons Learned:

Not a fan of Swing. It’s slow, buggy, and the API isn’t terribly consistent. Having used other GUI libraries like Cocoa and GTK+, Swing seems pretty immature. I’d want to look into SWT before writing another Java GUI app.
Testing is important! We really drug our feet at the whole testing idea at first, but when we got farther in the project and didn’t have the ability to test anymore, it became difficult to integrate peoples changes.

Gimp-Ruby

Tue, 03 Apr 2007 20:06:27 Z

Note: Gimp-Ruby is written against GIMP 2.3 which is the developmental version and not the current stable version. I’m looking into what would be necessary to backport Gimp-Ruby to 2.2.

Gimp-Ruby:

Gimp-Ruby allows you write new GIMP plugins in the Ruby programming language. Gimp-Ruby also contains a module, Ruby-Fu, which allows you to define new procedures similarly to Script-Fu.

Download:

Get the source tarball here: gimp-ruby.tgz

Gimp-Ruby can also be checked out of the GNOME SVN repository using the following command: svn co http://svn.gnome.org/svn/gimp-ruby/trunk gimp-ruby

Documentation:

For more information, read the Gimp-Ruby guide, and the Gimp-Ruby tutorial.

Special Thanks:

Gimp-Ruby was created as a project for the Google Summer of Code 2006 program. My project mentor was Kevin Cozens, who was almost entirely responsible for setting up the build scripts for me.

The gimp irc channel was also a big help to completing the project.

More information to come

Smile Delivery

Tue, 03 Apr 2007 19:03:57 Z

Smile Delivery

Introduction:

Smile Delivery was written for an informal 24-hour game contest with a “one button” theme. The game was written over a period of 6 hours. I coded the game up while a friend of mine, Luke Anderson, drew out levels.

Story:

A story? Um, well, you’re a smiley face that’s trying to spread cheer to all the grumpy faces. That’s good enough to be a story right? :p

Controls:

As this was a one button contest, you only need to have your finger on the mouse button. You still have a considerable amount of control over your character though.

Click and hold: Move your character in the direction the arrow is pointing.
Tap: Switch the direction of your character’s arrow.
Double click: Jump.

You can also string these together in order to perform fancier jumps.

Tap then hold: Jump and move in the opposite direction.
Tap, tap, then hold: Jump and continue in the same direction.

Play!

OS X binary (PPC)

The X-Fish

Tue, 03 Apr 2007 19:03:00 Z

Info:

Created for one of the shorter iDevGames game contests during the summer of 2005. The X-Fish is really the first game that I’ve ever made public. It placed 5^th out of 8 in the contest, but almost undoubtedly would have taken 1^st by the numbers if it had run on the 4^th judge’s machine. The game required a Radeon or better, but the judge only had a Rage 128. C’est la vive. Not that I’m complaining or anything. :p

Story:

Swimmy the fish is lost in the bad part of the ocean. If only he’d listened to his mother. Now he’ll have to fight his way to the top of the food chain.

Controls:

Use the mouse or arrows keys to maneuver Swimmy.

Objectives:

Eat fish smaller than you in order to grow. Avoid bigger fish as they will be doing the same! You win once you make it to the top of the food chain.

Play!

OS X binary (PPC)

Source:

Not available at this time

Aerosol

Tue, 03 Apr 2007 04:23:41 Z

Aerosol is a 2D game programming environment based around the Ruby programming language. Unfortunately, Aerosol is far from completion at the moment.

It has support for:

PNG and JPEG Texture loading.
Rigid Body physics supplied by my Chipmunk physics library.
Simple, fast, and Ruby-esque event handling with support for joysticks.
Access to OpenGL and OpenAL.
Support for .wav files and streaming Ogg Vorbis music.

Write your gameplay code in nice, easy to read, easy to develop Ruby code, while the real grunt work (physics, graphics, sound) is offloaded to C extensions.

Check out the Google Code page.

XPTracker

Tue, 03 Apr 2007 04:07:26 Z

Click for full image

Overview:

XPTracker is a project tracker based on the Extreme Programming software development methodologies. It was started as the final group project for my software engineering course, but has been revived for my current client-server programming course. It is also being used by the software design class to track their labs.

Get the Source:

Sourceforge page

We recently migrated the project from a private SVN server to Sourceforge. The page is still a bit devoid of information, but you can go there and at least check out the code.

More to come.