Computer Graphics, Spring 2025

Announcements

• Be careful when computing the bounding box of a triangle. If all three vertices lie an axis-aligned plane, your bounding box will have zero extent along one dimension (and hence it will have zero volume). This could be problematic in terms of down-stream numerical precision issues. To avoid this, consider padding your bounding box to make it a little bit bigger along each dimension.

Overview

• The code skeleton can be downloaded here.
• A short description of the files can be found here.
• An overview of the code you will be using can be found here or downloaded here.
• An overview of the .ray file syntax can be found here.
• Example .ray files can be downloaded here.
• A description of what your ray-tracer should do as you implement the different parts of the assignment can be found here.
• A (Windows x64) compiled version of the renderer implementing some of the basic features can be found here.

Getting Started

Note: Though you will need to modify the code in *.todo.* files, you can also augment the class definitions in the *.h files. However, please make sure to keep all function declarations in place.

After you download the files, the first thing to do is compile the program. To do this, you will first have to compile the GLEW, Image, (JPEG on Windows), Ray, and Util libraries and then compile the Assignment2 executable.

• On a Windows Machine
  Begin by double-clicking on Assignments.sln to open the workspace in Microsoft Visual Studios.
  • Compile the Assignment2 executable by right-clicking on "Assignment2" and selecting "Build". (If the GLEW.lib, Image.lib, JPEG.lib, Ray.lib, and Util.lib libraries have not already been compiled, they will be compiled first.)
  • The executable Assignment2.exe is compiled in Release mode for the 64-bit architecture and will be placed in the root directory.
