[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

# Re: Intersection

```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

```

• References: