edge_collapse_impl.h

很多二维 三维几何计算算法 C++ 类库

              }
              else // or is it the opposite?
              {
                edge_descriptor v1_k = k_v1->opposite();
                CGAL_SURF_SIMPL_TEST_assertion( !v1_k->is_border() ) ;
                CGAL_SURF_SIMPL_TEST_assertion(  v1_k                ->vertex() == k ) ;
                CGAL_SURF_SIMPL_TEST_assertion(  v1_k->next()        ->vertex() == aProfile.v0() ) ;
                CGAL_SURF_SIMPL_TEST_assertion(  v1_k->next()->next()->vertex() == aProfile.v1() ) ;
              }
            }
          );

          if ( !lIsFace )
          {
            CGAL_ECMS_TRACE(3,"  k=V" << k->id() << " IS NOT in a face with p-q. NON-COLLAPSABLE edge." ) ;
            rR = false ;
            break ;
          }  
          else 
          {
            CGAL_ECMS_TRACE(4,"  k=V" << k->id() << " is in a face with p-q") ;
          }
        }
      }  
    }
  }   
     
  if ( rR )
  {
    if ( aProfile.is_v0_v1_a_border() )
    {
      if ( Is_open_triangle(aProfile.v0_v1()) )
      {
        rR = false ;
        CGAL_ECMS_TRACE(3,"  p-q belongs to an open triangle. NON-COLLAPSABLE edge." ) ;
      }
    }
    else if ( aProfile.is_v1_v0_a_border() )
    {
      if ( Is_open_triangle(aProfile.v1_v0()) )
      {
        rR = false ;
        CGAL_ECMS_TRACE(3,"  p-q belongs to an open triangle. NON-COLLAPSABLE edge." ) ;
      }
    }
    else
    {
      if ( is_border(aProfile.v0()) && is_border(aProfile.v1()) )
      {
        rR = false ;
        CGAL_ECMS_TRACE(3,"  both p and q are boundary vertices but p-q is not. NON-COLLAPSABLE edge." ) ;
      }  
      else
      {
        bool lTetra = Is_tetrahedron(aProfile.v0_v1());

        CGAL_SURF_SIMPL_TEST_assertion( lTetra == mSurface.is_tetrahedron(aProfile.v0_v1()) ) ;

        if ( lTetra )
        {
          rR = false ;
          CGAL_ECMS_TRACE(3,"  p-q belongs to a tetrahedron. NON-COLLAPSABLE edge." ) ;
        }
      }
    }
  }
  
  return rR ;
}

template<class M,class SP, class VIM,class EIM,class EBM, class CF,class PF,class V>
bool EdgeCollapse<M,SP,VIM,EIM,EBM,CF,PF,V>::Is_tetrahedron( edge_descriptor const& h1 )
{
  //
  // Code copied from Polyhedron_3::is_tetrahedron()
  //
  edge_descriptor h2 = next_edge(h1,mSurface);
  edge_descriptor h3 = next_edge(h2,mSurface);
  
  edge_descriptor h1o = opposite_edge(h1,mSurface) ;
  edge_descriptor h2o = opposite_edge(h2,mSurface) ;
  edge_descriptor h3o = opposite_edge(h3,mSurface) ;
  
  edge_descriptor h4 = next_edge(h1o,mSurface);
  edge_descriptor h5 = next_edge(h2o,mSurface);
  edge_descriptor h6 = next_edge(h3o,mSurface);
  
  edge_descriptor h4o = opposite_edge(h4,mSurface) ;
  edge_descriptor h5o = opposite_edge(h5,mSurface) ;
  edge_descriptor h6o = opposite_edge(h6,mSurface) ;
  
  // check halfedge combinatorics.
  // at least three edges at vertices 1, 2, 3.
  if ( h4 == h3o ) return false;
  if ( h5 == h1o ) return false;
  if ( h6 == h2o ) return false;
  
  // exact three edges at vertices 1, 2, 3.
  if ( next_edge(h4o,mSurface) != h3o ) return false;
  if ( next_edge(h5o,mSurface) != h1o ) return false;
  if ( next_edge(h6o,mSurface) != h2o ) return false;
  
  // three edges at v4.
  if ( opposite_edge(next_edge(h4,mSurface),mSurface) != h5) return false;
  if ( opposite_edge(next_edge(h5,mSurface),mSurface) != h6) return false;
  if ( opposite_edge(next_edge(h6,mSurface),mSurface) != h4) return false;
  
  // All facets are triangles.
  if ( next_edge(next_edge(next_edge(h1,mSurface),mSurface),mSurface) != h1) return false;
  if ( next_edge(next_edge(next_edge(h4,mSurface),mSurface),mSurface) != h4) return false;
  if ( next_edge(next_edge(next_edge(h5,mSurface),mSurface),mSurface) != h5) return false;
  if ( next_edge(next_edge(next_edge(h6,mSurface),mSurface),mSurface) != h6) return false;
  
  // all edges are non-border edges.
  if ( is_border(h1)) return false;  // implies h2 and h3
  if ( is_border(h4)) return false;
  if ( is_border(h5)) return false;
  if ( is_border(h6)) return false;

  return true;
}

