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