[Indigo]<3DGraphics>NewThreeDRender>SurfaceRenderImpl.mesa!5

SurfaceRenderImpl.mesa

Last Edited by: Crow, April 11, 1989 11:35:35 am PDT

Bloomenthal, September 26, 1988 12:04:48 pm PDT

DIRECTORY

Atom USING [ GetPropFromList, PutPropOnList, PropList ],

Real USING [ Round, Fix, MinusInfinity, PlusInfinity ],

RealFns USING [ CosDeg, SinDeg, SqRt, TanDeg ],

Basics USING [ BITOR, BITAND ],

BasicTime USING [ PulsesToSeconds, GetClockPulses ],

IO USING [ Flush, PutRope, STREAM ],

Rope USING [ ROPE, Cat ],

Convert USING [ RopeFromReal, RopeFromInt ],

Process USING [ PauseMsec ],

CedarProcess USING [ DoWithPriority ],

ImagerSample USING [ Clip, GetBox, SampleMap ],

ImagerPixel USING [ MakePixelMap, PixelMap ],

ScanConvert USING [ justNoticeable ],

G3dVector USING [ Add, Cross, Div, Dot, Length, Mul, Normalize, Null, Sub ],

G3dMatrix USING [ Identity, Mul, TransformVec ],

G3dPlane USING [ Error, FromThreePoints ],

G3dRender USING [ AllOut,Box, BoxFromRectangle, ClipState, Context, ContextProc,
Error, FacingDir, IntegerSequence,
IntersectRectangles, IntegerPair, LoadShadingClass,
LoadSurfaceType, NatSequence, NoneOut, OutCode, Pair, Patch,
PatchProc, PatchSequence, Pixel, PtrPatchSequence, PtrPatch,
Quad, RealSequence, Rectangle, RectangleFromBox, RGB,
SetPosition, SetView, ShadingClass, ShadingSequence,
ShadingValue, ShapeInstance, ShapeSequence, ShapeProc,
SixSides, Triple, TripleSequence, Vertex, VertexInfo,
VertexInfoProc, VertexInfoSequence, VertexSequence, Xfm3D ],

ShapeUtilities USING [ BackFacing, ClipPoly, GetPatch, GetPolyShades, GetVtxNmls,
GetVtxShades, ReleasePatch, ShapePatch, ShapePatchToPatch,
SortSequence, XfmPtToDisplay, XfmToDisplay, XfmToEyeSpace],

SurfaceRender USING [ ];

SurfaceRenderImpl: CEDAR MONITOR

IMPORTS Atom, Basics, BasicTime, CedarProcess, Convert, ImagerPixel, IO, G3dMatrix, G3dPlane, G3dVector, Real, RealFns, Rope, ImagerSample, Process, ShapeUtilities, G3dRender

EXPORTS SurfaceRender

~ BEGIN

Internal Declarations

Context: TYPE ~ G3dRender.Context;

ContextProc: TYPE ~ G3dRender.ContextProc;

RGB: TYPE ~ G3dRender.RGB; -- [ r, g, b: REAL];

Pixel: TYPE ~ G3dRender.Pixel;

IntegerPair: TYPE ~ G3dRender.IntegerPair;

Pair: TYPE ~ G3dRender.Pair;

Box: TYPE ~ G3dRender.Box;

Rectangle: TYPE ~ G3dRender.Rectangle;

SixSides: TYPE ~ G3dRender.SixSides;

OutCode: TYPE ~ G3dRender.OutCode;

NoneOut: OutCode ~ G3dRender.NoneOut;

AllOut: OutCode ~ G3dRender.AllOut;

Triple: TYPE ~ G3dRender.Triple;

Quad: TYPE ~ G3dRender.Quad;

TripleSequence: TYPE ~ G3dRender.TripleSequence;

NatSequence: TYPE ~ G3dRender.NatSequence;

IntegerSequence: TYPE ~ G3dRender.IntegerSequence;

RealSequence: TYPE ~ G3dRender.RealSequence;

ShapeInstance: TYPE ~ G3dRender.ShapeInstance;

ShapeSequence: TYPE ~ G3dRender.ShapeSequence;

FacingDir: TYPE ~ G3dRender.FacingDir;

Patch: TYPE ~ G3dRender.Patch;

PatchProc: TYPE ~ G3dRender.PatchProc;

PatchSequence: TYPE ~ G3dRender.PatchSequence;

PtrPatch: TYPE ~ G3dRender.PtrPatch;

PtrPatchSequence: TYPE ~ G3dRender.PtrPatchSequence;

ShapePatch: TYPE ~ ShapeUtilities.ShapePatch;

SortSequence: TYPE ~ ShapeUtilities.SortSequence;

Vertex: TYPE ~ G3dRender.Vertex;

VertexSequence: TYPE ~ G3dRender.VertexSequence;

VertexInfo: TYPE ~ G3dRender.VertexInfo;

VertexInfoProc: TYPE ~ G3dRender.VertexInfoProc;

VertexInfoSequence: TYPE ~ G3dRender.VertexInfoSequence;

ShadingValue: TYPE ~ G3dRender.ShadingValue;

ShadingSequence: TYPE ~ G3dRender.ShadingSequence;

Xfm3D: TYPE ~ G3dRender.Xfm3D;

Order: TYPE ~ {inFront, behind, coincident, intersects};

Bounds: TYPE ~ RECORD[left, right, bottom, top, near, far: REAL];

BoundsSequence: TYPE ~ RECORD[SEQUENCE length: NAT OF Bounds];

RenderData: TYPE ~ G3dRender.RenderData;

ShadingClass: TYPE ~ G3dRender.ShadingClass;

ShapeProc: TYPE ~ G3dRender.ShapeProc; -- PROC[ Context, ShapeInstance ]

defaultWhite: REF RGB ← NEW[ RGB ← [1.0, 1.0, 1.0] ]; -- default color

debug: BOOLEAN ← FALSE;

Renamed Procedures

GetProp: PROC [propList: Atom.PropList, prop: REF ANY] RETURNS [REF ANY] ~
Atom.GetPropFromList;

PutProp: PROC [propList: Atom.PropList, prop: REF ANY, val: REF ANY]
RETURNS [Atom.PropList] ~ Atom.PutPropOnList;

Global Variables

nullPtr: INT ~ 0; -- handy name for zero in sort sequences

progressReportsPerFrame: INT ← 0; -- set to non zero for progress reports on long frames

Utility Procedures

Sqr: PROCEDURE [number: REAL] RETURNS [REAL] ~ INLINE { RETURN[number * number]; };

ElapsedTime: PROC[startTime: REAL] RETURNS[Rope.ROPE] ~ {

timeX100: REAL ← 100.0 * (CurrentTime[] - startTime);

RETURN[ Rope.Cat[ Convert.RopeFromReal[ Real.Fix[timeX100] / 100.0 ], "s," ] ];

};

CurrentTime: PROC[] RETURNS[REAL] ~ {

RETURN[ BasicTime.PulsesToSeconds[BasicTime.GetClockPulses[]] ];

};

GetPtrPatchClipState: PUBLIC PROC[ shape: REF ShapeInstance, patch: REF PtrPatch] ~ {

orOfCodes: OutCode ← NoneOut;

andOfCodes: OutCode ← AllOut;

FOR j: NAT IN [0..patch.nVtces) DO

k: NAT ← patch.vtxPtr[j];

orOfCodes ← LOOPHOLE[

Basics.BITOR[ LOOPHOLE[orOfCodes], LOOPHOLE[shape.vertex[k].clip]],

OutCode];

andOfCodes ← LOOPHOLE[

Basics.BITAND[LOOPHOLE[andOfCodes], LOOPHOLE[shape.vertex[k].clip]],

OutCode];

ENDLOOP;

IF andOfCodes # NoneOut

THEN patch.clipState ← out

ELSE IF orOfCodes = NoneOut

THEN patch.clipState ← in

ELSE patch.clipState ← clipped;

};

FlushLog: PUBLIC PROC [context: REF Context] ~ {

log: IO.STREAM ← NARROW[Atom.GetPropFromList[context.props, $Log]];

IF log # NIL THEN IO.Flush[log];

};

Procedures for Updating Context

ValidateContext: PUBLIC PROC[ context: REF Context ] ~ {

j: CARDINAL ← 0;

IF context.viewer = NIL AND context.pixels = NIL AND context.viewPort = NIL

THEN SIGNAL G3dRender.Error[[$Fatal, "Image Area Undefined"]];

IF context.class = NIL THEN Process.PauseMsec[3000]; -- wait 3s. (maybe viewers settling)

IF context.class = NIL THEN G3dRender.Error[[$Fatal, "No Class for Context"]];

IF context.viewer # NIL AND context.viewPort = NIL

AND (context.pixels = NIL OR context.pixels.samplesPerPixel = 1)

THEN context.class.updateViewer[context];

IF context.viewPort = NIL AND context.pixels # NIL

THEN { ValidateView[context]; ValidateDisplay[context]; }

ELSE { ValidateDisplay[context]; ValidateView[context]; };

IF context.shapes # NIL THEN { -- get light sources and visible shapes (convenience)

IF context.lightSources = NIL OR context.lightSources.length < context.shapes.length

THEN context.lightSources ← NEW[ ShapeSequence[context.shapes.length] ];

FOR i: NAT IN [0..context.shapes.length) DO

IF context.shapes[i].class = NIL

THEN G3dRender.LoadSurfaceType[context.shapes[i], $ConvexPolygon]; -- default

IF context.shapes[i].class.type = $Light

THEN { context.lightSources[j] ← context.shapes[i]; j ← j + 1; };

ENDLOOP;

context.lightSources.length ← j;

j ← 0;

IF context.visibleShapes = NIL OR context.visibleShapes.length < context.shapes.length

THEN context.visibleShapes ← NEW[ ShapeSequence[context.shapes.length] ];

FOR i: NAT IN [0..context.shapes.length) DO

shape: REF ShapeInstance ← ValidateShape[context, context.shapes[i]];

IF shape # NIL THEN { context.visibleShapes[j] ← shape; j ← j + 1; };

ENDLOOP;

context.visibleShapes.length ← j;

};

ValidateDisplay: PUBLIC PROC[ context: REF Context ] ~ {

This eventually assumes that context.viewPort # NIL

IF context.displayInValid THEN {

context.class.validateDisplay[context];

IF context.shapes # NIL THEN FOR i: NAT IN [0..context.shapes.length) DO

context.shapes[i].vtcesInValid ← TRUE;

context.shapes[i].shadingInValid ← TRUE;

ENDLOOP;

G3dRender.SetView[ -- get new screen dimensions into transformations

context: context,

eyePoint: context.eyePoint,

ptOfInterest: context.ptOfInterest,

fieldOfView: context.fieldOfView,

rollAngle: context.rollAngle,

upDirection: context.upDirection,

hitherLimit: context.hitherLimit,

yonLimit: context.yonLimit

];

IF context.window = NIL

THEN context.window ← WindowFromViewPort[context]; -- fit to viewprt

};

context.extentCovered ← [[0,0], [0,0]]; -- clear coverage (new frame, alpha buffer, or display)

context.displayInValid ← FALSE;

};

