kicad-developers team mailing list archive

[Tomasz Wlostowski <tomasz.wlostowski@xxxxxxx>]

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)?