00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include <iostream>
00026 #include <list>
00027 #include <map>
00028 #include <sstream>
00029 #include <string>
00030 #include <vector>
00031
00032 #include <osg/io_utils>
00033
00034 #include "../common/datastructures/WUnionFind.h"
00035 #include "WTriangleMesh.h"
00036
00037
00038 boost::shared_ptr< WPrototyped > WTriangleMesh::m_prototype = boost::shared_ptr< WPrototyped >();
00039
00040 boost::shared_ptr< WPrototyped > WTriangleMesh::getPrototype()
00041 {
00042 if( !m_prototype )
00043 {
00044 m_prototype = boost::shared_ptr< WPrototyped >( new WTriangleMesh( 0, 0 ) );
00045 }
00046 return m_prototype;
00047 }
00048
00049
00050
00051
00052 WTriangleMesh::WTriangleMesh( size_t vertNum, size_t triangleNum )
00053 : m_countVerts( 0 ),
00054 m_countTriangles( 0 ),
00055 m_meshDirty( true ),
00056 m_neighborsCalculated( false )
00057 {
00058 m_verts = osg::ref_ptr< osg::Vec3Array >( new osg::Vec3Array( vertNum ) );
00059 m_textureCoordinates = osg::ref_ptr< osg::Vec3Array >( new osg::Vec3Array( vertNum ) );
00060 m_vertNormals = osg::ref_ptr< osg::Vec3Array >( new osg::Vec3Array( vertNum ) );
00061 m_vertColors = osg::ref_ptr< osg::Vec4Array >( new osg::Vec4Array( vertNum ) );
00062
00063 m_triangles.resize( triangleNum * 3 );
00064 m_triangleNormals = osg::ref_ptr< osg::Vec3Array >( new osg::Vec3Array( triangleNum ) );
00065 m_triangleColors = osg::ref_ptr< osg::Vec4Array >( new osg::Vec4Array( triangleNum ) );
00066 }
00067
00068 WTriangleMesh::WTriangleMesh( osg::ref_ptr< osg::Vec3Array > vertices, const std::vector< size_t >& triangles )
00069 : m_countVerts( vertices->size() ),
00070 m_countTriangles( triangles.size() / 3 ),
00071 m_meshDirty( true ),
00072 m_neighborsCalculated( false ),
00073 m_verts( vertices ),
00074 m_textureCoordinates( new osg::Vec3Array( vertices->size() ) ),
00075 m_vertNormals( new osg::Vec3Array( vertices->size() ) ),
00076 m_vertColors( new osg::Vec4Array( vertices->size() ) ),
00077 m_triangles( triangles ),
00078 m_triangleNormals( new osg::Vec3Array( triangles.size() / 3 ) ),
00079 m_triangleColors( new osg::Vec4Array( triangles.size() / 3 ) )
00080 {
00081 WAssert( triangles.size() % 3 == 0, "Invalid triangle vector, having an invalid size (not divideable by 3)" );
00082 }
00083
00084 WTriangleMesh::~WTriangleMesh()
00085 {
00086 }
00087
00088 void WTriangleMesh::addVertex( float x, float y, float z )
00089 {
00090 addVertex( osg::Vec3( x, y, z ) );
00091 }
00092
00093 void WTriangleMesh::addVertex( WPosition vert )
00094 {
00095 addVertex( osg::Vec3( vert[0], vert[1], vert[2] ) );
00096 }
00097
00098 void WTriangleMesh::addTriangle( size_t vert0, size_t vert1, size_t vert2 )
00099 {
00100 if( m_triangles.size() == m_countTriangles * 3 )
00101 {
00102 m_triangles.resize( m_countTriangles * 3 + 3 );
00103 }
00104 m_triangles[ m_countTriangles * 3 ] = vert0;
00105 m_triangles[ m_countTriangles * 3 + 1 ] = vert1;
00106 m_triangles[ m_countTriangles * 3 + 2 ] = vert2;
00107 ++m_countTriangles;
00108 }
00109
00110 void WTriangleMesh::addTriangle( osg::Vec3 vert0, osg::Vec3 vert1, osg::Vec3 vert2 )
00111 {
00112 addVertex( vert0 );
00113 addVertex( vert1 );
00114 addVertex( vert2 );
00115 addTriangle( m_countVerts - 3, m_countVerts - 2, m_countVerts - 1 );
00116 }
00117
00118 void WTriangleMesh::setVertexNormal( size_t index, osg::Vec3 normal )
00119 {
00120 WAssert( index < m_countVerts, "set vertex normal: index out of range" );
00121 ( *m_vertNormals )[index] = normal;
00122 }
00123
00124 void WTriangleMesh::setVertexNormal( size_t index, WPosition normal )
00125 {
00126 WAssert( index < m_countVerts, "set vertex normal: index out of range" );
00127 setVertexNormal( index, osg::Vec3( normal[0], normal[1], normal[2] ) );
00128 }
00129
00130 void WTriangleMesh::setVertexColor( size_t index, osg::Vec4 color )
00131 {
00132 WAssert( index < m_countVerts, "set vertex color: index out of range" );
00133 ( *m_vertColors )[index] = color;
00134 }
00135
00136 void WTriangleMesh::setTriangleColor( size_t index, osg::Vec4 color )
00137 {
00138 WAssert( index < m_countTriangles, "set triangle color: index out of range" );
00139 ( *m_triangleColors )[index] = color;
00140 }
00141
00142 osg::ref_ptr< osg::Vec3Array >WTriangleMesh::getVertexArray()
00143 {
00144 return m_verts;
00145 }
00146
00147 osg::ref_ptr< const osg::Vec3Array >WTriangleMesh::getVertexArray() const
00148 {
00149 return m_verts;
00150 }
00151
00152 osg::ref_ptr< osg::Vec3Array > WTriangleMesh::getTextureCoordinateArray()
00153 {
00154 return m_textureCoordinates;
00155 }
00156
00157 osg::ref_ptr< const osg::Vec3Array > WTriangleMesh::getTextureCoordinateArray() const
00158 {
00159 return m_textureCoordinates;
00160 }
00161
00162 osg::ref_ptr< osg::Vec3Array >WTriangleMesh::getVertexNormalArray( bool forceRecalc )
00163 {
00164 if( forceRecalc || m_meshDirty )
00165 {
00166 recalcVertNormals();
00167 }
00168 return m_vertNormals;
00169 }
00170
00171 osg::ref_ptr< osg::Vec3Array >WTriangleMesh::getTriangleNormalArray( bool forceRecalc )
00172 {
00173 if( forceRecalc || m_meshDirty )
00174 {
00175 recalcVertNormals();
00176 }
00177 return m_triangleNormals;
00178 }
00179
00180
00181 osg::ref_ptr< osg::Vec4Array >WTriangleMesh::getVertexColorArray()
00182 {
00183 return m_vertColors;
00184 }
00185
00186 const std::vector< size_t >& WTriangleMesh::getTriangles() const
00187 {
00188 return m_triangles;
00189 }
00190
00191 osg::Vec3 WTriangleMesh::getVertex( size_t index ) const
00192 {
00193 WAssert( index < m_countVerts, "get vertex: index out of range" );
00194 return ( *m_verts )[index];
00195 }
00196
00197 osg::Vec4 WTriangleMesh::getVertColor( size_t index ) const
00198 {
00199 WAssert( index < m_countVerts, "get vertex color: index out of range" );
00200 return ( *m_vertColors )[index];
00201 }
00202
00203 WVector3d WTriangleMesh::getNormal( size_t index ) const
00204 {
00205 WAssert( index < m_countVerts, "get normal as position: index out of range" );
00206 return WPosition( ( *m_vertNormals )[index][0], ( *m_vertNormals )[index][1], ( *m_vertNormals )[index][2] );
00207 }
00208
00209 void WTriangleMesh::removeVertex( size_t index )
00210 {
00211 WAssert( index < m_countVerts, "remove vertex: index out of range" );
00212 if( m_vertexIsInTriangle[ index ].size() > 0 )
00213 {
00214 return;
00215 }
00216 ( *m_verts ).erase( ( *m_verts ).begin() + index );
00217
00218 for( size_t i = 0; i < m_countTriangles * 3; ++i )
00219 {
00220 if( m_triangles[ i ] > index )
00221 {
00222 --m_triangles[ i ];
00223 }
00224 }
00225 m_meshDirty = true;
00226 }
00227
00228 void WTriangleMesh::removeTriangle( size_t index )
00229 {
00230 WAssert( index < m_countTriangles, "remove triangle: index out of range" );
00231 m_triangles.erase( m_triangles.begin() + index * 3, m_triangles.begin() + index * 3 + 3 );
00232 m_meshDirty = true;
00233 }
00234
00235 void WTriangleMesh::recalcVertNormals()
00236 {
00237 updateVertsInTriangles();
00238
00239 ( *m_vertNormals ).resize( m_countVerts );
00240 ( *m_triangleNormals ).resize( m_countTriangles );
00241
00242 for( size_t i = 0; i < m_countTriangles; ++i )
00243 {
00244 ( *m_triangleNormals )[i] = calcTriangleNormal( i );
00245 }
00246
00247 for( size_t vertId = 0; vertId < m_countVerts; ++vertId )
00248 {
00249 osg::Vec3 tempNormal( 0.0, 0.0, 0.0 );
00250 for( size_t neighbour = 0; neighbour < m_vertexIsInTriangle[vertId].size(); ++neighbour )
00251 {
00252 tempNormal += ( *m_triangleNormals )[ m_vertexIsInTriangle[vertId][neighbour] ];
00253 }
00254 tempNormal *= 1./m_vertexIsInTriangle[vertId].size();
00255
00256 tempNormal.normalize();
00257 ( *m_vertNormals )[vertId] = tempNormal;
00258 }
00259
00260 m_meshDirty = false;
00261 }
00262
00263 void WTriangleMesh::updateVertsInTriangles()
00264 {
00265 m_vertexIsInTriangle.clear();
00266 std::vector< size_t >v;
00267 m_vertexIsInTriangle.resize( ( *m_verts ).size(), v );
00268
00269 for( size_t i = 0; i < m_countTriangles; ++i )
00270 {
00271 m_vertexIsInTriangle[ getTriVertId0( i ) ].push_back( i );
00272 m_vertexIsInTriangle[ getTriVertId1( i ) ].push_back( i );
00273 m_vertexIsInTriangle[ getTriVertId2( i ) ].push_back( i );
00274 }
00275 }
00276
00277 osg::Vec3 WTriangleMesh::calcTriangleNormal( size_t triangle )
00278 {
00279 osg::Vec3 v1( getTriVert( triangle, 1 ) - getTriVert( triangle, 0 ) );
00280 osg::Vec3 v2( getTriVert( triangle, 2 ) - getTriVert( triangle, 0 ) );
00281
00282 osg::Vec3 tempNormal( 0, 0, 0 );
00283
00284 tempNormal[0] = v1[1] * v2[2] - v1[2] * v2[1];
00285 tempNormal[1] = v1[2] * v2[0] - v1[0] * v2[2];
00286 tempNormal[2] = v1[0] * v2[1] - v1[1] * v2[0];
00287
00288 tempNormal.normalize();
00289
00290 return tempNormal;
00291 }
00292
00293 osg::Vec3 WTriangleMesh::calcNormal( osg::Vec3 vert0, osg::Vec3 vert1, osg::Vec3 vert2 )
00294 {
00295 osg::Vec3 v1( vert1 - vert0 );
00296 osg::Vec3 v2( vert2 - vert0 );
00297
00298 osg::Vec3 tempNormal( 0, 0, 0 );
00299
00300 tempNormal[0] = v1[1] * v2[2] - v1[2] * v2[1];
00301 tempNormal[1] = v1[2] * v2[0] - v1[0] * v2[2];
00302 tempNormal[2] = v1[0] * v2[1] - v1[1] * v2[0];
00303
00304 tempNormal.normalize();
00305
00306 return tempNormal;
00307 }
00308
00309 size_t WTriangleMesh::vertSize() const
00310 {
00311 return m_countVerts;
00312 }
00313
00314 size_t WTriangleMesh::triangleSize() const
00315 {
00316 return m_countTriangles;
00317 }
00318
00319 void WTriangleMesh::calcNeighbors()
00320 {
00321 std::vector<size_t> v( 3, -1 );
00322 m_triangleNeighbors.resize( ( *m_triangleNormals ).size(), v );
00323
00324 for( size_t triId = 0; triId < m_countTriangles; ++triId )
00325 {
00326 size_t coVert0 = getTriVertId0( triId );
00327 size_t coVert1 = getTriVertId1( triId );
00328 size_t coVert2 = getTriVertId2( triId );
00329
00330 m_triangleNeighbors[triId][0] = getNeighbor( coVert0, coVert1, triId );
00331 m_triangleNeighbors[triId][1] = getNeighbor( coVert1, coVert2, triId );
00332 m_triangleNeighbors[triId][2] = getNeighbor( coVert2, coVert0, triId );
00333 }
00334 m_neighborsCalculated = true;
00335 }
00336
00337 size_t WTriangleMesh::getNeighbor( const size_t coVert1, const size_t coVert2, const size_t triangleNum )
00338 {
00339 std::vector< size_t > candidates = m_vertexIsInTriangle[coVert1];
00340 std::vector< size_t > compares = m_vertexIsInTriangle[coVert2];
00341
00342 for( size_t i = 0; i < candidates.size(); ++i )
00343 {
00344 for( size_t k = 0; k < compares.size(); ++k )
00345 {
00346 if( ( candidates[i] != triangleNum ) && ( candidates[i] == compares[k] ) )
00347 {
00348 return candidates[i];
00349 }
00350 }
00351 }
00352 return triangleNum;
00353 }
00354
00355 void WTriangleMesh::doLoopSubD()
00356 {
00357 m_numTriVerts = m_countVerts;
00358 m_numTriFaces = m_countTriangles;
00359
00360 ( *m_verts ).resize( m_numTriVerts * 4 );
00361 m_triangles.resize( m_numTriFaces * 4 * 3 );
00362
00363 updateVertsInTriangles();
00364
00365 osg::Vec3* newVertexPositions = new osg::Vec3[m_numTriVerts];
00366
00367
00368 for( size_t i = 0; i < m_numTriVerts; ++i )
00369 {
00370 newVertexPositions[i] = loopCalcNewPosition( i );
00371 }
00372
00373
00374 for( size_t i = 0; i < m_numTriFaces; ++i )
00375 {
00376 loopInsertCenterTriangle( i );
00377 }
00378 ( *m_verts ).resize( m_countVerts );
00379 std::vector< size_t >v;
00380 m_vertexIsInTriangle.resize( ( *m_verts ).size(), v );
00381
00382
00383 for( size_t i = 0; i < m_numTriFaces; ++i )
00384 {
00385 loopInsertCornerTriangles( i );
00386 }
00387
00388
00389 for( size_t i = 0; i < m_numTriVerts; ++i )
00390 {
00391 ( *m_verts )[i] = newVertexPositions[i];
00392 }
00393
00394 delete[] newVertexPositions;
00395
00396 m_vertNormals->resize( m_verts->size() );
00397 m_vertColors->resize( m_verts->size() );
00398 m_triangleColors->resize( m_triangles.size() / 3 );
00399
00400 m_meshDirty = true;
00401 }
00402
00403
00404 osg::Vec3 WTriangleMesh::loopCalcNewPosition( size_t vertId )
00405 {
00406 std::vector< size_t > starP = m_vertexIsInTriangle[vertId];
00407 int starSize = starP.size();
00408
00409 osg::Vec3 oldPos = getVertex( vertId );
00410 double alpha = loopGetAlpha( starSize );
00411
00412 double scale = 1.0 - ( static_cast<double>( starSize ) * alpha );
00413 oldPos *= scale;
00414
00415 osg::Vec3 newPos;
00416 int edgeV = 0;
00417 for( int i = 0; i < starSize; i++ )
00418 {
00419 edgeV = loopGetNextVertex( starP[i], vertId );
00420 osg::Vec3 translate = getVertex( edgeV );
00421 newPos += translate;
00422 }
00423 newPos *= alpha;
00424
00425 return oldPos + newPos;
00426 }
00427
00428 void WTriangleMesh::loopInsertCenterTriangle( size_t triId )
00429 {
00430 size_t edgeVerts[3];
00431
00432 edgeVerts[0] = loopCalcEdgeVert( triId, getTriVertId0( triId ), getTriVertId1( triId ), getTriVertId2( triId ) );
00433 edgeVerts[1] = loopCalcEdgeVert( triId, getTriVertId1( triId ), getTriVertId2( triId ), getTriVertId0( triId ) );
00434 edgeVerts[2] = loopCalcEdgeVert( triId, getTriVertId2( triId ), getTriVertId0( triId ), getTriVertId1( triId ) );
00435
00436 addTriangle( edgeVerts[0], edgeVerts[1], edgeVerts[2] );
00437 }
00438
00439
00440 size_t WTriangleMesh::loopCalcEdgeVert( size_t triId, size_t edgeV1, size_t edgeV2, size_t V3 )
00441 {
00442 size_t neighborVert = -1;
00443 size_t neighborFaceNum = -1;
00444 osg::Vec3 edgeVert;
00445
00446 neighborFaceNum = getNeighbor( edgeV1, edgeV2, triId );
00447
00448 if( neighborFaceNum == triId )
00449 {
00450 osg::Vec3 edgeVert = ( ( *m_verts )[edgeV1] + ( *m_verts )[edgeV2] ) / 2.0;
00451 size_t vertId = m_countVerts;
00452 addVertex( edgeVert );
00453 return vertId;
00454 }
00455
00456 else if( neighborFaceNum > triId )
00457 {
00458 neighborVert = loopGetThirdVert( edgeV1, edgeV2, neighborFaceNum );
00459
00460 osg::Vec3 edgePart = ( *m_verts )[edgeV1] + ( *m_verts )[edgeV2];
00461 osg::Vec3 neighborPart = ( *m_verts )[neighborVert] + ( *m_verts )[V3];
00462
00463 edgeVert = ( ( edgePart * ( 3.0 / 8.0 ) ) + ( neighborPart * ( 1.0 / 8.0 ) ) );
00464 size_t vertId = m_countVerts;
00465 addVertex( edgeVert );
00466 return vertId;
00467 }
00468 else
00469 {
00470 size_t neighborCenterP = neighborFaceNum + m_numTriFaces;
00471 size_t neighborP = neighborFaceNum;
00472
00473 if( getTriVertId0( neighborP ) == edgeV2 )
00474 {
00475 return getTriVertId0( neighborCenterP );
00476 }
00477 else if( getTriVertId1( neighborP ) == edgeV2 )
00478 {
00479 return getTriVertId1( neighborCenterP );
00480 }
00481 else
00482 {
00483 return getTriVertId2( neighborCenterP );
00484 }
00485 }
00486 return -1;
00487 }
00488
00489 void WTriangleMesh::loopInsertCornerTriangles( size_t triId )
00490 {
00491
00492
00493
00494
00495
00496
00497
00498 size_t originalTri0 = getTriVertId0( triId );
00499 size_t originalTri1 = getTriVertId1( triId );
00500 size_t originalTri2 = getTriVertId2( triId );
00501
00502 size_t centerTri0 = getTriVertId0( triId + m_numTriFaces );
00503 size_t centerTri1 = getTriVertId1( triId + m_numTriFaces );
00504 size_t centerTri2 = getTriVertId2( triId + m_numTriFaces );
00505
00506 addTriangle( originalTri1, centerTri1, centerTri0 );
00507 addTriangle( originalTri2, centerTri2, centerTri1 );
00508 loopSetTriangle( triId, originalTri0, centerTri0, centerTri2 );
00509 }
00510
00511 void WTriangleMesh::loopSetTriangle( size_t triId, size_t vertId1, size_t vertId2, size_t vertId3 )
00512 {
00513 loopEraseTriangleFromVertex( triId, getTriVertId1( triId ) );
00514 loopEraseTriangleFromVertex( triId, getTriVertId2( triId ) );
00515
00516 setTriVert0( triId, vertId1 );
00517 setTriVert1( triId, vertId2 );
00518 setTriVert2( triId, vertId3 );
00519
00520 m_vertexIsInTriangle[vertId2].push_back( triId );
00521 m_vertexIsInTriangle[vertId3].push_back( triId );
00522 }
00523
00524 void WTriangleMesh::loopEraseTriangleFromVertex( size_t triId, size_t vertId )
00525 {
00526 std::vector< size_t > temp;
00527 for( size_t i = 0; i < m_vertexIsInTriangle[vertId].size(); ++i )
00528 {
00529 if( triId != m_vertexIsInTriangle[vertId][i] )
00530 temp.push_back( m_vertexIsInTriangle[vertId][i] );
00531 }
00532 m_vertexIsInTriangle[vertId] = temp;
00533 }
00534
00535 double WTriangleMesh::loopGetAlpha( int n )
00536 {
00537 double answer;
00538 if( n > 3 )
00539 {
00540 double center = ( 0.375 + ( 0.25 * cos( ( 2.0 * 3.14159265358979 ) / static_cast<double>( n ) ) ) );
00541 answer = ( 0.625 - ( center * center ) ) / static_cast<double>( n );
00542 }
00543 else
00544 {
00545 answer = 3.0 / 16.0;
00546 }
00547 return answer;
00548 }
00549
00550 size_t WTriangleMesh::loopGetNextVertex( size_t triNum, size_t vertNum )
00551 {
00552 if( getTriVertId0( triNum ) == vertNum )
00553 {
00554 return getTriVertId1( triNum );
00555 }
00556 else if( getTriVertId1( triNum ) == vertNum )
00557 {
00558 return getTriVertId2( triNum );
00559 }
00560 return getTriVertId0( triNum );
00561 }
00562
00563 size_t WTriangleMesh::loopGetThirdVert( size_t coVert1, size_t coVert2, size_t triangleNum )
00564 {
00565 if( !( getTriVertId0( triangleNum ) == coVert1 ) && !( getTriVertId0( triangleNum ) == coVert2 ) )
00566 {
00567 return getTriVertId0( triangleNum );
00568 }
00569 else if( !( getTriVertId1( triangleNum ) == coVert1 ) && !( getTriVertId1( triangleNum ) == coVert2 ) )
00570 {
00571 return getTriVertId1( triangleNum );
00572 }
00573 return getTriVertId2( triangleNum );
00574 }
00575
00576 void WTriangleMesh::addMesh( boost::shared_ptr<WTriangleMesh> mesh, float xOff, float yOff, float zOff )
00577 {
00578 size_t oldVertSize = m_countVerts;
00579
00580 ( *m_vertColors ).resize( oldVertSize + mesh->vertSize() );
00581 for( size_t i = 0; i < mesh->vertSize(); ++i )
00582 {
00583 osg::Vec3 v( mesh->getVertex( i ) );
00584 v[0] += xOff;
00585 v[1] += yOff;
00586 v[2] += zOff;
00587 addVertex( v );
00588 setVertexColor( oldVertSize + i, mesh->getVertColor( i ) );
00589 }
00590 for( size_t i = 0; i < mesh->triangleSize(); ++i )
00591 {
00592 addTriangle( mesh->getTriVertId0( i ) + oldVertSize, mesh->getTriVertId1( i ) + oldVertSize, mesh->getTriVertId2( i ) + oldVertSize );
00593 }
00594 m_meshDirty = true;
00595 }
00596
00597 void WTriangleMesh::translateMesh( float xOff, float yOff, float zOff )
00598 {
00599 osg::Vec3 t( xOff, yOff, zOff );
00600 for( size_t i = 0; i < ( *m_verts ).size(); ++i )
00601 {
00602 ( *m_verts )[i] += t;
00603 }
00604 }
00605
00606 void WTriangleMesh::zoomMesh( float zoom )
00607 {
00608 for( size_t i = 0; i < ( *m_verts ).size(); ++i )
00609 {
00610 ( *m_verts )[i] *= zoom;
00611 }
00612 }
00613
00614 std::ostream& tm_utils::operator<<( std::ostream& os, const WTriangleMesh& rhs )
00615 {
00616 std::stringstream ss;
00617 ss << "WTriangleMesh( #vertices=" << rhs.vertSize() << " #triangles=" << rhs.triangleSize() << " )" << std::endl;
00618 using string_utils::operator<<;
00619 size_t count = 0;
00620 ss << std::endl;
00621 const std::vector< size_t >& triangles = rhs.getTriangles();
00622 osg::ref_ptr< const osg::Vec3Array > vertices = rhs.getVertexArray();
00623 for( size_t vID = 0 ; vID <= triangles.size() - 3; ++count )
00624 {
00625 std::stringstream prefix;
00626 prefix << "triangle: " << count << "[ ";
00627 std::string indent( prefix.str().size(), ' ' );
00628 using osg::operator<<;
00629 ss << prefix.str() << vertices->at( triangles[ vID++ ] ) << std::endl;
00630 ss << indent << vertices->at( triangles[ vID++ ] ) << std::endl;
00631 ss << indent << vertices->at( triangles[ vID++ ] ) << std::endl;
00632 ss << std::string( indent.size() - 2, ' ' ) << "]" << std::endl;
00633 }
00634 return os << ss.str();
00635 }
00636
00637 boost::shared_ptr< std::list< boost::shared_ptr< WTriangleMesh > > > tm_utils::componentDecomposition( const WTriangleMesh& mesh )
00638 {
00639 boost::shared_ptr< std::list< boost::shared_ptr< WTriangleMesh > > > result( new std::list< boost::shared_ptr< WTriangleMesh > >() );
00640 if( mesh.vertSize() <= 0 )
00641 {
00642 return result;
00643 }
00644 if( mesh.triangleSize() < 3 )
00645 {
00646 if( mesh.vertSize() > 0 )
00647 {
00648
00649 WAssert( false, "Not implemented the decomposition of a TriangleMesh without any triangles" );
00650 }
00651 else
00652 {
00653 return result;
00654 }
00655 }
00656
00657 WUnionFind uf( mesh.vertSize() );
00658
00659 const std::vector< size_t >& triangles = mesh.getTriangles();
00660 for( size_t vID = 0; vID <= triangles.size() - 3; vID += 3)
00661 {
00662 uf.merge( triangles[ vID ], triangles[ vID + 1 ] );
00663 uf.merge( triangles[ vID ], triangles[ vID + 2 ] );
00664 }
00665
00666
00667
00668
00669
00670
00671 typedef std::map< osg::Vec3, size_t > VertexType;
00672 typedef std::vector< size_t > TriangleType;
00673 typedef std::pair< VertexType, TriangleType > BucketType;
00674 std::map< size_t, BucketType > buckets;
00675
00676 osg::ref_ptr< const osg::Vec3Array > vertices = mesh.getVertexArray();
00677 for( size_t vID = 0; vID <= triangles.size() - 3; vID += 3 )
00678 {
00679 size_t component = uf.find( triangles[ vID ] );
00680 if( buckets.find( component ) == buckets.end() )
00681 {
00682 buckets[ component ] = BucketType( VertexType(), TriangleType() );
00683 }
00684
00685
00686 VertexType& mapRef = buckets[ component ].first;
00687 for( int i = 0; i < 3; ++i )
00688 {
00689 size_t id = 0;
00690 const osg::Vec3& vertex = ( *vertices )[ triangles[ vID + i ] ];
00691 if( mapRef.find( vertex ) == mapRef.end() )
00692 {
00693 id = mapRef.size();
00694 mapRef[ vertex ] = id;
00695 }
00696 else
00697 {
00698 id = mapRef[ vertex ];
00699 }
00700 buckets[ component ].second.push_back( id );
00701 }
00702 }
00703
00704 for( std::map< size_t, BucketType >::const_iterator cit = buckets.begin(); cit != buckets.end(); ++cit )
00705 {
00706 osg::ref_ptr< osg::Vec3Array > newVertices( new osg::Vec3Array );
00707 newVertices->resize( cit->second.first.size() );
00708 for( VertexType::const_iterator vit = cit->second.first.begin(); vit != cit->second.first.end(); ++vit )
00709 {
00710 newVertices->at( vit->second ) = vit->first;
00711 }
00712 boost::shared_ptr< WTriangleMesh > newMesh( new WTriangleMesh( newVertices, cit->second.second ) );
00713 result->push_back( newMesh );
00714 }
00715
00716 return result;
00717 }
00718
00719 osg::ref_ptr< osg::Vec4Array > WTriangleMesh::getTriangleColors() const
00720 {
00721 return m_triangleColors;
00722 }