[RFC PATCH 4/5] d2d1: Add cubic bezier-line intersection functions.
Connor McAdams
conmanx360 at gmail.com
Sun Mar 15 14:42:57 CDT 2020
Update bezier-line intersection function to handle both cubic and
quadratic beziers.
Signed-off-by: Connor McAdams <conmanx360 at gmail.com>
---
dlls/d2d1/geometry.c | 216 ++++++++++++++++++++++++++++++++++++++-----
1 file changed, 193 insertions(+), 23 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 0fb46a9c87..dd6f50bbec 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -1880,10 +1880,18 @@ 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)
{
+ const struct d2d_figure *figure;
+ enum d2d_vertex_type type;
D2D1_POINT_2F intersection;
float t;
- d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], p[2], s);
+ figure = &geometry->u.path.figures[idx_p->figure_idx];
+ type = figure->vertex_types[idx_p->vertex_idx];
+ if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER)
+ d2d_point_calculate_cubic_bezier(&intersection, p[0], p[1], p[2], p[3], s);
+ else
+ d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], 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
@@ -1902,35 +1910,18 @@ static BOOL d2d_geometry_add_bezier_line_intersections(struct d2d_geometry *geom
return TRUE;
}
-static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry,
+static BOOL d2d_geometry_get_quadratic_bezier_roots(struct d2d_geometry *geometry,
struct d2d_geometry_intersections *intersections,
- const struct d2d_segment_idx *idx_p, const struct d2d_segment_idx *idx_q)
+ const struct d2d_segment_idx *idx_p, const D2D1_POINT_2F **p,
+ const struct d2d_segment_idx *idx_q, const D2D1_POINT_2F **q)
{
- const D2D1_POINT_2F *p[3], *q[2];
- const struct d2d_figure *figure;
float y[3], root, theta, d, e;
- 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];
- next = idx_p->vertex_idx + 1;
- if (next == figure->vertex_count)
- next = 0;
- p[2] = &figure->vertices[next];
-
- figure = &geometry->u.path.figures[idx_q->figure_idx];
- q[0] = &figure->vertices[idx_q->vertex_idx];
- next = idx_q->vertex_idx + 1;
- if (next == figure->vertex_count)
- next = 0;
- q[1] = &figure->vertices[next];
/* Align the line with x-axis. */
theta = -atan2f(q[1]->y - q[0]->y, q[1]->x - q[0]->x);
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[2] = (p[3]->x - q[0]->x) * sinf(theta) + (p[3]->y - q[0]->y) * cosf(theta);
/* Intersect the transformed curve with the x-axis.
*
@@ -1947,7 +1938,7 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry,
* = (2P₀ - 2P₁ ± √(4P₀² + 4P₁² - 8P₀P₁ - 4P₀² + 8P₀P₁ - 4P₀P₂)) / (2P₀ - 4P₁ + 2P₂)
* = (P₀ - P₁ ± √(P₁² - P₀P₂)) / (P₀ - 2P₁ + P₂) */
- d = y[0] - 2 * y[1] + y[2];
+ d = y[0] - 2.0f * y[1] + y[2];
if (d == 0.0f)
{
/* P₀ - 2P₁ + P₂ = 0
@@ -1975,6 +1966,185 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry,
return FALSE;
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.0f)
+ return -powf(-a, 1.0f / 3.0f);
+ else
+ return powf(a, 1.0f / 3.0f);
+}
+
+static float d2d_bezier_round_to_zero(float a)
+{
+ if ((a < 0.0005f && a > -0.0005f))
+ return 0.0f;
+ else
+ return a;
+}
+
+static int d2d_cubic_bezier_get_roots(float *y, float *roots)
+{
+ float mp3, r, t, cosphi, phi, crtr, t1, u1, v1;
+ float p, p_3, q, q2, disc, sd, tmp;
+ float a, b, c, d;
+
+ /* 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 * y[0] - 6.0f * y[1] + 3.0f * y[2]);
+ b = (-3.0f * y[0] + 3.0f * y[1]);
+ c = y[0];
+ d = (-y[0] + 3.0f * y[1] - 3.0f * y[2] + y[3]);
+
+ /* Check if the curve is actually a quadratic. */
+ if (d2d_bezier_round_to_zero(d) == 0.0f)
+ {
+ /* Check if it's actually a line. */
+ if (d2d_bezier_round_to_zero(a) == 0.0f)
+ {
+ /* Check if it's just a point. If it is, no roots. */
+ if (d2d_bezier_round_to_zero(b) == 0.0f)
+ return 0;
+
+ roots[0] = -c / b;
+ return 1;
+ }
+
+ tmp = sqrtf(b * b - 4.0 * a * c);
+ roots[0] = (tmp - b) / (2.0 * a);
+ roots[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_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;
+
+ roots[0] = t1 * cosf(phi / 3) - a / 3.0f;
+ roots[1] = t1 * cosf((phi + 2 * M_PI) / 3) - a / 3.0f;
+ roots[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);
+ roots[0] = 2.0f * tmp - (a / 3.0f);
+ roots[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);
+ roots[0] = u1 - v1 - a / 3.0f;
+
+ return 1;
+ }
+
+ return 0;
+}
+
+static BOOL d2d_geometry_get_cubic_bezier_roots(struct d2d_geometry *geometry,
+ 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 y[4], roots[3], theta;
+ unsigned int num_roots, i;
+
+ /* 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);
+
+ num_roots = d2d_cubic_bezier_get_roots(y, roots);
+
+ for (i = 0; i < num_roots; i++)
+ {
+ 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]))
+ return FALSE;
+ }
+ }
+
+ return TRUE;
+}
+
+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[4], *q[2];
+ const struct d2d_figure *figure;
+ enum d2d_vertex_type type;
+ size_t next;
+
+ figure = &geometry->u.path.figures[idx_p->figure_idx];
+ type = figure->vertex_types[idx_p->vertex_idx];
+ p[0] = &figure->vertices[idx_p->vertex_idx];
+ p[1] = &figure->bezier_controls[idx_p->control_idx];
+ if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER)
+ p[2] = &figure->bezier_controls[idx_p->control_idx + 1];
+ next = idx_p->vertex_idx + 1;
+ if (next == figure->vertex_count)
+ next = 0;
+ p[3] = &figure->vertices[next];
+
+ figure = &geometry->u.path.figures[idx_q->figure_idx];
+ q[0] = &figure->vertices[idx_q->vertex_idx];
+ next = idx_q->vertex_idx + 1;
+ if (next == figure->vertex_count)
+ next = 0;
+ q[1] = &figure->vertices[next];
+
+ if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER)
+ return d2d_geometry_get_cubic_bezier_roots(geometry, intersections, idx_p, p, idx_q, q);
+ else
+ return d2d_geometry_get_quadratic_bezier_roots(geometry, intersections, idx_p, p, idx_q, q);
+
+ return TRUE;
}
static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
--
2.20.1
More information about the wine-devel
mailing list