Point.distance_to_face

[denis_bolomier]

Hi all,

Any simple way to compute point.distance_to_face ( not plane or line)
I’m looking to get the closest face of a point.
Thanks!

Denis

[eneroth3]

The simplest way would be to sort all vertices by distance to the point and get the first face of the first vertex that has any faces. However this does not gurantee to get the face that is actually closest, just one with the closest corner.

You could also project the point to all face’s planes. Then you test all these points to see if they are on the face. If they are not you can project them to each bounding edge’s line, check if they are on the edge and otherwise fall back to the closest end point. Now you have a bunch of points, all related to faces, that you can sort by distance to the original point to get the closest face. This is however quite a bit slower than the previous algorithm.

What is your use case?

[denis_bolomier]

Thanks Eneroth!

I was expected a simpliest solution. I found this one blender forum.

I will code it ( because if you don’t have any solution who will have it ? )

I work on 3d scan import and I need to extrude some edge until the closest face on the top.

Best regard !

[eneroth3]

If you have a defined direction you can use Model#raytest.

[jiminybillybob]

This is C++, but it may help get the logic:

959 vec Triangle::ClosestPoint(const vec &p) const
960 {
961         /** The code for Triangle-float3 test is from Christer Ericson's Real-Time Collision Detection, pp. 141-142. */
962 
963         // Check if P is in vertex region outside A.
964         vec ab = b - a;
965         vec ac = c - a;
966         vec ap = p - a;
967         float d1 = Dot(ab, ap);
968         float d2 = Dot(ac, ap);
969         if (d1 <= 0.f && d2 <= 0.f)
970                 return a; // Barycentric coordinates are (1,0,0).
971 
972         // Check if P is in vertex region outside B.
973         vec bp = p - b;
974         float d3 = Dot(ab, bp);
975         float d4 = Dot(ac, bp);
976         if (d3 >= 0.f && d4 <= d3)
977                 return b; // Barycentric coordinates are (0,1,0).
978 
979         // Check if P is in edge region of AB, and if so, return the projection of P onto AB.
980         float vc = d1*d4 - d3*d2;
981         if (vc <= 0.f && d1 >= 0.f && d3 <= 0.f)
982         {
983                 float v = d1 / (d1 - d3);
984                 return a + v * ab; // The barycentric coordinates are (1-v, v, 0).
985         }
986 
987         // Check if P is in vertex region outside C.
988         vec cp = p - c;
989         float d5 = Dot(ab, cp);
990         float d6 = Dot(ac, cp);
991         if (d6 >= 0.f && d5 <= d6)
992                 return c; // The barycentric coordinates are (0,0,1).
993 
994         // Check if P is in edge region of AC, and if so, return the projection of P onto AC.
995         float vb = d5*d2 - d1*d6;
996         if (vb <= 0.f && d2 >= 0.f && d6 <= 0.f)
997         {
998                 float w = d2 / (d2 - d6);
999                 return a + w * ac; // The barycentric coordinates are (1-w, 0, w).
1000         }
1001 
1002         // Check if P is in edge region of BC, and if so, return the projection of P onto BC.
1003         float va = d3*d6 - d5*d4;
1004         if (va <= 0.f && d4 - d3 >= 0.f && d5 - d6 >= 0.f)
1005         {
1006                 float w = (d4 - d3) / (d4 - d3 + d5 - d6);
1007                 return b + w * (c - b); // The barycentric coordinates are (0, 1-w, w).
1008         }
1009 
1010         // P must be inside the face region. Compute the closest point through its barycentric coordinates (u,v,w).
1011         float denom = 1.f / (va + vb + vc);
1012         float v = vb * denom;
1013         float w = vc * denom;
1014         return a + ab * v + ac * w;
1015 }

This is from MathGeoLib : DEMON.FI |

This method works for a single triangle, so first you’ll need to break up your face into several triangles using Face.mesh

It will give you the point on the triangle that is closest to the point you pass as argument, then you can simply compute the distance and compare with every other face/triangle. (Or use distance squared, as it’s faster to compute)

[MSP_Greg]

@denis_bolomier

I’m looking to get the closest face of a point.

This is a bit messy. You mentioned finding an algorithm elsewhere, but they’re often dependent on what calculations can be easily performed.

This problem is really about determining what the closest point on the model is to your point (TP). It can be one of three:

1. A vertex (assumed to be part of at least one face)
2. A point on an edge, as above
3. A normal from a face to TP

Issues:

1. QED
2. An edge may have the closest point to TP, without either of its vertices being the closest vertex. One could use Array#project_to_line(v1, v2) where v1 & v2 are an edge’s vertices, then see if that point of contained by the edge, then calc the distance…
3. QED, but more involved than #1

The issue is also complicated by the fact that a point/vertex can be classified by Face#classify_point, but I don’t believe there is an equivalent for Edge#classify_point.

Finally, what if several faces are all the same distance from TP? Should the algorithm return all of them?

Greg

[denis_bolomier]

@MSP_Greg

Finally, what if several faces are all the same distance from TP? Should the algorithm return all of them?

sorry Greg, I didn’t understand you perfectly. what do you means by TP and QED ?

[denis_bolomier]

ok merci!

[DanRathbun]

Q.E.D. is a Latin acronym that translates to English … “as was demonstrated” (or similar)
… ie, he was referring to the previous examples / ideas, etc.

I’m guessing that TP = The Point

[MSP_Greg]

@denis_bolomier Sorry. I guess QED is more commonly used in math, as opposed to coding…
QED = ‘quite easily done’

@DanRathbun Thanks for clarifying. Your guess is correct.

[Anssi]

@MSP_Greg

QED =

“Quod erat demonstrandum”, roughly “As was to be demonstrated”