Visualization Library 2.0.0-b5

A lightweight C++ OpenGL middleware for 2D/3D graphics

VL     Star     Watch     Fork     Issue

[Download] [Tutorials] [All Classes] [Grouped Classes]
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, 2007, 2011 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_UInt num_segments )
80  {
81  FT_Int idx_min, idx_max, idx0;
82  FT_UInt 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  xx1max = warper->x1max;
102  if ( xx1max + w > warper->x2max )
103  xx1max = warper->x2max - w;
104 
105  idx_min = xx1min - warper->t1;
106  idx_max = xx1max - warper->t1;
107 
108  if ( idx_min < 0 || idx_min > idx_max || idx_max > 64 )
109  {
110  FT_TRACE5(( "invalid indices:\n"
111  " min=%d max=%d, xx1=%ld xx2=%ld,\n"
112  " x1min=%ld x1max=%ld, x2min=%ld x2max=%ld\n",
113  idx_min, idx_max, xx1, xx2,
114  warper->x1min, warper->x1max,
115  warper->x2min, warper->x2max ));
116  return;
117  }
118  }
119 
120  for ( nn = 0; nn < num_segments; nn++ )
121  {
122  FT_Pos len = segments[nn].max_coord - segments[nn].min_coord;
123  FT_Pos y0 = FT_MulFix( segments[nn].pos, scale ) + delta;
124  FT_Pos y = y0 + ( idx_min - idx0 );
125  FT_Int idx;
126 
127 
128  /* score the length of the segments for the given range */
129  for ( idx = idx_min; idx <= idx_max; idx++, y++ )
130  scores[idx] += af_warper_weights[y & 63] * len;
131  }
132 
133  /* find best score */
134  {
135  FT_Int idx;
136 
137 
138  for ( idx = idx_min; idx <= idx_max; idx++ )
139  {
140  AF_WarpScore score = scores[idx];
141  AF_WarpScore distort = base_distort + ( idx - idx0 );
142 
143 
144  if ( score > warper->best_score ||
145  ( score == warper->best_score &&
146  distort < warper->best_distort ) )
147  {
148  warper->best_score = score;
149  warper->best_distort = distort;
150  warper->best_scale = scale;
151  warper->best_delta = delta + ( idx - idx0 );
152  }
153  }
154  }
155  }
156 
157 
158  /* Compute optimal scaling and delta values for a given glyph and */
159  /* dimension. */
160 
161  FT_LOCAL_DEF( void )
163  AF_GlyphHints hints,
164  AF_Dimension dim,
165  FT_Fixed *a_scale,
166  FT_Pos *a_delta )
167  {
168  AF_AxisHints axis;
170 
171  FT_Fixed org_scale;
172  FT_Pos org_delta;
173 
174  FT_UInt nn, num_points, num_segments;
175  FT_Int X1, X2;
176  FT_Int w;
177 
178  AF_WarpScore base_distort;
179  AF_Segment segments;
180 
181 
182  /* get original scaling transformation */
183  if ( dim == AF_DIMENSION_VERT )
184  {
185  org_scale = hints->y_scale;
186  org_delta = hints->y_delta;
187  }
188  else
189  {
190  org_scale = hints->x_scale;
191  org_delta = hints->x_delta;
192  }
193 
194  warper->best_scale = org_scale;
195  warper->best_delta = org_delta;
196  warper->best_score = INT_MIN;
197  warper->best_distort = 0;
198 
199  axis = &hints->axis[dim];
200  segments = axis->segments;
201  num_segments = axis->num_segments;
202  points = hints->points;
203  num_points = hints->num_points;
204 
205  *a_scale = org_scale;
206  *a_delta = org_delta;
207 
208  /* get X1 and X2, minimum and maximum in original coordinates */
209  if ( num_segments < 1 )
210  return;
211 
212 #if 1
213  X1 = X2 = points[0].fx;
214  for ( nn = 1; nn < num_points; nn++ )
215  {
216  FT_Int X = points[nn].fx;
217 
218 
219  if ( X < X1 )
220  X1 = X;
221  if ( X > X2 )
222  X2 = X;
223  }
224 #else
225  X1 = X2 = segments[0].pos;
226  for ( nn = 1; nn < num_segments; nn++ )
227  {
228  FT_Int X = segments[nn].pos;
229 
230 
231  if ( X < X1 )
232  X1 = X;
233  if ( X > X2 )
234  X2 = X;
235  }
236 #endif
237 
238  if ( X1 >= X2 )
239  return;
240 
241  warper->x1 = FT_MulFix( X1, org_scale ) + org_delta;
242  warper->x2 = FT_MulFix( X2, org_scale ) + org_delta;
243 
244  warper->t1 = AF_WARPER_FLOOR( warper->x1 );
245  warper->t2 = AF_WARPER_CEIL( warper->x2 );
246 
247  /* examine a half pixel wide range around the maximum coordinates */
248  warper->x1min = warper->x1 & ~31;
249  warper->x1max = warper->x1min + 32;
250  warper->x2min = warper->x2 & ~31;
251  warper->x2max = warper->x2min + 32;
252 
253  if ( warper->x1max > warper->x2 )
254  warper->x1max = warper->x2;
255 
256  if ( warper->x2min < warper->x1 )
257  warper->x2min = warper->x1;
258 
259  warper->w0 = warper->x2 - warper->x1;
260 
261  if ( warper->w0 <= 64 )
262  {
263  warper->x1max = warper->x1;
264  warper->x2min = warper->x2;
265  }
266 
267  /* examine (at most) a pixel wide range around the natural width */
268  warper->wmin = warper->x2min - warper->x1max;
269  warper->wmax = warper->x2max - warper->x1min;
270 
271 #if 1
272  /* some heuristics to reduce the number of widths to be examined */
273  {
274  int margin = 16;
275 
276 
277  if ( warper->w0 <= 128 )
278  {
279  margin = 8;
280  if ( warper->w0 <= 96 )
281  margin = 4;
282  }
283 
284  if ( warper->wmin < warper->w0 - margin )
285  warper->wmin = warper->w0 - margin;
286 
287  if ( warper->wmax > warper->w0 + margin )
288  warper->wmax = warper->w0 + margin;
289  }
290 
291  if ( warper->wmin < warper->w0 * 3 / 4 )
292  warper->wmin = warper->w0 * 3 / 4;
293 
294  if ( warper->wmax > warper->w0 * 5 / 4 )
295  warper->wmax = warper->w0 * 5 / 4;
296 #else
297  /* no scaling, just translation */
298  warper->wmin = warper->wmax = warper->w0;
299 #endif
300 
301  for ( w = warper->wmin; w <= warper->wmax; w++ )
302  {
303  FT_Fixed new_scale;
304  FT_Pos new_delta;
305  FT_Pos xx1, xx2;
306 
307 
308  /* compute min and max positions for given width, */
309  /* assuring that they stay within the coordinate ranges */
310  xx1 = warper->x1;
311  xx2 = warper->x2;
312  if ( w >= warper->w0 )
313  {
314  xx1 -= w - warper->w0;
315  if ( xx1 < warper->x1min )
316  {
317  xx2 += warper->x1min - xx1;
318  xx1 = warper->x1min;
319  }
320  }
321  else
322  {
323  xx1 -= w - warper->w0;
324  if ( xx1 > warper->x1max )
325  {
326  xx2 -= xx1 - warper->x1max;
327  xx1 = warper->x1max;
328  }
329  }
330 
331  if ( xx1 < warper->x1 )
332  base_distort = warper->x1 - xx1;
333  else
334  base_distort = xx1 - warper->x1;
335 
336  if ( xx2 < warper->x2 )
337  base_distort += warper->x2 - xx2;
338  else
339  base_distort += xx2 - warper->x2;
340 
341  /* give base distortion a greater weight while scoring */
342  base_distort *= 10;
343 
344  new_scale = org_scale + FT_DivFix( w - warper->w0, X2 - X1 );
345  new_delta = xx1 - FT_MulFix( X1, new_scale );
346 
347  af_warper_compute_line_best( warper, new_scale, new_delta, xx1, xx2,
348  base_distort,
349  segments, num_segments );
350  }
351 
352  {
353  FT_Fixed best_scale = warper->best_scale;
354  FT_Pos best_delta = warper->best_delta;
355 
356 
357  hints->xmin_delta = FT_MulFix( X1, best_scale - org_scale )
358  + best_delta;
359  hints->xmax_delta = FT_MulFix( X2, best_scale - org_scale )
360  + best_delta;
361 
362  *a_scale = best_scale;
363  *a_delta = best_delta;
364  }
365  }
366 
367 #else /* !AF_CONFIG_OPTION_USE_WARPER */
368 
369  /* ANSI C doesn't like empty source files */
370  typedef int _af_warp_dummy;
371 
372 #endif /* !AF_CONFIG_OPTION_USE_WARPER */
373 
374 /* END */
FT_Pos x1
Definition: afwarp.h:36
FT_DivFix(FT_Long a, FT_Long b)
Definition: ftcalc.c:586
FT_Short fx
Definition: afhints.h:257
GLenum GLenum GLenum GLenum GLenum scale
FT_BEGIN_HEADER typedef signed long FT_Pos
Definition: ftimage.h:59
GLsizei const GLfloat * points
FT_Pos xmax_delta
Definition: afhints.h:357
FT_Pos t1
Definition: afwarp.h:37
FT_Fixed y_scale
Definition: afhints.h:338
GLint GLint GLint GLint GLint GLint y
signed int FT_Int
Definition: fttypes.h:216
AF_Point points
Definition: afhints.h:343
png_infop png_charp png_int_32 png_int_32 * X1
Definition: png.h:2180
FT_Pos best_delta
Definition: afwarp.h:43
FT_Int num_segments
Definition: afhints.h:315
FT_Pos x1max
Definition: afwarp.h:38
FT_Pos wmax
Definition: afwarp.h:40
AF_WarpScore best_distort
Definition: afwarp.h:45
FT_Pos t2
Definition: afwarp.h:37
FT_Fixed best_scale
Definition: afwarp.h:42
int _af_warp_dummy
Definition: afwarp.c:370
FT_Pos x2min
Definition: afwarp.h:39
FT_Short min_coord
Definition: afhints.h:272
FT_Pos x_delta
Definition: afhints.h:336
FT_Short max_coord
Definition: afhints.h:273
FT_Int num_points
Definition: afhints.h:342
af_warper_compute(AF_Warper warper, AF_GlyphHints hints, AF_Dimension dim, FT_Fixed *a_scale, FT_Fixed *a_delta)
GLenum GLsizei len
FT_UInt idx
Definition: cffcmap.c:127
AF_Segment segments
Definition: afhints.h:317
FT_Int32 AF_WarpScore
Definition: afwarp.h:32
FT_Short pos
Definition: afhints.h:271
FT_Fixed x_scale
Definition: afhints.h:335
FT_Pos y_delta
Definition: afhints.h:339
FT_Pos x2max
Definition: afwarp.h:39
FT_Pos w0
Definition: afwarp.h:40
FT_Pos wmin
Definition: afwarp.h:40
FT_MulFix(FT_Long a, FT_Long b)
Definition: ftcalc.c:485
FT_BEGIN_HEADER enum AF_Dimension_ AF_Dimension
GLubyte GLubyte GLubyte GLubyte w
signed long FT_Fixed
Definition: fttypes.h:284
#define AF_WARPER_CEIL(x)
Definition: afwarp.h:29
unsigned int FT_UInt
Definition: fttypes.h:227
#define FT_TRACE5(varformat)
Definition: ftdebug.h:162
FT_Pos xmin_delta
Definition: afhints.h:356
AF_AxisHintsRec axis[AF_DIMENSION_MAX]
Definition: afhints.h:349
FT_Pos x1min
Definition: afwarp.h:38
AF_WarpScore best_score
Definition: afwarp.h:44
FT_Pos x2
Definition: afwarp.h:36
#define FT_LOCAL_DEF(x)
Definition: ftconfig.h:236
#define AF_WARPER_FLOOR(x)
Definition: afwarp.h:28