$search
00001 #include <stdio.h> 00002 #include <stdlib.h> 00003 #include <string.h> 00004 #include <assert.h> 00005 00062 #include <vector> 00063 00064 #include "concavity.h" 00065 #include "raytri.h" 00066 #include "bestfit.h" 00067 #include "cd_hull.h" 00068 #include "meshvolume.h" 00069 #include "cd_vector.h" 00070 #include "splitplane.h" 00071 #include "ConvexDecomposition.h" 00072 00073 00074 #define WSCALE 4 00075 #define CONCAVE_THRESH 0.05f 00076 00077 namespace ConvexDecomposition 00078 { 00079 00080 unsigned int getDebugColor(void) 00081 { 00082 static unsigned int colors[8] = 00083 { 00084 0xFF0000, 00085 0x00FF00, 00086 0x0000FF, 00087 0xFFFF00, 00088 0x00FFFF, 00089 0xFF00FF, 00090 0xFFFFFF, 00091 0xFF8040 00092 }; 00093 00094 static int count = 0; 00095 00096 count++; 00097 00098 if ( count == 8 ) count = 0; 00099 00100 assert( count >= 0 && count < 8 ); 00101 00102 unsigned int color = colors[count]; 00103 00104 return color; 00105 00106 } 00107 00108 class Wpoint 00109 { 00110 public: 00111 Wpoint(const Vector3d<double> &p,double w) 00112 { 00113 mPoint = p; 00114 mWeight = w; 00115 } 00116 00117 Vector3d<double> mPoint; 00118 double mWeight; 00119 }; 00120 00121 typedef std::vector< Wpoint > WpointVector; 00122 00123 00124 static inline double DistToPt(const double *p,const double *plane) 00125 { 00126 double x = p[0]; 00127 double y = p[1]; 00128 double z = p[2]; 00129 double d = x*plane[0] + y*plane[1] + z*plane[2] + plane[3]; 00130 return d; 00131 } 00132 00133 00134 static void intersect(const double *p1,const double *p2,double *split,const double *plane) 00135 { 00136 00137 double dp1 = DistToPt(p1,plane); 00138 double dp2 = DistToPt(p2,plane); 00139 00140 double dir[3]; 00141 00142 dir[0] = p2[0] - p1[0]; 00143 dir[1] = p2[1] - p1[1]; 00144 dir[2] = p2[2] - p1[2]; 00145 00146 double dot1 = dir[0]*plane[0] + dir[1]*plane[1] + dir[2]*plane[2]; 00147 double dot2 = dp1 - plane[3]; 00148 00149 double t = -(plane[3] + dot2 ) / dot1; 00150 00151 split[0] = (dir[0]*t)+p1[0]; 00152 split[1] = (dir[1]*t)+p1[1]; 00153 split[2] = (dir[2]*t)+p1[2]; 00154 00155 } 00156 00157 00158 class CTri 00159 { 00160 public: 00161 CTri(void) { }; 00162 00163 CTri(const double *p1,const double *p2,const double *p3,unsigned int i1,unsigned int i2,unsigned int i3) 00164 { 00165 mProcessed = 0; 00166 mI1 = i1; 00167 mI2 = i2; 00168 mI3 = i3; 00169 00170 mP1.Set(p1); 00171 mP2.Set(p2); 00172 mP3.Set(p3); 00173 00174 mPlaneD = mNormal.ComputePlane(mP1,mP2,mP3); 00175 } 00176 00177 double Facing(const CTri &t) 00178 { 00179 double d = mNormal.Dot(t.mNormal); 00180 return d; 00181 } 00182 00183 // clip this line segment against this triangle. 00184 bool clip(const Vector3d<double> &start,Vector3d<double> &end) const 00185 { 00186 Vector3d<double> sect; 00187 00188 bool hit = lineIntersectsTriangle(start.Ptr(), end.Ptr(), mP1.Ptr(), mP2.Ptr(), mP3.Ptr(), sect.Ptr() ); 00189 00190 if ( hit ) 00191 { 00192 end = sect; 00193 } 00194 return hit; 00195 } 00196 00197 bool Concave(const Vector3d<double> &p,double &distance,Vector3d<double> &n) const 00198 { 00199 n.NearestPointInTriangle(p,mP1,mP2,mP3); 00200 distance = p.Distance(n); 00201 return true; 00202 } 00203 00204 void addTri(unsigned int *indices,unsigned int i1,unsigned int i2,unsigned int i3,unsigned int &tcount) const 00205 { 00206 indices[tcount*3+0] = i1; 00207 indices[tcount*3+1] = i2; 00208 indices[tcount*3+2] = i3; 00209 tcount++; 00210 } 00211 00212 double getVolume(ConvexDecompInterface *callback) const 00213 { 00214 unsigned int indices[8*3]; 00215 00216 00217 unsigned int tcount = 0; 00218 00219 addTri(indices,0,1,2,tcount); 00220 addTri(indices,3,4,5,tcount); 00221 00222 addTri(indices,0,3,4,tcount); 00223 addTri(indices,0,4,1,tcount); 00224 00225 addTri(indices,1,4,5,tcount); 00226 addTri(indices,1,5,2,tcount); 00227 00228 addTri(indices,0,3,5,tcount); 00229 addTri(indices,0,5,2,tcount); 00230 00231 const double *vertices = mP1.Ptr(); 00232 00233 if ( callback ) 00234 { 00235 unsigned int color = getDebugColor(); 00236 00237 #if 0 00238 Vector3d<double> d1 = mNear1; 00239 Vector3d<double> d2 = mNear2; 00240 Vector3d<double> d3 = mNear3; 00241 00242 callback->ConvexDebugPoint(mP1.Ptr(),0.01f,0x00FF00); 00243 callback->ConvexDebugPoint(mP2.Ptr(),0.01f,0x00FF00); 00244 callback->ConvexDebugPoint(mP3.Ptr(),0.01f,0x00FF00); 00245 callback->ConvexDebugPoint(d1.Ptr(),0.01f,0xFF0000); 00246 callback->ConvexDebugPoint(d2.Ptr(),0.01f,0xFF0000); 00247 callback->ConvexDebugPoint(d3.Ptr(),0.01f,0xFF0000); 00248 00249 callback->ConvexDebugTri(mP1.Ptr(), d1.Ptr(), d1.Ptr(),0x00FF00); 00250 callback->ConvexDebugTri(mP2.Ptr(), d2.Ptr(), d2.Ptr(),0x00FF00); 00251 callback->ConvexDebugTri(mP3.Ptr(), d3.Ptr(), d3.Ptr(),0x00FF00); 00252 00253 #else 00254 for (unsigned int i=0; i<tcount; i++) 00255 { 00256 unsigned int i1 = indices[i*3+0]; 00257 unsigned int i2 = indices[i*3+1]; 00258 unsigned int i3 = indices[i*3+2]; 00259 00260 const double *p1 = &vertices[ i1*3 ]; 00261 const double *p2 = &vertices[ i2*3 ]; 00262 const double *p3 = &vertices[ i3*3 ]; 00263 00264 callback->ConvexDebugTri(p1,p2,p3,color); 00265 00266 } 00267 #endif 00268 } 00269 00270 double v = computeMeshVolume(mP1.Ptr(), tcount, indices ); 00271 00272 return v; 00273 00274 } 00275 00276 double raySect(const Vector3d<double> &p,const Vector3d<double> &dir,Vector3d<double> §) const 00277 { 00278 double plane[4]; 00279 00280 plane[0] = mNormal.x; 00281 plane[1] = mNormal.y; 00282 plane[2] = mNormal.z; 00283 plane[3] = mPlaneD; 00284 00285 Vector3d<double> dest = p+dir*100000; 00286 00287 intersect( p.Ptr(), dest.Ptr(), sect.Ptr(), plane ); 00288 00289 return sect.Distance(p); // return the intersection distance. 00290 00291 } 00292 00293 double planeDistance(const Vector3d<double> &p) const 00294 { 00295 double plane[4]; 00296 00297 plane[0] = mNormal.x; 00298 plane[1] = mNormal.y; 00299 plane[2] = mNormal.z; 00300 plane[3] = mPlaneD; 00301 00302 return DistToPt( p.Ptr(), plane ); 00303 00304 } 00305 00306 bool samePlane(const CTri &t) const 00307 { 00308 const double THRESH = 0.001f; 00309 double dd = fabs( t.mPlaneD - mPlaneD ); 00310 if ( dd > THRESH ) return false; 00311 dd = fabs( t.mNormal.x - mNormal.x ); 00312 if ( dd > THRESH ) return false; 00313 dd = fabs( t.mNormal.y - mNormal.y ); 00314 if ( dd > THRESH ) return false; 00315 dd = fabs( t.mNormal.z - mNormal.z ); 00316 if ( dd > THRESH ) return false; 00317 return true; 00318 } 00319 00320 bool hasIndex(unsigned int i) const 00321 { 00322 if ( i == mI1 || i == mI2 || i == mI3 ) return true; 00323 return false; 00324 } 00325 00326 bool sharesEdge(const CTri &t) const 00327 { 00328 bool ret = false; 00329 unsigned int count = 0; 00330 00331 if ( t.hasIndex(mI1) ) count++; 00332 if ( t.hasIndex(mI2) ) count++; 00333 if ( t.hasIndex(mI3) ) count++; 00334 00335 if ( count >= 2 ) ret = true; 00336 00337 return ret; 00338 } 00339 00340 void debug(unsigned int color,ConvexDecompInterface *callback) 00341 { 00342 callback->ConvexDebugTri( mP1.Ptr(), mP2.Ptr(), mP3.Ptr(), color ); 00343 callback->ConvexDebugTri( mP1.Ptr(), mP1.Ptr(), mNear1.Ptr(), 0xFF0000 ); 00344 callback->ConvexDebugTri( mP2.Ptr(), mP2.Ptr(), mNear2.Ptr(), 0xFF0000 ); 00345 callback->ConvexDebugTri( mP2.Ptr(), mP3.Ptr(), mNear3.Ptr(), 0xFF0000 ); 00346 callback->ConvexDebugPoint( mNear1.Ptr(), 0.01f, 0xFF0000 ); 00347 callback->ConvexDebugPoint( mNear2.Ptr(), 0.01f, 0xFF0000 ); 00348 callback->ConvexDebugPoint( mNear3.Ptr(), 0.01f, 0xFF0000 ); 00349 } 00350 00351 double area(void) 00352 { 00353 double a = mConcavity*mP1.Area(mP2,mP3); 00354 return a; 00355 } 00356 00357 void addWeighted(WpointVector &list,ConvexDecompInterface *callback) 00358 { 00359 00360 Wpoint p1(mP1,mC1); 00361 Wpoint p2(mP2,mC2); 00362 Wpoint p3(mP3,mC3); 00363 00364 Vector3d<double> d1 = mNear1 - mP1; 00365 Vector3d<double> d2 = mNear2 - mP2; 00366 Vector3d<double> d3 = mNear3 - mP3; 00367 00368 d1*=WSCALE; 00369 d2*=WSCALE; 00370 d3*=WSCALE; 00371 00372 d1 = d1 + mP1; 00373 d2 = d2 + mP2; 00374 d3 = d3 + mP3; 00375 00376 Wpoint p4(d1,mC1); 00377 Wpoint p5(d2,mC2); 00378 Wpoint p6(d3,mC3); 00379 00380 list.push_back(p1); 00381 list.push_back(p2); 00382 list.push_back(p3); 00383 00384 list.push_back(p4); 00385 list.push_back(p5); 00386 list.push_back(p6); 00387 00388 #if 0 00389 callback->ConvexDebugPoint(mP1.Ptr(),0.01f,0x00FF00); 00390 callback->ConvexDebugPoint(mP2.Ptr(),0.01f,0x00FF00); 00391 callback->ConvexDebugPoint(mP3.Ptr(),0.01f,0x00FF00); 00392 callback->ConvexDebugPoint(d1.Ptr(),0.01f,0xFF0000); 00393 callback->ConvexDebugPoint(d2.Ptr(),0.01f,0xFF0000); 00394 callback->ConvexDebugPoint(d3.Ptr(),0.01f,0xFF0000); 00395 00396 callback->ConvexDebugTri(mP1.Ptr(), d1.Ptr(), d1.Ptr(),0x00FF00); 00397 callback->ConvexDebugTri(mP2.Ptr(), d2.Ptr(), d2.Ptr(),0x00FF00); 00398 callback->ConvexDebugTri(mP3.Ptr(), d3.Ptr(), d3.Ptr(),0x00FF00); 00399 00400 Vector3d<double> np1 = mP1 + mNormal*0.05f; 00401 Vector3d<double> np2 = mP2 + mNormal*0.05f; 00402 Vector3d<double> np3 = mP3 + mNormal*0.05f; 00403 00404 callback->ConvexDebugTri(mP1.Ptr(), np1.Ptr(), np1.Ptr(), 0xFF00FF ); 00405 callback->ConvexDebugTri(mP2.Ptr(), np2.Ptr(), np2.Ptr(), 0xFF00FF ); 00406 callback->ConvexDebugTri(mP3.Ptr(), np3.Ptr(), np3.Ptr(), 0xFF00FF ); 00407 00408 callback->ConvexDebugPoint( np1.Ptr(), 0.01F, 0XFF00FF ); 00409 callback->ConvexDebugPoint( np2.Ptr(), 0.01F, 0XFF00FF ); 00410 callback->ConvexDebugPoint( np3.Ptr(), 0.01F, 0XFF00FF ); 00411 00412 #endif 00413 00414 00415 00416 } 00417 00418 Vector3d<double> mP1; 00419 Vector3d<double> mP2; 00420 Vector3d<double> mP3; 00421 Vector3d<double> mNear1; 00422 Vector3d<double> mNear2; 00423 Vector3d<double> mNear3; 00424 Vector3d<double> mNormal; 00425 double mPlaneD; 00426 double mConcavity; 00427 double mC1; 00428 double mC2; 00429 double mC3; 00430 unsigned int mI1; 00431 unsigned int mI2; 00432 unsigned int mI3; 00433 int mProcessed; // already been added... 00434 }; 00435 00436 typedef std::vector< CTri > CTriVector; 00437 00438 bool featureMatch(CTri &m,const CTriVector &tris,ConvexDecompInterface *callback,const CTriVector &input_mesh) 00439 { 00440 00441 bool ret = false; 00442 00443 double neardot = 0.707f; 00444 00445 m.mConcavity = 0; 00446 00447 //gLog->Display("*********** FEATURE MATCH *************\r\n"); 00448 //gLog->Display("Plane: %0.4f,%0.4f,%0.4f %0.4f\r\n", m.mNormal.x, m.mNormal.y, m.mNormal.z, m.mPlaneD ); 00449 //gLog->Display("*********************************************\r\n"); 00450 00451 CTriVector::const_iterator i; 00452 00453 CTri nearest; 00454 00455 double near[3] = { 1e9, 1e9, 1e9 }; 00456 00457 for (i=tris.begin(); i!=tris.end(); ++i) 00458 { 00459 const CTri &t = (*i); 00460 00461 00462 //gLog->Display(" HullPlane: %0.4f,%0.4f,%0.4f %0.4f\r\n", t.mNormal.x, t.mNormal.y, t.mNormal.z, t.mPlaneD ); 00463 00464 if ( t.samePlane(m) ) 00465 { 00466 //gLog->Display("*** PLANE MATCH!!!\r\n"); 00467 ret = false; 00468 break; 00469 } 00470 00471 double dot = t.mNormal.Dot(m.mNormal); 00472 00473 if ( dot > neardot ) 00474 { 00475 00476 double d1 = t.planeDistance( m.mP1 ); 00477 double d2 = t.planeDistance( m.mP2 ); 00478 double d3 = t.planeDistance( m.mP3 ); 00479 00480 if ( d1 > 0.001f || d2 > 0.001f || d3 > 0.001f ) // can't be near coplaner! 00481 { 00482 00483 neardot = dot; 00484 00485 Vector3d<double> n1,n2,n3; 00486 00487 t.raySect( m.mP1, m.mNormal, m.mNear1 ); 00488 t.raySect( m.mP2, m.mNormal, m.mNear2 ); 00489 t.raySect( m.mP3, m.mNormal, m.mNear3 ); 00490 00491 nearest = t; 00492 00493 ret = true; 00494 } 00495 00496 } 00497 } 00498 00499 if ( ret ) 00500 { 00501 if ( 0 ) 00502 { 00503 CTriVector::const_iterator i; 00504 for (i=input_mesh.begin(); i!=input_mesh.end(); ++i) 00505 { 00506 const CTri &c = (*i); 00507 if ( c.mI1 != m.mI1 && c.mI2 != m.mI2 && c.mI3 != m.mI3 ) 00508 { 00509 c.clip( m.mP1, m.mNear1 ); 00510 c.clip( m.mP2, m.mNear2 ); 00511 c.clip( m.mP3, m.mNear3 ); 00512 } 00513 } 00514 } 00515 00516 //gLog->Display("*********************************************\r\n"); 00517 //gLog->Display(" HullPlaneNearest: %0.4f,%0.4f,%0.4f %0.4f\r\n", nearest.mNormal.x, nearest.mNormal.y, nearest.mNormal.z, nearest.mPlaneD ); 00518 00519 m.mC1 = m.mP1.Distance( m.mNear1 ); 00520 m.mC2 = m.mP2.Distance( m.mNear2 ); 00521 m.mC3 = m.mP3.Distance( m.mNear3 ); 00522 00523 m.mConcavity = m.mC1; 00524 00525 if ( m.mC2 > m.mConcavity ) m.mConcavity = m.mC2; 00526 if ( m.mC3 > m.mConcavity ) m.mConcavity = m.mC3; 00527 00528 #if 0 00529 callback->ConvexDebugTri( m.mP1.Ptr(), m.mP2.Ptr(), m.mP3.Ptr(), 0x00FF00 ); 00530 callback->ConvexDebugTri( m.mNear1.Ptr(), m.mNear2.Ptr(), m.mNear3.Ptr(), 0xFF0000 ); 00531 00532 callback->ConvexDebugTri( m.mP1.Ptr(), m.mP1.Ptr(), m.mNear1.Ptr(), 0xFFFF00 ); 00533 callback->ConvexDebugTri( m.mP2.Ptr(), m.mP2.Ptr(), m.mNear2.Ptr(), 0xFFFF00 ); 00534 callback->ConvexDebugTri( m.mP3.Ptr(), m.mP3.Ptr(), m.mNear3.Ptr(), 0xFFFF00 ); 00535 #endif 00536 00537 } 00538 else 00539 { 00540 //gLog->Display("No match\r\n"); 00541 } 00542 00543 //gLog->Display("*********************************************\r\n"); 00544 return ret; 00545 } 00546 00547 bool isFeatureTri(CTri &t,CTriVector &flist,double fc,ConvexDecompInterface *callback,unsigned int color) 00548 { 00549 bool ret = false; 00550 00551 if ( t.mProcessed == 0 ) // if not already processed 00552 { 00553 00554 double c = t.mConcavity / fc; // must be within 80% of the concavity of the parent. 00555 00556 if ( c > 0.85f ) 00557 { 00558 // see if this triangle is a 'feature' triangle. Meaning it shares an 00559 // edge with any existing feature triangle and is within roughly the same 00560 // concavity of the parent. 00561 if ( flist.size() ) 00562 { 00563 CTriVector::iterator i; 00564 for (i=flist.begin(); i!=flist.end(); ++i) 00565 { 00566 CTri &ftri = (*i); 00567 if ( ftri.sharesEdge(t) ) 00568 { 00569 t.mProcessed = 2; // it is now part of a feature. 00570 flist.push_back(t); // add it to the feature list. 00571 // callback->ConvexDebugTri( t.mP1.Ptr(), t.mP2.Ptr(),t.mP3.Ptr(), color ); 00572 ret = true; 00573 break; 00574 } 00575 } 00576 } 00577 else 00578 { 00579 t.mProcessed = 2; 00580 flist.push_back(t); // add it to the feature list. 00581 // callback->ConvexDebugTri( t.mP1.Ptr(), t.mP2.Ptr(),t.mP3.Ptr(), color ); 00582 ret = true; 00583 } 00584 } 00585 else 00586 { 00587 t.mProcessed = 1; // eliminated for this feature, but might be valid for the next one.. 00588 } 00589 00590 } 00591 return ret; 00592 } 00593 00594 double computeConcavity(unsigned int vcount, 00595 const double *vertices, 00596 unsigned int tcount, 00597 const unsigned int *indices, 00598 ConvexDecompInterface *callback, 00599 double *plane, // plane equation to split on 00600 double &volume) 00601 { 00602 00603 00604 double cret = 0; 00605 volume = 1; 00606 00607 HullResult result; 00608 HullLibrary hl; 00609 HullDesc desc; 00610 00611 desc.mMaxVertices = 256; 00612 desc.SetHullFlag(QF_TRIANGLES); 00613 00614 00615 desc.mVcount = vcount; 00616 desc.mVertices = vertices; 00617 desc.mVertexStride = sizeof(double)*3; 00618 00619 HullError ret = hl.CreateConvexHull(desc,result); 00620 00621 if ( ret == QE_OK ) 00622 { 00623 00624 double bmin[3]; 00625 double bmax[3]; 00626 00627 double diagonal = getBoundingRegion( result.mNumOutputVertices, result.mOutputVertices, sizeof(double)*3, bmin, bmax ); 00628 00629 double dx = bmax[0] - bmin[0]; 00630 double dy = bmax[1] - bmin[1]; 00631 double dz = bmax[2] - bmin[2]; 00632 00633 Vector3d<double> center; 00634 00635 center.x = bmin[0] + dx*0.5f; 00636 center.y = bmin[1] + dy*0.5f; 00637 center.z = bmin[2] + dz*0.5f; 00638 00639 double boundVolume = dx*dy*dz; 00640 00641 volume = computeMeshVolume2( result.mOutputVertices, result.mNumFaces, result.mIndices ); 00642 00643 #if 1 00644 // ok..now..for each triangle on the original mesh.. 00645 // we extrude the points to the nearest point on the hull. 00646 const unsigned int *source = result.mIndices; 00647 00648 CTriVector tris; 00649 00650 for (unsigned int i=0; i<result.mNumFaces; i++) 00651 { 00652 unsigned int i1 = *source++; 00653 unsigned int i2 = *source++; 00654 unsigned int i3 = *source++; 00655 00656 const double *p1 = &result.mOutputVertices[i1*3]; 00657 const double *p2 = &result.mOutputVertices[i2*3]; 00658 const double *p3 = &result.mOutputVertices[i3*3]; 00659 00660 // callback->ConvexDebugTri(p1,p2,p3,0xFFFFFF); 00661 00662 CTri t(p1,p2,p3,i1,i2,i3); // 00663 tris.push_back(t); 00664 } 00665 00666 // we have not pre-computed the plane equation for each triangle in the convex hull.. 00667 00668 double totalVolume = 0; 00669 00670 CTriVector ftris; // 'feature' triangles. 00671 00672 const unsigned int *src = indices; 00673 00674 00675 double maxc=0; 00676 00677 00678 if ( 1 ) 00679 { 00680 CTriVector input_mesh; 00681 if ( 1 ) 00682 { 00683 const unsigned int *src = indices; 00684 for (unsigned int i=0; i<tcount; i++) 00685 { 00686 00687 unsigned int i1 = *src++; 00688 unsigned int i2 = *src++; 00689 unsigned int i3 = *src++; 00690 00691 const double *p1 = &vertices[i1*3]; 00692 const double *p2 = &vertices[i2*3]; 00693 const double *p3 = &vertices[i3*3]; 00694 00695 CTri t(p1,p2,p3,i1,i2,i3); 00696 input_mesh.push_back(t); 00697 } 00698 } 00699 00700 CTri maxctri; 00701 00702 for (unsigned int i=0; i<tcount; i++) 00703 { 00704 00705 unsigned int i1 = *src++; 00706 unsigned int i2 = *src++; 00707 unsigned int i3 = *src++; 00708 00709 const double *p1 = &vertices[i1*3]; 00710 const double *p2 = &vertices[i2*3]; 00711 const double *p3 = &vertices[i3*3]; 00712 00713 CTri t(p1,p2,p3,i1,i2,i3); 00714 00715 featureMatch(t, tris, callback, input_mesh ); 00716 00717 if ( t.mConcavity > CONCAVE_THRESH ) 00718 { 00719 00720 if ( t.mConcavity > maxc ) 00721 { 00722 maxc = t.mConcavity; 00723 maxctri = t; 00724 } 00725 00726 double v = t.getVolume(0); 00727 totalVolume+=v; 00728 ftris.push_back(t); 00729 } 00730 00731 } 00732 } 00733 00734 if ( ftris.size() && 0 ) 00735 { 00736 00737 // ok..now we extract the triangles which form the maximum concavity. 00738 CTriVector major_feature; 00739 double maxarea = 0; 00740 00741 while ( maxc > CONCAVE_THRESH ) 00742 { 00743 00744 unsigned int color = getDebugColor(); // 00745 00746 CTriVector flist; 00747 00748 bool found; 00749 00750 double totalarea = 0; 00751 00752 do 00753 { 00754 found = false; 00755 CTriVector::iterator i; 00756 for (i=ftris.begin(); i!=ftris.end(); ++i) 00757 { 00758 CTri &t = (*i); 00759 if ( isFeatureTri(t,flist,maxc,callback,color) ) 00760 { 00761 found = true; 00762 totalarea+=t.area(); 00763 } 00764 } 00765 } while ( found ); 00766 00767 00768 if ( totalarea > maxarea ) 00769 { 00770 major_feature = flist; 00771 maxarea = totalarea; 00772 } 00773 00774 maxc = 0; 00775 00776 for (unsigned int i=0; i<ftris.size(); i++) 00777 { 00778 CTri &t = ftris[i]; 00779 if ( t.mProcessed != 2 ) 00780 { 00781 t.mProcessed = 0; 00782 if ( t.mConcavity > maxc ) 00783 { 00784 maxc = t.mConcavity; 00785 } 00786 } 00787 } 00788 } 00789 00790 unsigned int color = getDebugColor(); 00791 00792 WpointVector list; 00793 for (unsigned int i=0; i<major_feature.size(); ++i) 00794 { 00795 major_feature[i].addWeighted(list,callback); 00796 major_feature[i].debug(color,callback); 00797 } 00798 00799 getBestFitPlane( list.size(), &list[0].mPoint.x, sizeof(Wpoint), &list[0].mWeight, sizeof(Wpoint), plane ); 00800 00801 computeSplitPlane( vcount, vertices, tcount, indices, callback, plane ); 00802 00803 00804 } 00805 else 00806 { 00807 computeSplitPlane( vcount, vertices, tcount, indices, callback, plane ); 00808 } 00809 #endif 00810 00811 cret = totalVolume; 00812 00813 hl.ReleaseResult(result); 00814 } 00815 00816 00817 return cret; 00818 } 00819 00820 00821 };