manifold icon indicating copy to clipboard operation
manifold copied to clipboard

accidental quadratic runtime in csg tree

Open pca006132 opened this issue 4 months ago • 13 comments

This causes large_scene_test.cpp to be slow. Because instead of running $n^3$ operations, we are actually having $n^6$ (simple) operations.

This is introduced in https://github.com/elalish/manifold/pull/368. Basically, the problem is that due to eager flattening, repeatedly unioning things will create and drop vectors of length $i$ from 1 to $n$, making the runtime quadratic. We should instead let the csg tree grow, flatten the csg tree when we evaluate it. To avoid stack overflow, we can avoid recursion, manually maintain a stack.

pca006132 avatar Oct 15 '24 16:10 pca006132