Re: Intersection

[Christian Reiniger <creinig@mayn.de>]

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