ANGLE interpolation

[vreuzon]

I'm facing a problem with some ANGLE calculation.

ANGLE is the 16 bit type used by the SGL to store angle values. All values are between 0 and 2*pi, represented by 0x0000 and 0xffff. pi/4 is 0x2000, pi/2 0x4000, etc.

What I want is to compute N interpolations between two angles a1 and a2.

for the interpolation i (i [0..N]), i have the angle a_i

a_i = a1 + i*(a2-a1)/N

The problem lies in the (a2-a1)/N part: As it makes no sens using float or int division, how can I divide the ANGLE value by the integer N ?

Any idea ?

 

[TakaIsSilly]

Well, my kind of lame idea is that you use right shift, ie.

a_i = a1 + i*(a2-a1) >> N

Would divide by 2*N at great speed gain. Another solution : there's documentation about a hardware divider solution using the DSP on the .txt files that come with the Saturn compiler (not with SGL), that calculates divisions using 30 clock cycles. I didn't really gasped the whole concept of the question, but I belive you meant this sort of solutions.

 

[Taelon]

Wouldn't a simple DIV operation (the counterpart of a MOD one) do the trick? Integer division disregarding the remainder? Perhaps that's what he needs.

But yeah, I had trouble actually understanding the whole question as well. My math is rusty...

 

[antime]

vreuzon: if I've understood correctly, you're worried about what happens when a_i gets small? One solution is to do the math using 16.16 fixed-point values. Also, if you're doing lots of these calculations, precompute (a2-a1)/N and then multiplicate the value with the step number (alternatively just add it for each step).

TakaIsSilly: the external divider is one of the peripherals of the SH7604, not the DSP. The manual has details on how to use it, dunno if Sega implemented some special support in their libs.

 

[TakaIsSilly]

TakaIsSilly: the external divider is one of the peripherals of the SH7604, not the DSP. The manual has details on how to use it, dunno if Sega implemented some special support in their libs.

.Oh, sorry. As I often state, I've not been reading the documentation recently. Anyway, there is minimal support, ie. a sample in how to use it using C is on the docs folder of the leaked compiler.

As for values too small, an ANGLE value of 0x0001 translates to something like 0.005 degrees, what should suffice for pretty mutch any interpolation purposes on a slow machine as a Saturn, as far as I could understand

 

[vreuzon]

Let me clarify the problem by adding some incorrect code:

ANGLE initial_ang = 0x0000; // 0 degrees

ANGLE final_ang  = 0x4000; // 90 degrees

...

ANGLE interpolate_angle(ANGLE i_angle, ANGLE f_angle, int nstep, int step) {

	ANGLE result;

	result = i_angle + step * (f_angle-i_angle) / nstep // won't work, afaik

	return 

}

...

void main (...) {

 int i;

 ANGLE r_angle;

 for (i=0;i<10;i++){

	r_angle = interpolate_angle(initial_ang,final_ang,10,i);

	// do something with r_angle

 }	

}

As you can guess, interpolate_angle is the function I'm trying to implement.

Taleon : I think I can't use an integer division beacause ANGLES are not integers. I don't know what a cast from ANGLE to int would look like because int is signed and ANGLE is not.

Antime : Not only when i_angle gets small. I think it never works. Ok for the one time calculation of reused elements.

TakkaIsSilly : Yes, I think I'll eventually use the shift operator, but I'd like to have an exact solution, just in case it is fast enough... not to mention the use of quaternions...

I think ANGLE is seen like a float by the compiler. Right ?

 

[antime]

Your code works fine. Small testapps are good for confirming whether something works or not:

#include <stdio.h>

typedef signed short ANGLE;

ANGLE interpolate_angle(ANGLE i_angle, ANGLE f_angle, int nstep, int step)

{

    ANGLE result;

    result = i_angle + step * (f_angle-i_angle) / nstep;

    return result;

}

int main(void)

{

    int i;

    signed short r_angle;

    for (i = 0; i < 10; i++)

    {

        r_angle = interpolate_angle(0x0000, 0x4000, 10, i);

        printf("%x\n", r_angle);

    }

    return 0;

}

The only thing you have to make sure is that you get the datatypes right. Fortunately GCC for SH2 uses the same types as most 32-bit CPUs, so there's only the user-defined types left to figure out. (SGL defines ANGLE as a Sint16 and Sint16 is defined as a signed short.)

 

[TakaIsSilly]

I've checked as well, and ANGLE is indeed a Sint16... This is somewhat strange... since this means angles are to be mesured measured from -pi to pi, not 0 to 2*pi (0 to 360) as decribed in the documentation. Anyway, this matters little, pi and -pi are basicly the same angle so value operations are carried out as expected.

The compiler will treat it like an integer as well ... Yet, division based on shift will work correctly only on the values 0x0000 to 0x7FFF, since higher values are signed.

 

[vreuzon]

I may be wrong, but when the / operator is used with signed int, the sign is treated a special way. ANGLE beeing signed 16 bits internaly does not give its "negative" values (which are not representing negative angles) the same meaning as in a true signed 16 bits int (Are negative values using two's complement, one's complement, or what ?).

That makes me think it won't work for all values, especially for those representing negative values in normal int16. But there might be some magic in it... I'll try to test it using slPrintHex.

 

[vreuzon]

takaissilly : ok. I had not seen your last post before I answered. I'm not sure whether there's an error in the doc or not. There might be no relation between the represented angle's sign and the potential ANGLE sign (int16 sign).

 

[antime]

I think I see what you mean. An easy fix is to change the interpolation function to use unsigned shorts.

TakaIsSilly: I think GCC specifies that right-shifting signed values will use arithmetic shift. It's however something that must be kept in mind when porting to/from other compilers and platforms. But in any case, micro-optimizing is a bit unnecessary here as the division only has to be carried out once; store the result of (f_angle - i_angle)/nstep and for each loop iteration calculate i_angle+step*step_angle. You can also avoid the multiplication by just adding step_angle to i_angle and accumulating the result.

 

[vreuzon]

I'll try it :

ANGLE interpolate_angle(ANGLE a_i, ANGLE a_f, unsigned short ns, unsigned short s) {

 ANGLE result;

 unsigned short i,f,r;

 i = (unsigned int) i_angle;

 f = (unsigned int) f_angle;

 r = i+s*(f-i)/ns;

 result = (ANGLE) r;

 return result;

}

Ok for you ?

 

[Reinhart]

The SGL has some math related fonctions, including angle conversion ...

It is in the SGL Developer's manual reference nearly page 100.

Maybe you have already check and it's not usefull for your purpose.

Another idea come to me ...

Can something like toFIXED(N) can do the trick ?

It is what I use to get integer value ?

Please don't flame if I'm completely off topic

 

[vreuzon]

Using sine/arcsine and cos/arcos is another way to do the interpolation using FIXED, but it would be much longer to convert angle to 2 lengths, interpolate the 2 lenghts and go back to ANGLE.

But it might be much easier.