Dark Bit Factory & Gravity
PROGRAMMING => Other languages => ASM => Topic started by: ferris on April 13, 2007
-
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 :P)
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 :)
-
What a great idea to post this :)
Have some Karma mate.
-
Definately. Karma boost ...
It's also interesting to hear that someone emailed you because of one of your
productions. This is very cool IMHO. Do you receive more emails in general
concerning questions/feedback of your intros ?
-
Usually when I do it's fanmail (which is barely ever, mind you :P) and not questions asking about methods, else they'd probably be posted too :)
Glad you like the explanation!
-
You make it sound so simple
Just one question its a raycaster but how then can it be on a per pixel basis is a raycaster simple a raytracer that doesnt reflect or refract cos my understanding of raycasting was that entire columns of pixels were produced by a single ray to create an interrior environment. So the use of a hieghtmap is a bit confusing to me. This might be a misunderstanding of the word on my part.
-
im with rainstorm the way ive done raycasting is colums projected at diffrent heights based on how far my ray traveld from my camera.
what your talking about is tracing isnt it?
-
The term "casting" referres to how a ray is followed - in raytracing a ray is checked for intersections once per object and in raycasting the ray is checked with a map in fixed intervals.
-
I was checking out the source code last night some of it I was surprised by how much work was being done on so few calculations but I'm afraid most of it was over my head nevertheless you got some skills there Thygrion thanks for sharing the code
-
Guys,
dont get confused by how games and demo coders misuse these terms they are straightforward. Lets say we were raycasting *long* before people used the term for DOOM (wrongly I might add).
Raycasting: A ray is sent from the eye and returns the closest intersection. Colour, lighting is calculated and possibly shadows. Calculation ends. Key point : One intersection with elements in the scene only.
Raytracing: As above but possible further rays are calculated (eg reflection and refection) and traced. This "tree" of rays is used to calculate the resulting colour for the eye.
Ray stepping: Can be used in either raycasting or raytracing. In this technique small increments are used along the direction of the ray to determine intersection with objects that cannot be directly evaluated (fractals, implicit surfaces, height fields etc )
Chris
-
k++; I learned something :)
-
Ugh just reread the post, I sounded like a preaching wanker. Sorry for that.
Chris
-
Dont worry Taj it cleared things up for me. I thought that only wolfenstien type rendering techniques were raycasters now I know better :D
-
Thanks for clear explaination Ferris. I fiddled with overhead many times, but nothing could be as clear as your own words for your own code.