Bullet Collision Detection

Collision Detection 

The collision detection provides algorithms and acceleration structures for closest point (distance and penetration) queries as well as ray and convex sweep tests. The main data structures are: 

충돌 감지는 가장 가까운 지점 (거리 및 침투) 쿼리와 광선 및 볼록 스윕 테스트에 대한 알고리즘 및 가속 구조를 제공합니다. 주요 데이터 구조는 다음과 같습니다.

   • btCollisionObject is the object that has a world transform and a collision shape. 

   • btCollisionShape describes the collision shape of a collision object, such as box, sphere, convex hull or triangle mesh. A single collision shape can be shared among multiple collision objects. 

   • btGhostObject is a special btCollisionObject, useful for fast localized collision queries. 

   • btCollisionWorld stores all btCollisionObjects and provides an interface to perform queries.

 

The broadphase collision detection provides acceleration structure to quickly reject pairs of objects based on axis aligned bounding box (AABB) overlap. Several different broadphase acceleration structures are available: 

광 위상 충돌 감지는 AABB (Axis Aligned Bounding Box) 중첩을 기반으로 객체 쌍을 빠르게 거부하는 가속 구조를 제공합니다. 다음과 같은 다양한 광대역 가속 구조를 사용할 수 있습니다.

   • btDbvtBroadphase uses a fast dynamic bounding volume hierarchy based on AABB tree 

   • btAxisSweep3 and bt32BitAxisSweep3 implement incremental 3d sweep and prune 

   • btSimpleBroadphase is a brute force reference implementation. It is slow but easy to understand and useful for debugging and testing a more advanced broadphase. 

The broadphase adds and removes overlapping pairs from a pair cache. Overlapping pairs are persistent over time and can cache information such as previous contact constraint forces that can be used for ‘warmstarting’: using the previous solution to converge faster towards constraint solving.  

broadphase는 쌍 캐시에서 겹치는 쌍을 추가하고 제거합니다. 겹치는 쌍은 시간이 지나도 지속되며 '웜 스타트'에 사용할 수있는 이전 접촉 구속력과 같은 정보를 캐시 할 수 있습니다. 이전 솔루션을 사용하여 구속 해결을 위해 더 빠르게 수렴합니다.

 

A collision dispatcher iterates over each pair, searches for a matching collision algorithm based on the types of objects involved and executes the collision algorithm computing contact points. 

충돌 디스패처는 각 쌍을 반복하고 관련된 객체 유형에 따라 일치하는 충돌 알고리즘을 검색하고 충돌 알고리즘 계산 ​​접점을 실행합니다.

   • btPersistentManifold is a contact point cache to store contact points for a given pair of objects.

 

Collision Shapes

Bullet supports a large variety of different collision shapes, and it is possible to add your own. For best performance and quality it is important to choose the collision shape that suits your purpose. The following diagram can help making a decision:

Bullet은 다양한 충돌 모양을 지원하며 자신 만의 충돌 모양을 추가 할 수 있습니다. 최상의 성능과 품질을 위해 목적에 맞는 충돌 모양을 선택하는 것이 중요합니다. 다음 다이어그램은 결정을 내리는 데 도움이 될 수 있습니다.

Convex Primitives

Most primitive shapes are centered around the origin of their local coordinate frame: 

btBoxShape : Box defined by the half extents (half length) of its sides  

btSphereShape : Sphere defined by its radius  

btCapsuleShape: Capsule around the Y axis. Also btCapsuleShapeX/Z 

btCylinderShape : Cylinder around the Y axis. Also btCylinderShapeX/Z.  btConeShape : Cone around the Y axis. Also btConeShapeX/Z. 

btMultiSphereShape : Convex hull of multiple spheres, that can be used to create a Capsule (by passing 2 spheres) or other convex shapes.  

 

Compound Shapes

Multiple convex shapes can be combined into a composite or compound shape, using the btCompoundShape. This is a concave shape made out of convex sub parts, called child shapes. Each child shape has its own local offset transform, relative to the btCompoundShape. It is a good idea to approximate concave shapes using a collection of convex hulls, and store them in a btCompoundShape. You can adjust the center of mass using a utility method btCompoundShape ::calculatePrincipalAxisTransform.

 

Convex Hull Shapes

Bullet supports several ways to represent a convex triangle meshes. The easiest way is to create a btConvexHullShape and pass in an array of vertices. In some cases the graphics mesh contains too many vertices to be used directly as btConvexHullShape. In that case, try to reduce the number of vertices. 

Bullet은 볼록한 삼각형 메시를 표현하는 여러 가지 방법을 지원합니다. 가장 쉬운 방법은 btConvexHullShape를 만들고 정점 배열을 전달하는 것입니다. 경우에 따라 그래픽 메시에 btConvexHullShape로 직접 사용하기에는 너무 많은 정점이 포함되어 있습니다. 이 경우 정점 수를 줄이십시오.

 

Concave Triangle Meshes 오목 삼각형 메쉬

