CS184 AS6: Reflections and Acceleration Structures
DUE DATE: Saturday March 5, 11:00pm
Groups of two are allowed!
Aim
In this assignment we add reflections to our raycaster to make it a
proper raytracer.
To support rendering more complicated scenes, we
will also implement a data structure for sublinear intersection tests of
our scene. Speedup structures come in many forms; for this assignment we
will strongly suggest using Hierarchical Axis-Aligned Bounding Boxes
[Shirley, 10.9.2] {or 12.3.2}.
IMPORTANT: To complete this project, we assume you've already read the textbook's chapter 6, 9 and 10.
Minimum Specifications
For this assignment, modify your raytracer in the following ways:
- Raytracing:
- Reflection: Create rays which reflect off objects (the
so-called "bounce ray"), and are again sent into the scene in the
bounce direction. To accomplish
this, write your raycast(Ray, depth) function in such a way that it can be
used recursively. Use ks as the coefficient of
reflection and multiply pairwise against S (as defined in as4) to account
for metalness: ks *
pairwiseMult(S, raycast(ray, depth-1)).
- Limited Bounce Depth: In theory you could estimate when the
maximum possible contribution
from an additional recursive bounce-ray is less than say 1/256, then
stop recursion at that point.
But estimating a good bound on maximum possible contribution is
tricky, and you would likely have excessive bounces in highly
reflective, brightly lit scenes. Instead, just set a hard limit
for the number of consecutive bounce
rays, i.e., terminate the recursive raycasts after some
specified depth. Set the default depth to 4 (so, discounting shadow
rays, you will cast at most 4 rays per image sample).
- Hierarchical Axis-Aligned Bounding Boxes (AABB trees) -- Construction:
- Construct an acceleration structure that
allows for sublinear time intersection tests. This acceleration structure
is in world space. Specifically, use an Axis Aligned Bounding
Box Tree
- Recursive Construction: You will now write a recursive
function that takes in a current list of primitives and an AABB node, and
constructs the given node's children or makes it a leaf node. Call this
function with a root node and the whole list of primitives.
- If you've reached some maximum recursive
depth or the number of primitives is less than the
maximum number of primitives you want to store in a leaf node, then
declare the current node a leaf and store all the primitives in this
leaf.
- If not, we need to separate the current list
of primitives into a left and a right list by partitioning the primitives
according to some axis. You can either calculate the average centroid of
the current list of primitives, or you can find the median of the current
list of primitives. Once you've done this, you can partition the list
into primitives on the left or on the right of this partitioning point.
To separate it into left and right, you need to consider only one of the
three axes. In Shirley, the suggestion is to cycle through axes as you
move down the tree. If you don't use the median to partition, a better
solution is to calculate which axis would
give the best partitioning. Calculate the difference in number of
primitives between the left and right branch for each axis. Choose to
partition the list by the axis that makes this difference the smallest,
thus constructing the most balanced tree.
-
Now that you've partitioned this list into
two sublists, create a left and a right child node for the current node,
and recursively call this build function on the left and right child
nodes with their respective left and right partitioned lists.
- When you reach the leaf nodes, your function
should return a bounding box for that node. The recursive function was
used to create the tree moving downwards, now we will generate the nested
bounding box hierarchy as we return bounding boxes upwards. At each node,
save its bounding box by constructing a bounding box out of both
children's bounding boxes. After this is complete, you should have a
nested bounding box structure.
- Hierarchical Axis-Aligned Bounding Boxes -- Traversal:
- After having built this additional data-access structure you
can now do the queries as to what each ray intersects much more
efficiently.
- Ray - Bbox intersection tests start at the root of the
hierarchy and will recursively test each child bounding box that the ray
intersects, starting with the closest.
- When the ray finally intersects a bounding box of a leaf, it
will then do an intersection calculation with each primitive in the leaf.
The closest intersection found in the leaf can then be returned up the
tree as a candidate for closest intersection point, and
optionally used to skip recursing into bounding boxes which would be hit
after that point.
- Evaluation of Performance Gain:
- Compare the rendering times in your ray-tracer with and without
using this data structure. Specifically, set max objects in a leaf to 1,
and then note timings for max depths of 1, 2, 8 and 16 for the two
provided scenes. Write a few sentences explaining the performance
differences you observe.
Extra Credit ideas:
- Mesh intersection: The provided scene loading framework
also supports loading triangle meshes from OBJ files. Use this to add
triangle mesh intersection to your raytracer, and trace some scenes with
meshes.
- Refraction: Create rays that can travel through your
scene primitives depending on coefficients of refraction (kt the
transparency of
the material and ktn the refractive index of the material). These rays
should bend according to Snell's
Law. Assume that the air has a refractive
index of 1 (thus, the "n" value for air in snell's law is 1).
- Different acceleration structures: Implement other
acceleration structures, such as KD
Trees or Bounding Interval
Hierarchies. Compare the performance you get.
- Other performance experiments: Experiment with
interesting other ways to improve performance of your raytracer. For
example, you could try progressively rendering the scene so that some
low resolution rendering is returned in real time, and the result is
iteratively refined over time. Or experiment with threading your program,
or even implementing it on a GPU.
Example Scene (for submission)
We want to see that your speedup
structures actually work. To that end, we're supplying you with a 1000
sphere scene that you need to render. In addition, we supply a smaller scene with some interesting reflections.
For those who want to
implement triangle meshes (one of the extra credit suggestions), here are
some scenes with OBJ files for you to have fun with:
Submission
To submit this project, all of the following needs to be done by the deadline:
- Submit using the submit as6 command on the INST machines:
- A copy of your code, including the whole framework, that compiles on the platform you
developed on.
- A README.txt containing: Your name, SID, Login and a description of the platform your
code compiles on, and any extra credit you did.
Also include your performance analysis (timings for depths
1,2,8,16, and a few sentences of analysis) for the thousand spheres and
helical spheres scenes.
- TWO
images generated by your raytracer. One of the thousand spheres scene, and one
of helical spheres scene.
- Put on your class instructional website:
- A separate page for this assignment.
- On this page, the images you are turning in, as well as the scene and OBJ files for them.
Windows Users: The grader should ONLY have to open your .sln file and press F5 to build and run your solution.
*Nix Users: The grader should ONLY have to run make with the appropriate makefile to build your project. Thus, for Mac and Linux
make
and for solaris
gmake
.
Note:
The submit program retains the directory structure of what you send it.
Thus, we recommend making a new directory for your assignment on the
server, cd'ing into that directory, copying the whole framework with
your code into this directory, and running
submit as6
to easily submit the whole project to us.
Group submissions
For this project, groups of two are allowed. If you're working in a group, only one of you should submit the full
project results; the other should only submit the README.txt file. Both of you should include your partner's name in the
README.txt file.
Implementation Tips
When testing performance, you'll want to enable optimizations in your
compiler. For mac and unix, the makefile should already do this for you.
For visual studio you can set the project to compile in 'Release
mode'.
To time your program performance, you can use the clock() function from
time.h. Use CLOCKS_PER_SEC to convert the timing value to
seconds.
Accessing Mesh Data (optional / extra credit)
Meshes are represented as an OBJTriangleMesh struct
containing a list of OBJTriangle and a list of OBJVertex objects. An
OBJTriangle consists of three indices, that indicate which OBJVertex
objects define the three corners of the mesh. Check whether a SceneGroup
contains a Mesh by using the SceneGroup.computeMesh() function. Each mesh
has its own color, material and transform just as Spheres had their own
color, material and transform.