Hulls

If we are writing a modern rigid body physics engine in C++, we should carry Quickhull in our backpack. That means: either use qhull or implement one from scratch.

It takes some time to learn how to use the qhull library. The implementation itself seems very reliable. The data structures exposed to the user, however, are somewhat difficult to digest. Perhaps because it was written many years ago. The other problem might be that is not very fast for run-time execution. However, qhull is a must for educational purposes as it contains a lot of computational geometry gems and related algorithms. For example, convex hull simplification.

Some time ago I decided to implement my own version of Quickhull. The mission objective was to design and implement a convex hull builder that could create convex hulls at run-time. Clean interface as a secondary objective. Quickhull is a very well studied and understood algorithm. These tasks weren’t very hard to accomplish.

The source code for my version is at Bounce official repository on GitHub. This version fixes all the geometrical and topological errors that can appear during the convex hull construction. Therefore is reliable. It’s fast: single memory allocation and pooling. The hull is a half-edge mesh. Everyone has heard of it. These topics are presented here.

I encourage one to rewrite an existing algorithm putting some of its personal design decisions in order to make it more fast, reliable, and user friendly. The results are most of the time rewarding.

This post was somewhat a delayed announcement in form of a blog post.

Building a Half-Edge Mesh from a Triangle List

The problem is to build a polygonal mesh from a triangle list efficiently. A solution is important specially when building or testing physics engines. The method below shows a possible solution. This can be done without needing the additional storage and processing cost of keeping a list of half-edges for a given face during its addition which would be linked at the end of the addition in that case.

Continue reading

Distance Constraint Derivation

Sometimes it’s desired to have a distance constraint. That constraint assumes a choosen separation distance for two points fixed in two bodies. I’ve written a derivation for it in 3D and shared here. An implementation should be pretty simple since we have minimally one Jacobian and solve a 1D linear system. Here is an example which you can use in your own projects.

Continue reading

Fast Segment-AABB Collision Detection

Let’s say we need to compute the intersection point and normal from a line segment to an axis-aligned bounding box (AABB) bounds, and we neither want to perform expensive plane computations nor keep the AABB boundaries as an intersection of 6 axis-aligned planes (as it is a waste of memory). A quick way to do that is by evaluating the slab plane equation for each axis-aligned plane of the AABB.

Continue reading