From: mark@cs.ualberta.ca (Mark Green)
Subject: Re: SOFTWARE: Collision detection algorithms?
Date: 	Sun, 18 Apr 1993 22:00:12 -0600
Organization: University of Alberta



>In article <1qmmojINNevt@shelley.u.washington.edu> fair@iss.nus.sg writes:

>> I am hoping that some of you might have done or know of related work
>> that I might be able to review and reference in the paper. 
>> 
>> PS We are also interested if people have found efficient collision
>> detection to be essential in your virtual worlds. If so, we might be
>> able to release the algorithm (at least the executable) in the public
>> domain.

If you use a BSP tree or similar data structure for your models then
collision detection can be done for close to free.  If you are
interested in the user colliding with objects in the environment, then
it can be done in the display loop with very little overhead.  In the
BSP display algorithm you substiture the user's position into the
polygon equation for each polygon in the database.  If the resulting
value is close to zero, the user is close to the plane of the polygon
(but, possibly not close to the polygon itself).  This part of the
computation is free (you are already doing it in the display loop),
and results in a list of polygons that the user may have collided
with.  This list is typically quite small (several dozen polygons for
relatively large data bases), and each polygon can be checked
afterwards for a collision.  The same approach can be done with
objects colliding with other objects.

If you are not using BSP trees a grid data structure similar to that
used in ray tracing can also be used to greatly speed up collision
detection.