[Cyan]<PreISLCedar>Stolfi>Dobkin>TriBlt.mesa!1

-- still to come:

-- clean code in a few places

-- fix attachment when endpoint is encountered making fractions add

-- version of June 26,1981 12:34pm (Dobkin)

-- converted to Tioga format by Stolfi - September 14, 1983 2:33 pm

DIRECTORY

IODefs USING[WriteLine,WriteString,WriteDecimal,ReadDecimal,ReadChar],

Storage USING[Node],

InlineDefs USING[LowHalf],

MiscDefs USING[Zero,SetBlock],

BitBltDefs,

KeyDefs,

AltoDisplay,

RandomCard USING[InitRandom,Choose],

SystemDefs USING[Even],

ProcessDefs USING[Pause,MsecToTicks];

Triblt: PROGRAM

IMPORTS RandomCard,InlineDefs,MiscDefs,IODefs,ProcessDefs,Storage,BitBltDefs,SystemDefs

BEGIN OPEN InlineDefs,RandomCard,MiscDefs,AltoDisplay,IODefs,ProcessDefs,

Storage,BitBltDefs,SystemDefs;

-- debug = 1 gives diagnostics debug =2 2 allows for keyboard input

-- debug =3 does both

debug: INTEGER ← 0;

numberofscanlines: INTEGER = 400;

numberofblanklines: INTEGER = 100;

seed: INTEGER ← 6561;

random: BOOLEAN ← FALSE;

nonstop: BOOLEAN ← FALSE;

output: BOOLEAN ← TRUE;

i,numbtri: INTEGER;

-- long number used to gain precision

Double: TYPE = RECORD[

int : INTEGER,

num : INTEGER];

Pdouble: TYPE = POINTER TO Double;

-- defining points

Point: TYPE = RECORD[

y: INTEGER,

x: Double,

on: BOOLEAN ← TRUE];

Ppoint: TYPE = POINTER TO Point;

top,left,right: Point;

t,l,r: Ppoint;

-- lines

Line: TYPE = RECORD[

start: Point,

end: Point];

first,second,third: Line;

-- slopes

Slope: TYPE = RECORD[

val: Double,

den: INTEGER,

had: INTEGER];

Pslope: TYPE = POINTER TO Slope;

leftslope,rightslope: Slope;

ls: Pslope = @leftslope;

rs: Pslope = @rightslope;

-- endpoint and width of scan lines

slxv,srxv: Double;

slx: Pdouble = @slxv;

srx: Pdouble = @srxv;

-- offset parameters

offset: RECORD[x: INTEGER ← 0 ,y: INTEGER ← 0 ];

Direction: TYPE = {up,down};

move: Direction ← down;

-- bitblt and screen management definitions

bltptr: BBptr = AlignedBBTable[Node[SIZE[BBTable]+1]];

blank,source,mine,bottom: ARRAY [0..SIZE[DCB]] OF UNSPECIFIED;

blankp,sourcep,minep,mesadisp,bottomp: AltoDisplay.DCBHandle;

sourcebits: POINTER TO ARRAY[0..76) OF CARDINAL;

mybits: POINTER TO ARRAY[0..38*numberofscanlines) OF CARDINAL;

-- getting input

mousebut: POINTER TO KeyDefs.MouseBits = LOOPHOLE[177030B];

mousepos: POINTER TO AltoDisplay.Coordinate = LOOPHOLE[424B];

error: BOOLEAN;

BtoC: PROCEDURE[a:BOOLEAN] RETURNS[INTEGER] =

{IF a THEN RETURN[1] ELSE RETURN[-1];};

Round: PROCEDURE[p:Pdouble,q:Pslope] RETURNS[INTEGER] =

BEGIN

WHILE ABS[p.num] >= q.had DO

SELECT p.num FROM

< -q.had => BEGIN p.int←p.int-1; p.num←p.num+q.den; END;

> q.had => BEGIN p.int←p.int+1; p.num←p.num-q.den; END;

= q.had => BEGIN p.int←p.int+1; p.num←-q.had; RETURN[p.int];END;

= -q.had => RETURN[p.int];

ENDCASE; ENDLOOP;

RETURN[p.int];

END;

-- updating scan line endpoints

Update: PROCEDURE[p:Pdouble,q:Pslope] RETURNS[INTEGER] =

BEGIN

p.int ← p.int + q.val.int;

p.num ← p.num + q.val.num;

RETURN[Round[p,q]];

END;

HalfUpdate: PROCEDURE[p:Pdouble,q:Pslope] RETURNS[INTEGER] =

