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.cpp457
1 files changed, 457 insertions, 0 deletions
diff --git a/skia/sgl/SkRegion_path.cpp b/skia/sgl/SkRegion_path.cpp
new file mode 100644
index 0000000..11e19b9
--- /dev/null
+++ b/skia/sgl/SkRegion_path.cpp
@@ -0,0 +1,457 @@
+/* libs/graphics/sgl/SkRegion_path.cpp
+**
+** Copyright 2006, Google Inc.
+**
+** 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();
+
+ void 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);
+}
+
+void SkRgnBuilder::init(int maxHeight, int maxTransitions) {
+ int count = maxHeight * (3 + maxTransitions);
+
+ // add maxTransitions to have slop for working buffer
+ fStorageCount = count + 3 + maxTransitions;
+ fStorage = (SkRegion::RunType*)sk_malloc_throw(fStorageCount * sizeof(SkRegion::RunType));
+
+ fCurrScanline = NULL; // signal empty collection
+ fPrevScanline = NULL; // signal first scanline
+}
+
+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;
+
+ builder.init(bot - top, SkMax32(pathTransitions, clipTransitions));
+ 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-03-12 13:55:34 +0000