accidental quadratic runtime in csg tree

[pca006132]

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

[elalish]

Interesting! Good catch.

[starseeker]

@pca006132 is this manifesting only with the linalg conversion in place? Doing my initial tests with that version in BRL-CAD, I'm seeing an enormous slowdown of the logic where we do booleans on shapes representing each triangle of a mesh to perform offsetting. I've not filed an issue yet since I've got multiple things in play, but I've somehow managed to have a problem that was previously ~3 seconds to calculate jump to taking many minutes.

[pca006132]

It should not be related to linalg. If you can reduce to simpler example or purely manifold example, just file an issue.

[pca006132]

@pca006132 is this manifesting only with the linalg conversion in place? Doing my initial tests with that version in BRL-CAD, I'm seeing an enormous slowdown of the logic where we do booleans on shapes representing each triangle of a mesh to perform offsetting. I've not filed an issue yet since I've got multiple things in play, but I've somehow managed to have a problem that was previously ~3 seconds to calculate jump to taking many minutes.

Thinking about it, are you comparing against a version before the double precision PR? It may be caused by mesh simplification. Basically, previously we were doing very aggressive mesh simplification due to the epsilon value being quite large (1e-6 times the maximum absolute value of coordinates, roughly speaking). However, after the double precision PR, the epsilon was drastically reduced, so we can only do less mesh simplification.

This is also an issue in openscad as well, but we don't think it is something manifold can fix, because we cannot arbitrarily increase the epsilon value or things will become imprecise later. Users should try to do remeshing based on their target tolerance value, which should be much larger than epsilon (epsilon is the tolerance value that we hope to guarantee, considering imprecision in floating point arithmetic, so this should be as small as possible). We may expose our simplification function, but that one is aiming for fast simplification, so it is not trying too hard.

[starseeker]

Yes, the previous version was before the double precision PR.

[starseeker]

If that is the issue, it might be quite helpful to expose the simplification function so we can try to recreate (at least functionally) the previous behavior. At least at the moment, BRL-CAD's native remeshing capabilities are very rudimentary.

[starseeker]

I'm a little suspicious though of that being the (only) issue in this case - the mesh I'm using as a basis for the current test has only 266 faces, 401 edges and 157 vertices. That multiplies a fair bit when they are represented by arbs, cylinders and spheres, but even so I wouldn't think there should be enough data to warrant the unioning process taking minutes...

[pca006132]

Yeah, this sounds like having multiple issues at play. For this issue in particular, the quadratic behavior is that the following code:

Manifold m;
for (auto part : parts)
  m += part;

will be a lot slower than

Manifold m = Manifold::BatchBoolean(parts, OpType::Add)

Maybe you can see if you are hitting this as well.

[elalish]

Yes, it would be very helpful if you can send us a PR adding a TEST that shows this issue. Also, can you point to what version/commit it was working properly fast on? I'm thinking of adding a SetPrecision method, either as a member or global, but I'll need that test to verify that's a good approach.

[pca006132]

I don't think users really want to set precision in this case. E.g. if they set a certain precision, scale it up, and union with some other object, now the other object will get remeshed as well with a larger precision value, which is usually not intended. I think they typically want a fixed precision that is independent of transformations.

[pca006132]

That said, that tolerance value can be useful to our API. E.g. users can set it to their model, and we perform simplification according to that. If we found that the epsilon we use internally is larger than this tolerance, we can let the user know that things are going imprecise.

[starseeker]

I'm working on recreating (more or less) what I'm doing in purely Manifold terms to try and serve as a performance test, although I don't know if it'll make sense as a standard Manifold test - we'll have to see. I think between Sphere, Cylinder and Extrude I might just be able to recast what I'm doing in terms of only Manifold types, but we'll see - maybe I'll accidentally wind up creating a crude Manifold::Offset in the process ;-)

We were on a rather older version - I think a patched version of 2.4.5, although I can try to narrow it down more once I've got a more isolated definition of the problem. I switched up a lot of stuff simultaneously - Mesh -> MeshGL64, float -> double, and a lot of changes, so if I need to bisect I need a simpler reproduction myself than complete BRL-CAD build cycles.

[pca006132]

You can just export a few meshes, no need to force yourself to work with those primitives we provide :)

And I don't think we need to check which version introduced such a performance regression before opening an issue. If it can be made faster, it is fine to have it as an issue.

Btw I think we are discussing too much here, maybe we should open another issue/discussion for this one.