aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/core/SkGeometry.h21
-rw-r--r--src/core/SkGeometry.cpp70
2 files changed, 77 insertions, 14 deletions
diff --git a/include/core/SkGeometry.h b/include/core/SkGeometry.h
index b8ab74caef..a20978326d 100644
--- a/include/core/SkGeometry.h
+++ b/include/core/SkGeometry.h
@@ -26,10 +26,13 @@
*/
typedef SkPoint SkXRay;
-/** Given a line segment from pts[0] to pts[1], and ax xray, return true if
- they intersect.
+/** Given a line segment from pts[0] to pts[1], and an xray, return true if
+ they intersect. Optional outgoing "ambiguous" argument indicates
+ whether the answer is ambiguous because the query occurred exactly at
+ one of the endpoints' y coordinates, indicating that another query y
+ coordinate is preferred for robustness.
*/
-bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2]);
+bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2], bool* ambiguous = NULL);
/** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the
equation.
@@ -155,8 +158,12 @@ int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], SkScalar tV
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.
+ Optional outgoing "ambiguous" argument indicates whether the answer is
+ ambiguous because the query occurred exactly at one of the endpoints' y
+ coordinates, indicating that another query y coordinate is preferred
+ for robustness.
*/
-bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4]);
+bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous = NULL);
/** Given an arbitrary cubic bezier, return the number of times an xray crosses
the cubic. Valid return values are [0..3]
@@ -165,8 +172,12 @@ bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4]);
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.
+ Optional outgoing "ambiguous" argument indicates whether the answer is
+ ambiguous because the query occurred exactly at one of the endpoints' y
+ coordinates or at a tangent point, indicating that another query y
+ coordinate is preferred for robustness.
*/
-int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4]);
+int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous = NULL);
///////////////////////////////////////////////////////////////////////////////////////////
diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp
index 34a0fe0647..3c9e9f90f0 100644
--- a/src/core/SkGeometry.cpp
+++ b/src/core/SkGeometry.cpp
@@ -19,12 +19,19 @@
#include "Sk64.h"
#include "SkMatrix.h"
-bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2]) {
+bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2], bool* ambiguous) {
+ if (ambiguous) {
+ *ambiguous = false;
+ }
// Determine quick discards.
// Consider query line going exactly through point 0 to not
// intersect, for symmetry with SkXRayCrossesMonotonicCubic.
- if (pt.fY == pts[0].fY)
+ if (pt.fY == pts[0].fY) {
+ if (ambiguous) {
+ *ambiguous = true;
+ }
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)
@@ -34,10 +41,27 @@ bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2]) {
// Determine degenerate cases
if (SkScalarNearlyZero(pts[0].fY - pts[1].fY))
return false;
- if (SkScalarNearlyZero(pts[0].fX - pts[1].fX))
+ 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;
+ if (pt.fX <= pts[0].fX) {
+ if (ambiguous) {
+ *ambiguous = (pt.fY == pts[1].fY);
+ }
+ return true;
+ }
+ return false;
+ }
+ // Ambiguity check
+ if (pt.fY == pts[1].fY) {
+ if (pt.fX <= pts[1].fX) {
+ if (ambiguous) {
+ *ambiguous = true;
+ }
+ return true;
+ }
+ return false;
+ }
// Full line segment evaluation
SkScalar delta_y = pts[1].fY - pts[0].fY;
SkScalar delta_x = pts[1].fX - pts[0].fX;
@@ -986,7 +1010,11 @@ int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], SkScalar tV
return count + 1;
}
-bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4]) {
+bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous) {
+ if (ambiguous) {
+ *ambiguous = false;
+ }
+
// 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);
@@ -996,9 +1024,14 @@ bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4]) {
|| pt.fY < min_y
|| pt.fY > max_y) {
// The query line definitely does not cross the curve
+ if (ambiguous) {
+ *ambiguous = (pt.fY == cubic[0].fY);
+ }
return false;
}
+ bool pt_at_extremum = (pt.fY == cubic[3].fY);
+
SkScalar min_x =
SkMinScalar(
SkMinScalar(
@@ -1007,6 +1040,9 @@ bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4]) {
cubic[3].fX);
if (pt.fX < min_x) {
// The query line definitely crosses the curve
+ if (ambiguous) {
+ *ambiguous = pt_at_extremum;
+ }
return true;
}
@@ -1053,23 +1089,39 @@ bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4]) {
} while (++iter < kMaxIter
&& !SkScalarNearlyZero(eval.fY - pt.fY));
if (pt.fX <= eval.fX) {
+ if (ambiguous) {
+ *ambiguous = pt_at_extremum;
+ }
return true;
}
return false;
}
-int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4]) {
+int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous) {
int num_crossings = 0;
SkPoint monotonic_cubics[10];
int num_monotonic_cubics = SkChopCubicAtYExtrema(cubic, monotonic_cubics);
- if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[0]))
+ if (ambiguous) {
+ *ambiguous = false;
+ }
+ bool locally_ambiguous;
+ if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[0], &locally_ambiguous))
++num_crossings;
+ if (ambiguous) {
+ *ambiguous |= locally_ambiguous;
+ }
if (num_monotonic_cubics > 0)
- if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[3]))
+ if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[3], &locally_ambiguous))
++num_crossings;
+ if (ambiguous) {
+ *ambiguous |= locally_ambiguous;
+ }
if (num_monotonic_cubics > 1)
- if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[6]))
+ if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[6], &locally_ambiguous))
++num_crossings;
+ if (ambiguous) {
+ *ambiguous |= locally_ambiguous;
+ }
return num_crossings;
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-28 19:53:48 +0000