[RFC PATCH 3/8] d2d1: Add cubic bezier bounds functions.
Connor McAdams
conmanx360 at gmail.com
Mon May 4 14:44:49 CDT 2020
Add functions for calculating the bounds of a cubic bezier.
Signed-off-by: Connor McAdams <conmanx360 at gmail.com>
---
dlls/d2d1/geometry.c | 189 ++++++++++++++++++++++++++++++++++++-------
1 file changed, 159 insertions(+), 30 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index f6608a19b4..ba7f51cccd 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -401,7 +401,7 @@ static void d2d_point_lerp(D2D1_POINT_2F *out,
out->y = a->y * (1.0f - t) + b->y * t;
}
-static void d2d_point_calculate_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F *p0,
+static void d2d_point_calculate_quadratic_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F *p0,
const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float t)
{
float t_c = 1.0f - t;
@@ -410,6 +410,20 @@ static void d2d_point_calculate_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F *
out->y = t_c * (t_c * p0->y + t * p1->y) + t * (t_c * p1->y + t * p2->y);
}
+static void d2d_point_calculate_cubic_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F *p0,
+ const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, float t)
+{
+ D2D1_POINT_2F q[5];
+
+ d2d_point_lerp(&q[0], p0, p1, t);
+ d2d_point_lerp(&q[1], p1, p2, t);
+ d2d_point_lerp(&q[2], p2, p3, t);
+
+ d2d_point_lerp(&q[3], &q[0], &q[1], t);
+ d2d_point_lerp(&q[4], &q[1], &q[2], t);
+ d2d_point_lerp(out, &q[3], &q[4], t);
+}
+
static void d2d_point_normalise(D2D1_POINT_2F *p)
{
float l;
@@ -564,6 +578,37 @@ static float d2d_point_ccw(const D2D1_POINT_2F *a, const D2D1_POINT_2F *b, const
return det_d[det_d_len - 1];
}
+static unsigned int d2d_solve_quadratic_roots(float a, float b, float c, float *roots)
+{
+ float sq_root, root, tmp;
+ unsigned int root_count = 0;
+
+ tmp = b * b - 4.0f * a * c;
+
+ if (tmp >= 0.0f)
+ {
+ sq_root = sqrtf(tmp);
+
+ if (b >= 0.0f)
+ root = (-b - sq_root) / (2.0f * a);
+ else
+ root = (2.0f * c) / (-b + sq_root);
+
+ if (root > 0.0f && root < 1.0f)
+ roots[root_count++] = root;
+
+ if (b >= 0.0f)
+ root = (2.0f * c) / (-b - sq_root);
+ else
+ root = (-b + sq_root) / (2.0f * a);
+
+ if (root > 0.0f && root < 1.0f)
+ roots[root_count++] = root;
+ }
+
+ return root_count;
+}
+
static void d2d_rect_union(D2D1_RECT_F *l, const D2D1_RECT_F *r)
{
l->left = min(l->left, r->left);
@@ -577,7 +622,7 @@ static BOOL d2d_rect_check_overlap(const D2D_RECT_F *p, const D2D_RECT_F *q)
return p->left < q->right && p->top < q->bottom && p->right > q->left && p->bottom > q->top;
}
-static void d2d_rect_get_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *p0,
+static void d2d_rect_get_quadratic_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *p0,
const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2)
{
D2D1_POINT_2F p;
@@ -599,18 +644,101 @@ static void d2d_rect_get_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *
root = (p0->x - p1->x) / (p2->x - 2.0f * p1->x + p0->x);
if (root > 0.0f && root < 1.0f)
{
- d2d_point_calculate_bezier(&p, p0, p1, p2, root);
+ d2d_point_calculate_quadratic_bezier(&p, p0, p1, p2, root);
d2d_rect_expand(bounds, &p);
}
root = (p0->y - p1->y) / (p2->y - 2.0f * p1->y + p0->y);
if (root > 0.0f && root < 1.0f)
{
- d2d_point_calculate_bezier(&p, p0, p1, p2, root);
+ d2d_point_calculate_quadratic_bezier(&p, p0, p1, p2, root);
d2d_rect_expand(bounds, &p);
}
}
+static BOOL d2d_check_if_cubic_is_quad(const D2D1_POINT_2F *p0, const D2D1_POINT_2F *p1,
+ const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3)
+{
+ D2D1_POINT_2F tmp;
+
+ tmp.x = -p0->x + 3.0f * p1->x - 3.0f * p2->x + p3->x;
+ tmp.y = -p0->y + 3.0f * p1->y - 3.0f * p2->y + p3->y;
+
+ if ((tmp.x < 0.0005f && tmp.x > -0.0005f) && (tmp.y < 0.0005f && tmp.y > -0.0005f))
+ return TRUE;
+ else
+ return FALSE;
+}
+
+static void d2d_rect_get_cubic_bezier_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *p0,
+ const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3)
+{
+ D2D1_POINT_2F p, v1, v2, v3;
+ float roots[2], a[2], b[2], c[2];
+ unsigned int i, y, root_count;
+
+ if (d2d_check_if_cubic_is_quad(p0, p1, p2, p3))
+ {
+ d2d_bezier_cubic_to_quad(p0, p1, p2, p3, &p);
+ d2d_rect_get_quadratic_bezier_bounds(bounds, p0, &p, p3);
+ return;
+ }
+
+ bounds->left = p0->x;
+ bounds->top = p0->y;
+ bounds->right = p0->x;
+ bounds->bottom = p0->y;
+
+ d2d_rect_expand(bounds, p3);
+
+ /*
+ * f(t) = (1 - t)³P₀ + 3(1 - t)²tP₁ + 3(1 - t)t²P₂ + t³P₃
+ * f'(t) = 3(1 - t)²(P₁ - P₀) + 6(1 - t)t(P₂ - P₁) + 3t²(P₃ - P₂)
+ *
+ * Or, from https://pomax.github.io/bezierinfo/#extremities
+ * V₁ = 3(P₁ - P₀)
+ * V₂ = 3(P₂ - P₁)
+ * V₃ = 3(P₃ - P₂)
+ * f'(t) = V₁(1 - t)² + 2V₂(1 - t)t + V₃t²
+ * = (V₁ - 2V₂ + V₃)t² + 2(V₂ - V₁)t + V₁
+ *
+ * And new quadratic coefficients a, b, and c are:
+ * a = V₁ - 2V₂ + V₃
+ * b = 2(V₂ - V₁)
+ * c = V₁
+ *
+ * f'(t) = 0
+ * t = (-b ± √(b² - 4ac)) / 2a
+ */
+ d2d_point_subtract(&v1, p1, p0);
+ d2d_point_scale(&v1, 3.0f);
+
+ d2d_point_subtract(&v2, p2, p1);
+ d2d_point_scale(&v2, 3.0f);
+
+ d2d_point_subtract(&v3, p3, p2);
+ d2d_point_scale(&v3, 3.0f);
+
+ a[0] = v1.x - 2.0f * v2.x + v3.x;
+ a[1] = v1.y - 2.0f * v2.y + v3.y;
+
+ b[0] = 2.0f * (v2.x - v1.x);
+ b[1] = 2.0f * (v2.y - v1.y);
+
+ c[0] = v1.x;
+ c[1] = v1.y;
+
+ for (i = 0; i < 2; ++i)
+ {
+ root_count = d2d_solve_quadratic_roots(a[i], b[i], c[i], roots);
+ for (y = 0; y < root_count; ++y)
+ {
+ d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, roots[y]);
+ d2d_rect_expand(bounds, &p);
+ }
+ }
+}
+
static void d2d_rect_get_bezier_segment_bounds(D2D_RECT_F *bounds, const D2D1_POINT_2F *p0,
const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float start, float end)
{
@@ -625,7 +753,7 @@ static void d2d_rect_get_bezier_segment_bounds(D2D_RECT_F *bounds, const D2D1_PO
d2d_point_lerp(&r[0], &r[1], p2, end);
d2d_point_lerp(&q[2], &q[1], &r[0], end);
- d2d_rect_get_bezier_bounds(bounds, &q[0], &q[1], &q[2]);
+ d2d_rect_get_quadratic_bezier_bounds(bounds, &q[0], &q[1], &q[2]);
}
static BOOL d2d_figure_insert_vertex(struct d2d_figure *figure, size_t idx, D2D1_POINT_2F vertex)
@@ -1802,7 +1930,7 @@ static BOOL d2d_geometry_add_bezier_line_intersections(struct d2d_geometry *geom
D2D1_POINT_2F intersection;
float t;
- d2d_point_calculate_bezier(&intersection, p[0], p[1], p[2], s);
+ d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], p[2], 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
@@ -1971,7 +2099,7 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
if (end_p - start_p < 1e-3f)
{
- d2d_point_calculate_bezier(&intersection, p[0], p[1], p[2], centre_p);
+ d2d_point_calculate_quadratic_bezier(&intersection, p[0], p[1], p[2], centre_p);
if (start_p > 0.0f && end_p < 1.0f && !d2d_geometry_intersections_add(intersections,
idx_p, centre_p, intersection))
return FALSE;
@@ -2766,8 +2894,8 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddBeziers(ID2D1GeometrySink *if
p.y -= (figure->vertices[figure->vertex_count - 1].y + beziers[i].point3.y) * 0.25f;
figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_CUBIC_BEZIER;
- d2d_rect_get_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1],
- &p, &beziers[i].point3);
+ d2d_rect_get_cubic_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1],
+ &beziers[i].point1, &beziers[i].point2, &beziers[i].point3);
c[0] = &beziers[i].point1;
c[1] = &beziers[i].point2;
@@ -3275,7 +3403,7 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddQuadraticBeziers(ID2D1Geometr
{
D2D1_RECT_F bezier_bounds;
- d2d_rect_get_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1],
+ d2d_rect_get_quadratic_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1],
&beziers[i].point1, &beziers[i].point2);
figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_QUADRATIC_BEZIER;
@@ -3445,7 +3573,7 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
const struct d2d_figure *figure = &geometry->u.path.figures[i];
enum d2d_vertex_type type = D2D_VERTEX_TYPE_NONE;
D2D1_RECT_F bezier_bounds;
- D2D1_POINT_2F p, p1, p2;
+ D2D1_POINT_2F p, p1, p2, p3;
size_t j, bezier_idx;
if (figure->flags & D2D_FIGURE_FLAG_HOLLOW)
@@ -3490,23 +3618,21 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
d2d_point_transform(&p1, transform, p1.x, p1.y);
p2 = figure->vertices[j];
d2d_point_transform(&p2, transform, p2.x, p2.y);
- d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2);
+ d2d_rect_get_quadratic_bezier_bounds(&bezier_bounds, &p, &p1, &p2);
d2d_rect_union(bounds, &bezier_bounds);
p = p2;
break;
case D2D_VERTEX_TYPE_CUBIC_BEZIER:
- d2d_bezier_cubic_to_quad(&figure->vertices[j - 1],
- &figure->original_bezier_controls[bezier_idx],
- &figure->original_bezier_controls[bezier_idx + 1],
- &figure->vertices[j], &p1);
- bezier_idx += 2;
+ p1 = figure->original_bezier_controls[bezier_idx++];
d2d_point_transform(&p1, transform, p1.x, p1.y);
- p2 = figure->vertices[j];
+ p2 = figure->original_bezier_controls[bezier_idx++];
d2d_point_transform(&p2, transform, p2.x, p2.y);
- d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2);
+ p3 = figure->vertices[j];
+ d2d_point_transform(&p3, transform, p3.x, p3.y);
+ d2d_rect_get_cubic_bezier_bounds(&bezier_bounds, &p, &p1, &p2, &p3);
d2d_rect_union(bounds, &bezier_bounds);
- p = p2;
+ p = p3;
break;
default:
@@ -3524,20 +3650,23 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
{
if (type == D2D_VERTEX_TYPE_CUBIC_BEZIER)
{
- d2d_bezier_cubic_to_quad(&figure->vertices[j - 1],
- &figure->original_bezier_controls[bezier_idx],
- &figure->original_bezier_controls[bezier_idx + 1],
- &figure->vertices[0], &p1);
-
- bezier_idx += 2;
+ p1 = figure->original_bezier_controls[bezier_idx++];
+ d2d_point_transform(&p1, transform, p1.x, p1.y);
+ p2 = figure->original_bezier_controls[bezier_idx++];
+ d2d_point_transform(&p2, transform, p2.x, p2.y);
+ p3 = figure->vertices[0];
+ d2d_point_transform(&p3, transform, p3.x, p3.y);
+ d2d_rect_get_cubic_bezier_bounds(&bezier_bounds, &p, &p1, &p2, &p3);
}
else
+ {
p1 = figure->original_bezier_controls[bezier_idx++];
+ d2d_point_transform(&p1, transform, p1.x, p1.y);
+ p2 = figure->vertices[0];
+ d2d_point_transform(&p2, transform, p2.x, p2.y);
+ d2d_rect_get_quadratic_bezier_bounds(&bezier_bounds, &p, &p1, &p2);
+ }
- d2d_point_transform(&p1, transform, p1.x, p1.y);
- p2 = figure->vertices[0];
- d2d_point_transform(&p2, transform, p2.x, p2.y);
- d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2);
d2d_rect_union(bounds, &bezier_bounds);
}
}
--
2.20.1
More information about the wine-devel
mailing list