1 #include "float_math.h"
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <string.h>
5 #include <assert.h>
6
7 #include <vector>
8
9 /*----------------------------------------------------------------------
10 Copyright (c) 2004 Open Dynamics Framework Group
11 www.physicstools.org
12 All rights reserved.
13
14 Redistribution and use in source and binary forms, with or without modification, are permitted provided
15 that the following conditions are met:
16
17 Redistributions of source code must retain the above copyright notice, this list of conditions
18 and the following disclaimer.
19
20 Redistributions in binary form must reproduce the above copyright notice,
21 this list of conditions and the following disclaimer in the documentation
22 and/or other materials provided with the distribution.
23
24 Neither the name of the Open Dynamics Framework Group nor the names of its contributors may
25 be used to endorse or promote products derived from this software without specific prior written permission.
26
27 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 'AS IS' AND ANY EXPRESS OR IMPLIED WARRANTIES,
28 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
29 DISCLAIMED. IN NO EVENT SHALL THE INTEL OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
31 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
32 IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
33 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 -----------------------------------------------------------------------*/
35
36 // http://codesuppository.blogspot.com
37 //
38 // mailto: jratcliff@infiniplex.net
39 //
40 // http://www.amillionpixels.us
41 //
42
43 #include "concavity.h"
44 #include "raytri.h"
45 #include "bestfit.h"
46 #include "cd_hull.h"
47 #include "meshvolume.h"
48 #include "cd_vector.h"
49 #include "splitplane.h"
50 #include "ConvexDecomposition.h"
51
52 #define WSCALE 4
53 #define CONCAVE_THRESH 0.05f
54
55 namespace ConvexDecomposition
56 {
getDebugColor(void)57 unsigned int getDebugColor(void)
58 {
59 static unsigned int colors[8] =
60 {
61 0xFF0000,
62 0x00FF00,
63 0x0000FF,
64 0xFFFF00,
65 0x00FFFF,
66 0xFF00FF,
67 0xFFFFFF,
68 0xFF8040};
69
70 static int count = 0;
71
72 count++;
73
74 if (count == 8) count = 0;
75
76 assert(count >= 0 && count < 8);
77
78 unsigned int color = colors[count];
79
80 return color;
81 }
82
83 class Wpoint
84 {
85 public:
Wpoint(const Vector3d & p,float w)86 Wpoint(const Vector3d &p, float w)
87 {
88 mPoint = p;
89 mWeight = w;
90 }
91
92 Vector3d mPoint;
93 float mWeight;
94 };
95
96 typedef std::vector<Wpoint> WpointVector;
97
DistToPt(const float * p,const float * plane)98 static inline float DistToPt(const float *p, const float *plane)
99 {
100 float x = p[0];
101 float y = p[1];
102 float z = p[2];
103 float d = x * plane[0] + y * plane[1] + z * plane[2] + plane[3];
104 return d;
105 }
106
intersect(const float * p1,const float * p2,float * split,const float * plane)107 static void intersect(const float *p1, const float *p2, float *split, const float *plane)
108 {
109 float dp1 = DistToPt(p1, plane);
110
111 float dir[3];
112
113 dir[0] = p2[0] - p1[0];
114 dir[1] = p2[1] - p1[1];
115 dir[2] = p2[2] - p1[2];
116
117 float dot1 = dir[0] * plane[0] + dir[1] * plane[1] + dir[2] * plane[2];
118 float dot2 = dp1 - plane[3];
119
120 float t = -(plane[3] + dot2) / dot1;
121
122 split[0] = (dir[0] * t) + p1[0];
123 split[1] = (dir[1] * t) + p1[1];
124 split[2] = (dir[2] * t) + p1[2];
125 }
126
127 class CTri
128 {
129 public:
CTri(void)130 CTri(void){};
131
CTri(const float * p1,const float * p2,const float * p3,unsigned int i1,unsigned int i2,unsigned int i3)132 CTri(const float *p1, const float *p2, const float *p3, unsigned int i1, unsigned int i2, unsigned int i3)
133 {
134 mProcessed = 0;
135 mI1 = i1;
136 mI2 = i2;
137 mI3 = i3;
138
139 mP1.Set(p1);
140 mP2.Set(p2);
141 mP3.Set(p3);
142
143 mPlaneD = mNormal.ComputePlane(mP1, mP2, mP3);
144 }
145
Facing(const CTri & t)146 float Facing(const CTri &t)
147 {
148 float d = mNormal.Dot(t.mNormal);
149 return d;
150 }
151
152 // clip this line segment against this triangle.
clip(const Vector3d & start,Vector3d & end) const153 bool clip(const Vector3d &start, Vector3d &end) const
154 {
155 Vector3d sect;
156
157 bool hit = lineIntersectsTriangle(start.Ptr(), end.Ptr(), mP1.Ptr(), mP2.Ptr(), mP3.Ptr(), sect.Ptr());
158
159 if (hit)
160 {
161 end = sect;
162 }
163 return hit;
164 }
165
Concave(const Vector3d & p,float & distance,Vector3d & n) const166 bool Concave(const Vector3d &p, float &distance, Vector3d &n) const
167 {
168 n.NearestPointInTriangle(p, mP1, mP2, mP3);
169 distance = p.Distance(n);
170 return true;
171 }
172
addTri(unsigned int * indices,unsigned int i1,unsigned int i2,unsigned int i3,unsigned int & tcount) const173 void addTri(unsigned int *indices, unsigned int i1, unsigned int i2, unsigned int i3, unsigned int &tcount) const
174 {
175 indices[tcount * 3 + 0] = i1;
176 indices[tcount * 3 + 1] = i2;
177 indices[tcount * 3 + 2] = i3;
178 tcount++;
179 }
180
getVolume(ConvexDecompInterface * callback) const181 float getVolume(ConvexDecompInterface *callback) const
182 {
183 unsigned int indices[8 * 3];
184
185 unsigned int tcount = 0;
186
187 addTri(indices, 0, 1, 2, tcount);
188 addTri(indices, 3, 4, 5, tcount);
189
190 addTri(indices, 0, 3, 4, tcount);
191 addTri(indices, 0, 4, 1, tcount);
192
193 addTri(indices, 1, 4, 5, tcount);
194 addTri(indices, 1, 5, 2, tcount);
195
196 addTri(indices, 0, 3, 5, tcount);
197 addTri(indices, 0, 5, 2, tcount);
198
199 const float *vertices = mP1.Ptr();
200
201 if (callback)
202 {
203 unsigned int color = getDebugColor();
204
205 #if 0
206 Vector3d d1 = mNear1;
207 Vector3d d2 = mNear2;
208 Vector3d d3 = mNear3;
209
210 callback->ConvexDebugPoint(mP1.Ptr(),0.01f,0x00FF00);
211 callback->ConvexDebugPoint(mP2.Ptr(),0.01f,0x00FF00);
212 callback->ConvexDebugPoint(mP3.Ptr(),0.01f,0x00FF00);
213 callback->ConvexDebugPoint(d1.Ptr(),0.01f,0xFF0000);
214 callback->ConvexDebugPoint(d2.Ptr(),0.01f,0xFF0000);
215 callback->ConvexDebugPoint(d3.Ptr(),0.01f,0xFF0000);
216
217 callback->ConvexDebugTri(mP1.Ptr(), d1.Ptr(), d1.Ptr(),0x00FF00);
218 callback->ConvexDebugTri(mP2.Ptr(), d2.Ptr(), d2.Ptr(),0x00FF00);
219 callback->ConvexDebugTri(mP3.Ptr(), d3.Ptr(), d3.Ptr(),0x00FF00);
220
221 #else
222 for (unsigned int i = 0; i < tcount; i++)
223 {
224 unsigned int i1 = indices[i * 3 + 0];
225 unsigned int i2 = indices[i * 3 + 1];
226 unsigned int i3 = indices[i * 3 + 2];
227
228 const float *p1 = &vertices[i1 * 3];
229 const float *p2 = &vertices[i2 * 3];
230 const float *p3 = &vertices[i3 * 3];
231
232 callback->ConvexDebugTri(p1, p2, p3, color);
233 }
234 #endif
235 }
236
237 float v = computeMeshVolume(mP1.Ptr(), tcount, indices);
238
239 return v;
240 }
241
raySect(const Vector3d & p,const Vector3d & dir,Vector3d & sect) const242 float raySect(const Vector3d &p, const Vector3d &dir, Vector3d §) const
243 {
244 float plane[4];
245
246 plane[0] = mNormal.x;
247 plane[1] = mNormal.y;
248 plane[2] = mNormal.z;
249 plane[3] = mPlaneD;
250
251 Vector3d dest = p + dir * 100000;
252
253 intersect(p.Ptr(), dest.Ptr(), sect.Ptr(), plane);
254
255 return sect.Distance(p); // return the intersection distance.
256 }
257
planeDistance(const Vector3d & p) const258 float planeDistance(const Vector3d &p) const
259 {
260 float plane[4];
261
262 plane[0] = mNormal.x;
263 plane[1] = mNormal.y;
264 plane[2] = mNormal.z;
265 plane[3] = mPlaneD;
266
267 return DistToPt(p.Ptr(), plane);
268 }
269
samePlane(const CTri & t) const270 bool samePlane(const CTri &t) const
271 {
272 const float THRESH = 0.001f;
273 float dd = fabsf(t.mPlaneD - mPlaneD);
274 if (dd > THRESH) return false;
275 dd = fabsf(t.mNormal.x - mNormal.x);
276 if (dd > THRESH) return false;
277 dd = fabsf(t.mNormal.y - mNormal.y);
278 if (dd > THRESH) return false;
279 dd = fabsf(t.mNormal.z - mNormal.z);
280 if (dd > THRESH) return false;
281 return true;
282 }
283
hasIndex(unsigned int i) const284 bool hasIndex(unsigned int i) const
285 {
286 if (i == mI1 || i == mI2 || i == mI3) return true;
287 return false;
288 }
289
sharesEdge(const CTri & t) const290 bool sharesEdge(const CTri &t) const
291 {
292 bool ret = false;
293 unsigned int count = 0;
294
295 if (t.hasIndex(mI1)) count++;
296 if (t.hasIndex(mI2)) count++;
297 if (t.hasIndex(mI3)) count++;
298
299 if (count >= 2) ret = true;
300
301 return ret;
302 }
303
debug(unsigned int color,ConvexDecompInterface * callback)304 void debug(unsigned int color, ConvexDecompInterface *callback)
305 {
306 callback->ConvexDebugTri(mP1.Ptr(), mP2.Ptr(), mP3.Ptr(), color);
307 callback->ConvexDebugTri(mP1.Ptr(), mP1.Ptr(), mNear1.Ptr(), 0xFF0000);
308 callback->ConvexDebugTri(mP2.Ptr(), mP2.Ptr(), mNear2.Ptr(), 0xFF0000);
309 callback->ConvexDebugTri(mP2.Ptr(), mP3.Ptr(), mNear3.Ptr(), 0xFF0000);
310 callback->ConvexDebugPoint(mNear1.Ptr(), 0.01f, 0xFF0000);
311 callback->ConvexDebugPoint(mNear2.Ptr(), 0.01f, 0xFF0000);
312 callback->ConvexDebugPoint(mNear3.Ptr(), 0.01f, 0xFF0000);
313 }
314
area(void)315 float area(void)
316 {
317 float a = mConcavity * mP1.Area(mP2, mP3);
318 return a;
319 }
320
addWeighted(WpointVector & list,ConvexDecompInterface * callback)321 void addWeighted(WpointVector &list, ConvexDecompInterface *callback)
322 {
323 Wpoint p1(mP1, mC1);
324 Wpoint p2(mP2, mC2);
325 Wpoint p3(mP3, mC3);
326
327 Vector3d d1 = mNear1 - mP1;
328 Vector3d d2 = mNear2 - mP2;
329 Vector3d d3 = mNear3 - mP3;
330
331 d1 *= WSCALE;
332 d2 *= WSCALE;
333 d3 *= WSCALE;
334
335 d1 = d1 + mP1;
336 d2 = d2 + mP2;
337 d3 = d3 + mP3;
338
339 Wpoint p4(d1, mC1);
340 Wpoint p5(d2, mC2);
341 Wpoint p6(d3, mC3);
342
343 list.push_back(p1);
344 list.push_back(p2);
345 list.push_back(p3);
346
347 list.push_back(p4);
348 list.push_back(p5);
349 list.push_back(p6);
350
351 #if 0
352 callback->ConvexDebugPoint(mP1.Ptr(),0.01f,0x00FF00);
353 callback->ConvexDebugPoint(mP2.Ptr(),0.01f,0x00FF00);
354 callback->ConvexDebugPoint(mP3.Ptr(),0.01f,0x00FF00);
355 callback->ConvexDebugPoint(d1.Ptr(),0.01f,0xFF0000);
356 callback->ConvexDebugPoint(d2.Ptr(),0.01f,0xFF0000);
357 callback->ConvexDebugPoint(d3.Ptr(),0.01f,0xFF0000);
358
359 callback->ConvexDebugTri(mP1.Ptr(), d1.Ptr(), d1.Ptr(),0x00FF00);
360 callback->ConvexDebugTri(mP2.Ptr(), d2.Ptr(), d2.Ptr(),0x00FF00);
361 callback->ConvexDebugTri(mP3.Ptr(), d3.Ptr(), d3.Ptr(),0x00FF00);
362
363 Vector3d np1 = mP1 + mNormal*0.05f;
364 Vector3d np2 = mP2 + mNormal*0.05f;
365 Vector3d np3 = mP3 + mNormal*0.05f;
366
367 callback->ConvexDebugTri(mP1.Ptr(), np1.Ptr(), np1.Ptr(), 0xFF00FF );
368 callback->ConvexDebugTri(mP2.Ptr(), np2.Ptr(), np2.Ptr(), 0xFF00FF );
369 callback->ConvexDebugTri(mP3.Ptr(), np3.Ptr(), np3.Ptr(), 0xFF00FF );
370
371 callback->ConvexDebugPoint( np1.Ptr(), 0.01F, 0XFF00FF );
372 callback->ConvexDebugPoint( np2.Ptr(), 0.01F, 0XFF00FF );
373 callback->ConvexDebugPoint( np3.Ptr(), 0.01F, 0XFF00FF );
374
375 #endif
376 }
377
378 Vector3d mP1;
379 Vector3d mP2;
380 Vector3d mP3;
381 Vector3d mNear1;
382 Vector3d mNear2;
383 Vector3d mNear3;
384 Vector3d mNormal;
385 float mPlaneD;
386 float mConcavity;
387 float mC1;
388 float mC2;
389 float mC3;
390 unsigned int mI1;
391 unsigned int mI2;
392 unsigned int mI3;
393 int mProcessed; // already been added...
394 };
395
396 typedef std::vector<CTri> CTriVector;
397
featureMatch(CTri & m,const CTriVector & tris,ConvexDecompInterface * callback,const CTriVector & input_mesh)398 bool featureMatch(CTri &m, const CTriVector &tris, ConvexDecompInterface *callback, const CTriVector &input_mesh)
399 {
400 bool ret = false;
401
402 float neardot = 0.707f;
403
404 m.mConcavity = 0;
405
406 //gLog->Display("*********** FEATURE MATCH *************\r\n");
407 //gLog->Display("Plane: %0.4f,%0.4f,%0.4f %0.4f\r\n", m.mNormal.x, m.mNormal.y, m.mNormal.z, m.mPlaneD );
408 //gLog->Display("*********************************************\r\n");
409
410 CTriVector::const_iterator i;
411
412 CTri nearest;
413
414 for (i = tris.begin(); i != tris.end(); ++i)
415 {
416 const CTri &t = (*i);
417
418 //gLog->Display(" HullPlane: %0.4f,%0.4f,%0.4f %0.4f\r\n", t.mNormal.x, t.mNormal.y, t.mNormal.z, t.mPlaneD );
419
420 if (t.samePlane(m))
421 {
422 //gLog->Display("*** PLANE MATCH!!!\r\n");
423 ret = false;
424 break;
425 }
426
427 float dot = t.mNormal.Dot(m.mNormal);
428
429 if (dot > neardot)
430 {
431 float d1 = t.planeDistance(m.mP1);
432 float d2 = t.planeDistance(m.mP2);
433 float d3 = t.planeDistance(m.mP3);
434
435 if (d1 > 0.001f || d2 > 0.001f || d3 > 0.001f) // can't be near coplaner!
436 {
437 neardot = dot;
438
439 Vector3d n1, n2, n3;
440
441 t.raySect(m.mP1, m.mNormal, m.mNear1);
442 t.raySect(m.mP2, m.mNormal, m.mNear2);
443 t.raySect(m.mP3, m.mNormal, m.mNear3);
444
445 nearest = t;
446
447 ret = true;
448 }
449 }
450 }
451
452 if (ret)
453 {
454 if (0)
455 {
456 CTriVector::const_iterator i;
457 for (i = input_mesh.begin(); i != input_mesh.end(); ++i)
458 {
459 const CTri &c = (*i);
460 if (c.mI1 != m.mI1 && c.mI2 != m.mI2 && c.mI3 != m.mI3)
461 {
462 c.clip(m.mP1, m.mNear1);
463 c.clip(m.mP2, m.mNear2);
464 c.clip(m.mP3, m.mNear3);
465 }
466 }
467 }
468
469 //gLog->Display("*********************************************\r\n");
470 //gLog->Display(" HullPlaneNearest: %0.4f,%0.4f,%0.4f %0.4f\r\n", nearest.mNormal.x, nearest.mNormal.y, nearest.mNormal.z, nearest.mPlaneD );
471
472 m.mC1 = m.mP1.Distance(m.mNear1);
473 m.mC2 = m.mP2.Distance(m.mNear2);
474 m.mC3 = m.mP3.Distance(m.mNear3);
475
476 m.mConcavity = m.mC1;
477
478 if (m.mC2 > m.mConcavity) m.mConcavity = m.mC2;
479 if (m.mC3 > m.mConcavity) m.mConcavity = m.mC3;
480
481 #if 0
482 callback->ConvexDebugTri( m.mP1.Ptr(), m.mP2.Ptr(), m.mP3.Ptr(), 0x00FF00 );
483 callback->ConvexDebugTri( m.mNear1.Ptr(), m.mNear2.Ptr(), m.mNear3.Ptr(), 0xFF0000 );
484
485 callback->ConvexDebugTri( m.mP1.Ptr(), m.mP1.Ptr(), m.mNear1.Ptr(), 0xFFFF00 );
486 callback->ConvexDebugTri( m.mP2.Ptr(), m.mP2.Ptr(), m.mNear2.Ptr(), 0xFFFF00 );
487 callback->ConvexDebugTri( m.mP3.Ptr(), m.mP3.Ptr(), m.mNear3.Ptr(), 0xFFFF00 );
488 #endif
489 }
490 else
491 {
492 //gLog->Display("No match\r\n");
493 }
494
495 //gLog->Display("*********************************************\r\n");
496 return ret;
497 }
498
isFeatureTri(CTri & t,CTriVector & flist,float fc,ConvexDecompInterface * callback,unsigned int color)499 bool isFeatureTri(CTri &t, CTriVector &flist, float fc, ConvexDecompInterface *callback, unsigned int color)
500 {
501 bool ret = false;
502
503 if (t.mProcessed == 0) // if not already processed
504 {
505 float c = t.mConcavity / fc; // must be within 80% of the concavity of the parent.
506
507 if (c > 0.85f)
508 {
509 // see if this triangle is a 'feature' triangle. Meaning it shares an
510 // edge with any existing feature triangle and is within roughly the same
511 // concavity of the parent.
512 if (flist.size())
513 {
514 CTriVector::iterator i;
515 for (i = flist.begin(); i != flist.end(); ++i)
516 {
517 CTri &ftri = (*i);
518 if (ftri.sharesEdge(t))
519 {
520 t.mProcessed = 2; // it is now part of a feature.
521 flist.push_back(t); // add it to the feature list.
522 // callback->ConvexDebugTri( t.mP1.Ptr(), t.mP2.Ptr(),t.mP3.Ptr(), color );
523 ret = true;
524 break;
525 }
526 }
527 }
528 else
529 {
530 t.mProcessed = 2;
531 flist.push_back(t); // add it to the feature list.
532 // callback->ConvexDebugTri( t.mP1.Ptr(), t.mP2.Ptr(),t.mP3.Ptr(), color );
533 ret = true;
534 }
535 }
536 else
537 {
538 t.mProcessed = 1; // eliminated for this feature, but might be valid for the next one..
539 }
540 }
541 return ret;
542 }
543
computeConcavity(unsigned int vcount,const float * vertices,unsigned int tcount,const unsigned int * indices,ConvexDecompInterface * callback,float * plane,float & volume)544 float computeConcavity(unsigned int vcount,
545 const float *vertices,
546 unsigned int tcount,
547 const unsigned int *indices,
548 ConvexDecompInterface *callback,
549 float *plane, // plane equation to split on
550 float &volume)
551 {
552 float cret = 0;
553 volume = 1;
554
555 HullResult result;
556 HullLibrary hl;
557 HullDesc desc;
558
559 desc.mMaxFaces = 256;
560 desc.mMaxVertices = 256;
561 desc.SetHullFlag(QF_TRIANGLES);
562
563 desc.mVcount = vcount;
564 desc.mVertices = vertices;
565 desc.mVertexStride = sizeof(float) * 3;
566
567 HullError ret = hl.CreateConvexHull(desc, result);
568
569 if (ret == QE_OK)
570 {
571 #if 0
572 float bmin[3];
573 float bmax[3];
574
575 float dx = bmax[0] - bmin[0];
576 float dy = bmax[1] - bmin[1];
577 float dz = bmax[2] - bmin[2];
578
579 Vector3d center;
580
581 center.x = bmin[0] + dx*0.5f;
582 center.y = bmin[1] + dy*0.5f;
583 center.z = bmin[2] + dz*0.5f;
584 #endif
585
586 volume = computeMeshVolume2(result.mOutputVertices, result.mNumFaces, result.mIndices);
587
588 #if 1
589 // ok..now..for each triangle on the original mesh..
590 // we extrude the points to the nearest point on the hull.
591 const unsigned int *source = result.mIndices;
592
593 CTriVector tris;
594
595 for (unsigned int i = 0; i < result.mNumFaces; i++)
596 {
597 unsigned int i1 = *source++;
598 unsigned int i2 = *source++;
599 unsigned int i3 = *source++;
600
601 const float *p1 = &result.mOutputVertices[i1 * 3];
602 const float *p2 = &result.mOutputVertices[i2 * 3];
603 const float *p3 = &result.mOutputVertices[i3 * 3];
604
605 // callback->ConvexDebugTri(p1,p2,p3,0xFFFFFF);
606
607 CTri t(p1, p2, p3, i1, i2, i3); //
608 tris.push_back(t);
609 }
610
611 // we have not pre-computed the plane equation for each triangle in the convex hull..
612
613 float totalVolume = 0;
614
615 CTriVector ftris; // 'feature' triangles.
616
617 const unsigned int *src = indices;
618
619 float maxc = 0;
620
621 if (1)
622 {
623 CTriVector input_mesh;
624 if (1)
625 {
626 const unsigned int *src = indices;
627 for (unsigned int i = 0; i < tcount; i++)
628 {
629 unsigned int i1 = *src++;
630 unsigned int i2 = *src++;
631 unsigned int i3 = *src++;
632
633 const float *p1 = &vertices[i1 * 3];
634 const float *p2 = &vertices[i2 * 3];
635 const float *p3 = &vertices[i3 * 3];
636
637 CTri t(p1, p2, p3, i1, i2, i3);
638 input_mesh.push_back(t);
639 }
640 }
641
642 CTri maxctri;
643
644 for (unsigned int i = 0; i < tcount; i++)
645 {
646 unsigned int i1 = *src++;
647 unsigned int i2 = *src++;
648 unsigned int i3 = *src++;
649
650 const float *p1 = &vertices[i1 * 3];
651 const float *p2 = &vertices[i2 * 3];
652 const float *p3 = &vertices[i3 * 3];
653
654 CTri t(p1, p2, p3, i1, i2, i3);
655
656 featureMatch(t, tris, callback, input_mesh);
657
658 if (t.mConcavity > CONCAVE_THRESH)
659 {
660 if (t.mConcavity > maxc)
661 {
662 maxc = t.mConcavity;
663 maxctri = t;
664 }
665
666 float v = t.getVolume(0);
667 totalVolume += v;
668 ftris.push_back(t);
669 }
670 }
671 }
672
673 #if 0
674 if ( ftris.size() && 0 )
675 {
676
677 // ok..now we extract the triangles which form the maximum concavity.
678 CTriVector major_feature;
679 float maxarea = 0;
680
681 while ( maxc > CONCAVE_THRESH )
682 {
683
684 unsigned int color = getDebugColor(); //
685
686 CTriVector flist;
687
688 bool found;
689
690 float totalarea = 0;
691
692 do
693 {
694 found = false;
695 CTriVector::iterator i;
696 for (i=ftris.begin(); i!=ftris.end(); ++i)
697 {
698 CTri &t = (*i);
699 if ( isFeatureTri(t,flist,maxc,callback,color) )
700 {
701 found = true;
702 totalarea+=t.area();
703 }
704 }
705 } while ( found );
706
707
708 if ( totalarea > maxarea )
709 {
710 major_feature = flist;
711 maxarea = totalarea;
712 }
713
714 maxc = 0;
715
716 for (unsigned int i=0; i<ftris.size(); i++)
717 {
718 CTri &t = ftris[i];
719 if ( t.mProcessed != 2 )
720 {
721 t.mProcessed = 0;
722 if ( t.mConcavity > maxc )
723 {
724 maxc = t.mConcavity;
725 }
726 }
727 }
728
729 }
730
731 unsigned int color = getDebugColor();
732
733 WpointVector list;
734 for (unsigned int i=0; i<major_feature.size(); ++i)
735 {
736 major_feature[i].addWeighted(list,callback);
737 major_feature[i].debug(color,callback);
738 }
739
740 getBestFitPlane( list.size(), &list[0].mPoint.x, sizeof(Wpoint), &list[0].mWeight, sizeof(Wpoint), plane );
741
742 computeSplitPlane( vcount, vertices, tcount, indices, callback, plane );
743
744
745 }
746 else
747 {
748 computeSplitPlane( vcount, vertices, tcount, indices, callback, plane );
749 }
750 #endif
751
752 cret = totalVolume;
753
754 hl.ReleaseResult(result);
755 }
756 #endif
757
758 return cret;
759 }
760
761 } // namespace ConvexDecomposition
762