[Bf-blender-cvs] [83617d2] master: Rework carve integration into boolean modifier
Sergey Sharybin
noreply at git.blender.org
Thu Feb 13 12:17:37 CET 2014
Commit: 83617d24d536ec234bbe53b8b0fbcb76e7b5b3ee
Author: Sergey Sharybin
Date: Thu Jan 30 18:32:23 2014 +0600
https://developer.blender.org/rB83617d24d536ec234bbe53b8b0fbcb76e7b5b3ee
Rework carve integration into boolean modifier
Goal of this commit is to support NGons for boolean modifier
(currently mesh is being tessellated before performing boolean
operation) and also solve the limitation of loosing edge custom
data layers after boolean operation is performed.
Main idea is to make it so boolean modifier uses Carve library
directly via it's C-API, avoiding BSP intermediate level which
was doubling amount of memory needed for the operation and which
also used quite reasonable amount of overhead time.
Perhaps memory usage and CPU usage are the same after all the
features are implemented but we've got support now:
- ORIGINDEX for all the geometry
- Interpolation of edge custom data (seams, crease)
- NGons support
Triangulation rule is changed now as well, so now non-flat
polygons are not being merged back after Carve work. This is
so because it's not so trivial to support for NGons and
having different behavior for quads and NGons is even more
creepy.
Reviewers: lukastoenne, campbellbarton
Differential Revision: https://developer.blender.org/D274
===================================================================
M extern/carve/CMakeLists.txt
M extern/carve/bundle.sh
A extern/carve/carve-capi.cc
A extern/carve/carve-capi.h
A extern/carve/carve-util.cc
A extern/carve/carve-util.h
M extern/carve/include/carve/interpolator.hpp
A extern/carve/patches/interpolator_reorder.patch
M extern/carve/patches/series
M intern/CMakeLists.txt
D intern/bsp/CMakeLists.txt
D intern/bsp/SConscript
D intern/bsp/extern/CSG_BooleanOps.h
D intern/bsp/intern/BOP_CarveInterface.cpp
D intern/bsp/intern/BOP_Interface.h
D intern/bsp/intern/BSP_CSGException.h
D intern/bsp/intern/BSP_CSGMesh.cpp
D intern/bsp/intern/BSP_CSGMesh.h
D intern/bsp/intern/BSP_CSGMesh_CFIterator.h
D intern/bsp/intern/BSP_MeshPrimitives.cpp
D intern/bsp/intern/BSP_MeshPrimitives.h
D intern/bsp/intern/CSG_BooleanOps.cpp
M intern/container/CMakeLists.txt
D intern/container/CTR_TaggedIndex.h
D intern/container/CTR_TaggedSetOps.h
M source/blender/blenkernel/CMakeLists.txt
M source/blender/blenkernel/SConscript
M source/blender/blenlib/BLI_polyfill2d.h
M source/blender/modifiers/CMakeLists.txt
M source/blender/modifiers/SConscript
M source/blender/modifiers/intern/MOD_boolean.c
M source/blender/modifiers/intern/MOD_boolean_util.c
===================================================================
diff --git a/extern/carve/CMakeLists.txt b/extern/carve/CMakeLists.txt
index 5e917ac..11a92f9 100644
--- a/extern/carve/CMakeLists.txt
+++ b/extern/carve/CMakeLists.txt
@@ -35,6 +35,8 @@ set(INC_SYS
)
set(SRC
+ carve-capi.cc
+ carve-util.cc
lib/aabb.cpp
lib/carve.cpp
lib/convex_hull.cpp
@@ -62,6 +64,8 @@ set(SRC
lib/timing.cpp
lib/triangulator.cpp
+ carve-capi.h
+ carve-util.h
lib/csg_collector.hpp
lib/csg_data.hpp
lib/csg_detail.hpp
diff --git a/extern/carve/bundle.sh b/extern/carve/bundle.sh
index 05967d6..91d5f44 100755
--- a/extern/carve/bundle.sh
+++ b/extern/carve/bundle.sh
@@ -70,8 +70,12 @@ set(INC_SYS
)
set(SRC
+ carve-capi.cc
+ carve-util.cc
${sources}
+ carve-capi.h
+ carve-util.h
${headers}
${includes}
diff --git a/extern/carve/carve-capi.cc b/extern/carve/carve-capi.cc
new file mode 100644
index 0000000..7478c34
--- /dev/null
+++ b/extern/carve/carve-capi.cc
@@ -0,0 +1,580 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2014 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): Blender Foundation,
+ * Sergey Sharybin
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include "carve-capi.h"
+#include "carve-util.h"
+
+#include <carve/interpolator.hpp>
+#include <carve/rescale.hpp>
+
+using carve::mesh::MeshSet;
+
+typedef std::pair<int, int> OrigIndex;
+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 struct CarveMeshDescr {
+ // Stores mesh data itself.
+ MeshSet<3> *poly;
+
+ // N-th element of the vector indicates index of an original mesh loop.
+ std::vector<int> orig_loop_index_map;
+
+ // N-th element of the vector indicates index of an original mesh poly.
+ std::vector<int> orig_poly_index_map;
+
+ // The folloving mapping is only filled in for output mesh.
+
+ // Mapping from the face verts back to original vert index.
+ OrigVertMapping orig_vert_mapping;
+
+ // Mapping from the face edges back to (original edge index, original loop index).
+ OrigFaceEdgeMapping orig_face_edge_mapping;
+
+ // Mapping from the faces back to original poly index.
+ OrigFaceMapping orig_face_mapping;
+} CarveMeshDescr;
+
+namespace {
+
+template <typename T1, typename T2>
+void edgeIndexMap_put(std::unordered_map<std::pair<T1, T1>, T2> *edge_map,
+ const T1 &v1,
+ const T1 &v2,
+ const T2 &index)
+{
+ if (v1 < v2) {
+ (*edge_map)[std::make_pair(v1, v2)] = index;
+ }
+ else {
+ (*edge_map)[std::make_pair(v2, v1)] = index;
+ }
+}
+
+template <typename T1, typename T2>
+const T2 &edgeIndexMap_get(const std::unordered_map<std::pair<T1, T1>, T2> &edge_map,
+ const T1 &v1,
+ const T1 &v2)
+{
+ typedef std::unordered_map<std::pair<T1, T1>, T2> Map;
+ typename Map::const_iterator found;
+
+ if (v1 < v2) {
+ found = edge_map.find(std::make_pair(v1, v2));
+ }
+ else {
+ found = edge_map.find(std::make_pair(v2, v1));
+ }
+
+ assert(found != edge_map.end());
+ return found->second;
+}
+
+template <typename T1, typename T2>
+bool edgeIndexMap_get_if_exists(const std::unordered_map<std::pair<T1, T1>, T2> &edge_map,
+ const T1 &v1,
+ const T1 &v2,
+ T2 *out)
+{
+ typedef std::unordered_map<std::pair<T1, T1>, T2> Map;
+ typename Map::const_iterator found;
+
+ if (v1 < v2) {
+ found = edge_map.find(std::make_pair(v1, v2));
+ }
+ else {
+ found = edge_map.find(std::make_pair(v2, v1));
+ }
+
+ if (found == edge_map.end()) {
+ return false;
+ }
+ *out = found->second;
+ return true;
+}
+
+template <typename T>
+inline int indexOf(const T *element, const std::vector<T> &vector_from)
+{
+ return element - &vector_from.at(0);
+}
+
+void initOrigIndexMeshFaceMapping(CarveMeshDescr *mesh,
+ int which_mesh,
+ const std::vector<int> &orig_loop_index_map,
+ const std::vector<int> &orig_poly_index_map,
+ OrigVertMapping *orig_vert_mapping,
+ OrigFaceEdgeMapping *orig_face_edge_mapping,
+ OrigFaceMapping *orig_face_attr)
+{
+ MeshSet<3> *poly = mesh->poly;
+
+ std::vector<MeshSet<3>::vertex_t>::iterator vertex_iter =
+ poly->vertex_storage.begin();
+ for (int i = 0;
+ vertex_iter != poly->vertex_storage.end();
+ ++i, ++vertex_iter)
+ {
+ MeshSet<3>::vertex_t *vertex = &(*vertex_iter);
+ orig_vert_mapping->setAttribute(vertex,
+ std::make_pair(which_mesh, i));
+ }
+
+ MeshSet<3>::face_iter face_iter = poly->faceBegin();
+ for (int i = 0, loop_map_index = 0;
+ face_iter != poly->faceEnd();
+ ++face_iter, ++i)
+ {
+ const MeshSet<3>::face_t *face = *face_iter;
+
+ // Mapping from carve face back to original poly index.
+ int orig_poly_index = orig_poly_index_map[i];
+ orig_face_attr->setAttribute(face, std::make_pair(which_mesh, orig_poly_index));
+
+ for (MeshSet<3>::face_t::const_edge_iter_t edge_iter = face->begin();
+ edge_iter != face->end();
+ ++edge_iter, ++loop_map_index)
+ {
+ int orig_loop_index = orig_loop_index_map[loop_map_index];
+ if (orig_loop_index != -1) {
+ // Mapping from carve face edge back to original loop index.
+ orig_face_edge_mapping->setAttribute(face,
+ edge_iter.idx(),
+ std::make_pair(which_mesh,
+ orig_loop_index));
+ }
+ }
+ }
+}
+
+void initOrigIndexMapping(CarveMeshDescr *left_mesh,
+ CarveMeshDescr *right_mesh,
+ OrigVertMapping *orig_vert_mapping,
+ OrigFaceEdgeMapping *orig_face_edge_mapping,
+ OrigFaceMapping *orig_face_mapping)
+{
+ initOrigIndexMeshFaceMapping(left_mesh,
+ CARVE_MESH_LEFT,
+ left_mesh->orig_loop_index_map,
+ left_mesh->orig_poly_index_map,
+ orig_vert_mapping,
+ orig_face_edge_mapping,
+ orig_face_mapping);
+
+ initOrigIndexMeshFaceMapping(right_mesh,
+ CARVE_MESH_RIGHT,
+ right_mesh->orig_loop_index_map,
+ right_mesh->orig_poly_index_map,
+ orig_vert_mapping,
+ orig_face_edge_mapping,
+ orig_face_mapping);
+}
+
+} // namespace
+
+CarveMeshDescr *carve_addMesh(struct ImportMeshData *import_data,
+ CarveMeshImporter *mesh_importer)
+{
+#define MAX_STATIC_VERTS 64
+
+ CarveMeshDescr *mesh_descr = new CarveMeshDescr;
+
+ // Import verices from external mesh to Carve.
+ int num_verts = mesh_importer->getNumVerts(import_data);
+ std::vector<carve::geom3d::Vector> vertices;
+ vertices.reserve(num_verts);
+ for (int i = 0; i < num_verts; i++) {
+ float position[3];
+ mesh_importer->getVertCoord(import_data, i, position);
+ vertices.push_back(carve::geom::VECTOR(position[0],
+ position[1],
+ position[2]));
+ }
+
+ // Import polys from external mesh to Carve.
+ int verts_of_poly_static[MAX_STATIC_VERTS];
+ int *verts_of_poly_dynamic = NULL;
+ int verts_of_poly_dynamic_size = 0;
+
+ int num_loops = mesh_importer->getNumLoops(import_data);
+ int num_polys = mesh_importer->getNumPolys(import_data);
+ int loop_index = 0;
+ int num_tessellated_polys = 0;
+ std::vector<int> face_indices;
+ face_indices.reserve(num_loops);
+ mesh_descr->orig_loop_index_map.reserve(num_polys);
+ mesh_descr->orig_poly_index_map.reserve(num_polys);
+ for (int i = 0; i < num_polys; i++) {
+ int verts_per_poly =
+ mesh_importer->getNumPolyVerts(import_data, i);
+ int *verts_of_poly;
+
+ if (verts_per_poly <= MAX_STATIC_VERTS) {
+ verts_of_poly = verts_of_poly_static;
+ }
+ else {
+ if (verts_of_poly_dynamic_size < verts_per_poly) {
+ if (verts_of_poly_dynamic != NULL) {
+ delete [] verts_of_poly_dynamic;
+ }
+ verts_of_poly_dynamic = new int[verts_per_poly];
+ verts_of_poly_dynamic_size = verts_per_poly;
+ }
+ verts_of_poly = verts_of_poly_dynamic;
+ }
+
+ mesh_importer->getPolyVerts(import_data, i, verts_of_poly);
+
+ carve::math::Matrix3 axis_matrix;
+ if (!carve_checkPolyPlanarAndGetNormal(vertices,
+ verts_per_poly,
+ verts_of_poly,
+ &axis_matrix)) {
+ int num_triangles;
+
+ num_triangles = carve_triangulatePoly(import_data,
+ mesh_importer,
+ i,
+ loop_index,
+ vertices,
+ verts_per_poly,
+ verts_of_poly,
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list