The Parametric Pseudo-Manifold (PPS) Library 1.0
surface.h
Go to the documentation of this file.
00001 
00026 #ifndef SURFACE_H
00027 #define SURFACE_H
00028 
00029 #include "vertex.h"    // Vertex
00030 #include "halfedge.h"  // Halfedge
00031 #include "edge.h"      // Edge
00032 #include "face.h"      // Face
00033 
00034 #include <cassert>     // assert
00035 #include <list>        // std::list
00036 #include <map>         // std::map
00037 
00038 
00055 namespace dcel {
00056 
00057 
00064   template < 
00065              typename VAttrib = int ,
00066              typename FAttrib = int ,
00067              typename EAttrib = int ,
00068              typename HAttrib = int 
00069            >
00070   class Surface {
00071   public:
00072     // ---------------------------------------------------------------
00073     //
00074     // Type definitions
00075     //
00076     // ---------------------------------------------------------------
00077 
00084     typedef dcel::Vertex< VAttrib, FAttrib , EAttrib , HAttrib > Vertex ;
00085 
00092     typedef dcel::Face< VAttrib, FAttrib , EAttrib , HAttrib > Face ;
00093 
00100     typedef dcel::Edge< VAttrib, FAttrib , EAttrib , HAttrib > Edge ;
00101 
00108     typedef dcel::Halfedge< VAttrib, FAttrib , EAttrib , HAttrib > Halfedge ;
00109 
00116     typedef typename std::list< Vertex* >::const_iterator VertexIterator ;
00117 
00118 
00124     typedef typename std::list< Edge* >::const_iterator EdgeIterator ;
00125 
00126 
00132     typedef typename std::list< Face* >::const_iterator FaceIterator ;
00133 
00134 
00141     typedef typename std::map< unsigned , Vertex* > VMAP ;
00142 
00143 
00150     typedef typename std::map< std::pair< unsigned , unsigned > ,
00151                                                Halfedge* > HMAP ;
00152  
00153 
00154     // ---------------------------------------------------------------
00155     //
00156     // Public methods
00157     //
00158     // ---------------------------------------------------------------
00159 
00171     Surface(
00172             unsigned nverts ,
00173             double* lverts ,
00174             unsigned nfaces ,
00175             unsigned* lfaces
00176            ) ;
00177 
00178 
00184     virtual ~Surface() ;
00185 
00186 
00194     inline unsigned get_number_of_vertices() const
00195     {
00196       return _list_of_vertices.size() ;
00197     }
00198 
00199 
00208     inline unsigned get_number_of_edges() const
00209     { 
00210       return _list_of_edges.size() ; 
00211     }
00212 
00213 
00221     inline unsigned get_number_of_faces() const
00222     { 
00223       return _list_of_faces.size() ; 
00224     }
00225 
00226 
00236     inline VertexIterator vertices_begin() const
00237     { 
00238       return _list_of_vertices.begin() ;
00239     }
00240 
00241 
00251     inline EdgeIterator edges_begin() const
00252     {
00253       return _list_of_edges.begin() ;  
00254     }
00255 
00256 
00265     FaceIterator faces_begin() const
00266     {
00267       return _list_of_faces.begin() ;  
00268     }
00269 
00270 
00280     inline VertexIterator vertices_end() const
00281     { 
00282       return _list_of_vertices.end() ;
00283     }
00284 
00285 
00295     inline EdgeIterator edges_end() const
00296     {
00297       return _list_of_edges.end() ;  
00298     }
00299 
00300 
00309     FaceIterator faces_end() const
00310     {
00311       return _list_of_faces.end() ;  
00312     }
00313 
00321     void add_vertex(Vertex *v) {
00322 
00323         _list_of_vertices.push_back(v);
00324     }
00325 
00333     void add_face(Face *f) {
00334 
00335         _list_of_faces.push_back(f);
00336     }
00337 
00345     void add_edge(Edge* e) {
00346 
00347         _list_of_edges.push_back(e);
00348     }
00349 
00350 
00351   private:
00352     // ---------------------------------------------------------------
00353     //
00354     // Private methods
00355     //
00356     // ---------------------------------------------------------------
00357 
00367     void create_vertices(
00368                          unsigned nverts , 
00369                          double* lverts , 
00370                          VMAP& vmap 
00371                         ) ;
00372 
00373 
00385     void create_faces( unsigned nfaces , unsigned* lfaces , HMAP& hmap , VMAP& vmap ) ;
00386 
00387 
00396     void create_edges( HMAP& hmap ) ;
00397 
00398 
00408     bool is_consistent() const ;
00409 
00410 
00411   protected:
00412 
00413     // ---------------------------------------------------------------
00414     //
00415     // Protected data members
00416     //
00417     // ---------------------------------------------------------------
00418 
00419     std::list< Vertex* > _list_of_vertices ;  
00420 
00421 
00422     std::list< Edge* > _list_of_edges ;  
00423 
00424 
00425     std::list< Face* > _list_of_faces ;  
00426 
00427   } ;
00428 
00429 
00441   template < 
00442              typename VAttrib ,
00443              typename FAttrib ,
00444              typename EAttrib ,
00445              typename HAttrib 
00446            >
00447   Surface< VAttrib , FAttrib , EAttrib , HAttrib >::Surface(
00448      unsigned nverts ,
00449      double* lverts ,
00450      unsigned nfaces ,
00451      unsigned* lfaces 
00452     )
00453   {
00454     //
00455     // Create the vertices of the surface.
00456     //
00457 
00459     VMAP vmap ;
00460 
00462     create_vertices( nverts , lverts , vmap ) ;
00463 
00464     //
00465     // Create the faces and halfedges of the surface.
00466     //
00467 
00469     HMAP hmap ;
00470 
00472     create_faces( nfaces , lfaces , hmap , vmap ) ;
00473 
00475     vmap.clear();
00476 
00477     //
00478     // Create the edges of the surface.
00479     //
00480     create_edges( hmap ) ;
00481 
00483     hmap.clear();
00484 
00486     assert( is_consistent() ) ;
00487 
00488     return ;
00489   }
00490 
00491 
00497   template < 
00498              typename VAttrib ,
00499              typename FAttrib ,
00500              typename EAttrib ,
00501              typename HAttrib 
00502            >
00503   Surface< VAttrib , FAttrib , EAttrib , HAttrib >::~Surface()
00504   {
00508     for( VertexIterator vit = vertices_begin() ; vit != vertices_end() ; ++vit ) {
00509       Vertex* vertex = *vit ;
00510 
00511       if ( vertex != 0 ) delete vertex ;
00512     }
00513 
00514     _list_of_vertices.clear() ;
00515 
00519     for( EdgeIterator eit = edges_begin() ; eit != edges_end() ; ++eit ) {
00520       Edge* edge = *eit ;
00521 
00522       Halfedge* h1 = edge->get_first_halfedge() ;
00523       Halfedge* h2 = edge->get_second_halfedge() ;
00524 
00525       if ( h1 != 0 ) delete h1 ;
00526       if ( h2 != 0 ) delete h2 ;
00527 
00528       if ( edge != 0 ) delete edge ;
00529     }
00530 
00531     _list_of_edges.clear() ;
00532 
00536     for( FaceIterator fit = faces_begin() ; fit != faces_end() ; ++fit ) {
00537       Face* face = *fit ;
00538 
00539       if ( face != 0 ) delete face ;
00540     }
00541 
00542     _list_of_faces.clear() ;
00543 
00544     return;
00545   }
00546 
00547 
00557   template < 
00558              typename VAttrib ,
00559              typename FAttrib ,
00560              typename EAttrib ,
00561              typename HAttrib 
00562            >
00563   void
00564   Surface< VAttrib , FAttrib , EAttrib , HAttrib >::create_vertices(
00565      unsigned nverts ,
00566      double* lverts ,
00567      VMAP& vmap
00568     )
00569   {
00575     for ( unsigned i = 0 ; i < nverts ; i++ ) {
00577       const unsigned j = 3 * i;
00578 
00580       Vertex* vertex = new Vertex( 
00581                                   lverts[ j     ] ,
00582                                   lverts[ j + 1 ] ,
00583                                   lverts[ j + 2 ] ,
00584                                   0
00585                                  ) ;
00586 
00588       vmap.insert( std::make_pair( i , vertex ) ) ;
00589     }
00590 
00591     return ;
00592   }
00593 
00594 
00606   template < 
00607              typename VAttrib ,
00608              typename FAttrib ,
00609              typename EAttrib ,
00610              typename HAttrib 
00611            >
00612   void
00613   Surface< VAttrib , FAttrib , EAttrib , HAttrib >::create_faces(
00614                                                                  unsigned nfaces ,
00615                                                                  unsigned* lfaces ,
00616                                                                  HMAP& hmap ,
00617                                                                  VMAP& vmap
00618                                                                 )
00619   {
00625     for ( unsigned i = 0 ; i < nfaces ; i++ ) {
00627       unsigned j = 3 * i ;
00628 
00630       Face* face = new Face( 0 ) ;
00631 
00632       //
00633       // Create the three half-edges of the i-th face.
00634       //
00635 
00636       Halfedge* h[ 3 ] ;
00637 
00638       for ( unsigned k = 0 ; k < 3 ; k++ ) {
00642         typename VMAP::const_iterator vit = vmap.find( lfaces[ j + k ] ) ;
00643 
00647         assert( vit != vmap.end() ) ;
00648 
00649         Vertex* vertex = vit->second ;
00650 
00654         h[ k ] = new Halfedge(
00655                               vertex ,
00656                               0 ,
00657                               face ,
00658                               0 ,
00659                               0
00660                              ) ;
00661 
00665         vertex->set_halfedge( h[ k ] ) ;
00666       }
00667 
00671       h[ 0 ]->set_prev( h[ 2 ] ) ;
00672       h[ 2 ]->set_next( h[ 0 ] ) ;
00673 
00674       h[ 1 ]->set_prev( h[ 0 ] ) ;
00675       h[ 0 ]->set_next( h[ 1 ] ) ;
00676 
00677       h[ 2 ]->set_prev( h[ 1 ] ) ;
00678       h[ 1 ]->set_next( h[ 2 ] ) ;
00679 
00683       face->set_halfedge( h[ 0 ] ) ;
00684 
00685 
00689       for ( unsigned k = 0 ; k < 3 ; k++ ) {
00690         const unsigned v1 = lfaces[ j +     k             ] ;
00691         const unsigned v2 = lfaces[ j + ( ( k + 1 ) % 3 ) ] ;
00692 
00693         hmap.insert( std::make_pair( std::make_pair( v1 , v2 ) , h[ k ] ) ) ;
00694       }
00695 
00699       _list_of_faces.push_back( face ) ;
00700     }
00701 
00707     for ( typename VMAP::iterator vit = vmap.begin() ; 
00708           vit != vmap.end() ; vit++ ) {
00709       if ( vit->second->get_halfedge() != 0 ) {
00710         _list_of_vertices.push_back( vit->second ) ;
00711       }
00712       else {
00713         delete vit->second ;
00714         vit->second = 0 ;
00715       }
00716     }
00717 
00718     return ;
00719   }
00720 
00721 
00729   template < 
00730              typename VAttrib ,
00731              typename FAttrib ,
00732              typename EAttrib ,
00733              typename HAttrib 
00734            >
00735   void
00736   Surface< VAttrib , FAttrib , EAttrib , HAttrib >::create_edges( HMAP& hmap )
00737   {
00744     for ( typename HMAP::iterator hit = hmap.begin(); 
00745           hit != hmap.end(); ++hit ) {
00751       if ( hit->second->get_edge() == 0 ) {
00756         Edge* edge = new Edge( hit->second , 0 ) ;
00757 
00761         hit->second->set_edge( edge ) ;
00762 
00767         _list_of_edges.push_back( edge ) ;
00768 
00772         unsigned v1 = hit->first.first ;
00773         unsigned v2 = hit->first.second ;
00774 
00778         typename HMAP::iterator ait = 
00779           hmap.find( std::make_pair( v2 , v1 ) ) ;
00780 
00781         if ( ait != hmap.end() ) {
00782           ait->second->set_edge( edge ) ;
00783           edge->set_second_halfedge( ait->second ) ;
00784         }
00785 
00786       }
00787     }
00788 
00789     return ;
00790   }
00791 
00792 
00801   template < 
00802              typename VAttrib ,
00803              typename FAttrib ,
00804              typename EAttrib ,
00805              typename HAttrib
00806            >
00807   bool
00808   Surface< VAttrib , FAttrib , EAttrib , HAttrib >::is_consistent() const
00809   {
00810     //
00811     // Check half-edge and face pointers. 
00812     //
00813 
00814     for ( FaceIterator fit = faces_begin(); fit != faces_end() ; ++fit ) {
00819       Halfedge* h1 = ( *fit )->get_halfedge() ;
00820 
00824       if ( h1 == 0 ) return false ;
00825 
00829       Halfedge* h2 = h1->get_next() ;
00830       Halfedge* h3 = h1->get_prev() ;
00831 
00836       if ( ( h2 == 0 ) || ( h3 == 0 ) ) return false ;
00837 
00841       if ( ( h1->get_face() == 0 ) || ( h2->get_face() == 0 ) ||
00842            ( h3->get_face() == 0 ) )
00843       {
00844         return false ;
00845       }
00846 
00850       if ( ( h1->get_face() != h2->get_face() ) ||
00851            ( h1->get_face() != h3->get_face() ) ||
00852            ( h2->get_face() != h3->get_face() ) )
00853       {
00854         return false ;
00855       }
00856 
00860       if ( h2->get_prev() != h1 ) return false ;
00861 
00862       if ( h3->get_next() != h1 ) return false ;
00863 
00864       if ( h2->get_next() != h3 ) return false ;
00865 
00866       if ( h3->get_prev() != h2 ) return false ;
00867 
00871       if ( h1->get_origin() == 0 ) return false ;
00872 
00873       if ( h2->get_origin() == 0 ) return false ;
00874 
00875       if ( h3->get_origin() == 0 ) return false ;
00876 
00880       if ( h1->get_edge() == 0 ) return false ;
00881 
00882       if ( h2->get_edge() == 0 ) return false ;
00883 
00884       if ( h3->get_edge() == 0 ) return false ;
00885 
00889       if ( 
00890           ( h1 != h1->get_edge()->get_first_halfedge()  ) &&
00891           ( h1 != h1->get_edge()->get_second_halfedge() ) 
00892          )
00893       {
00894         return false ;
00895       }
00896 
00897       if ( 
00898           ( h2 != h2->get_edge()->get_first_halfedge()  ) &&
00899           ( h2 != h2->get_edge()->get_second_halfedge() ) 
00900          )
00901       {
00902         return false ;
00903       }
00904 
00905       if ( 
00906           ( h3 != h3->get_edge()->get_first_halfedge()  ) &&
00907           ( h3 != h3->get_edge()->get_second_halfedge() ) 
00908          )
00909       {
00910         return false ;
00911       }
00912 
00916       if ( h1->get_mate() == 0 ) return false ;
00917 
00918       if ( h2->get_mate() == 0 ) return false ;
00919 
00920       if ( h3->get_mate() == 0 ) return false ;
00921 
00922       if ( h1->get_mate()->get_mate() != h1 ) return false ;
00923 
00924       if ( h2->get_mate()->get_mate() != h2 ) return false ;
00925 
00926       if ( h3->get_mate()->get_mate() != h3 ) return false ;
00927 
00928     } 
00929     // end of the for loop for checking faces.
00930 
00931     //
00932     // Check vertex pointers.
00933     //
00934 
00935     for ( VertexIterator vit = vertices_begin() ; vit != vertices_end() ; ++vit ) {
00940       Halfedge* h1 = ( *vit )->get_halfedge() ;
00941 
00945       if ( h1 == 0 ) return false ;
00946 
00951       if ( h1->get_origin() != *vit ) return false ;
00952 
00958       Halfedge* h2 = h1->get_prev()->get_mate() ;
00959       do {
00964         if ( h2->get_origin() != *vit ) {
00965           return false;
00966         }
00967         else {
00968           h2 = h2->get_prev()->get_mate() ;
00969         }
00970       }
00971       while ( h2 != h1) ;
00972     }
00973     // end of the for loop for checking vertices
00974 
00978     for( EdgeIterator eit = edges_begin(); eit != edges_end() ; ++eit ) {
00982       Halfedge* h1 = (*eit)->get_first_halfedge() ;
00983 
00987       if ( h1 == 0 ) return false ;
00988 
00992       if ( h1->get_edge() != *eit ) return false ;
00993 
00994 
00998       Halfedge* h2 = (*eit)->get_second_halfedge() ;
00999 
01003       if ( h2 == 0 ) return false ;
01004 
01008       if ( h2->get_edge() != *eit ) return false ;
01009 
01013       if ( h1 == h2 ) return false ;
01014 
01018       if ( ( h1 != h2->get_mate() ) || ( h2 != h1->get_mate() ) )
01019       {
01020         return false ;
01021       }
01022     }
01023     // end of the for loop for checking edges
01024 
01025     return true;
01026   }
01027 
01028 }
01029  //end of group class.
01031 
01032 #endif   // SURFACE_H