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 edge
  std::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 overlap
    if(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 intersection
      return false;
    }
  }

  // check for shared vertex --> maybe intersection, maybe not
  int 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 triangles
    const 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 intersection
  const 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_impl

  typedef 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里面的实现

原文地址：https://blog.csdn.net/u011208918/article/details/144057566

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！