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

My Project

dgConvexHull4d.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_CONVEXHULL_4D__
23 #define __DG_CONVEXHULL_4D__
24
25 #include "dgStdafx.h"
26 #include "dgList.h"
27 #include "dgArray.h"
28 #include "dgPlane.h"
29 #include "dgVector.h"
30 #include "dgMatrix.h"
31 #include "dgQuaternion.h"
32
33 class dgMemoryAllocator;
34 class dgAABBPointTree4d;
35
36 class dgHullVector: public dgBigVector
37 {
38 public:
39 void operator = (const dgBigVector& a)
40 {
41 m_x = a.m_x;
42 m_y = a.m_y;
43 m_z = a.m_z;
44 m_w = a.m_w;
45 m_index = 0;
46 m_mark = 0;
47 }
48
49 dgInt32 m_index;
50 dgInt32 m_mark;
51 };
52
53
54 class dgConvexHull4dTetraherum
55 {
56 public:
57 class dgTetrahedrumFace
58 {
59 public:
60 dgInt32 m_index[4];
61 dgList<dgConvexHull4dTetraherum>::dgListNode* m_twin;
62 };
63
64
65 class dgTetrahedrumPlane: public dgBigVector
66 {
67 public:
68 dgTetrahedrumPlane (const dgBigVector& p0, const dgBigVector& p1, const dgBigVector& p2, const dgBigVector& p3);
69 dgFloat64 Evalue (const dgBigVector& point) const;
70 dgFloat64 m_dist;
71 };
72
73 dgConvexHull4dTetraherum();
74 dgTetrahedrumPlane GetPlaneEquation (const dgHullVector* const points) const;
75 dgFloat64 Evalue (const dgHullVector* const pointArray, const dgBigVector& point) const;
76
77 dgBigVector CircumSphereCenter (const dgHullVector* const pointArray) const;
78
79 dgInt32 GetMark() const { return m_mark; }
80 void SetMark(dgInt32 mark) { m_mark = mark; }
81
82 private:
83 void Init (const dgHullVector* const points, dgInt32 v0, dgInt32 v1, dgInt32 v2, dgInt32 v3);
84
85 public:
86 dgTetrahedrumFace m_faces[4];
87 dgInt32 m_mark;
88 dgInt32 m_uniqueID;
89
90 #ifdef _DEBUG
91 dgInt32 m_debugID;
92 #endif
93 friend class dgConvexHull4d;
94 friend class dgDelaunayTetrahedralization;
95 };
96
97
98 class dgConvexHull4d: public dgList<dgConvexHull4dTetraherum>
99 {
100 public:
101 dgConvexHull4d(dgMemoryAllocator* const allocator, const dgBigVector* const vertexCloud, dgInt32 count, dgFloat32 distTol);
102 virtual ~dgConvexHull4d();
103
104 dgInt32 GetVertexCount() const;
105 dgInt32 GetVertexIndex(dgInt32 i) const;
106 const dgBigVector& GetVertex(dgInt32 i) const;
107
108 const dgHullVector* GetHullVertexArray() const;
109
110 dgInt32 IncMark ();
111 void Save (const char* const filename) const;
112
113 protected:
114 dgConvexHull4d(dgMemoryAllocator* const allocator);
115
116 void BuildHull (dgMemoryAllocator* const allocator, const dgBigVector* const vertexCloud, dgInt32 count, dgFloat64 distTol);
117
118 virtual dgInt32 AddVertex (const dgBigVector& vertex);
119 virtual dgInt32 InitVertexArray(dgHullVector* const points, const dgBigVector* const vertexCloud, dgInt32 count, void* const memoryPool, dgInt32 maxMemSize);
120 virtual dgListNode* AddFace (dgInt32 i0, dgInt32 i1, dgInt32 i2, dgInt32 i3);
121 virtual void DeleteFace (dgListNode* const node);
122
123 dgListNode* FindFacingNode(const dgBigVector& vertex);
124 dgInt32 BuildNormalList (dgBigVector* const normalArray) const;
125 void InsertNewVertex(dgInt32 vertexIndex, dgListNode* const frontFace, dgList<dgListNode*>& deletedFaces, dgList<dgListNode*>& newFaces);
126 dgInt32 SupportVertex (dgAABBPointTree4d** const tree, const dgHullVector* const points, const dgBigVector& dir) const;
127 void TessellateTriangle (dgInt32 level, const dgVector& p0, const dgVector& p1, const dgVector& p2, dgInt32& count, dgBigVector* const ouput, dgInt32& start) const;
128 void CalculateConvexHull (dgAABBPointTree4d* vertexTree, dgHullVector* const points, dgInt32 count, dgFloat64 distTol);
129 void LinkSibling (dgListNode* node0, dgListNode* node1) const;
130 bool Sanity() const;
131 dgAABBPointTree4d* BuildTree (dgAABBPointTree4d* const parent, dgHullVector* const points, dgInt32 count, dgInt32 baseIndex, dgInt8** const memoryPool, dgInt32& maxMemSize) const;
132
133 static dgInt32 ConvexCompareVertex(const dgHullVector* const A, const dgHullVector* const B, void* const context);
134
135 dgFloat64 RoundToFloat (dgFloat64 val) const;
136 dgInt32 m_mark;
137 dgInt32 m_count;
138 dgFloat64 m_diag;
139 dgArray<dgHullVector> m_points;
140 };
141
142
143 inline dgInt32 dgConvexHull4d::IncMark ()
144 {
145 m_mark ++;
146 return m_mark;
147 }
148
149 inline dgInt32 dgConvexHull4d::GetVertexCount() const
150 {
151 return m_count;
152 }
153
154 inline dgInt32 dgConvexHull4d::GetVertexIndex(dgInt32 index) const
155 {
156 dgAssert (index >= 0);
157 dgAssert (index < m_count);
158 return m_points[index].m_index;
159 }
160
161
162 inline const dgBigVector& dgConvexHull4d::GetVertex(dgInt32 index) const
163 {
164 dgAssert (index >= 0);
165 dgAssert (index < m_count);
166 // return dgVector (dgFloat32 (m_points[index].m_x), dgFloat32 (m_points[index].m_y), dgFloat32 (m_points[index].m_z), dgFloat32 (m_points[index].m_w));
167 return m_points[index];
168 }
169
170 inline const dgHullVector* dgConvexHull4d::GetHullVertexArray() const
171 {
172 return &m_points[0];
173 }
174
175 #endif
dgHullVector::m_mark
dgInt32 m_mark
Definition: dgConvexHull4d.h:50
dgConvexHull4d::GetVertex
const dgBigVector & GetVertex(dgInt32 i) const
Definition: dgConvexHull4d.h:162
dgAABBPointTree4d
Definition: dgConvexHull4d.cpp:35
dgConvexHull4d::m_points
dgArray< dgHullVector > m_points
Definition: dgConvexHull4d.h:139
dgConvexHull4dTetraherum::dgTetrahedrumFace::m_twin
dgList< dgConvexHull4dTetraherum >::dgListNode * m_twin
Definition: dgConvexHull4d.h:61
dgConvexHull4d::GetHullVertexArray
const dgHullVector * GetHullVertexArray() const
Definition: dgConvexHull4d.h:170
dgConvexHull4dTetraherum::dgTetrahedrumPlane
Definition: dgConvexHull4d.h:65
dgAssert
#define dgAssert(x)
Definition: dgTypes.h:158
dgConvexHull4d::m_mark
dgInt32 m_mark
Definition: dgConvexHull4d.h:136
dgFloat32
float dgFloat32
Definition: dgTypes.h:233
dgInt32
int dgInt32
Definition: dgTypes.h:218
dgConvexHull4d::m_count
dgInt32 m_count
Definition: dgConvexHull4d.h:137
dgVector
Definition: dgVector.h:639
dgTemplateVector< dgFloat64 >::m_z
dgFloat64 m_z
Definition: dgVector.h:195
dgConvexHull4dTetraherum::dgTetrahedrumPlane::m_dist
dgFloat64 m_dist
Definition: dgConvexHull4d.h:70
dgConvexHull4dTetraherum::m_uniqueID
dgInt32 m_uniqueID
Definition: dgConvexHull4d.h:88
dgConvexHull4dTetraherum
Definition: dgConvexHull4d.h:54
dgTemplateVector< dgFloat64 >::m_y
dgFloat64 m_y
Definition: dgVector.h:194
dgHullVector::operator=
void operator=(const dgBigVector &a)
Definition: dgConvexHull4d.h:39
dgConvexHull4d::IncMark
dgInt32 IncMark()
Definition: dgConvexHull4d.h:143
dgFloat64
double dgFloat64
Definition: dgTypes.h:224
dgMatrix.h
dgList
Definition: dgList.h:33
dgVector.h
dgConvexHull4d::GetVertexIndex
dgInt32 GetVertexIndex(dgInt32 i) const
Definition: dgConvexHull4d.h:154
dgConvexHull4dTetraherum::m_mark
dgInt32 m_mark
Definition: dgConvexHull4d.h:87
dgStdafx.h
dgInt8
char dgInt8
Definition: dgTypes.h:212
dgList.h
dgArray< dgHullVector >
dgConvexHull4dTetraherum::GetMark
dgInt32 GetMark() const
Definition: dgConvexHull4d.h:79
dgConvexHull4d
Definition: dgConvexHull4d.h:98
dgConvexHull4d::GetVertexCount
dgInt32 GetVertexCount() const
Definition: dgConvexHull4d.h:149
dgQuaternion.h
dgDelaunayTetrahedralization
Definition: dgDelaunayTetrahedralization.h:28
dgMemoryAllocator
Definition: dgMemory.h:73
dgConvexHull4d::m_diag
dgFloat64 m_diag
Definition: dgConvexHull4d.h:138
dgPlane.h
dgConvexHull4dTetraherum::SetMark
void SetMark(dgInt32 mark)
Definition: dgConvexHull4d.h:80
dgHullVector
Definition: dgConvexHull4d.h:36
dgConvexHull4dTetraherum::dgTetrahedrumFace
Definition: dgConvexHull4d.h:57
dgTemplateVector< dgFloat64 >::m_w
dgFloat64 m_w
Definition: dgVector.h:196
dgHullVector::m_index
dgInt32 m_index
Definition: dgConvexHull4d.h:49
dgBigVector
Definition: dgVector.h:207
dgArray.h
dgTemplateVector< dgFloat64 >::m_x
dgFloat64 m_x
Definition: dgVector.h:193