1 #include "float_math.h"
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <string.h>
6 #include <assert.h>
7
8 /*----------------------------------------------------------------------
9 Copyright (c) 2004 Open Dynamics Framework Group
10 www.physicstools.org
11 All rights reserved.
12
13 Redistribution and use in source and binary forms, with or without modification, are permitted provided
14 that the following conditions are met:
15
16 Redistributions of source code must retain the above copyright notice, this list of conditions
17 and the following disclaimer.
18
19 Redistributions in binary form must reproduce the above copyright notice,
20 this list of conditions and the following disclaimer in the documentation
21 and/or other materials provided with the distribution.
22
23 Neither the name of the Open Dynamics Framework Group nor the names of its contributors may
24 be used to endorse or promote products derived from this software without specific prior written permission.
25
26 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 'AS IS' AND ANY EXPRESS OR IMPLIED WARRANTIES,
27 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
28 DISCLAIMED. IN NO EVENT SHALL THE INTEL OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
29 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
31 IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
32 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 -----------------------------------------------------------------------*/
34
35 // http://codesuppository.blogspot.com
36 //
37 // mailto: jratcliff@infiniplex.net
38 //
39 // http://www.amillionpixels.us
40 //
41
42 #include "ConvexDecomposition.h"
43 #include "cd_vector.h"
44 #include "cd_hull.h"
45 #include "bestfit.h"
46 #include "planetri.h"
47 #include "vlookup.h"
48 #include "splitplane.h"
49 #include "meshvolume.h"
50 #include "concavity.h"
51 #include "bestfitobb.h"
52 #include "float_math.h"
53 #include "fitsphere.h"
54
55 #define SHOW_MESH 0
56 #define MAKE_MESH 1
57
58 using namespace ConvexDecomposition;
59
60 namespace ConvexDecomposition
61 {
62 class FaceTri
63 {
64 public:
FaceTri(void)65 FaceTri(void){};
FaceTri(const float * vertices,unsigned int i1,unsigned int i2,unsigned int i3)66 FaceTri(const float *vertices, unsigned int i1, unsigned int i2, unsigned int i3)
67 {
68 mP1.Set(&vertices[i1 * 3]);
69 mP2.Set(&vertices[i2 * 3]);
70 mP3.Set(&vertices[i3 * 3]);
71 }
72
73 Vector3d mP1;
74 Vector3d mP2;
75 Vector3d mP3;
76 Vector3d mNormal;
77 };
78
addTri(VertexLookup vl,UintVector & list,const Vector3d & p1,const Vector3d & p2,const Vector3d & p3)79 void addTri(VertexLookup vl, UintVector &list, const Vector3d &p1, const Vector3d &p2, const Vector3d &p3)
80 {
81 unsigned int i1 = Vl_getIndex(vl, p1.Ptr());
82 unsigned int i2 = Vl_getIndex(vl, p2.Ptr());
83 unsigned int i3 = Vl_getIndex(vl, p3.Ptr());
84
85 // do *not* process degenerate triangles!
86
87 if (i1 != i2 && i1 != i3 && i2 != i3)
88 {
89 list.push_back(i1);
90 list.push_back(i2);
91 list.push_back(i3);
92 }
93 }
94
calcConvexDecomposition(unsigned int vcount,const float * vertices,unsigned int tcount,const unsigned int * indices,ConvexDecompInterface * callback,float masterVolume,unsigned int depth)95 void calcConvexDecomposition(unsigned int vcount,
96 const float *vertices,
97 unsigned int tcount,
98 const unsigned int *indices,
99 ConvexDecompInterface *callback,
100 float masterVolume,
101 unsigned int depth)
102
103 {
104 float plane[4];
105
106 bool split = false;
107
108 if (depth < MAXDEPTH)
109 {
110 float volume;
111 float c = computeConcavity(vcount, vertices, tcount, indices, callback, plane, volume);
112
113 if (depth == 0)
114 {
115 masterVolume = volume;
116 }
117
118 float percent = (c * 100.0f) / masterVolume;
119
120 if (percent > CONCAVE_PERCENT) // if great than 5% of the total volume is concave, go ahead and keep splitting.
121 {
122 split = true;
123 }
124 }
125
126 if (depth >= MAXDEPTH || !split)
127 {
128 #if 1
129
130 HullResult result;
131 HullLibrary hl;
132 HullDesc desc;
133
134 desc.SetHullFlag(QF_TRIANGLES);
135
136 desc.mVcount = vcount;
137 desc.mVertices = vertices;
138 desc.mVertexStride = sizeof(float) * 3;
139
140 HullError ret = hl.CreateConvexHull(desc, result);
141
142 if (ret == QE_OK)
143 {
144 ConvexResult r(result.mNumOutputVertices, result.mOutputVertices, result.mNumFaces, result.mIndices);
145
146 callback->ConvexDecompResult(r);
147 }
148
149 #else
150
151 static unsigned int colors[8] =
152 {
153 0xFF0000,
154 0x00FF00,
155 0x0000FF,
156 0xFFFF00,
157 0x00FFFF,
158 0xFF00FF,
159 0xFFFFFF,
160 0xFF8040};
161
162 static int count = 0;
163
164 count++;
165
166 if (count == 8) count = 0;
167
168 assert(count >= 0 && count < 8);
169
170 unsigned int color = colors[count];
171
172 const unsigned int *source = indices;
173
174 for (unsigned int i = 0; i < tcount; i++)
175 {
176 unsigned int i1 = *source++;
177 unsigned int i2 = *source++;
178 unsigned int i3 = *source++;
179
180 FaceTri t(vertices, i1, i2, i3);
181
182 callback->ConvexDebugTri(t.mP1.Ptr(), t.mP2.Ptr(), t.mP3.Ptr(), color);
183 }
184 #endif
185
186 hl.ReleaseResult(result);
187 return;
188 }
189
190 UintVector ifront;
191 UintVector iback;
192
193 VertexLookup vfront = Vl_createVertexLookup();
194 VertexLookup vback = Vl_createVertexLookup();
195
196 bool showmesh = false;
197 #if SHOW_MESH
198 showmesh = true;
199 #endif
200
201 if (0)
202 {
203 showmesh = true;
204 for (float x = -1; x < 1; x += 0.10f)
205 {
206 for (float y = 0; y < 1; y += 0.10f)
207 {
208 for (float z = -1; z < 1; z += 0.04f)
209 {
210 float d = x * plane[0] + y * plane[1] + z * plane[2] + plane[3];
211 Vector3d p(x, y, z);
212 if (d >= 0)
213 callback->ConvexDebugPoint(p.Ptr(), 0.02f, 0x00FF00);
214 else
215 callback->ConvexDebugPoint(p.Ptr(), 0.02f, 0xFF0000);
216 }
217 }
218 }
219 }
220
221 if (1)
222 {
223 // ok..now we are going to 'split' all of the input triangles against this plane!
224 const unsigned int *source = indices;
225 for (unsigned int i = 0; i < tcount; i++)
226 {
227 unsigned int i1 = *source++;
228 unsigned int i2 = *source++;
229 unsigned int i3 = *source++;
230
231 FaceTri t(vertices, i1, i2, i3);
232
233 Vector3d front[4];
234 Vector3d back[4];
235
236 unsigned int fcount = 0;
237 unsigned int bcount = 0;
238
239 PlaneTriResult result;
240
241 result = planeTriIntersection(plane, t.mP1.Ptr(), sizeof(Vector3d), 0.00001f, front[0].Ptr(), fcount, back[0].Ptr(), bcount);
242
243 if (fcount > 4 || bcount > 4)
244 {
245 result = planeTriIntersection(plane, t.mP1.Ptr(), sizeof(Vector3d), 0.00001f, front[0].Ptr(), fcount, back[0].Ptr(), bcount);
246 }
247
248 switch (result)
249 {
250 case PTR_FRONT:
251
252 assert(fcount == 3);
253
254 if (showmesh)
255 callback->ConvexDebugTri(front[0].Ptr(), front[1].Ptr(), front[2].Ptr(), 0x00FF00);
256
257 #if MAKE_MESH
258
259 addTri(vfront, ifront, front[0], front[1], front[2]);
260
261 #endif
262
263 break;
264 case PTR_BACK:
265 assert(bcount == 3);
266
267 if (showmesh)
268 callback->ConvexDebugTri(back[0].Ptr(), back[1].Ptr(), back[2].Ptr(), 0xFFFF00);
269
270 #if MAKE_MESH
271
272 addTri(vback, iback, back[0], back[1], back[2]);
273
274 #endif
275
276 break;
277 case PTR_SPLIT:
278
279 assert(fcount >= 3 && fcount <= 4);
280 assert(bcount >= 3 && bcount <= 4);
281
282 #if MAKE_MESH
283
284 addTri(vfront, ifront, front[0], front[1], front[2]);
285 addTri(vback, iback, back[0], back[1], back[2]);
286
287 if (fcount == 4)
288 {
289 addTri(vfront, ifront, front[0], front[2], front[3]);
290 }
291
292 if (bcount == 4)
293 {
294 addTri(vback, iback, back[0], back[2], back[3]);
295 }
296
297 #endif
298
299 if (showmesh)
300 {
301 callback->ConvexDebugTri(front[0].Ptr(), front[1].Ptr(), front[2].Ptr(), 0x00D000);
302 callback->ConvexDebugTri(back[0].Ptr(), back[1].Ptr(), back[2].Ptr(), 0xD0D000);
303
304 if (fcount == 4)
305 {
306 callback->ConvexDebugTri(front[0].Ptr(), front[2].Ptr(), front[3].Ptr(), 0x00D000);
307 }
308 if (bcount == 4)
309 {
310 callback->ConvexDebugTri(back[0].Ptr(), back[2].Ptr(), back[3].Ptr(), 0xD0D000);
311 }
312 }
313
314 break;
315 }
316 }
317
318 // ok... here we recursively call
319 if (ifront.size())
320 {
321 unsigned int vcount = Vl_getVcount(vfront);
322 const float *vertices = Vl_getVertices(vfront);
323 unsigned int tcount = ifront.size() / 3;
324
325 calcConvexDecomposition(vcount, vertices, tcount, &ifront[0], callback, masterVolume, depth + 1);
326 }
327
328 ifront.clear();
329
330 Vl_releaseVertexLookup(vfront);
331
332 if (iback.size())
333 {
334 unsigned int vcount = Vl_getVcount(vback);
335 const float *vertices = Vl_getVertices(vback);
336 unsigned int tcount = iback.size() / 3;
337
338 calcConvexDecomposition(vcount, vertices, tcount, &iback[0], callback, masterVolume, depth + 1);
339 }
340
341 iback.clear();
342 Vl_releaseVertexLookup(vback);
343 }
344 }
345
346 } // namespace ConvexDecomposition
347