kicad-developers team mailing list archive

[Seth Hillbrand <seth@xxxxxxxxxxxxx>]

Hi All-

I've finished implementing Tom's suggestion as well as completing the
replacement of poly2tri in the ray tracer as well.  I've posted a merge
proposal to launchpad for comments.  I'd greatly appreciate any feedback
(small or large) before merging.  You can find the merge proposal at
https://code.launchpad.net/~sethh/kicad/+git/kicad/+merge/353697

Thanks-
Seth

Am Do., 19. Juli 2018 um 09:23 Uhr schrieb 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
>