For static world environment, a very efficient way to represent static triangle meshes is to use a btBvhTriangleMeshShape. This collision shape builds an internal acceleration structure from a btTriangleMesh or btStridingMeshInterface.  Instead of building the tree at run-time, it is also possible to serialize the binary tree to disc. See examples/ConcaveDemo how to save and load this btOptimizedBvh tree acceleration structure. When you have several instances of the same triangle mesh, but with different scaling, you can instance a btBvhTriangleMeshShape multiple times using the btScaledBvhTriangleMeshShape. The btBvhTriangleMeshShape can store multiple mesh parts. It keeps a triangle index and part index in a 32bit structure, reserving 10 bits for the part Id and the remaining 22 bits for triangle index. If you need more than 2 million triangles, either split the the triangle mesh into multiple sub meshes, or change the default in #define MAX_NUM_PARTS_IN_BITS in the file src\BulletCollision\BroadphaseCollision\btQuantizedBvh.h 

정적 세계 환경에서 정적 삼각형 메시를 표현하는 매우 효율적인 방법은 btBvhTriangleMeshShape를 사용하는 것입니다. 이 충돌 모양은 For static world 환경에서 내부 가속 구조를 구축합니다. 정적 삼각형 메시를 표현하는 매우 효율적인 방법은 btBvhTriangleMeshShape를 사용하는 것입니다. 이 충돌 모양은 btTriangleMesh 또는 btStridingMeshInterface에서 내부 가속 구조를 만듭니다. 런타임에 트리를 구축하는 대신 바이너리 트리를 디스크에 직렬화 할 수도 있습니다. 이 btOptimizedBvh 트리 가속 구조를 저장하고로드하는 방법은 examples / ConcaveDemo를 참조하십시오. 동일한 삼각형 메시의 인스턴스가 여러 개 있지만 배율이 다른 경우 btScaledBvhTriangleMeshShape를 사용하여 btBvhTriangleMeshShape를 여러 번 인스턴스화 할 수 있습니다. btBvhTriangleMeshShape는 여러 메쉬 부분을 저장할 수 있습니다. 32 비트 구조의 삼각형 인덱스와 부분 인덱스를 유지하여 부분 ID에 대해 10 비트를 예약하고 삼각형 인덱스에 대해 나머지 22 비트를 예약합니다. 2 백만 개 이상의 삼각형이 필요한 경우 삼각형 메시를 여러 하위 메시로 분할하거나 src \ BulletCollision \ BroadphaseCollision \ btQuantizedBvh.h 파일의 #define MAX_NUM_PARTS_IN_BITS에서 기본값을 변경하십시오.

 

Convex Decomposition

Ideally, concave meshes should only be used for static artwork. Otherwise its convex hull should be used by passing the mesh to btConvexHullShape. If a single convex shape is not detailed enough, multiple convex parts can be combined into a composite object called btCompoundShape. Convex decomposition can be used to decompose the concave mesh into several convex parts. See the Demos/ConvexDecompositionDemo for an automatic way of doing convex decomposition.

이상적으로 오목한 메시는 정적 아트웍에만 사용해야합니다. 그렇지 않으면 메시를 btConvexHullShape에 전달하여 볼록 껍질을 사용해야합니다. 단일 볼록 모양이 충분히 상세하지 않은 경우 여러 볼록 부분을 btCompoundShape라는 복합 개체로 결합 할 수 있습니다. 볼록 분해를 사용하여 오목 메시를 여러 볼록 부분으로 분해 할 수 있습니다. 볼록 분해를 자동으로 수행하는 방법은 Demos / ConvexDecompositionDemo를 참조하세요.

 

Height field

Bullet provides support for the special case of a flat 2D concave terrain through the btHeightfieldTerrainShape. See examples/TerrainDemo for its usage.

Bullet은 btHeightfieldTerrainShape를 통해 평평한 2D 오목 지형의 특수한 경우를 지원합니다. 사용법은 examples / TerrainDemo를 참조하십시오.

 

btStaticPlaneShape

As the name suggests, the btStaticPlaneShape can represent an infinite plane or half space. This shape can only be used for static, non-moving objects. This shape has been introduced mainly for demo purposes.

이름에서 알 수 있듯이 btStaticPlaneShape는 무한 평면 또는 절반 공간을 나타낼 수 있습니다. 이 모양은 움직이지 않는 정적 개체에만 사용할 수 있습니다. 이 모양은 주로 데모 목적으로 도입되었습니다.

 

Scaling of Collision Shapes

Some collision shapes can have local scaling applied. Use btCollisionShape::setScaling(vector3). Non uniform scaling with different scaling values for each axis, can be used for btBoxShape, btMultiSphereShape, btConvexShape, btTriangleMeshShape. Uniform scaling, using x value for all axis, can be used for btSphereShape. Note that a non-uniform scaled sphere can be created by using a btMultiSphereShape with 1 sphere.  As mentioned before, the btScaledBvhTriangleMeshShape allows to instantiate a btBvhTriangleMeshShape at different non-uniform scale factors. The btUniformScalingShape allows to instantiate convex shapes at different scales, reducing the amount of memory.

