Tag Archives: Q&A

Gemini Physics Development 3: Progress Update

Its been a while since my last update…

API

One of the main complaints I see with other physics engines is that the interface is too complicated or hard to use. The past week or two, I have been working towards a straightforward API that gracefully exposes all of the various features that Gemini offers.

The core of Gemini is written in pure C with zero external dependencies other than the standard C header files that should be available to any half decent C89 compliant compiler. It is data driven, meaning most parts of the engine are configured by simply modifying fields of a struct.

While the C interface is very clean, some (including myself) prefer a more object oriented approach. Therefor, I have also written a C++ wrapper on top of the C interface. Both API’s are efficient and memory-leak friendly (as in, hard to memory leak). They have also been designed to allow easy integration with scripting engines.

From the beginning, it was in the design to support single, double, and fixed point precision. I was debating how to include these different modes. As it is now, the mode is specified by the library you link with. In addition to a numeric precision mode, you can also choose between a 32-bit or 64-bit build for your platform. At present, there are no optimizations in the 64-bit build, but that will hopefully change. The alpha release should include builds for the following platforms: Windows, Linux, OSX, and Android.

For the next build (the beta), the plan is to fix various bugs that pop up, add a selection of user requested features, add an iPhone build, and add a C# wrapper interface.

Technical Developments

In addition to the major API work, I have also been added some cool features to the engine itself. No video today – next time :)

The first major improvement was in the constraint solver. The new constraint solver, which I’ll call the adaptive solver, solves selectively until the error from all constraints and collisions reach a user specified value. This means there are less parameters to tweak, and you can easily adjust performance of the solver to suit your needs.

The second major improvement is the addition of friction. Normally this might not be considered a major improvement – but in the context of the verlet-style framework that Gemini uses, it was very tricky to get right. It supports both static and kinetic friction with coefficients that can be based on real world ones, as described here.

In order to keep the implementation fast and to easily support many of Gemini’s features (such as serialization), there needs to be a minimal amount of state stored between each simulation step. This is why friction was so tricky – normally physics engines keep a cache of contacts which they can rely on to store various values that help with solving during the next run. With Gemini, very minimal caching goes on. Most of this information therefor needs to be derived during the next solving step, including that used for friction and stacking.

A slew of other features have also been added (which you will see in the next video). These include:

  • Stable stacking – a side effect of using the new adaptive solving mechanism and friction detailed above
  • One sided edges – particles can pass through one side, but are blocked on the other
  • Rigid body constraint – solves all constraints of a body at once, causing quicker convergence and more accurate rigid shapes
  • Rope constraint – similar to the rigid body constraint, a special constraint that solves chains of constraints more quickly and which keeps rope more stiff
  • Time of impact ordering – before, order of impact was not considered, leading to the occasional ghost force
  • Air drag and wind – applied to each edge independently based on its velocity and the wind direction
  • Various forms of collision filtering – allows for a simple form of depth based on layers, and things like rag-dolls where certain limbs should not collide
Implementation Specifics

I’ve been getting many questions above specific features and how it all works internally. While I can’t give away all the secret sauce, I will give as much as I reasonably can.

How does the solving work?

The solver uses Jacobi style iteration to solve constraints. Since we use verlet integration, we can directly move particle positions when solving both cosntraints and collisions. In the demo shown in a previous post, constraints are iterated a fixed number of times, while collisions are iterated until there are no more continuous collisions or a maximum iteration count is reached. In the previous demo video, I believe I used 10 iterations for constraints, and a maximum of 10000 iterations for collisions.

The main solver loop is roughly:

 

How do you prevent lock ups?

The lock up problem does exist. However, its only a problem when there are fixed particles or impossible situations involved. For example, if you had two static edges that are moved to trap a particle in between them, it would iterate forever. As far as I’m aware, this is an unavoidable problem, and you simply need some extra logic to account for these situations. My solution was to add a “max iterations” parameter to keep it from freezing. Even without fixed points, it can still take hundreds of iterations sometimes which will cause some delay (as can be seen in the video when i play with the rope). In my latest updates to the solver, it solves more selectively and intelligently to almost completely eliminate this issue.

How does the collision ordering work?

The ordering didn’t make as big an impact as I thought. In the videos in previous posts, there is actually no ordering going on, not even local ordering per particle. I’m solving ALL TOI collisions for each particle! It doesn’t appear to have much of an effect on number of iterations required, just the correctness of the results. Without the ordering, you can shoot a particle at a static line and it will affect things on the other side of the line (which is obviously incorrect). In the latest solver updates, collisions are correctly ordered which fixes this problem.

How do sliding particles from edge to edge not snag on corners?

Gemini sweep tests all collisions, however when resolving collisions, we add a little bit more to the correction in order to keep the particles a certain distance from edges. This amount is so small that its not very noticeable, and facilitates in solving many of the numerical rounding problems when sweep testing. A side effect of having the particles maintain a slight distance from edges is that particles can smoothly slide around without snagging.

What about friction?

I assumed that friction would be an easy addition to the framework.

It was not…

When I first implemented friction, it appeared to work nicely and was actually very easy to add. I applied a position correction to each particle based on how much it moved relative to the edge’s tangent. This works until you have objects stacking. Then, numerical error adds up and you see objects slowly drift apart, and ultimately tumble over. If you don’t care about stacking, that solution will work. What I ultimately spent a week trying to figure out, I need to keep as part of the secret sauce :)

Next…

I wish I had a video to show today, but I am in the process of updating the test bed application using the new API, so it’s not exactly impressive to look at. In the next post, I will show off some of the new features mentioned above, and talk more about whats coming up, as well as the alpha release.