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 > A question about accuracy

#33982 - ProblemBaby - Tue Jan 11, 2005 10:51 pm

Hi

for example if I want to find out the slope of a line and represent it with a fixed integer how can I find what format I should use if I always want exact results.

for example:
I know that the difference in x never will be greater then 256
and I also know that the difference in y never will be greater then 64

how much accuracy do ? need for to always get exct results for y when I do (x*slope)>>acc .

And how do I find an accuracy that works for all possible numbers if I know the intervals.

Hope ou understand what I mean!
thanks in adv

#33985 - DekuTree64 - Tue Jan 11, 2005 11:32 pm

There is no perfect accuracy. You can always get things like 1/3, which repeats infinitely. What is it you're trying to do? You may be able to run operations on your lines just storing the slope as a fraction, with two seperate variables (ala Bresenham line drawing)

EDIT: On second thought, I think there would be a certain range of accuracy that would work, as long as you round off your answers rather than truncating.
For example, if your line is 150 wide and 50 tall, you'll get a slope of 1/3. Anytime you truncate (or round) to binary, you'll get something slightly smaller. Going with 16-bit fixed-point, you'd get (65536*50)/150 = 21845. Then multiply that by 150 again and divide by 65536 and you get 49.9992... You'll never get at/above 50, but you can round it.

Nothing's coming to mind on how to figure the range though. My gut says the fraction will need to be either the sum of the bits in both, or maybe 1 more bit than the larger of the two (because of the rounding), but I have no evidence at all to back either one of those up.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku

#34089 - AnthC - Thu Jan 13, 2005 1:41 pm

ProblemBaby wrote:
Hi

for example if I want to find out the slope of a line and represent it with a fixed integer how can I find what format I should use if I always want exact results.

for example:
I know that the difference in x never will be greater then 256
and I also know that the difference in y never will be greater then 64

how much accuracy do ? need for to always get exct results for y when I do (x*slope)>>acc .

And how do I find an accuracy that works for all possible numbers if I know the intervals.

Hope ou understand what I mean!
thanks in adv


If we represent a 2d line in real format we get

A1+B1*t

(where t is an integer number of iterations A1 is start B1 is slope)

In similar way, if we represent a line in space in fixed point format we also get

A+B*t

Where A is floor(A1*FPM) and B is floor(B1*FPM)

FPM (fixed point multiplier) in your case would be 256 or if you are using 16:16 numbers it would be 65536

We can form an error term (e) and work out how the error behaves as we iterate

error= actual - approx (scaling A, B by 1/FPM so they are compatible)

e=A1+B1*t - (A+B*t)
e=A1-A/FPM+(B1-B/FPM)*t

You can see that this is just a function like your straight line, so the error should get larger as we iterate.

Now you want to know when your error is >=1

1=A1-A/FPM+(B1-B/FPM)*t

1-A1+A/FPM = (B1-B/FPM)*t
t=(1-A1+A/FPM)/(B1-B/FPM)

t*FPM = (FPM-A1*FPM+A)/(B1*FPM-B)
t=((FPM-A1*FPM+A)/(B1*FPM-B))/FPM

Hope this is correct + helps :)
Anth

#34105 - ProblemBaby - Thu Jan 13, 2005 6:09 pm

Thanks both of you