Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!seismo!esosun!cogen!celerity!celit!hutch
From: hutch@celerity.uucp (Jim Hutchison)
Newsgroups: comp.graphics
Subject: Re: Triangle/Triangle Intersection
Message-ID: <338@celit.UUCP>
Date: 16 Jun 89 17:23:38 GMT
References: <18798@vax5.CIT.CORNELL.EDU>
Sender: news@celerity
Reply-To: hutch%celerity.UUCP@ucsd.ucsd.EDU (Jim Hutchison)
Organization: FPS Computing
Lines: 13

When you are doing 3-D with a lot of objects to be discarded, a good trivial
test is either a sphere test or a bounding cube test.  Choice of which depends
on the object.  Probably for the triangles you'd want to use a cube.  You
might even gain a good deal of performance from sorting them out in a quad
tree (depending on spatial distribution).  That would get you in the O(n)
range instead of the O(n^n) range where you compare everything with everything.
Even if you can't get good groupings, it would be o.k. to have some duplication
in the lower branches of the tree to avoid the n^n cost.  Ofcourse with overlap
you will need to keep some notion of whether or not a node (triangle in this
case) has been processed.  Sounds like a neat problem, what's it for?

/*    Jim Hutchison   		{dcdwest,ucbvax}!ucsd!celerity!hutch  */
/*    Disclaimor:  I am not an official spokesman for FPS computing   */