Due: March 21, 2021 @ 11:59 PM

Important Notes

  1. Read the submission instructions carefully!

Table of Contents

For your second programming assignment you will implement a Bounding Volume Hierarchy and use it to ray trace two scenes. The first scene will simply be spheres. The second scene will be a rendering of a triangulated surface mesh.

Building the BVH

BVH

Construct a BVH with the following characteristics

  • The structure is a binary tree

  • Axis-aligned bounding boxes (AABBs) are used as the bounding volumes.

    Reference: Ray Tracing Next Week Section 3 Link

  • The partitioning scheme cuts the axis on which the projected AABB centroids have the greatest spread.
    The midpoint method is used to position the partition.

    Reference: Physically Based Rendering Section 4 Link

  • The structure supports both triangles and spheres as geometric primitives.
  • Geometric primitives are located at the leaf nodes, with each leaf containing \(k\) or fewer primitives.
    The choice of \(k\) is up to you.

Rendering Spheres

Spheres

Use the BVH to render a set of scenes containing many, many spheres and do a performance study.

  • Render the spheres using the Phong reflection model. Just the diffuse component is sufficient.
  • Have the color of the spheres vary…you can randomly choose a color from a small set (e.g. red, green, and blue).
  • Use a directional or point light. You can use multiple light sources if you wish.
  • You should position the spheres such that all of them will be inside the view volume. The positioning can be structured or random. A structured placement will place sphere centers at points in a grid, stepping by uniform amounts along the \(x\), \(y\), and \(z\) axes.
  • The radii of the spheres can be uniform. Choose what ever value you to generate a reasonable image.
  • Render 3 different scenes; one with 1000 spheres, one with 10,000 spheres and one with 100,000 spheres.

Performance Study

Time how long it takes to render the scene with a BVH and without it. Construct a table such as this one: Table

Obviously…your table should replace the word grid with BVH. Write a brief paragraph that details the following:

  • what programming language you used.
  • what type of CPU was used
  • what GPU was used if you are implementing a GPU-based ray-tracer
  • number of rays shot per pixel

If your renderer breaks down and can’t render some given number of spheres, record a value of NA in the table.

Rendering a Mesh

Dragon

Finally, add support to your renderer to import triangulated surface meshes and render them using the BVH:

  1. You can write your code to read an OBJ file…or you can use a library function. Either is acceptable. A number of OBJ files are listed at the end of this assignment, you can select one (or more) of those to read and render. Parsing these files is pretty simple…they typically only use the line tags F and V and # so you do not need to implement a full-featured parser.

    Reference: OBJ File Format Wikipedia Link
    Reference: Tiny OBJ Loader C++ Library Github Repo

  2. Compute per-vertex normals using area weighted averaging of the surrounding triangle normals.

    Reference: Normals Week 6 Lecture

  3. Compute the normal vector at a hit point on the mesh by using barycentric interpolation of the normals of the vertices of the enclosing triangle.

    Reference: Barycentric Coordinates Week 4 Lecture

  4. Shading that uses both diffuse and specular reflection components of the Phong reflection model

    Reference: Phong reflection model wikipedia link

Using a BVH for a Mesh

While there are several reasonable approaches, we would suggest using a BVH with a mesh in following way way:

  • Build a BVH using the untransformed geometry of the mesh (i.e. build it in the model coordinate space).
  • Consider creating leaf nodes when the number of triangles in the node is less than some thereshold \(k\) where \(k>1\)…there probably is little performance to be gained from building the tree so finely.
  • If an affine transformtion (i.e. a model transformation is associated with the mesh, use an inverse-transformed ray to test against the mesh instance.

This MP does not require a scene witha mesh and multiple objects. But if you were to create suchs as scene each mesh shold have it’s own BVH. You can use a global BVH where the mesh is considered a single object in that BVH…and then when testing a ray against the mesh you use the mesh BVH.

Hand-in

  • You will hand in your code and 4 images and a report:

    Submit 3 renderings of the spheres from your performance study.
    These should be 1000 spheres and 10,000 spheres and 100,000 spheres respectively. Submit one rendering of your mesh.
    The images should be at at least 400x400 and in the PPM or PNG format.
    If 400x400 is too large for the sphere images use 200x200.

  • You also need to write a brief technical report:

    Write one paragraph describing your BVH implementation and the platform you ran your tests on. Include a table that shows the time required to render the following 1000 spheres, 10,000 spheres, and 100,000 spheres with and without using the BVH for acceleration. This can be just a text file, a link to a Google doc, or a PDF file.

  • Include a link to a repo containing your source code as note in the submission or in a readme.md file

    Hand-in will be done on Compass. Upload a zipped folder containing the above materials.

Resources

  • Cow mesh OBJ
    Cow

  • Bunny mesh OBJ
    Bunny

  • Dragon mesh OBJ
    Dragon

  • Teapot mesh OBJ
    Teapot

Note that these meshes may need to be scaled and translated to work with easily. You can do so as pre-processing step or you can implement affine transformations in your renderer.

Reference: Affine Transformations Week 6 Lecture

Submission Instructions

Hand-in will be done on Compass.

Name Points Description
Commented 10 Each function in your code is commented in the required style.
Import a Mesh 10 Read a mesh from an OBJ file
Per-vertex normals 10 For the mesh, generate per-vertex normals using triangle area weighting
Smooth shading 20 For the mesh, generate interpolated normal at a hitpoint using barycentric interpolation of the triangle per-vertex normal
Construct BVH 20 Build a BVH based on AABBs supporting sphere and triangle geometric primitives.
BVH speedup 10 Show the BVH is effective using a 1000 sphere scene
10000 Spheres 10 Demonstrate ability to render 10000 spheres
100000 Spheres 5 Demonstrate ability to render 10000 spheres
Technical Report 5 Submit a concise and clear document of the BVH performance.
Total 100