Free-directional tunnels
Mikael Kalms
1997'ish




Describe the tunnel as "an infinitely long cylinder, stretched out along the Z
axis, with centre along (0,0,t) line (ie the Z axis), and radius R".
The tunnel can be described with the following equation:

x^2 + y^2 = r^2

(ie "all XYZ combinations that are solutions to the above equations are points
on the cylinder's surface")

Next thing to do is to try to generate a view of the tunnel. This is done by
calculating for every pixel: "What little piece of the tunnel should I see
'through' this pixel?" (The screen is thus considered a window into the 3d
world.)
When looking 'through' a pixel, one actually looks along a ray. One sees the
piece of tunnel where the ray intersects it.
Therefore, generating a 2d screen view of the tunnel is done by intersecting
lots of rays (one per pixel) with the tunnel.

Describing the ray mathematically is easiest done if it's considered a line.
The line would then be written on this form:

    { x = x0 + t * dx
l = { y = y0 + t * dy
    { z = z0 + t * dz

(x0,y0,z0) is a point on the line, and dx,dy,dz are its direction coefficients
in XYZ direction.
By varying t one gets different XYZ values, all of which are on the line.

Calculation of the intersection between a line and our cylinder is done
by inserting the line's equation into that of the tunnel. The resulting
equation is:

(x0 + t * dx)^2 + (y0 + t * dy)^2 = r^2

(the above equation has solutions only for those t that are both on the line,
and on the cylinder.)

Solving for t yields...

x0^2 + t^2 * dx^2 + 2 * x0 * t * dx + y0^2 + t^2 * dy^2 + 2 * y0 * t * dy = r^2

(x0^2 + y0^2 - r^2)
+ t * (2 * (x0 * dx + y0 * dy))
+ t^2 * (dx^2 + dy^2)
= 0

(x0^2 + y0^2 - r^2) / (dx^2 + dy^2)
+ t * (2 * (x0 * dx + y0 * dy)) / (dx^2 + dy^2)
+ t^2
= 0

Solving the 2nd order equation using:
t^2 + pt + q = 0;       t = -p/2 +/- sqrt((p/2)^2 - q)    <some cool formula>
                                     | discriminant  |
....gives...

a = (dx^2 + dy^2)
halfp = (x0 * dx + y0 * dy) / a
q = (x0^2 + y0^2 - r^2) / a
discriminant = sqrt(halfp^2 - q)

t1 = halfp + discriminant
(t2 = halfp - discriminant)

So, you get 2 intersection points. Choose the one that fits best (the one that's
>0 (ie t1, cause as long as you're inside the tunnel t2 will be <0)), and insert
it into the line equations to get XYZ of the intersection point.
After that use atan2(y,x) to get angle, and Z for distance.



Okay, all that's missing now is how to formulate the rays for each pixel.

Do that by first writing vectors to the upper-left, upper-right and lower-left
corner of screen <HFOV = 60 degrees, VFOV = 45 degrees>:
(-tan(HFOV/2),tan(VFOV/2),1);
(tan(HFOV/2),tan(VFOV/2),1);
(-tan(HFOV/2),-tan(VFOV/2),1);

(~= (-0.5,0.33,1), (0.5,0.33,1), (-0.5,-0.33,1))

Interpolate their XYZs to get the intermediate vectors.
Then use the vectors' XYZs for dx,dy,dz in the line equ. (the x0,y0,z0 is given
as the position of the eye and for that (0,0,0) is good in a test rout. :))

In order to rotate the eye one just rotates the 3 reference vectors using
standard 3d rotation formulas.



We've got our traced tunnel, although it isn't particularly fast. How do
we up the speed a bit?
  Instead of tracing every pixel, we trace every Nth pixel in x- and
y-direction, and interpolate the texture coordinates linearly inside
each NxN-pixel square that is formed by the "grid" of sample points.
  The grid size is typically 8x8 or 4x4 pixels (Showbase Shape
(Icing Beta '97) used 8x8).
  Grid-interpolation speeds up a lot -- with 8x8 gridsize, the actual
tracing should take about 1/10th of the total time, if not less.