Coder Social home page Coder Social logo

Comments (16)

starseeker avatar starseeker commented on July 23, 2024

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

from manifold.

elalish avatar elalish commented on July 23, 2024

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?

from manifold.

starseeker avatar starseeker commented on July 23, 2024

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.

from manifold.

starseeker avatar starseeker commented on July 23, 2024

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.

from manifold.

elalish avatar elalish commented on July 23, 2024

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.

from manifold.

starseeker avatar starseeker commented on July 23, 2024

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?

from manifold.

starseeker avatar starseeker commented on July 23, 2024

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.

from manifold.

elalish avatar elalish commented on July 23, 2024

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.

from manifold.

starseeker avatar starseeker commented on July 23, 2024

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.

image

from manifold.

starseeker avatar starseeker commented on July 23, 2024

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

from manifold.

starseeker avatar starseeker commented on July 23, 2024

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 ;-)

from manifold.

elalish avatar elalish commented on July 23, 2024

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

from manifold.

starseeker avatar starseeker commented on July 23, 2024

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

from manifold.

pca006132 avatar pca006132 commented on July 23, 2024

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.

from manifold.

elalish avatar elalish commented on July 23, 2024

Quite possibly - something #741 may help with too.

from manifold.

pca006132 avatar pca006132 commented on July 23, 2024

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.

from manifold.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.