ref: 2ea511eed81770f423544525adebf7f954b8be93
parent: 80475edead39eb3e7305ebfd43c3fb03a04d372f
author: Alexei Podtelezhnikov <[email protected]>
date: Mon Apr 29 18:49:15 EDT 2019
[smooth] Simplify cubic Bézier flattening. The previous implementation is correct but it is too complex. The revised algorithm is based on the fact that each split moves the control points closer to the trisection points on the chord. The corresponding distances are good surrogates for the curve deviation from the straight line. This cubic flattening algorithm is somewhat similar to the conic algorithm based the distance from the control point to the middle of the chord. The cubic distances, however, decrease less predictably but are easy enough to calculate on each step. * src/smooth/ftgrays.c (gray_render_cubic): Replace the split condition.
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,21 @@
+2019-04-29 Alexei Podtelezhnikov <[email protected]>
+
+ [smooth] Simplify cubic Bézier flattening.
+
+ The previous implementation is correct but it is too complex.
+ The revised algorithm is based on the fact that each split moves
+ the control points closer to the trisection points on the chord.
+ The corresponding distances are good surrogates for the curve
+ deviation from the straight line.
+
+ This cubic flattening algorithm is somewhat similar to the conic
+ algorithm based the distance from the control point to the middle of
+ the chord. The cubic distances, however, decrease less predictably
+ but are easy enough to calculate on each step.
+
+ * src/smooth/ftgrays.c (gray_render_cubic): Replace the split
+ condition.
+
2019-04-26 Alexei Podtelezhnikov <[email protected]>
[smooth] Bithacks and cosmetics.
--- a/src/smooth/ftgrays.c
+++ b/src/smooth/ftgrays.c
@@ -1093,9 +1093,6 @@
{FT_Vector bez_stack[16 * 3 + 1]; /* enough to accommodate bisections */
FT_Vector* arc = bez_stack;
- TPos dx, dy, dx_, dy_;
- TPos dx1, dy1, dx2, dy2;
- TPos L, s, s_limit;
arc[0].x = UPSCALE( to->x );
@@ -1124,45 +1121,13 @@
for (;;)
{- /* Decide whether to split or draw. See `Rapid Termination */
- /* Evaluation for Recursive Subdivision of Bezier Curves' by Thomas */
- /* F. Hain, at */
- /* http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf */
-
- /* dx and dy are x and y components of the P0-P3 chord vector. */
- dx = dx_ = arc[3].x - arc[0].x;
- dy = dy_ = arc[3].y - arc[0].y;
-
- L = FT_HYPOT( dx_, dy_ );
-
- /* Avoid possible arithmetic overflow below by splitting. */
- if ( L > 32767 )
- goto Split;
-
- /* Max deviation may be as much as (s/L) * 3/4 (if Hain's v = 1). */
- s_limit = L * (TPos)( ONE_PIXEL / 6 );
-
- /* s is L * the perpendicular distance from P1 to the line P0-P3. */
- dx1 = arc[1].x - arc[0].x;
- dy1 = arc[1].y - arc[0].y;
- s = FT_ABS( SUB_LONG( MUL_LONG( dy, dx1 ), MUL_LONG( dx, dy1 ) ) );
-
- if ( s > s_limit )
- goto Split;
-
- /* s is L * the perpendicular distance from P2 to the line P0-P3. */
- dx2 = arc[2].x - arc[0].x;
- dy2 = arc[2].y - arc[0].y;
- s = FT_ABS( SUB_LONG( MUL_LONG( dy, dx2 ), MUL_LONG( dx, dy2 ) ) );
-
- if ( s > s_limit )
- goto Split;
-
- /* Split super curvy segments where the off points are so far
- from the chord that the angles P0-P1-P3 or P0-P2-P3 become
- acute as detected by appropriate dot products. */
- if ( dx1 * ( dx1 - dx ) + dy1 * ( dy1 - dy ) > 0 ||
- dx2 * ( dx2 - dx ) + dy2 * ( dy2 - dy ) > 0 )
+ /* with each split, control points quickly converge towards */
+ /* chord trisection points and the vanishing distances below */
+ /* indicate when the segment is flat enough to draw */
+ if ( FT_ABS( 2 * arc[0].x - 3 * arc[1].x + arc[3].x ) > ONE_PIXEL / 2 ||
+ FT_ABS( 2 * arc[0].y - 3 * arc[1].y + arc[3].y ) > ONE_PIXEL / 2 ||
+ FT_ABS( arc[0].x - 3 * arc[2].x + 2 * arc[3].x ) > ONE_PIXEL / 2 ||
+ FT_ABS( arc[0].y - 3 * arc[2].y + 2 * arc[3].y ) > ONE_PIXEL / 2 )
goto Split;
gray_render_line( RAS_VAR_ arc[0].x, arc[0].y );