Action:
PROC ~ {
Lerp: PROC [lo, hi, a: REAL] RETURNS [REAL] ~ { RETURN[lo + (a * (hi-lo))]; };
LerpPair:
PROC [lo, hi: Pair, a:
REAL]
RETURNS [Pair] ~ {
RETURN[[Lerp[lo.x, hi.x, a], Lerp[lo.y, hi.y, a]]];
};
IntersectPairs:
PROC [j0, j1, k0, k1: Pair]
RETURNS [Pair] ~ {
Intersect:
PROC [a, b: Triple]
RETURNS [Pair] ~ {
det: REAL ¬ a.x*b.y - b.x*a.y;
IF det # 0.0 THEN det ¬ 1.0/det ELSE det ¬ 1.0;
RETURN[[det*(a.y*b.z - b.y*a.z), det*(b.x*a.z - a.x*b.z)]];
};
a: Triple ¬ [j0.y-j1.y, j1.x-j0.x, j0.x*j1.y - j1.x*j0.y];
b: Triple ¬ [k0.y-k1.y, k1.x-k0.x, k0.x*k1.y - k1.x*k0.y];
RETURN[Intersect[a, b]];
};
InsertHorizon:
PROC [h: HorizonList, left, right: Pair] ~ {
InsertABeforeB:
PROC [a, b: HorizonNode] ~ {
a.prev ¬ b.prev;
a.next ¬ b;
b.prev.next ¬ a;
b.prev ¬ a;
};
InsertAAfterB:
PROC [a, b: HorizonNode] ~ {
a.prev ¬ b;
a.next ¬ b.next;
b.next.prev ¬ a;
b.next ¬ a;
};
DeleteA:
PROC [a: HorizonNode] ~ {
a.prev.next ¬ a.next;
a.next.prev ¬ a.prev;
a.prev ¬ a.next ¬ NIL;
};
ll, lr, rl, rr: HorizonNode;
newright, newleft: HorizonNode;
oldly, oldry, lm, lb, rm, rb: REAL;
ll ¬ lr ¬ rl ¬ rr ¬ h.firstSaved;
WHILE lr # NIL AND lr.x <= left.x DO lr ¬ lr.next; ENDLOOP;
ll ¬ lr.prev;
WHILE rr # NIL AND rr.x <= right.x DO rr ¬ rr.next; ENDLOOP;
rl ¬ rr.prev;
find old left and right positions
lm ¬ (lr.ly - ll.ry) / MAX[1.0, (lr.x - ll.x)];
lb ¬ ll.ry - (ll.x * lm);
oldly ¬ lb + (lm * left.x);
rm ¬ (rr.ly - rl.ry) / MAX[1.0, (rr.x - rl.x)];
rb ¬ rr.ry - (rr.x * rm);
oldry ¬ rb + (rm * right.x);
delete inbetween nodes
IF lr # rr
THEN {
-- just wipe the links, the gc will pick up the nodes
lr.prev ¬ rl.next ¬ NIL;
ll.next ¬ rr;
rr.prev ¬ ll;
};
build new nodes
newleft ¬ NEW[HorizonNodeRep];
newleft.x ¬ left.x;
newleft.ly ¬ oldly;
newleft.ry ¬ left.y;
newright ¬ NEW[HorizonNodeRep];
newright.x ¬ right.x;
newright.ly ¬ right.y;
newright.ry ¬ oldry;
link them in
InsertAAfterB[newleft, ll];
InsertABeforeB[newright, rr];
IF
ABS[ll.x - newleft.x] < ht.epsilon
THEN {
newleft.ly ¬ ll.ly;
IF rr # ll THEN DeleteA[ll];
};
IF
ABS[rr.x - newright.x] < ht.epsilon
THEN {
newright.ry ¬ rr.ry;
IF rr # ll THEN DeleteA[rr];
};
};
UpdateAction: TYPE ~ { draw, insert };
LineAction:
PROC [h: HorizonList, left, right: Pair, action: UpdateAction] ~ {
Flush:
PROC ~ {
IF qLeft.x > qRight.x
THEN {
tmp: Pair ¬ qLeft;
qLeft ¬ qRight;
qRight ¬ tmp;
};
IF pending
AND
ABS[qRight.x - qLeft.x] > ht.epsilon
THEN
IF action = draw
THEN Draw2d.Line[context, qLeft, qRight, solid, zip]
ELSE InsertHorizon[h, qLeft, qRight];
pending ¬ FALSE;
};
Extend:
PROC [left, right: Pair] ~ {
IF NOT pending THEN { qLeft ¬ left; pending ¬ TRUE; };
qRight ¬ right;
};
NearBy:
PROC [a, b: Pair]
RETURNS [
BOOL] ~ {
RETURN[(ABS[a.x - b.x] < ht.epsilon) AND (ABS[a.y - b.y] < ht.epsilon)];
};
pending: BOOL ¬ FALSE;
qLeft, qRight: Pair;
n: HorizonNode;
m: REAL ¬ (right.y - left.y) / MAX[1.0, (right.x - left.x)];
b: REAL ¬ right.y - (right.x * m);
n ¬ h.first;
WHILE n # NIL AND n.x < left.x DO n ¬ n.next; ENDLOOP;
n ¬ n.prev;
WHILE n.x < right.x
DO
xWindow: RealRange ¬ [MAX[n.x, left.x], MIN[n.next.x, right.x]];
bandm: REAL ¬ (n.next.ly - n.ry) / MAX[1.0, (n.next.x - n.x)];
bandb: REAL ¬ n.ry - (n.x * bandm);
oldLeft: Pair ¬ [xWindow.l, bandb + (bandm * xWindow.l)];
oldRight: Pair ¬ [xWindow.h, bandb + (bandm * xWindow.h)];
newLeft: Pair ¬ [xWindow.l, b + (m * xWindow.l)];
newRight: Pair ¬ [xWindow.h, b + (m * xWindow.h)];
leftSign:
BOOL ¬
IF h.type = upper
THEN newLeft.y >= oldLeft.y ELSE newLeft.y <= oldLeft.y;
rightSign:
BOOL ¬
IF h.type = upper
THEN newRight.y >= oldRight.y ELSE newRight.y <= oldRight.y;
IF NearBy[left, [n.x, n.ry]]
THEN {
IF h.type = upper
THEN IF m > bandm THEN leftSign ¬ TRUE ELSE leftSign ¬ FALSE
ELSE IF m < bandm THEN leftSign ¬ TRUE ELSE leftSign ¬ FALSE;
};
IF NearBy[right, [n.next.x, n.next.ly]]
THEN {
IF h.type = upper
THEN IF m < bandm THEN leftSign ¬ TRUE ELSE leftSign ¬ FALSE
ELSE IF m > bandm THEN leftSign ¬ TRUE ELSE leftSign ¬ FALSE;
};
IF leftSign # rightSign
THEN {
hitPt: Pair ¬ IntersectPairs[oldLeft, oldRight, newLeft, newRight];
IF leftSign =
TRUE
THEN { Extend[newLeft, hitPt]; Flush[]; }
ELSE { Flush[]; Extend[hitPt, newRight]; };
}
ELSE IF leftSign = TRUE THEN Extend[newLeft, newRight];
IF n.next =
NIL
THEN
n ¬ n;
n ¬ n.next;
ENDLOOP;
Flush[];
};
CopyAction: TYPE ~ { backup, restore };
CopyHorizonList:
PROC [h: HorizonList, action: CopyAction] ~ {
src: HorizonNode ¬ IF action = backup THEN h.first ELSE h.firstSaved;
dst: HorizonNode ¬ NIL;
WHILE src #
NIL
DO
n: HorizonNode ¬ NEW[HorizonNodeRep];
n.x ¬ src.x; n.ly ¬ src.ly; n.ry ¬ src.ry;
IF dst =
NIL
THEN {
IF action = backup
THEN h.firstSaved ¬ n
ELSE h.first ¬ n;
}
ELSE {
n.prev ¬ dst;
dst.next ¬ n;
};
dst ¬ n;
src ¬ src.next;
ENDLOOP;
};
UpdateLines:
PROC [list: LineSequence] ~ {
FOR k:
INT
IN [0 .. 1]
DO
h: HorizonList ¬ IF k = 0 THEN upper ELSE lower;
FOR i:
INT IN [0 .. list.length)
DO
-- first draw all the lines
LineAction[h, list[i].left, list[i].right, draw];
ENDLOOP;
CopyHorizonList[h, backup];
FOR i:
INT IN [0 .. list.length)
DO
-- now update visibility lists
LineAction[h, list[i].left, list[i].right, insert];
ENDLOOP;
CopyHorizonList[h, restore];
ENDLOOP;
};
InitLists:
PROC ~ {
ul: HorizonNode ¬ NEW[HorizonNodeRep];
ur: HorizonNode ¬ NEW[HorizonNodeRep];
ll: HorizonNode ¬ NEW[HorizonNodeRep];
lr: HorizonNode ¬ NEW[HorizonNodeRep];
ul.x ¬ -1.0; ul.ly ¬ ul.ry ¬ -1.0; ul.next ¬ ur;
ur.x ¬ bounds.w+1.0; ur.ly ¬ ur.ry ¬ -1.0; ur.prev ¬ ul;
ll.x ¬ -1.0; ll.ly ¬ ll.ry ¬ bounds.h+1; ll.next ¬ lr;
lr.x ¬ bounds.w+1.0; lr.ly ¬ lr.ry ¬ bounds.h+1; lr.prev ¬ ll;
upper.first ¬ ul;
lower.first ¬ ll;
upper.type ¬ upper;
lower.type ¬ lower;
};
zip: Draw2d.Zip ¬ Draw2d.GetZip[context];
intWidth: INT ¬ Real.Round[canvasWidth];
nearSlice: PairSequence ¬ NEW[PairSequenceRep[ht.nXSamples]];
upper: HorizonList ¬ NEW[HorizonListRep];
lower: HorizonList ¬ NEW[HorizonListRep];
farSlice: PairSequence ¬ NEW[PairSequenceRep[ht.nXSamples]];
xDistance: REAL ¬ ht.xRange.h - ht.xRange.l;
yDistance: REAL ¬ ht.yRange.h - ht.yRange.l;
invYAlpha: REAL ¬ 1.0 / MAX[1.0, (ht.nYSamples-1.0)];
invXAlpha: REAL ¬ 1.0 / MAX[1.0, (ht.nXSamples-1.0)];
maxLines: INT ¬ MAX[ht.nXSamples, ht.nYSamples];
lineList: LineSequence ¬ NEW[LineSequenceRep[maxLines]];
initialize the sequences and lists
InitLists[];
lineList.length ¬ 0;
nearSlice.length ¬ farSlice.length ¬ ht.nXSamples;
FOR yIndex:
INT
IN [0 .. ht.nYSamples)
DO
yAlpha: REAL ¬ yIndex * invYAlpha;
nextyAlpha: REAL ¬ (yIndex+1) * invYAlpha;
yValue: REAL ¬ ht.yRange.l + (yAlpha * yDistance);
nextyValue: REAL ¬ ht.yRange.l + (nextyAlpha * yDistance);
bFL: Pair ¬ LerpPair[pFL, pBL, yAlpha];
bFR: Pair ¬ LerpPair[pFR, pBR, yAlpha];
bBL: Pair ¬ LerpPair[pFL, pBL, nextyAlpha];
bBR: Pair ¬ LerpPair[pFR, pBR, nextyAlpha];
GetVal:
PROC [xIndex, yIndex:
INT, xValue, yValue:
REAL]
RETURNS [
REAL] ~ {
v:
REAL ¬
IF ht.heightProc =
NIL
THEN ht.heightField[yIndex][xIndex]
ELSE ht.heightProc[xValue, yValue, ht.clientData];
RETURN[ht.zScale * v];
};
Process.CheckForAbort[];
FOR xIndex:
INT
IN [0 .. ht.nXSamples)
DO
xAlpha: REAL ¬ xIndex * invXAlpha;
xValue: REAL ¬ ht.xRange.l + (xAlpha * xDistance);
get the heights along the near slice
IF yIndex > 0
THEN {
nearSlice[xIndex] ¬ farSlice[xIndex];
}
ELSE {
nearSlice[xIndex] ¬ LerpPair[bFL, bFR, xAlpha];
nearSlice[xIndex].y ¬ nearSlice[xIndex].y + GetVal[xIndex, yIndex, xValue, yValue];
};
get the heights along the far slice (we'll compute it even if not needed!)
farSlice[xIndex] ¬ LerpPair[bBL, bBR, xAlpha];
farSlice[xIndex].y ¬ farSlice[xIndex].y + GetVal[xIndex, yIndex+1, xValue, nextyValue];
first the horizontal pass along bFL to bFR
lineList.length ← 0;
IF ht.drawX THEN {
FOR xIndex: INT IN [0 .. ht.nXSamples-1) DO
lineList[lineList.length] ← [nearSlice[xIndex], nearSlice[xIndex+1]];
lineList.length ← lineList.length+1;
ENDLOOP;
UpdateLines[lineList];
};
now the vertical stripes between the bands
lineList.length ← 0;
IF ht.drawY THEN {
IF yIndex < ht.nYSamples-1 THEN {
FOR xIndex: INT IN [0 .. ht.nXSamples) DO
lineList[lineList.length] ← [nearSlice[xIndex], farSlice[xIndex]];
lineList.length ← lineList.length+1;
ENDLOOP;
UpdateLines[lineList];
};
};
-- first the right-most near-far edge
lineList.length ¬ 1;
lineList[0] ¬ [nearSlice[ht.nXSamples-1], farSlice[ht.nXSamples-1]];
IF ht.drawY THEN UpdateLines[lineList];
-- now the h/v pairs
FOR xIndex:
INT
DECREASING
IN [0 .. ht.nXSamples-1)
DO
lineList.length ¬ 0;
IF ht.drawX
THEN {
lineList[lineList.length] ¬ [nearSlice[xIndex], nearSlice[xIndex+1]];
lineList.length ¬ lineList.length+1;
};
IF ht.drawY
THEN {
lineList[lineList.length] ¬ [nearSlice[xIndex], farSlice[xIndex]];
lineList.length ¬ lineList.length+1;
};
UpdateLines[lineList];
ENDLOOP;
ENDLOOP;
draw the outline (so we know we're alive!)
Draw2d.Line[context, pFL, pFR, dotted, zip];
Draw2d.Line[context, pFR, pBR, dotted, zip];
Draw2d.Line[context, pBR, pBL, dotted, zip];
Draw2d.Line[context, pBL, pFL, dotted, zip];
};