Started with an implementation of Bresenham's algorithm that ensures that the computation can be made effective by reducing the computation to bit manipulation using integers. And then continuing on Xiaolin Wu's line algorithm to increase the quality of the output.

Sampled triangle coverage by splitting each triangle into two triangles with a common horizontal base. In this algorithm, the navigation occurs along the lines contained in the triangles which increases the efficiency of the algorithm.
‍
Furthermore, extended the rasterizer to anti-alias triangle edges via supersampling and averaging the sample values to smooth out the pixels shown in the images. In response to the user changing the screen sampling rate, the triangle edges become noticeably smoother with larger sample rates. The implementation is using a sample buffer vector to store each pixel's color components and then resample the supersampled results buffer (average their colors together) to obtain sample values for each pixel.

Implemented Simple Alpha Blending which is a method of displaying transparent elements in the SVG specification. This tasks focuses on pre-computed alpha that the formula for computation are based on the current value on the screen and the incoming value, creating a blend between the two using the alpha value(weight) specified.

Mapped a texture on a surface. Given location (x,y), the texel(texture coordinate) is obtained by normalizing the given coordinates first and then mapping in the texture dimensions. For each covered sample, the color of the image at the specified sample location would be computed using Bilinear Filtering of the input texture which would cause anti-aliasing.
‍
Next, adding Trilinear Filtering to improve the anti-aliasing. My implementation first is generating mipmaps (Minification and Magnification) of desired resolution which are stored in a data structure. Based on the dimension of the texture, we computed the appropriate level at which to sample from the mip-hierarchy. As image elements shrink on screen, to avoid aliasing the rasterizer should sample from increasingly high (increasing pre-filtered) levels of the hierarchy. Finally, the values at any given pixel are interpolated by trilinear interpolation. That means we sampled more than one pixel at any given location and then average the value of all the locations to create smoother images,

Implemented three types of bevels: Vertex Bevel, Edge Bevel, and Face Bevel. The bevel action creates a new copy of the selected element that is inset and offset from the original element. Clicking and dragging on an element will perform a bevel; the horizontal motion of the cursor controls the amount by which the new element shrinks or expands relative to the original element, and the vertical motion of the cursor controls the amount by which the new element is offset from the original element.

Implemented a variety of commands used to alter the connectivity of the mesh (for instance, splitting or collapsing edges). These commands are applied by selecting a mesh element (in any mode) and pressing the appropriate key, as listed below. Local mesh editing operations include:
- Edge Flip: Rotates the edge in the anti-clockwise direction by one vertex.
- Edge Split: Split edge at its midpoint, and the new vertex is connected to the two opposite vertices.
- Erase Vertex: Replace a vertex together with all incident edges and faces with a single face.
- Erase Edge: Replace edge with the union of the faces containing it, producing a new face.
- Edge Collapse: Replace edge with a single vertex. This vertex is connected by edges to all vertices previously connected to either endpoint of e. Moreover, if either of the polygons containing e was a triangle, it will be replaced by an edge.
- Face Collapse: Replace face with a single vertex. All edges previously connected to vertices of face are now connected directly to the vertex.
All the operations consider the edge case of selecting the boundary vertex, edge, of face.

Implemented three schemes of geometry subdivision which upsample the low-resolution polygon mesh for display and simulation:
- Linear Subdivision: Each polygon in the selected mesh is split into quadrilaterals by inserting a vertex at the midpoint and connecting it to the midpoint of all edges. New vertices are placed at the average of old vertices and old vertices remain where they were. However, it will  results in a mesh that is purely quad.
- Catmull Clark Subdivision: Just as with linear subdivision, each polygon is split into quadrilaterals, but this time the vertex positions are updated according to the Catmull-Clark subdivision rules, ultimately generating a nice rounded surface.
- Loop Subdivision: Need to operate Triangulation first and then each triangle is split into four by connecting the edge midpoints. Vertex positions are updated according to the Loop subdivision rules.

The mesh is resampled so that triangles all have roughly the same size and shape, and vertex valence is close to regular (i.e., about six edges incident on every vertex). The algorithm to be implemented is based on the paper Botsch and Kobbelt, “A Remeshing Approach to Multiresolution Modeling” (Section 4), and can be summarized in just a few simple steps:
1. If an edge is too long, split it.
2. If an edge is too short, collapse it.
3. If flipping an edge improves the degree of neighboring vertices, flip it.
4. Move vertices toward the average of their neighbors.
Repeating this simple process several times typically produces a mesh with fairly uniform triangle areas, angles, and vertex degrees. However, each of the steps deserves slightly more explanation.

The number of triangles in the mesh is reduced by a factor of about four, aiming to preserve the appearance of the original mesh as closely as possible. The simplification method simplifies a given triangle mesh by applying quadric error simplification, was originally developed by Michael Garland and Paul Heckbert, in their paper Surface Simplification Using Quadric Error Metrics.

