SkOpAngle.cpp | Explore in Territory

/*
 * Copyright 2012 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
#include "src/pathops/SkOpAngle.h"

#include "include/core/SkPoint.h"
#include "include/core/SkScalar.h"
#include "include/private/base/SkFloatingPoint.h"
#include "include/private/base/SkTemplates.h"
#include "src/base/SkTSort.h"
#include "src/pathops/SkIntersections.h"
#include "src/pathops/SkOpSegment.h"
#include "src/pathops/SkOpSpan.h"
#include "src/pathops/SkPathOpsCubic.h"
#include "src/pathops/SkPathOpsCurve.h"
#include "src/pathops/SkPathOpsLine.h"
#include "src/pathops/SkPathOpsPoint.h"

#include <algorithm>
#include <cmath>

/* Angles are sorted counterclockwise. The smallest angle has a positive x and the smallest
   positive y. The largest angle has a positive x and a zero y. */

#if DEBUG_ANGLE
    static bool CompareResult(const char* func, SkString* bugOut, SkString* bugPart, int append,
             bool compare) {
        SkDebugf("%s %c %d\n", bugOut->c_str(), compare ? 'T' : 'F', append);
        SkDebugf("%sPart %s\n", func, bugPart[0].c_str());
        SkDebugf("%sPart %s\n", func, bugPart[1].c_str());
        SkDebugf("%sPart %s\n", func, bugPart[2].c_str());
        return compare;
    }

    #define COMPARE_RESULT …
#else
    #define COMPARE_RESULT(append, compare) …
#endif

/*             quarter angle values for sector

31   x > 0, y == 0              horizontal line (to the right)
0    x > 0, y == epsilon        quad/cubic horizontal tangent eventually going +y
1    x > 0, y > 0, x > y        nearer horizontal angle
2                  x + e == y   quad/cubic 45 going horiz
3    x > 0, y > 0, x == y       45 angle
4                  x == y + e   quad/cubic 45 going vert
5    x > 0, y > 0, x < y        nearer vertical angle
6    x == epsilon, y > 0        quad/cubic vertical tangent eventually going +x
7    x == 0, y > 0              vertical line (to the top)

                                      8  7  6
                                 9       |       5
                              10         |          4
                            11           |            3
                          12  \          |           / 2
                         13              |              1
                        14               |               0
                        15 --------------+------------- 31
                        16               |              30
                         17              |             29
                          18  /          |          \ 28
                            19           |           27
                              20         |         26
                                 21      |      25
                                     22 23 24
*/

// return true if lh < this < rh
bool SkOpAngle::after(SkOpAngle* test) { … }

int SkOpAngle::lineOnOneSide(const SkDPoint& origin, const SkDVector& line, const SkOpAngle* test,
        bool useOriginal) const { … }

// given a line, see if the opposite curve's convex hull is all on one side
// returns -1=not on one side    0=this CW of test   1=this CCW of test
int SkOpAngle::lineOnOneSide(const SkOpAngle* test, bool useOriginal) { … }

// experiment works only with lines for now
int SkOpAngle::linesOnOriginalSide(const SkOpAngle* test) { … }

// To sort the angles, all curves are translated to have the same starting point.
// If the curve's control point in its original position is on one side of a compared line,
// and translated is on the opposite side, reverse the previously computed order.
void SkOpAngle::alignmentSameSide(const SkOpAngle* test, int* order) const { … }

bool SkOpAngle::checkCrossesZero() const { … }

bool SkOpAngle::checkParallel(SkOpAngle* rh) { … }

// the original angle is too short to get meaningful sector information
// lengthen it until it is long enough to be meaningful or leave it unset if lengthening it
// would cause it to intersect one of the adjacent angles
bool SkOpAngle::computeSector() { … }

int SkOpAngle::convexHullOverlaps(const SkOpAngle* rh) { … }

// OPTIMIZATION: longest can all be either lazily computed here or precomputed in setup
double SkOpAngle::distEndRatio(double dist) const { … }

bool SkOpAngle::endsIntersect(SkOpAngle* rh) { … }

bool SkOpAngle::endToSide(const SkOpAngle* rh, bool* inside) const { … }

/*      y<0 y==0 y>0  x<0 x==0 x>0 xy<0 xy==0 xy>0
    0    x                      x               x
    1    x                      x          x
    2    x                      x    x
    3    x                  x        x
    4    x             x             x
    5    x             x                   x
    6    x             x                        x
    7         x        x                        x
    8             x    x                        x
    9             x    x                   x
    10            x    x             x
    11            x         x        x
    12            x             x    x
    13            x             x          x
    14            x             x               x
    15        x                 x               x
*/
int SkOpAngle::findSector(SkPath::Verb verb, double x, double y) const { … }

SkOpGlobalState* SkOpAngle::globalState() const { … }


// OPTIMIZE: if this loops to only one other angle, after first compare fails, insert on other side
// OPTIMIZE: return where insertion succeeded. Then, start next insertion on opposite side
bool SkOpAngle::insert(SkOpAngle* angle) { … }

SkOpSpanBase* SkOpAngle::lastMarked() const { … }

bool SkOpAngle::loopContains(const SkOpAngle* angle) const { … }

int SkOpAngle::loopCount() const { … }

bool SkOpAngle::merge(SkOpAngle* angle) { … }

double SkOpAngle::midT() const { … }

bool SkOpAngle::midToSide(const SkOpAngle* rh, bool* inside) const { … }

bool SkOpAngle::oppositePlanes(const SkOpAngle* rh) const { … }

int SkOpAngle::orderable(SkOpAngle* rh) { … }

// OPTIMIZE: if this shows up in a profile, add a previous pointer
// as is, this should be rarely called
SkOpAngle* SkOpAngle::previous() const { … }

SkOpSegment* SkOpAngle::segment() const { … }

void SkOpAngle::set(SkOpSpanBase* start, SkOpSpanBase* end) { … }

void SkOpAngle::setSpans() { … }

void SkOpAngle::setSector() { … }

SkOpSpan* SkOpAngle::starter() { … }

bool SkOpAngle::tangentsDiverge(const SkOpAngle* rh, double s0xt0) { … }
chromium/third_party/skia/src/pathops/SkOpAngle.cpp
