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
29class b2Shape;
30class b2CircleShape;
31class b2EdgeShape;
32class b2PolygonShape;
33
34const uint8 b2_nullFeature = UCHAR_MAX;
35
36/// The features that intersect to form the contact point
37/// This must be 4 bytes or less.
38struct 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.
53union 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.
69struct 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.
93struct 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.
110struct 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.
126enum 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.
136void b2GetPointStates(b2PointState state1[b2_maxManifoldPoints], b2PointState state2[b2_maxManifoldPoints],
137 const b2Manifold* manifold1, const b2Manifold* manifold2);
138
139/// Used for computing contact manifolds.
140struct 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).
147struct 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.
155struct b2RayCastOutput
156{
157 b2Vec2 normal;
158 float32 fraction;
159};
160
161/// An axis aligned bounding box.
162struct 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.
219void 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.
224void 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.
229void 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.
234void 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.
239void b2CollideEdgeAndPolygon(b2Manifold* manifold,
240 const b2EdgeShape* edgeA, const b2Transform& xfA,
241 const b2PolygonShape* circleB, const b2Transform& xfB);
242
243/// Clipping for contact manifolds.
244int32 b2ClipSegmentToLine(b2ClipVertex vOut[2], const b2ClipVertex vIn[2],
245 const b2Vec2& normal, float32 offset, int32 vertexIndexA);
246
247/// Determine if two generic shapes overlap.
248bool b2TestOverlap( const b2Shape* shapeA, int32 indexA,
249 const b2Shape* shapeB, int32 indexB,
250 const b2Transform& xfA, const b2Transform& xfB);
251
252// ---------------- Inline Functions ------------------------------------------
253
254inline 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
262inline 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