[PATCH 02/12] d2d1: Add cubic bezier bounds functions.
Connor McAdams
conmanx360 at gmail.com
Mon Feb 24 20:32:13 CST 2020
Add functions for calculating the bounds of a cubic bezier.
Signed-off-by: Connor McAdams <conmanx360 at gmail.com>
---
dlls/d2d1/geometry.c | 185 +++++++++++++++++++++++++++++++++++--------
1 file changed, 152 insertions(+), 33 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index a8e6a3f2b7..4ec0f16d07 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -399,12 +399,14 @@ static void d2d_point_lerp(D2D1_POINT_2F *out,
}
static void d2d_point_calculate_bezier(D2D1_POINT_2F *out, const D2D1_POINT_2F *p0,
- const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float t)
+ const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, float t)
{
float t_c = 1.0f - t;
+ float t_c_cube = t_c * t_c * t_c, t_cube = t * t * t;
+ float t_c_sq = t_c * t_c, t_sq = t * t;
- out->x = t_c * (t_c * p0->x + t * p1->x) + t * (t_c * p1->x + t * p2->x);
- out->y = t_c * (t_c * p0->y + t * p1->y) + t * (t_c * p1->y + t * p2->y);
+ out->x = t_c_cube * p0->x + 3.0f * t_c_sq * t * p1->x + 3.0f * t_c * t_sq * p2->x + t_cube * p3->x;
+ out->y = t_c_cube * p0->y + 3.0f * t_c_sq * t * p1->y + 3.0f * t_c * t_sq * p2->y + t_cube * p3->y;
}
static void d2d_point_normalise(D2D1_POINT_2F *p)
@@ -424,6 +426,28 @@ static void d2d_bezier_quad_to_cubic(const D2D1_POINT_2F *p0, const D2D1_POINT_2
c1->y = p2->y * (1.0f / 3.0f) + (2.0f / 3.0f) * p1->y;
}
+static void d2d_bezier_cubic_to_quad(const D2D1_POINT_2F *p0, const D2D1_POINT_2F *p1,
+ const D2D1_POINT_2F *p2, const D2D1_POINT_2F *p3, D2D1_POINT_2F *c0)
+{
+ c0->x = (p1->x + p2->x) * 0.75f;
+ c0->y = (p1->y + p2->y) * 0.75f;
+ c0->x -= (p0->x + p3->x) * 0.25f;
+ c0->y -= (p0->y + p3->y) * 0.25f;
+}
+
+/*
+ * This value is useful for many different cubic bezier operations, including
+ * root finding, derivative checking, and texture coordinate calculations.
+ */
+#define D2D1_CUBIC_BEZIER_EPSILON 0.00005f
+static float d2d_cubic_bezier_round_to_zero(float a)
+{
+ if (a < 0.00005f && a > -0.00005f)
+ return 0.0f;
+
+ return a;
+}
+
/* This implementation is based on the paper "Adaptive Precision
* Floating-Point Arithmetic and Fast Robust Geometric Predicates" and
* associated (Public Domain) code by Jonathan Richard Shewchuk. */
@@ -521,44 +545,131 @@ 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,
- const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2)
+static void d2d_rect_get_quad_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;
+ D2D1_POINT_2F p, c;
float root;
- bounds->left = p0->x;
- bounds->top = p0->y;
- bounds->right = p0->x;
- bounds->bottom = p0->y;
-
- d2d_rect_expand(bounds, p2);
+ d2d_bezier_cubic_to_quad(p0, p1, p2, p3, &c);
/* f(t) = (1 - t)²P₀ + 2(1 - t)tP₁ + t²P₂
* f'(t) = 2(1 - t)(P₁ - P₀) + 2t(P₂ - P₁)
* = 2(P₂ - 2P₁ + P₀)t + 2(P₁ - P₀)
*
* f'(t) = 0
- * t = (P₀ - P₁) / (P₂ - 2P₁ + P₀) */
- root = (p0->x - p1->x) / (p2->x - 2.0f * p1->x + p0->x);
+ * t = (P₀ - P₁) / (P₂ - 2P₁ + P₀)
+ */
+ root = (p0->x - c.x) / (p3->x - 2.0f * c.x + p0->x);
if (root > 0.0f && root < 1.0f)
{
- d2d_point_calculate_bezier(&p, p0, p1, p2, root);
+ d2d_point_calculate_bezier(&p, p0, p1, p2, p3, root);
d2d_rect_expand(bounds, &p);
}
- root = (p0->y - p1->y) / (p2->y - 2.0f * p1->y + p0->y);
+ root = (p0->y - c.y) / (p3->y - 2.0f * c.y + p0->y);
if (root > 0.0f && root < 1.0f)
{
- d2d_point_calculate_bezier(&p, p0, p1, p2, root);
+ d2d_point_calculate_bezier(&p, p0, p1, p2, p3, root);
d2d_rect_expand(bounds, &p);
}
}
+static void d2d_rect_get_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;
+
+ 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
+ */
+ v1.x = 3.0f * (p1->x - p0->x);
+ v1.y = 3.0f * (p1->y - p0->y);
+
+ v2.x = 3.0f * (p2->x - p1->x);
+ v2.y = 3.0f * (p2->y - p1->y);
+
+ v3.x = 3.0f * (p3->x - p2->x);
+ v3.y = 3.0f * (p3->y - p2->y);
+
+ /* This will check if the cubic bezier is actually a quadratic, in which
+ * case we need the second derivative to get the extremities. */
+ a.x = v1.x - 2.0f * v2.x + v3.x;
+ a.y = v1.y - 2.0f * v2.y + v3.y;
+ if ((d2d_cubic_bezier_round_to_zero(a.x) == 0.0f) && (d2d_cubic_bezier_round_to_zero(a.y) == 0.0f))
+ {
+ d2d_rect_get_quad_bezier_bounds(bounds, p0, p1, p2, p3);
+ return;
+ }
+ 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_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_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_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_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)
{
- D2D1_POINT_2F q[3], r[2];
+ D2D1_POINT_2F q[3], r[2], c[2];
d2d_point_lerp(&r[0], p0, p1, start);
d2d_point_lerp(&r[1], p1, p2, start);
@@ -569,7 +680,8 @@ 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_bezier_quad_to_cubic(&q[0], &q[1], &q[2], &c[0], &c[1]);
+ d2d_rect_get_bezier_bounds(bounds, &q[0], &c[0], &c[1], &q[2]);
}
static BOOL d2d_figure_insert_vertex(struct d2d_figure *figure, size_t idx, D2D1_POINT_2F vertex)
@@ -1715,10 +1827,12 @@ 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;
+ D2D1_POINT_2F intersection, c[2];
float t;
- d2d_point_calculate_bezier(&intersection, p[0], p[1], p[2], s);
+
+ 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);
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
@@ -1820,7 +1934,7 @@ static BOOL d2d_geometry_intersect_bezier_bezier(struct d2d_geometry *geometry,
const D2D1_POINT_2F *p[3], *q[3];
const struct d2d_figure *figure;
D2D_RECT_F p_bounds, q_bounds;
- D2D1_POINT_2F intersection;
+ D2D1_POINT_2F intersection, c[2];
float centre_p, centre_q;
size_t next;
@@ -1851,7 +1965,8 @@ 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_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], centre_p);
if (start_p > 0.0f && end_p < 1.0f && !d2d_geometry_intersections_add(intersections,
idx_p, centre_p, intersection))
return FALSE;
@@ -2565,7 +2680,7 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddBeziers(ID2D1GeometrySink *if
figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_BEZIER;
d2d_rect_get_bezier_bounds(&bezier_bounds, &figure->vertices[figure->vertex_count - 1],
- &p, &beziers[i].point3);
+ &beziers[i].point1, &beziers[i].point2, &beziers[i].point3);
if (!d2d_figure_add_bezier_control(figure, &beziers[i].point1, &beziers[i].point2, &p))
{
@@ -2993,7 +3108,7 @@ static void STDMETHODCALLTYPE d2d_geometry_sink_AddQuadraticBeziers(ID2D1Geometr
p2 = beziers[i].point2;
d2d_bezier_quad_to_cubic(&p0, &p1, &p2, &c[0], &c[1]);
- d2d_rect_get_bezier_bounds(&bezier_bounds, &p0, &p1, &p2);
+ d2d_rect_get_bezier_bounds(&bezier_bounds, &p0, &c[0], &c[1], &p2);
figure->vertex_types[figure->vertex_count - 1] = D2D_VERTEX_TYPE_BEZIER;
if (!d2d_figure_add_bezier_control(figure, &c[0], &c[1], &p1))
@@ -3162,7 +3277,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)
@@ -3203,13 +3318,15 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
break;
case D2D_VERTEX_TYPE_BEZIER:
- p1 = figure->original_bezier_controls[bezier_idx++].cq0;
+ p1 = figure->original_bezier_controls[bezier_idx].c0;
d2d_point_transform(&p1, transform, p1.x, p1.y);
- p2 = figure->vertices[j];
+ p2 = figure->original_bezier_controls[bezier_idx++].c1;
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_bezier_bounds(&bezier_bounds, &p, &p1, &p2, &p3);
d2d_rect_union(bounds, &bezier_bounds);
- p = p2;
+ p = p3;
break;
default:
@@ -3225,11 +3342,13 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_GetBounds(ID2D1PathGeometry *
if (type == D2D_VERTEX_TYPE_BEZIER)
{
- p1 = figure->original_bezier_controls[bezier_idx++].cq0;
+ p1 = figure->original_bezier_controls[bezier_idx].c0;
d2d_point_transform(&p1, transform, p1.x, p1.y);
- p2 = figure->vertices[0];
+ p2 = figure->original_bezier_controls[bezier_idx++].c1;
d2d_point_transform(&p2, transform, p2.x, p2.y);
- d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2);
+ p3 = figure->vertices[0];
+ d2d_point_transform(&p3, transform, p3.x, p3.y);
+ d2d_rect_get_bezier_bounds(&bezier_bounds, &p, &p1, &p2, &p3);
d2d_rect_union(bounds, &bezier_bounds);
}
}
--
2.20.1
More information about the wine-devel
mailing list