ReactOS  0.4.15-dev-1201-gb2cf5a4
afwarp.c
Go to the documentation of this file.
1 /***************************************************************************/
2 /* */
3 /* afwarp.c */
4 /* */
5 /* Auto-fitter warping algorithm (body). */
6 /* */
7 /* Copyright 2006-2018 by */
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */
9 /* */
10 /* This file is part of the FreeType project, and may only be used, */
11 /* modified, and distributed under the terms of the FreeType project */
12 /* license, LICENSE.TXT. By continuing to use, modify, or distribute */
13 /* this file you indicate that you have read the license and */
14 /* understand and accept it fully. */
15 /* */
16 /***************************************************************************/
17 
18 
19  /*
20  * The idea of the warping code is to slightly scale and shift a glyph
21  * within a single dimension so that as much of its segments are aligned
22  * (more or less) on the grid. To find out the optimal scaling and
23  * shifting value, various parameter combinations are tried and scored.
24  */
25 
26 #include "afwarp.h"
27 
28 #ifdef AF_CONFIG_OPTION_USE_WARPER
29 
30  /*************************************************************************/
31  /* */
32  /* The macro FT_COMPONENT is used in trace mode. It is an implicit */
33  /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
34  /* messages during execution. */
35  /* */
36 #undef FT_COMPONENT
37 #define FT_COMPONENT trace_afwarp
38 
39 
40  /* The weights cover the range 0/64 - 63/64 of a pixel. Obviously, */
41  /* values around a half pixel (which means exactly between two grid */
42  /* lines) gets the worst weight. */
43 #if 1
44  static const AF_WarpScore
45  af_warper_weights[64] =
46  {
47  35, 32, 30, 25, 20, 15, 12, 10, 5, 1, 0, 0, 0, 0, 0, 0,
48  0, 0, 0, 0, 0, 0, -1, -2, -5, -8,-10,-10,-20,-20,-30,-30,
49 
50  -30,-30,-20,-20,-10,-10, -8, -5, -2, -1, 0, 0, 0, 0, 0, 0,
51  0, 0, 0, 0, 0, 0, 0, 1, 5, 10, 12, 15, 20, 25, 30, 32,
52  };
53 #else
54  static const AF_WarpScore
55  af_warper_weights[64] =
56  {
57  30, 20, 10, 5, 4, 4, 3, 2, 1, 0, 0, 0, 0, 0, 0, 0,
58  0, 0, 0, 0, 0, 0, 0, -1, -2, -2, -5, -5,-10,-10,-15,-20,
59 
60  -20,-15,-15,-10,-10, -5, -5, -2, -2, -1, 0, 0, 0, 0, 0, 0,
61  0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 4, 5, 10, 20,
62  };
63 #endif
64 
65 
66  /* Score segments for a given `scale' and `delta' in the range */
67  /* `xx1' to `xx2', and store the best result in `warper'. If */
68  /* the new best score is equal to the old one, prefer the */
69  /* value with a smaller distortion (around `base_distort'). */
70 
71  static void
72  af_warper_compute_line_best( AF_Warper warper,
74  FT_Pos delta,
75  FT_Pos xx1,
76  FT_Pos xx2,
77  AF_WarpScore base_distort,
78  AF_Segment segments,
79  FT_Int num_segments )
80  {
81  FT_Int idx_min, idx_max, idx0;
82  FT_Int nn;
83  AF_WarpScore scores[65];
84 
85 
86  for ( nn = 0; nn < 65; nn++ )
87  scores[nn] = 0;
88 
89  idx0 = xx1 - warper->t1;
90 
91  /* compute minimum and maximum indices */
92  {
93  FT_Pos xx1min = warper->x1min;
94  FT_Pos xx1max = warper->x1max;
95  FT_Pos w = xx2 - xx1;
96 
97 
98  if ( xx1min + w < warper->x2min )
99  xx1min = warper->x2min - w;
100 
101  if ( xx1max + w > warper->x2max )
102  xx1max = warper->x2max - w;
103 
104  idx_min = xx1min - warper->t1;
105  idx_max = xx1max - warper->t1;
106 
107  if ( idx_min < 0 || idx_min > idx_max || idx_max > 64 )
108  {
109  FT_TRACE5(( "invalid indices:\n"
110  " min=%d max=%d, xx1=%ld xx2=%ld,\n"
111  " x1min=%ld x1max=%ld, x2min=%ld x2max=%ld\n",
112  idx_min, idx_max, xx1, xx2,
113  warper->x1min, warper->x1max,
114  warper->x2min, warper->x2max ));
115  return;
116  }
117  }
118 
119  for ( nn = 0; nn < num_segments; nn++ )
120  {
121  FT_Pos len = segments[nn].max_coord - segments[nn].min_coord;
122  FT_Pos y0 = FT_MulFix( segments[nn].pos, scale ) + delta;
123  FT_Pos y = y0 + ( idx_min - idx0 );
124  FT_Int idx;
125 
126 
127  /* score the length of the segments for the given range */
128  for ( idx = idx_min; idx <= idx_max; idx++, y++ )
129  scores[idx] += af_warper_weights[y & 63] * len;
130  }
131 
132  /* find best score */
133  {
134  FT_Int idx;
135 
136 
137  for ( idx = idx_min; idx <= idx_max; idx++ )
138  {
139  AF_WarpScore score = scores[idx];
140  AF_WarpScore distort = base_distort + ( idx - idx0 );
141 
142 
143  if ( score > warper->best_score ||
144  ( score == warper->best_score &&
145  distort < warper->best_distort ) )
146  {
147  warper->best_score = score;
148  warper->best_distort = distort;
149  warper->best_scale = scale;
150  warper->best_delta = delta + ( idx - idx0 );
151  }
152  }
153  }
154  }
155 
156 
157  /* Compute optimal scaling and delta values for a given glyph and */
158  /* dimension. */
159 
160  FT_LOCAL_DEF( void )
163  AF_Dimension dim,
164  FT_Fixed *a_scale,
165  FT_Pos *a_delta )
166  {
167  AF_AxisHints axis;
169 
170  FT_Fixed org_scale;
171  FT_Pos org_delta;
172 
173  FT_Int nn, num_points, num_segments;
174  FT_Int X1, X2;
175  FT_Int w;
176 
177  AF_WarpScore base_distort;
178  AF_Segment segments;
179 
180 
181  /* get original scaling transformation */
182  if ( dim == AF_DIMENSION_VERT )
183  {
184  org_scale = hints->y_scale;
185  org_delta = hints->y_delta;
186  }
187  else
188  {
189  org_scale = hints->x_scale;
190  org_delta = hints->x_delta;
191  }
192 
193  warper->best_scale = org_scale;
194  warper->best_delta = org_delta;
195  warper->best_score = FT_INT_MIN;
196  warper->best_distort = 0;
197 
198  axis = &hints->axis[dim];
199  segments = axis->segments;
200  num_segments = axis->num_segments;
201  points = hints->points;
202  num_points = hints->num_points;
203 
204  *a_scale = org_scale;
205  *a_delta = org_delta;
206 
207  /* get X1 and X2, minimum and maximum in original coordinates */
208  if ( num_segments < 1 )
209  return;
210 
211 #if 1
212  X1 = X2 = points[0].fx;
213  for ( nn = 1; nn < num_points; nn++ )
214  {
215  FT_Int X = points[nn].fx;
216 
217 
218  if ( X < X1 )
219  X1 = X;
220  if ( X > X2 )
221  X2 = X;
222  }
223 #else
224  X1 = X2 = segments[0].pos;
225  for ( nn = 1; nn < num_segments; nn++ )
226  {
227  FT_Int X = segments[nn].pos;
228 
229 
230  if ( X < X1 )
231  X1 = X;
232  if ( X > X2 )
233  X2 = X;
234  }
235 #endif
236 
237  if ( X1 >= X2 )
238  return;
239 
240  warper->x1 = FT_MulFix( X1, org_scale ) + org_delta;
241  warper->x2 = FT_MulFix( X2, org_scale ) + org_delta;
242 
243  warper->t1 = AF_WARPER_FLOOR( warper->x1 );
244  warper->t2 = AF_WARPER_CEIL( warper->x2 );
245 
246  /* examine a half pixel wide range around the maximum coordinates */
247  warper->x1min = warper->x1 & ~31;
248  warper->x1max = warper->x1min + 32;
249  warper->x2min = warper->x2 & ~31;
250  warper->x2max = warper->x2min + 32;
251 
252  if ( warper->x1max > warper->x2 )
253  warper->x1max = warper->x2;
254 
255  if ( warper->x2min < warper->x1 )
256  warper->x2min = warper->x1;
257 
258  warper->w0 = warper->x2 - warper->x1;
259 
260  if ( warper->w0 <= 64 )
261  {
262  warper->x1max = warper->x1;
263  warper->x2min = warper->x2;
264  }
265 
266  /* examine (at most) a pixel wide range around the natural width */
267  warper->wmin = warper->x2min - warper->x1max;
268  warper->wmax = warper->x2max - warper->x1min;
269 
270 #if 1
271  /* some heuristics to reduce the number of widths to be examined */
272  {
273  int margin = 16;
274 
275 
276  if ( warper->w0 <= 128 )
277  {
278  margin = 8;
279  if ( warper->w0 <= 96 )
280  margin = 4;
281  }
282 
283  if ( warper->wmin < warper->w0 - margin )
284  warper->wmin = warper->w0 - margin;
285 
286  if ( warper->wmax > warper->w0 + margin )
287  warper->wmax = warper->w0 + margin;
288  }
289 
290  if ( warper->wmin < warper->w0 * 3 / 4 )
291  warper->wmin = warper->w0 * 3 / 4;
292 
293  if ( warper->wmax > warper->w0 * 5 / 4 )
294  warper->wmax = warper->w0 * 5 / 4;
295 #else
296  /* no scaling, just translation */
297  warper->wmin = warper->wmax = warper->w0;
298 #endif
299 
300  for ( w = warper->wmin; w <= warper->wmax; w++ )
301  {
302  FT_Fixed new_scale;
303  FT_Pos new_delta;
304  FT_Pos xx1, xx2;
305 
306 
307  /* compute min and max positions for given width, */
308  /* assuring that they stay within the coordinate ranges */
309  xx1 = warper->x1;
310  xx2 = warper->x2;
311  if ( w >= warper->w0 )
312  {
313  xx1 -= w - warper->w0;
314  if ( xx1 < warper->x1min )
315  {
316  xx2 += warper->x1min - xx1;
317  xx1 = warper->x1min;
318  }
319  }
320  else
321  {
322  xx1 -= w - warper->w0;
323  if ( xx1 > warper->x1max )
324  {
325  xx2 -= xx1 - warper->x1max;
326  xx1 = warper->x1max;
327  }
328  }
329 
330  if ( xx1 < warper->x1 )
331  base_distort = warper->x1 - xx1;
332  else
333  base_distort = xx1 - warper->x1;
334 
335  if ( xx2 < warper->x2 )
336  base_distort += warper->x2 - xx2;
337  else
338  base_distort += xx2 - warper->x2;
339 
340  /* give base distortion a greater weight while scoring */
341  base_distort *= 10;
342 
343  new_scale = org_scale + FT_DivFix( w - warper->w0, X2 - X1 );
344  new_delta = xx1 - FT_MulFix( X1, new_scale );
345 
346  af_warper_compute_line_best( warper, new_scale, new_delta, xx1, xx2,
347  base_distort,
348  segments, num_segments );
349  }
350 
351  {
352  FT_Fixed best_scale = warper->best_scale;
353  FT_Pos best_delta = warper->best_delta;
354 
355 
356  hints->xmin_delta = FT_MulFix( X1, best_scale - org_scale )
357  + best_delta;
358  hints->xmax_delta = FT_MulFix( X2, best_scale - org_scale )
359  + best_delta;
360 
361  *a_scale = best_scale;
362  *a_delta = best_delta;
363  }
364  }
365 
366 #else /* !AF_CONFIG_OPTION_USE_WARPER */
367 
368  /* ANSI C doesn't like empty source files */
369  typedef int _af_warp_dummy;
370 
371 #endif /* !AF_CONFIG_OPTION_USE_WARPER */
372 
373 /* END */
namespace GUID const ADDRINFOEXW * hints
Definition: sock.c:80
FT_DivFix(FT_Long a, FT_Long b)
Definition: ftcalc.c:608
GLubyte GLubyte GLubyte GLubyte w
Definition: glext.h:6102
FT_BEGIN_HEADER typedef signed long FT_Pos
Definition: ftimage.h:58
signed int FT_Int
Definition: fttypes.h:220
FT_Short min_coord
Definition: afhints.h:264
GLenum GLenum GLenum GLenum GLenum scale
Definition: glext.h:9032
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG x1
Definition: winddi.h:3706
FT_Pos x1max
Definition: afwarp.h:38
FT_Short max_coord
Definition: afhints.h:265
FT_Pos t1
Definition: afwarp.h:37
FT_Pos x2max
Definition: afwarp.h:39
int _af_warp_dummy
Definition: afwarp.c:369
unsigned int idx
Definition: utils.c:41
af_warper_compute(AF_Warper warper, AF_GlyphHints hints, AF_Dimension dim, FT_Fixed *a_scale, FT_Fixed *a_delta)
FT_Pos w0
Definition: afwarp.h:40
#define FT_LOCAL_DEF(x)
Definition: ftconfig.h:388
FT_Int32 AF_WarpScore
Definition: afwarp.h:32
#define FT_INT_MIN
Definition: ftstdlib.h:64
FT_Pos x1min
Definition: afwarp.h:38
FT_Pos t2
Definition: afwarp.h:37
AF_Segment segments
Definition: afhints.h:309
GLsizei const GLfloat * points
Definition: glext.h:8112
FT_Pos x2min
Definition: afwarp.h:39
GLenum GLsizei len
Definition: glext.h:6722
FT_Pos x1
Definition: afwarp.h:36
FT_Int num_segments
Definition: afhints.h:307
FT_MulFix(FT_Long a, FT_Long b)
Definition: ftcalc.c:509
FT_Short pos
Definition: afhints.h:262
FT_Pos wmin
Definition: afwarp.h:40
FT_BEGIN_HEADER enum AF_Dimension_ AF_Dimension
signed long FT_Fixed
Definition: fttypes.h:288
#define AF_WARPER_CEIL(x)
Definition: afwarp.h:29
GLint y0
Definition: linetemp.h:96
FT_Pos x2
Definition: afwarp.h:36
FT_Pos best_delta
Definition: afwarp.h:43
#define FT_TRACE5(varformat)
Definition: ftdebug.h:162
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG _In_ LONG x2
Definition: winddi.h:3706
AF_WarpScore best_score
Definition: afwarp.h:44
FT_Fixed best_scale
Definition: afwarp.h:42
FT_Pos wmax
Definition: afwarp.h:40
#define X2(f, ord)
#define X(b, s)
AF_WarpScore best_distort
Definition: afwarp.h:45
#define AF_WARPER_FLOOR(x)
Definition: afwarp.h:28