ValidateView: PUBLIC PROC[ context: REF Context ] ~ {

IF context.viewPort = NIL THEN { -- evidently not using a viewer

s: ARRAY [0..5) OF ImagerSample.SampleMap ← ALL[NIL];

pixels: ImagerPixel.PixelMap ← NARROW[

Atom.GetPropFromList[ context.displayProps, $FullDisplayMemory ]

];

IF pixels # NIL

THEN context.pixels ← pixels

ELSE IF context.pixels = NIL

THEN SIGNAL G3dRender.Error[[$MisMatch, "no pixel memory"]];

context.viewPort ← NEW[

Rectangle ← G3dRender.RectangleFromBox[ ImagerSample.GetBox[context.pixels[0]] ]

];

context.viewPort^ ← G3dRender.IntersectRectangles[

context.viewPort^, context.preferredViewPort -- clip viewPort to preferredViewPort

];

context.ndcToPixels ← [ -- going to VM so render with origin at top left

context.viewPort.w-1.0, -(context.viewPort.h-1.0), REAL[context.depthResolution-1],

0.0, context.viewPort.h-1.0, 0.0 -- last line scales, this line adds

];

FOR i: NAT IN [0..context.pixels.samplesPerPixel) DO -- re-address pixelmap

s[i] ← ImagerSample.Clip[ context.pixels[i],
G3dRender.BoxFromRectangle[context.viewPort^] ];

ENDLOOP;

context.pixels ← ImagerPixel.MakePixelMap[s[0], s[1], s[2], s[3], s[4]];

};

IF context.window = NIL THEN {

context.window ← WindowFromViewPort[context];

context.viewInValid ← TRUE;

};

IF context.viewInValid

THEN SetView[ context, context.eyePoint, context.ptOfInterest,
context.fieldOfView,
context.rollAngle, context.upDirection,
context.hitherLimit, context.yonLimit ];

context.viewInValid ← FALSE;

IF context.pixels # NIL -- check for mismatched viewPort and pixel storage

THEN IF context.pixels.box.max.f < context.viewPort.w

OR context.pixels.box.max.s < context.viewPort.h

THEN SIGNAL G3dRender.Error[[$MisMatch, "pixel memory smaller than viewport"]];

};

ValidateShape: PUBLIC ShapeProc ~ {

PROC[context: REF Context, shape: REF ShapeInstance, data: REF] RETURNS[REF ShapeInstance];

Update shading and transform matrices, return visibility (based on clipping and "hidden")

render: REF RenderData ← NARROW[shape.renderData];

IF context.stopMe^ THEN RETURN[shape];

IF shape.shadingClass = NIL THEN G3dRender.LoadShadingClass[shape]; -- load default

IF Atom.GetPropFromList[shape.props, $Hidden] # NIL AND shape.class.type # $Light

THEN RETURN[NIL]; -- not visible, removed from scene temporarily

IF shape.positionInValid THEN G3dRender.SetPosition[ shape ];

IF shape.boundingRadius = 0.0 THEN GetBoundingSphere[ shape ];

IF shape.vtcesInValid THEN { -- do only if object or eyespace transform has moved

Transform vertices to eyespace, get clip state of vertices and whole shape

shape.clipState ← ShapeUtilities.XfmToEyeSpace[ context, shape ];

};

IF shape.class.validate # NIL

THEN [] ← shape.class.validate[context, shape, data]; -- get shading, etc.

IF shape.clipState # out THEN {

Transform vertices to screen coordinates, get screen extent for whole shape

ShapeUtilities.XfmToDisplay[context, shape ];

};

IF shape.clipState # out AND shape.surface # NIL THEN RETURN[shape] ELSE RETURN[NIL];

};

ValidatePolyhedron: PUBLIC ShapeProc ~ {

PROC[context: REF Context, shape: REF ShapeInstance, data: REF] RETURNS[REF ShapeInstance];

Update shading and transform matrices

doAlways: BOOLEAN ← IF data # NIL THEN TRUE ELSE FALSE;

xfm: Xfm3D ← G3dMatrix.Mul[shape.position, context.eyeSpaceXfm];

IF GetProp[ shape.shadingProps, $VtxInfoComputed] = NIL

THEN ShapeUtilities.GetVtxNmls[context, shape];

IF shape.vtcesInValid AND (shape.clipState # out OR doAlways) THEN {

IF shape.shade # NIL THEN FOR i: NAT IN [0..shape.shade.length) DO

OPEN shape.shade[i]; -- transform normal vectors for shading, backfacing test

[ [exn, eyn, ezn] ] ← G3dMatrix.TransformVec[ [xn, yn, zn] , xfm];

ENDLOOP;

IF shape.surface # NIL THEN { -- get clipping info for patches

patch: REF PtrPatchSequence ← NARROW[shape.surface];

FOR i: NAT IN [0..shape.numSurfaces) DO

IF patch[i] # NIL

THEN IF shape.clipState = in

THEN patch[i].clipState ← in -- unclipped, inside

ELSE IF shape.clipState = clipped

THEN GetPtrPatchClipState[ shape, patch[i] ] -- evaluate clipping tags

ELSE patch[i].clipState ← out;

ENDLOOP;

};

IF shape.shadingInValid AND (shape.clipState # out OR doAlways) THEN {

shadingType: REF ANY ← shape.shadingClass.shadingType;

SELECT shadingType FROM

$Faceted => {

polyShade: REF ShadingSequence;

IF GetProp[shape.shadingProps, $PolygonInfoComputed] = NIL

THEN ShapeUtilities.GetPolyShades[ context, shape ]; -- get data structure for facets

polyShade ← shape.shadingClass.patchShade;

IF shape.vtcesInValid THEN FOR i: NAT IN [0..polyShade.length) DO

IF polyShade[i] # NIL THEN {

OPEN polyShade[i]; -- transform normal vectors

[ [exn, eyn, ezn] ] ← G3dMatrix.TransformVec[ [xn, yn, zn] , xfm];

};

ENDLOOP;

ShapeUtilities.GetPolyShades[ context, shape ]; -- shade polygons (2nd call sometimes)

};

$Smooth, $ShadedLines => ShapeUtilities.GetVtxShades[ context, shape ]; -- shade vtces

$Lines, $HiddenLines, $NormaledLines => IF context.antiAliasing

THEN ShapeUtilities.GetVtxShades[ context, shape ];

NIL => {}; -- For lights, this is a little shaky, what does no shading mean??!!

ENDCASE => WITH shadingType SELECT FROM

shadingProc: REF ShapeProc => [] ← shadingProc[ context, shape ]; -- supplied proc

ENDCASE => G3dRender.Error[[$MisMatch, "Unknown Shading Type"]];

shape.shadingInValid ← FALSE;

};

shape.vtcesInValid ← FALSE;

RETURN[shape];

};

ValidateRopeShape: PUBLIC ShapeProc ~ {

PROC[context: REF Context, shape: REF ShapeInstance, data: REF] RETURNS[REF ShapeInstance];

Update shading and transform matrices

shape.shadingInValid ← FALSE;

shape.vtcesInValid ← FALSE;

RETURN[shape];

};

GetBoundingSphere: PUBLIC PROC[shape: REF ShapeInstance] ~ {

Find approximation to bounding sphere

{ min, max: Triple;

min ← max ← [shape.vertex[0].x, shape.vertex[0].y, shape.vertex[0].z];

FOR i: NAT IN (0..shape.vertex.length) DO -- get min and max in x, y, and z

IF shape.vertex[i] # NIL THEN {

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].z > 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..shape.vertex.length) DO -- find radius

radius: REAL ← 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;

};

SetView: PUBLIC PROC[context: REF Context, eyePoint, ptOfInterest: Triple,
fieldOfView: REAL �.0,
rollAngle: REAL ← 0.0, upDirection: Triple ← [ 0., 0., 1.],
hitherLimit: REAL ← .01, yonLimit: REAL ← 1000.0] ~ {

context.eyePoint ← eyePoint;

context.ptOfInterest ← ptOfInterest;

context.fieldOfView ← fieldOfView;

context.rollAngle ← rollAngle;

context.upDirection ← upDirection;

context.hitherLimit ← hitherLimit;

context.yonLimit ← yonLimit;

SetEyeSpace[ context ];

IF context.shapes # NIL THEN FOR i: NAT IN [0..context.shapes.length) DO

context.shapes[i].vtcesInValid ← TRUE; -- eyespace and image space will change

IF context.shapes[i].shadingClass.shininess > 0.0

OR context.shapes[i].shadingClass.transmittance > 0.0

THEN context.shapes[i].shadingInValid ← TRUE; -- highlights and trans. will change

ENDLOOP;

};

SetEyeSpace: PUBLIC PROC[ context: REF Context ] ~ {

in, right, up, normal: Triple;

mtx: Xfm3D;

wndw: Rectangle;

viewSize, xSize, ySize, aspectRatio: REAL;

IF context.viewPort.h <= 0 OR context.viewPort.w <= 0 THEN RETURN[];

transform from world to eye

in ← G3dVector.Normalize[G3dVector.Sub[context.ptOfInterest, context.eyePoint]];

IF G3dVector.Null[in] THEN

SIGNAL G3dRender.Error[[$MisMatch, "Eye and Pt of Interest identical"]];

right ← G3dVector.Normalize[G3dVector.Cross[in, context.upDirection]];

IF G3dVector.Null[right] THEN right ← [1.0, 0.0, 0.0]; -- looking straight down

up ← G3dVector.Normalize[G3dVector.Cross[right, in]];

normalize not really needed (to avoid roundoff problems)

context.eyeSpaceXfm ← G3dMatrix.Identity[];

context.eyeSpaceXfm[0][0] ← right.x;

context.eyeSpaceXfm[1][0] ← right.y;

context.eyeSpaceXfm[2][0] ← right.z;

context.eyeSpaceXfm[3][0] ← -G3dVector.Dot[right, context.eyePoint];

context.eyeSpaceXfm[0][1] ← up.x;

context.eyeSpaceXfm[1][1] ← up.y;

context.eyeSpaceXfm[2][1] ← up.z;

context.eyeSpaceXfm[3][1] ← -G3dVector.Dot[up, context.eyePoint];

context.eyeSpaceXfm[0][2] ← in.x;

context.eyeSpaceXfm[1][2] ← in.y;

context.eyeSpaceXfm[2][2] ← in.z;

context.eyeSpaceXfm[3][2] ← -G3dVector.Dot[in, context.eyePoint];

mtx ← G3dMatrix.Identity[]; -- Roll about z-axis, clockwise

mtx[0][0] ← RealFns.CosDeg[context.rollAngle];

mtx[0][1] ← -RealFns.SinDeg[context.rollAngle];

mtx[1][0] ← RealFns.SinDeg[context.rollAngle];

mtx[1][1] ← RealFns.CosDeg[context.rollAngle];

context.eyeSpaceXfm ← G3dMatrix.Mul[context.eyeSpaceXfm, mtx];

bound window by -1.0 < x, y < 1.0

IF NOT (context.window.w > 0.0 AND context.window.h > 0.0) THEN RETURN[];

aspectRatio ← context.pixelAspectRatio * (context.viewPort.w/context.viewPort.h);

xSize ← IF aspectRatio > 1.0 THEN 1.0 ELSE aspectRatio;

ySize ← IF aspectRatio < 1.0 THEN 1.0 ELSE 1.0 / aspectRatio;

wndw.x ← MIN[xSize, MAX[-xSize, context.window.x] ];

wndw.w ← MIN[xSize-wndw.x, context.window.w ];

wndw.y ← MIN[ySize, MAX[-ySize, context.window.y] ];

wndw.h ← MIN[ySize-wndw.y, context.window.h ];

viewSize ← 2.0*RealFns.TanDeg[context.fieldOfView/2.0]; -- scale factor for angle of view

generate clipping planes

context.clippingPlanes[Near] ← [0., 0., 1., -context.hitherLimit];

context.clippingPlanes[Far] ← [0., 0., -1., context.yonLimit];

normalize plane equation for true distances

normal ← G3dVector.Normalize[[1., 0., -(wndw.x * viewSize/2.)]];

context.clippingPlanes[Left] ← [normal.x, 0., normal.z, 0.];

normal ← G3dVector.Normalize[[-1., 0., (wndw.x + wndw.w) * viewSize/2.]];

context.clippingPlanes[Right] ← [normal.x, 0., normal.z, 0.];

normal ← G3dVector.Normalize[[0., 1., -(wndw.y * viewSize/2.)]];

context.clippingPlanes[Bottom] ← [0., normal.y, normal.z, 0.];

normal ← G3dVector.Normalize[[0., -1., (wndw.y + wndw.h) * viewSize/2.]];

context.clippingPlanes[Top] ← [0., normal.y, normal.z, 0.];

compute the transformation from the eye coord sys to normalized display coordinates (0.—1.)

context.eyeToNdc.addX ← -(wndw.x / wndw.w);

context.eyeToNdc.addY ← -(wndw.y / wndw.h);

context.eyeToNdc.addZ ← 1.0/(1.0 - context.hitherLimit/context.yonLimit);

context.eyeToNdc.scaleX ← 1.0/(wndw.w * viewSize / 2.0);

context.eyeToNdc.scaleY ← 1.0/(wndw.h * viewSize / 2.0);

context.eyeToNdc.scaleZ ← -context.hitherLimit/(1. - context.hitherLimit/context.yonLimit);

};

