[Indigo]<3DGraphics>RenderShop>StandardPatchProcs.mesa!3

StandardPatchProcs.mesa

Last Edited by: Crow, May 3, 1989 3:46:05 pm PDT

DIRECTORY Atom, Basics, G3dBasic, G3dMatrix, G3dRender, G3dScanConvert, G3dShadeClipXfm, G3dSortandDisplay, G3dVector, Real, RealFns;

StandardPatchProcs: CEDAR MONITOR

IMPORTS Atom, Basics, G3dMatrix, G3dRender, G3dShadeClipXfm, G3dSortandDisplay, G3dVector, Real, RealFns

= BEGIN

Internal Declarations

Ray: TYPE ~ G3dBasic.Ray;

RGB: TYPE ~ G3dRender.RGB;

RealSequence: TYPE ~ G3dRender.RealSequence;

Context: TYPE ~ G3dRender.Context;

SixSides: TYPE ~ G3dRender.SixSides;

Pair: TYPE ~ G3dRender.Pair;

Triple: TYPE ~ G3dRender.Triple;

Matrix: TYPE ~ G3dRender.Matrix;

Shape: TYPE ~ G3dRender.Shape;

ShapeClass: TYPE ~ G3dRender.ShapeClass;

RenderStyle: TYPE ~ G3dRender.RenderStyle;

ShapeProc: TYPE ~ G3dRender.ShapeProc;

RenderData: TYPE ~ G3dRender.RenderData;

Patch: TYPE ~ G3dRender.Patch;

PatchSequence: TYPE ~ G3dRender.PatchSequence;

PatchSequenceRep: TYPE ~ G3dRender.PatchSequenceRep;

PatchProc: TYPE ~ G3dRender.PatchProc;

CtlPoint: TYPE ~ G3dRender.CtlPoint;

CtlPtInfo: TYPE ~ G3dRender.CtlPtInfo;

CtlPtInfoSequence: TYPE ~ G3dRender.CtlPtInfoSequence;

CtlPtInfoSequenceRep: TYPE ~ G3dRender.CtlPtInfoSequenceRep;

CtlPtInfoProc: TYPE ~ G3dRender.CtlPtInfoProc;

ClipState: TYPE ~ G3dRender.ClipState;

OutCode: TYPE ~ G3dRender.OutCode;

AllOut: OutCode ~ G3dRender.AllOut;

NoneOut: OutCode ~ G3dRender.NoneOut;

FacingDir: TYPE ~ G3dRender.FacingDir;

FacingDirArray: TYPE ~ ARRAY [0..9) OF FacingDir;

MidPtProc: TYPE ~ PROC[v0, v1: REF CtlPtInfo, texture: BOOLEAN ← FALSE]
RETURNS[REF CtlPtInfo];

LORA: TYPE = LIST OF REF ANY;

maxDeviation: REAL ← 0.25; -- subdivision tolerance with antialiasing in pixels

maxInteriorDev: REAL ← 0.25; -- (1.0) tolerance on internal edges

maxJaggyDeviation: REAL ← 1.0; -- jaggy subdivision tolerance in pixels

maxJaggyInteriorDev: REAL ← 1.0; -- (4.0) tolerance on internal edges

closenessFactor: REAL ← 20.0; -- times maxDeviation gets clipping cutoff for straightness

recurseLimit: NAT ← 14; -- safety valve on recursion

stopIfStraight: BOOLEAN ← TRUE; -- set false to defeat termination algorithm

stopOnDegenerate: BOOLEAN ← FALSE; -- signals on badly degenerate patches

showLines: BOOLEAN ← FALSE; -- debug and pedagogical aid

showCtlPts: BOOLEAN ← FALSE; -- debug and pedagogical aid

refPt5: REF REAL ← NEW[REAL ← 0.5];

Renamed Procedures

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

Utility Procedures

ShowCoords: PROC[poly: REF Patch, space: ATOM ← $Screen]
RETURNS[list: LIST OF REF Pair] ~ {

FOR i: CARD16 DECREASING IN [0..poly.nVtces) DO

p: REF Pair;

SELECT space FROM

$Screen => p ← NEW[ Pair ← [ poly[i].coord.sx, poly[i].coord.sy ] ];

$Eye => p ← NEW[ Pair ← [ poly[i].coord.ex, poly[i].coord.ey ] ];

$Object => p ← NEW[ Pair ← [ poly[i].coord.x, poly[i].coord.y ] ];

ENDCASE;

list ← CONS[p, list];

ENDLOOP;

RETURN[list];

};

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

CopyVtx: PROC[vtx: CtlPtInfo] RETURNS[vtxOut: REF CtlPtInfo] ~ {

vtxOut ← G3dShadeClipXfm.GetCtlPtInfo[];

vtxOut^ ← vtx;

};

Sub: PROC[f, g: REAL] RETURNS[REAL] ~ {

Difference f - g, returns zero if less than 6 decimal places

IF RealFns.AlmostEqual[f, g, -20] THEN RETURN [0.0] ELSE RETURN[f-g];

};

Sub1: PROC[f, g: REAL] RETURNS[REAL] ~ {

Screen space f - g, returns zero if less than noticeable

result: REAL ← f-g;

IF ABS[result] < G3dScanConvert.justNoticeable THEN RETURN [0.0] ELSE RETURN[result];

};

DiffTriple: PROC[v1, v2: Triple] RETURNS[Triple] ~ {

RETURN[[Sub[v1.x, v2.x], Sub[v1.y, v2.y], Sub[v1.z, v2.z]]];

};

DiffPosns: PROC[vtx1, vtx2: CtlPoint, space: ATOM ← NIL] RETURNS[Triple] ~ {

SELECT space FROM

$Eye => RETURN[[Sub[vtx1.ex, vtx2.ex], Sub[vtx1.ey, vtx2.ey], Sub[vtx1.ez, vtx2.ez]]];

$Screen=> RETURN[[Sub1[vtx1.sx, vtx2.sx], Sub1[vtx1.sy, vtx2.sy], Sub1[vtx1.sz, vtx2.sz]]];

ENDCASE => -- object space

RETURN[[Sub[vtx1.x, vtx2.x], Sub[vtx1.y, vtx2.y], Sub[vtx1.z, vtx2.z]]];

};

VtxDisplayMidPt: MidPtProc ~ {

PROC[v0, v1: REF CtlPtInfo, texture: BOOLEAN ← FALSE] RETURNS[REF CtlPtInfo]

v: REF CtlPtInfo ← G3dShadeClipXfm.GetCtlPtInfo[];

v.coord.sx ← (v0.coord.sx + v1.coord.sx) / 2; -- for position on screen

v.coord.sy ← (v0.coord.sy + v1.coord.sy) / 2;

v.coord.sz ← (v0.coord.sz + v1.coord.sz) / 2;

v.coord.ex ← (v0.coord.ex + v1.coord.ex) / 2; -- for normal-vector shading

v.coord.ey ← (v0.coord.ey + v1.coord.ey) / 2;

v.coord.ez ← (v0.coord.ez + v1.coord.ez) / 2;

[[v.coord.sx, v.coord.sy, v.coord.sz]] ← G3dShadeClipXfm.XfmPtToDisplay[

context, [v.coord.ex, v.coord.ey, v.coord.ez]

];

v.shade.r ← (v0.shade.r + v1.shade.r) / 2; -- for color-per-vertex (could be avoided)

v.shade.g ← (v0.shade.g + v1.shade.g) / 2;

v.shade.b ← (v0.shade.b + v1.shade.b) / 2;

IF texture THEN {

v.shade.txtrX ← (v0.shade.txtrX + v1.shade.txtrX) / 2;

v.shade.txtrY ← (v0.shade.txtrY + v1.shade.txtrY) / 2;

v.coord.x ← (v0.coord.x + v1.coord.x) / 2; -- original coords (for solid texture)

v.coord.y ← (v0.coord.y + v1.coord.y) / 2;

v.coord.z ← (v0.coord.z + v1.coord.z) / 2;

};

RETURN[v];

};

