Performance regression with many multiple sequential union operations

[starseeker]

In BRL-CAD, we convert an implicit volume mesh to an explicit volume the "hard way" by representing each mesh element as a shape and unioning them together. It's a brute force approach, but with Manifold's booleans it has proven able to handle simple shapes reasonably well.

With the latest code (started testing after linalg change, but delta also includes MeshGL64 and double precision changes) a problem that was taking ~3 seconds to process with v2.4.5 is now taking a couple of minutes, and considerably longer if the build isn't compiled optimized.

I'm working on making a more isolated encapsulation of the issue to try and help narrow down what's going on - discussion in #989 got to the point were we needed another issue, so setting this up. As I get more info, will update here.

[starseeker]

OK, first progress at setting up a self contained reproduction of what we're doing:

starseeker@592b51e

It's using the new APIs, so it'll have to be back ported to properly get a sense of how it behaves with older codes in this form. The triangle count does end up higher than I expected, so that could very well be what's going on - I think it peaked out at about 600k.

[starseeker]

Oh, wow. Yeah, that's gotta be it. A quick-and-dirty back-port to the v2.4.5 code shows a peak triangle count of just shy of 11k.

Hrm. If the simplification function is exposed, could I apply that between iterations with a tolerance closer to the old version, maybe?

[elalish]

Take a look at the discussion this issue started: #994. We're looking at exactly that kind of API - feedback welcome.

[starseeker]

Did you want this in some form or other as a pull request? I wasn't sure it was suitable, since it was basically the shortest path for me to be (reasonably) sure I was reproducing my specific issue.... I doubt it can be a normal test though, since it's ultimately timing based, so if you do want it in some form please advise what would be best.

[elalish]

This is perfect as a test - you can add it to boolean_complex_test.cpp. You'll see others in there that also import meshes - follow their example. You can simply add a surface area and volume check to serve as a regression test of correctness. GTest tells us how long each test takes to run, and we tend to pay a fair bit of attention when something gets much slower. I ask that you size it so it takes no more than a few seconds when running properly; we'll notice anything that adds a couple of seconds to the overall runtime of the tests, so that'll serve as the performance regression test.

Please just simplify it as much as you can, e.g. use Manifold::Cylinder instead of your own function.

[starseeker]

@elalish I'll give it a go. I may need a little help with the Cylinder part - I messed up the math a couple times trying to place them before punting and reproducing my other construction logic. I think to use the Cylinder API I need to construct the cylinder itself at the origin in the z direction, create a rotation matrix to orient it, and then create a translate to move it to the correct position in space?

[elalish]

I did something very similar awhile back, which might help: https://github.com/elalish/manifold/pull/668/files#r1803936252

[starseeker]

Oh, that reminds me - since my C++ chops are a little weak, I wanted to ask about this method of adding to the arrays:

m.triVerts.insert(m.triVerts.end() ...

Naively I would have done m.push_back for that - is there a performance advantage to using insert?

[elalish]

But if it's a pain, you can keep yours as is too. I'd rather have a test.

[elalish]

I think it's just slightly more convenient for doing a bunch of them. Probably let's the compiler resize the vector once instead of several times. Probably optimizes down to the same code anyway.

[starseeker]

But if it's a pain, you can keep yours as is too. I'd rather have a test.

Actually I'd like to figure it out and then do that in my code as well, but if I get too badly wrapped around the axle I'll set it up as is. I've got a busy day tomorrow so it might be a little bit, but one way or another I'll get a PR put together soon.

[starseeker]

Being worked in #998

[elalish]

Fixed by #997 and #1005