Randomly generates uniformly distributed rays from the camera. Each ray can be expressed in the form: P = o + t * d, where o is the origin, t is a parameter to reach point P, and d is the direction. The program transforms the ray from a point in the image plane into the world space through a matrix multiplication. For each ray, detects the first intersection with a primitive object including triangles (using Möller-Trumbore algorithm) and spheres in the scene.

In order to accelerate rendering, implemented the bounding volume hierarchy (BVH) by spatially partitioning primitive objects into bounding boxes. Instead of ray tracing each individual primitive, this acceleration structure allows us to test for ray intersection against groups of primitives (axis-aligned planes).

The BVH algorithm is defined recursively, and takes in a vector of primitives and a max leaf size. When the node is a leaf, we simply return that bounding box and its list of primitives; otherwise, we split along the axis of the lowest Surface Area Heuristic, which is found by comparing x, y, and z axis values. Then, we partition the primitives into two vectors based on which axis the primitive centroids are on. With these left and right vectors, we can recursively call the construction algorithm, setting nodes accordingly.

Implemented accurate shadows according to light(hemisphere light, direction light, spot light, and point light) in the scene. The algorithm is checking whether a ray originating from the hit point, and traveling towards the light source (direction to light) hits any scene geometry before reaching the light.

Implemented Monte Carlo Rendering that considering materials BSDF and the complicated light paths, bouncing off many surfaces before eventually reaching the camera. Simulating this multi-bounce light is referred to as indirect illumination, and it is critical to producing realistic images, especially when specular surfaces are present.

For the BSDF, implemented Lambertian for diffuse reflections, Mirror for perfect specular reflection, and Glass for both reflecting light and transmit light. We use Snell’s Law and Schlick’s approximation to compute a transmittance BSDF in the Glass.

For the Ray Tracing, simulated multiple bounces using the Russian Roulette algorithm in order to avoid spending time evaluating function for samples that make a small contribution to the final results. The structure is:
(1) Randomly select a new ray direction
(2) Potentially terminate the path (using Russian Roulette)
(3) Recursively trace the ray to evaluate weighted reflectance contribution due to light from this direction.

Simulated the effects of de-focus blur and bokeh found in real cameras by modifying the generated rays from the camera according to member parameters - aperture and focal distance. Focal distance represents the distance between the camera aperture and the plane that is perfectly in focus. Setting aperture could randomly choose the ray origin from an square centered at the origin and facing the camera direction. Now it’s as if the same image was taken from slightly off origin. This simulates real cameras with non-pinhole apertures: the final photo is equivalent to averaging images taken by pinhole cameras placed at every point in the aperture.

Implemented an infinite environment light, a light that supplies incident radiance (really, the light intensity dPhi/dOmega) from all directions on the sphere. Rather than using a predefined collection of explicit lights, an environment light is a capture of the actual incoming light from some real-world scene; rendering using environment lighting can be quite striking.

Furthermore, implemented an importance sampling scheme for environment lights to sampling directions towards the directions for which incoming radiance is the greatest. In the real world, most of the energy provided by an environment light source is concentrated in the directions toward bright light sources. For environment lights with large variation in incoming light intensities, good importance sampling will significantly improve the quality of renderings.

Implemented the function allow users to make simple animations by translating, rotating, or scaling the mesh in the scene. I implemented Cubic Hermite Curve over the unit interval first, which evaluates a spline defined over the time interval  given a pair of endpoints and tangents at endpoints. And then use this method to evaluates a general Catmull-Romspline at the specified time in a sequence of points (called “knots”).

Implemented these basic kinematics to allow user to define skeletons, set their positions at a collection of keyframes, and watch the skeleton smoothly interpolate the motion. A skeleton can be posed by selecting a joint and changing its pose i.e., rotating the joint.

In this project, I implemented a Capsule-Radius Linear Blend Skin method, which only moves vertices with a joint if they lie in the joint’s radius. This method could link the skeleton to the mesh in order to get the mesh to follow the movements of the skeleton

Implemented Inverse Kinematics, which will move the joints around in order to reach a target point. In this task, I implemented an iterative method called gradient descent in order to find the minimum of a function, more specifically, using a technique called Jacobian Transpose to update the angles along a single axis. And then extended it to 3 dimensions and support multi-target IK, which allows users to create a series of joints and get a particular joint to move to the desired final position users have selected.

Implemented a collection of non-interacting, physics-simulated, spherical particles that interact with the rest of the scene.I n this task, I use the simple forward Euler which not concerning with stability or energy conservation for our particle system. Forward Euler simply steps our position forward by our velocity, and then velocity by our acceleration.

Next, I used ray-tracing capabilities to find collisions along particles’ paths. If the ray intersects with the scene, computing when the particle would experience a collision. When finding a collision, assume all particles collide elastically - that is, the magnitude of their velocity should be the same before and after the collision, and its direction should be reflected about the normal of the collision surface. Repeated the ray-casting procedure(if the particle collided with the scene again?) in a loop until have used up the entire time-step.