Minor Gripe

2019-08-04 -- ERP Update: Change of course, problems, new adventures

Chris Ertel

Current State of the Elixir Rigid Physics Library

Create stub physics engine server in Elixir as a GenServer(done)
Create visualizer for engine state using Three.js and Phoenix Channels (done)
Add first body type to physics engine: boxes! (done)
Add framework for doing dynamics sans collisions in engine (done)
Add collision detection framework for finding contact manifolds (abandoned)
Add collision restitution code
Add friction
Add joints and motors
~~Add more types of bodies beyond boxes~~ (we’re going full convex hull, God help me)
Figure out how to spread the simulation across multiple processes
Figure out how to spread the simulation across multiple nodes

Changing course

So, I kinda need a break on this. It’s been about ten weeks of banging on it, and the last few haven’t been nearly productive enough–my experience is telling me I need to either switch sub-tasks, or pull the ripcord entirely and switch to something else while I wrap up here at RC.

I have enough progress on the collision detection (more on this later) to go ahead and start working on collision restitution, but I need to read up a bit more on whether or not that’s going to be another rabbit-hole. If it is, I think I’m just going to go back to my personal search engine project. Hell, even writing that fill me with such a feeling of relief that I might just go ahead and do it.

The one thing that I am quite sure of is that if I keep grinding along on this hull-hull intersection code I will be upset with myself later for burning my last week on it.

Remarks on hull-hull code

Okay, so, as hinted at by previous write-ups, I’ve been stuck on the GJK algorithm. Things that have gone wrong in the course of working on this:

Finding a talk that everybody references, but which is a “bastardized” version of GJK not useful for finding distances–leaving that instead for a SAT approach or EPA.
Finding a very approachable tutorial…that concludes with a gigantic switch statement and goto blob that was really annoying to translate to Elixir–and then realizing that it was the same approach that was “bastardized”!
Finding an utter lack of resources on the 3D GJK algo. Everybody points to the same Catto talk from 2010 and says “lol yeah it’s trivial to extend to 3D, git gud”. Spoilers: it’s not quite a straightforward port. I swear I’ll write a subsequent post about it when I get it right.
Realizing that I’d been operating off of a collection of slides from Catto2010 that lacked the speaker notes and explanation, leaving out some critical info. FML.
Losing a couple of days after making an incorrect assumption about the way that we can back out the Voronoi regions of a tetrahedron from Barycentric coordinates–turns out you need those of the constituent edges and faces as well as the volume ones.
I’m pretty sure that the entire week spent on the tetra thing (which I thought was important due to its role as the 3-simplex in the evolution of a GJK pass) quite possibly was a neat thing that was a waste of time. Like, a fascinating sub-problem orthogonal to actual progress. Occupational hazard, I guess.
Numerical precision issues, even with the doubles that back numbers in Elixir, are totally a thing. I chased down some annoying behavior where a barycoord was near (but critically not at!) 0. In general I question the robustness of a lot of the work I’ve done, but if I start worrying too much about that now I’ll never write another line of code on the damned thing.

I’ll probably post up the test data for the nearest-point-on-tetrahedron code, in case anybody else decides to pursue that in their own work.

Other useful road-mapping spoilers, that ultimate forced my hand on this:

GJK proper is about finding the distance from a point to a convex hull. This is extended to “normal” GJK by having that convex hull be the Minkowski difference of your two hulls–and a neat little point is that the distance between the hulls is the distance of the origin to that difference.

However, even with that information, if the origin is inside the difference, you need to resort to some other algorithm (SAT, EPA) to figure out how deep the penetration is. This is annoying.

Further complicating things is that you have both the cases of deep and shallow penetration: is the center of the hull contained inside the other hull, or is the overlap just in the surface? Even further, at least with polyhedra, there’s also the question of edge vs face collision.

It’s just a whole lot more work for me to do without screwing it up and I don’t have the time right now to finish it to the level of quality I’d like. :(