|
|
|
Given a point P and a triangle T(s, t) = B + s * E0 + t * E1 with s and t in [0, 1] and s + t <= 1 we want to find the closest distance of P to T. We want to find the parameter pair (s, t) that gives us the closest point on the triangle to P. To do so we have to minimze the squared-distance function Q(s, t) = |T - P|^2 This function is quadratic in s and t and is of the form Q(s, t) = as^2 + 2bst + ct^2 + 2ds + 2et + f with a = E0 * E0 b = E0 * E1 c = E1 * E1 d = E0 * (B - P) e = E1 * (B - P) f = (B - P) * (B - P) Quadratics are classified by the sign of the determinant ac - b^2 = (E0 * E0) * (E1 * E1) - (E0 * E1)^2 = |E0 x E1|^2 > 0 The determinant is always > 0 since E0 and E1 are linearly independent and thus the cross product of the two vectors always yields a nonzero vector. The minimum of Q(s, t) either occurs at an interior point or at a boundary of the domain of T(s, t). So we minimize Q(s, t) by determining the gradient dQ(s, t) and calculating s and t where dQ = (0, 0) dQ(s, t) = (2as + 2bt + 2d, 2bs + 2ct + 2e) = (0, 0) which is at s = (be - cd) / (ac - b^2) t = (bd - ae) / (ac - b^2) If (s, t) is an interior point we have found the minimum. Otherwise we must determine the correct boundary of the triangle where the minimum occurs. Consider the following figure: t \ 2| \ | \| |\ | \ 1 | \ 3 | 0 \ | \ --------------- s 4 | 5 \ 6 | \ | \ If (s, t) is in region 0 we have found the minimum. If (s, t) is in region 1 we intersect the graph with the plane s + t = 1 and get the parabola F(s) = Q(s, 1 - s) for s in [0, 1] as curve of intersection that we can minimize. Either the minimum occurs at F'(s) = 0 or at an end point where s = 0 or s = 1. Regions 3 and 5 are handled similarly. If (s, t) is in region 2 the minimum could be on the edge s + t = 1 or s = 0. Because the global minimum occurs in region 2 the gradient at the corner (0, 1) cannot point inside the triangle. If dQ = (Qs, Qt) with Qs and Qt being the respective partial derivatives of Q, it must be that (0, -1) * dQ(0, 1) and (1, -1) * dQ(0, 1) cannot both be negative and the signs of these values can be used to determine the correct edge. (0, -1) and (1, -1) are direction vectors for the edges s = 0 and s + t = 1. Similar arguments apply to regions 4 and 6.
|
Copyright © by Martin Ecker |