Dark Bit Factory & Gravity
PROGRAMMING => Freebasic => Topic started by: Stonemonkey on June 03, 2007
-
Been looking into some other ways of doing this and came up with the possibility of adding the magic number before interpolation but it appears to be a bit unstable, I think the divide by z for perspective correction may be making it worse. Any Ideas on this anyone? am I doing anything wrong and could it be made to work? Seems to work fine for this example but it has problems when it's actually used in my rendering although there might be something else causing the problems, i'll keep at it anyway.
option explicit
dim as integer i
dim as double x0,x1
dim as short pointer xi
xi=cast(short ptr,@x0)+2
'start and end values
x0=-10066.00
x1=1767.000
dim as single dx,dy
'number of steps
dy=10.0
'add the magic numbers
x0+=1572864.0
x1+=1572864.0
'interpolate
dx=(x1-x0)/dy
for i=0 to 10
print *xi
x0+=dx
next
sleep
end
-
Actually, it seems to work pretty well linearly but just has problems with the perspective correction.
-
please do keep at it fryer!
its all very intresting!
-
I don't think that will work. When you do an operation on a pair of floats, the scale will change depending on the result. So you need to add the correction in afterwards.
It might be informative to print out the hex version of the float to see what's changing, the top bit is the sign, the next 11 bits are the exponent, and the next 52 are the mantissa.
Maybe:
print hex$(((int ptr)@x0)(0))
Jim
-
The example works as long as the values are within the range of signed or unsigned shorts .... as I was just typing 'not too much of a problem with shading or uv coords' I just realised that I shift the v coord up before the interpolation and that's probably going out of that range.
EDIT: Pretty sure that's the problem, it's just happening with the tiled textures.
-
Bah, wrong again. Too late for this atm anyway.
-
Another example, now with perspective correction and it still seems to be working:
option explicit
dim as integer i
dim as double u0,u1,z0,z1,du,dy,dz,result
dim as short ptr ui=cast(short ptr,@result)+2
'start and end values
u0=-1234.0
z0=1000.0
u1=10255.0
z1=2000.0
dy=15.0
'add the magic numbers
u0+=1572864.0
u1+=1572864.0
z0=1.0/z0
z1=1.0/z1
u0*=z0
u1*=z1
'interpolate
du=(u1-u0)/dy
dz=(z1-z0)/dy
for i=0 to 15
result=u0/z0
print "my_short=";*ui;" double=";result-1572864.0
u0+=du
z0+=dz
next
sleep
end
-
On a slightly different note, while searching for anything related to this I found what is supposed to be quake3s approx. invsqrt, the code in C++
public static float invSqrt(float x)
{
float xhalf = 0.5f * x;
int i = Float.floatToRawIntBits(x);
i = 0x5f3759df - (i >> 1);
x = Float.intBitsToFloat(i);
x = x * (1.5f - xhalf*x*x);
return x;
}
and re written for FB:
function invSqrt(byval x as single)as single
dim as single xhalf = 0.5 * x
dim i as integer ptr=cast(integer ptr,@x)
*i=&h5f3759df-(*i shr 1)
x=x*(1.5-xhalf*x*x)
return x
end function
The FB function is only very slightly faster that using 1/sqr(x) but improves a little bit if it's written inline rather than calling the function.
I've not tried it in c++ yet to do any comparisons but I'm not sure why it uses 'i' when it could use *(int*)&x
-
Anyone know if there's any method similar to the invsqrt above for either dividing or reciprocal, I can use invsqrt for reciprocal but have to square the input first but it still looks like that's at least as fast as just doing the divide. There is a slight error in the results but it's good enough for texture mapping.
-
Another interesting trick for divides:
http://www.stereopsis.com/2div.html
-
Fantastic link. Karma++
-
The fast routine there is using Newton-Raphson approximation (1 level) to get a reasonable approximation for 1/sqrt. I don't think this technique is applicable to division directly.
http://en.wikipedia.org/wiki/Newton's_method (http://en.wikipedia.org/wiki/Newton's_method)
http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ (http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/)
Jim
-
cool stuff, most of the links i found on it didn't even try to explain it. Still, not like i understand it now.
-
Not only can you use the magic number to convert from float to int, but it works the other way too (or at least seems to so far and the high int has to be set first). Probably not much use though.
dim as double test
dim as integer pointer itest
itest=cast(integer pointer,@test)
'convert float to int
test=1659.6555
test+=6755399441055744.0
print *itest
'convert int to float
*itest=98765
test-=6755399441055744.0
print test
sleep
end
Had another thought too, when using pointers, the program has to look up the address of the pointer, read the address stored there and then look up that address. Would using unions be a better idea as it wouldn't need to look up an address to get an address?
EDIT: my idea of int to float doesn't work for negative numbers.
-
Would using unions be a better idea as it wouldn't need to look up an address to get an address?
The only way to tell is to try it and disassemble the results. If you use the value more than once, keeping pointers hanging round is going to win, I would guess.
Jim
-
This is the sort of thing I was meaning:
union float_to_int
{
double in;
int out;
};
image_struct *texture=triangle->texture;
int u_mask=texture->wwidth-1,v_mask=(texture->height-1)*texture->wwidth;
double magic=6755399441055744.0;
union float_to_int convert_u,convert_v,convert_s;
//z_buffer, tiled pc texture lookup and shading
if(z>*z_buffer)
{
*z_buffer=z
zr=1.0f/z;
convert_u.in=u*zr+magic;
convert_v.in=v*zr+magic;
convert_s.in=s*zr+magic;
argb=*(texture->argb+((convert_u.out&u_mask)|(convert_v.out&v_mask)));
*(z_buffer+argb_offset)=((((argb&0x00ff00ff)*convert_s.out)&0xff00ff00)|(((argb&0x0000ff00)*convert_s.out)&0x00ff0000))>>8;
}
And I'm still convinced I can take the magic number addition out of the loop.
-
Sorry, that was from my C++ code, here's how it could be done in FB:
option explicit
union float_to_int_conversion
_in as double
_out as integer
end union
const magic=6755399441055744.0
dim shared as float_to_int_conversion float_to_int
sub main()
dim as single my_float=123.456
float_to_int._in=my_float+magic
print float_to_int._out
sleep
end sub
main()
end
And in this case it does use 1 less memory lookup, whatever difference that might make.
asm output doing the conversion using unions:
fld qword ptr [_Lt_0006]
fadd dword ptr [ebp-4]
fstp qword ptr [_FLOAT_TO_INT]
push 1
push dword ptr [_FLOAT_TO_INT]
push 0
call _fb_PrintInt@12
asm output doing the conversion using pointers:
fld qword ptr [_Lt_0006]
fadd dword ptr [ebp-4]
fstp qword ptr [_DOUBLE_IN]
push 1
mov eax, dword ptr [_INT_OUT]
push dword ptr [eax]
push 0
call _fb_PrintInt@12
-
Are you sure? The 3 pushes at the end of each are the code to put the parameters on the stack for the call to PrintInt. It's not clear in this example whether you've gained anything.
I've been thinking about your technique of adding the conversion factor before the interpolation.
I'm pretty sure that as long as your converted number never changes its power-of-2 (that is, it doesn't double or half during the interpolation), then you will always be OK. I can't see how that could ever happen in your case since the conversion factor is huge in comparison to your interpolates.
The only other possible flaw is you will lose precision every time you do an add because most of the bits are being taken up by the conversion factor.
ie. your mantissa used to look like (for a value of, say, 5)
before
010000...00000000000000000000
^this is the 5
after
100000...00000000000000001000
^this is the correction factor
^ this is the 5
(not accurate bit patterns, just an example)
so instead of having 53bits of precision you may only have 4 or 5.
Jim
-
The line:
push dword ptr [eax]
in the pointers version is pushing the contents of address [eax] onto the stack so it has to load the address into eax then retrieve the data from that address then write it to the stack whereas the version with unions uses an absolute address that it reads from and writes to the stack.
I think the problem with my other method might be due to innacuracy due to the division, I was adding the magic number to the U/V values before the division by z but I think due to there being a very large part (the magic number) and a very small part (the actual U or V) some of the very small part might be getting lost in the division. It's not a huge error but the textures don't line up on adjacent polys and tend to jump/slide about a little bit.
It might still be possible but could involve some shifting or masking which would probably not give much advantage.
-
Your magic is 2^53 + 1/2 x 2^53 (=2^53 + 2^52), which shunts all the remainder of the precise bits down into the lower 32. If your range of numbers is much smaller than 2^(53-32) (+-2Meg) then you're going to be losing bits compared with what you had when you were working in ints. Every operation you do will reduce the precision, especially division.
I guess to get more precision, you could use (say) 2^33+2^32, but then as you say, you'd have to scale the resulting integers after you'd converted them.
Jim
-
Sorry for dragging up an old topic but looking into float->int again and come up with this:
'setup data and unions for floor(float)->short
union floor_float_to_short_data
_float_in as double
type
_pad as short
_short_out as short
end type
end union
dim as const double floor_float_to_short_magic = 2^35 + 2^36
'************************************************************************
dim as floor_float_to_short_data floor
floor._float_in = floor_float_to_short_magic + 15000.999992
print floor._short_out
sleep
end
It floors (not perfect but pretty well) a float to a short so it's in the range -32768>32767
After reading your post there Jim I'm now wondering if this can be used with the magic outside the loop now.
EDIT: seems to work fine.
-
And can now use different magic numbers to give different rounding modes:
'setup data types and unions for rounding to short
union float_to_short
_float_in as double
type
_pad as short
_short_out as short
end type
end union
'magic numbers for different rounding modes
dim as const double floor_float_to_short = 2^35 + 2^36
dim shared as double ceil_float_to_short = 2^35 + 2^36
*cast ( integer pointer , @ceil_float_to_short ) = 65535
dim shared as double nearest_float_to_short = 2^35 + 2^36
*cast ( integer pointer , @nearest_float_to_short ) = 32768
'rounding float to short macros
dim shared as float_to_short round_to_short
#macro round_down(my_float,my_short)
round_to_short._float_in = floor_float_to_short + my_float
my_short = round_to_short._short_out
#endmacro
#macro round_up(my_float,my_short)
round_to_short._float_in = ceil_float_to_short + my_float
my_short = round_to_short._short_out
#endmacro
#macro round_nearest(my_float,my_short)
round_to_short._float_in = nearest_float_to_short + my_float
my_short = round_to_short._short_out
#endmacro
'**********************************************************************
I'd prefer to make them all consts but I can't see how to put in the data, I guess it won't make much difference anyway since const floats aren't assembled the same way as const ints.
The 'nearest' will always round down xx.5
If you change 32767 to 32768 it'll always round up xx.5
I've still to try it in a real situation but it looks like it's possible to do the interpolation including perspective correction with the magic number added beforehand with the fpu almost acting like 16:16 fixed point and the padding could be split into 2 bytes with the high byte giving the fraction for bi-linear filtering.
-
G_triangle function to draw to any buffer given the start address and the buffer dimensions so can draw to any array or whatever. Not really sure about the speed or accuracy so if anyone finds any problems let me know. It uses the idea from above to have 16:16 fixed point in the low 32 bits of the double. I might have a go at doing this in asm.