[RFC PATCH 5/8] d2d1: Implement cubic bezier-line intersection.
Connor McAdams
conmanx360 at gmail.com
Mon May 4 14:44:51 CDT 2020
Signed-off-by: Connor McAdams <conmanx360 at gmail.com>
---
dlls/d2d1/geometry.c | 216 ++++++++++++++++++++++++++++++++++++-------
1 file changed, 181 insertions(+), 35 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 49fb517636..3f57cc1852 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -1943,10 +1943,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
@@ -1965,48 +1973,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;
- enum d2d_vertex_type type;
- D2D1_POINT_2F tmp;
- 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];
- next = idx_p->vertex_idx + 1;
- if (next == figure->vertex_count)
- next = 0;
- p[2] = &figure->vertices[next];
- if (d2d_vertex_type_is_cubic_bezier(type))
- {
- d2d_bezier_cubic_to_quad(p[0],
- &figure->bezier_controls[idx_p->control_idx],
- &figure->bezier_controls[idx_p->control_idx + 1],
- p[2], &tmp);
-
- p[1] = &tmp;
- }
- else
- p[1] = &figure->bezier_controls[idx_p->control_idx];
-
- 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.
*
@@ -2053,6 +2031,174 @@ static BOOL d2d_geometry_intersect_bezier_line(struct d2d_geometry *geometry,
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 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, a, b, c, d;
+ unsigned int root_count;
+
+ /* 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 ((d < 0.0005f && d > -0.0005f))
+ {
+ /* Check if it's actually a line. */
+ if ((a < 0.0005f && a > -0.0005f))
+ {
+ /* Check if it's just a point. If it is, no roots. */
+ if ((b < 0.0005f && b > -0.0005f))
+ return 0;
+
+ roots[0] = -c / b;
+ return 1;
+ }
+
+ return d2d_solve_quadratic_roots(a, b, c, roots);
+ }
+
+ 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;
+
+ if ((disc < 0.00005f && disc > -0.00005f))
+ disc = 0.0f;
+
+ 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.0f) - a / 3.0f;
+ roots[1] = t1 * cosf((phi + 2.0f * M_PI) / 3.0f) - a / 3.0f;
+ roots[2] = t1 * cosf((phi + 4.0f * M_PI) / 3.0f) - a / 3.0f;
+
+ root_count = 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);
+
+ root_count = 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;
+
+ root_count = 1;
+ }
+
+ return root_count;
+}
+
+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);
+}
+
static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
struct d2d_geometry_intersections *intersections,
const struct d2d_segment_idx *idx_p, float start_p, float end_p,
--
2.20.1
More information about the wine-devel
mailing list