November 9, 2012

Convex Hull mesh generation

by groogy

Been working the last week on a convex hull mesh generation algorithm called Quickhull. The usage of these would be mostly for the camera so that it got a smoother movement along walls since a lot of our walls in Project Temporality have bumps on several spots. Without these the camera would jump around a lot in order to not be placed “outside” the walls. The basic idea of generating a convex hull is pretty simple really and when you get it right it’s very little things that can actually go wrong with it. So it’s a pretty rewarding and fast technique to do.

Convex hull mesh generation
Green represents the original collision hull, blue the convex hull. The white lines are the faces normals and the pink cross is the centroid of the convex hull.

As the name of the algorithm implies, it’s based on the common quicksort. The obvious difference is that instead of sorting data you are trying to wrap the given data in a hull. While I searched trying to find any working algorithm I found that all of them had breaking bugs in them or they broke down with an artist provided mesh which made them totally unusable. This caused some pain for me since that meant I had to implement it myself from the start.

It might be based on quicksort but since this is in three dimensions it isn’t as easy as just dividing the vertices in half like you do in quicksort or quickhull for two dimensions. Instead you have to generate a simplex from four points in the point cloud. Here’s what some of the implementations did wrong that I found, they took the first four points in the input list. This might work for random point clouds which are often used to demonstrate the technique but not in an actual use-case with a mesh. The problem that occur is that these four vertices most often create a plane together using two triangles. Well you are not going to get a simplex from that and the end result is a very wonky looking convex hull.

The mesh to the left is the original algorithm I found while the right is my implementation.

As you can see the left one does not work at all, that’s not a simplex, that gives you a plane, an incorrect plane at that as well. My version is the one you should always implement as it gives you a guaranteed simplex if it is possible given the input data. It felt like a ‘duh’ moment when I read the other implementations since this can also fail for them. All you have to do to get a proper simplex is find a triangle, if you have a mesh as input just use the first triangle otherwise use the three first points. The plane these three points or triangle create, do a test to find the first point that is not on the plane. This point will be the fourth point you use to create the simplex. If you have no fourth point that is not on the plane then I’m sorry but the mesh you have is already as convex it will ever be because the entire mesh is a plane. :)

Left is generated with the invalid simplex and right is generated with the correct simplex

When you finally got your initial simplex. That’s when you really have to start playing around with mathematics. The algorithm is based on that each face of the current mesh(which starts as the initial simplex) has a list with points that are in-front of it and not behind it. What you want to achieve is to empty these lists. So you iterate trough the faces until you eventually run out of faces. But during each iteration you take the current face’s vertex that is furthest away from it in it’s outside list, find the edges that let you connect with that point and create a new triangle connected with the neighbours of the current face. Assign new outside points to this newly made face and then at last invalidate the current face so that it is not part of the mesh any more. And voila! You have extended your mesh to cover that one furthest point. Now it just has to be done with the remaining faces and the new ones that are created and eventually you will encapsulate all the points completely in a convex hull.

It’s pretty simple and straightforward when you take a step back and just look at it with a “Alright, what is it that we are actually trying to do here?”. The biggest problem I found was that I had to write a lot of code for edge detection and new triangle creation before I could actually test if anything worked. So I always had a “I hope I didn’t screw up big time now” and of course I did. So in retrospect I should have tried isolated out each separate part and really tested so that the mathematics worked as I intended with data I knew the result of. I for instance got something as simple as side-detection of faces wrong and didn’t know it and was a major delay as that was the last thing I looked at. I had to start writing down the formulas step by step, draw the result on a paper and try to see what was actually happening before I saw that I had done a simple but fatal error with the plane dot test to see which side a point was on. Kind of embarrassing really.

In conclusion, mathematics is a cruel mistress but so rewarding when you finally treat her right.

Share this

Convex Hull mesh generation Convex Hull mesh generation Convex Hull mesh generation Convex Hull mesh generation

Comments are closed.