Minimum Distance between a Triangle and a Distance Field 3D

Question

I am looking for (possibly numerical) solution to this geometric problem:

Given a filled 3D triangle $T = \text{conv}(p_1, p_2, p_3) \subseteq R^3$, and a distance field $D(x) : R^3 \to R$, what is the point in the triangle $p^*$ which minimizes $D$, and what is the value of $d^* = D(p^*)$?

Assumptions:

• $p_1, p_2, p_3$ are coplanar 3d points, and their convex combination forms the triangle $T$.

• $D(x)$ is the minimum Euclidean distance of $x \in R^3$ to a (not necessarily convex) set $S \subseteq R^3$. No other properties of $D$ can be assumed.

• There may be multiple solutions for $p^*$ (for instance, D may be constant over $T$).

• $d^* = \text{min} ~D(x)~\forall~x \in T$ exists.

• It is easy to compute the gradient $\nabla D$.

I think it is possible to solve the problem numerically using Gradient Descent, representing the triangle as a set of linear constraints. Another possibility is to represent the triangle using Barycentric Coordinates and do gradient descent in that space rather than representing the triangle as a set of constraints.

Is there an easier way?

Answer 1

Unless I am misunderstanding, you are seeking the closest point in $T$ to $S$, where $S$ could be nonconvex (but is perhaps connected?). If that interpretation is correct, then a key search phrase is collision detection. In computer graphics, one often must compute the closest point between two polyhedral objects to anticipate collision, and there is a large literature on the topic. If you can approximate your set $S$ by polyhedra, then you can apply collision detection techniques.

For example:

Ponamgi, Manocha, Lin. "Incremental algorithms for collision detection between solid models." (ACM link)

A software package named SWIFT++ is maintained at the Univ. North Carolina: SWIFT++ link :

SWIFT++ is a collision detection package capable of detecting intersection, performing tolerance verification, computing approximate and exact distance, or determining the contacts between pairs of objects in a scene composed of general rigid polyhedral models.

To illustrate the sophistication of collision-detection state of the art, here is a snapshot from a video showing a computation of two colliding knots, each composed of 37,000 triangles:

---

    _{Video: Interactive Continuous Collision Detection for Non-Convex Polyhedra}

---

The paper describing this work is here:

Zhang, Xinyu, Minkyoung Lee, and Young J. Kim. "Interactive continuous collision detection for non-convex polyhedra." The Visual Computer 22.9-11 (2006): 749-760. (Springer link).