Report

2.4. PRIMITIVE TESTS -CLOSEST POINT Closest point forms of intersection detection Closest point forms of intersection detection Finding the closest point between two objects provides a number of benefits. If positive, the objects are separated, if negative, the objects are interpenetrating (and knowledge of the closest point can be used to provide contact information). Two different approaches can be used to find the minimum point: • Formulate the test as a minimisation problem and solve it using calculus. • Use the geometric properties of the objects to geometrically derive the closest point (considered here). Forms of closest point test Consult the recommended course text for details of the following tests: • • • • • • • • • • Closest Point on Plane to Point Closest Point on Line Segment to Point Closest Point on AABB to Point Closest Point on OBB to Point Closest Point on Triangle to Point Closest Point on Convex Polyhedron to Point Closest Points of Two Lines Closest Points of Two Line Segments Closest Points of a Line Segment and a Triangle Closest Points of Two Triangles Two illustrative forms of closest point test are explored next. Closest point between an OBB and a Point Closest point on an OBB to a Point Consider an OBB with centre point C, orthogonal unit vectors (u0, u1, u2) and half-width distances (e0, e1, e2) and a point P. Closest point on an OBB to a Point The closest point on/in the OBB to P can be determined by: 1. Transforming the point P into the local coordinate system of the OBB, 2. Computing the point on the OBB (now effectively an AABB) closest to the transformed point. 3. Transforming the resulting point back into world coordinates Closest point on an OBB to a Point 1. Transform P into the OBB P ● coordinate system: The transformed point Q is found from: P-C ● Qx = (P – C)● uo Qy = (P – C)● u1 Qz = (P – C)● u2 (P-C)● uo ● i.e. the distance vector of the point from the centre of the OBB as projected onto each defined OBB axis C u0 Closest point on an OBB to a Point 2. Computing OBB point closest to the transformed point. If the transformed point u0, u1, u2 distances are respectively longer than e0, e1, e2 then clamp to halfwidth extents Qi = (P–C)● ui if(Qi>ei) Qi=ei if(Qi<-ei) Qi=-ei 3. Transform the point back into world coordinates Qi = C + Qiui P ● ● u1 ● C Q e1 u0 e2 Closest point on an OBB to a Point Expressed as code: ClosestPointToOBB(Point point, OBB box, out Point closestPt) { Vector distance = point- box.centre; Initially set closest point as box centre closestPt = box.centre; for (int i = 0; i < 3; i++) { Iterate over box axis Determine projection float length = Dot(distance, box.axis[i]);along axis Clamp if needed if (length > box.extent[i]) length = box.extent[i]; if (length < -box.extent[i]) length = -box.extent[i]; closestPt += length * box.axis[i]; Build world location component by moving determine distance } along OBB axis } Closest point on an OBB to a Point The separation (actual or squared) can then be determined simply as: float distance = (closestPt – point).length() Closest point between a Triangle and a Point Closest point on a triangle to a point Given a triangle defined by points ABC and a point P, assume Q defines the point of ABC closest to P. A An efficient means of computing Q is: 1. Determine which triangle Voronoi region P is within (i.e. find which feature P is closest to). 2.Orthogonally project P onto the determined closest feature. C Voronoi region of edge CB B A Closest point on a triangle to a point Intersection with the Voronoi region for vertex A, B and C can be determined as the intersection of the negative half-space of the two planes through that point, e.g. for A each plane passes through A, one with a normal (BA) and the other with normal (CA). A A C B A Closest point on a triangle to a point The Voronoi region of each triangle edge can be efficiently computed by determining the triangle barycentric coordinates of P. Assuming n is the normal of triangle ABC and R is the projection of P onto the triangle’s plane, i.e. R = P – tn some for t, the barycentric coordinates of R (R = uA + vB + wC) are given by: n = rab rbc rca abc u = (B-A)×(C-A) = n ● ((A-P)×(B-P)) = n ● ((B-P)×(C-P)) = n ● ((C-P)×(A-P)) = rab + rbc + rca rbc/abc, v = rca/abc, w = rab/abc C Voronoi region of edge CB B Closest point on a triangle to a point To determine if P is within a triangle edge Voronoi region the following conditions must hold: A 1. Calculated area of the barycentric region must be <= 0 (i.e. for AB, rab <= 0) C 2.The point must be within the positive half- spaces of the planes (assuming an edge AB): (X-A)●(B-A) = 0 and (X-B)●(A-B) = 0 B B Closest point on a Triangle to a Point Points ABC defined the triangle, point P is the source point, point Q is the closest triangle point to P ClosestPointToTriangle( Point a, Point b, Point c, Point p, out Point q { Build edge vectors Vector ab = b – a, ac = c – a, bc = c - b; Determine the parametric position s for the projection of P onto AB (i.e. P’ = A+s*AB, where s = snom/ (snom+sdenom), and then parametric position t for P projected onto AC float snom = Dot(p - a, ab), sdenom = Dot(p - b, a - b); float tnom = Dot(p - a, ac), tdenom = Dot(p - c, a - c); if (snom <= 0.0f && tnom <= 0.0f) return a; Vertex Voronoi region hit early out Parametric position u for P projected onto BC float unom = Dot(p - b, bc), udenom = Dot(p - c, b - c); if (sdenom <= 0.0f && unom <= 0.0f) return b; if (tdenom <= 0.0f && udenom <= 0.0f) return c; Closest point on a Triangle to a Point Determine if P is outside (or on) edge AB by finding the area formed by vectors PA, PB and the triangle normal. A scalar triple product is used. Vector n = Cross(b - a, c - a); float vc = Dot(n, Cross(a - p, b - p)); If P is outside of AB (signed area <= 0) and within Voronoi feature region, then return projection of P onto AB if (vc <= 0.0f && snom >= 0.0f && sdenom >= 0.0f) return a + snom / (snom + sdenom) * ab; Repeat the same test for P onto BC float va = Dot(n, Cross(b if (va <= 0.0f && unom >= return b + unom / (unom + Repeat the same test for P onto CA float vb = Dot(n, Cross(c if (vb <= 0.0f && tnom >= return a + tnom / (tnom + - p, c - p)); 0.0f && udenom >= 0.0f) udenom) * bc; - p, a - p)); 0.0f && tdenom >= 0.0f) tdenom) * ac; P must project onto inside face. Find closest point using the barycentric coordinates float u = va / (va + vb + vc); float v = vb / (va + vb + vc); float w = 1.0f - u - v; // = vc / (va + vb + vc) return u * a + v * b + w * c; } Directed mathematical reading Directed reading • Read Chapter 5 (pp125-155) of Real Time Collision Detection • Related papers can be found from: http://realtimecollisiondetection.net/books/rtcd/references/ Summary Today we explored: Notion of closest point forms of intersection testing. Closest point to an OBB or triangle