gbadev.org forum archive

My knowledge about trigonometry is quite blury so i hope you may help me a little bit :)

I am using the swi 0xA0000 function to get the angle between 2 points. I started to write a test to see if it works for me...

The goal is to display a sprite whenever it is in my frustum (the frustum is defined by an angle from 0...2047 (2047 entry lut for sin and cos)).

Code:

test = (ArcTan2(posX>>17,posY>>17)>>3)-ViewY;

if((test <= 239) & (test >= 0)) {
//visible
sprites[4].attribute0 = A0_COLOR_256 | A0_SHAPE_SQUARE | (40);
sprites[4].attribute1 = A1_SIZE_8 | (test);
sprites[4].attribute2 = A2_PRIORITY(0) | (512+64);
} else {
//invisible
sprites[4].attribute0 = 160;
sprites[4].attribute1 = 240;
}

well, posX and posY is in this format:
IIII IIII IIFF FFFF FFFF FFFF FFFF FFFF

I = integer
F = fraction

i shift it down 17 bits because the docu said that the function will take a 16 bit value with 1 bit sign, 1 bit integer and 14 bit fraction (i shift by 17 and not by 16 because posX and posY is always positive).

ViewY is the rotation of my camera. I thought that after subtracting it from the angle between (0,0) and (posX, posY) i would get the X coordinate because each column of my screen represents 1 "degree" of my custom sin/cos function.

Well, of course it doesn't work ;(
I have no clue how to get it work but i think i do something very simple very wrong :P
Please tell me how to work with arctan2...

Last edited by Lupin on Sun Mar 21, 2004 8:50 pm; edited 1 time in total

I can see a couple of things that might cause problems

1) if posX and posY are 10.22 fixeds, the shifting it down 17 notches makes them 27.5 fixeds, and not .14 fixed that arctan wants. But this hardly matters, since ArcTan2 calculates atan(y/x), so the fixed point is divided out anyway.

2) what does matter is what types you use in your definition of the function ArcTan2. what I use is

Code:

s16 ArcTan2(s16 x, s16 y)
{ asm("swi 0x0a"); }

which seems to work fine. If you use standard ints or (or any unsigned types), get ready to be amazed.

3) Uhm, that single "&" in the if statement makes me very nervous.

4) the angle that arctan returns is between -0x4000 and +0x4000, which you don't want to write into OAM as the x coordinate. I know that's what the if is for, but I thought I'd mention it anyway.

I have modified my swi_demo to use ArcTan2 as well. See http://user.chem.tue.nl/jakvijn/tonc/swi.htm for details.

Just some thoughts on the angle of a line topic since I happened to be working on this over the last 2 days.

How fast is ArcTan2 on the GBA? The following function uses a atan lookup table, which is portable, but Im unsure how the GBA code does it. Uses one divide. I've included the tablegen code for reference. Obviously you would have to convert the table to a C/C++ array.

Code:

#define ABS(A) ((A)<(0)?-(A):(A))
#define f2i(A) ((A)>>8)
#define i2f(A) ((A)<<8)
#define fixdiv(A,B) (i2f(A)/(B))

#define DEG_1 i2f(1)
#define DEG_45 i2f(32)
#define DEG_90 i2f(64)
#define DEG_180 i2f(128)
#define DEG_270 i2f(192)
#define DEG_360 i2f(256)

/*
** Name: fixangle
** Desc: Returns the angle of a line. Angles are defined as
** (u16)(0...65536) = 0..360 degrees. Which means they fit into u16's
** and wrap nicely without using AND's. Plus you have ample fractional
** bits for angular velocity. X & Y position uses 24:8 fixed point maths.
*/
u16 fixangle(int x, int y)
{
static int table[32768];

if (!table[100])
{
int i;

for (i = 32768; i--;)
{
table[i] = atan(i * M_PI / 180.0) * 256.0 * 8192.0 / 360.0;
}
}
if (y || x)
{
int yabs = ABS(y), xabs = ABS(x);
int degs = xabs <= yabs ? table[fixdiv(xabs, yabs)] : DEG_90 - table[fixdiv(yabs, xabs)];
return x < 0 ? y < 0 ? degs - DEG_180 : -degs : y < 0 ? DEG_180 - degs : degs;
}
else
{
return 0;
}
}

