[Bf-blender-cvs] [74c56382b88] newboolean: A large refactor of newboolean to perpare for performance tuning.
Howard Trickey
noreply at git.blender.org
Sun Jul 12 22:32:14 CEST 2020
Commit: 74c56382b888bd39a0268e200d3fc99ee6c6bd0f
Author: Howard Trickey
Date: Sun Jul 12 16:27:57 2020 -0400
Branches: newboolean
https://developer.blender.org/rB74c56382b888bd39a0268e200d3fc99ee6c6bd0f
A large refactor of newboolean to perpare for performance tuning.
Many changes aimed at, broadly, more sharing and less copying;
and having coordinates stored simultaneously in double and multiprecision,
as that will be needed for floating predicate filtering.
Biggest change is that faces are represented by arrays of pointers to
Verts instead of as integer indices into a vertex array.
===================================================================
M source/blender/blenlib/BLI_boolean.hh
M source/blender/blenlib/BLI_delaunay_2d.h
M source/blender/blenlib/BLI_mesh_intersect.hh
M source/blender/blenlib/BLI_mpq3.hh
M source/blender/blenlib/intern/boolean.cc
M source/blender/blenlib/intern/delaunay_2d.cc
M source/blender/blenlib/intern/math_vec.cc
M source/blender/blenlib/intern/mesh_intersect.cc
M source/blender/bmesh/tools/bmesh_boolean.cc
M tests/gtests/blenlib/BLI_boolean_test.cc
M tests/gtests/blenlib/BLI_delaunay_2d_test.cc
M tests/gtests/blenlib/BLI_mesh_intersect_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_boolean.hh b/source/blender/blenlib/BLI_boolean.hh
index 487a35c55c2..58b252b8e95 100644
--- a/source/blender/blenlib/BLI_boolean.hh
+++ b/source/blender/blenlib/BLI_boolean.hh
@@ -21,10 +21,8 @@
* \ingroup bli
*/
-#include "BLI_array.hh"
-#include "BLI_math_mpq.hh"
#include "BLI_mesh_intersect.hh"
-#include "BLI_mpq3.hh"
+#include <functional>
namespace blender::meshintersect {
@@ -38,32 +36,31 @@ enum bool_optype {
BOOLEAN_DIFFERENCE = 2,
};
-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;
- /* triangulation can have zero length: then boolean will do it. */
- Array<Array<IndexedTriangle>> triangulation;
- /* orig can be dummy for boolean input, but has useful information for its output. */
- PolyMeshOrig orig;
-};
-
-PolyMesh boolean(PolyMesh &pm, bool_optype op, int nshapes, std::function<int(int)> shape_fn);
-
-TriMesh boolean_trimesh(const TriMesh &tm,
- bool_optype op,
- int nshapes,
- std::function<int(int)> shape_fn);
+/* Do the boolean operation op on the mesh pm_in.
+ * The boolean operation has nshapes input shapes. Each is a disjoint subset of the input mesh.
+ * The shape_fn argument, when applied to an input face argument, says which shape it is in
+ * (should be a value from -1 to nshapes - 1: if -1, it is not part of any shape).
+ * Sometimes the caller has already done a triangulation of the faces,
+ * and if so, *pm_triangulated contains a triangulation: if non-null, it contains a mesh
+ * of triangles, each of whose orig_field says which face in pm that triangle belongs to.
+ * pm arg isn't const because we may populate its verts (for debugging).
+ * Same goes for the pm_triangulated arg.
+ * The output Mesh will have faces whose orig fields map back to faces and edges in
+ * the input mesh.
+ */
+Mesh boolean_mesh(Mesh &pm,
+ bool_optype op,
+ int nshapes,
+ std::function<int(int)> shape_fn,
+ Mesh *pm_triangulated,
+ MArena *arena);
-void write_obj_polymesh(const Array<mpq3> &vert,
- const Array<Array<int>> &face,
- const std::string &objname);
+/* This is like boolean, but operates on Mesh's whose faces are all triangles.
+ * It is exposed mainly for unit testing, at the moment: boolean_mesh() uses
+ * it to do most of its work.
+ */
+Mesh boolean_trimesh(
+ Mesh &tm, bool_optype op, int nshapes, std::function<int(int)> shape_fn, MArena *arena);
} // namespace blender::meshintersect
-
#endif /* __BLI_BOOLEAN_HH__ */
diff --git a/source/blender/blenlib/BLI_delaunay_2d.h b/source/blender/blenlib/BLI_delaunay_2d.h
index 818b9b74cd7..edbb7cc692d 100644
--- a/source/blender/blenlib/BLI_delaunay_2d.h
+++ b/source/blender/blenlib/BLI_delaunay_2d.h
@@ -148,12 +148,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;
@@ -239,9 +236,20 @@ template<typename Arith_t> class CDT_result {
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;
};
diff --git a/source/blender/blenlib/BLI_mesh_intersect.hh b/source/blender/blenlib/BLI_mesh_intersect.hh
index d1d11401195..8f6ccdf1709 100644
--- a/source/blender/blenlib/BLI_mesh_intersect.hh
+++ b/source/blender/blenlib/BLI_mesh_intersect.hh
@@ -26,91 +26,318 @@
#include <iostream>
#include "BLI_array.hh"
+#include "BLI_double3.hh"
+#include "BLI_index_range.hh"
+#include "BLI_map.hh"
#include "BLI_math_mpq.hh"
#include "BLI_mpq3.hh"
+#include "BLI_span.hh"
#include "BLI_vector.hh"
namespace blender::meshintersect {
-/* The indices are for vertices in some external space of coordinates.
- * The "orig" component is used to track how a triangle originally came
- * from some other space of triangle indices. Which we usually need,
- * and it packs nicely into this structure, so keeping it here will save
- * memory.
+constexpr int NO_INDEX = -1;
+constexpr uint NO_INDEX_U = UINT_MAX;
+
+/* Vertex coordinates are stored both as double3 and mpq3, which should agree.
+ * Most calculations are done in exact arithmetic, using the mpq3 version,
+ * but some predicates can be sped up by operating on doubles and using error analysis
+ * to find the cases where that is good enough.
+ * Vertices also carry along an id, created on allocation. The id
+ * is useful for making algorithms that don't depend on pointers.
+ * Also, they are easier to read while debugging.
+ * They also carry an orig index, which can be used to tie them back to
+ * vertices that tha caller may have in a different way (e.g., BMVerts).
+ * An orig index can be NO_INDEX, indicating the Vert was created by
+ * the algorithm and doesn't match an original Vert.
+ * Vertices can be reliably compared for equality,
+ * and hashed (on their co_exact field).
*/
-class IndexedTriangle {
- int v_[3]{-1, -1, -1};
- int orig_{-1};
+struct Vert {
+ mpq3 co_exact;
+ double3 co;
+ int id = NO_INDEX;
+ int orig = NO_INDEX;
- public:
- IndexedTriangle() = default;
- IndexedTriangle(int v0, int v1, int v2, int orig) : v_{v0, v1, v2}, orig_{orig}
+ Vert() = default;
+ Vert(const mpq3 &mco, const double3 &dco, int id, int orig);
+ Vert(const Vert &other);
+ Vert(Vert &&other) noexcept;
+
+ ~Vert() = default;
+
+ Vert &operator=(const Vert &other);
+ Vert &operator=(Vert &&other) noexcept;
+
+ /* Test equality on the co_exact field. */
+ bool operator==(const Vert &other) const;
+
+ /* Hash on the co_exact field. */
+ uint32_t hash() const;
+};
+
+/* Use Vertp for Verts everywhere: can modify the pointer
+ * but not the underlying Vert, which should stay constant
+ * after creation.
+ */
+using Vertp = const Vert *;
+
+std::ostream &operator<<(std::ostream &os, Vertp v);
+
+/* A Plane whose equation is dot(nprm, p) + d = 0. */
+struct Plane {
+ mpq3 norm_exact;
+ mpq_class d_exact;
+ double3 norm;
+ double d;
+
+ Plane() = default;
+ Plane(const mpq3 &norm_exact, const mpq_class &d_exact);
+
+ /* Test equality on the exact fields. */
+ bool operator==(const Plane &other) const;
+
+ /* Hash onthe exact fields. */
+ uint32_t hash() const;
+
+ void make_canonical();
+};
+
+std::ostream &operator<<(std::ostream &os, const Plane &plane);
+
+/* A Face has a sequence of Verts that for a CCW ordering around them.
+ * Faces carry an index, created at allocation time, useful for making
+ * pointer-indenpendent algorithms, and for debugging.
+ * They also carry an original index, meaningful to the caller.
+ * And they carry original edge indices too: each is a number meaningful
+ * to the caller for the edge starting from the corresponding face position.
+ * A "face position" is the index of a vertex around a face.
+ * Faces don't own the memory pointed at by the vert array.
+ * Since the intersect algorithm needs the plane for each face,
+ * a Face also stores the Plane of the face.
+ */
+struct Face {
+ Array<Vertp> vert;
+ Array<int> edge_orig;
+ Plane plane;
+ int id = NO_INDEX;
+ int orig = NO_INDEX;
+
+ using FacePos = uint;
+
+ Face() = default;
+ Face(Span<Vertp> verts, int id, int orig, Span<int> edge_origs);
+ Face(const Face &other);
+ Face(Face &&other) noexcept;
+
+ ~Face() = default;
+
+ Face &operator=(const Face &other);
+ Face &operator=(Face &&other) noexcept;
+
+ bool is_tri() const
{
+ return vert.size() == 3;
}
- int v0() const
+ /* Test equality of verts, in same positions. */
+ bool operator==(const Face &other) const;
+
+ /* Test equaliy faces allowing cyclic shifts. */
+ bool cyclic_equal(const Face &other) const;
+
+ FacePos next_pos(FacePos p) const
{
- return v_[0];
+ return (p + 1) % vert.size();
}
- int v1() const
+
+ FacePos prev_pos(FacePos p) const
{
- return v_[1];
+ return (p + vert.size() - 1) % vert.size();
}
- int v2() const
+
+ const Vertp &operator[](uint index) const
{
- return v_[2];
+ return vert[index];
}
- int orig() const
+
+ uint size() const
{
- return orig_;
+ return vert.size();
}
- int operator[](int i) const
+
+ const Vertp *begin() const
{
- return v_[i];
+ return vert.begin();
}
- int &operator[](int i)
+
+ const Vertp *end() const
{
- return v_[i];
+ return vert.end();
}
- bool operator==(const IndexedTriangle &other)
+
+ IndexRange index_range() const
{
- /* Let equality happen with any cyclic ordering difference, but not orientation difference. */
- return (((v_[0] == other.v_[0] && v_[1] == other.v_[1] && v_[2] == other.v_[2]) ||
-
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list