WindowFromViewPort: PUBLIC PROC[context: REF Context]
RETURNS[REF Rectangle] ~ {

Fits window to shape of viewport

window: REF Rectangle ← NEW[Rectangle];

vp: Rectangle;

IF context.viewPort = NIL OR context.viewPort.h <= 0.0 OR context.viewPort.w <= 0.0

THEN RETURN[ NIL ];

vp ← [ context.viewPort.x * context.pixelAspectRatio, context.viewPort.y,
context.viewPort.w * context.pixelAspectRatio, context.viewPort.h ];

IF vp.w > vp.h

THEN {

window.x ← -1.0; window.w ← 2.0;

window.y ← -vp.h / vp.w; window.h ← 2.0 * vp.h / vp.w;

}

ELSE {

window.y ← -1.0; window.h ← 2.0;

window.x ← -vp.w / vp.h; window.w ← 2.0 * vp.w / vp.h;

};

RETURN[ window ];

};

Procedures for Sorting

GetBounds: PROC[patch: REF PtrPatch, shape: REF ShapeInstance] RETURNS[pBnds: Bounds] ~ {

Get bounding box for patch

pBnds.near ← pBnds.far ← shape.vertex[patch.vtxPtr[0]].ez;

pBnds.left ← pBnds.right ← shape.vertex[patch.vtxPtr[0]].sx;

pBnds.bottom ← pBnds.top ← shape.vertex[patch.vtxPtr[0]].sy;

FOR j: NAT IN [1..patch.nVtces) DO -- get bounds in depth, on display

pBnds.near ← MIN[pBnds.near, shape.vertex[patch.vtxPtr[j]].ez];

pBnds.far ← MAX[pBnds.far, shape.vertex[patch.vtxPtr[j]].ez];

pBnds.left ← MIN[pBnds.left, shape.vertex[patch.vtxPtr[j]].sx];

pBnds.right ← MAX[pBnds.right, shape.vertex[patch.vtxPtr[j]].sx];

pBnds.bottom ← MIN[pBnds.bottom, shape.vertex[patch.vtxPtr[j]].sy];

pBnds.top ← MAX[pBnds.top, shape.vertex[patch.vtxPtr[j]].sy];

ENDLOOP;

};

GetPlane: PROC[patch: REF PtrPatch, shape: REF ShapeInstance] RETURNS[plane: Quad] ~ {

find plane defined by first three vertices

p1, p2, p3: Triple; vtx: REF Vertex;

vtx ← shape.vertex[patch.vtxPtr[0]]; p1 ← [vtx.ex, vtx.ey, vtx.ez];

vtx ← shape.vertex[patch.vtxPtr[1]]; p2 ← [vtx.ex, vtx.ey, vtx.ez];

vtx ← shape.vertex[patch.vtxPtr[2]]; p3 ← [vtx.ex, vtx.ey, vtx.ez];

plane ← G3dPlane.FromThreePoints[p1, p2, p3, TRUE]; -- get normalized plane

RETURN[ [plane.x*100.0, plane.y*100.0, plane.z*100.0, plane.w*100.0] ]; -- scale up

};

precisionLimit: REAL ← 0.0001; -- limits precision of intersection calc. to one part in 10,000

CheckAgainstPlane: PROC[nPatch: REF ShapePatch, plane: Quad] RETURNS[order: Order] ~ {

Returns status of newPatch with respect to plane

shape: REF ShapeInstance ← nPatch.shape;

patches: REF PtrPatchSequence ← NARROW[shape.surface];

patch: REF PtrPatch ← patches[nPatch.patch];

minusSum, plusSum, side: REAL ← 0.0;

FOR j: NAT IN [0..patch.nVtces) DO

vtx: REF Vertex ← shape.vertex[patch.vtxPtr[j]];

pt: Triple ← [vtx.ex, vtx.ey, vtx.ez];

dist: REAL ← pt.x*plane.x + pt.y*plane.y + pt.z*plane.z + plane.w; -- eval plane eq.

IF dist < 0.0

THEN minusSum ← minusSum - dist

ELSE plusSum ← plusSum + dist

ENDLOOP;

IF minusSum + plusSum < precisionLimit THEN RETURN[coincident]; -- coincident planes

IF minusSum < precisionLimit*plusSum

THEN side ← 1.0

ELSE IF plusSum < precisionLimit*minusSum

THEN side ← -1.0

ELSE RETURN[intersects];

IF ABS[plane.w] < precisionLimit

THEN RETURN[behind]; -- clip plane on edge (goes thru eye)

IF plane.w * side > 0.0

THEN RETURN[inFront] -- all points of nPatch between plane and eyepoint (origin)

ELSE RETURN[behind]; -- all points of nPatch on other side of plane

};

ClipPolyToPlane: PROC[context: REF Context, nPatch: REF ShapePatch, plane: Quad]
RETURNS[p1, p2: REF ShapePatch]~ {

Clip polygon by plane, add new vertices and new polys to shape structures.

Return 2 polys p1 on near side of plane, p2 on far side.

GetSurfacePlace: PROC[] RETURNS[place: INT32] ~ { -- place to add 2 polys

place ← NARROW[GetProp[shape.props, $ClippedPatches], REF INT32]^;

IF place+1 >= patches.maxLength THEN {

newPatches: REF PtrPatchSequence ← NEW[

PtrPatchSequence[place + MAX[16, INTEGER[place/8]]]

];

newPatches.length ← patches.length;

FOR i: NAT IN [0..INTEGER[place]) DO newPatches[i] ← patches[i]; ENDLOOP;

shape.surface ← patches ← newPatches;

};

shape.props ← PutProp[ shape.props, $ClippedPatches, NEW[INT32 ← place+2] ];

IF patchInfo # NIL THEN {

IF place+1 >= patchInfo.maxLength THEN {

newPatchInfo: REF ShadingSequence ← NEW[

ShadingSequence[place + MAX[16, INTEGER[place/8]]]

];

newPatchInfo.length ← patchInfo.length;

FOR i: NAT IN [0..INTEGER[place]) DO newPatchInfo[i] ← patchInfo[i]; ENDLOOP;

patchInfo ← shape.shadingClass.patchShade ← newPatchInfo;

};

GetVertexPlace: PROC[] RETURNS[place: INT32] ~ { -- place to add 1 vertex

place ← NARROW[GetProp[shape.props, $ClippedVertices], REF INT32]^;

IF place >= shape.vertex.maxLength THEN {

newVertices: REF VertexSequence ← NEW[

VertexSequence[place + MAX[16, INTEGER[place/8]]]

];

newShades: REF ShadingSequence ← NEW[

ShadingSequence[place + MAX[16, INTEGER[place/8]]]

];

newVertices.length ← shape.vertex.length;

FOR i: NAT IN [0..INTEGER[place]) DO newVertices[i] ← shape.vertex[i]; ENDLOOP;

newShades.length ← shape.shade.length;

FOR i: NAT IN [0..INTEGER[place]) DO newShades[i] ← shape.shade[i]; ENDLOOP;

shape.vertex ← newVertices; shape.shade ← newShades;

};

shape.props ← PutProp[ shape.props, $ClippedVertices, NEW[INT32 ← place+1] ];

};

shape: REF ShapeInstance ← nPatch.shape;

lerpProc: VertexInfoProc ← shape.shadingClass.lerpVtxAux;

patches: REF PtrPatchSequence ← NARROW[shape.surface];

patchInfo: REF ShadingSequence ← shape.shadingClass.patchShade;

patch: REF PtrPatch ← patches[nPatch.patch];

patch1, patch2: PtrPatch;

i1, i2, place: NAT ← 0;

lastVtx: REF Vertex ← shape.vertex[patch.vtxPtr[patch.nVtces-1]];

lastShade: REF ShadingValue ← shape.shade[patch.vtxPtr[patch.nVtces-1]];

lastDist: REAL ← lastVtx.ex*plane.x + lastVtx.ey*plane.y + lastVtx.ez*plane.z + plane.w;

IF lerpProc # NIL THEN SIGNAL G3dRender.Error[[$Unimplemented, "Aux not done yet "]];

patch1.type ← patch2.type ← patch.type;

patch1.oneSided ← patch2.oneSided ← patch.oneSided;

patch1.clipState ← patch2.clipState ← patch.clipState;

patch1.dir ← patch2.dir ← patch.dir;

patch1.props ← patch2.props ← patch.props;

patch1.vtxPtr ← NEW[NatSequence[patch.nVtces+2]];

patch2.vtxPtr ← NEW[NatSequence[patch.nVtces+2]];

FOR j: NAT IN [0..patch.nVtces) DO

vtx: REF Vertex ← shape.vertex[patch.vtxPtr[j]];

shade: REF ShadingValue ← shape.shade[patch.vtxPtr[j]];

dist: REAL ← vtx.ex*plane.x + vtx.ey*plane.y + vtx.ez*plane.z + plane.w; -- eval plane eq.

IF lastDist * dist < 0.0 THEN { -- intersection, copy computed vertex to both

newVtx: Vertex; newShade: ShadingValue;

b: REAL ← dist / (dist - lastDist); a: REAL ← 1.0 - b;

newVtx.x ← vtx.x * a + lastVtx.x * b;

newVtx.y ← vtx.y * a + lastVtx.y * b;

newVtx.z ← vtx.z * a + lastVtx.z * b;

newVtx.ex ← vtx.ex * a + lastVtx.ex * b;

newVtx.ey ← vtx.ey * a + lastVtx.ey * b;

newVtx.ez ← vtx.ez * a + lastVtx.ez * b;

[[newVtx.sx, newVtx.sy, newVtx.sz]] ← ShapeUtilities.XfmPtToDisplay[

context, [newVtx.ex, newVtx.ey, newVtx.ez]

];

newShade.exn ← shade.exn*a + lastShade.exn*b;

newShade.eyn ← shade.eyn*a + lastShade.eyn*b;

newShade.ezn ← shade.ezn*a + lastShade.ezn*b;

newShade.r ← shade.r * a + lastShade.r * b;

newShade.g ← shade.g * a + lastShade.g * b;

newShade.b ← shade.b * a + lastShade.b * b;

newShade.t ← shade.t * a + lastShade.t* b;

newShade.er ← shade.er * a + lastShade.er * b;

newShade.eg ← shade.eg * a + lastShade.eg * b;

newShade.eb ← shade.eb * a + lastShade.eb * b;

newShade.et ← shade.et * a + lastShade.et * b;

IF pIn.vtx[i].aux # NIL AND pIn.vtx[last].aux # NIL

THEN {

data: LORA ← LIST[

pIn.vtx[i].aux, pIn.vtx[last].aux, NEW[REAL ← a], NEW[REAL ← b]

];

pOut.vtx[outCnt] ← lerpProc[ context, pOut.vtx[outCnt], data ];

}

ELSE pOut.vtx[outCnt].aux ← pIn.vtx[i].aux;

place ← GetVertexPlace[]; -- store clipped pt with shape

shape.vertex[place] ← NEW[Vertex ← newVtx];

shape.shade[place] ← NEW[ShadingValue ← newShade];

patch1.vtxPtr[i1] ← patch2.vtxPtr[i2] ← place; i1 ← i1+1; i2 ← i2+1;

};

IF dist = 0.0

THEN { -- right on plane, copy to both sides

patch1.vtxPtr[i1] ← patch.vtxPtr[j]; i1 ← i1+1;

patch2.vtxPtr[i2] ← patch.vtxPtr[j]; i2 ← i2+1;

}

ELSE IF dist*plane.w > 0.0 OR (plane.w = 0.0 AND dist > 0.0)

THEN { patch1.vtxPtr[i1] ← patch.vtxPtr[j]; i1 ← i1+1; } -- on eye side of plane

ELSE { patch2.vtxPtr[i2] ← patch.vtxPtr[j]; i2 ← i2+1; }; -- on far side of plane

lastDist ← dist; lastVtx ← vtx; lastShade ← shade;

ENDLOOP;

patch1.nVtces ← i1; patch2.nVtces ← i2;

IF i1 < 3 OR i2 < 3 THEN SIGNAL G3dRender.Error[[$MisMatch, "Degenerate polygon"]];

place ← GetSurfacePlace[];

patches[place] ← NEW[PtrPatch ← patch1]; patches[place+1] ← NEW[PtrPatch ← patch2];

IF patchInfo # NIL THEN {

patchInfo[place] ← patchInfo[place+1] ← patchInfo[nPatch.patch];

};

p1 ← NEW[ShapePatch ← [shape, place, 0, 0, nPatch.awayness]];

p2 ← NEW[ShapePatch ← [shape, place+1, 0, 0, nPatch.awayness]];

};