On the speed issue. The best "point in frustum" check is via dot products.

Code:

int cx = 200; // Camera X
int cy = 200; // Camera Y
int angle = 0; // Camera view angle. ie Turn.

// These should be lookup tables. Demo code only :-)
int lx = cos(DegToRad(angle - 25)) * 256; // Left plane X
int ly = sin(DegToRad(angle - 25)) * 256; // Left plane Y
int rx = cos(DegToRad(angle + 25)) * 256; // Right plane X
int ry = sin(DegToRad(angle + 25)) * 256; // Right plane Y

// Convert world test point to camera relative position.
X -= cx;
Y -= cy;

// A couple of dot products detects a points visiblity.
int isvisible = (ly * X - lx * Y) < 0 && (rx * Y - ry * X) < 0;

Worst case = 4 lookups and 4 multiplies.
Best case = 2 lookups and 2 multiplies.
(if lookups are merged into the test)

Would be great for a large number of point tests, and if the FOV is 90 degrees, then the equation breaks down to 4 additions/subtractions.

Variable FOV is achieved via multipling the matrix using 3 multiplies per loop.

Hope that helps. I actually found it tuff to find a fast working arctan2 function.

Derek

Assume it's not too fast. :)

Ok, i tried a lot of different arctan functions including the bios one of course but for now it seems like my own atan2 function works best.

How it should work: Every column of my screen represents 1 degre in my sin/cos LUT (0...2047) and i cast my rays for my voxel renderer using these columns (thus giving me 1 slice of terrain for each column). Now i want to render sprites and i thought i would just a) Get the angle from my current position to the sprite b) check if the sprite lies within my cameras frustum and then just draw it

How it works now: it displays the sprite now but when i move my camera left or right it moves way too fast and it doesn't look like the sprite is stuck to a specific point of the terrain (since the sprite is a tree that's really bad :)).

Now please take a look at this:

Code:

//The sprite should be in the middle of the map
//posX is XXXX XXXX XXFF FFFF FFFF FFFF FFFF FFFF
//where X is integer and F is decimal part
//The shift is just because for preventing overflow
a = ((s32)(posX>>12))-0x7F000;
b = ((s32)(posY>>12))-0x7F000;

//ArcTan2 return values:
//If the sprite is right above the position it should be 2048, if you move the sprite clockwise around the position it goes from 2048 to 0
//I don't really know why i subtract 1024 here but it seems to work better :)
test=((-ArcTan2(b,a) - 1024) & 0x7FF) - ViewY;
a >>= 10; //shift down because ^2 would overflow the value
b >>= 10;
//This is like projection calculation, don't pay attention to this because it works :)
//persp is a divide LUT with 12 bit precission
//CamHeight is just for fake up/down "rotation"
//the (s32) is redundant because 128-384 is signed
d=CamHeight - ((s32)((128-384) * persp[iSqrt(a*a+b*b)])>>12);

//Test if the sprite is outside of the screen (but don't clamp half visible sprites, that's why i test with -64)
if((test <= 239) && (test >= -64)) {
sprites[4].attribute0 = A0_COLOR_256 | A0_SHAPE_TALL | (d&255);
sprites[4].attribute1 = A1_SIZE_64 | (test&511);
sprites[4].attribute2 = A2_PRIORITY(1) | (512+100);
} else {
sprites[4].attribute0 = 160;
sprites[4].attribute1 = 240;
}

To test the result by yourself just run... http://home.arcor.de/lupin003/test.bin ... in emulator and move around a bit and see what happens. You should see the sprite if you move the camera angle down a bit and just rotate around.

You can find the ArcTan2 code here: http://home.arcor.de/lupin003/arctan2.txt

any help would be greatly appreciated!
_________________
Team Pokeme
My blog and PM ASM tutorials

Hi Lupin,

Very nice demo. But, is that a arctan function? Looks like a slope of line function to me, but I could be wrong.

Problem is, If you had 100 trees, are you saying you are planning on 100 atans & 100 isqrts just to find the visible ones?!

