2022 November 16,
You are not responsible for knowing this material in any project work or exam. I put it here, just to give you a glimpse of graphics topics that we didn't have time to explore.
Although we started in two dimensions for the sake of clarity, this course is really about 3D graphics. We can use our triangle-rasterizing 3D engine to do 2D graphics by restricting our meshes to a plane. However, there are many techniques specific to 2D graphics that we've ignored entirely.
One example is splines, which you might have encountered in drawing programs such as Adobe's Illustrator. Another example is 2D scene graphs, which are used in graphical user interfaces. A related concept is the nested bounding rectangles used in TeX's page-layout algorithm.
A huge topic in 2D graphics is image processing. It connects to mathematical topics such as Fourier analysis, statistical topics such as time series, and AI topics such as computer vision. Maybe someday Carleton will offer an image processing course.
In our software triangle rasterization engine, we implemented nearest-neighbor texture filtering, linear texture filtering, and perspective-corrected interpolation. However, our textures still looked pretty poor. One reason is that good textures require careful artistic attention, which is outside the scope of this course. But there are also improved computational techniques, which we could have studied.
One such technique is mipmapping, in which the texture is pre-filtered to several sizes. At run time, the size that best matches the screen size is automatically selected, so that minification and magnification are kept close to 1. The results are prettier than ours, with little performance penalty. Another technique is anisotropic filtering, which incorporates perspective effects into the texture filtering itself. More generally, texture filtering is affected by large swathes of the theory of image processing.
Our mesh data structure is quite simple: a list of vertices and a list of triangles, with each triangle being three indices into the vertex list. However, many graphics applications endow meshes with more information. For example, each triangle might store three more integers: the indices of its three neighbor triangles. With this kind of topological (connectivity) information, a graphical mesh-editing application might let the user pull on parts of the mesh, adjusting many contiguous triangles at once. If the mesh is a landscape, and we want AIs to traverse that landscape, then topological information helps their path-finding algorithms.
Someday this course will include a loader for a popular mesh file format such as OBJ or PLY. Then we'll be able to load better art more easily.
We have implemented only rudimentary scene graphs. More sophisticated scene graphs can have various kinds of nodes. For example, a node can implement level of detail (LoD). An LoD node has multiple children, all representing the same subscene at differing levels of detail. When the LoD node is told to render, it passes the message onto just one, or even none, of its children according to some criterion. For example, if the subscene is off-screen, it might be pruned entirely; but if it casts shadows onto the screen, then a low-detail version of it might be rendered in the first shadow-mapping pass.
Physics engines, which handle tasks such as gravity and collisions, often introduce their own graphs to model the relationships among bodies. For example, in the Open Dynamics Engine, bodies can be connected by various kinds of joints: ball, hinge, etc. Joints are also made dynamically, whenever bodies collide or slide against each other. Here is a video demonstrating some of ODE's capabilities.
In earlier years, but not in this term, we have incorporated translucent bodies into our ray tracer. As a ray enters or leaves a body, it bends according to Snell's law of refraction. If the body is not perfectly transparent, then it dims the ray as the ray passes through it. This dimming can even affect shadow rays.
It might seem that simple primitives such as spheres, cylinders, and planes are merely a warm-up for meshes. But actually a lot can be done with the simple primitives. The technique of constructive solid geometry lets us express rather complicated shapes as intersections, unions, and complements of simpler shapes. And ray tracing these intersections, unions, and complements turns out to be surprisingly fast and easy.
Ray tracing a mesh is slow, because you have to intersect the ray with each triangle. So a big part of ray tracing is designing data structures that speed up these intersection queries. Essentially, you enclose your meshes in simple primitives — spheres, axis-aligned boxes, etc. — for which intersections are fast. When testing intersection with a mesh, you first test intersection with the enclosing primitive; if there is no intersection, then you skip the mesh entirely. In fact, you probably want a hierarchy of enclosing primitives. So it ends up looking like a scene graph with LoD pruning.
Ray tracing is highly parallelizable (over the pixels). So another way to improve the speed of ray tracing is to make it multi-threaded. Some GPUs now provide ray-tracing functionality. In late 2018 and early 2019, video games started to take advantage of GPU ray tracing. My understanding is that they still generate most of their imagery using triangle rasterization, but they employ ray tracing in certain parts of each scene to produce superior lighting effects. Sometimes they have to compromise other aspects of performance or quality. For example, here is a detailed review of the graphics in Battlefield V; check out the aggressive LoD culling on the ground around 11:55 of that video.
As far as improving the quality goes, the obvious next step is distribution ray tracing. This technique lets us soften our images in various ways — anti-aliasing, soft shadows (penumbras), blurry reflections, etc. — so that they appear less harsh and more natural. Here's the basic idea. Wherever we would cast a single ray in basic ray tracing, we instead cast multiple rays sampled from some probability distribution. Then we average the results of those rays. This is slow.
In class we've mentioned textured light, shadow mapping, and mirror reflections off planar surfaces. In past years, the students implemented some of these techniques. This term we ran out of time.
More generally, there are various techniques of global illumination, which attempt to capture how light bounces around a scene. For example, the radiosity algorithm subdivides the scene into pieces, constructs a linear equation governing how much light is bouncing between each pair of pieces, and solves the resulting linear system. This method can compute diffuse inter-reflection, which is difficult even for ray tracing.
For people who don't want to stray far from the basic triangle rasterization algorithm, there are many tweaks to make the lighting a bit better. For example, ambient occlusion is the idea that fragments in crevices and corners should receive less ambient light than fragments that are more exposed in the scene.
Deferred shading is a rearrangement of the triangle rasterization algorithm. As far as I can tell, most contemporary high-end video games use variants of this algorithm. Adrian Courreges has detailed analyses of games such as Deus Ex: Human Revolution and the 2016 version of Doom.
Roughly speaking, there are two rendering passes. On the first pass, the scene is rendered into several off-screen framebuffers simultaneously — diffuse surface color, normal direction, etc. — to assemble all of the data that are eventually needed for lighting and other shading effects. On the second pass, the scene is not used at all. Instead, the framebuffers are combined, pixel by pixel, to produce the final image. This method can be faster than regular triangle rasterization when the lighting and shading calculations are complicated. It also allows for various screen-space image-processing techniques, such as screen-space ambient occlusion. One disadvantage of this method is the large amount of GPU memory required.
Anti-aliasing, bloom, depth of field, and motion blur are all techniques involving some kind of tactical blurring. Some of these are explored in the Deus Ex analysis linked above.
Blending and translucency in triangle rasterization? It depends on how the translucent bodies overlap on the screen. Try the painter's algorithm paired with careful scene design.
How does one make human figures that don't look like they're made of rigid bodies? How does one make a human arm that bends? Skeletal animation. That requires pretty significant modification of mesh geometry at run time. So maybe now is a good time to mention geometry shaders and tesselation shaders.
We have randomly generated landscapes. We could study procedural textures such as Perlin noise. We could study fractal landscapes, foliage, etc.
We haven't done much with user interface. How does the user pick an object out of a 3D scene with the mouse? How do we do it well, so that the user has a sense that they are manipulating virtual objects in a tactile way? That's really important for virtual reality.
Perhaps it's because I'm too lazy to make good textures, but non-realistic techniques such as cel shading (below left) really appeal to me. Also, my research uses 3D graphics for visualizing scientific data sets (below right), and textures are rarely involved.