Hey guys,
For all of you who've seen YUP's intro Overhead [
http://thygrion.untergrund.net/yup-overhead.zip ], the code is kinda complicated.
Well I got an email from a guy called "NWA", asking how it was done.
So here's his email and my reply, hopefully if anyone was wondering how it worked this should clarify (like anybody really cares
)
Also if you have NASM, put the line "mov si,0fa00h" at the beginning of the program if it runs super slow.
Original message:
Hi!
I'am a beginning coder. I saw your overhead 256b intro using voxels.
could you write some information about that, algorithm. What kind of
informations do I need to write voxel effect usign c++/directx?
Kind regards
NWA
Reply:
Hey,
Glad you liked the intro :)
Unfortunately, it's horrendously slow on modern machines (mostly because of the Pentium IIII's 20-step pipeline..) so the algorithm I used probably won't work too well.
Also, I am unfamiliar with DirectX directly. I've used TinyPTC by Gaffer (no link, I don't remember where it came from, sorry.) before for software 3D engines, but that's about it.
Basically the needs for this method are:
1. A linear screenbuffer. DirectX, I know for sure, supplies this.
2. A palette buffer, which is just a 256-index array (0 to 255) that stores colors. For simplicity just make the first one 0 and the last one 255 and this will give you a blue palette. If you know about colors in DirectX or palettes already, just take care of this yourself.
3. A heightmap. Technically, what I used aren't voxels, but what you see are just pixels of a heightmap. The heightmap I used is 256x256 because it's small and easy to generate. For simplicity again, I'd suggest loading one from a file such as a bitmap or using a simple pattern generator. The only thing to remember here is that the map is 256x256 and each pixel in the heightmap ranges from 0 to 255 for palette indexing (I'll explain later).
And that's all that's necessary.
Now, the algorithm. As I mentioned before, it's very slow, so don't expect too much out of it.
The algorithm is called raycasting, and the idea is this: Set up a virtual camera, that's defined as x, y, and z coordinates. Since it's an overhead rendering (drawing) system, x and z move us around in the map, and y (y *MUST* be greater than 0) is how high our camera is. Until the algorithm is complete and you want to play with it more, set x and z to zero and y to 255. Also, these coordinates could be floats or integers. I would reccomend floats because of accuracy and less type conversions, but it doesn't really matter too much.
For explaining the algorithm, let's call the camera coordinates Cx, Cy, and Cz. We will be using pixel coordinates in the algorithm, so we'll call those Px and Py. The map coordinates will be Mx and My, and the center of the screen is Cx, Cy. Next we'll need ray stuff. These *MUST* be floats. We'll call them Rx, Ry, Rz, Rxv, Ryv, and Rzv. Finally, a variable will be used to scale our rays, S. In overhead, S = 480.
Finally, the algorithm explanation:
1. Setup Cx, Cy, and Cz. For now, Cx = Cz = 0 and Cy = 255. These may be changed as long as y stays a positive number.
2. Loop through the 2D screen.
3. For each pixel, Px = x coordinate of pixel in screen space and Py = y coordinate of pixel in screen space. Given these, we now calculate Rx, Ry, and Rz. Rx Ry, and Rz are ray coordinates. Raycasting shoots rays from the camera in a direction determined by the screen coordinates. A ray is followed until it hits the heightmap, where the pixel is drawn. So, since the ray starts where the camera is, Rx = Cx, Ry = Cy, and Rz = Cz . Simple so far, eh?
4. Now it gets trickier. At this point we must calculate Rxv, Ryv, and Rzv. Rxv and Rzv will be converted to map coordinates. Ryv is constant for each ray, and will simply be -1. Don't change this, ever! :P There's no need. Now, since Rxv and Rzv will be different for each pixel, we will calculate them from Px and Py. The calculations are as follows: Rxv = (Px - Cx) / S. Rzv = (Py - Cy) / S. What this does is calculate each ray so that the rays go outward from the center of the screen.
5. This is where we trace each ray. First we'll set up a forever loop. This is done by just typing "do { ... } while(true);" where the "..." will be our tracing code. You're probably thinking, "Why on God's green earth would we do a forever loop?!?" It's because of the lovely command "break". When "break;" is done, the loop will escape and the machine will move on, which is exactly what we need. Now, what goes in this loop? Well, first, we'll move the ray by Rxv, Ryv and Rzv. This is simple: Rx += Rxv; Ry += Ryv; Rz += Rzv; . This moves the ray in it's correct direction and one unit downwards. Now, we sample the heightmap. This means that we will compare Ry to a value in our map at (Mx,My). So, we need to calculate Mx and My: Mx = (int) Rx & 255; My = (int) Rz & 255; (No, that Rz isn't a typo ;) ). The "& 255" just limits the values to go from 0 to 255, so there's no memory problems when looking up our heightmap.
6. Now that we have Mx and My, we have everything we need to sample the heightmap. This is done by a simple If statement: If((int) Ry <= heightmap(Mx,My)) break; . What this does is, if our ray "crashes" into our heightmap, we end the loop and move on. This is sure to break the forever loop, since Ry will always be zero or greater and our heightmap never goes below zero. So eventually each ray will collide with the heightmap.
7. So our loop is complete. What now? Drawing. This is the easiest part. What we do is draw a pixel at Px, Py with a value from our palette. What value? I just used the heightmap's value at Mx, My. So, this is all: setpixel(Px,Py,palette(heightmap(Mx,My))); , and I assume setpixel will be replaced with however you draw pixels.
That's everything. This is all done each frame. Of course there are other things like generating the heightmap, but I leave this up to you, because otherwise where would all your fun be? ;)
If you have any other questions feel free to ask.
Hope this helps and happy coding,
Jake
And also, * HEAVEN SEVEN USES NO ASSEMBLY WHAT SO EVER!!!!!!!!!!!!!! * <- Just thought I'd put that out there in an ASM thread
