On 19/07/18 06:15, Seth Hillbrand wrote: > Hi All- > > Our current triangulation caching is based on the poly2tri codebase and > has a number of constraints. Most notably, it does not allow touching > holes, holes on the boundary or duplicate vertices. In these cases, we > do not cache the triangulation and instead use the OpenGL single-thread > triangulation routine each time we draw a complicated polygon. This has > the side-effect of making some boards much slower in Accelerated mode > than in Fallback. > > I've been noodling with an idea for how to better cache our > triangulation and I think it's ready for some wider testing. It > combines the Sloan ear-cutting algorithm with a plane division and > simplication approach to address difficult polygons. It generally > follows the approach of Lamot and Zalik > (https://www.sciencedirect.com/science/article/pii/S0097849302002819) > but implements some of the shortcuts from the mapbox earcut library > (https://github.com/mapbox/earcut) > > The code is located in my GitHub > (https://github.com/sethhillbrand/kicad-source-mirror/tree/tesselation). If > you clone the tree, be sure to check out the branch "tesselation". > > Comments/feedback greatly appreciated.
Wow, just tried the code, it's quite fast :) Good job. I've been trying to use TTL/HalfEdge or poly2tri for such triangulations but without much success. Tom PS. Does your algorithm support arbitrary Steiner points (i.e. adding a regular grid inside the polygon area to obtain more regularly shaped triangles which can be efficiently indexed using an R-Tree)? _______________________________________________ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
