TilersImpl.mesa
Last Edited by: Crow, December 16, 1986 4:01:33 pm PST
Bloomenthal, January 19, 1987 5:36:29 pm PST
DIRECTORY
Atom      USING [ PropList, GetPropFromList, PutPropOnList ],
Real      USING [ FixI, Float, RoundI, RoundC, FixC, LargestNumber ],
RealFns     USING [ SqRt, Power],
Imager     USING [ Context, PathProc, MaskFill, SetColor ],
ImagerColor    USING [ ColorFromRGB ],
ImagerPixelMap   USING [ PixelMap ],
Vector3d     USING [ Normalize, Mul, Add ],
QuickViewer    USING [ DrawInViewer ],
Pixels      USING [ GetSampleSet, PixelBuffer, SampleSet, SampleSetSequence ],
ScanConvert    USING [ Spot, IntPairSequence, GetColorProc, ConstantPoly,
          SmoothPoly, ShinyPoly, SpotSequence, justNoticeable,
          PutSpot, Extend ],
ThreeDBasics   USING [ Context, Pair, PatchProc, RealSequence, RGB, ShadingValue,
          Triple, Vertex, VertexInfo, VtxToRealSeqProc ],
ThreeDScenes   USING [ GetShading, ShadeVtx, ShadingProcs],
ThreeDSurfaces   USING [ Patch ],
ThreeDMisc    USING [ GetMappedColor ],
TextureMaps    USING [ GetTxtrAt, TextureMap ],
Tilers      USING [ LerpVtx, LerpVtxSequence, FancyPatch ];
TilersImpl: CEDAR MONITOR
IMPORTS Real, Imager, ImagerColor, QuickViewer, RealFns, ThreeDMisc, ScanConvert, Vector3d, Atom, Pixels, ThreeDScenes, TextureMaps
EXPORTS Tilers
= BEGIN
Types
TilersError: PUBLIC SIGNAL [reason: ATOM] ~ CODE;
RGB: TYPE ~ ThreeDBasics.RGB;
Pair: TYPE ~ ThreeDBasics.Pair;          -- RECORD [ x, y: REAL];
Triple: TYPE ~ ThreeDBasics.Triple;        -- RECORD [ x, y, z: REAL];
SampleSet: TYPE ~ Pixels.SampleSet;
Patch: TYPE ~ ThreeDSurfaces.Patch;
ColorPrimary: TYPE ~ { red, green, blue, grey };
PixelMap: TYPE ~ ImagerPixelMap.PixelMap;
BooleanSequence: TYPE ~ RECORD [ length: NAT, s: SEQUENCE maxLength: NAT OF BOOLEAN ];
RealSequence: TYPE ~ ThreeDBasics.RealSequence;
Vertex: TYPE ~ ThreeDBasics.Vertex;
VertexInfo: TYPE ~ ThreeDBasics.VertexInfo;
LerpVtx: TYPE ~ Tilers.LerpVtx;
RECORD [x, y: REAL, val: REF RealSequence];
LerpVtxSequence: TYPE ~ Tilers.LerpVtxSequence;
RECORD [ length: NAT, s: SEQUENCE maxLength: NAT OF REF LerpVtx ];
FancyPatch: TYPE ~ Tilers.FancyPatch;
RECORD [ recurseLevel: NAT ← 0, spot: ScanConvert.Spot,
vtx: SEQUENCE length: NAT OF LerpVtx ];
Data Structure for trapezoid edges
EdgeBlock: TYPE ~ RECORD [
moreVertical: BOOLEAN, start, end: REAL,
x, y, xIncr, yIncr: REAL,
val, incr: REF RealSequence
];
ScanSegment: TYPE ~ RECORD [
start, end: REAL,
coverage, cvrgIncr: REAL,
lMask, rMask: CARDINAL,
val, yIncr, xIncrVal, xIncrForY: REF RealSequence
];
ScanSegSequence: TYPE ~ RECORD [
length: NAT,
segs: SEQUENCE maxLength: NAT OF REF ScanSegment
];
IntPolySequence: TYPE ~ RECORD [
length: NAT,
polys: SEQUENCE maxLength: NAT OF REF ScanConvert.IntPairSequence
];
SpotSeqSequence: TYPE ~ RECORD [
length: NAT,
s: SEQUENCE maxLength: NAT OF REF ScanConvert.SpotSequence
];
HilitSeqs: TYPE ~ RECORD [   -- reflection vectors and light source flags for hilites
refls: REF RealSequence,
flags: REF BooleanSequence
];
HilitSeqsSequence: TYPE ~ RECORD [
length: NAT,
s: SEQUENCE maxLength: NAT OF REF HilitSeqs
];
Global Constants
tblLngth: NAT ~ 256;
justNoticeable: REAL ~ ScanConvert.justNoticeable;         -- 0.02
Global Variables
recurseLimit: NAT ← 32;       -- limits recursion in fancy tiler
weight: ARRAY [0..tblLngth] OF REAL;   -- filter table
allocation avoidance structures - caches of peculiar data types
pixelBytesCache: REF Pixels.SampleSetSequence ← NEW[ Pixels.SampleSetSequence[2] ];
pixelBytesCacheLength: NAT ← 2;
pixelBytesCachePtr: NAT ← 0;        -- place to return next free record
intPolyCache: REF IntPolySequence ← NEW[ IntPolySequence[2] ]; -- for constant tiler
intPolyCacheLength: NAT ← 2;
intPolyCachePtr: NAT ← 0;
scanSegCache: REF ScanSegSequence ← NEW[ ScanSegSequence[2] ]; -- for ShowSteepTrap
scanSegCacheLength: NAT ← 2;
scanSegCachePtr: NAT ← 0;
spotSeqCache: REF SpotSeqSequence ← NEW[ SpotSeqSequence[2] ]; -- for smooth tiler
spotSeqCacheLength: NAT ← 2;
spotSeqCachePtr: NAT ← 0;
hilitSeqCache: REF HilitSeqsSequence ← NEW[ HilitSeqsSequence[2] ]; -- for hilites
hilitSeqCacheLength: NAT ← 2;
hilitSeqCachePtr: NAT ← 0;
vertexCache: REF LerpVtxSequence ← NEW[ LerpVtxSequence[2] ]; -- for hilites
vertexCacheLength: NAT ← 2;
vertexCachePtr: NAT ← 0;
Caching Procedures
GetPixelBytes: ENTRY PROC[size: NAT] RETURNS[SampleSet] ~ {
ENABLE UNWIND => NULL;
s: SampleSet;
IF pixelBytesCachePtr = 0
THEN s ← Pixels.GetSampleSet[size]
ELSE {
pixelBytesCachePtr ← pixelBytesCachePtr - 1;
s ← pixelBytesCache[pixelBytesCachePtr];
pixelBytesCache[pixelBytesCachePtr] ← NIL;
IF s.maxLength < size THEN s ← Pixels.GetSampleSet[size];
};
RETURN[ s ];
};
ReleasePixelBytes: ENTRY PROC[s: SampleSet] ~ {
ENABLE UNWIND => NULL;
IF pixelBytesCachePtr = pixelBytesCacheLength THEN {
pixelBytesCache ← NEW[ Pixels.SampleSetSequence[pixelBytesCacheLength + 2] ];
pixelBytesCacheLength ← pixelBytesCacheLength + 2;
pixelBytesCachePtr ← 0;
};
pixelBytesCache[pixelBytesCachePtr] ← s;
pixelBytesCachePtr ← pixelBytesCachePtr + 1;
};
GetScanSeg: ENTRY PROC[size: NAT] RETURNS[REF ScanSegment] ~ {
ENABLE UNWIND => NULL;
seg: REF ScanSegment;
IF scanSegCachePtr = 0
THEN seg ← NEW[ ScanSegment ]
ELSE {
scanSegCachePtr ← scanSegCachePtr - 1;
seg ← scanSegCache[scanSegCachePtr];
scanSegCache[scanSegCachePtr] ← NIL;
};
IF seg.val = NIL OR seg.val.maxLength < size THEN {
seg.val ← NEW[ RealSequence[size] ];
seg.yIncr ← NEW[ RealSequence[size] ];
seg.xIncrVal ← NEW[ RealSequence[size] ];
seg.xIncrForY ← NEW[ RealSequence[size] ];
};
RETURN[ seg ];
};
ReleaseScanSeg: ENTRY PROC[s: REF ScanSegment] ~ {
ENABLE UNWIND => NULL;
IF scanSegCachePtr = scanSegCacheLength THEN {
scanSegCache ← NEW[ ScanSegSequence[scanSegCacheLength + 2] ];
scanSegCacheLength ← scanSegCacheLength + 2;
scanSegCachePtr ← 0;
};
scanSegCache[scanSegCachePtr] ← s;
scanSegCachePtr ← scanSegCachePtr + 1;
};
GetSpotSeq: ENTRY PROC[size: NAT] RETURNS[REF ScanConvert.SpotSequence] ~ {
ENABLE UNWIND => NULL;
s: REF ScanConvert.SpotSequence;
IF spotSeqCachePtr = 0
THEN s ← NEW[ ScanConvert.SpotSequence[size] ]
ELSE {
spotSeqCachePtr ← spotSeqCachePtr - 1;
s ← spotSeqCache[spotSeqCachePtr];
spotSeqCache[spotSeqCachePtr] ← NIL;
IF s.maxLength < size THEN s ← NEW[ ScanConvert.SpotSequence[size] ];
};
RETURN[ s ];
};
ReleaseSpotSeq: ENTRY PROC[s: REF ScanConvert.SpotSequence] ~ {
ENABLE UNWIND => NULL;
IF spotSeqCachePtr = spotSeqCacheLength THEN {
spotSeqCache ← NEW[ SpotSeqSequence[spotSeqCacheLength + 2] ];
spotSeqCacheLength ← spotSeqCacheLength + 2;
spotSeqCachePtr ← 0;
};
spotSeqCache[spotSeqCachePtr] ← s;
spotSeqCachePtr ← spotSeqCachePtr + 1;
};
GetHilitSeqs: ENTRY PROC[reflSize, flagSize: NAT]
     RETURNS[REF HilitSeqs] ~ {
ENABLE UNWIND => NULL;
s: REF HilitSeqs;
IF hilitSeqCachePtr = 0
THEN {
s ← NEW[ HilitSeqs ];
s.refls ← NEW[ RealSequence[reflSize] ];
s.flags ← NEW[ BooleanSequence[flagSize] ];
}
ELSE {
hilitSeqCachePtr ← hilitSeqCachePtr - 1;
s ← hilitSeqCache[hilitSeqCachePtr];
hilitSeqCache[hilitSeqCachePtr] ← NIL;
IF s.refls.maxLength < reflSize THEN s.refls ← NEW[ RealSequence[reflSize] ];
IF s.flags.maxLength < flagSize THEN s.flags ← NEW[ BooleanSequence[flagSize] ];
};
RETURN[ s ];
};
ReleaseHilitSeqs: ENTRY PROC[s: REF HilitSeqs] ~ {
ENABLE UNWIND => NULL;
IF hilitSeqCachePtr = hilitSeqCacheLength THEN {
hilitSeqCache ← NEW[ HilitSeqsSequence[hilitSeqCacheLength + 2] ];
hilitSeqCacheLength ← hilitSeqCacheLength + 2;
hilitSeqCachePtr ← 0;
};
hilitSeqCache[hilitSeqCachePtr] ← s;
hilitSeqCachePtr ← hilitSeqCachePtr + 1;
};
GetVertex: ENTRY PROC[size: NAT] RETURNS[REF LerpVtx] ~ {
ENABLE UNWIND => NULL;
vtx: REF LerpVtx;
IF vertexCachePtr = 0
THEN vtx ← NEW[ LerpVtx ]
ELSE {
vertexCachePtr ← vertexCachePtr - 1;
vtx ← vertexCache[vertexCachePtr];
vertexCache[vertexCachePtr] ← NIL;
};
IF vtx.val = NIL OR vtx.val.maxLength < size THEN vtx.val ← NEW[ RealSequence[size] ];
RETURN[ vtx ];
};
ReleaseVertex: ENTRY PROC[vtx: REF LerpVtx] ~ {
ENABLE UNWIND => NULL;
IF vertexCachePtr = vertexCacheLength THEN {
vertexCache ← NEW[ LerpVtxSequence[vertexCacheLength + 2] ];
vertexCacheLength ← vertexCacheLength + 2;
vertexCachePtr ← 0;
};
vertexCache[vertexCachePtr] ← vtx;
vertexCachePtr ← vertexCachePtr + 1;
};
Utility procedures
Sqr: PROCEDURE [number: REAL] RETURNS [REAL] ~ INLINE { RETURN[number * number]; };
Sgn: PROCEDURE [number: REAL] RETURNS [REAL] ~ INLINE {
IF number < 0. THEN RETURN[-1.] ELSE RETURN[1.];
};
Ceiling: PROC[ in: REAL ] RETURNS[ out: INTEGER ] ~ {
out ← Real.RoundI[in];
IF Real.Float[out] < in THEN out ← out + 1;
};
Floor: PROC[ in: REAL ] RETURNS[ out: INTEGER ] ~ {
out ← Real.RoundI[in];
IF Real.Float[out] > in THEN out ← out - 1;
};
Init: PROC[] ~ {
Calculates the integral over the left half of a pyramid function, equal to the left half of a parabolic window or B-spline basis function
FOR i: NAT IN [0..tblLngth/2] DO
t: REAL ← i * 1.0 / (tblLngth/2);
weight[i]     ← Sqr[t] / 2.;
weight[i + tblLngth/2] ← 1. - Sqr[1. - t] / 2.;
ENDLOOP;
};
DupLerpVtx: PROC[vtx: LerpVtx] RETURNS[newVtx: LerpVtx] ~ {
newVtx.x ← vtx.x;
newVtx.y ← vtx.y;
newVtx.val ← NEW[RealSequence[vtx.val.length]];
FOR i: NAT IN [0..vtx.val.length) DO newVtx.val[i] ← vtx.val[i] ENDLOOP;
newVtx.val.length ← vtx.val.length;
};
DupEdgeBlock: PROC[srce: EdgeBlock] RETURNS[dest : EdgeBlock] ~ {
dest.moreVertical ← srce.moreVertical;
dest.start ← srce.start; dest.end ← srce.end;
dest.x ← srce.x; dest.xIncr ← srce.xIncr;
dest.y ← srce.y; dest.yIncr ← srce.yIncr;
dest.val ← NEW[RealSequence[srce.val.length]]; dest.val.length ← srce.val.length;
FOR i: NAT IN [0..srce.val.length) DO dest.val[i] ← srce.val[i] ENDLOOP;
dest.incr ← NEW[RealSequence[srce.incr.length]]; dest.incr.length ← srce.incr.length;
FOR i: NAT IN [0..srce.incr.length) DO dest.incr[i] ← srce.incr[i] ENDLOOP;
};
GetLerpedVals: ThreeDBasics.VtxToRealSeqProc ~ {
PROC[dest: REF RealSequence, source: VertexInfo] RETURNS[REF RealSequence];
IF dest = NIL OR dest.maxLength < 9 THEN dest ← NEW[ RealSequence[9] ];  -- leave room
dest[0] ← source.shade.er;
dest[1] ← source.shade.eg;
dest[2] ← source.shade.eb;
dest[3] ← source.shade.et;
dest.length ← 4;
RETURN [dest];
};
GetLerpedValsForHighLights: ThreeDBasics.VtxToRealSeqProc ~ {
PROC[dest: REF RealSequence, source: VertexInfo] RETURNS[REF RealSequence];
IF dest = NIL OR dest.maxLength < 15 THEN dest ← NEW[ RealSequence[15] ]; -- leave room
dest[0] ← source.shade.r;
dest[1] ← source.shade.g;
dest[2] ← source.shade.b;
dest[3] ← source.shade.t;
dest[4] ← source.shade.exn;
dest[5]  ← source.shade.eyn;
dest[6] ← source.shade.ezn;
dest[7] ← source.coord.ex;
dest[8] ← source.coord.ey;
dest[9] ← source.coord.ez;
dest.length ← 10;
RETURN [dest];
};
RecoverColor: ScanConvert.GetColorProc ~ {
PROC[spot: Spot] RETURNS[RGB, REAL]
IF Atom.GetPropFromList[spot.props, $TextureMap] # NIL
THEN spot ← TextureMaps.GetTxtrAt[spot];
IF Atom.GetPropFromList[spot.props, $HltPwr] # NIL
THEN spot ← AddHighlight[spot];
RETURN[
[ R: spot.val[0], G: spot.val[1], B: spot.val[2] ],
spot.val[3]
];
};
AddHighlight: PUBLIC PROC[spot: ScanConvert.Spot] RETURNS[ScanConvert.Spot] ~ {
context: REF ThreeDBasics.Context ← NARROW[ Atom.GetPropFromList[spot.props, $Context] ];
ref: REF ← Atom.GetPropFromList[spot.props, $HltPwr];
shininess: REAL ← IF ref # NIL THEN NARROW[ref, REF REAL]^ ELSE 0.0;
pt: VertexInfo;
pt.coord.ex ← spot.val[7]; pt.coord.ey ← spot.val[8]; pt.coord.ez ← spot.val[9];
pt.shade.exn ← spot.val[4]; pt.shade.eyn ← spot.val[5]; pt.shade.ezn ← spot.val[6];
pt.shade.r ← spot.val[0]; pt.shade.g ← spot.val[1]; pt.shade.b ← spot.val[2];
pt.shade.t ← spot.val[3];
[ [spot.val[0], spot.val[1], spot.val[2]], spot.val[3] ] ← ThreeDScenes.ShadeVtx[
context, pt, shininess];
RETURN[spot];
};
Simple, Fast Tilers
PolygonTiler: PUBLIC PROC[context: REF ThreeDBasics.Context, poly: REF Patch] ~ {
shadingType: REF ANY ← Atom.GetPropFromList[poly.props, $Type ];
IF context.alphaBuffer
THEN {
tilingProc: REF ANY ← Atom.GetPropFromList[poly.props, $Tiler ];
IF tilingProc = NIL
THEN FancyTiler[context, poly]   -- standard anti-aliasing tiler
ELSE [] ← NARROW[tilingProc, REF ThreeDBasics.PatchProc]^[context, poly]; -- other
}
ELSE IF Atom.GetPropFromList[poly.props, $Shininess ] # NIL
THEN ShinyTiler[context, poly]         -- highlight tiler
ELSE SELECT shadingType FROM
$Faceted => IF NOT context.depthBuffer
THEN ConstantTiler[context, poly]
ELSE SmoothTiler[context, poly];
ENDCASE => SmoothTiler[context, poly];   -- default is smooth shading
};
ConstantTiler: PUBLIC PROC[ context: REF ThreeDBasics.Context, poly: REF Patch] ~ {
pixelBytes: SampleSet ← GetPixelBytes[3];
intPoly: REF ScanConvert.SpotSequence ← GetSpotSeq[poly.nVtces];
SELECT context.renderMode FROM 
$Dithered, $Bitmap, $Interpress  => {    -- use Imager in these modes
Path: Imager.PathProc ~ {
moveTo[[ poly.vtx[poly.nVtces-1].coord.sx, poly.vtx[poly.nVtces-1].coord.sy ]];
FOR i: NAT IN [0..poly.nVtces) DO
lineTo[[ poly.vtx[i].coord.sx, poly.vtx[i].coord.sy ]];
ENDLOOP;
};
DoFill: PROC[ imagerCtx: Imager.Context ] ~ {
Imager.SetColor[ imagerCtx, ImagerColor.ColorFromRGB[
[ poly.vtx[0].shade.er, poly.vtx[0].shade.eg, poly.vtx[0].shade.eb ]
] ];
Imager.MaskFill[imagerCtx, Path];
};
IF context.renderMode = $Interpress
THEN DoFill[ NARROW[ Atom.GetPropFromList[context.props, $ImagerCtx] ] ]
ELSE QuickViewer.DrawInViewer[ NARROW[context.viewer], DoFill ];
RETURN;
};
$PseudoColor => {
pixelBytes[0] ← ThreeDMisc.GetMappedColor[
context,
[poly.vtx[0].shade.er, poly.vtx[0].shade.eg, poly.vtx[0].shade.eb]
];
pixelBytes.length ← 1;
};
$Grey   => {
pixelBytes[0] ← Real.RoundC[
(poly.vtx[0].shade.er + poly.vtx[0].shade.eg + poly.vtx[0].shade.eb)/3
];
pixelBytes.length ← 1;
};
$FullColor, $Dorado24  => {
pixelBytes[0] ← Real.RoundC[poly.vtx[0].shade.er * 255.0];
pixelBytes[1] ← Real.RoundC[poly.vtx[0].shade.eg * 255.0];
pixelBytes[2] ← Real.RoundC[poly.vtx[0].shade.eb * 255.0];
pixelBytes.length ← 3;
};
ENDCASE  => TilersError[$BadRenderMode];
FOR i: CARDINAL IN [0..poly.nVtces) DO
intPoly[i].x ← Real.FixC[poly.vtx[i].coord.sx];
intPoly[i].y ← Real.FixC[poly.vtx[i].coord.sy];
ENDLOOP;
intPoly.length ← poly.nVtces;
ScanConvert.ConstantPoly[context.display, pixelBytes, intPoly];
ReleasePixelBytes[pixelBytes];
};
SmoothTiler: PUBLIC PROC[ context: REF ThreeDBasics.Context, poly: REF Patch] ~ {
spotSeq: REF ScanConvert.SpotSequence ← GetSpotSeq[poly.nVtces];
zScale: NAT ← LAST[NAT] / context.depthResolution;
addOn: NAT ← IF context.depthBuffer THEN 1 ELSE 0;
spotSeq.length ← poly.nVtces;
FOR i: NAT IN [0..poly.nVtces) DO
SELECT context.renderMode FROM 
$Grey  => {
IF spotSeq[i].val = NIL OR spotSeq[i].val.maxLength < 1+addOn
THEN spotSeq[i].val ← NEW[RealSequence[1]];
spotSeq[i].val[0] ←
    (poly.vtx[i].shade.er + poly.vtx[i].shade.eg + poly.vtx[i].shade.eb) / 3;
spotSeq[i].val.length ← 1+addOn;
};
$Dithered, $PseudoColor, $FullColor, $Dorado24  => {
IF spotSeq[i].val = NIL OR spotSeq[i].val.maxLength < 3+addOn
THEN spotSeq[i].val ← NEW[RealSequence[3+addOn]];
spotSeq[i].val[0] ← poly.vtx[i].shade.er;
spotSeq[i].val[1] ← poly.vtx[i].shade.eg;
spotSeq[i].val[2] ← poly.vtx[i].shade.eb;
spotSeq[i].val.length ← 3+addOn;
};
ENDCASE  => TilersError[$BadRenderMode];
IF context.depthBuffer
THEN spotSeq[i].val[spotSeq[i].val.length-1] ← Real.FixC[poly.vtx[i].coord.sz * zScale];
spotSeq[i].x ← Real.FixC[poly.vtx[i].coord.sx];
spotSeq[i].y ← Real.FixC[poly.vtx[i].coord.sy];
ENDLOOP;
ScanConvert.SmoothPoly[context.display, spotSeq, context.renderMode];
ReleaseSpotSeq[spotSeq];
};
ShinyTiler for Phong shading and Highlight Utilities
ShinyTiler: PUBLIC PROC[context: REF ThreeDBasics.Context, poly: REF Patch] ~ {
spotSeq: REF ScanConvert.SpotSequence;
zScale: NAT ← LAST[NAT] / context.depthResolution;
addOn: NAT ← IF context.depthBuffer THEN 1 ELSE 0;
hiliteInfo: REF HilitSeqs;
idealReflSeq: REF RealSequence;
lightFlags: REF BooleanSequence;
shininess: REAL ← NARROW[Atom.GetPropFromList[poly.props, $Shininess], REF REAL]^;
shinyPwr: NAT ← Real.RoundC[shininess];
normalInfoLength, nmlCnt, hltCnt: NAT ← 0;
IF context.renderMode = $Bitmap THEN TilersError[$BadRenderMode];
hiliteInfo ← GotAHilite[context, poly, shininess]; -- do we have a possible highlight?
IF hiliteInfo = NIL THEN {        -- no highlight
IF Atom.GetPropFromList[poly.props, $Type ] = $Faceted
THEN IF NOT context.depthBuffer
THEN ConstantTiler[context, poly]
ELSE SmoothTiler[context, poly]
ELSE SmoothTiler[context, poly];
RETURN[];
};
spotSeq ← GetSpotSeq[poly.nVtces];
idealReflSeq ← hiliteInfo.refls;      -- got a highlight, lets do it!
lightFlags ← hiliteInfo.flags;
FOR j: NAT IN [0 .. context.lights.length) DO  -- figure storage needed for extra normal info
IF lightFlags[j] THEN normalInfoLength ← normalInfoLength + 5;
ENDLOOP;
FOR i: NAT IN [0..poly.nVtces) DO      -- get storage for each vertex in turn
IF spotSeq[i].val = NIL OR spotSeq[i].val.maxLength < 3 + normalInfoLength + addOn
THEN spotSeq[i].val ← NEW[RealSequence[3 + normalInfoLength + addOn]];
spotSeq[i].val[0] ← poly.vtx[i].shade.er * 255.0;
spotSeq[i].val[1] ← poly.vtx[i].shade.eg * 255.0;
spotSeq[i].val[2] ← poly.vtx[i].shade.eb * 255.0;
spotSeq[i].x ← Real.FixC[poly.vtx[i].coord.sx];
spotSeq[i].y ← Real.FixC[poly.vtx[i].coord.sy];
spotSeq[i].val.length ← 3 + normalInfoLength + addOn;
IF context.depthBuffer
THEN spotSeq[i].val[spotSeq[i].val.length-1] ← Real.FixC[poly.vtx[i].coord.sz * zScale];
ENDLOOP;
spotSeq.length ← poly.nVtces;
FOR j: NAT IN [0..context.lights.length) DO -- pick up info for each highlight-causing light
IF lightFlags[j] THEN {
FOR i: NAT IN [0..poly.nVtces) DO
outBase: NAT ← 3 + hltCnt*5; -- r, g, b + 5 per highlight
inBase: NAT ← (j * 5 * poly.nVtces) + (i * 5);
FOR k: NAT IN [0..5) DO
spotSeq[i].val[outBase+k] ← 256.0 * idealReflSeq[inBase + k];
ENDLOOP;
ENDLOOP;
hltCnt ← hltCnt + 1;
};
ENDLOOP;
ScanConvert.ShinyPoly[context.display, spotSeq, shinyPwr, context.renderMode];
ReleaseHilitSeqs[hiliteInfo];
ReleaseSpotSeq[spotSeq];
};
defaultHiliteState: BOOL ← FALSE;    -- Kludge of the day
PhongShadeAllPolygons: PUBLIC PROC ~ {defaultHiliteState ← TRUE};
PhongShadeOnlyHighLightedPolygons: PUBLIC PROC ~ {defaultHiliteState ← FALSE};
GotAHilite: PROC[context: REF ThreeDBasics.Context, poly: REF Patch, shininess: REAL]
    RETURNS[REF HilitSeqs ] ~ {
XfmNormal: PROC[light: Vertex, vtx: VertexInfo] RETURNS[ Triple ] ~ {
Transform the normal to a space in which a normal aligned with the z-axis would reflect the light straight into the eye
toLightSrc: Triple ← Vector3d.Normalize[     -- normalized direction to light
[ light.ex - vtx.coord.ex, light.ey - vtx.coord.ey, light.ez - vtx.coord.ez ] ];
toEye: Triple ← Vector3d.Normalize[      -- normalized direction to eye
[ -vtx.coord.ex, -vtx.coord.ey, -vtx.coord.ez ] ];
idealRefl: Triple ← Vector3d.Mul[ Vector3d.Add[toLightSrc, toEye], 0.5 ];
hypotA: REAL ← RealFns.SqRt[ Sqr[idealRefl.x] + Sqr[idealRefl.z] ]; -- rotate about y
cosA: REAL ← idealRefl.z / hypotA; sinA: REAL ← idealRefl.x / hypotA;
hypotB: REAL ← RealFns.SqRt[ Sqr[idealRefl.y] + Sqr[hypotA] ];  -- rotate about x
cosB: REAL ← hypotA / hypotB; sinB: REAL ← idealRefl.y / hypotB;
tx: REAL ← cosA*vtx.shade.exn - sinA*vtx.shade.ezn;
ty: REAL ← vtx.shade.eyn;
tz: REAL ← sinA*vtx.shade.exn + cosA*vtx.shade.ezn;
RETURN[ Vector3d.Normalize[ [x: tx, y: cosB*ty - sinB*tz, z: sinB*ty + cosB*tz] ] ];
};
gotAHilite: BOOLEAN ← FALSE;
gotAHilite: BOOLEAN ← defaultHiliteState;
seqLength: NAT ← (poly.nVtces*5) * context.lights.length;
hilitInfo: REF HilitSeqs ← GetHilitSeqs[seqLength, context.lights.length];
idealReflSeq: REF RealSequence ← hilitInfo.refls;
lightFlags: REF BooleanSequence ← hilitInfo.flags;
lightFlags.length ← context.lights.length;
FOR j: NAT IN [0..context.lights.length) DO
lightClr: RGB ← NARROW[ThreeDScenes.GetShading[ context.lights[j], $Color], REF RGB ]^;
minX, minY: REAL ← Real.LargestNumber;
maxX, maxY: REAL ← -Real.LargestNumber;
FOR i: NAT IN [0..poly.nVtces) DO -- get bounding box on highlight reflection vectors
reflVec: Triple ← XfmNormal[ context.lights[j].centroid, poly[i] ];
base: NAT ← (j * 5 * poly.nVtces) + (i * 5);
minX ← MIN[minX, reflVec.x];   maxX ← MAX[maxX, reflVec.x];
minY ← MIN[minY, reflVec.y];  maxY ← MAX[maxY, reflVec.y];
idealReflSeq[base ] ← reflVec.x;  
idealReflSeq[base+1] ← reflVec.y;
idealReflSeq[base+2] ← lightClr.R;  
idealReflSeq[base+3] ← lightClr.G;
idealReflSeq[base+4] ← lightClr.B;
idealReflSeq.length ← base+5;
ENDLOOP;
Get closest point to zero spanned in bounding box
minX ← IF Sgn[minX] # Sgn[maxX] THEN 0.0 ELSE MIN[ABS[minX], ABS[maxX]];
minY ← IF Sgn[minY] # Sgn[maxY] THEN 0.0 ELSE MIN[ABS[minY], ABS[maxY]];
IF RealFns.Power[ MAX[ 0.0, 1.0 - Sqr[minX] - Sqr[minY] ], shininess ] > justNoticeable
THEN { gotAHilite ← TRUE; lightFlags[j] ← TRUE; }
ELSE lightFlags[j] ← FALSE;
ENDLOOP;
IF NOT gotAHilite THEN { ReleaseHilitSeqs[hilitInfo]; hilitInfo ← NIL; };
RETURN[hilitInfo];
};
Anti-Aliasing Tiler for Fancier shading, etc.
FancyTiler: PUBLIC PROC[context: REF ThreeDBasics.Context, poly: REF Patch] ~ {
getVtxProc: ThreeDBasics.VtxToRealSeqProc ← NIL;
getColorProc: ScanConvert.GetColorProc ← NIL;
LerpVtxFromVtx: PROC[vtx: VertexInfo, fancy: BOOL] RETURNS[LerpVtx] ~ {
lerpVtx: LerpVtx ← [vtx.coord.sx, vtx.coord.sy, NIL];
lerpVtx.val ← IF fancy
THEN GetLerpedValsForHighLights[dest: lerpVtx.val, source: vtx]
ELSE GetLerpedVals[dest: lerpVtx.val, source: vtx];
RETURN[lerpVtx];
};
AddTextureCoords: PROC[vtx: LerpVtx, addVtx: VertexInfo] RETURNS[LerpVtx] ~ {
IF vtx.val.maxLength < vtx.val.length+2
THEN vtx.val ← ScanConvert.Extend[vtx.val, vtx.val.length+2];
vtx.val[vtx.val.length ] ← NARROW[addVtx.aux, REF Triple].x;
vtx.val[vtx.val.length+1] ← NARROW[addVtx.aux, REF Triple].y;
vtx.val.length ← vtx.val.length+2;
RETURN [vtx];
};
AdjustTexture: PROC[poly: REF Patch] ~ {
maxXtxtr, maxYtxtr, minXtxtr, minYtxtr: REAL ← 0.0;
FOR i: CARDINAL IN [0..poly.nVtces) DO  -- find maximum
txtr: REF Triple ← NARROW[poly[i].aux];
IF maxXtxtr < txtr.x THEN maxXtxtr ← txtr.x;
IF maxYtxtr < txtr.y THEN maxYtxtr ← txtr.y;
ENDLOOP;
FOR i: CARDINAL IN [0..poly.nVtces) DO  -- push small ones beyond maximum
txtr: REF Triple ← NARROW[poly[i].aux];
WHILE maxXtxtr - txtr.x > .5 DO txtr.x ← txtr.x + 1.0; ENDLOOP;
WHILE maxYtxtr - txtr.y > .5 DO txtr.y ← txtr.y + 1.0; ENDLOOP;
ENDLOOP;
minXtxtr ← maxXtxtr; minYtxtr ← maxYtxtr;
FOR i: CARDINAL IN [0..poly.nVtces) DO  -- find minimum
txtr: REF Triple ← NARROW[poly[i].aux];
IF minXtxtr > txtr.x THEN minXtxtr ← txtr.x;
IF minYtxtr > txtr.y THEN minYtxtr ← txtr.y;
ENDLOOP;
minXtxtr ← Real.Float[Real.FixI[minXtxtr]]; minYtxtr ← Real.Float[Real.FixI[minYtxtr]];
FOR i: CARDINAL IN [0..poly.nVtces) DO  -- adjust everything to minima under 1.0
txtr: REF Triple ← NARROW[poly[i].aux];
txtr.x ← txtr.x - minXtxtr;
txtr.y ← txtr.y - minYtxtr;
ENDLOOP;
};
keepYIncrements, shadingPerPixel, textureMapping: BOOLEAN ← FALSE;
spot: ScanConvert.Spot;
fancyPoly: REF FancyPatch ← NEW[ FancyPatch[poly.nVtces] ];
shininess: REF REAL;
Get custom procedures for storing and extracting spot values
ref: REF ← Atom.GetPropFromList[poly.props, $ShadingProcs];
IF ref # NIL
THEN [getVtxProc, getColorProc] ← NARROW[ ref, REF ThreeDScenes.ShadingProcs]^;
IF getColorProc # NIL
THEN shadingPerPixel ← TRUE     -- custom shading, must use raw surface color
ELSE getColorProc ← RecoverColor;    -- default shading
IF NOT context.alphaBuffer THEN SIGNAL TilersError[$NoAlphaBuffer];
Do we have a highlight?
shininess ← NARROW[Atom.GetPropFromList[poly.props, $Shininess], REF REAL];
IF shininess # NIL AND shininess^ > 0.0
THEN {
hilitInfo: REF HilitSeqs ← GotAHilite[context, poly, shininess^];
IF hilitInfo # NIL THEN {
spot.props ← Atom.PutPropOnList[spot.props, $HltPwr, shininess];
keepYIncrements ← TRUE; shadingPerPixel ← TRUE;
ReleaseHilitSeqs[hilitInfo];
};
};
Do we have mapped texture?
ref ← Atom.GetPropFromList[poly.props, $TextureMap];
IF ref # NIL THEN {
spot.props ← Atom.PutPropOnList[ spot.props, $TextureMap, ref ];
IF NARROW[ref, REF TextureMaps.TextureMap].type = $Bump THEN
IF NOT shadingPerPixel THEN {
IF shininess = NIL THEN shininess ← NEW[REAL ← 0.0];
spot.props ← Atom.PutPropOnList[spot.props, $HltPwr, shininess];
shadingPerPixel ← TRUE;  -- change shading mode for bump mapping
};
keepYIncrements ← TRUE;   
textureMapping ← TRUE;
AdjustTexture[poly];       -- fix texture seams
};
spot.proc ← getColorProc;           -- set up remaining spot fields
IF keepYIncrements
THEN spot.props ← Atom.PutPropOnList[ spot.props, $KeepYIncrements, $DoIt ];
spot.props ← Atom.PutPropOnList[spot.props, $Context, context]; -- pass context.
spot.props ← Atom.PutPropOnList[spot.props, $ShapeShadingProps, poly.props ]; -- pass props
FOR i: NAT IN [0..poly.nVtces) DO -- convert vertices to lerp
fancyPoly[i] ← LerpVtxFromVtx[poly[i], shadingPerPixel];
ENDLOOP;
IF textureMapping THEN {        -- add texture coordinates
FOR i: NAT IN [0..poly.nVtces) DO
fancyPoly[i] ← AddTextureCoords[ fancyPoly[i], poly[i] ];
ENDLOOP;
spot.props ← Atom.PutPropOnList[     -- store texture coord position marker
spot.props,
$MapVals,
NEW[ NAT ← fancyPoly[0].val.length - 2 ]
];
};
IF getVtxProc # NIL THEN FOR i: CARDINAL IN [0..poly.nVtces) DO -- for custom shading
fancyPoly[i].val ← getVtxProc[ dest: fancyPoly[i].val, source: poly[i] ];
ENDLOOP;
fancyPoly.spot ← spot;
RealFancyTiler[context, fancyPoly];   -- now go tile it
};
RealFancyTiler: PUBLIC PROC[context: REF ThreeDBasics.Context, poly: REF FancyPatch] ~ {
least, top, bottom: REAL;
lEdge, rEdge: EdgeBlock;
vtxCount, lVtx, rVtx, nxtlVtx, nxtrVtx, nVtcesMinusOne: NAT;
leftVtxNeeded, rightVtxNeeded: BOOLEAN;
least ← poly.vtx[0].y; nxtlVtx ← 0;
FOR i: CARDINAL IN [1..poly.length) DO -- find bottom vertex
IF poly.vtx[i].y < least
THEN { least ← poly[i].y; nxtlVtx ← i; };
ENDLOOP;
nxtrVtx ← nxtlVtx; -- set pointers to bottom vertex
leftVtxNeeded ← rightVtxNeeded ← TRUE;
nVtcesMinusOne ← poly.length - 1;
vtxCount ← 1;
WHILE vtxCount < poly.length DO -- Do until all vertices reached
IF leftVtxNeeded THEN { -- work around left side
lVtx ← nxtlVtx; nxtlVtx ← (nxtlVtx + 1) MOD poly.length;
lEdge ← MakeEdge[poly[lVtx], poly[nxtlVtx]];
leftVtxNeeded ← FALSE;
};
IF rightVtxNeeded THEN { -- work around right side
rVtx ← nxtrVtx; nxtrVtx ← (nxtrVtx + nVtcesMinusOne) MOD poly.length;
rEdge ← MakeEdge[poly[rVtx], poly[nxtrVtx]];
rightVtxNeeded ← FALSE;
};
get trapezoid given by next higher vertex
IF poly[nxtlVtx].y < poly[nxtrVtx].y THEN {
top ← poly[nxtlVtx].y; -- next left vertex reached
leftVtxNeeded ← TRUE; vtxCount ← vtxCount + 1;
}
ELSE {
top ← poly[nxtrVtx].y; -- next right vertex reached
rightVtxNeeded ← TRUE; vtxCount ← vtxCount + 1;
};
bottom ← MAX[poly[lVtx].y, poly[rVtx].y];
ShowFancyTrap[ context, poly, bottom, top, lEdge, rEdge
     ! TilersError => IF reason = $DeepRecursionInTiler THEN CONTINUE];
ENDLOOP;
};
MakeEdge: PROC[vtx1, vtx2: LerpVtx] RETURNS[edge: EdgeBlock] ~ {
length: REAL;
edge.val ← NEW[ RealSequence[vtx1.val.length] ];
edge.incr ← NEW[ RealSequence[vtx1.val.length] ];
IF ABS[vtx2.y - vtx1.y] >= ABS[vtx2.x - vtx1.x]
THEN {
length ← vtx2.y - vtx1.y;
edge.start ← MIN[vtx1.y, vtx2.y];
edge.end ← MAX[vtx1.y, vtx2.y];
edge.moreVertical ← TRUE;
}
ELSE {
length ← vtx2.x - vtx1.x;
edge.start ← MIN[vtx1.x, vtx2.x];
edge.end ← MAX[vtx1.x, vtx2.x];
edge.moreVertical ← FALSE;
};
IF ABS[length] < justNoticeable THEN length ← 1.;        -- prevent divide errors
edge.x ← vtx1.x;  edge.xIncr ← (vtx2.x - vtx1.x) / length;
edge.y ← vtx1.y;  edge.yIncr ← (vtx2.y - vtx1.y) / length;
FOR i: NAT IN [0..vtx1.val.length) DO
edge.val[i] ← vtx1.val[i];  edge.incr[i] ← (vtx2.val[i] - vtx1.val[i]) / length;
ENDLOOP;
edge.val.length ← edge.incr.length ← vtx1.val.length;
RETURN[edge];
};
EvalEdgeAt: PROC[vtx: LerpVtx, edge: EdgeBlock, position: REAL] RETURNS[LerpVtx] ~ {
pos, dist: REAL;
IF vtx.val = NIL OR vtx.val.maxLength < edge.val.length
THEN vtx.val ← NEW[ RealSequence[edge.val.length] ];
IF position > edge.end THEN pos ← edge.end    -- keep values between vertex values
ELSE IF position < edge.start THEN pos ← edge.start
ELSE pos ← position;
dist ← IF edge.moreVertical THEN pos - edge.y ELSE pos - edge.x;
vtx.x ← edge.x + edge.xIncr * dist;
vtx.y ← edge.y + edge.yIncr * dist;
FOR i: NAT IN [0..edge.val.length) DO
vtx.val[i] ← edge.val[i] + edge.incr[i] * dist;
ENDLOOP;
vtx.val.length ← edge.val.length;
RETURN[vtx];
};
EvalCvrgeAt: PROC[ start, end, position: REAL]
     RETURNS[ cvrge: REAL, mask: CARDINAL] ~ {
Get Pixel area coverage weighted by function stored in "weight"
rCoverage, rUnCoverage: REAL;
lCoverage: REAL ← position - start;
IF lCoverage >= 1. THEN lCoverage ← 2.0   -- fully covered
ELSE IF lCoverage > -1.0 THEN lCoverage ← 1.0 + lCoverage  -- partially covered
ELSE lCoverage ← 0.;
lCoverage ← weight[Real.FixI[ tblLngth/2 * lCoverage ]];
rCoverage ← end - position;
IF rCoverage >= 1. THEN rCoverage ← 2.0   -- fully covered
ELSE IF rCoverage > -1.0 THEN rCoverage ← 1.0 + rCoverage -- partially covered
ELSE rCoverage ← 0.;
rUnCoverage ← weight[Real.FixI[ tblLngth/2 * (2.0 - rCoverage) ]]; -- weight uncovered part
cvrge ← lCoverage - rUnCoverage; -- l - r is total coverage
mask ← 0;        -- not yet implemented
};
MakeScanSeg: PROC[seg: REF ScanSegment, lEdge, rEdge: EdgeBlock, position: REAL,
       increments: BOOLEAN] RETURNS[REF ScanSegment] ~ {
length, lCvrge, rCvrge: REAL;
lVtx: REF LerpVtx ← GetVertex[lEdge.val.length];
rVtx: REF LerpVtx ← GetVertex[lEdge.val.length];
lVtx^ ← EvalEdgeAt[lVtx^, lEdge, position];
rVtx^ ← EvalEdgeAt[rVtx^, rEdge, position];
IF lEdge.moreVertical -- horizontal scan segment
THEN {
length ← rVtx.x - lVtx.x;
seg.start ← lVtx.x; seg.end ← rVtx.x;
}
ELSE {      -- vertical scan segment
length ← rVtx.y - lVtx.y;
seg.start ← lVtx.y; seg.end ← rVtx.y;
};
IF ABS[length] > justNoticeable THEN { -- long enough to show up
[lCvrge, seg.lMask] ← EvalCvrgeAt[lEdge.start, lEdge.end, position];
[rCvrge, seg.rMask] ← EvalCvrgeAt[rEdge.start, rEdge.end, position];
seg.coverage ← lCvrge;  
seg.cvrgIncr ← (rCvrge - lCvrge) / length;
FOR i: NAT IN [0..lEdge.val.length) DO
seg.val[i] ← lVtx.val[i];  
seg.xIncrVal[i] ← (rVtx.val[i] - lVtx.val[i]) / length;    -- x-increments
ENDLOOP;
seg.val.length ← seg.xIncrVal.length ← lEdge.val.length;
IF increments THEN {
FOR i: NAT IN [0..lEdge.val.length) DO
seg.yIncr[i] ← lEdge.incr[i];          -- y—increments
seg.xIncrForY[i] ← (rEdge.incr[i] - lEdge.incr[i]) / length; -- x-incrs for y—incrs
ENDLOOP;
seg.yIncr.length ← seg.xIncrForY.length ← lEdge.val.length;
};
IF seg.val[0] < 0.0 THEN SIGNAL TilersError[$NegativeColor];
};
ReleaseVertex[lVtx]; ReleaseVertex[rVtx];
RETURN[seg];
};
EvalScanSegAt: PROC[spot: ScanConvert.Spot, seg: REF ScanSegment, position: REAL]
      RETURNS[REAL, ScanConvert.Spot] ~ {
pos, dist, coverage: REAL;
mask: CARDINAL;
IF spot.val = NIL OR spot.val.maxLength < seg.val.length THEN {
spot.val ← NEW[ RealSequence[seg.val.length] ];
spot.yIncr ← NEW[ RealSequence[seg.val.length] ];
spot.xIncr ← NEW[ RealSequence[seg.val.length] ];
};
IF position > seg.end THEN pos ← seg.end    -- keep values between vertex values
ELSE IF position < seg.start THEN pos ← seg.start
ELSE pos ← position;
dist ← pos - seg.start;
FOR i: NAT IN [0..seg.val.length) DO    -- load up spot values
spot.val[i] ← seg.val[i] + seg.xIncrVal[i] * dist;
spot.yIncr[i] ← seg.yIncr[i] + seg.xIncrForY[i] * dist;
ENDLOOP;
spot.xIncr ← seg.xIncrVal;            -- use x increments as is
spot.val.length ← spot.yIncr.length ← spot.xIncr.length ← seg.val.length;
[coverage, mask] ← EvalCvrgeAt[seg.start, seg.end, position];
coverage ← coverage * (seg.coverage + seg.cvrgIncr * dist);
RETURN[coverage, spot];
};
ShowFancyTrap: PROC[ context: REF ThreeDBasics.Context, inPoly: REF FancyPatch,
        bottom, top: REAL, lEdge, rEdge: EdgeBlock] ~ {
GetXcoordAt: PROC[edge: EdgeBlock, yPos: REAL] RETURNS [REAL] ~ {
dist: REAL ← yPos - edge.y;
RETURN [ edge.x + dist / edge.yIncr ];
};
spot: ScanConvert.Spot ← inPoly.spot;
tEdge, bEdge, midlEdge, midrEdge: EdgeBlock;
leftTopVtx, leftBotVtx, rightTopVtx, rightBotVtx, vtx0, vtx1, vtx2, vtx3, vertex: LerpVtx;
sideways, midSection: BOOLEAN ← TRUE;
toughCase: BOOLEAN ← FALSE;
a, b: REAL;        -- parameters for defining 45 degree lines
IF bottom + justNoticeable >= top THEN RETURN[]; -- too thin to affect image
midlEdge ← DupEdgeBlock[lEdge];  -- copy sides for possible later use
midrEdge ← DupEdgeBlock[rEdge];
FOR i: NAT IN [0..midlEdge.val.length) DO
midlEdge.val[i] ← lEdge.val[i]; midlEdge.incr[i] ← lEdge.incr[i];
midrEdge.val[i] ← rEdge.val[i]; midrEdge.incr[i] ← rEdge.incr[i];
ENDLOOP;
IF NOT (lEdge.moreVertical AND rEdge.moreVertical) THEN { -- get corners
IF lEdge.moreVertical THEN {
leftTopVtx ← EvalEdgeAt[leftTopVtx, lEdge, top];
leftBotVtx ← EvalEdgeAt[leftBotVtx, lEdge, bottom];
}
ELSE {
topX: REAL ← GetXcoordAt[lEdge, top];
botX: REAL ← GetXcoordAt[lEdge, bottom];
leftTopVtx ← EvalEdgeAt[leftTopVtx, lEdge, topX];
leftBotVtx ← EvalEdgeAt[leftBotVtx, lEdge, botX];
};
IF rEdge.moreVertical THEN {
rightTopVtx ← EvalEdgeAt[rightTopVtx, rEdge, top];
rightBotVtx ← EvalEdgeAt[rightBotVtx, rEdge, bottom];
}
ELSE {
topX: REAL ← GetXcoordAt[rEdge, top];
botX: REAL ← GetXcoordAt[rEdge, bottom];
rightTopVtx ← EvalEdgeAt[rightTopVtx, rEdge, topX];
rightBotVtx ← EvalEdgeAt[rightBotVtx, rEdge, botX];
};
IF rightTopVtx.x + justNoticeable < leftTopVtx.x OR rightBotVtx.x + justNoticeable < leftBotVtx.x
THEN RETURN[]; -- twisted or backfacing
};

if left side more horizontal, check for slope, make top or bottom edge,
do right triangle, do new left edge
IF NOT lEdge.moreVertical THEN IF lEdge.yIncr < 0.
THEN {         -- left edge is more horizontal, top vertex is leftmost
tEdge ← MakeEdge[leftTopVtx, rightTopVtx]; bEdge ← DupEdgeBlock[lEdge];
IF leftBotVtx.x <= rightTopVtx.x
THEN {       -- easy case: right triangle containing whole left edge
ShowSteepTrap[context, spot,
     leftTopVtx.x, leftBotVtx.x, bEdge, tEdge, sideways];
midlEdge ← MakeEdge[leftBotVtx, EvalEdgeAt[vertex, tEdge, leftBotVtx.x]];
}
ELSE {        -- right top is left of left bottom
IF rEdge.moreVertical THEN {  -- difficult case bot. more horz. top more vert.
toughCase ← TRUE;
ShowSteepTrap[context, spot,
     leftTopVtx.x, rightTopVtx.x, bEdge, tEdge, sideways];
vtx0 ← EvalEdgeAt[vtx0, bEdge, rightTopVtx.x];  --build new polygon
vtx1 ← EvalEdgeAt[vtx1, rEdge, rightTopVtx.y];
vtx2 ← EvalEdgeAt[vtx2, rEdge, rightBotVtx.y];
vtx3 ← EvalEdgeAt[vtx3, bEdge, leftBotVtx.x];
a ← .707; b ← .707;       -- test against negative 45 degree slope
}
ELSE {        -- both more horz. do triangle then trapezoid
ShowSteepTrap[context, spot,
     leftTopVtx.x, rightTopVtx.x, bEdge, tEdge, sideways];
ShowSteepTrap[context, spot,
     rightTopVtx.x, leftBotVtx.x, bEdge, rEdge, sideways];
midSection ← FALSE;
};
};
}
ELSE {     -- left edge is more horizontal, bottom vertex is leftmost
bEdge ← MakeEdge[leftBotVtx, rightBotVtx]; tEdge ← DupEdgeBlock[lEdge];
IF leftTopVtx.x <= rightBotVtx.x
THEN {      -- easy case: right triangle containing whole left edge
ShowSteepTrap[context, spot,
     leftBotVtx.x, leftTopVtx.x, bEdge, tEdge, sideways];
midlEdge ← MakeEdge[leftTopVtx, EvalEdgeAt[vertex, bEdge, leftTopVtx.x]];
}
ELSE {      -- right bottom is left of left top
IF rEdge.moreVertical THEN {  -- difficult case bot. more vert. top more horz.
toughCase ← TRUE;
ShowSteepTrap[context, spot,
     leftBotVtx.x, rightBotVtx.x, bEdge, tEdge, sideways];
vtx0 ← EvalEdgeAt[vtx0, rEdge, rightBotVtx.y];  --build new polygon
vtx1 ← EvalEdgeAt[vtx1, tEdge, rightBotVtx.x];
vtx2 ← EvalEdgeAt[vtx2, tEdge, leftTopVtx.x];
vtx3 ← EvalEdgeAt[vtx3, rEdge, rightTopVtx.y];
a ← -.707; b ← .707;       -- test against positive 45 degree slope
}
ELSE {        -- both more horz. do triangle then trapezoid
ShowSteepTrap[context, spot,
     leftBotVtx.x, rightBotVtx.x, bEdge, tEdge, sideways];
ShowSteepTrap[context, spot,
     rightBotVtx.x, leftTopVtx.x, rEdge, tEdge, sideways];
midSection ← FALSE;
};
};
};
if right side more horizontal do likewise
IF NOT rEdge.moreVertical THEN IF rEdge.yIncr < 0.
THEN {        -- right edge is more horizontal, top vertex is leftmost
bEdge ← MakeEdge[leftBotVtx, rightBotVtx]; tEdge ← DupEdgeBlock[rEdge];
IF leftBotVtx.x <= rightTopVtx.x
THEN {       -- easy case: right triangle containing whole right edge
ShowSteepTrap[context, spot,
     rightTopVtx.x, rightBotVtx.x, bEdge, tEdge, sideways];
midrEdge ← MakeEdge[EvalEdgeAt[vertex, bEdge, rightTopVtx.x], rightTopVtx];
}
ELSE {       -- left bottom is right of right top
IF lEdge.moreVertical THEN {  -- difficult case bot. more vert. top more horz.
toughCase ← TRUE;
vtx0 ← EvalEdgeAt[vtx0, lEdge, rightTopVtx.y];  --build new polygon
vtx1 ← EvalEdgeAt[vtx1, tEdge, rightTopVtx.x];
vtx2 ← EvalEdgeAt[vtx2, tEdge, leftBotVtx.x];
vtx3 ← EvalEdgeAt[vtx3, lEdge, leftBotVtx.y];
a ← .707; b ← .707;       -- test against negative 45 degree slope
};
get triangle at right, if both horz. then left edge got middle trapezoid
ShowSteepTrap[context, spot,
     leftBotVtx.x, rightBotVtx.x, bEdge, tEdge, sideways];
};
}
ELSE {        -- right edge is more horizontal, bottom vertex is leftmost
tEdge ← MakeEdge[leftTopVtx, rightTopVtx]; bEdge ← DupEdgeBlock[rEdge];
IF leftTopVtx.x <= rightBotVtx.x
THEN {      -- easy case: right triangle containing whole right edge
ShowSteepTrap[context, spot,
     rightBotVtx.x, rightTopVtx.x, bEdge, tEdge, sideways];
midrEdge ← MakeEdge[rightBotVtx, EvalEdgeAt[vertex, tEdge, rightBotVtx.x]];
}
ELSE {       -- left top is right of right bottom
IF lEdge.moreVertical THEN {  -- difficult case bot. more vert. top more horz.
toughCase ← TRUE;
vtx0 ← EvalEdgeAt[vtx0, bEdge, rightBotVtx.x];  --build new polygon
vtx1 ← EvalEdgeAt[vtx1, lEdge, rightBotVtx.y];
vtx2 ← EvalEdgeAt[vtx2, lEdge, leftTopVtx.y];
vtx3 ← EvalEdgeAt[vtx3, bEdge, leftTopVtx.x];
a ← -.707; b ← .707;       -- test against positive 45 degree slope
};
get triangle at right, if both horz. then left edge got middle trapezoid
ShowSteepTrap[context, spot,
     leftTopVtx.x, rightTopVtx.x, bEdge, tEdge, sideways];
};
};
Do middle section
IF toughCase THEN { -- quadrilateral with top and bottom slopes on both sides of 45 deg.
c, d1, d2, d3: REAL; -- evaluate area based on distance of vertices from 45 degree line
c ← -(a * vtx0.x + b * vtx0.y); -- equation for line through vtx0
d1 ← a * vtx1.x + b * vtx1.y + c;   -- distances of other vertices from line
d2 ← a * vtx2.x + b * vtx2.y + c;
d3 ← a * vtx3.x + b * vtx3.y + c;
IF (top - bottom) * ( MAX[d1, d2, d3, 0.0] - MIN[d1, d2, d3, 0.0] ) / 2.0 < justNoticeable
THEN RETURN[]         -- estimated area too small to matter
ELSE {
poly: REF FancyPatch ← NEW[FancyPatch[4]];
poly.vtx[0] ← DupLerpVtx[vtx0]; poly.vtx[1] ← DupLerpVtx[vtx1];
poly.vtx[2] ← DupLerpVtx[vtx2]; poly.vtx[3] ← DupLerpVtx[vtx3];
poly.spot ← spot;
poly.recurseLevel ← inPoly.recurseLevel + 1;
IF poly.recurseLevel > recurseLimit THEN SIGNAL TilersError[$DeepRecursionInTiler];
RealFancyTiler[context, poly]; -- go draw it (recursively)
};
}
ELSE IF midSection THEN ShowSteepTrap[context, spot, bottom, top, midlEdge, midrEdge];
};
ShowSteepTrap: PROC[ context: REF ThreeDBasics.Context, spot: ScanConvert.Spot,
       bottom, top: REAL, lEdge, rEdge: EdgeBlock,
        sideways: BOOLEAN ← FALSE ] ~ {
Swap: PROC[ref1, ref2: REF RealSequence] RETURNS [outRef1, outRef2: REF RealSequence] ~{
RETURN[ outRef1: ref2, outRef2: ref1 ];
};
shadingType: REF ANY ← Atom.GetPropFromList[
NARROW[ Atom.GetPropFromList[spot.props, $ShapeShadingProps], Atom.PropList ],
$Type
];
scanSeg: REF ScanSegment ← GetScanSeg[lEdge.val.length];
writeOp: ATOM ← IF shadingType = $Lines THEN $WriteLineUnder ELSE $WriteUnder;
lStartSave: REAL ← lEdge.start;  lEndSave: REAL ← lEdge.end; -- save limits to restore later
rStartSave: REAL ← rEdge.start; rEndSave: REAL ← rEdge.end;
yLimit: INTEGER ← IF sideways THEN Ceiling[context.viewPort.w]
          ELSE Ceiling[context.viewPort.h];
xLimit: INTEGER ← IF sideways THEN Ceiling[context.viewPort.h]
          ELSE Ceiling[context.viewPort.w];
yIncrements: BOOLEAN ← FALSE;
IF context.stopMe THEN RETURN;
IF bottom + justNoticeable >= top THEN RETURN[]; -- too vertically thin to affect image
IF Atom.GetPropFromList[spot.props, $KeepYIncrements] = $DoIt THEN yIncrements ←TRUE;
lEdge.start ← rEdge.start ← bottom; -- set edge limits for coverage calcs.
lEdge.end ← rEdge.end ← top;
FOR y: INTEGER IN [Floor[bottom]..Ceiling[top]] DO
IF context.stopMe THEN RETURN;
IF y < 0 OR y >= yLimit THEN LOOP;  -- scissor off if out-of-bounds
scanSeg ← MakeScanSeg[scanSeg, lEdge, rEdge, Real.Float[y], yIncrements];
IF scanSeg.end - scanSeg.start > justNoticeable THEN { -- if wide enough to affect image
FOR x: INTEGER IN [Floor[scanSeg.start]..Ceiling[scanSeg.end]] DO
IF x < 0 OR x >= xLimit THEN LOOP;  -- scissor off if out-of-bounds
[spot.coverage, spot] ← EvalScanSegAt[ spot, scanSeg, Real.Float[x] ];
IF sideways
THEN { [spot.yIncr, spot.xIncr] ← Swap[spot.xIncr, spot.yIncr]; -- switch x and y
   spot.x ← y;  spot.y ← x; }
ELSE { spot.x ← x;  spot.y ← y; };
ScanConvert.PutSpot[ context.display, spot, writeOp, context.renderMode ];
IF sideways THEN [spot.yIncr, spot.xIncr] ← Swap[spot.xIncr, spot.yIncr]; -- put back
ENDLOOP;
};
ENDLOOP;
lEdge.start ← lStartSave; lEdge.end ← lEndSave; -- restore limits
rEdge.start ← rStartSave; rEdge.end ← rEndSave;
ReleaseScanSeg[scanSeg];
};
Init[];
END.