From 6492fcbc5fbe9a07962f989247731b6435fd72b9 Mon Sep 17 00:00:00 2001 From: johanengelen Date: Tue, 17 Jun 2008 21:03:42 +0000 Subject: [PATCH] update 2geom --- src/2geom/bezier.h | 2 +- src/2geom/concepts.h | 2 +- src/2geom/curve.h | 6 +++- src/2geom/d2.h | 8 ++--- src/2geom/elliptical-arc.cpp | 11 +++--- src/2geom/hvlinesegment.h | 66 +++++++++++++++++++++--------------- src/2geom/path.h | 17 +++++++++- src/2geom/piecewise.h | 4 +-- src/2geom/sbasis-roots.cpp | 22 ++++++++++-- src/2geom/sbasis.cpp | 9 ++--- 10 files changed, 95 insertions(+), 52 deletions(-) diff --git a/src/2geom/bezier.h b/src/2geom/bezier.h index 289a67729..bc9d6032e 100644 --- a/src/2geom/bezier.h +++ b/src/2geom/bezier.h @@ -171,7 +171,7 @@ public: std::vector valueAndDerivatives(Coord t, unsigned n_derivs) const { std::vector val_n_der; Coord d_[order()+1]; - unsigned nn = n_derivs; + unsigned nn = n_derivs + 1; // the size of the result vector equals n_derivs+1 if(nn > order()) //nn = order(); nn = order()+1; diff --git a/src/2geom/concepts.h b/src/2geom/concepts.h index ba4522274..3b6fd3577 100644 --- a/src/2geom/concepts.h +++ b/src/2geom/concepts.h @@ -78,7 +78,7 @@ struct FragmentConcept { o = t.at1(); o = t.valueAt(d); o = t(d); - v = t.valueAndDerivatives(d, u); + v = t.valueAndDerivatives(d, u-1); //Is a pure derivative (ignoring others) accessor ever much faster? //u = number of values returned. first val is value. sb = t.toSBasis(); diff --git a/src/2geom/curve.h b/src/2geom/curve.h index d201d5d5e..7f138dabf 100644 --- a/src/2geom/curve.h +++ b/src/2geom/curve.h @@ -103,10 +103,14 @@ public: virtual Curve *transformed(Matrix const &m) const = 0; - virtual Point pointAt(Coord t) const { return pointAndDerivatives(t, 1).front(); } + virtual Point pointAt(Coord t) const { return pointAndDerivatives(t, 0).front(); } virtual Coord valueAt(Coord t, Dim2 d) const { return pointAt(t)[d]; } virtual Point operator() (double t) const { return pointAt(t); } + + /* pointAndDerivatives returns a vector that looks like the following: + * [ point at t, 1st derivative at t, 2nd derivative at t, ... , n'th derivative at t] */ virtual std::vector pointAndDerivatives(Coord t, unsigned n) const = 0; + virtual D2 toSBasis() const = 0; }; diff --git a/src/2geom/d2.h b/src/2geom/d2.h index 3becc813d..db8cf68c4 100644 --- a/src/2geom/d2.h +++ b/src/2geom/d2.h @@ -88,11 +88,11 @@ class D2{ boost::function_requires >(); return (*this)(t); } - std::vector valueAndDerivatives(double t, unsigned count) const { - std::vector x = f[X].valueAndDerivatives(t, count), - y = f[Y].valueAndDerivatives(t, count); + std::vector valueAndDerivatives(double t, unsigned n) const { + std::vector x = f[X].valueAndDerivatives(t, n), + y = f[Y].valueAndDerivatives(t, n); std::vector res; - for(unsigned i = 0; i < count; i++) { + for(unsigned i = 0; i <= n; i++) { res.push_back(Point(x[i], y[i])); } return res; diff --git a/src/2geom/elliptical-arc.cpp b/src/2geom/elliptical-arc.cpp index a433ca370..b30dfde5d 100644 --- a/src/2geom/elliptical-arc.cpp +++ b/src/2geom/elliptical-arc.cpp @@ -326,31 +326,32 @@ Curve* EllipticalArc::derivative() const std::vector EllipticalArc::pointAndDerivatives(Coord t, unsigned int n) const { + unsigned int nn = n+1; // nn represents the size of the result vector. std::vector result; - result.reserve(n); + result.reserve(nn); double angle = map_unit_interval_on_circular_arc(t, start_angle(), end_angle(), sweep_flag()); EllipticalArc ea(*this); ea.m_center = Point(0,0); - unsigned int m = std::min(n, 4u); + unsigned int m = std::min(nn, 4u); for ( unsigned int i = 0; i < m; ++i ) { result.push_back( ea.pointAtAngle(angle) ); angle += M_PI/2; if ( !(angle < 2*M_PI) ) angle -= 2*M_PI; } - m = n / 4; + m = nn / 4; for ( unsigned int i = 1; i < m; ++i ) { for ( unsigned int j = 0; j < 4; ++j ) result.push_back( result[j] ); } - m = n - 4 * m; + m = nn - 4 * m; for ( unsigned int i = 0; i < m; ++i ) { result.push_back( result[i] ); } - if ( !result.empty() ) // n != 0 + if ( !result.empty() ) // nn != 0 result[0] = pointAtAngle(angle); return result; } diff --git a/src/2geom/hvlinesegment.h b/src/2geom/hvlinesegment.h index b3c200378..732c29938 100644 --- a/src/2geom/hvlinesegment.h +++ b/src/2geom/hvlinesegment.h @@ -243,20 +243,25 @@ class HLineSegment : public Curve return initialPoint()[X] + t * (finalPoint()[X] - initialPoint()[X]); } - - std::vector pointAndDerivatives(Coord t, unsigned n) const - { - std::vector result; - if ( n > 0) - result.push_back(pointAt(t)); - if (n > 1) - { - double x = finalPoint()[X] - initialPoint()[X]; - result.push_back( Point(x, 0) ); - } - return result; - } - + + std::vector pointAndDerivatives(Coord t, unsigned n) const + { + std::vector result; + result.push_back(pointAt(t)); + if (n > 0) + { + double x = finalPoint()[X] - initialPoint()[X]; + result.push_back( Point(x, 0) ); + } + if (n > 1) + { + /* higher order derivatives are zero, + * so the other n-1 vector elements are (0,0) */ + result.insert( result.end(), n-1, Point(0, 0) ); + } + return result; + } + D2 toSBasis() const { return m_line_seg.toSBasis(); @@ -473,20 +478,25 @@ class VLineSegment : public Curve return initialPoint()[Y] + t * (finalPoint()[Y] - initialPoint()[Y]); } - - std::vector pointAndDerivatives(Coord t, unsigned n) const - { - std::vector result; - if ( n > 0) - result.push_back(pointAt(t)); - if (n > 1) - { - double y = finalPoint()[Y] - initialPoint()[Y]; - result.push_back( Point(0, y) ); - } - return result; - } - + + std::vector pointAndDerivatives(Coord t, unsigned n) const + { + std::vector result; + result.push_back(pointAt(t)); + if (n > 0) + { + double y = finalPoint()[Y] - initialPoint()[Y]; + result.push_back( Point(0, y) ); + } + if (n > 1) + { + /* higher order derivatives are zero, + * so the other n-1 vector elements are (0,0) */ + result.insert( result.end(), n-1, Point(0, 0) ); + } + return result; + } + D2 toSBasis() const { return m_line_seg.toSBasis(); diff --git a/src/2geom/path.h b/src/2geom/path.h index 8f51c46c2..719a66478 100644 --- a/src/2geom/path.h +++ b/src/2geom/path.h @@ -126,6 +126,21 @@ private: Iterator impl_; }; +/* + * Open and closed paths: all paths, whether open or closed, store a final + * segment which connects the initial and final endpoints of the "real" + * path data. While similar to the "z" in an SVG path, it exists for + * both open and closed paths, and is not considered part of the "normal" + * path data, which is always covered by the range [begin(), end_open()). + * Conversely, the range [begin(), end_closed()) always contains the "extra" + * closing segment. + * + * The only difference between a closed and an open path is whether end() + * returns end_closed() or end_open(). The idea behind this is to let + * any path be stroked using [begin(), end()), and filled using + * [begin(), end_closed()), without requiring a separate "filled" version + * of the path to use for filling. + */ class Path { private: typedef std::vector Sequence; @@ -598,7 +613,7 @@ class PathPortion : public Curve { virtual Curve *transformed(Matrix const &m) const = 0; - virtual Point pointAt(Coord t) const { return pointAndDerivatives(t, 1).front(); } + virtual Point pointAt(Coord t) const { return pointAndDerivatives(t, 0).front(); } virtual Coord valueAt(Coord t, Dim2 d) const { return pointAt(t)[d]; } virtual std::vector pointAndDerivatives(Coord t, unsigned n) const = 0; virtual D2 toSBasis() const = 0; diff --git a/src/2geom/piecewise.h b/src/2geom/piecewise.h index 3f13d15b0..8992c0097 100644 --- a/src/2geom/piecewise.h +++ b/src/2geom/piecewise.h @@ -79,9 +79,9 @@ class Piecewise { inline output_type lastValue() const { return valueAt(cuts.back()); } - std::vector valueAndDerivatives(double t, unsigned cnt) const { + std::vector valueAndDerivatives(double t, unsigned n_derivs) const { unsigned n = segN(t); - std::vector ret, val = segs[n].valueAndDerivatives(segT(t, n), cnt); + std::vector ret, val = segs[n].valueAndDerivatives(segT(t, n), n_derivs); double mult = 1; for(unsigned i = 0; i < val.size(); i++) { ret.push_back(val[i] * mult); diff --git a/src/2geom/sbasis-roots.cpp b/src/2geom/sbasis-roots.cpp index 52d3ef6a9..51a4ec97d 100644 --- a/src/2geom/sbasis-roots.cpp +++ b/src/2geom/sbasis-roots.cpp @@ -330,10 +330,26 @@ void subdiv_sbasis(SBasis const & s, // It is faster to use the bernstein root finder for small degree polynomials (<100?. +std::vector roots1(SBasis const & s) { + std::vector res; + double d = s[0][0] - s[0][1]; + if(d != 0) { + double r = s[0][0] / d; + if(0 <= r and r <= 1) + res.push_back(r); + } + return res; +} + std::vector roots(SBasis const & s) { - if(s.size() == 0) return std::vector(); - - return sbasis_to_bezier(s).roots(); + switch(s.size()) { + case 0: + return std::vector(); + case 1: + return roots1(s); + default: + return sbasis_to_bezier(s).roots(); + } } }; diff --git a/src/2geom/sbasis.cpp b/src/2geom/sbasis.cpp index 920fd37fe..d7a3972e1 100644 --- a/src/2geom/sbasis.cpp +++ b/src/2geom/sbasis.cpp @@ -69,15 +69,12 @@ bool SBasis::isFinite() const { } std::vector SBasis::valueAndDerivatives(double t, unsigned n) const { - std::vector ret(n); - if(n==1) { - ret.push_back(valueAt(t)); - return ret; - } + std::vector ret(n+1); + ret.push_back(valueAt(t)); SBasis tmp = *this; for(unsigned i = 0; i < n; i++) { - ret[i] = tmp.valueAt(t); tmp.derive(); + ret[i] = tmp.valueAt(t); } return ret; } -- 2.30.2