manifold
manifold copied to clipboard
triangulator optimization
The triangulator takes O(n^2)
time, which performs poorly when the number of points of a polygon increases. For example, for the woodgrain svg we had for #502, there are around 60k points in the polygon. The old triangulator (not as robust) takes 35ms to triangulate the 60k points, while our current triangulator takes around 11500ms (11.5s!). We should try to use bvh to reduce the number of points to check, to avoid quadratic complexity in the general case (for degenerate cases bvh can't help much I guess).
- [ ] Make
Collider
generic and support 2DRect
. This is not necessary, but will probably help with performance and is not hard to do. - [ ] Add
Remove
method toCollider
to support point removal. We don't have to care about rebalancing because the height is bounded (at least in terms of complexity it does not matter, not sure about that in practice, and rebalancing is costly). - [ ] Avoid calculating
DelaunayCost
. We can just categorize ears into different categories: definitely valid, potentially valid, definitely invalid, according to the max cost over query results.
@elalish what do you think?