DIRECTORY
Real					USING [LargestNumber, FixI, RoundC, Float],
RealFns				USING [SqRt, CosDeg, SinDeg, TanDeg],
Basics					USING [BITOR, BITAND],
Rope					USING [ROPE],
FS						USING [StreamOpen],
IO						USING [STREAM, GetChar, GetInt, GetReal],
ThreeDPackage		USING [Triple, SumTriple, Normalize, DotProd, CrossProd, 
								 Transform3D, TransformVec3D, GetIDTransform, ConcatT],
PolygonPackage;

PolygonPackageImpl: CEDAR PROGRAM
IMPORTS Real, RealFns, FS, IO, Basics, ThreeDPackage
EXPORTS PolygonPackage 

= BEGIN OPEN PolygonPackage, ThreeDPackage;

ShadingUnspecified, BadColorLength, BadTextureLength: PUBLIC SIGNAL = CODE;

ClipLimit: TYPE =  {left, right, bottom, top, near, far};
depthResolution: NAT = 8192;
buckets: REF SortSequenceRep _ NIL;
cotanField, sinField, cosField, aspectRatio, resFctrX, resFctrY: REAL;
hitherLimit: REAL;
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.];   
};
DiffPosns: PROC[vtx1, vtx2: Vertex] RETURNS[Triple] ~ {
RETURN[[vtx1.x - vtx2.x, vtx1.y - vtx2.y, vtx1.z - vtx2.z]] };

GetTransforms: PUBLIC PROC[ eyePt, ptOfInterest: Triple, width, height: NAT, 
								   fieldOfView: REAL _ 40., nearLimit: REAL _ .01 ] 
					RETURNS[eyeSpace: Transformation3D] ~{
pt1, pt2: Triple;
mtx: Transformation3D;
hypotenuse, cosA, sinA: REAL;
resFctrX _ (width - 1) / 2.;    resFctrY _ (height - 1) / 2.;    
aspectRatio _ Real.Float[width] / height;
eyeSpace _ GetIDTransform[];		-- Translate eyepoint to origin
eyeSpace.d.x _ -eyePt.x;    eyeSpace.d.y _ -eyePt.y;    eyeSpace.d.z _ -eyePt.z;
pt1 _ Transform3D[ptOfInterest, eyeSpace];
mtx _ GetIDTransform[];								-- Rotate ptOfInterest about Z into YZ plane
hypotenuse _ RealFns.SqRt[pt1.x * pt1.x + pt1.y * pt1.y];
IF hypotenuse # 0. THEN {
cosA _ pt1.y / hypotenuse;		sinA _ pt1.x / hypotenuse; 
mtx.a.x _  cosA;		mtx.a.y _ sinA; 
mtx.b.x _ -sinA;		mtx.b.y _ cosA;
eyeSpace _ ConcatT[eyeSpace, mtx];
};
pt2 _ Transform3D[ptOfInterest, eyeSpace];
mtx _ GetIDTransform[];								-- Rotate ptOfInterest about X into Y axis
hypotenuse _ RealFns.SqRt[pt2.y * pt2.y + pt2.z * pt2.z]; 
IF hypotenuse # 0. THEN {
cosA _ pt2.y / hypotenuse;		sinA _ -pt2.z / hypotenuse; 
mtx.b.y _  cosA;		mtx.b.z _ sinA; 
mtx.c.y _ -sinA;		mtx.c.z _ cosA;
eyeSpace _ ConcatT[eyeSpace, mtx];
}; 
mtx _ GetIDTransform[];								-- Interchange y and z axes
mtx.b.y _  0.;		mtx.b.z _ 1.; 
mtx.c.y _ 1.;			mtx.c.z _ 0.;
eyeSpace _ ConcatT[eyeSpace, mtx];
mtx _ GetIDTransform[];								-- Scale to 90 degree field of view
sinField _ RealFns.SinDeg[fieldOfView/2.];
cosField _ RealFns.CosDeg[fieldOfView/2.];
cotanField _ 1. / RealFns.TanDeg[fieldOfView/2.];
mtx.a.x _  cotanField;
mtx.b.y _ aspectRatio * cotanField;							-- aspect ratio on display
eyeSpace _ ConcatT[eyeSpace, mtx];
hitherLimit _ nearLimit;								-- store hither clipping plane
};

BackFacing: PUBLIC PROC[ poly: REF Polygon] RETURNS [BOOLEAN] ~ {
this: VertexInfo _ poly.vtx[0];
next: VertexInfo _ poly.vtx[1];
last:  VertexInfo _ poly.vtx[poly.nVtces - 1]; 
direction: Triple _ Normalize[CrossProd[
[next.coord.ex - this.coord.ex, next.coord.ey - this.coord.ey, next.coord.ez - this.coord.ez], 
[last.coord.ex - this.coord.ex,  last.coord.ey - this.coord.ey,  last.coord.ez - this.coord.ez] ] ];
RETURN[ DotProd[ [this.coord.ex, this.coord.ey, this.coord.ez] , direction] > 0. ];
};

