blob: 3942eb2db3201026b27d7f28f8fe0a5c8dc84f04 [file] [log] [blame]
/* 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 = SkToS16((int)(fCurrXPtr - fCurrScanline->firstX()));
if (!this->collapsWithPrev()) // flush the last line
fCurrScanline = fCurrScanline->nextScanline();
}
}
int computeRunCount() const;
void copyToRect(SkRect16*) const;
void copyToRgn(S16 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 {
S16 fLastY;
S16 fXCount;
S16* firstX() const { return (S16*)(this + 1); }
Scanline* nextScanline() const { return (Scanline*)((S16*)(this + 1) + fXCount); }
};
S16* fStorage;
Scanline* fCurrScanline;
Scanline* fPrevScanline;
S16* fCurrXPtr; // points at next avialable x[] in fCurrScanline
S16 fTop; // first Y value
bool collapsWithPrev()
{
if (fPrevScanline != nil &&
fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
fPrevScanline->fXCount == fCurrScanline->fXCount &&
!memcmp(fPrevScanline->firstX(),
fCurrScanline->firstX(),
fCurrScanline->fXCount * sizeof(S16)))
{
// 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
fStorage = (S16*)sk_malloc_throw((count + 3 + maxTransitions) * sizeof(S16));
fCurrScanline = nil; // signal empty collection
fPrevScanline = nil; // signal first scanline
}
void SkRgnBuilder::blitH(int x, int y, int width)
{
if (fCurrScanline == nil) // first time
{
fTop = SkToS16(y);
fCurrScanline = (Scanline*)fStorage;
fCurrScanline->fLastY = SkToS16(y);
fCurrXPtr = fCurrScanline->firstX();
}
else
{
SkASSERT(y >= fCurrScanline->fLastY);
if (y > fCurrScanline->fLastY)
{
// if we get here, we're done with fCurrScanline
fCurrScanline->fXCount = SkToS16((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 = SkToS16(y - 1);
fCurrScanline->fXCount = 0;
fCurrScanline = fCurrScanline->nextScanline();
}
// setup for the new curr line
fCurrScanline->fLastY = SkToS16(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] = SkToS16(x + width);
else
{
fCurrXPtr[0] = SkToS16(x);
fCurrXPtr[1] = SkToS16(x + width);
fCurrXPtr += 2;
}
}
int SkRgnBuilder::computeRunCount() const
{
if (fCurrScanline == nil)
return 0;
const S16* line = fStorage;
const S16* stop = (const S16*)fCurrScanline;
return 2 + (int)(stop - line);
}
void SkRgnBuilder::copyToRect(SkRect16* r) const
{
SkASSERT(fCurrScanline != nil);
SkASSERT((const S16*)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(S16 runs[]) const
{
SkASSERT(fCurrScanline != nil);
SkASSERT((const S16*)fCurrScanline - fStorage > 4);
const Scanline* line = (const Scanline*)fStorage;
const Scanline* stop = fCurrScanline;
*runs++ = fTop;
do {
*runs++ = SkToS16(line->fLastY + 1);
int count = line->fXCount;
if (count)
{
memcpy(runs, line->firstX(), count * sizeof(S16));
runs += count;
}
*runs++ = kRunTypeSentinel;
line = line->nextScanline();
} while (line < stop);
SkASSERT(line == stop);
*runs = kRunTypeSentinel;
}
static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot)
{
static const U8 gPathVerbToInitialPointCount[] = {
0, // kMove_Verb
1, // kLine_Verb
2, // kQuad_Verb
3, // kCubic_Verb
0, // kClose_Verb
0 // kDone_Verb
};
static const U8 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)
{
int ptCount = gPathVerbToInitialPointCount[verb];
if (ptCount)
{
maxEdges += gPathVerbToMaxEdges[verb];
for (int i = ptCount - 1; i >= 0; --i)
{
if (top > pts[i].fY)
top = pts[i].fY;
else if (bot < pts[i].fY)
bot = pts[i].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 (path.isEmpty() || clip && clip->isEmpty())
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 = 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->runs());
compute_run_bounds(tmp.fRunHead->runs(), count, &tmp.fBounds);
this->swap(tmp);
}
SkDEBUGCODE(this->validate();)
return true;
}
/////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////
struct SkPrivPoint {
int fX, fY;
friend int operator==(const SkPrivPoint& a, const SkPrivPoint& b)
{
return a.fX == b.fX && a.fY == b.fY;
}
friend int operator!=(const SkPrivPoint& a, const SkPrivPoint& b)
{
return a.fX != b.fX || a.fY != b.fY;
}
};
struct SkPrivLine {
SkPrivPoint fP0, fP1;
int fWinding;
SkPrivLine* fNext, *fPrev;
void set(int x, int y0, int y1)
{
fP0.fX = x;
fP0.fY = y0;
fP1.fX = x;
fP1.fY = y1;
fWinding = y1 > y0; // 1: up, 0: down
fNext = fPrev = nil;
}
void detach()
{
fNext->fPrev = fPrev;
fPrev->fNext = fNext;
}
void attachNext(SkPrivLine* next)
{
next->fNext = fNext;
next->fPrev = this;
fNext->fPrev = next;
fNext = next;
}
};
static SkPrivLine* find_match(SkPrivLine* ctr, SkPrivLine* skip)
{
const SkPrivPoint pt = skip->fP1;
int winding = skip->fWinding;
SkPrivLine* start = ctr;
SkPrivLine* closest_pos = nil;
int dist_pos = 0x7FFFFFFF;
SkPrivLine* closest_neg = nil;
int dist_neg = -0x7FFFFFFF;
do {
// find a Line one the same scan as pt
if (ctr != skip && (ctr->fP0.fY == pt.fY || ctr->fP1.fY == pt.fY))
{
int dist = ctr->fP0.fX - pt.fX; // keep the sign
if (dist == 0)
{
if (winding == ctr->fWinding) // quick accept
goto FOUND;
else
goto NEXT; // quick reject
}
if (dist < 0)
{
if (dist > dist_neg)
{
dist_neg = dist;
closest_neg = ctr;
}
}
else
{
if (dist < dist_pos)
{
dist_pos = dist;
closest_pos = ctr;
}
}
}
NEXT:
ctr = ctr->fNext;
} while (ctr != start);
SkASSERT(closest_pos != nil || closest_neg != nil);
if (closest_pos == nil)
ctr = closest_neg;
else if (closest_neg == nil)
ctr = closest_pos;
else
{
if (closest_neg->fP0.fY != pt.fY)
ctr = closest_pos;
else if (closest_pos->fP0.fY != pt.fY)
ctr = closest_neg;
else
{
if (closest_pos->fWinding != closest_neg->fWinding)
{
if (closest_pos->fWinding == winding)
ctr = closest_pos;
else
ctr = closest_neg;
}
else
{
if (winding == 0)
ctr = closest_pos;
else
ctr = closest_neg;
}
}
}
FOUND:
SkASSERT(ctr && ctr->fP0.fY == pt.fY);
return ctr;
}
static void LinesToPath(SkPrivLine lines[], int count, SkPath* path)
{
SkASSERT(count > 1);
// turn the array into a linked list
lines[0].fNext = &lines[1];
lines[0].fPrev = &lines[count - 1];
for (int i = 1; i < count - 1; i++)
{
lines[i].fNext = &lines[i+1];
lines[i].fPrev = &lines[i-1];
}
lines[count - 1].fNext = &lines[0];
lines[count - 1].fPrev = &lines[count - 2];
SkPrivLine* head = lines;
// loop through looking for contours
while (count > 0)
{
SkPrivLine* ctr = head;
SkPrivLine* first = ctr;
head = head->fNext;
path->moveTo(SkIntToScalar(ctr->fP0.fX), SkIntToScalar(ctr->fP0.fY));
do {
SkPrivLine* next = find_match(head, ctr);
if (ctr->fP1 != next->fP0)
{
path->lineTo(SkIntToScalar(ctr->fP1.fX), SkIntToScalar(ctr->fP1.fY)); // Vertical
path->lineTo(SkIntToScalar(next->fP0.fX), SkIntToScalar(next->fP0.fY)); // Horzontal
}
if (head == next)
head = head->fNext;
next->detach();
count -= 1;
ctr = next;
} while (ctr != first);
path->close();
ctr->detach();
count -= 1;
}
// SkASSERT(count == 0);
}
bool SkRegion::getBoundaryPath(SkPath* path) const
{
if (this->isEmpty())
return false;
const SkRect16& 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<SkPrivLine> lines;
for (const SkRect16& r = iter.rect(); !iter.done(); iter.next())
{
SkPrivLine* line = lines.append(2);
line[0].set(r.fLeft, r.fBottom, r.fTop);
line[1].set(r.fRight, r.fTop, r.fBottom);
}
LinesToPath(lines.begin(), lines.count(), path);
return true;
}