FPGA Ray Tracer |

The idea for our project came from Prof. Land's lectures on ray tracing. Ray tracing is very well suited for FPGA's where many calculations can proceed in parallel. Spheres allow quite interesting scenes to be drawn, especially when reflections are added. We found that once we had implemented sphere rendering, adding planes was easier because fewer calculations were needed and we had existing experience and states in place to do the required calculations, reflections, and shadowing. Ray Tracing
Figure 1
The tracer would then repeat the process for the next pixel in the scene (or another ray for that pixel if anti-aliasing is used). Since each ray must check for intersections with every object in the scene, the processing time increases significantly with a large number of objects. However, since pixel is independent of each other, they can be processed in parallel if the hardware is available.
Figure 2 and Figure 3
Our coordinate system and sample scene setup are shown in Figure 4 Our ray decision tree is shown in Figure 5 figure 5.
At reset, the tracer is initialized. It then proceeds to load the sphere
list from the CPU. The transfer is controlled by the CPU once the hardware
signals that a frame has completed. A ray then checks for the closest intersection,
if any, with the spheres in the scene. If it hits one, Lambertian lighting
is applied to give it a color based on the amount of shadow. If the intersection
is completely in shadow, no shadow ray would be needed as it will be blocked
by the sphere the ray intersected with. If the ray did not hit a sphere,
the planes in the scene are checked for the closest intersection. We chose
to give spheres priority and not check planes in the event of a sphere intersection
because of performance considerations and that we added planes as a last
minute extra once we satisfied our initial project specifications. This
imposed the restriction that spheres must be on top of planes and not behind
them, which is a reasonable restriction for the scenes we wanted to render.
A shadow ray was launched towards the light source. Again, the shadow ray checked the sphere list for an intersection, but only spheres closer than the light source were counted as actual intersections. Because spheres must be in front of planes, the plane list was not checked to see if a plane cast a shadow on a sphere. At this point, the pixel has an initial color, it is either black because
it missed all objects, the color of the intersected object, or the color
of the intersected object with a shadow. For shadows, we halved the color
of the intersection object to allow for some ambient lighting affects.
For the Lambertian/cosine shading, the dot product of the normalized normal
with the normalized vector from the intersection point to the light source
was multiplied by the object's color. Because both vectors were normalized,
the dot product produces a scaling factor between 1 and 0. We offset the
resulting color by the completely shadowed color and made sure the resulting
color did not overflow when the offset was added to the color with a saturating
addition. Sphere Background Math Figure 6 R_{origin }= R_{o }= [ X_{o}
Y_{o} Z_{o }]R _{direction }= R_{d }= [ X_{d} Y_{d} Z_{d
}]R(t) = R _{o} + R_{d} * tR _{intersection }= R_{i} = [ X_{i} Y_{i}
Z_{i} ] = [ X_{o} + X_{d} * t
Y_{o} + Y_{d} * t Z_{o} + Z_{d} * t ]R _{normal} = R_{n} = [ X_{n} Y_{n} Z_{n
}] = [ (X_{i} – X_{c})/S_{r} (Y_{i} – Y_{c})/S_{r}
(Z_{i} – Z_{c})/S_{r} ]t = intersection distance D ^{2} = L^{2}_{oc} – t_{ca}^{2}t ^{2}_{hc }= S_{r}^{2 }– D^{2 }=
S_{r}^{2} - L^{2}_{oc} + t_{ca}^{2}OC = S _{c} - R_{o}L ^{2}_{oc} = OC · OCt _{ca} = OC · R_{d}S _{center} = S_{c} = [ X_{c} Y_{c} Z_{c
}]S _{radius} = S_{r}S _{surface} = S_{s} = [ X_{s} Y_{s} Z_{s
}]S _{r}^{2} = (X_{s} – X_{c})^{2}
+ (Y_{s} – Y_{c})^{2}
+ (Z_{s} – Z_{c})^{2}
This final equation gives us the implicit equation for a sphere. We can
test points to see if they in fact lie on the sphere's surface. The algebraic
solution is as follows. By substituting X(t), Y(t), and Z(t) in the form
of You can then solve the quadratic equation for t and find the closet intersection point, if any. However, we chose to use a faster geometric solution to the intersection problem which delays the square root of the quadratic equation and offers checks to bail out of the calculations sooner if an intersection is impossible. First we check if the ray originates inside the sphere by calculating
a vector from the ray origin to the center of the sphere and its magnitude:
If L Next we calculate the distance from the origin to the point along the
ray that is closest to the sphere's center. Following that comparison, we next calculate the half cord distance squared,
where the half chord distance is the distance from the point found by
tca and the surface of the sphere. ^{2}_{hc
}= S_{r}^{2 }– D^{2 }= S_{r}^{2}
- L^{2}_{oc} + t_{ca}^{2}D ^{2}_{
}= L^{2}_{oc} + t_{ca}^{2}If t _{i}
= [ X_{o} + X_{d} * t
Y_{o} + Y_{d} * t Z_{o} + Z_{d} * t ]R _{n}
= [ (X_{i} – X_{c})/S_{r} (Y_{i} – Y_{c})/S_{r}
(Z_{i} – Z_{c})/S_{r} ]We check all spheres in the sphere list in order to find the closest intersection if there is more than one. All direction vectors are normalized in our calculations to simplify and reduce the number of calculations required. This also helps prevent overflowing when we determine the magnitude of vectors by limiting the size of the result. The inverse radius and radius squared are precomputed and stored in the sphere list to save calculation time at the expense of memory/register usage. Plane Background Math _{origin }= R_{o }= [ X_{o}
Y_{o} Z_{o }]R _{direction }= R_{d }= [ X_{d} Y_{d} Z_{d
}]R(t) = R _{o} + R_{d} * tR _{intersection }= R_{i} = [ X_{i} Y_{i}
Z_{i} ] = [ X_{o} + X_{d} * t
Y_{o} + Y_{d} * t Z_{o} + Z_{d} * t ]R _{normal} = R_{n} = [ X_{n} Y_{n} Z_{n
}] = [ (X_{i} – X_{c})/S_{r} (Y_{i} – Y_{c})/S_{r}
(Z_{i} – Z_{c})/S_{r} ]P = A * x + B * y + C * z + D = 0 A ^{2} + B^{2 }+ C^{2} = 1D = - P _{n} · point, distance from [0 0 0]P _{normal} = P_{n} = [A B C]Planes, in comparison, require fewer calculations to determine if there
is a ray intersection. We start with the implicit equation for a plane. t
= - (A * X_{o} + B * Y_{o} + C * Z_{o} + D) /
(A * X_{d} + B * Y_{d} + C * Z_{d}) t = - (P _{n} · R_{o} + D) / P_{n} · R_{d}_{ }t
= v_{o} / v_{d} , where v_{o} = - (P_{n}
· R_{o} + D) and v_{d} = P_{n} · R_{d}
We calculate the denominator first. If v Next, we calculate the numerator v Reflections Figure 7 θ Physics tells us that the above two statements are true; the angle of
incidence equals the angle of reflection, and the reflection vector is
a linear combination of the incident and normal vectors. This can be transformed
into a useable equation by the following: _{i})
= cos(θ_{r})- I · N = N · R - I · N = α(N · I) + β If we set α = 1, β = - 2*(N · I). Substituting into our physical law, we get that, R = I – 2*(N · I)*N
The resulting reflection vector R is also normalized when the incident
vector I and the normal vector N are also normalized. Software/Hardware Tradeoff |