| 1 |
% nurbstobezier.mp |
| 2 |
% Troy Henderson |
| 3 |
% 2007 |
| 4 |
|
| 5 |
prologues := 1; |
| 6 |
|
| 7 |
% Evaluate a cubic polynomial of the "standard" Bezier form at t |
| 8 |
vardef evalbezier(expr p,t) = |
| 9 |
save _a,_b,_c,_d; |
| 10 |
numeric _a,_b,_c,_d; |
| 11 |
_a:=(1-t)**3; |
| 12 |
_b:=3*((1-t)**2)*t; |
| 13 |
_c:=3*(1-t)*(t**2); |
| 14 |
_d:=t**3; |
| 15 |
(point 0 of p)*_a + (postcontrol 0 of p)*_b + (precontrol 1 of p)*_c + (point 1 of p)*_d |
| 16 |
enddef; |
| 17 |
|
| 18 |
% Evaluate the derivative of a cubic polynomial of the "standard" |
| 19 |
% Bezier form at t |
| 20 |
vardef evalbezierderivative(expr p,t) = |
| 21 |
save _a,_b,_c; |
| 22 |
pair _a,_b,_c; |
| 23 |
_a:=3*((point 1 of p) - 3*(precontrol 1 of p) + 3*(postcontrol 0 of p) -(point 0 of p)); |
| 24 |
_b:=6*((precontrol 1 of p) - 2*(postcontrol 0 of p) + (point 0 of p)); |
| 25 |
_c:=3*((postcontrol 0 of p) - (point 0 of p)); |
| 26 |
_a*(t**2) + _b*t + _c |
| 27 |
enddef; |
| 28 |
|
| 29 |
% Evaluate a rational function of the "standard" cubic NURBS form at t |
| 30 |
vardef evalnurbs(expr p,w,t) = |
| 31 |
save _q,_r; |
| 32 |
path _q,_r; |
| 33 |
_q:=((cyanpart w)*(point 0 of p)).. controls ((magentapart w)*(postcontrol 0 of p)) and ((yellowpart w)*(precontrol 1 of p)) .. ((blackpart w)*(point 1 of p)); |
| 34 |
_r:=(cyanpart w,0) .. controls (magentapart w,0) and (yellowpart w,0) .. (blackpart w,0); |
| 35 |
evalbezier(_q,t)/(xpart evalbezier(_r,t)) |
| 36 |
enddef; |
| 37 |
|
| 38 |
% Evaluate the derivative of a rational function of the "standard" |
| 39 |
% cubic NURBS form at t |
| 40 |
vardef evalnurbsderivative(expr p,w,t) = |
| 41 |
save _a,_b,_c,_d,_q,_r; |
| 42 |
pair _a,_b; |
| 43 |
numeric _c,_d; |
| 44 |
path _q,_r; |
| 45 |
_q:=((cyanpart w)*(point 0 of p)) .. controls ((magentapart w)*(postcontrol 0 of p)) and ((yellowpart w)*(precontrol 1 of p)) .. ((blackpart w)*(point 1 of p)); |
| 46 |
_r:=(cyanpart w,0) .. controls (magentapart w,0) and (yellowpart w,0) .. (blackpart w,0); |
| 47 |
_a:=evalbezier(_q,t); |
| 48 |
_b:=evalbezierderivative(_q,t); |
| 49 |
_c:=xpart evalbezier(_r,t); |
| 50 |
_d:=xpart evalbezierderivative(_r,t); |
| 51 |
(_b*_c-_a*_d)/(_c**2) |
| 52 |
enddef; |
| 53 |
|
| 54 |
% Fit a cubic polynomial of the "standard" Bezier form to a |
| 55 |
% rational function of the |
| 56 |
% "standard" cubic NURBS form with function and derivative agreement |
| 57 |
% at tmin and tmax |
| 58 |
vardef nurbstobezier(expr p,w,tmin,tmax) = |
| 59 |
save _a,_b,_c,_d,_e; |
| 60 |
pair _a,_b,_c,_d; |
| 61 |
numeric _e; |
| 62 |
_e:=(tmax-tmin)/3; |
| 63 |
_a:=evalnurbs(p,w,tmin); |
| 64 |
_b:=_a + _e*evalnurbsderivative(p,w,tmin); |
| 65 |
_d:=evalnurbs(p,w,tmax); |
| 66 |
_c:=_d - _e*evalnurbsderivative(p,w,tmax); |
| 67 |
_a .. controls _b and _c .. _d |
| 68 |
enddef; |
| 69 |
|
| 70 |
% Reparameterize a cubic polynomial of the "standard" Bezier form by mapping |
| 71 |
% the interval [tmin,tmax] to [0,1] |
| 72 |
vardef beziertobezier(expr p,tmin,tmax) = |
| 73 |
nurbstobezier(p,(1,1,1,1),tmin,tmax) |
| 74 |
enddef; |
| 75 |
|
| 76 |
% Evalute the L^2[0,1] norm of a cubic polynomial of the "standard" |
| 77 |
% Bezier form |
| 78 |
vardef beziernorm(expr p) = |
| 79 |
save _a,_b,_c,_d,_i,_xabs,_yabs,_A,_B,_C,_D,_I; |
| 80 |
numeric _a,_b,_c,_d,_i,_xabs,_yabs,_A,_B,_C,_D,_I; |
| 81 |
_xabs:=max(abs(xpart point 0 of p),abs(xpart postcontrol 0 of p),abs(xpart precontrol 1 of p),abs(xpart point 1 of p)); |
| 82 |
_yabs:=max(abs(ypart point 0 of p),abs(ypart postcontrol 0 of p),abs(ypart precontrol 1 of p),abs(ypart point 1 of p)); |
| 83 |
if (_xabs > 0): |
| 84 |
_a:=xpart((point 1 of p) - 3*(precontrol 1 of p) + 3*(postcontrol 0 of p) - (point 0 of p))/_xabs; |
| 85 |
_b:=3*xpart((precontrol 1 of p) - 2*(postcontrol 0 of p) + (point 0 of p))/_xabs; |
| 86 |
_c:=3*xpart((postcontrol 0 of p) - (point 0 of p))/_xabs; |
| 87 |
_d:=xpart(point 0 of p)/_xabs; |
| 88 |
_i:=(_a**2)/7 + ((_b)**2 + 2*_a*_c)/5 + (_a*_b + 2*_b*_d + (_c**2))/3 + (_a*_d + _b*_c)/2 + (_c*_d + (_d**2)); |
| 89 |
else: |
| 90 |
_i:=0; |
| 91 |
fi; |
| 92 |
if (_yabs > 0): |
| 93 |
_A:=ypart((point 1 of p) - 3*(precontrol 1 of p) + 3*(postcontrol 0 of p) - (point 0 of p))/_yabs; |
| 94 |
_B:=3*ypart((precontrol 1 of p) - 2*(postcontrol 0 of p) + (point 0 of p))/_yabs; |
| 95 |
_C:=3*ypart((postcontrol 0 of p) - (point 0 of p))/_yabs; |
| 96 |
_D:=ypart(point 0 of p)/_yabs; |
| 97 |
_I:=(_A**2)/7 + ((_B)**2 + 2*_A*_C)/5 + (_A*_B + 2*_B*_D + (_C**2))/3 + (_A*_D + _B*_C)/2 + (_C*_D + (_D**2)); |
| 98 |
else: |
| 99 |
_I:=0; |
| 100 |
fi; |
| 101 |
(_xabs*sqrt(_i)) ++ (_yabs*sqrt(_I)) |
| 102 |
enddef; |
| 103 |
|
| 104 |
% Fit a cubic Bezier spline to a rational function of the "standard" |
| 105 |
% cubic NURBS form by iteratively refining the Bezier curve. |
| 106 |
% p is a 4 point path containing the 4 cubic NURBS (2D) control points |
| 107 |
% w is a cmykcolor containing the 4 cubic NURBS weights |
| 108 |
% EPS is the tolerance to stop refining each branch of the Bezier spline |
| 109 |
vardef fitnurbswithbezier(expr p,w,EPS) = |
| 110 |
save _a,_b,_c,_e,_error,_k,_q; |
| 111 |
numeric _a,_b,_c,_error,_k; |
| 112 |
path _q,_q[],_e; |
| 113 |
_a:=0; |
| 114 |
_b:=1; |
| 115 |
_k:=1/sqrt(2); |
| 116 |
_q:=(point 0 of p); |
| 117 |
_q[4]:=nurbstobezier(p,w,_a,_b); |
| 118 |
forever: |
| 119 |
exitunless(_a<1); |
| 120 |
_q[1]:=_q[4]; |
| 121 |
_c:=_b-_k*((_b-_a)**2); |
| 122 |
_q[2]:=beziertobezier(_q[1],_a,_c); |
| 123 |
_q[3]:=nurbstobezier(p,w,_a,_c); |
| 124 |
_q[4]:=_q[3]; |
| 125 |
_e:=((point 0 of _q[2])-(point 0 of _q[3])) .. controls ((postcontrol 0 of _q[2])-(postcontrol 0 of _q[3])) and ((precontrol 1 of _q[2])-(precontrol 1 of _q[3])) .. ((point 1 of _q[2])-(point 1 of _q[3])); |
| 126 |
_error:=beziernorm(_e)/beziernorm(_q[3]); |
| 127 |
show _error; |
| 128 |
if (_error > EPS): |
| 129 |
_b:=_c; |
| 130 |
else: |
| 131 |
_q[2]:=beziertobezier(_q[1],_c,_b); |
| 132 |
_q[3]:=nurbstobezier(p,w,_c,_b); |
| 133 |
_e:=((point 0 of _q[2])-(point 0 of _q[3])) .. controls ((postcontrol 0 of _q[2])-(postcontrol 0 of _q[3])) and ((precontrol 1 of _q[2])-(precontrol 1 of _q[3])) .. ((point 1 of _q[2])-(point 1 of _q[3])); |
| 134 |
_error:=beziernorm(_e)/beziernorm(_q[3]); |
| 135 |
if (_error > EPS): |
| 136 |
_q:=_q .. controls (postcontrol 0 of _q[4]) and (precontrol 1 of _q[4]) .. (point 1 of _q[4]); |
| 137 |
_a:=_c; |
| 138 |
_q[4]:=_q[3]; |
| 139 |
else: |
| 140 |
_q:=_q .. controls (postcontrol 0 of _q[1]) and (precontrol 1 of _q[1]) .. (point 1 of _q[1]); |
| 141 |
_a:=_b; |
| 142 |
_q[4]:=nurbstobezier(p,w,_a,1); |
| 143 |
fi; |
| 144 |
_b:=1; |
| 145 |
fi; |
| 146 |
endfor; |
| 147 |
_q |
| 148 |
enddef; |
| 149 |
|
| 150 |
% This macro is used to provide a path to draw the NURBS |
| 151 |
% It returns a path of length N passing through N+1 equally spaced |
| 152 |
% (in time) points along the NURBS connected by line segments |
| 153 |
vardef samplednurbs(expr p,w,N) = |
| 154 |
save _a,_b,_c,_d,_n,_t,_q; |
| 155 |
numeric _a,_b,_c,_d,_n,_t; |
| 156 |
path _q; |
| 157 |
_q:=(point 0 of p); |
| 158 |
for _n=1 upto N: |
| 159 |
_t:=_n/N; |
| 160 |
_a:=(cyanpart w)*((1-_t)**3); |
| 161 |
_b:=3*(magentapart w)*((1-_t)**2)*_t; |
| 162 |
_c:=3*(yellowpart w)*(1-_t)*(_t**2); |
| 163 |
_d:=(blackpart w)*(_t**3); |
| 164 |
_q:=_q .. ((_a*(point 0 of p)+_b*(postcontrol 0 of p)+_c*(precontrol 1 of p)+_d*(point 1 of p))/(_a+_b+_c+_d)); |
| 165 |
endfor; |
| 166 |
( _q ) |
| 167 |
enddef; |
| 168 |
|
| 169 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 170 |
% Here's where the fun begins % |
| 171 |
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 172 |
|
| 173 |
beginfig(0); |
| 174 |
% p contains the 4 control points of the rational function of the |
| 175 |
% "standard" cubic NURBS form |
| 176 |
path p; |
| 177 |
p:=(297.63725,297.63725) .. controls (132.98871,286.67885) and (180.62535,152.16249) .. (429.54399,226.31157); |
| 178 |
|
| 179 |
% w contains the 4 weights for the rational function of the |
| 180 |
% "standard" cubic NURBS form |
| 181 |
cmykcolor w; |
| 182 |
w:=(2.15756,1.6709,0.8598,1.34647); |
| 183 |
|
| 184 |
% EPS represents the minimum "acceptable error" to stop refining any |
| 185 |
% given branch of the Bezier |
| 186 |
Err:=0.040; |
| 187 |
|
| 188 |
% q represents the Bezier spline fit to the rational function of the |
| 189 |
% "standard" cubic NURBS form |
| 190 |
path q; |
| 191 |
q:=fitnurbswithbezier(p,w,Err); |
| 192 |
% q:=fitnurbswithbezier(reverse p,(blackpart w,yellowpart w,magentapart w,cyanpart w),Err); |
| 193 |
|
| 194 |
% draw the NURBS by sampling it at many points and connecting the |
| 195 |
% samples via line segments |
| 196 |
draw samplednurbs(p,w,20) withcolor red withpen pencircle scaled 2bp; |
| 197 |
|
| 198 |
% draw the Bezier spline and its knots |
| 199 |
draw q; |
| 200 |
for n=0 upto length q: |
| 201 |
draw fullcircle scaled 2 shifted point n of q withcolor blue; |
| 202 |
endfor; |
| 203 |
endfig; |
| 204 |
|
| 205 |
end |