SkRegion_path.cpp revision d3b65972aad96453ff4510caa3e25a2b847c6d1e
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 14757212f9469c8056bab3c85243dbb904e386eab95reed@google.com int64_t size = sk_64_mul(fStorageCount, sizeof(SkRegion::RunType)); 14857212f9469c8056bab3c85243dbb904e386eab95reed@google.com if (size < 0 || !sk_64_isS32(size)) { 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 151472629190eb3c8220742c584e19f3a07b2d09c8cskia.committer@gmail.com 15257212f9469c8056bab3c85243dbb904e386eab95reed@google.com fStorage = (SkRegion::RunType*)sk_malloc_flags(sk_64_asS32(size), 0); 15396fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (nullptr == fStorage) { 1548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 1558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 15796fcdcc219d2a0d3579719b84b28bede76efba64halcanary fCurrScanline = nullptr; // signal empty collection 15896fcdcc219d2a0d3579719b84b28bede76efba64halcanary fPrevScanline = nullptr; // signal first scanline 1598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 1608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkRgnBuilder::blitH(int x, int y, int width) { 16396fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (fCurrScanline == nullptr) { // first time 1648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fTop = (SkRegion::RunType)(y); 1658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline = (Scanline*)fStorage; 1668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fLastY = (SkRegion::RunType)(y); 1678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr = fCurrScanline->firstX(); 1688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(y >= fCurrScanline->fLastY); 1708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (y > fCurrScanline->fLastY) { 1728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // if we get here, we're done with fCurrScanline 1738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX())); 1748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int prevLastY = fCurrScanline->fLastY; 1768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!this->collapsWithPrev()) { 1778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevScanline = fCurrScanline; 1788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline = fCurrScanline->nextScanline(); 1798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (y - 1 > prevLastY) { // insert empty run 1828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fLastY = (SkRegion::RunType)(y - 1); 1838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fXCount = 0; 1848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline = fCurrScanline->nextScanline(); 1858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // setup for the new curr line 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fLastY = (SkRegion::RunType)(y); 1888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr = fCurrScanline->firstX(); 1898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // check if we should extend the current run, or add a new one 1928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) { 1938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr[-1] = (SkRegion::RunType)(x + width); 1948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr[0] = (SkRegion::RunType)(x); 1968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr[1] = (SkRegion::RunType)(x + width); 1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr += 2; 1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCurrXPtr - fStorage < fStorageCount); 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkRgnBuilder::computeRunCount() const { 20396fcdcc219d2a0d3579719b84b28bede76efba64halcanary if (fCurrScanline == nullptr) { 2048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 2058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkRegion::RunType* line = fStorage; 2088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline; 2098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 2 + (int)(stop - line); 2118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkRgnBuilder::copyToRect(SkIRect* r) const { 21496fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(fCurrScanline != nullptr); 2159c36a76102453db964cb6e51078a3d74d4126b2creed@google.com // A rect's scanline is [bottom intervals left right sentinel] == 5 2169c36a76102453db964cb6e51078a3d74d4126b2creed@google.com SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5); 2178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Scanline* line = (const Scanline*)fStorage; 2198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(line->fXCount == 2); 2208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1); 2228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const { 22596fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(fCurrScanline != nullptr); 2268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4); 2278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Scanline* line = (const Scanline*)fStorage; 2298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Scanline* stop = fCurrScanline; 2308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *runs++ = fTop; 2328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 2338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *runs++ = (SkRegion::RunType)(line->fLastY + 1); 2348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = line->fXCount; 2359c36a76102453db964cb6e51078a3d74d4126b2creed@google.com *runs++ = count >> 1; // intervalCount 2368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count) { 2378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType)); 2388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com runs += count; 2398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *runs++ = SkRegion::kRunTypeSentinel; 2418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com line = line->nextScanline(); 2428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } while (line < stop); 2438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(line == stop); 2448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *runs = SkRegion::kRunTypeSentinel; 2458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 247277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.comstatic unsigned verb_to_initial_last_index(unsigned verb) { 2488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static const uint8_t gPathVerbToInitialLastIndex[] = { 2498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0, // kMove_Verb 2508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1, // kLine_Verb 2518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2, // kQuad_Verb 252277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com 2, // kConic_Verb 2538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3, // kCubic_Verb 2548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0, // kClose_Verb 2558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 // kDone_Verb 2568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 257277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex)); 258277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com return gPathVerbToInitialLastIndex[verb]; 259277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com} 2608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 261277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.comstatic unsigned verb_to_max_edges(unsigned verb) { 2628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static const uint8_t gPathVerbToMaxEdges[] = { 2638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0, // kMove_Verb 2648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1, // kLine_Verb 2658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2, // kQuad_VerbB 266277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com 2, // kConic_VerbB 2678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3, // kCubic_Verb 2688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0, // kClose_Verb 2698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 // kDone_Verb 2708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 271277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges)); 272277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com return gPathVerbToMaxEdges[verb]; 273277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com} 2748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 275c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed// If returns 0, ignore itop and ibot 276277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.comstatic int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) { 2778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPath::Iter iter(path, true); 2788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint pts[4]; 2798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPath::Verb verb; 2808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int maxEdges = 0; 2828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar top = SkIntToScalar(SK_MaxS16); 2838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bot = SkIntToScalar(SK_MinS16); 2848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2854a3b714d73e585a3985d614600c6b79d5c8b1f1ereed@google.com while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 286277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com maxEdges += verb_to_max_edges(verb); 2878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 288277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com int lastIndex = verb_to_initial_last_index(verb); 2898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (lastIndex > 0) { 2908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 1; i <= lastIndex; i++) { 2918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (top > pts[i].fY) { 2928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com top = pts[i].fY; 2938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (bot < pts[i].fY) { 2948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bot = pts[i].fY; 2958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (SkPath::kMove_Verb == verb) { 2988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (top > pts[0].fY) { 2998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com top = pts[0].fY; 3008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (bot < pts[0].fY) { 3018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bot = pts[0].fY; 3028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 305c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed if (0 == maxEdges) { 306c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed return 0; // we have only moves+closes 307c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed } 3088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 309c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed SkASSERT(top <= bot); 310e1ca705cac4b946993f6cbf798e2a0ba27e739f3reed@google.com *itop = SkScalarRoundToInt(top); 311e1ca705cac4b946993f6cbf798e2a0ba27e739f3reed@google.com *ibot = SkScalarRoundToInt(bot); 3128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return maxEdges; 3138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 315c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freedstatic bool check_inverse_on_empty_return(SkRegion* dst, const SkPath& path, const SkRegion& clip) { 316c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed if (path.isInverseFillType()) { 317c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed return dst->set(clip); 318c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed } else { 319c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed return dst->setEmpty(); 320c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed } 321c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed} 322c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed 3238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkRegion::setPath(const SkPath& path, const SkRegion& clip) { 3248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDEBUGCODE(this->validate();) 3258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (clip.isEmpty()) { 3278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->setEmpty(); 3288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (path.isEmpty()) { 331c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed return check_inverse_on_empty_return(this, path, clip); 3328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // compute worst-case rgn-size for the path 3358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int pathTop, pathBot; 3368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot); 337c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed if (0 == pathTransitions) { 338c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed return check_inverse_on_empty_return(this, path, clip); 339c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed } 340fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 341c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed int clipTop, clipBot; 342c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed int clipTransitions = clip.count_runtype_values(&clipTop, &clipBot); 3438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int top = SkMax32(pathTop, clipTop); 3458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int bot = SkMin32(pathBot, clipBot); 346c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed if (top >= bot) { 347c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed return check_inverse_on_empty_return(this, path, clip); 348c1b11f1db69bea8d64ebf656ae92ea9ec6dbb40freed } 3498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRgnBuilder builder; 351fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 352b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com if (!builder.init(bot - top, 353b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com SkMax32(pathTransitions, clipTransitions), 354b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com path.isInverseFillType())) { 3558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // can't allocate working space, so return false 3568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->setEmpty(); 3578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScan::FillPath(path, clip, &builder); 3608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com builder.done(); 3618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = builder.computeRunCount(); 3638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count == 0) { 3648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->setEmpty(); 3658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (count == kRectRegionRuns) { 3668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com builder.copyToRect(&fBounds); 3678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->setRect(fBounds); 3688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 3699c36a76102453db964cb6e51078a3d74d4126b2creed@google.com SkRegion tmp; 3708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp.fRunHead = RunHead::Alloc(count); 3728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com builder.copyToRgn(tmp.fRunHead->writable_runs()); 3739c36a76102453db964cb6e51078a3d74d4126b2creed@google.com tmp.fRunHead->computeRunBounds(&tmp.fBounds); 3748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->swap(tmp); 3758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDEBUGCODE(this->validate();) 3778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 3788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///////////////////////////////////////////////////////////////////////////////////////////////// 3818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///////////////////////////////////////////////////////////////////////////////////////////////// 3828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstruct Edge { 3848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com enum { 3858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kY0Link = 0x01, 3868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kY1Link = 0x02, 387fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 3888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kCompleteLink = (kY0Link | kY1Link) 3898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 3908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType fX; 3928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType fY0, fY1; 3938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com uint8_t fFlags; 3948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* fNext; 395fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 3968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void set(int x, int y0, int y1) { 3978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(y0 != y1); 3988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fX = (SkRegion::RunType)(x); 4008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fY0 = (SkRegion::RunType)(y0); 4018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fY1 = (SkRegion::RunType)(y1); 4028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fFlags = 0; 40396fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkDEBUGCODE(fNext = nullptr;) 4048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 405fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 4068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int top() const { 4078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkFastMin32(fY0, fY1); 4088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 4108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic void find_link(Edge* base, Edge* stop) { 4128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(base < stop); 4138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (base->fFlags == Edge::kCompleteLink) { 4158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(base->fNext); 4168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return; 4178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(base + 1 < stop); 4208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int y0 = base->fY0; 4228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int y1 = base->fY1; 4238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* e = base; 4258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((base->fFlags & Edge::kY0Link) == 0) { 4268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (;;) { 4278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e += 1; 4288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) { 42996fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(nullptr == e->fNext); 4308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e->fNext = base; 4318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e->fFlags = SkToU8(e->fFlags | Edge::kY1Link); 4328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 4338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 436fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 4378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e = base; 4388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((base->fFlags & Edge::kY1Link) == 0) { 4398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (;;) { 4408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e += 1; 4418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) { 44296fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(nullptr == base->fNext); 4438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base->fNext = e; 4448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e->fFlags = SkToU8(e->fFlags | Edge::kY0Link); 4458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 4468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 449fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 4508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base->fFlags = Edge::kCompleteLink; 4518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic int extract_path(Edge* edge, Edge* stop, SkPath* path) { 4548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (0 == edge->fFlags) { 4558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge++; // skip over "used" edges 4568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(edge < stop); 4598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* base = edge; 4618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* prev = edge; 4628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge = edge->fNext; 4638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(edge != base); 4648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = 1; 4668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0)); 4678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com prev->fFlags = 0; 4688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 4698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear 4708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V 4718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H 4728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com prev = edge; 4748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge = edge->fNext; 4758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com count += 1; 4768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com prev->fFlags = 0; 4778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } while (edge != base); 4788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V 4798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->close(); 4808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count; 4818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 48360e0fee6d4acff638ccc9670c4055aced529a7a0bungemanstruct EdgeLT { 48460e0fee6d4acff638ccc9670c4055aced529a7a0bungeman bool operator()(const Edge& a, const Edge& b) const { 48560e0fee6d4acff638ccc9670c4055aced529a7a0bungeman return (a.fX == b.fX) ? a.top() < b.top() : a.fX < b.fX; 48660e0fee6d4acff638ccc9670c4055aced529a7a0bungeman } 48760e0fee6d4acff638ccc9670c4055aced529a7a0bungeman}; 4888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkRegion::getBoundaryPath(SkPath* path) const { 49096fcdcc219d2a0d3579719b84b28bede76efba64halcanary // path could safely be nullptr if we're empty, but the caller shouldn't 491d5d9dadcdd5fdbc8a17f3f398e3199b9d12c8d70tomhudson@google.com // *know* that 492d5d9dadcdd5fdbc8a17f3f398e3199b9d12c8d70tomhudson@google.com SkASSERT(path); 493d5d9dadcdd5fdbc8a17f3f398e3199b9d12c8d70tomhudson@google.com 4948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (this->isEmpty()) { 4958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 4968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkIRect& bounds = this->getBounds(); 4998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (this->isRect()) { 501fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com SkRect r; 5028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r.set(bounds); // this converts the ints to scalars 5038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->addRect(r); 5048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 5058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::Iterator iter(*this); 5088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTDArray<Edge> edges; 509fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 5108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) { 5118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* edge = edges.append(2); 5128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge[0].set(r.fLeft, r.fBottom, r.fTop); 5138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge[1].set(r.fRight, r.fTop, r.fBottom); 5148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 515fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 5168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = edges.count(); 5178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* start = edges.begin(); 5188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* stop = start + count; 51960e0fee6d4acff638ccc9670c4055aced529a7a0bungeman SkTQSort<Edge>(start, stop - 1, EdgeLT()); 5208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 52160e0fee6d4acff638ccc9670c4055aced529a7a0bungeman Edge* e; 5228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (e = start; e != stop; e++) { 5238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com find_link(e, stop); 5248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 5278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (e = start; e != stop; e++) { 52896fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkASSERT(e->fNext != nullptr); 5298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(e->fFlags == Edge::kCompleteLink); 5308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 5328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->incReserve(count << 1); 5348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 5358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(count > 1); 5368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com count -= extract_path(start, stop, path); 5378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } while (count > 0); 5388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 5408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 541