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