Final Project: Developing and Optimizing an HPC Ray Tracing Engine

The final project is optional and meant to increase your final grade. If you have completed all the bonus exercises, your starting grade is B, and you will need to achieve +1 to obtain an A as the final grade.

If you don't want to complete the final project, please upload a pdf file stating the expected final grade.

The final project allows you to apply some of the concepts and approaches you learned during the course to a topic of your interest.

The final project is individual and not in groups.

Project - Developing and Optimizing HPC Ray Tracing Engine

A. The Ray Tracing Model

Ray tracing consists of rendering a scene by simulating the physical properties of light propagation. This rendering method leads to photorealistic scenes, but it is computationally intensive and therefore optimization is needed.

We model a 3D scene with objects such as planes and spheres. In the example, we model one sphere. There is also a camera and a plane representing the rendered image

There is the main loop over all pixels of the image. 

For each pixel, we launch a ray from the camera center to the scene through the current pixel and compute the first intersection point between that ray and an object from the scene.

Then, we compute the pixel's color as a function of the object material's color, the position of the lights, the normal of the object at the intersection point, and so on.

There are several physics-based lighting equations that describe how the color depends on these parameters. In this project, we use the Blinn-Phong shading model with ambient, diffuse, and specular lighting components

A full ray tracing engine is far more complex. For instance, we can model other optic and lighting characteristics such as reflections, refractions, shadows, depth of field, and others. It is also possible to implement ray tracing algorithms on the graphics card for real-time photorealistic rendering.

Blinn-Phong shading model on Wikipedia, available at https://en.wikipedia.org/wiki/Blinn-Phong_shading_model (Links to an external site.)

 (Links to an external site.)Ray tracing on Wikipedia, available at https://en.wikipedia.org/wiki/Ray_tracing_%28graphics%29 (Links to an external site.)

B. The Ray Tracing Engine in Python

To explain the development of a ray-tracing engine we use the Python language and NumPy operations that provide basic primitives for vector operations. Your task is to develop, monitor the performance, and optimize a ray-tracing engine.

1. Import module for NumPy and plotting, and set scene size

>>> import numpy as np
    import matplotlib.pyplot as plt
>>> w, h = 400, 400  # Size of the screen in pixels.

2. Create a normalization function for vectors

>>> def normalize(x):
        # This function normalizes a vector.
        x /= np.linalg.norm(x)
        return x

3. Create a function that computes the intersection of a ray with a sphere

>>> def intersect_sphere(O, D, S, R):
        # Return the distance from O to the intersection
        # of the ray (O, D) with the sphere (S, R), or
        # +inf if there is no intersection.
        # O and S are 3D points, D (direction) is a
        # normalized vector, R is a scalar.
        a = np.dot(D, D)
        OS = O - S
        b = 2 * np.dot(D, OS)
        c = np.dot(OS, OS) - R * R
        disc = b * b - 4 * a * c
        if disc > 0:
            distSqrt = np.sqrt(disc)
            q = (-b - distSqrt) / 2.0 if b < 0 \
                else (-b + distSqrt) / 2.0
            t0 = q / a
            t1 = c / q
            t0, t1 = min(t0, t1), max(t0, t1)
            if t1 >= 0:
                return t1 if t0 < 0 else t0
        return np.inf

4. Create a function that traces a ray and apply the Bling-phon shading

>>> def trace_ray(O, D):
        # Find first point of intersection with the scene.
        t = intersect_sphere(O, D, position, radius)
        # No intersection?
        if t == np.inf:
            return
        # Find the point of intersection on the object.
        M = O + D * t
        N = normalize(M - position)
        toL = normalize(L - M)
        toO = normalize(O - M)
        # Ambient light.
        col = ambient
        # Lambert shading (diffuse).
        col += diffuse * max(np.dot(N, toL), 0) * color
        # Blinn-Phong shading (specular).
        col += specular_c * color_light * \
            max(np.dot(N, normalize(toL + toO)), 0) \
            ** specular_k
        return col

5.  The main loop through all pixels is implemented in the function below. 

>>> def run():
        img = np.zeros((h, w, 3))
        # Loop through all pixels.
        for i, x in enumerate(np.linspace(-1, 1, w)):
            for j, y in enumerate(np.linspace(-1, 1, h)):
                # Position of the pixel.
                Q[0], Q[1] = x, y
                # Direction of the ray going through
                # the optical center.
                D = normalize(Q - O)
                # Launch the ray and get the color
                # of the pixel.
                col = trace_ray(O, D)
                if col is None:
                    continue
                img[h - j - 1, i, :] = np.clip(col, 0, 1)
        return img

6. We initialize the scene and define a few parameters

