Project: 3D Primitives
Basic Raytracing and Primitives
The basic ingredients we need for our raytracer are:
- A representation of a scene (collection of 3D objects)
- The ability to shoot rays into the scene
- A way to show the result
Fortunately, the framework already provides a way to represent scenes (and even loads them from json files), so your first task will be to shoot rays into the scene and show the result. The only two files you need to change for this task are raytracer.pde and Primitives.pde.
Start in raytracer.pde. The method getColor(int x, int y) should return the color placed at the pixel x, y of the result image. The variables w and h tell you the desired width and height of the resulting image. For now, let us assume a square image, a field of view of 90 degrees in both directions, and a camera location that is fixed at (0, 0, 0), and looking in direction (0, 1, 0) (which are also the default values if not specified differently in the input file). To shoot a ray, you can place a virtual “raster” with size equal to w times h a number of units away from the origin down the y-axis. The distance of this raster from the origin determines the field of view angle: If you place the raster centered on the y-axis, in w/2 units of distance, the angle to the left edge will be determined by a right triangle: The distance down the y-axis is (as we just set) w/2. The distance from the center to the left edge is, as the raster is centered, also w/2, leading to an angle of 45 degrees. By the same argument, the angle to the right edge is also 45 degrees, leading to a horizontal field of view of 90 degrees, as desired. You can verify that the same holds for the vertical field of view (if the image is square). How do we get rays from this? If you can determine the position of each of the cells in the raster, you can create a vector from the camera position to the cell (hint: for now, the camera is at (0,0,0), so the position is already the vector you need), and then you normalize it, and that’s your ray direction.
The second step getColor needs to do is take this ray you just created and shoot it into the scene. The Scene object has a root, which represents the objects present in the scene, and this root has an intersect method, which takes a ray and returns an ArrayList<RayHit>, so that is what you will need to call for this step.
Finally, once you have the ArrayList of RayHits, this will tell you what your ray, well, hit in the scene. Of course, it may be nothing (an empty list), then getColor should just return the background color of the scene. However, if the ray hits something, the first RayHit object in the list will tell you what you hit. You could use the material contained in this RayHit to determine which color to return, but an easier way is to use the LightingModel contained in the Scene: To determine the color, you pass the RayHit, the Scene and the position of the viewer (i.e. camera, in our case (0,0,0) so far) to its getColor-method, and this will give you the color to return.
However, so far you will not be able to see anything, because there is no code that would detect if an object is hit or not. To get your first raytraced scene, you will therefore also need to implement the intersect-method of the primitives that occur in the scene. This intersect-method always gets a Ray and returns an ArrayList<RayHit>, where the RayHits that are returned should be ordered in ascending distance from the camera (and only hits in front of the camera should be returned). Note that RayHits represent when a ray enters or leaves a primitive (this will become important for the next milestone; for now only the first hit is used anyway, but it will make things easier in the future if you already return entry and exit-hits). Note: Make sure that the ray direction is normalized, or the intersection calculations will be wrong!
This is also the perfect time to allow placing the camera at an arbitrary position. This should only involve changing the origin of the ray in your Raytracer’s getColor-method. An arbitrary viewing direction is slightly trickier, though.
Ray Intersections
We assume that we have a ray y with origin o and (normalized!) direction d. Each point on the ray is then associated with a parameter t, which represents the distance of that point from the origin (with a negative value for t if the point is in the opposite direction as d):
The result of the intersect-method is a RayHit object:
class RayHit
{
float t;
PVector location;
PVector normal;
boolean entry;
Material material;
float u, v;
}
The value t is exactly the t from the equation above, which is the distance of the hit from the origin of the ray. location represents where the ray hits the surface of the object (this is, of course, redundant, as it could be calculated using t and the ray, but calculating it once and storing it is beneficial for performance). The normal vector is a vector that points away from the surface (in normal/orthogonal direction), which is important for lighting. entry is true if the hit represents the ray entering the object, otherwise it is false (i.e. when the ray leaves the object again). Finally, the material is just a reference to the material of the object that was hit. You can ignore u and v for now (or set them to 0), they are only relevant for textures (which we will address in milestone 4).
From this definition we can see that we need to calculate two main values: t, which tells us how far away from the origin we hit the object (and which then also gives us location), and normal, which tells us the orientation of the surface at the impact point.
Spheres
To determine the intersection of a ray with a sphere, first we calculate the projection of the vector from the origin of the ray o to the sphere center c onto the ray:
\[t_p = (c - o) \cdot \vec{d}\]This value tells us where the ray gets closest to the sphere center. To get the actual point p on the ray that is closest to the center of the sphere, we calculate:
\[p = o + t_p \cdot \vec{d}\]Since p is the closest point on the ray to the center of the sphere, the ray hits the sphere if the distance of p and c is less than its radius. To calculate the actual impact points, we need to adjust our t-value. We have a right triangle, where the longest side is the radius r, one leg is the distance from p to c (let’s call it x), and the other leg tells us how much closer (or further away) from the origin the impact point is along the ray.
We calculate the t-values for the two impact points as:
Recall: A t-value that is less than 0 means that a point is behind the origin on the ray, and we can therefore discard it. The lower of the two t-values determines the entry, the higher the exit point (if one t-value is negative and the other one is not, we started inside the sphere). With the t-value we also get the actual impact location.
The second part we need to determine is the normal-vector at the impact point. For a sphere this is straightforward: The normal vector points from the center of the sphere to the impact location. You just have to make sure to normalize this vector.
Planes
A plane is given as an arbitrary point p on the plane and a normal vector n. To determine where a ray hits a plane, we calculate t as:
Note: If the dot product $\vec{d} \cdot \vec{n}$ is 0 this means that d and n are orthogonal, i.e. the ray will never hit the sphere. Otherwise, you can calculate t as given above. If t is negative, the ray is shot away from the plane, otherwise you can calculate the impact location as usual. The normal vector, is just the normal vector of the plane.
The only missing piece is whether the hit is an entry or exit, which depends on which side of the plane the ray started on. To determine this, you can use the dot product $\vec{d}\cdot\vec{n}$ which you calculated earlier: If this dot product is negative, the normal vector and the ray direction point in opposite directions. This means, if the ray hits the plane, it must have started “in front of” the plane, i.e. the hit is an entry. Otherwise, it is an exit (You may be wondering what difference this makes. For now, it doesn’t, but later, in milestone 2, we want to compute intersections of shapes, and for that it will be relevant).
Triangles
To compute the intersection of a ray with a triangle, first calculate if the ray intersects the plane the triangle lies in. You can compute a normal vector for the triangle using the cross product: $(c-b)\times (a-b)$ (assuming the vertices are given in counterclockwise order!). For the plane-ray-intersection any of the three vertices will work as a point on the plane.
You can then determine if the impact point p is inside the triangle using either of the methods discussed in class, but barycentric coordinates will be more advantageous later in milestone 4:
ComputeUV(a, b, c, p)
e = b - a
g' = c - a
d = p - a
denom = e.e * g'.g' - e.g' * g'.e
u = (g'.g' * d.e - e.g' * d.g')/denom
v = (e.e * d.g' - e.g' * d.e)/denom
return (u,v)
PointInTriangle(a,b,c,p)
u,v = ComputeUV(a,b,c,p)
return (u >= 0) and (v >= 0) and u+v <= 1
If this check is positive, you again return the one impact point as an entry point if the ray started in front of the triangle (the direction the normal vector is pointing to), or as an exit point otherwise.
Cylinders (optional)
For a cylinder with radius r that is centered at the origin, and (for now) infinite in height, we compute t:
This will give us the impact locations as before, with the smaller value being the entry and the larger value the exit (make sure to check if t is greater than 0 to exclude impacts behind the origin of the ray). The normal vector is given as: The z-direction is always 0, and the x- and y-directions point from the z-axis to the impact location. You can just use the x- and y-coordinates of the impact location, with a z-value of 0, and normalize the resulting vector.
For a finite cylinder, we need to perform some additional checks: If the z-coordinate of an impact location is below 0 or above the height, we do not hit the cylinder side. However, in this case we may still hit the cylinder in the top or bottom surfaces. To address this, calculate the intersection of the ray with the plane that is at the top or bottom of the cylinder, and determine if the impact point is inside a circle with the radius of the cylinder.
Note: As this will only give you cylinders at the origin, this will make testing a bit challenging (the camera will always be inside the cylinder). But note that the formulas all included the origin of the ray o, and moving the camera just involves selecting a different origin point. It is likely very helpful to better see the cylinder if you use the camera-value from the scene description instead of the default (0,0,0) that we used so far. Note that rotating the camera is a bit more challenging, and is described elsewhere. Also note that milestone 2 will allow you to move (and rotate!) the cylinder, giving you even more freedom in testing this primitive.
Other Quadrics (optional)
The equation for the cylinder above was derived from the cylinder equation:
\[x^2 + y^2 - 1 = 0\]We take our ray $r(t) = \vec{o} + t \vec{d}$ and solve for t:
\[(o_x + t\cdot d_x)^2 + (o_y + t \cdot d_y)^2 - 1= 0\\\\ o_x^2 + 2 o_x d_x t + d_x^2 t^2 + o_y^2 + 2 o_y d_y t + d_y^2 t^2 - 1 = 0\\\\ t^2\cdot(d_x^2 + d_y^2) + t\cdot(2o_x d_x + 2 o_y d_y) + (o_x^2 + o_y^2 - 1) = 0\\\\ t^2\cdot a + t\cdot b + c = 0\\\\ t = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\]In class we also did the same for the (double) cone, which has the equation:
\[x^2 + y^2 - z^2 = 0\]The derivation is the same, and you end up with another quadratic equation for $t$, but the coefficients $a$, $b$ and $c$ will be different.
Other quadrics include the paraboloid:
\[x^2 + y^2 - z = 0\]The hyperboloid of one sheet:
\[x^2 + y^2 - z^2 - 1 = 0\]The hyperboloid of two sheets:
\[x^2 + y^2 - z^2 + 1 = 0\]You can derive quadratic equations for $t$ in the same way. Note: Once you have the quadratic equations, solving them and determining ray impact points, etc. are all the same. If you choose to implement all quadrics it may be useful to declare a common base class that does all of this, and the derived classes just differ in how they obtain $a, b$ and $c$ for the quadratic equation.
What about the normal vectors? Interestingly, these are very easy to determine: The normal vector at the impact point consists of the partial derivatives of the quadric equation wrt. to $x, y$ and $z$. For example, for the paraboloid, the normal vector at impact point $(x,y,z)$ is $(\frac{\partial (x^2 + y^2 - z)}{\partial x}, \frac{\partial (x^2 + y^2 - z)}{\partial y}, \frac{\partial (x^2 + y^2 - z)}{\partial z}) = (2x, 2y, -1)$ (Recall: a partial derivative will ignore any terms that do not contain the variable you calculate the derivative for). Important: Normalize this vector before you actually use it as a normal vector. Note that the sphere is also a quadric with the equation $x^2 + y^2 + z^2 - 1 = 0$, and if we determine its normal vector we will get $(2x, 2y, 2z)$, which, when normalized, is exactly $(x,y,z)$, i.e. the vector point from the center to the impact point, as it should be (this does, of course, not prove the correctness in the general case, but it is a good validation step nevertheless).