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.

13 thoughts on “Gemini Physics Development 3: Progress Update”

  1. I’m really curious about friction, especially in a position-based solver; the only way we found to make static friction work was to explicitly track the position of the contact point along the surface tangent, and constrain that using a motorized/limited constraint… replacing a regular friction constraint, which deals with velocity, to a position constraint which varies over time (frame to frame).

    (I’m not sure if this is really mathematically sound, but since velocity is the change of position over time, having a constraint that dealt with a change of position over time seemed like the closest thing to a proper velocity constraint that would work in a position-based system.)

    I’m also still quite curious about how you can manage to deal with collisions inside the solving loop; are you updating your broadphase each iteration, or do you simply use a conservative estimate? (e.g before solving, find all line segments within a large radius around a particle, test the particle vs. that fixed list of segments at each iteration, hoping that the solver doesn’t move things too much, so that the large radius properly captures all segments that will interact with that particle during the current frame).

    We settled on the conservative estimate approach, however this was still quite costly — something like 4-8x as many collisions were being tested as actually happened, but this was the only way we could find to avoid errors while only updating the broadphase once per frame. Maybe we should have optimized our broadphase a bit more instead?

    Anyway, thanks for writing/working on this! I can’t wait for the next post :)

    1. Ok so minor update on friction – my previous statements about not caching is no longer true heh. I thought it was working but I ran into some unforeseen problems. I am now back to caching the current contact position for static friction (like what you described). bleh.

      For broadphase I use a combination of conservative and update. I first conservatively add each edge based on its velocity (expanding its bounding box by that much). After each iteration, if the new bounding box is larger, I remove and re-add that edge. Its good enough for now, but I’ll probably do some more research here later on. My goal is to be able to run 4k boxes in less than 16ms (like in one of my old non-continuous demos). Its gonna be really tough but hopefully its possible

      1. Cool — one problem with the caching method is that it doesn’t seem compatible with rounded surfaces (i.e circles and capsules); at least, we could never figure out a way to make it work properly, because the a contact point’s movement along the surface is no longer a linear segment, it’s a circular arc.

        Do you support capsules as a collision shape? Using static tests for their area and just keeping a rigid linesegment core for continuous tests seems like it might be the best of both worlds, and allow a LOT of objects; boxes are over-rated anyway :)

        1. I decided against explicit circle / capsule shapes – I just didn’t see very many use cases there and allowing them would make the interface and underlying code more complicated.

          I do allow changing the margin on edges, which can sort of emulate circles and capsules (though like you said, the friction wont be exact at the end points).

          If you want true circles and capsules, you can always make it out of a bunch of edges hehe. I have the rigid body type now which adds a mid-phase to its collision detection, so its only a little slower than having native circles / capsules, though not as exact

  2. Hi Chris – this is great work – well done – I’m really interested in this tech – can you divulge how you get the spheres rotating with verlet integration – are you using 2 or 3 sub particles inside the spheres body or some other crafty trick? I did some fluid stuff in the past – and it turned out that MPM fluid is much much faster the SPH fluid – MPM is just a special case of SPH with a fixed grid that replaces the spatial hash. btw how is your hash working or you using a fixed size fixed allocated hash table or a dynamic resizing hash?

    1. Thanks! So for the circles I currently just use a 32 point polygon in the shape of a circle – nothing fancy. However, it is also possible to do like you said and have two points slightly offset from each other with a large margin. I didn’t do it that way just because I didn’t feel like writing special rendering code in my testbed application to handle margins.

      MPM is amazing, I’ve been experimenting with it lately and like you said, it’s wayyyy faster than SPH, handles large pressures very well and just flat out looks better. The only thing I’m having trouble with is getting it to look good at edge boundarys. The way i’m currently resolving edge collisions – simply moving the particle’s position directly – results in grid artifacts. Any thoughts on that?

      My hash table grows linearly with the number of particles / edges, it’s dynamic and gets created from scratch at the beginning of every step.

      1. Hi Chris

        Thanks for the info on the circles – I’m just rolling my own now – I actually tried a verlet based 2D physics engine a few years back but could never get it stable – and seeing your stuff has really inspired me to try it again thx :) I totally hate the code bloat in all these modern physics engines so I’m trying to make it as small as possible and I’m gonna use the cross prod quadratic from the bullet forum as my main collider – wicked clever stuff!

        Cross(C – (A + q(B-A)), Av + q(vB-vA)) = 0 e.t.c

        I’m hoping there’s a faster geometric equivilant – but we’ll see :)

        With the MPM problem – do mean edges as in the edges of the MPM grid or collision with your particle edge system? I just implemented pure MPM and no other collsion – and I just clipped the particles to the grid dimensions by adding a force instead of moving the particles directly – some vids of my mpm running

        http://www.youtube.com/playlist?list=PL8E58048A8FB8EC69

        have fun

        Shabby

        1. Yeah I’m not sure why more people don’t use verlet style engines, they are so much simpler! Granted, there are a few things that are a bit tricky (like friction), but overall much simpler and easier to work with in my experience.

          You’re fluid stuff is really cool! Best of luck with your next engine

          1. Yeah I’m just hitting the friction issues – I got it stable using that cross eqn as the detector and standard impulse response after. Running into major trouble with friction tho – wish me luck 😛

            There’s a “new” SPH system doing the rounds at the moment – u prolly seen it but just in case.

            http://physxinfo.com/news/11109/introduction-to-position-based-fluids/
            http://physxinfo.com/news/11164/physx-research-position-based-fluids-explained/
            http://mmacklin.com/pbf_sig_preprint.pdf
            http://www.matthiasmueller.info/publications/posBasedDyn.pdf

            it’s really nout new – it’s like a rehash of the advanced character paper – but with a different projection system.

            have fun

          2. Yeah friction is tricky, I’m still fighting with it a bit.

            Thanks for the links – very interesting. I wonder how fast this is compared to plain SPH…

  3. Hi Chris,
    Have you made any progress on your physics engine? I’ve been trying to make a similar physics engine for some specialized applications, but I’ve ran into complications involving the nature of continuous collision detection, and it seems you’ve solved it in a more elegant manner based upon the number of lines of code. Your physics engine is the closest thing that I require, but you haven’t made any updates in a long time.
    Do you think you’ll ever get around to releasing it? If not, can you at least release the secret sauce (ie open source)? If you don’t, then I’ll attempt to make “the go-to solution for 2D physics simulation” 😉

    1. Hey,
      I’m still working on the physics engine, but as part of a larger project now.

      However, I am working on a physics tutorial that covers most of the stuff I have been showing on here.
      I’m just trying to get it perfect before I put it up, since there are still a couple “hacks” that I would like to implement more cleanly.

Leave a Reply