EdgeWalker.cpp revision c17972e7acc784553445adc18f608a8c4b1beac8
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 17c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.comstatic bool fShowDebugf = true; // FIXME: remove once debugging is complete 18c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com 19c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.comconst int kOpenerVerbBitShift = 3; // leaves 3 bits for SkPath::Verb 20c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com 216680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic int LineIntersect(const SkPoint a[2], const SkPoint b[2], 22c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com double aRange[2], double bRange[2]) { 23c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 24c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com _Line bLine = {{b[0].fX, b[0].fY}, {b[1].fX, b[1].fY}}; 25c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return intersect(aLine, bLine, aRange, bRange); 26c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 27c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 286680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic int LineIntersect(const SkPoint a[2], SkScalar y, double aRange[2]) { 29c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 30c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return horizontalIntersect(aLine, y, aRange); 31c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 32c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 336680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic SkScalar LineYAtT(const SkPoint a[2], double t) { 346680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 356680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com double y; 366680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com xy_at_t(aLine, t, *(double*) 0, y); 376680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return SkDoubleToScalar(y); 386680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com} 396680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 406680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic void LineSubDivide(const SkPoint a[2], double startT, double endT, 416680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkPoint sub[2]) { 426680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com _Line aLine = {{a[0].fX, a[0].fY}, {a[1].fX, a[1].fY}}; 436680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com _Line dst; 446680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub_divide(aLine, startT, endT, dst); 456680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub[0].fX = SkDoubleToScalar(dst[0].x); 466680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub[0].fY = SkDoubleToScalar(dst[0].y); 476680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub[1].fX = SkDoubleToScalar(dst[1].x); 486680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com sub[1].fY = SkDoubleToScalar(dst[1].y); 496680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com} 506680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 516680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 52c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com// functions 53c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray); 54c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid simplify(const SkPath& path, bool asFill, SkPath& simple); 55c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com/* 56c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comlist of edges 57c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combounds for edge 58c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comsort 59c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comactive T 60c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 61c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comif a contour's bounds is outside of the active area, no need to create edges 62c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com*/ 63c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 64c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com/* given one or more paths, 65c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com find the bounds of each contour, select the active contours 66c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for each active contour, compute a set of edges 67c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com each edge corresponds to one or more lines and curves 68c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com leave edges unbroken as long as possible 69c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com when breaking edges, compute the t at the break but leave the control points alone 70c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 71c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com */ 72c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 73c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid contourBounds(const SkPath& path, SkTDArray<SkRect>& boundsArray) { 74c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Iter iter(path, false); 75c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPoint pts[4]; 76c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Verb verb; 77c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkRect bounds; 78c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bounds.setEmpty(); 79c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int count = 0; 80c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 81c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com switch (verb) { 82c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kMove_Verb: 83c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (!bounds.isEmpty()) { 84c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *boundsArray.append() = bounds; 85c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 86c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bounds.set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY); 87c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 0; 88c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 89c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kLine_Verb: 90c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 1; 91c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 92c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kQuad_Verb: 93c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 2; 94c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 95c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kCubic_Verb: 96c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 3; 97c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 98c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kClose_Verb: 99c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com count = 0; 100c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 101c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com default: 102c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkDEBUGFAIL("bad verb"); 103c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 104c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 105c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (int i = 1; i <= count; ++i) { 106c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bounds.growToInclude(pts[i].fX, pts[i].fY); 107c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 108c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 109c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 110c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 111f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic bool extendLine(const SkPoint line[2], const SkPoint& add) { 112f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // FIXME: allow this to extend lines that have slopes that are nearly equal 113f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar dx1 = line[1].fX - line[0].fX; 114f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar dy1 = line[1].fY - line[0].fY; 115f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar dx2 = add.fX - line[0].fX; 116f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar dy2 = add.fY - line[0].fY; 117f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com return dx1 * dy2 == dx2 * dy1; 118f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 1196680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 120f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstruct OutEdge { 121f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com bool operator<(const OutEdge& rh) const { 122f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const SkPoint& first = fPts.begin()[0]; 123f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const SkPoint& rhFirst = rh.fPts.begin()[0]; 124f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com return first.fY == rhFirst.fY 125f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com ? first.fX < rhFirst.fX 126f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com : first.fY < rhFirst.fY; 127f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 128f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 1296680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTDArray<SkPoint> fPts; 130c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com // contains the SkPath verb, plus 1<<kOpenerVerbBitShift if edge opens span 131c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkTDArray<uint8_t> fVerbs; // FIXME: not read from everywhere 132c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com bool fOpener; 133f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com}; 134f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 1356680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comclass OutEdgeBuilder { 1366680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.compublic: 137f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com OutEdgeBuilder(bool fill) 138f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com : fFill(fill) { 139f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 140f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 141c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com void addLine(const SkPoint line[2], bool opener) { 142f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com size_t count = fEdges.count(); 143f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com for (size_t index = 0; index < count; ++index) { 144c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com OutEdge& edge = fEdges[index]; 145c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (opener != edge.fOpener) { 146c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com continue; 147c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 148c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkTDArray<SkPoint>& pts = edge.fPts; 149c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkPoint& last = pts.top(); 150c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (last == line[0]) { 151c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkTDArray<uint8_t>& verbs = edge.fVerbs; 152c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com uint8_t lastVerb = verbs.top(); 153c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (lastVerb == SkPath::kLine_Verb 154c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com && extendLine(&last - 1, line[1])) { 155c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com last = line[1]; 156f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } else { 157f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com *pts.append() = line[1]; 158c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com *verbs.append() = SkPath::kLine_Verb; 159f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 160f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com return; 161f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 162f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 163c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com OutEdge& newEdge = fEdges.push_back(); 164c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com *newEdge.fPts.append() = line[0]; 165c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com *newEdge.fVerbs.append() = SkPath::kMove_Verb; 166c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com *newEdge.fPts.append() = line[1]; 167c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com *newEdge.fVerbs.append() = SkPath::kLine_Verb; 168c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com newEdge.fOpener = opener; 169f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 170f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 171f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com void assemble(SkPath& simple) { 1726008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com size_t listCount = fEdges.count(); 1736008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (listCount == 0) { 1746008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return; 1756008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 176f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 1776008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com size_t listIndex = 0; 1786008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int advance = 1; 1796008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (listIndex < listCount && fTops[listIndex] == 0) { 1806008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ++listIndex; 181f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1826008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (listIndex >= listCount) { 1836008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com break; 184f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1856008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkPoint firstPt; 1866008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool doMove = true; 1876008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int edgeIndex; 1886008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com do { 1896008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkTDArray<SkPoint>& ptArray = fEdges[listIndex].fPts; 1906008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkASSERT(ptArray.count() > 0); 1916008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkPoint* pts, * end; 1926008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (advance < 0) { 1936008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com pts = ptArray.end() - 1; 1946008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com end = ptArray.begin(); 1956008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 1966008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com pts = ptArray.begin(); 1976008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com end = ptArray.end() - 1; 198f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 1996008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (doMove) { 2006008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com firstPt = pts[0]; 2016008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com simple.moveTo(pts[0].fX, pts[0].fY); 202c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (fShowDebugf) { 203c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkDebugf("%s moveTo (%g,%g)\n", __FUNCTION__, pts[0].fX, pts[0].fY); 204c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 2056008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com doMove = false; 2066008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 2076008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com simple.lineTo(pts[0].fX, pts[0].fY); 208c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (fShowDebugf) { 209c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkDebugf("%s 1 lineTo (%g,%g)\n", __FUNCTION__, pts[0].fX, pts[0].fY); 210c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 2116008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (firstPt == pts[0]) { 2126008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com simple.close(); 213c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (fShowDebugf) { 214c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkDebugf("%s close\n", __FUNCTION__); 215c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 2166008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com break; 2176008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 2186008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 2196008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (pts != end) { 2206008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com pts += advance; 2216008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com simple.lineTo(pts->fX, pts->fY); 222c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (fShowDebugf) { 223c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkDebugf("%s 2 lineTo (%g,%g)\n", __FUNCTION__, pts[0].fX, pts[0].fY); 224c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 2256008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 2266008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (advance < 0) { 2276008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com edgeIndex = fTops[listIndex]; 2286008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fTops[listIndex] = 0; 2296008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 2306008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com edgeIndex = fBottoms[listIndex]; 2316008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fBottoms[listIndex] = 0; 2326008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 2336008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com listIndex = abs(edgeIndex) - 1; 2346008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (edgeIndex < 0) { 2356008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fTops[listIndex] = 0; 2366008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 2376008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fBottoms[listIndex] = 0; 2386008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 2396008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // if this and next edge go different directions 2406008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (advance > 0 ^ edgeIndex < 0) { 2416008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com advance = -advance; 2426008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 2436008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } while (edgeIndex); 2446008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } while (true); 245f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 246f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 2476008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com static bool lessThan(SkTArray<OutEdge>& edges, const int* onePtr, 248f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const int* twoPtr) { 249f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int one = *onePtr; 250f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const OutEdge& oneEdge = edges[(one < 0 ? -one : one) - 1]; 251f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const SkPoint* onePt = one < 0 ? oneEdge.fPts.begin() 252f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com : oneEdge.fPts.end() - 1; 253f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int two = *twoPtr; 254f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const OutEdge& twoEdge = edges[(two < 0 ? -two : two) - 1]; 255f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const SkPoint* twoPt = two < 0 ? twoEdge.fPts.begin() 256f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com : twoEdge.fPts.end() - 1; 2576008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return onePt->fY == twoPt->fY ? onePt->fX < twoPt->fX : onePt->fY < twoPt->fY; 258f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 259f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 2606008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // Sort the indices of paired points and then create more indices so 2616008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // assemble() can find the next edge and connect the top or bottom 262f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com void bridge() { 263f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com size_t index; 264f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com size_t count = fEdges.count(); 265f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (!count) { 266f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com return; 267f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 268f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkASSERT(!fFill || (count & 1) == 0); 269f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com fTops.setCount(count); 270f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com sk_bzero(fTops.begin(), sizeof(fTops[0]) * count); 271f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com fBottoms.setCount(count); 272f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com sk_bzero(fBottoms.begin(), sizeof(fBottoms[0]) * count); 2736008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkTDArray<int> order; 2746008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com for (index = 1; index <= count; ++index) { 2756008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com *order.append() = index; 2766008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com *order.append() = -index; 277f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 2786008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com QSort<SkTArray<OutEdge>, int>(fEdges, order.begin(), count * 2, lessThan); 2796008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int* lastPtr = order.end() - 1; 2806008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int* leftPtr = order.begin(); 2816008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (leftPtr < lastPtr) { 2826008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int leftIndex = *leftPtr; 2836008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int leftOutIndex = abs(leftIndex) - 1; 2846008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com const OutEdge& left = fEdges[leftOutIndex]; 285f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int* rightPtr = leftPtr + 1; 2866008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int rightIndex = *rightPtr; 2876008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int rightOutIndex = abs(rightIndex) - 1; 2886008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com const OutEdge& right = fEdges[rightOutIndex]; 2896008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // OPTIMIZATION: if fFill is true, we don't need leftMatch, rightMatch 2906008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkPoint& leftMatch = left.fPts[leftIndex < 0 ? 0 2916008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com : left.fPts.count() - 1]; 2926008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkPoint& rightMatch = right.fPts[rightIndex < 0 ? 0 2936008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com : right.fPts.count() - 1]; 2946008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkASSERT(!fFill || leftMatch.fY == rightMatch.fY); 2956008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (fFill || leftMatch == rightMatch) { 2966008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (leftIndex < 0) { 2976008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fTops[leftOutIndex] = rightIndex; 2986008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 2996008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fBottoms[leftOutIndex] = rightIndex; 3006008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 3016008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (rightIndex < 0) { 3026008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fTops[rightOutIndex] = leftIndex; 3036008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } else { 3046008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fBottoms[rightOutIndex] = leftIndex; 305f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 3066008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ++rightPtr; 307f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 308f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com leftPtr = rightPtr; 3096680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 3106680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 3116680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 3126008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comprotected: 3136680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTArray<OutEdge> fEdges; 3146008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkTDArray<int> fTops; 3156008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkTDArray<int> fBottoms; 316f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com bool fFill; 3176680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com}; 3186680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 319c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com// Bounds, unlike Rect, does not consider a vertical line to be empty. 320c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comstruct Bounds : public SkRect { 321c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com static bool Intersects(const Bounds& a, const Bounds& b) { 322c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return a.fLeft <= b.fRight && b.fLeft <= a.fRight && 323c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com a.fTop <= b.fBottom && b.fTop <= a.fBottom; 324c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 3256008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 3266008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool isEmpty() { 3276008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return fLeft > fRight || fTop > fBottom 3286008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com || fLeft == fRight && fTop == fBottom 3296008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com || isnan(fLeft) || isnan(fRight) 3306008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com || isnan(fTop) || isnan(fBottom); 3316008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 332c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 333c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 334c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comstruct Intercepts { 335c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkTDArray<double> fTs; 336c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 337c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 3386680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstruct InEdge { 3396680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool operator<(const InEdge& rh) const { 340c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return fBounds.fTop == rh.fBounds.fTop 341c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com ? fBounds.fLeft < rh.fBounds.fLeft 342c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com : fBounds.fTop < rh.fBounds.fTop; 343c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 344c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 3456008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool add(double* ts, size_t count, ptrdiff_t verbIndex) { 346c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // FIXME: in the pathological case where there is a ton of intercepts, binary search? 3476008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool foundIntercept = false; 3486008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com Intercepts& intercepts = fIntercepts[verbIndex]; 349c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (size_t index = 0; index < count; ++index) { 350c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com double t = ts[index]; 3516008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (t <= 0 || t >= 1) { 3526008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com continue; 3536008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 3546008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com foundIntercept = true; 355c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com size_t tCount = intercepts.fTs.count(); 356c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (size_t idx2 = 0; idx2 < tCount; ++idx2) { 357c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (t <= intercepts.fTs[idx2]) { 358c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (t < intercepts.fTs[idx2]) { 359c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *intercepts.fTs.insert(idx2) = t; 360c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 361c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 362c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 363c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 364c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (tCount == 0 || t > intercepts.fTs[tCount - 1]) { 365c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *intercepts.fTs.append() = t; 366c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 367c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 3686008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return foundIntercept; 369c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 370c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 3716680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool cached(const InEdge* edge) { 372c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // FIXME: in the pathological case where there is a ton of edges, binary search? 373c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com size_t count = fCached.count(); 374c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (size_t index = 0; index < count; ++index) { 375c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (edge == fCached[index]) { 376c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return true; 377c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 378c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (edge < fCached[index]) { 379c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *fCached.insert(index) = edge; 380c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return false; 381c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 382c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 383c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *fCached.append() = edge; 384c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return false; 385c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 386c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 387c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com void complete(signed char winding) { 388c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPoint* ptPtr = fPts.begin(); 389c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPoint* ptLast = fPts.end(); 390c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (ptPtr == ptLast) { 391c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkDebugf("empty edge\n"); 392c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkASSERT(0); 393c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // FIXME: delete empty edge? 394c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 395c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 396c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fBounds.set(ptPtr->fX, ptPtr->fY, ptPtr->fX, ptPtr->fY); 397c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com ++ptPtr; 398c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com while (ptPtr != ptLast) { 399c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fBounds.growToInclude(ptPtr->fX, ptPtr->fY); 400c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com ++ptPtr; 401c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 4026008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fIntercepts.push_back_n(fVerbs.count()); 4036680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com if ((fWinding = winding) < 0) { // reverse verbs, pts, if bottom to top 4046680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com size_t index; 4056680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com size_t last = fPts.count() - 1; 4066680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com for (index = 0; index < last; ++index, --last) { 4076680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTSwap<SkPoint>(fPts[index], fPts[last]); 4086680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 4096680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com last = fVerbs.count() - 1; 4106680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com for (index = 0; index < last; ++index, --last) { 4116680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTSwap<uint8_t>(fVerbs[index], fVerbs[last]); 4126680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 4136680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 4146680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fContainsIntercepts = false; 415c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 416c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 417c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // temporary data : move this to a separate struct? 4186680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTDArray<const InEdge*> fCached; // list of edges already intercepted 419c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkTArray<Intercepts> fIntercepts; // one per verb 420c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 421c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // persistent data 422c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkTDArray<SkPoint> fPts; 423c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkTDArray<uint8_t> fVerbs; 424c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com Bounds fBounds; 425c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com signed char fWinding; 4266680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool fContainsIntercepts; 427c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 428c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 4296680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comclass InEdgeBuilder { 430c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.compublic: 431c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 4326680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comInEdgeBuilder(const SkPath& path, bool ignoreHorizontal, SkTArray<InEdge>& edges) 433c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com : fPath(path) 434c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com , fCurrentEdge(NULL) 435c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com , fEdges(edges) 436c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com , fIgnoreHorizontal(ignoreHorizontal) 437c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com{ 438c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com walk(); 439c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 440c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 441c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comprotected: 442c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 443c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid addEdge() { 444f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkASSERT(fCurrentEdge); 445c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fCurrentEdge->fPts.append(fPtCount - fPtOffset, &fPts[fPtOffset]); 446c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fPtOffset = 1; 447c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *fCurrentEdge->fVerbs.append() = fVerb; 448c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 449c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 4506008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.combool complete() { 4516008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (fCurrentEdge && fCurrentEdge->fVerbs.count()) { 4526008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fCurrentEdge->complete(fWinding); 4536008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fCurrentEdge = NULL; 4546008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return true; 4556008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 4566008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return false; 4576008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com} 4586008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 459c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comint direction(int count) { 460c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fPtCount = count; 461c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fIgnorableHorizontal = fIgnoreHorizontal && isHorizontal(); 462c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (fIgnorableHorizontal) { 463c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return 0; 464c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 465c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int last = count - 1; 466c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return fPts[0].fY == fPts[last].fY 4676680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com ? fPts[0].fX == fPts[last].fX ? 0 : fPts[0].fX < fPts[last].fX 4686680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com ? 1 : -1 : fPts[0].fY < fPts[last].fY ? 1 : -1; 469c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 470c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 471c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool isHorizontal() { 472c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkScalar y = fPts[0].fY; 473c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (int i = 1; i < fPtCount; ++i) { 474c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (fPts[i].fY != y) { 475c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return false; 476c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 477c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 478c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return true; 479c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 480c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 481c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid startEdge() { 4826008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (!fCurrentEdge) { 4836008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fCurrentEdge = fEdges.push_back_n(1); 4846008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 485c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fWinding = 0; 486c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fPtOffset = 0; 487c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 488c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 489c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid walk() { 490c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Iter iter(fPath, true); 4916008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com int winding; 492c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com while ((fVerb = iter.next(fPts)) != SkPath::kDone_Verb) { 493c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com switch (fVerb) { 494c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kMove_Verb: 495c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com startEdge(); 496c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com continue; 497c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kLine_Verb: 498c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com winding = direction(2); 499c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 500c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kQuad_Verb: 501c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com winding = direction(3); 502c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 503c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kCubic_Verb: 504c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com winding = direction(4); 505c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com break; 506c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com case SkPath::kClose_Verb: 507f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkASSERT(fCurrentEdge); 5086008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com complete(); 509c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com continue; 510c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com default: 511c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkDEBUGFAIL("bad verb"); 512c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 513c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 514c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (fIgnorableHorizontal) { 5156008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (complete()) { 5166008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com startEdge(); 5176008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 518c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com continue; 519c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 520c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (fWinding + winding == 0) { 521c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // FIXME: if prior verb or this verb is a horizontal line, reverse 522c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // it instead of starting a new edge 523f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkASSERT(fCurrentEdge); 524c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fCurrentEdge->complete(fWinding); 525c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com startEdge(); 526c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 527c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com fWinding = winding; 528c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com addEdge(); 529c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 5306b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (!complete()) { 5316b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (fCurrentEdge) { 5326b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com fEdges.pop_back(); 5336b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 5346b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 535c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 536c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 537c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comprivate: 538c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com const SkPath& fPath; 5396680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com InEdge* fCurrentEdge; 5406680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkTArray<InEdge>& fEdges; 541c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPoint fPts[4]; 542c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Verb fVerb; 543c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int fPtCount; 544c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int fPtOffset; 545c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com int8_t fWinding; 546c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bool fIgnorableHorizontal; 547c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com bool fIgnoreHorizontal; 548c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 549c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 5506680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstruct WorkEdge { 551c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkScalar bottom() const { 5526680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return fPts[verb()].fY; 553c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 554c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 5556680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com void init(const InEdge* edge) { 5566680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fEdge = edge; 5576680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fPts = edge->fPts.begin(); 5586680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fVerb = edge->fVerbs.begin(); 559c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 560c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 5616680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool next() { 5626680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkASSERT(fVerb < fEdge->fVerbs.end()); 5636680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fPts += *fVerb++; 5646680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return fVerb != fEdge->fVerbs.end(); 565c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 566c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 567c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath::Verb verb() const { 568c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return (SkPath::Verb) *fVerb; 569c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 570c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 5716008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ptrdiff_t verbIndex() const { 5726680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return fVerb - fEdge->fVerbs.begin(); 5736680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 5746680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 5756680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com int winding() const { 5766680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return fEdge->fWinding; 577c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 578c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 5796680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com const InEdge* fEdge; 580c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com const SkPoint* fPts; 581c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com const uint8_t* fVerb; 582c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 583c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 5846680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com// always constructed with SkTDArray because new edges are inserted 5856680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com// this may be a inappropriate optimization, suggesting that a separate array of 5866680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com// ActiveEdge* may be faster to insert and search 587c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comstruct ActiveEdge { 5886008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool operator<(const ActiveEdge& rh) const { 5896008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return fX < rh.fX; 5906008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 5916008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 5926008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com void calcLeft() { 5936008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fX = fWorkEdge.fPts[fWorkEdge.verb()].fX; 5946008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 5956008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 5966680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com void init(const InEdge* edge) { 5976680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fWorkEdge.init(edge); 5986680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com initT(); 5996680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 6006680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 6016680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com void initT() { 6026008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com const Intercepts& intercepts = fWorkEdge.fEdge->fIntercepts.front(); 6036008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkASSERT(fWorkEdge.verbIndex() <= fWorkEdge.fEdge->fIntercepts.count()); 6046008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com const Intercepts* interceptPtr = &intercepts + fWorkEdge.verbIndex(); 6056008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com fTs = &interceptPtr->fTs; 6066008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // the above is conceptually the same as 6076008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // fTs = &fWorkEdge.fEdge->fIntercepts[fWorkEdge.verbIndex()].fTs; 6086008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // but templated arrays don't allow returning a pointer to the end() element 6096680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com fTIndex = 0; 6106680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 6116680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 6126680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool nextT() { 6136680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com SkASSERT(fTIndex <= fTs->count()); 6146680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return ++fTIndex == fTs->count() + 1; 6156680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 6166680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 6176680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool next() { 6186680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com bool result = fWorkEdge.next(); 6196680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com initT(); 6206680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return result; 6216680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 622c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 6236680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com double t() { 6246680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com if (fTIndex == 0) { 6256680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return 0; 6266680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 6276680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com if (fTIndex > fTs->count()) { 6286680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return 1; 629c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 6306680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return (*fTs)[fTIndex - 1]; 631c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 632c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 6336680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com WorkEdge fWorkEdge; 6346680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com const SkTDArray<double>* fTs; 6356008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkScalar fX; 6366680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com int fTIndex; 6376008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool fSkip; 638c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 639c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 6406680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.comstatic void addToActive(SkTDArray<ActiveEdge>& activeEdges, const InEdge* edge) { 6416680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com size_t count = activeEdges.count(); 6426680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com for (size_t index = 0; index < count; ++index) { 6436680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com if (edge == activeEdges[index].fWorkEdge.fEdge) { 6446680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com return; 6456680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 6466680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 6476680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com ActiveEdge* active = activeEdges.append(); 6486680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com active->init(edge); 6496680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com} 6506680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 651f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // find any intersections in the range of active edges 652f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic void addBottomT(InEdge** currentPtr, InEdge** lastPtr, SkScalar bottom) { 653f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge** testPtr = currentPtr; 654f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge* test = *testPtr; 655f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com while (testPtr != lastPtr) { 656f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (test->fBounds.fBottom > bottom) { 657f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com WorkEdge wt; 658f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com wt.init(test); 659f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 660f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // FIXME: add all curve types 661f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // OPTIMIZATION: if bottom intersection does not change 662f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // the winding on either side of the split, don't intersect 663f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (wt.verb() == SkPath::kLine_Verb) { 664f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com double wtTs[2]; 665f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int pts = LineIntersect(wt.fPts, bottom, wtTs); 666f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (pts) { 6676008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com test->fContainsIntercepts |= test->add(wtTs, pts, 6686008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com wt.verbIndex()); 669f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 670f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 671f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } while (wt.next()); 672f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 673f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com test = *++testPtr; 674f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 675f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 676f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 677f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic void addIntersectingTs(InEdge** currentPtr, InEdge** lastPtr) { 678f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge** testPtr = currentPtr; 679f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge* test = *testPtr; 680f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com while (testPtr != lastPtr - 1) { 681f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge* next = *++testPtr; 682f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (!test->cached(next) 683f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com && Bounds::Intersects(test->fBounds, next->fBounds)) { 684f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com WorkEdge wt, wn; 685f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com wt.init(test); 686f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com wn.init(next); 687f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 688f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // FIXME: add all combinations of curve types 689f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (wt.verb() == SkPath::kLine_Verb 690f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com && wn.verb() == SkPath::kLine_Verb) { 691f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com double wtTs[2], wnTs[2]; 692f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int pts = LineIntersect(wt.fPts, wn.fPts, wtTs, wnTs); 693f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (pts) { 6946008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com test->fContainsIntercepts |= test->add(wtTs, pts, 6956008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com wt.verbIndex()); 6966008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com next->fContainsIntercepts |= next->add(wnTs, pts, 6976008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com wn.verbIndex()); 698f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 699f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 700f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } while (wt.bottom() <= wn.bottom() ? wt.next() : wn.next()); 701f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 702f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com test = next; 703f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 704f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 705f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 7066008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comstatic InEdge** advanceEdges(SkTDArray<ActiveEdge>& activeEdges, 7076008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com InEdge** currentPtr, InEdge** lastPtr, SkScalar y) { 7086008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com InEdge** testPtr = currentPtr - 1; 7096008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (++testPtr != lastPtr) { 7106008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if ((*testPtr)->fBounds.fBottom > y) { 7116008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com continue; 7126008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 7136008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com InEdge* test = *testPtr; 7146008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge* activePtr = activeEdges.begin() - 1; 7156008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge* lastActive = activeEdges.end(); 7166008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (++activePtr != lastActive) { 7176008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (activePtr->fWorkEdge.fEdge == test) { 7186008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com activeEdges.remove(activePtr - activeEdges.begin()); 7196008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com break; 7206008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 7216008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 7226008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (testPtr == currentPtr) { 7236008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ++currentPtr; 7246008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 7256008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 7266008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return currentPtr; 7276008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com} 7286008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 729f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com// compute bottom taking into account any intersected edges 730f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic void computeInterceptBottom(SkTDArray<ActiveEdge>& activeEdges, 7316008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkScalar y, SkScalar& bottom) { 732f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com ActiveEdge* activePtr = activeEdges.begin() - 1; 733f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com ActiveEdge* lastActive = activeEdges.end(); 734f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com while (++activePtr != lastActive) { 735f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const InEdge* test = activePtr->fWorkEdge.fEdge; 736f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (!test->fContainsIntercepts) { 737f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com continue; 738f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 739f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com WorkEdge wt; 740f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com wt.init(test); 741f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 742f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // FIXME: add all curve types 743f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const Intercepts& intercepts = test->fIntercepts[wt.verbIndex()]; 744f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const SkTDArray<double>& fTs = intercepts.fTs; 745f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com size_t count = fTs.count(); 746f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com for (size_t index = 0; index < count; ++index) { 747f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (wt.verb() == SkPath::kLine_Verb) { 748f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar yIntercept = LineYAtT(wt.fPts, fTs[index]); 7496008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (yIntercept > y && bottom > yIntercept) { 750f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com bottom = yIntercept; 751f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 752f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 753f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 754f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } while (wt.next()); 755f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 756f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 757f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 758f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic SkScalar findBottom(InEdge** currentPtr, 759f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge** edgeListEnd, SkTDArray<ActiveEdge>& activeEdges, SkScalar y, 7606008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bool asFill, InEdge**& testPtr) { 761f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge* current = *currentPtr; 762f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar bottom = current->fBounds.fBottom; 763f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 764f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // find the list of edges that cross y 7656008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com InEdge* test = *testPtr; 7666008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (testPtr != edgeListEnd) { 7676008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkScalar testTop = test->fBounds.fTop; 7686008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (bottom <= testTop) { 769f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com break; 770f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 7716008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkScalar testBottom = test->fBounds.fBottom; 772f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // OPTIMIZATION: Shortening the bottom is only interesting when filling 773f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // and when the edge is to the left of a longer edge. If it's a framing 774f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // edge, or part of the right, it won't effect the longer edges. 7756008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (testTop > y) { 7766008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bottom = testTop; 7776008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com break; 7786008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 7796008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (y < testBottom) { 7806008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (bottom > testBottom) { 7816008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com bottom = testBottom; 782f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 7836008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com addToActive(activeEdges, test); 784f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 7856008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com test = *++testPtr; 786f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 787f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com return bottom; 788f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 789f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 790f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comstatic void makeEdgeList(SkTArray<InEdge>& edges, InEdge& edgeSentinel, 791f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkTDArray<InEdge*>& edgeList) { 792c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com size_t edgeCount = edges.count(); 793c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (edgeCount == 0) { 794c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 795c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 796c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com for (size_t index = 0; index < edgeCount; ++index) { 797c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *edgeList.append() = &edges[index]; 798c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 799c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com edgeSentinel.fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 800c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com *edgeList.append() = &edgeSentinel; 801c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com ++edgeCount; 8026680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com QSort<InEdge>(edgeList.begin(), edgeCount); 803f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 804f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com 8056b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com 8066b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.comstatic void skipCoincidence(int lastWinding, int winding, int windingMask, 8076b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com ActiveEdge* activePtr, ActiveEdge* firstCoincident) { 8086b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (((lastWinding & windingMask) == 0) ^ (winding & windingMask) != 0) { 8096b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com return; 8106b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 8116b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (lastWinding) { 8126b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com activePtr->fSkip = false; 8136b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } else { 8146b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident->fSkip = false; 8156b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 8166b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com} 8176b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com 8186008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comstatic void sortHorizontal(SkTDArray<ActiveEdge>& activeEdges, 8196b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com SkTDArray<ActiveEdge*>& edgeList, int windingMask) { 8206008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com size_t edgeCount = activeEdges.count(); 8216008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (edgeCount == 0) { 8226008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com return; 8236008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 8246008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com size_t index; 8256008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com for (index = 0; index < edgeCount; ++index) { 8266008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge& activeEdge = activeEdges[index]; 8276008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com activeEdge.calcLeft(); 8286008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com activeEdge.fSkip = false; 8296008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com *edgeList.append() = &activeEdge; 8306008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 8316008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com QSort<ActiveEdge>(edgeList.begin(), edgeCount); 8326008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // remove coincident edges 8336b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com // OPTIMIZE: remove edges? This is tricky because the current logic expects 8346b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com // the winding count to be maintained while skipping coincident edges. In 8356b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com // addition to removing the coincident edges, the remaining edges would need 8366b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com // to have a different winding value, possibly different per intercept span. 8376b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com int lastWinding = 0; 8386b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com bool lastSkipped = false; 8396008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge* activePtr = edgeList[0]; 8406b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com ActiveEdge* firstCoincident = NULL; 8416b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com int winding = 0; 8426008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com for (index = 1; index < edgeCount; ++index) { 8436b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com winding += activePtr->fWorkEdge.winding(); 8446008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge* nextPtr = edgeList[index]; 8456b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (activePtr->fX == nextPtr->fX) { 8466b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (!firstCoincident) { 8476b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident = activePtr; 8486b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 8496b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com activePtr->fSkip = nextPtr->fSkip = lastSkipped = true; 8506b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } else if (lastSkipped) { 8516b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com skipCoincidence(lastWinding, winding, windingMask, activePtr, 8526b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident); 8536b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com lastSkipped = false; 8546b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident = NULL; 8556b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 8566b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (!lastSkipped) { 8576b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com lastWinding = winding; 858c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 8596008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com activePtr = nextPtr; 860f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 8616b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (lastSkipped) { 8626b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com winding += activePtr->fWorkEdge.winding(); 8636b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com skipCoincidence(lastWinding, winding, windingMask, activePtr, 8646b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com firstCoincident); 8656b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 866f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 8676680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 868f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com// stitch edge and t range that satisfies operation 8696008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comstatic void stitchEdge(SkTDArray<ActiveEdge*>& edgeList, SkScalar y, 870f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar bottom, int windingMask, OutEdgeBuilder& outBuilder) { 871f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int winding = 0; 8726008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge** activeHandle = edgeList.begin() - 1; 8736008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge** lastActive = edgeList.end(); 874c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (fShowDebugf) { 875c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkDebugf("%s y=%g bottom=%g\n", __FUNCTION__, y, bottom); 876c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 8776008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com while (++activeHandle != lastActive) { 8786008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com ActiveEdge* activePtr = *activeHandle; 879f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const WorkEdge& wt = activePtr->fWorkEdge; 880f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int lastWinding = winding; 881f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com winding += wt.winding(); 882c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com int opener = (lastWinding & windingMask) == 0; 883c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com bool closer = (winding & windingMask) == 0; 884c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkASSERT(!opener | !closer); 885c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com bool inWinding = opener | closer; 886c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com opener <<= kOpenerVerbBitShift; 887f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 888f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com double currentT = activePtr->t(); 8896008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkASSERT(currentT < 1); 890f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const SkPoint* points = wt.fPts; 891f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com bool last; 8926680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com do { 893f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com last = activePtr->nextT(); 894f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com double nextT = activePtr->t(); 895f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // FIXME: add all combinations of curve types 896f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (wt.verb() == SkPath::kLine_Verb) { 897f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkPoint clippedPts[2]; 898f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com const SkPoint* clipped; 899f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (currentT * nextT != 0 || currentT + nextT != 1) { 9006008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // OPTIMIZATION: if !inWinding, we only need 9016008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com // clipped[1].fY 902f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com LineSubDivide(points, currentT, nextT, clippedPts); 903f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com clipped = clippedPts; 904f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } else { 905f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com clipped = points; 9066680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 9076008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (inWinding && !activePtr->fSkip) { 908c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (fShowDebugf) { 909c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkDebugf("%s line %g,%g %g,%g\n", __FUNCTION__, 910c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com clipped[0].fX, clipped[0].fY, 911c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com clipped[1].fX, clipped[1].fY); 912c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 913c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com outBuilder.addLine(clipped, opener); 9146008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 915f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com if (clipped[1].fY >= bottom) { 9166008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (last) { 9176008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com activePtr->next(); 9186008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 919f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com goto nextEdge; 9206680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com } 921f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 922f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com currentT = nextT; 923f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } while (!last); 924f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } while (activePtr->next()); 925f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comnextEdge: 926f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com ; 927f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com } 928f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com} 9296680fb1dc0ca55e5e3ddd41cb26dcd74fce28f6ecaryclark@google.com 930f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comvoid simplify(const SkPath& path, bool asFill, SkPath& simple) { 931f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // returns 1 for evenodd, -1 for winding, regardless of inverse-ness 932f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com int windingMask = (path.getFillType() & 1) ? 1 : -1; 933f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com simple.reset(); 934f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com simple.setFillType(SkPath::kEvenOdd_FillType); 935f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // turn path into list of edges increasing in y 936f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // if an edge is a quad or a cubic with a y extrema, note it, but leave it unbroken 937f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // once we have a list, sort it, then walk the list (walk edges twice that have y extrema's on top) 938f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // and detect crossings -- look for raw bounds that cross over, then tight bounds that cross 939f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkTArray<InEdge> edges; 940f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdgeBuilder builder(path, asFill, edges); 941f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkTDArray<InEdge*> edgeList; 942f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge edgeSentinel; 943f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com makeEdgeList(edges, edgeSentinel, edgeList); 944f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge** currentPtr = edgeList.begin(); 945f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com // walk the sorted edges from top to bottom, computing accumulated winding 946f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkTDArray<ActiveEdge> activeEdges; 947f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com OutEdgeBuilder outBuilder(asFill); 948f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar y = (*currentPtr)->fBounds.fTop; 949f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com do { 950f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com InEdge** lastPtr = currentPtr; // find the edge below the bottom of the first set 951f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com SkScalar bottom = findBottom(currentPtr, edgeList.end(), 952f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com activeEdges, y, asFill, lastPtr); 953c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (lastPtr > currentPtr) { 954c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com addBottomT(currentPtr, lastPtr, bottom); 955c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com addIntersectingTs(currentPtr, lastPtr); 956c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com computeInterceptBottom(activeEdges, y, bottom); 957c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkTDArray<ActiveEdge*> activeEdgeList; 958c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com sortHorizontal(activeEdges, activeEdgeList, windingMask); 959c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com stitchEdge(activeEdgeList, y, bottom, windingMask, outBuilder); 960c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 961c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com y = bottom; 9626008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com currentPtr = advanceEdges(activeEdges, currentPtr, lastPtr, y); 963c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } while (*currentPtr != &edgeSentinel); 964c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com // assemble output path from string of pts, verbs 965f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com outBuilder.bridge(); 966f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.com outBuilder.assemble(simple); 967c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 968c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 9696008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comstatic void testSimplifyCoincidentVertical() { 9706008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkPath path, out; 9716008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.setFillType(SkPath::kWinding_FillType); 9726008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.addRect(10, 10, 30, 30); 9736008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.addRect(10, 30, 30, 40); 9746008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com simplify(path, true, out); 9756008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkRect rect; 9766008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (!out.isRect(&rect)) { 9776008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkDebugf("%s expected rect\n", __FUNCTION__); 9786008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 9796008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (rect != SkRect::MakeLTRB(10, 10, 30, 40)) { 9806008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkDebugf("%s expected union\n", __FUNCTION__); 9816008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 9826008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com} 983c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 9846008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comstatic void testSimplifyCoincidentHorizontal() { 9856008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkPath path, out; 9866008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.setFillType(SkPath::kWinding_FillType); 9876008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.addRect(10, 10, 30, 30); 9886008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.addRect(30, 10, 40, 30); 9896008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com simplify(path, true, out); 9906008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkRect rect; 9916008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (!out.isRect(&rect)) { 9926008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkDebugf("%s expected rect\n", __FUNCTION__); 9936008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 9946008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (rect != SkRect::MakeLTRB(10, 10, 40, 30)) { 9956008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkDebugf("%s expected union\n", __FUNCTION__); 9966008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 9976008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com} 9986008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 9996008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comstatic void testSimplifyMulti() { 1000c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com SkPath path, out; 1001c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com path.setFillType(SkPath::kWinding_FillType); 1002c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com path.addRect(10, 10, 30, 30); 1003c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com path.addRect(20, 20, 40, 40); 1004c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com simplify(path, true, out); 10056b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com SkPath expected; 10066b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com expected.setFillType(SkPath::kEvenOdd_FillType); 10076b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com expected.moveTo(10,10); // two cutout corners 10086b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com expected.lineTo(10,30); 10096b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com expected.lineTo(20,30); 10106b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com expected.lineTo(20,40); 10116b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com expected.lineTo(40,40); 10126b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com expected.lineTo(40,20); 10136b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com expected.lineTo(30,20); 10146b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com expected.lineTo(30,10); 10156b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com expected.lineTo(10,10); 10166b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com expected.close(); 10176b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (out != expected) { 10186b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com SkDebugf("%s expected equal\n", __FUNCTION__); 10196b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 10206b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com 1021c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com path = out; 1022c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com path.addRect(30, 10, 40, 20); 1023c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com path.addRect(10, 30, 20, 40); 1024c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com simplify(path, true, out); 10256b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com SkRect rect; 10266b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (!out.isRect(&rect)) { 10276b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com SkDebugf("%s expected rect\n", __FUNCTION__); 10286b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 10296b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) { 10306b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com SkDebugf("%s expected union\n", __FUNCTION__); 10316b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 10326b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com 1033c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com path = out; 1034c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction); 1035c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com simplify(path, true, out); 1036c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com if (!out.isEmpty()) { 10376008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkDebugf("%s expected empty\n", __FUNCTION__); 1038c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 1039c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 10406008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 10416008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comstatic void testSimplifyAddL() { 10426008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkPath path, out; 10436008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.moveTo(10,10); // 'L' shape 10446008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.lineTo(10,40); 10456008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.lineTo(40,40); 10466008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.lineTo(40,20); 10476008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.lineTo(30,20); 10486008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.lineTo(30,10); 10496008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.lineTo(10,10); 10506008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.close(); 10516008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com path.addRect(30, 10, 40, 20); // missing notch of 'L' 10526008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com simplify(path, true, out); 10536008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkRect rect; 10546008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (!out.isRect(&rect)) { 10556008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkDebugf("%s expected rect\n", __FUNCTION__); 10566008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 10576008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) { 10586008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com SkDebugf("%s expected union\n", __FUNCTION__); 10596008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 10606008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com} 10616008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 10626b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.comstatic void testSimplifyCoincidentCCW() { 10636b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com SkPath path, out; 10646b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction); 10656b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction); 10666b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com simplify(path, true, out); 10676b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com SkRect rect; 10686b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (!out.isRect(&rect)) { 10696b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com SkDebugf("%s expected rect\n", __FUNCTION__); 10706b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 10716b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) { 10726b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com SkDebugf("%s expected union\n", __FUNCTION__); 10736b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 10746b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com} 10756b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com 10766b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.comstatic void testSimplifyCoincidentCW() { 10776b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com SkPath path, out; 10786b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction); 10796b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com path.addRect(10, 10, 40, 40, SkPath::kCW_Direction); 10806b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com simplify(path, true, out); 10816b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (!out.isEmpty()) { 10826b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com SkDebugf("%s expected empty\n", __FUNCTION__); 10836b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 10846b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com} 10856b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com 1086c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.comstatic void testSimplifyCorner() { 1087c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkPath path, out; 1088c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com path.addRect(10, 10, 20, 20, SkPath::kCCW_Direction); 1089c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com path.addRect(20, 20, 40, 40, SkPath::kCW_Direction); 1090c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com simplify(path, true, out); 1091c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkTDArray<SkRect> boundsArray; 1092c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com contourBounds(out, boundsArray); 1093c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (boundsArray.count() != 2) { 1094c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkDebugf("%s expected 2 contours\n", __FUNCTION__); 1095c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com return; 1096c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 1097c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkRect one = SkRect::MakeLTRB(10, 10, 20, 20); 1098c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkRect two = SkRect::MakeLTRB(20, 20, 40, 40); 1099c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (boundsArray[0] != one && boundsArray[0] != two 1100c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com || boundsArray[1] != one && boundsArray[1] != two) { 1101c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkDebugf("%s expected match\n", __FUNCTION__); 1102c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 1103c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com} 1104c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com 1105c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com// non-intersecting test points, two equal sized rectangles 1106c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.comstatic void lookForFailingTests(const SkPoint* pts, size_t ptsSize, int width, 1107c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com int height, const SkRect& center) { 1108c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com size_t index = 0; 1109c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com for ( ; index < ptsSize; ++index) { 1110c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkPath path, out; 1111c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com path.addRect(center); 1112c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkRect test = SkRect::MakeXYWH(pts[index].fX, 1113c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com pts[index].fY, width, height); 1114c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com path.addRect(test); 1115c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com simplify(path, true, out); 1116c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkPath::Iter iter(out, false); 1117c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkPoint pts[2]; 1118c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkRect bounds[2]; 1119c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com bounds[0].setEmpty(); 1120c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com bounds[1].setEmpty(); 1121c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkRect* boundsPtr = bounds; 1122c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com int count = 0; 1123c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkPath::Verb verb; 1124c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { 1125c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com switch (verb) { 1126c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com case SkPath::kMove_Verb: 1127c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (!boundsPtr->isEmpty()) { 1128c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkASSERT(boundsPtr == bounds); 1129c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com ++boundsPtr; 1130c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 1131c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com boundsPtr->set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY); 1132c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com count = 0; 1133c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com break; 1134c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com case SkPath::kLine_Verb: 1135c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com count = 1; 1136c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com break; 1137c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com case SkPath::kClose_Verb: 1138c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com count = 0; 1139c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com break; 1140c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com default: 1141c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkDEBUGFAIL("bad verb"); 1142c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com return; 1143c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 1144c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com for (int i = 1; i <= count; ++i) { 1145c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com boundsPtr->growToInclude(pts[i].fX, pts[i].fY); 1146c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 1147c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 1148c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkASSERT(bounds[0] == center && bounds[1] == test 1149c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com || bounds[1] == center && bounds[0] == test); 1150c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 1151c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com} 1152c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com 1153c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.comstatic void twoEqualRects() { 1154c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkPoint pts[] = { 1155c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com { 0, 0}, {10, 0}, {20, 0}, {30, 0}, {40, 0}, {50, 0}, {60, 0}, // above 1156c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com { 0, 10}, { 0, 20}, { 0, 30}, { 0, 40}, { 0, 50}, { 0, 60}, // left 1157c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com {10, 60}, {20, 60}, {30, 60}, {40, 60}, {50, 60}, // below 1158c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com {60, 10}, {60, 20}, {60, 30}, {60, 40}, {60, 50}, {60, 60}, // right 1159c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com }; 1160c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com size_t ptsCount = sizeof(pts) / sizeof(pts[0]); 1161c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkRect center = SkRect::MakeLTRB(30, 30, 50, 50); 1162c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com lookForFailingTests(pts, ptsCount, 20, 20, center); 1163c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com} 1164c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com 1165c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.comstatic void largerOuter() { 1166c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkRect center = SkRect::MakeLTRB(50, 50, 70, 70); 1167c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com const size_t count = 9; 1168c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkPoint pts[count]; 1169c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com size_t index; 1170c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com for (index = 0; index < count; ++index) { // above 1171c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com pts[index].fX = index * 10; 1172c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com pts[index].fY = 0; 1173c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 1174c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com lookForFailingTests(pts, count, 40, 20, center); 1175c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com for (index = 0; index < count; ++index) { // left 1176c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com pts[index].fX = 0; 1177c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com pts[index].fY = index * 10; 1178c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 1179c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com lookForFailingTests(pts, count, 20, 40, center); 1180c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com for (index = 0; index < count; ++index) { // below 1181c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com pts[index].fX = index * 10; 1182c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com pts[index].fY = 80; 1183c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 1184c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com lookForFailingTests(pts, count, 40, 20, center); 1185c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com for (index = 0; index < count; ++index) { // right 1186c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com pts[index].fX = 80; 1187c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com pts[index].fY = index * 10; 1188c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 1189c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com lookForFailingTests(pts, count, 20, 40, center); 1190c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com} 1191c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com 1192c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.comstatic void smallerOuter() { 1193c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkPoint pts[] = { 1194c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com { 0, 0}, {10, 0}, {20, 0}, {30, 0}, {40, 0}, {50, 0}, {60, 0}, // above 1195c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com { 0, 10}, { 0, 20}, { 0, 30}, { 0, 40}, { 0, 50}, { 0, 60}, // left 1196c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com {10, 60}, {20, 60}, {30, 60}, {40, 60}, {50, 60}, // below 1197c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com {60, 10}, {60, 20}, {60, 30}, {60, 40}, {60, 50}, {60, 60}, // right 1198c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com }; 1199c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com size_t ptsCount = sizeof(pts) / sizeof(pts[0]); 1200c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com SkRect center = SkRect::MakeLTRB(20, 20, 50, 50); 1201c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com lookForFailingTests(pts, ptsCount, 10, 10, center); 1202c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com} 1203c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com 12046008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comvoid testSimplify(); 12056008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 12066008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comvoid (*simplifyTests[])() = { 1207c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com testSimplifyCorner, 12086b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com testSimplifyCoincidentCW, 12096b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com testSimplifyCoincidentCCW, 12106b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com testSimplifyCoincidentVertical, 12116b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com testSimplifyCoincidentHorizontal, 12126b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com testSimplifyAddL, 12136b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com testSimplifyMulti, 12146008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com}; 12156008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 12166008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comsize_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]); 12176008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 1218c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.comstatic void (*firstTest)() = 0; 1219c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.comstatic bool lookForFailing = false; 12206008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 12216008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.comvoid testSimplify() { 1222c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com/* look for failing test cases */ 1223c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com if (lookForFailing) { 1224c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com// rects do not touch 1225c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com twoEqualRects(); 1226c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com largerOuter(); 1227c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com smallerOuter(); 1228c17972e7acc784553445adc18f608a8c4b1beac8caryclark@google.com } 12296b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com size_t index = 0; 12306b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com if (firstTest) { 12316b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com while (index < simplifyTestsCount && simplifyTests[index] != firstTest) { 12326b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com ++index; 12336b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 12346b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com } 12356b9cfb34a3ed256a56571ebe3e39f5df940a16fbcaryclark@google.com for ( ; index < simplifyTestsCount; ++index) { 12366008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com (*simplifyTests[index])(); 12376008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com } 12386008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com} 12396008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 12406008c656f90026a3b434938454fd2b67cf135e0acaryclark@google.com 1241