For doubleanti, Voxel algorithms - very long

[VirtualAce]

Alright been coding this crazy voxel thing for some time now, among other projects. Two or three algo's have stood out.

Both of these algos wrap the ray world coords to the edge of the world, thus the world repeats itself giving a continuous landscape.
The 3D matrix idea does not repeat since all you are doing is drawing vertexes at set points in screen space based on x,y,z of voxel - (x*viewdist)/z+halfvertres; (y*viewdist)/z+halfres; where viewdist is distance you are from the screen - flattens projection.

Floating horizon
First is the floating horizon. Basically start at the player's world coords and raycast through 60 degrees across the world map.
Divide the world coords by the cellsize of the word. Find out how far into the cell we are. Extract 4 values from the height map -x,y; x+1,y; x,y+1, x+1,y+1. Perform a bilinear interpolation to find out altitude for where the ray is inside the cell. Perform the same for the color value. If the height is less than the previous height (in a variable, starts at bottom of screen) then draw a gouraud interpolated line from lasty to currenty. Repeat for distance iterations, increment angle by angle increment for screen (.1875 for 320, .09375 for 640, 60/horzres) and repeat the process through 60 degrees.

Benefits

• Terrain looks excellent
• Cellsize does not matter - bilinear creates hills not blocks
• Color is bilinear and linear from bottom to top which looks great.
• Raylength is not totally accurate since dist is just incremented
• Very fast

Problems

• Does not allow you to 'see' very far into the distance.
• Bi-linears are very slow if not done in assembly (DJGPP flags errors on assembly - REG class not found or something - even on downloaded examples - don't know why?)
• Almost has to be run in 16 or 24 bit mode due to the amount of colors required for blending

Texture-mapped floating horizon
This is the same process except that instead of drawing column by column, you draw one row at a time from left to right. Find leftangle and rightangle, rotate ray into position to get samples of each. Subtract rightray from leftray and divide by screen horzres to find increment value for ray. Find ray distance
COR[i]*(Player.Height*Player.ViewDist)/(Player.ViewDist-RowInvert)

COR[] -> Sine correction for fisheye sin(90-angle) as angle moves from -30 to +30 degrees. Way better than cosine correction.
Player.Height -> Player's height
Player.ViewDist -> How far up the screen we can see
RowInvert -> BottomOfScreen-CurrentRow - so at bottom rowinvert would be 0, bottom-1 would be 1, etc. Increments.

Benefits

• View depth
• Compact algo - less code than above
• Linear interpolation of angles

Problems

• Can cause divide by zero if you are not careful - since dividing by (Player.ViewDist-RowInvert) If ViewDist is 120 then divide by zero will happen at row bottom-120. Not good.
• No bilinear height or color, but w/o is is still far slower than floating horizon algo.
• Way too many divides - Need another way like using a FloorDistance[] table or something instead of (Player.ViewDist-RowInv).
• Very ugly in the distance - extremely ugly in the distance.
• Much harder to do bilinear and to draw linear interpolated heights
• Very slow

Obviously the first choice has more benefits. But it has to have more view depth. Doubleanti, see if you can use the top algo but find a way to get me the correct distance. Notice my distance is just an integer increment, not taking into account the height of the viewer. Really need 6 degrees of freedom, too. Don't think this algo can do it.

The 3D raycasting algo was very slow (using dry=-tan(VFOV/2)).
Not even an option w/o DirectX or something for realtime rendering.

The 3D package - using matrices tracking the point of the voxel. Draw blocks instead of points VoxelSize*ViewDist/VoxelZ is very fast, but you can see where the world ends - don't know how to repeat landscape using 3D methods. Also 6 degrees of freedom is very easy.

I know this is long, but did not know how to post it any different. This will take some time to look at. If you have any questions, just PM me. If you need some code I have it for about 4 algos. Thought it might be more confusing than just explaining algos so did not attach it. Maybe we could come up with an algo that incorporates both of these together - viewdistance, acceptable visual quality, and speed.

[doubleanti]

what's the profile on these functions? seems to me like i'd recommend the first method... if you scale the worldmap size down to coordinates you can handle you might get the view distance you want... i guess you'd have to use fixed point math to get it more accurate... you might use fixed point math as well in order to get accurate ray length values too [as opposed to incrementing them...]

you could scrap both, and just apply fixed point math in place of floating point and lookup tables for trig functions... and just use your fundamental knowledge of 3 dimensional geometrics to get all 6 degrees of freedom... [and it can be done, quickly too... seeing as how it has been done...]

get me your algorithms and implementation files so i can get one up and running on my system...

-doubleanti

PS oh, and i'll be posting here so everyone can see, in case anyone has any input... okay?

[VirtualAce]

If I scale the coords down using the first method then I've effectively nullified the bilinear interpolation since the distance between x and x+1 and y and y+1 would be 1. Also the voxels are clearly visible and the algorithm falls apart because it is trying to show too much detail. The mountains turn into the columns of pixels that they are. Also, the map repeats so fast that your eye catches the tiling of the world.

Six degrees of freedom is not as easy as you might first think. Simply because when you rotate on y there comes a point when the columns of pixels will not be columns at all due to perspective. Unfortunately my algo is limited to drawing columns of pixels from top to bottom. You might think that the cell diff might make up for it thus causing the colors to come out as if the columns were no longer just columns, but it does not. To rotate on z is nearly impossible, and indeed not many voxel games rotate beyond about 30 and -30 on z. In my engine you can only look left and right - up and down is done by shearing the distance in z and -z directions, but it does not look right.

Also sky mapping does not look correct when you shear z since sky mapping pre-comp is related to center of screen and not current horizon. Re-computing the tables for sky mapping would be to costly during the render loop.

All trig functions are pre-computed and all screen addresses (y*320) are pre computed. All you have to do is add x to ScreenAddr[y] to get the correct address. Colors are also in a table. Everything is pre-computed even the lighting on the map as well as shadows - when I get around to doing them.

I'll get some code to you. I use near pointers in DJGPP for video access via __djgpp_nearptr_enable() - let me know if this does not work on your system and I'll get you a simulated far pointer version (farpokeb(),farnspokeb(), etc).

[doubleanti]

okay... and nearptr's work on my system... [unfort not XP-ers since they cant run my demos...] i have heard of rendering problems when you're viewport converges to the y axis... so that isn't entirely a surprise to me... are you versed in simulating a non-perspective corrected, perhaps isometric 3d environment? then you can just mask over the raycasting... get me the code, and i sure hope i can understand it!

[VirtualAce]

For 3D objects in raycasting I will just render the entire scene from above the objects. There are only y render problems on the texture mapping algo since I'm using screeny to determine the distance for that row. This is not a problem in the other algo.

Trying to get my code commented so you can easily understand what I'm doing. I know how difficult it can be to read someone else's code - especially mine.