
DIRECTORY Draw2d, G2dBasic, G2dScan, ImagerSample, Real, Rope, SF;

G2dScanImpl: CEDAR PROGRAM
IMPORTS ImagerSample, Real
EXPORTS G2dScan

~ BEGIN

Error: PUBLIC ERROR [code: ATOM, reason: ROPE] ~ CODE;
PixelProc:		TYPE ~ Draw2d.PixelProc;
IntegerPair:	TYPE ~ G2dBasic.IntegerPair;
SampleMap:	TYPE ~ ImagerSample.SampleMap;
ROPE:			TYPE ~ Rope.ROPE;

Vertex:		TYPE ~ G2dScan.Vertex;

Edge:			TYPE ~ RECORD [ 
v1, v2:				Vertex,	-- two end vertices of edge
x:						REAL,		-- x value of current scan line 
dx:						REAL,		-- change in x value per scan line 
val, dval:				REAL,		-- shade value and change in shade value per scan line 
ix:						INT,		-- current integer x value
ival:					INT];		-- current integer shade value

Edges:		TYPE ~ RECORD [length: INT м 0, seq: SEQUENCE maxLength: INT OF Edge];
abort: ERROR = CODE;

ScanTriangle: PUBLIC PROC [p0, p1, p2: IntegerPair, pixelProc: PixelProc] ~ {
DoScanTriangle: PROC ~ {
Edge: TYPE ~ RECORD [p0, p1: IntegerPair];
ScanSegment: PROC [y, xMin, xMax: INT] ~ {
IF xMin > xMax THEN {temp: INT м xMin; xMin м xMax; xMax м temp};
FOR x: NAT IN [xMin..xMax] DO
IF NOT pixelProc[x, y] THEN ERROR abort;
ENDLOOP;
};
top, mid, bot: IntegerPair;
IF p0.y = p1.y AND p0.y = p2.y
THEN ScanSegment[p0.y, MIN[p0.x, p1.x, p2.x], MAX[p0.x, p1.x, p2.x]]
ELSE {
InnerTriangle: PROC [e0, e1: Edge, skipFirst: BOOL м FALSE] ~ {
dy: REAL м e0.p1.y-e0.p0.y;
x0: REAL м e0.p0.x;
x1: REAL м e1.p0.x;
x0Inc: REAL м  (e0.p1.x-e0.p0.x)/dy;
x1Inc: REAL м  (e1.p1.x-e1.p0.x)/dy;
FOR y: INT IN [e0.p0.y..e0.p1.y] DO
IF NOT skipFirst OR y # e0.p0.y
THEN ScanSegment[y, Real.Round[x0], Real.Round[x1]];
x0 м x0+x0Inc;
x1 м x1+x1Inc;
ENDLOOP;
};
SELECT MIN[p0.y, p1.y, p2.y] FROM
p0.y => {
top м p0;
IF p1.y > p2.y THEN {mid м p2; bot м p1} ELSE {mid м p1; bot м p2};
};
p1.y => {
top м p1;
IF p0.y > p2.y THEN {mid м p2; bot м p0} ELSE {mid м p0; bot м p2};
};
ENDCASE => {
top м p2;
IF p0.y > p1.y THEN {mid м p1; bot м p0} ELSE {mid м p0; bot м p1};
};
SELECT TRUE FROM
top.y = mid.y => InnerTriangle[[top, bot], [mid, bot]];
mid.y = bot.y => InnerTriangle[[top, mid], [top, bot]];
ENDCASE => {
cut: IntegerPair м [top.x+(mid.y-top.y)*(bot.x-top.x)/(bot.y-top.y), mid.y];
InnerTriangle[[top, mid], [top, cut]];
InnerTriangle[[mid, bot], [cut, bot], TRUE];
};
};
};
DoScanTriangle[! abort => CONTINUE];
};

SortX: PROC [e: REF Edges] RETURNS [REF Edges] ~ {
DO
ok: BOOL м TRUE;
FOR i: INT IN [0..e.length-1) DO
ix1: INT м e[i].ix; ix2: INT м e[i+1].ix;
IF ix1 > ix2 OR (ix1 = ix2 AND e[i].v2.x > e[i+1].v2.x) THEN
{tmp: Edge м e[i]; e[i] м e[i+1]; e[i+1] м tmp; ok м FALSE};
ENDLOOP;
IF ok THEN RETURN[e];
ENDLOOP;
};

