Rework carve integration into 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
33 using carve::mesh::MeshSet;
34
35 typedef std::pair<int, int> OrigIndex;
36 typedef std::pair<MeshSet<3>::vertex_t *, MeshSet<3>::vertex_t *> VertexPair;
37 typedef carve::interpolate::VertexAttr<OrigIndex> OrigVertMapping;
38 typedef carve::interpolate::FaceAttr<OrigIndex> OrigFaceMapping;
39 typedef carve::interpolate::FaceEdgeAttr<OrigIndex> OrigFaceEdgeMapping;
40
41 typedef struct CarveMeshDescr {
42         // Stores mesh data itself.
43         MeshSet<3> *poly;
44
45         // N-th element of the vector indicates index of an original mesh loop.
46         std::vector<int> orig_loop_index_map;
47
48         // N-th element of the vector indicates index of an original mesh poly.
49         std::vector<int> orig_poly_index_map;
50
51         // The folloving mapping is only filled in for output mesh.
52
53         // Mapping from the face verts back to original vert index.
54         OrigVertMapping orig_vert_mapping;
55
56         // Mapping from the face edges back to (original edge index, original loop index).
57         OrigFaceEdgeMapping orig_face_edge_mapping;
58
59         // Mapping from the faces back to original poly index.
60         OrigFaceMapping orig_face_mapping;
61 } CarveMeshDescr;
62
63 namespace {
64
65 template <typename T1, typename T2>
66 void edgeIndexMap_put(std::unordered_map<std::pair<T1, T1>, T2> *edge_map,
67                       const T1 &v1,
68                       const T1 &v2,
69                       const T2 &index)
70 {
71         if (v1 < v2) {
72                 (*edge_map)[std::make_pair(v1, v2)] = index;
73         }
74         else {
75                 (*edge_map)[std::make_pair(v2, v1)] = index;
76         }
77 }
78
79 template <typename T1, typename T2>
80 const T2 &edgeIndexMap_get(const std::unordered_map<std::pair<T1, T1>, T2> &edge_map,
81                            const T1 &v1,
82                            const T1 &v2)
83 {
84         typedef std::unordered_map<std::pair<T1, T1>, T2> Map;
85         typename Map::const_iterator found;
86
87         if (v1 < v2) {
88                 found = edge_map.find(std::make_pair(v1, v2));
89         }
90         else {
91                 found = edge_map.find(std::make_pair(v2, v1));
92         }
93
94         assert(found != edge_map.end());
95         return found->second;
96 }
97
98 template <typename T1, typename T2>
99 bool edgeIndexMap_get_if_exists(const std::unordered_map<std::pair<T1, T1>, T2> &edge_map,
100                                 const T1 &v1,
101                                 const T1 &v2,
102                                 T2 *out)
103 {
104         typedef std::unordered_map<std::pair<T1, T1>, T2> Map;
105         typename Map::const_iterator found;
106
107         if (v1 < v2) {
108                 found = edge_map.find(std::make_pair(v1, v2));
109         }
110         else {
111                 found = edge_map.find(std::make_pair(v2, v1));
112         }
113
114         if (found == edge_map.end()) {
115                 return false;
116         }
117         *out = found->second;
118         return true;
119 }
120
121 template <typename T>
122 inline int indexOf(const T *element, const std::vector<T> &vector_from)
123 {
124         return element - &vector_from.at(0);
125 }
126
127 void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
128                                   int which_mesh,
129                                   const std::vector<int> &orig_loop_index_map,
130                                   const std::vector<int> &orig_poly_index_map,
131                                   OrigVertMapping *orig_vert_mapping,
132                                   OrigFaceEdgeMapping *orig_face_edge_mapping,
133                                   OrigFaceMapping *orig_face_attr)
134 {
135         MeshSet<3> *poly = mesh->poly;
136
137         std::vector<MeshSet<3>::vertex_t>::iterator vertex_iter =
138                 poly->vertex_storage.begin();
139         for (int i = 0;
140              vertex_iter != poly->vertex_storage.end();
141              ++i, ++vertex_iter)
142         {
143                 MeshSet<3>::vertex_t *vertex = &(*vertex_iter);
144                 orig_vert_mapping->setAttribute(vertex,
145                                                 std::make_pair(which_mesh, i));
146         }
147
148         MeshSet<3>::face_iter face_iter = poly->faceBegin();
149         for (int i = 0, loop_map_index = 0;
150              face_iter != poly->faceEnd();
151              ++face_iter, ++i)
152         {
153                 const MeshSet<3>::face_t *face = *face_iter;
154
155                 // Mapping from carve face back to original poly index.
156                 int orig_poly_index = orig_poly_index_map[i];
157                 orig_face_attr->setAttribute(face, std::make_pair(which_mesh, orig_poly_index));
158
159                 for (MeshSet<3>::face_t::const_edge_iter_t edge_iter = face->begin();
160                      edge_iter != face->end();
161                      ++edge_iter, ++loop_map_index)
162                 {
163                         int orig_loop_index = orig_loop_index_map[loop_map_index];
164                         if (orig_loop_index != -1) {
165                                 // Mapping from carve face edge back to original loop index.
166                                 orig_face_edge_mapping->setAttribute(face,
167                                                                      edge_iter.idx(),
168                                                                      std::make_pair(which_mesh,
169                                                                                     orig_loop_index));
170                         }
171                 }
172         }
173 }
174
175 void initOrigIndexMapping(CarveMeshDescr *left_mesh,
176                           CarveMeshDescr *right_mesh,
177                           OrigVertMapping *orig_vert_mapping,
178                           OrigFaceEdgeMapping *orig_face_edge_mapping,
179                           OrigFaceMapping *orig_face_mapping)
180 {
181         initOrigIndexMeshFaceMapping(left_mesh,
182                                      CARVE_MESH_LEFT,
183                                      left_mesh->orig_loop_index_map,
184                                      left_mesh->orig_poly_index_map,
185                                      orig_vert_mapping,
186                                      orig_face_edge_mapping,
187                                      orig_face_mapping);
188
189         initOrigIndexMeshFaceMapping(right_mesh,
190                                      CARVE_MESH_RIGHT,
191                                      right_mesh->orig_loop_index_map,
192                                      right_mesh->orig_poly_index_map,
193                                      orig_vert_mapping,
194                                      orig_face_edge_mapping,
195                                      orig_face_mapping);
196 }
197
198 }  // namespace
199
200 CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
201                               CarveMeshImporter *mesh_importer)
202 {
203 #define MAX_STATIC_VERTS 64
204
205         CarveMeshDescr *mesh_descr = new CarveMeshDescr;
206
207         // Import verices from external mesh to Carve.
208         int num_verts = mesh_importer->getNumVerts(import_data);
209         std::vector<carve::geom3d::Vector> vertices;
210         vertices.reserve(num_verts);
211         for (int i = 0; i < num_verts; i++) {
212                 float position[3];
213                 mesh_importer->getVertCoord(import_data, i, position);
214                 vertices.push_back(carve::geom::VECTOR(position[0],
215                                                        position[1],
216                                                        position[2]));
217         }
218
219         // Import polys from external mesh to Carve.
220         int verts_of_poly_static[MAX_STATIC_VERTS];
221         int *verts_of_poly_dynamic = NULL;
222         int verts_of_poly_dynamic_size = 0;
223
224         int num_loops = mesh_importer->getNumLoops(import_data);
225         int num_polys = mesh_importer->getNumPolys(import_data);
226         int loop_index = 0;
227         int num_tessellated_polys = 0;
228         std::vector<int> face_indices;
229         face_indices.reserve(num_loops);
230         mesh_descr->orig_loop_index_map.reserve(num_polys);
231         mesh_descr->orig_poly_index_map.reserve(num_polys);
232         for (int i = 0; i < num_polys; i++) {
233                 int verts_per_poly =
234                         mesh_importer->getNumPolyVerts(import_data, i);
235                 int *verts_of_poly;
236
237                 if (verts_per_poly <= MAX_STATIC_VERTS) {
238                         verts_of_poly = verts_of_poly_static;
239                 }
240                 else {
241                         if (verts_of_poly_dynamic_size < verts_per_poly) {
242                                 if (verts_of_poly_dynamic != NULL) {
243                                         delete [] verts_of_poly_dynamic;
244                                 }
245                                 verts_of_poly_dynamic = new int[verts_per_poly];
246                                 verts_of_poly_dynamic_size = verts_per_poly;
247                         }
248                         verts_of_poly = verts_of_poly_dynamic;
249                 }
250
251                 mesh_importer->getPolyVerts(import_data, i, verts_of_poly);
252
253                 carve::math::Matrix3 axis_matrix;
254                 if (!carve_checkPolyPlanarAndGetNormal(vertices,
255                                                        verts_per_poly,
256                                                        verts_of_poly,
257                                                        &axis_matrix)) {
258                         int num_triangles;
259
260                         num_triangles = carve_triangulatePoly(import_data,
261                                                               mesh_importer,
262                                                               i,
263                                                               loop_index,
264                                                               vertices,
265                                                               verts_per_poly,
266                                                               verts_of_poly,
267                                                               axis_matrix,
268                                                               &face_indices,
269                                                               &mesh_descr->orig_loop_index_map,
270                                                               &mesh_descr->orig_poly_index_map);
271
272                         num_tessellated_polys += num_triangles;
273                 }
274                 else {
275                         face_indices.push_back(verts_per_poly);
276                         for (int j = 0; j < verts_per_poly; ++j) {
277                                 mesh_descr->orig_loop_index_map.push_back(loop_index++);
278                                 face_indices.push_back(verts_of_poly[j]);
279                         }
280                         mesh_descr->orig_poly_index_map.push_back(i);
281                         num_tessellated_polys++;
282                 }
283         }
284
285         if (verts_of_poly_dynamic != NULL) {
286                 delete [] verts_of_poly_dynamic;
287         }
288
289         mesh_descr->poly = new MeshSet<3> (vertices,
290                                            num_tessellated_polys,
291                                            face_indices);
292
293         return mesh_descr;
294
295 #undef MAX_STATIC_VERTS
296 }
297
298 void carve_deleteMesh(CarveMeshDescr *mesh_descr)
299 {
300         delete mesh_descr->poly;
301         delete mesh_descr;
302 }
303
304 bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
305                                    CarveMeshDescr *right_mesh,
306                                    int operation,
307                                    CarveMeshDescr **output_mesh)
308 {
309         *output_mesh = NULL;
310
311         carve::csg::CSG::OP op;
312         switch (operation) {
313 #define OP_CONVERT(the_op) \
314                 case CARVE_OP_ ## the_op: \
315                         op = carve::csg::CSG::the_op; \
316                         break;
317                 OP_CONVERT(UNION)
318                 OP_CONVERT(INTERSECTION)
319                 OP_CONVERT(A_MINUS_B)
320                 default:
321                         return false;
322 #undef OP_CONVERT
323         }
324
325         CarveMeshDescr *output_descr = new CarveMeshDescr;
326         output_descr->poly = NULL;
327         try {
328                 MeshSet<3> *left = left_mesh->poly, *right = right_mesh->poly;
329                 carve::geom3d::Vector min, max;
330
331                 // TODO(sergey): Make importer/exporter to care about re-scale
332                 // to save extra mesh iteration here.
333                 carve_getRescaleMinMax(left, right, &min, &max);
334
335                 carve::rescale::rescale scaler(min.x, min.y, min.z, max.x, max.y, max.z);
336                 carve::rescale::fwd fwd_r(scaler);
337                 carve::rescale::rev rev_r(scaler);
338
339                 left->transform(fwd_r);
340                 right->transform(fwd_r);
341
342                 // Initialize attributes for maping from boolean result mesh back to
343                 // original geometry indices.
344                 initOrigIndexMapping(left_mesh, right_mesh,
345                                      &output_descr->orig_vert_mapping,
346                                      &output_descr->orig_face_edge_mapping,
347                                      &output_descr->orig_face_mapping);
348
349                 carve::csg::CSG csg;
350
351                 output_descr->orig_vert_mapping.installHooks(csg);
352                 output_descr->orig_face_edge_mapping.installHooks(csg);
353                 output_descr->orig_face_mapping.installHooks(csg);
354
355                 // Prepare operands for actual boolean operation.
356                 //
357                 // It's needed because operands might consist of several intersecting
358                 // meshes and in case of another operands intersect an edge loop of
359                 // intersecting that meshes tessellation of operation result can't be
360                 // done properly. The only way to make such situations working is to
361                 // union intersecting meshes of the same operand.
362                 carve_unionIntersections(&csg, &left, &right);
363                 left_mesh->poly = left;
364                 right_mesh->poly = right;
365
366                 if (left->meshes.size() == 0 || right->meshes.size() == 0) {
367                         // Normally shouldn't happen (zero-faces objects are handled by
368                         // modifier itself), but unioning intersecting meshes which doesn't
369                         // have consistent normals might lead to empty result which
370                         // wouldn't work here.
371
372                         return false;
373                 }
374
375                 output_descr->poly = csg.compute(left,
376                                                  right,
377                                                  op,
378                                                  NULL,
379                                                  carve::csg::CSG::CLASSIFY_EDGE);
380                 if (output_descr->poly) {
381                         output_descr->poly->transform(rev_r);
382                 }
383         }
384         catch (carve::exception e) {
385                 std::cerr << "CSG failed, exception " << e.str() << std::endl;
386         }
387         catch (...) {
388                 std::cerr << "Unknown error in Carve library" << std::endl;
389         }
390
391         *output_mesh = output_descr;
392
393         return output_descr->poly != NULL;
394 }
395
396 static void exportMesh_handle_edges_list(MeshSet<3> *poly,
397                                          const std::vector<MeshSet<3>::edge_t*> &edges,
398                                          int start_edge_index,
399                                          CarveMeshExporter *mesh_exporter,
400                                          struct ExportMeshData *export_data,
401                                          const std::unordered_map<VertexPair, OrigIndex> &edge_origindex_map,
402                                          std::unordered_map<VertexPair, int> *edge_map)
403 {
404         for (int i = 0, edge_index = start_edge_index;
405              i < edges.size();
406              ++i, ++edge_index)
407         {
408                 MeshSet<3>::edge_t *edge = edges.at(i);
409                 MeshSet<3>::vertex_t *v1 = edge->vert;
410                 MeshSet<3>::vertex_t *v2 = edge->next->vert;
411
412                 OrigIndex orig_edge_index;
413
414                 if (!edgeIndexMap_get_if_exists(edge_origindex_map,
415                                                 v1,
416                                                 v2,
417                                                 &orig_edge_index))
418                 {
419                         orig_edge_index.first = CARVE_MESH_NONE;
420                         orig_edge_index.second = -1;
421                 }
422
423                 mesh_exporter->setEdge(export_data,
424                                        edge_index,
425                                        indexOf(v1, poly->vertex_storage),
426                                        indexOf(v2, poly->vertex_storage),
427                                        orig_edge_index.first,
428                                        orig_edge_index.second);
429
430                 edgeIndexMap_put(edge_map, v1, v2, edge_index);
431         }
432 }
433
434 void carve_exportMesh(CarveMeshDescr *mesh_descr,
435                       CarveMeshExporter *mesh_exporter,
436                       struct ExportMeshData *export_data)
437 {
438         OrigIndex origindex_none = std::make_pair((int)CARVE_MESH_NONE, -1);
439         MeshSet<3> *poly = mesh_descr->poly;
440         int num_vertices = poly->vertex_storage.size();
441         int num_edges = 0, num_loops = 0, num_polys = 0;
442
443         // Count edges from all manifolds.
444         for (int i = 0; i < poly->meshes.size(); ++i) {
445                 carve::mesh::Mesh<3> *mesh = poly->meshes[i];
446                 num_edges += mesh->closed_edges.size() + mesh->open_edges.size();
447         }
448
449         // Count polys and loops from all manifolds.
450         for (MeshSet<3>::face_iter face_iter = poly->faceBegin();
451              face_iter != poly->faceEnd();
452              ++face_iter, ++num_polys)
453         {
454                 MeshSet<3>::face_t *face = *face_iter;
455                 num_loops += face->n_edges;
456         }
457
458         // Initialize arrays for geometry in exported mesh.
459         mesh_exporter->initGeomArrays(export_data,
460                                       num_vertices,
461                                       num_edges,
462                                       num_loops,
463                                       num_polys);
464
465         // Get mapping from edge denoted by vertex pair to original edge index,
466         //
467         // This is needed because internally Carve interpolates data for per-face
468         // edges rather then having some global edge storage.
469         std::unordered_map<VertexPair, OrigIndex> edge_origindex_map;
470         for (MeshSet<3>::face_iter face_iter = poly->faceBegin();
471              face_iter != poly->faceEnd();
472              ++face_iter)
473         {
474                 MeshSet<3>::face_t *face = *face_iter;
475                 for (MeshSet<3>::face_t::edge_iter_t edge_iter = face->begin();
476                      edge_iter != face->end();
477                      ++edge_iter)
478                 {
479                         MeshSet<3>::edge_t &edge = *edge_iter;
480                         int edge_iter_index = edge_iter.idx();
481
482                         const OrigIndex &orig_loop_index =
483                                 mesh_descr->orig_face_edge_mapping.getAttribute(face,
484                                                                                 edge_iter_index,
485                                                                                 origindex_none);
486
487                         if (orig_loop_index.first != CARVE_MESH_NONE) {
488                                 OrigIndex orig_edge_index;
489
490                                 orig_edge_index.first = orig_loop_index.first;
491                                 orig_edge_index.second =
492                                         mesh_exporter->mapLoopToEdge(export_data,
493                                                                      orig_loop_index.first,
494                                                                      orig_loop_index.second);
495
496                                 MeshSet<3>::vertex_t *v1 = edge.vert;
497                                 MeshSet<3>::vertex_t *v2 = edge.next->vert;
498
499                                 edgeIndexMap_put(&edge_origindex_map, v1, v2, orig_edge_index);
500                         }
501                 }
502         }
503
504         // Export all the vertices.
505         std::vector<MeshSet<3>::vertex_t>::iterator vertex_iter = poly->vertex_storage.begin();
506         for (int i = 0; vertex_iter != poly->vertex_storage.end(); ++i, ++vertex_iter) {
507                 MeshSet<3>::vertex_t *vertex = &(*vertex_iter);
508
509                 OrigIndex orig_vert_index =
510                         mesh_descr->orig_vert_mapping.getAttribute(vertex, origindex_none);
511
512                 float coord[3];
513                 coord[0] = vertex->v[0];
514                 coord[1] = vertex->v[1];
515                 coord[2] = vertex->v[2];
516                 mesh_exporter->setVert(export_data, i, coord,
517                                        orig_vert_index.first,
518                                        orig_vert_index.second);
519         }
520
521         // Export all the edges.
522         std::unordered_map<VertexPair, int> edge_map;
523         for (int i = 0, edge_index = 0; i < poly->meshes.size(); ++i) {
524                 carve::mesh::Mesh<3> *mesh = poly->meshes[i];
525
526                 // Export closed edges.
527                 exportMesh_handle_edges_list(poly,
528                                              mesh->closed_edges,
529                                              edge_index,
530                                              mesh_exporter,
531                                              export_data,
532                                              edge_origindex_map,
533                                              &edge_map);
534
535                 // Export open edges.
536                 exportMesh_handle_edges_list(poly,
537                                              mesh->open_edges,
538                                              edge_index,
539                                              mesh_exporter,
540                                              export_data,
541                                              edge_origindex_map,
542                                              &edge_map);
543
544                 edge_index += mesh->closed_edges.size();
545         }
546
547         // Export all the loops and polys.
548         MeshSet<3>::face_iter face_iter = poly->faceBegin();
549         for (int loop_index = 0, poly_index = 0;
550              face_iter != poly->faceEnd();
551              ++face_iter, ++poly_index)
552         {
553                 int start_loop_index = loop_index;
554                 MeshSet<3>::face_t *face = *face_iter;
555                 const OrigIndex &orig_face_index =
556                         mesh_descr->orig_face_mapping.getAttribute(face, origindex_none);
557
558                 for (MeshSet<3>::face_t::edge_iter_t edge_iter = face->begin();
559                      edge_iter != face->end();
560                      ++edge_iter, ++loop_index)
561                 {
562                         MeshSet<3>::edge_t &edge = *edge_iter;
563                         const OrigIndex &orig_loop_index =
564                                 mesh_descr->orig_face_edge_mapping.getAttribute(face,
565                                                                                 edge_iter.idx(),
566                                                                                 origindex_none);
567
568                         mesh_exporter->setLoop(export_data,
569                                            loop_index,
570                                            indexOf(edge.vert, poly->vertex_storage),
571                                            edgeIndexMap_get(edge_map, edge.vert, edge.next->vert),
572                                            orig_loop_index.first,
573                                            orig_loop_index.second);
574                 }
575
576                 mesh_exporter->setPoly(export_data,
577                                        poly_index, start_loop_index, face->n_edges,
578                                        orig_face_index.first, orig_face_index.second);
579         }
580 }