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] ~ { 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; 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; 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. ðBendImpl.mesa Greene, September 17, 1986 4:14:23 pm PDT Fragment a line with positive slope less than one First do a GCD calculation, stacking the results: Use the results of the GCD calculation to piece together the fragmented line: Êx˜Jšœ7™7J˜JšÏk œ˜J˜JšÏnœœœœ˜&J˜Jšœœ˜Jšœœ˜J˜J˜codeš œœœœœ˜)Kš œœœœœœ˜%K˜—J˜Jš ž œœœœžœž œ˜fJšœ1™1šœ˜Jšœ œ œœ˜%Jšœœ˜ Jšœœ˜Jšœœ˜ J˜JšœœÏc˜%Jšœ œ˜JšœœŸ˜&Jšœ œ˜J˜J˜Jšœœ˜Jšœ œœ˜Jšœ œœ˜Jšœœ˜J˜šž œœ˜šœ œ˜Kšœ ˜ Kšœ œ˜K˜—K˜K˜—Jšœœ˜J˜šžœœœ˜,Kšœ#˜#K˜šœ œ)œ˜@Kšœ˜Kšœ˜—šœ˜Kšœ˜K˜K˜Kšœ œ˜Kšœ˜K˜—Kšœ!˜!Kšœ!˜!K˜—K˜šž œœ˜Kšœœ˜K˜šœ!˜!Kšœ3˜3—Kšœœ,œ˜>šœ˜Kšœ˜šœœœœ˜$Kšœ*œ˜7Kšœœ,œ˜>Kšœ+œ˜AKšœ!œ ˜3K˜—Kšœ œ˜!Kšœ˜—K˜—K˜šž œœ,œ˜FKšœœ œ˜Kšœ9œ˜Ršœ˜KšœQ˜QKšœœ ˜:šœ˜Kšœ/˜/Kšœ˜Kšœ˜Kšœ˜—K˜—K˜—J˜J˜J˜&J˜(—˜Kšœ1™1š˜šœ œ˜Kšœ2˜2K˜ Kšœ˜K˜—K˜K˜XK˜ Kšœ˜—K˜K˜Kšœœ œ˜,K˜KšœM™Mš˜Kšœ œœ œ ˜-šœœ˜Kš œ œœœœœ˜6šœ˜Kš œœœ œœ˜)Kšœ#˜#Kšœœ1˜>Kšœ ˜ Kšœ˜—K˜—K˜šœŸ ˜Kš œœœœœœ˜;šœ œ˜Kš œ œ œœœ˜OKš œœ œœœ˜WK˜,šœœ˜Kšœ#˜#šœœ˜Kšœ˜Kšœ œ5œ˜KKšœœ˜ Kšœœ˜'Kšœ œ˜K˜—šœ œ˜/Kšœ2œ˜8—Kšœ˜K˜—K˜—šœŸ ˜Kš œ œ œœœ˜OK˜Fšœœ˜Kšœ8˜8Kš œœ œ œœ˜MKšœ œœ3œ˜dKšœ˜Kšœ˜—K˜—Kšœ ˜ K˜—Kšœ˜—K˜K˜K˜—K˜š žœœœœžœž œ˜mK˜K˜(š˜Kšœ!˜!K˜Kšœ/˜/˜"Kšœ#˜#—K˜˜Kšœ>˜>Kšœ)˜)K˜—Kšœ˜—KšœJ˜JK˜—Jšœ˜—…—Ò: