# point on 3d triangle

This topic is 3023 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

OK. So my question is this: how would I find if a 3d point is on a 3d triangle? It doesn't have to be directly on the plane of the triangle, which is almost impossible due to floating point inaccuracy, but within maybe 0.01 units. So, it would be more of a 3d triangular prism? Well anyway, any help would be appreciated. I couldn't find anything on the web, except for saying to project to a 2d plane, which again I don't know how to do. Thanks in advance.

##### Share on other sites
I'm surprised, that you haven't found anything.

Read through carefully, and you will find it.

##### Share on other sites
And here I was, about to explain how I eventually did it :)

(Do not take anything in the OP of that thread to be fact. I was completely mislead by Princeton's slides)

##### Share on other sites
Quote:
 Original post by _Sauce_And here I was, about to explain how I eventually did it :)(Do not take anything in the OP of that thread to be fact. I was completely mislead by Princeton's slides)
Hehe...
I think that's a good thread, because it follows your learning process of the topic, so it can be a great help to anyone (if (s)he reads carefully).
And some common methods/implementations are shown there.

##### Share on other sites
I didn't participate in the other thread, but the easiest way to determine if a 3D point is on a 3D triangle is to establish a coordinate frame using the triangle and transform the point in question into that space.

Given a triangle with points P0, P1, and P2, compute three vectors (P1-P0), (P2-P0), and (P1-P0)x(P2-P0) (this can be any triangle normal, if you already have one). Plug them into the first three columns of a 3x3 matrix 'M' which will represent our "triangle frame". If we call the 3D point 'P', we can describe it's location with the equation Mp = (P - P0), where 'p' is the transformed point. From here we invert M, and solve p = M-1(P - P0).

Assuming the point is on the triangle plane, we will have p.z ≅ 0 (given some floating-point error), and if the point is inside the triangle, then p.x ≥ 0, p.y ≥ 0, and (p.x + p.y) ≤ 1. If we can't assume the point is on the triangle plane, then there are some extra steps involved :)

##### Share on other sites
try that. It's reasonably efficient.

Quote:
 // test if a point is inside the 3D extrusion of a polygon [v, v_count, normal].Vector PointInPolygonVolume(const Vector& point, const vector& normal, const Vector* v, const int v_count){ assert(v_count > 0); for(int j=(v_count-1),i=0; i < v_count; j=i, i++) { // edge direction of polygon Vector edge(v - v[j]); // normal shooting out of the plane. Vector edge_normal = cros_product(edge, normal); // point relative to edge plane position Vector delta = (point - v); float distance = delta.dot_product(edge_normal); // point front facing edge plane. // point is exterior to polygon. if(distance > 0.0f) return false; } return true;}

You can extend that to any directions (not just along the normal), or in case for example, of a point light source (and find if a point is inside a shadow volume).

##### Share on other sites
All right, thanks a million oliii! I implemented the code and it works! Now I just have to find out why it works...but I'll have to leave that until after I implement Cg...

##### Share on other sites
It's quite simple really. It builds planes for each edge, aligned with the polygon normal (and the edge direction), with the normal facing outwards. If the point is front facing any of those planes, then the point is outside.

1. 1
2. 2
3. 3
4. 4
Rutin
17
5. 5

• 11
• 37
• 12
• 12
• 11
• ### Forum Statistics

• Total Topics
631414
• Total Posts
2999952
×

## Important Information

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!