| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /** | ||
| 2 | * \file | ||
| 3 | * \brief Bezier curve | ||
| 4 | *//* | ||
| 5 | * Authors: | ||
| 6 | * MenTaLguY <mental@rydia.net> | ||
| 7 | * Marco Cecchetti <mrcekets at gmail.com> | ||
| 8 | * Krzysztof Kosiński <tweenk.pl@gmail.com> | ||
| 9 | * | ||
| 10 | * Copyright 2007-2011 Authors | ||
| 11 | * | ||
| 12 | * This library is free software; you can redistribute it and/or | ||
| 13 | * modify it either under the terms of the GNU Lesser General Public | ||
| 14 | * License version 2.1 as published by the Free Software Foundation | ||
| 15 | * (the "LGPL") or, at your option, under the terms of the Mozilla | ||
| 16 | * Public License Version 1.1 (the "MPL"). If you do not alter this | ||
| 17 | * notice, a recipient may use your version of this file under either | ||
| 18 | * the MPL or the LGPL. | ||
| 19 | * | ||
| 20 | * You should have received a copy of the LGPL along with this library | ||
| 21 | * in the file COPYING-LGPL-2.1; if not, write to the Free Software | ||
| 22 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | ||
| 23 | * You should have received a copy of the MPL along with this library | ||
| 24 | * in the file COPYING-MPL-1.1 | ||
| 25 | * | ||
| 26 | * The contents of this file are subject to the Mozilla Public License | ||
| 27 | * Version 1.1 (the "License"); you may not use this file except in | ||
| 28 | * compliance with the License. You may obtain a copy of the License at | ||
| 29 | * http://www.mozilla.org/MPL/ | ||
| 30 | * | ||
| 31 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY | ||
| 32 | * OF ANY KIND, either express or implied. See the LGPL or the MPL for | ||
| 33 | * the specific language governing rights and limitations. | ||
| 34 | */ | ||
| 35 | |||
| 36 | #ifndef LIB2GEOM_SEEN_BEZIER_CURVE_H | ||
| 37 | #define LIB2GEOM_SEEN_BEZIER_CURVE_H | ||
| 38 | |||
| 39 | #include <2geom/curve.h> | ||
| 40 | #include <2geom/sbasis-curve.h> // for non-native winding method | ||
| 41 | #include <2geom/bezier.h> | ||
| 42 | #include <2geom/transforms.h> | ||
| 43 | |||
| 44 | namespace Geom | ||
| 45 | { | ||
| 46 | |||
| 47 | class BezierCurve : public Curve { | ||
| 48 | protected: | ||
| 49 | D2<Bezier> inner; | ||
| 50 |
1/2✓ Branch 2 taken 1129663 times.
✗ Branch 3 not taken.
|
1129663 | BezierCurve() {} |
| 51 | ✗ | BezierCurve(Bezier const &x, Bezier const &y) : inner(x, y) {} | |
| 52 | BezierCurve(std::vector<Point> const &pts); | ||
| 53 | |||
| 54 | public: | ||
| 55 | ✗ | explicit BezierCurve(D2<Bezier> const &b) : inner(b) {} | |
| 56 | |||
| 57 | /// @name Access and modify control points | ||
| 58 | /// @{ | ||
| 59 | /** @brief Get the order of the Bezier curve. | ||
| 60 | * A Bezier curve has order() + 1 control points. */ | ||
| 61 | 46583 | unsigned order() const { return inner[X].order(); } | |
| 62 | /** @brief Get the number of control points. */ | ||
| 63 | 5574216 | unsigned size() const { return inner[X].order() + 1; } | |
| 64 | /** @brief Access control points of the curve. | ||
| 65 | * @param ix The (zero-based) index of the control point. Note that the caller is responsible for checking that this value is <= order(). | ||
| 66 | * @return The control point. No-reference return, use setPoint() to modify control points. */ | ||
| 67 | 2326724 | Point controlPoint(unsigned ix) const { return Point(inner[X][ix], inner[Y][ix]); } | |
| 68 | 889374 | Point operator[](unsigned ix) const { return Point(inner[X][ix], inner[Y][ix]); } | |
| 69 | /** @brief Get the control points. | ||
| 70 | * @return Vector with order() + 1 control points. */ | ||
| 71 | ✗ | std::vector<Point> controlPoints() const { return bezier_points(inner); } | |
| 72 | 20027 | D2<Bezier> const &fragment() const { return inner; } | |
| 73 | |||
| 74 | /** @brief Modify a control point. | ||
| 75 | * @param ix The zero-based index of the point to modify. Note that the caller is responsible for checking that this value is <= order(). | ||
| 76 | * @param v The new value of the point */ | ||
| 77 | 2693579 | void setPoint(unsigned ix, Point const &v) { | |
| 78 | 2693579 | inner[X][ix] = v[X]; | |
| 79 | 2693579 | inner[Y][ix] = v[Y]; | |
| 80 | 2693579 | } | |
| 81 | /** @brief Set new control points. | ||
| 82 | * @param ps Vector which must contain order() + 1 points. | ||
| 83 | * Note that the caller is responsible for checking the size of this vector. | ||
| 84 | * @throws LogicalError Thrown when the size of the vector does not match the order. */ | ||
| 85 | ✗ | virtual void setPoints(std::vector<Point> const &ps) { | |
| 86 | // must be virtual, because HLineSegment will need to redefine it | ||
| 87 | ✗ | if (ps.size() != order() + 1) | |
| 88 | ✗ | THROW_LOGICALERROR("BezierCurve::setPoints: incorrect number of points in vector"); | |
| 89 | ✗ | for(unsigned i = 0; i <= order(); i++) { | |
| 90 | ✗ | setPoint(i, ps[i]); | |
| 91 | } | ||
| 92 | ✗ | } | |
| 93 | /// @} | ||
| 94 | |||
| 95 | /// @name Construct a Bezier curve with runtime-determined order. | ||
| 96 | /// @{ | ||
| 97 | /** @brief Construct a curve from a vector of control points. | ||
| 98 | * This will construct the appropriate specialization of BezierCurve (i.e. LineSegment, | ||
| 99 | * QuadraticBezier or Cubic Bezier) if the number of control points in the passed vector | ||
| 100 | * does not exceed 4. */ | ||
| 101 | static BezierCurve *create(std::vector<Point> const &pts); | ||
| 102 | /// @} | ||
| 103 | |||
| 104 | // implementation of virtual methods goes here | ||
| 105 | 1002387 | Point initialPoint() const override { return inner.at0(); } | |
| 106 | 619974 | Point finalPoint() const override { return inner.at1(); } | |
| 107 | bool isDegenerate() const override; | ||
| 108 | bool isLineSegment() const override; | ||
| 109 | 408996 | void setInitial(Point const &v) override { setPoint(0, v); } | |
| 110 | 26583 | void setFinal(Point const &v) override { setPoint(order(), v); } | |
| 111 |
1/2✓ Branch 2 taken 20000 times.
✗ Branch 3 not taken.
|
20000 | Rect boundsFast() const override { return *bounds_fast(inner); } |
| 112 | ✗ | Rect boundsExact() const override { return *bounds_exact(inner); } | |
| 113 | void expandToTransformed(Rect &bbox, Affine const &transform) const override; | ||
| 114 | ✗ | OptRect boundsLocal(OptInterval const &i, unsigned deg) const override { | |
| 115 | ✗ | if (!i) return OptRect(); | |
| 116 | ✗ | if(i->min() == 0 && i->max() == 1) return boundsFast(); | |
| 117 | ✗ | if(deg == 0) return bounds_local(inner, i); | |
| 118 | // TODO: UUUUUUGGGLLY | ||
| 119 | ✗ | if(deg == 1 && order() > 1) return OptRect(bounds_local(Geom::derivative(inner[X]), i), | |
| 120 | ✗ | bounds_local(Geom::derivative(inner[Y]), i)); | |
| 121 | ✗ | return OptRect(); | |
| 122 | } | ||
| 123 | ✗ | Curve *duplicate() const override { | |
| 124 | ✗ | return new BezierCurve(*this); | |
| 125 | } | ||
| 126 | |||
| 127 | Curve *portion(Coord f, Coord t) const override; | ||
| 128 | |||
| 129 | ✗ | Curve *reverse() const override { | |
| 130 | ✗ | return new BezierCurve(Geom::reverse(inner)); | |
| 131 | } | ||
| 132 | |||
| 133 | using Curve::operator*=; | ||
| 134 | 549000 | void operator*=(Translate const &tr) override { | |
| 135 |
2/2✓ Branch 1 taken 2178000 times.
✓ Branch 2 taken 549000 times.
|
2727000 | for (unsigned i = 0; i < size(); ++i) { |
| 136 | 2178000 | inner[X][i] += tr[X]; | |
| 137 | 2178000 | inner[Y][i] += tr[Y]; | |
| 138 | } | ||
| 139 | 549000 | } | |
| 140 | ✗ | void operator*=(Scale const &s) override { | |
| 141 | ✗ | for (unsigned i = 0; i < size(); ++i) { | |
| 142 | ✗ | inner[X][i] *= s[X]; | |
| 143 | ✗ | inner[Y][i] *= s[Y]; | |
| 144 | } | ||
| 145 | ✗ | } | |
| 146 | 589000 | void operator*=(Affine const &m) override { | |
| 147 |
2/2✓ Branch 1 taken 2258000 times.
✓ Branch 2 taken 589000 times.
|
2847000 | for (unsigned i = 0; i < size(); ++i) { |
| 148 |
3/6✓ Branch 3 taken 2258000 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2258000 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 2258000 times.
✗ Branch 10 not taken.
|
2258000 | setPoint(i, controlPoint(i) * m); |
| 149 | } | ||
| 150 | 589000 | } | |
| 151 | |||
| 152 | ✗ | Curve *derivative() const override { | |
| 153 | ✗ | return new BezierCurve(Geom::derivative(inner[X]), Geom::derivative(inner[Y])); | |
| 154 | } | ||
| 155 | ✗ | int degreesOfFreedom() const override { | |
| 156 | ✗ | return 2 * (order() + 1); | |
| 157 | } | ||
| 158 | ✗ | std::vector<Coord> roots(Coord v, Dim2 d) const override { | |
| 159 | ✗ | return (inner[d] - v).roots(); | |
| 160 | } | ||
| 161 | Coord nearestTime(Point const &p, Coord from = 0, Coord to = 1) const override; | ||
| 162 | Coord length(Coord tolerance) const override; | ||
| 163 | std::vector<CurveIntersection> intersect(Curve const &other, Coord eps = EPSILON) const override; | ||
| 164 | ✗ | Point pointAt(Coord t) const override { return inner.pointAt(t); } | |
| 165 | ✗ | std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const override { | |
| 166 | ✗ | return inner.valueAndDerivatives(t, n); | |
| 167 | } | ||
| 168 | ✗ | Coord valueAt(Coord t, Dim2 d) const override { return inner[d].valueAt(t); } | |
| 169 | 216 | D2<SBasis> toSBasis() const override {return inner.toSBasis(); } | |
| 170 | bool isNear(Curve const &c, Coord precision) const override; | ||
| 171 | void feed(PathSink &sink, bool) const override; | ||
| 172 | std::vector<Coord> timesWithRadiusOfCurvature(double radius) const; | ||
| 173 | |||
| 174 | protected: | ||
| 175 | bool _equalTo(Curve const &c) const override; | ||
| 176 | }; | ||
| 177 | |||
| 178 | template <unsigned degree> | ||
| 179 | class BezierCurveN | ||
| 180 | : public BezierCurve | ||
| 181 | { | ||
| 182 | template <unsigned required_degree> | ||
| 183 | 1889926 | static void assert_degree(BezierCurveN<required_degree> const *) {} | |
| 184 | |||
| 185 | public: | ||
| 186 | /// @name Construct Bezier curves | ||
| 187 | /// @{ | ||
| 188 | /** @brief Construct a Bezier curve of the specified order with all points zero. */ | ||
| 189 | BezierCurveN() { | ||
| 190 | inner = D2<Bezier>(Bezier(Bezier::Order(degree)), Bezier(Bezier::Order(degree))); | ||
| 191 | } | ||
| 192 | |||
| 193 | /** @brief Construct from 2D Bezier polynomial. */ | ||
| 194 | 329400 | explicit BezierCurveN(D2<Bezier > const &x) { | |
| 195 |
1/2✓ Branch 1 taken 164700 times.
✗ Branch 2 not taken.
|
329400 | inner = x; |
| 196 | 329400 | } | |
| 197 | |||
| 198 | /** @brief Construct from two 1D Bezier polynomials of the same order. */ | ||
| 199 | ✗ | BezierCurveN(Bezier x, Bezier y) { | |
| 200 | ✗ | inner = D2<Bezier > (x,y); | |
| 201 | ✗ | } | |
| 202 | |||
| 203 | /** @brief Construct a Bezier curve from a vector of its control points. */ | ||
| 204 | BezierCurveN(std::vector<Point> const &points) { | ||
| 205 | unsigned ord = points.size() - 1; | ||
| 206 | if (ord != degree) THROW_LOGICALERROR("BezierCurve<degree> does not match number of points"); | ||
| 207 | for (unsigned d = 0; d < 2; ++d) { | ||
| 208 | inner[d] = Bezier(Bezier::Order(ord)); | ||
| 209 | for(unsigned i = 0; i <= ord; i++) | ||
| 210 | inner[d][i] = points[i][d]; | ||
| 211 | } | ||
| 212 | } | ||
| 213 | |||
| 214 | /** @brief Construct a linear segment from its endpoints. */ | ||
| 215 | 547513 | BezierCurveN(Point c0, Point c1) { | |
| 216 | 547513 | assert_degree<1>(this); | |
| 217 |
2/2✓ Branch 0 taken 1095026 times.
✓ Branch 1 taken 547513 times.
|
1642539 | for(unsigned d = 0; d < 2; d++) |
| 218 |
2/4✓ Branch 4 taken 1095026 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 1095026 times.
✗ Branch 9 not taken.
|
1095026 | inner[d] = Bezier(c0[d], c1[d]); |
| 219 | 547513 | } | |
| 220 | |||
| 221 | /** @brief Construct a quadratic Bezier curve from its control points. */ | ||
| 222 | ✗ | BezierCurveN(Point c0, Point c1, Point c2) { | |
| 223 | ✗ | assert_degree<2>(this); | |
| 224 | ✗ | for(unsigned d = 0; d < 2; d++) | |
| 225 | ✗ | inner[d] = Bezier(c0[d], c1[d], c2[d]); | |
| 226 | ✗ | } | |
| 227 | |||
| 228 | /** @brief Construct a cubic Bezier curve from its control points. */ | ||
| 229 | 417450 | BezierCurveN(Point c0, Point c1, Point c2, Point c3) { | |
| 230 | 417450 | assert_degree<3>(this); | |
| 231 |
2/2✓ Branch 0 taken 834900 times.
✓ Branch 1 taken 417450 times.
|
1252350 | for(unsigned d = 0; d < 2; d++) |
| 232 |
2/4✓ Branch 6 taken 834900 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 834900 times.
✗ Branch 11 not taken.
|
834900 | inner[d] = Bezier(c0[d], c1[d], c2[d], c3[d]); |
| 233 | 417450 | } | |
| 234 | |||
| 235 | // default copy | ||
| 236 | // default assign | ||
| 237 | |||
| 238 | /// @} | ||
| 239 | |||
| 240 | /** @brief Divide a Bezier curve into two curves | ||
| 241 | * @param t Time value | ||
| 242 | * @return Pair of Bezier curves \f$(\mathbf{D}, \mathbf{E})\f$ such that | ||
| 243 | * \f$\mathbf{D}[ [0,1] ] = \mathbf{C}[ [0,t] ]\f$ and | ||
| 244 | * \f$\mathbf{E}[ [0,1] ] = \mathbf{C}[ [t,1] ]\f$ */ | ||
| 245 | std::pair<BezierCurveN, BezierCurveN> subdivide(Coord t) const { | ||
| 246 | std::pair<Bezier, Bezier> sx = inner[X].subdivide(t), sy = inner[Y].subdivide(t); | ||
| 247 | return std::make_pair( | ||
| 248 | BezierCurveN(sx.first, sy.first), | ||
| 249 | BezierCurveN(sx.second, sy.second)); | ||
| 250 | } | ||
| 251 | |||
| 252 | 432 | bool isDegenerate() const override { | |
| 253 | 432 | return BezierCurve::isDegenerate(); | |
| 254 | } | ||
| 255 | |||
| 256 | ✗ | bool isLineSegment() const override { | |
| 257 | if constexpr (degree == 1) { | ||
| 258 | return true; | ||
| 259 | } else { | ||
| 260 | ✗ | return BezierCurve::isLineSegment(); | |
| 261 | } | ||
| 262 | } | ||
| 263 | |||
| 264 | 46548 | Curve *duplicate() const override { | |
| 265 |
1/4✓ Branch 2 taken 23274 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
|
46548 | return new BezierCurveN(*this); |
| 266 | } | ||
| 267 | ✗ | Curve *portion(Coord f, Coord t) const override { | |
| 268 | if (degree == 1) { | ||
| 269 | ✗ | return new BezierCurveN<1>(pointAt(f), pointAt(t)); | |
| 270 | } else { | ||
| 271 | ✗ | return new BezierCurveN(Geom::portion(inner, f, t)); | |
| 272 | } | ||
| 273 | } | ||
| 274 | 658800 | Curve *reverse() const override { | |
| 275 | if (degree == 1) { | ||
| 276 |
3/8✓ Branch 2 taken 164700 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 164700 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 164700 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
|
329400 | return new BezierCurveN<1>(finalPoint(), initialPoint()); |
| 277 | } else { | ||
| 278 |
2/6✓ Branch 3 taken 164700 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 164700 times.
✗ Branch 7 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
|
329400 | return new BezierCurveN(Geom::reverse(inner)); |
| 279 | } | ||
| 280 | } | ||
| 281 | Curve *derivative() const override; | ||
| 282 | |||
| 283 | ✗ | Coord nearestTime(Point const &p, Coord from = 0, Coord to = 1) const override { | |
| 284 | ✗ | return BezierCurve::nearestTime(p, from, to); | |
| 285 | } | ||
| 286 | std::vector<CurveIntersection> intersect(Curve const &other, Coord eps = EPSILON) const override { | ||
| 287 | // call super. this is implemented only to allow specializations | ||
| 288 | return BezierCurve::intersect(other, eps); | ||
| 289 | } | ||
| 290 | ✗ | int winding(Point const &p) const override { | |
| 291 | ✗ | return Curve::winding(p); | |
| 292 | } | ||
| 293 | void feed(PathSink &sink, bool moveto_initial) const override { | ||
| 294 | // call super. this is implemented only to allow specializations | ||
| 295 | BezierCurve::feed(sink, moveto_initial); | ||
| 296 | } | ||
| 297 | void expandToTransformed(Rect &bbox, Affine const &transform) const override { | ||
| 298 | // call super. this is implemented only to allow specializations | ||
| 299 | BezierCurve::expandToTransformed(bbox, transform); | ||
| 300 | } | ||
| 301 | }; | ||
| 302 | |||
| 303 | // BezierCurveN<0> is meaningless; specialize it out | ||
| 304 | template<> class BezierCurveN<0> : public BezierCurveN<1> { private: BezierCurveN();}; | ||
| 305 | |||
| 306 | /** @brief Line segment. | ||
| 307 | * Line segments are Bezier curves of order 1. They have only two control points, | ||
| 308 | * the starting point and the ending point. | ||
| 309 | * @ingroup Curves */ | ||
| 310 | typedef BezierCurveN<1> LineSegment; | ||
| 311 | |||
| 312 | /** @brief Quadratic (order 2) Bezier curve. | ||
| 313 | * @ingroup Curves */ | ||
| 314 | typedef BezierCurveN<2> QuadraticBezier; | ||
| 315 | |||
| 316 | /** @brief Cubic (order 3) Bezier curve. | ||
| 317 | * @ingroup Curves */ | ||
| 318 | typedef BezierCurveN<3> CubicBezier; | ||
| 319 | |||
| 320 | template <unsigned degree> | ||
| 321 | inline | ||
| 322 | ✗ | Curve *BezierCurveN<degree>::derivative() const { | |
| 323 | ✗ | return new BezierCurveN<degree-1>(Geom::derivative(inner[X]), Geom::derivative(inner[Y])); | |
| 324 | } | ||
| 325 | |||
| 326 | // optimized specializations | ||
| 327 | ✗ | template <> inline bool BezierCurveN<1>::isDegenerate() const { | |
| 328 | ✗ | return inner[X][0] == inner[X][1] && inner[Y][0] == inner[Y][1]; | |
| 329 | } | ||
| 330 | ✗ | template <> inline bool BezierCurveN<1>::isLineSegment() const { return true; } | |
| 331 | template <> Curve *BezierCurveN<1>::derivative() const; | ||
| 332 | template <> Coord BezierCurveN<1>::nearestTime(Point const &, Coord, Coord) const; | ||
| 333 | template <> std::vector<CurveIntersection> BezierCurveN<1>::intersect(Curve const &, Coord) const; | ||
| 334 | template <> std::vector<CurveIntersection> BezierCurveN<2>::intersect(Curve const &, Coord) const; | ||
| 335 | template <> std::vector<CurveIntersection> BezierCurveN<3>::intersect(Curve const &, Coord) const; | ||
| 336 | template <> int BezierCurveN<1>::winding(Point const &) const; | ||
| 337 | template <> void BezierCurveN<1>::feed(PathSink &sink, bool moveto_initial) const; | ||
| 338 | template <> void BezierCurveN<2>::feed(PathSink &sink, bool moveto_initial) const; | ||
| 339 | template <> void BezierCurveN<3>::feed(PathSink &sink, bool moveto_initial) const; | ||
| 340 | template <> void BezierCurveN<1>::expandToTransformed(Rect &bbox, Affine const &transform) const; | ||
| 341 | template <> void BezierCurveN<2>::expandToTransformed(Rect &bbox, Affine const &transform) const; | ||
| 342 | template <> void BezierCurveN<3>::expandToTransformed(Rect &bbox, Affine const &transform) const; | ||
| 343 | |||
| 344 | ✗ | inline Point middle_point(LineSegment const& _segment) { | |
| 345 | ✗ | return ( _segment.initialPoint() + _segment.finalPoint() ) / 2; | |
| 346 | } | ||
| 347 | |||
| 348 | inline Coord length(LineSegment const& seg) { | ||
| 349 | return distance(seg.initialPoint(), seg.finalPoint()); | ||
| 350 | } | ||
| 351 | |||
| 352 | Coord bezier_length(std::vector<Point> const &points, Coord tolerance = 0.01); | ||
| 353 | Coord bezier_length(Point p0, Point p1, Point p2, Coord tolerance = 0.01); | ||
| 354 | Coord bezier_length(Point p0, Point p1, Point p2, Point p3, Coord tolerance = 0.01); | ||
| 355 | |||
| 356 | } // end namespace Geom | ||
| 357 | |||
| 358 | #endif // LIB2GEOM_SEEN_BEZIER_CURVE_H | ||
| 359 | |||
| 360 | /* | ||
| 361 | Local Variables: | ||
| 362 | mode:c++ | ||
| 363 | c-file-style:"stroustrup" | ||
| 364 | c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) | ||
| 365 | indent-tabs-mode:nil | ||
| 366 | fill-column:99 | ||
| 367 | End: | ||
| 368 | */ | ||
| 369 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : | ||
| 370 |