TooClose: PROC[ context: Context, v: CtlPoint, outCode: OutCode, tol: REAL ]
RETURNS[BOOLEAN] ~ {

Find max distance from screen edge on inside

maxDist: REAL ← 0.0;

IF v.sz = 0.0 THEN RETURN [FALSE]; -- invalid screen coord, ignore

IF outCode.left

THEN maxDist ← MAX[maxDist, v.sx - context.viewPort.x];

IF outCode.right

THEN maxDist ← MAX[maxDist, context.viewPort.w + context.viewPort.x - v.sx];

IF outCode.bottom

THEN maxDist ← MAX[maxDist, v.sy - context.viewPort.y];

IF outCode.top

THEN maxDist ← MAX[maxDist, context.viewPort.h + context.viewPort.y - v.sy];

IF maxDist < tol * closenessFactor THEN RETURN[TRUE] ELSE RETURN[FALSE];

};

MakeStraight: PROC[ v0, v1, vMid: CtlPtInfo, texture: BOOLEAN ← FALSE ]
RETURNS[CtlPtInfo] ~ {

Interpolate displayed values to point defined by projection of vMid on v1 - v0

a, b, alpha: REAL;

Projection given by dot product normalized by magnitude of v1 - v0

mag: REAL ← RealFns.SqRt[ Sqr[v1.coord.sx - v0.coord.sx] + Sqr[v1.coord.sy - v0.coord.sy] ];

IF mag < G3dScanConvert.justNoticeable -- effectively invisible detail

THEN { vMid.coord ← v0.coord; vMid.shade ← v0.shade; RETURN[vMid]; };

alpha ← ( (vMid.coord.sx - v0.coord.sx) * (v1.coord.sx - v0.coord.sx) -- vMid-v0 dot v1-v0
+ (vMid.coord.sy - v0.coord.sy) * (v1.coord.sy - v0.coord.sy) ) / Sqr[mag];

a ← 1.0 - alpha; b ← alpha;

vMid.coord.sx ← a * v0.coord.sx + b * v1.coord.sx ; -- screen coords (for scan conversion)

vMid.coord.sy ← a * v0.coord.sy + b * v1.coord.sy ;

vMid.coord.sz ← a * v0.coord.sz + b * v1.coord.sz ;

Don't straighten eyespace coords, will cause shading discontinuities

vMid.shade.r ← a * v0.shade.r + b * v1.shade.r ; -- surface color

vMid.shade.g ← a * v0.shade.g + b * v1.shade.g ;

vMid.shade.b ← a * v0.shade.b + b * v1.shade.b ;

IF texture THEN {

vMid.shade.txtrX ← a * v0.shade.txtrX + b * v1.shade.txtrX;

vMid.shade.txtrY ← a * v0.shade.txtrY + b * v1.shade.txtrY;

vMid.coord.x ← a * v0.coord.x + b * v1.coord.x ; -- original coords (for solid texture)

vMid.coord.y ← a * v0.coord.y + b * v1.coord.y ;

vMid.coord.z ← a * v0.coord.z + b * v1.coord.z ;

};

RETURN[vMid];

};

SetStraight: PROC[ p: REF Patch, v0, v1, v2, v3: NAT] ~ {

Straight! Force inner display values to lie on line between patch corners

p[v1] ← MakeStraight[ p[v0], p[v3], p[v1] ];

p[v2] ← MakeStraight[ p[v0], p[v3], p[v2] ];

p[v0].data ← $Straight;

};

StraightWithin: PROC[ context: Context, p: REF Patch, v0, v1, v2, v3: NAT,
lilTol, bigTol: REAL] RETURNS[BOOLEAN] ~ {

StraightenUp: PROC[] ~ {

Length of control poly within tolerated deviation from linear

p[v0].data ← $Straight;

};

InteriorEdge: PROC[] RETURNS[BOOLEAN] ~ {

All control point polygons touched by this edge face the same way

PolyNo: PROC[v: INTEGER] RETURNS[NAT] ~ {

i: NAT ← MAX[v / 4 -1 , 0]; j: NAT ← MAX[v MOD 4 -1 , 0]; RETURN[ i*3 + j ];

};

facingDir: FacingDir;

subDirs: REF FacingDirArray ← NARROW[

Atom.GetPropFromList[p.props, $FacingDirArray]

];

IF subDirs = NIL THEN RETURN[FALSE];

facingDir ← subDirs[PolyNo[v0]];

IF subDirs[PolyNo[v1]] # facingDir THEN RETURN[FALSE];

IF subDirs[PolyNo[v2]] # facingDir THEN RETURN[FALSE];

IF subDirs[PolyNo[v3]] # facingDir THEN RETURN[FALSE];

IF facingDir = unknown THEN RETURN[FALSE];

RETURN[TRUE];

};

DistOffEdge: PROC[v: CtlPoint, line: Ray] RETURNS[REAL] ~ {

ptOnEdge: Triple ← G3dShadeClipXfm.XfmPtToDisplay[

context, G3dVector.NearestToLine[line, [v.ex, v.ey, v.ez]]

];

vs: Triple ← G3dShadeClipXfm.XfmPtToDisplay[ context, [v.ex, v.ey, v.ez] ];

RETURN[ RealFns.SqRt[ Sqr[ptOnEdge.x - vs.x] + Sqr[ptOnEdge.y - vs.y] ] ];

};

dist1, dist2, dist3, baseDist, a, b: REAL ← 0.0;

reversed: BOOLEAN ← FALSE;

IF p[v0].data = $Straight THEN RETURN[TRUE];

a ← p[v3].coord.sy - p[v0].coord.sy; b ← p[v3].coord.sx - p[v0].coord.sx;

baseDist ← RealFns.SqRt[a*a + b*b];

IF baseDist > G3dScanConvert.justNoticeable THEN {

a ← a/baseDist; b ← b/baseDist; -- get normalized distances from v0-v3

dist1 ← a * (p[v1].coord.sx - p[v0].coord.sx) + b * (p[v0].coord.sy - p[v1].coord.sy);

IF ABS[dist1] > bigTol THEN RETURN[FALSE];

dist2 ← a * (p[v2].coord.sx - p[v0].coord.sx) + b * (p[v0].coord.sy - p[v2].coord.sy);

IF ABS[dist2] > bigTol THEN RETURN[FALSE];

IF p.renderData.shadingClass.texture # NIL THEN {

Watch for perspective depth distortion here

point: Triple ← [p[v0].coord.ex, p[v0].coord.ey, p[v0].coord.ez];

line: Ray ← [ point, DiffPosns[p[v3].coord, p[v0].coord, $Eye] ];

Get screen distance of inner knots from edge formed by outer knots

dist1: REAL ← DistOffEdge[p[v1].coord, line];

dist2: REAL ← DistOffEdge[p[v2].coord, line];

IF dist1 > bigTol OR dist2 > bigTol THEN RETURN[FALSE];

};

SELECT TRUE FROM

MAX[dist1, dist2] < lilTol => { -- inside minimum deviation used onshape boundary

StraightenUp[]; RETURN[ TRUE ]; };

p.dir # unknown => { StraightenUp[]; RETURN[ TRUE ]; }; -- interior patch

InteriorEdge[] => { StraightenUp[]; RETURN[ TRUE ]; }; -- interior edge

ENDCASE => RETURN[ FALSE ];

};

