Simplify.cpp revision 7db7c6bba9e9a61ad574a1d60b65bce4563beee5
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copyright 2012 Google Inc. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Use of this source code is governed by a BSD-style license that can be 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * found in the LICENSE file. 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "Simplify.h" 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#undef SkASSERT 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define SkASSERT(cond) while (!(cond)) { sk_throw(); } 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Terminology: 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A Path contains one of more Contours 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A Contour is made up of Segment array 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// A Segment is described by a Verb and a Point array with 2, 3, or 4 points 1690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// A Verb is one of Line, Quad(ratic), or Cubic 1790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// A Segment contains a Span array 1890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// A Span is describes a portion of a Segment using starting and ending T 1990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// T values range from 0 to 1, where 0 is the first Point in the Segment 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// An Edge is a Segment generated from a Span 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// FIXME: remove once debugging is complete 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef SK_DEBUG 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int gDebugMaxWindSum = SK_MaxS32; 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int gDebugMaxWindValue = SK_MaxS32; 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_UNUSED 0 // set to expose unused functions 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if 0 // set to 1 for multiple thread -- no debugging 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const bool gRunTestsInOneThread = false; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_ACTIVE_SPANS 0 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_ADD_INTERSECTING_TS 0 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_ADD_T_PAIR 0 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_CONCIDENT 0 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_CROSS 0 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_DUMP 0 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_MARK_DONE 0 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_PATH_CONSTRUCTION 0 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_SORT 0 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_WIND_BUMP 0 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_WINDING 0 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const bool gRunTestsInOneThread = true; 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_ACTIVE_SPANS 1 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_ADD_INTERSECTING_TS 0 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_ADD_T_PAIR 0 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_CONCIDENT 0 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_CROSS 1 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_DUMP 1 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_MARK_DONE 1 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_PATH_CONSTRUCTION 1 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_SORT 1 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_WIND_BUMP 0 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_WINDING 1 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if (DEBUG_ACTIVE_SPANS || DEBUG_CONCIDENT) && !DEBUG_DUMP 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#undef DEBUG_DUMP 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_DUMP 1 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if DEBUG_DUMP 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const char* kLVerbStr[] = {"", "line", "quad", "cubic"}; 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// static const char* kUVerbStr[] = {"", "Line", "Quad", "Cubic"}; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int gContourID; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int gSegmentID; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef DEBUG_TEST 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DEBUG_TEST 0 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int LineIntersect(const SkPoint a[2], const SkPoint b[2], 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Intersections& intersections) { 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return intersect(aLine, bLine, intersections.fT[0], intersections.fT[1]); 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int QuadLineIntersect(const SkPoint a[3], const SkPoint b[2], 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Intersections& intersections) { 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) intersect(aQuad, bLine, intersections); 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return intersections.fUsed; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int CubicLineIntersect(const SkPoint a[2], const SkPoint b[3], 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Intersections& intersections) { 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[3].fX, a[3].fY}}; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return intersect(aCubic, bLine, intersections.fT[0], intersections.fT[1]); 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int QuadIntersect(const SkPoint a[3], const SkPoint b[3], 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Intersections& intersections) { 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic bQuad = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}}; 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) intersect(aQuad, bQuad, intersections); 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return intersections.fUsed; 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int CubicIntersect(const SkPoint a[4], const SkPoint b[4], 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Intersections& intersections) { 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[3].fX, a[3].fY}}; 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic bCubic = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}, {b[2].fX, b[2].fY}, 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {b[3].fX, b[3].fY}}; 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) intersect(aCubic, bCubic, intersections); 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return intersections.fUsed; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int HLineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkScalar y, bool flipped, Intersections& intersections) { 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return horizontalIntersect(aLine, left, right, y, flipped, intersections); 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int HQuadIntersect(const SkPoint a[3], SkScalar left, SkScalar right, 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkScalar y, bool flipped, Intersections& intersections) { 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return horizontalIntersect(aQuad, left, right, y, flipped, intersections); 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int HCubicIntersect(const SkPoint a[4], SkScalar left, SkScalar right, 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkScalar y, bool flipped, Intersections& intersections) { 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[3].fX, a[3].fY}}; 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return horizontalIntersect(aCubic, left, right, y, flipped, intersections); 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int VLineIntersect(const SkPoint a[2], SkScalar top, SkScalar bottom, 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkScalar x, bool flipped, Intersections& intersections) { 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return verticalIntersect(aLine, top, bottom, x, flipped, intersections); 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int VQuadIntersect(const SkPoint a[3], SkScalar top, SkScalar bottom, 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkScalar x, bool flipped, Intersections& intersections) { 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return verticalIntersect(aQuad, top, bottom, x, flipped, intersections); 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int VCubicIntersect(const SkPoint a[4], SkScalar top, SkScalar bottom, 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkScalar x, bool flipped, Intersections& intersections) { 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[3].fX, a[3].fY}}; 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return verticalIntersect(aCubic, top, bottom, x, flipped, intersections); 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int (* const VSegmentIntersect[])(const SkPoint [], SkScalar , 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkScalar , SkScalar , bool , Intersections& ) = { 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NULL, 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VLineIntersect, 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VQuadIntersect, 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) VCubicIntersect 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line line = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double x, y; 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xy_at_t(line, t, x, y); 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out->fX = SkDoubleToScalar(x); 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out->fY = SkDoubleToScalar(y); 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1752a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static void QuadXYAtT(const SkPoint a[3], double t, SkPoint* out) { 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double x, y; 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xy_at_t(quad, t, x, y); 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out->fX = SkDoubleToScalar(x); 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out->fY = SkDoubleToScalar(y); 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void CubicXYAtT(const SkPoint a[4], double t, SkPoint* out) { 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[3].fX, a[3].fY}}; 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double x, y; 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xy_at_t(cubic, t, x, y); 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out->fX = SkDoubleToScalar(x); 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out->fY = SkDoubleToScalar(y); 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void (* const SegmentXYAtT[])(const SkPoint [], double , SkPoint* ) = { 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NULL, 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LineXYAtT, 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QuadXYAtT, 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CubicXYAtT 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar LineXAtT(const SkPoint a[2], double t) { 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double x; 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xy_at_t(aLine, t, x, *(double*) 0); 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SkDoubleToScalar(x); 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar QuadXAtT(const SkPoint a[3], double t) { 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double x; 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xy_at_t(quad, t, x, *(double*) 0); 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SkDoubleToScalar(x); 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar CubicXAtT(const SkPoint a[4], double t) { 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[3].fX, a[3].fY}}; 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double x; 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xy_at_t(cubic, t, x, *(double*) 0); 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SkDoubleToScalar(x); 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar (* const SegmentXAtT[])(const SkPoint [], double ) = { 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NULL, 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LineXAtT, 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QuadXAtT, 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CubicXAtT 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar LineYAtT(const SkPoint a[2], double t) { 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double y; 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xy_at_t(aLine, t, *(double*) 0, y); 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SkDoubleToScalar(y); 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar QuadYAtT(const SkPoint a[3], double t) { 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double y; 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xy_at_t(quad, t, *(double*) 0, y); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SkDoubleToScalar(y); 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar CubicYAtT(const SkPoint a[4], double t) { 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[3].fX, a[3].fY}}; 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double y; 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xy_at_t(cubic, t, *(double*) 0, y); 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SkDoubleToScalar(y); 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar (* const SegmentYAtT[])(const SkPoint [], double ) = { 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NULL, 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LineYAtT, 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QuadYAtT, 2542a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) CubicYAtT 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar LineDXAtT(const SkPoint a[2], double ) { 2582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) return a[1].fX - a[0].fX; 2592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar QuadDXAtT(const SkPoint a[3], double t) { 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}}; 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double x; 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dxdy_at_t(quad, t, x, *(double*) 0); 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SkDoubleToScalar(x); 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar CubicDXAtT(const SkPoint a[4], double t) { 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, {a[2].fX, a[2].fY}, 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[3].fX, a[3].fY}}; 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double x; 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dxdy_at_t(cubic, t, x, *(double*) 0); 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SkDoubleToScalar(x); 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar (* const SegmentDXAtT[])(const SkPoint [], double ) = { 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NULL, 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LineDXAtT, 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QuadDXAtT, 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CubicDXAtT 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void LineSubDivide(const SkPoint a[2], double startT, double endT, 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkPoint sub[2]) { 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) _Line dst; 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub_divide(aLine, startT, endT, dst); 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[0].fX = SkDoubleToScalar(dst[0].x); 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[0].fY = SkDoubleToScalar(dst[0].y); 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[1].fX = SkDoubleToScalar(dst[1].x); 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[1].fY = SkDoubleToScalar(dst[1].y); 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void QuadSubDivide(const SkPoint a[3], double startT, double endT, 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkPoint sub[3]) { 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[2].fX, a[2].fY}}; 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Quadratic dst; 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub_divide(aQuad, startT, endT, dst); 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[0].fX = SkDoubleToScalar(dst[0].x); 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[0].fY = SkDoubleToScalar(dst[0].y); 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[1].fX = SkDoubleToScalar(dst[1].x); 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[1].fY = SkDoubleToScalar(dst[1].y); 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[2].fX = SkDoubleToScalar(dst[2].x); 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[2].fY = SkDoubleToScalar(dst[2].y); 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void CubicSubDivide(const SkPoint a[4], double startT, double endT, 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkPoint sub[4]) { 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Cubic dst; 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub_divide(aCubic, startT, endT, dst); 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[0].fX = SkDoubleToScalar(dst[0].x); 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[0].fY = SkDoubleToScalar(dst[0].y); 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[1].fX = SkDoubleToScalar(dst[1].x); 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[1].fY = SkDoubleToScalar(dst[1].y); 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[2].fX = SkDoubleToScalar(dst[2].x); 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[2].fY = SkDoubleToScalar(dst[2].y); 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[3].fX = SkDoubleToScalar(dst[3].x); 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub[3].fY = SkDoubleToScalar(dst[3].y); 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void (* const SegmentSubDivide[])(const SkPoint [], double , double , 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkPoint []) = { 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NULL, 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LineSubDivide, 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QuadSubDivide, 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CubicSubDivide 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if DEBUG_UNUSED 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void QuadSubBounds(const SkPoint a[3], double startT, double endT, 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkRect& bounds) { 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkPoint dst[3]; 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QuadSubDivide(a, startT, endT, dst); 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bounds.fLeft = bounds.fRight = dst[0].fX; 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bounds.fTop = bounds.fBottom = dst[0].fY; 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int index = 1; index < 3; ++index) { 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bounds.growToInclude(dst[index].fX, dst[index].fY); 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void CubicSubBounds(const SkPoint a[4], double startT, double endT, 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkRect& bounds) { 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkPoint dst[4]; 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CubicSubDivide(a, startT, endT, dst); 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bounds.fLeft = bounds.fRight = dst[0].fX; 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bounds.fTop = bounds.fBottom = dst[0].fY; 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int index = 1; index < 4; ++index) { 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bounds.growToInclude(dst[index].fX, dst[index].fY); 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkPath::Verb QuadReduceOrder(const SkPoint a[3], 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkTDArray<SkPoint>& reducePts) { 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[2].fX, a[2].fY}}; 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Quadratic dst; 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int order = reduceOrder(aQuad, dst); 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (order == 3) { 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SkPath::kQuad_Verb; 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int index = 0; index < order; ++index) { 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkPoint* pt = reducePts.append(); 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pt->fX = SkDoubleToScalar(dst[index].x); 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pt->fY = SkDoubleToScalar(dst[index].y); 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (SkPath::Verb) (order - 1); 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkPath::Verb CubicReduceOrder(const SkPoint a[4], 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkTDArray<SkPoint>& reducePts) { 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Cubic dst; 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int order = reduceOrder(aCubic, dst, kReduceOrder_QuadraticsAllowed); 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (order == 4) { 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SkPath::kCubic_Verb; 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int index = 0; index < order; ++index) { 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkPoint* pt = reducePts.append(); 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pt->fX = SkDoubleToScalar(dst[index].x); 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pt->fY = SkDoubleToScalar(dst[index].y); 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (SkPath::Verb) (order - 1); 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool QuadIsLinear(const SkPoint a[3]) { 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[2].fX, a[2].fY}}; 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return isLinear(aQuad, 0, 2); 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool CubicIsLinear(const SkPoint a[4]) { 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return isLinear(aCubic, 0, 3); 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar LineLeftMost(const SkPoint a[2], double startT, double endT) { 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double x[2]; 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xy_at_t(aLine, startT, x[0], *(double*) 0); 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) xy_at_t(aLine, endT, x[1], *(double*) 0); 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SkMinScalar((float) x[0], (float) x[1]); 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar QuadLeftMost(const SkPoint a[3], double startT, double endT) { 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Quadratic aQuad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[2].fX, a[2].fY}}; 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (float) leftMostT(aQuad, startT, endT); 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar CubicLeftMost(const SkPoint a[4], double startT, double endT) { 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Cubic aCubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (float) leftMostT(aCubic, startT, endT); 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SkScalar (* const SegmentLeftMost[])(const SkPoint [], double , double) = { 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NULL, 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LineLeftMost, 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QuadLeftMost, 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CubicLeftMost 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if DEBUG_UNUSED 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static bool IsCoincident(const SkPoint a[2], const SkPoint& above, 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SkPoint& below) { 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const _Line bLine = {{above.fX, above.fY}, {below.fX, below.fY}}; 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return implicit_matches_ulps(aLine, bLine, 32); 4352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)} 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class Segment; 4392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 4402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// sorting angles 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// given angles of {dx dy ddx ddy dddx dddy} sort them 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class Angle { 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // FIXME: this is bogus for quads and cubics 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if the quads and cubics' line from end pt to ctrl pt are coincident, 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // there's no obvious way to determine the curve ordering from the 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // derivatives alone. In particular, if one quadratic's coincident tangent 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // is longer than the other curve, the final control point can place the 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // longer curve on either side of the shorter one. 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Using Bezier curve focus http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // may provide some help, but nothing has been figured out yet. 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool operator<(const Angle& rh) const { 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((fDy < 0) ^ (rh.fDy < 0)) { 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fDy < 0; 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (fDy == 0 && rh.fDy == 0 && fDx != rh.fDx) { 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fDx < rh.fDx; 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkScalar cmp = fDx * rh.fDy - rh.fDx * fDy; 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (cmp) { 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return cmp < 0; 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((fDDy < 0) ^ (rh.fDDy < 0)) { 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fDDy < 0; 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (fDDy == 0 && rh.fDDy == 0 && fDDx != rh.fDDx) { 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fDDx < rh.fDDx; 4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) cmp = fDDx * rh.fDDy - rh.fDDx * fDDy; 4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (cmp) { 4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return cmp < 0; 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((fDDDy < 0) ^ (rh.fDDDy < 0)) { 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fDDDy < 0; 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (fDDDy == 0 && rh.fDDDy == 0) { 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fDDDx < rh.fDDDx; 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fDDDx * rh.fDDDy < rh.fDDDx * fDDDy; 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double dx() const { 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fDx; 4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double dy() const { 4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fDy; 4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int end() const { 4915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fEnd; 4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool firstBump(int sumWinding) const { 4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return sign() * sumWinding > 0; 4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool isHorizontal() const { 4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fDy == 0 && fDDy == 0 && fDDDy == 0; 5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // since all angles share a point, this needs to know which point 5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // is the common origin, i.e., whether the center is at pts[0] or pts[verb] 5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // practically, this should only be called by addAngle 5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void set(const SkPoint* pts, SkPath::Verb verb, const Segment* segment, 5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int start, int end) { 5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkASSERT(start != end); 5085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fSegment = segment; 5095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fStart = start; 5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fEnd = end; 5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fDx = pts[1].fX - pts[0].fX; // b - a 5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fDy = pts[1].fY - pts[0].fY; 5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (verb == SkPath::kLine_Verb) { 5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fDDx = fDDy = fDDDx = fDDDy = 0; 5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fDDx = pts[2].fX - pts[1].fX - fDx; // a - 2b + c 5185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fDDy = pts[2].fY - pts[1].fY - fDy; 5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (verb == SkPath::kQuad_Verb) { 5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fDDDx = fDDDy = 0; 5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fDDDx = pts[3].fX + 3 * (pts[1].fX - pts[2].fX) - pts[0].fX; 5245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fDDDy = pts[3].fY + 3 * (pts[1].fY - pts[2].fY) - pts[0].fY; 5255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // noncoincident quads/cubics may have the same initial angle 5285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // as lines, so must sort by derivatives as well 5295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if flatness turns out to be a reasonable way to sort, use the below: 5305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void setFlat(const SkPoint* pts, SkPath::Verb verb, Segment* segment, 5315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int start, int end) { 5325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fSegment = segment; 5335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fStart = start; 5345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fEnd = end; 5355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fDx = pts[1].fX - pts[0].fX; // b - a 5365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fDy = pts[1].fY - pts[0].fY; 5375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (verb == SkPath::kLine_Verb) { 5385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fDDx = fDDy = fDDDx = fDDDy = 0; 5395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 5405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (verb == SkPath::kQuad_Verb) { 5425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int uplsX = FloatAsInt(pts[2].fX - pts[1].fY - fDx); 5432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int uplsY = FloatAsInt(pts[2].fY - pts[1].fY - fDy); 5442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int larger = std::max(abs(uplsX), abs(uplsY)); 5452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) int shift = 0; 5462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) double flatT; 5472a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SkPoint ddPt; // FIXME: get rid of copy (change fDD_ to point) 5482a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LineParameters implicitLine; 5492a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) _Line tangent = {{pts[0].fX, pts[0].fY}, {pts[1].fX, pts[1].fY}}; 5505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) implicitLine.lineEndPoints(tangent); 5515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) implicitLine.normalize(); 5522a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) while (larger > UlpsEpsilon * 1024) { 5535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) larger >>= 2; 5545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++shift; 5555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) flatT = 0.5 / (1 << shift); 5565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) QuadXYAtT(pts, flatT, &ddPt); 557 _Point _pt = {ddPt.fX, ddPt.fY}; 558 double distance = implicitLine.pointDistance(_pt); 559 if (approximately_zero(distance)) { 560 SkDebugf("%s ulps too small %1.9g\n", __FUNCTION__, distance); 561 break; 562 } 563 } 564 flatT = 0.5 / (1 << shift); 565 QuadXYAtT(pts, flatT, &ddPt); 566 fDDx = ddPt.fX - pts[0].fX; 567 fDDy = ddPt.fY - pts[0].fY; 568 SkASSERT(fDDx != 0 || fDDy != 0); 569 fDDDx = fDDDy = 0; 570 return; 571 } 572 SkASSERT(0); // FIXME: add cubic case 573 } 574 575 Segment* segment() const { 576 return const_cast<Segment*>(fSegment); 577 } 578 579 int sign() const { 580 return SkSign32(fStart - fEnd); 581 } 582 583 int start() const { 584 return fStart; 585 } 586 587private: 588 SkScalar fDx; 589 SkScalar fDy; 590 SkScalar fDDx; 591 SkScalar fDDy; 592 SkScalar fDDDx; 593 SkScalar fDDDy; 594 const Segment* fSegment; 595 int fStart; 596 int fEnd; 597}; 598 599static void sortAngles(SkTDArray<Angle>& angles, SkTDArray<Angle*>& angleList) { 600 int angleCount = angles.count(); 601 int angleIndex; 602 angleList.setReserve(angleCount); 603 for (angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 604 *angleList.append() = &angles[angleIndex]; 605 } 606 QSort<Angle>(angleList.begin(), angleList.end() - 1); 607} 608 609// Bounds, unlike Rect, does not consider a line to be empty. 610struct Bounds : public SkRect { 611 static bool Intersects(const Bounds& a, const Bounds& b) { 612 return a.fLeft <= b.fRight && b.fLeft <= a.fRight && 613 a.fTop <= b.fBottom && b.fTop <= a.fBottom; 614 } 615 616 void add(SkScalar left, SkScalar top, SkScalar right, SkScalar bottom) { 617 if (left < fLeft) { 618 fLeft = left; 619 } 620 if (top < fTop) { 621 fTop = top; 622 } 623 if (right > fRight) { 624 fRight = right; 625 } 626 if (bottom > fBottom) { 627 fBottom = bottom; 628 } 629 } 630 631 void add(const Bounds& toAdd) { 632 add(toAdd.fLeft, toAdd.fTop, toAdd.fRight, toAdd.fBottom); 633 } 634 635 bool isEmpty() { 636 return fLeft > fRight || fTop > fBottom 637 || fLeft == fRight && fTop == fBottom 638 || isnan(fLeft) || isnan(fRight) 639 || isnan(fTop) || isnan(fBottom); 640 } 641 642 void setCubicBounds(const SkPoint a[4]) { 643 _Rect dRect; 644 Cubic cubic = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 645 {a[2].fX, a[2].fY}, {a[3].fX, a[3].fY}}; 646 dRect.setBounds(cubic); 647 set((float) dRect.left, (float) dRect.top, (float) dRect.right, 648 (float) dRect.bottom); 649 } 650 651 void setQuadBounds(const SkPoint a[3]) { 652 const Quadratic quad = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}, 653 {a[2].fX, a[2].fY}}; 654 _Rect dRect; 655 dRect.setBounds(quad); 656 set((float) dRect.left, (float) dRect.top, (float) dRect.right, 657 (float) dRect.bottom); 658 } 659}; 660 661struct Span { 662 Segment* fOther; 663 mutable SkPoint fPt; // lazily computed as needed 664 double fT; 665 double fOtherT; // value at fOther[fOtherIndex].fT 666 int fOtherIndex; // can't be used during intersection 667 int fWindSum; // accumulated from contours surrounding this one 668 int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident 669 bool fDone; // if set, this span to next higher T has been processed 670}; 671 672class Segment { 673public: 674 Segment() { 675#if DEBUG_DUMP 676 fID = ++gSegmentID; 677#endif 678 } 679 680 bool activeAngle(int index, int& done, SkTDArray<Angle>& angles) const { 681 if (activeAngleInner(index, done, angles)) { 682 return true; 683 } 684 double referenceT = fTs[index].fT; 685 int lesser = index; 686 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 687 if (activeAngleOther(lesser, done, angles)) { 688 return true; 689 } 690 } 691 do { 692 if (activeAngleOther(index, done, angles)) { 693 return true; 694 } 695 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 696 return false; 697 } 698 699 bool activeAngleOther(int index, int& done, SkTDArray<Angle>& angles) const { 700 Span* span = &fTs[index]; 701 Segment* other = span->fOther; 702 int oIndex = span->fOtherIndex; 703 return other->activeAngleInner(oIndex, done, angles); 704 } 705 706 bool activeAngleInner(int index, int& done, SkTDArray<Angle>& angles) const { 707 int next = nextSpan(index, 1); 708 if (next > 0) { 709 const Span& upSpan = fTs[index]; 710 if (upSpan.fWindValue) { 711 addAngle(angles, index, next); 712 if (upSpan.fDone) { 713 done++; 714 } else if (upSpan.fWindSum != SK_MinS32) { 715 return true; 716 } 717 } 718 } 719 int prev = nextSpan(index, -1); 720 // edge leading into junction 721 if (prev >= 0) { 722 const Span& downSpan = fTs[prev]; 723 if (downSpan.fWindValue) { 724 addAngle(angles, index, prev); 725 if (downSpan.fDone) { 726 done++; 727 } else if (downSpan.fWindSum != SK_MinS32) { 728 return true; 729 } 730 } 731 } 732 return false; 733 } 734 735 SkScalar activeTop() const { 736 SkASSERT(!done()); 737 int count = fTs.count(); 738 SkScalar result = SK_ScalarMax; 739 bool lastDone = true; 740 for (int index = 0; index < count; ++index) { 741 bool done = fTs[index].fDone; 742 if (!done || !lastDone) { 743 SkScalar y = yAtT(index); 744 if (result > y) { 745 result = y; 746 } 747 } 748 lastDone = done; 749 } 750 SkASSERT(result < SK_ScalarMax); 751 return result; 752 } 753 754 void addAngle(SkTDArray<Angle>& angles, int start, int end) const { 755 SkASSERT(start != end); 756 SkPoint edge[4]; 757 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 758 Angle* angle = angles.append(); 759 angle->set(edge, fVerb, this, start, end); 760 } 761 762 void addCancelOutsides(const SkTDArray<double>& outsideTs, Segment& other, 763 double oEnd) { 764 int tIndex = -1; 765 int tCount = fTs.count(); 766 int oIndex = -1; 767 int oCount = other.fTs.count(); 768 double tStart = outsideTs[0]; 769 double oStart = outsideTs[1]; 770 do { 771 ++tIndex; 772 } while (tStart - fTs[tIndex].fT >= FLT_EPSILON && tIndex < tCount); 773 int tIndexStart = tIndex; 774 do { 775 ++oIndex; 776 } while (oStart - other.fTs[oIndex].fT >= FLT_EPSILON && oIndex < oCount); 777 int oIndexStart = oIndex; 778 double nextT; 779 do { 780 nextT = fTs[++tIndex].fT; 781 } while (nextT < 1 && nextT - tStart < FLT_EPSILON); 782 double oNextT; 783 do { 784 oNextT = other.fTs[++oIndex].fT; 785 } while (oNextT < 1 && oNextT - oStart < FLT_EPSILON); 786 // at this point, spans before and after are at: 787 // fTs[tIndexStart - 1], fTs[tIndexStart], fTs[tIndex] 788 // if tIndexStart == 0, no prior span 789 // if nextT == 1, no following span 790 791 // advance the span with zero winding 792 // if the following span exists (not past the end, non-zero winding) 793 // connect the two edges 794 if (!fTs[tIndexStart].fWindValue) { 795 if (tIndexStart > 0 && fTs[tIndexStart - 1].fWindValue) { 796 #if DEBUG_CONCIDENT 797 SkDebugf("%s 1 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 798 __FUNCTION__, fID, other.fID, tIndexStart - 1, 799 fTs[tIndexStart].fT, xyAtT(tIndexStart).fX, 800 xyAtT(tIndexStart).fY); 801 #endif 802 addTPair(fTs[tIndexStart].fT, other, other.fTs[oIndex].fT); 803 } 804 if (nextT < 1 && fTs[tIndex].fWindValue) { 805 #if DEBUG_CONCIDENT 806 SkDebugf("%s 2 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 807 __FUNCTION__, fID, other.fID, tIndex, 808 fTs[tIndex].fT, xyAtT(tIndex).fX, 809 xyAtT(tIndex).fY); 810 #endif 811 addTPair(fTs[tIndex].fT, other, other.fTs[oIndexStart].fT); 812 } 813 } else { 814 SkASSERT(!other.fTs[oIndexStart].fWindValue); 815 if (oIndexStart > 0 && other.fTs[oIndexStart - 1].fWindValue) { 816 #if DEBUG_CONCIDENT 817 SkDebugf("%s 3 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 818 __FUNCTION__, fID, other.fID, oIndexStart - 1, 819 other.fTs[oIndexStart].fT, other.xyAtT(oIndexStart).fX, 820 other.xyAtT(oIndexStart).fY); 821 other.debugAddTPair(other.fTs[oIndexStart].fT, *this, fTs[tIndex].fT); 822 #endif 823 } 824 if (oNextT < 1 && other.fTs[oIndex].fWindValue) { 825 #if DEBUG_CONCIDENT 826 SkDebugf("%s 4 this=%d other=%d t [%d] %1.9g (%1.9g,%1.9g)\n", 827 __FUNCTION__, fID, other.fID, oIndex, 828 other.fTs[oIndex].fT, other.xyAtT(oIndex).fX, 829 other.xyAtT(oIndex).fY); 830 other.debugAddTPair(other.fTs[oIndex].fT, *this, fTs[tIndexStart].fT); 831 #endif 832 } 833 } 834 } 835 836 void addCoinOutsides(const SkTDArray<double>& outsideTs, Segment& other, 837 double oEnd) { 838 // walk this to outsideTs[0] 839 // walk other to outsideTs[1] 840 // if either is > 0, add a pointer to the other, copying adjacent winding 841 int tIndex = -1; 842 int oIndex = -1; 843 double tStart = outsideTs[0]; 844 double oStart = outsideTs[1]; 845 do { 846 ++tIndex; 847 } while (tStart - fTs[tIndex].fT >= FLT_EPSILON); 848 do { 849 ++oIndex; 850 } while (oStart - other.fTs[oIndex].fT >= FLT_EPSILON); 851 if (tIndex > 0 || oIndex > 0) { 852 addTPair(tStart, other, oStart); 853 } 854 tStart = fTs[tIndex].fT; 855 oStart = other.fTs[oIndex].fT; 856 do { 857 double nextT; 858 do { 859 nextT = fTs[++tIndex].fT; 860 } while (nextT - tStart < FLT_EPSILON); 861 tStart = nextT; 862 do { 863 nextT = other.fTs[++oIndex].fT; 864 } while (nextT - oStart < FLT_EPSILON); 865 oStart = nextT; 866 if (tStart == 1 && oStart == 1) { 867 break; 868 } 869 addTPair(tStart, other, oStart); 870 } while (tStart < 1 && oStart < 1 && oEnd - oStart >= FLT_EPSILON); 871 } 872 873 void addCubic(const SkPoint pts[4]) { 874 init(pts, SkPath::kCubic_Verb); 875 fBounds.setCubicBounds(pts); 876 } 877 878 // FIXME: this needs to defer add for aligned consecutive line segments 879 SkPoint addCurveTo(int start, int end, SkPath& path, bool active) { 880 SkPoint edge[4]; 881 // OPTIMIZE? if not active, skip remainder and return xy_at_t(end) 882 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 883 if (active) { 884 #if DEBUG_PATH_CONSTRUCTION 885 SkDebugf("%s %s (%1.9g,%1.9g)", __FUNCTION__, 886 kLVerbStr[fVerb], edge[1].fX, edge[1].fY); 887 if (fVerb > 1) { 888 SkDebugf(" (%1.9g,%1.9g)", edge[2].fX, edge[2].fY); 889 } 890 if (fVerb > 2) { 891 SkDebugf(" (%1.9g,%1.9g)", edge[3].fX, edge[3].fY); 892 } 893 SkDebugf("\n"); 894 #endif 895 switch (fVerb) { 896 case SkPath::kLine_Verb: 897 path.lineTo(edge[1].fX, edge[1].fY); 898 break; 899 case SkPath::kQuad_Verb: 900 path.quadTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY); 901 break; 902 case SkPath::kCubic_Verb: 903 path.cubicTo(edge[1].fX, edge[1].fY, edge[2].fX, edge[2].fY, 904 edge[3].fX, edge[3].fY); 905 break; 906 } 907 } 908 return edge[fVerb]; 909 } 910 911 void addLine(const SkPoint pts[2]) { 912 init(pts, SkPath::kLine_Verb); 913 fBounds.set(pts, 2); 914 } 915 916 const SkPoint& addMoveTo(int tIndex, SkPath& path, bool active) { 917 const SkPoint& pt = xyAtT(tIndex); 918 if (active) { 919 #if DEBUG_PATH_CONSTRUCTION 920 SkDebugf("%s (%1.9g,%1.9g)\n", __FUNCTION__, pt.fX, pt.fY); 921 #endif 922 path.moveTo(pt.fX, pt.fY); 923 } 924 return pt; 925 } 926 927 // add 2 to edge or out of range values to get T extremes 928 void addOtherT(int index, double otherT, int otherIndex) { 929 Span& span = fTs[index]; 930 span.fOtherT = otherT; 931 span.fOtherIndex = otherIndex; 932 } 933 934 void addQuad(const SkPoint pts[3]) { 935 init(pts, SkPath::kQuad_Verb); 936 fBounds.setQuadBounds(pts); 937 } 938 939 // Defer all coincident edge processing until 940 // after normal intersections have been computed 941 942// no need to be tricky; insert in normal T order 943// resolve overlapping ts when considering coincidence later 944 945 // add non-coincident intersection. Resulting edges are sorted in T. 946 int addT(double newT, Segment* other) { 947 // FIXME: in the pathological case where there is a ton of intercepts, 948 // binary search? 949 int insertedAt = -1; 950 size_t tCount = fTs.count(); 951 for (size_t index = 0; index < tCount; ++index) { 952 // OPTIMIZATION: if there are three or more identical Ts, then 953 // the fourth and following could be further insertion-sorted so 954 // that all the edges are clockwise or counterclockwise. 955 // This could later limit segment tests to the two adjacent 956 // neighbors, although it doesn't help with determining which 957 // circular direction to go in. 958 if (newT < fTs[index].fT) { 959 insertedAt = index; 960 break; 961 } 962 } 963 Span* span; 964 if (insertedAt >= 0) { 965 span = fTs.insert(insertedAt); 966 } else { 967 insertedAt = tCount; 968 span = fTs.append(); 969 } 970 span->fT = newT; 971 span->fOther = other; 972 span->fPt.fX = SK_ScalarNaN; 973 span->fWindSum = SK_MinS32; 974 span->fWindValue = 1; 975 if ((span->fDone = newT == 1)) { 976 ++fDoneSpans; 977 } 978 return insertedAt; 979 } 980 981 // set spans from start to end to decrement by one 982 // note this walks other backwards 983 // FIMXE: there's probably an edge case that can be constructed where 984 // two span in one segment are separated by float epsilon on one span but 985 // not the other, if one segment is very small. For this 986 // case the counts asserted below may or may not be enough to separate the 987 // spans. Even if the counts work out, what if the spanw aren't correctly 988 // sorted? It feels better in such a case to match the span's other span 989 // pointer since both coincident segments must contain the same spans. 990 void addTCancel(double startT, double endT, Segment& other, 991 double oStartT, double oEndT) { 992 SkASSERT(endT - startT >= FLT_EPSILON); 993 SkASSERT(oEndT - oStartT >= FLT_EPSILON); 994 int index = 0; 995 while (startT - fTs[index].fT >= FLT_EPSILON) { 996 ++index; 997 } 998 int oIndex = other.fTs.count(); 999 while (other.fTs[--oIndex].fT - oEndT > -FLT_EPSILON) 1000 ; 1001 Span* test = &fTs[index]; 1002 Span* oTest = &other.fTs[oIndex]; 1003 SkTDArray<double> outsideTs; 1004 SkTDArray<double> oOutsideTs; 1005 do { 1006 bool decrement = test->fWindValue && oTest->fWindValue; 1007 bool track = test->fWindValue || oTest->fWindValue; 1008 Span* end = test; 1009 double startT = end->fT; 1010 double oStartT = oTest->fT; 1011 do { 1012 if (decrement) { 1013 decrementSpan(end); 1014 } else if (track && end->fT < 1 && oStartT < 1) { 1015 TrackOutside(outsideTs, end->fT, oStartT); 1016 } 1017 end = &fTs[++index]; 1018 } while (end->fT - test->fT < FLT_EPSILON); 1019 Span* oTestStart = oTest; 1020 do { 1021 if (decrement) { 1022 other.decrementSpan(oTestStart); 1023 } else if (track && oTestStart->fT < 1 && startT < 1) { 1024 TrackOutside(oOutsideTs, oTestStart->fT, startT); 1025 } 1026 if (!oIndex) { 1027 break; 1028 } 1029 oTestStart = &other.fTs[--oIndex]; 1030 } while (oTest->fT - oTestStart->fT < FLT_EPSILON); 1031 test = end; 1032 oTest = oTestStart; 1033 } while (test->fT < endT - FLT_EPSILON); 1034 SkASSERT(!oIndex || oTest->fT <= oStartT - FLT_EPSILON); 1035 // FIXME: determine if canceled edges need outside ts added 1036 if (!done() && outsideTs.count()) { 1037 addCancelOutsides(outsideTs, other, oEndT); 1038 } 1039 if (!other.done() && oOutsideTs.count()) { 1040 other.addCancelOutsides(oOutsideTs, *this, endT); 1041 } 1042 } 1043 1044 // set spans from start to end to increment the greater by one and decrement 1045 // the lesser 1046 void addTCoincident(double startT, double endT, Segment& other, 1047 double oStartT, double oEndT) { 1048 SkASSERT(endT - startT >= FLT_EPSILON); 1049 SkASSERT(oEndT - oStartT >= FLT_EPSILON); 1050 int index = 0; 1051 while (startT - fTs[index].fT >= FLT_EPSILON) { 1052 ++index; 1053 } 1054 int oIndex = 0; 1055 while (oStartT - other.fTs[oIndex].fT >= FLT_EPSILON) { 1056 ++oIndex; 1057 } 1058 Span* test = &fTs[index]; 1059 Span* oTest = &other.fTs[oIndex]; 1060 SkTDArray<double> outsideTs; 1061 SkTDArray<double> xOutsideTs; 1062 SkTDArray<double> oOutsideTs; 1063 SkTDArray<double> oxOutsideTs; 1064 do { 1065 bool transfer = test->fWindValue && oTest->fWindValue; 1066 bool decrementOther = test->fWindValue >= oTest->fWindValue; 1067 Span* end = test; 1068 double startT = end->fT; 1069 int startIndex = index; 1070 double oStartT = oTest->fT; 1071 int oStartIndex = oIndex; 1072 do { 1073 if (transfer) { 1074 if (decrementOther) { 1075 SkASSERT(abs(end->fWindValue) <= gDebugMaxWindValue); 1076 ++(end->fWindValue); 1077 } else if (decrementSpan(end)) { 1078 TrackOutside(outsideTs, end->fT, oStartT); 1079 } 1080 } else if (oTest->fWindValue) { 1081 SkASSERT(!decrementOther); 1082 if (startIndex > 0 && fTs[startIndex - 1].fWindValue) { 1083 TrackOutside(xOutsideTs, end->fT, oStartT); 1084 } 1085 } 1086 end = &fTs[++index]; 1087 } while (end->fT - test->fT < FLT_EPSILON); 1088 Span* oEnd = oTest; 1089 do { 1090 if (transfer) { 1091 if (!decrementOther) { 1092 SkASSERT(abs(oEnd->fWindValue) <= gDebugMaxWindValue); 1093 ++(oEnd->fWindValue); 1094 } else if (other.decrementSpan(oEnd)) { 1095 TrackOutside(oOutsideTs, oEnd->fT, startT); 1096 } 1097 } else if (test->fWindValue) { 1098 SkASSERT(!decrementOther); 1099 if (oStartIndex > 0 && other.fTs[oStartIndex - 1].fWindValue) { 1100 SkASSERT(0); // track for later? 1101 } 1102 } 1103 oEnd = &other.fTs[++oIndex]; 1104 } while (oEnd->fT - oTest->fT < FLT_EPSILON); 1105 test = end; 1106 oTest = oEnd; 1107 } while (test->fT < endT - FLT_EPSILON); 1108 SkASSERT(oTest->fT < oEndT + FLT_EPSILON); 1109 SkASSERT(oTest->fT > oEndT - FLT_EPSILON); 1110 if (!done()) { 1111 if (outsideTs.count()) { 1112 addCoinOutsides(outsideTs, other, oEndT); 1113 } 1114 if (xOutsideTs.count()) { 1115 addCoinOutsides(xOutsideTs, other, oEndT); 1116 } 1117 } 1118 if (!other.done() && oOutsideTs.count()) { 1119 other.addCoinOutsides(oOutsideTs, *this, endT); 1120 } 1121 } 1122 1123 // FIXME: this doesn't prevent the same span from being added twice 1124 // fix in caller, assert here? 1125 void addTPair(double t, Segment& other, double otherT) { 1126 int tCount = fTs.count(); 1127 for (int tIndex = 0; tIndex < tCount; ++tIndex) { 1128 const Span& span = fTs[tIndex]; 1129 if (span.fT > t) { 1130 break; 1131 } 1132 if (span.fT == t && span.fOther == &other && span.fOtherT == otherT) { 1133#if DEBUG_ADD_T_PAIR 1134 SkDebugf("%s addTPair duplicate this=%d %1.9g other=%d %1.9g\n", 1135 __FUNCTION__, fID, t, other.fID, otherT); 1136#endif 1137 return; 1138 } 1139 } 1140#if DEBUG_ADD_T_PAIR 1141 SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n", 1142 __FUNCTION__, fID, t, other.fID, otherT); 1143#endif 1144 int insertedAt = addT(t, &other); 1145 int otherInsertedAt = other.addT(otherT, this); 1146 addOtherT(insertedAt, otherT, otherInsertedAt); 1147 other.addOtherT(otherInsertedAt, t, insertedAt); 1148 Span& newSpan = fTs[insertedAt]; 1149 if (insertedAt > 0) { 1150 const Span& lastSpan = fTs[insertedAt - 1]; 1151 if (t - lastSpan.fT < FLT_EPSILON) { 1152 int tWind = lastSpan.fWindValue; 1153 newSpan.fWindValue = tWind; 1154 if (!tWind) { 1155 newSpan.fDone = true; 1156 ++fDoneSpans; 1157 } 1158 } 1159 } 1160 int oIndex = newSpan.fOtherIndex; 1161 if (oIndex > 0) { 1162 const Span& lastOther = other.fTs[oIndex - 1]; 1163 if (otherT - lastOther.fT < FLT_EPSILON) { 1164 int oWind = lastOther.fWindValue; 1165 Span& otherSpan = other.fTs[oIndex]; 1166 otherSpan.fWindValue = oWind; 1167 if (!oWind) { 1168 otherSpan.fDone = true; 1169 ++(other.fDoneSpans); 1170 } 1171 } 1172 } 1173 } 1174 1175 void addTwoAngles(int start, int end, SkTDArray<Angle>& angles) const { 1176 // add edge leading into junction 1177 if (fTs[SkMin32(end, start)].fWindValue > 0) { 1178 addAngle(angles, end, start); 1179 } 1180 // add edge leading away from junction 1181 int step = SkSign32(end - start); 1182 int tIndex = nextSpan(end, step); 1183 if (tIndex >= 0 && fTs[SkMin32(end, tIndex)].fWindValue > 0) { 1184 addAngle(angles, end, tIndex); 1185 } 1186 } 1187 1188 const Bounds& bounds() const { 1189 return fBounds; 1190 } 1191 1192 void buildAngles(int index, SkTDArray<Angle>& angles) const { 1193 double referenceT = fTs[index].fT; 1194 int lesser = index; 1195 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 1196 buildAnglesInner(lesser, angles); 1197 } 1198 do { 1199 buildAnglesInner(index, angles); 1200 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 1201 } 1202 1203 void buildAnglesInner(int index, SkTDArray<Angle>& angles) const { 1204 Span* span = &fTs[index]; 1205 Segment* other = span->fOther; 1206 // if there is only one live crossing, and no coincidence, continue 1207 // in the same direction 1208 // if there is coincidence, the only choice may be to reverse direction 1209 // find edge on either side of intersection 1210 int oIndex = span->fOtherIndex; 1211 // if done == -1, prior span has already been processed 1212 int step = 1; 1213 int next = other->nextSpan(oIndex, step); 1214 if (next < 0) { 1215 step = -step; 1216 next = other->nextSpan(oIndex, step); 1217 } 1218 // add candidate into and away from junction 1219 other->addTwoAngles(next, oIndex, angles); 1220 } 1221 1222 bool cancels(const Segment& other) const { 1223 SkASSERT(fVerb == SkPath::kLine_Verb); 1224 SkASSERT(other.fVerb == SkPath::kLine_Verb); 1225 SkPoint dxy = fPts[0] - fPts[1]; 1226 SkPoint odxy = other.fPts[0] - other.fPts[1]; 1227 return dxy.fX * odxy.fX < 0 || dxy.fY * odxy.fY < 0; 1228 } 1229 1230 // figure out if the segment's ascending T goes clockwise or not 1231 // not enough context to write this as shown 1232 // instead, add all segments meeting at the top 1233 // sort them using buildAngleList 1234 // find the first in the sort 1235 // see if ascendingT goes to top 1236 bool clockwise(int /* tIndex */) const { 1237 SkASSERT(0); // incomplete 1238 return false; 1239 } 1240 1241 int crossedSpan(const SkPoint& basePt, SkScalar& bestY, double& hitT) const { 1242 int bestT = -1; 1243 SkScalar top = bounds().fTop; 1244 SkScalar bottom = bounds().fBottom; 1245 int end = 0; 1246 do { 1247 int start = end; 1248 end = nextSpan(start, 1); 1249 if (fTs[start].fWindValue == 0) { 1250 continue; 1251 } 1252 SkPoint edge[4]; 1253 // OPTIMIZE: wrap this so that if start==0 end==fTCount-1 we can 1254 // work with the original data directly 1255 (*SegmentSubDivide[fVerb])(fPts, fTs[start].fT, fTs[end].fT, edge); 1256 // intersect ray starting at basePt with edge 1257 Intersections intersections; 1258 int pts = (*VSegmentIntersect[fVerb])(edge, top, bottom, basePt.fX, 1259 false, intersections); 1260 if (pts == 0) { 1261 continue; 1262 } 1263 if (pts > 1 && fVerb == SkPath::kLine_Verb) { 1264 // if the intersection is edge on, wait for another one 1265 continue; 1266 } 1267 SkASSERT(pts == 1); // FIXME: more code required to disambiguate 1268 SkPoint pt; 1269 double foundT = intersections.fT[0][0]; 1270 (*SegmentXYAtT[fVerb])(fPts, foundT, &pt); 1271 if (bestY < pt.fY) { 1272 bestY = pt.fY; 1273 bestT = foundT < 1 ? start : end; 1274 hitT = fTs[start].fT + (fTs[end].fT - fTs[start].fT) * foundT; 1275 } 1276 } while (fTs[end].fT != 1); 1277 return bestT; 1278 } 1279 1280 bool decrementSpan(Span* span) { 1281 SkASSERT(span->fWindValue > 0); 1282 if (--(span->fWindValue) == 0) { 1283 span->fDone = true; 1284 ++fDoneSpans; 1285 return true; 1286 } 1287 return false; 1288 } 1289 1290 bool done() const { 1291 SkASSERT(fDoneSpans <= fTs.count()); 1292 return fDoneSpans == fTs.count(); 1293 } 1294 1295 bool done(const Angle& angle) const { 1296 int start = angle.start(); 1297 int end = angle.end(); 1298 const Span& mSpan = fTs[SkMin32(start, end)]; 1299 return mSpan.fDone; 1300 } 1301 1302 // so the span needs to contain the pairing info found here 1303 // this should include the winding computed for the edge, and 1304 // what edge it connects to, and whether it is discarded 1305 // (maybe discarded == abs(winding) > 1) ? 1306 // only need derivatives for duration of sorting, add a new struct 1307 // for pairings, remove extra spans that have zero length and 1308 // reference an unused other 1309 // for coincident, the last span on the other may be marked done 1310 // (always?) 1311 1312 // if loop is exhausted, contour may be closed. 1313 // FIXME: pass in close point so we can check for closure 1314 1315 // given a segment, and a sense of where 'inside' is, return the next 1316 // segment. If this segment has an intersection, or ends in multiple 1317 // segments, find the mate that continues the outside. 1318 // note that if there are multiples, but no coincidence, we can limit 1319 // choices to connections in the correct direction 1320 1321 // mark found segments as done 1322 1323 // start is the index of the beginning T of this edge 1324 // it is guaranteed to have an end which describes a non-zero length (?) 1325 // winding -1 means ccw, 1 means cw 1326 // firstFind allows coincident edges to be treated differently 1327 Segment* findNext(SkTDArray<Span*>& chase, bool firstFind, bool active, 1328 const int startIndex, const int endIndex, int& nextStart, 1329 int& nextEnd, int& winding, int& spanWinding) { 1330 int sumWinding = winding + spanWinding; 1331 if (sumWinding == 0) { 1332 sumWinding = spanWinding; 1333 } 1334 bool insideContour = active && winding && winding * sumWinding < 0; 1335 if (insideContour) { 1336 sumWinding = winding; 1337 } 1338 1339 #if DEBUG_WINDING 1340 SkDebugf("%s winding=%d spanWinding=%d sumWinding=%d\n", 1341 __FUNCTION__, winding, spanWinding, sumWinding); 1342 #endif 1343 SkASSERT(startIndex != endIndex); 1344 int count = fTs.count(); 1345 SkASSERT(startIndex < endIndex ? startIndex < count - 1 1346 : startIndex > 0); 1347 int step = SkSign32(endIndex - startIndex); 1348 int end = nextSpan(startIndex, step); 1349 SkASSERT(end >= 0); 1350 Span* endSpan = &fTs[end]; 1351 Segment* other; 1352 if (isSimple(end)) { 1353 // mark the smaller of startIndex, endIndex done, and all adjacent 1354 // spans with the same T value (but not 'other' spans) 1355 markDone(SkMin32(startIndex, endIndex), sumWinding); 1356 other = endSpan->fOther; 1357 nextStart = endSpan->fOtherIndex; 1358 double startT = other->fTs[nextStart].fT; 1359 nextEnd = nextStart; 1360 do { 1361 nextEnd += step; 1362 } while (fabs(startT - other->fTs[nextEnd].fT) < FLT_EPSILON); 1363 SkASSERT(step < 0 ? nextEnd >= 0 : nextEnd < other->fTs.count()); 1364 return other; 1365 } 1366 // more than one viable candidate -- measure angles to find best 1367 SkTDArray<Angle> angles; 1368 SkASSERT(startIndex - endIndex != 0); 1369 SkASSERT((startIndex - endIndex < 0) ^ (step < 0)); 1370 addTwoAngles(startIndex, end, angles); 1371 buildAngles(end, angles); 1372 SkTDArray<Angle*> sorted; 1373 sortAngles(angles, sorted); 1374 int angleCount = angles.count(); 1375 int firstIndex = findStartingEdge(sorted, startIndex, end); 1376 SkASSERT(firstIndex >= 0); 1377 #if DEBUG_SORT 1378 debugShowSort(sorted, firstIndex, winding, sumWinding); 1379 #endif 1380 bool doBump = sorted[firstIndex]->firstBump(sumWinding); 1381 #if DEBUG_WINDING 1382 SkDebugf("%s sumWinding=%d sign=%d (%sbump)\n", __FUNCTION__, 1383 sumWinding, sorted[firstIndex]->sign(), doBump ? "" : "no "); 1384 #endif 1385 bool innerSwap = active && (doBump || insideContour); 1386 int startWinding = sumWinding; 1387 // SkASSERT(SkSign32(sumWinding) == SkSign32(winding) || winding == 0); 1388 if (doBump || insideContour) { 1389 sumWinding -= windBump(sorted[firstIndex]); 1390 } 1391 int nextIndex = firstIndex + 1; 1392 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 1393 const Angle* foundAngle = NULL; 1394 bool foundDone = false; 1395 // iterate through the angle, and compute everyone's winding 1396 bool toggleWinding = false; 1397 bool flipFound = false; 1398 int flipped = 1; 1399 Segment* nextSegment; 1400 do { 1401 if (nextIndex == angleCount) { 1402 nextIndex = 0; 1403 } 1404 const Angle* nextAngle = sorted[nextIndex]; 1405 int maxWinding = sumWinding; 1406 nextSegment = nextAngle->segment(); 1407 sumWinding -= nextSegment->windBump(nextAngle); 1408 SkASSERT(abs(sumWinding) <= gDebugMaxWindSum); 1409 #if DEBUG_WINDING 1410 SkDebugf("%s maxWinding=%d sumWinding=%d sign=%d\n", __FUNCTION__, 1411 maxWinding, sumWinding, nextAngle->sign()); 1412 #endif 1413 if (maxWinding * sumWinding < 0) { 1414 flipFound ^= true; 1415 #if DEBUG_WINDING 1416 SkDebugf("flipFound maxWinding=%d sumWinding=%d\n", 1417 maxWinding, sumWinding); 1418 #endif 1419 } 1420 if (!sumWinding) { 1421 if (!active) { 1422 markDone(SkMin32(startIndex, endIndex), startWinding); 1423 nextSegment->markWinding(SkMin32(nextAngle->start(), 1424 nextAngle->end()), maxWinding); 1425 #if DEBUG_WINDING 1426 SkDebugf("%s inactive\n", __FUNCTION__); 1427 #endif 1428 return NULL; 1429 } 1430 if (!foundAngle || foundDone) { 1431 foundAngle = nextAngle; 1432 foundDone = nextSegment->done(*nextAngle); 1433 if (flipFound || (maxWinding * startWinding < 0)) { 1434 flipped = -flipped; 1435 #if DEBUG_WINDING 1436 SkDebugf("flipped flipFound=%d maxWinding=%d startWinding=%d\n", 1437 flipFound, maxWinding, startWinding); 1438 #endif 1439 } 1440 } 1441 continue; 1442 } 1443 if (!maxWinding && innerSwap && !foundAngle) { 1444 if (sumWinding * startWinding < 0 && flipped > 0) { 1445 #if DEBUG_WINDING 1446 SkDebugf("%s toggleWinding\n"); 1447 #endif 1448 toggleWinding = true; 1449 } else if (startWinding != sumWinding) { 1450 winding = sumWinding; 1451 } 1452 foundAngle = nextAngle; 1453 if (flipFound) { 1454 flipped = -1; 1455 #if DEBUG_WINDING 1456 SkDebugf("flipped flipFound=%d\n", flipFound); 1457 #endif 1458 } 1459 } 1460 if (nextSegment->done()) { 1461 continue; 1462 } 1463 // if the winding is non-zero, nextAngle does not connect to 1464 // current chain. If we haven't done so already, mark the angle 1465 // as done, record the winding value, and mark connected unambiguous 1466 // segments as well. 1467 if (nextSegment->windSum(nextAngle) == SK_MinS32) { 1468 if (abs(maxWinding) < abs(sumWinding)) { 1469 maxWinding = sumWinding; 1470 } 1471 Span* last; 1472 if (foundAngle || innerSwap) { 1473 last = nextSegment->markAndChaseWinding(nextAngle, maxWinding); 1474 } else { 1475 last = nextSegment->markAndChaseDone(nextAngle, maxWinding); 1476 } 1477 if (last) { 1478 *chase.append() = last; 1479 } 1480 } 1481 } while (++nextIndex != lastIndex); 1482 SkASSERT(sorted[firstIndex]->segment() == this); 1483 markDone(SkMin32(startIndex, endIndex), startWinding); 1484 if (!foundAngle) { 1485 return NULL; 1486 } 1487 nextStart = foundAngle->start(); 1488 nextEnd = foundAngle->end(); 1489 nextSegment = foundAngle->segment(); 1490 spanWinding = SkSign32(spanWinding) * flipped * nextSegment->windValue( 1491 SkMin32(nextStart, nextEnd)); 1492 if (toggleWinding) { 1493 if (winding) { 1494 winding = 0; 1495 } else { 1496 winding = -startWinding; 1497 } 1498 } 1499 #if 0 1500 int min = SkMin32(nextStart, nextEnd); 1501 int sign = foundAngle->sign(); 1502 int windSum = nextSegment->windSum(min); 1503 int windValue = nextSegment->windValue(min); 1504 SkASSERT(winding + sign * windValue == windSum); 1505 #endif 1506 #if DEBUG_WINDING 1507 SkDebugf("%s spanWinding=%d\n", __FUNCTION__, spanWinding); 1508 #endif 1509 return nextSegment; 1510 } 1511 1512 int findStartingEdge(SkTDArray<Angle*>& sorted, int start, int end) { 1513 int angleCount = sorted.count(); 1514 int firstIndex = -1; 1515 for (int angleIndex = 0; angleIndex < angleCount; ++angleIndex) { 1516 const Angle* angle = sorted[angleIndex]; 1517 if (angle->segment() == this && angle->start() == end && 1518 angle->end() == start) { 1519 firstIndex = angleIndex; 1520 break; 1521 } 1522 } 1523 return firstIndex; 1524 } 1525 1526 // FIXME: this is tricky code; needs its own unit test 1527 void findTooCloseToCall(int /* winding */ ) { // FIXME: winding should be considered 1528 int count = fTs.count(); 1529 if (count < 3) { // require t=0, x, 1 at minimum 1530 return; 1531 } 1532 int matchIndex = 0; 1533 int moCount; 1534 Span* match; 1535 Segment* mOther; 1536 do { 1537 match = &fTs[matchIndex]; 1538 mOther = match->fOther; 1539 moCount = mOther->fTs.count(); 1540 if (moCount >= 3) { 1541 break; 1542 } 1543 if (++matchIndex >= count) { 1544 return; 1545 } 1546 } while (true); // require t=0, x, 1 at minimum 1547 // OPTIMIZATION: defer matchPt until qualifying toCount is found? 1548 const SkPoint* matchPt = &xyAtT(match); 1549 // look for a pair of nearby T values that map to the same (x,y) value 1550 // if found, see if the pair of other segments share a common point. If 1551 // so, the span from here to there is coincident. 1552 for (int index = matchIndex + 1; index < count; ++index) { 1553 Span* test = &fTs[index]; 1554 if (test->fDone) { 1555 continue; 1556 } 1557 Segment* tOther = test->fOther; 1558 int toCount = tOther->fTs.count(); 1559 if (toCount < 3) { // require t=0, x, 1 at minimum 1560 continue; 1561 } 1562 const SkPoint* testPt = &xyAtT(test); 1563 if (*matchPt != *testPt) { 1564 matchIndex = index; 1565 moCount = toCount; 1566 match = test; 1567 mOther = tOther; 1568 matchPt = testPt; 1569 continue; 1570 } 1571 int moStart = -1; 1572 int moEnd = -1; 1573 double moStartT, moEndT; 1574 for (int moIndex = 0; moIndex < moCount; ++moIndex) { 1575 Span& moSpan = mOther->fTs[moIndex]; 1576 if (moSpan.fDone) { 1577 continue; 1578 } 1579 if (moSpan.fOther == this) { 1580 if (moSpan.fOtherT == match->fT) { 1581 moStart = moIndex; 1582 moStartT = moSpan.fT; 1583 } 1584 continue; 1585 } 1586 if (moSpan.fOther == tOther) { 1587 SkASSERT(moEnd == -1); 1588 moEnd = moIndex; 1589 moEndT = moSpan.fT; 1590 } 1591 } 1592 if (moStart < 0 || moEnd < 0) { 1593 continue; 1594 } 1595 // FIXME: if moStartT, moEndT are initialized to NaN, can skip this test 1596 if (moStartT == moEndT) { 1597 continue; 1598 } 1599 int toStart = -1; 1600 int toEnd = -1; 1601 double toStartT, toEndT; 1602 for (int toIndex = 0; toIndex < toCount; ++toIndex) { 1603 Span& toSpan = tOther->fTs[toIndex]; 1604 if (toSpan.fOther == this) { 1605 if (toSpan.fOtherT == test->fT) { 1606 toStart = toIndex; 1607 toStartT = toSpan.fT; 1608 } 1609 continue; 1610 } 1611 if (toSpan.fOther == mOther && toSpan.fOtherT == moEndT) { 1612 SkASSERT(toEnd == -1); 1613 toEnd = toIndex; 1614 toEndT = toSpan.fT; 1615 } 1616 } 1617 // FIXME: if toStartT, toEndT are initialized to NaN, can skip this test 1618 if (toStart <= 0 || toEnd <= 0) { 1619 continue; 1620 } 1621 if (toStartT == toEndT) { 1622 continue; 1623 } 1624 // test to see if the segment between there and here is linear 1625 if (!mOther->isLinear(moStart, moEnd) 1626 || !tOther->isLinear(toStart, toEnd)) { 1627 continue; 1628 } 1629 // FIXME: defer implementation until the rest works 1630 // this may share code with regular coincident detection 1631 SkASSERT(0); 1632 #if 0 1633 if (flipped) { 1634 mOther->addTCancel(moStart, moEnd, tOther, tStart, tEnd); 1635 } else { 1636 mOther->addTCoincident(moStart, moEnd, tOther, tStart, tEnd); 1637 } 1638 #endif 1639 } 1640 } 1641 1642 // OPTIMIZATION : for a pair of lines, can we compute points at T (cached) 1643 // and use more concise logic like the old edge walker code? 1644 // FIXME: this needs to deal with coincident edges 1645 Segment* findTop(int& tIndex, int& endIndex) { 1646 // iterate through T intersections and return topmost 1647 // topmost tangent from y-min to first pt is closer to horizontal 1648 SkASSERT(!done()); 1649 int firstT; 1650 int lastT; 1651 SkPoint topPt; 1652 topPt.fY = SK_ScalarMax; 1653 int count = fTs.count(); 1654 // see if either end is not done since we want smaller Y of the pair 1655 bool lastDone = true; 1656 for (int index = 0; index < count; ++index) { 1657 const Span& span = fTs[index]; 1658 if (!span.fDone || !lastDone) { 1659 const SkPoint& intercept = xyAtT(&span); 1660 if (topPt.fY > intercept.fY || (topPt.fY == intercept.fY 1661 && topPt.fX > intercept.fX)) { 1662 topPt = intercept; 1663 firstT = lastT = index; 1664 } else if (topPt == intercept) { 1665 lastT = index; 1666 } 1667 } 1668 lastDone = span.fDone; 1669 } 1670 // sort the edges to find the leftmost 1671 int step = 1; 1672 int end = nextSpan(firstT, step); 1673 if (end == -1) { 1674 step = -1; 1675 end = nextSpan(firstT, step); 1676 SkASSERT(end != -1); 1677 } 1678 // if the topmost T is not on end, or is three-way or more, find left 1679 // look for left-ness from tLeft to firstT (matching y of other) 1680 SkTDArray<Angle> angles; 1681 SkASSERT(firstT - end != 0); 1682 addTwoAngles(end, firstT, angles); 1683 buildAngles(firstT, angles); 1684 SkTDArray<Angle*> sorted; 1685 sortAngles(angles, sorted); 1686 // skip edges that have already been processed 1687 firstT = -1; 1688 Segment* leftSegment; 1689 do { 1690 const Angle* angle = sorted[++firstT]; 1691 leftSegment = angle->segment(); 1692 tIndex = angle->end(); 1693 endIndex = angle->start(); 1694 } while (leftSegment->fTs[SkMin32(tIndex, endIndex)].fDone); 1695 return leftSegment; 1696 } 1697 1698 // FIXME: not crazy about this 1699 // when the intersections are performed, the other index is into an 1700 // incomplete array. as the array grows, the indices become incorrect 1701 // while the following fixes the indices up again, it isn't smart about 1702 // skipping segments whose indices are already correct 1703 // assuming we leave the code that wrote the index in the first place 1704 void fixOtherTIndex() { 1705 int iCount = fTs.count(); 1706 for (int i = 0; i < iCount; ++i) { 1707 Span& iSpan = fTs[i]; 1708 double oT = iSpan.fOtherT; 1709 Segment* other = iSpan.fOther; 1710 int oCount = other->fTs.count(); 1711 for (int o = 0; o < oCount; ++o) { 1712 Span& oSpan = other->fTs[o]; 1713 if (oT == oSpan.fT && this == oSpan.fOther) { 1714 iSpan.fOtherIndex = o; 1715 break; 1716 } 1717 } 1718 } 1719 } 1720 1721 // OPTIMIZATION: uses tail recursion. Unwise? 1722 Span* innerChaseDone(int index, int step, int winding) { 1723 int end = nextSpan(index, step); 1724 SkASSERT(end >= 0); 1725 if (multipleSpans(end)) { 1726 return &fTs[end]; 1727 } 1728 const Span& endSpan = fTs[end]; 1729 Segment* other = endSpan.fOther; 1730 index = endSpan.fOtherIndex; 1731 int otherEnd = other->nextSpan(index, step); 1732 Span* last = other->innerChaseDone(index, step, winding); 1733 other->markDone(SkMin32(index, otherEnd), winding); 1734 return last; 1735 } 1736 1737 Span* innerChaseWinding(int index, int step, int winding) { 1738 int end = nextSpan(index, step); 1739 SkASSERT(end >= 0); 1740 if (multipleSpans(end)) { 1741 return &fTs[end]; 1742 } 1743 const Span& endSpan = fTs[end]; 1744 Segment* other = endSpan.fOther; 1745 index = endSpan.fOtherIndex; 1746 int otherEnd = other->nextSpan(index, step); 1747 int min = SkMin32(index, otherEnd); 1748 if (other->fTs[min].fWindSum != SK_MinS32) { 1749 SkASSERT(other->fTs[min].fWindSum == winding); 1750 return NULL; 1751 } 1752 Span* last = other->innerChaseWinding(index, step, winding); 1753 other->markWinding(min, winding); 1754 return last; 1755 } 1756 1757 void init(const SkPoint pts[], SkPath::Verb verb) { 1758 fPts = pts; 1759 fVerb = verb; 1760 fDoneSpans = 0; 1761 } 1762 1763 bool intersected() const { 1764 return fTs.count() > 0; 1765 } 1766 1767 bool isConnected(int startIndex, int endIndex) const { 1768 return fTs[startIndex].fWindSum != SK_MinS32 1769 || fTs[endIndex].fWindSum != SK_MinS32; 1770 } 1771 1772 bool isLinear(int start, int end) const { 1773 if (fVerb == SkPath::kLine_Verb) { 1774 return true; 1775 } 1776 if (fVerb == SkPath::kQuad_Verb) { 1777 SkPoint qPart[3]; 1778 QuadSubDivide(fPts, fTs[start].fT, fTs[end].fT, qPart); 1779 return QuadIsLinear(qPart); 1780 } else { 1781 SkASSERT(fVerb == SkPath::kCubic_Verb); 1782 SkPoint cPart[4]; 1783 CubicSubDivide(fPts, fTs[start].fT, fTs[end].fT, cPart); 1784 return CubicIsLinear(cPart); 1785 } 1786 } 1787 1788 // OPTIMIZE: successive calls could start were the last leaves off 1789 // or calls could specialize to walk forwards or backwards 1790 bool isMissing(double startT) const { 1791 size_t tCount = fTs.count(); 1792 for (size_t index = 0; index < tCount; ++index) { 1793 if (fabs(startT - fTs[index].fT) < FLT_EPSILON) { 1794 return false; 1795 } 1796 } 1797 return true; 1798 } 1799 1800 bool isSimple(int end) const { 1801 int count = fTs.count(); 1802 if (count == 2) { 1803 return true; 1804 } 1805 double t = fTs[end].fT; 1806 if (t < FLT_EPSILON) { 1807 return fTs[1].fT >= FLT_EPSILON; 1808 } 1809 if (t > 1 - FLT_EPSILON) { 1810 return fTs[count - 2].fT <= 1 - FLT_EPSILON; 1811 } 1812 return false; 1813 } 1814 1815 bool isHorizontal() const { 1816 return fBounds.fTop == fBounds.fBottom; 1817 } 1818 1819 bool isVertical() const { 1820 return fBounds.fLeft == fBounds.fRight; 1821 } 1822 1823 SkScalar leftMost(int start, int end) const { 1824 return (*SegmentLeftMost[fVerb])(fPts, fTs[start].fT, fTs[end].fT); 1825 } 1826 1827 // this span is excluded by the winding rule -- chase the ends 1828 // as long as they are unambiguous to mark connections as done 1829 // and give them the same winding value 1830 Span* markAndChaseDone(const Angle* angle, int winding) { 1831 int index = angle->start(); 1832 int endIndex = angle->end(); 1833 int step = SkSign32(endIndex - index); 1834 Span* last = innerChaseDone(index, step, winding); 1835 markDone(SkMin32(index, endIndex), winding); 1836 return last; 1837 } 1838 1839 Span* markAndChaseWinding(const Angle* angle, int winding) { 1840 int index = angle->start(); 1841 int endIndex = angle->end(); 1842 int min = SkMin32(index, endIndex); 1843 int step = SkSign32(endIndex - index); 1844 Span* last = innerChaseWinding(index, step, winding); 1845 markWinding(min, winding); 1846 return last; 1847 } 1848 1849 // FIXME: this should also mark spans with equal (x,y) 1850 // This may be called when the segment is already marked done. While this 1851 // wastes time, it shouldn't do any more than spin through the T spans. 1852 // OPTIMIZATION: abort on first done found (assuming that this code is 1853 // always called to mark segments done). 1854 void markDone(int index, int winding) { 1855 // SkASSERT(!done()); 1856 double referenceT = fTs[index].fT; 1857 int lesser = index; 1858 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 1859 Span& span = fTs[lesser]; 1860 if (span.fDone) { 1861 continue; 1862 } 1863 #if DEBUG_MARK_DONE 1864 const SkPoint& pt = xyAtT(&span); 1865 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", 1866 __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding); 1867 #endif 1868 span.fDone = true; 1869 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1870 SkASSERT(abs(winding) <= gDebugMaxWindSum); 1871 span.fWindSum = winding; 1872 fDoneSpans++; 1873 } 1874 do { 1875 Span& span = fTs[index]; 1876 // SkASSERT(!span.fDone); 1877 if (span.fDone) { 1878 continue; 1879 } 1880 #if DEBUG_MARK_DONE 1881 const SkPoint& pt = xyAtT(&span); 1882 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", 1883 __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding); 1884 #endif 1885 span.fDone = true; 1886 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1887 SkASSERT(abs(winding) <= gDebugMaxWindSum); 1888 span.fWindSum = winding; 1889 fDoneSpans++; 1890 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 1891 } 1892 1893 void markWinding(int index, int winding) { 1894 // SkASSERT(!done()); 1895 double referenceT = fTs[index].fT; 1896 int lesser = index; 1897 while (--lesser >= 0 && referenceT - fTs[lesser].fT < FLT_EPSILON) { 1898 Span& span = fTs[lesser]; 1899 if (span.fDone) { 1900 continue; 1901 } 1902 // SkASSERT(span.fWindValue == 1 || winding == 0); 1903 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1904 #if DEBUG_MARK_DONE 1905 const SkPoint& pt = xyAtT(&span); 1906 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", 1907 __FUNCTION__, fID, lesser, span.fT, pt.fX, pt.fY, winding); 1908 #endif 1909 SkASSERT(abs(winding) <= gDebugMaxWindSum); 1910 span.fWindSum = winding; 1911 } 1912 do { 1913 Span& span = fTs[index]; 1914 // SkASSERT(!span.fDone || span.fCoincident); 1915 if (span.fDone) { 1916 continue; 1917 } 1918 // SkASSERT(span.fWindValue == 1 || winding == 0); 1919 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding); 1920 #if DEBUG_MARK_DONE 1921 const SkPoint& pt = xyAtT(&span); 1922 SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g) wind=%d\n", 1923 __FUNCTION__, fID, index, span.fT, pt.fX, pt.fY, winding); 1924 #endif 1925 SkASSERT(abs(winding) <= gDebugMaxWindSum); 1926 span.fWindSum = winding; 1927 } while (++index < fTs.count() && fTs[index].fT - referenceT < FLT_EPSILON); 1928 } 1929 1930 // return span if when chasing, two or more radiating spans are not done 1931 // OPTIMIZATION: ? multiple spans is detected when there is only one valid 1932 // candidate and the remaining spans have windValue == 0 (canceled by 1933 // coincidence). The coincident edges could either be removed altogether, 1934 // or this code could be more complicated in detecting this case. Worth it? 1935 bool multipleSpans(int end) const { 1936 return end > 0 && end < fTs.count() - 1; 1937 } 1938 1939 // This has callers for two different situations: one establishes the end 1940 // of the current span, and one establishes the beginning of the next span 1941 // (thus the name). When this is looking for the end of the current span, 1942 // coincidence is found when the beginning Ts contain -step and the end 1943 // contains step. When it is looking for the beginning of the next, the 1944 // first Ts found can be ignored and the last Ts should contain -step. 1945 // OPTIMIZATION: probably should split into two functions 1946 int nextSpan(int from, int step) const { 1947 const Span& fromSpan = fTs[from]; 1948 int count = fTs.count(); 1949 int to = from; 1950 while (step > 0 ? ++to < count : --to >= 0) { 1951 const Span& span = fTs[to]; 1952 if ((step > 0 ? span.fT - fromSpan.fT : fromSpan.fT - span.fT) < FLT_EPSILON) { 1953 continue; 1954 } 1955 return to; 1956 } 1957 return -1; 1958 } 1959 1960 const SkPoint* pts() const { 1961 return fPts; 1962 } 1963 1964 void reset() { 1965 init(NULL, (SkPath::Verb) -1); 1966 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 1967 fTs.reset(); 1968 } 1969 1970 // OPTIMIZATION: mark as debugging only if used solely by tests 1971 const Span& span(int tIndex) const { 1972 return fTs[tIndex]; 1973 } 1974 1975 int spanSign(int startIndex, int endIndex) const { 1976 return startIndex < endIndex ? -fTs[startIndex].fWindValue : 1977 fTs[endIndex].fWindValue; 1978 } 1979 1980 // OPTIMIZATION: mark as debugging only if used solely by tests 1981 double t(int tIndex) const { 1982 return fTs[tIndex].fT; 1983 } 1984 1985 static void TrackOutside(SkTDArray<double>& outsideTs, double end, 1986 double start) { 1987 int outCount = outsideTs.count(); 1988 if (outCount == 0 || end - outsideTs[outCount - 2] >= FLT_EPSILON) { 1989 *outsideTs.append() = end; 1990 *outsideTs.append() = start; 1991 } 1992 } 1993 1994 void updatePts(const SkPoint pts[]) { 1995 fPts = pts; 1996 } 1997 1998 SkPath::Verb verb() const { 1999 return fVerb; 2000 } 2001 2002 int windBump(const Angle* angle) const { 2003 SkASSERT(angle->segment() == this); 2004 const Span& span = fTs[SkMin32(angle->start(), angle->end())]; 2005 int result = angle->sign() * span.fWindValue; 2006#if DEBUG_WIND_BUMP 2007 SkDebugf("%s bump=%d\n", __FUNCTION__, result); 2008#endif 2009 return result; 2010 } 2011 2012 int windSum(int tIndex) const { 2013 return fTs[tIndex].fWindSum; 2014 } 2015 2016 int windSum(const Angle* angle) const { 2017 int start = angle->start(); 2018 int end = angle->end(); 2019 int index = SkMin32(start, end); 2020 return windSum(index); 2021 } 2022 2023 int windValue(int tIndex) const { 2024 return fTs[tIndex].fWindValue; 2025 } 2026 2027 int windValue(const Angle* angle) const { 2028 int start = angle->start(); 2029 int end = angle->end(); 2030 int index = SkMin32(start, end); 2031 return windValue(index); 2032 } 2033 2034 SkScalar xAtT(const Span* span) const { 2035 return xyAtT(span).fX; 2036 } 2037 2038 const SkPoint& xyAtT(int index) const { 2039 return xyAtT(&fTs[index]); 2040 } 2041 2042 const SkPoint& xyAtT(const Span* span) const { 2043 if (SkScalarIsNaN(span->fPt.fX)) { 2044 if (span->fT == 0) { 2045 span->fPt = fPts[0]; 2046 } else if (span->fT == 1) { 2047 span->fPt = fPts[fVerb]; 2048 } else { 2049 (*SegmentXYAtT[fVerb])(fPts, span->fT, &span->fPt); 2050 } 2051 } 2052 return span->fPt; 2053 } 2054 2055 SkScalar yAtT(int index) const { 2056 return yAtT(&fTs[index]); 2057 } 2058 2059 SkScalar yAtT(const Span* span) const { 2060 return xyAtT(span).fY; 2061 } 2062 2063#if DEBUG_DUMP 2064 void dump() const { 2065 const char className[] = "Segment"; 2066 const int tab = 4; 2067 for (int i = 0; i < fTs.count(); ++i) { 2068 SkPoint out; 2069 (*SegmentXYAtT[fVerb])(fPts, t(i), &out); 2070 SkDebugf("%*s [%d] %s.fTs[%d]=%1.9g (%1.9g,%1.9g) other=%d" 2071 " otherT=%1.9g windSum=%d\n", 2072 tab + sizeof(className), className, fID, 2073 kLVerbStr[fVerb], i, fTs[i].fT, out.fX, out.fY, 2074 fTs[i].fOther->fID, fTs[i].fOtherT, fTs[i].fWindSum); 2075 } 2076 SkDebugf("%*s [%d] fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)", 2077 tab + sizeof(className), className, fID, 2078 fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom); 2079 } 2080#endif 2081 2082#if DEBUG_CONCIDENT 2083 // assert if pair has not already been added 2084 void debugAddTPair(double t, const Segment& other, double otherT) { 2085 for (int i = 0; i < fTs.count(); ++i) { 2086 if (fTs[i].fT == t && fTs[i].fOther == &other && fTs[i].fOtherT == otherT) { 2087 return; 2088 } 2089 } 2090 SkASSERT(0); 2091 } 2092#endif 2093 2094#if DEBUG_CONCIDENT 2095 void debugShowTs() { 2096 SkDebugf("%s %d", __FUNCTION__, fID); 2097 for (int i = 0; i < fTs.count(); ++i) { 2098 SkDebugf(" [o=%d %1.9g (%1.9g,%1.9g) w=%d]", fTs[i].fOther->fID, 2099 fTs[i].fT, xAtT(&fTs[i]), yAtT(&fTs[i]), fTs[i].fWindValue); 2100 } 2101 SkDebugf("\n"); 2102 } 2103#endif 2104 2105#if DEBUG_ACTIVE_SPANS 2106 void debugShowActiveSpans(int contourID, int segmentIndex) { 2107 if (done()) { 2108 return; 2109 } 2110 for (int i = 0; i < fTs.count(); ++i) { 2111 if (fTs[i].fDone) { 2112 continue; 2113 } 2114 SkDebugf("%s contour=%d segment=%d (%d)", __FUNCTION__, contourID, 2115 segmentIndex, fID); 2116 SkDebugf(" (%1.9g,%1.9g", fPts[0].fX, fPts[0].fY); 2117 for (int vIndex = 1; vIndex <= fVerb; ++vIndex) { 2118 SkDebugf(" %1.9g,%1.9g", fPts[vIndex].fX, fPts[vIndex].fY); 2119 } 2120 const Span* span = &fTs[i]; 2121 SkDebugf(") fT=%d (%1.9g) (%1.9g,%1.9g)", i, fTs[i].fT, 2122 xAtT(span), yAtT(i)); 2123 const Segment* other = fTs[i].fOther; 2124 SkDebugf(" other=%d otherT=%1.9g otherIndex=%d", other->fID, 2125 fTs[i].fOtherT, fTs[i].fOtherIndex); 2126 SkDebugf(" windSum=%d windValue=%d\n", fTs[i].fWindSum, 2127 fTs[i].fWindValue); 2128 } 2129 } 2130#endif 2131 2132#if DEBUG_SORT 2133 void debugShowSort(const SkTDArray<Angle*>& angles, int first, 2134 int contourWinding, int sumWinding) { 2135 SkASSERT(angles[first]->segment() == this); 2136 bool doBump = angles[first]->firstBump(sumWinding); 2137 bool insideContour = contourWinding && contourWinding * sumWinding < 0; 2138 int windSum = insideContour ? contourWinding : sumWinding; 2139 int lastSum = windSum; 2140 if (insideContour || doBump) { 2141 windSum -= windBump(angles[first]); 2142 } else { 2143 lastSum += windBump(angles[first]); 2144 } 2145 int index = first; 2146 bool firstTime = true; 2147 do { 2148 const Angle& angle = *angles[index]; 2149 const Segment& segment = *angle.segment(); 2150 int start = angle.start(); 2151 int end = angle.end(); 2152 const Span& sSpan = segment.fTs[start]; 2153 const Span& eSpan = segment.fTs[end]; 2154 const Span& mSpan = segment.fTs[SkMin32(start, end)]; 2155 if (firstTime) { 2156 firstTime = false; 2157 } else { 2158 lastSum = windSum; 2159 windSum -= segment.windBump(&angle); 2160 } 2161 SkDebugf("%s [%d] id=%d start=%d (%1.9g,%,1.9g) end=%d (%1.9g,%,1.9g)" 2162 " sign=%d windValue=%d winding: %d->%d (max=%d) done=%d\n", 2163 __FUNCTION__, index, segment.fID, start, segment.xAtT(&sSpan), 2164 segment.yAtT(&sSpan), end, segment.xAtT(&eSpan), 2165 segment.yAtT(&eSpan), angle.sign(), mSpan.fWindValue, 2166 lastSum, windSum, abs(lastSum) > abs(windSum) ? lastSum : 2167 windSum, mSpan.fDone); 2168 ++index; 2169 if (index == angles.count()) { 2170 index = 0; 2171 } 2172 } while (index != first); 2173 } 2174#endif 2175 2176private: 2177 const SkPoint* fPts; 2178 SkPath::Verb fVerb; 2179 Bounds fBounds; 2180 SkTDArray<Span> fTs; // two or more (always includes t=0 t=1) 2181 int fDoneSpans; // used for quick check that segment is finished 2182#if DEBUG_DUMP 2183 int fID; 2184#endif 2185}; 2186 2187class Contour; 2188 2189struct Coincidence { 2190 Contour* fContours[2]; 2191 int fSegments[2]; 2192 double fTs[2][2]; 2193}; 2194 2195class Contour { 2196public: 2197 Contour() { 2198 reset(); 2199#if DEBUG_DUMP 2200 fID = ++gContourID; 2201#endif 2202 } 2203 2204 bool operator<(const Contour& rh) const { 2205 return fBounds.fTop == rh.fBounds.fTop 2206 ? fBounds.fLeft < rh.fBounds.fLeft 2207 : fBounds.fTop < rh.fBounds.fTop; 2208 } 2209 2210 void addCoincident(int index, Contour* other, int otherIndex, 2211 const Intersections& ts, bool swap) { 2212 Coincidence& coincidence = *fCoincidences.append(); 2213 coincidence.fContours[0] = this; 2214 coincidence.fContours[1] = other; 2215 coincidence.fSegments[0] = index; 2216 coincidence.fSegments[1] = otherIndex; 2217 coincidence.fTs[swap][0] = ts.fT[0][0]; 2218 coincidence.fTs[swap][1] = ts.fT[0][1]; 2219 coincidence.fTs[!swap][0] = ts.fT[1][0]; 2220 coincidence.fTs[!swap][1] = ts.fT[1][1]; 2221 } 2222 2223 void addCross(const Contour* crosser) { 2224#ifdef DEBUG_CROSS 2225 for (int index = 0; index < fCrosses.count(); ++index) { 2226 SkASSERT(fCrosses[index] != crosser); 2227 } 2228#endif 2229 *fCrosses.append() = crosser; 2230 } 2231 2232 void addCubic(const SkPoint pts[4]) { 2233 fSegments.push_back().addCubic(pts); 2234 fContainsCurves = true; 2235 } 2236 2237 int addLine(const SkPoint pts[2]) { 2238 fSegments.push_back().addLine(pts); 2239 return fSegments.count(); 2240 } 2241 2242 void addOtherT(int segIndex, int tIndex, double otherT, int otherIndex) { 2243 fSegments[segIndex].addOtherT(tIndex, otherT, otherIndex); 2244 } 2245 2246 int addQuad(const SkPoint pts[3]) { 2247 fSegments.push_back().addQuad(pts); 2248 fContainsCurves = true; 2249 return fSegments.count(); 2250 } 2251 2252 int addT(int segIndex, double newT, Contour* other, int otherIndex) { 2253 containsIntercepts(); 2254 return fSegments[segIndex].addT(newT, &other->fSegments[otherIndex]); 2255 } 2256 2257 const Bounds& bounds() const { 2258 return fBounds; 2259 } 2260 2261 void complete() { 2262 setBounds(); 2263 fContainsIntercepts = false; 2264 } 2265 2266 void containsIntercepts() { 2267 fContainsIntercepts = true; 2268 } 2269 2270 const Segment* crossedSegment(const SkPoint& basePt, SkScalar& bestY, 2271 int &tIndex, double& hitT) { 2272 int segmentCount = fSegments.count(); 2273 const Segment* bestSegment = NULL; 2274 for (int test = 0; test < segmentCount; ++test) { 2275 Segment* testSegment = &fSegments[test]; 2276 const SkRect& bounds = testSegment->bounds(); 2277 if (bounds.fTop < bestY) { 2278 continue; 2279 } 2280 if (bounds.fTop > basePt.fY) { 2281 continue; 2282 } 2283 if (bounds.fLeft > basePt.fX) { 2284 continue; 2285 } 2286 if (bounds.fRight < basePt.fX) { 2287 continue; 2288 } 2289 double testHitT; 2290 int testT = testSegment->crossedSpan(basePt, bestY, testHitT); 2291 if (testT >= 0) { 2292 bestSegment = testSegment; 2293 tIndex = testT; 2294 hitT = testHitT; 2295 } 2296 } 2297 return bestSegment; 2298 } 2299 2300 bool crosses(const Contour* crosser) const { 2301 for (int index = 0; index < fCrosses.count(); ++index) { 2302 if (fCrosses[index] == crosser) { 2303 return true; 2304 } 2305 } 2306 return false; 2307 } 2308 2309 void findTooCloseToCall(int winding) { 2310 int segmentCount = fSegments.count(); 2311 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 2312 fSegments[sIndex].findTooCloseToCall(winding); 2313 } 2314 } 2315 2316 void fixOtherTIndex() { 2317 int segmentCount = fSegments.count(); 2318 for (int sIndex = 0; sIndex < segmentCount; ++sIndex) { 2319 fSegments[sIndex].fixOtherTIndex(); 2320 } 2321 } 2322 2323 void reset() { 2324 fSegments.reset(); 2325 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 2326 fContainsCurves = fContainsIntercepts = false; 2327 fWindingSum = SK_MinS32; 2328 } 2329 2330 void resolveCoincidence(int winding) { 2331 int count = fCoincidences.count(); 2332 for (int index = 0; index < count; ++index) { 2333 Coincidence& coincidence = fCoincidences[index]; 2334 Contour* thisContour = coincidence.fContours[0]; 2335 Contour* otherContour = coincidence.fContours[1]; 2336 int thisIndex = coincidence.fSegments[0]; 2337 int otherIndex = coincidence.fSegments[1]; 2338 Segment& thisOne = thisContour->fSegments[thisIndex]; 2339 Segment& other = otherContour->fSegments[otherIndex]; 2340 #if DEBUG_CONCIDENT 2341 thisOne.debugShowTs(); 2342 other.debugShowTs(); 2343 #endif 2344 double startT = coincidence.fTs[0][0]; 2345 double endT = coincidence.fTs[0][1]; 2346 if (startT > endT) { 2347 SkTSwap<double>(startT, endT); 2348 } 2349 SkASSERT(endT - startT >= FLT_EPSILON); 2350 double oStartT = coincidence.fTs[1][0]; 2351 double oEndT = coincidence.fTs[1][1]; 2352 if (oStartT > oEndT) { 2353 SkTSwap<double>(oStartT, oEndT); 2354 } 2355 SkASSERT(oEndT - oStartT >= FLT_EPSILON); 2356 if (winding > 0 || thisOne.cancels(other)) { 2357 // make sure startT and endT have t entries 2358 if (thisOne.isMissing(startT) || other.isMissing(oEndT)) { 2359 thisOne.addTPair(startT, other, oEndT); 2360 } 2361 if (thisOne.isMissing(endT) || other.isMissing(oStartT)) { 2362 other.addTPair(oStartT, thisOne, endT); 2363 } 2364 thisOne.addTCancel(startT, endT, other, oStartT, oEndT); 2365 } else { 2366 if (thisOne.isMissing(startT) || other.isMissing(oStartT)) { 2367 thisOne.addTPair(startT, other, oStartT); 2368 } 2369 if (thisOne.isMissing(endT) || other.isMissing(oEndT)) { 2370 other.addTPair(oEndT, thisOne, endT); 2371 } 2372 thisOne.addTCoincident(startT, endT, other, oStartT, oEndT); 2373 } 2374 #if DEBUG_CONCIDENT 2375 thisOne.debugShowTs(); 2376 other.debugShowTs(); 2377 #endif 2378 } 2379 } 2380 2381 const SkTArray<Segment>& segments() { 2382 return fSegments; 2383 } 2384 2385 void setWinding(int winding) { 2386 SkASSERT(fWindingSum < 0 || fWindingSum == winding); 2387 fWindingSum = winding; 2388 } 2389 2390 // OPTIMIZATION: feel pretty uneasy about this. It seems like once again 2391 // we need to sort and walk edges in y, but that on the surface opens the 2392 // same can of worms as before. But then, this is a rough sort based on 2393 // segments' top, and not a true sort, so it could be ameniable to regular 2394 // sorting instead of linear searching. Still feel like I'm missing something 2395 Segment* topSegment(SkScalar& bestY) { 2396 int segmentCount = fSegments.count(); 2397 SkASSERT(segmentCount > 0); 2398 int best = -1; 2399 Segment* bestSegment = NULL; 2400 while (++best < segmentCount) { 2401 Segment* testSegment = &fSegments[best]; 2402 if (testSegment->done()) { 2403 continue; 2404 } 2405 bestSegment = testSegment; 2406 break; 2407 } 2408 if (!bestSegment) { 2409 return NULL; 2410 } 2411 SkScalar bestTop = bestSegment->activeTop(); 2412 for (int test = best + 1; test < segmentCount; ++test) { 2413 Segment* testSegment = &fSegments[test]; 2414 if (testSegment->done()) { 2415 continue; 2416 } 2417 if (testSegment->bounds().fTop > bestTop) { 2418 continue; 2419 } 2420 SkScalar testTop = testSegment->activeTop(); 2421 if (bestTop > testTop) { 2422 bestTop = testTop; 2423 bestSegment = testSegment; 2424 } 2425 } 2426 bestY = bestTop; 2427 return bestSegment; 2428 } 2429 2430 int updateSegment(int index, const SkPoint* pts) { 2431 Segment& segment = fSegments[index]; 2432 segment.updatePts(pts); 2433 return segment.verb() + 1; 2434 } 2435 2436 int windSum() { 2437 if (fWindingSum >= 0) { 2438 return fWindingSum; 2439 } 2440 // check peers 2441 int count = fCrosses.count(); 2442 for (int index = 0; index < count; ++index) { 2443 const Contour* crosser = fCrosses[index]; 2444 if (0 <= crosser->fWindingSum) { 2445 fWindingSum = crosser->fWindingSum; 2446 break; 2447 } 2448 } 2449 return fWindingSum; 2450 } 2451 2452#if DEBUG_TEST 2453 SkTArray<Segment>& debugSegments() { 2454 return fSegments; 2455 } 2456#endif 2457 2458#if DEBUG_DUMP 2459 void dump() { 2460 int i; 2461 const char className[] = "Contour"; 2462 const int tab = 4; 2463 SkDebugf("%s %p (contour=%d)\n", className, this, fID); 2464 for (i = 0; i < fSegments.count(); ++i) { 2465 SkDebugf("%*s.fSegments[%d]:\n", tab + sizeof(className), 2466 className, i); 2467 fSegments[i].dump(); 2468 } 2469 SkDebugf("%*s.fBounds=(l:%1.9g, t:%1.9g r:%1.9g, b:%1.9g)\n", 2470 tab + sizeof(className), className, 2471 fBounds.fLeft, fBounds.fTop, 2472 fBounds.fRight, fBounds.fBottom); 2473 SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), 2474 className, fContainsIntercepts); 2475 SkDebugf("%*s.fContainsCurves=%d\n", tab + sizeof(className), 2476 className, fContainsCurves); 2477 } 2478#endif 2479 2480#if DEBUG_ACTIVE_SPANS 2481 void debugShowActiveSpans() { 2482 for (int index = 0; index < fSegments.count(); ++index) { 2483 fSegments[index].debugShowActiveSpans(fID, index); 2484 } 2485 } 2486#endif 2487 2488protected: 2489 void setBounds() { 2490 int count = fSegments.count(); 2491 if (count == 0) { 2492 SkDebugf("%s empty contour\n", __FUNCTION__); 2493 SkASSERT(0); 2494 // FIXME: delete empty contour? 2495 return; 2496 } 2497 fBounds = fSegments.front().bounds(); 2498 for (int index = 1; index < count; ++index) { 2499 fBounds.add(fSegments[index].bounds()); 2500 } 2501 } 2502 2503private: 2504 SkTArray<Segment> fSegments; 2505 SkTDArray<Coincidence> fCoincidences; 2506 SkTDArray<const Contour*> fCrosses; 2507 Bounds fBounds; 2508 bool fContainsIntercepts; 2509 bool fContainsCurves; 2510 int fWindingSum; // initial winding number outside 2511#if DEBUG_DUMP 2512 int fID; 2513#endif 2514}; 2515 2516class EdgeBuilder { 2517public: 2518 2519EdgeBuilder(const SkPath& path, SkTArray<Contour>& contours) 2520 : fPath(path) 2521 , fCurrentContour(NULL) 2522 , fContours(contours) 2523{ 2524#if DEBUG_DUMP 2525 gContourID = 0; 2526 gSegmentID = 0; 2527#endif 2528 walk(); 2529} 2530 2531protected: 2532 2533void complete() { 2534 if (fCurrentContour && fCurrentContour->segments().count()) { 2535 fCurrentContour->complete(); 2536 fCurrentContour = NULL; 2537 } 2538} 2539 2540void walk() { 2541 // FIXME:remove once we can access path pts directly 2542 SkPath::RawIter iter(fPath); // FIXME: access path directly when allowed 2543 SkPoint pts[4]; 2544 SkPath::Verb verb; 2545 do { 2546 verb = iter.next(pts); 2547 *fPathVerbs.append() = verb; 2548 if (verb == SkPath::kMove_Verb) { 2549 *fPathPts.append() = pts[0]; 2550 } else if (verb >= SkPath::kLine_Verb && verb <= SkPath::kCubic_Verb) { 2551 fPathPts.append(verb, &pts[1]); 2552 } 2553 } while (verb != SkPath::kDone_Verb); 2554 // FIXME: end of section to remove once path pts are accessed directly 2555 2556 SkPath::Verb reducedVerb; 2557 uint8_t* verbPtr = fPathVerbs.begin(); 2558 const SkPoint* pointsPtr = fPathPts.begin(); 2559 const SkPoint* finalCurveStart = NULL; 2560 const SkPoint* finalCurveEnd = NULL; 2561 while ((verb = (SkPath::Verb) *verbPtr++) != SkPath::kDone_Verb) { 2562 switch (verb) { 2563 case SkPath::kMove_Verb: 2564 complete(); 2565 if (!fCurrentContour) { 2566 fCurrentContour = fContours.push_back_n(1); 2567 finalCurveEnd = pointsPtr++; 2568 *fExtra.append() = -1; // start new contour 2569 } 2570 continue; 2571 case SkPath::kLine_Verb: 2572 // skip degenerate points 2573 if (pointsPtr[-1].fX != pointsPtr[0].fX 2574 || pointsPtr[-1].fY != pointsPtr[0].fY) { 2575 fCurrentContour->addLine(&pointsPtr[-1]); 2576 } 2577 break; 2578 case SkPath::kQuad_Verb: 2579 2580 reducedVerb = QuadReduceOrder(&pointsPtr[-1], fReducePts); 2581 if (reducedVerb == 0) { 2582 break; // skip degenerate points 2583 } 2584 if (reducedVerb == 1) { 2585 *fExtra.append() = 2586 fCurrentContour->addLine(fReducePts.end() - 2); 2587 break; 2588 } 2589 fCurrentContour->addQuad(&pointsPtr[-1]); 2590 break; 2591 case SkPath::kCubic_Verb: 2592 reducedVerb = CubicReduceOrder(&pointsPtr[-1], fReducePts); 2593 if (reducedVerb == 0) { 2594 break; // skip degenerate points 2595 } 2596 if (reducedVerb == 1) { 2597 *fExtra.append() = 2598 fCurrentContour->addLine(fReducePts.end() - 2); 2599 break; 2600 } 2601 if (reducedVerb == 2) { 2602 *fExtra.append() = 2603 fCurrentContour->addQuad(fReducePts.end() - 3); 2604 break; 2605 } 2606 fCurrentContour->addCubic(&pointsPtr[-1]); 2607 break; 2608 case SkPath::kClose_Verb: 2609 SkASSERT(fCurrentContour); 2610 if (finalCurveStart && finalCurveEnd 2611 && *finalCurveStart != *finalCurveEnd) { 2612 *fReducePts.append() = *finalCurveStart; 2613 *fReducePts.append() = *finalCurveEnd; 2614 *fExtra.append() = 2615 fCurrentContour->addLine(fReducePts.end() - 2); 2616 } 2617 complete(); 2618 continue; 2619 default: 2620 SkDEBUGFAIL("bad verb"); 2621 return; 2622 } 2623 finalCurveStart = &pointsPtr[verb - 1]; 2624 pointsPtr += verb; 2625 SkASSERT(fCurrentContour); 2626 } 2627 complete(); 2628 if (fCurrentContour && !fCurrentContour->segments().count()) { 2629 fContours.pop_back(); 2630 } 2631 // correct pointers in contours since fReducePts may have moved as it grew 2632 int cIndex = 0; 2633 int extraCount = fExtra.count(); 2634 SkASSERT(extraCount == 0 || fExtra[0] == -1); 2635 int eIndex = 0; 2636 int rIndex = 0; 2637 while (++eIndex < extraCount) { 2638 int offset = fExtra[eIndex]; 2639 if (offset < 0) { 2640 ++cIndex; 2641 continue; 2642 } 2643 fCurrentContour = &fContours[cIndex]; 2644 rIndex += fCurrentContour->updateSegment(offset - 1, 2645 &fReducePts[rIndex]); 2646 } 2647 fExtra.reset(); // we're done with this 2648} 2649 2650private: 2651 const SkPath& fPath; 2652 SkTDArray<SkPoint> fPathPts; // FIXME: point directly to path pts instead 2653 SkTDArray<uint8_t> fPathVerbs; // FIXME: remove 2654 Contour* fCurrentContour; 2655 SkTArray<Contour>& fContours; 2656 SkTDArray<SkPoint> fReducePts; // segments created on the fly 2657 SkTDArray<int> fExtra; // -1 marks new contour, > 0 offsets into contour 2658}; 2659 2660class Work { 2661public: 2662 enum SegmentType { 2663 kHorizontalLine_Segment = -1, 2664 kVerticalLine_Segment = 0, 2665 kLine_Segment = SkPath::kLine_Verb, 2666 kQuad_Segment = SkPath::kQuad_Verb, 2667 kCubic_Segment = SkPath::kCubic_Verb, 2668 }; 2669 2670 void addCoincident(Work& other, const Intersections& ts, bool swap) { 2671 fContour->addCoincident(fIndex, other.fContour, other.fIndex, ts, swap); 2672 } 2673 2674 // FIXME: does it make sense to write otherIndex now if we're going to 2675 // fix it up later? 2676 void addOtherT(int index, double otherT, int otherIndex) { 2677 fContour->addOtherT(fIndex, index, otherT, otherIndex); 2678 } 2679 2680 // Avoid collapsing t values that are close to the same since 2681 // we walk ts to describe consecutive intersections. Since a pair of ts can 2682 // be nearly equal, any problems caused by this should be taken care 2683 // of later. 2684 // On the edge or out of range values are negative; add 2 to get end 2685 int addT(double newT, const Work& other) { 2686 return fContour->addT(fIndex, newT, other.fContour, other.fIndex); 2687 } 2688 2689 bool advance() { 2690 return ++fIndex < fLast; 2691 } 2692 2693 SkScalar bottom() const { 2694 return bounds().fBottom; 2695 } 2696 2697 const Bounds& bounds() const { 2698 return fContour->segments()[fIndex].bounds(); 2699 } 2700 2701 const SkPoint* cubic() const { 2702 return fCubic; 2703 } 2704 2705 void init(Contour* contour) { 2706 fContour = contour; 2707 fIndex = 0; 2708 fLast = contour->segments().count(); 2709 } 2710 2711 bool isAdjacent(const Work& next) { 2712 return fContour == next.fContour && fIndex + 1 == next.fIndex; 2713 } 2714 2715 bool isFirstLast(const Work& next) { 2716 return fContour == next.fContour && fIndex == 0 2717 && next.fIndex == fLast - 1; 2718 } 2719 2720 SkScalar left() const { 2721 return bounds().fLeft; 2722 } 2723 2724 void promoteToCubic() { 2725 fCubic[0] = pts()[0]; 2726 fCubic[2] = pts()[1]; 2727 fCubic[3] = pts()[2]; 2728 fCubic[1].fX = (fCubic[0].fX + fCubic[2].fX * 2) / 3; 2729 fCubic[1].fY = (fCubic[0].fY + fCubic[2].fY * 2) / 3; 2730 fCubic[2].fX = (fCubic[3].fX + fCubic[2].fX * 2) / 3; 2731 fCubic[2].fY = (fCubic[3].fY + fCubic[2].fY * 2) / 3; 2732 } 2733 2734 const SkPoint* pts() const { 2735 return fContour->segments()[fIndex].pts(); 2736 } 2737 2738 SkScalar right() const { 2739 return bounds().fRight; 2740 } 2741 2742 ptrdiff_t segmentIndex() const { 2743 return fIndex; 2744 } 2745 2746 SegmentType segmentType() const { 2747 const Segment& segment = fContour->segments()[fIndex]; 2748 SegmentType type = (SegmentType) segment.verb(); 2749 if (type != kLine_Segment) { 2750 return type; 2751 } 2752 if (segment.isHorizontal()) { 2753 return kHorizontalLine_Segment; 2754 } 2755 if (segment.isVertical()) { 2756 return kVerticalLine_Segment; 2757 } 2758 return kLine_Segment; 2759 } 2760 2761 bool startAfter(const Work& after) { 2762 fIndex = after.fIndex; 2763 return advance(); 2764 } 2765 2766 SkScalar top() const { 2767 return bounds().fTop; 2768 } 2769 2770 SkPath::Verb verb() const { 2771 return fContour->segments()[fIndex].verb(); 2772 } 2773 2774 SkScalar x() const { 2775 return bounds().fLeft; 2776 } 2777 2778 bool xFlipped() const { 2779 return x() != pts()[0].fX; 2780 } 2781 2782 SkScalar y() const { 2783 return bounds().fTop; 2784 } 2785 2786 bool yFlipped() const { 2787 return y() != pts()[0].fY; 2788 } 2789 2790protected: 2791 Contour* fContour; 2792 SkPoint fCubic[4]; 2793 int fIndex; 2794 int fLast; 2795}; 2796 2797#if DEBUG_ADD_INTERSECTING_TS 2798static void debugShowLineIntersection(int pts, const Work& wt, 2799 const Work& wn, const double wtTs[2], const double wnTs[2]) { 2800 if (!pts) { 2801 SkDebugf("%s no intersect (%1.9g,%1.9g %1.9g,%1.9g) (%1.9g,%1.9g %1.9g,%1.9g)\n", 2802 __FUNCTION__, wt.pts()[0].fX, wt.pts()[0].fY, 2803 wt.pts()[1].fX, wt.pts()[1].fY, wn.pts()[0].fX, wn.pts()[0].fY, 2804 wn.pts()[1].fX, wn.pts()[1].fY); 2805 return; 2806 } 2807 SkPoint wtOutPt, wnOutPt; 2808 LineXYAtT(wt.pts(), wtTs[0], &wtOutPt); 2809 LineXYAtT(wn.pts(), wnTs[0], &wnOutPt); 2810 SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g)", 2811 __FUNCTION__, 2812 wtTs[0], wt.pts()[0].fX, wt.pts()[0].fY, 2813 wt.pts()[1].fX, wt.pts()[1].fY, wtOutPt.fX, wtOutPt.fY); 2814 if (pts == 2) { 2815 SkDebugf(" wtTs[1]=%g", wtTs[1]); 2816 } 2817 SkDebugf(" wnTs[0]=%g (%g,%g, %g,%g) (%g,%g)", 2818 wnTs[0], wn.pts()[0].fX, wn.pts()[0].fY, 2819 wn.pts()[1].fX, wn.pts()[1].fY, wnOutPt.fX, wnOutPt.fY); 2820 if (pts == 2) { 2821 SkDebugf(" wnTs[1]=%g", wnTs[1]); 2822 } 2823 SkDebugf("\n"); 2824} 2825#else 2826static void debugShowLineIntersection(int , const Work& , 2827 const Work& , const double [2], const double [2]) { 2828} 2829#endif 2830 2831static bool addIntersectTs(Contour* test, Contour* next) { 2832 2833 if (test != next) { 2834 if (test->bounds().fBottom < next->bounds().fTop) { 2835 return false; 2836 } 2837 if (!Bounds::Intersects(test->bounds(), next->bounds())) { 2838 return true; 2839 } 2840 } 2841 Work wt; 2842 wt.init(test); 2843 bool foundCommonContour = test == next; 2844 do { 2845 Work wn; 2846 wn.init(next); 2847 if (test == next && !wn.startAfter(wt)) { 2848 continue; 2849 } 2850 do { 2851 if (!Bounds::Intersects(wt.bounds(), wn.bounds())) { 2852 continue; 2853 } 2854 int pts; 2855 Intersections ts; 2856 bool swap = false; 2857 switch (wt.segmentType()) { 2858 case Work::kHorizontalLine_Segment: 2859 swap = true; 2860 switch (wn.segmentType()) { 2861 case Work::kHorizontalLine_Segment: 2862 case Work::kVerticalLine_Segment: 2863 case Work::kLine_Segment: { 2864 pts = HLineIntersect(wn.pts(), wt.left(), 2865 wt.right(), wt.y(), wt.xFlipped(), ts); 2866 debugShowLineIntersection(pts, wt, wn, 2867 ts.fT[1], ts.fT[0]); 2868 break; 2869 } 2870 case Work::kQuad_Segment: { 2871 pts = HQuadIntersect(wn.pts(), wt.left(), 2872 wt.right(), wt.y(), wt.xFlipped(), ts); 2873 break; 2874 } 2875 case Work::kCubic_Segment: { 2876 pts = HCubicIntersect(wn.pts(), wt.left(), 2877 wt.right(), wt.y(), wt.xFlipped(), ts); 2878 break; 2879 } 2880 default: 2881 SkASSERT(0); 2882 } 2883 break; 2884 case Work::kVerticalLine_Segment: 2885 swap = true; 2886 switch (wn.segmentType()) { 2887 case Work::kHorizontalLine_Segment: 2888 case Work::kVerticalLine_Segment: 2889 case Work::kLine_Segment: { 2890 pts = VLineIntersect(wn.pts(), wt.top(), 2891 wt.bottom(), wt.x(), wt.yFlipped(), ts); 2892 debugShowLineIntersection(pts, wt, wn, 2893 ts.fT[1], ts.fT[0]); 2894 break; 2895 } 2896 case Work::kQuad_Segment: { 2897 pts = VQuadIntersect(wn.pts(), wt.top(), 2898 wt.bottom(), wt.x(), wt.yFlipped(), ts); 2899 break; 2900 } 2901 case Work::kCubic_Segment: { 2902 pts = VCubicIntersect(wn.pts(), wt.top(), 2903 wt.bottom(), wt.x(), wt.yFlipped(), ts); 2904 break; 2905 } 2906 default: 2907 SkASSERT(0); 2908 } 2909 break; 2910 case Work::kLine_Segment: 2911 switch (wn.segmentType()) { 2912 case Work::kHorizontalLine_Segment: 2913 pts = HLineIntersect(wt.pts(), wn.left(), 2914 wn.right(), wn.y(), wn.xFlipped(), ts); 2915 debugShowLineIntersection(pts, wt, wn, 2916 ts.fT[1], ts.fT[0]); 2917 break; 2918 case Work::kVerticalLine_Segment: 2919 pts = VLineIntersect(wt.pts(), wn.top(), 2920 wn.bottom(), wn.x(), wn.yFlipped(), ts); 2921 debugShowLineIntersection(pts, wt, wn, 2922 ts.fT[1], ts.fT[0]); 2923 break; 2924 case Work::kLine_Segment: { 2925 pts = LineIntersect(wt.pts(), wn.pts(), ts); 2926 debugShowLineIntersection(pts, wt, wn, 2927 ts.fT[1], ts.fT[0]); 2928 break; 2929 } 2930 case Work::kQuad_Segment: { 2931 swap = true; 2932 pts = QuadLineIntersect(wn.pts(), wt.pts(), ts); 2933 break; 2934 } 2935 case Work::kCubic_Segment: { 2936 swap = true; 2937 pts = CubicLineIntersect(wn.pts(), wt.pts(), ts); 2938 break; 2939 } 2940 default: 2941 SkASSERT(0); 2942 } 2943 break; 2944 case Work::kQuad_Segment: 2945 switch (wn.segmentType()) { 2946 case Work::kHorizontalLine_Segment: 2947 pts = HQuadIntersect(wt.pts(), wn.left(), 2948 wn.right(), wn.y(), wn.xFlipped(), ts); 2949 break; 2950 case Work::kVerticalLine_Segment: 2951 pts = VQuadIntersect(wt.pts(), wn.top(), 2952 wn.bottom(), wn.x(), wn.yFlipped(), ts); 2953 break; 2954 case Work::kLine_Segment: { 2955 pts = QuadLineIntersect(wt.pts(), wn.pts(), ts); 2956 break; 2957 } 2958 case Work::kQuad_Segment: { 2959 pts = QuadIntersect(wt.pts(), wn.pts(), ts); 2960 break; 2961 } 2962 case Work::kCubic_Segment: { 2963 wt.promoteToCubic(); 2964 pts = CubicIntersect(wt.cubic(), wn.pts(), ts); 2965 break; 2966 } 2967 default: 2968 SkASSERT(0); 2969 } 2970 break; 2971 case Work::kCubic_Segment: 2972 switch (wn.segmentType()) { 2973 case Work::kHorizontalLine_Segment: 2974 pts = HCubicIntersect(wt.pts(), wn.left(), 2975 wn.right(), wn.y(), wn.xFlipped(), ts); 2976 break; 2977 case Work::kVerticalLine_Segment: 2978 pts = VCubicIntersect(wt.pts(), wn.top(), 2979 wn.bottom(), wn.x(), wn.yFlipped(), ts); 2980 break; 2981 case Work::kLine_Segment: { 2982 pts = CubicLineIntersect(wt.pts(), wn.pts(), ts); 2983 break; 2984 } 2985 case Work::kQuad_Segment: { 2986 wn.promoteToCubic(); 2987 pts = CubicIntersect(wt.pts(), wn.cubic(), ts); 2988 break; 2989 } 2990 case Work::kCubic_Segment: { 2991 pts = CubicIntersect(wt.pts(), wn.pts(), ts); 2992 break; 2993 } 2994 default: 2995 SkASSERT(0); 2996 } 2997 break; 2998 default: 2999 SkASSERT(0); 3000 } 3001 if (!foundCommonContour && pts > 0) { 3002 test->addCross(next); 3003 next->addCross(test); 3004 foundCommonContour = true; 3005 } 3006 // in addition to recording T values, record matching segment 3007 if (pts == 2 && wn.segmentType() <= Work::kLine_Segment 3008 && wt.segmentType() <= Work::kLine_Segment) { 3009 wt.addCoincident(wn, ts, swap); 3010 continue; 3011 } 3012 for (int pt = 0; pt < pts; ++pt) { 3013 SkASSERT(ts.fT[0][pt] >= 0 && ts.fT[0][pt] <= 1); 3014 SkASSERT(ts.fT[1][pt] >= 0 && ts.fT[1][pt] <= 1); 3015 int testTAt = wt.addT(ts.fT[swap][pt], wn); 3016 int nextTAt = wn.addT(ts.fT[!swap][pt], wt); 3017 wt.addOtherT(testTAt, ts.fT[!swap][pt], nextTAt); 3018 wn.addOtherT(nextTAt, ts.fT[swap][pt], testTAt); 3019 } 3020 } while (wn.advance()); 3021 } while (wt.advance()); 3022 return true; 3023} 3024 3025// resolve any coincident pairs found while intersecting, and 3026// see if coincidence is formed by clipping non-concident segments 3027static void coincidenceCheck(SkTDArray<Contour*>& contourList, int winding) { 3028 int contourCount = contourList.count(); 3029 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 3030 Contour* contour = contourList[cIndex]; 3031 contour->findTooCloseToCall(winding); 3032 } 3033 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 3034 Contour* contour = contourList[cIndex]; 3035 contour->resolveCoincidence(winding); 3036 } 3037} 3038 3039// project a ray from the top of the contour up and see if it hits anything 3040// note: when we compute line intersections, we keep track of whether 3041// two contours touch, so we need only look at contours not touching this one. 3042// OPTIMIZATION: sort contourList vertically to avoid linear walk 3043static int innerContourCheck(SkTDArray<Contour*>& contourList, 3044 Contour* baseContour, const Segment* current, int index, int endIndex) { 3045 const SkPoint& basePt = current->xyAtT(endIndex); 3046 int contourCount = contourList.count(); 3047 SkScalar bestY = SK_ScalarMin; 3048 const Segment* test = NULL; 3049 int tIndex; 3050 double tHit; 3051 bool checkCrosses = true; 3052 for (int cTest = 0; cTest < contourCount; ++cTest) { 3053 Contour* contour = contourList[cTest]; 3054 if (basePt.fY < contour->bounds().fTop) { 3055 continue; 3056 } 3057 if (bestY > contour->bounds().fBottom) { 3058 continue; 3059 } 3060 // even though the contours crossed, if spans cancel through concidence, 3061 // the contours may be not have any span links to chase, and the current 3062 // segment may be isolated. Detect this by seeing if current has 3063 // uninitialized wind sums. If so, project a ray instead of relying on 3064 // previously found intersections. 3065 if (baseContour == contour) { 3066 continue; 3067 } 3068 if (checkCrosses && baseContour->crosses(contour)) { 3069 if (current->isConnected(index, endIndex)) { 3070 continue; 3071 } 3072 checkCrosses = false; 3073 } 3074 const Segment* next = contour->crossedSegment(basePt, bestY, tIndex, tHit); 3075 if (next) { 3076 test = next; 3077 } 3078 } 3079 if (!test) { 3080 baseContour->setWinding(0); 3081 return 0; 3082 } 3083 int winding, windValue; 3084 // If the ray hit the end of a span, we need to construct the wheel of 3085 // angles to find the span closest to the ray -- even if there are just 3086 // two spokes on the wheel. 3087 if (fabs(tHit - test->t(tIndex)) < FLT_EPSILON) { 3088 SkTDArray<Angle> angles; 3089 int end = test->nextSpan(tIndex, 1); 3090 if (end < 0) { 3091 end = test->nextSpan(tIndex, -1); 3092 } 3093 test->addTwoAngles(end, tIndex, angles); 3094 test->buildAngles(tIndex, angles); 3095 SkTDArray<Angle*> sorted; 3096 // OPTIMIZATION: call a sort that, if base point is the leftmost, 3097 // returns the first counterclockwise hour before 6 o'clock, 3098 // or if the base point is rightmost, returns the first clockwise 3099 // hour after 6 o'clock 3100 sortAngles(angles, sorted); 3101#if DEBUG_SORT 3102 sorted[0]->segment()->debugShowSort(sorted, 0, 0, 0); 3103#endif 3104 // walk the sorted angle fan to find the lowest angle 3105 // above the base point. Currently, the first angle in the sorted array 3106 // is 12 noon or an earlier hour (the next counterclockwise) 3107 int count = sorted.count(); 3108 int left = -1; 3109 int mid = -1; 3110 int right = -1; 3111 bool baseMatches = test->yAtT(tIndex) == basePt.fY; 3112 for (int index = 0; index < count; ++index) { 3113 const Angle* angle = sorted[index]; 3114 if (baseMatches && angle->isHorizontal()) { 3115 continue; 3116 } 3117 double indexDx = angle->dx(); 3118 if (indexDx < 0) { 3119 left = index; 3120 } else if (indexDx > 0) { 3121 right = index; 3122 break; 3123 } else { 3124 mid = index; 3125 } 3126 } 3127 if (left < 0 && right < 0) { 3128 left = mid; 3129 } 3130 SkASSERT(left >= 0 || right >= 0); 3131 if (left < 0) { 3132 left = right; 3133 } 3134 const Angle* angle = sorted[left]; 3135 test = angle->segment(); 3136 winding = test->windSum(angle); 3137 SkASSERT(winding != SK_MinS32); 3138 windValue = test->windValue(angle); 3139 #if 0 3140 if (angle->firstBump(winding)) { 3141 winding -= test->windBump(angle); 3142 } 3143 #endif 3144#if DEBUG_WINDING 3145 SkDebugf("%s angle winding=%d windValue=%d\n", __FUNCTION__, winding, 3146 windValue); 3147#endif 3148 } else { 3149 winding = test->windSum(tIndex); 3150 SkASSERT(winding != SK_MinS32); 3151 windValue = test->windValue(tIndex); 3152#if DEBUG_WINDING 3153 SkDebugf("%s single winding=%d windValue=%d\n", __FUNCTION__, winding, 3154 windValue); 3155#endif 3156 } 3157 // see if a + change in T results in a +/- change in X (compute x'(T)) 3158 SkScalar dx = (*SegmentDXAtT[test->verb()])(test->pts(), tHit); 3159#if DEBUG_WINDING 3160 SkDebugf("%s dx=%1.9g\n", __FUNCTION__, dx); 3161#endif 3162 SkASSERT(dx != 0); 3163 if (winding * dx > 0) { // if same signs, result is negative 3164 winding += dx > 0 ? -windValue : windValue; 3165#if DEBUG_WINDING 3166 SkDebugf("%s final winding=%d\n", __FUNCTION__, winding); 3167#endif 3168 } 3169 start here; 3170 // we're broken because we find a vertical span 3171 // also, does it make sense to compute a contour's winding? Won't it 3172 // depend on coincidence and (e.g. a figure eight) self intersection? 3173 // (hopefully no one uses this) so remove it 3174 baseContour->setWinding(winding); 3175 return winding; 3176} 3177 3178// OPTIMIZATION: not crazy about linear search here to find top active y. 3179// seems like we should break down and do the sort, or maybe sort each 3180// contours' segments? 3181// Once the segment array is built, there's no reason I can think of not to 3182// sort it in Y. hmmm 3183// FIXME: return the contour found to pass to inner contour check 3184static Segment* findTopContour(SkTDArray<Contour*>& contourList, 3185 Contour*& topContour) { 3186 int contourCount = contourList.count(); 3187 int cIndex = 0; 3188 Segment* topStart; 3189 SkScalar bestY = SK_ScalarMax; 3190 Contour* contour; 3191 do { 3192 contour = contourList[cIndex]; 3193 topStart = contour->topSegment(bestY); 3194 } while (!topStart && ++cIndex < contourCount); 3195 if (!topStart) { 3196 return NULL; 3197 } 3198 topContour = contour; 3199 while (++cIndex < contourCount) { 3200 contour = contourList[cIndex]; 3201 if (bestY < contour->bounds().fTop) { 3202 continue; 3203 } 3204 SkScalar testY = SK_ScalarMax; 3205 Segment* test = contour->topSegment(testY); 3206 if (!test || bestY <= testY) { 3207 continue; 3208 } 3209 topContour = contour; 3210 topStart = test; 3211 bestY = testY; 3212 } 3213 return topStart; 3214} 3215 3216static Segment* findChase(SkTDArray<Span*>& chase, int& tIndex, int& endIndex, 3217 int contourWinding) { 3218 while (chase.count()) { 3219 Span* span = chase[chase.count() - 1]; 3220 const Span& backPtr = span->fOther->span(span->fOtherIndex); 3221 Segment* segment = backPtr.fOther; 3222 tIndex = backPtr.fOtherIndex; 3223 SkTDArray<Angle> angles; 3224 int done = 0; 3225 if (segment->activeAngle(tIndex, done, angles)) { 3226 Angle* last = angles.end() - 1; 3227 tIndex = last->start(); 3228 endIndex = last->end(); 3229 return last->segment(); 3230 } 3231 if (done == angles.count()) { 3232 chase.pop(&span); 3233 continue; 3234 } 3235 SkTDArray<Angle*> sorted; 3236 sortAngles(angles, sorted); 3237 // find first angle, initialize winding to computed fWindSum 3238 int firstIndex = -1; 3239 const Angle* angle; 3240 int spanWinding; 3241 do { 3242 angle = sorted[++firstIndex]; 3243 spanWinding = angle->segment()->windSum(angle); 3244 } while (spanWinding == SK_MinS32); 3245 #if DEBUG_SORT 3246 angle->segment()->debugShowSort(sorted, firstIndex, contourWinding, 3247 spanWinding); 3248 #endif 3249 if (angle->firstBump(spanWinding)) { 3250 spanWinding -= angle->segment()->windBump(angle); 3251 } 3252 // we care about first sign and whether wind sum indicates this 3253 // edge is inside or outside. Maybe need to pass span winding 3254 // or first winding or something into this function? 3255 // advance to first undone angle, then return it and winding 3256 // (to set whether edges are active or not) 3257 int nextIndex = firstIndex + 1; 3258 int angleCount = sorted.count(); 3259 int lastIndex = firstIndex != 0 ? firstIndex : angleCount; 3260 do { 3261 SkASSERT(nextIndex != firstIndex); 3262 if (nextIndex == angleCount) { 3263 nextIndex = 0; 3264 } 3265 const Angle* angle = sorted[nextIndex]; 3266 segment = angle->segment(); 3267 int maxWinding = spanWinding; 3268 spanWinding -= segment->windBump(angle); 3269 if (maxWinding * spanWinding < 0) { 3270 SkDebugf("%s flipped sign %d %d\n", __FUNCTION__, maxWinding, spanWinding); 3271 } 3272 tIndex = angle->start(); 3273 endIndex = angle->end(); 3274 int lesser = SkMin32(tIndex, endIndex); 3275 const Span& nextSpan = segment->span(lesser); 3276 if (!nextSpan.fDone) { 3277 // FIXME: this be wrong. assign startWinding if edge is in 3278 // same direction. If the direction is opposite, winding to 3279 // assign is flipped sign or +/- 1? 3280 if (abs(maxWinding) < abs(spanWinding)) { 3281 maxWinding = spanWinding; 3282 } 3283 segment->markWinding(lesser, maxWinding); 3284 break; 3285 } 3286 } while (++nextIndex != lastIndex); 3287 return segment; 3288 } 3289 return NULL; 3290} 3291 3292#if DEBUG_ACTIVE_SPANS 3293static void debugShowActiveSpans(SkTDArray<Contour*>& contourList) { 3294 for (int index = 0; index < contourList.count(); ++ index) { 3295 contourList[index]->debugShowActiveSpans(); 3296 } 3297} 3298#endif 3299 3300static bool windingIsActive(int winding, int spanWinding) { 3301 return winding * spanWinding <= 0 && abs(winding) <= abs(spanWinding) 3302 && (!winding || !spanWinding || winding == -spanWinding); 3303} 3304 3305// Each segment may have an inside or an outside. Segments contained within 3306// winding may have insides on either side, and form a contour that should be 3307// ignored. Segments that are coincident with opposing direction segments may 3308// have outsides on either side, and should also disappear. 3309// 'Normal' segments will have one inside and one outside. Subsequent connections 3310// when winding should follow the intersection direction. If more than one edge 3311// is an option, choose first edge that continues the inside. 3312 // since we start with leftmost top edge, we'll traverse through a 3313 // smaller angle counterclockwise to get to the next edge. 3314static void bridge(SkTDArray<Contour*>& contourList, SkPath& simple) { 3315 bool firstContour = true; 3316 do { 3317 Contour* topContour; 3318 Segment* topStart = findTopContour(contourList, topContour); 3319 if (!topStart) { 3320 break; 3321 } 3322 // Start at the top. Above the top is outside, below is inside. 3323 // follow edges to intersection by changing the index by direction. 3324 int index, endIndex; 3325 Segment* current = topStart->findTop(index, endIndex); 3326 int contourWinding; 3327 if (firstContour) { 3328 contourWinding = 0; 3329 firstContour = false; 3330 } else { 3331 contourWinding = innerContourCheck(contourList, topContour, current, 3332 index, endIndex); 3333#if DEBUG_WINDING 3334 SkDebugf("%s contourWinding=%d\n", __FUNCTION__, contourWinding); 3335#endif 3336 } 3337 SkPoint lastPt; 3338 bool firstTime = true; 3339 int winding = contourWinding; 3340 int spanWinding = current->spanSign(index, endIndex); 3341 int spanWindSum = current->windSum(SkMin32(index, endIndex)); 3342 if (spanWindSum != SK_MinS32) { 3343 int calcWinding = spanWindSum; 3344 if (spanWinding > 0) { 3345 // calcWinding -= spanWinding; 3346 } 3347 SkDebugf("%s *** winding=%d calcWinding=%d\n", __FUNCTION__, 3348 winding, calcWinding); 3349 winding = calcWinding; 3350 } 3351 // FIXME: needs work. While it works in limited situations, it does 3352 // not always compute winding correctly. Active should be removed and instead 3353 // the initial winding should be correctly passed in so that if the 3354 // inner contour is wound the same way, it never finds an accumulated 3355 // winding of zero. Inside 'find next', we need to look for transitions 3356 // other than zero when resolving sorted angles. 3357 bool active = windingIsActive(winding, spanWinding); 3358 SkTDArray<Span*> chaseArray; 3359 do { 3360 #if DEBUG_WINDING 3361 SkDebugf("%s active=%s winding=%d spanWinding=%d\n", 3362 __FUNCTION__, active ? "true" : "false", 3363 winding, spanWinding); 3364 #endif 3365 const SkPoint* firstPt = NULL; 3366 do { 3367 SkASSERT(!current->done()); 3368 int nextStart, nextEnd; 3369 Segment* next = current->findNext(chaseArray, 3370 firstTime, active, index, endIndex, 3371 nextStart, nextEnd, winding, spanWinding); 3372 if (!next) { 3373 break; 3374 } 3375 if (!firstPt) { 3376 firstPt = ¤t->addMoveTo(index, simple, active); 3377 } 3378 lastPt = current->addCurveTo(index, endIndex, simple, active); 3379 current = next; 3380 index = nextStart; 3381 endIndex = nextEnd; 3382 firstTime = false; 3383 } while (*firstPt != lastPt && (active || !current->done())); 3384 if (firstPt && active) { 3385 #if DEBUG_PATH_CONSTRUCTION 3386 SkDebugf("%s close\n", __FUNCTION__); 3387 #endif 3388 simple.close(); 3389 } 3390 current = findChase(chaseArray, index, endIndex, contourWinding); 3391 #if DEBUG_ACTIVE_SPANS 3392 debugShowActiveSpans(contourList); 3393 #endif 3394 if (!current) { 3395 break; 3396 } 3397 int lesser = SkMin32(index, endIndex); 3398 spanWinding = current->windSum(lesser); 3399 int spanValue = current->windValue(lesser); 3400 SkASSERT(spanWinding != SK_MinS32); 3401 #if DEBUG_WINDING 3402 SkDebugf("%s spanWinding=%d winding=%d spanValue=%d\n", 3403 __FUNCTION__, spanWinding, winding, spanValue); 3404 #endif 3405 if (abs(spanWinding) != spanValue) { 3406 winding = spanWinding; 3407 spanWinding = spanValue * SkSign32(spanWinding); 3408 winding -= spanWinding; 3409 #if DEBUG_WINDING 3410 SkDebugf("%s != spanWinding=%d winding=%d\n", __FUNCTION__, 3411 spanWinding, winding); 3412 #endif 3413 active = windingIsActive(winding, spanWinding); 3414 } else if (winding) { 3415 #if DEBUG_WINDING 3416 SkDebugf("%s ->0 contourWinding=%d winding=%d\n", __FUNCTION__, 3417 contourWinding, winding); 3418 #endif 3419 // start here; 3420 // set active=false if it was false when chase was created 3421 active = abs(winding) <= abs(spanWinding); 3422 winding = 0; 3423 } 3424 } while (true); 3425 } while (true); 3426} 3427 3428static void fixOtherTIndex(SkTDArray<Contour*>& contourList) { 3429 int contourCount = contourList.count(); 3430 for (int cTest = 0; cTest < contourCount; ++cTest) { 3431 Contour* contour = contourList[cTest]; 3432 contour->fixOtherTIndex(); 3433 } 3434} 3435 3436static void makeContourList(SkTArray<Contour>& contours, 3437 SkTDArray<Contour*>& list) { 3438 int count = contours.count(); 3439 if (count == 0) { 3440 return; 3441 } 3442 for (int index = 0; index < count; ++index) { 3443 *list.append() = &contours[index]; 3444 } 3445 QSort<Contour>(list.begin(), list.end() - 1); 3446} 3447 3448void simplifyx(const SkPath& path, SkPath& simple) { 3449 // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 3450 int winding = (path.getFillType() & 1) ? 1 : -1; 3451 simple.reset(); 3452 simple.setFillType(SkPath::kEvenOdd_FillType); 3453 3454 // turn path into list of segments 3455 SkTArray<Contour> contours; 3456 // FIXME: add self-intersecting cubics' T values to segment 3457 EdgeBuilder builder(path, contours); 3458 SkTDArray<Contour*> contourList; 3459 makeContourList(contours, contourList); 3460 Contour** currentPtr = contourList.begin(); 3461 if (!currentPtr) { 3462 return; 3463 } 3464 Contour** listEnd = contourList.end(); 3465 // find all intersections between segments 3466 do { 3467 Contour** nextPtr = currentPtr; 3468 Contour* current = *currentPtr++; 3469 Contour* next; 3470 do { 3471 next = *nextPtr++; 3472 } while (addIntersectTs(current, next) && nextPtr != listEnd); 3473 } while (currentPtr != listEnd); 3474 // eat through coincident edges 3475 coincidenceCheck(contourList, winding); 3476 fixOtherTIndex(contourList); 3477 // construct closed contours 3478 bridge(contourList, simple); 3479} 3480 3481