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 <limits.h>
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.
GetCenterb2AABB168 b2Vec2 GetCenter() const
169 {
170 return 0.5f * (lowerBound + upperBound);
171 }
172
173 /// Get the extents of the AABB (half-widths).
GetExtentsb2AABB174 b2Vec2 GetExtents() const
175 {
176 return 0.5f * (upperBound - lowerBound);
177 }
178
179 /// Get the perimeter length
GetPerimeterb2AABB180 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.
Combineb2AABB188 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.
Combineb2AABB195 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.
Containsb2AABB202 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
IsValid()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
b2TestOverlap(const b2AABB & a,const b2AABB & b)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