PutPropSafely: PROC[propList: Atom.PropList, prop, val: REF ANY] RETURNS[Atom.PropList] ~{

Put property on new property list, to avoid clobbering other lists inherited from same place

newProps: Atom.PropList ← NIL;

FOR list: Atom.PropList ← propList, list.rest UNTIL list = NIL DO -- new proplist

element: Atom.DottedPair ← NEW[Atom.DottedPairNode ← list.first^];

newProps ← CONS[element, newProps];

ENDLOOP;

RETURN[ Atom.PutPropOnList[ newProps, prop, val ] ];

};

PatchSort: PROC[ context: Context, p0, p1, p2, p3: REF Patch]
RETURNS[REF Patch, REF Patch, REF Patch, REF Patch] ~ {

z: ARRAY[0..4) OF REAL;

pOut: ARRAY[0..4) OF REF Patch;

Get average of depths at corners

z[0] ← (p0[0].coord.ez + p0[12].coord.ez + p0[15].coord.ez + p0[3].coord.ez)/4; pOut[0] ← p0;

z[1] ← (p1[0].coord.ez + p1[12].coord.ez + p1[15].coord.ez + p1[3].coord.ez)/4; pOut[1] ← p1;

z[2] ← (p2[0].coord.ez + p2[12].coord.ez + p2[15].coord.ez + p2[3].coord.ez)/4; pOut[2] ← p2;

z[3] ← (p3[0].coord.ez + p3[12].coord.ez + p3[15].coord.ez + p3[3].coord.ez)/4; pOut[3] ← p3;

FOR i: NAT IN [1..4) DO

FOR j: NAT DECREASING IN [0..i) DO -- sort to increasing depth order

IF z[j+1] < z[j] THEN {

t: REAL ← z[j+1]; p: REF Patch ← pOut[j+1];

z[j+1] ← z[j]; pOut[j+1] ← pOut[j];

z[j] ← t; pOut[j] ← p;

};

ENDLOOP;

IF context.antiAliasing

THEN RETURN[ pOut[0], pOut[1], pOut[2], pOut[3] ]

ELSE RETURN[ pOut[3], pOut[2], pOut[1], pOut[0] ];

};

ValidatePatchShape: ShapeProc ~ { --

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

Update shading and transform matrices)

render: REF RenderData ← G3dRender.RenderDataFrom[shape];

renderStyle: RenderStyle;

xfm: Matrix ← G3dMatrix.Mul[shape.matrix, context.eyeSpaceXfm];

allPolysIn, allPolysOut: BOOLEAN ← TRUE;

WITH render.shadingClass.renderMethod SELECT FROM

style: REF RenderStyle => renderStyle ← style^;

ENDCASE => renderStyle ← smooth; -- default to smooth

IF GetProp[render.props, $Hidden] # NIL THEN RETURN[shape]; -- don't bother, not visible

IF NOT render.patchesValid OR context.changed OR render.patch = NIL THEN {

IF render.patch = NIL THEN {

Build patch sequence for shape

render.patch ← NEW[PatchSequenceRep[shape.surfaces.length]];

render.patch.length ← shape.surfaces.length;

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

render.patch[i] ← NEW[Patch[shape.surfaces[i].length]];

FOR j: NAT IN [0..shape.surfaces[i].length) DO

vtx: NAT ← shape.surfaces[i][j];

render.patch[i][j].coord.x ← shape.vertices[vtx].point.x;

render.patch[i][j].coord.y ← shape.vertices[vtx].point.y;

render.patch[i][j].coord.z ← shape.vertices[vtx].point.z;

render.patch[i][j].shade.xn ← shape.vertices[vtx].normal.x;

render.patch[i][j].shade.yn ← shape.vertices[vtx].normal.y;

render.patch[i][j].shade.zn ← shape.vertices[vtx].normal.z;

render.patch[i][j].shade.txtrX ← shape.vertices[vtx].texture.x;

render.patch[i][j].shade.txtrY ← shape.vertices[vtx].texture.y;

render.patch[i][j].vtxPtr ← vtx;

ENDLOOP;

render.patch[i].nVtces ← shape.surfaces[i].length;

render.patch[i].type ← shape.type;

render.patch[i].oneSided ← NOT shape.showBackfaces;

render.patch[i].renderData ← render; -- store REF to shading information

ENDLOOP;

};

shape.screenExtent ← [[32768, 32768], [0, 0]]; -- initialize for computing screenExtent

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

Transform and shade vertices, get clip state for each polygon

andOfCodes: OutCode ← AllOut; -- test for trivially out

orOfCodes: OutCode ← NoneOut; -- test for trivially in

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

OPEN render.patch[i][j].coord; -- transform control points to eyespace

[ [ex, ey, ez] ] ← G3dMatrix.Transform[ [x, y, z] , xfm];

IF shape.clipState = clipped

THEN {

clip ← G3dShadeClipXfm.GetClipCodeForPt[ context, [ex, ey, ez] ];

orOfCodes ← LOOPHOLE[

Basics.BITOR[LOOPHOLE[orOfCodes], LOOPHOLE[ clip] ], OutCode];

andOfCodes ← LOOPHOLE[

Basics.BITAND[ LOOPHOLE[andOfCodes], LOOPHOLE[ clip] ], OutCode];

}

ELSE clip ← NoneOut;

Plain lines take object color

IF renderStyle = lines

THEN {

OPEN render.patch[i][j].shade;

[er, eg, eb] ← render.shadingClass.color;

}

Else take vertex and face colors

ELSE {

OPEN render.patch[i][j].shade;

vtx: NAT ← render.patch[i][j].vtxPtr;

[r, g, b] ← shape.vertices[vtx].color; t ← shape.vertices[vtx].transmittance;

IF shape.faces # NIL THEN IF shape.faces.valid.color THEN { -- scale w/ face clr

clr: Triple ← shape.faces[i].color; r ← clr.x * r; g ← clr.y * g; b ← clr.z * b;

};

ENDLOOP;

Collect clipping data for vertices to tag patches, patches to tag shapes

IF orOfCodes = NoneOut THEN render.patch[i].clipState ← in -- default case

ELSE IF andOfCodes # NoneOut THEN render.patch[i].clipState ← out

ELSE render.patch[i].clipState ← clipped;

IF shape.clipState = clipped THEN {

allPolysIn ← allPolysIn AND (render.patch[i].clipState = in);

allPolysOut ← allPolysOut AND (render.patch[i].clipState = out);

};

Get screen coordinates for on-screen patches

IF render.patch[i].clipState # out THEN FOR j: NAT IN [0..render.patch[i].nVtces) DO

OPEN render.patch[i][j].coord; -- xfm to display, update shape screen extent

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

ENDLOOP;

render.patchesValid ← TRUE;

};

