From: broehl@watserv1.waterloo.edu (Bernie Roehl)
Subject: TECH: Collision detection -- a possible new approach
Date: Wed, 4 Mar 1992 14:52:23 GMT
Message-ID: <1992Mar4.145223.17869@watserv1.waterloo.edu>
Organization: University of Waterloo



Just thought of a new idea for collision detection.

As we talked about earlier, polygon-based collision detection is very
expensive.  Collision detection based on CSG representations of objects
is cheaper, but still involves a fair amount of computation (and complexity,
since routines must be written for each possible pair of collisions between
CSG primitives; e.g sphere-sphere, sphere-cylinder, cube-cone, etc etc).

It occurs to me that a "hybrid" approach may work better.

Assume that all the objects in your VR start out in a CSG form, and are
polygonalized when they're brought in.  Thus every object has both a CSG
representation and a polygon representation.

Now, object A can only collide into something if it's moving; so whenever
you move object A, you check for collisions with each of the other objects
(call them B, C, D etc).  Obviously, you do distance-based tests first to
eliminate most objects; the expensive part is the nitty-gritty detailed
intersection testing.

My idea is that you would use the polygon rep of object A (the one that's
moving) and check it against the CSG rep of each of the others.  Thus you
only have to worry about poly-to-primitive intersection, which is simple
and can probably be made quite cheap.  Certainly point-in-CSG-object is
very cheap and straightforward, and edge-intersecting-CSG-object is the most
primitive operation in a raytracing package (note: raytracers are only slow
because they have to deal with so *many* rays, not because the test itself
is inherently expensive).

The only problem is, points and edges aren't enough.  A CSG cone intersecting
a polygon without hitting any of the poly's edges would go undetected.  You
could conceiveably reverse the roles of the two objects (i.e. use the CSG rep
of A and the polygon reps of the others) and thereby cover all those
possibilities, but doing both may double your computation time (at least for
those objects that failed to intersect using the first version).

A better approach may be to look at polygon-to-CSG-primitive intersection; if
it can be made fast and cheap, we may have a good basis for collision
detection.

Thoughts?

-- 
	Bernie Roehl, University of Waterloo Electrical Engineering Dept
	Mail: broehl@sunee.waterloo.edu OR broehl@sunee.UWaterloo.ca
	BangPath: uunet!watmath!sunee!broehl
	Voice:  (519) 885-1211 x 2607 [work]