summaryrefslogtreecommitdiff
path: root/Build/source/texk/dvisvgm/dvisvgm-1.8/src/Bezier.cpp
diff options
context:
space:
mode:
authorPeter Breitenlohner <peb@mppmu.mpg.de>2014-07-31 07:10:42 +0000
committerPeter Breitenlohner <peb@mppmu.mpg.de>2014-07-31 07:10:42 +0000
commit4768b1b377517534111ca75dadc6b9bf4f6a6746 (patch)
tree98ef7890e09b49b3ead45778e78358d49ecefe50 /Build/source/texk/dvisvgm/dvisvgm-1.8/src/Bezier.cpp
parentcacd4d369a87819295d5b1759f2b3e8f9eedfab3 (diff)
dvisvgm 1.8
git-svn-id: svn://tug.org/texlive/trunk@34783 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/texk/dvisvgm/dvisvgm-1.8/src/Bezier.cpp')
-rw-r--r--Build/source/texk/dvisvgm/dvisvgm-1.8/src/Bezier.cpp188
1 files changed, 188 insertions, 0 deletions
diff --git a/Build/source/texk/dvisvgm/dvisvgm-1.8/src/Bezier.cpp b/Build/source/texk/dvisvgm/dvisvgm-1.8/src/Bezier.cpp
new file mode 100644
index 00000000000..10201fa5062
--- /dev/null
+++ b/Build/source/texk/dvisvgm/dvisvgm-1.8/src/Bezier.cpp
@@ -0,0 +1,188 @@
+/*************************************************************************
+** Bezier.cpp **
+** **
+** This file is part of dvisvgm -- the DVI to SVG converter **
+** Copyright (C) 2005-2014 Martin Gieseking <martin.gieseking@uos.de> **
+** **
+** This program is free software; you can redistribute it and/or **
+** modify it under the terms of the GNU General Public License as **
+** published by the Free Software Foundation; either version 3 of **
+** the License, or (at your option) any later version. **
+** **
+** This program is distributed in the hope that it will be useful, but **
+** WITHOUT ANY WARRANTY; without even the implied warranty of **
+** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the **
+** GNU General Public License for more details. **
+** **
+** You should have received a copy of the GNU General Public License **
+** along with this program; if not, see <http://www.gnu.org/licenses/>. **
+*************************************************************************/
+
+#include <utility>
+#include "Bezier.h"
+
+using namespace std;
+
+Bezier::Bezier () {
+ _points[0] = _points[1] = _points[2] = _points[3] = 0;
+}
+
+
+/** Creates a quadratic Bézier curve. internally, it's represented as a cubic one. */
+Bezier::Bezier (const DPair &p0, const DPair &p1, const DPair &p2) {
+ _points[0] = p0;
+ _points[1] = p0+(p1-p0)*2.0/3.0;
+ _points[2] = p2+(p1-p2)*2.0/3.0;
+ _points[3] = p2;
+}
+
+
+Bezier::Bezier (const DPair &p0, const DPair &p1, const DPair &p2, const DPair &p3) {
+ _points[0] = p0;
+ _points[1] = p1;
+ _points[2] = p2;
+ _points[3] = p3;
+}
+
+
+/** Creates a subcurve of a given Bézier curve.
+ * @param[in] source original curve to be clipped
+ * @param[in] t0 'time' parameter \f$\in[0,1]\f$ of source curve where the subcurve starts
+ * @param[in] t1 'time' parameter \f$\in[0,1]\f$ of source curve where the subcurve ends */
+Bezier::Bezier (const Bezier &source, double t0, double t1) {
+ if (t0 == t1)
+ _points[0] = _points[1] = _points[2] = _points[3] = source.pointAt(t0);
+ else {
+ if (t0 > t1)
+ swap(t0, t1);
+ if (t0 == 0)
+ source.subdivide(t1, this, 0);
+ else if (t1 == 1)
+ source.subdivide(t0, 0, this);
+ else {
+ Bezier subcurve;
+ source.subdivide(t0, 0, &subcurve);
+ subcurve.subdivide((t1-t0)/(1-t0), this, 0);
+ }
+ }
+}
+
+
+void Bezier::reverse() {
+ swap(_points[0], _points[3]);
+ swap(_points[1], _points[2]);
+}
+
+
+DPair Bezier::pointAt (double t) const {
+ const double s = 1-t;
+ return _points[0]*s*s*s + _points[1]*3.0*s*s*t + _points[2]*3.0*s*t*t + _points[3]*t*t*t;
+}
+
+
+/** Splits the curve at t into two sub-curves. */
+void Bezier::subdivide (double t, Bezier *bezier1, Bezier *bezier2) const {
+ const double s = 1-t;
+ DPair p01 = _points[0]*s + _points[1]*t;
+ DPair p12 = _points[1]*s + _points[2]*t;
+ DPair p23 = _points[2]*s + _points[3]*t;
+ DPair p012 = p01*s + p12*t;
+ DPair p123 = p12*s + p23*t;
+ DPair p0123 = p012*s + p123*t;
+ if (bezier1) {
+ bezier1->_points[0] = _points[0];
+ bezier1->_points[1] = p01;
+ bezier1->_points[2] = p012;
+ bezier1->_points[3] = p0123;
+ }
+ if (bezier2) {
+ bezier2->_points[0] = p0123;
+ bezier2->_points[1] = p123;
+ bezier2->_points[2] = p23;
+ bezier2->_points[3] = _points[3];
+ }
+}
+
+
+/** Approximates the current Bézier curve by a sequence of line segments.
+ * This is done by subdividing the curve several times using De Casteljau's algorithm.
+ * If a sub-curve is almost flat, i.e. \f$\sum\limits_{k=0}^2 |p_{k+1}-p_k| - |p_3-p_0| < \delta\f$,
+ * the curve is not further subdivided.
+ * @param[in] delta threshold where to stop further subdivisions (see description above)
+ * @param[out] p the resulting sequence of points defining the start/end points of the line segments
+ * @param[out] t corresponding curve parameters of the approximated points p: \f$ b(t_i)=p_i \f$
+ * @return number of points in vector p */
+int Bezier::approximate (double delta, std::vector<DPair> &p, vector<double> *t) const {
+ p.push_back(_points[0]);
+ if (t)
+ t->push_back(0);
+ return approximate(delta, 0, 1, p, t);
+}
+
+
+int Bezier::approximate (double delta, double t0, double t1, vector<DPair> &p, vector<double> *t) const {
+ // compute distance of adjacent control points
+ const double l01 = (_points[1]-_points[0]).length();
+ const double l12 = (_points[2]-_points[1]).length();
+ const double l23 = (_points[3]-_points[2]).length();
+ const double l03 = (_points[3]-_points[0]).length();
+ if (l01+l12+l23-l03 < delta) { // is curve flat enough?
+ p.push_back(_points[3]); // => store endpoint
+ if (t)
+ t->push_back(t1);
+ }
+ else {
+ // subdivide curve at b(0.5) and approximate the resulting parts separately
+ Bezier b1, b2;
+ subdivide(0.5, &b1, &b2);
+ double tmid = (t0+t1)/2;
+ b1.approximate(delta, t0, tmid, p, t);
+ b2.approximate(delta, tmid, t1, p, t);
+ }
+ return p.size();
+}
+
+
+static inline double signed_area (const DPair &p1, const DPair &p2, const DPair &p3) {
+ return (p2.x()-p1.x())*(p3.y()-p1.y()) - (p3.x()-p1.x())*(p2.y()-p1.y());
+}
+
+
+static inline double dot_prod (const DPair &p1, const DPair &p2) {
+ return p1.x()*p2.x() + p1.y()*p2.y();
+}
+
+
+static bool between (const DPair &p1, const DPair &p2, const DPair &p3, double delta) {
+ if (fabs(signed_area(p1, p2, p3)) < delta) {
+ double dotp = dot_prod(p2-p1, p3-p1);
+ return dotp > 0 && dotp < dot_prod(p2-p1, p2-p1);
+ }
+ return false;
+}
+
+
+static inline bool near (const DPair &p1, const DPair &p2, double delta) {
+ DPair diff = p2-p1;
+ return fabs(diff.x()) < delta && fabs(diff.y()) < delta;
+}
+
+
+int Bezier::reduceDegree (double delta, vector<DPair> &p) const {
+ if (near(_points[0], _points[1], delta) && near(_points[0], _points[2], delta) && near(_points[0], _points[3], delta))
+ p.push_back(_points[0]);
+ else if (between(_points[0], _points[1], _points[3], delta) && between(_points[0], _points[2], _points[3], delta)) {
+ p.push_back(_points[1]);
+ p.push_back(_points[3]);
+ }
+ else if (near((_points[1]-_points[0])*1.5+_points[0], (_points[2]-_points[3])*1.5+_points[3], delta)) {
+ p.push_back(_points[0]);
+ p.push_back((_points[1]-_points[0])*1.5 + _points[0]);
+ p.push_back(_points[3]);
+ }
+ else {
+ for (int i=0; i < 4; i++)
+ p.push_back(p[i]);
+ }
+ return p.size()-1;
+}