d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen * \brief Bezier curve
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen * MenTaLguY <mental@rydia.net>
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen * Marco Cecchetti <mrcekets at gmail.com>
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen * Krzysztof Kosiński <tweenk.pl@gmail.com>
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * Copyright 2007-2011 Authors
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * This library is free software; you can redistribute it and/or
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * modify it either under the terms of the GNU Lesser General Public
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * License version 2.1 as published by the Free Software Foundation
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * (the "LGPL") or, at your option, under the terms of the Mozilla
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * Public License Version 1.1 (the "MPL"). If you do not alter this
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * notice, a recipient may use your version of this file under either
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * the MPL or the LGPL.
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * You should have received a copy of the LGPL along with this library
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * in the file COPYING-LGPL-2.1; if not, write to the Free Software
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * You should have received a copy of the MPL along with this library
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * in the file COPYING-MPL-1.1
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * The contents of this file are subject to the Mozilla Public License
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * Version 1.1 (the "License"); you may not use this file except in
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * compliance with the License. You may obtain a copy of the License at
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * OF ANY KIND, either express or implied. See the LGPL or the MPL for
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti * the specific language governing rights and limitations.
8001ba81cb851b38d86650a2fef5817facffb763johanengelen#include <2geom/sbasis-curve.h> // for non-native winding method
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński BezierCurve(Bezier const &x, Bezier const &y) : inner(x, y) {}
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński BezierCurve(std::vector<Point> const &pts);
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński explicit BezierCurve(D2<Bezier> const &b) : inner(b) {}
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen /// @name Access and modify control points
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen /** @brief Get the order of the Bezier curve.
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen * A Bezier curve has order() + 1 control points. */
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen unsigned order() const { return inner[X].order(); }
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński /** @brief Get the number of control points. */
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński unsigned size() const { return inner[X].order() + 1; }
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński /** @brief Access control points of the curve.
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński * @param ix The (zero-based) index of the control point. Note that the caller is responsible for checking that this value is <= order().
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński * @return The control point. No-reference return, use setPoint() to modify control points. */
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Point controlPoint(unsigned ix) const { return Point(inner[X][ix], inner[Y][ix]); }
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński Point operator[](unsigned ix) const { return Point(inner[X][ix], inner[Y][ix]); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen /** @brief Get the control points.
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen * @return Vector with order() + 1 control points. */
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński std::vector<Point> controlPoints() const { return bezier_points(inner); }
00f9ca0b3aa57e09f3c3f3632c5427fc03499df5Krzysztof Kosiński D2<Bezier> const &fragment() const { return inner; }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen /** @brief Modify a control point.
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen * @param ix The zero-based index of the point to modify. Note that the caller is responsible for checking that this value is <= order().
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen * @param v The new value of the point */
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński void setPoint(unsigned ix, Point const &v) {
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński /** @brief Set new control points.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * @param ps Vector which must contain order() + 1 points.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * Note that the caller is responsible for checking the size of this vector.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * @throws LogicalError Thrown when the size of the vector does not match the order. */
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen virtual void setPoints(std::vector<Point> const &ps) {
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen // must be virtual, because HLineSegment will need to redefine it
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen THROW_LOGICALERROR("BezierCurve::setPoints: incorrect number of points in vector");
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen for(unsigned i = 0; i <= order(); i++) {
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński /// @name Construct a Bezier curve with runtime-determined order.
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński /** @brief Construct a curve from a vector of control points.
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński * This will construct the appropriate specialization of BezierCurve (i.e. LineSegment,
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński * QuadraticBezier or Cubic Bezier) if the number of control points in the passed vector
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński * does not exceed 4. */
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński static BezierCurve *create(std::vector<Point> const &pts);
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen // implementation of virtual methods goes here
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen virtual Point initialPoint() const { return inner.at0(); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen virtual Point finalPoint() const { return inner.at1(); }
00f9ca0b3aa57e09f3c3f3632c5427fc03499df5Krzysztof Kosiński virtual bool isLineSegment() const { return size() == 2; }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen virtual void setInitial(Point const &v) { setPoint(0, v); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen virtual void setFinal(Point const &v) { setPoint(order(), v); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen virtual Rect boundsFast() const { return *bounds_fast(inner); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen virtual Rect boundsExact() const { return *bounds_exact(inner); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen virtual OptRect boundsLocal(OptInterval const &i, unsigned deg) const {
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen if (!i) return OptRect();
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen if(i->min() == 0 && i->max() == 1) return boundsFast();
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen // TODO: UUUUUUGGGLLY
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen if(deg == 1 && order() > 1) return OptRect(bounds_local(Geom::derivative(inner[X]), i),
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński virtual Curve *portion(Coord f, Coord t) const {
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński return new BezierCurve(Geom::portion(inner, f, t));
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński return new BezierCurve(Geom::reverse(inner));
e4369b05aaa20df73a37f4d319ce456865cc74f3Krzysztof Kosiński virtual void operator*=(Translate const &tr) {
e4369b05aaa20df73a37f4d319ce456865cc74f3Krzysztof Kosiński for (unsigned i = 0; i < size(); ++i) {
e4369b05aaa20df73a37f4d319ce456865cc74f3Krzysztof Kosiński virtual void operator*=(Scale const &s) {
e4369b05aaa20df73a37f4d319ce456865cc74f3Krzysztof Kosiński for (unsigned i = 0; i < size(); ++i) {
e4369b05aaa20df73a37f4d319ce456865cc74f3Krzysztof Kosiński inner[X][i] *= s[X];
e4369b05aaa20df73a37f4d319ce456865cc74f3Krzysztof Kosiński inner[Y][i] *= s[Y];
e4369b05aaa20df73a37f4d319ce456865cc74f3Krzysztof Kosiński virtual void operator*=(Affine const &m) {
e4369b05aaa20df73a37f4d319ce456865cc74f3Krzysztof Kosiński for (unsigned i = 0; i < size(); ++i) {
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński return new BezierCurve(Geom::derivative(inner[X]), Geom::derivative(inner[Y]));
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen virtual std::vector<Coord> roots(Coord v, Dim2 d) const {
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński virtual Coord nearestTime(Point const &p, Coord from = 0, Coord to = 1) const;
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński virtual std::vector<CurveIntersection> intersect(Curve const &other, Coord eps = EPSILON) const;
00f9ca0b3aa57e09f3c3f3632c5427fc03499df5Krzysztof Kosiński virtual Point pointAt(Coord t) const { return inner.pointAt(t); }
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński virtual std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const {
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen virtual Coord valueAt(Coord t, Dim2 d) const { return inner[d].valueAt(t); }
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen virtual D2<SBasis> toSBasis() const {return inner.toSBasis(); }
a16a494f042310ee849a6f717ffea70846f1f22cKrzysztof Kosiński virtual bool isNear(Curve const &c, Coord precision) const;
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński virtual bool operator==(Curve const &c) const;
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński virtual void feed(PathSink &sink, bool) const;
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński static void assert_degree(BezierCurveN<required_degree> const *) {}
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński /// @name Construct Bezier curves
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen /** @brief Construct a Bezier curve of the specified order with all points zero. */
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński inner = D2<Bezier>(Bezier(Bezier::Order(degree)), Bezier(Bezier::Order(degree)));
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen /** @brief Construct from 2D Bezier polynomial. */
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen /** @brief Construct from two 1D Bezier polynomials of the same order. */
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen /** @brief Construct a Bezier curve from a vector of its control points. */
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen BezierCurveN(std::vector<Point> const &points) {
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen if (ord != degree) THROW_LOGICALERROR("BezierCurve<degree> does not match number of points");
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen for (unsigned d = 0; d < 2; ++d) {
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen for(unsigned i = 0; i <= ord; i++)
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen /** @brief Construct a linear segment from its endpoints. */
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen for(unsigned d = 0; d < 2; d++)
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen /** @brief Construct a quadratic Bezier curve from its control points. */
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen for(unsigned d = 0; d < 2; d++)
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen /** @brief Construct a cubic Bezier curve from its control points. */
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen BezierCurveN(Point c0, Point c1, Point c2, Point c3) {
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen for(unsigned d = 0; d < 2; d++)
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen inner[d] = Bezier(c0[d], c1[d], c2[d], c3[d]);
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen // default copy
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen // default assign
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński /** @brief Divide a Bezier curve into two curves
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * @param t Time value
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * @return Pair of Bezier curves \f$(\mathbf{D}, \mathbf{E})\f$ such that
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * \f$\mathbf{D}[ [0,1] ] = \mathbf{C}[ [0,t] ]\f$ and
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * \f$\mathbf{E}[ [0,1] ] = \mathbf{C}[ [t,1] ]\f$ */
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński std::pair<BezierCurveN, BezierCurveN> subdivide(Coord t) const {
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński std::pair<Bezier, Bezier> sx = inner[X].subdivide(t), sy = inner[Y].subdivide(t);
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen virtual Curve *portion(Coord f, Coord t) const {
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen return new BezierCurveN<1>(pointAt(f), pointAt(t));
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen return new BezierCurveN(Geom::portion(inner, f, t));
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen return new BezierCurveN<1>(finalPoint(), initialPoint());
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen return new BezierCurveN(Geom::reverse(inner));
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński virtual Coord nearestTime(Point const &p, Coord from = 0, Coord to = 1) const {
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński return BezierCurve::nearestTime(p, from, to);
00f9ca0b3aa57e09f3c3f3632c5427fc03499df5Krzysztof Kosiński virtual std::vector<CurveIntersection> intersect(Curve const &other, Coord eps = EPSILON) const {
00f9ca0b3aa57e09f3c3f3632c5427fc03499df5Krzysztof Kosiński // call super. this is implemented only to allow specializations
00f9ca0b3aa57e09f3c3f3632c5427fc03499df5Krzysztof Kosiński return BezierCurve::intersect(other, eps);
a16a494f042310ee849a6f717ffea70846f1f22cKrzysztof Kosiński virtual int winding(Point const &p) const {
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński virtual void feed(PathSink &sink, bool moveto_initial) const {
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński // call super. this is implemented only to allow specializations
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen// BezierCurveN<0> is meaningless; specialize it out
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosińskitemplate<> class BezierCurveN<0> : public BezierCurveN<1> { private: BezierCurveN();};
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński/** @brief Line segment.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * Line segments are Bezier curves of order 1. They have only two control points,
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * the starting point and the ending point.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * @ingroup Curves */
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński/** @brief Quadratic (order 2) Bezier curve.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * @ingroup Curves */
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński/** @brief Cubic (order 3) Bezier curve.
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosiński * @ingroup Curves */
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan EngelenCurve *BezierCurveN<degree>::derivative() const {
0a0c1d89932c9d33060525acb8a91069c0e6c673Johan Engelen return new BezierCurveN<degree-1>(Geom::derivative(inner[X]), Geom::derivative(inner[Y]));
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński// optimized specializations
a16a494f042310ee849a6f717ffea70846f1f22cKrzysztof Kosińskitemplate <> inline bool BezierCurveN<1>::isDegenerate() const {
a16a494f042310ee849a6f717ffea70846f1f22cKrzysztof Kosiński return inner[X][0] == inner[X][1] && inner[Y][0] == inner[Y][1];
00f9ca0b3aa57e09f3c3f3632c5427fc03499df5Krzysztof Kosińskitemplate <> inline bool BezierCurveN<1>::isLineSegment() const { return true; }
40742313779ee5e43be93a9191f1c86412cf183bKrzysztof Kosińskitemplate <> Curve *BezierCurveN<1>::derivative() const;
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskitemplate <> Coord BezierCurveN<1>::nearestTime(Point const &, Coord, Coord) const;
00f9ca0b3aa57e09f3c3f3632c5427fc03499df5Krzysztof Kosińskitemplate <> std::vector<CurveIntersection> BezierCurveN<1>::intersect(Curve const &, Coord) const;
a16a494f042310ee849a6f717ffea70846f1f22cKrzysztof Kosińskitemplate <> int BezierCurveN<1>::winding(Point const &) const;
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskitemplate <> void BezierCurveN<1>::feed(PathSink &sink, bool moveto_initial) const;
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskitemplate <> void BezierCurveN<2>::feed(PathSink &sink, bool moveto_initial) const;
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosińskitemplate <> void BezierCurveN<3>::feed(PathSink &sink, bool moveto_initial) const;
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engeleninline Point middle_point(LineSegment const& _segment) {
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen return ( _segment.initialPoint() + _segment.finalPoint() ) / 2;
d37634d73670180f99a3e0ea583621373d90ec4fJohan Engelen return distance(seg.initialPoint(), seg.finalPoint());
d37634d73670180f99a3e0ea583621373d90ec4fJohan EngelenCoord bezier_length(std::vector<Point> const &points, Coord tolerance = 0.01);
d37634d73670180f99a3e0ea583621373d90ec4fJohan EngelenCoord bezier_length(Point p0, Point p1, Point p2, Coord tolerance = 0.01);
d37634d73670180f99a3e0ea583621373d90ec4fJohan EngelenCoord bezier_length(Point p0, Point p1, Point p2, Point p3, Coord tolerance = 0.01);
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti} // end namespace Geom
76addc201c409e81eaaa73fe27cc0f79c4db097cKrzysztof Kosiński#endif // LIB2GEOM_SEEN_BEZIER_CURVE_H
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti Local Variables:
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti c-file-style:"stroustrup"
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti indent-tabs-mode:nil
6e16a663ee96cd1329e48518138efb415046d9f6mcecchetti fill-column:99
a4030d5ca449e7e384bc699cd249ee704faaeab0Chris Morgan// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :