StandardPatchesImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Last Edited by: Crow, April 12, 1986 6:39:07 pm PST
DIRECTORY
Basics     USING [BITOR, BITAND],
Real     USING [FixC, Float],
RealFns    USING [SqRt],
Vector3d    USING [Triple, Normalize, Cross, Dot, Null],
ScanConvert   USING [justNoticeable],
ThreeDScenes  USING [ClipState, Context, GetClipCodeForPt, NoneOut, OutCode,         ShadingSequence, ShadingValue, ShapeInstance, SixSides,
        Vertex, VertexInfo, VertexInfoSequence, VertexSequence,
        XfmPtToDisplay],
ThreeDSurfaces  USING [GetPatchClipState, Patch, PtrPatchSequence, PtrPatch,
        PatchSequence, PatchExpandProc, PatchDisplayProc, ShadePoly],
StandardPatches;
StandardPatchesImpl: CEDAR MONITOR
IMPORTS Basics, Real, RealFns, Vector3d, ThreeDScenes, ThreeDSurfaces
EXPORTS StandardPatches
= BEGIN
Internal Declarations
StandardPatchesError: PUBLIC SIGNAL [reason: ATOM] = CODE;
Context: TYPE ~ ThreeDScenes.Context;
SixSides: TYPE ~ ThreeDScenes.SixSides;
Triple: TYPE ~ Vector3d.Triple;
ShapeInstance: TYPE ~ ThreeDScenes.ShapeInstance;
Patch: TYPE ~ ThreeDSurfaces.Patch;
PatchSequence: TYPE ~ ThreeDSurfaces.PatchSequence;
PtrPatch: TYPE ~ ThreeDSurfaces.PtrPatch;
PtrPatchSequence: TYPE ~ ThreeDSurfaces.PtrPatchSequence;
Vertex: TYPE ~ ThreeDScenes.Vertex;
VertexInfo: TYPE ~ ThreeDScenes.VertexInfo;
VertexInfoSequence: TYPE ~ ThreeDScenes.VertexInfoSequence;
MidPtProc: TYPE ~ PROC[v0, v1: REF VertexInfo] RETURNS[REF VertexInfo];
patchStore: REF PatchSequence ← NEW[ PatchSequence[32] ];
patchStoreLength: NAT ← 32;
patchStorePtr: NAT ← 0;        -- place to return next free record
vertexStore: REF VertexInfoSequence ← NEW[ VertexInfoSequence[96] ];
vertexStoreLength: NAT ← 32;
vertexStorePtr: NAT ← 0;        -- place to return next free record
Utility Procedures
Sqr: PROCEDURE [number: REAL] RETURNS [REAL] ~ INLINE { RETURN[number * number]; };
GetPatch: ENTRY PROC[] RETURNS[REF Patch] ~ {
p: REF Patch;
IF patchStorePtr = 0
THEN p ← NEW[Patch[16]]
ELSE {
patchStorePtr ← patchStorePtr - 1;
p ← patchStore[patchStorePtr];
patchStore[patchStorePtr] ← NIL;
};
RETURN[ p ];
};
ReleasePatch: ENTRY PROC[p: REF Patch] ~ {
IF patchStorePtr = patchStoreLength THEN {
patchStore ← NEW[ PatchSequence[patchStoreLength + 32] ];
patchStoreLength ← patchStoreLength + 32;
patchStorePtr ← 0;
};
patchStore[patchStorePtr] ← p;
patchStorePtr ← patchStorePtr + 1;
};
GetVertexInfo: ENTRY PROC[] RETURNS[REF VertexInfo] ~ {
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] ~ {
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;
v.shade.txtrX ← (v0.shade.txtrX + v1.shade.txtrX) / 2;
v.shade.txtrY ← (v0.shade.txtrY + v1.shade.txtrY) / 2;
v.shade.txtrZ ← (v0.shade.txtrZ + v1.shade.txtrZ) / 2;
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.txtrX ← (v0.shade.txtrX + v1.shade.txtrX) / 2;
v.shade.txtrY ← (v0.shade.txtrY + v1.shade.txtrY) / 2;
v.shade.txtrZ ← (v0.shade.txtrZ + v1.shade.txtrZ) / 2;
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;
vOut.shade.txtrX ←
   f0*v0.shade.txtrX + f1*v1.shade.txtrX + f2*v2.shade.txtrX + f3*v3.shade.txtrX;
vOut.shade.txtrY ←
   f0*v0.shade.txtrY + f1*v1.shade.txtrY + f2*v2.shade.txtrY + f3*v3.shade.txtrY;
vOut.shade.txtrZ ←
   f0*v0.shade.txtrZ + f1*v1.shade.txtrZ + f2*v2.shade.txtrZ + f3*v3.shade.txtrZ;
};
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.txtrX ← a * v0.shade.txtrX + b * v1.shade.txtrX ;
v.shade.txtrY ← a * v0.shade.txtrY + b * v1.shade.txtrY ;
v.shade.txtrZ ← a * v0.shade.txtrZ + b * v1.shade.txtrZ ;
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 ← $ConvexPolygon;
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
ReleasePatch[p0]; ReleasePatch[p1];
ReleasePatch[p2]; ReleasePatch[p3];     -- return storage
};
};
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
};
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: ThreeDScenes.ClipState;
IF patch.clipState = in     -- get clipState of convex hull
THEN clipState ← in
ELSE {
outCode: ThreeDScenes.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] ]
],
ThreeDScenes.OutCode ];
IF outCode = ThreeDScenes.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] ]
],
ThreeDScenes.OutCode ];
IF outCode # ThreeDScenes.NoneOut
THEN clipState ← out
ELSE clipState ← clipped;
};
};
outP ← GetPatch[];
IF outP.length < numPts THEN outP ← NEW[ Patch[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;
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.ir ← Real.FixC[ 255.0 * (f0*patch[v0].shade.r + f1*patch[v1].shade.r
          + f2*patch[v2].shade.r + f3*patch[v3].shade.r) ];
outP[i].shade.ig ← Real.FixC[ 255.0 * (f0*patch[v0].shade.g + f1*patch[v1].shade.g
          + f2*patch[v2].shade.g + f3*patch[v3].shade.g) ];
outP[i].shade.ib ← Real.FixC[ 255.0 * (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 ]; ReleasePatch[path];
path ← EvalCoords[ context, patch, 12, 13, 14, 15 ];
action[context, path ]; ReleasePatch[path];
path ← EvalCoords[ context, patch, 0, 4, 8, 12 ];
action[context, path ]; ReleasePatch[path];
path ← EvalCoords[ context, patch, 3, 7, 11, 15 ];
action[context, path ]; ReleasePatch[path];
};
BezierBackFacing: PROC[p: REF Patch] RETURNS [BOOLEAN] ~ {
frontFacing: BOOLEAN ← FALSE; 
FOR i: NAT IN [0..16) DO
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] ← GetPatch[];        -- 16 point patch returned
outPatch[i].type ← p.type;
outPatch[i].oneSided ← p.oneSided;
outPatch[i].nVtces ← 16;
outPatch[i].clipState ← p.clipState;
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, [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 ThreeDScenes.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 ThreeDScenes.VertexSequence ← shape.vertex;
shade: REF ThreeDScenes.ShadingSequence ← shape.shade;
FOR i: INTEGER IN [0..4) DO
FOR j: INTEGER IN [0..4) DO
k: NAT ← patch[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[v1Beg] = patch[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[v1Beg] = patch[v1End]
THEN SIGNAL StandardPatchesError[$DegeneratePatch];
};
IF patch[v2Beg] = patch[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[v2Beg] = patch[v2End]
THEN SIGNAL StandardPatchesError[$DegeneratePatch];
};
[[ shade[k].xn, shade[k].yn, shade[k].zn ]] ← GetXProd[ vertex,
patch[v1Beg], patch[v1End], patch[v2Beg], patch[v2End]
];
};
ENDLOOP;
ENDLOOP;
};
BezierParametricExpand: PROC[shape: REF ShapeInstance, patch: REF PtrPatch, nPrSide: NAT]
        RETURNS [REF VertexInfoSequence, REF PtrPatchSequence] ~ {
vertex: REF ThreeDScenes.VertexSequence ← shape.vertex;
shade: REF ThreeDScenes.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 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[i*4 + j]]^;
ctlPtRow[j].shade ← shade[patch[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
outPatch[ptchCnt] ← NEW[ PtrPatch[4] ];
outPatch[ptchCnt][0] ← (nPrSide+1) * (i-1) + j-1;
outPatch[ptchCnt][1] ← (nPrSide+1) * (i-1) + j;
outPatch[ptchCnt][2] ← (nPrSide+1) * i + j;
outPatch[ptchCnt][3] ← (nPrSide+1) * i + j-1;
outPatch[ptchCnt].type ← $ConvexPolygon;
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 ThreeDScenes.ShapeInstance, patch: REF PtrPatch]
     RETURNS [REF VertexInfoSequence, REF PtrPatchSequence] ~{
vertex: REF ThreeDScenes.VertexSequence ←shape.vertex;
shade: REF ThreeDScenes.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[i*4 + j]]^;
ctlPtRow[j].shade ← shade[patch[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] ← NEW [PtrPatch[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][(3-j)*4+k] ← base + 7*j + k; -- count along rows, jump by 7 to next row
ENDLOOP;
ENDLOOP;
ENDLOOP;
RETURN[outVtx, outPatch];
};
Procedures for expansion of B-Spline patches to convex polygons
BSplineExpand: PUBLIC ThreeDSurfaces.PatchExpandProc ~ {
RETURN[ NIL, NIL ];
};
BSplineSubdivide: PUBLIC ThreeDSurfaces.PatchExpandProc ~ {
RETURN[ NIL, NIL ];
};
BSplineDisplay: PUBLIC ThreeDSurfaces.PatchDisplayProc ~ {
};
BSplineDisplayLines: PUBLIC ThreeDSurfaces.PatchDisplayProc ~ {
};
Procedures for expansion of convex polygons
PolygonExpand: PUBLIC ThreeDSurfaces.PatchExpandProc ~ {
RETURN[ NIL, NIL ];
};
PolygonSubdivide: PUBLIC ThreeDSurfaces.PatchExpandProc ~ {
RETURN[ NIL, NIL ];
};
PolygonDisplay: PUBLIC ThreeDSurfaces.PatchDisplayProc ~ {
};
PolygonDisplayLines: PUBLIC ThreeDSurfaces.PatchDisplayProc ~ {
};
Procedure for expansion of Non-convex to semi-convex polygons
NonConvexDisplay: PUBLIC ThreeDSurfaces.PatchDisplayProc ~ {
};
END.