|
|
|
We want to compute the distance between a line L(r) = P + r * D and a triangle T(s, t) = B + s * E0 + t * E1 with s and t in [0, 1] and s + t <= 1. The squared-distance function between a point on the line and a point on the triangle is Q(s, t, r) = |T(s, t) - L(R)|^2. Q(s, t, r) = a00s^2 + a11t^2 + a22r^2 + 2a01st + 2a02sr + 2a12tr + 2b0s + 2b1t + 2b2r + c where a00 = E0 * E0 a11 = E1 * E1 a22 = D * D a01 = E0 * E1 a02 = -E0 * D a12 = -E1 * D b0 = E0 * (B - P) b1 = E1 * (B - P) b2 = -D * (B - P) c = (B - P) * (B - P) The partition of R^3 is similar to the partitioning of R^2 shown in the algorithm for calculating the squared distance between a triangle and a point. Consider the following figure: t \ 2| \ | \| |\ | \ 3 | \ | 0 \ 1 | \ ---r----------- s | \ 4 | 5 \ 6 | \ This is a 2-dimensional cut with the s-t plane of the regions in R^3. Imagine the triangle extruded along the r axis which comes out of the cut. In the case of line-to-triangle calculations region 0 is an infinite prism and we get 7 regions. For a ray we get 14 regions and for a segment 21 regions. As with other distance algorithms, if the solution to dQ(s, t, r) = (0, 0, 0) lies in region 0, the minimum occurs at an interior point determined by the solution. Otherwise the minimum occurs on one of the boundary faces of the prism that is region 0. dQ(s, t, r) = (2a00s + 2a01t + 2a02r + 2b0, 2a11t + 2a01s + 2a12r + 2b1t, 2a22r + 2a02s + 2a12t + 2b2r) We can transform the system dQ(s, t, r) = (0, 0, 0) into matrix form A * p = -b where [ a00 a01 a02 ] [ s ] [ b0 ] A = [ a01 a11 a12 ], p = [ t ] and b = [ b1 ] [ a02 a12 a22 ] [ r ] [ b2 ] To solve for p we must determine p = A^-1 * -b Since A is a symmetric matrix we can easily determine A^-1 by building the cofactor matrix of A and multiplying it by 1 / determinant(A). Therefore we get as solution for p: [ (-b0 * cf00 - b1 * cf01 - b2 * cf02) / determinant(A) ] p = [ (-b0 * cf01 - b1 * cf11 - b2 * cf12) / determinant(A) ] [ (-b0 * cf02 - b1 * cf12 - b2 * cf22) / determinant(A) ] where cfij represents the cofactor at position (i, j) in the cofactor matrix of A. After having computed s, t and r we can decide in which region the solution lies in. If s + t <= 1, s > 0 and t > 0 we're in region 0 and the line and triangle intersect, so the squared distance is 0. The other regions require the recursion in dimension. For region 5, for example, the minimum is somewhere on the plane t = 0. The quadratic function to minimize is therefore Q5(s, r) with s in [0, 1] and r any real number. The sr-plane is partitioned into three parts: an infinite strip in the middle and two half planes. To calculate the minimum we have to solve dQ5(s, r) = (0, 0). The algorithm for this happens to be exactly the same as the distance calculation algorithm for the segment-to-line problem (since for a segment the parameter is in [0, 1] and for a line it is any real number, just like in our case). So we can just call the according segment-to-line routine. Also note that it is possible that the determinant of the equation system dQ = (0, 0, 0) is zero in which case the line is parallel to the triangle. In this case, a closest pair of points can be found by computing the minimum distance from the line to the three triangle edges.
|
Copyright © by Martin Ecker |