Free Direction Rendering

This article gives information on how to render various objects in high quality and in real time.

@DrWatson

Published in 

atari

 · 11 months ago

• Document Title : Free Direction Rendering
• Author : Ohad Eder Pressman aka Kombat/Immortals
• Date : 20/02/1998
• Tabsize : 3

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 neet objectives, by tracing a ray from the users 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 be RayTracing

All of the 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 give 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, I will explain how to calculate it later.

Since we will be dealing 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 yourself 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 that pencil of yours 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'r 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, thats 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, we just need to intersect our ray with the circle.

[Math coming up]

* according to some old guy called Pitagoras, (a^2 + b^2 = c^2) , O + D \cdot t is our intersection vector, we will break it up to the 'x' and 'y' components.

where r is the radius of our cone.

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 \cdot t , you scale the D vector by t and adding it to O. After we have our Intersection point, we need to ask "Hmm, ok, we hit that circlish thinggy 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 comming 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 interest to our cone, lets see how far away the Intersection point it, the deeper it is the darker things are (or vice versa).

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'r 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 piece of cake and looks better too.

The RayTracing in this one is by far simpler than the above Cone example. 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 for 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, lets 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]

Lets 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 it job and that the calculation is the same for whatever type of Origin we have. The only place we need to take a carefull look is at 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 luckily some of us do, the meaning of 't' is, how many steps of size Direction.y should we 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 be using planar mapping which is the simplest situation possible, u treat the values of the intersection points as U,V coordinates since the texture just 'sits' ON the plane.

After we've found our U,V coords, lets 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)' + (Intersection.z-Origin.z)';

