a48
2.0.2
|
00001 00009 #ifndef A48_MESH_HH 00010 #define A48_MESH_HH 00011 00142 //== INCLUDES ================================================================= 00143 00144 #include <map> 00145 #include <queue> 00146 #include <fstream> 00147 #include <iostream> 00148 00149 #include <adaptivemesht.hh> 00150 00151 //== NAMESPACES =============================================================== 00152 00157 namespace a48 { 00158 00159 //=== IMPLEMENTATION ========================================================== 00160 00183 template< class Mesh > 00184 bool 00185 write_off_mesh( const Mesh& _m, 00186 std::ostream& _out, 00187 const bool& _wq = false, 00188 void (*_fratt)( std::string&, const typename Mesh::vertex_type* ) = 0, 00189 void (*_frid)( unsigned&, const typename Mesh::vertex_type* ) = 0 ) { 00190 00191 typedef typename Mesh::vertex_type vertex_type; 00192 typedef typename Mesh::halfedge_type halfedge_type; 00193 typedef typename Mesh::vertex_const_iterator vertex_const_iterator; 00194 typedef typename Mesh::face_const_iterator face_const_iterator; 00195 typedef typename Mesh::face_container face_container; 00196 00197 unsigned nv = _m.size_of_vertices(); // number of vertices 00198 halfedge_type *hcurr; // current halfedge 00199 face_container mfc = _m.set_of_faces(); // copy mesh face container 00200 std::map< vertex_type*, unsigned > vmap; // auxiliary vertex map 00201 std::vector< std::string > vatt( nv ); // auxiliary vertex attributes 00202 00203 if( vatt.empty() ) { std::cerr << "[error] Not enough memory writing OFF\n"; return false; } 00204 00205 if( _wq ) { 00206 for (face_const_iterator fit = mfc.begin(); fit != mfc.end(); ++fit) { 00207 hcurr = (*fit)->halfedge(); 00208 if( !hcurr->is_boundary() and hcurr->opposite()->is_split() ) 00209 mfc.erase( hcurr->opposite()->face() ); 00210 } 00211 } 00212 00213 unsigned nf = mfc.size(); // number of faces 00214 _out << "OFF\n" << nv << " " << nf << " 0\n"; // header 00215 if( !_out.good() ) { std::cerr << "[error] Writing OFF\n"; return false; } 00216 00217 unsigned id = 0; 00218 std::string str; 00219 for (vertex_const_iterator vit = _m.vertices_begin(); vit != _m.vertices_end(); ++vit, ++id) { 00220 if( _frid ) _frid( id, *vit ); 00221 vmap[ *vit ] = id; 00222 if( _fratt ) _fratt( str, *vit ); 00223 vatt[ id ] = str; 00224 } 00225 00226 if( vmap.empty() ) { std::cerr << "[error] Not enough memory writing OFF\n"; return false; } 00227 00228 for (unsigned i = 0; i < nv; ++i) { 00229 _out << vatt[i] << "\n"; 00230 if( !_out.good() ) { std::cerr << "[error] Writing OFF\n"; return false; } 00231 } 00232 00233 unsigned nvf; 00234 for (face_const_iterator fit = mfc.begin(); fit != mfc.end(); ++fit) { 00235 00236 nvf = (*fit)->sides(); 00237 hcurr = (*fit)->halfedge(); 00238 00239 if( _wq and !hcurr->is_boundary() and hcurr->opposite()->is_split() ) { // quad 00240 00241 unsigned qid[4]; 00242 qid[0] = vmap[ hcurr->vertex() ]; 00243 hcurr = hcurr->next(); 00244 qid[1] = vmap[ hcurr->vertex() ]; 00245 hcurr = hcurr->next(); 00246 qid[2] = vmap[ hcurr->vertex() ]; 00247 hcurr = (*fit)->halfedge()->opposite()->next(); 00248 qid[3] = vmap[ hcurr->vertex() ]; 00249 00250 _out << "4 " << qid[0] << " " << qid[1] << " " << qid[2] << " " << qid[3] << "\n"; 00251 00252 } else { // tri or other 00253 00254 _out << nvf; 00255 00256 do { 00257 _out << " " << vmap[ hcurr->vertex() ]; 00258 hcurr = hcurr->next(); 00259 } while( hcurr != (*fit)->halfedge() ); 00260 00261 _out << "\n"; 00262 00263 } 00264 00265 if( !_out.good() ) { std::cerr << "[error] Writing OFF\n"; return false; } 00266 00267 } 00268 00269 return true; 00270 00271 } 00272 00285 template< class Mesh > 00286 bool 00287 write_off_mesh( const Mesh& _m, 00288 const char* _fn, 00289 const bool& _wq = false, 00290 void (*_fratt)( std::string&, const typename Mesh::vertex_type* ) = 0, 00291 void (*_frid)( unsigned&, const typename Mesh::vertex_type* ) = 0 ) { 00292 00293 std::ofstream out( _fn ); // open file 00294 if( !out.is_open() or !out.good() ) { std::cerr << "[error] Writing OFF: " << _fn << "\n"; return false; } 00295 bool rf = write_off_mesh( _m, out, _wq, _fratt, _frid ); // result flag 00296 out.close(); // close file after using it 00297 return rf; 00298 00299 } 00300 00321 template< class Mesh > 00322 bool 00323 read_off_mesh( Mesh& _m, 00324 std::istream& _in, 00325 void (*_fsatt)( typename Mesh::vertex_type*, const std::string& ) = 0, 00326 void (*_fsid)( typename Mesh::vertex_type*, const unsigned& ) = 0 ) { 00327 00328 typedef typename Mesh::vertex_type vertex_type; // define the vertex type 00329 00330 std::string str; 00331 unsigned nv, nf, ne; // number of vertices, faces and edges 00332 vertex_type **verts; // mesh vertices 00333 00334 std::getline( _in, str ); // read header line 00335 _in >> nv >> nf >> ne; // read mesh quantities 00336 std::getline( _in, str ); 00337 00338 verts = new vertex_type*[ nv ]; // mesh vertices 00339 if( !verts ) { std::cerr << "[error] Not enough memory reading OFF\n"; return false; } 00340 00341 _m.clear(); // clear the mesh 00342 00343 for (unsigned i = 0; i < nv; ++i) { 00344 00345 if( !_in.good() ) { std::cerr << "[error] Reading OFF\n"; return false; } 00346 std::getline( _in, str ); 00347 00348 verts[i] = _m.add_vertex(); 00349 00350 if( _fsatt ) _fsatt( verts[i], str ); 00351 if( _fsid ) _fsid( verts[i], i ); 00352 00353 } 00354 00355 std::vector< unsigned > conn; // mesh connectivity 00356 conn.reserve(nf*3); 00357 00358 for (unsigned i = 0; i < nf; ++i) { 00359 00360 unsigned nvf, fc[3]; // number of vertices per face and face connectivity 00361 00362 if( !_in.good() ) { std::cerr << "[error] Reading OFF\n"; return false; } 00363 _in >> nvf; 00364 00365 if( nvf != 3 and nvf != 4 ) { std::cerr << "[error] OFF is not a tri/quad mesh!\n[error] @ i = " << i << " nvf = " << nvf << " ; nv = " << nv << " ; nf = " << nf << "\n"; return false; } 00366 00367 _in >> fc[0] >> fc[1] >> fc[2]; 00368 00369 if( nvf == 4 ) { 00370 00371 conn.push_back( fc[2] ); 00372 conn.push_back( fc[0] ); 00373 conn.push_back( fc[1] ); 00374 00375 _in >> fc[1]; 00376 00377 conn.push_back( fc[0] ); 00378 conn.push_back( fc[2] ); 00379 conn.push_back( fc[1] ); 00380 00381 } else { 00382 00383 conn.push_back( fc[0] ); 00384 conn.push_back( fc[1] ); 00385 conn.push_back( fc[2] ); 00386 00387 } 00388 00389 } 00390 00391 _m.set_base( verts, &conn[0], conn.size()/3 ); 00392 00393 delete [] verts; 00394 conn.clear(); 00395 00396 return true; 00397 00398 } 00399 00411 template< class Mesh > 00412 bool 00413 read_off_mesh( Mesh& _m, 00414 const char* _fn, 00415 void (*_fsatt)( typename Mesh::vertex_type*, const std::string& ) = 0, 00416 void (*_fsid)( typename Mesh::vertex_type*, const unsigned& ) = 0 ) { 00417 00418 std::ifstream in( _fn ); // open file 00419 if( !in.is_open() or !in.good() ) { std::cerr << "[error] Reading OFF: " << _fn << "\n"; return false; } 00420 bool rf = read_off_mesh( _m, in, _fsatt, _fsid ); // result flag 00421 in.close(); // close file after using it 00422 return rf; 00423 00424 } 00425 00432 template< class halfedge_type > 00433 void 00434 flip_orientation( halfedge_type *h ) { 00435 00436 halfedge_type *fhe, *che; // first and current halfedge 00437 halfedge_type *phe, *nhe; // previous and next halfedge 00438 typename halfedge_type::vertex_type *pv, *cv; // previous and current vertex 00439 00440 che = fhe = h; 00441 phe = che->previous(); 00442 pv = phe->vertex(); 00443 00444 do { 00445 nhe = che->next(); 00446 cv = che->vertex(); 00447 che->set_next( phe ); 00448 che->set_vertex( pv ); 00449 if( pv->halfedge() == phe ) 00450 pv->set_halfedge( che ); 00451 phe = che; 00452 pv = cv; 00453 che = nhe; 00454 } while (che != fhe); 00455 00456 } 00457 00471 template< class Mesh > 00472 bool 00473 make_consistent( Mesh& _m ) { 00474 00475 typename Mesh::face_type *of; // opposed face 00476 typename Mesh::face_iterator fit; // face iterator 00477 typename Mesh::face_container fnp, fp; // set of faces (not) processed 00478 typename Mesh::halfedge_type *fhe, *che; // first and current halfedge 00479 00480 fnp.insert( *_m.faces_begin() ); 00481 00482 do { // O(n) where n is the number of faces in the mesh 00483 fit = fnp.begin(); 00484 fnp.erase( fit ); 00485 fp.insert( *fit ); 00486 00487 che = fhe = (*fit)->halfedge(); 00488 00489 do { 00490 00491 if( !che->is_boundary() ) { 00492 00493 of = che->opposite()->face(); 00494 00495 if( fp.find( of ) == fp.end() ) 00496 fnp.insert( of ); 00497 00498 if( !che->is_consistent() ) 00499 flip_orientation( che->opposite() ); 00500 00501 } 00502 00503 che = che->next(); 00504 00505 } while( che != fhe ); 00506 00507 } while( !fnp.empty() ); 00508 00509 _m.fix_vertices_stars(); 00510 00511 // In the end, if there is still one halfedge inconsistent, 00512 // the mesh is non-orientable 00513 return _m.is_consistent(); 00514 00515 } 00516 00537 template< class Mesh > 00538 bool 00539 make_triquad( Mesh& _m, 00540 float (*_fr)( typename Mesh::halfedge_type* ) = 0, 00541 unsigned int ualg = 0 ) { 00542 00543 bool rs = true; // return status 00544 00545 if( ualg == 0 ) rs = make_triquad_48clustering( _m, _fr ); 00546 else if( ualg == 1 ) rs = make_triquad_crawler( _m, _fr ); 00547 00548 return rs; 00549 00550 } 00551 00579 template< class Mesh > 00580 bool 00581 make_triquad_48clustering( Mesh& _m, 00582 float (*_fr)( typename Mesh::halfedge_type* ) = 0 ) { 00583 00584 typedef typename Mesh::halfedge_type halfedge_type; 00585 typedef typename Mesh::halfedge_iterator halfedge_iterator; 00586 00587 typedef typename Mesh::edge_type edge_type; 00588 00589 typedef typename Mesh::vertex_iterator vertex_iterator; 00590 typedef typename Mesh::face_iterator face_iterator; 00591 00592 typedef std::pair< float, halfedge_type* > ranked_halfedge; 00593 typedef std::map< edge_type, bool > marked_container; 00594 typedef typename std::priority_queue< ranked_halfedge, std::vector< ranked_halfedge > > rh_container; 00595 00596 if( !_m.is_closed() ) return false; // if mesh is not closed this algorithm does not work 00597 00598 edge_type e; // edge 00599 rh_container rhc; // container of ranked halfedge 00600 marked_container mc; // marked halfedges container 00601 float ew = 0.f; // edge weight 00602 00603 for (halfedge_iterator hit = _m.halfedges_begin(); hit != _m.halfedges_end(); ++hit) { 00604 00605 e = (*hit)->edge(); 00606 00607 if( mc.find( e ) == mc.end() ) { 00608 00609 mc[ e ] = false; 00610 00611 if( _fr ) ew = _fr( *hit ); 00612 00613 rhc.push( std::make_pair(ew, *hit) ); 00614 00615 } 00616 00617 } 00618 00619 while( !rhc.empty() ) { 00620 00621 ranked_halfedge rh = rhc.top(); rhc.pop(); 00622 00623 if( !mc[ (rh.second)->edge() ] ) { 00624 00625 mc[ rh.second->next()->edge() ] = true; 00626 mc[ rh.second->previous()->edge() ] = true; 00627 mc[ rh.second->opposite()->next()->edge() ] = true; 00628 mc[ rh.second->opposite()->previous()->edge() ] = true; 00629 00630 _m.split( rh.second ); 00631 00632 unsigned int l0 = rh.second->face()->level(), 00633 l1 = ( rh.second->is_boundary() ) ? 0 : rh.second->opposite()->face()->level(); 00634 rh.second->vertex()->set_level( std::max( l0, l1 ) + 1 ); 00635 00636 } 00637 00638 } 00639 00640 for (face_iterator fit = _m.faces_begin(); fit != _m.faces_end(); ++fit) { 00641 00642 if( (*fit)->level() == 0 ) { 00643 _m.face_split( *fit ); 00644 (*fit)->halfedge()->next()->vertex()->set_level(1); 00645 } 00646 00647 } 00648 00649 for (vertex_iterator vit = _m.vertices_begin(); vit != _m.vertices_end(); ++vit) { 00650 00651 (*vit)->set_level(0); 00652 00653 } 00654 00655 return true; 00656 00657 } 00658 00689 template< class Mesh > 00690 bool 00691 make_triquad_crawler( Mesh& _m, 00692 float (*_fr)( typename Mesh::halfedge_type* ) = 0 ) { 00693 00694 typedef typename Mesh::halfedge_type halfedge_type; 00695 typedef typename Mesh::halfedge_iterator halfedge_iterator; 00696 00697 typedef typename Mesh::edge_type edge_type; 00698 typedef std::set< edge_type > edge_container; 00699 00700 typedef typename Mesh::face_type face_type; 00701 typedef typename Mesh::face_container face_container; 00702 typedef typename Mesh::face_iterator face_iterator; 00703 00704 typedef std::pair< float, halfedge_type* > ranked_halfedge; 00705 typedef typename std::vector< ranked_halfedge > rh_container; 00706 typedef typename rh_container::iterator rh_iterator; 00707 00708 edge_container ec; // edge container 00709 edge_type e; // edge 00710 rh_container rhc; // container of ranked halfedge 00711 float ew = 0.f; // edge weight 00712 00713 for (halfedge_iterator hit = _m.halfedges_begin(); hit != _m.halfedges_end(); ++hit) { 00714 00715 if( (*hit)->is_boundary() ) continue; 00716 00717 e = (*hit)->edge(); 00718 00719 if( ec.find( e ) == ec.end() ) { 00720 00721 ec.insert( e ); 00722 00723 if( _fr ) ew = _fr( *hit ); 00724 00725 if( ew < 0 ) continue; 00726 00727 rhc.push_back( std::make_pair(ew, *hit) ); 00728 00729 } 00730 00731 } 00732 00733 if( _fr ) std::sort( rhc.begin(), rhc.end() ); 00734 00735 face_type *cf, *of; // current and opposed face 00736 face_container qfc; // quad face container 00737 00738 for (rh_iterator rhit = rhc.begin(); rhit != rhc.end(); ++rhit) { 00739 00740 cf = (*rhit).second->face(); 00741 of = (*rhit).second->opposite()->face(); 00742 00743 if( qfc.find( cf ) != qfc.end() or qfc.find( of ) != qfc.end() ) continue; 00744 00745 // A quad in a triquad mesh is simply two adjacent 00746 // triangle faces pointing to the same 'diagonal' edge 00747 cf->set_halfedge( (*rhit).second ); 00748 of->set_halfedge( (*rhit).second->opposite() ); 00749 00750 qfc.insert( cf ); 00751 qfc.insert( of ); 00752 00753 } 00754 00755 face_container mfc = _m.set_of_faces(); // mesh's face container 00756 face_container ifc; // isolated faces container 00757 00758 // Compute the set of isolated faces by computing the 00759 // difference between the total set of faces and the set of 00760 // quad faces, i.e. the faces combined in quads previously 00761 std::set_difference( mfc.begin(), mfc.end(), qfc.begin(), qfc.end(), std::inserter(ifc, ifc.begin()) ); 00762 00763 qfc.clear(); // quad face set will not be used 00764 00765 halfedge_type *fhe, *che; // first and current halfedges 00766 halfedge_type *bhe, *she; // border and shared halfedges 00767 halfedge_type *nhe; // next halfedge to become border 00768 00769 typedef std::pair< face_type*, face_type* > quad_type; 00770 typedef std::vector< quad_type > quad_container; 00771 typedef std::map< quad_type, int > quad_map; 00772 00773 face_type *qf; // quad face 00774 quad_type cq, oq, pq; // current, opposed and previous quad 00775 00776 quad_container qpath; // quad path 00777 quad_map iq; // inserted quads in path 00778 halfedge_type *qh[4]; // quad halfedges 00779 float qcw[4]; // quad configuration weights 00780 int qcv[4], qcs, qcb; // quad configuration values 00781 halfedge_type the[6]; // test halfedges 00782 face_type tf[2]; // test faces 00783 the[0].set( &the[1], &tf[0], &the[3] ); 00784 the[3].set( &the[4], &tf[1], &the[0] ); 00785 the[1].set( &the[2], &tf[0] ); 00786 the[2].set( &the[0], &tf[0] ); 00787 the[4].set( &the[5], &tf[1] ); 00788 the[5].set( &the[3], &tf[1] ); 00789 tf[0].set_halfedge( &the[0] ); 00790 tf[1].set_halfedge( &the[1] ); 00791 00792 if( (ifc.size() % 2) == 1 ) { // odd number of isolated faces means that this mesh is not closed 00793 00794 bool sf = false; // split a boundary face flags 00795 00796 for (face_iterator fit = ifc.begin(); fit != ifc.end(); ++fit) { 00797 00798 che = fhe = (*fit)->halfedge(); 00799 00800 do { 00801 if( che->is_boundary() ) { 00802 00803 ifc.erase( *fit ); 00804 _m.split( che ); 00805 00806 che->face()->set_halfedge( che->next() ); 00807 che->next()->opposite()->face()->set_halfedge( che->next()->opposite() ); 00808 00809 sf = true; 00810 break; 00811 00812 } 00813 00814 che = che->next(); 00815 00816 } while( che != fhe ); 00817 00818 if( sf ) break; 00819 00820 } 00821 00822 if( !sf ) return false; // if a boundary face was not split, the mesh can not be converted to a triquad mesh 00823 00824 } 00825 00826 // The idea in the following loop is to 'crawl' triangle faces 00827 // over the surface towards another isolated triangle face 00828 while( !ifc.empty() ) { 00829 00830 cf = ( *ifc.begin() ); // take one isolated face 00831 00832 che = fhe = cf->halfedge(); 00833 00834 do { // loop over the neighbor faces 00835 00836 if( !che->is_boundary() ) { 00837 00838 of = che->opposite()->face(); 00839 00840 if( of->halfedge()->opposite() == of->halfedge()->opposite()->face()->halfedge() ) { // if it is a quad face 00841 00842 qf = of->halfedge()->opposite()->face(); 00843 if( of < qf ) cq = std::make_pair( of, qf ); 00844 else cq = std::make_pair( qf, of ); 00845 00846 qpath.push_back( cq ); 00847 iq[ cq ] = -1; 00848 00849 } else return false; // not expected 00850 00851 } 00852 00853 che = che->next(); 00854 00855 } while( che != fhe ); 00856 00857 for (unsigned int i = 0; i < qpath.size(); ++i) { // loop over quad path 00858 00859 cq = qpath[i]; // current quad 00860 00861 qh[0] = cq.first->halfedge()->next(); 00862 qh[1] = cq.first->halfedge()->next()->next(); 00863 qh[2] = cq.second->halfedge()->next(); 00864 qh[3] = cq.second->halfedge()->next()->next(); 00865 00866 for (unsigned j = 0; j < 4; ++j) { // 4 possible neighbors of the current quad 00867 00868 if( qh[j]->is_boundary() ) continue; 00869 00870 of = qh[j]->opposite()->face(); 00871 00872 if( of == cf ) continue; // skip other face when it is the current isolated face 00873 00874 if( of->halfedge()->opposite() == of->halfedge()->opposite()->face()->halfedge() ) { // neighbor face is a quad face 00875 00876 // Make the opposed quad by looking at the other 'quad' face 00877 qf = of->halfedge()->opposite()->face(); // quad face 00878 if( of < qf ) oq = std::make_pair( of, qf ); 00879 else oq = std::make_pair( qf, of ); 00880 00881 if( iq.find( oq ) == iq.end() ) { // if opposed quad was not inserted 00882 00883 qpath.push_back( oq ); // insert opposed quad in the path 00884 iq[ oq ] = i; // opposed quad points to the current quad 00885 00886 } 00887 00888 } else { // nearest isolated face found 'of' 00889 00890 int piq = iq[ cq ]; // previous quad index 00891 00892 bhe = qh[j]; // border halfedge dividing quad and triangle 00893 she = bhe->face()->halfedge(); // shared halfedge inside quad 00894 00895 while(1) { 00896 00897 nhe = she; 00898 00899 if( piq == -1 ) { 00900 00901 che = fhe = cf->halfedge(); 00902 00903 do { 00904 00905 if( !che->is_boundary() and 00906 (che->opposite()->face() == cq.first or 00907 che->opposite()->face() == cq.second) ) { 00908 00909 nhe = che; 00910 break; 00911 00912 } 00913 00914 che = che->next(); 00915 00916 } while( che != fhe ); 00917 00918 } else { 00919 00920 pq = qpath[ piq ]; // previous quad 00921 00922 qh[0] = pq.first->halfedge()->next(); 00923 qh[1] = pq.first->halfedge()->next()->next(); 00924 qh[2] = pq.second->halfedge()->next(); 00925 qh[3] = pq.second->halfedge()->next()->next(); 00926 00927 for (unsigned int k = 0; k < 4; ++k) { 00928 00929 if( !qh[k]->is_boundary() and 00930 (qh[k]->opposite()->face() == cq.first or 00931 qh[k]->opposite()->face() == cq.second) ) { 00932 00933 nhe = qh[k]; 00934 break; 00935 00936 } 00937 00938 } 00939 00940 } 00941 00942 if( nhe == she ) return false; // not expected 00943 00944 if( bhe->from_vertex() == nhe->from_vertex() ) { // case I 00945 00946 if( bhe->next() == she ) _m.flip( she ); 00947 00948 if( _fr ) { 00949 00950 qcw[0] = _fr( bhe ); 00951 qcv[0] = (qcw[0] < 0) ? 0 : 1; 00952 00953 if( bhe->is_flip_ok() ) { 00954 00955 the[0].set_vertex( bhe->next()->vertex() ); 00956 the[1].set_vertex( she->vertex() ); 00957 the[2].set_vertex( bhe->opposite()->next()->vertex() ); 00958 the[3].set_vertex( the[2].vertex() ); 00959 the[4].set_vertex( bhe->vertex() ); 00960 the[5].set_vertex( the[0].vertex() ); 00961 00962 qcw[1] = _fr( &the[0] ); 00963 qcv[1] = (qcw[1] < 0) ? 0 : 1; 00964 00965 } else qcv[1] = 0; 00966 00967 if( qcv[0] ) { 00968 if( qcv[1] and qcw[1] < qcw[0] ) 00969 _m.flip( bhe ); 00970 } else if( qcv[1] ) 00971 _m.flip( bhe ); 00972 else return false; // no valid quad configuration interrupts the algorithm 00973 00974 } // _fr 00975 00976 } else if( bhe->vertex() == nhe->vertex() ) { // case II 00977 00978 if( bhe->next() != she ) _m.unflip( she ); 00979 00980 if( _fr ) { 00981 00982 qcw[0] = _fr( bhe ); 00983 qcv[0] = (qcw[0] < 0) ? 0 : 1; 00984 00985 if( bhe->is_flip_ok() ) { 00986 00987 the[0].set_vertex( bhe->opposite()->next()->vertex() ); 00988 the[1].set_vertex( bhe->vertex() ); 00989 the[2].set_vertex( she->vertex() ); 00990 the[3].set_vertex( the[2].vertex() ); 00991 the[4].set_vertex( bhe->from_vertex() ); 00992 the[5].set_vertex( the[0].vertex() ); 00993 00994 qcw[1] = _fr( &the[0] ); 00995 qcv[1] = (qcw[1] < 0) ? 0 : 1; 00996 00997 } else qcv[1] = 0; 00998 00999 if( qcv[0] ) { 01000 if( qcv[1] and qcw[1] < qcw[0] ) 01001 _m.flip( bhe ); 01002 } else if( qcv[1] ) 01003 _m.flip( bhe ); 01004 else return false; // no valid quad configuration interrupts the algorithm 01005 01006 } // _fr 01007 01008 } else { // case III 01009 01010 if( _fr ) { 01011 01012 if( bhe->next() != she ) _m.unflip( she ); 01013 01014 qcw[0] = _fr( bhe ); 01015 qcv[0] = (qcw[0] < 0) ? 0 : 1; 01016 01017 if( bhe->is_flip_ok() ) { 01018 01019 the[0].set_vertex( bhe->opposite()->next()->vertex() ); 01020 the[1].set_vertex( bhe->vertex() ); 01021 the[2].set_vertex( she->vertex() ); 01022 the[3].set_vertex( the[2].vertex() ); 01023 the[4].set_vertex( bhe->from_vertex() ); 01024 the[5].set_vertex( the[0].vertex() ); 01025 01026 qcw[1] = _fr( &the[0] ); 01027 qcv[1] = (qcw[1] < 0) ? 0 : 1; 01028 01029 } else qcv[1] = 0; 01030 01031 if( qcv[0] ) { 01032 if( qcv[1] ) 01033 if( qcw[0] < qcw[1] ) 01034 qcs = 0; 01035 else qcs = 1; 01036 else qcs = 0; 01037 } else if( qcv[1] ) 01038 qcs = 1; 01039 else qcs = -1; 01040 01041 _m.flip( she ); 01042 01043 qcw[2] = _fr( bhe ); 01044 qcv[2] = (qcw[2] < 0) ? 0 : 1; 01045 01046 if( bhe->is_flip_ok() ) { 01047 01048 the[0].set_vertex( bhe->next()->vertex() ); 01049 the[1].set_vertex( she->vertex() ); 01050 the[2].set_vertex( bhe->opposite()->next()->vertex() ); 01051 the[3].set_vertex( the[2].vertex() ); 01052 the[4].set_vertex( bhe->vertex() ); 01053 the[5].set_vertex( the[0].vertex() ); 01054 01055 qcw[3] = _fr( &the[0] ); 01056 qcv[3] = (qcw[3] < 0) ? 0 : 1; 01057 01058 } else qcv[3] = 0; 01059 01060 if( qcv[2] ) { 01061 if( qcv[3] ) 01062 if( qcw[2] < qcw[3] ) 01063 qcb = 2; 01064 else qcb = 3; 01065 else qcb = 2; 01066 } else if( qcv[3] ) 01067 qcb = 3; 01068 else qcb = -1; 01069 01070 if( qcs != -1 ) { 01071 if( qcb != -1 ) { 01072 if( qcw[qcs] < qcw[qcb] ) { 01073 _m.unflip( she ); 01074 if( qcs == 1 ) _m.unflip( bhe ); 01075 } else { 01076 if( qcb == 3 ) _m.flip( bhe ); 01077 } 01078 } else { 01079 _m.unflip( she ); 01080 if( qcs == 1 ) _m.unflip( bhe ); 01081 } 01082 } else if( qcb != -1 ) { 01083 if( qcb == 3 ) _m.flip( bhe ); 01084 } else return false; // no valid quad configuration interrupts the algorithm 01085 01086 01087 } // _fr 01088 01089 } // three cases 01090 01091 bhe->face()->set_halfedge( bhe ); 01092 bhe->opposite()->face()->set_halfedge( bhe->opposite() ); 01093 01094 ifc.erase( bhe->face() ); 01095 ifc.erase( bhe->opposite()->face() ); 01096 ifc.insert( nhe->opposite()->face() ); 01097 01098 if( piq == -1 ) break; 01099 01100 piq = iq[ pq ]; // next previous-quad 01101 01102 cq = pq; 01103 01104 bhe = nhe; 01105 she = nhe->face()->halfedge(); 01106 01107 // verify if next iteration is a quad 01108 if( piq != -1 and she->opposite()->face()->halfedge() != she->opposite() ) return false; 01109 if( bhe == she ) return false; 01110 01111 } // while(1) 01112 01113 cf = nhe->face(); 01114 of = nhe->opposite()->face(); 01115 01116 cf->set_halfedge( nhe ); 01117 of->set_halfedge( nhe->opposite() ); 01118 01119 ifc.erase( cf ); 01120 ifc.erase( of ); 01121 01122 qpath.clear(); 01123 iq.clear(); 01124 01125 break; 01126 01127 } // if quad or nearest isolated face 01128 01129 } // for j 01130 01131 } // for i 01132 01133 } // while ifc 01134 01135 return true; 01136 01137 } 01145 //============================================================================= 01146 } // namespace a48 01147 01148 //== SECONDARY DOCUMENTATION ================================================== 01149 01356 //============================================================================= 01357 #endif // A48_MESH_HH 01358 //=============================================================================