
DIRECTORY G3dBasic, G3dMatrix, G3dPatch, G3dSpline, G3dVector;

G3dPatchImpl: CEDAR PROGRAM
IMPORTS G3dSpline, G3dVector
EXPORTS G3dPatch

~ BEGIN
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;
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;
};
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]];
};
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];
};

END.
..
If ever we want forward differencing:

Patch: TYPE ~ REF RECORD [ARRAY [0..4) OF ARRAY [0..4) OF ARRAY [0..4) OF REAL;
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
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;
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;
};
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;
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
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;
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;
};

     
G3dPatchImpl.mesa
Copyright ╙ 1985, 1992 by Xerox Corporation.  All rights reserved.
Bloomenthal, October 21, 1992 4:35 pm PDT
Types
Creation
Evaluation


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

Creation
Postmultiply by Beziert:
Premultiply by Bezier:
Drawing
Postmultiply patch by view:
Postmultiply transformed patch by D[nCurves]T:
Premultiply by D[nSegments]:

Э╩~  ХNewlineDelimiter
Ц"cedarcode" styleЩ ЩJЪЬ	╧eЬ6ЩBJЩ)JШ ЧЪ╧k	Ь5Ш>JШ ЧЪ╨lnЬЮШJЪЮЬШJЪЮЬ	ШJШ ЧJЪЬЮШheadЪ╧lЩJЪЬ
ЮЬШ"JЪЬ
ЮЬШ#JЪЬ
ЮЬШ#ЪЬ
ЮЬШ#JШ ЧJЪЬЮЬШ.JЪЬЮЬШ3JЪЬЮЬШ+JЪЬЮ	ЬШ!JЪЬ	ЮЬШ&ЧЪаЩЪ
╧n
ЬЮЬЮЬ"ЮЬЮЬШTJЪЬЮЬЮЬЮЬЮЬЮЬШ-JШЪЮЬЮЬЮЬЮШJЪЬO╧sЬШ^JЪЮЬШЧЪЮЬЮЬЮЬЮШJЪЬOвЬШ^JЪЮЬШЧJШЧЧЪа
Щ
Ъ
бЬЮЬЮЬЮЬЮЬШEЪбЬЮЬЮЬЮЬШ5JЪЮЬ6Ш<JШЧJШ5JШ5JШ5JШ5JШJЪЮЬ9Ш?JШJЩ ЧЪбЬЮЬЮЬЮЬЮЬЮЬЮЬШYJШ5JШ5JШ$JЪЮЬЮЬ	ЮЬЮЬШ1JШJШ ЧЪбЬЮЬ
ЮЬЮЬЮЬЮЬШNJЪЮЬШJШ.JШ.JШ.JШ.JЪЮЬ4Ш:JШJЩ ЧЪбЬЮЬЮЬЮЬЮЬЮЬШSJЪЮЬ%Ш+JШJЩ ЧЪбЬЮЬЮЬЮЬЮЬЮЬШSJЪЮЬ%Ш+JШЧЧЪаЩЪ
б	ЬЮЬЮЬЮЬЮЬШUЪбЬЮЬЮЬЮЬШDЪбЬЮЬЮЬЮЬШ5JЪЬЮЬ	ШJЪЮЬ-Ш3JШЧJШJШJШJШJШJШ'JЪЮЬ?ШEJШЧЪбЬЮЬЮЬШEЪЮЬЮЬШ*JЪЬШJЪЬШJЪЬШJЪЬ!Ш!ЧJШЧJШ(JЪЬcШcJШEJШEJШEJШEJШ9JШ9JШ9JШ9JШ9JШ;JШ;JШ(JШ(JШ*JШ*JШJШ ЧЪЬЮЬЩ!JЩ JЩ JЩ JЩ"JЩ ЧЪ
б	ЬЮЬЮЬЮЬЮЬЩUЪб
ЬЮЬЮЬЩNJЩ%JЪ!ЬвЬвЬвЬвЬвЬвЬвЬвЬвЬвЬвЬвЬвЬвЬвЬвЬЩfJЩJЩ*JЩ*JЩ*JЩ*JЩЧJЩЧJЩ ЧJЪЮЬШJШJШ%JШ JЪЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬШOЪаЩЪ
бЬЮЬЮЬ"ЮЬЮЬШPJШJЪЬЮЬЮЬЮЬЮЬЮЬШ-ЪЮЬЮЬЮЬЮШЪЬ╧b╧uгЩЪЮЬШЪЮЬЮЬЮЬЮШJШFJШ=JШ-JШJЪЮШЧЪЮЬЮЬЮЬЮШJШJШJШJШJЪЮЬШЧЧЧЪЬгЬЩЪЮЬЮЬЮЬЮШJШBJШ:JШ,JШJЪЮЬШЧЧJЪЮЬШЧJШЧЧЪаЩЪбЬЮЬЮЬ/вЬвЬ
вЮЬвЬвЬШ]JШ%JШJЪЬЮЬЮЬШJЪЬЮЬ	ШJЪЬЮЬ	ШJЪЬЮЬШJЪЬЮЬ
ШJЪЬЮЬЮЬ
ШJЪЬЮЬ	ШJЪЬЮЬ	ШJЪЬЮЬ	ШJЪЬЮЬ
ШJЪЬЮЬЮЬШЩЪЮЬЮЬЮЬЮШЪЮЬЮЬЮЬЮШЪЮЬЮЬЮЬЮШШJШJШJШJШЧJЪЮЬШЧJЪЮЬШЧJЪЮЬШЧЧЪЮЬЮЬЮЬЮШЪЬ"гЬ	дЬЩ.ЪЮЬЮЬЮЬЮШJШ JШIJШ$JШ2JЪЮЬШЧЧЪЬгЬЩЪЮЬЮЬЮЬЮШJШJШCJШ"JШ0JЪЮЬШЧJЪЮЬШЧЧJШЧJЩ ЧJШ Ч ЕЧ    ╠  #j  