From 8906fdca3f5f66a7ca79500a6d223e11db7d64d4 Mon Sep 17 00:00:00 2001 From: Nicola Fontana Date: Tue, 14 Oct 2014 12:55:29 +0200 Subject: [PATCH] doc: move old algorithm description on its own MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Removed description of the offset algorithm for cubic Bézier curve from the source code to its own PDF inside nodist/ directory. Renamed two letters variables to an arbitrary one-letter so it can be expressed better in mathematical formulae. --- nodist/.gitignore | 3 +- nodist/Makefile | 5 +- nodist/handcraft.tex | 198 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/cpml/cpml-curve.c | 156 +++------------------------------------ 4 files changed, 216 insertions(+), 146 deletions(-) create mode 100644 nodist/handcraft.tex diff --git a/nodist/.gitignore b/nodist/.gitignore index 5657cd6a..3872b076 100644 --- a/nodist/.gitignore +++ b/nodist/.gitignore @@ -1,7 +1,8 @@ /adg.0 /adg.log -/desktop.png /baioca.pdf +/desktop.png +/handcraft.pdf /overview.pdf /web.png *.aux diff --git a/nodist/Makefile b/nodist/Makefile index b154edf2..e59a4cf2 100644 --- a/nodist/Makefile +++ b/nodist/Makefile @@ -25,11 +25,14 @@ CLEAN_1=latexmk -C CONVERT=convert -flatten -density 150 -quality 90 -all: overview.pdf baioca.pdf desktop.png web.png +all: overview.pdf handcraft.pdf baioca.pdf desktop.png web.png overview.pdf: overview.tex symbols-0.mps ALWAYS_OUTDATED $(DOC)$(TEX2PDF) overview.tex +handcraft.pdf: handcraft.tex ALWAYS_OUTDATED + $(DOC)$(TEX2PDF) handcraft.tex + baioca.pdf: baioca.tex ALWAYS_OUTDATED $(DOC)$(TEX2PDF) baioca.tex diff --git a/nodist/handcraft.tex b/nodist/handcraft.tex new file mode 100644 index 00000000..83975e8a --- /dev/null +++ b/nodist/handcraft.tex @@ -0,0 +1,198 @@ +\documentclass{scrartcl} +\usepackage{amsmath,amssymb,mathtools} +\usepackage[english]{babel} + +% Allow to build the PDF with either lualatex (preferred) or pdflatex +\usepackage{iftex} +\ifLuaTeX + \usepackage{luatextra} +\else + \usepackage[T1]{fontenc} + \usepackage[utf8]{inputenc} + \usepackage{lmodern} +\fi + +\title{Handcraft algorithm} +\subtitle{A disjointed algorithm for offsetting cubic Bézier curves} +\author{Nicola Fontana} +\date{February 25, 2009} + +\setlength\parindent{0pt} +\setlength\parskip{6pt} + +\begin{document} + +\maketitle + +\begin{abstract} +This is basically the transcription of the algorithm used by the +ADG canvas on its early development phases. This algorithm has been +superseded in recent releases by BAIOCA. It is included here for +completeness and historical reasons. +\end{abstract} + +Given a cubic Bézier primitive, it must be found the approximated +Bézier curve parallel to the original one at a specific distance +(the so called "offset curve"). The four points needed to build +the new curve must be returned. + +To solve the offset problem, a custom algorithm is used. First, the +resulting curve MUST have the same slope at the start and end point. +These constraints are not sufficient to resolve the system, so I let +the curve pass thought a given point (r, known and got from the +original curve) at a given time (m, now hardcoded to 0.5). + +Firstly, some useful variables are defined: + +\begin{equation*} +\begin{split} + v_0 &= \text{unitvector}(\text{p[1]} - \text{p[0]}) \times \text{offset} \\ + v_3 &= \text{unitvector}(\text{p[3]} - \text{p[2]}) \times \text{offset} \\ + p_0 &= \text{p[0]} + \text{normal}(v_0) \\ + p_3 &= \text{p[3]} + \text{normal}(v_3) \\ +\end{split} +\end{equation*} + +The resulting curve must have the same slopes than the original +one at the start and end points. Forcing the same slopes means: + +\begin{equation*} +p_1 = p_0 + k_0 v_0. +\end{equation*} + +where $k_0$ is an arbitrary factor. Decomposing for $x$ and $y$: + +\begin{equation*} +\begin{dcases} + p_{1x} = p_{0x} + k_0 v_{0x} \\ + p_{1y} = p_{0y} + k_0 v_{0y} \\ +\end{dcases} +\end{equation*} + +and doing the same for the end point: + +\begin{equation*} +\begin{dcases} + p_{2x} = p_{3x} + k_3 v_{3x} \\ + p_{2y} = p_{3y} + k_3 v_{3y} \\ +\end{dcases} +\end{equation*} + +This does not give a resolvable system though. The curve will be +interpolated by forcing its path to pass throught $r$ when +\textit{time} is $m$, where $0 \leq m \leq 1$. Knowing the function of +the cubic Bézier: + +\begin{equation*} +C(t) = (1-t)^3p_0 + 3t(1-t)^2p_1 + 3t^2(1-t)p_2 + t^3p_3. +\end{equation*} + +and forcing $t = m$ and $C(t) = r$: + +\begin{equation*} +\begin{split} + r &= (1-m)^3 p_0 + 3m(1-m)^2 p_1 + 3m^2 (1-m) p_2 + m^3 p_3 \\ + (1-m) p_1 + m p_2 &= \frac{r - (1-m)^3p_0 - m^3p_3}{3m (1-m)} \\ +\end{split} +\end{equation*} + +brings to the final system: + +\begin{equation*} +\begin{dcases} + p_{1x} = p_{0x} + k_0 v_{0x} \\ + p_{1y} = p_{0y} + k_0 v_{0y} \\ + p_{2x} = p_{3x} + k_3 v_{3x} \\ + p_{2y} = p_{3y} + k_3 v_{3y} \\ + (1-m) p_{1x} + m p_{2x} = \frac{r_x - (1-m)^3 p_{0x} - m^3 p_{3x}}{3m (1-m)} \\ + (1-m) p_{1y} + m p_{2y} = \frac{r_y - (1-m)^3 p_{0y} - m^3 p_{3y}}{3m (1-m)} \\ +\end{dcases} +\end{equation*} + +Substituting and resolving for $k_0$ and $k_3$: + +\begin{equation*} +\begin{dcases} + (1-m) k_0 v_{0x} + m k_3 v_{3x} = \frac{r_x - (1-m)^3 p_{0x} - m^3 p_{3x}}{3m (1-m)} - (1-m) p_{0x} - m p_{3x} \\ + (1-m) k_0 v_{0y} + m k_3 v_{3y} = \frac{r_y - (1-m)^3 p_{0y} - m^3 p_{3y}}{3m (1-m)} - (1-m) p_{0y} - m p_{3y} \\ +\end{dcases} +\end{equation*} + +\begin{equation*} +\begin{dcases} + (1-m) k_0 v_{0x} + m k_3 v_{3x} = \frac{r_x - (1-m)^2 (1+2m) p_{0x} - m^2 (3-2m) p_{3x}}{3m (1-m)} \\ + (1-m) k_0 v_{0y} + m k_3 v_{3y} = \frac{r_y - (1-m)^2 (1+2m) p_{0y} - m^2 (3-2m) p_{3y}}{3m (1-m)} \\ +\end{dcases} +\end{equation*} + +Letting: + +\begin{equation*} + s = \frac{r - (1-m)^2(1+2m) p_0 - m^2(3-2m) p_3}{3m (1 - m)} +\end{equation*} + +reduces the above to this final equations: + +\begin{equation*} +\begin{dcases} + s_x = (1-m) k_0 v_{0x} + m k_3 v_{3x} \\ + s_y = (1-m) k_0 v_{0y} + m k_3 v_{3y} \\ +\end{dcases} +\end{equation*} + +If $v_{0x} \ne; 0$, the system can be resolved for $k_0$ and $k_3$ +calculated accordingly: + +\begin{equation*} +\begin{dcases} + k_0 = \frac{s_x - m k_3 v_{3x}}{(1-m) v_{0x}} \\ + s_y = \frac{(s_x - m k_3 v_{3x}) v_{0y}}{v_{0x}} + m k_3 v_{3y} \\ +\end{dcases} +\end{equation*} + +\begin{equation*} +\begin{dcases} + k_0 = \frac{s_x - m k_3 v_{3x}}{(1-m) v_{0x}} \\ + s_y - \frac{s_x v_{0y}}{v_{0x}} = k_3 m (v_{3y} - \frac{v_{3x} v_{0y}}{v_{0x}}) \\ +\end{dcases} +\end{equation*} + +\begin{equation*} +\begin{dcases} + k_0 = \frac{s_x - m k_3 v_{3x}}{(1-m) v_{0x}} \\ + k_3 = \frac{s_y - s_x \frac{v_{0y}}{v_{0x}}}{m (v_{3y} - v_{3x} \frac{v_{0y}}{v_{0x}})} \\ +\end{dcases} +\end{equation*} + +Otherwise, if $v_{3x} \ne 0$, the system can be solved for $k_3$ and $k_0$ +calculated accordingly: + +\begin{equation*} +\begin{dcases} + k_3 = \frac{s_x - (1-m) k_0 v_{0x}}{m v_{3x}} \\ + s_y = (1-m) k_0 v_{0y} + \frac{[s_x - (1-m) k_0 v_{0x}] v_{3y}}{v_{3x}} \\ +\end{dcases} +\end{equation*} + +\begin{equation*} +\begin{dcases} + k_3 = \frac{s_x - (1-m) k_0 v_{0x}}{m v_{3x}} \\ + k_0 (1-m) (v_{0y} - k_0 v_{0x} \frac{v_{3y}}{v_{3x}}) = s_y - s_x \frac{v_{3y}}{v_{3x}} \\ +\end{dcases} +\end{equation*} + +\begin{equation*} +\begin{dcases} + k_3 = \frac{s_x - (1-m) k_0 v_{0x}}{m v_{3x}} \\ + k_0 = \frac{s_y - s_x \frac{v_{3y}}{v_{3x}}}{(1-m) (v_{0y} - v_{0x} \frac{v_{3y}}{v_{3x}})} \\ +\end{dcases} +\end{equation*} + +The whole process must be guarded against division by 0 exceptions. +If either $v_{0x}$ and $v_{3x}$ are 0, the first equation will be +inconsistent. More in general, the +$v_{0x} \times v_{3y} = v_{3x} \times v_{3y}$ condition must be avoided. This is +the first situation to avoid, in which case an alternative approach +should be used. + +\end{document} diff --git a/src/cpml/cpml-curve.c b/src/cpml/cpml-curve.c index 1c4288e9..be0aa534 100644 --- a/src/cpml/cpml-curve.c +++ b/src/cpml/cpml-curve.c @@ -54,138 +54,6 @@ * opposite or staggered. * * - * - * Offseting algorithm - * - * Given a cubic Bézier primitive, it must be found the approximated - * Bézier curve parallel to the original one at a specific distance - * (the so called "offset curve"). The four points needed to build - * the new curve must be returned. - * - * To solve the offset problem, a custom algorithm is used. First, the - * resulting curve MUST have the same slope at the start and end point. - * These constraints are not sufficient to resolve the system, so I let - * the curve pass thought a given point (pm, known and got from the - * original curve) at a given time (m, now hardcoded to 0.5). - * - * Firstly, some useful variables are defined: - * - * - * v0 = unitvector(p[1] − p[0]) × offset; - * v3 = unitvector(p[3] − p[2]) × offset; - * p0 = p[0] + normal v0; - * p3 = p[3] + normal v3. - * - * - * The resulting curve must have the same slopes than the original - * one at the start and end points. Forcing the same slopes means: - * - * - * p1 = p0 + k0 v0. - * - * - * where %k0 is an arbitrary factor. Decomposing for %x and %y: - * - * - * p1.x = p0.x + k0 v0.x; - * p1.y = p0.y + k0 v0.y. - * - * - * and doing the same for the end point: - * - * - * p2.x = p3.x + k3 v3.x; - * p2.y = p3.y + k3 v3.y. - * - * - * This does not give a resolvable system, though. The curve will be - * interpolated by forcing its path to pass throught %pm when - * time is %m, where 0 ≤ m ≤ 1. - * Knowing the function of the cubic Bézier: - * - * - * C(t) = (1 − t)³p0 + 3t(1 − t)²p1 + 3t²(1 − t)p2 + t³p3. - * - * - * and forcing t = m and C(t) = pm: - * - * - * pm = (1 − m)³p0 + 3m(1 − m)²p1 + 3m²(1 − m)p2 + m³p3. - * - * (1 − m) p1 + m p2 = (pm − (1 − m)³p0 − m³p3) / (3m (1 − m)). - * - * - * gives this final system: - * - * - * p1.x = p0.x + k0 v0.x; - * p1.y = p0.y + k0 v0.y; - * p2.x = p3.x + k3 v3.x; - * p2.y = p3.y + k3 v3.y; - * (1 − m) p1.x + m p2.x = (pm.x − (1 − m)³p0.x − m³p3.x) / (3m (1 − m)); - * (1 − m) p1.y + m p2.y = (pm.y − (1 − m)³p0.y − m³p3.y) / (3m (1 − m)). - * - * - * Substituting and resolving for %k0 and %k3: - * - * - * (1 − m) k0 v0.x + m k3 v3.x = (pm.x − (1 − m)³p0.x − m³p3.x) / (3m (1 − m)) − (1 − m) p0.x − m p3.x; - * (1 − m) k0 v0.y + m k3 v3.y = (pm.y − (1 − m)³p0.y − m³p3.y) / (3m (1 − m)) − (1 − m) p0.y − m p3.y. - * - * (1 − m) k0 v0.x + m k3 v3.x = (pm.x − (1 − m)²(1+2m) p0.x − m²(3 − 2m) p3.x) / (3m (1 − m)); - * (1 − m) k0 v0.y + m k3 v3.y = (pm.y − (1 − m)²(1+2m) p0.y − m²(3 − 2m) p3.y) / (3m (1 − m)). - * - * - * Letting: - * - * - * pk = (pm − (1 − m)²(1+2m) p0 − m²(3 − 2m) p3) / (3m (1 − m)). - * - * - * reduces the above to this final equations: - * - * - * (1 − m) k0 v0.x + m k3 v3.x = pk.x; - * (1 − m) k0 v0.y + m k3 v3.y = pk.y. - * - * - * If v0.x ≠ 0, the system can be resolved for %k0 and - * %k3 calculated accordingly: - * - * - * k0 = (pk.x − m k3 v3.x) / ((1 − m) v0.x); - * (pk.x − m k3 v3.x) v0.y / v0.x + m k3 v3.y = pk.y. - * - * k0 = (pk.x − m k3 v3.x) / ((1 − m) v0.x); - * k3 m (v3.y − v3.x v0.y / v0.x) = pk.y − pk.x v0.y / v0.x. - * - * k3 = (pk.y − pk.x v0.y / v0.x) / (m (v3.y − v3.x v0.y / v0.x)); - * k0 = (pk.x − m k3 v3.x) / ((1 − m) v0.x). - * - * - * Otherwise, if v3.x ≠ 0, the system can be solved - * for %k3 and %k0 calculated accordingly: - * - * - * k3 = (pk.x − (1 − m) k0 v0.x) / (m v3.x); - * (1 − m) k0 v0.y + (pk.x − (1 − m) k0 v0.x) v3.y / v3.x = pk.y. - * - * k3 = (pk.x − (1 − m) k0 v0.x) / (m v3.x); - * k0 (1 − m) (v0.y − k0 v0.x v3.y / v3.x) = pk.y − pk.x v3.y / v3.x. - * - * k0 = (pk.y − pk.x v3.y / v3.x) / ((1 − m) (v0.y − v0.x v3.y / v3.x)); - * k3 = (pk.x − (1 − m) k0 v0.x) / (m v3.x). - * - * - * The whole process must be guarded against division by 0 exceptions. - * If either v0.x and v3.x are 0, the first - * equation will be inconsistent. More in general, the - * v0.x × v3.y = v3.x × v3.y condition must - * be avoided. This is the first situation to avoid, in which case - * an alternative approach should be used. - * - * - * * * Since: 1.0 **/ @@ -331,7 +199,7 @@ offset(CpmlPrimitive *curve, double offset) { double m, mm; CpmlVector v0, v3, vm, vtmp; - CpmlPair p0, p1, p2, p3, pm; + CpmlPair p0, p1, p2, p3, r; m = 0.5; mm = 1-m; @@ -351,13 +219,13 @@ offset(CpmlPrimitive *curve, double offset) v3.x = p3.x - p2.x; v3.y = p3.y - p2.y; - /* pm = point in C(m) offseted the requested @offset distance */ + /* r = point in C(m) offseted the requested @offset distance */ cpml_curve_put_vector_at_time(curve, m, &vm); cpml_vector_set_length(&vm, offset); cpml_vector_normal(&vm); - cpml_curve_put_pair_at_time(curve, m, &pm); - pm.x += vm.x; - pm.y += vm.y; + cpml_curve_put_pair_at_time(curve, m, &r); + r.x += vm.x; + r.y += vm.y; /* p0 = p0 + normal of v0 of @offset magnitude (exact value) */ cpml_pair_copy(&vtmp, &v0); @@ -380,18 +248,18 @@ offset(CpmlPrimitive *curve, double offset) p2.x = p3.x - v3.x + vm.x * 4/3; p2.y = p3.y - v3.y + vm.y * 4/3; } else { - CpmlPair pk; + CpmlPair s; double k0, k3; - pk.x = (pm.x - mm*mm*(1+m+m)*p0.x - m*m*(1+mm+mm)*p3.x) / (3*m*(1-m)); - pk.y = (pm.y - mm*mm*(1+m+m)*p0.y - m*m*(1+mm+mm)*p3.y) / (3*m*(1-m)); + s.x = (r.x - mm*mm*(1+m+m)*p0.x - m*m*(1+mm+mm)*p3.x) / (3*m*(1-m)); + s.y = (r.y - mm*mm*(1+m+m)*p0.y - m*m*(1+mm+mm)*p3.y) / (3*m*(1-m)); if (v0.x != 0) { - k3 = (pk.y - pk.x*v0.y / v0.x) / (m*(v3.y - v3.x*v0.y / v0.x)); - k0 = (pk.x - m*k3*v3.x) / (mm*v0.x); + k3 = (s.y - s.x*v0.y / v0.x) / (m*(v3.y - v3.x*v0.y / v0.x)); + k0 = (s.x - m*k3*v3.x) / (mm*v0.x); } else { - k0 = (pk.y - pk.x*v3.y / v3.x) / (mm*(v0.y - v0.x*v3.y / v3.x)); - k3 = (pk.x - mm*k0*v0.x) / (m*v3.x); + k0 = (s.y - s.x*v3.y / v3.x) / (mm*(v0.y - v0.x*v3.y / v3.x)); + k3 = (s.x - mm*k0*v0.x) / (m*v3.x); } p1.x = p0.x + k0*v0.x; -- 2.11.4.GIT