kicad-developers team mailing list archive
Mailing list archive
Re: Tesselation Ideas
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
Am Do., 19. Juli 2018 um 09:23 Uhr schrieb Seth Hillbrand <
> Am Do., 19. Juli 2018 um 00:49 Uhr schrieb Tomasz Wlostowski <
>> 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).
>> > 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
>> 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.