**Rays** [A Graphics Codex Programming Project](../projects/index.html) ![Figure [teaser]: Ray trace beautiful lighting...with 100 lines of equally beautiful code.](boxes.jpg border=1) *Prerequisites* - Complete the [Cubes](../cubes/index.html) project - Read in the [Graphics Codex](http://graphicscodex.com): - A Model of Light - Surface Geometry - A Camera Model - Ray Casting - Direct Illumination - Ray-Triangle Intersection - Ray-Sphere Intersection - Floating Point Introduction ============================================================================================ Photographs are produced in the real world by rays of light from emissive sources interacting with surfaces in the scene and being measured by a camera's sensor. We can create realistic images of virtual scenes by emulating that process. "Backward" ray tracing algorithms iterate over the light rays that entered a camera and trace them back along the negative direction of propagation to discover the surfaces, and eventually light sources, that gave rise to them. In this project, you'll implement a backwards ray tracer from scratch and then optimize it using multiple CPU threads. This is the core idea of how offline renderers for movies work. The results will be beautiful images produced by code that you've written yourself and a solid understanding of both the theory and implementation practice of ray casting. Educational Goals --------------------------------------------------------------------------------------------- - Map rendering theory to practice - Solve for analytic ray-primitive intersections - Design a ray casting algorithm framework - Gain experience with: - Numerical precision issues - Concurrent programming - Barrier synchronization - More complex C++ programming Rules for this Project --------------------------------------------------------------------------------------------- During this project, you are not permitted to invoke or look at the source code for any G3D ray intersection routine in either the API or the sample programs. This includes but is not limited to `G3D::TriTree::intersectRay`, `G3D::Triangle::intersect`, `G3D::Box::intersect`, and `G3D::Sphere::intersect`. You are not permitted to look at the implementation of `App::rayTrace` in the G3D `cpuRealTimeRayTrace` sample program or `RayTracer::L_direct` in the G3D `photonMap` sample. You _are_ permitted to look at all other code and design in those particular sample programs, and may find it helpful to do so. You are not permitted to look at the `G3D::PathTrace` source code in G3D. You may look at the `pathTrace` sample program to see how it configures the GUI. Specification ============================================================================================ Extend your solution to the [Meshes project](../cubes/index.html) or the [G3D starter project](https://casual-effects.com/g3d/G3D10/samples/starter/) to ray trace direct illumination with shadows for spheres, boxes, and indexed triangle meshes. 1. Make a user interface with the following controls: 1. Resolution dropdown box featuring at least 1x1, 320x200, and 640x400 options. 2. Check box for adding "fixed primitives" to the scene. 3. Check box for "multithreading" the ray tracing. 4. Integer number box for the number of "indirect" rays per pixel, between 0 and 2048. 5. Loading a G3D scene (already provided for you in `G3D::GApp` by the Scene Editor Window). 6. A "Render" button for launching rendering. 2. When the "Render" button is pressed, the program: 1. Immediately displays a waiting screen. 2. Renders an image as described below and then displays it in a new window with proper gamma encoding. 3. Prints the wall-clock rendering time to the debug console and also puts it in the image window title. The rendering time must exclude the time for posing the scene and constructing any data structures (e.g., `G3D::TriTree`). 3. Image rendering: 1. Obey the multithreading checkbox (`G3D::runConcurrently` can do this for you) 2. Cast one primary ray per pixel through the center of that pixel, from the `G3D::GApp::activeCamera`. 3. Use self-documenting types correctly in the implementation (e.g., `G3D::Radiance3`, `G3D::Power3`, `G3D::Point3`, etc.) 4. Abstract the ray tracing algorithm's implementation to make the radiometry clear and reusable. 5. Consider the scene to be all of the `G3D::Tri`s produced from the surfaces when posed, plus at least two hard-coded spheres of your choice when "fixed primitives" are selected in the GUI. 6. Use some non-zero radiance function that varies with ray direction for rays that miss the scene and "hit the sky." 7. Perform correct $\alpha$-testing on triangles (`G3D::Tri` has a helper method for this). 8. The illumination terms in the shading must be: 1. Emitted radiance. 2. An "ambient" incident radiance of $ L_\mathrm{ambient} = 0.05 $ W/(m^2 sr). 3. Single-scattered ("direct") illumination from omni ("point"), spot, and directional sources. - If the light is marked to cast shadows, perform a proper shadowing test. - Ignore the light if it is marked to not create direct illumination, then ignore it. - Spot lights must be correctly restricted to their cone (G3D can do this for you). 4. One additional scattering event of indirect radiance sampled from random directions about the normal. Recall that the reflected radiance at $X$ due to a single, unshadowed point light at $Y$ is given by: \begin{equation} \Lo(X, \wo) = \beta(X, Y) \cdot f_X(\wi, \wo) \cdot |\wi \cdot \n| \end{equation} where $\beta$ is the biradiance function of the light, $f_X$ is the bidirectional scattering distribution function of the surface at $X$, $\wi$ is the unit vector from $X$ towards $Y$, $\wo$ is the outgoing direction, and $\n$ is the normal to the surface at $X$. The indirect radiance term is one more iteration of the rendering equation's integral equation (for nontransmissive surfaces). The total indirect contribution from one indirect scattering event is therefore: \begin{equation} L_\mathrm{reflected~indirect}(X, \wo) = \int_{\mathbf{S}^2_+} \Li^1(X, \wi) \cdot f_X(\wi,\wo) \cdot |\wi \cdot \n| ~ d\wi \label{eqn:indirect} \end{equation} where $\Li^1$ is the "one bounce" (i.e., nonrecursive) incident light function.
![Figure [fig:spheres]: Perfect spheres and triangles](spheres.jpg height=140px border=1) ![Figure [fig:sponza]: Sponza with direct illumination](sponza.jpg height=140px border=1) ![Figure [fig:teapot]: Complex indirect lighting](teapot.jpg height=140px border=1) Report ============================================================================================ 1. Describe the mapping from the rendering algorithms in the _Graphics Codex_ and this document to your implementation. Ideally, this will be a copy of some documentation comments that you've already written. Note important design decisions, observations about the algorithms, and any "gotchas" that you encountered while turning the math into code. 1. Demonstrate correctness of your program by rendering with your ray tracer at 640x400 resolution (and saving the result to a lossless PNG file): 1. The "G3D Triangle" scene without indirect light. 2. The "G3D Cornell Box" scene without indirect light. 3. A scene containing your analytic spheres (not spheres constructed from triangles!) _and_ triangles. 4. The "G3D Cornell Box" scene with 2048 indirect light rays. 5. The "G3D Sponza" scene with no indirect light at 640x400 (_this will take quite a while_). *Report the time to render this image.* 6. Indirect and no-indirect images of an interesting scene of your own design for which there is a significant difference between the two versions. This need not be complex--simple colored boxes with appropriate lighting are sufficient. 1. Measure and graph the running time of your program with respect to the five major parameters. In each case, ensure that the _other_ parameters are sufficiently large that your tests have low variance and clear their startup overhead, but are small enough that you can complete the tests in a reasonable amount of time. A few cubes and a single light (the Cornell Box is modeled with six!) with multithreading enabled and indirect disabled at 256x256 is a good default for the parameters you aren't intentionally varying. 1. Number of cores (1 vs. [`G3D::System::numCores`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_system.html#a4acba57a7c4353b59622dd6225f8e509) when multithreading is enabled) 2. Number of triangles in the scene, e.g., 1, 10, 100, 1000, 10000 (_Tip: you can use a heightfield to easily vary the number of triangles in a scene_) 3. Number of pixels (e.g., 1, 64^2, 128^2, 256^2, 1024^2) 4. Number of lights (e.g., 1, 6, 20, 100) 5. Number of indirect rays (e.g., 0, 1, 10, 100, 1000, 2000) 1. Derive a theoretical asymptotic time bound for your renderer in terms of the above variables. Describe situations in which this does and does not provide a good model for the runtime (and why), referring to your results from the previous question. 1. Answer the following questions in no more than four sentences each. You may include diagrams and equations. 1. How would you derive an analytic intersection algorithm for a finite right cylinder? Do not actually do so. 2. How would compute the intersection with a surface for which there was no analytic intersection solution? For example, an arbitrary continuous height function $y(x, z)$. Sketch an algorithm, but do not attempt to refine it. 3. How do you think a binary tree could be leveraged to accelerate the ray intersection process? If you choose to research this (not required) before answering, be sure to cite the resources that you consult. 1. Evaluate your own work on this project as a grade (A+ through F) and one sentence each critiquing: your code style, workflow as represented by your journal, report writing quality, and the report depth and your confidence in its correctness. 1. Describe what you learned while working on this project. Distinguish software engineering, algorithmic, and mathematical skills. Include the reading and ideas that you had to implicitly work through even if not required. 1. How long did the project take you, from start to finish? Exclude time spent on the required reading and when the computer was rendering unattended. Distinguish required minimum time to complete the specification from polishing time. Reporting Time for Team Projects -------------------------------------------------------------------------------------------- When reporting time for team projects, report the time as observed by each team member separately. For example, if A and B are on a team and they work the following: - 2h A drafts the header file while B drafts the report - 4h A + B pair programming and debugging - 1h A brings code to MVP alone - 2h A debugs alone and renders a custom scene - 1h B polishes the report Then you'd report: - A: 6h MVP + 3h polish - B: 6h MVP + 1h polish Advice ============================================================================================ Workflow -------------------------------------------------------------------------------------------- ![Figure [fig:cornell]: The classic Cornell Box
rendering test.](cornell.jpg height=140px border=1) My implementation was 180 source lines of code, measured by counting semicolons in my `.cpp` and `.h` files. Only 100 lines of that were in the implementation of my `RayTracer` class. The rest were headers and GUI. If you didn't complete the [Meshes project](../meshes/index.html) (which is not a prerequisite for this project), look at the workflow planning table for it and consider creating at least an informal version for this project. You aren't required to document your plan in the report or journal for this project, but it is a good idea to at least sketch it. Write code for the full implementation before you try to debug. While debugging, it is a good idea to temporarilly disable parts of the program that you don't trust. But if you haven't written the whole program before debugging, then you have no basis for knowing which are the most important buts and allocating time accordingly. For example, a common _bad_ workflow on this project is to encounter shadow acne and spend a long time debugging it before even implementing shading or indirect light. If there's shadow acne, you know that is a really small bug in the code, and you can still tell if everything else is working. Keep going on the code. When you've completed everything and believe that the most significant bug is in the shadows, you can come back to it. All industry software ships with hundreds of bugs. The alternative is shipping years (probably decades) late. All research code has bugs as well--but nothing would ever get published if we tried to fix every small error. The key is making sure that those bugs aren't in the critical parts for the functioning of the application or for creating the results for research. In each case, all of the functionality must be present before bugs can be prioritized. Why should your educational project code be any different, or held to a higher standard than an operating system or scientific result? The programming work for this project is about evenly divided in four parts between user interface development, setting up the ray tracing loop and post-processing the image, the actual ray tracing, and the ray-primitive intersection routines. The ray tracing algorithm takes only a few lines to implement when designed well. It is the physics (and nominally, rendering) heart of the project, but the other parts are equally essential and deserve the same care. This is representative of most graphics projects. What you might think of as the "real" part of the project is simple and elegant...but only because it can rely on a solid framework. Allocate your time accordingly, and don't forget to budget the time you'll spend debugging, working with version control, documenting the project, and then producing the final report. Make the defaults for your program match what you're currently debugging. Don't waste time manually selecting your scene, resolution, and options every time that the program launches. Programmatically configure those so that it immediately runs in the configuration you're working with. Graphics programs perform a large number of computations compared to school projects in other areas of computer science. My laptop has a 2880x1800 screen. Rendering a 10k triangle scene with 10 lights and 100 indirect rays at that resolution using the algorithms from this project requires quadrillions of operations. Your program will take a very long time to produce results. This leads to two important workflow observations. You must: 1. Debug using small images and simple scenes, otherwise it will take minutes to see the result of each change and amplify your development time. 2. Anticipate the rendering time for your scalability tests, and plan to have the program running for hours to produce the final data for the graphs. Plan to grab a meal while your renderings are in progress and the computer is unattended, or have some other work on hand so that you don't waste time staring at the screen. If you're working with someone else on this project, I recommend pair programming the RayTracer header and implementation instead of dividing the work up between you. There aren't that many lines of code to write and errors can set you back for hours of debugging. So, it makes sense to have one person typing and two people looking at the same screen and working out the algorithms together. Because your code is in SVN, you can each easily check it out on separate computers and write the report in parallel or render final results twice as fast. Of course, the sum of all times is the resource cost to your team. You're burning your time resource twice as fast when pair programming, and it is only worthwhile if you can reduce later debugging time by getting the code (more) right the first time. You often can, but if you're pair programming something simple like the GUI or the experiment automation, consider dividing and conquering instead. G3D conveniently provides the completely empty "G3D Whiteroom" scene and the "G3D Triangle" scene with a single triangle. From completing the Cubes project, you know how to make your own scene files in many ways. You can generate them programmatically when performing the scalability experiments, and manually in text or using the drag-and-drop scene editor for debugging and creating visually interesting examples. The main bugs that I encountered in my initial implementation of this project were poorly chosen epsilon values and missing negations on directions. In every case, I was able to find these quickly through reducing to very simple test cases and then relying on breakpoints and assertions to question my assumptions about the code. For example, when the lighting disappeared after I added shadows, I single-stepped into my line-of-sight helper routine to discover why it always returned false. Almost all of the methods on the ray tracer can be implemented as an iteration structure and a call to a helper method. There are only three methods that do any work: 1. compute the scattered direct lighting ("shading") 2. intersect one triangle 3. intersect one sphere The first one is easy: iterate over the lights and multiply three values: the biradiance from the light, the value of the scattering distribution function, and the cosine of the angle of incidence (a dot product). So, there are only two hard methods to write in the entire project (once you've designed the ray tracer, which admittedly requires some thought). Fortunately, G3D comes with really nice versions of the intersection methods. "Wait!", you say: You aren't allowed to use those intersection methods..._in your eventual solution_. The rules of this project do not prohibit you from using G3D's intersectors while debugging (you just can't look at the implementation code). Bring up your program using the built-in intersection methods and render a Cornell Box. Then, replace the intersection methods with your own. When debugging the rest of the program you can trust the G3D intersectors, and when debugging your own intersectors, you can trust the rest of your program that was already debugged! Just be sure to remove these "illegal" calls before completing your project. Design -------------------------------------------------------------------------------------------- Here's the core of program design. Start with the highest-level method, the one that kicks off the call chain. For this program, that will be something like `RayTracer::traceImage`. Work solely in your header file at first. Think through and document what the method does (e.g., "iterates overall pixels calling `traceRay`"), and then write prototypes for the helper methods that will be invoked. As a rule of thumb, if your method's implementation is likely to take up more than 15 lines of code, it probably needs more helpers. When writing the helper methods, only concern yourself with their return values. Ignore their parameters. Continue this way down the call chain until you reach some method that does not call helpers. That method is either relatively simple to implement (just math, no data structure iteration) or just invokes some library function. At this point in the design, you can probably imagine what input you'll need for the "leaf" method in the call chain in order for it to provide the desired return value. For example, your `intersectTriangle` method probably needs to return a `shared_ptr`, so it had better take as an argument something that has a method to produce a `shared_ptr` or provide enough information to construct one. Keep working back up the call chain filling in arguments. You'll find yourself refering to the documentation a lot during this process. It is like plugging together adaptors: you have an X and need a Y, so find something that produces Y from X in the documentation. Style -------------------------------------------------------------------------------------------- Remember your basic C++ best practices. Use `const shared_ptr<...>&` for passing most shared pointers and local variables on large objects to avoid the cost of incrementing the reference count and to avoid manual memory management. Allocate small objects on the stack and pass them by `const` reference if they are larger than 64 bits. Eliminate unused code and debugging code and clean up the documentation as you progress through the specification. Plan to refactor frequently as the implementation guides you into recognizing good helper routines. As a rules of thumb: - Method names should be verbs, for example: `render`, `intersectRay` - Class names and members should be nouns, for example: `RayTracer`, `scene` - Methods shouldn't be more than 20 lines long - Variables should be declared in the tightest possible scope - Method names should implicitly provide the bulk of the implementation documentation, making the algorithms clear on scanning the code using them - There should be no implementation code in your header files - Destructors should be `virtual` - Most state and methods should be `protected` - Most methods and variables should be `const` unless there is a reason for them not to be - Subclasses of `ReferenceCountedObject` should have protected constructors and public static factory methods named `create` - Large objects such as arrays and tables should not be passed by value or copy-constructed - Don't use lower-case `L` or any case of `O` as variable names, because they look like 1 and 0 in many fonts. (This comes up a lot in graphics because you're tempted to use them for iterating over lights and objects.) There are of course specific cases where these guidelines don't apply. For example, "options" classes and event handlers often have slightly different conventions. I also tend to lump all of my GUI creation code into one giant method (because it is so inherently ugly that there's no hope of abstracting it well). Fix all warnings as they arise. There's a reason that the compiler is warning you about them--each is a potential bug. Add lots of assertions as you progress. The scariest program to debug is one that runs without error on the first try. You know that the odds are that there are bugs in there...but they aren't making themselves known. When you hit a few assertions on the first run, you can have some confidence that you're catching the bugs. Recall that in this document, I use full namespaces--`G3D::` and `std::`--so that you'll know whether the referenced APIs are in G3D or the standard library, or specific to the project. In your actual program you don't need those namespace qualifiers and I recommend eliminating them to increase code clarity. GUI -------------------------------------------------------------------------------------------- I abstracted fetching the resolution from the GUI into a `App::resolution() const` helper function that I called at the top of my `App::render()` method instead of trying to respond to events from the `G3D::GuiDropDownList`. Within `App::resolution`, I used [`G3D::Vector2int32::parseResolution`](https://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_vector2int32.html#a4feab90e1e38b8c7882bae7bdb170221). [`G3D::GApp::drawMessage`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_g_app.html#a1d796dc185b9528b900d936a8b537f8d) allows you to show a message on the screen without waiting for the next hardware graphics frame. This is convenient for showing the "Rendering..." message. There are various G3D and C++ standard library timing routines. I prefer [`G3D::Stopwatch`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_stopwatch.html) for its convenience and accuracy. See the `tick`, `tock`, `after` and `elapsedTime` methods. Render Setup -------------------------------------------------------------------------------------------- I wrote an `App::onRender` callback function to performed the following tasks: 1. Determine the rendering options (e.g., resolution) 2. Create the output [`G3D::Image`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_image.html) 3. Pose the scene (with [`G3D::GApp::onPose`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_g_app.html#a745bded65252fdb9e030fab3dac267d1)) to extract the [`G3D::Surface`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_surface.html)s. I ignored the `G3D::Surface2D`s that it produced. 4. Create a `RayTracer` instance (my own class for this project) and set the scene from [`G3D::GApp::scene`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_g_app.html#a90dc01900fe550e53ba51b1440378988) 5. Launch the actual rendering on `RayTracer` with the image and the [`G3D::GApp::activeCamera`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_g_app.html#a71e82db8c06ec12d86abbe8c7acb4251), using [`G3D::Stopwatch`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_stopwatch.html) for timing 6. Convert the image to a [`G3D::Texture`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_texture.html) and post-process the image with [`G3D::Film`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_film.html) 7. Display the image on screen I copied the post-processing code from the [`cpuRealTimeRayTrace`](https://casual-effects.com/g3d/G3D10/samples/cpuRealTimeRayTrace/) project, looking up the relevant classes and images to ensure I was using them correctly. My code looked like: `G3D::Texture` is an image stored on the graphics processing unit (GPU) instead of the CPU. I converted from `Image` to `Texture` for two reasons. First, it makes the post-processing faster to run it on the GPU. Second...G3D provides GPU post-processing and not CPU post-processing, so this saved me having to write my own image filters. Ray Generation -------------------------------------------------------------------------------------------- I abstracted the ray intersection and ray tracing algorithms into a `RayTracer` class. That class separated setting the scene from the actual rendering, and contained a large number of small helper routines with names such as `traceOneRay`. My core internal data structure was a [`G3D::TriTree`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_tri_tree.html), which I used as an array via its `operator[]` overload. The [`G3D::Scene::onPose`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_scene.html#ad82e03c87a121c682c4702ba50f4c869) and [`G3D::TriTree::setContents`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_tri_tree.html#a04d93cb570c3db3babc20556aa149f7c) methods handled the heavy lifting of data structure initialization. There are other ways to do this, but this was the easiest. I also extracted all of the lights from the scene into an array. I abstracted rendering options for adding the fixed primitives to the scene, multithreading, and so on, and some debugging flags into a `RayTracer::Options` class. I set this at the same time as the scene. This will allow me to have some other global options for future projects. I used this directly as the state for the GUI objects in `App`. I used the 1x1 resolution a lot for debugging because that made it easy to point the camera at an object, push render, and then single-step through the rendering loop. For the single threaded ray tracer, I used the following graphics idiom: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ c++ for (Point2int32 point; point.y < height; ++point.y) { for (point.x = 0; point.x < width; ++point.x) { ... } } ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This has two nice properties. The first is that the iteration variable is a 2D point ready for use in the body. The second is that the loop iterates most tightly along the horizontal axis, which is how images are usually stored on the GPU. This gives good cache coherence and grouping tightly in space (in either $x$ or $y$) gives good branch coherence. Note the C++ iterator style of preincrement on the loop variables as well. For the multithreaded ray tracer, I used [`G3D::runConcurrently`](http://casual-effects.com/g3d/G3D10/build/manual/namespace_g3_d.html#a30fe8097c590faffb051b6ed500bff50) to launch a 2D block: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ c++ runConcurrently(Point2int32(0, 0), Point2int32(image->width(), image->height()), ...); ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This is much more efficient than explicitly creating individual threads because `runConcurrently` optimizes for memory locality and performs load-balancing across processors. You'll need a `std::function` for the `...` portion. I used a C++ lambda expression. Multithreading -------------------------------------------------------------------------------------------- Code inside of the lambda argument to `runConcurrently` must be *threadsafe*. It cannot mutate non-local variables unless you either can guarantee that two threads are never going to access the same location in a data structure at the same time or you synchronize them using some kind of atomic or locking structure (which is both slow and complicated, so let's not do that for this project). If you need a random number in a thread, be sure to use the `G3D::Random::threadCommon` instance, and always use that instance from the same thread that extracts it. Don't allocate memory in a `runConcurrently` lambda body. Doing so is going to be slow, and if you resize an `Array` or other structure, you'll create a race condition. How do you know if you have a threading problem? Your program will likely crash, seemingly at random. You can force `runConcurrently` to operate on a single thread with the optional final argument in order to try and track this down. _Note that `G3D::TriTree::setContents` uses `newImageStorage = ImageStorage::COPY_TO_CPU` by default. This is essential for a multithreaded program. It ensures that textures are copied to the CPU when the `Tri`s are extracted from the scene, on a single thread. Your program will crash at a random time if you use `G3D::runConcurrently` to extract a `G3D::Surfel` from a `G3D::Tri` and the data was not previously copied._ Intersection -------------------------------------------------------------------------------------------- I implemented sphere primitive intersection first because it is a little easier than triangle intersection. Once that was working, I added the triangles. In each case, I simply copied the relevant code from the Graphics Codex and then adapted it to my program. There is no need to rederive the intersections from scratch for this project. Writing those derivations yourself is enlightening and I recommend doing it at _some_ point, but for triangles, is also an opportunity for a lot of hard-to-debug errors because the intermediate terms have no simple geometric interpretation. It is hard enough just adapting existing correct code to your own program. Recall that the equation for a sphere of radius $r$ about point $C$ is $|X - C| -r = 0$. Substitute the equation of a ray, $X(t) = P + \w t$ into the sphere equation for $X$ and solve for the intersection distances. Reject any negative and imaginary solutions. The smallest nonnegative real solution gives you the intersection distance. If an intersection exists, you need to construct a _surface element_ (surfel) to store the information and return it to the shading portion of the algorithm. I recommend that you make a [`G3D::UniversalSurfel`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_universal_surfel.html) and then directly assign to its member variables (in later projects, you may wish to create your own surfel subclass with different material parameters). The simplest material parameter is to set the `G3D::UniversalSurfel::lambertianReflectivity` to the color that you want the object to appear. You'll also need to set the `geometricNormal` and `shadingNormal` to the same value: the normal to the sphere at the intersection point, and to set the `position` of the intersection. You can ignore the other properties. When you have more than one primitive in the scene, you must separate the variables used for tracking the current-closest intersection distance and current-closest surfel from those used for testing each primitive. Only when a new intersection is discovered that is closer to the camera than the previous one should the current closest-values be updated. The [`G3D::TriTree`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_tri_tree.html) acts like an array of triangle indices and materials. (Why is it named "tree" if it acts like an array? Because it also stores a binary tree internally that we'll use for $ \O(\lg n) $ time intersections in another project. This week, we'll have $ \O(n) $ time intersections for $n$ triangles.) `TriTree` also stores a vertex position array to complete the indexed-triangle mesh data structure. The basic algorithm for intersecting a triangle with a ray is in the _Graphics Codex_. It intersects the plane of the triangle and then tests whether the barycentric coordinates of the intersection actually lie within the triangle. If they do, then the ray hits the triangle and its properties can be sampled at the intersection point. There are several ways to perform the sampling. [`G3D::TriTree::sample`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_tri_tree_base.html#a4c2a68b5d8bd26b5599651394c5bd006) is the simplest if you construct a [`G3D::TriTree::Hit`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_tri_tree_base_1_1_hit.html) for your closest intersection. There are two important features that must be handled for proper triangle intersections. The first feature is normal flipping for backfaces. We'll allow all of our triangles to be "two sided" for now, so that we see consistent results from the front and back of the triangle. When you detect a hit on the triangle, if the dot product of the ray direction and the counter-clockwise normal is positive, then the ray actually struck the triangle from behind. Set the `G3D::TriTree::Hit::backface` flag to true in this case. That tells `G3D::TriTree::sample` to flip the normal direction to be the one facing the ray when sampling materials and geometry for shading. The second triangle intersection feature is "alpha testing", also known as "alpha masking", "$\alpha$ testing", and "coverage testing". Some surfaces, such as tree leaves, are modeled with triangles that have areas cut out of them. The cutout is stored in a special coverage material channel that is typically denoted $\alpha$. Once you've sampled a triangle, check the coverage value in the surfel. If it is less than 1.0, ignore the intersection and allow the ray to continue. ### Precision Issues A serious practical limitation of ray-based algorithms is that they are very sensitive to numerical precision problems in the representation of directions, positions, and distances. Your code will be full of many different "epsilon" values in an attempt to conservatively detect--or avoid--intersections. ![Figure [fig:acne]: Left: Shadow "acne" from limited precision near intersections. Right: Ray bumping compensates for this limitation.](acne.png) To avoid intersecting the origin surface, rays often have to be "bumped" a short distance from their origin before beginning computations. The [`G3D::Ray::minDistance`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_ray.html#a75525b1e41c81337bb7fbc3ca3c1540f) can accomplish this without loss of precision that would come from recomputing the origin. However, for indirect light rays at glancing angles, it is often necessary to push the ray not just out from the origin point but specifically _away from the surface_. The normal is the known direction away from the surface, so shifting ray origins by a small epsilon times the (geometric) surface normal is a common practice. The [`G3D::Ray::bumpedRay`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_ray.html#ab10215f63498133e2f7350aa0db7c85b) can do this for you, although in some cases it is easier to compute the bumped origin explicitly before constructing a ray. For a *shadow ray*, bump the ray with: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ C++ static const float epsilon = 1e-5f; // m // Shoot at a point just above the surface Vector3 w_i = lightPosition - (surfacePosition + geometricNormal * epsilon); const float distance = w_i.length(); w_i /= distance; // Start from slightly forward from the light in case it is on a surface const Ray& shadowRay = Ray::fromOriginAndDirection (lightPosition + w_i * epsilon, direction, 0.0f, distance - epsilon); ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ For an *indirect light ray*, bump the ray with: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ C++ // Start from slightly away from the surface, on the side that the // ray is traveling away from const Ray& shadowRay = Ray::fromOriginAndDirection (position + epsilon * geometricNormal * sign(geometricNormal.dot(direction)), direction); ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Shading -------------------------------------------------------------------------------------------- Shading only took about 20 lines of code, most of which were branches and loops, in my implementation. I had to think about those 20 lines for a long time, however, because they were the core of the algorithm. ![Figure [fig:reflectivity]: Lambertian](reflectivity.png border=1 width=140px) ![Figure [fig:direct]: Direct lighting](lighting.png border=1 width=140px) ![Figure [fig:shadows]: + Shadows](shadows.png border=1 width=140px) ![Figure [fig:indirect]: + Indirect](indirect.png border=1 width=140px) I used [`G3D::Surfel::finiteScatteringDensity`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_surfel.html#aa0fb097d5a3527a00411940efb7e67b9) to evaluate $ f_X(\wi, \wo) $ and [`G3D::Light::biradiance`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_light.html#ac4d2f32e4082e7a4980bc05bb52f18d0) to compute the _unshadowed_ biradiance $ \beta(X, y) $. You can of course compute these values yourself from the parameters, and should at least look at the implementations to see what they are doing for you. G3D's point light sources have a position represented in _homogeneous coordinates_. This means that the 3D position of the light is stored in a `G3D::Vector4`. If the `w` component of this vector is `1`, then the light is at a finite position. If the `w` component is `0`, then the light is at infinity (e.g., approximating the sun). In this case, the direction _to_ the light is given by its other coordinates, and the idiom `light->position().xyz().direction()` can be used to extract it. Because the `w` component is binary, there's also a convenient trick for finding the direction from finite point $X$ to potentially-infinite homogeneous point $Y$: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ c++ const Vector3& w_i = (Y.xyz() - X * Y.w).direction(); ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ For reasons that will not be clear until the next project, I recommend that you cast your shadow visibility rays _from the light_ towards the surface for finite lights. Remember to avoid numerical precision issues by making the ray slightly shorter than the actual distance. There are several design choices about when to use `G3D::Ray` vs. a distinct point and direction and when to use homogeneous coordinates that greatly affect the clarity of this portion of the program. Try a few designs and see what leads to the clearest, shortest code. Be really careful with vector direction. Recall that in the mathematical notation of rendering, all vectors point _away_ from the point being shaded. You'll often have to negate ray directions and such to maintain consistency with the typeset mathematics. The "ambient" term approximates the interreflected light that is missed by computing only direct illumination. (It also helps us to see the materials when the lights aren't working properly.) To compute outgoing radiance from the "ambient" incoming constant, use: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ c++ L_o += surfel->reflectivity(Random::threadCommon()) * 0.05f; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ [`G3D::Random::threadCommon`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_random.html#a830d5f9ffbe70751ca859e1c05ba1a03) produces a pseudo-random number generator that is tied to the current thread. This avoids race conditions when running your program in multithreaded mode. You could also use the threadsafe `G3D::Random::common`, however, that is slower because it must lock for each number generated. At first, render your image without any shading. Just let the radiance equal the surfel's `lambertianReflectivity`. When that is working, compute direct illumination without shadows. Then, compute shadows. Finally, when everything else is working, add the indirect rays. These should only add three lines to your program (and make it run _really_ slowly.) When you're testing the performance of your program versus the number of lights, don't try to create many lights in the scene file. That will just crash the real-time preview renderer, which was only designed to handle about eight lights per scene. Instead, either loop your code for a single light in the renderer (you're just timing; you don't care what the image looks like) or construct lights directly into the ray tracer's lighting array instead of loading them from the scene. ### Indirect rays There are several ways to numerically evaluate the Equation \ref{eqn:indirect}. Sophisticated evaluation of indirect light is the focus of the next project, not this one, so any correct solution is acceptable on this project. The key design choices are have to select the discrete $ \wi $ values from the hemisphere and solving for the corresponding measure of $ d\wi $. Let $ k $ be the number of indirect rays. If you choose $ \wi $ uniformly at random (say, with `G3D::Vector3::hemiRandom`), then each one represents a solid angle patch of measure $ 1/k $ of the area of a hemisphere. If you instead choose your rays from a cosine distribution on the hemisphere (using [`G3D::Vector3::cosHemiRandom`](http://casual-effects.com/g3d/G3D10/build/manual/class_g3_d_1_1_vector3.html#a5d0b67550a0019cb48227ce935630f19)`(surfel->shadingNormal, G3D::Random::threadRandom())`), then you should also drop the cosine (dot-product) weighting from the integrand, because it is already accounted for by the sampling distribution. If this trick doesn't make sense yet, just ignore it. We'll soon see how we can improve our convergence rate using probability. When you add indirect rays, you'll probably find that the scenes you are rendering are too bright. This is because those scenes have cameras that were adjusted for direct illumination only. Simply switch to the debugging camera (press F2), open its properties, and decrease the sensitivity. You can probably disable your "ambient" term when casting indirect rays, or at least reduce its magnitude. It now only needs to account for the unmeasured energy for paths of length four rays and longer, which is a smaller fraction of the energy in most scenes. If you see white spots and highlights on the red and green walls of the Cornell Box, that is a sign that you forgot to modulate the indirect light by $ f_X(\wi, \wo) | \wi \cdot \n| $ at the surface that scattered it. This code should look identical to direct illumination, but with the biradiance replaced with the indirect light radiance and a $ d\wi $ term that is the $ 1/k $ fraction of the hemisphere's measure. (If you used cosine scattered rays, then you should _not_ have a $ |\wi \cdot \n| $ term in your modulation, because that's the cosine you were accounting for.) Gallery ============================================================================================ For more inspiration, look at some examples of work created by my students for this project: - [Williams College CS371 2016](https://www.cs.williams.edu/~morgan/cs371-f16/gallery/2-rays/index.html) - [Williams College CS371 2014](https://www.cs.williams.edu/~morgan/cs371-f14/gallery/2-EyeRays/index.html) - [Williams College CS371 2012](https://www.cs.williams.edu/~morgan/cs371-f12/gallery/2-EyeRays/index.html) - [Williams College CS371 2010](https://www.cs.williams.edu/~morgan/cs371-f10/gallery/2-EyeRays/index.html)