[Indigo]<3DGraphics>NewThreeDRender>StandardPatchProcs.mesa!2

StandardPatchProcs.mesa

Last Edited by: Crow, March 13, 1988 3:55:52 pm PST

DIRECTORY

Atom USING [ DottedPair, DottedPairNode, GetPropFromList, PropList,
PutPropOnList, RemPropFromList ],

Basics USING [ BITOR, BITAND, BITSHIFT ],

Real USING [ Float ],

RealFns USING [ SqRt, AlmostEqual ],

G3dVector USING [ Add, Cross, NearestToLine, Normalize, Null ],

G3dBasic USING [ origin, Ray ],

ScanConvert USING [ justNoticeable ],

ThreeDBasics USING [ AllOut, ClipState, Context, Error, FacingDir,
GetSurfaceType, NoneOut, OutCode, Pair, Patch, PatchProc,
PatchSequence, PtrPatch, PtrPatchSequence, RealSequence,
RegisterSurfaceType, RGB, ShadingSequence, ShadingClass,
ShadingValue, ShapeClass, ShapeInstance, ShapeProc, SixSides,
Triple, Vertex, VertexInfo, VertexInfoProc, VertexInfoSequence,
VertexSequence, Xfm3D ],

ShapeUtilities USING [ BackFacing, GetClipCodeForPt, GetPatch, GetPatchClipState,
GetVertexInfo, ReleasePatch, ReleaseVertexInfo, ShadePoly, XfmPtToDisplay, XfmToEyeSpace ],

SurfaceRender USING [ GetPtrPatchClipState, OutputPolygon, ValidatePolyhedron ];

StandardPatchProcs: CEDAR MONITOR

IMPORTS Atom, Basics, G3dVector, Real, RealFns, SurfaceRender, ThreeDBasics, ShapeUtilities

= BEGIN

Internal Declarations

Ray: TYPE ~ G3dBasic.Ray;

RGB: TYPE ~ ThreeDBasics.RGB;

RealSequence: TYPE ~ ThreeDBasics.RealSequence;

Context: TYPE ~ ThreeDBasics.Context;

SixSides: TYPE ~ ThreeDBasics.SixSides;

Pair: TYPE ~ ThreeDBasics.Pair;

Triple: TYPE ~ ThreeDBasics.Triple;

Xfm3D: TYPE ~ ThreeDBasics.Xfm3D;

ShapeInstance: TYPE ~ ThreeDBasics.ShapeInstance;

Patch: TYPE ~ ThreeDBasics.Patch;

PatchSequence: TYPE ~ ThreeDBasics.PatchSequence;

PatchProc: TYPE ~ ThreeDBasics.PatchProc;

PtrPatch: TYPE ~ ThreeDBasics.PtrPatch;

PtrPatchSequence: TYPE ~ ThreeDBasics.PtrPatchSequence;

Vertex: TYPE ~ ThreeDBasics.Vertex;

VertexInfo: TYPE ~ ThreeDBasics.VertexInfo;

VertexInfoSequence: TYPE ~ ThreeDBasics.VertexInfoSequence;

VertexInfoProc: TYPE ~ ThreeDBasics.VertexInfoProc;

ShapeClass: TYPE ~ ThreeDBasics.ShapeClass;

ShapeProc: TYPE ~ ThreeDBasics.ShapeProc;

ClipState: TYPE ~ ThreeDBasics.ClipState;

OutCode: TYPE ~ ThreeDBasics.OutCode;

AllOut: OutCode ~ ThreeDBasics.AllOut;

NoneOut: OutCode ~ ThreeDBasics.NoneOut;

FacingDir: TYPE ~ ThreeDBasics.FacingDir;

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

MidPtProc: TYPE ~ PROC[v0, v1: REF VertexInfo] RETURNS[REF VertexInfo];

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];

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: VertexInfo]
RETURNS[vtxOut: REF VertexInfo] ~ {

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

lerpProc: VertexInfoProc ← IF shape # NIL THEN shape.shadingClass.lerpVtxAux ELSE NIL;

vtxOut ← ShapeUtilities.GetVertexInfo[];

vtxOut^ ← vtx;

IF lerpProc # NIL THEN { -- copy vtx.aux, has to be done remotely since type not available

data: LORA ← LIST[ vtx.aux, vtx.aux, refPt5, refPt5 ];

vtxOut^ ← lerpProc[ NIL, vtxOut^, data]; -- shoehorn into lerp form since its available

}

};

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] < ScanConvert.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: Vertex, 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 VertexInfo] RETURNS[REF VertexInfo]

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

