Walter Gray
wrgray@ucsc.edu
CS 161, Final Project

This is my final project for CMPS 161 demonstrating physically based modeling of large numbers of objects

The readme with instructions for the controls can be found here

Outline

The overall goal of this project was to create a simulation of a huge number of physically constrained objects. The original plan was to be completed in two phases. First the underlying physical simulation would be put in place. This would enable objects to be dynamically inserted and removed from the simulation, and enforce physical constraints on the objects. The base required physics model included Brownian motion, spring connections, collision detection, and the ability of the user to drag objects around with the mouse. Individual objects would also be able to multiply and delete themselves under certain conditions. The second, and more complex part would concentrate primarily on graphical enhancements and adding more diverse behavior. Some examples include the ability for different clusters of cells to function in different ways, multiple cell types and the ability for cells to infect others or mutate themselves, a deformable boundary around cell clusters, or a more realistic looking division behavior when spawning.

Product

The first phase is 100% completed, however nothing has been done on phase two. Exact features include:

-Objects are dynamically created and deleted from the heap
-Objects may be picked and dragged about the screen
-Objects collide against each other in a soft manner
-Objects may delete themselves
-Objects may duplicate themselves
-All objects have a constant frictional force as well as Brownian motion applied to them
-Objects use predictive collision detection to ensure they are never outside the level boundaries
-The Simulation frame rate is completely decoupled from the render frame rate.
-Different simulation states are interpolated to create an illusion of higher resolution physics

Also, thanks to the judicious use of reference counted smart pointers, there are no known conditions that cause a segmentation fault and memory leaks are scarce The architecture is shaky, but it should hold up well.

What Went Right

One of the other features I am quite happy with is the underlying physics engine. While it could be vastly improved and optimized by more clearly defining the ownership and responsibility of certain member classes, It does have several very nice features, and has seems to be both deterministic and stable: A somewhat tricky thing to pull off while maintaining speed. It does only use Euler integration, but to help make up for that it uses a completely fixed time step, so the consistency issues arising from differing integration lengths are eliminated. Normally this would result in a somewhat jerky animation, but the trick here is that it can interpolate between physics updates to make the rendering appear smooth while the actual simulation might be stuttering. There is still a definite error, and if the time step is set too low the springs will explode, but that can be avoided by simply increasing the simulation time step in Simulator.cpp. The collision response could also be improved slightly for realism, but on the whole I'm fairly pleased with it.

What Went Wrong and How It Could Be Fixed

Perhaps the most glaring issue with this program is how slow it can get. Though I don't have a profiler handy, I suspect that the collision detection algorithm is responsible. It only checks every pair once, and it excludes objects that it already has a spring connection to, but it is still O(n^2), which is simply unacceptable if you want 500+ objects on screen and moving at once

In retrospect, The largest thing that messed this whole thing up was the use of dynamic allocation and poor definitions of ownership. Given that it was possible, and even reasonable to have some arbitrary cap on the number of simulated elements, as well as the fact that each cell wasn't terribly large, allocating things from the stack instead of the heap would have been a much better choice. There is also a lot of cross ownership going on. Every system has pointers going to the internal bits of other systems... It's ugly, and if it wasn't for many hours of debugging It wouldn't work at all. I think that not having to worry about checking for null constantly or inform other subsystems of deletion would both vastly improve performance, and allow much greater compartmentalization.

Really, this should have been modeled as a glorified particle system, with some max # of cells being allocated on creation and simply having some bIsInUse flag to indicate if they should be drawn or simulated or not. This would also have eliminated the need for smart pointers entirely since once allocated, the particles would not be deallocated until the particle system object containing them was destroyed anyways. Such a model would have automatically provided an ID system in the form of the index of the object, since I didn't care about wrapping or Re-use. Even better, I would have had one and only one central repository for the particles which everything else would be subordinate to. This could significantly cut down on information sharing, since subsystems could point directly at the objects and never have to worry about informing other subsystems about what they did to them, and having all active cells in one handy list is also the first step towards optimizing the collision detection with a spacial hashing function.

To make a long story short, now that I'm actually conscious and not cramming like mad to get a working product finish, I'm kicking myself for not thinking of most of this stuff sooner. It would have probably saved me hours of debugging work and produced a higher quality result.
Downloads

Windows Exe : Download
Source Files : Download

Screen Shots

A Typical Screen:

With Springs Viewable:

Another typical shot:

Due to the interactive nature of the application, I recommend that you simply run the exe or compile using the provided source files if you want to see it in action.