Copyright © 1983, 1986 by Xerox Corporation. All rights reserved.

Written by Shand, September 12, 1983 11:40 pm PDT

Last Edited by: McCreight, November 28, 1983 5:53 pm

Last Edited by: Jacobi, February 23, 1984 3:59 pm

Last Edited by: Shand, August 6, 1984 4:16:51 am PDT

Last Edited by: Jacobi, March 19, 1986 6:50:50 pm PST

Last Edited by: Beretta, February 13, 1985 11:46:26 am PST

Commander, CStitching, IO, Process, SafeStorage;

IMPORTS Commander, CStitching, IO, Process, SafeStorage

EXPORTS CStitching =

neLimit: Pos = [x: Number.LAST, y: Number.LAST];

nwLimit: Pos = [x: Number.FIRST, y: Number.LAST];

swLimit: Pos = [x: Number.FIRST, y: Number.FIRST];

seLimit: Pos = [x: Number.LAST, y: Number.FIRST];

allSpace: Rect = [x1: Number.FIRST+1, y1: Number.FIRST, x2: Number.LAST-1, y2: Number.LAST-1];

maxSpace: Rect = [x1: allSpace.x1+1, y1: allSpace.y1+1, x2: allSpace.x2-1, y2: allSpace.y2-1];

empty: Rect = [x1: Number.LAST, y1: Number.LAST, x2: Number.FIRST, y2: Number.FIRST];

PrivateRec: TYPE = RECORD[notused: REF];

guard: REF = NEW[PrivateRec←[$CSGuard]];

deleted: REF = NEW[PrivateRec←[$CSDeleted]];

northLimit: Tile = NEW[TileRec ← [pos: nwLimit, value: guard]];

northBuffer: Tile = NEW[TileRec ← [pos: [allSpace.x1, allSpace.y2], value: guard]];

southLimit: Tile = NEW[TileRec ← [pos: swLimit, value: guard]];

eastLimit: Tile = NEW[TileRec ← [pos: seLimit, value: guard]];

westLimit: Tile = NEW[TileRec ← [pos: swLimit, value: guard]];

BEGIN

-- The stitching is not quite kosher at Guard corners.

-- Think of the guard tile as having bevelled ends

-- which fit together like a picture-frame and are stitched accordingly.

-- North-East

-- South-East

-- North-West

-- South-West

-- northBuffer

END;

BEGIN

ENABLE UNWIND => NULL;

IF disposedTiles#NIL THEN {

IF disguiseCache#NIL THEN {

END;

BEGIN

ENABLE UNWIND => NULL;

tile ← InternalNewTile[];

END;

BEGIN

IF disposedTiles#NIL THEN {

ELSE tile ← NEW[TileRec];

END;

--caller must check that it is not a current tile

--and cache the tile, this is faster than going through the garbage collector

BEGIN

ENABLE UNWIND => NULL;

tile.sW ← NIL; -- Prevent potential circular chains in the disposed cache.

tile.nE ← tile.wS ← NIL;

tile.value ← deleted;

tile.eN ← disposedTiles;

disposedTiles ← tile;

END;

BEGIN

ENABLE UNWIND => NULL;

IF disguiseCache#NIL THEN {

ELSE disguise ← NEW[Disguise];

disguise.hiddenValue ← hiddenValue;

END;

BEGIN

ENABLE UNWIND => NULL;

disguise.hiddenValue ← disguiseCache;

disguiseCache ← disguise;

END;

BEGIN

eastSpace: Tile = InternalNewTile[];

centreSpace: Tile = InternalNewTile[];