BEGIN

IF ABS[q.val.int] MOD 2 = 1

THEN {p.int ← p.int + q.val.int/2;

p.num ← p.num +q.val.num/2;

IF q.val.int > 0 THEN p.num ← p.num +q.had

ELSE p.num ← p.num -q.had;}

ELSE {p.int ← p.int + q.val.int/2; p.num ← p.num +q.val.num/2 ;};

RETURN[Round[p,q]];

END;

HalfNUpdate: PROCEDURE[p:Pdouble,q:Pslope] RETURNS[INTEGER] =

BEGIN

IF ABS[q.val.int] MOD 2 = 1

THEN {p.int ← p.int - q.val.int/2;

IF q.val.int > 0 THEN p.num ← p.num +q.val.num/2 -q.had

ELSE p.num ← p.num +q.val.num/2 +q.had;}

ELSE {p.int ← p.int - q.val.int/2; p.num ← p.num -q.val.num/2 ;};

RETURN[Round[p,q]];

END;

-- procedure for computing slopes

FindSlope: PROCEDURE[p:Pslope, a,b: Ppoint] RETURNS[BOOLEAN] =

BEGIN

dx: INTEGER;

p.den𡤋.y-a.y;

dx ← b.x.int-a.x.int;

p.val.int ← dx/p.den;

IF p.den MOD 2 = 1 THEN {p.den←p.den+p.den; dx𡤍x+dx;};

p.val.num ← dx MOD p.den;

p.had ← p.den/2;

IF debug MOD 2 = 1 THEN

BEGIN

WriteString["slope "];

WriteDecimal[p.val.int];

WriteString[" "];

WriteDecimal[p.val.num];

WriteString["/"];

WriteDecimal[p.den];

WriteString[" half den is"];

WriteDecimal[p.had];

WriteString[" slope is "];

IF p.val.int >0 OR (p.val.int = 0 AND p.val.num >=0)

THEN WriteLine["positive"] ELSE WriteLine["negative"];

END;

RETURN[p.val.int>0 OR (p.val.int = 0 AND p.val.num >=0)];

END;

-- reading the mouse

ReadPoint: PROCEDURE[] RETURNS[p:Point] =

BEGIN

IF random THEN RETURN[RRpoint[]];

IF debug < 2 THEN

BEGIN

WriteLine["Waiting for coordinates of Vertex via mouse"];

WHILE mousebut.buttons=None DO ENDLOOP;

IF mousebut.buttons=Blue THEN

BEGIN ChangeParms[];RETURN[ReadPoint[]]; END;

IF mousebut.buttons=Yellow THEN p.on ← FALSE;

p.x.int ← mousepos.x;

p.y ← mousepos.y - numberofblanklines;

Pause[MsecToTicks[17]];

END

ELSE

BEGIN

WriteLine["Specify coordinates of vertex (y,x) separated by a space"];

p.y ← ReadDecimal[];

IF p.y < 0 THEN BEGIN ChangeParms[]; RETURN[ReadPoint[]]; END;

WriteString[" "];

p.x.int ← ReadDecimal[];

END;

Wpoint[" VERTEX",p.y,p.x.int];

p.x.num ← 0;

RETURN[p];

END;

-- creating random points

RRpoint: PROCEDURE[] RETURNS[p:Point] =

BEGIN

p.y ← Choose[0,numberofscanlines-1];

p.x.int𡤌hoose[0,599];

p.x.num ← 0;

Wpoint[" VERTEX",p.y,p.x.int];

RETURN[p];

END;

-- reading lines

ReadLine: PROCEDURE[] RETURNS[p:Line] =

BEGIN

WriteLine["Waiting for coordinates of Line via mouse"];

p.start ← ReadPoint[];

p.end ← ReadPoint[];

END;

ChangeParms: PROCEDURE[] RETURNS[] =

BEGIN

WriteLine[" Specify which parameters you would like to change "];

SELECT ReadChar[] FROM

'd => BEGIN

WriteLine["new value of debug "];

debug ← ReadDecimal[];

END;

'r => random ← NOT random;

'n => nonstop ← NOT nonstop;

'o => output ← NOT output;

ENDCASE;

END;

Wpoint: PROCEDURE[t: STRING, x,y: INTEGER] RETURNS[] =

BEGIN

IF NOT output THEN RETURN[];

WriteString[t]; WriteString[" is ("];

WriteDecimal[x];

WriteString[","];

WriteDecimal[y];

WriteLine[")"];

END;