template<class M,class SP, class VIM,class EIM,class EBM, class CF,class PF,class V>
bool EdgeCollapse<M,SP,VIM,EIM,EBM,CF,PF,V>::Is_open_triangle( edge_descriptor const& h1 )
{
  edge_descriptor h2 = next_edge(h1,mSurface);
  edge_descriptor h3 = next_edge(h2,mSurface);
  
  bool rR = is_border(h2) && is_border(h3);  

  CGAL_SURF_SIMPL_TEST_assertion( rR == (  h1->is_border()
                                        && h1->next()->is_border()
                                        && h1->next()->next()->is_border()
                                        ) 
                                ) ;
  return rR ;
}


template<class M,class SP, class VIM,class EIM,class EBM, class CF,class PF,class V>
void EdgeCollapse<M,SP,VIM,EIM,EBM,CF,PF,V>::Collapse( Profile const& aProfile )
{
  CGAL_ECMS_TRACE(1,"S" << mStep << ". Collapsig " << edge_to_string(aProfile.v0v1()) ) ;
  
  vertex_descriptor rResult ;
    
  // The external function Get_new_vertex_point() is allowed to return an absent point if there is no way to place the vertex
  // satisfying its constrians. In that case the vertex-pair is simply not removed.
  Placement_type lPlacement = get_placement(aProfile);
  
  if ( Visitor )
    Visitor->OnCollapsing(aProfile,lPlacement);

  -- mCurrentEdgeCount ;
      
  CGAL_SURF_SIMPL_TEST_assertion_code( size_type lResultingVertexCount = mSurface.size_of_vertices() ;
                                       size_type lResultingEdgeCount   = mSurface.size_of_halfedges() / 2 ;
                                     ) ; 

  // If the top/bottom facets exists, they are removed and the edges v0vt and Q-B along with them.
  // In that case their corresponding pairs must be pop off the queue
  
  if ( aProfile.left_face_exists() )
  {
    edge_descriptor lV0VL = primary_edge(aProfile.vL_v0());
    
    CGAL_ECMS_TRACE(3,"V0VL E" << lV0VL->id()
                   << "(V" <<  lV0VL->vertex()->id() << "->V" << lV0VL->opposite()->vertex()->id() << ")"
                   ) ;
                   
    Edge_data& lData = get_data(lV0VL) ;
    if ( lData.is_in_PQ() )
    {
      CGAL_ECMS_TRACE(2,"Removing E" << lV0VL->id() << " from PQ" ) ;
      remove_from_PQ(lV0VL,lData) ;
    }

    -- mCurrentEdgeCount ;
    CGAL_SURF_SIMPL_TEST_assertion_code( -- lResultingEdgeCount ) ; 
  }
  
  if ( aProfile.right_face_exists() )
  {
    edge_descriptor lVRV1 = primary_edge(aProfile.vR_v1());
    
    CGAL_ECMS_TRACE(3,"V1VRE" << lVRV1->id()
                   << "(V" <<  lVRV1->vertex()->id() << "->V" << lVRV1->opposite()->vertex()->id() << ")"
                   ) ;
                   
    Edge_data& lData = get_data(lVRV1) ;
    if ( lData.is_in_PQ() )
    {
      CGAL_ECMS_TRACE(2,"Removing E" << lVRV1->ID << " from PQ") ;
      remove_from_PQ(lVRV1,lData) ;
    }
    -- mCurrentEdgeCount ;
    CGAL_SURF_SIMPL_TEST_assertion_code( -- lResultingEdgeCount ) ; 
  }

  CGAL_ECMS_TRACE(1,"Removing:\n  v0v1: E" << aProfile.v0v1()->ID << "(V" << lP->ID << "->V" << lQ->ID << ")" );
  
    
  // Perform the actuall collapse.
  // This is an external function.
  // It's REQUIRED to remove ONLY 1 vertex (P or Q) and edges PQ,PT and QB
  // (PT and QB are removed if they are not null).
  // All other edges must be kept.
  // All directed edges incident to vertex removed are relink to the vertex kept.
  rResult = halfedge_collapse(aProfile.v0_v1(),mSurface);

  CGAL_SURF_SIMPL_TEST_assertion_code( -- lResultingEdgeCount ) ; 

  CGAL_SURF_SIMPL_TEST_assertion_code( -- lResultingVertexCount ) ; 

  CGAL_SURF_SIMPL_TEST_assertion( lResultingEdgeCount * 2 == mSurface.size_of_halfedges() ) ;

  CGAL_SURF_SIMPL_TEST_assertion( lResultingVertexCount == mSurface.size_of_vertices() ) ;

  CGAL_SURF_SIMPL_TEST_assertion( mSurface.is_valid() && mSurface.is_pure_triangle() ) ;
  
  CGAL_ECMS_TRACE(1,"V" << rResult->ID << " kept." ) ;
                 
#ifdef CGAL_SURFACE_SIMPLIFICATION_ENABLE_TRACE
  out_edge_iterator eb1, ee1 ;     
  for ( tie(eb1,ee1) = out_edges(rResult,mSurface) ; eb1 != ee1 ; ++ eb1 )  
    CGAL_ECMS_TRACE(2, edge_to_string(*eb1) ) ;
#endif

  if ( lPlacement )  
  {
    CGAL_ECMS_TRACE(2,"New vertex point: " << xyz_to_string(*lPlacement) ) ;
    put(vertex_point,mSurface,rResult,*lPlacement) ;
  }  

  Update_neighbors(rResult) ;
  
  CGAL_ECMS_DEBUG_CODE ( ++mStep ; )
}

