Sqrt

[sandruzzo]

Hi All,

I'm plaing a little bit with raycasting stuff, and I need a way to perform asqrt on 68000. Can someone help me here?

[chb]

Long thread from the Atari forum:
http://www.atari-forum.com/viewtopic.php?t=4984

From "Dr. Dobb's Toolbook of 68000 Programming":
https://github.com/jefftranter/68000...squareroot.asm

But they might or might not fit your requirements for speed and precision.

[sandruzzo]

Originally Posted by chb

Long thread from the Atari forum:
http://www.atari-forum.com/viewtopic.php?t=4984

From "Dr. Dobb's Toolbook of 68000 Programming":
https://github.com/jefftranter/68000...squareroot.asm

Thanks

[chb]

Probably for a game a table-based approach is preferable, but are you sure you really need a sqrt for the raycaster?

[sandruzzo]

Originally Posted by chb

Probably for a game a table-based approach is preferable, but are you sure you really need a sqrt for the raycaster?

According to this tutorial yes. You need it!

http://lodev.org/cgtutor/raycasting.html

[chb]

Funny, actually because of that tutorial I was asking, as he does not use sqrts in the code AFAICS - except for one instance where he computes deltaDistX rep. deltaDistY and does not apply the simplification he mentions in the text, probably simply because he did not update that piece of code.

[sandruzzo]

Originally Posted by chb

Funny, actually because of that tutorial I was asking, as he does not use sqrts in the code AFAICS - except for one instance where he computes deltaDistX rep. deltaDistY and does not apply the simplification he mentions in the text, probably simply because he did not update that piece of code.

Do you have any better tutorial?

[LaBodilsen]

Originally Posted by chb

Funny, actually because of that tutorial I was asking, as he does not use sqrts in the code AFAICS - except for one instance where he computes deltaDistX rep. deltaDistY and does not apply the simplification he mentions in the text, probably simply because he did not update that piece of code.

Exactly.. i startet work on my raycaster following this tutorial before he updated with the simplification, and then when i looked at it again, i was all confused

but as you mention, he replaced the sqrt with a much simpler ABS(1 / rayDirX). which made my work alot easier, as now we can pre-calc all deltaDistX and Y and use a lookup table.

[LaBodilsen]

Originally Posted by sandruzzo

Do you have any better tutorial?

This one is pretty good to get an understanding of the workings:
http://www.permadi.com/tutorial/raycast/rayc1.html

but the one you are using, is easier to translate to 68k code.

[sandruzzo]

Thanks. I'll get rid of that sqrt!!!

[sandruzzo]

Originally Posted by LaBodilsen

This one is pretty good to get an understanding of the workings:
http://www.permadi.com/tutorial/raycast/rayc1.html

but the one you are using, is easier to translate to 68k code.

I'll start for the easier, then we'll see!

[LaBodilsen]

my approach have been to take the C code, and then write lot's of comment lines with 68k code. eg.

while hit = 0

(
IF sideDistX < sideDistY

#CPM.W sideDistY,sideDistX
#BHI.w sideDistY_Smaller

(
sideDistX = sideDistX + deltaDistX

#Add.w deltaDistX,sideDistX

mapX = mapX + stepX

#Add.w StepX,mapX

side = 0

#moveq #0,side
#BRA CheckMap

that way i can still maintain an overview of the process, and quickly see where to improve (this is only my 4th project since i'm trying to re-learn Assembler after 20 years og abcense). atm i'm only working in the powershell ISE editor (to get syntax highlight), until i'm satisfied with the code. then i will start to move it to Asm-pro.

[kamelito]

Check this book. The author is also working on a book about Doom.
https://www.amazon.com/gp/aw/d/15396...06L&ref=plSrch

[jotd]

ever heard of the fast pseudo-sqrt algorithm? https://stackoverflow.com/questions/...t-optimization

[chb]

Originally Posted by jotd

ever heard of the fast pseudo-sqrt algorithm? https://stackoverflow.com/questions/...t-optimization

I've known only of the probably more well-known fast inverse square root before, but they look very similar. But they work on floating point values and exploit some tricky relation between the binary representation of a float and an integer, so they need a reasonable fast FPU to work well. On the 68000 almost certainly not interesting, maybe more so for 040 or 060.

[Megol]

Well floats are just scaled integers with a funky encoding.
But a lookup table should be faster in this case I think?

[chb]

Originally Posted by Megol

Well floats are just scaled integers with a funky encoding.

Well, of course that's true in some sense, but the fast sqrt exploits the fact that if you take an integer number i and cast it as an IEEE float (so interpret its binary representation as floating point, not converting anything), you are performing a piecewise linear approximation of log2:

f(i) \approx L*log2(i)+ L*log2(B + \sigma)

where L= 2^23, B = 127 and \sigma a constant to improve the approximation. Using this relation, dividing (shifting) an integer number by 2 gives log2(0.5*i) = log2(i)^0.5 = sqrt(log2(i)), so the sqrt of our fp number (I am ignoring the B + \sigma term here for simplicity).

That relation was (at last for me) quite surprising when I saw it the first time, especially as some bits of the integer are interpreted as exponent and some as mantissa. Wouldn't have thought there's something useful to do with it.

So for that reason that algorithm isn't of very much use if you want to work with integers, the conversions to float and back and the fp-operations needed will be quite likely much slower than an integer-only algorithm without a fast FPU, and the fast sqrt is also just an usable, but rather rough approximation.

Originally Posted by Megol

But a lookup table should be faster in this case I think?

Of course, if you have 16 bit values and can afford the 64k (128k for unsigned int) for the table. But as written above, there is no need for a square root here.

[Megol]

Thanks for the explanation! While I have used the "trick" in the past I've never actually looked at how it works.