lerpProc: VertexInfoProc ← IF shape # NIL THEN shape.shadingClass.lerpVtxAux ELSE NIL;

v: REF VertexInfo ← ShapeUtilities.GetVertexInfo[];

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]] ← ShapeUtilities.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 shape.shadingClass.texture # NIL THEN {

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

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

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

};

IF lerpProc # NIL

THEN { -- get auxiliary info from supplied proc

data: LORA ← LIST[ v0.aux, v1.aux, refPt5, refPt5 ];

v^ ← lerpProc[ NIL, v^, data];

}

ELSE v.aux ← v0.aux;

v.props ← v0.props;

RETURN[v];

};

TooClose: PROC[ context: REF Context, v: Vertex, 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];

};

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 ] ];

};

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

Remove property from new property list, to avoid clobbering 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.RemPropFromList[ newProps, prop ] ];

};

MakeStraight: PROC[ v0, v1, vMid: VertexInfo ]
RETURNS[VertexInfo] ~ {

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

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

lerpProc: VertexInfoProc ← IF shape # NIL THEN shape.shadingClass.lerpVtxAux ELSE NIL;

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 < ScanConvert.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 shape.shadingClass.texture # NIL THEN { -- original coords (for solid texture)

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

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

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

};

IF lerpProc # NIL

THEN { -- get auxiliary info from supplied proc

data: LORA ← LIST[ v0.aux, v1.aux, NEW[REAL ← a], NEW[REAL ← b] ];

vMid ← lerpProc[ NIL, vMid, data];

};

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].props ← PutPropSafely[p[v0].props, $Straight, $Itis];

};

StraightWithin: PROC[ context: REF 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].props ← PutPropSafely[p[v0].props, $Straight, $DoIt];

};

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 = undetermined THEN RETURN[FALSE];

RETURN[TRUE];

};

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

ptOnEdge: Triple ← ShapeUtilities.XfmPtToDisplay[

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

];

vs: Triple ← ShapeUtilities.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;

shape: REF ShapeInstance;

IF Atom.GetPropFromList[p[v0].props, $Straight] # NIL 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 > ScanConvert.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];

shape ← NARROW[ Atom.GetPropFromList[p.props, $Shape] ];

IF shape.shadingClass.texture # NIL THEN { -- watch for perspective depth distortion

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 # undetermined => { StraightenUp[]; RETURN[ TRUE ]; }; -- interior patch

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

ENDCASE => RETURN[ FALSE ];

};

PatchSort: PROC[ context: REF 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: REF Context, shape: REF ShapeInstance, data: REF] RETURNS[REF ShapeInstance];

Update shading and transform matrices)

IF shape.vtcesInValid THEN {

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

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

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 -- evaluate clipping tags

THEN SurfaceRender.GetPtrPatchClipState[ shape, patch[i] ]

ELSE patch[i].clipState ← out;

ENDLOOP;

};

shape.vtcesInValid ← FALSE;

};

shape.shadingInValid ← FALSE;

RETURN[shape];

};

Initialization of Classes

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

standardClass: ShapeClass ← ThreeDBasics.GetSurfaceType[$ConvexPolygon];

standardClass.type ← $Bezier;

standardClass.validate ← ValidatePatchShape;

standardClass.displayPatch ← BezierDisplay;

ThreeDBasics.RegisterSurfaceType[standardClass, $Bezier];

standardClass.type ← $BSpline;

standardClass.validate ← ValidatePatchShape;

standardClass.displayPatch ← BSplineDisplay;

ThreeDBasics.RegisterSurfaceType[standardClass, $BSpline];

standardClass.type ← $NonConvexPolygon;

standardClass.validate ← SurfaceRender.ValidatePolyhedron;

