From 9643b2e5b50399c8224d6de8d150d88c0d3e2848 Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Mon, 24 Feb 2014 17:58:56 +0600 Subject: Preserve non-flat faces in boolean modifier 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 | 1 + extern/carve/bundle.sh | 1 + extern/carve/carve-capi.cc | 125 +++++++++++++++++++++ extern/carve/carve-util.cc | 13 ++- extern/carve/files.txt | 1 + extern/carve/include/carve/mesh_simplify.hpp | 29 ++++- .../carve/include/carve/triangle_intersection.hpp | 53 +++++++++ extern/carve/include/carve/win32.h | 0 .../patches/mesh_simplify_dissolve_edges.patch | 46 ++++++++ extern/carve/patches/series | 1 + 10 files changed, 263 insertions(+), 7 deletions(-) create mode 100644 extern/carve/include/carve/triangle_intersection.hpp mode change 100644 => 100755 extern/carve/include/carve/win32.h create mode 100644 extern/carve/patches/mesh_simplify_dissolve_edges.patch (limited to 'extern') diff --git a/extern/carve/CMakeLists.txt b/extern/carve/CMakeLists.txt index 11a92f92abc..5754290d710 100644 --- a/extern/carve/CMakeLists.txt +++ b/extern/carve/CMakeLists.txt @@ -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 diff --git a/extern/carve/bundle.sh b/extern/carve/bundle.sh index 91d5f44a880..2a3e621fab0 100755 --- a/extern/carve/bundle.sh +++ b/extern/carve/bundle.sh @@ -111,6 +111,7 @@ cat > SConscript << EOF Import ('env') sources = env.Glob('lib/*.cpp') +sources += env.Glob('*.cc') defs = [] incs = ['include'] diff --git a/extern/carve/carve-capi.cc b/extern/carve/carve-capi.cc index ed46d196d72..319a20129d1 100644 --- a/extern/carve/carve-capi.cc +++ b/extern/carve/carve-capi.cc @@ -30,6 +30,7 @@ #include #include #include +#include using carve::mesh::MeshSet; @@ -38,6 +39,7 @@ typedef std::pair::vertex_t *, MeshSet<3>::vertex_t *> VertexPair; typedef carve::interpolate::VertexAttr OrigVertMapping; typedef carve::interpolate::FaceAttr OrigFaceMapping; typedef carve::interpolate::FaceEdgeAttr OrigFaceEdgeMapping; +typedef carve::interpolate::FaceEdgeAttr 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 &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 *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::edge_t *> edge_set_t; + typedef std::unordered_set::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 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) { diff --git a/extern/carve/carve-util.cc b/extern/carve/carve-util.cc index b9b7fb1c03f..b1943a6dd74 100644 --- a/extern/carve/carve-util.cc +++ b/extern/carve/carve-util.cc @@ -619,6 +619,7 @@ int triangulateNGon_carveTriangulator(const std::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 { \ diff --git a/extern/carve/files.txt b/extern/carve/files.txt index f7da6038692..5c02a04dfe2 100644 --- a/extern/carve/files.txt +++ b/extern/carve/files.txt @@ -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 diff --git a/extern/carve/include/carve/mesh_simplify.hpp b/extern/carve/include/carve/mesh_simplify.hpp index 1c5169caf58..2126c57011b 100644 --- a/extern/carve/include/carve/mesh_simplify.hpp +++ b/extern/carve/include/carve/mesh_simplify.hpp @@ -32,8 +32,6 @@ #include #include -#include "write_ply.hpp" - namespace carve { namespace mesh { @@ -1184,6 +1182,33 @@ namespace carve { return modifications; } + void dissolveMeshEdges(mesh_t *mesh, std::unordered_set 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 index 00000000000..f1f4c2137f1 --- /dev/null +++ b/extern/carve/include/carve/triangle_intersection.hpp @@ -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 + +#include + +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); + } +} diff --git a/extern/carve/include/carve/win32.h b/extern/carve/include/carve/win32.h old mode 100644 new mode 100755 diff --git a/extern/carve/patches/mesh_simplify_dissolve_edges.patch b/extern/carve/patches/mesh_simplify_dissolve_edges.patch new file mode 100644 index 00000000000..bd671bfcbcf --- /dev/null +++ b/extern/carve/patches/mesh_simplify_dissolve_edges.patch @@ -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 + #include + +-#include "write_ply.hpp" +- + + namespace carve { + namespace mesh { +@@ -1184,6 +1182,33 @@ + return modifications; + } + ++ void dissolveMeshEdges(mesh_t *mesh, std::unordered_set 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/patches/series b/extern/carve/patches/series index 30937b4b9cf..2c187af4808 100644 --- a/extern/carve/patches/series +++ b/extern/carve/patches/series @@ -6,3 +6,4 @@ gcc46.patch clang_is_heap_fix.patch strict_flags.patch interpolator_reorder.patch +mesh_simplify_dissolve_edges.patch -- cgit v1.2.3