1 /* 2 * Copyright (c) 2006-2009 Erin Catto http://www.box2d.org 3 * 4 * This software is provided 'as-is', without any express or implied 5 * warranty. In no event will the authors be held liable for any damages 6 * arising from the use of this software. 7 * Permission is granted to anyone to use this software for any purpose, 8 * including commercial applications, and to alter it and redistribute it 9 * freely, subject to the following restrictions: 10 * 1. The origin of this software must not be misrepresented; you must not 11 * claim that you wrote the original software. If you use this software 12 * in a product, an acknowledgment in the product documentation would be 13 * appreciated but is not required. 14 * 2. Altered source versions must be plainly marked as such, and must not be 15 * misrepresented as being the original software. 16 * 3. This notice may not be removed or altered from any source distribution. 17 */ 18 19 #ifndef B2_COLLISION_H 20 #define B2_COLLISION_H 21 22 #include <Box2D/Common/b2Math.h> 23 #include <climits> 24 25 /// @file 26 /// Structures and functions used for computing contact points, distance 27 /// queries, and TOI queries. 28 29 class b2Shape; 30 class b2CircleShape; 31 class b2EdgeShape; 32 class b2PolygonShape; 33 34 const uint8 b2_nullFeature = UCHAR_MAX; 35 36 /// The features that intersect to form the contact point 37 /// This must be 4 bytes or less. 38 struct b2ContactFeature 39 { 40 enum Type 41 { 42 e_vertex = 0, 43 e_face = 1 44 }; 45 46 uint8 indexA; ///< Feature index on shapeA 47 uint8 indexB; ///< Feature index on shapeB 48 uint8 typeA; ///< The feature type on shapeA 49 uint8 typeB; ///< The feature type on shapeB 50 }; 51 52 /// Contact ids to facilitate warm starting. 53 union b2ContactID 54 { 55 b2ContactFeature cf; 56 uint32 key; ///< Used to quickly compare contact ids. 57 }; 58 59 /// A manifold point is a contact point belonging to a contact 60 /// manifold. It holds details related to the geometry and dynamics 61 /// of the contact points. 62 /// The local point usage depends on the manifold type: 63 /// -e_circles: the local center of circleB 64 /// -e_faceA: the local center of cirlceB or the clip point of polygonB 65 /// -e_faceB: the clip point of polygonA 66 /// This structure is stored across time steps, so we keep it small. 67 /// Note: the impulses are used for internal caching and may not 68 /// provide reliable contact forces, especially for high speed collisions. 69 struct b2ManifoldPoint 70 { 71 b2Vec2 localPoint; ///< usage depends on manifold type 72 float32 normalImpulse; ///< the non-penetration impulse 73 float32 tangentImpulse; ///< the friction impulse 74 b2ContactID id; ///< uniquely identifies a contact point between two shapes 75 }; 76 77 /// A manifold for two touching convex shapes. 78 /// Box2D supports multiple types of contact: 79 /// - clip point versus plane with radius 80 /// - point versus point with radius (circles) 81 /// The local point usage depends on the manifold type: 82 /// -e_circles: the local center of circleA 83 /// -e_faceA: the center of faceA 84 /// -e_faceB: the center of faceB 85 /// Similarly the local normal usage: 86 /// -e_circles: not used 87 /// -e_faceA: the normal on polygonA 88 /// -e_faceB: the normal on polygonB 89 /// We store contacts in this way so that position correction can 90 /// account for movement, which is critical for continuous physics. 91 /// All contact scenarios must be expressed in one of these types. 92 /// This structure is stored across time steps, so we keep it small. 93 struct b2Manifold 94 { 95 enum Type 96 { 97 e_circles, 98 e_faceA, 99 e_faceB 100 }; 101 102 b2ManifoldPoint points[b2_maxManifoldPoints]; ///< the points of contact 103 b2Vec2 localNormal; ///< not use for Type::e_points 104 b2Vec2 localPoint; ///< usage depends on manifold type 105 Type type; 106 int32 pointCount; ///< the number of manifold points 107 }; 108 109 /// This is used to compute the current state of a contact manifold. 110 struct b2WorldManifold 111 { 112 /// Evaluate the manifold with supplied transforms. This assumes 113 /// modest motion from the original state. This does not change the 114 /// point count, impulses, etc. The radii must come from the shapes 115 /// that generated the manifold. 116 void Initialize(const b2Manifold* manifold, 117 const b2Transform& xfA, float32 radiusA, 118 const b2Transform& xfB, float32 radiusB); 119 120 b2Vec2 normal; ///< world vector pointing from A to B 121 b2Vec2 points[b2_maxManifoldPoints]; ///< world contact point (point of intersection) 122 float32 separations[b2_maxManifoldPoints]; ///< a negative value indicates overlap, in meters 123 }; 124 125 /// This is used for determining the state of contact points. 126 enum b2PointState 127 { 128 b2_nullState, ///< point does not exist 129 b2_addState, ///< point was added in the update 130 b2_persistState, ///< point persisted across the update 131 b2_removeState ///< point was removed in the update 132 }; 133 134 /// Compute the point states given two manifolds. The states pertain to the transition from manifold1 135 /// to manifold2. So state1 is either persist or remove while state2 is either add or persist. 136 void b2GetPointStates(b2PointState state1[b2_maxManifoldPoints], b2PointState state2[b2_maxManifoldPoints], 137 const b2Manifold* manifold1, const b2Manifold* manifold2); 138 139 /// Used for computing contact manifolds. 140 struct b2ClipVertex 141 { 142 b2Vec2 v; 143 b2ContactID id; 144 }; 145 146 /// Ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1). 147 struct b2RayCastInput 148 { 149 b2Vec2 p1, p2; 150 float32 maxFraction; 151 }; 152 153 /// Ray-cast output data. The ray hits at p1 + fraction * (p2 - p1), where p1 and p2 154 /// come from b2RayCastInput. 155 struct b2RayCastOutput 156 { 157 b2Vec2 normal; 158 float32 fraction; 159 }; 160 161 /// An axis aligned bounding box. 162 struct b2AABB 163 { 164 /// Verify that the bounds are sorted. 165 bool IsValid() const; 166 167 /// Get the center of the AABB. 168 b2Vec2 GetCenter() const 169 { 170 return 0.5f * (lowerBound + upperBound); 171 } 172 173 /// Get the extents of the AABB (half-widths). 174 b2Vec2 GetExtents() const 175 { 176 return 0.5f * (upperBound - lowerBound); 177 } 178 179 /// Get the perimeter length 180 float32 GetPerimeter() const 181 { 182 float32 wx = upperBound.x - lowerBound.x; 183 float32 wy = upperBound.y - lowerBound.y; 184 return 2.0f * (wx + wy); 185 } 186 187 /// Combine an AABB into this one. 188 void Combine(const b2AABB& aabb) 189 { 190 lowerBound = b2Min(lowerBound, aabb.lowerBound); 191 upperBound = b2Max(upperBound, aabb.upperBound); 192 } 193 194 /// Combine two AABBs into this one. 195 void Combine(const b2AABB& aabb1, const b2AABB& aabb2) 196 { 197 lowerBound = b2Min(aabb1.lowerBound, aabb2.lowerBound); 198 upperBound = b2Max(aabb1.upperBound, aabb2.upperBound); 199 } 200 201 /// Does this aabb contain the provided AABB. 202 bool Contains(const b2AABB& aabb) const 203 { 204 bool result = true; 205 result = result && lowerBound.x <= aabb.lowerBound.x; 206 result = result && lowerBound.y <= aabb.lowerBound.y; 207 result = result && aabb.upperBound.x <= upperBound.x; 208 result = result && aabb.upperBound.y <= upperBound.y; 209 return result; 210 } 211 212 bool RayCast(b2RayCastOutput* output, const b2RayCastInput& input) const; 213 214 b2Vec2 lowerBound; ///< the lower vertex 215 b2Vec2 upperBound; ///< the upper vertex 216 }; 217 218 /// Compute the collision manifold between two circles. 219 void b2CollideCircles(b2Manifold* manifold, 220 const b2CircleShape* circleA, const b2Transform& xfA, 221 const b2CircleShape* circleB, const b2Transform& xfB); 222 223 /// Compute the collision manifold between a polygon and a circle. 224 void b2CollidePolygonAndCircle(b2Manifold* manifold, 225 const b2PolygonShape* polygonA, const b2Transform& xfA, 226 const b2CircleShape* circleB, const b2Transform& xfB); 227 228 /// Compute the collision manifold between two polygons. 229 void b2CollidePolygons(b2Manifold* manifold, 230 const b2PolygonShape* polygonA, const b2Transform& xfA, 231 const b2PolygonShape* polygonB, const b2Transform& xfB); 232 233 /// Compute the collision manifold between an edge and a circle. 234 void b2CollideEdgeAndCircle(b2Manifold* manifold, 235 const b2EdgeShape* polygonA, const b2Transform& xfA, 236 const b2CircleShape* circleB, const b2Transform& xfB); 237 238 /// Compute the collision manifold between an edge and a circle. 239 void b2CollideEdgeAndPolygon(b2Manifold* manifold, 240 const b2EdgeShape* edgeA, const b2Transform& xfA, 241 const b2PolygonShape* circleB, const b2Transform& xfB); 242 243 /// Clipping for contact manifolds. 244 int32 b2ClipSegmentToLine(b2ClipVertex vOut[2], const b2ClipVertex vIn[2], 245 const b2Vec2& normal, float32 offset, int32 vertexIndexA); 246 247 /// Determine if two generic shapes overlap. 248 bool b2TestOverlap( const b2Shape* shapeA, int32 indexA, 249 const b2Shape* shapeB, int32 indexB, 250 const b2Transform& xfA, const b2Transform& xfB); 251 252 // ---------------- Inline Functions ------------------------------------------ 253 254 inline bool b2AABB::IsValid() const 255 { 256 b2Vec2 d = upperBound - lowerBound; 257 bool valid = d.x >= 0.0f && d.y >= 0.0f; 258 valid = valid && lowerBound.IsValid() && upperBound.IsValid(); 259 return valid; 260 } 261 262 inline bool b2TestOverlap(const b2AABB& a, const b2AABB& b) 263 { 264 b2Vec2 d1, d2; 265 d1 = b.lowerBound - a.upperBound; 266 d2 = a.lowerBound - b.upperBound; 267 268 if (d1.x > 0.0f || d1.y > 0.0f) 269 return false; 270 271 if (d2.x > 0.0f || d2.y > 0.0f) 272 return false; 273 274 return true; 275 } 276 277 #endif 278
