igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM > Class Template Reference

#include <src/libigl/igl/copyleft/cgal/SelfIntersectMesh.h>

Collaboration diagram for igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >:

Public Types
typedef CGAL::Point_3< Kernel >	Point_3
typedef CGAL::Segment_3< Kernel >	Segment_3
typedef CGAL::Triangle_3< Kernel >	Triangle_3
typedef CGAL::Plane_3< Kernel >	Plane_3
typedef CGAL::Tetrahedron_3< Kernel >	Tetrahedron_3
typedef CGAL::Point_2< Kernel >	Point_2
typedef CGAL::Segment_2< Kernel >	Segment_2
typedef CGAL::Triangle_2< Kernel >	Triangle_2
typedef CGAL::Exact_intersections_tag	Itag
typedef std::vector< Triangle_3 >	Triangles
typedef Triangles::iterator	TrianglesIterator
typedef Triangles::const_iterator	TrianglesConstIterator
typedef CGAL::Box_intersection_d::Box_with_handle_d< double, 3, TrianglesIterator >	Box
typedef DerivedF::Index	Index
typedef std::vector< std::pair< Index, CGAL::Object > >	ObjectList
typedef std::vector< Index >	IndexList
typedef std::pair< Index, Index >	EMK
typedef std::vector< Index >	EMV
typedef std::map< EMK, EMV >	EdgeMap

Public Member Functions
	SelfIntersectMesh (const Eigen::MatrixBase< DerivedV > &V, const Eigen::MatrixBase< DerivedF > &F, const RemeshSelfIntersectionsParam &params, Eigen::PlainObjectBase< DerivedVV > &VV, Eigen::PlainObjectBase< DerivedFF > &FF, Eigen::PlainObjectBase< DerivedIF > &IF, Eigen::PlainObjectBase< DerivedJ > &J, Eigen::PlainObjectBase< DerivedIM > &IM)
void	box_intersect (const Box &a, const Box &b)
void	process_intersecting_boxes ()

Static Public Member Functions
static void	box_intersect_static (SelfIntersectMesh *SIM, const Box &a, const Box &b)

Public Attributes
const Eigen::MatrixBase< DerivedV > &	V
const Eigen::MatrixBase< DerivedF > &	F
Index	count
Triangles	T
IndexList	lIF
std::map< Index, ObjectList >	offending
std::vector< std::pair< TrianglesIterator, TrianglesIterator > >	candidate_triangle_pairs
RemeshSelfIntersectionsParam	params

Private Types
typedef SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >	Self

Private Member Functions
void	mark_offensive (const Index f)
void	count_intersection (const Index fa, const Index fb)
bool	intersect (const Triangle_3 &A, const Triangle_3 &B, const Index fa, const Index fb)
bool	single_shared_vertex (const Triangle_3 &A, const Triangle_3 &B, const Index fa, const Index fb, const Index va, const Index vb)
bool	single_shared_vertex (const Triangle_3 &A, const Triangle_3 &B, const Index fa, const Index fb, const Index va)
bool	double_shared_vertex (const Triangle_3 &A, const Triangle_3 &B, const Index fa, const Index fb, const std::vector< std::pair< Index, Index > > shared)

Private Attributes
std::mutex	m_offending_lock

Detailed Description

template<typename Kernel, typename DerivedV, typename DerivedF, typename DerivedVV, typename DerivedFF, typename DerivedIF, typename DerivedJ, typename DerivedIM>
class igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >

Member Typedef Documentation

Box

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef CGAL::Box_intersection_d::Box_with_handle_d<double,3,TrianglesIterator> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Box

EdgeMap

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef std::map<EMK,EMV> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::EdgeMap

EMK

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef std::pair<Index,Index> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::EMK

EMV

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef std::vector<Index> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::EMV

Index

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef DerivedF::Index igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Index

IndexList

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef std::vector<Index> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::IndexList

Itag

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef CGAL::Exact_intersections_tag igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Itag

ObjectList

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef std::vector<std::pair<Index, CGAL::Object> > igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::ObjectList

Plane_3

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef CGAL::Plane_3<Kernel> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Plane_3

Point_2

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef CGAL::Point_2<Kernel> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Point_2

Point_3

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef CGAL::Point_3<Kernel> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Point_3

Segment_2

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef CGAL::Segment_2<Kernel> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Segment_2

Segment_3

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef CGAL::Segment_3<Kernel> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Segment_3

Self

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Self

private

Tetrahedron_3

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef CGAL::Tetrahedron_3<Kernel> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Tetrahedron_3

Triangle_2

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef CGAL::Triangle_2<Kernel> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Triangle_2

Triangle_3

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef CGAL::Triangle_3<Kernel> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Triangle_3

Triangles

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef std::vector<Triangle_3> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::Triangles

TrianglesConstIterator

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef Triangles::const_iterator igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::TrianglesConstIterator

TrianglesIterator

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

typedef Triangles::iterator igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::TrianglesIterator

Constructor & Destructor Documentation

SelfIntersectMesh()

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::SelfIntersectMesh ( const Eigen::MatrixBase< DerivedV > &  V, const Eigen::MatrixBase< DerivedF > &  F, const RemeshSelfIntersectionsParam &  params, Eigen::PlainObjectBase< DerivedVV > &  VV, Eigen::PlainObjectBase< DerivedFF > &  FF, Eigen::PlainObjectBase< DerivedIF > &  IF, Eigen::PlainObjectBase< DerivedJ > &  J, Eigen::PlainObjectBase< DerivedIM > &  IM  )

inline

                                       :
  V(V),
  F(F),
  count(0),
  T(),
  lIF(),
  offending(),
  params(params)
{
  using namespace std;
  using namespace Eigen;
 
#ifdef IGL_SELFINTERSECTMESH_DEBUG
  const auto & tictoc = []() -> double
  {
    static double t_start = igl::get_seconds();
    double diff = igl::get_seconds()-t_start;
    t_start += diff;
    return diff;
  };
  const auto log_time = [&](const std::string& label) -> void{
    std::cout << "SelfIntersectMesh." << label << ": "
      << tictoc() << std::endl;
  };
  tictoc();
#endif
 
  // Compute and process self intersections
  mesh_to_cgal_triangle_list(V,F,T);
#ifdef IGL_SELFINTERSECTMESH_DEBUG
  log_time("convert_to_triangle_list");
#endif
  // http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Box_intersection_d/Chapter_main.html#Section_63.5 
  // Create the corresponding vector of bounding boxes
  std::vector<Box> boxes;
  boxes.reserve(T.size());
  for ( 
    TrianglesIterator tit = T.begin(); 
    tit != T.end(); 
    ++tit)
  {
    if (!tit->is_degenerate())
    {
      boxes.push_back(Box(tit->bbox(), tit));
    }
  }
  // Leapfrog callback
  std::function<void(const Box &a,const Box &b)> cb = 
    std::bind(&box_intersect_static, this, 
      // Explicitly use std namespace to avoid confusion with boost (who puts
      // _1 etc. in global namespace)
      std::placeholders::_1,
      std::placeholders::_2);
#ifdef IGL_SELFINTERSECTMESH_DEBUG
  log_time("box_and_bind");
#endif
  // Run the self intersection algorithm with all defaults
  CGAL::box_self_intersection_d(boxes.begin(), boxes.end(),cb);
#ifdef IGL_SELFINTERSECTMESH_DEBUG
  log_time("box_intersection_d");
#endif
  try{
    process_intersecting_boxes();
  }catch(int e)
  {
    // Rethrow if not IGL_FIRST_HIT_EXCEPTION
    if(e != IGL_FIRST_HIT_EXCEPTION)
    {
      throw e;
    }
    // Otherwise just fall through
  }
#ifdef IGL_SELFINTERSECTMESH_DEBUG
  log_time("resolve_intersection");
#endif
 
  // Convert lIF to Eigen matrix
  assert(lIF.size()%2 == 0);
  IF.resize(lIF.size()/2,2);
  {
    Index i=0;
    for(
      typename IndexList::const_iterator ifit = lIF.begin();
      ifit!=lIF.end();
      )
    {
      IF(i,0) = (*ifit);
      ifit++; 
      IF(i,1) = (*ifit);
      ifit++;
      i++;
    }
  }
#ifdef IGL_SELFINTERSECTMESH_DEBUG
  log_time("store_intersecting_face_pairs");
#endif
 
  if(params.detect_only)
  {
    return;
  }
 
  remesh_intersections(
    V,F,T,offending,params.stitch_all,VV,FF,J,IM);
 
#ifdef IGL_SELFINTERSECTMESH_DEBUG
  log_time("remesh_intersection");
#endif
}

References igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::box_intersect_static(), igl::count(), igl::copyleft::cgal::RemeshSelfIntersectionsParam::detect_only, igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::F, igl::get_seconds(), IGL_FIRST_HIT_EXCEPTION, igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::lIF, igl::copyleft::cgal::mesh_to_cgal_triangle_list(), igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::offending, igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::params, igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::process_intersecting_boxes(), igl::copyleft::cgal::remesh_intersections(), Eigen::PlainObjectBase< Derived >::resize(), igl::copyleft::cgal::RemeshSelfIntersectionsParam::stitch_all, igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::T, igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::V, and void().

Here is the call graph for this function:

Member Function Documentation

box_intersect()

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

void igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::box_intersect ( const Box &  a, const Box &  b  )

inline

{
  candidate_triangle_pairs.push_back({a.handle(), b.handle()});
}

Referenced by igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::box_intersect_static().

Here is the caller graph for this function:

box_intersect_static()

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

void igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::box_intersect_static ( SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM > *  SIM, const Box &  a, const Box &  b  )

inlinestatic

{
  SIM->box_intersect(a,b);
}

References igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::box_intersect().

Referenced by igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::SelfIntersectMesh().

Here is the call graph for this function:

Here is the caller graph for this function:

count_intersection()

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

void igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::count_intersection ( const Index  fa, const Index  fb  )

inlineprivate

{
  std::lock_guard<std::mutex> guard(m_offending_lock);
  mark_offensive(fa);
  mark_offensive(fb);
  this->count++;
  // We found the first intersection
  if(params.first_only && this->count >= 1)
  {
    throw IGL_FIRST_HIT_EXCEPTION;
  }
 
}

References igl::count(), and IGL_FIRST_HIT_EXCEPTION.

Here is the call graph for this function:

double_shared_vertex()

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

bool igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::double_shared_vertex ( const Triangle_3 &  A, const Triangle_3 &  B, const Index  fa, const Index  fb, const std::vector< std::pair< Index, Index > >  shared  )

inlineprivate

