I am working on a lightmap generator and i need an algoritm tnat will check if line intersects polygon. Can anyone help?

good old algebra i''m going through all of that stuff right now, however here is a pretty good resource:

http://www.geocities.com/SiliconValley/2151/math3d.html

Scott
swojtowicz@gokenora.com
http://www.intercities.tv/swojtowicz



"If you try and don''t succeed, destroy all evidence that you tried."

If you have a large light map and a lot of polygons in the scene, in such a way (as I was convinced on my own experience) it will calculates for 3 years… It is better to try it to make in another way.

That what I have do with light map generation you can see at oscp.pochta.org

I'm working on the exact same thing.

I found some interesting info on Flipcode's message board (this isn't to say you can't find it on this one
Check out this and this.
Also, this is from Ray Tracing News a explains the same algorithm based on barycentric coordinates. I haven't understood it so it annoys me to use it, if somebody can explain this to me I'd be eternally grateful

Edited by - /*Vince*/ on April 15, 2001 8:51:50 PM

quote: Original post by /*Vince*/
Also, this is from Ray Tracing News a explains the same algorithm based on barycentric coordinates. I haven't understood it so it annoys me to use it, if somebody can explain this to me I'd be eternally grateful

I have a page that attempts to explain this method if you want to have a look maybe it'll clarify things for you.
ray triangle intersections
if you have any questions on these pages let me know.
http://tannara.net/


Edited by - avianRR on April 15, 2001 12:54:40 AM

OK, I didn't know a cross product equaled the parallelogram area.
But then I'm still missing nothing, why are dot products used in the areas (or barycentric coordinates) computation ?

////////////////////////////////////////////////////////
//from the Ray Tracing News article
1
/|\
/ | / | / t | s / _-P-_ / _- -_ /_- r -_3---------------2

N = triangle normal = (vec(1 2) cross vec(1 3))

s = ((vec(1 P) cross vec(1 3)) dot N) / length N

t = ((vec(1 2) cross vec(1 P)) dot N) / length N

r = 1 - (s + t)
//////////////////////////////////////////////////////////

N is actually 2 times the triangle area, but that's okay since the values of s and t also equal double the sub-areas (2/2 = 1).

BUT I don't understand the usefulness of the 2 dot products

Edited by - /*Vince*/ on April 16, 2001 4:46:20 AM

OK, forget the ASCII art (damned HTML)

the dot product is simply the sum of the parts of the two vectors multiplyed together. There useing it as a shortcut for finding the length of the vector. It''s easier to write but makes the formula harder to figure out. A difficulty you discovered by not knowing why they were useing a dot product when the theroy behind it dosn''t.
The code I wrote dosn''t use any dot products, here''s a snipit of part of it that shows what I''m doing...

Temp1 = p3 - p1;
Temp2 = P - p1;
Temp1 = Temp1.Cross(Temp2);
s = Temp1.Magnatude();

...

rst = r + s + t;
rst -= a;
if(rst <= -0.000001*a || rst >= 0.000001*a)
return false;

Any more questions?

Yes of course, it''s so obvious now, but thanks a lot anyway

I checked your site, it''s starting well, congrats! I''m working on a 3D engine and I''m regularly having trouble finding out what maths formula to use when (finally got a Quake-style camera to work though, woohoo!)

Thanx again for your help