일부 충돌 모양에는 로컬 배율이 적용될 수 있습니다. btCollisionShape :: setScaling (vector3)을 사용하십시오. btBoxShape, btMultiSphereShape, btConvexShape, btTriangleMeshShape에 사용할 수 있습니다. 모든 축에 x 값을 사용하는 균일 한 배율 조정은 btSphereShape에 사용할 수 있습니다. 1 개의 구가있는 btMultiSphereShape를 사용하여 비 균일 스케일 된 구를 만들 수 있습니다. 앞서 언급했듯이 btScaledBvhTriangleMeshShape를 사용하면 서로 다른 비 균일 배율에서 btBvhTriangleMeshShape를 인스턴스화 할 수 있습니다. btUniformScalingShape를 사용하면 볼록한 모양을 다른 배율로 인스턴스화하여 메모리 양을 줄일 수 있습니다.

 

Collision Margin

Bullet uses a small collision margin for collision shapes, to improve performance and reliability of the collision detection. It is best not to modify the default collision margin, and if you do use a positive value: zero margin might introduce problems. By default this collision margin is set to 0.04, which is 4 centimeter if your units are in meters (recommended).  

Dependent on which collision shapes, the margin has different meaning. Generally the collision margin will expand the object. This will create a small gap. To compensate for this, some shapes will subtract the margin from the actual size. For example, the btBoxShape subtracts the collision margin from the half extents. For a btSphereShape, the entire radius is collision margin so no gap will occur. Don’t override the collision margin for spheres. For convex hulls, cylinders and cones, the margin is added to the extents of the object, so a gap will occur, unless you adjust the graphics mesh or collision size. For convex hull objects, there is a method to remove the gap introduced by the margin, by shrinking the object. See the examples/Importers/ImportBsp for this advanced use.

Bullet은 충돌 모양에 대해 작은 충돌 마진을 사용하여 충돌 감지의 성능과 신뢰성을 향상시킵니다. 기본 충돌 마진을 수정하지 않는 것이 가장 좋으며 양수 값을 사용하는 경우 마진이 0이면 문제가 발생할 수 있습니다. 기본적으로이 충돌 여백은 0.04로 설정되며 단위가 미터 단위 인 경우 4 센티미터입니다 (권장).

충돌 모양에 따라 여백은 다른 의미를 갖습니다. 일반적으로 충돌 여백은 개체를 확장합니다. 이것은 작은 간격을 만들 것입니다. 이를 보완하기 위해 일부 도형은 실제 크기에서 여백을 뺍니다. 예를 들어, btBoxShape는 절반 범위에서 충돌 여백을 뺍니다. btSphereShape의 경우 전체 반경이 충돌 마진이므로 간격이 발생하지 않습니다. 구의 충돌 여백을 재정의하지 마십시오. 볼록 껍질, 원통 및 원뿔의 경우 여백이 개체 범위에 추가되므로 그래픽 메시 또는 충돌 크기를 조정하지 않으면 간격이 발생합니다. 볼록한 껍질 물체의 경우 물체를 축소하여 여백으로 인한 틈새를 제거하는 방법이 있습니다. 이 고급 사용에 대해서는 examples / Importers / ImportBsp를 참조하십시오.

 

Collision Matrix

For each pair of shape types, Bullet will dispatch a certain collision algorithm, by using the dispatcher. By default, the entire matrix is filled with the following algorithms. Note that Convex represents convex polyhedron, cylinder, cone and capsule and other GJK compatible primitives. GJK stands for Gilbert, Johnson and Keerthi, the people behind this convex distance calculation algorithm. It is combined with EPA for penetration depth calculation. EPA stands for Expanding Polythope Algorithm by Gino van den Bergen. Bullet has its own free implementation of GJK and EPA.

각 모양 유형 쌍에 대해 Bullet은 디스패처를 사용하여 특정 충돌 알고리즘을 디스패치합니다. 기본적으로 전체 행렬은 다음 알고리즘으로 채워집니다. 볼록은 볼록 다면체, 원통, 원뿔 및 캡슐 및 기타 GJK 호환 기본 요소를 나타냅니다. GJK는이 볼록 거리 계산 알고리즘 뒤에있는 사람들 인 Gilbert, Johnson 및 Keerthi를 나타냅니다. 침투 깊이 계산을 위해 EPA와 결합됩니다. EPA는 Gino van den Bergen의 Expanding Polythope Algorithm의 약자입니다. Bullet에는 GJK 및 EPA의 자체 무료 구현이 있습니다.

 

Registering custom collision shapes and algorithms

The user can register a custom collision detection algorithm and override any entry in this Collision Matrix by using the btDispatcher::registerCollisionAlgorithm. See examples/UserCollisionAlgorithm for an example, that registers a SphereSphere collision algorithm. 

사용자는 사용자 정의 충돌 감지 알고리즘을 등록하고 btDispatcher :: registerCollisionAlgorithm을 사용하여이 Collision Matrix의 모든 항목을 재정의 할 수 있습니다. SphereSphere 충돌 알고리즘을 등록하는 예제는 examples / UserCollisionAlgorithm을 참조하세요.