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.
The Demo Program
When you run the demo program, it will:
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
Feel free to send me comments or feedback. If I have made any mistakes anywhere please tell me.