<> <> 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 ]; }; <> <<{ zees: ARRAY [0..8) OF REAL; >> <> <> <> <> <> <> << [next.x - x, next.y - y, next.z - z], [last.x - x, last.y - y, last.z - z] ]];>> <> <> <> < mostPos THEN { mostPos _ zees[i]; mostPtr _ i; };>> <> <> <> < 0. >> <> << 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] ~ { <> 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; << transform>> 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.