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.
This commit is contained in:
Sergey Sharybin 2014-02-24 17:58:56 +06:00
parent 59472df8d6
commit 9643b2e5b5
Notes: blender-bot 2023-02-14 11:09:51 +01:00
Referenced by issue #38694, Boolean Modifier will triangulate 2 polyspheres on union
10 changed files with 263 additions and 7 deletions

View 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

View File

@ -111,6 +111,7 @@ cat > SConscript << EOF
Import ('env')
sources = env.Glob('lib/*.cpp')
sources += env.Glob('*.cc')
defs = []
incs = ['include']

View 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) {

View 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 { \

View 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

View 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,

View File

@ -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);
}
}

0
extern/carve/include/carve/win32.h vendored Normal file → Executable file
View File

View File

@ -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,

View File

@ -6,3 +6,4 @@ gcc46.patch
clang_is_heap_fix.patch
strict_flags.patch
interpolator_reorder.patch
mesh_simplify_dissolve_edges.patch