next up previous contents index
Next: Connection of Path Segments Up: Stroked Characters Previous: Approach   Contents   Index


Computation of Parallel Paths

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

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 . 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 [*] represents the basis of our discussion.

Figure: 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.
\includegraphics[scale=0.7]{t1dump/parallelpath_sk}

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 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{displaymath}
A'_x = A_x + \frac{w}{2}\frac{B_y - A_y}{\vert\vec{B} - \vec{A}\vert}
\end{displaymath} (1)

and
\begin{displaymath}
A'_y = A_x - \frac{w}{2}\frac{B_x - A_x}{\vert\vec{B} - \vec{A}\vert}.
\end{displaymath} (2)

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{displaymath}
\vec{B}' = \vec{A}' + \mu_B (\vec{B} - \vec{A}),
\end{displaymath} (3)

and correspondingly
\begin{displaymath}
\vec{C}' = \vec{D}' + \mu_C (\vec{C} - \vec{D})\phantom{,}
\end{displaymath} (4)

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 middle point of the curve segment. In Figure [*], this point is named $\vec{P}_6$. It can be computed by computing some intermediate points:

\begin{displaymath}
\vec{P}_1 = \frac{1}{2} ( \vec{A} + \vec{B} )
\end{displaymath} (5)


\begin{displaymath}
\vec{P}_2 = \frac{1}{2} ( \vec{B} + \vec{C} )
\end{displaymath} (6)


\begin{displaymath}
\vec{P}_3 = \frac{1}{2} ( \vec{C} + \vec{D} )
\end{displaymath} (7)


\begin{displaymath}
\vec{P}_4 = \frac{1}{2} ( \vec{P}_1 + \vec{P}_2 )
\end{displaymath} (8)


\begin{displaymath}
\vec{P}_5 = \frac{1}{2} ( \vec{P}_2 + \vec{P}_3 )
\end{displaymath} (9)

and finally
\begin{displaymath}
\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{displaymath} (10)

Using the same geometrical considerations as in Eqs. [*] and [*], we can now compute a unit vector, $\vec{n}_6$, perpendicular to the curve at $\vec{P}_6$ and obtain
\begin{displaymath}
n_{6x} = \frac{ P_{5y} - P_{4y} }{\sqrt{(P_{5x}-P_{4x})^2 + (P_{5y}-P_{4y})^2}}
\end{displaymath} (11)


\begin{displaymath}
n_{6y} = - \frac{ P_{5x} - P_{4x} }{\sqrt{(P_{5x}-P_{4x})^2 + (P_{5y}-P_{4y})^2}}
\end{displaymath} (12)

$\vec{P}'_6$ can now be computed as
\begin{displaymath}
\vec{P}'_6 = \vec{P}_6 + \vec{N}_6,
\end{displaymath} (13)

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 . 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 [*] we find

\begin{eqnarray*}
\vec{P}'_5 - \vec{P}'_4 & = & \nu \left( \vec{P}_5 - \vec{P}_...
...ac{\vec{C} + \vec{D}}{2} -
\frac{\vec{A} + \vec{B}}{2} \right)
\end{eqnarray*}

and hence finally
\begin{displaymath}
\vec{C}' + \vec{D}' - \vec{A}' - \vec{B}' = \nu \left(
\vec{C} + \vec{D} - \vec{A} - \vec{B} \right)\;.
\end{displaymath} (14)

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. [*] and [*]). On the way to Eq. [*], we made use of the well-known geometrical relations Eqs. [*] - [*].

Based on the same considerations that led to Eq. [*], we can write the corresponding equation for the point $\vec{P}'_6$:

\begin{displaymath}
\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{displaymath} (15)

Exploiting Eq. [*] and solving for $\vec{C}'$, we can reorganize Eq. [*]:
\begin{displaymath}
\vec{C}' = \frac{8 (\vec{N}_6 + \vec{P}_6) - \vec{A}' - \vec{D}'}{3} -
\vec{B}'
\end{displaymath} (16)

From this equation, we are able eliminate $\vec{B}'$ by substituting the transformed slope condition for point $\vec{P}'_6$ (Eq. [*]). We obtain
$\displaystyle \vec{C}'$ $\textstyle =$ $\displaystyle \frac{8 (\vec{N}_6 + \vec{P}_6) - \vec{A}' - \vec{D}'}{3}
+ \left...
... + \vec{D} - \vec{A} - \vec{B} \right)
- \vec{C}' - \vec{D}' + \vec{A}' \right]$  
$\displaystyle 2\, \vec{C}'$ $\textstyle =$ $\displaystyle \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)$  
$\displaystyle \vec{C}'$ $\textstyle =$ $\displaystyle \underbrace{\frac{4 (\vec{N}_6 + \vec{P}_6) + \vec{A}' - 2 \vec{D...
...{\left( \vec{C} + \vec{D} - \vec{A} -
\vec{B}\right)}
_{\mbox{$\vec{d}_C$}} \,.$ (17)

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. [*] and [*], 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 ([*]) and ([*]), we obtain the following $2\times2$ system of linear equations:

\begin{displaymath}
\left[
\begin{array}{cc}
(\vec{C}-\vec{D}) & \vec{d}_C...
.../2
\end{array} \right)
= \left( \vec{l}_C - \vec{D}' \right)
\end{displaymath} (18)

Formally, all vectors appearing in this equation are column vectors. The solution of the system can be written as
\begin{displaymath}
\left(
\begin{array}{cc}
\mu_C \\
\nu/2
\end{array} ...
...d{array} \right]^{-1}
\left( \vec{l}_C - \vec{D}' \right)\, .
\end{displaymath} (19)

Once $\vec{C}'$ has been computed, it is easy to compute $\vec{B}'$, by making use of Eq. [*].

A few remarks about the approach described above are appropriate.


next up previous contents index
Next: Connection of Path Segments Up: Stroked Characters Previous: Approach   Contents   Index
2004-10-04