next up previous contents index
Next: Function Index Up: Stroked Characters Previous: Computation of Parallel Paths   Contents   Index


Connection of Path Segments and Prolongation

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.
  1. 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.
  2. 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.
We will now explain this principle using the example shown in Figure [*].
Figure: 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.
\includegraphics[scale=1.1]{t1dump/t1dump_B}

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{displaymath}
d =
\left\vert
\begin{array}{cc}
\vec{T}_1 & \vec{T}_2
\end{array} \right\vert
\end{displaymath} (20)

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 mitered line joining. t1lib does not impose a limit on the width of mitered corners, so that the operation t1lib implements is identical to what PostScript does by default, i.e., using a line join type of 0 and an infinite miter limit.


next up previous contents index
Next: Function Index Up: Stroked Characters Previous: Computation of Parallel Paths   Contents   Index
2004-10-04