• On a Linux Machine
  
  • Type make -f Makefile2 to compile the Assignment2 executable. (If the libGLEW.a, libImage.a, libRay.a, and libUtil.a libraries have not already been compiled, they will be compiled first.) This assumes that JPEG libraries have already been installed on your machine. (If it hasn't been installed yet, you can install it by typing sudo apt-get install libjpeg-dev.)
  • The executable Assignment2 is compiled in Release mode and will be placed in the root directory.
  • If you are having trouble linking either to the gl libraries or the glu libraries, you should install the associated packages:

    sudo apt-get install libgl1-mesa-dev libglu1-mesa-dev

    For subsequent assignments, you should also install the glut package:

    sudo apt-get install freeglut3-dev

  • If you are compiling under Linux and are getting an error about being unable to find pthread_create, try adding the parameter -pthread to the end of the definition of LFLAGS in Makefile2.

How the Executable Works

% Assignment2 --in <input ray-file name> --out <output image file name>

--width <image width>=640
--height <image height>=480
--rLimit <recursion limit>=5
--cutOff <recursion cut-off threshold>=0.0001
--lSamples <number of light samples>=100

How the Ray-Tracing Happens

• Ray::Shape::processFirstIntersection, and
• Ray::Shape::processAllIntersections

• ray: This is the Util::Ray3D traversing the scene graph.
• range: This is the Util::BoundingBox1D describing the range of times over which intersections are considered valid.
• rFilter: This is the Ray::Shape::RayIntersectionFilter filtering candidate intersection times. It is a function that takes in a double representing the time-to-intersection and returns a bool indicating if the associated intersection is valid. If it is not, the computation kernel does not get invoked. (If using Ray::Shape::processFirstIntersection, an invalid intersection does not count a first intersection and the traversal should continue.)
• rKernel: This is the Ray::Shape::RayIntersectionKernel describing the comptuation that is to be performed if a valid intersection is detected. It is a function that takes two arguments:
  • A Ray::ShapeShapeProcessingInfo object that describes information accumulated as the Util::Ray3D traversed the scene graph from the source, including the accumulated tranformations that were applied to the Util::Ray3D (these are set for you in Ray::AffineShape::processFirstIntersection and Ray::AffineShape::processAllIntersection) and the Ray::Material to be applied at the next intersection.
  • A Ray::RayShapeIntersectionInfo object describing the state of the intersection, including the time at which the intersection occured, the position of the intersection, the normal of the surface at the point of intersection, and the texture coordinate at the point of intersection.

What You Have to Do

The assignment is worth 30 points. The following is a list of features that you may implement. The number in parentheses corresponds to how many points it is worth.

• (1) Ray::Camera::getRay (Ray/camera.todo.cpp):
  Generate Util::Ray3Ds from the camera's position through (i,j)-th pixel of a widthxheight view plane.

• (2) Ray::ShapeList::processFirstIntersection (Ray/shapeList.todo.cpp):
  Cast rays through scene-graph nodes. For now, ignore the local transformation and bounding volume information, and compute the first intersection within the vector of Ray::Shapes associated to the Ray::ShapeList. If a valid intersection is found, construct a Ray::RayShapeIntersectionInfo object with the intersection information and invoke the Ray::Shape::RayIntersectionKernel rKernel with the intersection information. (The first argument to the kernel, an object of type Ray::Shape::ShapeProcessingInfo, should just be the argument passed in to Ray::ShapeList::processFirstIntersection).
  The list of shapes is stored in Ray::ShapeList::shapes.
  This method returns true if an intersection is found. It returns false if either there is no intersection in the range prescribed by the Util::BoundingBox1D range, or the filter Ray::Shape::RayIntersectionFilter rFilter returns false when evaluated with the time to intersection.

• (2) Ray::Sphere::processFirstInersection (Ray/sphere.todo.cpp):
  Compute ray intersections with a sphere and, if a valid intersection is found, apply the computation kernel to the point of intersection.
  Be sure so set the Ray::ShapeProcessingInfo::material member of the Ray::ShapeProcessingInfo object passed to the kernel to the meterial of the sphere.
  (Ignore the texture coordinates for now.)
  
  Hint

  To make things easier, you may want to consider using the Util::Polynomial3D class to represent the implicit function describing a sphere. In particular, this class defines the Util::Polynomial3D::operator() that evalutes the implicit function along a Util::Ray3D and returns the associated Util::Polynomial1D. You can then use the Util::Polynomial1D::roots method to find the roots of the polynomial.
  You can also use the Util::Polynomial3D::d method to get the partial derivative of the implicit function.

• (2) Ray::Triangle::processFirstIntersection (Ray/triangle.todo.cpp):
  Compute ray intersections with a triangle. (Ignore the texture coordinates for now.)
  Note that the containing Ray::TriangleList is responsible for setting the Ray::Material member material of the Ray::ShapeShapeProcessingInfo object passed to rKernel.
  
  Hint

  In computing the intersection of a ray with a triangle, there is a large amount of information that is re-computed, independent of the ray. Rather than computing this information each time, you are encouraged to pre-compute and re-use as much information as possible. You can declare auxiliary variables by adding them to the Ray::Triangle class (in Ray/Triangle.h) and you can set these values at the time that the scene-graph is initialized by adding to the Ray::Triangle::init method.

• (2) To obtain the ambient and diffuse color contributions of the lights at the point of intersection, implement:
  • Ray::PointLight::getAmbient and Ray::PointLight::getDiffuse (Ray/pointLight.todo.cpp);
  • Ray::SpotLight::getAmbient and Ray::SpotLight::getDiffuse (Ray/spotLight.todo.cpp); and
  • Ray::DirectionalLight::getAmbient and Ray::DirectionalLight::getDiffuse (Ray/directionalLight.todo.cpp).

• (2) To obtain the specular color contribution of the lights at the point of intersection, implement:
  • Ray::PointLight::getSpecular (Ray/pointLight.todo.cpp);
  • Ray::SpotLight::getSpecular (Ray/spotLight.todo.cpp); and
  • Ray::DirectionalLight::getSpecular (Ray/directionalLight.todo.cpp).

• (2) To determine if the point of intersection is in shadow from a particular light source, implement:
  • Ray::PointLight::isInShadow (Ray/pointLight.todo.cpp);
  • Ray::SpotLight::isInShadow (Ray/spotLight.todo.cpp); and
  • Ray::DirectionalLight::isInShadow (Ray/directionalLight.todo.cpp)
  In implementing this method, you will cast a ray from the intersection point in the direction of the light source. Keep in mind that for point- and spot-lights, you only need to test for intersections along a line segment (not the full ray), so you can use the range argument of the Ray::Shape::processFirstIntersection to limit the extent of the ray along which intersections are tested.

• (1) Ray::Scene::getColor (Ray/scene.todo.cpp):
  Using the material properties in the Ray::Shape::ShapeProcessingInfo::material member of the Ray::Shape::ShapeProcessingInfo object passed to the kernel, modify the definition of the computation kernel to take into account the emissive, ambient, diffuse, and specular contributions of all of the light sources (Ray::Light::getAmbient, Ray::Light::getDiffuse, Ray::Light::getSpecular), and use the Ray::Light::isInShadow method to determine if the light contributes.
  In order to implement this method, you will need to consider the contributions of all the light sources in the scene. The vector of lights is stored in Ray::GlobalSceneData::lights that Ray::Scene stores in Ray::Scene::_globalData.

• (1) Ray::StaticAffineShape::init (Ray/shapeList.todo.cpp):
  Initialize the local-to-global position transform Ray::StaticAffineShape::_inverseTransform and the local-to-global normal transform Ray::StaticAffineShape::_normalTransform.

• (2) Ray::Scene::getColor (Ray/scene.todo.cpp):
  Modify your definition of the computation kernel so that it takes into account the cumulative transformation information stored in the Ray::Shape::ShapeProcessingInfo object passed to the kernel.

• (1) Ray::Scene::getColor (Ray/scene.todo.cpp):
  Implement RayScene::Reflect (in scene.todo.cpp) so that given the normal n at a point of intersection, it returns the reflected direction of a ray hitting the surface with direction v. Then modify the implementation of Ray::Scene::getColor to recursively cast reflected rays from the point of intersection and add the reflected color contribution to returned color value. Be sure to:
  • Modulate the reflected color contribution by the specularity of the surface.
  • Terminate the recursion if the specularity of the surface is smaller than the cut-off cLimit.
  • Only compute the reflected color contribution when the ray is hitting the surface from the outside.

• (1) Ray::Scene::getColor (Ray/scene.todo.cpp):
  Modify the implementation of the computational kernel in Ray::Scene::getColor to recursively cast refracted rays through the point of intersection and add the refracted color contribution to returned color value, ignoring the indices of refraction for now. Be sure to:
  • Modulate the reflacted color contribution by the transparency of the surface.
  • Terminate the recursion if the transparency of the surface is smaller than the cut-off cLimit.

• (1) Ray::Sphere::processAllIntersections (Ray/sphere.todo.cpp):
  Support processing of all ray-sphere intersections instead of just the first.

• (2) Ray::Scene::getColor (Ray/scene.todo.cpp):
  To allow transparent objects to cast partial shadows, implement:
  • Ray::PointLight::transparency (Ray/pointLight.todo.cpp)
  • Ray::SpotLight::transparency (Ray/spotLight.todo.cpp)
  • Ray::DirectionalLight::transparency (Ray/directionalLight.todo.cpp)
  Hint

  To calculate transparencies you are interested in all (or at least multiple) intersections along a ray. To support this calculation, the method Ray::Shape::processAllIntersections invokes the computation kernel for every point of intersection (instead of just the first as in Ray::Shape::processFirstIntersection).
  Then, replace the call to Ray::Light::isInShadow with a call to Ray::Light::transparency in the implementation of Ray::Scene::getColor to allow for partial shadowing.
  As in the implementation of Ray::Light::isInShadow, for point- and spot-lights you only need to accumulate transparency along a line segment (not the full ray), so you can use the range parameter of the Ray::Shape::processAllIntersections to limit the extent of the ray along which intersections are tested.

• (2) Implement Ray::SphereLight::transparency (Ray/sphereLight.todo.cpp) to support illumination using a spherical light source. The method should compute the transparency by sending rays to (uniformly) random positions distributed over the surface of the sphere (with the random number given by the parameter samples) and computing the average transparency over the different rays.
  Hint

  To generate random samples on the unit sphere, you can repeatedly generate random samples inside the cube [-1,1]x[-1,1]x[-1,1], (e.g. using std::default_random_engine and std::uniform_real_distribution) until you find a sample that is inside the unit sphere and not at the origin. Then you can return the position, normalized to lie on the unit sphere.

• (2) Ray::Scene::getColor (Ray/scene.todo.cpp):
  Implement Ray::Scene::Refract (in scene.todo.cpp) so that, given the index of refraction ir of the surface at an intersection point and given the normal n at the point of intersection, it sets the refracted direction of a ray hitting the surface with direction v into the vector refract. The function should return a value of false if the ray could not be refracted (e.g. if computing the refraction direction would require evaluating the arcsin of a number with magnitude larger than 1 so that the angle of the ray is greater than the critical angle). Then, modify the implementation of Ray::Scene::getColor so that it uses the correct direction for computing the color contribution from refracted rays.

• Accelerated Ray-Tracing
  (3) Accelerate ray intersection tests with hierarchical bounding boxes. To do this you will have to:
  • Ray::Shape::updateBoundingBox (Ray/*.todo.cpp):
    For each shape you implement (Ray::Sphere, Ray::Triangle, etc.) this method should set the bounding box, Ray::Shape::_bBox.
  • Ray::AffineShape::updateBoundingBox (Ray/shapeList.todo.cpp):
    To implement Ray::AffineShape::updateBoundingBox, first update the bounding box of the shape that is to be affinely deformed, Ray::AffineShape::_shape and then compute the bounding box of the affinely deformed bounding box.
    Hint

    There is an overloaded operator* (apologies that the documentation seems messed up for this) that multiplies a Util::BoundingBox3D by a Util::Matrix4D representing an affine transformation, and returns the (smallest) Util::BoundingBox3D containing the affinely deformed vertices of the Util::BoundingBox3D.
  • Ray::ShapeList::updateBoundingBox (Ray/shapeList.todo.cpp):
    To implement Ray::ShapeList::updateBoundingBox, first update the bounding boxes of all the child Ray::Shapes and then compute a bounding box for the accumulation of bounding boxes, storing the result in the Ray::Shape::_bBox that Ray::ShapeList inherits from Ray::Shape.
    
    Hint

    The Util::BoundingBox3D defines Util::BoundingBox3D::operator+ and Util::BoundingBox3D::operator+= operators that return the (smallest) bounding box enclosing two bounding boxes.
  Note: At the very beginning of the Ray::Scene::rayTrace method the function calls Ray::Shape::updateBoundingBox on the root of the scene-graph. If you have implemented things correctly, this should trickle-down to all descendents in the graph.
  • Util::BoundingBox::intersect (Util/geometry.todo.inl):
    This method returns the 1D span (i.e. a Util::BoundingBox1D) of the intersection of the Util::Ray with the Ray::BoundingBox. If the ray does not intersect the bounding box, the returned bounding box is empty (which can be tested by calling Util::BoundingBox::isEmpty.)
    Note: Because of the use of templates, your implementation will have to support the more general case of intersecting a Dim-dimensional Util::Ray with a Dim-dimensional Ray::BoundingBox.
  • Ray::ShapeList::processFirstIntersection and Ray::ShapeList::processAllIntersections (Ray/shapeList.todo.cpp):
    Modify these methods to only test for an intersection of a Util::Ray with a child Ray::Shape if the intersection with the Ray::Shape's Ray::BoundingBox indicates there could be.
    
    Hint

    If either:

    • Calling Ray::BoundingBox::isEmpty on the intersection of the Util::Ray with the Ray::BoundingBox returns true, or
    • The maximaum value of the range parameter is less than the minimum value of the intersection of the the Util::Ray with the Ray::BoundingBox,

    then there cannot be an intersection of the Util::Ray with the Ray::Shape.
  • (2) Ray::ShapeList::processFirstIntersection and Ray::ShapeList::processAllIntersections (Ray/shapeList.todo.cpp):
    Modify these methods so that they first computes the intersection with the Util::BoundingBoxs of the Ray::Shapes in Ray::ShapeList::shapes, then sorts the shapes based on the proximity of the start of their Util::BoundingBox intersection, and finally intersects the Ray::Shapes in order, allowing for early termination of the ray tracing.
    
    Hint

    • You may want to use a std::vector of Ray::ShapeBoundingBoxHits to store information about the intresection of the Util::Ray with the Util::BoundingBoxs and then call std::sort using Ray::ShapeBoundingBoxHit::Compare as the comparison function.
    • Rather than declaring the std::vector every time Ray::ShapeList::processFirstIntersection and Ray::ShapeList::processAllIntersections (Ray/shapeList.todo.cpp) are called, you can add it as a member of Ray::ShapeList and then resize it within the Ray::ShapeList::init method. (To get around the fact that Ray::ShapeList::processFirstIntersection is declared const, you may want to use const_cast to remove the const designator from the std::vector.)
  • (1) Ray::ShapeList::processAllIntersections (Ray/shapeList.todo.cpp and Ray/triangle.todo.cpp):
    Modify the implementation of Ray::ShapeList::processAllIntersections to test if range overlaps the bounding boxes and only propagate the traversal to those Ray::Shapes whose bounding box overlaps range non-trivially.
  • (1) Ray::Scene::rayTrace (Ray/scene.cpp):
    Attempt to parallelize your code by commenting out the line:

    for( size_t idx=0 ; idx<(size_t)(width*height) ; idx++ ) RayTraceFunction( 0 , idx );

    and replacing it with the next line:

    ThreadPool::Parallel_for( 0 , (size_t)(width*height) , RayTraceFunction );

    Note that if you initialized resources to accelarate intersection testing, you will like need to initialize separate resources for each paralellization thread. To help you with this, the function ThreadPool::NumThreads gives the (maximum) number of parallelization threads and most of the function performing ray-intersection take a tIdx argument indicating the index of the thread doing the processing.

• (2) Ray::Triangle::processFirstIntersection (Ray/triangle.todo.cpp):
  Modify this method so that it sets the texture coordinates at the point of intersection within Ray::RayShapeIntersectionInfo::texture and modify the computation kernel Ray::Scene::getColor (Ray/scene.todo.cpp) to support texture mapping (with bilinear interpolation of texture samples). That is, modulate the contribution of the emissive, ambient, diffuse, and specular terms by multiplying by the color sampled from the texture map.

• (1) Implement a jittered supersampling scheme to reduce aliasing by casting multiple rays per pixel, randomly jittered about pixel centers, and averaging the radiance samples.

• (1) Generate a 3D scene and save it as a .ray file. The scene should have both spheres and triangles, should have all three types of light sources in it, and should contain at least one primitive with a transparent material.

• (1) Ray::Box::processFirstIntersection, Ray::Box::processAllIntersections, and Ray::Box::updateBoundingBox (Ray/box.todo.cpp):
  Compute ray intersections with a box. (Feel free to add functionality to Ray::Box::init if you need it.)

• (1) Ray::Cylinder::processFirstIntersection, Ray::Cylinder::processAllIntersections, and Ray::Cylinder::updateBoundingBox (Ray/cylinder.todo.cpp):
  Compute ray intersections with a cylinder. (Feel free to add functionality to Ray::Cylinder::init if you need it.)

• (1) Ray::Cone::processFirstIntersection, Ray::Cone::processAllIntersections, and Ray::Cone::updateBoundingBox (Ray/cone.todo.cpp):
  Compute ray intersections with a cone. (Feel free to add functionality to Ray::Cone::init if you need it.)

• (2) Ray::Torus::processFirstIntersection, Ray::Torus::processAllIntersections, and Ray::Torus::updateBoundingBox (Ray/torus.todo.cpp):
  Compute ray intersections with a torus. (Feel free to add functionality to Ray::Torus::init if you need it.)

• (3) Constructive solid geometry
  • Ray::Shape::isInside (Ray/*.todo.cpp):
    Implement a function that returns true if a point is inside of the shape and false if it is outside.
    For the Ray::Triangle, you can leave the implementation as is -- returning false because a triangle does not have a well-defined inerior/exterior.
  • Ray::Union::processFirstIntersection, Ray::Union::processAllIntersections, Ray::Union::updateBoundingBox, and Ray::Union::isInside (Ray/shapeList.todo.cpp):
    This Ray::Shape represents the union of the set of shapes stored in Ray::Union::_shapeList. In contrast to the class Ray::ShapeList, the surface of a Ray::Union consists of all points with the property that they are on the surface of one of the Ray::Shapes in Ray::Union::_shapeList and not in the interior of any of the others.
  • Ray::Intersection::processFirstIntersection, Ray::Intersection::processAllIntersections, Ray::Intersection::updateBoundingBox, and Ray::Intersection::isInside (Ray/shapeList.todo.cpp):
    This Ray::Shape represents the intersection of the set of shapes stored in Ray::Intersection::_shapeList. The surface of a Ray::Intersection consists of all points with the property that they are on the surface of one of the Ray::Shapes in Ray::Intersection::_shapeList and in the interior of all of the other others.
  • Ray::Difference::processFirstIntersection, Ray::Difference::processAllIntersections, Ray::Difference::updateBoundingBox, and Ray::Difference::isInside (Ray/shapeList.todo.cpp):
    This Ray::Shape represents the differences of the set of thes shapes stored in Ray::Difference::_shape0 and Ray::Difference::_shape1. The surface of a Ray::Difference consists of all points with the property that they are either:
    • on the surface of Ray::Difference::_shape0 and exterior to on the surface of one of the Ray::Difference::_shape1, or
    • on the surface of Ray::Difference::_shape1 and in interior to Ray::Difference::_shape0.
    Hint

    For computing the intersection of a Util::Ray3D with a Ray::Union, a Ray::Intersection, or a Ray::Difference, you can use the argument rFilter in the Ray::Shape::processFirstIntersection and Ray::Shape::processAllIntersections methods to ignore intersections with the individual shapes that are not on the surface of the union, instersection, and difference respectively.

• (2) Implement procedural texture mapping with Perlin noise functions to create 3-D solid wood, marble, etc.

• (1) Implement bump mapping for either or both texturing schemes.

• (1) Simulate the behavior of a real camera lens by implementing the procedure in this SIGGRAPH paper.

• (2) Accelerate ray intersections with an octree or BSP spatial data structure.

• (?) Impress us with something we hadn't considered...

• (1) Submitting one or more images for the art contests.
• (1) Submitting one or more .ray files for the art contests.
• (1) winning the regular art contest,
• (1) winning the .ray file art contest,
• (?) Implementing an accelerated ray-tracer that can ray-trace a very large model in very little time (e.g. a few minutes for a model consisting of hundreds of thousands of triangles, with a recursion depth of 5).

It is possible to get more than 30 points. However, after 30 points, each point is divided by 2, and after 32 points, each point is divided by 4. If your raw score is 29, your final score will be 29. If the raw score is 33, you'll get 31.25. For a raw score of 36, you'll get 32.

What to Submit

• A write up describing what you have implemented and what you did for the art contest. (See the general submission page for more information.)
• For the code, pack the contents of the Ray folder into Ray.zip. Submit the Ray.zip file as well as the geometry.todo.inl file from the Util folder.
• For the art contest, pack the submissions (both .ray files as well as images) into artcontest.zip.
• In summary, the file tree you upload should look like:
  • writeup.pdf
  • [Ray.zip]
  • [geometry.todo.inl]
  • [artcontest.zip]
    • awesomepicture.bmp
    • interestingartpiece.ray
    • ...