CS 426 Graphics Group Project

JAW ray tracer

Team members

Introduction

We (aaron, wagner and jing) are going to do a ray tracing project for the COS426. The project will demonstrate the technique we have learnt from the course. The project will also do some bench marking in investigating the efficiency of different algorithms and data structures. Since we all have done a basic ray tracer in assignment 5, the following paragraphs will illustrate the special features that we have implemented in this project.

Special Features of Our Project

Hierarchical Bounding Volume and Octree Representation

The idea for the Octree Representation is to subdivide the space into 8 parts (either uniformly or adaptively) and store a list of objects in each box so that the object-ray intersection test will not be performed if the ray does not hit the box. The termination criterion is usually set to the maximum level of the tree or the number of objects in the box is small enough. The advantage of this scheme the number of object-ray intersection tests can be reduced, but the disadvantage is we need to calculate the ray-box intersection as the ray proceed from one box to another. Another way of organising the objects is to use the Automatic Hierarchical Bounding Volume (HBV). This idea came from the Ray Tracing News (April 6, 1988 - Volume 1, Number 6) by Goldsmith and Salmon in their May '87 paper in IEEE Computer Graphics and Application. The basic idea is to use a heuristic function to choose the best way of inserting successive object into the HBV tree by calculating the increase in area. Interested reader can visit the Ray Tracing News Web Page RTNews for further information. Below we will demonstrate the forming of the HBV tree by successively inserting a spiral of (84) spheres:

Stage 1

Stage 2

Stage 3

Stage 4

Stage 5

Stage 6

The following picture shows the Octree representation of the spiral of spheres:
Here is the ray tracing result of the spiral of spheres:

Primitive Objects: Square, Ellipsoid, Elliptical Cylinder, Elliptical Cone, Elliptical Paraboloid and Elliptical Hyperboloid

We try to solve the general second order conic equation by setting up the general matrix equation. This has the benefit when solving the intersection points of a transformed conic simply by multiplying the inverse of the transformation matrix. Here are some of the ray tracing results: Here we can see the sphere is on top of the hyperboloid and there is a paraboloid intersecting with the hyperboloid as well. The ellipsoid can be seen near the bottom of the hyperboloid. Notice that the general conic is infinite, hence in order to calculate the intersection of a truncated transformed conic, we must first map the global coordinates back to the local coordinates and check for the condition. Also the user is able to define any transformation i.e. translation and rotation of the general conic. This option is also included in the tsd file format.

CSG Boolean Operation: Union, Intersection and Difference

This operator is applied to any two kinds of primitive objects and produce the resuling set operation on it. The idea is very simple for ray tracing, assume we have a sorted list of the intersection points for object1 and a sorted list of the intersection points for object2, we would like to reorder the combined list and changing the flag of the surface, i.e. either entering the resulting object or exiting the result object. The following pictures show the boolean operators performed on a purple ellipsoid and a red sphere.

Union

Intersection

Difference

Here we can have sphere \ ellipsoid and ellipsoid \ sphere, notice that after the set operation, some of the hidden objects are revealed, as shown in the diagram.

Antialiasing schemes: supersampling, adaptative sampling, and stochastic sampling

There are two basic appoaches to minimize the aliasing problem: supersampling and adaptative sampling.

Supersampling uses more than one sample per pixel. However, since the subsamples are regularly spaced, it alleviates but does not eliminate aliasing.

Adaptative sampling traces additional rays between previously traced rays if there is high contrast between them.

A more sophisticated approach is stochastic sampling, which samples the image at nonuniformly spaced locations. In this case, aliasing is replaced by noise, what makes the images look better, since noise is an artefact that the human visual system tolerates well.

By using stochastic sampling, we implemnt distributed ray tracing, which allows the simulation of fuzzy phenoma, such as depth of field, penumbras, gloss, translucency, and motion blur.

Here we have the same image processed without antialiasing and with adaptative stochastic antialiasing:

Finer control of the camera: Depth of Field, Focusing and Aperature control

Here we have the same image processed using different camera focal length. This produces depth of field.

Depth of Field Examples


Finally here's a Tic-Tac-Toe movie to enjoy Tic-TacToe Movie