diff options
Diffstat (limited to 'Client/ThirdParty/Box2D/docs/collision.md')
| -rw-r--r-- | Client/ThirdParty/Box2D/docs/collision.md | 433 |
1 files changed, 433 insertions, 0 deletions
diff --git a/Client/ThirdParty/Box2D/docs/collision.md b/Client/ThirdParty/Box2D/docs/collision.md new file mode 100644 index 0000000..fe00aa4 --- /dev/null +++ b/Client/ThirdParty/Box2D/docs/collision.md @@ -0,0 +1,433 @@ +# Collision Module +The Collision module contains shapes and functions that operate on them. +The module also contains a dynamic tree and broad-phase to acceleration +collision processing of large systems. + +The collision module is designed to be usable outside of the dynamic +system. For example, you can use the dynamic tree for other aspects of +your game besides physics. + +However, the main purpose of Box2D is to provide a rigid body physics +engine, so the using the collision module by itself may feel limited for +some applications. Likewise, I will not make a strong effort to document +it or polish the APIs. + +## Shapes +Shapes describe collision geometry and may be used independently of +physics simulation. At a minimum, you should understand how to create +shapes that can be later attached to rigid bodies. + +Box2D shapes implement the b2Shape base class. The base class defines +functions to: +- Test a point for overlap with the shape. +- Perform a ray cast against the shape. +- Compute the shape's AABB. +- Compute the mass properties of the shape. + +In addition, each shape has a type member and a radius. The radius even +applies to polygons, as discussed below. + +Keep in mind that a shape does not know about bodies and stand apart +from the dynamics system. Shapes are stored in a compact form that is +optimized for size and performance. As such, shapes are not easily moved +around. You have to manually set the shape vertex positions to move a +shape. However, when a shape is attached to a body using a fixture, the +shapes move rigidly with the host body. In summary: +- When a shape is **not** attached to a body, you can view it's vertices as being expressed in world-space. +- When a shape is attached to a body, you can view it's vertices as being expressed in local coordinates. + +### Circle Shapes +Circle shapes have a position and radius. Circles are solid. You cannot +make a hollow circle using the circle shape. + +```cpp +b2CircleShape circle; +circle.m_p.Set(2.0f, 3.0f); +circle.m_radius = 0.5f; +``` + +### Polygon Shapes +Polygon shapes are solid convex polygons. A polygon is convex when all +line segments connecting two points in the interior do not cross any +edge of the polygon. Polygons are solid and never hollow. A polygon must +have 3 or more vertices. + + + +Polygons vertices are stored with a counter clockwise winding (CCW). We +must be careful because the notion of CCW is with respect to a +right-handed coordinate system with the z-axis pointing out of the +plane. This might turn out to be clockwise on your screen, depending on +your coordinate system conventions. + + + +The polygon members are public, but you should use initialization +functions to create a polygon. The initialization functions create +normal vectors and perform validation. + +You can create a polygon shape by passing in a vertex array. The maximal +size of the array is controlled by `b2_maxPolygonVertices` which has a +default value of 8. This is sufficient to describe most convex polygons. + +The `b2PolygonShape::Set` function automatically computes the convex hull +and establishes the proper winding order. This function is fast when the +number of vertices is low. If you increase `b2_maxPolygonVertices`, then +the convex hull computation might become slow. Also note that the convex +hull function may eliminate and/or re-order the points you provide. +Vertices that are closer than `b2_linearSlop` may be merged. + +```cpp +// This defines a triangle in CCW order. +b2Vec2 vertices[3]; +vertices[0].Set(0.0f, 0.0f); +vertices[1].Set(1.0f, 0.0f); +vertices[2].Set(0.0f, 1.0f); + +int32 count = 3; +b2PolygonShape polygon; +polygon.Set(vertices, count); +``` + +The polygon shape has some convenience functions to create boxes. + +```cpp +void SetAsBox(float hx, float hy); +void SetAsBox(float hx, float hy, const b2Vec2& center, float angle); +``` + +Polygons inherit a radius from b2Shape. The radius creates a skin around +the polygon. The skin is used in stacking scenarios to keep polygons +slightly separated. This allows continuous collision to work against the +core polygon. + + + +The polygon skin helps prevent tunneling by keeping the polygons +separated. This results in small gaps between the shapes. Your visual +representation can be larger than the polygon to hide any gaps. + + + +Not that polygon skin is only provided to help with continuous collision. +The purpose is not to simulate rounded polygons. + +### Edge Shapes +Edge shapes are line segments. These are provided to assist in making a +free-form static environment for your game. A major limitation of edge +shapes is that they can collide with circles and polygons but not with +themselves. The collision algorithms used by Box2D require that at least +one of two colliding shapes have volume. Edge shapes have no volume, so +edge-edge collision is not possible. + +```cpp +// This an edge shape. +b2Vec2 v1(0.0f, 0.0f); +b2Vec2 v2(1.0f, 0.0f); + +b2EdgeShape edge; +edge.SetTwoSided(v1, v2); +``` + +In many cases a game environment is constructed by connecting several +edge shapes end-to-end. This can give rise to an unexpected artifact +when a polygon slides along the chain of edges. In the figure below we +see a box colliding with an internal vertex. These *ghost* collisions +are caused when the polygon collides with an internal vertex generating +an internal collision normal. + + + +If edge1 did not exist this collision would seem fine. With edge1 +present, the internal collision seems like a bug. But normally when +Box2D collides two shapes, it views them in isolation. + +Fortunately, the edge shape provides a mechanism for eliminating ghost +collisions by storing the adjacent *ghost* vertices. Box2D uses these +ghost vertices to prevent internal collisions. + + + +The Box2D algorithm for dealing with ghost collisions only supports +one-sided collision. The front face is to the right when looking from the first +vertex towards the second vertex. This matches the CCW winding order +used by polygons. + +```cpp +// This is an edge shape with ghost vertices. +b2Vec2 v0(1.7f, 0.0f); +b2Vec2 v1(1.0f, 0.25f); +b2Vec2 v2(0.0f, 0.0f); +b2Vec2 v3(-1.7f, 0.4f); + +b2EdgeShape edge; +edge.SetOneSided(v0, v1, v2, v3); +``` + +In general stitching edges together this way is a bit wasteful and +tedious. This brings us to chain shapes. + +### Chain Shapes + +The chain shape provides an efficient way to connect many edges together +to construct your static game worlds. Chain shapes automatically +eliminate ghost collisions and provide one-sided collision. The collision is +one-sided to eliminate ghost collisions. + +If you don't care about ghost collisions, you can just create a bunch of +two-sided edge shapes. The efficiency is similar. + +The simplest way to use chain shapes is to create loops. Simply provide an +array of vertices. + +```cpp +b2Vec2 vs[4]; +vs[0].Set(1.7f, 0.0f); +vs[1].Set(1.0f, 0.25f); +vs[2].Set(0.0f, 0.0f); +vs[3].Set(-1.7f, 0.4f); + +b2ChainShape chain; +chain.CreateLoop(vs, 4); +``` + +The edge normal depends on the winding order. A counter-clockwise winding order orients the normal outwards and a clockwise winding order orients the normal inwards. + + + + + +You may have a scrolling game world and would like to connect several chains together. +You can connect chains together using ghost vertices, like we did with b2EdgeShape. + + + +```cpp +b2ChainShape::CreateChain(const b2Vec2* vertices, int32 count, + const b2Vec2& prevVertex, const b2Vec2& nextVertex); +``` + +Self-intersection of chain shapes is not supported. It might work, it +might not. The code that prevents ghost collisions assumes there are no +self-intersections of the chain. Also, very close vertices can cause +problems. Make sure all your edges are longer than b2_linearSlop (5mm). + + + +Each edge in the chain is treated as a child shape and can be accessed +by index. When a chain shape is connected to a body, each edge gets its +own bounding box in the broad-phase collision tree. + +```cpp +// Visit each child edge. +for (int32 i = 0; i \< chain.GetChildCount(); ++i) +{ + b2EdgeShape edge; + chain.GetChildEdge(&edge, i); + + ... +} +``` + +## Geometric Queries +You can perform a couple geometric queries on a single shape. + +### Shape Point Test +You can test a point for overlap with a shape. You provide a transform +for the shape and a world point. + +```cpp +b2Transform transform; +transform.SetIdentity(); +b2Vec2 point(5.0f, 2.0f); + +bool hit = shape->TestPoint(transform, point); +``` + +Edge and chain shapes always return false, even if the chain is a loop. + +### Shape Ray Cast +You can cast a ray at a shape to get the point of first intersection and normal vector. A child index is included for chain shapes because the ray cast will only check a single edge at a time. + +> **Caution**: +> No hit will register if the ray starts inside a convex shape like a circle or polygon. This is consistent with Box2D treating convex shapes as solid. +> + +```cpp +b2Transfrom transform; +transform.SetIdentity(); + +b2RayCastInput input; +input.p1.Set(0.0f, 0.0f); +input.p2.Set(1.0f, 0.0f); +input.maxFraction = 1.0f; +int32 childIndex = 0; + +b2RayCastOutput output; +bool hit = shape->RayCast(&output, input, transform, childIndex); + +if (hit) +{ + b2Vec2 hitPoint = input.p1 + output.fraction * (input.p2 -- input.p1); + ... +} +``` + +## Pairwise Functions +The Collision module contains functions that take a pair of shapes and compute some results. These include: +- Overlap +- Contact manifolds +- Distance +- Time of impact + +### Overlap +You can test two shapes for overlap using this function: + +```cpp +b2Transform xfA = ..., xfB = ...; +bool overlap = b2TestOverlap(shapeA, indexA, shapeB, indexB, xfA, xfB); +``` + +Again you must provide child indices to for the case of chain shapes. + +### Contact Manifolds +Box2D has functions to compute contact points for overlapping shapes. If +we consider circle-circle or circle-polygon, we can only get one contact +point and normal. In the case of polygon-polygon we can get two points. +These points share the same normal vector so Box2D groups them into a +manifold structure. The contact solver takes advantage of this to +improve stacking stability. + + + +Normally you don't need to compute contact manifolds directly, however +you will likely use the results produced in the simulation. + +The b2Manifold structure holds a normal vector and up to two contact +points. The normal and points are held in local coordinates. As a +convenience for the contact solver, each point stores the normal and +tangential (friction) impulses. + +The data stored in b2Manifold is optimized for internal use. If you need +this data, it is usually best to use the b2WorldManifold structure to +generate the world coordinates of the contact normal and points. You +need to provide a b2Manifold and the shape transforms and radii. + +```cpp +b2WorldManifold worldManifold; +worldManifold.Initialize(&manifold, transformA, shapeA.m_radius, +transformB, shapeB.m_radius); + +for (int32 i = 0; i \< manifold.pointCount; ++i) +{ + b2Vec2 point = worldManifold.points[i]; + ... +} +``` + +Notice that the world manifold uses the point count from the original +manifold. + +During simulation shapes may move and the manifolds may change. Points +may be added or removed. You can detect this using b2GetPointStates. + +```cpp +b2PointState state1[2], state2[2]; +b2GetPointStates(state1, state2, &manifold1, &manifold2); + +if (state1[0] == b2_removeState) +{ + // process event +} +``` + +### Distance +The `b2Distance` function can be used to compute the distance between two +shapes. The distance function needs both shapes to be converted into a +b2DistanceProxy. There is also some caching used to warm start the +distance function for repeated calls. + + + +### Time of Impact +If two shapes are moving fast, they may *tunnel* through each other in a +single time step. + + + +The `b2TimeOfImpact` function is used to determine the time when two +moving shapes collide. This is called the *time of impact* (TOI). The +main purpose of `b2TimeOfImpact` is for tunnel prevention. In particular, +it is designed to prevent moving objects from tunneling outside of +static level geometry. + +This function accounts for rotation and translation of both shapes, +however if the rotations are large enough, then the function may miss a +collision. However the function will still report a non-overlapped time +and will capture all translational collisions. + +The time of impact function identities an initial separating axis and +ensures the shapes do not cross on that axis. This might miss collisions +that are clear at the final positions. While this approach may miss some +collisions, it is very fast and adequate for tunnel prevention. + + + + + +It is difficult to put a restriction on the rotation magnitude. There +may be cases where collisions are missed for small rotations. Normally, +these missed rotational collisions should not harm game play. They tend +to be glancing collisions. + +The function requires two shapes (converted to b2DistanceProxy) and two +b2Sweep structures. The sweep structure defines the initial and final +transforms of the shapes. + +You can use fixed rotations to perform a *shape cast*. In this case, the +time of impact function will not miss any collisions. + +## Dynamic Tree +The b2DynamicTree class is used by Box2D to organize large numbers of +shapes efficiently. The class does not know about shapes. Instead it +operates on axis-aligned bounding boxes (AABBs) with user data pointers. + +The dynamic tree is a hierarchical AABB tree. Each internal node in the +tree has two children. A leaf node is a single user AABB. The tree uses +rotations to keep the tree balanced, even in the case of degenerate +input. + +The tree structure allows for efficient ray casts and region queries. +For example, you may have hundreds of shapes in your scene. You could +perform a ray cast against the scene in a brute force manner by ray +casting each shape. This would be inefficient because it does not take +advantage of shapes being spread out. Instead, you can maintain a +dynamic tree and perform ray casts against the tree. This traverses the +ray through the tree skipping large numbers of shapes. + +A region query uses the tree to find all leaf AABBs that overlap a query +AABB. This is faster than a brute force approach because many shapes can +be skipped. + + + + + +Normally you will not use the dynamic tree directly. Rather you will go +through the b2World class for ray casts and region queries. If you plan +to instantiate your own dynamic tree, you can learn how to use it by +looking at how Box2D uses it. + +## Broad-phase +Collision processing in a physics step can be divided into narrow-phase +and broad-phase. In the narrow-phase we compute contact points between +pairs of shapes. Imagine we have N shapes. Using brute force, we would +need to perform the narrow-phase for N*N/2 pairs. + +The b2BroadPhase class reduces this load by using a dynamic tree for +pair management. This greatly reduces the number of narrow-phase calls. + +Normally you do not interact with the broad-phase directly. Instead, +Box2D creates and manages a broad-phase internally. Also, b2BroadPhase +is designed with Box2D's simulation loop in mind, so it is likely not +suited for other use cases. |