kicad-developers team mailing list archive

[Seth Hillbrand <seth@xxxxxxxxxxxxx>]

Am Do., 19. Juli 2018 um 00:49 Uhr schrieb 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)?
>
>
​Thanks for testing.  I had similar experiences with TTL.  SGI's libtess
worked for me but is exceptionally slow.

Steiner points is an excellent idea.  I'd been struggling with overlapping
bounding boxes making solutions to lp:1718831 excessively slow.  I think
that might be helpful there.  The code doesn't currently support steiner
points (they are removed during the updateList() stage as NULL triangles).
I use your FractureSingle routine to eliminate holes, so I think I'd need
to mark the steiner points there to avoid removing them later.
Alternatively, maybe we could just allow NULL triangles when forming the
list but not allow them to be an ear and drop them during the last pass if
the polygon can't be triangulated.  That might be the best approach.

-Seth