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

*To*: linuxgames@sunsite.dk*Subject*: Re: Intersection*From*: Christian Reiniger <creinig@mayn.de>*Date*: Tue, 16 Jan 2001 11:52:45 +0100*Delivered-To*: mailing list linuxgames@sunsite.dk*Delivery-Date*: Tue, 16 Jan 2001 05:53:27 -0500*In-Reply-To*: <01011603320402.03284@sleepwalkers.ru>*Mailing-List*: contact linuxgames-help@sunsite.dk; run by ezmlm*Organization*: LGDC (http://sunsite.dk/lgdc/)*References*: <01011603320402.03284@sleepwalkers.ru>*Reply-To*: linuxgames@sunsite.dk

On Tuesday 16 January 2001 01:32, Dmitry Samoyloff wrote: > 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 You're lucky - I had to give a talk on this some weeks ago at uni :) I copied the slides tp http://sunsite.dk/lgdc/tmp/raytracing/ Unfortunately they're in german, but I'll translate the important part (ray-trinabgle intersection) here. Look at the slides for the formulas. Ok. The in this context interesting part is chapter 2.6 (http://sunsite.dk/lgdc/tmp/raytracing/i_triangle-1.html) Some basic translations: und = and Dreieck = triangle Punkt = point Ortsvektor = vector from (0,0,0) to point (slide1) The slide starts with a definition of a triangle as set of all points t(u,v) with (formula1) and (formula2) The first formula can also be written as t(u,v) = u*e1 + v*e2 with e1 = v2-v1 and e2 = v3-v1 (i.e. e1 and e2 are the vectors from v1 to the other two vertices) In other words: with this t is described as point in the local (2dim) coordinate system of the triangle with (so-called barycentric) Coordinates u, v (the same ones that are used for texture mapping etc) (slide2) Note: The ray equation I use there is p = r0 + t*rd with r0 = starting point of the ray, rd = direction vector, t = parameter Ok, now if you set rayeqn = triangleeqn you get (formula1). Transformed this becomes (formula2) and with application of Cramer's rule you get (formula3) with vectors as described in (formula4) (slide3) There's something in linear algebra telling us (formula1), so we can write our equation as (formula2) with vectors as described in (formula3) (slide4) Here is a detailed look at how computationally expensive the algorithm is. The steps are listed in the correct order, and the ones marked with "*" can lead to an early (no, we didn't hit) result. Some terms here: Berechnung = Calculation Nenner = denominator Schnittpunkt = intersection point Vergleich = comparison Summary: With the formula given in (slide3) you can quite easily and quickly compute the intersection (the algorithm is "noted" in (slide4)). On getting the intersection coordinates: Simply insert the value of t you get into the ray equation. I hope that helped -- Christian Reiniger LGDC Webmaster (http://sunsite.dk/lgdc/) What luck for the rulers that men do not think. - Adolf Hitler --------------------------------------------------------------------- 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:
**Re: Is this list still alive?** - Next by Date:
**Re: Collision detection Re: Is this list still alive?** - Prev by thread:
**Re: Intersection** - Next by thread:
**Re: Intersection** - Index(es):