freezes when entering edit mode with active geometry nodes #87554

New Issue

kaiwas · 2021-04-16T09:19:02+02:00

kaiwas commented

2021-04-16 09:19:02 +02:00

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: fa8d566c3b
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)]

bug2.blend

**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: `fa8d566c3b` 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. ![Peek 2021-04-16 10-10.gif](https://archive.blender.org/developer/F9935625/Peek_2021-04-16_10-10.gif) **Exact steps for others to reproduce the error** [Based on the default startup or an attached .blend file (as simple as possible)] [bug2.blend](https://archive.blender.org/developer/F9935627/bug2.blend)

kaiwas commented

2021-04-16 09:19:02 +02:00

Added subscriber: @kaiwas

Jacques Lucke commented

2021-04-16 13:27:15 +02:00

Added subscribers: @howardt, @JacquesLucke

Jacques Lucke commented

2021-04-16 13:27:16 +02:00

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 1266df87c8.

Here is a more simplified file:
boolean_quadratic.blend

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 #87505.

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 1266df87c8. Here is a more simplified file: [boolean_quadratic.blend](https://archive.blender.org/developer/F9935822/boolean_quadratic.blend) ![image.png](https://archive.blender.org/developer/F9935823/image.png) 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 #87505.

Howard Trickey self-assigned this 2021-04-30 15:54:58 +02:00

Howard Trickey commented

2021-04-30 15:54:58 +02:00

I will remove this quadratic behavior.

blender-admin commented

2021-05-02 22:37:05 +02:00

This issue was referenced by 28bf1d4037

This issue was referenced by 28bf1d4037496397e3bc5d69ce51d8ac9b8a2738

Howard Trickey commented

2021-05-02 22:40:11 +02:00

Changed status from 'Needs Triage' to: 'Resolved'

Howard Trickey closed this issue

2021-05-02 22:40:11 +02:00

Sign in to join this conversation.

No Label

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

freezes when entering edit mode with active geometry nodes #87554