LineSeparable: PROC[in1, in2: REF ShapePatch] RETURNS[BOOLEAN] ~ {

Can patches be separated by a line on screen?

overlap: REAL;

ptr1, ptr2: NAT;

Get Centroids of two patches

centroid1, centroid2: Pair ← [0.0, 0.0];

patches1: REF PtrPatchSequence ← NARROW[in1.shape.surface];

patches2: REF PtrPatchSequence ← NARROW[in2.shape.surface];

patch1: REF PtrPatch ← patches1[in1.patch];

patch2: REF PtrPatch ← patches2[in2.patch];

FOR j: NAT IN [0..patch1.nVtces) DO

vtx: REF Vertex ← in1.shape.vertex[patch1.vtxPtr[j]];

centroid1.x ← centroid1.x + vtx.sx; centroid1.y ← centroid1.y + vtx.sy;

ENDLOOP;

FOR j: NAT IN [0..patch2.nVtces) DO

vtx: REF Vertex ← in2.shape.vertex[patch2.vtxPtr[j]];

centroid2.x ← centroid2.x + vtx.sx; centroid2.y ← centroid2.y + vtx.sy;

ENDLOOP;

centroid1.x ← centroid1.x / patch1.nVtces; centroid1.y ← centroid1.y / patch1.nVtces;

centroid2.x ← centroid2.x / patch2.nVtces; centroid2.y ← centroid2.y / patch2.nVtces;

Project vertices on vector from centroid1 to centroid2 to get max1 and min2

{

max1, min2: REAL;

cntrVec: Pair ← [ centroid2.x - centroid1.x, centroid2.y - centroid1.y ]; -- from 1 to 2

cntrVecMag: REAL ← RealFns.SqRt[cntrVec.x*cntrVec.x+cntrVec.y*cntrVec.y];

IF cntrVecMag = 0.0 THEN RETURN[FALSE]; -- can't be separated if identical centroids

cntrVec.x ← cntrVec.x / cntrVecMag; cntrVec.y ← cntrVec.y / cntrVecMag;

FOR j: NAT IN [0..patch1.nVtces) DO

vtx: REF Vertex ← in1.shape.vertex[patch1.vtxPtr[j]];

prod: REAL ← cntrVec.x * (vtx.sx - centroid1.x) + cntrVec.y * (vtx.sy - centroid1.y);

IF j = 0 OR prod > max1 THEN { max1 ← prod; ptr1 ← j; } ;

ENDLOOP;

FOR j: NAT IN [0..patch2.nVtces) DO

vtx: REF Vertex ← in2.shape.vertex[patch2.vtxPtr[j]];

prod: REAL ← cntrVec.x * (vtx.sx - centroid1.x) + cntrVec.y * (vtx.sy - centroid1.y);

IF j = 0 OR prod < min2 THEN { min2 ← prod; ptr2 ← j; } ;

ENDLOOP;

Clearly separable if projections don't overlap

IF min2 >= max1 * (1.0 - precisionLimit) THEN RETURN[TRUE];

overlap ← max1 - min2;

};

Use edge between selected vertices as separator

WHILE TRUE DO

min1, min2, centroid1Dist, centroid2Dist, sgn: REAL;

nPtr1, nPtr2: NAT;

vtx1: REF Vertex ← in1.shape.vertex[patch1.vtxPtr[ptr1]];

vtx2: REF Vertex ← in2.shape.vertex[patch2.vtxPtr[ptr2]];

sepEdge: Triple ← [vtx2.sy - vtx1.sy, vtx1.sx - vtx2.sx, 0.0];

sepEdge ← G3dVector.Normalize[sepEdge];

sepEdge.z ← -(vtx2.sx * sepEdge.x + vtx2.sy * sepEdge.y);

centroid1Dist ← sepEdge.x * centroid1.x + sepEdge.y * centroid1.y + sepEdge.z;

centroid2Dist ← sepEdge.x * centroid2.x + sepEdge.y * centroid2.y + sepEdge.z;

IF centroid1Dist * centroid2Dist > 0.0 THEN RETURN[FALSE]; -- both on same side

sgn ← IF centroid1Dist < 0.0 THEN -1.0 ELSE 1.0;

FOR j: NAT IN [0..patch1.nVtces) DO

vtx: REF Vertex ← in1.shape.vertex[patch1.vtxPtr[j]];

dist: REAL ← sgn * (sepEdge.x * vtx.sx + sepEdge.y * vtx.sy + sepEdge.z);

IF j = 0 OR dist < min1 THEN { min1 ← dist; IF min1 < 0.0 THEN nPtr1 ← j; };

ENDLOOP;

sgn ← IF centroid2Dist < 0.0 THEN -1.0 ELSE 1.0;

FOR j: NAT IN [0..patch2.nVtces) DO

vtx: REF Vertex ← in2.shape.vertex[patch2.vtxPtr[j]];

dist: REAL ← sgn * (sepEdge.x * vtx.sx + sepEdge.y * vtx.sy + sepEdge.z);

IF j = 0 OR dist < min2 THEN { min2 ← dist; IF min2 < 0.0 THEN nPtr2 ← j; };

ENDLOOP;

IF min1 > -ScanConvert.justNoticeable AND min2 > -ScanConvert.justNoticeable

THEN RETURN[TRUE]

ELSE {

nOverlap: REAL ← 0.0;

IF min1 < 0.0 THEN { nOverlap ← nOverlap - min1; ptr1 ← nPtr1; };

IF min2 < 0.0 THEN { nOverlap ← nOverlap - min2; ptr2 ← nPtr2; };

IF nOverlap >= overlap THEN RETURN[FALSE]

ELSE overlap ← nOverlap;

};

ENDLOOP;

RETURN[FALSE]; -- can't get here, but compiler doesn't know that

};

