OpenWalnut  1.3.1
WTriangleMesh.h
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 #ifndef WTRIANGLEMESH_H
26 #define WTRIANGLEMESH_H
27 
28 #include <list>
29 #include <string>
30 #include <vector>
31 
32 #include <osg/Geode>
33 
34 #include "../common/math/linearAlgebra/WLinearAlgebra.h"
35 #include "../common/WAssert.h"
36 #include "../common/WColor.h"
37 #include "../common/WTransferable.h"
38 
39 
40 /**
41  * Triangle mesh data structure allowing for convenient access of the elements.
42  */
44 {
45 friend class WTriangleMeshTest;
46 public:
47  /**
48  * Shared pointer
49  */
50  typedef boost::shared_ptr< WTriangleMesh > SPtr;
51 
52  /**
53  * Const shared pointer
54  */
55  typedef boost::shared_ptr< const WTriangleMesh > ConstSPtr;
56 
57  /**
58  * constructor that already reserves space for a given number of triangles and vertexes
59  *
60  * \param vertNum
61  * \param triangleNum
62  */
63  WTriangleMesh( size_t vertNum, size_t triangleNum );
64 
65  /**
66  * Constructs a new mesh out of the given vertices and triangles.
67  *
68  * \param vertices Vec3Array storing all vertices
69  * \param triangles Vector of consecutive vertex indices where each 3 IDs are a triangle starting at 0,1,2 for first triangle 3,4,5 for the second
70  */
71  WTriangleMesh( osg::ref_ptr< osg::Vec3Array > vertices, const std::vector< size_t >& triangles );
72 
73  /**
74  * destructor
75  */
76  virtual ~WTriangleMesh();
77 
78  /**
79  * Returns a prototype instantiated with the true type of the deriving class.
80  *
81  * \return the prototype.
82  */
83  static boost::shared_ptr< WPrototyped > getPrototype();
84 
85  /**
86  * Gets the name of this prototype.
87  *
88  * \return the name.
89  */
90  virtual const std::string getName() const;
91 
92  /**
93  * Gets the description for this prototype.
94  *
95  * \return the description
96  */
97  virtual const std::string getDescription() const;
98 
99  /**
100  * adds a vertex position to the mesh
101  *
102  * \param vert
103  */
104  void addVertex( osg::Vec3 vert );
105 
106  /**
107  * adds a vertex position to the mesh
108  *
109  * \param x
110  * \param y
111  * \param z
112  */
113  void addVertex( float x, float y, float z );
114 
115  /**
116  * adds a vertex position to the mesh
117  *
118  * \param vert
119  */
120  void addVertex( WPosition vert );
121 
122  /**
123  * Adds a texture coordinate for the vertex.
124  *
125  * \param texCoord the texture coordinate
126  */
127  void addTextureCoordinate( osg::Vec3 texCoord );
128 
129  /**
130  * Adds a texture coordinate for the vertex.
131  *
132  * \param x texture coordinate X
133  * \param y texture coordinate Y
134  * \param z texture coordinate Z
135  */
136  void addTextureCoordinate( float x, float y, float z );
137 
138  /**
139  * adds a tringle to the mesh
140  *
141  * \param vert0 index of the first vertex
142  * \param vert1 index of the second vertex
143  * \param vert2 index of the third vertex
144  */
145  void addTriangle( size_t vert0, size_t vert1, size_t vert2 );
146 
147  /**
148  * adds a tringle and its 3 vertexes to the mesh
149  *
150  * \param vert0 position of the first vertex
151  * \param vert1 position of the second vertex
152  * \param vert2 position of the third vertex
153  */
154  void addTriangle( osg::Vec3 vert0, osg::Vec3 vert1, osg::Vec3 vert2 );
155 
156  /**
157  * sets a vertex to a new position
158  *
159  * \param index
160  * \param vert
161  */
162  void setVertex( size_t index, osg::Vec3 vert );
163 
164  /**
165  * sets the normal for a given vertex
166  *
167  * \param index
168  * \param normal
169  */
170  void setVertexNormal( size_t index, osg::Vec3 normal );
171 
172  /**
173  * sets the normal for a given vertex
174  *
175  * \param index
176  * \param normal
177  */
178  void setVertexNormal( size_t index, WPosition normal );
179 
180  /**
181  * sets the color for a given vertex
182  *
183  * \param index
184  * \param color
185  */
186  void setVertexColor( size_t index, osg::Vec4 color );
187 
188  /**
189  * sets the color for a given triangle
190  *
191  * \param index
192  * \param color
193  */
194  void setTriangleColor( size_t index, osg::Vec4 color );
195 
196  /**
197  * Return triangle colors
198  *
199  * \return OSG Vec4 Array of triangle colors
200  */
201  osg::ref_ptr< osg::Vec4Array > getTriangleColors() const;
202 
203  /**
204  * getter
205  *
206  * \return pointer to the vertex array
207  */
208  osg::ref_ptr< osg::Vec3Array > getVertexArray();
209 
210  /**
211  * Returns a const reference pointer to the vertex array.
212  *
213  * \return vertex array
214  */
215  osg::ref_ptr< const osg::Vec3Array > getVertexArray() const;
216 
217  /**
218  * Returns a reference pointer to the texture coordinate array.
219  *
220  * \return texture coordinate array
221  */
222  osg::ref_ptr< osg::Vec3Array > getTextureCoordinateArray();
223 
224  /**
225  * Returns a const reference pointer to the texture coordinate array.
226  *
227  * \return texture coordinate array
228  */
229  osg::ref_ptr< const osg::Vec3Array > getTextureCoordinateArray() const;
230 
231  /**
232  * getter
233  *
234  * \param forceRecalc
235  * \return pointer to the vertex normal array
236  */
237  osg::ref_ptr< osg::Vec3Array > getVertexNormalArray( bool forceRecalc = false );
238 
239  /**
240  * getter
241  *
242  * \return pointer to the vertex color array
243  */
244  osg::ref_ptr< osg::Vec4Array > getVertexColorArray();
245 
246  /**
247  * Returns a const reference to the vertex ids of the triangles.
248  *
249  * \return The triangle vertex id list
250  */
251  const std::vector< size_t >& getTriangles() const;
252 
253  /**
254  * getter
255  *
256  * \param forceRecalc
257  * \return pointer to the triangle normal array
258  */
259  osg::ref_ptr< osg::Vec3Array > getTriangleNormalArray( bool forceRecalc = false );
260 
261 
262  /**
263  * getter
264  *
265  * \param index
266  * \return vertex
267  */
268  osg::Vec3 getVertex( size_t index ) const;
269 
270  /**
271  * getter
272  *
273  * \param index
274  * \return color
275  */
276  osg::Vec4 getVertColor( size_t index ) const;
277 
278  /**
279  * getter
280  *
281  * \param triId
282  * \param vertNum
283  * \return vertex
284  */
285  osg::Vec3 getTriVert( size_t triId, size_t vertNum );
286 
287  /**
288  * getter
289  *
290  * \param index
291  * \return normal
292  */
293  WVector3d getNormal( size_t index );
294 
295  /**
296  * getter
297  *
298  * \return number of vertices in the mesh
299  */
300  size_t vertSize() const;
301 
302  /**
303  * getter
304  *
305  * \return number of triangles in the mesh
306  */
307  size_t triangleSize() const;
308 
309  /**
310  * performs a loop subdivision on the triangle mesh
311  */
312  void doLoopSubD();
313 
314  /**
315  * returns the id of the first vertex of a triangle
316  *
317  * \param triId id of the triangle
318  * \return id of the vertex
319  */
320  size_t getTriVertId0( size_t triId ) const;
321 
322  /**
323  * returns the id of the second vertex of a triangle
324  *
325  * \param triId id of the triangle
326  * \return id of the vertex
327  */
328  size_t getTriVertId1( size_t triId ) const;
329 
330  /**
331  * return the id of the third vertex of a triangle
332  *
333  * \param triId id of the triangle
334  * \return id of the vertex
335  */
336  size_t getTriVertId2( size_t triId ) const;
337 
338  /**
339  * adds a mesh to the existing, no check for duplicate vertexes is performed, an additional
340  * vector may be specified to move the mesh to add
341  *
342  * \param mesh
343  * \param xOff
344  * \param yOff
345  * \param zOff
346  */
347  void addMesh( boost::shared_ptr<WTriangleMesh> mesh, float xOff = 0., float yOff = 0., float zOff = 0. );
348 
349  /**
350  * moves the entire mesh to a new postion
351  *
352  * \param xOff
353  * \param yOff
354  * \param zOff
355  */
356  void translateMesh( float xOff, float yOff, float zOff );
357 
358  /**
359  * multiplies the vertex vectors of the mesh with a given number
360  *
361  * \param zoom
362  */
363  void zoomMesh( float zoom );
364 
365  /**
366  * Checks if two meshes are exactly the same. Same number of triangles, and
367  * points, and indices as well as same ordering. Keep in mind different
368  * ordering might result in the same structure but is considered different
369  * here.
370  *
371  * \param rhs The other mesh to compare with
372  *
373  * \return True if and only if both: vertices and triangles are exactly the same.
374  */
375  bool operator==( const WTriangleMesh& rhs ) const;
376 
377  /**
378  * Rescale the vertex colors so that the maximum of all r, g and b values is 1
379  */
380  void rescaleVertexColors();
381 
382 protected:
383  static boost::shared_ptr< WPrototyped > m_prototype; //!< The prototype as singleton.
384 private:
385  /**
386  * we don't allow the standard constructor
387  */
388  WTriangleMesh();
389 
390  /**
391  * removes a vertex from the vertex array, if any triangles still index that vertex they will be
392  * removed if forceRemoveTriangle is true
393  *
394  * \param index the index of the vertex to remove
395  */
396  void removeVertex( size_t index );
397 
398  /**
399  * removes a triangle from the mesh
400  *
401  * \param index the triangle to remove
402  */
403  void removeTriangle( size_t index );
404 
405  /**
406  * recalculates the vertex normals
407  */
408  void recalcVertNormals();
409 
410  /**
411  * calculates a normal from the 3 points in space defining a triangle
412  *
413  * \param triangle
414  *
415  * \return the normal of the triangle
416  */
417  osg::Vec3 calcTriangleNormal( size_t triangle );
418 
419  /**
420  * calculates a normal from the 3 points in space
421  *
422  * \param vert0 vertex 1
423  * \param vert1 vertex 2
424  * \param vert2 vertex 3
425  *
426  * \return the normal of the plane defined by these three points
427  */
428  osg::Vec3 calcNormal( osg::Vec3 vert0, osg::Vec3 vert1, osg::Vec3 vert2 );
429 
430  /**
431  * updates the list for which vertexes appear in which triangle
432  */
433  void updateVertsInTriangles();
434 
435  /**
436  * calculates neighbor information for triangles
437  */
438  void calcNeighbors();
439 
440  /**
441  * returns the triangle index of a triangle neighboring a given edge of a vertex
442  *
443  * \param coVert1
444  * \param coVert2
445  * \param triangleNum
446  *
447  * \return the number of the neighboring triangle.
448  */
449  size_t getNeighbor( const size_t coVert1, const size_t coVert2, const size_t triangleNum );
450 
451  /**
452  * higher level access function to the triangle vector, sets the first vertex of a triangle to
453  * a given vertex id
454  *
455  * \param triId the id of the triangle to modify
456  * \param vertId new id of the first vertex
457  */
458  void setTriVert0( size_t triId, size_t vertId );
459 
460  /**
461  * higher level access function to the triangle vector, sets the second vertex of a triangle to
462  * a given vertex id
463  *
464  * \param triId the id of the triangle to modify
465  * \param vertId new id of the second vertex
466  */
467  void setTriVert1( size_t triId, size_t vertId );
468 
469  /**
470  * higher level access function to the triangle vector, sets the third vertex of a triangle to
471  * a given vertex id
472  *
473  * \param triId the id of the triangle to modify
474  * \param vertId new id of the third vertex
475  */
476  void setTriVert2( size_t triId, size_t vertId );
477 
478 
479  // the next functions are helper functions for the loop subdivision algorithm and exist only for that
480  // purpose, for more information read http://research.microsoft.com/en-us/um/people/cloop/thesis.pdf
481 
482 
483  /**
484  * changes the vertex ids of a triangle
485  *
486  * \param triId
487  * \param vertId1
488  * \param vertId2
489  * \param vertId3
490  */
491  void loopSetTriangle( size_t triId, size_t vertId1, size_t vertId2, size_t vertId3 );
492 
493  /**
494  * erases a triangle from the vertexe's list of triangles it is part of
495  *
496  * \param triId
497  * \param vertId
498  */
499  void loopEraseTriangleFromVertex( size_t triId, size_t vertId );
500 
501  /**
502  * calculates the new position of a vertex depending on it's location in the grid and number of neighbors
503  *
504  * \param vertId the vertex id
505  * \return new position in 3D space
506  */
507  osg::Vec3 loopCalcNewPosition( size_t vertId );
508 
509  /**
510  * inserts the center triangle in a given triangle,
511  *
512  * \param triId the triangle id
513  */
514  void loopInsertCenterTriangle( size_t triId );
515 
516  /**
517  * inserts the 3 corner triangles in a given triangle
518  *
519  * \param triId the triangle id
520  */
521  void loopInsertCornerTriangles( size_t triId );
522 
523  /**
524  * calculates the vertex id for a given edge, inserts a new vertex of none exists yet
525  *
526  * \param triId the triangle id
527  * \param edgeV1
528  * \param edgeV2
529  * \param V3
530  * \return index of the vertex
531  */
532  size_t loopCalcEdgeVert( size_t triId, size_t edgeV1, size_t edgeV2, size_t V3 );
533 
534  /**
535  * loop helper function
536  * \param n
537  * \return alpha
538  */
539  double loopGetAlpha( int n );
540 
541  /**
542  * returns the id of the next vertex int he triangle
543  *
544  * \param triNum id of the triangle
545  * \param vertNum id of the vertex
546  * \return id of the next vertex
547  */
548  size_t loopGetNextVertex( size_t triNum, size_t vertNum );
549 
550  /**
551  * returns the id of the third vertex of a triangle for two given vertexes
552  *
553  * \param coVert1
554  * \param coVert2
555  * \param triangleNum
556  * \return id of the third vertex
557  */
558  size_t loopGetThirdVert( size_t coVert1, size_t coVert2, size_t triangleNum );
559 
560 
561  size_t m_countVerts; //!< number of vertexes in the mesh
562 
563  size_t m_countTriangles; //!< number of triangles in the mesh
564 
565  bool m_meshDirty; //!< flag indicating a change took place which requires a recalculation of components
566 
567  bool m_neighborsCalculated; //!< flag indicating whether the neighbor information has been calculated yet
568 
569  osg::ref_ptr< osg::Vec3Array > m_verts; //!< array containing the vertices
570 
571  osg::ref_ptr< osg::Vec3Array > m_textureCoordinates; //!< array containing the texture coordinates
572 
573  osg::ref_ptr< osg::Vec3Array > m_vertNormals; //!< array containing the vertex normals
574 
575  osg::ref_ptr< osg::Vec4Array > m_vertColors; //!< array containing vertex colors
576 
577  std::vector< size_t > m_triangles; //!< array containing the triangles
578 
579  osg::ref_ptr< osg::Vec3Array > m_triangleNormals; //!< array containing the triangle normals
580 
581  osg::ref_ptr< osg::Vec4Array > m_triangleColors; //!< array containing the triangle colors
582 
583  // helper structures
584  std::vector < std::vector< size_t > > m_vertexIsInTriangle; //!< for each vertex, list of triangles it is part of
585 
586  std::vector< std::vector< size_t > > m_triangleNeighbors; //!< edge neighbors for each triangle
587 
588  size_t m_numTriVerts; //!< stores the number of vertexes before the loop subdivion is run, needed by the loop algorithm
589 
590  size_t m_numTriFaces; //!< stores the number of triangles before the loop subdivion is run, needed by the loop algorithm
591 };
592 
593 /**
594  * TriangleMesh utils
595  */
596 namespace tm_utils
597 {
598  /**
599  * Decompose the given mesh into connected components.
600  *
601  * \param mesh The triangle mesh to decompose
602  *
603  * \return List of components where each of them is a WTriangleMesh again.
604  */
605  boost::shared_ptr< std::list< boost::shared_ptr< WTriangleMesh > > > componentDecomposition( const WTriangleMesh& mesh );
606 
607  /**
608  * Prints for each mesh \#vertices and \#triangles, as well as each triangle with its positions. No point IDs are printed.
609  *
610  * \param os Output stream to print on.
611  * \param rhs The mesh instance.
612  *
613  * \return The output stream again for further usage.
614  */
615  std::ostream& operator<<( std::ostream& os, const WTriangleMesh& rhs );
616 }
617 
618 inline bool WTriangleMesh::operator==( const WTriangleMesh& rhs ) const
619 {
620  return std::equal( m_verts->begin(), m_verts->end(), rhs.m_verts->begin() ) &&
621  std::equal( m_triangles.begin(), m_triangles.end(), rhs.m_triangles.begin() );
622 }
623 
624 inline void WTriangleMesh::addTextureCoordinate( osg::Vec3 texCoord )
625 {
626  ( *m_textureCoordinates )[m_countVerts-1] = texCoord;
627 }
628 
629 inline void WTriangleMesh::addTextureCoordinate( float x, float y, float z )
630 {
631  addTextureCoordinate( osg::Vec3( x, y, z ) );
632 }
633 
634 inline void WTriangleMesh::addVertex( osg::Vec3 vert )
635 {
636  if( ( *m_verts ).size() == m_countVerts )
637  {
638  ( *m_verts ).resize( m_countVerts + 1 );
639  }
640  if( ( *m_textureCoordinates ).size() == m_countVerts )
641  {
642  ( *m_textureCoordinates ).resize( m_countVerts + 1 );
643  }
644  if( ( *m_vertColors ).size() == m_countVerts )
645  {
646  ( *m_vertColors ).resize( m_countVerts + 1 );
647  }
648 
649  ( *m_verts )[m_countVerts] = vert;
650  ++m_countVerts;
651 }
652 
653 inline const std::string WTriangleMesh::getName() const
654 {
655  return "WTriangleMesh";
656 }
657 
658 inline const std::string WTriangleMesh::getDescription() const
659 {
660  return "Triangle mesh data structure allowing for convenient access of the elements.";
661 }
662 
663 inline void WTriangleMesh::setTriVert0( size_t triId, size_t vertId )
664 {
665  WAssert( triId < m_countTriangles, "set tri vert 0: triangle id out of range" );
666  WAssert( vertId < m_countVerts, "vertex id out of range" );
667  m_triangles[ triId * 3 ] = vertId;
668 }
669 
670 inline void WTriangleMesh::setTriVert1( size_t triId, size_t vertId )
671 {
672  WAssert( triId < m_countTriangles, "set tri vert 1: triangle id out of range" );
673  WAssert( vertId < m_countVerts, "vertex id out of range" );
674  m_triangles[ triId * 3 + 1] = vertId;
675 }
676 
677 inline void WTriangleMesh::setTriVert2( size_t triId, size_t vertId )
678 {
679  WAssert( triId < m_countTriangles, "set tri vert 2: triangle id out of range" );
680  WAssert( vertId < m_countVerts, "vertex id out of range" );
681  m_triangles[ triId * 3 + 2] = vertId;
682 }
683 
684 inline osg::Vec3 WTriangleMesh::getTriVert( size_t triId, size_t vertNum )
685 {
686  WAssert( triId < m_countTriangles, "triangle id out of range" );
687  return ( *m_verts )[ m_triangles[ triId * 3 + vertNum] ];
688 }
689 
690 inline size_t WTriangleMesh::getTriVertId0( size_t triId ) const
691 {
692  WAssert( triId < m_countTriangles, "get tri vert id 0: triangle id out of range" );
693  return m_triangles[triId * 3];
694 }
695 
696 inline size_t WTriangleMesh::getTriVertId1( size_t triId ) const
697 {
698  WAssert( triId < m_countTriangles, "get tri vert id 1: triangle id out of range" );
699  return m_triangles[triId * 3 + 1];
700 }
701 
702 inline size_t WTriangleMesh::getTriVertId2( size_t triId ) const
703 {
704  WAssert( triId < m_countTriangles, "get tri vert id 2: triangle id out of range" );
705  return m_triangles[triId * 3 + 2];
706 }
707 
708 inline void WTriangleMesh::setVertex( size_t index, osg::Vec3 vert )
709 {
710  ( *m_verts )[index] = vert;
711 }
712 
713 #endif // WTRIANGLEMESH_H