RETURN[shape];

};

Initialization of Classes

InitClasses: PROC[] ~ { -- register procedures for basic surface types

standardClass: ShapeClass ← G3dRender.GetShapeClass[$ConvexPolygon];

standardClass.type ← $Bezier;

standardClass.validate ← ValidatePatchShape;

standardClass.displayPatch ← BezierDisplay;

G3dRender.RegisterShapeClass[standardClass, $Bezier];

standardClass.type ← $BSpline;

standardClass.validate ← ValidatePatchShape;

standardClass.displayPatch ← BSplineDisplay;

G3dRender.RegisterShapeClass[standardClass, $BSpline];

standardClass.type ← $NonConvexPolygon;

standardClass.validate ← G3dSortandDisplay.ValidatePolyhedron;

standardClass.displayPatch ← NonConvexDisplay;

G3dRender.RegisterShapeClass[standardClass, $NonConvexPolygon];

};

Procedures for expansion of Bezier patches to convex polygons

BezierDisplay: PatchProc ~ {

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

renderStyle: RenderStyle;

WITH patch.renderData.shadingClass.renderMethod SELECT FROM

style: REF RenderStyle => {

renderStyle ← style^;

SELECT renderStyle FROM

lines => { [] ← BezierDisplayLines[context, patch]; RETURN[NIL]; };

controlPoints => { [] ← BezierDisplayCtrlPts[context, patch]; RETURN[NIL]; };

ENDCASE;

};

ENDCASE;

patch ← BezierClipState[context, patch];

IF patch.nVtces = 16 -- Divide till all outside patch edges are straight or recursion exceeded

THEN BezierPatchDisplay[context, patch, 0]

ELSE IF patch.nVtces = 10

THEN BezierTriangleDisplay[ context, patch, MIN[6, recurseLimit] ];

RETURN[patch]; -- patch should be unmodified

};

BezierPatchDisplay: PROC[ context: Context, p: REF Patch, level: NAT] ~ {

allStraight: BOOLEAN ← TRUE;

lilTol: REAL ← IF context.antiAliasing THEN maxDeviation ELSE maxJaggyDeviation;

bigTol: REAL ← IF context.antiAliasing THEN maxInteriorDev ELSE maxJaggyInteriorDev;

Quit if out of field of view or all polys in convex hull point away from observer

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

IF p.clipState = out THEN RETURN[];

IF p.oneSided AND p.dir = back THEN RETURN[]; -- backfacing on closed surface

IF p.clipState = unknown

THEN allStraight ← FALSE

ELSE { -- Straightness test on patch boundary, if straight enough, force straightness

IF NOT StraightWithin[context, p, 0, 4, 8,12, lilTol, bigTol] THEN allStraight ← FALSE;

IF NOT StraightWithin[context, p,12,13,14,15, lilTol, bigTol] THEN allStraight ← FALSE;

IF NOT StraightWithin[context, p,15,11, 7, 3, lilTol, bigTol] THEN allStraight ← FALSE;

IF NOT StraightWithin[context, p, 3, 2, 1, 0, lilTol, bigTol] THEN allStraight ← FALSE;

};

IF stopIfStraight AND allStraight OR level >= recurseLimit

THEN IF showCtlPts -- outer edges straight, display as polygon

THEN p ← BezierDisplayCtrlPts[context, p]

ELSE {

p ← PolygonFromBezierPatch[p]; -- construct polygon

G3dShadeClipXfm.ShadePoly[context, p];

IF showLines THEN p.type ← $PolyLine;

p ← G3dSortandDisplay.OutputPolygon[context, p]; -- display

}

ELSE { -- not straight enough, subdivide and recurse

p0, p1, p2, p3: REF Patch;

[p0, p1, p2, p3] ← BezierPatchDivide[ context, p, VtxDisplayMidPt ]; -- subdivide

IF NOT context.depthBuffering

THEN [p0, p1, p2, p3] ← PatchSort[ context, p0, p1, p2, p3]; -- sort to display order

display in order

BezierPatchDisplay[context, p0, level+1]; BezierPatchDisplay[context, p1, level+1];

BezierPatchDisplay[context, p2, level+1]; BezierPatchDisplay[context, p3, level+1];

};

IF level > 0 THEN G3dShadeClipXfm.ReleasePatch[p]; -- end of life for sub-patch

};

BezierTriangleDisplay: PROC[ context: Context, p: REF Patch, divisions: NAT] ~ {

MdPt: PROC[v0, v1, v2: CtlPtInfo, r, s, t: REAL] RETURNS[CtlPtInfo] ~ {

v: CtlPtInfo;

v.coord.sx ← r * v0.coord.sx + s * v1.coord.sx + t * v2.coord.sx; -- for position on screen

v.coord.sy ← r * v0.coord.sy + s * v1.coord.sy + t * v2.coord.sy;

v.coord.sz ← r * v0.coord.sz + s * v1.coord.sz + t * v2.coord.sz;

v.coord.ex ← r * v0.coord.ex + s * v1.coord.ex + t * v2.coord.ex; -- for nml-vector shading

v.coord.ey ← r * v0.coord.ey + s * v1.coord.ey + t * v2.coord.ey;

v.coord.ez ← r * v0.coord.ez + s * v1.coord.ez + t * v2.coord.ez;

v.shade.r ← r * v0.shade.r + s * v1.shade.r + t * v2.shade.r; -- clr/vtx (could be avoided)

v.shade.g ← r * v0.shade.g + s * v1.shade.g + t * v2.shade.g;

v.shade.b ← r * v0.shade.b + s * v1.shade.b + t * v2.shade.b;

IF p.renderData.shadingClass.texture # NIL THEN {

v.shade.txtrX ← r * v0.shade.txtrX + s * v1.shade.txtrX + t * v2.shade.txtrX;

v.shade.txtrY ← r * v0.shade.txtrY + s * v1.shade.txtrY + t * v2.shade.txtrY;

v.coord.x ← r * v0.coord.x + s * v1.coord.x + t * v2.coord.x;

v.coord.y ← r * v0.coord.y + s * v1.coord.y + t * v2.coord.y;

v.coord.z ← r * v0.coord.z + s * v1.coord.z + t * v2.coord.z;

};

RETURN[v];

};

