0000184: (suggestion) fractional angles and ranges

(0000342)
brad (administrator)
2002-07-17 17:20

Yes I should have done this when I switched the game to use fractional positions. Unfortunately it is too late in the 1.4 development cycle for a change like this. I'll keep this bug around for future work though.

(0000397)
brad (administrator)
2002-08-19 22:21

Actually this would be a big performance hit on the game because now all the trig is table driven.

(0000405)
jamie (reporter)
2002-08-25 18:32

I agree that calling the library sin() and cos() functions would be dog slow. I think I can show that linear interpolation between whole degrees yields a maximum error of about 0.00004, and quadratic interpolation can reduce the worst case error to about 0.00000004 (4.0e-8). I'd be happy to help with details if you decide to implement this in a future version.

(I'm trying to track the leading edge (actually corner) of a robot, and the quantization at long range is somewhat of a problem.)

(0000406)
brad (administrator)
2002-08-26 11:29

That sounds like a decent compromise. Feel free to post the algorithms in a bugnote if you have them handy. When I get back to this I'll test them for accuracy and performance.

(0000521)
jamie (reporter)
2002-12-12 05:13
edited on: 2002-12-12 05:14

For an angle, first make sure it's in the interval [0, 360). Then split it into integer part and fractional part
int angle_ip = (int)floor(angle)
double angle_fp = angle - angle_ip

f0 = g_sinTable[angle_ip]
f1 = g_sinTable[angle_ip + 1] // (btw, make sure sine table goes to 360, not just 359)

then,
C0 = f0
C2 = -((f0 + f1)/4) * PI * PI / (180 * 180) // Actually collapse into one multiplication, but written out long hand here for clarity.
C1 = f1 - C0 - C2

then
answer = C0 + C1 * angle_fp + C2 * angle_fp * angle_fp

I have a spreadsheet that details the accuracy of this method, which I'll send by email. Cosine works exactly the same way. The only difference is using g_cosTable instead of g_sinTable.

edited on: 12-12-02 05:14

(0000522)
brad (administrator)
2002-12-12 10:34

Ok thanks, got the spreadsheet. This isn't going to happen in 1.4, but I will do some perf test and see if this can go into the next version.

(0000825)
jamie (reporter)
2005-07-15 19:22

Even if angles are not fractional in general, they could be fractional for _cldbearing, _pingbearing, and _radiocomm[n]._bearing with no performance penalty.

Issue History
Date Modified	Username	Field	Change
2005-07-15 19:22	jamie	Note Added: 0000825

Notes
(0000342) brad (administrator) 2002-07-17 17:20	Yes I should have done this when I switched the game to use fractional positions. Unfortunately it is too late in the 1.4 development cycle for a change like this. I'll keep this bug around for future work though.

(0000397) brad (administrator) 2002-08-19 22:21	Actually this would be a big performance hit on the game because now all the trig is table driven.

(0000405) jamie (reporter) 2002-08-25 18:32	I agree that calling the library sin() and cos() functions would be dog slow. I think I can show that linear interpolation between whole degrees yields a maximum error of about 0.00004, and quadratic interpolation can reduce the worst case error to about 0.00000004 (4.0e-8). I'd be happy to help with details if you decide to implement this in a future version. (I'm trying to track the leading edge (actually corner) of a robot, and the quantization at long range is somewhat of a problem.)

(0000406) brad (administrator) 2002-08-26 11:29	That sounds like a decent compromise. Feel free to post the algorithms in a bugnote if you have them handy. When I get back to this I'll test them for accuracy and performance.

(0000521) jamie (reporter) 2002-12-12 05:13 edited on: 2002-12-12 05:14	For an angle, first make sure it's in the interval [0, 360). Then split it into integer part and fractional part int angle_ip = (int)floor(angle) double angle_fp = angle - angle_ip f0 = g_sinTable[angle_ip] f1 = g_sinTable[angle_ip + 1] // (btw, make sure sine table goes to 360, not just 359) then, C0 = f0 C2 = -((f0 + f1)/4) * PI * PI / (180 * 180) // Actually collapse into one multiplication, but written out long hand here for clarity. C1 = f1 - C0 - C2 then answer = C0 + C1 * angle_fp + C2 * angle_fp * angle_fp I have a spreadsheet that details the accuracy of this method, which I'll send by email. Cosine works exactly the same way. The only difference is using g_cosTable instead of g_sinTable. edited on: 12-12-02 05:14

(0000522) brad (administrator) 2002-12-12 10:34	Ok thanks, got the spreadsheet. This isn't going to happen in 1.4, but I will do some perf test and see if this can go into the next version.

(0000825) jamie (reporter) 2005-07-15 19:22	Even if angles are not fractional in general, they could be fractional for _cldbearing, _pingbearing, and _radiocomm[n]._bearing with no performance penalty.

Relationships