cnsy@vax5.CIT.CORNELL.EDU (06/16/89)
I have an interesting problem to solve that hasn't been posted here before (I think--someone undoubtedly will find a solution in their comp.graphics files from 1981...). I know how to solve it, but feel that I'm probably missing a number of optimizations and "early exits", hence this posting. Problem: given two triangles defined in 3 dimensions, find the line segment (if any) common to both triangles. Assume that we don't care what happens when two triangles are in the same plane and overlap, and that we don't care about what happens when two triangles share an edge. We really just want to know what interior line segment overlap there is, if any. One other factor: given our testing situation, we suspect most of our triangle pairs will not have any overlap, so there is a lot of chances of quitting early on. My solution is to get the line equation from the two triangle's planes, then test the line against each triangle and obtain the parametric distances of intersection with each triangle's edge. Compare these two pairs of distances and get the common interval (i.e. take the intersection of the two line segments). Simple enough, but I feel I'm missing some optimizations, and was wondering if anyone else might shed some light here. For instance, I could do a test at first to determine if one triangle is entirely on one side of the other triangle's plane: if so, the triangles cannot overlap. I could project the triangles onto various planes to simplify comparisons (2D instead of 3D). I could use some specialized transformations for one triangle's space (like Jeff Arenberg did some months ago here on comp.graphics to simplify ray & triangle intersection). There are enough variables here that I thought I'd check here first before rushing off and trying all the blind alleys. Any ideas or references appreciated, Eric Haines, ...!cs.cornell.edu!eye!erich
hutch@celerity.uucp (Jim Hutchison) (07/23/89)
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 */