EvalTriangle: PROC[p: REF Patch, r, s, t: REAL] RETURNS[CtlPtInfo] ~ {

[Artwork node; type 'Artwork on' to command tool]

p1: ARRAY[0..6) OF CtlPtInfo;

p2: ARRAY[0..3) OF CtlPtInfo;

p3: CtlPtInfo;

p1[0] ← MdPt[p[1], p[8], p[0], r,s,t]; -- p1[0,0,2] ← r*p[1,0,2] + s*p[0,1,2] + t*p[0,0,3];

p1[2] ← MdPt[p[3], p[4], p[2], r,s,t]; -- p1[2,0,0] ← r*p[3,0,0] + s*p[2,1,0] + t*p[2,0,1];

p1[4] ← MdPt[p[5], p[6], p[7], r,s,t]; -- p1[0,2,0] ← r*p[1,2,0] + s*p[0,3,0] + t*p[0,2,1];

p1[1] ← MdPt[p[2], p[9], p[1], r,s,t]; -- p1[1,0,1] ← r*p[2,0,1] + s*p[1,1,1] + t*p[1,0,2];

p1[3] ← MdPt[p[4], p[5], p[9], r,s,t]; -- p1[1,1,0] ← r*p[2,1,0] + s*p[1,2,0] + t*p[1,1,1];

p1[5] ← MdPt[p[9], p[7], p[8], r,s,t]; -- p1[0,1,1] ← r*p[1,1,1] + s*p[0,2,1] + t*p[0,1,2];

p2[0] ← MdPt[p1[1], p1[5], p1[0], r,s,t]; -- p2[0,0,1] ← r*p[1,0,1] + s*p[0,1,1] + t*p[0,0,2];

p2[1] ← MdPt[p1[2], p1[3], p1[1], r,s,t]; -- p2[1,0,0] ← r*p[2,0,0] + s*p[1,1,0] + t*p[1,0,1];

p2[2] ← MdPt[p1[3], p1[4], p1[5], r,s,t]; -- p2[0,1,0] ← r*p[1,1,0] + s*p[0,2,0] + t*p[0,1,1];

p3 ← MdPt[p2[1], p2[2], p2[0], r,s,t]; -- p3[0,0,0] ← r*p[1,0,0] + s*p[0,1,0] + t*p[0,0,1];

RETURN[p3];

};

steps: NAT ← INTEGER[Basics.BITSHIFT[ 1, divisions ]];

rotateBy: NAT;

Quit if out of field of view or all polys in convex hull point away from observer

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

IF p.clipState = out THEN RETURN[];

IF p.oneSided AND p.dir = back THEN RETURN[]; -- backfacing on closed surface

IF p[6].coord.ez > p[3].coord.ez -- Reorder outer control points to sort for view

THEN IF p[6].coord.ez > p[0].coord.ez THEN rotateBy ← 0 ELSE rotateBy ← 3

ELSE IF p[3].coord.ez > p[0].coord.ez THEN rotateBy ← 6 ELSE rotateBy ← 3;

FOR i: NAT IN [0..3) DO -- put vtx 6 farthest from viewer

tmpVtx: CtlPtInfo;

SELECT rotateBy FROM

3 => { tmpVtx ← p[i]; p[i] ← p[i+3]; p[i+3] ← p[i+6]; p[i+6] ← tmpVtx };

6 => { tmpVtx ← p[i]; p[i] ← p[i+6]; p[i+6] ← p[i+3]; p[i+3] ← tmpVtx };

ENDCASE; -- no changes needed if 6 already farthest

ENDLOOP;

FOR i: NAT IN [1..steps] DO -- walk across patch with barycentric coordinates

ls: REAL ← IF context.antiAliasing THEN 1.0 * (i-1) / steps ELSE 1.0 * (steps-i+1) / steps;

s: REAL ← IF context.antiAliasing THEN 1.0 * i / steps ELSE 1.0 * (steps-i) / steps;

Step from s=0 to s=1 if anti-aliasing else s=1 to s=0

FOR j: NAT IN [1..i] DO

lr: REAL ← 1.0 * (j-1) / steps; -- step from r=0 to r=s

r: REAL ← 1.0 * j / steps;

tp: REF Patch ← G3dShadeClipXfm.GetPatch[3]; -- will be released by action proc

tp.type ← $ConvexPolygon; tp.oneSided ← p.oneSided; tp.nVtces ← 3;

tp.clipState ← p.clipState; tp.dir ← p.dir; tp.props ← p.props;

tp[0] ← EvalTriangle[p, lr, ls, 1.0 - lr - ls];

tp[1] ← EvalTriangle[p, r, s, 1.0 - r - s];

tp[2] ← EvalTriangle[p, lr, s, 1.0 - lr - s];

G3dShadeClipXfm.ShadePoly[context, tp];

IF showLines THEN tp.type ← $PolyLine;

tp ← G3dSortandDisplay.OutputPolygon[context, tp]; -- display

IF j # i THEN {

ttp: REF Patch ← G3dShadeClipXfm.GetPatch[3]; -- will be released by action proc

ttp.type ← $ConvexPolygon; ttp.oneSided ← p.oneSided; ttp.nVtces ← 3;

ttp.clipState ← p.clipState; ttp.dir ← p.dir; ttp.props ← p.props;

ttp[0] ← EvalTriangle[p, lr, ls, 1.0 - lr - ls];

ttp[1] ← EvalTriangle[p, r, ls, 1.0 - r - ls];

ttp[2] ← EvalTriangle[p, r, s, 1.0 - r - s];

G3dShadeClipXfm.ShadePoly[context, ttp];

IF showLines THEN ttp.type ← $PolyLine;

ttp ← G3dSortandDisplay.OutputPolygon[context, ttp]; -- display

};

ENDLOOP;

};