SortY: PROC [e: REF Edges] RETURNS [REF Edges] ~ {
DO
ok: BOOL м TRUE;
FOR i: INT IN [0..e.length-1) DO
IF e[i].v1.y > e[i+1].v1.y THEN
{tmp: Edge м e[i]; e[i] м e[i+1]; e[i+1] м tmp; ok м FALSE};
ENDLOOP;
IF ok THEN RETURN[e];
ENDLOOP;
};

EdgesFromVertices: PROC [vertices: LIST OF Vertex] RETURNS [edges: REF Edges] ~ {
n: INT м 0;
FOR l: LIST OF Vertex м vertices, l.rest WHILE l # NIL DO n м n+1; ENDLOOP;
edges м NEW[Edges[n]];
FOR l: LIST OF Vertex м vertices, l.rest WHILE l # NIL DO
v1: Vertex м l.first;
v2: Vertex м IF l.rest # NIL THEN l.rest.first ELSE vertices.first;
IF v1.y = v2.y THEN LOOP; -- discard horizontal edges
IF v2.y < v1.y THEN {v1 м v2; v2 м l.first};
edges[edges.length] м [v1: v1, v2: v2, x: v1.x, dx: REAL[v2.x-v1.x]/REAL[v2.y-v1.y],		ix: v1.x, val: v1.val, dval: REAL[v2.val-v1.val]/REAL[v2.y-v1.y], ival: v1.val];
edges.length м edges.length+1;
ENDLOOP;
};

VerticesFromPairs: PROC [pairs: LIST OF IntegerPair] RETURNS [ret: LIST OF Vertex м NIL] ~ {
FOR l: LIST OF IntegerPair м pairs, l.rest WHILE l # NIL DO
ret м CONS[[l.first.x, l.first.y, 0], ret];
ENDLOOP;
};

MinMax: PROC [vertices: LIST OF Vertex] RETURNS [box: SF.Box] ~ {
FOR l: LIST OF Vertex м vertices, l.rest WHILE l # NIL DO
box.min м [MIN[l.first.y, box.min.s], MIN[l.first.x, box.min.f]];
box.max м [MAX[l.first.y, box.max.s], MAX[l.first.x, box.max.f]];
ENDLOOP;
};

FlatShade: PUBLIC PROC [map: SampleMap, pairs: LIST OF IntegerPair, value: INT]
RETURNS [affectedRegion: SF.Box]
~ {
vertices: LIST OF Vertex м VerticesFromPairs[pairs];
width: INT м ImagerSample.GetSize[map].f;
line: ImagerSample.SampleBuffer ~ ImagerSample.ObtainScratchSamples[width];
wait: REF Edges м SortY[EdgesFromVertices[vertices]];
active: REF Edges м NEW[Edges[wait.length]];
waitIndex: INT м 0;
IF wait.length = 0 THEN RETURN[[[0, 0], [0, 0]]];
affectedRegion м MinMax[vertices];
FOR y: INT м wait[0].v1.y, y+1 DO
i: INT м 0;
WHILE i < active.length DO -- remove inactive edges
IF active[i].v2.y # y THEN {i м i+1; LOOP};
FOR j: INT IN [i..active.length-1) DO active[i] м active[i+1]; ENDLOOP;
active.length м active.length-1;
ENDLOOP;
WHILE waitIndex < wait.maxLength AND wait[waitIndex].v1.y = y DO -- add new active
active[active.length] м wait[waitIndex];
active.length м active.length+1;
waitIndex м waitIndex+1;
ENDLOOP;
IF active.length = 0 THEN EXIT;
active м SortX[active];
ImagerSample.GetSamples[map, [y, 0],, line, 0, width];
FOR i: INT м 0, i+2 WHILE i < active.length DO -- shade
FOR ix: INT IN [active[i].ix..active[i+1].ix] DO line[ix] м value; ENDLOOP;
ENDLOOP;
ImagerSample.PutSamples[map, [y, 0],, line, 0, width];
FOR i: INT IN [0..active.length) DO -- update edge.x
active[i].ix м Real.Round[active[i].x м active[i].x+active[i].dx];
ENDLOOP;
ENDLOOP;
ImagerSample.ReleaseScratchSamples[line];
};

