diff options
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.tex | 679 |
1 files changed, 0 insertions, 679 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 deleted file mode 100644 index 9f232dbf598..00000000000 --- a/Build/source/libs/t1lib/t1lib-5.1.2/doc/internals.tex +++ /dev/null @@ -1,679 +0,0 @@ -%---------------------------------------------------------------------------- -% ----- 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: |