Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(187)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: third_party/freetype/src/base/ftbbox.c

Issue 815103002: Update freetype to 2.5.4. (Closed) Base URL: https://pdfium.googlesource.com/pdfium.git@master
Patch Set: Adjust GYP and GN Created 6 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « third_party/freetype/src/base/ftbase.c ('k') | third_party/freetype/src/base/ftbdf.c » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /***************************************************************************/ 1 /***************************************************************************/
2 /* */ 2 /* */
3 /* ftbbox.c */ 3 /* ftbbox.c */
4 /* */ 4 /* */
5 /* FreeType bbox computation (body). */ 5 /* FreeType bbox computation (body). */
6 /* */ 6 /* */
7 /* Copyright 1996-2002, 2004, 2006, 2010, 2013 by */ 7 /* Copyright 1996-2002, 2004, 2006, 2010, 2013, 2014 by */
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */ 8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */
9 /* */ 9 /* */
10 /* This file is part of the FreeType project, and may only be used */ 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 */ 11 /* modified and distributed under the terms of the FreeType project */
12 /* license, LICENSE.TXT. By continuing to use, modify, or distribute */ 12 /* license, LICENSE.TXT. By continuing to use, modify, or distribute */
13 /* this file you indicate that you have read the license and */ 13 /* this file you indicate that you have read the license and */
14 /* understand and accept it fully. */ 14 /* understand and accept it fully. */
15 /* */ 15 /* */
16 /***************************************************************************/ 16 /***************************************************************************/
17 17
18 18
19 /*************************************************************************/ 19 /*************************************************************************/
20 /* */ 20 /* */
21 /* This component has a _single_ role: to compute exact outline bounding */ 21 /* This component has a _single_ role: to compute exact outline bounding */
22 /* boxes. */ 22 /* boxes. */
23 /* */ 23 /* */
24 /*************************************************************************/ 24 /*************************************************************************/
25 25
26 26
27 #include "../../include/ft2build.h" 27 #include <ft2build.h>
28 #include "../../include/freetype/internal/ftdebug.h" 28 #include FT_INTERNAL_DEBUG_H
29 29
30 #include "../../include/freetype/ftbbox.h" 30 #include FT_BBOX_H
31 #include "../../include/freetype/ftimage.h" 31 #include FT_IMAGE_H
32 #include "../../include/freetype/ftoutln.h" 32 #include FT_OUTLINE_H
33 #include "../../include/freetype/internal/ftcalc.h" 33 #include FT_INTERNAL_CALC_H
34 #include "../../include/freetype/internal/ftobjs.h" 34 #include FT_INTERNAL_OBJECTS_H
35 35
36 36
37 typedef struct TBBox_Rec_ 37 typedef struct TBBox_Rec_
38 { 38 {
39 FT_Vector last; 39 FT_Vector last;
40 FT_BBox bbox; 40 FT_BBox bbox;
41 41
42 } TBBox_Rec; 42 } TBBox_Rec;
43 43
44 44
45 #define FT_UPDATE_BBOX(p, bbox) \
46 FT_BEGIN_STMNT \
47 if ( p->x < bbox.xMin ) \
48 bbox.xMin = p->x; \
49 if ( p->x > bbox.xMax ) \
50 bbox.xMax = p->x; \
51 if ( p->y < bbox.yMin ) \
52 bbox.yMin = p->y; \
53 if ( p->y > bbox.yMax ) \
54 bbox.yMax = p->y; \
55 FT_END_STMNT
56
57 #define CHECK_X( p, bbox ) \
58 ( p->x < bbox.xMin || p->x > bbox.xMax )
59
60 #define CHECK_Y( p, bbox ) \
61 ( p->y < bbox.yMin || p->y > bbox.yMax )
62
63
45 /*************************************************************************/ 64 /*************************************************************************/
46 /* */ 65 /* */
47 /* <Function> */ 66 /* <Function> */
48 /* BBox_Move_To */ 67 /* BBox_Move_To */
49 /* */ 68 /* */
50 /* <Description> */ 69 /* <Description> */
51 /* This function is used as a `move_to' and `line_to' emitter during */ 70 /* This function is used as a `move_to' emitter during */
52 /* FT_Outline_Decompose(). It simply records the destination point */ 71 /* FT_Outline_Decompose(). It simply records the destination point */
53 /* in `user->last'; no further computations are necessary since we */ 72 /* in `user->last'. We also update bbox in case contour starts with */
54 /* use the cbox as the starting bbox which must be refined. */ 73 /* an implicit `on' point. */
55 /* */ 74 /* */
56 /* <Input> */ 75 /* <Input> */
57 /* to :: A pointer to the destination vector. */ 76 /* to :: A pointer to the destination vector. */
58 /* */ 77 /* */
59 /* <InOut> */ 78 /* <InOut> */
60 /* user :: A pointer to the current walk context. */ 79 /* user :: A pointer to the current walk context. */
61 /* */ 80 /* */
62 /* <Return> */ 81 /* <Return> */
63 /* Always 0. Needed for the interface only. */ 82 /* Always 0. Needed for the interface only. */
64 /* */ 83 /* */
65 static int 84 static int
66 BBox_Move_To( FT_Vector* to, 85 BBox_Move_To( FT_Vector* to,
67 TBBox_Rec* user ) 86 TBBox_Rec* user )
68 { 87 {
88 FT_UPDATE_BBOX( to, user->bbox );
89
90 user->last = *to;
91
92 return 0;
93 }
94
95
96 /*************************************************************************/
97 /* */
98 /* <Function> */
99 /* BBox_Line_To */
100 /* */
101 /* <Description> */
102 /* This function is used as a `line_to' emitter during */
103 /* FT_Outline_Decompose(). It simply records the destination point */
104 /* in `user->last'; no further computations are necessary because */
105 /* bbox already contains both explicit ends of the line segment. */
106 /* */
107 /* <Input> */
108 /* to :: A pointer to the destination vector. */
109 /* */
110 /* <InOut> */
111 /* user :: A pointer to the current walk context. */
112 /* */
113 /* <Return> */
114 /* Always 0. Needed for the interface only. */
115 /* */
116 static int
117 BBox_Line_To( FT_Vector* to,
118 TBBox_Rec* user )
119 {
69 user->last = *to; 120 user->last = *to;
70 121
71 return 0; 122 return 0;
72 } 123 }
73 124
74 125
75 #define CHECK_X( p, bbox ) \
76 ( p->x < bbox.xMin || p->x > bbox.xMax )
77
78 #define CHECK_Y( p, bbox ) \
79 ( p->y < bbox.yMin || p->y > bbox.yMax )
80
81
82 /*************************************************************************/ 126 /*************************************************************************/
83 /* */ 127 /* */
84 /* <Function> */ 128 /* <Function> */
85 /* BBox_Conic_Check */ 129 /* BBox_Conic_Check */
86 /* */ 130 /* */
87 /* <Description> */ 131 /* <Description> */
88 /* Finds the extrema of a 1-dimensional conic Bezier curve and update */ 132 /* Find the extrema of a 1-dimensional conic Bezier curve and update */
89 /* a bounding range. This version uses direct computation, as it */ 133 /* a bounding range. This version uses direct computation, as it */
90 /* doesn't need square roots. */ 134 /* doesn't need square roots. */
91 /* */ 135 /* */
92 /* <Input> */ 136 /* <Input> */
93 /* y1 :: The start coordinate. */ 137 /* y1 :: The start coordinate. */
94 /* */ 138 /* */
95 /* y2 :: The coordinate of the control point. */ 139 /* y2 :: The coordinate of the control point. */
96 /* */ 140 /* */
97 /* y3 :: The end coordinate. */ 141 /* y3 :: The end coordinate. */
98 /* */ 142 /* */
99 /* <InOut> */ 143 /* <InOut> */
100 /* min :: The address of the current minimum. */ 144 /* min :: The address of the current minimum. */
101 /* */ 145 /* */
102 /* max :: The address of the current maximum. */ 146 /* max :: The address of the current maximum. */
103 /* */ 147 /* */
104 static void 148 static void
105 BBox_Conic_Check( FT_Pos y1, 149 BBox_Conic_Check( FT_Pos y1,
106 FT_Pos y2, 150 FT_Pos y2,
107 FT_Pos y3, 151 FT_Pos y3,
108 FT_Pos* min, 152 FT_Pos* min,
109 FT_Pos* max ) 153 FT_Pos* max )
110 { 154 {
111 if ( y1 <= y3 && y2 == y1 ) /* flat arc */ 155 /* This function is only called when a control off-point is outside */
112 goto Suite; 156 /* the bbox that contains all on-points. It finds a local extremum */
157 /* within the segment, equal to (y1*y3 - y2*y2)/(y1 - 2*y2 + y3). */
158 /* Or, offsetting from y2, we get */
113 159
114 if ( y1 < y3 ) 160 y1 -= y2;
115 { 161 y3 -= y2;
116 if ( y2 >= y1 && y2 <= y3 ) /* ascending arc */ 162 y2 += FT_MulDiv( y1, y3, y1 + y3 );
117 goto Suite;
118 }
119 else
120 {
121 if ( y2 >= y3 && y2 <= y1 ) /* descending arc */
122 {
123 y2 = y1;
124 y1 = y3;
125 y3 = y2;
126 goto Suite;
127 }
128 }
129 163
130 y1 = y3 = y1 - FT_MulDiv( y2 - y1, y2 - y1, y1 - 2*y2 + y3 ); 164 if ( y2 < *min )
131 165 *min = y2;
132 Suite: 166 if ( y2 > *max )
133 if ( y1 < *min ) *min = y1; 167 *max = y2;
134 if ( y3 > *max ) *max = y3;
135 } 168 }
136 169
137 170
138 /*************************************************************************/ 171 /*************************************************************************/
139 /* */ 172 /* */
140 /* <Function> */ 173 /* <Function> */
141 /* BBox_Conic_To */ 174 /* BBox_Conic_To */
142 /* */ 175 /* */
143 /* <Description> */ 176 /* <Description> */
144 /* This function is used as a `conic_to' emitter during */ 177 /* This function is used as a `conic_to' emitter during */
(...skipping 14 matching lines...) Expand all
159 /* */ 192 /* */
160 /* <Note> */ 193 /* <Note> */
161 /* In the case of a non-monotonous arc, we compute directly the */ 194 /* In the case of a non-monotonous arc, we compute directly the */
162 /* extremum coordinates, as it is sufficiently fast. */ 195 /* extremum coordinates, as it is sufficiently fast. */
163 /* */ 196 /* */
164 static int 197 static int
165 BBox_Conic_To( FT_Vector* control, 198 BBox_Conic_To( FT_Vector* control,
166 FT_Vector* to, 199 FT_Vector* to,
167 TBBox_Rec* user ) 200 TBBox_Rec* user )
168 { 201 {
169 /* we don't need to check `to' since it is always an `on' point, thus */ 202 /* in case `to' is implicit and not included in bbox yet */
170 /* within the bbox */ 203 FT_UPDATE_BBOX( to, user->bbox );
171 204
172 if ( CHECK_X( control, user->bbox ) ) 205 if ( CHECK_X( control, user->bbox ) )
173 BBox_Conic_Check( user->last.x, 206 BBox_Conic_Check( user->last.x,
174 control->x, 207 control->x,
175 to->x, 208 to->x,
176 &user->bbox.xMin, 209 &user->bbox.xMin,
177 &user->bbox.xMax ); 210 &user->bbox.xMax );
178 211
179 if ( CHECK_Y( control, user->bbox ) ) 212 if ( CHECK_Y( control, user->bbox ) )
180 BBox_Conic_Check( user->last.y, 213 BBox_Conic_Check( user->last.y,
181 control->y, 214 control->y,
182 to->y, 215 to->y,
183 &user->bbox.yMin, 216 &user->bbox.yMin,
184 &user->bbox.yMax ); 217 &user->bbox.yMax );
185 218
186 user->last = *to; 219 user->last = *to;
187 220
188 return 0; 221 return 0;
189 } 222 }
190 223
191 224
192 /*************************************************************************/ 225 /*************************************************************************/
193 /* */ 226 /* */
194 /* <Function> */ 227 /* <Function> */
195 /* BBox_Cubic_Check */ 228 /* BBox_Cubic_Check */
196 /* */ 229 /* */
197 /* <Description> */ 230 /* <Description> */
198 /* Finds the extrema of a 1-dimensional cubic Bezier curve and */ 231 /* Find the extrema of a 1-dimensional cubic Bezier curve and */
199 /* updates a bounding range. This version uses splitting because we */ 232 /* update a bounding range. This version uses iterative splitting */
200 /* don't want to use square roots and extra accuracy. */ 233 /* because it is faster than the exact solution with square roots. */
201 /* */ 234 /* */
202 /* <Input> */ 235 /* <Input> */
203 /* p1 :: The start coordinate. */ 236 /* p1 :: The start coordinate. */
204 /* */ 237 /* */
205 /* p2 :: The coordinate of the first control point. */ 238 /* p2 :: The coordinate of the first control point. */
206 /* */ 239 /* */
207 /* p3 :: The coordinate of the second control point. */ 240 /* p3 :: The coordinate of the second control point. */
208 /* */ 241 /* */
209 /* p4 :: The end coordinate. */ 242 /* p4 :: The end coordinate. */
210 /* */ 243 /* */
211 /* <InOut> */ 244 /* <InOut> */
212 /* min :: The address of the current minimum. */ 245 /* min :: The address of the current minimum. */
213 /* */ 246 /* */
214 /* max :: The address of the current maximum. */ 247 /* max :: The address of the current maximum. */
215 /* */ 248 /* */
249 static FT_Pos
250 cubic_peak( FT_Pos q1,
251 FT_Pos q2,
252 FT_Pos q3,
253 FT_Pos q4 )
254 {
255 FT_Pos peak = 0;
256 FT_Int shift;
216 257
217 #if 0 258 /* This function finds a peak of a cubic segment if it is above 0 */
259 /* using iterative bisection of the segment, or returns 0. */
260 /* The fixed-point arithmetic of bisection is inherently stable */
261 /* but may loose accuracy in the two lowest bits. To compensate, */
262 /* we upscale the segment if there is room. Large values may need */
263 /* to be downscaled to avoid overflows during bisection. */
264 /* It is called with either q2 or q3 positive, which is necessary */
265 /* for the peak to exist and avoids undefined FT_MSB. */
218 266
219 static void 267 shift = 27 -
220 BBox_Cubic_Check( FT_Pos p1, 268 FT_MSB( FT_ABS( q1 ) | FT_ABS( q2 ) | FT_ABS( q3 ) | FT_ABS( q4 ) );
221 FT_Pos p2,
222 FT_Pos p3,
223 FT_Pos p4,
224 FT_Pos* min,
225 FT_Pos* max )
226 {
227 FT_Pos q1, q2, q3, q4;
228 269
270 if ( shift > 0 )
271 {
272 /* upscaling too much just wastes time */
273 if ( shift > 2 )
274 shift = 2;
229 275
230 q1 = p1; 276 q1 <<= shift;
231 q2 = p2; 277 q2 <<= shift;
232 q3 = p3; 278 q3 <<= shift;
233 q4 = p4; 279 q4 <<= shift;
280 }
281 else
282 {
283 q1 >>= -shift;
284 q2 >>= -shift;
285 q3 >>= -shift;
286 q4 >>= -shift;
287 }
234 288
235 /* for a conic segment to possibly reach new maximum */ 289 /* for a peak to exist above 0, the cubic segment must have */
236 /* one of its off-points must be above the current value */ 290 /* at least one of its control off-points above 0. */
237 while ( q2 > *max || q3 > *max ) 291 while ( q2 > 0 || q3 > 0 )
238 { 292 {
239 /* determine which half contains the maximum and split */ 293 /* determine which half contains the maximum and split */
240 if ( q1 + q2 > q3 + q4 ) /* first half */ 294 if ( q1 + q2 > q3 + q4 ) /* first half */
241 { 295 {
242 q4 = q4 + q3; 296 q4 = q4 + q3;
243 q3 = q3 + q2; 297 q3 = q3 + q2;
244 q2 = q2 + q1; 298 q2 = q2 + q1;
245 q4 = q4 + q3; 299 q4 = q4 + q3;
246 q3 = q3 + q2; 300 q3 = q3 + q2;
247 q4 = ( q4 + q3 ) / 8; 301 q4 = ( q4 + q3 ) / 8;
248 q3 = q3 / 4; 302 q3 = q3 / 4;
249 q2 = q2 / 2; 303 q2 = q2 / 2;
250 } 304 }
251 else /* second half */ 305 else /* second half */
252 { 306 {
253 q1 = q1 + q2; 307 q1 = q1 + q2;
254 q2 = q2 + q3; 308 q2 = q2 + q3;
255 q3 = q3 + q4; 309 q3 = q3 + q4;
256 q1 = q1 + q2; 310 q1 = q1 + q2;
257 q2 = q2 + q3; 311 q2 = q2 + q3;
258 q1 = ( q1 + q2 ) / 8; 312 q1 = ( q1 + q2 ) / 8;
259 q2 = q2 / 4; 313 q2 = q2 / 4;
260 q3 = q3 / 2; 314 q3 = q3 / 2;
261 } 315 }
262 316
263 /* check if either end reached the maximum */ 317 /* check whether either end reached the maximum */
264 if ( q1 == q2 && q1 >= q3 ) 318 if ( q1 == q2 && q1 >= q3 )
265 { 319 {
266 *max = q1; 320 peak = q1;
267 break; 321 break;
268 } 322 }
269 if ( q3 == q4 && q2 <= q4 ) 323 if ( q3 == q4 && q2 <= q4 )
270 { 324 {
271 *max = q4; 325 peak = q4;
272 break; 326 break;
273 } 327 }
274 } 328 }
275 329
276 q1 = p1; 330 if ( shift > 0 )
277 q2 = p2; 331 peak >>= shift;
278 q3 = p3; 332 else
279 q4 = p4; 333 peak <<= -shift;
280 334
281 /* for a conic segment to possibly reach new minimum */ 335 return peak;
282 /* one of its off-points must be below the current value */
283 while ( q2 < *min || q3 < *min )
284 {
285 /* determine which half contains the minimum and split */
286 if ( q1 + q2 < q3 + q4 ) /* first half */
287 {
288 q4 = q4 + q3;
289 q3 = q3 + q2;
290 q2 = q2 + q1;
291 q4 = q4 + q3;
292 q3 = q3 + q2;
293 q4 = ( q4 + q3 ) / 8;
294 q3 = q3 / 4;
295 q2 = q2 / 2;
296 }
297 else /* second half */
298 {
299 q1 = q1 + q2;
300 q2 = q2 + q3;
301 q3 = q3 + q4;
302 q1 = q1 + q2;
303 q2 = q2 + q3;
304 q1 = ( q1 + q2 ) / 8;
305 q2 = q2 / 4;
306 q3 = q3 / 2;
307 }
308
309 /* check if either end reached the minimum */
310 if ( q1 == q2 && q1 <= q3 )
311 {
312 *min = q1;
313 break;
314 }
315 if ( q3 == q4 && q2 >= q4 )
316 {
317 *min = q4;
318 break;
319 }
320 }
321 }
322
323 #else
324
325 static void
326 test_cubic_extrema( FT_Pos y1,
327 FT_Pos y2,
328 FT_Pos y3,
329 FT_Pos y4,
330 FT_Fixed u,
331 FT_Pos* min,
332 FT_Pos* max )
333 {
334 /* FT_Pos a = y4 - 3*y3 + 3*y2 - y1; */
335 FT_Pos b = y3 - 2*y2 + y1;
336 FT_Pos c = y2 - y1;
337 FT_Pos d = y1;
338 FT_Pos y;
339 FT_Fixed uu;
340
341 FT_UNUSED ( y4 );
342
343
344 /* The polynomial is */
345 /* */
346 /* P(x) = a*x^3 + 3b*x^2 + 3c*x + d , */
347 /* */
348 /* dP/dx = 3a*x^2 + 6b*x + 3c . */
349 /* */
350 /* However, we also have */
351 /* */
352 /* dP/dx(u) = 0 , */
353 /* */
354 /* which implies by subtraction that */
355 /* */
356 /* P(u) = b*u^2 + 2c*u + d . */
357
358 if ( u > 0 && u < 0x10000L )
359 {
360 uu = FT_MulFix( u, u );
361 y = d + FT_MulFix( c, 2*u ) + FT_MulFix( b, uu );
362
363 if ( y < *min ) *min = y;
364 if ( y > *max ) *max = y;
365 }
366 } 336 }
367 337
368 338
369 static void 339 static void
370 BBox_Cubic_Check( FT_Pos y1, 340 BBox_Cubic_Check( FT_Pos p1,
371 FT_Pos y2, 341 FT_Pos p2,
372 FT_Pos y3, 342 FT_Pos p3,
373 FT_Pos y4, 343 FT_Pos p4,
374 FT_Pos* min, 344 FT_Pos* min,
375 FT_Pos* max ) 345 FT_Pos* max )
376 { 346 {
377 /* always compare first and last points */ 347 /* This function is only called when a control off-point is outside */
378 if ( y1 < *min ) *min = y1; 348 /* the bbox that contains all on-points. So at least one of the */
379 else if ( y1 > *max ) *max = y1; 349 /* conditions below holds and cubic_peak is called with at least one */
350 /* non-zero argument. */
380 351
381 if ( y4 < *min ) *min = y4; 352 if ( p2 > *max || p3 > *max )
382 else if ( y4 > *max ) *max = y4; 353 *max += cubic_peak( p1 - *max, p2 - *max, p3 - *max, p4 - *max );
383 354
384 /* now, try to see if there are split points here */ 355 /* now flip the signs to update the minimum */
385 if ( y1 <= y4 ) 356 if ( p2 < *min || p3 < *min )
386 { 357 *min -= cubic_peak( *min - p1, *min - p2, *min - p3, *min - p4 );
387 /* flat or ascending arc test */
388 if ( y1 <= y2 && y2 <= y4 && y1 <= y3 && y3 <= y4 )
389 return;
390 }
391 else /* y1 > y4 */
392 {
393 /* descending arc test */
394 if ( y1 >= y2 && y2 >= y4 && y1 >= y3 && y3 >= y4 )
395 return;
396 }
397
398 /* There are some split points. Find them. */
399 /* We already made sure that a, b, and c below cannot be all zero. */
400 {
401 FT_Pos a = y4 - 3*y3 + 3*y2 - y1;
402 FT_Pos b = y3 - 2*y2 + y1;
403 FT_Pos c = y2 - y1;
404 FT_Pos d;
405 FT_Fixed t;
406 FT_Int shift;
407
408
409 /* We need to solve `ax^2+2bx+c' here, without floating points! */
410 /* The trick is to normalize to a different representation in order */
411 /* to use our 16.16 fixed-point routines. */
412 /* */
413 /* We compute FT_MulFix(b,b) and FT_MulFix(a,c) after normalization. */
414 /* These values must fit into a single 16.16 value. */
415 /* */
416 /* We normalize a, b, and c to `8.16' fixed-point values to ensure */
417 /* that their product is held in a `16.16' value including the sign. */
418 /* Necessarily, we need to shift `a', `b', and `c' so that the most */
419 /* significant bit of their absolute values is at position 22. */
420 /* */
421 /* This also means that we are using 23 bits of precision to compute */
422 /* the zeros, independently of the range of the original polynomial */
423 /* coefficients. */
424 /* */
425 /* This algorithm should ensure reasonably accurate values for the */
426 /* zeros. Note that they are only expressed with 16 bits when */
427 /* computing the extrema (the zeros need to be in 0..1 exclusive */
428 /* to be considered part of the arc). */
429
430 shift = FT_MSB( FT_ABS( a ) | FT_ABS( b ) | FT_ABS( c ) );
431
432 if ( shift > 22 )
433 {
434 shift -= 22;
435
436 /* this loses some bits of precision, but we use 23 of them */
437 /* for the computation anyway */
438 a >>= shift;
439 b >>= shift;
440 c >>= shift;
441 }
442 else
443 {
444 shift = 22 - shift;
445
446 a <<= shift;
447 b <<= shift;
448 c <<= shift;
449 }
450
451 /* handle a == 0 */
452 if ( a == 0 )
453 {
454 if ( b != 0 )
455 {
456 t = - FT_DivFix( c, b ) / 2;
457 test_cubic_extrema( y1, y2, y3, y4, t, min, max );
458 }
459 }
460 else
461 {
462 /* solve the equation now */
463 d = FT_MulFix( b, b ) - FT_MulFix( a, c );
464 if ( d < 0 )
465 return;
466
467 if ( d == 0 )
468 {
469 /* there is a single split point at -b/a */
470 t = - FT_DivFix( b, a );
471 test_cubic_extrema( y1, y2, y3, y4, t, min, max );
472 }
473 else
474 {
475 /* there are two solutions; we need to filter them */
476 d = FT_SqrtFixed( (FT_Int32)d );
477 t = - FT_DivFix( b - d, a );
478 test_cubic_extrema( y1, y2, y3, y4, t, min, max );
479
480 t = - FT_DivFix( b + d, a );
481 test_cubic_extrema( y1, y2, y3, y4, t, min, max );
482 }
483 }
484 }
485 } 358 }
486 359
487 #endif
488
489 360
490 /*************************************************************************/ 361 /*************************************************************************/
491 /* */ 362 /* */
492 /* <Function> */ 363 /* <Function> */
493 /* BBox_Cubic_To */ 364 /* BBox_Cubic_To */
494 /* */ 365 /* */
495 /* <Description> */ 366 /* <Description> */
496 /* This function is used as a `cubic_to' emitter during */ 367 /* This function is used as a `cubic_to' emitter during */
497 /* FT_Outline_Decompose(). It checks a cubic Bezier curve with the */ 368 /* FT_Outline_Decompose(). It checks a cubic Bezier curve with the */
498 /* current bounding box, and computes its extrema if necessary to */ 369 /* current bounding box, and computes its extrema if necessary to */
(...skipping 15 matching lines...) Expand all
514 /* <Note> */ 385 /* <Note> */
515 /* In the case of a non-monotonous arc, we don't compute directly */ 386 /* In the case of a non-monotonous arc, we don't compute directly */
516 /* extremum coordinates, we subdivide instead. */ 387 /* extremum coordinates, we subdivide instead. */
517 /* */ 388 /* */
518 static int 389 static int
519 BBox_Cubic_To( FT_Vector* control1, 390 BBox_Cubic_To( FT_Vector* control1,
520 FT_Vector* control2, 391 FT_Vector* control2,
521 FT_Vector* to, 392 FT_Vector* to,
522 TBBox_Rec* user ) 393 TBBox_Rec* user )
523 { 394 {
524 /* we don't need to check `to' since it is always an `on' point, thus */ 395 /* We don't need to check `to' since it is always an on-point, */
525 /* within the bbox */ 396 /* thus within the bbox. Only segments with an off-point outside */
397 /* the bbox can possibly reach new extreme values. */
526 398
527 if ( CHECK_X( control1, user->bbox ) || 399 if ( CHECK_X( control1, user->bbox ) ||
528 CHECK_X( control2, user->bbox ) ) 400 CHECK_X( control2, user->bbox ) )
529 BBox_Cubic_Check( user->last.x, 401 BBox_Cubic_Check( user->last.x,
530 control1->x, 402 control1->x,
531 control2->x, 403 control2->x,
532 to->x, 404 to->x,
533 &user->bbox.xMin, 405 &user->bbox.xMin,
534 &user->bbox.xMax ); 406 &user->bbox.xMax );
535 407
536 if ( CHECK_Y( control1, user->bbox ) || 408 if ( CHECK_Y( control1, user->bbox ) ||
537 CHECK_Y( control2, user->bbox ) ) 409 CHECK_Y( control2, user->bbox ) )
538 BBox_Cubic_Check( user->last.y, 410 BBox_Cubic_Check( user->last.y,
539 control1->y, 411 control1->y,
540 control2->y, 412 control2->y,
541 to->y, 413 to->y,
542 &user->bbox.yMin, 414 &user->bbox.yMin,
543 &user->bbox.yMax ); 415 &user->bbox.yMax );
544 416
545 user->last = *to; 417 user->last = *to;
546 418
547 return 0; 419 return 0;
548 } 420 }
549 421
550 FT_DEFINE_OUTLINE_FUNCS(bbox_interface, 422 FT_DEFINE_OUTLINE_FUNCS(bbox_interface,
551 (FT_Outline_MoveTo_Func) BBox_Move_To, 423 (FT_Outline_MoveTo_Func) BBox_Move_To,
552 (FT_Outline_LineTo_Func) BBox_Move_To, 424 (FT_Outline_LineTo_Func) BBox_Line_To,
553 (FT_Outline_ConicTo_Func)BBox_Conic_To, 425 (FT_Outline_ConicTo_Func)BBox_Conic_To,
554 (FT_Outline_CubicTo_Func)BBox_Cubic_To, 426 (FT_Outline_CubicTo_Func)BBox_Cubic_To,
555 0, 0 427 0, 0
556 ) 428 )
557 429
558 /* documentation is in ftbbox.h */ 430 /* documentation is in ftbbox.h */
559 431
560 FT_EXPORT_DEF( FT_Error ) 432 FT_EXPORT_DEF( FT_Error )
561 FT_Outline_Get_BBox( FT_Outline* outline, 433 FT_Outline_Get_BBox( FT_Outline* outline,
562 FT_BBox *abbox ) 434 FT_BBox *abbox )
563 { 435 {
564 FT_BBox cbox; 436 FT_BBox cbox = { 0x7FFFFFFF, 0x7FFFFFFF, -0x7FFFFFFF, -0x7FFFFFFF };
565 FT_BBox bbox; 437 FT_BBox bbox = { 0x7FFFFFFF, 0x7FFFFFFF, -0x7FFFFFFF, -0x7FFFFFFF };
566 FT_Vector* vec; 438 FT_Vector* vec;
567 FT_UShort n; 439 FT_UShort n;
568 440
569 441
570 if ( !abbox ) 442 if ( !abbox )
571 return FT_THROW( Invalid_Argument ); 443 return FT_THROW( Invalid_Argument );
572 444
573 if ( !outline ) 445 if ( !outline )
574 return FT_THROW( Invalid_Outline ); 446 return FT_THROW( Invalid_Outline );
575 447
576 /* if outline is empty, return (0,0,0,0) */ 448 /* if outline is empty, return (0,0,0,0) */
577 if ( outline->n_points == 0 || outline->n_contours <= 0 ) 449 if ( outline->n_points == 0 || outline->n_contours <= 0 )
578 { 450 {
579 abbox->xMin = abbox->xMax = 0; 451 abbox->xMin = abbox->xMax = 0;
580 abbox->yMin = abbox->yMax = 0; 452 abbox->yMin = abbox->yMax = 0;
581 return 0; 453 return 0;
582 } 454 }
583 455
584 /* We compute the control box as well as the bounding box of */ 456 /* We compute the control box as well as the bounding box of */
585 /* all `on' points in the outline. Then, if the two boxes */ 457 /* all `on' points in the outline. Then, if the two boxes */
586 /* coincide, we exit immediately. */ 458 /* coincide, we exit immediately. */
587 459
588 vec = outline->points; 460 vec = outline->points;
589 bbox.xMin = bbox.xMax = cbox.xMin = cbox.xMax = vec->x;
590 bbox.yMin = bbox.yMax = cbox.yMin = cbox.yMax = vec->y;
591 vec++;
592 461
593 for ( n = 1; n < outline->n_points; n++ ) 462 for ( n = 0; n < outline->n_points; n++ )
594 { 463 {
595 FT_Pos x = vec->x; 464 FT_UPDATE_BBOX( vec, cbox);
596 FT_Pos y = vec->y;
597
598
599 /* update control box */
600 if ( x < cbox.xMin ) cbox.xMin = x;
601 if ( x > cbox.xMax ) cbox.xMax = x;
602
603 if ( y < cbox.yMin ) cbox.yMin = y;
604 if ( y > cbox.yMax ) cbox.yMax = y;
605 465
606 if ( FT_CURVE_TAG( outline->tags[n] ) == FT_CURVE_TAG_ON ) 466 if ( FT_CURVE_TAG( outline->tags[n] ) == FT_CURVE_TAG_ON )
607 { 467 FT_UPDATE_BBOX( vec, bbox);
608 /* update bbox for `on' points only */
609 if ( x < bbox.xMin ) bbox.xMin = x;
610 if ( x > bbox.xMax ) bbox.xMax = x;
611
612 if ( y < bbox.yMin ) bbox.yMin = y;
613 if ( y > bbox.yMax ) bbox.yMax = y;
614 }
615 468
616 vec++; 469 vec++;
617 } 470 }
618 471
619 /* test two boxes for equality */ 472 /* test two boxes for equality */
620 if ( cbox.xMin < bbox.xMin || cbox.xMax > bbox.xMax || 473 if ( cbox.xMin < bbox.xMin || cbox.xMax > bbox.xMax ||
621 cbox.yMin < bbox.yMin || cbox.yMax > bbox.yMax ) 474 cbox.yMin < bbox.yMin || cbox.yMax > bbox.yMax )
622 { 475 {
623 /* the two boxes are different, now walk over the outline to */ 476 /* the two boxes are different, now walk over the outline to */
624 /* get the Bezier arc extrema. */ 477 /* get the Bezier arc extrema. */
(...skipping 15 matching lines...) Expand all
640 *abbox = user.bbox; 493 *abbox = user.bbox;
641 } 494 }
642 else 495 else
643 *abbox = bbox; 496 *abbox = bbox;
644 497
645 return FT_Err_Ok; 498 return FT_Err_Ok;
646 } 499 }
647 500
648 501
649 /* END */ 502 /* END */
OLDNEW
« no previous file with comments | « third_party/freetype/src/base/ftbase.c ('k') | third_party/freetype/src/base/ftbdf.c » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698