Hi, I''ve been using the standard plane-ray intersection test to do some simple ray-tracing... but I now need to know if a given point-of-intersection is actually in the triangle... I know that the point is on the surface of the triangle, I need to know if it''s within the boundaries... I have: • the 3 vertices making up the triangle (in 3D space) • the collision point (in 3D space) • the plane coefficients/normal etc... I''ve got a feeling I''ll need "barycentric" coordinates - but I dont know how to use the formula/algorithm... could someone tell me how to sort this out?? many thanks, Jack;

I''ve seen this topic so many times here,

you''d think people in this age would be smart enough to search before posting any such message

or do you just want attention

quote:

---

Original post by Anonymous Poster
I''ve seen this topic so many times here,

you''d think people in this age would be smart enough to search before posting any such message

---

Actually, I think that as the barriers to entry are lowered the average intelligence in any field will decline (as the tools become more available and more automated). You''ll find more and more people who don''t understand netiquette, who don''t understand math and who don''t understand programming.

That said, here''s my two pieces of advice to jollyjeffers:
1.) Search the forums for "inside tests."
2.) Since you know they lie in the same plane, project that plane as xy and do a 2D inside test.

"I''ve seen this topic so many times here,

you''d think people in this age would be smart enough to search before posting any such message

or do you just want attention "

- Hey, screw you pal. I did search the net for what I was looking for (google) - it''s how I found the code for the intersection testing... HOWEVER, WHAT I DID NOT FIND was what I just asked for. Having not found it, I thought someone else might be nice enough to help me out (and it obviously isn''t you). I spend a considerable amount of time helping other people out (I run my own website, and get asked many questions), and I never ever send a reply as stupid as yours...

Anyway, Oluseyi - Many thanks for pointing me in the right direction - it''s much appreciated.

Jack Hoxley.

jollyjeffers >> Never mind that idiot !

Folks,

Careful with the language please.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Here''s a good web page reference for point-in-polygon strategies, from the author of "Real-Time Rendering".

http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Well, if the triangle is facing you.. then the points should be clock-wise (or counter-clock wise depending on how you do your back-face stuff)... but anyways. If you know that the triangle is clockwise...

P1



P2 P3

Now if you put another point in there... and split it into 3 triangles..

P1

P4

P2 P3

If P1->P3->P4 makes a clockwise triangle & p4->p3->p2 makes a clockwise triangel & P1->P4->P2 makes a clockwise triangle... then the point is within the boundries.. if any of them make a counterclockwise triangle... then it is outside the boundries. P4 is your Point of Intersection, while P1,P2,and P3 are your triangle points. If your triangle is counterclockwise, then the inverse would be true.. if all 3 triangles created are counterclockwise then it''s inside, if any are clockwise it''d be outside.

Hope this helps.

Billy

BillyB@mrsnj.com

Dope, the spaces didn''t come out...

First Diagram

..........P1
........./..\
......./......\
...../..........\
.../..............\
P2-----------------P3

Second Diagram

..........P1
........./.|\
......./...|..\
...../....P4....\
.../.../......\...\
P2../____________\..P3

Repost: something went wrong in the diagrams after I edited my post. Weird! Does anyone know what caused that?


For all you non-HTML people, to do proper ASCII art, place it between <pre></pre> tags. Ie:
<pre>
P1
/|\
/ | \
/ P4 \
/ / \ \
P2-------P3
;</pre>
Becomes:

    P1    /|\       / | \     / P4  \   / /   \ \ P2-------P3

Now on the problem at hand, since it''s for a ray-tracer, you''ll probably want the barycentric coordinates for the intersection point. If any of the barycentric coordinates is below zero or over one, the point is not in the triangle. If the point is in the triangle then the barycentric coordinates allow you to do linear interpolation between the three vertices practically for free.

I suggest searching for ''signed area of a 3d triangle'' algorithms, because such an algorithm can be used to calculate the barycentric coordinates of the intersection point like this:
w1 = signed area of (P4, P2, P3) / signed area of (P1, P2, P3)
w2 = signed area of (P4, P3, P1) / signed area of (P1, P2, P3)
w3 = signed area of (P4, P1, P2) / signed area of (P1, P2, P3)

I hope that is of some help.