template<class M,class SP, class VIM,class EIM,class EBM, class CF,class PF,class V>
void EdgeCollapse<M,SP,VIM,EIM,EBM,CF,PF,V>::Update_neighbors( vertex_descriptor const& aKeptV )
{
  CGAL_ECMS_TRACE(3,"Updating cost of neighboring edges..." ) ;

  //
  // (A) Collect all edges to update its cost: all those around each vertex adjacent to the vertex kept
  //  
  
  typedef std::set<edge_descriptor,Compare_id> edges ;
  
  edges lToUpdate(Compare_id(this)) ;
  
  // (A.1) Loop around all vertices adjacent to the vertex kept
  in_edge_iterator eb1, ee1 ; 
  for ( tie(eb1,ee1) = in_edges(aKeptV,mSurface) ; eb1 != ee1 ; ++ eb1 )
  {
    edge_descriptor lEdge1 = *eb1 ;
    
    vertex_descriptor lAdj_k = source(lEdge1,mSurface);
    
    // (A.2) Loop around all edges incident on each adjacent vertex
    in_edge_iterator eb2, ee2 ; 
    for ( tie(eb2,ee2) = in_edges(lAdj_k,mSurface) ; eb2 != ee2 ; ++ eb2 )
    {
      edge_descriptor lEdge2 = primary_edge(*eb2) ;
      
      Edge_data& lData2 = get_data(lEdge2);
      CGAL_ECMS_TRACE(4,"Inedge around V" << lAdj_k->ID << edge_to_string(lEdge2) ) ;
    
      // Only those edges still in the PQ _and_ not already collected are updated.
      if ( lData2.is_in_PQ() && lToUpdate.find(lEdge2) == lToUpdate.end() )
        lToUpdate.insert(lEdge2) ;
    } 
  }  
  
  //
  // (B) Proceed to update the costs.
  //
  
  for ( typename edges::iterator it = lToUpdate.begin(), eit = lToUpdate.end() ; it != eit ; ++ it )
  {
    edge_descriptor lEdge = *it;
    
    Edge_data& lData = get_data(lEdge);
    
    Profile const& lProfile = create_profile(lEdge);
    
    lData.cost() = get_cost(lProfile) ;
    
    CGAL_ECMS_TRACE(3, edge_to_string(lEdge) << " updated in the PQ") ;
    
    update_in_PQ(lEdge,lData);
  }
    
}


} // namespace Surface_mesh_simplification

CGAL_END_NAMESPACE

#endif // CGAL_SURFACE_MESH_SIMPLIFICATION_DETAIL_EDGE_COLLAPSE_IMPL_H //
// EOF //