Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 1 | /***************************************************************************/ |
| 2 | /* */ |
| 3 | /* fttrigon.c */ |
| 4 | /* */ |
| 5 | /* FreeType trigonometric functions (body). */ |
| 6 | /* */ |
Werner Lemberg | cee37a3 | 2005-11-12 07:34:40 +0000 | [diff] [blame] | 7 | /* Copyright 2001, 2002, 2003, 2004, 2005 by */ |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +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 | |
| 18 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 19 | #include <ft2build.h> |
Werner Lemberg | 80cfbd7 | 2003-12-26 07:26:08 +0000 | [diff] [blame] | 20 | #include FT_INTERNAL_OBJECTS_H |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 21 | #include FT_TRIGONOMETRY_H |
| 22 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 23 | |
| 24 | /* the following is 0.2715717684432231 * 2^30 */ |
| 25 | #define FT_TRIG_COSCALE 0x11616E8EUL |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 26 | |
| 27 | /* this table was generated for FT_PI = 180L << 16, i.e. degrees */ |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 28 | #define FT_TRIG_MAX_ITERS 23 |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 29 | |
| 30 | static const FT_Fixed |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 31 | ft_trig_arctan_table[24] = |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 32 | { |
Werner Lemberg | cf24d51 | 2001-06-18 14:23:45 +0000 | [diff] [blame] | 33 | 4157273L, 2949120L, 1740967L, 919879L, 466945L, 234379L, 117304L, |
| 34 | 58666L, 29335L, 14668L, 7334L, 3667L, 1833L, 917L, 458L, 229L, 115L, |
| 35 | 57L, 29L, 14L, 7L, 4L, 2L, 1L |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 36 | }; |
| 37 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 38 | /* the Cordic shrink factor, multiplied by 2^32 */ |
| 39 | #define FT_TRIG_SCALE 1166391785UL /* 0x4585BA38UL */ |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 40 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 41 | |
| 42 | #ifdef FT_CONFIG_HAS_INT64 |
| 43 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 44 | /* multiply a given value by the CORDIC shrink factor */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 45 | static FT_Fixed |
| 46 | ft_trig_downscale( FT_Fixed val ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 47 | { |
| 48 | FT_Fixed s; |
| 49 | FT_Int64 v; |
| 50 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 51 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 52 | s = val; |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 53 | val = ( val >= 0 ) ? val : -val; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 54 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 55 | v = ( val * (FT_Int64)FT_TRIG_SCALE ) + 0x100000000UL; |
| 56 | val = (FT_Fixed)( v >> 32 ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 57 | |
| 58 | return ( s >= 0 ) ? val : -val; |
| 59 | } |
| 60 | |
| 61 | #else /* !FT_CONFIG_HAS_INT64 */ |
| 62 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 63 | /* multiply a given value by the CORDIC shrink factor */ |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 64 | static FT_Fixed |
| 65 | ft_trig_downscale( FT_Fixed val ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 66 | { |
| 67 | FT_Fixed s; |
| 68 | FT_UInt32 v1, v2, k1, k2, hi, lo1, lo2, lo3; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 69 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 70 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 71 | s = val; |
| 72 | val = ( val >= 0 ) ? val : -val; |
| 73 | |
| 74 | v1 = (FT_UInt32)val >> 16; |
Werner Lemberg | 43ba084 | 2003-06-23 19:26:53 +0000 | [diff] [blame] | 75 | v2 = (FT_UInt32)val & 0xFFFFL; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 76 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 77 | k1 = FT_TRIG_SCALE >> 16; /* constant */ |
Werner Lemberg | 43ba084 | 2003-06-23 19:26:53 +0000 | [diff] [blame] | 78 | k2 = FT_TRIG_SCALE & 0xFFFFL; /* constant */ |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 79 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 80 | hi = k1 * v1; |
| 81 | lo1 = k1 * v2 + k2 * v1; /* can't overflow */ |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 82 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 83 | lo2 = ( k2 * v2 ) >> 16; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 84 | lo3 = ( lo1 >= lo2 ) ? lo1 : lo2; |
| 85 | lo1 += lo2; |
| 86 | |
| 87 | hi += lo1 >> 16; |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 88 | if ( lo1 < lo3 ) |
| 89 | hi += 0x10000UL; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 90 | |
| 91 | val = (FT_Fixed)hi; |
| 92 | |
| 93 | return ( s >= 0 ) ? val : -val; |
| 94 | } |
| 95 | |
| 96 | #endif /* !FT_CONFIG_HAS_INT64 */ |
| 97 | |
| 98 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 99 | static FT_Int |
| 100 | ft_trig_prenorm( FT_Vector* vec ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 101 | { |
| 102 | FT_Fixed x, y, z; |
| 103 | FT_Int shift; |
| 104 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 105 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 106 | x = vec->x; |
| 107 | y = vec->y; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 108 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 109 | z = ( ( x >= 0 ) ? x : - x ) | ( (y >= 0) ? y : -y ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 110 | shift = 0; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 111 | |
David Turner | 9fbd2ab | 2005-10-28 16:14:14 +0000 | [diff] [blame] | 112 | #if 1 |
Werner Lemberg | cee37a3 | 2005-11-12 07:34:40 +0000 | [diff] [blame] | 113 | /* determine msb bit index in `shift' */ |
| 114 | if ( z >= ( 1L << 16 ) ) |
David Turner | 9fbd2ab | 2005-10-28 16:14:14 +0000 | [diff] [blame] | 115 | { |
| 116 | z >>= 16; |
| 117 | shift += 16; |
| 118 | } |
Werner Lemberg | cee37a3 | 2005-11-12 07:34:40 +0000 | [diff] [blame] | 119 | if ( z >= ( 1L << 8 ) ) |
David Turner | 9fbd2ab | 2005-10-28 16:14:14 +0000 | [diff] [blame] | 120 | { |
| 121 | z >>= 8; |
| 122 | shift += 8; |
| 123 | } |
Werner Lemberg | cee37a3 | 2005-11-12 07:34:40 +0000 | [diff] [blame] | 124 | if ( z >= ( 1L << 4 ) ) |
David Turner | 9fbd2ab | 2005-10-28 16:14:14 +0000 | [diff] [blame] | 125 | { |
| 126 | z >>= 4; |
| 127 | shift += 4; |
| 128 | } |
Werner Lemberg | cee37a3 | 2005-11-12 07:34:40 +0000 | [diff] [blame] | 129 | if ( z >= ( 1L << 2 ) ) |
David Turner | 9fbd2ab | 2005-10-28 16:14:14 +0000 | [diff] [blame] | 130 | { |
| 131 | z >>= 2; |
| 132 | shift += 2; |
| 133 | } |
David Turner | f7cc181 | 2005-11-15 17:30:56 +0000 | [diff] [blame] | 134 | if ( z >= ( 1L << 1 ) ) |
David Turner | 9fbd2ab | 2005-10-28 16:14:14 +0000 | [diff] [blame] | 135 | { |
David Turner | f7cc181 | 2005-11-15 17:30:56 +0000 | [diff] [blame] | 136 | z >>= 1; |
| 137 | shift += 1; |
| 138 | } |
| 139 | |
| 140 | if ( shift <= 27 ) |
| 141 | { |
| 142 | shift = 27 - shift; |
David Turner | 9fbd2ab | 2005-10-28 16:14:14 +0000 | [diff] [blame] | 143 | vec->x = x << shift; |
| 144 | vec->y = y << shift; |
| 145 | } |
David Turner | f7cc181 | 2005-11-15 17:30:56 +0000 | [diff] [blame] | 146 | else |
David Turner | 9fbd2ab | 2005-10-28 16:14:14 +0000 | [diff] [blame] | 147 | { |
David Turner | f7cc181 | 2005-11-15 17:30:56 +0000 | [diff] [blame] | 148 | shift -= 27; |
David Turner | 9fbd2ab | 2005-10-28 16:14:14 +0000 | [diff] [blame] | 149 | vec->x = x >> shift; |
| 150 | vec->y = y >> shift; |
| 151 | shift = -shift; |
| 152 | } |
Werner Lemberg | cee37a3 | 2005-11-12 07:34:40 +0000 | [diff] [blame] | 153 | |
| 154 | #else /* 0 */ |
| 155 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 156 | if ( z < ( 1L << 27 ) ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 157 | { |
| 158 | do |
| 159 | { |
| 160 | shift++; |
| 161 | z <<= 1; |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 162 | } while ( z < ( 1L << 27 ) ); |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 163 | vec->x = x << shift; |
| 164 | vec->y = y << shift; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 165 | } |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 166 | else if ( z > ( 1L << 28 ) ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 167 | { |
| 168 | do |
| 169 | { |
| 170 | shift++; |
| 171 | z >>= 1; |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 172 | } while ( z > ( 1L << 28 ) ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 173 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 174 | vec->x = x >> shift; |
| 175 | vec->y = y >> shift; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 176 | shift = -shift; |
| 177 | } |
Werner Lemberg | cee37a3 | 2005-11-12 07:34:40 +0000 | [diff] [blame] | 178 | |
| 179 | #endif /* 0 */ |
| 180 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 181 | return shift; |
| 182 | } |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 183 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 184 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 185 | static void |
| 186 | ft_trig_pseudo_rotate( FT_Vector* vec, |
| 187 | FT_Angle theta ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 188 | { |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 189 | FT_Int i; |
| 190 | FT_Fixed x, y, xtemp; |
| 191 | const FT_Fixed *arctanptr; |
| 192 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 193 | |
| 194 | x = vec->x; |
| 195 | y = vec->y; |
| 196 | |
| 197 | /* Get angle between -90 and 90 degrees */ |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 198 | while ( theta <= -FT_ANGLE_PI2 ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 199 | { |
| 200 | x = -x; |
| 201 | y = -y; |
| 202 | theta += FT_ANGLE_PI; |
| 203 | } |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 204 | |
| 205 | while ( theta > FT_ANGLE_PI2 ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 206 | { |
| 207 | x = -x; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 208 | y = -y; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 209 | theta -= FT_ANGLE_PI; |
| 210 | } |
| 211 | |
| 212 | /* Initial pseudorotation, with left shift */ |
| 213 | arctanptr = ft_trig_arctan_table; |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 214 | |
| 215 | if ( theta < 0 ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 216 | { |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 217 | xtemp = x + ( y << 1 ); |
| 218 | y = y - ( x << 1 ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 219 | x = xtemp; |
| 220 | theta += *arctanptr++; |
| 221 | } |
| 222 | else |
| 223 | { |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 224 | xtemp = x - ( y << 1 ); |
| 225 | y = y + ( x << 1 ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 226 | x = xtemp; |
| 227 | theta -= *arctanptr++; |
| 228 | } |
| 229 | |
| 230 | /* Subsequent pseudorotations, with right shifts */ |
| 231 | i = 0; |
| 232 | do |
| 233 | { |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 234 | if ( theta < 0 ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 235 | { |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 236 | xtemp = x + ( y >> i ); |
| 237 | y = y - ( x >> i ); |
| 238 | x = xtemp; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 239 | theta += *arctanptr++; |
| 240 | } |
| 241 | else |
| 242 | { |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 243 | xtemp = x - ( y >> i ); |
| 244 | y = y + ( x >> i ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 245 | x = xtemp; |
| 246 | theta -= *arctanptr++; |
| 247 | } |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 248 | } while ( ++i < FT_TRIG_MAX_ITERS ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 249 | |
| 250 | vec->x = x; |
| 251 | vec->y = y; |
| 252 | } |
| 253 | |
| 254 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 255 | static void |
| 256 | ft_trig_pseudo_polarize( FT_Vector* vec ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 257 | { |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 258 | FT_Fixed theta; |
| 259 | FT_Fixed yi, i; |
| 260 | FT_Fixed x, y; |
| 261 | const FT_Fixed *arctanptr; |
| 262 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 263 | |
| 264 | x = vec->x; |
| 265 | y = vec->y; |
| 266 | |
| 267 | /* Get the vector into the right half plane */ |
| 268 | theta = 0; |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 269 | if ( x < 0 ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 270 | { |
| 271 | x = -x; |
| 272 | y = -y; |
| 273 | theta = 2 * FT_ANGLE_PI2; |
| 274 | } |
| 275 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 276 | if ( y > 0 ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 277 | theta = - theta; |
| 278 | |
| 279 | arctanptr = ft_trig_arctan_table; |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 280 | |
| 281 | if ( y < 0 ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 282 | { |
| 283 | /* Rotate positive */ |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 284 | yi = y + ( x << 1 ); |
| 285 | x = x - ( y << 1 ); |
| 286 | y = yi; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 287 | theta -= *arctanptr++; /* Subtract angle */ |
| 288 | } |
| 289 | else |
| 290 | { |
| 291 | /* Rotate negative */ |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 292 | yi = y - ( x << 1 ); |
| 293 | x = x + ( y << 1 ); |
| 294 | y = yi; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 295 | theta += *arctanptr++; /* Add angle */ |
| 296 | } |
| 297 | |
| 298 | i = 0; |
| 299 | do |
| 300 | { |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 301 | if ( y < 0 ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 302 | { |
| 303 | /* Rotate positive */ |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 304 | yi = y + ( x >> i ); |
| 305 | x = x - ( y >> i ); |
| 306 | y = yi; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 307 | theta -= *arctanptr++; |
| 308 | } |
| 309 | else |
| 310 | { |
| 311 | /* Rotate negative */ |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 312 | yi = y - ( x >> i ); |
| 313 | x = x + ( y >> i ); |
| 314 | y = yi; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 315 | theta += *arctanptr++; |
| 316 | } |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 317 | } while ( ++i < FT_TRIG_MAX_ITERS ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 318 | |
| 319 | /* round theta */ |
| 320 | if ( theta >= 0 ) |
David Turner | 87c0d30 | 2003-12-24 01:10:46 +0000 | [diff] [blame] | 321 | theta = FT_PAD_ROUND( theta, 32 ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 322 | else |
Werner Lemberg | f13516c | 2005-03-03 17:09:08 +0000 | [diff] [blame] | 323 | theta = -FT_PAD_ROUND( -theta, 32 ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 324 | |
| 325 | vec->x = x; |
| 326 | vec->y = theta; |
| 327 | } |
| 328 | |
| 329 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 330 | /* documentation is in fttrigon.h */ |
| 331 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 332 | FT_EXPORT_DEF( FT_Fixed ) |
| 333 | FT_Cos( FT_Angle angle ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 334 | { |
| 335 | FT_Vector v; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 336 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 337 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 338 | v.x = FT_TRIG_COSCALE >> 2; |
| 339 | v.y = 0; |
| 340 | ft_trig_pseudo_rotate( &v, angle ); |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 341 | |
Werner Lemberg | 5da9dd7 | 2001-12-16 08:17:33 +0000 | [diff] [blame] | 342 | return v.x / ( 1 << 12 ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 343 | } |
| 344 | |
| 345 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 346 | /* documentation is in fttrigon.h */ |
| 347 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 348 | FT_EXPORT_DEF( FT_Fixed ) |
| 349 | FT_Sin( FT_Angle angle ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 350 | { |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 351 | return FT_Cos( FT_ANGLE_PI2 - angle ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 352 | } |
| 353 | |
| 354 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 355 | /* documentation is in fttrigon.h */ |
| 356 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 357 | FT_EXPORT_DEF( FT_Fixed ) |
| 358 | FT_Tan( FT_Angle angle ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 359 | { |
| 360 | FT_Vector v; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 361 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 362 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 363 | v.x = FT_TRIG_COSCALE >> 2; |
| 364 | v.y = 0; |
| 365 | ft_trig_pseudo_rotate( &v, angle ); |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 366 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 367 | return FT_DivFix( v.y, v.x ); |
| 368 | } |
| 369 | |
| 370 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 371 | /* documentation is in fttrigon.h */ |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 372 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 373 | FT_EXPORT_DEF( FT_Angle ) |
| 374 | FT_Atan2( FT_Fixed dx, |
| 375 | FT_Fixed dy ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 376 | { |
| 377 | FT_Vector v; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 378 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 379 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 380 | if ( dx == 0 && dy == 0 ) |
| 381 | return 0; |
| 382 | |
| 383 | v.x = dx; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 384 | v.y = dy; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 385 | ft_trig_prenorm( &v ); |
| 386 | ft_trig_pseudo_polarize( &v ); |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 387 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 388 | return v.y; |
| 389 | } |
| 390 | |
| 391 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 392 | /* documentation is in fttrigon.h */ |
| 393 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 394 | FT_EXPORT_DEF( void ) |
| 395 | FT_Vector_Unit( FT_Vector* vec, |
| 396 | FT_Angle angle ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 397 | { |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 398 | vec->x = FT_TRIG_COSCALE >> 2; |
| 399 | vec->y = 0; |
| 400 | ft_trig_pseudo_rotate( vec, angle ); |
| 401 | vec->x >>= 12; |
| 402 | vec->y >>= 12; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 403 | } |
| 404 | |
| 405 | |
Werner Lemberg | 4f10745 | 2003-05-17 12:07:45 +0000 | [diff] [blame] | 406 | /* these macros return 0 for positive numbers, |
| 407 | and -1 for negative ones */ |
| 408 | #define FT_SIGN_LONG( x ) ( (x) >> ( FT_SIZEOF_LONG * 8 - 1 ) ) |
| 409 | #define FT_SIGN_INT( x ) ( (x) >> ( FT_SIZEOF_INT * 8 - 1 ) ) |
| 410 | #define FT_SIGN_INT32( x ) ( (x) >> 31 ) |
| 411 | #define FT_SIGN_INT16( x ) ( (x) >> 15 ) |
| 412 | |
| 413 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 414 | /* documentation is in fttrigon.h */ |
| 415 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 416 | FT_EXPORT_DEF( void ) |
| 417 | FT_Vector_Rotate( FT_Vector* vec, |
| 418 | FT_Angle angle ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 419 | { |
| 420 | FT_Int shift; |
| 421 | FT_Vector v; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 422 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 423 | |
Werner Lemberg | 4f10745 | 2003-05-17 12:07:45 +0000 | [diff] [blame] | 424 | v.x = vec->x; |
| 425 | v.y = vec->y; |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 426 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 427 | if ( angle && ( v.x != 0 || v.y != 0 ) ) |
| 428 | { |
| 429 | shift = ft_trig_prenorm( &v ); |
| 430 | ft_trig_pseudo_rotate( &v, angle ); |
| 431 | v.x = ft_trig_downscale( v.x ); |
| 432 | v.y = ft_trig_downscale( v.y ); |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 433 | |
Werner Lemberg | 4f10745 | 2003-05-17 12:07:45 +0000 | [diff] [blame] | 434 | if ( shift > 0 ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 435 | { |
Werner Lemberg | 4f10745 | 2003-05-17 12:07:45 +0000 | [diff] [blame] | 436 | FT_Int32 half = 1L << ( shift - 1 ); |
| 437 | |
| 438 | |
| 439 | vec->x = ( v.x + half + FT_SIGN_LONG( v.x ) ) >> shift; |
| 440 | vec->y = ( v.y + half + FT_SIGN_LONG( v.y ) ) >> shift; |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 441 | } |
| 442 | else |
| 443 | { |
| 444 | shift = -shift; |
| 445 | vec->x = v.x << shift; |
| 446 | vec->y = v.y << shift; |
| 447 | } |
| 448 | } |
| 449 | } |
| 450 | |
| 451 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 452 | /* documentation is in fttrigon.h */ |
| 453 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 454 | FT_EXPORT_DEF( FT_Fixed ) |
| 455 | FT_Vector_Length( FT_Vector* vec ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 456 | { |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 457 | FT_Int shift; |
| 458 | FT_Vector v; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 459 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 460 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 461 | v = *vec; |
| 462 | |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 463 | /* handle trivial cases */ |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 464 | if ( v.x == 0 ) |
| 465 | { |
| 466 | return ( v.y >= 0 ) ? v.y : -v.y; |
| 467 | } |
| 468 | else if ( v.y == 0 ) |
| 469 | { |
| 470 | return ( v.x >= 0 ) ? v.x : -v.x; |
| 471 | } |
| 472 | |
| 473 | /* general case */ |
| 474 | shift = ft_trig_prenorm( &v ); |
| 475 | ft_trig_pseudo_polarize( &v ); |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 476 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 477 | v.x = ft_trig_downscale( v.x ); |
Werner Lemberg | 04728a8 | 2002-04-02 14:50:31 +0000 | [diff] [blame] | 478 | |
| 479 | if ( shift > 0 ) |
| 480 | return ( v.x + ( 1 << ( shift - 1 ) ) ) >> shift; |
| 481 | |
| 482 | return v.x << -shift; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 483 | } |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 484 | |
| 485 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 486 | /* documentation is in fttrigon.h */ |
| 487 | |
Werner Lemberg | f814d0f | 2001-06-27 16:18:10 +0000 | [diff] [blame] | 488 | FT_EXPORT_DEF( void ) |
| 489 | FT_Vector_Polarize( FT_Vector* vec, |
| 490 | FT_Fixed *length, |
| 491 | FT_Angle *angle ) |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 492 | { |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 493 | FT_Int shift; |
| 494 | FT_Vector v; |
| 495 | |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 496 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 497 | v = *vec; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 498 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 499 | if ( v.x == 0 && v.y == 0 ) |
| 500 | return; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 501 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 502 | shift = ft_trig_prenorm( &v ); |
| 503 | ft_trig_pseudo_polarize( &v ); |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 504 | |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 505 | v.x = ft_trig_downscale( v.x ); |
| 506 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 507 | *length = ( shift >= 0 ) ? ( v.x >> shift ) : ( v.x << -shift ); |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 508 | *angle = v.y; |
Werner Lemberg | 415235d | 2001-06-28 17:49:10 +0000 | [diff] [blame] | 509 | } |
David Turner | ebe85f5 | 2001-05-11 14:25:57 +0000 | [diff] [blame] | 510 | |
| 511 | |
David Turner | b7e18ef | 2002-06-26 22:05:05 +0000 | [diff] [blame] | 512 | /* documentation is in fttrigon.h */ |
| 513 | |
David Turner | 0d73b0c | 2002-06-26 23:45:21 +0000 | [diff] [blame] | 514 | FT_EXPORT_DEF( void ) |
| 515 | FT_Vector_From_Polar( FT_Vector* vec, |
| 516 | FT_Fixed length, |
| 517 | FT_Angle angle ) |
| 518 | { |
| 519 | vec->x = length; |
| 520 | vec->y = 0; |
| 521 | |
| 522 | FT_Vector_Rotate( vec, angle ); |
| 523 | } |
| 524 | |
| 525 | |
| 526 | /* documentation is in fttrigon.h */ |
| 527 | |
David Turner | b7e18ef | 2002-06-26 22:05:05 +0000 | [diff] [blame] | 528 | FT_EXPORT_DEF( FT_Angle ) |
David Turner | ac90c0e | 2002-07-01 21:35:17 +0000 | [diff] [blame] | 529 | FT_Angle_Diff( FT_Angle angle1, |
| 530 | FT_Angle angle2 ) |
David Turner | b7e18ef | 2002-06-26 22:05:05 +0000 | [diff] [blame] | 531 | { |
| 532 | FT_Angle delta = angle2 - angle1; |
David Turner | 0d73b0c | 2002-06-26 23:45:21 +0000 | [diff] [blame] | 533 | |
Werner Lemberg | 1ec3963 | 2004-11-24 07:08:21 +0000 | [diff] [blame] | 534 | |
David Turner | b7e18ef | 2002-06-26 22:05:05 +0000 | [diff] [blame] | 535 | delta %= FT_ANGLE_2PI; |
David Turner | 20e3315 | 2003-01-07 22:54:02 +0000 | [diff] [blame] | 536 | if ( delta < 0 ) |
| 537 | delta += FT_ANGLE_2PI; |
David Turner | b7e18ef | 2002-06-26 22:05:05 +0000 | [diff] [blame] | 538 | |
| 539 | if ( delta > FT_ANGLE_PI ) |
| 540 | delta -= FT_ANGLE_2PI; |
David Turner | 0d73b0c | 2002-06-26 23:45:21 +0000 | [diff] [blame] | 541 | |
David Turner | b7e18ef | 2002-06-26 22:05:05 +0000 | [diff] [blame] | 542 | return delta; |
David Turner | 0d73b0c | 2002-06-26 23:45:21 +0000 | [diff] [blame] | 543 | } |
David Turner | b7e18ef | 2002-06-26 22:05:05 +0000 | [diff] [blame] | 544 | |
| 545 | |
Werner Lemberg | ec6ddd5 | 2001-05-12 18:04:08 +0000 | [diff] [blame] | 546 | /* END */ |