Report

2.5. BASIC PRIMITIVE INTERSECTION Details of common forms of primitive intersection test Basic Primitive Intersection Tests Basic primitive intersection testing concerns determining if two primitives intersect. Testing if two primitives intersect is often easier (and faster) than determining how two primitives intersect (e.g. generating contact information such as the distance of interpenetration, etc.). Types of basic primitive test Consult the recommended course text for details of the following tests: • • • • • • • • • • Separating-axis test Sphere against plane Box against plane Cone against plane Sphere against AABB Sphere against OBB Sphere against triangle Sphere against polygon AABB against polygon Triangle against triangle Two illustrative forms of closest point test are explored next. Overview of the separating axis theory Separating-axis test The separating-axis test provides a core tool for implementing a range of intersection tests. The test is based on the separating hyperplane theorem, which states that given two convex sets A and B, either the two sets are intersecting or there exists a separating hyperplane P such that A is on one side of P and B is on the other. The theory is intuitive as two convex objects cannot “curve” around each other. Thus, when they are not intersecting there will be a gap between them into which a plane can be inserted to separate the two objects. Separating-axis test A separating axis is a line which is perpendicular to some separating hyperplane. It is called a separating axis because the orthogonal projections of A and B onto the separating axis result in two non-overlapping intervals. In principle, a test for a separating axis or hyperplane is equally valid, however, in practice, it is less expensive to test for separation on an axis. Separating-axis test: Symmetrical primitives For symmetrical primitives with a defined centre point (e.g. AABBs, OBBs, spheres, etc.), the centre point will always project onto the middle of the projection interval along the tested axis. An efficient separation test of two symmetrical objects A and B is to compute the halfwidth, or radii, of their projection intervals and compare the sum of them against the distance between their centre projections. If the sum is less than the distance between the centre projections, the objects must be disjoint. Separating-axis test: Arbitrary primitives Given two arbitrary convex hulls (i.e. polyhedra) the following forms of intersection are possible: face-face, face-edge, and edge-edge. For face-face and face-edge cases, the face normals of both objects should be tested as potential separating axes. For edge-edge case, the cross product of the two edges should be tested as the potential separating axis (the points on the edges closest to each other form the feet of a perpendicular between the two edges). In summary, to determine intersection of two polyhedral objects, the following axes should be tested for separation: • Axes parallel to face normals of object A • Axes parallel to face normals of object B • Axes parallel to the vectors resulting from the cross products of all edges in A with all edges in B Aside: More fully: this list also includes face-vertex, edgevertex and vertex-vertex, however, the vertex combinations can be considered a special case of edge contact. Separating-axis test: Arbitrary primitives As soon as a separating axis is found, a test can exit immediately, i.e. it is not until all identified axes have been tested with no separating axis that the objects must be intersecting. Aside: The separating-axis test can also be used to derive contact information, e.g. instead of exiting early when an overlap is detected, all axes are tested for overlap. After all axes have been tested, the axis with the least (normalized) overlap can be used as the contact normal, and the overlap can be used to estimate the penetration depth. With some extra work, contact points can also be computed with the help of the separating axis. Sphere and box plane-intersection tests Sphere vs Plane Intersection It is possible to test a sphere against a plane in several ways, e.g. testing if the sphere intersects the plane, or if the sphere intersects the negative halfspace of the plane. bool TestSphereAndHalfspace( Sphere sphere, Plane plane) { float separation = Dot(sphere.Centre, plane.Normal) - plane.Distance; return separation <= sphere.Radius; } Box vs Plane Intersection Given that the box vertices represent the points furthest away from the centre of the box, they need only be compared for distance against the plane. By projecting each vertex along the plane’s normal and accumulating the result, the maximum projection radius is obtained. Comparing this to the distance of the OBB’s centre from the plane determines if it is in intersection. e1 (P-C)● uo u0 u1 ● Centre-plane distance C e0 Projected radius n ● e1 Box vs Plane Intersection (P-C)● uo u0 u1 ● C e0 Centre-plane Projected distance radius n ● bool IsOBBIntersectingPlane(OBB box, Plane plane) { Accumulate the projections of each box half-width along the plane float radius = normal to determine the total box radius along towards the plane. box.e[0] * abs( dot( plane.n, box.u[0] ) ) + box.e[1] * abs( dot( plane.n, box.u[1] ) ) + box.e[2] * abs( dot( plane.n, box.u[2] ) ); Determine distance of box’s centre from the plane float distance = dot( plane.n, box.c ) – plane.d; Intersection if distance is within ±radius return abs(distance) <= radius; } Intersection tests involving rays Intersecting lines rays and segments Consult the recommended course text for details of the following tests: • • • • • • • Intersecting segment against plane Intersecting ray or segment against sphere Intersecting ray or segment against box Intersecting line against triangle Intersecting line against quadrilateral Intersecting ray or segment against triangle Intersecting ray or segment against convex polyhedron An illustrative form of ray test is explored next. Ray or Segment vs. Sphere Given a ray defined as R(t) = P + td, t ≥ 0, where P is the ray origin and d the normalized direction vector (for a defined segment 0 ≤ t ≤ tmax). For a sphere defined as (X-C)●(X-C)=r2, the point(s) of intersecti0n can be found by substituting R(t) for X and solving for values of t, i.e. (P+td-C)●(P+td-C)=r2 Rearranging the above provides a quadratic expression in terms of t, i.e.: t2 + 2(m●d)t+(m●m)-r2 = 0, where m=P-C Solving for t will enable the points of intersection to be determined, i.e. t = -b±√(b2-c) where b=m●d and c=(m●m)-r2 Zero, one or two solutions will be found, negative solutions should be ignored! Ray or Segment vs. Sphere bool IntersectRaySphere( Point p, Vector d, Sphere s, d out float t, out Point q) P● { Vector m = p - s.c; Determine b and c for use float b = dot(m, d); within t = -b±√(b2-c) float c = dot(m, m) - s.r * s.r; t● Q Return false if the ray origin is outside of the sphere (i.e. c>0) and pointing away from the sphere (b>0) if (c > 0.0f && b > 0.0f) return false; } If the discriminant is float discr = b*b - c; negative, i.e. No real if (discr < 0.0f) return false; solutions, then the ray misses sphere t = -b - sqrt(discr); if (t < 0.0f) t = 0.0f; Determine the smallest (nonnegative) value of t which gives the q = p + t * d; nearest point of intersection. If return true; negative, then clamp to zero (ray started within sphere) r C● Directed reading on primitive intersection Directed reading • Read Chapter 5 of Real Time Collision Detection: o pp156-174 for primitive intersection tests o pp175-200 for line, ray and segment intersection o pp201-231 for dynamic and other forms of intersection test • Related papers can be found from: http://realtimecollisiondetection.net/books/rtcd/references/ Summary Today we explored: Basic primitive intersection tests Separating axis theory Sample plane and ray intersection tests