%!PS % An improved Bezier Cubic Spline through 4 points utility % ======================================================== % by Don Lancaster % Copyright c 2006 by Don Lancaster & Synergetics, Box 809, Thatcher, AZ, 85552 % (928) 428-4073 Email: don@tinaja.com Website: http://www.tinaja.com % Consulting services available http://www.tinaja.com/info01.html % All commercial rights and all electronic media rights ~fully~ reserved. % Linking usually welcome. Reposting expressly forbidden. Version 1.1 % IMPORTANT NOTE: Don Lancaster's file gonzo.ps is optional but recommended % for this program. To activate after obvious location mods, uncomment ONE % of the following two lines: (C:\\Documents and Settings\\don\\Desktop\\gonzo\\gonzo.ps) run % use internal gonzo % (A:\\gonzo.ps) run % use external gonzo % NOTE THAT ALL PS FILENAME STRINGS !!!DEMAND!!! DOUBLE REVERSE SLASHES. % Accepts four ON-CURVE cubic spline data points of x0y0, x4y4, x5y5, and x3y3 and % transforms them via basis functins to standard control points of x0y0, x1y1, x2y2, % and x3y3. Chord apportionment used to restrict spline choice. % Run as PostScript ASCII textfile sent to Acrobat Distiller. % Linear equation solver utility solves equation pair ai + bj = c and di + ej = f % if a solution exists. Multiplies second equation by a/d, subtracts the two, and % then back substitutes. Code left obvious rather than speed optimized. % Returns untrapped div(0) error if equations are parallel lines with no solution. /solvexy {/ff exch store % grab data values /ee exch store /dd exch store /cc exch store /bb exch store /aa exch store cc aa dd div ff mul sub % find j bb aa ee mul dd div sub div /jj exch store /ii cc bb jj mul sub aa div store % find i ii jj } store % return to stack % New /bez4pts1 utility accepts ON-CURVE x0y0, x4y4, x5y5, and x3y3 and % transforms them to NORMAL CONTROL POINTS x0y0, x1y1, x2y2,x3y3, Restricts % curve selections by chord apportionment. Then does a normal curveto. % Uses basis function of xx = x0B0(t) + x1 B1(t) + x2B2(t) + x3B3(t) % An option of additional iterations is newly provided for a slightly % "better" final curve at additional calculation time. Defaults are... /iterations 1 store % # of passes total /improve {} store % default null routine /bez4pts1 {/y3 exch store % grab data /x3 exch store /y5 exch store % strange numbering here /x5 exch store /y4 exch store /x4 exch store /y0 exch store /x0 exch store /c1 x4 x0 sub dup mul y4 y0 sub % find chord lengths between points dup mul add sqrt store /c2 x5 x4 sub dup mul y5 y4 sub dup mul add sqrt store /c3 x3 x5 sub dup mul y3 y5 sub dup mul add sqrt store /t1 c1 dup c2 add c3 add div store % guess at the "best" t values /t2 c1 c2 add dup c3 add div store /b0 {1 exch sub dup dup mul mul} store % define basis functions /b1 {dup 1 exch sub dup mul mul 3 mul} store /b2 {dup 1 exch sub exch dup mul mul 3 mul} store /b3 {dup dup mul mul} store t1 b1 t1 b2 x4 x0 t1 b0 mul sub % transform to find x1 and x2 x3 t1 b3 mul sub t2 b1 t2 b2 x5 x0 t2 b0 mul sub x3 t2 b3 mul sub solvexy /x2 exch store /x1 exch store t1 b1 t1 b2 y4 y0 t1 b0 mul sub % transform to find y1 and y2 y3 t1 b3 mul sub t2 b1 t2 b2 y5 y0 t2 b0 mul sub y3 t2 b3 mul sub solvexy /y2 exch store /y1 exch store iterations 1 sub {improve} repeat % optional multi-pass improvement 0 0 0 setrgbcolor x0 y0 moveto % and draw the curve x1 y1 x2 y2 x3 y3 curveto } def %%% First Demo (no iterations) -- Remove or alter before reuse % To use, edit & save new standard ASCII textfile, then send to Acrobat Distiller. /data [100 100 200 120 300 190 267 300] store % your four on-curve data points /iterations 1 store % no repeatiterations /dot {gsave translate 0 0 2 0 360 arc fill grestore} store % dot utility data 0 get data 1 get dot % show the points data 2 get data 3 get dot data 4 get data 5 get dot data 6 get data 7 get dot data aload pop bez4pts1 % draw the curve 0.1 setlinewidth stroke showpage % and show it %%%%%%%%% "IMPROVED" version seeks out shortest or "best" curve through 4 points %%%%%% % This is preliminary code, so extra plotting and diagnostics have been left in. % An optimal method to find the shortest curve would be to actually compute the % true Bezier length. This is quite computationally intensive (besides still being % an approximation), so a much faster and simpler method is used that "should" give % very nearly the same results. % What happens is this: Each chord is subdivided into three cords, giving a nine-chord % approximation to the curve length. Revised values of t1 and t2 are then iterively % calculated. Convergence appears quite rapid, with negligible error after five passes. /improve { % optionally report present t1 and t2 (\n\nt1 is now ) t1 20 string cvs mergestr (.\n) mergestr print (t2 is now ) t2 20 string cvs mergestr (.\n) mergestr print (original length was ) c1 c2 add c3 add 20 string cvs mergestr (.\n) mergestr print % repeat some of the original code to find x1 and x2 /b0 {1 exch sub dup dup mul mul} store % define basis functions /b1 {dup 1 exch sub dup mul mul 3 mul} store /b2 {dup 1 exch sub exch dup mul mul 3 mul} store /b3 {dup dup mul mul} store t1 b1 t1 b2 x4 x0 t1 b0 mul sub % transform to find x1 and x2 x3 t1 b3 mul sub t2 b1 t2 b2 x5 x0 t2 b0 mul sub x3 t2 b3 mul sub solvexy /x2 exch store /x1 exch store t1 b1 t1 b2 y4 y0 t1 b0 mul sub % transform to find y1 and y2 y3 t1 b3 mul sub t2 b1 t2 b2 y5 y0 t2 b0 mul sub y3 t2 b3 mul sub solvexy /y2 exch store /y1 exch store % find nine chords that approximate the total curve length. Note that new x and % y values must be found for the intermediate chord ends per the sub utilities below 0 findx 0 findy 2 copy /yy0 exch store /xx0 exch store t1 3 div findx t1 3 div findy /yy1 exch store /xx1 exch store /c11 xx1 xx0 sub dup mul yy1 yy0 sub dup mul add sqrt store t1 3 div 2 mul findx t1 3 div 2 mul findy /yy2 exch store /xx2 exch store /c12 xx2 xx1 sub dup mul yy2 yy1 sub dup mul add sqrt store t1 findx t1 findy /yy3 exch store /xx3 exch store /c13 xx3 xx2 sub dup mul yy3 yy2 sub dup mul add sqrt store t2 t1 sub 3 div t1 add findx t2 t1 sub 3 div t1 add findy /yy4 exch store /xx4 exch store /c21 xx4 xx3 sub dup mul yy4 yy3 sub dup mul add sqrt store t2 t1 sub 3 div 2 mul t1 add findx t2 t1 sub 3 div 2 mul t1 add findy /yy5 exch store /xx5 exch store /c22 xx5 xx4 sub dup mul yy5 yy4 sub dup mul add sqrt store t2 findx t2 findy /yy6 exch store /xx6 exch store /c23 xx6 xx5 sub dup mul yy6 yy5 sub dup mul add sqrt store 1 t2 sub 3 div t2 add findx 1 t2 sub 3 div t2 add findy /yy7 exch store /xx7 exch store /c31 xx7 xx6 sub dup mul yy7 yy6 sub dup mul add sqrt store 1 t2 sub 3 div 2 mul t2 add findx 1 t2 sub 3 div 2 mul t2 add findy /yy8 exch store /xx8 exch store /c32 xx8 xx7 sub dup mul yy8 yy7 sub dup mul add sqrt store 1 findx 1 findy /yy9 exch store /xx9 exch store /c33 xx9 xx8 sub dup mul yy9 yy9 sub dup mul add sqrt store % optionally plot the new chords... 0 setlinewidth 1 0 0 setrgbcolor x0 y0 moveto xx1 yy1 lineto stroke xx1 yy1 dot xx1 yy1 moveto xx2 yy2 lineto stroke xx2 yy2 dot xx2 yy2 moveto xx3 yy3 lineto stroke xx3 yy3 dot xx3 yy3 moveto xx4 yy4 lineto stroke xx4 yy4 dot xx4 yy4 moveto xx5 yy5 lineto stroke xx5 yy5 dot xx5 yy5 moveto xx6 yy6 lineto stroke xx6 yy6 dot xx6 yy6 moveto xx7 yy7 lineto stroke xx7 yy7 dot xx7 yy7 moveto xx8 yy8 lineto stroke xx8 yy8 dot xx8 yy8 moveto xx9 yy9 lineto stroke xx9 yy9 dot % optionally calculate and report the revised length for this iteration (\n\nThe new approximate length is ) c11 c12 add c13 add c21 add c22 add c23 add c31 add c32 add c33 add 20 string cvs mergestr (.\n)mergestr print % revise the values of t1 and t2 per this iteration.... /t1 c11 c12 add c13 add c11 c12 add c13 add c21 add c22 add c23 add c31 add c32 add c33 add div store /t2 c11 c12 add c13 add c21 add c22 add c23 add c11 c12 add c13 add c21 add c22 add c23 add c31 add c32 add c33 add div store % optionally report the newly revised t1 and t2 values (\n\nt1 is now ) t1 20 string cvs mergestr (.\n) mergestr print (t2 is now ) t2 20 string cvs mergestr (.\n) mergestr print (\n\n\n\n\n) print flush % borrow code from original to find x1 x2 y1 y2 t1 b1 t1 b2 x4 x0 t1 b0 mul sub % transform to find x1 and x2 x3 t1 b3 mul sub t2 b1 t2 b2 x5 x0 t2 b0 mul sub x3 t2 b3 mul sub solvexy /x2 exch store /x1 exch store t1 b1 t1 b2 y4 y0 t1 b0 mul sub % transform to find y1 and y2 y3 t1 b3 mul sub t2 b1 t2 b2 y5 y0 t2 b0 mul sub y3 t2 b3 mul sub solvexy /y2 exch store /y1 exch store } store % Basis function calculations to find on-curve chord ends.... /findx { /tt exch store tt b0 x0 mul tt b1 x1 mul add tt b2 x2 mul add tt b3 x3 mul add } store /findy { /tt exch store tt b0 y0 mul tt b1 y1 mul add tt b2 y2 mul add tt b3 y3 mul add } store %%% Demo of iterive code -- Remove or alter before reuse 0 0 0 setrgbcolor % To use, edit & save new standard ASCII textfile, then send to Acrobat Distiller. % convergence info may be read from log file or bottom of distiller box. /iterations 25 store % wayyy to many. used to prove convergence. /data [100 100 200 120 300 190 267 300] store % your four on-curve data points /dot {gsave translate 0 0 2 0 360 arc fill grestore} store % dot utility data 0 get data 1 get dot % show the points data 2 get data 3 get dot data 4 get data 5 get dot data 6 get data 7 get dot data aload pop bez4pts1 % draw the curve 0.1 setlinewidth stroke showpage % and show it % eof