Preserve non-flat faces in boolean modifier
authorSergey Sharybin <sergey.vfx@gmail.com>
Mon, 24 Feb 2014 11:58:56 +0000 (17:58 +0600)
committerSergey Sharybin <sergey.vfx@gmail.com>
Mon, 24 Feb 2014 12:10:33 +0000 (18:10 +0600)
This commit implements dissolving of edges which were used
to triangulate non-flat faces. This slows things down a bit
(around 5% on heave mesh with all faces triangulated).

We could improve speed of dissolve a bit here (so not a bell
to add an option for triangulation yet).

Also fixed wrong edge origindex mapping.

extern/carve/CMakeLists.txt
extern/carve/bundle.sh
extern/carve/carve-capi.cc
extern/carve/carve-util.cc
extern/carve/files.txt
extern/carve/include/carve/mesh_simplify.hpp
extern/carve/include/carve/triangle_intersection.hpp [new file with mode: 0644]
extern/carve/include/carve/win32.h [changed mode: 0644->0755]
extern/carve/patches/mesh_simplify_dissolve_edges.patch [new file with mode: 0644]
extern/carve/patches/series

index 11a92f92abc3ed9b1d8be54672d73e1072cc59da..5754290d710c7f5f1964cc2165d20de7d510b8d2 100644 (file)
@@ -140,6 +140,7 @@ set(SRC
        include/carve/tag.hpp
        include/carve/timing.hpp
        include/carve/tree.hpp
+       include/carve/triangle_intersection.hpp
        include/carve/triangulator.hpp
        include/carve/triangulator_impl.hpp
        include/carve/util.hpp
index 91d5f44a880aa9cc0468fe764de50d761e802668..2a3e621fab0c623b12d848366302d09739cfedef 100755 (executable)
@@ -111,6 +111,7 @@ cat > SConscript << EOF
 Import ('env')
 
 sources = env.Glob('lib/*.cpp')
+sources += env.Glob('*.cc')
 
 defs = []
 incs = ['include']
index ed46d196d72ca07a7c208f57bbe62c17f6c69fe2..319a20129d166a51dbcc8e7ff310e19c72fac30d 100644 (file)
@@ -30,6 +30,7 @@
 #include <carve/interpolator.hpp>
 #include <carve/rescale.hpp>
 #include <carve/csg_triangulator.hpp>
+#include <carve/mesh_simplify.hpp>
 
 using carve::mesh::MeshSet;
 
@@ -38,6 +39,7 @@ typedef std::pair<MeshSet<3>::vertex_t *, MeshSet<3>::vertex_t *> VertexPair;
 typedef carve::interpolate::VertexAttr<OrigIndex> OrigVertMapping;
 typedef carve::interpolate::FaceAttr<OrigIndex> OrigFaceMapping;
 typedef carve::interpolate::FaceEdgeAttr<OrigIndex> OrigFaceEdgeMapping;
+typedef carve::interpolate::FaceEdgeAttr<bool> FaceEdgeTriangulatedFlag;
 
 typedef struct CarveMeshDescr {
        // Stores mesh data itself.
@@ -57,6 +59,8 @@ typedef struct CarveMeshDescr {
        // Mapping from the face edges back to (original edge index, original loop index).
        OrigFaceEdgeMapping orig_face_edge_mapping;
 
+       FaceEdgeTriangulatedFlag face_edge_triangulated_flag;
+
        // Mapping from the faces back to original poly index.
        OrigFaceMapping orig_face_mapping;
 } CarveMeshDescr;
@@ -131,6 +135,7 @@ void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
                                   const std::vector<int> &orig_poly_index_map,
                                   OrigVertMapping *orig_vert_mapping,
                                   OrigFaceEdgeMapping *orig_face_edge_mapping,
+                                  FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
                                   OrigFaceMapping *orig_face_attr)
 {
        MeshSet<3> *poly = mesh->poly;
@@ -169,6 +174,9 @@ void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
                                                                     std::make_pair(which_mesh,
                                                                                    orig_loop_index));
                        }
