[PATCH 04/12] d2d1: Update bezier-line intersection for cubics.
Connor McAdams
conmanx360 at gmail.com
Mon Feb 24 20:32:15 CST 2020
Update bezier-line intersection function to handle cubic bezier curves.
Signed-off-by: Connor McAdams <conmanx360 at gmail.com>
---
dlls/d2d1/geometry.c | 172 +++++++++++++++++++++++++++++++------------
1 file changed, 126 insertions(+), 46 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 8dad84fca3..05b1d10ed8 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -1860,12 +1860,10 @@ static BOOL d2d_geometry_add_bezier_line_intersections(struct d2d_geometry *geom
struct d2d_geometry_intersections *intersections, const struct d2d_segment_idx *idx_p,
const D2D1_POINT_2F **p, const struct d2d_segment_idx *idx_q, const D2D1_POINT_2F **q, float s)
{
- D2D1_POINT_2F intersection, c[2];
+ D2D1_POINT_2F intersection;
float t;
-
- d2d_bezier_quad_to_cubic(p[0], p[1], p[2], &c[0], &c[1]);
- d2d_point_calculate_bezier(&intersection, p[0], &c[0], &c[1], p[2], s);
+ d2d_point_calculate_bezier(&intersection, p[0], p[1], p[2], p[3], s);
if (fabsf(q[1]->x - q[0]->x) > fabsf(q[1]->y - q[0]->y))
t = (intersection.x - q[0]->x) / (q[1]->x - q[0]->x);
else
@@ -1884,22 +1882,125 @@ static BOOL d2d_geometry_add_bezier_line_intersections(struct d2d_geometry *geom
return TRUE;
}
+/* Cubic root finding method adapted from code at
+ * https://pomax.github.io/bezierinfo/#extremities */
+static float d2d_cubic_bezier_cuberoot(float a)
+{
+ if (a < 0)
+ return -powf(-a, 1.0f / 3.0f);
+ else
+ return powf(a, 1.0f / 3.0f);
+}
+
+static int d2d_cubic_bezier_get_roots(float p0, float p1, float p2, float p3, float root[3])
+{
+ float a, b, c, d;
+ float p, p_3, q, q2, disc, sd, tmp;
+ float mp3, r, t, cosphi, phi, crtr, t1, u1, v1;
+
+ /* First, we need to convert the bezier coefficients to 'power basis'
+ * coefficients so that we can use a generic cubic root solving equation. */
+ a = (3.0f * p0 - 6.0f * p1 + 3.0f * p2);
+ b = (-3.0f * p0 + 3.0f * p1);
+ c = p0;
+ d = (-p0 + 3.0f * p1 - 3.0f * p2 + p3);
+
+ /* Check if the curve is actually a quadratic. */
+ if (d2d_cubic_bezier_round_to_zero(d) == 0.0f)
+ {
+ /* Check if it's actually a line. */
+ if (d2d_cubic_bezier_round_to_zero(a) == 0.0f)
+ {
+ /* Check if it's just a point. If it is, no roots. */
+ if (d2d_cubic_bezier_round_to_zero(b) == 0.0f)
+ return 0;
+
+ root[0] = -c / b;
+ return 1;
+ }
+
+ tmp = sqrtf(b * b - 4.0 * a * c);
+ root[0] = (tmp - b) / (2.0 * a);
+ root[1] = (-b - tmp) / (2.0 * a);
+ return 2;
+ }
+
+ a /= d;
+ b /= d;
+ c /= d;
+
+ p = (3.0f * b - a * a) / 3.0f;
+ p_3 = p / 3.0f;
+ q = (2.0f * a * a * a - 9.0f * a * b + 27.0f * c) / 27.0f;
+ q2 = q / 2.0f;
+ disc = q2 * q2 + p_3 * p_3 * p_3;
+
+ disc = d2d_cubic_bezier_round_to_zero(disc);
+ if (disc < 0.0f)
+ {
+ /* Three real roots. */
+ mp3 = -p / 3.0f;
+ r = sqrtf(mp3 * mp3 * mp3);
+ t = -q / (2.0f * r);
+
+ if (t < -1.0f)
+ cosphi = -1.0f;
+ else if (t > 1.0f)
+ cosphi = 1.0f;
+ else
+ cosphi = t;
+
+ phi = acosf(cosphi);
+ crtr = d2d_cubic_bezier_cuberoot(r);
+ t1 = 2.0f * crtr;
+
+ root[0] = t1 * cosf(phi / 3) - a / 3.0f;
+ root[1] = t1 * cosf((phi + 2 * M_PI) / 3) - a / 3.0f;
+ root[2] = t1 * cosf((phi + 4 * M_PI) / 3) - a / 3.0f;
+ return 3;
+ }
+ else if (disc == 0.0f)
+ {
+ /* Three real roots, but two are equal. */
+ if (q2 < 0.0f)
+ tmp = d2d_cubic_bezier_cuberoot(-q2);
+ else
+ tmp = -d2d_cubic_bezier_cuberoot(q2);
+ root[0] = 2.0f * tmp - (a / 3.0f);
+ root[1] = -tmp - (a / 3.0f);
+ return 2;
+ }
+ else
+ {
+ /* One real root, and two complex roots. */
+ sd = sqrtf(disc);
+ u1 = d2d_cubic_bezier_cuberoot(sd - q2);
+ v1 = d2d_cubic_bezier_cuberoot(sd + q2);
+ root[0] = u1 - v1 - a / 3.0f;
+ return 1;
+ }
+
+ return 0;
+}
+
static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry,
struct d2d_geometry_intersections *intersections,
const struct d2d_segment_idx *idx_p, const struct d2d_segment_idx *idx_q)
{
- const D2D1_POINT_2F *p[3], *q[2];
+ const D2D1_POINT_2F *p[4], *q[2];
const struct d2d_figure *figure;
- float y[3], root, theta, d, e;
+ float y[4], roots[3], theta;
+ int num_of_roots, i;
size_t next;
figure = &geometry->u.path.figures[idx_p->figure_idx];
p[0] = &figure->vertices[idx_p->vertex_idx];
- p[1] = &figure->bezier_controls[idx_p->control_idx].cq0;
+ p[1] = &figure->bezier_controls[idx_p->control_idx].c0;
+ p[2] = &figure->bezier_controls[idx_p->control_idx].c1;
next = idx_p->vertex_idx + 1;
if (next == figure->vertex_count)
next = 0;
- p[2] = &figure->vertices[next];
+ p[3] = &figure->vertices[next];
figure = &geometry->u.path.figures[idx_q->figure_idx];
q[0] = &figure->vertices[idx_q->vertex_idx];
@@ -1908,54 +2009,33 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry,
next = 0;
q[1] = &figure->vertices[next];
+ /* If it's just a point, this isn't going to work. */
+ if (q[0]->x == q[1]->x && q[0]->y == q[1]->y)
+ return TRUE;
+
/* Align the line with x-axis. */
theta = -atan2f(q[1]->y - q[0]->y, q[1]->x - q[0]->x);
+ /* Rotate the Y coordinates of the cubic bezier. */
y[0] = (p[0]->x - q[0]->x) * sinf(theta) + (p[0]->y - q[0]->y) * cosf(theta);
y[1] = (p[1]->x - q[0]->x) * sinf(theta) + (p[1]->y - q[0]->y) * cosf(theta);
y[2] = (p[2]->x - q[0]->x) * sinf(theta) + (p[2]->y - q[0]->y) * cosf(theta);
+ y[3] = (p[3]->x - q[0]->x) * sinf(theta) + (p[3]->y - q[0]->y) * cosf(theta);
- /* Intersect the transformed curve with the x-axis.
- *
- * f(t) = (1 - t)²P₀ + 2(1 - t)tP₁ + t²P₂
- * = (P₀ - 2P₁ + P₂)t² + 2(P₁ - P₀)t + P₀
- *
- * a = P₀ - 2P₁ + P₂
- * b = 2(P₁ - P₀)
- * c = P₀
- *
- * f(t) = 0
- * t = (-b ± √(b² - 4ac)) / 2a
- * = (-2(P₁ - P₀) ± √((2(P₁ - P₀))² - 4((P₀ - 2P₁ + P₂)P₀))) / 2(P₀ - 2P₁ + P₂)
- * = (2P₀ - 2P₁ ± √(4P₀² + 4P₁² - 8P₀P₁ - 4P₀² + 8P₀P₁ - 4P₀P₂)) / (2P₀ - 4P₁ + 2P₂)
- * = (P₀ - P₁ ± √(P₁² - P₀P₂)) / (P₀ - 2P₁ + P₂) */
+ num_of_roots = d2d_cubic_bezier_get_roots(y[0], y[1], y[2], y[3], roots);
- d = y[0] - 2 * y[1] + y[2];
- if (d == 0.0f)
+ for (i = 0; i < num_of_roots; i++)
{
- /* P₀ - 2P₁ + P₂ = 0
- * f(t) = (P₀ - 2P₁ + P₂)t² + 2(P₁ - P₀)t + P₀ = 0
- * t = -P₀ / 2(P₁ - P₀) */
- root = -y[0] / (2.0f * (y[1] - y[0]));
- if (root < 0.0f || root > 1.0f)
- return TRUE;
-
- return d2d_geometry_add_bezier_line_intersections(geometry, intersections, idx_p, p, idx_q, q, root);
+ if (roots[i] >= 0.0f && roots[i] <= 1.0f)
+ {
+ if (!d2d_geometry_add_bezier_line_intersections(geometry,
+ intersections, idx_p, p, idx_q, q, roots[i]))
+ {
+ TRACE("d2d_geometry_add_bezier_line_intersections failed.\n");
+ return FALSE;
+ }
+ }
}
- e = y[1] * y[1] - y[0] * y[2];
- if (e < 0.0f)
- return TRUE;
-
- root = (y[0] - y[1] + sqrtf(e)) / d;
- if (root >= 0.0f && root <= 1.0f && !d2d_geometry_add_bezier_line_intersections(geometry,
- intersections, idx_p, p, idx_q, q, root))
- return FALSE;
-
- root = (y[0] - y[1] - sqrtf(e)) / d;
- if (root >= 0.0f && root <= 1.0f && !d2d_geometry_add_bezier_line_intersections(geometry,
- intersections, idx_p, p, idx_q, q, root))
- return FALSE;
-
return TRUE;
}
--
2.20.1
More information about the wine-devel
mailing list