[ft-devel] [patch] simplify and speed up smooth cubic splines

[Алексей Подтележников]

Graham, David,

The patch below does away with cute (as in octagon) but complex estimate
of Euclidean length in favour of straightforward Manhattan distance.
Who says that we have to religiously use Euclidean metrics? As a bonus,
the code runs faster  The speed up of course comes from fewer splits or
'diagonal' arches, but 'diagonal' artifacts are harder to notice too.
So that's warranted IMHO.

The removed protection against overflows (32767) was not sufficient anyway
because the control points themselves can also be way too far.
Should the bands take care of this?

The second hank is less interesting. It's just an arithmetic
simplification of the code.

Alexi




diff -uNr freetype2/src/smooth/ftgrays.c freetype3/src/smooth/ftgrays.c
--- freetype2/src/smooth/ftgrays.c      2010-10-06 07:21:46.033075170 -0400
+++ freetype3/src/smooth/ftgrays.c      2010-10-08 22:16:07.148230683 -0400
@@ -1037,44 +1037,18 @@
       /* 
http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf
*/

       {
-        TPos  dx, dy, dx_, dy_;
+        TPos  dx, dy;
         TPos  dx1, dy1, dx2, dy2;
-        TPos  L, s, s_limit;
+        TPos  s, s_limit;


         /* dx and dy are x and y components of the P0-P3 chord vector. */
         dx = arc[3].x - arc[0].x;
         dy = arc[3].y - arc[0].y;

-        /* L is an (under)estimate of the Euclidean distance P0-P3.       */
-        /*                                                                */
-        /* If dx >= dy, then r = sqrt(dx^2 + dy^2) can be overestimated   */
-        /* with least maximum error by                                    */
-        /*                                                                */
-        /*   r_upperbound = dx + (sqrt(2) - 1) * dy  ,                    */
-        /*                                                                */
-        /* where sqrt(2) - 1 can be (over)estimated by 107/256, giving an */
-        /* error of no more than 8.4%.                                    */
-        /*                                                                */
-        /* Similarly, some elementary calculus shows that r can be        */
-        /* underestimated with least maximum error by                     */
-        /*                                                                */
-        /*   r_lowerbound = sqrt(2 + sqrt(2)) / 2 * dx                    */
-        /*                  + sqrt(2 - sqrt(2)) / 2 * dy  .               */
-        /*                                                                */
-        /* 236/256 and 97/256 are (under)estimates of the two algebraic   */
-        /* numbers, giving an error of no more than 8.1%.                 */
-
-        dx_ = FT_ABS( dx );
-        dy_ = FT_ABS( dy );
-        L = ( 236 * FT_MAX( dx_, dy_ ) + 97 * FT_MIN( dx_, dy_ ) ) >> 8;
-
-        /* 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)( FT_MAX_CURVE_DEVIATION / 0.75 );
+        /* the maximum tolerable areal gap around the chord */
+        s_limit = ( FT_ABS( dx ) + FT_ABS( dy ) )
+                  * (TPos)( FT_MAX_CURVE_DEVIATION * 4 / 3 );

         /* s is L * the perpendicular distance from P1 to the line P0-P3. */
         dx1 = arc[1].x - arc[0].x;
@@ -1093,10 +1067,13 @@
           goto Split;

         /* If P1 or P2 is outside P0-P3, split the curve. */
-        if ( dy * dy1 + dx * dx1 < 0                                     ||
-             dy * dy2 + dx * dx2 < 0                                     ||
-             dy * (arc[3].y - arc[1].y) + dx * (arc[3].x - arc[1].x) < 0 ||
-             dy * (arc[3].y - arc[2].y) + dx * (arc[3].x - arc[2].x) < 0 )
+        s_limit = dx * dx + dy * dy;
+        s = dx * dx1 + dy * dy1;
+        if ( s < 0 || s > s_limit )
+          goto Split;
+
+        s = dx * dx2 + dy * dy2;
+        if ( s < 0 || s > s_limit )
           goto Split;

         /* No reason to split. */