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

My Project

dgPolyhedra.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 __dgPolyhedra__
23 #define __dgPolyhedra__
24
25 #include "dgStdafx.h"
26 #include "dgList.h"
27 #include "dgTree.h"
28 #include "dgHeap.h"
29 #include "dgDebug.h"
30
31
32
33
34 class dgEdge;
35 class dgPlane;
36 class dgObb;
37 class dgMatrix;
38 class dgPolyhedra;
39 class dgVertexCollapseVertexMetric;
40
41 typedef dgInt64 dgEdgeKey;
42
43
44 DG_MSC_VECTOR_ALIGMENT
45 class dgEdge
46 {
47 public:
48 dgEdge ();
49 dgEdge (dgInt32 vertex, dgInt32 face, dgUnsigned64 userdata = 0);
50 ~dgEdge ();
51
52 dgInt32 m_incidentVertex;
53 dgInt32 m_incidentFace;
54 dgUnsigned64 m_userData;
55 dgEdge* m_next;
56 dgEdge* m_prev;
57 dgEdge* m_twin;
58 dgInt32 m_mark;
59 } DG_GCC_VECTOR_ALIGMENT;
60
61
62 class dgPolyhedra: public dgTree <dgEdge, dgEdgeKey>
63 {
64 public:
65 class dgPairKey
66 {
67 public:
68 dgPairKey ();
69 dgPairKey (dgInt64 val);
70 dgPairKey (dgInt32 v0, dgInt32 v1);
71 dgInt64 GetVal () const;
72 dgInt32 GetLowKey () const;
73 dgInt32 GetHighKey () const;
74
75 private:
76 dgUnsigned64 m_key;
77 };
78
79 dgPolyhedra (dgMemoryAllocator* const allocator);
80 dgPolyhedra (const dgPolyhedra &polyhedra);
81 virtual ~dgPolyhedra();
82
83 virtual void BeginFace();
84 dgEdge* AddFace (dgInt32 v0, dgInt32 v1, dgInt32 v2);
85 dgEdge* AddFace (dgInt32 count, const dgInt32* const index);
86 dgEdge* AddFace (dgInt32 count, const dgInt32* const index, const dgInt64* const userdata);
87 virtual void EndFace ();
88 virtual void DeleteFace(dgEdge* const edge);
89
90 dgInt32 GetFaceCount() const;
91 dgInt32 GetEdgeCount() const;
92 dgInt32 GetLastVertexIndex() const;
93
94 dgInt32 IncLRU() const;
95 void SetLRU(dgInt32 lru) const;
96
97 dgEdge* FindEdge (dgInt32 v0, dgInt32 v1) const;
98 dgTreeNode* FindEdgeNode (dgInt32 v0, dgInt32 v1) const;
99
100 dgEdge* AddHalfEdge (dgInt32 v0, dgInt32 v1);
101 void DeleteEdge (dgEdge* const edge);
102 void DeleteEdge (dgInt32 v0, dgInt32 v1);
103
104 dgEdge* ConnectVertex (dgEdge* const e0, dgEdge* const e1);
105
106 bool FlipEdge (dgEdge* const edge);
107 dgEdge* SpliteEdge (dgInt32 newIndex, dgEdge* const edge);
108 dgBigVector FaceNormal (const dgEdge* const face, const dgFloat64* const vertex, dgInt32 strideInBytes) const;
109
110 void BeginConectedSurface() const;
111 bool GetConectedSurface (dgPolyhedra &polyhedra) const;
112 void EndConectedSurface() const;
113
114 dgObb CalculateSphere (const dgFloat64* const vertex, dgInt32 strideInBytes, const dgMatrix* const basis = NULL) const;
115 void ChangeEdgeIncidentVertex (dgEdge* const edge, dgInt32 newIndex);
116 void DeleteDegenerateFaces (const dgFloat64* const pool, dgInt32 dstStrideInBytes, dgFloat64 minArea);
117
118 bool Optimize (const dgFloat64* const pool, dgInt32 strideInBytes, dgReportProgress normalizedProgress, void* const reportProgressUserData, dgFloat64 tol, dgInt32 maxFaceCount = 1<<28);
119 void Triangulate (const dgFloat64* const vertex, dgInt32 strideInBytes, dgPolyhedra* const leftOversOut);
120 void ConvexPartition (const dgFloat64* const vertex, dgInt32 strideInBytes, dgPolyhedra* const leftOversOut);
121 dgEdge* CollapseEdge(dgEdge* const edge);
122 void PolygonizeFace (dgEdge* face, const dgFloat64* const pool, dgInt32 stride);
123
124 private:
125 void RefineTriangulation (const dgFloat64* const vertex, dgInt32 stride);
126 void RefineTriangulation (const dgFloat64* const vertex, dgInt32 stride, dgBigVector* const normal, dgInt32 perimeterCount, dgEdge** const perimeter);
127 void OptimizeTriangulation (const dgFloat64* const vertex, dgInt32 strideInBytes);
128 void MarkAdjacentCoplanarFaces (dgPolyhedra& polyhedraOut, dgEdge* const face, const dgFloat64* const pool, dgInt32 strideInBytes);
129 dgEdge* FindEarTip (dgEdge* const face, const dgFloat64* const pool, dgInt32 stride, dgDownHeap<dgEdge*, dgFloat64>& heap, const dgBigVector &normal) const;
130 dgEdge* TriangulateFace (dgEdge* const face, const dgFloat64* const pool, dgInt32 stride, dgDownHeap<dgEdge*, dgFloat64>& heap, dgBigVector* const faceNormalOut);
131
132
133 void RemoveHalfEdge (dgEdge* const edge);
134 dgEdge* OptimizeCollapseEdge (dgEdge* const edge);
135 bool IsOkToCollapse (const dgBigVector* const pool, dgEdge* const edge) const;
136 dgFloat64 EdgePenalty (const dgBigVector* const pool, dgEdge* const edge, dgFloat64 dist) const;
137 dgBigPlane EdgePlane (dgInt32 i0, dgInt32 i1, dgInt32 i2, const dgBigVector* const pool) const;
138 void CalculateAllMetrics (dgVertexCollapseVertexMetric* const table, const dgBigVector* const pool) const;
139 void CalculateVertexMetrics (dgVertexCollapseVertexMetric* const table, const dgBigVector* const pool, dgEdge* const edge) const;
140
141
142 mutable dgInt32 m_baseMark;
143 mutable dgInt32 m_edgeMark;
144 mutable dgInt32 m_faceSecuence;
145
146 friend class dgPolyhedraDescriptor;
147
148 };
149
150
151
152 DG_INLINE dgEdge::dgEdge ()
153 {
154 }
155
156 DG_INLINE dgEdge::dgEdge (dgInt32 vertex, dgInt32 face, dgUnsigned64 userdata)
157 :m_incidentVertex(vertex)
158 ,m_incidentFace(face)
159 ,m_userData(userdata)
160 ,m_next(NULL)
161 ,m_prev(NULL)
162 ,m_twin(NULL)
163 ,m_mark(0)
164 {
165 }
166
167 DG_INLINE dgEdge::~dgEdge ()
168 {
169 }
170
171 DG_INLINE dgPolyhedra::dgPairKey::dgPairKey ()
172 {
173 }
174
175 DG_INLINE dgPolyhedra::dgPairKey::dgPairKey (dgInt64 val)
176 :m_key(dgUnsigned64 (val))
177 {
178 }
179
180 DG_INLINE dgPolyhedra::dgPairKey::dgPairKey (dgInt32 v0, dgInt32 v1)
181 :m_key (dgUnsigned64 ((dgInt64 (v0) << 32) | v1))
182 {
183 }
184
185 DG_INLINE dgInt64 dgPolyhedra::dgPairKey::GetVal () const
186 {
187 return dgInt64 (m_key);
188 }
189
190 DG_INLINE dgInt32 dgPolyhedra::dgPairKey::GetLowKey () const
191 {
192 return dgInt32 (m_key>>32);
193 }
194
195 DG_INLINE dgInt32 dgPolyhedra::dgPairKey::GetHighKey () const
196 {
197 return dgInt32 (m_key & 0xffffffff);
198 }
199
200 DG_INLINE void dgPolyhedra::BeginFace ()
201 {
202 }
203
204 DG_INLINE dgEdge* dgPolyhedra::AddFace (dgInt32 count, const dgInt32* const index)
205 {
206 return AddFace (count, index, NULL);
207 }
208
209 DG_INLINE dgEdge* dgPolyhedra::AddFace (dgInt32 v0, dgInt32 v1, dgInt32 v2)
210 {
211 dgInt32 vertex[3];
212
213 vertex [0] = v0;
214 vertex [1] = v1;
215 vertex [2] = v2;
216 return AddFace (3, vertex, NULL);
217 }
218
219 DG_INLINE dgInt32 dgPolyhedra::GetEdgeCount() const
220 {
221 #ifdef _DEBUG
222 dgInt32 edgeCount = 0;
223 Iterator iter(*this);
224 for (iter.Begin(); iter; iter ++) {
225 edgeCount ++;
226 }
227 dgAssert (edgeCount == GetCount());;
228 #endif
229 return GetCount();
230 }
231
232 DG_INLINE dgInt32 dgPolyhedra::GetLastVertexIndex() const
233 {
234 dgInt32 maxVertexIndex = -1;
235 Iterator iter(*this);
236 for (iter.Begin(); iter; iter ++) {
237 const dgEdge* const edge = &(*iter);
238 if (edge->m_incidentVertex > maxVertexIndex) {
239 maxVertexIndex = edge->m_incidentVertex;
240 }
241 }
242 return maxVertexIndex + 1;
243 }
244
245
246 DG_INLINE dgInt32 dgPolyhedra::IncLRU() const
247 {
248 m_edgeMark ++;
249 dgAssert (m_edgeMark < 0x7fffffff);
250 return m_edgeMark;
251 }
252
253 DG_INLINE void dgPolyhedra::SetLRU(dgInt32 lru) const
254 {
255 if (lru > m_edgeMark) {
256 m_edgeMark = lru;
257 }
258 }
259
260 DG_INLINE void dgPolyhedra::BeginConectedSurface() const
261 {
262 m_baseMark = IncLRU();
263 }
264
265 DG_INLINE void dgPolyhedra::EndConectedSurface() const
266 {
267 }
268
269
270 DG_INLINE dgPolyhedra::dgTreeNode* dgPolyhedra::FindEdgeNode (dgInt32 i0, dgInt32 i1) const
271 {
272 dgPairKey key (i0, i1);
273 return Find (key.GetVal());
274 }
275
276
277 DG_INLINE dgEdge *dgPolyhedra::FindEdge (dgInt32 i0, dgInt32 i1) const
278 {
279 // dgTreeNode *node;
280 // dgPairKey key (i0, i1);
281 // node = Find (key.GetVal());
282 // return node ? &node->GetInfo() : NULL;
283 dgTreeNode* const node = FindEdgeNode (i0, i1);
284 return node ? &node->GetInfo() : NULL;
285 }
286
287 DG_INLINE void dgPolyhedra::DeleteEdge (dgInt32 v0, dgInt32 v1)
288 {
289 dgPairKey pairKey (v0, v1);
290 dgTreeNode* const node = Find(pairKey.GetVal());
291 dgEdge* const edge = node ? &node->GetInfo() : NULL;
292 if (!edge) {
293 return;
294 }
295 DeleteEdge (edge);
296 }
297
298
299 #endif
300
dgTree< dgEdge, dgEdgeKey >::Find
dgTreeNode * Find(dgEdgeKey key) const
Definition: dgTree.h:403
dgPlane
Definition: dgPlane.h:29
dgPolyhedra::FindEdge
dgEdge * FindEdge(dgInt32 v0, dgInt32 v1) const
Definition: dgPolyhedra.h:277
dgInt64
long long dgInt64
Definition: dgTypes.h:222
dgUnsigned64
unsigned long long dgUnsigned64
Definition: dgTypes.h:223
dgPolyhedra::SetLRU
void SetLRU(dgInt32 lru) const
Definition: dgPolyhedra.h:253
dgDebug.h
dgHeap.h
dgTree.h
dgEdge::~dgEdge
~dgEdge()
Definition: dgPolyhedra.h:167
dgObb
Definition: dgObb.h:35
dgTree< dgEdge, dgEdgeKey >::dgTreeNode
friend class dgTreeNode
Definition: dgTree.h:291
dgEdge::m_userData
dgUnsigned64 m_userData
Definition: dgPolyhedra.h:54
DG_INLINE
#define DG_INLINE
Definition: dgTypes.h:178
dgAssert
#define dgAssert(x)
Definition: dgTypes.h:158
dgPolyhedra::AddFace
dgEdge * AddFace(dgInt32 v0, dgInt32 v1, dgInt32 v2)
Definition: dgPolyhedra.h:209
dgInt32
int dgInt32
Definition: dgTypes.h:218
dgPolyhedra::dgPairKey::GetLowKey
dgInt32 GetLowKey() const
Definition: dgPolyhedra.h:190
dgEdge
Definition: dgPolyhedra.h:45
dgFloat64
double dgFloat64
Definition: dgTypes.h:224
dgPolyhedra::dgPairKey::GetHighKey
dgInt32 GetHighKey() const
Definition: dgPolyhedra.h:195
dgEdge::m_prev
dgEdge * m_prev
Definition: dgPolyhedra.h:56
dgTree
Definition: dgTree.h:88
DG_MSC_VECTOR_ALIGMENT
#define DG_MSC_VECTOR_ALIGMENT
Definition: dgTypes.h:194
dgPolyhedra::BeginFace
virtual void BeginFace()
Definition: dgPolyhedra.h:200
dgVertexCollapseVertexMetric
Definition: dgPolyhedra.cpp:82
dgPolyhedra
Definition: dgPolyhedra.h:62
dgStdafx.h
dgDownHeap
Definition: dgHeap.h:74
dgList.h
dgPolyhedra::DeleteEdge
void DeleteEdge(dgEdge *const edge)
Definition: dgPolyhedra.cpp:450
dgPolyhedra::dgPairKey
Definition: dgPolyhedra.h:65
dgEdge::dgEdge
dgEdge()
Definition: dgPolyhedra.h:152
dgPolyhedra::GetLastVertexIndex
dgInt32 GetLastVertexIndex() const
Definition: dgPolyhedra.h:232
dgEdge::m_incidentFace
dgInt32 m_incidentFace
Definition: dgPolyhedra.h:53
iter
int iter
Definition: benchtest1.c:63
dgPolyhedra::FindEdgeNode
dgTreeNode * FindEdgeNode(dgInt32 v0, dgInt32 v1) const
Definition: dgPolyhedra.h:270
dgReportProgress
bool(dgApi * dgReportProgress)(dgFloat32 progressNormalzedPercent, void *const userData)
Definition: dgTypes.h:281
dgBigPlane
Definition: dgPlane.h:45
dgPolyhedra::IncLRU
dgInt32 IncLRU() const
Definition: dgPolyhedra.h:246
dgEdgeKey
dgInt64 dgEdgeKey
Definition: dgPolyhedra.h:39
dgEdge::m_next
dgEdge * m_next
Definition: dgPolyhedra.h:55
DG_GCC_VECTOR_ALIGMENT
DG_MSC_VECTOR_ALIGMENT class dgEdge DG_GCC_VECTOR_ALIGMENT
dgMatrix
Definition: dgMatrix.h:40
dgMemoryAllocator
Definition: dgMemory.h:73
dgEdge::m_twin
dgEdge * m_twin
Definition: dgPolyhedra.h:57
dgPolyhedra::dgPairKey::dgPairKey
dgPairKey()
Definition: dgPolyhedra.h:171
dgEdge::m_incidentVertex
dgInt32 m_incidentVertex
Definition: dgPolyhedra.h:52
dgEdge::m_mark
dgInt32 m_mark
Definition: dgPolyhedra.h:58
dgPolyhedra::dgPairKey::GetVal
dgInt64 GetVal() const
Definition: dgPolyhedra.h:185
dgBigVector
Definition: dgVector.h:207
dgTree< dgEdge, dgEdgeKey >::GetCount
dgInt32 GetCount() const
Definition: dgTree.h:379
dgPolyhedra::GetEdgeCount
dgInt32 GetEdgeCount() const
Definition: dgPolyhedra.h:219
dgPolyhedra::BeginConectedSurface
void BeginConectedSurface() const
Definition: dgPolyhedra.h:260
dgPolyhedra::EndConectedSurface
void EndConectedSurface() const
Definition: dgPolyhedra.h:265