What options for distance in raycasting?
category: general [glöplog]
It seems to me one of the slowest parts of raycasting is checking the distance to the wall.
Most implementations use square root to find the distance.
Its also pointed out in the permadi tutorial that you can use the angle and sine to work out the hypotenuse which will be the distance.
I'm looking to implement this on an 8bit CPU. I'm looking for opinions on how best to do this.
Do I use the sine trig method, which needs a divide?
Or do I look at approximations of distance?
will an approximation be adequate , or is it going to end up looking really bad ?
Just wondering if anyone has tried before I dive in!
Most implementations use square root to find the distance.
Its also pointed out in the permadi tutorial that you can use the angle and sine to work out the hypotenuse which will be the distance.
I'm looking to implement this on an 8bit CPU. I'm looking for opinions on how best to do this.
Do I use the sine trig method, which needs a divide?
Or do I look at approximations of distance?
will an approximation be adequate , or is it going to end up looking really bad ?
Just wondering if anyone has tried before I dive in!
Some ideas:
* check where squared distance is sufficient
* if you do not need a free directional view (that is, only 4 directions, maybe also some diagonals) you can resort to single axis linear distance and scale it horizontally depending on the distance form the horizontal center (easy lookup)
* exploit grid regularities where available: once a wall is found you can calculate the rendered columns for start and end in the current grid and interpolate in between
* check where squared distance is sufficient
* if you do not need a free directional view (that is, only 4 directions, maybe also some diagonals) you can resort to single axis linear distance and scale it horizontally depending on the distance form the horizontal center (easy lookup)
* exploit grid regularities where available: once a wall is found you can calculate the rendered columns for start and end in the current grid and interpolate in between
What I did was a bit of look up tables, but it's a small one.
Since a ray jumps constant steps from one block horizontal edge (or vertical for the second case) to the next, these distances are constant for one angle. So, i make a look up table of 16bit fixed point distances for the whole 360 degrees (I preclac 256 angles fitting the circle just because I prefer page aligned tables). One for distances between horizontal block steps and one for vertical.
So during most steps, depending on the ray angle I can pick up the stable distance I have to add as fixed point to a distance sum for every step. The only little problem is with the first step where the player is inside a block in any arbitrary position. If he is at Y=192 and the block edge is at 255, the first distance step is (PrecalcedDistY[angle] * (256 - 192)) >> 8. So it's a percentage of the full one block distance the ray travels. So, I still have to do a mul here, but the next calcs are one 16bit add per ray step. No need to use sqrt anymore.
Maybe I didn't explain it very well and need a shape.
Since a ray jumps constant steps from one block horizontal edge (or vertical for the second case) to the next, these distances are constant for one angle. So, i make a look up table of 16bit fixed point distances for the whole 360 degrees (I preclac 256 angles fitting the circle just because I prefer page aligned tables). One for distances between horizontal block steps and one for vertical.
So during most steps, depending on the ray angle I can pick up the stable distance I have to add as fixed point to a distance sum for every step. The only little problem is with the first step where the player is inside a block in any arbitrary position. If he is at Y=192 and the block edge is at 255, the first distance step is (PrecalcedDistY[angle] * (256 - 192)) >> 8. So it's a percentage of the full one block distance the ray travels. So, I still have to do a mul here, but the next calcs are one 16bit add per ray step. No need to use sqrt anymore.
Maybe I didn't explain it very well and need a shape.
My lut was 256 angles * 16bit fixed * 2 cases (horizontal and veritcal) = 1024 bytes.
Then I still haven't figured out how to avoid one division (or a mul if divide by reciprocal) for fishbowl correction. There is a lot to improve in my again abandoned CPC wolfenstein code (like rewriting some C parts in asm :P).
Then I still haven't figured out how to avoid one division (or a mul if divide by reciprocal) for fishbowl correction. There is a lot to improve in my again abandoned CPC wolfenstein code (like rewriting some C parts in asm :P).
avoid floats and sqrts, use fixedpoint arithmetic or lookuptables.
i used raycasting for pluto128 my 128b voxel landscape, and i only needed one unsigned divide per column and it was really fast. you do most if not all the multiply and divide operations in fixedpoint and on 8-bit cpu one use lookup-tables for most of this.
I bet there are just some minor adjustments to make this work for wall (filled or textured), the basic idea is similar.
One axis is fixed while two are operated on.
For a linear framebuffer a prototype would look something like this:
i used raycasting for pluto128 my 128b voxel landscape, and i only needed one unsigned divide per column and it was really fast. you do most if not all the multiply and divide operations in fixedpoint and on 8-bit cpu one use lookup-tables for most of this.
I bet there are just some minor adjustments to make this work for wall (filled or textured), the basic idea is similar.
One axis is fixed while two are operated on.
For a linear framebuffer a prototype would look something like this:
Code:
1. calculate ray-direction on both axies
2. step/increment the ray
3. check wether the ray has hited a wall:
* if false: jump to 2.
* if true: color or texture it
4. jump to 1.
@ T$ many of those things I can't really do as it is full raycasting, although interpolating the distance if the wall is the same grid of wall I think would be useful. Though you still need to decide if you hit a horizontal or vertical wall first based on which was closer.
@ Optimus
I understand what you are saying a table of distances for full squares on the grid. I'm still a little confused how you worked out the first distance - need to re read what you wrote a few times.
@rudi
floats? what are they lol :) - no chance of that happening:)
@ Optimus
I understand what you are saying a table of distances for full squares on the grid. I'm still a little confused how you worked out the first distance - need to re read what you wrote a few times.
@rudi
floats? what are they lol :) - no chance of that happening:)