| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /** | ||
| 2 | * \file | ||
| 3 | * \brief Symmetric power basis 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-2009 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_SBASIS_CURVE_H | ||
| 37 | #define LIB2GEOM_SEEN_SBASIS_CURVE_H | ||
| 38 | |||
| 39 | #include <2geom/curve.h> | ||
| 40 | #include <2geom/exception.h> | ||
| 41 | #include <2geom/nearest-time.h> | ||
| 42 | #include <2geom/sbasis-geometric.h> | ||
| 43 | #include <2geom/transforms.h> | ||
| 44 | |||
| 45 | namespace Geom | ||
| 46 | { | ||
| 47 | |||
| 48 | /** @brief Symmetric power basis curve. | ||
| 49 | * | ||
| 50 | * Symmetric power basis (S-basis for short) polynomials are a versatile numeric | ||
| 51 | * representation of arbitrary continuous curves. They are the main representation of curves | ||
| 52 | * in 2Geom. | ||
| 53 | * | ||
| 54 | * S-basis is defined for odd degrees and composed of the following polynomials: | ||
| 55 | * \f{align*}{ | ||
| 56 | P_k^0(t) &= t^k (1-t)^{k+1} \\ | ||
| 57 | P_k^1(t) &= t^{k+1} (1-t)^k \f} | ||
| 58 | * This can be understood more easily with the help of the chart below. Each square | ||
| 59 | * represents a product of a specific number of \f$t\f$ and \f$(1-t)\f$ terms. Red dots | ||
| 60 | * are the canonical (monomial) basis, the green dots are the Bezier basis, and the blue | ||
| 61 | * dots are the S-basis, all of them of degree 7. | ||
| 62 | * | ||
| 63 | * @image html sbasis.png "Illustration of the monomial, Bezier and symmetric power bases" | ||
| 64 | * | ||
| 65 | * The S-Basis has several important properties: | ||
| 66 | * - S-basis polynomials are closed under multiplication. | ||
| 67 | * - Evaluation is fast, using a modified Horner scheme. | ||
| 68 | * - Degree change is as trivial as in the monomial basis. To elevate, just add extra | ||
| 69 | * zero coefficients. To reduce the degree, truncate the terms in the highest powers. | ||
| 70 | * Compare this with Bezier curves, where degree change is complicated. | ||
| 71 | * - Conversion between S-basis and Bezier basis is numerically stable. | ||
| 72 | * | ||
| 73 | * More in-depth information can be found in the following paper: | ||
| 74 | * J Sanchez-Reyes, "The symmetric analogue of the polynomial power basis". | ||
| 75 | * ACM Transactions on Graphics, Vol. 16, No. 3, July 1997, pages 319--357. | ||
| 76 | * http://portal.acm.org/citation.cfm?id=256162 | ||
| 77 | * | ||
| 78 | * @ingroup Curves | ||
| 79 | */ | ||
| 80 | class SBasisCurve : public Curve { | ||
| 81 | private: | ||
| 82 | D2<SBasis> inner; | ||
| 83 | |||
| 84 | public: | ||
| 85 | ✗ | explicit SBasisCurve(D2<SBasis> const &sb) : inner(sb) {} | |
| 86 | explicit SBasisCurve(Curve const &other) : inner(other.toSBasis()) {} | ||
| 87 | |||
| 88 | ✗ | Curve *duplicate() const override { return new SBasisCurve(*this); } | |
| 89 | ✗ | Point initialPoint() const override { return inner.at0(); } | |
| 90 | ✗ | Point finalPoint() const override { return inner.at1(); } | |
| 91 | ✗ | bool isDegenerate() const override { return inner.isConstant(0); } | |
| 92 | ✗ | bool isLineSegment() const override { return inner[X].size() == 1; } | |
| 93 | ✗ | Point pointAt(Coord t) const override { return inner.valueAt(t); } | |
| 94 | ✗ | std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const override { | |
| 95 | ✗ | return inner.valueAndDerivatives(t, n); | |
| 96 | } | ||
| 97 | ✗ | Coord valueAt(Coord t, Dim2 d) const override { return inner[d].valueAt(t); } | |
| 98 | ✗ | void setInitial(Point const &v) override { | |
| 99 | ✗ | for (unsigned d = 0; d < 2; d++) { inner[d][0][0] = v[d]; } | |
| 100 | ✗ | } | |
| 101 | ✗ | void setFinal(Point const &v) override { | |
| 102 | ✗ | for (unsigned d = 0; d < 2; d++) { inner[d][0][1] = v[d]; } | |
| 103 | ✗ | } | |
| 104 | ✗ | Rect boundsFast() const override { return *bounds_fast(inner); } | |
| 105 | ✗ | Rect boundsExact() const override { return *bounds_exact(inner); } | |
| 106 | ✗ | void expandToTransformed(Rect &bbox, Affine const &transform) const override { | |
| 107 | ✗ | bbox |= bounds_exact(inner * transform); | |
| 108 | ✗ | } | |
| 109 | ✗ | OptRect boundsLocal(OptInterval const &i, unsigned deg) const override { | |
| 110 | ✗ | return bounds_local(inner, i, deg); | |
| 111 | } | ||
| 112 | ✗ | std::vector<Coord> roots(Coord v, Dim2 d) const override { return Geom::roots(inner[d] - v); } | |
| 113 | ✗ | Coord nearestTime( Point const& p, Coord from = 0, Coord to = 1 ) const override { | |
| 114 | ✗ | return nearest_time(p, inner, from, to); | |
| 115 | } | ||
| 116 | ✗ | std::vector<Coord> allNearestTimes( Point const& p, Coord from = 0, | |
| 117 | Coord to = 1 ) const override | ||
| 118 | { | ||
| 119 | ✗ | return all_nearest_times(p, inner, from, to); | |
| 120 | } | ||
| 121 | ✗ | Coord length(Coord tolerance) const override { return ::Geom::length(inner, tolerance); } | |
| 122 | ✗ | Curve *portion(Coord f, Coord t) const override { | |
| 123 | ✗ | return new SBasisCurve(Geom::portion(inner, f, t)); | |
| 124 | } | ||
| 125 | |||
| 126 | using Curve::operator*=; | ||
| 127 | ✗ | void operator*=(Affine const &m) override { inner = inner * m; } | |
| 128 | |||
| 129 | ✗ | Curve *derivative() const override { | |
| 130 | ✗ | return new SBasisCurve(Geom::derivative(inner)); | |
| 131 | } | ||
| 132 | ✗ | D2<SBasis> toSBasis() const override { return inner; } | |
| 133 | ✗ | bool isNear(Curve const &/*c*/, Coord /*eps*/) const override { | |
| 134 | ✗ | THROW_NOTIMPLEMENTED(); | |
| 135 | return false; | ||
| 136 | } | ||
| 137 | ✗ | int degreesOfFreedom() const override { | |
| 138 | ✗ | return inner[0].degreesOfFreedom() + inner[1].degreesOfFreedom(); | |
| 139 | } | ||
| 140 | |||
| 141 | protected: | ||
| 142 | ✗ | bool _equalTo(Curve const &c) const override { | |
| 143 | ✗ | if (this == &c) return true; | |
| 144 | ✗ | auto other = dynamic_cast<SBasisCurve const *>(&c); | |
| 145 | ✗ | if (!other) return false; | |
| 146 | ✗ | return inner == other->inner; | |
| 147 | } | ||
| 148 | }; | ||
| 149 | |||
| 150 | } // end namespace Geom | ||
| 151 | |||
| 152 | #endif // LIB2GEOM_SEEN_SBASIS_CURVE_H | ||
| 153 | |||
| 154 | /* | ||
| 155 | Local Variables: | ||
| 156 | mode:c++ | ||
| 157 | c-file-style:"stroustrup" | ||
| 158 | c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) | ||
| 159 | indent-tabs-mode:nil | ||
| 160 | fill-column:99 | ||
| 161 | End: | ||
| 162 | */ | ||
| 163 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : | ||
| 164 |