summaryrefslogtreecommitdiffstats
path: root/skia/sgl/SkRegion_path.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'skia/sgl/SkRegion_path.cpp')
-rw-r--r--skia/sgl/SkRegion_path.cpp480
1 files changed, 0 insertions, 480 deletions
diff --git a/skia/sgl/SkRegion_path.cpp b/skia/sgl/SkRegion_path.cpp
deleted file mode 100644
index d00baf9..0000000
--- a/skia/sgl/SkRegion_path.cpp
+++ /dev/null
@@ -1,480 +0,0 @@
-/* libs/graphics/sgl/SkRegion_path.cpp
-**
-** Copyright 2006, The Android Open Source Project
-**
-** Licensed under the Apache License, Version 2.0 (the "License");
-** you may not use this file except in compliance with the License.
-** You may obtain a copy of the License at
-**
-** http://www.apache.org/licenses/LICENSE-2.0
-**
-** Unless required by applicable law or agreed to in writing, software
-** distributed under the License is distributed on an "AS IS" BASIS,
-** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-** See the License for the specific language governing permissions and
-** limitations under the License.
-*/
-
-#include "SkRegionPriv.h"
-#include "SkBlitter.h"
-#include "SkScan.h"
-#include "SkTDArray.h"
-#include "SkPath.h"
-
-class SkRgnBuilder : public SkBlitter {
-public:
- virtual ~SkRgnBuilder();
-
- // returns true if it could allocate the working storage needed
- bool init(int maxHeight, int maxTransitions);
-
- void done() {
- if (fCurrScanline != NULL) {
- fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
- if (!this->collapsWithPrev()) { // flush the last line
- fCurrScanline = fCurrScanline->nextScanline();
- }
- }
- }
-
- int computeRunCount() const;
- void copyToRect(SkIRect*) const;
- void copyToRgn(SkRegion::RunType runs[]) const;
-
- virtual void blitH(int x, int y, int width);
-
-#ifdef SK_DEBUG
- void dump() const {
- SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
- const Scanline* line = (Scanline*)fStorage;
- while (line < fCurrScanline) {
- SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
- for (int i = 0; i < line->fXCount; i++) {
- SkDebugf(" %d", line->firstX()[i]);
- }
- SkDebugf("\n");
-
- line = line->nextScanline();
- }
- }
-#endif
-private:
- struct Scanline {
- SkRegion::RunType fLastY;
- SkRegion::RunType fXCount;
-
- SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
- Scanline* nextScanline() const {
- return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount);
- }
- };
- SkRegion::RunType* fStorage;
- Scanline* fCurrScanline;
- Scanline* fPrevScanline;
- // points at next avialable x[] in fCurrScanline
- SkRegion::RunType* fCurrXPtr;
- SkRegion::RunType fTop; // first Y value
-
- int fStorageCount;
-
- bool collapsWithPrev() {
- if (fPrevScanline != NULL &&
- fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
- fPrevScanline->fXCount == fCurrScanline->fXCount &&
- !memcmp(fPrevScanline->firstX(),
- fCurrScanline->firstX(),
- fCurrScanline->fXCount * sizeof(SkRegion::RunType)))
- {
- // update the height of fPrevScanline
- fPrevScanline->fLastY = fCurrScanline->fLastY;
- return true;
- }
- return false;
- }
-};
-
-SkRgnBuilder::~SkRgnBuilder() {
- sk_free(fStorage);
-}
-
-bool SkRgnBuilder::init(int maxHeight, int maxTransitions) {
- if ((maxHeight | maxTransitions) < 0) {
- return false;
- }
-
- Sk64 count, size;
-
- // compute the count with +1 and +3 slop for the working buffer
- count.setMul(maxHeight + 1, 3 + maxTransitions);
- if (!count.is32() || count.isNeg()) {
- return false;
- }
- fStorageCount = count.get32();
-
- size.setMul(fStorageCount, sizeof(SkRegion::RunType));
- if (!size.is32() || size.isNeg()) {
- return false;
- }
-
- fStorage = (SkRegion::RunType*)sk_malloc_flags(size.get32(), 0);
- if (NULL == fStorage) {
- return false;
- }
-
- fCurrScanline = NULL; // signal empty collection
- fPrevScanline = NULL; // signal first scanline
- return true;
-}
-
-void SkRgnBuilder::blitH(int x, int y, int width) {
- if (fCurrScanline == NULL) { // first time
- fTop = (SkRegion::RunType)(y);
- fCurrScanline = (Scanline*)fStorage;
- fCurrScanline->fLastY = (SkRegion::RunType)(y);
- fCurrXPtr = fCurrScanline->firstX();
- } else {
- SkASSERT(y >= fCurrScanline->fLastY);
-
- if (y > fCurrScanline->fLastY) {
- // if we get here, we're done with fCurrScanline
- fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
-
- int prevLastY = fCurrScanline->fLastY;
- if (!this->collapsWithPrev()) {
- fPrevScanline = fCurrScanline;
- fCurrScanline = fCurrScanline->nextScanline();
-
- }
- if (y - 1 > prevLastY) { // insert empty run
- fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
- fCurrScanline->fXCount = 0;
- fCurrScanline = fCurrScanline->nextScanline();
- }
- // setup for the new curr line
- fCurrScanline->fLastY = (SkRegion::RunType)(y);
- fCurrXPtr = fCurrScanline->firstX();
- }
- }
- // check if we should extend the current run, or add a new one
- if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
- fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
- } else {
- fCurrXPtr[0] = (SkRegion::RunType)(x);
- fCurrXPtr[1] = (SkRegion::RunType)(x + width);
- fCurrXPtr += 2;
- }
- SkASSERT(fCurrXPtr - fStorage < fStorageCount);
-}
-
-int SkRgnBuilder::computeRunCount() const {
- if (fCurrScanline == NULL) {
- return 0;
- }
-
- const SkRegion::RunType* line = fStorage;
- const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline;
-
- return 2 + (int)(stop - line);
-}
-
-void SkRgnBuilder::copyToRect(SkIRect* r) const {
- SkASSERT(fCurrScanline != NULL);
- SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 4);
-
- const Scanline* line = (const Scanline*)fStorage;
- SkASSERT(line->fXCount == 2);
-
- r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
-}
-
-void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
- SkASSERT(fCurrScanline != NULL);
- SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);
-
- const Scanline* line = (const Scanline*)fStorage;
- const Scanline* stop = fCurrScanline;
-
- *runs++ = fTop;
- do {
- *runs++ = (SkRegion::RunType)(line->fLastY + 1);
- int count = line->fXCount;
- if (count) {
- memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
- runs += count;
- }
- *runs++ = SkRegion::kRunTypeSentinel;
- line = line->nextScanline();
- } while (line < stop);
- SkASSERT(line == stop);
- *runs = SkRegion::kRunTypeSentinel;
-}
-
-static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
- static const uint8_t gPathVerbToInitialLastIndex[] = {
- 0, // kMove_Verb
- 1, // kLine_Verb
- 2, // kQuad_Verb
- 3, // kCubic_Verb
- 0, // kClose_Verb
- 0 // kDone_Verb
- };
-
- static const uint8_t gPathVerbToMaxEdges[] = {
- 0, // kMove_Verb
- 1, // kLine_Verb
- 2, // kQuad_VerbB
- 3, // kCubic_Verb
- 0, // kClose_Verb
- 0 // kDone_Verb
- };
-
- SkPath::Iter iter(path, true);
- SkPoint pts[4];
- SkPath::Verb verb;
-
- int maxEdges = 0;
- SkScalar top = SkIntToScalar(SK_MaxS16);
- SkScalar bot = SkIntToScalar(SK_MinS16);
-
- while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
- maxEdges += gPathVerbToMaxEdges[verb];
-
- int lastIndex = gPathVerbToInitialLastIndex[verb];
- if (lastIndex > 0) {
- for (int i = 1; i <= lastIndex; i++) {
- if (top > pts[i].fY) {
- top = pts[i].fY;
- } else if (bot < pts[i].fY) {
- bot = pts[i].fY;
- }
- }
- } else if (SkPath::kMove_Verb == verb) {
- if (top > pts[0].fY) {
- top = pts[0].fY;
- } else if (bot < pts[0].fY) {
- bot = pts[0].fY;
- }
- }
- }
- SkASSERT(top <= bot);
-
- *itop = SkScalarRound(top);
- *ibot = SkScalarRound(bot);
- return maxEdges;
-}
-
-bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
- SkDEBUGCODE(this->validate();)
-
- if (clip.isEmpty()) {
- return this->setEmpty();
- }
-
- if (path.isEmpty()) {
- if (path.isInverseFillType()) {
- return this->set(clip);
- } else {
- return this->setEmpty();
- }
- }
-
- // compute worst-case rgn-size for the path
- int pathTop, pathBot;
- int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
- int clipTop, clipBot;
- int clipTransitions;
-
- clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);
-
- int top = SkMax32(pathTop, clipTop);
- int bot = SkMin32(pathBot, clipBot);
-
- if (top >= bot)
- return this->setEmpty();
-
- SkRgnBuilder builder;
-
- if (!builder.init(bot - top, SkMax32(pathTransitions, clipTransitions))) {
- // can't allocate working space, so return false
- return this->setEmpty();
- }
-
- SkScan::FillPath(path, clip, &builder);
- builder.done();
-
- int count = builder.computeRunCount();
- if (count == 0) {
- return this->setEmpty();
- } else if (count == kRectRegionRuns) {
- builder.copyToRect(&fBounds);
- this->setRect(fBounds);
- } else {
- SkRegion tmp;
-
- tmp.fRunHead = RunHead::Alloc(count);
- builder.copyToRgn(tmp.fRunHead->writable_runs());
- ComputeRunBounds(tmp.fRunHead->readonly_runs(), count, &tmp.fBounds);
- this->swap(tmp);
- }
- SkDEBUGCODE(this->validate();)
- return true;
-}
-
-/////////////////////////////////////////////////////////////////////////////////////////////////
-/////////////////////////////////////////////////////////////////////////////////////////////////
-
-struct Edge {
- enum {
- kY0Link = 0x01,
- kY1Link = 0x02,
-
- kCompleteLink = (kY0Link | kY1Link)
- };
-
- SkRegion::RunType fX;
- SkRegion::RunType fY0, fY1;
- uint8_t fFlags;
- Edge* fNext;
-
- void set(int x, int y0, int y1) {
- SkASSERT(y0 != y1);
-
- fX = (SkRegion::RunType)(x);
- fY0 = (SkRegion::RunType)(y0);
- fY1 = (SkRegion::RunType)(y1);
- fFlags = 0;
- SkDEBUGCODE(fNext = NULL;)
- }
-
- int top() const {
- return SkFastMin32(fY0, fY1);
- }
-};
-
-static void find_link(Edge* base, Edge* stop) {
- SkASSERT(base < stop);
-
- if (base->fFlags == Edge::kCompleteLink) {
- SkASSERT(base->fNext);
- return;
- }
-
- SkASSERT(base + 1 < stop);
-
- int y0 = base->fY0;
- int y1 = base->fY1;
-
- Edge* e = base;
- if ((base->fFlags & Edge::kY0Link) == 0) {
- for (;;) {
- e += 1;
- if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
- SkASSERT(NULL == e->fNext);
- e->fNext = base;
- e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
- break;
- }
- }
- }
-
- e = base;
- if ((base->fFlags & Edge::kY1Link) == 0) {
- for (;;) {
- e += 1;
- if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
- SkASSERT(NULL == base->fNext);
- base->fNext = e;
- e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
- break;
- }
- }
- }
-
- base->fFlags = Edge::kCompleteLink;
-}
-
-static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
- while (0 == edge->fFlags) {
- edge++; // skip over "used" edges
- }
-
- SkASSERT(edge < stop);
-
- Edge* base = edge;
- Edge* prev = edge;
- edge = edge->fNext;
- SkASSERT(edge != base);
-
- int count = 1;
- path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
- prev->fFlags = 0;
- do {
- if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
- path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
- path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H
- }
- prev = edge;
- edge = edge->fNext;
- count += 1;
- prev->fFlags = 0;
- } while (edge != base);
- path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
- path->close();
- return count;
-}
-
-#include "SkTSearch.h"
-
-static int EdgeProc(const Edge* a, const Edge* b) {
- return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
-}
-
-bool SkRegion::getBoundaryPath(SkPath* path) const {
- if (this->isEmpty()) {
- return false;
- }
-
- const SkIRect& bounds = this->getBounds();
-
- if (this->isRect()) {
- SkRect r;
- r.set(bounds); // this converts the ints to scalars
- path->addRect(r);
- return true;
- }
-
- SkRegion::Iterator iter(*this);
- SkTDArray<Edge> edges;
-
- for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
- Edge* edge = edges.append(2);
- edge[0].set(r.fLeft, r.fBottom, r.fTop);
- edge[1].set(r.fRight, r.fTop, r.fBottom);
- }
- SkQSort(edges.begin(), edges.count(), sizeof(Edge), (SkQSortCompareProc)EdgeProc);
-
- int count = edges.count();
- Edge* start = edges.begin();
- Edge* stop = start + count;
- Edge* e;
-
- for (e = start; e != stop; e++) {
- find_link(e, stop);
- }
-
-#ifdef SK_DEBUG
- for (e = start; e != stop; e++) {
- SkASSERT(e->fNext != NULL);
- SkASSERT(e->fFlags == Edge::kCompleteLink);
- }
-#endif
-
- path->incReserve(count << 1);
- do {
- SkASSERT(count > 1);
- count -= extract_path(start, stop, path);
- } while (count > 0);
-
- return true;
-}
-
generated by cgit v1.1 at 2025-01-30 10:26:42 +0000