Phynix 129 Report post Posted March 12, 2010 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. 0 Share this post Link to post Share on other sites
szecs 2990 Report post Posted March 13, 2010 I'm surprised, that you haven't found anything.thi threadRead through carefully, and you will find it. 0 Share this post Link to post Share on other sites
_Sauce_ 116 Report post Posted March 13, 2010 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) 0 Share this post Link to post Share on other sites
szecs 2990 Report post Posted March 13, 2010 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. 0 Share this post Link to post Share on other sites
Zipster 2377 Report post Posted March 14, 2010 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 :) 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted March 14, 2010 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). 0 Share this post Link to post Share on other sites
Phynix 129 Report post Posted March 14, 2010 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... 0 Share this post Link to post Share on other sites
oliii 2196 Report post Posted March 14, 2010 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. 0 Share this post Link to post Share on other sites