Merging polygons

Picture a square frame of metal on a chip, with a strap across the middle, a few fingers, a pad at each end of the strap, and a diagonal brace in the upper corners. Nobody draws that in one stroke. You build it like a frame of lumber, bar by bar, each one lapping over its neighbor so nothing is left loose. The picture at the top shows that frame twice at once. Left of the dark blue line are the pieces as they were drawn, a dozen overlapping rectangles and a slanted bar, each still carrying its own outline. Right of the line is the same layer after a merge: one solid shape, no inner lines, with windows where the frame encloses empty space. The two halves are mirror images, so you can match every piece on the left with the region it became on the right.

To merge is to replace overlapping or touching shapes on one layer with the outline of the area they cover together. In the language of sets, that is a boolean OR, also called a union. Afterwards the original shapes are gone, and what remains is a polygon, or a few, whose edges all separate metal from no metal. This note is about the operation itself: how a computer works it out, what it writes into the file, when it is really required, and what goes wrong inside it. Why stacked shapes are not yet one shape is the subject of overlapping is not merging.

Why it matters

Some machines read every polygon as an instruction. An electron-beam writer draws a pattern into resist one shape at a time, and it exposes each polygon it receives. Where two of your rectangles overlap, it exposes that patch twice. A double dose prints wider than you drew, or closes a gap you meant to keep open. E-beam instructions therefore say: merge away overlaps before you send the file, and keep shapes that need different doses on separate layers so the merge cannot mix them. The data preparation that turns a chip layout into photomask writing data does the same housekeeping before it fractures every shape into the rectangles and trapezoids a mask writer can expose.

Arithmetic cares too. Add up the areas of overlapping rectangles and every shared patch is counted twice, so a density figure computed from unmerged shapes reports more metal than the chip will have. Operations that count coverage are worse: an exclusive OR on a single layer keeps area covered an odd number of times, so every overlap between two of your own pieces drops out.

Other readers merge for you. Design-rule checkers usually merge each layer as they read it, so a width check measures the frame rather than each rectangle. A Gerber file for a circuit board paints its shapes one over another, so overlapping copper plots as one area. Knowing who merges for you keeps merging a deliberate step instead of a nervous habit.

How it works

The outline of a merge follows the covered area, not the pieces you drew. That is why the corner count often surprises people.

Walk the figure from left to right. Each column is one experiment: input on top, and below it what LayoutEditor stored after the merge, with a dark square on every corner it wrote.

In the first column, two rectangles overlap at one corner. One corner of each disappears inside the other, and the two points where their edges cross become new corners: one polygon with eight corners. In the second column, four bars laid out as a square frame become one polygon that encloses a hole. In the third, two squares that touch only at a single point stay two squares. In the fourth, two rectangles look like one bar, but the corner marks in the middle of the top and bottom edges show that the merge returned two shapes. Between them is a gap of one database unit, the smallest step the file can store, here one nanometer. You will not see it at any zoom, but the corners give it away. In the fifth column, a slanted bar crosses a flat one, and the union has twelve corners.

How does a program find those outlines? Imagine a vertical line sliding across the layer from left to right. It stops wherever an edge begins, ends, or crosses another edge. At each stop, the program knows how many shapes cover each stretch of the line: none, one, two, or more. It writes a result edge only where that count changes between zero and at least one. Where the count goes from one to two, the edge lies inside metal and is thrown away. This is called a sweep-line, or scanline, method, and fast versions of it have been part of mask data processing since the early 1980s. Read the lead picture the same way: wherever the left half shows a dark line running through tinted metal, the count changes from one to two, and the merged half on the right has no edge there.

Slanted edges bring arithmetic into it. The slanted bar in the fifth column climbs 9 µm while it moves 3.5 µm sideways, so its left edge meets the bottom of the flat bar at x = 59,166.67 nm in that drawing, not a whole number of nanometers. The file can only hold whole database units, so LayoutEditor stored 59,166 nm. The red squares mark the four crossings that were moved this way, each by less than a nanometer.

What the file stores

GDSII, the file format most chip layouts travel in, has no flag that says "merged" and no way to say "hole." Every boundary stands on its own, and two boundaries that overlap cover the same area twice. A hole therefore has to be part of the outline itself. To store the frame from the second column, LayoutEditor wrote one outline with ten corners. It starts on the outside, runs down a cut line through the top bar into the hole (the red mark in the figure), travels around the hole, comes back up the same line, and finishes the outside. The two edges of the cut lie exactly on top of each other, so no metal is missing. This self-touching outline is often called a keyhole, and it is legal in GDSII as long as the edges touch without crossing. Holes in polygons looks at holes in more detail.

