Preserve non-flat faces in boolean modifier
[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::FaceEdgeAttr<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::vector<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 T>
127 inline int indexOf(const T *element, const std::vector<T> &vector_from)
128 {
129         return element - &vector_from.at(0);
130 }
131
132 void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
133                                   int which_mesh,
134                                   const std::vector<int> &orig_loop_index_map,
135                                   const std::vector<int> &orig_poly_index_map,
136                                   OrigVertMapping *orig_vert_mapping,
137                                   OrigFaceEdgeMapping *orig_face_edge_mapping,
138                                   FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
139                                   OrigFaceMapping *orig_face_attr)
140 {
141         MeshSet<3> *poly = mesh->poly;
142
143         std::vector<MeshSet<3>::vertex_t>::iterator vertex_iter =
144                 poly->vertex_storage.begin();
145         for (int i = 0;
146              vertex_iter != poly->vertex_storage.end();
147              ++i, ++vertex_iter)
148         {
149                 MeshSet<3>::vertex_t *vertex = &(*vertex_iter);
150                 orig_vert_mapping->setAttribute(vertex,
151                                                 std::make_pair(which_mesh, i));
152         }
153
154         MeshSet<3>::face_iter face_iter = poly->faceBegin();
155         for (int i = 0, loop_map_index = 0;
156              face_iter != poly->faceEnd();
157              ++face_iter, ++i)
158         {
159                 const MeshSet<3>::face_t *face = *face_iter;
160
161                 // Mapping from carve face back to original poly index.
162                 int orig_poly_index = orig_poly_index_map[i];
163                 orig_face_attr->setAttribute(face, std::make_pair(which_mesh, orig_poly_index));
164
165                 for (MeshSet<3>::face_t::const_edge_iter_t edge_iter = face->begin();
166                      edge_iter != face->end();
167                      ++edge_iter, ++loop_map_index)
168                 {
169                         int orig_loop_index = orig_loop_index_map[loop_map_index];
170                         if (orig_loop_index != -1) {
171                                 // Mapping from carve face edge back to original loop index.
172                                 orig_face_edge_mapping->setAttribute(face,
173                                                                      edge_iter.idx(),
174                                                                      std::make_pair(which_mesh,
175                                                                                     orig_loop_index));
176                         }
177                         else {
178                                 face_edge_triangulated_flag->setAttribute(face, edge_iter.idx(), true);
179                         }
180                 }
181         }
182 }
183
184 void initOrigIndexMapping(CarveMeshDescr *left_mesh,
185                           CarveMeshDescr *right_mesh,
186                           OrigVertMapping *orig_vert_mapping,
187                           OrigFaceEdgeMapping *orig_face_edge_mapping,
188                           FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
189                           OrigFaceMapping *orig_face_mapping)
190 {
191         initOrigIndexMeshFaceMapping(left_mesh,
192                                      CARVE_MESH_LEFT,
193                                      left_mesh->orig_loop_index_map,
194                                      left_mesh->orig_poly_index_map,
195                                      orig_vert_mapping,
196                                      orig_face_edge_mapping,
197                                      face_edge_triangulated_flag,
198                                      orig_face_mapping);
199
200         initOrigIndexMeshFaceMapping(right_mesh,
201                                      CARVE_MESH_RIGHT,
202                                      right_mesh->orig_loop_index_map,
203                                      right_mesh->orig_poly_index_map,
204                                      orig_vert_mapping,
205                                      orig_face_edge_mapping,
206                                      face_edge_triangulated_flag,
207                                      orig_face_mapping);
208 }
209
210 void origEdgeMappingForFace(MeshSet<3>::face_t *face,
211                             OrigFaceEdgeMapping *orig_face_edge_mapping,
212                             std::unordered_map<VertexPair, OrigIndex> *edge_origindex_map)
213 {
214         OrigIndex origindex_none = std::make_pair((int)CARVE_MESH_NONE, -1);
215
216         MeshSet<3>::edge_t *edge = face->edge;
217         for (int i = 0;
218              i < face->n_edges;
219              ++i, edge = edge->next)
220         {
221                 MeshSet<3>::vertex_t *v1 = edge->vert;
222                 MeshSet<3>::vertex_t *v2 = edge->next->vert;
223
224                 OrigIndex orig_edge_index =
225                         orig_face_edge_mapping->getAttribute(edge->face, i, origindex_none);
226
227                 edgeIndexMap_put(edge_origindex_map, v1, v2, orig_edge_index);
228         }
229 }
230
231 void dissolveTriangulatedEdges(MeshSet<3>::mesh_t *mesh,
232                                OrigFaceEdgeMapping *orig_face_edge_mapping,
233                                FaceEdgeTriangulatedFlag *face_edge_triangulated_flag)
234 {
235         typedef std::unordered_set<MeshSet<3>::edge_t *> edge_set_t;
236         typedef std::unordered_set<MeshSet<3>::face_t *> face_set_t;
237         edge_set_t triangulated_face_edges;
238
239         for (int face_index = 0; face_index < mesh->faces.size(); face_index++) {
240                 MeshSet<3>::face_t *face = mesh->faces[face_index];
241                 MeshSet<3>::edge_t *edge = face->edge;
242                 for (int edge_index = 0;
243                      edge_index < face->n_edges;
244                      ++edge_index, edge = edge->next)
245                 {
246                         const bool is_triangulated_edge =
247                                 face_edge_triangulated_flag->getAttribute(face,
248                                                                           edge_index,
249                                                                           false);
250                         if (is_triangulated_edge) {
251                                 MeshSet<3>::edge_t *e1 = std::min(edge, edge->rev);
252                                 triangulated_face_edges.insert(e1);
253                         }
254                 }
255         }
256
257         if (triangulated_face_edges.size()) {
258                 face_set_t triangulated_faces;
259                 std::unordered_map<VertexPair, OrigIndex> edge_origindex_map;
260
261                 for (edge_set_t::iterator it = triangulated_face_edges.begin();
262                      it != triangulated_face_edges.end();
263                      ++it)
264                 {
265                         MeshSet<3>::edge_t *edge = *it;
266
267                         origEdgeMappingForFace(edge->face,
268                                                orig_face_edge_mapping,
269                                                &edge_origindex_map);
270                         triangulated_faces.insert(edge->face);
271
272                         origEdgeMappingForFace(edge->rev->face,
273                                                orig_face_edge_mapping,
274                                                &edge_origindex_map);
275                         triangulated_faces.insert(edge->rev->face);
276                 }
277
278                 carve::mesh::MeshSimplifier simplifier;
279                 simplifier.dissolveMeshEdges(mesh, triangulated_face_edges);
280
281                 for (int face_index = 0; face_index < mesh->faces.size(); face_index++) {
282                         MeshSet<3>::face_t *face = mesh->faces[face_index];
283
284                         if (triangulated_faces.find(face) != triangulated_faces.end()) {
285                                 MeshSet<3>::edge_t *edge = face->edge;
286                                 for (int edge_index = 0;
287                                      edge_index < face->n_edges;
288                                      ++edge_index, edge = edge->next)
289                                 {
290                                         MeshSet<3>::vertex_t *v1 = edge->vert;
291                                         MeshSet<3>::vertex_t *v2 = edge->next->vert;
292
293                                         OrigIndex orig_edge_index =
294                                                 edgeIndexMap_get(edge_origindex_map,
295                                                                  v1,
296                                                                  v2);
297
298                                         orig_face_edge_mapping->setAttribute(face, edge_index, orig_edge_index);
299                                 }
300                         }
301                 }
302         }
303 }
304
305 void dissolveTriangulatedEdges(CarveMeshDescr *mesh_descr)
306 {
307         MeshSet<3> *poly = mesh_descr->poly;
308         FaceEdgeTriangulatedFlag *face_edge_triangulated_flag =
309                 &mesh_descr->face_edge_triangulated_flag;
310
311         for (int i = 0; i < poly->meshes.size(); ++i) {
312                 MeshSet<3>::mesh_t *mesh = poly->meshes[i];
313                 dissolveTriangulatedEdges(mesh,
314                                           &mesh_descr->orig_face_edge_mapping,
315                                           face_edge_triangulated_flag);
316         }
317 }
318
319 }  // namespace
320
321 CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
322                               CarveMeshImporter *mesh_importer)
323 {
324 #define MAX_STATIC_VERTS 64
325
326         CarveMeshDescr *mesh_descr = new CarveMeshDescr;
327
328         // Import verices from external mesh to Carve.
329         int num_verts = mesh_importer->getNumVerts(import_data);
330         std::vector<carve::geom3d::Vector> vertices;
331         vertices.reserve(num_verts);
332         for (int i = 0; i < num_verts; i++) {
333                 float position[3];
334                 mesh_importer->getVertCoord(import_data, i, position);
335                 vertices.push_back(carve::geom::VECTOR(position[0],
336                                                        position[1],
337                                                        position[2]));
338         }
339
340         // Import polys from external mesh to Carve.
341         int verts_of_poly_static[MAX_STATIC_VERTS];
342         int *verts_of_poly_dynamic = NULL;
343         int verts_of_poly_dynamic_size = 0;
344
345         int num_loops = mesh_importer->getNumLoops(import_data);
346         int num_polys = mesh_importer->getNumPolys(import_data);
347         int loop_index = 0;
348         int num_tessellated_polys = 0;
349         std::vector<int> face_indices;
350         face_indices.reserve(num_loops);
351         mesh_descr->orig_loop_index_map.reserve(num_polys);
352         mesh_descr->orig_poly_index_map.reserve(num_polys);
353         for (int i = 0; i < num_polys; i++) {
354                 int verts_per_poly =
355                         mesh_importer->getNumPolyVerts(import_data, i);
356                 int *verts_of_poly;
357
358                 if (verts_per_poly <= MAX_STATIC_VERTS) {
359                         verts_of_poly = verts_of_poly_static;
360                 }
361                 else {
362                         if (verts_of_poly_dynamic_size < verts_per_poly) {
363                                 if (verts_of_poly_dynamic != NULL) {
364                                         delete [] verts_of_poly_dynamic;
365                                 }
366                                 verts_of_poly_dynamic = new int[verts_per_poly];
367                                 verts_of_poly_dynamic_size = verts_per_poly;
368                         }
369                         verts_of_poly = verts_of_poly_dynamic;
370                 }
371
372                 mesh_importer->getPolyVerts(import_data, i, verts_of_poly);
373
374                 carve::math::Matrix3 axis_matrix;
375                 if (!carve_checkPolyPlanarAndGetNormal(vertices,
376                                                        verts_per_poly,
377                                                        verts_of_poly,
378                                                        &axis_matrix)) {
379                         int num_triangles;
380
381                         num_triangles = carve_triangulatePoly(import_data,
382                                                               mesh_importer,
383                                                               i,
384                                                               loop_index,
385                                                               vertices,
386                                                               verts_per_poly,
387                                                               verts_of_poly,
388                                                               axis_matrix,
389                                                               &face_indices,
390                                                               &mesh_descr->orig_loop_index_map,
391                                                               &mesh_descr->orig_poly_index_map);
392
393                         num_tessellated_polys += num_triangles;
394                         loop_index += verts_per_poly;
395                 }
396                 else {
397                         face_indices.push_back(verts_per_poly);
398                         for (int j = 0; j < verts_per_poly; ++j) {
399                                 mesh_descr->orig_loop_index_map.push_back(loop_index++);
400                                 face_indices.push_back(verts_of_poly[j]);
401                         }
402                         mesh_descr->orig_poly_index_map.push_back(i);
403                         num_tessellated_polys++;
404                 }
405         }
406
407         if (verts_of_poly_dynamic != NULL) {
408                 delete [] verts_of_poly_dynamic;
409         }
410
411         mesh_descr->poly = new MeshSet<3> (vertices,
412                                            num_tessellated_polys,
413                                            face_indices);
414
415         return mesh_descr;
416
417 #undef MAX_STATIC_VERTS
418 }
419
420 void carve_deleteMesh(CarveMeshDescr *mesh_descr)
421 {
422         delete mesh_descr->poly;
423         delete mesh_descr;
424 }
425
426 bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
427                                    CarveMeshDescr *right_mesh,
428                                    int operation,
429                                    CarveMeshDescr **output_mesh)
430 {
431         *output_mesh = NULL;
432
433         carve::csg::CSG::OP op;
434         switch (operation) {
435 #define OP_CONVERT(the_op) \
436                 case CARVE_OP_ ## the_op: \
437                         op = carve::csg::CSG::the_op; \
438                         break;
439                 OP_CONVERT(UNION)
440                 OP_CONVERT(INTERSECTION)
441                 OP_CONVERT(A_MINUS_B)
442                 default:
443                         return false;
444 #undef OP_CONVERT
445         }
446
447         CarveMeshDescr *output_descr = new CarveMeshDescr;
448         output_descr->poly = NULL;
449         try {
450                 MeshSet<3> *left = left_mesh->poly, *right = right_mesh->poly;
451                 carve::geom3d::Vector min, max;
452
453                 // TODO(sergey): Make importer/exporter to care about re-scale
454                 // to save extra mesh iteration here.
455                 carve_getRescaleMinMax(left, right, &min, &max);
456
457                 carve::rescale::rescale scaler(min.x, min.y, min.z, max.x, max.y, max.z);
458                 carve::rescale::fwd fwd_r(scaler);
459                 carve::rescale::rev rev_r(scaler);
460
461                 left->transform(fwd_r);
462                 right->transform(fwd_r);
463
464                 // Initialize attributes for maping from boolean result mesh back to
465                 // original geometry indices.
466                 initOrigIndexMapping(left_mesh, right_mesh,
467                                      &output_descr->orig_vert_mapping,
468                                      &output_descr->orig_face_edge_mapping,
469                                      &output_descr->face_edge_triangulated_flag,
470                                      &output_descr->orig_face_mapping);
471
472                 carve::csg::CSG csg;
473
474                 csg.hooks.registerHook(new carve::csg::CarveHoleResolver,
475                                        carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT);
476
477                 output_descr->orig_vert_mapping.installHooks(csg);
478                 output_descr->orig_face_edge_mapping.installHooks(csg);
479                 output_descr->face_edge_triangulated_flag.installHooks(csg);
480                 output_descr->orig_face_mapping.installHooks(csg);
481
482                 // Prepare operands for actual boolean operation.
483                 //
484                 // It's needed because operands might consist of several intersecting
485                 // meshes and in case of another operands intersect an edge loop of
486                 // intersecting that meshes tessellation of operation result can't be
487                 // done properly. The only way to make such situations working is to
488                 // union intersecting meshes of the same operand.
489                 carve_unionIntersections(&csg, &left, &right);
490                 left_mesh->poly = left;
491                 right_mesh->poly = right;
492
493                 if (left->meshes.size() == 0 || right->meshes.size() == 0) {
494                         // Normally shouldn't happen (zero-faces objects are handled by
495                         // modifier itself), but unioning intersecting meshes which doesn't
496                         // have consistent normals might lead to empty result which
497                         // wouldn't work here.
498
499                         return false;
500                 }
501
502                 output_descr->poly = csg.compute(left,
503                                                  right,
504                                                  op,
505                                                  NULL,
506                                                  carve::csg::CSG::CLASSIFY_EDGE);
507                 if (output_descr->poly) {
508                         output_descr->poly->transform(rev_r);
509
510                         dissolveTriangulatedEdges(output_descr);
511                 }
512         }
513         catch (carve::exception e) {
514                 std::cerr << "CSG failed, exception " << e.str() << std::endl;
515         }
516         catch (...) {
517                 std::cerr << "Unknown error in Carve library" << std::endl;
518         }
519
520         *output_mesh = output_descr;
521
522         return output_descr->poly != NULL;
523 }
524
525 static void exportMesh_handle_edges_list(MeshSet<3> *poly,
526                                          const std::vector<MeshSet<3>::edge_t*> &edges,
527                                          int start_edge_index,
528                                          CarveMeshExporter *mesh_exporter,
529                                          struct ExportMeshData *export_data,
530                                          const std::unordered_map<VertexPair, OrigIndex> &edge_origindex_map,
531                                          std::unordered_map<VertexPair, int> *edge_map)
532 {
533         for (int i = 0, edge_index = start_edge_index;
534              i < edges.size();
535              ++i, ++edge_index)
536         {
537                 MeshSet<3>::edge_t *edge = edges.at(i);
538                 MeshSet<3>::vertex_t *v1 = edge->vert;
539                 MeshSet<3>::vertex_t *v2 = edge->next->vert;
540
541                 OrigIndex orig_edge_index;
542
543                 if (!edgeIndexMap_get_if_exists(edge_origindex_map,
544                                                 v1,
545                                                 v2,
546                                                 &orig_edge_index))
547                 {
548                         orig_edge_index.first = CARVE_MESH_NONE;
549                         orig_edge_index.second = -1;
550                 }
551
552                 mesh_exporter->setEdge(export_data,
553                                        edge_index,
554                                        indexOf(v1, poly->vertex_storage),
555                                        indexOf(v2, poly->vertex_storage),
556                                        orig_edge_index.first,
557                                        orig_edge_index.second);
558
559                 edgeIndexMap_put(edge_map, v1, v2, edge_index);
560         }
561 }
562
563 void carve_exportMesh(CarveMeshDescr *mesh_descr,
564                       CarveMeshExporter *mesh_exporter,
565                       struct ExportMeshData *export_data)
566 {
567         OrigIndex origindex_none = std::make_pair((int)CARVE_MESH_NONE, -1);
568         MeshSet<3> *poly = mesh_descr->poly;
569         int num_vertices = poly->vertex_storage.size();
570         int num_edges = 0, num_loops = 0, num_polys = 0;
571
572         // Count edges from all manifolds.
573         for (int i = 0; i < poly->meshes.size(); ++i) {
574                 carve::mesh::Mesh<3> *mesh = poly->meshes[i];
575                 num_edges += mesh->closed_edges.size() + mesh->open_edges.size();
576         }
577
578         // Count polys and loops from all manifolds.
579         for (MeshSet<3>::face_iter face_iter = poly->faceBegin();
580              face_iter != poly->faceEnd();
581              ++face_iter, ++num_polys)
582         {
583                 MeshSet<3>::face_t *face = *face_iter;
584                 num_loops += face->n_edges;
585         }
586
587         // Initialize arrays for geometry in exported mesh.
588         mesh_exporter->initGeomArrays(export_data,
589                                       num_vertices,
590                                       num_edges,
591                                       num_loops,
592                                       num_polys);
593
594         // Get mapping from edge denoted by vertex pair to original edge index,
595         //
596         // This is needed because internally Carve interpolates data for per-face
597         // edges rather then having some global edge storage.
598         std::unordered_map<VertexPair, OrigIndex> edge_origindex_map;
599         for (MeshSet<3>::face_iter face_iter = poly->faceBegin();
600              face_iter != poly->faceEnd();
601              ++face_iter)
602         {
603                 MeshSet<3>::face_t *face = *face_iter;
604                 for (MeshSet<3>::face_t::edge_iter_t edge_iter = face->begin();
605                      edge_iter != face->end();
606                      ++edge_iter)
607                 {
608                         MeshSet<3>::edge_t &edge = *edge_iter;
609                         int edge_iter_index = edge_iter.idx();
610
611                         const OrigIndex &orig_loop_index =
612                                 mesh_descr->orig_face_edge_mapping.getAttribute(face,
613                                                                                 edge_iter_index,
614                                                                                 origindex_none);
615
616                         if (orig_loop_index.first != CARVE_MESH_NONE) {
617                                 OrigIndex orig_edge_index;
618
619                                 orig_edge_index.first = orig_loop_index.first;
620                                 orig_edge_index.second =
621                                         mesh_exporter->mapLoopToEdge(export_data,
622                                                                      orig_loop_index.first,
623                                                                      orig_loop_index.second);
624
625                                 MeshSet<3>::vertex_t *v1 = edge.vert;
626                                 MeshSet<3>::vertex_t *v2 = edge.next->vert;
627
628                                 edgeIndexMap_put(&edge_origindex_map, v1, v2, orig_edge_index);
629                         }
630                 }
631         }
632
633         // Export all the vertices.
634         std::vector<MeshSet<3>::vertex_t>::iterator vertex_iter = poly->vertex_storage.begin();
635         for (int i = 0; vertex_iter != poly->vertex_storage.end(); ++i, ++vertex_iter) {
636                 MeshSet<3>::vertex_t *vertex = &(*vertex_iter);
637
638                 OrigIndex orig_vert_index =
639                         mesh_descr->orig_vert_mapping.getAttribute(vertex, origindex_none);
640
641                 float coord[3];
642                 coord[0] = vertex->v[0];
643                 coord[1] = vertex->v[1];
644                 coord[2] = vertex->v[2];
645                 mesh_exporter->setVert(export_data, i, coord,
646                                        orig_vert_index.first,
647                                        orig_vert_index.second);
648         }
649
650         // Export all the edges.
651         std::unordered_map<VertexPair, int> edge_map;
652         for (int i = 0, edge_index = 0; i < poly->meshes.size(); ++i) {
653                 carve::mesh::Mesh<3> *mesh = poly->meshes[i];
654                 // Export closed edges.
655                 exportMesh_handle_edges_list(poly,
656                                              mesh->closed_edges,
657                                              edge_index,
658                                              mesh_exporter,
659                                              export_data,
660                                              edge_origindex_map,
661                                              &edge_map);
662                 edge_index += mesh->closed_edges.size();
663
664                 // Export open edges.
665                 exportMesh_handle_edges_list(poly,
666                                              mesh->open_edges,
667                                              edge_index,
668                                              mesh_exporter,
669                                              export_data,
670                                              edge_origindex_map,
671                                              &edge_map);
672                 edge_index += mesh->open_edges.size();
673         }
674
675         // Export all the loops and polys.
676         MeshSet<3>::face_iter face_iter = poly->faceBegin();
677         for (int loop_index = 0, poly_index = 0;
678              face_iter != poly->faceEnd();
679              ++face_iter, ++poly_index)
680         {
681                 int start_loop_index = loop_index;
682                 MeshSet<3>::face_t *face = *face_iter;
683                 const OrigIndex &orig_face_index =
684                         mesh_descr->orig_face_mapping.getAttribute(face, origindex_none);
685
686                 for (MeshSet<3>::face_t::edge_iter_t edge_iter = face->begin();
687                      edge_iter != face->end();
688                      ++edge_iter, ++loop_index)
689                 {
690                         MeshSet<3>::edge_t &edge = *edge_iter;
691                         const OrigIndex &orig_loop_index =
692                                 mesh_descr->orig_face_edge_mapping.getAttribute(face,
693                                                                                 edge_iter.idx(),
694                                                                                 origindex_none);
695
696                         mesh_exporter->setLoop(export_data,
697                                            loop_index,
698                                            indexOf(edge.vert, poly->vertex_storage),
699                                            edgeIndexMap_get(edge_map, edge.vert, edge.next->vert),
700                                            orig_loop_index.first,
701                                            orig_loop_index.second);
702                 }
703
704                 mesh_exporter->setPoly(export_data,
705                                        poly_index, start_loop_index, face->n_edges,
706                                        orig_face_index.first, orig_face_index.second);
707         }
708 }