From 55d43e4e27e0ba58a47fad70957dfa989aa173ad Mon Sep 17 00:00:00 2001 From: "Johan B. C. Engelen" Date: Tue, 14 Aug 2007 20:54:48 +0000 Subject: Commit LivePathEffect branch to trunk! (disabled extension/internal/bitmap/*.* in build.xml to fix compilation) (bzr r3472) --- src/2geom/path.cpp | 367 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 367 insertions(+) create mode 100644 src/2geom/path.cpp (limited to 'src/2geom/path.cpp') diff --git a/src/2geom/path.cpp b/src/2geom/path.cpp new file mode 100644 index 000000000..91868eb7e --- /dev/null +++ b/src/2geom/path.cpp @@ -0,0 +1,367 @@ +/* + * Path - Series of continuous curves + * + * Copyright 2007 MenTaLguY + * + * This library is free software; you can redistribute it and/or + * modify it either under the terms of the GNU Lesser General Public + * License version 2.1 as published by the Free Software Foundation + * (the "LGPL") or, at your option, under the terms of the Mozilla + * Public License Version 1.1 (the "MPL"). If you do not alter this + * notice, a recipient may use your version of this file under either + * the MPL or the LGPL. + * + * You should have received a copy of the LGPL along with this library + * in the file COPYING-LGPL-2.1; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * You should have received a copy of the MPL along with this library + * in the file COPYING-MPL-1.1 + * + * The contents of this file are subject to the Mozilla Public License + * Version 1.1 (the "License"); you may not use this file except in + * compliance with the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY + * OF ANY KIND, either express or implied. See the LGPL or the MPL for + * the specific language governing rights and limitations. + */ + +#include "path.h" + +namespace Geom { + +namespace { + +enum Cmp { + LESS_THAN=-1, + GREATER_THAN=1, + EQUAL_TO=0 +}; + +template +inline Cmp cmp(T1 const &a, T2 const &b) { + if ( a < b ) { + return LESS_THAN; + } else if ( b < a ) { + return GREATER_THAN; + } else { + return EQUAL_TO; + } +} + +} + +boost::optional CurveHelpers::sbasis_winding(D2 const &sb, Point p) { + Interval ix = bounds_fast(sb[X]); + + if ( p[X] > ix.max() ) { /* ray does not intersect bbox */ + return 0; + } + + SBasis fy = sb[Y]; + fy -= p[Y]; + + if (fy.empty()) { /* coincident horizontal segment */ + return boost::optional(); + } + + if ( p[X] < ix.min() ) { /* ray does not originate in bbox */ + double y = p[Y]; + /* winding determined by position of endpoints */ + Cmp initial_to_ray = cmp(fy[0][0], y); + Cmp final_to_ray = cmp(fy[0][1], y); + switch (cmp(final_to_ray, initial_to_ray)) { + case GREATER_THAN: + /* exclude final endpoint */ + return ( final_to_ray != EQUAL_TO ); + case LESS_THAN: + /* exclude final endpoint */ + return -( final_to_ray != EQUAL_TO ); + default: + /* any intersections cancel out */ + return 0; + } + } else { /* ray originates in bbox */ + std::vector ts = roots(fy); + + static const unsigned MAX_DERIVATIVES=8; + boost::optional ds[MAX_DERIVATIVES]; + ds[0] = derivative(fy); + + /* winding determined by summing signs of derivatives at intersections */ + int winding=0; + for ( std::vector::iterator ti = ts.begin() + ; ti != ts.end() + ; ++ti ) + { + double t = *ti; + if ( sb[X](t) >= p[X] ) { /* root is ray intersection */ + for ( boost::optional *di = ds + ; di != ( ds + MAX_DERIVATIVES ) + ; ++di ) + { + if (!*di) { + *di = derivative(**(di-1)); + } + switch (cmp((**di)(t), 0)) { + case GREATER_THAN: + if ( t < 1 ) { /* exclude final endpoint */ + winding += 1; + } + goto next_root; + case LESS_THAN: + if ( t < 1 ) { /* exclude final endpoint */ + winding -= 1; + } + goto next_root; + default: (void)0; + /* give up */ + }; + } + } +next_root: (void)0; + } + + return winding; + } +} + +Rect BezierHelpers::bounds(unsigned degree, Point const *points) { + Point min=points[0]; + Point max=points[0]; + for ( unsigned i = 1 ; i <= degree ; ++i ) { + for ( unsigned axis = 0 ; axis < 2 ; ++axis ) { + min[axis] = std::min(min[axis], points[i][axis]); + max[axis] = std::max(max[axis], points[i][axis]); + } + } + return Rect(min, max); +} + +Point BezierHelpers::point_and_derivatives_at(Coord t, + unsigned degree, + Point const *points, + unsigned n_derivs, + Point *derivs) +{ + return Point(0,0); // TODO +} + +Geom::Point +BezierHelpers::subdivideArr(Coord t, // Parameter value + unsigned degree, // Degree of bezier curve + Geom::Point const *V, // Control pts + Geom::Point *Left, // RETURN left half ctl pts + Geom::Point *Right) // RETURN right half ctl pts +{ + Geom::Point Vtemp[degree+1][degree+1]; + + /* Copy control points */ + std::copy(V, V+degree+1, Vtemp[0]); + + /* Triangle computation */ + for (unsigned i = 1; i <= degree; i++) { + for (unsigned j = 0; j <= degree - i; j++) { + Vtemp[i][j] = lerp(t, Vtemp[i-1][j], Vtemp[i-1][j+1]); + } + } + + for (unsigned j = 0; j <= degree; j++) + Left[j] = Vtemp[j][0]; + for (unsigned j = 0; j <= degree; j++) + Right[j] = Vtemp[degree-j][j]; + + return (Vtemp[degree][0]); +} + +void Path::swap(Path &other) { + std::swap(curves_, other.curves_); + std::swap(closed_, other.closed_); + std::swap(*final_, *other.final_); + curves_[curves_.size()-1] = final_; + other.curves_[other.curves_.size()-1] = other.final_; +} + +Rect Path::bounds_fast() const { + Rect bounds=front().bounds_fast(); + for ( const_iterator iter=++begin(); iter != end() ; ++iter ) { + bounds.unionWith(iter->bounds_fast()); + } + return bounds; +} + +Rect Path::bounds_exact() const { + Rect bounds=front().bounds_exact(); + for ( const_iterator iter=++begin(); iter != end() ; ++iter ) { + bounds.unionWith(iter->bounds_exact()); + } + return bounds; +} + +int Path::winding(Point p) const { + int winding = 0; + boost::optional ignore = boost::optional(); + for ( const_iterator iter = begin() + ; iter != end_closed() + ; ++iter ) + { + boost::optional w = iter->winding(p); + if (w) { + winding += *w; + ignore = boost::optional(); + } else { + Point initial = iter->initialPoint(); + Point final = iter->finalPoint(); + switch (cmp(initial[X], final[X])) { + case GREATER_THAN: + if ( !ignore || *ignore != GREATER_THAN ) { /* ignore repeated */ + winding += 1; + ignore = GREATER_THAN; + } + break; + case LESS_THAN: + if ( !ignore || *ignore != LESS_THAN ) { /* ignore repeated */ + if ( p[X] < final[X] ) { /* ignore final point */ + winding -= 1; + ignore = LESS_THAN; + } + } + break; + case EQUAL_TO: + /* always ignore null segments */ + break; + } + } + } + return winding; +} + +void Path::append(Curve const &curve) { + if ( curves_.front() != final_ && curve.initialPoint() != (*final_)[0] ) { + throw ContinuityError(); + } + do_append(curve.duplicate()); +} + +void Path::append(D2 const &curve) { + if ( curves_.front() != final_ ) { + for ( int i = 0 ; i < 2 ; ++i ) { + if ( curve[i][0][0] != (*final_)[0][i] ) { + throw ContinuityError(); + } + } + } + do_append(new SBasisCurve(curve)); +} + +void Path::do_update(Sequence::iterator first_replaced, + Sequence::iterator last_replaced, + Sequence::iterator first, + Sequence::iterator last) +{ + // note: modifies the contents of [first,last) + + check_continuity(first_replaced, last_replaced, first, last); + delete_range(first_replaced, last_replaced); + if ( ( last - first ) == ( last_replaced - first_replaced ) ) { + std::copy(first, last, first_replaced); + } else { + // this approach depends on std::vector's behavior WRT iterator stability + curves_.erase(first_replaced, last_replaced); + curves_.insert(first_replaced, first, last); + } + + if ( curves_.front() != final_ ) { + (*final_)[0] = back().finalPoint(); + (*final_)[1] = front().initialPoint(); + } +} + +void Path::do_append(Curve *curve) { + if ( curves_.front() == final_ ) { + (*final_)[1] = curve->initialPoint(); + } + curves_.insert(curves_.end()-1, curve); + (*final_)[0] = curve->finalPoint(); +} + +void Path::delete_range(Sequence::iterator first, Sequence::iterator last) { + for ( Sequence::iterator iter=first ; iter != last ; ++iter ) { + delete *iter; + } +} + +void Path::check_continuity(Sequence::iterator first_replaced, + Sequence::iterator last_replaced, + Sequence::iterator first, + Sequence::iterator last) +{ + if ( first != last ) { + if ( first_replaced != curves_.begin() ) { + if ( (*first_replaced)->initialPoint() != (*first)->initialPoint() ) { + throw ContinuityError(); + } + } + if ( last_replaced != (curves_.end()-1) ) { + if ( (*(last_replaced-1))->finalPoint() != (*(last-1))->finalPoint() ) { + throw ContinuityError(); + } + } + } else if ( first_replaced != last_replaced && first_replaced != curves_.begin() && last_replaced != curves_.end()-1) { + if ( (*first_replaced)->initialPoint() != + (*(last_replaced-1))->finalPoint() ) + { + throw ContinuityError(); + } + } +} + +Rect SBasisCurve::bounds_fast() const { + throw NotImplemented(); + return Rect(Point(0,0), Point(0,0)); +} + +Rect SBasisCurve::bounds_exact() const { + throw NotImplemented(); + return Rect(Point(0,0), Point(0,0)); +} + +Point SBasisCurve::pointAndDerivativesAt(Coord t, unsigned n_derivs, Point *derivs) const { + throw NotImplemented(); + return Point(0,0); +} + +Path const &SBasisCurve::subdivide(Coord t, Path &out) const { + throw NotImplemented(); +} + +Rect SVGEllipticalArc::bounds_fast() const { + throw NotImplemented(); +} +Rect SVGEllipticalArc::bounds_exact() const { + throw NotImplemented(); +} + +Point SVGEllipticalArc::pointAndDerivativesAt(Coord t, unsigned n_derivs, Point *derivs) const { + throw NotImplemented(); +} + +D2 SVGEllipticalArc::sbasis() const { + throw NotImplemented(); +} + +} + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(substatement-open . 0)) + indent-tabs-mode:nil + c-brace-offset:0 + fill-column:99 + End: + vim: filetype=cpp:expandtab:shiftwidth=2:tabstop=8:softtabstop=2 : +*/ + -- cgit v1.2.3