Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!vax5!cnsy
From: cnsy@vax5.CIT.CORNELL.EDU
Newsgroups: comp.graphics
Subject: Triangle/Triangle Intersection
Summary: What's the fastest way?
Message-ID: <18798@vax5.CIT.CORNELL.EDU>
Date: 15 Jun 89 17:06:59 GMT
Sender: news@vax5.CIT.CORNELL.EDU
Reply-To: cnsy@vax5.cit.cornell.edu (Eric Haines)
Organization: 3D/Eye Inc
Lines: 32

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