Copyright © 1984 by Xerox Corporation. All rights reserved.
Last Edited by: Crow, January 22, 1986 10:05:40 pm PST
DIRECTORY
Atom USING [GetPropFromList],
Real USING [RoundC, FixI, FixC],
RealFns USING [SqRt],
Basics USING [BITOR, BITAND],
Rope USING [ROPE],
IO USING [STREAM, GetInt],
Imager USING [Context, MaskVectorI],
ImagerColor USING [RGB],
Pixels USING [GetSampleSet, SampleSet],
ScanConvert USING [PutLine],
Linear3d USING [DotProd, Triple, Quad, Normalize, CrossProd, SumTriple,
EvalPlane],
ThreeDMisc USING [GetMappedColor, GetImagerContext, SetNamedColor],
ThreeDScenes USING [SixSides, OutCode, NoneOut, AllOut,
ShapeInstance, ShapeSequence, Context, ShadingSequence,
ClipState, Vertex, VertexInfo, VertexSequence, SetUpStandardFile,
ReadColors, PutShading, GetShading, ShadePt, FillInBackGround,
XfmToEyeSpace, XfmToDisplay, ReadVertexCoords,
FillViewPort, GetVtxShades, XfmPtToDisplay],
Tilers USING [PolygonTiler],
ThreeDPolygons USING [Polygon, PtrPolySequence, PtrPoly, SortSequence,
ShapePolygon];
ThreeDPolygonsImpl:
CEDAR
PROGRAM
IMPORTS Atom, Real, RealFns, IO, Basics, ThreeDScenes, Tilers, Linear3d, ScanConvert, ThreeDMisc, Pixels, Imager
EXPORTS ThreeDPolygons
= BEGIN
Internal Declarations
ThreeDPolygonsError: PUBLIC SIGNAL [reason: ATOM] = CODE;
RGB: TYPE ~ ImagerColor.RGB; -- [ r, g, b: REAL];
SixSides: TYPE ~ ThreeDScenes.SixSides;
Triple: TYPE ~ Linear3d.Triple;
SampleSet: TYPE ~ Pixels.SampleSet;
ShapeInstance: TYPE ~ ThreeDScenes.ShapeInstance;
Polygon: TYPE ~ ThreeDPolygons.Polygon;
Vertex: TYPE ~ ThreeDScenes.Vertex;
tempPoly, tempPoly2: REF Polygon ← NIL; -- temps for clipping, etc.
pixelBytes: SampleSet ← Pixels.GetSampleSet[1]; -- cache for pixel size
stopMe: BOOLEAN ← FALSE;
sortSeq, buckets: REF ThreeDPolygons.SortSequence ← NIL; -- made global to limit garbage collection
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.];
};
DiffPosns:
PROC[vtx1, vtx2: Vertex]
RETURNS[Triple] ~ {
RETURN[[vtx1.x - vtx2.x, vtx1.y - vtx2.y, vtx1.z - vtx2.z]] };
HoldEverything:
PROCEDURE [] ~ {
stopMe ← FALSE;
ERROR ABORTED;
};
EnableDisplay: PUBLIC PROC [] ~ { stopMe ← FALSE; };
StopDisplay: PUBLIC PROC [] ~ { stopMe ← TRUE; };
ShapetoColorBytes:
PROC [context:
REF ThreeDScenes.Context, s:
REF ShapeInstance]
RETURNS[SampleSet] ~ {
ref: REF ANY ← ThreeDScenes.GetShading[ s, $Color];
r, g, b: REAL;
ir, ig, ib: INTEGER;
IF ref #
NIL
THEN {
[r, g, b] ← NARROW[ ref, REF RGB]^; -- shape color
ir ← Real.RoundC[r*255.0]; ig ← Real.RoundC[g*255.0]; ib ← Real.RoundC[b*255.0];
}
ELSE ir ← ig ← ib ← 255;
SELECT context.renderMode
FROM
-- convert color to byte sequence
$LF => {};
$Dithered, $PseudoClr => {
IF pixelBytes.length # 1 THEN pixelBytes ← Pixels.GetSampleSet[1];
pixelBytes[0] ← ThreeDMisc.GetMappedColor[context, [ir, ig, ib] ];
};
$Grey => {
IF pixelBytes.length # 1 THEN pixelBytes ← Pixels.GetSampleSet[1];
pixelBytes[0] ← (ir + ig + ib)/3;
};
$FullClr, $Dorado24 => {
IF pixelBytes.length # 3 THEN pixelBytes ← Pixels.GetSampleSet[3];
pixelBytes[0] ← ir;
pixelBytes[1] ← ig;
pixelBytes[2] ← ib;
};
ENDCASE => SIGNAL ThreeDPolygonsError[$BadRenderMode];
RETURN[pixelBytes];
};
CombineBoxes:
PROC[context:
REF ThreeDScenes.Context] ~ {
-- get combined bounding box
context.extentCovered ← [LAST[NAT], 0, LAST[NAT], 0];
FOR i:
NAT
IN [0..context.shapes.length)
DO
IF context.shapes[i].clipState # out
THEN {
IF context.extentCovered.left > context.shapes[i].screenExtent.left
THEN context.extentCovered.left ← context.shapes[i].screenExtent.left;
IF context.extentCovered.right < context.shapes[i].screenExtent.right
THEN context.extentCovered.right ← context.shapes[i].screenExtent.right;
IF context.extentCovered.bottom > context.shapes[i].screenExtent.bottom
THEN context.extentCovered.bottom ← context.shapes[i].screenExtent.bottom;
IF context.extentCovered.top < context.shapes[i].screenExtent.top
THEN context.extentCovered.top ← context.shapes[i].screenExtent.top;
};
ENDLOOP;
};
Procedures for Reading in Shape Descriptions
Load
Shape:
PUBLIC
PROC[ shape:
REF ShapeInstance, fileName: Rope.
ROPE,
type:
ATOM ← $Polyhedron ] ~ {
numVtces: NAT;
min, max: Triple;
radius:
REAL;
Get File, Read number of points and number of polygons
input: IO.STREAM;
[input, numVtces] ← ThreeDScenes.SetUpStandardFile[fileName];
shape.numSurfaces ← IO.GetInt[input];
shape.type ← type;
ThreeDScenes.ReadVertexCoords[shape, input, numVtces]; -- read vertices
ReadPolygons[shape, input, shape.numSurfaces];
-- read polygons
Find approximation to bounding sphere
min ← max ← [shape.vertex[0].x, shape.vertex[0].y, shape.vertex[0].z];
FOR i:
NAT
IN (0..numVtces)
DO
-- get min and max in x, y, and z
IF shape.vertex[i].x < min.x
THEN min.x ← shape.vertex[i].x
ELSE IF shape.vertex[i].x > max.x THEN max.x ← shape.vertex[i].x;
IF shape.vertex[i].y < min.y
THEN min.y ← shape.vertex[i].y
ELSE IF shape.vertex[i].y > max.y THEN max.y ← shape.vertex[i].y;
IF shape.vertex[i].z < min.z
THEN min.z ← shape.vertex[i].z
ELSE IF shape.vertex[i].x > max.z THEN max.z ← shape.vertex[i].z;
ENDLOOP;
shape.centroid.x ← (min.x + max.x) / 2; -- get middle point in each coordinate
shape.centroid.y ← (min.y + max.y) / 2;
shape.centroid.z ← (min.z + max.z) / 2;
shape.boundingRadius ← 0.;
FOR i:
NAT
IN [0..numVtces)
DO
-- find radius
radius ← RealFns.SqRt[
Sqr[shape.vertex[i].x - shape.centroid.x]
+ Sqr[shape.vertex[i].y - shape.centroid.y]
+ Sqr[shape.vertex[i].z - shape.centroid.z] ];
IF radius > shape.boundingRadius
THEN shape.boundingRadius ← radius;
ENDLOOP;
};
ReadPolygons:
PUBLIC
PROC[shape:
REF ShapeInstance, in:
IO.
STREAM, nPolys:
NAT] ~ {
surface: REF ThreeDPolygons.PtrPolySequence;
shape.surface ← NEW[ ThreeDPolygons.PtrPolySequence[shape.numSurfaces] ];
surface ← NARROW[shape.surface, REF ThreeDPolygons.PtrPolySequence];
FOR i:
NAT
IN [0..nPolys)
DO
--
Read Polygons
nVtces: NAT ← IO.GetInt[in];
surface[i] ← NEW[ThreeDPolygons.PtrPoly[nVtces]];
surface[i].nVtces ← nVtces;
FOR j:
NAT
IN [0..nVtces)
DO
surface[i].vtxPtr[j] ← IO.GetInt[in] - 1; -- switch to counting from zero
ENDLOOP;
ENDLOOP;
};
GetPolygonColors:
PUBLIC
PROC[shape:
REF ShapeInstance, fileName: Rope.
ROPE] ~ {
in: IO.STREAM;
nPolys: NAT;
ThreeDScenes.PutShading[ shape, $Type, $Faceted ];
[in, nPolys] ← ThreeDScenes.SetUpStandardFile[fileName];
ThreeDScenes.ReadColors[shape, in, nPolys];
GetPolyNormals[shape];
ThreeDScenes.PutShading[ shape, $PolyColors, fileName ];
shape.shadingInValid ← TRUE;
};
Procedures for Transformations and Clipping
ClipPoly:
PUBLIC
PROC[ context:
REF ThreeDScenes.Context, shape:
REF ShapeInstance,
poly, poly2:
REF Polygon]
RETURNS [
REF Polygon,
REF Polygon] ~ {
Clip:
PROC[side: SixSides, pIn, pOut:
REF Polygon]
RETURNS [
REF Polygon,
REF Polygon] = {
Dist:
PROC[side: SixSides, vtx: Vertex]
RETURNS [
REAL] = {
-- + inside, - outside
RETURN[ Linear3d.EvalPlane[
context.clippingPlanes[side],
[vtx.ex, vtx.ey, vtx.ez]
] ];
};
shading: ATOM ← NARROW[ ThreeDScenes.GetShading[shape, $Type] ];
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;
pOut.vtx[outCnt].coord.x ← pIn.vtx[i].coord.x * a + pIn.vtx[last].coord.x * b;
pOut.vtx[outCnt].coord.y ← pIn.vtx[i].coord.y * a + pIn.vtx[last].coord.y * b;
pOut.vtx[outCnt].coord.z ← pIn.vtx[i].coord.z * a + pIn.vtx[last].coord.z * b;
IF shading # $Fancy
THEN {
-- Integer shading, using precomputed colors
pOut.vtx[outCnt].shade.ir ← Real.RoundC[
pIn.vtx[i].shade.ir * a + pIn.vtx[last].shade.ir * b ];
pOut.vtx[outCnt].shade.ig ← Real.RoundC[
pIn.vtx[i].shade.ig * a + pIn.vtx[last].shade.ig * b ];
pOut.vtx[outCnt].shade.ib ← Real.RoundC[
pIn.vtx[i].shade.ib * a + pIn.vtx[last].shade.ib * b ];
pOut.vtx[outCnt].shade.it ← Real.RoundC[
pIn.vtx[i].shade.it * a + pIn.vtx[last].shade.it * b ];
}
ELSE {
-- fancy shading, using original colors and texture
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;
};
IF (shading = $Shiny
OR shading = $Fancy)
THEN {
-- normals
pOut.vtx[outCnt].shade.exn ← pIn.vtx[i].shade.exn*a + pIn.vtx[last].shade.exn*b;
pOut.vtx[outCnt].shade.eyn ← pIn.vtx[i].shade.eyn*a + pIn.vtx[last].shade.eyn*b;
pOut.vtx[outCnt].shade.ezn ← pIn.vtx[i].shade.ezn*a + pIn.vtx[last].shade.ezn*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;
pOut.vtx[outCnt].coord.x ← pIn.vtx[i].coord.x;
pOut.vtx[outCnt].coord.y ← pIn.vtx[i].coord.y;
pOut.vtx[outCnt].coord.z ← pIn.vtx[i].coord.z;
IF shading # $Fancy
THEN {
-- Integer shading, using precomputed colors
pOut.vtx[outCnt].shade.ir ← pIn.vtx[i].shade.ir;
pOut.vtx[outCnt].shade.ig ← pIn.vtx[i].shade.ig;
pOut.vtx[outCnt].shade.ib ← pIn.vtx[i].shade.ib;
pOut.vtx[outCnt].shade.it ← pIn.vtx[i].shade.it;
}
ELSE {
-- fancy shading, using original colors and texture
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;
};
IF (shading = $Shiny
OR shading = $Fancy)
THEN {
-- normals
pOut.vtx[outCnt].shade.exn ← pIn.vtx[i].shade.exn;
pOut.vtx[outCnt].shade.eyn ← pIn.vtx[i].shade.eyn;
pOut.vtx[outCnt].shade.ezn ← pIn.vtx[i].shade.ezn;
};
outCnt ← outCnt + 1;
};
lastDist ← dist; last ← i;
ENDLOOP;
pOut.nVtces ← outCnt;
RETURN [ pOut, pIn ];
}; -- end Clip Proc
orOfCodes: ThreeDScenes.OutCode ← ThreeDScenes.NoneOut;
FOR i:
NAT
IN [0..poly.nVtces)
DO
orOfCodes ←
LOOPHOLE[
Basics.BITOR[LOOPHOLE[orOfCodes], LOOPHOLE[poly.vtx[i].coord.clip]],
ThreeDScenes.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 ];
};
Procedures for Shading
BackFacing:
PUBLIC
PROC[ poly:
REF Polygon]
RETURNS [
BOOLEAN] ~ {
Backfacing test based on first vertex and adjacent vertices
this: ThreeDScenes.VertexInfo ← poly.vtx[0];
next: ThreeDScenes.VertexInfo ← poly.vtx[1];
last: ThreeDScenes.VertexInfo ← poly.vtx[poly.nVtces - 1];
direction: Triple ← Linear3d.Normalize[Linear3d.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[ Linear3d.DotProd[[this.coord.ex, this.coord.ey, this.coord.ez] , direction] > 0. ];
};
ShadePoly:
PUBLIC
PROC[ context:
REF ThreeDScenes.Context, poly:
REF Polygon] ~ {
ref: REF ← Atom.GetPropFromList[poly.props, $Shininess];
shininess: REAL ← IF ref # NIL THEN NARROW[ref, REF REAL]^ ELSE 0.0;
clr: RGB;
transmittance: REAL;
shading: ATOM ← NARROW[ Atom.GetPropFromList[ poly.props, $Type ] ];
IF shading = $Shiny OR shading = $Fancy THEN shininess ← 0.0; -- highlights later
FOR i:
NAT
IN [0..poly.nVtces)
DO
-- Check limits and store with vertices
[clr, transmittance] ← ThreeDScenes.ShadePt[context, poly.vtx[i], shininess];
poly.vtx[i].shade.ir ← Real.FixC[clr.R * 255.0];
poly.vtx[i].shade.ig ← Real.FixC[clr.G * 255.0];
poly.vtx[i].shade.ib ← Real.FixC[clr.B * 255.0];
poly.vtx[i].shade.it ← Real.FixC[ transmittance * 255.0];
ENDLOOP;
};
GetShades:
PUBLIC
PROC[context:
REF ThreeDScenes.Context, shape:
REF ShapeInstance] ~ {
Calculate shades for Faceted shading (Used for quick display)
AverageVertices:
PROC[poly:
REF ThreeDPolygons.PtrPoly]
RETURNS[vtx: Vertex] ~ {
FOR i:
NAT
IN [0..poly.nVtces)
DO
addVtx: Vertex ← shape.vertex[poly.vtxPtr[i]];
vtx.x ← vtx.x + addVtx.x; vtx.y ← vtx.y + addVtx.y; vtx.z ← vtx.z + addVtx.z;
vtx.ex ← vtx.ex + addVtx.ex; vtx.ey ← vtx.ey + addVtx.ey; vtx.ez ← vtx.ez + addVtx.ez;
vtx.sx ← vtx.sx + addVtx.sx; vtx.sy ← vtx.sy + addVtx.sy; vtx.sz ← vtx.sz + addVtx.sz;
vtx.clip ← LOOPHOLE[ Basics.BITOR[ LOOPHOLE[vtx.clip], LOOPHOLE[addVtx.clip] ],
ThreeDScenes.OutCode];
ENDLOOP;
vtx.x ← vtx.x/poly.nVtces; vtx.y ← vtx.y/poly.nVtces; vtx.z ← vtx.z/poly.nVtces;
vtx.ex ← vtx.ex/poly.nVtces; vtx.ey ← vtx.ey/poly.nVtces; vtx.ez ← vtx.ez/poly.nVtces;
vtx.sx ← vtx.sx/poly.nVtces; vtx.sy ← vtx.sy/poly.nVtces; vtx.sz ← vtx.sz/poly.nVtces;
};
poly: REF ThreeDPolygons.PtrPolySequence;
ref: REF ← Atom.GetPropFromList[shape.shadingProps, $Shininess];
shininess: REAL ← IF ref # NIL THEN NARROW[ref, REF REAL]^ ELSE 0.0;
clr: RGB;
IF shape.surface =
NIL
OR ThreeDScenes.GetShading[shape, $Type] # $Faceted
THEN {
SIGNAL ThreeDPolygonsError[$InsufficientInfo];
RETURN;
};
poly ←
NARROW[ shape.surface,
REF ThreeDPolygons.PtrPolySequence ];
FOR i:
NAT
IN [0..shape.shade.length)
DO
IF poly[i].clipState # out
THEN {
trns: REAL ← 0.0; -- transmittance
vtx: Vertex ← AverageVertices[poly[i]];
pt: ThreeDScenes.VertexInfo ← [ vtx, shape.shade[i], NIL ];
[clr, trns] ← ThreeDScenes.ShadePt[context, pt, shininess]; -- calculate shade
shape.shade[i].ir ← Real.FixC[clr.R * 255.0];
shape.shade[i].ig ← Real.FixC[clr.G * 255.0];
shape.shade[i].ib ← Real.FixC[clr.B * 255.0];
shape.shade[i].it ← Real.FixC[ trns * 255.0];
}; ENDLOOP;
shape.shadingInValid ← FALSE;
};
GetNormal:
PROC[vertex:
REF ThreeDScenes.VertexSequence,
poly:
REF ThreeDPolygons.PtrPoly, cVtx:
NAT]
RETURNS[normal: Triple] ~ {
lVtx: NAT ← (cVtx + poly.nVtces - 1) MOD poly.nVtces;
nVtx: NAT ← (cVtx + 1) MOD poly.nVtces;
normal ← Linear3d.CrossProd[
DiffPosns[ vertex[poly.vtxPtr[lVtx]], vertex[poly.vtxPtr[cVtx]] ],
DiffPosns[ vertex[poly.vtxPtr[nVtx]], vertex[poly.vtxPtr[cVtx]] ]
];
};
GetPolyNormals:
PUBLIC
PROC[shape:
REF ShapeInstance] ~ {
Compute Normals, Sum normals at polygon corners to get polygon normal
surface: REF ThreeDPolygons.PtrPolySequence;
IF shape.surface = NIL THEN RETURN; -- not a shape (probably a light source)
surface ← NARROW[shape.surface, REF ThreeDPolygons.PtrPolySequence];
IF shape.shade =
NIL
OR shape.shade.length # shape.numSurfaces
THEN {
shape.shade ← NEW[ ThreeDScenes.ShadingSequence[shape.numSurfaces] ];
ThreeDScenes.PutShading[shape, $Type, $Faceted];
};
FOR i:
NAT
IN [0..shape.numSurfaces)
DO
sumNmls: Triple ← [0., 0., 0.];
FOR cVtx:
NAT
IN [0..surface[i].nVtces)
DO
sumNmls ← Linear3d.SumTriple[ sumNmls,
GetNormal[shape.vertex, surface[i], cVtx] ];
ENDLOOP;
sumNmls ← Linear3d.Normalize[sumNmls];
shape.shade[i].xn ← sumNmls.x;
shape.shade[i].yn ← sumNmls.y;
shape.shade[i].zn ← sumNmls.z;
ENDLOOP;
shape.vtcesInValid ← TRUE; -- make sure eye-space normals correct
};
GetVtxNormals:
PUBLIC
PROC[shape:
REF ShapeInstance] ~ {
Sum normals for vertices given by adjacent polygon corners
surface: REF ThreeDPolygons.PtrPolySequence ← NARROW[shape.surface];
IF shape.shade =
NIL
OR shape.shade.length # shape.vertex.length
THEN {
shape.shade ← NEW[ ThreeDScenes.ShadingSequence[shape.vertex.length] ];
IF ThreeDScenes.GetShading[ shape, $Type ] =
NIL
OR ThreeDScenes.GetShading[ shape, $Type ] = $Faceted
THEN ThreeDScenes.PutShading[ shape, $Type, $Smooth];
};
FOR i:
NAT
IN [0..shape.vertex.length)
DO
shape.shade[i].xn ← shape.shade[i].yn ← shape.shade[i].zn ← 0.;
ENDLOOP;
FOR i:
NAT
IN [0..shape.numSurfaces)
DO
-- get normals at vertices, add to earlier ones
FOR cVtx:
NAT
IN [0..surface[i].nVtces)
DO
OPEN shape.shade[surface[i].vtxPtr[cVtx]];
cornerNormal: Triple ← GetNormal[ shape.vertex, surface[i], cVtx ];
[[xn, yn, zn]] ← Linear3d.SumTriple[ cornerNormal, [xn, yn, zn]];
ENDLOOP;
ENDLOOP;
FOR i:
NAT
IN [0..shape.shade.length)
DO
OPEN shape.shade[i];
[[xn, yn, zn]] ← Linear3d.Normalize[ [xn, yn, zn] ];
ENDLOOP;
shape.vtcesInValid ← TRUE; -- make sure eye-space normals correct
};
Procedures for Sorting and Display
LoadSortSequence:
PUBLIC
PROC[ context:
REF ThreeDScenes.Context,
buckets:
REF ThreeDPolygons.SortSequence ←
NIL ]
RETURNS[
REF ThreeDPolygons.SortSequence] ~ {
shape: REF ThreeDScenes.ShapeSequence ← context.shapes;
polygonCount: NAT ← 0;
bucketListPtr: NAT ← context.depthResolution;
minDepth, maxDepth: REAL ← shape[0].centroid.ez;
zScale: REAL ← 1.;
FOR i:
NAT
IN [0.. shape.length)
DO
-- get minimum and maximum depth and polygon count
IF shape[i].clipState # out
AND shape[i].surface #
NIL
THEN {
radius: REAL ← shape[i].boundingRadius;
IF shape[i].centroid.ez - radius < minDepth
THEN minDepth ← shape[i].centroid.ez - radius;
IF shape[i].centroid.ez + radius > maxDepth
THEN maxDepth ← shape[i].centroid.ez + radius;
polygonCount ← polygonCount + shape[i].numSurfaces;
};
ENDLOOP;
minDepth ← MAX[minDepth, 0]; -- nothing allowed behind the eyepoint
IF (maxDepth - minDepth) > 0.
THEN zScale ← (context.depthResolution - 1) / (maxDepth - minDepth);
IF buckets =
NIL
OR buckets.length < polygonCount + context.depthResolution
THEN
buckets ← NEW[ThreeDPolygons.SortSequence[polygonCount + context.depthResolution]];
FOR i:
NAT
IN [0..context.depthResolution)
DO
buckets[i].shape ← NIL; buckets[i].next ← 0; ENDLOOP;
FOR s:
NAT
IN [0.. shape.length)
DO
-- Enter polygons (by z-centroid) in bucket lists
IF shape[s].clipState # out
AND shape[s].surface #
NIL THEN {
poly: REF ThreeDPolygons.PtrPolySequence ← NARROW[shape[s].surface];
FOR i:
NAT
IN [0..shape[s].numSurfaces)
DO
zSum: REAL ← 0.;
iz: INTEGER;
IF shape[s].clipState = in
THEN {
-- unclipped, inside
FOR j:
NAT
IN [0..poly[i].nVtces)
DO
zSum ← zSum + shape[s].vertex[poly[i].vtxPtr[j]].ez;
ENDLOOP;
iz ← Real.FixI[zScale * ((zSum / poly[i].nVtces) - minDepth)];
poly[i].clipState ← in;
}
ELSE
IF shape[s].clipState = clipped
THEN {
-- clipped, evaluate clipping tags
orOfCodes: ThreeDScenes.OutCode ← ThreeDScenes.NoneOut;
andOfCodes: ThreeDScenes.OutCode ← ThreeDScenes.AllOut;
FOR j:
NAT
IN [0..poly[i].nVtces)
DO
k: NAT ← poly[i].vtxPtr[j];
zSum ← zSum + shape[s].vertex[k].ez;
orOfCodes ←
LOOPHOLE[
Basics.BITOR[ LOOPHOLE[orOfCodes], LOOPHOLE[shape[s].vertex[k].clip] ],
ThreeDScenes.OutCode];
andOfCodes ←
LOOPHOLE[
Basics.BITAND[LOOPHOLE[andOfCodes], LOOPHOLE[shape[s].vertex[k].clip]],
ThreeDScenes.OutCode];
ENDLOOP;
IF andOfCodes # ThreeDScenes.NoneOut
THEN poly[i].clipState ← out
ELSE
IF orOfCodes = ThreeDScenes.NoneOut
THEN poly[i].clipState ← in
ELSE poly[i].clipState ← clipped;
IF poly[i].clipState # out
THEN {
iz ← Real.FixI[zScale * ((zSum / poly[i].nVtces) - minDepth)];
IF iz < 0 THEN iz ← 0;
};
};
IF poly[i].clipState # out
THEN {
IF buckets[iz].shape #
NIL
THEN {
-- previous entry in this bucket
buckets[bucketListPtr].next ← buckets[iz].next;
buckets[iz].next ← bucketListPtr;
iz ← bucketListPtr; bucketListPtr ← bucketListPtr + 1;
};
buckets[iz].shape ← shape[s];
buckets[iz].polygon ← i;
};
ENDLOOP;
};
ENDLOOP;
RETURN[ buckets ];
};
DoBackToFront:
PUBLIC
PROC[ context:
REF ThreeDScenes.Context,
sortSeq:
REF ThreeDPolygons.SortSequence,
action:
PROC[ThreeDPolygons.ShapePolygon] ] ~ {
ThreeDScenes.FillInBackGround[context];
FOR i:
NAT
DECREASING IN [0..context.depthResolution)
DO
j: NAT ← i;
WHILE sortSeq[j].shape #
NIL
DO
action[sortSeq[j]]; -- call back with next polygon in order
j ← sortSeq[j].next;
IF j = 0 THEN EXIT;
ENDLOOP;
ENDLOOP;
CombineBoxes[context]; -- get combined bounding box on scene
};
DoFrontToBack:
PUBLIC
PROC[ context:
REF ThreeDScenes.Context,
sortSeq:
REF ThreeDPolygons.SortSequence,
action:
PROC[ThreeDPolygons.ShapePolygon] ] ~ {
ThreeDScenes.FillViewPort[context, [0.0,0.0,0.0] ]; -- clear screen and alpha buffer
FOR i:
NAT
IN [0..context.depthResolution)
DO
j: NAT ← i;
WHILE sortSeq[j].shape #
NIL
DO
action[sortSeq[j]]; -- call back with next polygon in order
j ← sortSeq[j].next;
IF j = 0 THEN EXIT;
ENDLOOP;
ENDLOOP;
CombineBoxes[context]; -- get combined bounding box on scene
ThreeDScenes.FillInBackGround[context];
};
DoForPolygons:
PUBLIC
PROC[ set:
REF ThreeDScenes.ShapeSequence,
action1:
PROC[ThreeDPolygons.ShapePolygon],
action2:
PROC[
REF ThreeDScenes.ShapeInstance] ←
NIL ] ~ {
FOR s:
NAT
IN [0..set.length)
DO
IF set[s].clipState = in AND action2 # NIL THEN action2[set[s]]
ELSE IF set[s].clipState # out
AND set[s].surface #
NIL
THEN {
poly: REF ThreeDPolygons.PtrPolySequence ← NARROW[set[s].surface];
FOR i:
NAT
IN [0..set[s].numSurfaces)
DO
IF set[s].clipState = in
THEN poly[i].clipState ← in -- unclipped, inside
ELSE
IF set[s].clipState = clipped
THEN {
-- clipped, evaluate clipping tags
orOfCodes: ThreeDScenes.OutCode ← ThreeDScenes.NoneOut;
andOfCodes: ThreeDScenes.OutCode ← ThreeDScenes.AllOut;
FOR j:
NAT
IN [0..poly[i].nVtces)
DO
k: NAT ← poly[i].vtxPtr[j];
orOfCodes ←
LOOPHOLE[
Basics.BITOR[ LOOPHOLE[orOfCodes], LOOPHOLE[set[s].vertex[k].clip] ],
ThreeDScenes.OutCode];
andOfCodes ←
LOOPHOLE[
Basics.BITAND[LOOPHOLE[andOfCodes], LOOPHOLE[set[s].vertex[k].clip]],
ThreeDScenes.OutCode];
ENDLOOP;
IF andOfCodes # ThreeDScenes.NoneOut THEN poly[i].clipState ← out
ELSE IF orOfCodes = ThreeDScenes.NoneOut THEN poly[i].clipState ← in
ELSE poly[i].clipState ← clipped;
};
IF poly[i].clipState # out THEN action1[ [set[s], i, 0] ];
ENDLOOP;
};
ENDLOOP;
};
ShowObjects:
PUBLIC
PROC[ context:
REF ThreeDScenes.Context, frontToBack:
BOOLEAN ←
FALSE ] ~ {
ShowPolygon:
PROC[p: ThreeDPolygons.ShapePolygon] ~{
OutputPoly[ context, p ];
};
shape: REF ThreeDScenes.ShapeSequence ← context.shapes;
sortSeq:
REF ThreeDPolygons.SortSequence;
Get Everything (including light centroids) into eyespace
FOR i:
NAT
IN [0.. shape.length)
DO
IF shape[i].vtcesInValid
THEN {
shape[i].clipState ← ThreeDScenes.XfmToEyeSpace[ context, shape[i] ];
IF shape[i].clipState # out THEN ThreeDScenes.XfmToDisplay[context, shape[i] ];
};
ENDLOOP;
FOR i:
NAT
IN [0.. shape.length)
DO
-- now, get everything shaded
IF shape[i].shadingInValid
AND (shape[i].clipState # out)
THEN {
IF shape[i].shade = NIL THEN GetPolyNormals[shape[i]]; -- makes default faceted
IF ThreeDScenes.GetShading[ shape[i], $Type ] = $Faceted
THEN GetShades[ context, shape[i] ]
ELSE ThreeDScenes.GetVtxShades[ context, shape[i] ];
};
ENDLOOP;
sortSeq ← LoadSortSequence[context];
IF frontToBack THEN DoFrontToBack[context, sortSeq, ShowPolygon]
ELSE DoBackToFront[context, sortSeq, ShowPolygon];
};
ShowWireFrameObjects:
PUBLIC
PROC[context:
REF ThreeDScenes.Context ] ~ {
ShowPolygon:
PROC[p: ThreeDPolygons.ShapePolygon] ~{
OutputPlygnLines[ context, p ];
};
ShowShape:
PROC[s:
REF ThreeDScenes.ShapeInstance] ~{
OutputShapeLines[ context, s ];
};
shape: REF ThreeDScenes.ShapeSequence ← context.shapes;
FOR i:
NAT
IN [0.. shape.length)
DO
IF shape[i].vtcesInValid
THEN {
shape[i].clipState ← ThreeDScenes.XfmToEyeSpace[ context, shape[i] ];
IF shape[i].clipState # out THEN ThreeDScenes.XfmToDisplay[context, shape[i] ];
};
ENDLOOP;
ThreeDScenes.FillInBackGround[context];
IF context.renderMode = $LF
OR context.renderMode = $Dithered
THEN ThreeDMisc.SetNamedColor[context, "White" ];
DoForPolygons[context.shapes, ShowPolygon, ShowShape];
CombineBoxes[context]; -- get combined bounding box on scene
};
OutputShapeLines:
PUBLIC
PROC[context:
REF ThreeDScenes.Context,
s:
REF ThreeDScenes.ShapeInstance] ~ {
Unclipped shape output
ax, ay, bx, by: NAT;
color: SampleSet ← ShapetoColorBytes[context, s];
imagerCtx: Imager.Context;
usingImager: BOOLEAN ← FALSE;
polygons: REF ThreeDPolygons.PtrPolySequence;
IF s.surface = NIL THEN RETURN;
IF context.renderMode = $LF
OR context.renderMode = $Dithered
THEN {
usingImager ← TRUE;
imagerCtx ← ThreeDMisc.GetImagerContext[context];
};
polygons ← NARROW[s.surface, REF ThreeDPolygons.PtrPolySequence];
FOR i:
NAT
IN [0..s.numSurfaces)
DO
FOR j:
NAT
IN [0..polygons[i].nVtces]
DO
k: NAT ← IF j = polygons[i].nVtces THEN 0 ELSE j;
bx ← Real.RoundC[s.vertex[polygons[i].vtxPtr[k]].sx];
by ← Real.RoundC[s.vertex[polygons[i].vtxPtr[k]].sy];
IF j > 0
THEN
IF
NOT usingImager
THEN ScanConvert.PutLine[ context.display, [ax,ay], [bx,by], color ]
ELSE Imager.MaskVectorI[ imagerCtx, ax, ay, bx, by ];
ax ← bx; ay ← by;
ENDLOOP;
IF stopMe THEN HoldEverything[]; -- shut down if stop signal received
ENDLOOP;
};
OutputPlygnLines:
PUBLIC
PROC[context:
REF ThreeDScenes.Context,
p: ThreeDPolygons.ShapePolygon] ~ {
poly: REF ThreeDPolygons.PtrPoly ←
NARROW[p.shape.surface, REF ThreeDPolygons.PtrPolySequence][p.polygon];
vertex: REF ThreeDScenes.VertexSequence ← p.shape.vertex;
color: SampleSet ← ShapetoColorBytes[context, p.shape];
imagerCtx: Imager.Context;
usingImager: BOOLEAN ← FALSE;
IF poly.clipState = out THEN RETURN[]; -- reject if outside frame
IF context.renderMode = $LF
OR context.renderMode = $Dithered
THEN {
usingImager ← TRUE;
imagerCtx ← ThreeDMisc.GetImagerContext[context];
};
IF poly.clipState = in
THEN {
ax, ay, bx, by: NAT;
FOR j:
NAT
IN [0..poly.nVtces]
DO
i: NAT ← IF j = poly.nVtces THEN 0 ELSE j;
bx ← Real.RoundC[vertex[poly.vtxPtr[i]].sx];
by ← Real.RoundC[vertex[poly.vtxPtr[i]].sy];
IF j > 0
THEN
IF
NOT usingImager
THEN ScanConvert.PutLine[ context.display, [ax,ay], [bx,by], color ]
ELSE Imager.MaskVectorI[ imagerCtx, ax, ay, bx, by ];
ax ← bx; ay ← by;
ENDLOOP;
}
ELSE
IF poly.clipState = clipped
THEN {
IF (tempPoly =
NIL)
OR (tempPoly.length < 2 * poly.nVtces)
THEN {
tempPoly ← NEW[Polygon[2 * poly.nVtces] ];
tempPoly2 ← NEW[Polygon[2 * poly.nVtces] ];
};
tempPoly.nVtces ← poly.nVtces;
FOR i:
NAT
IN [0..poly.nVtces)
DO
tempPoly.vtx[i].coord ← p.shape.vertex[poly.vtxPtr[i]];
ENDLOOP;
[tempPoly, tempPoly2] ← ClipPoly[ context, p.shape, tempPoly, tempPoly2 ];
IF tempPoly.nVtces > 2
THEN {
ax, ay, bx, by: NAT;
FOR j:
NAT
IN [0..tempPoly.nVtces]
DO
i: NAT ← IF j = tempPoly.nVtces THEN 0 ELSE j;
x, y, z: REAL;
[[x, y, z]] ← ThreeDScenes.XfmPtToDisplay[
context,
[tempPoly.vtx[i].coord.ex, tempPoly.vtx[i].coord.ey, tempPoly.vtx[i].coord.ez]
];
bx ← Real.RoundC[x]; by ← Real.RoundC[y];
IF j > 0
THEN
IF
NOT usingImager
THEN ScanConvert.PutLine[ context.display, [ax,ay], [bx,by], color ]
ELSE Imager.MaskVectorI[ imagerCtx, ax, ay, bx, by ];
ax ← bx; ay ← by;
ENDLOOP;
};
};
IF stopMe THEN HoldEverything[]; -- shut down if stop signal received
};
OutputPoly:
PUBLIC
PROC[context:
REF ThreeDScenes.Context,
p: ThreeDPolygons.ShapePolygon] ~ {
poly: REF ThreeDPolygons.PtrPoly ←
NARROW[p.shape.surface, REF ThreeDPolygons.PtrPolySequence][p.polygon];
vertex: REF ThreeDScenes.VertexSequence ← p.shape.vertex;
shade: REF ThreeDScenes.ShadingSequence ← p.shape.shade;
shading: ATOM ← NARROW[ ThreeDScenes.GetShading[ p.shape, $Type ] ];
faceted: BOOLEAN ← shading = $Faceted;
IF poly.clipState = out THEN RETURN[]; -- reject if outside frame
IF (tempPoly =
NIL)
OR (tempPoly.length < 2 * poly.nVtces)
THEN {
tempPoly ← NEW[Polygon[2 * poly.nVtces] ];
tempPoly2 ← NEW[Polygon[2 * poly.nVtces] ];
};
tempPoly.nVtces ← poly.nVtces;
FOR i:
NAT
IN [0..poly.nVtces)
DO
j: NAT ← poly.vtxPtr[i];
k: NAT ← IF faceted THEN p.polygon ELSE j; -- shades go with polygons when faceted
tempPoly.vtx[i].coord ← vertex[j];
tempPoly.vtx[i].shade ← shade[k];
ENDLOOP;
IF BackFacing[tempPoly]
THEN
IF p.shape.type = $Polyhedron
-- backfacing poly!!
THEN RETURN[] -- Reject if closed surface
ELSE {
FOR i:
NAT
IN [0..tempPoly.nVtces)
DO
-- recalculate shading for back side
r, g, b, t: REAL;
tempPoly.vtx[i].shade.exn ← -tempPoly.vtx[i].shade.exn; -- reverse normals
tempPoly.vtx[i].shade.eyn ← -tempPoly.vtx[i].shade.eyn;
tempPoly.vtx[i].shade.ezn ← -tempPoly.vtx[i].shade.ezn;
[[r,g,b], t] ← ThreeDScenes.ShadePt[ context, tempPoly.vtx[i], 0.0 ];
tempPoly.vtx[i].shade.ir ← Real.FixC[r * 255.0];
tempPoly.vtx[i].shade.ig ← Real.FixC[g * 255.0];
tempPoly.vtx[i].shade.ib ← Real.FixC[b * 255.0];
tempPoly.vtx[i].shade.it ← Real.FixC[ t * 255.0];
ENDLOOP;
FOR i:
NAT
IN [0..tempPoly.nVtces/2)
DO
-- reorder to keep clockwise on display
tempVtx: ThreeDScenes.VertexInfo ← tempPoly.vtx[i];
tempPoly.vtx[i] ← tempPoly.vtx[tempPoly.nVtces-1 - i];
tempPoly.vtx[tempPoly.nVtces-1 - i] ← tempVtx;
ENDLOOP;
};
IF poly.clipState = clipped
THEN {
[tempPoly, tempPoly2] ← ClipPoly[context, p.shape, tempPoly, tempPoly2];
FOR i:
NAT
IN [0..tempPoly.nVtces)
DO OPEN tempPoly.vtx[i].coord;
[[sx, sy, sz]] ← ThreeDScenes.XfmPtToDisplay[context, [ex, ey, ez]];
ENDLOOP;
};
IF tempPoly.nVtces > 2
THEN {
tempPoly.props ← p.shape.shadingProps; -- transmit shading info
Tilers.PolygonTiler[context, shading, tempPoly];
};
IF stopMe THEN HoldEverything[]; -- shut down if stop signal received
};