[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[freetype2] master 2ea511e: [smooth] Simplify cubic Bézier flattening.
From: 
Alexei Podtelezhnikov 
Subject: 
[freetype2] master 2ea511e: [smooth] Simplify cubic Bézier flattening. 
Date: 
Mon, 29 Apr 2019 22:50:45 0400 (EDT) 
branch: master
commit 2ea511eed81770f423544525adebf7f954b8be93
Author: Alexei Podtelezhnikov <address@hidden>
Commit: Alexei Podtelezhnikov <address@hidden>
[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.

ChangeLog  18 ++++++++++++++++++
src/smooth/ftgrays.c  49 +++++++
2 files changed, 25 insertions(+), 42 deletions()
diff git a/ChangeLog b/ChangeLog
index dd9f48c..1efd28a 100644
 a/ChangeLog
+++ b/ChangeLog
@@ 1,3 +1,21 @@
+20190429 Alexei Podtelezhnikov <address@hidden>
+
+ [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.
+
20190426 Alexei Podtelezhnikov <address@hidden>
[smooth] Bithacks and cosmetics.
diff git a/src/smooth/ftgrays.c b/src/smooth/ftgrays.c
index b421fc8..72ab546 100644
 a/src/smooth/ftgrays.c
+++ b/src/smooth/ftgrays.c
@@ 1093,9 +1093,6 @@ typedef ptrdiff_t FT_PtrDist;
{
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 @@ typedef ptrdiff_t FT_PtrDist;
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/Cameraready%20CISST02%202.pdf
*/

 /* dx and dy are x and y components of the P0P3 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 P0P3. */
 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 P0P3. */
 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 P0P1P3 or P0P2P3 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 );
[Prev in Thread] 
Current Thread 
[Next in Thread] 
 [freetype2] master 2ea511e: [smooth] Simplify cubic Bézier flattening.,
Alexei Podtelezhnikov <=