1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkRegionPriv.h" 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkBlitter.h" 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkScan.h" 1160e0fee6d4acff638ccc9670c4055aced529a7a0bungeman#include "SkTSort.h" 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkTDArray.h" 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkPath.h" 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 15b8f07988494a62fbe8fba70129b1bb9366e9f6eereed// The rgnbuilder caller *seems* to pass short counts, possible often seens early failure, so 16b8f07988494a62fbe8fba70129b1bb9366e9f6eereed// we may not want to promote this to a "std" routine just yet. 17b8f07988494a62fbe8fba70129b1bb9366e9f6eereedstatic bool sk_memeq32(const int32_t* SK_RESTRICT a, const int32_t* SK_RESTRICT b, int count) { 18b8f07988494a62fbe8fba70129b1bb9366e9f6eereed for (int i = 0; i < count; ++i) { 19b8f07988494a62fbe8fba70129b1bb9366e9f6eereed if (a[i] != b[i]) { 20b8f07988494a62fbe8fba70129b1bb9366e9f6eereed return false; 21b8f07988494a62fbe8fba70129b1bb9366e9f6eereed } 22b8f07988494a62fbe8fba70129b1bb9366e9f6eereed } 23b8f07988494a62fbe8fba70129b1bb9366e9f6eereed return true; 24b8f07988494a62fbe8fba70129b1bb9366e9f6eereed} 25b8f07988494a62fbe8fba70129b1bb9366e9f6eereed 268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comclass SkRgnBuilder : public SkBlitter { 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.compublic: 2873be1fc2b02757e3d98621d7cf735591aa6dffdbcommit-bot@chromium.org SkRgnBuilder(); 29d3b65972aad96453ff4510caa3e25a2b847c6d1eBrian Salomon ~SkRgnBuilder() override; 30fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // returns true if it could allocate the working storage needed 32b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com bool init(int maxHeight, int maxTransitions, bool pathIsInverse); 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void done() { 3596fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (fCurrScanline != nullptr) { 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX())); 378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!this->collapsWithPrev()) { // flush the last line 388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline = fCurrScanline->nextScanline(); 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int computeRunCount() const; 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void copyToRect(SkIRect*) const; 458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void copyToRgn(SkRegion::RunType runs[]) const; 468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4736352bf5e38f45a70ee4f4fc132a38048d38206dmtklein void blitH(int x, int y, int width) override; 487df9e4a87d84415391c167ea54cd389d4b423c2dherb void blitAntiH(int x, int y, const SkAlpha antialias[], const int16_t runs[]) override { 497df9e4a87d84415391c167ea54cd389d4b423c2dherb SkDEBUGFAIL("blitAntiH not implemented"); 507df9e4a87d84415391c167ea54cd389d4b423c2dherb } 518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void dump() const { 548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDebugf("SkRgnBuilder: Top = %d\n", fTop); 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Scanline* line = (Scanline*)fStorage; 568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (line < fCurrScanline) { 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount); 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 0; i < line->fXCount; i++) { 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDebugf(" %d", line->firstX()[i]); 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDebugf("\n"); 628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com line = line->nextScanline(); 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comprivate: 689c36a76102453db964cb6e51078a3d74d4126b2creed@google.com /* 699c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * Scanline mimics a row in the region, nearly. A row in a region is: 709c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * [Bottom IntervalCount [L R]... Sentinel] 719c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * while a Scanline is 729c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * [LastY XCount [L R]... uninitialized] 739c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * The two are the same length (which is good), but we have to transmute 749c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * the scanline a little when we convert it to a region-row. 759c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * 769c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * Potentially we could recode this to exactly match the row format, in 779c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * which case copyToRgn() could be a single memcpy. Not sure that is worth 789c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * the effort. 799c36a76102453db964cb6e51078a3d74d4126b2creed@google.com */ 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com struct Scanline { 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType fLastY; 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType fXCount; 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); } 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Scanline* nextScanline() const { 869c36a76102453db964cb6e51078a3d74d4126b2creed@google.com // add final +1 for the x-sentinel 879c36a76102453db964cb6e51078a3d74d4126b2creed@google.com return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1); 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType* fStorage; 918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Scanline* fCurrScanline; 928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Scanline* fPrevScanline; 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // points at next avialable x[] in fCurrScanline 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType* fCurrXPtr; 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType fTop; // first Y value 96fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int fStorageCount; 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool collapsWithPrev() { 10096fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (fPrevScanline != nullptr && 1018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevScanline->fLastY + 1 == fCurrScanline->fLastY && 1028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevScanline->fXCount == fCurrScanline->fXCount && 103b8f07988494a62fbe8fba70129b1bb9366e9f6eereed sk_memeq32(fPrevScanline->firstX(), fCurrScanline->firstX(), fCurrScanline->fXCount)) 1048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 1058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // update the height of fPrevScanline 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevScanline->fLastY = fCurrScanline->fLastY; 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 1128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 11373be1fc2b02757e3d98621d7cf735591aa6dffdbcommit-bot@chromium.orgSkRgnBuilder::SkRgnBuilder() 11496fcdcc219d2a0d3579719b84b28bede76efba64halcanary : fStorage(nullptr) { 11573be1fc2b02757e3d98621d7cf735591aa6dffdbcommit-bot@chromium.org} 11673be1fc2b02757e3d98621d7cf735591aa6dffdbcommit-bot@chromium.org 1178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkRgnBuilder::~SkRgnBuilder() { 1188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sk_free(fStorage); 1198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 121b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.combool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) { 1228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((maxHeight | maxTransitions) < 0) { 1238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 1248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 126b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com if (pathIsInverse) { 127b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com // allow for additional X transitions to "invert" each scanline 128b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com // [ L' ... normal transitions ... R' ] 129b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com // 130b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com maxTransitions += 2; 131b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com } 132b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // compute the count with +1 and +3 slop for the working buffer 13457212f9469c8056bab3c85243dbb904e386eab95reed@google.com int64_t count = sk_64_mul(maxHeight + 1, 3 + maxTransitions); 135b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com 136b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com if (pathIsInverse) { 137b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com // allow for two "empty" rows for the top and bottom 138b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com // [ Y, 1, L, R, S] == 5 (*2 for top and bottom) 13957212f9469c8056bab3c85243dbb904e386eab95reed@google.com count += 10; 140b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com } 141b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com 14257212f9469c8056bab3c85243dbb904e386eab95reed@google.com if (count < 0 || !sk_64_isS32(count)) { 1438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 14557212f9469c8056bab3c85243dbb904e386eab95reed@google.com fStorageCount = sk_64_asS32(count); 1468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1478dc8dbc8211e7b0245a6e7db911265efbe0fccafMike Reed fStorage = (SkRegion::RunType*)sk_malloc_canfail(fStorageCount, sizeof(SkRegion::RunType)); 14896fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == fStorage) { 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 15296fcdcc219d2a0d3579719b84b28bede76efba64halcanary fCurrScanline = nullptr; // signal empty collection 15396fcdcc219d2a0d3579719b84b28bede76efba64halcanary fPrevScanline = nullptr; // signal first scanline 1548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 1558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkRgnBuilder::blitH(int x, int y, int width) { 15896fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (fCurrScanline == nullptr) { // first time 1598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fTop = (SkRegion::RunType)(y); 1608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline = (Scanline*)fStorage; 1618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fLastY = (SkRegion::RunType)(y); 1628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr = fCurrScanline->firstX(); 1638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(y >= fCurrScanline->fLastY); 1658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (y > fCurrScanline->fLastY) { 1678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // if we get here, we're done with fCurrScanline 1688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX())); 1698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int prevLastY = fCurrScanline->fLastY; 1718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!this->collapsWithPrev()) { 1728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevScanline = fCurrScanline; 1738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline = fCurrScanline->nextScanline(); 1748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (y - 1 > prevLastY) { // insert empty run 1778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fLastY = (SkRegion::RunType)(y - 1); 1788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fXCount = 0; 1798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline = fCurrScanline->nextScanline(); 1808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // setup for the new curr line 1828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fLastY = (SkRegion::RunType)(y); 1838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr = fCurrScanline->firstX(); 1848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // check if we should extend the current run, or add a new one 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) { 1888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr[-1] = (SkRegion::RunType)(x + width); 1898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr[0] = (SkRegion::RunType)(x); 1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr[1] = (SkRegion::RunType)(x + width); 1928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr += 2; 1938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCurrXPtr - fStorage < fStorageCount); 1958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkRgnBuilder::computeRunCount() const { 19896fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (fCurrScanline == nullptr) { 1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkRegion::RunType* line = fStorage; 2038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline; 2048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 2 + (int)(stop - line); 2068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkRgnBuilder::copyToRect(SkIRect* r) const { 20996fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(fCurrScanline != nullptr); 2109c36a76102453db964cb6e51078a3d74d4126b2creed@google.com // A rect's scanline is [bottom intervals left right sentinel] == 5 2119c36a76102453db964cb6e51078a3d74d4126b2creed@google.com SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5); 2128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Scanline* line = (const Scanline*)fStorage; 2148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(line->fXCount == 2); 2158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1); 2178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const { 22096fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(fCurrScanline != nullptr); 2218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4); 2228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Scanline* line = (const Scanline*)fStorage; 2248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Scanline* stop = fCurrScanline; 2258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *runs++ = fTop; 2278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 2288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *runs++ = (SkRegion::RunType)(line->fLastY + 1); 2298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = line->fXCount; 2309c36a76102453db964cb6e51078a3d74d4126b2creed@google.com *runs++ = count >> 1; // intervalCount 2318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count) { 2328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType)); 2338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com runs += count; 2348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *runs++ = SkRegion::kRunTypeSentinel; 2368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com line = line->nextScanline(); 2378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } while (line < stop); 2388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(line == stop); 2398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *runs = SkRegion::kRunTypeSentinel; 2408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 242277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.comstatic unsigned verb_to_initial_last_index(unsigned verb) { 2438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static const uint8_t gPathVerbToInitialLastIndex[] = { 2448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0, // kMove_Verb 2458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1, // kLine_Verb 2468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2, // kQuad_Verb 247277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com 2, // kConic_Verb 2488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3, // kCubic_Verb 2498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0, // kClose_Verb 2508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 // kDone_Verb 2518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 252277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex)); 253277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com return gPathVerbToInitialLastIndex[verb]; 254277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com} 2558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 256277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.comstatic unsigned verb_to_max_edges(unsigned verb) { 2578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static const uint8_t gPathVerbToMaxEdges[] = { 2588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0, // kMove_Verb 2598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1, // kLine_Verb 2608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2, // kQuad_VerbB 261277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com 2, // kConic_VerbB 2628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3, // kCubic_Verb 2638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0, // kClose_Verb 2648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 // kDone_Verb 2658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 266277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges)); 267277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com return gPathVerbToMaxEdges[verb]; 268277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com} 2698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 270c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed// If returns 0, ignore itop and ibot 271277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.comstatic int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) { 2728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPath::Iter iter(path, true); 2738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint pts[4]; 2748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPath::Verb verb; 2758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int maxEdges = 0; 2778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar top = SkIntToScalar(SK_MaxS16); 2788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bot = SkIntToScalar(SK_MinS16); 2798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2804a3b714d73e585a3985d614600c6b79d5c8b1f1ereed@google.com while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 281277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com maxEdges += verb_to_max_edges(verb); 2828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 283277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com int lastIndex = verb_to_initial_last_index(verb); 2848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (lastIndex > 0) { 2858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 1; i <= lastIndex; i++) { 2868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (top > pts[i].fY) { 2878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com top = pts[i].fY; 2888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (bot < pts[i].fY) { 2898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bot = pts[i].fY; 2908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (SkPath::kMove_Verb == verb) { 2938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (top > pts[0].fY) { 2948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com top = pts[0].fY; 2958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (bot < pts[0].fY) { 2968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bot = pts[0].fY; 2978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 300c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed if (0 == maxEdges) { 301c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed return 0; // we have only moves+closes 302c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed } 3038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 304c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed SkASSERT(top <= bot); 305e1ca705cac4b946993f6cbf798e2a0ba27e739f3reed@google.com *itop = SkScalarRoundToInt(top); 306e1ca705cac4b946993f6cbf798e2a0ba27e739f3reed@google.com *ibot = SkScalarRoundToInt(bot); 3078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return maxEdges; 3088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 310c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freedstatic bool check_inverse_on_empty_return(SkRegion* dst, const SkPath& path, const SkRegion& clip) { 311c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed if (path.isInverseFillType()) { 312c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed return dst->set(clip); 313c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed } else { 314c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed return dst->setEmpty(); 315c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed } 316c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed} 317c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed 3188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkRegion::setPath(const SkPath& path, const SkRegion& clip) { 3198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDEBUGCODE(this->validate();) 3208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3211c6e7831e517c9a2026233fc76f6196da4b9053bMike Reed if (clip.isEmpty() || !path.isFinite()) { 3228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->setEmpty(); 3238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (path.isEmpty()) { 326c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed return check_inverse_on_empty_return(this, path, clip); 3278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // compute worst-case rgn-size for the path 3308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int pathTop, pathBot; 3318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot); 332c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed if (0 == pathTransitions) { 333c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed return check_inverse_on_empty_return(this, path, clip); 334c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed } 335fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 336c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed int clipTop, clipBot; 337c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed int clipTransitions = clip.count_runtype_values(&clipTop, &clipBot); 3388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int top = SkMax32(pathTop, clipTop); 3408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int bot = SkMin32(pathBot, clipBot); 341c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed if (top >= bot) { 342c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed return check_inverse_on_empty_return(this, path, clip); 343c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed } 3448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRgnBuilder builder; 346fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 347b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com if (!builder.init(bot - top, 348b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com SkMax32(pathTransitions, clipTransitions), 349b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com path.isInverseFillType())) { 3508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // can't allocate working space, so return false 3518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->setEmpty(); 3528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScan::FillPath(path, clip, &builder); 3558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com builder.done(); 3568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = builder.computeRunCount(); 3588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count == 0) { 3598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->setEmpty(); 3608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (count == kRectRegionRuns) { 3618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com builder.copyToRect(&fBounds); 3628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->setRect(fBounds); 3638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 3649c36a76102453db964cb6e51078a3d74d4126b2creed@google.com SkRegion tmp; 3658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp.fRunHead = RunHead::Alloc(count); 3678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com builder.copyToRgn(tmp.fRunHead->writable_runs()); 3689c36a76102453db964cb6e51078a3d74d4126b2creed@google.com tmp.fRunHead->computeRunBounds(&tmp.fBounds); 3698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->swap(tmp); 3708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDEBUGCODE(this->validate();) 3728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 3738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///////////////////////////////////////////////////////////////////////////////////////////////// 3768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///////////////////////////////////////////////////////////////////////////////////////////////// 3778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstruct Edge { 3798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com enum { 3808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kY0Link = 0x01, 3818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kY1Link = 0x02, 382fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 3838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kCompleteLink = (kY0Link | kY1Link) 3848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 3858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType fX; 3878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType fY0, fY1; 3888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com uint8_t fFlags; 3898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* fNext; 390fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 3918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void set(int x, int y0, int y1) { 3928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(y0 != y1); 3938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fX = (SkRegion::RunType)(x); 3958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fY0 = (SkRegion::RunType)(y0); 3968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fY1 = (SkRegion::RunType)(y1); 3978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fFlags = 0; 39896fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkDEBUGCODE(fNext = nullptr;) 3998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 400fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 4018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int top() const { 4028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkFastMin32(fY0, fY1); 4038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 4058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic void find_link(Edge* base, Edge* stop) { 4078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(base < stop); 4088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (base->fFlags == Edge::kCompleteLink) { 4108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(base->fNext); 4118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return; 4128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(base + 1 < stop); 4158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int y0 = base->fY0; 4178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int y1 = base->fY1; 4188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* e = base; 4208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((base->fFlags & Edge::kY0Link) == 0) { 4218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (;;) { 4228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e += 1; 4238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) { 42496fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(nullptr == e->fNext); 4258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e->fNext = base; 4268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e->fFlags = SkToU8(e->fFlags | Edge::kY1Link); 4278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 4288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 431fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 4328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e = base; 4338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((base->fFlags & Edge::kY1Link) == 0) { 4348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (;;) { 4358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e += 1; 4368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) { 43796fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(nullptr == base->fNext); 4388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base->fNext = e; 4398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e->fFlags = SkToU8(e->fFlags | Edge::kY0Link); 4408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 4418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 444fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 4458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base->fFlags = Edge::kCompleteLink; 4468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic int extract_path(Edge* edge, Edge* stop, SkPath* path) { 4498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (0 == edge->fFlags) { 4508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge++; // skip over "used" edges 4518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(edge < stop); 4548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* base = edge; 4568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* prev = edge; 4578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge = edge->fNext; 4588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(edge != base); 4598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = 1; 4618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0)); 4628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com prev->fFlags = 0; 4638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 4648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear 4658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V 4668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H 4678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com prev = edge; 4698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge = edge->fNext; 4708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com count += 1; 4718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com prev->fFlags = 0; 4728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } while (edge != base); 4738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V 4748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->close(); 4758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count; 4768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 47860e0fee6d4acff638ccc9670c4055aced529a7a0bungemanstruct EdgeLT { 47960e0fee6d4acff638ccc9670c4055aced529a7a0bungeman bool operator()(const Edge& a, const Edge& b) const { 48060e0fee6d4acff638ccc9670c4055aced529a7a0bungeman return (a.fX == b.fX) ? a.top() < b.top() : a.fX < b.fX; 48160e0fee6d4acff638ccc9670c4055aced529a7a0bungeman } 48260e0fee6d4acff638ccc9670c4055aced529a7a0bungeman}; 4838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkRegion::getBoundaryPath(SkPath* path) const { 48596fcdcc219d2a0d3579719b84b28bede76efba64halcanary // path could safely be nullptr if we're empty, but the caller shouldn't 486d5d9dadcdd5fdbc8a17f3f398e3199b9d12c8d70tomhudson@google.com // *know* that 487d5d9dadcdd5fdbc8a17f3f398e3199b9d12c8d70tomhudson@google.com SkASSERT(path); 488d5d9dadcdd5fdbc8a17f3f398e3199b9d12c8d70tomhudson@google.com 4898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (this->isEmpty()) { 4908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 4918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkIRect& bounds = this->getBounds(); 4948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (this->isRect()) { 496fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com SkRect r; 4978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r.set(bounds); // this converts the ints to scalars 4988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->addRect(r); 4998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 5008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::Iterator iter(*this); 5038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTDArray<Edge> edges; 504fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 5058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) { 5068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* edge = edges.append(2); 5078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge[0].set(r.fLeft, r.fBottom, r.fTop); 5088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge[1].set(r.fRight, r.fTop, r.fBottom); 5098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 510fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 5118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = edges.count(); 5128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* start = edges.begin(); 5138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* stop = start + count; 51460e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkTQSort<Edge>(start, stop - 1, EdgeLT()); 5158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 51660e0fee6d4acff638ccc9670c4055aced529a7a0bungeman Edge* e; 5178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (e = start; e != stop; e++) { 5188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com find_link(e, stop); 5198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 5228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (e = start; e != stop; e++) { 52396fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(e->fNext != nullptr); 5248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(e->fFlags == Edge::kCompleteLink); 5258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 5278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->incReserve(count << 1); 5298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 5308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(count > 1); 5318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com count -= extract_path(start, stop, path); 5328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } while (count > 0); 5338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 5358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 536