ShadePoly: PUBLIC PROC[ poly: REF Polygon, light: LightList] RETURNS [REF Polygon] ~ {
colorSequenceRep: TYPE ~ RECORD[SEQUENCE length: NAT OF RECORD [r, g, b: REAL]];
clr: REF colorSequenceRep _ NEW[ colorSequenceRep[poly.nVtces] ];
FOR i: NAT IN [0..poly.nVtces) DO  clr[i].r _ clr[i].g _ clr[i].b _ 0.;  ENDLOOP;
WHILE light # NIL DO
FOR i: NAT IN [0..poly.nVtces) DO		-- Run through the vertices for each light
OPEN poly.vtx[i].coord;
next: Vertex _ poly.vtx[ (i + 1) MOD poly.nVtces ].coord;    
last: Vertex _ poly.vtx[ (i + poly.nVtces - 1) MOD poly.nVtces ].coord;
normal: Triple _ Normalize[CrossProd[
					[next.x - x, next.y - y, next.z - z], [last.x - x, last.y - y, last.z - z] ]];
value: REAL _ RealFns.SqRt[DotProd[Normalize[light.first.pos], normal]];
IF value < 0. THEN value _ 0.;
value _ light.first.ambient + (1. - light.first.ambient) * value;	-- Add ambient light
clr[i].r _ clr[i].r  + value * poly.vtx[i].shade.r;
clr[i].g _ clr[i].g + value * poly.vtx[i].shade.g;
clr[i].b _ clr[i].b + value * poly.vtx[i].shade.b;
ENDLOOP;
light _ light.rest;
ENDLOOP;
FOR i: NAT IN [0..poly.nVtces) DO		-- Check limits and store with vertices
poly.vtx[i].shade.r _ IF clr[i].r > 1. THEN 1. ELSE clr[i].r;
poly.vtx[i].shade.g _ IF clr[i].g > 1. THEN 1. ELSE clr[i].g;
poly.vtx[i].shade.b _ IF clr[i].b > 1. THEN 1. ELSE clr[i].b;
ENDLOOP;
RETURN [ poly ];
};
ClipPoly: PUBLIC PROC[ poly, poly2: REF Polygon, shading, normals: BOOLEAN] 
					RETURNS [REF Polygon, REF Polygon] ~ {
Clip: PROC[side: ClipLimit, pIn, pOut: REF Polygon] RETURNS [REF Polygon, REF Polygon] = {
Dist: PROC[side: ClipLimit, vtx: Vertex] RETURNS [REAL] = INLINE {
maxDst: REAL = Real.LargestNumber;
SELECT side FROM
left	=> RETURN[vtx.ez + vtx.ex];
right	=> RETURN[vtx.ez - vtx.ex];
bottom => RETURN[vtx.ez + vtx.ey];
top	=> RETURN[vtx.ez - vtx.ey];
near	=> RETURN[vtx.ez];
far	=> RETURN[maxDst - vtx.ez];
ENDCASE => ERROR;
};	--end Dist Proc
lastDist, dist: REAL;    outCnt, last: NAT;
IF pIn.nVtces < 3 THEN RETURN[ pIn, pOut ];	-- return if degenerate
last _ pIn.nVtces - 1;
outCnt _ 0;
lastDist _ Dist[side, pIn.vtx[last].coord];
IF pOut.length < 2 * pIn.nVtces THEN pOut _ NEW[Polygon[2 * pIn.nVtces]];
FOR i: NAT IN [0..pIn.nVtces) DO
a, b: REAL;
dist _ Dist[side, pIn.vtx[i].coord];
IF lastDist * dist < 0. THEN {			-- put out point if clip plane crossed
b _ dist / (dist - lastDist);    a _ 1.0 - b;
pOut.vtx[outCnt].coord.ex _ pIn.vtx[i].coord.ex * a + pIn.vtx[last].coord.ex * b;
pOut.vtx[outCnt].coord.ey _ pIn.vtx[i].coord.ey * a + pIn.vtx[last].coord.ey * b;
pOut.vtx[outCnt].coord.ez _ pIn.vtx[i].coord.ez * a + pIn.vtx[last].coord.ez * b;
IF normals THEN {
pOut.vtx[outCnt].shade.xn _ pIn.vtx[i].shade.xn * a + pIn.vtx[last].shade.xn * b;
pOut.vtx[outCnt].shade.yn _ pIn.vtx[i].shade.yn * a + pIn.vtx[last].shade.yn * b;
pOut.vtx[outCnt].shade.zn _ pIn.vtx[i].shade.zn * a + pIn.vtx[last].shade.zn * b;
};
IF shading THEN {
pOut.vtx[outCnt].shade.r _ pIn.vtx[i].shade.r * a + pIn.vtx[last].shade.r * b;
pOut.vtx[outCnt].shade.g _ pIn.vtx[i].shade.g * a + pIn.vtx[last].shade.g * b;
pOut.vtx[outCnt].shade.b _ pIn.vtx[i].shade.b * a + pIn.vtx[last].shade.b * b;
pOut.vtx[outCnt].shade.t _ pIn.vtx[i].shade.t * a + pIn.vtx[last].shade.t * b;
pOut.vtx[outCnt].shade.txtrX _ 
								pIn.vtx[i].shade.txtrX * a + pIn.vtx[last].shade.txtrX * b;
pOut.vtx[outCnt].shade.txtrY _ 
								pIn.vtx[i].shade.txtrY * a + pIn.vtx[last].shade.txtrY * b;
};
outCnt _ outCnt + 1;
};
IF dist >= 0. THEN {						-- put out point if inside
pOut.vtx[outCnt].coord.ex _ pIn.vtx[i].coord.ex;
pOut.vtx[outCnt].coord.ey _ pIn.vtx[i].coord.ey;
pOut.vtx[outCnt].coord.ez _ pIn.vtx[i].coord.ez;
IF normals THEN {
pOut.vtx[outCnt].shade.xn _ pIn.vtx[i].shade.xn;
pOut.vtx[outCnt].shade.yn _ pIn.vtx[i].shade.yn;
pOut.vtx[outCnt].shade.zn _ pIn.vtx[i].shade.zn;
};
IF shading THEN {
pOut.vtx[outCnt].shade.r _ pIn.vtx[i].shade.r;
pOut.vtx[outCnt].shade.g _ pIn.vtx[i].shade.g;
pOut.vtx[outCnt].shade.b _ pIn.vtx[i].shade.b;
pOut.vtx[outCnt].shade.t _ pIn.vtx[i].shade.t;
pOut.vtx[outCnt].shade.txtrX _ pIn.vtx[i].shade.txtrX;
pOut.vtx[outCnt].shade.txtrY _ pIn.vtx[i].shade.txtrY;
};
outCnt _ outCnt + 1;
};
lastDist _ dist;    last _ i;
ENDLOOP;
pOut.nVtces _ outCnt;
RETURN [ pOut, pIn ];
};	-- end Clip Proc
orOfCodes: OutCode _ NoneOut;
FOR i: NAT IN [0..poly.nVtces) DO 
orOfCodes _ LOOPHOLE[
Basics.BITOR[LOOPHOLE[orOfCodes], LOOPHOLE[poly.vtx[i].coord.clip]],
OutCode]; 
ENDLOOP;
IF orOfCodes.near    THEN [poly, poly2] _ Clip[  near, poly, poly2]; 
IF orOfCodes.far      THEN [poly, poly2] _ Clip[    far, poly, poly2]; 
IF orOfCodes.left     THEN [poly, poly2] _ Clip[    left, poly, poly2]; 
IF orOfCodes.right   THEN [poly, poly2] _ Clip[  right, poly, poly2]; 
IF orOfCodes.bottom THEN [poly, poly2] _ Clip[bottom, poly, poly2];
IF orOfCodes.top     THEN [poly, poly2] _ Clip[    top, poly, poly2];
RETURN[ poly, poly2 ];
};
GetObject: PUBLIC PROC[fileName: Rope.ROPE] RETURNS[REF Object] ~ {
object: REF Object _ NEW[Object];
min, max: Triple;
radius: REAL;
input: IO.STREAM _ FS.StreamOpen[fileName];
char: CHAR _ ' ;
[] _ IO.GetChar[input];											-- burn first char (sometimes a CR)
WHILE char # 15C DO char _ IO.GetChar[input];  ENDLOOP;		-- burn first input line
object.name _ fileName;
object.numVtces _ IO.GetInt[input];
object.numPolys _ IO.GetInt[input]; 
object.shading _ none;
object.color _ [1., 1., 1.];
object.shininess _ object.transmittance _ 0.;
object.position _ GetIDTransform[];
object.vertex _ NEW[ VertexSequenceRep[object.numVtces] ];
FOR i: INT IN [0..object.numVtces) DO 						-- Read Vertices
object.vertex[i].x _ IO.GetReal[input];
object.vertex[i].y _ IO.GetReal[input];
object.vertex[i].z _ IO.GetReal[input];
ENDLOOP;
object.polygon _ NEW[ PtrPolySequenceRep[object.numPolys] ]; 
FOR i: INT IN [0..object.numPolys) DO                      -- Read Polygons
nVtces: NAT _ IO.GetInt[input];
object.polygon[i] _ NEW[PtrPoly[nVtces]];
object.polygon[i].nVtces _ nVtces;
FOR j: NAT IN [0..nVtces) DO
object.polygon[i].vtxPtr[j] _ IO.GetInt[input] - 1;  	-- switch to counting from zero
ENDLOOP;
ENDLOOP;
min _ max _ [object.vertex[0].x, object.vertex[0].y, object.vertex[0].z];
FOR i: INT IN (0..object.numVtces) DO                       -- find centroid
IF object.vertex[i].x < min.x THEN min.x _ object.vertex[i].x 
							ELSE IF object.vertex[i].x > max.x THEN max.x _ object.vertex[i].x;
IF object.vertex[i].y < min.y THEN min.y _ object.vertex[i].y 
							ELSE IF object.vertex[i].y > max.y THEN max.y _ object.vertex[i].y;
IF object.vertex[i].z < min.z THEN min.z _ object.vertex[i].z 
							ELSE IF object.vertex[i].x > max.z THEN max.z _ object.vertex[i].z;
ENDLOOP;
object.centroid.x _ (min.x + max.x) / 2; 
object.centroid.y _ (min.y + max.y) / 2;  
object.centroid.z _ (min.z + max.z) / 2; 
object.boundingRadius _ 0.;
FOR i: INT IN [0..object.numVtces) DO                      -- find radius
radius _ RealFns.SqRt[ 
	  Sqr[object.vertex[i].x - object.centroid.x] 
+ Sqr[object.vertex[i].y - object.centroid.y]
+ Sqr[object.vertex[i].z - object.centroid.z] ];
IF radius > object.boundingRadius 
THEN object.boundingRadius _ radius;
ENDLOOP; 
RETURN[object];
};
GetColors: PUBLIC PROC[colorFile: Rope.ROPE, object: REF Object, numExpected: INT] ~ { 
input: IO.STREAM _ FS.StreamOpen[colorFile];
char: CHAR _ ' ; 
numColors: INT;
IF (object.shade = NIL) OR (object.shade.length # numExpected) THEN 
object.shade _ NEW[ShadingSequenceRep[numExpected]];
[] _ IO.GetChar[input];              -- in case file has leading CR
WHILE char # 15C DO char _ IO.GetChar[input];  ENDLOOP; -- burn 1st line
numColors _ IO.GetInt[input];
IF numColors # numExpected 
THEN SIGNAL BadColorLength[];
numColors _ MIN[numColors, numExpected];
FOR i: INT IN [0..numColors) DO
object.shade[i].r _ IO.GetReal[input];
object.shade[i].g _ IO.GetReal[input];
object.shade[i].b _ IO.GetReal[input];
ENDLOOP;
};
GetCoords: PUBLIC PROC[coordinateFile: Rope.ROPE, object: REF Object, numExpected: INT] ~ {
input: IO.STREAM _ FS.StreamOpen[coordinateFile];
char: CHAR _ ' ; 
numPolys: INT;
IF (object.texture = NIL) OR (object.texture.length # numExpected) THEN 
object.texture _ NEW[PolygonTextureSequenceRep[numExpected]];
[] _ IO.GetChar[input];              -- in case file has leading CR
WHILE char # 15C DO char _ IO.GetChar[input];  ENDLOOP; -- burn 1st line
numPolys _ IO.GetInt[input];
IF numPolys # numExpected 
THEN SIGNAL BadTextureLength[];
numPolys _ MIN[numPolys, numExpected];
FOR i: INT IN [0..numPolys) DO
nVtces: NAT _ IO.GetInt[input];
object.texture[i] _ NEW[PolygonTexture[nVtces]];
object.texture[i].nVtces _ nVtces;
FOR j: NAT IN [0..nVtces) DO
object.texture[i].vtx[j].txtrX _ IO.GetReal[input];
object.texture[i].vtx[j].txtrY _ IO.GetReal[input];
ENDLOOP;
ENDLOOP;
};

GetSolidColor: PUBLIC PROC[color: ClrTriple, object: REF Object, numExpected: INT] ~ {
IF (object.shade = NIL) OR (object.shade.length # numExpected) THEN 
object.shade _ NEW[ShadingSequenceRep[numExpected]]; 
FOR i: INT IN [0..numExpected) DO
OPEN object.shade[i];    r _ color.r;    g _ color.g;    b _ color.b;    ENDLOOP;
};
GetPolyNormals: PUBLIC PROC[object: REF Object] ~ { 
OPEN object;
IF (shade = NIL) OR (shade.length # numPolys) THEN {
shade _ NEW[ ShadingSequenceRep[numPolys] ]; 
shading _ faceted;
};
FOR i: INT IN [0..numPolys) DO OPEN polygon[i];
sumNmls: Triple _ [0., 0., 0.];
FOR cVtx: NAT IN [0..nVtces) DO 
lVtx: NAT _ (cVtx + nVtces - 1) MOD nVtces; 
nVtx: NAT _ (cVtx + 1) MOD nVtces; 
sumNmls _ SumTriple[sumNmls, CrossProd[
DiffPosns[ vertex[vtxPtr[lVtx]], vertex[vtxPtr[cVtx]] ],
DiffPosns[ vertex[vtxPtr[nVtx]], vertex[vtxPtr[cVtx]] ] 
]]; 
ENDLOOP;
sumNmls _ Normalize[sumNmls];
shade[i].xn _ sumNmls.x;
shade[i].yn _ sumNmls.y;
shade[i].zn _ sumNmls.z; 
ENDLOOP; 
};
GetVtxNormals: PUBLIC PROC[object: REF Object] ~ {
OPEN object;
IF  (shade = NIL) OR (shade.length # numVtces) THEN {
shade _ NEW[ ShadingSequenceRep[numVtces] ];
shading _ smooth;
};
FOR i: INT IN [0..numVtces) DO shade[i].xn _ shade[i].yn _ shade[i].zn _ 0.;  ENDLOOP; 
FOR i: INT IN [0..numPolys) DO OPEN polygon[i];
FOR cVtx: NAT IN [0..nVtces) DO 
lVtx: NAT _ (cVtx + nVtces - 1) MOD nVtces; 
nVtx: NAT _ (cVtx + 1) MOD nVtces;
{   OPEN shade[vtxPtr[cVtx]];
[[xn, yn, zn]] _ SumTriple[ [xn, yn, zn], CrossProd[
DiffPosns[ vertex[vtxPtr[lVtx]], vertex[vtxPtr[cVtx]] ], 
DiffPosns[ vertex[vtxPtr[nVtx]], vertex[vtxPtr[cVtx]] ]
]];
};
ENDLOOP;
ENDLOOP; 
FOR i: INT IN [0..numVtces) DO OPEN shade[i];
[[xn, yn, zn]] _ Normalize[ [xn, yn, zn] ];
ENDLOOP;
}; 
XfmVtces: PUBLIC PROC[object: REF Object, xfm: Transformation3D] RETURNS[ClipState] ~ { 
andOfCodes, orOfCodes: OutCode;
xfmCentroid: Triple _ Transform3D[object.centroid, xfm];
xDiff: REAL _ cotanField * cosField * object.boundingRadius; -- x offset equivalent to radius
yDiff: REAL _ xDiff * 4./3.;
zCheck: REAL _ xfmCentroid.z - (sinField * object.boundingRadius);    -- z adjusted by radius
IF ( xfmCentroid.z - object.boundingRadius > hitherLimit ) 
	AND (ABS[xfmCentroid.x + Sgn[xfmCentroid.x] * xDiff ] < zCheck) 
	AND (ABS[xfmCentroid.y + Sgn[xfmCentroid.y] * yDiff ] < zCheck)  
THEN object.clipState _ in														-- all in
ELSE IF ( xfmCentroid.z + object.boundingRadius < hitherLimit ) 
	OR ( Sgn[xfmCentroid.x] * (xfmCentroid.x - Sgn[xfmCentroid.x] * xDiff) > zCheck ) 
	OR ( Sgn[xfmCentroid.y] * (xfmCentroid.y - Sgn[xfmCentroid.y] * yDiff) > zCheck )  
THEN {  object.clipState _ out;    RETURN[ out ];  }						-- all out
ELSE object.clipState _ clipped;
object.eyeCntroid _ xfmCentroid;
object.eyeBndngRadius _ object.boundingRadius;		-- should take scaling xfm into account
orOfCodes _ NoneOut;    andOfCodes _ AllOut;
FOR i: INT IN [0..object.numVtces) DO OPEN object.vertex[i];
[ [ex, ey, ez] ] _ Transform3D[ [x, y, z] , xfm];    
ENDLOOP;
IF object.clipState = clipped THEN {
FOR i: INT IN [0..object.numVtces) DO OPEN object.vertex[i];    
clip.bottom _ ey < -ez;				clip.top   _ ey > ez;    
clip.left 	 _ ex < -ez;    	 		clip.right _ ex > ez;
clip.near 	 _ ez < hitherLimit;	clip.far    _ FALSE;
orOfCodes _ LOOPHOLE[
Basics.BITOR[LOOPHOLE[orOfCodes], LOOPHOLE[clip]],
OutCode];   
andOfCodes _ LOOPHOLE[
Basics.BITAND[LOOPHOLE[andOfCodes], LOOPHOLE[clip]],
OutCode];
IF clip = NoneOut THEN {
ix _  Real.RoundC[ resFctrX * (ex / ez + 1.) ];
iy _  Real.RoundC[ resFctrY * (ey / ez + 1.) ];
};
ENDLOOP;
IF        orOfCodes = NoneOut THEN object.clipState _ in
ELSE IF andOfCodes # NoneOut THEN object.clipState _ out;
}
ELSE IF object.clipState = in THEN FOR i: INT IN [0..object.numVtces) DO OPEN object.vertex[i];
ix _  Real.RoundC[ resFctrX * (ex / ez + 1.) ];
iy _  Real.RoundC[ resFctrY * (ey / ez + 1.) ];
clip _ NoneOut;
ENDLOOP;
object.vtcesInValid _ FALSE;
RETURN[ object.clipState ];
};
GetShades: PUBLIC PROC[object: REF Object, lights: LightList, Proc: RGBToPixelProc] ~ { 
FOR i: NAT IN [0..object.shade.length) DO OPEN object.shade[i];
red, grn, blu: REAL _ 0.;
lightsTemp: LightList _ lights;
WHILE lights # NIL DO
gray: REAL _ DotProd[lights.first.pos, TransformVec3D[ [xn, yn, zn], object.position] ];
IF gray < 0. THEN gray _ 0.;
gray _ lights.first.ambient + (1. - lights.first.ambient) * gray;	-- Add ambient light
red _  red + gray * r * lights.first.clr.r;
grn _ grn + gray * g * lights.first.clr.g;
blu _ blu + gray * b * lights.first.clr.b;
lights _ lights.rest;
ENDLOOP;
red _ MIN[red, 1.];    grn _ MIN[grn, 1.];   blu _ MIN[blu, 1.];   
SELECT object.shading FROM
faceted =>  value _  Proc[red, grn, blu];
smooth =>  value _  Proc[red, grn, blu];
fancy =>   value _  Proc[red, grn, blu];
ENDCASE => SIGNAL ShadingUnspecified[];
lights _ lightsTemp;
ENDLOOP;
object.shadingInValid _ FALSE;
};

LoadSortSequence: PUBLIC PROC[objects: LIST OF REF Object] RETURNS[REF SortSequenceRep] ~ {
polygonCount: INT _ 0;
bucketListPtr: NAT _ depthResolution;
minDepth, maxDepth: REAL _ objects.first.eyeCntroid.z;
zScale: REAL _ 1.;
objectsTemp: LIST OF REF Object _ objects;
WHILE objects # NIL DO		-- get minimum and maximum depth and polygon count
IF objects.first.clipState # out THEN {
polygonCount _ polygonCount + objects.first.numPolys;
IF objects.first.eyeCntroid.z - objects.first.eyeBndngRadius < minDepth
THEN minDepth _ objects.first.eyeCntroid.z - objects.first.eyeBndngRadius;
IF objects.first.eyeCntroid.z + objects.first.eyeBndngRadius > maxDepth
THEN maxDepth _ objects.first.eyeCntroid.z + objects.first.eyeBndngRadius;
};
objects _ objects.rest;
ENDLOOP;
IF (maxDepth - minDepth) > 0. THEN zScale _ (depthResolution - 1) / (maxDepth - minDepth);
IF (buckets = NIL ) OR (buckets.length < polygonCount + depthResolution)
THEN buckets _ NEW[SortSequenceRep[polygonCount + depthResolution]];
FOR i: NAT IN [0..depthResolution) DO buckets[i].object _ NIL;  buckets[i].next _ 0;  ENDLOOP;
objects _ objectsTemp;
WHILE objects # NIL DO      		-- Enter polygons (by z-centroid) in bucket lists
IF objects.first.clipState # out THEN FOR i: INT IN [0..objects.first.numPolys) DO 
OPEN objects.first.polygon[i];
zSum: REAL _ 0.;    iz: NAT;
IF objects.first.clipState = in THEN { 								-- unclipped, inside
FOR j: NAT IN [0..nVtces) DO zSum _ zSum + objects.first.vertex[vtxPtr[j]].ez; ENDLOOP; 
iz _ Real.FixI[zScale * ((zSum / nVtces) - minDepth)]; 
clipState _ in;
}
ELSE IF objects.first.clipState = clipped THEN {								-- clipped
orOfCodes: OutCode _ NoneOut;    andOfCodes: OutCode _ AllOut; 
FOR j: NAT IN [0..nVtces) DO
k: NAT _ vtxPtr[j];
zSum _ zSum + objects.first.vertex[k].ez;
orOfCodes _ LOOPHOLE[
Basics.BITOR[LOOPHOLE[orOfCodes], LOOPHOLE[objects.first.vertex[k].clip]],
OutCode];
andOfCodes _ LOOPHOLE[
Basics.BITAND[LOOPHOLE[andOfCodes], LOOPHOLE[objects.first.vertex[k].clip]],
OutCode];
ENDLOOP;
IF andOfCodes # NoneOut THEN clipState _ out 
ELSE IF orOfCodes = NoneOut THEN clipState _ in
ELSE clipState _ clipped;
IF clipState # out THEN {
iz _ Real.FixI[zScale * ((zSum / nVtces) - minDepth)];
IF iz < 0 THEN iz _ 0;
};
};
IF clipState # out THEN {
IF buckets[iz].object # NIL THEN {
buckets[bucketListPtr].next _ buckets[iz].next;    buckets[iz].next _ bucketListPtr;
iz _ bucketListPtr;    bucketListPtr _ bucketListPtr + 1;
};
buckets[iz].object _ objects.first;    buckets[iz].polygon _ i;
};
ENDLOOP; 
objects _ objects.rest;
ENDLOOP;
RETURN[ buckets ];
}; 
DoInSequence: PUBLIC PROC[sortSeq: REF SortSequenceRep, action: PROC[ObjectPolygon]] ~ {
FOR i: NAT DECREASING IN [0..depthResolution) DO 
j: NAT _ i;
WHILE sortSeq[j].object # NIL DO
action[sortSeq[j]];								-- call back with next polygon in order
j _ sortSeq[j].next;
IF j = 0 THEN EXIT;
ENDLOOP;
ENDLOOP;
}; 
DoForPolygons: PUBLIC PROC[objects: LIST OF REF Object, action: PROC[ObjectPolygon]] ~ {
WHILE objects # NIL DO      		-- Enter polygons (by z-centroid) in bucket lists
IF objects.first.clipState # out THEN FOR i: INT IN [0..objects.first.numPolys) DO 
OPEN objects.first.polygon[i];
zSum: REAL _ 0.;
IF objects.first.clipState = in THEN { 								-- unclipped, inside
clipState _ in;
}
ELSE IF objects.first.clipState = clipped THEN {								-- clipped
orOfCodes: OutCode _ NoneOut;    andOfCodes: OutCode _ AllOut; 
FOR j: NAT IN [0..nVtces) DO
k: NAT _ vtxPtr[j];
orOfCodes _ LOOPHOLE[
Basics.BITOR[LOOPHOLE[orOfCodes], LOOPHOLE[objects.first.vertex[k].clip]],
OutCode];
andOfCodes _ LOOPHOLE[
Basics.BITAND[LOOPHOLE[andOfCodes], LOOPHOLE[objects.first.vertex[k].clip]],
OutCode];
ENDLOOP;
IF andOfCodes # NoneOut THEN clipState _ out 
ELSE IF orOfCodes = NoneOut THEN clipState _ in
ELSE clipState _ clipped;
};
IF clipState # out THEN {
action[ [objects.first, i, 0] ];
};
ENDLOOP; 
objects _ objects.rest;
ENDLOOP;
};
ClipIntPoly: PUBLIC PROC[poly: ObjectPolygon] ~ {
};
IntShade: PUBLIC PROC[xn, yn, zn: INTEGER, lights: LightList] 
RETURNS[INTEGER] ~ {
RETURN[0];
};

