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];
};
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;
};
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 i: INT IN [0..wait.length) DO PrintEdge[wait[i], "wait"]; ENDLOOP;
FOR y:
INT ¬ wait[0].v1.y, y+1
DO
i: INT ¬ 0;
TerminalIO.PutF["y = %g\n", IO.int[y]];
WHILE i < active.length
DO
-- remove inactive edges
IF active[i].v2.y # y THEN {i ¬ i+1; LOOP};
PrintEdge[active[i], "remove from active"];
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];
PrintEdge[active[active.length], "added to active"];
active.length ¬ active.length+1;
waitIndex ¬ waitIndex+1;
ENDLOOP;
IF active.length = 0 THEN EXIT;
active ¬ SortX[active];
FOR i: INT IN [0..active.length) DO PrintEdge[active[i], "active"]; ENDLOOP;
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];
};