[Bf-blender-cvs] [833514b2cef] newboolean: Work in progress to treat nary boolean differently.
Howard Trickey
noreply at git.blender.org
Mon Jul 20 11:29:38 CEST 2020
Commit: 833514b2cefc9c18234d6daf29c6974426405886
Author: Howard Trickey
Date: Mon Jul 20 05:28:42 2020 -0400
Branches: newboolean
https://developer.blender.org/rB833514b2cefc9c18234d6daf29c6974426405886
Work in progress to treat nary boolean differently.
This will make it faster. There's one bug in it still,
but committing progress.
===================================================================
M source/blender/blenlib/BLI_boolean.hh
M source/blender/blenlib/BLI_mesh_intersect.hh
M source/blender/blenlib/intern/boolean.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_mesh_intersect_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_boolean.hh b/source/blender/blenlib/BLI_boolean.hh
index 58b252b8e95..13fffcee634 100644
--- a/source/blender/blenlib/BLI_boolean.hh
+++ b/source/blender/blenlib/BLI_boolean.hh
@@ -40,6 +40,8 @@ enum bool_optype {
* 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).
+ * The use_self arg says whether or not the function should assume that faces in the
+ * same shape intersect - if the argument is true, such self-intersections will be found.
* 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.
@@ -52,6 +54,7 @@ Mesh boolean_mesh(Mesh &pm,
bool_optype op,
int nshapes,
std::function<int(int)> shape_fn,
+ bool use_self,
Mesh *pm_triangulated,
MArena *arena);
@@ -59,8 +62,12 @@ Mesh boolean_mesh(Mesh &pm,
* 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);
+Mesh boolean_trimesh(Mesh &tm,
+ bool_optype op,
+ int nshapes,
+ std::function<int(int)> shape_fn,
+ bool use_self,
+ MArena *arena);
} // namespace blender::meshintersect
#endif /* __BLI_BOOLEAN_HH__ */
diff --git a/source/blender/blenlib/BLI_mesh_intersect.hh b/source/blender/blenlib/BLI_mesh_intersect.hh
index 8f6ccdf1709..72ea71a0879 100644
--- a/source/blender/blenlib/BLI_mesh_intersect.hh
+++ b/source/blender/blenlib/BLI_mesh_intersect.hh
@@ -336,6 +336,12 @@ std::ostream &operator<<(std::ostream &os, const Mesh &mesh);
*/
Mesh trimesh_self_intersect(const Mesh &tm_in, MArena *arena);
+Mesh trimesh_nary_intersect(const Mesh &tm_in,
+ int nshapes,
+ std::function<int(int)> shape_fn,
+ bool use_self,
+ MArena *arena);
+
/* This has the side effect of populating verts in the Mesh. */
void write_obj_mesh(Mesh &m, const std::string &objname);
diff --git a/source/blender/blenlib/intern/boolean.cc b/source/blender/blenlib/intern/boolean.cc
index 4f325947e62..6916bb67c57 100644
--- a/source/blender/blenlib/intern/boolean.cc
+++ b/source/blender/blenlib/intern/boolean.cc
@@ -1976,21 +1976,32 @@ static Mesh polymesh_from_trimesh_with_dissolve(const Mesh &tm_out,
* The shape_fn function should take a triangle index in tm_in and return
* a number in the range 0 to nshapes-1, to say which shape that triangle is in.
*/
-Mesh boolean_trimesh(
- Mesh &tm_in, bool_optype op, int nshapes, std::function<int(int)> shape_fn, MArena *arena)
+Mesh boolean_trimesh(Mesh &tm_in,
+ bool_optype op,
+ int nshapes,
+ std::function<int(int)> shape_fn,
+ bool use_self,
+ MArena *arena)
{
- constexpr int dbg_level = 0;
+ constexpr int dbg_level = 2;
if (dbg_level > 0) {
std::cout << "BOOLEAN of " << nshapes << " operand" << (nshapes == 1 ? "" : "s")
<< " op=" << bool_optype_name(op) << "\n";
if (dbg_level > 1) {
std::cout << "boolean_trimesh input:\n" << tm_in;
+ write_obj_mesh(tm_in, "boolean_in");
}
}
if (tm_in.face_size() == 0) {
return Mesh(tm_in);
}
- Mesh tm_si = trimesh_self_intersect(tm_in, arena);
+ Mesh tm_si;
+ if (use_self) {
+ tm_si = trimesh_self_intersect(tm_in, arena);
+ }
+ else {
+ tm_si = trimesh_nary_intersect(tm_in, nshapes, shape_fn, use_self, arena);
+ }
if (dbg_level > 1) {
write_obj_mesh(tm_si, "boolean_tm_si");
std::cout << "\nboolean_tm_input after intersection:\n" << tm_si;
@@ -2036,6 +2047,7 @@ Mesh boolean_mesh(Mesh &pm,
bool_optype op,
int nshapes,
std::function<int(int)> shape_fn,
+ bool use_self,
Mesh *pm_triangulated,
MArena *arena)
{
@@ -2045,7 +2057,7 @@ Mesh boolean_mesh(Mesh &pm,
our_triangulation = triangulate_polymesh(pm, arena);
tm_in = &our_triangulation;
}
- Mesh tm_out = boolean_trimesh(*tm_in, op, nshapes, shape_fn, arena);
+ Mesh tm_out = boolean_trimesh(*tm_in, op, nshapes, shape_fn, use_self, arena);
Mesh ans = polymesh_from_trimesh_with_dissolve(tm_out, pm, arena);
return ans;
}
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index c4befd32f5c..715c6db2fa0 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -2142,6 +2142,124 @@ static bool bvhtreeverlap_cmp(const BVHTreeOverlap &a, const BVHTreeOverlap &b)
}
return false;
}
+class TriOverlaps {
+ BVHTree *tree_{nullptr};
+ BVHTree *tree_b_{nullptr};
+ BVHTreeOverlap *overlap_{nullptr};
+ uint overlap_tot_{0};
+
+ struct CBData {
+ const Mesh &tm;
+ std::function<int(int)> shape_fn;
+ int nshapes;
+ bool use_self;
+ };
+
+ public:
+ TriOverlaps(const Mesh &tm,
+ const Array<BoundingBox> &tri_bb,
+ int nshapes,
+ std::function<int(int)> shape_fn,
+ bool use_self)
+ {
+ constexpr int dbg_level = 1;
+ if (dbg_level > 0) {
+ std::cout << "TriOverlaps construction\n";
+ }
+ /* Tree type is 8 => octtree; axis = 6 => using XYZ axes only. */
+ tree_ = BLI_bvhtree_new(static_cast<int>(tm.face_size()), FLT_EPSILON, 8, 6);
+ /* In the common case of a binary boolean and no self intersection in
+ * each shape, we will use two trees and simple bounding box overlap.
+ */
+ bool two_trees_no_self = nshapes == 2 && !use_self;
+ if (two_trees_no_self) {
+ tree_b_ = BLI_bvhtree_new(static_cast<int>(tm.face_size()), FLT_EPSILON, 8, 6);
+ }
+ float bbpts[6];
+ for (uint t : tm.face_index_range()) {
+ const BoundingBox &bb = tri_bb[t];
+ copy_v3_v3(bbpts, bb.min);
+ copy_v3_v3(bbpts + 3, bb.max);
+ int shape = shape_fn(tm.face(t)->orig);
+ if (two_trees_no_self) {
+ if (shape == 0) {
+ BLI_bvhtree_insert(tree_, static_cast<int>(t), bbpts, 2);
+ }
+ else if (shape == 1) {
+ BLI_bvhtree_insert(tree_b_, static_cast<int>(t), bbpts, 2);
+ }
+ }
+ else {
+ if (shape != -1) {
+ BLI_bvhtree_insert(tree_, static_cast<int>(t), bbpts, 2);
+ }
+ }
+ }
+ BLI_bvhtree_balance(tree_);
+ if (two_trees_no_self) {
+ BLI_bvhtree_balance(tree_b_);
+ /* Don't expect a lot of trivial intersects in this case. */
+ overlap_ = BLI_bvhtree_overlap(tree_, tree_b_, &overlap_tot_, NULL, NULL);
+ }
+ else {
+ CBData cbdata{tm, shape_fn, nshapes, use_self};
+ if (nshapes == 1 && use_self) {
+ /* Expect a lot of trivial intersects from quads that are triangulated
+ * and faces that share vertices.
+ * Filter them out with a callback.
+ */
+ overlap_ = BLI_bvhtree_overlap(
+ tree_, tree_, &overlap_tot_, only_nontrivial_intersects, &cbdata);
+ }
+ else {
+ overlap_ = BLI_bvhtree_overlap(
+ tree_, tree_, &overlap_tot_, only_different_shapes, &cbdata);
+ }
+ }
+ /* Sort the overlaps to bring all the intersects with a given indexA together. */
+ std::sort(overlap_, overlap_ + overlap_tot_, bvhtreeverlap_cmp);
+ if (dbg_level > 0) {
+ std::cout << overlap_tot_ << " overlaps found:\n";
+ for (BVHTreeOverlap ov : overlap()) {
+ std::cout << "A: " << ov.indexA << ", B: " << ov.indexB << "\n";
+ }
+ }
+ }
+
+ ~TriOverlaps()
+ {
+ if (tree_) {
+ BLI_bvhtree_free(tree_);
+ }
+ if (tree_b_) {
+ BLI_bvhtree_free(tree_b_);
+ }
+ if (overlap_) {
+ MEM_freeN(overlap_);
+ }
+ }
+
+ Span<BVHTreeOverlap> overlap() const
+ {
+ return Span<BVHTreeOverlap>(overlap_, overlap_tot_);
+ }
+
+ private:
+ static bool only_nontrivial_intersects(void *userdata,
+ int index_a,
+ int index_b,
+ int UNUSED(thread))
+ {
+ CBData *cbdata = static_cast<CBData *>(userdata);
+ return may_non_trivially_intersect(cbdata->tm.face(index_a), cbdata->tm.face(index_b));
+ }
+
+ static bool only_different_shapes(void *userdata, int index_a, int index_b, int UNUSED(thread))
+ {
+ CBData *cbdata = static_cast<CBData *>(userdata);
+ return cbdata->tm.face(index_a)->orig != cbdata->tm.face(index_b)->orig;
+ }
+};
/* For each triangle in tm, fill in the corresponding slot in
* r_tri_subdivided with the result of intersecting it with
@@ -2153,25 +2271,16 @@ static bool bvhtreeverlap_cmp(const BVHTreeOverlap &a, const BVHTreeOverlap &b)
static void calc_subdivided_tris(Array<Mesh> &r_tri_subdivided,
const Mesh &tm,
const CoplanarClusterInfo &clinfo,
- BVHTree *tri_tree,
+ const TriOverlaps &ov,
MArena *arena)
{
const int dbg_level = 0;
if (dbg_level > 0) {
std::cout << "\nCALC_SUBDIVIDED_TRIS\n\n";
}
- uint overlap_tot;
- BVHTreeOverlap *overlap = BLI_bvhtree_overlap(tri_tree, tri_tree, &overlap_tot, NULL, NULL);
- if (overlap == nullptr) {
- return;
- }
- if (overlap_tot <= 1) {
- MEM_freeN(overlap);
- return;
- }
- /* Sort the overlaps to bring all the intersects with a given indexA together. */
- std::sort(overlap, overlap + overlap_tot, bvhtreeverl
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list