Inquiry regarding optimization of fractureSingleCacheFriendly for polygons with high hole counts

[Liang Jia]

Dear KiCad Developers,

I have a big project with 50000 holes within one copper zone, I found the performance for fill zones is not very good.

So after some digging into the geometry processing code in KiCad, specifically the fractureSingleCacheFriendly and processHole functions.

I noticed that the current implementation for handling polygon holes relies on a linear search(maybe) within processHole. For every hole, the algorithm iterates through the existing edges (up to the provokingIndex) to perform ray-casting and find the nearest left-side neighbor for the bridge connection.

While I understand the current implementation is highly optimized for memory locality (as the function name suggests), the algorithmic complexity appears to be roughly O(N * M), where N is the number of outline edges and M is the number of holes.

My observation:
In scenarios involving complex geometries with a massive number of holes (e.g., large BGA footprints, or complex thermal reliefs), this linear approach might become a performance bottleneck as the edge list grows with every processed hole.

My question:
Has the team considered implementing a Plane Sweep (Scanline) algorithm combined with an Active Edge List (e.g., using a Balanced BST or Interval Tree) for this task?
Standard computational geometry literature suggests this could reduce the complexity to O((N+M) log N), which would theoretically offer significant speedups for high-complexity polygons.

I am curious if the current linear approach was chosen specifically to avoid the overhead of pointer-based structures (to maintain cache friendliness) or if it is simply a case where optimization hasn't been necessary yet.

Would the team be interested in a patch or a prototype that attempts to implement a sweep-line or spatial indexing approach here, or are there specific constraints that make the current implementation preferable?

Thank you for your time and for the great work on KiCad.

Sincerely

Liang

[Jon Evans]

Hello Liang,

The current implementation was added in a merge request last year: https://gitlab.com/kicad/code/kicad/-/merge_requests/1891

I don't think that anyone on the core team has studied the performance deeply.

There are many places where KiCad could do better handling very large designs, and we welcome contributions to improve these areas.

With regards to your proposed algorithm, I think a prototype showing performance differences is a good next step.

The best way to do this would be to work in a branch and then open a merge request when you are ready for others to look at it and test with various designs.

We will need to do careful testing of any new algorithm before it is released in a stable version, as we have seen subtle bugs show up related to polygon fracturing in the past.

Best,

Jon

--
You received this message because you are subscribed to the Google Groups "KiCad Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to devlist+u...@kicad.org.
To view this discussion visit https://groups.google.com/a/kicad.org/d/msgid/devlist/CAE0Ak8bBLP_3b14nTSZ7LRLuXXiB1VfOmDbFoG4WhCc_gy%2BqmA%40mail.gmail.com.

[Liang Jia]

Hi Jon,

Thanks for your reply, I will try to work on it, but I'm not sure that I can fix.

Sincerely

Liang

To view this discussion visit https://groups.google.com/a/kicad.org/d/msgid/devlist/CA%2BqGbCD7rXPKY1C5qg0wPUzVnCePdJniOnZ8waC8Q9XDsEAd7A%40mail.gmail.com.