Sign in to follow this  
Phynix

point on 3d triangle

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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[i] - 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[i]);
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this