EdgeWalker.cpp revision d88e0894d0156f4d427b812fec69bfba3eec7a8d
1c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 2c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com/* 3c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com * Copyright 2012 Google Inc. 4c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com * 5c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 6c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com * found in the LICENSE file. 7c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com */ 8c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 96680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com#include "CurveIntersection.h" 10c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "LineIntersection.h" 11c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "SkPath.h" 12c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "SkRect.h" 13c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "SkTArray.h" 14c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "SkTDArray.h" 15d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#include "ShapeOps.h" 16c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "TSearch.h" 17c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if 0 // set to 1 for no debugging whatsoever 19d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.comconst bool gShowDebugf = false; // FIXME: remove once debugging is complete 202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_DUMP 0 222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD 0 232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD_INTERSECTING_TS 0 242e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD_BOTTOM_TS 0 252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define COMPARE_DOUBLE 0 262e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ABOVE_BELOW 0 272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ACTIVE_LESS_THAN 0 282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_SORT_HORIZONTAL 0 292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_OUT 0 302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_OUT_LESS_THAN 0 312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADJUST_COINCIDENT 0 32752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#define DEBUG_BOTTOM 0 33752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#else 35d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.comconst bool gShowDebugf = true; // FIXME: remove once debugging is complete 362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_DUMP 01 382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD 01 392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD_INTERSECTING_TS 0 402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD_BOTTOM_TS 0 41d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#define COMPARE_DOUBLE 0 422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ABOVE_BELOW 01 43752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#define DEBUG_ACTIVE_LESS_THAN 01 442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_SORT_HORIZONTAL 01 452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_OUT 01 462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_OUT_LESS_THAN 0 472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADJUST_COINCIDENT 1 48752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#define DEBUG_BOTTOM 01 49752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 52d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com// FIXME: not wild about this -- for SkScalars backed by floats, would like to 532e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// represent deltas in terms of number of significant matching bits 542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define MIN_PT_DELTA 0.000001 55c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com 566680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic int LineIntersect(const SkPoint a[2], const SkPoint b[2], 57c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com double aRange[2], double bRange[2]) { 58c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 59c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 60c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return intersect(aLine, bLine, aRange, bRange); 61c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 62c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, 642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar y, double aRange[2]) { 65c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return horizontalLineIntersect(aLine, left, right, y, aRange); 67c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 68c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 69cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.comstatic void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { 70cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 71cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com double x, y; 72cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com xy_at_t(aLine, t, x, y); 73cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com out->fX = SkDoubleToScalar(x); 74cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com out->fY = SkDoubleToScalar(y); 75cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com} 76cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com 772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if COMPARE_DOUBLE 782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic void LineXYAtT(const SkPoint a[2], double t, _Point* out) { 792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com xy_at_t(aLine, t, out->x, out->y); 812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if 0 // unused for now 852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic SkScalar LineXAtT(const SkPoint a[2], double t) { 862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com double x; 882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com xy_at_t(aLine, t, x, *(double*) 0); 892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return SkDoubleToScalar(x); 902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 936680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic SkScalar LineYAtT(const SkPoint a[2], double t) { 946680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 956680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com double y; 966680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com xy_at_t(aLine, t, *(double*) 0, y); 976680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return SkDoubleToScalar(y); 986680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com} 996680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 1006680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic void LineSubDivide(const SkPoint a[2], double startT, double endT, 1016680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkPoint sub[2]) { 1026680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 1036680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com _Line dst; 1046680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub_divide(aLine, startT, endT, dst); 1056680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub[0].fX = SkDoubleToScalar(dst[0].x); 1066680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub[0].fY = SkDoubleToScalar(dst[0].y); 1076680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub[1].fX = SkDoubleToScalar(dst[1].x); 1086680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub[1].fY = SkDoubleToScalar(dst[1].y); 1096680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com} 1106680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 1112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if COMPARE_DOUBLE 1122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic void LineSubDivide(const SkPoint a[2], double startT, double endT, 1132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Line& dst) { 1142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 1152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com sub_divide(aLine, startT, endT, dst); 1162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 1172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 1186680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 119c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com/* 120c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comlist of edges 121c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combounds for edge 122c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comsort 123c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comactive T 124c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 125c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comif a contour's bounds is outside of the active area, no need to create edges 126c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com*/ 127c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 128c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com/* given one or more paths, 129c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com find the bounds of each contour, select the active contours 130c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for each active contour, compute a set of edges 131c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com each edge corresponds to one or more lines and curves 132c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com leave edges unbroken as long as possible 133c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com when breaking edges, compute the t at the break but leave the control points alone 134c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 135c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com */ 136c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 137c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray) { 138c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Iter iter(path, false); 139c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPoint pts[4]; 140c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Verb verb; 141c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkRect bounds; 142c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bounds.setEmpty(); 143c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int count = 0; 144c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 145c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com switch (verb) { 146c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kMove_Verb: 147c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (!bounds.isEmpty()) { 148c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *boundsArray.append() = bounds; 149c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 150c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bounds.set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY); 151c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 0; 152c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 153c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kLine_Verb: 154c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 1; 155c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 156c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kQuad_Verb: 157c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 2; 158c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 159c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kCubic_Verb: 160c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 3; 161c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 162c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kClose_Verb: 163c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 0; 164c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 165c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com default: 166c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkDEBUGFAIL("bad verb"); 167c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 168c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 169c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (int i = 1; i <= count; ++i) { 170c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bounds.growToInclude(pts[i].fX, pts[i].fY); 171c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 172c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 173c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 174c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 175f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic bool extendLine(const SkPoint line[2], const SkPoint& add) { 176f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // FIXME: allow this to extend lines that have slopes that are nearly equal 177f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar dx1 = line[1].fX - line[0].fX; 178f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar dy1 = line[1].fY - line[0].fY; 179f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar dx2 = add.fX - line[0].fX; 180f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar dy2 = add.fY - line[0].fY; 181f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com return dx1 * dy2 == dx2 * dy1; 182f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1836680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 1842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// OPTIMIZATION: this should point to a list of input data rather than duplicating 1852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// the line data here. This would reduce the need to assemble the results. 186f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstruct OutEdge { 187f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com bool operator<(const OutEdge& rh) const { 188cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const SkPoint& first = fPts[0]; 189cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const SkPoint& rhFirst = rh.fPts[0]; 190f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com return first.fY == rhFirst.fY 191f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com ? first.fX < rhFirst.fX 192f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com : first.fY < rhFirst.fY; 193f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 194752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 195cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkPoint fPts[4]; 1962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int fID; // id of edge generating data 197cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com uint8_t fVerb; // FIXME: not read from everywhere 1982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool fCloseCall; // edge is trimmable if not originally coincident 199f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com}; 200f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 2016680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comclass OutEdgeBuilder { 2026680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.compublic: 203f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com OutEdgeBuilder(bool fill) 204f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com : fFill(fill) { 205f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 206f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 2072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void addLine(const SkPoint line[2], int id, bool closeCall) { 208c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com OutEdge& newEdge = fEdges.push_back(); 209cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com newEdge.fPts[0] = line[0]; 210cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com newEdge.fPts[1] = line[1]; 211cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com newEdge.fVerb = SkPath::kLine_Verb; 2122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com newEdge.fID = id; 2132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com newEdge.fCloseCall = closeCall; 2142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 215752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 2162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool trimLine(SkScalar y, int id) { 2172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com size_t count = fEdges.count(); 2182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com while (count-- != 0) { 2192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com OutEdge& edge = fEdges[count]; 2202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (edge.fID != id) { 2212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com continue; 2222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 2232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (edge.fCloseCall) { 2242e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return false; 2252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 2262e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkASSERT(edge.fPts[0].fY <= y); 2272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (edge.fPts[1].fY <= y) { 2282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com continue; 2292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 2302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com edge.fPts[1].fX = edge.fPts[0].fX + (y - edge.fPts[0].fY) 2312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com * (edge.fPts[1].fX - edge.fPts[0].fX) 2322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com / (edge.fPts[1].fY - edge.fPts[0].fY); 2332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com edge.fPts[1].fY = y; 2342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (gShowDebugf) { 2352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s edge=%d %1.9g,%1.9g\n", __FUNCTION__, id, 2362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com edge.fPts[1].fX, y); 2372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 2382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return true; 2392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 2402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return false; 241f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 242f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 243f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com void assemble(SkPath& simple) { 2446008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com size_t listCount = fEdges.count(); 2456008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (listCount == 0) { 2466008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return; 2476008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 248f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 2496008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com size_t listIndex = 0; 2506008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int advance = 1; 2516008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (listIndex < listCount && fTops[listIndex] == 0) { 2526008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ++listIndex; 253f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 2546008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (listIndex >= listCount) { 2556008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com break; 256f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 2574917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com int closeEdgeIndex = -listIndex - 1; 258cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkPoint firstPt, lastLine[2]; 2596008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool doMove = true; 2606008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int edgeIndex; 2616008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com do { 262cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkPoint* ptArray = fEdges[listIndex].fPts; 263cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com uint8_t verb = fEdges[listIndex].fVerb; 264cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkPoint* start, * end; 2656008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (advance < 0) { 266cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com start = &ptArray[verb]; 267cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com end = &ptArray[0]; 2686008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 269cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com start = &ptArray[0]; 270cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com end = &ptArray[verb]; 271f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 272cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com switch (verb) { 273cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com case SkPath::kLine_Verb: 274cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com bool gap; 275cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (doMove) { 276cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com firstPt = *start; 277cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com simple.moveTo(start->fX, start->fY); 278cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gShowDebugf) { 279cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkDebugf("%s moveTo (%g,%g)\n", __FUNCTION__, 280cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com start->fX, start->fY); 281cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 282cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com lastLine[0] = *start; 283cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com lastLine[1] = *end; 284cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com doMove = false; 285cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com break; 286cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 287cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com gap = lastLine[1] != *start; 288cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gap) { 289d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com // FIXME: see comment in bridge -- this probably 290d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com // conceals errors 291d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com SkASSERT(fFill && UlpsDiff(lastLine[1].fY, start->fY) <= 10); 292cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com simple.lineTo(lastLine[1].fX, lastLine[1].fY); 293cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gShowDebugf) { 294cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkDebugf("%s lineTo x (%g,%g)\n", __FUNCTION__, 295cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com lastLine[1].fX, lastLine[1].fY); 296cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 297cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 298cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gap || !extendLine(lastLine, *end)) { 299d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com // FIXME: see comment in bridge -- this probably 300d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com // conceals errors 301cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(lastLine[1] == *start || 302d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com (fFill && UlpsDiff(lastLine[1].fY, start->fY) <= 10)); 303cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com simple.lineTo(start->fX, start->fY); 304cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gShowDebugf) { 305cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkDebugf("%s lineTo (%g,%g)\n", __FUNCTION__, 306cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com start->fX, start->fY); 307cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 308cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com lastLine[0] = *start; 309cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 310cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com lastLine[1] = *end; 3116008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com break; 312cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com default: 313cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add other curve types 314cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com ; 3156008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 3166008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (advance < 0) { 3176008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com edgeIndex = fTops[listIndex]; 3186008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fTops[listIndex] = 0; 3196008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 3206008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com edgeIndex = fBottoms[listIndex]; 3216008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fBottoms[listIndex] = 0; 3226008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 3234917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (edgeIndex) { 3244917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com listIndex = abs(edgeIndex) - 1; 3254917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (edgeIndex < 0) { 3264917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com fTops[listIndex] = 0; 3274917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } else { 3284917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com fBottoms[listIndex] = 0; 3294917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 3304917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 3314917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (edgeIndex == closeEdgeIndex || edgeIndex == 0) { 3324917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (lastLine[1] != firstPt) { 3334917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com simple.lineTo(lastLine[1].fX, lastLine[1].fY); 3342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (gShowDebugf) { 3352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s lineTo last (%g, %g)\n", __FUNCTION__, 3362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com lastLine[1].fX, lastLine[1].fY); 3372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 3384917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 339cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com simple.lineTo(firstPt.fX, firstPt.fY); 340cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com simple.close(); 341cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gShowDebugf) { 3424917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com SkDebugf("%s close (%g, %g)\n", __FUNCTION__, 3434917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com firstPt.fX, firstPt.fY); 344cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 345cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com break; 346cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 3476008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // if this and next edge go different directions 3486008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (advance > 0 ^ edgeIndex < 0) { 3496008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com advance = -advance; 3506008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 3514917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } while (edgeIndex); 3526008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } while (true); 353f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 354752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 355cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // sort points by y, then x 356cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // if x/y is identical, sort bottoms before tops 357cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // if identical and both tops/bottoms, sort by angle 358cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com static bool lessThan(SkTArray<OutEdge>& edges, const int one, 359cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const int two) { 360cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const OutEdge& oneEdge = edges[abs(one) - 1]; 361cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com int oneIndex = one < 0 ? 0 : oneEdge.fVerb; 362cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const SkPoint& startPt1 = oneEdge.fPts[oneIndex]; 363cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const OutEdge& twoEdge = edges[abs(two) - 1]; 364cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com int twoIndex = two < 0 ? 0 : twoEdge.fVerb; 365cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const SkPoint& startPt2 = twoEdge.fPts[twoIndex]; 366cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (startPt1.fY != startPt2.fY) { 3672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_OUT_LESS_THAN 3682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s %d<%d (%g,%g) %s startPt1.fY < startPt2.fY\n", __FUNCTION__, 3692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com one, two, startPt1.fY, startPt2.fY, 3702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com startPt1.fY < startPt2.fY ? "true" : "false"); 3712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 372cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return startPt1.fY < startPt2.fY; 373cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 374cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (startPt1.fX != startPt2.fX) { 3752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_OUT_LESS_THAN 3762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s %d<%d (%g,%g) %s startPt1.fX < startPt2.fX\n", __FUNCTION__, 3772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com one, two, startPt1.fX, startPt2.fX, 3782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com startPt1.fX < startPt2.fX ? "true" : "false"); 3792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 380cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return startPt1.fX < startPt2.fX; 381cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 382cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const SkPoint& endPt1 = oneEdge.fPts[oneIndex ^ oneEdge.fVerb]; 383cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const SkPoint& endPt2 = twoEdge.fPts[twoIndex ^ twoEdge.fVerb]; 384cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkScalar dy1 = startPt1.fY - endPt1.fY; 385cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkScalar dy2 = startPt2.fY - endPt2.fY; 386cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkScalar dy1y2 = dy1 * dy2; 387cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (dy1y2 < 0) { // different signs 3882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_OUT_LESS_THAN 389cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkDebugf("%s %d<%d %s dy1 > 0\n", __FUNCTION__, one, two, 390cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com dy1 > 0 ? "true" : "false"); 3912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 392cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return dy1 > 0; // one < two if one goes up and two goes down 393cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 394cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (dy1y2 == 0) { 3952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_OUT_LESS_THAN 3962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s %d<%d %s endPt1.fX < endPt2.fX\n", __FUNCTION__, 3972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com one, two, endPt1.fX < endPt2.fX ? "true" : "false"); 3982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 399cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return endPt1.fX < endPt2.fX; 400cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 401cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkScalar dx1y2 = (startPt1.fX - endPt1.fX) * dy2; 402cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkScalar dx2y1 = (startPt2.fX - endPt2.fX) * dy1; 4032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_OUT_LESS_THAN 4042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s %d<%d %s dy2 < 0 ^ dx1y2 < dx2y1\n", __FUNCTION__, 4052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com one, two, dy2 < 0 ^ dx1y2 < dx2y1 ? "true" : "false"); 4062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 407cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return dy2 > 0 ^ dx1y2 < dx2y1; 408f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 409f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 4106008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // Sort the indices of paired points and then create more indices so 4116008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // assemble() can find the next edge and connect the top or bottom 412f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com void bridge() { 413f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com size_t index; 414f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com size_t count = fEdges.count(); 415f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (!count) { 416f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com return; 417f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 418cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(!fFill || count > 1); 419f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com fTops.setCount(count); 420f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com sk_bzero(fTops.begin(), sizeof(fTops[0]) * count); 421f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com fBottoms.setCount(count); 422f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com sk_bzero(fBottoms.begin(), sizeof(fBottoms[0]) * count); 4236008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkTDArray<int> order; 4246008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com for (index = 1; index <= count; ++index) { 4256008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com *order.append() = -index; 426f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 427cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com for (index = 1; index <= count; ++index) { 428cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com *order.append() = index; 429cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 430cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com QSort<SkTArray<OutEdge>, int>(fEdges, order.begin(), order.end() - 1, lessThan); 4316008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int* lastPtr = order.end() - 1; 4326008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int* leftPtr = order.begin(); 4336008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (leftPtr < lastPtr) { 4346008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int leftIndex = *leftPtr; 4356008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int leftOutIndex = abs(leftIndex) - 1; 4366008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com const OutEdge& left = fEdges[leftOutIndex]; 437f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int* rightPtr = leftPtr + 1; 4386008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int rightIndex = *rightPtr; 4396008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int rightOutIndex = abs(rightIndex) - 1; 4406008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com const OutEdge& right = fEdges[rightOutIndex]; 441cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com bool pairUp = fFill; 442cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (!pairUp) { 443cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const SkPoint& leftMatch = 444cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com left.fPts[leftIndex < 0 ? 0 : left.fVerb]; 445cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const SkPoint& rightMatch = 446cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com right.fPts[rightIndex < 0 ? 0 : right.fVerb]; 447cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com pairUp = leftMatch == rightMatch; 448cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } else { 4492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_OUT 450d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com // FIXME : not happy that error in low bit is allowed 451d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com // this probably conceals error elsewhere 452d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com if (UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY, 453d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) > 1) { 4542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com *fMismatches.append() = leftIndex; 4552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (rightPtr == lastPtr) { 4562e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com *fMismatches.append() = rightIndex; 4572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 4582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com pairUp = false; 4592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 4602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #else 461d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com SkASSERT(UlpsDiff(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY, 462d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) <= 10); 4632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 464cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 465cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (pairUp) { 4666008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (leftIndex < 0) { 4676008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fTops[leftOutIndex] = rightIndex; 4686008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 4696008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fBottoms[leftOutIndex] = rightIndex; 4706008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 4716008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (rightIndex < 0) { 4726008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fTops[rightOutIndex] = leftIndex; 4736008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 4746008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fBottoms[rightOutIndex] = leftIndex; 475f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 4766008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ++rightPtr; 477f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 478f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com leftPtr = rightPtr; 4796680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 4802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_OUT 4812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int* mismatch = fMismatches.begin(); 4822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com while (mismatch != fMismatches.end()) { 4832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int leftIndex = *mismatch++; 4842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int leftOutIndex = abs(leftIndex) - 1; 4852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const OutEdge& left = fEdges[leftOutIndex]; 4862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const SkPoint& leftPt = left.fPts[leftIndex < 0 ? 0 : left.fVerb]; 4872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s left=%d %s (%1.9g,%1.9g)\n", 4882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com __FUNCTION__, left.fID, leftIndex < 0 ? "top" : "bot", 4892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com leftPt.fX, leftPt.fY); 4902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 4912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkASSERT(fMismatches.count() == 0); 4922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 4936680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 4946680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 4956008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comprotected: 4966680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTArray<OutEdge> fEdges; 4976008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkTDArray<int> fTops; 4986008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkTDArray<int> fBottoms; 499f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com bool fFill; 5002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_OUT 5012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTDArray<int> fMismatches; 5022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 5036680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com}; 5046680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 505c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com// Bounds, unlike Rect, does not consider a vertical line to be empty. 506c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comstruct Bounds : public SkRect { 507c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com static bool Intersects(const Bounds& a, const Bounds& b) { 508c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return a.fLeft <= b.fRight && b.fLeft <= a.fRight && 509c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com a.fTop <= b.fBottom && b.fTop <= a.fBottom; 510c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 511752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 5126008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool isEmpty() { 5136008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return fLeft > fRight || fTop > fBottom 5146008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com || fLeft == fRight && fTop == fBottom 5156008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com || isnan(fLeft) || isnan(fRight) 5166008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com || isnan(fTop) || isnan(fBottom); 5176008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 518c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 519c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 5204917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.comclass Intercepts { 5214917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.compublic: 5224917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com Intercepts() 5234917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com : fTopIntercepts(0) 5244917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com , fBottomIntercepts(0) { 5254917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 526752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 5272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_DUMP 5282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: pass current verb as parameter 5292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void dump(const SkPoint* pts) { 5302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const char className[] = "Intercepts"; 5312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const int tab = 8; 5322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (int i = 0; i < fTs.count(); ++i) { 5332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkPoint out; 5342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineXYAtT(pts, fTs[i], &out); 535752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s.fTs[%d]=%1.9g (%1.9g,%1.9g)\n", tab + sizeof(className), 5362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, i, fTs[i], out.fX, out.fY); 5372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 5382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fTopIntercepts=%d\n", tab + sizeof(className), 5392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, fTopIntercepts); 5402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fBottomIntercepts=%d\n", tab + sizeof(className), 5412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, fBottomIntercepts); 5422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 5432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 5442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 545c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkTDArray<double> fTs; 5464917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com int fTopIntercepts; 5474917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com int fBottomIntercepts; 548c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 549c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 5502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstruct HorizontalEdge { 5512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool operator<(const HorizontalEdge& rh) const { 5522e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return fY == rh.fY ? fLeft == rh.fLeft ? fRight < rh.fRight 5532e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com : fLeft < rh.fLeft : fY < rh.fY; 5542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 5552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 5562e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_DUMP 5572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void dump() { 5582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const char className[] = "HorizontalEdge"; 5592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const int tab = 4; 560752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s.fLeft=%1.9g\n", tab + sizeof(className), className, fLeft); 561752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s.fRight=%1.9g\n", tab + sizeof(className), className, fRight); 562752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s.fY=%1.9g\n", tab + sizeof(className), className, fY); 5632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 5642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 5652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 5662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar fLeft; 5672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar fRight; 5682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar fY; 5692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com}; 5702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 5716680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstruct InEdge { 5726680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool operator<(const InEdge& rh) const { 573c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return fBounds.fTop == rh.fBounds.fTop 574c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com ? fBounds.fLeft < rh.fBounds.fLeft 575c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com : fBounds.fTop < rh.fBounds.fTop; 576c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 577c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 5782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // Avoid collapsing t values that are close to the same since 5792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // we walk ts to describe consecutive intersections. Since a pair of ts can 5802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // be nearly equal, any problems caused by this should be taken care 5812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // of later. 5822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int add(double* ts, size_t count, ptrdiff_t verbIndex) { 583c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // FIXME: in the pathological case where there is a ton of intercepts, binary search? 5846008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool foundIntercept = false; 5852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int insertedAt = -1; 5866008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com Intercepts& intercepts = fIntercepts[verbIndex]; 587c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (size_t index = 0; index < count; ++index) { 588c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com double t = ts[index]; 5894917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (t <= 0) { 5904917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com fContainsIntercepts |= ++intercepts.fTopIntercepts > 1; 5914917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com continue; 5924917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 5934917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (t >= 1) { 5944917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com fContainsIntercepts |= ++intercepts.fBottomIntercepts > 1; 5956008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com continue; 5966008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 5976008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com foundIntercept = true; 598c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com size_t tCount = intercepts.fTs.count(); 5992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com double delta; 600c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (size_t idx2 = 0; idx2 < tCount; ++idx2) { 601c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (t <= intercepts.fTs[idx2]) { 6022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: ? if (t < intercepts.fTs[idx2]) // failed 6032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com delta = intercepts.fTs[idx2] - t; 604cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (delta > 0) { 6052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com insertedAt = idx2; 606c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *intercepts.fTs.insert(idx2) = t; 607c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 6082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com goto nextPt; 609c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 610c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 6112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (tCount == 0 || (delta = t - intercepts.fTs[tCount - 1]) > 0) { 6122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com insertedAt = tCount; 613c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *intercepts.fTs.append() = t; 614c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 6152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com nextPt: 6162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ; 617c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 6184917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com fContainsIntercepts |= foundIntercept; 6192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return insertedAt; 620c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 621c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 6226680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool cached(const InEdge* edge) { 623c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // FIXME: in the pathological case where there is a ton of edges, binary search? 624c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com size_t count = fCached.count(); 625c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (size_t index = 0; index < count; ++index) { 626c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (edge == fCached[index]) { 627c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return true; 628c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 629c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (edge < fCached[index]) { 630c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *fCached.insert(index) = edge; 631c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return false; 632c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 633c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 634c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *fCached.append() = edge; 635c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return false; 636c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 637c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 6382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void complete(signed char winding, int id) { 639c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPoint* ptPtr = fPts.begin(); 640c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPoint* ptLast = fPts.end(); 641c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (ptPtr == ptLast) { 642c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkDebugf("empty edge\n"); 643c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkASSERT(0); 644c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // FIXME: delete empty edge? 645c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 646c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 647c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fBounds.set(ptPtr->fX, ptPtr->fY, ptPtr->fX, ptPtr->fY); 648c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com ++ptPtr; 649c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com while (ptPtr != ptLast) { 650c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fBounds.growToInclude(ptPtr->fX, ptPtr->fY); 651c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com ++ptPtr; 652c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 6536008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fIntercepts.push_back_n(fVerbs.count()); 6546680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top 6556680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com size_t index; 6566680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com size_t last = fPts.count() - 1; 6576680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com for (index = 0; index < last; ++index, --last) { 6586680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTSwap<SkPoint>(fPts[index], fPts[last]); 6596680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 6606680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com last = fVerbs.count() - 1; 6616680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com for (index = 0; index < last; ++index, --last) { 6626680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTSwap<uint8_t>(fVerbs[index], fVerbs[last]); 6636680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 6646680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 6656680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fContainsIntercepts = false; 6662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fID = id; 6672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 6682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 6692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_DUMP 6702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void dump() { 6712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int i; 6722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const char className[] = "InEdge"; 6732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const int tab = 4; 6742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("InEdge %p (edge=%d)\n", this, fID); 6752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (i = 0; i < fCached.count(); ++i) { 6762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fCached[%d]=0x%08x\n", tab + sizeof(className), 6772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, i, fCached[i]); 6782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 6792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com uint8_t* verbs = fVerbs.begin(); 6802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkPoint* pts = fPts.begin(); 6812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (i = 0; i < fIntercepts.count(); ++i) { 6822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fIntercepts[%d]:\n", tab + sizeof(className), 6832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, i); 6842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: take current verb into consideration 6852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fIntercepts[i].dump(pts); 6862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com pts += *verbs++; 6872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 6882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (i = 0; i < fPts.count(); ++i) { 689752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s.fPts[%d]=(%1.9g,%1.9g)\n", tab + sizeof(className), 6902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, i, fPts[i].fX, fPts[i].fY); 6912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 6922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (i = 0; i < fVerbs.count(); ++i) { 6932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fVerbs[%d]=%d\n", tab + sizeof(className), 6942e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, i, fVerbs[i]); 6952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 696752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s.fBounds=(%1.9g. %1.9g, %1.9g, %1.9g)\n", tab + sizeof(className), 6972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, fBounds.fLeft, fBounds.fTop, 6982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fBounds.fRight, fBounds.fBottom); 6992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fWinding=%d\n", tab + sizeof(className), className, 7002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fWinding); 7012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), 7022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, fContainsIntercepts); 703c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 7042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 705c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 706c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // temporary data : move this to a separate struct? 7076680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTDArray<const InEdge*> fCached; // list of edges already intercepted 708c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkTArray<Intercepts> fIntercepts; // one per verb 7094917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com 710c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // persistent data 711c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkTDArray<SkPoint> fPts; 712c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkTDArray<uint8_t> fVerbs; 713c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com Bounds fBounds; 7142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int fID; 715c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com signed char fWinding; 7166680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool fContainsIntercepts; 717c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 718c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 7196680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comclass InEdgeBuilder { 720c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.compublic: 721c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 7222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comInEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges, 7232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTDArray<HorizontalEdge>& horizontalEdges) 724c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com : fPath(path) 725c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com , fCurrentEdge(NULL) 726c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com , fEdges(edges) 7272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com , fID(0) 7282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com , fHorizontalEdges(horizontalEdges) 729c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com , fIgnoreHorizontal(ignoreHorizontal) 730c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com{ 731c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com walk(); 732c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 733c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 734c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comprotected: 735c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 736c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid addEdge() { 737f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkASSERT(fCurrentEdge); 738c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fCurrentEdge->fPts.append(fPtCount - fPtOffset, &fPts[fPtOffset]); 739c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fPtOffset = 1; 740c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *fCurrentEdge->fVerbs.append() = fVerb; 741c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 742c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 7436008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.combool complete() { 7446008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (fCurrentEdge && fCurrentEdge->fVerbs.count()) { 7452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fCurrentEdge->complete(fWinding, ++fID); 7466008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fCurrentEdge = NULL; 7476008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return true; 7486008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 7496008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return false; 7506008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com} 7516008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 752c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comint direction(int count) { 753c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fPtCount = count; 7542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (fIgnoreHorizontal && isHorizontal()) { 755c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return 0; 756c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 757c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int last = count - 1; 758c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return fPts[0].fY == fPts[last].fY 7596680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com ? fPts[0].fX == fPts[last].fX ? 0 : fPts[0].fX < fPts[last].fX 7606680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com ? 1 : -1 : fPts[0].fY < fPts[last].fY ? 1 : -1; 761c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 762c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 763c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool isHorizontal() { 764c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkScalar y = fPts[0].fY; 765c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (int i = 1; i < fPtCount; ++i) { 766c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (fPts[i].fY != y) { 767c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return false; 768c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 769c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 770c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return true; 771c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 772c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 773c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid startEdge() { 7746008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (!fCurrentEdge) { 7756008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fCurrentEdge = fEdges.push_back_n(1); 7766008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 777c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fWinding = 0; 778c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fPtOffset = 0; 779c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 780c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 781c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid walk() { 782c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Iter iter(fPath, true); 7832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int winding = 0; 784c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com while ((fVerb = iter.next(fPts)) != SkPath::kDone_Verb) { 785c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com switch (fVerb) { 786c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kMove_Verb: 787c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com startEdge(); 788c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com continue; 789c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kLine_Verb: 790c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com winding = direction(2); 791c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 792c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kQuad_Verb: 793c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com winding = direction(3); 794c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 795c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kCubic_Verb: 796c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com winding = direction(4); 797c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 798c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kClose_Verb: 799f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkASSERT(fCurrentEdge); 8006008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com complete(); 801c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com continue; 802c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com default: 803c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkDEBUGFAIL("bad verb"); 804c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 805c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 8062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (winding == 0) { 8072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge* horizontalEdge = fHorizontalEdges.append(); 8082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: for degenerate quads and cubics, compute x extremes 8092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horizontalEdge->fLeft = fPts[0].fX; 8102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horizontalEdge->fRight = fPts[fVerb].fX; 8112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horizontalEdge->fY = fPts[0].fY; 8122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (horizontalEdge->fLeft > horizontalEdge->fRight) { 8132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTSwap<SkScalar>(horizontalEdge->fLeft, horizontalEdge->fRight); 8142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 8156008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (complete()) { 8166008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com startEdge(); 8176008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 818c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com continue; 819c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 820c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (fWinding + winding == 0) { 821c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // FIXME: if prior verb or this verb is a horizontal line, reverse 822c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // it instead of starting a new edge 823f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkASSERT(fCurrentEdge); 824cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (complete()) { 825cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com startEdge(); 826cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 827c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 828c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fWinding = winding; 829c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com addEdge(); 830c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 8316b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (!complete()) { 8326b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (fCurrentEdge) { 8336b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com fEdges.pop_back(); 8346b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 8356b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 836c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 837c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 838c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comprivate: 839c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com const SkPath& fPath; 8406680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com InEdge* fCurrentEdge; 8416680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTArray<InEdge>& fEdges; 8422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTDArray<HorizontalEdge>& fHorizontalEdges; 843c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPoint fPts[4]; 844c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Verb fVerb; 845c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int fPtCount; 846c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int fPtOffset; 8472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int fID; 848c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int8_t fWinding; 849c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bool fIgnoreHorizontal; 850c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 851c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 8526680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstruct WorkEdge { 853c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkScalar bottom() const { 8546680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return fPts[verb()].fY; 855c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 856c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 8576680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com void init(const InEdge* edge) { 8586680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fEdge = edge; 8596680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fPts = edge->fPts.begin(); 8606680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fVerb = edge->fVerbs.begin(); 861c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 862c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 863cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com bool advance() { 8646680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkASSERT(fVerb < fEdge->fVerbs.end()); 8656680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fPts += *fVerb++; 8666680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return fVerb != fEdge->fVerbs.end(); 867c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 868752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 869cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkPath::Verb lastVerb() const { 870cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkASSERT(fVerb > fEdge->fVerbs.begin()); 871cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return (SkPath::Verb) fVerb[-1]; 872cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 873cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com 874c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 875c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Verb verb() const { 876c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return (SkPath::Verb) *fVerb; 877c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 878c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 8796008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ptrdiff_t verbIndex() const { 8806680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return fVerb - fEdge->fVerbs.begin(); 8816680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 882752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 8836680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com int winding() const { 8846680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return fEdge->fWinding; 885c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 886c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 8876680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com const InEdge* fEdge; 888c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com const SkPoint* fPts; 889c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com const uint8_t* fVerb; 890c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 891c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 8926680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com// always constructed with SkTDArray because new edges are inserted 8936680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com// this may be a inappropriate optimization, suggesting that a separate array of 8946680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com// ActiveEdge* may be faster to insert and search 895cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com 896cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com// OPTIMIZATION: Brian suggests that global sorting should be unnecessary, since 897cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com// as active edges are introduced, only local sorting should be required 8982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comclass ActiveEdge { 8992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.compublic: 9006008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool operator<(const ActiveEdge& rh) const { 901d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com double topD = fAbove.fX - rh.fAbove.fX; 902d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com if (rh.fAbove.fY < fAbove.fY) { 903d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com topD = (rh.fBelow.fY - rh.fAbove.fY) * topD 904d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com - (fAbove.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX); 905d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } else if (rh.fAbove.fY > fAbove.fY) { 906d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com topD = (fBelow.fY - fAbove.fY) * topD 907d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com + (rh.fAbove.fY - fAbove.fY) * (fBelow.fX - fAbove.fX); 908d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } 909d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com double botD = fBelow.fX - rh.fBelow.fX; 910d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com if (rh.fBelow.fY > fBelow.fY) { 911d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com botD = (rh.fBelow.fY - rh.fAbove.fY) * botD 912d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com - (fBelow.fY - rh.fBelow.fY) * (rh.fBelow.fX - rh.fAbove.fX); 913d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } else if (rh.fBelow.fY < fBelow.fY) { 914d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com botD = (fBelow.fY - fAbove.fY) * botD 915d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com + (rh.fBelow.fY - fBelow.fY) * (fBelow.fX - fAbove.fX); 916d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } 917d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com // return sign of greater absolute value 918d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com return (fabs(topD) > fabs(botD) ? topD : botD) < 0; 919d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } 920d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com 921d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com // OPTIMIZATION: fold return statements into one 922d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com bool operator_less_than(const ActiveEdge& rh) const { 923cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (rh.fAbove.fY - fAbove.fY > fBelow.fY - rh.fAbove.fY 924cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com && fBelow.fY < rh.fBelow.fY 925cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com || fAbove.fY - rh.fAbove.fY < rh.fBelow.fY - fAbove.fY 926cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com && rh.fBelow.fY < fBelow.fY) { 927cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // FIXME: need to compute distance, not check for points equal 928cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com const SkPoint& check = rh.fBelow.fY <= fBelow.fY 929cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com && fBelow != rh.fBelow ? rh.fBelow : 930cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com rh.fAbove; 9312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_ACTIVE_LESS_THAN 9322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s 1 %c %cthis (edge=%d) {%g,%g %g,%g}" 9332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com " < rh (edge=%d) {%g,%g %g,%g} upls=(%d)\n", __FUNCTION__, 9342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com rh.fBelow.fY <= fBelow.fY && fBelow != rh.fBelow ? 'B' : 'A', 9352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) 9362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX) ? ' ' 9372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com : '!', ID(), fAbove.fX, fAbove.fY, fBelow.fX, fBelow.fY, 9382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com rh.ID(), rh.fAbove.fX, rh.fAbove.fY, rh.fBelow.fX, rh.fBelow.fY, 9392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com UlpsDiff((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX), 9402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX))); 9412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 942752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if COMPARE_DOUBLE 943752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkASSERT(((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) 944752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX)) 945752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com == ((check.fY - fDAbove.y) * (fDBelow.x - fDAbove.x) 946752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com < (fDBelow.y - fDAbove.y) * (check.fX - fDAbove.x))); 9472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 948cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) 949cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX); 950cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 951cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // FIXME: need to compute distance, not check for points equal 952cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com const SkPoint& check = fBelow.fY <= rh.fBelow.fY 953cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com && fBelow != rh.fBelow ? fBelow : fAbove; 9542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_ACTIVE_LESS_THAN 9552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s 2 %c %cthis (edge=%d) {%g,%g %g,%g}" 956752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com " < rh (edge=%d) {%g,%g %g,%g} upls=(%d) (%d,%d)\n", __FUNCTION__, 957752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com fBelow.fY <= rh.fBelow.fY && fBelow != rh.fBelow ? 'B' : 'A', 9582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) 9592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX) 9602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ? ' ' : '!', ID(), fAbove.fX, fAbove.fY, fBelow.fX, fBelow.fY, 9612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com rh.ID(), rh.fAbove.fX, rh.fAbove.fY, rh.fBelow.fX, rh.fBelow.fY, 9622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com UlpsDiff((rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX), 963752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX)), 964752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com UlpsDiff(fBelow.fX, rh.fBelow.fX), UlpsDiff(fBelow.fY, rh.fBelow.fY)); 9652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 966752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if COMPARE_DOUBLE 967752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkASSERT(((rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) 968752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX)) 969752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com == ((rh.fDBelow.y - rh.fDAbove.y) * (check.fX - rh.fDAbove.x) 970752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com < (check.fY - rh.fDAbove.y) * (rh.fDBelow.x - rh.fDAbove.x))); 9712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 972cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) 973cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX); 9746008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 975752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 9762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // If a pair of edges are nearly coincident for some span, add a T in the 9772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // edge so it can be shortened to match the other edge. Note that another 9782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // approach is to trim the edge after it is added to the OutBuilder list -- 9792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: since this has no effect if the edge is already done (i.e., 9802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // fYBottom >= y) maybe this can only be done by calling trimLine later. 9812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void addTatYBelow(SkScalar y) { 9822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (fBelow.fY <= y || fYBottom >= y) { 9832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return; 9842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 9852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com addTatYInner(y); 9862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fFixBelow = true; 9872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 988752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 9892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void addTatYAbove(SkScalar y) { 9902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (fBelow.fY <= y) { 9912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return; 9922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 9932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com addTatYInner(y); 9942e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 9952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 9962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void addTatYInner(SkScalar y) { 997752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (fWorkEdge.fPts[0].fY > y) { 998752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com backup(y); 999752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } 10002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar left = fWorkEdge.fPts[0].fX; 10012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar right = fWorkEdge.fPts[1].fX; 10022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (left > right) { 10032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTSwap(left, right); 10042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1005752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com double ts[2]; 10062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int pts = LineIntersect(fWorkEdge.fPts, left, right, y, ts); 10072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkASSERT(pts == 1); 10082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // An ActiveEdge or WorkEdge has no need to modify the T values computed 10092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // in the InEdge, except in the following case. If a pair of edges are 10102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // nearly coincident, this may not be detected when the edges are 10112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // intersected. Later, when sorted, and this near-coincidence is found, 10122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // an additional t value must be added, requiring the cast below. 10132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge* writable = const_cast<InEdge*>(fWorkEdge.fEdge); 10142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int insertedAt = writable->add(ts, pts, fWorkEdge.verbIndex()); 1015752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if DEBUG_ADJUST_COINCIDENT 1016752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s edge=%d y=%1.9g t=%1.9g\n", __FUNCTION__, ID(), y, ts[0]); 1017752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #endif 10182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (insertedAt >= 0) { 10192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (insertedAt + 1 < fTIndex) { 10202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkASSERT(insertedAt + 2 == fTIndex); 10212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com --fTIndex; 10222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 10232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 10242e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 10256008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 1026cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com bool advanceT() { 1027cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkASSERT(fTIndex <= fTs->count()); 1028cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return ++fTIndex <= fTs->count(); 1029cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 10302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 1031cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com bool advance() { 1032cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // FIXME: flip sense of next 1033cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com bool result = fWorkEdge.advance(); 1034cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com fDone = !result; 1035cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com initT(); 1036cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return result; 1037cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1038752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1039752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com void backup(SkScalar y) { 1040752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com do { 1041752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkASSERT(fWorkEdge.fEdge->fVerbs.begin() < fWorkEdge.fVerb); 1042752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com fWorkEdge.fPts -= *--fWorkEdge.fVerb; 1043752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkASSERT(fWorkEdge.fEdge->fPts.begin() <= fWorkEdge.fPts); 1044752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } while (fWorkEdge.fPts[0].fY >= y); 1045752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com initT(); 1046752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com fTIndex = fTs->count() + 1; 1047752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } 1048752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1049cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com void calcLeft(SkScalar y) { 1050cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // OPTIMIZE: put a kDone_Verb at the end of the verb list? 10514917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (fDone || fBelow.fY > y) { 1052cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return; // nothing to do; use last 10534917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 1054cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com calcLeft(); 1055752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (fAbove.fY == fBelow.fY) { 1056752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s edge=%d fAbove.fY != fBelow.fY %1.9g\n", __FUNCTION__, 1057752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com ID(), fAbove.fY); 1058752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } 1059cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1060752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1061cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com void calcLeft() { 1062cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com switch (fWorkEdge.verb()) { 1063cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com case SkPath::kLine_Verb: { 1064cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // OPTIMIZATION: if fXAbove, fXBelow have already been computed 1065cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // for the fTIndex, don't do it again 1066cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // For identical x, this lets us know which edge is first. 1067cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // If both edges have T values < 1, check x at next T (fXBelow). 1068cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com int add = (fTIndex <= fTs->count()) - 1; 1069cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com double tAbove = t(fTIndex + add); 1070cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // OPTIMIZATION: may not need Y 1071cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove); 1072cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com double tBelow = t(fTIndex - ~add); 1073cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow); 10742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkASSERT(tAbove != tBelow); 1075752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com while (fAbove.fY == fBelow.fY) { 1076752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (add < 0) { 1077752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com add -= 1; 1078752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkASSERT(fTIndex + add >= 0); 1079752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com tAbove = t(fTIndex + add); 1080752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove); 1081752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } else { 1082752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com add += 1; 1083752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkASSERT(fTIndex - ~add <= fTs->count() + 1); 1084752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com tBelow = t(fTIndex - ~add); 1085752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow); 1086752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } 10872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 10882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if COMPARE_DOUBLE 10892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineXYAtT(fWorkEdge.fPts, tAbove, &fDAbove); 10902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineXYAtT(fWorkEdge.fPts, tBelow, &fDBelow); 10912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 10922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_ABOVE_BELOW 10932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fTAbove = tAbove; 10942e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fTBelow = tBelow; 10952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 1096cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com break; 1097cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1098cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com default: 1099cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add support for all curve types 1100cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(0); 1101cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 11026008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 11036008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 1104752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com bool done(SkScalar bottom) const { 1105752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com return fDone || fYBottom >= bottom; 1106cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1107752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 11082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void fixBelow() { 11092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (fFixBelow) { 11102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineXYAtT(fWorkEdge.fPts, nextT(), &fBelow); 11112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fFixBelow = false; 11122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 11132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 11142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 11156680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com void init(const InEdge* edge) { 11166680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fWorkEdge.init(edge); 11176680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com initT(); 11184917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com fBelow.fY = SK_ScalarMin; 1119cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com fDone = false; 1120cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com fYBottom = SK_ScalarMin; 11216680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 1122752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 11236680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com void initT() { 11246008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front(); 11256008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count()); 11266008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com const Intercepts* interceptPtr = &intercepts + fWorkEdge.verbIndex(); 11276008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fTs = &interceptPtr->fTs; 11286008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // the above is conceptually the same as 11296008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // fTs = &fWorkEdge.fEdge->fIntercepts[fWorkEdge.verbIndex()].fTs; 11306008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // but templated arrays don't allow returning a pointer to the end() element 11316680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fTIndex = 0; 11326680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 1133752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1134cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // OPTIMIZATION: record if two edges are coincident when the are intersected 1135cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // It's unclear how to do this -- seems more complicated than recording the 1136cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // t values, since the same t values could exist intersecting non-coincident 1137cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // edges. 1138cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com bool isCoincidentWith(const ActiveEdge* edge, SkScalar y) const { 1139752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1140d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#if 0 11412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (!fAbove.equalsWithinTolerance(edge->fAbove, MIN_PT_DELTA) 11422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com || !fBelow.equalsWithinTolerance(edge->fBelow, MIN_PT_DELTA)) { 1143cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return false; 1144cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1145d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#else 1146d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com if (fAbove != edge->fAbove || fBelow != edge->fBelow) { 1147d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com return false; 1148d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } 1149d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#endif 1150cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com uint8_t verb = fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb(); 1151cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com uint8_t edgeVerb = edge->fDone ? edge->fWorkEdge.lastVerb() 1152cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com : edge->fWorkEdge.verb(); 1153cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (verb != edgeVerb) { 1154cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return false; 1155cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1156cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com switch (verb) { 1157cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com case SkPath::kLine_Verb: { 11584917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com return true; 1159cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1160cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com default: 1161cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add support for all curve types 1162cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(0); 1163cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1164cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return false; 1165cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1166752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 11672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // The shortest close call edge should be moved into a position where 11682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // it contributes if the winding is transitioning to or from zero. 11692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool swapClose(const ActiveEdge* next, int prev, int wind, int mask) const { 1170d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#if DEBUG_ADJUST_COINCIDENT 1171d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com SkDebugf("%s edge=%d (%g) next=%d (%g) prev=%d wind=%d nextWind=%d\n", 1172d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com __FUNCTION__, ID(), fBelow.fY, next->ID(), next->fBelow.fY, 1173d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com prev, wind, wind + next->fWorkEdge.winding()); 1174d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#endif 11752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if ((prev & mask) == 0 || (wind & mask) == 0) { 11762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return next->fBelow.fY < fBelow.fY; 11772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 11782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int nextWinding = wind + next->fWorkEdge.winding(); 11792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if ((nextWinding & mask) == 0) { 11802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return fBelow.fY < next->fBelow.fY; 11812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 11822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return false; 11832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1184752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1185cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com bool swapCoincident(const ActiveEdge* edge, SkScalar bottom) const { 1186cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (fBelow.fY >= bottom || fDone || edge->fDone) { 1187cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return false; 1188cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1189cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com ActiveEdge thisWork = *this; 1190cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com ActiveEdge edgeWork = *edge; 1191cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com while ((thisWork.advanceT() || thisWork.advance()) 1192cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com && (edgeWork.advanceT() || edgeWork.advance())) { 1193cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com thisWork.calcLeft(); 1194cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com edgeWork.calcLeft(); 1195cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (thisWork < edgeWork) { 1196cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return false; 1197cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1198cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (edgeWork < thisWork) { 1199cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return true; 1200cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1201cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1202cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return false; 1203cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1204752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 12052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool tooCloseToCall(const ActiveEdge* edge) const { 12062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int ulps; 1207d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com // FIXME: the first variation works better (or at least causes fewer tests 1208d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com // to fail than the second, although the second's logic better matches the 1209d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com // current sort criteria. Need to track down the cause of the crash, and 1210d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com // see if the second case isn't somehow buggy. 1211d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#if 01 12122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: don't compare points for equality 12132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // OPTIMIZATION: refactor to make one call to UlpsDiff 12142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (edge->fAbove.fY - fAbove.fY > fBelow.fY - edge->fAbove.fY 12152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && fBelow.fY < edge->fBelow.fY 12162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com || fAbove.fY - edge->fAbove.fY < edge->fBelow.fY - fAbove.fY 12172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && edge->fBelow.fY < fBelow.fY) { 12182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const SkPoint& check = edge->fBelow.fY <= fBelow.fY 12192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && fBelow != edge->fBelow ? edge->fBelow : 12202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com edge->fAbove; 12212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ulps = UlpsDiff((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX), 12222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX)); 12232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } else { 12242e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const SkPoint& check = fBelow.fY <= edge->fBelow.fY 12252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && fBelow != edge->fBelow ? fBelow : fAbove; 12262e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ulps = UlpsDiff((edge->fBelow.fY - edge->fAbove.fY) 12272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com * (check.fX - edge->fAbove.fX), 12282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (check.fY - edge->fAbove.fY) 12292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com * (edge->fBelow.fX - edge->fAbove.fX)); 12302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1231d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#else 1232d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com double t1, t2, b1, b2; 1233d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com if (edge->fAbove.fY < fAbove.fY) { 1234d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com t1 = (edge->fBelow.fY - edge->fAbove.fY) * (fAbove.fX - edge->fAbove.fX); 1235d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com t2 = (fAbove.fY - edge->fAbove.fY) * (edge->fBelow.fX - edge->fAbove.fX); 1236d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } else if (edge->fAbove.fY > fAbove.fY) { 1237d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com t1 = (fBelow.fY - fAbove.fY) * (fAbove.fX - edge->fAbove.fX); 1238d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com t2 = (fAbove.fY - edge->fAbove.fY) * (fBelow.fX - fAbove.fX); 1239d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } else { 1240d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com t1 = fAbove.fX; 1241d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com t2 = edge->fAbove.fX; 1242d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } 1243d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com if (edge->fBelow.fY > fBelow.fY) { 1244d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com b1 = (edge->fBelow.fY - edge->fAbove.fY) * (fBelow.fX - edge->fBelow.fX); 1245d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com b2 = (fBelow.fY - edge->fBelow.fY) * (edge->fBelow.fX - edge->fAbove.fX); 1246d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } else if (edge->fBelow.fY < fBelow.fY) { 1247d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com b1 = (fBelow.fY - fAbove.fY) * (fBelow.fX - edge->fBelow.fX); 1248d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com b2 = (fBelow.fY - edge->fBelow.fY) * (fBelow.fX - fAbove.fX); 1249d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } else { 1250d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com b1 = fBelow.fX; 1251d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com b2 = edge->fBelow.fX; 1252d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } 1253d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com if (fabs(t1 - t2) > fabs(b1 - b2)) { 1254d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com ulps = UlpsDiff(t1, t2); 1255d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } else { 1256d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com ulps = UlpsDiff(b1, b2); 1257d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com } 1258d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#if DEBUG_ADJUST_COINCIDENT 1259d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com SkDebugf("%s this=%d edge=%d ulps=%d\n", __FUNCTION__, ID(), edge->ID(), 1260d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com ulps); 1261d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#endif 1262d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#endif 12632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return ulps >= 0 && ulps <= 32; 12642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1265cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com 12662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com double nextT() const { 1267cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(fTIndex <= fTs->count()); 1268cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return t(fTIndex + 1); 1269cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1270c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 1271cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com double t() const { 12726680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com if (fTIndex == 0) { 12736680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return 0; 12746680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 12756680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com if (fTIndex > fTs->count()) { 12766680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return 1; 1277c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 12786680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return (*fTs)[fTIndex - 1]; 1279c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 1280c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 1281cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com double t(int tIndex) const { 1282cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (tIndex == 0) { 1283cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return 0; 1284cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1285cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (tIndex > fTs->count()) { 1286cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return 1; 1287cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1288cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return (*fTs)[tIndex - 1]; 1289cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1290cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com 12912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: debugging only 1292752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com int ID() const { 12932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return fWorkEdge.fEdge->fID; 12942e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 12952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 12962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.compublic: 12976680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com WorkEdge fWorkEdge; 12986680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com const SkTDArray<double>* fTs; 1299cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkPoint fAbove; 1300cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkPoint fBelow; 13012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if COMPARE_DOUBLE 13022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Point fDAbove; 13032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Point fDBelow; 13042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 13052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ABOVE_BELOW 13062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com double fTAbove; 13072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com double fTBelow; 13082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 1309cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkScalar fYBottom; 13102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int fCoincident; 13116680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com int fTIndex; 13122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool fSkip; // OPTIMIZATION: use bitfields? 13132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool fCloseCall; 1314cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com bool fDone; 13152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool fFixBelow; 1316c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 1317c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 13186680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) { 13196680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com size_t count = activeEdges.count(); 13206680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com for (size_t index = 0; index < count; ++index) { 13216680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com if (edge == activeEdges[index].fWorkEdge.fEdge) { 13226680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return; 13236680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 13246680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 13256680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com ActiveEdge* active = activeEdges.append(); 13266680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com active->init(edge); 13276680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com} 13286680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 13294917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// Find any intersections in the range of active edges. A pair of edges, on 13304917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// either side of another edge, may change the winding contribution for part of 13314917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// the edge. 13322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// Keep horizontal edges just for 13334917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// the purpose of computing when edges change their winding contribution, since 13344917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// this is essentially computing the horizontal intersection. 13352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic void addBottomT(InEdge** currentPtr, InEdge** lastPtr, 13362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge** horizontal) { 13372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge** testPtr = currentPtr - 1; 13382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge* horzEdge = *horizontal; 13392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar left = horzEdge->fLeft; 13402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar bottom = horzEdge->fY; 13412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com while (++testPtr != lastPtr) { 13422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge* test = *testPtr; 13432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (test->fBounds.fBottom <= bottom || test->fBounds.fRight <= left) { 13442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com continue; 13452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 13462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com WorkEdge wt; 13472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com wt.init(test); 13482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com do { 13492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge** sorted = horizontal; 13502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horzEdge = *sorted; 1351f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 1352f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (wt.verb() == SkPath::kLine_Verb) { 1353f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com double wtTs[2]; 13542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int pts = LineIntersect(wt.fPts, horzEdge->fLeft, 13552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horzEdge->fRight, horzEdge->fY, wtTs); 1356f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (pts) { 13572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ADD_BOTTOM_TS 13582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s y=%g wtTs[0]=%g (%g,%g, %g,%g)\n", __FUNCTION__, 13592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horzEdge->fY, wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY, 13602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com wt.fPts[1].fX, wt.fPts[1].fY); 13612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (pts == 2) { 13622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]); 13632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 13642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 13654917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com test->add(wtTs, pts, wt.verbIndex()); 1366f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1367cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } else { 1368cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add all curve types 1369cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(0); 1370f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 13712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horzEdge = *++sorted; 13722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } while (horzEdge->fY == bottom 13732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && horzEdge->fLeft <= test->fBounds.fRight); 13742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } while (wt.advance()); 1375f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1376f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1377f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 1378f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) { 1379cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com InEdge** testPtr = currentPtr - 1; 1380752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com // FIXME: lastPtr should be past the point of interest, so 1381752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com // test below should be lastPtr - 2 1382752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com // that breaks testSimplifyTriangle22, so further investigation is needed 1383cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com while (++testPtr != lastPtr - 1) { 1384cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com InEdge* test = *testPtr; 1385cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com InEdge** nextPtr = testPtr; 1386cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com do { 1387cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com InEdge* next = *++nextPtr; 1388cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (test->cached(next)) { 1389cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com continue; 1390cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1391cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (!Bounds::Intersects(test->fBounds, next->fBounds)) { 1392cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com continue; 1393cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1394f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com WorkEdge wt, wn; 1395f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com wt.init(test); 1396f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com wn.init(next); 1397f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 1398f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (wt.verb() == SkPath::kLine_Verb 1399f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com && wn.verb() == SkPath::kLine_Verb) { 1400f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com double wtTs[2], wnTs[2]; 1401f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int pts = LineIntersect(wt.fPts, wn.fPts, wtTs, wnTs); 1402f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (pts) { 14032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ADD_INTERSECTING_TS 14042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkPoint wtOutPt, wnOutPt; 14052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineXYAtT(wt.fPts, wtTs[0], &wtOutPt); 14062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineXYAtT(wn.fPts, wnTs[0], &wnOutPt); 14072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g) (%d,%d)\n", 14082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com __FUNCTION__, 14092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY, 14102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com wt.fPts[1].fX, wt.fPts[1].fY, wtOutPt.fX, wtOutPt.fY, 14112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com test->fID, next->fID); 14122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (pts == 2) { 14132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]); 14142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 14152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g) (%d,%d)\n", 14162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com __FUNCTION__, 14172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com wnTs[0], wn.fPts[0].fX, wn.fPts[0].fY, 14182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com wn.fPts[1].fX, wn.fPts[1].fY, wnOutPt.fX, wnOutPt.fY, 14192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com test->fID, next->fID); 14202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (pts == 2) { 14212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]); 14222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 14232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 14244917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com test->add(wtTs, pts, wt.verbIndex()); 14254917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com next->add(wnTs, pts, wn.verbIndex()); 1426f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1427cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } else { 1428cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add all combinations of curve types 1429cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(0); 1430f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1431cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } while (wt.bottom() <= wn.bottom() ? wt.advance() : wn.advance()); 1432cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } while (nextPtr != lastPtr); 1433f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1434f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1435f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 14362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic InEdge** advanceEdges(SkTDArray<ActiveEdge>* activeEdges, 14376008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com InEdge** currentPtr, InEdge** lastPtr, SkScalar y) { 14386008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com InEdge** testPtr = currentPtr - 1; 14396008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (++testPtr != lastPtr) { 14406008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if ((*testPtr)->fBounds.fBottom > y) { 14416008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com continue; 14426008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 14432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activeEdges) { 14442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge* test = *testPtr; 14452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ActiveEdge* activePtr = activeEdges->begin() - 1; 14462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ActiveEdge* lastActive = activeEdges->end(); 14472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com while (++activePtr != lastActive) { 14482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activePtr->fWorkEdge.fEdge == test) { 14492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activeEdges->remove(activePtr - activeEdges->begin()); 14502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com break; 14512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 14526008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 14536008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 14546008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (testPtr == currentPtr) { 14556008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ++currentPtr; 14566008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 14576008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 14586008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return currentPtr; 14596008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com} 14606008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 14612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// OPTIMIZE: inline? 14622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic HorizontalEdge** advanceHorizontal(HorizontalEdge** edge, SkScalar y) { 14632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com while ((*edge)->fY < y) { 14642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ++edge; 14652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 14662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return edge; 14672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 14682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 1469f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com// compute bottom taking into account any intersected edges 14702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic SkScalar computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges, 14712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar y, SkScalar bottom) { 1472f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com ActiveEdge* activePtr = activeEdges.begin() - 1; 1473f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com ActiveEdge* lastActive = activeEdges.end(); 1474f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com while (++activePtr != lastActive) { 1475f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const InEdge* test = activePtr->fWorkEdge.fEdge; 1476f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (!test->fContainsIntercepts) { 1477f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com continue; 1478f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1479f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com WorkEdge wt; 1480f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com wt.init(test); 1481f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 1482f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const Intercepts& intercepts = test->fIntercepts[wt.verbIndex()]; 14834917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (intercepts.fTopIntercepts > 1) { 14844917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com SkScalar yTop = wt.fPts[0].fY; 14854917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (yTop > y && bottom > yTop) { 14864917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com bottom = yTop; 14874917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 14884917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 14894917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (intercepts.fBottomIntercepts > 1) { 14904917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com SkScalar yBottom = wt.fPts[wt.verb()].fY; 14914917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (yBottom > y && bottom > yBottom) { 14924917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com bottom = yBottom; 14934917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 14944917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 1495f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const SkTDArray<double>& fTs = intercepts.fTs; 1496f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com size_t count = fTs.count(); 1497f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com for (size_t index = 0; index < count; ++index) { 1498f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (wt.verb() == SkPath::kLine_Verb) { 1499f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar yIntercept = LineYAtT(wt.fPts, fTs[index]); 15006008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (yIntercept > y && bottom > yIntercept) { 1501f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com bottom = yIntercept; 1502f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1503cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } else { 1504cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add all curve types 1505cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(0); 1506f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1507f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1508cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } while (wt.advance()); 1509f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 15102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return bottom; 1511f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1512f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 1513f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic SkScalar findBottom(InEdge** currentPtr, 15142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge** edgeListEnd, SkTDArray<ActiveEdge>* activeEdges, SkScalar y, 15156008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool asFill, InEdge**& testPtr) { 1516f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge* current = *currentPtr; 1517f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar bottom = current->fBounds.fBottom; 1518752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1519f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // find the list of edges that cross y 15206008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com InEdge* test = *testPtr; 15216008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (testPtr != edgeListEnd) { 15226008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkScalar testTop = test->fBounds.fTop; 15236008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (bottom <= testTop) { 1524f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com break; 1525f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 15266008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkScalar testBottom = test->fBounds.fBottom; 1527f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // OPTIMIZATION: Shortening the bottom is only interesting when filling 1528f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // and when the edge is to the left of a longer edge. If it's a framing 1529f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // edge, or part of the right, it won't effect the longer edges. 15306008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (testTop > y) { 15316008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bottom = testTop; 15326008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com break; 15336008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 15346008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (y < testBottom) { 15356008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (bottom > testBottom) { 15366008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bottom = testBottom; 1537f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 15382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activeEdges) { 15392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com addToActive(*activeEdges, test); 15402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1541f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 15426008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com test = *++testPtr; 1543f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1544f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com return bottom; 1545f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1546f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 1547f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic void makeEdgeList(SkTArray<InEdge>& edges, InEdge& edgeSentinel, 1548f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkTDArray<InEdge*>& edgeList) { 1549c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com size_t edgeCount = edges.count(); 1550c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (edgeCount == 0) { 1551c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 1552c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 1553c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (size_t index = 0; index < edgeCount; ++index) { 1554c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *edgeList.append() = &edges[index]; 1555c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 1556c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com edgeSentinel.fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 1557c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *edgeList.append() = &edgeSentinel; 1558cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com QSort<InEdge>(edgeList.begin(), edgeList.end() - 1); 1559f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1560f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 15612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic void makeHorizontalList(SkTDArray<HorizontalEdge>& edges, 15622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge& edgeSentinel, SkTDArray<HorizontalEdge*>& edgeList) { 15632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com size_t edgeCount = edges.count(); 15642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (edgeCount == 0) { 15652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return; 15662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 15672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (size_t index = 0; index < edgeCount; ++index) { 15682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com *edgeList.append() = &edges[index]; 15692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 15702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com edgeSentinel.fLeft = edgeSentinel.fRight = edgeSentinel.fY = SK_ScalarMax; 15712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com *edgeList.append() = &edgeSentinel; 15722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com QSort<HorizontalEdge>(edgeList.begin(), edgeList.end() - 1); 15732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 15746b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com 15756b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.comstatic void skipCoincidence(int lastWinding, int winding, int windingMask, 15766b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com ActiveEdge* activePtr, ActiveEdge* firstCoincident) { 15776b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (((lastWinding & windingMask) == 0) ^ (winding & windingMask) != 0) { 15786b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com return; 15796b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 15802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: ? shouldn't this be if (lastWinding & windingMask) ? 15816b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (lastWinding) { 1582752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#if DEBUG_ADJUST_COINCIDENT 1583752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s edge=%d 1 set skip=false\n", __FUNCTION__, activePtr->ID()); 1584752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#endif 15856b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com activePtr->fSkip = false; 15866b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } else { 1587752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#if DEBUG_ADJUST_COINCIDENT 1588752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s edge=%d 2 set skip=false\n", __FUNCTION__, firstCoincident->ID()); 1589752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#endif 15906b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident->fSkip = false; 15916b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 15926b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com} 15936b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com 15946008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comstatic void sortHorizontal(SkTDArray<ActiveEdge>& activeEdges, 15952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTDArray<ActiveEdge*>& edgeList, SkScalar y) { 15966008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com size_t edgeCount = activeEdges.count(); 15976008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (edgeCount == 0) { 15986008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return; 15996008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 16002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_SORT_HORIZONTAL 1601d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com const int tab = 3; // FIXME: debugging only 16022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s y=%1.9g\n", __FUNCTION__, y); 16032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 16046008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com size_t index; 16056008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com for (index = 0; index < edgeCount; ++index) { 16066008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge& activeEdge = activeEdges[index]; 16072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com do { 16082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activeEdge.calcLeft(y); 16092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // skip segments that don't span y 16102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activeEdge.fAbove != activeEdge.fBelow) { 16112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com break; 16122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activeEdge.fDone) { 16142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_SORT_HORIZONTAL 16152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s edge=%d done\n", tab, "", activeEdge.ID()); 16162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 16172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com goto nextEdge; 16182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_SORT_HORIZONTAL 16202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s edge=%d above==below\n", tab, "", activeEdge.ID()); 16212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 16222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } while (activeEdge.advanceT() || activeEdge.advance()); 16232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_SORT_HORIZONTAL 16242e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s edge=%d above=(%1.9g,%1.9g) (%1.9g) below=(%1.9g,%1.9g)" 16252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com " (%1.9g)\n", tab, "", activeEdge.ID(), 16262e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activeEdge.fAbove.fX, activeEdge.fAbove.fY, activeEdge.fTAbove, 16272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activeEdge.fBelow.fX, activeEdge.fBelow.fY, activeEdge.fTBelow); 16282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 16292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activeEdge.fSkip = activeEdge.fCloseCall = activeEdge.fFixBelow = false; 16306008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com *edgeList.append() = &activeEdge; 16312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comnextEdge: 16322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ; 16336008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 1634cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com QSort<ActiveEdge>(edgeList.begin(), edgeList.end() - 1); 16352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 16362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 16372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// remove coincident edges 16382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// OPTIMIZE: remove edges? This is tricky because the current logic expects 16392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// the winding count to be maintained while skipping coincident edges. In 16402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// addition to removing the coincident edges, the remaining edges would need 16412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// to have a different winding value, possibly different per intercept span. 16422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic SkScalar adjustCoincident(SkTDArray<ActiveEdge*>& edgeList, 16432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int windingMask, SkScalar y, SkScalar bottom, OutEdgeBuilder& outBuilder) 16442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com{ 16452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ADJUST_COINCIDENT 16462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom); 16472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 16482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com size_t edgeCount = edgeList.count(); 16492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (edgeCount == 0) { 16502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return bottom; 16512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16526008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge* activePtr = edgeList[0]; 16532e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com size_t index; 16542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool foundCoincident = false; 16552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int firstIndex = 0; 16562e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (index = 1; index < edgeCount; ++index) { 16572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ActiveEdge* nextPtr = edgeList[index]; 16582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool closeCall = false; 16592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fCoincident = firstIndex; 16602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activePtr->isCoincidentWith(nextPtr, y) 16612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com || (closeCall = activePtr->tooCloseToCall(nextPtr))) { 16622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fSkip = nextPtr->fSkip = foundCoincident = true; 16632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fCloseCall = nextPtr->fCloseCall = closeCall; 16642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } else { 16652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com firstIndex = index; 16662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr = nextPtr; 16682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fCoincident = firstIndex; 16702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (!foundCoincident) { 16712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return bottom; 16722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16736b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com int winding = 0; 16742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr = edgeList[0]; 16756008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com for (index = 1; index < edgeCount; ++index) { 16762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int priorWinding = winding; 16776b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com winding += activePtr->fWorkEdge.winding(); 16786008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge* nextPtr = edgeList[index]; 16792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activePtr->fCoincident == nextPtr->fCoincident) { 1680cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // the coincident edges may not have been sorted above -- advance 1681cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // the edges and resort if needed 1682cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // OPTIMIZE: if sorting is done incrementally as new edges are added 1683cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // and not all at once as is done here, fold this test into the 1684cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // current less than test. 16852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activePtr->fCloseCall ? activePtr->swapClose(nextPtr, 16862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com priorWinding, winding, windingMask) 16872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com : activePtr->swapCoincident(nextPtr, bottom)) { 16884917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com winding -= activePtr->fWorkEdge.winding(); 1689cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]); 1690cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkTSwap<ActiveEdge*>(activePtr, nextPtr); 16914917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com winding += activePtr->fWorkEdge.winding(); 1692cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 16932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16942e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr = nextPtr; 16952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int firstCoincidentWinding = 0; 16972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ActiveEdge* firstCoincident = NULL; 16982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com winding = 0; 16992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr = edgeList[0]; 17002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (index = 1; index < edgeCount; ++index) { 17012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int priorWinding = winding; 17022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com winding += activePtr->fWorkEdge.winding(); 17032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ActiveEdge* nextPtr = edgeList[index]; 17042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activePtr->fCoincident == nextPtr->fCoincident) { 17056b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (!firstCoincident) { 17066b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident = activePtr; 17072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com firstCoincidentWinding = priorWinding; 17082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 17092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activePtr->fCloseCall) { 17102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // If one of the edges has already been added to out as a non 17112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // coincident edge, trim it back to the top of this span 17122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (outBuilder.trimLine(y, activePtr->ID())) { 17132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->addTatYAbove(y); 1714752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if DEBUG_ADJUST_COINCIDENT 1715752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s 1 edge=%d y=%1.9g (was fYBottom=%1.9g)\n", 1716752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com __FUNCTION__, activePtr->ID(), y, activePtr->fYBottom); 1717752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #endif 17182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fYBottom = y; 17192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 17202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (outBuilder.trimLine(y, nextPtr->ID())) { 17212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com nextPtr->addTatYAbove(y); 1722752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if DEBUG_ADJUST_COINCIDENT 1723752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s 2 edge=%d y=%1.9g (was fYBottom=%1.9g)\n", 1724752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com __FUNCTION__, nextPtr->ID(), y, nextPtr->fYBottom); 1725752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #endif 17262e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com nextPtr->fYBottom = y; 17272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 17282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // add missing t values so edges can be the same length 17292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar testY = activePtr->fBelow.fY; 17302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com nextPtr->addTatYBelow(testY); 17312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (bottom > testY && testY > y) { 1732752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if DEBUG_ADJUST_COINCIDENT 1733752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s 3 edge=%d bottom=%1.9g (was bottom=%1.9g)\n", 1734752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com __FUNCTION__, activePtr->ID(), testY, bottom); 1735752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #endif 17362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bottom = testY; 17372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 17382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com testY = nextPtr->fBelow.fY; 17392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->addTatYBelow(testY); 17402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (bottom > testY && testY > y) { 1741752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if DEBUG_ADJUST_COINCIDENT 1742752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s 4 edge=%d bottom=%1.9g (was bottom=%1.9g)\n", 1743752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com __FUNCTION__, nextPtr->ID(), testY, bottom); 1744752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #endif 17452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bottom = testY; 17462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 17476b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 17482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } else if (firstCoincident) { 17492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com skipCoincidence(firstCoincidentWinding, winding, windingMask, 17502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr, firstCoincident); 17516b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident = NULL; 17526b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 17536008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com activePtr = nextPtr; 1754f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 17552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (firstCoincident) { 17566b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com winding += activePtr->fWorkEdge.winding(); 17572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com skipCoincidence(firstCoincidentWinding, winding, windingMask, activePtr, 17586b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident); 17596b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 17602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // fix up the bottom for close call edges. OPTIMIZATION: maybe this could 17612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // be in the loop above, but moved here since loop above reads fBelow and 17622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // it felt unsafe to write it in that loop 17632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (index = 0; index < edgeCount; ++index) { 17642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (edgeList[index])->fixBelow(); 17652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 17662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return bottom; 1767f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 17686680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 1769f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com// stitch edge and t range that satisfies operation 17706008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comstatic void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar y, 1771752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkScalar bottom, int windingMask, bool fill, OutEdgeBuilder& outBuilder) { 1772f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int winding = 0; 17736008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge** activeHandle = edgeList.begin() - 1; 17746008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge** lastActive = edgeList.end(); 17752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const int tab = 7; // FIXME: debugging only 1776cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gShowDebugf) { 17772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom); 1778c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 17796008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (++activeHandle != lastActive) { 17806008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge* activePtr = *activeHandle; 1781f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const WorkEdge& wt = activePtr->fWorkEdge; 1782f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int lastWinding = winding; 1783f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com winding += wt.winding(); 17842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (gShowDebugf) { 17852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s edge=%d lastWinding=%d winding=%d skip=%d close=%d" 17862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ABOVE_BELOW 17872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com " above=%1.9g below=%1.9g" 17882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 17892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com "\n", 17902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com tab-4, "", activePtr->ID(), lastWinding, 17912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com winding, activePtr->fSkip, activePtr->fCloseCall 17922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ABOVE_BELOW 17932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com , activePtr->fTAbove, activePtr->fTBelow 17942e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 17952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ); 17962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1797752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (activePtr->done(bottom)) { 1798752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (gShowDebugf) { 1799752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s fDone=%d || fYBottom=%1.9g >= bottom\n", tab, "", 1800752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com activePtr->fDone, activePtr->fYBottom); 1801cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1802752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com continue; 1803cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1804c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com int opener = (lastWinding & windingMask) == 0; 1805c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com bool closer = (winding & windingMask) == 0; 1806c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkASSERT(!opener | !closer); 1807c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com bool inWinding = opener | closer; 18084917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com SkPoint clippedPts[2]; 18094917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com const SkPoint* clipped = NULL; 18102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if COMPARE_DOUBLE 18112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Line dPoints; 18122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Line clippedDPts; 18132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const _Point* dClipped = NULL; 18142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 1815cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com uint8_t verb = wt.verb(); 1816cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com bool moreToDo, aboveBottom; 1817f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 1818f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com double currentT = activePtr->t(); 18196008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkASSERT(currentT < 1); 1820f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const SkPoint* points = wt.fPts; 1821cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com double nextT; 18226680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com do { 1823cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com nextT = activePtr->nextT(); 1824cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (verb == SkPath::kLine_Verb) { 1825cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: obtuse: want efficient way to say 1826cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // !currentT && currentT != 1 || !nextT && nextT != 1 1827f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (currentT * nextT != 0 || currentT + nextT != 1) { 18286008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // OPTIMIZATION: if !inWinding, we only need 18296008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // clipped[1].fY 1830f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com LineSubDivide(points, currentT, nextT, clippedPts); 1831f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com clipped = clippedPts; 18322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if COMPARE_DOUBLE 18332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineSubDivide(points, currentT, nextT, clippedDPts); 18342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com dClipped = clippedDPts; 18352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 1836f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } else { 1837f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com clipped = points; 18382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if COMPARE_DOUBLE 18392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com dPoints[0].x = SkScalarToDouble(points[0].fX); 18402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com dPoints[0].y = SkScalarToDouble(points[1].fY); 18412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com dPoints[1].x = SkScalarToDouble(points[0].fX); 18422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com dPoints[1].y = SkScalarToDouble(points[1].fY); 18432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com dClipped = dPoints; 18442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 18456680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 1846752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (inWinding && !activePtr->fSkip && (fill ? clipped[0].fY 1847752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com != clipped[1].fY : clipped[0] != clipped[1])) { 1848cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gShowDebugf) { 18492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s line %1.9g,%1.9g %1.9g,%1.9g edge=%d" 18502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com " v=%d t=(%1.9g,%1.9g)\n", tab, "", 18512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com clipped[0].fX, clipped[0].fY, 18522e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com clipped[1].fX, clipped[1].fY, 18532e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->ID(), 18542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fWorkEdge.fVerb 18552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com - activePtr->fWorkEdge.fEdge->fVerbs.begin(), 18562e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com currentT, nextT); 18572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1858752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com outBuilder.addLine(clipped, 1859752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com activePtr->fWorkEdge.fEdge->fID, 1860752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com activePtr->fCloseCall); 18612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } else { 18622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (gShowDebugf) { 18632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s skip %1.9g,%1.9g %1.9g,%1.9g" 18642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com " edge=%d v=%d t=(%1.9g,%1.9g)\n", tab, "", 1865c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com clipped[0].fX, clipped[0].fY, 18662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com clipped[1].fX, clipped[1].fY, 18672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->ID(), 18682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fWorkEdge.fVerb 18692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com - activePtr->fWorkEdge.fEdge->fVerbs.begin(), 18702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com currentT, nextT); 1871c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 18726680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 18732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // by advancing fAbove/fBelow, the next call to sortHorizontal 18742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // will use these values if they're still valid instead of 18752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // recomputing 18762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if COMPARE_DOUBLE 18772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkASSERT((clipped[1].fY > activePtr->fBelow.fY 18782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && bottom >= activePtr->fBelow.fY) 18792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com == (dClipped[1].y > activePtr->fDBelow.y 18802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && bottom >= activePtr->fDBelow.y)); 18812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 18824917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (clipped[1].fY > activePtr->fBelow.fY 18834917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com && bottom >= activePtr->fBelow.fY ) { 18844917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com activePtr->fAbove = activePtr->fBelow; 18854917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com activePtr->fBelow = clipped[1]; 18862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if COMPARE_DOUBLE 18872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fDAbove = activePtr->fDBelow; 18882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fDBelow = dClipped[1]; 18892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 18902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_ABOVE_BELOW 18912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fTAbove = activePtr->fTBelow; 18922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fTBelow = nextT; 18932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 18944917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 1895cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } else { 1896cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add all curve types 1897cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(0); 1898f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1899f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com currentT = nextT; 1900cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com moreToDo = activePtr->advanceT(); 19012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fYBottom = clipped[verb].fY; // was activePtr->fCloseCall ? bottom : 19022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 19032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // clearing the fSkip/fCloseCall bit here means that trailing edges 19042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // fall out of sync, if one edge is long and another is a series of short pieces 19052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // if fSkip/fCloseCall is set, need to recompute coincidence/too-close-to-call 19062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // after advancing 19072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // another approach would be to restrict bottom to smaller part of close call 19082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // maybe this is already happening with coincidence when intersection is computed, 19092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // and needs to be added to the close call computation as well 19102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // this is hard to do because that the bottom is important is not known when 19112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // the lines are intersected; only when the computation for edge sorting is done 19122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // does the need for new bottoms become apparent. 19132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // maybe this is good incentive to scrap the current sort and do an insertion 19142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // sort that can take this into consideration when the x value is computed 19152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 19162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: initialized in sortHorizontal, cleared here as well so 19172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // that next edge is not skipped -- but should skipped edges ever 19182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // continue? (probably not) 1919752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com aboveBottom = clipped[verb].fY < bottom; 1920752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (clipped[0].fY != clipped[verb].fY) { 1921752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com activePtr->fSkip = false; 1922752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com activePtr->fCloseCall = false; 1923752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com aboveBottom &= !activePtr->fCloseCall; 1924752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } else { 1925752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (activePtr->fSkip || activePtr->fCloseCall) { 1926752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("== %1.9g\n", clippedPts[0].fY); 1927752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } 1928752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } 1929cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } while (moreToDo & aboveBottom); 1930cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } while ((moreToDo || activePtr->advance()) & aboveBottom); 1931f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1932f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 19336680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 1934f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comvoid simplify(const SkPath& path, bool asFill, SkPath& simple) { 1935f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 1936f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int windingMask = (path.getFillType() & 1) ? 1 : -1; 1937f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com simple.reset(); 1938f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com simple.setFillType(SkPath::kEvenOdd_FillType); 1939f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // turn path into list of edges increasing in y 1940cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // if an edge is a quad or a cubic with a y extrema, note it, but leave it 1941cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // unbroken. Once we have a list, sort it, then walk the list (walk edges 1942cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // twice that have y extrema's on top) and detect crossings -- look for raw 1943cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // bounds that cross over, then tight bounds that cross 1944f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkTArray<InEdge> edges; 19452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTDArray<HorizontalEdge> horizontalEdges; 19462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdgeBuilder builder(path, asFill, edges, horizontalEdges); 1947f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkTDArray<InEdge*> edgeList; 1948f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge edgeSentinel; 1949f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com makeEdgeList(edges, edgeSentinel, edgeList); 19502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTDArray<HorizontalEdge*> horizontalList; 19512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge horizontalSentinel; 19522e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com makeHorizontalList(horizontalEdges, horizontalSentinel, horizontalList); 1953f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge** currentPtr = edgeList.begin(); 19544917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (!currentPtr) { 19554917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com return; 19564917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 19572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // find all intersections between edges 19582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// beyond looking for horizontal intercepts, we need to know if any active edges 19592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// intersect edges below 'bottom', but above the active edge segment. 19602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// maybe it makes more sense to compute all intercepts before doing anything 19612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// else, since the intercept list is long-lived, at least in the current design. 19622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar y = (*currentPtr)->fBounds.fTop; 19632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge** currentHorizontal = horizontalList.begin(); 19642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com do { 19652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set 19662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar bottom = findBottom(currentPtr, edgeList.end(), 19672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com NULL, y, asFill, lastPtr); 19682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (lastPtr > currentPtr) { 19692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (currentHorizontal) { 19702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if ((*currentHorizontal)->fY < SK_ScalarMax) { 19712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com addBottomT(currentPtr, lastPtr, currentHorizontal); 19722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 19732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com currentHorizontal = advanceHorizontal(currentHorizontal, bottom); 19742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 19752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com addIntersectingTs(currentPtr, lastPtr); 19762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 19772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com y = bottom; 19782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com currentPtr = advanceEdges(NULL, currentPtr, lastPtr, y); 19792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } while (*currentPtr != &edgeSentinel); 1980752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 19812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_DUMP 19822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge** debugPtr = edgeList.begin(); 19832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com do { 19842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (*debugPtr++)->dump(); 19852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } while (*debugPtr != &edgeSentinel); 19862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 1987752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1988f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // walk the sorted edges from top to bottom, computing accumulated winding 1989f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkTDArray<ActiveEdge> activeEdges; 1990f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com OutEdgeBuilder outBuilder(asFill); 19912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com currentPtr = edgeList.begin(); 19922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com y = (*currentPtr)->fBounds.fTop; 1993f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 1994f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set 1995f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar bottom = findBottom(currentPtr, edgeList.end(), 19962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com &activeEdges, y, asFill, lastPtr); 1997752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#if DEBUG_BOTTOM 1998752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s findBottom bottom=%1.9g\n", __FUNCTION__, bottom); 1999752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#endif 2000c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (lastPtr > currentPtr) { 20012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bottom = computeInterceptBottom(activeEdges, y, bottom); 2002752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#if DEBUG_BOTTOM 2003752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s computeInterceptBottom bottom=%1.9g\n", __FUNCTION__, bottom); 2004752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#endif 2005c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkTDArray<ActiveEdge*> activeEdgeList; 20062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com sortHorizontal(activeEdges, activeEdgeList, y); 20072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bottom = adjustCoincident(activeEdgeList, windingMask, y, bottom, 20082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com outBuilder); 2009752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#if DEBUG_BOTTOM 2010752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s adjustCoincident bottom=%1.9g\n", __FUNCTION__, bottom); 2011752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#endif 2012752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com stitchEdge(activeEdgeList, y, bottom, windingMask, asFill, outBuilder); 2013c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 2014c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com y = bottom; 20152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // OPTIMIZATION: as edges expire, InEdge allocations could be released 20162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com currentPtr = advanceEdges(&activeEdges, currentPtr, lastPtr, y); 2017c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } while (*currentPtr != &edgeSentinel); 2018c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // assemble output path from string of pts, verbs 2019f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com outBuilder.bridge(); 2020f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com outBuilder.assemble(simple); 2021c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 2022