ReadOffset: PROCEDURE[] RETURNS[] =

BEGIN

IF random THEN {offset.x ← offset.y ← 0; RETURN[]};

IF debug < 2 THEN

BEGIN

WriteLine[" Set two points to act as the offset "];

WHILE mousebut.buttons = None DO ENDLOOP;

offset.x ← mousepos.x;

offset.y ← mousepos.y;

Pause[MsecToTicks[200]];

WHILE mousebut.buttons = None DO ENDLOOP;

offset.x ← mousepos.x - offset.x;

offset.y ← mousepos.y - offset.y;

END

ELSE

BEGIN

WriteLine["Specify coordinates of offset (y,x) separated by a space"];

offset.y ← ReadDecimal[]; WriteString[" "];

offset.x ← ReadDecimal[];

END;

IF offset.y < 0 THEN move ← up ELSE move ← down;

Wpoint["OFFSET",offset.y,offset.x];

END;

-- swapping and area calculating routines;

Swap: PROCEDURE[a,b:Ppoint] RETURNS[] =

{temp: Point ← a^;a^𡤋^;b^←temp;};

Posarea: PROCEDURE[a,b,c:Ppoint] RETURNS[BOOLEAN] =

{ai,bi,ci,di: LONG INTEGER;

ai𡤊.x.int - c.x.int; bi𡤋.y-c.y ;

ci𡤋.x.int-c.x.int ; di𡤊.y-c.y ;

RETURN[ai*bi>ci*di];};

-- getting input and sorting points

GetInput: PROCEDURE[] RETURNS[] =

BEGIN

top←Inc[first];

left←Inc[second];

right←Inc[third];

t←@top;

l←@left;

r←@right;

offset.x ← offset.y ← 0;

-- someday may want this ReadOffset[];

IF move = up THEN BEGIN t.y ← -t.y; l.y ← -l.y; r.y ← -r.y; END;

IF l^.y < t^.y OR (t^.y = l^.y AND t^.x.int <l^.x.int) THEN Swap[t,l];

IF r^.y < t^.y OR (t^.y = r^.y AND t^.x.int >r^.x.int) THEN Swap[t,r];

IF t^.y = l^.y THEN {Swap[r,l]; Swap[r,t];};

IF Posarea[t,l,r] THEN Swap[l,r];

IF move=down THEN bltptr.dty←t^.y + offset.y ELSE bltptr.dty←offset.y-t^.y;

bltptr.slx ← slx.int ← t^.x.int; slx.num ← 0;

IF t^.y = r^.y THEN srx.int ← r^.x.int ELSE srx.int ← t^.x.int;

srx.num ← 0;

error ← FALSE;

-- IF debug MOD 2 = 1 THEN

-- BEGIN

-- Wpoint["top ",t.y,t.x.int];

-- Wpoint["left ",l.y,l.x.int];

-- Wpoint["right ",r.y,r.x.int];

-- END

END;

Inc: PROCEDURE[p:Line] RETURNS[q:Point] =

BEGIN

a,b: LONG INTEGER;

a ← p.start.x.int ;

b ← p.end.x.int ;

q.x.int ← LowHalf[(a*(numbtri-i) + b*(i-1))/(numbtri-1)];

a ← p.start.y ;

b ← p.end.y ;

q.y ← LowHalf[(a*(numbtri-i) + b*(i-1))/(numbtri-1)];

q.x.num ← 0;

RETURN[q];

END;

-- output lines to bitblt

NewBlt: PROCEDURE[iter:INTEGER] RETURNS[] =

BEGIN

count: INTEGER;

FOR count IN [1..iter] DO

BEGIN

bltptr.slx ← Update[slx,ls];

[] ← Update[srx,rs];

Blt[];

END;

ENDLOOP;

END;

Blt: PROCEDURE[] RETURNS[] =

BEGIN

bltptr.dw ← srx.int - bltptr.slx + 1;

bltptr.dlx ← bltptr.slx + offset.x;

IF bltptr.dty>numberofscanlines OR bltptr.dlx+bltptr.dw >606

THEN {WriteLine[" address out of bounds"]; error ← TRUE;}

ELSE BITBLT[bltptr];

IF debug MOD 2 = 1 OR error THEN

{Wpoint["source start ",bltptr.sty,bltptr.slx];

WriteString[" length is "];

WriteDecimal[bltptr.dw];

WriteLine[" "];

Wpoint["destination start ",bltptr.dty,bltptr.dlx];

Wpoint["destination 1stpoint ",slx.int,slx.num];

Wpoint["destination endpoint ",srx.int,srx.num];};

