manifold icon indicating copy to clipboard operation
manifold copied to clipboard

triangulator optimization

Open pca006132 opened this issue 1 year ago • 6 comments

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 2D Rect. This is not necessary, but will probably help with performance and is not hard to do.
  • [ ] Add Remove method to Collider 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?

pca006132 avatar Jan 28 '24 15:01 pca006132