blender
/
blender
129
397
Fork 571
Code Issues 6.2k Pull Requests 752 Projects 19 Wiki Activity

Boolean: applying patch D11431 to speed up hole-tolerant raycast. 

This patch from Erik Abrahamsson uses a parallel_for to speed up
the case where the input is not manifold and the "hole_tolerant"
option is set.
In a test case on a 24 core (48 thread) machine, this sped up a
the boolean part on an object with 221k triangles from 12.06s to 0.46s.
This commit is contained in:
Howard Trickey 2021-05-30 16:37:49 -04:00
parent e6a69f7653
commit a1556fa05c
Notes: blender-bot 2023-02-14 08:06:35 +01:00 
Referenced by issue #94418, No image.previews for some D.images
Referenced by issue #93995, Cycles: motion blur only applies on Left view
Referenced by issue #93751, Extrude crash
Referenced by issue #90540, NoneType object error with entering grease pencil draw mode
Referenced by issue #89545, Weight / Vertex paint mode "Show Wireframe" is not working
Referenced by issue #89029, Baking to Vertex colors causes Blender shutdown/crash
1 changed files with 52 additions and 36 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

88
source/blender/blenlib/intern/mesh_boolean.cc
View File

@ -41,6 +41,7 @@
# include "BLI_set.hh"
# include "BLI_span.hh"
# include "BLI_stack.hh"
# include "BLI_task.hh"
# include "BLI_vector.hh"
# include "BLI_vector_set.hh"
@ -48,6 +49,10 @@
# include "BLI_mesh_boolean.hh"
# ifdef WITH_TBB
# include "tbb/spin_mutex.h"
# endif
// # define PERFDEBUG
namespace blender::meshintersect {
@ -2567,47 +2572,58 @@ static IMesh raycast_tris_boolean(const IMesh &tm,
BVHTree *tree = raycast_tree(tm);
Vector<Face *> out_faces;
out_faces.reserve(tm.face_size());
Array<float> in_shape(nshapes, 0);
Array<int> winding(nshapes, 0);
for (int t : tm.face_index_range()) {
Face &tri = *tm.face(t);
int shape = shape_fn(tri.orig);
if (dbg_level > 0) {
std::cout << "process triangle " << t << " = " << &tri << "\n";
std::cout << "shape = " << shape << "\n";
}
test_tri_inside_shapes(tm, shape_fn, nshapes, t, tree, in_shape);
for (int other_shape = 0; other_shape < nshapes; ++other_shape) {
if (other_shape == shape) {
continue;
}
/* The in_shape array has a confidence value for "insideness".
* For most operations, even a hint of being inside
* gives good results, but when shape is a cutter in a Difference
* operation, we want to be pretty sure that the point is inside other_shape.
* E.g., T75827.
* Also, when the operation is intersection, we also want high confidence.
*/
bool need_high_confidence = (op == BoolOpType::Difference && shape != 0) ||
op == BoolOpType::Intersect;
bool inside = in_shape[other_shape] >= (need_high_confidence ? 0.5f : 0.1f);
# ifdef WITH_TBB
tbb::spin_mutex mtx;
# endif
const int grainsize = 256;
parallel_for(IndexRange(tm.face_size()), grainsize, [&](IndexRange range) {
Array<float> in_shape(nshapes, 0);
Array<int> winding(nshapes, 0);
for (int t : range) {
Face &tri = *tm.face(t);
int shape = shape_fn(tri.orig);
if (dbg_level > 0) {
std::cout << "test point is " << (inside ? "inside" : "outside") << " other_shape "
<< other_shape << " val = " << in_shape[other_shape] << "\n";
std::cout << "process triangle " << t << " = " << &tri << "\n";
std::cout << "shape = " << shape << "\n";
}
winding[other_shape] = inside;
}
bool do_flip;
bool do_remove = raycast_test_remove(op, winding, shape, &do_flip);
if (!do_remove) {
if (!do_flip) {
out_faces.append(&tri);
test_tri_inside_shapes(tm, shape_fn, nshapes, t, tree, in_shape);
for (int other_shape = 0; other_shape < nshapes; ++other_shape) {
if (other_shape == shape) {
continue;
}
/* The in_shape array has a confidence value for "insideness".
* For most operations, even a hint of being inside
* gives good results, but when shape is a cutter in a Difference
* operation, we want to be pretty sure that the point is inside other_shape.
* E.g., T75827.
* Also, when the operation is intersection, we also want high confidence.
*/
bool need_high_confidence = (op == BoolOpType::Difference && shape != 0) ||
op == BoolOpType::Intersect;
bool inside = in_shape[other_shape] >= (need_high_confidence ? 0.5f : 0.1f);
if (dbg_level > 0) {
std::cout << "test point is " << (inside ? "inside" : "outside") << " other_shape "
<< other_shape << " val = " << in_shape[other_shape] << "\n";
}
winding[other_shape] = inside;
}
else {
raycast_add_flipped(out_faces, tri, arena);
bool do_flip;
bool do_remove = raycast_test_remove(op, winding, shape, &do_flip);
{
# ifdef WITH_TBB
tbb::spin_mutex::scoped_lock lock(mtx);
# endif
if (!do_remove) {
if (!do_flip) {
out_faces.append(&tri);
}
else {
raycast_add_flipped(out_faces, tri, arena);
}
}
}
}
}
});
BLI_bvhtree_free(tree);
ans.set_faces(out_faces);
return ans;