manifold
manifold copied to clipboard
accidental quadratic runtime in csg tree
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.