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;
BezierCurve()50 BezierCurve() {}
BezierCurve(Bezier const & x,Bezier const & y)51 BezierCurve(Bezier const &x, Bezier const &y) : inner(x, y) {}
52 BezierCurve(std::vector<Point> const &pts);
53
54 public:
BezierCurve(D2<Bezier> const & b)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. */
order()61 unsigned order() const { return inner[X].order(); }
62 /** @brief Get the number of control points. */
size()63 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. */
controlPoint(unsigned ix)67 Point controlPoint(unsigned ix) const { return Point(inner[X][ix], inner[Y][ix]); }
68 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. */
controlPoints()71 std::vector<Point> controlPoints() const { return bezier_points(inner); }
fragment()72 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 */
setPoint(unsigned ix,Point const & v)77 void setPoint(unsigned ix, Point const &v) {
78 inner[X][ix] = v[X];
79 inner[Y][ix] = v[Y];
80 }
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. */
setPoints(std::vector<Point> const & ps)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
initialPoint()105 virtual Point initialPoint() const { return inner.at0(); }
finalPoint()106 virtual Point finalPoint() const { return inner.at1(); }
107 virtual bool isDegenerate() const;
isLineSegment()108 virtual bool isLineSegment() const { return size() == 2; }
setInitial(Point const & v)109 virtual void setInitial(Point const &v) { setPoint(0, v); }
setFinal(Point const & v)110 virtual void setFinal(Point const &v) { setPoint(order(), v); }
boundsFast()111 virtual Rect boundsFast() const { return *bounds_fast(inner); }
boundsExact()112 virtual Rect boundsExact() const { return *bounds_exact(inner); }
boundsLocal(OptInterval const & i,unsigned deg)113 virtual OptRect boundsLocal(OptInterval const &i, unsigned deg) const {
114 if (!i) return OptRect();
115 if(i->min() == 0 && i->max() == 1) return boundsFast();
116 if(deg == 0) return bounds_local(inner, i);
117 // TODO: UUUUUUGGGLLY
118 if(deg == 1 && order() > 1) return OptRect(bounds_local(Geom::derivative(inner[X]), i),
119 bounds_local(Geom::derivative(inner[Y]), i));
120 return OptRect();
121 }
duplicate()122 virtual Curve *duplicate() const {
123 return new BezierCurve(*this);
124 }
portion(Coord f,Coord t)125 virtual Curve *portion(Coord f, Coord t) const {
126 return new BezierCurve(Geom::portion(inner, f, t));
127 }
reverse()128 virtual Curve *reverse() const {
129 return new BezierCurve(Geom::reverse(inner));
130 }
131
132 using Curve::operator*=;
133 virtual void operator*=(Translate const &tr) {
134 for (unsigned i = 0; i < size(); ++i) {
135 inner[X][i] += tr[X];
136 inner[Y][i] += tr[Y];
137 }
138 }
139 virtual void operator*=(Scale const &s) {
140 for (unsigned i = 0; i < size(); ++i) {
141 inner[X][i] *= s[X];
142 inner[Y][i] *= s[Y];
143 }
144 }
145 virtual void operator*=(Affine const &m) {
146 for (unsigned i = 0; i < size(); ++i) {
147 setPoint(i, controlPoint(i) * m);
148 }
149 }
150
derivative()151 virtual Curve *derivative() const {
152 return new BezierCurve(Geom::derivative(inner[X]), Geom::derivative(inner[Y]));
153 }
degreesOfFreedom()154 virtual int degreesOfFreedom() const {
155 return 2 * (order() + 1);
156 }
roots(Coord v,Dim2 d)157 virtual std::vector<Coord> roots(Coord v, Dim2 d) const {
158 return (inner[d] - v).roots();
159 }
160 virtual Coord nearestTime(Point const &p, Coord from = 0, Coord to = 1) const;
161 virtual Coord length(Coord tolerance) const;
162 virtual std::vector<CurveIntersection> intersect(Curve const &other, Coord eps = EPSILON) const;
pointAt(Coord t)163 virtual Point pointAt(Coord t) const { return inner.pointAt(t); }
pointAndDerivatives(Coord t,unsigned n)164 virtual std::vector<Point> pointAndDerivatives(Coord t, unsigned n) const {
165 return inner.valueAndDerivatives(t, n);
166 }
valueAt(Coord t,Dim2 d)167 virtual Coord valueAt(Coord t, Dim2 d) const { return inner[d].valueAt(t); }
toSBasis()168 virtual D2<SBasis> toSBasis() const {return inner.toSBasis(); }
169 virtual bool isNear(Curve const &c, Coord precision) const;
170 virtual bool operator==(Curve const &c) const;
171 virtual void feed(PathSink &sink, bool) const;
172 };
173
174 template <unsigned degree>
175 class BezierCurveN
176 : public BezierCurve
177 {
178 template <unsigned required_degree>
assert_degree(BezierCurveN<required_degree> const *)179 static void assert_degree(BezierCurveN<required_degree> const *) {}
180
181 public:
182 /// @name Construct Bezier curves
183 /// @{
184 /** @brief Construct a Bezier curve of the specified order with all points zero. */
BezierCurveN()185 BezierCurveN() {
186 inner = D2<Bezier>(Bezier(Bezier::Order(degree)), Bezier(Bezier::Order(degree)));
187 }
188
189 /** @brief Construct from 2D Bezier polynomial. */
BezierCurveN(D2<Bezier> const & x)190 explicit BezierCurveN(D2<Bezier > const &x) {
191 inner = x;
192 }
193
194 /** @brief Construct from two 1D Bezier polynomials of the same order. */
BezierCurveN(Bezier x,Bezier y)195 BezierCurveN(Bezier x, Bezier y) {
196 inner = D2<Bezier > (x,y);
197 }
198
199 /** @brief Construct a Bezier curve from a vector of its control points. */
BezierCurveN(std::vector<Point> const & points)200 BezierCurveN(std::vector<Point> const &points) {
201 unsigned ord = points.size() - 1;
202 if (ord != degree) THROW_LOGICALERROR("BezierCurve<degree> does not match number of points");
203 for (unsigned d = 0; d < 2; ++d) {
204 inner[d] = Bezier(Bezier::Order(ord));
205 for(unsigned i = 0; i <= ord; i++)
206 inner[d][i] = points[i][d];
207 }
208 }
209
210 /** @brief Construct a linear segment from its endpoints. */
BezierCurveN(Point c0,Point c1)211 BezierCurveN(Point c0, Point c1) {
212 assert_degree<1>(this);
213 for(unsigned d = 0; d < 2; d++)
214 inner[d] = Bezier(c0[d], c1[d]);
215 }
216
217 /** @brief Construct a quadratic Bezier curve from its control points. */
BezierCurveN(Point c0,Point c1,Point c2)218 BezierCurveN(Point c0, Point c1, Point c2) {
219 assert_degree<2>(this);
220 for(unsigned d = 0; d < 2; d++)
221 inner[d] = Bezier(c0[d], c1[d], c2[d]);
222 }
223
224 /** @brief Construct a cubic Bezier curve from its control points. */
BezierCurveN(Point c0,Point c1,Point c2,Point c3)225 BezierCurveN(Point c0, Point c1, Point c2, Point c3) {
226 assert_degree<3>(this);
227 for(unsigned d = 0; d < 2; d++)
228 inner[d] = Bezier(c0[d], c1[d], c2[d], c3[d]);
229 }
230
231 // default copy
232 // default assign
233
234 /// @}
235
236 /** @brief Divide a Bezier curve into two curves
237 * @param t Time value
238 * @return Pair of Bezier curves \f$(\mathbf{D}, \mathbf{E})\f$ such that
239 * \f$\mathbf{D}[ [0,1] ] = \mathbf{C}[ [0,t] ]\f$ and
240 * \f$\mathbf{E}[ [0,1] ] = \mathbf{C}[ [t,1] ]\f$ */
subdivide(Coord t)241 std::pair<BezierCurveN, BezierCurveN> subdivide(Coord t) const {
242 std::pair<Bezier, Bezier> sx = inner[X].subdivide(t), sy = inner[Y].subdivide(t);
243 return std::make_pair(
244 BezierCurveN(sx.first, sy.first),
245 BezierCurveN(sx.second, sy.second));
246 }
247
isDegenerate()248 virtual bool isDegenerate() const {
249 return BezierCurve::isDegenerate();
250 }
251
isLineSegment()252 virtual bool isLineSegment() const {
253 return size() == 2;
254 }
255
duplicate()256 virtual Curve *duplicate() const {
257 return new BezierCurveN(*this);
258 }
portion(Coord f,Coord t)259 virtual Curve *portion(Coord f, Coord t) const {
260 if (degree == 1) {
261 return new BezierCurveN<1>(pointAt(f), pointAt(t));
262 } else {
263 return new BezierCurveN(Geom::portion(inner, f, t));
264 }
265 }
reverse()266 virtual Curve *reverse() const {
267 if (degree == 1) {
268 return new BezierCurveN<1>(finalPoint(), initialPoint());
269 } else {
270 return new BezierCurveN(Geom::reverse(inner));
271 }
272 }
273 virtual Curve *derivative() const;
274
275 virtual Coord nearestTime(Point const &p, Coord from = 0, Coord to = 1) const {
276 return BezierCurve::nearestTime(p, from, to);
277 }
278 virtual std::vector<CurveIntersection> intersect(Curve const &other, Coord eps = EPSILON) const {
279 // call super. this is implemented only to allow specializations
280 return BezierCurve::intersect(other, eps);
281 }
winding(Point const & p)282 virtual int winding(Point const &p) const {
283 return Curve::winding(p);
284 }
feed(PathSink & sink,bool moveto_initial)285 virtual void feed(PathSink &sink, bool moveto_initial) const {
286 // call super. this is implemented only to allow specializations
287 BezierCurve::feed(sink, moveto_initial);
288 }
289 };
290
291 // BezierCurveN<0> is meaningless; specialize it out
292 template<> class BezierCurveN<0> : public BezierCurveN<1> { private: BezierCurveN();};
293
294 /** @brief Line segment.
295 * Line segments are Bezier curves of order 1. They have only two control points,
296 * the starting point and the ending point.
297 * @ingroup Curves */
298 typedef BezierCurveN<1> LineSegment;
299
300 /** @brief Quadratic (order 2) Bezier curve.
301 * @ingroup Curves */
302 typedef BezierCurveN<2> QuadraticBezier;
303
304 /** @brief Cubic (order 3) Bezier curve.
305 * @ingroup Curves */
306 typedef BezierCurveN<3> CubicBezier;
307
308 template <unsigned degree>
309 inline
derivative()310 Curve *BezierCurveN<degree>::derivative() const {
311 return new BezierCurveN<degree-1>(Geom::derivative(inner[X]), Geom::derivative(inner[Y]));
312 }
313
314 // optimized specializations
isDegenerate()315 template <> inline bool BezierCurveN<1>::isDegenerate() const {
316 return inner[X][0] == inner[X][1] && inner[Y][0] == inner[Y][1];
317 }
isLineSegment()318 template <> inline bool BezierCurveN<1>::isLineSegment() const { return true; }
319 template <> Curve *BezierCurveN<1>::derivative() const;
320 template <> Coord BezierCurveN<1>::nearestTime(Point const &, Coord, Coord) const;
321 template <> std::vector<CurveIntersection> BezierCurveN<1>::intersect(Curve const &, Coord) const;
322 template <> int BezierCurveN<1>::winding(Point const &) const;
323 template <> void BezierCurveN<1>::feed(PathSink &sink, bool moveto_initial) const;
324 template <> void BezierCurveN<2>::feed(PathSink &sink, bool moveto_initial) const;
325 template <> void BezierCurveN<3>::feed(PathSink &sink, bool moveto_initial) const;
326
middle_point(LineSegment const & _segment)327 inline Point middle_point(LineSegment const& _segment) {
328 return ( _segment.initialPoint() + _segment.finalPoint() ) / 2;
329 }
330
length(LineSegment const & seg)331 inline Coord length(LineSegment const& seg) {
332 return distance(seg.initialPoint(), seg.finalPoint());
333 }
334
335 Coord bezier_length(std::vector<Point> const &points, Coord tolerance = 0.01);
336 Coord bezier_length(Point p0, Point p1, Point p2, Coord tolerance = 0.01);
337 Coord bezier_length(Point p0, Point p1, Point p2, Point p3, Coord tolerance = 0.01);
338
339 } // end namespace Geom
340
341 #endif // LIB2GEOM_SEEN_BEZIER_CURVE_H
342
343 /*
344 Local Variables:
345 mode:c++
346 c-file-style:"stroustrup"
347 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
348 indent-tabs-mode:nil
349 fill-column:99
350 End:
351 */
352 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
353