The Parametric Pseudo-Manifold (PPS) Library 1.0
|
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