1 #ifndef CONVEX_HULL_H
2 
3 #define CONVEX_HULL_H
4 
5 #include "PlatformConfigHACD.h"
6 
7 /*!
8 **
9 ** Copyright (c) 20011 by John W. Ratcliff mailto:jratcliffscarab@gmail.com
10 **
11 **
12 ** The MIT license:
13 **
14 ** Permission is hereby granted, free of charge, to any person obtaining a copy
15 ** of this software and associated documentation files (the "Software"), to deal
16 ** in the Software without restriction, including without limitation the rights
17 ** to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
18 ** copies of the Software, and to permit persons to whom the Software is furnished
19 ** to do so, subject to the following conditions:
20 **
21 ** The above copyright notice and this permission notice shall be included in all
22 ** copies or substantial portions of the Software.
23 
24 ** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
25 ** IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26 ** FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
27 ** AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
28 ** WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
29 ** CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
30 
31 */
32 
33 namespace HACD
34 {
35 
36 class HullResult
37 {
38 public:
HullResult(void)39 	HullResult(void)
40 	{
41 		mNumOutputVertices = 0;
42 		mOutputVertices = 0;
43 		mNumTriangles = 0;
44 		mIndices = 0;
45 	}
46 	hacd::HaU32			mNumOutputVertices;         // number of vertices in the output hull
47 	hacd::HaF32			*mOutputVertices;            // array of vertices, 3 floats each x,y,z
48 	hacd::HaU32			mNumTriangles;                  // the number of faces produced
49 	hacd::HaU32			*mIndices;                   // pointer to indices.
50 
51 // If triangles, then indices are array indexes into the vertex list.
52 // If polygons, indices are in the form (number of points in face) (p1, p2, p3, ..) etc..
53 };
54 
55 class HullDesc
56 {
57 public:
HullDesc(void)58 	HullDesc(void)
59 	{
60 		mVcount         = 0;
61 		mVertices       = 0;
62 		mVertexStride   = sizeof(hacd::HaF32)*3;
63 		mNormalEpsilon  = 0.001f;
64 		mMaxVertices = 256; // maximum number of points to be considered for a convex hull.
65 		mSkinWidth = 0.0f; // default is one centimeter
66 		mUseWuQuantizer = true;
67 	};
68 
HullDesc(hacd::HaU32 vcount,const hacd::HaF32 * vertices,hacd::HaU32 stride)69 	HullDesc(hacd::HaU32 vcount,
70 			 const hacd::HaF32 *vertices,
71 			 hacd::HaU32 stride)
72 	{
73 		mVcount         = vcount;
74 		mVertices       = vertices;
75 		mVertexStride   = stride;
76 		mNormalEpsilon  = 0.001f;
77 		mMaxVertices    = 4096;
78 		mSkinWidth = 0.01f; // default is one centimeter
79 	}
80 
81 	bool				mUseWuQuantizer;		// if True, uses the WuQuantizer to clean-up the input point cloud.  Of false, it uses Kmeans clustering.  More accurate but slower.
82 	hacd::HaU32			mVcount;          // number of vertices in the input point cloud
83 	const hacd::HaF32	*mVertices;        // the array of vertices.
84 	hacd::HaU32			mVertexStride;    // the stride of each vertex, in bytes.
85 	hacd::HaF32			mNormalEpsilon;   // the epsilon for removing duplicates.  This is a normalized value, if normalized bit is on.
86 	hacd::HaF32			mSkinWidth;
87 	hacd::HaU32			mMaxVertices;               // maximum number of vertices to be considered for the hull!
88 };
89 
90 enum HullError
91 {
92 	QE_OK,            // success!
93 	QE_FAIL,           // failed.
94 	QE_NOT_READY,
95 };
96 
97 // This class is used when converting a convex hull into a triangle mesh.
98 class ConvexHullVertex
99 {
100 public:
101 	hacd::HaF32         mPos[3];
102 	hacd::HaF32         mNormal[3];
103 	hacd::HaF32         mTexel[2];
104 };
105 
106 // A virtual interface to receive the triangles from the convex hull.
107 class ConvexHullTriangleInterface
108 {
109 public:
110 	virtual void ConvexHullTriangle(const ConvexHullVertex &v1,const ConvexHullVertex &v2,const ConvexHullVertex &v3) = 0;
111 };
112 
113 
114 class HullLibrary
115 {
116 public:
117 
118 	HullError CreateConvexHull(const HullDesc       &desc,           // describes the input request
119 								HullResult           &result);        // contains the resulst
120 
121 	HullError ReleaseResult(HullResult &result); // release memory allocated for this result, we are done with it.
122 
123 	HullError CreateTriangleMesh(HullResult &answer,ConvexHullTriangleInterface *iface);
124 private:
125 	hacd::HaF32 ComputeNormal(hacd::HaF32 *n,const hacd::HaF32 *A,const hacd::HaF32 *B,const hacd::HaF32 *C);
126 	void AddConvexTriangle(ConvexHullTriangleInterface *callback,const hacd::HaF32 *p1,const hacd::HaF32 *p2,const hacd::HaF32 *p3);
127 
128 	void BringOutYourDead(const hacd::HaF32 *verts,hacd::HaU32 vcount, hacd::HaF32 *overts,hacd::HaU32 &ocount,hacd::HaU32 *indices,hacd::HaU32 indexcount);
129 
130 	bool    NormalizeAndCleanupVertices(hacd::HaU32 svcount,
131 							const hacd::HaF32 *svertices,
132 							hacd::HaU32 stride,
133 							hacd::HaU32 &vcount,       // output number of vertices
134 							hacd::HaF32 *vertices,                 // location to store the results.
135 							hacd::HaF32  normalepsilon,
136 							hacd::HaF32 *scale,
137 							hacd::HaF32 *center,
138 							hacd::HaU32 maxVertices,
139 							bool useWuQuantizer);
140 };
141 
142 } // end of namespace HACD
143 
144 #endif
145