3D Physics Engine Pt. 5

Hey folks! I’ve just published the new version of elm-physics and realized that it has been almost a year since the last update. I am going to take this as an oportunity to write another progress report. You can find all the posts here.

This blogpost is going to focus on the following things:

  1. Performance improvements
  2. Better inertia support
  3. New shape types
  4. What’s next

Performance Improvements

Since the last performance improvements I have identified more hot places in the code using Chrome Development Tools. I then inlined some code blocks and reduced object allocations. I also removed more List.foldl and List.map occurences in favor of tail optimized recursions. A tail optimized recursion in Elm is compiled to a while loop in JavaScript with function arguments becoming a bunch of local variables. This makes it pretty fast! Besides these simple improvements, I have made three rather complex ones.

One of them was improving the collision algorithm between two convex polyhedrons. In the last part of collision, two faces from colliding shapes are being clipped against each other. The former implementation used adjacent faces for clipping, the new implementation does not need this, it uses planes, that are perpendicular to the clipping face. Now it is following the else part in the original Cannon.js code. My understanding is that this was transpiled from the bullet engine code where the BLA1 was replaced with true. Maybe there is more to this, because the maintainers of cannon-es, the continuation of Cannon.js, have deleted the else part as dead code. However this has been working fine so far in elm-physics and haven’t noticed any issues.

Another improvement was to further reduce slow Array.insert operations in the solver. Basically the solver iterates over a list of equations of pairs of bodies. When an equation is processed, both bodies need to be updated and thus written to an immutable array. I had already done an improvement in this part of the solver before. I grouped the equations for each pair of bodies, this way I could update two bodies in the recursion, and then finally write them to the array after I looped through the whole group. In this case I took this a little further. I noticed a pattern of how contacts between pairs of bodies are generated for all combinations of bodies. If a single body collided with two other, it would be likely for it to be present in subsequent equation groups. I decided to keep this body on the recursion and write to the array only when the next equation group doesn’t include this body.

The last improvement was to cache the shape definitions (faces, vertices, edges, etc.) in the world coordinates, to avoid having to transform them from the body local coordinates in all other places in the code multiple times.

The result of this work — 125 boxes are now simulated at 60fps! This is quite fast for an engine where each simulation cycle creates a new immutable copy of the world.

Better Inertia Support

The moment of inertia tensor is what affects the rotational movement of a body. It basically defines how the mass is distributed. This is one of the things that elm-physics takes care of, so that you don’t have to worry about it! The original implementation had an oversimplified calculation of the moment of inertia tensor. It basically took a bounding box and assumed it was a solid body. The new implementation uses the right formula for each primitive shape, and also properly aggregates inertia for a compound body made of multiple shapes.

I didn’t simply decide to work on this myself, but was encouraged by Ian Mackenzie, and the work of folks from McMaster Outreach who used elm-physics to build a programming playground for students, in which they could assemble a space ship and then control the thrusters. I wasn’t asked to improve inertia, but thought that it would make simulations more realistic.

It took a lot of time to learn the physics and get this right, including solving the bug, that took about a month to figure out. I had to write pretty interesting tests too. The result is very rewarding and noticeable even in some of the existing demos. For example, try flipping the table with a mouse — it is more likely for it to land upside down now than it was before!

New Shape Types

The previous version of elm-physics only supported blocks and spheres. Even though it was possible to build demos with just these shapes, that was pretty limiting. The new version has two new additions.

The first new addition is the cylinder shape, that was contributed by Martin Stewart! It is tremendously hard to implement collisions for a proper mathematical representation of a cylinder, so this implementation simplifies it as a convex polyhedron. It also lets you choose how much you would like to subdivide the sides.

The second kind of shape — unsafe convex — is something that I am very excited about. This opens up the internal API for folks who want to use their own convex shapes. The input for the constructor is the same TriangularMesh type, that is used in elm-3d-scene too. The reason why it is called “unsafe”, is because there are a few gotchas: it has to be convex, it has to be watertight, and the faces should have the correct winding order of vertices.

But don’t worry, there are existing tools that let you create proper shapes — like Blender, where you can select vertices and enclose them in a convex polyhedron. And if the result mesh has too many faces, you can also apply the decimate modifier, that would simplify the collider shape and make the physics simulation more performant.

Up until recently, there was no easy way to import things from Blender into elm-3d-scene. Thankfully to the elm-obj-file package, we can now export 3D meshes from Blender, and then render and simulate them with Elm. It is even possible to store both visual and physical representations in the same OBJ file, and then write a decoder for both, like it is done in the Duckling demo.

The source code for this demo is just 256 lines of Elm. I am excited what folks can build using these tools!

What’s next

Ian Mackenzie gave a pretty nice overview of what’s next in 3D in Elm at London Elm Meetup. As you can see, most of elm-physics items have been implemented.

Continuous collision detection, a mechanism to prevent bodies moving at high velocities to pass right through each other, is something that is still pending. It would be nice to implement this at least for spheres. If you would like to collaborate with me on this functionality, please get in touch!

Something that is almost complete is the raycast car demo, that implements manipulations on top of elm-physics to simulate a car. It shoots rays and applies impulses where they hit the ground. This way it is possible to simulate suspension, that results in a more smooth behaviour than the current rigid version that uses hinge constraints.

You might have seen a variation of this demo in Evan’s ICFP keynote, that was built by Luca Mugnaini. This example used the demo rendering code from elm-physics examples. I plan to make a package that implements the pluggable raycast car behavior, and then build concise examples that render with elm-3d-scene.

Last but not least, the topic of the next Elm Game Jam is going to be “3D”. We will be organizing this together with Ian. Stay tuned for the official announcement!


That is so cool, I played with the table demo for a lot longer than I had planned to, great work!

1 Like

Amazing project, work, and posts! :raised_hands:

Out of curiosity, do you know what the performance difference with the cannon.js library for something like the boxes demo?

I browsed around but couldn’t find a similar example to check (closest were sphere stacking, and sph (which I don’t know what it is)).

1 Like

I don’t know this, but I am very curious. Would you like to setup the same scene of 5x5x5 boxes in Cannon.js to help figure this out?

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.