gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Where on rotated line (slope rounding)?

#176039 - LOst? - Sun Mar 27, 2011 12:33 pm

I want to understand why it is sometimes good to do this in a fixed point multiplication (example uses n.12 fixed point):

Code:

Result = (A * B + 0x800) >> 12;

/****Testing******
A = 0x2000; // 2.0f * 4096.f
B = 0x0800; // 0.5f * 4096.f

C = A * B;
C == 0x1000000; // 1.f * 4096.f * 4096.f

C += 0x800; // 0.5f * 4096.f
C == 0x1000800; // ------------------Why??

C >>= 12; // (float) C / 4096.f
Result = C;
Result = 0x1000; // 1.f * 4096.f
****************/


And sometimes, it is not good at all! It all depends on the situation. But I haven't been able to figure out why. And I have never seen any explainations to it.

If you don't understand at this point, I don't know if you should waste time trying to figure it out. I am mainly asking if some of you program this way, and know why you do it :P

Now, according to THE source that I learned this from, it also uses a simular thing when trying to figure out where on a rotated line you are:

Code:

A = Pos * YDir + 0x800;
B = ((A << 12) / XDir) + 0x800;
Result = B >> 12;


It yields a different result from how I used to do things:

Code:

Slope = (YDir << 12) / XDir;
Result = (Pos * Slope) >> 12;


I am so damn curious to why THE source I learned this from uses this kind of rounding!

I am trying to rewrite my own slope formula to be compatibe with the "rounded?" one, and the problem is that "Slope" has already been pre-calculated, so that I can just do "Pos * Slope" to get the "Result" without having to do a divide. But I am having trouble when trying to get the same result as the OTHER one, as it multiplies Pos with YDir, applies that 0.5f rounding, etc, etc.
The biggest difference is +/- 1 unit, and is hardly visible anyway in my case. But I am still curious!
_________________
Exceptions are fun

#176041 - Dwedit - Sun Mar 27, 2011 1:34 pm

When you do stuff in fixed point, you usually need to add something to the fractional part, so that you can get your original value back.

For example, in a 32.32 fixed point number, let's write down 1/3.
0x55555555
Multiply that by 3, and you get 0xFFFFFFFF, which is not quite 0x100000000.
Add 1 to 0x55555555, then multiply by 3, and you get 0x100000002, which gets you back your original integer part.

You usually use this technique when you are trying to accurately do integer division the fast way. Whenever your compiler does 32-bit integer division by a constant, it rewrites it as a long multiplication, followed by a right shift. Example: dividing by 5 multiplies by 0xCCCCCCCD, then shifts right 2. You can leave out the right shift if you don't need accuracy for the full range of integers, and just multiply by 0x33333334 to divide by 5, but that's inaccurate past 0x40000000. THUMB mode does not have the long multiplication instruction available, so division by a constant is much slower in THUMB mode.

But the technique of adding AFTER doing the multiplication sounds more like someone multiplied 3 by 0x55555555, then tried to fix it by adding AFTER the multiply to get 1.0 again. Sloppy.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."

#176052 - Miked0801 - Mon Mar 28, 2011 5:55 pm

Another way to think of it is: Computers always truncate when they run out of precision bits. In order to change a truncate to a round, you need to add 0.5 to the result. The 0x800 you see there is the value used to round.

Or, you can skip the rounding part and change your logic to always expect truncated numbers. Though, often this causes more problems than the simple 0.5 add.