My Project: dynamics.mod/NewtonDynamics/source/core/dgAABBPolygonSoup.h Source File

My Project

dgAABBPolygonSoup.h
Go to the documentation of this file.
1 /* Copyright (c) <2003-2011> <Julio Jerez, Newton Game Dynamics>
2 *
3 * This software is provided 'as-is', without any express or implied
4 * warranty. In no event will the authors be held liable for any damages
5 * arising from the use of this software.
6 *
7 * Permission is granted to anyone to use this software for any purpose,
8 * including commercial applications, and to alter it and redistribute it
9 * freely, subject to the following restrictions:
10 *
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 *
16 * 2. Altered source versions must be plainly marked as such, and must not be
17 * misrepresented as being the original software.
18 *
19 * 3. This notice may not be removed or altered from any source distribution.
20 */
21
22 #ifndef __DG_AABB_POLYGON_SOUP_H_
23 #define __DG_AABB_POLYGON_SOUP_H_
24
25 #include "dgStdafx.h"
26 #include "dgIntersections.h"
27 #include "dgPolygonSoupDatabase.h"
28
29
30 class dgPolygonSoupDatabaseBuilder;
31
32
33 class dgAABBPolygonSoup: public dgPolygonSoupDatabase
34 {
35 public:
36 class dgNode
37 {
38 public:
39 enum dgNodeType
40 {
41 m_binary = 0,
42 m_leaf,
43 };
44
45 class dgLeafNodePtr
46 {
47 #define DG_INDEX_COUNT_BITS 6
48
49 public:
50 DG_INLINE dgLeafNodePtr ()
51 {
52 dgAssert (0);
53 }
54
55 DG_INLINE dgLeafNodePtr (dgUnsigned32 node)
56 {
57 m_node = node;
58 dgAssert (!IsLeaf());
59 }
60
61 DG_INLINE dgUnsigned32 IsLeaf () const
62 {
63 return m_node & 0x80000000;
64 }
65
66 DG_INLINE dgUnsigned32 GetCount() const
67 {
68 dgAssert (IsLeaf());
69 return (m_node & (~0x80000000)) >> (32 - DG_INDEX_COUNT_BITS - 1);
70 }
71
72 DG_INLINE dgUnsigned32 GetIndex() const
73 {
74 dgAssert (IsLeaf());
75 return m_node & (~(-(1 << (32 - DG_INDEX_COUNT_BITS - 1))));
76 }
77
78
79 DG_INLINE dgLeafNodePtr (dgUnsigned32 faceIndexCount, dgUnsigned32 faceIndexStart)
80 {
81 dgAssert (faceIndexCount < (1<<DG_INDEX_COUNT_BITS));
82 m_node = 0x80000000 | (faceIndexCount << (32 - DG_INDEX_COUNT_BITS - 1)) | faceIndexStart;
83 }
84
85 DG_INLINE dgNode* GetNode (const void* const root) const
86 {
87 return ((dgNode*) root) + m_node;
88 }
89
90 union {
91 dgUnsigned32 m_node;
92 };
93 };
94
95
96 dgNode ()
97 :m_indexBox0(0)
98 ,m_indexBox1(0)
99 ,m_left(0)
100 ,m_right(0)
101 {
102 }
103
104 DG_INLINE dgFloat32 RayDistance (const dgFastRayTest& ray, const dgTriplex* const vertexArray) const
105 {
106 dgVector minBox (&vertexArray[m_indexBox0].m_x);
107 dgVector maxBox (&vertexArray[m_indexBox1].m_x);
108 return ray.BoxIntersect(minBox, maxBox);
109 }
110
111 DG_INLINE dgFloat32 BoxPenetration (const dgFastAABBInfo& obb, const dgTriplex* const vertexArray) const
112 {
113 dgVector p0 (&vertexArray[m_indexBox0].m_x);
114 dgVector p1 (&vertexArray[m_indexBox1].m_x);
115 dgVector minBox (p0 - obb.m_p1);
116 dgVector maxBox (p1 - obb.m_p0);
117 dgVector mask ((minBox.CompProduct4(maxBox)) < dgVector (dgFloat32 (0.0f)));
118 //mask = mask & mask.ShiftTripleRight();
119 //mask = mask & mask.ShiftTripleRight();
120 dgVector dist (maxBox.GetMin (minBox.Abs()) & mask);
121 dist = dist.GetMin(dist.ShiftTripleRight());
122 dist = dist.GetMin(dist.ShiftTripleRight());
123
124 if (dist.GetScalar() > dgFloat32 (0.0f)) {
125 dgVector origin ((p1 + p0).CompProduct4(dgVector::m_half));
126 dgVector size ((p1 - p0).CompProduct4(dgVector::m_half));
127
128 origin = obb.UntransformVector(origin);
129 size = obb.m_absDir.RotateVector(size);
130 dgVector q0 (origin - size);
131 dgVector q1 (origin + size);
132 dgVector minBox (q0 - obb.m_size);
133 dgVector maxBox (q1 + obb.m_size);
134 dgVector mask ((minBox.CompProduct4(maxBox)) < dgVector (dgFloat32 (0.0f)));
135 //mask = mask & mask.ShiftTripleRight();
136 //mask = mask & mask.ShiftTripleRight();
137 dgVector dist1 (maxBox.GetMin (minBox.Abs()) & mask);
138 dist1 = dist1.GetMin(dist1.ShiftTripleRight());
139 dist1 = dist1.GetMin(dist1.ShiftTripleRight());
140 dist = dist.GetMin(dist1);
141 }
142 return dist.GetScalar();
143 }
144
145 DG_INLINE dgFloat32 BoxIntersect (const dgFastRayTest& ray, const dgFastRayTest& obbRay, const dgFastAABBInfo& obb, const dgTriplex* const vertexArray) const
146 {
147 dgVector p0 (&vertexArray[m_indexBox0].m_x);
148 dgVector p1 (&vertexArray[m_indexBox1].m_x);
149 dgVector minBox (p0 - obb.m_p1);
150 dgVector maxBox (p1 - obb.m_p0);
151 dgFloat32 dist = ray.BoxIntersect(minBox, maxBox);
152 if (dist < dgFloat32 (1.0f)) {
153 dgVector origin ((p1 + p0).CompProduct4(dgVector::m_half));
154 dgVector size ((p1 - p0).CompProduct4(dgVector::m_half));
155
156 origin = obb.UntransformVector(origin);
157 size = obb.m_absDir.RotateVector(size);
158 dgVector q0 (origin - size);
159 dgVector q1 (origin + size);
160
161 dgVector minBox1 (q0 - obb.m_size);
162 dgVector maxBox1 (q1 + obb.m_size);
163 dgFloat32 dist1 = obbRay.BoxIntersect(minBox1, maxBox1);
164 //dgAssert (dist1 <= 1.0f);
165 //dgAssert (dist == dist1);
166 //dist = dist1;
167 dist = (dist1 > dgFloat32 (1.0f)) ? dist1 : dgMax (dist1, dist);
168 }
169 return dist;
170 }
171
172
173
174 dgInt32 m_indexBox0;
175 dgInt32 m_indexBox1;
176 dgLeafNodePtr m_left;
177 dgLeafNodePtr m_right;
178 };
179
180 class dgSpliteInfo;
181 class dgNodeBuilder;
182
183 virtual void GetAABB (dgVector& p0, dgVector& p1) const;
184 virtual void Serialize (dgSerialize callback, void* const userData) const;
185 virtual void Deserialize (dgDeserialize callback, void* const userData);
186
187 protected:
188 dgAABBPolygonSoup ();
189 virtual ~dgAABBPolygonSoup ();
190
191 void Create (const dgPolygonSoupDatabaseBuilder& builder, bool optimizedBuild);
192 void CalculateAdjacendy ();
193 virtual void ForAllSectorsRayHit (const dgFastRayTest& ray, dgFloat32 maxT, dgRayIntersectCallback callback, void* const context) const;
194 virtual void ForAllSectors (const dgFastAABBInfo& obbAabb, const dgVector& boxDistanceTravel, dgFloat32 m_maxT, dgAABBIntersectCallback callback, void* const context) const;
195
196
197 DG_INLINE void* GetRootNode() const
198 {
199 return m_aabb;
200 }
201
202 DG_INLINE void* GetBackNode(const void* const root) const
203 {
204 dgNode* const node = (dgNode*) root;
205 return node->m_left.IsLeaf() ? NULL : node->m_left.GetNode(m_aabb);
206 }
207
208 DG_INLINE void* GetFrontNode(const void* const root) const
209 {
210 dgNode* const node = (dgNode*) root;
211 return node->m_right.IsLeaf() ? NULL : node->m_right.GetNode(m_aabb);
212 }
213
214 DG_INLINE void GetNodeAABB(const void* const root, dgVector& p0, dgVector& p1) const
215 {
216 const dgNode* const node = (dgNode*)root;
217 p0 = dgVector (&((dgTriplex*)m_localVertex)[node->m_indexBox0].m_x);
218 p1 = dgVector (&((dgTriplex*)m_localVertex)[node->m_indexBox1].m_x);
219 }
220 virtual dgVector ForAllSectorsSupportVectex (const dgVector& dir) const;
221
222
223
224 private:
225 dgNodeBuilder* BuildTopDown (dgNodeBuilder* const leafArray, dgInt32 firstBox, dgInt32 lastBox, dgNodeBuilder** const allocator) const;
226 dgFloat32 CalculateFaceMaxSize (const dgVector* const vertex, dgInt32 indexCount, const dgInt32* const indexArray) const;
227 // static dgIntersectStatus CalculateManifoldFaceEdgeNormals (void* const context, const dgFloat32* const polygon, dgInt32 strideInBytes, const dgInt32* const indexArray, dgInt32 indexCount);
228 static dgIntersectStatus CalculateDisjointedFaceEdgeNormals (void* const context, const dgFloat32* const polygon, dgInt32 strideInBytes, const dgInt32* const indexArray, dgInt32 indexCount, dgFloat32 hitDistance);
229 static dgIntersectStatus CalculateAllFaceEdgeNormals (void* const context, const dgFloat32* const polygon, dgInt32 strideInBytes, const dgInt32* const indexArray, dgInt32 indexCount, dgFloat32 hitDistance);
230 void ImproveNodeFitness (dgNodeBuilder* const node) const;
231
232 dgInt32 m_nodesCount;
233 dgInt32 m_indexCount;
234 dgNode* m_aabb;
235 dgInt32* m_indices;
236 };
237
238
239 #endif
240
241
dgAABBPolygonSoup::CalculateAdjacendy
void CalculateAdjacendy()
Definition: dgAABBPolygonSoup.cpp:446
dgAABBPolygonSoup::dgNode::dgLeafNodePtr::dgLeafNodePtr
DG_INLINE dgLeafNodePtr(dgUnsigned32 node)
Definition: dgAABBPolygonSoup.h:55
dgAABBPolygonSoup::dgNode
Definition: dgAABBPolygonSoup.h:36
dgFastAABBInfo::m_absDir
dgMatrix m_absDir
Definition: dgIntersections.h:372
dgFastAABBInfo::m_p0
dgVector m_p0
Definition: dgIntersections.h:373
dgAABBPolygonSoup::dgNode::dgLeafNodePtr::dgLeafNodePtr
DG_INLINE dgLeafNodePtr()
Definition: dgAABBPolygonSoup.h:50
dgPolygonSoupDatabase
Definition: dgPolygonSoupDatabase.h:40
dgAABBPolygonSoup::dgNode::dgLeafNodePtr::GetNode
DG_INLINE dgNode * GetNode(const void *const root) const
Definition: dgAABBPolygonSoup.h:85
dgAABBPolygonSoup::dgNode::BoxIntersect
DG_INLINE dgFloat32 BoxIntersect(const dgFastRayTest &ray, const dgFastRayTest &obbRay, const dgFastAABBInfo &obb, const dgTriplex *const vertexArray) const
Definition: dgAABBPolygonSoup.h:145
dgFastRayTest
Definition: dgIntersections.h:52
dgAABBPolygonSoup::dgAABBPolygonSoup
dgAABBPolygonSoup()
Definition: dgAABBPolygonSoup.cpp:237
dgAABBPolygonSoup::GetAABB
virtual void GetAABB(dgVector &p0, dgVector &p1) const
Definition: dgAABBPolygonSoup.cpp:434
dgAABBPolygonSoup::dgNodeBuilder
Definition: dgAABBPolygonSoup.cpp:35
dgRayIntersectCallback
dgFloat32(* dgRayIntersectCallback)(void *const context, const dgFloat32 *const polygon, dgInt32 strideInBytes, const dgInt32 *const indexArray, dgInt32 indexCount)
Definition: dgIntersections.h:45
dgAABBPolygonSoup::GetNodeAABB
DG_INLINE void GetNodeAABB(const void *const root, dgVector &p0, dgVector &p1) const
Definition: dgAABBPolygonSoup.h:214
userData
void *const userData
Definition: dgBroadPhase.h:35
dgVector::m_half
static dgVector m_half
Definition: dgVector.h:1041
DG_INLINE
#define DG_INLINE
Definition: dgTypes.h:178
dgAssert
#define dgAssert(x)
Definition: dgTypes.h:158
dgFloat32
float dgFloat32
Definition: dgTypes.h:233
dgInt32
int dgInt32
Definition: dgTypes.h:218
dgMax
DG_INLINE T dgMax(T A, T B)
Definition: dgTypes.h:299
dgVector
Definition: dgVector.h:639
dgAABBPolygonSoup::Serialize
virtual void Serialize(dgSerialize callback, void *const userData) const
Definition: dgAABBPolygonSoup.cpp:857
dgVector::GetScalar
DG_INLINE dgFloat32 GetScalar() const
Definition: dgVector.h:691
dgAABBPolygonSoup::dgNode::m_left
dgLeafNodePtr m_left
Definition: dgAABBPolygonSoup.h:176
dgAABBPolygonSoup::ForAllSectors
virtual void ForAllSectors(const dgFastAABBInfo &obbAabb, const dgVector &boxDistanceTravel, dgFloat32 m_maxT, dgAABBIntersectCallback callback, void *const context) const
Definition: dgAABBPolygonSoup.cpp:1104
dgAABBPolygonSoup::dgNode::dgLeafNodePtr::dgLeafNodePtr
DG_INLINE dgLeafNodePtr(dgUnsigned32 faceIndexCount, dgUnsigned32 faceIndexStart)
Definition: dgAABBPolygonSoup.h:79
dgAABBPolygonSoup::dgNode::dgNode
dgNode()
Definition: dgAABBPolygonSoup.h:96
dgPolygonSoupDatabaseBuilder
Definition: dgPolygonSoupBuilder.h:46
dgMatrix::RotateVector
dgVector RotateVector(const dgVector &v) const
Definition: dgMatrix.h:200
dgFastRayTest::BoxIntersect
DG_INLINE dgFloat32 BoxIntersect(const dgVector &minBox, const dgVector &maxBox) const
Definition: dgIntersections.h:130
dgPolygonSoupDatabase.h
dgAABBPolygonSoup::dgNode::m_binary
Definition: dgAABBPolygonSoup.h:41
dgObb::m_size
dgVector m_size
Definition: dgObb.h:74
dgSerialize
void(dgApi * dgSerialize)(void *const userData, const void *const buffer, size_t size)
Definition: dgTypes.h:280
dgAABBPolygonSoup::dgNode::dgLeafNodePtr::GetIndex
DG_INLINE dgUnsigned32 GetIndex() const
Definition: dgAABBPolygonSoup.h:72
dgAABBPolygonSoup::dgNode::dgLeafNodePtr::m_node
dgUnsigned32 m_node
Definition: dgAABBPolygonSoup.h:91
dgMatrix::UntransformVector
dgVector UntransformVector(const dgVector &v) const
Definition: dgMatrix.h:233
dgAABBPolygonSoup::dgNode::dgNodeType
dgNodeType
Definition: dgAABBPolygonSoup.h:39
dgAABBPolygonSoup::ForAllSectorsRayHit
virtual void ForAllSectorsRayHit(const dgFastRayTest &ray, dgFloat32 maxT, dgRayIntersectCallback callback, void *const context) const
Definition: dgAABBPolygonSoup.cpp:1022
dgStdafx.h
dgDeserialize
void(dgApi * dgDeserialize)(void *const userData, void *buffer, size_t size)
Definition: dgTypes.h:279
dgPolygonSoupDatabase::m_localVertex
dgFloat32 * m_localVertex
Definition: dgPolygonSoupDatabase.h:61
dgAABBIntersectCallback
dgIntersectStatus(* dgAABBIntersectCallback)(void *const context, const dgFloat32 *const polygon, dgInt32 strideInBytes, const dgInt32 *const indexArray, dgInt32 indexCount, dgFloat32 hitDistance)
Definition: dgIntersections.h:41
dgFastAABBInfo
Definition: dgIntersections.h:245
dgAABBPolygonSoup::GetFrontNode
DG_INLINE void * GetFrontNode(const void *const root) const
Definition: dgAABBPolygonSoup.h:208
DG_INDEX_COUNT_BITS
#define DG_INDEX_COUNT_BITS
Definition: dgAABBPolygonSoup.h:47
dgAABBPolygonSoup::dgNode::dgLeafNodePtr::IsLeaf
DG_INLINE dgUnsigned32 IsLeaf() const
Definition: dgAABBPolygonSoup.h:61
dgAABBPolygonSoup::dgNode::m_leaf
Definition: dgAABBPolygonSoup.h:42
dgUnsigned32
unsigned dgUnsigned32
Definition: dgTypes.h:219
dgAABBPolygonSoup::GetRootNode
DG_INLINE void * GetRootNode() const
Definition: dgAABBPolygonSoup.h:197
dgFastAABBInfo::m_p1
dgVector m_p1
Definition: dgIntersections.h:374
dgVector::CompProduct4
DG_INLINE dgVector CompProduct4(const dgVector &A) const
Definition: dgVector.h:851
dgAABBPolygonSoup::~dgAABBPolygonSoup
virtual ~dgAABBPolygonSoup()
Definition: dgAABBPolygonSoup.cpp:246
dgAABBPolygonSoup::dgNode::m_indexBox1
dgInt32 m_indexBox1
Definition: dgAABBPolygonSoup.h:175
dgAABBPolygonSoup::Deserialize
virtual void Deserialize(dgDeserialize callback, void *const userData)
Definition: dgAABBPolygonSoup.cpp:870
dgAABBPolygonSoup::dgSpliteInfo
Definition: dgAABBPolygonSoup.cpp:139
dgVector::Abs
DG_INLINE dgVector Abs() const
Definition: dgVector.h:862
dgAABBPolygonSoup::dgNode::dgLeafNodePtr::GetCount
DG_INLINE dgUnsigned32 GetCount() const
Definition: dgAABBPolygonSoup.h:66
dgAABBPolygonSoup::ForAllSectorsSupportVectex
virtual dgVector ForAllSectorsSupportVectex(const dgVector &dir) const
Definition: dgAABBPolygonSoup.cpp:894
dgIntersectStatus
dgIntersectStatus
Definition: dgIntersections.h:35
dgAABBPolygonSoup::dgNode::m_indexBox0
dgInt32 m_indexBox0
Definition: dgAABBPolygonSoup.h:174
dgAABBPolygonSoup::GetBackNode
DG_INLINE void * GetBackNode(const void *const root) const
Definition: dgAABBPolygonSoup.h:202
dgAABBPolygonSoup::dgNode::dgLeafNodePtr
Definition: dgAABBPolygonSoup.h:45
dgAABBPolygonSoup::Create
void Create(const dgPolygonSoupDatabaseBuilder &builder, bool optimizedBuild)
Definition: dgAABBPolygonSoup.cpp:648
dgVector::GetMin
dgVector GetMin(const dgVector &data) const
Definition: dgVector.h:874
dgAABBPolygonSoup
Definition: dgAABBPolygonSoup.h:33
dgAABBPolygonSoup::dgNode::m_right
dgLeafNodePtr m_right
Definition: dgAABBPolygonSoup.h:177
dgAABBPolygonSoup::dgNode::BoxPenetration
DG_INLINE dgFloat32 BoxPenetration(const dgFastAABBInfo &obb, const dgTriplex *const vertexArray) const
Definition: dgAABBPolygonSoup.h:111
dgIntersections.h
dgTriplex
Definition: dgTypes.h:237
dgVector::ShiftTripleRight
DG_INLINE dgVector ShiftTripleRight() const
Definition: dgVector.h:976
dgAABBPolygonSoup::dgNode::RayDistance
DG_INLINE dgFloat32 RayDistance(const dgFastRayTest &ray, const dgTriplex *const vertexArray) const
Definition: dgAABBPolygonSoup.h:104