1 // MIT License
2
3 // Copyright (c) 2019 Erin Catto
4
5 // Permission is hereby granted, free of charge, to any person obtaining a copy
6 // of this software and associated documentation files (the "Software"), to deal
7 // in the Software without restriction, including without limitation the rights
8 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 // copies of the Software, and to permit persons to whom the Software is
10 // furnished to do so, subject to the following conditions:
11
12 // The above copyright notice and this permission notice shall be included in all
13 // copies or substantial portions of the Software.
14
15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21 // SOFTWARE.
22
23 #ifndef B2_COLLISION_H
24 #define B2_COLLISION_H
25
26 #include <limits.h>
27
28 #include "b2_api.h"
29 #include "b2_math.h"
30
31 /// @file
32 /// Structures and functions used for computing contact points, distance
33 /// queries, and TOI queries.
34
35 class b2Shape;
36 class b2CircleShape;
37 class b2EdgeShape;
38 class b2PolygonShape;
39
40 const uint8 b2_nullFeature = UCHAR_MAX;
41
42 /// The features that intersect to form the contact point
43 /// This must be 4 bytes or less.
44 struct B2_API b2ContactFeature
45 {
46 enum Type
47 {
48 e_vertex = 0,
49 e_face = 1
50 };
51
52 uint8 indexA; ///< Feature index on shapeA
53 uint8 indexB; ///< Feature index on shapeB
54 uint8 typeA; ///< The feature type on shapeA
55 uint8 typeB; ///< The feature type on shapeB
56 };
57
58 /// Contact ids to facilitate warm starting.
59 union B2_API b2ContactID
60 {
61 b2ContactFeature cf;
62 uint32 key; ///< Used to quickly compare contact ids.
63 };
64
65 /// A manifold point is a contact point belonging to a contact
66 /// manifold. It holds details related to the geometry and dynamics
67 /// of the contact points.
68 /// The local point usage depends on the manifold type:
69 /// -e_circles: the local center of circleB
70 /// -e_faceA: the local center of cirlceB or the clip point of polygonB
71 /// -e_faceB: the clip point of polygonA
72 /// This structure is stored across time steps, so we keep it small.
73 /// Note: the impulses are used for internal caching and may not
74 /// provide reliable contact forces, especially for high speed collisions.
75 struct B2_API b2ManifoldPoint
76 {
77 b2Vec2 localPoint; ///< usage depends on manifold type
78 float normalImpulse; ///< the non-penetration impulse
79 float tangentImpulse; ///< the friction impulse
80 b2ContactID id; ///< uniquely identifies a contact point between two shapes
81 };
82
83 /// A manifold for two touching convex shapes.
84 /// Box2D supports multiple types of contact:
85 /// - clip point versus plane with radius
86 /// - point versus point with radius (circles)
87 /// The local point usage depends on the manifold type:
88 /// -e_circles: the local center of circleA
89 /// -e_faceA: the center of faceA
90 /// -e_faceB: the center of faceB
91 /// Similarly the local normal usage:
92 /// -e_circles: not used
93 /// -e_faceA: the normal on polygonA
94 /// -e_faceB: the normal on polygonB
95 /// We store contacts in this way so that position correction can
96 /// account for movement, which is critical for continuous physics.
97 /// All contact scenarios must be expressed in one of these types.
98 /// This structure is stored across time steps, so we keep it small.
99 struct B2_API b2Manifold
100 {
101 enum Type
102 {
103 e_circles,
104 e_faceA,
105 e_faceB
106 };
107
108 b2ManifoldPoint points[b2_maxManifoldPoints]; ///< the points of contact
109 b2Vec2 localNormal; ///< not use for Type::e_points
110 b2Vec2 localPoint; ///< usage depends on manifold type
111 Type type;
112 int32 pointCount; ///< the number of manifold points
113 };
114
115 /// This is used to compute the current state of a contact manifold.
116 struct B2_API b2WorldManifold
117 {
118 /// Evaluate the manifold with supplied transforms. This assumes
119 /// modest motion from the original state. This does not change the
120 /// point count, impulses, etc. The radii must come from the shapes
121 /// that generated the manifold.
122 void Initialize(const b2Manifold* manifold,
123 const b2Transform& xfA, float radiusA,
124 const b2Transform& xfB, float radiusB);
125
126 b2Vec2 normal; ///< world vector pointing from A to B
127 b2Vec2 points[b2_maxManifoldPoints]; ///< world contact point (point of intersection)
128 float separations[b2_maxManifoldPoints]; ///< a negative value indicates overlap, in meters
129 };
130
131 /// This is used for determining the state of contact points.
132 enum b2PointState
133 {
134 b2_nullState, ///< point does not exist
135 b2_addState, ///< point was added in the update
136 b2_persistState, ///< point persisted across the update
137 b2_removeState ///< point was removed in the update
138 };
139
140 /// Compute the point states given two manifolds. The states pertain to the transition from manifold1
141 /// to manifold2. So state1 is either persist or remove while state2 is either add or persist.
142 B2_API void b2GetPointStates(b2PointState state1[b2_maxManifoldPoints], b2PointState state2[b2_maxManifoldPoints],
143 const b2Manifold* manifold1, const b2Manifold* manifold2);
144
145 /// Used for computing contact manifolds.
146 struct B2_API b2ClipVertex
147 {
148 b2Vec2 v;
149 b2ContactID id;
150 };
151
152 /// Ray-cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1).
153 struct B2_API b2RayCastInput
154 {
155 b2Vec2 p1, p2;
156 float maxFraction;
157 };
158
159 /// Ray-cast output data. The ray hits at p1 + fraction * (p2 - p1), where p1 and p2
160 /// come from b2RayCastInput.
161 struct B2_API b2RayCastOutput
162 {
163 b2Vec2 normal;
164 float fraction;
165 };
166
167 /// An axis aligned bounding box.
168 struct B2_API b2AABB
169 {
170 /// Verify that the bounds are sorted.
171 bool IsValid() const;
172
173 /// Get the center of the AABB.
GetCenterb2AABB174 b2Vec2 GetCenter() const
175 {
176 return 0.5f * (lowerBound + upperBound);
177 }
178
179 /// Get the extents of the AABB (half-widths).
GetExtentsb2AABB180 b2Vec2 GetExtents() const
181 {
182 return 0.5f * (upperBound - lowerBound);
183 }
184
185 /// Get the perimeter length
GetPerimeterb2AABB186 float GetPerimeter() const
187 {
188 float wx = upperBound.x - lowerBound.x;
189 float wy = upperBound.y - lowerBound.y;
190 return 2.0f * (wx + wy);
191 }
192
193 /// Combine an AABB into this one.
Combineb2AABB194 void Combine(const b2AABB& aabb)
195 {
196 lowerBound = b2Min(lowerBound, aabb.lowerBound);
197 upperBound = b2Max(upperBound, aabb.upperBound);
198 }
199
200 /// Combine two AABBs into this one.
Combineb2AABB201 void Combine(const b2AABB& aabb1, const b2AABB& aabb2)
202 {
203 lowerBound = b2Min(aabb1.lowerBound, aabb2.lowerBound);
204 upperBound = b2Max(aabb1.upperBound, aabb2.upperBound);
205 }
206
207 /// Does this aabb contain the provided AABB.
Containsb2AABB208 bool Contains(const b2AABB& aabb) const
209 {
210 bool result = true;
211 result = result && lowerBound.x <= aabb.lowerBound.x;
212 result = result && lowerBound.y <= aabb.lowerBound.y;
213 result = result && aabb.upperBound.x <= upperBound.x;
214 result = result && aabb.upperBound.y <= upperBound.y;
215 return result;
216 }
217
218 bool RayCast(b2RayCastOutput* output, const b2RayCastInput& input) const;
219
220 b2Vec2 lowerBound; ///< the lower vertex
221 b2Vec2 upperBound; ///< the upper vertex
222 };
223
224 /// Compute the collision manifold between two circles.
225 B2_API void b2CollideCircles(b2Manifold* manifold,
226 const b2CircleShape* circleA, const b2Transform& xfA,
227 const b2CircleShape* circleB, const b2Transform& xfB);
228
229 /// Compute the collision manifold between a polygon and a circle.
230 B2_API void b2CollidePolygonAndCircle(b2Manifold* manifold,
231 const b2PolygonShape* polygonA, const b2Transform& xfA,
232 const b2CircleShape* circleB, const b2Transform& xfB);
233
234 /// Compute the collision manifold between two polygons.
235 B2_API void b2CollidePolygons(b2Manifold* manifold,
236 const b2PolygonShape* polygonA, const b2Transform& xfA,
237 const b2PolygonShape* polygonB, const b2Transform& xfB);
238
239 /// Compute the collision manifold between an edge and a circle.
240 B2_API void b2CollideEdgeAndCircle(b2Manifold* manifold,
241 const b2EdgeShape* polygonA, const b2Transform& xfA,
242 const b2CircleShape* circleB, const b2Transform& xfB);
243
244 /// Compute the collision manifold between an edge and a polygon.
245 B2_API void b2CollideEdgeAndPolygon(b2Manifold* manifold,
246 const b2EdgeShape* edgeA, const b2Transform& xfA,
247 const b2PolygonShape* circleB, const b2Transform& xfB);
248
249 /// Clipping for contact manifolds.
250 B2_API int32 b2ClipSegmentToLine(b2ClipVertex vOut[2], const b2ClipVertex vIn[2],
251 const b2Vec2& normal, float offset, int32 vertexIndexA);
252
253 /// Determine if two generic shapes overlap.
254 B2_API bool b2TestOverlap( const b2Shape* shapeA, int32 indexA,
255 const b2Shape* shapeB, int32 indexB,
256 const b2Transform& xfA, const b2Transform& xfB);
257
258 // ---------------- Inline Functions ------------------------------------------
259
IsValid()260 inline bool b2AABB::IsValid() const
261 {
262 b2Vec2 d = upperBound - lowerBound;
263 bool valid = d.x >= 0.0f && d.y >= 0.0f;
264 valid = valid && lowerBound.IsValid() && upperBound.IsValid();
265 return valid;
266 }
267
b2TestOverlap(const b2AABB & a,const b2AABB & b)268 inline bool b2TestOverlap(const b2AABB& a, const b2AABB& b)
269 {
270 b2Vec2 d1, d2;
271 d1 = b.lowerBound - a.upperBound;
272 d2 = a.lowerBound - b.upperBound;
273
274 if (d1.x > 0.0f || d1.y > 0.0f)
275 return false;
276
277 if (d2.x > 0.0f || d2.y > 0.0f)
278 return false;
279
280 return true;
281 }
282
283 #endif
284