[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