BendImpl.mesa
Greene, September 17, 1986 4:14:23 pm PDT
DIRECTORY
Bend;
BendImpl: CEDAR PROGRAM EXPORTS Bend =
BEGIN OPEN Bend;
logMax: INT = 20;
XOR:
PROC [a, b:
BOOL]
RETURNS [
BOOL] ~ {
RETURN[(a OR b) AND (NOT a OR NOT b)]
};
BendToHooks: PUBLIC PROC [lineX, lineY: INT, NextHook: NextHookProc, OutputSegment:OutputSegmentProc]
Fragment a line with positive slope less than one
~ {
pX, pY, pZ: ARRAY [0..logMax] OF INT;
i: INT ← 2;
deltaX, deltaY: INT;
f, q: INT;
below: BOOLEAN; -- FALSE means above
primary: BOOLEAN;
away: BOOLEAN; -- FALSE means towards
crossing: BOOLEAN;
break, remainder: INT;
down, quit: BOOLEAN ← FALSE;
bufferFull: BOOLEAN ← FALSE;
bufferX, bufferY: INT ← 0;
FlushBuffer:
PROC [] ~ {
IF bufferFull
THEN {
OutputSegment[bufferX, bufferY];
bufferFull ← FALSE;
};
};
currentX, currentY: INT ← 0;
Move:
PROC [incrementX, incrementY:
INT] ~ {
remainder ← remainder - incrementX;
IF bufferFull
AND incrementX*bufferY = incrementY*bufferX
THEN {
bufferX ← bufferX + incrementX;
bufferY ← bufferY + incrementY}
ELSE {
FlushBuffer[];
bufferX ← incrementX;
bufferY ← incrementY;
bufferFull ← TRUE;
};
currentX ← currentX + incrementX;
currentY ← currentY + incrementY;
};
GetNextHook:
PROC [] ~ {
away ← FALSE; FlushBuffer[];
[down, break, quit] ← NextHook[];
IF break = 0 THEN [down, break, quit] ← NextHook[];
IF quit THEN {remainder ← lineX - currentX; crossing ← FALSE}
ELSE {
remainder ← break - currentX;
IF remainder = 0
AND
NOT down
THEN {
[down, break, quit] ← NextHook[]; below ← FALSE; i ← 1;
IF quit THEN {remainder ← lineX - currentX; crossing ← FALSE}
ELSE {remainder ← break - currentX; crossing ← XOR[below, down]};
IF currentX*lineY > currentY*lineX THEN Move[0, 1];
}
ELSE crossing ← XOR[below, down];
};
};
CrossingMove:
PROC [goodX, goodY, majorX, majorY, minorIndex:
INT] ~ {
away ← TRUE; below ← NOT below;
IF (goodY + currentY) * lineX = (goodX + currentX) * lineY THEN Move[goodX, goodY]
ELSE {
goodX ← goodX + majorX - pX[minorIndex]; goodY ← goodY + majorY - pY[minorIndex];
IF goodX <= remainder THEN {Move[goodX, goodY]; i ← i - 1}
ELSE {
goodX ← goodX - majorX; goodY ← goodY - majorY;
f ← remainder / goodX;
Move[f*goodX, f*goodY];
i ← minorIndex}
}
};
pX[0] ← 0; pY[0] ← 0;
pX[1] ← 0; pY[1] ← 1; pZ[1] ← lineX;
pX[2] ← 1; pY[2] ← 0; pZ[2] ← - lineY;
First do a GCD calculation, stacking the results:
DO
IF pZ[i] = 0
THEN {
pX[i+1] ← pX[i]; pY[i+1] ← pY[i]; pZ[i+1] ← pZ[i];
i ← i + 1;
EXIT;
};
q ← - pZ[i-1]/pZ[i];
pZ[i+1] ← pZ[i-1] + q*pZ[i]; pX[i+1] ← pX[i-1] + q*pX[i]; pY[i+1] ← pY[i-1] + q*pY[i];
i ← i + 1;
ENDLOOP;
[] ← GetNextHook[];
away ← TRUE; crossing ← FALSE; below ← down;
Use the results of the GCD calculation to piece together the fragmented line:
DO
primary ← XOR[below, XOR[away, i MOD 2 = 0]];
IF away
THEN {
IF i < 2 THEN {IF quit THEN EXIT ELSE GetNextHook[]}
ELSE {
base: INT ← IF primary THEN 0 ELSE i - 1;
f ← (remainder - pX[base]) / pX[i];
IF f > 0 THEN Move[ pX[base] + f*pX[i], pY[base] + f*pY[i] ];
i ← i - 1;
};
}
ELSE {
--towards
IF remainder = 0 THEN IF quit THEN EXIT ELSE GetNextHook[];
IF primary
THEN {
IF pZ[i] = 0 THEN {away ← TRUE; i ← i + 1; below ← XOR[below, crossing]; LOOP};
IF pX[i] > remainder THEN {away ← TRUE; i ← i - 1; below ← XOR[below, crossing]; LOOP};
f ← (lineY*currentX - lineX*currentY)/pZ[i];
IF f > 0
THEN {
deltaX ← f*pX[i]; deltaY ← f*pY[i];
IF deltaX > remainder
THEN {
f ← remainder / pX[i];
IF crossing THEN {CrossingMove[f*pX[i], f*pY[i], pX[i], pY[i], i-1]; LOOP};
away ← TRUE;
IF f > 0 THEN Move[ f*pX[i], f*pY[i] ];
i ← i - 1; LOOP;
};
IF crossing
AND deltaX + pX[i] > remainder
THEN
{CrossingMove[deltaX, deltaY, pX[i], pY[i], i-1]; LOOP};
Move[deltaX,deltaY]
};
}
ELSE {
-- secondary
IF pZ[i] = 0 THEN {away ← TRUE; i ← i + 1; below ← XOR[below, crossing]; LOOP};
f ← (lineX*(currentY + pY[i+1]) - lineY*(currentX + pX[i+1])) / pZ[i];
IF f > 0
THEN {
deltaX ← pX[i+1] - f*pX[i]; deltaY ← pY[i+1] - f*pY[i];
IF deltaX > remainder THEN {away ← TRUE; below ← XOR[below, crossing]; LOOP};
IF crossing AND deltaX * 2 > remainder THEN {CrossingMove[deltaX, deltaY, deltaX, deltaY, i]; LOOP};
Move[deltaX, deltaY];
};
};
i ← i + 1;
};
ENDLOOP;
FlushBuffer[];
};
DiagonalToHooks:
PUBLIC
PROC [lineX, lineY:
INT,
NextHook: NextHookProc,
OutputSegment:OutputSegmentProc] ~ {
remainder, currentX: INT ← 0;
down, quit: BOOLEAN ← FALSE; break: INT;
DO
[down, break, quit] ← NextHook[];
IF quit THEN EXIT;
remainder ← break - currentX; currentX ← break;
IF NOT down AND remainder > 0 THEN
OutputSegment[remainder, remainder]
ELSE
IF down THEN {
IF remainder > 1 THEN OutputSegment[remainder-1, remainder-1];
OutputSegment[1, 0]; OutputSegment[0, 1];
};
ENDLOOP;
IF currentX # lineX THEN OutputSegment[lineX - currentX, lineX - currentX]
};
END.