AccurateIntersectImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Greene, October 3, 1986 6:12:02 pm PDT
DIRECTORY
Basics,
Bend,
Heap,
List,
Sweep;
AccurateIntersectImpl: CEDAR PROGRAM IMPORTS Basics, Bend, Heap, List, Sweep EXPORTS Sweep =
BEGIN OPEN Sweep;
XOR: PROC [a, b: BOOL] RETURNS [BOOL] ~ INLINE {
RETURN[(a OR b) AND (NOT a OR NOT b)]
};
IntersectEvent: TYPE = REF IntersectEventRec;
IntersectEventRec: TYPE = RECORD [
time: Point,
new: BOOLEAN ← FALSE, swap: BOOLEAN ← FALSE,
isALine: BOOLEAN ← TRUE,
line: Line,
lineCarrier, lineRight: LineCarrier,
next: IntersectEvent ← NIL];
CompareLL: PROC [e1, e2: Heap.Event] RETURNS[r: Basics.Comparison] ~ {
event1: IntersectEvent ← NARROW[e1];
event2: IntersectEvent ← NARROW[e2];
r ← Basics.CompareINT[event1.time.y, event2.time.y];
IF r = equal THEN {
IF event1.swap THEN RETURN[greater];
IF event2.swap THEN RETURN[less];
IF event1.new THEN RETURN[greater];
IF event2.new THEN RETURN[less];
r ← Basics.CompareINT[event1.time.x, event2.time.x];
};
RETURN[r];
};
CompareHL: PROC [e1, e2: Heap.Event] RETURNS[r: Basics.Comparison] ~ {
event1: IntersectEvent ← NARROW[e1];
event2: IntersectEvent ← NARROW[e2];
r ← Basics.CompareINT[event1.time.y, event2.time.y];
IF r = equal THEN {
IF event1.swap THEN RETURN[greater]; --swaps
IF event2.swap THEN RETURN[less];
IF event1.new AND event1.isALine THEN RETURN[greater]; --new lines
IF event2.new AND event2.isALine THEN RETURN[less];
IF NOT event1.new AND NOT event1.isALine THEN RETURN[greater]; --old hooks
IF NOT event2.new AND NOT event2.isALine THEN RETURN[less];
IF event1.new AND NOT event1.isALine THEN { --new hooks
IF event2.new AND NOT event2.isALine THEN
RETURN[Basics.CompareINT[event1.time.x, event2.time.x]];
RETURN[greater]
};
IF event2.new AND NOT event2.isALine THEN RETURN[less];
r ← Basics.CompareINT[event1.time.x, event2.time.x]; --both must be line removals
};
RETURN[r];
};
CompareRC: PROC [e1, e2: Heap.Event] RETURNS[r: Basics.Comparison] ~ {
event1: IntersectEvent ← NARROW[e1];
event2: IntersectEvent ← NARROW[e2];
r ← ComparePoints[event1.time, event2.time];
IF r = equal THEN {
r ← IF event1.new THEN greater ELSE less;
};
RETURN[r];
};
LineCarrier: TYPE = REF LineCarrierRec;
LineCarrierRec: TYPE = RECORD[
isALine: BOOLEAN ← TRUE,
carried: Line,
lineLeft, lineRight: LineCarrier ← NIL
];
LineState: TYPE = REF LineStateRec;
LineStateRec: TYPE = RECORD[
clientState: REF ANY,
hooks: List.LORA ← NIL
];
NilCopy: PUBLIC PROC [stateIn: REF ANY] RETURNS [stateOut: REF ANY] ~ {
RETURN[stateIn]
};
NilCombine: PUBLIC PROC [state1, state2: REF ANY] RETURNS [state: REF ANY] ~ {
RETURN[NIL]
};
NilFlip: PUBLIC PROC [stateIn: REF ANY] RETURNS [stateOut: REF ANY] ~ {
RETURN[NIL]
};
Intersect: PUBLIC PROC [in: Graph, Copy: CopyLineProc ← NilCopy, Combine: CombineLineProc ← NilCombine, Flip: FlipLineProc ← NilFlip] RETURNS [out: Graph] ~ {
FlipLine: PROC [line: Line] ~ {
OPEN line;
temp: Point ← above; above ← below; below ← temp;
state ← Flip[state];
};
freeLC: LineCarrier ← NIL;
NewLC: PROC [carried: Line, lineLeft, lineRight: LineCarrier ← NIL, isALine: BOOLEAN ← TRUE] RETURNS [alive: LineCarrier] ~ INLINE {
IF freeLC = NIL THEN RETURN[NEW[LineCarrierRec← [carried: carried, lineLeft: lineLeft, lineRight: lineRight, isALine: isALine]]] ELSE {
alive ← freeLC; freeLC ← alive.lineRight;
alive.carried ← carried; alive.lineLeft ← lineLeft; alive.lineRight ← lineRight;
alive.isALine ← isALine;
}
};
TrashFreeLC: PROC [] ~ {
UNTIL freeLC = NIL DO
freeLC.lineLeft ← NIL; freeLC ← freeLC.lineRight;
ENDLOOP;
};
freeE: IntersectEvent ← NIL;
NewE: PROC [time: Point ← NIL, line: Line ← NIL, isALine: BOOLEAN ← TRUE, new: BOOLEAN ← FALSE, swap: BOOLEAN ← FALSE] RETURNS [alive: IntersectEvent] ~ INLINE {
IF freeE = NIL THEN RETURN[NEW[IntersectEventRec← [time: time, line: line, isALine: isALine, new: new, swap: swap]]] ELSE {
alive ← freeE; freeE ← alive.next;
alive.time ← time; alive.line ← line;
alive.isALine ← isALine; alive.new ← new; alive.swap ← swap;
}
};
TrashFreeE: PROC [] ~ {
UNTIL freeE = NIL DO
freeE.line ← NIL; freeE.lineCarrier ← freeE.lineRight ← NIL; freeE.time ← NIL;
freeE ← freeE.next;
ENDLOOP;
};
InitialScanLines: PROC [l: Line] RETURNS [quit: BOOL ← FALSE] ~ {
event:IntersectEvent ← NEW[IntersectEventRec ← [time: l.above, new: TRUE, line: l]];
YQ.InsertEvent[event];
l.state ← NEW[LineStateRec ← [clientState: l.state]];
};
LineLineProcessEvent: PROC [] ~ {
OrderInsert: PROC [e: IntersectEvent] ~ {
l: Line ← e.line; p: Point ← l.above; lc: LineCarrier;
scan: LineCarrier ← XO; prev: LineCarrier ← NIL;
UNTIL scan = NIL DO
IF ComparePointLine[p, scan.carried] = greater THEN EXIT;
prev ← scan; scan ← scan.lineLeft;
ENDLOOP;
e.lineCarrier ← lc ← NewLC[carried: l, lineLeft: scan, lineRight: prev];
e.time ← l.below; e.new ← FALSE;
YQ.InsertEvent[e];
IF scan # NIL THEN {scan.lineRight ← lc; TestIntersect[YQ, scan, lc, p]};
IF prev # NIL THEN {prev.lineLeft ← lc; TestIntersect[YQ, lc, prev, p]} ELSE XO ← lc;
};
OrderRemove: PROC [e: IntersectEvent] ~ {
lc: LineCarrier ← e.lineCarrier;
IF lc.lineRight # NIL THEN lc.lineRight.lineLeft ← lc.lineLeft ELSE XO ← lc.lineLeft;
IF lc.lineLeft # NIL THEN {
lc.lineLeft.lineRight ← lc.lineRight;
IF lc.lineRight # NIL THEN TestIntersect[YQ, lc.lineLeft, lc.lineRight, e.time];
};
lc.lineRight ← freeLC; freeLC ← lc; lc.lineLeft ← NIL;
e.next ← freeE; freeE ← e;
};
OrderSwap: PROC [e: IntersectEvent] ~ {
left: LineCarrier ← e.lineCarrier;
right: LineCarrier ← e.lineRight;
currentPoint: Point ← e.time;
IF right.lineLeft = left THEN {
hook: Line ← NEW[LineRec ← [above: NEW[PointRec ← [x: currentPoint.x, y: currentPoint.y+1]], below: currentPoint]];
left.lineRight ← right.lineRight; right.lineLeft ← left.lineLeft;
left.lineLeft ← right; right.lineRight ← left;
IF left.lineRight # NIL THEN {
left.lineRight.lineLeft ← left;
TestIntersect[YQ, left, left.lineRight, currentPoint]}
ELSE XO ← left;
IF right.lineLeft # NIL THEN {
right.lineLeft.lineRight ← right;
TestIntersect[YQ, right.lineLeft, right, currentPoint ]};
AddOriginalHook[hook];
};
e.next ← freeE; freeE ← e;
};
AddOriginalHook: PROC [h: Line] ~ {
e: IntersectEvent ← NewE[line: h, isALine: FALSE, new: TRUE];
e.time ← h.above;
HQ.InsertEvent[e];
};
event: IntersectEvent ← NARROW[YQ.NextEvent[]];
IF event.new THEN OrderInsert[event]
ELSE IF event.swap THEN OrderSwap[event]
ELSE OrderRemove[event];
};
TestIntersect: PROC [Q: Heap.Queue, left, right: LineCarrier, currentPoint: Point] ~ {
p: Point; s: LineRelation; s1, s2: EndPointRelation;
leftLine: Line ← left.carried; rightLine: Line ← right.carried;
[p, s, s1, s2] ← PairIntersection[leftLine, rightLine];
IF s = intersect AND p.y <= currentPoint.y THEN {
IF p.y < currentPoint.y OR CompareSlopes[leftLine, rightLine] = greater THEN {
event:IntersectEvent ← NewE[time: p, new: FALSE, line: NIL, swap: TRUE];
event.lineCarrier←left; event.lineRight←right;
Q.InsertEvent[event];
};
};
};
HookScanLines: PROC [l: Line] RETURNS [quit: BOOL ← FALSE] ~ {
event:IntersectEvent ← NewE[time: l.above, new: TRUE, line: l];
HQ.InsertEvent[event];
};
otherPoint: Point ← NEW[PointRec];
HookLineProcessEvent: PROC [] ~ {
OrderInsert: PROC [e: IntersectEvent] ~ {
currentPoint: Point ← e.time; lc: LineCarrier;
scan: LineCarrier ← XO; prev: LineCarrier ← NIL;
IF NOT e.isALine THEN {
DO
ne: IntersectEvent ← NARROW[HQ.PeekNextEvent];
IF ne.isALine OR NOT ne.new OR ComparePoints[currentPoint, ne.time] # equal THEN EXIT;
[] ← HQ.NextEvent[];
ne.next ← freeE; freeE ← ne;
ENDLOOP;
};
UNTIL scan = NIL DO
IF ComparePointLine[currentPoint, scan.carried] = greater THEN EXIT;
prev ← scan; scan ← scan.lineLeft;
ENDLOOP;
e.lineCarrier ← lc ← NewLC[carried: e.line, lineLeft: scan, lineRight: prev];
e.time ← e.line.below; e.new ← FALSE;
IF NOT e.isALine THEN {
backScan: LineCarrier ← prev;
otherPoint.x ← currentPoint.x + 1; otherPoint.y ← currentPoint.y;
UNTIL backScan = NIL DO
IF ComparePointLine[otherPoint, backScan.carried] # greater THEN EXIT;
AddInducedHook[e.line, backScan.carried]; backScan ← backScan.lineRight;
ENDLOOP;
lc.isALine ← FALSE;
};
e.new ← FALSE;
HQ.InsertEvent[e];
IF scan # NIL THEN {scan.lineRight ← lc; TestIntersect[HQ, scan, lc, currentPoint]};
IF prev # NIL THEN {prev.lineLeft ← lc; TestIntersect[HQ, lc, prev, currentPoint]} ELSE XO ← lc;
};
OrderRemove: PROC [e: IntersectEvent] ~ {
lc: LineCarrier ← e.lineCarrier;
IF lc.lineRight # NIL THEN lc.lineRight.lineLeft ← lc.lineLeft ELSE XO ← lc.lineLeft;
IF lc.lineLeft # NIL THEN {
lc.lineLeft.lineRight ← lc.lineRight;
IF lc.lineRight # NIL THEN TestIntersect[HQ, lc.lineLeft, lc.lineRight, e.time];
};
IF NOT lc.isALine THEN {
backScan: LineCarrier ← lc.lineRight;
currentPoint: Point ← e.time;
otherPoint.x ← currentPoint.x + 1; otherPoint.y ← currentPoint.y;
UNTIL backScan = NIL DO
IF ComparePointLine[otherPoint, backScan.carried] # greater THEN EXIT;
AddInducedHook[e.line, backScan.carried]; backScan ← backScan.lineRight;
ENDLOOP;
lc.isALine ← FALSE;
};
lc.lineRight ← freeLC; freeLC ← lc; lc.lineLeft ← NIL;
e.next ← freeE; freeE ← e;
};
OrderSwap: PROC [e: IntersectEvent] ~ {
left: LineCarrier ← e.lineCarrier;
right: LineCarrier ← e.lineRight;
currentPoint: Point ← e.time;
IF right.lineLeft = left THEN {
IF XOR[left.isALine, right.isALine] THEN {
IF left.isALine THEN AddInducedHook[right.carried, left.carried] ELSE AddInducedHook[left.carried, right.carried]
};
left.lineRight ← right.lineRight; right.lineLeft ← left.lineLeft;
left.lineLeft ← right; right.lineRight ← left;
IF left.lineRight # NIL THEN {
left.lineRight.lineLeft ← left;
TestIntersect[HQ, left, left.lineRight, currentPoint]}
ELSE XO ← left;
IF right.lineLeft # NIL THEN {
right.lineLeft.lineRight ← right;
TestIntersect[HQ, right.lineLeft, right, currentPoint ]};
};
e.next ← freeE; freeE ← e;
};
AddInducedHook: PROC [h: Line, l: Line] ~ {
ls: LineState ← NARROW[l.state];
IF h.state = NIL THEN {
h.state ← ComputeHead[h.below]};
ls.hooks ← CONS[h.state, ls.hooks];
};
ComputeHead: PROC [p: Point] RETURNS [np: Point] ~ INLINE {
OddBump: PROC [i: INT] RETURNS [o: INT] ~ INLINE {RETURN[(i+1)/2]};
np ← NEW[PointRec ← [x: OddBump[p.x], y: OddBump[p.y]]];
};
event: IntersectEvent ← NARROW[HQ.NextEvent[]];
IF event.new THEN OrderInsert[event]
ELSE IF event.swap THEN OrderSwap[event]
ELSE OrderRemove[event];
};
intermediate: Graph ← NewGraph[in.points.size];
BendScanLines: PROC [l: Line] RETURNS [quit: BOOLEAN ← FALSE] ~ {
ls: LineState ← NARROW[l.state];
dy: INT ← l.above.y - l.below.y; --automatically negateY
dx: INT ← l.below.x - l.above.x;
negateX: BOOLEAN ← ( dx < 0 );
exchangeXY: BOOLEAN;
originX, currentX: INT ← l.above.x; originY, currentY: INT ← l.above.y;
SegmentOutput: PROC [incrementX, incrementY: INT] ~ {
IF exchangeXY THEN {
temp: INT ← incrementX; incrementX ← incrementY; incrementY ← temp
};
IF negateX THEN incrementX ← - incrementX;
currentX ← currentX + incrementX; currentY ← currentY - incrementY;
intermediate ← intermediate.LineTo[currentX, currentY, Copy[ls.clientState], Flip];
};
NextHook: PROC [] RETURNS [down: BOOL ← FALSE, break: INT ← 0, quit: BOOLEAN ← FALSE] ~ {
hook: Point; clockwise: BOOLEAN;
IF ls.hooks = NIL THEN RETURN[quit: TRUE];
hook ← NARROW[ls.hooks.first]; ls.hooks ← ls.hooks.rest;
clockwise ← ComparePointLine[hook, l] = greater;
break ← IF exchangeXY THEN originY - hook.y ELSE
IF negateX THEN originX - hook.x ELSE
hook.x - originX;
down ← XOR[XOR[negateX, exchangeXY], clockwise];
};
DiagonalNextHook: PROC [] RETURNS [down: BOOL ← FALSE, break: INT ← 0, quit: BOOLEAN ← FALSE] ~ {
hook: Point; breakY: INT;
IF ls.hooks = NIL THEN RETURN[quit: TRUE];
hook ← NARROW[ls.hooks.first]; ls.hooks ← ls.hooks.rest;
negateX is FALSE; exchangeXY is FALSE
break ← hook.x - originX;
breakY ← originY - hook.y;
down ← NOT break = breakY;
};
HookCompare: PROC[ref1: REF ANY, ref2: REF ANY] RETURNS [res: Basics.Comparison] ~ {
hook1: Point ← NARROW[ref1];
hook2: Point ← NARROW[ref2];
cX: Basics.Comparison ← Basics.CompareINT[hook1.x, hook2.x];
cY: Basics.Comparison ← Basics.CompareINT[hook2.y, hook1.y]; --auto negateY
Flip: PROC [in: Basics.Comparison] RETURNS [out: Basics.Comparison] ~ {
IF in = less THEN RETURN[greater];
IF in = greater THEN RETURN[less];
RETURN[equal];
};
res ← IF exchangeXY THEN cY ELSE
IF negateX THEN Flip[cX] ELSE cX;
IF res = equal THEN {
res ← IF NOT exchangeXY THEN cY ELSE
IF negateX THEN Flip[cX] ELSE cX;
};
};
IF negateX THEN dx ← - dx;
exchangeXY ← ( dy > dx );
IF exchangeXY THEN {temp: INT ← dx; dx ← dy; dy ← temp};
ls.hooks ← List.UniqueSort[ls.hooks, HookCompare];
intermediate ← intermediate.NewPoint[currentX, currentY];
IF dx = dy AND NOT negateX THEN -- Special Diagonal Case
Bend.DiagonalToHooks[dx, dy, DiagonalNextHook, SegmentOutput]
ELSE Bend.BendToHooks[dx, dy, NextHook, SegmentOutput];
};
FinalScanLines: PROC [l: Line] RETURNS [quit: BOOL ← FALSE] ~ {
event:IntersectEvent;
IF ComparePoints[l.above, l.below] = equal THEN ERROR;
event ← NewE[time: l.above, new: TRUE, line: l];
YQ.InsertEvent[event];
};
RemoveColinearProcessEvent: PROC [] ~ {
PointOnLineFix: PROC [p: Point, nl: Line] RETURNS [rpl: Basics.Comparison] ~ {
rpl ← ComparePointLine[p, nl];
IF rpl = equal THEN {
IF ComparePoints[p, nl.above] = equal THEN {
IF p # nl.above THEN MergePoints[nl.above, p];
}
ELSE {
IF ComparePoints[p, nl.below] = equal THEN {
IF p # nl.below THEN MergePoints[nl.below, p];
}
ELSE { -- mid line
newAboveHalf: Line ← NEW[LineRec ← [above: nl.above, below: p, state: Copy[nl.state]]];
RemoveLineFromPointAbove[nl];
nl.above ← p;
InsertLineInPointAbove[nl];
InsertLineInEndPoints[newAboveHalf];
};
};
};
};
AddToOut: PROC [p: Point] ~ {
OPEN out.points;
IF size > 0 THEN {
IF ComparePoints[p, data[size-1]] = equal THEN {
IF data[size-1].incoming = NIL AND data[size-1].outgoing = NIL THEN data[size-1]←p;
RETURN[];
};
};
data[size] ← p; size ← size + 1;
};
e: IntersectEvent ← NARROW[YQ.NextEvent[]];
l: Line ← e.line; lc: LineCarrier ← e.lineCarrier;
rpl: Basics.Comparison;
scan: LineCarrier;
IF e.new THEN {
p: Point ← l.above; prev: LineCarrier ← NIL;
AddToOut[l.above];
scan ← XO;
UNTIL scan = NIL DO
neighborLine: Line ← scan.carried;
rpl ← PointOnLineFix[l.above, neighborLine];
IF rpl = greater THEN EXIT;
IF rpl = equal THEN {
IF l.above # neighborLine.below THEN {
rll: Basics.Comparison ← CompareSlopes[l, neighborLine];
IF rll = greater THEN EXIT;
IF rll = equal THEN {
rpp: Basics.Comparison ← ComparePoints[l.below, neighborLine.below];
IF rpp = greater THEN {
Break neighborLine
ne: IntersectEvent ← NewE[time: l.below, new: TRUE, line: neighborLine];
YQ.InsertEvent[ne]; scan.carried ← NIL; --obsolete future event
scan ← scan.lineLeft; --remove current entry
RemoveLineFromPointAbove[neighborLine];
neighborLine.above ← l.below;
InsertLineInPointAbove[neighborLine];
l.state ← Combine[l.state, neighborLine.state];
EXIT;
}
ELSE IF rpp = less THEN {
Break l
RemoveLineFromPointAbove[l];
l.above ← neighborLine.below;
InsertLineInPointAbove[l];
neighborLine.state ← Combine[neighborLine.state, l.state];
e.time ← l.above;
YQ.InsertEvent[e];
RETURN[];
}
ELSE
{neighborLine.state ← Combine[neighborLine.state, l.state];
RemoveLineFromEndPoints[l];
RETURN[];
};
};
};
};
prev ← scan; scan ← scan.lineLeft;
ENDLOOP;
e.lineCarrier ← lc ← NewLC[carried: l, lineLeft: scan, lineRight: prev];
e.time ← l.below;
e.new ← FALSE;
YQ.InsertEvent[e];
IF scan # NIL THEN {scan.lineRight ← lc};
IF prev # NIL THEN {prev.lineLeft ← lc} ELSE XO ← lc;
}
ELSE {
IF lc.carried # l THEN RETURN[]; --Obsolete Event
AddToOut[l.below];
IF lc.lineRight # NIL THEN lc.lineRight.lineLeft ← lc.lineLeft ELSE XO ← lc.lineLeft;
IF lc.lineLeft # NIL THEN lc.lineLeft.lineRight ← lc.lineRight;
scan ← lc.lineRight;
UNTIL scan = NIL DO
rpl ← PointOnLineFix[l.below, scan.carried];
IF rpl = greater THEN EXIT;
scan ← scan.lineRight;
ENDLOOP;
scan ← lc.lineLeft;
UNTIL scan = NIL DO
rpl ← PointOnLineFix[l.below, scan.carried];
IF rpl = less THEN EXIT;
scan ← scan.lineRight;
ENDLOOP;
lc.lineRight ← freeLC; freeLC ← lc;
e.next ← freeE; freeE ← e;
};
};
YQ: Heap.Queue ← Heap.CreateQueue[CompareLL, in.points.size];
HQ: Heap.Queue ← Heap.CreateQueue[CompareHL, in.points.size];
XO: LineCarrier ← NIL;
ExpandPoint: PROC [p: Point] ~ INLINE {p.x ← p.x*2; p.y ← p.y*2};
ContractPoint: PROC [p: Point] ~ INLINE {p.x ← p.x/2; p.y ← p.y/2};
FOR i: CARDINAL IN [0..in.points.size) DO ExpandPoint[in.points.data[i]] ENDLOOP;
[] ← EnumerateLines[in, InitialScanLines];
UNTIL YQ.Empty[] DO LineLineProcessEvent[] ENDLOOP;
[] ← EnumerateLines[in, HookScanLines];
UNTIL HQ.Empty[] DO HookLineProcessEvent[] ENDLOOP;
FOR i: CARDINAL IN [0..in.points.size) DO ContractPoint[in.points.data[i]] ENDLOOP;
[] ← EnumerateLines[in, BendScanLines];
out ← NewGraph[intermediate.points.size]; out.status ← planar;
IF XO # NIL THEN ERROR;
Heap.ChangeCompareProc[YQ, CompareRC];
[] ← EnumerateLines[intermediate, FinalScanLines];
UNTIL YQ.Empty[] DO RemoveColinearProcessEvent[] ENDLOOP;
DestroyGraph[in];
TrashFreeLC[]; TrashFreeE[];
};
END.