EdgeWalker.cpp revision 752b60e633a349c5b9f7bcc6a28b8064fc77bb41
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" 15c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "TSearch.h" 16c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if 0 // set to 1 for no debugging whatsoever 184917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.comstatic bool gShowDebugf = false; // FIXME: remove once debugging is complete 192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_DUMP 0 212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD 0 222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD_INTERSECTING_TS 0 232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD_BOTTOM_TS 0 242e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define COMPARE_DOUBLE 0 252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ABOVE_BELOW 0 262e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ACTIVE_LESS_THAN 0 272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_SORT_HORIZONTAL 0 282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_OUT 0 292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_OUT_LESS_THAN 0 302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADJUST_COINCIDENT 0 31752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#define DEBUG_BOTTOM 0 32752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#else 342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic bool gShowDebugf = true; // FIXME: remove once debugging is complete 352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_DUMP 01 372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD 01 382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD_INTERSECTING_TS 0 392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADD_BOTTOM_TS 0 40752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#define COMPARE_DOUBLE 01 412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ABOVE_BELOW 01 42752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#define DEBUG_ACTIVE_LESS_THAN 01 432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_SORT_HORIZONTAL 01 442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_OUT 01 452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_OUT_LESS_THAN 0 462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define DEBUG_ADJUST_COINCIDENT 1 47752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#define DEBUG_BOTTOM 01 48752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// FIXME: not wild about this -- min delta should be based on size of curve, not t 522e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// #define MIN_T_DELTA 0.000001 532e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// not wild about this either -- for SkScalars backed by floats, would like to 542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// represent deltas in terms of number of significant matching bits 552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#define MIN_PT_DELTA 0.000001 56c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com 576680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic int LineIntersect(const SkPoint a[2], const SkPoint b[2], 58c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com double aRange[2], double bRange[2]) { 59c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 60c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 61c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return intersect(aLine, bLine, aRange, bRange); 62c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 63c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic int LineIntersect(const SkPoint a[2], SkScalar left, SkScalar right, 652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar y, double aRange[2]) { 66c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return horizontalLineIntersect(aLine, left, right, y, aRange); 68c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 69c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 70cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.comstatic void LineXYAtT(const SkPoint a[2], double t, SkPoint* out) { 71cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 72cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com double x, y; 73cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com xy_at_t(aLine, t, x, y); 74cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com out->fX = SkDoubleToScalar(x); 75cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com out->fY = SkDoubleToScalar(y); 76cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com} 77cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com 782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if COMPARE_DOUBLE 792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic void LineXYAtT(const SkPoint a[2], double t, _Point* out) { 802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com xy_at_t(aLine, t, out->x, out->y); 822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if 0 // unused for now 862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic SkScalar LineXAtT(const SkPoint a[2], double t) { 872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com double x; 892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com xy_at_t(aLine, t, x, *(double*) 0); 902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return SkDoubleToScalar(x); 912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 946680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic SkScalar LineYAtT(const SkPoint a[2], double t) { 956680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 966680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com double y; 976680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com xy_at_t(aLine, t, *(double*) 0, y); 986680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return SkDoubleToScalar(y); 996680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com} 1006680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 1016680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic void LineSubDivide(const SkPoint a[2], double startT, double endT, 1026680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkPoint sub[2]) { 1036680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 1046680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com _Line dst; 1056680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub_divide(aLine, startT, endT, dst); 1066680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub[0].fX = SkDoubleToScalar(dst[0].x); 1076680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub[0].fY = SkDoubleToScalar(dst[0].y); 1086680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub[1].fX = SkDoubleToScalar(dst[1].x); 1096680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub[1].fY = SkDoubleToScalar(dst[1].y); 1106680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com} 1116680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 1122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if COMPARE_DOUBLE 1132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic void LineSubDivide(const SkPoint a[2], double startT, double endT, 1142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Line& dst) { 1152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 1162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com sub_divide(aLine, startT, endT, dst); 1172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 1182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 1196680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 120c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com// functions 121c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray); 122c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid simplify(const SkPath& path, bool asFill, SkPath& simple); 123c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com/* 124c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comlist of edges 125c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combounds for edge 126c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comsort 127c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comactive T 128c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 129c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comif a contour's bounds is outside of the active area, no need to create edges 130c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com*/ 131c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 132c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com/* given one or more paths, 133c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com find the bounds of each contour, select the active contours 134c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for each active contour, compute a set of edges 135c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com each edge corresponds to one or more lines and curves 136c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com leave edges unbroken as long as possible 137c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com when breaking edges, compute the t at the break but leave the control points alone 138c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 139c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com */ 140c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 141c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray) { 142c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Iter iter(path, false); 143c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPoint pts[4]; 144c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Verb verb; 145c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkRect bounds; 146c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bounds.setEmpty(); 147c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int count = 0; 148c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 149c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com switch (verb) { 150c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kMove_Verb: 151c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (!bounds.isEmpty()) { 152c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *boundsArray.append() = bounds; 153c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 154c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bounds.set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY); 155c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 0; 156c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 157c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kLine_Verb: 158c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 1; 159c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 160c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kQuad_Verb: 161c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 2; 162c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 163c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kCubic_Verb: 164c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 3; 165c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 166c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kClose_Verb: 167c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 0; 168c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 169c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com default: 170c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkDEBUGFAIL("bad verb"); 171c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 172c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 173c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (int i = 1; i <= count; ++i) { 174c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bounds.growToInclude(pts[i].fX, pts[i].fY); 175c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 176c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 177c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 178c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 179f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic bool extendLine(const SkPoint line[2], const SkPoint& add) { 180f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // FIXME: allow this to extend lines that have slopes that are nearly equal 181f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar dx1 = line[1].fX - line[0].fX; 182f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar dy1 = line[1].fY - line[0].fY; 183f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar dx2 = add.fX - line[0].fX; 184f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar dy2 = add.fY - line[0].fY; 185f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com return dx1 * dy2 == dx2 * dy1; 186f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1876680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 1882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// OPTIMIZATION: this should point to a list of input data rather than duplicating 1892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// the line data here. This would reduce the need to assemble the results. 190f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstruct OutEdge { 191f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com bool operator<(const OutEdge& rh) const { 192cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const SkPoint& first = fPts[0]; 193cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com const SkPoint& rhFirst = rh.fPts[0]; 194f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com return first.fY == rhFirst.fY 195f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com ? first.fX < rhFirst.fX 196f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com : first.fY < rhFirst.fY; 197f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 198752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 199cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkPoint fPts[4]; 2002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int fID; // id of edge generating data 201cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com uint8_t fVerb; // FIXME: not read from everywhere 2022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool fCloseCall; // edge is trimmable if not originally coincident 203f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com}; 204f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 2056680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comclass OutEdgeBuilder { 2066680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.compublic: 207f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com OutEdgeBuilder(bool fill) 208f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com : fFill(fill) { 209f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 210f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 2112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void addLine(const SkPoint line[2], int id, bool closeCall) { 212c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com OutEdge& newEdge = fEdges.push_back(); 213cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com newEdge.fPts[0] = line[0]; 214cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com newEdge.fPts[1] = line[1]; 215cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com newEdge.fVerb = SkPath::kLine_Verb; 2162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com newEdge.fID = id; 2172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com newEdge.fCloseCall = closeCall; 2182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 219752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 2202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool trimLine(SkScalar y, int id) { 2212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com size_t count = fEdges.count(); 2222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com while (count-- != 0) { 2232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com OutEdge& edge = fEdges[count]; 2242e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (edge.fID != id) { 2252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com continue; 2262e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 2272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (edge.fCloseCall) { 2282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return false; 2292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 2302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkASSERT(edge.fPts[0].fY <= y); 2312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (edge.fPts[1].fY <= y) { 2322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com continue; 2332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 2342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com edge.fPts[1].fX = edge.fPts[0].fX + (y - edge.fPts[0].fY) 2352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com * (edge.fPts[1].fX - edge.fPts[0].fX) 2362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com / (edge.fPts[1].fY - edge.fPts[0].fY); 2372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com edge.fPts[1].fY = y; 2382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (gShowDebugf) { 2392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s edge=%d %1.9g,%1.9g\n", __FUNCTION__, id, 2402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com edge.fPts[1].fX, y); 2412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 2422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return true; 2432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 2442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return false; 245f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 246f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 247f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com void assemble(SkPath& simple) { 2486008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com size_t listCount = fEdges.count(); 2496008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (listCount == 0) { 2506008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return; 2516008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 252f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 2536008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com size_t listIndex = 0; 2546008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int advance = 1; 2556008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (listIndex < listCount && fTops[listIndex] == 0) { 2566008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ++listIndex; 257f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 2586008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (listIndex >= listCount) { 2596008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com break; 260f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 2614917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com int closeEdgeIndex = -listIndex - 1; 262cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkPoint firstPt, lastLine[2]; 2636008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool doMove = true; 2646008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int edgeIndex; 2656008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com do { 266cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkPoint* ptArray = fEdges[listIndex].fPts; 267cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com uint8_t verb = fEdges[listIndex].fVerb; 268cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkPoint* start, * end; 2696008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (advance < 0) { 270cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com start = &ptArray[verb]; 271cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com end = &ptArray[0]; 2726008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 273cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com start = &ptArray[0]; 274cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com end = &ptArray[verb]; 275f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 276cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com switch (verb) { 277cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com case SkPath::kLine_Verb: 278cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com bool gap; 279cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (doMove) { 280cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com firstPt = *start; 281cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com simple.moveTo(start->fX, start->fY); 282cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gShowDebugf) { 283cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkDebugf("%s moveTo (%g,%g)\n", __FUNCTION__, 284cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com start->fX, start->fY); 285cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 286cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com lastLine[0] = *start; 287cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com lastLine[1] = *end; 288cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com doMove = false; 289cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com break; 290cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 291cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com gap = lastLine[1] != *start; 292cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gap) { 293cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(fFill && lastLine[1].fY == start->fY); 294cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com simple.lineTo(lastLine[1].fX, lastLine[1].fY); 295cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gShowDebugf) { 296cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkDebugf("%s lineTo x (%g,%g)\n", __FUNCTION__, 297cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com lastLine[1].fX, lastLine[1].fY); 298cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 299cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 300cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gap || !extendLine(lastLine, *end)) { 301cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(lastLine[1] == *start || 302cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com (fFill && lastLine[1].fY == start->fY)); 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 4502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY 4512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com != right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY) { 4522e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com *fMismatches.append() = leftIndex; 4532e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (rightPtr == lastPtr) { 4542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com *fMismatches.append() = rightIndex; 4552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 4562e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com pairUp = false; 4572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 4582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #else 459cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(left.fPts[leftIndex < 0 ? 0 : left.fVerb].fY 460cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com == right.fPts[rightIndex < 0 ? 0 : right.fVerb].fY); 4612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 462cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 463cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (pairUp) { 4646008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (leftIndex < 0) { 4656008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fTops[leftOutIndex] = rightIndex; 4666008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 4676008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fBottoms[leftOutIndex] = rightIndex; 4686008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 4696008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (rightIndex < 0) { 4706008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fTops[rightOutIndex] = leftIndex; 4716008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 4726008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fBottoms[rightOutIndex] = leftIndex; 473f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 4746008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ++rightPtr; 475f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 476f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com leftPtr = rightPtr; 4776680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 4782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_OUT 4792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int* mismatch = fMismatches.begin(); 4802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com while (mismatch != fMismatches.end()) { 4812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int leftIndex = *mismatch++; 4822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int leftOutIndex = abs(leftIndex) - 1; 4832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const OutEdge& left = fEdges[leftOutIndex]; 4842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const SkPoint& leftPt = left.fPts[leftIndex < 0 ? 0 : left.fVerb]; 4852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s left=%d %s (%1.9g,%1.9g)\n", 4862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com __FUNCTION__, left.fID, leftIndex < 0 ? "top" : "bot", 4872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com leftPt.fX, leftPt.fY); 4882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 4892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkASSERT(fMismatches.count() == 0); 4902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 4916680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 4926680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 4936008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comprotected: 4946680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTArray<OutEdge> fEdges; 4956008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkTDArray<int> fTops; 4966008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkTDArray<int> fBottoms; 497f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com bool fFill; 4982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_OUT 4992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTDArray<int> fMismatches; 5002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 5016680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com}; 5026680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 503c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com// Bounds, unlike Rect, does not consider a vertical line to be empty. 504c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comstruct Bounds : public SkRect { 505c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com static bool Intersects(const Bounds& a, const Bounds& b) { 506c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return a.fLeft <= b.fRight && b.fLeft <= a.fRight && 507c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com a.fTop <= b.fBottom && b.fTop <= a.fBottom; 508c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 509752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 5106008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool isEmpty() { 5116008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return fLeft > fRight || fTop > fBottom 5126008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com || fLeft == fRight && fTop == fBottom 5136008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com || isnan(fLeft) || isnan(fRight) 5146008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com || isnan(fTop) || isnan(fBottom); 5156008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 516c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 517c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 5184917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.comclass Intercepts { 5194917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.compublic: 5204917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com Intercepts() 5214917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com : fTopIntercepts(0) 5224917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com , fBottomIntercepts(0) { 5234917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 524752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 5252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_DUMP 5262e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: pass current verb as parameter 5272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void dump(const SkPoint* pts) { 5282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const char className[] = "Intercepts"; 5292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const int tab = 8; 5302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (int i = 0; i < fTs.count(); ++i) { 5312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkPoint out; 5322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineXYAtT(pts, fTs[i], &out); 533752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s.fTs[%d]=%1.9g (%1.9g,%1.9g)\n", tab + sizeof(className), 5342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, i, fTs[i], out.fX, out.fY); 5352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 5362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fTopIntercepts=%d\n", tab + sizeof(className), 5372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, fTopIntercepts); 5382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fBottomIntercepts=%d\n", tab + sizeof(className), 5392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, fBottomIntercepts); 5402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 5412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 5422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 543c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkTDArray<double> fTs; 5444917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com int fTopIntercepts; 5454917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com int fBottomIntercepts; 546c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 547c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 5482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstruct HorizontalEdge { 5492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool operator<(const HorizontalEdge& rh) const { 5502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return fY == rh.fY ? fLeft == rh.fLeft ? fRight < rh.fRight 5512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com : fLeft < rh.fLeft : fY < rh.fY; 5522e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 5532e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 5542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_DUMP 5552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void dump() { 5562e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const char className[] = "HorizontalEdge"; 5572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const int tab = 4; 558752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s.fLeft=%1.9g\n", tab + sizeof(className), className, fLeft); 559752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s.fRight=%1.9g\n", tab + sizeof(className), className, fRight); 560752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s.fY=%1.9g\n", tab + sizeof(className), className, fY); 5612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 5622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 5632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 5642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar fLeft; 5652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar fRight; 5662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar fY; 5672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com}; 5682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 5696680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstruct InEdge { 5706680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool operator<(const InEdge& rh) const { 571c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return fBounds.fTop == rh.fBounds.fTop 572c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com ? fBounds.fLeft < rh.fBounds.fLeft 573c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com : fBounds.fTop < rh.fBounds.fTop; 574c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 575c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 5762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // Avoid collapsing t values that are close to the same since 5772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // we walk ts to describe consecutive intersections. Since a pair of ts can 5782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // be nearly equal, any problems caused by this should be taken care 5792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // of later. 5802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int add(double* ts, size_t count, ptrdiff_t verbIndex) { 581c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // FIXME: in the pathological case where there is a ton of intercepts, binary search? 5826008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool foundIntercept = false; 5832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int insertedAt = -1; 5846008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com Intercepts& intercepts = fIntercepts[verbIndex]; 585c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (size_t index = 0; index < count; ++index) { 586c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com double t = ts[index]; 5874917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (t <= 0) { 5884917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com fContainsIntercepts |= ++intercepts.fTopIntercepts > 1; 5894917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com continue; 5904917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 5914917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (t >= 1) { 5924917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com fContainsIntercepts |= ++intercepts.fBottomIntercepts > 1; 5936008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com continue; 5946008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 5956008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com foundIntercept = true; 596c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com size_t tCount = intercepts.fTs.count(); 5972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com double delta; 598c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (size_t idx2 = 0; idx2 < tCount; ++idx2) { 599c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (t <= intercepts.fTs[idx2]) { 6002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: ? if (t < intercepts.fTs[idx2]) // failed 6012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com delta = intercepts.fTs[idx2] - t; 602cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (delta > 0) { 6032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com insertedAt = idx2; 604c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *intercepts.fTs.insert(idx2) = t; 605c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 6062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com goto nextPt; 607c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 608c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 6092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (tCount == 0 || (delta = t - intercepts.fTs[tCount - 1]) > 0) { 6102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com insertedAt = tCount; 611c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *intercepts.fTs.append() = t; 612c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 6132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com nextPt: 6142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ; 615c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 6164917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com fContainsIntercepts |= foundIntercept; 6172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return insertedAt; 618c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 619c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 6206680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool cached(const InEdge* edge) { 621c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // FIXME: in the pathological case where there is a ton of edges, binary search? 622c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com size_t count = fCached.count(); 623c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (size_t index = 0; index < count; ++index) { 624c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (edge == fCached[index]) { 625c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return true; 626c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 627c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (edge < fCached[index]) { 628c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *fCached.insert(index) = edge; 629c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return false; 630c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 631c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 632c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *fCached.append() = edge; 633c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return false; 634c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 635c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 6362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void complete(signed char winding, int id) { 637c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPoint* ptPtr = fPts.begin(); 638c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPoint* ptLast = fPts.end(); 639c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (ptPtr == ptLast) { 640c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkDebugf("empty edge\n"); 641c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkASSERT(0); 642c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // FIXME: delete empty edge? 643c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 644c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 645c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fBounds.set(ptPtr->fX, ptPtr->fY, ptPtr->fX, ptPtr->fY); 646c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com ++ptPtr; 647c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com while (ptPtr != ptLast) { 648c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fBounds.growToInclude(ptPtr->fX, ptPtr->fY); 649c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com ++ptPtr; 650c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 6516008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fIntercepts.push_back_n(fVerbs.count()); 6526680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top 6536680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com size_t index; 6546680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com size_t last = fPts.count() - 1; 6556680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com for (index = 0; index < last; ++index, --last) { 6566680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTSwap<SkPoint>(fPts[index], fPts[last]); 6576680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 6586680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com last = fVerbs.count() - 1; 6596680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com for (index = 0; index < last; ++index, --last) { 6606680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTSwap<uint8_t>(fVerbs[index], fVerbs[last]); 6616680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 6626680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 6636680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fContainsIntercepts = false; 6642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fID = id; 6652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 6662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 6672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_DUMP 6682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void dump() { 6692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int i; 6702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const char className[] = "InEdge"; 6712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const int tab = 4; 6722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("InEdge %p (edge=%d)\n", this, fID); 6732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (i = 0; i < fCached.count(); ++i) { 6742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fCached[%d]=0x%08x\n", tab + sizeof(className), 6752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, i, fCached[i]); 6762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 6772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com uint8_t* verbs = fVerbs.begin(); 6782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkPoint* pts = fPts.begin(); 6792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (i = 0; i < fIntercepts.count(); ++i) { 6802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fIntercepts[%d]:\n", tab + sizeof(className), 6812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, i); 6822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: take current verb into consideration 6832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fIntercepts[i].dump(pts); 6842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com pts += *verbs++; 6852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 6862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (i = 0; i < fPts.count(); ++i) { 687752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s.fPts[%d]=(%1.9g,%1.9g)\n", tab + sizeof(className), 6882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, i, fPts[i].fX, fPts[i].fY); 6892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 6902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (i = 0; i < fVerbs.count(); ++i) { 6912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fVerbs[%d]=%d\n", tab + sizeof(className), 6922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, i, fVerbs[i]); 6932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 694752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s.fBounds=(%1.9g. %1.9g, %1.9g, %1.9g)\n", tab + sizeof(className), 6952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, fBounds.fLeft, fBounds.fTop, 6962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fBounds.fRight, fBounds.fBottom); 6972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fWinding=%d\n", tab + sizeof(className), className, 6982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fWinding); 6992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s.fContainsIntercepts=%d\n", tab + sizeof(className), 7002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com className, fContainsIntercepts); 701c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 7022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 703c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 704c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // temporary data : move this to a separate struct? 7056680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTDArray<const InEdge*> fCached; // list of edges already intercepted 706c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkTArray<Intercepts> fIntercepts; // one per verb 7074917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com 708c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // persistent data 709c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkTDArray<SkPoint> fPts; 710c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkTDArray<uint8_t> fVerbs; 711c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com Bounds fBounds; 7122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int fID; 713c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com signed char fWinding; 7146680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool fContainsIntercepts; 715c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 716c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 7176680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comclass InEdgeBuilder { 718c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.compublic: 719c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 7202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comInEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges, 7212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTDArray<HorizontalEdge>& horizontalEdges) 722c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com : fPath(path) 723c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com , fCurrentEdge(NULL) 724c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com , fEdges(edges) 7252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com , fID(0) 7262e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com , fHorizontalEdges(horizontalEdges) 727c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com , fIgnoreHorizontal(ignoreHorizontal) 728c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com{ 729c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com walk(); 730c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 731c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 732c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comprotected: 733c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 734c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid addEdge() { 735f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkASSERT(fCurrentEdge); 736c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fCurrentEdge->fPts.append(fPtCount - fPtOffset, &fPts[fPtOffset]); 737c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fPtOffset = 1; 738c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *fCurrentEdge->fVerbs.append() = fVerb; 739c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 740c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 7416008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.combool complete() { 7426008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (fCurrentEdge && fCurrentEdge->fVerbs.count()) { 7432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fCurrentEdge->complete(fWinding, ++fID); 7446008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fCurrentEdge = NULL; 7456008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return true; 7466008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 7476008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return false; 7486008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com} 7496008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 750c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comint direction(int count) { 751c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fPtCount = count; 7522e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (fIgnoreHorizontal && isHorizontal()) { 753c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return 0; 754c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 755c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int last = count - 1; 756c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return fPts[0].fY == fPts[last].fY 7576680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com ? fPts[0].fX == fPts[last].fX ? 0 : fPts[0].fX < fPts[last].fX 7586680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com ? 1 : -1 : fPts[0].fY < fPts[last].fY ? 1 : -1; 759c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 760c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 761c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool isHorizontal() { 762c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkScalar y = fPts[0].fY; 763c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (int i = 1; i < fPtCount; ++i) { 764c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (fPts[i].fY != y) { 765c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return false; 766c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 767c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 768c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return true; 769c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 770c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 771c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid startEdge() { 7726008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (!fCurrentEdge) { 7736008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fCurrentEdge = fEdges.push_back_n(1); 7746008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 775c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fWinding = 0; 776c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fPtOffset = 0; 777c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 778c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 779c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid walk() { 780c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Iter iter(fPath, true); 7812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int winding = 0; 782c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com while ((fVerb = iter.next(fPts)) != SkPath::kDone_Verb) { 783c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com switch (fVerb) { 784c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kMove_Verb: 785c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com startEdge(); 786c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com continue; 787c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kLine_Verb: 788c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com winding = direction(2); 789c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 790c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kQuad_Verb: 791c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com winding = direction(3); 792c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 793c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kCubic_Verb: 794c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com winding = direction(4); 795c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 796c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kClose_Verb: 797f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkASSERT(fCurrentEdge); 7986008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com complete(); 799c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com continue; 800c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com default: 801c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkDEBUGFAIL("bad verb"); 802c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 803c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 8042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (winding == 0) { 8052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge* horizontalEdge = fHorizontalEdges.append(); 8062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: for degenerate quads and cubics, compute x extremes 8072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horizontalEdge->fLeft = fPts[0].fX; 8082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horizontalEdge->fRight = fPts[fVerb].fX; 8092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horizontalEdge->fY = fPts[0].fY; 8102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (horizontalEdge->fLeft > horizontalEdge->fRight) { 8112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTSwap<SkScalar>(horizontalEdge->fLeft, horizontalEdge->fRight); 8122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 8136008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (complete()) { 8146008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com startEdge(); 8156008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 816c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com continue; 817c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 818c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (fWinding + winding == 0) { 819c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // FIXME: if prior verb or this verb is a horizontal line, reverse 820c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // it instead of starting a new edge 821f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkASSERT(fCurrentEdge); 822cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (complete()) { 823cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com startEdge(); 824cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 825c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 826c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fWinding = winding; 827c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com addEdge(); 828c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 8296b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (!complete()) { 8306b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (fCurrentEdge) { 8316b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com fEdges.pop_back(); 8326b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 8336b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 834c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 835c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 836c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comprivate: 837c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com const SkPath& fPath; 8386680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com InEdge* fCurrentEdge; 8396680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTArray<InEdge>& fEdges; 8402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTDArray<HorizontalEdge>& fHorizontalEdges; 841c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPoint fPts[4]; 842c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Verb fVerb; 843c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int fPtCount; 844c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int fPtOffset; 8452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int fID; 846c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int8_t fWinding; 847c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bool fIgnoreHorizontal; 848c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 849c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 8506680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstruct WorkEdge { 851c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkScalar bottom() const { 8526680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return fPts[verb()].fY; 853c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 854c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 8556680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com void init(const InEdge* edge) { 8566680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fEdge = edge; 8576680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fPts = edge->fPts.begin(); 8586680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fVerb = edge->fVerbs.begin(); 859c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 860c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 861cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com bool advance() { 8626680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkASSERT(fVerb < fEdge->fVerbs.end()); 8636680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fPts += *fVerb++; 8646680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return fVerb != fEdge->fVerbs.end(); 865c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 866752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 867cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkPath::Verb lastVerb() const { 868cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkASSERT(fVerb > fEdge->fVerbs.begin()); 869cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return (SkPath::Verb) fVerb[-1]; 870cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 871cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com 872c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 873c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Verb verb() const { 874c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return (SkPath::Verb) *fVerb; 875c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 876c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 8776008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ptrdiff_t verbIndex() const { 8786680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return fVerb - fEdge->fVerbs.begin(); 8796680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 880752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 8816680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com int winding() const { 8826680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return fEdge->fWinding; 883c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 884c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 8856680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com const InEdge* fEdge; 886c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com const SkPoint* fPts; 887c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com const uint8_t* fVerb; 888c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 889c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 8906680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com// always constructed with SkTDArray because new edges are inserted 8916680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com// this may be a inappropriate optimization, suggesting that a separate array of 8926680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com// ActiveEdge* may be faster to insert and search 893cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com 894cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com// OPTIMIZATION: Brian suggests that global sorting should be unnecessary, since 895cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com// as active edges are introduced, only local sorting should be required 8962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comclass ActiveEdge { 8972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.compublic: 898cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // OPTIMIZATION: fold return statements into one 8996008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool operator<(const ActiveEdge& rh) const { 900cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (rh.fAbove.fY - fAbove.fY > fBelow.fY - rh.fAbove.fY 901cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com && fBelow.fY < rh.fBelow.fY 902cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com || fAbove.fY - rh.fAbove.fY < rh.fBelow.fY - fAbove.fY 903cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com && rh.fBelow.fY < fBelow.fY) { 904cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // FIXME: need to compute distance, not check for points equal 905cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com const SkPoint& check = rh.fBelow.fY <= fBelow.fY 906cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com && fBelow != rh.fBelow ? rh.fBelow : 907cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com rh.fAbove; 9082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_ACTIVE_LESS_THAN 9092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s 1 %c %cthis (edge=%d) {%g,%g %g,%g}" 9102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com " < rh (edge=%d) {%g,%g %g,%g} upls=(%d)\n", __FUNCTION__, 9112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com rh.fBelow.fY <= fBelow.fY && fBelow != rh.fBelow ? 'B' : 'A', 9122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) 9132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX) ? ' ' 9142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com : '!', ID(), fAbove.fX, fAbove.fY, fBelow.fX, fBelow.fY, 9152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com rh.ID(), rh.fAbove.fX, rh.fAbove.fY, rh.fBelow.fX, rh.fBelow.fY, 9162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com UlpsDiff((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX), 9172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX))); 9182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 919752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if COMPARE_DOUBLE 920752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkASSERT(((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) 921752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX)) 922752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com == ((check.fY - fDAbove.y) * (fDBelow.x - fDAbove.x) 923752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com < (fDBelow.y - fDAbove.y) * (check.fX - fDAbove.x))); 9242e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 925cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return (check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX) 926cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com < (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX); 927cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 928cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // FIXME: need to compute distance, not check for points equal 929cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com const SkPoint& check = fBelow.fY <= rh.fBelow.fY 930cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com && fBelow != rh.fBelow ? fBelow : fAbove; 9312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_ACTIVE_LESS_THAN 9322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s 2 %c %cthis (edge=%d) {%g,%g %g,%g}" 933752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com " < rh (edge=%d) {%g,%g %g,%g} upls=(%d) (%d,%d)\n", __FUNCTION__, 934752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com fBelow.fY <= rh.fBelow.fY && fBelow != rh.fBelow ? 'B' : 'A', 9352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) 9362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.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((rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX), 940752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX)), 941752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com UlpsDiff(fBelow.fX, rh.fBelow.fX), UlpsDiff(fBelow.fY, rh.fBelow.fY)); 9422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 943752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if COMPARE_DOUBLE 944752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkASSERT(((rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) 945752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX)) 946752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com == ((rh.fDBelow.y - rh.fDAbove.y) * (check.fX - rh.fDAbove.x) 947752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com < (check.fY - rh.fDAbove.y) * (rh.fDBelow.x - rh.fDAbove.x))); 9482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 949cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return (rh.fBelow.fY - rh.fAbove.fY) * (check.fX - rh.fAbove.fX) 950cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com < (check.fY - rh.fAbove.fY) * (rh.fBelow.fX - rh.fAbove.fX); 9516008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 952752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 9532e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // If a pair of edges are nearly coincident for some span, add a T in the 9542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // edge so it can be shortened to match the other edge. Note that another 9552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // approach is to trim the edge after it is added to the OutBuilder list -- 9562e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: since this has no effect if the edge is already done (i.e., 9572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // fYBottom >= y) maybe this can only be done by calling trimLine later. 9582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void addTatYBelow(SkScalar y) { 9592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (fBelow.fY <= y || fYBottom >= y) { 9602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return; 9612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 9622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com addTatYInner(y); 9632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fFixBelow = true; 9642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 965752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 9662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void addTatYAbove(SkScalar y) { 9672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (fBelow.fY <= y) { 9682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return; 9692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 9702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com addTatYInner(y); 9712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 9722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 9732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void addTatYInner(SkScalar y) { 974752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (fWorkEdge.fPts[0].fY > y) { 975752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com backup(y); 976752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } 9772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar left = fWorkEdge.fPts[0].fX; 9782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar right = fWorkEdge.fPts[1].fX; 9792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (left > right) { 9802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTSwap(left, right); 9812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 982752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com double ts[2]; 9832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int pts = LineIntersect(fWorkEdge.fPts, left, right, y, ts); 9842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkASSERT(pts == 1); 9852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // An ActiveEdge or WorkEdge has no need to modify the T values computed 9862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // in the InEdge, except in the following case. If a pair of edges are 9872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // nearly coincident, this may not be detected when the edges are 9882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // intersected. Later, when sorted, and this near-coincidence is found, 9892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // an additional t value must be added, requiring the cast below. 9902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge* writable = const_cast<InEdge*>(fWorkEdge.fEdge); 9912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int insertedAt = writable->add(ts, pts, fWorkEdge.verbIndex()); 992752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if DEBUG_ADJUST_COINCIDENT 993752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s edge=%d y=%1.9g t=%1.9g\n", __FUNCTION__, ID(), y, ts[0]); 994752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #endif 9952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (insertedAt >= 0) { 9962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (insertedAt + 1 < fTIndex) { 9972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkASSERT(insertedAt + 2 == fTIndex); 9982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com --fTIndex; 9992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 10002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 10012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 10026008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 1003cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com bool advanceT() { 1004cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkASSERT(fTIndex <= fTs->count()); 1005cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return ++fTIndex <= fTs->count(); 1006cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 10072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 1008cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com bool advance() { 1009cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // FIXME: flip sense of next 1010cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com bool result = fWorkEdge.advance(); 1011cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com fDone = !result; 1012cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com initT(); 1013cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return result; 1014cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1015752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1016752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com void backup(SkScalar y) { 1017752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com do { 1018752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkASSERT(fWorkEdge.fEdge->fVerbs.begin() < fWorkEdge.fVerb); 1019752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com fWorkEdge.fPts -= *--fWorkEdge.fVerb; 1020752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkASSERT(fWorkEdge.fEdge->fPts.begin() <= fWorkEdge.fPts); 1021752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } while (fWorkEdge.fPts[0].fY >= y); 1022752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com initT(); 1023752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com fTIndex = fTs->count() + 1; 1024752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } 1025752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1026cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com void calcLeft(SkScalar y) { 1027cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // OPTIMIZE: put a kDone_Verb at the end of the verb list? 10284917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (fDone || fBelow.fY > y) { 1029cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return; // nothing to do; use last 10304917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 1031cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com calcLeft(); 1032752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (fAbove.fY == fBelow.fY) { 1033752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s edge=%d fAbove.fY != fBelow.fY %1.9g\n", __FUNCTION__, 1034752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com ID(), fAbove.fY); 1035752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } 1036cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1037752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1038cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com void calcLeft() { 1039cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com switch (fWorkEdge.verb()) { 1040cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com case SkPath::kLine_Verb: { 1041cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // OPTIMIZATION: if fXAbove, fXBelow have already been computed 1042cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // for the fTIndex, don't do it again 1043cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // For identical x, this lets us know which edge is first. 1044cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // If both edges have T values < 1, check x at next T (fXBelow). 1045cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com int add = (fTIndex <= fTs->count()) - 1; 1046cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com double tAbove = t(fTIndex + add); 1047cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // OPTIMIZATION: may not need Y 1048cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove); 1049cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com double tBelow = t(fTIndex - ~add); 1050cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow); 10512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkASSERT(tAbove != tBelow); 1052752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com while (fAbove.fY == fBelow.fY) { 1053752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (add < 0) { 1054752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com add -= 1; 1055752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkASSERT(fTIndex + add >= 0); 1056752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com tAbove = t(fTIndex + add); 1057752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com LineXYAtT(fWorkEdge.fPts, tAbove, &fAbove); 1058752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } else { 1059752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com add += 1; 1060752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkASSERT(fTIndex - ~add <= fTs->count() + 1); 1061752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com tBelow = t(fTIndex - ~add); 1062752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com LineXYAtT(fWorkEdge.fPts, tBelow, &fBelow); 1063752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } 10642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 10652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if COMPARE_DOUBLE 10662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineXYAtT(fWorkEdge.fPts, tAbove, &fDAbove); 10672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineXYAtT(fWorkEdge.fPts, tBelow, &fDBelow); 10682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 10692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_ABOVE_BELOW 10702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fTAbove = tAbove; 10712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fTBelow = tBelow; 10722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 1073cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com break; 1074cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1075cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com default: 1076cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add support for all curve types 1077cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(0); 1078cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 10796008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 10806008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 1081752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com bool done(SkScalar bottom) const { 1082752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com return fDone || fYBottom >= bottom; 1083cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1084752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 10852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com void fixBelow() { 10862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (fFixBelow) { 10872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineXYAtT(fWorkEdge.fPts, nextT(), &fBelow); 10882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com fFixBelow = false; 10892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 10902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 10912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 10926680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com void init(const InEdge* edge) { 10936680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fWorkEdge.init(edge); 10946680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com initT(); 10954917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com fBelow.fY = SK_ScalarMin; 1096cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com fDone = false; 1097cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com fYBottom = SK_ScalarMin; 10986680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 1099752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 11006680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com void initT() { 11016008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front(); 11026008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count()); 11036008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com const Intercepts* interceptPtr = &intercepts + fWorkEdge.verbIndex(); 11046008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fTs = &interceptPtr->fTs; 11056008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // the above is conceptually the same as 11066008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // fTs = &fWorkEdge.fEdge->fIntercepts[fWorkEdge.verbIndex()].fTs; 11076008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // but templated arrays don't allow returning a pointer to the end() element 11086680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fTIndex = 0; 11096680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 1110752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1111cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // OPTIMIZATION: record if two edges are coincident when the are intersected 1112cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // It's unclear how to do this -- seems more complicated than recording the 1113cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // t values, since the same t values could exist intersecting non-coincident 1114cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // edges. 1115cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com bool isCoincidentWith(const ActiveEdge* edge, SkScalar y) const { 1116752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 11172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (!fAbove.equalsWithinTolerance(edge->fAbove, MIN_PT_DELTA) 11182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com || !fBelow.equalsWithinTolerance(edge->fBelow, MIN_PT_DELTA)) { 1119cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return false; 1120cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1121cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com uint8_t verb = fDone ? fWorkEdge.lastVerb() : fWorkEdge.verb(); 1122cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com uint8_t edgeVerb = edge->fDone ? edge->fWorkEdge.lastVerb() 1123cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com : edge->fWorkEdge.verb(); 1124cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (verb != edgeVerb) { 1125cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return false; 1126cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1127cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com switch (verb) { 1128cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com case SkPath::kLine_Verb: { 11294917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com return true; 1130cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1131cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com default: 1132cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add support for all curve types 1133cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(0); 1134cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1135cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return false; 1136cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1137752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 11382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // The shortest close call edge should be moved into a position where 11392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // it contributes if the winding is transitioning to or from zero. 11402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool swapClose(const ActiveEdge* next, int prev, int wind, int mask) const { 11412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if ((prev & mask) == 0 || (wind & mask) == 0) { 11422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return next->fBelow.fY < fBelow.fY; 11432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 11442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int nextWinding = wind + next->fWorkEdge.winding(); 11452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if ((nextWinding & mask) == 0) { 11462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return fBelow.fY < next->fBelow.fY; 11472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 11482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return false; 11492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1150752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1151cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com bool swapCoincident(const ActiveEdge* edge, SkScalar bottom) const { 1152cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (fBelow.fY >= bottom || fDone || edge->fDone) { 1153cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return false; 1154cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1155cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com ActiveEdge thisWork = *this; 1156cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com ActiveEdge edgeWork = *edge; 1157cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com while ((thisWork.advanceT() || thisWork.advance()) 1158cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com && (edgeWork.advanceT() || edgeWork.advance())) { 1159cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com thisWork.calcLeft(); 1160cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com edgeWork.calcLeft(); 1161cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (thisWork < edgeWork) { 1162cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return false; 1163cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1164cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (edgeWork < thisWork) { 1165cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return true; 1166cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1167cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1168cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return false; 1169cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1170752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 11712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool tooCloseToCall(const ActiveEdge* edge) const { 11722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int ulps; 11732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: don't compare points for equality 11742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // OPTIMIZATION: refactor to make one call to UlpsDiff 11752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (edge->fAbove.fY - fAbove.fY > fBelow.fY - edge->fAbove.fY 11762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && fBelow.fY < edge->fBelow.fY 11772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com || fAbove.fY - edge->fAbove.fY < edge->fBelow.fY - fAbove.fY 11782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && edge->fBelow.fY < fBelow.fY) { 11792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const SkPoint& check = edge->fBelow.fY <= fBelow.fY 11802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && fBelow != edge->fBelow ? edge->fBelow : 11812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com edge->fAbove; 11822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ulps = UlpsDiff((check.fY - fAbove.fY) * (fBelow.fX - fAbove.fX), 11832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (fBelow.fY - fAbove.fY) * (check.fX - fAbove.fX)); 11842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } else { 11852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const SkPoint& check = fBelow.fY <= edge->fBelow.fY 11862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && fBelow != edge->fBelow ? fBelow : fAbove; 11872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ulps = UlpsDiff((edge->fBelow.fY - edge->fAbove.fY) 11882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com * (check.fX - edge->fAbove.fX), 11892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (check.fY - edge->fAbove.fY) 11902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com * (edge->fBelow.fX - edge->fAbove.fX)); 11912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 11922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return ulps >= 0 && ulps <= 32; 11932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1194cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com 11952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com double nextT() const { 1196cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(fTIndex <= fTs->count()); 1197cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return t(fTIndex + 1); 1198cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1199c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 1200cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com double t() const { 12016680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com if (fTIndex == 0) { 12026680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return 0; 12036680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 12046680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com if (fTIndex > fTs->count()) { 12056680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return 1; 1206c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 12076680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return (*fTs)[fTIndex - 1]; 1208c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 1209c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 1210cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com double t(int tIndex) const { 1211cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (tIndex == 0) { 1212cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return 0; 1213cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1214cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (tIndex > fTs->count()) { 1215cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return 1; 1216cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1217cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return (*fTs)[tIndex - 1]; 1218cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1219cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com 12202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: debugging only 1221752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com int ID() const { 12222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return fWorkEdge.fEdge->fID; 12232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 12242e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 12252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.compublic: 12266680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com WorkEdge fWorkEdge; 12276680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com const SkTDArray<double>* fTs; 1228cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkPoint fAbove; 1229cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkPoint fBelow; 12302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if COMPARE_DOUBLE 12312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Point fDAbove; 12322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Point fDBelow; 12332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 12342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ABOVE_BELOW 12352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com double fTAbove; 12362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com double fTBelow; 12372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 1238cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkScalar fYBottom; 12392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int fCoincident; 12406680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com int fTIndex; 12412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool fSkip; // OPTIMIZATION: use bitfields? 12422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool fCloseCall; 1243cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com bool fDone; 12442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool fFixBelow; 1245c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 1246c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 12476680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) { 12486680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com size_t count = activeEdges.count(); 12496680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com for (size_t index = 0; index < count; ++index) { 12506680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com if (edge == activeEdges[index].fWorkEdge.fEdge) { 12516680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return; 12526680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 12536680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 12546680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com ActiveEdge* active = activeEdges.append(); 12556680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com active->init(edge); 12566680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com} 12576680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 12584917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// Find any intersections in the range of active edges. A pair of edges, on 12594917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// either side of another edge, may change the winding contribution for part of 12604917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// the edge. 12612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// Keep horizontal edges just for 12624917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// the purpose of computing when edges change their winding contribution, since 12634917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com// this is essentially computing the horizontal intersection. 12642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic void addBottomT(InEdge** currentPtr, InEdge** lastPtr, 12652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge** horizontal) { 12662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge** testPtr = currentPtr - 1; 12672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge* horzEdge = *horizontal; 12682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar left = horzEdge->fLeft; 12692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar bottom = horzEdge->fY; 12702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com while (++testPtr != lastPtr) { 12712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge* test = *testPtr; 12722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (test->fBounds.fBottom <= bottom || test->fBounds.fRight <= left) { 12732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com continue; 12742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 12752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com WorkEdge wt; 12762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com wt.init(test); 12772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com do { 12782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge** sorted = horizontal; 12792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horzEdge = *sorted; 1280f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 1281f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (wt.verb() == SkPath::kLine_Verb) { 1282f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com double wtTs[2]; 12832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int pts = LineIntersect(wt.fPts, horzEdge->fLeft, 12842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horzEdge->fRight, horzEdge->fY, wtTs); 1285f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (pts) { 12862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ADD_BOTTOM_TS 12872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s y=%g wtTs[0]=%g (%g,%g, %g,%g)\n", __FUNCTION__, 12882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horzEdge->fY, wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY, 12892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com wt.fPts[1].fX, wt.fPts[1].fY); 12902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (pts == 2) { 12912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]); 12922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 12932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 12944917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com test->add(wtTs, pts, wt.verbIndex()); 1295f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1296cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } else { 1297cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add all curve types 1298cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(0); 1299f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 13002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com horzEdge = *++sorted; 13012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } while (horzEdge->fY == bottom 13022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && horzEdge->fLeft <= test->fBounds.fRight); 13032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } while (wt.advance()); 1304f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1305f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1306f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 1307f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) { 1308cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com InEdge** testPtr = currentPtr - 1; 1309752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com // FIXME: lastPtr should be past the point of interest, so 1310752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com // test below should be lastPtr - 2 1311752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com // that breaks testSimplifyTriangle22, so further investigation is needed 1312cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com while (++testPtr != lastPtr - 1) { 1313cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com InEdge* test = *testPtr; 1314cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com InEdge** nextPtr = testPtr; 1315cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com do { 1316cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com InEdge* next = *++nextPtr; 1317cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (test->cached(next)) { 1318cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com continue; 1319cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1320cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (!Bounds::Intersects(test->fBounds, next->fBounds)) { 1321cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com continue; 1322cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1323f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com WorkEdge wt, wn; 1324f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com wt.init(test); 1325f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com wn.init(next); 1326f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 1327f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (wt.verb() == SkPath::kLine_Verb 1328f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com && wn.verb() == SkPath::kLine_Verb) { 1329f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com double wtTs[2], wnTs[2]; 1330f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int pts = LineIntersect(wt.fPts, wn.fPts, wtTs, wnTs); 1331f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (pts) { 13322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ADD_INTERSECTING_TS 13332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkPoint wtOutPt, wnOutPt; 13342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineXYAtT(wt.fPts, wtTs[0], &wtOutPt); 13352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineXYAtT(wn.fPts, wnTs[0], &wnOutPt); 13362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s wtTs[0]=%g (%g,%g, %g,%g) (%g,%g) (%d,%d)\n", 13372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com __FUNCTION__, 13382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com wtTs[0], wt.fPts[0].fX, wt.fPts[0].fY, 13392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com wt.fPts[1].fX, wt.fPts[1].fY, wtOutPt.fX, wtOutPt.fY, 13402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com test->fID, next->fID); 13412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (pts == 2) { 13422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s wtTs[1]=%g\n", __FUNCTION__, wtTs[1]); 13432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 13442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s wnTs[0]=%g (%g,%g, %g,%g) (%g,%g) (%d,%d)\n", 13452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com __FUNCTION__, 13462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com wnTs[0], wn.fPts[0].fX, wn.fPts[0].fY, 13472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com wn.fPts[1].fX, wn.fPts[1].fY, wnOutPt.fX, wnOutPt.fY, 13482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com test->fID, next->fID); 13492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (pts == 2) { 13502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s wnTs[1]=%g\n", __FUNCTION__, wnTs[1]); 13512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 13522e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 13534917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com test->add(wtTs, pts, wt.verbIndex()); 13544917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com next->add(wnTs, pts, wn.verbIndex()); 1355f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1356cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } else { 1357cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add all combinations of curve types 1358cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(0); 1359f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1360cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } while (wt.bottom() <= wn.bottom() ? wt.advance() : wn.advance()); 1361cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } while (nextPtr != lastPtr); 1362f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1363f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1364f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 13652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic InEdge** advanceEdges(SkTDArray<ActiveEdge>* activeEdges, 13666008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com InEdge** currentPtr, InEdge** lastPtr, SkScalar y) { 13676008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com InEdge** testPtr = currentPtr - 1; 13686008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (++testPtr != lastPtr) { 13696008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if ((*testPtr)->fBounds.fBottom > y) { 13706008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com continue; 13716008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 13722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activeEdges) { 13732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge* test = *testPtr; 13742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ActiveEdge* activePtr = activeEdges->begin() - 1; 13752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ActiveEdge* lastActive = activeEdges->end(); 13762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com while (++activePtr != lastActive) { 13772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activePtr->fWorkEdge.fEdge == test) { 13782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activeEdges->remove(activePtr - activeEdges->begin()); 13792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com break; 13802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 13816008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 13826008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 13836008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (testPtr == currentPtr) { 13846008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ++currentPtr; 13856008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 13866008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 13876008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return currentPtr; 13886008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com} 13896008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 13902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// OPTIMIZE: inline? 13912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic HorizontalEdge** advanceHorizontal(HorizontalEdge** edge, SkScalar y) { 13922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com while ((*edge)->fY < y) { 13932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ++edge; 13942e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 13952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return edge; 13962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 13972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 1398f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com// compute bottom taking into account any intersected edges 13992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic SkScalar computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges, 14002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar y, SkScalar bottom) { 1401f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com ActiveEdge* activePtr = activeEdges.begin() - 1; 1402f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com ActiveEdge* lastActive = activeEdges.end(); 1403f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com while (++activePtr != lastActive) { 1404f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const InEdge* test = activePtr->fWorkEdge.fEdge; 1405f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (!test->fContainsIntercepts) { 1406f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com continue; 1407f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1408f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com WorkEdge wt; 1409f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com wt.init(test); 1410f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 1411f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const Intercepts& intercepts = test->fIntercepts[wt.verbIndex()]; 14124917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (intercepts.fTopIntercepts > 1) { 14134917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com SkScalar yTop = wt.fPts[0].fY; 14144917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (yTop > y && bottom > yTop) { 14154917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com bottom = yTop; 14164917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 14174917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 14184917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (intercepts.fBottomIntercepts > 1) { 14194917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com SkScalar yBottom = wt.fPts[wt.verb()].fY; 14204917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (yBottom > y && bottom > yBottom) { 14214917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com bottom = yBottom; 14224917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 14234917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 1424f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const SkTDArray<double>& fTs = intercepts.fTs; 1425f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com size_t count = fTs.count(); 1426f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com for (size_t index = 0; index < count; ++index) { 1427f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (wt.verb() == SkPath::kLine_Verb) { 1428f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar yIntercept = LineYAtT(wt.fPts, fTs[index]); 14296008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (yIntercept > y && bottom > yIntercept) { 1430f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com bottom = yIntercept; 1431f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1432cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } else { 1433cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add all curve types 1434cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(0); 1435f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1436f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1437cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } while (wt.advance()); 1438f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 14392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return bottom; 1440f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1441f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 1442f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic SkScalar findBottom(InEdge** currentPtr, 14432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge** edgeListEnd, SkTDArray<ActiveEdge>* activeEdges, SkScalar y, 14446008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool asFill, InEdge**& testPtr) { 1445f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge* current = *currentPtr; 1446f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar bottom = current->fBounds.fBottom; 1447752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1448f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // find the list of edges that cross y 14496008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com InEdge* test = *testPtr; 14506008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (testPtr != edgeListEnd) { 14516008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkScalar testTop = test->fBounds.fTop; 14526008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (bottom <= testTop) { 1453f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com break; 1454f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 14556008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkScalar testBottom = test->fBounds.fBottom; 1456f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // OPTIMIZATION: Shortening the bottom is only interesting when filling 1457f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // and when the edge is to the left of a longer edge. If it's a framing 1458f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // edge, or part of the right, it won't effect the longer edges. 14596008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (testTop > y) { 14606008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bottom = testTop; 14616008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com break; 14626008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 14636008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (y < testBottom) { 14646008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (bottom > testBottom) { 14656008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bottom = testBottom; 1466f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 14672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activeEdges) { 14682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com addToActive(*activeEdges, test); 14692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1470f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 14716008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com test = *++testPtr; 1472f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1473f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com return bottom; 1474f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1475f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 1476f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic void makeEdgeList(SkTArray<InEdge>& edges, InEdge& edgeSentinel, 1477f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkTDArray<InEdge*>& edgeList) { 1478c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com size_t edgeCount = edges.count(); 1479c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (edgeCount == 0) { 1480c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 1481c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 1482c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (size_t index = 0; index < edgeCount; ++index) { 1483c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *edgeList.append() = &edges[index]; 1484c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 1485c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com edgeSentinel.fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 1486c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *edgeList.append() = &edgeSentinel; 1487cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com QSort<InEdge>(edgeList.begin(), edgeList.end() - 1); 1488f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1489f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 14902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic void makeHorizontalList(SkTDArray<HorizontalEdge>& edges, 14912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge& edgeSentinel, SkTDArray<HorizontalEdge*>& edgeList) { 14922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com size_t edgeCount = edges.count(); 14932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (edgeCount == 0) { 14942e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return; 14952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 14962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (size_t index = 0; index < edgeCount; ++index) { 14972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com *edgeList.append() = &edges[index]; 14982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 14992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com edgeSentinel.fLeft = edgeSentinel.fRight = edgeSentinel.fY = SK_ScalarMax; 15002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com *edgeList.append() = &edgeSentinel; 15012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com QSort<HorizontalEdge>(edgeList.begin(), edgeList.end() - 1); 15022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 15036b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com 15046b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.comstatic void skipCoincidence(int lastWinding, int winding, int windingMask, 15056b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com ActiveEdge* activePtr, ActiveEdge* firstCoincident) { 15066b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (((lastWinding & windingMask) == 0) ^ (winding & windingMask) != 0) { 15076b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com return; 15086b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 15092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: ? shouldn't this be if (lastWinding & windingMask) ? 15106b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (lastWinding) { 1511752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#if DEBUG_ADJUST_COINCIDENT 1512752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s edge=%d 1 set skip=false\n", __FUNCTION__, activePtr->ID()); 1513752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#endif 15146b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com activePtr->fSkip = false; 15156b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } else { 1516752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#if DEBUG_ADJUST_COINCIDENT 1517752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s edge=%d 2 set skip=false\n", __FUNCTION__, firstCoincident->ID()); 1518752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#endif 15196b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident->fSkip = false; 15206b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 15216b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com} 15226b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com 15236008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comstatic void sortHorizontal(SkTDArray<ActiveEdge>& activeEdges, 15242e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTDArray<ActiveEdge*>& edgeList, SkScalar y) { 15252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const int tab = 3; // FIXME: debugging only 15266008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com size_t edgeCount = activeEdges.count(); 15276008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (edgeCount == 0) { 15286008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return; 15296008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 15302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_SORT_HORIZONTAL 15312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s y=%1.9g\n", __FUNCTION__, y); 15322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 15336008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com size_t index; 15346008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com for (index = 0; index < edgeCount; ++index) { 15356008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge& activeEdge = activeEdges[index]; 15362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com do { 15372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activeEdge.calcLeft(y); 15382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // skip segments that don't span y 15392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activeEdge.fAbove != activeEdge.fBelow) { 15402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com break; 15412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 15422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activeEdge.fDone) { 15432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_SORT_HORIZONTAL 15442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s edge=%d done\n", tab, "", activeEdge.ID()); 15452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 15462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com goto nextEdge; 15472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 15482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_SORT_HORIZONTAL 15492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s edge=%d above==below\n", tab, "", activeEdge.ID()); 15502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 15512e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } while (activeEdge.advanceT() || activeEdge.advance()); 15522e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_SORT_HORIZONTAL 15532e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s edge=%d above=(%1.9g,%1.9g) (%1.9g) below=(%1.9g,%1.9g)" 15542e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com " (%1.9g)\n", tab, "", activeEdge.ID(), 15552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activeEdge.fAbove.fX, activeEdge.fAbove.fY, activeEdge.fTAbove, 15562e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activeEdge.fBelow.fX, activeEdge.fBelow.fY, activeEdge.fTBelow); 15572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 15582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activeEdge.fSkip = activeEdge.fCloseCall = activeEdge.fFixBelow = false; 15596008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com *edgeList.append() = &activeEdge; 15602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comnextEdge: 15612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ; 15626008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 1563cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com QSort<ActiveEdge>(edgeList.begin(), edgeList.end() - 1); 15642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com} 15652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 15662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// remove coincident edges 15672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// OPTIMIZE: remove edges? This is tricky because the current logic expects 15682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// the winding count to be maintained while skipping coincident edges. In 15692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// addition to removing the coincident edges, the remaining edges would need 15702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// to have a different winding value, possibly different per intercept span. 15712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.comstatic SkScalar adjustCoincident(SkTDArray<ActiveEdge*>& edgeList, 15722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int windingMask, SkScalar y, SkScalar bottom, OutEdgeBuilder& outBuilder) 15732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com{ 15742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ADJUST_COINCIDENT 15752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom); 15762e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 15772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com size_t edgeCount = edgeList.count(); 15782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (edgeCount == 0) { 15792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return bottom; 15802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 15816008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge* activePtr = edgeList[0]; 15822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com size_t index; 15832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool foundCoincident = false; 15842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int firstIndex = 0; 15852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (index = 1; index < edgeCount; ++index) { 15862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ActiveEdge* nextPtr = edgeList[index]; 15872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bool closeCall = false; 15882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fCoincident = firstIndex; 15892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activePtr->isCoincidentWith(nextPtr, y) 15902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com || (closeCall = activePtr->tooCloseToCall(nextPtr))) { 15912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fSkip = nextPtr->fSkip = foundCoincident = true; 15922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fCloseCall = nextPtr->fCloseCall = closeCall; 15932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } else { 15942e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com firstIndex = index; 15952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 15962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr = nextPtr; 15972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 15982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fCoincident = firstIndex; 15992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (!foundCoincident) { 16002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return bottom; 16012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16026b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com int winding = 0; 16032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr = edgeList[0]; 16046008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com for (index = 1; index < edgeCount; ++index) { 16052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int priorWinding = winding; 16066b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com winding += activePtr->fWorkEdge.winding(); 16076008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge* nextPtr = edgeList[index]; 16082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activePtr->fCoincident == nextPtr->fCoincident) { 1609cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // the coincident edges may not have been sorted above -- advance 1610cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // the edges and resort if needed 1611cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // OPTIMIZE: if sorting is done incrementally as new edges are added 1612cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // and not all at once as is done here, fold this test into the 1613cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com // current less than test. 16142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activePtr->fCloseCall ? activePtr->swapClose(nextPtr, 16152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com priorWinding, winding, windingMask) 16162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com : activePtr->swapCoincident(nextPtr, bottom)) { 16174917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com winding -= activePtr->fWorkEdge.winding(); 1618cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkTSwap<ActiveEdge*>(edgeList[index - 1], edgeList[index]); 1619cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkTSwap<ActiveEdge*>(activePtr, nextPtr); 16204917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com winding += activePtr->fWorkEdge.winding(); 1621cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 16222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr = nextPtr; 16242e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int firstCoincidentWinding = 0; 16262e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ActiveEdge* firstCoincident = NULL; 16272e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com winding = 0; 16282e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr = edgeList[0]; 16292e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (index = 1; index < edgeCount; ++index) { 16302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com int priorWinding = winding; 16312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com winding += activePtr->fWorkEdge.winding(); 16322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ActiveEdge* nextPtr = edgeList[index]; 16332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activePtr->fCoincident == nextPtr->fCoincident) { 16346b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (!firstCoincident) { 16356b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident = activePtr; 16362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com firstCoincidentWinding = priorWinding; 16372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (activePtr->fCloseCall) { 16392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // If one of the edges has already been added to out as a non 16402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // coincident edge, trim it back to the top of this span 16412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (outBuilder.trimLine(y, activePtr->ID())) { 16422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->addTatYAbove(y); 1643752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if DEBUG_ADJUST_COINCIDENT 1644752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s 1 edge=%d y=%1.9g (was fYBottom=%1.9g)\n", 1645752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com __FUNCTION__, activePtr->ID(), y, activePtr->fYBottom); 1646752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #endif 16472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fYBottom = y; 16482e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16492e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (outBuilder.trimLine(y, nextPtr->ID())) { 16502e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com nextPtr->addTatYAbove(y); 1651752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if DEBUG_ADJUST_COINCIDENT 1652752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s 2 edge=%d y=%1.9g (was fYBottom=%1.9g)\n", 1653752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com __FUNCTION__, nextPtr->ID(), y, nextPtr->fYBottom); 1654752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #endif 16552e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com nextPtr->fYBottom = y; 16562e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16572e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // add missing t values so edges can be the same length 16582e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar testY = activePtr->fBelow.fY; 16592e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com nextPtr->addTatYBelow(testY); 16602e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (bottom > testY && testY > y) { 1661752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if DEBUG_ADJUST_COINCIDENT 1662752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s 3 edge=%d bottom=%1.9g (was bottom=%1.9g)\n", 1663752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com __FUNCTION__, activePtr->ID(), testY, bottom); 1664752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #endif 16652e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bottom = testY; 16662e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com testY = nextPtr->fBelow.fY; 16682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->addTatYBelow(testY); 16692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (bottom > testY && testY > y) { 1670752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #if DEBUG_ADJUST_COINCIDENT 1671752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s 4 edge=%d bottom=%1.9g (was bottom=%1.9g)\n", 1672752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com __FUNCTION__, nextPtr->ID(), testY, bottom); 1673752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com #endif 16742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bottom = testY; 16752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16766b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 16772e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } else if (firstCoincident) { 16782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com skipCoincidence(firstCoincidentWinding, winding, windingMask, 16792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr, firstCoincident); 16806b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident = NULL; 16816b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 16826008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com activePtr = nextPtr; 1683f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 16842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (firstCoincident) { 16856b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com winding += activePtr->fWorkEdge.winding(); 16862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com skipCoincidence(firstCoincidentWinding, winding, windingMask, activePtr, 16876b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident); 16886b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 16892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // fix up the bottom for close call edges. OPTIMIZATION: maybe this could 16902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // be in the loop above, but moved here since loop above reads fBelow and 16912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // it felt unsafe to write it in that loop 16922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com for (index = 0; index < edgeCount; ++index) { 16932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (edgeList[index])->fixBelow(); 16942e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 16952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com return bottom; 1696f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 16976680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 1698f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com// stitch edge and t range that satisfies operation 16996008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comstatic void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar y, 1700752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkScalar bottom, int windingMask, bool fill, OutEdgeBuilder& outBuilder) { 1701f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int winding = 0; 17026008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge** activeHandle = edgeList.begin() - 1; 17036008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge** lastActive = edgeList.end(); 17042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const int tab = 7; // FIXME: debugging only 1705cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gShowDebugf) { 17062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%s y=%1.9g bottom=%1.9g\n", __FUNCTION__, y, bottom); 1707c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 17086008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (++activeHandle != lastActive) { 17096008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge* activePtr = *activeHandle; 1710f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const WorkEdge& wt = activePtr->fWorkEdge; 1711f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int lastWinding = winding; 1712f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com winding += wt.winding(); 17132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (gShowDebugf) { 17142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s edge=%d lastWinding=%d winding=%d skip=%d close=%d" 17152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ABOVE_BELOW 17162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com " above=%1.9g below=%1.9g" 17172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 17182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com "\n", 17192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com tab-4, "", activePtr->ID(), lastWinding, 17202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com winding, activePtr->fSkip, activePtr->fCloseCall 17212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_ABOVE_BELOW 17222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com , activePtr->fTAbove, activePtr->fTBelow 17232e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 17242e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com ); 17252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1726752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (activePtr->done(bottom)) { 1727752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (gShowDebugf) { 1728752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%*s fDone=%d || fYBottom=%1.9g >= bottom\n", tab, "", 1729752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com activePtr->fDone, activePtr->fYBottom); 1730cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com } 1731752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com continue; 1732cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } 1733c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com int opener = (lastWinding & windingMask) == 0; 1734c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com bool closer = (winding & windingMask) == 0; 1735c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkASSERT(!opener | !closer); 1736c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com bool inWinding = opener | closer; 17374917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com SkPoint clippedPts[2]; 17384917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com const SkPoint* clipped = NULL; 17392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if COMPARE_DOUBLE 17402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Line dPoints; 17412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com _Line clippedDPts; 17422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com const _Point* dClipped = NULL; 17432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 1744cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com uint8_t verb = wt.verb(); 1745cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com bool moreToDo, aboveBottom; 1746f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 1747f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com double currentT = activePtr->t(); 17486008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkASSERT(currentT < 1); 1749f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const SkPoint* points = wt.fPts; 1750cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com double nextT; 17516680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com do { 1752cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com nextT = activePtr->nextT(); 1753cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (verb == SkPath::kLine_Verb) { 1754cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: obtuse: want efficient way to say 1755cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // !currentT && currentT != 1 || !nextT && nextT != 1 1756f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (currentT * nextT != 0 || currentT + nextT != 1) { 17576008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // OPTIMIZATION: if !inWinding, we only need 17586008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // clipped[1].fY 1759f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com LineSubDivide(points, currentT, nextT, clippedPts); 1760f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com clipped = clippedPts; 17612e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if COMPARE_DOUBLE 17622e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com LineSubDivide(points, currentT, nextT, clippedDPts); 17632e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com dClipped = clippedDPts; 17642e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 1765f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } else { 1766f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com clipped = points; 17672e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if COMPARE_DOUBLE 17682e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com dPoints[0].x = SkScalarToDouble(points[0].fX); 17692e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com dPoints[0].y = SkScalarToDouble(points[1].fY); 17702e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com dPoints[1].x = SkScalarToDouble(points[0].fX); 17712e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com dPoints[1].y = SkScalarToDouble(points[1].fY); 17722e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com dClipped = dPoints; 17732e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 17746680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 1775752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (inWinding && !activePtr->fSkip && (fill ? clipped[0].fY 1776752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com != clipped[1].fY : clipped[0] != clipped[1])) { 1777cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (gShowDebugf) { 17782e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s line %1.9g,%1.9g %1.9g,%1.9g edge=%d" 17792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com " v=%d t=(%1.9g,%1.9g)\n", tab, "", 17802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com clipped[0].fX, clipped[0].fY, 17812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com clipped[1].fX, clipped[1].fY, 17822e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->ID(), 17832e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fWorkEdge.fVerb 17842e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com - activePtr->fWorkEdge.fEdge->fVerbs.begin(), 17852e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com currentT, nextT); 17862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 1787752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com outBuilder.addLine(clipped, 1788752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com activePtr->fWorkEdge.fEdge->fID, 1789752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com activePtr->fCloseCall); 17902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } else { 17912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (gShowDebugf) { 17922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkDebugf("%*s skip %1.9g,%1.9g %1.9g,%1.9g" 17932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com " edge=%d v=%d t=(%1.9g,%1.9g)\n", tab, "", 1794c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com clipped[0].fX, clipped[0].fY, 17952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com clipped[1].fX, clipped[1].fY, 17962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->ID(), 17972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fWorkEdge.fVerb 17982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com - activePtr->fWorkEdge.fEdge->fVerbs.begin(), 17992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com currentT, nextT); 1800c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 18016680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 18022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // by advancing fAbove/fBelow, the next call to sortHorizontal 18032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // will use these values if they're still valid instead of 18042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // recomputing 18052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if COMPARE_DOUBLE 18062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkASSERT((clipped[1].fY > activePtr->fBelow.fY 18072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && bottom >= activePtr->fBelow.fY) 18082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com == (dClipped[1].y > activePtr->fDBelow.y 18092e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com && bottom >= activePtr->fDBelow.y)); 18102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 18114917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (clipped[1].fY > activePtr->fBelow.fY 18124917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com && bottom >= activePtr->fBelow.fY ) { 18134917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com activePtr->fAbove = activePtr->fBelow; 18144917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com activePtr->fBelow = clipped[1]; 18152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if COMPARE_DOUBLE 18162e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fDAbove = activePtr->fDBelow; 18172e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fDBelow = dClipped[1]; 18182e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 18192e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #if DEBUG_ABOVE_BELOW 18202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fTAbove = activePtr->fTBelow; 18212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fTBelow = nextT; 18222e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com #endif 18234917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 1824cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } else { 1825cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // FIXME: add all curve types 1826cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkASSERT(0); 1827f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1828f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com currentT = nextT; 1829cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com moreToDo = activePtr->advanceT(); 18302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com activePtr->fYBottom = clipped[verb].fY; // was activePtr->fCloseCall ? bottom : 18312e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 18322e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // clearing the fSkip/fCloseCall bit here means that trailing edges 18332e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // fall out of sync, if one edge is long and another is a series of short pieces 18342e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // if fSkip/fCloseCall is set, need to recompute coincidence/too-close-to-call 18352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // after advancing 18362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // another approach would be to restrict bottom to smaller part of close call 18372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // maybe this is already happening with coincidence when intersection is computed, 18382e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // and needs to be added to the close call computation as well 18392e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // this is hard to do because that the bottom is important is not known when 18402e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // the lines are intersected; only when the computation for edge sorting is done 18412e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // does the need for new bottoms become apparent. 18422e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // maybe this is good incentive to scrap the current sort and do an insertion 18432e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // sort that can take this into consideration when the x value is computed 18442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com 18452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // FIXME: initialized in sortHorizontal, cleared here as well so 18462e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // that next edge is not skipped -- but should skipped edges ever 18472e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // continue? (probably not) 1848752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com aboveBottom = clipped[verb].fY < bottom; 1849752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (clipped[0].fY != clipped[verb].fY) { 1850752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com activePtr->fSkip = false; 1851752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com activePtr->fCloseCall = false; 1852752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com aboveBottom &= !activePtr->fCloseCall; 1853752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } else { 1854752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com if (activePtr->fSkip || activePtr->fCloseCall) { 1855752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("== %1.9g\n", clippedPts[0].fY); 1856752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } 1857752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com } 1858cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } while (moreToDo & aboveBottom); 1859cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com } while ((moreToDo || activePtr->advance()) & aboveBottom); 1860f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1861f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 18626680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 1863f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comvoid simplify(const SkPath& path, bool asFill, SkPath& simple) { 1864f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 1865f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int windingMask = (path.getFillType() & 1) ? 1 : -1; 1866f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com simple.reset(); 1867f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com simple.setFillType(SkPath::kEvenOdd_FillType); 1868f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // turn path into list of edges increasing in y 1869cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // if an edge is a quad or a cubic with a y extrema, note it, but leave it 1870cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // unbroken. Once we have a list, sort it, then walk the list (walk edges 1871cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // twice that have y extrema's on top) and detect crossings -- look for raw 1872cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com // bounds that cross over, then tight bounds that cross 1873f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkTArray<InEdge> edges; 18742e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTDArray<HorizontalEdge> horizontalEdges; 18752e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdgeBuilder builder(path, asFill, edges, horizontalEdges); 1876f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkTDArray<InEdge*> edgeList; 1877f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge edgeSentinel; 1878f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com makeEdgeList(edges, edgeSentinel, edgeList); 18792e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkTDArray<HorizontalEdge*> horizontalList; 18802e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge horizontalSentinel; 18812e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com makeHorizontalList(horizontalEdges, horizontalSentinel, horizontalList); 1882f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge** currentPtr = edgeList.begin(); 18834917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com if (!currentPtr) { 18844917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com return; 18854917f17bf6bd8bff7f4b03717dcb02561cf227c9caryclark@google.com } 18862e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // find all intersections between edges 18872e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// beyond looking for horizontal intercepts, we need to know if any active edges 18882e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// intersect edges below 'bottom', but above the active edge segment. 18892e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// maybe it makes more sense to compute all intercepts before doing anything 18902e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com// else, since the intercept list is long-lived, at least in the current design. 18912e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar y = (*currentPtr)->fBounds.fTop; 18922e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com HorizontalEdge** currentHorizontal = horizontalList.begin(); 18932e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com do { 18942e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set 18952e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com SkScalar bottom = findBottom(currentPtr, edgeList.end(), 18962e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com NULL, y, asFill, lastPtr); 18972e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (lastPtr > currentPtr) { 18982e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if (currentHorizontal) { 18992e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com if ((*currentHorizontal)->fY < SK_ScalarMax) { 19002e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com addBottomT(currentPtr, lastPtr, currentHorizontal); 19012e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 19022e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com currentHorizontal = advanceHorizontal(currentHorizontal, bottom); 19032e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 19042e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com addIntersectingTs(currentPtr, lastPtr); 19052e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } 19062e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com y = bottom; 19072e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com currentPtr = advanceEdges(NULL, currentPtr, lastPtr, y); 19082e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } while (*currentPtr != &edgeSentinel); 1909752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 19102e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#if DEBUG_DUMP 19112e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com InEdge** debugPtr = edgeList.begin(); 19122e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com do { 19132e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com (*debugPtr++)->dump(); 19142e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com } while (*debugPtr != &edgeSentinel); 19152e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com#endif 1916752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com 1917f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // walk the sorted edges from top to bottom, computing accumulated winding 1918f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkTDArray<ActiveEdge> activeEdges; 1919f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com OutEdgeBuilder outBuilder(asFill); 19202e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com currentPtr = edgeList.begin(); 19212e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com y = (*currentPtr)->fBounds.fTop; 1922f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 1923f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set 1924f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar bottom = findBottom(currentPtr, edgeList.end(), 19252e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com &activeEdges, y, asFill, lastPtr); 1926752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#if DEBUG_BOTTOM 1927752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s findBottom bottom=%1.9g\n", __FUNCTION__, bottom); 1928752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#endif 1929c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (lastPtr > currentPtr) { 19302e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bottom = computeInterceptBottom(activeEdges, y, bottom); 1931752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#if DEBUG_BOTTOM 1932752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s computeInterceptBottom bottom=%1.9g\n", __FUNCTION__, bottom); 1933752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#endif 1934c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkTDArray<ActiveEdge*> activeEdgeList; 19352e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com sortHorizontal(activeEdges, activeEdgeList, y); 19362e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com bottom = adjustCoincident(activeEdgeList, windingMask, y, bottom, 19372e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com outBuilder); 1938752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#if DEBUG_BOTTOM 1939752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com SkDebugf("%s adjustCoincident bottom=%1.9g\n", __FUNCTION__, bottom); 1940752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com#endif 1941752b60e633a349c5b9f7bcc6a28b8064fc77bb41caryclark@google.com stitchEdge(activeEdgeList, y, bottom, windingMask, asFill, outBuilder); 1942c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 1943c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com y = bottom; 19442e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com // OPTIMIZATION: as edges expire, InEdge allocations could be released 19452e7f4c810dc717383df42d27bdba862514ab6d51caryclark@google.com currentPtr = advanceEdges(&activeEdges, currentPtr, lastPtr, y); 1946c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } while (*currentPtr != &edgeSentinel); 1947c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // assemble output path from string of pts, verbs 1948f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com outBuilder.bridge(); 1949f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com outBuilder.assemble(simple); 1950c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 1951