libs/graphics/sgl/SkRegion_path.cpp - platform/external/skia - Gitiles

 /* 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;
 }
	/* 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;
	}