BezierDisplayLines: PatchProc ~ {

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

EvalCoords: PROC[ v0, v1, v2, v3: NAT ] RETURNS[ REF Patch ] ~ {

clipState: ClipState;

IF patch.clipState = in -- get clipState of convex hull

THEN clipState ← in

ELSE {

outCode: OutCode ← LOOPHOLE[

Basics.BITOR[

Basics.BITOR[ LOOPHOLE[patch[v0].coord.clip], LOOPHOLE[patch[v1].coord.clip] ],

Basics.BITOR[ LOOPHOLE[patch[v2].coord.clip], LOOPHOLE[patch[v3].coord.clip] ]

OutCode ];

IF outCode = NoneOut

THEN clipState ← in

ELSE {

outCode ← LOOPHOLE[

Basics.BITAND[

LOOPHOLE[patch[v0].coord.clip], LOOPHOLE[patch[v1].coord.clip] ],

Basics.BITAND[

LOOPHOLE[patch[v2].coord.clip], LOOPHOLE[patch[v3].coord.clip] ]

OutCode ];

IF outCode # NoneOut

THEN clipState ← out

ELSE clipState ← clipped;

};

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

t: REAL ← Real.Float[i] / (8-1); t2: REAL ← t * t; t3: REAL ← t2 * t;

f0: REAL ← -1.0*t3 + 3.0*t2 - 3.0*t + 1;

f1: REAL ← 3.0*t3 - 6.0*t2 + 3.0*t;

f2: REAL ← -3.0*t3 + 3.0*t2;

f3: REAL ← 1.0*t3;

IF clipState # in OR context.antiAliasing

THEN {

path[i].coord.ex ← f0*patch[v0].coord.ex + f1*patch[v1].coord.ex
+ f2*patch[v2].coord.ex + f3*patch[v3].coord.ex;

path[i].coord.ey ← f0*patch[v0].coord.ey + f1*patch[v1].coord.ey
+ f2*patch[v2].coord.ey + f3*patch[v3].coord.ey;

path[i].coord.ez ← f0*patch[v0].coord.ez + f1*patch[v1].coord.ez
+ f2*patch[v2].coord.ez + f3*patch[v3].coord.ez;

IF clipState # in THEN path[i].coord.clip ← G3dShadeClipXfm.GetClipCodeForPt[

context,

[path[i].coord.ex, path[i].coord.ey, path[i].coord.ez]

];

IF context.antiAliasing THEN {

path[i].shade.r ← f0*patch[v0].shade.r + f1*patch[v1].shade.r
+ f2*patch[v2].shade.r + f3*patch[v3].shade.r;

path[i].shade.g ← f0*patch[v0].shade.g + f1*patch[v1].shade.g
+ f2*patch[v2].shade.g + f3*patch[v3].shade.g;

path[i].shade.b ← f0*patch[v0].shade.b + f1*patch[v1].shade.b
+ f2*patch[v2].shade.b + f3*patch[v3].shade.b;

};

}

ELSE {

path[i].coord.sx ← f0*patch[v0].coord.sx + f1*patch[v1].coord.sx
+ f2*patch[v2].coord.sx + f3*patch[v3].coord.sx;

path[i].coord.sy ← f0*patch[v0].coord.sy + f1*patch[v1].coord.sy
+ f2*patch[v2].coord.sy + f3*patch[v3].coord.sy;

path[i].coord.sz ← f0*patch[v0].coord.sz + f1*patch[v1].coord.sz
+ f2*patch[v2].coord.sz + f3*patch[v3].coord.sz;

};

path[i].coord.x ← f0*patch[v0].coord.x + f1*patch[v1].coord.x -- needed for display lists
+ f2*patch[v2].coord.x + f3*patch[v3].coord.x;

path[i].coord.y ← f0*patch[v0].coord.y + f1*patch[v1].coord.y
+ f2*patch[v2].coord.y + f3*patch[v3].coord.y;

path[i].coord.z ← f0*patch[v0].coord.z + f1*patch[v1].coord.z
+ f2*patch[v2].coord.z + f3*patch[v3].coord.z;

path[i].shade.er ← f0*patch[v0].shade.er + f1*patch[v1].shade.er
+ f2*patch[v2].shade.er + f3*patch[v3].shade.er;

path[i].shade.eg ← f0*patch[v0].shade.eg + f1*patch[v1].shade.eg
+ f2*patch[v2].shade.eg + f3*patch[v3].shade.eg;

path[i].shade.eb ← f0*patch[v0].shade.eb + f1*patch[v1].shade.eb
+ f2*patch[v2].shade.eb + f3*patch[v3].shade.eb;

ENDLOOP;

path.type ← $PolyLine;

path.nVtces ← 8;

path.clipState ← clipState;

path.renderData ← patch.renderData;

path.props ← patch.props;

RETURN[path];

};

path: REF Patch ← G3dShadeClipXfm.GetPatch[8];

IF patch.nVtces = 16

THEN {

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 0, 1, 2, 3 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[12,13,14,15 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 0, 4, 8,12 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 3, 7,11,15 ]];

}

ELSE IF patch.nVtces = 10 THEN { -- triangular patch

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 0, 1, 2, 3 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 3, 4, 5, 6 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 6, 7, 8, 0 ]];

};

G3dShadeClipXfm.ReleasePatch[path];

RETURN[patch]; -- patch should be unmodified

};

BezierDisplayCtrlPts: PatchProc ~ {

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

EvalCoords: PROC[ v0, v1, v2, v3: NAT ] RETURNS [REF Patch] ~ {

clipState: ClipState;

IF patch.clipState = in -- get clipState of convex hull

THEN clipState ← in

ELSE {

outCode: OutCode ← LOOPHOLE[

Basics.BITOR[

Basics.BITOR[ LOOPHOLE[patch[v0].coord.clip], LOOPHOLE[patch[v1].coord.clip] ],

Basics.BITOR[ LOOPHOLE[patch[v2].coord.clip], LOOPHOLE[patch[v3].coord.clip] ]

OutCode ];

IF outCode = NoneOut

THEN clipState ← in

ELSE {

outCode ← LOOPHOLE[

Basics.BITAND[

LOOPHOLE[patch[v0].coord.clip], LOOPHOLE[patch[v1].coord.clip] ],

Basics.BITAND[

LOOPHOLE[patch[v2].coord.clip], LOOPHOLE[patch[v3].coord.clip] ]

OutCode ];

IF outCode # NoneOut

THEN clipState ← out

ELSE clipState ← clipped;

};

path[0] ← patch[v0];

path[1] ← patch[v1];

path[2] ← patch[v2];

path[3] ← patch[v3];

path.type ← $PolyLine;

path.nVtces ← 4;

path.clipState ← clipState;

path.renderData ← patch.renderData;

path.props ← patch.props;

RETURN[path];

};

path: REF Patch ← G3dShadeClipXfm.GetPatch[4];

IF patch.nVtces = 16

THEN {

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 0, 1, 2, 3 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 4, 5, 6, 7 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 8, 9,10,11 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ ,13,14,15 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 0, 4, 8,12 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 1, 5, 9,13 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 2, 6,10,14 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 3, 7,11,15 ]];

}

ELSE IF patch.nVtces = 10 THEN { -- triangular Bezier patch

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 0, 1, 2, 3 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 3, 4, 5, 6 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 6, 7, 8, 0 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 9, 8, 1, 9 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 9, 7, 4, 9 ]];

path ← G3dSortandDisplay.OutputPolygon[context, EvalCoords[ 9, 5, 7, 9 ]];

};

G3dShadeClipXfm.ReleasePatch[path];

RETURN[patch]; -- patch should be unmodified

};