END.
PolygonPackageImpl.mesa
Last Edited by: Crow, December 6, 1983 4:04 pm
cotangent, etc. of 1/2 angle included in field of view, set by GetTransforms
anything clser to the eyepoint than this will be clipped
Backfacing test based on first vertex and adjacent vertices
value: REAL _ DotProd[Normalize[light.first.pos], Normalize[ [xn, yn, zn] ]];
Remove backfacers and fix twisted quadrilaterals
{  zees: ARRAY [0..8) OF REAL;  
mostPos: REAL _ -Real.LargestNumber;    mostPtr: NAT _ 0;    allPos: BOOLEAN _ TRUE;
FOR i: NAT IN [0..poly.nVtces) DO
OPEN poly.vtx[i];
next: Vertex _ poly.vtx[ (i + 1) MOD poly.nVtces ];
last: Vertex _ poly.vtx[ (i + poly.nVtces - 1) MOD poly.nVtces ];
direction: Triple _ Normalize[CrossProd[
					[next.x - x, next.y - y, next.z - z], [last.x - x, last.y - y, last.z - z] ]];
zees[i] _ DotProd[ Normalize[ [x, y, z] ], direction];
IF zees[i] < 0. 
THEN allPos _ FALSE
ELSE IF zees[i] > mostPos THEN {  mostPos _ zees[i];    mostPtr _ i;  };
ENDLOOP;
IF allPos 
THEN {  poly.nVtces _ 0;    RETURN[ poly ];  }		-- Backfacing at all corners
ELSE IF mostPos > 0. 
THEN IF zees[(mostPtr + 2) MOD poly.nVtces] < 0. THEN {	-- Twisted
		FOR i: NAT IN [mostPtr..poly.nVtces) DO poly.vtx[i] _ poly.vtx[i+1]; ENDLOOP;
   		poly.nVtces _ poly.nVtces - 1;
		};    
};

