forked from fontforge/fontforge.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbezier.html
238 lines (238 loc) · 10.1 KB
/
bezier.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
<HTML>
<HEAD>
<!-- Created with AOLpress/2.0 -->
<!-- AP: Created on: 18-Dec-2000 -->
<!-- AP: Last modified: 20-Feb-2011 -->
<TITLE>Bézier Splines</TITLE>
<LINK REL="icon" href="fftype16.png">
<LINK REL="stylesheet" TYPE="text/css" HREF="/assets/css/old/FontForge.css">
</HEAD>
>
<div style="margin:0; height: 4 em; padding: 0.5em; background: red; color:yellow; text-align:center; font-size:1em; font-family: sans-serif;">
<p><a href="http://fontforge.github.io" style="padding: 0.5em; color: yellow; font-weight: bold; text-decoration: none;" onmouseover="this.style.background='black';" onmouseout="this.style.background='red';" >This is part of the old website. New website begins at fontforge.github.io</a></p>
<p><a href="https://github.com/fontforge/fontforge.github.io" style="padding: 0.5em; color: yellow; font-weight: bold; text-decoration: none;" onmouseover="this.style.background='black';" onmouseout="this.style.background='red';" >Are you a web developer? Help us migrate this page on Github</a></p>
</div>
<DIV id="in">
<H1 ALIGN=Center>
Bézier<SUP><SMALL><A HREF="#bezier">1</A></SMALL></SUP> Splines
</H1>
<P>
<IMG SRC="/assets/img/old/splines.gif" WIDTH="172" HEIGHT="179" ALIGN="Left">Technically
PostScript uses cubic Bézier splines. Each control point determines
the slope of the spline at the corresponding end point. TrueType uses quadratic
Bézier splines, in these there is only one control point between two
end points and that point determines the slope of the spline at both end
points. Both formats also use lines (which are linear Bézier splines).
<P>
<IMG SRC="/assets/img/old/quadbezier.gif" WIDTH="113" HEIGHT="88" ALIGN="Right">It is also
possible to have other degree Bézier splines. For a quartic spline
there would be 3 control points, for a quintic 4 control points, etc. Of
these only the linear, quadratic and cubic splines are interesting to us--
those used by TrueType and PostScript.
<P>
The examples at left are cubic splines with two control points, each determining
the slope at the nearest end point, while the example at right shows a quadratic
spline with one control point used to determine the slopes at both end points.
<P>
In general if there are n+1 points labeled P<SUB>0</SUB>, P<SUB>1</SUB>,
... P<SUB>n</SUB>, with P<SUB>0</SUB> and P<SUB>n</SUB> the end points (and
all the others control points) then the equation of the Bézier spline
between them is: <IMG SRC="/assets/img/old/bezier.gif" WIDTH="137" HEIGHT="56" ALIGN="Middle">.
If there are two points then this is just the line between the two end points,
if three then the quadratic spline used by TrueType, if four then the cubic
spline used by PostScript.
<P>
A cubic Bézier curve may be viewed as:
<BLOCKQUOTE>
x = a<SUB>x</SUB>*t<SUP>3</SUP> + b<SUB>x</SUB>*t<SUP>2</SUP> +
c<SUB>x</SUB>*t +d<SUB>x</SUB><BR>
y = a<SUB>y</SUB>*t<SUP>3</SUP> + b<SUB>y</SUB>*t<SUP>2</SUP> +
c<SUB>y</SUB>*t +d<SUB>y</SUB>
</BLOCKQUOTE>
<P>
Where
<TABLE CELLPADDING="2">
<TR>
<TD> </TD>
<TD>d<SUB>x </SUB>= P0.x</TD>
<TD>d<SUB>y</SUB> = P0.y</TD>
</TR>
<TR>
<TD></TD>
<TD>c<SUB>x</SUB> = 3*P1.x-3*P0.x</TD>
<TD>c<SUB>y</SUB> = 3*P1.y-3*P0.y</TD>
</TR>
<TR>
<TD></TD>
<TD>b<SUB>x</SUB> = 3*P2.x-6*P1.x+3*P0.x</TD>
<TD>b<SUB>y</SUB> = 3*P2.y-6*P1.y+3*P0.y</TD>
</TR>
<TR>
<TD></TD>
<TD>a<SUB>x</SUB> = P3.x-3*P2.x+3*P1.x-P0.x</TD>
<TD>a<SUB>y</SUB> = P3.y-3*P2.y+3*P1.y-P0.y</TD>
</TR>
</TABLE>
<P>
And a quadratic Bézier curve:
<BLOCKQUOTE>
x = b<SUB>x</SUB>*t<SUP>2</SUP> + c<SUB>x</SUB>*t +d<SUB>x</SUB><BR>
y = b<SUB>y</SUB>*t<SUP>2</SUP> + c<SUB>y</SUB>*t +d<SUB>y</SUB>
</BLOCKQUOTE>
<P>
with
<TABLE CELLPADDING="2">
<TR>
<TD> </TD>
<TD>d<SUB>x</SUB> = P0.x</TD>
<TD>d<SUB>y</SUB> = P0.y</TD>
</TR>
<TR>
<TD></TD>
<TD>c<SUB>x</SUB> = 2*P1.x-2*P0.x</TD>
<TD>c<SUB>y</SUB> = 2*P1.y-2*P0.y</TD>
</TR>
<TR>
<TD></TD>
<TD>b<SUB>x</SUB> = P2.x-2*P1.x+P0.x</TD>
<TD>b<SUB>y</SUB> = P2.y-2*P1.y+P0.y</TD>
</TR>
</TABLE>
<P>
And a line:
<TABLE CELLPADDING="2">
<TR>
<TD> </TD>
<TD>d<SUB>x </SUB>= P0.x</TD>
<TD>d<SUB>y</SUB> = P0.y</TD>
</TR>
<TR>
<TD></TD>
<TD>c<SUB>x</SUB> = P1.x-P0.x</TD>
<TD>c<SUB>y</SUB> = P1.y-P0.y</TD>
</TR>
</TABLE>
<H2>
Converting <A NAME="ttf2ps">TrueType to PostScript</A>
</H2>
<P>
Lines convert with no math whatsoever.
<P>
Any quadratic spline can be expressed as a cubic (where the cubic term is
zero). The end points of the cubic will be the same as the quadratic's.
<BLOCKQUOTE>
CP<SUB>0</SUB> = QP<SUB>0</SUB><BR>
CP<SUB>3</SUB> = QP<SUB>2</SUB>
</BLOCKQUOTE>
<P>
The two control points for the cubic are:
<BLOCKQUOTE>
CP<SUB>1</SUB> = QP<SUB>0</SUB> + 2/3
*(QP<SUB>1</SUB>-QP<SUB>0</SUB>)<BR>
CP<SUB>2</SUB> = QP<SUB>2</SUB> + 2/3 *(QP<SUB>1</SUB>-QP<SUB>2</SUB>)
</BLOCKQUOTE>
<P>
So converting from TrueType to PostScript is trivial. There is a slight error
introduced due to rounding, but it is usually not noticeable.
<P>
(Anish Mehta points out that in truetype it is possible to specify points
which are in the middle of a pixel (ie. with an x or y value ending in 1/2).
These will also introduce rounding errors when converted to postscript, but
here the solution is simple: Scale the em-square of the font by a factor
of 2 and the problem vanishes).
<H2>
Converting <A NAME="ps2ttf">PostScript to TrueType</A>
</H2>
<P>
Most cubic splines cannot be represented exactly by a quadratic (or even
by a series of quadratics). The best that can be done is to approximate the
cubic to within some margin of error. Here is a way to do that:
<P>
Given a cubic spline. Look at two points on the spline. Then there is only
one possible quadratic spline between those two points which has the desired
slope at those two points. (the one quadratic has its end points as the end
points of the interval, and its control point is determined by the intersections
of the lines tangent to the cubic at the start and end of the interval).
<P>
<IMG SRC="/assets/img/old/cubic2quad.png" WIDTH="482" HEIGHT="180" ALIGN="Right">I cannot
prove this, but have determined empirically (after being told it worked)
that if a cubic spline -- like the quarter ellipse at right -- is divided
"evenly" into n quadratic splines (here n==3) then the control points will
have the nice property that the on-curve points are exactly mid-way between
control points -- this means that truetype can represent them as interpolated
points. An even division means means that each sub-point is placed where
t=i/n (where 0<i<n).
<P>
FontForge first checks to see if the curve is already a quadratic -- this
might happen if the cubic originally came from a truetype font. If it is
it simply converts the control point.
<P>
Otherwise FontForge start inserting points. It begins by inserting a single
point mid-way on the spline. If this produces a good approximation it stops,
otherwise it tries again with two, three ... additional points.
<P>
On each test it will round the control points to integer values because truetype
output requires this (note that it does not do this to the on-curve points,
they are interpolated between control points and will be ok if the control
points are). Then it checks to see if the resultant quadratics are close
to the original curve.
<P>
FontForge may also break the curve at its points of inflection (because no
quadratic can have one there should be a point there to start a new quadratic)
and apply the above algorithm to the components.
<P>
If FontForge can find no good approximation using the above algorithm it
will fall back to its old method, which is:
<P>
Start from the end of the spline and every so often (ie. within the margin
of error) check to see if the one permissible quadratic approximation actually
matches the cubic closely enough .
<P>
If this approximation works then keep it as part of the result, and continue
the process by advancing our start point along to the cubic spline to the
end of the quadratic we just created.
<P>
(There are some slight complexities introduced because there may not be a
quadratic approximation at a given point (if the tangents happen to be parallel)
or because the approximation happens to be linear, but these are easily dealt
with).
<P>
It may, of course, happen that the "cubic" we are given is actually a quadratic
(if its third degree term is 0), the most likely cause is that the font came
from a truetype source. In that case the control point for the quadratic
is at:
<BLOCKQUOTE>
QP<SUB>1</SUB> = CP<SUB>0</SUB> + 3/2 * (CP<SUB>1</SUB> - CP<SUB>0</SUB>)
</BLOCKQUOTE>
<P>
Other sources I have read on the net suggest checking the cubic spline for
points of inflection (which quadratic splines cannot have) and forcing breaks
there. To my eye this actually makes the result worse, it uses more points
and the approximation does not look as close as it does when ignoring the
points of inflection. So I ignore them.
<H2>
Open Type, another solution
</H2>
<P>
Adobe and Microsoft decided to produce one font format which could hold either
a true type font or a postscript font. This is called Open Type. It is
essentially a superset of TrueType. Any TrueType font is a valid Open Type
font, but Open Type fonts can also contain postscript. Anything that supports
Open Type will not require converting between PostScript and True Type.
<H3>
See Also
</H3>
<UL>
<LI>
<A HREF="pfaeditmath.html">FontForge's math</A>
</UL>
<P>
<P>
<SUP><A NAME="bezier">1 </A></SUP>Bézier splines were developed by
Pierre Bézier (1910-1999).
<P>
<P ALIGN=Center>
-- <A HREF="sfdformat.html">Prev</A> -- <A HREF="overview.html">TOC</A> --
<A HREF="corpchar.html">Next</A> --
</DIV>
</BODY></HTML>