OpenWalnut  1.2.5
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
WTriangleMesh.cpp
1 //---------------------------------------------------------------------------
2 //
3 // Project: OpenWalnut ( http://www.openwalnut.org )
4 //
5 // Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS
6 // For more information see http://www.openwalnut.org/copying
7 //
8 // This file is part of OpenWalnut.
9 //
10 // OpenWalnut is free software: you can redistribute it and/or modify
11 // it under the terms of the GNU Lesser General Public License as published by
12 // the Free Software Foundation, either version 3 of the License, or
13 // (at your option) any later version.
14 //
15 // OpenWalnut is distributed in the hope that it will be useful,
16 // but WITHOUT ANY WARRANTY; without even the implied warranty of
17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 // GNU Lesser General Public License for more details.
19 //
20 // You should have received a copy of the GNU Lesser General Public License
21 // along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>.
22 //
23 //---------------------------------------------------------------------------
24 
25 #include <iostream>
26 #include <list>
27 #include <map>
28 #include <sstream>
29 #include <string>
30 #include <vector>
31 
32 #include <osg/io_utils>
33 
34 #include "../common/datastructures/WUnionFind.h"
35 #include "WTriangleMesh.h"
36 
37 // init _static_ member variable and provide a linker reference to it
38 boost::shared_ptr< WPrototyped > WTriangleMesh::m_prototype = boost::shared_ptr< WPrototyped >();
39 
40 boost::shared_ptr< WPrototyped > WTriangleMesh::getPrototype()
41 {
42  if( !m_prototype )
43  {
44  m_prototype = boost::shared_ptr< WPrototyped >( new WTriangleMesh( 0, 0 ) );
45  }
46  return m_prototype;
47 }
48 
49 /**
50  * constructor that already reserves space for a given number of triangles and vertexes
51  */
52 WTriangleMesh::WTriangleMesh( size_t vertNum, size_t triangleNum )
53  : m_countVerts( 0 ),
54  m_countTriangles( 0 ),
55  m_meshDirty( true ),
56  m_neighborsCalculated( false )
57 {
58  m_verts = osg::ref_ptr< osg::Vec3Array >( new osg::Vec3Array( vertNum ) );
59  m_textureCoordinates = osg::ref_ptr< osg::Vec3Array >( new osg::Vec3Array( vertNum ) );
60  m_vertNormals = osg::ref_ptr< osg::Vec3Array >( new osg::Vec3Array( vertNum ) );
61  m_vertColors = osg::ref_ptr< osg::Vec4Array >( new osg::Vec4Array( vertNum ) );
62 
63  m_triangles.resize( triangleNum * 3 );
64  m_triangleNormals = osg::ref_ptr< osg::Vec3Array >( new osg::Vec3Array( triangleNum ) );
65  m_triangleColors = osg::ref_ptr< osg::Vec4Array >( new osg::Vec4Array( triangleNum ) );
66 }
67 
68 WTriangleMesh::WTriangleMesh( osg::ref_ptr< osg::Vec3Array > vertices, const std::vector< size_t >& triangles )
69  : m_countVerts( vertices->size() ),
70  m_countTriangles( triangles.size() / 3 ),
71  m_meshDirty( true ),
72  m_neighborsCalculated( false ),
73  m_verts( vertices ),
74  m_textureCoordinates( new osg::Vec3Array( vertices->size() ) ),
75  m_vertNormals( new osg::Vec3Array( vertices->size() ) ),
76  m_vertColors( new osg::Vec4Array( vertices->size() ) ),
77  m_triangles( triangles ),
78  m_triangleNormals( new osg::Vec3Array( triangles.size() / 3 ) ),
79  m_triangleColors( new osg::Vec4Array( triangles.size() / 3 ) )
80 {
81  WAssert( triangles.size() % 3 == 0, "Invalid triangle vector, having an invalid size (not divideable by 3)" );
82 }
83 
85 {
86 }
87 
88 void WTriangleMesh::addVertex( float x, float y, float z )
89 {
90  addVertex( osg::Vec3( x, y, z ) );
91 }
92 
94 {
95  addVertex( osg::Vec3( vert[0], vert[1], vert[2] ) );
96 }
97 
98 void WTriangleMesh::addTriangle( size_t vert0, size_t vert1, size_t vert2 )
99 {
100  if( m_triangles.size() == m_countTriangles * 3 )
101  {
102  m_triangles.resize( m_countTriangles * 3 + 3 );
103  }
104  m_triangles[ m_countTriangles * 3 ] = vert0;
105  m_triangles[ m_countTriangles * 3 + 1 ] = vert1;
106  m_triangles[ m_countTriangles * 3 + 2 ] = vert2;
108 }
109 
110 void WTriangleMesh::addTriangle( osg::Vec3 vert0, osg::Vec3 vert1, osg::Vec3 vert2 )
111 {
112  addVertex( vert0 );
113  addVertex( vert1 );
114  addVertex( vert2 );
116 }
117 
118 void WTriangleMesh::setVertexNormal( size_t index, osg::Vec3 normal )
119 {
120  WAssert( index < m_countVerts, "set vertex normal: index out of range" );
121  ( *m_vertNormals )[index] = normal;
122 }
123 
124 void WTriangleMesh::setVertexNormal( size_t index, WPosition normal )
125 {
126  WAssert( index < m_countVerts, "set vertex normal: index out of range" );
127  setVertexNormal( index, osg::Vec3( normal[0], normal[1], normal[2] ) );
128 }
129 
130 void WTriangleMesh::setVertexColor( size_t index, osg::Vec4 color )
131 {
132  WAssert( index < m_countVerts, "set vertex color: index out of range" );
133  ( *m_vertColors )[index] = color;
134 }
135 
136 void WTriangleMesh::setTriangleColor( size_t index, osg::Vec4 color )
137 {
138  WAssert( index < m_countTriangles, "set triangle color: index out of range" );
139  ( *m_triangleColors )[index] = color;
140 }
141 
142 osg::ref_ptr< osg::Vec3Array >WTriangleMesh::getVertexArray()
143 {
144  return m_verts;
145 }
146 
147 osg::ref_ptr< const osg::Vec3Array >WTriangleMesh::getVertexArray() const
148 {
149  return m_verts;
150 }
151 
152 osg::ref_ptr< osg::Vec3Array > WTriangleMesh::getTextureCoordinateArray()
153 {
154  return m_textureCoordinates;
155 }
156 
157 osg::ref_ptr< const osg::Vec3Array > WTriangleMesh::getTextureCoordinateArray() const
158 {
159  return m_textureCoordinates;
160 }
161 
162 osg::ref_ptr< osg::Vec3Array >WTriangleMesh::getVertexNormalArray( bool forceRecalc )
163 {
164  if( forceRecalc || m_meshDirty )
165  {
167  }
168  return m_vertNormals;
169 }
170 
171 osg::ref_ptr< osg::Vec3Array >WTriangleMesh::getTriangleNormalArray( bool forceRecalc )
172 {
173  if( forceRecalc || m_meshDirty )
174  {
176  }
177  return m_triangleNormals;
178 }
179 
180 
181 osg::ref_ptr< osg::Vec4Array >WTriangleMesh::getVertexColorArray()
182 {
183  return m_vertColors;
184 }
185 
186 const std::vector< size_t >& WTriangleMesh::getTriangles() const
187 {
188  return m_triangles;
189 }
190 
191 osg::Vec3 WTriangleMesh::getVertex( size_t index ) const
192 {
193  WAssert( index < m_countVerts, "get vertex: index out of range" );
194  return ( *m_verts )[index];
195 }
196 
197 osg::Vec4 WTriangleMesh::getVertColor( size_t index ) const
198 {
199  WAssert( index < m_countVerts, "get vertex color: index out of range" );
200  return ( *m_vertColors )[index];
201 }
202 
203 WVector3d WTriangleMesh::getNormal( size_t index ) const
204 {
205  WAssert( index < m_countVerts, "get normal as position: index out of range" );
206  return WPosition( ( *m_vertNormals )[index][0], ( *m_vertNormals )[index][1], ( *m_vertNormals )[index][2] );
207 }
208 
209 void WTriangleMesh::removeVertex( size_t index )
210 {
211  WAssert( index < m_countVerts, "remove vertex: index out of range" );
212  if( m_vertexIsInTriangle[ index ].size() > 0 )
213  {
214  return;
215  }
216  ( *m_verts ).erase( ( *m_verts ).begin() + index );
217 
218  for( size_t i = 0; i < m_countTriangles * 3; ++i )
219  {
220  if( m_triangles[ i ] > index )
221  {
222  --m_triangles[ i ];
223  }
224  }
225  m_meshDirty = true;
226 }
227 
228 void WTriangleMesh::removeTriangle( size_t index )
229 {
230  WAssert( index < m_countTriangles, "remove triangle: index out of range" );
231  m_triangles.erase( m_triangles.begin() + index * 3, m_triangles.begin() + index * 3 + 3 );
232  m_meshDirty = true;
233 }
234 
236 {
238 
239  ( *m_vertNormals ).resize( m_countVerts );
240  ( *m_triangleNormals ).resize( m_countTriangles );
241 
242  for( size_t i = 0; i < m_countTriangles; ++i )
243  {
244  ( *m_triangleNormals )[i] = calcTriangleNormal( i );
245  }
246 
247  for( size_t vertId = 0; vertId < m_countVerts; ++vertId )
248  {
249  osg::Vec3 tempNormal( 0.0, 0.0, 0.0 );
250  for( size_t neighbour = 0; neighbour < m_vertexIsInTriangle[vertId].size(); ++neighbour )
251  {
252  tempNormal += ( *m_triangleNormals )[ m_vertexIsInTriangle[vertId][neighbour] ];
253  }
254  tempNormal *= 1./m_vertexIsInTriangle[vertId].size();
255 
256  tempNormal.normalize();
257  ( *m_vertNormals )[vertId] = tempNormal;
258  }
259 
260  m_meshDirty = false;
261 }
262 
264 {
265  m_vertexIsInTriangle.clear();
266  std::vector< size_t >v;
267  m_vertexIsInTriangle.resize( ( *m_verts ).size(), v );
268 
269  for( size_t i = 0; i < m_countTriangles; ++i )
270  {
271  m_vertexIsInTriangle[ getTriVertId0( i ) ].push_back( i );
272  m_vertexIsInTriangle[ getTriVertId1( i ) ].push_back( i );
273  m_vertexIsInTriangle[ getTriVertId2( i ) ].push_back( i );
274  }
275 }
276 
277 osg::Vec3 WTriangleMesh::calcTriangleNormal( size_t triangle )
278 {
279  osg::Vec3 v1( getTriVert( triangle, 1 ) - getTriVert( triangle, 0 ) );
280  osg::Vec3 v2( getTriVert( triangle, 2 ) - getTriVert( triangle, 0 ) );
281 
282  osg::Vec3 tempNormal( 0, 0, 0 );
283 
284  tempNormal[0] = v1[1] * v2[2] - v1[2] * v2[1];
285  tempNormal[1] = v1[2] * v2[0] - v1[0] * v2[2];
286  tempNormal[2] = v1[0] * v2[1] - v1[1] * v2[0];
287 
288  tempNormal.normalize();
289 
290  return tempNormal;
291 }
292 
293 osg::Vec3 WTriangleMesh::calcNormal( osg::Vec3 vert0, osg::Vec3 vert1, osg::Vec3 vert2 )
294 {
295  osg::Vec3 v1( vert1 - vert0 );
296  osg::Vec3 v2( vert2 - vert0 );
297 
298  osg::Vec3 tempNormal( 0, 0, 0 );
299 
300  tempNormal[0] = v1[1] * v2[2] - v1[2] * v2[1];
301  tempNormal[1] = v1[2] * v2[0] - v1[0] * v2[2];
302  tempNormal[2] = v1[0] * v2[1] - v1[1] * v2[0];
303 
304  tempNormal.normalize();
305 
306  return tempNormal;
307 }
308 
310 {
311  return m_countVerts;
312 }
313 
315 {
316  return m_countTriangles;
317 }
318 
320 {
321  std::vector<size_t> v( 3, -1 );
322  m_triangleNeighbors.resize( ( *m_triangleNormals ).size(), v );
323 
324  for( size_t triId = 0; triId < m_countTriangles; ++triId )
325  {
326  size_t coVert0 = getTriVertId0( triId );
327  size_t coVert1 = getTriVertId1( triId );
328  size_t coVert2 = getTriVertId2( triId );
329 
330  m_triangleNeighbors[triId][0] = getNeighbor( coVert0, coVert1, triId );
331  m_triangleNeighbors[triId][1] = getNeighbor( coVert1, coVert2, triId );
332  m_triangleNeighbors[triId][2] = getNeighbor( coVert2, coVert0, triId );
333  }
334  m_neighborsCalculated = true;
335 }
336 
337 size_t WTriangleMesh::getNeighbor( const size_t coVert1, const size_t coVert2, const size_t triangleNum )
338 {
339  std::vector< size_t > candidates = m_vertexIsInTriangle[coVert1];
340  std::vector< size_t > compares = m_vertexIsInTriangle[coVert2];
341 
342  for( size_t i = 0; i < candidates.size(); ++i )
343  {
344  for( size_t k = 0; k < compares.size(); ++k )
345  {
346  if( ( candidates[i] != triangleNum ) && ( candidates[i] == compares[k] ) )
347  {
348  return candidates[i];
349  }
350  }
351  }
352  return triangleNum;
353 }
354 
356 {
359 
360  ( *m_verts ).resize( m_numTriVerts * 4 );
361  m_triangles.resize( m_numTriFaces * 4 * 3 );
362 
364 
365  osg::Vec3* newVertexPositions = new osg::Vec3[m_numTriVerts];
366 
367  //std::cout << "Loop subdivision pass 1" << std::endl;
368  for( size_t i = 0; i < m_numTriVerts; ++i )
369  {
370  newVertexPositions[i] = loopCalcNewPosition( i );
371  }
372 
373  //std::cout << "Loop subdivision pass 2" << std::endl;
374  for( size_t i = 0; i < m_numTriFaces; ++i )
375  {
377  }
378  ( *m_verts ).resize( m_countVerts );
379  std::vector< size_t >v;
380  m_vertexIsInTriangle.resize( ( *m_verts ).size(), v );
381 
382  //std::cout << "Loop subdivision pass 3" << std::endl;
383  for( size_t i = 0; i < m_numTriFaces; ++i )
384  {
386  }
387 
388  //std::cout << "Loop subdivision pass 4" << std::endl;
389  for( size_t i = 0; i < m_numTriVerts; ++i )
390  {
391  ( *m_verts )[i] = newVertexPositions[i];
392  }
393 
394  delete[] newVertexPositions;
395 
396  m_vertNormals->resize( m_verts->size() );
397  m_vertColors->resize( m_verts->size() );
398  m_triangleColors->resize( m_triangles.size() / 3 );
399 
400  m_meshDirty = true;
401 }
402 
403 
404 osg::Vec3 WTriangleMesh::loopCalcNewPosition( size_t vertId )
405 {
406  std::vector< size_t > starP = m_vertexIsInTriangle[vertId];
407  int starSize = starP.size();
408 
409  osg::Vec3 oldPos = getVertex( vertId );
410  double alpha = loopGetAlpha( starSize );
411 
412  double scale = 1.0 - ( static_cast<double>( starSize ) * alpha );
413  oldPos *= scale;
414 
415  osg::Vec3 newPos;
416  int edgeV = 0;
417  for( int i = 0; i < starSize; i++ )
418  {
419  edgeV = loopGetNextVertex( starP[i], vertId );
420  osg::Vec3 translate = getVertex( edgeV );
421  newPos += translate;
422  }
423  newPos *= alpha;
424 
425  return oldPos + newPos;
426 }
427 
429 {
430  size_t edgeVerts[3];
431 
432  edgeVerts[0] = loopCalcEdgeVert( triId, getTriVertId0( triId ), getTriVertId1( triId ), getTriVertId2( triId ) );
433  edgeVerts[1] = loopCalcEdgeVert( triId, getTriVertId1( triId ), getTriVertId2( triId ), getTriVertId0( triId ) );
434  edgeVerts[2] = loopCalcEdgeVert( triId, getTriVertId2( triId ), getTriVertId0( triId ), getTriVertId1( triId ) );
435 
436  addTriangle( edgeVerts[0], edgeVerts[1], edgeVerts[2] );
437 }
438 
439 
440 size_t WTriangleMesh::loopCalcEdgeVert( size_t triId, size_t edgeV1, size_t edgeV2, size_t V3 )
441 {
442  size_t neighborVert = -1;
443  size_t neighborFaceNum = -1;
444  osg::Vec3 edgeVert;
445 
446  neighborFaceNum = getNeighbor( edgeV1, edgeV2, triId );
447 
448  if( neighborFaceNum == triId )
449  {
450  osg::Vec3 edgeVert = ( ( *m_verts )[edgeV1] + ( *m_verts )[edgeV2] ) / 2.0;
451  size_t vertId = m_countVerts;
452  addVertex( edgeVert );
453  return vertId;
454  }
455 
456  else if( neighborFaceNum > triId )
457  {
458  neighborVert = loopGetThirdVert( edgeV1, edgeV2, neighborFaceNum );
459 
460  osg::Vec3 edgePart = ( *m_verts )[edgeV1] + ( *m_verts )[edgeV2];
461  osg::Vec3 neighborPart = ( *m_verts )[neighborVert] + ( *m_verts )[V3];
462 
463  edgeVert = ( ( edgePart * ( 3.0 / 8.0 ) ) + ( neighborPart * ( 1.0 / 8.0 ) ) );
464  size_t vertId = m_countVerts;
465  addVertex( edgeVert );
466  return vertId;
467  }
468  else
469  {
470  size_t neighborCenterP = neighborFaceNum + m_numTriFaces;
471  size_t neighborP = neighborFaceNum;
472 
473  if( getTriVertId0( neighborP ) == edgeV2 )
474  {
475  return getTriVertId0( neighborCenterP );
476  }
477  else if( getTriVertId1( neighborP ) == edgeV2 )
478  {
479  return getTriVertId1( neighborCenterP );
480  }
481  else
482  {
483  return getTriVertId2( neighborCenterP );
484  }
485  }
486  return -1;
487 }
488 
490 {
491  // comment: center are twisted from the orignal vertices.
492  // original: 0, 1, 2
493  // center: a, b, c
494  // reAsgnOrig: 0, a, c
495  // addTris: 1, b, a
496  // addTris: 2, c, b
497  //
498  size_t originalTri0 = getTriVertId0( triId );
499  size_t originalTri1 = getTriVertId1( triId );
500  size_t originalTri2 = getTriVertId2( triId );
501 
502  size_t centerTri0 = getTriVertId0( triId + m_numTriFaces );
503  size_t centerTri1 = getTriVertId1( triId + m_numTriFaces );
504  size_t centerTri2 = getTriVertId2( triId + m_numTriFaces );
505 
506  addTriangle( originalTri1, centerTri1, centerTri0 );
507  addTriangle( originalTri2, centerTri2, centerTri1 );
508  loopSetTriangle( triId, originalTri0, centerTri0, centerTri2 );
509 }
510 
511 void WTriangleMesh::loopSetTriangle( size_t triId, size_t vertId1, size_t vertId2, size_t vertId3 )
512 {
513  loopEraseTriangleFromVertex( triId, getTriVertId1( triId ) );
514  loopEraseTriangleFromVertex( triId, getTriVertId2( triId ) );
515 
516  setTriVert0( triId, vertId1 );
517  setTriVert1( triId, vertId2 );
518  setTriVert2( triId, vertId3 );
519 
520  m_vertexIsInTriangle[vertId2].push_back( triId );
521  m_vertexIsInTriangle[vertId3].push_back( triId );
522 }
523 
524 void WTriangleMesh::loopEraseTriangleFromVertex( size_t triId, size_t vertId )
525 {
526  std::vector< size_t > temp;
527  for( size_t i = 0; i < m_vertexIsInTriangle[vertId].size(); ++i )
528  {
529  if( triId != m_vertexIsInTriangle[vertId][i] )
530  temp.push_back( m_vertexIsInTriangle[vertId][i] );
531  }
532  m_vertexIsInTriangle[vertId] = temp;
533 }
534 
536 {
537  double answer;
538  if( n > 3 )
539  {
540  double center = ( 0.375 + ( 0.25 * cos( ( 2.0 * 3.14159265358979 ) / static_cast<double>( n ) ) ) );
541  answer = ( 0.625 - ( center * center ) ) / static_cast<double>( n );
542  }
543  else
544  {
545  answer = 3.0 / 16.0;
546  }
547  return answer;
548 }
549 
550 size_t WTriangleMesh::loopGetNextVertex( size_t triNum, size_t vertNum )
551 {
552  if( getTriVertId0( triNum ) == vertNum )
553  {
554  return getTriVertId1( triNum );
555  }
556  else if( getTriVertId1( triNum ) == vertNum )
557  {
558  return getTriVertId2( triNum );
559  }
560  return getTriVertId0( triNum );
561 }
562 
563 size_t WTriangleMesh::loopGetThirdVert( size_t coVert1, size_t coVert2, size_t triangleNum )
564 {
565  if( !( getTriVertId0( triangleNum ) == coVert1 ) && !( getTriVertId0( triangleNum ) == coVert2 ) )
566  {
567  return getTriVertId0( triangleNum );
568  }
569  else if( !( getTriVertId1( triangleNum ) == coVert1 ) && !( getTriVertId1( triangleNum ) == coVert2 ) )
570  {
571  return getTriVertId1( triangleNum );
572  }
573  return getTriVertId2( triangleNum );
574 }
575 
576 void WTriangleMesh::addMesh( boost::shared_ptr<WTriangleMesh> mesh, float xOff, float yOff, float zOff )
577 {
578  size_t oldVertSize = m_countVerts;
579 
580  ( *m_vertColors ).resize( oldVertSize + mesh->vertSize() );
581  for( size_t i = 0; i < mesh->vertSize(); ++i )
582  {
583  osg::Vec3 v( mesh->getVertex( i ) );
584  v[0] += xOff;
585  v[1] += yOff;
586  v[2] += zOff;
587  addVertex( v );
588  setVertexColor( oldVertSize + i, mesh->getVertColor( i ) );
589  }
590  for( size_t i = 0; i < mesh->triangleSize(); ++i )
591  {
592  addTriangle( mesh->getTriVertId0( i ) + oldVertSize, mesh->getTriVertId1( i ) + oldVertSize, mesh->getTriVertId2( i ) + oldVertSize );
593  }
594  m_meshDirty = true;
595 }
596 
597 void WTriangleMesh::translateMesh( float xOff, float yOff, float zOff )
598 {
599  osg::Vec3 t( xOff, yOff, zOff );
600  for( size_t i = 0; i < ( *m_verts ).size(); ++i )
601  {
602  ( *m_verts )[i] += t;
603  }
604 }
605 
606 void WTriangleMesh::zoomMesh( float zoom )
607 {
608  for( size_t i = 0; i < ( *m_verts ).size(); ++i )
609  {
610  ( *m_verts )[i] *= zoom;
611  }
612 }
613 
614 std::ostream& tm_utils::operator<<( std::ostream& os, const WTriangleMesh& rhs )
615 {
616  std::stringstream ss;
617  ss << "WTriangleMesh( #vertices=" << rhs.vertSize() << " #triangles=" << rhs.triangleSize() << " )" << std::endl;
618  using string_utils::operator<<;
619  size_t count = 0;
620  ss << std::endl;
621  const std::vector< size_t >& triangles = rhs.getTriangles();
622  osg::ref_ptr< const osg::Vec3Array > vertices = rhs.getVertexArray();
623  for( size_t vID = 0 ; vID <= triangles.size() - 3; ++count )
624  {
625  std::stringstream prefix;
626  prefix << "triangle: " << count << "[ ";
627  std::string indent( prefix.str().size(), ' ' );
628  using osg::operator<<; // using operator<< as defined in osg/io_utils
629  ss << prefix.str() << vertices->at( triangles[ vID++ ] ) << std::endl;
630  ss << indent << vertices->at( triangles[ vID++ ] ) << std::endl;
631  ss << indent << vertices->at( triangles[ vID++ ] ) << std::endl;
632  ss << std::string( indent.size() - 2, ' ' ) << "]" << std::endl;
633  }
634  return os << ss.str();
635 }
636 
637 boost::shared_ptr< std::list< boost::shared_ptr< WTriangleMesh > > > tm_utils::componentDecomposition( const WTriangleMesh& mesh )
638 {
639  boost::shared_ptr< std::list< boost::shared_ptr< WTriangleMesh > > > result( new std::list< boost::shared_ptr< WTriangleMesh > >() );
640  if( mesh.vertSize() <= 0 ) // no component possible
641  {
642  return result;
643  }
644  if( mesh.triangleSize() < 3 )
645  {
646  if( mesh.vertSize() > 0 )
647  {
648  // there are vertices but no triangles
649  WAssert( false, "Not implemented the decomposition of a TriangleMesh without any triangles" );
650  }
651  else // no component possible
652  {
653  return result;
654  }
655  }
656 
657  WUnionFind uf( mesh.vertSize() ); // idea: every vertex in own component, then successivley join in accordance with the triangles
658 
659  const std::vector< size_t >& triangles = mesh.getTriangles();
660  for( size_t vID = 0; vID <= triangles.size() - 3; vID += 3)
661  {
662  uf.merge( triangles[ vID ], triangles[ vID + 1 ] );
663  uf.merge( triangles[ vID ], triangles[ vID + 2 ] ); // uf.merge( triangles[ vID + 2 ], triangles[ vID + 1 ] ); they are already in same
664  }
665 
666  // ATTENTION: The reason for using the complex BucketType instead of pasting vertices directly into a new WTriangleMesh
667  // is performance! For example: If there are many vertices reused inside the former WTriangleMesh mesh, then we want
668  // to reuse them in the new components too. Hence we must determine if a certain vertex is already inside the new component.
669  // Since the vertices are organized in a vector, we can use std::find( v.begin, v.end(), vertexToLookUp ) which results
670  // in O(N^2) or we could use faster lookUp via key and value leading to the map and the somehow complicated BucketType.
671  typedef std::map< osg::Vec3, size_t > VertexType; // look up fast if a vertex is already inside the new mesh!
672  typedef std::vector< size_t > TriangleType;
673  typedef std::pair< VertexType, TriangleType > BucketType; // Later on the Bucket will be transformed into the new WTriangleMesh component
674  std::map< size_t, BucketType > buckets; // Key identify with the cannonical element from UnionFind the new connected component
675 
676  osg::ref_ptr< const osg::Vec3Array > vertices = mesh.getVertexArray();
677  for( size_t vID = 0; vID <= triangles.size() - 3; vID += 3 )
678  {
679  size_t component = uf.find( triangles[ vID ] );
680  if( buckets.find( component ) == buckets.end() )
681  {
682  buckets[ component ] = BucketType( VertexType(), TriangleType() ); // create new bucket
683  }
684 
685  // Note: We discard the order of the points and indices, but semantically the structure remains the same
686  VertexType& mapRef = buckets[ component ].first; // short hand alias
687  for( int i = 0; i < 3; ++i )
688  {
689  size_t id = 0;
690  const osg::Vec3& vertex = ( *vertices )[ triangles[ vID + i ] ];
691  if( mapRef.find( vertex ) == mapRef.end() )
692  {
693  id = mapRef.size(); // since size might change in next line
694  mapRef[ vertex ] = id;
695  }
696  else
697  {
698  id = mapRef[ vertex ];
699  }
700  buckets[ component ].second.push_back( id );
701  }
702  }
703 
704  for( std::map< size_t, BucketType >::const_iterator cit = buckets.begin(); cit != buckets.end(); ++cit )
705  {
706  osg::ref_ptr< osg::Vec3Array > newVertices( new osg::Vec3Array );
707  newVertices->resize( cit->second.first.size() );
708  for( VertexType::const_iterator vit = cit->second.first.begin(); vit != cit->second.first.end(); ++vit )
709  {
710  newVertices->at( vit->second ) = vit->first; // if you are sure that vit->second is always valid replace at() call with operator[]
711  }
712  boost::shared_ptr< WTriangleMesh > newMesh( new WTriangleMesh( newVertices, cit->second.second ) );
713  result->push_back( newMesh );
714  }
715 
716  return result;
717 }
718 
719 osg::ref_ptr< osg::Vec4Array > WTriangleMesh::getTriangleColors() const
720 {
721  return m_triangleColors;
722 }