GouraudShade: PUBLIC PROC [map: SampleMap, vertices: LIST OF Vertex]
RETURNS [affectedRegion: SF.Box]
~ {
width: INT м ImagerSample.GetSize[map].f;
line: ImagerSample.SampleBuffer ~ ImagerSample.ObtainScratchSamples[width];
wait: REF Edges м SortY[EdgesFromVertices[vertices]];
active: REF Edges м NEW[Edges[wait.length]];
waitIndex: INT м 0;
IF wait.length = 0 THEN RETURN[[[0, 0], [0, 0]]];
affectedRegion м MinMax[vertices];
FOR y: INT м wait[0].v1.y, y+1 DO
i: INT м 0;
WHILE i < active.length DO -- remove inactive edges
IF active[i].v2.y # y THEN {i м i+1; LOOP};
FOR j: INT IN [i..active.length-1) DO active[i] м active[i+1]; ENDLOOP;
active.length м active.length-1;
ENDLOOP;
WHILE waitIndex < wait.maxLength AND wait[waitIndex].v1.y = y DO -- add new active
active[active.length] м wait[waitIndex];
active.length м active.length+1;
waitIndex м waitIndex+1;
ENDLOOP;
IF active.length = 0 THEN EXIT;
active м SortX[active];
ImagerSample.GetSamples[map, [y, 0],, line, 0, width];
FOR i: INT м 0, i+2 WHILE i < active.length DO -- shade
e1: Edge м active[i];
e2: Edge м active[i+1];
dval: REAL м e2.val-e1.val;
IF ABS[dval] < 0.001 OR e1.ix = e2.ix
THEN FOR ix: INT IN [e1.ix..e2.ix] DO line[ix] м e1.ival; ENDLOOP
ELSE {
val: REAL м e1.val;
dv: REAL м dval/REAL[e2.ix-e1.ix];
FOR ix: INT IN [e1.ix..e2.ix] DO
line[ix] м Real.Round[val];
val м val+dv;
ENDLOOP
};
ENDLOOP;
ImagerSample.PutSamples[map, [y, 0],, line, 0, width];
FOR i: INT IN [0..active.length) DO -- update edge.x
e: Edge м active[i];
active[i].ix м Real.Round[active[i].x м e.x+e.dx];
active[i].ival м Real.Round[active[i].val м e.val+e.dval];
ENDLOOP;
ENDLOOP;
ImagerSample.ReleaseScratchSamples[line];
};


END.


    
G2dScanImpl.mesa
Copyright ╙ 1988, 1992 by Xerox Corporation.  All rights reserved.
Bloomenthal, November 22, 1992 1:19 pm PST
Types
Procedures
FOR i: INT IN [0..wait.length) DO PrintEdge[wait[i], "wait"]; ENDLOOP;
TerminalIO.PutF["y = %g\n", IO.int[y]];
PrintEdge[active[i], "remove from active"];
PrintEdge[active[active.length], "added to active"];
FOR i: INT IN [0..active.length) DO PrintEdge[active[i], "active"]; ENDLOOP;
PrintEdge: PROC [e: Edge, title: Rope.ROPE] ~ {
TerminalIO.PutF["%g: (%g, %g) to (%g, %g), ", IO.rope[title], IO.int[e.v1.x], IO.int[e.v1.y], IO.int[e.v2.x], IO.int[e.v2.y]];
TerminalIO.PutF["ix = %g, dx = %g\n", IO.int[e.ix], IO.real[e.dx]];
};

