1
%----------------------------------------------------------------------------
2
% ----- File: internals.tex
3
% ----- Author: Rainer Menzner (Rainer.Menzner@web.de)
4
% ----- Date: 2003-03-01
5
% ----- Description: This file is part of the t1lib-documentation.
6
% ----- Copyright: t1lib is copyrighted (c) Rainer Menzner, 1996-2003.
7
% As of version 0.5, t1lib is distributed under the
8
% GNU General Public Library License. The
9
% conditions can be found in the files LICENSE and
10
% LGPL, which should reside in the toplevel
11
% directory of the distribution. Please note that
12
% there are parts of t1lib that are subject to
14
% The parseAFM-package is copyrighted by Adobe Systems
16
% The type1 rasterizer is copyrighted by IBM and the
18
% ----- Warranties: Of course, there's NO WARRANTY OF ANY KIND :-)
19
% ----- Credits: I want to thank IBM and the X11-consortium for making
20
% their rasterizer freely available.
21
% Also thanks to Piet Tutelaers for his ps2pk, from
22
% which I took the rasterizer sources in a format
23
% independent from X11.
24
% Thanks to all people who make free software living!
25
%----------------------------------------------------------------------------
28
\section{Internals (incomplete)}
35
{\Huge\bfseries Note!}\\
36
This section is still very incomplete and some facts are not true
37
anymore. This should be kept in mind. Currently I have no time to
38
write this section. But I try to keep figure \ref{figure:t1data}
39
consistent to the current releases. This may lead to inconsistencies
40
between the text and the figure.
44
In this section, some information on internals of \tonelib\ is given. There is
45
no need for an average user to read this section although having understood
46
what is going on internally might be helpful if problems occur.
48
The basic idea of this section is to describe the data structures and to give
49
information on when they are initialized, allocated and referenced. Figure
50
\ref{figure:t1data} shows an image of the data-structures for the special case that
51
the font with ID 0 has already been loaded and several size-instances have
53
%-- Figure: The data structures of t1lib
56
\includegraphics*[angle=90]{t1_data}
59
\caption{\label{figure:t1data}The internal data structures of \tonelib. The
60
underlying substructures are shown only for the first font
63
As the figure indicates, the complete area may be split into three
64
different sub-areas, thereby pointing out their logical functions.
66
\subsection{Level 0: Global Data}
68
This area contains information needed for the overall organization of the
69
\tonelib. Its contents and its size are thus determined at the time
70
\tonelib\ is initialized. This is done based on the contents of the
71
configuration file and the fontdatabase file. The entries in detail are:
73
\item {\tt Filename-Searchpaths}: This entry essentially does not depend on
74
any other data. It consists of 4 \verb+\0+-terminated strings that are read
75
from the configuration file. They are referenced internally by the global
77
\verb+PFAB_ptr+, \verb+AFM_ptr+, \verb+ENC_ptr+ and \verb+FDB_ptr+
78
respectively. All these are declared as \verb+unsigned char *+. These
79
strings are used by \tonelib\ to locate the respective file types. If no
80
configuration file exists or some path declaration is missing, the
81
corresponding searchpath is set to ``\verb+.+'', causing \tonelib\ to only
82
search the current working directory.
83
\item \verb+no_fonts_ini+: This value is assigned after examining the
84
fontdatabase file. It is meant to store the number of fonts initially
85
declared in the fontdatabase file. In other words, it is assigned the
86
integer number located on the first line of the fontdatabase file.
87
\item \verb+no_fonts+: The number of actually allocated fonts. Initially, this
88
quantity is identical to \verb+no_fonts_ini+. But if one creates a new
89
logical font by calling \verb+T1_CopyFont()+ this counter is incremented to
90
keep track of allocated fonts. \verb+no_fonts+ thus represents most large
91
\verb+FontID+ minus 1 that makes sense to specify to any function of
93
\item \verb+no_fonts_limit+: The number of fonts for which memory is currently
94
allocated. This also is initially set to \verb+no_fonts_ini+ and is
95
automatically enlarged to a multiple of the initial value if a call to
96
\verb+T1_CopyFont()+ requires additional memory for logical fonts (see
98
\item \verb+bitmap_pad+: This variable contains the number of bits to which
99
scanlines of bitmaps and antialiased bitmaps are padded. It is set during
100
initialization, either to a default value or to the value the application
101
specified before starting initialization using
102
\verb+T1_SetBimapPad()+. Allowed values are currently `8', `16' and `32'.
103
\item \verb+endian+: During initialization the hardware is checked for
104
representation of data in memory. If Big Endian is used, \verb+endian+ is
105
set to \verb+1+ and otherwise it is set to \verb+0+. \verb+endian+ is needed
106
at several times when an application or \tonelib\ itself must know the
107
byte order of words and long words.
108
\item \verb+pFontArray+: This a pointer to an array of structures whose type
110
\verb+FONTPRIVATE+ in \tonelib. The contents of these
111
structures will be described below. After \tonelib\ has been
112
initialized, memory is allocated for exactly \verb+no_fonts_ini+
113
structures. This memory pool may be enlarged later if the one wants to make
114
use of logical fonts, for example. The data in these structures initially is
115
not specified. It is written with meaningful values when a font is loaded
116
into memory. The index to access this array-elements is the well known font
117
identification number (\verb+FontID+).
118
\item \verb+pFontFileNameIDArray+: A pointer to a memory area where the
119
font file names corresponding to the \verb+FontID+s are stored. During
120
initialization, \tonelib\ looks for font files with extension \verb+.pfa+
121
and \verb+.pfb+. The basename of the file found is stored in this area and
122
if the font is to be loaded later, its font file name is looked up here.
124
We should now discuss the entries of the structures of type
125
\verb+FONTPRIVATE+. The term \verb+FONTPRIVATE+ indicates that every font
126
needs its own structure area. As mentioned earlier, this area is initialized
127
when the corresponding font is loaded.
129
\item \verb+pAFMData+: A pointer to a memory area where Adobe Font Metric data
130
of the font is stored. The memory area itself is build by the
131
\verb+parse_afm+-package which is supplied by Adobe System and included in
132
\tonelib. This happens while a font is loaded. In case there is no AFM file
133
for the font in question, this pointer is given the value \verb+NULL+.
134
\item \verb+pType1Data+: A pointer to the data area where the Type 1
135
information is stored. The known PostScript Type 1 objects
136
Charstrings-dictionary, Subroutines, Othersubroutines and
137
Fontinfo-dictionary are located here. The memory is filled with data during
138
parsing the font file when the font is loaded.
139
\item \verb+pFontEnc+: A pointer to an optional external encoding
140
vector. During initialization, this pointer is set to \verb+NULL+, thus
141
indicating that by default the font's internal encoding should be used.
142
If a font is reencoded using a previously loaded encoding vector from an
143
encoding file, this pointer simply is assigned the address of a valid
144
encoding array somewhere in memory.
145
\item \verb+vm_base+: The base address of the virtual memory required by the
146
font. Unlike the original rasterizer, which allocated virtual memory in
147
chunks of a fixed size, t1lib uses another principle. Since it is \`a
148
priori not obvious how many virtual memory a font consumes, \tonelib\ tries
149
to load a font repeatedly and increases the amount of virtual memory during
150
every trial. In order not to waste memory, the memory is reallocated to the
151
needed size when the font is completely loaded. Finally, the starting
152
address of the virtual memory is needed when a font is to be unloaded and
153
the memory it consumes is to be given back to system.
154
\item \verb+pFontSizeDeps+: A pointer to the area where the size dependent
155
data is to be stored. This data essentially consists of generated glyphs
156
plus some administrative item (see \ref{sizedependentfontdata}).
157
\item \verb+FontMatrix+: A matrix of four \verb+double+-values specifying the
158
font matrix. If the FontInfo-dictionary of the font file defines a
159
FontMatrix, it is copied to this location. If not, a default matrix is
160
used which does no transformation and scales to $1/1000$~bp.
161
\item \verb+FontTransform+: A matrix that will be concatenated with the
162
FontMatrix to produce the final transformation of the characters. It is this
163
matrix that is modified if a font is to be slanted or extended.
164
\item \verb+slant+: A slant factor for the current font. Note that this
165
value is initially 0, even for italic font. Only artificially slanting a
166
font leads to values different from 0.
167
\item \verb+extend+: The horizontal extension factor for the current font. Its
168
default value is 1 and the font is thus rendered at its natural width.
169
\item \verb+physical+: This is a switch that marks a font either being
170
``physical'' or ``logical''. A physical font by definition is a font for
171
which a Type 1 font file is available and for which thus Level 1
172
(size-independent) data is present (see Fig.\ 5.1). In contrast, the term
173
``logical font'' refers to a structure of type \verb+FONTPRIVATE+ whose
174
entry \verb+pType1Data+ points to Level 1 data of another (physical)
175
font. This \verb+FONTPRIVATE+-structure is created by calling
176
\verb+T1_CopyFont()+ with the identification number of an existing physical
177
font as argument (see \ref{logicalfonts}).
178
\item \verb+refcount+: This counter keeps track on how much logical fonts
179
refer to the physical font that is represented by the current structure of
180
type \verb+FONTPRIVATE+. In this since, \verb+refcount+ is only meaningful for
181
physical fonts. It is necessary to keep track of the reference of logical
182
fonts because if this font would be removed from memory by calling
183
\verb+T1_DeleteFont()+, the Level 1 font data memory area would be given back
184
to the system but the logical fonts referring to that font would still
185
expect to find Type 1 or Font Metric data at this address. By checking
186
\verb+refcount+, \verb+T1_DeleteFont()+ can check for logical fonts referring
187
to the font in question and prevent from removing this font from memory.
189
In structures describing logical fonts, \verb+refcount+ is used to
190
store the information which physical font this logical font is
191
referring to. This information is also needed by
192
\verb+T1_DeleteFont()+ since when removing logical fonts, the
193
reference counter of the corresponding physical font has to be
195
\item \verb+space_position+: This variable stores the encoding index of the
196
``space''-character of the current font. If the space character does not
197
appear in the current font's encoding, \verb+space_position+ is assigned
198
-1. It follows that \verb+space_position+
199
is assigned when (1) a font loaded and (2) every time a
200
font is reencoded. Why is it convenient to store the position of the space
201
character in the encoding vector? The properties of the space character are
202
set apart from the other characters' properties not only by the fact that it
203
does not produce any colored pixels but also by that it may shrink and
204
stretch in \tonelib. As a consequence a space character is treated by simply
205
inserting a horizontal escapement of the width of the space
206
character---corrected by the quantity \verb+space_off+ that a user may
207
specify (see \ref{generatingbitmaps}). This involves always checking every
208
character for being the space character and since the encoding principle is
209
used in \tonelib, every check needs a call to \verb+strcmp()+. This overhead
210
is avoided if the position of space is stored.
212
\subsection{Level 1: Size-Independent Font Data}
213
\label{sizeindependentfontdata}%
214
Size-independent data may be split into three categories as indicated in
215
figure \ref{figure:t1data}. The external encoding is optional and is generated
216
by loading an encoding file as described in \ref{encoding}. It is simply an
217
array of 256 pointers to \verb+unsigned char+ and an ensemble of 256
218
\verb+\0+-terminated strings. Each pointer references one of the 256 strings
219
in order. The strings are the characters' names to be defined in a
220
\tonelib-encoding file.
222
The internal Type 1 data structures hold all data specified in a type font
223
file. I do not want to describe these data structures here, because this could
224
fill a book. Adobe has made the description of the Type 1 font format
225
available to the public.
227
The Adobe Font Metrics area is entirely created by the
228
\verb+parse_afm+-package. Adobe has made this available by means of the file
229
\verb+parseAFM.shar+ which is a shell-archive and included in \tonelib\ in the
230
subdirectory \verb+parse_afm+.
232
\subsection{Level 2: Size-Dependent Font Data}
233
\label{sizedependentfontdata}%
239
\section{Stroked Characters}
240
\label{strokingimplementation}%
241
This section is only meant for the reader interested in details about the
242
algorithm used to create stroked versions from outlines intended to be
243
filled. It can help to understand the code I added to \verb+type1.c+, which
244
may seem a little bit strange.
246
The basic idea to achieve stroked outlines was to map the stroking operation
247
to a simple filling operation as already implemented by the rasterizer. Why
248
did I choose this approach? Well, the actual reason for doing so was that I
249
felt like doing so. One of the pivotal problems in this context turned out to
250
be the computation of a third order Bezier curve, being located {\em in
251
parallel} to a given third order Bezier curve---a problem set which
252
everybody on the net said to be impossible to solve. After some experimenting
253
I had to admit that these people actually were right: It is not possible to
254
solve this problem in general, in particular because tracing a given cubic
255
Bezier spline using a finite pen width might produce delimiting curves which
256
aren't Bezier splines at all. In particular, the angular range and the pen
257
width in relation to the original curve's bend are of importance.
259
However, under some constraints, which usually are fulfilled by adhering to
260
the Adobe design rules for Type 1 Fonts and by choosing reasonable stroke
261
widths, it is possible to approximate these delimiting curves by cubic Bezier
264
\subsection{Approach}
265
Type 1 character outline descriptions consist of mathematically thin defining curves
266
and lines with an associated running direction. By convention, regions left of
267
these defining curves are painted and regions right of these curves are left
268
blank. For each properly defined character, this way, a finite area to be filled
269
results by applying this rule, especially because for filled characters every
270
subpath must be closed. Figure~\ref{figure:stroking1}~\fbox{A} shows the
271
character ``8'' from the ComputerModern Roman font as an example.
274
\fbox{A}\includegraphics[scale=0.5]{t1dump/t1dump_eight}
276
\fbox{B}\includegraphics[scale=0.5]{t1dump/t1dump_o}
278
\hrule\vskip3mm\small
279
\caption{\label{figure:stroking1}\fbox{A} Character ``8'' from font
280
ComputerModern Roman. The arrows indicate the direction of the paths. From
281
the outer subpath it follows that the inner region will be filled (left of the
282
path). From this massive black region, the holes are cut by means of the two
283
inner subpaths (and their direction). \fbox{B} The principle of creating a
284
stroked character by filling a newly created set of subpaths which surround
285
the original path in an appropriate manor.}
287
We find three subpaths which by means of their direction relations yield the
290
When talking about {\em stroking}, we mean tracing a pen of finite width along
291
these subpaths. When doing so, a new finite (more complex) region of ink is
292
built. Actually we can consider this filled region being the result of filling
293
a newly created path that consists of two subpaths surrounding the original
294
path and having appropriate directions. These newly created subpaths are
295
referred as the {\em right path} and the {\em left path}.
296
Figure~\ref{figure:stroking1} \fbox{B} illustrates this idea for the
297
character ``o''. The original path is represented by dashed curves whereas
298
left paths and right paths are shown as solid curves. The respective
299
directions are indicated by arrows.
301
Now, what are the steps required to compute a right path or left path from a
302
given path and given a certain strokewidth? Firstly, for each path segment two
303
{\em parallel paths} the right and the left path, located half the strokewidth
304
right and left of the original path have to be computed. This is shown for the
305
character ``t'' in Figure~\ref{figure:stroking2}, \fbox{A}.
308
\fbox{A}\includegraphics[scale=0.5]{t1dump/t1dump_t_1}
310
\fbox{B}\includegraphics[scale=0.5]{t1dump/t1dump_t_2}
312
\hrule\vskip3mm\small
313
\caption{\label{figure:stroking2}\fbox{A} Character ``t'' from font
314
ComputerModern Roman. The original path is shown in a thick dashed
315
style. Each segment is surrounded by a parallel path to the right hand side
316
and a parallel path to the left hand side.
317
\fbox{B} Required additional connection segments in order to complete the
321
In particular, it turns out that in order to connect two parallel right or
322
left paths of two neighboring original path segments, additional path segments
323
are required. Therefore, in a second step, these parallel path
324
segments---which in general may be disjoint---have to be connected
325
appropriately. These additional path segments are shown in \fbox{B} of the
326
figure. We term these path segments {\em Prolongation Segments}. They
327
are always built as straight lines. It is also obvious, that for convex edges,
328
prolongation actually is what it indicates, and for concave edges, some trick
329
must be applied so that prolongation yields a path that actually {\em
330
shortens} the respective parallel path segments.
332
\subsection{Computation of Parallel Paths}
333
\label{parallelpaths}%
334
For straight lines, the notion of a parallel path in distance $w/2$ immediately
335
becomes evident, but what about Bezier curves? Let us define the parallel of a
336
curve as the infinite set of points, that results from tracing along the
337
curve and for each point of the curve computing the point which in direction
338
orthogonally to the curve's tangent at the respective location is just the
339
distance $w/2$ apart.
341
The {\em parallel curve} resulting from the principle above actually no longer
342
is a third order Bezier curve. But if a few additional constraints hold, it
343
can be approximated quite well by such a third order Bezier curve:
345
\item The curvature should not exceed an angular range of 90 degrees. This
346
condition automatically is fulfilled for Type 1 fonts which adhere to the
347
Adobe recommendations.
348
\item The strokewidth $w$ the curve should be drawn width is small compared to
349
the extension and the curvature of the curve. This principle usually is
350
fulfilled by nature because tracing a character outline path with a very
351
thick pen won't lead to a good representation of the character.
353
In the following, we will describe how to compute a parallel Bezier curve
354
defined by four points $\vec{A}'$, $\vec{B}'$, $\vec{C}'$ and $\vec{D}'$,
355
given an original Bezier curve defined by four points $\vec{A}$, $\vec{B}$,
356
$\vec{C}$ and $\vec{D}$ and a strokewidth $w$. The computation of parallel
357
straight lines results as the special case of only respecting the points
358
$\vec{A}$ and $\vec{D}$ from these considerations.
360
Figure~\ref{figure:stroking3} represents the basis of our discussion.
362
\centerline{\includegraphics[scale=0.7]{t1dump/parallelpath_sk}}
363
\hrule\vskip3mm\small
364
\caption{\label{figure:stroking3}Construction of parallel Bezier path
365
segments. The original curve is shown in dashed style and the light gray
366
area indicates the thick Bezier curve segment that later will result from
367
filling between left and right parallel path. Furthermore, important
368
intermediate points are shown. A detailed discussion is given in the text.}
370
It shows the original mathematically thin Bezier segment defined by the points
371
$\vec{A}$, $\vec{B}$, $\vec{C}$ and $\vec{D}$ in dashed style. The
372
counterpart of $\vec{A}$ in the parallel path follows from simple geometric
373
considerations, as illustrated for the point $\vec{A}'$. It lies half the
374
strokewidth $w$ away from $\vec{A}$ and the direction is determined by the
375
location of point $\vec{B}$. For the two coordinates of $\vec{A}'$ we find
378
A'_x = A_x + \frac{w}{2}\frac{B_y - A_y}{|\vec{B} - \vec{A}|}
383
A'_y = A_x - \frac{w}{2}\frac{B_x - A_x}{|\vec{B} - \vec{A}|}.
385
Corresponding equations can be derived for the point $\vec{D}'$, so that, up to now, we
386
are able to compute parallel straight line segments. It remains to compute two
387
control points, $\vec{B}'$ and $\vec{C}'$, in a way that the resulting Bezier
388
curve appears as parallel to the original curve in the sense defined above.
390
In order to make the path at point $\vec{A}'$ actually parallel to the orginal
391
path at $\vec{A}$, we require $\vec{B}' - \vec{A}'$ to be parallel to $\vec{B}
392
- \vec{A}$. From this we can derive an equation that expresses the fact that
393
$\vec{B}'$ lies somewhere on the straight line that runs through point
394
$\vec{A}'$ and has the direction $\vec{B} - \vec{A}$, i.e.,
397
\vec{B}' = \vec{A}' + \mu_B (\vec{B} - \vec{A}),
402
\vec{C}' = \vec{D}' + \mu_C (\vec{C} - \vec{D})\phantom{,}
404
for point $\vec{C}'$. Here, $\mu_B$ and $\mu_C$ are two positive quantities, whose
405
exact values are still to be determined.
407
In order to compute $\mu_B$ and $\mu_C$, we consider a third point on the
408
curve. Using a well-known algorithm that iteratively approximates a Bezier
409
curve via straight line segments, we can easily determine the coordinates of
410
the point that---in the parameter equation $f(t)$ of a Bezier
411
curve---corresponds to the parameter $t=1/2$. It can be considered as a {\em
412
middle point} of the curve segment. In Figure~\ref{figure:stroking3}, this
413
point is named $\vec{P}_6$. It can be computed by computing some intermediate
417
\vec{P}_1 = \frac{1}{2} ( \vec{A} + \vec{B} )
421
\vec{P}_2 = \frac{1}{2} ( \vec{B} + \vec{C} )
425
\vec{P}_3 = \frac{1}{2} ( \vec{C} + \vec{D} )
429
\vec{P}_4 = \frac{1}{2} ( \vec{P}_1 + \vec{P}_2 )
433
\vec{P}_5 = \frac{1}{2} ( \vec{P}_2 + \vec{P}_3 )
438
\vec{P}_6 = \frac{1}{2} ( \vec{P}_4 + \vec{P}_5 )
439
= \frac{1}{8} ( \vec{A} + 3 \vec{B} + 3 \vec{C} + \vec{D} )
441
Using the same geometrical considerations as in Eqs.~\ref{eq:eq1} and
442
\ref{eq:eq2}, we can now compute a unit vector, $\vec{n}_6$, perpendicular to
443
the curve at $\vec{P}_6$ and obtain
446
n_{6x} = \frac{ P_{5y} - P_{4y} }{\sqrt{(P_{5x}-P_{4x})^2 + (P_{5y}-P_{4y})^2}}
450
n_{6y} = - \frac{ P_{5x} - P_{4x} }{\sqrt{(P_{5x}-P_{4x})^2 + (P_{5y}-P_{4y})^2}}
452
$\vec{P}'_6$ can now be computed as
455
\vec{P}'_6 = \vec{P}_6 + \vec{N}_6,
457
where $\vec{N}_6 = \frac{w}{2} \vec{n}_6$, i.e., the vector orthogonal to the
458
curve at $\vec{P}_6$ with a length of half the strokewidth $w$. As before, we
459
have to require that the slope of the curve $\vec{P}_6$ equals the one at
460
$\vec{P}'_6$, i.e., with respect to Figure~\ref{figure:stroking3} we find
462
\vec{P}'_5 - \vec{P}'_4 & = & \nu \left( \vec{P}_5 - \vec{P}_4 \right) \\
463
\frac{\vec{P}'_2 + \vec{P}'_3}{2} -
464
\frac{\vec{P}'_1 + \vec{P}'_2}{2}
466
\frac{\vec{P}_2 + \vec{P}_3}{2} -
467
\frac{\vec{P}_1 + \vec{P}_2}{2} \right) \\
468
\frac{\vec{C}' + \vec{D}'}{2} -
469
\frac{\vec{A}' + \vec{B}'}{2}
471
\frac{\vec{C} + \vec{D}}{2} -
472
\frac{\vec{A} + \vec{B}}{2} \right)
477
\vec{C}' + \vec{D}' - \vec{A}' - \vec{B}' = \nu \left(
478
\vec{C} + \vec{D} - \vec{A} - \vec{B} \right)\;.
480
We have thus expressed the slope condition at $\vec{P}_6$ in terms of the
481
characteristic points of a Bezier curve and a factor, $\nu$, still to be
482
determined (cf.~Eqs.~\ref{eq:eq3} and \ref{eq:eq4}). On the way to
483
Eq.~\ref{eq:eq14}, we made use of the well-known geometrical relations
484
\hbox{Eqs.~\ref{eq:eq5} -- \ref{eq:eq9}}.
486
Based on the same considerations that led to Eq.~\ref{eq:eq10}, we can write
487
the corresponding equation for the point $\vec{P}'_6$:
490
\vec{P}'_6 = \frac{1}{2} ( \vec{P}'_4 + \vec{P}'_5 )
491
= \frac{1}{8} ( \vec{A}' + 3 \vec{B}' + 3 \vec{C}' + \vec{D}' )
493
Exploiting Eq.~\ref{eq:eq13} and solving for $\vec{C}'$, we can reorganize
497
\vec{C}' = \frac{8 (\vec{N}_6 + \vec{P}_6) - \vec{A}' - \vec{D}'}{3} -
500
From this equation, we are able eliminate $\vec{B}'$ by substituting the
501
transformed slope condition for point $\vec{P}'_6$ (Eq.~\ref{eq:eq14}). We
505
\vec{C}' &=& \frac{8 (\vec{N}_6 + \vec{P}_6) - \vec{A}' - \vec{D}'}{3}
506
+ \left[ \nu \left( \vec{C} + \vec{D} - \vec{A} - \vec{B} \right)
507
- \vec{C}' - \vec{D}' + \vec{A}' \right] \\
509
2\, \vec{C}' &=& \frac{8 (\vec{N}_6 + \vec{P}_6) - \vec{A}' - \vec{D}'}{3}
510
+ \vec{A}' - \vec{D}' +
511
\nu \left( \vec{C} + \vec{D} - \vec{A} - \vec{B}\right) \\
514
\underbrace{\frac{4 (\vec{N}_6 + \vec{P}_6) + \vec{A}' - 2 \vec{D}'}{3}}
515
_{\mbox{$\vec{l}_C$}}
516
+ \frac{\nu}{2} \underbrace{\left( \vec{C} + \vec{D} - \vec{A} -
518
_{\mbox{$\vec{d}_C$}} \,.
520
Here, for the sake of brevity, we introduced a location vector, $\vec{l}_C$,
521
and a direction vector, $\vec{d}_C$, which together with the parameter $\nu$
522
define the point $\vec{C}'$.
524
Considering Eqs.~\ref{eq:eq4} and \ref{eq:eq17}, we finally found two
525
independent relations for $\vec{C}'$, that linearly depend on two quantities,
526
$\mu_C$ and $\frac{\nu}{2}$. Therefore, by substituting the right hand sides
527
of (\ref{eq:eq4}) and (\ref{eq:eq17}), we obtain the following $2 \times
528
2$ system of linear equations:
533
(\vec{C}-\vec{D}) & \vec{d}_C
542
= \left( \vec{l}_C - \vec{D}' \right)
544
Formally, all vectors appearing in this equation are column vectors. The
545
solution of the system can be written as
557
(\vec{C}-\vec{D}) & \vec{d}_C
560
\left( \vec{l}_C - \vec{D}' \right)\, .
562
Once $\vec{C}'$ has been computed, it is easy to compute $\vec{B}'$, by making
563
use of Eq.~\ref{eq:eq16}.
565
A few remarks about the approach described above are appropriate.
567
\item It is also possible to first compute the point $\vec{B}'$ and then use
568
Eq.~\ref{eq:eq16} to compute $\vec{C}'$.
569
\item The numerical stability at the respective end of the curve determines
570
the preference of which point to compute first. A criterion for the
571
numerical stability is the absolute value of determinant of the $2 \times 2$
572
matrix in Eq.~\ref{eq:eq18}.
573
\item This determinant may become zero in which case the curve transforms into
574
a straight line. These cases must be treated extraordinarily.
575
\item There are a number of further exceptional cases, e.g., if point $\vec{C}$
576
equals $\vec{D}$. Then the slope at this end of the curve is not enforced by
578
\item A good solution, that is, a {\em parallel curve}, will only result, if
579
the set of assumptions discussed previously holds. If the resulting curve
580
does not appear {\em parallel} to the original curve, the parallel curve
581
cannot be approximated by a third order Bezier spline.
585
\subsection{Connection of Path Segments and Prolongation}
586
\label{connectingpaths}
587
In order to actually obtain delimiting paths for character outlines, the
588
parallel paths have to be connected to a continuous path. This raises the
589
problem of line joining. When connecting two neighboring parallel path
590
segments, we have to distinguish between two qualitatively different
593
\item Convex Corner\\
594
When tracing along two neighboring parallel path segments, we turn to the
595
left and a convex corner appears. In these cases, we prolongate the end of
596
the first path and the beginning of the second path using straight lines and
597
compute an intersection between these prolongation segments. The resulting
598
lengths of both prolongation segments will be positive.
599
\item Concave Corner\\
600
When tracing along two neighboring parallel path segments, we turn to the
601
right and a concave corner results. In these cases, the two neighboring
602
parallel path segments intersect by nature and actually would have to be
603
trimmed to their intersection point. Trimming on the other hand would make
604
it impossible to feed the resulting curve in the standard format into the
605
rasterizer. We therefore use a trick that saves us computing an intersection
606
and recomputing the Bezier control points. From the ideal end point of the
607
first parallel path we insert a straight prolongation to the connection
608
point of the original path segments and a second straight prolongation
609
segment from there to the starting point of the second parallel path
610
segment. Then, the area left of the path is ensured to be within the extents
611
that finally are to be filled with ink.
613
We will now explain this principle using the example shown in
614
Figure~\ref{figure:stroking4}.
616
\centerline{\includegraphics[scale=1.1]{t1dump/t1dump_B}}
617
\vskip3mm\hrule\vskip3mm\small
618
\caption{\label{figure:stroking4}A small excerpt at the middle right from the
619
character ``B'' of ComputerModern Roman. The ideal mathematical outline of
620
the filled character is shown in thick dashed style. Left and right path of
621
the character's outline representation are shown in medium solid
622
style. Prolongation is indicated by large dashes of medium thickness.}
624
The interesting part is in the middle right. The original path---shown in bold
625
dashed style---steps into the figure in the lower right as the end of a curve
626
segment $p_1$. At the following connection point, the path strongly turns to
627
the right so that a concave corner results and continues with a further curve
628
segment $p_2$. This path is now to be surrounded in a symmetrical manner by
629
one right and one left path. For $p_1$, we find the right path as a parallel
630
curve segment above the original path. It has been computed as described in
631
the previous section. For $p_2$, the right path is a parallel curve segment
632
located in an appropriate distance below $p_2$. The two neighboring right path
633
segments are disjoint because of the concavity of the resulting corner. Hence,
634
rule 2 from above applies in order to connect them using straight prolongation
635
lines, in the figure shown in wide dashes of a medium linewidth: From the end
636
of right path 1, we prolongate to the point where the original segments $p_1$ and
637
$p_2$ join, and from there, a second prolongation to the beginning of right
638
path 2 is inserted. The direction is indicated by arrows. Obviously, even the
639
right path alone produces a closed region in this case, but this does not
642
The left path runs into the direction opposite to the original path. By
643
nature, the curvature at the point under consideration now is convex. Hence,
644
according to rule 1, the neighboring left paths' segments are prolongated to
645
their common intersection point, respecting the ending direction of left
646
path 1 and the starting direction of left path 2.
648
The kind of corner at two neighboring parallel path segments $p_1$ and $p_2$
649
can be computed analytically. Let $\vec{T}_1$ be the tangent vector at the end
650
point of $p_1$ and $\vec{T}_2$ be the tangent vector at the starting point of
651
$p_2$. Assuming that both $\vec{T}_1$ and $\vec{T}_2$ are column vectors, we
652
can use the determinant of the square matrix constructed by these vectors to
653
determine the corner type:
659
\vec{T}_1 & \vec{T}_2
663
If $d<0$, the corner type is concave whereas for $d>0$, the corner type is
664
convex. For the special case $d=0$, the slope at the joining point is
665
continuous, so that effectively $\vec{T}_1$ and $\vec{T}_2$ linearly depend on
666
each other. For those cases, prolongation is not required at all, because if
667
the neighboring segments in the original path join, neighboring segments in the
668
left and right path will do so too.
670
The kind of joining lines described above is known as {\em mitered line
671
joining}. \tonelib\ does not impose a limit on the width of mitered corners,
672
so that the operation \tonelib\ implements is identical to what PostScript
673
does by default, i.e., using a line join type of 0 and an infinite miter
678
%%% TeX-master: "t1lib_doc"
added
removed
libs/t1lib/t1lib-5.1.2/doc/internals.tex