PlaneSeparable: PROC[in1, in2: REF ShapePatch] RETURNS[Order] ~ {

Can patches be separated by a plane in eyespace? If so what is position of in1 wrt. in2

overlap: REAL;

ptr1, ptr2, nxtPtr1, nxtPtr2: NAT;

Get Centroids of two patches

centroid1, centroid2: Triple ← [0.0, 0.0, 0.0];

patches1: REF PtrPatchSequence ← NARROW[in1.shape.surface];

patches2: REF PtrPatchSequence ← NARROW[in2.shape.surface];

patch1: REF PtrPatch ← patches1[in1.patch];

patch2: REF PtrPatch ← patches2[in2.patch];

FOR j: NAT IN [0..patch1.nVtces) DO

vtx: REF Vertex ← in1.shape.vertex[patch1.vtxPtr[j]];

centroid1 ← G3dVector.Add[ centroid1, [vtx.ex, vtx.ey, vtx.ez] ];

ENDLOOP;

FOR j: NAT IN [0..patch2.nVtces) DO

vtx: REF Vertex ← in2.shape.vertex[patch2.vtxPtr[j]];

centroid2 ← G3dVector.Add[ centroid2, [vtx.ex, vtx.ey, vtx.ez] ];

ENDLOOP;

centroid1 ← G3dVector.Div[ centroid1 , patch1.nVtces ];

centroid2 ← G3dVector.Div[ centroid2 , patch2.nVtces ];

Project vertices on vector from centroid1 to centroid2 to get max1 and min2

{

max1, next1: REAL ← Real.MinusInfinity;

min2, next2: REAL ← Real.PlusInfinity;

cntrVec: Triple ← G3dVector.Sub[ centroid2, centroid1 ]; -- from 1 to 2

cntrVecMag: REAL ← G3dVector.Length[ cntrVec ];

IF cntrVecMag = 0.0 THEN RETURN[intersects]; -- can't be separated if identical centroids

cntrVec ← G3dVector.Div[ cntrVec, cntrVecMag ];

FOR j: NAT IN [0..patch1.nVtces) DO

vtx: REF Vertex ← in1.shape.vertex[patch1.vtxPtr[j]];

prod: REAL ← G3dVector.Dot[

cntrVec,

G3dVector.Sub[ [vtx.ex, vtx.ey, vtx.ez], centroid1 ]

];

IF j = 0 OR prod > max1

THEN { max1 ← prod; ptr1 ← j; next1 ← max1; nxtPtr1 ← ptr1; } -- new largest

ELSE IF prod > next1 THEN { next1 ← prod; nxtPtr1 ← j; }; -- new 2nd largest

ENDLOOP;

FOR j: NAT IN [0..patch2.nVtces) DO

vtx: REF Vertex ← in2.shape.vertex[patch2.vtxPtr[j]];

prod: REAL ← G3dVector.Dot[

cntrVec,

G3dVector.Sub[ [vtx.ex, vtx.ey, vtx.ez], centroid1 ]

];

IF j = 0 OR prod < min2

THEN { min2 ← prod; ptr2 ← j; next2 ← min2; nxtPtr2 ← ptr2; } -- new min.

ELSE IF prod < next2 THEN { next2 ← prod; nxtPtr2 ← j; }; -- new 2nd minimum

ENDLOOP;

Clearly separable if projections don't overlap

IF min2 >= max1 * (1.0 - precisionLimit) THEN {

max1Vec: Triple ← G3dVector.Add[ -- position of max1 projection on cntrVec

centroid1,

G3dVector.Mul[cntrVec, max1 / cntrVecMag]

];

IF G3dVector.Dot[max1Vec, cntrVec] > 0.0

THEN RETURN[inFront] -- cntrVec tilts away from the eye, in1 in front

ELSE RETURN[behind]; -- cntrVec tilts toward the eye, in1 behind

};

overlap ← max1 - min2;

};

Use plane through innermost vertices and an adjacent vertex as separator

{

vtx1: REF Vertex ← in1.shape.vertex[patch1.vtxPtr[ptr1]];

vtx2: REF Vertex ← in2.shape.vertex[patch2.vtxPtr[ptr2]];

FOR i: NAT IN [0..2) DO

state1, state2: Order;

adjPtr: NAT ← IF i = 0

THEN (ptr1 + 1) MOD patch1.nVtces

ELSE (ptr1 + patch1.nVtces-1) MOD patch1.nVtces;

vtx1a: REF Vertex ← in1.shape.vertex[patch1.vtxPtr[adjPtr]];

sepPlane: Quad ← G3dPlane.FromThreePoints[

[vtx1.ex, vtx1.ey, vtx1.ez],

[vtx2.ex, vtx2.ey, vtx2.ez],

[vtx1a.ex, vtx1a.ey, vtx1a.ez],

TRUE -- normalize

! G3dPlane.Error => LOOP

];

sepPlane ← [sepPlane.x*100.0, sepPlane.y*100.0, sepPlane.z*100.0, sepPlane.w*100.0];

state1 ← CheckAgainstPlane[in1, sepPlane];

state2 ← CheckAgainstPlane[in2, sepPlane];

IF (state1 = behind AND state2 = inFront) OR (state1 = inFront AND state2 = behind)

THEN RETURN[state1];

ENDLOOP;

FOR i: NAT IN [0..2) DO -- failed to get good planes on first poly, try other one

state1, state2: Order;

adjPtr: NAT ← IF i = 0

THEN (ptr2 + 1) MOD patch2.nVtces

ELSE (ptr2 + patch2.nVtces-2) MOD patch2.nVtces;

vtx2a: REF Vertex ← in2.shape.vertex[patch2.vtxPtr[adjPtr]];

sepPlane: Quad ← G3dPlane.FromThreePoints[

[vtx1.ex, vtx1.ey, vtx1.ez],

[vtx2.ex, vtx2.ey, vtx2.ez],

[vtx2a.ex, vtx2a.ey, vtx2a.ez],

TRUE -- normalize

! G3dPlane.Error => LOOP

];

sepPlane ← [sepPlane.x*100.0, sepPlane.y*100.0, sepPlane.z*100.0, sepPlane.w*100.0];

state1 ← CheckAgainstPlane[in1, sepPlane];

state2 ← CheckAgainstPlane[in2, sepPlane];

IF (state1 = behind AND state2 = inFront) OR (state1 = inFront AND state2 = behind)

THEN RETURN[state1] ELSE IF i # 0 THEN RETURN[intersects];

ENDLOOP;

};

RETURN[intersects]; -- come here on utter failure to get a reasonable answer

};

ShowPrioritySeq: PROC[context: REF Context, sortOrder: REF SortSequence] ~ {

Debugging aid shows state of partially-completed priority order

j: NAT ← sortOrder[1].prev;

context.class.loadBackground[context];

WHILE j > 0 DO

ShowOnePatch[context, sortOrder[j].shape, sortOrder[j].patch];

j ← sortOrder[j].prev;

ENDLOOP;

};