PolygonFromBezierPatch: PROC[p: REF Patch] RETURNS [REF Patch] ~ {

Return patch corner vertices and calculate normal vectors

leftCrnr: ARRAY [0..16) OF NAT ← [12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 0, 0, 3];

rghtCrnr: ARRAY [0..16) OF NAT ← [3, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12];

GetNorm: PROC[v, lft, nxtLft, rgt, nxtRgt: NAT] RETURNS[CtlPtInfo] ~ {

Get normal at corner vertex,v, defined by cross-product of vectors formed by adjacent vertices. Vertices, nxtLft and nxtRgt are used in case of degenerate edges forming triangular patches

normal: Triple;

d1: Triple ← DiffPosns[ p[lft].coord, p[v].coord, $Eye ]; -- results zero if < 6 sig. digits

d2: Triple ← DiffPosns[ p[rgt].coord, p[v].coord, $Eye ];

IF G3dVector.Null[ d1 ] THEN d1 ← DiffPosns[ p[nxtLft].coord, p[v].coord, $Eye ];

IF G3dVector.Null[ d2 ] THEN d2 ← DiffPosns[ p[nxtRgt].coord, p[v].coord, $Eye ];

normal ← G3dVector.Normalize[ G3dVector.Cross[d2, d1 ] ];

Check that normal is not insignificantly small, if too small use outer knots only

IF NOT G3dVector.Null[ DiffTriple[ d2, G3dVector.Add[d2, normal] ] ]

THEN [p[v].shade.exn, p[v].shade.eyn, p[v].shade.ezn] ← normal -- significant length

ELSE IF p.nVtces = 16

THEN { -- use polygon corners, too many degenerate knots

d1 ← DiffPosns[ p[leftCrnr[v]].coord, p[v].coord, $Eye ];

d2 ← DiffPosns[ p[rghtCrnr[v]].coord, p[v].coord, $Eye ];

IF G3dVector.Null[ d1 ]

THEN d1 ← DiffPosns[ p[leftCrnr[leftCrnr[v]]].coord, p[v].coord, $Eye ];

IF G3dVector.Null[ d2 ]

THEN d2 ← DiffPosns[ p[rghtCrnr[rghtCrnr[v]]].coord, p[v].coord, $Eye ];

normal ← G3dVector.Normalize[ G3dVector.Cross[d2, d1 ] ];

IF NOT G3dVector.Null[ DiffTriple[ d2, G3dVector.Add[d2, normal] ] ]

THEN [p[v].shade.exn, p[v].shade.eyn, p[v].shade.ezn] ← normal

ELSE [p[v].shade.exn, p[v].shade.eyn, p[v].shade.ezn] ← G3dBasic.origin;

}

ELSE [p[v].shade.exn, p[v].shade.eyn, p[v].shade.ezn] ← G3dBasic.origin;

RETURN [p[v]];

};

Get special output type for weird things like displacement mapping

outputType: ATOM ← NARROW[ Atom.GetPropFromList[ p.props, $InterimPatchType ] ];

IF outputType = NIL THEN outputType ← $ConvexPolygon;

p.type ← outputType; -- type of output patch

IF p.nVtces = 16

THEN {

Polygons taken clockwise: Patches taken rowwise, right to left:

[Artwork node; type 'Artwork on' to command tool]

p[0] ← GetNorm[v: 0, lft: 1, nxtLft: 7, rgt: 4, nxtRgt: 13]; -- use next control pt and

p[3] ← GetNorm[v: 3, lft: 7, nxtLft: 14, rgt: 2, nxtRgt: 4]; -- pt around next corner

p[15] ← GetNorm[v: 15, lft: 14, nxtLft: 8, rgt: 11, nxtRgt: 2]; -- to catch degeneracies

p[12] ← GetNorm[v: 12, lft: 8, nxtLft: 1, rgt: 13, nxtRgt: 11];

p.nVtces ← 4; -- copy corners (p[0], p[3] stay put)

p[1] ← CopyVtx[ p[12] ]^; p[2] ← CopyVtx[ p[15] ]^;

}

ELSE IF p.nVtces = 10 THEN { -- triangular patches taken clockwise, last pt in middle

p[0] ← GetNorm[v: 0, lft: 1, nxtLft: 4, rgt: 8, nxtRgt: 5]; -- use next control pt and

p[3] ← GetNorm[v: 3, lft: 4, nxtLft: 7, rgt: 2, nxtRgt: 8]; -- pt around next corner

p[6] ← GetNorm[v: 6, lft: 5, nxtLft: 2, rgt: 7, nxtRgt: 1]; -- to catch degeneracies

p.nVtces ← 3; -- copy corners (p[0] stays put)

p[1] ← CopyVtx[ p[3] ]^; p[2] ← CopyVtx[ p[6] ]^;

};

FOR i: NAT IN [0..p.nVtces) DO -- check for null normals (aligned vertices at corner)

IF G3dVector.Null[ [p[i].shade.exn, p[i].shade.eyn, p[i].shade.ezn] ] THEN {

j: NAT ← (i+1) MOD p.nVtces; -- found a null normal, try next vertex in order

p[i].shade.exn ← p[j].shade.exn;

p[i].shade.eyn ← p[j].shade.eyn;

p[i].shade.ezn ← p[j].shade.ezn;

IF G3dVector.Null[ [p[i].shade.exn, p[i].shade.eyn, p[i].shade.ezn] ] THEN {

IF stopOnDegenerate

THEN SIGNAL G3dRender.Error[$MisMatch, "Very degenerate Patch"];

p.nVtces ← 2; -- 2 null nmls, polygon will be ignored by scan converter

RETURN[p];

};

ENDLOOP;

IF showLines -- extra vertex closes path for lines

THEN { p[p.nVtces] ← CopyVtx[ p[0] ]^; p.nVtces ← p.nVtces+1; };

RETURN[p];

};

BezierBackFacing: PROC[context: Context, p: REF Patch] RETURNS[BOOLEAN] ~ {

Check facing direction of each of the 9 polygons described by the 10 or 16 control points

facing: FacingDir;

back, front, unknown: BOOLEAN ← FALSE;

subdir: FacingDirArray;

IF p.dir = front THEN RETURN[FALSE];

IF p.dir = back THEN RETURN[TRUE];

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

FOR j: NAT IN [0..3) DO

patch: REF Patch ← G3dShadeClipXfm.GetPatch[3];

patch.type ← $ConvexPolygon;

IF p.nVtces = 16

THEN {

k: NAT ← 4*i + j; -- index of lower left corner

patch[0] ← p[k]; patch[1] ← p[k + 4]; patch[2] ← p[k + 1];

}

ELSE IF p.nVtces = 10 THEN { -- triangular patch

k: NAT ← 3*j;

SELECT i FROM

0 => { patch[0] ← p[k]; patch[1] ← p[k+1]; patch[2] ← p[(k+8) MOD 9]; };

1 => { patch[0] ← p[k+1]; patch[1] ← p[k+2]; patch[2] ← p[9]; };

2 => { patch[0] ← p[k+1]; patch[1] ← p[9]; patch[2] ← p[(k+8) MOD 9]; };

ENDCASE;

};

facing ← G3dShadeClipXfm.BackFacing[

context, patch, TRUE

! G3dRender.Error => IF code = $Condition

THEN { facing ← unknown; CONTINUE; }

];

IF facing = back THEN back ← TRUE

ELSE IF facing = front THEN front ← TRUE

ELSE IF facing = unknown THEN unknown ← TRUE;

G3dShadeClipXfm.ReleasePatch[patch];

subdir[i*3 + j] ← facing;

ENDLOOP;

IF (back AND front) OR unknown

THEN p.dir ← unknown

ELSE IF back

THEN p.dir ← back

ELSE IF front

THEN p.dir ← front

ELSE p.dir ← unknown;

IF p.dir = unknown THEN

p.props ← PutPropSafely[p.props, $FacingDirArray, NEW[FacingDirArray ← subdir] ];

IF p.dir = back THEN RETURN[TRUE] ELSE RETURN[FALSE];

};

BezierPatchDivide: PROC[context: Context, p: REF Patch, midPt: MidPtProc]
RETURNS[REF Patch, REF Patch, REF Patch, REF Patch] ~ {

Subdivides a REF Patch for display purposes

outPatch: ARRAY [0..4) OF REF Patch;

row: ARRAY [0..8) OF CtlPtInfoSequence;

col: ARRAY [0..4) OF CtlPtInfoSequence;

Expand patch by evaluating control point rows, to get 49 vertices

Polygons taken clockwise: Patches taken rowwise, right to left:

3 -> 0 3 -> 0 3 2 1 0

^ ^ 7 6 5 4

2 <- 1 15 <- 12 11 10 9 8

15 14 13 12

Have any edges been marked straight but not straightened?

IF p[ 0].data = $Straight THEN SetStraight[ p, 0, 4, 8,12 ];

IF p[12].data = $Straight THEN SetStraight[ p,12,13,14,15 ];

IF p[15].data = $Straight THEN SetStraight[ p,15,11, 7, 3 ];

IF p[ 3].data = $Straight THEN SetStraight[ p, 3, 2, 1, 0 ];

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

p0, p1, p2, p3: REF CtlPtInfo;

p0 ← CopyVtx[ p[i] ]; p1 ← CopyVtx[ p[i+4] ];

p2 ← CopyVtx[ p[i+8] ]; p3 ← CopyVtx[ p[i+12] ];

[p0, p1, p2, p3] => [col[0], col[1], col[2], col[3], col[4], col[5], col[6], col[7]]

p0.data copied to col[0][0] and co[0]l[4], p3.data copied to col[3][7] and col[3][3]

SELECT i FROM

0 => col[0] ← BezierCurveDivide[ p0, p1, p2, p3, midPt, front ]; -- p[0]-p[12], 0 leads

3 => col[3] ← BezierCurveDivide[ p0, p1, p2, p3, midPt, back ]; -- p[3]-p[15], 15 leads

ENDCASE => col[i] ← BezierCurveDivide[ p0, p1, p2, p3, midPt, unknown ];

G3dShadeClipXfm.ReleaseCtlPtInfo[p0]; G3dShadeClipXfm.ReleaseCtlPtInfo[p1];

G3dShadeClipXfm.ReleaseCtlPtInfo[p2]; G3dShadeClipXfm.ReleaseCtlPtInfo[p3];

ENDLOOP;

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

col[0], col[1], col[2], col[3] => row[0],row[1],row[2],row[3], row[4],row[5],row[6],row[7]

col[0].data copied to row[0][0] & row[0][4], col[3].props copied to row[7][7] & row[7][3]

SELECT i FROM

0 => -- p[0] - p[3], 3 leads

row[0] ← BezierCurveDivide[ col[0][0], col[1][0], col[2][0], col[3][0], midPt, back ];

7 => -- p[12] - p[15], 12 leads

row[7] ← BezierCurveDivide[ col[0][7], col[1][7], col[2][7], col[3][7], midPt, front ];

ENDCASE => row[i] ←

BezierCurveDivide[ col[0][i], col[1][i], col[2][i], col[3][i], midPt, unknown ];

ENDLOOP;

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

rowBase: NAT ← (i MOD 2) * 4;

colBase: NAT ← (i / 2) * 4;

outPatch[i] ← G3dShadeClipXfm.GetPatch[16]; -- 16 point patch, released by display action

outPatch[i].type ← p.type;

outPatch[i].oneSided ← p.oneSided;

outPatch[i].nVtces ← 16;

outPatch[i].clipState ← p.clipState;

outPatch[i].dir ← p.dir;

outPatch[i].renderData ← p.renderData;

outPatch[i].props ← p.props;

FOR j: NAT IN [0..4) DO

FOR k: NAT IN [0..4) DO

outPatch[i][j*4 + k] ← row[colBase+j][rowBase+k]^; -- count along rows

outPatch[i][j*4 + k] ← CopyVtx[ row[colBase+j][rowBase+k]^ ]^; -- count along rows

ENDLOOP;

IF outPatch[i].clipState # in THEN {

FOR j: NAT IN [0..16) DO

OPEN outPatch[i][j].coord;

clip ← G3dShadeClipXfm.GetClipCodeForPt[ context, [ex, ey, ez] ];

IF clip = NoneOut

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

ENDLOOP;

outPatch[i] ← BezierClipState[context, outPatch[i] ];

};

IF outPatch[i].dir = unknown THEN [] ← BezierBackFacing[context, outPatch[i]];

ENDLOOP;

FOR i: NAT IN [0..8) DO FOR j: NAT IN [0..row[i].length) DO -- return borrowed storage

G3dShadeClipXfm.ReleaseCtlPtInfo[ row[i][j] ];

ENDLOOP; ENDLOOP;

FOR i: NAT IN [0..4) DO FOR j: NAT IN [0..col[i].length) DO

G3dShadeClipXfm.ReleaseCtlPtInfo[ col[i][j] ];

ENDLOOP; ENDLOOP;

RETURN[ outPatch[0], outPatch[1], outPatch[2], outPatch[3] ]; -- return four sub-patches

};

