Hobby’s 2D Direction Algorithm

hbghlyj

iciam07.pdf从第7页开始 或者 marburg07.pdf从第43页开始 或者 asyTUG.pdf从第7页开始 Smooth Paths • Asymptote can choose control points for you, using the algorithms of Hobby [1986] and Knuth [1986] Hobby’s 2D Direction Algorithm • A tridiagonal system of linear equations is solved to determine any unspecified directions $θ_k$ and $φ_k$ through each knot $z_k$:$$\frac{\theta_{k-1}-2 \phi_{k}}{\ell_{k}}=\frac{\phi_{k+1}-2 \theta_{k}}{\ell_{k+1}}$$

• The resulting shape may be adjusted by modifying optional tension parameters and curl boundary conditions Hobby’s 2D Control Point Algorithm Having prescribed outgoing and incoming path directions $e^{iθ_0}$ at node $z_0$ and $e^{iθ_1}$ at node $z_1$ relative to the vector $z_1 − z_0$, the control points are determined as: \begin{array}{l}u=z_{0}+e^{i \theta}\left(z_{1}-z_{0}\right) f(\theta,-\phi) \\ v=z_{1}-e^{i \phi}\left(z_{1}-z_{0}\right) f(-\phi, \theta)\end{array}where the relative distance function $f(\theta, \phi)$ is given by Hobby [1986].

Bezier Curves in 3D • Apply an affine transformation$$x_{i}^{\prime}=A_{i j} x_{j}+C_{i}$$to a Bezier curve:$$x(t)=\sum_{k=0}^{3} B_{k}(t) P_{k}, \quad t \in[0,1].$$$$x_{i}^{\prime}=A_{i j} x_{j}+C_{i} .$$• The resulting curve is also a Bezier curve:\begin{aligned} x_{i}^{\prime}(t) &=\sum_{k=0}^{3} B_{k}(t) A_{i j}\left(P_{k}\right)_{j}+C_{i} \\&=\sum_{k=0}^{3} B_{k}(t) P_{k}^{\prime},\end{aligned}where $P_{k}^{\prime}$ is the transformed $k^{\text {th}}$ control point, noting $\sum_{k=0}^{3} B_{k}(t)=1$. 3D Generalization of Hobby's algorithm • Must reduce to $2 \mathrm{D}$ algorithm in planar case. • Determine directions by applying Hobby's algorithm in the plane containing $z_{k-1}, z_{k}, z_{k+1}$. • The only ambiguity that can arise is the overall sign of the angles, which relates to viewing each $2 \mathrm{D}$ plane from opposing normal directions. • A reference vector based on the mean unit normal of successive segments can be used to resolve such ambiguities. 3D Control Point Algorithm • Hobby's control point algorithm can be generalized to 3D by expressing it in terms of the absolute directions $\omega_{0}$ and $\omega_{1}$:\begin{aligned} &u=z_{0}+\omega_{0}\left|z_{1}-z_{0}\right| f(\theta,-\phi) \\ &v=z_{1}-\omega_{1}\left|z_{1}-z_{0}\right| f(-\phi, \theta) \end{aligned}interpreting $\theta$ and $\phi$ as the angle between the corresponding path direction vector and $z_{1}-z_{0}$. • In this case there is an unambiguous reference vector for determining the relative sign of the angles $\phi$ and $\theta$.

hbghlyj

Hobby 1986 page 13:

Any particular family of curves determines a specific function $k$ that satisfies (12). The corresponding mock curvature function $\hat{k}$ consists of the linear terms in the Taylor series for $k(\theta, \phi, \tau, \bar{\tau})$, expanded about $(\theta, \phi)=(0,0)$. For the curves determined by (3) and (4) with $\rho$ and $\sigma$ determined by (10) or (11), $$ k(\theta, \phi, \tau, \bar{\tau})=\frac{2 \sigma(\theta, \phi) \sin (\theta+\phi) / \bar{\tau}-6 \sin \theta}{(\rho(\theta, \phi) / \tau)^{2}} $$ and $$ \hat{k}(\theta, \phi, \tau, \bar{\tau})=\tau^{2}\left(\frac{2(\theta+\phi)}{\bar{\tau}}-6 \theta\right), $$ where the angles are measured in radians. Since the tension parameters are always known in advance, they are treated like constants in this expansion.