G3dStandardPatchProcs.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Last Edited by: Crow, May 17, 1989 11:11:23 am PDT
DIRECTORY Atom, Basics, G3dBasic, G3dMatrix, G3dRender, G3dScanConvert, G3dClipXfmShade, G3dSortandDisplay, G3dVector, Real, RealFns;
G3dStandardPatchProcs: CEDAR MONITOR
IMPORTS Atom, Basics, G3dMatrix, G3dRender, G3dClipXfmShade, 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;
PutProp: PROC [propList: Atom.PropList, prop: REF ANY, val: REF ANY]
   RETURNS [Atom.PropList] ~ Atom.PutPropOnList;
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 ← G3dClipXfmShade.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 ← G3dClipXfmShade.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]] ← G3dClipXfmShade.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;
};
v.data ← v0.data;
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
txtr: BOOLEAN ← p.renderData.shadingClass.texture # NIL;
p[v1] ← MakeStraight[ p[v0], p[v3], p[v1], txtr ];
p[v2] ← MakeStraight[ p[v0], p[v3], p[v2], txtr ];
p[v0].data ← $Straight;
};
StraightWithin: PROC[ context: Context, p: REF Patch, v0, v1, v2, v3: NAT,
       lilTol, bigTol: REAL] RETURNS[BOOLEAN] ~ {
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[ GetProp[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 ← G3dClipXfmShade.XfmPtToDisplay[
context, G3dVector.NearestToLine[line, [v.ex, v.ey, v.ez]]
];
vs: Triple ← G3dClipXfmShade.XfmPtToDisplay[ context, [v.ex, v.ey, v.ez] ];
RETURN[ RealFns.SqRt[ Sqr[ptOnEdge.x - vs.x] + Sqr[ptOnEdge.y - vs.y] ] ];
};
dist1, dist2, 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 on shape boundary
p.dir # unknown,    -- interior patch
InteriorEdge[]    =>  -- interior edge
{ p[v0].data ← $Straight; RETURN[ TRUE ]; };
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;
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
Store REF to parent shape
render.patch[i].props ← PutProp[render.patch[i].props, $Shape, shape];
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 ← G3dClipXfmShade.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] ] ← G3dClipXfmShade.XfmPtToDisplay[ context, [ex, ey, ez], shape ];
ENDLOOP;
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 ← $Poly;
standardClass.validate ← G3dSortandDisplay.ValidatePolyhedron;
standardClass.displayPatch ← NonConvexDisplay;
G3dRender.RegisterShapeClass[standardClass, $Poly];
};
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[patch]; };
controlPoints => { [] ← BezierDisplayCtrlPts[context, patch]; RETURN[patch]; };
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
G3dClipXfmShade.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 G3dClipXfmShade.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 ← G3dClipXfmShade.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];
G3dClipXfmShade.ShadePoly[context, tp];
IF showLines THEN tp.type ← $PolyLine;
tp ← G3dSortandDisplay.OutputPolygon[context, tp]; -- display
IF j # i THEN {
ttp: REF Patch ← G3dClipXfmShade.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];
G3dClipXfmShade.ShadePoly[context, ttp];
IF showLines THEN ttp.type ← $PolyLine;
ttp ← G3dSortandDisplay.OutputPolygon[context, ttp]; -- display
};
ENDLOOP;
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[
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 ← G3dClipXfmShade.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 ← G3dClipXfmShade.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 ]];
};
G3dClipXfmShade.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[
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 ← G3dClipXfmShade.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 ]];
};
G3dClipXfmShade.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 ← G3dClipXfmShade.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 ← G3dClipXfmShade.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;
G3dClipXfmShade.ReleasePatch[patch];
subdir[i*3 + j] ← facing;
ENDLOOP;
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 AND stopIfStraight THEN SetStraight[ p, 0, 4, 8,12 ];
IF p[12].data = $Straight AND stopIfStraight THEN SetStraight[ p,12,13,14,15 ];
IF p[15].data = $Straight AND stopIfStraight THEN SetStraight[ p,15,11, 7, 3 ];
IF p[ 3].data = $Straight AND stopIfStraight 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 col[0][4], p3.data copied to col[3][7] and col[3][3]
SELECT i FROM
0 => col[0] ← BezierCurveDivide[p, p0, p1, p2, p3, midPt, front]; -- p[0]-p[12], 0 leads
3 => col[3] ← BezierCurveDivide[p, p0, p1, p2, p3, midPt, back]; -- p[3]-p[15], 15 leads
ENDCASE => col[i] ← BezierCurveDivide[ p, p0, p1, p2, p3, midPt, unknown ];
G3dClipXfmShade.ReleaseCtlPtInfo[p0]; G3dClipXfmShade.ReleaseCtlPtInfo[p1];
G3dClipXfmShade.ReleaseCtlPtInfo[p2]; G3dClipXfmShade.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[p, col[0][0], col[1][0], col[2][0], col[3][0], midPt, back];
7 =>                  -- p[12] - p[15], 12 leads
row[7] ← BezierCurveDivide[p, col[0][7], col[1][7], col[2][7], col[3][7], midPt, front];
ENDCASE => row[i] ←
BezierCurveDivide[ p, 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] ← G3dClipXfmShade.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
ENDLOOP;
ENDLOOP;
IF outPatch[i].clipState # in THEN {
FOR j: NAT IN [0..16) DO
OPEN outPatch[i][j].coord;
clip ← G3dClipXfmShade.GetClipCodeForPt[ context, [ex, ey, ez] ];
IF clip = NoneOut
THEN [ [sx, sy, sz] ] ← G3dClipXfmShade.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
G3dClipXfmShade.ReleaseCtlPtInfo[ row[i][j] ];
ENDLOOP; ENDLOOP;
FOR i: NAT IN [0..4) DO FOR j: NAT IN [0..col[i].length) DO
G3dClipXfmShade.ReleaseCtlPtInfo[ col[i][j] ];
ENDLOOP; ENDLOOP;
RETURN[ outPatch[0], outPatch[1], outPatch[2], outPatch[3] ]; -- return four sub-patches
};
BezierCurveDivide: PROC[ p: REF Patch, v0, v1, v2, v3: REF CtlPtInfo,
         midPt: MidPtProc, dir: FacingDir ]
    RETURNS[pt: CtlPtInfoSequence] ~ {
DeCasteljau subdivision algorithm
txtr: BOOLEAN ← p.renderData.shadingClass.texture # NIL;
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, txtr];  pt[6] ← midPt[v2, v3, txtr];  -- tangent midpoints
tempPt ← midPt[v1, v2, txtr];         -- midway between inner knots
pt[2] ← midPt[pt[1], tempPt, txtr]; pt[5] ← midPt[pt[6], tempPt, txtr]; -- mid betw midpts
pt[3] ← midPt[pt[2], pt[5], txtr];    -- midway between midways between midpoints
pt[4] ← CopyVtx[ pt[3]^ ];    -- copy middle ctl pt to make ends for both sub-curves
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;
G3dClipXfmShade.ReleaseCtlPtInfo[ tempPt ];
};
BezierClipState: PatchProc ~ {
PROC[ context: Context, patch: REF Patch, data: REF ANY ← NIL ] RETURNS[REF Patch]
G3dClipXfmShade.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[patch];
};
BSplineDisplayLines: PatchProc ~ {
RETURN[patch];
};
Procedure for expansion of Non-convex to semi-convex polygons
NonConvexDisplay: PatchProc ~ {
This should make sure that the screen image of a polygon is semiconvex to match the abilities of the scan conversion algorithms
RETURN[ G3dSortandDisplay.OutputPolygon[context, patch] ];
};
InitClasses[];
END.