The calculation is once again according to pitagoras, the distance between two points, and we don't use a 'sqrt' since light affects points according to the distance', therefore 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 mechanism, just start writing it on a piece of paper. You have your Ray O + D \cdot 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 continues on the screen, and is usually calculated for each pixel, you can calculate this effects 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 somewhat 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 you 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 will draw this box. If your lazy, you can use your regular texture-mapper (or gouraud texture-mapper if you wan't 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 modells people always implement in raytracers, well, why not try :) A good example for this is the new Intro by Pulse (Sink) from TG97

The Source code

The source code provided (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

equivalent 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 examplatory 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 learn't from this document, please don't be shy and greet me in your demo/intro/whatever. If you have 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 maximum 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 source code 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 made 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

and

therefore

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 :

1. send a postcard with your countrie'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 all you guys I must have forgotten but shit happens, tell me and I'll fix it by the next doc. ;-)

special 10x :
civax - keeping jewish scene alive as long he can, and cFx
statix - beeing a better designer than a coder ;)
submissive - convincing me to write that mpeg2 player :)
silvatar - joining the corporation
rage - beeing damn lazy
Israeli armi - taking darkspirit :) (just kiddin')
school - for ending soon
soundvirus - making them mp3's for me

Contact :

Ohad Eder Pressman aka Kombat/Immortals/Taat/62m

email : kombat@netvision.net.il
tel : 972-9-7742244
snailmail already listed above.

-------------
End Of Document, Free Diretion Rendering, Ohad Eder Pressman 1998

FD.CPP

/* 
	Document Title : Free Direction Rendering 
	Author         : Ohad Eder Pressman aka Kombat/Immortals 
	Date           : 20/02/1998 

	Sample Source-Code 
*/ 

//#define GENERATE_UGLY_TEXTURE 

// Graphical and Mathematical routines/variables 
#include "stuff.h" 

// Constnats 
const float CONE_RADIUS 	= 256; 
const float PLANE_OFFSET 	= 650; 
const float SPHERE_RADIUS = 256; 

 
// Free-Direction Tunnel 
void fd_tunnel(int x, int y, char *u, char *v, char *z) 
{ 
	Vector Origin = {-128,128,0}, 
			 // Pixel Direction Calculation 
			 Direction = {(x-160)/FOV,(y-100)/FOV,1}, 
			 Intersect; 
	float a, b, c, delta, 
			t1, t2, t; 

	// Normalize our Direction Vector 
	vec_norm(&Direction); 

	// (Dxý+Dyý)*tý + 2*(Ox*Dx+Oy*Dy)*t + (Oxý+Oyý-rý) = 0 
	a = sqr(Direction.x) + sqr(Direction.y); 
	b = 2*(Origin.x*Direction.x + Origin.y*Direction.y); 
	c = sqr(Origin.x) + sqr(Origin.y) - sqr(CONE_RADIUS); 

	// delta = û ( bý - 4ac ) 
	delta = sqrt(b*b - 4*a*c); 

        //           -b + delta             -b + delta 
	//	x1 = ÄÄÄÄÄÄÄÄÄÄ    ;   x2 = ÄÄÄÄÄÄÄÄÄÄ 
        //               2a                     2a 
	t1 = (-b + delta) / (2*a+EPSILON); 
	t2 = (-b - delta) / (2*a+EPSILON); 

	// Find positive solution 
	t = t1 > 0 ? t1 : t2; 

	// Calculate Intersect Point (O + D*t) 
	Intersect.x = Origin.x + Direction.x*t; 
	Intersect.y = Origin.y + Direction.y*t; 
	Intersect.z = Origin.z + Direction.z*t; 

	// Calculate Mapping Coordinates (Radial Coordinates) 
	*u = (char)(fabs(Intersect.z)*0.6); 
	*v = (char)(fabs(atan2(Intersect.y, Intersect.x)*256/PI)); 

	// Calculate Depth 
	t = 20000.0/t; 
	*z = (char)(t > 63 ? 63 : t); 
} 

// Free-Direction Planes 
void fd_planes(int x, int y, char *u, char *v, char *z) 
{ 
	Vector Origin = {0,0,0}, 
			 // Pixel Direction Calculation 
			 Direction = {(x-160)/FOV,(y-100)/FOV,1}, 
			 Intersect; 
	float t; 

	// Normalize our Direction Vector 
	vec_norm(&Direction); 

	// Find t 
	t = (sgn(Direction.y)*PLANE_OFFSET-Origin.y) / Direction.y; 

	// Calculate Intersect Point (O + D*t) 
	Intersect.x = Origin.x + Direction.x*t; 
	Intersect.y = Origin.y + Direction.y*t; 
	Intersect.z = Origin.z + Direction.z*t; 

	// Calculate Mapping Coordinates ( Coordiantes) 
	*u = (char)(fabs(Intersect.x)*0.3); 
	*v = (char)(fabs(Intersect.z)*0.3); 

	// Calculate Depth 
	t = sqr(Intersect.x-Origin.x) + sqr(Intersect.z-Origin.z); 
	if (t <= EPSILON) *z = 0; 
	else 
	{ 
		t = 50000.0 / sqrt(t); 
		*z = (char)(t > 63 ? 63 : t); 
	} 
} 

// Free-Direction Sphere 
void fd_sphere(int x, int y, char *u, char *v, char *z) 
{ 
	Vector Origin = {0,-100,-100}, 
			 // Pixel Direction Calculation 
			 Direction = {(x-160)/FOV,(y-100)/FOV-.4,.7}, 
			 Intersect; 
	float a, b, c, delta, 
			t1, t2, t; 

	// Normalize our Direction Vector 
	vec_norm(&Direction); 

	// (Dxý+Dyý+Dzý)*tý + 2*(Ox*Dx+Oy*Dy+Oz*Dz)*t + (Oxý+Oyý+Ozý-rý) = 0 
	a = sqr(Direction.x) + sqr(Direction.y) + sqr(Direction.z); 
	b = 2*(Origin.x*Direction.x + Origin.y*Direction.y + Origin.z*Direction.z); 
	c = sqr(Origin.x) + sqr(Origin.y) + sqr(Origin.z) - sqr(SPHERE_RADIUS); 

	// delta = û ( bý - 4ac ) 
	delta = sqrt(b*b - 4*a*c); 

        //           -b + delta             -b + delta 
	//	x1 = ÄÄÄÄÄÄÄÄÄÄ    ;   x2 = ÄÄÄÄÄÄÄÄÄÄ 
        //               2a                     2a 
	t1 = (-b + delta) / (2*a); 
	t2 = (-b - delta) / (2*a); 

	// Find positive solution 
	t = t1 > 0 ? t1 : t2; 

	// Calculate Intersect Point (O + D*t) 
	Intersect.x = Origin.x + Direction.x*t; 
	Intersect.y = Origin.y + Direction.y*t; 
	Intersect.z = Origin.z + Direction.z*t; 

	// Calculate Mapping Coordinates (Radial Coordiantes) 
	*u = asin((Intersect.y) / sqrt(sqr(Intersect.x) + 
		  sqr(Intersect.y) +	sqr(Intersect.z)))*128+128; 
	*v = atan2(Intersect.z, Intersect.x)*256/PI; 

	// Calculate Depth 
	t = (fabs(Intersect.z) / SPHERE_RADIUS) * 90; 
	*z = (char)(t > 63 ? 63 : t); 
} 

void main() 
{ 
	int i, j; 
	char u, v, z; 

	mode(0x13); 

	// Generate a simple texture or Load one from a file 
	init_txtr(); 

	// Generate a Free-Direction Tunnel 
	for (i=0; i<320; i++) 
		for (j=0; j<200; j++) 
		{ 
			// Perform RayTracing, calculate mapp. coords. and shadow 
			fd_tunnel(i,j,&u,&v,&z); 
			// Put pixel from Texture, darken according to shadow 
			vga[i + j*320] = texture[u+v*256] * (int)z >> 6; 
		} 

	delay(3000); 

	// Generate Free-Direction Planes 
	for (i=0; i<320; i++) 
		for (j=0; j<200; j++) 
		{ 
			// Perform RayTracing, calculate mapp. coords. and shadow 
			fd_planes(i,j,&u,&v,&z); 
			// Put pixel from Texture, darken according to shadow 
			vga[i + j*320] = texture[u+v*256] * (int)z >> 6; 
		} 

	delay(3000); 

	// Generate a Free-Direction Sphere 
	for (i=0; i<320; i++) 
		for (j=0; j<200; j++) 
		{ 
			// Perform RayTracing, calculate mapp. coords. and shadow 
			fd_sphere(i,j,&u,&v,&z); 
			// Put pixel from Texture, darken according to shadow 
			vga[i + j*320] = texture[u+v*256] * (int)z >> 6; 
		} 

	getchar(); 

	mode(3); 

	cout << "\nFree Direction Rendering\n"; 
	cout << "Sample Source Code\n"; 
	cout << "Ohad Eder Pressman aka Kombat/Immortals 1998\n\n"; 
}

STUFF.H

/* 
	Document Title : Free Direction Rendering 
	Author         : Ohad Eder Pressman aka Kombat/Immortals 
	Date           : 20/02/1998 

	Graphical and Mathematical routines/variables 
*/ 

 
// Includes 

#include <stdio.h> 
#include <iostream.h> 
#include <math.h> 
#include <dos.h> 

// Graphics 

void mode(int); 
#pragma aux mode=\ 
"int 0x10"\ 
parm [eax] modify exact [eax]; 

char *vga = (char *)0xA0000, texture[256*256]; 

void outp(unsigned short, char); 
#pragma aux outp=\ 
"out dx, al"\ 
parm [dx] [al] modify exact [dx al]; 

void init_txtr() 
{ 
	int i, j; 

#ifdef GENERATE_UGLY_TEXTURE 
	// Generate A Xor Texture 
	for (i=0; i<256; i++) 
		for (j=0; j<256; j++) 
			texture[i + j*256] = i^j; 
#else 
	FILE *f; 
	f = fopen("texture.raw","rb"); 
	fread(texture,256*256,1,f); 
	fclose(f); 
#endif 

	// Setup A Fading Palette 
	outp(0x3c8, 0); 
	for (i=0;i<256;i++) 
	{ 
		outp(0x3c9, i>>2); 
		outp(0x3c9, i>>2); 
		outp(0x3c9, i>>2); 
	} 
} 

 
// Math 

#define PI 3.141 

#define EPSILON 1.0E-6 // a tiny number 

#define FOV 120.0 

typedef struct Vector 
{ 
	float x, y, z; 
} Vector; 

#define sqr(a)		((a)*(a)) 
#define sgn(a)    (((a) > 0) ? 1 : -1) 

void vec_norm(Vector *v) 
{ 
	float l = 1.0 / sqrt(v->x*v->x + v->y*v->y + v->z*v->z); 

	v->x *= l; 
	v->y *= l; 
	v->z *= l; 
}