+                       else {
+                               face_edge_triangulated_flag->setAttribute(face, edge_iter.idx(), true);
+                       }
                }
        }
 }
@@ -177,6 +185,7 @@ void initOrigIndexMapping(CarveMeshDescr *left_mesh,
                           CarveMeshDescr *right_mesh,
                           OrigVertMapping *orig_vert_mapping,
                           OrigFaceEdgeMapping *orig_face_edge_mapping,
+                          FaceEdgeTriangulatedFlag *face_edge_triangulated_flag,
                           OrigFaceMapping *orig_face_mapping)
 {
        initOrigIndexMeshFaceMapping(left_mesh,
@@ -185,6 +194,7 @@ void initOrigIndexMapping(CarveMeshDescr *left_mesh,
                                     left_mesh->orig_poly_index_map,
                                     orig_vert_mapping,
                                     orig_face_edge_mapping,
+                                    face_edge_triangulated_flag,
                                     orig_face_mapping);
 
        initOrigIndexMeshFaceMapping(right_mesh,
@@ -193,9 +203,119 @@ void initOrigIndexMapping(CarveMeshDescr *left_mesh,
                                     right_mesh->orig_poly_index_map,
                                     orig_vert_mapping,
                                     orig_face_edge_mapping,
+                                    face_edge_triangulated_flag,
                                     orig_face_mapping);
 }
 
+void origEdgeMappingForFace(MeshSet<3>::face_t *face,
+                            OrigFaceEdgeMapping *orig_face_edge_mapping,
+                            std::unordered_map<VertexPair, OrigIndex> *edge_origindex_map)
+{
+       OrigIndex origindex_none = std::make_pair((int)CARVE_MESH_NONE, -1);
+
+       MeshSet<3>::edge_t *edge = face->edge;
+       for (int i = 0;
+            i < face->n_edges;
+            ++i, edge = edge->next)
+       {
+               MeshSet<3>::vertex_t *v1 = edge->vert;
+               MeshSet<3>::vertex_t *v2 = edge->next->vert;
+
+               OrigIndex orig_edge_index =
+                       orig_face_edge_mapping->getAttribute(edge->face, i, origindex_none);
+
+               edgeIndexMap_put(edge_origindex_map, v1, v2, orig_edge_index);
+       }
+}
+
+void dissolveTriangulatedEdges(MeshSet<3>::mesh_t *mesh,
+                               OrigFaceEdgeMapping *orig_face_edge_mapping,
+                               FaceEdgeTriangulatedFlag *face_edge_triangulated_flag)
+{
+       typedef std::unordered_set<MeshSet<3>::edge_t *> edge_set_t;
+       typedef std::unordered_set<MeshSet<3>::face_t *> face_set_t;
+       edge_set_t triangulated_face_edges;
+
+       for (int face_index = 0; face_index < mesh->faces.size(); face_index++) {
+               MeshSet<3>::face_t *face = mesh->faces[face_index];
+               MeshSet<3>::edge_t *edge = face->edge;
+               for (int edge_index = 0;
+                    edge_index < face->n_edges;
+                    ++edge_index, edge = edge->next)
+               {
+                       const bool is_triangulated_edge =
+                               face_edge_triangulated_flag->getAttribute(face,
+                                                                         edge_index,
+                                                                         false);
+                       if (is_triangulated_edge) {
+                               MeshSet<3>::edge_t *e1 = std::min(edge, edge->rev);
+                               triangulated_face_edges.insert(e1);
+                       }
+               }
+       }
+
+       if (triangulated_face_edges.size()) {
+               face_set_t triangulated_faces;
+               std::unordered_map<VertexPair, OrigIndex> edge_origindex_map;
+
+               for (edge_set_t::iterator it = triangulated_face_edges.begin();
+                    it != triangulated_face_edges.end();
+                    ++it)
+               {
+                       MeshSet<3>::edge_t *edge = *it;
+
+                       origEdgeMappingForFace(edge->face,
+                                              orig_face_edge_mapping,
+                                              &edge_origindex_map);
+                       triangulated_faces.insert(edge->face);
+
+                       origEdgeMappingForFace(edge->rev->face,
+                                              orig_face_edge_mapping,
+                                              &edge_origindex_map);
+                       triangulated_faces.insert(edge->rev->face);
+               }
+
+               carve::mesh::MeshSimplifier simplifier;
+               simplifier.dissolveMeshEdges(mesh, triangulated_face_edges);
+
+               for (int face_index = 0; face_index < mesh->faces.size(); face_index++) {
+                       MeshSet<3>::face_t *face = mesh->faces[face_index];
+
+                       if (triangulated_faces.find(face) != triangulated_faces.end()) {
+                               MeshSet<3>::edge_t *edge = face->edge;
+                               for (int edge_index = 0;
+                                    edge_index < face->n_edges;
+                                    ++edge_index, edge = edge->next)
+                               {
+                                       MeshSet<3>::vertex_t *v1 = edge->vert;
+                                       MeshSet<3>::vertex_t *v2 = edge->next->vert;
+
+                                       OrigIndex orig_edge_index =
+                                               edgeIndexMap_get(edge_origindex_map,
+                                                                v1,
+                                                                v2);
+
+                                       orig_face_edge_mapping->setAttribute(face, edge_index, orig_edge_index);
+                               }
+                       }
+               }
+       }
+}
+
+void dissolveTriangulatedEdges(CarveMeshDescr *mesh_descr)
+{
+       MeshSet<3> *poly = mesh_descr->poly;
+       FaceEdgeTriangulatedFlag *face_edge_triangulated_flag =
+               &mesh_descr->face_edge_triangulated_flag;
+
+       for (int i = 0; i < poly->meshes.size(); ++i) {
+               MeshSet<3>::mesh_t *mesh = poly->meshes[i];
+               dissolveTriangulatedEdges(mesh,
+                                         &mesh_descr->orig_face_edge_mapping,
+                                         face_edge_triangulated_flag);
+       }
+}
+
 }  // namespace
 
 CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
@@ -271,6 +391,7 @@ CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
                                                              &mesh_descr->orig_poly_index_map);
 
                        num_tessellated_polys += num_triangles;
