Calculating the nearest point on a plane to your
Author
Apologies: My maths is not all that good, though it is getting better through study.
If I have a triangle ABC and a point in space D, how do I calculate the nearest point in ABC to D?
D.V.
Carpe Diem
That''s not that difficult:
(small letters are Vectors, capital are Points)
(a1, a2, a3 are the x, y, z values of your vector or point)
Calculate the normal for your triangle:
u = a - b
v = a - c
/u2*v3 - u3*v2\
|u3*v1 - u1*v3| = n
\u1*v2 - u2*v1/
Now you have to normalize your vector:
n° = n / sqrt(n1^2 + n2^2 + n3^2)
The distance between the triangle and the point is:
s = n1(p1 - a1) + n2(p2 - a2) + n3(p3 - a3)
ignore the sign of ''s''! (abs())
I hope that helps and is right!
Yesterday we still stood at the verge of the abyss,
today we''re a step onward!
(small letters are Vectors, capital are Points)
(a1, a2, a3 are the x, y, z values of your vector or point)
Calculate the normal for your triangle:
u = a - b
v = a - c
/u2*v3 - u3*v2\
|u3*v1 - u1*v3| = n
\u1*v2 - u2*v1/
Now you have to normalize your vector:
n° = n / sqrt(n1^2 + n2^2 + n3^2)
The distance between the triangle and the point is:
s = n1(p1 - a1) + n2(p2 - a2) + n3(p3 - a3)
ignore the sign of ''s''! (abs())
I hope that helps and is right!
Yesterday we still stood at the verge of the abyss,
today we''re a step onward!
I''m glad that I could help you!
Oh and, if someone finds a mistake in there...please tell me, cause I should be able to manage this stuff by friday!
Stupid tests!
Yesterday we still stood at the verge of the abyss,
today we''re a step onward!
Oh and, if someone finds a mistake in there...please tell me, cause I should be able to manage this stuff by friday!
Stupid tests!
Yesterday we still stood at the verge of the abyss,
today we''re a step onward!
Correction:
Those formulas is computation of distance between a point and a plane on what the triangel lies. Computation of the nearest point to the triangel is more complicated, and requires finding the nearest point to particular edge of the triangel in case when the point is out of perpendicular (to plane) boundaries of the triangel.
I am also trying to find out some algorithm for it in my collision detection. Since it is time critical part of every 3D engine, it should be pretty fast. Only I know is that first test in collision detection is the one described, because it''s not computationaly expensive. In case of test match you procceed with complicated algorithms to find the nearest point.
I don''t have any comprehensive link to this problem so far
Have a nice day.
Bedgo
Those formulas is computation of distance between a point and a plane on what the triangel lies. Computation of the nearest point to the triangel is more complicated, and requires finding the nearest point to particular edge of the triangel in case when the point is out of perpendicular (to plane) boundaries of the triangel.
I am also trying to find out some algorithm for it in my collision detection. Since it is time critical part of every 3D engine, it should be pretty fast. Only I know is that first test in collision detection is the one described, because it''s not computationaly expensive. In case of test match you procceed with complicated algorithms to find the nearest point.
I don''t have any comprehensive link to this problem so far
Have a nice day.
Bedgo
Oh right, haven''t thought of this!
Well, but that had at least nothin to do with my math-test (geometry went well, but the rest...)
Maybe you could project the vector from the plane to the point onto the plane and then, if it point''s outside of your tri, clip it back until it fits in. Then you just have to calculate the distance between these two points...
Yesterday we still stood at the verge of the abyss,
today we''re a step onward!
Well, but that had at least nothin to do with my math-test (geometry went well, but the rest...)
Maybe you could project the vector from the plane to the point onto the plane and then, if it point''s outside of your tri, clip it back until it fits in. Then you just have to calculate the distance between these two points...
Yesterday we still stood at the verge of the abyss,
today we''re a step onward!
What you need to do is to find the intersection point then you check if it's in the trianlge.
To find if the intersection point (P) is in the triangle ABC, you compute : APB+ BPC + APC.
It should be 360 degrees or 2PI radians if it's inside the triangle. But since you can't have the ultimate precision in your calculs, you do the check like that:
Edited by - Strange Monkey on January 13, 2002 2:56:38 PM
B *** * * * * P * * * * * * * * * * * * *A***************C To find if the intersection point (P) is in the triangle ABC, you compute : APB+ BPC + APC.
It should be 360 degrees or 2PI radians if it's inside the triangle. But since you can't have the ultimate precision in your calculs, you do the check like that:
if (angle >= (0.9999 * (2.0f * D3DX_PI))){ //The intersection point is in the triangle} Edited by - Strange Monkey on January 13, 2002 2:56:38 PM
Just seek info on the web about Voronoi diagrams of convex polygons or polyhedrons.
Well, I explain shortly :
Try to imagine convex cells connected to the d-facets of your triangle (face, the edges and vertices).
In each cell, for any point P, the nearest point Q on the triangle belongs to the facet.
Then you have 3 cases to project P and find Q.
d = DistPointLine( A, B, P, Q );
d = DistPointPlane( A, B, C, P, Q );
d = DistPointPoint( A, P ); // Q is A here
Well I hope you understood.
The same algo, with a Voronoi graph walk added, will give you the nearest point on a convex polyhedron in an almost constant time by using spatial coherency between frames. Requires to cache the last cell index in the Voronoi graph.
In the case of the triangle, you can optimize a lot. But it''s too tedious to explain here.
Charles B from Paris.
Rather good at geometric algorithms ! LOL
Seeking for interesting ppl to work with !
cbcht@wanadoo.fr
Well, I explain shortly :
Try to imagine convex cells connected to the d-facets of your triangle (face, the edges and vertices).
In each cell, for any point P, the nearest point Q on the triangle belongs to the facet.
Then you have 3 cases to project P and find Q.
d = DistPointLine( A, B, P, Q );
d = DistPointPlane( A, B, C, P, Q );
d = DistPointPoint( A, P ); // Q is A here
Well I hope you understood.
The same algo, with a Voronoi graph walk added, will give you the nearest point on a convex polyhedron in an almost constant time by using spatial coherency between frames. Requires to cache the last cell index in the Voronoi graph.
In the case of the triangle, you can optimize a lot. But it''s too tedious to explain here.
Charles B from Paris.
Rather good at geometric algorithms ! LOL
Seeking for interesting ppl to work with !
cbcht@wanadoo.fr
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
