CDMEBESGeomFns.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
McCreight, May 16, 1986 3:03:28 pm PDT
Hoel, February 27, 1986 3:33:39 pm PST
DIRECTORY
Atom, CD, CDBasics, CDMEBES, CStitching, IO;
CDMEBESGeomFns: CEDAR PROGRAM
IMPORTS Atom, CDBasics, CDMEBES, CStitching, IO =
BEGIN OPEN CDMEBES;
NOTFn: PROC [ ms: MaskState, spec: LIST OF REF ANY, extInfluenceDiameter: Nm ← 0 ] RETURNS [ result: Tesselation ] -- CoverProc -- =
BEGIN
ComplementTile: PROC [tile: CStitching.Tile, data: REF ANY] -- CStitching.PerTileProc -- =
{result.ChangeRect[CDBasics.Intersection[CDBasics.universe, tile.Area], $covered]};
basis: Tesselation ← GenerateCover[ms, spec.first, extInfluenceDiameter];
result ← NewTesselation[NIL];
[] ← basis.EnumerateArea[rect: CDBasics.universe, eachTile: ComplementTile, skip: $covered];
basis ← DisposeTesselation[basis];
END;
ANDFn: PROC [ ms: MaskState, spec: LIST OF REF ANY, extInfluenceDiameter: Nm ← 0 ] RETURNS [ result: Tesselation ] -- CoverProc -- =
BEGIN
NilTile: PROC [tile: CStitching.Tile, data: REF ANY] -- CStitching.PerTileProc -- =
{result.ChangeRect[CDBasics.Intersection[CDBasics.universe, tile.Area], NIL]};
result ← GenerateCover[ms, spec.first, extInfluenceDiameter];
FOR rest: LIST OF REF ANY ← spec.rest, rest.rest WHILE rest # NIL DO
term: Tesselation ← GenerateCover[ms, rest.first, extInfluenceDiameter];
[] ← term.EnumerateArea[rect: CDBasics.universe, eachTile: NilTile, skip: $covered];
term ← DisposeTesselation[term];
ENDLOOP;
END;
ANDNOTFn: PROC [ ms: MaskState, spec: LIST OF REF ANY, extInfluenceDiameter: Nm ← 0 ] RETURNS [ result: Tesselation ] -- CoverProc -- =
BEGIN
NilTile: PROC [tile: CStitching.Tile, data: REF ANY] -- CStitching.PerTileProc -- =
{result.ChangeRect[CDBasics.Intersection[CDBasics.universe, tile.Area], NIL]};
result ← GenerateCover[ms, spec.first, extInfluenceDiameter];
FOR rest: LIST OF REF ANY ← spec.rest, rest.rest WHILE rest # NIL DO
term: Tesselation ← GenerateCover[ms, rest.first, extInfluenceDiameter];
[] ← term.EnumerateArea[rect: CDBasics.universe, eachTile: NilTile, skip: NIL];
term ← DisposeTesselation[term];
ENDLOOP;
END;
ORFn: PROC [ ms: MaskState, spec: LIST OF REF ANY, extInfluenceDiameter: Nm ← 0 ] RETURNS [ result: Tesselation ] -- CoverProc -- =
BEGIN
This is a very common case, so we speed it up by separating it into two lists: CDLayer's with nonnegative deltaDiameter's, and other things. We compute the other things first, and then take a single pass at the design for the CDLayer's with nonnegative deltaDiameter's.
CoverTile: PROC [tile: CStitching.Tile, data: REF ANY] -- CStitching.PerTileProc -- =
{result.ChangeRect[tile.Area, $covered]};
layers: LIST OF CDLayer ← NIL;
otherThings: LIST OF REF ANYNIL;
FOR subList: LIST OF REF ANY ← spec, subList.rest WHILE subList # NIL DO
WITH subList.first SELECT FROM
layer: CDLayer =>
IF layer.deltaDiameter >= 0 THEN layers ← CONS[layer, layers]
ELSE otherThings ← CONS[layer, otherThings];
ENDCASE => otherThings ← CONS[subList.first, otherThings];
ENDLOOP;
IF otherThings = NIL THEN result ← NewTesselation[NIL]
ELSE
BEGIN
result ← GenerateCover[ms, otherThings.first, extInfluenceDiameter];
FOR rest: LIST OF REF ANY ← otherThings.rest, rest.rest WHILE rest # NIL DO
term: Tesselation ← GenerateCover[ms, rest.first, extInfluenceDiameter];
[] ← term.EnumerateArea[rect: CDBasics.universe, eachTile: CoverTile];
term ← DisposeTesselation[term];
ENDLOOP;
END;
IF layers # NIL THEN
DrawLayersWithPosDeltas[ms: ms, rects: result, layers: layers, extInfluenceDiameter: extInfluenceDiameter];
END;
RunRec: TYPE = RECORD [
desc: ROPE,
areaInSqMeters: REAL ← 0,
perimInMeters: Meters ← 0.0,
runsInMeters: ARRAY Sense OF RECORD [
sense: ROPE,
r: REF RunArray
]
];
RunArray: TYPE = RECORD [ ra: SEQUENCE size: NAT OF Meters ];
MeasureRuns: PROC [ ms: MaskState, spec: LIST OF REF ANY, extInfluenceDiameter: Nm ← 0 ] RETURNS [ result: Tesselation ] -- CoverProc -- =
BEGIN
PixelRunArray: TYPE = RECORD [ ra: SEQUENCE size: NAT OF MEBESPixels ];
PixelCoverRec: TYPE = RECORD [ sense: ROPE, maxInterestDist, minFeature: MEBESPixels ← 0, r: REF PixelRunArray ];
areaInSqPixels: INT ← 0;
perimInPixels: MEBESPixels ← 0;
table: ARRAY Sense OF REF PixelCoverRec ← ALL[NIL];
runRef: REF RunRec ← NIL; -- for external consumption
mebesPixelPitch: Meters ← ms.mebesPixelPitch -- nm -- *1.0E-9;
LookForRuns: PROC [tile: CStitching.Tile, data: REF ANY]
-- CStitching.PerTileProc -- =
BEGIN
ComplainAboutFeature: PROC [ dia: MEBESPixels, pos: MEBESPosition ] =
BEGIN
chose: NAT = ComplainAt[ms: ms, pos: pos,
explanation: IO.PutFR["Too-small %g", IO.rope[c.sense]],
choice: LIST ["Reduce min feature", "Proceed"]];
SELECT chose FROM
1 => c.minFeature ← dia;
ENDCASE => NULL;
END;
EWRuns: PROC [ cov: CStitching.Tile, x1, x2: MEBESPixels ] =
BEGIN
IF cov.NEdge < keyTileArea.y2+c.maxInterestDist THEN
BEGIN
covHeight: MEBESPixels = cov.NEdge-keyTileArea.y2;
FOR tile: CStitching.Tile ← cov.EN, tile.SW WHILE x1 < tile.EEdge DO
tx1: MEBESPixels = MAX[x1, tile.WEdge];
tx2: MEBESPixels = MIN[x2, tile.EEdge];
SELECT TRUE FROM
tx2 <= tx1 => NULL;
tile.value # keyTilevalue =>
BEGIN
IF covHeight = 0 THEN perimInPixels ← perimInPixels+(tx2-tx1);
EWRuns[cov: tile, x1: tx1, x2: tx2];
END;
covHeight >= c.minFeature =>
c.r[covHeight] ← c.r[covHeight]+(tx2-tx1);
covHeight > 0 => -- IN (0..minFeature) --
BEGIN
ComplainAboutFeature[covHeight, [x: (tx1+tx2)/2, y: (cov.NEdge+keyTileArea.y2)/2]];
c.r[covHeight] ← c.r[covHeight]+(tx2-tx1);
END;
ENDCASE => NULL;
ENDLOOP;
END;
END; -- of EWRuns
NSRuns: PROC [ cov: CStitching.Tile, y1, y2: MEBESPixels ] =
BEGIN
IF cov.EEdge < keyTileArea.x2+c.maxInterestDist THEN
BEGIN
covWidth: MEBESPixels = cov.EEdge-keyTileArea.x2;
FOR tile: CStitching.Tile ← cov.NE, tile.WS WHILE y1 < tile.NEdge DO
ty1: MEBESPixels = MAX[y1, tile.SEdge];
ty2: MEBESPixels = MIN[y2, tile.NEdge];
SELECT TRUE FROM
ty2 <= ty1 => NULL;
tile.value # keyTilevalue =>
BEGIN
IF covWidth = 0 THEN perimInPixels ← perimInPixels+(ty2-ty1);
NSRuns[cov: tile, y1: ty1, y2: ty2];
END;
covWidth >= c.minFeature =>
c.r[covWidth] ← c.r[covWidth]+(ty2-ty1);
covWidth > 0 => -- IN (0..minFeature) --
BEGIN
ComplainAboutFeature[covWidth, [x: (cov.EEdge+keyTileArea.x2)/2, y: (ty1+ty2)/2]];
c.r[covWidth] ← c.r[covWidth]+(ty2-ty1);
END;
ENDCASE => NULL;
ENDLOOP;
END;
END; -- of NSRuns
keyTilevalue: REF ANY = tile.value;
c: REF PixelCoverRec = table[(IF keyTilevalue = NIL THEN cover ELSE space)];
keyTileArea: CStitching.Rect = tile.Area;
clippedKeyTileArea: CStitching.Rect =
CDBasics.Intersection[ms.mebesStripeClip, keyTileArea];
IF keyTilevalue # NIL THEN
areaInSqPixels ← areaInSqPixels+
(clippedKeyTileArea.x2-clippedKeyTileArea.x1)*
(clippedKeyTileArea.y2-clippedKeyTileArea.y1);
We examine first the north and then the east neighbors of this key rectangle, noting the nearest rectangle of the same kind in the direction of view.
IF keyTileArea.y2 IN (ms.mebesStripeClip.y1 .. ms.mebesStripeClip.y2] THEN
EWRuns[cov: tile, x1: clippedKeyTileArea.x1, x2: clippedKeyTileArea.x2];
IF keyTileArea.x2 IN (ms.mebesStripeClip.x1 .. ms.mebesStripeClip.x2] THEN
NSRuns[cov: tile, y1: clippedKeyTileArea.y1, y2: clippedKeyTileArea.y2];
END; -- of LookForRuns
GetCoverRec: PROC [sense: ROPE, l: LIST OF REF ANY] RETURNS [c: REF PixelCoverRec] =
BEGIN
c ← NEW[PixelCoverRec ← [sense: sense]];
c.maxInterestDist ← NARROW[l.first, REF Nm]^/ms.mebesPixelPitch;
c.minFeature ← NARROW[l.rest.first, REF Nm]^/ms.mebesPixelPitch;
c.r ← NEW[PixelRunArray[c.maxInterestDist]];
FOR width: MEBESPixels IN [0..c.r.size) DO
c.r[width] ← 0;
ENDLOOP;
END;
table[cover] ← GetCoverRec["cover", spec.rest.rest];
table[space] ← GetCoverRec["space", spec.rest.rest.rest.rest];
result ← GenerateCover[ms, spec.rest.first, extInfluenceDiameter+MAX[table[cover].maxInterestDist, table[space].maxInterestDist]];
[] ← result.EnumerateArea[rect: ms.mebesStripeClip, eachTile: LookForRuns, skip: $none];
ms.data ← runRef ← NEW[RunRec ← [
desc: NARROW[spec.first],
areaInSqMeters: areaInSqPixels*mebesPixelPitch*mebesPixelPitch,
perimInMeters: perimInPixels*mebesPixelPitch,
runsInMeters: [
space: [sense: "space", r: NEW[RunArray[table[space].r.size]]],
cover: [sense: "cover", r: NEW[RunArray[table[cover].r.size]]]
]
]];
FOR sense: Sense IN Sense DO
FOR width: MEBESPixels IN [0..table[sense].r.size) DO
runRef.runsInMeters[sense].r[width] ← table[sense].r[width]*mebesPixelPitch;
ENDLOOP;
ENDLOOP;
END;
RestrictedEnlarge: PROC [ ms: MaskState, spec: LIST OF REF ANY, extInfluenceDiameter: Nm ← 0 ] RETURNS [ result: Tesselation ] -- CoverProc -- =
BEGIN
PlaceNImplant: PROC [tile: CStitching.Tile, data: REF ANY]
-- CStitching.PerTileProc -- =
BEGIN
InteractWithPImplant: PROC [tile: CStitching.Tile, data: REF ANY]
-- CStitching.PerTileProc -- =
BEGIN
Relationship: TYPE = {pNn, pEn, pSn, pWn};
pTile: CStitching.Tile = tile;
pTileArea: MEBESRect = pTile.Area;
bestDir: Relationship;
bestGap: MEBESPixels ← -1;
tGap: MEBESPixels;
gaps: ARRAY Relationship OF MEBESPixels ← ALL[maxRadialExtension];
deInsertedArea: MEBESRect;
IF (tGap ← nTileArea.x1-pTileArea.x2)>bestGap THEN
{bestDir ← $pWn; bestGap ← tGap};
IF (tGap ← pTileArea.x1-nTileArea.x2)>bestGap THEN
{bestDir ← $pEn; bestGap ← tGap};
IF (tGap ← nTileArea.y1-pTileArea.y2)>bestGap THEN
{bestDir ← $pSn; bestGap ← tGap};
IF (tGap ← pTileArea.y1-nTileArea.y2)>bestGap THEN
{bestDir ← $pNn; bestGap ← tGap};
IF bestGap<0 THEN ERROR; -- design rule violation
IF NOT anyInteractingPImplant THEN
BEGIN
anyInteractingPImplant ← TRUE;
nImplPieces.ChangeRect[CDBasics.universe, NIL];
nImplPieces.ChangeRect[desiredNImplant, $covered];
END;
gaps[bestDir] ← bestGap/2;
deInsertedArea ← [x1: pTileArea.x1-gaps[$pEn], y1: pTileArea.y1-gaps[$pNn], x2: pTileArea.x2+gaps[$pWn], y2: pTileArea.y2+gaps[$pSn]];
IF CDBasics.NonEmpty[deInsertedArea] THEN nImplPieces.ChangeRect[deInsertedArea, NIL];
END;
CoverNegotiatedPiece: PROCEDURE [tile: CStitching.Tile, data: REF ANY]
-- CStitching.PerTileProc -- =
{area: MEBESRect = tile.Area; result.ChangeRect[area, $covered]};
nTile: CStitching.Tile = tile;
nTileArea: MEBESRect = nTile.Area;
desiredNImplant: MEBESRect = CDBasics.Extend[nTileArea, maxRadialExtension];
anyInteractingPImplant: BOOLFALSE;
[] ← pDif.EnumerateArea[rect: CDBasics.Extend[nTileArea, 2*maxRadialExtension], eachTile: InteractWithPImplant];
IF NOT anyInteractingPImplant THEN result.ChangeRect[desiredNImplant, $covered]
ELSE [] ← nImplPieces.EnumerateArea[desiredNImplant, CoverNegotiatedPiece];
END;
maxRadialExtension: MEBESPixels = NARROW[spec.first, REF Nm]^/ms.mebesPixelPitch;
nDif: Tesselation ← GenerateCover[ms, spec.rest.first, extInfluenceDiameter+2*maxRadialExtension];
pDif: Tesselation ← GenerateCover[ms, spec.rest.rest.first, extInfluenceDiameter+2*maxRadialExtension];
nImplPieces: Tesselation ← NewTesselation[];
result ← NewTesselation[];
[] ← nDif.EnumerateArea[rect: CDBasics.universe, eachTile: PlaceNImplant];
nDif ← DisposeTesselation[nDif];
pDif ← DisposeTesselation[pDif];
nImplPieces ← DisposeTesselation[nImplPieces];
END;
EnlargeFn: PROC [ ms: MaskState, spec: LIST OF REF ANY, extInfluenceDiameter: Nm ← 0 ] RETURNS [ result: Tesselation ] -- CoverProc -- =
BEGIN
deltaDiameterNm: Nm = NARROW[spec.first, REF Nm]^;
deltaDiameterPixels: MEBESPixels = deltaDiameterNm/ms.mebesPixelPitch;
SELECT deltaDiameterPixels FROM
=0 => result ← GenerateCover[ms, spec.rest.first, extInfluenceDiameter];
>0 =>
BEGIN
EnlargeTile: PROC [tile: CStitching.Tile, data: REF ANY] -- CStitching.PerTileProc -- =
{result.ChangeRect[Bloat[tile.Area, deltaDiameterPixels], tile.value]};
basis: Tesselation ← GenerateCover[ms, spec.rest.first, extInfluenceDiameter+deltaDiameterNm];
result ← NewTesselation[NIL];
[] ← basis.EnumerateArea[rect: CDBasics.universe, eachTile: EnlargeTile];
basis ← DisposeTesselation[basis];
END;
<0 =>
BEGIN
EnlargeGap: PROC [tile: CStitching.Tile, data: REF ANY] -- CStitching.PerTileProc -- =
{result.ChangeRect[CDBasics.Intersection[CDBasics.universe, Bloat[tile.Area, -deltaDiameterPixels]], tile.value]};
basis: Tesselation ← GenerateCover[ms, spec.rest.first, extInfluenceDiameter-deltaDiameterNm];
result ← NewTesselation[NIL];
result.ChangeRect[CDBasics.universe, $covered];
[] ← basis.EnumerateArea[rect: CDBasics.universe, eachTile: EnlargeGap, skip: $covered];
basis ← DisposeTesselation[basis];
END;
ENDCASE => ERROR;
END;
DeNotchFn: PROC [ ms: MaskState, spec: LIST OF REF ANY, extInfluenceDiameter: Nm ← 0 ] RETURNS [ result: Tesselation ] -- CoverProc -- =
BEGIN
deltaDiams: ARRAY [-1..2] OF Nm ← ALL[0];
ndd: [0..2];
newSpec: REF;
FOR ndd𡤀, ndd+1 WHILE ndd<2 DO
WITH spec.first SELECT FROM
rnm: REF Nm => {deltaDiams[ndd] ← rnm^; spec ← spec.rest};
ENDCASE => EXIT;
ENDLOOP;
newSpec ← spec.first;
FOR i: [0..2] IN [0..ndd] DO
IF deltaDiams[i] # deltaDiams[i-1] THEN
newSpec ← LIST[$Enlarge, NEW[Nm ← (deltaDiams[i]-deltaDiams[i-1])], newSpec];
ENDLOOP;
result ← GenerateCover[ms, newSpec, extInfluenceDiameter];
END;
SizeLEqFn: PROC [ ms: MaskState, spec: LIST OF REF ANY, extInfluenceDiameter: Nm ← 0 ] RETURNS [ result: Tesselation ] -- CoverProc -- =
SizeLEq returns a tesselation of all isolated $covered rectangles from input tesselation L3 which are no larger than L1 x L2 nanometers, where L1, L2, and L3 are the elements of spec. Shapes larger than L1 x L2 nanometers, as well as non-rectangular shapes, are omitted. This was added February 27, 1986 to handle VTI's requirement to enlarge minimum size vias over diffusion. JHH.
BEGIN
sieveWidth: Nm = NARROW[spec.first, REF Nm]^;
sieveHeight: Nm = NARROW[spec.rest.first, REF Nm]^;
sieveWidthPixels: MEBESPixels = MAX[sieveWidth, sieveHeight]/ms.mebesPixelPitch;
sieveHeightPixels: MEBESPixels = MIN[sieveWidth, sieveHeight]/ms.mebesPixelPitch;
BEGIN
SizeFilterTile: PROC [tile: CStitching.Tile, data: REF ANY] -- CStitching.PerTileProc -- =
{
tileWidth: MEBESPixels;
tileHeight: MEBESPixels;
IsolatedTile: PROC [tile: CStitching.Tile] RETURNS [b:BOOLEAN] ~ {
Returns TRUE iff tile doesn't touch other tiles of the same value.
Assumes the cornerstitched plane has tiles of only two values.
en: CStitching.Tile ← tile.EN;
ws: CStitching.Tile ← tile.WS;
b ← (
(en.value # tile.value) AND (en.WEdge < tile.WEdge) AND
(ws.value # tile.value) AND (ws.EEdge > tile.EEdge)
);
};
tileWidth ← MAX[(tile.EEdge - tile.WEdge), (tile.NEdge - tile.SEdge)];
tileHeight ← MIN[(tile.EEdge - tile.WEdge), (tile.NEdge - tile.SEdge)];
IF (
IsolatedTile[tile] AND
(sieveWidthPixels >= tileWidth) AND
(sieveHeightPixels >= tileHeight)
) THEN
result.ChangeRect[rect: tile.Area, new: $covered];
};
result ← CStitching.NewTesselation[];
[] ← CStitching.EnumerateArea[
plane: GenerateCover[ms, spec.rest.rest.first, extInfluenceDiameter],
rect: CDBasics.universe,
eachTile: SizeFilterTile];
END;
END;
Init: PROC =
BEGIN
Atom.PutProp[$CDMEBESCoverProcs, $NOT, NEW[CoverProc ← NOTFn]];
Atom.PutProp[$CDMEBESCoverProcs, $AND, NEW[CoverProc ← ANDFn]];
Atom.PutProp[$CDMEBESCoverProcs, $ANDNOT, NEW[CoverProc ← ANDNOTFn]];
Atom.PutProp[$CDMEBESCoverProcs, $OR, NEW[CoverProc ← ORFn]];
Atom.PutProp[$CDMEBESCoverProcs, $MeasureRuns, NEW[CoverProc ← MeasureRuns]];
Atom.PutProp[$CDMEBESCoverProcs, $RestrictedEnlarge, NEW[CoverProc ← RestrictedEnlarge]];
Atom.PutProp[$CDMEBESCoverProcs, $Enlarge, NEW[CoverProc ← EnlargeFn]];
Atom.PutProp[$CDMEBESCoverProcs, $DeNotch, NEW[CoverProc ← DeNotchFn]];
Atom.PutProp[$CDMEBESCoverProcs, $SizeLEq, NEW[CoverProc ← SizeLEqFn]];
END;
Init[];
END. -- of CDMEBESGeomFns