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.)
Conclusion
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.
|
