<<>> <> <> <> 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. <> <> <> <<};>> <<>> <> <> <> <> <> < order[j].v1.y THEN LOOP;>> <> <> <> < order[order.length] _ edges[i];>> <> <> <> <> <> <> <> <> <<};>>