collision.h (28696B)
1 // SPDX-FileCopyrightText: 2023 Erin Catto 2 // SPDX-License-Identifier: MIT 3 4 #pragma once 5 6 #include "base.h" 7 #include "math_functions.h" 8 9 #include <stdbool.h> 10 11 typedef struct b2SimplexCache b2SimplexCache; 12 typedef struct b2Hull b2Hull; 13 14 /** 15 * @defgroup geometry Geometry 16 * @brief Geometry types and algorithms 17 * 18 * Definitions of circles, capsules, segments, and polygons. Various algorithms to compute hulls, mass properties, and so on. 19 * @{ 20 */ 21 22 /// The maximum number of vertices on a convex polygon. Changing this affects performance even if you 23 /// don't use more vertices. 24 #define B2_MAX_POLYGON_VERTICES 8 25 26 /// Low level ray cast input data 27 typedef struct b2RayCastInput 28 { 29 /// Start point of the ray cast 30 b2Vec2 origin; 31 32 /// Translation of the ray cast 33 b2Vec2 translation; 34 35 /// The maximum fraction of the translation to consider, typically 1 36 float maxFraction; 37 } b2RayCastInput; 38 39 /// Low level shape cast input in generic form. This allows casting an arbitrary point 40 /// cloud wrap with a radius. For example, a circle is a single point with a non-zero radius. 41 /// A capsule is two points with a non-zero radius. A box is four points with a zero radius. 42 typedef struct b2ShapeCastInput 43 { 44 /// A point cloud to cast 45 b2Vec2 points[B2_MAX_POLYGON_VERTICES]; 46 47 /// The number of points 48 int count; 49 50 /// The radius around the point cloud 51 float radius; 52 53 /// The translation of the shape cast 54 b2Vec2 translation; 55 56 /// The maximum fraction of the translation to consider, typically 1 57 float maxFraction; 58 } b2ShapeCastInput; 59 60 /// Low level ray cast or shape-cast output data 61 typedef struct b2CastOutput 62 { 63 /// The surface normal at the hit point 64 b2Vec2 normal; 65 66 /// The surface hit point 67 b2Vec2 point; 68 69 /// The fraction of the input translation at collision 70 float fraction; 71 72 /// The number of iterations used 73 int iterations; 74 75 /// Did the cast hit? 76 bool hit; 77 } b2CastOutput; 78 79 /// This holds the mass data computed for a shape. 80 typedef struct b2MassData 81 { 82 /// The mass of the shape, usually in kilograms. 83 float mass; 84 85 /// The position of the shape's centroid relative to the shape's origin. 86 b2Vec2 center; 87 88 /// The rotational inertia of the shape about the local origin. 89 float rotationalInertia; 90 } b2MassData; 91 92 /// A solid circle 93 typedef struct b2Circle 94 { 95 /// The local center 96 b2Vec2 center; 97 98 /// The radius 99 float radius; 100 } b2Circle; 101 102 /// A solid capsule can be viewed as two semicircles connected 103 /// by a rectangle. 104 typedef struct b2Capsule 105 { 106 /// Local center of the first semicircle 107 b2Vec2 center1; 108 109 /// Local center of the second semicircle 110 b2Vec2 center2; 111 112 /// The radius of the semicircles 113 float radius; 114 } b2Capsule; 115 116 /// A solid convex polygon. It is assumed that the interior of the polygon is to 117 /// the left of each edge. 118 /// Polygons have a maximum number of vertices equal to B2_MAX_POLYGON_VERTICES. 119 /// In most cases you should not need many vertices for a convex polygon. 120 /// @warning DO NOT fill this out manually, instead use a helper function like 121 /// b2MakePolygon or b2MakeBox. 122 typedef struct b2Polygon 123 { 124 /// The polygon vertices 125 b2Vec2 vertices[B2_MAX_POLYGON_VERTICES]; 126 127 /// The outward normal vectors of the polygon sides 128 b2Vec2 normals[B2_MAX_POLYGON_VERTICES]; 129 130 /// The centroid of the polygon 131 b2Vec2 centroid; 132 133 /// The external radius for rounded polygons 134 float radius; 135 136 /// The number of polygon vertices 137 int count; 138 } b2Polygon; 139 140 /// A line segment with two-sided collision. 141 typedef struct b2Segment 142 { 143 /// The first point 144 b2Vec2 point1; 145 146 /// The second point 147 b2Vec2 point2; 148 } b2Segment; 149 150 /// A line segment with one-sided collision. Only collides on the right side. 151 /// Several of these are generated for a chain shape. 152 /// ghost1 -> point1 -> point2 -> ghost2 153 typedef struct b2ChainSegment 154 { 155 /// The tail ghost vertex 156 b2Vec2 ghost1; 157 158 /// The line segment 159 b2Segment segment; 160 161 /// The head ghost vertex 162 b2Vec2 ghost2; 163 164 /// The owning chain shape index (internal usage only) 165 int chainId; 166 } b2ChainSegment; 167 168 /// Validate ray cast input data (NaN, etc) 169 B2_API bool b2IsValidRay( const b2RayCastInput* input ); 170 171 /// Make a convex polygon from a convex hull. This will assert if the hull is not valid. 172 /// @warning Do not manually fill in the hull data, it must come directly from b2ComputeHull 173 B2_API b2Polygon b2MakePolygon( const b2Hull* hull, float radius ); 174 175 /// Make an offset convex polygon from a convex hull. This will assert if the hull is not valid. 176 /// @warning Do not manually fill in the hull data, it must come directly from b2ComputeHull 177 B2_API b2Polygon b2MakeOffsetPolygon( const b2Hull* hull, b2Vec2 position, b2Rot rotation ); 178 179 /// Make an offset convex polygon from a convex hull. This will assert if the hull is not valid. 180 /// @warning Do not manually fill in the hull data, it must come directly from b2ComputeHull 181 B2_API b2Polygon b2MakeOffsetRoundedPolygon( const b2Hull* hull, b2Vec2 position, b2Rot rotation, float radius ); 182 183 /// Make a square polygon, bypassing the need for a convex hull. 184 /// @param halfWidth the half-width 185 B2_API b2Polygon b2MakeSquare( float halfWidth ); 186 187 /// Make a box (rectangle) polygon, bypassing the need for a convex hull. 188 /// @param halfWidth the half-width (x-axis) 189 /// @param halfHeight the half-height (y-axis) 190 B2_API b2Polygon b2MakeBox( float halfWidth, float halfHeight ); 191 192 /// Make a rounded box, bypassing the need for a convex hull. 193 /// @param halfWidth the half-width (x-axis) 194 /// @param halfHeight the half-height (y-axis) 195 /// @param radius the radius of the rounded extension 196 B2_API b2Polygon b2MakeRoundedBox( float halfWidth, float halfHeight, float radius ); 197 198 /// Make an offset box, bypassing the need for a convex hull. 199 /// @param halfWidth the half-width (x-axis) 200 /// @param halfHeight the half-height (y-axis) 201 /// @param center the local center of the box 202 /// @param rotation the local rotation of the box 203 B2_API b2Polygon b2MakeOffsetBox( float halfWidth, float halfHeight, b2Vec2 center, b2Rot rotation ); 204 205 /// Make an offset rounded box, bypassing the need for a convex hull. 206 /// @param halfWidth the half-width (x-axis) 207 /// @param halfHeight the half-height (y-axis) 208 /// @param center the local center of the box 209 /// @param rotation the local rotation of the box 210 /// @param radius the radius of the rounded extension 211 B2_API b2Polygon b2MakeOffsetRoundedBox( float halfWidth, float halfHeight, b2Vec2 center, b2Rot rotation, float radius ); 212 213 /// Transform a polygon. This is useful for transferring a shape from one body to another. 214 B2_API b2Polygon b2TransformPolygon( b2Transform transform, const b2Polygon* polygon ); 215 216 /// Compute mass properties of a circle 217 B2_API b2MassData b2ComputeCircleMass( const b2Circle* shape, float density ); 218 219 /// Compute mass properties of a capsule 220 B2_API b2MassData b2ComputeCapsuleMass( const b2Capsule* shape, float density ); 221 222 /// Compute mass properties of a polygon 223 B2_API b2MassData b2ComputePolygonMass( const b2Polygon* shape, float density ); 224 225 /// Compute the bounding box of a transformed circle 226 B2_API b2AABB b2ComputeCircleAABB( const b2Circle* shape, b2Transform transform ); 227 228 /// Compute the bounding box of a transformed capsule 229 B2_API b2AABB b2ComputeCapsuleAABB( const b2Capsule* shape, b2Transform transform ); 230 231 /// Compute the bounding box of a transformed polygon 232 B2_API b2AABB b2ComputePolygonAABB( const b2Polygon* shape, b2Transform transform ); 233 234 /// Compute the bounding box of a transformed line segment 235 B2_API b2AABB b2ComputeSegmentAABB( const b2Segment* shape, b2Transform transform ); 236 237 /// Test a point for overlap with a circle in local space 238 B2_API bool b2PointInCircle( b2Vec2 point, const b2Circle* shape ); 239 240 /// Test a point for overlap with a capsule in local space 241 B2_API bool b2PointInCapsule( b2Vec2 point, const b2Capsule* shape ); 242 243 /// Test a point for overlap with a convex polygon in local space 244 B2_API bool b2PointInPolygon( b2Vec2 point, const b2Polygon* shape ); 245 246 /// Ray cast versus circle shape in local space. Initial overlap is treated as a miss. 247 B2_API b2CastOutput b2RayCastCircle( const b2RayCastInput* input, const b2Circle* shape ); 248 249 /// Ray cast versus capsule shape in local space. Initial overlap is treated as a miss. 250 B2_API b2CastOutput b2RayCastCapsule( const b2RayCastInput* input, const b2Capsule* shape ); 251 252 /// Ray cast versus segment shape in local space. Optionally treat the segment as one-sided with hits from 253 /// the left side being treated as a miss. 254 B2_API b2CastOutput b2RayCastSegment( const b2RayCastInput* input, const b2Segment* shape, bool oneSided ); 255 256 /// Ray cast versus polygon shape in local space. Initial overlap is treated as a miss. 257 B2_API b2CastOutput b2RayCastPolygon( const b2RayCastInput* input, const b2Polygon* shape ); 258 259 /// Shape cast versus a circle. Initial overlap is treated as a miss. 260 B2_API b2CastOutput b2ShapeCastCircle( const b2ShapeCastInput* input, const b2Circle* shape ); 261 262 /// Shape cast versus a capsule. Initial overlap is treated as a miss. 263 B2_API b2CastOutput b2ShapeCastCapsule( const b2ShapeCastInput* input, const b2Capsule* shape ); 264 265 /// Shape cast versus a line segment. Initial overlap is treated as a miss. 266 B2_API b2CastOutput b2ShapeCastSegment( const b2ShapeCastInput* input, const b2Segment* shape ); 267 268 /// Shape cast versus a convex polygon. Initial overlap is treated as a miss. 269 B2_API b2CastOutput b2ShapeCastPolygon( const b2ShapeCastInput* input, const b2Polygon* shape ); 270 271 /// A convex hull. Used to create convex polygons. 272 /// @warning Do not modify these values directly, instead use b2ComputeHull() 273 typedef struct b2Hull 274 { 275 /// The final points of the hull 276 b2Vec2 points[B2_MAX_POLYGON_VERTICES]; 277 278 /// The number of points 279 int count; 280 } b2Hull; 281 282 /// Compute the convex hull of a set of points. Returns an empty hull if it fails. 283 /// Some failure cases: 284 /// - all points very close together 285 /// - all points on a line 286 /// - less than 3 points 287 /// - more than B2_MAX_POLYGON_VERTICES points 288 /// This welds close points and removes collinear points. 289 /// @warning Do not modify a hull once it has been computed 290 B2_API b2Hull b2ComputeHull( const b2Vec2* points, int count ); 291 292 /// This determines if a hull is valid. Checks for: 293 /// - convexity 294 /// - collinear points 295 /// This is expensive and should not be called at runtime. 296 B2_API bool b2ValidateHull( const b2Hull* hull ); 297 298 /**@}*/ 299 300 /** 301 * @defgroup distance Distance 302 * Functions for computing the distance between shapes. 303 * 304 * These are advanced functions you can use to perform distance calculations. There 305 * are functions for computing the closest points between shapes, doing linear shape casts, 306 * and doing rotational shape casts. The latter is called time of impact (TOI). 307 * @{ 308 */ 309 310 /// Result of computing the distance between two line segments 311 typedef struct b2SegmentDistanceResult 312 { 313 /// The closest point on the first segment 314 b2Vec2 closest1; 315 316 /// The closest point on the second segment 317 b2Vec2 closest2; 318 319 /// The barycentric coordinate on the first segment 320 float fraction1; 321 322 /// The barycentric coordinate on the second segment 323 float fraction2; 324 325 /// The squared distance between the closest points 326 float distanceSquared; 327 } b2SegmentDistanceResult; 328 329 /// Compute the distance between two line segments, clamping at the end points if needed. 330 B2_API b2SegmentDistanceResult b2SegmentDistance( b2Vec2 p1, b2Vec2 q1, b2Vec2 p2, b2Vec2 q2 ); 331 332 /// A distance proxy is used by the GJK algorithm. It encapsulates any shape. 333 typedef struct b2ShapeProxy 334 { 335 /// The point cloud 336 b2Vec2 points[B2_MAX_POLYGON_VERTICES]; 337 338 /// The number of points 339 int count; 340 341 /// The external radius of the point cloud 342 float radius; 343 } b2ShapeProxy; 344 345 /// Used to warm start the GJK simplex. If you call this function multiple times with nearby 346 /// transforms this might improve performance. Otherwise you can zero initialize this. 347 /// The distance cache must be initialized to zero on the first call. 348 /// Users should generally just zero initialize this structure for each call. 349 typedef struct b2SimplexCache 350 { 351 /// The number of stored simplex points 352 uint16_t count; 353 354 /// The cached simplex indices on shape A 355 uint8_t indexA[3]; 356 357 /// The cached simplex indices on shape B 358 uint8_t indexB[3]; 359 } b2SimplexCache; 360 361 static const b2SimplexCache b2_emptySimplexCache = B2_ZERO_INIT; 362 363 /// Input for b2ShapeDistance 364 typedef struct b2DistanceInput 365 { 366 /// The proxy for shape A 367 b2ShapeProxy proxyA; 368 369 /// The proxy for shape B 370 b2ShapeProxy proxyB; 371 372 /// The world transform for shape A 373 b2Transform transformA; 374 375 /// The world transform for shape B 376 b2Transform transformB; 377 378 /// Should the proxy radius be considered? 379 bool useRadii; 380 } b2DistanceInput; 381 382 /// Output for b2ShapeDistance 383 typedef struct b2DistanceOutput 384 { 385 b2Vec2 pointA; ///< Closest point on shapeA 386 b2Vec2 pointB; ///< Closest point on shapeB 387 // todo_erin implement this 388 // b2Vec2 normal; ///< Normal vector that points from A to B 389 float distance; ///< The final distance, zero if overlapped 390 int iterations; ///< Number of GJK iterations used 391 int simplexCount; ///< The number of simplexes stored in the simplex array 392 } b2DistanceOutput; 393 394 /// Simplex vertex for debugging the GJK algorithm 395 typedef struct b2SimplexVertex 396 { 397 b2Vec2 wA; ///< support point in proxyA 398 b2Vec2 wB; ///< support point in proxyB 399 b2Vec2 w; ///< wB - wA 400 float a; ///< barycentric coordinate for closest point 401 int indexA; ///< wA index 402 int indexB; ///< wB index 403 } b2SimplexVertex; 404 405 /// Simplex from the GJK algorithm 406 typedef struct b2Simplex 407 { 408 b2SimplexVertex v1, v2, v3; ///< vertices 409 int count; ///< number of valid vertices 410 } b2Simplex; 411 412 /// Compute the closest points between two shapes represented as point clouds. 413 /// b2SimplexCache cache is input/output. On the first call set b2SimplexCache.count to zero. 414 /// The underlying GJK algorithm may be debugged by passing in debug simplexes and capacity. You may pass in NULL and 0 for these. 415 B2_API b2DistanceOutput b2ShapeDistance( b2SimplexCache* cache, const b2DistanceInput* input, b2Simplex* simplexes, 416 int simplexCapacity ); 417 418 /// Input parameters for b2ShapeCast 419 typedef struct b2ShapeCastPairInput 420 { 421 b2ShapeProxy proxyA; ///< The proxy for shape A 422 b2ShapeProxy proxyB; ///< The proxy for shape B 423 b2Transform transformA; ///< The world transform for shape A 424 b2Transform transformB; ///< The world transform for shape B 425 b2Vec2 translationB; ///< The translation of shape B 426 float maxFraction; ///< The fraction of the translation to consider, typically 1 427 } b2ShapeCastPairInput; 428 429 /// Perform a linear shape cast of shape B moving and shape A fixed. Determines the hit point, normal, and translation fraction. 430 B2_API b2CastOutput b2ShapeCast( const b2ShapeCastPairInput* input ); 431 432 /// Make a proxy for use in GJK and related functions. 433 B2_API b2ShapeProxy b2MakeProxy( const b2Vec2* vertices, int count, float radius ); 434 435 /// This describes the motion of a body/shape for TOI computation. Shapes are defined with respect to the body origin, 436 /// which may not coincide with the center of mass. However, to support dynamics we must interpolate the center of mass 437 /// position. 438 typedef struct b2Sweep 439 { 440 b2Vec2 localCenter; ///< Local center of mass position 441 b2Vec2 c1; ///< Starting center of mass world position 442 b2Vec2 c2; ///< Ending center of mass world position 443 b2Rot q1; ///< Starting world rotation 444 b2Rot q2; ///< Ending world rotation 445 } b2Sweep; 446 447 /// Evaluate the transform sweep at a specific time. 448 B2_API b2Transform b2GetSweepTransform( const b2Sweep* sweep, float time ); 449 450 /// Input parameters for b2TimeOfImpact 451 typedef struct b2TOIInput 452 { 453 b2ShapeProxy proxyA; ///< The proxy for shape A 454 b2ShapeProxy proxyB; ///< The proxy for shape B 455 b2Sweep sweepA; ///< The movement of shape A 456 b2Sweep sweepB; ///< The movement of shape B 457 float maxFraction; ///< Defines the sweep interval [0, maxFraction] 458 } b2TOIInput; 459 460 /// Describes the TOI output 461 typedef enum b2TOIState 462 { 463 b2_toiStateUnknown, 464 b2_toiStateFailed, 465 b2_toiStateOverlapped, 466 b2_toiStateHit, 467 b2_toiStateSeparated 468 } b2TOIState; 469 470 /// Output parameters for b2TimeOfImpact. 471 typedef struct b2TOIOutput 472 { 473 b2TOIState state; ///< The type of result 474 float fraction; ///< The sweep time of the collision 475 } b2TOIOutput; 476 477 /// Compute the upper bound on time before two shapes penetrate. Time is represented as 478 /// a fraction between [0,tMax]. This uses a swept separating axis and may miss some intermediate, 479 /// non-tunneling collisions. If you change the time interval, you should call this function 480 /// again. 481 B2_API b2TOIOutput b2TimeOfImpact( const b2TOIInput* input ); 482 483 /**@}*/ 484 485 /** 486 * @defgroup collision Collision 487 * @brief Functions for colliding pairs of shapes 488 * @{ 489 */ 490 491 /// A manifold point is a contact point belonging to a contact manifold. 492 /// It holds details related to the geometry and dynamics of the contact points. 493 /// Box2D uses speculative collision so some contact points may be separated. 494 /// You may use the maxNormalImpulse to determine if there was an interaction during 495 /// the time step. 496 typedef struct b2ManifoldPoint 497 { 498 /// Location of the contact point in world space. Subject to precision loss at large coordinates. 499 /// @note Should only be used for debugging. 500 b2Vec2 point; 501 502 /// Location of the contact point relative to shapeA's origin in world space 503 /// @note When used internally to the Box2D solver, this is relative to the body center of mass. 504 b2Vec2 anchorA; 505 506 /// Location of the contact point relative to shapeB's origin in world space 507 /// @note When used internally to the Box2D solver, this is relative to the body center of mass. 508 b2Vec2 anchorB; 509 510 /// The separation of the contact point, negative if penetrating 511 float separation; 512 513 /// The impulse along the manifold normal vector. 514 float normalImpulse; 515 516 /// The friction impulse 517 float tangentImpulse; 518 519 /// The maximum normal impulse applied during sub-stepping. This is important 520 /// to identify speculative contact points that had an interaction in the time step. 521 float maxNormalImpulse; 522 523 /// Relative normal velocity pre-solve. Used for hit events. If the normal impulse is 524 /// zero then there was no hit. Negative means shapes are approaching. 525 float normalVelocity; 526 527 /// Uniquely identifies a contact point between two shapes 528 uint16_t id; 529 530 /// Did this contact point exist the previous step? 531 bool persisted; 532 } b2ManifoldPoint; 533 534 /// A contact manifold describes the contact points between colliding shapes. 535 /// @note Box2D uses speculative collision so some contact points may be separated. 536 typedef struct b2Manifold 537 { 538 /// The unit normal vector in world space, points from shape A to bodyB 539 b2Vec2 normal; 540 541 /// Angular impulse applied for rolling resistance. N * m * s = kg * m^2 / s 542 float rollingImpulse; 543 544 /// The manifold points, up to two are possible in 2D 545 b2ManifoldPoint points[2]; 546 547 /// The number of contacts points, will be 0, 1, or 2 548 int pointCount; 549 550 } b2Manifold; 551 552 /// Compute the contact manifold between two circles 553 B2_API b2Manifold b2CollideCircles( const b2Circle* circleA, b2Transform xfA, const b2Circle* circleB, b2Transform xfB ); 554 555 /// Compute the contact manifold between a capsule and circle 556 B2_API b2Manifold b2CollideCapsuleAndCircle( const b2Capsule* capsuleA, b2Transform xfA, const b2Circle* circleB, 557 b2Transform xfB ); 558 559 /// Compute the contact manifold between an segment and a circle 560 B2_API b2Manifold b2CollideSegmentAndCircle( const b2Segment* segmentA, b2Transform xfA, const b2Circle* circleB, 561 b2Transform xfB ); 562 563 /// Compute the contact manifold between a polygon and a circle 564 B2_API b2Manifold b2CollidePolygonAndCircle( const b2Polygon* polygonA, b2Transform xfA, const b2Circle* circleB, 565 b2Transform xfB ); 566 567 /// Compute the contact manifold between a capsule and circle 568 B2_API b2Manifold b2CollideCapsules( const b2Capsule* capsuleA, b2Transform xfA, const b2Capsule* capsuleB, b2Transform xfB ); 569 570 /// Compute the contact manifold between an segment and a capsule 571 B2_API b2Manifold b2CollideSegmentAndCapsule( const b2Segment* segmentA, b2Transform xfA, const b2Capsule* capsuleB, 572 b2Transform xfB ); 573 574 /// Compute the contact manifold between a polygon and capsule 575 B2_API b2Manifold b2CollidePolygonAndCapsule( const b2Polygon* polygonA, b2Transform xfA, const b2Capsule* capsuleB, 576 b2Transform xfB ); 577 578 /// Compute the contact manifold between two polygons 579 B2_API b2Manifold b2CollidePolygons( const b2Polygon* polygonA, b2Transform xfA, const b2Polygon* polygonB, b2Transform xfB ); 580 581 /// Compute the contact manifold between an segment and a polygon 582 B2_API b2Manifold b2CollideSegmentAndPolygon( const b2Segment* segmentA, b2Transform xfA, const b2Polygon* polygonB, 583 b2Transform xfB ); 584 585 /// Compute the contact manifold between a chain segment and a circle 586 B2_API b2Manifold b2CollideChainSegmentAndCircle( const b2ChainSegment* segmentA, b2Transform xfA, const b2Circle* circleB, 587 b2Transform xfB ); 588 589 /// Compute the contact manifold between a chain segment and a capsule 590 B2_API b2Manifold b2CollideChainSegmentAndCapsule( const b2ChainSegment* segmentA, b2Transform xfA, const b2Capsule* capsuleB, 591 b2Transform xfB, b2SimplexCache* cache ); 592 593 /// Compute the contact manifold between a chain segment and a rounded polygon 594 B2_API b2Manifold b2CollideChainSegmentAndPolygon( const b2ChainSegment* segmentA, b2Transform xfA, const b2Polygon* polygonB, 595 b2Transform xfB, b2SimplexCache* cache ); 596 597 /**@}*/ 598 599 /** 600 * @defgroup tree Dynamic Tree 601 * The dynamic tree is a binary AABB tree to organize and query large numbers of geometric objects 602 * 603 * Box2D uses the dynamic tree internally to sort collision shapes into a binary bounding volume hierarchy. 604 * This data structure may have uses in games for organizing other geometry data and may be used independently 605 * of Box2D rigid body simulation. 606 * 607 * A dynamic AABB tree broad-phase, inspired by Nathanael Presson's btDbvt. 608 * A dynamic tree arranges data in a binary tree to accelerate 609 * queries such as AABB queries and ray casts. Leaf nodes are proxies 610 * with an AABB. These are used to hold a user collision object. 611 * Nodes are pooled and relocatable, so I use node indices rather than pointers. 612 * The dynamic tree is made available for advanced users that would like to use it to organize 613 * spatial game data besides rigid bodies. 614 * @{ 615 */ 616 617 /// The dynamic tree structure. This should be considered private data. 618 /// It is placed here for performance reasons. 619 typedef struct b2DynamicTree 620 { 621 /// The tree nodes 622 struct b2TreeNode* nodes; 623 624 /// The root index 625 int root; 626 627 /// The number of nodes 628 int nodeCount; 629 630 /// The allocated node space 631 int nodeCapacity; 632 633 /// Node free list 634 int freeList; 635 636 /// Number of proxies created 637 int proxyCount; 638 639 /// Leaf indices for rebuild 640 int* leafIndices; 641 642 /// Leaf bounding boxes for rebuild 643 b2AABB* leafBoxes; 644 645 /// Leaf bounding box centers for rebuild 646 b2Vec2* leafCenters; 647 648 /// Bins for sorting during rebuild 649 int* binIndices; 650 651 /// Allocated space for rebuilding 652 int rebuildCapacity; 653 } b2DynamicTree; 654 655 /// These are performance results returned by dynamic tree queries. 656 typedef struct b2TreeStats 657 { 658 /// Number of internal nodes visited during the query 659 int nodeVisits; 660 661 /// Number of leaf nodes visited during the query 662 int leafVisits; 663 } b2TreeStats; 664 665 /// Constructing the tree initializes the node pool. 666 B2_API b2DynamicTree b2DynamicTree_Create( void ); 667 668 /// Destroy the tree, freeing the node pool. 669 B2_API void b2DynamicTree_Destroy( b2DynamicTree* tree ); 670 671 /// Create a proxy. Provide an AABB and a userData value. 672 B2_API int b2DynamicTree_CreateProxy( b2DynamicTree* tree, b2AABB aabb, uint64_t categoryBits, int userData ); 673 674 /// Destroy a proxy. This asserts if the id is invalid. 675 B2_API void b2DynamicTree_DestroyProxy( b2DynamicTree* tree, int proxyId ); 676 677 /// Move a proxy to a new AABB by removing and reinserting into the tree. 678 B2_API void b2DynamicTree_MoveProxy( b2DynamicTree* tree, int proxyId, b2AABB aabb ); 679 680 /// Enlarge a proxy and enlarge ancestors as necessary. 681 B2_API void b2DynamicTree_EnlargeProxy( b2DynamicTree* tree, int proxyId, b2AABB aabb ); 682 683 /// This function receives proxies found in the AABB query. 684 /// @return true if the query should continue 685 typedef bool b2TreeQueryCallbackFcn( int proxyId, int userData, void* context ); 686 687 /// Query an AABB for overlapping proxies. The callback class is called for each proxy that overlaps the supplied AABB. 688 /// @return performance data 689 B2_API b2TreeStats b2DynamicTree_Query( const b2DynamicTree* tree, b2AABB aabb, uint64_t maskBits, 690 b2TreeQueryCallbackFcn* callback, void* context ); 691 692 /// This function receives clipped ray cast input for a proxy. The function 693 /// returns the new ray fraction. 694 /// - return a value of 0 to terminate the ray cast 695 /// - return a value less than input->maxFraction to clip the ray 696 /// - return a value of input->maxFraction to continue the ray cast without clipping 697 typedef float b2TreeRayCastCallbackFcn( const b2RayCastInput* input, int proxyId, int userData, void* context ); 698 699 /// Ray cast against the proxies in the tree. This relies on the callback 700 /// to perform a exact ray cast in the case were the proxy contains a shape. 701 /// The callback also performs the any collision filtering. This has performance 702 /// roughly equal to k * log(n), where k is the number of collisions and n is the 703 /// number of proxies in the tree. 704 /// Bit-wise filtering using mask bits can greatly improve performance in some scenarios. 705 /// However, this filtering may be approximate, so the user should still apply filtering to results. 706 /// @param tree the dynamic tree to ray cast 707 /// @param input the ray cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1) 708 /// @param maskBits mask bit hint: `bool accept = (maskBits & node->categoryBits) != 0;` 709 /// @param callback a callback class that is called for each proxy that is hit by the ray 710 /// @param context user context that is passed to the callback 711 /// @return performance data 712 B2_API b2TreeStats b2DynamicTree_RayCast( const b2DynamicTree* tree, const b2RayCastInput* input, uint64_t maskBits, 713 b2TreeRayCastCallbackFcn* callback, void* context ); 714 715 /// This function receives clipped ray cast input for a proxy. The function 716 /// returns the new ray fraction. 717 /// - return a value of 0 to terminate the ray cast 718 /// - return a value less than input->maxFraction to clip the ray 719 /// - return a value of input->maxFraction to continue the ray cast without clipping 720 typedef float b2TreeShapeCastCallbackFcn( const b2ShapeCastInput* input, int proxyId, int userData, void* context ); 721 722 /// Ray cast against the proxies in the tree. This relies on the callback 723 /// to perform a exact ray cast in the case were the proxy contains a shape. 724 /// The callback also performs the any collision filtering. This has performance 725 /// roughly equal to k * log(n), where k is the number of collisions and n is the 726 /// number of proxies in the tree. 727 /// @param tree the dynamic tree to ray cast 728 /// @param input the ray cast input data. The ray extends from p1 to p1 + maxFraction * (p2 - p1). 729 /// @param maskBits filter bits: `bool accept = (maskBits & node->categoryBits) != 0;` 730 /// @param callback a callback class that is called for each proxy that is hit by the shape 731 /// @param context user context that is passed to the callback 732 /// @return performance data 733 B2_API b2TreeStats b2DynamicTree_ShapeCast( const b2DynamicTree* tree, const b2ShapeCastInput* input, uint64_t maskBits, 734 b2TreeShapeCastCallbackFcn* callback, void* context ); 735 736 /// Get the height of the binary tree. 737 B2_API int b2DynamicTree_GetHeight( const b2DynamicTree* tree ); 738 739 /// Get the ratio of the sum of the node areas to the root area. 740 B2_API float b2DynamicTree_GetAreaRatio( const b2DynamicTree* tree ); 741 742 /// Get the number of proxies created 743 B2_API int b2DynamicTree_GetProxyCount( const b2DynamicTree* tree ); 744 745 /// Rebuild the tree while retaining subtrees that haven't changed. Returns the number of boxes sorted. 746 B2_API int b2DynamicTree_Rebuild( b2DynamicTree* tree, bool fullBuild ); 747 748 /// Get the number of bytes used by this tree 749 B2_API int b2DynamicTree_GetByteCount( const b2DynamicTree* tree ); 750 751 /// Get proxy user data 752 B2_API int b2DynamicTree_GetUserData( const b2DynamicTree* tree, int proxyId ); 753 754 /// Get the AABB of a proxy 755 B2_API b2AABB b2DynamicTree_GetAABB( const b2DynamicTree* tree, int proxyId ); 756 757 /// Validate this tree. For testing. 758 B2_API void b2DynamicTree_Validate( const b2DynamicTree* tree ); 759 760 /// Validate this tree has no enlarged AABBs. For testing. 761 B2_API void b2DynamicTree_ValidateNoEnlarged( const b2DynamicTree* tree ); 762 763 764 765 /**@}*/