/* * Copyright 2006 The Android Open Source Project * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #include "include/core/SkPath.h" #include "include/core/SkArc.h" #include "include/core/SkPathBuilder.h" #include "include/core/SkRRect.h" #include "include/core/SkStream.h" #include "include/core/SkString.h" #include "include/private/SkPathRef.h" #include "include/private/base/SkFloatingPoint.h" #include "include/private/base/SkMalloc.h" #include "include/private/base/SkSpan_impl.h" #include "include/private/base/SkTArray.h" #include "include/private/base/SkTDArray.h" #include "include/private/base/SkTo.h" #include "src/base/SkFloatBits.h" #include "src/base/SkTLazy.h" #include "src/base/SkVx.h" #include "src/core/SkCubicClipper.h" #include "src/core/SkEdgeClipper.h" #include "src/core/SkGeometry.h" #include "src/core/SkMatrixPriv.h" #include "src/core/SkPathEnums.h" #include "src/core/SkPathMakers.h" #include "src/core/SkPathPriv.h" #include "src/core/SkPointPriv.h" #include "src/core/SkStringUtils.h" #include <algorithm> #include <cmath> #include <cstring> #include <iterator> #include <limits.h> #include <utility> struct SkPath_Storage_Equivalent { … }; static_assert …; static float poly_eval(float A, float B, float C, float t) { … } static float poly_eval(float A, float B, float C, float D, float t) { … } //////////////////////////////////////////////////////////////////////////// /** * Path.bounds is defined to be the bounds of all the control points. * If we called bounds.join(r) we would skip r if r was empty, which breaks * our promise. Hence we have a custom joiner that doesn't look at emptiness */ static void joinNoEmptyChecks(SkRect* dst, const SkRect& src) { … } static bool is_degenerate(const SkPath& path) { … } class SkAutoDisableDirectionCheck { … }; /* This class's constructor/destructor bracket a path editing operation. It is used when we know the bounds of the amount we are going to add to the path (usually a new contour, but not required). It captures some state about the path up front (i.e. if it already has a cached bounds), and then if it can, it updates the cache bounds explicitly, avoiding the need to revisit all of the points in getBounds(). It also notes if the path was originally degenerate, and if so, sets isConvex to true. Thus it can only be used if the contour being added is convex. */ class SkAutoPathBoundsUpdate { … }; //////////////////////////////////////////////////////////////////////////// /* Stores the verbs and points as they are given to us, with exceptions: - we only record "Close" if it was immediately preceeded by Move | Line | Quad | Cubic - we insert a Move(0,0) if Line | Quad | Cubic is our first command The iterator does more cleanup, especially if forceClose == true 1. If we encounter degenerate segments, remove them 2. if we encounter Close, return a cons'd up Line() first (if the curr-pt != start-pt) 3. if we encounter Move without a preceeding Close, and forceClose is true, goto #2 4. if we encounter Line | Quad | Cubic after Close, cons up a Move */ //////////////////////////////////////////////////////////////////////////// // flag to require a moveTo if we begin with something else, like lineTo etc. // This will also be the value of lastMoveToIndex for a single contour // ending with close, so countVerbs needs to be checked against 0. #define INITIAL_LASTMOVETOINDEX_VALUE … SkPath::SkPath() : … { … } SkPath::SkPath(sk_sp<SkPathRef> pr, SkPathFillType ft, bool isVolatile, SkPathConvexity ct, SkPathFirstDirection firstDirection) : … { … } void SkPath::resetFields() { … } SkPath::SkPath(const SkPath& that) : … { … } SkPath::~SkPath() { … } SkPath& SkPath::operator=(const SkPath& that) { … } void SkPath::copyFields(const SkPath& that) { … } bool operator==(const SkPath& a, const SkPath& b) { … } void SkPath::swap(SkPath& that) { … } bool SkPath::isInterpolatable(const SkPath& compare) const { … } bool SkPath::interpolate(const SkPath& ending, SkScalar weight, SkPath* out) const { … } static inline bool check_edge_against_rect(const SkPoint& p0, const SkPoint& p1, const SkRect& rect, SkPathFirstDirection dir) { … } bool SkPath::conservativelyContainsRect(const SkRect& rect) const { … } uint32_t SkPath::getGenerationID() const { … } SkPath& SkPath::reset() { … } SkPath& SkPath::rewind() { … } bool SkPath::isLastContourClosed() const { … } bool SkPath::isLine(SkPoint line[2]) const { … } bool SkPath::isEmpty() const { … } bool SkPath::isFinite() const { … } bool SkPath::isConvex() const { … } const SkRect& SkPath::getBounds() const { … } uint32_t SkPath::getSegmentMasks() const { … } bool SkPath::isValid() const { … } bool SkPath::hasComputedBounds() const { … } void SkPath::setBounds(const SkRect& rect) { … } SkPathConvexity SkPath::getConvexityOrUnknown() const { … } #ifdef SK_DEBUG void SkPath::validate() const { … } void SkPath::validateRef() const { … } #endif /* Determines if path is a rect by keeping track of changes in direction and looking for a loop either clockwise or counterclockwise. The direction is computed such that: 0: vertical up 1: horizontal left 2: vertical down 3: horizontal right A rectangle cycles up/right/down/left or up/left/down/right. The test fails if: The path is closed, and followed by a line. A second move creates a new endpoint. A diagonal line is parsed. There's more than four changes of direction. There's a discontinuity on the line (e.g., a move in the middle) The line reverses direction. The path contains a quadratic or cubic. The path contains fewer than four points. *The rectangle doesn't complete a cycle. *The final point isn't equal to the first point. *These last two conditions we relax if we have a 3-edge path that would form a rectangle if it were closed (as we do when we fill a path) It's OK if the path has: Several colinear line segments composing a rectangle side. Single points on the rectangle side. The direction takes advantage of the corners found since opposite sides must travel in opposite directions. FIXME: Allow colinear quads and cubics to be treated like lines. FIXME: If the API passes fill-only, return true if the filled stroke is a rectangle, though the caller failed to close the path. directions values: 0x1 is set if the segment is horizontal 0x2 is set if the segment is moving to the right or down thus: two directions are opposites iff (dirA ^ dirB) == 0x2 two directions are perpendicular iff (dirA ^ dirB) == 0x1 */ static int rect_make_dir(SkScalar dx, SkScalar dy) { … } bool SkPath::isRect(SkRect* rect, bool* isClosed, SkPathDirection* direction) const { … } bool SkPath::isOval(SkRect* bounds) const { … } bool SkPath::isRRect(SkRRect* rrect) const { … } int SkPath::countPoints() const { … } int SkPath::getPoints(SkPoint dst[], int max) const { … } SkPoint SkPath::getPoint(int index) const { … } int SkPath::countVerbs() const { … } int SkPath::getVerbs(uint8_t dst[], int max) const { … } size_t SkPath::approximateBytesUsed() const { … } bool SkPath::getLastPt(SkPoint* lastPt) const { … } void SkPath::setPt(int index, SkScalar x, SkScalar y) { … } void SkPath::setLastPt(SkScalar x, SkScalar y) { … } // This is the public-facing non-const setConvexity(). void SkPath::setConvexity(SkPathConvexity c) { … } // Const hooks for working with fConvexity and fFirstDirection from const methods. void SkPath::setConvexity(SkPathConvexity c) const { … } void SkPath::setFirstDirection(SkPathFirstDirection d) const { … } SkPathFirstDirection SkPath::getFirstDirection() const { … } bool SkPath::isConvexityAccurate() const { … } SkPathConvexity SkPath::getConvexity() const { … } ////////////////////////////////////////////////////////////////////////////// // Construction methods SkPath& SkPath::dirtyAfterEdit() { … } void SkPath::incReserve(int extraPtCount, int extraVerbCount, int extraConicCount) { … } SkPath& SkPath::moveTo(SkScalar x, SkScalar y) { … } SkPath& SkPath::rMoveTo(SkScalar x, SkScalar y) { … } void SkPath::injectMoveToIfNeeded() { … } SkPath& SkPath::lineTo(SkScalar x, SkScalar y) { … } SkPath& SkPath::rLineTo(SkScalar x, SkScalar y) { … } SkPath& SkPath::quadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) { … } SkPath& SkPath::rQuadTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2) { … } SkPath& SkPath::conicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, SkScalar w) { … } SkPath& SkPath::rConicTo(SkScalar dx1, SkScalar dy1, SkScalar dx2, SkScalar dy2, SkScalar w) { … } SkPath& SkPath::cubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, SkScalar x3, SkScalar y3) { … } SkPath& SkPath::rCubicTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, SkScalar x3, SkScalar y3) { … } SkPath& SkPath::close() { … } /////////////////////////////////////////////////////////////////////////////// static void assert_known_direction(SkPathDirection dir) { … } SkPath& SkPath::addRect(const SkRect &rect, SkPathDirection dir, unsigned startIndex) { … } SkPath& SkPath::addPoly(const SkPoint pts[], int count, bool close) { … } static bool arc_is_lone_point(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle, SkPoint* pt) { … } // Return the unit vectors pointing at the start/stop points for the given start/sweep angles // static void angles_to_unit_vectors(SkScalar startAngle, SkScalar sweepAngle, SkVector* startV, SkVector* stopV, SkRotationDirection* dir) { … } /** * If this returns 0, then the caller should just line-to the singlePt, else it should * ignore singlePt and append the specified number of conics. */ static int build_arc_conics(const SkRect& oval, const SkVector& start, const SkVector& stop, SkRotationDirection dir, SkConic conics[SkConic::kMaxConicsForArc], SkPoint* singlePt) { … } SkPath& SkPath::addRoundRect(const SkRect& rect, const SkScalar radii[], SkPathDirection dir) { … } SkPath& SkPath::addRRect(const SkRRect& rrect, SkPathDirection dir) { … } SkPath& SkPath::addRRect(const SkRRect &rrect, SkPathDirection dir, unsigned startIndex) { … } bool SkPath::hasOnlyMoveTos() const { … } bool SkPath::isZeroLengthSincePoint(int startPtIndex) const { … } SkPath& SkPath::addRoundRect(const SkRect& rect, SkScalar rx, SkScalar ry, SkPathDirection dir) { … } SkPath& SkPath::addOval(const SkRect& oval, SkPathDirection dir) { … } SkPath& SkPath::addOval(const SkRect &oval, SkPathDirection dir, unsigned startPointIndex) { … } SkPath& SkPath::addCircle(SkScalar x, SkScalar y, SkScalar r, SkPathDirection dir) { … } SkPath& SkPath::arcTo(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle, bool forceMoveTo) { … } // This converts the SVG arc to conics. // Partly adapted from Niko's code in kdelibs/kdecore/svgicons. // Then transcribed from webkit/chrome's SVGPathNormalizer::decomposeArcToCubic() // See also SVG implementation notes: // http://www.w3.org/TR/SVG/implnote.html#ArcConversionEndpointToCenter // Note that arcSweep bool value is flipped from the original implementation. SkPath& SkPath::arcTo(SkScalar rx, SkScalar ry, SkScalar angle, SkPath::ArcSize arcLarge, SkPathDirection arcSweep, SkScalar x, SkScalar y) { … } SkPath& SkPath::rArcTo(SkScalar rx, SkScalar ry, SkScalar xAxisRotate, SkPath::ArcSize largeArc, SkPathDirection sweep, SkScalar dx, SkScalar dy) { … } SkPath& SkPath::addArc(const SkRect& oval, SkScalar startAngle, SkScalar sweepAngle) { … } /* Need to handle the case when the angle is sharp, and our computed end-points for the arc go behind pt1 and/or p2... */ SkPath& SkPath::arcTo(SkScalar x1, SkScalar y1, SkScalar x2, SkScalar y2, SkScalar radius) { … } /////////////////////////////////////////////////////////////////////////////// SkPath& SkPath::addPath(const SkPath& path, SkScalar dx, SkScalar dy, AddPathMode mode) { … } SkPath& SkPath::addPath(const SkPath& srcPath, const SkMatrix& matrix, AddPathMode mode) { … } /////////////////////////////////////////////////////////////////////////////// // ignore the last point of the 1st contour SkPath& SkPath::reversePathTo(const SkPath& path) { … } SkPath& SkPath::reverseAddPath(const SkPath& srcPath) { … } /////////////////////////////////////////////////////////////////////////////// void SkPath::offset(SkScalar dx, SkScalar dy, SkPath* dst) const { … } static void subdivide_cubic_to(SkPath* path, const SkPoint pts[4], int level = 2) { … } void SkPath::transform(const SkMatrix& matrix, SkPath* dst, SkApplyPerspectiveClip pc) const { … } /////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////// SkPath::Iter::Iter() { … } SkPath::Iter::Iter(const SkPath& path, bool forceClose) { … } void SkPath::Iter::setPath(const SkPath& path, bool forceClose) { … } bool SkPath::Iter::isClosedContour() const { … } SkPath::Verb SkPath::Iter::autoClose(SkPoint pts[2]) { … } SkPath::Verb SkPath::Iter::next(SkPoint ptsParam[4]) { … } void SkPath::RawIter::setPath(const SkPath& path) { … } SkPath::Verb SkPath::RawIter::next(SkPoint pts[4]) { … } /////////////////////////////////////////////////////////////////////////////// static void append_params(SkString* str, const char label[], const SkPoint pts[], int count, SkScalarAsStringType strType, SkScalar conicWeight = -12345) { … } void SkPath::dump(SkWStream* wStream, bool dumpAsHex) const { … } void SkPath::dumpArrays(SkWStream* wStream, bool dumpAsHex) const { … } bool SkPath::isValidImpl() const { … } /////////////////////////////////////////////////////////////////////////////// static int sign(SkScalar x) { … } #define kValueNeverReturnedBySign … enum DirChange { … }; // only valid for a single contour struct Convexicator { … }; SkPathConvexity SkPath::computeConvexity() const { … } /////////////////////////////////////////////////////////////////////////////// class ContourIter { … }; ContourIter::ContourIter(const SkPathRef& pathRef) { … } void ContourIter::next() { … } // returns cross product of (p1 - p0) and (p2 - p0) static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) { … } // Returns the first pt with the maximum Y coordinate static int find_max_y(const SkPoint pts[], int count) { … } static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) { … } /** * Starting at index, and moving forward (incrementing), find the xmin and * xmax of the contiguous points that have the same Y. */ static int find_min_max_x_at_y(const SkPoint pts[], int index, int n, int* maxIndexPtr) { … } static SkPathFirstDirection crossToDir(SkScalar cross) { … } /* * We loop through all contours, and keep the computed cross-product of the * contour that contained the global y-max. If we just look at the first * contour, we may find one that is wound the opposite way (correctly) since * it is the interior of a hole (e.g. 'o'). Thus we must find the contour * that is outer most (or at least has the global y-max) before we can consider * its cross product. */ SkPathFirstDirection SkPathPriv::ComputeFirstDirection(const SkPath& path) { … } /////////////////////////////////////////////////////////////////////////////// static bool between(SkScalar a, SkScalar b, SkScalar c) { … } static SkScalar eval_cubic_pts(SkScalar c0, SkScalar c1, SkScalar c2, SkScalar c3, SkScalar t) { … } template <size_t N> static void find_minmax(const SkPoint pts[], SkScalar* minPtr, SkScalar* maxPtr) { … } static bool checkOnCurve(SkScalar x, SkScalar y, const SkPoint& start, const SkPoint& end) { … } static int winding_mono_cubic(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) { … } static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) { … } static double conic_eval_numerator(const SkScalar src[], SkScalar w, SkScalar t) { … } static double conic_eval_denominator(SkScalar w, SkScalar t) { … } static int winding_mono_conic(const SkConic& conic, SkScalar x, SkScalar y, int* onCurveCount) { … } static bool is_mono_quad(SkScalar y0, SkScalar y1, SkScalar y2) { … } static int winding_conic(const SkPoint pts[], SkScalar x, SkScalar y, SkScalar weight, int* onCurveCount) { … } static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) { … } static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) { … } static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y, int* onCurveCount) { … } static void tangent_cubic(const SkPoint pts[], SkScalar x, SkScalar y, SkTDArray<SkVector>* tangents) { … } static void tangent_conic(const SkPoint pts[], SkScalar x, SkScalar y, SkScalar w, SkTDArray<SkVector>* tangents) { … } static void tangent_quad(const SkPoint pts[], SkScalar x, SkScalar y, SkTDArray<SkVector>* tangents) { … } static void tangent_line(const SkPoint pts[], SkScalar x, SkScalar y, SkTDArray<SkVector>* tangents) { … } static bool contains_inclusive(const SkRect& r, SkScalar x, SkScalar y) { … } bool SkPath::contains(SkScalar x, SkScalar y) const { … } // Sort of like makeSpace(0) but the the additional requirement that we actively shrink the // allocations to just fit the current needs. makeSpace() will only grow, but never shrinks. // void SkPath::shrinkToFit() { … } int SkPath::ConvertConicToQuads(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w, SkPoint pts[], int pow2) { … } bool SkPathPriv::IsSimpleRect(const SkPath& path, bool isSimpleFill, SkRect* rect, SkPathDirection* direction, unsigned* start) { … } bool SkPathPriv::DrawArcIsConvex(SkScalar sweepAngle, SkArc::Type arcType, bool isFillNoPathEffect) { … } void SkPathPriv::CreateDrawArcPath(SkPath* path, const SkArc& arc, bool isFillNoPathEffect) { … } /////////////////////////////////////////////////////////////////////////////////////////////////// static int compute_quad_extremas(const SkPoint src[3], SkPoint extremas[3]) { … } static int compute_conic_extremas(const SkPoint src[3], SkScalar w, SkPoint extremas[3]) { … } static int compute_cubic_extremas(const SkPoint src[4], SkPoint extremas[5]) { … } SkRect SkPath::computeTightBounds() const { … } bool SkPath::IsLineDegenerate(const SkPoint& p1, const SkPoint& p2, bool exact) { … } bool SkPath::IsQuadDegenerate(const SkPoint& p1, const SkPoint& p2, const SkPoint& p3, bool exact) { … } bool SkPath::IsCubicDegenerate(const SkPoint& p1, const SkPoint& p2, const SkPoint& p3, const SkPoint& p4, bool exact) { … } ////////////////////////////////////////////////////////////////////////////////////////////////// SkPathVerbAnalysis sk_path_analyze_verbs(const uint8_t vbs[], int verbCount) { … } SkPath SkPath::Make(const SkPoint pts[], int pointCount, const uint8_t vbs[], int verbCount, const SkScalar ws[], int wCount, SkPathFillType ft, bool isVolatile) { … } SkPath SkPath::Rect(const SkRect& r, SkPathDirection dir, unsigned startIndex) { … } SkPath SkPath::Oval(const SkRect& r, SkPathDirection dir) { … } SkPath SkPath::Oval(const SkRect& r, SkPathDirection dir, unsigned startIndex) { … } SkPath SkPath::Circle(SkScalar x, SkScalar y, SkScalar r, SkPathDirection dir) { … } SkPath SkPath::RRect(const SkRRect& rr, SkPathDirection dir) { … } SkPath SkPath::RRect(const SkRRect& rr, SkPathDirection dir, unsigned startIndex) { … } SkPath SkPath::RRect(const SkRect& r, SkScalar rx, SkScalar ry, SkPathDirection dir) { … } SkPath SkPath::Polygon(const SkPoint pts[], int count, bool isClosed, SkPathFillType ft, bool isVolatile) { … } SkPath SkPath::MakeInternal(const SkPathVerbAnalysis& analysis, const SkPoint points[], const uint8_t verbs[], int verbCount, const SkScalar conics[], SkPathFillType fillType, bool isVolatile) { … } ////////////////////////////////////////////////////////////////////////////////////////////////// bool SkPathPriv::IsRectContour(const SkPath& path, bool allowPartial, int* currVerb, const SkPoint** ptsPtr, bool* isClosed, SkPathDirection* direction, SkRect* rect) { … } bool SkPathPriv::IsNestedFillRects(const SkPath& path, SkRect rects[2], SkPathDirection dirs[2]) { … } /////////////////////////////////////////////////////////////////////////////////////////////////// struct SkHalfPlane { … }; // assumes plane is pre-normalized // If we fail in our calculations, we return the empty path static SkPath clip(const SkPath& path, const SkHalfPlane& plane) { … } // true means we have written to clippedPath bool SkPathPriv::PerspectiveClip(const SkPath& path, const SkMatrix& matrix, SkPath* clippedPath) { … } int SkPathPriv::GenIDChangeListenersCount(const SkPath& path) { … } bool SkPathPriv::IsAxisAligned(const SkPath& path) { … } ////////////////////////////////////////////////////////////////////////////////////////////////// SkPathEdgeIter::SkPathEdgeIter(const SkPath& path) { … }
Codebase Browser
chromium