refresh from skia/trunk - xray utilities
diff --git a/include/core/SkGeometry.h b/include/core/SkGeometry.h
index 853a7c3..b8ab74c 100644
--- a/include/core/SkGeometry.h
+++ b/include/core/SkGeometry.h
@@ -20,6 +20,17 @@
#include "SkMatrix.h"
+/** An XRay is a half-line that runs from the specific point/origin to
+ +infinity in the X direction. e.g. XRay(3,5) is the half-line
+ (3,5)....(infinity, 5)
+ */
+typedef SkPoint SkXRay;
+
+/** Given a line segment from pts[0] to pts[1], and ax xray, return true if
+ they intersect.
+*/
+bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2]);
+
/** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the
equation.
*/
@@ -72,6 +83,12 @@
*/
int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]);
+/** Given 3 points on a quadratic bezier, use degree elevation to
+ convert it into the cubic fitting the same curve. The new cubic
+ curve is returned in dst[0..3].
+*/
+void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]);
+
////////////////////////////////////////////////////////////////////////////////////////
/** Convert from parametric from (pts) to polynomial coefficients
@@ -131,6 +148,26 @@
int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]);
int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], SkScalar tValues[3] = NULL);
+/** Given a monotonic cubic bezier, determine whether an xray intersects the
+ cubic.
+ By definition the cubic is open at the starting point; in other
+ words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the
+ left of the curve, the line is not considered to cross the curve,
+ but if it is equal to cubic[3].fY then it is considered to
+ cross.
+ */
+bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4]);
+
+/** Given an arbitrary cubic bezier, return the number of times an xray crosses
+ the cubic. Valid return values are [0..3]
+ By definition the cubic is open at the starting point; in other
+ words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the
+ left of the curve, the line is not considered to cross the curve,
+ but if it is equal to cubic[3].fY then it is considered to
+ cross.
+ */
+int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4]);
+
///////////////////////////////////////////////////////////////////////////////////////////
enum SkRotationDirection {
diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp
index 4704236..c0ef4a5 100644
--- a/src/core/SkGeometry.cpp
+++ b/src/core/SkGeometry.cpp
@@ -19,6 +19,35 @@
#include "Sk64.h"
#include "SkMatrix.h"
+bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2]) {
+ // Determine quick discards.
+ // Consider query line going exactly through point 0 to not
+ // intersect, for symmetry with SkXRayCrossesMonotonicCubic.
+ if (pt.fY == pts[0].fY)
+ return false;
+ if (pt.fY < pts[0].fY && pt.fY < pts[1].fY)
+ return false;
+ if (pt.fY > pts[0].fY && pt.fY > pts[1].fY)
+ return false;
+ if (pt.fX > pts[0].fX && pt.fX > pts[1].fX)
+ return false;
+ // Determine degenerate cases
+ if (SkScalarNearlyZero(pts[0].fY - pts[1].fY))
+ return false;
+ if (SkScalarNearlyZero(pts[0].fX - pts[1].fX))
+ // We've already determined the query point lies within the
+ // vertical range of the line segment.
+ return pt.fX <= pts[0].fX;
+ // Full line segment evaluation
+ SkScalar delta_y = pts[1].fY - pts[0].fY;
+ SkScalar delta_x = pts[1].fX - pts[0].fX;
+ SkScalar slope = SkScalarDiv(delta_y, delta_x);
+ SkScalar b = pts[0].fY - SkScalarMul(slope, pts[0].fX);
+ // Solve for x coordinate at y = pt.fY
+ SkScalar x = SkScalarDiv(pt.fY - b, slope);
+ return pt.fX <= x;
+}
+
/** If defined, this makes eval_quad and eval_cubic do more setup (sometimes
involving integer multiplies by 2 or 3, but fewer calls to SkScalarMul.
May also introduce overflow of fixed when we compute our setup.
@@ -391,6 +420,20 @@
}
}
+void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4])
+{
+ SkScalar two = SkIntToScalar(2);
+ SkScalar one_third = SkScalarDiv(SK_Scalar1, SkIntToScalar(3));
+ dst[0].set(src[0].fX, src[0].fY);
+ dst[1].set(
+ SkScalarMul(SkScalarMulAdd(src[1].fX, two, src[0].fX), one_third),
+ SkScalarMul(SkScalarMulAdd(src[1].fY, two, src[0].fY), one_third));
+ dst[2].set(
+ SkScalarMul(SkScalarMulAdd(src[1].fX, two, src[2].fX), one_third),
+ SkScalarMul(SkScalarMulAdd(src[1].fY, two, src[2].fY), one_third));
+ dst[3].set(src[2].fX, src[2].fY);
+}
+
////////////////////////////////////////////////////////////////////////////////////////
///// CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS /////
////////////////////////////////////////////////////////////////////////////////////////
@@ -939,6 +982,93 @@
return count + 1;
}
+bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4]) {
+ // Find the minimum and maximum y of the extrema, which are the
+ // first and last points since this cubic is monotonic
+ SkScalar min_y = SkMinScalar(cubic[0].fY, cubic[3].fY);
+ SkScalar max_y = SkMaxScalar(cubic[0].fY, cubic[3].fY);
+
+ if (pt.fY == cubic[0].fY
+ || pt.fY < min_y
+ || pt.fY > max_y) {
+ // The query line definitely does not cross the curve
+ return false;
+ }
+
+ SkScalar min_x =
+ SkMinScalar(
+ SkMinScalar(
+ SkMinScalar(cubic[0].fX, cubic[1].fX),
+ cubic[2].fX),
+ cubic[3].fX);
+ if (pt.fX < min_x) {
+ // The query line definitely crosses the curve
+ return true;
+ }
+
+ SkScalar max_x =
+ SkMaxScalar(
+ SkMaxScalar(
+ SkMaxScalar(cubic[0].fX, cubic[1].fX),
+ cubic[2].fX),
+ cubic[3].fX);
+ if (pt.fX > max_x) {
+ // The query line definitely does not cross the curve
+ return false;
+ }
+
+ // Do a binary search to find the parameter value which makes y as
+ // close as possible to the query point. See whether the query
+ // line's origin is to the left of the associated x coordinate.
+
+ // kMaxIter is chosen as the number of mantissa bits for a float,
+ // since there's no way we are going to get more precision by
+ // iterating more times than that.
+ const int kMaxIter = 23;
+ SkPoint eval;
+ int iter = 0;
+ SkScalar upper_t;
+ SkScalar lower_t;
+ // Need to invert direction of t parameter if cubic goes up
+ // instead of down
+ if (cubic[3].fY > cubic[0].fY) {
+ upper_t = SK_Scalar1;
+ lower_t = SkFloatToScalar(0);
+ } else {
+ upper_t = SkFloatToScalar(0);
+ lower_t = SK_Scalar1;
+ }
+ do {
+ SkScalar t = SkScalarAve(upper_t, lower_t);
+ SkEvalCubicAt(cubic, t, &eval, NULL, NULL);
+ if (pt.fY > eval.fY) {
+ lower_t = t;
+ } else {
+ upper_t = t;
+ }
+ } while (++iter < kMaxIter
+ && !SkScalarNearlyZero(eval.fY - pt.fY));
+ if (pt.fX <= eval.fX) {
+ return true;
+ }
+ return false;
+}
+
+int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4]) {
+ int num_crossings = 0;
+ SkPoint monotonic_cubics[10];
+ int num_monotonic_cubics = SkChopCubicAtYExtrema(cubic, monotonic_cubics);
+ if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[0]))
+ ++num_crossings;
+ if (num_monotonic_cubics > 0)
+ if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[3]))
+ ++num_crossings;
+ if (num_monotonic_cubics > 1)
+ if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[6]))
+ ++num_crossings;
+ return num_crossings;
+}
+
////////////////////////////////////////////////////////////////////////////////
/* Find t value for quadratic [a, b, c] = d.
