%! % Subdividing a Cubic Spline % =========================================================== % by Don Lancaster v1.3 February 8, 1998 Version 1.1 January 15, 1998 % Copyright c. 1992, 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 avaialable % Further support on www.tinaja.com/info01.html %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % (The following is believed correct. Please report any errors or differing experiences.) % SUMMARY: Guru Don Lancaster gives us three new methods to subdivide % a cubic spline into individual chord segments. % % These include the CONSTANT ERROR method useful for vector % conversion, the CONSTANT T PARAMETER method useful for % various art applications, and Don's new and nonobvious % CONSTANT CHORD LENGTH method for placing glyphs along an % arbitrary path. % % ************************************************************************ % There are lots of intriguing PostScript opportunities that emerge % whenever you subdivide a cubic spline into smaller pieces. % There are three methods that yield different results for different % purposes: % (A) The CONSTANT ERROR method uses the flattenpath operator % to break the spline up into chords of usually uneven % length. Any and all chords will always be within a % given error distance to the real curve. % % One use is to convert PostScript curves into vectors % for use on a plotter, Santa Claus machine, engraver, % embroidery or other non-PostScript device. % (B) The CONSTANT "t" PARAMETER method uses the equations % behind cubic splines to break the spline up into chords % of usually uneven length. The chords will be somewhat % longer along the "more bent" portions of the curve. % % Two uses are for avuncular sleezoids or similar "artsy % craftsy" stuff. % (C) The CONSTANT CHORD method uses successive approximations % of method (B) to break the spline up into chords of % virtually identical length. This method is non obvious % and computationally intensive. But the results are % easily distilled and compiled. % % One major use is to nonlinear map border elements or % other glyphs along a serpentine or otherwise arbitrary % path. More on this in a followup file. % Let's look at each method in turn, generating some working utilities % along the way. We will use my gonzo utilities to quickly and conveniently % show the results. Most of the actual tools do not necessarily require % gonzo for their final use. %%%%%%%%% (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 % Build a graph space... 100 100 10 setgrid % set up a working grid 30 40 showgrid % and show part of it %%%%%%%%%%%%%%% (B) CONSTANT ERROR METHOD %%%%%%%%%%%%%%%%%%%%%% % The CONSTANT ERROR method uses the flattenpath operator to break % the spline up into chords of usually uneven length. Any and all % chords will always be within a given error distance to the real % curve. The chords will typically be different lengths. gsave 0 5 translate % position on graph /maxpixelerror 5 def % set maximum error in pixels line1 % set drawing width beige 0.25 setgray % nice color gsave 5 0 mt 10 10 20 0 25 10 curveto % define the curve gsave stroke grestore % draw the curve gsave maxpixelerror setflat % replace curve with chords flattenpath mark % create xy array for use or export {}{}{}{} pathforall ] /xyvalues exch def grestore % showflatchords plots the endpoints of your chords /showflatchordends {0 2 xyvalues length 1 sub {/posn exch def xyvalues posn get xyvalues posn 1 add get mt dot} for} def showflatchordends % show chord ends as dots /cstretch 0.04 def % and Gonzo label the curve /sstretch 0.2 def /font1 /Helvetica 0.85 gonzofont font1 black 12 3 ((A) Constant error method) cl grestore %%%%%%%%%%%%%%% (C) CONSTANT "t" PARAMETER METHOD %%%%%%%%%%%%%%%%%%% % The CONSTANT "t" PARAMETER method uses the equations behind cubic % splines to break the spline up into chords of usually uneven length. % The chords will be somewhat longer along the "more bent" portions % of the curve. % Let's start with three Bezier general curve utilities % grabcoeffs takes the eight spline xy values and changes them into % some intermediate variables handy to calculate x and y as a function % of t... /grabcoeffs { /y3a exch def % final y /x3a exch def % final x /y2a exch def % 2nd influence y /x2a exch def % 2nd influence x /y1a exch def % 1st influence y /x1a exch def % 1st influence x /y0a exch def % initial y /x0a exch def % initial x /A x3a x1a x2a sub 3 mul add x0a sub store % as in A(x)t^3 /B x2a x1a dup add sub x0a add 3 mul store % as in B(x)t^2 /C x1a x0a sub 3 mul store % as in C(x)t /D y3a y1a y2a sub 3 mul add y0a sub store % as in D(y)t^3 /E y2a y1a dup add sub y0a add 3 mul store % as in E(y)t^2 /F y1a y0a sub 3 mul store % as in F(y)t } def % And this is the "magic" code to find x and y given tt from 0 to 1.. /ytt { dup dup D mul E add mul F add mul y0a add} def /xtt { dup dup A mul B add mul C add mul x0a add} def gsave 0 10 translate % set position on graph line1 % set the linewidth beige 0.25 setgray % nice color 5 0 10 10 20 0 25 10 grabcoeffs % grab curveto values 5 0 moveto 10 10 20 0 25 10 % draw the curve curveto stroke /numsegs 14 def % select number of segments x0a y0a mt % plot the dots 0 1 numsegs div 1.0001 {dup xtt exch ytt lineto currentpoint dot mt} for % Note that the tt values are 0, 1 numsegs div, 2 numsegs div, ... 1 % An explicit custom array is probably not required /cstretch 0.04 def % and Gonzo label the curve /sstretch 0.2 def /font1 /Helvetica 0.85 gonzofont font1 black 12 3 ((B) Constant "t" parameter method) cl grestore grestore %%%%%%%%%%%%%%% (D) CONSTANT CHORD METHOD %%%%%%%%%%%%%%%%%%% % The CONSTANT CHORD method uses successive approximations of method % (B) to break the spline up into chords of virtually identical length. % This method is non obvious and computationally intensive. But the % results are easily distilled and compiled. % bezierlength finds the length of a Bezier curve and leaves that length % on the stack. It works by breaking the curve up into straight line % approximate segments. /bezierlength {/oldx x0a store /oldy y0a store /blength 0 store 0 1 numlenpts 1 sub div 1.0001 {dup xtt exch ytt /newy exch store /newx exch store newx oldx sub dup mul newy oldy sub dup mul add sqrt blength add /blength exch store /oldy newy store /oldx newx store} for }def gsave 0 20 translate % set position on graph line1 % set the linewidth beige 0.25 setgray % nice color /numlenpts 400 def % # of samples for length 5 0 10 10 20 0 25 10 grabcoeffs % grab curveto values bezierlength % get 23.9937 in this example /segments 14 def % number of equal length chords /chord blength segments div def % length along curve between repeats /numtrials 100 def % needed accuracy of chording % grabprevxy saves the previous x and y values /grabprevxy { dup dup xtt /prevx exch store ytt /prevy exch store} def % findchordguess measures the current chord /findchordguess {dup dup xtt exch ytt prevy sub dup mul exch prevx sub dup mul add sqrt} def % guessnextttt estimates the chord length by assuming it is equal to % the change in t. This greatly reduces the number of trials needed... /guessnexttt {1 copy 1 segments div add findchordguess chord lt} def % findtvalues creates an array of the t values needed for virtually % equal length chords /findtvalues {mark 0 grabprevxy segments {guessnexttt /guessdir exch store {1 segments numtrials mul div guessdir {add}{sub} ifelse findchordguess chord guessdir {gt}{lt} ifelse {exit} if dup dup 0 lt exch 1 gt or {exit} if} loop grabprevxy} repeat 1 gt {1} if ] /ttvalues exch def} def findtvalues % creates an array of tt values % plotchordvalues puts a dot at each tt location /plotchordvalues { ttvalues { dup xtt exch ytt mt dot} forall } def gsave 0 5 translate line1 x0a y0a moveto x1a y1a x2a y2a x3a y3a curveto stroke plotchordvalues /cstretch 0.04 def % and Gonzo label the curve /sstretch 0.2 def /font1 /Helvetica 0.85 gonzofont font1 black 12 3 ((C) Constant chord length method) cl grestore showpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % See http://www.tinaja.com/glib/bezchord.pdf for a demo %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % 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 avaialable % Further support on www.tinaja.com/info01.html %EOF