Couldn't you use your raycasting to find the visible trees & objects + z-order? ie: a second terrain map with entity id's. Check the entity map to see if a tree should be rendered at the current ray position.

Lets say your ray is rx & ry and your screen pos is sx & sy.

Code:

if (entity_map[f2i(ry)][f2i(rx)] == ENTITY_TREE)
{
// position tree sprite at sx, sy
}

Im guessing you also have a depth that could be used to scale the tree as well.

Yeah, i already thought about that Derek, but that would mean i would have to check for entities in every step of my ray and this approx like 120*256 times and it's also possible that my rays won't hit the entitie and don't grab the information of it (because the rays are spreading in distance). I would have to use a low precission entity map to avoid missing some of the sprites but that would force me to do extra calculations.... i think i won't come away with less than 4 additional opcodes per step of my ray (and you also have to take the branch into account when the sprite is invisible)...

Of course i am going to add scaling to the sprites, but i didn't yet bother with it (though i know how to do it :))
_________________
Team Pokeme
My blog and PM ASM tutorials

Yea, I though those might be problems after I posted, but you can still use the idea in a secondary ray casting algorithm for entitiy management.

1) For yeti3d (and previous terrain engines I've written), I shoot rays out to collect a visible cells list. I also tag/mark each cell with the current frame count.

2) I then iterate the entities, grab the cell pointer the entity is in and compare the current frame count with the one stored in the cell to see if the entity is visible.

3) If the entity is in a visible cell, I then rotate the entity and add it to the cell entity link list based on Z. Its just a insertion sort.

4) I can then iterate the cell VIS (which is just an array of XY's) and iterate the link list in each cell to render the entities in the correct order. The view space XYZ coords are stored in each entity from step (3) so its just a simple projection.

This system doesn't bog down and should work for both mode 7 and voxel engines.

*****

But, on second thought. It would probably be easier to use the 2 frustum vectors and use 2 2D dotproducts to get a entities visiblity before rotation/projection. But, then with a large number of visible entities you will have a larger sorting task.

Should be fine for this task.

[quote=Derek]Very nice demo. But, is that a arctan function? Looks like a slope of line function to me, but I could be wrong. [/quote]
I was wondering about this too ... is there a LUT access in here somewhere that we're not seeing here too?

Anyway, about the demo itself. I've been playing with it for a while and it almost seems as if the sprite's rotation is around a point somewhere in the distance. I've traced the way that the tree moves (see voxspr1.png and voxspr2.png). The tree does follow the terrain, but, like I said, seems to be moving in a circle around a point in far view, but it's kinda hard to tell what's going on exactly. Maybe debugging would be easier if with a flat map (preferably with grid-lines) and a big red dot where the tree is supposed to be.

Also, erm, there are three coordinates that you have to take into account: the world-system, the camera system (both 3D) and the GBA screen coordinates (2d, seems cylindrical coords, what with the angles and everything). In which system are posX and posY? They should be in the camera system, but I can't tell from the provided code. Also, I'm not too sure about why you need the length of (a,b); shouldn't this be a dot-product with the view-direction or something?

I set up a simple test for my atan2 function. Please don't kill me for using VB for a simple test app, but it proves that my atan2 function works (at least it should work because the code i used in this sample is a direct port from my asm code).

I tried to work out the math behind it and it seemed to work with my test app, but as i tried to port it to gba it didn't want to work :(

http://home.arcor.de/lupin003/atan2test.zip

I can send you the full source via mail if you want to help me (i don't want to publish it public).
_________________
Team Pokeme
My blog and PM ASM tutorials

Interesting. The function does seem to return an approximate arctan2. The angle returned seems to pan arround the true angle by about 4 degrees. I'll have to check that. Cool. So, I converted the code to C.

Code:

/*
** Name: lupin_arctan2
** Desc: Returns an approximate arctan2 angle.
** Angles are 0..2048 = 0..360 degrees
** AND the result by 2047 to clip.
*/
int lupin_arctan2(int y, int x)
{
int a = ABS(x);
y = y < 0 ?
1792 - (y + a) / ((a - y) >> 8) :
1280 - (y - a) / ((y + a) >> 8) ;
return x < 0 ? -y : y;
}

I then wrote a quick plugin for my fixangle() function used in Yeti3D.

Code:

u16 fixangle(int x, int y)
{
return lupin_arctan2(-y << 8, -x << 8) << 5;
}

Works a treat! Mmm, kinda. Im using this for a 3rd person camera view. The function works perfect for a 2D rotation camera, but has wobble/shuttering problems with a 3D camera. ie: When I get both the turn and pitch angle of the view vector, the angles returned cause the camera to "kick" since the wobble is added in 3D. In 2D it looks like a smooth "sin wave"-ish offset.

**EDIT** Actually, the shuttering might be an unrelated bug. Maybe

But, yea. cool. Learn something everyday. This would be valid for a 2D 3rd person view like a mode 7 car game. But, the arctan LUT version isn't that much slower, produces nicer camera movement and is only called once to setup the camera matrix.

I'd still use the dotproduct method of determining visible sprites. I'll see if I can code something generic tommorrow. The code should be able to rip though hundreds of entities without a single divide or function call.
_________________
Yeti3D Portable 3D Engine

How about this. Shift up by 8 bits before the divide. Looks a little smoother but it could just be the late hour.

Code:

int lupin_arctan2(int y, int x)
{
int a = ABS(x);
y = y < 0 ?
1792 - ((y + a) << 8) / (a - y) :
1280 - ((y - a) << 8) / (y + a) ;
return x < 0 ? -y : y;
}

So the final code becomes:

Code:

int lupin_arctan2(int y, int x)
{
int a = ABS(x);
y = y < 0 ? 1792 - fixdiv(y + a, a - y) : 1280 - fixdiv(y - a, y + a);
return x < 0 ? -y : y;
}

u16 fixangle(int x, int y)
{
return lupin_arctan2(-y, -x) << 5;
}

crazy stuff, can a arctan2 be this simple !
_________________
Yeti3D Portable 3D Engine

well, but you got to be aware of evil overflow errors if your input values are fixed point :)

For me even this is not giving better results:
y = 1792 - ((((y + a)<<16) / ((a - y)))>>8);
_________________
Team Pokeme
My blog and PM ASM tutorials

I started to create a little game structure (an array with enemies) and i tried to tidy up my code :)

