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

My Project

dgConvexHull3d.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_3D__
23 #define __DG_CONVEXHULL_3D__
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 dgAABBPointTree3d;
35
36 class dgConvexHull3DFace
37 {
38 public:
39 dgConvexHull3DFace();
40
41
42 void SetMark(dgInt32 mark) {m_mark = mark;}
43 dgInt32 GetMark() const {return m_mark;}
44 dgList<dgConvexHull3DFace>::dgListNode* GetTwin(dgInt32 index) const { return m_twin[index];}
45
46 private:
47 dgFloat64 Evalue (const dgBigVector* const pointArray, const dgBigVector& point) const;
48 dgBigPlane GetPlaneEquation (const dgBigVector* const pointArray) const;
49
50 public:
51 dgInt32 m_index[3];
52 private:
53 dgInt32 m_mark;
54 dgList<dgConvexHull3DFace>::dgListNode* m_twin[3];
55 friend class dgConvexHull3d;
56 };
57
58 class dgHullVertex;
59
60 class dgConvexHull3d: public dgList<dgConvexHull3DFace>
61 {
62 public:
63 dgConvexHull3d(const dgConvexHull3d& source);
64 dgConvexHull3d(dgMemoryAllocator* const allocator, const dgFloat64* const vertexCloud, dgInt32 strideInBytes, dgInt32 count, dgFloat64 distTol, dgInt32 maxVertexCount = 0x7fffffff);
65 virtual ~dgConvexHull3d();
66
67 dgInt32 GetVertexCount() const;
68 const dgBigVector* GetVertexPool() const;
69 const dgBigVector& GetVertex(dgInt32 i) const;
70
71 dgFloat64 GetDiagonal() const;
72 void GetAABB (dgBigVector& boxP0, dgBigVector& boxP1) const;
73 dgFloat64 RayCast (const dgBigVector& localP0, const dgBigVector& localP1) const;
74 void CalculateVolumeAndSurfaceArea (dgFloat64& volume, dgFloat64& surcafeArea) const;
75
76 protected:
77 dgConvexHull3d(dgMemoryAllocator* const allocator);
78 void BuildHull (const dgFloat64* const vertexCloud, dgInt32 strideInBytes, dgInt32 count, dgFloat64 distTol, dgInt32 maxVertexCount);
79
80 virtual dgListNode* AddFace (dgInt32 i0, dgInt32 i1, dgInt32 i2);
81 virtual void DeleteFace (dgListNode* const node) ;
82 virtual dgInt32 InitVertexArray(dgHullVertex* const points, const dgFloat64* const vertexCloud, dgInt32 strideInBytes, dgInt32 count, void* const memoryPool, dgInt32 maxMemSize);
83
84 void CalculateConvexHull (dgAABBPointTree3d* vertexTree, dgHullVertex* const points, dgInt32 count, dgFloat64 distTol, dgInt32 maxVertexCount);
85 dgInt32 BuildNormalList (dgBigVector* const normalArray) const;
86 dgInt32 SupportVertex (dgAABBPointTree3d** const tree, const dgHullVertex* const points, const dgBigVector& dir) const;
87 dgFloat64 TetrahedrumVolume (const dgBigVector& p0, const dgBigVector& p1, const dgBigVector& p2, const dgBigVector& p3) const;
88 void TessellateTriangle (dgInt32 level, const dgVector& p0, const dgVector& p1, const dgVector& p2, dgInt32& count, dgBigVector* const ouput, dgInt32& start) const;
89
90 dgAABBPointTree3d* BuildTree (dgAABBPointTree3d* const parent, dgHullVertex* const points, dgInt32 count, dgInt32 baseIndex, dgInt8** const memoryPool, dgInt32& maxMemSize) const;
91 static dgInt32 ConvexCompareVertex(const dgHullVertex* const A, const dgHullVertex* const B, void* const context);
92 bool Sanity() const;
93
94 dgInt32 m_count;
95 dgFloat64 m_diag;
96 dgBigVector m_aabbP0;
97 dgBigVector m_aabbP1;
98 dgArray<dgBigVector> m_points;
99 };
100
101
102 inline dgInt32 dgConvexHull3d::GetVertexCount() const
103 {
104 return m_count;
105 }
106
107 inline const dgBigVector* dgConvexHull3d::GetVertexPool() const
108 {
109 return &m_points[0];
110 }
111
112 inline const dgBigVector& dgConvexHull3d::GetVertex(dgInt32 index) const
113 {
114 return m_points[index];
115 }
116
117 inline dgFloat64 dgConvexHull3d::GetDiagonal() const
118 {
119 return m_diag;
120 }
121
122
123 inline void dgConvexHull3d::GetAABB (dgBigVector& boxP0, dgBigVector& boxP1) const
124 {
125 boxP0 = m_aabbP0;
126 boxP1 = m_aabbP1;
127 }
128
129 #endif
dgConvexHull3DFace
Definition: dgConvexHull3d.h:36
dgConvexHull3DFace::SetMark
void SetMark(dgInt32 mark)
Definition: dgConvexHull3d.h:42
dgConvexHull3d::m_points
dgArray< dgBigVector > m_points
Definition: dgConvexHull3d.h:98
dgConvexHull3d::GetAABB
void GetAABB(dgBigVector &boxP0, dgBigVector &boxP1) const
Definition: dgConvexHull3d.h:123
dgInt32
int dgInt32
Definition: dgTypes.h:218
dgConvexHull3DFace::GetTwin
dgList< dgConvexHull3DFace >::dgListNode * GetTwin(dgInt32 index) const
Definition: dgConvexHull3d.h:44
dgVector
Definition: dgVector.h:639
dgConvexHull3d
Definition: dgConvexHull3d.h:60
dgConvexHull3DFace::dgConvexHull3d
friend class dgConvexHull3d
Definition: dgConvexHull3d.h:55
dgConvexHull3d::GetVertexPool
const dgBigVector * GetVertexPool() const
Definition: dgConvexHull3d.h:107
dgConvexHull3d::GetDiagonal
dgFloat64 GetDiagonal() const
Definition: dgConvexHull3d.h:117
dgFloat64
double dgFloat64
Definition: dgTypes.h:224
dgMatrix.h
dgList
Definition: dgList.h:33
dgConvexHull3DFace::dgConvexHull3DFace
dgConvexHull3DFace()
Definition: dgConvexHull3d.cpp:65
dgConvexHull3d::m_aabbP1
dgBigVector m_aabbP1
Definition: dgConvexHull3d.h:97
dgVector.h
dgStdafx.h
dgInt8
char dgInt8
Definition: dgTypes.h:212
dgList.h
dgArray< dgBigVector >
dgConvexHull3d::m_count
dgInt32 m_count
Definition: dgConvexHull3d.h:94
dgConvexHull3DFace::GetMark
dgInt32 GetMark() const
Definition: dgConvexHull3d.h:43
dgHullVertex
Definition: dgConvexHull3d.cpp:51
dgConvexHull3d::m_diag
dgFloat64 m_diag
Definition: dgConvexHull3d.h:95
dgAABBPointTree3d
Definition: dgConvexHull3d.cpp:32
dgBigPlane
Definition: dgPlane.h:45
dgQuaternion.h
dgConvexHull3d::m_aabbP0
dgBigVector m_aabbP0
Definition: dgConvexHull3d.h:96
dgMemoryAllocator
Definition: dgMemory.h:73
dgPlane.h
dgConvexHull3d::GetVertex
const dgBigVector & GetVertex(dgInt32 i) const
Definition: dgConvexHull3d.h:112
dgConvexHull3d::GetVertexCount
dgInt32 GetVertexCount() const
Definition: dgConvexHull3d.h:102
dgConvexHull3DFace::m_index
dgInt32 m_index[3]
Definition: dgConvexHull3d.h:51
dgBigVector
Definition: dgVector.h:207
dgArray.h