LoadPrioritySequence: PUBLIC PROC[context: REF Context, sortOrder: LIST OF REF ANY ← NIL]
RETURNS[LIST OF REF ANY, CARDINAL] ~ {

Keep 2 lists:

(1) Active patches whose far limit is farther than current near limit

(2) permanent list

Compare with sorted active list (those that overlap in depth):

- if far limit closer than current near, delete from active list

- if same shape go to next one

- if screen limits don't overlap go to next one

- compare planes for intersection, clip if not separable, insert if in front

- if clipped

- insert new patches into shape data structures to create new ShapePatch

- put frontmost new patch into active and permanent lists, continue with both halves

sortKey: REF NatSequence; -- 1st element of 'sortOrder', sort buckets with linked lists of

buckets: REF SortSequence; -- 2nd element of 'sortOrder', sort buckets with linked lists of

-- REF ShapePatch

ShapePatch: TYPE ~ RECORD[shape: REF ShapeInstance, patch, next, prev: INT, awayness: REAL];

sorted: REF SortSequence;

active: REF SortSequence;

bounds: REF BoundsSequence; -- RECORD[left, right, bottom, top, near, far: REAL];

activeKey: REF NatSequence; -- keeps order on active and bounds

numActive: NAT ← 0;

emptySpace: INTEGER ← -1; -- hole in active - negative means NIL

endOfActive: NAT ← 0; -- beginning of unused space in active

endOfSort: NAT; -- beginning of unused space in sort

patchCount: CARDINAL ← 0;

ExtendBds: PROC[seq: REF BoundsSequence] RETURNS[newSeq: REF BoundsSequence] ~ {

newSeq ← NEW[ BoundsSequence[seq.length + MAX[16, INTEGER[seq.length/8]]] ];

FOR i: NAT IN [0..seq.length) DO newSeq[i] ← seq[i]; ENDLOOP;

};

ExtendNat: PROC[seq: REF NatSequence] RETURNS[newSeq: REF NatSequence] ~ {

newSeq ← NEW[ NatSequence[seq.maxLength + MAX[16, INTEGER[seq.maxLength/8]]] ];

FOR i: NAT IN [0..seq.maxLength) DO newSeq[i] ← seq[i]; ENDLOOP;

};

Extend: PROC[seq: REF SortSequence] RETURNS[newSeq: REF SortSequence] ~ {

newSeq ← NEW[ SortSequence[seq.length + MAX[16, INTEGER[seq.length/8]]] ];

FOR i: NAT IN [0..seq.length) DO newSeq[i] ← seq[i]; ENDLOOP;

};

DeleteActive: PROC[index: NAT] ~ {

j: NAT ← activeKey[index];

active[j] ← NIL; -- nil entry

bounds[j] ← [0.0, 0.0, 0.0, 0.0, 0.0, 0.0];

emptySpace ← j;

FOR i: NAT IN [index..numActive-1) DO -- close up pointer array

activeKey[i] ← activeKey[i+1];

ENDLOOP;

activeKey[numActive-1] ← 0;

numActive ← numActive - 1;

};

InsertActive: PROC[index: NAT, pBnds: Bounds, patch: REF ShapePatch] ~ {

place: NAT;

IF emptySpace < 0

THEN {

place ← endOfActive; endOfActive ← endOfActive+1;

IF endOfActive >= active.length THEN { -- overflow, extend sequences

active ← Extend[active]; bounds ← ExtendBds[bounds];

activeKey ← ExtendNat[activeKey];

};

}

ELSE { place ← emptySpace; emptySpace ← -1; };

IF index = 0

THEN IF numActive = 0 -- first entry in active list ?

THEN { patch.prev ← sorted[1].next; patch.next ← sorted[patch.prev].next; }

ELSE patch.next ← sorted[active[activeKey[index]].prev].next -- heading active list

ELSE patch.next ← active[activeKey[index-1]].next; -- not heading active list

IF numActive > 0 THEN patch.prev ← sorted[patch.next].prev; -- back ptr. from next patch

sorted[patch.prev].next ← endOfSort; -- fore pointer from current patch

sorted[patch.next].prev ← endOfSort; -- back ptr to new patch

IF endOfSort >= sorted.length THEN sorted ← Extend[sorted];

sorted[endOfSort] ← patch; -- put in sorted array

endOfSort ← endOfSort + 1; -- increment store location

FOR i: NAT DECREASING IN [index..numActive) DO -- open up pointer array

activeKey[i+1] ← activeKey[i];

ENDLOOP;

activeKey[index] ← place; -- insert pointer to Patch and bounds arrays

active[place] ← patch;

bounds[place] ← pBnds;

numActive ← numActive + 1;

};

Promote: PROC[from, to: NAT] RETURNS[NAT] ~ {

Move entry forward in active list

fromPlace: NAT ← activeKey[from];

toPlace: NAT ← activeKey[to];

promoteeAddr: NAT; -- location of promotee in sorted sequence

tBnds: Bounds ← bounds[fromPlace];

tActive: REF ShapePatch ← active[fromPlace];

FOR i: NAT DECREASING IN [to..from) DO -- move intermediate entries back one

activeKey[i+1] ← activeKey[i];

ENDLOOP;

activeKey[to] ← fromPlace; -- insert promoted entry

remove from previous spot in linked list

promoteeAddr ← sorted[tActive.prev].next; -- get pointer to promotee

sorted[tActive.prev].next ← tActive.next; -- redirect fore pointer from promoted patch

sorted[tActive.next].prev ← tActive.prev; -- redirect back ptr from promoted patch

insert in new spot

tActive.prev ← active[toPlace].prev; -- link promotee into new position

tActive.next ← sorted[tActive.prev].next;

sorted[tActive.prev].next ← promoteeAddr; -- redirect fore pointer to promoted patch

sorted[tActive.next].prev ← promoteeAddr; -- redirect back ptr to promoted patch

Note! Cyclically overlapping surfaces may occur and should be checked for here

RETURN[to+1]; -- next site to insert polygon

};

Insert: PROC[inPatch: REF ShapePatch, start, level: NAT ← 0] RETURNS[NAT] ~ {

Insert patch in sorted list

newPatch: REF ShapePatch ← NEW[ShapePatch ← inPatch^]; -- insulate external patch ptrs

rearParts: LIST OF REF ShapePatch ← NIL;

shape: REF ShapeInstance ← newPatch.shape;

away: REAL ← newPatch.awayness;

selfIntersecting: BOOLEAN ← FALSE; -- shape property?

patches: REF PtrPatchSequence ← NARROW[shape.surface];

patch: REF PtrPatch ← patches[newPatch.patch];

pBnds: Bounds ← GetBounds[patch, shape]; -- Get bounding box for patch

i: NAT ← start;

inserted: BOOLEAN ← FALSE;

insertionPt: NAT;

Cull active polygons entirely closer than newPatch (if dealing with original poly)

WHILE level = 0 AND i < numActive AND bounds[activeKey[i]].far <= pBnds.near DO

DeleteActive[i]; i ← i+1; -- cull anything at beginning no depth overlap

ENDLOOP;

WHILE i < numActive DO

newPlane: Quad;

j: NAT ← activeKey[i];

i ← i+1;

IF bounds[j].right <= pBnds.left THEN LOOP; -- bounds overlap on screen?

IF bounds[j].left >= pBnds.right THEN LOOP;

IF bounds[j].top <= pBnds.bottom THEN LOOP;

IF bounds[j].bottom >= pBnds.top THEN LOOP;

IF LineSeparable[active[j], newPatch] THEN LOOP; -- linearly separable on screen

IF active[j].shape = shape -- overlapping, same shape

THEN IF NOT selfIntersecting

THEN IF NOT shape.insideVisible

THEN LOOP -- no backfacing polygons

ELSE IF ABS[active[j].awayness - newPatch.awayness] < 0.5 -- kluge!!

THEN LOOP; -- from same poly

THEN IF ABS[active[j].awayness - away] > 0.5 * ABS[active[j].awayness + away]

THEN IF active[j].awayness < away -- significantly different awayness

THEN { -- if new entry more backfacing

IF inserted THEN insertionPt ← Promote[from: i-1, to: insertionPt];

LOOP

}

ELSE { -- if earlier entry more backfacing

IF NOT inserted THEN

{ InsertActive[i-1, pBnds, newPatch]; inserted ← TRUE; insertionPt ← i-1; };

LOOP;

}

ELSE LOOP

ELSE {}; -- self-intersecting shape, find common edge

newPlane ← GetPlane[patch, shape]; -- try plane of new polygon as separator

SELECT CheckAgainstPlane[active[j], newPlane] FROM

inFront, coincident => { -- polygon in front of or coincident with new plane

IF inserted THEN insertionPt ← Promote[from: i-1, to: insertionPt]; -- new order

LOOP;

}; -- else go to next polygon

behind => { -- insert in front of polygon

IF inserted THEN LOOP;

InsertActive[i-1, pBnds, newPatch]; inserted ← TRUE;

insertionPt ← i-1; LOOP;

};

intersects => { -- vertices on both sides of plane, test other way

shape: REF ShapeInstance ← active[j].shape;

oldPatches: REF PtrPatchSequence ← NARROW[shape.surface];

oldPatch: REF PtrPatch ← oldPatches[active[j].patch];

oldPlane: Quad ← GetPlane[oldPatch, shape]; -- plane of polygon from active list

SELECT CheckAgainstPlane[newPatch, oldPlane] FROM

behind, coincident => { -- new poly behind or coincident with old plane

IF inserted THEN insertionPt ← Promote[from: i-1, to: insertionPt];

LOOP;

}; -- else go to next polygon

inFront => { -- insert in front of polygon

IF inserted THEN LOOP;

InsertActive[i-1, pBnds, newPatch];

inserted ← TRUE; insertionPt ← i-1; LOOP;

};

intersects => { -- not resolvable, check for separating plane

SELECT PlaneSeparable[newPatch, active[j]] FROM

behind => { -- new poly behind old poly

IF inserted THEN insertionPt ← Promote[from: i-1, to: insertionPt];

LOOP;

}; -- else go to next polygon

inFront => { -- insert in front of polygon

IF inserted THEN LOOP;

InsertActive[i-1, pBnds, newPatch];

inserted ← TRUE; insertionPt ← i-1; LOOP;

};

intersects => { -- not resolvable, split new polygon by plane of old

rearPatch: REF ShapePatch;

[newPatch, rearPatch] ← ClipPolyToPlane[context, newPatch, oldPlane];

rearParts ← CONS[rearPatch, rearParts];

patchCount ← patchCount + 1; -- a new polygon generated

IF inserted -- replace whole patch with front part if inserted

THEN active[activeKey[insertionPt]].patch ← newPatch.patch

ELSE IF NOT LineSeparable[active[j], newPatch] THEN {

InsertActive[i-1, pBnds, newPatch]; inserted ← TRUE;

insertionPt ← i-1; i ← i+1; -- insert front part

};

ENDCASE;

};

ENDCASE;

};

ENDCASE;

ENDLOOP;

IF NOT inserted THEN { InsertActive[i, pBnds, newPatch]; insertionPt ← i; };

IF NOT debug THEN WHILE rearParts # NIL DO -- continue recursively with rear parts

insertionPt ← Insert[rearParts.first, MIN[numActive, insertionPt+2], level+1];

rearParts ← rearParts.rest;

ENDLOOP;

RETURN[insertionPt];

};

[sortOrder, patchCount] ← LoadDepthSequence[context, sortOrder]; -- sort by nearest vertex

sortKey ← NARROW[sortOrder.first, REF NatSequence];

buckets ← NARROW[sortOrder.rest.first, REF SortSequence];

sorted ← NEW[SortSequence[2*patchCount+2]];

bounds ← NEW[BoundsSequence[2*patchCount]];

active ← NEW[SortSequence[2*patchCount]];

activeKey ← NEW[NatSequence[2*patchCount+1]];

sorted[0] ← NEW[ShapePatch ← [NIL, 0, 1, 0, 0.0]]; -- initialize list header

sorted[1] ← NEW[ShapePatch ← [NIL, 0, 0, 0, 0.0]]; -- initialize dummy list tail

endOfSort ← 2;

FOR i: NAT IN [0..sortKey.length) DO -- compose initial sort into complete ordering

j: NAT ← sortKey[i];

WHILE j # nullPtr DO

[] ← Insert[buckets[j]]; -- insert next polygon in order in list

j ← buckets[j].next;

IF context.stopMe^ THEN RETURN[sortOrder, patchCount]; -- quit if stop signal received

ENDLOOP;

sortKey[0] ← sorted[0].next; -- start linked list at 1st element

sortKey.length ← 1;

sorted[sorted[1].prev].next ← 0; -- bind off linked list at last real element

sorted[sortKey[0]].prev ← sorted[1].prev; -- set pointer to list tail at 1st element

RETURN[ LIST[sortKey, sorted, NIL], patchCount ];

};

LoadDepthSequence: PUBLIC PROC[ context: REF Context, sortOrder: LIST OF REF ANY ← NIL ]
RETURNS[LIST OF REF ANY, CARDINAL] ~ {

Builds front-to-back sorted array of buckets, bidirectional linked lists within buckets

sortKey: REF NatSequence; -- 1st element of 'sortOrder', sort buckets with linked lists of

buckets: REF SortSequence; -- 2nd element of 'sortOrder', sort buckets with linked lists of

-- REF ShapePatch

shape: REF ShapeSequence ← context.visibleShapes;

patchCount: CARDINAL ← 0;

bucketListPtr: INT ← 1; -- start bucket count at 1 to allow use of zero as null

minDepth: REAL ← context.yonLimit;

maxDepth: REAL ← context.hitherLimit;

zScale: REAL ← 1.;

NewSortOrder: PROC[] ~ {

buckets ← NEW[SortSequence[patchCount+1]];

sortKey ← NEW[NatSequence[context.depthResolution]];

sortKey.length ← context.depthResolution;

};

FOR i: NAT IN [0.. shape.length) DO -- get minimum and maximum depth and patch count

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;

patchCount ← patchCount + shape[i].numSurfaces;

shape[i].props ← PutProp[ -- set sizes for intersections in priority sdort

shape[i].props, $ClippedPatches, NEW[INT32 ← shape[i].numSurfaces]

];

shape[i].props ← PutProp[

shape[i].props, $ClippedVertices, NEW[INT32 ← shape[i].vertex.length]

];

ENDLOOP;

minDepth ← MAX[minDepth, 0]; -- nothing allowed behind the eyepoint

IF (maxDepth - minDepth) > 0.

THEN zScale ← (context.depthResolution - 1) / (maxDepth - minDepth);

IF sortOrder # NIL

THEN {

sortKey ← NARROW[sortOrder.first];

buckets ← NARROW[sortOrder.rest.first];

}

ELSE NewSortOrder[];

IF buckets.length < patchCount OR sortKey.length < context.depthResolution

THEN NewSortOrder[]; -- get new storage if sizes have expanded

FOR i: NAT IN [0..sortKey.length) DO sortKey[i] ← nullPtr; ENDLOOP; -- clear sort structure

FOR s: NAT IN [0.. shape.length) DO -- Enter patches (by nearest z) in bucket lists

patch: REF PtrPatchSequence ← NARROW[shape[s].surface];

FOR i: NAT IN [0..shape[s].numSurfaces) DO

IF context.stopMe^ THEN RETURN[NIL, 0]; -- shut down if stop signal received

IF patch[i] # NIL AND patch[i].clipState # out THEN { -- can't be proven not visible

neg, pos: BOOLEAN ← FALSE;

dirSum: REAL ← 0.0;

zNear: REAL ← maxDepth;

iz: INT;

FOR j: NAT IN [0..patch[i].nVtces) DO -- get minimum z-coordinate

zNear ← MIN[zNear, shape[s].vertex[patch[i].vtxPtr[j]].ez];

ENDLOOP;

iz ← INTEGER[Real.Fix[zScale *(zNear - minDepth)]]; -- get matching bucket addr.

IF iz < 0 THEN iz ← 0; -- clip at zero

IF patch[i].type = $ConvexPolygon THEN -- normals valid only for polygons

FOR k: NAT IN [0..patch[i].nVtces) DO

j: NAT ← patch[i].vtxPtr[k];

dir: REAL ← G3dVector.Dot[ -- normal front or back facing?

[shape[s].vertex[j].ex, shape[s].vertex[j].ey, shape[s].vertex[j].ez],

[shape[s].shade[j].exn, shape[s].shade[j].eyn, shape[s].shade[j].ezn]

];

IF dir > 0.0 THEN pos ← TRUE ELSE IF dir < 0.0 THEN neg ← TRUE;

dirSum ← dirSum + dir; -- sum normals to characterize orientation

ENDLOOP;

IF pos AND NOT neg THEN patch[i].dir ← back

ELSE IF neg AND NOT pos THEN patch[i].dir ← front

ELSE patch[i].dir ← undetermined;

IF NOT (patch[i].oneSided AND patch[i].dir = back) THEN { -- will be displayed

bckPtr, nxtPtr: INT ← nullPtr;

nxtPtr ← sortKey[iz];

WHILE nxtPtr # nullPtr AND buckets[nxtPtr].awayness < dirSum DO

bckPtr ← nxtPtr; -- find right place in ordered chain

nxtPtr ← buckets[nxtPtr].next;

ENDLOOP;

Maintain doubly-linked list with back pointer to tail at list head

buckets[bucketListPtr] ← NEW[ShapePatch];

buckets[bucketListPtr].shape ← shape[s];

buckets[bucketListPtr].patch ← i;

buckets[bucketListPtr].next ← buckets[bucketListPtr].prev ← nullPtr; -- clear

IF nxtPtr # nullPtr THEN { -- not at tail of list

buckets[bucketListPtr].prev ← buckets[nxtPtr].prev;

buckets[bucketListPtr].next ← nxtPtr;

buckets[nxtPtr].prev ← bucketListPtr;

};

IF bckPtr # nullPtr THEN { -- not at head of list

buckets[bucketListPtr].next ← buckets[bckPtr].next;

buckets[bucketListPtr].prev ← bckPtr;

buckets[bckPtr].next ← bucketListPtr;

};

IF bckPtr = nullPtr THEN { -- at head of list

sortKey[iz] ← bucketListPtr; -- reset list header

};

IF nxtPtr = nullPtr THEN -- at tail of list

buckets[sortKey[iz]].prev ← bucketListPtr; -- reset tail ptr at head

buckets[bucketListPtr].awayness ← dirSum; -- sum of dot prods of vertex nmls
-- with eyept dir, quantitative measure of "backfacingness"

bucketListPtr ← bucketListPtr + 1;

};

ENDLOOP;

sortKey.length ← context.depthResolution;

RETURN[ LIST[sortKey, buckets], patchCount ];

};

Procedures for Display

GetDepths: PROC[ context: REF Context] ~ {

Calculate depths scaled over max and min depth for depth-buffering

shape: REF G3dRender.ShapeSequence ← context.visibleShapes;

minDepth: REAL ← context.yonLimit;

maxDepth: REAL ← context.hitherLimit;

zScale: REAL ← 1.;

FOR i: NAT IN [0.. shape.length) DO -- get minimum and maximum depth

radius: REAL ← shape[i].boundingRadius;

IF shape[i].class.type # $ConvexPolygon THEN radius ← 1.1 * radius; -- fudge for patches

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;

ENDLOOP;

minDepth ← MAX[minDepth, context.hitherLimit]; -- nothing allowed behind the eyepoint

IF (maxDepth - minDepth) > 0.

THEN zScale ← (context.depthResolution - 1) / (maxDepth - minDepth);

context.eyeToNdc.addZ ← 1./(1. - minDepth/maxDepth); --smash hither-yon factors

context.eyeToNdc.scaleZ ← -minDepth/(1. - minDepth/maxDepth);

FOR s: NAT IN [0.. shape.length) DO

ShapeUtilities.XfmToDisplay[context, shape[s] ];

ENDLOOP;

};

DoBackToFront: PUBLIC PROC[ context: REF Context,
sortInfo: LIST OF REF ANY,
action: PROC[REF ShapePatch] ] ~ {

sortKey: REF NatSequence ← NARROW[sortInfo.first];

buckets: REF SortSequence ← NARROW[sortInfo.rest.first];

FOR i: NAT DECREASING IN [0..sortKey.length) DO

j: NAT ← sortKey[i];

WHILE j # nullPtr DO

j ← buckets[j].prev; -- jump to tail of list and work back

action[buckets[j]]; -- call back with next polygon in order

IF j = sortKey[i] THEN j ← nullPtr; -- exit if head of list reached

IF context.stopMe^ THEN RETURN[]; -- shut down if stop signal received

ENDLOOP;

CombineBoxes[context]; -- get combined bounding box on scene

};

DoFrontToBack: PUBLIC PROC[ context: REF Context,
sortInfo: LIST OF REF ANY,
action: PROC[REF ShapePatch] ] ~ {

sortKey: REF NatSequence ← NARROW[sortInfo.first];

buckets: REF SortSequence ← NARROW[sortInfo.rest.first];

FOR i: NAT IN [0..sortKey.length) DO

j: NAT ← sortKey[i];

WHILE j # nullPtr DO

action[buckets[j]]; -- call back with next polygon in order

j ← buckets[j].next;

IF context.stopMe^ THEN RETURN[]; -- shut down if stop signal received

ENDLOOP;

CombineBoxes[context]; -- get combined bounding box on scene

};

DoForPatches: PUBLIC PROC[ context: REF Context, set: REF G3dRender.ShapeSequence,
patchAction: PROC[REF ShapePatch],
shapeAction: PROC[REF ShapeInstance] ← NIL ] ~ {

FOR s: NAT IN [0..set.length) DO

IF set[s].clipState = in AND shapeAction # NIL

THEN shapeAction[set[s]]

ELSE {

patch: REF PtrPatchSequence ← NARROW[set[s].surface];

FOR i: NAT IN [0..set[s].numSurfaces) DO IF patch[i] # NIL THEN {

IF context.stopMe^ THEN RETURN[]; -- shut down if stop signal received

IF set[s].clipState = in

THEN patch[i].clipState ← in -- unclipped, inside

ELSE IF set[s].clipState = clipped

THEN GetPtrPatchClipState[ set[s], patch[i] ]

ELSE patch[i].clipState ← out;

IF patch[i].clipState # out

THEN patchAction[NEW[ ShapePatch ← [set[s], i, 0, 0, 0.0] ]];

};

ENDLOOP;

};

ENDLOOP;

};

CombineBoxes: PUBLIC PROC[context: REF Context] ~ { -- get combined bounding box

context.extentCovered ← [ [LAST[NAT], LAST[NAT]], [FIRST[NAT], FIRST[NAT]] ];

FOR i: NAT IN [0..context.visibleShapes.length) DO

IF context.extentCovered.min.f > context.visibleShapes[i].screenExtent.min.f

THEN context.extentCovered.min.f ← context.visibleShapes[i].screenExtent.min.f;

IF context.extentCovered.max.f < context.visibleShapes[i].screenExtent.max.f

THEN context.extentCovered.max.f ← context.visibleShapes[i].screenExtent.max.f;

IF context.extentCovered.min.s > context.visibleShapes[i].screenExtent.min.s

THEN context.extentCovered.min.s ← context.visibleShapes[i].screenExtent.min.s;

IF context.extentCovered.max.s < context.visibleShapes[i].screenExtent.max.s

THEN context.extentCovered.max.s ← context.visibleShapes[i].screenExtent.max.s;

ENDLOOP;

};

ShowOnePatch: PROC[ context: REF Context, shape: REF ShapeInstance, i: NAT] ~ {

patch: REF PtrPatchSequence ← NARROW[shape.surface];

IF shape.clipState = in

THEN patch[i].clipState ← in -- unclipped, inside

ELSE IF shape.clipState = clipped

THEN GetPtrPatchClipState[ shape, patch[i] ]

ELSE patch[i].clipState ← out;

IF patch[i].clipState # out THEN {

patch: REF Patch ← ShapeUtilities.ShapePatchToPatch[

context, NEW[ ShapePatch ← [shape, i, 0, 0, 0.0] ]

];

[] ← shape.class.displayPatch[ context, patch ];

};

ShowOneVtx: PROC[ context: REF Context, shape: REF ShapeInstance, j: NAT] ~ {

patch: REF PtrPatchSequence ← NARROW[shape.surface];

FOR i: NAT IN [0..patch.length) DO

containsVtx: BOOLEAN ← FALSE;

FOR k: NAT IN [0..patch[i].nVtces) DO

IF patch[i].vtxPtr[k] = j THEN { containsVtx ← TRUE; EXIT; };

ENDLOOP;

IF containsVtx THEN {

IF shape.clipState = in

THEN patch[i].clipState ← in -- unclipped, inside

ELSE IF shape.clipState = clipped

THEN GetPtrPatchClipState[ shape, patch[i] ]

ELSE patch[i].clipState ← out;

IF patch[i].clipState # out THEN {

patch: REF Patch ← ShapeUtilities.ShapePatchToPatch[

context, NEW[ ShapePatch ← [shape, i, 0, 0, 0.0] ]

];

[] ← shape.class.displayPatch[ context, patch ];

};

ENDLOOP;

};

ShowObjects: PUBLIC PROC[ context: REF Context, frontToBack: BOOLEAN ← FALSE ] ~ {

ShowPatch: PROC[p: REF ShapePatch] ~{

patch: REF Patch ← ShapeUtilities.ShapePatchToPatch[ context, p ];

[] ← p.shape.class.displayPatch[ context, patch ];

patchCount ← patchCount + 1;

IF log # NIL AND context.antiAliasing AND progressReportsPerFrame > 0
AND patchCount >= nextReport THEN {

log.PutRope[ Rope.Cat[

Rope.Cat[ "\n ", Convert.RopeFromInt[patchCount], " of " ],

Rope.Cat[ Convert.RopeFromInt[patchTotal], " done in ", ElapsedTime[time] ]

] ];

nextReport ← MIN[patchCount + patchTotal/progressReportsPerFrame, patchTotal-1];

};

patchCount, patchTotal, nextReport: INT ← 0;

time: REAL ← CurrentTime[];

log: IO.STREAM ← NARROW[ Atom.GetPropFromList[context.props, $Log] ];

timing: Rope.ROPE;

justOne: REF IntegerPair ← NARROW[ Atom.GetPropFromList[context.props, $SinglePatch] ];

oneVtx: REF IntegerPair ← NARROW[ Atom.GetPropFromList[context.props, $SingleVtx] ];

shape: REF G3dRender.ShapeSequence ← context.visibleShapes;

IF shape = NIL THEN RETURN[];

IF context.depthBuffering THEN GetDepths[context];

IF justOne # NIL

THEN { ShowOnePatch[context, shape[justOne.x], justOne.y]; RETURN[]; };

IF oneVtx # NIL

THEN { ShowOneVtx[context, shape[oneVtx.x], oneVtx.y]; RETURN[]; };

IF context.depthBuffering AND NOT context.antiAliasing

THEN DoForPatches[context, shape, ShowPatch]

ELSE {

IF GetProp[context.props, $SortToPriority] # NIL

THEN [context.sortSequence, patchTotal] ← LoadPrioritySequence[context,
NARROW[context.sortSequence] ]

ELSE [context.sortSequence, patchTotal] ← LoadDepthSequence[context,
NARROW[context.sortSequence] ];

timing ← Rope.Cat[ timing, " Sort: ", ElapsedTime[time] ]; time ← CurrentTime[];

IF context.delayClear THEN context.class.loadBackground[context]; -- load background

IF context.stopMe^ THEN RETURN[]; -- shut down if stop signal received

IF frontToBack

THEN DoFrontToBack[context, NARROW[context.sortSequence], ShowPatch]

ELSE DoBackToFront[context, NARROW[context.sortSequence], ShowPatch];

};

IF log # NIL THEN log.PutRope[ Rope.Cat[ timing, " Scan: ", ElapsedTime[time] ] ];

};

ShowWireFrameObjects: PUBLIC PROC[context: REF Context ] ~ {

ShowPatch: PROC[p: REF ShapePatch] ~{

patch: REF Patch ← ShapeUtilities.ShapePatchToPatch[ context, p ];

[] ← p.shape.class.displayPatch[ context, patch ];

};

ShowShape: PROC[s: REF ShapeInstance] ~{

IF s.class.display # NIL

THEN SELECT context.class.displayType FROM

$PseudoColor, $Gray, $FullColor => [] ← s.class.display[ context, s ];

ENDCASE => OutputShape[context, s]

ELSE OutputShape[context, s];

};

shape: REF G3dRender.ShapeSequence ← context.visibleShapes;

justOne: REF IntegerPair ← NARROW[ Atom.GetPropFromList[context.props, $SinglePatch] ];

oneVtx: REF IntegerPair ← NARROW[ Atom.GetPropFromList[context.props, $SingleVtx] ];

IF shape = NIL THEN RETURN[];

IF context.delayClear THEN context.class.loadBackground[context]; -- load background

IF justOne # NIL

THEN { ShowOnePatch[context, shape[justOne.x], justOne.y]; RETURN[]; };

IF oneVtx # NIL

THEN { ShowOneVtx[context, shape[oneVtx.x], oneVtx.y]; RETURN[]; };

DoForPatches[context, shape, ShowPatch, ShowShape];

CombineBoxes[context]; -- get combined bounding box on scene

};

OutputShape: PROC[context: REF Context, shape: REF ShapeInstance] ~ {

Unclipped shape output

patch: REF PtrPatchSequence;

IF shape.surface = NIL THEN RETURN;

IF context.stopMe^ THEN RETURN[]; -- shut down if stop signal received

patch ← NARROW[shape.surface];

FOR i: NAT IN [0..shape.numSurfaces) DO IF patch[i] # NIL THEN {

p: REF Patch ← ShapeUtilities.ShapePatchToPatch[

context, NEW[ShapePatch ← [shape, i, 0, 0, 0.0]]

];

[] ← shape.class.displayPatch[ context, p ];

};

ENDLOOP;

};

