G3dPatchImpl.mesa
Copyright Ó 1985, 1992 by Xerox Corporation. All rights reserved.
Bloomenthal, October 21, 1992 4:35 pm PDT
DIRECTORY G3dBasic, G3dMatrix, G3dPatch, G3dSpline, G3dVector;
G3dPatchImpl: CEDAR PROGRAM
IMPORTS G3dSpline, G3dVector
EXPORTS G3dPatch
~ BEGIN
Types
Triple:    TYPE ~ G3dBasic.Triple;
Matrix:    TYPE ~ G3dMatrix.Matrix;
Bezier:    TYPE ~ G3dSpline.Bezier;
Spline:    TYPE ~ G3dSpline.Spline;
ControlPoints:  TYPE ~ G3dPatch.ControlPoints;
ControlPointsRep: TYPE ~ G3dPatch.ControlPointsRep;
FourPatches:   TYPE ~ G3dPatch.FourPatches;
Patch:     TYPE ~ G3dPatch.Patch;
PatchRep:    TYPE ~ G3dPatch.PatchRep;
Creation
FromBezier: PUBLIC PROC [cp: ControlPoints, out: Patch ¬ NIL] RETURNS [p: Patch] ~ {
p ¬ IF out # NIL THEN out ELSE NEW[PatchRep];
p.controlPoints ¬ cp;
FOR i: NAT IN [0..4) DO
p.sCurves[i]¬G3dSpline.SplineFromBezier[[cp[i][0],cp[i][1],cp[i][2], cp[i][3]], p.sCurves[i]];
ENDLOOP;
FOR i: NAT IN [0..4) DO
p.tCurves[i]¬G3dSpline.SplineFromBezier[[cp[0][i],cp[1][i],cp[2][i], cp[3][i]], p.tCurves[i]];
ENDLOOP;
};
Evaluation
Position: PUBLIC PROC [patch: Patch, s, t: REAL] RETURNS [Triple] ~ {
Lerp: PROC [p, q: Triple] RETURNS [Triple] ~ INLINE {
RETURN[[p.x+s*(q.x-p.x), p.y+s*(q.y-p.y), p.z+s*(q.z-p.z)]];
};
s0: Triple ¬ G3dSpline.Position[patch.sCurves[0], t];
s1: Triple ¬ G3dSpline.Position[patch.sCurves[1], t];
s2: Triple ¬ G3dSpline.Position[patch.sCurves[2], t];
s3: Triple ¬ G3dSpline.Position[patch.sCurves[3], t];
s12: Triple ¬ Lerp[s1, s2];
RETURN[Lerp[Lerp[Lerp[s0, s1], s12], Lerp[s12, Lerp[s2, s3]]]];
};
Normal: PUBLIC PROC [patch: Patch, s, t: REAL, unitize: BOOL ¬ TRUE] RETURNS [Triple] ~ {
vs: Triple ¬ G3dSpline.Velocity[SCurve[patch, s], t];
vt: Triple ¬ G3dSpline.Velocity[SCurve[patch, t], s];
n: Triple ¬ G3dVector.Cross[vs, vt];
RETURN[IF unitize THEN G3dVector.Unit[n] ELSE n];
};
SplineFrom4: PROC [curves: ARRAY [0..4) OF Spline, t: REAL, out: Spline ¬ NIL]
RETURNS [Spline] ~ {
p0: Triple ¬ G3dSpline.Position[curves[0], t];
p1: Triple ¬ G3dSpline.Position[curves[1], t];
p2: Triple ¬ G3dSpline.Position[curves[2], t];
p3: Triple ¬ G3dSpline.Position[curves[3], t];
RETURN[G3dSpline.SplineFromBezier[[p0, p1, p2, p3], out]];
};
SCurve: PUBLIC PROC [patch: Patch, s: REAL, out: Spline ¬ NIL] RETURNS [Spline] ~ {
RETURN[SplineFrom4[patch.tCurves, s, out]];
};
TCurve: PUBLIC PROC [patch: Patch, t: REAL, out: Spline ¬ NIL] RETURNS [Spline] ~ {
RETURN[SplineFrom4[patch.sCurves, t, out]];
};
Subdivision
Subdivide: PUBLIC PROC [patch: Patch, s, t: REAL ¬ 0.5] RETURNS [fp: FourPatches] ~ {
BezierDivide: PROC [b: Bezier, t: REAL] RETURNS [b1, b2: Bezier] ~ {
Lerp: PROC [p, q: Triple] RETURNS [Triple] ~ INLINE {
tt: REAL ¬ 1.0-t;
RETURN[[tt*p.x+t*q.x, tt*p.y+t*q.y, tt*p.z+t*q.z]];
};
b01: Triple ¬ Lerp[b.b0, b.b1];
b12: Triple ¬ Lerp[b.b1, b.b2];
b23: Triple ¬ Lerp[b.b2, b.b3];
b0112: Triple ¬ Lerp[b01, b12];
b1223: Triple ¬ Lerp[b12, b23];
b01121223: Triple ¬ Lerp[b0112, b1223];
RETURN[[b.b0, b01, b0112, b01121223], [b01121223, b1223, b23, b.b3]];
};
PatchFromBezier: PROC [b0, b1, b2, b3: Bezier] RETURNS [p: Patch] ~ {
RETURN[FromBezier[NEW[ControlPointsRep ¬ [
[b0.b0, b0.b1, b0.b2, b0.b3],
[b1.b0, b1.b1, b1.b2, b1.b3],
[b2.b0, b2.b1, b2.b2, b2.b3],
[b3.b0, b3.b1, b3.b2, b3.b3]]]]];
};
cp: ControlPoints ¬ patch.controlPoints;
s0, s1, s2, s3, s4, s5, s6, s7, t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11, t12, t13: Bezier;
[s0, s1] ¬ BezierDivide[[cp[0][0], cp[0][1], cp[0][2], cp[0][3]], s];
[s2, s3] ¬ BezierDivide[[cp[1][0], cp[1][1], cp[1][2], cp[1][3]], s];
[s4, s5] ¬ BezierDivide[[cp[2][0], cp[2][1], cp[2][2], cp[2][3]], s];
[s6, s7] ¬ BezierDivide[[cp[3][0], cp[3][1], cp[3][2], cp[3][3]], s];
[t0, t1] ¬ BezierDivide[[s0.b0, s2.b0, s4.b0, s6.b0], t];
[t2, t3] ¬ BezierDivide[[s0.b1, s2.b1, s4.b1, s6.b1], t];
[t4, t5] ¬ BezierDivide[[s0.b2, s2.b2, s4.b2, s6.b2], t];
[t6, t7] ¬ BezierDivide[[s0.b3, s2.b3, s4.b3, s6.b3], t];
[t8, t9] ¬ BezierDivide[[s1.b1, s3.b1, s5.b1, s7.b1], t];
[t10, t11] ¬ BezierDivide[[s1.b2, s3.b2, s5.b2, s7.b2], t];
[t11, t12] ¬ BezierDivide[[s1.b3, s3.b3, s5.b3, s7.b3], t];
fp[0] ¬ PatchFromBezier[t0, t2, t4, t6];
fp[1] ¬ PatchFromBezier[t1, t3, t5, t7];
fp[2] ¬ PatchFromBezier[t6, t8, t10, t12];
fp[3] ¬ PatchFromBezier[t7, t9, t11, t13];
};
split: Matrix ← NEW[MatrixRep ← [
   [1.000, 0.000, 0.000, 0.000],
   [0.500, 0.500, 0.000, 0.000],
   [0.025, 0.500, 0.250, 0.000],
   [0.125, 0.375, 0.375, 0.125]]];
