Simplify.cpp revision 027de226c144d9e6b7a76acb2e904952b5620a5e
10b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov/* 20b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov * Copyright 2012 Google Inc. 30b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov * 40b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov * Use of this source code is governed by a BSD-style license that can be 50b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov * found in the LICENSE file. 60b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov */ 70b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#include "Simplify.h" 80b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 90b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#undef SkASSERT 100b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define SkASSERT(cond) while (!(cond)) { sk_throw(); } 110b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 120b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov// Terminology: 130b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov// A Path contains one of more Contours 140b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov// A Contour is made up of Segment array 150b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov// A Segment is described by a Verb and a Point array with 2, 3, or 4 points 160b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov// A Verb is one of Line, Quad(ratic), or Cubic 170b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov// A Segment contains a Span array 180b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov// A Span is describes a portion of a Segment using starting and ending T 190b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov// T values range from 0 to 1, where 0 is the first Point in the Segment 200b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 210b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov// FIXME: remove once debugging is complete 220b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#if 0 // set to 1 for no debugging whatsoever 230b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 240b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov//const bool gxRunTestsInOneThread = false; 250b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 260b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_ADD_INTERSECTING_TS 0 270b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_BRIDGE 0 28cc4053e031371456fe54d51bbad1db721db4ae38Svetoslav Ganov#define DEBUG_CROSS 0 2958d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov#define DEBUG_DUMP 0 300b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_PATH_CONSTRUCTION 0 310b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_ACTIVE_SPANS 0 320b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_WINDING 0 330b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_UNUSED 0 // set to expose unused functions 340b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_MARK_DONE 0 350b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 360b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#else 370b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 380b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov//const bool gRunTestsInOneThread = true; 390b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 400b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_ADD_INTERSECTING_TS 0 410b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_BRIDGE 1 420b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_CROSS 1 430b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_DUMP 1 440b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_PATH_CONSTRUCTION 1 450b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_ACTIVE_SPANS 01 460b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_WINDING 01 470b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_UNUSED 0 // set to expose unused functions 480b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_MARK_DONE 01 490b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 500b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#endif 510b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 520b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#if DEBUG_ACTIVE_SPANS && !DEBUG_DUMP 530b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#undef DEBUG_DUMP 540b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_DUMP 1 550b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#endif 560b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 570b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#if DEBUG_DUMP 580b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic const char* kLVerbStr[] = {"", "line", "quad", "cubic"}; 590b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"}; 600b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic int gContourID; 610b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic int gSegmentID; 620b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#endif 630b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 640b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#ifndef DEBUG_TEST 650b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov#define DEBUG_TEST 0 66cc4053e031371456fe54d51bbad1db721db4ae38Svetoslav Ganov#endif 67cc4053e031371456fe54d51bbad1db721db4ae38Svetoslav Ganov 68cc4053e031371456fe54d51bbad1db721db4ae38Svetoslav Ganovstatic int LineIntersect(const SkPoint a[2], const SkPoint b[2], 69cc4053e031371456fe54d51bbad1db721db4ae38Svetoslav Ganov Intersections& intersections) { 700b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 710b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 720b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]); 7358d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov} 7458d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov 7500aabf7d187bc05408199bd687a538b2e68bdc17Svetoslav Ganovstatic int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2], 7658d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov Intersections& intersections) { 7758d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 780b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 790b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov intersect(aQuad, bLine, intersections); 800b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return intersections.fUsed; 8158d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov} 8258d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov 83cc4053e031371456fe54d51bbad1db721db4ae38Svetoslav Ganovstatic int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3], 84cc4053e031371456fe54d51bbad1db721db4ae38Svetoslav Ganov Intersections& intersections) { 850b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 860b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov {a[3].fX, a[3].fY}}; 870b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 880b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]); 890b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 900b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 910b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic int QuadIntersect(const SkPoint a[3], const SkPoint b[3], 920b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov Intersections& intersections) { 930b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 940b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}}; 950b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov intersect(aQuad, bQuad, intersections); 960b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return intersections.fUsed; 9758d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov} 9858d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov 9958d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganovstatic int CubicIntersect(const SkPoint a[4], const SkPoint b[4], 10058d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov Intersections& intersections) { 1010b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 1020b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov {a[3].fX, a[3].fY}}; 1030b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}, 10458d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov {b[3].fX, b[3].fY}}; 10558d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov intersect(aCubic, bCubic, intersections); 1060b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return intersections.fUsed; 1070b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 1080b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 1090b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, 1100b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov SkScalar y, bool flipped, Intersections& intersections) { 1110b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 1120b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return horizontalIntersect(aLine, left, right, y, flipped, intersections); 1130b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 1140b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 1150b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right, 11658d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov SkScalar y, bool flipped, Intersections& intersections) { 11758d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 11858d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov return horizontalIntersect(aQuad, left, right, y, flipped, intersections); 1190b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 1200b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 1210b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, 12258d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov SkScalar y, bool flipped, Intersections& intersections) { 12358d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 1240b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov {a[3].fX, a[3].fY}}; 1250b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return horizontalIntersect(aCubic, left, right, y, flipped, intersections); 1260b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 1270b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 1280b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom, 1290b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov SkScalar x, bool flipped, Intersections& intersections) { 13000aabf7d187bc05408199bd687a538b2e68bdc17Svetoslav Ganov const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 1310b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return verticalIntersect(aLine, top, bottom, x, flipped, intersections); 1320b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 1330b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 1340b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom, 1350b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov SkScalar x, bool flipped, Intersections& intersections) { 1360b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 1370b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return verticalIntersect(aQuad, top, bottom, x, flipped, intersections); 1380b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 1390b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 1400b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom, 1410b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov SkScalar x, bool flipped, Intersections& intersections) { 1420b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 1430b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov {a[3].fX, a[3].fY}}; 1440b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return verticalIntersect(aCubic, top, bottom, x, flipped, intersections); 1450b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 1460b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 1470b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic int (* const VSegmentIntersect[])(const SkPoint [], SkScalar , 1480b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov SkScalar , SkScalar , bool , Intersections& ) = { 1490b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov NULL, 1500b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov VLineIntersect, 1510b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov VQuadIntersect, 1520b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov VCubicIntersect 15358d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov}; 15458d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov 15558d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganovstatic void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { 15658d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 15758d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov double x, y; 15858d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov xy_at_t(line, t, x, y); 15958d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov out->fX = SkDoubleToScalar(x); 1600b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov out->fY = SkDoubleToScalar(y); 1610b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 1620b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 16358d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganovstatic void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) { 16458d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 1650b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov double x, y; 1660b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov xy_at_t(quad, t, x, y); 1670b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov out->fX = SkDoubleToScalar(x); 1680b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov out->fY = SkDoubleToScalar(y); 1690b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 1700b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 1710b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) { 1720b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 1730b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov {a[3].fX, a[3].fY}}; 1740b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov double x, y; 1750b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov xy_at_t(cubic, t, x, y); 1760b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov out->fX = SkDoubleToScalar(x); 1770b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov out->fY = SkDoubleToScalar(y); 1780b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 1790b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 1800b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = { 1810b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov NULL, 1820b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov LineXYAtT, 1830b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov QuadXYAtT, 1840b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov CubicXYAtT 1850b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov}; 1860b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 1870b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic SkScalar LineXAtT(const SkPoint a[2], double t) { 1880b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 1890b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov double x; 1900b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov xy_at_t(aLine, t, x, *(double*) 0); 19158d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov return SkDoubleToScalar(x); 19258d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov} 1930b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 1940b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic SkScalar QuadXAtT(const SkPoint a[3], double t) { 1950b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 19658d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov double x; 19758d37b55bd228032355360ea3303e46a804e0516Svetoslav Ganov xy_at_t(quad, t, x, *(double*) 0); 1980b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return SkDoubleToScalar(x); 1990b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 2000b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 2010b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic SkScalar CubicXAtT(const SkPoint a[4], double t) { 2020b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 2030b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov {a[3].fX, a[3].fY}}; 2040b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov double x; 2050b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov xy_at_t(cubic, t, x, *(double*) 0); 2060b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return SkDoubleToScalar(x); 2070b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 2080b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 2090b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = { 2100b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov NULL, 2110b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov LineXAtT, 2120b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov QuadXAtT, 2130b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov CubicXAtT 2140b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov}; 2150b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 2160b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic SkScalar LineYAtT(const SkPoint a[2], double t) { 2170b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 2180b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov double y; 2190b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov xy_at_t(aLine, t, *(double*) 0, y); 2200b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return SkDoubleToScalar(y); 2210b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 2220b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 2230b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic SkScalar QuadYAtT(const SkPoint a[3], double t) { 2240b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 2250b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov double y; 2260b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov xy_at_t(quad, t, *(double*) 0, y); 2270b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return SkDoubleToScalar(y); 2280b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 2290b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 2300b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic SkScalar CubicYAtT(const SkPoint a[4], double t) { 2310b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 2320b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov {a[3].fX, a[3].fY}}; 2330b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov double y; 2340b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov xy_at_t(cubic, t, *(double*) 0, y); 2350b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return SkDoubleToScalar(y); 2360b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 2370b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 2380b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = { 2390b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov NULL, 2400b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov LineYAtT, 2410b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov QuadYAtT, 2420b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov CubicYAtT 2430b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov}; 2440b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 2450b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic SkScalar LineDXAtT(const SkPoint a[2], double ) { 2460b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return a[1].fX - a[0].fX; 2470b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 2480b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 2490b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic SkScalar QuadDXAtT(const SkPoint a[3], double t) { 2500b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 2510b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov double x; 2520b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov dxdy_at_t(quad, t, x, *(double*) 0); 2530b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return SkDoubleToScalar(x); 2540b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 2550b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 2560b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic SkScalar CubicDXAtT(const SkPoint a[4], double t) { 2570b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 2580b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov {a[3].fX, a[3].fY}}; 2590b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov double x; 2600b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov dxdy_at_t(cubic, t, x, *(double*) 0); 2610b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov return SkDoubleToScalar(x); 2620b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov} 2630b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 2640b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic SkScalar (* const SegmentDXAtT[])(const SkPoint [], double ) = { 2650b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov NULL, 2660b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov LineDXAtT, 2670b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov QuadDXAtT, 2680b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov CubicDXAtT 2690b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov}; 2700b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov 2710b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganovstatic void LineSubDivide(const SkPoint a[2], double startT, double endT, 2720b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov SkPoint sub[2]) { 2730b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 2740b29a587142b19ed25dd6489cfa037d06145afd1Svetoslav Ganov _Line dst; 275 sub_divide(aLine, startT, endT, dst); 276 sub[0].fX = SkDoubleToScalar(dst[0].x); 277 sub[0].fY = SkDoubleToScalar(dst[0].y); 278 sub[1].fX = SkDoubleToScalar(dst[1].x); 279 sub[1].fY = SkDoubleToScalar(dst[1].y); 280} 281 282static void QuadSubDivide(const SkPoint a[3], double startT, double endT, 283 SkPoint sub[3]) { 284 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 285 {a[2].fX, a[2].fY}}; 286 Quadratic dst; 287 sub_divide(aQuad, startT, endT, dst); 288 sub[0].fX = SkDoubleToScalar(dst[0].x); 289 sub[0].fY = SkDoubleToScalar(dst[0].y); 290 sub[1].fX = SkDoubleToScalar(dst[1].x); 291 sub[1].fY = SkDoubleToScalar(dst[1].y); 292 sub[2].fX = SkDoubleToScalar(dst[2].x); 293 sub[2].fY = SkDoubleToScalar(dst[2].y); 294} 295 296static void CubicSubDivide(const SkPoint a[4], double startT, double endT, 297 SkPoint sub[4]) { 298 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 299 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 300 Cubic dst; 301 sub_divide(aCubic, startT, endT, dst); 302 sub[0].fX = SkDoubleToScalar(dst[0].x); 303 sub[0].fY = SkDoubleToScalar(dst[0].y); 304 sub[1].fX = SkDoubleToScalar(dst[1].x); 305 sub[1].fY = SkDoubleToScalar(dst[1].y); 306 sub[2].fX = SkDoubleToScalar(dst[2].x); 307 sub[2].fY = SkDoubleToScalar(dst[2].y); 308 sub[3].fX = SkDoubleToScalar(dst[3].x); 309 sub[3].fY = SkDoubleToScalar(dst[3].y); 310} 311 312static void (* const SegmentSubDivide[])(const SkPoint [], double , double , 313 SkPoint []) = { 314 NULL, 315 LineSubDivide, 316 QuadSubDivide, 317 CubicSubDivide 318}; 319 320#if DEBUG_UNUSED 321static void QuadSubBounds(const SkPoint a[3], double startT, double endT, 322 SkRect& bounds) { 323 SkPoint dst[3]; 324 QuadSubDivide(a, startT, endT, dst); 325 bounds.fLeft = bounds.fRight = dst[0].fX; 326 bounds.fTop = bounds.fBottom = dst[0].fY; 327 for (int index = 1; index < 3; ++index) { 328 bounds.growToInclude(dst[index].fX, dst[index].fY); 329 } 330} 331 332static void CubicSubBounds(const SkPoint a[4], double startT, double endT, 333 SkRect& bounds) { 334 SkPoint dst[4]; 335 CubicSubDivide(a, startT, endT, dst); 336 bounds.fLeft = bounds.fRight = dst[0].fX; 337 bounds.fTop = bounds.fBottom = dst[0].fY; 338 for (int index = 1; index < 4; ++index) { 339 bounds.growToInclude(dst[index].fX, dst[index].fY); 340 } 341} 342#endif 343 344static SkPath::Verb QuadReduceOrder(const SkPoint a[3], 345 SkTDArray<SkPoint>& reducePts) { 346 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 347 {a[2].fX, a[2].fY}}; 348 Quadratic dst; 349 int order = reduceOrder(aQuad, dst); 350 if (order == 3) { 351 return SkPath::kQuad_Verb; 352 } 353 for (int index = 0; index < order; ++index) { 354 SkPoint* pt = reducePts.append(); 355 pt->fX = SkDoubleToScalar(dst[index].x); 356 pt->fY = SkDoubleToScalar(dst[index].y); 357 } 358 return (SkPath::Verb) (order - 1); 359} 360 361static SkPath::Verb CubicReduceOrder(const SkPoint a[4], 362 SkTDArray<SkPoint>& reducePts) { 363 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 364 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 365 Cubic dst; 366 int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed); 367 if (order == 4) { 368 return SkPath::kCubic_Verb; 369 } 370 for (int index = 0; index < order; ++index) { 371 SkPoint* pt = reducePts.append(); 372 pt->fX = SkDoubleToScalar(dst[index].x); 373 pt->fY = SkDoubleToScalar(dst[index].y); 374 } 375 return (SkPath::Verb) (order - 1); 376} 377 378static bool QuadIsLinear(const SkPoint a[3]) { 379 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 380 {a[2].fX, a[2].fY}}; 381 return isLinear(aQuad, 0, 2); 382} 383 384static bool CubicIsLinear(const SkPoint a[4]) { 385 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 386 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 387 return isLinear(aCubic, 0, 3); 388} 389 390static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) { 391 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 392 double x[2]; 393 xy_at_t(aLine, startT, x[0], *(double*) 0); 394 xy_at_t(aLine, endT, x[1], *(double*) 0); 395 return SkMinScalar((float) x[0], (float) x[1]); 396} 397 398static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) { 399 const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 400 {a[2].fX, a[2].fY}}; 401 return (float) leftMostT(aQuad, startT, endT); 402} 403 404static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) { 405 const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 406 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 407 return (float) leftMostT(aCubic, startT, endT); 408} 409 410static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = { 411 NULL, 412 LineLeftMost, 413 QuadLeftMost, 414 CubicLeftMost 415}; 416 417#if DEBUG_UNUSED 418static bool IsCoincident(const SkPoint a[2], const SkPoint& above, 419 const SkPoint& below) { 420 const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 421 const _Line bLine = {{above.fX, above.fY}, {below.fX, below.fY}}; 422 return implicit_matches_ulps(aLine, bLine, 32); 423} 424#endif 425 426class Segment; 427 428// sorting angles 429// given angles of {dx dy ddx ddy dddx dddy} sort them 430class Angle { 431public: 432 // FIXME: this is bogus for quads and cubics 433 // if the quads and cubics' line from end pt to ctrl pt are coincident, 434 // there's no obvious way to determine the curve ordering from the 435 // derivatives alone. In particular, if one quadratic's coincident tangent 436 // is longer than the other curve, the final control point can place the 437 // longer curve on either side of the shorter one. 438 // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf 439 // may provide some help, but nothing has been figured out yet. 440 bool operator<(const Angle& rh) const { 441 if ((fDy < 0) ^ (rh.fDy < 0)) { 442 return fDy < 0; 443 } 444 if (fDy == 0 && rh.fDy == 0 && fDx != rh.fDx) { 445 return fDx < rh.fDx; 446 } 447 SkScalar cmp = fDx * rh.fDy - rh.fDx * fDy; 448 if (cmp) { 449 return cmp < 0; 450 } 451 if ((fDDy < 0) ^ (rh.fDDy < 0)) { 452 return fDDy < 0; 453 } 454 if (fDDy == 0 && rh.fDDy == 0 && fDDx != rh.fDDx) { 455 return fDDx < rh.fDDx; 456 } 457 cmp = fDDx * rh.fDDy - rh.fDDx * fDDy; 458 if (cmp) { 459 return cmp < 0; 460 } 461 if ((fDDDy < 0) ^ (rh.fDDDy < 0)) { 462 return fDDDy < 0; 463 } 464 if (fDDDy == 0 && rh.fDDDy == 0) { 465 return fDDDx < rh.fDDDx; 466 } 467 return fDDDx * rh.fDDDy < rh.fDDDx * fDDDy; 468 } 469 470 int end() const { 471 return fEnd; 472 } 473 474 bool isHorizontal() const { 475 return fDy == 0 && fDDy == 0 && fDDDy == 0; 476 } 477 478 // since all angles share a point, this needs to know which point 479 // is the common origin, i.e., whether the center is at pts[0] or pts[verb] 480 // practically, this should only be called by addAngle 481 void set(const SkPoint* pts, SkPath::Verb verb, const Segment* segment, 482 int start, int end) { 483 SkASSERT(start != end); 484 fSegment = segment; 485 fStart = start; 486 fEnd = end; 487 fDx = pts[1].fX - pts[0].fX; // b - a 488 fDy = pts[1].fY - pts[0].fY; 489 if (verb == SkPath::kLine_Verb) { 490 fDDx = fDDy = fDDDx = fDDDy = 0; 491 return; 492 } 493 fDDx = pts[2].fX - pts[1].fX - fDx; // a - 2b + c 494 fDDy = pts[2].fY - pts[1].fY - fDy; 495 if (verb == SkPath::kQuad_Verb) { 496 fDDDx = fDDDy = 0; 497 return; 498 } 499 fDDDx = pts[3].fX + 3 * (pts[1].fX - pts[2].fX) - pts[0].fX; 500 fDDDy = pts[3].fY + 3 * (pts[1].fY - pts[2].fY) - pts[0].fY; 501 } 502 503 // noncoincident quads/cubics may have the same initial angle 504 // as lines, so must sort by derivatives as well 505 // if flatness turns out to be a reasonable way to sort, use the below: 506 void setFlat(const SkPoint* pts, SkPath::Verb verb, Segment* segment, 507 int start, int end) { 508 fSegment = segment; 509 fStart = start; 510 fEnd = end; 511 fDx = pts[1].fX - pts[0].fX; // b - a 512 fDy = pts[1].fY - pts[0].fY; 513 if (verb == SkPath::kLine_Verb) { 514 fDDx = fDDy = fDDDx = fDDDy = 0; 515 return; 516 } 517 if (verb == SkPath::kQuad_Verb) { 518 int uplsX = FloatAsInt(pts[2].fX - pts[1].fY - fDx); 519 int uplsY = FloatAsInt(pts[2].fY - pts[1].fY - fDy); 520 int larger = std::max(abs(uplsX), abs(uplsY)); 521 int shift = 0; 522 double flatT; 523 SkPoint ddPt; // FIXME: get rid of copy (change fDD_ to point) 524 LineParameters implicitLine; 525 _Line tangent = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}}; 526 implicitLine.lineEndPoints(tangent); 527 implicitLine.normalize(); 528 while (larger > UlpsEpsilon * 1024) { 529 larger >>= 2; 530 ++shift; 531 flatT = 0.5 / (1 << shift); 532 QuadXYAtT(pts, flatT, &ddPt); 533 _Point _pt = {ddPt.fX, ddPt.fY}; 534 double distance = implicitLine.pointDistance(_pt); 535 if (approximately_zero(distance)) { 536 SkDebugf("%s ulps too small %1.9g\n", __FUNCTION__, distance); 537 break; 538 } 539 } 540 flatT = 0.5 / (1 << shift); 541 QuadXYAtT(pts, flatT, &ddPt); 542 fDDx = ddPt.fX - pts[0].fX; 543 fDDy = ddPt.fY - pts[0].fY; 544 SkASSERT(fDDx != 0 || fDDy != 0); 545 fDDDx = fDDDy = 0; 546 return; 547 } 548 SkASSERT(0); // FIXME: add cubic case 549 } 550 551 Segment* segment() const { 552 return const_cast<Segment*>(fSegment); 553 } 554 555 int sign() const { 556 return SkSign32(fStart - fEnd); 557 } 558 559 int start() const { 560 return fStart; 561 } 562 563private: 564 SkScalar fDx; 565 SkScalar fDy; 566 SkScalar fDDx; 567 SkScalar fDDy; 568 SkScalar fDDDx; 569 SkScalar fDDDy; 570 const Segment* fSegment; 571 int fStart; 572 int fEnd; 573}; 574 575static void sortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) { 576 int angleCount = angles.count(); 577 int angleIndex; 578 angleList.setReserve(angleCount); 579 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 580 *angleList.append() = &angles[angleIndex]; 581 } 582 QSort<Angle>(angleList.begin(), angleList.end() - 1); 583} 584 585// Bounds, unlike Rect, does not consider a line to be empty. 586struct Bounds : public SkRect { 587 static bool Intersects(const Bounds& a, const Bounds& b) { 588 return a.fLeft <= b.fRight && b.fLeft <= a.fRight && 589 a.fTop <= b.fBottom && b.fTop <= a.fBottom; 590 } 591 592 void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) { 593 if (left < fLeft) { 594 fLeft = left; 595 } 596 if (top < fTop) { 597 fTop = top; 598 } 599 if (right > fRight) { 600 fRight = right; 601 } 602 if (bottom > fBottom) { 603 fBottom = bottom; 604 } 605 } 606 607 void add(const Bounds& toAdd) { 608 add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom); 609 } 610 611 bool isEmpty() { 612 return fLeft > fRight || fTop > fBottom 613 || fLeft == fRight && fTop == fBottom 614 || isnan(fLeft) || isnan(fRight) 615 || isnan(fTop) || isnan(fBottom); 616 } 617 618 void setCubicBounds(const SkPoint a[4]) { 619 _Rect dRect; 620 Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 621 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 622 dRect.setBounds(cubic); 623 set((float) dRect.left, (float) dRect.top, (float) dRect.right, 624 (float) dRect.bottom); 625 } 626 627 void setQuadBounds(const SkPoint a[3]) { 628 const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 629 {a[2].fX, a[2].fY}}; 630 _Rect dRect; 631 dRect.setBounds(quad); 632 set((float) dRect.left, (float) dRect.top, (float) dRect.right, 633 (float) dRect.bottom); 634 } 635}; 636 637struct Span { 638 Segment* fOther; 639 mutable SkPoint const* fPt; // lazily computed as needed 640 double fT; 641 double fOtherT; // value at fOther[fOtherIndex].fT 642 int fOtherIndex; // can't be used during intersection 643 int fWindSum; // accumulated from contours surrounding this one 644 int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident 645 bool fDone; // if set, this span to next higher T has been processed 646}; 647 648class Segment { 649public: 650 Segment() { 651#if DEBUG_DUMP 652 fID = ++gSegmentID; 653#endif 654 } 655 656 bool activeAngles(int index) const { 657 double referenceT = fTs[index].fT; 658 int lesser = index; 659 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 660 if (activeAnglesInner(lesser)) { 661 return true; 662 } 663 } 664 do { 665 if (activeAnglesInner(index)) { 666 return true; 667 } 668 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 669 return false; 670 } 671 672 bool activeAnglesInner(int index) const { 673 Span* span = &fTs[index]; 674 Segment* other = span->fOther; 675 int oIndex = span->fOtherIndex; 676 int next = other->nextSpan(oIndex, 1); 677 if (next > 0 && !other->fTs[oIndex].fDone) { 678 return true; 679 } 680 int prev = other->nextSpan(oIndex, -1); 681 // edge leading into junction 682 return prev >= 0 && !other->fTs[prev].fDone; 683 } 684 685 SkScalar activeTop() const { 686 SkASSERT(!done()); 687 int count = fTs.count(); 688 SkScalar result = SK_ScalarMax; 689 bool lastDone = true; 690 for (int index = 0; index < count; ++index) { 691 bool done = fTs[index].fDone; 692 if (!done || !lastDone) { 693 SkScalar y = yAtT(index); 694 if (result > y) { 695 result = y; 696 } 697 } 698 lastDone = done; 699 } 700 SkASSERT(result < SK_ScalarMax); 701 return result; 702 } 703 704 void addAngle(SkTDArray<Angle>& angles, int start, int end) const { 705 SkASSERT(start != end); 706 SkPoint edge[4]; 707 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 708 Angle* angle = angles.append(); 709 angle->set(edge, fVerb, this, start, end); 710 } 711 712 void addCubic(const SkPoint pts[4]) { 713 init(pts, SkPath::kCubic_Verb); 714 fBounds.setCubicBounds(pts); 715 } 716 717 // FIXME: this needs to defer add for aligned consecutive line segments 718 SkPoint addCurveTo(int start, int end, SkPath& path, bool active) { 719 SkPoint edge[4]; 720 // OPTIMIZE? if not active, skip remainder and return xy_at_t(end) 721 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 722 if (active) { 723 #if DEBUG_PATH_CONSTRUCTION 724 SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__, 725 kLVerbStr[fVerb], edge[1].fX, edge[1].fY); 726 if (fVerb > 1) { 727 SkDebugf(" (%1.9g,%1.9g)", edge[2].fX, edge[2].fY); 728 } 729 if (fVerb > 2) { 730 SkDebugf(" (%1.9g,%1.9g)", edge[3].fX, edge[3].fY); 731 } 732 SkDebugf("\n"); 733 #endif 734 switch (fVerb) { 735 case SkPath::kLine_Verb: 736 path.lineTo(edge[1].fX, edge[1].fY); 737 break; 738 case SkPath::kQuad_Verb: 739 path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY); 740 break; 741 case SkPath::kCubic_Verb: 742 path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY, 743 edge[3].fX, edge[3].fY); 744 break; 745 } 746 } 747 return edge[fVerb]; 748 } 749 750 void addLine(const SkPoint pts[2]) { 751 init(pts, SkPath::kLine_Verb); 752 fBounds.set(pts, 2); 753 } 754 755 const SkPoint& addMoveTo(int tIndex, SkPath& path, bool active) { 756 const SkPoint& pt = xyAtT(tIndex); 757 if (active) { 758 #if DEBUG_PATH_CONSTRUCTION 759 SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY); 760 #endif 761 path.moveTo(pt.fX, pt.fY); 762 } 763 return pt; 764 } 765 766 // add 2 to edge or out of range values to get T extremes 767 void addOtherT(int index, double otherT, int otherIndex) { 768 Span& span = fTs[index]; 769 span.fOtherT = otherT; 770 span.fOtherIndex = otherIndex; 771 } 772 773 void addQuad(const SkPoint pts[3]) { 774 init(pts, SkPath::kQuad_Verb); 775 fBounds.setQuadBounds(pts); 776 } 777 778 // Defer all coincident edge processing until 779 // after normal intersections have been computed 780 781// no need to be tricky; insert in normal T order 782// resolve overlapping ts when considering coincidence later 783 784 // add non-coincident intersection. Resulting edges are sorted in T. 785 int addT(double newT, Segment* other) { 786 // FIXME: in the pathological case where there is a ton of intercepts, 787 // binary search? 788 int insertedAt = -1; 789 size_t tCount = fTs.count(); 790 for (size_t index = 0; index < tCount; ++index) { 791 // OPTIMIZATION: if there are three or more identical Ts, then 792 // the fourth and following could be further insertion-sorted so 793 // that all the edges are clockwise or counterclockwise. 794 // This could later limit segment tests to the two adjacent 795 // neighbors, although it doesn't help with determining which 796 // circular direction to go in. 797 if (newT < fTs[index].fT) { 798 insertedAt = index; 799 break; 800 } 801 } 802 Span* span; 803 if (insertedAt >= 0) { 804 span = fTs.insert(insertedAt); 805 } else { 806 insertedAt = tCount; 807 span = fTs.append(); 808 } 809 span->fT = newT; 810 span->fOther = other; 811 span->fPt = NULL; 812 span->fWindSum = SK_MinS32; 813 span->fWindValue = 1; 814 if ((span->fDone = newT == 1)) { 815 ++fDoneSpans; 816 } 817 return insertedAt; 818 } 819 820 // set spans from start to end to decrement by one 821 // note this walks other backwards 822 // FIMXE: there's probably an edge case that can be constructed where 823 // two span in one segment are separated by float epsilon on one span but 824 // not the other, if one segment is very small. For this 825 // case the counts asserted below may or may not be enough to separate the 826 // spans. Even if the counts work out, what if the spanw aren't correctly 827 // sorted? It feels better in such a case to match the span's other span 828 // pointer since both coincident segments must contain the same spans. 829 void addTCancel(double startT, double endT, Segment& other, 830 double oStartT, double oEndT) { 831 SkASSERT(endT - startT >= FLT_EPSILON); 832 SkASSERT(oEndT - oStartT >= FLT_EPSILON); 833 int index = 0; 834 while (startT - fTs[index].fT >= FLT_EPSILON) { 835 ++index; 836 } 837 int oIndex = other.fTs.count(); 838 while (other.fTs[--oIndex].fT - oEndT > -FLT_EPSILON) 839 ; 840 Span* test = &fTs[index]; 841 Span* oTest = &other.fTs[oIndex]; 842 do { 843 bool decrement = test->fWindValue && oTest->fWindValue; 844 Span* end = test; 845 do { 846 if (decrement) { 847 SkASSERT(end->fWindValue > 0); 848 if (--(end->fWindValue) == 0) { 849 end->fDone = true; 850 ++fDoneSpans; 851 } 852 } 853 end = &fTs[++index]; 854 } while (end->fT - test->fT < FLT_EPSILON); 855 Span* oTestStart = oTest; 856 do { 857 if (decrement) { 858 SkASSERT(oTestStart->fWindValue > 0); 859 if (--(oTestStart->fWindValue) == 0) { 860 oTestStart->fDone = true; 861 ++other.fDoneSpans; 862 } 863 } 864 if (!oIndex) { 865 break; 866 } 867 oTestStart = &other.fTs[--oIndex]; 868 } while (oTest->fT - oTestStart->fT < FLT_EPSILON); 869 test = end; 870 oTest = oTestStart; 871 } while (test->fT < endT - FLT_EPSILON); 872 SkASSERT(!oIndex || oTest->fT <= oStartT - FLT_EPSILON); 873 } 874 875 // set spans from start to end to increment the greater by one and decrement 876 // the lesser 877 void addTCoincident(double startT, double endT, Segment& other, 878 double oStartT, double oEndT) { 879 SkASSERT(endT - startT >= FLT_EPSILON); 880 SkASSERT(oEndT - oStartT >= FLT_EPSILON); 881 int index = 0; 882 while (startT - fTs[index].fT >= FLT_EPSILON) { 883 ++index; 884 } 885 int oIndex = 0; 886 while (oStartT - other.fTs[oIndex].fT >= FLT_EPSILON) { 887 ++oIndex; 888 } 889 Span* test = &fTs[index]; 890 Span* oTest = &other.fTs[oIndex]; 891 SkTDArray<double> outsideTs; 892 SkTDArray<double> oOutsideTs; 893 do { 894 bool transfer = test->fWindValue && oTest->fWindValue; 895 bool decrementOther = test->fWindValue >= oTest->fWindValue; 896 Span* end = test; 897 double startT = end->fT; 898 double oStartT = oTest->fT; 899 do { 900 if (transfer) { 901 if (decrementOther) { 902 ++(end->fWindValue); 903 } else { 904 SkASSERT(end->fWindValue > 0); 905 if (--(end->fWindValue) == 0) { 906 end->fDone = true; 907 ++fDoneSpans; 908 int outCount = outsideTs.count(); 909 if (outCount == 0 || end->fT - outsideTs[outCount - 2] 910 >= FLT_EPSILON) { 911 *outsideTs.append() = end->fT; 912 *outsideTs.append() = oStartT; 913 } 914 } 915 } 916 } 917 end = &fTs[++index]; 918 } while (end->fT - test->fT < FLT_EPSILON); 919 Span* oEnd = oTest; 920 do { 921 if (transfer) { 922 if (decrementOther) { 923 SkASSERT(oEnd->fWindValue > 0); 924 if (--(oEnd->fWindValue) == 0) { 925 oEnd->fDone = true; 926 ++other.fDoneSpans; 927 int oOutCount = oOutsideTs.count(); 928 if (oOutCount == 0 || oEnd->fT 929 - oOutsideTs[oOutCount - 2] >= FLT_EPSILON) { 930 *oOutsideTs.append() = oEnd->fT; 931 *oOutsideTs.append() = startT; 932 } 933 } 934 } else { 935 ++(oEnd->fWindValue); 936 } 937 } 938 oEnd = &other.fTs[++oIndex]; 939 } while (oEnd->fT - oTest->fT < FLT_EPSILON); 940 test = end; 941 oTest = oEnd; 942 } while (test->fT < endT - FLT_EPSILON); 943 SkASSERT(oTest->fT < oEndT + FLT_EPSILON); 944 SkASSERT(oTest->fT > oEndT - FLT_EPSILON); 945 if (!done() && outsideTs.count()) { 946 addTOutsides(outsideTs, other, oEndT); 947 } 948 if (!other.done() && oOutsideTs.count()) { 949 other.addTOutsides(oOutsideTs, *this, endT); 950 } 951 } 952 953 void addTOutsides(const SkTDArray<double>& outsideTs, Segment& other, 954 double otherEnd) { 955 int count = outsideTs.count(); 956 double endT = 0; 957 int endSpan = 0; 958 for (int index = 0; index < count; index += 2) { 959 double t = outsideTs[index]; 960 double otherT = outsideTs[index + 1]; 961 if (t > 1 - FLT_EPSILON) { 962 return; 963 } 964 if (t - endT > FLT_EPSILON) { 965 endSpan = addTDonePair(t, other, otherT); 966 } 967 do { 968 endT = fTs[++endSpan].fT; 969 } while (endT - t < FLT_EPSILON); 970 } 971 addTPair(endT, other, otherEnd); 972 } 973 974 // match the other.fWindValue to its mates 975 int addTDonePair(double t, Segment& other, double otherT) { 976 int insertedAt = addTPair(t, other, otherT); 977 Span& end = fTs[insertedAt]; 978 SkASSERT(end.fWindValue == 1); 979 end.fWindValue = 0; 980 end.fDone = true; 981 ++fDoneSpans; 982 Span& otherEnd = other.fTs[end.fOtherIndex]; 983 Span* match = NULL; 984 if (end.fOtherIndex > 0) { 985 match = &other.fTs[end.fOtherIndex - 1]; 986 } 987 if (!match || match->fT < otherT) { 988 match = &other.fTs[end.fOtherIndex + 1]; 989 } 990 otherEnd.fWindValue = match->fWindValue; 991 return insertedAt; 992 } 993 994 int addTPair(double t, Segment& other, double otherT) { 995 int insertedAt = addT(t, &other); 996 int otherInsertedAt = other.addT(otherT, this); 997 addOtherT(insertedAt, otherT, otherInsertedAt); 998 other.addOtherT(otherInsertedAt, t, insertedAt); 999 return insertedAt; 1000 } 1001 1002 void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const { 1003 // add edge leading into junction 1004 if (fTs[SkMin32(end, start)].fWindValue > 0) { 1005 addAngle(angles, end, start); 1006 } 1007 // add edge leading away from junction 1008 int step = SkSign32(end - start); 1009 int tIndex = nextSpan(end, step); 1010 if (tIndex >= 0 && fTs[SkMin32(end, tIndex)].fWindValue > 0) { 1011 addAngle(angles, end, tIndex); 1012 } 1013 } 1014 1015 const Bounds& bounds() const { 1016 return fBounds; 1017 } 1018 1019 void buildAngles(int index, SkTDArray<Angle>& angles) const { 1020 double referenceT = fTs[index].fT; 1021 int lesser = index; 1022 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 1023 buildAnglesInner(lesser, angles); 1024 } 1025 do { 1026 buildAnglesInner(index, angles); 1027 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 1028 } 1029 1030 void buildAnglesInner(int index, SkTDArray<Angle>& angles) const { 1031 Span* span = &fTs[index]; 1032 Segment* other = span->fOther; 1033 // if there is only one live crossing, and no coincidence, continue 1034 // in the same direction 1035 // if there is coincidence, the only choice may be to reverse direction 1036 // find edge on either side of intersection 1037 int oIndex = span->fOtherIndex; 1038 // if done == -1, prior span has already been processed 1039 int step = 1; 1040 int next = other->nextSpan(oIndex, step); 1041 if (next < 0) { 1042 step = -step; 1043 next = other->nextSpan(oIndex, step); 1044 } 1045 // add candidate into and away from junction 1046 other->addTwoAngles(next, oIndex, angles); 1047 } 1048 1049 bool cancels(const Segment& other) const { 1050 SkASSERT(fVerb == SkPath::kLine_Verb); 1051 SkASSERT(other.fVerb == SkPath::kLine_Verb); 1052 SkPoint dxy = fPts[0] - fPts[1]; 1053 SkPoint odxy = other.fPts[0] - other.fPts[1]; 1054 return dxy.fX * odxy.fX < 0 || dxy.fY * odxy.fY < 0; 1055 } 1056 1057 // figure out if the segment's ascending T goes clockwise or not 1058 // not enough context to write this as shown 1059 // instead, add all segments meeting at the top 1060 // sort them using buildAngleList 1061 // find the first in the sort 1062 // see if ascendingT goes to top 1063 bool clockwise(int /* tIndex */) const { 1064 SkASSERT(0); // incomplete 1065 return false; 1066 } 1067 1068 int crossedSpan(const SkPoint& basePt, SkScalar& bestY, double& hitT) const { 1069 int start = 0; 1070 int bestT = -1; 1071 SkScalar top = bounds().fTop; 1072 SkScalar bottom = bounds().fBottom; 1073 int end; 1074 do { 1075 end = nextSpan(start, 1); 1076 SkPoint edge[4]; 1077 // OPTIMIZE: wrap this so that if start==0 end==fTCount-1 we can 1078 // work with the original data directly 1079 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 1080 // intersect ray starting at basePt with edge 1081 Intersections intersections; 1082 int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX, 1083 false, intersections); 1084 if (pts == 0) { 1085 continue; 1086 } 1087 if (pts > 1 && fVerb == SkPath::kLine_Verb) { 1088 // if the intersection is edge on, wait for another one 1089 continue; 1090 } 1091 SkASSERT(pts == 1); // FIXME: more code required to disambiguate 1092 SkPoint pt; 1093 double foundT = intersections.fT[0][0]; 1094 (*SegmentXYAtT[fVerb])(fPts, foundT, &pt); 1095 if (bestY < pt.fY) { 1096 bestY = pt.fY; 1097 bestT = foundT < 1 ? start : end; 1098 hitT = foundT; 1099 } 1100 start = end; 1101 } while (fTs[end].fT != 1); 1102 return bestT; 1103 } 1104 1105 bool done() const { 1106 SkASSERT(fDoneSpans <= fTs.count()); 1107 return fDoneSpans == fTs.count(); 1108 } 1109 1110 // so the span needs to contain the pairing info found here 1111 // this should include the winding computed for the edge, and 1112 // what edge it connects to, and whether it is discarded 1113 // (maybe discarded == abs(winding) > 1) ? 1114 // only need derivatives for duration of sorting, add a new struct 1115 // for pairings, remove extra spans that have zero length and 1116 // reference an unused other 1117 // for coincident, the last span on the other may be marked done 1118 // (always?) 1119 1120 // if loop is exhausted, contour may be closed. 1121 // FIXME: pass in close point so we can check for closure 1122 1123 // given a segment, and a sense of where 'inside' is, return the next 1124 // segment. If this segment has an intersection, or ends in multiple 1125 // segments, find the mate that continues the outside. 1126 // note that if there are multiples, but no coincidence, we can limit 1127 // choices to connections in the correct direction 1128 1129 // mark found segments as done 1130 1131 // start is the index of the beginning T of this edge 1132 // it is guaranteed to have an end which describes a non-zero length (?) 1133 // winding -1 means ccw, 1 means cw 1134 // firstFind allows coincident edges to be treated differently 1135 Segment* findNext(SkTDArray<Span*>& chase, int winding, const int startIndex, 1136 const int endIndex, 1137 int& nextStart, int& nextEnd, int& flipped, bool firstFind) { 1138 SkASSERT(startIndex != endIndex); 1139 int count = fTs.count(); 1140 SkASSERT(startIndex < endIndex ? startIndex < count - 1 1141 : startIndex > 0); 1142 int step = SkSign32(endIndex - startIndex); 1143 int end = nextSpan(startIndex, step); 1144 SkASSERT(end >= 0); 1145 Span* endSpan = &fTs[end]; 1146 Segment* other; 1147 if (isSimple(end)) { 1148 // mark the smaller of startIndex, endIndex done, and all adjacent 1149 // spans with the same T value (but not 'other' spans) 1150 markDone(SkMin32(startIndex, endIndex), winding); 1151 other = endSpan->fOther; 1152 nextStart = endSpan->fOtherIndex; 1153 nextEnd = nextStart + step; 1154 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count()); 1155 return other; 1156 } 1157 // more than one viable candidate -- measure angles to find best 1158 SkTDArray<Angle> angles; 1159 SkASSERT(startIndex - endIndex != 0); 1160 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 1161 addTwoAngles(startIndex, end, angles); 1162 buildAngles(end, angles); 1163 SkTDArray<Angle*> sorted; 1164 sortAngles(angles, sorted); 1165 int angleCount = angles.count(); 1166 int firstIndex = findStartingEdge(sorted, startIndex, end); 1167 1168 SkASSERT(firstIndex >= 0); 1169 int startWinding = winding; 1170 int nextIndex = firstIndex + 1; 1171 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 1172 const Angle* foundAngle = NULL; 1173 // iterate through the angle, and compute everyone's winding 1174 bool firstEdge = true; 1175 do { 1176 if (nextIndex == angleCount) { 1177 nextIndex = 0; 1178 } 1179 const Angle* nextAngle = sorted[nextIndex]; 1180 int maxWinding = winding; 1181 Segment* nextSegment = nextAngle->segment(); 1182 int windValue = nextSegment->windValue(nextAngle); 1183 SkASSERT(windValue > 0); 1184 winding -= nextAngle->sign() * windValue; 1185 #if DEBUG_WINDING 1186 SkDebugf("%s maxWinding=%d winding=%d\n", __FUNCTION__, maxWinding, 1187 winding); 1188 #endif 1189 if (maxWinding * winding < 0) { 1190 flipped = -flipped; 1191 SkDebugf("flipped sign %d %d\n", maxWinding, winding); 1192 } 1193 firstEdge = false; 1194 if (!winding) { 1195 if (!foundAngle) { 1196 foundAngle = nextAngle; 1197 } 1198 continue; 1199 } 1200 if (nextSegment->done()) { 1201 continue; 1202 } 1203 // if the winding is non-zero, nextAngle does not connect to 1204 // current chain. If we haven't done so already, mark the angle 1205 // as done, record the winding value, and mark connected unambiguous 1206 // segments as well. 1207 if (nextSegment->windSum(nextAngle) == SK_MinS32) { 1208 if (abs(maxWinding) < abs(winding)) { 1209 maxWinding = winding; 1210 } 1211 Span* last; 1212 if (foundAngle) { 1213 last = nextSegment->markAndChaseWinding(nextAngle, maxWinding); 1214 } else { 1215 last = nextSegment->markAndChaseDone(nextAngle, maxWinding); 1216 } 1217 if (last) { 1218 *chase.append() = last; 1219 } 1220 } 1221 } while (++nextIndex != lastIndex); 1222 sorted[firstIndex]->segment()-> 1223 markDone(SkMin32(startIndex, endIndex), startWinding); 1224 if (!foundAngle) { 1225 return NULL; 1226 } 1227 nextStart = foundAngle->start(); 1228 nextEnd = foundAngle->end(); 1229 return foundAngle->segment(); 1230 } 1231 1232 int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) { 1233 int angleCount = sorted.count(); 1234 int firstIndex = -1; 1235 for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 1236 const Angle* angle = sorted[angleIndex]; 1237 if (angle->segment() == this && angle->start() == end && 1238 angle->end() == start) { 1239 firstIndex = angleIndex; 1240 break; 1241 } 1242 } 1243 return firstIndex; 1244 } 1245 1246 // FIXME: this is tricky code; needs its own unit test 1247 void findTooCloseToCall(int /* winding */ ) { // FIXME: winding should be considered 1248 int count = fTs.count(); 1249 if (count < 3) { // require t=0, x, 1 at minimum 1250 return; 1251 } 1252 int matchIndex = 0; 1253 int moCount; 1254 Span* match; 1255 Segment* mOther; 1256 do { 1257 match = &fTs[matchIndex]; 1258 mOther = match->fOther; 1259 moCount = mOther->fTs.count(); 1260 if (moCount >= 3) { 1261 break; 1262 } 1263 if (++matchIndex >= count) { 1264 return; 1265 } 1266 } while (true); // require t=0, x, 1 at minimum 1267 // OPTIMIZATION: defer matchPt until qualifying toCount is found? 1268 const SkPoint* matchPt = &xyAtT(match); 1269 // look for a pair of nearby T values that map to the same (x,y) value 1270 // if found, see if the pair of other segments share a common point. If 1271 // so, the span from here to there is coincident. 1272 for (int index = matchIndex + 1; index < count; ++index) { 1273 Span* test = &fTs[index]; 1274 if (test->fDone) { 1275 continue; 1276 } 1277 Segment* tOther = test->fOther; 1278 int toCount = tOther->fTs.count(); 1279 if (toCount < 3) { // require t=0, x, 1 at minimum 1280 continue; 1281 } 1282 const SkPoint* testPt = &xyAtT(test); 1283 if (*matchPt != *testPt) { 1284 matchIndex = index; 1285 moCount = toCount; 1286 match = test; 1287 mOther = tOther; 1288 matchPt = testPt; 1289 continue; 1290 } 1291 int moStart = -1; 1292 int moEnd = -1; 1293 double moStartT, moEndT; 1294 for (int moIndex = 0; moIndex < moCount; ++moIndex) { 1295 Span& moSpan = mOther->fTs[moIndex]; 1296 if (moSpan.fDone) { 1297 continue; 1298 } 1299 if (moSpan.fOther == this) { 1300 if (moSpan.fOtherT == match->fT) { 1301 moStart = moIndex; 1302 moStartT = moSpan.fT; 1303 } 1304 continue; 1305 } 1306 if (moSpan.fOther == tOther) { 1307 SkASSERT(moEnd == -1); 1308 moEnd = moIndex; 1309 moEndT = moSpan.fT; 1310 } 1311 } 1312 if (moStart < 0 || moEnd < 0) { 1313 continue; 1314 } 1315 // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test 1316 if (moStartT == moEndT) { 1317 continue; 1318 } 1319 int toStart = -1; 1320 int toEnd = -1; 1321 double toStartT, toEndT; 1322 for (int toIndex = 0; toIndex < toCount; ++toIndex) { 1323 Span& toSpan = tOther->fTs[toIndex]; 1324 if (toSpan.fOther == this) { 1325 if (toSpan.fOtherT == test->fT) { 1326 toStart = toIndex; 1327 toStartT = toSpan.fT; 1328 } 1329 continue; 1330 } 1331 if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) { 1332 SkASSERT(toEnd == -1); 1333 toEnd = toIndex; 1334 toEndT = toSpan.fT; 1335 } 1336 } 1337 // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test 1338 if (toStart <= 0 || toEnd <= 0) { 1339 continue; 1340 } 1341 if (toStartT == toEndT) { 1342 continue; 1343 } 1344 // test to see if the segment between there and here is linear 1345 if (!mOther->isLinear(moStart, moEnd) 1346 || !tOther->isLinear(toStart, toEnd)) { 1347 continue; 1348 } 1349 // FIXME: defer implementation until the rest works 1350 // this may share code with regular coincident detection 1351 SkASSERT(0); 1352 #if 0 1353 if (flipped) { 1354 mOther->addTCancel(moStart, moEnd, tOther, tStart, tEnd); 1355 } else { 1356 mOther->addTCoincident(moStart, moEnd, tOther, tStart, tEnd); 1357 } 1358 #endif 1359 } 1360 } 1361 1362 // OPTIMIZATION : for a pair of lines, can we compute points at T (cached) 1363 // and use more concise logic like the old edge walker code? 1364 // FIXME: this needs to deal with coincident edges 1365 Segment* findTop(int& tIndex, int& endIndex) { 1366 // iterate through T intersections and return topmost 1367 // topmost tangent from y-min to first pt is closer to horizontal 1368 SkASSERT(!done()); 1369 int firstT; 1370 int lastT; 1371 SkPoint topPt; 1372 topPt.fY = SK_ScalarMax; 1373 int count = fTs.count(); 1374 // see if either end is not done since we want smaller Y of the pair 1375 bool lastDone = true; 1376 for (int index = 0; index < count; ++index) { 1377 const Span& span = fTs[index]; 1378 if (!span.fDone || !lastDone) { 1379 const SkPoint& intercept = xyAtT(&span); 1380 if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY 1381 && topPt.fX > intercept.fX)) { 1382 topPt = intercept; 1383 firstT = lastT = index; 1384 } else if (topPt == intercept) { 1385 lastT = index; 1386 } 1387 } 1388 lastDone = span.fDone; 1389 } 1390 // sort the edges to find the leftmost 1391 int step = 1; 1392 int end = nextSpan(firstT, step); 1393 if (end == -1) { 1394 step = -1; 1395 end = nextSpan(firstT, step); 1396 SkASSERT(end != -1); 1397 } 1398 // if the topmost T is not on end, or is three-way or more, find left 1399 // look for left-ness from tLeft to firstT (matching y of other) 1400 SkTDArray<Angle> angles; 1401 SkASSERT(firstT - end != 0); 1402 addTwoAngles(end, firstT, angles); 1403 buildAngles(firstT, angles); 1404 SkTDArray<Angle*> sorted; 1405 sortAngles(angles, sorted); 1406 // skip edges that have already been processed 1407 firstT = -1; 1408 Segment* leftSegment; 1409 do { 1410 const Angle* angle = sorted[++firstT]; 1411 leftSegment = angle->segment(); 1412 tIndex = angle->end(); 1413 endIndex = angle->start(); 1414 } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone); 1415 return leftSegment; 1416 } 1417 1418 // FIXME: not crazy about this 1419 // when the intersections are performed, the other index is into an 1420 // incomplete array. as the array grows, the indices become incorrect 1421 // while the following fixes the indices up again, it isn't smart about 1422 // skipping segments whose indices are already correct 1423 // assuming we leave the code that wrote the index in the first place 1424 void fixOtherTIndex() { 1425 int iCount = fTs.count(); 1426 for (int i = 0; i < iCount; ++i) { 1427 Span& iSpan = fTs[i]; 1428 double oT = iSpan.fOtherT; 1429 Segment* other = iSpan.fOther; 1430 int oCount = other->fTs.count(); 1431 for (int o = 0; o < oCount; ++o) { 1432 Span& oSpan = other->fTs[o]; 1433 if (oT == oSpan.fT && this == oSpan.fOther) { 1434 iSpan.fOtherIndex = o; 1435 break; 1436 } 1437 } 1438 } 1439 } 1440 1441 // OPTIMIZATION: uses tail recursion. Unwise? 1442 Span* innerChaseDone(int index, int step, int winding) { 1443 int end = nextSpan(index, step); 1444 if (multipleSpans(index, end)) { 1445 return index >= 0 ? &fTs[index] : NULL; 1446 } 1447 const Span& endSpan = fTs[end]; 1448 Segment* other = endSpan.fOther; 1449 index = endSpan.fOtherIndex; 1450 int otherEnd = other->nextSpan(index, step); 1451 Span* last = other->innerChaseDone(index, step, winding); 1452 other->markDone(SkMin32(index, otherEnd), winding); 1453 return last; 1454 } 1455 1456 Span* innerChaseWinding(int index, int step, int winding) { 1457 int end = nextSpan(index, step); 1458 if (multipleSpans(index, end)) { 1459 return index >= 0 ? &fTs[index] : NULL; 1460 } 1461 const Span& endSpan = fTs[end]; 1462 Segment* other = endSpan.fOther; 1463 index = endSpan.fOtherIndex; 1464 int otherEnd = other->nextSpan(index, step); 1465 int min = SkMin32(index, otherEnd); 1466 if (other->fTs[min].fWindSum != SK_MinS32) { 1467 SkASSERT(other->fTs[index].fWindSum == winding); 1468 return NULL; 1469 } 1470 Span* last = other->innerChaseWinding(index, step, winding); 1471 other->markWinding(min, winding); 1472 return last; 1473 } 1474 1475 void init(const SkPoint pts[], SkPath::Verb verb) { 1476 fPts = pts; 1477 fVerb = verb; 1478 fDoneSpans = 0; 1479 } 1480 1481 bool intersected() const { 1482 return fTs.count() > 0; 1483 } 1484 1485 bool isLinear(int start, int end) const { 1486 if (fVerb == SkPath::kLine_Verb) { 1487 return true; 1488 } 1489 if (fVerb == SkPath::kQuad_Verb) { 1490 SkPoint qPart[3]; 1491 QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart); 1492 return QuadIsLinear(qPart); 1493 } else { 1494 SkASSERT(fVerb == SkPath::kCubic_Verb); 1495 SkPoint cPart[4]; 1496 CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart); 1497 return CubicIsLinear(cPart); 1498 } 1499 } 1500 1501 // OPTIMIZE: successive calls could start were the last leaves off 1502 // or calls could specialize to walk forwards or backwards 1503 bool isMissing(double startT) const { 1504 size_t tCount = fTs.count(); 1505 for (size_t index = 0; index < tCount; ++index) { 1506 if (fabs(startT - fTs[index].fT) < FLT_EPSILON) { 1507 return false; 1508 } 1509 } 1510 return true; 1511 } 1512 1513 bool isSimple(int end) const { 1514 int count = fTs.count(); 1515 if (count == 2) { 1516 return true; 1517 } 1518 double t = fTs[end].fT; 1519 if (t < FLT_EPSILON) { 1520 return fTs[1].fT >= FLT_EPSILON; 1521 } 1522 if (t > 1 - FLT_EPSILON) { 1523 return fTs[count - 2].fT <= 1 - FLT_EPSILON; 1524 } 1525 return false; 1526 } 1527 1528 bool isHorizontal() const { 1529 return fBounds.fTop == fBounds.fBottom; 1530 } 1531 1532 bool isVertical() const { 1533 return fBounds.fLeft == fBounds.fRight; 1534 } 1535 1536 SkScalar leftMost(int start, int end) const { 1537 return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT); 1538 } 1539 1540 // this span is excluded by the winding rule -- chase the ends 1541 // as long as they are unambiguous to mark connections as done 1542 // and give them the same winding value 1543 Span* markAndChaseDone(const Angle* angle, int winding) { 1544 int index = angle->start(); 1545 int endIndex = angle->end(); 1546 int step = SkSign32(endIndex - index); 1547 Span* last = innerChaseDone(index, step, winding); 1548 markDone(SkMin32(index, endIndex), winding); 1549 return last; 1550 } 1551 1552 Span* markAndChaseWinding(const Angle* angle, int winding) { 1553 int index = angle->start(); 1554 int endIndex = angle->end(); 1555 int min = SkMin32(index, endIndex); 1556 int step = SkSign32(endIndex - index); 1557 Span* last = innerChaseWinding(index, step, winding); 1558 markWinding(min, winding); 1559 return last; 1560 } 1561 1562 // FIXME: this should also mark spans with equal (x,y) 1563 // This may be called when the segment is already marked done. While this 1564 // wastes time, it shouldn't do any more than spin through the T spans. 1565 // OPTIMIZATION: abort on first done found (assuming that this code is 1566 // always called to mark segments done). 1567 void markDone(int index, int winding) { 1568 // SkASSERT(!done()); 1569 double referenceT = fTs[index].fT; 1570 int lesser = index; 1571 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 1572 Span& span = fTs[lesser]; 1573 if (span.fDone) { 1574 continue; 1575 } 1576 #if DEBUG_MARK_DONE 1577 const SkPoint& pt = xyAtT(&span); 1578 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", 1579 __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding); 1580 #endif 1581 span.fDone = true; 1582 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1583 span.fWindSum = winding; 1584 fDoneSpans++; 1585 } 1586 do { 1587 Span& span = fTs[index]; 1588 // SkASSERT(!span.fDone); 1589 if (span.fDone) { 1590 continue; 1591 } 1592 #if DEBUG_MARK_DONE 1593 const SkPoint& pt = xyAtT(&span); 1594 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", 1595 __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding); 1596 #endif 1597 span.fDone = true; 1598 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1599 span.fWindSum = winding; 1600 fDoneSpans++; 1601 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 1602 } 1603 1604 void markWinding(int index, int winding) { 1605 SkASSERT(!done()); 1606 double referenceT = fTs[index].fT; 1607 int lesser = index; 1608 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 1609 Span& span = fTs[lesser]; 1610 if (span.fDone) { 1611 continue; 1612 } 1613 SkASSERT(span.fWindValue == 1 || winding == 0); 1614 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1615 #if DEBUG_MARK_DONE 1616 const SkPoint& pt = xyAtT(&span); 1617 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", 1618 __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding); 1619 #endif 1620 span.fWindSum = winding; 1621 } 1622 do { 1623 Span& span = fTs[index]; 1624 // SkASSERT(!span.fDone || span.fCoincident); 1625 if (span.fDone) { 1626 continue; 1627 } 1628 SkASSERT(span.fWindValue == 1 || winding == 0); 1629 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1630 #if DEBUG_MARK_DONE 1631 const SkPoint& pt = xyAtT(&span); 1632 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", 1633 __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding); 1634 #endif 1635 span.fWindSum = winding; 1636 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 1637 } 1638 1639 bool multipleSpans(int& index, int end) const { 1640 if (end > index ? end + 1 >= fTs.count() : end <= 0) { 1641 return false; 1642 } 1643 // return span if when chasing, two or more radiating spans are not done 1644 int lesser = SkMin32(index, end); 1645 if (!activeAngles(lesser)) { 1646 index = -1; 1647 } 1648 index = lesser; 1649 return true; 1650 } 1651 1652 // This has callers for two different situations: one establishes the end 1653 // of the current span, and one establishes the beginning of the next span 1654 // (thus the name). When this is looking for the end of the current span, 1655 // coincidence is found when the beginning Ts contain -step and the end 1656 // contains step. When it is looking for the beginning of the next, the 1657 // first Ts found can be ignored and the last Ts should contain -step. 1658 // OPTIMIZATION: probably should split into two functions 1659 int nextSpan(int from, int step) const { 1660 const Span& fromSpan = fTs[from]; 1661 int count = fTs.count(); 1662 int to = from; 1663 while (step > 0 ? ++to < count : --to >= 0) { 1664 const Span& span = fTs[to]; 1665 if ((step > 0 ? span.fT - fromSpan.fT : fromSpan.fT - span.fT) < FLT_EPSILON) { 1666 continue; 1667 } 1668 return to; 1669 } 1670 return -1; 1671 } 1672 1673 const SkPoint* pts() const { 1674 return fPts; 1675 } 1676 1677 void reset() { 1678 init(NULL, (SkPath::Verb) -1); 1679 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 1680 fTs.reset(); 1681 } 1682 1683 // OPTIMIZATION: mark as debugging only if used solely by tests 1684 const Span& span(int tIndex) const { 1685 return fTs[tIndex]; 1686 } 1687 1688 int spanSign(int startIndex, int endIndex) const { 1689 return startIndex < endIndex ? -fTs[startIndex].fWindValue : 1690 fTs[endIndex].fWindValue; 1691 } 1692 1693 // OPTIMIZATION: mark as debugging only if used solely by tests 1694 double t(int tIndex) const { 1695 return fTs[tIndex].fT; 1696 } 1697 1698 void updatePts(const SkPoint pts[]) { 1699 fPts = pts; 1700 } 1701 1702 SkPath::Verb verb() const { 1703 return fVerb; 1704 } 1705 1706 int windSum(int tIndex) const { 1707 return fTs[tIndex].fWindSum; 1708 } 1709 1710 int windSum(const Angle* angle) const { 1711 int start = angle->start(); 1712 int end = angle->end(); 1713 int index = SkMin32(start, end); 1714 return windSum(index); 1715 } 1716 1717 int windValue(int tIndex) const { 1718 return fTs[tIndex].fWindValue; 1719 } 1720 1721 int windValue(const Angle* angle) const { 1722 int start = angle->start(); 1723 int end = angle->end(); 1724 int index = SkMin32(start, end); 1725 return windValue(index); 1726 } 1727 1728 SkScalar xAtT(const Span* span) const { 1729 return xyAtT(span).fX; 1730 } 1731 1732 const SkPoint& xyAtT(int index) const { 1733 return xyAtT(&fTs[index]); 1734 } 1735 1736 const SkPoint& xyAtT(const Span* span) const { 1737 if (!span->fPt) { 1738 if (span->fT == 0) { 1739 span->fPt = &fPts[0]; 1740 } else if (span->fT == 1) { 1741 span->fPt = &fPts[fVerb]; 1742 } else { 1743 SkPoint* pt = fIntersections.append(); 1744 (*SegmentXYAtT[fVerb])(fPts, span->fT, pt); 1745 span->fPt = pt; 1746 } 1747 } 1748 return *span->fPt; 1749 } 1750 1751 SkScalar yAtT(int index) const { 1752 return yAtT(&fTs[index]); 1753 } 1754 1755 SkScalar yAtT(const Span* span) const { 1756 return xyAtT(span).fY; 1757 } 1758 1759#if DEBUG_DUMP 1760 void dump() const { 1761 const char className[] = "Segment"; 1762 const int tab = 4; 1763 for (int i = 0; i < fTs.count(); ++i) { 1764 SkPoint out; 1765 (*SegmentXYAtT[fVerb])(fPts, t(i), &out); 1766 SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d" 1767 " otherT=%1.9g windSum=%d\n", 1768 tab + sizeof(className), className, fID, 1769 kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY, 1770 fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum); 1771 } 1772 SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)", 1773 tab + sizeof(className), className, fID, 1774 fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); 1775 } 1776#endif 1777 1778#if DEBUG_ACTIVE_SPANS 1779 void debugShowActiveSpans(int contourID, int segmentIndex) { 1780 if (done()) { 1781 return; 1782 } 1783 for (int i = 0; i < fTs.count(); ++i) { 1784 if (fTs[i].fDone) { 1785 continue; 1786 } 1787 SkDebugf("%s contour=%d segment=%d (%d)", __FUNCTION__, contourID, 1788 segmentIndex, fID); 1789 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 1790 for (int vIndex = 1; vIndex <= fVerb; ++vIndex) { 1791 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 1792 } 1793 const Span* span = &fTs[i]; 1794 SkDebugf(") fT=%d (%1.9g) (%1.9g,%1.9g)", i, fTs[i].fT, 1795 xAtT(span), yAtT(i)); 1796 const Segment* other = fTs[i].fOther; 1797 SkDebugf(" other=%d otherT=%1.9g otherIndex=%d", other->fID, 1798 fTs[i].fOtherT, fTs[i].fOtherIndex); 1799 SkDebugf(" windSum=%d windValue=%d\n", fTs[i].fWindSum, 1800 fTs[i].fWindValue); 1801 } 1802 } 1803#endif 1804 1805private: 1806 const SkPoint* fPts; 1807 SkPath::Verb fVerb; 1808 Bounds fBounds; 1809 SkTDArray<Span> fTs; // two or more (always includes t=0 t=1) 1810 // OPTIMIZATION:if intersections array is a pointer, the it could only 1811 // be allocated as needed instead of always initialized -- though maybe 1812 // the initialization is lightweight enough that it hardly matters 1813 mutable SkTDArray<SkPoint> fIntersections; 1814 int fDoneSpans; // used for quick check that segment is finished 1815#if DEBUG_DUMP 1816 int fID; 1817#endif 1818}; 1819 1820class Contour; 1821 1822struct Coincidence { 1823 Contour* fContours[2]; 1824 int fSegments[2]; 1825 double fTs[2][2]; 1826}; 1827 1828class Contour { 1829public: 1830 Contour() { 1831 reset(); 1832#if DEBUG_DUMP 1833 fID = ++gContourID; 1834#endif 1835 } 1836 1837 bool operator<(const Contour& rh) const { 1838 return fBounds.fTop == rh.fBounds.fTop 1839 ? fBounds.fLeft < rh.fBounds.fLeft 1840 : fBounds.fTop < rh.fBounds.fTop; 1841 } 1842 1843 void addCoincident(int index, Contour* other, int otherIndex, 1844 const Intersections& ts, bool swap) { 1845 Coincidence& coincidence = *fCoincidences.append(); 1846 coincidence.fContours[0] = this; 1847 coincidence.fContours[1] = other; 1848 coincidence.fSegments[0] = index; 1849 coincidence.fSegments[1] = otherIndex; 1850 coincidence.fTs[swap][0] = ts.fT[0][0]; 1851 coincidence.fTs[swap][1] = ts.fT[0][1]; 1852 coincidence.fTs[!swap][0] = ts.fT[1][0]; 1853 coincidence.fTs[!swap][1] = ts.fT[1][1]; 1854 } 1855 1856 void addCross(const Contour* crosser) { 1857#ifdef DEBUG_CROSS 1858 for (int index = 0; index < fCrosses.count(); ++index) { 1859 SkASSERT(fCrosses[index] != crosser); 1860 } 1861#endif 1862 *fCrosses.append() = crosser; 1863 } 1864 1865 void addCubic(const SkPoint pts[4]) { 1866 fSegments.push_back().addCubic(pts); 1867 fContainsCurves = true; 1868 } 1869 1870 int addLine(const SkPoint pts[2]) { 1871 fSegments.push_back().addLine(pts); 1872 return fSegments.count(); 1873 } 1874 1875 void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) { 1876 fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex); 1877 } 1878 1879 int addQuad(const SkPoint pts[3]) { 1880 fSegments.push_back().addQuad(pts); 1881 fContainsCurves = true; 1882 return fSegments.count(); 1883 } 1884 1885 int addT(int segIndex, double newT, Contour* other, int otherIndex) { 1886 containsIntercepts(); 1887 return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]); 1888 } 1889 1890 const Bounds& bounds() const { 1891 return fBounds; 1892 } 1893 1894 void complete() { 1895 setBounds(); 1896 fContainsIntercepts = false; 1897 } 1898 1899 void containsIntercepts() { 1900 fContainsIntercepts = true; 1901 } 1902 1903 const Segment* crossedSegment(const SkPoint& basePt, SkScalar& bestY, 1904 int &tIndex, double& hitT) { 1905 int segmentCount = fSegments.count(); 1906 const Segment* bestSegment = NULL; 1907 for (int test = 0; test < segmentCount; ++test) { 1908 Segment* testSegment = &fSegments[test]; 1909 const SkRect& bounds = testSegment->bounds(); 1910 if (bounds.fTop < bestY) { 1911 continue; 1912 } 1913 if (bounds.fTop > basePt.fY) { 1914 continue; 1915 } 1916 if (bounds.fLeft > basePt.fX) { 1917 continue; 1918 } 1919 if (bounds.fRight < basePt.fX) { 1920 continue; 1921 } 1922 double testHitT; 1923 int testT = testSegment->crossedSpan(basePt, bestY, testHitT); 1924 if (testT >= 0) { 1925 bestSegment = testSegment; 1926 tIndex = testT; 1927 hitT = testHitT; 1928 } 1929 } 1930 return bestSegment; 1931 } 1932 1933 bool crosses(const Contour* crosser) const { 1934 if (this == crosser) { 1935 return true; 1936 } 1937 for (int index = 0; index < fCrosses.count(); ++index) { 1938 if (fCrosses[index] == crosser) { 1939 return true; 1940 } 1941 } 1942 return false; 1943 } 1944 1945 void findTooCloseToCall(int winding) { 1946 int segmentCount = fSegments.count(); 1947 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 1948 fSegments[sIndex].findTooCloseToCall(winding); 1949 } 1950 } 1951 1952 void fixOtherTIndex() { 1953 int segmentCount = fSegments.count(); 1954 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 1955 fSegments[sIndex].fixOtherTIndex(); 1956 } 1957 } 1958 1959 void reset() { 1960 fSegments.reset(); 1961 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 1962 fContainsCurves = fContainsIntercepts = false; 1963 fWindingSum = SK_MinS32; 1964 } 1965 1966 void resolveCoincidence(int winding) { 1967 int count = fCoincidences.count(); 1968 for (int index = 0; index < count; ++index) { 1969 Coincidence& coincidence = fCoincidences[index]; 1970 Contour* thisContour = coincidence.fContours[0]; 1971 Contour* otherContour = coincidence.fContours[1]; 1972 int thisIndex = coincidence.fSegments[0]; 1973 int otherIndex = coincidence.fSegments[1]; 1974 Segment& thisOne = thisContour->fSegments[thisIndex]; 1975 Segment& other = otherContour->fSegments[otherIndex]; 1976 double startT = coincidence.fTs[0][0]; 1977 double endT = coincidence.fTs[0][1]; 1978 if (startT > endT) { 1979 SkTSwap<double>(startT, endT); 1980 } 1981 SkASSERT(endT - startT >= FLT_EPSILON); 1982 double oStartT = coincidence.fTs[1][0]; 1983 double oEndT = coincidence.fTs[1][1]; 1984 if (oStartT > oEndT) { 1985 SkTSwap<double>(oStartT, oEndT); 1986 } 1987 SkASSERT(oEndT - oStartT >= FLT_EPSILON); 1988 if (winding > 0 || thisOne.cancels(other)) { 1989 // make sure startT and endT have t entries 1990 if (thisOne.isMissing(startT) || other.isMissing(oEndT)) { 1991 thisOne.addTPair(startT, other, oEndT); 1992 } 1993 if (thisOne.isMissing(endT) || other.isMissing(oStartT)) { 1994 other.addTPair(oStartT, thisOne, endT); 1995 } 1996 thisOne.addTCancel(startT, endT, other, oStartT, oEndT); 1997 } else { 1998 if (thisOne.isMissing(startT) || other.isMissing(oStartT)) { 1999 thisOne.addTPair(startT, other, oStartT); 2000 } 2001 if (thisOne.isMissing(endT) || other.isMissing(oEndT)) { 2002 other.addTPair(oEndT, thisOne, endT); 2003 } 2004 thisOne.addTCoincident(startT, endT, other, oStartT, oEndT); 2005 } 2006 } 2007 } 2008 2009 const SkTArray<Segment>& segments() { 2010 return fSegments; 2011 } 2012 2013 void setWinding(int winding) { 2014 SkASSERT(fWindingSum < 0); 2015 fWindingSum = winding; 2016 } 2017 2018 // OPTIMIZATION: feel pretty uneasy about this. It seems like once again 2019 // we need to sort and walk edges in y, but that on the surface opens the 2020 // same can of worms as before. But then, this is a rough sort based on 2021 // segments' top, and not a true sort, so it could be ameniable to regular 2022 // sorting instead of linear searching. Still feel like I'm missing something 2023 Segment* topSegment(SkScalar& bestY) { 2024 int segmentCount = fSegments.count(); 2025 SkASSERT(segmentCount > 0); 2026 int best = -1; 2027 Segment* bestSegment = NULL; 2028 while (++best < segmentCount) { 2029 Segment* testSegment = &fSegments[best]; 2030 if (testSegment->done()) { 2031 continue; 2032 } 2033 bestSegment = testSegment; 2034 break; 2035 } 2036 if (!bestSegment) { 2037 return NULL; 2038 } 2039 SkScalar bestTop = bestSegment->activeTop(); 2040 for (int test = best + 1; test < segmentCount; ++test) { 2041 Segment* testSegment = &fSegments[test]; 2042 if (testSegment->done()) { 2043 continue; 2044 } 2045 if (testSegment->bounds().fTop > bestTop) { 2046 continue; 2047 } 2048 SkScalar testTop = testSegment->activeTop(); 2049 if (bestTop > testTop) { 2050 bestTop = testTop; 2051 bestSegment = testSegment; 2052 } 2053 } 2054 bestY = bestTop; 2055 return bestSegment; 2056 } 2057 2058 int updateSegment(int index, const SkPoint* pts) { 2059 Segment& segment = fSegments[index]; 2060 segment.updatePts(pts); 2061 return segment.verb() + 1; 2062 } 2063 2064 int windSum() { 2065 if (fWindingSum >= 0) { 2066 return fWindingSum; 2067 } 2068 // check peers 2069 int count = fCrosses.count(); 2070 for (int index = 0; index < count; ++index) { 2071 const Contour* crosser = fCrosses[index]; 2072 if (0 <= crosser->fWindingSum) { 2073 fWindingSum = crosser->fWindingSum; 2074 break; 2075 } 2076 } 2077 return fWindingSum; 2078 } 2079 2080#if DEBUG_TEST 2081 SkTArray<Segment>& debugSegments() { 2082 return fSegments; 2083 } 2084#endif 2085 2086#if DEBUG_DUMP 2087 void dump() { 2088 int i; 2089 const char className[] = "Contour"; 2090 const int tab = 4; 2091 SkDebugf("%s %p (contour=%d)\n", className, this, fID); 2092 for (i = 0; i < fSegments.count(); ++i) { 2093 SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className), 2094 className, i); 2095 fSegments[i].dump(); 2096 } 2097 SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n", 2098 tab + sizeof(className), className, 2099 fBounds.fLeft, fBounds.fTop, 2100 fBounds.fRight, fBounds.fBottom); 2101 SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), 2102 className, fContainsIntercepts); 2103 SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className), 2104 className, fContainsCurves); 2105 } 2106#endif 2107 2108#if DEBUG_ACTIVE_SPANS 2109 void debugShowActiveSpans() { 2110 for (int index = 0; index < fSegments.count(); ++index) { 2111 fSegments[index].debugShowActiveSpans(fID, index); 2112 } 2113 } 2114#endif 2115 2116protected: 2117 void setBounds() { 2118 int count = fSegments.count(); 2119 if (count == 0) { 2120 SkDebugf("%s empty contour\n", __FUNCTION__); 2121 SkASSERT(0); 2122 // FIXME: delete empty contour? 2123 return; 2124 } 2125 fBounds = fSegments.front().bounds(); 2126 for (int index = 1; index < count; ++index) { 2127 fBounds.add(fSegments[index].bounds()); 2128 } 2129 } 2130 2131private: 2132 SkTArray<Segment> fSegments; 2133 SkTDArray<Coincidence> fCoincidences; 2134 SkTDArray<const Contour*> fCrosses; 2135 Bounds fBounds; 2136 bool fContainsIntercepts; 2137 bool fContainsCurves; 2138 int fWindingSum; // initial winding number outside 2139#if DEBUG_DUMP 2140 int fID; 2141#endif 2142}; 2143 2144class EdgeBuilder { 2145public: 2146 2147EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours) 2148 : fPath(path) 2149 , fCurrentContour(NULL) 2150 , fContours(contours) 2151{ 2152#if DEBUG_DUMP 2153 gContourID = 0; 2154 gSegmentID = 0; 2155#endif 2156 walk(); 2157} 2158 2159protected: 2160 2161void complete() { 2162 if (fCurrentContour && fCurrentContour->segments().count()) { 2163 fCurrentContour->complete(); 2164 fCurrentContour = NULL; 2165 } 2166} 2167 2168void walk() { 2169 // FIXME:remove once we can access path pts directly 2170 SkPath::RawIter iter(fPath); // FIXME: access path directly when allowed 2171 SkPoint pts[4]; 2172 SkPath::Verb verb; 2173 do { 2174 verb = iter.next(pts); 2175 *fPathVerbs.append() = verb; 2176 if (verb == SkPath::kMove_Verb) { 2177 *fPathPts.append() = pts[0]; 2178 } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) { 2179 fPathPts.append(verb, &pts[1]); 2180 } 2181 } while (verb != SkPath::kDone_Verb); 2182 // FIXME: end of section to remove once path pts are accessed directly 2183 2184 SkPath::Verb reducedVerb; 2185 uint8_t* verbPtr = fPathVerbs.begin(); 2186 const SkPoint* pointsPtr = fPathPts.begin(); 2187 const SkPoint* finalCurveStart = NULL; 2188 const SkPoint* finalCurveEnd = NULL; 2189 while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) { 2190 switch (verb) { 2191 case SkPath::kMove_Verb: 2192 complete(); 2193 if (!fCurrentContour) { 2194 fCurrentContour = fContours.push_back_n(1); 2195 finalCurveEnd = pointsPtr++; 2196 *fExtra.append() = -1; // start new contour 2197 } 2198 continue; 2199 case SkPath::kLine_Verb: 2200 // skip degenerate points 2201 if (pointsPtr[-1].fX != pointsPtr[0].fX 2202 || pointsPtr[-1].fY != pointsPtr[0].fY) { 2203 fCurrentContour->addLine(&pointsPtr[-1]); 2204 } 2205 break; 2206 case SkPath::kQuad_Verb: 2207 2208 reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts); 2209 if (reducedVerb == 0) { 2210 break; // skip degenerate points 2211 } 2212 if (reducedVerb == 1) { 2213 *fExtra.append() = 2214 fCurrentContour->addLine(fReducePts.end() - 2); 2215 break; 2216 } 2217 fCurrentContour->addQuad(&pointsPtr[-1]); 2218 break; 2219 case SkPath::kCubic_Verb: 2220 reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts); 2221 if (reducedVerb == 0) { 2222 break; // skip degenerate points 2223 } 2224 if (reducedVerb == 1) { 2225 *fExtra.append() = 2226 fCurrentContour->addLine(fReducePts.end() - 2); 2227 break; 2228 } 2229 if (reducedVerb == 2) { 2230 *fExtra.append() = 2231 fCurrentContour->addQuad(fReducePts.end() - 3); 2232 break; 2233 } 2234 fCurrentContour->addCubic(&pointsPtr[-1]); 2235 break; 2236 case SkPath::kClose_Verb: 2237 SkASSERT(fCurrentContour); 2238 if (finalCurveStart && finalCurveEnd 2239 && *finalCurveStart != *finalCurveEnd) { 2240 *fReducePts.append() = *finalCurveStart; 2241 *fReducePts.append() = *finalCurveEnd; 2242 *fExtra.append() = 2243 fCurrentContour->addLine(fReducePts.end() - 2); 2244 } 2245 complete(); 2246 continue; 2247 default: 2248 SkDEBUGFAIL("bad verb"); 2249 return; 2250 } 2251 finalCurveStart = &pointsPtr[verb - 1]; 2252 pointsPtr += verb; 2253 SkASSERT(fCurrentContour); 2254 } 2255 complete(); 2256 if (fCurrentContour && !fCurrentContour->segments().count()) { 2257 fContours.pop_back(); 2258 } 2259 // correct pointers in contours since fReducePts may have moved as it grew 2260 int cIndex = 0; 2261 int extraCount = fExtra.count(); 2262 SkASSERT(extraCount == 0 || fExtra[0] == -1); 2263 int eIndex = 0; 2264 int rIndex = 0; 2265 while (++eIndex < extraCount) { 2266 int offset = fExtra[eIndex]; 2267 if (offset < 0) { 2268 ++cIndex; 2269 continue; 2270 } 2271 fCurrentContour = &fContours[cIndex]; 2272 rIndex += fCurrentContour->updateSegment(offset - 1, 2273 &fReducePts[rIndex]); 2274 } 2275 fExtra.reset(); // we're done with this 2276} 2277 2278private: 2279 const SkPath& fPath; 2280 SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead 2281 SkTDArray<uint8_t> fPathVerbs; // FIXME: remove 2282 Contour* fCurrentContour; 2283 SkTArray<Contour>& fContours; 2284 SkTDArray<SkPoint> fReducePts; // segments created on the fly 2285 SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour 2286}; 2287 2288class Work { 2289public: 2290 enum SegmentType { 2291 kHorizontalLine_Segment = -1, 2292 kVerticalLine_Segment = 0, 2293 kLine_Segment = SkPath::kLine_Verb, 2294 kQuad_Segment = SkPath::kQuad_Verb, 2295 kCubic_Segment = SkPath::kCubic_Verb, 2296 }; 2297 2298 void addCoincident(Work& other, const Intersections& ts, bool swap) { 2299 fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap); 2300 } 2301 2302 // FIXME: does it make sense to write otherIndex now if we're going to 2303 // fix it up later? 2304 void addOtherT(int index, double otherT, int otherIndex) { 2305 fContour->addOtherT(fIndex, index, otherT, otherIndex); 2306 } 2307 2308 // Avoid collapsing t values that are close to the same since 2309 // we walk ts to describe consecutive intersections. Since a pair of ts can 2310 // be nearly equal, any problems caused by this should be taken care 2311 // of later. 2312 // On the edge or out of range values are negative; add 2 to get end 2313 int addT(double newT, const Work& other) { 2314 return fContour->addT(fIndex, newT, other.fContour, other.fIndex); 2315 } 2316 2317 bool advance() { 2318 return ++fIndex < fLast; 2319 } 2320 2321 SkScalar bottom() const { 2322 return bounds().fBottom; 2323 } 2324 2325 const Bounds& bounds() const { 2326 return fContour->segments()[fIndex].bounds(); 2327 } 2328 2329 const SkPoint* cubic() const { 2330 return fCubic; 2331 } 2332 2333 void init(Contour* contour) { 2334 fContour = contour; 2335 fIndex = 0; 2336 fLast = contour->segments().count(); 2337 } 2338 2339 bool isAdjacent(const Work& next) { 2340 return fContour == next.fContour && fIndex + 1 == next.fIndex; 2341 } 2342 2343 bool isFirstLast(const Work& next) { 2344 return fContour == next.fContour && fIndex == 0 2345 && next.fIndex == fLast - 1; 2346 } 2347 2348 SkScalar left() const { 2349 return bounds().fLeft; 2350 } 2351 2352 void promoteToCubic() { 2353 fCubic[0] = pts()[0]; 2354 fCubic[2] = pts()[1]; 2355 fCubic[3] = pts()[2]; 2356 fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3; 2357 fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3; 2358 fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3; 2359 fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3; 2360 } 2361 2362 const SkPoint* pts() const { 2363 return fContour->segments()[fIndex].pts(); 2364 } 2365 2366 SkScalar right() const { 2367 return bounds().fRight; 2368 } 2369 2370 ptrdiff_t segmentIndex() const { 2371 return fIndex; 2372 } 2373 2374 SegmentType segmentType() const { 2375 const Segment& segment = fContour->segments()[fIndex]; 2376 SegmentType type = (SegmentType) segment.verb(); 2377 if (type != kLine_Segment) { 2378 return type; 2379 } 2380 if (segment.isHorizontal()) { 2381 return kHorizontalLine_Segment; 2382 } 2383 if (segment.isVertical()) { 2384 return kVerticalLine_Segment; 2385 } 2386 return kLine_Segment; 2387 } 2388 2389 bool startAfter(const Work& after) { 2390 fIndex = after.fIndex; 2391 return advance(); 2392 } 2393 2394 SkScalar top() const { 2395 return bounds().fTop; 2396 } 2397 2398 SkPath::Verb verb() const { 2399 return fContour->segments()[fIndex].verb(); 2400 } 2401 2402 SkScalar x() const { 2403 return bounds().fLeft; 2404 } 2405 2406 bool xFlipped() const { 2407 return x() != pts()[0].fX; 2408 } 2409 2410 SkScalar y() const { 2411 return bounds().fTop; 2412 } 2413 2414 bool yFlipped() const { 2415 return y() != pts()[0].fY; 2416 } 2417 2418protected: 2419 Contour* fContour; 2420 SkPoint fCubic[4]; 2421 int fIndex; 2422 int fLast; 2423}; 2424 2425#if DEBUG_ADD_INTERSECTING_TS 2426static void debugShowLineIntersection(int pts, const Work& wt, 2427 const Work& wn, const double wtTs[2], const double wnTs[2]) { 2428 if (!pts) { 2429 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n", 2430 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, 2431 wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY, 2432 wn.pts()[1].fX, wn.pts()[1].fY); 2433 return; 2434 } 2435 SkPoint wtOutPt, wnOutPt; 2436 LineXYAtT(wt.pts(), wtTs[0], &wtOutPt); 2437 LineXYAtT(wn.pts(), wnTs[0], &wnOutPt); 2438 SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)", 2439 __FUNCTION__, 2440 wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, 2441 wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY); 2442 if (pts == 2) { 2443 SkDebugf(" wtTs[1]=%g", wtTs[1]); 2444 } 2445 SkDebugf(" wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)", 2446 wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, 2447 wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY); 2448 if (pts == 2) { 2449 SkDebugf(" wnTs[1]=%g", wnTs[1]); 2450 } 2451 SkDebugf("\n"); 2452} 2453#else 2454static void debugShowLineIntersection(int , const Work& , 2455 const Work& , const double [2], const double [2]) { 2456} 2457#endif 2458 2459static bool addIntersectTs(Contour* test, Contour* next) { 2460 2461 if (test != next) { 2462 if (test->bounds().fBottom < next->bounds().fTop) { 2463 return false; 2464 } 2465 if (!Bounds::Intersects(test->bounds(), next->bounds())) { 2466 return true; 2467 } 2468 } 2469 Work wt; 2470 wt.init(test); 2471 bool foundCommonContour = test == next; 2472 do { 2473 Work wn; 2474 wn.init(next); 2475 if (test == next && !wn.startAfter(wt)) { 2476 continue; 2477 } 2478 do { 2479 if (!Bounds::Intersects(wt.bounds(), wn.bounds())) { 2480 continue; 2481 } 2482 int pts; 2483 Intersections ts; 2484 bool swap = false; 2485 switch (wt.segmentType()) { 2486 case Work::kHorizontalLine_Segment: 2487 swap = true; 2488 switch (wn.segmentType()) { 2489 case Work::kHorizontalLine_Segment: 2490 case Work::kVerticalLine_Segment: 2491 case Work::kLine_Segment: { 2492 pts = HLineIntersect(wn.pts(), wt.left(), 2493 wt.right(), wt.y(), wt.xFlipped(), ts); 2494 debugShowLineIntersection(pts, wt, wn, 2495 ts.fT[1], ts.fT[0]); 2496 break; 2497 } 2498 case Work::kQuad_Segment: { 2499 pts = HQuadIntersect(wn.pts(), wt.left(), 2500 wt.right(), wt.y(), wt.xFlipped(), ts); 2501 break; 2502 } 2503 case Work::kCubic_Segment: { 2504 pts = HCubicIntersect(wn.pts(), wt.left(), 2505 wt.right(), wt.y(), wt.xFlipped(), ts); 2506 break; 2507 } 2508 default: 2509 SkASSERT(0); 2510 } 2511 break; 2512 case Work::kVerticalLine_Segment: 2513 swap = true; 2514 switch (wn.segmentType()) { 2515 case Work::kHorizontalLine_Segment: 2516 case Work::kVerticalLine_Segment: 2517 case Work::kLine_Segment: { 2518 pts = VLineIntersect(wn.pts(), wt.top(), 2519 wt.bottom(), wt.x(), wt.yFlipped(), ts); 2520 debugShowLineIntersection(pts, wt, wn, 2521 ts.fT[1], ts.fT[0]); 2522 break; 2523 } 2524 case Work::kQuad_Segment: { 2525 pts = VQuadIntersect(wn.pts(), wt.top(), 2526 wt.bottom(), wt.x(), wt.yFlipped(), ts); 2527 break; 2528 } 2529 case Work::kCubic_Segment: { 2530 pts = VCubicIntersect(wn.pts(), wt.top(), 2531 wt.bottom(), wt.x(), wt.yFlipped(), ts); 2532 break; 2533 } 2534 default: 2535 SkASSERT(0); 2536 } 2537 break; 2538 case Work::kLine_Segment: 2539 switch (wn.segmentType()) { 2540 case Work::kHorizontalLine_Segment: 2541 pts = HLineIntersect(wt.pts(), wn.left(), 2542 wn.right(), wn.y(), wn.xFlipped(), ts); 2543 debugShowLineIntersection(pts, wt, wn, 2544 ts.fT[1], ts.fT[0]); 2545 break; 2546 case Work::kVerticalLine_Segment: 2547 pts = VLineIntersect(wt.pts(), wn.top(), 2548 wn.bottom(), wn.x(), wn.yFlipped(), ts); 2549 debugShowLineIntersection(pts, wt, wn, 2550 ts.fT[1], ts.fT[0]); 2551 break; 2552 case Work::kLine_Segment: { 2553 pts = LineIntersect(wt.pts(), wn.pts(), ts); 2554 debugShowLineIntersection(pts, wt, wn, 2555 ts.fT[1], ts.fT[0]); 2556 break; 2557 } 2558 case Work::kQuad_Segment: { 2559 swap = true; 2560 pts = QuadLineIntersect(wn.pts(), wt.pts(), ts); 2561 break; 2562 } 2563 case Work::kCubic_Segment: { 2564 swap = true; 2565 pts = CubicLineIntersect(wn.pts(), wt.pts(), ts); 2566 break; 2567 } 2568 default: 2569 SkASSERT(0); 2570 } 2571 break; 2572 case Work::kQuad_Segment: 2573 switch (wn.segmentType()) { 2574 case Work::kHorizontalLine_Segment: 2575 pts = HQuadIntersect(wt.pts(), wn.left(), 2576 wn.right(), wn.y(), wn.xFlipped(), ts); 2577 break; 2578 case Work::kVerticalLine_Segment: 2579 pts = VQuadIntersect(wt.pts(), wn.top(), 2580 wn.bottom(), wn.x(), wn.yFlipped(), ts); 2581 break; 2582 case Work::kLine_Segment: { 2583 pts = QuadLineIntersect(wt.pts(), wn.pts(), ts); 2584 break; 2585 } 2586 case Work::kQuad_Segment: { 2587 pts = QuadIntersect(wt.pts(), wn.pts(), ts); 2588 break; 2589 } 2590 case Work::kCubic_Segment: { 2591 wt.promoteToCubic(); 2592 pts = CubicIntersect(wt.cubic(), wn.pts(), ts); 2593 break; 2594 } 2595 default: 2596 SkASSERT(0); 2597 } 2598 break; 2599 case Work::kCubic_Segment: 2600 switch (wn.segmentType()) { 2601 case Work::kHorizontalLine_Segment: 2602 pts = HCubicIntersect(wt.pts(), wn.left(), 2603 wn.right(), wn.y(), wn.xFlipped(), ts); 2604 break; 2605 case Work::kVerticalLine_Segment: 2606 pts = VCubicIntersect(wt.pts(), wn.top(), 2607 wn.bottom(), wn.x(), wn.yFlipped(), ts); 2608 break; 2609 case Work::kLine_Segment: { 2610 pts = CubicLineIntersect(wt.pts(), wn.pts(), ts); 2611 break; 2612 } 2613 case Work::kQuad_Segment: { 2614 wn.promoteToCubic(); 2615 pts = CubicIntersect(wt.pts(), wn.cubic(), ts); 2616 break; 2617 } 2618 case Work::kCubic_Segment: { 2619 pts = CubicIntersect(wt.pts(), wn.pts(), ts); 2620 break; 2621 } 2622 default: 2623 SkASSERT(0); 2624 } 2625 break; 2626 default: 2627 SkASSERT(0); 2628 } 2629 if (!foundCommonContour && pts > 0) { 2630 test->addCross(next); 2631 next->addCross(test); 2632 foundCommonContour = true; 2633 } 2634 // in addition to recording T values, record matching segment 2635 if (pts == 2 && wn.segmentType() <= Work::kLine_Segment 2636 && wt.segmentType() <= Work::kLine_Segment) { 2637 wt.addCoincident(wn, ts, swap); 2638 continue; 2639 } 2640 for (int pt = 0; pt < pts; ++pt) { 2641 SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1); 2642 SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1); 2643 int testTAt = wt.addT(ts.fT[swap][pt], wn); 2644 int nextTAt = wn.addT(ts.fT[!swap][pt], wt); 2645 wt.addOtherT(testTAt, ts.fT[!swap][pt], nextTAt); 2646 wn.addOtherT(nextTAt, ts.fT[swap][pt], testTAt); 2647 } 2648 } while (wn.advance()); 2649 } while (wt.advance()); 2650 return true; 2651} 2652 2653// resolve any coincident pairs found while intersecting, and 2654// see if coincidence is formed by clipping non-concident segments 2655static void coincidenceCheck(SkTDArray<Contour*>& contourList, int winding) { 2656 int contourCount = contourList.count(); 2657 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 2658 Contour* contour = contourList[cIndex]; 2659 contour->findTooCloseToCall(winding); 2660 } 2661 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 2662 Contour* contour = contourList[cIndex]; 2663 contour->resolveCoincidence(winding); 2664 } 2665} 2666 2667// project a ray from the top of the contour up and see if it hits anything 2668// note: when we compute line intersections, we keep track of whether 2669// two contours touch, so we need only look at contours not touching this one. 2670// OPTIMIZATION: sort contourList vertically to avoid linear walk 2671static int innerContourCheck(SkTDArray<Contour*>& contourList, 2672 Contour* baseContour, const SkPoint& basePt) { 2673 int contourCount = contourList.count(); 2674 int winding = 0; 2675 SkScalar bestY = SK_ScalarMin; 2676 for (int cTest = 0; cTest < contourCount; ++cTest) { 2677 Contour* contour = contourList[cTest]; 2678 if (basePt.fY < contour->bounds().fTop) { 2679 continue; 2680 } 2681 if (bestY > contour->bounds().fBottom) { 2682 continue; 2683 } 2684 if (baseContour->crosses(contour)) { 2685 continue; 2686 } 2687 int tIndex; 2688 double tHit; 2689 const Segment* test = contour->crossedSegment(basePt, bestY, tIndex, 2690 tHit); 2691 if (!test) { 2692 continue; 2693 } 2694 // If the ray hit the end of a span, we need to construct the wheel of 2695 // angles to find the span closest to the ray -- even if there are just 2696 // two spokes on the wheel. 2697 if (tHit == test->t(tIndex)) { 2698 SkTDArray<Angle> angles; 2699 int end = test->nextSpan(tIndex, 1); 2700 if (end < 0) { 2701 end = test->nextSpan(tIndex, -1); 2702 } 2703 test->addTwoAngles(tIndex, end, angles); 2704 // test->buildAnglesInner(tIndex, angles); 2705 test->buildAngles(tIndex, angles); 2706 SkTDArray<Angle*> sorted; 2707 sortAngles(angles, sorted); 2708 const Angle* angle = sorted[0]; 2709 test = angle->segment(); 2710 SkScalar testDx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit); 2711 if (testDx == 0) { 2712 angle = *(sorted.end() - 1); 2713 test = angle->segment(); 2714 SkASSERT((*SegmentDXAtT[test->verb()])(test->pts(), tHit) != 0); 2715 } 2716 tIndex = angle->start(); // lesser Y 2717 winding = test->windSum(SkMin32(tIndex, angle->end())); 2718 #if DEBUG_WINDING 2719 SkDebugf("%s 1 winding=%d\n", __FUNCTION__, winding); 2720 #endif 2721 } else { 2722 winding = test->windSum(tIndex); 2723 #if DEBUG_WINDING 2724 SkDebugf("%s 2 winding=%d\n", __FUNCTION__, winding); 2725 #endif 2726 } 2727 // see if a + change in T results in a +/- change in X (compute x'(T)) 2728 SkScalar dx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit); 2729 #if DEBUG_WINDING 2730 SkDebugf("%s dx=%1.9g\n", __FUNCTION__, dx); 2731 #endif 2732 SkASSERT(dx != 0); 2733 if (winding * dx > 0) { // if same signs, result is negative 2734 winding += dx > 0 ? -1 : 1; 2735 #if DEBUG_WINDING 2736 SkDebugf("%s 3 winding=%d\n", __FUNCTION__, winding); 2737 #endif 2738 } 2739 } 2740 baseContour->setWinding(winding); 2741 return winding; 2742} 2743 2744// OPTIMIZATION: not crazy about linear search here to find top active y. 2745// seems like we should break down and do the sort, or maybe sort each 2746// contours' segments? 2747// Once the segment array is built, there's no reason I can think of not to 2748// sort it in Y. hmmm 2749// FIXME: return the contour found to pass to inner contour check 2750static Segment* findTopContour(SkTDArray<Contour*>& contourList, 2751 Contour*& topContour) { 2752 int contourCount = contourList.count(); 2753 int cIndex = 0; 2754 Segment* topStart; 2755 SkScalar bestY = SK_ScalarMax; 2756 Contour* contour; 2757 do { 2758 contour = contourList[cIndex]; 2759 topStart = contour->topSegment(bestY); 2760 } while (!topStart && ++cIndex < contourCount); 2761 if (!topStart) { 2762 return NULL; 2763 } 2764 topContour = contour; 2765 while (++cIndex < contourCount) { 2766 contour = contourList[cIndex]; 2767 if (bestY < contour->bounds().fTop) { 2768 continue; 2769 } 2770 SkScalar testY = SK_ScalarMax; 2771 Segment* test = contour->topSegment(testY); 2772 if (!test || bestY <= testY) { 2773 continue; 2774 } 2775 topContour = contour; 2776 topStart = test; 2777 bestY = testY; 2778 } 2779 return topStart; 2780} 2781 2782static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex) { 2783 while (chase.count()) { 2784 Span* span; 2785 chase.pop(&span); 2786 const Span& backPtr = span->fOther->span(span->fOtherIndex); 2787 Segment* segment = backPtr.fOther; 2788 tIndex = backPtr.fOtherIndex; 2789 if (segment->activeAngles(tIndex)) { 2790 endIndex = segment->nextSpan(tIndex, 1); 2791 if (span->fDone) { 2792 SkTDArray<Angle> angles; 2793 segment->addTwoAngles(endIndex, tIndex, angles); 2794 segment->buildAngles(tIndex, angles); 2795 SkTDArray<Angle*> sorted; 2796 sortAngles(angles, sorted); 2797 // find first angle, initialize winding to computed fWindSum 2798 int winding = span->fWindSum; 2799 int firstIndex = segment->findStartingEdge(sorted, endIndex, tIndex); 2800 int firstSign = sorted[firstIndex]->sign(); 2801 if (firstSign * winding > 0) { 2802 winding -= firstSign; 2803 } 2804 SkDebugf("%s firstSign=%d\n", __FUNCTION__, firstSign); 2805 // we care about first sign and whether wind sum indicates this 2806 // edge is inside or outside. Maybe need to pass span winding 2807 // or first winding or something into this function? 2808 SkASSERT(firstIndex >= 0); 2809 // advance to first undone angle, then return it and winding 2810 // (to set whether edges are active or not) 2811 int nextIndex = firstIndex + 1; 2812 int angleCount = sorted.count(); 2813 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 2814 do { 2815 SkASSERT(nextIndex != firstIndex); 2816 if (nextIndex == angleCount) { 2817 nextIndex = 0; 2818 } 2819 const Angle* angle = sorted[nextIndex]; 2820 segment = angle->segment(); 2821 int windValue = segment->windValue(angle); 2822 SkASSERT(windValue > 0); 2823 int maxWinding = winding; 2824 winding -= angle->sign() * windValue; 2825 if (maxWinding * winding < 0) { 2826 SkDebugf("%s flipped sign %d %d\n", __FUNCTION__, maxWinding, winding); 2827 } 2828 tIndex = angle->start(); 2829 endIndex = angle->end(); 2830 int lesser = SkMin32(tIndex, endIndex); 2831 const Span& nextSpan = segment->span(lesser); 2832 if (!nextSpan.fDone) { 2833 // FIXME: this be wrong. assign startWinding if edge is in 2834 // same direction. If the direction is opposite, winding to 2835 // assign is flipped sign or +/- 1? 2836 if (abs(maxWinding) < abs(winding)) { 2837 maxWinding = winding; 2838 } 2839 segment->markWinding(lesser, maxWinding); 2840 break; 2841 } 2842 } while (++nextIndex != lastIndex); 2843 } else { 2844 SkASSERT(endIndex > tIndex); 2845 } 2846 return segment; 2847 } 2848 } 2849 return NULL; 2850} 2851 2852#if DEBUG_ACTIVE_SPANS 2853static void debugShowActiveSpans(SkTDArray<Contour*>& contourList) { 2854 for (int index = 0; index < contourList.count(); ++ index) { 2855 contourList[index]->debugShowActiveSpans(); 2856 } 2857} 2858#endif 2859 2860// Each segment may have an inside or an outside. Segments contained within 2861// winding may have insides on either side, and form a contour that should be 2862// ignored. Segments that are coincident with opposing direction segments may 2863// have outsides on either side, and should also disappear. 2864// 'Normal' segments will have one inside and one outside. Subsequent connections 2865// when winding should follow the intersection direction. If more than one edge 2866// is an option, choose first edge that continues the inside. 2867 // since we start with leftmost top edge, we'll traverse through a 2868 // smaller angle counterclockwise to get to the next edge. 2869static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) { 2870 bool firstContour = true; 2871 do { 2872 Contour* topContour; 2873 Segment* topStart = findTopContour(contourList, topContour); 2874 if (!topStart) { 2875 break; 2876 } 2877 // Start at the top. Above the top is outside, below is inside. 2878 // follow edges to intersection by changing the index by direction. 2879 int index, endIndex; 2880 Segment* current = topStart->findTop(index, endIndex); 2881 int contourWinding; 2882 if (firstContour) { 2883 contourWinding = 0; 2884 firstContour = false; 2885 } else { 2886 const SkPoint& topPoint = current->xyAtT(endIndex); 2887 contourWinding = innerContourCheck(contourList, topContour, topPoint); 2888#if DEBUG_WINDING 2889 SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding); 2890#endif 2891 } 2892 SkPoint lastPt; 2893 bool firstTime = true; 2894 int winding = contourWinding; 2895 int spanWinding = current->spanSign(index, endIndex); 2896 // int firstWinding = contourWinding + spanWinding; 2897 // FIXME: needs work. While it works in limited situations, it does 2898 // not always compute winding correctly. Active should be removed and instead 2899 // the initial winding should be correctly passed in so that if the 2900 // inner contour is wound the same way, it never finds an accumulated 2901 // winding of zero. Inside 'find next', we need to look for transitions 2902 // other than zero when resolving sorted angles. 2903 SkTDArray<Span*> chaseArray; 2904 do { 2905 bool active = winding * spanWinding <= 0; 2906 const SkPoint* firstPt = NULL; 2907 do { 2908 SkASSERT(!current->done()); 2909 int nextStart, nextEnd, flipped = 1; 2910 Segment* next = current->findNext(chaseArray, 2911 winding + spanWinding, index, 2912 endIndex, nextStart, nextEnd, flipped, firstTime); 2913 if (!next) { 2914 break; 2915 } 2916 if (!firstPt) { 2917 firstPt = ¤t->addMoveTo(index, simple, active); 2918 } 2919 lastPt = current->addCurveTo(index, endIndex, simple, active); 2920 current = next; 2921 index = nextStart; 2922 endIndex = nextEnd; 2923 spanWinding = SkSign32(spanWinding) * flipped * next->windValue( 2924 SkMin32(nextStart, nextEnd)); 2925 #if DEBUG_WINDING 2926 SkDebugf("%s spanWinding=%d\n", __FUNCTION__, spanWinding); 2927 #endif 2928 firstTime = false; 2929 } while (*firstPt != lastPt && (active || !current->done())); 2930 if (firstPt && active) { 2931 #if DEBUG_PATH_CONSTRUCTION 2932 SkDebugf("%s close\n", __FUNCTION__); 2933 #endif 2934 simple.close(); 2935 } 2936 current = findChase(chaseArray, index, endIndex); 2937#if DEBUG_ACTIVE_SPANS 2938 debugShowActiveSpans(contourList); 2939#endif 2940 if (!current) { 2941 break; 2942 } 2943 int lesser = SkMin32(index, endIndex); 2944 spanWinding = current->windSum(lesser); 2945 int spanValue = current->windValue(lesser); 2946 SkASSERT(spanWinding != SK_MinS32); 2947 int spanSign = current->spanSign(index, endIndex); 2948 #if DEBUG_WINDING 2949 SkDebugf("%s spanWinding=%d spanSign=%d winding=%d spanValue=%d\n", 2950 __FUNCTION__, spanWinding, spanSign, winding, spanValue); 2951 #endif 2952 if (spanWinding * spanSign < 0) { 2953 #if DEBUG_WINDING 2954 SkDebugf("%s spanWinding * spanSign < 0\n", __FUNCTION__); 2955 #endif 2956 SkTSwap<int>(index, endIndex); 2957 } 2958 if (abs(spanWinding) > spanValue) { 2959 #if DEBUG_WINDING 2960 SkDebugf("%s abs(spanWinding) > spanValue\n", __FUNCTION__); 2961 #endif 2962 winding = spanWinding; 2963 spanWinding = spanValue * SkSign32(spanWinding); 2964 winding -= spanWinding; 2965 } 2966 } while (true); 2967 } while (true); 2968} 2969 2970static void fixOtherTIndex(SkTDArray<Contour*>& contourList) { 2971 int contourCount = contourList.count(); 2972 for (int cTest = 0; cTest < contourCount; ++cTest) { 2973 Contour* contour = contourList[cTest]; 2974 contour->fixOtherTIndex(); 2975 } 2976} 2977 2978static void makeContourList(SkTArray<Contour>& contours, 2979 SkTDArray<Contour*>& list) { 2980 int count = contours.count(); 2981 if (count == 0) { 2982 return; 2983 } 2984 for (int index = 0; index < count; ++index) { 2985 *list.append() = &contours[index]; 2986 } 2987 QSort<Contour>(list.begin(), list.end() - 1); 2988} 2989 2990void simplifyx(const SkPath& path, SkPath& simple) { 2991 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 2992 int winding = (path.getFillType() & 1) ? 1 : -1; 2993 simple.reset(); 2994 simple.setFillType(SkPath::kEvenOdd_FillType); 2995 2996 // turn path into list of segments 2997 SkTArray<Contour> contours; 2998 // FIXME: add self-intersecting cubics' T values to segment 2999 EdgeBuilder builder(path, contours); 3000 SkTDArray<Contour*> contourList; 3001 makeContourList(contours, contourList); 3002 Contour** currentPtr = contourList.begin(); 3003 if (!currentPtr) { 3004 return; 3005 } 3006 Contour** listEnd = contourList.end(); 3007 // find all intersections between segments 3008 do { 3009 Contour** nextPtr = currentPtr; 3010 Contour* current = *currentPtr++; 3011 Contour* next; 3012 do { 3013 next = *nextPtr++; 3014 } while (addIntersectTs(current, next) && nextPtr != listEnd); 3015 } while (currentPtr != listEnd); 3016 // eat through coincident edges 3017 coincidenceCheck(contourList, winding); 3018 fixOtherTIndex(contourList); 3019 // construct closed contours 3020 bridge(contourList, simple); 3021} 3022 3023