Werner Lemberg | f13516c | 2005-03-03 17:09:08 +0000 | [diff] [blame] | 1 | /***************************************************************************/ |
| 2 | /* */ |
| 3 | /* afangles.c */ |
| 4 | /* */ |
| 5 | /* Routines used to compute vector angles with limited accuracy */ |
| 6 | /* and very high speed. It also contains sorting routines (body). */ |
| 7 | /* */ |
Werner Lemberg | 332da87 | 2011-01-23 12:42:23 +0100 | [diff] [blame] | 8 | /* Copyright 2003-2006, 2011 by */ |
Werner Lemberg | f13516c | 2005-03-03 17:09:08 +0000 | [diff] [blame] | 9 | /* David Turner, Robert Wilhelm, and Werner Lemberg. */ |
| 10 | /* */ |
| 11 | /* This file is part of the FreeType project, and may only be used, */ |
| 12 | /* modified, and distributed under the terms of the FreeType project */ |
| 13 | /* license, LICENSE.TXT. By continuing to use, modify, or distribute */ |
| 14 | /* this file you indicate that you have read the license and */ |
| 15 | /* understand and accept it fully. */ |
| 16 | /* */ |
| 17 | /***************************************************************************/ |
| 18 | |
| 19 | |
David Turner | d25ad56 | 2003-10-02 21:07:10 +0000 | [diff] [blame] | 20 | #include "aftypes.h" |
| 21 | |
Werner Lemberg | 111b5ae | 2006-11-03 09:40:12 +0000 | [diff] [blame] | 22 | |
David Turner | effd15d | 2006-11-02 17:21:02 +0000 | [diff] [blame] | 23 | #if 0 |
Werner Lemberg | 111b5ae | 2006-11-03 09:40:12 +0000 | [diff] [blame] | 24 | |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 25 | FT_LOCAL_DEF( FT_Int ) |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 26 | af_corner_is_flat( FT_Pos x_in, |
| 27 | FT_Pos y_in, |
| 28 | FT_Pos x_out, |
| 29 | FT_Pos y_out ) |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 30 | { |
| 31 | FT_Pos ax = x_in; |
| 32 | FT_Pos ay = y_in; |
| 33 | |
| 34 | FT_Pos d_in, d_out, d_corner; |
| 35 | |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 36 | |
| 37 | if ( ax < 0 ) |
| 38 | ax = -ax; |
| 39 | if ( ay < 0 ) |
| 40 | ay = -ay; |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 41 | d_in = ax + ay; |
| 42 | |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 43 | ax = x_out; |
| 44 | if ( ax < 0 ) |
| 45 | ax = -ax; |
| 46 | ay = y_out; |
| 47 | if ( ay < 0 ) |
| 48 | ay = -ay; |
| 49 | d_out = ax + ay; |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 50 | |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 51 | ax = x_out + x_in; |
| 52 | if ( ax < 0 ) |
| 53 | ax = -ax; |
| 54 | ay = y_out + y_in; |
| 55 | if ( ay < 0 ) |
| 56 | ay = -ay; |
| 57 | d_corner = ax + ay; |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 58 | |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 59 | return ( d_in + d_out - d_corner ) < ( d_corner >> 4 ); |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 60 | } |
| 61 | |
| 62 | |
| 63 | FT_LOCAL_DEF( FT_Int ) |
| 64 | af_corner_orientation( FT_Pos x_in, |
| 65 | FT_Pos y_in, |
| 66 | FT_Pos x_out, |
| 67 | FT_Pos y_out ) |
| 68 | { |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 69 | FT_Pos delta; |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 70 | |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 71 | |
| 72 | delta = x_in * y_out - y_in * x_out; |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 73 | |
| 74 | if ( delta == 0 ) |
| 75 | return 0; |
| 76 | else |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 77 | return 1 - 2 * ( delta < 0 ); |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 78 | } |
Werner Lemberg | 111b5ae | 2006-11-03 09:40:12 +0000 | [diff] [blame] | 79 | |
Werner Lemberg | 332da87 | 2011-01-23 12:42:23 +0100 | [diff] [blame] | 80 | #endif /* 0 */ |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 81 | |
Werner Lemberg | 111b5ae | 2006-11-03 09:40:12 +0000 | [diff] [blame] | 82 | |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 83 | /* |
| 84 | * We are not using `af_angle_atan' anymore, but we keep the source |
| 85 | * code below just in case... |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 86 | */ |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 87 | |
| 88 | |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 89 | #if 0 |
| 90 | |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 91 | |
| 92 | /* |
| 93 | * The trick here is to realize that we don't need a very accurate angle |
| 94 | * approximation. We are going to use the result of `af_angle_atan' to |
| 95 | * only compare the sign of angle differences, or check whether its |
| 96 | * magnitude is very small. |
| 97 | * |
| 98 | * The approximation |
| 99 | * |
| 100 | * dy * PI / (|dx|+|dy|) |
| 101 | * |
| 102 | * should be enough, and much faster to compute. |
| 103 | */ |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 104 | FT_LOCAL_DEF( AF_Angle ) |
| 105 | af_angle_atan( FT_Fixed dx, |
| 106 | FT_Fixed dy ) |
| 107 | { |
| 108 | AF_Angle angle; |
| 109 | FT_Fixed ax = dx; |
| 110 | FT_Fixed ay = dy; |
| 111 | |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 112 | |
| 113 | if ( ax < 0 ) |
| 114 | ax = -ax; |
| 115 | if ( ay < 0 ) |
| 116 | ay = -ay; |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 117 | |
| 118 | ax += ay; |
| 119 | |
| 120 | if ( ax == 0 ) |
| 121 | angle = 0; |
| 122 | else |
| 123 | { |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 124 | angle = ( AF_ANGLE_PI2 * dy ) / ( ax + ay ); |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 125 | if ( dx < 0 ) |
| 126 | { |
| 127 | if ( angle >= 0 ) |
| 128 | angle = AF_ANGLE_PI - angle; |
| 129 | else |
| 130 | angle = -AF_ANGLE_PI - angle; |
| 131 | } |
| 132 | } |
| 133 | |
| 134 | return angle; |
| 135 | } |
| 136 | |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 137 | |
David Turner | 281679d | 2006-05-17 13:34:21 +0000 | [diff] [blame] | 138 | #elif 0 |
David Turner | 03ee7c8 | 2005-09-23 14:14:15 +0000 | [diff] [blame] | 139 | |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 140 | |
David Turner | 03ee7c8 | 2005-09-23 14:14:15 +0000 | [diff] [blame] | 141 | /* the following table has been automatically generated with */ |
| 142 | /* the `mather.py' Python script */ |
| 143 | |
Werner Lemberg | 7c25946 | 2005-09-28 07:34:45 +0000 | [diff] [blame] | 144 | #define AF_ATAN_BITS 8 |
David Turner | 03ee7c8 | 2005-09-23 14:14:15 +0000 | [diff] [blame] | 145 | |
| 146 | static const FT_Byte af_arctan[1L << AF_ATAN_BITS] = |
| 147 | { |
| 148 | 0, 0, 1, 1, 1, 2, 2, 2, |
| 149 | 3, 3, 3, 3, 4, 4, 4, 5, |
| 150 | 5, 5, 6, 6, 6, 7, 7, 7, |
| 151 | 8, 8, 8, 9, 9, 9, 10, 10, |
| 152 | 10, 10, 11, 11, 11, 12, 12, 12, |
| 153 | 13, 13, 13, 14, 14, 14, 14, 15, |
| 154 | 15, 15, 16, 16, 16, 17, 17, 17, |
| 155 | 18, 18, 18, 18, 19, 19, 19, 20, |
| 156 | 20, 20, 21, 21, 21, 21, 22, 22, |
| 157 | 22, 23, 23, 23, 24, 24, 24, 24, |
| 158 | 25, 25, 25, 26, 26, 26, 26, 27, |
| 159 | 27, 27, 28, 28, 28, 28, 29, 29, |
| 160 | 29, 30, 30, 30, 30, 31, 31, 31, |
| 161 | 31, 32, 32, 32, 33, 33, 33, 33, |
| 162 | 34, 34, 34, 34, 35, 35, 35, 35, |
| 163 | 36, 36, 36, 36, 37, 37, 37, 38, |
| 164 | 38, 38, 38, 39, 39, 39, 39, 40, |
| 165 | 40, 40, 40, 41, 41, 41, 41, 42, |
| 166 | 42, 42, 42, 42, 43, 43, 43, 43, |
| 167 | 44, 44, 44, 44, 45, 45, 45, 45, |
| 168 | 46, 46, 46, 46, 46, 47, 47, 47, |
| 169 | 47, 48, 48, 48, 48, 48, 49, 49, |
| 170 | 49, 49, 50, 50, 50, 50, 50, 51, |
| 171 | 51, 51, 51, 51, 52, 52, 52, 52, |
| 172 | 52, 53, 53, 53, 53, 53, 54, 54, |
| 173 | 54, 54, 54, 55, 55, 55, 55, 55, |
| 174 | 56, 56, 56, 56, 56, 57, 57, 57, |
| 175 | 57, 57, 57, 58, 58, 58, 58, 58, |
| 176 | 59, 59, 59, 59, 59, 59, 60, 60, |
| 177 | 60, 60, 60, 61, 61, 61, 61, 61, |
| 178 | 61, 62, 62, 62, 62, 62, 62, 63, |
| 179 | 63, 63, 63, 63, 63, 64, 64, 64 |
| 180 | }; |
| 181 | |
| 182 | |
| 183 | FT_LOCAL_DEF( AF_Angle ) |
| 184 | af_angle_atan( FT_Fixed dx, |
| 185 | FT_Fixed dy ) |
| 186 | { |
| 187 | AF_Angle angle; |
| 188 | |
| 189 | |
| 190 | /* check trivial cases */ |
| 191 | if ( dy == 0 ) |
| 192 | { |
| 193 | angle = 0; |
| 194 | if ( dx < 0 ) |
| 195 | angle = AF_ANGLE_PI; |
| 196 | return angle; |
| 197 | } |
| 198 | else if ( dx == 0 ) |
| 199 | { |
| 200 | angle = AF_ANGLE_PI2; |
| 201 | if ( dy < 0 ) |
| 202 | angle = -AF_ANGLE_PI2; |
| 203 | return angle; |
| 204 | } |
| 205 | |
| 206 | angle = 0; |
| 207 | if ( dx < 0 ) |
| 208 | { |
| 209 | dx = -dx; |
| 210 | dy = -dy; |
| 211 | angle = AF_ANGLE_PI; |
| 212 | } |
| 213 | |
| 214 | if ( dy < 0 ) |
| 215 | { |
| 216 | FT_Pos tmp; |
| 217 | |
| 218 | |
| 219 | tmp = dx; |
| 220 | dx = -dy; |
| 221 | dy = tmp; |
| 222 | angle -= AF_ANGLE_PI2; |
| 223 | } |
| 224 | |
| 225 | if ( dx == 0 && dy == 0 ) |
| 226 | return 0; |
| 227 | |
| 228 | if ( dx == dy ) |
| 229 | angle += AF_ANGLE_PI4; |
| 230 | else if ( dx > dy ) |
| 231 | angle += af_arctan[FT_DivFix( dy, dx ) >> ( 16 - AF_ATAN_BITS )]; |
| 232 | else |
| 233 | angle += AF_ANGLE_PI2 - |
| 234 | af_arctan[FT_DivFix( dx, dy ) >> ( 16 - AF_ATAN_BITS )]; |
| 235 | |
| 236 | if ( angle > AF_ANGLE_PI ) |
| 237 | angle -= AF_ANGLE_2PI; |
| 238 | |
| 239 | return angle; |
| 240 | } |
| 241 | |
| 242 | |
Werner Lemberg | 545c4e5 | 2006-05-17 22:55:04 +0000 | [diff] [blame] | 243 | #endif /* 0 */ |
David Turner | d25ad56 | 2003-10-02 21:07:10 +0000 | [diff] [blame] | 244 | |
David Turner | 87c0d30 | 2003-12-24 01:10:46 +0000 | [diff] [blame] | 245 | |
David Turner | ff9d241 | 2003-11-23 21:39:51 +0000 | [diff] [blame] | 246 | FT_LOCAL_DEF( void ) |
Werner Lemberg | f13516c | 2005-03-03 17:09:08 +0000 | [diff] [blame] | 247 | af_sort_pos( FT_UInt count, |
| 248 | FT_Pos* table ) |
David Turner | ff9d241 | 2003-11-23 21:39:51 +0000 | [diff] [blame] | 249 | { |
David Turner | cf2c49c | 2003-12-24 18:42:04 +0000 | [diff] [blame] | 250 | FT_UInt i, j; |
| 251 | FT_Pos swap; |
David Turner | ff9d241 | 2003-11-23 21:39:51 +0000 | [diff] [blame] | 252 | |
| 253 | |
| 254 | for ( i = 1; i < count; i++ ) |
| 255 | { |
| 256 | for ( j = i; j > 0; j-- ) |
| 257 | { |
| 258 | if ( table[j] > table[j - 1] ) |
| 259 | break; |
| 260 | |
| 261 | swap = table[j]; |
| 262 | table[j] = table[j - 1]; |
| 263 | table[j - 1] = swap; |
| 264 | } |
| 265 | } |
David Turner | 87c0d30 | 2003-12-24 01:10:46 +0000 | [diff] [blame] | 266 | } |
David Turner | cf2c49c | 2003-12-24 18:42:04 +0000 | [diff] [blame] | 267 | |
| 268 | |
| 269 | FT_LOCAL_DEF( void ) |
| 270 | af_sort_widths( FT_UInt count, |
| 271 | AF_Width table ) |
| 272 | { |
| 273 | FT_UInt i, j; |
| 274 | AF_WidthRec swap; |
| 275 | |
| 276 | |
| 277 | for ( i = 1; i < count; i++ ) |
| 278 | { |
| 279 | for ( j = i; j > 0; j-- ) |
| 280 | { |
| 281 | if ( table[j].org > table[j - 1].org ) |
| 282 | break; |
| 283 | |
| 284 | swap = table[j]; |
| 285 | table[j] = table[j - 1]; |
| 286 | table[j - 1] = swap; |
| 287 | } |
| 288 | } |
| 289 | } |
David Turner | e664efa | 2004-06-04 17:41:59 +0000 | [diff] [blame] | 290 | |
| 291 | |
Werner Lemberg | f13516c | 2005-03-03 17:09:08 +0000 | [diff] [blame] | 292 | /* END */ |