Blender  V3.3
btConvexHull.h
Go to the documentation of this file.
1 
2 /*
3 Stan Melax Convex Hull Computation
4 Copyright (c) 2008 Stan Melax http://www.melax.com/
5 
6 This software is provided 'as-is', without any express or implied warranty.
7 In no event will the authors be held liable for any damages 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 freely,
10 subject to the following restrictions:
11 
12 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
13 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
14 3. This notice may not be removed or altered from any source distribution.
15 */
16 
18 
19 #ifndef BT_CD_HULL_H
20 #define BT_CD_HULL_H
21 
22 #include "btVector3.h"
23 #include "btAlignedObjectArray.h"
24 
26 
28 {
29 public:
30  HullResult(void)
31  {
32  mPolygons = true;
34  mNumFaces = 0;
35  mNumIndices = 0;
36  }
37  bool mPolygons; // true if indices represents polygons, false indices are triangles
38  unsigned int mNumOutputVertices; // number of vertices in the output hull
40  unsigned int mNumFaces; // the number of faces produced
41  unsigned int mNumIndices; // the total number of indices
43 
44  // If triangles, then indices are array indexes into the vertex list.
45  // If polygons, indices are in the form (number of points in face) (p1, p2, p3, ..) etc..
46 };
47 
49 {
50  QF_TRIANGLES = (1 << 0), // report results as triangles, not polygons.
51  QF_REVERSE_ORDER = (1 << 1), // reverse order of the triangle indices.
53 };
54 
55 class HullDesc
56 {
57 public:
58  HullDesc(void)
59  {
61  mVcount = 0;
62  mVertices = 0;
63  mVertexStride = sizeof(btVector3);
64  mNormalEpsilon = 0.001f;
65  mMaxVertices = 4096; // maximum number of points to be considered for a convex hull.
66  mMaxFaces = 4096;
67  };
68 
70  unsigned int vcount,
71  const btVector3* vertices,
72  unsigned int stride = sizeof(btVector3))
73  {
74  mFlags = flag;
75  mVcount = vcount;
76  mVertices = vertices;
78  mNormalEpsilon = btScalar(0.001);
79  mMaxVertices = 4096;
80  }
81 
82  bool HasHullFlag(HullFlag flag) const
83  {
84  if (mFlags & flag) return true;
85  return false;
86  }
87 
88  void SetHullFlag(HullFlag flag)
89  {
90  mFlags |= flag;
91  }
92 
94  {
95  mFlags &= ~flag;
96  }
97 
98  unsigned int mFlags; // flags to use when generating the convex hull.
99  unsigned int mVcount; // number of vertices in the input point cloud
100  const btVector3* mVertices; // the array of vertices.
101  unsigned int mVertexStride; // the stride of each vertex, in bytes.
102  btScalar mNormalEpsilon; // the epsilon for removing duplicates. This is a normalized value, if normalized bit is on.
103  unsigned int mMaxVertices; // maximum number of vertices to be considered for the hull!
104  unsigned int mMaxFaces;
105 };
106 
108 {
109  QE_OK, // success!
110  QE_FAIL // failed.
111 };
112 
113 class btPlane
114 {
115 public:
117  btScalar dist; // distance below origin - the D from plane equasion Ax+By+Cz+D=0
118  btPlane(const btVector3& n, btScalar d) : normal(n), dist(d) {}
119  btPlane() : normal(), dist(0) {}
120 };
121 
122 class ConvexH
123 {
124 public:
125  class HalfEdge
126  {
127  public:
128  short ea; // the other half of the edge (index into edges list)
129  unsigned char v; // the vertex at the start of this edge (index into vertices list)
130  unsigned char p; // the facet on which this edge lies (index into facets list)
131  HalfEdge() {}
132  HalfEdge(short _ea, unsigned char _v, unsigned char _p) : ea(_ea), v(_v), p(_p) {}
133  };
135  {
136  }
138  {
139  }
143  ConvexH(int vertices_size, int edges_size, int facets_size);
144 };
145 
146 class int4
147 {
148 public:
149  int x, y, z, w;
150  int4(){};
151  int4(int _x, int _y, int _z, int _w)
152  {
153  x = _x;
154  y = _y;
155  z = _z;
156  w = _w;
157  }
158  const int& operator[](int i) const { return (&x)[i]; }
159  int& operator[](int i) { return (&x)[i]; }
160 };
161 
163 {
164 public:
166  {
167  mVcount = 0;
168  mIndexCount = 0;
169  mFaceCount = 0;
170  mVertices = 0;
171  }
172 
173  unsigned int mVcount;
174  unsigned int mIndexCount;
175  unsigned int mFaceCount;
178 };
179 
183 {
185 
186 public:
188 
189  HullError CreateConvexHull(const HullDesc& desc, // describes the input request
190  HullResult& result); // contains the resulst
191  HullError ReleaseResult(HullResult& result); // release memory allocated for this result, we are done with it.
192 
193 private:
194  bool ComputeHull(unsigned int vcount, const btVector3* vertices, PHullResult& result, unsigned int vlimit);
195 
196  class btHullTriangle* allocateTriangle(int a, int b, int c);
197  void deAllocateTriangle(btHullTriangle*);
198  void b2bfix(btHullTriangle* s, btHullTriangle* t);
199 
200  void removeb2b(btHullTriangle* s, btHullTriangle* t);
201 
202  void checkit(btHullTriangle* t);
203 
204  btHullTriangle* extrudable(btScalar epsilon);
205 
206  int calchull(btVector3* verts, int verts_count, TUIntArray& tris_out, int& tris_count, int vlimit);
207 
208  int calchullgen(btVector3* verts, int verts_count, int vlimit);
209 
210  int4 FindSimplex(btVector3* verts, int verts_count, btAlignedObjectArray<int>& allow);
211 
212  class ConvexH* ConvexHCrop(ConvexH& convex, const btPlane& slice);
213 
214  void extrude(class btHullTriangle* t0, int v);
215 
216  ConvexH* test_cube();
217 
218  //BringOutYourDead (John Ratcliff): When you create a convex hull you hand it a large input set of vertices forming a 'point cloud'.
219  //After the hull is generated it give you back a set of polygon faces which index the *original* point cloud.
220  //The thing is, often times, there are many 'dead vertices' in the point cloud that are on longer referenced by the hull.
221  //The routine 'BringOutYourDead' find only the referenced vertices, copies them to an new buffer, and re-indexes the hull so that it is a minimal representation.
222  void BringOutYourDead(const btVector3* verts, unsigned int vcount, btVector3* overts, unsigned int& ocount, unsigned int* indices, unsigned indexcount);
223 
224  bool CleanupVertices(unsigned int svcount,
225  const btVector3* svertices,
226  unsigned int stride,
227  unsigned int& vcount, // output number of vertices
228  btVector3* vertices, // location to store the results.
229  btScalar normalepsilon,
230  btVector3& scale);
231 };
232 
233 #endif //BT_CD_HULL_H
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei stride
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble t
ATTR_WARN_UNUSED_RESULT const BMVert * v
HullError
Definition: btConvexHull.h:108
@ QE_OK
Definition: btConvexHull.h:109
@ QE_FAIL
Definition: btConvexHull.h:110
btAlignedObjectArray< unsigned int > TUIntArray
includes modifications/improvements by John Ratcliff, see BringOutYourDead below.
Definition: btConvexHull.h:25
HullFlag
Definition: btConvexHull.h:49
@ QF_TRIANGLES
Definition: btConvexHull.h:50
@ QF_REVERSE_ORDER
Definition: btConvexHull.h:51
@ QF_DEFAULT
Definition: btConvexHull.h:52
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
Definition: btScalar.h:314
btVector3
btVector3 can be used to represent 3D points and vectors. It has an un-used w component to suit 16-by...
Definition: btVector3.h:82
unsigned char p
Definition: btConvexHull.h:130
unsigned char v
Definition: btConvexHull.h:129
HalfEdge(short _ea, unsigned char _v, unsigned char _p)
Definition: btConvexHull.h:132
btAlignedObjectArray< HalfEdge > edges
Definition: btConvexHull.h:141
btAlignedObjectArray< btPlane > facets
Definition: btConvexHull.h:142
btAlignedObjectArray< btVector3 > vertices
Definition: btConvexHull.h:140
HullDesc(HullFlag flag, unsigned int vcount, const btVector3 *vertices, unsigned int stride=sizeof(btVector3))
Definition: btConvexHull.h:69
bool HasHullFlag(HullFlag flag) const
Definition: btConvexHull.h:82
unsigned int mVcount
Definition: btConvexHull.h:99
unsigned int mFlags
Definition: btConvexHull.h:98
btScalar mNormalEpsilon
Definition: btConvexHull.h:102
unsigned int mMaxFaces
Definition: btConvexHull.h:104
HullDesc(void)
Definition: btConvexHull.h:58
void ClearHullFlag(HullFlag flag)
Definition: btConvexHull.h:93
unsigned int mMaxVertices
Definition: btConvexHull.h:103
const btVector3 * mVertices
Definition: btConvexHull.h:100
unsigned int mVertexStride
Definition: btConvexHull.h:101
void SetHullFlag(HullFlag flag)
Definition: btConvexHull.h:88
HullError ReleaseResult(HullResult &result)
HullError CreateConvexHull(const HullDesc &desc, HullResult &result)
btAlignedObjectArray< int > m_vertexIndexMapping
Definition: btConvexHull.h:187
btAlignedObjectArray< btVector3 > m_OutputVertices
Definition: btConvexHull.h:39
btAlignedObjectArray< unsigned int > m_Indices
Definition: btConvexHull.h:42
HullResult(void)
Definition: btConvexHull.h:30
unsigned int mNumOutputVertices
Definition: btConvexHull.h:38
unsigned int mNumFaces
Definition: btConvexHull.h:40
bool mPolygons
Definition: btConvexHull.h:37
unsigned int mNumIndices
Definition: btConvexHull.h:41
unsigned int mFaceCount
Definition: btConvexHull.h:175
PHullResult(void)
Definition: btConvexHull.h:165
unsigned int mVcount
Definition: btConvexHull.h:173
unsigned int mIndexCount
Definition: btConvexHull.h:174
btVector3 * mVertices
Definition: btConvexHull.h:176
TUIntArray m_Indices
Definition: btConvexHull.h:177
btPlane(const btVector3 &n, btScalar d)
Definition: btConvexHull.h:118
btVector3 normal
Definition: btConvexHull.h:116
btScalar dist
Definition: btConvexHull.h:117
int x
Definition: btConvexHull.h:149
int w
Definition: btConvexHull.h:149
const int & operator[](int i) const
Definition: btConvexHull.h:158
int4(int _x, int _y, int _z, int _w)
Definition: btConvexHull.h:151
int y
Definition: btConvexHull.h:149
int z
Definition: btConvexHull.h:149
int & operator[](int i)
Definition: btConvexHull.h:159
static float verts[][3]
ccl_gpu_kernel_postfix int ccl_global int * indices
static unsigned c
Definition: RandGen.cpp:83
static unsigned a[3]
Definition: RandGen.cpp:78
static double epsilon
static const pxr::TfToken b("b", pxr::TfToken::Immortal)