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