Commit 6eb6158dd787dfbd7576904f99346f5b18a72ee7
2015-10-06T22:39:54
[smooth] Faster alternative line renderer. This implementation renders the entire line segment at once without subdividing it into scanlines. The main speed improvement comes from reducing the number of divisions to just two per line segment, which is a bare minimum to calculate cell coverage in a smooth rasterizer. Notably, the progression from cell to cell does not itself require any divisions at all. The speed improvement is more noticeable at larger sizes. * src/smooth/ftgrays.c (gray_render_line): New implementation.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
diff --git a/ChangeLog b/ChangeLog
index f167eae..f076420 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,17 @@
+2015-10-01 Alexei Podtelezhnikov <apodtele@gmail.com>
+
+ [smooth] Faster alternative line renderer.
+
+ This implementation renders the entire line segment at once without
+ subdividing it into scanlines. The main speed improvement comes from
+ reducing the number of divisions to just two per line segment, which
+ is a bare minimum to calculate cell coverage in a smooth rasterizer.
+ Notably, the progression from cell to cell does not itself require any
+ divisions at all. The speed improvement is more noticeable at larger
+ sizes.
+
+ * src/smooth/ftgrays.c (gray_render_line): New implementation.
+
2015-10-06 Werner Lemberg <wl@gnu.org>
[cff] Return correct PS names from pure CFF (#46130).
diff --git a/src/smooth/ftgrays.c b/src/smooth/ftgrays.c
index ba29445..9a43c07 100644
--- a/src/smooth/ftgrays.c
+++ b/src/smooth/ftgrays.c
@@ -135,8 +135,10 @@
#include <string.h>
#include <setjmp.h>
#include <limits.h>
-#define FT_UINT_MAX UINT_MAX
-#define FT_INT_MAX INT_MAX
+#define FT_CHAR_BIT CHAR_BIT
+#define FT_UINT_MAX UINT_MAX
+#define FT_INT_MAX INT_MAX
+#define FT_ULONG_MAX ULONG_MAX
#define ft_memset memset
@@ -366,6 +368,15 @@ typedef ptrdiff_t FT_PtrDist;
#endif /* __arm__ */
+ /* These macros speed up repetitive divisions by replacing them */
+ /* with multiplications and right shifts. */
+#define FT_UDIVPREP( b ) \
+ long b ## _r = (long)( FT_ULONG_MAX >> PIXEL_BITS ) / ( b )
+#define FT_UDIV( a, b ) \
+ ( ( (unsigned long)( a ) * (unsigned long)( b ## _r ) ) >> \
+ ( sizeof( long ) * FT_CHAR_BIT - PIXEL_BITS ) )
+
+
/*************************************************************************/
/* */
/* TYPE DEFINITIONS */
@@ -678,6 +689,7 @@ typedef ptrdiff_t FT_PtrDist;
gray_set_cell( RAS_VAR_ ex, ey );
}
+#if 0
/*************************************************************************/
/* */
@@ -910,6 +922,143 @@ typedef ptrdiff_t FT_PtrDist;
ras.y = to_y;
}
+#else
+
+ /*************************************************************************/
+ /* */
+ /* Render a straight line across multiple cells in any direction. */
+ /* */
+ static void
+ gray_render_line( RAS_ARG_ TPos to_x,
+ TPos to_y )
+ {
+ TPos dx, dy, fx1, fy1, fx2, fy2;
+ TCoord ex1, ex2, ey1, ey2;
+
+
+ ex1 = TRUNC( ras.x );
+ ex2 = TRUNC( to_x );
+ ey1 = TRUNC( ras.y );
+ ey2 = TRUNC( to_y );
+
+ /* perform vertical clipping */
+ if ( ( ey1 >= ras.max_ey && ey2 >= ras.max_ey ) ||
+ ( ey1 < ras.min_ey && ey2 < ras.min_ey ) )
+ goto End;
+
+ dx = to_x - ras.x;
+ dy = to_y - ras.y;
+
+ fx1 = ras.x - SUBPIXELS( ex1 );
+ fy1 = ras.y - SUBPIXELS( ey1 );
+
+ if ( ex1 == ex2 && ey1 == ey2 ) /* inside one cell */
+ ;
+ else if ( dy == 0 ) /* ex1 != ex2 */ /* any horizontal line */
+ {
+ ex1 = ex2;
+ gray_set_cell( RAS_VAR_ ex1, ey1 );
+ }
+ else if ( dx == 0 )
+ {
+ if ( dy > 0 ) /* vertical line up */
+ do
+ {
+ fy2 = ONE_PIXEL;
+ ras.cover += ( fy2 - fy1 );
+ ras.area += ( fy2 - fy1 ) * fx1 * 2;
+ fy1 = 0;
+ ey1++;
+ gray_set_cell( RAS_VAR_ ex1, ey1 );
+ } while ( ey1 != ey2 );
+ else /* vertical line down */
+ do
+ {
+ fy2 = 0;
+ ras.cover += ( fy2 - fy1 );
+ ras.area += ( fy2 - fy1 ) * fx1 * 2;
+ fy1 = ONE_PIXEL;
+ ey1--;
+ gray_set_cell( RAS_VAR_ ex1, ey1 );
+ } while ( ey1 != ey2 );
+ }
+ else /* any other line */
+ {
+ TArea prod = dx * fy1 - dy * fx1;
+ FT_UDIVPREP( dx );
+ FT_UDIVPREP( dy );
+
+
+ /* The fundamental value `prod' determines which side and the */
+ /* exact coordinate where the line exits current cell. It is */
+ /* also easily updated when moving from one cell to the next. */
+ do
+ {
+ if ( prod <= 0 &&
+ prod - dx * ONE_PIXEL > 0 ) /* left */
+ {
+ fx2 = 0;
+ fy2 = (TPos)FT_UDIV( -prod, -dx );
+ prod -= dy * ONE_PIXEL;
+ ras.cover += ( fy2 - fy1 );
+ ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 );
+ fx1 = ONE_PIXEL;
+ fy1 = fy2;
+ ex1--;
+ }
+ else if ( prod - dx * ONE_PIXEL <= 0 &&
+ prod - dx * ONE_PIXEL + dy * ONE_PIXEL > 0 ) /* up */
+ {
+ prod -= dx * ONE_PIXEL;
+ fx2 = (TPos)FT_UDIV( -prod, dy );
+ fy2 = ONE_PIXEL;
+ ras.cover += ( fy2 - fy1 );
+ ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 );
+ fx1 = fx2;
+ fy1 = 0;
+ ey1++;
+ }
+ else if ( prod - dx * ONE_PIXEL + dy * ONE_PIXEL <= 0 &&
+ prod + dy * ONE_PIXEL >= 0 ) /* right */
+ {
+ prod += dy * ONE_PIXEL;
+ fx2 = ONE_PIXEL;
+ fy2 = (TPos)FT_UDIV( prod, dx );
+ ras.cover += ( fy2 - fy1 );
+ ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 );
+ fx1 = 0;
+ fy1 = fy2;
+ ex1++;
+ }
+ else /* ( prod + dy * ONE_PIXEL < 0 &&
+ prod > 0 ) down */
+ {
+ fx2 = (TPos)FT_UDIV( prod, -dy );
+ fy2 = 0;
+ prod += dx * ONE_PIXEL;
+ ras.cover += ( fy2 - fy1 );
+ ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 );
+ fx1 = fx2;
+ fy1 = ONE_PIXEL;
+ ey1--;
+ }
+
+ gray_set_cell( RAS_VAR_ ex1, ey1 );
+ } while ( ex1 != ex2 || ey1 != ey2 );
+ }
+
+ fx2 = to_x - SUBPIXELS( ex2 );
+ fy2 = to_y - SUBPIXELS( ey2 );
+
+ ras.cover += ( fy2 - fy1 );
+ ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 );
+
+ End:
+ ras.x = to_x;
+ ras.y = to_y;
+ }
+
+#endif
static void
gray_split_conic( FT_Vector* base )