David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 1 | /***************************************************************************/ |
| 2 | /* */ |
| 3 | /* ftbbox.c */ |
| 4 | /* */ |
| 5 | /* FreeType bbox computation (body). */ |
| 6 | /* */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 7 | /* Copyright 1996-2001, 2002, 2004 by */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 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 | |
Werner Lemberg | ddbb8e7 | 2000-10-26 10:04:16 +0000 | [diff] [blame] | 18 | |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 19 | /*************************************************************************/ |
| 20 | /* */ |
| 21 | /* This component has a _single_ role: to compute exact outline bounding */ |
| 22 | /* boxes. */ |
| 23 | /* */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 24 | /*************************************************************************/ |
| 25 | |
Werner Lemberg | cc069be | 2000-12-08 16:17:16 +0000 | [diff] [blame] | 26 | |
| 27 | #include <ft2build.h> |
| 28 | #include FT_BBOX_H |
| 29 | #include FT_IMAGE_H |
| 30 | #include FT_OUTLINE_H |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 31 | #include FT_INTERNAL_CALC_H |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 32 | |
Werner Lemberg | ddbb8e7 | 2000-10-26 10:04:16 +0000 | [diff] [blame] | 33 | |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 34 | typedef struct TBBox_Rec_ |
| 35 | { |
| 36 | FT_Vector last; |
| 37 | FT_BBox bbox; |
| 38 | |
| 39 | } TBBox_Rec; |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 40 | |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 41 | |
| 42 | /*************************************************************************/ |
| 43 | /* */ |
| 44 | /* <Function> */ |
| 45 | /* BBox_Move_To */ |
| 46 | /* */ |
| 47 | /* <Description> */ |
| 48 | /* This function is used as a `move_to' and `line_to' emitter during */ |
Werner Lemberg | ddbb8e7 | 2000-10-26 10:04:16 +0000 | [diff] [blame] | 49 | /* FT_Outline_Decompose(). It simply records the destination point */ |
Werner Lemberg | 7b45c28 | 2000-11-03 07:34:29 +0000 | [diff] [blame] | 50 | /* in `user->last'; no further computations are necessary since we */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 51 | /* use the cbox as the starting bbox which must be refined. */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 52 | /* */ |
| 53 | /* <Input> */ |
| 54 | /* to :: A pointer to the destination vector. */ |
| 55 | /* */ |
| 56 | /* <InOut> */ |
| 57 | /* user :: A pointer to the current walk context. */ |
| 58 | /* */ |
| 59 | /* <Return> */ |
Werner Lemberg | ddbb8e7 | 2000-10-26 10:04:16 +0000 | [diff] [blame] | 60 | /* Always 0. Needed for the interface only. */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 61 | /* */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 62 | static int |
| 63 | BBox_Move_To( FT_Vector* to, |
| 64 | TBBox_Rec* user ) |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 65 | { |
| 66 | user->last = *to; |
| 67 | |
| 68 | return 0; |
| 69 | } |
| 70 | |
| 71 | |
| 72 | #define CHECK_X( p, bbox ) \ |
| 73 | ( p->x < bbox.xMin || p->x > bbox.xMax ) |
| 74 | |
| 75 | #define CHECK_Y( p, bbox ) \ |
| 76 | ( p->y < bbox.yMin || p->y > bbox.yMax ) |
| 77 | |
| 78 | |
| 79 | /*************************************************************************/ |
| 80 | /* */ |
| 81 | /* <Function> */ |
| 82 | /* BBox_Conic_Check */ |
| 83 | /* */ |
| 84 | /* <Description> */ |
| 85 | /* Finds the extrema of a 1-dimensional conic Bezier curve and update */ |
| 86 | /* a bounding range. This version uses direct computation, as it */ |
| 87 | /* doesn't need square roots. */ |
| 88 | /* */ |
| 89 | /* <Input> */ |
| 90 | /* y1 :: The start coordinate. */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 91 | /* */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 92 | /* y2 :: The coordinate of the control point. */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 93 | /* */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 94 | /* y3 :: The end coordinate. */ |
| 95 | /* */ |
| 96 | /* <InOut> */ |
| 97 | /* min :: The address of the current minimum. */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 98 | /* */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 99 | /* max :: The address of the current maximum. */ |
| 100 | /* */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 101 | static void |
| 102 | BBox_Conic_Check( FT_Pos y1, |
| 103 | FT_Pos y2, |
Werner Lemberg | c70818a | 2003-05-15 06:44:09 +0000 | [diff] [blame] | 104 | FT_Pos y3, |
| 105 | FT_Pos* min, |
| 106 | FT_Pos* max ) |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 107 | { |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 108 | if ( y1 <= y3 && y2 == y1 ) /* flat arc */ |
| 109 | goto Suite; |
| 110 | |
| 111 | if ( y1 < y3 ) |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 112 | { |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 113 | if ( y2 >= y1 && y2 <= y3 ) /* ascending arc */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 114 | goto Suite; |
| 115 | } |
| 116 | else |
| 117 | { |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 118 | if ( y2 >= y3 && y2 <= y1 ) /* descending arc */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 119 | { |
| 120 | y2 = y1; |
| 121 | y1 = y3; |
| 122 | y3 = y2; |
| 123 | goto Suite; |
| 124 | } |
| 125 | } |
| 126 | |
David Turner | ac83e7e | 2000-11-29 23:59:08 +0000 | [diff] [blame] | 127 | y1 = y3 = y1 - FT_MulDiv( y2 - y1, y2 - y1, y1 - 2*y2 + y3 ); |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 128 | |
| 129 | Suite: |
| 130 | if ( y1 < *min ) *min = y1; |
| 131 | if ( y3 > *max ) *max = y3; |
| 132 | } |
| 133 | |
| 134 | |
| 135 | /*************************************************************************/ |
| 136 | /* */ |
| 137 | /* <Function> */ |
| 138 | /* BBox_Conic_To */ |
| 139 | /* */ |
| 140 | /* <Description> */ |
| 141 | /* This function is used as a `conic_to' emitter during */ |
| 142 | /* FT_Raster_Decompose(). It checks a conic Bezier curve with the */ |
| 143 | /* current bounding box, and computes its extrema if necessary to */ |
| 144 | /* update it. */ |
| 145 | /* */ |
| 146 | /* <Input> */ |
| 147 | /* control :: A pointer to a control point. */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 148 | /* */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 149 | /* to :: A pointer to the destination vector. */ |
| 150 | /* */ |
| 151 | /* <InOut> */ |
| 152 | /* user :: The address of the current walk context. */ |
| 153 | /* */ |
| 154 | /* <Return> */ |
Werner Lemberg | ddbb8e7 | 2000-10-26 10:04:16 +0000 | [diff] [blame] | 155 | /* Always 0. Needed for the interface only. */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 156 | /* */ |
| 157 | /* <Note> */ |
| 158 | /* In the case of a non-monotonous arc, we compute directly the */ |
| 159 | /* extremum coordinates, as it is sufficiently fast. */ |
| 160 | /* */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 161 | static int |
| 162 | BBox_Conic_To( FT_Vector* control, |
| 163 | FT_Vector* to, |
| 164 | TBBox_Rec* user ) |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 165 | { |
Werner Lemberg | 77fb4ce | 2000-11-04 09:41:45 +0000 | [diff] [blame] | 166 | /* we don't need to check `to' since it is always an `on' point, thus */ |
| 167 | /* within the bbox */ |
| 168 | |
| 169 | if ( CHECK_X( control, user->bbox ) ) |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 170 | BBox_Conic_Check( user->last.x, |
| 171 | control->x, |
| 172 | to->x, |
| 173 | &user->bbox.xMin, |
| 174 | &user->bbox.xMax ); |
| 175 | |
Werner Lemberg | 77fb4ce | 2000-11-04 09:41:45 +0000 | [diff] [blame] | 176 | if ( CHECK_Y( control, user->bbox ) ) |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 177 | BBox_Conic_Check( user->last.y, |
| 178 | control->y, |
| 179 | to->y, |
| 180 | &user->bbox.yMin, |
| 181 | &user->bbox.yMax ); |
| 182 | |
Werner Lemberg | 7b45c28 | 2000-11-03 07:34:29 +0000 | [diff] [blame] | 183 | user->last = *to; |
| 184 | |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 185 | return 0; |
| 186 | } |
| 187 | |
| 188 | |
| 189 | /*************************************************************************/ |
| 190 | /* */ |
| 191 | /* <Function> */ |
| 192 | /* BBox_Cubic_Check */ |
| 193 | /* */ |
| 194 | /* <Description> */ |
| 195 | /* Finds the extrema of a 1-dimensional cubic Bezier curve and */ |
| 196 | /* updates a bounding range. This version uses splitting because we */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 197 | /* don't want to use square roots and extra accuracy. */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 198 | /* */ |
| 199 | /* <Input> */ |
| 200 | /* p1 :: The start coordinate. */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 201 | /* */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 202 | /* p2 :: The coordinate of the first control point. */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 203 | /* */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 204 | /* p3 :: The coordinate of the second control point. */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 205 | /* */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 206 | /* p4 :: The end coordinate. */ |
| 207 | /* */ |
| 208 | /* <InOut> */ |
| 209 | /* min :: The address of the current minimum. */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 210 | /* */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 211 | /* max :: The address of the current maximum. */ |
| 212 | /* */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 213 | |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 214 | #if 0 |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 215 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 216 | static void |
| 217 | BBox_Cubic_Check( FT_Pos p1, |
| 218 | FT_Pos p2, |
| 219 | FT_Pos p3, |
| 220 | FT_Pos p4, |
| 221 | FT_Pos* min, |
| 222 | FT_Pos* max ) |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 223 | { |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 224 | FT_Pos stack[32*3 + 1], *arc; |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 225 | |
| 226 | |
| 227 | arc = stack; |
| 228 | |
| 229 | arc[0] = p1; |
| 230 | arc[1] = p2; |
| 231 | arc[2] = p3; |
| 232 | arc[3] = p4; |
| 233 | |
| 234 | do |
| 235 | { |
| 236 | FT_Pos y1 = arc[0]; |
| 237 | FT_Pos y2 = arc[1]; |
| 238 | FT_Pos y3 = arc[2]; |
| 239 | FT_Pos y4 = arc[3]; |
| 240 | |
| 241 | |
| 242 | if ( y1 == y4 ) |
| 243 | { |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 244 | if ( y1 == y2 && y1 == y3 ) /* flat */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 245 | goto Test; |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 246 | } |
| 247 | else if ( y1 < y4 ) |
| 248 | { |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 249 | if ( y2 >= y1 && y2 <= y4 && y3 >= y1 && y3 <= y4 ) /* ascending */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 250 | goto Test; |
| 251 | } |
| 252 | else |
| 253 | { |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 254 | if ( y2 >= y4 && y2 <= y1 && y3 >= y4 && y3 <= y1 ) /* descending */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 255 | { |
| 256 | y2 = y1; |
| 257 | y1 = y4; |
| 258 | y4 = y2; |
| 259 | goto Test; |
| 260 | } |
| 261 | } |
| 262 | |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 263 | /* unknown direction -- split the arc in two */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 264 | arc[6] = y4; |
| 265 | arc[1] = y1 = ( y1 + y2 ) / 2; |
| 266 | arc[5] = y4 = ( y4 + y3 ) / 2; |
| 267 | y2 = ( y2 + y3 ) / 2; |
| 268 | arc[2] = y1 = ( y1 + y2 ) / 2; |
| 269 | arc[4] = y4 = ( y4 + y2 ) / 2; |
| 270 | arc[3] = ( y1 + y4 ) / 2; |
| 271 | |
| 272 | arc += 3; |
| 273 | goto Suite; |
| 274 | |
| 275 | Test: |
| 276 | if ( y1 < *min ) *min = y1; |
| 277 | if ( y4 > *max ) *max = y4; |
| 278 | arc -= 3; |
| 279 | |
| 280 | Suite: |
| 281 | ; |
Werner Lemberg | ddbb8e7 | 2000-10-26 10:04:16 +0000 | [diff] [blame] | 282 | } while ( arc >= stack ); |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 283 | } |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 284 | |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 285 | #else |
| 286 | |
| 287 | static void |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 288 | test_cubic_extrema( FT_Pos y1, |
| 289 | FT_Pos y2, |
| 290 | FT_Pos y3, |
| 291 | FT_Pos y4, |
| 292 | FT_Fixed u, |
| 293 | FT_Pos* min, |
| 294 | FT_Pos* max ) |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 295 | { |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 296 | /* FT_Pos a = y4 - 3*y3 + 3*y2 - y1; */ |
| 297 | FT_Pos b = y3 - 2*y2 + y1; |
| 298 | FT_Pos c = y2 - y1; |
| 299 | FT_Pos d = y1; |
| 300 | FT_Pos y; |
| 301 | FT_Fixed uu; |
| 302 | |
| 303 | FT_UNUSED ( y4 ); |
| 304 | |
| 305 | |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 306 | /* The polynom is */ |
| 307 | /* */ |
| 308 | /* P(x) = a*x^3 + 3b*x^2 + 3c*x + d , */ |
| 309 | /* */ |
| 310 | /* dP/dx = 3a*x^2 + 6b*x + 3c . */ |
| 311 | /* */ |
| 312 | /* However, we also have */ |
| 313 | /* */ |
| 314 | /* dP/dx(u) = 0 , */ |
| 315 | /* */ |
| 316 | /* which implies by subtraction that */ |
| 317 | /* */ |
| 318 | /* P(u) = b*u^2 + 2c*u + d . */ |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 319 | |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 320 | if ( u > 0 && u < 0x10000L ) |
| 321 | { |
| 322 | uu = FT_MulFix( u, u ); |
| 323 | y = d + FT_MulFix( c, 2*u ) + FT_MulFix( b, uu ); |
| 324 | |
| 325 | if ( y < *min ) *min = y; |
| 326 | if ( y > *max ) *max = y; |
| 327 | } |
| 328 | } |
| 329 | |
| 330 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 331 | static void |
| 332 | BBox_Cubic_Check( FT_Pos y1, |
| 333 | FT_Pos y2, |
| 334 | FT_Pos y3, |
| 335 | FT_Pos y4, |
| 336 | FT_Pos* min, |
| 337 | FT_Pos* max ) |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 338 | { |
| 339 | /* always compare first and last points */ |
| 340 | if ( y1 < *min ) *min = y1; |
| 341 | else if ( y1 > *max ) *max = y1; |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 342 | |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 343 | if ( y4 < *min ) *min = y4; |
| 344 | else if ( y4 > *max ) *max = y4; |
| 345 | |
| 346 | /* now, try to see if there are split points here */ |
| 347 | if ( y1 <= y4 ) |
| 348 | { |
| 349 | /* flat or ascending arc test */ |
| 350 | if ( y1 <= y2 && y2 <= y4 && y1 <= y3 && y3 <= y4 ) |
| 351 | return; |
| 352 | } |
| 353 | else /* y1 > y4 */ |
| 354 | { |
| 355 | /* descending arc test */ |
| 356 | if ( y1 >= y2 && y2 >= y4 && y1 >= y3 && y3 >= y4 ) |
| 357 | return; |
| 358 | } |
| 359 | |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 360 | /* There are some split points. Find them. */ |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 361 | { |
| 362 | FT_Pos a = y4 - 3*y3 + 3*y2 - y1; |
| 363 | FT_Pos b = y3 - 2*y2 + y1; |
| 364 | FT_Pos c = y2 - y1; |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 365 | FT_Pos d; |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 366 | FT_Fixed t; |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 367 | |
| 368 | |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 369 | /* We need to solve `ax^2+2bx+c' here, without floating points! */ |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 370 | /* The trick is to normalize to a different representation in order */ |
| 371 | /* to use our 16.16 fixed point routines. */ |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 372 | /* */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 373 | /* We compute FT_MulFix(b,b) and FT_MulFix(a,c) after normalization. */ |
| 374 | /* These values must fit into a single 16.16 value. */ |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 375 | /* */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 376 | /* We normalize a, b, and c to `8.16' fixed float values to ensure */ |
| 377 | /* that its product is held in a `16.16' value. */ |
| 378 | |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 379 | { |
| 380 | FT_ULong t1, t2; |
| 381 | int shift = 0; |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 382 | |
| 383 | |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 384 | /* The following computation is based on the fact that for */ |
| 385 | /* any value `y', if `n' is the position of the most */ |
| 386 | /* significant bit of `abs(y)' (starting from 0 for the */ |
| 387 | /* least significant bit), then `y' is in the range */ |
| 388 | /* */ |
| 389 | /* -2^n..2^n-1 */ |
| 390 | /* */ |
| 391 | /* We want to shift `a', `b', and `c' concurrently in order */ |
| 392 | /* to ensure that they all fit in 8.16 values, which maps */ |
| 393 | /* to the integer range `-2^23..2^23-1'. */ |
| 394 | /* */ |
| 395 | /* Necessarily, we need to shift `a', `b', and `c' so that */ |
| 396 | /* the most significant bit of its absolute values is at */ |
| 397 | /* _most_ at position 23. */ |
| 398 | /* */ |
| 399 | /* We begin by computing `t1' as the bitwise `OR' of the */ |
| 400 | /* absolute values of `a', `b', `c'. */ |
| 401 | |
| 402 | t1 = (FT_ULong)( ( a >= 0 ) ? a : -a ); |
| 403 | t2 = (FT_ULong)( ( b >= 0 ) ? b : -b ); |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 404 | t1 |= t2; |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 405 | t2 = (FT_ULong)( ( c >= 0 ) ? c : -c ); |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 406 | t1 |= t2; |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 407 | |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 408 | /* Now we can be sure that the most significant bit of `t1' */ |
| 409 | /* is the most significant bit of either `a', `b', or `c', */ |
| 410 | /* depending on the greatest integer range of the particular */ |
| 411 | /* variable. */ |
| 412 | /* */ |
| 413 | /* Next, we compute the `shift', by shifting `t1' as many */ |
| 414 | /* times as necessary to move its MSB to position 23. This */ |
| 415 | /* corresponds to a value of `t1' that is in the range */ |
| 416 | /* 0x40_0000..0x7F_FFFF. */ |
| 417 | /* */ |
| 418 | /* Finally, we shift `a', `b', and `c' by the same amount. */ |
| 419 | /* This ensures that all values are now in the range */ |
| 420 | /* -2^23..2^23, i.e., they are now expressed as 8.16 */ |
| 421 | /* fixed-float numbers. This also means that we are using */ |
| 422 | /* 24 bits of precision to compute the zeros, independently */ |
| 423 | /* of the range of the original polynomial coefficients. */ |
| 424 | /* */ |
| 425 | /* This algorithm should ensure reasonably accurate values */ |
| 426 | /* for the zeros. Note that they are only expressed with */ |
| 427 | /* 16 bits when computing the extrema (the zeros need to */ |
| 428 | /* be in 0..1 exclusive to be considered part of the arc). */ |
| 429 | |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 430 | if ( t1 == 0 ) /* all coefficients are 0! */ |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 431 | return; |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 432 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 433 | if ( t1 > 0x7FFFFFUL ) |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 434 | { |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 435 | do |
| 436 | { |
David Turner | e6d4518 | 2001-04-27 09:49:27 +0000 | [diff] [blame] | 437 | shift++; |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 438 | t1 >>= 1; |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 439 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 440 | } while ( t1 > 0x7FFFFFUL ); |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 441 | |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 442 | /* this loses some bits of precision, but we use 24 of them */ |
| 443 | /* for the computation anyway */ |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 444 | a >>= shift; |
| 445 | b >>= shift; |
| 446 | c >>= shift; |
| 447 | } |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 448 | else if ( t1 < 0x400000UL ) |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 449 | { |
| 450 | do |
| 451 | { |
| 452 | shift++; |
| 453 | t1 <<= 1; |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 454 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 455 | } while ( t1 < 0x400000UL ); |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 456 | |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 457 | a <<= shift; |
| 458 | b <<= shift; |
| 459 | c <<= shift; |
| 460 | } |
| 461 | } |
| 462 | |
| 463 | /* handle a == 0 */ |
| 464 | if ( a == 0 ) |
| 465 | { |
| 466 | if ( b != 0 ) |
| 467 | { |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 468 | t = - FT_DivFix( c, b ) / 2; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 469 | test_cubic_extrema( y1, y2, y3, y4, t, min, max ); |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 470 | } |
| 471 | } |
| 472 | else |
| 473 | { |
| 474 | /* solve the equation now */ |
| 475 | d = FT_MulFix( b, b ) - FT_MulFix( a, c ); |
| 476 | if ( d < 0 ) |
| 477 | return; |
| 478 | |
| 479 | if ( d == 0 ) |
| 480 | { |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 481 | /* there is a single split point at -b/a */ |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 482 | t = - FT_DivFix( b, a ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 483 | test_cubic_extrema( y1, y2, y3, y4, t, min, max ); |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 484 | } |
| 485 | else |
| 486 | { |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 487 | /* there are two solutions; we need to filter them */ |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 488 | d = FT_SqrtFixed( (FT_Int32)d ); |
| 489 | t = - FT_DivFix( b - d, a ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 490 | test_cubic_extrema( y1, y2, y3, y4, t, min, max ); |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 491 | |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 492 | t = - FT_DivFix( b + d, a ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 493 | test_cubic_extrema( y1, y2, y3, y4, t, min, max ); |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 494 | } |
| 495 | } |
| 496 | } |
Werner Lemberg | 3780273 | 2001-04-26 13:34:36 +0000 | [diff] [blame] | 497 | } |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 498 | |
| 499 | #endif |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 500 | |
| 501 | |
| 502 | /*************************************************************************/ |
| 503 | /* */ |
| 504 | /* <Function> */ |
| 505 | /* BBox_Cubic_To */ |
| 506 | /* */ |
| 507 | /* <Description> */ |
| 508 | /* This function is used as a `cubic_to' emitter during */ |
| 509 | /* FT_Raster_Decompose(). It checks a cubic Bezier curve with the */ |
| 510 | /* current bounding box, and computes its extrema if necessary to */ |
| 511 | /* update it. */ |
| 512 | /* */ |
| 513 | /* <Input> */ |
| 514 | /* control1 :: A pointer to the first control point. */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 515 | /* */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 516 | /* control2 :: A pointer to the second control point. */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 517 | /* */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 518 | /* to :: A pointer to the destination vector. */ |
| 519 | /* */ |
| 520 | /* <InOut> */ |
| 521 | /* user :: The address of the current walk context. */ |
| 522 | /* */ |
| 523 | /* <Return> */ |
Werner Lemberg | ddbb8e7 | 2000-10-26 10:04:16 +0000 | [diff] [blame] | 524 | /* Always 0. Needed for the interface only. */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 525 | /* */ |
| 526 | /* <Note> */ |
| 527 | /* In the case of a non-monotonous arc, we don't compute directly */ |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 528 | /* extremum coordinates, we subdivide instead. */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 529 | /* */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 530 | static int |
| 531 | BBox_Cubic_To( FT_Vector* control1, |
| 532 | FT_Vector* control2, |
| 533 | FT_Vector* to, |
| 534 | TBBox_Rec* user ) |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 535 | { |
Werner Lemberg | 77fb4ce | 2000-11-04 09:41:45 +0000 | [diff] [blame] | 536 | /* we don't need to check `to' since it is always an `on' point, thus */ |
| 537 | /* within the bbox */ |
| 538 | |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 539 | if ( CHECK_X( control1, user->bbox ) || |
Werner Lemberg | 77fb4ce | 2000-11-04 09:41:45 +0000 | [diff] [blame] | 540 | CHECK_X( control2, user->bbox ) ) |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 541 | BBox_Cubic_Check( user->last.x, |
| 542 | control1->x, |
| 543 | control2->x, |
| 544 | to->x, |
| 545 | &user->bbox.xMin, |
| 546 | &user->bbox.xMax ); |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 547 | |
| 548 | if ( CHECK_Y( control1, user->bbox ) || |
Werner Lemberg | 77fb4ce | 2000-11-04 09:41:45 +0000 | [diff] [blame] | 549 | CHECK_Y( control2, user->bbox ) ) |
Werner Lemberg | b637038 | 2004-05-19 09:22:26 +0000 | [diff] [blame] | 550 | BBox_Cubic_Check( user->last.y, |
| 551 | control1->y, |
| 552 | control2->y, |
| 553 | to->y, |
| 554 | &user->bbox.yMin, |
| 555 | &user->bbox.yMax ); |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 556 | |
Werner Lemberg | 7b45c28 | 2000-11-03 07:34:29 +0000 | [diff] [blame] | 557 | user->last = *to; |
| 558 | |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 559 | return 0; |
| 560 | } |
| 561 | |
| 562 | |
Werner Lemberg | 90a0330 | 2000-11-07 17:21:11 +0000 | [diff] [blame] | 563 | /* documentation is in ftbbox.h */ |
| 564 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 565 | FT_EXPORT_DEF( FT_Error ) |
| 566 | FT_Outline_Get_BBox( FT_Outline* outline, |
| 567 | FT_BBox *abbox ) |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 568 | { |
Werner Lemberg | ddbb8e7 | 2000-10-26 10:04:16 +0000 | [diff] [blame] | 569 | FT_BBox cbox; |
| 570 | FT_BBox bbox; |
| 571 | FT_Vector* vec; |
| 572 | FT_UShort n; |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 573 | |
| 574 | |
Werner Lemberg | ddbb8e7 | 2000-10-26 10:04:16 +0000 | [diff] [blame] | 575 | if ( !abbox ) |
| 576 | return FT_Err_Invalid_Argument; |
| 577 | |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 578 | if ( !outline ) |
| 579 | return FT_Err_Invalid_Outline; |
| 580 | |
Werner Lemberg | ddbb8e7 | 2000-10-26 10:04:16 +0000 | [diff] [blame] | 581 | /* if outline is empty, return (0,0,0,0) */ |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 582 | if ( outline->n_points == 0 || outline->n_contours <= 0 ) |
| 583 | { |
| 584 | abbox->xMin = abbox->xMax = 0; |
| 585 | abbox->yMin = abbox->yMax = 0; |
| 586 | return 0; |
| 587 | } |
| 588 | |
| 589 | /* We compute the control box as well as the bounding box of */ |
| 590 | /* all `on' points in the outline. Then, if the two boxes */ |
| 591 | /* coincide, we exit immediately. */ |
| 592 | |
| 593 | vec = outline->points; |
| 594 | bbox.xMin = bbox.xMax = cbox.xMin = cbox.xMax = vec->x; |
| 595 | bbox.yMin = bbox.yMax = cbox.yMin = cbox.yMax = vec->y; |
David Turner | caf72cd | 2001-04-25 18:11:16 +0000 | [diff] [blame] | 596 | vec++; |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 597 | |
| 598 | for ( n = 1; n < outline->n_points; n++ ) |
| 599 | { |
| 600 | FT_Pos x = vec->x; |
| 601 | FT_Pos y = vec->y; |
| 602 | |
| 603 | |
| 604 | /* update control box */ |
| 605 | if ( x < cbox.xMin ) cbox.xMin = x; |
| 606 | if ( x > cbox.xMax ) cbox.xMax = x; |
| 607 | |
| 608 | if ( y < cbox.yMin ) cbox.yMin = y; |
| 609 | if ( y > cbox.yMax ) cbox.yMax = y; |
| 610 | |
David Turner | b08fe2d | 2002-08-27 20:20:29 +0000 | [diff] [blame] | 611 | if ( FT_CURVE_TAG( outline->tags[n] ) == FT_CURVE_TAG_ON ) |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 612 | { |
| 613 | /* update bbox for `on' points only */ |
| 614 | if ( x < bbox.xMin ) bbox.xMin = x; |
| 615 | if ( x > bbox.xMax ) bbox.xMax = x; |
| 616 | |
| 617 | if ( y < bbox.yMin ) bbox.yMin = y; |
| 618 | if ( y > bbox.yMax ) bbox.yMax = y; |
| 619 | } |
| 620 | |
| 621 | vec++; |
| 622 | } |
| 623 | |
| 624 | /* test two boxes for equality */ |
| 625 | if ( cbox.xMin < bbox.xMin || cbox.xMax > bbox.xMax || |
| 626 | cbox.yMin < bbox.yMin || cbox.yMax > bbox.yMax ) |
| 627 | { |
| 628 | /* the two boxes are different, now walk over the outline to */ |
| 629 | /* get the Bezier arc extrema. */ |
| 630 | |
Werner Lemberg | 5f0ee94 | 2002-04-30 06:37:52 +0000 | [diff] [blame] | 631 | static const FT_Outline_Funcs bbox_interface = |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 632 | { |
| 633 | (FT_Outline_MoveTo_Func) BBox_Move_To, |
| 634 | (FT_Outline_LineTo_Func) BBox_Move_To, |
| 635 | (FT_Outline_ConicTo_Func)BBox_Conic_To, |
Werner Lemberg | 8c883fb | 2000-11-05 23:41:08 +0000 | [diff] [blame] | 636 | (FT_Outline_CubicTo_Func)BBox_Cubic_To, |
| 637 | 0, 0 |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 638 | }; |
| 639 | |
| 640 | FT_Error error; |
| 641 | TBBox_Rec user; |
| 642 | |
| 643 | |
| 644 | user.bbox = bbox; |
| 645 | |
Werner Lemberg | 5f0ee94 | 2002-04-30 06:37:52 +0000 | [diff] [blame] | 646 | error = FT_Outline_Decompose( outline, &bbox_interface, &user ); |
David Turner | 54169b3 | 2000-10-26 00:06:35 +0000 | [diff] [blame] | 647 | if ( error ) |
| 648 | return error; |
| 649 | |
| 650 | *abbox = user.bbox; |
| 651 | } |
| 652 | else |
| 653 | *abbox = bbox; |
| 654 | |
| 655 | return FT_Err_Ok; |
| 656 | } |
| 657 | |
| 658 | |
| 659 | /* END */ |