search

mapbox / earcut.hpp

Fast, header-only polygon triangulation
ISC License
858 stars 133 forks source link

Add notes about 3D to the readme #20

Closed benadler closed 6 years ago

benadler commented 8 years ago

Half a year ago, I was wondering whether earcut.hpp supports 3d triangulation, you said "not at this time". I just noticed the javascript version of earcut supports that - at least since October (judging by the 2.0.7 release comment), maybe from the start.

Are there any plans or timeline for earcut.hpp to support 3d polygons?

Thanks!

mourner commented 8 years ago

Note that 3D support in JS is in the sense that the 3rd dimension isn't considered when triangulating, as if the polygon was projected on a XY plane, although the output includes original vertices including the 3rd dimension. Is it acceptable for you?

benadler commented 8 years ago

Ah. This 2.5d is what I hacked into my wrapper, but in the medium term I need to do real 3d triangulation. I understand this might not be earcut.pp's focus, but maybe you could add a note about 2/2.5/3d support to the readme? Thanks!

mourner commented 8 years ago

@benadler it's pretty hard to define what "real 3d triangulation" means. You can read more about this in Held's FIST paper. One of the approaches to it is choosing a projection plane and then reducing the task to 2D triangulation. Earcut doesn't choose a projection plane, but that can be done as a preprocessing step (calculating 2d polygon area for each of the 3 planes and choosing one with the biggest area) — I know people who successfully used this approach with Earcut.