BezierCurveDivide: PROC[v0, v1, v2, v3: REF CtlPtInfo, midPt: MidPtProc, dir: FacingDir]
RETURNS[pt: CtlPtInfoSequence] ~ {

DeCasteljau subdivision algorithm

tempPt: REF CtlPtInfo;

pt ← NEW[ CtlPtInfoSequenceRep[8] ]; pt.length ← 8;

pt[0] ← CopyVtx[ v0^ ]; pt[7] ← CopyVtx[ v3^ ]; -- preserve endpoints

pt[1] ← midPt[v1, v0]; pt[6] ← midPt[v2, v3]; -- tangent midpoints

tempPt ← midPt[v1, v2]; -- midway between inner knots

pt[2] ← midPt[pt[1], tempPt]; pt[5] ← midPt[pt[6], tempPt]; -- midway between midpoints

pt[3] ← midPt[pt[2], pt[5]]; -- midway between midways between midpoints

pt[4] ← CopyVtx[ pt[3]^ ];

IF dir = front -- inner ends inherit outer straightness data if on directed patch boundary

THEN pt[4].data ← pt[0].data

ELSE IF dir = back THEN pt[3].data ← pt[7].data;

G3dShadeClipXfm.ReleaseCtlPtInfo[ tempPt ];

};

BezierClipState: PatchProc ~ {

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

G3dShadeClipXfm.GetPatchClipState[ patch ];

IF patch.clipState = clipped THEN {

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

IF patch[i].coord.clip # NoneOut THEN {

OPEN patch[i].coord;

sx ← context.eyeToNdc.scaleX * ex / ez + context.eyeToNdc.addX;

sy ← context.eyeToNdc.scaleY * ey / ez + context.eyeToNdc.addY;

sz ← context.eyeToNdc.scaleZ / ez + context.eyeToNdc.addZ;

IF sx < -0.5 OR sx > 1.5 OR sy < -0.5 OR sy > 1.5 OR sz < 0.0

THEN patch.clipState ← unknown -- too far out for stability (arbitrary)

ELSE { -- convert to screen coordinates

sx ← context.ndcToPixels.scaleX * sx + context.ndcToPixels.addX;

sy ← context.ndcToPixels.scaleY * sy + context.ndcToPixels.addY;

sz ← context.ndcToPixels.scaleZ * sz + context.ndcToPixels.addZ;

IF context.antiAliasing THEN { sx ← sx - 0.5; sy ← sy - 0.5; };

};

ENDLOOP;

};

RETURN[patch];

};

Procedures for expansion of B-Spline patches to convex polygons

BSplineDisplay: PatchProc ~ {

RETURN[NIL];

};

BSplineDisplayLines: PatchProc ~ {

RETURN[NIL];

};

Procedure for expansion of Non-convex to semi-convex polygons

NonConvexDisplay: PatchProc ~ {

RETURN[NIL];

};

InitClasses[];

END.