%! % THREE CUBIC SPLINE GENERATION ALGORITHMS % ======================================== % by Don Lancaster % SUMMARY: Tutorial and demo looks at three different ways to generate % cubic splines. Which is to use the PostScript -curveto- operator, % to brute force plot the equations in t space, or to use an % elegant "differencing method" that only needs repeated additions. % Copyright c. 1998 by Don Lancaster and Synergetics, Box 809, % Thatcher AZ, 85552 (520) 428-4073. synergetics@tinaja.com % All commercial rights and all electronic media rights are % *fully* reserved. Linking welcome. Reposting is expressly forbidden. % Consulting services available. % Further support on www.tinaja.com/info01.html % The GENERAL PROCEDURE for using PostScript-as-language is as % follows: % (1) Carefully READ the entire sourcecode file inside your % favorite WP or Editor as an ASCII textfile. % % (2) Carefully MODIFY the filenames and variables and such % so they apply to you. % % (3) SAVE the modified code AS A STANDARD ASCII TEXTFILE % using a unique filename. % % (4) RUN the modified code by dragging and dropping it into % Acrobat Distiller. GhostScript may alternately be used. % % (5) TEST, INTERPRET, and MODIFY your results. % %%%%%%%%%%%% (A) INSTALL AND RUN GONZO UTILITIES %%%%%%%%%%%%%%%%%% % ========= % This file requires the previous download of gonzo.psl % available from http://www.tinaja.com/post01.asp % Make sure the following line agrees with your own gonzo.psl location (C:/Users/don/Desktop/gonzo/gonzo.psl) run % use internal gonzo % ========== gonzo begin % activate the gonzo utilities ps.util.1 begin % printerror nuisance begin %%%%%%%%%%%% (B) USE THE POSTSCRIPT -CURVETO- OPERATOR %%%%%%%%%%%%%% % first establish a rubbergrid... 60 175 8 setgrid 65 50 showgrid % pick your control points. This would probably be a matrix later on... /x0 0 def /y0 0 def /x1 10 def /y1 45 def /x2 50 def /y2 40 def /x3 60 def /y3 10 def % Plot the spline as a standard PostScript curveto... x0 y0 moveto x1 y1 x2 y2 x3 y3 curveto line1 stroke % Show the control points x0 y0 mt dot x1 y1 mt dot x2 y2 mt dot x3 y3 mt dot %%%%%%%%%%%%%(C) BRUTE FORCE T-PARAMETER PLOTTING %%%%%%%%%%%%%%% % calculate t-power coefficients a-d given control points. See HACK62.PDF for % more details. This moves you from graph space to math space.. /ax x3 x2 3 mul sub x1 3 mul add x0 sub def /ay y3 y2 3 mul sub y1 3 mul add y0 sub def /bx x2 3 mul x1 6 mul sub x0 3 mul add def /by y2 3 mul y1 6 mul sub y0 3 mul add def /cx x1 3 mul x0 3 mul sub def /cy y1 3 mul y0 3 mul sub def /dx x0 def /dy y0 def % check for identical results by actually plotting the t equations % one unit above original... gsave 0 1 translate % move new curve up by one for visibility. 0 0 moveto 0 0.01 1 {/tt exch store tt ax mul bx add tt mul cx add tt mul dx add tt ay mul by add tt mul cy add tt mul dy add lineto} for stroke grestore %%%%%%%%%%% (D) ELEGANT ADDITION-ONLY DIFFERENCING METHOD %%%%%%%% % The method works as follows. Given a point on the spline curve, the next % point on the curve can be found by simple addition of running terms. % The method is device and language independent, letting you generate % a cubic spline **without** using the PostScript -curveto- operator! /numincs 100 def % number of steps to generate the spline % next, precalculate delta-t increment, square, and cube /dt1 1 numincs div store % delta t /dt2 dt1 dup mul store % delta t squared /dt3 dt1 dt2 mul store % delta t cubed % initialize some stuff... /xx dx store /yy dy store /ux 0 store /uy 0 store /vx 0 store /vy 0 store /mx1 ax dt3 mul store /my1 ay dt3 mul store /lx1 bx dt2 mul store /ly1 by dt2 mul store /kx mx1 lx1 add cx dt1 mul add store /ky my1 ly1 add cy dt1 mul add store /mx mx1 6 mul store /my my1 6 mul store /lx mx lx1 2 mul add store /ly my ly1 2 mul add store % now generate the fake curveto... 0 2 translate % tempory offset xx yy moveto numincs { /xx xx ux add kx add store /yy yy uy add ky add store /ux ux vx add lx add store /uy uy vy add ly add store /vx vx mx add store /vy vy my add store xx yy lineto } repeat line2 stroke % Note that successive points along the curve require only *ten* repeated % additions. There are no multiplies or other time-intensive operators. % Note that this is **not** an approximation, but an exact solution! % Try changing -numincs- to 3 to prove this to yourself. showpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Copyright c. 1998 by Don Lancaster and Synergetics, Box 809, % Thatcher AZ, 85552 (520) 428-4073. synergetics@tinaja.com % All commercial rights and all electronic media rights are % *fully* reserved. Linking welcome. Reposting is expressly forbidden. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%EOF