bltptr.dty ← bltptr.dty + BtoC[move=down];

END;

-- setting up DCBs for blank top of screen, then my area, then MESA's area

AllocateScreen: PROCEDURE[] RETURNS[] =

BEGIN

bltptr^←[];

bltptr.dbca ← mybits 𡤎ven[Node[38*numberofscanlines+1]];

bltptr.sbca ← sourcebits ← Even[Node[77]];

bltptr.dbmr ← bltptr.sbmr ← 38;

bltptr.dh ← 1;

bltptr.sty ← 1;

bltptr.function ← invert;

sourcep ← Even[@source];

minep ← Even[@mine];

bottomp ← Even[@bottom];

mesadisp ← DCBchainHead^;

DCBchainHead^ ← blankp ← Even[@blank];

blankp^←DCB[ next: sourcep, resolution: high, background: white,

indenting: 0, width: 0, bitmap: NIL, height: numberofblanklines/2];

sourcep^←DCB[ next: minep, resolution: high, background: white,

indenting: 0, width: 38, bitmap: sourcebits, height: 1];

minep^←DCB[ next: bottomp, resolution: high, background: white,

indenting: 0, width: 38, bitmap: mybits, height: numberofscanlines/2];

bottomp^←DCB[ next: mesadisp, resolution: high, background: white,

indenting: 0, width: 38, bitmap: sourcebits, height: 1];

END;

-- start of main program

AllocateScreen[];

[] ← InitRandom[seed];

SetBlock[sourcebits,177777B,76];

Zero[mybits,38*numberofscanlines]; --clear screen

WriteLine["How many triangles would you like"];

numbtri ← ReadDecimal[];

first ← ReadLine[];

second ← ReadLine[];

third ← ReadLine[];

FOR i IN [1..numbtri]

DO BEGIN --looping part of program

GetInput[]; --read input and sort points

-- Find higher of left and right endpoints dividing the triangle in two parts

-- and outputing the two parts

IF t.y = r.y AND t.y = l.y THEN

{bltptr.slx ← MIN[r.x.int,l.x.int,t.x.int];

srx.int←MAX[r.x.int,l.x.int,t.x.int];

Blt[];}

ELSE

BEGIN

niter: INTEGER;

lspos,rspos,apos: BOOLEAN;

lspos ← FindSlope[ls,t,l];

rspos ← IF t.y = r.y THEN FindSlope[rs,r,l] ELSE FindSlope[rs,t,r];

IF NOT lspos THEN bltptr.slx ← HalfUpdate [slx,ls];

IF rspos THEN [] ← HalfUpdate[srx,rs];

Blt[];

IF t.y = r.y THEN niter←l.y - t.y -2 ELSE niter ← MIN[l.y,r.y] - t.y -2;

IF niter > -1 THEN

{bltptr.slx←IF lspos THEN HalfUpdate[slx,ls] ELSE Update[slx,ls];

IF rspos THEN []←Update[srx,rs] ELSE [] ← HalfUpdate[srx,rs];

Blt[];

NewBlt[niter]};

IF l.y # r.y AND r.y # t.y THEN

BEGIN

IF l.y<r.y THEN

{IF lspos THEN NewBlt[1];

bltptr.slx ← HalfUpdate[slx,ls];

[] ← Update[srx,rs];

apos ← lspos;

lspos← FindSlope[ls,l,r];

IF apos OR NOT lspos THEN bltptr.slx ← HalfUpdate[slx,ls];

Blt[];

IF NOT apos THEN

{IF lspos THEN bltptr.slx ← HalfNUpdate[slx,ls];

NewBlt[1];}}

ELSE

{IF NOT rspos THEN NewBlt[1];

[] ← HalfUpdate[srx,rs];

bltptr.slx ← Update[slx,ls];

apos ← rspos;

rspos← FindSlope[rs,r,l];

IF rspos OR NOT apos THEN [] ← HalfUpdate[srx,rs];

Blt[];

IF apos THEN

{IF NOT rspos THEN [] ← HalfNUpdate[srx,rs];

NewBlt[1];}};

NewBlt[MAX[r.y,l.y] - MIN[l.y,r.y]-2];

END;

IF NOT lspos THEN [] ← HalfNUpdate[slx,ls];

IF rspos THEN [] ← HalfNUpdate[srx,rs];

NewBlt[1];

END;

ENDLOOP;

SELECT ReadChar[] FROM

'q => STOP;

'p => ChangeParms[];

ENDCASE;

ENDLOOP;

END.