{
  using namespace std;
 
  auto opposite_vertex = [](const Index a0, const Index a1) {
    // get opposite index of A
    int a2=-1;
  for(int c=0;c<3;++c)
      if(c!=a0 && c!=a1) {
        a2 = c;
        break;
      }
      assert(a2 != -1);
      return a2;
  };
 
  // must be co-planar
  Index a2 = opposite_vertex(shared[0].first, shared[1].first);
  if (! B.supporting_plane().has_on(A.vertex(a2)))
    return false;
  
  Index b2 = opposite_vertex(shared[0].second, shared[1].second);
 
  if (int(CGAL::coplanar_orientation(A.vertex(shared[0].first), A.vertex(shared[1].first), A.vertex(a2))) * 
    int(CGAL::coplanar_orientation(B.vertex(shared[0].second), B.vertex(shared[1].second), B.vertex(b2))) < 0)
    // There is certainly no self intersection as the non-shared triangle vertices lie on opposite sides of the shared edge.
    return false;
 
  // Since A and B are non-degenerate the intersection must be a polygon
  // (triangle). Either
  //   - the vertex of A (B) opposite the shared edge of lies on B (A), or
  //   - an edge of A intersects and edge of B without sharing a vertex
  //
  // Determine if the vertex opposite edge (a0,a1) in triangle A lies in
  // (intersects) triangle B
  const auto & opposite_point_inside = [](
    const Triangle_3 & A, const Index a2, const Triangle_3 & B) 
    -> bool
  {
    return CGAL::do_intersect(A.vertex(a2),B);
  };
 
  // Determine if edge opposite vertex va in triangle A intersects edge
  // opposite vertex vb in triangle B.
  const auto & opposite_edges_intersect = [](
    const Triangle_3 & A, const Index va,
    const Triangle_3 & B, const Index vb) -> bool
  {
    Segment_3 sa( A.vertex((va+1)%3), A.vertex((va+2)%3));
    Segment_3 sb( B.vertex((vb+1)%3), B.vertex((vb+2)%3));
    bool ret = CGAL::do_intersect(sa,sb);
    return ret;
  };
 
  if( 
    !opposite_point_inside(A,a2,B) &&
    !opposite_point_inside(B,b2,A) &&
    !opposite_edges_intersect(A,shared[0].first,B,shared[1].second) && 
    !opposite_edges_intersect(A,shared[1].first,B,shared[0].second))
  {
    return false;
  }
 
  // there is an intersection indeed
  count_intersection(fa,fb);
  if(params.detect_only)
  {
    return true;
  }
  // Construct intersection
  try
  {
    // This can fail for Epick but not Epeck
    CGAL::Object result = CGAL::intersection(A,B);
    if(!result.empty())
    {
      if(CGAL::object_cast<Segment_3 >(&result))
      {
        // not coplanar
        assert(false && 
          "Co-planar non-degenerate triangles should intersect over triangle");
        return false;
      } else if(CGAL::object_cast<Point_3 >(&result))
      {
        // this "shouldn't" happen but does for inexact
        assert(false && 
          "Co-planar non-degenerate triangles should intersect over triangle");
        return false;
      } else
      {
        // Triangle object
        std::lock_guard<std::mutex> guard(m_offending_lock);
        offending[fa].push_back({fb, result});
        offending[fb].push_back({fa, result});
        return true;
      }
    }else
    {
      // CGAL::intersection is disagreeing with do_intersect
      assert(false && "CGAL::intersection should agree with predicate tests");
      return false;
    }
  }catch(...)
  {
    // This catches some cgal assertion:
    //     CGAL error: assertion violation!
    //     Expression : is_finite(d)
    //     File       : /opt/local/include/CGAL/GMP/Gmpq_type.h
    //     Line       : 132
    //     Explanation: 
    // But only if NDEBUG is not defined, otherwise there's an uncaught
    // "Floating point exception: 8" SIGFPE
    return false;
  }
  // No intersection.
  return false;
}

intersect()

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

bool igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::intersect ( const Triangle_3 &  A, const Triangle_3 &  B, const Index  fa, const Index  fb  )

inlineprivate

{
  // Determine whether there is an intersection
  if(!CGAL::do_intersect(A,B))
  {
    return false;
  }
  count_intersection(fa,fb);
  if(!params.detect_only)
  {
    // Construct intersection
    CGAL::Object result = CGAL::intersection(A,B);
    std::lock_guard<std::mutex> guard(m_offending_lock);
    offending[fa].push_back({fb, result});
    offending[fb].push_back({fa, result});
  }
  return true;
}

mark_offensive()

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

void igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::mark_offensive ( const Index  f )

inlineprivate

{
  using namespace std;
  lIF.push_back(f);
  if(offending.count(f) == 0)
  {
    // first time marking, initialize with new id and empty list
    offending[f] = {};
  }
}

process_intersecting_boxes()

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

void igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::process_intersecting_boxes

inline

