Draw a fairly realistic looking sphere using ray tracing and Newton method. Ray tracing is a simple yet powerful method to render complex 3D images...

Draw a fairly realistic looking sphere using ray tracing and Newton method. Ray tracing is a simple yet powerful method to render complex 3D images and animations(wiki link). Pixar used ray tracing for the movie Cars(more info) to mimic shininess and reflections of real cars.

What is Ray Tracing? (click to view)

Imagine a 3D scene composed of a group of objects and a light source. A viewer wishes to view this scene from a certain angle. In ray tracing, the principle is to follow a ray of light as it starts from the light source, bounces around the scene and reaches the eye of the viewer. We need to draw the scene on a computer screen from the viewer's perspective. We will place a virtual screen between the viewer and the scene as shown in the figure. As the ray intersects a pixel of the screen before reaching the eye, that pixel acquires the color of the ray. Once we account for all such rays, we will have the complete scene drawn in terms of colored pixels.

In practice, we take a slightly different approach. As there are a large number of rays originating from the light source which will never reach the eye, it will be a waste of computation to track such rays. So we backtrace the rays. We track a ray starting from the eye and after it intersects the screen we follow it until it intersects an object. From the point of intersection , we follow a reflected ray. If the reflected ray reaches the light source (without being intercepted) then that point is visible to the viewer. A pixel on the screen takes the color of that point.

Tracing a Sphere (click to view)

To further simplify our problem we use orthographic projection rather than perspective projection. In orthographic projection, we trace one ray for each pixel with the pixel being the starting point of a ray. All the rays will be parallel, moving in a fixed direction say d⃗.

In this discussion, we will indicate points in 3D space in boldface like this p and vectors in space as v⃗. Let p be the coordinates of a pixel in 3D space. In this homework problem, the view plane will be the z=0 plane and our virtual screen will be a square with coordinates in the range [−1,−1,0]×[1,1,0]. The parametric equation for each ray is given by x=p+td⃗ (where t is a scalar). As t increases, the ray is traced farther out into space.

For each pixel we will follow the ray until it hits the sphere. The center of the sphere is given by c∈R^3 and its radius is r. The equation of the sphere is ‖x−c‖22=r2.

To find the point of intersection we can substitute equation of ray into the equation of the sphere. First, consider representing the sphere using the implicit function s(x)=‖x−c‖22=r2. This function returns 0 when x is on the surface of the sphere. To evaluate if a point on a ray is on the surface for the sphere, we set x=p+td⃗. The implicit function is then a function of the parameter t and an intersection occurs when f(t)=0. We will use Newton's method to solve for the zero of f(t).

After we get the point of intersection, we can calculate how the light source illuminates the point, which will give the color at the point. That will in turn be the color of the pixel from which we started tracing the ray. We make several more simplifying assumptions for this problem. We have assumed a fixed light source at infinity. We do not trace a reflected ray from the intersection point, we simply shade using the surface normal and an equation approximating the reflectance of a rough surface that reflects light diffusely...there's no shininess. You will be given a function which takes as input a point of intersection and outputs the color. This is a version of the Blinn-Phong shading model. If you are curious, the shading model is explained, with code, at the link.

What is Given? (click to view)

You are given ray direction in a 1D array ray_direction, center of the sphere in center , radius in radius and size of the screen in pixels. pixels is a 2-tuple of kind (H,W)

where H

is the height of the screen in number of pixels and W

is the width of the screen.

You are also given following helper functions:

pixel2window(pixel) which takes input pixel index(pass it as a list) and returns the 3D spatial coordinates of the pixel. This maps the (i,j) integer index of a pixel to a point in our virtual 3D space on the z=0
plane. This point in the 3D space will be the starting point of a ray.
pixel_color(x) which takes input a point on the sphere and gives back it's color value. To simplify things, this function uses greyscale rather than full color.

Write code following the steps given below to draw a sphere:

Python function which takes a value and a source point p and direction d⃗ for a ray. The function should compute the point along the ray corresponding to t and return the value f(t) given by the implicit function for the sphere at that point.
Python function which gives the derivative of f(t) at t.
function named newton_method. It should take four inputs: a guess value for t, name of function f, name of derivative function, a list of extra arguments which are needed in f and the derivative function. It should return the next guess for t after one iteration of the method.
an array traced_sphere of pixels of size (H,W). You will draw the sphere on this array by determining color of each pixel. For each pixel, construct a ray and find the first intersection point (if any) between the ray and sphere. To construct the ray, convert the (i,j) index of the pixel to a point 3D space using pixel2window() and use ray_direction as the direction of the ray. Using a starting guess t0=0, do Newton interations to get the point of intersection of the ray and the sphere. If the value of f(t) is below 10−8, we consider the method to have converged and so found an intersection. After the point of intersection is found, use pixel_color to get color value for the pixel. This value will be in range [0,1] and should be stored in traced_sphere. If the method does not converge, there is no intesection and the pixel value should be 0, which will be black.
Output an array two_step_t of size (H,W). two_step_t[i,j] should be the value of t after two steps of newton iteration for pixel with index (i,j). This is used by the autograder to verify that newton's iteration is implemented correctly and give partial credit.
Use function matplotlib.pyplot.imshow(traced_sphere,cmap="gray") to plot the pixels.

NOTE:

Rememeber to stop the Newton iteration if the value of f(t) is below tolerance of 10−8 or 10 iterations have been reached.

INPUT:

ray_direction: the vector indicating the direction of the rays in 3D space, given as a numpy array
center : the point in 3D space corresponding to the sphere center, given as a numpy array
radius: radius of the sphere.
pixels: a tuple of screen size (H,W).
pixel2window(pixel), pixel_color(x): Python functions.

OUTPUT:

traced_sphere: 2D numpy array of pixels giving image of sphere.
two_step_t: 2D numpy array of t values.
plot of the traced sphere.

Problem set up code:

import