曲面简化中通过边塌缩的方式删除顶点、边和面。边塌缩有两种方式：一种是“edge-collapse”，另一种是“halfedge-collapse”。给定一个边e，其关联的顶点分别是w和v，edge-collapse用一个新顶点r取代边e和顶点w、v，而半边塌缩则是把顶点v移到w处，即w的位置是不变的。两种方式都能够删掉边e，以及e连接的两个三角形。CGAL中使用的是halfedge-collapse。

在对某个半边进行塌缩操作之前，要检查该半边是否可进行塌缩，代码如下：

// Edge_collapse_impl.h

// 有些边塌缩之后，会导致网格的拓扑一致性被破坏，因此不能对这些边进行塌缩操作。

// 该函数用于检查边p->q的可塌缩性，若p->q可塌缩，该函数返回true

// 判断p->q是否具有可塌缩性的依据是1993年Hoppe等人的论文“Mesh Optimization”中的“link condition”，

// link condition： 对于网格中每个既是p又是q的邻居的顶点k，p-k-q是网格的一个面。

//

template
      

bool EdgeCollapse
      
       ::Is_collapse_topologically_valid( Profile const& aProfile )
      

{

bool rR = true ;

CGAL_ECMS_TRACE(3,"Testing topological collapsabilty of p_q=V" << aProfile.v0()->id() << "(%" << aProfile.v0()->vertex_degree() << ")"

<< "->V" << aProfile.v1()->id() << "(%" << aProfile.v1()->vertex_degree() << ")"

);

CGAL_ECMS_TRACE(4, "is p_q border:" << aProfile.is_v0_v1_a_border() );

CGAL_ECMS_TRACE(4, "is q_q border:" << aProfile.is_v1_v0_a_border() );

out_edge_iterator eb1, ee1 ;

out_edge_iterator eb2, ee2 ;

CGAL_ECMS_TRACE(4,"  t=V"

<< ( aProfile.left_face_exists() ? aProfile.vL()->id() : -1 )

<< "(%"

<< ( aProfile.left_face_exists() ? aProfile.vL()->vertex_degree() : 0 )

<< ")"

);

CGAL_ECMS_TRACE(4,"  b=V"

<< ( aProfile.right_face_exists() ? aProfile.vR()->id() : -1 )

<< "(%"

<< ( aProfile.right_face_exists() ? aProfile.vR()->vertex_degree() :0 )

<< ")"

);

// The following loop checks the link condition for v0_v1.

// Specifically, that for every vertex 'k' adjacent to both 'p and 'q', 'pkq' is a face of the mesh.

//

for ( boost::tie(eb1,ee1) = out_edges(aProfile.v0(),mSurface) ; rR && eb1 != ee1 ; ++ eb1 )

{

edge_descriptor v0_k = *eb1 ;

if ( v0_k != aProfile.v0_v1() )//边v0_k不是边v0_v1

{

vertex_descriptor k = target(v0_k,mSurface);

for ( boost::tie(eb2,ee2) = out_edges(k,mSurface) ; rR && eb2 != ee2 ; ++ eb2 )//遍历环绕k的半边，找出连接k与v1的那条

{

edge_descriptor k_v1 = *eb2 ;

if ( target(k_v1,mSurface) == aProfile.v1() )//找到了连接k和v1的半边

{

// 现在已知p-q-k是连通的，接下来要判断这个三角形是否是网格的一个面

//

// 由于必须是三角网格，所以至多有两个面共享边p-q

//

// 若p->q不是border edge, 设t = target(next(p->q))，则p->q上方的面为p-q-t

// 若q->p不是border edge, 设b = target(next(q->p))，则q->p下方的面为q-p-b

//

// 若k是t或者b，则p-q-k ★可能★是网格的一个面。 It won't be if k==t but p->q is border

// 若p-q-k是一个面的话，则不会出现k==t，而k->q是border或k==b而q->b是border的情况

bool lIsFace =   ( aProfile.vL() == k && aProfile.left_face_exists () )

|| ( aProfile.vR() == k && aProfile.right_face_exists() ) ;

CGAL_SURF_SIMPL_TEST_assertion_code

(

if ( lIsFace )

{

// Is k_v1 the halfedge bounding the face 'k-v1-v0'?

if ( !k_v1->is_border() && k_v1->next()->vertex() == aProfile.v0() )

{

CGAL_SURF_SIMPL_TEST_assertion( !k_v1->is_border() ) ;

CGAL_SURF_SIMPL_TEST_assertion(  k_v1                ->vertex() == aProfile.v1() ) ;

CGAL_SURF_SIMPL_TEST_assertion(  k_v1->next()        ->vertex() == aProfile.v0() ) ;

CGAL_SURF_SIMPL_TEST_assertion(  k_v1->next()->next()->vertex() == k ) ;

}

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 )//rR为真，说明p-q-k是个面，但是有可能pq边关联的另一个三角形是个洞，或者顶点p、q周围存在border

{

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 ;

}