SkPathOpsAsWinding.cpp File Reference

#include "include/core/SkPath.h"
#include "include/core/SkPathBuilder.h"
#include "include/core/SkPathTypes.h"
#include "include/core/SkPoint.h"
#include "include/core/SkRect.h"
#include "include/core/SkScalar.h"
#include "include/core/SkTypes.h"
#include "include/pathops/SkPathOps.h"
#include "include/private/base/SkMacros.h"
#include "src/core/SkPathPriv.h"
#include "src/pathops/SkPathOpsConic.h"
#include "src/pathops/SkPathOpsCubic.h"
#include "src/pathops/SkPathOpsCurve.h"
#include "src/pathops/SkPathOpsPoint.h"
#include "src/pathops/SkPathOpsQuad.h"
#include "src/pathops/SkPathOpsTypes.h"
#include <algorithm>
#include <vector>

Go to the source code of this file.

Classes
struct	Contour
class	OpAsWinding

Functions
static Contour::Direction	to_direction (SkScalar dy)
static int	contains_edge (SkPoint pts[4], SkPath::Verb verb, SkScalar weight, const SkPoint &edge)
static SkScalar	conic_weight (const SkPath::Iter &iter, SkPath::Verb verb)
static SkPoint	left_edge (SkPoint pts[4], SkPath::Verb verb, SkScalar weight)
static bool	set_result_path (SkPath *result, const SkPath &path, SkPathFillType fillType)
bool	AsWinding (const SkPath &path, SkPath *result)

Variables
static const int	kPtCount [] = { 1, 1, 2, 2, 3, 0 }
static const int	kPtIndex [] = { 0, 1, 1, 1, 1, 0 }

Function Documentation

AsWinding()

bool AsWinding	(	const SkPath &	path,
		SkPath *	result
	)

Set the result with fill type winding to area equivalent to path. Returns true if successful. Does not detect if path contains contours which contain self-crossings or cross other contours; in these cases, may return true even though result does not fill same area as path.

Returns true if operation was able to produce a result; otherwise, result is unmodified. The result may be the input.

Parameters

path	The path typically with fill type set to even odd.
result	The equivalent path with fill type set to winding.

Returns

True if winding path was set.

Definition at line 408 of file SkPathOpsAsWinding.cpp.

                                                   {
    if (!path.isFinite()) {
        return false;
    }
    SkPathFillType fillType = path.getFillType();
    if (fillType == SkPathFillType::kWinding
            || fillType == SkPathFillType::kInverseWinding ) {
        return set_result_path(result, path, fillType);
    }
    fillType = path.isInverseFillType() ? SkPathFillType::kInverseWinding :
            SkPathFillType::kWinding;
    if (path.isEmpty() || path.isConvex()) {
        return set_result_path(result, path, fillType);
    }
    // count contours
    vector<Contour> contours;   // one per contour
    OpAsWinding winder(path);
    winder.contourBounds(&contours);
    if (contours.size() <= 1) {
        return set_result_path(result, path, fillType);
    }
    // create contour bounding box tree
    Contour sorted(SkRect(), 0, 0);
    for (auto& contour : contours) {
        winder.inParent(contour, sorted);
    }
    // if sorted has no grandchildren, no child has to fix its children's winding
    if (std::all_of(sorted.fChildren.begin(), sorted.fChildren.end(),
            [](const Contour* contour) -> bool { return contour->fChildren.empty(); } )) {
        return set_result_path(result, path, fillType);
    }
    // starting with outermost and moving inward, see if one path contains another
    for (auto contour : sorted.fChildren) {
        winder.nextEdge(*contour, OpAsWinding::Edge::kInitial);
        contour->fDirection = winder.getDirection(*contour);
        if (!winder.checkContainerChildren(nullptr, contour)) {
            return false;
        }
    }
    // starting with outermost and moving inward, mark paths to reverse
    bool reversed = false;
    for (auto contour : sorted.fChildren) {
        reversed |= winder.markReverse(nullptr, contour);
    }
    if (!reversed) {
        return set_result_path(result, path, fillType);
    }
    *result = winder.reverseMarkedContours(contours, fillType);
    return true;
}

conic_weight()

static SkScalar conic_weight ( const SkPath::Iter &  iter, SkPath::Verb  verb  )

static

Definition at line 113 of file SkPathOpsAsWinding.cpp.

                                                                      {
    return SkPath::kConic_Verb == verb ? iter.conicWeight() : 1;
}

contains_edge()

static int contains_edge ( SkPoint  pts[4], SkPath::Verb  verb, SkScalar  weight, const SkPoint &  edge  )

static

