[Bf-blender-cvs] [d40819946b1] newboolean: Start of PolyMesh interface for boolean.
Howard Trickey
noreply at git.blender.org
Fri Jun 26 14:46:08 CEST 2020
Commit: d40819946b1d2498a8164f52cd1f78c582bee5b3
Author: Howard Trickey
Date: Wed Jun 17 08:55:05 2020 -0400
Branches: newboolean
https://developer.blender.org/rBd40819946b1d2498a8164f52cd1f78c582bee5b3
Start of PolyMesh interface for boolean.
Also refactored delaunay to put the 2d mesh representation into
an externally visible CDTArrangement class. Not sure yet whether
I will use this; if I end up not using it, will move that part of
the header back into the implementation file.
===================================================================
M release/datafiles/locale
M release/scripts/addons
M release/scripts/addons_contrib
M source/blender/blenlib/BLI_boolean.h
M source/blender/blenlib/BLI_delaunay_2d.h
M source/blender/blenlib/intern/boolean.cc
M source/blender/blenlib/intern/delaunay_2d.cc
M source/blender/blenlib/intern/mesh_intersect.cc
M tests/gtests/blenlib/BLI_boolean_test.cc
M tests/gtests/blenlib/BLI_delaunay_2d_test.cc
===================================================================
diff --git a/release/datafiles/locale b/release/datafiles/locale
index 6a514935090..72e5040232a 160000
--- a/release/datafiles/locale
+++ b/release/datafiles/locale
@@ -1 +1 @@
-Subproject commit 6a51493509090c7fa3bd2e69105761c3c144c7dd
+Subproject commit 72e5040232a544b293dca05dac5707bd4e4bffaf
diff --git a/release/scripts/addons b/release/scripts/addons
index ba2521b7ed1..aea05413b76 160000
--- a/release/scripts/addons
+++ b/release/scripts/addons
@@ -1 +1 @@
-Subproject commit ba2521b7ed14b5deb6bb9a82a442bc85d2e05224
+Subproject commit aea05413b7689f1c72e04804b4faabc3694aec91
diff --git a/release/scripts/addons_contrib b/release/scripts/addons_contrib
index 4cf486c4eba..7c36b48507f 160000
--- a/release/scripts/addons_contrib
+++ b/release/scripts/addons_contrib
@@ -1 +1 @@
-Subproject commit 4cf486c4eba158b453bdd87d97b74192ef7497b2
+Subproject commit 7c36b48507f79ca62f8c038bad0fb3468c4f48e2
diff --git a/source/blender/blenlib/BLI_boolean.h b/source/blender/blenlib/BLI_boolean.h
index d9105e025a1..080804dd643 100644
--- a/source/blender/blenlib/BLI_boolean.h
+++ b/source/blender/blenlib/BLI_boolean.h
@@ -55,6 +55,34 @@ void BLI_boolean_trimesh_free(Boolean_trimesh_output *output);
#ifdef __cplusplus
}
+
+# include "BLI_array.hh"
+# include "BLI_mesh_intersect.hh"
+# include "BLI_mpq3.hh"
+# include "BLI_optional.hh"
+# include "gmpxx.h"
+
+namespace blender {
+namespace meshintersect {
+
+struct PolyMeshOrig {
+ Array<int> vert_orig;
+ Array<Array<int>> face_orig;
+ Array<Array<std::pair<int, int>>> edge_orig;
+};
+
+struct PolyMesh {
+ Array<mpq3> vert;
+ Array<Array<int>> face;
+ Optional<Array<Array<IndexedTriangle>>> triangulation;
+ Optional<PolyMeshOrig> orig;
+};
+
+PolyMesh boolean(PolyMesh &pm, int bool_optype, int nshapes, std::function<int(int)> shape_fn);
+
+} // namespace meshintersect
+} // namespace blender
+
#endif
#endif /* __BLI_BOOLEAN_H__ */
diff --git a/source/blender/blenlib/BLI_delaunay_2d.h b/source/blender/blenlib/BLI_delaunay_2d.h
index 51820247e50..34722982022 100644
--- a/source/blender/blenlib/BLI_delaunay_2d.h
+++ b/source/blender/blenlib/BLI_delaunay_2d.h
@@ -218,7 +218,9 @@ void BLI_delaunay_2d_cdt_free(CDT_result *result);
# include "BLI_vector.hh"
namespace blender {
+namespace 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;
@@ -228,6 +230,151 @@ template<> struct vec2_impl<mpq_class> {
};
template<typename Arith_t> using vec2 = typename vec2_impl<Arith_t>::type;
+/* Define a templated 2D arrangment of vertices, edges, and faces.
+ * The SymEdge data structure is the basis for a structure that allows
+ * easy traversal to neighboring (by toplogy) geometric elements.
+ * Each of CDTVert, CDTEdge, and CDTFace have an input_id linked list,
+ * whose nodes contain integers that keep track of which input verts, edges,
+ * and faces, respectively, that the element was derived from.
+ *
+ * While this could be cleaned up some, it is usable by other routines in Blender
+ * that need to keep track of a 2D arrangement, with topology.
+ */
+template<typename Arith_t> class CDTVert;
+template<typename Arith_t> class CDTEdge;
+template<typename Arith_t> class CDTFace;
+
+template<typename Arith_t> class SymEdge {
+ public:
+ SymEdge<Arith_t> *next{nullptr}; /* In face, doing CCW traversal of face. */
+ SymEdge<Arith_t> *rot{nullptr}; /* CCW around vert. */
+ CDTVert<Arith_t> *vert{nullptr}; /* Vert at origin. */
+ CDTEdge<Arith_t> *edge{nullptr}; /* Undirected edge this is for. */
+ CDTFace<Arith_t> *face{nullptr}; /* Face on left side. */
+
+ SymEdge() = default;
+};
+
+/* Return other SymEdge for same CDTEdge as se. */
+template<typename T> inline SymEdge<T> *sym(const SymEdge<T> *se)
+{
+ return se->next->rot;
+}
+
+/* Return SymEdge whose next is se. */
+template<typename T> inline SymEdge<T> *prev(const SymEdge<T> *se)
+{
+ return se->rot->next->rot;
+}
+
+template<typename Arith_t> class CDTVert {
+ public:
+ vec2<Arith_t> co; /* Coordinate. */
+ SymEdge<Arith_t> *symedge{nullptr}; /* Some edge attached to it. */
+ LinkNode *input_ids{nullptr}; /* List of corresponding vertex input ids. */
+ int index{-1}; /* Index into array that CDTArrangement keeps. */
+ int merge_to_index{-1}; /* Index of a CDTVert that this has merged to. -1 if no merge. */
+ int visit_index{0}; /* Used by algorithms operating on CDT structures. */
+
+ CDTVert() = default;
+ explicit CDTVert(const vec2<Arith_t> &pt);
+};
+
+template<typename Arith_t> class CDTEdge {
+ public:
+ LinkNode *input_ids{nullptr}; /* List of input edge ids that this is part of. */
+ SymEdge<Arith_t> symedges[2]{SymEdge<Arith_t>(),
+ SymEdge<Arith_t>()}; /* The directed edges for this edge. */
+
+ CDTEdge() = default;
+};
+
+template<typename Arith_t> class CDTFace {
+ public:
+ SymEdge<Arith_t> *symedge{
+ nullptr}; /* A symedge in face; only used during output, so only valid then. */
+ LinkNode *input_ids{nullptr}; /* List of input face ids that this is part of. */
+ int visit_index{0}; /* Used by algorithms operating on CDT structures. */
+ bool deleted{false}; /* Marks this face no longer used. */
+
+ CDTFace() = default;
+};
+
+template<typename Arith_t> class CDTArrangement {
+ public:
+ /* The arrangement owns the memory pointed to by the pointers in these vectors.
+ * They are pointers instead of actual structures because these vectors may be resized and
+ * other elements refer to the elements by pointer.
+ */
+ Vector<CDTVert<Arith_t> *>
+ verts; /* The verts. Some may be merged to others (see their merge_to_index). */
+ Vector<CDTEdge<Arith_t> *>
+ edges; /* The edges. Some may be deleted (SymEdge next and rot pointers are null). */
+ Vector<CDTFace<Arith_t> *> faces; /* The faces. Some may be deleted (see their delete member). */
+ CDTFace<Arith_t> *outer_face{nullptr}; /* Which CDTFace is the outer face. */
+
+ CDTArrangement() = default;
+ ~CDTArrangement();
+
+ /* Hint to how much space to reserve in the Vectors of the arrangement, based on these counts of
+ * input elements. */
+ void reserve(int num_verts, int num_edges, int num_faces);
+
+ /* Add a new vertex to the arrangement, with the given 2D coordinate. It will not be connected to
+ * anything yet. */
+ CDTVert<Arith_t> *add_vert(const vec2<Arith_t> &pt);
+
+ /* Add an edge from v1 to v2. The edge will have a left face and a right face, specified by fleft
+ * and fright. The edge will not be connected to anything yet. If the vertices do not yet have a
+ * symedge pointer, their pointer is set to the symedge in this new edge.
+ */
+ CDTEdge<Arith_t> *add_edge(CDTVert<Arith_t> *v1,
+ CDTVert<Arith_t> *v2,
+ CDTFace<Arith_t> *fleft,
+ CDTFace<Arith_t> *fright);
+
+ /* Add a new face. It is disconnected until an add_edge makes it the left or right face of an
+ * edge. */
+ CDTFace<Arith_t> *add_face();
+
+ /* Make a new edge from v to se->vert, splicing it in. */
+ CDTEdge<Arith_t> *add_vert_to_symedge_edge(CDTVert<Arith_t> *v, SymEdge<Arith_t> *se);
+
+ /* Assuming s1 and s2 are both SymEdges in a face with > 3 sides and one is not the next of the
+ * other, Add an edge from s1->v to s2->v, splitting the face in two. The original face will be
+ * the one that s1 has as left face, and a new face will be added and made s2 and its
+ * next-cycle's left face.
+ */
+ CDTEdge<Arith_t> *add_diagonal(SymEdge<Arith_t> *s1, SymEdge<Arith_t> *s2);
+
+ /* Connect the verts of se1 and se2, assuming that currently those two SymEdges are on teh outer
+ * boundary (have face == outer_face) of two components that are isolated from each other.
+ */
+ CDTEdge<Arith_t> *connect_separate_parts(SymEdge<Arith_t> *se1, SymEdge<Arith_t> *se2);
+
+ /* Split se at fraction lambda, and return the new CDTEdge that is the new second half.
+ * Copy the edge input_ids into the new one.
+ */
+ CDTEdge<Arith_t> *split_edge(SymEdge<Arith_t> *se, Arith_t lambda);
+
+ /* Delete an edge. The new combined face on either side of the deleted edge will be the one that
+ * was e's face. There will now be an unused face, which will be marked deleted, and an unused
+ * CDTEdge, marked by setting the next and rot pointers of its SymEdges to nullptr.
+ */
+ void delete_edge(SymEdge<Arith_t> *se);
+
+ /* If the vertex with index i in the vert array has not been merge, return it.
+ * Else return the one that it has merged to. */
+ CDTVert<Arith_t> *get_vert_resolve_merge(int i)
+ {
+ CDTVert<Arith_t> *v = this->verts[i];
+ if (v->merge_to_index != -1) {
+ v = this->verts[v->merge_to_index];
+ }
+ return v;
+ }
+};
+
template<typename Arith_t> class CDT_input {
public:
Array<vec2<Arith_t>> vert;
@@ -252,6 +399,7 @@ CDT_result<double> delaunay_2d_calc(const CDT_input<double> &input, CDT_output_t
CDT_result<mpq_class> delaunay_2d_calc(const CDT_input<mpq_class> &input,
CDT_output_type output_type);
+} /* namespace meshintersect */
} /* namespace blender */
#endif /* __cplusplus */
diff --git a/source/blender/blenlib/intern/boolean.cc b/source/blender/blenlib/intern/boolean.cc
index 4920df768af..15d3f8037c3 100644
--- a/source/blender/blenlib/intern/boolean.cc
+++ b/source/blender/blenlib/intern/boolean.cc
@@ -26,6 +26,7 @@
#include "BLI_math.h"
#include "BLI_mesh_intersect.hh"
#include "BLI_mpq3.hh"
+#include "BLI_optional.hh"
#include "BLI_set.hh"
#include "BLI_span.hh"
#include "BLI_stack.hh"
@@ -1238,13 +1239,47 @@ static TriMesh binary_boolean(const TriMesh &tm_in_a, const TriMesh &tm_in_b, in
return nary_boolean(tm_in, bool_optype, 2, shape_fn);
}
+/* Will add triangulation if it isn't already there. */
+static TriMesh trimesh_from_polymesh(PolyMesh &pm)
+{
+ TriMesh ans;
+ ans.vert = pm.vert;
+ if (pm.triangulation.has_value()) {
+ const Array<Array<IndexedTriangle>> &tri_arrays = pm.
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list