Bullet Collision Detection & Physics Library
btConvexHull.h
Go to the documentation of this file.
1
2/*
3Stan Melax Convex Hull Computation
4Copyright (c) 2008 Stan Melax http://www.melax.com/
5
6This software is provided 'as-is', without any express or implied warranty.
7In no event will the authors be held liable for any damages arising from the use of this software.
8Permission is granted to anyone to use this software for any purpose,
9including commercial applications, and to alter it and redistribute it freely,
10subject to the following restrictions:
11
121. 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.
132. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
143. 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"
24
26
28{
29public:
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
56{
57public:
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;
76 mVertices = vertices;
77 mVertexStride = stride;
78 mNormalEpsilon = btScalar(0.001);
79 mMaxVertices = 4096;
80 }
81
83 {
84 if (mFlags & flag) return true;
85 return false;
86 }
87
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.
112
114{
115public:
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
123{
124public:
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)
132 HalfEdge(short _ea, unsigned char _v, unsigned char _p) : ea(_ea), v(_v), p(_p) {}
133 };
135 {
136 }
138 {
139 }
144};
145
146class int4
147{
148public:
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{
164public:
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
186public:
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
193private:
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);
199
201
202 void checkit(btHullTriangle* t);
203
205
207
209
211
213
214 void extrude(class btHullTriangle* t0, int v);
215
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.
230 btVector3& scale);
231};
232
233#endif //BT_CD_HULL_H
HullError
@ QE_OK
@ QE_FAIL
btAlignedObjectArray< unsigned int > TUIntArray
includes modifications/improvements by John Ratcliff, see BringOutYourDead below.
HullFlag
@ QF_TRIANGLES
@ QF_REVERSE_ORDER
@ QF_DEFAULT
const T & btMax(const T &a, const T &b)
Definition btMinMax.h:27
float btScalar
The btScalar type abstracts floating point numbers, to easily switch between double and single floati...
Definition btScalar.h:314
unsigned char p
unsigned char v
HalfEdge(short _ea, unsigned char _v, unsigned char _p)
btAlignedObjectArray< HalfEdge > edges
btAlignedObjectArray< btPlane > facets
btAlignedObjectArray< btVector3 > vertices
HullDesc(HullFlag flag, unsigned int vcount, const btVector3 *vertices, unsigned int stride=sizeof(btVector3))
bool HasHullFlag(HullFlag flag) const
unsigned int mVcount
unsigned int mFlags
btScalar mNormalEpsilon
unsigned int mMaxFaces
HullDesc(void)
void ClearHullFlag(HullFlag flag)
unsigned int mMaxVertices
const btVector3 * mVertices
unsigned int mVertexStride
void SetHullFlag(HullFlag flag)
The HullLibrary class can create a convex hull from a collection of vertices, using the ComputeHull m...
btHullTriangle * extrudable(btScalar epsilon)
class btHullTriangle * allocateTriangle(int a, int b, int c)
bool ComputeHull(unsigned int vcount, const btVector3 *vertices, PHullResult &result, unsigned int vlimit)
HullError ReleaseResult(HullResult &result)
void BringOutYourDead(const btVector3 *verts, unsigned int vcount, btVector3 *overts, unsigned int &ocount, unsigned int *indices, unsigned indexcount)
HullError CreateConvexHull(const HullDesc &desc, HullResult &result)
void deAllocateTriangle(btHullTriangle *)
int calchull(btVector3 *verts, int verts_count, TUIntArray &tris_out, int &tris_count, int vlimit)
btAlignedObjectArray< int > m_vertexIndexMapping
void b2bfix(btHullTriangle *s, btHullTriangle *t)
void removeb2b(btHullTriangle *s, btHullTriangle *t)
btAlignedObjectArray< class btHullTriangle * > m_tris
class ConvexH * ConvexHCrop(ConvexH &convex, const btPlane &slice)
void checkit(btHullTriangle *t)
ConvexH * test_cube()
void extrude(class btHullTriangle *t0, int v)
int calchullgen(btVector3 *verts, int verts_count, int vlimit)
int4 FindSimplex(btVector3 *verts, int verts_count, btAlignedObjectArray< int > &allow)
bool CleanupVertices(unsigned int svcount, const btVector3 *svertices, unsigned int stride, unsigned int &vcount, btVector3 *vertices, btScalar normalepsilon, btVector3 &scale)
btAlignedObjectArray< btVector3 > m_OutputVertices
btAlignedObjectArray< unsigned int > m_Indices
HullResult(void)
unsigned int mNumOutputVertices
unsigned int mNumFaces
unsigned int mNumIndices
unsigned int mFaceCount
PHullResult(void)
unsigned int mVcount
unsigned int mIndexCount
btVector3 * mVertices
TUIntArray m_Indices
The btAlignedObjectArray template class uses a subset of the stl::vector interface for its methods It...
btPlane(const btVector3 &n, btScalar d)
btVector3 normal
btScalar dist
btVector3 can be used to represent 3D points and vectors.
Definition btVector3.h:82
int4(int _x, int _y, int _z, int _w)
int & operator[](int i)
const int & operator[](int i) const