dummyShape: REF ShapeInstance ← NEW[ShapeInstance];

EdgesToPolygons: PatchProc ~ {

PROC[ context: REF Context, patch: REF Patch, data: REF ANY ← NIL ] RETURNS[REF Patch]

Make a polygon for each edge and tile it, this causes shading as seen from outside

MakeEdge: PROC[pt1, pt2: VertexInfo, edge: REF Patch] ~ {

dirX, dirY, mag, offSetX1, offSetY1, offSetX2, offSetY2: REAL;

dirX ← pt2.coord.ex - pt1.coord.ex; -- get unit vector in edge direction

dirY ← pt2.coord.ey - pt1.coord.ey;

mag ← RealFns.SqRt[ Sqr[dirX] + Sqr[dirY] ];

IF mag < ScanConvert.justNoticeable THEN RETURN[]; -- quit if too short to be seen

dirX ← dirX / mag; dirY ← dirY / mag;

offSetX1 ← dirX * baseRadius; offSetY1 ← dirY * baseRadius;

offSetX2 ← dirX * baseRadius; offSetY2 ← dirY * baseRadius;

FOR i: NAT IN [0..3) DO edge[i] ← pt1; ENDLOOP;

FOR i: NAT IN [3..6) DO edge[i] ← pt2; ENDLOOP;

edge[0].coord.ex ← edge[0].coord.ex+offSetY1; edge[0].coord.ey ← edge[0].coord.ey-offSetX1;

edge[1].coord.ex ← edge[1].coord.ex-offSetX1; edge[1].coord.ey ← edge[1].coord.ey-offSetY1;

edge[2].coord.ex ← edge[2].coord.ex-offSetY1; edge[2].coord.ey ← edge[2].coord.ey+offSetX1;

edge[3].coord.ex ← edge[3].coord.ex-offSetY2; edge[3].coord.ey ← edge[3].coord.ey+offSetX2;

edge[4].coord.ex ← edge[4].coord.ex+offSetX2; edge[4].coord.ey ← edge[4].coord.ey+offSetY2;

edge[5].coord.ex ← edge[5].coord.ex+offSetY2; edge[5].coord.ey ← edge[5].coord.ey-offSetX2;

IF patch.dir = back THEN FOR i: NAT IN [0..3) DO -- reverse order to make backfacing

temp: VertexInfo ← edge[i]; edge[i] ← edge[5-i]; edge[5-i] ← temp;

ENDLOOP;

IF edge.clipState = in THEN FOR i: NAT IN [0..6) DO

OPEN edge[i].coord;

[[sx, sy, sz]] ← ShapeUtilities.XfmPtToDisplay[ context, [ex, ey, ez] ];

ENDLOOP;

[] ← OutputPolygon[context, edge];

};

shape: REF ShapeInstance ← NARROW[ Atom.GetPropFromList[patch.props, $Shape] ];

baseRadius: REAL ← .003;

limit: NAT ← IF patch.type = $PolyLine THEN patch.nVtces - 1 ELSE patch.nVtces;

IF dummyShape.shadingClass = NIL THEN {

G3dRender.LoadShadingClass[dummyShape];

dummyShape.shadingClass.shadingType ← $Smooth;

};

dummyShape.shadingClass.color ← shape.shadingClass.color;

{

IF patch.dir = undetermined THEN patch.dir ← ShapeUtilities.BackFacing[

context, patch

! G3dRender.Error => IF reason.code = $Condition THEN GO TO GiveUp

];

IF patch.dir = front OR NOT patch.oneSided THEN FOR i: NAT IN [0..limit) DO

edge: REF Patch ← ShapeUtilities.GetPatch[6]; -- will be released by OutputPolygon

edge.type ← $ConvexPolygon;

edge.nVtces ← 6;

edge.oneSided ← patch.oneSided;

edge.dir ← patch.dir;

edge.clipState ← patch.clipState;

edge.props ← Atom.PutPropOnList[ NIL, $Shape, dummyShape ];

MakeEdge[ patch[i], patch[(i+1) MOD patch.nVtces], edge ];

ENDLOOP;

EXITS GiveUp => NULL

};

ShapeUtilities.ReleasePatch[patch]; -- end of the line for this patch

RETURN[NIL];

};

OutputPolygon: PUBLIC PatchProc ~ {

PROC[ context: REF Context, patch: REF Patch, data: REF ANY ← NIL ] RETURNS[REF Patch]

shape: REF ShapeInstance ← NARROW[ Atom.GetPropFromList[patch.props, $Shape] ];

{ IF patch = NIL OR patch.clipState = out THEN GO TO CleanUp; -- reject if outside frame

IF patch.type # $ConvexPolygon AND patch.type # $PolyLine THEN {

SIGNAL G3dRender.Error[[$MisMatch, "Not a Polygon or PolyLine"]];

GO TO CleanUp; -- catches unexpanded patches, etc.

};

IF context.antiAliasing AND
( patch.type = $PolyLine OR shape.shadingClass.shadingType = $Lines
OR shape.shadingClass.shadingType = $ShadedLines ) -- antialiased lines

THEN { patch ← EdgesToPolygons[context, patch]; GO TO CleanUp; };

IF patch.clipState = clipped THEN {

patch ← ShapeUtilities.ClipPoly[context, patch];

IF patch.nVtces > 2 OR ( patch.type = $PolyLine AND patch.nVtces > 1 ) THEN {

FOR i: NAT IN [0..patch.nVtces) DO OPEN patch[i].coord;

[[sx, sy, sz]] ← ShapeUtilities.XfmPtToDisplay[context, [ex, ey, ez]];

ENDLOOP;

};

IF patch.nVtces > 2 OR ( patch.type = $PolyLine AND patch.nVtces > 1 ) THEN {

IF patch.type = $PolyLine OR shape.shadingClass.shadingType = $Lines THEN {

patch ← context.class.displayPolygon[context, patch];

GO TO GiveUp;

};

IF patch.dir = undetermined THEN patch.dir ← ShapeUtilities.BackFacing[

context, patch

! G3dRender.Error => IF reason.code = $Condition THEN GO TO GiveUp

];

IF patch.dir = front

THEN patch ← context.class.displayPolygon[context, patch]

ELSE IF patch.oneSided -- backfacing!!

THEN GO TO GiveUp -- Reject if closed surface

ELSE {

IF shape.shadingClass.shadingType # $HiddenLines AND
shape.shadingClass.shadingType # $NormaledLines THEN FOR i: NAT IN [0..patch.nVtces) DO -- recalculate shading for back side

patch[i].shade.exn ← -patch[i].shade.exn; -- reverse normals

patch[i].shade.eyn ← -patch[i].shade.eyn;

patch[i].shade.ezn ← -patch[i].shade.ezn;

patch[i] ← shape.shadingClass.shadeVtx[context, patch[i], shape.shadingClass];

ENDLOOP;

FOR i: NAT IN [0..patch.nVtces/2) DO -- reorder to keep clockwise on display

tempVtx: VertexInfo ← patch[i];

patch[i] ← patch[patch.nVtces-1 - i];

patch[patch.nVtces-1 - i] ← tempVtx;

ENDLOOP;

patch ← context.class.displayPolygon[context, patch]

};

EXITS GiveUp => NULL

};

EXITS CleanUp => NULL;

};

IF patch # NIL THEN ShapeUtilities.ReleasePatch[patch];

RETURN[NIL]; -- end of the line, nobody wants this polygon back certainly

};

RopeDisplay: PUBLIC PatchProc ~ {

shape: REF ShapeInstance ← NARROW[ Atom.GetPropFromList[patch.props, $Shape] ];

msg: Rope.ROPE ← NARROW[ Atom.GetPropFromList[shape.fixedProps, $RopeMessage ] ];

font: Rope.ROPE ← NARROW[ Atom.GetPropFromList[shape.fixedProps, $RopeFont ] ];

xfm: Xfm3D ← G3dMatrix.Mul[shape.position, context.eyeSpaceXfm];

color: Pixel ← [

Real.Fix[shape.shadingClass.color.R*255.0],

Real.Fix[shape.shadingClass.color.G*255.0],

Real.Fix[shape.shadingClass.color.B*255.0],

0, 0 ];

position: Triple ← [shape.vertex[0].sx, shape.vertex[0].sy, shape.vertex[0].sz];

position2: Triple ← [shape.vertex[1].sx, shape.vertex[1].sy, shape.vertex[1].sz];

size: REAL ← G3dVector.Length[ G3dVector.Sub[position2, position] ];

IF context.antiAliasing -- ensure entire rope represented

THEN shape.screenExtent.max.f ← Real.Round[context.viewPort.w];

context.class.draw2DRope[

context, msg,

[ position.x/context.ndcToPixels.scaleX, 1.0 - position.y/ABS[context.ndcToPixels.scaleY] ],

color, size, font

];

RETURN[NIL];

};

Frame Generation and Animation

MakeFrame: PUBLIC ContextProc ~ {

MakeTheFrame[context];

};

ShowShapes: PUBLIC ContextProc ~ {

Makes image without clearing frame, for compositing contexts, etc.

delay: BOOLEAN ← context.delayClear;

context.delayClear ← FALSE; -- avoids frame clear before making new frame

MakeTheFrame[context: context, clear: FALSE];

context.delayClear ← delay;

};

MakeTheFrame: PROC[context: REF Context, clear: BOOLEAN ← TRUE] ~ {

Makes image, clears frame, etc.

Action: PROC ~ {

allLines: BOOLEAN ← TRUE;

time: REAL ← CurrentTime[];

log: IO.STREAM ← NARROW[ Atom.GetPropFromList[context.props, $Log] ];

context.stopMe^ ← FALSE; -- get stop flag unstuck, if necessary

context.imageReady ← FALSE; -- discourage use of bits by other processes

context.extentCovered ← [[0,0], [0,0]]; -- clear bounding box of coverage

ValidateContext[context]; -- update everything

FOR i: NAT IN [0..context.shapes.length) DO

IF context.shapes[i].class.doBeforeFrame # NIL THEN -- execute animation updates

FOR doList: LIST OF ShapeProc ← context.shapes[i].class.doBeforeFrame, doList.rest

UNTIL doList = NIL DO

context.shapes[i] ← doList.first[context, context.shapes[i]];

ENDLOOP;

IF log # NIL THEN log.PutRope[ Rope.Cat[ " VtxOps: ", ElapsedTime[time] ] ];

IF clear AND NOT context.delayClear

THEN context.class.loadBackground[context]; -- load background

IF context.visibleShapes # NIL AND context.visibleShapes.length > 0

THEN {

FOR i: NAT IN [0 .. context.visibleShapes.length) DO -- all line drawing?

IF context.visibleShapes[i].shadingClass.shadingType # $Lines

THEN allLines ← FALSE;

ENDLOOP;

IF allLines AND NOT context.antiAliasing

THEN ShowWireFrameObjects[ context ]

ELSE ShowObjects[ context: context, frontToBack: context.antiAliasing ];

context.imageReady ← TRUE; -- encourage use of bits by other processes

IF log # NIL THEN {

log.PutRope[ Rope.Cat[ " Frame: ", ElapsedTime[time], "\n"] ];

FlushLog[context];

};

}

ELSE {

IF log # NIL THEN {

log.PutRope[" No visible objects in frame " ];

FlushLog[context];

};

CedarProcess.DoWithPriority[background, Action];

};

END.