Not a member yet? Register for full benefits!

Convex Hull Simplification With Containment By Successive Plane Removal

In case the title and pictures above didn't make it clear, we are talking about the construction, simplification, and usage of polygonal convex hulls (the shrink-wrap around your 3D model). The technology presented in this web page could be useful if you are doing collision-detection, physics, object to frustum culling, or projection shadows in the 3D video game you are making.

Try the illustrative demonstration program: hulldemo.exe

A plugin for 3DS Max (V2.5) - put the file hullchop.dlm in 3dsmax's plugins directory. There is no charge - this software is free! I only ask that you just give me some feedback and tell me how useful this is or how it could be improved.

Read the FORMAL WRITEUP that explains what this is all about and how it works.

If you are really interested then dont forget to also look at simplifying the convex decomposition which deals with a different but related issue.

The Demo Program

When you run the demo program, it will:

show the initial model (bunny) for a few seconds.
construct the convex hull.
show the model and the hull alpha-blended around it.
let the user simplify the hull by removing bounding planes (either by user's selection or by using the minimal removal-cost formula).

Note that this demo works best with a 3D accellerated PC computer with working OpenGL drivers. Program tested on Permedia and TNT video cards as well as an InterGraph and a SGI-NT box.

After the hull has been computed, you can select faces by holding down the left mouse button. If you click the right button while a face is selected, then that face will be removed. Dont let go of the left mouse right away, since the coloring of the selected neighbors will show better how the geometry is modified as the former neighbors enclose the region. Rather than selecting faces to remove yourself, by just clicking the right mouse the program picks the best candidate face for removal. So you can just sit back clicking the right mouse repeatedly and watch the bounding planes dissapear. You can take the bunny rabbit right down to about 12 faces or so and maintain pretty tight coverage.

Computing A Convex Hull

Code to compute the convex hull of an object isn't that exciting. If you were locked in a room with no means of escape other than coming up with an algorithm to compute the convex hull of a point cloud, then Im sure you could get out in a few minutes. i.e. Its obvious. So then, why are we here? Read on and learn about why we need hulls, and how we can reduce the hull's polygon count.

The writeup contains more details of where convex hulls can be used as well as how and why we simplify them. The picture on the right shows our rabbit bouncing around in the physics demo I made working here at Bioware. Internally, a convex hull is used in place of the rabbit's geometry to determine when it collides with other objects in the scene. As you might expect, when a separating plane cannot be found between our rabbit and another object, we use the previous frame's separating plane to determine point and direction of impact and then compute the impulses (using the inertal tensors, mass, velocity, ...) to be applied to the colliding objects.

Here, the convex hull is also used for the shadows cast on the walls. This lets us use simple drop-shadows and have them blended (instead of being pitch black), without fear of overlapping patches or z-fighting causing varying degrees of darkness within 1 shadow. With blending, we still see the shadows from 2 different objects overlap but this is what we wanted in order to help us visualize their relative positions. (note that we increase glpolygon offset for each object to avoid z-fighting in the case of overlap.)


In case you missed it, the technique discussed here simplifies a convex polyhedron by the plane-removal operation. This gives us the containment property which is a requirement for producing reduced model representations used by convex piece collision-detection engines and certain types of shadow renderers. Given the efficiency of v-clip (or the the newer stuff the stanford guys are working on) a convex piece must be reduced substantially in order to have a measurable gain in collision detection performance. Although its not difficult to imagine situations where the input model has highly tessellated curved surfaces which would allow for massive reductions while maintaining reasonably tight coverage (accuracy). Shadow applications have a performance gain that is more proportional to the simplification ratio.
Special thanks to Brian Mirtich for useful feedback.

Feel free to send me comments or feedback. If I have made any mistakes anywhere please tell me.

Staff Comments


Untitled Document .