180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2006 The Android Open Source Project 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkRegionPriv.h" 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkBlitter.h" 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkScan.h" 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkTDArray.h" 1480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkPath.h" 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruclass SkRgnBuilder : public SkBlitter { 1780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querupublic: 1880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru virtual ~SkRgnBuilder(); 1980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // returns true if it could allocate the working storage needed 2180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool init(int maxHeight, int maxTransitions); 2280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void done() { 2480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (fCurrScanline != NULL) { 2580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX())); 2680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (!this->collapsWithPrev()) { // flush the last line 2780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline = fCurrScanline->nextScanline(); 2880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 2980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 3080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 3180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int computeRunCount() const; 3380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void copyToRect(SkIRect*) const; 3480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void copyToRgn(SkRegion::RunType runs[]) const; 3580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru virtual void blitH(int x, int y, int width); 3780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_DEBUG 3980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void dump() const { 4080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDebugf("SkRgnBuilder: Top = %d\n", fTop); 4180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const Scanline* line = (Scanline*)fStorage; 4280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (line < fCurrScanline) { 4380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount); 4480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 0; i < line->fXCount; i++) { 4580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDebugf(" %d", line->firstX()[i]); 4680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 4780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDebugf("\n"); 4880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 4980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru line = line->nextScanline(); 5080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 5280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 5380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruprivate: 5480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru /* 5580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Scanline mimics a row in the region, nearly. A row in a region is: 5680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * [Bottom IntervalCount [L R]... Sentinel] 5780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * while a Scanline is 5880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * [LastY XCount [L R]... uninitialized] 5980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * The two are the same length (which is good), but we have to transmute 6080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * the scanline a little when we convert it to a region-row. 6180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 6280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Potentially we could recode this to exactly match the row format, in 6380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * which case copyToRgn() could be a single memcpy. Not sure that is worth 6480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * the effort. 6580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 6680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru struct Scanline { 6780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRegion::RunType fLastY; 6880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRegion::RunType fXCount; 6980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 7080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); } 7180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Scanline* nextScanline() const { 7280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // add final +1 for the x-sentinel 7380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1); 7480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 7580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 7680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRegion::RunType* fStorage; 7780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Scanline* fCurrScanline; 7880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Scanline* fPrevScanline; 7980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // points at next avialable x[] in fCurrScanline 8080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRegion::RunType* fCurrXPtr; 8180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRegion::RunType fTop; // first Y value 8280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int fStorageCount; 8480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 8580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bool collapsWithPrev() { 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (fPrevScanline != NULL && 8780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fPrevScanline->fLastY + 1 == fCurrScanline->fLastY && 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fPrevScanline->fXCount == fCurrScanline->fXCount && 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru !memcmp(fPrevScanline->firstX(), 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline->firstX(), 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline->fXCount * sizeof(SkRegion::RunType))) 9280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru { 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // update the height of fPrevScanline 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fPrevScanline->fLastY = fCurrScanline->fLastY; 9580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 9680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 9880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 10080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste QueruSkRgnBuilder::~SkRgnBuilder() { 10280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru sk_free(fStorage); 10380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 10480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querubool SkRgnBuilder::init(int maxHeight, int maxTransitions) { 10680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if ((maxHeight | maxTransitions) < 0) { 10780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 10980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Sk64 count, size; 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // compute the count with +1 and +3 slop for the working buffer 11380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru count.setMul(maxHeight + 1, 3 + maxTransitions); 11480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (!count.is32() || count.isNeg()) { 11580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 11680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 11780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fStorageCount = count.get32(); 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru size.setMul(fStorageCount, sizeof(SkRegion::RunType)); 12080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (!size.is32() || size.isNeg()) { 12180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 12280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fStorage = (SkRegion::RunType*)sk_malloc_flags(size.get32(), 0); 12580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (NULL == fStorage) { 12680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 12780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 12980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline = NULL; // signal empty collection 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fPrevScanline = NULL; // signal first scanline 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 13280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 13380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkRgnBuilder::blitH(int x, int y, int width) { 13580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (fCurrScanline == NULL) { // first time 13680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fTop = (SkRegion::RunType)(y); 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline = (Scanline*)fStorage; 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline->fLastY = (SkRegion::RunType)(y); 13980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrXPtr = fCurrScanline->firstX(); 14080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 14180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(y >= fCurrScanline->fLastY); 14280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 14380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (y > fCurrScanline->fLastY) { 14480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // if we get here, we're done with fCurrScanline 14580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX())); 14680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 14780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int prevLastY = fCurrScanline->fLastY; 14880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (!this->collapsWithPrev()) { 14980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fPrevScanline = fCurrScanline; 15080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline = fCurrScanline->nextScanline(); 15180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 15280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 15380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (y - 1 > prevLastY) { // insert empty run 15480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline->fLastY = (SkRegion::RunType)(y - 1); 15580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline->fXCount = 0; 15680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline = fCurrScanline->nextScanline(); 15780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 15880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // setup for the new curr line 15980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrScanline->fLastY = (SkRegion::RunType)(y); 16080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrXPtr = fCurrScanline->firstX(); 16180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 16280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 16380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // check if we should extend the current run, or add a new one 16480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) { 16580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrXPtr[-1] = (SkRegion::RunType)(x + width); 16680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 16780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrXPtr[0] = (SkRegion::RunType)(x); 16880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrXPtr[1] = (SkRegion::RunType)(x + width); 16980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fCurrXPtr += 2; 17080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 17180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fCurrXPtr - fStorage < fStorageCount); 17280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 17380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 17480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruint SkRgnBuilder::computeRunCount() const { 17580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (fCurrScanline == NULL) { 17680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 0; 17780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 17880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 17980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const SkRegion::RunType* line = fStorage; 18080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline; 18180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 18280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return 2 + (int)(stop - line); 18380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 18480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 18580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkRgnBuilder::copyToRect(SkIRect* r) const { 18680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fCurrScanline != NULL); 18780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // A rect's scanline is [bottom intervals left right sentinel] == 5 18880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5); 18980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 19080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const Scanline* line = (const Scanline*)fStorage; 19180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(line->fXCount == 2); 19280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 19380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1); 19480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 19580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 19680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queruvoid SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const { 19780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(fCurrScanline != NULL); 19880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4); 19980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 20080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const Scanline* line = (const Scanline*)fStorage; 20180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const Scanline* stop = fCurrScanline; 20280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 20380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *runs++ = fTop; 20480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru do { 20580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *runs++ = (SkRegion::RunType)(line->fLastY + 1); 20680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = line->fXCount; 20780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *runs++ = count >> 1; // intervalCount 20880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (count) { 20980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType)); 21080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru runs += count; 21180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 21280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *runs++ = SkRegion::kRunTypeSentinel; 21380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru line = line->nextScanline(); 21480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } while (line < stop); 21580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(line == stop); 21680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *runs = SkRegion::kRunTypeSentinel; 21780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 21880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 21980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) { 22080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static const uint8_t gPathVerbToInitialLastIndex[] = { 22180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 0, // kMove_Verb 22280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1, // kLine_Verb 22380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2, // kQuad_Verb 22480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3, // kCubic_Verb 22580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 0, // kClose_Verb 22680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 0 // kDone_Verb 22780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 22880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 22980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru static const uint8_t gPathVerbToMaxEdges[] = { 23080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 0, // kMove_Verb 23180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1, // kLine_Verb 23280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 2, // kQuad_VerbB 23380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 3, // kCubic_Verb 23480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 0, // kClose_Verb 23580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 0 // kDone_Verb 23680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 23780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 23880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPath::Iter iter(path, true); 23980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPoint pts[4]; 24080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkPath::Verb verb; 24180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 24280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int maxEdges = 0; 24380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar top = SkIntToScalar(SK_MaxS16); 24480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScalar bot = SkIntToScalar(SK_MinS16); 24580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 24680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 24780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru maxEdges += gPathVerbToMaxEdges[verb]; 24880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 24980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int lastIndex = gPathVerbToInitialLastIndex[verb]; 25080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (lastIndex > 0) { 25180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (int i = 1; i <= lastIndex; i++) { 25280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (top > pts[i].fY) { 25380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru top = pts[i].fY; 25480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else if (bot < pts[i].fY) { 25580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bot = pts[i].fY; 25680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 25780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 25880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else if (SkPath::kMove_Verb == verb) { 25980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (top > pts[0].fY) { 26080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru top = pts[0].fY; 26180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else if (bot < pts[0].fY) { 26280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru bot = pts[0].fY; 26380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 26480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 26580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 26680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(top <= bot); 26780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 26880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *itop = SkScalarRound(top); 26980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru *ibot = SkScalarRound(bot); 27080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return maxEdges; 27180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 27280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 27380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querubool SkRegion::setPath(const SkPath& path, const SkRegion& clip) { 27480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDEBUGCODE(this->validate();) 27580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 27680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (clip.isEmpty()) { 27780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return this->setEmpty(); 27880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 27980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 28080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (path.isEmpty()) { 28180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (path.isInverseFillType()) { 28280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return this->set(clip); 28380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 28480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return this->setEmpty(); 28580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 28680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 28780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 28880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // compute worst-case rgn-size for the path 28980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int pathTop, pathBot; 29080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot); 29180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int clipTop, clipBot; 29280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int clipTransitions; 29380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 29480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru clipTransitions = clip.count_runtype_values(&clipTop, &clipBot); 29580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 29680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int top = SkMax32(pathTop, clipTop); 29780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int bot = SkMin32(pathBot, clipBot); 29880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 29980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (top >= bot) 30080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return this->setEmpty(); 30180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 30280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRgnBuilder builder; 30380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 30480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (!builder.init(bot - top, SkMax32(pathTransitions, clipTransitions))) { 30580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // can't allocate working space, so return false 30680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return this->setEmpty(); 30780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 30880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 30980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkScan::FillPath(path, clip, &builder); 31080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru builder.done(); 31180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 31280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = builder.computeRunCount(); 31380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (count == 0) { 31480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return this->setEmpty(); 31580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else if (count == kRectRegionRuns) { 31680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru builder.copyToRect(&fBounds); 31780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->setRect(fBounds); 31880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 31980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRegion tmp; 32080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 32180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp.fRunHead = RunHead::Alloc(count); 32280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru builder.copyToRgn(tmp.fRunHead->writable_runs()); 32380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru tmp.fRunHead->computeRunBounds(&tmp.fBounds); 32480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru this->swap(tmp); 32580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 32680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDEBUGCODE(this->validate();) 32780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 32880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 32980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 33080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru///////////////////////////////////////////////////////////////////////////////////////////////// 33180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru///////////////////////////////////////////////////////////////////////////////////////////////// 33280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 33380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustruct Edge { 33480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru enum { 33580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru kY0Link = 0x01, 33680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru kY1Link = 0x02, 33780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 33880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru kCompleteLink = (kY0Link | kY1Link) 33980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru }; 34080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 34180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRegion::RunType fX; 34280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRegion::RunType fY0, fY1; 34380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru uint8_t fFlags; 34480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Edge* fNext; 34580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 34680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru void set(int x, int y0, int y1) { 34780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(y0 != y1); 34880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 34980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fX = (SkRegion::RunType)(x); 35080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fY0 = (SkRegion::RunType)(y0); 35180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fY1 = (SkRegion::RunType)(y1); 35280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru fFlags = 0; 35380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkDEBUGCODE(fNext = NULL;) 35480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 35580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 35680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int top() const { 35780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return SkFastMin32(fY0, fY1); 35880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 35980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru}; 36080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 36180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic void find_link(Edge* base, Edge* stop) { 36280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(base < stop); 36380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 36480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (base->fFlags == Edge::kCompleteLink) { 36580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(base->fNext); 36680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 36780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 36880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 36980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(base + 1 < stop); 37080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 37180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int y0 = base->fY0; 37280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int y1 = base->fY1; 37380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 37480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Edge* e = base; 37580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if ((base->fFlags & Edge::kY0Link) == 0) { 37680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (;;) { 37780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru e += 1; 37880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) { 37980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(NULL == e->fNext); 38080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru e->fNext = base; 38180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru e->fFlags = SkToU8(e->fFlags | Edge::kY1Link); 38280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru break; 38380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 38480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 38580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 38680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 38780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru e = base; 38880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if ((base->fFlags & Edge::kY1Link) == 0) { 38980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (;;) { 39080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru e += 1; 39180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) { 39280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(NULL == base->fNext); 39380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru base->fNext = e; 39480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru e->fFlags = SkToU8(e->fFlags | Edge::kY0Link); 39580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru break; 39680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 39780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 39880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 39980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 40080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru base->fFlags = Edge::kCompleteLink; 40180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 40280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 40380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic int extract_path(Edge* edge, Edge* stop, SkPath* path) { 40480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (0 == edge->fFlags) { 40580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru edge++; // skip over "used" edges 40680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 40780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 40880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(edge < stop); 40980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 41080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Edge* base = edge; 41180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Edge* prev = edge; 41280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru edge = edge->fNext; 41380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(edge != base); 41480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 41580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = 1; 41680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0)); 41780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru prev->fFlags = 0; 41880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru do { 41980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear 42080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V 42180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H 42280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 42380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru prev = edge; 42480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru edge = edge->fNext; 42580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru count += 1; 42680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru prev->fFlags = 0; 42780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } while (edge != base); 42880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V 42980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path->close(); 43080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return count; 43180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 43280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 43380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkTSearch.h" 43480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 43580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querustatic int EdgeProc(const Edge* a, const Edge* b) { 43680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX; 43780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 43880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 43980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Querubool SkRegion::getBoundaryPath(SkPath* path) const { 44080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // path could safely be NULL if we're empty, but the caller shouldn't 44180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru // *know* that 44280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(path); 44380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 44480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (this->isEmpty()) { 44580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return false; 44680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 44780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 44880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru const SkIRect& bounds = this->getBounds(); 44980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 45080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (this->isRect()) { 45180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRect r; 45280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru r.set(bounds); // this converts the ints to scalars 45380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path->addRect(r); 45480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 45580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 45680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 45780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkRegion::Iterator iter(*this); 45880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTDArray<Edge> edges; 45980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 46080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) { 46180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Edge* edge = edges.append(2); 46280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru edge[0].set(r.fLeft, r.fBottom, r.fTop); 46380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru edge[1].set(r.fRight, r.fTop, r.fBottom); 46480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 46580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru qsort(edges.begin(), edges.count(), sizeof(Edge), SkCastForQSort(EdgeProc)); 46680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 46780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru int count = edges.count(); 46880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Edge* start = edges.begin(); 46980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Edge* stop = start + count; 47080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru Edge* e; 47180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 47280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (e = start; e != stop; e++) { 47380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru find_link(e, stop); 47480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 47580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 47680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifdef SK_DEBUG 47780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru for (e = start; e != stop; e++) { 47880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(e->fNext != NULL); 47980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(e->fFlags == Edge::kCompleteLink); 48080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 48180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 48280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 48380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru path->incReserve(count << 1); 48480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru do { 48580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkASSERT(count > 1); 48680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru count -= extract_path(start, stop, path); 48780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } while (count > 0); 48880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 48980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return true; 49080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 491