SelfIntersectMesh.h 29 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007
  1. // This file is part of libigl, a simple c++ geometry processing library.
  2. //
  3. // Copyright (C) 2014 Alec Jacobson <alecjacobson@gmail.com>
  4. //
  5. // This Source Code Form is subject to the terms of the Mozilla Public License
  6. // v. 2.0. If a copy of the MPL was not distributed with this file, You can
  7. // obtain one at http://mozilla.org/MPL/2.0/.
  8. #ifndef IGL_COPYLEFT_CGAL_SELFINTERSECTMESH_H
  9. #define IGL_COPYLEFT_CGAL_SELFINTERSECTMESH_H
  10. #include "CGAL_includes.hpp"
  11. #include "RemeshSelfIntersectionsParam.h"
  12. #include "../../unique.h"
  13. #include <Eigen/Dense>
  14. #include <list>
  15. #include <map>
  16. #include <vector>
  17. #include <thread>
  18. #include <mutex>
  19. //#define IGL_SELFINTERSECTMESH_DEBUG
  20. #ifndef IGL_FIRST_HIT_EXCEPTION
  21. #define IGL_FIRST_HIT_EXCEPTION 10
  22. #endif
  23. // The easiest way to keep track of everything is to use a class
  24. namespace igl
  25. {
  26. namespace copyleft
  27. {
  28. namespace cgal
  29. {
  30. // Kernel is a CGAL kernel like:
  31. // CGAL::Exact_predicates_inexact_constructions_kernel
  32. // or
  33. // CGAL::Exact_predicates_exact_constructions_kernel
  34. template <
  35. typename Kernel,
  36. typename DerivedV,
  37. typename DerivedF,
  38. typename DerivedVV,
  39. typename DerivedFF,
  40. typename DerivedIF,
  41. typename DerivedJ,
  42. typename DerivedIM>
  43. class SelfIntersectMesh
  44. {
  45. typedef
  46. SelfIntersectMesh<
  47. Kernel,
  48. DerivedV,
  49. DerivedF,
  50. DerivedVV,
  51. DerivedFF,
  52. DerivedIF,
  53. DerivedJ,
  54. DerivedIM> Self;
  55. public:
  56. // 3D Primitives
  57. typedef CGAL::Point_3<Kernel> Point_3;
  58. typedef CGAL::Segment_3<Kernel> Segment_3;
  59. typedef CGAL::Triangle_3<Kernel> Triangle_3;
  60. typedef CGAL::Plane_3<Kernel> Plane_3;
  61. typedef CGAL::Tetrahedron_3<Kernel> Tetrahedron_3;
  62. //typedef CGAL::Polyhedron_3<Kernel> Polyhedron_3;
  63. //typedef CGAL::Nef_polyhedron_3<Kernel> Nef_polyhedron_3;
  64. // 2D Primitives
  65. typedef CGAL::Point_2<Kernel> Point_2;
  66. typedef CGAL::Segment_2<Kernel> Segment_2;
  67. typedef CGAL::Triangle_2<Kernel> Triangle_2;
  68. // 2D Constrained Delaunay Triangulation types
  69. typedef CGAL::Triangulation_vertex_base_2<Kernel> TVB_2;
  70. typedef CGAL::Constrained_triangulation_face_base_2<Kernel> CTFB_2;
  71. typedef CGAL::Triangulation_data_structure_2<TVB_2,CTFB_2> TDS_2;
  72. typedef CGAL::Exact_intersections_tag Itag;
  73. typedef CGAL::Constrained_Delaunay_triangulation_2<Kernel,TDS_2,Itag>
  74. CDT_2;
  75. typedef CGAL::Constrained_triangulation_plus_2<CDT_2> CDT_plus_2;
  76. // Axis-align boxes for all-pairs self-intersection detection
  77. typedef std::vector<Triangle_3> Triangles;
  78. typedef typename Triangles::iterator TrianglesIterator;
  79. typedef typename Triangles::const_iterator TrianglesConstIterator;
  80. typedef
  81. CGAL::Box_intersection_d::Box_with_handle_d<double,3,TrianglesIterator>
  82. Box;
  83. // Input mesh
  84. const Eigen::PlainObjectBase<DerivedV> & V;
  85. const Eigen::PlainObjectBase<DerivedF> & F;
  86. // Number of self-intersecting triangle pairs
  87. typedef typename DerivedF::Index Index;
  88. Index count;
  89. typedef std::vector<std::pair<Index, CGAL::Object>> ObjectList;
  90. // Using a vector here makes this **not** output sensitive
  91. Triangles T;
  92. typedef std::vector<Index> IndexList;
  93. IndexList lIF;
  94. // #F-long list of faces with intersections mapping to the order in
  95. // which they were first found
  96. std::map<Index,ObjectList> offending;
  97. // Make a short name for the edge map's key
  98. typedef std::pair<Index,Index> EMK;
  99. // Make a short name for the type stored at each edge, the edge map's
  100. // value
  101. typedef std::vector<Index> EMV;
  102. // Make a short name for the edge map
  103. typedef std::map<EMK,EMV> EdgeMap;
  104. // Maps edges of offending faces to all incident offending faces
  105. //EdgeMap edge2faces;
  106. std::vector<std::pair<const Box, const Box> > candidate_box_pairs;
  107. public:
  108. RemeshSelfIntersectionsParam params;
  109. public:
  110. // Constructs (VV,FF) a new mesh with self-intersections of (V,F)
  111. // subdivided
  112. //
  113. // See also: remesh_self_intersections.h
  114. inline SelfIntersectMesh(
  115. const Eigen::PlainObjectBase<DerivedV> & V,
  116. const Eigen::PlainObjectBase<DerivedF> & F,
  117. const RemeshSelfIntersectionsParam & params,
  118. Eigen::PlainObjectBase<DerivedVV> & VV,
  119. Eigen::PlainObjectBase<DerivedFF> & FF,
  120. Eigen::PlainObjectBase<DerivedIF> & IF,
  121. Eigen::PlainObjectBase<DerivedJ> & J,
  122. Eigen::PlainObjectBase<DerivedIM> & IM);
  123. private:
  124. // Helper function to mark a face as offensive
  125. //
  126. // Inputs:
  127. // f index of face in F
  128. inline void mark_offensive(const Index f);
  129. // Helper function to count intersections between faces
  130. //
  131. // Input:
  132. // fa index of face A in F
  133. // fb index of face B in F
  134. inline void count_intersection( const Index fa, const Index fb);
  135. // Helper function for box_intersect. Intersect two triangles A and B,
  136. // append the intersection object (point,segment,triangle) to a running
  137. // list for A and B
  138. //
  139. // Inputs:
  140. // A triangle in 3D
  141. // B triangle in 3D
  142. // fa index of A in F (and key into offending)
  143. // fb index of B in F (and key into offending)
  144. // Returns true only if A intersects B
  145. //
  146. inline bool intersect(
  147. const Triangle_3 & A,
  148. const Triangle_3 & B,
  149. const Index fa,
  150. const Index fb);
  151. // Helper function for box_intersect. In the case where A and B have
  152. // already been identified to share a vertex, then we only want to add
  153. // possible segment intersections. Assumes truly duplicate triangles are
  154. // not given as input
  155. //
  156. // Inputs:
  157. // A triangle in 3D
  158. // B triangle in 3D
  159. // fa index of A in F (and key into offending)
  160. // fb index of B in F (and key into offending)
  161. // va index of shared vertex in A (and key into offending)
  162. // vb index of shared vertex in B (and key into offending)
  163. //// Returns object of intersection (should be Segment or point)
  164. // Returns true if intersection (besides shared point)
  165. //
  166. inline bool single_shared_vertex(
  167. const Triangle_3 & A,
  168. const Triangle_3 & B,
  169. const Index fa,
  170. const Index fb,
  171. const Index va,
  172. const Index vb);
  173. // Helper handling one direction
  174. inline bool single_shared_vertex(
  175. const Triangle_3 & A,
  176. const Triangle_3 & B,
  177. const Index fa,
  178. const Index fb,
  179. const Index va);
  180. // Helper function for box_intersect. In the case where A and B have
  181. // already been identified to share two vertices, then we only want to add
  182. // a possible coplanar (Triangle) intersection. Assumes truly degenerate
  183. // facets are not givin as input.
  184. inline bool double_shared_vertex(
  185. const Triangle_3 & A,
  186. const Triangle_3 & B,
  187. const Index fa,
  188. const Index fb,
  189. const std::vector<std::pair<Index,Index> > shared);
  190. public:
  191. // Callback function called during box self intersections test. Means
  192. // boxes a and b intersect. This method then checks if the triangles in
  193. // each box intersect and if so, then processes the intersections
  194. //
  195. // Inputs:
  196. // a box containing a triangle
  197. // b box containing a triangle
  198. inline void box_intersect(const Box& a, const Box& b);
  199. inline void process_intersecting_boxes();
  200. private:
  201. // Compute 2D delaunay triangulation of a given 3d triangle and a list of
  202. // intersection objects (points,segments,triangles). CGAL uses an affine
  203. // projection rather than an isometric projection, so we're not
  204. // guaranteed that the 2D delaunay triangulation here will be a delaunay
  205. // triangulation in 3D.
  206. //
  207. // Inputs:
  208. // A triangle in 3D
  209. // A_objects_3 updated list of intersection objects for A
  210. // Outputs:
  211. // cdt Contrained delaunay triangulation in projected 2D plane
  212. public:
  213. // Getters:
  214. //const IndexList& get_lIF() const{ return lIF;}
  215. static inline void box_intersect_static(
  216. SelfIntersectMesh * SIM,
  217. const Box &a,
  218. const Box &b);
  219. private:
  220. std::mutex m_offending_lock;
  221. };
  222. }
  223. }
  224. }
  225. // Implementation
  226. #include "mesh_to_cgal_triangle_list.h"
  227. #include "remesh_intersections.h"
  228. #include "../../REDRUM.h"
  229. #include "../../get_seconds.h"
  230. #include "../../C_STR.h"
  231. #include <functional>
  232. #include <algorithm>
  233. #include <exception>
  234. #include <cassert>
  235. #include <iostream>
  236. // References:
  237. // http://minregret.googlecode.com/svn/trunk/skyline/src/extern/CGAL-3.3.1/examples/Polyhedron/polyhedron_self_intersection.cpp
  238. // http://www.cgal.org/Manual/3.9/examples/Boolean_set_operations_2/do_intersect.cpp
  239. // Q: Should we be using CGAL::Polyhedron_3?
  240. // A: No! Input is just a list of unoriented triangles. Polyhedron_3 requires
  241. // a 2-manifold.
  242. // A: But! It seems we could use CGAL::Triangulation_3. Though it won't be easy
  243. // to take advantage of functions like insert_in_facet because we want to
  244. // constrain segments. Hmmm. Actualy Triangulation_3 doesn't look right...
  245. //static void box_intersect(SelfIntersectMesh * SIM,const Box & A, const Box & B)
  246. //{
  247. // return SIM->box_intersect(A,B);
  248. //}
  249. // CGAL's box_self_intersection_d uses C-style function callbacks without
  250. // userdata. This is a leapfrog method for calling a member function. It should
  251. // be bound as if the prototype was:
  252. // static void box_intersect(const Box &a, const Box &b)
  253. // using boost:
  254. // boost::function<void(const Box &a,const Box &b)> cb
  255. // = boost::bind(&::box_intersect, this, _1,_2);
  256. //
  257. template <
  258. typename Kernel,
  259. typename DerivedV,
  260. typename DerivedF,
  261. typename DerivedVV,
  262. typename DerivedFF,
  263. typename DerivedIF,
  264. typename DerivedJ,
  265. typename DerivedIM>
  266. inline void igl::copyleft::cgal::SelfIntersectMesh<
  267. Kernel,
  268. DerivedV,
  269. DerivedF,
  270. DerivedVV,
  271. DerivedFF,
  272. DerivedIF,
  273. DerivedJ,
  274. DerivedIM>::box_intersect_static(
  275. Self * SIM,
  276. const typename Self::Box &a,
  277. const typename Self::Box &b)
  278. {
  279. SIM->box_intersect(a,b);
  280. }
  281. template <
  282. typename Kernel,
  283. typename DerivedV,
  284. typename DerivedF,
  285. typename DerivedVV,
  286. typename DerivedFF,
  287. typename DerivedIF,
  288. typename DerivedJ,
  289. typename DerivedIM>
  290. inline igl::copyleft::cgal::SelfIntersectMesh<
  291. Kernel,
  292. DerivedV,
  293. DerivedF,
  294. DerivedVV,
  295. DerivedFF,
  296. DerivedIF,
  297. DerivedJ,
  298. DerivedIM>::SelfIntersectMesh(
  299. const Eigen::PlainObjectBase<DerivedV> & V,
  300. const Eigen::PlainObjectBase<DerivedF> & F,
  301. const RemeshSelfIntersectionsParam & params,
  302. Eigen::PlainObjectBase<DerivedVV> & VV,
  303. Eigen::PlainObjectBase<DerivedFF> & FF,
  304. Eigen::PlainObjectBase<DerivedIF> & IF,
  305. Eigen::PlainObjectBase<DerivedJ> & J,
  306. Eigen::PlainObjectBase<DerivedIM> & IM):
  307. V(V),
  308. F(F),
  309. count(0),
  310. T(),
  311. lIF(),
  312. offending(),
  313. //edge2faces(),
  314. params(params)
  315. {
  316. using namespace std;
  317. using namespace Eigen;
  318. #ifdef IGL_SELFINTERSECTMESH_DEBUG
  319. const auto & tictoc = []() -> double
  320. {
  321. static double t_start = igl::get_seconds();
  322. double diff = igl::get_seconds()-t_start;
  323. t_start += diff;
  324. return diff;
  325. };
  326. const auto log_time = [&](const std::string& label) -> void{
  327. std::cout << "SelfIntersectMesh." << label << ": "
  328. << tictoc() << std::endl;
  329. };
  330. tictoc();
  331. #endif
  332. // Compute and process self intersections
  333. mesh_to_cgal_triangle_list(V,F,T);
  334. #ifdef IGL_SELFINTERSECTMESH_DEBUG
  335. log_time("convert_to_triangle_list");
  336. #endif
  337. // http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Box_intersection_d/Chapter_main.html#Section_63.5
  338. // Create the corresponding vector of bounding boxes
  339. std::vector<Box> boxes;
  340. boxes.reserve(T.size());
  341. for (
  342. TrianglesIterator tit = T.begin();
  343. tit != T.end();
  344. ++tit)
  345. {
  346. if (!tit->is_degenerate())
  347. {
  348. boxes.push_back(Box(tit->bbox(), tit));
  349. }
  350. }
  351. // Leapfrog callback
  352. std::function<void(const Box &a,const Box &b)> cb =
  353. std::bind(&box_intersect_static, this,
  354. // Explicitly use std namespace to avoid confusion with boost (who puts
  355. // _1 etc. in global namespace)
  356. std::placeholders::_1,
  357. std::placeholders::_2);
  358. #ifdef IGL_SELFINTERSECTMESH_DEBUG
  359. log_time("box_and_bind");
  360. #endif
  361. // Run the self intersection algorithm with all defaults
  362. CGAL::box_self_intersection_d(boxes.begin(), boxes.end(),cb);
  363. #ifdef IGL_SELFINTERSECTMESH_DEBUG
  364. log_time("box_intersection_d");
  365. #endif
  366. try{
  367. process_intersecting_boxes();
  368. }catch(int e)
  369. {
  370. // Rethrow if not IGL_FIRST_HIT_EXCEPTION
  371. if(e != IGL_FIRST_HIT_EXCEPTION)
  372. {
  373. throw e;
  374. }
  375. // Otherwise just fall through
  376. }
  377. #ifdef IGL_SELFINTERSECTMESH_DEBUG
  378. log_time("resolve_intersection");
  379. #endif
  380. // Convert lIF to Eigen matrix
  381. assert(lIF.size()%2 == 0);
  382. IF.resize(lIF.size()/2,2);
  383. {
  384. Index i=0;
  385. for(
  386. typename IndexList::const_iterator ifit = lIF.begin();
  387. ifit!=lIF.end();
  388. )
  389. {
  390. IF(i,0) = (*ifit);
  391. ifit++;
  392. IF(i,1) = (*ifit);
  393. ifit++;
  394. i++;
  395. }
  396. }
  397. #ifdef IGL_SELFINTERSECTMESH_DEBUG
  398. log_time("store_intersecting_face_pairs");
  399. #endif
  400. if(params.detect_only)
  401. {
  402. return;
  403. }
  404. remesh_intersections(
  405. V,F,T,offending,params.stitch_all,VV,FF,J,IM);
  406. #ifdef IGL_SELFINTERSECTMESH_DEBUG
  407. log_time("remesh_intersection");
  408. #endif
  409. }
  410. template <
  411. typename Kernel,
  412. typename DerivedV,
  413. typename DerivedF,
  414. typename DerivedVV,
  415. typename DerivedFF,
  416. typename DerivedIF,
  417. typename DerivedJ,
  418. typename DerivedIM>
  419. inline void igl::copyleft::cgal::SelfIntersectMesh<
  420. Kernel,
  421. DerivedV,
  422. DerivedF,
  423. DerivedVV,
  424. DerivedFF,
  425. DerivedIF,
  426. DerivedJ,
  427. DerivedIM>::mark_offensive(const Index f)
  428. {
  429. using namespace std;
  430. lIF.push_back(f);
  431. if(offending.count(f) == 0)
  432. {
  433. // first time marking, initialize with new id and empty list
  434. offending[f] = {};
  435. for(Index e = 0; e<3;e++)
  436. {
  437. // append face to edge's list
  438. Index i = F(f,(e+1)%3) < F(f,(e+2)%3) ? F(f,(e+1)%3) : F(f,(e+2)%3);
  439. Index j = F(f,(e+1)%3) < F(f,(e+2)%3) ? F(f,(e+2)%3) : F(f,(e+1)%3);
  440. //edge2faces[EMK(i,j)].push_back(f);
  441. }
  442. }
  443. }
  444. template <
  445. typename Kernel,
  446. typename DerivedV,
  447. typename DerivedF,
  448. typename DerivedVV,
  449. typename DerivedFF,
  450. typename DerivedIF,
  451. typename DerivedJ,
  452. typename DerivedIM>
  453. inline void igl::copyleft::cgal::SelfIntersectMesh<
  454. Kernel,
  455. DerivedV,
  456. DerivedF,
  457. DerivedVV,
  458. DerivedFF,
  459. DerivedIF,
  460. DerivedJ,
  461. DerivedIM>::count_intersection(
  462. const Index fa,
  463. const Index fb)
  464. {
  465. std::lock_guard<std::mutex> guard(m_offending_lock);
  466. mark_offensive(fa);
  467. mark_offensive(fb);
  468. this->count++;
  469. // We found the first intersection
  470. if(params.first_only && this->count >= 1)
  471. {
  472. throw IGL_FIRST_HIT_EXCEPTION;
  473. }
  474. }
  475. template <
  476. typename Kernel,
  477. typename DerivedV,
  478. typename DerivedF,
  479. typename DerivedVV,
  480. typename DerivedFF,
  481. typename DerivedIF,
  482. typename DerivedJ,
  483. typename DerivedIM>
  484. inline bool igl::copyleft::cgal::SelfIntersectMesh<
  485. Kernel,
  486. DerivedV,
  487. DerivedF,
  488. DerivedVV,
  489. DerivedFF,
  490. DerivedIF,
  491. DerivedJ,
  492. DerivedIM>::intersect(
  493. const Triangle_3 & A,
  494. const Triangle_3 & B,
  495. const Index fa,
  496. const Index fb)
  497. {
  498. // Determine whether there is an intersection
  499. if(!CGAL::do_intersect(A,B))
  500. {
  501. return false;
  502. }
  503. count_intersection(fa,fb);
  504. if(!params.detect_only)
  505. {
  506. // Construct intersection
  507. CGAL::Object result = CGAL::intersection(A,B);
  508. std::lock_guard<std::mutex> guard(m_offending_lock);
  509. offending[fa].push_back({fb, result});
  510. offending[fb].push_back({fa, result});
  511. }
  512. return true;
  513. }
  514. template <
  515. typename Kernel,
  516. typename DerivedV,
  517. typename DerivedF,
  518. typename DerivedVV,
  519. typename DerivedFF,
  520. typename DerivedIF,
  521. typename DerivedJ,
  522. typename DerivedIM>
  523. inline bool igl::copyleft::cgal::SelfIntersectMesh<
  524. Kernel,
  525. DerivedV,
  526. DerivedF,
  527. DerivedVV,
  528. DerivedFF,
  529. DerivedIF,
  530. DerivedJ,
  531. DerivedIM>::single_shared_vertex(
  532. const Triangle_3 & A,
  533. const Triangle_3 & B,
  534. const Index fa,
  535. const Index fb,
  536. const Index va,
  537. const Index vb)
  538. {
  539. ////using namespace std;
  540. //CGAL::Object result = CGAL::intersection(A,B);
  541. //if(CGAL::object_cast<Segment_3 >(&result))
  542. //{
  543. // // Append to each triangle's running list
  544. // F_objects[fa].push_back(result);
  545. // F_objects[fb].push_back(result);
  546. // count_intersection(fa,fb);
  547. //}else
  548. //{
  549. // // Then intersection must be at point
  550. // // And point must be at shared vertex
  551. // assert(CGAL::object_cast<Point_3>(&result));
  552. //}
  553. if(single_shared_vertex(A,B,fa,fb,va))
  554. {
  555. return true;
  556. }
  557. return single_shared_vertex(B,A,fb,fa,vb);
  558. }
  559. template <
  560. typename Kernel,
  561. typename DerivedV,
  562. typename DerivedF,
  563. typename DerivedVV,
  564. typename DerivedFF,
  565. typename DerivedIF,
  566. typename DerivedJ,
  567. typename DerivedIM>
  568. inline bool igl::copyleft::cgal::SelfIntersectMesh<
  569. Kernel,
  570. DerivedV,
  571. DerivedF,
  572. DerivedVV,
  573. DerivedFF,
  574. DerivedIF,
  575. DerivedJ,
  576. DerivedIM>::single_shared_vertex(
  577. const Triangle_3 & A,
  578. const Triangle_3 & B,
  579. const Index fa,
  580. const Index fb,
  581. const Index va)
  582. {
  583. // This was not a good idea. It will not handle coplanar triangles well.
  584. using namespace std;
  585. Segment_3 sa(
  586. A.vertex((va+1)%3),
  587. A.vertex((va+2)%3));
  588. if(CGAL::do_intersect(sa,B))
  589. {
  590. // can't put count_intersection(fa,fb) here since we use intersect below
  591. // and then it will be counted twice.
  592. if(params.detect_only)
  593. {
  594. count_intersection(fa,fb);
  595. return true;
  596. }
  597. CGAL::Object result = CGAL::intersection(sa,B);
  598. if(const Point_3 * p = CGAL::object_cast<Point_3 >(&result))
  599. {
  600. // Single intersection --> segment from shared point to intersection
  601. CGAL::Object seg = CGAL::make_object(Segment_3(
  602. A.vertex(va),
  603. *p));
  604. count_intersection(fa,fb);
  605. std::lock_guard<std::mutex> guard(m_offending_lock);
  606. offending[fa].push_back({fb, seg});
  607. offending[fb].push_back({fa, seg});
  608. return true;
  609. }else if(CGAL::object_cast<Segment_3 >(&result))
  610. {
  611. //cerr<<REDRUM("Coplanar at: "<<fa<<" & "<<fb<<" (single shared).")<<endl;
  612. // Must be coplanar
  613. // WRONG:
  614. //// Segment intersection --> triangle from shared point to intersection
  615. //CGAL::Object tri = CGAL::make_object(Triangle_3(
  616. // A.vertex(va),
  617. // s->vertex(0),
  618. // s->vertex(1)));
  619. //F_objects[fa].push_back(tri);
  620. //F_objects[fb].push_back(tri);
  621. //count_intersection(fa,fb);
  622. // Need to do full test. Intersection could be a general poly.
  623. bool test = intersect(A,B,fa,fb);
  624. ((void)test);
  625. assert(test && "intersect should agree with do_intersect");
  626. return true;
  627. }else
  628. {
  629. cerr<<REDRUM("Segment ∩ triangle neither point nor segment?")<<endl;
  630. assert(false);
  631. }
  632. }
  633. return false;
  634. }
  635. template <
  636. typename Kernel,
  637. typename DerivedV,
  638. typename DerivedF,
  639. typename DerivedVV,
  640. typename DerivedFF,
  641. typename DerivedIF,
  642. typename DerivedJ,
  643. typename DerivedIM>
  644. inline bool igl::copyleft::cgal::SelfIntersectMesh<
  645. Kernel,
  646. DerivedV,
  647. DerivedF,
  648. DerivedVV,
  649. DerivedFF,
  650. DerivedIF,
  651. DerivedJ,
  652. DerivedIM>::double_shared_vertex(
  653. const Triangle_3 & A,
  654. const Triangle_3 & B,
  655. const Index fa,
  656. const Index fb,
  657. const std::vector<std::pair<Index,Index> > shared)
  658. {
  659. using namespace std;
  660. // must be co-planar
  661. if(
  662. A.supporting_plane() != B.supporting_plane() &&
  663. A.supporting_plane() != B.supporting_plane().opposite())
  664. {
  665. return false;
  666. }
  667. // Since A and B are non-degenerate the intersection must be a polygon
  668. // (triangle). Either
  669. // - the vertex of A (B) opposite the shared edge of lies on B (A), or
  670. // - an edge of A intersects and edge of B without sharing a vertex
  671. // Determine if the vertex opposite edge (a0,a1) in triangle A lies in
  672. // (intersects) triangle B
  673. const auto & opposite_point_inside = [](
  674. const Triangle_3 & A, const Index a0, const Index a1, const Triangle_3 & B)
  675. -> bool
  676. {
  677. // get opposite index
  678. Index a2 = -1;
  679. for(int c = 0;c<3;c++)
  680. {
  681. if(c != a0 && c != a1)
  682. {
  683. a2 = c;
  684. break;
  685. }
  686. }
  687. assert(a2 != -1);
  688. bool ret = CGAL::do_intersect(A.vertex(a2),B);
  689. //cout<<"opposite_point_inside: "<<ret<<endl;
  690. return ret;
  691. };
  692. // Determine if edge opposite vertex va in triangle A intersects edge
  693. // opposite vertex vb in triangle B.
  694. const auto & opposite_edges_intersect = [](
  695. const Triangle_3 & A, const Index va,
  696. const Triangle_3 & B, const Index vb) -> bool
  697. {
  698. Segment_3 sa( A.vertex((va+1)%3), A.vertex((va+2)%3));
  699. Segment_3 sb( B.vertex((vb+1)%3), B.vertex((vb+2)%3));
  700. //cout<<sa<<endl;
  701. //cout<<sb<<endl;
  702. bool ret = CGAL::do_intersect(sa,sb);
  703. //cout<<"opposite_edges_intersect: "<<ret<<endl;
  704. return ret;
  705. };
  706. if(
  707. !opposite_point_inside(A,shared[0].first,shared[1].first,B) &&
  708. !opposite_point_inside(B,shared[0].second,shared[1].second,A) &&
  709. !opposite_edges_intersect(A,shared[0].first,B,shared[1].second) &&
  710. !opposite_edges_intersect(A,shared[1].first,B,shared[0].second))
  711. {
  712. return false;
  713. }
  714. // there is an intersection indeed
  715. count_intersection(fa,fb);
  716. if(params.detect_only)
  717. {
  718. return true;
  719. }
  720. // Construct intersection
  721. try
  722. {
  723. // This can fail for Epick but not Epeck
  724. CGAL::Object result = CGAL::intersection(A,B);
  725. if(!result.empty())
  726. {
  727. if(CGAL::object_cast<Segment_3 >(&result))
  728. {
  729. // not coplanar
  730. assert(false &&
  731. "Co-planar non-degenerate triangles should intersect over triangle");
  732. return false;
  733. } else if(CGAL::object_cast<Point_3 >(&result))
  734. {
  735. // this "shouldn't" happen but does for inexact
  736. assert(false &&
  737. "Co-planar non-degenerate triangles should intersect over triangle");
  738. return false;
  739. } else
  740. {
  741. // Triangle object
  742. std::lock_guard<std::mutex> guard(m_offending_lock);
  743. offending[fa].push_back({fb, result});
  744. offending[fb].push_back({fa, result});
  745. //cerr<<REDRUM("Coplanar at: "<<fa<<" & "<<fb<<" (double shared).")<<endl;
  746. return true;
  747. }
  748. }else
  749. {
  750. // CGAL::intersection is disagreeing with do_intersect
  751. assert(false && "CGAL::intersection should agree with predicate tests");
  752. return false;
  753. }
  754. }catch(...)
  755. {
  756. // This catches some cgal assertion:
  757. // CGAL error: assertion violation!
  758. // Expression : is_finite(d)
  759. // File : /opt/local/include/CGAL/GMP/Gmpq_type.h
  760. // Line : 132
  761. // Explanation:
  762. // But only if NDEBUG is not defined, otherwise there's an uncaught
  763. // "Floating point exception: 8" SIGFPE
  764. return false;
  765. }
  766. // No intersection.
  767. return false;
  768. }
  769. template <
  770. typename Kernel,
  771. typename DerivedV,
  772. typename DerivedF,
  773. typename DerivedVV,
  774. typename DerivedFF,
  775. typename DerivedIF,
  776. typename DerivedJ,
  777. typename DerivedIM>
  778. inline void igl::copyleft::cgal::SelfIntersectMesh<
  779. Kernel,
  780. DerivedV,
  781. DerivedF,
  782. DerivedVV,
  783. DerivedFF,
  784. DerivedIF,
  785. DerivedJ,
  786. DerivedIM>::box_intersect(
  787. const Box& a,
  788. const Box& b)
  789. {
  790. candidate_box_pairs.push_back({a, b});
  791. }
  792. template <
  793. typename Kernel,
  794. typename DerivedV,
  795. typename DerivedF,
  796. typename DerivedVV,
  797. typename DerivedFF,
  798. typename DerivedIF,
  799. typename DerivedJ,
  800. typename DerivedIM>
  801. inline void igl::copyleft::cgal::SelfIntersectMesh<
  802. Kernel,
  803. DerivedV,
  804. DerivedF,
  805. DerivedVV,
  806. DerivedFF,
  807. DerivedIF,
  808. DerivedJ,
  809. DerivedIM>::process_intersecting_boxes()
  810. {
  811. std::vector<std::mutex> triangle_locks(T.size());
  812. std::vector<std::mutex> vertex_locks(V.rows());
  813. std::mutex index_lock;
  814. std::mutex exception_mutex;
  815. bool exception_fired = false;
  816. int exception = -1;
  817. auto process_chunk =
  818. [&](
  819. const size_t first,
  820. const size_t last) -> void
  821. {
  822. try
  823. {
  824. assert(last >= first);
  825. for (size_t i=first; i<last; i++)
  826. {
  827. if(exception_fired) return;
  828. Index fa=T.size(), fb=T.size();
  829. {
  830. // Before knowing which triangles are involved, we need to lock
  831. // everything to prevent race condition in updating reference counters.
  832. std::lock_guard<std::mutex> guard(index_lock);
  833. const auto& box_pair = candidate_box_pairs[i];
  834. const auto& a = box_pair.first;
  835. const auto& b = box_pair.second;
  836. fa = a.handle()-T.begin();
  837. fb = b.handle()-T.begin();
  838. }
  839. assert(fa < T.size());
  840. assert(fb < T.size());
  841. // Lock triangles
  842. std::lock_guard<std::mutex> guard_A(triangle_locks[fa]);
  843. std::lock_guard<std::mutex> guard_B(triangle_locks[fb]);
  844. // Lock vertices
  845. std::list<std::lock_guard<std::mutex> > guard_vertices;
  846. {
  847. std::vector<typename DerivedF::Scalar> unique_vertices;
  848. std::vector<size_t> tmp1, tmp2;
  849. igl::unique({F(fa,0), F(fa,1), F(fa,2), F(fb,0), F(fb,1), F(fb,2)},
  850. unique_vertices, tmp1, tmp2);
  851. std::for_each(unique_vertices.begin(), unique_vertices.end(),
  852. [&](const typename DerivedF::Scalar& vi) {
  853. guard_vertices.emplace_back(vertex_locks[vi]);
  854. });
  855. }
  856. if(exception_fired) return;
  857. const Triangle_3& A = T[fa];
  858. const Triangle_3& B = T[fb];
  859. // Number of combinatorially shared vertices
  860. Index comb_shared_vertices = 0;
  861. // Number of geometrically shared vertices (*not* including combinatorially
  862. // shared)
  863. Index geo_shared_vertices = 0;
  864. // Keep track of shared vertex indices
  865. std::vector<std::pair<Index,Index> > shared;
  866. Index ea,eb;
  867. for(ea=0;ea<3;ea++)
  868. {
  869. for(eb=0;eb<3;eb++)
  870. {
  871. if(F(fa,ea) == F(fb,eb))
  872. {
  873. comb_shared_vertices++;
  874. shared.emplace_back(ea,eb);
  875. }else if(A.vertex(ea) == B.vertex(eb))
  876. {
  877. geo_shared_vertices++;
  878. shared.emplace_back(ea,eb);
  879. }
  880. }
  881. }
  882. const Index total_shared_vertices = comb_shared_vertices + geo_shared_vertices;
  883. if(exception_fired) return;
  884. if(comb_shared_vertices== 3)
  885. {
  886. assert(shared.size() == 3);
  887. //// Combinatorially duplicate face, these should be removed by preprocessing
  888. //cerr<<REDRUM("Facets "<<fa<<" and "<<fb<<" are combinatorial duplicates")<<endl;
  889. continue;
  890. }
  891. if(total_shared_vertices== 3)
  892. {
  893. assert(shared.size() == 3);
  894. //// Geometrically duplicate face, these should be removed by preprocessing
  895. //cerr<<REDRUM("Facets "<<fa<<" and "<<fb<<" are geometrical duplicates")<<endl;
  896. continue;
  897. }
  898. if(total_shared_vertices == 2)
  899. {
  900. assert(shared.size() == 2);
  901. // Q: What about coplanar?
  902. //
  903. // o o
  904. // |\ /|
  905. // | \/ |
  906. // | /\ |
  907. // |/ \|
  908. // o----o
  909. double_shared_vertex(A,B,fa,fb,shared);
  910. continue;
  911. }
  912. assert(total_shared_vertices<=1);
  913. if(total_shared_vertices==1)
  914. {
  915. single_shared_vertex(A,B,fa,fb,shared[0].first,shared[0].second);
  916. }else
  917. {
  918. intersect(A,B,fa,fb);
  919. }
  920. }
  921. }catch(int e)
  922. {
  923. std::lock_guard<std::mutex> exception_lock(exception_mutex);
  924. exception_fired = true;
  925. exception = e;
  926. }
  927. };
  928. size_t num_threads=0;
  929. const size_t hardware_limit = std::thread::hardware_concurrency();
  930. if (const char* igl_num_threads = std::getenv("LIBIGL_NUM_THREADS")) {
  931. num_threads = atoi(igl_num_threads);
  932. }
  933. if (num_threads == 0 || num_threads > hardware_limit) {
  934. num_threads = hardware_limit;
  935. }
  936. assert(num_threads > 0);
  937. const size_t num_pairs = candidate_box_pairs.size();
  938. const size_t chunk_size = num_pairs / num_threads;
  939. std::vector<std::thread> threads;
  940. for (size_t i=0; i<num_threads-1; i++)
  941. {
  942. threads.emplace_back(process_chunk, i*chunk_size, (i+1)*chunk_size);
  943. }
  944. // Do some work in the master thread.
  945. process_chunk((num_threads-1)*chunk_size, num_pairs);
  946. for (auto& t : threads)
  947. {
  948. if (t.joinable()) t.join();
  949. }
  950. if(exception_fired) throw exception;
  951. //process_chunk(0, candidate_box_pairs.size());
  952. }
  953. #endif