Well, here is what i got and it's (of course) still not working as it should:

Code:

nRotations = 0;
nSprites = 4;
for(i=0;i<32;i++) {

//positions are all 9.23 bit fixed point (that's why i shift down here)
a = (s32)(posY>>16)-(s32)(Enemies[i].y>>16);
b = (s32)(posX>>16)-(s32)(Enemies[i].x>>16);
//AcrTan3 = bios atan2
test = (((ArcTan3((s16)a,(s16)b)>>5)-1024) - ViewY) & 0x7FF;
//Shift down to decimal bits (9 bits) because of ^2
a >>= 7; b >>= 7;
c = (iSqrt(a*a+b*b));

//"far-" and "near-cliping"
if((c <= 256) && (c >= 32)) {
//Perspective calculation (that's not mathematical correct at all, but looks ok)
d= ((s32)((384-0x200) * persp[128+c>>1])>>12)-16;
//Sprites are 32x32, get the center by x=x-16
test = test - 16;

//If the sprite is still on screenY
if(d < (160+16)) {
//if the sprite is still on screenX (how to check for X<0 here? Because x<0 would result in test being something like 2047 (2047=-1, 2046=-2, 2045=-3... bla) this happens because of the AND i am using above
if((test <= 239)) {
sprites[nSprites].attribute0 = A0_COLOR_256 | A0_SHAPE_SQUARE | A0_SIZE_DOUBLE | A0_ROTATION_FLAG | (d&255);
sprites[nSprites].attribute1 = A1_SIZE_32 | A1_ROTDATAINDEX(nRotations) | (test&511);
sprites[nSprites].attribute2 = A2_PRIORITY(1) | (512+INTERCEPTOR_START);
//perspective scaling
rotData[nRotations].hdx = 96+c;
rotData[nRotations].hdy = 0;
rotData[nRotations].vdx = 0;
rotData[nRotations].vdy = 96+c;
nSprites++;
nRotations++;
//this is my attempt of checking for negative x values (but it really sucks :))
} else if(((test-2048) >= (-48)) && (test > 1808)) {

sprites[nSprites].attribute0 = A0_COLOR_256 | A0_SHAPE_SQUARE | A0_SIZE_DOUBLE | A0_ROTATION_FLAG | (d&255);
sprites[nSprites].attribute1 = A1_SIZE_32 | A1_ROTDATAINDEX(nRotations) | ((test-2048)&511);
sprites[nSprites].attribute2 = A2_PRIORITY(1) | (512+INTERCEPTOR_START);
rotData[nRotations].hdx = 96+c;
rotData[nRotations].hdy = 0;
rotData[nRotations].vdx = 0;
rotData[nRotations].vdy = 96+c;
nSprites++;
nRotations++;

}
}
}
}

