Let's start with a simpler problem: ray casting.
We will use rays from our virtual eye (or camera)
to check which objects are visible in the direction of consecutive pixels.
If an object is visible for a ray from the eye to a pixel, draw that pixel in the object's color;
if no object is visible, draw a black background.
This is called ray casting (and not ray tracing)
because it only casts rays from the virtual eye into the virtual scene to check object visibility.
We don't check lights, shading, shadows, reflections, etc.
The algorithm goes as follows:
for each pixel on the screen ps
let v be the vector from our virtual eye through ps
let dmin (the minimum distance to an element) be set to max float
let emin (the element of the scene with the minimum distance) be set to NULL
for each element in our scene e
let p be the point of the intersection of v and e
if p exists then
let d be the distance of p from the eye
if d < dmin then
dmin := d;
emin := e;
end;
end;
end;
if emin <> NULL then
let ps be the color of emin
else
let ps be black
end;
end.
Thus, if emin <> NULL, emin points to the element of our virtual scene
that is closest to the eye (thus visible) in the direction of v.
Hence, we draw the pixel in the color of emin.
However, if emin = NULL, then in the direction of v no objects were found,
thus we draw the default background color (for now, let this be black).
Though it's only ray casting, even this simple algorithm requires the basic framework
that will be later used for more complex calculations.
First, we need to decide what kinds of objects we may place in the virtual scene.
For various reasons, let's start with scenes that include triangles only.
We will add other shapes in the future,
but mathematics behind rendering triangles shows the basic calculations
plus you can build many shapes out of triangles.
Moreover, you can simulate any other shape using triangles
(though some shapes may require lots of very small triangles to be simulated well enough).
Next, we need to be able to calculate the intersection point of a ray with a triangle.
Having that, the rest in the above algorithm is quite easy.
Before we go into detail, let's pause for a moment to get our terminology right.
-
A point in 3D space is easy enough -
three float numbers representing the point's position in standard coordinates (x, y, z).
-
A ray in 3D space is a vector with the starting point p1 = (x1, y1, z1) and the ending point p2 = (x2, y2, z2).
We will assume that the ray's direction is from p1 to p2.
-
A vector is a ray with the starting point p1 = (0, 0, 0).
Thus, there is no real difference between vectors
(which are uniquely defined by their ending point) and points in 3D space -
we will use them interchangeably.
Now, for intersections of rays and triangles.
There are many different algorithms for calculating these intersections,
but we should prefer those that involve as little calculations as possible
(note that in the our ray casting procedure, we calculate a total of #pixels x #triangles intersections).
Intersections of Rays, Segments, Planes and Triangles in 3D gives the required algorithms.
I will not go into much detail here (since everything is described quite nicely in the above article),
let's just note that the two important steps in the process are:
- Find the intersection point of the ray with the plane defined by the vertex points of the triangle.
- If such a point exists, check whether the point lies inside the triangle.
The implementation is pretty straightforward (after reading the linked article).
Before downloading the source, a couple words of explanation may be needed:
-
There is no "point" class;
vectors were defined as a single point (since the starting point is known).
Use vectors anywhere you want to use points.
-
We don't actually calculate the distance, but the square of the distance.
Since we're just looking for the closest object, we don't have to use the (time consuming) sqrt() function.
-
Sometimes, a small value (EPSILON) is used to compare two points / vectors.
The problem comes from the inherently limited precision of floating point calculations.
The solution is to check not against exact values, but to check approximations
(but these still need to be precise enough; hence EPSILON is defined as 1e-10).
-
Right, we'll be using float instead of double, since high precision is not that important for scene rendering.
However, faster speed of float calculations is.
-
The engine class runs the rendering calculations;
Canvas->Pixels[x][y] is pretty slow (takes about half of the rendering time in the example below),
but when we start to complicate the algorithm, this problem will become irrelevant.
-
The scene class is responsible for organizing all objects into a scene.
It also has methods for generating scenes.
TYRTScene::GenerateExample_01Triangles is used to generate the image below.
Ok, after all these introductory comments, let's try our algorithm out on a simple example:
Not quite complex yet, but it's a start nevertheless!
Not quite complex yet, but it's a start nevertheless!
And the sources to the above - in a C++Builder project - can be found
here.
Top
|