Polygon De-Embedding is the ability to take a layer of polygons "embedded" within other polygons, figure out which surrounds which, and produce a GDSII output that sorts out the changes in polarity due to each boundary.
You can think of this as follows: If a polygon is not surrounded by any other it is set to the 0 level. If a polygon is fully surrounded by only one other polygon (its parent) it is assigned a level of 1. If its parent is surrounded then it is assigned a level of 2 and so on.
Figure 2: polygons inside of polygons can be given a level indicating how deeply embedded they are.
All polygons with even levels: 0, 2, 4, 6, 8 ... are "dark" or "filled" and all polygons with odd levels of 1, 3, 5, 7 ... are "clear" or "empty."
We are also going to require than no polygon may cross itself or even touch another polygon -- they have to be fully enclosed by the parent. If any polygons do touch or overlap we will first unionize them before performing the embedding level computation.
Figure 3: Overlapping or touching polygons have to be dealt with before computing the dembedding level.
Those who work in the mask business are familiar with this problem. IC layout tools don't generate nested polygons but designs that originate from mechanical drawing software such as AutoCAD, SolidWorks or ProEngineer do. Very often they are complex IC package layouts, MEMs, RF or microwave circuits or optical devices.
ASM 3500's (DXF to GDSII) de-embedding function can automatically sort out this type of drawing. There are three distinct processing steps.
Prior to doing any sorting, the program first does a union on any touching or overlapping polygons. This is required so that the sorting routine doesn't encounter ambiguous situations produced by overlapping polygons.
Figure 4: Prior to sorting, any overlapping or touching polygons are unionized.
Step 2 - Sorting
The de-embeddding routine then sorts the polygons assigning each a level - 0 for polygons not surrounded by any parent, 1 for those surrounded by one parent, 2 for those 2 levels deep and so on. This can be a very complex process when the polygons are large.
Figure 5: Polygons are sorted by their embedding level.
Since GDSII has only "dark" polygons we have to do a boolean operation. All polygons in level 1 are subtracted from those in level 0. All polygons in level 3 are subtracted from those in level 2 and so on. The output of the boolean can produce either re-entrant polygons (those with a cut line) or slices (the slice option is available for some CAD systems that have problems processing re-entrant polygons.)
Figure 6: After Boolean, the resulting mask consists of only dark polygons. Two options are possible: cut-lines or sliced.