>>> # Sphere properties.
    position = np.array([0., 0., 1.])
    radius = 1.
    color = np.array([0., 0., 1.])
    diffuse = 1.
    specular_c = 1.
    specular_k = 50
    
    # Light position and color.
    L = np.array([5., 5., -10.])
    color_light = np.ones(3)
    ambient = .05
    
    # Camera.
    O = np.array([0., 0., -1.])  # Position.
    Q = np.array([0., 0., 0.])  # Pointing to.

7. The final step is to render the scene

>>> img = run()
    fig, ax = plt.subplots(1, 1, figsize=(10, 10))
    ax.imshow(img)
    ax.set_axis_off()
    plt.show()

The final outcome should be something like this:

Code: raytracing.py  

An extended version of the code with plane intersections and multiple spheres is available at: https://gist.github.com/rossant/6046463 (Links to an external site.)

C. Project Assignment

The goal of this project is to develop and optimize a simple ray tracing engine, characterize its performance (via using the tools you learn), and submit a report.

You can use the Python code presented above as starting point for your implementation and as the base of your implementation.

For the sake of the project, you can only visualize the sphere, as in the example above. However, feel free to visualize more complicated scenes as in https://gist.github.com/rossant/6046463 (Links to an external site.).

When characterizing the performance, make sure to vary the image size and other factors that impact the performance. Also report the average of execution times and errors, e.g. standard deviation of min and max of the performance measurements. Make sure to include the performance plots and analysis in the report.

The project also includes the preparation of a report (max 8 pages).

D. Project Report 

The report should include your name and the expected final grade (A, B, ...). The report should be a maximum of 8 pages long.

Report Format

The report should include at least the following sections:

• Introduction. Provide some background on the performed problem
• Methodology. Explain all the different steps in your implementation 
• Experimental Setup. Describe the computing platform (both software and hardware) you used for your project and the tools you used.
• Results. Present the validation tests, together with performance/profiling results.
• Discussion and Conclusion. Discuss the performance results critically providing insights about performance bottlenecks. Describe the challenges and limitations of your work. Discuss the optimization and their performance result.