eastSpace^ ← [

centreSpace^ ← [

plane^ ← [southEast: eastSpace, current: centreSpace, data: NIL, stopFlag: plane.stopFlag, tileCount: 1];

IF plane.stopFlag=NIL THEN plane.stopFlag ← NEW[BOOL←FALSE];

END;

BEGIN

plane ← NEW[CStitching.TesselationRec←[current: NIL, southEast: NIL, stopFlag: stopFlag, data: data]];

Setup[plane];

SafeStorage.EnableFinalization[plane];

END;

--This is to help the Garbage Collector (by NILing all REFs).

BEGIN

CacheTileList: PROC [header: Tile] = {

CacheIt: TileProc = {

MySetup: ENTRY PROC [plane: Tesselation] = {

header: Tile ← NIL;

IF plane#NIL THEN {

END;

--test whether tiles have same west border, same east border and same value

RETURN [a.value=b.value AND a.pos.x=b.pos.x AND NE[a].pos.x=NE[b].pos.x]

};

BEGIN

SplitEWRunning: PROC [rider: Tile, splitY, endX: Number] =

tile: Tile;

rect.x1 ← MAX[maxSpace.x1, rect.x1];

rect.x2 ← MIN[maxSpace.x2, rect.x2];

rect.y1 ← MAX[maxSpace.y1, rect.y1];

rect.y2 ← MIN[maxSpace.y2, rect.y2];

IF rect.x1>=rect.x2 OR rect.y1>=rect.y2 THEN RETURN;

tile ← MyFindTile[plane.current, rect.x1, rect.y2];

-- tile containing nw corner (right north of area of interest)

plane.current ← tile;

SplitEWRunning[tile, rect.y2, rect.x2]; --north border

SplitEWRunning[MyFindTile[plane.current, rect.x1, rect.y1], rect.y1, rect.x2]; --south border

-- change values.

tile ← MyFindTile[plane.current, rect.x1, rect.y2-1];

DO

END;

BEGIN

DisguiseTile: TileProc =

ApplyFuncToTile: TileProc =

--ChangeEnumerateArea

EnumerateArea[plane, rect, DisguiseTile, NIL, deleted];

EnumerateArea[plane, rect, ApplyFuncToTile, data, deleted];

END;

TRUSTED BEGIN

IF tile.value#new THEN [] ← MyChangeTile[plane, tile, new]

END;

-- returns the northernmost tile intersecting the changed region.

-- (there is exactly one such tile! maximal-EW-property)

BEGIN

n: Number = NEdge[tile];

e: Number = EEdge[tile];

s: Number = SEdge[tile];

w: Number = WEdge[tile];

tWest, tEast, tNorth: Tile;

IF tile.value=new THEN RETURN [tile];

tile.value ← new;

-- restore maximal East-West strip property

-- split up tiles that horizontally abut any of the tile's four corners,

-- but extend beyond the corner in a North-South direction

--northeast corner

tEast ← NE[tile];

IF tEast.value=new AND NEdge[tEast]>n THEN [] ← NSSplit[plane, tEast, n];

--northwest corner

tWest ← tile.eN; --east now but west soon

WHILE WEdge[tWest]>=w DO tWest ← tWest.sW ENDLOOP;

-- the tile with EEdge >= w but WEdge < w.

-- In fact SEdge[tWest] < n holds only if EEdge = w

IF tWest.value=new AND SEdge[tWest]<n THEN [] ← NSSplit[plane, tWest, n];

--southwest corner

tWest ← tile.sW;

IF tWest.value=new AND SEdge[tWest]<s THEN [] ← NSSplit[plane, tWest, s];

--southeast corner

tEast ← WS[tile];

WHILE EEdge[tEast]<=e DO tEast ← NE[tEast] ENDLOOP;

-- analogous to split of northwest corner.

IF tEast.value=new AND NEdge[tEast]>s THEN [] ← NSSplit[plane, tEast, s];

-- convert the West and East adjacent tiles to maximal East-West strips

-- run South to North along the West edge

-- splitting North-South, merging East-West

tWest ← tile.sW;

WHILE NEdge[tWest]<n DO

-- tile is the northernmost strip in the changed area.

IF tWest.value=new THEN tile ← EWMerge[plane, tWest, tile];

-- now any maximal-EW-property violations of tile are confined to its Eastern border.

-- however, some merges at the northern and southern borders may be pending.

-- run North to South along the East edge splitting North-South any tile to

-- the East which abuts more than one new tile in the changed area.

tEast ← NE[tile];

WHILE SEdge[tEast]>s DO

--I SEdge[tEast]<=s

-- run South to North along the East edge

-- splitting North-South, merging East-West; eventually merging North-South..

tNorth ← tEast.sW; --not yet north..

WHILE NEdge[tNorth]<=s DO tNorth ← tNorth.eN ENDLOOP;

DO

IF EWCompatible[tile, tNorth] THEN [] ← NSMerge[plane, tile, tNorth];

RETURN [tile]

END;

-- Relies on the Maximal East-West strip property.

BEGIN

rect.x1 ← MAX[maxSpace.x1, rect.x1];

rect.x2 ← MIN[maxSpace.x2, rect.x2];

rect.y1 ← MAX[maxSpace.y1, rect.y1];

rect.y2 ← MIN[maxSpace.y2, rect.y2];

IF rect.x1>rect.x2 OR rect.y1>rect.y2 THEN RETURN [TRUE];

plane.current ← MyFindTile[plane.current, rect.x1, rect.y1];

FOR tile: Tile ← plane.current, Above[tile, rect.x1] WHILE SEdge[tile]<rect.y2 DO

RETURN [TRUE]

END;

-- relies on the Maximal East-West strip property.

BEGIN

tile: Tile;

rect.x1 ← MAX[maxSpace.x1, rect.x1];

rect.x2 ← MIN[maxSpace.x2, rect.x2];

rect.y1 ← MAX[maxSpace.y1, rect.y1];

rect.y2 ← MIN[maxSpace.y2, rect.y2];

IF rect.x1>rect.x2 OR rect.y1>rect.y2 THEN RETURN [empty];

--find south west corner

plane.current ← MyFindTile[plane.current, rect.x1, rect.y1];

FOR tile ← plane.current, Above[tile, rect.x1] DO

bBox.y1 ← MAX[SEdge[tile], rect.y1];

WHILE SEdge[tile]<rect.y2 DO

--find north east corner by going up starting at the south east corner

tile ← MyFindTile[plane.current, rect.x2-1, rect.y1];

WHILE SEdge[tile]<rect.y2 DO

END;

-- Uses the tiles own links to maintain an implicit stack of tiles.

-- Enumeration proceeds in a manner which ensures that a tiles nE and eN

-- pointers will never be needed once that tile has appeared in the enumeration;

-- this fact is exploited in ResetTesselation.

-- Defn: b is a's child iff b.sW = a.

BEGIN

IsChild: PROC [me: Tile, you: Tile] RETURNS [BOOL] = INLINE {

IsBrother: PROC [me: Tile, you: Tile] RETURNS [BOOL] = INLINE {

tile, visit: Tile;

doneSouthEastTile: BOOL ← FALSE;

rect.x1 ← MAX[maxSpace.x1, rect.x1];

rect.x2 ← MIN[maxSpace.x2, rect.x2];

rect.y1 ← MAX[maxSpace.y1, rect.y1];

rect.y2 ← MIN[maxSpace.y2, rect.y2];

IF rect.x1>=rect.x2 OR rect.y1>=rect.y2 THEN RETURN;

tile ← MyFindTile[plane.current, rect.x1, rect.y2];

-- correct for one off error when rect.y2 lies at tile boundary (YUK)

IF SEdge[tile]=rect.y2 AND SEdge[tile]>rect.y1 THEN tile ← Below[tile, rect.x1];

plane.current ← tile;

--a tile is visited only after all its children

WHILE ~doneSouthEastTile DO

END;

BEGIN

PerTile: TileProc = {

EnumerateArea[plane, rect, PerTile, NIL, skip];

END;

-- assumes x is within tile (i.e. WEdge[tile] <= x & EEdge[tile] > x)

BEGIN

t ← WS[tile];

WHILE NE[t].pos.x<=x DO t ← NE[t] ENDLOOP;

END;

-- assumes x is within tile (i.e. WEdge[tile] <= x & EEdge[tile] > x)

BEGIN

t ← tile.eN;

WHILE t.pos.x>x DO t ← t.sW ENDLOOP;

END;

BEGIN

pos.x ← MIN[maxSpace.x2, pos.x];

pos.y ← MIN[maxSpace.y2, pos.y];

tile ← MyFindTile[current: plane.current, x: pos.x, y: pos.y];

IF tile.value=guard THEN ERROR;

plane.current ← tile;

END;

--a-symmetric

TRUSTED BEGIN

IF current.value=deleted THEN ERROR UseOfAlreadyDeletedTile;

DO

RETURN [current]

END;

-- the East tile will be the new one.

-- x is west point in new east tile.

BEGIN

t: Tile;

east ← NewTile[];

IF WEdge[tile]>=x OR EEdge[tile]<= x THEN ERROR;

-- east starts out a replica of tile

east^ ← tile^;

plane.tileCount ← plane.tileCount + 1;

-- Fix the tiles relative to each other.

tile.nE ← RtoP[east];

east.sW ← tile;

east.pos.x ← x;

-- Fix North boundary

t ← east.eN;

WHILE t.pos.x>=x DO t.wS ← RtoP[east]; t ← t.sW ENDLOOP;

tile.eN ← t;

-- Fix East boundary

t ← NE[east];

WHILE t.sW=tile DO t.sW ← east; t ← WS[t] ENDLOOP;

-- Fix South boundary

t ← Below[tile, x];

east.wS ← RtoP[t];

WHILE t.eN=tile DO t.eN ← east; t ← NE[t] ENDLOOP;

RETURN [east]

END;

-- the North tile will be the new one.

-- y is south point of new north tile

BEGIN

t: Tile;

north ← NewTile[];

IF SEdge[tile]>=y OR NEdge[tile]<=y THEN ERROR;

-- north starts out a replica of tile

north^ ← tile^;

plane.tileCount ← plane.tileCount + 1;

-- Fix the tiles relative to each other.

tile.eN ← north;

north.wS ← RtoP[tile];

north.pos.y ← y;

-- Fix East boundary

t ← NE[north];

WHILE t.pos.y>=y DO t.sW ← north; t ← WS[t] ENDLOOP;

tile.nE ← RtoP[t];

-- Fix North boundary

t ← north.eN;

WHILE t.wS=RtoP[tile] DO t.wS ← RtoP[north]; t ← t.sW ENDLOOP;

-- Fix West boundary

t ← tile.sW;

WHILE t.eN.pos.y<=y DO t ← t.eN ENDLOOP;

north.sW ← t;

WHILE NE[t]=tile DO t.nE ← RtoP[north]; t ← t.eN ENDLOOP;

RETURN [north]

END;

-- The East tile will be deallocated.

-- The caller must assure that tileW.value=tileE.value and that the tiles really

-- do have a common border of equal length.

BEGIN

--checks

IF tileE.sW#tileW OR NE[tileW]#tileE OR tileW.pos.y#tileE.pos.y OR tileW.eN.pos.y#tileE.eN.pos.y OR tileW.value#tileE.value THEN ERROR;

-- Fix the tiles relative to each other.

tileW.eN ← tileE.eN;

tileW.nE ← tileE.nE;

-- Fix North boundary

FOR t: Tile ← tileW.eN, t.sW WHILE WS[t]=tileE DO t.wS ← RtoP[tileW] ENDLOOP;

-- Fix East boundary

FOR t: Tile ← NE[tileW], WS[t] WHILE t.sW=tileE DO t.sW ← tileW ENDLOOP;

-- Fix South boundary

FOR t: Tile ← WS[tileE], NE[t] WHILE t.eN=tileE DO t.eN ← tileW ENDLOOP;

IF plane.current=tileE THEN plane.current ← tileW;

DisposeTile[tileE];

plane.tileCount ← plane.tileCount - 1;

RETURN [tileW];

END;

-- the north tile will be deallocated.

-- the caller must assure that tileS.value=tileN.value and that the tiles really

-- do have a common border of equal length.

BEGIN

--checks

IF WS[tileN]#tileS OR tileS.eN#tileN OR tileS.pos.x#tileN.pos.x OR NE[tileS].pos.x#NE[tileN].pos.x OR tileS.value#tileN.value THEN ERROR;

-- Fix the tiles relative to each other.

tileS.nE ← tileN.nE;

tileS.eN ← tileN.eN;

-- Fix East boundary

FOR t: Tile ← NE[tileS], WS[t] WHILE t.sW=tileN DO t.sW ← tileS ENDLOOP;

-- Fix North boundary

FOR t: Tile ← tileS.eN, t.sW WHILE WS[t]=tileN DO t.wS ← RtoP[tileS] ENDLOOP;

-- Fix West boundary

FOR t: Tile ← tileN.sW, t.eN WHILE NE[t]=tileN DO t.nE ← RtoP[tileS] ENDLOOP;

IF plane.current=tileN THEN plane.current ← tileS;

DisposeTile[tileN];

plane.tileCount ← plane.tileCount - 1;

RETURN [tileS];

END;

TRUSTED { RETURN [LOOPHOLE[r]] }

};

cmd.out.PutRope["CornerStiching loaded\n"];

};

BEGIN

ENABLE UNWIND => NULL;

InternalDispose: TileProc =

header: Tile ← NIL;

IF plane.current#NIL THEN EnumerateArea[plane, maxSpace, InternalDispose, NIL, deleted];

plane.current ← plane.southEast ← NIL;

plane.data ← NIL;

WHILE header#NIL DO

END;

BEGIN

DO

END;

Formatting

MyFindTile completely rewritten

Correct comments when which procedure is valid included in definition

EnumerateArea and ListArea made two procedures whith simpler parameters

maxSpace introduced,

finalization introduced

comments, invariants, shorter,

bug correction in ChangeTile,

Below, WS, NE introduced

better names,

better parameters