Subdivide: PUBLIC PROC [patch: Patch, s, t: REAL ← 0.5] RETURNS [fp: FourPatches] ~ {
SubdivideS: PROC [p0, p1, p2, p3: Triple] RETURNS [q0, q1, q2, q3: Triple] ~ {
p: Matrix ← G3dMatrix.ObtainMatrix[];
p^ ← [[p0.x, p0.y, p0.z, 1.], [p1.x, p1.y, p1.z, 1.], [p2.x, p2.y, p2.z, 1.], [p3.x, p3.y, p3.z, 1.]];
p ← G3dMatrix.Mul[split, p, p];
q0 ← [p[0][0], p[0][1], p[0][2], p[0][3]];
q0 ← [p[0][0], p[0][1], p[0][2], p[0][3]];
q0 ← [p[0][0], p[0][1], p[0][2], p[0][3]];
q0 ← [p[0][0], p[0][1], p[0][2], p[0][3]];
G3dMatrix.ReleaseMatrix[p];
};
END.
..
If ever we want forward differencing:
Patch: TYPE ~ REF RECORD [ARRAY [0..4) OF ARRAY [0..4) OF ARRAY [0..4) OF REAL;
Creation
Bezier: PUBLIC PROC [cp: ControlPoints, out: Patch ¬ NIL] RETURNS [p: Patch] ~ {
b: PatchRep;
p ¬ IF out # NIL THEN out ELSE NEW[PatchRep];
FOR k: NAT IN [0..4) DO
Postmultiply by Beziert:
IF k = 3
THEN FOR i: NAT IN [0..4) DO
b[i][0][k] ¬ -cp[i][0][k]+3.0*cp[i][1][k]-3.0*cp[i][2][k]+cp[i][3][k];
b[i][1][k] ¬ 3.0*cp[i][0][k]-6.0*cp[i][1][k]+3.0*cp[i][2][k];
b[i][2][k] ¬ 3.0*cp[i][0][k]+3.0*cp[i][1][k];
b[i][3][k] ¬ 1.0;
ENDLOOP
ELSE FOR i: NAT IN [0..4) DO
b[i][0][3] ¬ 0.0;
b[i][1][3] ¬ 0.0;
b[i][2][3] ¬ 6.0;
b[i][3][3] ¬ 1.0;
ENDLOOP;
Premultiply by Bezier:
FOR j: NAT IN [0..4) DO
p[0][j][k] ¬ -b[0][j][k]+3.0*b[1][j][k]-3.0*b[2][j][k]+b[3][j][k];
p[1][j][k] ¬ 3.0*b[0][j][k]-6.0*b[1][j][k]+3.0*b[2][j][k];
p[2][j][k] ¬ -3.0*b[0][j][k]+3.0*b[1][j][k];
p[3][j][k] ¬ b[0][j][k];
ENDLOOP;
ENDLOOP;
};
Drawing
Draw: PUBLIC PROC [context: Context, view: Matrix, patch: Patch, nCurves, nSegments: NAT] ~ {
tcoeff, ucoeff, temp, diff: PatchRep;
curve: Spline;
s1: REAL ¬ 1.0/REAL[nSegments];
s2: REAL ¬ s1*s1;
s22: REAL ¬ s2+s2;
s3: REAL ¬s2*s1;
s36: REAL ¬ 6.0*s3;
c1: REAL ¬ 1.0/REAL[nCurves];
c2: REAL ¬ c1*c1;
c22: REAL ¬ c2+c2;
c3: REAL ¬ c2*c1;
c36: REAL ¬ 6.0*c3;
sDirection: BOOL ¬ TRUE;
Postmultiply patch by view:
FOR j: NAT IN [0..4) DO
FOR i: NAT IN [0..4) DO
FOR k: NAT IN [0..4) DO
tcoeff[i][j][k] ¬
patch[i][j][0]*view[0][k]+
patch[i][j][1]*view[1][k]+
patch[i][j][2]*view[2][k]+
patch[i][j][3]*view[3][k];
ENDLOOP;
ENDLOOP;
ENDLOOP;
FOR k: NAT IN [0..4) DO
Postmultiply transformed patch by D[nCurves]T:
FOR i: NAT IN [0..4) DO
temp[i][0][k] ¬ tcoeff[i][3][k];
temp[i][1][k] ¬ tcoeff[i][0][k]*c3+tcoeff[i][1][k]*c2+tcoeff[i][2][k]*c1;
temp[i][3][k] ¬ tcoeff[i][0][k]*c36;
temp[i][2][k] ¬ temp[i][3][k]+tcoeff[i][1][k]*c22;
ENDLOOP;
Premultiply by D[nSegments]:
FOR j: NAT IN [0..4) DO
diff[0][j][k] ¬ temp[3][j][k];
diff[1][j][k] ¬ s3*temp[0][j][k]+s2*temp[1][j][k]+s1*temp[2][j][k];
diff[3][j][k] ¬ s36*temp[0][j][k];
diff[2][j][k] ¬ diff[3][j][k]+s22*temp[1][j][k];
ENDLOOP;
ENDLOOP;
};