src/utils/SkCullPoints.cpp - platform/external/skia - Gitiles


 /*
  * Copyright 2006 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */


 #include "SkCullPoints.h"
 #include "Sk64.h"

 static bool cross_product_is_neg(const SkIPoint& v, int dx, int dy) {
 #if 0
     return v.fX * dy - v.fY * dx < 0;
 #else
     Sk64   tmp0, tmp1;

     tmp0.setMul(v.fX, dy);
     tmp1.setMul(dx, v.fY);
     tmp0.sub(tmp1);
     return tmp0.isNeg() != 0;
 #endif
 }

 bool SkCullPoints::sect_test(int x0, int y0, int x1, int y1) const {
     const SkIRect& r = fR;

     if ((x0 < r.fLeft    && x1 < r.fLeft) ||
         (x0 > r.fRight   && x1 > r.fRight) ||
         (y0 < r.fTop     && y1 < r.fTop) ||
         (y0 > r.fBottom  && y1 > r.fBottom)) {
         return false;
     }

     // since the crossprod test is a little expensive, check for easy-in cases first
     if (r.contains(x0, y0) || r.contains(x1, y1)) {
         return true;
     }

     // At this point we're not sure, so we do a crossprod test
     SkIPoint           vec;
     const SkIPoint*    rAsQuad = fAsQuad;

     vec.set(x1 - x0, y1 - y0);
     bool isNeg = cross_product_is_neg(vec, x0 - rAsQuad[0].fX, y0 - rAsQuad[0].fY);
     for (int i = 1; i < 4; i++) {
         if (cross_product_is_neg(vec, x0 - rAsQuad[i].fX, y0 - rAsQuad[i].fY) != isNeg) {
             return true;
         }
     }
     return false;   // we didn't intersect
 }

 static void toQuad(const SkIRect& r, SkIPoint quad[4]) {
     SkASSERT(quad);

     quad[0].set(r.fLeft, r.fTop);
     quad[1].set(r.fRight, r.fTop);
     quad[2].set(r.fRight, r.fBottom);
     quad[3].set(r.fLeft, r.fBottom);
 }

 SkCullPoints::SkCullPoints() {
     SkIRect    r;
     r.setEmpty();
     this->reset(r);
 }

 SkCullPoints::SkCullPoints(const SkIRect& r) {
     this->reset(r);
 }

 void SkCullPoints::reset(const SkIRect& r) {
     fR = r;
     toQuad(fR, fAsQuad);
     fPrevPt.set(0, 0);
     fPrevResult = kNo_Result;
 }

 void SkCullPoints::moveTo(int x, int y) {
     fPrevPt.set(x, y);
     fPrevResult = kNo_Result;   // so we trigger a movetolineto later
 }

 SkCullPoints::LineToResult SkCullPoints::lineTo(int x, int y, SkIPoint line[]) {
     SkASSERT(line != NULL);

     LineToResult result = kNo_Result;
     int x0 = fPrevPt.fX;
     int y0 = fPrevPt.fY;

     // need to upgrade sect_test to chop the result
     // and to correctly return kLineTo_Result when the result is connected
     // to the previous call-out
     if (this->sect_test(x0, y0, x, y)) {
         line[0].set(x0, y0);
         line[1].set(x, y);

         if (fPrevResult != kNo_Result && fPrevPt.equals(x0, y0)) {
             result = kLineTo_Result;
         } else {
             result = kMoveToLineTo_Result;
         }
     }

     fPrevPt.set(x, y);
     fPrevResult = result;

     return result;
 }

 /////////////////////////////////////////////////////////////////////////////////////////////////

 #include "SkPath.h"

 SkCullPointsPath::SkCullPointsPath()
     : fCP(), fPath(NULL) {
 }

 SkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst)
     : fCP(r), fPath(dst) {
 }

 void SkCullPointsPath::reset(const SkIRect& r, SkPath* dst) {
     fCP.reset(r);
     fPath = dst;
 }

 void SkCullPointsPath::moveTo(int x, int y) {
     fCP.moveTo(x, y);
 }

 void SkCullPointsPath::lineTo(int x, int y) {
     SkIPoint   pts[2];

     switch (fCP.lineTo(x, y, pts)) {
     case SkCullPoints::kMoveToLineTo_Result:
         fPath->moveTo(SkIntToScalar(pts[0].fX), SkIntToScalar(pts[0].fY));
         // fall through to the lineto case
     case SkCullPoints::kLineTo_Result:
         fPath->lineTo(SkIntToScalar(pts[1].fX), SkIntToScalar(pts[1].fY));
         break;
     default:
         break;
     }
 }

 ///////////////////////////////////////////////////////////////////////////////

 #include "SkMatrix.h"
 #include "SkRegion.h"

 bool SkHitTestPath(const SkPath& path, SkRect& target, bool hires) {
     if (target.isEmpty()) {
         return false;
     }

     bool isInverse = path.isInverseFillType();
     if (path.isEmpty()) {
         return isInverse;
     }

     SkRect bounds = path.getBounds();

     bool sects = SkRect::Intersects(target, bounds);
     if (isInverse) {
         if (!sects) {
             return true;
         }
     } else {
         if (!sects) {
             return false;
         }
         if (target.contains(bounds)) {
             return true;
         }
     }

     SkPath devPath;
     const SkPath* pathPtr;
     SkRect        devTarget;

     if (hires) {
         const SkScalar coordLimit = SkIntToScalar(16384);
         const SkRect limit = { 0, 0, coordLimit, coordLimit };

         SkMatrix matrix;
         matrix.setRectToRect(bounds, limit, SkMatrix::kFill_ScaleToFit);

         path.transform(matrix, &devPath);
         matrix.mapRect(&devTarget, target);

         pathPtr = &devPath;
     } else {
         devTarget = target;
         pathPtr = &path;
     }

     SkIRect iTarget;
     devTarget.round(&iTarget);
     if (iTarget.isEmpty()) {
         iTarget.fLeft = SkScalarFloorToInt(devTarget.fLeft);
         iTarget.fTop = SkScalarFloorToInt(devTarget.fTop);
         iTarget.fRight = iTarget.fLeft + 1;
         iTarget.fBottom = iTarget.fTop + 1;
     }

     SkRegion clip(iTarget);
     SkRegion rgn;
     return rgn.setPath(*pathPtr, clip) ^ isInverse;
 }

 bool SkHitTestPath(const SkPath& path, SkScalar x, SkScalar y, bool hires) {
     const SkScalar half = SK_ScalarHalf;
     const SkScalar one = SK_Scalar1;
     SkRect r = SkRect::MakeXYWH(x - half, y - half, one, one);
     return SkHitTestPath(path, r, hires);
 }

 ///////////////////////////////////////////////////////////////////////////////

 #include "SkGeometry.h"

 static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
     SkScalar y0 = pts[0].fY;
     SkScalar y2 = pts[2].fY;

     int dir = 1;
     if (y0 > y2) {
         SkTSwap(y0, y2);
         dir = -1;
     }
     if (y < y0 || y >= y2) {
         return 0;
     }

     // bounds check on X (not required, but maybe faster)
 #if 0
     if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
         return 0;
     }
 #endif

     SkScalar roots[2];
     int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
                                 2 * (pts[1].fY - pts[0].fY),
                                 pts[0].fY - y,
                                 roots);
     SkASSERT(n <= 1);
     SkScalar xt;
     if (0 == n) {
         SkScalar mid = SkScalarAve(y0, y2);
         // Need [0] and [2] if dir == 1
         // and  [2] and [0] if dir == -1
         xt = y < mid ? pts[1 - dir].fX : pts[dir - 1].fX;
     } else {
         SkScalar t = roots[0];
         SkScalar C = pts[0].fX;
         SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
         SkScalar B = 2 * (pts[1].fX - C);
         xt = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C);
     }
     return xt < x ? dir : 0;
 }

 static bool is_mono(SkScalar y0, SkScalar y1, SkScalar y2) {
 //    return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
     if (y0 == y1) {
         return true;
     }
     if (y0 < y1) {
         return y1 <= y2;
     } else {
         return y1 >= y2;
     }
 }

 static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
     SkPoint dst[5];
     int     n = 0;

     if (!is_mono(pts[0].fY, pts[1].fY, pts[2].fY)) {
         n = SkChopQuadAtYExtrema(pts, dst);
         pts = dst;
     }
     int w = winding_mono_quad(pts, x, y);
     if (n > 0) {
         w += winding_mono_quad(&pts[2], x, y);
     }
     return w;
 }

 static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y) {
     SkScalar x0 = pts[0].fX;
     SkScalar y0 = pts[0].fY;
     SkScalar x1 = pts[1].fX;
     SkScalar y1 = pts[1].fY;

     SkScalar dy = y1 - y0;

     int dir = 1;
     if (y0 > y1) {
         SkTSwap(y0, y1);
         dir = -1;
     }
     if (y < y0 || y >= y1) {
         return 0;
     }

     SkScalar cross = SkScalarMul(x1 - x0, y - pts[0].fY) -
                      SkScalarMul(dy, x - pts[0].fX);

     if (SkScalarSignAsInt(cross) == dir) {
         dir = 0;
     }
     return dir;
 }

 static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
     return 0;
 }

 bool SkHitTestPathEx(const SkPath& path, SkScalar x, SkScalar y) {
     bool isInverse = path.isInverseFillType();
     if (path.isEmpty()) {
         return isInverse;
     }

     const SkRect& bounds = path.getBounds();
     if (!bounds.contains(x, y)) {
         return isInverse;
     }

     SkPath::Iter iter(path, true);
     bool done = false;
     int w = 0;
     do {
         SkPoint pts[4];
         switch (iter.next(pts, false)) {
             case SkPath::kMove_Verb:
             case SkPath::kClose_Verb:
                 break;
             case SkPath::kLine_Verb:
                 w += winding_line(pts, x, y);
                 break;
             case SkPath::kQuad_Verb:
                 w += winding_quad(pts, x, y);
                 break;
             case SkPath::kCubic_Verb:
                 w += winding_cubic(pts, x, y);
                 break;
             case SkPath::kDone_Verb:
                 done = true;
                 break;
         }
     } while (!done);

     switch (path.getFillType()) {
         case SkPath::kEvenOdd_FillType:
         case SkPath::kInverseEvenOdd_FillType:
             w &= 1;
             break;
     }
     return SkToBool(w);
 }

	/*
	* Copyright 2006 The Android Open Source Project
	*
	* Use of this source code is governed by a BSD-style license that can be
	* found in the LICENSE file.
	*/


	#include "SkCullPoints.h"
	#include "Sk64.h"

	static bool cross_product_is_neg(const SkIPoint& v, int dx, int dy) {
	#if 0
	return v.fX * dy - v.fY * dx < 0;
	#else
	Sk64 tmp0, tmp1;

	tmp0.setMul(v.fX, dy);
	tmp1.setMul(dx, v.fY);
	tmp0.sub(tmp1);
	return tmp0.isNeg() != 0;
	#endif
	}

	bool SkCullPoints::sect_test(int x0, int y0, int x1, int y1) const {
	const SkIRect& r = fR;

	if ((x0 < r.fLeft && x1 < r.fLeft) \|\|
	(x0 > r.fRight && x1 > r.fRight) \|\|
	(y0 < r.fTop && y1 < r.fTop) \|\|
	(y0 > r.fBottom && y1 > r.fBottom)) {
	return false;
	}

	// since the crossprod test is a little expensive, check for easy-in cases first
	if (r.contains(x0, y0) \|\| r.contains(x1, y1)) {
	return true;
	}

	// At this point we're not sure, so we do a crossprod test
	SkIPoint vec;
	const SkIPoint* rAsQuad = fAsQuad;

	vec.set(x1 - x0, y1 - y0);
	bool isNeg = cross_product_is_neg(vec, x0 - rAsQuad[0].fX, y0 - rAsQuad[0].fY);
	for (int i = 1; i < 4; i++) {
	if (cross_product_is_neg(vec, x0 - rAsQuad[i].fX, y0 - rAsQuad[i].fY) != isNeg) {
	return true;
	}
	}
	return false; // we didn't intersect
	}

	static void toQuad(const SkIRect& r, SkIPoint quad[4]) {
	SkASSERT(quad);

	quad[0].set(r.fLeft, r.fTop);
	quad[1].set(r.fRight, r.fTop);
	quad[2].set(r.fRight, r.fBottom);
	quad[3].set(r.fLeft, r.fBottom);
	}

	SkCullPoints::SkCullPoints() {
	SkIRect r;
	r.setEmpty();
	this->reset(r);
	}

	SkCullPoints::SkCullPoints(const SkIRect& r) {
	this->reset(r);
	}

	void SkCullPoints::reset(const SkIRect& r) {
	fR = r;
	toQuad(fR, fAsQuad);
	fPrevPt.set(0, 0);
	fPrevResult = kNo_Result;
	}

	void SkCullPoints::moveTo(int x, int y) {
	fPrevPt.set(x, y);
	fPrevResult = kNo_Result; // so we trigger a movetolineto later
	}

	SkCullPoints::LineToResult SkCullPoints::lineTo(int x, int y, SkIPoint line[]) {
	SkASSERT(line != NULL);

	LineToResult result = kNo_Result;
	int x0 = fPrevPt.fX;
	int y0 = fPrevPt.fY;

	// need to upgrade sect_test to chop the result
	// and to correctly return kLineTo_Result when the result is connected
	// to the previous call-out
	if (this->sect_test(x0, y0, x, y)) {
	line[0].set(x0, y0);
	line[1].set(x, y);

	if (fPrevResult != kNo_Result && fPrevPt.equals(x0, y0)) {
	result = kLineTo_Result;
	} else {
	result = kMoveToLineTo_Result;
	}
	}

	fPrevPt.set(x, y);
	fPrevResult = result;

	return result;
	}

	/////////////////////////////////////////////////////////////////////////////////////////////////

	#include "SkPath.h"

	SkCullPointsPath::SkCullPointsPath()
	: fCP(), fPath(NULL) {
	}

	SkCullPointsPath::SkCullPointsPath(const SkIRect& r, SkPath* dst)
	: fCP(r), fPath(dst) {
	}

	void SkCullPointsPath::reset(const SkIRect& r, SkPath* dst) {
	fCP.reset(r);
	fPath = dst;
	}

	void SkCullPointsPath::moveTo(int x, int y) {
	fCP.moveTo(x, y);
	}

	void SkCullPointsPath::lineTo(int x, int y) {
	SkIPoint pts[2];

	switch (fCP.lineTo(x, y, pts)) {
	case SkCullPoints::kMoveToLineTo_Result:
	fPath->moveTo(SkIntToScalar(pts[0].fX), SkIntToScalar(pts[0].fY));
	// fall through to the lineto case
	case SkCullPoints::kLineTo_Result:
	fPath->lineTo(SkIntToScalar(pts[1].fX), SkIntToScalar(pts[1].fY));
	break;
	default:
	break;
	}
	}

	///////////////////////////////////////////////////////////////////////////////

	#include "SkMatrix.h"
	#include "SkRegion.h"

	bool SkHitTestPath(const SkPath& path, SkRect& target, bool hires) {
	if (target.isEmpty()) {
	return false;
	}

	bool isInverse = path.isInverseFillType();
	if (path.isEmpty()) {
	return isInverse;
	}

	SkRect bounds = path.getBounds();

	bool sects = SkRect::Intersects(target, bounds);
	if (isInverse) {
	if (!sects) {
	return true;
	}
	} else {
	if (!sects) {
	return false;
	}
	if (target.contains(bounds)) {
	return true;
	}
	}

	SkPath devPath;
	const SkPath* pathPtr;
	SkRect devTarget;

	if (hires) {
	const SkScalar coordLimit = SkIntToScalar(16384);
	const SkRect limit = { 0, 0, coordLimit, coordLimit };

	SkMatrix matrix;
	matrix.setRectToRect(bounds, limit, SkMatrix::kFill_ScaleToFit);

	path.transform(matrix, &devPath);
	matrix.mapRect(&devTarget, target);

	pathPtr = &devPath;
	} else {
	devTarget = target;
	pathPtr = &path;
	}

	SkIRect iTarget;
	devTarget.round(&iTarget);
	if (iTarget.isEmpty()) {
	iTarget.fLeft = SkScalarFloorToInt(devTarget.fLeft);
	iTarget.fTop = SkScalarFloorToInt(devTarget.fTop);
	iTarget.fRight = iTarget.fLeft + 1;
	iTarget.fBottom = iTarget.fTop + 1;
	}

	SkRegion clip(iTarget);
	SkRegion rgn;
	return rgn.setPath(*pathPtr, clip) ^ isInverse;
	}

	bool SkHitTestPath(const SkPath& path, SkScalar x, SkScalar y, bool hires) {
	const SkScalar half = SK_ScalarHalf;
	const SkScalar one = SK_Scalar1;
	SkRect r = SkRect::MakeXYWH(x - half, y - half, one, one);
	return SkHitTestPath(path, r, hires);
	}

	///////////////////////////////////////////////////////////////////////////////

	#include "SkGeometry.h"

	static int winding_mono_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
	SkScalar y0 = pts[0].fY;
	SkScalar y2 = pts[2].fY;

	int dir = 1;
	if (y0 > y2) {
	SkTSwap(y0, y2);
	dir = -1;
	}
	if (y < y0 \|\| y >= y2) {
	return 0;
	}

	// bounds check on X (not required, but maybe faster)
	#if 0
	if (pts[0].fX > x && pts[1].fX > x && pts[2].fX > x) {
	return 0;
	}
	#endif

	SkScalar roots[2];
	int n = SkFindUnitQuadRoots(pts[0].fY - 2 * pts[1].fY + pts[2].fY,
	2 * (pts[1].fY - pts[0].fY),
	pts[0].fY - y,
	roots);
	SkASSERT(n <= 1);
	SkScalar xt;
	if (0 == n) {
	SkScalar mid = SkScalarAve(y0, y2);
	// Need [0] and [2] if dir == 1
	// and [2] and [0] if dir == -1
	xt = y < mid ? pts[1 - dir].fX : pts[dir - 1].fX;
	} else {
	SkScalar t = roots[0];
	SkScalar C = pts[0].fX;
	SkScalar A = pts[2].fX - 2 * pts[1].fX + C;
	SkScalar B = 2 * (pts[1].fX - C);
	xt = SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C);
	}
	return xt < x ? dir : 0;
	}

	static bool is_mono(SkScalar y0, SkScalar y1, SkScalar y2) {
	// return SkScalarSignAsInt(y0 - y1) + SkScalarSignAsInt(y1 - y2) != 0;
	if (y0 == y1) {
	return true;
	}
	if (y0 < y1) {
	return y1 <= y2;
	} else {
	return y1 >= y2;
	}
	}

	static int winding_quad(const SkPoint pts[], SkScalar x, SkScalar y) {
	SkPoint dst[5];
	int n = 0;

	if (!is_mono(pts[0].fY, pts[1].fY, pts[2].fY)) {
	n = SkChopQuadAtYExtrema(pts, dst);
	pts = dst;
	}
	int w = winding_mono_quad(pts, x, y);
	if (n > 0) {
	w += winding_mono_quad(&pts[2], x, y);
	}
	return w;
	}

	static int winding_line(const SkPoint pts[], SkScalar x, SkScalar y) {
	SkScalar x0 = pts[0].fX;
	SkScalar y0 = pts[0].fY;
	SkScalar x1 = pts[1].fX;
	SkScalar y1 = pts[1].fY;

	SkScalar dy = y1 - y0;

	int dir = 1;
	if (y0 > y1) {
	SkTSwap(y0, y1);
	dir = -1;
	}
	if (y < y0 \|\| y >= y1) {
	return 0;
	}

	SkScalar cross = SkScalarMul(x1 - x0, y - pts[0].fY) -
	SkScalarMul(dy, x - pts[0].fX);

	if (SkScalarSignAsInt(cross) == dir) {
	dir = 0;
	}
	return dir;
	}

	static int winding_cubic(const SkPoint pts[], SkScalar x, SkScalar y) {
	return 0;
	}

	bool SkHitTestPathEx(const SkPath& path, SkScalar x, SkScalar y) {
	bool isInverse = path.isInverseFillType();
	if (path.isEmpty()) {
	return isInverse;
	}

	const SkRect& bounds = path.getBounds();
	if (!bounds.contains(x, y)) {
	return isInverse;
	}

	SkPath::Iter iter(path, true);
	bool done = false;
	int w = 0;
	do {
	SkPoint pts[4];
	switch (iter.next(pts, false)) {
	case SkPath::kMove_Verb:
	case SkPath::kClose_Verb:
	break;
	case SkPath::kLine_Verb:
	w += winding_line(pts, x, y);
	break;
	case SkPath::kQuad_Verb:
	w += winding_quad(pts, x, y);
	break;
	case SkPath::kCubic_Verb:
	w += winding_cubic(pts, x, y);
	break;
	case SkPath::kDone_Verb:
	done = true;
	break;
	}
	} while (!done);

	switch (path.getFillType()) {
	case SkPath::kEvenOdd_FillType:
	case SkPath::kInverseEvenOdd_FillType:
	w &= 1;
	break;
	}
	return SkToBool(w);
	}