Page MenuHome

freezes when entering edit mode with active geometry nodes
Closed, ResolvedPublic

Description

System Information
Operating system: Linux-5.4.108-1-MANJARO-x86_64-with-glibc2.33 64 Bits
Graphics card: GeForce GTX 660/PCIe/SSE2 NVIDIA Corporation 4.5.0 NVIDIA 460.67

Blender Version
Broken: version: 2.93.0 Beta, branch: master, commit date: 2021-04-15 17:14, hash: rBfa8d566c3b12
Worked: (newest version of Blender that worked as expected)

Short description of error
the program hangs when entering edit mode with active geometry nodes.

If you turn off the visibility of the modifier, then the problem disappears.

Exact steps for others to reproduce the error
[Based on the default startup or an attached .blend file (as simple as possible)]

Revisions and Commits

Event Timeline

Looks like there is an O(n^2) algorithm in the boolean code. The issue seems to be that many faces are on the same plane.
Note, the file from the original report might not show the issue anymore, because there was another bug that was fixed in rB1266df87c86067d7c2d18ef71dd0e5520de1a382.

Here is a more simplified file:

Adding some prints shows the quadratic behavior:

diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index ce3a5b55f98..f64519cb24f 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -1852,6 +1852,7 @@ static IMesh extract_subdivided_tri(const CDT_data &cd,
 {
   const CDT_result<mpq_class> &cdt_out = cd.cdt_out;
   int t_in_cdt = -1;
+  std::cout << "a: " << cd.input_face.size() << "\n";
   for (int i = 0; i < cd.input_face.size(); ++i) {
     if (cd.input_face[i] == t) {
       t_in_cdt = i;
@@ -1865,6 +1866,7 @@ static IMesh extract_subdivided_tri(const CDT_data &cd,
   int t_orig = in_tm.face(t)->orig;
   constexpr int inline_buf_size = 20;
   Vector<Face *, inline_buf_size> faces;
+  std::cout << "b: " << cdt_out.face.size() << "\n";
   for (int f : cdt_out.face.index_range()) {
     if (cdt_out.face_orig[f].contains(t_in_cdt)) {
       BLI_assert(cdt_out.face[f].size() == 3);
@@ -2638,6 +2640,7 @@ IMesh trimesh_nary_intersect(const IMesh &tm_in,
 #  endif
   for (int t : tm_clean->face_index_range()) {
     int c = clinfo.tri_cluster(t);
+    std::cout << t << "\n";
     if (c != NO_INDEX) {
       BLI_assert(tri_subdivided[t].face_size() == 0);
       tri_subdivided[t] = extract_subdivided_tri(cluster_subdivided[c], *tm_clean, t, arena);

The output ends with

507
a: 512
b: 512
508
a: 512
b: 512
509
a: 512
b: 512
510
a: 512
b: 512
511
a: 512
b: 512

This might also be related to T87505.

I will remove this quadratic behavior.