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