CornerStitchingImpl.mesa
Copyright © 1983, 1985 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, May 28, 1985 5:59:03 pm PDT
Last Edited by: Beretta, February 13, 1985 11:46:26 am PST
DIRECTORY
CornerStitching;
CornerStitchingImpl:
CEDAR
MONITOR
EXPORTS CornerStitching =
BEGIN
Tesselation: TYPE = CornerStitching.Tesselation;
Tile: TYPE = CornerStitching.Tile;
Number: TYPE = CornerStitching.Number;
Coord: TYPE = CornerStitching.Coord;
Rect: TYPE = CornerStitching.Rect;
NEdge: PROCEDURE [t: REF Tile] RETURNS [Number] = INLINE {RETURN [t.en.pos.y]};
EEdge: PROCEDURE [t: REF Tile] RETURNS [Number] = INLINE {RETURN [PtoR[t.ne].pos.x]};
SEdge: PROCEDURE [t: REF Tile] RETURNS [Number] = INLINE {RETURN [t.pos.y]};
WEdge: PROCEDURE [t: REF Tile] RETURNS [Number] = INLINE {RETURN [t.pos.x]};
-- Error Codes
TileValue: PUBLIC ERROR = CODE;
TileDeleted: PUBLIC ERROR = CODE;
DegenerateTile: ERROR = CODE;
-- Co-ordinates at "infinity"
neLimitCoord: Coord = [x: Number.LAST, y: Number.LAST];
nwLimitCoord: Coord = [x: Number.FIRST, y: Number.LAST];
swLimitCoord: Coord = [x: Number.FIRST, y: Number.FIRST];
seLimitCoord: Coord = [x: Number.LAST, y: Number.FIRST];
emptyRect: Rect = [x1: Number.FIRST+1, y1: Number.FIRST, x2: Number.LAST-1, y2: Number.LAST-1];
-- House-keeping tile values to flag deleted tiles and tiles at "infinity"
guard: REF ANY = $CornerStitchingPrivateEdgeGuard;
deleted: REF ANY = $CornerStitchingPrivateDeletedTile;
-- Border Tiles (shared by all tesselations)
northLimit: REF Tile = NEW[Tile ← [pos: nwLimitCoord, value: guard]];
northBuffer: REF Tile = NEW[Tile ← [pos: [emptyRect.x1, emptyRect.y2], value: guard]];
southLimit: REF Tile = NEW[Tile ← [pos: swLimitCoord, value: guard]];
eastLimit: REF Tile = NEW[Tile ← [pos: seLimitCoord, value: guard]];
westLimit: REF Tile = NEW[Tile ← [pos: swLimitCoord, value: guard]];
InitTesselationBorderTiles:
PROCEDURE =
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
northLimit.ne ← RtoP[eastLimit];
eastLimit.en ← northLimit;
-- South-East
southLimit.en ← eastLimit;
southLimit.ne ← RtoP[eastLimit];
eastLimit.ws ← RtoP[southLimit];
eastLimit.sw ← southLimit;
-- North-West
westLimit.ne ← RtoP[northLimit];
westLimit.en ← northLimit;
northLimit.sw ← westLimit;
northLimit.ws ← RtoP[westLimit];
-- South-West
southLimit.sw ← westLimit;
westLimit.ws ← RtoP[southLimit];
-- northBuffer
northBuffer.en ← northLimit;
northBuffer.ne ← RtoP[eastLimit];
northBuffer.sw ← westLimit;
northBuffer.ws ← NIL;
END;
Disguise:
TYPE =
RECORD [
hiddenValue: REF ANY
];
disposedTiles: REF Tile ← NIL;
disguiseCache: REF Disguise ← NIL;
DumpCache:
PUBLIC
ENTRY
PROCEDURE =
BEGIN
ENABLE UNWIND => NULL;
IF disposedTiles#
NIL
THEN {
lag: REF Tile ← disposedTiles;
FOR tc:
REF Tile ← disposedTiles.en, tc.en
WHILE tc#
NIL
DO
lag.en ← NIL;
lag ← tc
ENDLOOP;
disposedTiles ← NIL
};
IF disguiseCache#
NIL
THEN {
lag: REF Disguise ← disguiseCache;
FOR dc:
REF Disguise ←
NARROW[disguiseCache.hiddenValue],
NARROW[dc.hiddenValue]
WHILE dc #
NIL
DO
lag.hiddenValue ← NIL;
lag ← dc
ENDLOOP;
disguiseCache ← NIL
};
END;
NewTile:
ENTRY
PROCEDURE
RETURNS [tile:
REF Tile] =
BEGIN
ENABLE UNWIND => NULL;
IF disposedTiles#
NIL
THEN {
tile ← disposedTiles;
disposedTiles ← disposedTiles.en;
}
ELSE tile ← NEW[Tile];
END;
DisposeTile:
ENTRY
PROCEDURE [tile:
REF 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;
NewDisguise:
ENTRY
PROCEDURE [hiddenValue:
REF←NIL]
RETURNS [disguise:
REF Disguise] =
BEGIN
ENABLE UNWIND => NULL;
IF disguiseCache#
NIL
THEN {
disguise ← disguiseCache;
disguiseCache ← NARROW[disguiseCache.hiddenValue];
}
ELSE disguise ← NEW[Disguise];
disguise.hiddenValue ← hiddenValue;
END;
DisposeDisguise:
ENTRY
PROCEDURE [disguise:
REF Disguise] =
BEGIN
ENABLE UNWIND => NULL;
disguise.hiddenValue ← disguiseCache;
disguiseCache ← disguise;
END;
NewTesselation:
PUBLIC
PROCEDURE [data:
REF←
NIL, stopFlag:
REF
BOOL←
NIL]
RETURNS [REF Tesselation] =
BEGIN
eastSpace: REF Tile = NewTile[];
centreSpace: REF Tile = NewTile[];
IF stopFlag=NIL THEN stopFlag ← NEW[BOOL←FALSE];
eastSpace^ ← [
en: northBuffer, ne: RtoP[eastLimit], sw: centreSpace, ws: RtoP[southLimit],
pos: [emptyRect.x2, emptyRect.y1],
value: guard
];
centreSpace^ ← [
en: northBuffer, ne: RtoP[eastSpace], sw: westLimit, ws: RtoP[southLimit],
pos: [emptyRect.x1, emptyRect.y1],
value: NIL
];
RETURN [NEW[Tesselation ← [southEast: eastSpace, current: centreSpace, data: data, stopFlag: stopFlag]]]
END;
FreeTesselation:
PUBLIC
PROCEDURE [plane:
REF Tesselation, freeCache:
BOOLEAN ←
TRUE] =
BEGIN
CacheIt: CornerStitching.PerTileProc =
[tile: REF Tile, data: REF ANY] RETURNS [REF ANY] --
-- Depends on fact that Enumeration proceeds NE to SW, so en ref may be clobbered by caching process.
BEGIN
DisposeTile[tile];
END;
When freeing the tile cache as well as the tesselation, the tesselation's tiles are first added to the cache, and then the cache is dumped. This is to help the Garbage Collector (by NILing all REFs).
[] ← EnumerateArea[plane, [x1~Number.FIRST/2, y1~Number.FIRST/2, x2~Number.LAST/2, y2~Number.LAST/2], CacheIt, NIL, deleted];
plane.current ← plane.southEast ← NIL;
IF freeCache
THEN
DumpCache[];
plane.tilesInTesselationCount ← 0
END;
ChangeRect:
PUBLIC
PROCEDURE [plane:
REF Tesselation, rect: Rect, newValue:
REF
ANY ←
NIL] =
BEGIN
SplitEWRunningBorder:
PROCEDURE [StartTile:
REF Tile, splitLine, lineEndpoint: Number] =
INLINE BEGIN
boundaryRider: REF Tile ← StartTile;
WHILE WEdge[boundaryRider]<lineEndpoint
DO
WHILE SEdge[boundaryRider]>splitLine
DO
boundaryRider ← PtoR[boundaryRider.ws]
ENDLOOP;
-- The second clause here is necessary to avoid splitting tiles which will never be repaired by changeTile, and will thus not be made maximal north-south. Its kind of subtle, and probably more than a little ugly, but I can probably prove its correct if pressed.
IF SEdge[boundaryRider]<splitLine
AND (boundaryRider.value#newValue
OR EEdge[boundaryRider]<lineEndpoint)
THEN
-- This tile straddles the border, chop chop.
boundaryRider ← NSSplit[ plane, boundaryRider, splitLine];
boundaryRider ← PtoR[boundaryRider.ne]
ENDLOOP;
END;
tile: REF Tile ← FindTileContainingPoint[plane.current, rect.x1, rect.y2];
-- tile contains nw corner (sort of!)
plane.current ← tile;
SplitEWRunningBorder[tile, rect.y2, rect.x2]; --north border
SplitEWRunningBorder[FindTileContainingPoint[plane.current, rect.x1, rect.y1],
rect.y1, rect.x2]; --south border
-- Now we start gobbling up all the tiles into wide flat bands of newValue.
tile ← FindTileContainingPoint[plane.current, rect.x1, rect.y2-1];
-- First get our western border tile into shape.
DO
IF tile.value # newValue
AND WEdge[tile] < rect.x1
THEN {
outsideTile: REF Tile;
tile ← EWSplit[plane, tile, rect.x1];
outsideTile ← tile.sw;
-- Better make sure we keep outside tile in order NS-wise.
IF outsideTile.value=outsideTile.en.value
AND WEdge[outsideTile]=WEdge[outsideTile.en]
AND EEdge[outsideTile]=EEdge[outsideTile.en]
THEN
outsideTile ← NSMerge[plane, outsideTile, outsideTile.en];
IF outsideTile.value=PtoR[outsideTile.ws].value
AND WEdge[outsideTile]=WEdge[PtoR[outsideTile.ws]]
AND EEdge[outsideTile]=EEdge[PtoR[outsideTile.ws]]
THEN
outsideTile ← NSMerge[plane, PtoR[outsideTile.ws], outsideTile]
};
DO
IF tile.value#newValue
THEN {
IF EEdge[tile]>rect.x2
THEN {
outsideTile: REF Tile;
outsideTile ← EWSplit[plane, tile, rect.x2];
IF outsideTile.value=outsideTile.en.value
AND WEdge[outsideTile]=WEdge[outsideTile.en]
AND EEdge[outsideTile] = EEdge[outsideTile.en]
THEN
outsideTile ← NSMerge[plane, outsideTile, outsideTile.en];
IF outsideTile.value=PtoR[outsideTile.ws].value
AND WEdge[outsideTile]=WEdge[PtoR[outsideTile.ws]]
AND EEdge[outsideTile]=EEdge[PtoR[outsideTile.ws]]
THEN
outsideTile ← NSMerge[plane, PtoR[outsideTile.ws], outsideTile]
};
tile ← ChangeTile[plane, tile, newValue]
};
IF EEdge[tile]>=rect.x2 THEN EXIT;
tile ← PtoR[tile.ne];
WHILE SEdge[tile]>=rect.y2
DO
tile ← PtoR[tile.ws]
ENDLOOP; -- EMM
ENDLOOP;
IF WEdge[tile]>rect.x1 THEN ERROR;
IF SEdge[tile]<=rect.y1 THEN EXIT;
tile ← PtoR[tile.ws];
WHILE EEdge[tile]<=rect.x1
DO
tile ← PtoR[tile.ne]
ENDLOOP
ENDLOOP
END;
FuncChangeRect:
PUBLIC
PROCEDURE [plane:
REF Tesselation,
rect: Rect,
perTile: CornerStitching.PerTileChangeProc,
data: REF ANY ← NIL] =
BEGIN
DisguiseTile: CornerStitching.PerTileProc =
-- [tile: REF Tile, data: REF ANY] RETURNS [REF ANY]
BEGIN
tile.value ← NewDisguise[tile.value];
END;
ApplyFuncToTile: CornerStitching.PerTileProc =
--[tile: REF Tile, data: REF ANY] RETURNS [REF ANY]
BEGIN
disguise: REF Disguise = NARROW[tile.value];
clippedBB: Rect = [
MAX[WEdge[tile], rect.x1],
MAX[SEdge[tile], rect.y1],
MIN[EEdge[tile], rect.x2],
MIN[NEdge[tile], rect.y2]
]; -- Clip tile against Enumeration's bounding box
-- Restore tile value
[] ← ChangeTile[plane: plane, tile: tile, newValue: disguise.hiddenValue];
-- Call user perTile function
perTile[plane: plane, rect: clippedBB, oldValue: disguise.hiddenValue, data: data];
DisposeDisguise[disguise];
END;
--FuncChangeRect
[] ← EnumerateArea[plane, rect, DisguiseTile, NIL, deleted];
[] ← EnumerateArea[plane, rect, ApplyFuncToTile, data, deleted];
END;
ChangeTile:
PROCEDURE [plane:
REF Tesselation, tile:
REF Tile, newValue:
REF
ANY ←
NIL]
RETURNS [
REF Tile] =
-- Returns the northernmost tile in the changed region. (There is only one such tile by the maximal-EW-property)
BEGIN
north: Number = NEdge[tile];
east: Number = EEdge[tile];
south: Number = SEdge[tile];
west: Number = WEdge[tile];
tWest, tEast, tNorth: REF Tile;
tile.value ← newValue;
-- Give tile newValue, then restore maximal East-West strip property
-- First we tidy up any newValue tiles that abut any of the tile's four corners,
-- but extend beyond the corner in a North-South direction
tEast ← PtoR[tile.ne];
IF tEast.value=newValue AND NEdge[tEast]>north THEN [] ← NSSplit[plane, tEast, north];
tWest ← tile.en;
WHILE WEdge[tWest]>=west
DO
tWest ← tWest.sw
ENDLOOP;
-- Now we are at the tile whose east EEdge is >= west but whose WEdge is < west.
-- In fact SEdge[tWest] < north will only hold if EEdge = west
IF tWest.value=newValue AND SEdge[tWest]<north THEN [] ← NSSplit[plane, tWest, north];
tWest ← tile.sw;
IF tWest.value=newValue AND SEdge[tWest]<south THEN [] ← NSSplit[plane, tWest, south];
tEast ← PtoR[tile.ws];
WHILE EEdge[tEast]<=east
DO
tEast ← PtoR[tEast.ne]
ENDLOOP;
-- Analogous to split of NW corner.
IF tEast.value=newValue AND NEdge[tEast]>south THEN [] ← NSSplit[plane, tEast, south];
-- Now we convert the West and East adjacent tiles to maximal East-West strips
-- First run South to North along the West edge splitting North-South, and merging East-West the newValue tile created from the tile being changed.
tWest ← tile.sw;
WHILE NEdge[tWest]<north
DO
IF tWest.value#newValue AND tWest.en.value#newValue THEN tWest ← tWest.en
ELSE {
tile ← NSSplit[plane, tile, NEdge[tWest]];
IF tWest.value=newValue THEN [] ← EWMerge[plane, tWest, PtoR[tWest.ne]];
tWest ← tile.sw;
}
ENDLOOP;
-- tile is the northernmost strip in the changed area.
IF tWest.value=newValue THEN tile ← EWMerge[plane, tWest, tile];
-- Now any maximal-EW-property violations of tile are confined to its Eastern border.
-- There may however still be some pending merges at the northern and southern borders.
-- Run North to South along the East edge splitting North-South any newValue tile to
-- the East which abuts more than one newValue tile in the changed area.
tEast ← PtoR[tile.ne];
WHILE SEdge[tEast]>south
DO
tile ← tEast.sw;
IF (tEast.value=newValue
OR PtoR[tEast.ws].value=newValue)
AND SEdge[tile]<SEdge[tEast]
THEN
[] ← NSSplit[plane, tile, SEdge[tEast]];
tEast ← PtoR[tEast.ws]
ENDLOOP;
-- Then run South to North along the East edge splitting North-South,
-- and merging East-West the newValue tiles created from the tile being changed.
tNorth ← tEast.sw;
WHILE NEdge[tNorth]<=south
DO
tNorth ← tNorth.en;
ENDLOOP;
DO
tile ← tNorth;
tNorth ← tNorth.en;
IF PtoR[tile.ne].value=newValue
THEN {
IF tile.ne=tNorth.ne THEN [] ← NSSplit[plane, PtoR[tile.ne], NEdge[tile]];
tile ← EWMerge[plane, tile, PtoR[tile.ne]]
};
IF tile.value=PtoR[tile.ws].value
AND WEdge[tile]=WEdge[PtoR[tile.ws]]
AND EEdge[tile]=EEdge[PtoR[tile.ws]]
THEN
tile ← NSMerge[plane, PtoR[tile.ws], tile];
IF NEdge[tNorth]>north THEN EXIT
ENDLOOP;
IF tile.value=tNorth.value
AND WEdge[tile]=WEdge[tNorth]
AND EEdge[tile]=EEdge[tNorth]
THEN
[] ← NSMerge[plane, tile, tNorth];
RETURN [tile]
END;
AreaEmpty:
PUBLIC
PROCEDURE [plane:
REF Tesselation, rect: Rect, backgroundValue:
REF
ANY ←
NIL]
RETURNS [
BOOLEAN] =
-- Return TRUE if all tiles in area are of value backgroundValue, else FALSE.
-- Relies on the Maximal East-West strip property.
BEGIN
plane.current ← FindTileContainingPoint[plane.current, rect.x1, rect.y1];
FOR tile:
REF Tile ← plane.current, TileAbove[tile, rect.x1]
WHILE SEdge[tile]<rect.y2
DO
IF tile.value#backgroundValue OR EEdge[tile]<rect.x2 THEN RETURN [FALSE]
ENDLOOP;
RETURN [TRUE]
END;
ContentsBound:
PUBLIC
PROCEDURE [plane:
REF Tesselation, rect: Rect, backgroundValue:
REF
ANY ←
NIL]
RETURNS [bBox: Rect] =
-- ContentsBound returns a minimal bounding box for non-backgroundValue
-- tiles in rect.
-- Relies on the Maximal East-West strip property.
BEGIN
tile: REF Tile;
bBox ← [x1~Number.LAST, y1~Number.LAST, x2~Number.FIRST, y2~Number.FIRST];
IF rect.x1=rect.x2 THEN ERROR DegenerateTile;
plane.current ← FindTileContainingPoint[plane.current, rect.x1, rect.y1];
FOR tile ← plane.current, TileAbove[tile, rect.x1]
DO
IF SEdge[tile]>=rect.y2 THEN RETURN; -- Tile is empty
IF tile.value#backgroundValue OR EEdge[tile]<rect.x2 THEN EXIT
ENDLOOP;
bBox.y1 ← MAX[SEdge[tile], rect.y1];
WHILE SEdge[tile]<rect.y2
DO
IF tile.value#backgroundValue
THEN {
bBox.x1 ← rect.x1;
EXIT
};
-- else the east edge of tile must abut a non-backgroundValue tile (by the Maximal East-West strip property)
IF EEdge[tile]<rect.x2 AND EEdge[tile]<bBox.x1 THEN bBox.x1 ← EEdge[tile];
tile ← TileAbove[tile, rect.x1];
ENDLOOP;
tile ← FindTileContainingPoint[plane.current, rect.x2-1, rect.y1];
WHILE SEdge[tile]<rect.y2
DO
-- Note FindTileContainingPoint is assymetric so code is different here!
-- (This is the cause of the ugly .PREDs)
IF tile.value#backgroundValue
THEN {
bBox.x2 ← rect.x2;
bBox.y2 ← NEdge[tile]
}
ELSE
IF WEdge[tile]>rect.x1
THEN {
IF WEdge[tile]>bBox.x2 THEN bBox.x2 ← WEdge[tile];
bBox.y2 ← NEdge[tile]
};
tile ← TileAbove[tile, rect.x2-1];
ENDLOOP;
END;
EnumerateArea:
PUBLIC
PROCEDURE [plane:
REF Tesselation, rect: Rect, perTile: CornerStitching.PerTileProc ←
NIL, data:
REF
ANY ←
NIL, backgroundValue:
REF
ANY ←
NIL]
RETURNS [
REF
ANY] =
-- 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 FreeTesselation.
-- Defn: b is a's child iff b.sw = a.
BEGIN
IsChildOf:
PROCEDURE [ me:
REF Tile, you:
REF Tile]
RETURNS [
BOOLEAN] =
INLINE {
RETURN [you.sw=me AND SEdge[you]>rect.y1];
};
IsBrotherOf:
PROCEDURE [ me:
REF Tile, you:
REF Tile]
RETURNS [
BOOLEAN] =
INLINE {
RETURN [me.sw=you.sw AND SEdge[you]>rect.y1];
};
tileEnumeration: LIST OF REF CornerStitching.Region ← NIL;
tile: REF Tile ← FindTileContainingPoint[plane.current, rect.x1, rect.y2];
doneSouthEastTile: BOOLEAN ← FALSE;
-- 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 ← PtoR[tile.ws];
WHILE EEdge[tile]<=rect.x1
DO
tile ← PtoR[tile.ne]
ENDLOOP;
};
plane.current ← tile;
WHILE ~doneSouthEastTile
DO
seeking: {youth, experience, nothing} ← youth;
DO
prevT: REF Tile;
IF seeking=youth
THEN {
child: REF Tile ← PtoR[tile.ne];
WHILE SEdge[child]>=rect.y2
DO
child ← PtoR[child.ws]
ENDLOOP;
IF IsChildOf[tile, child]
AND WEdge[child]<rect.x2
THEN {
tile ← child;
LOOP
}
ELSE seeking ← experience
};
prevT ← tile;
-- Is tile a border tile?
IF WEdge[tile]<=rect.x1
OR SEdge[tile]<=rect.y1
THEN {
-- Find next border tile, i.e. next tree root
seeking ← nothing;
IF SEdge[tile]>rect.y1
THEN {
tile ← PtoR[tile.ws];
WHILE EEdge[tile]<=rect.x1
DO
tile ← PtoR[tile.ne]
ENDLOOP
}
ELSE {
IF EEdge[tile]>=rect.x2 THEN doneSouthEastTile ← TRUE
ELSE {
tile ← PtoR[tile.ne];
WHILE SEdge[tile]>rect.y1
DO
tile ← PtoR[tile.ws]
ENDLOOP;
}
}
}
ELSE {
IF IsBrotherOf[tile, PtoR[tile.ws]]
THEN {
tile ← PtoR[tile.ws];
seeking ← youth
}
ELSE tile ← tile.sw;
};
IF prevT.value#backgroundValue
THEN {
IF perTile#NIL THEN perTile[prevT, data]
ELSE tileEnumeration ← CONS[NEW[ CornerStitching.Region ← [
[ MAX[WEdge[prevT], rect.x1], MAX[SEdge[prevT], rect.y1], MIN[EEdge[prevT], rect.x2], MIN[NEdge[prevT], rect.y2]],
prevT.value] ], tileEnumeration];
};
IF seeking=nothing THEN EXIT
ENDLOOP
ENDLOOP;
IF perTile=NIL THEN data ← tileEnumeration;
RETURN [data]
END;
TileAbove:
PROCEDURE [tile:
REF Tile, x: Number]
RETURNS [
REF Tile] =
-- Assumes x is within tile (i.e. WEdge[tile] <= x & EEdge[tile] > x)
BEGIN
IF WEdge[tile]>x OR EEdge[tile]<=x THEN ERROR;
tile ← tile.en;
WHILE WEdge[tile]>x
DO
tile ← tile.sw;
ENDLOOP;
RETURN [tile]
END;
lastm1: Number = Number.LAST-2;
TileAt:
PUBLIC
PROCEDURE [plane:
REF Tesselation, pos: Coord]
RETURNS [tile:
REF Tile] =
BEGIN
tile ← FindTileContainingPoint[plane.current, MIN[lastm1, pos.x], MIN[lastm1, pos.y]];
IF tile=northBuffer THEN ERROR;
plane.current ← tile;
END;
FindTileContainingPoint:
PROCEDURE [tile:
REF Tile, x, y: Number]
RETURNS [
REF Tile] =
--a-symmetric
TRUSTED BEGIN
IF tile.value=deleted THEN ERROR TileDeleted;
DO
--south-- WHILE y<tile.pos.y DO tile ← LOOPHOLE[tile.ws] ENDLOOP;
--north-- WHILE y>=tile.en.pos.y DO tile ← tile.en ENDLOOP;
IF x<tile.pos.x
THEN
--west--
WHILE x<tile.pos.x DO tile ← tile.sw ENDLOOP
ELSE
IF x>=tile.ne.pos.x
THEN
--east--
WHILE x>=tile.ne.pos.x DO tile ← LOOPHOLE[tile.ne] ENDLOOP
ELSE EXIT
ENDLOOP;
RETURN [tile]
END;
EWSplit:
PROCEDURE [plane:
REF Tesselation, tile:
REF Tile, x: Number]
RETURNS [
REF Tile] =
-- The East one will be the new one.
BEGIN
eastTile: REF Tile ← NewTile[];
t: REF Tile;
IF WEdge[tile]>=x OR EEdge[tile]<= x THEN ERROR;
-- eastTile starts out a replica of tile
eastTile^ ← tile^;
plane.tilesInTesselationCount ← plane.tilesInTesselationCount + 1;
-- Fix the tiles relative to each other.
tile.ne ← RtoP[eastTile];
eastTile.sw ← tile;
eastTile.pos.x ← x;
-- Fix North boundary
t ← eastTile.en;
WHILE t.pos.x>=x
DO
t.ws ← RtoP[eastTile];
t ← t.sw
ENDLOOP;
tile.en ← t;
-- Fix East boundary
t ← PtoR[eastTile.ne];
WHILE t.sw=tile
DO
t.sw ← eastTile;
t ← PtoR[t.ws]
ENDLOOP;
-- Fix South boundary
t ← PtoR[tile.ws];
WHILE PtoR[t.ne].pos.x<=x
DO
t ← PtoR[t.ne]
ENDLOOP;
eastTile.ws ← RtoP[t];
WHILE t.en=tile
DO
t.en ← eastTile;
t ← PtoR[t.ne]
ENDLOOP;
RETURN [eastTile]
END;
NSSplit:
PROCEDURE [plane:
REF Tesselation, tile:
REF Tile, y: Number]
RETURNS [
REF Tile] =
-- The North one will be the new one.
BEGIN
northTile: REF Tile ← NewTile[];
t: REF Tile;
IF SEdge[tile]>=y OR NEdge[tile]<=y THEN ERROR;
-- northTile starts out a replica of tile
northTile^ ← tile^;
plane.tilesInTesselationCount ← plane.tilesInTesselationCount + 1;
-- Fix the tiles relative to each other.
tile.en ← northTile;
northTile.ws ← RtoP[tile];
northTile.pos.y ← y;
-- Fix East boundary
t ← PtoR[northTile.ne];
WHILE t.pos.y>=y
DO
t.sw ← northTile;
t ← PtoR[t.ws]
ENDLOOP;
tile.ne ← RtoP[t];
-- Fix North boundary
t ← northTile.en;
WHILE t.ws=RtoP[tile]
DO
t.ws ← RtoP[northTile];
t ← t.sw
ENDLOOP;
-- Fix West boundary
t ← tile.sw;
WHILE t.en.pos.y<=y
DO
t ← t.en
ENDLOOP;
northTile.sw ← t;
WHILE PtoR[t.ne]=tile
DO
t.ne ← RtoP[northTile];
t ← t.en
ENDLOOP;
RETURN [northTile]
END;
EWMerge:
PROCEDURE [plane:
REF Tesselation, tileW, tileE:
REF Tile]
RETURNS [
REF Tile] =
-- 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 PtoR[tileW.ne]#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:
REF Tile ← tileW.en, t.sw
WHILE PtoR[t.ws]=tileE
DO
t.ws ← RtoP[tileW];
ENDLOOP;
-- Fix East boundary
FOR t:
REF Tile ← PtoR[tileW.ne], PtoR[t.ws]
WHILE t.sw=tileE
DO
t.sw ← tileW;
ENDLOOP;
-- Fix South boundary
FOR t:
REF Tile ← PtoR[tileE.ws], PtoR[t.ne]
WHILE t.en=tileE
DO
t.en ← tileW;
ENDLOOP;
tileE.value ← deleted;
tileE.en ← NIL;
IF plane.current=tileE THEN plane.current ← tileW;
DisposeTile[tileE];
plane.tilesInTesselationCount ← plane.tilesInTesselationCount - 1;
RETURN [tileW];
END;
NSMerge:
PROCEDURE [plane:
REF Tesselation, tileS, tileN:
REF Tile]
RETURNS [
REF Tile] =
-- 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 PtoR[tileN.ws]#tileS OR tileS.en#tileN OR tileS.pos.x#tileN.pos.x OR PtoR[tileS.ne].pos.x#PtoR[tileN.ne].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:
REF Tile ← PtoR[tileS.ne], PtoR[t.ws]
WHILE t.sw=tileN
DO
t.sw ← tileS;
ENDLOOP;
-- Fix North boundary
FOR t:
REF Tile ← tileS.en, t.sw
WHILE PtoR[t.ws]=tileN
DO
t.ws ← RtoP[tileS];
ENDLOOP;
-- Fix West boundary
FOR t:
REF Tile ← tileN.sw, t.en
WHILE PtoR[t.ne]=tileN
DO
t.ne ← RtoP[tileS];
ENDLOOP;
tileN.value ← deleted;
tileN.en ← NIL;
IF plane.current=tileN THEN plane.current ← tileS;
DisposeTile[tileN];
plane.tilesInTesselationCount ← plane.tilesInTesselationCount - 1;
RETURN [tileS];
END;
PtoR:
PROCEDURE [p:
LONG
POINTER
TO Tile]
RETURNS [
REF Tile] ~
INLINE {
TRUSTED { RETURN [LOOPHOLE[p]] }
};
RtoP:
PROCEDURE [r:
REF Tile]
RETURNS [
LONG
POINTER
TO Tile] ~
INLINE {
TRUSTED { RETURN [LOOPHOLE[r]] }
};
InitTesselationBorderTiles[]
END.
Edited on February 8, 1985 4:40:46 pm PST, by Jacobi
Formatting
Edited on February 8, 1985 4:40:46 pm PST, by Jacobi
FindTileContainingPoint rewritten