1 2 /* 3 * Copyright (c) 2006-2009 Erin Catto http://www.box2d.org 4 * 5 * This software is provided 'as-is', without any express or implied 6 * warranty. In no event will the authors be held liable for any damages 7 * arising from the use of this software. 8 * Permission is granted to anyone to use this software for any purpose, 9 * including commercial applications, and to alter it and redistribute it 10 * freely, subject to the following restrictions: 11 * 1. The origin of this software must not be misrepresented; you must not 12 * claim that you wrote the original software. If you use this software 13 * in a product, an acknowledgment in the product documentation would be 14 * appreciated but is not required. 15 * 2. Altered source versions must be plainly marked as such, and must not be 16 * misrepresented as being the original software. 17 * 3. This notice may not be removed or altered from any source distribution. 18 */ 19 20 #ifndef B2_DISTANCE_H 21 #define B2_DISTANCE_H 22 23 #include <Box2D/Common/b2Math.h> 24 25 class b2Shape; 26 27 /// A distance proxy is used by the GJK algorithm. 28 /// It encapsulates any shape. 29 struct b2DistanceProxy 30 { 31 b2DistanceProxy() : m_vertices(NULL), m_count(0), m_radius(0.0f) {} 32 33 /// Initialize the proxy using the given shape. The shape 34 /// must remain in scope while the proxy is in use. 35 void Set(const b2Shape* shape, int32 index); 36 37 /// Get the supporting vertex index in the given direction. 38 int32 GetSupport(const b2Vec2& d) const; 39 40 /// Get the supporting vertex in the given direction. 41 const b2Vec2& GetSupportVertex(const b2Vec2& d) const; 42 43 /// Get the vertex count. 44 int32 GetVertexCount() const; 45 46 /// Get a vertex by index. Used by b2Distance. 47 const b2Vec2& GetVertex(int32 index) const; 48 49 b2Vec2 m_buffer[2]; 50 const b2Vec2* m_vertices; 51 int32 m_count; 52 float32 m_radius; 53 }; 54 55 /// Used to warm start b2Distance. 56 /// Set count to zero on first call. 57 struct b2SimplexCache 58 { 59 float32 metric; ///< length or area 60 uint16 count; 61 uint8 indexA[3]; ///< vertices on shape A 62 uint8 indexB[3]; ///< vertices on shape B 63 }; 64 65 /// Input for b2Distance. 66 /// You have to option to use the shape radii 67 /// in the computation. Even 68 struct b2DistanceInput 69 { 70 b2DistanceProxy proxyA; 71 b2DistanceProxy proxyB; 72 b2Transform transformA; 73 b2Transform transformB; 74 bool useRadii; 75 }; 76 77 /// Output for b2Distance. 78 struct b2DistanceOutput 79 { 80 b2Vec2 pointA; ///< closest point on shapeA 81 b2Vec2 pointB; ///< closest point on shapeB 82 float32 distance; 83 int32 iterations; ///< number of GJK iterations used 84 }; 85 86 /// Compute the closest points between two shapes. Supports any combination of: 87 /// b2CircleShape, b2PolygonShape, b2EdgeShape. The simplex cache is input/output. 88 /// On the first call set b2SimplexCache.count to zero. 89 void b2Distance(b2DistanceOutput* output, 90 b2SimplexCache* cache, 91 const b2DistanceInput* input); 92 93 94 ////////////////////////////////////////////////////////////////////////// 95 96 inline int32 b2DistanceProxy::GetVertexCount() const 97 { 98 return m_count; 99 } 100 101 inline const b2Vec2& b2DistanceProxy::GetVertex(int32 index) const 102 { 103 b2Assert(0 <= index && index < m_count); 104 return m_vertices[index]; 105 } 106 107 inline int32 b2DistanceProxy::GetSupport(const b2Vec2& d) const 108 { 109 int32 bestIndex = 0; 110 float32 bestValue = b2Dot(m_vertices[0], d); 111 for (int32 i = 1; i < m_count; ++i) 112 { 113 float32 value = b2Dot(m_vertices[i], d); 114 if (value > bestValue) 115 { 116 bestIndex = i; 117 bestValue = value; 118 } 119 } 120 121 return bestIndex; 122 } 123 124 inline const b2Vec2& b2DistanceProxy::GetSupportVertex(const b2Vec2& d) const 125 { 126 int32 bestIndex = 0; 127 float32 bestValue = b2Dot(m_vertices[0], d); 128 for (int32 i = 1; i < m_count; ++i) 129 { 130 float32 value = b2Dot(m_vertices[i], d); 131 if (value > bestValue) 132 { 133 bestIndex = i; 134 bestValue = value; 135 } 136 } 137 138 return m_vertices[bestIndex]; 139 } 140 141 #endif 142