[PATCH v2 3/8] d2d1: Implement new bezier flattening method.
Connor McAdams
conmanx360 at gmail.com
Fri May 15 14:03:16 CDT 2020
Add new flattening methods for cubic beziers and quadratic beziers.
Signed-off-by: Connor McAdams <conmanx360 at gmail.com>
---
dlls/d2d1/geometry.c | 249 +++++++++++++++++++++++++++++++++++++------
1 file changed, 215 insertions(+), 34 deletions(-)
diff --git a/dlls/d2d1/geometry.c b/dlls/d2d1/geometry.c
index e5aa8d6327..001f142fe5 100644
--- a/dlls/d2d1/geometry.c
+++ b/dlls/d2d1/geometry.c
@@ -374,6 +374,13 @@ static void d2d_fp_scale_expansion_zeroelim(float *out, size_t *out_len, const f
*out_len = out_idx;
}
+static void d2d_point_add(D2D1_POINT_2F *out,
+ const D2D1_POINT_2F *a, const D2D1_POINT_2F *b)
+{
+ out->x = a->x + b->x;
+ out->y = a->y + b->y;
+}
+
static void d2d_point_subtract(D2D1_POINT_2F *out,
const D2D1_POINT_2F *a, const D2D1_POINT_2F *b)
{
@@ -3577,48 +3584,222 @@ static HRESULT STDMETHODCALLTYPE d2d_path_geometry_CompareWithGeometry(ID2D1Path
return E_NOTIMPL;
}
+/*
+ * Cubic flattening method derived from now expired US Patent 5,367,617,
+ * titled "System and Method of Hybrid Forward Differencing To Render Bezier
+ * Splines". This is the same method used in WPF, which through testing
+ * appears to be the same method used in D2D.
+ *
+ * This method uses the same principles as Adaptive Foward Differencing,
+ * except instead of adaptively creating points along the curve depending on
+ * the flattening tolerance threshold, we always split at fixed points, so
+ * that the results line up with recursive subdivision.
+ *
+ * Applying AFD to cubic/quadratic beziers basically comes down to this:
+ * p[0] is always p[0].
+ * p[1] is always the difference between the end point and the start point.
+ * p[2] is the second derivative at p[0] for cubics, and just the individual
+ * second derivative for quadratics.
+ * p[3] is the second derivative at p[3] for cubics, and unused for
+ * quadratics, because the second derivative for a quadratic is non-linear.
+ */
+static BOOL d2d_cubic_flattener_half_step_check(D2D1_POINT_2F *p2, D2D1_POINT_2F *p3, float step_size,
+ float flat_tol)
+{
+ /* Step size should never go below half of this amount, which is the
+ * minimum possible tolerance of this method, 0.000001f. */
+ if (step_size < 0.001f)
+ return FALSE;
+
+ /* Check if either derivative is greater than the flattening tolerance, if
+ * one of them is, there is more halving to be done. */
+ if (p2)
+ {
+ if ((max(fabsf(p2->x), fabsf(p2->y))) > flat_tol)
+ return TRUE;
+ }
+
+ if (p3)
+ {
+ if ((max(fabsf(p3->x), fabsf(p3->y))) > flat_tol)
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+/*
+ * Try to take a double-step forward if doing so would be within tolerance and
+ * also wouldn't break up splitting at halves.
+ */
+static BOOL d2d_cubic_flattener_try_double_step(D2D1_POINT_2F *p, int *steps, float *step_size, float q_tol)
+{
+ BOOL doubled = (0 == (*steps & 1));
+ D2D1_POINT_2F tmp;
+
+ if (doubled)
+ {
+ tmp = p[2];
+ d2d_point_scale(&tmp, 2.0f);
+ d2d_point_subtract(&tmp, &tmp, &p[3]);
+
+ if (((max(fabsf(p[3].x), fabsf(p[3].y))) <= q_tol) && ((max(fabsf(tmp.x), fabsf(tmp.y))) <= q_tol))
+ {
+ d2d_point_scale(&p[1], 2.0f);
+
+ p[1].x += p[2].x;
+ p[1].y += p[2].y;
+
+ d2d_point_scale(&p[3], 4.0f);
+
+ p[2] = tmp;
+ d2d_point_scale(&p[2], 4.0f);
+
+ *steps /= 2; // Halve the number of steps left
+ *step_size *= 2.0f;
+ }
+ else
+ doubled = FALSE;
+ }
+
+ return doubled;
+}
+
+/*
+ * Take a half step backwards on the cubic bezier, splitting the cubic bezier
+ * in half.
+ */
+static void d2d_cubic_flattener_half_step(D2D1_POINT_2F *p, int *steps, float *step_size)
+{
+ d2d_point_add(&p[2], &p[2], &p[3]);
+ d2d_point_scale(&p[2], 0.125f);
+
+ d2d_point_subtract(&p[1], &p[1], &p[2]);
+ d2d_point_scale(&p[1], 0.50f);
+
+ d2d_point_scale(&p[3], 0.25f);
+
+ *steps *= 2;
+ *step_size *= 0.5f;
+}
+
+static void d2d_quadratic_flattener_half_step(D2D1_POINT_2F *p, int *steps, float *step_size)
+{
+ d2d_point_scale(&p[1], 0.5f);
+ p[1].x += p[2].x * -0.125f;
+ p[1].y += p[2].y * -0.125f;
+
+ d2d_point_scale(&p[2], 0.25f);
+
+ *steps *= 2;
+ *step_size *= 0.5f;
+}
+
+/*
+ * Go forward a step from a previously halved cubic bezier.
+ */
+static void d2d_cubic_flattener_forward_step(ID2D1SimplifiedGeometrySink *sink, D2D1_POINT_2F *p,
+ int *steps, float *step_size)
+{
+ D2D1_POINT_2F tmp = p[2];
+
+ d2d_point_add(&p[0], &p[0], &p[1]);
+ d2d_point_add(&p[1], &p[1], &tmp);
+ d2d_point_add(&p[2], &p[2], &tmp);
+ d2d_point_subtract(&p[2], &p[2], &p[3]);
+
+ p[3] = tmp;
+
+ ID2D1SimplifiedGeometrySink_AddLines(sink, &p[0], 1);
+
+ *steps -= 1;
+}
+
+static void d2d_quadratic_flattener_forward_step(ID2D1SimplifiedGeometrySink *sink, D2D1_POINT_2F *p,
+ int *steps, float *step_size)
+{
+ p[0].x += p[1].x;
+ p[0].y += p[1].y;
+
+ p[1].x += p[2].x;
+ p[1].y += p[2].y;
+
+ ID2D1SimplifiedGeometrySink_AddLines(sink, &p[0], 1);
+
+ *steps -= 1;
+}
+
static void d2d_geometry_flatten_cubic(ID2D1SimplifiedGeometrySink *sink, const D2D1_POINT_2F *p0,
const D2D1_BEZIER_SEGMENT *b, float tolerance)
{
- D2D1_BEZIER_SEGMENT b0, b1;
- D2D1_POINT_2F q;
- float d;
+ float flat_tol, q_flat_tol;
+ float step_size = 1.0f;
+ int step_count = 1;
+ D2D1_POINT_2F q[4];
- /* It's certainly possible to calculate the maximum deviation of the
- * approximation from the curve, but it's a little involved. Instead, note
- * that if the control points were evenly spaced and collinear, p1 would
- * be exactly between p0 and p2, and p2 would be exactly between p1 and
- * p3. The deviation is a decent enough approximation, and much easier to
- * calculate.
- *
- * p1' = (p0 + p2) / 2
- * p2' = (p1 + p3) / 2
- * d = ‖p1 - p1'‖₁ + ‖p2 - p2'‖₁ */
- d2d_point_lerp(&q, p0, &b->point2, 0.5f);
- d2d_point_subtract(&q, &b->point1, &q);
- d = fabsf(q.x) + fabsf(q.y);
- d2d_point_lerp(&q, &b->point1, &b->point3, 0.5f);
- d2d_point_subtract(&q, &b->point2, &q);
- d += fabsf(q.x) + fabsf(q.y);
- if (d < tolerance)
- {
- ID2D1SimplifiedGeometrySink_AddLines(sink, &b->point3, 1);
- return;
+
+ q[0] = *p0;
+ d2d_point_subtract(&q[1], &b->point3, p0);
+ q[2].x = (b->point1.x - b->point2.x * 2.0f + b->point3.x) * 6.0f;
+ q[2].y = (b->point1.y - b->point2.y * 2.0f + b->point3.y) * 6.0f;
+ q[3].x = (p0->x - b->point1.x * 2.0f + b->point2.x) * 6.0f;
+ q[3].y = (p0->y - b->point1.y * 2.0f + b->point2.y) * 6.0f;
+
+ flat_tol = tolerance >= 0.0f ? tolerance : 0.0f;
+ flat_tol *= 6.0f;
+ q_flat_tol = flat_tol * 0.25f;
+
+ while (d2d_cubic_flattener_half_step_check(&q[2], &q[3], step_size, flat_tol))
+ d2d_cubic_flattener_half_step(q, &step_count, &step_size);
+
+ while(step_count > 1)
+ {
+ d2d_cubic_flattener_forward_step(sink, q, &step_count, &step_size);
+
+ if (d2d_cubic_flattener_half_step_check(&q[2], NULL, step_size, flat_tol))
+ d2d_cubic_flattener_half_step(q, &step_count, &step_size);
+ else
+ {
+ while (d2d_cubic_flattener_try_double_step(q, &step_count, &step_size, q_flat_tol))
+ continue;
+ }
+
+ ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN);
}
- d2d_point_lerp(&q, &b->point1, &b->point2, 0.5f);
+ /* Add final point. */
+ ID2D1SimplifiedGeometrySink_AddLines(sink, &b->point3, 1);
+ ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink, D2D1_PATH_SEGMENT_NONE);
+}
+
+static void d2d_geometry_flatten_quadratic(ID2D1SimplifiedGeometrySink *sink, const D2D1_POINT_2F *p0,
+ const D2D1_POINT_2F *p1, const D2D1_POINT_2F *p2, float tolerance)
+{
+ float step_size = 1.0f;
+ D2D1_POINT_2F q[3];
+ int step_count = 1;
+ float flat_tol;
+
+ q[0] = *p0;
+ d2d_point_subtract(&q[1], p2, p0);
+ q[2].x = 2.0f * (p2->x - (2.0f * p1->x) + p0->x);
+ q[2].y = 2.0f * (p2->y - (2.0f * p1->y) + p0->y);
- b1.point3 = b->point3;
- d2d_point_lerp(&b1.point2, &b1.point3, &b->point2, 0.5f);
- d2d_point_lerp(&b1.point1, &b1.point2, &q, 0.5f);
+ flat_tol = tolerance >= 0.0f ? tolerance : 0.0f;
+ flat_tol *= 6.0f;
- d2d_point_lerp(&b0.point1, p0, &b->point1, 0.5f);
- d2d_point_lerp(&b0.point2, &b0.point1, &q, 0.5f);
- d2d_point_lerp(&b0.point3, &b0.point2, &b1.point1, 0.5f);
+ while (d2d_cubic_flattener_half_step_check(&q[2], NULL, step_size, flat_tol))
+ d2d_quadratic_flattener_half_step(q, &step_count, &step_size);
- d2d_geometry_flatten_cubic(sink, p0, &b0, tolerance);
- ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN);
- d2d_geometry_flatten_cubic(sink, &b0.point3, &b1, tolerance);
+ while (step_count > 1)
+ {
+ d2d_quadratic_flattener_forward_step(sink, q, &step_count, &step_size);
+
+ ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink, D2D1_PATH_SEGMENT_FORCE_ROUND_LINE_JOIN);
+ }
+
+ /* Add final point. */
+ ID2D1SimplifiedGeometrySink_AddLines(sink, p2, 1);
ID2D1SimplifiedGeometrySink_SetSegmentFlags(sink, D2D1_PATH_SEGMENT_NONE);
}
@@ -3632,7 +3813,7 @@ static void d2d_geometry_simplify_quadratic(ID2D1SimplifiedGeometrySink *sink,
b.point3 = *p2;
if (option == D2D1_GEOMETRY_SIMPLIFICATION_OPTION_LINES)
- d2d_geometry_flatten_cubic(sink, p0, &b, tolerance);
+ d2d_geometry_flatten_quadratic(sink, p0, p1, p2, tolerance);
else
ID2D1SimplifiedGeometrySink_AddBeziers(sink, &b, 1);
}
--
2.20.1
More information about the wine-devel
mailing list