John W. Barrus (barrus++at++merl.com)
Tue, 9 Nov 1993 13:33:38 -0500
The following is not a Performer specific answer, but has to do with
collision checking in general. I do not know about Performer specific
object collision detection (in fact, I don't even know if Performer does
object collision detection!)
You must have each object in the same coordinate system to do collision
checking. However, you don't have to actually test each object to
determine whether or not that object is intersecting another object. There
are many methods for detecting collisions based on bounding boxes and
spheres, and simulation techniques that use information already calculated
to determine whether or not two objects intersect.
When two objects are very close together, you _have_ to do a vertex, edge,
face check to determine whether or not they intersect and that check must
be done with both objects in the same coordinate system. The trick is
determining when they are close together.
Bounding spheres:
Choose a point (not necessarily a vertex of the model) that is
approximately in the center of the object. Now choose a radius that is
large enough for the sphere it describes to completely enclose the object
(can be calculated using the vertexes of polyhedral objects). To check two
objects, simply check the distance, d, between the two center points (Pa
and Pb). If d is greater than the sum of the two radii (Ra and Rb) then it
is impossible for the two objects to be intersecting. Only do a detailed
intersection check when
(Pa - Pb) < (Ra + Rb).
The nicest thing about using bounding spheres for collision checking is
that the transformation of a sphere from one coordinate system to another
simply requires a translation of a single point. Much much cheaper than
transforming the whole object for every check.
Bounding boxes:
Same idea, only use the x, y, and z mins and maxes to construct a box.
If
Axmin > Bxmax OR Axmax < Bxmin OR
Aymin > Bymax OR Aymax < Bymin OR
Azmin > Bzmax OR Azmax < Bzmin
you know that the boxes cannot intersect and the objects can not be
occupying the same space. Boxes are slightly more complicated because you
have to be conservative when you transform them between coordinate systems.
The box may grow with rotations, but it should not be permitted to shrink.
The fact that the box changes at all is because it is constructed aligned
with the axes. Rotations misalign the box and it must be realigned by
creating a new box that completely encloses the transformed box.
Unfortunately, I can't find any good discussions of collision detection so
if anyone else has some reading suggestions, that might help here. The
above is a very terse description of just a few possible options. (The
Graphics Gems series - GG, GG II, and GG III - do discuss calculating
bounding spheres and intersecting rays with spheres and axis-aligned boxes
for ray-tracing applications.)
One other thing to remember: When comparing two objects, it is not
necessary to transform both objects into some "world" coordinate system.
Often, it is only necessary to transform one of the objects into the
coordinate system of the other object to do the test. If each object has
1000 vertices, you will save 1000 3x1 X 4x4 matrix calculations at the
expense of one 4x4 matrix inversion and one 4x4 X 4x4 matrix multiply.
>
>IS IT A GOOD IDEA TO DO COLLISION CHECKING USING PERFORMER?
>The collision checking is done for each object moving
>in the scene against the other object belonging to the
>same scene.
>
>
>--Ricardo Galli
>Universitat de les Illes Balears
>Palma de Mallorca - SPAIN
>Tel. +34 71 17 3201
>FAX. +34 71 17 3003
>e-mail. gallir++at++anim.uib.es
>+--------------------------------------------------------------------+
>|The nice thing about standards is that there are so many of them to |
>|choose from. |
>| -- Andrew S. Tanenbaum |
>+--------------------------------------------------------------------+
-------------------------
John Barrus barrus++at++merl.com
Mitsubishi Electric Research Laboratories 617.621.7535 (VOICE)
201 Broadway 617.621.7550 (FAX)
Cambridge, MA 02139
This archive was generated by hypermail 2.0b2 on Mon Aug 10 1998 - 17:50:05 PDT