Definition at line 60 of file SkPathOpsAsWinding.cpp.

                                                                                                {
    SkRect bounds;
    bounds.setBounds(pts, kPtCount[verb] + 1);
    if (bounds.fTop > edge.fY) {
        return 0;
    }
    if (bounds.fBottom <= edge.fY) {  // check to see if y is at line end to avoid double counting
        return 0;
    }
    if (bounds.fLeft >= edge.fX) {
        return 0;
    }
    int winding = 0;
    double tVals[3];
    Contour::Direction directions[3];
    // must intersect horz ray with curve in case it intersects more than once
    int count = (*CurveIntercept[verb * 2])(pts, weight, edge.fY, tVals);
    SkASSERT(between(0, count, 3));
    // remove results to the right of edge
    for (int index = 0; index < count; ) {
        SkScalar intersectX = (*CurvePointAtT[verb])(pts, weight, tVals[index]).fX;
        if (intersectX < edge.fX) {
            ++index;
            continue;
        }
        if (intersectX > edge.fX) {
            tVals[index] = tVals[--count];
            continue;
        }
        // if intersect x equals edge x, we need to determine if pts is to the left or right of edge
        if (pts[0].fX < edge.fX && pts[kPtCount[verb]].fX < edge.fX) {
            ++index;
            continue;
        }
        // TODO : other cases need discriminating. need op angle code to figure it out
        // example: edge ends 45 degree diagonal going up. If pts is to the left of edge, keep.
        // if pts is to the right of edge, discard. With code as is, can't distiguish the two cases.
        tVals[index] = tVals[--count];
    }
    // use first derivative to determine if intersection is contributing +1 or -1 to winding
    for (int index = 0; index < count; ++index) {
        directions[index] = to_direction((*CurveSlopeAtT[verb])(pts, weight, tVals[index]).fY);
    }
    for (int index = 0; index < count; ++index) {
        // skip intersections that end at edge and go up
        if (zero_or_one(tVals[index]) && Contour::Direction::kCCW != directions[index]) {
            continue;
        }
        winding += (int) directions[index];
    }
    return winding;  // note winding indicates containership, not contour direction
}

left_edge()

static SkPoint left_edge ( SkPoint  pts[4], SkPath::Verb  verb, SkScalar  weight  )

static

Definition at line 117 of file SkPathOpsAsWinding.cpp.

                                                                           {
    SkASSERT(SkPath::kLine_Verb <= verb && verb <= SkPath::kCubic_Verb);
    SkPoint result;
    double t SK_INIT_TO_AVOID_WARNING;
    int roots = 0;
    if (SkPath::kLine_Verb == verb) {
        result = pts[0].fX < pts[1].fX ? pts[0] : pts[1];
    } else if (SkPath::kQuad_Verb == verb) {
        SkDQuad quad;
        quad.set(pts);
        if (!quad.monotonicInX()) {
            roots = SkDQuad::FindExtrema(&quad[0].fX, &t);
        }
        if (roots) {
            result = quad.ptAtT(t).asSkPoint();
        } else {
            result = pts[0].fX < pts[2].fX ? pts[0] : pts[2];
        }
    } else if (SkPath::kConic_Verb == verb) {
        SkDConic conic;
        conic.set(pts, weight);
        if (!conic.monotonicInX()) {
            roots = SkDConic::FindExtrema(&conic[0].fX, weight, &t);
        }
        if (roots) {
            result = conic.ptAtT(t).asSkPoint();
        } else {
            result = pts[0].fX < pts[2].fX ? pts[0] : pts[2];
        }
    } else {
        SkASSERT(SkPath::kCubic_Verb == verb);
        SkDCubic cubic;
        cubic.set(pts);
        if (!cubic.monotonicInX()) {
            double tValues[2];
            roots = SkDCubic::FindExtrema(&cubic[0].fX, tValues);
            SkASSERT(roots <= 2);
            for (int index = 0; index < roots; ++index) {
                SkPoint temp = cubic.ptAtT(tValues[index]).asSkPoint();
                if (0 == index || result.fX > temp.fX) {
                    result = temp;
                }
            }
        }
        if (roots) {
            result = cubic.ptAtT(t).asSkPoint();
        } else {
            result = pts[0].fX < pts[3].fX ? pts[0] : pts[3];
        }
    }
    return result;
}

set_result_path()

static bool set_result_path ( SkPath *  result, const SkPath &  path, SkPathFillType  fillType  )

static

Definition at line 402 of file SkPathOpsAsWinding.cpp.

                                                                                         {
    *result = path;
    result->setFillType(fillType);
    return true;
}

to_direction()

static Contour::Direction to_direction ( SkScalar  dy )

static

Definition at line 55 of file SkPathOpsAsWinding.cpp.

                                                  {
    return dy > 0 ? Contour::Direction::kCCW : dy < 0 ? Contour::Direction::kCW :
            Contour::Direction::kNone;
}

Variable Documentation

kPtCount

const int kPtCount[] = { 1, 1, 2, 2, 3, 0 }

static

Definition at line 52 of file SkPathOpsAsWinding.cpp.

{ 1, 1, 2, 2, 3, 0 };

kPtIndex

const int kPtIndex[] = { 0, 1, 1, 1, 1, 0 }

static

Definition at line 53 of file SkPathOpsAsWinding.cpp.

{ 0, 1, 1, 1, 1, 0 };