Google Git
Sign in
skia / skia / 8e712021de51eadb887c4aa6b18ceb4bf3f78f07 / . / experimental / Intersection / Simplify.cpp
blob: d99cdf315e92d5c649835635d047e1d4d6cbb249 [file] [log] [blame]
/*
* 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 "Simplify.h"
#undef SkASSERT
#define SkASSERT(cond) while (!(cond)) { sk_throw(); }
// Terminology:
// A Path contains one of more Contours
// A Contour is made up of Segment array
// A Segment is described by a Verb and a Point array with 2, 3, or 4 points
// A Verb is one of Line, Quad(ratic), or Cubic
// A Segment contains a Span array
// A Span is describes a portion of a Segment using starting and ending T
// T values range from 0 to 1, where 0 is the first Point in the Segment
// An Edge is a Segment generated from a Span
// FIXME: remove once debugging is complete
#ifdef SK_DEBUG
int gDebugMaxWindSum = SK_MaxS32;
int gDebugMaxWindValue = SK_MaxS32;
#endif
#define PIN_ADD_T 0
#define TRY_ROTATE 1
#define ONE_PASS_COINCIDENCE_CHECK 0
#define APPROXIMATE_CUBICS 1
#define COMPACT_DEBUG_SORT 0
#define DEBUG_UNUSED 0 // set to expose unused functions
#if FORCE_RELEASE || defined SK_RELEASE
const bool gRunTestsInOneThread = false;
#define DEBUG_ACTIVE_OP 0
#define DEBUG_ACTIVE_SPANS 0
#define DEBUG_ACTIVE_SPANS_SHORT_FORM 0
#define DEBUG_ADD_INTERSECTING_TS 0
#define DEBUG_ADD_T_PAIR 0
#define DEBUG_ANGLE 0
#define DEBUG_AS_C_CODE 1
#define DEBUG_ASSEMBLE 0
#define DEBUG_CONCIDENT 0
#define DEBUG_CROSS 0
#define DEBUG_FLOW 0
#define DEBUG_MARK_DONE 0
#define DEBUG_PATH_CONSTRUCTION 0
#define DEBUG_SHOW_WINDING 0
#define DEBUG_SORT 0
#define DEBUG_SWAP_TOP 0
#define DEBUG_UNSORTABLE 0
#define DEBUG_WIND_BUMP 0
#define DEBUG_WINDING 0
#define DEBUG_WINDING_AT_T 0
#else
const bool gRunTestsInOneThread = true;
#define DEBUG_ACTIVE_OP 1
#define DEBUG_ACTIVE_SPANS 1
#define DEBUG_ACTIVE_SPANS_SHORT_FORM 0
#define DEBUG_ADD_INTERSECTING_TS 1
#define DEBUG_ADD_T_PAIR 1
#define DEBUG_ANGLE 1
#define DEBUG_AS_C_CODE 1
#define DEBUG_ASSEMBLE 1
#define DEBUG_CONCIDENT 1
#define DEBUG_CROSS 0
#define DEBUG_FLOW 1
#define DEBUG_MARK_DONE 1
#define DEBUG_PATH_CONSTRUCTION 1
#define DEBUG_SHOW_WINDING 0
#define DEBUG_SORT 1
#define DEBUG_SWAP_TOP 1
#define DEBUG_UNSORTABLE 1
#define DEBUG_WIND_BUMP 0
#define DEBUG_WINDING 1
#define DEBUG_WINDING_AT_T 1
#endif
#define DEBUG_DUMP (DEBUG_ACTIVE_OP | DEBUG_ACTIVE_SPANS | DEBUG_CONCIDENT | DEBUG_SORT | \
DEBUG_PATH_CONSTRUCTION)
#if DEBUG_AS_C_CODE
#define CUBIC_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
#define QUAD_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}, {%1.17g,%1.17g}}"
#define LINE_DEBUG_STR "{{%1.17g,%1.17g}, {%1.17g,%1.17g}}"
#define PT_DEBUG_STR "{{%1.17g,%1.17g}}"
#else
#define CUBIC_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
#define QUAD_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)"
#define LINE_DEBUG_STR "(%1.9g,%1.9g %1.9g,%1.9g)"
#define PT_DEBUG_STR "(%1.9g,%1.9g)"
#endif
#define T_DEBUG_STR(t, n) #t "[" #n "]=%1.9g"
#define TX_DEBUG_STR(t) #t "[%d]=%1.9g"
#define CUBIC_DEBUG_DATA(c) c[0].fX, c[0].fY, c[1].fX, c[1].fY, c[2].fX, c[2].fY, c[3].fX, c[3].fY
#define QUAD_DEBUG_DATA(q) q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY
#define LINE_DEBUG_DATA(l) l[0].fX, l[0].fY, l[1].fX, l[1].fY
#define PT_DEBUG_DATA(i, n) i.fPt[n].x, i.fPt[n].y
#if DEBUG_DUMP
static const char* kLVerbStr[] = {"", "line", "quad", "cubic"};
// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"};
static int gContourID;
static int gSegmentID;
#endif
#if DEBUG_SORT || DEBUG_SWAP_TOP
static int gDebugSortCountDefault = SK_MaxS32;
static int gDebugSortCount;
#endif
#if DEBUG_ACTIVE_OP
static const char* kShapeOpStr[] = {"diff", "sect", "union", "xor"};
#endif
#ifndef DEBUG_TEST
#define DEBUG_TEST 0
#endif
#define MAKE_CONST_LINE(line, pts) \
const _Line line = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}}
#define MAKE_CONST_QUAD(quad, pts) \
const Quadratic quad = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \
{pts[2].fX, pts[2].fY}}
#define MAKE_CONST_CUBIC(cubic, pts) \
const Cubic cubic = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}, \
{pts[2].fX, pts[2].fY}, {pts[3].fX, pts[3].fY}}
static int LineIntersect(const SkPoint a[2], const SkPoint b[2],
Intersections& intersections) {
MAKE_CONST_LINE(aLine, a);
MAKE_CONST_LINE(bLine, b);
return intersect(aLine, bLine, intersections);
}
static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2],
Intersections& intersections) {
MAKE_CONST_QUAD(aQuad, a);
MAKE_CONST_LINE(bLine, b);
return intersect(aQuad, bLine, intersections);
}
static int CubicLineIntersect(const SkPoint a[4], const SkPoint b[2],
Intersections& intersections) {
MAKE_CONST_CUBIC(aCubic, a);
MAKE_CONST_LINE(bLine, b);
return intersect(aCubic, bLine, intersections);
}
static int QuadIntersect(const SkPoint a[3], const SkPoint b[3],
Intersections& intersections) {
MAKE_CONST_QUAD(aQuad, a);
MAKE_CONST_QUAD(bQuad, b);
#define TRY_QUARTIC_SOLUTION 1
#if TRY_QUARTIC_SOLUTION
intersect2(aQuad, bQuad, intersections);
#else
intersect(aQuad, bQuad, intersections);
#endif
return intersections.fUsed;
}
#if APPROXIMATE_CUBICS
static int CubicQuadIntersect(const SkPoint a[4], const SkPoint b[3],
Intersections& intersections) {
MAKE_CONST_CUBIC(aCubic, a);
MAKE_CONST_QUAD(bQuad, b);
return intersect(aCubic, bQuad, intersections);
}
#endif
static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], Intersections& intersections) {
MAKE_CONST_CUBIC(aCubic, a);
MAKE_CONST_CUBIC(bCubic, b);
#if APPROXIMATE_CUBICS
intersect3(aCubic, bCubic, intersections);
#else
intersect(aCubic, bCubic, intersections);
#endif
return intersections.fUsed;
}
static int CubicIntersect(const SkPoint a[4], Intersections& intersections) {
MAKE_CONST_CUBIC(aCubic, a);
return intersect(aCubic, intersections);
}
static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right,
SkScalar y, bool flipped, Intersections& intersections) {
MAKE_CONST_LINE(aLine, a);
return horizontalIntersect(aLine, left, right, y, flipped, intersections);
}
static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right,
SkScalar y, bool flipped, Intersections& intersections) {
MAKE_CONST_QUAD(aQuad, a);
return horizontalIntersect(aQuad, left, right, y, flipped, intersections);
}
static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right,
SkScalar y, bool flipped, Intersections& intersections) {
MAKE_CONST_CUBIC(aCubic, a);
return horizontalIntersect(aCubic, left, right, y, flipped, intersections);
}
static int (* const HSegmentIntersect[])(const SkPoint [], SkScalar ,
SkScalar , SkScalar , bool , Intersections& ) = {
NULL,
HLineIntersect,
HQuadIntersect,
HCubicIntersect
};
static int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom,
SkScalar x, bool flipped, Intersections& intersections) {
MAKE_CONST_LINE(aLine, a);
return verticalIntersect(aLine, top, bottom, x, flipped, intersections);
}
static int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom,
SkScalar x, bool flipped, Intersections& intersections) {
MAKE_CONST_QUAD(aQuad, a);
return verticalIntersect(aQuad, top, bottom, x, flipped, intersections);
}
static int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom,
SkScalar x, bool flipped, Intersections& intersections) {
MAKE_CONST_CUBIC(aCubic, a);
return verticalIntersect(aCubic, top, bottom, x, flipped, intersections);
}
static int (* const VSegmentIntersect[])(const SkPoint [], SkScalar ,
SkScalar , SkScalar , bool , Intersections& ) = {
NULL,
VLineIntersect,
VQuadIntersect,
VCubicIntersect
};
static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) {
MAKE_CONST_LINE(line, a);
double x, y;
xy_at_t(line, t, x, y);
out->fX = SkDoubleToScalar(x);
out->fY = SkDoubleToScalar(y);
}
static void LineXYAtT(const SkPoint a[2], double t, _Point* out) {
MAKE_CONST_LINE(line, a);
xy_at_t(line, t, out->x, out->y);
}
static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) {
MAKE_CONST_QUAD(quad, a);
double x, y;
xy_at_t(quad, t, x, y);
out->fX = SkDoubleToScalar(x);
out->fY = SkDoubleToScalar(y);
}
static void QuadXYAtT(const SkPoint a[3], double t, _Point* out) {
MAKE_CONST_QUAD(quad, a);
xy_at_t(quad, t, out->x, out->y);
}
static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) {
MAKE_CONST_CUBIC(cubic, a);
double x, y;
xy_at_t(cubic, t, x, y);
out->fX = SkDoubleToScalar(x);
out->fY = SkDoubleToScalar(y);
}
static void CubicXYAtT(const SkPoint a[4], double t, _Point* out) {
MAKE_CONST_CUBIC(cubic, a);
xy_at_t(cubic, t, out->x, out->y);
}
static void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = {
NULL,
LineXYAtT,
QuadXYAtT,
CubicXYAtT
};
static void (* const SegmentXYAtT2[])(const SkPoint [], double , _Point* ) = {
NULL,
LineXYAtT,
QuadXYAtT,
CubicXYAtT
};
static SkScalar LineXAtT(const SkPoint a[2], double t) {
MAKE_CONST_LINE(aLine, a);
double x;
xy_at_t(aLine, t, x, *(double*) 0);
return SkDoubleToScalar(x);
}
static SkScalar QuadXAtT(const SkPoint a[3], double t) {
MAKE_CONST_QUAD(quad, a);
double x;
xy_at_t(quad, t, x, *(double*) 0);
return SkDoubleToScalar(x);
}
static SkScalar CubicXAtT(const SkPoint a[4], double t) {
MAKE_CONST_CUBIC(cubic, a);
double x;
xy_at_t(cubic, t, x, *(double*) 0);
return SkDoubleToScalar(x);
}
static SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = {
NULL,
LineXAtT,
QuadXAtT,
CubicXAtT
};
static SkScalar LineYAtT(const SkPoint a[2], double t) {
MAKE_CONST_LINE(aLine, a);
double y;
xy_at_t(aLine, t, *(double*) 0, y);
return SkDoubleToScalar(y);
}
static SkScalar QuadYAtT(const SkPoint a[3], double t) {
MAKE_CONST_QUAD(quad, a);
double y;
xy_at_t(quad, t, *(double*) 0, y);
return SkDoubleToScalar(y);
}
static SkScalar CubicYAtT(const SkPoint a[4], double t) {
MAKE_CONST_CUBIC(cubic, a);
double y;
xy_at_t(cubic, t, *(double*) 0, y);
return SkDoubleToScalar(y);
}
static SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = {
NULL,
LineYAtT,
QuadYAtT,
CubicYAtT
};
static SkScalar LineDXAtT(const SkPoint a[2], double ) {
return a[1].fX - a[0].fX;
}
static SkScalar QuadDXAtT(const SkPoint a[3], double t) {
MAKE_CONST_QUAD(quad, a);
double x = dx_at_t(quad, t);
return SkDoubleToScalar(x);
}
static SkScalar CubicDXAtT(const SkPoint a[4], double t) {
MAKE_CONST_CUBIC(cubic, a);
double x = dx_at_t(cubic, t);
return SkDoubleToScalar(x);
}
static SkScalar (* const SegmentDXAtT[])(const SkPoint [], double ) = {
NULL,
LineDXAtT,
QuadDXAtT,
CubicDXAtT
};
static SkScalar LineDYAtT(const SkPoint a[2], double ) {
return a[1].fY - a[0].fY;
}
static SkScalar QuadDYAtT(const SkPoint a[3], double t) {
MAKE_CONST_QUAD(quad, a);
double y = dy_at_t(quad, t);
return SkDoubleToScalar(y);
}
static SkScalar CubicDYAtT(const SkPoint a[4], double t) {
MAKE_CONST_CUBIC(cubic, a);
double y = dy_at_t(cubic, t);
return SkDoubleToScalar(y);
}
static SkScalar (* const SegmentDYAtT[])(const SkPoint [], double ) = {
NULL,
LineDYAtT,
QuadDYAtT,
CubicDYAtT
};
static SkVector LineDXDYAtT(const SkPoint a[2], double ) {
return a[1] - a[0];
}
static SkVector QuadDXDYAtT(const SkPoint a[3], double t) {
MAKE_CONST_QUAD(quad, a);
_Vector v = dxdy_at_t(quad, t);
return v.asSkVector();
}
static SkVector CubicDXDYAtT(const SkPoint a[4], double t) {
MAKE_CONST_CUBIC(cubic, a);
_Vector v = dxdy_at_t(cubic, t);
return v.asSkVector();
}
static SkVector (* const SegmentDXDYAtT[])(const SkPoint [], double ) = {
NULL,
LineDXDYAtT,
QuadDXDYAtT,
CubicDXDYAtT
};
static void LineSubDivide(const SkPoint a[2], double startT, double endT,
SkPoint sub[2]) {
MAKE_CONST_LINE(aLine, a);
_Line dst;
sub_divide(aLine, startT, endT, dst);
sub[0].fX = SkDoubleToScalar(dst[0].x);
sub[0].fY = SkDoubleToScalar(dst[0].y);
sub[1].fX = SkDoubleToScalar(dst[1].x);
sub[1].fY = SkDoubleToScalar(dst[1].y);
}
static void QuadSubDivide(const SkPoint a[3], double startT, double endT,
SkPoint sub[3]) {
MAKE_CONST_QUAD(aQuad, a);
Quadratic dst;
sub_divide(aQuad, startT, endT, dst);
sub[0].fX = SkDoubleToScalar(dst[0].x);
sub[0].fY = SkDoubleToScalar(dst[0].y);
sub[1].fX = SkDoubleToScalar(dst[1].x);
sub[1].fY = SkDoubleToScalar(dst[1].y);
sub[2].fX = SkDoubleToScalar(dst[2].x);
sub[2].fY = SkDoubleToScalar(dst[2].y);
}
static void CubicSubDivide(const SkPoint a[4], double startT, double endT,
SkPoint sub[4]) {
MAKE_CONST_CUBIC(aCubic, a);
Cubic dst;
sub_divide(aCubic, startT, endT, dst);
sub[0].fX = SkDoubleToScalar(dst[0].x);
sub[0].fY = SkDoubleToScalar(dst[0].y);
sub[1].fX = SkDoubleToScalar(dst[1].x);
sub[1].fY = SkDoubleToScalar(dst[1].y);
sub[2].fX = SkDoubleToScalar(dst[2].x);
sub[2].fY = SkDoubleToScalar(dst[2].y);
sub[3].fX = SkDoubleToScalar(dst[3].x);
sub[3].fY = SkDoubleToScalar(dst[3].y);
}
static void (* const SegmentSubDivide[])(const SkPoint [], double , double ,
SkPoint []) = {
NULL,
LineSubDivide,
QuadSubDivide,
CubicSubDivide
};
static void LineSubDivideHD(const SkPoint a[2], double startT, double endT, _Line& dst) {
MAKE_CONST_LINE(aLine, a);
sub_divide(aLine, startT, endT, dst);
}
static void QuadSubDivideHD(const SkPoint a[3], double startT, double endT, Quadratic& dst) {
MAKE_CONST_QUAD(aQuad, a);
sub_divide(aQuad, startT, endT, dst);
}
static void CubicSubDivideHD(const SkPoint a[4], double startT, double endT, Cubic& dst) {
MAKE_CONST_CUBIC(aCubic, a);
sub_divide(aCubic, startT, endT, dst);
}
static SkPoint QuadTop(const SkPoint a[3], double startT, double endT) {
MAKE_CONST_QUAD(quad, a);
_Point topPt = top(quad, startT, endT);
return topPt.asSkPoint();
}
static SkPoint CubicTop(const SkPoint a[3], double startT, double endT) {
MAKE_CONST_CUBIC(cubic, a);
_Point topPt = top(cubic, startT, endT);
return topPt.asSkPoint();
}
static SkPoint (* SegmentTop[])(const SkPoint[], double , double ) = {
NULL,
NULL,
QuadTop,
CubicTop
};
#if DEBUG_UNUSED
static void QuadSubBounds(const SkPoint a[3], double startT, double endT,
SkRect& bounds) {
SkPoint dst[3];
QuadSubDivide(a, startT, endT, dst);
bounds.fLeft = bounds.fRight = dst[0].fX;
bounds.fTop = bounds.fBottom = dst[0].fY;
for (int index = 1; index < 3; ++index) {
bounds.growToInclude(dst[index].fX, dst[index].fY);
}
}
static void CubicSubBounds(const SkPoint a[4], double startT, double endT,
SkRect& bounds) {
SkPoint dst[4];
CubicSubDivide(a, startT, endT, dst);
bounds.fLeft = bounds.fRight = dst[0].fX;
bounds.fTop = bounds.fBottom = dst[0].fY;
for (int index = 1; index < 4; ++index) {
bounds.growToInclude(dst[index].fX, dst[index].fY);
}
}
#endif
static SkPath::Verb QuadReduceOrder(const SkPoint a[3],
SkTDArray<SkPoint>& reducePts) {
MAKE_CONST_QUAD(aQuad, a);
Quadratic dst;
int order = reduceOrder(aQuad, dst, kReduceOrder_TreatAsFill);
if (order == 2) { // quad became line
for (int index = 0; index < order; ++index) {
SkPoint* pt = reducePts.append();
pt->fX = SkDoubleToScalar(dst[index].x);
pt->fY = SkDoubleToScalar(dst[index].y);
}
}
return (SkPath::Verb) (order - 1);
}
static SkPath::Verb CubicReduceOrder(const SkPoint a[4],
SkTDArray<SkPoint>& reducePts) {
MAKE_CONST_CUBIC(aCubic, a);
Cubic dst;
int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed, kReduceOrder_TreatAsFill);
if (order == 2 || order == 3) { // cubic became line or quad
for (int index = 0; index < order; ++index) {
SkPoint* pt = reducePts.append();
pt->fX = SkDoubleToScalar(dst[index].x);
pt->fY = SkDoubleToScalar(dst[index].y);
}
}
return (SkPath::Verb) (order - 1);
}
static bool QuadIsLinear(const SkPoint a[3]) {
MAKE_CONST_QUAD(aQuad, a);
return isLinear(aQuad, 0, 2);
}
static bool CubicIsLinear(const SkPoint a[4]) {
MAKE_CONST_CUBIC(aCubic, a);
return isLinear(aCubic, 0, 3);
}
static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) {
MAKE_CONST_LINE(aLine, a);
double x[2];
xy_at_t(aLine, startT, x[0], *(double*) 0);
xy_at_t(aLine, endT, x[1], *(double*) 0);
return SkMinScalar((float) x[0], (float) x[1]);
}
static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) {
MAKE_CONST_QUAD(aQuad, a);
return (float) leftMostT(aQuad, startT, endT);
}
static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) {
MAKE_CONST_CUBIC(aCubic, a);
return (float) leftMostT(aCubic, startT, endT);
}
static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = {
NULL,
LineLeftMost,
QuadLeftMost,
CubicLeftMost
};
#if 0 // currently unused
static int QuadRayIntersect(const SkPoint a[3], const SkPoint b[2],
Intersections& intersections) {
MAKE_CONST_QUAD(aQuad, a);
MAKE_CONST_LINE(bLine, b);
return intersectRay(aQuad, bLine, intersections);
}
#endif
static int QuadRayIntersect(const SkPoint a[3], const _Line& bLine, Intersections& intersections) {
MAKE_CONST_QUAD(aQuad, a);
return intersectRay(aQuad, bLine, intersections);
}
static int CubicRayIntersect(const SkPoint a[3], const _Line& bLine, Intersections& intersections) {
MAKE_CONST_CUBIC(aCubic, a);
return intersectRay(aCubic, bLine, intersections);
}
static int (* const SegmentRayIntersect[])(const SkPoint [], const _Line& , Intersections&) = {
NULL,
NULL,
QuadRayIntersect,
CubicRayIntersect
};
static bool LineVertical(const SkPoint a[2], double startT, double endT) {
MAKE_CONST_LINE(aLine, a);
double x[2];
xy_at_t(aLine, startT, x[0], *(double*) 0);
xy_at_t(aLine, endT, x[1], *(double*) 0);
return AlmostEqualUlps((float) x[0], (float) x[1]);
}
static bool QuadVertical(const SkPoint a[3], double startT, double endT) {
SkPoint dst[3];
QuadSubDivide(a, startT, endT, dst);
return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX);
}
static bool CubicVertical(const SkPoint a[4], double startT, double endT) {
SkPoint dst[4];
CubicSubDivide(a, startT, endT, dst);
return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX)
&& AlmostEqualUlps(dst[2].fX, dst[3].fX);
}
static bool (* const SegmentVertical[])(const SkPoint [], double , double) = {
NULL,
LineVertical,
QuadVertical,
CubicVertical
};
class Segment;
struct Span {
Segment* fOther;
mutable SkPoint fPt; // lazily computed as needed
double fT;
double fOtherT; // value at fOther[fOtherIndex].fT
int fOtherIndex; // can't be used during intersection
int fWindSum; // accumulated from contours surrounding this one.
int fOppSum; // for binary operators: the opposite winding sum
int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident
int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here
bool fDone; // if set, this span to next higher T has been processed
bool fUnsortableStart; // set when start is part of an unsortable pair
bool fUnsortableEnd; // set when end is part of an unsortable pair
bool fTiny; // if set, span may still be considered once for edge following
bool fLoop; // set when a cubic loops back to this point
};
// sorting angles
// given angles of {dx dy ddx ddy dddx dddy} sort them
class Angle {
public:
// FIXME: this is bogus for quads and cubics
// if the quads and cubics' line from end pt to ctrl pt are coincident,
// there's no obvious way to determine the curve ordering from the
// derivatives alone. In particular, if one quadratic's coincident tangent
// is longer than the other curve, the final control point can place the
// longer curve on either side of the shorter one.
// Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
// may provide some help, but nothing has been figured out yet.
/*(
for quads and cubics, set up a parameterized line (e.g. LineParameters )
for points [0] to [1]. See if point [2] is on that line, or on one side
or the other. If it both quads' end points are on the same side, choose
the shorter tangent. If the tangents are equal, choose the better second
tangent angle
maybe I could set up LineParameters lazily
*/
bool operator<(const Angle& rh) const {
double y = dy();
double ry = rh.dy();
if ((y < 0) ^ (ry < 0)) { // OPTIMIZATION: better to use y * ry < 0 ?
return y < 0;
}
double x = dx();
double rx = rh.dx();
if (y == 0 && ry == 0 && x * rx < 0) {
return x < rx;
}
double x_ry = x * ry;
double rx_y = rx * y;
double cmp = x_ry - rx_y;
if (!approximately_zero(cmp)) {
return cmp < 0;
}
if (approximately_zero(x_ry) && approximately_zero(rx_y)
&& !approximately_zero_squared(cmp)) {
return cmp < 0;
}
// at this point, the initial tangent line is coincident
// see if edges curl away from each other
if (fSide * rh.fSide <= 0 && (!approximately_zero(fSide)
|| !approximately_zero(rh.fSide))) {
// FIXME: running demo will trigger this assertion
// (don't know if commenting out will trigger further assertion or not)
// commenting it out allows demo to run in release, though
// SkASSERT(fSide != rh.fSide);
return fSide < rh.fSide;
}
// see if either curve can be lengthened and try the tangent compare again
if (cmp && (*fSpans)[fEnd].fOther != rh.fSegment // tangents not absolutely identical
&& (*rh.fSpans)[rh.fEnd].fOther != fSegment) { // and not intersecting
Angle longer = *this;
Angle rhLonger = rh;
if (longer.lengthen() | rhLonger.lengthen()) {
return longer < rhLonger;
}
#if 0
// what if we extend in the other direction?
longer = *this;
rhLonger = rh;
if (longer.reverseLengthen() | rhLonger.reverseLengthen()) {
return longer < rhLonger;
}
#endif
}
if ((fVerb == SkPath::kLine_Verb && approximately_zero(x) && approximately_zero(y))
|| (rh.fVerb == SkPath::kLine_Verb
&& approximately_zero(rx) && approximately_zero(ry))) {
// See general unsortable comment below. This case can happen when
// one line has a non-zero change in t but no change in x and y.
fUnsortable = true;
rh.fUnsortable = true;
return this < &rh; // even with no solution, return a stable sort
}
if ((*rh.fSpans)[SkMin32(rh.fStart, rh.fEnd)].fTiny
|| (*fSpans)[SkMin32(fStart, fEnd)].fTiny) {
fUnsortable = true;
rh.fUnsortable = true;
return this < &rh; // even with no solution, return a stable sort
}
SkASSERT(fVerb >= SkPath::kQuad_Verb);
SkASSERT(rh.fVerb >= SkPath::kQuad_Verb);
// FIXME: until I can think of something better, project a ray from the
// end of the shorter tangent to midway between the end points
// through both curves and use the resulting angle to sort
// FIXME: some of this setup can be moved to set() if it works, or cached if it's expensive
double len = fTangent1.normalSquared();
double rlen = rh.fTangent1.normalSquared();
_Line ray;
Intersections i, ri;
int roots, rroots;
bool flip = false;
do {
bool useThis = (len < rlen) ^ flip;
const Cubic& part = useThis ? fCurvePart : rh.fCurvePart;
SkPath::Verb partVerb = useThis ? fVerb : rh.fVerb;
ray[0] = partVerb == SkPath::kCubic_Verb && part[0].approximatelyEqual(part[1]) ?
part[2] : part[1];
ray[1].x = (part[0].x + part[partVerb].x) / 2;
ray[1].y = (part[0].y + part[partVerb].y) / 2;
SkASSERT(ray[0] != ray[1]);
roots = (*SegmentRayIntersect[fVerb])(fPts, ray, i);
rroots = (*SegmentRayIntersect[rh.fVerb])(rh.fPts, ray, ri);
} while ((roots == 0 || rroots == 0) && (flip ^= true));
if (roots == 0 || rroots == 0) {
// FIXME: we don't have a solution in this case. The interim solution
// is to mark the edges as unsortable, exclude them from this and
// future computations, and allow the returned path to be fragmented
fUnsortable = true;
rh.fUnsortable = true;
return this < &rh; // even with no solution, return a stable sort
}
_Point loc;
double best = SK_ScalarInfinity;
double dx, dy, dist;
int index;
for (index = 0; index < roots; ++index) {
(*SegmentXYAtT2[fVerb])(fPts, i.fT[0][index], &loc);
dx = loc.x - ray[0].x;
dy = loc.y - ray[0].y;
dist = dx * dx + dy * dy;
if (best > dist) {
best = dist;
}
}
for (index = 0; index < rroots; ++index) {
(*SegmentXYAtT2[rh.fVerb])(rh.fPts, ri.fT[0][index], &loc);
dx = loc.x - ray[0].x;
dy = loc.y - ray[0].y;
dist = dx * dx + dy * dy;
if (best > dist) {
return fSide < 0;
}
}
return fSide > 0;
}
double dx() const {
return fTangent1.dx();
}
double dy() const {
return fTangent1.dy();
}
int end() const {
return fEnd;
}
bool isHorizontal() const {
return dy() == 0 && fVerb == SkPath::kLine_Verb;
}
bool lengthen() {
int newEnd = fEnd;
if (fStart < fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
fEnd = newEnd;
setSpans();
return true;
}
return false;
}
bool reverseLengthen() {
if (fReversed) {
return false;
}
int newEnd = fStart;
if (fStart > fEnd ? ++newEnd < fSpans->count() : --newEnd >= 0) {
fEnd = newEnd;
fReversed = true;
setSpans();
return true;
}
return false;
}
void set(const SkPoint* orig, SkPath::Verb verb, const Segment* segment,
int start, int end, const SkTDArray<Span>& spans) {
fSegment = segment;
fStart = start;
fEnd = end;
fPts = orig;
fVerb = verb;
fSpans = &spans;
fReversed = false;
fUnsortable = false;
setSpans();
}
void setSpans() {
double startT = (*fSpans)[fStart].fT;
double endT = (*fSpans)[fEnd].fT;
switch (fVerb) {
case SkPath::kLine_Verb:
_Line l;
LineSubDivideHD(fPts, startT, endT, l);
// OPTIMIZATION: for pure line compares, we never need fTangent1.c
fTangent1.lineEndPoints(l);
fSide = 0;
break;
case SkPath::kQuad_Verb: {
Quadratic& quad = (Quadratic&)fCurvePart;
QuadSubDivideHD(fPts, startT, endT, quad);
fTangent1.quadEndPoints(quad, 0, 1);
if (dx() == 0 && dy() == 0) {
fTangent1.quadEndPoints(quad);
}
fSide = -fTangent1.pointDistance(fCurvePart[2]); // not normalized -- compare sign only
} break;
case SkPath::kCubic_Verb: {
int nextC = 2;
CubicSubDivideHD(fPts, startT, endT, fCurvePart);
fTangent1.cubicEndPoints(fCurvePart, 0, 1);
if (dx() == 0 && dy() == 0) {
fTangent1.cubicEndPoints(fCurvePart, 0, 2);
nextC = 3;
if (dx() == 0 && dy() == 0) {
fTangent1.cubicEndPoints(fCurvePart, 0, 3);
}
}
fSide = -fTangent1.pointDistance(fCurvePart[nextC]); // compare sign only
if (nextC == 2 && approximately_zero(fSide)) {
fSide = -fTangent1.pointDistance(fCurvePart[3]);
}
} break;
default:
SkASSERT(0);
}
fUnsortable = dx() == 0 && dy() == 0;
if (fUnsortable) {
return;
}
SkASSERT(fStart != fEnd);
int step = fStart < fEnd ? 1 : -1; // OPTIMIZE: worth fStart - fEnd >> 31 type macro?
for (int index = fStart; index != fEnd; index += step) {
#if 1
const Span& thisSpan = (*fSpans)[index];
const Span& nextSpan = (*fSpans)[index + step];
if (thisSpan.fTiny || precisely_equal(thisSpan.fT, nextSpan.fT)) {
continue;
}
fUnsortable = step > 0 ? thisSpan.fUnsortableStart : nextSpan.fUnsortableEnd;
#if DEBUG_UNSORTABLE
if (fUnsortable) {
SkPoint iPt, ePt;
(*SegmentXYAtT[fVerb])(fPts, thisSpan.fT, &iPt);
(*SegmentXYAtT[fVerb])(fPts, nextSpan.fT, &ePt);
SkDebugf("%s unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
index, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
}
#endif
return;
#else
if ((*fSpans)[index].fUnsortableStart) {
fUnsortable = true;
return;
}
#endif
}
#if 1
#if DEBUG_UNSORTABLE
SkPoint iPt, ePt;
(*SegmentXYAtT[fVerb])(fPts, startT, &iPt);
(*SegmentXYAtT[fVerb])(fPts, endT, &ePt);
SkDebugf("%s all tiny unsortable [%d] (%1.9g,%1.9g) [%d] (%1.9g,%1.9g)\n", __FUNCTION__,
fStart, iPt.fX, iPt.fY, fEnd, ePt.fX, ePt.fY);
#endif
fUnsortable = true;
#endif
}
Segment* segment() const {
return const_cast<Segment*>(fSegment);
}
int sign() const {
return SkSign32(fStart - fEnd);
}
const SkTDArray<Span>* spans() const {
return fSpans;
}
int start() const {
return fStart;
}
bool unsortable() const {
return fUnsortable;
}
#if DEBUG_ANGLE
const SkPoint* pts() const {
return fPts;
}
SkPath::Verb verb() const {
return fVerb;
}
void debugShow(const SkPoint& a) const {
SkDebugf(" d=(%1.9g,%1.9g) side=%1.9g\n", dx(), dy(), fSide);
}
#endif
private:
const SkPoint* fPts;
Cubic fCurvePart;
SkPath::Verb fVerb;
double fSide;
LineParameters fTangent1;
const SkTDArray<Span>* fSpans;
const Segment* fSegment;
int fStart;
int fEnd;
bool fReversed;
mutable bool fUnsortable; // this alone is editable by the less than operator
};
// Bounds, unlike Rect, does not consider a line to be empty.
struct Bounds : public SkRect {
static bool Intersects(const Bounds& a, const Bounds& b) {
return a.fLeft <= b.fRight && b.fLeft <= a.fRight &&
a.fTop <= b.fBottom && b.fTop <= a.fBottom;
}
void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) {
if (left < fLeft) {
fLeft = left;
}
if (top < fTop) {
fTop = top;
}
if (right > fRight) {
fRight = right;
}
if (bottom > fBottom) {
fBottom = bottom;
}
}
void add(const Bounds& toAdd) {
add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom);
}
void add(const SkPoint& pt) {
if (pt.fX < fLeft) fLeft = pt.fX;
if (pt.fY < fTop) fTop = pt.fY;
if (pt.fX > fRight) fRight = pt.fX;
if (pt.fY > fBottom) fBottom = pt.fY;
}
bool isEmpty() {
return fLeft > fRight || fTop > fBottom
|| (fLeft == fRight && fTop == fBottom)
|| sk_double_isnan(fLeft) || sk_double_isnan(fRight)
|| sk_double_isnan(fTop) || sk_double_isnan(fBottom);
}
void setCubicBounds(const SkPoint a[4]) {
_Rect dRect;
MAKE_CONST_CUBIC(cubic, a);
dRect.setBounds(cubic);
set((float) dRect.left, (float) dRect.top, (float) dRect.right,
(float) dRect.bottom);
}
void setLineBounds(const SkPoint a[2]) {
setPoint(a[0]);
add(a[1]);
}
void setQuadBounds(const SkPoint a[3]) {
MAKE_CONST_QUAD(quad, a);
_Rect dRect;
dRect.setBounds(quad);
set((float) dRect.left, (float) dRect.top, (float) dRect.right,
(float) dRect.bottom);
}
void setPoint(const SkPoint& pt) {
fLeft = fRight = pt.fX;
fTop = fBottom = pt.fY;
}
};
static void (Bounds::*setSegmentBounds[])(const SkPoint[]) = {
NULL,
&Bounds::setLineBounds,
&Bounds::setQuadBounds,
&Bounds::setCubicBounds
};
// OPTIMIZATION: does the following also work, and is it any faster?
// return outerWinding * innerWinding > 0
// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
static bool useInnerWinding(int outerWinding, int innerWinding) {
SkASSERT(outerWinding != SK_MaxS32);
SkASSERT(innerWinding != SK_MaxS32);
int absOut = abs(outerWinding);
int absIn = abs(innerWinding);
bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
#if 0 && DEBUG_WINDING
if (outerWinding * innerWinding < 0) {
SkDebugf("%s outer=%d inner=%d result=%s\n", __FUNCTION__,
outerWinding, innerWinding, result ? "true" : "false");
}
#endif
return result;
}
#define F (false) // discard the edge
#define T (true) // keep the edge
static const bool gUnaryActiveEdge[2][2] = {
// from=0 from=1
// to=0,1 to=0,1
{F, T}, {T, F},
};
static const bool gActiveEdge[kShapeOp_Count][2][2][2][2] = {
// miFrom=0 miFrom=1
// miTo=0 miTo=1 miTo=0 miTo=1
// suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1
// suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1
{{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su
{{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su
{{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su
{{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su
};
#undef F
#undef T
// wrap path to keep track of whether the contour is initialized and non-empty
class PathWrapper {
public:
PathWrapper(SkPath& path)
: fPathPtr(&path)
, fCloses(0)
, fMoves(0)
{
init();
}
void close() {
if (!fHasMove) {
return;
}
bool callClose = isClosed();
lineTo();
if (fEmpty) {
return;
}
if (callClose) {
#if DEBUG_PATH_CONSTRUCTION
SkDebugf("path.close();\n");
#endif
fPathPtr->close();
fCloses++;
}
init();
}
void cubicTo(const SkPoint& pt1, const SkPoint& pt2, const SkPoint& pt3) {
lineTo();
moveTo();
fDefer[1] = pt3;
nudge();
fDefer[0] = fDefer[1];
#if DEBUG_PATH_CONSTRUCTION
SkDebugf("path.cubicTo(%1.9g,%1.9g, %1.9g,%1.9g, %1.9g,%1.9g);\n",
pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY);
#endif
fPathPtr->cubicTo(pt1.fX, pt1.fY, pt2.fX, pt2.fY, fDefer[1].fX, fDefer[1].fY);
fEmpty = false;
}
void deferredLine(const SkPoint& pt) {
if (pt == fDefer[1]) {
return;
}
if (changedSlopes(pt)) {
lineTo();
fDefer[0] = fDefer[1];
}
fDefer[1] = pt;
}
void deferredMove(const SkPoint& pt) {
fMoved = true;
fHasMove = true;
fEmpty = true;
fDefer[0] = fDefer[1] = pt;
}
void deferredMoveLine(const SkPoint& pt) {
if (!fHasMove) {
deferredMove(pt);
}
deferredLine(pt);
}
bool hasMove() const {
return fHasMove;
}
void init() {
fEmpty = true;
fHasMove = false;
fMoved = false;
}
bool isClosed() const {
return !fEmpty && fFirstPt == fDefer[1];
}
void lineTo() {
if (fDefer[0] == fDefer[1]) {
return;
}
moveTo();
nudge();
fEmpty = false;
#if DEBUG_PATH_CONSTRUCTION
SkDebugf("path.lineTo(%1.9g,%1.9g);\n", fDefer[1].fX, fDefer[1].fY);
#endif
fPathPtr->lineTo(fDefer[1].fX, fDefer[1].fY);
fDefer[0] = fDefer[1];
}
const SkPath* nativePath() const {
return fPathPtr;
}
void nudge() {
if (fEmpty || !AlmostEqualUlps(fDefer[1].fX, fFirstPt.fX)
|| !AlmostEqualUlps(fDefer[1].fY, fFirstPt.fY)) {
return;
}
fDefer[1] = fFirstPt;
}
void quadTo(const SkPoint& pt1, const SkPoint& pt2) {
lineTo();
moveTo();
fDefer[1] = pt2;
nudge();
fDefer[0] = fDefer[1];
#if DEBUG_PATH_CONSTRUCTION
SkDebugf("path.quadTo(%1.9g,%1.9g, %1.9g,%1.9g);\n",
pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY);
#endif
fPathPtr->quadTo(pt1.fX, pt1.fY, fDefer[1].fX, fDefer[1].fY);
fEmpty = false;
}
bool someAssemblyRequired() const {
return fCloses < fMoves;
}
protected:
bool changedSlopes(const SkPoint& pt) const {
if (fDefer[0] == fDefer[1]) {
return false;
}
SkScalar deferDx = fDefer[1].fX - fDefer[0].fX;
SkScalar deferDy = fDefer[1].fY - fDefer[0].fY;
SkScalar lineDx = pt.fX - fDefer[1].fX;
SkScalar lineDy = pt.fY - fDefer[1].fY;
return deferDx * lineDy != deferDy * lineDx;
}
void moveTo() {
if (!fMoved) {
return;
}
fFirstPt = fDefer[0];
#if DEBUG_PATH_CONSTRUCTION
SkDebugf("path.moveTo(%1.9g,%1.9g);\n", fDefer[0].fX, fDefer[0].fY);
#endif
fPathPtr->moveTo(fDefer[0].fX, fDefer[0].fY);
fMoved = false;
fMoves++;
}
private:
SkPath* fPathPtr;
SkPoint fDefer[2];
SkPoint fFirstPt;
int fCloses;
int fMoves;
bool fEmpty;
bool fHasMove;
bool fMoved;
};
class Segment {
public:
Segment() {
#if DEBUG_DUMP
fID = ++gSegmentID;
#endif
}
bool operator<(const Segment& rh) const {
return fBounds.fTop < rh.fBounds.fTop;
}
bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) {
if (activeAngleInner(index, done, angles)) {
return true;
}
int lesser = index;
while (--lesser >= 0 && equalPoints(index, lesser)) {
if (activeAngleOther(lesser, done, angles)) {
return true;
}
}
lesser = index;
do {
if (activeAngleOther(index, done, angles)) {
return true;
}
} while (++index < fTs.count() && equalPoints(index, lesser));
return false;
}
bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) {
Span* span = &fTs[index];
Segment* other = span->fOther;
int oIndex = span->fOtherIndex;
return other->activeAngleInner(oIndex, done, angles);
}
bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) {
int next = nextExactSpan(index, 1);
if (next > 0) {
Span& upSpan = fTs[index];
if (upSpan.fWindValue || upSpan.fOppValue) {
addAngle(angles, index, next);
if (upSpan.fDone || upSpan.fUnsortableEnd) {
done++;
} else if (upSpan.fWindSum != SK_MinS32) {
return true;
}
} else if (!upSpan.fDone) {
upSpan.fDone = true;
fDoneSpans++;
}
}
int prev = nextExactSpan(index, -1);
// edge leading into junction
if (prev >= 0) {
Span& downSpan = fTs[prev];
if (downSpan.fWindValue || downSpan.fOppValue) {
addAngle(angles, index, prev);
if (downSpan.fDone) {
done++;
} else if (downSpan.fWindSum != SK_MinS32) {
return true;
}
} else if (!downSpan.fDone) {
downSpan.fDone = true;
fDoneSpans++;
}
}
return false;
}
SkPoint activeLeftTop(bool onlySortable, int* firstT) const {
SkASSERT(!done());
SkPoint topPt = {SK_ScalarMax, SK_ScalarMax};
int count = fTs.count();
// see if either end is not done since we want smaller Y of the pair
bool lastDone = true;
bool lastUnsortable = false;
double lastT = -1;
for (int index = 0; index < count; ++index) {
const Span& span = fTs[index];
if (onlySortable && (span.fUnsortableStart || lastUnsortable)) {
goto next;
}
if (span.fDone && lastDone) {
goto next;
}
if (approximately_negative(span.fT - lastT)) {
goto next;
}
{
const SkPoint& xy = xyAtT(&span);
if (topPt.fY > xy.fY || (topPt.fY == xy.fY && topPt.fX > xy.fX)) {
topPt = xy;
if (firstT) {
*firstT = index;
}
}
if (fVerb != SkPath::kLine_Verb && !lastDone) {
SkPoint curveTop = (*SegmentTop[fVerb])(fPts, lastT, span.fT);
if (topPt.fY > curveTop.fY || (topPt.fY == curveTop.fY
&& topPt.fX > curveTop.fX)) {
topPt = curveTop;
if (firstT) {
*firstT = index;
}
}
}
lastT = span.fT;
}
next:
lastDone = span.fDone;
lastUnsortable = span.fUnsortableEnd;
}
return topPt;
}
bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, ShapeOp op) {
int sumMiWinding = updateWinding(endIndex, index);
int sumSuWinding = updateOppWinding(endIndex, index);
if (fOperand) {
SkTSwap<int>(sumMiWinding, sumSuWinding);
}
int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
return activeOp(xorMiMask, xorSuMask, index, endIndex, op, sumMiWinding, sumSuWinding,
maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
}
bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, ShapeOp op,
int& sumMiWinding, int& sumSuWinding,
int& maxWinding, int& sumWinding, int& oppMaxWinding, int& oppSumWinding) {
setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
bool miFrom;
bool miTo;
bool suFrom;
bool suTo;
if (operand()) {
miFrom = (oppMaxWinding & xorMiMask) != 0;
miTo = (oppSumWinding & xorMiMask) != 0;
suFrom = (maxWinding & xorSuMask) != 0;
suTo = (sumWinding & xorSuMask) != 0;
} else {
miFrom = (maxWinding & xorMiMask) != 0;
miTo = (sumWinding & xorMiMask) != 0;
suFrom = (oppMaxWinding & xorSuMask) != 0;
suTo = (oppSumWinding & xorSuMask) != 0;
}
bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
#if DEBUG_ACTIVE_OP
SkDebugf("%s op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", __FUNCTION__,
kShapeOpStr[op], miFrom, miTo, suFrom, suTo, result);
#endif
SkASSERT(result != -1);
return result;
}
bool activeWinding(int index, int endIndex) {
int sumWinding = updateWinding(endIndex, index);
int maxWinding;
return activeWinding(index, endIndex, maxWinding, sumWinding);
}
bool activeWinding(int index, int endIndex, int& maxWinding, int& sumWinding) {
setUpWinding(index, endIndex, maxWinding, sumWinding);
bool from = maxWinding != 0;
bool to = sumWinding != 0;
bool result = gUnaryActiveEdge[from][to];
SkASSERT(result != -1);
return result;
}
void addAngle(SkTDArray<Angle>& angles, int start, int end) const {
SkASSERT(start != end);
Angle* angle = angles.append();
#if DEBUG_ANGLE
if (angles.count() > 1 && !fTs[start].fTiny) {
SkPoint angle0Pt, newPt;
(*SegmentXYAtT[angles[0].verb()])(angles[0].pts(),
(*angles[0].spans())[angles[0].start()].fT, &angle0Pt);
(*SegmentXYAtT[fVerb])(fPts, fTs[start].fT, &newPt);
SkASSERT(AlmostEqualUlps(angle0Pt.fX, newPt.fX));
SkASSERT(AlmostEqualUlps(angle0Pt.fY, newPt.fY));
}
#endif
angle->set(fPts, fVerb, this, start, end, fTs);
}
void addCancelOutsides(double tStart, double oStart, Segment& other,
double oEnd) {
int tIndex = -1;
int tCount = fTs.count();
int oIndex = -1;
int oCount = other.fTs.count();
do {
++tIndex;
} while (!approximately_negative(tStart - fTs[tIndex].fT) && tIndex < tCount);
int tIndexStart = tIndex;
do {
++oIndex;
} while (!approximately_negative(oStart - other.fTs[oIndex].fT) && oIndex < oCount);
int oIndexStart = oIndex;
double nextT;
do {
nextT = fTs[++tIndex].fT;
} while (nextT < 1 && approximately_negative(nextT - tStart));
double oNextT;
do {
oNextT = other.fTs[++oIndex].fT;
} while (oNextT < 1 && approximately_negative(oNextT - oStart));
// at this point, spans before and after are at:
// fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex]
// if tIndexStart == 0, no prior span
// if nextT == 1, no following span
// advance the span with zero winding
// if the following span exists (not past the end, non-zero winding)
// connect the two edges
if (!fTs[tIndexStart].fWindValue) {
if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) {
#if DEBUG_CONCIDENT
SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
__FUNCTION__, fID, other.fID, tIndexStart - 1,
fTs[tIndexStart].fT, xyAtT(tIndexStart).fX,
xyAtT(tIndexStart).fY);
#endif
addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT, false,
fTs[tIndexStart].fPt);
}
if (nextT < 1 && fTs[tIndex].fWindValue) {
#if DEBUG_CONCIDENT
SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
__FUNCTION__, fID, other.fID, tIndex,
fTs[tIndex].fT, xyAtT(tIndex).fX,
xyAtT(tIndex).fY);
#endif
addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT, false, fTs[tIndex].fPt);
}
} else {
SkASSERT(!other.fTs[oIndexStart].fWindValue);
if (oIndexStart > 0 && other.fTs[oIndexStart - 1].fWindValue) {
#if DEBUG_CONCIDENT
SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
__FUNCTION__, fID, other.fID, oIndexStart - 1,
other.fTs[oIndexStart].fT, other.xyAtT(oIndexStart).fX,
other.xyAtT(oIndexStart).fY);
other.debugAddTPair(other.fTs[oIndexStart].fT, *this, fTs[tIndex].fT);
#endif
}
if (oNextT < 1 && other.fTs[oIndex].fWindValue) {
#if DEBUG_CONCIDENT
SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n",
__FUNCTION__, fID, other.fID, oIndex,
other.fTs[oIndex].fT, other.xyAtT(oIndex).fX,
other.xyAtT(oIndex).fY);
other.debugAddTPair(other.fTs[oIndex].fT, *this, fTs[tIndexStart].fT);
#endif
}
}
}
void addCoinOutsides(const SkTDArray<double>& outsideTs, Segment& other,
double oEnd) {
// walk this to outsideTs[0]
// walk other to outsideTs[1]
// if either is > 0, add a pointer to the other, copying adjacent winding
int tIndex = -1;
int oIndex = -1;
double tStart = outsideTs[0];
double oStart = outsideTs[1];
do {
++tIndex;
} while (!approximately_negative(tStart - fTs[tIndex].fT));
SkPoint ptStart = fTs[tIndex].fPt;
do {
++oIndex;
} while (!approximately_negative(oStart - other.fTs[oIndex].fT));
if (tIndex > 0 || oIndex > 0 || fOperand != other.fOperand) {
addTPair(tStart, other, oStart, false, ptStart);
}
tStart = fTs[tIndex].fT;
oStart = other.fTs[oIndex].fT;
do {
double nextT;
do {
nextT = fTs[++tIndex].fT;
} while (approximately_negative(nextT - tStart));
tStart = nextT;
ptStart = fTs[tIndex].fPt;
do {
nextT = other.fTs[++oIndex].fT;
} while (approximately_negative(nextT - oStart));
oStart = nextT;
if (tStart == 1 && oStart == 1 && fOperand == other.fOperand) {
break;
}
addTPair(tStart, other, oStart, false, ptStart);
} while (tStart < 1 && oStart < 1 && !approximately_negative(oEnd - oStart));
}
void addCubic(const SkPoint pts[4], bool operand, bool evenOdd) {
init(pts, SkPath::kCubic_Verb, operand, evenOdd);
fBounds.setCubicBounds(pts);
}
/* SkPoint */ void addCurveTo(int start, int end, PathWrapper& path, bool active) const {
SkPoint edge[4];
const SkPoint* ePtr;
int lastT = fTs.count() - 1;
if (lastT < 0 || (start == 0 && end == lastT) || (start == lastT && end == 0)) {
ePtr = fPts;
} else {
// OPTIMIZE? if not active, skip remainder and return xy_at_t(end)
subDivide(start, end, edge);
ePtr = edge;
}
if (active) {
bool reverse = ePtr == fPts && start != 0;
if (reverse) {
path.deferredMoveLine(ePtr[fVerb]);
switch (fVerb) {
case SkPath::kLine_Verb:
path.deferredLine(ePtr[0]);
break;
case SkPath::kQuad_Verb:
path.quadTo(ePtr[1], ePtr[0]);
break;
case SkPath::kCubic_Verb:
path.cubicTo(ePtr[2], ePtr[1], ePtr[0]);
break;
default:
SkASSERT(0);
}
// return ePtr[0];
} else {
path.deferredMoveLine(ePtr[0]);
switch (fVerb) {
case SkPath::kLine_Verb:
path.deferredLine(ePtr[1]);
break;
case SkPath::kQuad_Verb:
path.quadTo(ePtr[1], ePtr[2]);
break;
case SkPath::kCubic_Verb:
path.cubicTo(ePtr[1], ePtr[2], ePtr[3]);
break;
default:
SkASSERT(0);
}
}
}
// return ePtr[fVerb];
}
void addLine(const SkPoint pts[2], bool operand, bool evenOdd) {
init(pts, SkPath::kLine_Verb, operand, evenOdd);
fBounds.set(pts, 2);
}
#if 0
const SkPoint& addMoveTo(int tIndex, PathWrapper& path, bool active) const {
const SkPoint& pt = xyAtT(tIndex);
if (active) {
path.deferredMove(pt);
}
return pt;
}
#endif
// add 2 to edge or out of range values to get T extremes
void addOtherT(int index, double otherT, int otherIndex) {
Span& span = fTs[index];
#if PIN_ADD_T
if (precisely_less_than_zero(otherT)) {
otherT = 0;
} else if (precisely_greater_than_one(otherT)) {
otherT = 1;
}
#endif
span.fOtherT = otherT;
span.fOtherIndex = otherIndex;
}
void addQuad(const SkPoint pts[3], bool operand, bool evenOdd) {
init(pts, SkPath::kQuad_Verb, operand, evenOdd);
fBounds.setQuadBounds(pts);
}
// Defer all coincident edge processing until
// after normal intersections have been computed
// no need to be tricky; insert in normal T order
// resolve overlapping ts when considering coincidence later
// add non-coincident intersection. Resulting edges are sorted in T.
int addT(Segment* other, const SkPoint& pt, double& newT) {
// FIXME: in the pathological case where there is a ton of intercepts,
// binary search?
int insertedAt = -1;
size_t tCount = fTs.count();
#if PIN_ADD_T
// FIXME: only do this pinning here (e.g. this is done also in quad/line intersect)
if (precisely_less_than_zero(newT)) {
newT = 0;
} else if (precisely_greater_than_one(newT)) {
newT = 1;
}
#endif
for (size_t index = 0; index < tCount; ++index) {
// OPTIMIZATION: if there are three or more identical Ts, then
// the fourth and following could be further insertion-sorted so
// that all the edges are clockwise or counterclockwise.
// This could later limit segment tests to the two adjacent
// neighbors, although it doesn't help with determining which
// circular direction to go in.
if (newT < fTs[index].fT) {
insertedAt = index;
break;
}
}
Span* span;
if (insertedAt >= 0) {
span = fTs.insert(insertedAt);
} else {
insertedAt = tCount;
span = fTs.append();
}
span->fT = newT;
span->fOther = other;
span->fPt = pt;
span->fWindSum = SK_MinS32;
span->fOppSum = SK_MinS32;
span->fWindValue = 1;
span->fOppValue = 0;
span->fTiny = false;
span->fLoop = false;
if ((span->fDone = newT == 1)) {
++fDoneSpans;
}
span->fUnsortableStart = false;
span->fUnsortableEnd = false;
int less = -1;
while (&span[less + 1] - fTs.begin() > 0 && xyAtT(&span[less]) == xyAtT(span)) {
#if 1
if (span[less].fDone) {
break;
}
double tInterval = newT - span[less].fT;
if (precisely_negative(tInterval)) {
break;
}
if (fVerb == SkPath::kCubic_Verb) {
double tMid = newT - tInterval / 2;
_Point midPt;
CubicXYAtT(fPts, tMid, &midPt);
if (!midPt.approximatelyEqual(xyAtT(span))) {
break;
}
}
span[less].fTiny = true;
span[less].fDone = true;
if (approximately_negative(newT - span[less].fT)) {
if (approximately_greater_than_one(newT)) {
span[less].fUnsortableStart = true;
span[less - 1].fUnsortableEnd = true;
}
if (approximately_less_than_zero(span[less].fT)) {
span[less + 1].fUnsortableStart = true;
span[less].fUnsortableEnd = true;
}
}
++fDoneSpans;
#else
double tInterval = newT - span[less].fT;
if (precisely_negative(tInterval)) {
break;
}
if (fVerb == SkPath::kCubic_Verb) {
double tMid = newT - tInterval / 2;
_Point midPt;
CubicXYAtT(fPts, tMid, &midPt);
if (!midPt.approximatelyEqual(xyAtT(span))) {
break;
}
}
SkASSERT(span[less].fDone == span->fDone);
if (span[less].fT == 0) {
span->fT = newT = 0;
} else {
setSpanT(less, newT);
}
#endif
--less;
}
int more = 1;
while (fTs.end() - &span[more - 1] > 1 && xyAtT(&span[more]) == xyAtT(span)) {
#if 1
if (span[more - 1].fDone) {
break;
}
double tEndInterval = span[more].fT - newT;
if (precisely_negative(tEndInterval)) {
break;
}
if (fVerb == SkPath::kCubic_Verb) {
double tMid = newT - tEndInterval / 2;
_Point midEndPt;
CubicXYAtT(fPts, tMid, &midEndPt);
if (!midEndPt.approximatelyEqual(xyAtT(span))) {
break;
}
}
span[more - 1].fTiny = true;
span[more - 1].fDone = true;
if (approximately_negative(span[more].fT - newT)) {
if (approximately_greater_than_one(span[more].fT)) {
span[more + 1].fUnsortableStart = true;
span[more].fUnsortableEnd = true;
}
if (approximately_less_than_zero(newT)) {
span[more].fUnsortableStart = true;
span[more - 1].fUnsortableEnd = true;
}
}
++fDoneSpans;
#else
double tEndInterval = span[more].fT - newT;
if (precisely_negative(tEndInterval)) {
break;
}
if (fVerb == SkPath::kCubic_Verb) {
double tMid = newT - tEndInterval / 2;
_Point midEndPt;
CubicXYAtT(fPts, tMid, &midEndPt);
if (!midEndPt.approximatelyEqual(xyAtT(span))) {
break;
}
}
SkASSERT(span[more - 1].fDone == span[more].fDone);
if (newT == 0) {
setSpanT(more, 0);
} else {
span->fT = newT = span[more].fT;
}
#endif
++more;
}
return insertedAt;
}
// set spans from start to end to decrement by one
// note this walks other backwards
// FIMXE: there's probably an edge case that can be constructed where
// two span in one segment are separated by float epsilon on one span but
// not the other, if one segment is very small. For this
// case the counts asserted below may or may not be enough to separate the
// spans. Even if the counts work out, what if the spans aren't correctly
// sorted? It feels better in such a case to match the span's other span
// pointer since both coincident segments must contain the same spans.
void addTCancel(double startT, double endT, Segment& other,
double oStartT, double oEndT) {
SkASSERT(!approximately_negative(endT - startT));
SkASSERT(!approximately_negative(oEndT - oStartT));
bool binary = fOperand != other.fOperand;
int index = 0;
while (!approximately_negative(startT - fTs[index].fT)) {
++index;
}
int oIndex = other.fTs.count();
while (approximately_positive(other.fTs[--oIndex].fT - oEndT))
;
double tRatio = (oEndT - oStartT) / (endT - startT);
Span* test = &fTs[index];
Span* oTest = &other.fTs[oIndex];
SkTDArray<double> outsideTs;
SkTDArray<double> oOutsideTs;
do {
bool decrement = test->fWindValue && oTest->fWindValue && !binary;
bool track = test->fWindValue || oTest->fWindValue;
double testT = test->fT;
double oTestT = oTest->fT;
Span* span = test;
do {
if (decrement) {
decrementSpan(span);
} else if (track && span->fT < 1 && oTestT < 1) {
TrackOutside(outsideTs, span->fT, oTestT);
}
span = &fTs[++index];
} while (approximately_negative(span->fT - testT));
Span* oSpan = oTest;
double otherTMatchStart = oEndT - (span->fT - startT) * tRatio;
double otherTMatchEnd = oEndT - (test->fT - startT) * tRatio;
SkDEBUGCODE(int originalWindValue = oSpan->fWindValue);
while (approximately_negative(otherTMatchStart - oSpan->fT)
&& !approximately_negative(otherTMatchEnd - oSpan->fT)) {
#ifdef SK_DEBUG
SkASSERT(originalWindValue == oSpan->fWindValue);
#endif
if (decrement) {
other.decrementSpan(oSpan);
} else if (track && oSpan->fT < 1 && testT < 1) {
TrackOutside(oOutsideTs, oSpan->fT, testT);
}
if (!oIndex) {
break;
}
oSpan = &other.fTs[--oIndex];
}
test = span;
oTest = oSpan;
} while (!approximately_negative(endT - test->fT));
SkASSERT(!oIndex || approximately_negative(oTest->fT - oStartT));
// FIXME: determine if canceled edges need outside ts added
if (!done() && outsideTs.count()) {
double tStart = outsideTs[0];
double oStart = outsideTs[1];
addCancelOutsides(tStart, oStart, other, oEndT);
int count = outsideTs.count();
if (count > 2) {
double tStart = outsideTs[count - 2];
double oStart = outsideTs[count - 1];
addCancelOutsides(tStart, oStart, other, oEndT);
}
}
if (!other.done() && oOutsideTs.count()) {
double tStart = oOutsideTs[0];
double oStart = oOutsideTs[1];
other.addCancelOutsides(tStart, oStart, *this, endT);
}
}
int addSelfT(Segment* other, const SkPoint& pt, double& newT) {
int result = addT(other, pt, newT);
Span* span = &fTs[result];
span->fLoop = true;
return result;
}
int addUnsortableT(Segment* other, bool start, const SkPoint& pt, double& newT) {
int result = addT(other, pt, newT);
Span* span = &fTs[result];
if (start) {
if (result > 0) {
span[result - 1].fUnsortableEnd = true;
}
span[result].fUnsortableStart = true;
} else {
span[result].fUnsortableEnd = true;
if (result + 1 < fTs.count()) {
span[result + 1].fUnsortableStart = true;
}
}
return result;
}
int bumpCoincidentThis(const Span* oTest, bool opp, int index,
SkTDArray<double>& outsideTs) {
int oWindValue = oTest->fWindValue;
int oOppValue = oTest->fOppValue;
if (opp) {
SkTSwap<int>(oWindValue, oOppValue);
}
Span* const test = &fTs[index];
Span* end = test;
const double oStartT = oTest->fT;
do {
if (bumpSpan(end, oWindValue, oOppValue)) {
TrackOutside(outsideTs, end->fT, oStartT);
}
end = &fTs[++index];
} while (approximately_negative(end->fT - test->fT));
return index;
}
// because of the order in which coincidences are resolved, this and other
// may not have the same intermediate points. Compute the corresponding
// intermediate T values (using this as the master, other as the follower)
// and walk other conditionally -- hoping that it catches up in the end
int bumpCoincidentOther(const Span* test, double oEndT, int& oIndex,
SkTDArray<double>& oOutsideTs) {
Span* const oTest = &fTs[oIndex];
Span* oEnd = oTest;
const double startT = test->fT;
const double oStartT = oTest->fT;
while (!approximately_negative(oEndT - oEnd->fT)
&& approximately_negative(oEnd->fT - oStartT)) {
zeroSpan(oEnd);
TrackOutside(oOutsideTs, oEnd->fT, startT);
oEnd = &fTs[++oIndex];
}
return oIndex;
}
// FIXME: need to test this case:
// contourA has two segments that are coincident
// contourB has two segments that are coincident in the same place
// each ends up with +2/0 pairs for winding count
// since logic below doesn't transfer count (only increments/decrements) can this be
// resolved to +4/0 ?
// set spans from start to end to increment the greater by one and decrement
// the lesser
void addTCoincident(double startT, double endT, Segment& other, double oStartT, double oEndT) {
SkASSERT(!approximately_negative(endT - startT));
SkASSERT(!approximately_negative(oEndT - oStartT));
bool opp = fOperand ^ other.fOperand;
int index = 0;
while (!approximately_negative(startT - fTs[index].fT)) {
++index;
}
int oIndex = 0;
while (!approximately_negative(oStartT - other.fTs[oIndex].fT)) {
++oIndex;
}
Span* test = &fTs[index];
Span* oTest = &other.fTs[oIndex];
SkTDArray<double> outsideTs;
SkTDArray<double> oOutsideTs;
do {
// if either span has an opposite value and the operands don't match, resolve first
// SkASSERT(!test->fDone || !oTest->fDone);
if (test->fDone || oTest->fDone) {
index = advanceCoincidentThis(oTest, opp, index);
oIndex = other.advanceCoincidentOther(test, oEndT, oIndex);
} else {
index = bumpCoincidentThis(oTest, opp, index, outsideTs);
oIndex = other.bumpCoincidentOther(test, oEndT, oIndex, oOutsideTs);
}
test = &fTs[index];
oTest = &other.fTs[oIndex];
} while (!approximately_negative(endT - test->fT));
SkASSERT(approximately_negative(oTest->fT - oEndT));
SkASSERT(approximately_negative(oEndT - oTest->fT));
if (!done() && outsideTs.count()) {
addCoinOutsides(outsideTs, other, oEndT);
}
if (!other.done() && oOutsideTs.count()) {
other.addCoinOutsides(oOutsideTs, *this, endT);
}
}
// FIXME: this doesn't prevent the same span from being added twice
// fix in caller, SkASSERT here?
void addTPair(double t, Segment& other, double otherT, bool borrowWind, const SkPoint& pt) {
int tCount = fTs.count();
for (int tIndex = 0; tIndex < tCount; ++tIndex) {
const Span& span = fTs[tIndex];
if (!approximately_negative(span.fT - t)) {
break;
}
if (approximately_negative(span.fT - t) && span.fOther == &other
&& approximately_equal(span.fOtherT, otherT)) {
#if DEBUG_ADD_T_PAIR
SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n",
__FUNCTION__, fID, t, other.fID, otherT);
#endif
return;
}
}
#if DEBUG_ADD_T_PAIR
SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
__FUNCTION__, fID, t, other.fID, otherT);
#endif
int insertedAt = addT(&other, pt, t);
int otherInsertedAt = other.addT(this, pt, otherT);
addOtherT(insertedAt, otherT, otherInsertedAt);
other.addOtherT(otherInsertedAt, t, insertedAt);
matchWindingValue(insertedAt, t, borrowWind);
other.matchWindingValue(otherInsertedAt, otherT, borrowWind);
}
void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const {
// add edge leading into junction
int min = SkMin32(end, start);
if (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0) {
addAngle(angles, end, start);
}
// add edge leading away from junction
int step = SkSign32(end - start);
int tIndex = nextExactSpan(end, step);
min = SkMin32(end, tIndex);
if (tIndex >= 0 && (fTs[min].fWindValue > 0 || fTs[min].fOppValue > 0)) {
addAngle(angles, end, tIndex);
}
}
int advanceCoincidentThis(const Span* oTest, bool opp, int index) {
Span* const test = &fTs[index];
Span* end = test;
do {
end = &fTs[++index];
} while (approximately_negative(end->fT - test->fT));
return index;
}
int advanceCoincidentOther(const Span* test, double oEndT, int& oIndex) {
Span* const oTest = &fTs[oIndex];
Span* oEnd = oTest;
const double oStartT = oTest->fT;
while (!approximately_negative(oEndT - oEnd->fT)
&& approximately_negative(oEnd->fT - oStartT)) {
oEnd = &fTs[++oIndex];
}
return oIndex;
}
bool betweenTs(int lesser, double testT, int greater) {
if (lesser > greater) {
SkTSwap<int>(lesser, greater);
}
return approximately_between(fTs[lesser].fT, testT, fTs[greater].fT);
}
const Bounds& bounds() const {
return fBounds;
}
void buildAngles(int index, SkTDArray<Angle>& angles, bool includeOpp) const {
double referenceT = fTs[index].fT;
int lesser = index;
while (--lesser >= 0 && (includeOpp || fTs[lesser].fOther->fOperand == fOperand)
&& precisely_negative(referenceT - fTs[lesser].fT)) {
buildAnglesInner(lesser, angles);
}
do {
buildAnglesInner(index, angles);
} while (++index < fTs.count() && (includeOpp || fTs[index].fOther->fOperand == fOperand)
&& precisely_negative(fTs[index].fT - referenceT));
}
void buildAnglesInner(int index, SkTDArray<Angle>& angles) const {
const Span* span = &fTs[index];
Segment* other = span->fOther;
// if there is only one live crossing, and no coincidence, continue
// in the same direction
// if there is coincidence, the only choice may be to reverse direction
// find edge on either side of intersection
int oIndex = span->fOtherIndex;
// if done == -1, prior span has already been processed
int step = 1;
int next = other->nextExactSpan(oIndex, step);
if (next < 0) {
step = -step;
next = other->nextExactSpan(oIndex, step);
}
// add candidate into and away from junction
other->addTwoAngles(next, oIndex, angles);
}
int computeSum(int startIndex, int endIndex, bool binary) {
SkTDArray<Angle> angles;
addTwoAngles(startIndex, endIndex, angles);
buildAngles(endIndex, angles, false);
// OPTIMIZATION: check all angles to see if any have computed wind sum
// before sorting (early exit if none)
SkTDArray<Angle*> sorted;
bool sortable = SortAngles(angles, sorted);
#if DEBUG_SORT
sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0);
#endif
if (!sortable) {
return SK_MinS32;
}
int angleCount = angles.count();
const Angle* angle;
const Segment* base;
int winding;
int oWinding;
int firstIndex = 0;
do {
angle = sorted[firstIndex];
base = angle->segment();
winding = base->windSum(angle);
if (winding != SK_MinS32) {
oWinding = base->oppSum(angle);
break;
}
if (++firstIndex == angleCount) {
return SK_MinS32;
}
} while (true);
// turn winding into contourWinding
int spanWinding = base->spanSign(angle);
bool inner = useInnerWinding(winding + spanWinding, winding);
#if DEBUG_WINDING
SkDebugf("%s spanWinding=%d winding=%d sign=%d inner=%d result=%d\n", __FUNCTION__,
spanWinding, winding, angle->sign(), inner,
inner ? winding + spanWinding : winding);
#endif
if (inner) {
winding += spanWinding;
}
#if DEBUG_SORT
base->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, oWinding);
#endif
int nextIndex = firstIndex + 1;
int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
winding -= base->spanSign(angle);
oWinding -= base->oppSign(angle);
do {
if (nextIndex == angleCount) {
nextIndex = 0;
}
angle = sorted[nextIndex];
Segment* segment = angle->segment();
bool opp = base->fOperand ^ segment->fOperand;
int maxWinding, oMaxWinding;
int spanSign = segment->spanSign(angle);
int oppoSign = segment->oppSign(angle);
if (opp) {
oMaxWinding = oWinding;
oWinding -= spanSign;
maxWinding = winding;
if (oppoSign) {
winding -= oppoSign;
}
} else {
maxWinding = winding;
winding -= spanSign;
oMaxWinding = oWinding;
if (oppoSign) {
oWinding -= oppoSign;
}
}
if (segment->windSum(angle) == SK_MinS32) {
if (opp) {
if (useInnerWinding(oMaxWinding, oWinding)) {
oMaxWinding = oWinding;
}
if (oppoSign && useInnerWinding(maxWinding, winding)) {
maxWinding = winding;
}
(void) segment->markAndChaseWinding(angle, oMaxWinding, maxWinding);
} else {
if (useInnerWinding(maxWinding, winding)) {
maxWinding = winding;
}
if (oppoSign && useInnerWinding(oMaxWinding, oWinding)) {
oMaxWinding = oWinding;
}
(void) segment->markAndChaseWinding(angle, maxWinding,
binary ? oMaxWinding : 0);
}
}
} while (++nextIndex != lastIndex);
int minIndex = SkMin32(startIndex, endIndex);
return windSum(minIndex);
}
int crossedSpanY(const SkPoint& basePt, SkScalar& bestY, double& hitT, bool& hitSomething,
double mid, bool opp, bool current) const {
SkScalar bottom = fBounds.fBottom;
int bestTIndex = -1;
if (bottom <= bestY) {
return bestTIndex;
}
SkScalar top = fBounds.fTop;
if (top >= basePt.fY) {
return bestTIndex;
}
if (fBounds.fLeft > basePt.fX) {
return bestTIndex;
}
if (fBounds.fRight < basePt.fX) {
return bestTIndex;
}
if (fBounds.fLeft == fBounds.fRight) {
// if vertical, and directly above test point, wait for another one
return AlmostEqualUlps(basePt.fX, fBounds.fLeft) ? SK_MinS32 : bestTIndex;
}
// intersect ray starting at basePt with edge
Intersections intersections;
// OPTIMIZE: use specialty function that intersects ray with curve,
// returning t values only for curve (we don't care about t on ray)
int pts = (*VSegmentIntersect[fVerb])(fPts, top, bottom, basePt.fX, false, intersections);
if (pts == 0 || (current && pts == 1)) {
return bestTIndex;
}
if (current) {
SkASSERT(pts > 1);
int closestIdx = 0;
double closest = fabs(intersections.fT[0][0] - mid);
for (int idx = 1; idx < pts; ++idx) {
double test = fabs(intersections.fT[0][idx] - mid);
if (closest > test) {
closestIdx = idx;
closest = test;
}
}
if (closestIdx < pts - 1) {
intersections.fT[0][closestIdx] = intersections.fT[0][pts - 1];
}
--pts;
}
double bestT = -1;
for (int index = 0; index < pts; ++index) {
double foundT = intersections.fT[0][index];
if (approximately_less_than_zero(foundT)
|| approximately_greater_than_one(foundT)) {
continue;
}
SkScalar testY = (*SegmentYAtT[fVerb])(fPts, foundT);
if (approximately_negative(testY - bestY)
|| approximately_negative(basePt.fY - testY)) {
continue;
}
if (pts > 1 && fVerb == SkPath::kLine_Verb) {
return SK_MinS32; // if the intersection is edge on, wait for another one
}
if (fVerb > SkPath::kLine_Verb) {
SkScalar dx = (*SegmentDXAtT[fVerb])(fPts, foundT);
if (approximately_zero(dx)) {
return SK_MinS32; // hit vertical, wait for another one
}
}
bestY = testY;
bestT = foundT;
}
if (bestT < 0) {
return bestTIndex;
}
SkASSERT(bestT >= 0);
SkASSERT(bestT <= 1);
int start;
int end = 0;
do {
start = end;
end = nextSpan(start, 1);
} while (fTs[end].fT < bestT);
// FIXME: see next candidate for a better pattern to find the next start/end pair
while (start + 1 < end && fTs[start].fDone) {
++start;
}
if (!isCanceled(start)) {
hitT = bestT;
bestTIndex = start;
hitSomething = true;
}
return bestTIndex;
}
void decrementSpan(Span* span) {
SkASSERT(span->fWindValue > 0);
if (--(span->fWindValue) == 0) {
if (!span->fOppValue && !span->fDone) {
span->fDone = true;
++fDoneSpans;
}
}
}
bool bumpSpan(Span* span, int windDelta, int oppDelta) {
SkASSERT(!span->fDone);
span->fWindValue += windDelta;
SkASSERT(span->fWindValue >= 0);
span->fOppValue += oppDelta;
SkASSERT(span->fOppValue >= 0);
if (fXor) {
span->fWindValue &= 1;
}
if (fOppXor) {
span->fOppValue &= 1;
}
if (!span->fWindValue && !span->fOppValue) {
span->fDone = true;
++fDoneSpans;
return true;
}
return false;
}
// OPTIMIZE
// when the edges are initially walked, they don't automatically get the prior and next
// edges assigned to positions t=0 and t=1. Doing that would remove the need for this check,
// and would additionally remove the need for similar checks in condition edges. It would
// also allow intersection code to assume end of segment intersections (maybe?)
bool complete() const {
int count = fTs.count();
return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1;
}
bool done() const {
SkASSERT(fDoneSpans <= fTs.count());
return fDoneSpans == fTs.count();
}
bool done(int min) const {
return fTs[min].fDone;
}
bool done(const Angle* angle) const {
return done(SkMin32(angle->start(), angle->end()));
}
SkVector dxdy(int index) const {
return (*SegmentDXDYAtT[fVerb])(fPts, fTs[index].fT);
}
SkScalar dy(int index) const {
return (*SegmentDYAtT[fVerb])(fPts, fTs[index].fT);
}
bool equalPoints(int greaterTIndex, int lesserTIndex) {
SkASSERT(greaterTIndex >= lesserTIndex);
double greaterT = fTs[greaterTIndex].fT;
double lesserT = fTs[lesserTIndex].fT;
if (greaterT == lesserT) {
return true;
}
if (!approximately_negative(greaterT - lesserT)) {
return false;
}
return xyAtT(greaterTIndex) == xyAtT(lesserTIndex);
}
/*
The M and S variable name parts stand for the operators.
Mi stands for Minuend (see wiki subtraction, analogous to difference)
Su stands for Subtrahend
The Opp variable name part designates that the value is for the Opposite operator.
Opposite values result from combining coincident spans.
*/
Segment* findNextOp(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd,
bool& unsortable, ShapeOp op, const int xorMiMask, const int xorSuMask) {
const int startIndex = nextStart;
const int endIndex = nextEnd;
SkASSERT(startIndex != endIndex);
const int count = fTs.count();
SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
const int step = SkSign32(endIndex - startIndex);
const int end = nextExactSpan(startIndex, step);
SkASSERT(end >= 0);
Span* endSpan = &fTs[end];
Segment* other;
if (isSimple(end)) {
// mark the smaller of startIndex, endIndex done, and all adjacent
// spans with the same T value (but not 'other' spans)
#if DEBUG_WINDING
SkDebugf("%s simple\n", __FUNCTION__);
#endif
int min = SkMin32(startIndex, endIndex);
if (fTs[min].fDone) {
return NULL;
}
markDoneBinary(min);
other = endSpan->fOther;
nextStart = endSpan->fOtherIndex;
double startT = other->fTs[nextStart].fT;
nextEnd = nextStart;
do {
nextEnd += step;
}
while (precisely_zero(startT - other->fTs[nextEnd].fT));
SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
return other;
}
// more than one viable candidate -- measure angles to find best
SkTDArray<Angle> angles;
SkASSERT(startIndex - endIndex != 0);
SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
addTwoAngles(startIndex, end, angles);
buildAngles(end, angles, true);
SkTDArray<Angle*> sorted;
bool sortable = SortAngles(angles, sorted);
int angleCount = angles.count();
int firstIndex = findStartingEdge(sorted, startIndex, end);
SkASSERT(firstIndex >= 0);
#if DEBUG_SORT
debugShowSort(__FUNCTION__, sorted, firstIndex);
#endif
if (!sortable) {
unsortable = true;
return NULL;
}
SkASSERT(sorted[firstIndex]->segment() == this);
#if DEBUG_WINDING
SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
sorted[firstIndex]->sign());
#endif
int sumMiWinding = updateWinding(endIndex, startIndex);
int sumSuWinding = updateOppWinding(endIndex, startIndex);
if (operand()) {
SkTSwap<int>(sumMiWinding, sumSuWinding);
}
int nextIndex = firstIndex + 1;
int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
const Angle* foundAngle = NULL;
bool foundDone = false;
// iterate through the angle, and compute everyone's winding
Segment* nextSegment;
int activeCount = 0;
do {
SkASSERT(nextIndex != firstIndex);
if (nextIndex == angleCount) {
nextIndex = 0;
}
const Angle* nextAngle = sorted[nextIndex];
nextSegment = nextAngle->segment();
int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
nextAngle->end(), op, sumMiWinding, sumSuWinding,
maxWinding, sumWinding, oppMaxWinding, oppSumWinding);
if (activeAngle) {
++activeCount;
if (!foundAngle || (foundDone && activeCount & 1)) {
if (nextSegment->tiny(nextAngle)) {
unsortable = true;
return NULL;
}
foundAngle = nextAngle;
foundDone = nextSegment->done(nextAngle) && !nextSegment->tiny(nextAngle);
}
}
if (nextSegment->done()) {
continue;
}
if (nextSegment->windSum(nextAngle) != SK_MinS32) {
continue;
}
Span* last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding,
oppSumWinding, activeAngle, nextAngle);
if (last) {
*chase.append() = last;
#if DEBUG_WINDING
SkDebugf("%s chase.append id=%d\n", __FUNCTION__,
last->fOther->fTs[last->fOtherIndex].fOther->debugID());
#endif
}
} while (++nextIndex != lastIndex);
markDoneBinary(SkMin32(startIndex, endIndex));
if (!foundAngle) {
return NULL;
}
nextStart = foundAngle->start();
nextEnd = foundAngle->end();
nextSegment = foundAngle->segment();
#if DEBUG_WINDING
SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
__FUNCTION__, debugID(), nextSegment->debugID(), nextStart, nextEnd);
#endif
return nextSegment;
}
Segment* findNextWinding(SkTDArray<Span*>& chase, int& nextStart, int& nextEnd,
bool& unsortable) {
const int startIndex = nextStart;
const int endIndex = nextEnd;
SkASSERT(startIndex != endIndex);
const int count = fTs.count();
SkASSERT(startIndex < endIndex ? startIndex < count - 1 : startIndex > 0);
const int step = SkSign32(endIndex - startIndex);
const int end = nextExactSpan(startIndex, step);
SkASSERT(end >= 0);
Span* endSpan = &fTs[end];
Segment* other;
if (isSimple(end)) {
// mark the smaller of startIndex, endIndex done, and all adjacent
// spans with the same T value (but not 'other' spans)
#if DEBUG_WINDING
SkDebugf("%s simple\n", __FUNCTION__);
#endif
int min = SkMin32(startIndex, endIndex);
if (fTs[min].fDone) {
return NULL;
}
markDoneUnary(min);
other = endSpan->fOther;
nextStart = endSpan->fOtherIndex;
double startT = other->fTs[nextStart].fT;
nextEnd = nextStart;
do {
nextEnd += step;
}
while (precisely_zero(startT - other->fTs[nextEnd].fT));
SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count());
return other;
}
// more than one viable candidate -- measure angles to find best
SkTDArray<Angle> angles;
SkASSERT(startIndex - endIndex != 0);
SkASSERT((startIndex - endIndex < 0) ^ (step < 0));
addTwoAngles(startIndex, end, angles);
buildAngles(end, angles, true);
SkTDArray<Angle*> sorted;
bool sortable = SortAngles(angles, sorted);
int angleCount = angles.count();
int firstIndex = findStartingEdge(sorted, startIndex, end);
SkASSERT(firstIndex >= 0);
#if DEBUG_SORT
debugShowSort(__FUNCTION__, sorted, firstIndex);
#endif
if (!sortable) {
unsortable = true;
return NULL;
}
SkASSERT(sorted[firstIndex]->segment() == this);
#if DEBUG_WINDING
SkDebugf("%s firstIndex=[%d] sign=%d\n", __FUNCTION__, firstIndex,
sorted[firstIndex]->sign());
#endif
int sumWinding = updateWinding(endIndex, startIndex);
int nextIndex = firstIndex + 1;
int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
const Angle* foundAngle = NULL;
bool foundDone = false;
// iterate through the angle, and compute everyone's winding
Segment* nextSegment;
int activeCount = 0;
do {
SkASSERT(nextIndex != firstIndex);
if (nextIndex == angleCount) {
nextIndex = 0;
}