OrderEdges: PROC [edges: REF Edges] RETURNS [order: REF Edges] ~ {
order _ NEW[Edges[edges.length]];
FOR i: INT IN [0..edges.length) DO
y: INT _ edges[i].v1.y;
FOR j: INT IN [0..order.length) DO
IF y > order[j].v1.y THEN LOOP;
FOR k: INT DECREASING IN (j..order.length] DO order[k] _ order[k-1]; ENDLOOP;
order[j] _ edges[i];
EXIT;
REPEAT FINISHED => order[order.length] _ edges[i];
ENDLOOP;
order.length _ order.length+1;
ENDLOOP;
FOR i: INT IN [0..order.length) DO
dy: INT _ order[i].v2.y-order[i].v1.y;
order[i].x _ order[i].v1.x;
IF dy # 0 THEN order[i].dx _ REAL[order[i].v2.x-order[i].v1.x]/REAL[dy];
ENDLOOP;
};
Э╩Ю  Ц"cedarcode" styleХNewlineDelimiter
Щ ЩJЪЬ	╧eЬ6ЩBJЩ*JШ JЪ╧k	Ь9ШBJШ ЧЪ╨blЬЮЬЮШJЪЮЬШJЪЮЬШJШ ЧЪЬЮШJШ JЪЬЮЬЮЬЮЬ
ЮЬЮЬШ6ЧheadЪ╧lЩJЪЬ
ЮЬШ$JЪЬЮЬШ)JЪЬ
ЮЬШ)ЪЮЬЮЬЮЬШJШ ЧЪЬ	ЮЬШJШ ЧЪЬЮЬЮЬШJЪЬ╧cШ.JЪЬЮЮЮЬб"Ш/JЪЬЮЮЮЬб%Ш3JЪЬ
ЮЮЬб9ШLJЪЬ	ЮЬбШ)ЪЬ
ЮЬбШ/JШ ЧЧJЪЬЮЬЮЬ
ЮЬЮЬЮЬЮЬШNЧЪа
Щ
ЪЬЮЬЮЬШJШ ЧЪ╧nЬЮЬЮЬ4ШMЪвЬЮЬШJЪЬЮЬЮЬШ*ЪвЬЮЬЮЬШ*JЪЮЬЮЬЮЬ#ШAЪЮЬЮЬЮЬЮШJЪЮЬЮЬЮЬЮЬШ(JЪЮЬШЧJШЧJШЪЮЬЮЬШJЪЮЬЮЬЮЬШDЪЮЬШЪвЬЮЬЮЬЮЬШ?JЪЬЮЬШJЪЬЮЬШJЪЬЮЬШJЪЬЮЬШ$JЪЬЮЬШ$ЪЮЬЮЬЮЬЮШ#ЪЮЬЮЬЮЬШJЪЮЬ0Ш4ЧJШJШJЪЮЬШЧJШЧЪЮЬЮЬЮШ!Ш	JШ	JЪЮЬЮЬЮЬШCJШЧШ	JШ	JЪЮЬЮЬЮЬШCJШЧЪЮЬШJШ	JЪЮЬЮЬЮЬШCJШЧЧЪЮЬЮЬЮШJЪЬ7Ш7JЪЬ7Ш7ЪЮЬШJШLJШ&JЪЬ&ЮЬШ,JШЧЧJШЧJШЧЧJЪЬЮЬШ$JШJШ ЧЪ
вЬЮЬЮЬЮЬЮЬШ2ЪЮШJЪЬЮЬЮЬШЪЮЬЮЬЮЬЮШ JЪЬЬЮЬЮЬШ)ЪЮЬЮЬЮЬЮШ<JЪЬ5ЮЬШ<ЧJЪЮЬШЧJЪЮЬЮЬЮЬШJЪЮЬШЧJШJШ ЧЪ
вЬЮЬЮЬЮЬЮЬШ2ЪЮШJЪЬЮЬЮЬШЪЮЬЮЬЮЬЮШ ЪЮЬЮШJЪЬ5ЮЬШ<ЧJЪЮЬШЧJЪЮЬЮЬЮЬШJЪЮЬШЧJШJШ ЧЪвЬЮЬЮЬЮЬ	ЮЬ	ЮЬШQJЪЬЮЬШJЪЮЬЮЬЮЬЮЬЮЬЮЬ
ЮЬШKJЪЬЮЬШЪЮЬЮЬЮЬЮЬЮЬЮШ9JШJЪ	ЬЮЬ
ЮЬЮЬЮЬШCJЪЮЬЮЬЮЬбШ5JЪЮЬЮЬШ,JЪЬ╧sЬ
гЬгЬЮЬЮЬ+ЮЬЮЬШжJШJЪЮЬШЧJШJШ ЧЪвЬгЮгЬЮЬЮЬЮЬЮЬЮЬ
ЮЬШ\ЪЮЬЮЬЮЬЮЬЮЬЮШ;JЪЬЮЬ!Ш+JЪЮЬШЧJШJШ ЧЪвЬЮЬЮЬЮЬ	ЮЬЮЬ	ШAЪЮЬЮЬЮЬЮЬЮЬЮШ9JЪЬЮЬЮЬШAJЪЬЮЬЮЬШAJЪЮЬШЧJШJШ ЧЪв	ЬЮЬЮЬЮЬЮЬЮЬШOJЪЮЬЮЬШ JЪЬШJЪЬ
ЮЬЮЬ#Ш4JЪЬЮЬШ)JЪЬKШKJЪЬЮЬ,Ш5JЪЬЮЬ	ЮЬШ,JЪЬЮЬШJЪЮЬЮЬЮЬШ1JШ"JЪ
ЮЬЮЬЮЬЮЬЮЬЩFЪЮЬЮЬЮШ!JЪЬЮЬШJЪЬЮЬ	Щ'ЪЮЬЮЬбШ3JЪЮЬЮЬЮЬШ+JЩ+JЪ
ЮЬЮЬЮЬЮЬЮЬШGJШ JЪЮЬШЧЪЮЬЮЬЮЬбШRJШ(JЩ4JШ JШJЪЮЬШЧJЪЮЬЮЬЮЬШJШJЪ
ЮЬЮЬЮЬЮЬ!ЮЬЩLJШ6Ъ	ЮЬЮЬ
ЮЬЮЬбШ7JЪ
ЮЬЮЬЮЬ ЮЬЮЬШKJЪЮЬШЧJШ6Ъ	ЮЬЮЬЮЬЮЬбШ4JШBJЪЮЬШЧJЪЮЬШЧJШ)JШJШ ЧЪ
вЬЮЬЮЬЮЬЮЬШDJЪЮЬЮЬШ JЪЬШJЪЬЮЬШ)JЪЬKШKJЪЬЮЬ,Ш5JЪЬЮЬ	ЮЬШ,JЪЬЮЬШJЪЮЬЮЬЮЬШ1JШ"ЪЮЬЮЬЮШ!JЪЬЮЬШЪЮЬЮЬбШ3JЪЮЬЮЬЮЬШ+JЪ
ЮЬЮЬЮЬЮЬЮЬШGJШ JЪЮЬШЧЪЮЬЮЬЮЬбШRJШ(JШ JШJЪЮЬШЧJЪЮЬЮЬЮЬШJШJШ6Ъ	ЮЬЮЬ
ЮЬЮЬбШ7JШJШJЪЬЮЬШЪЮЬЮЬЮЬШ%JЪЮЬЮЬЮЬЮЬЮЬЮШAЪЮЬШJЪЬЮЬ
ШJЪЬЮЬЮЬШ"ЪЮЬЮЬЮЬЮШ JШJШJЪЮШЧJШЧЧJЪЮЬШЧJШ6Ъ	ЮЬЮЬЮЬЮЬбШ4JШJШ2JШ:JЪЮЬШЧJЪЮЬШЧJШ)JШJШ ЧЧJШ ЪЮЬШJШ Ъв	ЬЮЬЮЬЩ/JЪЬ.ЮЬЮЬЮЬЮЬЮЬЩ~JЪЬ&ЮЬЮЬЩCJЩJЩ ЧЪ
в
ЬЮЬ	ЮЬЮЬ	ЮЬЩBJЪЬЮЬЩ!ЪЮЬЮЬЮЬЮЩ"JЪЬЮЬЩЪЮЬЮЬЮЬЮЩ"JЪЮЬЮЬЮЬЩJЪЮЬЮЬЮ
ЬЮЬЮЬЮЬЩMJЩJЪЮЬЩJЪЮЬЮЬ#Щ2JЪЮЬЩЧJЩJЪЮЬЩЧЪЮЬЮЬЮЬЮЩ"JЪЬЮЬЩ&JЪЬЩJЪЮЬЮЬЮЬЮЬЩHJЪЮЬЩЧJЩЧЧJШ Ч ЕЧ    ▄  ,Р  