• The final project is optional and meant to increase your final grade. If you have completed all the bonus exercises, your starting grade is B, and you will need to achieve +1 to obtain an A as the final grade.

  The final project allows you to apply some of the concepts and approaches you learned during the course to a topic of your interest.

  The project is individual and not in groups.

  Project - Developing and Optimizing a Ray Tracing Engine 

  A. The Ray Tracing Model

  Ray tracing consists of rendering a scene by simulating the physical properties of light propagation. This rendering method leads to photorealistic scenes, but it is computationally intensive and therefore optimization is needed.

  We model a 3D scene with objects such as planes and spheres. In the example, we model one sphere. There is also a camera and a plane representing the rendered image

  

  There is the main loop over all pixels of the image. Likely, we are going to optimize this loop.

  For each pixel, we launch a ray from the camera center to the scene through the current pixel and compute the first intersection point between that ray and an object from the scene.

  Then, we compute the pixel's color as a function of the object material's color, the position of the lights, the normal of the object at the intersection point, and so on.

  There are several physics-based lighting equations that describe how the color depends on these parameters. In this project, we use the Blinn-Phong shading model with ambient, diffuse, and specular lighting components

  

  A full ray tracing engine is far more complex. For instance, we can model other optic and lighting characteristics such as reflections, refractions, shadows, depth of field, and others. It is also possible to implement ray tracing algorithms on the graphics card for real-time photorealistic rendering.

  Blinn-Phong shading model on Wikipedia, available at https://en.wikipedia.org/wiki/Blinn-Phong_shading_model (Links to an external site.)

   (Links to an external site.)Ray tracing on Wikipedia, available at https://en.wikipedia.org/wiki/Ray_tracing_%28graphics%29 (Links to an external site.)

  B. The Ray Tracing Engine in Python

  To explain the development of a ray-tracing engine we use the Python language and NumPy operations that provide basic primitives for vector operations. Your task is to develop and optimize a ray-tracing engine.

  1. Import module for NumPy and plotting, and set scene size

  >>> import numpy as np
      import matplotlib.pyplot as plt
  >>> w, h = 400, 400  # Size of the screen in pixels.

  2. Create a normalization function for vectors

  >>> def normalize(x):
          # This function normalizes a vector.
          x /= np.linalg.norm(x)
          return x

  3. Create a function that computes the intersection of a ray with a sphere

  >>> def intersect_sphere(O, D, S, R):
          # Return the distance from O to the intersection
          # of the ray (O, D) with the sphere (S, R), or
          # +inf if there is no intersection.
          # O and S are 3D points, D (direction) is a
          # normalized vector, R is a scalar.
          a = np.dot(D, D)
          OS = O - S
          b = 2 * np.dot(D, OS)
          c = np.dot(OS, OS) - R * R
          disc = b * b - 4 * a * c
          if disc > 0:
              distSqrt = np.sqrt(disc)
              q = (-b - distSqrt) / 2.0 if b < 0 \
                  else (-b + distSqrt) / 2.0
              t0 = q / a
              t1 = c / q
              t0, t1 = min(t0, t1), max(t0, t1)
              if t1 >= 0:
                  return t1 if t0 < 0 else t0
          return np.inf

  4. Create a function that traces a ray and apply the Bling-phon shading

  >>> def trace_ray(O, D):
          # Find first point of intersection with the scene.
          t = intersect_sphere(O, D, position, radius)
          # No intersection?
          if t == np.inf:
              return
          # Find the point of intersection on the object.
          M = O + D * t
          N = normalize(M - position)
          toL = normalize(L - M)
          toO = normalize(O - M)
          # Ambient light.
          col = ambient
          # Lambert shading (diffuse).
          col += diffuse * max(np.dot(N, toL), 0) * color
          # Blinn-Phong shading (specular).
          col += specular_c * color_light * \
              max(np.dot(N, normalize(toL + toO)), 0) \
              ** specular_k
          return col

  5.  The main loop through all pixels is implemented in the function below. This is likely the loop that you will optimize.

  >>> def run():
          img = np.zeros((h, w, 3))
          # Loop through all pixels.
          for i, x in enumerate(np.linspace(-1, 1, w)):
              for j, y in enumerate(np.linspace(-1, 1, h)):
                  # Position of the pixel.
                  Q[0], Q[1] = x, y
                  # Direction of the ray going through
                  # the optical center.
                  D = normalize(Q - O)
                  # Launch the ray and get the color
                  # of the pixel.
                  col = trace_ray(O, D)
                  if col is None:
                      continue
                  img[h - j - 1, i, :] = np.clip(col, 0, 1)
          return img

  6. We initialize the scene and define a few parameters

  >>> # Sphere properties.
      position = np.array([0., 0., 1.])
      radius = 1.
      color = np.array([0., 0., 1.])
      diffuse = 1.
      specular_c = 1.
      specular_k = 50
      
      # Light position and color.
      L = np.array([5., 5., -10.])
      color_light = np.ones(3)
      ambient = .05
      
      # Camera.
      O = np.array([0., 0., -1.])  # Position.
      Q = np.array([0., 0., 0.])  # Pointing to.

  7. The final step is to render the scene

  >>> img = run()
      fig, ax = plt.subplots(1, 1, figsize=(10, 10))
      ax.imshow(img)
      ax.set_axis_off()
      plt.show()

  The final outcome should be something like this:

  

  Code: raytracing.py 

  An extended version of the code with plane intersections and multiple spheres is available at: https://gist.github.com/rossant/6046463 (Links to an external site.)

  

  C. Project Assignment

  The goal of this project is to develop and optimize a simple ray tracing engine, characterize its performance and submit a report. You can use the Python code presented above as starting point for your implementation and optimization. 

  You can use any performance monitoring and optimization approach you learned during the course. 

  For the sake of the project, you can only visualize the sphere, as in the example above. However, feel free to visualize more complicated scenes as in https://gist.github.com/rossant/6046463 (Links to an external site.).

  When characterizing the performance, make sure to vary the image size and other factors that impact the performance. Also report the average of execution times and errors, e.g. standard deviation of min and max of the performance measurements. Make sure to include the performance plots and analysis in the report.

  The project also includes the preparation of a report (max 8 pages).

  D. Project Report 

  The report should include your name and the expected final grade (A, B, ...). The report should be a maximum of 8 pages long.

  Report Format

  The report should include at least the following sections:

  • Introduction. Provide some background on the performed problem
  • Methodology. Explain all the different steps in your implementation, performance monitoring and optimization 
  • Experimental Setup. Describe your computing platform (both software and hardware) you used for your project and the tools you used.
  • Results. Present the validation tests, together with performance/profiling results.
  • Discussion and Conclusion. Discuss the performance results critically. Describe the challenges and limitations of your work. If optimizations are included, discuss the optimization and their performance result.
  • References. Provide a list of articles and books you consulted for preparing the project.

  Submission

  Please upload to Canvas the final report as a pdf file and provide a link to the GitHub (either in the report or as a comment) repository with your code.

  References. Provide a list of articles and books you consulted for preparing the project.

Submission

Please upload to Canvas the final report as a pdf file and provide a link to the GitHub (either in the report or as a comment) repository with your code.