Monday, November 19, 2012

Physics Engine - Part One (Introduction)

Inspired by Shamus Young's soft-body physics explanation, and disillusioned by the shortcomings of jODE and jBullet, I recently started working on an OpenCL-based physics engine in Java.  After reading up a lot about how these systems work, I discovered a way to handle the full continuum from soft to hard constraints, which, to my knowledge, not even the top-of-the-range commercial physics libraries do.

To keep the development fast, I decided to first implement it in 2-D in Java, then upgrade it to 3-D and finally port it to OpenCL.  Normally one couldn't just port from a serial language to a parallel language and expect a performance improvement, but I will keep this in mind throughout the design and implementation.

I am handling all objects as sets of connected simplices with a particle at every vertex, and a length constraint on every edge.  To calculate the mass of each particle, I will divide each simplex into Voronoi cells for its vertices, calculate the volumes of these cells, multiply these volumes by the density of the simplex, and finally sum these masses for each vertex.

Unlike most soft-body systems, my simulation will support rigid length constraints between the particles.  The way to do this, I believe, is not to use forces directly, but rather to find the closest local minimum in a potential field.  And with 'closest' I mean that I minimize the sum of the squares of the impulse required to reach that minimum.  The potential functions applied are simple enough that this means that I could use gradient descent or a related method.  In fact, I plan on having each individual constraint simple enough to solve in one step.  In the end, this is identical to using the forces directly, except that the forces' strengths are exactly as required, rather than arbitrary, and therefore causes/allows no oscillations or exponentials.

Of course, it would not be a soft-body system without soft constraints.  I will handle soft constraints the same as the rigid constraints, except with a hard limit on the strength.  This is again very similar to the force-based method, except that it doesn't apply more force than is needed.  (However, I do expect some trouble with keeping track of the total applied impulse over multiple iterations.)

To handle collisions, sliding, rolling and friction, I could use conditional constraints if I can think up the right data structure to optimize the calculations.  It will probably resemble some of the common collision detection algorithms, except adapted to run in parallel.  I will post more about this when I have the details sorted out.

No comments:

Post a Comment