The format also has a ceiling. The record that holds a boundary's coordinates has a two-byte length field, which allows at most 8,191 coordinate pairs in one boundary. The last pair repeats the first, so a boundary can have 8,190 corners. Older readers may expect far fewer; the original specification spoke of 200. A merge can cross that line without anyone trying.

That figure is a window of about 12 µm from the middle of a comb: a spine 880 µm long and 2 µm tall, with 2,200 teeth that are 0.2 µm wide on a 0.4 µm pitch, drawn as separate rectangles and merged into one outline with 8,802 corners. That is more than one boundary can hold. When LayoutEditor writes the result to a GDSII file, it stores it as two boundaries of 4,404 and 4,402 corners that meet along a straight cut at x = 440.049 µm. The cut runs through the spine and right through one tooth, which is why the tooth at the seam is partly navy and partly copper. Nothing is lost, because the pieces abut exactly, but every program downstream now sees a seam you never drew. Merging a large ground area or a field of fill, or inverting a layer by subtracting everything from one big rectangle, produces outlines like this easily, and some tools slow down badly on them.

A common mix-up

A merge is not a group. Selecting shapes together, grouping them, or moving them into a cell changes how you handle them, not the geometry in the file. A merge changes the geometry, and the file keeps no record of which rectangles the result came from.

A merge is not a repair either. If a rule check reports a neck that is too narrow, the union has the same neck: merging removes lines inside the metal, never metal itself. And a merge works on one layer at a time. Metal on one layer does not merge with metal on another because they overlap on screen, the via between them stays its own shape, and most tools also keep a different datatype on the same layer number apart.

Things that go wrong

The most common surprise is a merge that returns more polygons than you expected. Count the result. If one strap comes back as two polygons, there is a gap, perhaps a single database unit like the one in the fourth column. Find it before you cover it with a patch.

Corners that only touch are a matter of definition. LayoutEditor's Merge leaves the two squares from the third column as two shapes, while its rule-file checker documents the other choice: merged() stitches a pair that shares only a corner into one outline that touches itself. If a corner contact matters electrically, draw a real overlap instead of relying on a definition.

Rounding is the quiet one. Horizontal and vertical edges always cross at coordinates that already exist, so Manhattan layouts merge exactly, and 45-degree edges meet them on whole units too. Edges at other angles almost never cross on a whole database unit, and each crossing is moved to one. The difference is less than a unit, but it can leave a tiny jog in a straight edge, turn a right angle into one that is slightly sharp, or put a corner off the manufacturing grid that the factory requires, which an off-grid check will then report. Repeated booleans add up these small moves; when the computer moves an edge follows that thread.

Treat a keyhole cut with care. Drag a corner on the cut and the two coincident edges separate: you have opened a real slit in the metal, as narrow as the distance you moved. Gerber allows such cut-ins only under strict conditions and prefers a separate clearing shape for each hole.

Hierarchy hides shapes from a merge. A merge sees the shapes in the cell you are editing; shapes inside placed cells are not inputs and stay as they were, even where they overlap your new metal. To merge metal that lives in many cells you have to flatten that layer, copying every instance's shapes into one cell and giving up the savings of hierarchy.

A merged polygon also forgets what kind of shape it came from. A path has a centerline and a width you can edit; inside a polygon union both are gone. In LayoutEditor, Merge joins a path only with another path that shares an end point, and a path lying across a box stays a path. To fold paths into the outline, convert them to polygons first or use the layer-wide merge described below. A box becomes a polygon as soon as the union is not a rectangle, though two boxes sharing a full edge come back as one box.

Finally, some commands leave the inputs behind. LayoutEditor's Boolean tool and Bool on Layer write the union onto a layer you choose and keep the originals unless you ask them to delete the sources. That is the safe default, and also how a layer ends up holding both the old pieces and the new union: the overlap problem all over again.

In LayoutEditor

Draw > Merge, shortcut V, merges the selected shapes that share a layer into a single shape wherever possible and replaces them; every merge in the second figure was made this way. Merge to Layer, Shift+V, is the deliberate exception to the one-layer rule: it merges the selection regardless of layer onto the active layer and keeps the originals. For large selections the Boolean tool is faster. Bool on Layer, in the full version, runs "A merge" over an entire layer, ignores cell hierarchy, and splits the work into frames across all processor cores. In rule files, a layer is merged as it is read unless you ask for the raw shapes, merged(a) gives the union, and merged(a, n) keeps only area covered by at least n shapes.

One habit catches nearly everything above: merge a copy onto a scratch layer first. Count the polygons and the corners, compare the area with what you expect, and compute the exclusive OR of the result against the original shapes, as described in AND, OR, NOT; it should be empty. Zoom in on every slanted crossing. Then delete the inputs, and only then move the union onto the real layer.