kicad-developers team mailing list archive

[Seth Hillbrand <seth@xxxxxxxxxxxxx>]

​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.
-Seth