three-bvh-csg
three-bvh-csg copied to clipboard
Perform clipping / splitting an general polygons and then triangulate
Perhaps it can be drop in replaceable for the triangle splitter
Relating to #49 - implementing a better strategy for clipping and then triagulating polygons will leave more edges full intact and ultimately afford more connectivity in addition to being faster. Polygon splitting should occur by gathering all intersections edges with triangles and deriving new polygon boundaries from those connected lines.
Polygon triangulation:
- https://algo.kaust.edu.sa/Documents/cs372l05.pdf
- https://en.wikipedia.org/wiki/Polygon_triangulation
Three.js may already have a good implementation:
- https://github.com/mrdoob/three.js/blob/master/src/extras/Earcut.js
- Construct polygon edge sets with a set of pre-connected edges for the triangle
- When a splitting by a triangle
- Find the intersection edge overlap
- If the edge intersects another edge then split it into two edges and connect it to the split side edges
- Unconnected edges should be added to a list so they can be easily found for future splits
Notably, Earcut is fast (and is technically a separate library vendored into Three: https://github.com/mapbox/earcut), but it is far, far from ideal/Delaunay triangulation.
Closing in favor of #51