{
  std::vector<std::mutex> triangle_locks(T.size());
  std::vector<std::mutex> vertex_locks(V.rows());
  std::mutex index_lock;
  std::mutex exception_mutex;
  bool exception_fired = false;
  int exception = -1;
  auto process_chunk = 
    [&](
      const size_t first, 
      const size_t last) -> void
  {
    try
    {
      assert(last >= first);
 
      for (size_t i=first; i<last; i++) 
      {
        if(exception_fired) return;
        Index fa=T.size(), fb=T.size();
        {
          // Before knowing which triangles are involved, we need to lock
          // everything to prevent race condition in updating reference
          // counters.
          std::lock_guard<std::mutex> guard(index_lock);
          const auto& tri_pair = candidate_triangle_pairs[i];
          fa = tri_pair.first - T.begin();
          fb = tri_pair.second - T.begin();
        }
        assert(fa < T.size());
        assert(fb < T.size());
 
        // Lock triangles
        std::lock_guard<std::mutex> guard_A(triangle_locks[fa]);
        std::lock_guard<std::mutex> guard_B(triangle_locks[fb]);
 
        // Lock vertices
        std::list<std::lock_guard<std::mutex> > guard_vertices;
        {
          std::vector<typename DerivedF::Scalar> unique_vertices;
          std::vector<size_t> tmp1, tmp2;
          igl::unique({F(fa,0), F(fa,1), F(fa,2), F(fb,0), F(fb,1), F(fb,2)},
              unique_vertices, tmp1, tmp2);
          std::for_each(unique_vertices.begin(), unique_vertices.end(),
              [&](const typename DerivedF::Scalar& vi) {
              guard_vertices.emplace_back(vertex_locks[vi]);
              });
        }
        if(exception_fired) return;
 
        const Triangle_3& A = T[fa];
        const Triangle_3& B = T[fb];
 
        // Number of combinatorially shared vertices
        Index comb_shared_vertices = 0;
        // Number of geometrically shared vertices (*not* including
        // combinatorially shared)
        Index geo_shared_vertices = 0;
        // Keep track of shared vertex indices
        std::vector<std::pair<Index,Index> > shared;
        Index ea,eb;
        for(ea=0;ea<3;ea++)
        {
          for(eb=0;eb<3;eb++)
          {
            if(F(fa,ea) == F(fb,eb))
            {
              comb_shared_vertices++;
              shared.emplace_back(ea,eb);
            }else if(A.vertex(ea) == B.vertex(eb))
            {
              geo_shared_vertices++;
              shared.emplace_back(ea,eb);
            }
          }
        }
        const Index total_shared_vertices = 
          comb_shared_vertices + geo_shared_vertices;
        if(exception_fired) return;
 
        if(comb_shared_vertices== 3)
        {
          assert(shared.size() == 3);
          // Combinatorially duplicate face, these should be removed by
          // preprocessing
          continue;
        }
        if(total_shared_vertices== 3)
        {
          assert(shared.size() == 3);
          // Geometrically duplicate face, these should be removed by
          // preprocessing
          continue;
        }
        if(total_shared_vertices == 2)
        {
          assert(shared.size() == 2);
          // Q: What about coplanar?
          //
          // o    o
          // |\  /|
          // | \/ |
          // | /\ |
          // |/  \|
          // o----o
          double_shared_vertex(A,B,fa,fb,shared);
          continue;
        }
        assert(total_shared_vertices<=1);
        if(total_shared_vertices==1)
        {
          single_shared_vertex(A,B,fa,fb,shared[0].first,shared[0].second);
        }else
        {
          intersect(A,B,fa,fb);
        }
      }
    }catch(int e)
    {
      std::lock_guard<std::mutex> exception_lock(exception_mutex);
      exception_fired = true;
      exception = e;
    }
  };
  size_t num_threads=0;
  const size_t hardware_limit = std::thread::hardware_concurrency();
  if (const char* igl_num_threads = std::getenv("LIBIGL_NUM_THREADS")) {
    num_threads = atoi(igl_num_threads);
  }
  if (num_threads == 0 || num_threads > hardware_limit) {
    num_threads = hardware_limit;
  }
  assert(num_threads > 0);
  const size_t num_pairs = candidate_triangle_pairs.size();
  const size_t chunk_size = num_pairs / num_threads;
  std::vector<std::thread> threads;
  for (size_t i=0; i<num_threads-1; i++) 
  {
    threads.emplace_back(process_chunk, i*chunk_size, (i+1)*chunk_size);
  }
  // Do some work in the master thread.
  process_chunk((num_threads-1)*chunk_size, num_pairs);
  for (auto& t : threads) 
  {
    if (t.joinable()) t.join();
  }
  if(exception_fired) throw exception;
  //process_chunk(0, candidate_triangle_pairs.size());
}

