微网站的案例,莱芜东风街吧,网站footer设计,网站被301跳转CGAL::Polygon_mesh_processing::self_intersections 是用于检测多边形网格#xff08;Polygon Mesh#xff09;中的自相交的函数。自相交是指网格中的某些面#xff08;例如三角形#xff09;与同一网格中的其他面交叉的情况。这种情况通常是不期望的#xff0c;因为它会…CGAL::Polygon_mesh_processing::self_intersections 是用于检测多边形网格Polygon Mesh中的自相交的函数。自相交是指网格中的某些面例如三角形与同一网格中的其他面交叉的情况。这种情况通常是不期望的因为它会导致网格的不一致性和潜在的几何错误。 std::vectorstd::pairMesh::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_wrapperTM::face_descriptor fh,typename Triangle_mesh_and_triangle_soup_wrapperTM::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_wrapperTM Wrapper;typedef typename Wrapper::vertex_descriptor vertex_descriptor;typedef typename GT::Segment_3 Segment;typedef typename GT::Triangle_3 Triangle;std::arrayvertex_descriptor, 3 hv, gv;Wrapper::get_face_vertices(fh, hv, tmesh);Wrapper::get_face_vertices(fg, gv, tmesh);// check for shared edgestd::arrayvertex_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(; i3 (! shared); i){for(j0; j3 (! 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[(i1)%3]), get(vpmap, hv[(i2)%3]));const Segment s2 construct_segment(get(vpmap, gv[(j1)%3]), get(vpmap, gv[(j2)%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_facesBox, TM, VPM, GT, FacePairOutputIterator Intersecting_faces_filter;Intersecting_faces_filter intersect_faces(tmesh, vpmap, gt, out);//省略......CGAL::box_self_intersection_dCGAL::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_intersectGT(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里面的实现
