summaryrefslogtreecommitdiff
path: root/dviware/dvisvgm/src/EllipticalArc.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'dviware/dvisvgm/src/EllipticalArc.cpp')
-rw-r--r--dviware/dvisvgm/src/EllipticalArc.cpp260
1 files changed, 260 insertions, 0 deletions
diff --git a/dviware/dvisvgm/src/EllipticalArc.cpp b/dviware/dvisvgm/src/EllipticalArc.cpp
new file mode 100644
index 0000000000..b820af0052
--- /dev/null
+++ b/dviware/dvisvgm/src/EllipticalArc.cpp
@@ -0,0 +1,260 @@
+/*************************************************************************
+** EllipticalArc.cpp **
+** **
+** This file is part of dvisvgm -- a fast DVI to SVG converter **
+** Copyright (C) 2005-2019 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 <cmath>
+#include "EllipticalArc.hpp"
+#include "utility.hpp"
+
+using namespace std;
+
+
+/** Constructs an elliptical arc from end point parameterization.
+ * @param[in] start start point of arc
+ * @param[in] rx length of semi-major axis
+ * @param[in] ry length of semi-minor axis
+ * @param[in] angle rotation of ellipse around its center (in radians)
+ * @param[in] laf if true, choose the larger arc between start and end point
+ * @param[in] sweep if true, arc is drawn in the direction of increasing angles
+ * @param[in] end end point of the arc */
+EllipticalArc::EllipticalArc (const DPair &start, double rx, double ry, double angle, bool laf, bool sweep, const DPair &end)
+ : _rx(abs(rx)), _ry(abs(ry)), _rotationAngle(math::normalize_angle(angle, math::PI)),
+ _largeArc(laf), _sweepPositive(sweep), _startPoint(start), _endPoint(end)
+{
+ if (!isStraightLine()) {
+ // fix out-of-range radii according to section F.6.6.3 in
+ // https://www.w3.org/TR/SVG/implnote.html#ArcCorrectionOutOfRangeRadii
+ double c = cos(_rotationAngle);
+ double s = sin(_rotationAngle);
+ DPair p = (_startPoint-_endPoint)/2.0;
+ p = DPair(c*p.x()+s*p.y(), c*p.y()-s*p.x());
+ double lambda = (p.x()*p.x())/(_rx*_rx) + (p.y()*p.y())/(_ry*_ry);
+ if (lambda > 1) {
+ lambda = sqrt(lambda);
+ _rx *= lambda;
+ _ry *= lambda;
+ }
+ }
+}
+
+
+/** Constructs an elliptical arc from center parameterization
+ * @param[in] center absolute coordinates of the center of the ellipse
+ * @param[in] rx length of semi-major axis
+ * @param[in] ry length of semi-minor axis
+ * @param[in] rot rotation of ellipse around its center (in radians)
+ * @param[in] startAngle angle between major axis and vector from center to start point
+ * @param[in] deltaAngle angle between the vectors from center to start and end point, respectively */
+EllipticalArc::EllipticalArc (const DPair &center, double rx, double ry, double rot, double startAngle, double deltaAngle)
+ : _rx(rx), _ry(ry), _rotationAngle(math::normalize_angle(rot, math::TWO_PI)),
+ _largeArc(abs(deltaAngle) > math::PI), _sweepPositive(deltaAngle > 0)
+{
+ // https://www.w3.org/TR/SVG/implnote.html#ArcConversionCenterToEndpoint
+ double c = cos(_rotationAngle);
+ double s = sin(_rotationAngle);
+ double c1 = cos(startAngle);
+ double s1 = sin(startAngle);
+ double c2 = cos(startAngle+deltaAngle);
+ double s2 = sin(startAngle+deltaAngle);
+ _startPoint = DPair(c*rx*c1*c - s*ry*s1, s*rx*c1 + c*ry*s1) + center;
+ _endPoint = DPair(c*rx*c2*c - s*ry*s2, s*rx*c2 + c*ry*s2) + center;
+}
+
+
+/** Returns the angle between (1, 0) and a given vector.
+ * The angle is normalized to the range [0, 2pi). */
+static inline double angle (const DPair &p) {
+ return math::normalize_0_2pi(atan2(p.y(), p.x()));
+}
+
+
+/** Computes the center parameterization of the arc. */
+EllipticalArc::CenterParams EllipticalArc::getCenterParams () const {
+ EllipticalArc::CenterParams params;
+ if (isStraightLine()) {
+ params.center = (_endPoint-_startPoint)/2.0;
+ params.startAngle = params.deltaAngle = 0;
+ }
+ else {
+ // https://www.w3.org/TR/SVG/implnote.html#ArcConversionEndpointToCenter
+ double c = cos(_rotationAngle);
+ double s = sin(_rotationAngle);
+ DPair p = (_startPoint-_endPoint)/2.0;
+ p = DPair(c*p.x()+s*p.y(), c*p.y()-s*p.x());
+ double rx2 = _rx*_rx, ry2 = _ry*_ry;
+ double px2 = p.x()*p.x(), py2 = p.y()*p.y();
+ double radicand = rx2*ry2 - rx2*py2 - ry2*px2;
+ if (radicand < 0) // should not happen if out-of-range radii were fixed correctly
+ radicand = 0;
+ else
+ radicand /= rx2*py2 + ry2*px2;
+ double root = sqrt(radicand) * (_largeArc == _sweepPositive ? -1 : 1);
+ DPair cp(root*p.y()*_rx/_ry, -root*p.x()*_ry/_rx);
+ DPair mid = (_startPoint+_endPoint)/2.0;
+ params.center = DPair(c*cp.x() - s*cp.y() + mid.x(), s*cp.x() + c*cp.y() + mid.y());
+ DPair q1((p.x() - cp.x())/_rx, (p.y() - cp.y())/_ry);
+ DPair q2(-(p.x() + cp.x())/_rx, -(p.y() + cp.y())/_ry);
+ params.startAngle = angle(q1);
+ params.deltaAngle = angle(q2) - params.startAngle;
+ if (_sweepPositive && params.deltaAngle < 0)
+ params.deltaAngle += math::TWO_PI;
+ else if (!_sweepPositive && params.deltaAngle > 0)
+ params.deltaAngle -= math::TWO_PI;
+ }
+ return params;
+}
+
+
+/** Applies the affine transformation described by a given matrix to the arc. */
+void EllipticalArc::transform (const Matrix &matrix) {
+ double c = cos(_rotationAngle);
+ double s = sin(_rotationAngle);
+ Matrix ellipse({_rx*c, -_ry*s, 0, _rx*s, _ry*c}); // E := rotate(xrot)*scale(rx, ry)
+ ellipse.lmultiply(matrix); // E':= M*E
+ // Compute the singular value decomposition of the transformed ellipse shape:
+ // E' = rotate(phi)*scale(sx, sy)*rotate(theta)
+ // The initial, right-hand rotation can be ignored because it rotates the unit circle
+ // around the origin, i.e. rotate(theta) maps the circle to itself.
+ // The signs of sx and sy don't matter either. They just flip the yet unrotated
+ // ellipse on the x- and/or y-axis. Thus, |sx| and |sy| are the new radii,
+ // and phi the new rotation angle.
+ auto vec = math::svd({{ellipse.get(0,0), ellipse.get(0,1)}, {ellipse.get(1,0), ellipse.get(1,1)}});
+ if (std::abs(vec[1]-vec[2]) < 1e-7) { // circle?
+ _rx = _ry = vec[1]; // always >= 0
+ _rotationAngle = 0;
+ }
+ else {
+ _rx = vec[1]; // always >= 0
+ _ry = abs(vec[2]); // ensure >= 0
+ _rotationAngle = math::normalize_angle(vec[0], math::HALF_PI);
+ }
+ // change drawing direction (clockwise vs. counter-clockwise) if 'matrix'
+ // flipped the ellipse horizontally or vertically but not both
+ if ((matrix.get(0, 0) < 0) != (matrix.get(1, 1) < 0))
+ _sweepPositive = !_sweepPositive;
+ _startPoint = matrix * _startPoint;
+ _endPoint = matrix * _endPoint;
+}
+
+
+/** Approximates an arc of the unit circle by a single cubic Bézier curve.
+ * @param[in] phi start angle of the arc in radians
+ * @param[in] delta length of the arc */
+static Bezier approx_unit_arc (double phi, double delta) {
+ double c = 0.551915024494; // see http://spencermortensen.com/articles/bezier-circle
+ if (abs(delta + math::HALF_PI) < 1e-7)
+ c = -c;
+ else
+ c = 4.0/3*tan(delta/4);
+ DPair p1(cos(phi), sin(phi));
+ DPair p4(cos(phi+delta), sin(phi+delta));
+ DPair p2(p1.x()-c*p1.y(), p1.y()+c*p1.x());
+ DPair p3(p4.x()+c*p4.y(), p4.y()-c*p4.x());
+ return Bezier(p1, p2, p3, p4);
+}
+
+
+/** Approximates the arc by a sequence of cubic Bézier curves. */
+vector<Bezier> EllipticalArc::approximate () const {
+ vector<Bezier> beziers;
+ if (_startPoint != _endPoint) {
+ if (isStraightLine()) {
+ DPair dir = (_endPoint - _startPoint);
+ dir /= dir.length()/3.0;
+ beziers.emplace_back(Bezier(_startPoint, _startPoint+dir, _endPoint-dir, _endPoint));
+ }
+ else {
+ CenterParams cparams = getCenterParams();
+ int numCurves = ceil(cparams.deltaAngle/math::HALF_PI);
+ double remainder = abs(fmod(cparams.deltaAngle, math::HALF_PI));
+ if (remainder < 1e-7)
+ numCurves--;
+ else if (math::HALF_PI-remainder < 1e-7)
+ numCurves++;
+ if (numCurves > 0) {
+ double c = cos(_rotationAngle);
+ double s = sin(_rotationAngle);
+ Matrix ellipse = {_rx*c, -_ry*s, cparams.center.x(), _rx*s, _ry*c, cparams.center.y()};
+ double angle = cparams.startAngle;
+ double diff = cparams.deltaAngle/numCurves;
+ while (numCurves-- > 0) {
+ beziers.emplace_back(approx_unit_arc(angle, diff).transform(ellipse));
+ angle += diff;
+ }
+ }
+ }
+ }
+ return beziers;
+}
+
+
+static inline bool is_angle_between (double t, double angle1, double angle2) {
+ if (angle1 < angle2)
+ return angle1 < t && t < angle2;
+ return angle2 > t || t > angle1;
+}
+
+
+/** Returns the tight bounding box of the arc. */
+BoundingBox EllipticalArc::getBBox () const {
+ BoundingBox bbox;
+ bbox.embed(_startPoint);
+ bbox.embed(_endPoint);
+ if (!isStraightLine()) {
+ // compute extremes of ellipse centered at the origin
+ double c = cos(_rotationAngle);
+ double s = sin(_rotationAngle);
+ double tx1 = math::normalize_0_2pi(-atan2(_ry*s, _rx*c)); // position of vertical tangent, d/dt E(tx1)=(0, y)
+ double tx2 = math::normalize_0_2pi(math::PI+tx1); // position of second vertical tangent
+ double ct = cos(tx1);
+ double st = sin(tx1);
+ DPair pv1(_rx*c*ct - _ry*s*st, _rx*s*ct + _ry*c*st); // E(tx1), 1st point on ellipse with vertical tangent
+ DPair pv2 = -pv1; // E(tx2), 2nd point on ellipse with vertical tangent
+
+ double ty1 = math::normalize_0_2pi(atan2(_ry*c, _rx*s)); // position of horizontal tangent, d/dt E(ty1)=(x, 0)
+ double ty2 = math::normalize_0_2pi(math::PI+ty1); // position of second horizontal tangent
+ ct = cos(ty1);
+ st = sin(ty1);
+ DPair ph1(_rx*c*ct - _ry*s*st, _rx*s*ct + _ry*c*st); // E(ty1), 1st point on ellipse with horizontal tangent
+ DPair ph2 = -ph1; // E(ty2), 2nd point on ellipse with horizontal tangent
+
+ // translate extreme points to actual coordinates
+ CenterParams cparams = getCenterParams();
+ pv1 += cparams.center;
+ pv2 += cparams.center;
+ ph1 += cparams.center;
+ ph2 += cparams.center;
+
+ double angle1 = cparams.startAngle;
+ double angle2 = math::normalize_0_2pi(angle1+cparams.deltaAngle);
+ if (!_sweepPositive)
+ swap(angle1, angle2);
+
+ // only consider extreme points located on the arc
+ if (is_angle_between(tx1, angle1, angle2))
+ bbox.embed(pv1);
+ if (is_angle_between(tx2, angle1, angle2))
+ bbox.embed(pv2);
+ if (is_angle_between(ty1, angle1, angle2))
+ bbox.embed(ph1);
+ if (is_angle_between(ty2, angle1, angle2))
+ bbox.embed(ph2);
+ }
+ return bbox;
+}