Added back code which was commented out for debug reasons
[blender.git] / extern / carve / carve-capi.cc
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2014 Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Blender Foundation,
22  *                 Sergey Sharybin
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 #include "carve-capi.h"
28 #include "carve-util.h"
29
30 #include <carve/interpolator.hpp>
31 #include <carve/rescale.hpp>
32 #include <carve/csg_triangulator.hpp>
33 #include <carve/mesh_simplify.hpp>
34
35 using carve::mesh::MeshSet;
36
37 typedef std::pair<int, int> OrigIndex;
38 typedef std::pair<MeshSet<3>::vertex_t *, MeshSet<3>::vertex_t *> VertexPair;
39 typedef carve::interpolate::VertexAttr<OrigIndex> OrigVertMapping;
40 typedef carve::interpolate::FaceAttr<OrigIndex> OrigFaceMapping;
41 typedef carve::interpolate::FaceEdgeAttr<OrigIndex> OrigFaceEdgeMapping;
42 typedef carve::interpolate::SimpleFaceEdgeAttr<bool> FaceEdgeTriangulatedFlag;
43
44 typedef struct CarveMeshDescr {
45         // Stores mesh data itself.
46         MeshSet<3> *poly;
47
48         // N-th element of the vector indicates index of an original mesh loop.
49         std::unordered_map<std::pair<int, int>, int> orig_loop_index_map;
50
51         // N-th element of the vector indicates index of an original mesh poly.
52         std::vector<int> orig_poly_index_map;
53
54         // The folloving mapping is only filled in for output mesh.
55
56         // Mapping from the face verts back to original vert index.
57         OrigVertMapping orig_vert_mapping;
58
59         // Mapping from the face edges back to (original edge index, original loop index).
60         OrigFaceEdgeMapping orig_face_edge_mapping;
61
62         FaceEdgeTriangulatedFlag face_edge_triangulated_flag;
63
64         // Mapping from the faces back to original poly index.
65         OrigFaceMapping orig_face_mapping;
66 } CarveMeshDescr;
67
68 namespace {
69
70 template <typename T1, typename T2>
71 void edgeIndexMap_put(std::unordered_map<std::pair<T1, T1>, T2> *edge_map,
72                       const T1 &v1,
73                       const T1 &v2,
74                       const T2 &index)
75 {
76         if (v1 < v2) {
77                 (*edge_map)[std::make_pair(v1, v2)] = index;
78         }
79         else {
80                 (*edge_map)[std::make_pair(v2, v1)] = index;
81         }
82 }
83
84 template <typename T1, typename T2>
85 const T2 &edgeIndexMap_get(const std::unordered_map<std::pair<T1, T1>, T2> &edge_map,
86                            const T1 &v1,
87                            const T1 &v2)
88 {
89         typedef std::unordered_map<std::pair<T1, T1>, T2> Map;
90         typename Map::const_iterator found;
91
92         if (v1 < v2) {
93                 found = edge_map.find(std::make_pair(v1, v2));
94         }
95         else {
96                 found = edge_map.find(std::make_pair(v2, v1));
97         }
98
99         assert(found != edge_map.end());
100         return found->second;
101 }
102
103 template <typename T1, typename T2>
104 bool edgeIndexMap_get_if_exists(const std::unordered_map<std::pair<T1, T1>, T2> &edge_map,
105                                 const T1 &v1,
106                                 const T1 &v2,
107                                 T2 *out)
108 {
109         typedef std::unordered_map<std::pair<T1, T1>, T2> Map;
110         typename Map::const_iterator found;
111
112         if (v1 < v2) {
113                 found = edge_map.find(std::make_pair(v1, v2));
114         }
115         else {
116                 found = edge_map.find(std::make_pair(v2, v1));
117         }
118
119         if (found == edge_map.end()) {
120                 return false;
121         }
122         *out = found->second;
123         return true;
124 }
125
126 template <typename T1, typename T2>
127 bool edgeIndexMap_exists(const std::unordered_map<std::pair<T1, T1>, T2> &edge_map,
128                          const T1 &v1,
129                          const T1 &v2)
130 {
131         typedef std::unordered_map<std::pair<T1, T1>, T2> Map;
132         typename Map::const_iterator found;
133
134         if (v1 < v2) {
135                 found = edge_map.find(std::make_pair(v1, v2));
136         }
137         else {
138                 found = edge_map.find(std::make_pair(v2, v1));
139         }
140
141         return found != edge_map.end();
142 }
143
144 template <typename T>
145 inline int indexOf(const T *element, const std::vector<T> &vector_from)
146 {
147         return element - &vector_from.at(0);
148 }
149
150 void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
151                                   int which_mesh,
152                                   std::unordered_map<std::pair<int, int>, int> &orig_loop_index_map,
153                                   const std::vector<int> &orig_poly_index_map,
154                                   OrigVertMapping *orig_vert_mapping,
155                                   OrigFaceEdgeMapping *orig_face_edge_mapping,
156                                   FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
157                                   OrigFaceMapping *orig_face_attr)
158 {
159         MeshSet<3> *poly = mesh->poly;
160
161         std::vector<MeshSet<3>::vertex_t>::iterator vertex_iter =
162                 poly->vertex_storage.begin();
163         for (int i = 0;
164              vertex_iter != poly->vertex_storage.end();
165              ++i, ++vertex_iter)
166         {
167                 MeshSet<3>::vertex_t *vertex = &(*vertex_iter);
168                 orig_vert_mapping->setAttribute(vertex,
169                                                 std::make_pair(which_mesh, i));
170         }
171
172         MeshSet<3>::face_iter face_iter = poly->faceBegin();
173         for (int i = 0, loop_map_index = 0;
174              face_iter != poly->faceEnd();
175              ++face_iter, ++i)
176         {
177                 const MeshSet<3>::face_t *face = *face_iter;
178
179                 // Mapping from carve face back to original poly index.
180                 int orig_poly_index = orig_poly_index_map[i];
181                 orig_face_attr->setAttribute(face, std::make_pair(which_mesh, orig_poly_index));
182
183                 for (MeshSet<3>::face_t::const_edge_iter_t edge_iter = face->begin();
184                      edge_iter != face->end();
185                      ++edge_iter, ++loop_map_index)
186                 {
187                         int v1 = indexOf(edge_iter->v1(), poly->vertex_storage);
188                         int v2 = indexOf(edge_iter->v2(), poly->vertex_storage);
189
190                         int orig_loop_index;
191                         if (!edgeIndexMap_get_if_exists(orig_loop_index_map,
192                                                         v1, v2,
193                                                         &orig_loop_index))
194                         {
195                                 orig_loop_index = -1;
196                         }
197
198                         if (orig_loop_index != -1) {
199                                 // Mapping from carve face edge back to original loop index.
200                                 orig_face_edge_mapping->setAttribute(face,
201                                                                      edge_iter.idx(),
202                                                                      std::make_pair(which_mesh,
203                                                                                     orig_loop_index));
204                         }
205                         else {
206                                 face_edge_triangulated_flag->setAttribute(face,
207                                                                           edge_iter.idx(),
208                                                                           true);
209                         }
210                 }
211         }
212 }
213
214 void initOrigIndexMapping(CarveMeshDescr *left_mesh,
215                           CarveMeshDescr *right_mesh,
216                           OrigVertMapping *orig_vert_mapping,
217                           OrigFaceEdgeMapping *orig_face_edge_mapping,
218                           FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
219                           OrigFaceMapping *orig_face_mapping)
220 {
221         initOrigIndexMeshFaceMapping(left_mesh,
222                                      CARVE_MESH_LEFT,
223                                      left_mesh->orig_loop_index_map,
224                                      left_mesh->orig_poly_index_map,
225                                      orig_vert_mapping,
226                                      orig_face_edge_mapping,
227                                      face_edge_triangulated_flag,
228                                      orig_face_mapping);
229
230         initOrigIndexMeshFaceMapping(right_mesh,
231                                      CARVE_MESH_RIGHT,
232                                      right_mesh->orig_loop_index_map,
233                                      right_mesh->orig_poly_index_map,
234                                      orig_vert_mapping,
235                                      orig_face_edge_mapping,
236                                      face_edge_triangulated_flag,
237                                      orig_face_mapping);
238 }
239
240 void origEdgeMappingForFace(MeshSet<3>::face_t *face,
241                             OrigFaceEdgeMapping *orig_face_edge_mapping,
242                             std::unordered_map<VertexPair, OrigIndex> *edge_origindex_map)
243 {
244         OrigIndex origindex_none = std::make_pair((int)CARVE_MESH_NONE, -1);
245
246         MeshSet<3>::edge_t *edge = face->edge;
247         for (int i = 0;
248              i < face->nEdges();
249              ++i, edge = edge->next)
250         {
251                 MeshSet<3>::vertex_t *v1 = edge->v1();
252                 MeshSet<3>::vertex_t *v2 = edge->v2();
253
254                 OrigIndex orig_edge_index =
255                         orig_face_edge_mapping->getAttribute(edge->face, i, origindex_none);
256
257                 edgeIndexMap_put(edge_origindex_map, v1, v2, orig_edge_index);
258         }
259 }
260
261 void dissolveTriangulatedEdges(MeshSet<3>::mesh_t *mesh,
262                                const std::set< std::pair<int, int> > &open_edges,
263                                FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
264                                OrigFaceEdgeMapping *orig_face_edge_mapping)
265 {
266         typedef std::unordered_set<MeshSet<3>::edge_t *> edge_set_t;
267         typedef std::unordered_set<MeshSet<3>::face_t *> face_set_t;
268         edge_set_t triangulated_face_edges;
269
270         for (int face_index = 0; face_index < mesh->faces.size(); ++face_index) {
271                 MeshSet<3>::face_t *face = mesh->faces[face_index];
272                 MeshSet<3>::edge_t *edge = face->edge;
273                 for (int edge_index = 0;
274                      edge_index < face->nEdges();
275                      ++edge_index, edge = edge->next)
276                 {
277                         if (edge->rev) {
278                                 const bool is_triangulated_edge =
279                                         face_edge_triangulated_flag->getAttribute(face,
280                                                                                   edge_index,
281                                                                                   false);
282                                 if (is_triangulated_edge) {
283                                         MeshSet<3>::edge_t *e1 = std::min(edge, edge->rev);
284                                         int v1 = indexOf(e1->v1(), mesh->meshset->vertex_storage),
285                                             v2 = indexOf(e1->v2(), mesh->meshset->vertex_storage);
286
287                                         bool is_open = false;
288                                         if (v1 < v2) {
289                                                 is_open = open_edges.find(std::make_pair(v1, v2)) != open_edges.end();
290                                         }
291                                         else {
292                                                 is_open = open_edges.find(std::make_pair(v2, v1)) != open_edges.end();
293                                         }
294
295                                         if (is_open == false) {
296                                                 triangulated_face_edges.insert(e1);
297                                         }
298                                 }
299                         }
300                 }
301         }
302
303         if (triangulated_face_edges.size()) {
304                 face_set_t triangulated_faces;
305                 std::unordered_map<VertexPair, OrigIndex> edge_origindex_map;
306
307                 for (edge_set_t::iterator it = triangulated_face_edges.begin();
308                      it != triangulated_face_edges.end();
309                      ++it)
310                 {
311                         MeshSet<3>::edge_t *edge = *it;
312
313                         origEdgeMappingForFace(edge->face,
314                                                orig_face_edge_mapping,
315                                                &edge_origindex_map);
316                         triangulated_faces.insert(edge->face);
317
318                         origEdgeMappingForFace(edge->rev->face,
319                                                orig_face_edge_mapping,
320                                                &edge_origindex_map);
321                         triangulated_faces.insert(edge->rev->face);
322                 }
323
324                 carve::mesh::MeshSimplifier simplifier;
325                 simplifier.dissolveMeshEdges(mesh, triangulated_face_edges);
326
327                 for (int face_index = 0; face_index < mesh->faces.size(); face_index++) {
328                         MeshSet<3>::face_t *face = mesh->faces[face_index];
329
330                         if (triangulated_faces.find(face) != triangulated_faces.end()) {
331                                 MeshSet<3>::edge_t *edge = face->edge;
332                                 for (int edge_index = 0;
333                                      edge_index < face->nEdges();
334                                      ++edge_index, edge = edge->next)
335                                 {
336                                         MeshSet<3>::vertex_t *v1 = edge->v1();
337                                         MeshSet<3>::vertex_t *v2 = edge->v2();
338
339                                         OrigIndex orig_edge_index =
340                                                 edgeIndexMap_get(edge_origindex_map,
341                                                                  v1,
342                                                                  v2);
343
344                                         orig_face_edge_mapping->setAttribute(face, edge_index, orig_edge_index);
345                                 }
346                         }
347                 }
348         }
349 }
350
351 void dissolveTriangulatedEdges(CarveMeshDescr *mesh_descr)
352 {
353         MeshSet<3> *poly = mesh_descr->poly;
354         FaceEdgeTriangulatedFlag *face_edge_triangulated_flag =
355                 &mesh_descr->face_edge_triangulated_flag;
356
357         std::set< std::pair<int, int> > open_edges;
358         for (int mesh_index = 0;
359              mesh_index < poly->meshes.size();
360              ++mesh_index)
361         {
362                 const MeshSet<3>::mesh_t *mesh = poly->meshes[mesh_index];
363                 for (int edge_index = 0;
364                      edge_index < mesh->open_edges.size();
365                      ++edge_index)
366                 {
367                         const MeshSet<3>::edge_t *edge = mesh->open_edges[edge_index];
368                         int v1 = indexOf(edge->v1(), poly->vertex_storage),
369                             v2 = indexOf(edge->v2(), poly->vertex_storage);
370                         if (v1 < v2) {
371                                 open_edges.insert(std::make_pair(v1, v2));
372                         }
373                         else {
374                                 open_edges.insert(std::make_pair(v2, v1));
375                         }
376                 }
377         }
378
379         for (int mesh_index = 0; mesh_index < poly->meshes.size(); ++mesh_index) {
380                 MeshSet<3>::mesh_t *mesh = poly->meshes[mesh_index];
381                 dissolveTriangulatedEdges(mesh,
382                                           open_edges,
383                                           face_edge_triangulated_flag,
384                                           &mesh_descr->orig_face_edge_mapping);
385         }
386 }
387
388 void clipEar(MeshSet<3>::edge_t *ear)
389 {
390         MeshSet<3>::edge_t *p_edge = ear->prev;
391         MeshSet<3>::edge_t *n_edge = ear->next;
392
393         p_edge->next = n_edge;
394         n_edge->prev = p_edge;
395
396         if (ear->face->edge == ear) {
397                 ear->face->edge = n_edge;
398         }
399         ear->face->n_edges--;
400
401         delete ear;
402 }
403
404 MeshSet<3>::edge_t *findDegenerateEar(MeshSet<3>::face_t *face)
405 {
406         for (MeshSet<3>::face_t::edge_iter_t edge_iter = face->begin();
407              edge_iter != face->end();
408              ++edge_iter)
409         {
410                 MeshSet<3>::edge_t &edge = *edge_iter;
411                 if (edge.vert == edge.next->next->vert) {
412                         return edge.next->next;
413                 }
414         }
415         return NULL;
416 }
417
418 class EarClipper : public carve::csg::CSG::Hook {
419 public:
420         virtual ~EarClipper() {
421         }
422
423         virtual void processOutputFace(std::vector<MeshSet<3>::face_t *> &faces,
424                                        const MeshSet<3>::face_t *orig,
425                                        bool flipped) {
426                 for (size_t face_index = 0; face_index < faces.size(); ++face_index) {
427                         carve::mesh::MeshSet<3>::face_t *face = faces[face_index];
428
429                         // There's no ears in quads and tris.
430                         if (face->nVertices() <= 4) {
431                                 continue;
432                         }
433
434                         MeshSet<3>::edge_t *ear;
435                         while ((ear = findDegenerateEar(face)) != NULL) {
436                                 clipEar(ear);
437                         }
438
439                 }
440         }
441 };
442
443 class HoleResolver : public carve::csg::CarveHoleResolver {
444
445         void removeDuplicatedFaces(std::vector<MeshSet<3>::face_t *> &faces) {
446                 std::vector<MeshSet<3>::face_t *> out_faces;
447                 std::vector<MeshSet<3>::face_t *> duplicated_faces;
448
449                 for (size_t face_index = 0; face_index < faces.size(); ++face_index) {
450                         carve::mesh::MeshSet<3>::face_t *face = faces[face_index];
451                         face->canonicalize();
452                 }
453
454                 for (size_t i = 0; i < faces.size(); ++i) {
455                         carve::mesh::MeshSet<3>::face_t *face = faces[i];
456
457                         bool found = false;
458                         for (size_t j = i + 1; j < faces.size() && found == false; ++j) {
459                                 MeshSet<3>::face_t *cur_face = faces[j];
460                                 if (cur_face->nEdges() == face->nEdges() &&
461                                     cur_face->edge->vert == face->edge->vert)
462                                 {
463
464                                         MeshSet<3>::edge_t *cur_edge = cur_face->edge,
465                                                            *forward_edge = face->edge,
466                                                            *backward_edge = face->edge;
467                                         bool forward_matches = true, backward_matches = true;
468
469                                         for (int a = 0; a < cur_face->nEdges(); ++a) {
470                                                 if (forward_edge->vert != cur_edge->vert) {
471                                                         forward_matches = false;
472                                                         if (backward_matches == false) {
473                                                                 break;
474                                                         }
475                                                 }
476
477                                                 if (backward_edge->vert != cur_edge->vert) {
478                                                         backward_matches = false;
479                                                         if (forward_matches == false) {
480                                                                 break;
481                                                         }
482                                                 }
483
484                                                 cur_edge = cur_edge->next;
485                                                 forward_edge = forward_edge->next;
486                                                 backward_edge = backward_edge->prev;
487                                         }
488
489                                         if (forward_matches || backward_matches) {
490                                                 found = true;
491                                                 break;
492                                         }
493                                 }
494                         }
495
496                         if (found) {
497                                 duplicated_faces.push_back(face);
498                         }
499                         else {
500                                 out_faces.push_back(face);
501                         }
502                 }
503
504                 for (int i = 0; i < duplicated_faces.size(); ++i) {
505                         delete duplicated_faces[i];
506                 }
507
508                 std::swap(faces, out_faces);
509         }
510
511 public:
512         virtual ~HoleResolver() {
513         }
514
515         virtual void processOutputFace(std::vector<MeshSet<3>::face_t *> &faces,
516                                        const MeshSet<3>::face_t *orig,
517                                        bool flipped) {
518                 carve::csg::CarveHoleResolver::processOutputFace(faces, orig, flipped);
519                 if (faces.size() > 1) {
520                         removeDuplicatedFaces(faces);
521                 }
522         }
523 };
524
525 }  // namespace
526
527 CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
528                               CarveMeshImporter *mesh_importer)
529 {
530 #define MAX_STATIC_VERTS 64
531
532         CarveMeshDescr *mesh_descr = new CarveMeshDescr;
533
534         // Import verices from external mesh to Carve.
535         int num_verts = mesh_importer->getNumVerts(import_data);
536         std::vector<carve::geom3d::Vector> vertices;
537         vertices.reserve(num_verts);
538         for (int i = 0; i < num_verts; i++) {
539                 float position[3];
540                 mesh_importer->getVertCoord(import_data, i, position);
541                 vertices.push_back(carve::geom::VECTOR(position[0],
542                                                        position[1],
543                                                        position[2]));
544         }
545
546         // Import polys from external mesh to Carve.
547         int verts_of_poly_static[MAX_STATIC_VERTS];
548         int *verts_of_poly_dynamic = NULL;
549         int verts_of_poly_dynamic_size = 0;
550
551         int num_loops = mesh_importer->getNumLoops(import_data);
552         int num_polys = mesh_importer->getNumPolys(import_data);
553         int loop_index = 0;
554         int num_tessellated_polys = 0;
555         std::vector<int> face_indices;
556         face_indices.reserve(num_loops);
557         mesh_descr->orig_poly_index_map.reserve(num_polys);
558         TrianglesStorage triangles_storage;
559         for (int i = 0; i < num_polys; i++) {
560                 int verts_per_poly =
561                         mesh_importer->getNumPolyVerts(import_data, i);
562                 int *verts_of_poly;
563
564                 if (verts_per_poly <= MAX_STATIC_VERTS) {
565                         verts_of_poly = verts_of_poly_static;
566                 }
567                 else {
568                         if (verts_of_poly_dynamic_size < verts_per_poly) {
569                                 if (verts_of_poly_dynamic != NULL) {
570                                         delete [] verts_of_poly_dynamic;
571                                 }
572                                 verts_of_poly_dynamic = new int[verts_per_poly];
573                                 verts_of_poly_dynamic_size = verts_per_poly;
574                         }
575                         verts_of_poly = verts_of_poly_dynamic;
576                 }
577
578                 mesh_importer->getPolyVerts(import_data, i, verts_of_poly);
579
580                 carve::math::Matrix3 axis_matrix;
581                 if (!carve_checkPolyPlanarAndGetNormal(vertices,
582                                                        verts_per_poly,
583                                                        verts_of_poly,
584                                                        &axis_matrix)) {
585                         int num_triangles = carve_triangulatePoly(import_data,
586                                                                   mesh_importer,
587                                                                   vertices,
588                                                                   verts_per_poly,
589                                                                   verts_of_poly,
590                                                                   axis_matrix,
591                                                                   &face_indices,
592                                                                   &triangles_storage);
593
594                         for (int j = 0; j < num_triangles; ++j) {
595                                 mesh_descr->orig_poly_index_map.push_back(i);
596                         }
597
598                         num_tessellated_polys += num_triangles;
599                 }
600                 else {
601                         face_indices.push_back(verts_per_poly);
602                         for (int j = 0; j < verts_per_poly; ++j) {
603                                 face_indices.push_back(verts_of_poly[j]);
604                         }
605                         mesh_descr->orig_poly_index_map.push_back(i);
606                         num_tessellated_polys++;
607                 }
608
609                 for (int j = 0; j < verts_per_poly; ++j) {
610                         int v1 = verts_of_poly[j];
611                         int v2 = verts_of_poly[(j + 1) % verts_per_poly];
612                         edgeIndexMap_put(&mesh_descr->orig_loop_index_map, v1, v2, loop_index++);
613                 }
614         }
615
616         if (verts_of_poly_dynamic != NULL) {
617                 delete [] verts_of_poly_dynamic;
618         }
619
620         mesh_descr->poly = new MeshSet<3> (vertices,
621                                            num_tessellated_polys,
622                                            face_indices);
623
624         return mesh_descr;
625
626 #undef MAX_STATIC_VERTS
627 }
628
629 void carve_deleteMesh(CarveMeshDescr *mesh_descr)
630 {
631         delete mesh_descr->poly;
632         delete mesh_descr;
633 }
634
635 bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
636                                    CarveMeshDescr *right_mesh,
637                                    int operation,
638                                    CarveMeshDescr **output_mesh)
639 {
640         *output_mesh = NULL;
641
642         carve::csg::CSG::OP op;
643         switch (operation) {
644 #define OP_CONVERT(the_op) \
645                 case CARVE_OP_ ## the_op: \
646                         op = carve::csg::CSG::the_op; \
647                         break;
648                 OP_CONVERT(UNION)
649                 OP_CONVERT(INTERSECTION)
650                 OP_CONVERT(A_MINUS_B)
651                 default:
652                         return false;
653 #undef OP_CONVERT
654         }
655
656         CarveMeshDescr *output_descr = new CarveMeshDescr;
657         output_descr->poly = NULL;
658         try {
659                 MeshSet<3> *left = left_mesh->poly, *right = right_mesh->poly;
660                 carve::geom3d::Vector min, max;
661
662                 // TODO(sergey): Make importer/exporter to care about re-scale
663                 // to save extra mesh iteration here.
664                 carve_getRescaleMinMax(left, right, &min, &max);
665
666                 carve::rescale::rescale scaler(min.x, min.y, min.z, max.x, max.y, max.z);
667                 carve::rescale::fwd fwd_r(scaler);
668                 carve::rescale::rev rev_r(scaler);
669
670                 left->transform(fwd_r);
671                 right->transform(fwd_r);
672
673                 // Initialize attributes for maping from boolean result mesh back to
674                 // original geometry indices.
675                 initOrigIndexMapping(left_mesh, right_mesh,
676                                      &output_descr->orig_vert_mapping,
677                                      &output_descr->orig_face_edge_mapping,
678                                      &output_descr->face_edge_triangulated_flag,
679                                      &output_descr->orig_face_mapping);
680
681                 carve::csg::CSG csg;
682
683                 csg.hooks.registerHook(new HoleResolver,
684                                        carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT);
685
686                 csg.hooks.registerHook(new EarClipper,
687                                        carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT);
688
689                 output_descr->orig_vert_mapping.installHooks(csg);
690                 output_descr->orig_face_edge_mapping.installHooks(csg);
691                 output_descr->face_edge_triangulated_flag.installHooks(csg);
692                 output_descr->orig_face_mapping.installHooks(csg);
693
694                 // Prepare operands for actual boolean operation.
695                 //
696                 // It's needed because operands might consist of several intersecting
697                 // meshes and in case of another operands intersect an edge loop of
698                 // intersecting that meshes tessellation of operation result can't be
699                 // done properly. The only way to make such situations working is to
700                 // union intersecting meshes of the same operand.
701                 carve_unionIntersections(&csg, &left, &right);
702                 left_mesh->poly = left;
703                 right_mesh->poly = right;
704
705                 if (left->meshes.size() == 0 || right->meshes.size() == 0) {
706                         // Normally shouldn't happen (zero-faces objects are handled by
707                         // modifier itself), but unioning intersecting meshes which doesn't
708                         // have consistent normals might lead to empty result which
709                         // wouldn't work here.
710
711                         return false;
712                 }
713
714                 output_descr->poly = csg.compute(left,
715                                                  right,
716                                                  op,
717                                                  NULL,
718                                                  carve::csg::CSG::CLASSIFY_EDGE);
719
720                 if (output_descr->poly) {
721                         output_descr->poly->transform(rev_r);
722
723                         dissolveTriangulatedEdges(output_descr);
724                 }
725         }
726         catch (carve::exception e) {
727                 std::cerr << "CSG failed, exception " << e.str() << std::endl;
728         }
729         catch (...) {
730                 std::cerr << "Unknown error in Carve library" << std::endl;
731         }
732
733         *output_mesh = output_descr;
734
735         return output_descr->poly != NULL;
736 }
737
738 static int exportMesh_handle_edges_list(MeshSet<3> *poly,
739                                         const std::vector<MeshSet<3>::edge_t*> &edges,
740                                         int start_edge_index,
741                                         CarveMeshExporter *mesh_exporter,
742                                         struct ExportMeshData *export_data,
743                                         std::unordered_map<VertexPair, OrigIndex> &edge_origindex_map,
744                                         std::unordered_map<VertexPair, int> *edge_map)
745 {
746         int num_exported_edges = 0;
747
748         for (int i = 0, edge_index = start_edge_index;
749              i < edges.size();
750              ++i)
751         {
752                 MeshSet<3>::edge_t *edge = edges.at(i);
753                 MeshSet<3>::vertex_t *v1 = edge->v1();
754                 MeshSet<3>::vertex_t *v2 = edge->v2();
755
756                 if (edgeIndexMap_exists(*edge_map, v1, v2)) {
757                         continue;
758                 }
759
760                 const OrigIndex &orig_edge_index = edgeIndexMap_get(edge_origindex_map,
761                                                                         v1,
762                                                                         v2);
763
764                 mesh_exporter->setEdge(export_data,
765                                        edge_index,
766                                        indexOf(v1, poly->vertex_storage),
767                                        indexOf(v2, poly->vertex_storage),
768                                        orig_edge_index.first,
769                                        orig_edge_index.second);
770
771                 edgeIndexMap_put(edge_map, v1, v2, edge_index);
772                 ++edge_index;
773                 ++num_exported_edges;
774         }
775
776         return num_exported_edges;
777 }
778
779 void carve_exportMesh(CarveMeshDescr *mesh_descr,
780                       CarveMeshExporter *mesh_exporter,
781                       struct ExportMeshData *export_data)
782 {
783         OrigIndex origindex_none = std::make_pair((int)CARVE_MESH_NONE, -1);
784         MeshSet<3> *poly = mesh_descr->poly;
785         int num_vertices = poly->vertex_storage.size();
786         int num_edges = 0, num_loops = 0, num_polys = 0;
787
788         // Get mapping from edge denoted by vertex pair to original edge index,
789         //
790         // This is needed because internally Carve interpolates data for per-face
791         // edges rather then having some global edge storage.
792         std::unordered_map<VertexPair, OrigIndex> edge_origindex_map;
793         for (MeshSet<3>::face_iter face_iter = poly->faceBegin();
794              face_iter != poly->faceEnd();
795              ++face_iter)
796         {
797                 MeshSet<3>::face_t *face = *face_iter;
798                 for (MeshSet<3>::face_t::edge_iter_t edge_iter = face->begin();
799                      edge_iter != face->end();
800                      ++edge_iter)
801                 {
802                         MeshSet<3>::edge_t &edge = *edge_iter;
803                         int edge_iter_index = edge_iter.idx();
804
805                         const OrigIndex &orig_loop_index =
806                                 mesh_descr->orig_face_edge_mapping.getAttribute(face,
807                                                                                 edge_iter_index,
808                                                                                 origindex_none);
809
810                         OrigIndex orig_edge_index;
811
812                         if (orig_loop_index.first != CARVE_MESH_NONE) {
813                                 orig_edge_index.first = orig_loop_index.first;
814                                 orig_edge_index.second =
815                                         mesh_exporter->mapLoopToEdge(export_data,
816                                                                      orig_loop_index.first,
817                                                                      orig_loop_index.second);
818                         }
819                         else {
820                                 orig_edge_index.first = CARVE_MESH_NONE;
821                                 orig_edge_index.second = -1;
822                         }
823
824                         MeshSet<3>::vertex_t *v1 = edge.v1();
825                         MeshSet<3>::vertex_t *v2 = edge.v2();
826
827                         edgeIndexMap_put(&edge_origindex_map, v1, v2, orig_edge_index);
828                 }
829         }
830
831         num_edges = edge_origindex_map.size();
832
833         // Count polys and loops from all manifolds.
834         for (MeshSet<3>::face_iter face_iter = poly->faceBegin();
835              face_iter != poly->faceEnd();
836              ++face_iter, ++num_polys)
837         {
838                 MeshSet<3>::face_t *face = *face_iter;
839                 num_loops += face->nEdges();
840         }
841
842         // Initialize arrays for geometry in exported mesh.
843         mesh_exporter->initGeomArrays(export_data,
844                                       num_vertices,
845                                       num_edges,
846                                       num_loops,
847                                       num_polys);
848
849         // Export all the vertices.
850         std::vector<MeshSet<3>::vertex_t>::iterator vertex_iter = poly->vertex_storage.begin();
851         for (int i = 0; vertex_iter != poly->vertex_storage.end(); ++i, ++vertex_iter) {
852                 MeshSet<3>::vertex_t *vertex = &(*vertex_iter);
853
854                 OrigIndex orig_vert_index =
855                         mesh_descr->orig_vert_mapping.getAttribute(vertex, origindex_none);
856
857                 float coord[3];
858                 coord[0] = vertex->v[0];
859                 coord[1] = vertex->v[1];
860                 coord[2] = vertex->v[2];
861                 mesh_exporter->setVert(export_data, i, coord,
862                                        orig_vert_index.first,
863                                        orig_vert_index.second);
864         }
865
866         // Export all the edges.
867         std::unordered_map<VertexPair, int> edge_map;
868         for (int i = 0, edge_index = 0; i < poly->meshes.size(); ++i) {
869                 carve::mesh::Mesh<3> *mesh = poly->meshes[i];
870                 // Export closed edges.
871                 edge_index += exportMesh_handle_edges_list(poly,
872                                                            mesh->closed_edges,
873                                                            edge_index,
874                                                            mesh_exporter,
875                                                            export_data,
876                                                            edge_origindex_map,
877                                                            &edge_map);
878
879                 // Export open edges.
880                 edge_index += exportMesh_handle_edges_list(poly,
881                                                            mesh->open_edges,
882                                                            edge_index,
883                                                            mesh_exporter,
884                                                            export_data,
885                                                            edge_origindex_map,
886                                                            &edge_map);
887         }
888
889         // Export all the loops and polys.
890         MeshSet<3>::face_iter face_iter = poly->faceBegin();
891         for (int loop_index = 0, poly_index = 0;
892              face_iter != poly->faceEnd();
893              ++face_iter, ++poly_index)
894         {
895                 int start_loop_index = loop_index;
896                 MeshSet<3>::face_t *face = *face_iter;
897                 const OrigIndex &orig_face_index =
898                         mesh_descr->orig_face_mapping.getAttribute(face, origindex_none);
899
900                 for (MeshSet<3>::face_t::edge_iter_t edge_iter = face->begin();
901                      edge_iter != face->end();
902                      ++edge_iter, ++loop_index)
903                 {
904                         MeshSet<3>::edge_t &edge = *edge_iter;
905                         const OrigIndex &orig_loop_index =
906                                 mesh_descr->orig_face_edge_mapping.getAttribute(face,
907                                                                                 edge_iter.idx(),
908                                                                                 origindex_none);
909
910                         mesh_exporter->setLoop(export_data,
911                                                loop_index,
912                                                indexOf(edge.vert, poly->vertex_storage),
913                                                edgeIndexMap_get(edge_map, edge.v1(), edge.v2()),
914                                                orig_loop_index.first,
915                                                orig_loop_index.second);
916                 }
917
918                 mesh_exporter->setPoly(export_data,
919                                        poly_index, start_loop_index, face->nEdges(),
920                                        orig_face_index.first, orig_face_index.second);
921         }
922 }