1 // This file is part of libigl, a simple c++ geometry processing library.
2 //
3 // Copyright (C) 2015 Qingnan Zhou <qnzhou@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 //
9 #include "extract_cells.h"
10 #include "closest_facet.h"
11 #include "order_facets_around_edge.h"
12 #include "outer_facet.h"
13 #include "submesh_aabb_tree.h"
14 #include "../../extract_manifold_patches.h"
15 #include "../../facet_components.h"
16 #include "../../get_seconds.h"
17 #include "../../triangle_triangle_adjacency.h"
18 #include "../../unique_edge_map.h"
19 #include "../../vertex_triangle_adjacency.h"
20
21 #include <CGAL/AABB_tree.h>
22 #include <CGAL/AABB_traits.h>
23 #include <CGAL/AABB_triangle_primitive.h>
24 #include <CGAL/intersections.h>
25 #include <CGAL/Exact_predicates_exact_constructions_kernel.h>
26
27 #include <iostream>
28 #include <vector>
29 #include <queue>
30 #include <map>
31 #include <set>
32
33 //#define EXTRACT_CELLS_DEBUG
34
35 template<
36 typename DerivedV,
37 typename DerivedF,
38 typename DerivedC >
extract_cells(const Eigen::PlainObjectBase<DerivedV> & V,const Eigen::PlainObjectBase<DerivedF> & F,Eigen::PlainObjectBase<DerivedC> & cells)39 IGL_INLINE size_t igl::copyleft::cgal::extract_cells(
40 const Eigen::PlainObjectBase<DerivedV>& V,
41 const Eigen::PlainObjectBase<DerivedF>& F,
42 Eigen::PlainObjectBase<DerivedC>& cells)
43 {
44 const size_t num_faces = F.rows();
45 // Construct edge adjacency
46 Eigen::MatrixXi E, uE;
47 Eigen::VectorXi EMAP;
48 std::vector<std::vector<size_t> > uE2E;
49 igl::unique_edge_map(F, E, uE, EMAP, uE2E);
50 // Cluster into manifold patches
51 Eigen::VectorXi P;
52 igl::extract_manifold_patches(F, EMAP, uE2E, P);
53 // Extract cells
54 DerivedC per_patch_cells;
55 const size_t num_cells =
56 igl::copyleft::cgal::extract_cells(V,F,P,E,uE,uE2E,EMAP,per_patch_cells);
57 // Distribute per-patch cell information to each face
58 cells.resize(num_faces, 2);
59 for (size_t i=0; i<num_faces; i++)
60 {
61 cells.row(i) = per_patch_cells.row(P[i]);
62 }
63 return num_cells;
64 }
65
66
67 template<
68 typename DerivedV,
69 typename DerivedF,
70 typename DerivedP,
71 typename DerivedE,
72 typename DeriveduE,
73 typename uE2EType,
74 typename DerivedEMAP,
75 typename DerivedC >
extract_cells(const Eigen::PlainObjectBase<DerivedV> & V,const Eigen::PlainObjectBase<DerivedF> & F,const Eigen::PlainObjectBase<DerivedP> & P,const Eigen::PlainObjectBase<DerivedE> & E,const Eigen::PlainObjectBase<DeriveduE> & uE,const std::vector<std::vector<uE2EType>> & uE2E,const Eigen::PlainObjectBase<DerivedEMAP> & EMAP,Eigen::PlainObjectBase<DerivedC> & cells)76 IGL_INLINE size_t igl::copyleft::cgal::extract_cells(
77 const Eigen::PlainObjectBase<DerivedV>& V,
78 const Eigen::PlainObjectBase<DerivedF>& F,
79 const Eigen::PlainObjectBase<DerivedP>& P,
80 const Eigen::PlainObjectBase<DerivedE>& E,
81 const Eigen::PlainObjectBase<DeriveduE>& uE,
82 const std::vector<std::vector<uE2EType> >& uE2E,
83 const Eigen::PlainObjectBase<DerivedEMAP>& EMAP,
84 Eigen::PlainObjectBase<DerivedC>& cells)
85 {
86 // Trivial base case
87 if(P.size() == 0)
88 {
89 assert(F.size() == 0);
90 cells.resize(0,2);
91 return 0;
92 }
93
94 typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
95 typedef Kernel::Point_3 Point_3;
96 typedef Kernel::Plane_3 Plane_3;
97 typedef Kernel::Segment_3 Segment_3;
98 typedef Kernel::Triangle_3 Triangle;
99 typedef std::vector<Triangle>::iterator Iterator;
100 typedef CGAL::AABB_triangle_primitive<Kernel, Iterator> Primitive;
101 typedef CGAL::AABB_traits<Kernel, Primitive> AABB_triangle_traits;
102 typedef CGAL::AABB_tree<AABB_triangle_traits> Tree;
103
104 #ifdef EXTRACT_CELLS_DEBUG
105 const auto & tictoc = []() -> double
106 {
107 static double t_start = igl::get_seconds();
108 double diff = igl::get_seconds()-t_start;
109 t_start += diff;
110 return diff;
111 };
112 const auto log_time = [&](const std::string& label) -> void {
113 std::cout << "extract_cells." << label << ": "
114 << tictoc() << std::endl;
115 };
116 tictoc();
117 #else
118 // no-op
119 const auto log_time = [](const std::string){};
120 #endif
121 const size_t num_faces = F.rows();
122 typedef typename DerivedF::Scalar Index;
123 assert(P.size() > 0);
124 const size_t num_patches = P.maxCoeff()+1;
125
126 // Extract all cells...
127 DerivedC raw_cells;
128 const size_t num_raw_cells =
129 extract_cells_single_component(V,F,P,uE,uE2E,EMAP,raw_cells);
130 log_time("extract_single_component_cells");
131
132 // Compute triangle-triangle adjacency data-structure
133 std::vector<std::vector<std::vector<Index > > > TT,_1;
134 igl::triangle_triangle_adjacency(E, EMAP, uE2E, false, TT, _1);
135 log_time("compute_face_adjacency");
136
137 // Compute connected components of the mesh
138 Eigen::VectorXi C, counts;
139 igl::facet_components(TT, C, counts);
140 log_time("form_components");
141
142 const size_t num_components = counts.size();
143 // components[c] --> list of face indices into F of faces in component c
144 std::vector<std::vector<size_t> > components(num_components);
145 // Loop over all faces
146 for (size_t i=0; i<num_faces; i++)
147 {
148 components[C[i]].push_back(i);
149 }
150 // Convert vector lists to Eigen lists...
151 // and precompute data-structures for each component
152 std::vector<std::vector<size_t> > VF,VFi;
153 igl::vertex_triangle_adjacency(V.rows(), F, VF, VFi);
154 std::vector<Eigen::VectorXi> Is(num_components);
155 std::vector<
156 CGAL::AABB_tree<
157 CGAL::AABB_traits<
158 Kernel,
159 CGAL::AABB_triangle_primitive<
160 Kernel, std::vector<
161 Kernel::Triangle_3 >::iterator > > > > trees(num_components);
162 std::vector< std::vector<Kernel::Triangle_3 > >
163 triangle_lists(num_components);
164 std::vector<std::vector<bool> > in_Is(num_components);
165
166 // Find outer facets, their orientations and cells for each component
167 Eigen::VectorXi outer_facets(num_components);
168 Eigen::VectorXi outer_facet_orientation(num_components);
169 Eigen::VectorXi outer_cells(num_components);
170 for (size_t i=0; i<num_components; i++)
171 {
172 Is[i].resize(components[i].size());
173 std::copy(components[i].begin(), components[i].end(),Is[i].data());
174 bool flipped;
175 igl::copyleft::cgal::outer_facet(V, F, Is[i], outer_facets[i], flipped);
176 outer_facet_orientation[i] = flipped?1:0;
177 outer_cells[i] = raw_cells(P[outer_facets[i]], outer_facet_orientation[i]);
178 }
179 #ifdef EXTRACT_CELLS_DEBUG
180 log_time("outer_facet_per_component");
181 #endif
182
183 // Compute barycenter of a triangle in mesh (V,F)
184 //
185 // Inputs:
186 // fid index into F
187 // Returns row-vector of barycenter coordinates
188 const auto get_triangle_center = [&V,&F](const size_t fid)
189 {
190 return ((V.row(F(fid,0))+V.row(F(fid,1))+V.row(F(fid,2)))/3.0).eval();
191 };
192 std::vector<std::vector<size_t> > nested_cells(num_raw_cells);
193 std::vector<std::vector<size_t> > ambient_cells(num_raw_cells);
194 std::vector<std::vector<size_t> > ambient_comps(num_components);
195 // Only bother if there's more than one component
196 if(num_components > 1)
197 {
198 // construct bounding boxes for each component
199 DerivedV bbox_min(num_components, 3);
200 DerivedV bbox_max(num_components, 3);
201 // Assuming our mesh (in exact numbers) fits in the range of double.
202 bbox_min.setConstant(std::numeric_limits<double>::max());
203 bbox_max.setConstant(std::numeric_limits<double>::min());
204 // Loop over faces
205 for (size_t i=0; i<num_faces; i++)
206 {
207 // component of this face
208 const auto comp_id = C[i];
209 const auto& f = F.row(i);
210 for (size_t j=0; j<3; j++)
211 {
212 for(size_t d=0;d<3;d++)
213 {
214 bbox_min(comp_id,d) = std::min(bbox_min(comp_id,d), V(f[j],d));
215 bbox_max(comp_id,d) = std::max(bbox_max(comp_id,d), V(f[j],d));
216 }
217 }
218 }
219 // Return true if box of component ci intersects that of cj
220 const auto bbox_intersects = [&bbox_max,&bbox_min](size_t ci, size_t cj)
221 {
222 return !(
223 bbox_max(ci,0) < bbox_min(cj,0) ||
224 bbox_max(ci,1) < bbox_min(cj,1) ||
225 bbox_max(ci,2) < bbox_min(cj,2) ||
226 bbox_max(cj,0) < bbox_min(ci,0) ||
227 bbox_max(cj,1) < bbox_min(ci,1) ||
228 bbox_max(cj,2) < bbox_min(ci,2));
229 };
230
231 // Loop over components. This section is O(m²)
232 for (size_t i=0; i<num_components; i++)
233 {
234 // List of components that could overlap with component i
235 std::vector<size_t> candidate_comps;
236 candidate_comps.reserve(num_components);
237 // Loop over components
238 for (size_t j=0; j<num_components; j++)
239 {
240 if (i == j) continue;
241 if (bbox_intersects(i,j)) candidate_comps.push_back(j);
242 }
243
244 const size_t num_candidate_comps = candidate_comps.size();
245 if (num_candidate_comps == 0) continue;
246
247 // Build aabb tree for this component.
248 submesh_aabb_tree(V,F,Is[i],trees[i],triangle_lists[i],in_Is[i]);
249
250 // Get query points on each candidate component: barycenter of
251 // outer-facet
252 DerivedV queries(num_candidate_comps, 3);
253 for (size_t j=0; j<num_candidate_comps; j++)
254 {
255 const size_t index = candidate_comps[j];
256 queries.row(j) = get_triangle_center(outer_facets[index]);
257 }
258
259 // Gather closest facets in ith component to each query point and their
260 // orientations
261 const auto& I = Is[i];
262 const auto& tree = trees[i];
263 const auto& in_I = in_Is[i];
264 const auto& triangles = triangle_lists[i];
265
266 Eigen::VectorXi closest_facets, closest_facet_orientations;
267 closest_facet(
268 V,
269 F,
270 I,
271 queries,
272 uE2E,
273 EMAP,
274 VF,
275 VFi,
276 tree,
277 triangles,
278 in_I,
279 closest_facets,
280 closest_facet_orientations);
281 // Loop over all candidates
282 for (size_t j=0; j<num_candidate_comps; j++)
283 {
284 const size_t index = candidate_comps[j];
285 const size_t closest_patch = P[closest_facets[j]];
286 const size_t closest_patch_side = closest_facet_orientations[j] ? 0:1;
287 // The cell id of the closest patch
288 const size_t ambient_cell =
289 raw_cells(closest_patch,closest_patch_side);
290 if (ambient_cell != (size_t)outer_cells[i])
291 {
292 // ---> component index inside component i, because the cell of the
293 // closest facet on i to component index is **not** the same as the
294 // "outer cell" of component i: component index is **not** outside of
295 // component i (therefore it's inside).
296 nested_cells[ambient_cell].push_back(outer_cells[index]);
297 ambient_cells[outer_cells[index]].push_back(ambient_cell);
298 ambient_comps[index].push_back(i);
299 }
300 }
301 }
302 }
303
304 #ifdef EXTRACT_CELLS_DEBUG
305 log_time("nested_relationship");
306 #endif
307
308 const size_t INVALID = std::numeric_limits<size_t>::max();
309 const size_t INFINITE_CELL = num_raw_cells;
310 std::vector<size_t> embedded_cells(num_raw_cells, INVALID);
311 for (size_t i=0; i<num_components; i++) {
312 const size_t outer_cell = outer_cells[i];
313 const auto& ambient_comps_i = ambient_comps[i];
314 const auto& ambient_cells_i = ambient_cells[outer_cell];
315 const size_t num_ambient_comps = ambient_comps_i.size();
316 assert(num_ambient_comps == ambient_cells_i.size());
317 if (num_ambient_comps > 0) {
318 size_t embedded_comp = INVALID;
319 size_t embedded_cell = INVALID;
320 for (size_t j=0; j<num_ambient_comps; j++) {
321 if (ambient_comps[ambient_comps_i[j]].size() ==
322 num_ambient_comps-1) {
323 embedded_comp = ambient_comps_i[j];
324 embedded_cell = ambient_cells_i[j];
325 break;
326 }
327 }
328 assert(embedded_comp != INVALID);
329 assert(embedded_cell != INVALID);
330 embedded_cells[outer_cell] = embedded_cell;
331 } else {
332 embedded_cells[outer_cell] = INFINITE_CELL;
333 }
334 }
335 for (size_t i=0; i<num_patches; i++) {
336 if (embedded_cells[raw_cells(i,0)] != INVALID) {
337 raw_cells(i,0) = embedded_cells[raw_cells(i, 0)];
338 }
339 if (embedded_cells[raw_cells(i,1)] != INVALID) {
340 raw_cells(i,1) = embedded_cells[raw_cells(i, 1)];
341 }
342 }
343
344 size_t count = 0;
345 std::vector<size_t> mapped_indices(num_raw_cells+1, INVALID);
346 // Always map infinite cell to index 0.
347 mapped_indices[INFINITE_CELL] = count;
348 count++;
349
350 for (size_t i=0; i<num_patches; i++) {
351 const size_t old_positive_cell_id = raw_cells(i, 0);
352 const size_t old_negative_cell_id = raw_cells(i, 1);
353 size_t positive_cell_id, negative_cell_id;
354 if (mapped_indices[old_positive_cell_id] == INVALID) {
355 mapped_indices[old_positive_cell_id] = count;
356 positive_cell_id = count;
357 count++;
358 } else {
359 positive_cell_id = mapped_indices[old_positive_cell_id];
360 }
361 if (mapped_indices[old_negative_cell_id] == INVALID) {
362 mapped_indices[old_negative_cell_id] = count;
363 negative_cell_id = count;
364 count++;
365 } else {
366 negative_cell_id = mapped_indices[old_negative_cell_id];
367 }
368 raw_cells(i, 0) = positive_cell_id;
369 raw_cells(i, 1) = negative_cell_id;
370 }
371 cells = raw_cells;
372 #ifdef EXTRACT_CELLS_DEBUG
373 log_time("finalize");
374 #endif
375 return count;
376 }
377
378 template<
379 typename DerivedV,
380 typename DerivedF,
381 typename DerivedP,
382 typename DeriveduE,
383 typename uE2EType,
384 typename DerivedEMAP,
385 typename DerivedC>
extract_cells_single_component(const Eigen::PlainObjectBase<DerivedV> & V,const Eigen::PlainObjectBase<DerivedF> & F,const Eigen::PlainObjectBase<DerivedP> & P,const Eigen::PlainObjectBase<DeriveduE> & uE,const std::vector<std::vector<uE2EType>> & uE2E,const Eigen::PlainObjectBase<DerivedEMAP> & EMAP,Eigen::PlainObjectBase<DerivedC> & cells)386 IGL_INLINE size_t igl::copyleft::cgal::extract_cells_single_component(
387 const Eigen::PlainObjectBase<DerivedV>& V,
388 const Eigen::PlainObjectBase<DerivedF>& F,
389 const Eigen::PlainObjectBase<DerivedP>& P,
390 const Eigen::PlainObjectBase<DeriveduE>& uE,
391 const std::vector<std::vector<uE2EType> >& uE2E,
392 const Eigen::PlainObjectBase<DerivedEMAP>& EMAP,
393 Eigen::PlainObjectBase<DerivedC>& cells)
394 {
395 const size_t num_faces = F.rows();
396 // Input:
397 // index index into #F*3 list of undirect edges
398 // Returns index into face
399 const auto edge_index_to_face_index = [&num_faces](size_t index)
400 {
401 return index % num_faces;
402 };
403 // Determine if a face (containing undirected edge {s,d} is consistently
404 // oriented with directed edge {s,d} (or otherwise it is with {d,s})
405 //
406 // Inputs:
407 // fid face index into F
408 // s source index of edge
409 // d destination index of edge
410 // Returns true if face F(fid,:) is consistent with {s,d}
411 const auto is_consistent =
412 [&F](const size_t fid, const size_t s, const size_t d) -> bool
413 {
414 if ((size_t)F(fid, 0) == s && (size_t)F(fid, 1) == d) return false;
415 if ((size_t)F(fid, 1) == s && (size_t)F(fid, 2) == d) return false;
416 if ((size_t)F(fid, 2) == s && (size_t)F(fid, 0) == d) return false;
417
418 if ((size_t)F(fid, 0) == d && (size_t)F(fid, 1) == s) return true;
419 if ((size_t)F(fid, 1) == d && (size_t)F(fid, 2) == s) return true;
420 if ((size_t)F(fid, 2) == d && (size_t)F(fid, 0) == s) return true;
421 throw "Invalid face!";
422 return false;
423 };
424
425 const size_t num_unique_edges = uE.rows();
426 const size_t num_patches = P.maxCoeff() + 1;
427
428 // Build patch-patch adjacency list.
429 std::vector<std::map<size_t, size_t> > patch_adj(num_patches);
430 for (size_t i=0; i<num_unique_edges; i++) {
431 const size_t s = uE(i,0);
432 const size_t d = uE(i,1);
433 const auto adj_faces = uE2E[i];
434 const size_t num_adj_faces = adj_faces.size();
435 if (num_adj_faces > 2) {
436 for (size_t j=0; j<num_adj_faces; j++) {
437 const size_t patch_j = P[edge_index_to_face_index(adj_faces[j])];
438 for (size_t k=j+1; k<num_adj_faces; k++) {
439 const size_t patch_k = P[edge_index_to_face_index(adj_faces[k])];
440 if (patch_adj[patch_j].find(patch_k) == patch_adj[patch_j].end()) {
441 patch_adj[patch_j].insert({patch_k, i});
442 }
443 if (patch_adj[patch_k].find(patch_j) == patch_adj[patch_k].end()) {
444 patch_adj[patch_k].insert({patch_j, i});
445 }
446 }
447 }
448 }
449 }
450
451
452 const int INVALID = std::numeric_limits<int>::max();
453 std::vector<size_t> cell_labels(num_patches * 2);
454 for (size_t i=0; i<num_patches; i++) cell_labels[i] = i;
455 std::vector<std::set<size_t> > equivalent_cells(num_patches*2);
456 std::vector<bool> processed(num_unique_edges, false);
457
458 size_t label_count=0;
459 for (size_t i=0; i<num_patches; i++) {
460 for (const auto& entry : patch_adj[i]) {
461 const size_t neighbor_patch = entry.first;
462 const size_t uei = entry.second;
463 if (processed[uei]) continue;
464 processed[uei] = true;
465
466 const auto& adj_faces = uE2E[uei];
467 const size_t num_adj_faces = adj_faces.size();
468 assert(num_adj_faces > 2);
469
470 const size_t s = uE(uei,0);
471 const size_t d = uE(uei,1);
472
473 std::vector<int> signed_adj_faces;
474 for (auto ej : adj_faces)
475 {
476 const size_t fid = edge_index_to_face_index(ej);
477 bool cons = is_consistent(fid, s, d);
478 signed_adj_faces.push_back((fid+1)*(cons ? 1:-1));
479 }
480 {
481 // Sort adjacent faces cyclically around {s,d}
482 Eigen::VectorXi order;
483 // order[f] will reveal the order of face f in signed_adj_faces
484 order_facets_around_edge(V, F, s, d, signed_adj_faces, order);
485 for (size_t j=0; j<num_adj_faces; j++) {
486 const size_t curr_idx = j;
487 const size_t next_idx = (j+1)%num_adj_faces;
488 const size_t curr_patch_idx =
489 P[edge_index_to_face_index(adj_faces[order[curr_idx]])];
490 const size_t next_patch_idx =
491 P[edge_index_to_face_index(adj_faces[order[next_idx]])];
492 const bool curr_cons = signed_adj_faces[order[curr_idx]] > 0;
493 const bool next_cons = signed_adj_faces[order[next_idx]] > 0;
494 const size_t curr_cell_idx = curr_patch_idx*2 + (curr_cons?0:1);
495 const size_t next_cell_idx = next_patch_idx*2 + (next_cons?1:0);
496 equivalent_cells[curr_cell_idx].insert(next_cell_idx);
497 equivalent_cells[next_cell_idx].insert(curr_cell_idx);
498 }
499 }
500 }
501 }
502
503 size_t count=0;
504 cells.resize(num_patches, 2);
505 cells.setConstant(INVALID);
506 const auto extract_equivalent_cells = [&](size_t i) {
507 if (cells(i/2, i%2) != INVALID) return;
508 std::queue<size_t> Q;
509 Q.push(i);
510 cells(i/2, i%2) = count;
511 while (!Q.empty()) {
512 const size_t index = Q.front();
513 Q.pop();
514 for (const auto j : equivalent_cells[index]) {
515 if (cells(j/2, j%2) == INVALID) {
516 cells(j/2, j%2) = count;
517 Q.push(j);
518 }
519 }
520 }
521 count++;
522 };
523 for (size_t i=0; i<num_patches; i++) {
524 extract_equivalent_cells(i*2);
525 extract_equivalent_cells(i*2+1);
526 }
527
528 assert((cells.array() != INVALID).all());
529 return count;
530 }
531
532
533 #ifdef IGL_STATIC_LIBRARY
534 // Explicit template instantiation
535 // generated by autoexplicit.sh
536 template unsigned long igl::copyleft::cgal::extract_cells<Eigen::Matrix<CGAL::Lazy_exact_nt<CGAL::Gmpq>, -1, -1, 1, -1, -1>, Eigen::Matrix<int, -1, 3, 1, -1, 3>, Eigen::Matrix<int, -1, 1, 0, -1, 1>, Eigen::Matrix<int, -1, -1, 0, -1, -1>, Eigen::Matrix<int, -1, -1, 0, -1, -1>, unsigned long, Eigen::Matrix<int, -1, 1, 0, -1, 1>, Eigen::Matrix<int, -1, -1, 0, -1, -1> >(Eigen::PlainObjectBase<Eigen::Matrix<CGAL::Lazy_exact_nt<CGAL::Gmpq>, -1, -1, 1, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 3, 1, -1, 3> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, std::vector<std::vector<unsigned long, std::allocator<unsigned long> >, std::allocator<std::vector<unsigned long, std::allocator<unsigned long> > > > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> >&);
537 // generated by autoexplicit.sh
538 template unsigned long igl::copyleft::cgal::extract_cells<Eigen::Matrix<CGAL::Lazy_exact_nt<CGAL::Gmpq>, -1, -1, 1, -1, -1>, Eigen::Matrix<int, -1, -1, 0, -1, -1>, Eigen::Matrix<int, -1, 1, 0, -1, 1>, Eigen::Matrix<int, -1, -1, 0, -1, -1>, Eigen::Matrix<int, -1, -1, 0, -1, -1>, unsigned long, Eigen::Matrix<int, -1, 1, 0, -1, 1>, Eigen::Matrix<int, -1, -1, 0, -1, -1> >(Eigen::PlainObjectBase<Eigen::Matrix<CGAL::Lazy_exact_nt<CGAL::Gmpq>, -1, -1, 1, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, std::vector<std::vector<unsigned long, std::allocator<unsigned long> >, std::allocator<std::vector<unsigned long, std::allocator<unsigned long> > > > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> >&);
539 #include <CGAL/Exact_predicates_exact_constructions_kernel.h>
540 template unsigned long igl::copyleft::cgal::extract_cells<Eigen::Matrix<CGAL::Lazy_exact_nt<CGAL::Gmpq>, -1, -1, 0, -1, -1>, Eigen::Matrix<int, -1, -1, 0, -1, -1>, Eigen::Matrix<int, -1, 1, 0, -1, 1>, Eigen::Matrix<int, -1, -1, 0, -1, -1>, Eigen::Matrix<int, -1, -1, 0, -1, -1>, unsigned long, Eigen::Matrix<int, -1, 1, 0, -1, 1>, Eigen::Matrix<int, -1, -1, 0, -1, -1> >(Eigen::PlainObjectBase<Eigen::Matrix<CGAL::Lazy_exact_nt<CGAL::Gmpq>, -1, -1, 0, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, std::vector<std::vector<unsigned long, std::allocator<unsigned long> >, std::allocator<std::vector<unsigned long, std::allocator<unsigned long> > > > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, 1, 0, -1, 1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> >&);
541 template unsigned long igl::copyleft::cgal::extract_cells<Eigen::Matrix<CGAL::Lazy_exact_nt<CGAL::Gmpq>, -1, -1, 0, -1, -1>, Eigen::Matrix<int, -1, -1, 0, -1, -1>, Eigen::Matrix<int, -1, -1, 0, -1, -1> >(Eigen::PlainObjectBase<Eigen::Matrix<CGAL::Lazy_exact_nt<CGAL::Gmpq>, -1, -1, 0, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> > const&, Eigen::PlainObjectBase<Eigen::Matrix<int, -1, -1, 0, -1, -1> >&);
542 #ifdef WIN32
543 template unsigned __int64 igl::copyleft::cgal::extract_cells<class Eigen::Matrix<class CGAL::Lazy_exact_nt<class CGAL::Gmpq>, -1, -1, 0, -1, -1>, class Eigen::Matrix<int, -1, -1, 0, -1, -1>, class Eigen::Matrix<int, -1, 1, 0, -1, 1>, class Eigen::Matrix<int, -1, -1, 0, -1, -1>, class Eigen::Matrix<int, -1, -1, 0, -1, -1>, unsigned __int64, class Eigen::Matrix<int, -1, 1, 0, -1, 1>, class Eigen::Matrix<int, -1, -1, 0, -1, -1>>(class Eigen::PlainObjectBase<class Eigen::Matrix<class CGAL::Lazy_exact_nt<class CGAL::Gmpq>, -1, -1, 0, -1, -1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, -1, 0, -1, -1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, 1, 0, -1, 1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, -1, 0, -1, -1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, -1, 0, -1, -1>> const &, class std::vector<class std::vector<unsigned __int64, class std::allocator<unsigned __int64>>, class std::allocator<class std::vector<unsigned __int64, class std::allocator<unsigned __int64>>>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, 1, 0, -1, 1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, -1, 0, -1, -1>> &);
544 template unsigned __int64 igl::copyleft::cgal::extract_cells<class Eigen::Matrix<class CGAL::Lazy_exact_nt<class CGAL::Gmpq>, -1, -1, 1, -1, -1>, class Eigen::Matrix<int, -1, -1, 0, -1, -1>, class Eigen::Matrix<int, -1, 1, 0, -1, 1>, class Eigen::Matrix<int, -1, -1, 0, -1, -1>, class Eigen::Matrix<int, -1, -1, 0, -1, -1>, unsigned __int64, class Eigen::Matrix<int, -1, 1, 0, -1, 1>, class Eigen::Matrix<int, -1, -1, 0, -1, -1>>(class Eigen::PlainObjectBase<class Eigen::Matrix<class CGAL::Lazy_exact_nt<class CGAL::Gmpq>, -1, -1, 1, -1, -1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, -1, 0, -1, -1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, 1, 0, -1, 1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, -1, 0, -1, -1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, -1, 0, -1, -1>> const &, class std::vector<class std::vector<unsigned __int64, class std::allocator<unsigned __int64>>, class std::allocator<class std::vector<unsigned __int64, class std::allocator<unsigned __int64>>>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, 1, 0, -1, 1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, -1, 0, -1, -1>> &);
545 template unsigned __int64 igl::copyleft::cgal::extract_cells<class Eigen::Matrix<class CGAL::Lazy_exact_nt<class CGAL::Gmpq>, -1, -1, 1, -1, -1>, class Eigen::Matrix<int, -1, 3, 1, -1, 3>, class Eigen::Matrix<int, -1, 1, 0, -1, 1>, class Eigen::Matrix<int, -1, -1, 0, -1, -1>, class Eigen::Matrix<int, -1, -1, 0, -1, -1>, unsigned __int64, class Eigen::Matrix<int, -1, 1, 0, -1, 1>, class Eigen::Matrix<int, -1, -1, 0, -1, -1>>(class Eigen::PlainObjectBase<class Eigen::Matrix<class CGAL::Lazy_exact_nt<class CGAL::Gmpq>, -1, -1, 1, -1, -1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, 3, 1, -1, 3>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, 1, 0, -1, 1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, -1, 0, -1, -1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, -1, 0, -1, -1>> const &, class std::vector<class std::vector<unsigned __int64, class std::allocator<unsigned __int64>>, class std::allocator<class std::vector<unsigned __int64, class std::allocator<unsigned __int64>>>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, 1, 0, -1, 1>> const &, class Eigen::PlainObjectBase<class Eigen::Matrix<int, -1, -1, 0, -1, -1>> &);
546 #endif
547 #endif
548