References igl::intersect(), and igl::unique().

Referenced by igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::SelfIntersectMesh().

Here is the call graph for this function:

Here is the caller graph for this function:

single_shared_vertex() [1/2]

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

bool igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::single_shared_vertex ( const Triangle_3 &  A, const Triangle_3 &  B, const Index  fa, const Index  fb, const Index  va  )

inlineprivate

{
  // This was not a good idea. It will not handle coplanar triangles well.
  using namespace std;
  Segment_3 sa(
    A.vertex((va+1)%3),
    A.vertex((va+2)%3));
 
  if(CGAL::do_intersect(sa,B))
  {
    // can't put count_intersection(fa,fb) here since we use intersect below
    // and then it will be counted twice.
    if(params.detect_only)
    {
      count_intersection(fa,fb);
      return true;
    }
    CGAL::Object result = CGAL::intersection(sa,B);
    if(const Point_3 * p = CGAL::object_cast<Point_3 >(&result))
    {
      // Single intersection --> segment from shared point to intersection
      CGAL::Object seg = CGAL::make_object(Segment_3(
        A.vertex(va),
        *p));
      count_intersection(fa,fb);
      std::lock_guard<std::mutex> guard(m_offending_lock);
      offending[fa].push_back({fb, seg});
      offending[fb].push_back({fa, seg});
      return true;
    }else if(CGAL::object_cast<Segment_3 >(&result))
    {
      // Need to do full test. Intersection could be a general poly.
      bool test = intersect(A,B,fa,fb);
      ((void)test);
      assert(test && "intersect should agree with do_intersect");
      return true;
    }else
    {
      cerr<<REDRUM("Segment ∩ triangle neither point nor segment?")<<endl;
      assert(false);
    }
  }
 
  return false;
}

References igl::intersect(), REDRUM, and void().

Here is the call graph for this function:

single_shared_vertex() [2/2]

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

bool igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::single_shared_vertex ( const Triangle_3 &  A, const Triangle_3 &  B, const Index  fa, const Index  fb, const Index  va, const Index  vb  )

inlineprivate

{
  if(single_shared_vertex(A,B,fa,fb,va))
  {
    return true;
  }
  return single_shared_vertex(B,A,fb,fa,vb);
}

Member Data Documentation

candidate_triangle_pairs

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

std::vector<std::pair<TrianglesIterator, TrianglesIterator> > igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::candidate_triangle_pairs

count

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

Index igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::count

F

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

const Eigen::MatrixBase<DerivedF>& igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::F

Referenced by igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::SelfIntersectMesh().

lIF

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

IndexList igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::lIF

Referenced by igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::SelfIntersectMesh().

m_offending_lock

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

std::mutex igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::m_offending_lock

private

offending

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

std::map<Index,ObjectList> igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::offending

Referenced by igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::SelfIntersectMesh().

params

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

RemeshSelfIntersectionsParam igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::params

Referenced by igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::SelfIntersectMesh().

T

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

Triangles igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::T

Referenced by igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::SelfIntersectMesh().

V

template<typename Kernel , typename DerivedV , typename DerivedF , typename DerivedVV , typename DerivedFF , typename DerivedIF , typename DerivedJ , typename DerivedIM >

const Eigen::MatrixBase<DerivedV>& igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::V

Referenced by igl::copyleft::cgal::SelfIntersectMesh< Kernel, DerivedV, DerivedF, DerivedVV, DerivedFF, DerivedIF, DerivedJ, DerivedIM >::SelfIntersectMesh().

---

The documentation for this class was generated from the following file:

• src/libigl/igl/copyleft/cgal/SelfIntersectMesh.h