Archived

This topic is now archived and is closed to further replies.

DevLiquidKnight

Calculating if a point is within a triangle?

Recommended Posts

sopose that you have the triangle (v1, v2, v3) and the point p

then if

(v2-v1)x(p-v1), (v3-v2)x(p-v2) and (v1-v3)x(p-v3) have all the same sign the point is in the triangle.

x is the vectorial product

// naher

Share this post


Link to post
Share on other sites
Right, so to expand the half-plane test rule, all non-zero numbers have to be the same sign. If two of the numbers are zero though, then it''s automatically inside the triangle, because that means it''s colinear with two of the sides (i.e on the corner).

Share this post


Link to post
Share on other sites
Just a quick tip:

If you''re scanning through lots of triangles to see if the point falls within them, it can be handy to use a quick test to test if it DOESN''T lie in the triangle.
E.g. if x-value of the point is less than the x-values of the all the triangle corners, then you can skip that triangle.
Then you only use the proper point-in-triangle stuff if the quick tests pass.

I''m sure you get the idea. This should speed it up a little.

Share this post


Link to post
Share on other sites
Each "variable" would be the distance from the point to each side respectively. The distance from the point to a side is defined by:

DotProduct(point, sideNormal) - DotProduct(sideNormal, known point on side)

But like tuita said, always perform the trivial tests first so you can possibly eliminate superfluous calculations.

Share this post


Link to post
Share on other sites
Do any of you have a basic c++ function(perferrably) or even any functions in any languages that calculate dot product efficently yet optimal. I don't know dot prodcut and it just confuses me to look ill look around to see what i can find but if you do it will be helpful. Or even just a function to test if an object is in a triangle.

[edited by - DevLiquidKnight on October 4, 2002 11:37:33 PM]

Share this post


Link to post
Share on other sites
Dot products can be calculated for 2D-lines.

p . q = (px * qx) + (py * qy)

So, in C/C++ code it becomes something along the lines of this:

float dot_product(float x1, float y1, float x2, float y2)
{
return x1*x2 + y1*y2; // (x1,y1) . (x2,y2)
}


For the 3D case it''s similar, just throw the Z-coordinates in there as well.

Share this post


Link to post
Share on other sites
Exactly how to do what? He gave you the formula for the dot product (code even), and I gave you the formula for finding what side the point is on.

Do you need to know the side normal? Since this is 2D, we can actually fabricate a vector that is used in the cross product to find the normal. So let''s say you had two points, (1,1) and (10,4). This vector is then (9,3). However, since the cross product is a 3D operation, we add a Z coordinate, 0 -> (9,3,0). But now we need another vector. This is the vector that can be fabricated. We create a vector that has the same X and Y, BUT we give it a Z value to make it perpendicular to the 2D plane, and thus the first vector -> (9,3,Z), where Z is any non-zero number. We can then take the cross product between the two vectors to get the perpendicular vector. We normalize it to get the normal. However, be wary. The cross product returns a resultant vector using the right hand rule, and combined with the fact that your fake Z can either be positive or negative, you have to make sure you know which way the normal will face.

Share this post


Link to post
Share on other sites
solution:

structure triangle
{
CVector Points[3];
CVector Edge[3];
}

Triangle:ointIsIn(CVector CheckPoint)
{
Edge[0] = Point[1]-Point[0];
Edge[1] = Point[2]-Point[1];
Edge[2] = Point[0]-Point[2];

DistanceFromEdge[0]=Point[1]-(CheckPoint-DotProduct(Edge[0],Point[1]-CheckPoint));

//same ... for the 2 edges left.

if(DistanceFromEdge[0] < 0 && DistanceFromEdge[1] < 0 && DistanceFromEdge[2] < 0)
return 1;
else
return 0;
}

hey guys... check if there are an error in the DistanceFromEdge Formula... I wrote this witout test it, but I know the principe is correct.

Share this post


Link to post
Share on other sites
hmmm.... I found that on the net and I tested it.

D3DVECTOR closestPointOnLine(D3DVECTOR a, D3DVECTOR b, D3DVECTOR p)
{
// Determine t (the length of the vector from ‘a’ to ‘p’)

D3DVECTOR c = p - a;
double d = Magnitude(b-a);
D3DVECTOR V = Normalize(b - a);
double t = DotProduct(V,c);

// Check to see if ‘t’ is beyond the extents of the line segment

//you dont need these 2 lines for DistanceFromEdge
if (t < 0) return a;
if (t > d) return b;

// Return the VECTOR between the nearest Point on the line and ''p''

V*=t;
return (a + V)-p; // nearest Point = a + V
}

Share this post


Link to post
Share on other sites
CVector Edge is a usefull data.. instead of Point[1]-Point[0], write Edge[0]...

I use that in
DistanceFromEdge[0]=Point[1]-(CheckPoint-DotProduct(Edge[0],Point[1]-CheckPoint));

Do you know how to use the very useful DotProduct in geometry?

Share this post


Link to post
Share on other sites
I saw an algoirthm somewhere that said to take a vertical ray and draw it straight down from the point. (Any direction, actually)

If that ray intersects exactly one of the segments that makes up the triangle, the point is inside.

If the ray exactly intersects a point of the triangle, if the point lies ON a segment, or the ray coincides exactly with a segment, then these are special cases, but most cases are covered by the above.

I'm not sure how well this works in 3D space. The ray you draw would have to lie on the same plane as the triangle.

Just an idea.

I suppose if you wanted to evolve the algorithm for 3D, you could take any arbitrary plane that passes through the point, and if exactly two of the segments intersect the plane, the point is inside. Blah, no, that wouldn't work. Arrgh!


[edited by - Waverider on October 7, 2002 10:23:05 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Fantasio
How I put an image with my message ??


I''m not sure what the HTML code is for an image, and actually that may be disabled now due to some destructive individuals who seem to want to attack the site in various ways.

But in theory I think you could just put standard HTML code to link in an image. Now, you do have to host the images on your own public website----gamedev doesn''t provide a way for you to upload and store images on our servers.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites