1 \documentclass{scrartcl
}
2 \usepackage{amsmath,amssymb,mathtools
}
3 \usepackage[english
]{babel
}
5 % Allow to build the PDF with either lualatex (preferred) or pdflatex
10 \usepackage[T1]{fontenc}
11 \usepackage[utf8
]{inputenc}
16 \subtitle{Bare Attempt to Improve Offset Curve Algorithm
}
17 \author{Giandomenico Rossi
\and Nicola Fontana
}
20 \DeclarePairedDelimiter\abs{\lvert}{\rvert}%
21 \DeclarePairedDelimiter\norm{\lVert}{\rVert}%
23 \setlength\parindent{0pt
}
24 \setlength\parskip{6pt
}
26 \newcommand\V[1]{\vec{#1}}
27 \newcommand\D[1]{\dot{#1}}
28 \newcommand\DV[1]{\D{\V{#1}}}
29 \newcommand\SP[2]{\langle #1,
#2 \rangle}
36 Computer Aided Design (CAD) and related software is often based on cubic
37 Bézier curves: the Postscript language and consecuentely the PDF file
38 format are two widespread examples of such software. Defining an optimal
39 algorithm for approximating a Bézier curve parallel to the original one
40 at a specific distance (the so called ``offset curve'') is a big
41 requirement in CAD drafting: it is heavily used while constructing
42 derived entities (e.g., a fillet) or to express machining allowance.
44 This
document describes an algorithm suitable for CAD purposes. In those
45 cases, the starting and ending points of the offset curve
\textbf{must
}
46 have coordinates and slopes coincident with the perfect solution, so the
47 continuity with previous and next offseted entity is preserved.
52 The generic formula for a cubic Bézier curve is
54 \V{B
}(t) = b_0(t)
\V{B
}_0 + b_1(t)
\V{B
}_1 + b_2(t)
\V{B
}_2 + b_3(t)
\V{B
}_3
59 \V{B
}_i &
\equiv ( B^i_x, B^i_y )
\in \mathbb{R
}; \\
60 b_i(t) &
\equiv \binom{3}{i
} t^i (
1-t)^
{3-i
}. \\
65 Given in $\
{t_i\
}_
{i=
0}^n$ a set of values for $t$ chosen in some
66 manner with $t_0=
0, t_n=
1$ and in $R$ the required distance of the offset
68 \begin{equation
}\label{eq:Ci
}
69 \V{C
}_i =
\V{B
}(t_i) + R
\left.
70 \frac{\D{B
}_y, -
\D{B
}_x
}{\sqrt{\D{B
}_x^
2 +
\D{B
}_y^
2}}
71 \,
\right|_
{t=t_i
} \forall t_i
73 is the equation of the offset curve that has in $\
{\V{C
}_i\
}_
{i=
0}^n$ the
74 set of its points and where $
\DV{B
} \equiv (
\D{B
}_x,
\D{B
}_y )
\equiv
75 \left(
\frac{d
}{dt
} B_x(t),
\frac{d
}{dt
} B_y(t)
\right)$.
77 We must find the Bézier curve
78 \begin{equation
}\label{eq:q
}
79 \V{Q
}(t) = b_0(t)
\V{Q
}_0 + b_1(t)
\V{Q
}_1 + b_2(t)
\V{Q
}_2 + b_3(t)
\V{Q
}_3
83 \V{Q
}_i
\equiv ( Q^i_x, Q^i_y )
\in \mathbb{R
} \qquad i =
0,
1,
2,
3
85 which best fits
\eqref{eq:Ci
} within the needed constraints, that is:
87 \item $
\V{Q
}(
0) =
\V{C
}_0$ and $
\V{Q
}(
1) =
\V{C
}_n$ (interpolation);
88 \item $
\DV{Q
}(
0) =
\DV{B
}(
0)$ and $
\DV{Q
}(
1) =
\DV{B
}(
1)$ (tangents),
89 where $
\DV{Q
} \equiv \frac{d
}{dt
} \V{Q
}(t)$.
93 Condition
1 implies that $
\V{Q
}_0 =
\V{C
}_1$ and $
\V{Q
}_3 =
\V{C
}_n$.
95 Condition
2 implies that $
\DV{Q
}_0 =
\DV{B
}_0$ and
96 $
\DV{Q
}_3 =
\DV{B
}_3$. Imposing by convention
97 \begin{equation
}\label{eq:pi
}
98 \V{P
}_i =
\V{B
}_
{i+
1} -
\V{B
}_i;
\qquad i =
0,
1,
2;
100 we can calculate $
\DV{B
}_0$ and $
\DV{B
}_3$ directly from the hodograph
103 \DV{B
}(t) &=
3 \left[ (
1-t)^
2 \V{P
}_0 +
2t(
1-t)
\V{P
}_1 + t^
2 \V{P
}_2
\right]; \\
104 \DV{B
}(
0) &=
3 \V{P
}_0
\equiv \DV{B
}_0 =
\DV{Q
}_0; \\
105 \DV{B
}(
1) &=
3 \V{P
}_2
\equiv \DV{B
}_3 =
\DV{Q
}_3.
107 Knowing that one of the properties of a Bézier curve is the start of the
108 curve is tangent to the first section of the control polygon and the end
109 is tangent to the last section, condition
2 is hence equivalent to:
110 \begin{equation
}\label{eq:q12
}
112 \V{Q
}_1 &=
\V{Q
}_0 +
\frac{r
}{3} \DV{Q
}_0 =
\V{Q
}_0 + r
\V{P
}_0; \\
113 \V{Q
}_2 &=
\V{Q
}_3 +
\frac{s
}{3} \DV{Q
}_3 =
\V{Q
}_3 + s
\V{P
}_2.
115 \qquad r, s
\in \mathbb{R
}
118 Substituting
\eqref{eq:q12
} in
\eqref{eq:q
} we get
120 \V{Q
}(t) = b_0(t)
\V{Q
}_0 + b_1(t)
\V{Q
}_0 + b_1(t) r
\V{P
}_0 +
121 b_2(t)
\V{Q
}_3 + b_2(t) s
\V{P
}_2 + b_3(t)
\V{Q
}_3.
124 Determine the value of $r$ and $s$ that minimizes the quantity
125 $
\phi =
\sum \left[ \V{C
}_i -
\V{Q
}(t_i)
\right]^
2$, equivalent to
129 \frac{\delta\phi}{\delta r
} =
0;\\
130 \frac{\delta\phi}{\delta s
} =
0.
134 Now, given the shortcuts
\footnote{Either $i =
0$ and $i = n$ are not
135 considered because $
\V{C
}_0$ and $
\V{C
}_n$ have been already used as
136 $
\V{Q
}_0$ and $
\V{Q
}_3$ by the interpolation constraint.
} $
\sum \equiv
137 \sum_{i=
1}^
{n-
1}$ and $b_j
\equiv b_j(t_i)$, we can write $
\phi$ as
139 \phi(r, s) =
\sum \left[ \V{C
}_i - b_0
\V{Q
}_0 - b_1
\V{Q
}_0 -
140 r b_1
\V{P
}_0 - b_2
\V{Q
}_3 - s b_2
\V{P
}_2 - b_3
\V{Q
}_3
\right]^
2;
143 that, applied to the previous system, bring us to the following linear system
147 \V{C
}_i - b_0
\V{Q
}_0 - b_1
\V{Q
}_0 - r b_1
\V{P
}_0 -
148 b_2
\V{Q
}_3 - s b_2
\V{P
}_2 - b_3
\V{Q
}_3
149 \right)
\left( -
2 b_1
\V{P
}_0
\right) &=
0; \\
151 \V{C
}_i - b_0
\V{Q
}_0 - b_1
\V{Q
}_0 - r b_1
\V{P
}_0 -
152 b_2
\V{Q
}_3 - s b_2
\V{P
}_2 - b_3
\V{Q
}_3
153 \right)
\left( -
2 b_2
\V{P
}_2
\right) &=
0; \\
161 b_1
\SP{\V{C
}_i
}{\V{P
}_0
} -
162 b_0 b_1
\SP{\V{Q
}_0
}{\V{P
}_0
} -
163 b_1 b_1
\SP{\V{Q
}_0
}{\V{P
}_0
} -
164 r b_1 b_1
\SP{\V{P
}_0
}{\V{P
}_0
} \\ -
165 b_1 b_2
\SP{\V{Q
}_3
}{\V{P
}_0
} -
166 s b_1 b_2
\SP{\V{P
}_2
}{\V{P
}_0
} -
167 b_1 b_3
\SP{\V{Q
}_3
}{\V{P
}_0
}
172 b_2
\SP{\V{C
}_i
}{\V{P
}_2
} -
173 b_0 b_2
\SP{\V{Q
}_0
}{\V{P
}_2
} -
174 b_1 b_2
\SP{\V{Q
}_0
}{\V{P
}_2
} -
175 r b_1 b_2
\SP{\V{P
}_0
}{\V{P
}_2
} \\ -
176 b_2 b_2
\SP{\V{Q
}_3
}{\V{P
}_2
} -
177 s b_2 b_2
\SP{\V{P
}_2
}{\V{P
}_2
} -
178 b_2 b_3
\SP{\V{Q
}_3
}{\V{P
}_2
}
184 Given the additional conventions
185 \begin{equation
}\label{eq:DE
}
187 D_0 &
\equiv \sum b_1
\SP{\V{C
}_i
}{\V{P
}_0
}; \\
188 D_2 &
\equiv \sum b_2
\SP{\V{C
}_i
}{\V{P
}_2
}; \\
189 E_
{jk
} &
\equiv \sum b_j b_k;
192 we can substitute to get
196 D_0 - E_
{01} \SP{\V{Q
}_0
}{\V{P
}_0
} -
197 E_
{11} \SP{\V{Q
}_0
}{\V{P
}_0
} -
198 r E_
{11} \SP{\V{P
}_0
}{\V{P
}_0
} -
199 E_
{12} \SP{\V{Q
}_3
}{\V{P
}_0
} \\ -
200 s E_
{12} \SP{\V{P
}_2
}{\V{P
}_0
} -
201 E_
{13} \SP{\V{Q
}_3
}{\V{P
}_0
} &=
0;
204 D_2 - E_
{02} \SP{\V{Q
}_0
}{\V{P
}_2
} -
205 E_
{12} \SP{\V{Q
}_0
}{\V{P
}_2
} -
206 r E_
{12} \SP{\V{P
}_0
}{\V{P
}_2
} -
207 E_
{22} \SP{\V{Q
}_3
}{\V{P
}_2
} \\ -
208 s E_
{22} \SP{\V{P
}_2
}{\V{P
}_2
} -
209 E_
{23} \SP{\V{Q
}_3
}{\V{P
}_2
} &=
0;
213 and derive the following known terms
214 \begin{equation
}\label{eq:ACD
}
216 A_1 &= D_0 -
\SP{\V{Q
}_0
}{\V{P
}_0
} (E_
{01} + E_
{11}) -
217 \SP{\V{Q
}_3
}{\V{P
}_0
} (E_
{12} + E_
{13}); \\
218 A_2 &= D_2 -
\SP{\V{Q
}_0
}{\V{P
}_2
} (E_
{02} + E_
{12}) -
219 \SP{\V{Q
}_3
}{\V{P
}_2
} (E_
{22} + E_
{23}); \\
220 A_3 &=
\SP{\V{P
}_0
}{\V{P
}_0
} E_
{11}; \\
221 A_4 &=
\SP{\V{P
}_0
}{\V{P
}_2
} E_
{12}; \\
222 A_5 &=
\SP{\V{P
}_2
}{\V{P
}_2
} E_
{22}. \\
226 The system is hence reduced to
229 r A_3 + s A_4 &= A_1; \\
230 r A_4 + s A_5 &= A_2; \\
233 from which we can calculate $r$ and $s$
234 \begin{equation
}\label{eq:rs
}
236 r &=
\frac{A_1 A_5 - A_4 A_2
}{A_3 A_5 - A_4 A_4
}; \\
237 s &=
\frac{A_3 A_2 - A_1 A_4
}{A_3 A_5 - A_4 A_4
}. \\
244 \item Select $\
{t_i\
}_
{i=
0}^n$ as shown in section~
\ref{sec:ti
};
245 \item compute $\
{\V{C
}_i\
}_
{i=
0}^n$ with
\eqref{eq:Ci
}:
246 $
\V{Q
}_0 =
\V{C
}_0$ and $
\V{Q
}_3 =
\V{C
}_n$;
247 \item calculate $
\V{P
}_0$ and $
\V{P
}_2$ with
\eqref{eq:pi
};
248 \item calculate $D_0$, $D_2$, $E_
{01}$, $E_
{02}$, $E_
{11}$,
249 $E_
{12}$, $E_
{13}$, $E_
{22}$ and $E_
{23}$ with
\eqref{eq:DE
};
250 \item calculate $A_1$, $A_2$, $A_3$, $A_4$ and $A_5$ with
252 \item calculate $r$ and $s$ with
\eqref{eq:rs
};
253 \item get $
\V{Q
}_1$ and $
\V{Q
}_2$ from
\eqref{eq:q12
}.
256 $
\V{Q
}_0$ and $
\V{Q
}_3$ are respectively the starting and ending
257 points of the offset Bézier curve while $
\V{Q
}_1$ and $
\V{Q
}_2$ are
261 \section{Choosing $t_i$
\label{sec:ti
}}
263 To select the $\
{t_i\
}_
{i=
0}^n$ set of values for $t$ needed by
264 the offsetting algorithm, we can use different methods. Here are some
265 basic ones: no further research is performed to check the quality of
268 \subsection{Method
1: too lazy to think
}
270 The most obvious method is to directly use evenly spaced time values:
276 \subsection{Method
2: squared distances
}
278 Let's select some $\
{\V{F
}_i\
}_
{i=
0}^n$ points on $
\V{B
}(t)$, for
279 instance by resolving the $t$ values got from the lazy method. The
280 following formula will partition the Bézier curve proportionally to
281 their squared distances:
286 t_i &= t_
{i-
1} +
\frac{\left(
\V{F
}_i -
\V{F
}_
{i-
1} \right)^
2}{f
}.
288 \qquad f =
\sum_{i=
1}^n
\left(
\V{F
}_i -
\V{F
}_
{i-
1} \right)^
2
291 \subsection{Method
3: distances
}
293 A variant of the previous method that uses distances instead of squared
294 distances. This is computationally more intensive because the norm of
295 a vector $\|
\V{F
} \|
\equiv \sqrt{F_x^
2 + F_y^
2}$ requires a square
301 t_i &= t_
{i-
1} +
\frac{\|
\V{F
}_i -
\V{F
}_
{i-
1} \|
}{f
}.
303 \qquad f =
\sum_{i=
1}^n \|
\V{F
}_i -
\V{F
}_
{i-
1} \|