OpenWalnut
1.2.5
|
00001 //--------------------------------------------------------------------------- 00002 // 00003 // Project: OpenWalnut ( http://www.openwalnut.org ) 00004 // 00005 // Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS 00006 // For more information see http://www.openwalnut.org/copying 00007 // 00008 // This file is part of OpenWalnut. 00009 // 00010 // OpenWalnut is free software: you can redistribute it and/or modify 00011 // it under the terms of the GNU Lesser General Public License as published by 00012 // the Free Software Foundation, either version 3 of the License, or 00013 // (at your option) any later version. 00014 // 00015 // OpenWalnut is distributed in the hope that it will be useful, 00016 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00018 // GNU Lesser General Public License for more details. 00019 // 00020 // You should have received a copy of the GNU Lesser General Public License 00021 // along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>. 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 // init _static_ member variable and provide a linker reference to it 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 * constructor that already reserves space for a given number of triangles and vertexes 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 //std::cout << "Loop subdivision pass 1" << std::endl; 00368 for( size_t i = 0; i < m_numTriVerts; ++i ) 00369 { 00370 newVertexPositions[i] = loopCalcNewPosition( i ); 00371 } 00372 00373 //std::cout << "Loop subdivision pass 2" << std::endl; 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 //std::cout << "Loop subdivision pass 3" << std::endl; 00383 for( size_t i = 0; i < m_numTriFaces; ++i ) 00384 { 00385 loopInsertCornerTriangles( i ); 00386 } 00387 00388 //std::cout << "Loop subdivision pass 4" << std::endl; 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 // comment: center are twisted from the orignal vertices. 00492 // original: 0, 1, 2 00493 // center: a, b, c 00494 // reAsgnOrig: 0, a, c 00495 // addTris: 1, b, a 00496 // addTris: 2, c, b 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<<; // using operator<< as defined in osg/io_utils 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 ) // no component possible 00641 { 00642 return result; 00643 } 00644 if( mesh.triangleSize() < 3 ) 00645 { 00646 if( mesh.vertSize() > 0 ) 00647 { 00648 // there are vertices but no triangles 00649 WAssert( false, "Not implemented the decomposition of a TriangleMesh without any triangles" ); 00650 } 00651 else // no component possible 00652 { 00653 return result; 00654 } 00655 } 00656 00657 WUnionFind uf( mesh.vertSize() ); // idea: every vertex in own component, then successivley join in accordance with the triangles 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 ] ); // uf.merge( triangles[ vID + 2 ], triangles[ vID + 1 ] ); they are already in same 00664 } 00665 00666 // ATTENTION: The reason for using the complex BucketType instead of pasting vertices directly into a new WTriangleMesh 00667 // is performance! For example: If there are many vertices reused inside the former WTriangleMesh mesh, then we want 00668 // to reuse them in the new components too. Hence we must determine if a certain vertex is already inside the new component. 00669 // Since the vertices are organized in a vector, we can use std::find( v.begin, v.end(), vertexToLookUp ) which results 00670 // in O(N^2) or we could use faster lookUp via key and value leading to the map and the somehow complicated BucketType. 00671 typedef std::map< osg::Vec3, size_t > VertexType; // look up fast if a vertex is already inside the new mesh! 00672 typedef std::vector< size_t > TriangleType; 00673 typedef std::pair< VertexType, TriangleType > BucketType; // Later on the Bucket will be transformed into the new WTriangleMesh component 00674 std::map< size_t, BucketType > buckets; // Key identify with the cannonical element from UnionFind the new connected component 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() ); // create new bucket 00683 } 00684 00685 // Note: We discard the order of the points and indices, but semantically the structure remains the same 00686 VertexType& mapRef = buckets[ component ].first; // short hand alias 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(); // since size might change in next line 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; // if you are sure that vit->second is always valid replace at() call with operator[] 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 }