double limit360(double angle_deg) { double limitedAngle_deg; int m = (int) (angle_deg/360); if (angle_deg >= 360) { limitedAngle_deg = angle_deg-m*360; } else if (angle_deg < 0) { limitedAngle_deg = angle_deg-(m-1)*360; if (360-limitedAngle_deg < 1e-15) { limitedAngle_deg = 0; //360 = 0 } } else { limitedAngle_deg = angle_deg; } return (limitedAngle_deg); }While I was looking at the source code of UFO:Alien Invasion, I found the following function in .\src\shared\mathlib.c (which is part of the 2001 engine by Id Software, now available as open source):

/** * @brief returns angle normalized to the range [0 <= angle < 360] * @param[in] angle Angle * @sa VecToAngles */ float AngleNormalize360 (float angle) { return(360.0/65536)*((int)(angle*(65536/360.0))&65535); }Apart from "360.0", nothing seemed familiar to me. So, I divided the single line into its parts and analyzed them: Let's call 65536 NUM, then the line becomes:

return 360.0/NUM * ((int)(angle * NUM/360.0) & (NUM-1));It first multiplies the angle with NUM/360.0, the casts the result to integer, does a bit-wise "and" operation with NUM-1 and finally divides the number by NUM/360.0. NUM is used to map 360 to 653536. This is done to reduce the truncation loss when we cast the angle to integer. 65536 = 2^16 = (in binary) 10000000000000000. NUM-1 in binary is 01111111111111111. If you do a bitwise "and" with NUM-1, you make all the bits except the first 16, zero. This means that (angle*NUM) & NUM-1 retains only the first 16 bits which in effect is a mod 360 operation. Example:

1. angle = 720+30 2. angle*NUM/360.0 = 136533.33... 3. (int)(136533.33...) = 136533 = (in binary) 100001010101010101 4. 136533 & (NUM-1) = 5461 = (in binary) 000001010101010101 5. 360.0/NUM*5461 = 29.9982.The exact value should be 30. We lost some precision (.33 part) due to the integer casting. To increase precision we should increase the value of NUM. If we choose NUM = 2^20 = 1048576, the result will be 29.9999.

music: * Kool & the Gang - Bad Woman * Zaz - Je veux

## 2 comments:

Benim anlamadığım bir şey var.

Niye mod fonksiyonu kullanılmıyor.

Benim precision problemim hiç evet hiç olmadı :(

El altında bir C compiler yok ama Matlab'da mod(750, 360) 30 donduruyor. mod(-361, 360)'da 359 donduruyor ki bu da istenen sonuç sanırım.

Sanırım bu hali o günlerde (2001) daha hızlı çalışıyordu. O zamanlar işlemciler integer işlemlerini float işlemlerinden daha hızlı yapıyordu.

Bugünkü durumu görmek için bir ara mod operasyonunu (C'de %), if'li algoritmayı ve bit operasyonlu algoritmayı performans açısından karşılaştırmak lazım.

Post a Comment