KLayout DRC .space() algorithm

katherine

Hello!

I have a question about implementing a method for checking the minimum distance between geometries on the same layer.

Recently, I ran a script to check spacing between shapes on a layer using the .space() method, and I wanted to implement a similar algorithm in C++. I couldn't find a description of this algorithm in the repository, so I'm asking for help with its implementation. As far as I know, it uses a sweep-line algorithm and compares edges.

Currently, I'm trying to use an approach that checks distances between cells: first determining if cells are close to each other, then checking distances between geometries inside them (currently using min/max coordinates). The problem arises when working with the GDSII format because I don't know how to properly parse geometries considering transformations (offsets, rotations, mirrors) without excessive copying, which requires a lot of memory.

I tried to build the project in Visual Studio but didn't succeed. I would like to know where in the KLayout source code the implementation of the space() function is located so I can write a similar educational algorithm. I'm interested in how you handle such complex topology hierarchy.

Matthias

Hi @katherine,

technically, the entry point to the space check is Region::space_check in dbRegion.h, line 725. However, that's just the entry point, the details are complex.

I need to say that KLayout is not an educational, but a practical implementation. It's not a proof-of-concept or study implementation, but one that needs to serve real-world use cases. The algorithmic kernel is hidden behind a number of architectural layers, alternative execution paths, caching and parallelization services and evaluation shortcuts.

The core idea is the same than you sketched.

In the flat case, you collect all (merged) polygons or their outline edges, run that through a sweep line algorithm (called a box scanner in KLayout) and identify space violations between adjacent objects. A hierarchy of cells is eliminated by creating polygon or edge copies transformed into the top cell space. This implies a memory overhead as you observed.

In the hierarchical case, the concept is to take one child cell and compute all unique environments of that cell (called the cell contexts in KLayout). You then compute the results of your operation (DRC, booleans etc.) in all these contexts and consolidate the results: everything that appears the same way in all contexts is placed in the child cell, everything else if propagated into the parent cells specific for the particular context. This gives you some "as hierarchical as possible" result without need to modify the original hierarchy. The last statement is important, as this is one differentiator between KLayout and some commercial tools.

That is the big picture. The details are, as mentioned, complex.

I assume that efficient hierarchical geometry processing is subject to a lot of research papers, all of which I did not read. For educational purposes, I'd recommend first to conduct a paper study before looking too deep into KLayout's implementation.

Matthias

katherine

Thanks a lot !