Re: Intersection

[Steve Baker <sjbaker1@airmail.net>]

Dmitry Samoyloff wrote:
> 
> Hello!
> 
> I want to check the intersection of line and triangle (or quad) in my game. I
> also need to know the coordinates of this intersection. Can anybody suggest
> me some algorithms? AFAIK the system of equations must be solved to find the
> point of intersection of line and plain, but I want to check just a polygon
> of the plain.

Firstly, don't even try working with quads - it's too hard.  Split into two
triangles.

There are LOTS of ways to do this.  I think this way is good.

Some of the tests are costly - so do an 'early-out' at each stage if you can.

1) Substitute each end of the line (presuming it's a finite line - you
   didn't say) into the plane equation of the triangle to get the distance
   of the points from the plane.  Since that's a signed quantity - positive
   on one side of the plane - negative on the other, you can compare the signs
   of the two distances.  If both ends of the line are on the same side
   of the plane - then there is no intersection - so punt.  If both distances
   are exactly zero - then your line is potentially 'embedded' in the triangle,
   and no good answer can come out of the math - under these circumstances,
   I pretend that it was a 'miss' and that's always been 'good enough' in my
   applications.

2) You can solve the simultaneous equation of the plane and the line to
   discover where the line intersects the plane.  Now all we need to know
   is whether that happened inside or outside of the triangle.

3) Because the next step is costly - I usually calculate a cheesy axially-aligned
   bounding box around the triangle - if the point lies outside that box then
   it also lies outside the triangle - so we can punt.

4) Compute three more plane equations - one for each side of the triangle.
   Make these planes be at right angles to the plane of the polygon such that
   they run through the triangle edges.  Think of this as three tall fences
   around the edges of the triangle.  Do this in a consistant order so that
   all three planes have normals that face outwards.  (You can form these
   planes by knowing that the cross-product of the triangle's surface normal
   and the normalized direction vector of the triangle edge is the normal
   of the 'fence' plane.  Since you know the normal and one point on the plane,
   (one of the two triangle vertices on that edge) you can figure out its
   equation.

5) Now you can substitute the coordinate of the intersection point from (2)
   into each 'fence' plane equation in turn - just like in step (1), this
   produces a signed distance from intersection point to 'fence'.  If the
   point is on the 'inside' of all three fences - then it lies inside the
   triangle.  (Do steps (4) and (5) for each edge in turn - because you can
   save some math if the point lies outside either the first or second edge
   that you test...every little helps!)

NOTES:

* If you know you need to do this very fast - but on only a relatively small
  number of non-moving triangles - then you can pre-compute plane and 'fence'
  equations and the bounding box for each triangle that you are going to need
  to test against.

* If your triangles are 'terrain' that's never going to form vertical 'cliffs'
  then you can cheat a bit on steps (3), (4) and (5) by doing everything in
  2 dimensions...that's a significant time saving.  Your boundary 'fences'
  can be vertical without upsetting the test.

* I've also played with using the surface normal of the triangle to discover
  in which of the three cardinal directions the triangle is smallest. Then I
  can switch to one of three sets of 2D code depending on which axis I can
  most afford to drop.

If your line-equation/plane-equation math isn't strong enough to follow
these instructions - then you need to go back and learn some more math - you
*NEED* to be really familiar with this stuff if you are going to work in 3D
graphics.  At any event - it's more to explain than I can fit into a reasonable
email.

-- 
Steve Baker   HomeEmail: <sjbaker1@airmail.net>
              WorkEmail: <sjbaker@link.com>
              HomePage : http://web2.airmail.net/sjbaker1
              Projects : http://plib.sourceforge.net
                         http://tuxaqfh.sourceforge.net
                         http://tuxkart.sourceforge.net
                         http://prettypoly.sourceforge.net
                         http://freeglut.sourceforge.net



---------------------------------------------------------------------
To unsubscribe, e-mail: linuxgames-unsubscribe@sunsite.dk
For additional commands, e-mail: linuxgames-help@sunsite.dk