|
|
|
We want to compute the distance between a line L(r) = P + r * D and a rectangle X(s, t) = B + s * E0 + t * E1 with s and t in [0, 1] and E0 * E1 = 0. The squared-distance function between a point on the line and a point on the rectangle is Q(s, t, r) = |X(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^3 shown in the algorithm for calculating the squared distance between a triangle and a line. Consider the following figure: t | | 4 | 3 | 2 | | ---|-----|----- | | 5 | 0 | 1 | | ---r----------- s | | 6 | 7 | 8 | | This is a 2-dimensional cut with the s-t plane of the regions in R^3. Imagine the rectangle 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 9 regions. For a ray we get 18 regions and for a segment 27 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 and t in [0, 1] we're in region 0 and the line and rectangle intersect, so the squared distance is 0. The other regions require the recursion in dimension as was explained for the line-to-triangle algorithm. 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 rectangle. In this case, a closest pair of points can be found by computing the minimum distance from the line to the four rectangle edges.
|
Copyright © by Martin Ecker |