triangulator optimization about manifold

[kintel]

Thx - looks very promising so far!

[elalish]

Yeah, that sounds good. And actually, I think Delaunay cost should work too - we only care within a bounded region: Delaunay only matters for points closer to the edge midpoint than its half-length. So we should still be able to safely screen out more distant points with BHV.

[pca006132]

https://github.com/elalish/manifold/blob/master/src/polygon/src/polygon.cpp

[pca006132]

btw wonder if it is possible to move some of the sort by morton code logic into the collider.

[elalish]

btw wonder if it is possible to move some of the sort by morton code logic into the collider.

Or in its own header file. Still, it's important the sort the actual underlying data structures, since that gives us cache coherence. So the Morton codes are for more than just the collider.

[onlynadeem]

I know how to do triangulator optimization very well, but where to import its source file?

[pca006132]

Adding a comment from #751:

Optimizations related to triangulator is interesting, I am open to adding fast paths, but a more general one (e.g. monotone triangulation, but doesn't handle epsilon), and directly into the triangulator rather than limited to extrude.

[kintel]

This is starting to hurt for some OpenSCAD usage too. It's also surprisingly slow in debug mode:

• Manifold debug: 5m50s
• Manifold release: 12s
• CGAL constrained delaunay triangulator: 0.3s

^ not very scientific, just measuring OpenSCAD e2e processing time.

[elalish]

Yeah, debug mode adds a lot of extra checks - we should probably go through and see how many are necessary. And you do mean just MANIFOLD_DEBUG right? Because actual C++ Debug mode is horrifically slow for some reason.

Yeah, we should get this done - it shouldn't even really be so difficult. What kind of example is this where you see the slowdown? Care to make a TEST of it?

[kintel]

The polygon in question is #831 - might be a tad big to add as a performance test