GetMesh core dump with SparseIndices too large about manifold

[starseeker]

Oh, reading the comments, this may be a similar situation to #720 after all.

[elalish]

yeah, closely related, but your PR still picked up and interesting difference. When you say "doesn't qualify as a large mesh", how many tris to each of these models have?

[starseeker]

Left should have on the order of 20k faces, and right about 11.5k. They're not small, certainly, but by the standards of some of the meshes we deal with they didn't strike me as huge.

[starseeker]

Unfortunately I don't have a smaller input that triggers the issue - if those are too large to be suitable for inclusion in the repo feel free to close the pull request. I mostly wanted to try and provide inputs so the problem could be reproduced.

[elalish]

yeah, agreed. Even at n^2, you're only looking at 230 million or so. I'm guessing these triangles just happen to have huge bounding boxes such that nearly everything collides with everything else? Still, I think the right solution is to index the sparse indices with 64 bit ints, in case we hit a not-sparse case like this.

[starseeker]

Yes - visually inspecting I think that's exactly what's going on - virtually all the triangle bboxes are colliding with each other. This is all automatically generated intermediate geometry... is there some functionality in manifold I could use to chop the triangles up into being a little more equilateral to help with the bounding box problem?

[starseeker]

Or alternately, if there's a way to check some metric for the "health" of the bounding box sparsity, I could maybe try bouncing the mesh over to geogram and see what their remesher can do with it.

[elalish]

In general, lots of huge triangles that are not axis-aligned will tend to create these situations. Generally speaking, huge triangles tends to mean few triangles, but I guess that's not true for yours. Care to drop in a screenshot of the models? I'm not sure of generic automated ways to fix it, but I'd be curious if you find some - as even if we fix the index problem, this will still have quite poor performance.

[starseeker]

This is the right mesh - the red line is the full length of the mesh, and the upper left is a somewhat zoomed in look at the structure.

[starseeker]

Left is the same idea, except more of them and some branches as it's the mesh onto which things are being unioned.

[starseeker]

I can probably look at what our internal CSG->mesh routines are generating and see if there's a way to improve that output - looking at the right cylinder, I'm wondering if maybe the long and narrow cylinder case is producing something odd from our side as well. Oh well - either way, another stress test added to the pile ;-)

[elalish]

I feel a little less bad now - that's some awful geometry! But yes, good stress test.

[starseeker]

Just as a follow up, I created a different routine to produce cylindrical input meshes for the specific case in question that doesn't produce such strange meshes, and that succeeded fully (still rather slow, but without the crazy super long and thin triangles we didn't hit any of the limits.)

[pca006132]

btw, I think one of the reasons for this seemingly small mesh hitting the limit of the sparse indices is due to the crazy long triangles. The AABB of them may just span the whole AABB of the mesh, making the collider naively give N^2 pairs. If uniform mesh refinement is allowed, maybe we can do better? Not sure about that.

[elalish]

Quite possibly - something #741 may help with too.

[pca006132]

Hmm, just FYI the memory usage for union this specific case with RefineToLength(50) causes the memory usage to basically explode, probably because the situation is still similar after mesh refinement... I think the solutions I saw were refining the bounding box and perform some filtering in the collider. Anyway, that is very complicated and we probably don't want to do it for now.