Bug 516047

Description Matthias Wienand 2017-05-02 08:57:56 EDT

In order to be able to compute the border/outline of a BezierCurve that is drawn onto the screen, one needs to be able to compute the offset of a BezierCurve for a given distance. Since, in the general case, the offset of a Bezier curve is not a Bezier curve, it has to be approximated using (potentially multiple) Bezier curves.

For linear and quadratic Bezier curves, the algorithm of Tiller and Hanson is best suited for the offset approximation. For cubic curves, their algorithm still yields satisfactory results, however for cubic curves and higher degree curves, fitting methods are superior, e.g. Hoschek's method.

As the offset is defined in terms of the input curve's derivative, that derivative needs to be well-defined for the whole parameter range of the input curve. Therefore, an input curve containing cusps needs to be split at the cusps, so that it is effectively treated as a sequence of G^0-continuous Bezier curves, also called a Bezier spline.

The offset approximation for G^0-continuous spline curves incorporates a computation of the offset for the incidence points in-between the individual curves. In practice, the computation depends on the style that is used for drawing the spline curve. Usually, a "StrokeLineJoin" attribute controls the drawing style at the incidence points, which can usually take one of three values: miter, round, or bevel.

However, the complete algorithm for computing the offset of a Bezier curve can be build on top of specialized algorithms that handle the offset computation for simple curves, as well as for the incidence/start/end points of a complex or spline curve.

The algorithm for computing the offset of a Bezier curve with a given distance could be provided by the BezierCurve class:

BezierCurve#getOffsetUnprocessed(distance: double): PolyBezier

The algorithm should work correctly for all curves that possess a well-defined derivative along their whole parameter range. For all other curves, the algorithm may not yield satisfactory or useful results.

Note however, offsetting a Bezier curve by a given distance may result in an offset curve that contains parts, which cannot be found on the outline when drawing the curve using halve the offset distance as the stroke width. Therefore, a refinement needs to be performed where those parts are removed from the offset approximation.

In general, the offset of a Bezier curve can be composed of multiple independent outline curves. However, in most cases, only simple refinements need to be performed, and the refined offset is still G^0-continuous. During the refinement process, some anomalies can be removed from the offset curve.

At all parameter values where the curvature of the input curve is greater than the offset distance, a local anomaly will emerge within the offset approximation. This anomaly may manifest itself as a self-intersection within the offset approximation.

All self-intersections within the offset approximation can be found by testing every pair of approximated offset curves for intersections. If an intersection occurs at parameter values where the curvature of the input curve is greater than the offset distance, then the self-intersection is called a local self-intersection and is subject to removal.

All local self-intersections can be removed without clipping a "hole" into the offset approximation. However, not all local anomalies manifest themselves as self-intersections. There can be regions where the curvature is greater than the offset distance, but it does not result in a self-intersection, because the curve does not extend far enough for its offset to intersect.

Therefore, a second algorithm should be provided that refines the approximated offset by removing all local self-intersections, as well as all other local anomalies from the offset approximation:

BezierCurve#getOffsetRefined(distance: double): PolyBezier

This second algorithm can be used to implement a holistic algorithm that is able to approximate the actual outlines of a BezierCurve that is drawn with a specific stroke width, stroke line join, stroke line cap, etc.

The holistic algorithm would need to combine the offset curves on both sides of the input curve, as well as the offset curves at the start/end/cusp/incidence points of the input curve(s). Again, the intersections need to be recorded and categorized to sort-out which parts of the offset to keep and which parts to dismiss.

The holistic algorithm could be provided outside of the BezierCurve class, e.g. within GEF FX NodeUtils, as the drawing style is kind-of specific to JavaFX (stroke-width, stroke-style, stroke-line-join, stroke-line-cap, stroke-miter-limit, stroke-dash-array, stroke-dash-offset).