From 945a139553a9c9da03766213661d7f5fd6ed3042 Mon Sep 17 00:00:00 2001 From: "reed@android.com" Date: Fri, 5 Feb 2010 20:41:02 +0000 Subject: add SkXRay geometry routines git-svn-id: http://skia.googlecode.com/svn/trunk@488 2bbb7eff-a529-9590-31e7-b0007b416f81 --- src/core/SkGeometry.cpp | 130 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 130 insertions(+) (limited to 'src/core/SkGeometry.cpp') diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp index 4704236fac..c0ef4a5aa5 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 @@ int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]) } } +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 @@ int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], SkScalar tV 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. -- cgit v1.2.3