chromium/third_party/skia/src/pathops/SkPathOpsWinding.cpp

/*
 * Copyright 2015 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

// given a prospective edge, compute its initial winding by projecting a ray
// if the ray hits another edge
    // if the edge doesn't have a winding yet, hop up to that edge and start over
        // concern : check for hops forming a loop
    // if the edge is unsortable, or
    // the intersection is nearly at the ends, or
    // the tangent at the intersection is nearly coincident to the ray,
        // choose a different ray and try again
            // concern : if it is unable to succeed after N tries, try another edge? direction?
// if no edge is hit, compute the winding directly

// given the top span, project the most perpendicular ray and look for intersections
    // let's try up and then down. What the hey

// bestXY is initialized by caller with basePt

#include "include/core/SkPath.h"
#include "include/core/SkPoint.h"
#include "include/core/SkRect.h"
#include "include/core/SkScalar.h"
#include "include/core/SkTypes.h"
#include "include/private/base/SkDebug.h"
#include "include/private/base/SkMalloc.h"
#include "include/private/base/SkMath.h"
#include "include/private/base/SkTArray.h"
#include "src/base/SkArenaAlloc.h"
#include "src/base/SkTSort.h"
#include "src/pathops/SkOpContour.h"
#include "src/pathops/SkOpSegment.h"
#include "src/pathops/SkOpSpan.h"
#include "src/pathops/SkPathOpsBounds.h"
#include "src/pathops/SkPathOpsCurve.h"
#include "src/pathops/SkPathOpsPoint.h"
#include "src/pathops/SkPathOpsTypes.h"

#include <cmath>
#include <utility>

usingnamespaceskia_private;

enum class SkOpRayDir { … };

#if DEBUG_WINDING
const char* gDebugRayDirName[] = {
    "kLeft",
    "kTop",
    "kRight",
    "kBottom"
};
#endif

static int xy_index(SkOpRayDir dir) { … }

static SkScalar pt_xy(const SkPoint& pt, SkOpRayDir dir) { … }

static SkScalar pt_yx(const SkPoint& pt, SkOpRayDir dir) { … }

static double pt_dxdy(const SkDVector& v, SkOpRayDir dir) { … }

static double pt_dydx(const SkDVector& v, SkOpRayDir dir) { … }

static SkScalar rect_side(const SkRect& r, SkOpRayDir dir) { … }

static bool sideways_overlap(const SkRect& rect, const SkPoint& pt, SkOpRayDir dir) { … }

static bool less_than(SkOpRayDir dir) { … }

static bool ccw_dxdy(const SkDVector& v, SkOpRayDir dir) { … }

struct SkOpRayHit { … };

void SkOpContour::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits,
                           SkArenaAlloc* allocator) { … }

void SkOpSegment::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits,
                           SkArenaAlloc* allocator) { … }

SkOpSpan* SkOpSegment::windingSpanAtT(double tHit) { … }

static bool hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) { … }

static bool reverse_hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) { … }

static bool hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) { … }

static bool reverse_hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) { … }

static double get_t_guess(int tTry, int* dirOffset) { … }

bool SkOpSpan::sortableTop(SkOpContour* contourHead) { … }

SkOpSpan* SkOpSegment::findSortableTop(SkOpContour* contourHead) { … }

SkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) { … }

SkOpSpan* FindSortableTop(SkOpContourHead* contourHead) { … }