three-bvh-csg icon indicating copy to clipboard operation
three-bvh-csg copied to clipboard

Perform clipping / splitting an general polygons and then triangulate

Open gkjohnson opened this issue 2 years ago • 4 comments

Perhaps it can be drop in replaceable for the triangle splitter

gkjohnson avatar Jun 17 '22 02:06 gkjohnson

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.

gkjohnson avatar Jun 22 '22 02:06 gkjohnson

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

gkjohnson avatar Jun 24 '22 17:06 gkjohnson

  • 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

gkjohnson avatar Jun 24 '22 20:06 gkjohnson

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.

johncalvinyoung avatar Jun 28 '22 15:06 johncalvinyoung

Closing in favor of #51

gkjohnson avatar Sep 12 '22 03:09 gkjohnson