+                       loop_index += verts_per_poly;
                }
                else {
                        face_indices.push_back(verts_per_poly);
@@ -345,6 +466,7 @@ bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
                initOrigIndexMapping(left_mesh, right_mesh,
                                     &output_descr->orig_vert_mapping,
                                     &output_descr->orig_face_edge_mapping,
+                                    &output_descr->face_edge_triangulated_flag,
                                     &output_descr->orig_face_mapping);
 
                carve::csg::CSG csg;
@@ -354,6 +476,7 @@ bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
 
                output_descr->orig_vert_mapping.installHooks(csg);
                output_descr->orig_face_edge_mapping.installHooks(csg);
+               output_descr->face_edge_triangulated_flag.installHooks(csg);
                output_descr->orig_face_mapping.installHooks(csg);
 
                // Prepare operands for actual boolean operation.
@@ -383,6 +506,8 @@ bool carve_performBooleanOperation(CarveMeshDescr *left_mesh,
                                                 carve::csg::CSG::CLASSIFY_EDGE);
                if (output_descr->poly) {
                        output_descr->poly->transform(rev_r);
+
+                       dissolveTriangulatedEdges(output_descr);
                }
        }
        catch (carve::exception e) {
index b9b7fb1c03fced3bc16f9486ce4e96bc4cfbc7ce..b1943a6dd7420b0b08cda50cc567619613854178 100644 (file)
@@ -619,6 +619,7 @@ int triangulateNGon_carveTriangulator(const std::vector<Vector> &vertices,
        }
 
        carve::triangulate::triangulate(poly_2d, *triangles);
+       carve::triangulate::improve(poly_2d, *triangles);
 
        return triangles->size();
 }
