Commit: 9e09b5c418c0a436e3c84ccf38c065527988b0a0
Author: Howard Trickey
Date: Fri Aug 28 10:56:44 2020 -0400
Branches: master
https://developer.blender.org/rB9e09b5c418c0a436e3c84ccf38c065527988b0a0
Merge newboolean branch into master.
This is for design task T67744, Boolean Redesign.
It adds a choice of solver to the Boolean modifier and the
Intersect (Boolean) and Intersect (Knife) tools.
The 'Fast' choice is the current Bmesh boolean.
The new 'Exact' choice is a more advanced algorithm that supports
overlapping geometry and uses more robust calculations, but is
slower than the Fast choice.
The default with this commit is set to 'Exact'. We can decide before
the 2.91 release whether or not this is the right choice, but this
choice now will get us more testing and feedback on the new code.
===================================================================
M CMakeLists.txt
M build_files/build_environment/CMakeLists.txt
M build_files/cmake/Modules/GTestTesting.cmake
M build_files/cmake/config/blender_full.cmake
M build_files/cmake/config/blender_lite.cmake
M build_files/cmake/config/blender_release.cmake
M build_files/cmake/macros.cmake
M build_files/cmake/platform/platform_apple.cmake
M build_files/cmake/platform/platform_unix.cmake
M source/blender/blenlib/BLI_delaunay_2d.h
A source/blender/blenlib/BLI_double2.hh
A source/blender/blenlib/BLI_double3.hh
M source/blender/blenlib/BLI_float2.hh
M source/blender/blenlib/BLI_float3.hh
M source/blender/blenlib/BLI_math_base.h
A source/blender/blenlib/BLI_math_boolean.hh
A source/blender/blenlib/BLI_math_mpq.hh
M source/blender/blenlib/BLI_math_vector.h
A source/blender/blenlib/BLI_mesh_boolean.hh
A source/blender/blenlib/BLI_mesh_intersect.hh
A source/blender/blenlib/BLI_mpq2.hh
A source/blender/blenlib/BLI_mpq3.hh
M source/blender/blenlib/CMakeLists.txt
D source/blender/blenlib/intern/delaunay_2d.c
A source/blender/blenlib/intern/delaunay_2d.cc
A source/blender/blenlib/intern/math_boolean.cc
A source/blender/blenlib/intern/math_vec.cc
M source/blender/blenlib/intern/math_vector.c
M source/blender/blenlib/intern/math_vector_inline.c
A source/blender/blenlib/intern/mesh_boolean.cc
A source/blender/blenlib/intern/mesh_intersect.cc
M source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
A source/blender/blenlib/tests/BLI_mesh_boolean_test.cc
A source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
M source/blender/blenloader/intern/versioning_290.c
M source/blender/bmesh/CMakeLists.txt
M source/blender/bmesh/bmesh_tools.h
A source/blender/bmesh/tools/bmesh_boolean.cc
A source/blender/bmesh/tools/bmesh_boolean.h
M source/blender/bmesh/tools/bmesh_decimate_collapse.c
M source/blender/bmesh/tools/bmesh_edgesplit.h
M source/blender/editors/mesh/CMakeLists.txt
M source/blender/editors/mesh/editmesh_intersect.c
M source/blender/makesdna/DNA_modifier_types.h
M source/blender/makesrna/intern/CMakeLists.txt
M source/blender/makesrna/intern/rna_modifier.c
M source/blender/modifiers/CMakeLists.txt
M source/blender/modifiers/intern/MOD_boolean.c
M source/blender/python/bmesh/CMakeLists.txt
M source/blender/python/mathutils/mathutils_geometry.c
M source/creator/CMakeLists.txt
M tests/python/CMakeLists.txt
===================================================================
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 87557b6e905..76d2d578dc3 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -188,6 +188,7 @@ if(APPLE)
else()
option(WITH_XR_OPENXR "Enable VR features through the OpenXR
specification" ON)
endif()
+option(WITH_GMP "Enable features depending on GMP (Exact Boolean)" ON)
# Compositor
option(WITH_COMPOSITOR "Enable the tile based nodal compositor" ON)
@@ -1739,6 +1740,7 @@ if(FIRST_RUN)
info_cfg_option(WITH_QUADRIFLOW)
info_cfg_option(WITH_USD)
info_cfg_option(WITH_TBB)
+ info_cfg_option(WITH_GMP)
info_cfg_text("Compiler Options:")
info_cfg_option(WITH_BUILDINFO)
diff --git a/build_files/build_environment/CMakeLists.txt
b/build_files/build_environment/CMakeLists.txt
index 6415d270773..6368430235c 100644
--- a/build_files/build_environment/CMakeLists.txt
+++ b/build_files/build_environment/CMakeLists.txt
@@ -120,6 +120,7 @@ endif()
if(NOT WIN32 OR ENABLE_MINGW64)
include(cmake/gmp.cmake)
include(cmake/openjpeg.cmake)
+ include(cmake/gmp.cmake)
if(NOT WIN32 OR BUILD_MODE STREQUAL Release)
if(WIN32)
include(cmake/zlib_mingw.cmake)
diff --git a/build_files/cmake/Modules/GTestTesting.cmake
b/build_files/cmake/Modules/GTestTesting.cmake
index a744f4202da..053d5196f41 100644
--- a/build_files/cmake/Modules/GTestTesting.cmake
+++ b/build_files/cmake/Modules/GTestTesting.cmake
@@ -70,6 +70,9 @@ macro(BLENDER_SRC_GTEST_EX)
if(WITH_TBB)
target_link_libraries(${TARGET_NAME} ${TBB_LIBRARIES})
endif()
+ if(WITH_GMP)
+ target_link_libraries(${TARGET_NAME} ${GMP_LIBRARIES})
+ endif()
get_property(GENERATOR_IS_MULTI_CONFIG GLOBAL PROPERTY
GENERATOR_IS_MULTI_CONFIG)
if(GENERATOR_IS_MULTI_CONFIG)
diff --git a/build_files/cmake/config/blender_full.cmake
b/build_files/cmake/config/blender_full.cmake
index 7d3284af158..e546cd8f457 100644
--- a/build_files/cmake/config/blender_full.cmake
+++ b/build_files/cmake/config/blender_full.cmake
@@ -20,6 +20,7 @@ set(WITH_LIBMV ON CACHE BOOL "" FORCE)
set(WITH_LIBMV_SCHUR_SPECIALIZATIONS ON CACHE BOOL "" FORCE)
set(WITH_COMPOSITOR ON CACHE BOOL "" FORCE)
set(WITH_FREESTYLE ON CACHE BOOL "" FORCE)
+set(WITH_GMP ON CACHE BOOL "" FORCE)
set(WITH_IK_SOLVER ON CACHE BOOL "" FORCE)
set(WITH_IK_ITASC ON CACHE BOOL "" FORCE)
set(WITH_IMAGE_CINEON ON CACHE BOOL "" FORCE)
diff --git a/build_files/cmake/config/blender_lite.cmake
b/build_files/cmake/config/blender_lite.cmake
index 16c15961c59..7a664bbc008 100644
--- a/build_files/cmake/config/blender_lite.cmake
+++ b/build_files/cmake/config/blender_lite.cmake
@@ -25,6 +25,7 @@ set(WITH_LIBMV OFF CACHE BOOL "" FORCE)
set(WITH_LLVM OFF CACHE BOOL "" FORCE)
set(WITH_COMPOSITOR OFF CACHE BOOL "" FORCE)
set(WITH_FREESTYLE OFF CACHE BOOL "" FORCE)
+set(WITH_GMP OFF CACHE BOOL "" FORCE)
set(WITH_IK_SOLVER OFF CACHE BOOL "" FORCE)
set(WITH_IK_ITASC OFF CACHE BOOL "" FORCE)
set(WITH_IMAGE_CINEON OFF CACHE BOOL "" FORCE)
diff --git a/build_files/cmake/config/blender_release.cmake
b/build_files/cmake/config/blender_release.cmake
index ddd9aa1d766..76294a2e046 100644
--- a/build_files/cmake/config/blender_release.cmake
+++ b/build_files/cmake/config/blender_release.cmake
@@ -21,6 +21,7 @@ set(WITH_LIBMV ON CACHE BOOL "" FORCE)
set(WITH_LIBMV_SCHUR_SPECIALIZATIONS ON CACHE BOOL "" FORCE)
set(WITH_COMPOSITOR ON CACHE BOOL "" FORCE)
set(WITH_FREESTYLE ON CACHE BOOL "" FORCE)
+set(WITH_GMP ON CACHE BOOL "" FORCE)
set(WITH_IK_SOLVER ON CACHE BOOL "" FORCE)
set(WITH_IK_ITASC ON CACHE BOOL "" FORCE)
set(WITH_IMAGE_CINEON ON CACHE BOOL "" FORCE)
diff --git a/build_files/cmake/macros.cmake b/build_files/cmake/macros.cmake
index 51cfadecc3e..dcab6d58870 100644
--- a/build_files/cmake/macros.cmake
+++ b/build_files/cmake/macros.cmake
@@ -496,6 +496,10 @@ function(SETUP_LIBDIRS)
link_directories(${ALEMBIC_LIBPATH})
endif()
+ if(WITH_GMP)
+ link_directories(${GMP_LIBPATH})
+ endif()
+
if(WITH_GHOST_WAYLAND)
link_directories(
${wayland-client_LIBRARY_DIRS}
diff --git a/build_files/cmake/platform/platform_apple.cmake
b/build_files/cmake/platform/platform_apple.cmake
index ace5de3330c..822110cb88f 100644
--- a/build_files/cmake/platform/platform_apple.cmake
+++ b/build_files/cmake/platform/platform_apple.cmake
@@ -407,6 +407,15 @@ if(WITH_TBB)
find_package(TBB)
endif()
+if(WITH_GMP)
+ find_package(GMP)
+
+ if(NOT GMP_FOUND)
+ set(WITH_GMP OFF)
+ message(STATUS "GMP not found")
+ endif()
+endif()
+
# CMake FindOpenMP doesn't know about AppleClang before 3.12, so provide
custom flags.
if(WITH_OPENMP)
if(CMAKE_C_COMPILER_ID MATCHES "AppleClang" AND CMAKE_C_COMPILER_VERSION
VERSION_GREATER_EQUAL "7.0")
diff --git a/build_files/cmake/platform/platform_unix.cmake
b/build_files/cmake/platform/platform_unix.cmake
index 0ef180435b3..3a7875ca46c 100644
--- a/build_files/cmake/platform/platform_unix.cmake
+++ b/build_files/cmake/platform/platform_unix.cmake
@@ -427,6 +427,15 @@ if(WITH_TBB)
find_package_wrapper(TBB)
endif()
+if(WITH_GMP)
+ find_package(GMP)
+
+ if(NOT GMP_FOUND)
+ set(WITH_GMP OFF)
+ message(STATUS "GMP not found")
+ endif()
+endif()
+
if(WITH_XR_OPENXR)
find_package(XR_OpenXR_SDK)
if(NOT XR_OPENXR_SDK_FOUND)
diff --git a/source/blender/blenlib/BLI_delaunay_2d.h
b/source/blender/blenlib/BLI_delaunay_2d.h
index a826a6b2677..7027477ac7f 100644
--- a/source/blender/blenlib/BLI_delaunay_2d.h
+++ b/source/blender/blenlib/BLI_delaunay_2d.h
@@ -18,6 +18,9 @@
/** \file
* \ingroup bli
+ *
+ * This header file contains both a C interface and a C++ interface
+ * to the 2D Constrained Delaunay Triangulation library routine.
*/
#ifdef __cplusplus
@@ -107,11 +110,6 @@ extern "C" {
* If zero is supplied for epsilon, an internal value of 1e-8 used
* instead, since this code will not work correctly if it is not allowed
* to merge "too near" vertices.
- *
- * Normally, if epsilon is non-zero, there is an "input modify" pass which
- * checks to see if some vertices are within epsilon of other edges, and
- * snapping them to those edges if so. You can skip this pass by setting
- * skip_input_modify to true. (This is also useful in some unit tests.)
*/
typedef struct CDT_input {
int verts_len;
@@ -123,7 +121,6 @@ typedef struct CDT_input {
int *faces_start_table;
int *faces_len_table;
float epsilon;
- bool skip_input_modify;
} CDT_input;
/**
@@ -150,12 +147,9 @@ typedef struct CDT_input {
* - faces_orig, faces_orig_start_table, faces_orig_len_table
*
* For edges, the edges_orig triple can also say which original face
- * edge is part of a given output edge. If an index in edges_orig
- * is greater than the input's edges_len, then subtract input's edges_len
- * from it to some number i: then the face edge that starts from the
- * input vertex at input's faces[i] is the corresponding face edge.
- * for convenience, face_edge_offset in the result will be the input's
- * edges_len, so that this conversion can be easily done by the caller.
+ * edge is part of a given output edge. See the comment below
+ * on the C++ interface for how to decode the entries in the edges_orig
+ * table.
*/
typedef struct CDT_result {
int verts_len;
@@ -207,4 +201,69 @@ void BLI_delaunay_2d_cdt_free(CDT_result *result);
#ifdef __cplusplus
}
-#endif
+
+/* C++ Interface. */
+
+# include "BLI_array.hh"
+# include "BLI_double2.hh"
+# include "BLI_math_mpq.hh"
+# include "BLI_mpq2.hh"
+# include "BLI_vector.hh"
+
+namespace blender::meshintersect {
+
+/* vec2<Arith_t> is a 2d vector with Arith_t as the type for coordinates. */
+template<typename Arith_t> struct vec2_impl;
+template<> struct vec2_impl<double> {
+ typedef double2 type;
+};
+
+# ifdef WITH_GMP
+template<> struct vec2_impl<mpq_class> {
+ typedef mpq2 type;
+};
+# endif
+
+template<typename Arith_t> using vec2 = typename vec2_impl<Arith_t>::type;
+
+template<typename Arith_t> class CDT_input {
+ public:
+ Array<vec2<Arith_t>> vert;
+ Array<std::pair<int, int>> edge;
+ Array<Vector<int>> face;
+ Arith_t epsilon{0};
+};
+
+template<typename Arith_t> class CDT_result {
+ public:
+ Array<vec2<Arith_t>> vert;
+ Array<std::pair<int, int>> edge;
+ Array<Vector<int>> face;
+ /** For each output vert, which input verts correspond to it? */
+ Array<Vector<int>> vert_orig;
+ /**
+ * For each output edge, which input edges does it overlap?
+ * The input edge ids are encoded as follows:
+ * if the value is less than face_edge_offset, then it is
+ * an index into the input edge[] array.
+ * else let (a, b) = the quotient and remainder of dividing
+ * the edge index by face_edge_offset; "a" will be the input face + 1,
+ * and "b" will be a position within that face.
+ */
+ Array<Vector<int>> edge_orig;
+ /** For each output face, which original faces does it overlap? */
+ Array<Vector<int>> face_orig;
+ /** Used to encode edge_orig (see above). */
+ int face_edge_offset;
+};
+
+CDT_result<double> delaunay_2d_calc(const CDT_input<double> &input,
CDT_output_type output_type);
+
+# ifdef WITH_GMP
+CDT_result<mpq_class> delaunay_2d_calc(const CDT_input<mpq_class> &input,
+ CDT_output_type output_type);
+# endif
+
+} /* namespace blender::meshintersect */
+
+#endif /* __cplusplus */
diff --git a/source/blender/blenlib/BLI_double2.hh
b/source/blender/blenlib/BLI_double2.hh
new file mode 100644
index 00000000000..3466b946e73
--- /dev/null
+++ b/source/blender/blenlib/BLI_double2.hh
@@ -0,0 +1,143 @@
+/*
+ * 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 e
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
