SkRegion_path.cpp revision b58ba8912ab1a372eb60ab111f477b915eb3da4d
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 8ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkRegionPriv.h" 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkBlitter.h" 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkScan.h" 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkTDArray.h" 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkPath.h" 158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comclass SkRgnBuilder : public SkBlitter { 178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.compublic: 188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com virtual ~SkRgnBuilder(); 19fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // returns true if it could allocate the working storage needed 21b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com bool init(int maxHeight, int maxTransitions, bool pathIsInverse); 228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void done() { 248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fCurrScanline != NULL) { 258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX())); 268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!this->collapsWithPrev()) { // flush the last line 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline = fCurrScanline->nextScanline(); 288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int computeRunCount() const; 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void copyToRect(SkIRect*) const; 348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void copyToRgn(SkRegion::RunType runs[]) const; 358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com virtual void blitH(int x, int y, int width); 378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void dump() const { 408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDebugf("SkRgnBuilder: Top = %d\n", fTop); 418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Scanline* line = (Scanline*)fStorage; 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (line < fCurrScanline) { 438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount); 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 0; i < line->fXCount; i++) { 458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDebugf(" %d", line->firstX()[i]); 468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDebugf("\n"); 488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com line = line->nextScanline(); 508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comprivate: 549c36a76102453db964cb6e51078a3d74d4126b2creed@google.com /* 559c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * Scanline mimics a row in the region, nearly. A row in a region is: 569c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * [Bottom IntervalCount [L R]... Sentinel] 579c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * while a Scanline is 589c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * [LastY XCount [L R]... uninitialized] 599c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * The two are the same length (which is good), but we have to transmute 609c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * the scanline a little when we convert it to a region-row. 619c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * 629c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * Potentially we could recode this to exactly match the row format, in 639c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * which case copyToRgn() could be a single memcpy. Not sure that is worth 649c36a76102453db964cb6e51078a3d74d4126b2creed@google.com * the effort. 659c36a76102453db964cb6e51078a3d74d4126b2creed@google.com */ 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com struct Scanline { 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType fLastY; 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType fXCount; 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); } 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Scanline* nextScanline() const { 729c36a76102453db964cb6e51078a3d74d4126b2creed@google.com // add final +1 for the x-sentinel 739c36a76102453db964cb6e51078a3d74d4126b2creed@google.com return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1); 748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType* fStorage; 778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Scanline* fCurrScanline; 788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Scanline* fPrevScanline; 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // points at next avialable x[] in fCurrScanline 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType* fCurrXPtr; 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType fTop; // first Y value 82fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int fStorageCount; 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bool collapsWithPrev() { 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fPrevScanline != NULL && 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevScanline->fLastY + 1 == fCurrScanline->fLastY && 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevScanline->fXCount == fCurrScanline->fXCount && 898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com !memcmp(fPrevScanline->firstX(), 908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->firstX(), 918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fXCount * sizeof(SkRegion::RunType))) 928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com { 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // update the height of fPrevScanline 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevScanline->fLastY = fCurrScanline->fLastY; 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 1008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comSkRgnBuilder::~SkRgnBuilder() { 1028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com sk_free(fStorage); 1038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 105b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.combool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) { 1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((maxHeight | maxTransitions) < 0) { 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Sk64 count, size; 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 112b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com if (pathIsInverse) { 113b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com // allow for additional X transitions to "invert" each scanline 114b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com // [ L' ... normal transitions ... R' ] 115b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com // 116b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com maxTransitions += 2; 117b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com } 118b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com 1198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // compute the count with +1 and +3 slop for the working buffer 1208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com count.setMul(maxHeight + 1, 3 + maxTransitions); 121b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com 122b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com if (pathIsInverse) { 123b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com // allow for two "empty" rows for the top and bottom 124b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com // [ Y, 1, L, R, S] == 5 (*2 for top and bottom) 125b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com count.add(10); 126b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com } 127b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com 1288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!count.is32() || count.isNeg()) { 1298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 1308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fStorageCount = count.get32(); 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com size.setMul(fStorageCount, sizeof(SkRegion::RunType)); 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!size.is32() || size.isNeg()) { 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 137b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fStorage = (SkRegion::RunType*)sk_malloc_flags(size.get32(), 0); 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (NULL == fStorage) { 1408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 1418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline = NULL; // signal empty collection 1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevScanline = NULL; // signal first scanline 1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 1468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkRgnBuilder::blitH(int x, int y, int width) { 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fCurrScanline == NULL) { // first time 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fTop = (SkRegion::RunType)(y); 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline = (Scanline*)fStorage; 1528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fLastY = (SkRegion::RunType)(y); 1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr = fCurrScanline->firstX(); 1548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(y >= fCurrScanline->fLastY); 1568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (y > fCurrScanline->fLastY) { 1588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // if we get here, we're done with fCurrScanline 1598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX())); 1608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int prevLastY = fCurrScanline->fLastY; 1628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (!this->collapsWithPrev()) { 1638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fPrevScanline = fCurrScanline; 1648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline = fCurrScanline->nextScanline(); 1658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (y - 1 > prevLastY) { // insert empty run 1688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fLastY = (SkRegion::RunType)(y - 1); 1698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fXCount = 0; 1708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline = fCurrScanline->nextScanline(); 1718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // setup for the new curr line 1738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrScanline->fLastY = (SkRegion::RunType)(y); 1748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr = fCurrScanline->firstX(); 1758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // check if we should extend the current run, or add a new one 1788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) { 1798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr[-1] = (SkRegion::RunType)(x + width); 1808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 1818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr[0] = (SkRegion::RunType)(x); 1828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr[1] = (SkRegion::RunType)(x + width); 1838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fCurrXPtr += 2; 1848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCurrXPtr - fStorage < fStorageCount); 1868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkRgnBuilder::computeRunCount() const { 1898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (fCurrScanline == NULL) { 1908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 0; 1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkRegion::RunType* line = fStorage; 1948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline; 1958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 2 + (int)(stop - line); 1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkRgnBuilder::copyToRect(SkIRect* r) const { 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCurrScanline != NULL); 2019c36a76102453db964cb6e51078a3d74d4126b2creed@google.com // A rect's scanline is [bottom intervals left right sentinel] == 5 2029c36a76102453db964cb6e51078a3d74d4126b2creed@google.com SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5); 2038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Scanline* line = (const Scanline*)fStorage; 2058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(line->fXCount == 2); 2068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1); 2088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const { 2118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(fCurrScanline != NULL); 2128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4); 2138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Scanline* line = (const Scanline*)fStorage; 2158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const Scanline* stop = fCurrScanline; 2168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *runs++ = fTop; 2188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 2198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *runs++ = (SkRegion::RunType)(line->fLastY + 1); 2208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = line->fXCount; 2219c36a76102453db964cb6e51078a3d74d4126b2creed@google.com *runs++ = count >> 1; // intervalCount 2228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count) { 2238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType)); 2248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com runs += count; 2258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *runs++ = SkRegion::kRunTypeSentinel; 2278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com line = line->nextScanline(); 2288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } while (line < stop); 2298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(line == stop); 2308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *runs = SkRegion::kRunTypeSentinel; 2318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 233277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.comstatic unsigned verb_to_initial_last_index(unsigned verb) { 2348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static const uint8_t gPathVerbToInitialLastIndex[] = { 2358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0, // kMove_Verb 2368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1, // kLine_Verb 2378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2, // kQuad_Verb 238277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com 2, // kConic_Verb 2398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3, // kCubic_Verb 2408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0, // kClose_Verb 2418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 // kDone_Verb 2428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 243277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex)); 244277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com return gPathVerbToInitialLastIndex[verb]; 245277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com} 2468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 247277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.comstatic unsigned verb_to_max_edges(unsigned verb) { 2488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static const uint8_t gPathVerbToMaxEdges[] = { 2498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0, // kMove_Verb 2508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1, // kLine_Verb 2518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2, // kQuad_VerbB 252277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com 2, // kConic_VerbB 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(gPathVerbToMaxEdges)); 258277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com return gPathVerbToMaxEdges[verb]; 259277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com} 2608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 261277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com 262277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.comstatic int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) { 2638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPath::Iter iter(path, true); 2648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPoint pts[4]; 2658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkPath::Verb verb; 2668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int maxEdges = 0; 2688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar top = SkIntToScalar(SK_MaxS16); 2698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScalar bot = SkIntToScalar(SK_MinS16); 2708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2714a3b714d73e585a3985d614600c6b79d5c8b1f1ereed@google.com while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 272277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com maxEdges += verb_to_max_edges(verb); 2738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 274277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com int lastIndex = verb_to_initial_last_index(verb); 2758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (lastIndex > 0) { 2768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (int i = 1; i <= lastIndex; i++) { 2778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (top > pts[i].fY) { 2788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com top = pts[i].fY; 2798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (bot < pts[i].fY) { 2808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bot = pts[i].fY; 2818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (SkPath::kMove_Verb == verb) { 2848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (top > pts[0].fY) { 2858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com top = pts[0].fY; 2868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (bot < pts[0].fY) { 2878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com bot = pts[0].fY; 2888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 2918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(top <= bot); 2928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *itop = SkScalarRound(top); 2948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com *ibot = SkScalarRound(bot); 2958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return maxEdges; 2968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 2978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkRegion::setPath(const SkPath& path, const SkRegion& clip) { 2998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDEBUGCODE(this->validate();) 3008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (clip.isEmpty()) { 3028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->setEmpty(); 3038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (path.isEmpty()) { 3068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (path.isInverseFillType()) { 3078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->set(clip); 3088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 3098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->setEmpty(); 3108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // compute worst-case rgn-size for the path 3148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int pathTop, pathBot; 3158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot); 3168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int clipTop, clipBot; 3178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int clipTransitions; 318fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 3198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com clipTransitions = clip.count_runtype_values(&clipTop, &clipBot); 3208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int top = SkMax32(pathTop, clipTop); 3228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int bot = SkMin32(pathBot, clipBot); 3238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (top >= bot) 3258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->setEmpty(); 3268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRgnBuilder builder; 328fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 329b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com if (!builder.init(bot - top, 330b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com SkMax32(pathTransitions, clipTransitions), 331b58ba8912ab1a372eb60ab111f477b915eb3da4dreed@google.com path.isInverseFillType())) { 3328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // can't allocate working space, so return false 3338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->setEmpty(); 3348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkScan::FillPath(path, clip, &builder); 3378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com builder.done(); 3388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = builder.computeRunCount(); 3408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (count == 0) { 3418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return this->setEmpty(); 3428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else if (count == kRectRegionRuns) { 3438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com builder.copyToRect(&fBounds); 3448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->setRect(fBounds); 3458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } else { 3469c36a76102453db964cb6e51078a3d74d4126b2creed@google.com SkRegion tmp; 3478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com tmp.fRunHead = RunHead::Alloc(count); 3498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com builder.copyToRgn(tmp.fRunHead->writable_runs()); 3509c36a76102453db964cb6e51078a3d74d4126b2creed@google.com tmp.fRunHead->computeRunBounds(&tmp.fBounds); 3518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com this->swap(tmp); 3528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDEBUGCODE(this->validate();) 3548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 3558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 3568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///////////////////////////////////////////////////////////////////////////////////////////////// 3588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///////////////////////////////////////////////////////////////////////////////////////////////// 3598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstruct Edge { 3618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com enum { 3628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kY0Link = 0x01, 3638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kY1Link = 0x02, 364fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 3658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kCompleteLink = (kY0Link | kY1Link) 3668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com }; 3678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType fX; 3698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::RunType fY0, fY1; 3708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com uint8_t fFlags; 3718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* fNext; 372fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 3738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com void set(int x, int y0, int y1) { 3748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(y0 != y1); 3758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fX = (SkRegion::RunType)(x); 3778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fY0 = (SkRegion::RunType)(y0); 3788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fY1 = (SkRegion::RunType)(y1); 3798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com fFlags = 0; 3808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkDEBUGCODE(fNext = NULL;) 3818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 382fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 3838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int top() const { 3848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return SkFastMin32(fY0, fY1); 3858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 3878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic void find_link(Edge* base, Edge* stop) { 3898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(base < stop); 3908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (base->fFlags == Edge::kCompleteLink) { 3928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(base->fNext); 3938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return; 3948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 3958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(base + 1 < stop); 3978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 3988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int y0 = base->fY0; 3998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int y1 = base->fY1; 4008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* e = base; 4028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((base->fFlags & Edge::kY0Link) == 0) { 4038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (;;) { 4048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e += 1; 4058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) { 4068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(NULL == e->fNext); 4078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e->fNext = base; 4088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e->fFlags = SkToU8(e->fFlags | Edge::kY1Link); 4098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 4108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 413fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 4148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e = base; 4158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((base->fFlags & Edge::kY1Link) == 0) { 4168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (;;) { 4178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e += 1; 4188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) { 4198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(NULL == base->fNext); 4208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base->fNext = e; 4218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com e->fFlags = SkToU8(e->fFlags | Edge::kY0Link); 4228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com break; 4238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 426fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 4278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com base->fFlags = Edge::kCompleteLink; 4288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic int extract_path(Edge* edge, Edge* stop, SkPath* path) { 4318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com while (0 == edge->fFlags) { 4328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge++; // skip over "used" edges 4338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(edge < stop); 4368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* base = edge; 4388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* prev = edge; 4398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge = edge->fNext; 4408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(edge != base); 4418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = 1; 4438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0)); 4448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com prev->fFlags = 0; 4458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 4468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear 4478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V 4488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H 4498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com prev = edge; 4518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge = edge->fNext; 4528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com count += 1; 4538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com prev->fFlags = 0; 4548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } while (edge != base); 4558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V 4568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->close(); 4578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return count; 4588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkTSearch.h" 4618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic int EdgeProc(const Edge* a, const Edge* b) { 4638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX; 4648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 4658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.combool SkRegion::getBoundaryPath(SkPath* path) const { 467d5d9dadcdd5fdbc8a17f3f398e3199b9d12c8d70tomhudson@google.com // path could safely be NULL if we're empty, but the caller shouldn't 468d5d9dadcdd5fdbc8a17f3f398e3199b9d12c8d70tomhudson@google.com // *know* that 469d5d9dadcdd5fdbc8a17f3f398e3199b9d12c8d70tomhudson@google.com SkASSERT(path); 470d5d9dadcdd5fdbc8a17f3f398e3199b9d12c8d70tomhudson@google.com 4718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (this->isEmpty()) { 4728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return false; 4738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com const SkIRect& bounds = this->getBounds(); 4768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (this->isRect()) { 478fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com SkRect r; 4798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com r.set(bounds); // this converts the ints to scalars 4808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->addRect(r); 4818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 4828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 4838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkRegion::Iterator iter(*this); 4858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkTDArray<Edge> edges; 486fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 4878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) { 4888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* edge = edges.append(2); 4898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge[0].set(r.fLeft, r.fBottom, r.fTop); 4908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com edge[1].set(r.fRight, r.fTop, r.fBottom); 4918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 492c7a67cb57e43f8e140c7bd21318b5ad3e2db6b2freed@google.com qsort(edges.begin(), edges.count(), sizeof(Edge), SkCastForQSort(EdgeProc)); 493fbfcd5602128ec010c82cb733c9cdc0a3254f9f3rmistry@google.com 4948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int count = edges.count(); 4958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* start = edges.begin(); 4968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* stop = start + count; 4978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Edge* e; 4988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 4998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (e = start; e != stop; e++) { 5008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com find_link(e, stop); 5018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifdef SK_DEBUG 5048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for (e = start; e != stop; e++) { 5058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(e->fNext != NULL); 5068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(e->fFlags == Edge::kCompleteLink); 5078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 5088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 5098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com path->incReserve(count << 1); 5118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com do { 5128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(count > 1); 5138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com count -= extract_path(start, stop, path); 5148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } while (count > 0); 5158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 5168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return true; 5178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 518