[RFC PATCH 2/5] d2d1: Add cubic bezier bounds functions.
Connor McAdams
conmanx360 at gmail.com
Sun Mar 15 14:42:55 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 | 181 ++++++++++++++++++++++++++++++++++++-------
1 file changed, 151 insertions(+), 30 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index 6f48980eb8..33d55c6451 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -399,7 +399,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;
@@ -408,6 +408,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;
@@ -522,7 +536,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;
@@ -544,18 +558,124 @@ 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, a, b, c;
+ float root, sq_root;
+
+ 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.x = v1.x - 2.0f * v2.x + v3.x;
+ a.y = v1.y - 2.0f * v2.y + v3.y;
+ b.x = 2.0f * (v2.x - v1.x);
+ b.y = 2.0f * (v2.y - v1.y);
+ c.x = v1.x;
+ c.y = v1.y;
+
+ /* If the square root in the equation is negative, there are no roots. */
+ if ((sq_root = sqrtf(b.x * b.x - 4.0f * a.x * c.x)) >= 0.0f)
+ {
+ root = (-b.x + sq_root) / (2.0f * a.x);
+ if (root < 1.0f && root > 0.0f)
+ {
+ d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root);
+ d2d_rect_expand(bounds, &p);
+ }
+
+ root = (-b.x - sq_root) / (2.0f * a.x);
+ if (root < 1.0f && root > 0.0f)
+ {
+ d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root);
+ d2d_rect_expand(bounds, &p);
+ }
+ }
+
+ if ((sq_root = sqrtf(b.y * b.y - 4.0f * a.y * c.y)) >= 0.0f)
+ {
+ root = (-b.y + sq_root) / (2.0f * a.y);
+ if (root < 1.0f && root > 0.0f)
+ {
+ d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root);
+ d2d_rect_expand(bounds, &p);
+ }
+
+ root = (-b.y - sq_root) / (2.0f * a.y);
+ if (root < 1.0f && root > 0.0f)
+ {
+ d2d_point_calculate_cubic_bezier(&p, p0, p1, p2, p3, root);
+ 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)
{
@@ -570,7 +690,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)
@@ -1715,7 +1835,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
@@ -1848,7 +1968,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;
@@ -2617,8 +2737,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_QUADRATIC_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);
if (!d2d_figure_add_quadratic_bezier_control(figure, &p))
{
@@ -3041,7 +3161,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;
@@ -3211,7 +3331,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)
@@ -3256,23 +3376,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:
@@ -3290,20 +3408,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