Copyright © 1986 by Xerox Corporation. All rights reserved.
Last Edited by: Crow, October 10, 1986 5:19:57 pm PDT
DIRECTORY
Atom USING [ GetPropFromList ],
Basics USING [ BITOR, BITAND ],
Real USING [ FixC, Float ],
RealFns USING [ SqRt ],
Vector3d USING [ Normalize, Cross, Dot, Null ],
ScanConvert USING [ justNoticeable ],
ThreeDBasics USING [ ClipState, Context, NatSequence, NoneOut, OutCode,
ShadingSequence, ShadingValue, ShapeInstance, SixSides,
Triple, Vertex, VertexInfo, VertexInfoProc, VertexInfoSequence,
VertexSequence ],
ThreeDScenes USING [ GetClipCodeForPt, XfmPtToDisplay ],
ThreeDSurfaces USING [ GetPatch, GetPatchClipState, Patch, PtrPatchSequence, PtrPatch,
PatchSequence, PatchExpandProc, PatchDisplayProc,
ReleasePatch, ShadePoly ],
StandardPatches;
Internal Declarations
StandardPatchesError: PUBLIC SIGNAL [reason: ATOM] = CODE;
Context: TYPE ~ ThreeDBasics.Context;
SixSides: TYPE ~ ThreeDBasics.SixSides;
Triple: TYPE ~ ThreeDBasics.Triple;
NatSequence: TYPE ~ ThreeDBasics.NatSequence;
ShapeInstance: TYPE ~ ThreeDBasics.ShapeInstance;
Patch: TYPE ~ ThreeDSurfaces.Patch;
PatchSequence: TYPE ~ ThreeDSurfaces.PatchSequence;
PtrPatch: TYPE ~ ThreeDSurfaces.PtrPatch;
PtrPatchSequence: TYPE ~ ThreeDSurfaces.PtrPatchSequence;
Vertex: TYPE ~ ThreeDBasics.Vertex;
VertexInfo: TYPE ~ ThreeDBasics.VertexInfo;
VertexInfoSequence: TYPE ~ ThreeDBasics.VertexInfoSequence;
MidPtProc: TYPE ~ PROC[v0, v1: REF VertexInfo] RETURNS[REF VertexInfo];
vertexStore: REF VertexInfoSequence ← NEW[ VertexInfoSequence[96] ]; -- Vertex Cache
vertexStoreLength: NAT ← 32;
vertexStorePtr: NAT ← 0; -- place to return next free record
Utility Procedures
Sqr:
PROCEDURE [number:
REAL]
RETURNS [
REAL] ~
INLINE {
RETURN[number * number]; };
GetVertexInfo:
ENTRY PROC[]
RETURNS[
REF VertexInfo] ~ {
ENABLE UNWIND => NULL;
vtx: REF VertexInfo;
IF vertexStorePtr = 0
THEN vtx ← NEW[VertexInfo]
ELSE
{
vertexStorePtr ← vertexStorePtr - 1;
vtx ← vertexStore[vertexStorePtr];
vertexStore[vertexStorePtr] ← NIL;
};
RETURN[ vtx ];
};
ReleaseVertexInfo:
ENTRY PROC[vtx:
REF VertexInfo] ~ {
ENABLE UNWIND => NULL;
IF vertexStorePtr = vertexStoreLength
THEN {
vertexStore ← NEW[ VertexInfoSequence[vertexStoreLength + 32] ];
vertexStoreLength ← vertexStoreLength + 32;
vertexStorePtr ← 0;
};
vertexStore[vertexStorePtr] ← vtx;
vertexStorePtr ← vertexStorePtr + 1;
};
DiffPosns:
PROC[vtx1, vtx2: Vertex, space:
ATOM ←
NIL]
RETURNS[Triple] ~ {
SELECT space
FROM
$Eye => RETURN[[vtx1.ex - vtx2.ex, vtx1.ey - vtx2.ey, vtx1.ez - vtx2.ez]];
$Screen => RETURN[[vtx1.sx - vtx2.sx, vtx1.sy - vtx2.sy, vtx1.sz - vtx2.sz]];
ENDCASE => RETURN[[vtx1.x - vtx2.x, vtx1.y - vtx2.y, vtx1.z - vtx2.z]]; -- object space
};
VtxShapeMidPt: MidPtProc ~ {
v: REF VertexInfo ← GetVertexInfo[];
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;
v.shade.xn ← (v0.shade.xn + v1.shade.xn) / 2;
v.shade.yn ← (v0.shade.yn + v1.shade.yn) / 2;
v.shade.zn ← (v0.shade.zn + v1.shade.zn) / 2;
v.shade.r ← (v0.shade.r + v1.shade.r) / 2;
v.shade.g ← (v0.shade.g + v1.shade.g) / 2;
v.shade.b ← (v0.shade.b + v1.shade.b) / 2;
v.shade.t ← (v0.shade.t + v1.shade.t) / 2;
IF v0.aux #
NIL
AND v1.aux #
NIL
THEN {
-- get auxiliary info from supplied proc
ref: REF ANY ← Atom.GetPropFromList[v0.props, $ShadeVtx];
IF ref #
NIL
THEN {
-- call custom interpolator
lerpProc: REF ThreeDBasics.VertexInfoProc ← NARROW[ref];
data: LIST OF REF ANY ← LIST[ v0.aux, v1.aux, NEW[REAL ← .5], NEW[REAL ← .5] ];
[] ← lerpProc^[ NIL, v, data];
}
ELSE v.aux ← v0.aux;
};
RETURN[v];
};
VtxDisplayMidPt: MidPtProc ~ {
v: REF VertexInfo ← GetVertexInfo[];
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;
v.coord.ex ← (v0.coord.ex + v1.coord.ex) / 2;
v.coord.ey ← (v0.coord.ey + v1.coord.ey) / 2;
v.coord.ez ← (v0.coord.ez + v1.coord.ez) / 2;
v.coord.sx ← (v0.coord.sx + v1.coord.sx) / 2;
v.coord.sy ← (v0.coord.sy + v1.coord.sy) / 2;
v.coord.sz ← (v0.coord.sz + v1.coord.sz) / 2;
v.shade.exn ← (v0.shade.exn + v1.shade.exn) / 2;
v.shade.eyn ← (v0.shade.eyn + v1.shade.eyn) / 2;
v.shade.ezn ← (v0.shade.ezn + v1.shade.ezn) / 2;
v.shade.r ← (v0.shade.r + v1.shade.r) / 2;
v.shade.g ← (v0.shade.g + v1.shade.g) / 2;
v.shade.b ← (v0.shade.b + v1.shade.b) / 2;
v.shade.t ← (v0.shade.t + v1.shade.t) / 2;
v.shade.er ← (v0.shade.er + v1.shade.er) / 2;
v.shade.eg ← (v0.shade.eg + v1.shade.eg) / 2;
v.shade.eb ← (v0.shade.eb + v1.shade.eb) / 2;
v.shade.et ← (v0.shade.et + v1.shade.et) / 2;
IF v0.aux #
NIL
AND v1.aux #
NIL
THEN {
-- get auxiliary info from supplied proc
ref: REF ANY ← Atom.GetPropFromList[v0.props, $ShadeVtx];
IF ref #
NIL
THEN {
-- call custom interpolator
lerpProc: REF ThreeDBasics.VertexInfoProc ← NARROW[ref];
data: LIST OF REF ANY ← LIST[ v0.aux, v1.aux, NEW[REAL ← .5], NEW[REAL ← .5] ];
[] ← lerpProc^[ NIL, v, data];
}
ELSE v.aux ← v0.aux;
};
RETURN[v];
};
ApplyCubicBasis:
PROC[ v0, v1, v2, v3:
REF VertexInfo, f0, f1, f2, f3:
REAL]
RETURNS[vOut:
REF VertexInfo] ~ {
vOut ← GetVertexInfo[];
vOut.coord.x ← f0*v0.coord.x + f1*v1.coord.x + f2*v2.coord.x + f3*v3.coord.x;
vOut.coord.y ← f0*v0.coord.y + f1*v1.coord.y + f2*v2.coord.y + f3*v3.coord.y;
vOut.coord.z ← f0*v0.coord.z + f1*v1.coord.z + f2*v2.coord.z + f3*v3.coord.z;
vOut.shade.xn ← f0*v0.shade.xn + f1*v1.shade.xn + f2*v2.shade.xn + f3*v3.shade.xn;
vOut.shade.yn ← f0*v0.shade.yn + f1*v1.shade.yn + f2*v2.shade.yn + f3*v3.shade.yn;
vOut.shade.zn ← f0*v0.shade.zn + f1*v1.shade.zn + f2*v2.shade.zn + f3*v3.shade.zn;
vOut.shade.r ← f0*v0.shade.r + f1*v1.shade.r + f2*v2.shade.r + f3*v3.shade.r;
vOut.shade.g ← f0*v0.shade.g + f1*v1.shade.g + f2*v2.shade.g + f3*v3.shade.g;
vOut.shade.b ← f0*v0.shade.b + f1*v1.shade.b + f2*v2.shade.b + f3*v3.shade.b;
vOut.shade.t ← f0*v0.shade.t + f1*v1.shade.t + f2*v2.shade.t + f3*v3.shade.t;
IF v0.aux #
NIL
THEN {
-- get auxiliary info from supplied proc
ref: REF ANY ← Atom.GetPropFromList[v0.props, $ShadeVtx];
IF ref #
NIL
THEN {
-- call custom interpolator 4 times to sum basis fns
lerpProc: REF ThreeDBasics.VertexInfoProc ← NARROW[ref];
data: LIST OF REF ANY ← LIST[v0.aux, vOut.aux, NEW[REAL ← f0], NEW[REAL ← 0.0]];
[] ← lerpProc^[ NIL, vOut, data];
data ← LIST[ v1.aux, vOut.aux, NEW[REAL ← f1], NEW[REAL ← 1.0]];
[] ← lerpProc^[ NIL, vOut, data];
data ← LIST[ v2.aux, vOut.aux, NEW[REAL ← f2], NEW[REAL ← 1.0]];
[] ← lerpProc^[ NIL, vOut, data];
data ← LIST[ v3.aux, vOut.aux, NEW[REAL ← f3], NEW[REAL ← 1.0]];
[] ← lerpProc^[ NIL, vOut, data];
}
ELSE vOut.aux ← v0.aux;
};
};
LerpToVtx:
PROC[ v0, v1, vMid: VertexInfo]
RETURNS[VertexInfo] ~ {
Interpolate to point defined by projection of vMid on v1 - v0
a, b, alpha: REAL;
v: VertexInfo;
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 THEN RETURN[v0]; -- effectively invisible detail
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;
v.coord.x ← a * v0.coord.x + b * v1.coord.x ;
v.coord.y ← a * v0.coord.y + b * v1.coord.y ;
v.coord.z ← a * v0.coord.z + b * v1.coord.z ;
v.coord.ex ← a * v0.coord.ex + b * v1.coord.ex ;
v.coord.ey ← a * v0.coord.ey + b * v1.coord.ey ;
v.coord.ez ← a * v0.coord.ez + b * v1.coord.ez ;
v.coord.sx ← a * v0.coord.sx + b * v1.coord.sx ;
v.coord.sy ← a * v0.coord.sy + b * v1.coord.sy ;
v.coord.sz ← a * v0.coord.sz + b * v1.coord.sz ;
v.shade.exn ← a * v0.shade.exn + b * v1.shade.exn ;
v.shade.eyn ← a * v0.shade.eyn + b * v1.shade.eyn ;
v.shade.ezn ← a * v0.shade.ezn + b * v1.shade.ezn ;
v.shade.r ← a * v0.shade.r + b * v1.shade.r ;
v.shade.g ← a * v0.shade.g + b * v1.shade.g ;
v.shade.b ← a * v0.shade.b + b * v1.shade.b ;
v.shade.t ← a * v0.shade.t + b * v1.shade.t ;
v.shade.er ← a * v0.shade.er + b * v1.shade.er ;
v.shade.eg ← a * v0.shade.eg + b * v1.shade.eg ;
v.shade.eb ← a * v0.shade.eb + b * v1.shade.eb ;
v.shade.et ← a * v0.shade.et + b * v1.shade.et ;
IF v0.aux #
NIL
AND v1.aux #
NIL
THEN {
-- get auxiliary info from supplied proc
ref: REF ANY ← Atom.GetPropFromList[v0.props, $ShadeVtx];
IF ref #
NIL
THEN {
-- call custom interpolator
lerpProc: REF ThreeDBasics.VertexInfoProc ← NARROW[ref];
data: LIST OF REF ANY ← LIST[ v0.aux, v1.aux, NEW[REAL ← a], NEW[REAL ← b] ];
v ← lerpProc^[ NIL, NEW[VertexInfo ← v], data]^;
}
ELSE v.aux ← v0.aux;
};
RETURN[v];
};
StraightWithin:
PROC[ p:
REF Patch, v0, v1, v2, v3:
NAT, tol:
REAL]
RETURNS[
BOOLEAN] ~ {
dist, a, b, mag: REAL;
IF p[v3].coord.sx < p[v0].coord.sx
THEN {
-- enforce consistent evaluation
t: NAT ← v3; v3 ← v0; v0 ← t; t ← v2; v2 ← v1; v1 ← t;
};
a ← p[v3].coord.sy - p[v0].coord.sy;
b ← p[v3].coord.sx - p[v0].coord.sx;
mag ← RealFns.SqRt[a*a + b*b];
IF mag > tol / 1000.0
THEN {
a ← a/mag; b ← b/mag;
dist ← a * (p[v1].coord.sx - p[v0].coord.sx) + b * (p[v0].coord.sy - p[v1].coord.sy);
IF ABS[dist] > tol THEN RETURN[FALSE];
dist ← a * (p[v2].coord.sx - p[v0].coord.sx) + b * (p[v0].coord.sy - p[v2].coord.sy);
IF ABS[dist] > tol THEN RETURN[FALSE];
};
Straight! Force inner control points to linear
p[v1] ← LerpToVtx[ p[v0], p[v3], p[v1] ];
p[v2] ← LerpToVtx[ p[v0], p[v3], p[v2] ];
RETURN[TRUE];
};
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;
ENDLOOP;
IF context.alphaBuffer
THEN RETURN[ pOut[0], pOut[1], pOut[2], pOut[3] ]
ELSE RETURN[ pOut[3], pOut[2], pOut[1], pOut[0] ];
};
Procedures for expansion of Bezier patches to convex polygons
BezierExpand:
PUBLIC ThreeDSurfaces.PatchExpandProc ~ {
PROC[ shape: REF ShapeInstance, patch: REF PtrPatch, limitType: ATOM, limit: REAL]
RETURNS [v: REF VertexInfoSequence, p: REF PtrPatchSequence]
nPerSide: NAT ← Real.FixC[limit];
IF limitType # NIL THEN SIGNAL StandardPatchesError[$Unimplemented];
[v, p] ← BezierParametricExpand[shape, patch, nPerSide];
RETURN[ v, p ];
};
BezierSubdivide:
PUBLIC ThreeDSurfaces.PatchExpandProc ~ {
PROC[ shape: REF ShapeInstance, patch: REF PtrPatch, limitType: ATOM, limit: REAL]
RETURNS [v: REF VertexInfoSequence, p: REF PtrPatchSequence]
IF limitType # NIL THEN SIGNAL StandardPatchesError[$Unimplemented];
[v, p] ← BezierSubdivideExpand[shape, patch];
RETURN[ v, p ];
};
minLimit: REAL ← .25; -- subdivision precision limit
recurseLimit: NAT ← 14; -- safety valve
BezierDisplay:
PUBLIC ThreeDSurfaces.PatchDisplayProc ~ {
PROC[ context: REF Context, patch: REF Patch, limitType: ATOM, limit: REAL
action: PROC[context: REF Context, patch: REF Patch] ];]
Display:
PROC[ p:
REF Patch, level:
NAT] ~ {
allStraight:
BOOLEAN ←
TRUE;
Quit if out of field of view or all normals point away from observer
IF (p.clipState = out)
OR BezierBackFacing[p]
THEN
RETURN[];
Straightness test, if straight enough make perfectly straight
IF NOT StraightWithin[p, 0, 1, 2, 3, limit] THEN allStraight ← FALSE;
IF NOT StraightWithin[p, 0, 4, 8, 12, limit] THEN allStraight ← FALSE;
IF NOT StraightWithin[p, 3, 7, 11,15, limit] THEN allStraight ← FALSE;
IF NOT StraightWithin[p, 12,13,14,15, limit] THEN allStraight ← FALSE;
IF allStraight
OR level >= recurseLimit
THEN {
-- outer edges straight, display as polygon
p.nVtces ← 4; p[1] ← p[12]; p[2] ← p[15]; -- copy corners (p[0], p[3] stay put)
p.type ← outputType; -- type of output patch
ThreeDSurfaces.ShadePoly[context, p];
action[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.depthBuffer
THEN [p0, p1, p2, p3] ← PatchSort[ context, p0, p1, p2, p3]; -- sort to display order
Display[p0, level+1]; Display[p1, level+1];
Display[p2, level+1]; Display[p3, level+1]; -- display in order
};
};
Get special output type for weird things like displacement mapping
outputType: ATOM ← NARROW[ Atom.GetPropFromList[ patch.props, $InterimPatchType ] ];
IF outputType = NIL THEN outputType ← $ConvexPolygon;
IF limitType #
NIL
AND limitType # $StraightEdges
THEN SIGNAL StandardPatchesError[$Unimplemented];
limit ← MAX[limit, minLimit]; -- straight to precision limit is sufficient (it says here)
BezierPatchNormals[patch]; -- Get Normals at control points
Display[patch, 0]; -- Divide till all outside patch edges are straight or recursion exceeded
ThreeDSurfaces.ReleasePatch[patch]; -- end of life for patch
};
BezierDisplayLines:
PUBLIC ThreeDSurfaces.PatchDisplayProc ~ {
EvalCoords:
PROC[ context:
REF Context, patch:
REF Patch, v0, v1, v2, v3:
NAT,
numPts:
NAT ← 8 ]
RETURNS [outP:
REF Patch] ~ {
clipState: ThreeDBasics.ClipState;
IF patch.clipState = in
-- get clipState of convex hull
THEN clipState ← in
ELSE {
outCode: ThreeDBasics.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] ]
],
ThreeDBasics.OutCode ];
IF outCode = ThreeDBasics.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] ]
],
ThreeDBasics.OutCode ];
IF outCode # ThreeDBasics.NoneOut
THEN clipState ← out
ELSE clipState ← clipped;
};
};
outP ← ThreeDSurfaces.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.alphaBuffer
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 ← ThreeDScenes.GetClipCodeForPt[
context,
[outP[i].coord.ex, outP[i].coord.ey, outP[i].coord.ez]
];
IF context.alphaBuffer
THEN {
-- set up color for display
outP[i].shade.er ← f0*patch[v0].shade.r + f1*patch[v1].shade.r
+ f2*patch[v2].shade.r + f3*patch[v3].shade.r;
outP[i].shade.eg ← f0*patch[v0].shade.g + f1*patch[v1].shade.g
+ f2*patch[v2].shade.g + f3*patch[v3].shade.g;
outP[i].shade.eb ← 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;
};
ENDLOOP;
outP.type ← $Path;
outP.clipState ← clipState;
outP.nVtces ← numPts;
};
path: REF Patch;
path ← EvalCoords[ context, patch, 0, 1, 2, 3 ]; action[context, path ];
path ← EvalCoords[ context, patch, 12, 13, 14, 15 ]; action[context, path ];
path ← EvalCoords[ context, patch, 0, 4, 8, 12 ]; action[context, path ];
path ← EvalCoords[ context, patch, 3, 7, 11, 15 ]; action[context, path ];
ThreeDSurfaces.ReleasePatch[patch]; -- end of life for patch
};
BezierDisplayCtrlPts:
PUBLIC ThreeDSurfaces.PatchDisplayProc ~ {
EvalCoords:
PROC[ context:
REF Context, patch:
REF Patch, v0, v1, v2, v3:
NAT,
numPts:
NAT ← 4 ]
RETURNS [outP:
REF Patch] ~ {
clipState: ThreeDBasics.ClipState;
IF patch.clipState = in
-- get clipState of convex hull
THEN clipState ← in
ELSE {
outCode: ThreeDBasics.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] ]
],
ThreeDBasics.OutCode ];
IF outCode = ThreeDBasics.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] ]
],
ThreeDBasics.OutCode ];
IF outCode # ThreeDBasics.NoneOut
THEN clipState ← out
ELSE clipState ← clipped;
};
};
outP ← ThreeDSurfaces.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 ← $Path;
outP.clipState ← clipState;
outP.nVtces ← numPts;
};
path: REF Patch;
path ← EvalCoords[ context, patch, 0, 1, 2, 3 ]; action[context, path ];
path ← EvalCoords[ context, patch, 4, 5, 6, 7 ]; action[context, path ];
path ← EvalCoords[ context, patch, 8, 9, 10, 11 ]; action[context, path ];
path ← EvalCoords[ context, patch, 12, 13, 14, 15 ]; action[context, path ];
path ← EvalCoords[ context, patch, 0, 4, 8, 12 ]; action[context, path ];
path ← EvalCoords[ context, patch, 3, 7, 11, 15 ]; action[context, path ];
ThreeDSurfaces.ReleasePatch[patch]; -- end of life for patch
};
BezierBackFacing:
PROC[p:
REF Patch]
RETURNS [
BOOLEAN] ~ {
frontFacing: BOOLEAN ← FALSE;
FOR i:
NAT
IN [0..16)
DO
-- this is not an adequate test!!!!
cosAng:
REAL ← Vector3d.Dot[
[p[i].coord.ex, p[i].coord.ey, p[i].coord.ez],
[p[i].shade.exn, p[i].shade.eyn, p[i].shade.ezn]
];
IF cosAng <= 0.0 THEN frontFacing ← TRUE;
ENDLOOP;
IF NOT frontFacing 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..7) OF REF VertexInfoSequence;
col:
ARRAY [0..4)
OF
REF VertexInfoSequence;
Expand patch by evaluating control point rows, to get 49 vertices
FOR i:
NAT
IN [0..4)
DO
p0, p1, p2, p3: REF VertexInfo;
p0 ← GetVertexInfo[]; p0^ ← p[i]; p1 ← GetVertexInfo[]; p1^ ← p[i+4];
p2 ← GetVertexInfo[]; p2^ ← p[i+8]; p3 ← GetVertexInfo[]; p3^ ← p[i+12];
col[i] ← BezierCurveDivide[ p0, p1, p2, p3, midPt ];
ReleaseVertexInfo[p0]; ReleaseVertexInfo[p1]; ReleaseVertexInfo[p2]; ReleaseVertexInfo[p3];
ENDLOOP;
FOR i:
NAT
IN [0..7)
DO
row[i] ← BezierCurveDivide[ col[0][i], col[1][i], col[2][i], col[3][i], midPt ];
ENDLOOP;
FOR i:
NAT
IN [0..4)
DO
rowBase: NAT ← (i MOD 2) * 3;
colBase: NAT ← (i / 2) * 3;
outPatch[i] ← ThreeDSurfaces.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
ENDLOOP;
ENDLOOP;
IF outPatch[i].clipState # in
THEN {
FOR j:
NAT
IN [0..16)
DO
OPEN outPatch[i][j].coord;
clip ← ThreeDScenes.GetClipCodeForPt[ context, [ex, ey, ez] ];
[ [sx, sy, sz] ] ← ThreeDScenes.XfmPtToDisplay[ context, NIL, [ex, ey, ez] ];
ENDLOOP;
ThreeDSurfaces.GetPatchClipState[ outPatch[i] ];
};
ENDLOOP;
FOR i:
NAT
IN [0..7)
DO
FOR j:
NAT
IN [0..row[i].length)
DO
-- return borrowed storage
ReleaseVertexInfo[ row[i][j] ];
ENDLOOP; ENDLOOP;
FOR i:
NAT
IN [0..4)
DO
FOR j:
NAT
IN [0..col[i].length)
DO
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]
RETURNS[pt:
REF VertexInfoSequence] ~ {
tempPt: REF VertexInfo;
pt ← NEW[ VertexInfoSequence[7] ];
pt[0] ← GetVertexInfo[]; pt[0]^ ← v0^; pt[6] ← GetVertexInfo[]; pt[6]^ ← v3^;
pt[1] ← midPt[v0, v1]; pt[5] ← midPt[v2, v3];
tempPt ← midPt[v1, v2];
pt[2] ← midPt[pt[1], tempPt]; pt[4] ← midPt[tempPt, pt[5]];
pt[3] ← midPt[pt[2], pt[4]];
ReleaseVertexInfo[ tempPt ];
};
BezierPatchNormals:
PROC[ patch:
REF Patch] ~ {
Get eyespace normals at control points, given by cross product of vectors formed from adjacent control points (limited to patch bounds, of course)
d1, d2: Triple;
GetXProd:
PROC[v1b, v1e, v2b, v2e:
NAT]
RETURNS[Triple] ~ {
d1 ← DiffPosns[ patch[v1e].coord, patch[v1b].coord, $Eye ];
d2 ← DiffPosns[ patch[v2e].coord, patch[v2b].coord, $Eye ];
IF Vector3d.Null[d1]
OR Vector3d.Null[d2]
THEN SIGNAL StandardPatchesError[$DegeneratePatch];
RETURN [ Vector3d.Normalize[ Vector3d.Cross[ d2, d1 ] ] ]; -- in eye space, left-handed
};
FOR i:
INTEGER
IN [0..4)
DO
FOR j:
INTEGER
IN [0..4)
DO
k: NAT ← j + i*4;
v1Beg: NAT ← 4*i + MAX[j-1, 0]; v1End: NAT ← 4*i + MIN[j+1, 3];
v2Beg: NAT ← 4*MAX[i-1, 0] + j; v2End: NAT ← 4*MIN[i+1, 3] + j;
{
[[ patch[k].shade.exn, patch[k].shade.eyn, patch[k].shade.ezn ]] ← GetXProd[
v1Beg, v1End, v2Beg, v2End
! ANY => GO TO FixUp
];
EXITS FixUp => {
-- degenerate edges, use alternate edges
IF
NOT Vector3d.Null[d1]
THEN {
l: NAT ← IF j = 3 THEN 2 ELSE j+1; -- use parallel pair of control points
v2Beg ← 4*MAX[i-1, 0] + l; v2End ← 4*MIN[i+1, 3] + l;
}
ELSE
IF
NOT Vector3d.Null[d2]
THEN {
l: NAT ← IF i = 3 THEN 2 ELSE i+1; -- use parallel pair of control points
v1Beg ← 4*l + MAX[j-1, 0]; v1End ← 4*l + MIN[j+1, 3];
}
ELSE SIGNAL StandardPatchesError[$DegeneratePatch]; -- failure
[[ patch[k].shade.exn, patch[k].shade.eyn, patch[k].shade.ezn ]] ← GetXProd[
v1Beg, v1End, v2Beg, v2End
]; -- try again with alternate edges
};
};
ENDLOOP;
ENDLOOP;
};
BezierPtrPatchNormals:
PROC[ shape:
REF ShapeInstance, patch:
REF PtrPatch] ~ {
Get normals at control points, given by cross product of vectors formed from adjacent control points (limited to patch bounds, of course)
GetXProd:
PROC[vertex:
REF ThreeDBasics.VertexSequence, v1b, v1e, v2b, v2e:
NAT]
RETURNS[Triple] ~ {
RETURN [ Vector3d.Normalize[ Vector3d.Cross[
-- in object space so do right-handed
DiffPosns[ vertex[v1e]^, vertex[v1b]^ ],
DiffPosns[ vertex[v2e]^, vertex[v2b]^ ]
] ] ];
};
vertex: REF ThreeDBasics.VertexSequence ← shape.vertex;
shade: REF ThreeDBasics.ShadingSequence ← shape.shade;
FOR i:
INTEGER
IN [0..4)
DO
FOR j:
INTEGER
IN [0..4)
DO
k: NAT ← patch.vtxPtr[j + i*4];
IF shade[k].xn = 0.0
AND shade[k].yn = 0.0
AND shade[k].zn = 0.0
THEN {
-- untouched
v1Beg: NAT ← 4*i + MAX[j-1, 0]; v1End: NAT ← 4*i + MIN[j+1, 3];
v2Beg: NAT ← 4*MAX[i-1, 0] + j; v2End: NAT ← 4*MIN[i+1, 3] + j;
IF patch.vtxPtr[v1Beg] = patch.vtxPtr[v1End]
THEN {
-- try to fix coalesced points
v1Beg ← 4*MAX[i-1, 0] + MAX[j-1, 0];
v1End ← 4*MIN[i+1, 3] + MIN[j+1, 3];
IF patch.vtxPtr[v1Beg] = patch.vtxPtr[v1End]
THEN SIGNAL StandardPatchesError[$DegeneratePatch];
};
IF patch.vtxPtr[v2Beg] = patch.vtxPtr[v2End]
THEN {
-- try to fix coalesced points
v2Beg ← 4*MAX[i-1, 0] + MAX[j-1, 0];
v2End ← 4*MIN[i+1, 3] + MIN[j+1, 3];
IF patch.vtxPtr[v2Beg] = patch.vtxPtr[v2End]
THEN SIGNAL StandardPatchesError[$DegeneratePatch];
};
[[ shade[k].xn, shade[k].yn, shade[k].zn ]] ← GetXProd[ vertex,
patch.vtxPtr[v1Beg], patch.vtxPtr[v1End], patch.vtxPtr[v2Beg], patch.vtxPtr[v2End]
];
};
ENDLOOP;
ENDLOOP;
};
BezierParametricExpand:
PROC[shape:
REF ShapeInstance, patch:
REF PtrPatch, nPrSide:
NAT]
RETURNS [
REF VertexInfoSequence,
REF PtrPatchSequence] ~ {
vertex: REF ThreeDBasics.VertexSequence ← shape.vertex;
shade: REF ThreeDBasics.ShadingSequence ← shape.shade;
RowEval:
PROC[ v0, v1, v2, v3:
REF VertexInfo, numPts:
NAT ]
RETURNS [pt:
REF VertexInfoSequence] ~ {
pt ← NEW[ VertexInfoSequence[numPts] ];
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;
pt[i] ← ApplyCubicBasis[v0, v1, v2, v3, f0, f1, f2, f3];
ENDLOOP;
};
row: ARRAY [0..4) OF REF VertexInfoSequence;
colA, colB: REF VertexInfoSequence;
vtxCnt, ptchCnt: NAT ← 0;
nVtces: NAT ← (nPrSide+1) * (nPrSide+1);
outVtx: REF VertexInfoSequence ← NEW[ VertexInfoSequence[nVtces] ];
outPatch: REF PtrPatchSequence ← NEW[ PtrPatchSequence[nPrSide*nPrSide] ];
ctlPtRow:
ARRAY [0..4)
OF
REF VertexInfo;
Get special output type for weird things like displacement mapping
outputType: ATOM ← NARROW[ Atom.GetPropFromList[ patch.props, $InterimPatchType ] ];
IF outputType =
NIL
THEN outputType ← $ConvexPolygon;
Get normals at control points
BezierPtrPatchNormals[shape, patch];
Expand patch by evaluating control point rows, then spitting out polygons columnwise
FOR i:
NAT
IN [0..4)
DO
FOR j:
NAT
IN [0..4)
DO
IF ctlPtRow[j] = NIL THEN ctlPtRow[j] ← NEW[ VertexInfo ];
ctlPtRow[j].coord ← vertex[patch.vtxPtr[i*4 + j]]^;
ctlPtRow[j].shade ← shade[patch.vtxPtr[i*4 + j]]^;
ENDLOOP;
row[i] ← RowEval[ ctlPtRow[0], ctlPtRow[1], ctlPtRow[2], ctlPtRow[3], nPrSide+1 ];
ENDLOOP;
colA ← RowEval[ row[0][0], row[1][0], row[2][0], row[3][0], nPrSide+1 ];
FOR i: NAT IN [0..nPrSide] DO outVtx[i+vtxCnt] ← colA[i]; ENDLOOP; -- store vertices
vtxCnt ← vtxCnt + nPrSide+1;
FOR i:
NAT
IN [1..nPrSide]
DO
colB ← RowEval[ row[0][i], row[1][i], row[2][i], row[3][i], nPrSide+1 ];
FOR j: NAT IN [0..nPrSide] DO outVtx[j+vtxCnt] ← colB[j]; ENDLOOP; -- store vertices
vtxCnt ← vtxCnt + nPrSide+1;
FOR j:
NAT
IN [1..nPrSide]
DO
IF outPatch[ptchCnt] = NIL THEN outPatch[ptchCnt] ← NEW[PtrPatch];
outPatch[ptchCnt].vtxPtr ← NEW[NatSequence[4]];
outPatch[ptchCnt].vtxPtr[0] ← (nPrSide+1) * (i-1) + j-1;
outPatch[ptchCnt].vtxPtr[1] ← (nPrSide+1) * (i-1) + j;
outPatch[ptchCnt].vtxPtr[2] ← (nPrSide+1) * i + j;
outPatch[ptchCnt].vtxPtr[3] ← (nPrSide+1) * i + j-1;
outPatch[ptchCnt].type ← outputType;
outPatch[ptchCnt].oneSided ← patch.oneSided;
outPatch[ptchCnt].nVtces ← 4;
outPatch[ptchCnt].clipState ← patch.clipState;
outPatch[ptchCnt].props ← patch.props;
ptchCnt ← ptchCnt + 1;
ENDLOOP;
colA ← colB;
ENDLOOP;
RETURN[ outVtx, outPatch ];
};
BezierSubdivideExpand:
PROC [shape:
REF ThreeDBasics.ShapeInstance, patch:
REF PtrPatch]
RETURNS [
REF VertexInfoSequence,
REF PtrPatchSequence] ~{
vertex: REF ThreeDBasics.VertexSequence ←shape.vertex;
shade: REF ThreeDBasics.ShadingSequence ← shape.shade;
outVtx: REF VertexInfoSequence ← NEW [ VertexInfoSequence [7*7] ];
outPatch: REF PtrPatchSequence ← NEW[PtrPatchSequence [4]];
row: ARRAY [0..4) OF REF VertexInfoSequence;
ctlPtRow:
ARRAY [0..4)
OF
REF VertexInfo;
Expand patch by evaluating control point rows, then spitting out polygons columnwise
FOR i:
NAT
IN [0..4)
DO
FOR j:
NAT
IN [0..4)
DO
IF ctlPtRow[j] = NIL THEN ctlPtRow[j] ← NEW[ VertexInfo ];
ctlPtRow[j].coord ← vertex[patch.vtxPtr[i*4 + j]]^;
ctlPtRow[j].shade ← shade[patch.vtxPtr[i*4 + j]]^;
ENDLOOP;
row[i] ← BezierCurveDivide[
ctlPtRow[0], ctlPtRow[1], ctlPtRow[2], ctlPtRow[3],
VtxShapeMidPt
];
ENDLOOP;
FOR i:
NAT
IN [0..7)
DO
vtces:
REF VertexInfoSequence ← BezierCurveDivide[
row[0][i], row[1][i], row[2][i], row[3][i],
VtxShapeMidPt
];
FOR j:
NAT
IN [0..7)
DO
outVtx[i*7 + j] ← NEW[ VertexInfo ← vtces[j]^ ];
ENDLOOP;
ENDLOOP;
FOR i:
NAT
IN [0..4)
DO
base: NAT ← (i / 2) * 21 + (i MOD 2) * 3; -- {0, 3, 21, 24}, least corners of 7x7 array
outPatch[i].vtxPtr ← NEW [NatSequence[16]];
outPatch[i].type ← patch.type;
outPatch[i].oneSided ← patch.oneSided;
outPatch[i].nVtces ← 16;
outPatch[i].clipState ← patch.clipState;
outPatch[i].props ← patch.props;
FOR j:
NAT
IN [0..4)
DO
FOR k:
NAT
IN [0..4)
DO
outPatch[i].vtxPtr[(3-j)*4+k] ← base + 7*j + k; -- count along rows, jump by 7 to next row
ENDLOOP;
ENDLOOP;
ENDLOOP;
RETURN[outVtx, outPatch];
};