DRC crash caused by two polygon subtraction

[dansharkey]

While attempting to run the below DRC script on the attached gds file (renamed with a .txt extension to circumvent GitHub's rules), KLayout crashes.

DRC_Crash_During_Boolean_Subtraction.txt

report("DRC Crash During Boolean Op", "DRC Crash During Boolean Op.lyrdb")
deep

# 'Raw' Layers
layer_a=polygons(3)
layer_b=polygons(4)

# Generated Layer
layer_c=(layer_a-layer_b)

I've tested this v0.28.17, on both Windows 10 (MD5=133b544dbff287e0da337ad1a9fead63) and MacOS (MD5=93444479d433e1f7a7e73c5478dfa2db).

The crash report from the MacOS hints that this is using db::Region::operator-, db::DeepRegion::not_with, and db::DeepRegion::and_or_not_with and the db::local_processor but I might be reading it wrong. It works fine in flat mode with tiling.

[klayoutmatthias]

Hi @dansharkey,

thanks for this well-prepared issue.

You can attach .zip files in an issue which is the usual way to convey binary test data.

I do not see the crash in my case (Ubuntu 22), but memory goes up quickly and I suspect you might get a bad::alloc error.

The reason is the following: in deep mode, KLayout splits polygons into smaller parts do reduce potential cross-hierarchy interactions. Polygons with many points (>32) and with a high bounding-box to polygon area ratio are split into smaller parts. The algorithms does so by iteratively splitting until the default area ratio of 3.0 is achieved and the new polygons have less than 32 points.

While this works well on Manhattan polygons, the search for low-area-ratio polygons does not properly converge for the skinny XOR result polygons as you can see here:

The solution is simply to turn off the splitting feature by putting these lines at the front of your script:

max_area_ratio(0.0)
max_vertex_count(0)

I'd not recommend doing that in general as for Manhattan-style layouts, the splitting feature is key to better performance of deep mode.

With the patch, the script runs quickly and renders 20 small XOR slivers instead of 0.5M triangles.

Matthias

[dansharkey]

Ah, now I feel silly! Both for the txt instead of zip, but also for not reading the docs properly.

I didn't receive the bad_alloc (as I usually do) on Windows - I wonder why that might be.

Many thanks (again!) for your quick support, it's much appreciated. That's a nice solution (convert to manhattan) for large VLSI designs, similar to the 'Magic' approach I guess.

[klayoutmatthias]

Very good, thanks for the feedback :)

Maybe the crash is because of stack overflow rather than bad_alloc, but I can't reproduce, so I can't say.

The approach is actually not to convert to Manhattan - it is about having polygons for which the bounding box is a better approximation. Imagine a thin rectangular ring running around your design - the bounding box of that ring would intersect with the whole design and induce a lot of first-tier interactions without need. Splitting that ring into the bars making up that ring will improve the situation and render many algorithms perform much better.

Matthias

[klayoutmatthias]

Can we close this issue?

Matthias

[dansharkey]

Sure, yes. Thanks again!