Add new flattening methods for cubic beziers and quadratic beziers.
Signed-off-by: Connor McAdams conmanx360@gmail.com --- Note: The documentation here is mainly because of RFC, probably isn't as well written as most math oriented people would like. I can try to explain it further if need be, and these will probably not need to be included in the actual patch series. 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 299e997ea1..f6608a19b4 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) { @@ -3598,48 +3605,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); }
@@ -3654,7 +3835,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); }