Read Object
Get File, Read number of points and number of polygons

Read texture coordinates from named file and enter in the corresponding vertices
Compute Normals, Sum normals at polygon corners to get polygon normal
Sum normals for vertices given by adjacent polygon corners
Transform Vertices, Centroid, and Radius to Eye Space, check for inside/outside field of view 
check clipstate of bounding ball
run through vertices
   transform
compute outcode
Compute Shading
Bucket Sort
Clip Integer Vertices
Integer Shading
Κ$˜
headš
œ™Jš
œ.™.J˜š
Οk	˜	Jšœ	œ&˜4Jšœœ ˜0Jšœœœœ˜!Jšœ	œœ˜Jšœœ˜Jšœœœ˜1Jšœœ4˜HJš
œ?˜?Jš
œ˜—J˜—
head2šœœ
˜!I
ašœ,˜4Mšœ˜J˜Jšœœ
˜+J˜Jšœ6œ
œœ˜LJšœœ*˜9Jšœœ˜Iunitšœ	œœ
˜#šœAœ
˜FMšΟc?œ
™L—šœ
œ
˜M™8——NšΟnœ	œ
œœœœœ˜SšŸœ	œ
œœœœ˜8Mšœ
œœ˜3Mš
œ˜—šŸ	œœœ˜7Jšœ8˜>J˜—NšŸ
œœ
œ.œ˜MMšœœœ	˜<šœœ˜+M˜Mš
œ˜Mšœœ
˜Nš
œA˜AMš
œ)˜)Nšœž˜=Mš
œP˜PMš
œ*˜*Mšœž,˜KMš
œ9˜9š
œ˜Mš
œ7˜7Mš
œ"˜"Mš
œ!˜!Mš
œ"˜"Mš
œ˜—Mš
œ*˜*Mšœ"ž'˜IMš
œ:˜:š
œ˜Mš
œ8˜8Mš
œ"˜"Mš
œ!˜!Mš
œ"˜"Mš
œ˜—Mšœž˜:Mš
œ˜Mš
œ˜Mš
œ"˜"Mšœž'˜BMš
œ*˜*Mš
œ*˜*Mš
œ1˜1Mš
œ˜Mšœ*ž˜DMš
œ"˜"Mšœ ž˜>Mš
œ˜—šŸ
œœ
œœ
œœ˜AMš
œ;™;Mš
œ˜Mš
œ˜Mš
œ/˜/š
œ(˜(Mš
œ_˜_Mš
œd˜d—NšœM˜SMš
œ˜M˜—šŸ	œœ
œœœœ
˜VMšœœœ
œ	œ
œ
œœ˜PMšœœœ"˜AMš
œœ
œœ&œ
˜Qšœ	œ
˜š	œœ
œœž*˜MMšœ˜Mšœ!œ˜=Mšœ/œ˜GMš
œ%˜%Mš
œS˜SMšœœ=˜HMšœœB™MMšœœ˜MšœBž˜VMš
œ3˜3Mš
œ2˜2Mš
œ2˜2Mšœ
˜—M˜Mšœ
˜—š	œœ
œœž'˜JMšœœœœ	˜=Mšœœœœ	˜=Mšœœœœ	˜=Mšœ
˜—Mšœ
˜Mš
œ˜—Nš
Ÿœœ
œœœ˜Lšœœ
œ
˜+šŸœœœ
œœœ
˜Zš
Ÿœœœœœ˜BMšœœ˜"Mšœ˜Mšœœ˜ Mšœ	œ˜!Mšœ
œ˜"Mšœœ˜Mšœœ	˜Mšœœ˜Mšœœ
˜M˜—Mšœœœ
˜+Nšœœ
œž˜CMš
œ˜M˜Mš
œ+˜+Mšœœœ˜Išœœ
œ˜ Mšœœ
˜Mš
œ$˜$šœœ+˜GMš
œ-˜-Mš
œQ˜QMš
œQ˜QMš
œQ˜Qšœ	œ˜Mš
œQ˜QMš
œQ˜QMš
œQ˜QM˜—šœ	œ˜Mš
œN˜NMš
œN˜NMš
œN˜NMš
œN˜NMš
œ˜Mš
œC˜CMš
œ˜Mš
œC˜CM˜—M˜M˜—šœœž˜4Mš
œ0˜0Mš
œ0˜0Mš
œ0˜0šœ	œ˜Mš
œ0˜0Mš
œ0˜0Mš
œ0˜0M˜—šœ	œ˜Mš
œ.˜.Mš
œ.˜.Mš
œ.˜.Mš
œ.˜.Mš
œ6˜6Mš
œ6˜6Mš
œ˜—M˜M˜—Mš
œ˜Mšœ
˜—M˜Mšœ˜Mš
œ˜—N˜šœœ
œœ
˜"šœœ
˜Jšœœ
œ
œ˜DJš
œ
˜
—Jšœ
˜—Jšœœ,˜EJšœœ-˜GJšœœ.˜HJšœœ-˜FJšœœ+˜CJšœœ,˜EJšœ˜M˜Nš
Οi0™0šœ	œœ
œ™ Mš	œ	œ$œœœ
™Tšœœ
œ™!Mšœ
™Mšœ!œ™3Mšœ/œ™AMš
œ(™(Mš
œS™SMš
œ6™6Mšœ™Mšœ
™Mšœ
œœ*™HMšœ
™—Mšœ™
Mšœœž™LMšœ
œ™š	œ
œœœž
™BMšœœœ
œœœ
™OMš
œ#™#Mš
œ™——M™—šŸ	œœ
œœœ
œ˜CMš
 ™Jšœœ
œ	˜!J˜šœœ
˜
Jš
œ6™6—Jšœœ
œ˜+Jšœœ˜Jšœœž#˜EJš	œœœœž˜QJš
œ˜Jš
œ#˜#Jš
œ$˜$J˜J˜J˜-Jš
œ#˜#Nšœœ'˜:š	œœ
œœž˜<Jš
œ'˜'Jš
œ'˜'Jš
œ'˜'Jšœ
˜—Nšœ
œœ)˜=š
œœ
œœž 
˜KJšœœœ˜Jšœœ˜)Jš
œ"˜"šœœ
œ
˜Jšœœž ˜UJšœ
˜—Jšœ
˜—Nš
œI˜Iš	œœ
œœž˜LJš
œ>˜>Jš
œJ˜JJš
œ>˜>Jš
œJ˜JJš
œ>˜>Jš
œJ˜JJšœ
˜—Jš
œ)˜)Jš
œ*˜*Jš
œ)˜)Jš
œ˜š	œœ
œœž˜IJš
œ˜š
œ/˜/Jš
œ-˜-Jš
œ0˜0—Jšœ ˜"Jšœ ˜$Jšœ˜	—Jšœ	˜J˜—šŸ	œœ
œœ
œœ˜WJšœœ
œ˜,Jšœœ˜Jšœœ
˜šœœœ%œ
˜DMšœœ"˜4—Jšœœž˜CJš	œœœœž˜HJšœœ˜Jšœ˜Jšœ
œ˜Jšœœ˜(šœœ
œ˜Jšœœ˜&Jšœœ˜&Jšœœ˜&Jšœ
˜—J˜M™Mš
œP™P—šŸ	œœ
œœ
œœ˜[Jšœœ
œ!˜1Jšœœ˜Jšœ
œ
˜šœœœ'œ
˜HMšœœ)˜=—Jšœœž˜CJš	œœœœž˜HJšœœ˜Jšœ˜Jšœ
œ˜Jšœœ˜&šœœ
œ˜Jšœœœ˜Jšœœ˜0Jš
œ"˜"šœœ
œ
˜Jšœ!œ˜3Jšœ!œ˜3Jšœ
˜—Jšœ
˜—Jš
œ˜J˜—š
Ÿ
œœ
œœœ˜Všœœœ%œ
˜DMšœœ#˜5—šœœ
œ˜!JšœEœ
˜Q—Jš
œ˜—šŸœœ
œ	œ
˜4Mš œ4™EJšœ˜šœ
œ
œœ˜4Jšœœ"˜-J˜J˜—š
œœ
œœ
œ˜/J˜šœœ
œ
œ
˜ Jšœœœ	˜,Jšœœœ	˜#˜'J˜8J˜8J˜—Jšœ
˜—J˜J˜J˜J˜Jšœ˜	—J˜—šŸ
œœ
œ	œ˜2Jš
œ:™:Jšœ˜šœœ
œœ˜5Jšœœ!˜,J˜J˜—Jš
œœ
œœ0œ˜Wš
œœ
œœ
œ˜/šœœ
œ
œ
˜ Jšœœœ	˜,Jšœœœ˜"šœœ˜˜4J˜9J˜7J˜—J˜—Jšœ
˜—Jšœ˜	—š
œœ
œœ
œ
˜-J˜+Jšœ
˜—J˜—š
Ÿœœ
œ	œ œ˜XMš
œ^™^š
œ˜Nš
  ™ —Jš
œ8˜8Jšœœ2ž ˜]Jšœœ˜Jšœœ6ž˜]Jšœ9˜;Jšœ
œ
œ8˜AJšœ
œœ9˜BJšœ$ž	˜1Jšœ
œ9˜@Jšœ
œP˜SJšœ
œQ˜TJšœœž
˜DJšœ˜ Jš
œ ˜ šœ0ž'˜WNš
 ™—Jš
