Ray tracing is a method that is used by 3D animators, like at Pixar, to turn mathematical models of objects into images. Ray tracing produces images by running a simulation of a camera, a light, and an object. Normally light is emitted from a light, like our sun, it hits an object, anything you can see, bounces off the object, and hits the camera sensor. Simulating *all* rays of light from the sun is computationally expensive. So ray tracing simplifies the problem by running the simulation backwards to only simulate the rays that hit the camera sensor.

For each pixel in the image to be produced, a ray from the pixel through a focal point is created. The closest triangle that intersects with the ray is used to determine the color of the pixel. The color of the pixel is computed by using the orientation of the triangle relative to the direction light source.

To compute where a ray intersects with a triangle use the following equations:

\[\vec{r_d} = \vec{f} - \vec{r_o}\] \[m = (\vec{r_d} \times (\vec{v_3} - \vec{v_1})) \bullet (\vec{v_2} - \vec{v_1})\] \[b_1 = \frac{(\vec{r_o} - \vec{v_1}) \bullet (\vec{r_d} \times (\vec{v_3} - \vec{v_1}))}{m}\] \[b_2 = \frac{\vec{r_d} \bullet ((\vec{r_o} - \vec{v_1}) \times (\vec{v_2} - \vec{v_1}))}{m}\] \[t = \frac{(\vec{v_3} - \vec{v_1}) \bullet ((\vec{r_o} - \vec{v_1}) \times (\vec{v_2} - \vec{v_1}))}{m}\] \[\vec{p} = \vec{v_1} + b_1 (\vec{v_2} - \vec{v_1}) + b_2 (\vec{v_3} - \vec{v_1})\]

Where \(f\) is the focal point, \(\vec{r_d}\) and \(\vec{r_o}\) are the ray direction and origin, respectively, \(\vec{v_1}\), \(\vec{v_2}\), and \(\vec{v_3}\) are the vertices of the triangle, and \(p\) is the point where the ray intersects with the triangle’s plane. If any of the following are true, then the ray does not intersect with the triangle.

- \(m\) is 0
- \(b_1\) is less than 0
- \(b_1\) is greater than 1
- \(b_2\) is less than 0
- \(b_1 + b_2\) is greater than 1
- \(t\) is less than 0

The distance, \(d\), between the intersection point, \(p\), and the ray origin, \(r_o\) is the magnitude of the vector from the origin to the intersection point:

\[d = \lvert \vec{p} - \vec{r_o} \rvert\]

The color of light reflected off of a point on a triangle is computed with the following equation.

\[\vec{n} = (\vec{v_2} - \vec{v_1}) \times (\vec{v_3} - \vec{v_1})\] \[\vec{v} = \vec{l} - \vec{p}\] \[\vec{c_r} = (\hat{n} \bullet \hat{v} + a) \vec{c_o}\]

Where \(L\) is the location of the light source, \(a\) is the amount of ambient light in the scene (pick a value between 0 and 1 where values closer to 0 are better), \(\vec{c_o}\) is the color of the object (pick any rgb color you want), and \(\vec{c_r}\) is the color of the light reflected. Note that the reflected color may have rgb values outside of the range \([0, 255]\). If so, just clamp the rgb values to the correct range.

#### Details

Create a C++ program that uses ray tracing to create an image of an object. The program should read, via standard in, an obj file of the object to render and write, via standard out, a ppm file rendering of the object. To redirect a text file to standard input of a program use file redirection.

`$ ./ray_tracer < sphere.obj > sphere.ppm`

To detect the end of the obj file use the istream function `good`

.

`while (std::cin.good())`

See the Wikipedia page on obj files for more information on the obj file format. The program can assume that all faces have 3 vertices and can ignore all lines that are not vertex or face lines. The Free3D website has more complicated obj files that you can use once you have tested your program on very simple models first. Note, will likely need to move the camera sensor and focal point when rendering an obj file that you have downloaded. Look at the range of vertex values to get an idea of where to move them and use global constants to make moving the camera easy.

The camera sensor can be located anywhere in three dimensional space, but it is easiest if it aligns with coordinate system. For example, in the x, y plane so that all z values of pixels are identical. Likewise the focal point can be located anywhere, but should be between the camera sensor and the object or else no rays will hit the object.

The program must use a structure to represent 3D vectors with the following functions:

```
// returns the magnitude, or length, of the vector
double magnitude() const;
// makes the vector have a length of 1
void normalize();
// returns the sum of two vectors
Vector3d operator+(const Vector3d& lhs, const Vector3d& rhs);
// returns the difference of two vectors
Vector3d operator-(const Vector3d& lhs, const Vector3d& rhs);
// returns the product of a vector and a number
Vector3d operator*(const Vector3d& lhs, double rhs);
// returns the cross product of two vectors
Vector3d cross(const Vector3d& lhs, const Vector3d& rhs);
// returns the dot product of two vectors
double dot(const Vector3d& lhs, const Vector3d& rhs);
```

To compute the magnitude of a vector use the equation:

\[\lvert v \rvert = \sqrt{v_x^2 + v_y^2 + v_z^2}\]

To normalize a vector use the equation:

\[\hat{v} = \frac{v}{\lvert v \rvert}\]

To add two vectors use the equation:

\[v_1 + v_2 = (v_{1x} + v_{2x}, v_{1y} + v_{2y}, v_{1z} + v_{2z})\]

To subtract two vectors use the equation:

\[v_1 - v_2 = (v_{1x} - v_{2x}, v_{1y} - v_{2y}, v_{1z} - v_{2z})\]

To multiply a vector and a number use the equation:

\[v s = (v_{x} s, v_{y} s, v_{z} s)\]

To compute the cross product of two vectors use the equation:

\[v_1 \times v_2 = (c_x, c_y, c_z)\] \[c_x = v_{1y} v_{2z} - v_{1z} v_{2y}\] \[c_y = v_{1z} v_{2x} - v_{1x} v_{2z}\] \[c_z = v_{1x} v_{2y} - v_{1y} v_{2x}\]

To compute the dot product of two vectors use the equation:

\[v_1 \bullet v_2 = v_{1x} v_{2x} + v_{1y} v_{2y} + v_{1z} v_{2z}\]

### Extra Credit

Add shadows to the ray tracer. When calculating the reflected color, only use the reflected color if the intersection point is not in shadow. If it is in shadow, use the ambient light equation to compute the reflected light:

\[c_r = a \vec{c_o}\]

To test if a point is in shadow cast another ray from the intersection location to the light and test if the ray intersects with any triangles.

### Collaboration

You may collaborate with a partner on this assignment. If you do, both partners must work on the same computer and actively contribute to **every** line of code. Only one partner needs to submit code, but both partners names should be in the code.

### Grading

The project will be graded according to the following weights:

20% - Style, design, and documentation

20% - Test cases (and assertions)

10% - 3D Vector struct with all above functions in a separate file

10% - Reads an obj file into vector

10% - Tests whether a ray intersects with a triangle

10% - Computes the color of light reflected off of a triangle

20% - Renders an image of an obj file.

### Submission

Submit an h and cpp files containing your Vector3D structure and a cpp file containing your test code for the structure on the course Inquire page before class on Wenesday, February 28^{th}.

Submit a cpp file containing your final program and some cool images you created using it on the course Inquire page before class on Wednesday, March 21^{st}.