OpenWalnut 1.3.1
WTriangleMesh.h
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 #ifndef WTRIANGLEMESH_H
00026 #define WTRIANGLEMESH_H
00027 
00028 #include <list>
00029 #include <string>
00030 #include <vector>
00031 
00032 #include <osg/Geode>
00033 
00034 #include "../common/math/linearAlgebra/WLinearAlgebra.h"
00035 #include "../common/WAssert.h"
00036 #include "../common/WColor.h"
00037 #include "../common/WTransferable.h"
00038 
00039 
00040 /**
00041  * Triangle mesh data structure allowing for convenient access of the elements.
00042  */
00043 class WTriangleMesh  : public WTransferable
00044 {
00045 friend class WTriangleMeshTest;
00046 public:
00047     /**
00048      * Shared pointer
00049      */
00050     typedef boost::shared_ptr< WTriangleMesh > SPtr;
00051 
00052     /**
00053      * Const shared pointer
00054      */
00055     typedef boost::shared_ptr< const WTriangleMesh > ConstSPtr;
00056 
00057     /**
00058      * constructor that already reserves space for a given number of triangles and vertexes
00059      *
00060      * \param vertNum
00061      * \param triangleNum
00062      */
00063     WTriangleMesh( size_t vertNum, size_t triangleNum );
00064 
00065     /**
00066      * Constructs a new mesh out of the given vertices and triangles.
00067      *
00068      * \param vertices Vec3Array storing all vertices
00069      * \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
00070      */
00071     WTriangleMesh( osg::ref_ptr< osg::Vec3Array > vertices, const std::vector< size_t >& triangles );
00072 
00073     /**
00074      * destructor
00075      */
00076     virtual ~WTriangleMesh();
00077 
00078     /**
00079      * Returns a prototype instantiated with the true type of the deriving class.
00080      *
00081      * \return the prototype.
00082      */
00083     static boost::shared_ptr< WPrototyped > getPrototype();
00084 
00085     /**
00086      * Gets the name of this prototype.
00087      *
00088      * \return the name.
00089      */
00090     virtual const std::string getName() const;
00091 
00092     /**
00093      * Gets the description for this prototype.
00094      *
00095      * \return the description
00096      */
00097     virtual const std::string getDescription() const;
00098 
00099     /**
00100      * adds a vertex position to the mesh
00101      *
00102      * \param vert
00103      */
00104     void addVertex( osg::Vec3 vert );
00105 
00106     /**
00107      * adds a vertex position to the mesh
00108      *
00109      * \param x
00110      * \param y
00111      * \param z
00112      */
00113     void addVertex( float x, float y, float z );
00114 
00115     /**
00116      * adds a vertex position to the mesh
00117      *
00118      * \param vert
00119      */
00120     void addVertex( WPosition vert );
00121 
00122     /**
00123      * Adds a texture coordinate for the vertex.
00124      *
00125      * \param texCoord the texture coordinate
00126      */
00127     void addTextureCoordinate( osg::Vec3 texCoord );
00128 
00129     /**
00130      * Adds a texture coordinate for the vertex.
00131      *
00132      * \param x texture coordinate X
00133      * \param y texture coordinate Y
00134      * \param z texture coordinate Z
00135      */
00136     void addTextureCoordinate( float x, float y, float z );
00137 
00138     /**
00139      * adds a tringle to the mesh
00140      *
00141      * \param vert0 index of the first vertex
00142      * \param vert1 index of the second vertex
00143      * \param vert2 index of the third vertex
00144      */
00145     void addTriangle( size_t vert0, size_t vert1, size_t vert2 );
00146 
00147     /**
00148      * adds a tringle and its 3 vertexes  to the mesh
00149      *
00150      * \param vert0 position of the first vertex
00151      * \param vert1 position of the second vertex
00152      * \param vert2 position of the third vertex
00153      */
00154     void addTriangle( osg::Vec3 vert0, osg::Vec3 vert1, osg::Vec3 vert2 );
00155 
00156     /**
00157      * sets a vertex to a new position
00158      *
00159      * \param index
00160      * \param vert
00161      */
00162     void setVertex( size_t index, osg::Vec3 vert );
00163 
00164     /**
00165      * sets the normal for a given vertex
00166      *
00167      * \param index
00168      * \param normal
00169      */
00170     void setVertexNormal( size_t index, osg::Vec3 normal );
00171 
00172     /**
00173      * sets the normal for a given vertex
00174      *
00175      * \param index
00176      * \param normal
00177      */
00178     void setVertexNormal( size_t index, WPosition normal );
00179 
00180     /**
00181      * sets the color for a given vertex
00182      *
00183      * \param index
00184      * \param color
00185      */
00186     void setVertexColor( size_t index, osg::Vec4 color );
00187 
00188     /**
00189      * sets the color for a given triangle
00190      *
00191      * \param index
00192      * \param color
00193      */
00194     void setTriangleColor( size_t index, osg::Vec4 color );
00195 
00196     /**
00197      * Return triangle colors
00198      *
00199      * \return OSG Vec4 Array of triangle colors
00200      */
00201     osg::ref_ptr< osg::Vec4Array > getTriangleColors() const;
00202 
00203     /**
00204      * getter
00205      *
00206      * \return pointer to the vertex array
00207      */
00208     osg::ref_ptr< osg::Vec3Array > getVertexArray();
00209 
00210     /**
00211      * Returns a const reference pointer to the vertex array.
00212      *
00213      * \return vertex array
00214      */
00215     osg::ref_ptr< const osg::Vec3Array > getVertexArray() const;
00216 
00217     /**
00218      * Returns a reference pointer to the texture coordinate array.
00219      *
00220      * \return texture coordinate array
00221      */
00222     osg::ref_ptr< osg::Vec3Array > getTextureCoordinateArray();
00223 
00224     /**
00225      * Returns a const reference pointer to the texture coordinate array.
00226      *
00227      * \return texture coordinate array
00228      */
00229     osg::ref_ptr< const osg::Vec3Array > getTextureCoordinateArray() const;
00230 
00231     /**
00232      * getter
00233      *
00234      * \param forceRecalc
00235      * \return pointer to the vertex normal array
00236      */
00237     osg::ref_ptr< osg::Vec3Array > getVertexNormalArray( bool forceRecalc = false );
00238 
00239     /**
00240      * getter
00241      *
00242      * \return pointer to the vertex color array
00243      */
00244     osg::ref_ptr< osg::Vec4Array > getVertexColorArray();
00245 
00246     /**
00247      * Returns a const reference to the vertex ids of the triangles.
00248      *
00249      * \return The triangle vertex id list
00250      */
00251     const std::vector< size_t >& getTriangles() const;
00252 
00253     /**
00254      * getter
00255      *
00256      * \param forceRecalc
00257      * \return pointer to the triangle normal array
00258      */
00259     osg::ref_ptr< osg::Vec3Array > getTriangleNormalArray( bool forceRecalc = false );
00260 
00261 
00262     /**
00263      * getter
00264      *
00265      * \param index
00266      * \return vertex
00267      */
00268     osg::Vec3 getVertex( size_t index ) const;
00269 
00270     /**
00271      * getter
00272      *
00273      * \param index
00274      * \return color
00275      */
00276     osg::Vec4 getVertColor( size_t index ) const;
00277 
00278     /**
00279      * getter
00280      *
00281      * \param triId
00282      * \param vertNum
00283      * \return vertex
00284      */
00285     osg::Vec3 getTriVert( size_t triId, size_t vertNum );
00286 
00287     /**
00288      * getter
00289      *
00290      * \param index
00291      * \return normal
00292      */
00293     WVector3d getNormal( size_t index );
00294 
00295     /**
00296      * getter
00297      *
00298      * \return number of vertices in the mesh
00299      */
00300     size_t vertSize() const;
00301 
00302     /**
00303      * getter
00304      *
00305      * \return number of triangles in the mesh
00306      */
00307     size_t triangleSize() const;
00308 
00309     /**
00310      * performs a loop subdivision on the triangle mesh
00311      */
00312     void doLoopSubD();
00313 
00314     /**
00315      * returns the id of the first vertex of a triangle
00316      *
00317      * \param triId id of the triangle
00318      * \return id of the vertex
00319      */
00320     size_t getTriVertId0( size_t triId ) const;
00321 
00322     /**
00323      * returns the id of the second vertex of a triangle
00324      *
00325      * \param triId id of the triangle
00326      * \return id of the vertex
00327      */
00328     size_t getTriVertId1( size_t triId ) const;
00329 
00330     /**
00331      * return the id of the third vertex of a triangle
00332      *
00333      * \param triId id of the triangle
00334      * \return id of the vertex
00335      */
00336     size_t getTriVertId2( size_t triId ) const;
00337 
00338     /**
00339      *  adds a mesh to the existing, no check for duplicate vertexes is performed, an additional
00340      *  vector may be specified to move the mesh to add
00341      *
00342      *  \param mesh
00343      *  \param xOff
00344      *  \param yOff
00345      *  \param zOff
00346      */
00347     void addMesh( boost::shared_ptr<WTriangleMesh> mesh, float xOff = 0., float yOff = 0., float zOff = 0. );
00348 
00349     /**
00350      *  moves the entire mesh to a new postion
00351      *
00352      *  \param xOff
00353      *  \param yOff
00354      *  \param zOff
00355      */
00356     void translateMesh( float xOff, float yOff, float zOff );
00357 
00358     /**
00359      * multiplies the vertex vectors of the mesh with a given number
00360      *
00361      * \param zoom
00362      */
00363     void zoomMesh( float zoom );
00364 
00365     /**
00366      * Checks if two meshes are exactly the same. Same number of triangles, and
00367      * points, and indices as well as same ordering. Keep in mind different
00368      * ordering might result in the same structure but is considered different
00369      * here.
00370      *
00371      * \param rhs The other mesh to compare with
00372      *
00373      * \return True if and only if both: vertices and triangles are exactly the same.
00374      */
00375     bool operator==( const WTriangleMesh& rhs ) const;
00376 
00377     /**
00378      * Rescale the vertex colors so that the maximum of all r, g and b values is 1
00379      */
00380     void rescaleVertexColors();
00381 
00382 protected:
00383     static boost::shared_ptr< WPrototyped > m_prototype; //!< The prototype as singleton.
00384 private:
00385     /**
00386      * we don't allow the standard constructor
00387      */
00388     WTriangleMesh();
00389 
00390     /**
00391      * removes a vertex from the vertex array, if any triangles still index that vertex they will be
00392      * removed if forceRemoveTriangle is true
00393      *
00394      * \param index the index of the vertex to remove
00395      */
00396     void removeVertex( size_t index );
00397 
00398     /**
00399      * removes a triangle from the mesh
00400      *
00401      * \param index the triangle to remove
00402      */
00403     void removeTriangle( size_t index );
00404 
00405     /**
00406      * recalculates the vertex normals
00407      */
00408     void recalcVertNormals();
00409 
00410     /**
00411      * calculates a normal from the 3 points in space defining a triangle
00412      *
00413      * \param triangle
00414      *
00415      * \return the normal of the triangle
00416      */
00417     osg::Vec3 calcTriangleNormal( size_t triangle );
00418 
00419     /**
00420      * calculates a normal from the 3 points in space
00421      *
00422      * \param vert0 vertex 1
00423      * \param vert1 vertex 2
00424      * \param vert2 vertex 3
00425      *
00426      * \return the normal of the plane defined by these three points
00427      */
00428     osg::Vec3 calcNormal( osg::Vec3 vert0, osg::Vec3 vert1, osg::Vec3 vert2 );
00429 
00430     /**
00431      * updates the list for which vertexes appear in which triangle
00432      */
00433     void updateVertsInTriangles();
00434 
00435     /**
00436      * calculates neighbor information for triangles
00437      */
00438     void calcNeighbors();
00439 
00440     /**
00441      * returns the triangle index of a triangle neighboring a given edge of a vertex
00442      *
00443      * \param coVert1
00444      * \param coVert2
00445      * \param triangleNum
00446      *
00447      * \return the number of the neighboring triangle.
00448      */
00449     size_t getNeighbor( const size_t coVert1, const size_t coVert2, const size_t triangleNum );
00450 
00451     /**
00452      * higher level access function to the triangle vector, sets the first vertex of a triangle to
00453      * a given vertex id
00454      *
00455      * \param triId the id of the triangle to modify
00456      * \param vertId new id of the first vertex
00457      */
00458     void setTriVert0( size_t triId, size_t vertId );
00459 
00460     /**
00461      * higher level access function to the triangle vector, sets the second vertex of a triangle to
00462      * a given vertex id
00463      *
00464      * \param triId the id of the triangle to modify
00465      * \param vertId new id of the second vertex
00466      */
00467     void setTriVert1( size_t triId, size_t vertId );
00468 
00469     /**
00470      * higher level access function to the triangle vector, sets the third vertex of a triangle to
00471      * a given vertex id
00472      *
00473      * \param triId the id of the triangle to modify
00474      * \param vertId new id of the third vertex
00475      */
00476     void setTriVert2( size_t triId, size_t vertId );
00477 
00478 
00479     // the next functions are helper functions for the loop subdivision algorithm and exist only for that
00480     // purpose, for more information read http://research.microsoft.com/en-us/um/people/cloop/thesis.pdf
00481 
00482 
00483     /**
00484      * changes the vertex ids of a triangle
00485      *
00486      * \param triId
00487      * \param vertId1
00488      * \param vertId2
00489      * \param vertId3
00490      */
00491     void loopSetTriangle( size_t triId, size_t vertId1, size_t vertId2, size_t vertId3 );
00492 
00493     /**
00494      * erases a triangle from the vertexe's list of triangles it is part of
00495      *
00496      * \param triId
00497      * \param vertId
00498      */
00499     void loopEraseTriangleFromVertex( size_t triId, size_t vertId );
00500 
00501     /**
00502      * calculates the new position of a vertex depending on it's location in the grid and number of neighbors
00503      *
00504      * \param vertId the vertex id
00505      * \return new position in 3D space
00506      */
00507     osg::Vec3 loopCalcNewPosition( size_t vertId );
00508 
00509     /**
00510      * inserts the center triangle in a given triangle,
00511      *
00512      * \param triId the triangle id
00513      */
00514     void loopInsertCenterTriangle( size_t triId );
00515 
00516     /**
00517      * inserts the 3 corner triangles in a given triangle
00518      *
00519      * \param triId the triangle id
00520      */
00521     void loopInsertCornerTriangles( size_t triId );
00522 
00523     /**
00524      * calculates the vertex id for a given edge, inserts a new vertex of none exists yet
00525      *
00526      * \param triId the triangle id
00527      * \param edgeV1
00528      * \param edgeV2
00529      * \param V3
00530      * \return index of the vertex
00531      */
00532     size_t loopCalcEdgeVert( size_t triId, size_t edgeV1, size_t edgeV2, size_t V3 );
00533 
00534     /**
00535      * loop helper function
00536      * \param n
00537      * \return alpha
00538      */
00539     double loopGetAlpha( int n );
00540 
00541     /**
00542      * returns the id of the next vertex int he triangle
00543      *
00544      * \param triNum id of the triangle
00545      * \param vertNum id of the vertex
00546      * \return id of the next vertex
00547      */
00548     size_t loopGetNextVertex( size_t triNum, size_t vertNum );
00549 
00550     /**
00551      * returns the id of the third vertex of a triangle for two given vertexes
00552      *
00553      * \param coVert1
00554      * \param coVert2
00555      * \param triangleNum
00556      * \return id of the third vertex
00557      */
00558     size_t loopGetThirdVert( size_t coVert1, size_t coVert2, size_t triangleNum );
00559 
00560 
00561     size_t m_countVerts; //!< number of vertexes in the mesh
00562 
00563     size_t m_countTriangles; //!< number of triangles in the mesh
00564 
00565     bool m_meshDirty; //!< flag indicating a change took place which requires a recalculation of components
00566 
00567     bool m_neighborsCalculated; //!< flag indicating whether the neighbor information has been calculated yet
00568 
00569     osg::ref_ptr< osg::Vec3Array > m_verts; //!< array containing the vertices
00570 
00571     osg::ref_ptr< osg::Vec3Array > m_textureCoordinates; //!< array containing the texture coordinates
00572 
00573     osg::ref_ptr< osg::Vec3Array > m_vertNormals; //!< array containing the vertex normals
00574 
00575     osg::ref_ptr< osg::Vec4Array > m_vertColors; //!< array containing vertex colors
00576 
00577     std::vector< size_t > m_triangles; //!< array containing the triangles
00578 
00579     osg::ref_ptr< osg::Vec3Array > m_triangleNormals; //!< array containing the triangle normals
00580 
00581     osg::ref_ptr< osg::Vec4Array > m_triangleColors; //!< array containing the triangle colors
00582 
00583     // helper structures
00584     std::vector < std::vector< size_t > > m_vertexIsInTriangle; //!< for each vertex, list of triangles it is part of
00585 
00586     std::vector< std::vector< size_t > > m_triangleNeighbors; //!< edge neighbors for each triangle
00587 
00588     size_t m_numTriVerts; //!< stores the number of vertexes before the loop subdivion is run, needed by the loop algorithm
00589 
00590     size_t m_numTriFaces; //!< stores the number of triangles before the loop subdivion is run, needed by the loop algorithm
00591 };
00592 
00593 /**
00594  * TriangleMesh utils
00595  */
00596 namespace tm_utils
00597 {
00598     /**
00599      * Decompose the given mesh into connected components.
00600      *
00601      * \param mesh The triangle mesh to decompose
00602      *
00603      * \return List of components where each of them is a WTriangleMesh again.
00604      */
00605     boost::shared_ptr< std::list< boost::shared_ptr< WTriangleMesh > > > componentDecomposition( const WTriangleMesh& mesh );
00606 
00607     /**
00608      * Prints for each mesh \#vertices and \#triangles, as well as each triangle with its positions. No point IDs are printed.
00609      *
00610      * \param os Output stream to print on.
00611      * \param rhs The mesh instance.
00612      *
00613      * \return The output stream again for further usage.
00614      */
00615     std::ostream& operator<<( std::ostream& os, const WTriangleMesh& rhs );
00616 }
00617 
00618 inline bool WTriangleMesh::operator==( const WTriangleMesh& rhs ) const
00619 {
00620     return std::equal( m_verts->begin(), m_verts->end(), rhs.m_verts->begin() ) &&
00621            std::equal( m_triangles.begin(), m_triangles.end(), rhs.m_triangles.begin() );
00622 }
00623 
00624 inline void WTriangleMesh::addTextureCoordinate( osg::Vec3 texCoord )
00625 {
00626     ( *m_textureCoordinates )[m_countVerts-1] = texCoord;
00627 }
00628 
00629 inline void WTriangleMesh::addTextureCoordinate( float x, float y, float z )
00630 {
00631     addTextureCoordinate( osg::Vec3( x, y, z ) );
00632 }
00633 
00634 inline void WTriangleMesh::addVertex( osg::Vec3 vert )
00635 {
00636     if( ( *m_verts ).size() == m_countVerts )
00637     {
00638         ( *m_verts ).resize( m_countVerts + 1 );
00639     }
00640     if( ( *m_textureCoordinates ).size() == m_countVerts )
00641     {
00642         ( *m_textureCoordinates ).resize( m_countVerts + 1 );
00643     }
00644     if( ( *m_vertColors ).size() == m_countVerts )
00645     {
00646         ( *m_vertColors ).resize( m_countVerts + 1 );
00647     }
00648 
00649     ( *m_verts )[m_countVerts] = vert;
00650     ++m_countVerts;
00651 }
00652 
00653 inline const std::string WTriangleMesh::getName() const
00654 {
00655     return "WTriangleMesh";
00656 }
00657 
00658 inline const std::string WTriangleMesh::getDescription() const
00659 {
00660     return "Triangle mesh data structure allowing for convenient access of the elements.";
00661 }
00662 
00663 inline void WTriangleMesh::setTriVert0( size_t triId, size_t vertId )
00664 {
00665     WAssert( triId < m_countTriangles, "set tri vert 0: triangle id out of range" );
00666     WAssert( vertId < m_countVerts, "vertex id out of range" );
00667     m_triangles[ triId * 3 ] = vertId;
00668 }
00669 
00670 inline void WTriangleMesh::setTriVert1( size_t triId, size_t vertId )
00671 {
00672     WAssert( triId < m_countTriangles, "set tri vert 1: triangle id out of range" );
00673     WAssert( vertId < m_countVerts, "vertex id out of range" );
00674     m_triangles[ triId * 3 + 1] = vertId;
00675 }
00676 
00677 inline void WTriangleMesh::setTriVert2( size_t triId, size_t vertId )
00678 {
00679     WAssert( triId < m_countTriangles, "set tri vert 2: triangle id out of range" );
00680     WAssert( vertId < m_countVerts, "vertex id out of range" );
00681     m_triangles[ triId * 3 + 2] = vertId;
00682 }
00683 
00684 inline osg::Vec3 WTriangleMesh::getTriVert( size_t triId, size_t vertNum )
00685 {
00686     WAssert( triId < m_countTriangles, "triangle id out of range" );
00687     return ( *m_verts )[ m_triangles[ triId * 3  + vertNum] ];
00688 }
00689 
00690 inline size_t WTriangleMesh::getTriVertId0( size_t triId ) const
00691 {
00692     WAssert( triId < m_countTriangles, "get tri vert id 0: triangle id out of range" );
00693     return m_triangles[triId * 3];
00694 }
00695 
00696 inline size_t WTriangleMesh::getTriVertId1( size_t triId ) const
00697 {
00698     WAssert( triId < m_countTriangles, "get tri vert id 1: triangle id out of range" );
00699     return m_triangles[triId * 3 + 1];
00700 }
00701 
00702 inline size_t WTriangleMesh::getTriVertId2( size_t triId ) const
00703 {
00704     WAssert( triId < m_countTriangles, "get tri vert id 2: triangle id out of range" );
00705     return m_triangles[triId * 3 + 2];
00706 }
00707 
00708 inline void WTriangleMesh::setVertex( size_t index, osg::Vec3 vert )
00709 {
00710     ( *m_verts )[index] = vert;
00711 }
00712 
00713 #endif  // WTRIANGLEMESH_H