@@ -737,9 +738,9 @@ int carve_triangulatePoly(struct ImportMeshData *import_data,
                }
 
                for (int i = 0; i < triangles.size(); ++i) {
-                       int v1 = triangles[i].c,
+                       int v1 = triangles[i].a,
                            v2 = triangles[i].b,
-                           v3 = triangles[i].a;
+                           v3 = triangles[i].c;
 
                        // Sanity check of the triangle.
                        assert(v1 != v2);
@@ -750,13 +751,15 @@ int carve_triangulatePoly(struct ImportMeshData *import_data,
                        assert(v3 < verts_per_poly);
 
                        face_indices->push_back(3);
-                       face_indices->push_back(verts_of_poly[v3]);
-                       face_indices->push_back(verts_of_poly[v2]);
                        face_indices->push_back(verts_of_poly[v1]);
+                       face_indices->push_back(verts_of_poly[v2]);
+                       face_indices->push_back(verts_of_poly[v3]);
 
 #define CHECK_TRIANGLE_LOOP_INDEX(v1, v2) \
        { \
-               if (v2 == v1 + 1) { \
+               int v1_ = std::min(v1, v2), \
+                   v2_ = std::max(v1, v2); \
+               if (v1_ + 1 == v2_ || v1_ + verts_per_poly == v2_ + 1) { \
                        orig_loop_index_map->push_back(start_loop_index + v1); \
                } \
                else { \
index f7da6038692000387b0ffa80f89a41fa8b231993..5c02a04dfe27044596b701f172cd7af7ee9e22a5 100644 (file)
@@ -1,6 +1,7 @@
 include/carve/vertex_impl.hpp
 include/carve/aabb_impl.hpp
 include/carve/csg.hpp
+include/carve/triangle_intersection.hpp
 include/carve/pointset_iter.hpp
 include/carve/debug_hooks.hpp
 include/carve/mesh.hpp
index 1c5169caf58ae293a0e7cc08432e008158ab351a..2126c57011ba9614972ca8cbb38a21442681f956 100644 (file)
@@ -32,8 +32,6 @@
 #include <algorithm>
 #include <vector>
 
-#include "write_ply.hpp"
-
 
 namespace carve {
   namespace mesh {
@@ -1184,6 +1182,33 @@ namespace carve {
         return modifications;
       }
 
+      void dissolveMeshEdges(mesh_t *mesh, std::unordered_set<edge_t *> dissolve_edges) {
+        while (dissolve_edges.size()) {
+            MeshSet<3>::edge_t *edge = *dissolve_edges.begin();
+            if (edge->face == edge->rev->face) {
+                dissolve_edges.erase(edge);
+                continue;
+            }
+
+            MeshSet<3>::edge_t *removed = edge->mergeFaces();
+            if (removed == NULL) {
+                dissolve_edges.erase(edge);
+            } else {
+                MeshSet<3>::edge_t *e = removed;
+                do {
+                    MeshSet<3>::edge_t *n = e->next;
+                    dissolve_edges.erase(std::min(e, e->rev));
+                    delete e->rev;
+                    delete e;
+                    e = n;
+                } while (e != removed);
+            }
+        }
+
+        removeRemnantFaces(mesh);
+        cleanFaceEdges(mesh);
+        mesh->cacheEdges();
+     }
 
 
       size_t improveMesh(meshset_t *meshset,
diff --git a/extern/carve/include/carve/triangle_intersection.hpp b/extern/carve/include/carve/triangle_intersection.hpp
new file mode 100644 (file)
index 0000000..f1f4c21
--- /dev/null
@@ -0,0 +1,53 @@
+// Begin License:
+// Copyright (C) 2006-2011 Tobias Sargeant (tobias.sargeant@gmail.com).
+// All rights reserved.
+//
+// This file is part of the Carve CSG Library (http://carve-csg.com/)
+//
+// This file may be used under the terms of the GNU General Public
+// License version 2.0 as published by the Free Software Foundation
+// and appearing in the file LICENSE.GPL2 included in the packaging of
+// this file.
+//
+// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
+// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE.
+// End:
+
+
+#pragma once
+
+#include <carve/carve.hpp>
+
+#include <carve/geom.hpp>
+
+namespace carve {
+  namespace geom {
+
+    enum TriangleIntType {
+      TR_TYPE_NONE = 0,
+      TR_TYPE_TOUCH = 1,
+      TR_TYPE_INT = 2
+    };
+
+    enum TriangleInt {
+      TR_INT_NONE = 0,      // no intersection.
+      TR_INT_INT = 1,       // intersection.
+      TR_INT_VERT = 2,      // intersection due to shared vertex.
+      TR_INT_EDGE = 3,      // intersection due to shared edge.
+      TR_INT_TRI = 4        // intersection due to identical triangle.
+    };
+
+    TriangleInt triangle_intersection(const vector<2> tri_a[3], const vector<2> tri_b[3]);
+    TriangleInt triangle_intersection(const vector<3> tri_a[3], const vector<3> tri_b[3]);
+
+    bool triangle_intersection_simple(const vector<2> tri_a[3], const vector<2> tri_b[3]);
+    bool triangle_intersection_simple(const vector<3> tri_a[3], const vector<3> tri_b[3]);
+
+    TriangleIntType triangle_intersection_exact(const vector<2> tri_a[3], const vector<2> tri_b[3]);
+    TriangleIntType triangle_intersection_exact(const vector<3> tri_a[3], const vector<3> tri_b[3]);
+
+    TriangleIntType triangle_linesegment_intersection_exact(const vector<2> tri_a[3], const vector<2> line_b[2]);
+    TriangleIntType triangle_point_intersection_exact(const vector<2> tri_a[3], const vector<2> &pt_b);
+  }
+}
old mode 100644 (file)
new mode 100755 (executable)
diff --git a/extern/carve/patches/mesh_simplify_dissolve_edges.patch b/extern/carve/patches/mesh_simplify_dissolve_edges.patch
new file mode 100644 (file)
index 0000000..bd671bf
--- /dev/null
@@ -0,0 +1,46 @@
+diff -r e82d852e4fb0 include/carve/mesh_simplify.hpp
+--- a/include/carve/mesh_simplify.hpp  Wed Jan 15 13:16:14 2014 +1100
++++ b/include/carve/mesh_simplify.hpp  Mon Feb 24 18:02:07 2014 +0600
+@@ -32,8 +32,6 @@
+ #include <algorithm>
+ #include <vector>
+-#include "write_ply.hpp"
+-
+ namespace carve {
+   namespace mesh {
+@@ -1184,6 +1182,33 @@
+         return modifications;
+       }
++      void dissolveMeshEdges(mesh_t *mesh, std::unordered_set<edge_t *> dissolve_edges) {
++        while (dissolve_edges.size()) {
++            MeshSet<3>::edge_t *edge = *dissolve_edges.begin();
++            if (edge->face == edge->rev->face) {
++                dissolve_edges.erase(edge);
++                continue;
++            }
++
++            MeshSet<3>::edge_t *removed = edge->mergeFaces();
++            if (removed == NULL) {
++                dissolve_edges.erase(edge);
++            } else {
++                MeshSet<3>::edge_t *e = removed;
++                do {
++                    MeshSet<3>::edge_t *n = e->next;
++                    dissolve_edges.erase(std::min(e, e->rev));
++                    delete e->rev;
++                    delete e;
++                    e = n;
++                } while (e != removed);
++            }
++        }
++
++        removeRemnantFaces(mesh);
++        cleanFaceEdges(mesh);
++        mesh->cacheEdges();
++     }
+       size_t improveMesh(meshset_t *meshset,
index 30937b4b9cf6c2ad639f6778e4b26c95f509f931..2c187af4808edf04901135743bea2b3e634289bb 100644 (file)
@@ -6,3 +6,4 @@ gcc46.patch
 clang_is_heap_fix.patch
 strict_flags.patch
 interpolator_reorder.patch
+mesh_simplify_dissolve_edges.patch