[Bf-blender-cvs] [9643b2e] master: Preserve non-flat faces in boolean modifier
Sergey Sharybin
noreply at git.blender.org
Mon Feb 24 13:12:40 CET 2014
Commit: 9643b2e5b50399c8224d6de8d150d88c0d3e2848
Author: Sergey Sharybin
Date: Mon Feb 24 17:58:56 2014 +0600
https://developer.blender.org/rB9643b2e5b50399c8224d6de8d150d88c0d3e2848
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.
===================================================================
M extern/carve/CMakeLists.txt
M extern/carve/bundle.sh
M extern/carve/carve-capi.cc
M extern/carve/carve-util.cc
M extern/carve/files.txt
M extern/carve/include/carve/mesh_simplify.hpp
A extern/carve/include/carve/triangle_intersection.hpp
M extern/carve/include/carve/win32.h
A extern/carve/patches/mesh_simplify_dissolve_edges.patch
M extern/carve/patches/series
===================================================================
diff --git a/extern/carve/CMakeLists.txt b/extern/carve/CMakeLists.txt
index 11a92f9..5754290 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 91d5f44..2a3e621 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 ed46d19..319a201 100644
--- a/extern/carve/carve-capi.cc
+++ b/extern/carve/carve-capi.cc
@@ -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) {
diff --git a/extern/carve/carve-util.cc b/extern/carve/carve-util.cc
index b9b7fb1..b1943a6 100644
--- a/extern/carve/carve-util.cc
+++ b/extern/carve/carve-util.cc
@@ -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_
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list