PolygonPackageImpl.mesa
Last Edited by: Crow, December 6, 1983 4:04 pm
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;
cotangent, etc. of 1/2 angle included in field of view, set by GetTransforms
hitherLimit:
REAL;
anything clser to the eyepoint than this will be clipped
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] ~ {
Backfacing test based on first vertex and adjacent vertices
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]];
value: REAL ← DotProd[Normalize[light.first.pos], Normalize[ [xn, yn, zn] ]];
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 ];
};
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;
};
};
GetObject:
PUBLIC
PROC[fileName: Rope.
ROPE]
RETURNS[
REF Object] ~ {
Read Object
object: REF Object ← NEW[Object];
min, max: Triple;
radius:
REAL;
Get File, Read number of points and number of polygons
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;
};
Read texture coordinates from named file and enter in the corresponding vertices
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] ~ {
Compute Normals, Sum normals at polygon corners to get polygon normal
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] ~ {
Sum normals for vertices given by adjacent polygon corners
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] ~ {
Transform Vertices, Centroid, and Radius to Eye Space, check for inside/outside field of view
andOfCodes, orOfCodes: OutCode;
check clipstate of bounding ball
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
run through vertices
orOfCodes ← NoneOut; andOfCodes ← AllOut;
transform
FOR i:
INT
IN [0..object.numVtces)
DO
OPEN object.vertex[i];
[ [ex, ey, ez] ] ← Transform3D[ [x, y, z] , xfm];
ENDLOOP;
compute outcode
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 ];
};
Compute Shading
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;
};
Bucket Sort
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] ~ {
Clip Integer Vertices
};
IntShade:
PUBLIC
PROC[xn, yn, zn:
INTEGER, lights: LightList]
RETURNS[INTEGER] ~ {
Integer Shading
RETURN[0];
END.