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

*To*: linuxgames@sunsite.dk*Subject*: Re: Intersection*From*: Steve Baker <sjbaker1@airmail.net>*Date*: Mon, 15 Jan 2001 22:36:50 -0600*Delivered-To*: mailing list linuxgames@sunsite.dk*Delivery-Date*: Mon, 15 Jan 2001 23:39:59 -0500*Mailing-List*: contact linuxgames-help@sunsite.dk; run by ezmlm*Organization*: Steve at Home*References*: <01011603320402.03284@sleepwalkers.ru>*Reply-To*: linuxgames@sunsite.dk*Sender*: steve@belegost.mit.edu

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**:**Intersection***From:*Dmitry Samoyloff <dsamoyloff@mail.ru>

- Prev by Date:
**Intersection** - Next by Date:
**Re: Is this list still alive?** - Prev by thread:
**Intersection** - Next by thread:
**Re: Intersection** - Index(es):