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

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

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?

1 Like

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 !

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

2 Likes

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 : http://clb.demon.fi/MathGeoLib/nightly/docs/Triangle.cpp_code.html#959

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)

1 Like

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:

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

Issues:

- QED
- 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…
- 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

1 Like

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

ok merci!

**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 = **T**he **P**oint

1 Like

@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.

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

1 Like

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.