standardClass.displayPatch ← NonConvexDisplay;

ThreeDBasics.RegisterSurfaceType[standardClass, $NonConvexPolygon];

};

Procedures for expansion of Bezier patches to convex polygons

BezierDisplay: PatchProc ~ {

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

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

SELECT shape.shadingClass.shadingType FROM

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

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

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[NIL]; -- end of the line, no patch returned

};

BezierPatchDisplay: PROC[ context: REF 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 = undetermined

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

ShapeUtilities.ShadePoly[context, p];

IF showLines THEN p.type ← $PolyLine;

p ← SurfaceRender.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 p # NIL THEN ShapeUtilities.ReleasePatch[p]; -- end of life for patch

};

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

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

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

lerpProc: VertexInfoProc ← IF shape # NIL THEN shape.shadingClass.lerpVtxAux ELSE NIL;

v: VertexInfo;

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 shape.shadingClass.texture # NIL THEN {

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;

};

IF lerpProc # NIL

THEN { -- get auxiliary info from supplied proc

data: LORA ← LIST[ v0.aux, v1.aux, NEW[REAL ← r], NEW[REAL ← s] ];

v ← lerpProc[ NIL, v, data];

data ← LIST[ v.aux, v2.aux, NEW[REAL ← r+s], NEW[REAL ← t] ];

v ← lerpProc[ NIL, v, data];

}

ELSE v.aux ← v0.aux;

v.props ← v0.props;

RETURN[v];

};

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

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

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

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

p3: VertexInfo;

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: VertexInfo;

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 ← ShapeUtilities.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];

ShapeUtilities.ShadePoly[context, tp];

IF showLines THEN tp.type ← $PolyLine;

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

IF j # i THEN {

ttp: REF Patch ← ShapeUtilities.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];

ShapeUtilities.ShadePoly[context, ttp];

IF showLines THEN ttp.type ← $PolyLine;

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

};

ENDLOOP;

IF p # NIL THEN ShapeUtilities.ReleasePatch[p]; -- end of life for patch

};

