Strange Polygon Point Sequence

[esigle]

Hey @klayoutmatthias

I'm reporting a strange behavior in 0.29.6 (also in 0.29.3) regarding the creation of polygons for derived layers using DRC.

I tried to make a minimum-example to show the issue. The files needed are in the .zip.

I created a shape in Virtuoso and exported it as a .gds file (called h_cutout.gds). Then, usually with more complex layouts, I want to create derived layers of the design with boolean operations using DRC. Using only the input() command and writing it to the derived_layer file, the newly created polygon in h_cutout_derived_layer.gds shows a different point sequence. The new point sequence is unnecessarily complex and creates issues when importing the derived layers into other programs (e.g. CST). The polygon is not self-intersecting, however I expected the point sequence to stay the same/similar.
Using Python, importing the layer to a region and writing the shapes of the region into the new layer, has the same result.

Steps:

1. Stark KLayout
2. Open: h_cutout.gds (see .zip)
3. execute DRC code on it: h_cutout_drc_code.lydrc
4. Open generated file (for completeness, also provided in the .zip)
5. Notice: Polygon point sequence changed, and is unnecessarily complex

h_cutout.zip

[sebastian-goeldi]

I think this is due to how polygons in gds can only be simple polygons, so this is just how the slicing algorithm goes through it. Regions afaik will make polygons from simple polygons if any merge operation is performed (iirc this depends on the settings of the merge_semantics). So when you load it into a region, the simple polygons become polygons with holes. On write they need to be sliced again.

[klayoutmatthias]

Hi @esigle,

In short: If you don't want a modification, don't do a merge.

The goal of the merge feature is not to create a polygon of "minimum complexity". The resulting polygon is orientable and not self-overlapping. It is self-touching, but that is inevitable to represent holes. Mathematically speaking, every point inside the polygon has wrap count 1 while points outside the polygon have wrap count 0. The polygon meets this condition and is valid in that sense. On a global scale, a merge step will meet this condition over the whole area of the region and across all polygons inside the region. Hence it acts on all objects inside the region, not just the ones that really need treatment.

The hole stitching algorithm follows the scan line order which is from left to right. More elaborate analysis may be possible, but that is a tradeoff vs. performance (hole stitching can be a performance killer) and is likely to fail in other boundary cases.

I wonder what is wrong with the CST tool (whatever that is). I don't know any tool myself that has serious trouble reading and processing these kind of polygons, including KLayout of course. The algorithms are in place that way for many years if not a decade now without negative feedback.

You can try trapezoid decomposition after merge which renders a decomposition into the most basic convex polygons:

l22 = input(22, 0)

l22.merge
l22.data = l22.data.decompose_trapezoids_to_region

l22.output(100, 0)

The result is not minimal in terms of number of shapes, but overlap-free and free of interpretation issues.

Matthias

[klayoutmatthias]

I found some time to investigate this issue.

Basically there was code already to improve the formation of hole insertion lines. However, the algorithm had a O(2) complexity in the number of holes along a horizontal line and this is clearly a no-go in a some applications.

I managed to find a shortcut, that provides an improved hole insertion scheme in many cases and does not create a performance issue. I will have to see if the new algorithm is a release candidate.

Matthias

[klayoutmatthias]

The PR does not solve this particular issue. It solves other issues of a similar kind, but the polygon in this particular case will not be rendered differently.