1 #include "ConvexHull.h"
2 #include "dgConvexHull3d.h"
3 #include "WuQuantizer.h"
4
5 /*!
6 **
7 ** Copyright (c) 20011 by John W. Ratcliff mailto:jratcliffscarab@gmail.com
8 **
9 **
10 ** The MIT license:
11 **
12 ** Permission is hereby granted, free of charge, to any person obtaining a copy
13 ** of this software and associated documentation files (the "Software"), to deal
14 ** in the Software without restriction, including without limitation the rights
15 ** to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
16 ** copies of the Software, and to permit persons to whom the Software is furnished
17 ** to do so, subject to the following conditions:
18 **
19 ** The above copyright notice and this permission notice shall be included in all
20 ** copies or substantial portions of the Software.
21
22 ** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23 ** IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24 ** FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
25 ** AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
26 ** WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
27 ** CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
28
29 */
30
31 #include <math.h>
32 #include <float.h>
33 #include <string.h>
34
35 #pragma warning(disable:4100)
36
37 using namespace hacd;
38
39 namespace HACD
40 {
41
CreateConvexHull(const HullDesc & desc,HullResult & result)42 HullError HullLibrary::CreateConvexHull(const HullDesc &desc, // describes the input request
43 HullResult &result) // contains the results
44 {
45 HullError ret = QE_FAIL;
46
47 hacd::HaU32 vcount = desc.mVcount;
48 if ( vcount < 8 ) vcount = 8;
49
50 hacd::HaF32 *vsource = (hacd::HaF32 *) HACD_ALLOC( sizeof(hacd::HaF32)*vcount*3 );
51 hacd::HaF32 scale[3];
52 hacd::HaF32 center[3];
53
54 hacd::HaU32 ovcount;
55 bool ok = NormalizeAndCleanupVertices(desc.mVcount,desc.mVertices, desc.mVertexStride, ovcount, vsource, desc.mNormalEpsilon, scale, center, desc.mMaxVertices*2, desc.mUseWuQuantizer ); // normalize point cloud, remove duplicates!
56 if ( ok )
57 {
58 HaF64 *bigVertices = (HaF64 *)HACD_ALLOC(sizeof(HaF64)*3*ovcount);
59 for (HaU32 i=0; i<3*ovcount; i++)
60 {
61 bigVertices[i] = vsource[i];
62 }
63
64 dgConvexHull3d convexHull(bigVertices,sizeof(HaF64)*3,ovcount,0.0001f,desc.mMaxVertices);
65
66 if ( convexHull.GetCount() )
67 {
68 HaF32 *hullVertices = (HaF32 *)HACD_ALLOC( sizeof(HaF32)*3*convexHull.GetVertexCount() );
69
70 HaF32 *dest = hullVertices;
71 for (HaU32 i=0; i<(HaU32)convexHull.GetVertexCount(); i++)
72 {
73 const dgBigVector &v = convexHull.GetVertex(i);
74 dest[0] = (HaF32)v.m_x*scale[0]+center[0];
75 dest[1] = (HaF32)v.m_y*scale[1]+center[1];
76 dest[2] = (HaF32)v.m_z*scale[2]+center[2];
77 dest+=3;
78 }
79
80 HaU32 triangleCount = convexHull.GetCount();
81 HaU32 *indices = (HaU32*)HACD_ALLOC(triangleCount*sizeof(HaU32)*3);
82 HaU32 *destIndices = indices;
83 dgList<dgConvexHull3DFace>::Iterator iter(convexHull);
84 HaU32 outCount = 0;
85 for (iter.Begin(); iter; iter++)
86 {
87 dgConvexHull3DFace &face = (*iter);
88 destIndices[0] = face.m_index[0];
89 destIndices[1] = face.m_index[1];
90 destIndices[2] = face.m_index[2];
91 destIndices+=3;
92 outCount++;
93 }
94 HACD_ASSERT( outCount == triangleCount );
95
96 // re-index triangle mesh so it refers to only used vertices, rebuild a new vertex table.
97 hacd::HaF32 *vscratch = (hacd::HaF32 *) HACD_ALLOC( sizeof(hacd::HaF32)*convexHull.GetVertexCount()*3 );
98 BringOutYourDead(hullVertices,convexHull.GetVertexCount(),vscratch, ovcount, indices, triangleCount*3 );
99
100 ret = QE_OK;
101
102 result.mNumOutputVertices = ovcount;
103 result.mOutputVertices = (hacd::HaF32 *)HACD_ALLOC( sizeof(hacd::HaF32)*ovcount*3);
104 result.mNumTriangles = triangleCount;
105 result.mIndices = (hacd::HaU32 *) HACD_ALLOC( sizeof(hacd::HaU32)*triangleCount*3);
106 memcpy(result.mOutputVertices, vscratch, sizeof(hacd::HaF32)*3*ovcount );
107 memcpy(result.mIndices, indices, sizeof(hacd::HaU32)*triangleCount*3);
108
109 HACD_FREE(indices);
110 HACD_FREE(vscratch);
111 }
112
113 HACD_FREE(bigVertices);
114 }
115
116 HACD_FREE(vsource);
117
118 return ret;
119 }
120
121
122
ReleaseResult(HullResult & result)123 HullError HullLibrary::ReleaseResult(HullResult &result) // release memory allocated for this result, we are done with it.
124 {
125 if ( result.mOutputVertices )
126 {
127 HACD_FREE(result.mOutputVertices);
128 result.mOutputVertices = 0;
129 }
130 if ( result.mIndices )
131 {
132 HACD_FREE(result.mIndices);
133 result.mIndices = 0;
134 }
135 return QE_OK;
136 }
137
138
NormalizeAndCleanupVertices(hacd::HaU32 svcount,const hacd::HaF32 * svertices,hacd::HaU32 stride,hacd::HaU32 & vcount,hacd::HaF32 * vertices,hacd::HaF32 normalepsilon,hacd::HaF32 * scale,hacd::HaF32 * center,hacd::HaU32 maxVertices,bool useWuQuantizer)139 bool HullLibrary::NormalizeAndCleanupVertices(hacd::HaU32 svcount,
140 const hacd::HaF32 *svertices,
141 hacd::HaU32 stride,
142 hacd::HaU32 &vcount, // output number of vertices
143 hacd::HaF32 *vertices, // location to store the results.
144 hacd::HaF32 normalepsilon,
145 hacd::HaF32 *scale,
146 hacd::HaF32 *center,
147 hacd::HaU32 maxVertices,
148 bool useWuQuantizer)
149 {
150 bool ret = false;
151
152 WuQuantizer *wq = createWuQuantizer();
153 if ( wq )
154 {
155 const HaF32 *quantizedVertices;
156 if ( useWuQuantizer )
157 {
158 quantizedVertices = wq->wuQuantize3D(svcount,svertices,false,maxVertices,vcount);
159 }
160 else
161 {
162 quantizedVertices = wq->kmeansQuantize3D(svcount,svertices,false,maxVertices,vcount);
163 }
164 if ( quantizedVertices )
165 {
166 memcpy(vertices,quantizedVertices,sizeof(HaF32)*3*vcount);
167 const HaF32 *_scale = wq->getDenormalizeScale();
168 scale[0] = _scale[0];
169 scale[1] = _scale[1];
170 scale[2] = _scale[2];
171 const HaF32 *_center = wq->getDenormalizeCenter();
172 center[0] = _center[0];
173 center[1] = _center[1];
174 center[2] = _center[2];
175 ret = true;
176 }
177 wq->release();
178 }
179 return ret;
180 }
181
BringOutYourDead(const hacd::HaF32 * verts,hacd::HaU32 vcount,hacd::HaF32 * overts,hacd::HaU32 & ocount,hacd::HaU32 * indices,hacd::HaU32 indexcount)182 void HullLibrary::BringOutYourDead(const hacd::HaF32 *verts,hacd::HaU32 vcount, hacd::HaF32 *overts,hacd::HaU32 &ocount,hacd::HaU32 *indices,hacd::HaU32 indexcount)
183 {
184 hacd::HaU32 *used = (hacd::HaU32 *)HACD_ALLOC(sizeof(hacd::HaU32)*vcount);
185 memset(used,0,sizeof(hacd::HaU32)*vcount);
186
187 ocount = 0;
188
189 for (hacd::HaU32 i=0; i<indexcount; i++)
190 {
191 hacd::HaU32 v = indices[i]; // original array index
192
193 HACD_ASSERT( v < vcount );
194
195 if ( used[v] ) // if already remapped
196 {
197 indices[i] = used[v]-1; // index to new array
198 }
199 else
200 {
201
202 indices[i] = ocount; // new index mapping
203
204 overts[ocount*3+0] = verts[v*3+0]; // copy old vert to new vert array
205 overts[ocount*3+1] = verts[v*3+1];
206 overts[ocount*3+2] = verts[v*3+2];
207
208 ocount++; // increment output vert count
209
210 HACD_ASSERT( ocount <= vcount );
211
212 used[v] = ocount; // assign new index remapping
213 }
214 }
215
216 HACD_FREE(used);
217 }
218
219 //==================================================================================
CreateTriangleMesh(HullResult & answer,ConvexHullTriangleInterface * iface)220 HullError HullLibrary::CreateTriangleMesh(HullResult &answer,ConvexHullTriangleInterface *iface)
221 {
222 HullError ret = QE_FAIL;
223
224
225 const hacd::HaF32 *p = answer.mOutputVertices;
226 const hacd::HaU32 *idx = answer.mIndices;
227 hacd::HaU32 fcount = answer.mNumTriangles;
228
229 if ( p && idx && fcount )
230 {
231 ret = QE_OK;
232
233 for (hacd::HaU32 i=0; i<fcount; i++)
234 {
235 hacd::HaU32 pcount = *idx++;
236
237 hacd::HaU32 i1 = *idx++;
238 hacd::HaU32 i2 = *idx++;
239 hacd::HaU32 i3 = *idx++;
240
241 const hacd::HaF32 *p1 = &p[i1*3];
242 const hacd::HaF32 *p2 = &p[i2*3];
243 const hacd::HaF32 *p3 = &p[i3*3];
244
245 AddConvexTriangle(iface,p1,p2,p3);
246
247 pcount-=3;
248 while ( pcount )
249 {
250 i3 = *idx++;
251 p2 = p3;
252 p3 = &p[i3*3];
253
254 AddConvexTriangle(iface,p1,p2,p3);
255 pcount--;
256 }
257
258 }
259 }
260
261 return ret;
262 }
263
264 //==================================================================================
AddConvexTriangle(ConvexHullTriangleInterface * callback,const hacd::HaF32 * p1,const hacd::HaF32 * p2,const hacd::HaF32 * p3)265 void HullLibrary::AddConvexTriangle(ConvexHullTriangleInterface *callback,const hacd::HaF32 *p1,const hacd::HaF32 *p2,const hacd::HaF32 *p3)
266 {
267 ConvexHullVertex v1,v2,v3;
268
269 #define TSCALE1 (1.0f/4.0f)
270
271 v1.mPos[0] = p1[0];
272 v1.mPos[1] = p1[1];
273 v1.mPos[2] = p1[2];
274
275 v2.mPos[0] = p2[0];
276 v2.mPos[1] = p2[1];
277 v2.mPos[2] = p2[2];
278
279 v3.mPos[0] = p3[0];
280 v3.mPos[1] = p3[1];
281 v3.mPos[2] = p3[2];
282
283 hacd::HaF32 n[3];
284 ComputeNormal(n,p1,p2,p3);
285
286 v1.mNormal[0] = n[0];
287 v1.mNormal[1] = n[1];
288 v1.mNormal[2] = n[2];
289
290 v2.mNormal[0] = n[0];
291 v2.mNormal[1] = n[1];
292 v2.mNormal[2] = n[2];
293
294 v3.mNormal[0] = n[0];
295 v3.mNormal[1] = n[1];
296 v3.mNormal[2] = n[2];
297
298 const hacd::HaF32 *tp1 = p1;
299 const hacd::HaF32 *tp2 = p2;
300 const hacd::HaF32 *tp3 = p3;
301
302 hacd::HaI32 i1 = 0;
303 hacd::HaI32 i2 = 0;
304
305 hacd::HaF32 nx = fabsf(n[0]);
306 hacd::HaF32 ny = fabsf(n[1]);
307 hacd::HaF32 nz = fabsf(n[2]);
308
309 if ( nx <= ny && nx <= nz )
310 i1 = 0;
311 if ( ny <= nx && ny <= nz )
312 i1 = 1;
313 if ( nz <= nx && nz <= ny )
314 i1 = 2;
315
316 switch ( i1 )
317 {
318 case 0:
319 if ( ny < nz )
320 i2 = 1;
321 else
322 i2 = 2;
323 break;
324 case 1:
325 if ( nx < nz )
326 i2 = 0;
327 else
328 i2 = 2;
329 break;
330 case 2:
331 if ( nx < ny )
332 i2 = 0;
333 else
334 i2 = 1;
335 break;
336 }
337
338 v1.mTexel[0] = tp1[i1]*TSCALE1;
339 v1.mTexel[1] = tp1[i2]*TSCALE1;
340
341 v2.mTexel[0] = tp2[i1]*TSCALE1;
342 v2.mTexel[1] = tp2[i2]*TSCALE1;
343
344 v3.mTexel[0] = tp3[i1]*TSCALE1;
345 v3.mTexel[1] = tp3[i2]*TSCALE1;
346
347 callback->ConvexHullTriangle(v3,v2,v1);
348 }
349
350 //==================================================================================
ComputeNormal(hacd::HaF32 * n,const hacd::HaF32 * A,const hacd::HaF32 * B,const hacd::HaF32 * C)351 hacd::HaF32 HullLibrary::ComputeNormal(hacd::HaF32 *n,const hacd::HaF32 *A,const hacd::HaF32 *B,const hacd::HaF32 *C)
352 {
353 hacd::HaF32 vx,vy,vz,wx,wy,wz,vw_x,vw_y,vw_z,mag;
354
355 vx = (B[0] - C[0]);
356 vy = (B[1] - C[1]);
357 vz = (B[2] - C[2]);
358
359 wx = (A[0] - B[0]);
360 wy = (A[1] - B[1]);
361 wz = (A[2] - B[2]);
362
363 vw_x = vy * wz - vz * wy;
364 vw_y = vz * wx - vx * wz;
365 vw_z = vx * wy - vy * wx;
366
367 mag = sqrtf((vw_x * vw_x) + (vw_y * vw_y) + (vw_z * vw_z));
368
369 if ( mag < 0.000001f )
370 {
371 mag = 0;
372 }
373 else
374 {
375 mag = 1.0f/mag;
376 }
377
378 n[0] = vw_x * mag;
379 n[1] = vw_y * mag;
380 n[2] = vw_z * mag;
381
382 return mag;
383 }
384
385 } // End of namespace HACD
386