BezierDisplayLines: PatchProc ~ {

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

EvalCoords: PROC[ context: REF Context, patch: REF Patch, v0, v1, v2, v3: NAT,
numPts: NAT ← 8 ]
RETURNS [outP: 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;

};

outP ← ShapeUtilities.GetPatch[numPts]; -- will be released by action proc

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

t: REAL ← Real.Float[i] / (numPts-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 {

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

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

outP[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 outP[i].coord.clip ← ShapeUtilities.GetClipCodeForPt[

context,

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

];

IF context.antiAliasing THEN {

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

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

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

};

}

ELSE {

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

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

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

};

outP[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;

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

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

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

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

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

ENDLOOP;

outP.type ← $PolyLine;

outP.props ← patch.props;

outP.clipState ← clipState;

outP.nVtces ← numPts;

};

path: REF Patch;

IF patch.nVtces = 16

THEN {

path ← EvalCoords[ context, patch, 0, 1, 2, 3 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch,12,13,14,15 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 0, 4, 8,12 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 3, 7,11,15 ];

[] ← SurfaceRender.OutputPolygon[context, path];

}

ELSE IF patch.nVtces = 10 THEN {

path ← EvalCoords[ context, patch, 0, 1, 2, 3 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 3, 4, 5, 6 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 6, 7, 8, 0 ];

[] ← SurfaceRender.OutputPolygon[context, path];

};

IF data # $DontRelease THEN ShapeUtilities.ReleasePatch[patch]; -- end of life for patch

RETURN[NIL]; -- end of the line, no patch returned

};

BezierDisplayCtrlPts: PatchProc ~ {

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

EvalCoords: PROC[ context: REF Context, patch: REF Patch, v0, v1, v2, v3: NAT,
numPts: NAT ← 4 ]
RETURNS [outP: 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;

};

outP ← ShapeUtilities.GetPatch[4]; -- will be released by action proc

outP[0] ← patch[v0];

outP[1] ← patch[v1];

outP[2] ← patch[v2];

outP[3] ← patch[v3];

outP.type ← $PolyLine;

outP.props ← patch.props;

outP.clipState ← clipState;

outP.nVtces ← numPts;

};

path: REF Patch;

IF patch.nVtces = 16

THEN {

path ← EvalCoords[ context, patch, 0, 1, 2, 3 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 4, 5, 6, 7 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 8, 9,10,11 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch,12,13,14,15 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 0, 4, 8,12 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 1, 5, 9,13 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 2, 6,10,14 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 3, 7,11,15 ];

[] ← SurfaceRender.OutputPolygon[context, path];

}

ELSE IF patch.nVtces = 10 THEN {

path ← EvalCoords[ context, patch, 0, 1, 2, 3 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 3, 4, 5, 6 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 6, 7, 8, 0 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 9, 8, 1, 9 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 9, 7, 4, 9 ];

[] ← SurfaceRender.OutputPolygon[context, path];

path ← EvalCoords[ context, patch, 9, 5, 7, 9 ];

[] ← SurfaceRender.OutputPolygon[context, path];

};

IF data # $DontRelease THEN ShapeUtilities.ReleasePatch[patch]; -- end of life for patch

RETURN[NIL]; -- end of the line, no patch returned

};

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[VertexInfo] ~ {

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 ThreeDBasics.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: REF 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, undetermined: 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 ← ShapeUtilities.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 ← ShapeUtilities.BackFacing[

context, patch, TRUE

! ThreeDBasics.Error => IF reason.code = $Condition

THEN { facing ← undetermined; CONTINUE; }

];

IF facing = back THEN back ← TRUE

ELSE IF facing = front THEN front ← TRUE

ELSE IF facing = undetermined THEN undetermined ← TRUE;

ShapeUtilities.ReleasePatch[patch];

subdir[i*3 + j] ← facing;

ENDLOOP;

IF (back AND front) OR undetermined

THEN p.dir ← undetermined

ELSE IF back

THEN p.dir ← back

ELSE IF front

THEN p.dir ← front

ELSE p.dir ← undetermined;

IF p.dir = undetermined THEN

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

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

};

BezierPatchDivide: PROC[context: REF 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 REF VertexInfoSequence;

col: ARRAY [0..4) OF REF VertexInfoSequence;

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 Atom.GetPropFromList[p[ 0].props, $Straight] = $DoIt THEN SetStraight[ p, 0, 4, 8,12 ];

IF Atom.GetPropFromList[p[12].props, $Straight] = $DoIt THEN SetStraight[ p,12,13,14,15 ];

IF Atom.GetPropFromList[p[15].props, $Straight] = $DoIt THEN SetStraight[ p,15,11, 7, 3 ];

IF Atom.GetPropFromList[p[ 3].props, $Straight] = $DoIt THEN SetStraight[ p, 3, 2, 1, 0 ];

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

p0, p1, p2, p3: REF VertexInfo;

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.props copied to col[0][0] and co[0]l[4], p3.props 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, undetermined ];

ShapeUtilities.ReleaseVertexInfo[p0]; ShapeUtilities.ReleaseVertexInfo[p1];

ShapeUtilities.ReleaseVertexInfo[p2]; ShapeUtilities.ReleaseVertexInfo[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].props 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, undetermined ];

ENDLOOP;

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

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

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

outPatch[i] ← ShapeUtilities.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].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 ← ShapeUtilities.GetClipCodeForPt[ context, [ex, ey, ez] ];

IF clip = NoneOut

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

ENDLOOP;

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

};

IF outPatch[i].dir = undetermined 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

ShapeUtilities.ReleaseVertexInfo[ row[i][j] ];

ENDLOOP; ENDLOOP;

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

ShapeUtilities.ReleaseVertexInfo[ 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 VertexInfo, midPt: MidPtProc, dir: FacingDir]
RETURNS[pt: REF VertexInfoSequence] ~ {

DeCasteljau subdivision algorithm

tempPt: REF VertexInfo;

pt ← NEW[ VertexInfoSequence[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 props if on directed patch boundary

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

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

ShapeUtilities.ReleaseVertexInfo[ tempPt ];

};

BezierClipState: PatchProc ~ {

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

ShapeUtilities.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 ← undetermined -- 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.