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