Free Direction Rendering
Free Direction effects are Ray-Tracing based effects. Sounds frightning, but it's really easy to code and fun to watch. Ray-Tracing is usually referred to as a slow method of rendering, but we will use a trick to minimize calculations and speed-up rendering time.
What is RayTracing:
Raytracing is a method of rendering a world made out of objects and other neat objectives, by tracing a ray from the user's view point, through the 3D world, until it hits any of these objectives. At RealTime aspects it is also referred to as SLOOOOOOOOOW. :)
How will we RayTrace:
All Free-Direction effects are based on the assumption that you are standing in a 3D world and looking at some direction. The speed of these effects is extracted from the given situations. We will be dealing with very simple aspects of RayTracing, situations where your rays always intersect with our given object.
We will assume that all of our rays are coming out of a certain point in our world (your camera source for instance). We'll call this point our 'Origin' vector. Since we are looking at a certain Direction, we also need a 'Direction' vector. This vector isn't the same for all points on the screen, so I will explain how to calculate it later.
Since we will deal with easy situations, in which we can assume that our ray always intersects with a given object, all we need to do is find the intersection point. Before knowing this point, we will define it as 'Origin + Direction*t', where 'Direction' is propagated through space, or in other words, it is scaled. Imagine a point in space (Origin), now take a pencil or anything else, place it at that point, and start moving it in a certain direction. This is what we will do, we will 'move' according to our direction until we hit something (once your pencil hits the wall for instance :).
Origin will be referred to as 'O', Direction as 'D' and the variable 't' will represent how much we have scaled this Direction vector through space.
Free Direction Tunnel:
This one is pretty simple, you're in a tunnel. :)
The tunnel is actually an endless cone, a set of 2D circles that are built on the XY axis and extend toward and back the Z axis with the same radius, a cone. :)
The raytracing here isn't to hard. We have our Origin vector, our Direction vector, and we need to find 't'.
Since we are inside the cone, once we fire a ray, it will collide with the cone at some point, which is the point we need to find. The point will be described as Origin + Direction*t. The collision occurs when the distance between the intersection point and the Z axis is the radius of our cone. If we look at the situation from the XY axis, we see a circle, so we just need to intersect our ray with the circle.
[Math coming up]
* According to some old guy called Pythagoras (a^2+b^2=c^2), O+D*t is our intersection vector. We will break it up to the 'x' and 'y' components.
(Ox+Dx*t)^2 + (Oy+Dy*t) = r^2 (r is the radius of our cone)
Ox^2 + 2*Ox*Dx*t + Dx^2*t^2 + Oy^2 + 2*Oy*Dy*t + Dy^2*t^2 - r^2 = 0
(Dx^2+Dy^2)*t^2 + 2*(Ox*Dx+Oy*Dy)*t + (Ox^2+Oy^2-r^2) = 0
Tada, a Quadratic equation, of the 'ax^2 + bx + c = 0' form. We will get 2 solutions. We need the positive one, since the negative solution will give us a point that is behind us. Once we find our 't' we can calculate the intersection point 'O + D*t', you scale the D vector by t and add it to O. When we have our Intersection point, we have to ask "Hmm, ok, we hit that circlish thingy right over there, but, now what?" We need to calculate a mapping coordinate (a U,V Coordinate). Assuming the texture is radially mapped on our cone, the texture coordinates would be:
[Math coming up]
U = fabs(Intersection.z)
V = fabs(atan2(Intersection.y, Intersection.x)*256/PI)
Please note, texture coordinates range from 0 to 255 (refer to example).
In order to add up a little more intereset to our cone, let's see how far away the Intersection point is. The deeper it is the darker things are (or vice versa).
Depth = 100.0 / t
This will give a nice spotlight effect (that is if we consider this Depth in our final color calculations).
Free Direction Planes:
This one is even simpler, you're between two huge packs of chocolate. :) This effect is made out of two parallel planes, which are placed on the XZ axis and can move up n' down on the Y axis. You can render one plane, but adding the other one is a piece of cake and looks better too.
The RayTracing in this one is by far simpler than the Cone example above. Our ray can hit either the top plane or the bottom plane. This depends only on the Y component of the direction vector. If we are looking up to the sky, we will most likely see the sky (upper plane), on the other hand looking down at the floor would give us... yes, the toaster, I mean the lower plane. Our ray will always hit one of the planes except in one situation in which the Y component of the Direction vector is nullified, which means you are looking straight forward (I personally never gave a damn about this situation, but I suggest placing an 'if' statement for it 'just in case').
Now, let's see, our ray will collide with one of the planes, and we can calculate 'when' just by looking at the distance from the Origin point to the Planes.
[Math coming up]
Let's take a look at both possible situations:
if (Direction.y > 0)
{
if (Origin.y > 0) t = (r - Origin.y) / Direction.y;
else t = (r - Origin.y) / Direction.y;
}
else
{
if (Origin.y > 0) t = (-r - Origin.y) / Direction.y;
else t = (-r - Origin.y) / Direction.y;
}
Logically we needed to write the calculation for Positive Origin and Negative Origin. After that we can see that math does its job and that the calculation is the same for whatever type of Origin we have. The only place we need to take a careful look at is the 'r' variable.
t = (sgn(Direction.y)*PLANE_OFFSET-Origin.y) / Direction.y
PLANE_OFFSET is changed according to the sign (+-) of Direction.y. If you really want to understand why, and fortunately some of us do: The meaning of 't' is, how many steps of size Direction.y we should do until we bump our head/legs into one of the planes. Once we know how many steps, we know that at the same time we need to do 't' steps of Direction.x on the X axis and 't' steps of Direction.z on the Z axis.
Once we have our intersection point, finding what point of the texture sits there is very easy, since logically we will use planar mapping which is the simplest situation possible. You treat the values of the intersection points as U,V coordinates since the texture just 'sits' ON the plane.
After we found our U,V coords, let's see how far away the Intersection point is from us. The deeper it is the darker things are (or vice versa).
Depth = (Intersection.x-Origin.x)^2 + (Intersection.z-Origin.z)^2;
The calculation is once again according to Pythagoras, the distance between two points, and we don't use a 'sqrt' since light affects points according to the distance^2, therefore there is no need to take a 'sqrt'. This will once again give us a nice spotlight effect (that is if we consider this Depth in our final color calculations).
Free Direction Sphere:
This one is going to be different. Why, you ask? 'cause I'm not going to talk about it. :)
First of all I don't like FD-Spheres, imho they don't look good. But how can I release this document without talking about it (easily). If you want to understand the Sphere RayTracing mechanisem, just start writing it on a piece of paper. You have your Ray (O+D*t) and it intersects with this sphere when the distance between the Ray and the Center of the Sphere (0,0,0) equals the radius, pretty much like the FD-Tunnel. The only thing that is different is the mapping coordinates calculation. Here we calculate spherical mapping coords. Take a look at the source and find those nasty long lines that calculate the coords.
How To Optimize This Stuff:
Like most normal people, you want these effects to run in more than 3fps. The trick is, treat all of these effects as 'Grid Effects'. I can hear the crowd screaming "WTF are grid effects?". Simple, once you have an effect that looks continued on the screen, and is usually calculated for each pixel, you can calculate this effect for only a part of the screen, a fixed size grid, and then interpolate between these grid boxes. Still sounds funny? Take a look at the following chart (cheer):
Your screen
(0,0) ---------------------
| | | | | |
(0,8) ---------------------
| | | | | |
(0,16) ---------------------
| | | | | |
. . . . . .
. . . . . .
Instead of calculating your effect (in our case RayTrace for each pixel), calculate the effect for the points of intersection in the grid. Your loop would look about like this:
for (x=0;x<320;x+=8)
for (y=0;y<200;y+=8)
Calculate_Effect(x, y, ...);
This gives you a grid of size 40x25 which means you calculate your effect only 1,000 times instead of 64,000. Make an array of this [45][20] size, for each point store the U,V coordinates you calculated. Once you have finished your calculations, run over all of the 8,8 boxes this grid creates. You have a fixed size box. Each of its 4 corners has a U,V coordinate. What will we do? YES, we will write a simple mapper that draws this box. If you're lazy, you can use your regular texture-mapper (or gouraud texture-mapper if you want to use the shade calculations), but, since this box is fixed in size (constant), the mapper won't take too much time code nor run, it will be faster than a coder drinking a can of coke.
Just one more tip about fdraytracing: Don't forget that you are raytracing. Remember all those shadows and cool illumination models people always implement in raytracers. Well, why not try. :) A good example for this is the intro by Pulse (Sink) from TG97.
The Source code:
The provided source code (FD.CPP) demonstrates an implementation of the 3 effects described in this document. It should be compiled with Watcom C 10.6 or above. The included file (STUFF.h) contains a very simple graphic interface and some math routines, nothing special.
I started using the '?:' syntax. If you don't know what this means...
x = x1 > x2 ? x1 : x2
is equal to
if (x1 > x2) x = x1; else x = x2;
IMPORTANT: I use a Left (or Right) handed axis based system. This means that X+ goes to your right, Y+ goes upwards and Z+ goes into the screen.
The example code provided is not supposed to be optimized, it's not supposed to be fast, it's not supposed to be anything, but an example of several Free-Direction effects. The source code doesn't include several 'if' statements that would help preventing Domain Errors in sqrt and asin, so if you implement this code, don't forget to check the values you pass to these functions.
If you use the code supplied with this document, or write your own code according to what you have learnt from this document, please don't be shy and greet me in your demo/intro/whatever. If you have amy questions don't hesitate to contact me and ask, but think twice before you do so, you may be able to solve that problem yourself (which is much more fun for both you and me :).
Just a few words about the direction. The direction vector in all of the examples is based on the idea of the human eye (cheers). The eye is actually one point (Origin) and it shoots rays to the direction the eye looks at. But, it doesn't shoot all the rays at the same direction. In the source code I used a simple implementation of FOV (Field-Of-View).
Direction = {(x-160)/FOV,(y-100)/FOV,1}
FOV is the maxium angle you can see, which means you can see FOV/2 degrees to your left and FOV/2 degrees to your right, etc. (in the sourcecode the value of FOV is actually FOV/2). x-160 and y-100 and 1 for the z (since we are looking into the screen) give us the global direction, the 1.0/FOV creates the eye effect.
In the source I use different Origin points and different to calculate the lighting. Please don't get confused, this is not standard. I just did it so that the outcome will look nice. Feel free to play with it.
Math Appendix:
1) The solutions for a Quadratic equation of the following form:
ax^2 + bx + c = 0
delta = b^2 - 4ac
-b + sqrt(delta) -b - sqrt(delta)
x1 = ---------------- ; x2 = ----------------
2a 2a
Just a Few More Words:
This Document + SourceCode are Smileware, what does this means?
If this document helped you, and you would like the writer to write more of this kind, you don't need to pay anybody, or send anybody 10$. You are on the other hand most welcome to do one of the two following things:
1. Send a postcard with your country's view to:
Ohad Eder Pressman aka Kombat/Immortals
32, Hativat Givaty St.
Raanana 43338
ISRAEL
2. Order a pizza to the same address, just let the writer know before you do so. (This is widely known as normal amongst the worldwide GNU authors. :)
I'd like to take this opportiunity to thank all of those who sent me postcards from Finland and The Netherlands (you have cool countries), and to all of those who emailed me to thank me about my last Camera document or ask questions about it.
Thanks to all my friends...
Rage, Adept, Borzom, CyberEagle, Thor, Dark-Spirit, Sound-Virus, DJ-Crazy, Silvatar, Falcor_, Civax, Turk182, T3a, Scroll-Lock, Yoav from YOE, Face, Riff-Raff, Shudder, Atomic, Diffuse, Nick-S, Gambit, Drool, SmallBrain, Kaos, Turk182, Krembo, Fractal, Cycat, Nimrod. All new Israeli Demo groups: We can bee good, Boost Up. :) Mali, Submissive, Scholar, Kalms, MAD, Pascal, Doj, Vastator, Statix, Mrz, Lnx, Ravian Sqrt, Wog, Tonic, Skal, Karl, Deathscar, Tobiasf, Xyz, Ex, Blackaxe, Xls, Beta, FVision, Codger, Hattara (3dpower:), Steffo, Dice, Vic, cremax, mri, Sol, Nitro, Unreal
I'm really sorry for all you guys I must have forgotten but shit happens, tell me and I'll fix it in the next doc. ;-)
Special 10x:
civax - keeping Jewish scene alive as long as he can, and cFx statix - being a better designer than a coder ;) submissive - convincing me to write that mpeg2 player :) silvatar - Joining the corporation rage - being damn lazy Israeli army - taking darkspirit :) (just kiddin') school - for ending soon soundvirus - making mp3's for me
Contact:
Ohad Eder Pressman aka Kombat/Immortals/Taat/62m
email: eder@bigfoot.com
tel: 972-9-7742244
Snailmail already listed above.
End Of Document, Free Direction Rendering, Ohad Eder Pressman 1998