CGAL CGAL::Polygon_mesh_processing::self_intersections解析

CGAL::Polygon_mesh_processing::self_intersections 是用于检测多边形网格（Polygon Mesh）中的自相交的函数。自相交是指网格中的某些面（例如三角形）与同一网格中的其他面交叉的情况。这种情况通常是不期望的，因为它会导致网格的不一致性和潜在的几何错误。

    std::vector<std::pair<Mesh::face_index, Mesh::face_index>> self_intersections;CGAL::Polygon_mesh_processing::self_intersections(mesh,std::back_inserter(self_intersections));

关键代码：

// Checks for 'real' intersections, i.e. not simply a shared vertex or edge
template <class GT, class TM, class VPM>
bool do_faces_intersect(typename Triangle_mesh_and_triangle_soup_wrapper<TM>::face_descriptor fh,typename Triangle_mesh_and_triangle_soup_wrapper<TM>::face_descriptor fg,const TM& tmesh,const VPM vpmap,const typename GT::Construct_segment_3& construct_segment,const typename GT::Construct_triangle_3& construct_triangle,const typename GT::Do_intersect_3& do_intersect)
{typedef Triangle_mesh_and_triangle_soup_wrapper<TM>       Wrapper;typedef typename Wrapper::vertex_descriptor     vertex_descriptor;typedef typename GT::Segment_3                            Segment;typedef typename GT::Triangle_3                          Triangle;std::array<vertex_descriptor, 3> hv, gv;Wrapper::get_face_vertices(fh, hv, tmesh);Wrapper::get_face_vertices(fg, gv, tmesh);// check for shared edgestd::array<vertex_descriptor, 4> verts;if (Wrapper::faces_have_a_shared_edge(fh, fg, verts, tmesh)){if (verts[2]==verts[3]) return false; // only for a soup of triangles// there is an intersection if the four points are coplanar and the triangles overlapif(CGAL::coplanar(get(vpmap, verts[0]),get(vpmap, verts[1]),get(vpmap, verts[2]),get(vpmap, verts[3])) &&CGAL::coplanar_orientation(get(vpmap, verts[0]),get(vpmap, verts[1]),get(vpmap, verts[2]),get(vpmap, verts[3]))== CGAL::POSITIVE){return true;}else{// there is a shared edge but no intersectionreturn false;}}// check for shared vertex --> maybe intersection, maybe notint i(0), j(0);bool shared = false;for(; i<3 && (! shared); ++i){for(j=0; j<3 && (! shared); ++j){if(hv[i] == gv[j]){shared = true;break;}}if(shared)break;}if(shared){// found shared vertex:CGAL_assertion(hv[i] == gv[j]);// geometric check if the opposite segments intersect the trianglesconst Triangle t1 = construct_triangle(get(vpmap, hv[0]), get(vpmap, hv[1]), get(vpmap, hv[2]));const Triangle t2 = construct_triangle(get(vpmap, gv[0]), get(vpmap, gv[1]), get(vpmap, gv[2]));const Segment s1 = construct_segment(get(vpmap, hv[(i+1)%3]), get(vpmap, hv[(i+2)%3]));const Segment s2 = construct_segment(get(vpmap, gv[(j+1)%3]), get(vpmap, gv[(j+2)%3]));if(do_intersect(t1, s2))return true;else if(do_intersect(t2, s1))return true;return false;}// check for geometric intersectionconst Triangle th = construct_triangle(get(vpmap, hv[0]), get(vpmap, hv[1]), get(vpmap, hv[2]));const Triangle tg = construct_triangle(get(vpmap, gv[0]), get(vpmap, gv[1]), get(vpmap, gv[2]));if(do_intersect(th, tg))return true;return false;
}

解析：

1.初步筛选

将每个三角形的Bbox计算出来，再调用CGAL::box_self_intersection_d，使用分段树算法，快速筛选两两相交的Bbox对，此时得到的三角形对有可能相交，有可能只是相邻但不相交

//self_intersections_impltypedef internal::Strict_intersect_faces<Box, TM, VPM, GT, FacePairOutputIterator> Intersecting_faces_filter;Intersecting_faces_filter intersect_faces(tmesh, vpmap, gt, out);//省略......CGAL::box_self_intersection_d<CGAL::Sequential_tag>(box_ptr.begin(), box_ptr.end(), intersect_faces, cutoff);

2.精确判断

当检测到两个Bbox相交，box_self_intersection_d函数会调用函数对象（第三个参数Intersecting_faces_filter）的成员 void operator()(const Box* b, const Box* c)进一步判断

template <class Box, class TM, class VPM, class GT,class OutputIterator>
struct Strict_intersect_faces // "strict" as in "not sharing a subface"
{//省略.......void operator()(const Box* b, const Box* c) const{if(do_faces_intersect<GT>(b->info(), c->info(), m_tmesh, m_vpmap, m_construct_segment,         m_construct_triangle, m_do_intersect))*m_iterator++ = std::make_pair(b->info(), c->info());}
};

do_faces_intersect的流程分三种情况，即有公共边，公共点的，没有公共边和公共顶点。

• ① t1和t2有公共边

1.若t1和t2不共面则不相交

2.若t1和t2共面，则判断v2是否在v0v1左边，若在左边则t1和 t2相交，否则不相交

• ② t1和t2有公共的顶点

1.判断边s1和三角形t2是否相交

2.判断边s2和三角形t1是否相交

• ③ t1和t2没有公共边和公共顶点

调用do_intersect碰撞检测，判断是否相交

步骤②步骤③中，判断边与三角形相交、三角形与三角形相交具体看CGAL\Intersections_3里面的实现