The result can be viewed here: http://spacecruiser.sourceforge.net/voxel.gba
_________________
Team Pokeme
My blog and PM ASM tutorials

It seems that when you rotate, near object move in the right direction, but further away off there's trouble. There's a freaky sign inversion going on somehwere, but I'm not eactly sure what it is right now. I'm guessing it's something to do with the line

Code:

test = (((ArcTan3((s16)a,(s16)b)>>5)-1024) - ViewY) & 0x7FF;

Here's what I think the intermediate ranges are:

Code:

alpha = atan(a,b)

alpha: <-4000h, +4000h> // represents open range <-pi/2, +pi/2>

2s comp: <c000h, 4000h> // <-4000h, +4000h>
>>5: <fe00h, 0200h> // <-0200h, +0200h> are you sure it shouldn't be >>4 ?
-0x0400: <fa00h, fe00h> // <-0600h, -0200h> both are negative!
viewY=0: <fa00h, fe00h>
&0x07ff: <0600h, 0200h> // <+0600h, +0200h>, signes are inverted!

Unless I made a mistake here, the AND at the end inverts the signs which is exactly what the end result looks like. But, since close-by everything seems to work OK, there's probably something else as well. Anyway, instead of shifting down the result of ArcTan3, you could also shift viewY up, do all the difference-calculations and the <i>shift</i> test down instead of ANDing it. If you use signed integers throughout, this should extend the sign bit as well, so you can test negative values like you wanted to in the first place.

Two other things, by the way: the arctan of y/x (which is what the BIOS ArcTan2 does) gives the counter-clockwise angle between the vector (x,y) and the x-axis. I have a feeling that your viewY angle is the clock-wise angle between the heading and the y-axis. This may be part of the problem as well.
The other thing concerns the line

Code:

d= ((s32)((384-0x200) * persp[128+c>>1])>>12)-16;

You <i>do</i> know that in C addition takes precedence over shifting, right? Are you sure (128+c)>>1 is what you want?

gbadev.org forum archive

Coding > Ongoing problem with arctan2/sprite rendering

#17775 - Lupin - Sun Mar 14, 2004 5:48 pm

#18005 - Cearn - Thu Mar 18, 2004 10:10 am

#18041 - Derek - Fri Mar 19, 2004 5:21 pm

#18048 - Miked0801 - Fri Mar 19, 2004 7:20 pm

#18145 - Lupin - Sun Mar 21, 2004 8:39 pm

#18183 - Derek - Mon Mar 22, 2004 2:15 pm

#18187 - Lupin - Mon Mar 22, 2004 2:57 pm

#18192 - Derek - Mon Mar 22, 2004 4:03 pm

#18279 - Cearn - Tue Mar 23, 2004 3:18 pm

#18283 - Lupin - Tue Mar 23, 2004 4:58 pm

#18292 - Derek - Tue Mar 23, 2004 6:38 pm

#18297 - Derek - Tue Mar 23, 2004 7:09 pm

#18305 - Lupin - Tue Mar 23, 2004 8:30 pm

#18655 - Lupin - Wed Mar 31, 2004 12:38 am

#18675 - Cearn - Wed Mar 31, 2004 3:36 pm