summaryrefslogtreecommitdiff
path: root/Build/source/libs/t1lib/t1lib-5.1.2/doc/internals.tex
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/libs/t1lib/t1lib-5.1.2/doc/internals.tex')
-rw-r--r--Build/source/libs/t1lib/t1lib-5.1.2/doc/internals.tex679
1 files changed, 679 insertions, 0 deletions
diff --git a/Build/source/libs/t1lib/t1lib-5.1.2/doc/internals.tex b/Build/source/libs/t1lib/t1lib-5.1.2/doc/internals.tex
new file mode 100644
index 00000000000..9f232dbf598
--- /dev/null
+++ b/Build/source/libs/t1lib/t1lib-5.1.2/doc/internals.tex
@@ -0,0 +1,679 @@
+%----------------------------------------------------------------------------
+% ----- File: internals.tex
+% ----- Author: Rainer Menzner (Rainer.Menzner@web.de)
+% ----- Date: 2003-03-01
+% ----- Description: This file is part of the t1lib-documentation.
+% ----- Copyright: t1lib is copyrighted (c) Rainer Menzner, 1996-2003.
+% As of version 0.5, t1lib is distributed under the
+% GNU General Public Library License. The
+% conditions can be found in the files LICENSE and
+% LGPL, which should reside in the toplevel
+% directory of the distribution. Please note that
+% there are parts of t1lib that are subject to
+% other licenses:
+% The parseAFM-package is copyrighted by Adobe Systems
+% Inc.
+% The type1 rasterizer is copyrighted by IBM and the
+% X11-consortium.
+% ----- Warranties: Of course, there's NO WARRANTY OF ANY KIND :-)
+% ----- Credits: I want to thank IBM and the X11-consortium for making
+% their rasterizer freely available.
+% Also thanks to Piet Tutelaers for his ps2pk, from
+% which I took the rasterizer sources in a format
+% independent from X11.
+% Thanks to all people who make free software living!
+%----------------------------------------------------------------------------
+
+\newpage
+\section{Internals (incomplete)}
+\label{internals}%
+\vskip1cm
+\hrule
+\vskip0.5cm
+\begin{center}
+\sffamily\large
+{\Huge\bfseries Note!}\\
+This section is still very incomplete and some facts are not true
+anymore. This should be kept in mind. Currently I have no time to
+write this section. But I try to keep figure \ref{figure:t1data}
+consistent to the current releases. This may lead to inconsistencies
+between the text and the figure.
+\end{center}
+\hrule
+\vskip1cm
+In this section, some information on internals of \tonelib\ is given. There is
+no need for an average user to read this section although having understood
+what is going on internally might be helpful if problems occur.
+
+The basic idea of this section is to describe the data structures and to give
+information on when they are initialized, allocated and referenced. Figure
+\ref{figure:t1data} shows an image of the data-structures for the special case that
+the font with ID 0 has already been loaded and several size-instances have
+already been created.
+%-- Figure: The data structures of t1lib
+\begin{figure}
+\begin{center}
+\includegraphics*[angle=90]{t1_data}
+\end{center}
+\hrule\vskip3mm\small
+\caption{\label{figure:t1data}The internal data structures of \tonelib. The
+underlying substructures are shown only for the first font
+{\tt FontID=0}.}
+\end{figure}
+As the figure indicates, the complete area may be split into three
+different sub-areas, thereby pointing out their logical functions.
+
+\subsection{Level 0: Global Data}
+\label{globaldata}%
+This area contains information needed for the overall organization of the
+\tonelib. Its contents and its size are thus determined at the time
+\tonelib\ is initialized. This is done based on the contents of the
+configuration file and the fontdatabase file. The entries in detail are:
+\begin{itemize}
+\item {\tt Filename-Searchpaths}: This entry essentially does not depend on
+ any other data. It consists of 4 \verb+\0+-terminated strings that are read
+ from the configuration file. They are referenced internally by the global
+ symbols
+ \verb+PFAB_ptr+, \verb+AFM_ptr+, \verb+ENC_ptr+ and \verb+FDB_ptr+
+ respectively. All these are declared as \verb+unsigned char *+. These
+ strings are used by \tonelib\ to locate the respective file types. If no
+ configuration file exists or some path declaration is missing, the
+ corresponding searchpath is set to ``\verb+.+'', causing \tonelib\ to only
+ search the current working directory.
+\item \verb+no_fonts_ini+: This value is assigned after examining the
+ fontdatabase file. It is meant to store the number of fonts initially
+ declared in the fontdatabase file. In other words, it is assigned the
+ integer number located on the first line of the fontdatabase file.
+\item \verb+no_fonts+: The number of actually allocated fonts. Initially, this
+ quantity is identical to \verb+no_fonts_ini+. But if one creates a new
+ logical font by calling \verb+T1_CopyFont()+ this counter is incremented to
+ keep track of allocated fonts. \verb+no_fonts+ thus represents most large
+ \verb+FontID+ minus 1 that makes sense to specify to any function of
+ \tonelib.
+\item \verb+no_fonts_limit+: The number of fonts for which memory is currently
+ allocated. This also is initially set to \verb+no_fonts_ini+ and is
+ automatically enlarged to a multiple of the initial value if a call to
+ \verb+T1_CopyFont()+ requires additional memory for logical fonts (see
+ \ref{logicalfonts}).
+\item \verb+bitmap_pad+: This variable contains the number of bits to which
+ scanlines of bitmaps and antialiased bitmaps are padded. It is set during
+ initialization, either to a default value or to the value the application
+ specified before starting initialization using
+ \verb+T1_SetBimapPad()+. Allowed values are currently `8', `16' and `32'.
+\item \verb+endian+: During initialization the hardware is checked for
+ representation of data in memory. If Big Endian is used, \verb+endian+ is
+ set to \verb+1+ and otherwise it is set to \verb+0+. \verb+endian+ is needed
+ at several times when an application or \tonelib\ itself must know the
+ byte order of words and long words.
+\item \verb+pFontArray+: This a pointer to an array of structures whose type
+ is referred to as \\
+ \verb+FONTPRIVATE+ in \tonelib. The contents of these
+ structures will be described below. After \tonelib\ has been
+ initialized, memory is allocated for exactly \verb+no_fonts_ini+
+ structures. This memory pool may be enlarged later if the one wants to make
+ use of logical fonts, for example. The data in these structures initially is
+ not specified. It is written with meaningful values when a font is loaded
+ into memory. The index to access this array-elements is the well known font
+ identification number (\verb+FontID+).
+\item \verb+pFontFileNameIDArray+: A pointer to a memory area where the
+ font file names corresponding to the \verb+FontID+s are stored. During
+ initialization, \tonelib\ looks for font files with extension \verb+.pfa+
+ and \verb+.pfb+. The basename of the file found is stored in this area and
+ if the font is to be loaded later, its font file name is looked up here.
+\end{itemize}
+We should now discuss the entries of the structures of type
+\verb+FONTPRIVATE+. The term \verb+FONTPRIVATE+ indicates that every font
+needs its own structure area. As mentioned earlier, this area is initialized
+when the corresponding font is loaded.
+\begin{itemize}
+\item \verb+pAFMData+: A pointer to a memory area where Adobe Font Metric data
+ of the font is stored. The memory area itself is build by the
+ \verb+parse_afm+-package which is supplied by Adobe System and included in
+ \tonelib. This happens while a font is loaded. In case there is no AFM file
+ for the font in question, this pointer is given the value \verb+NULL+.
+\item \verb+pType1Data+: A pointer to the data area where the Type 1
+ information is stored. The known PostScript Type 1 objects
+ Charstrings-dictionary, Subroutines, Othersubroutines and
+ Fontinfo-dictionary are located here. The memory is filled with data during
+ parsing the font file when the font is loaded.
+\item \verb+pFontEnc+: A pointer to an optional external encoding
+ vector. During initialization, this pointer is set to \verb+NULL+, thus
+ indicating that by default the font's internal encoding should be used.
+ If a font is reencoded using a previously loaded encoding vector from an
+ encoding file, this pointer simply is assigned the address of a valid
+ encoding array somewhere in memory.
+\item \verb+vm_base+: The base address of the virtual memory required by the
+ font. Unlike the original rasterizer, which allocated virtual memory in
+ chunks of a fixed size, t1lib uses another principle. Since it is \`a
+ priori not obvious how many virtual memory a font consumes, \tonelib\ tries
+ to load a font repeatedly and increases the amount of virtual memory during
+ every trial. In order not to waste memory, the memory is reallocated to the
+ needed size when the font is completely loaded. Finally, the starting
+ address of the virtual memory is needed when a font is to be unloaded and
+ the memory it consumes is to be given back to system.
+\item \verb+pFontSizeDeps+: A pointer to the area where the size dependent
+ data is to be stored. This data essentially consists of generated glyphs
+ plus some administrative item (see \ref{sizedependentfontdata}).
+\item \verb+FontMatrix+: A matrix of four \verb+double+-values specifying the
+ font matrix. If the FontInfo-dictionary of the font file defines a
+ FontMatrix, it is copied to this location. If not, a default matrix is
+ used which does no transformation and scales to $1/1000$~bp.
+\item \verb+FontTransform+: A matrix that will be concatenated with the
+ FontMatrix to produce the final transformation of the characters. It is this
+ matrix that is modified if a font is to be slanted or extended.
+\item \verb+slant+: A slant factor for the current font. Note that this
+ value is initially 0, even for italic font. Only artificially slanting a
+ font leads to values different from 0.
+\item \verb+extend+: The horizontal extension factor for the current font. Its
+ default value is 1 and the font is thus rendered at its natural width.
+\item \verb+physical+: This is a switch that marks a font either being
+ ``physical'' or ``logical''. A physical font by definition is a font for
+ which a Type 1 font file is available and for which thus Level 1
+ (size-independent) data is present (see Fig.\ 5.1). In contrast, the term
+ ``logical font'' refers to a structure of type \verb+FONTPRIVATE+ whose
+ entry \verb+pType1Data+ points to Level 1 data of another (physical)
+ font. This \verb+FONTPRIVATE+-structure is created by calling
+ \verb+T1_CopyFont()+ with the identification number of an existing physical
+ font as argument (see \ref{logicalfonts}).
+\item \verb+refcount+: This counter keeps track on how much logical fonts
+ refer to the physical font that is represented by the current structure of
+ type \verb+FONTPRIVATE+. In this since, \verb+refcount+ is only meaningful for
+ physical fonts. It is necessary to keep track of the reference of logical
+ fonts because if this font would be removed from memory by calling
+ \verb+T1_DeleteFont()+, the Level 1 font data memory area would be given back
+ to the system but the logical fonts referring to that font would still
+ expect to find Type 1 or Font Metric data at this address. By checking
+ \verb+refcount+, \verb+T1_DeleteFont()+ can check for logical fonts referring
+ to the font in question and prevent from removing this font from memory.
+
+ In structures describing logical fonts, \verb+refcount+ is used to
+ store the information which physical font this logical font is
+ referring to. This information is also needed by
+ \verb+T1_DeleteFont()+ since when removing logical fonts, the
+ reference counter of the corresponding physical font has to be
+ decremented.
+\item \verb+space_position+: This variable stores the encoding index of the
+ ``space''-character of the current font. If the space character does not
+ appear in the current font's encoding, \verb+space_position+ is assigned
+ -1. It follows that \verb+space_position+
+ is assigned when (1) a font loaded and (2) every time a
+ font is reencoded. Why is it convenient to store the position of the space
+ character in the encoding vector? The properties of the space character are
+ set apart from the other characters' properties not only by the fact that it
+ does not produce any colored pixels but also by that it may shrink and
+ stretch in \tonelib. As a consequence a space character is treated by simply
+ inserting a horizontal escapement of the width of the space
+ character---corrected by the quantity \verb+space_off+ that a user may
+ specify (see \ref{generatingbitmaps}). This involves always checking every
+ character for being the space character and since the encoding principle is
+ used in \tonelib, every check needs a call to \verb+strcmp()+. This overhead
+ is avoided if the position of space is stored.
+\end{itemize}
+\subsection{Level 1: Size-Independent Font Data}
+\label{sizeindependentfontdata}%
+Size-independent data may be split into three categories as indicated in
+figure \ref{figure:t1data}. The external encoding is optional and is generated
+by loading an encoding file as described in \ref{encoding}. It is simply an
+array of 256 pointers to \verb+unsigned char+ and an ensemble of 256
+\verb+\0+-terminated strings. Each pointer references one of the 256 strings
+in order. The strings are the characters' names to be defined in a
+\tonelib-encoding file.
+
+The internal Type 1 data structures hold all data specified in a type font
+file. I do not want to describe these data structures here, because this could
+fill a book. Adobe has made the description of the Type 1 font format
+available to the public.
+
+The Adobe Font Metrics area is entirely created by the
+\verb+parse_afm+-package. Adobe has made this available by means of the file
+\verb+parseAFM.shar+ which is a shell-archive and included in \tonelib\ in the
+subdirectory \verb+parse_afm+.
+
+\subsection{Level 2: Size-Dependent Font Data}
+\label{sizedependentfontdata}%
+
+$\ldots$
+
+\newpage
+
+\section{Stroked Characters}
+\label{strokingimplementation}%
+This section is only meant for the reader interested in details about the
+algorithm used to create stroked versions from outlines intended to be
+filled. It can help to understand the code I added to \verb+type1.c+, which
+may seem a little bit strange.
+
+The basic idea to achieve stroked outlines was to map the stroking operation
+to a simple filling operation as already implemented by the rasterizer. Why
+did I choose this approach? Well, the actual reason for doing so was that I
+felt like doing so. One of the pivotal problems in this context turned out to
+be the computation of a third order Bezier curve, being located {\em in
+ parallel} to a given third order Bezier curve---a problem set which
+everybody on the net said to be impossible to solve. After some experimenting
+I had to admit that these people actually were right: It is not possible to
+solve this problem in general, in particular because tracing a given cubic
+Bezier spline using a finite pen width might produce delimiting curves which
+aren't Bezier splines at all. In particular, the angular range and the pen
+width in relation to the original curve's bend are of importance.
+
+However, under some constraints, which usually are fulfilled by adhering to
+the Adobe design rules for Type 1 Fonts and by choosing reasonable stroke
+widths, it is possible to approximate these delimiting curves by cubic Bezier
+splines.
+
+\subsection{Approach}
+Type 1 character outline descriptions consist of mathematically thin defining curves
+and lines with an associated running direction. By convention, regions left of
+these defining curves are painted and regions right of these curves are left
+blank. For each properly defined character, this way, a finite area to be filled
+results by applying this rule, especially because for filled characters every
+subpath must be closed. Figure~\ref{figure:stroking1}~\fbox{A} shows the
+character ``8'' from the ComputerModern Roman font as an example.
+\begin{figure}[t]
+\hfill
+\fbox{A}\includegraphics[scale=0.5]{t1dump/t1dump_eight}
+\hfill
+\fbox{B}\includegraphics[scale=0.5]{t1dump/t1dump_o}
+\hfill\break
+\hrule\vskip3mm\small
+\caption{\label{figure:stroking1}\fbox{A} Character ``8'' from font
+ ComputerModern Roman. The arrows indicate the direction of the paths. From
+ the outer subpath it follows that the inner region will be filled (left of the
+ path). From this massive black region, the holes are cut by means of the two
+ inner subpaths (and their direction). \fbox{B} The principle of creating a
+ stroked character by filling a newly created set of subpaths which surround
+ the original path in an appropriate manor.}
+\end{figure}
+We find three subpaths which by means of their direction relations yield the
+filled character.
+
+When talking about {\em stroking}, we mean tracing a pen of finite width along
+these subpaths. When doing so, a new finite (more complex) region of ink is
+built. Actually we can consider this filled region being the result of filling
+a newly created path that consists of two subpaths surrounding the original
+path and having appropriate directions. These newly created subpaths are
+referred as the {\em right path} and the {\em left path}.
+Figure~\ref{figure:stroking1} \fbox{B} illustrates this idea for the
+character ``o''. The original path is represented by dashed curves whereas
+left paths and right paths are shown as solid curves. The respective
+directions are indicated by arrows.
+
+Now, what are the steps required to compute a right path or left path from a
+given path and given a certain strokewidth? Firstly, for each path segment two
+{\em parallel paths} the right and the left path, located half the strokewidth
+right and left of the original path have to be computed. This is shown for the
+character ``t'' in Figure~\ref{figure:stroking2}, \fbox{A}.
+\begin{figure}[t]
+\hfill
+\fbox{A}\includegraphics[scale=0.5]{t1dump/t1dump_t_1}
+\hfill
+\fbox{B}\includegraphics[scale=0.5]{t1dump/t1dump_t_2}
+\hfill\break
+\hrule\vskip3mm\small
+\caption{\label{figure:stroking2}\fbox{A} Character ``t'' from font
+ ComputerModern Roman. The original path is shown in a thick dashed
+ style. Each segment is surrounded by a parallel path to the right hand side
+ and a parallel path to the left hand side.
+ \fbox{B} Required additional connection segments in order to complete the
+ outline path.}
+\end{figure}
+
+In particular, it turns out that in order to connect two parallel right or
+left paths of two neighboring original path segments, additional path segments
+are required. Therefore, in a second step, these parallel path
+segments---which in general may be disjoint---have to be connected
+appropriately. These additional path segments are shown in \fbox{B} of the
+figure. We term these path segments {\em Prolongation Segments}. They
+are always built as straight lines. It is also obvious, that for convex edges,
+prolongation actually is what it indicates, and for concave edges, some trick
+must be applied so that prolongation yields a path that actually {\em
+ shortens} the respective parallel path segments.
+
+\subsection{Computation of Parallel Paths}
+\label{parallelpaths}%
+For straight lines, the notion of a parallel path in distance $w/2$ immediately
+becomes evident, but what about Bezier curves? Let us define the parallel of a
+curve as the infinite set of points, that results from tracing along the
+curve and for each point of the curve computing the point which in direction
+orthogonally to the curve's tangent at the respective location is just the
+distance $w/2$ apart.
+
+The {\em parallel curve} resulting from the principle above actually no longer
+is a third order Bezier curve. But if a few additional constraints hold, it
+can be approximated quite well by such a third order Bezier curve:
+\begin{itemize}
+\item The curvature should not exceed an angular range of 90 degrees. This
+ condition automatically is fulfilled for Type 1 fonts which adhere to the
+ Adobe recommendations.
+\item The strokewidth $w$ the curve should be drawn width is small compared to
+ the extension and the curvature of the curve. This principle usually is
+ fulfilled by nature because tracing a character outline path with a very
+ thick pen won't lead to a good representation of the character.
+\end{itemize}
+In the following, we will describe how to compute a parallel Bezier curve
+defined by four points $\vec{A}'$, $\vec{B}'$, $\vec{C}'$ and $\vec{D}'$,
+given an original Bezier curve defined by four points $\vec{A}$, $\vec{B}$,
+$\vec{C}$ and $\vec{D}$ and a strokewidth $w$. The computation of parallel
+straight lines results as the special case of only respecting the points
+$\vec{A}$ and $\vec{D}$ from these considerations.
+
+Figure~\ref{figure:stroking3} represents the basis of our discussion.
+\begin{figure}[t]
+\centerline{\includegraphics[scale=0.7]{t1dump/parallelpath_sk}}
+\hrule\vskip3mm\small
+\caption{\label{figure:stroking3}Construction of parallel Bezier path
+ segments. The original curve is shown in dashed style and the light gray
+ area indicates the thick Bezier curve segment that later will result from
+ filling between left and right parallel path. Furthermore, important
+ intermediate points are shown. A detailed discussion is given in the text.}
+\end{figure}
+It shows the original mathematically thin Bezier segment defined by the points
+$\vec{A}$, $\vec{B}$, $\vec{C}$ and $\vec{D}$ in dashed style. The
+counterpart of $\vec{A}$ in the parallel path follows from simple geometric
+considerations, as illustrated for the point $\vec{A}'$. It lies half the
+strokewidth $w$ away from $\vec{A}$ and the direction is determined by the
+location of point $\vec{B}$. For the two coordinates of $\vec{A}'$ we find
+\begin{equation}
+ \label{eq:eq1}
+ A'_x = A_x + \frac{w}{2}\frac{B_y - A_y}{|\vec{B} - \vec{A}|}
+\end{equation}
+and
+\begin{equation}
+ \label{eq:eq2}
+ A'_y = A_x - \frac{w}{2}\frac{B_x - A_x}{|\vec{B} - \vec{A}|}.
+\end{equation}
+Corresponding equations can be derived for the point $\vec{D}'$, so that, up to now, we
+are able to compute parallel straight line segments. It remains to compute two
+control points, $\vec{B}'$ and $\vec{C}'$, in a way that the resulting Bezier
+curve appears as parallel to the original curve in the sense defined above.
+
+In order to make the path at point $\vec{A}'$ actually parallel to the orginal
+path at $\vec{A}$, we require $\vec{B}' - \vec{A}'$ to be parallel to $\vec{B}
+- \vec{A}$. From this we can derive an equation that expresses the fact that
+$\vec{B}'$ lies somewhere on the straight line that runs through point
+$\vec{A}'$ and has the direction $\vec{B} - \vec{A}$, i.e.,
+\begin{equation}
+ \label{eq:eq3}
+ \vec{B}' = \vec{A}' + \mu_B (\vec{B} - \vec{A}),
+\end{equation}
+and correspondingly
+\begin{equation}
+ \label{eq:eq4}
+ \vec{C}' = \vec{D}' + \mu_C (\vec{C} - \vec{D})\phantom{,}
+\end{equation}
+for point $\vec{C}'$. Here, $\mu_B$ and $\mu_C$ are two positive quantities, whose
+exact values are still to be determined.
+
+In order to compute $\mu_B$ and $\mu_C$, we consider a third point on the
+curve. Using a well-known algorithm that iteratively approximates a Bezier
+curve via straight line segments, we can easily determine the coordinates of
+the point that---in the parameter equation $f(t)$ of a Bezier
+curve---corresponds to the parameter $t=1/2$. It can be considered as a {\em
+ middle point} of the curve segment. In Figure~\ref{figure:stroking3}, this
+point is named $\vec{P}_6$. It can be computed by computing some intermediate
+points:
+\begin{equation}
+ \label{eq:eq5}
+ \vec{P}_1 = \frac{1}{2} ( \vec{A} + \vec{B} )
+\end{equation}
+\begin{equation}
+ \label{eq:eq6}
+ \vec{P}_2 = \frac{1}{2} ( \vec{B} + \vec{C} )
+\end{equation}
+\begin{equation}
+ \label{eq:eq7}
+ \vec{P}_3 = \frac{1}{2} ( \vec{C} + \vec{D} )
+\end{equation}
+\begin{equation}
+ \label{eq:eq8}
+ \vec{P}_4 = \frac{1}{2} ( \vec{P}_1 + \vec{P}_2 )
+\end{equation}
+\begin{equation}
+ \label{eq:eq9}
+ \vec{P}_5 = \frac{1}{2} ( \vec{P}_2 + \vec{P}_3 )
+\end{equation}
+and finally
+\begin{equation}
+ \label{eq:eq10}
+ \vec{P}_6 = \frac{1}{2} ( \vec{P}_4 + \vec{P}_5 )
+ = \frac{1}{8} ( \vec{A} + 3 \vec{B} + 3 \vec{C} + \vec{D} )
+\end{equation}
+Using the same geometrical considerations as in Eqs.~\ref{eq:eq1} and
+\ref{eq:eq2}, we can now compute a unit vector, $\vec{n}_6$, perpendicular to
+the curve at $\vec{P}_6$ and obtain
+\begin{equation}
+ \label{eq:eq11}
+ n_{6x} = \frac{ P_{5y} - P_{4y} }{\sqrt{(P_{5x}-P_{4x})^2 + (P_{5y}-P_{4y})^2}}
+\end{equation}
+\begin{equation}
+ \label{eq:eq12}
+ n_{6y} = - \frac{ P_{5x} - P_{4x} }{\sqrt{(P_{5x}-P_{4x})^2 + (P_{5y}-P_{4y})^2}}
+\end{equation}
+$\vec{P}'_6$ can now be computed as
+\begin{equation}
+ \label{eq:eq13}
+ \vec{P}'_6 = \vec{P}_6 + \vec{N}_6,
+\end{equation}
+where $\vec{N}_6 = \frac{w}{2} \vec{n}_6$, i.e., the vector orthogonal to the
+curve at $\vec{P}_6$ with a length of half the strokewidth $w$. As before, we
+have to require that the slope of the curve $\vec{P}_6$ equals the one at
+$\vec{P}'_6$, i.e., with respect to Figure~\ref{figure:stroking3} we find
+\begin{eqnarray*}
+ \vec{P}'_5 - \vec{P}'_4 & = & \nu \left( \vec{P}_5 - \vec{P}_4 \right) \\
+ \frac{\vec{P}'_2 + \vec{P}'_3}{2} -
+ \frac{\vec{P}'_1 + \vec{P}'_2}{2}
+ & = & \nu \left(
+ \frac{\vec{P}_2 + \vec{P}_3}{2} -
+ \frac{\vec{P}_1 + \vec{P}_2}{2} \right) \\
+ \frac{\vec{C}' + \vec{D}'}{2} -
+ \frac{\vec{A}' + \vec{B}'}{2}
+ & = & \nu \left(
+ \frac{\vec{C} + \vec{D}}{2} -
+ \frac{\vec{A} + \vec{B}}{2} \right)
+\end{eqnarray*}
+and hence finally
+\begin{equation}
+ \label{eq:eq14}
+ \vec{C}' + \vec{D}' - \vec{A}' - \vec{B}' = \nu \left(
+ \vec{C} + \vec{D} - \vec{A} - \vec{B} \right)\;.
+\end{equation}
+We have thus expressed the slope condition at $\vec{P}_6$ in terms of the
+characteristic points of a Bezier curve and a factor, $\nu$, still to be
+determined (cf.~Eqs.~\ref{eq:eq3} and \ref{eq:eq4}). On the way to
+Eq.~\ref{eq:eq14}, we made use of the well-known geometrical relations
+\hbox{Eqs.~\ref{eq:eq5} -- \ref{eq:eq9}}.
+
+Based on the same considerations that led to Eq.~\ref{eq:eq10}, we can write
+the corresponding equation for the point $\vec{P}'_6$:
+\begin{equation}
+ \label{eq:eq15}
+ \vec{P}'_6 = \frac{1}{2} ( \vec{P}'_4 + \vec{P}'_5 )
+ = \frac{1}{8} ( \vec{A}' + 3 \vec{B}' + 3 \vec{C}' + \vec{D}' )
+\end{equation}
+Exploiting Eq.~\ref{eq:eq13} and solving for $\vec{C}'$, we can reorganize
+Eq.~\ref{eq:eq15}:
+\begin{equation}
+ \label{eq:eq16}
+ \vec{C}' = \frac{8 (\vec{N}_6 + \vec{P}_6) - \vec{A}' - \vec{D}'}{3} -
+ \vec{B}'
+\end{equation}
+From this equation, we are able eliminate $\vec{B}'$ by substituting the
+transformed slope condition for point $\vec{P}'_6$ (Eq.~\ref{eq:eq14}). We
+obtain
+\begin{eqnarray}
+ \nonumber
+ \vec{C}' &=& \frac{8 (\vec{N}_6 + \vec{P}_6) - \vec{A}' - \vec{D}'}{3}
+ + \left[ \nu \left( \vec{C} + \vec{D} - \vec{A} - \vec{B} \right)
+ - \vec{C}' - \vec{D}' + \vec{A}' \right] \\
+ \nonumber
+ 2\, \vec{C}' &=& \frac{8 (\vec{N}_6 + \vec{P}_6) - \vec{A}' - \vec{D}'}{3}
+ + \vec{A}' - \vec{D}' +
+ \nu \left( \vec{C} + \vec{D} - \vec{A} - \vec{B}\right) \\
+ \label{eq:eq17}
+ \vec{C}' &=&
+ \underbrace{\frac{4 (\vec{N}_6 + \vec{P}_6) + \vec{A}' - 2 \vec{D}'}{3}}
+ _{\mbox{$\vec{l}_C$}}
+ + \frac{\nu}{2} \underbrace{\left( \vec{C} + \vec{D} - \vec{A} -
+ \vec{B}\right)}
+ _{\mbox{$\vec{d}_C$}} \,.
+\end{eqnarray}
+Here, for the sake of brevity, we introduced a location vector, $\vec{l}_C$,
+and a direction vector, $\vec{d}_C$, which together with the parameter $\nu$
+define the point $\vec{C}'$.
+
+Considering Eqs.~\ref{eq:eq4} and \ref{eq:eq17}, we finally found two
+independent relations for $\vec{C}'$, that linearly depend on two quantities,
+$\mu_C$ and $\frac{\nu}{2}$. Therefore, by substituting the right hand sides
+of (\ref{eq:eq4}) and (\ref{eq:eq17}), we obtain the following $2 \times
+2$ system of linear equations:
+\begin{equation}
+ \label{eq:eq18}
+ \left[
+ \begin{array}{cc}
+ (\vec{C}-\vec{D}) & \vec{d}_C
+ \end{array}
+ \right]
+ \left(
+ \begin{array}{cc}
+ \mu_C \\
+ \nu/2
+ \end{array}
+ \right)
+ = \left( \vec{l}_C - \vec{D}' \right)
+\end{equation}
+Formally, all vectors appearing in this equation are column vectors. The
+solution of the system can be written as
+\begin{equation}
+ \label{eq:eq19}
+ \left(
+ \begin{array}{cc}
+ \mu_C \\
+ \nu/2
+ \end{array}
+ \right)
+ =
+ \left[
+ \begin{array}{cc}
+ (\vec{C}-\vec{D}) & \vec{d}_C
+ \end{array}
+ \right]^{-1}
+ \left( \vec{l}_C - \vec{D}' \right)\, .
+\end{equation}
+Once $\vec{C}'$ has been computed, it is easy to compute $\vec{B}'$, by making
+use of Eq.~\ref{eq:eq16}.
+
+A few remarks about the approach described above are appropriate.
+\begin{itemize}
+\item It is also possible to first compute the point $\vec{B}'$ and then use
+ Eq.~\ref{eq:eq16} to compute $\vec{C}'$.
+\item The numerical stability at the respective end of the curve determines
+ the preference of which point to compute first. A criterion for the
+ numerical stability is the absolute value of determinant of the $2 \times 2$
+ matrix in Eq.~\ref{eq:eq18}.
+\item This determinant may become zero in which case the curve transforms into
+ a straight line. These cases must be treated extraordinarily.
+\item There are a number of further exceptional cases, e.g., if point $\vec{C}$
+ equals $\vec{D}$. Then the slope at this end of the curve is not enforced by
+ point $\vec{C}$.
+\item A good solution, that is, a {\em parallel curve}, will only result, if
+ the set of assumptions discussed previously holds. If the resulting curve
+ does not appear {\em parallel} to the original curve, the parallel curve
+ cannot be approximated by a third order Bezier spline.
+\end{itemize}
+
+
+\subsection{Connection of Path Segments and Prolongation}
+\label{connectingpaths}
+In order to actually obtain delimiting paths for character outlines, the
+parallel paths have to be connected to a continuous path. This raises the
+problem of line joining. When connecting two neighboring parallel path
+segments, we have to distinguish between two qualitatively different
+situations.
+\begin{enumerate}
+\item Convex Corner\\
+ When tracing along two neighboring parallel path segments, we turn to the
+ left and a convex corner appears. In these cases, we prolongate the end of
+ the first path and the beginning of the second path using straight lines and
+ compute an intersection between these prolongation segments. The resulting
+ lengths of both prolongation segments will be positive.
+\item Concave Corner\\
+ When tracing along two neighboring parallel path segments, we turn to the
+ right and a concave corner results. In these cases, the two neighboring
+ parallel path segments intersect by nature and actually would have to be
+ trimmed to their intersection point. Trimming on the other hand would make
+ it impossible to feed the resulting curve in the standard format into the
+ rasterizer. We therefore use a trick that saves us computing an intersection
+ and recomputing the Bezier control points. From the ideal end point of the
+ first parallel path we insert a straight prolongation to the connection
+ point of the original path segments and a second straight prolongation
+ segment from there to the starting point of the second parallel path
+ segment. Then, the area left of the path is ensured to be within the extents
+ that finally are to be filled with ink.
+\end{enumerate}
+We will now explain this principle using the example shown in
+Figure~\ref{figure:stroking4}.
+\begin{figure}[t]
+\centerline{\includegraphics[scale=1.1]{t1dump/t1dump_B}}
+\vskip3mm\hrule\vskip3mm\small
+\caption{\label{figure:stroking4}A small excerpt at the middle right from the
+ character ``B'' of ComputerModern Roman. The ideal mathematical outline of
+ the filled character is shown in thick dashed style. Left and right path of
+ the character's outline representation are shown in medium solid
+ style. Prolongation is indicated by large dashes of medium thickness.}
+\end{figure}
+The interesting part is in the middle right. The original path---shown in bold
+dashed style---steps into the figure in the lower right as the end of a curve
+segment $p_1$. At the following connection point, the path strongly turns to
+the right so that a concave corner results and continues with a further curve
+segment $p_2$. This path is now to be surrounded in a symmetrical manner by
+one right and one left path. For $p_1$, we find the right path as a parallel
+curve segment above the original path. It has been computed as described in
+the previous section. For $p_2$, the right path is a parallel curve segment
+located in an appropriate distance below $p_2$. The two neighboring right path
+segments are disjoint because of the concavity of the resulting corner. Hence,
+rule 2 from above applies in order to connect them using straight prolongation
+lines, in the figure shown in wide dashes of a medium linewidth: From the end
+of right path 1, we prolongate to the point where the original segments $p_1$ and
+$p_2$ join, and from there, a second prolongation to the beginning of right
+path 2 is inserted. The direction is indicated by arrows. Obviously, even the
+right path alone produces a closed region in this case, but this does not
+cause problems here.
+
+The left path runs into the direction opposite to the original path. By
+nature, the curvature at the point under consideration now is convex. Hence,
+according to rule 1, the neighboring left paths' segments are prolongated to
+their common intersection point, respecting the ending direction of left
+path 1 and the starting direction of left path 2.
+
+The kind of corner at two neighboring parallel path segments $p_1$ and $p_2$
+can be computed analytically. Let $\vec{T}_1$ be the tangent vector at the end
+point of $p_1$ and $\vec{T}_2$ be the tangent vector at the starting point of
+$p_2$. Assuming that both $\vec{T}_1$ and $\vec{T}_2$ are column vectors, we
+can use the determinant of the square matrix constructed by these vectors to
+determine the corner type:
+\begin{equation}
+ \label{eq:eq20}
+ d =
+ \left|
+ \begin{array}{cc}
+ \vec{T}_1 & \vec{T}_2
+ \end{array}
+ \right|
+\end{equation}
+If $d<0$, the corner type is concave whereas for $d>0$, the corner type is
+convex. For the special case $d=0$, the slope at the joining point is
+continuous, so that effectively $\vec{T}_1$ and $\vec{T}_2$ linearly depend on
+each other. For those cases, prolongation is not required at all, because if
+the neighboring segments in the original path join, neighboring segments in the
+left and right path will do so too.
+
+The kind of joining lines described above is known as {\em mitered line
+ joining}. \tonelib\ does not impose a limit on the width of mitered corners,
+so that the operation \tonelib\ implements is identical to what PostScript
+does by default, i.e., using a line join type of 0 and an infinite miter
+limit.
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: "t1lib_doc"
+%%% End: