%!
% 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