œ,˜,J™š
œœ
œœ
œ˜<Jš
œ5˜5Jšœ
˜Jš
œ™—šœœ˜$š
œœ
œœ
œ˜@Jš
œ4˜4Jš
œ4˜4Jšœ.œ
˜4šœœ
˜Jšœœ
œ
œ˜2Jš
œ˜—šœ
œ
˜Jšœœ
œœ˜4Jš
œ	˜	—šœœ˜Jš
œ/˜/Jš
œ/˜/J˜—Jšœ
˜—Mšœœ˜8Jšœœ˜9J˜
—šœœœ
œœ
œ˜_Jš
œ/˜/Jš
œ/˜/Jš
œ˜Jš
˜—Jšœœ
˜Jšœ˜J˜Nš
 ™—šŸ	œœ
œ	œ6˜Xšœœ
œœ˜?Mšœœ˜Mš
œ˜šœ
œ
˜MšœœN˜XMšœœ˜MšœBž˜VMš
œ+˜+Mš
œ*˜*Mš
œ*˜*M˜Mšœ
˜Mšœœœœ
˜Cšœ˜Mš
œ)˜)Mš
œ(˜(Mš
œ(˜(Mšœœ˜'—Mš
œ˜—Mšœ
˜—Jšœœ
˜Mš
œ˜Nš
 ™—šŸœœ
œ
œ
œ
œ	œ
œ˜[Mšœœ˜Mšœœ˜%Mšœœ˜6Mšœœ˜Mšœ
œ
œ
œ˜*šœœ
œž2˜Jšœœ˜'Mš
œ5˜5MšœE˜GMšœF˜JMšœE˜GMšœF˜JM˜—Mš
œ˜Mšœ
˜—Mšœœ8˜Zšœœœ2˜HMšœœ2˜D—Mšœœ
œœœœ
˜^Mš
œ˜šœœ
œž7˜Ošœœ
œœ
œœ
˜SJšœ˜Jšœœœ
˜šœœž˜CJš
œœ
œ
œ3œ˜XJ˜7J˜J˜
—šœ
œ#œ
ž
˜BJ˜?šœœ
œ
˜Jšœœ
˜Jš
œ)˜)šœœ
˜Jšœœ
œ
œ ˜JJš
œ	˜	—šœ
œ
˜Jšœœ
œœ ˜LJš
œ	˜	—Jšœ
˜—Jšœœ˜-Jšœ
œœ˜/Jšœ˜šœœ˜Jš
œ6˜6Jšœœ˜J˜—J˜—šœœ˜šœœ
œ˜"J˜TJ˜9J˜—J˜?J˜—Jšœ˜	—Mš
œ˜Mšœ
˜—Mšœ˜Mš
œ˜—š
Ÿœœ
œ
œœ˜Xšœœ

œœ
˜1Mšœœ˜šœœ
˜ Mšœž,˜BMš
œ˜Mšœœ
œ
˜Mšœ
˜—Mšœ
˜—Mš
œ˜—šŸ
œœ
œ
œ
œ
œœ˜Xšœœ
œž7˜Ošœœ
œœ
œœ
˜SJšœ˜Jšœœ˜šœœž˜CJ˜Jš
œ
˜
—šœ
œ#œ
ž
˜BJ˜?šœœ
œ
˜Jšœœ
˜šœœ
˜Jšœœ
œ
œ ˜JJš
œ	˜	—šœ
œ
˜Jšœœ
œœ ˜LJš
œ	˜	—Jšœ
˜—Jšœœ˜-Jšœ
œœ˜/Jšœ˜J˜—šœœ˜Jš
œ ˜ J˜—Jšœ˜	—Mš
œ˜Mšœ
˜—Mš
œ˜—šŸœœ
œ˜1Jš
œ™Mš
œ˜—šŸœœ
œ
œ˜>Jšœ
œ˜Jš
œ™Jšœ˜
š
œ˜J˜——Jšœ
˜—…—Rςr,