Frustum Tracer | |
| Date Logged | Detail |
|
Overview: For polygonal scenes, bring the notion of full "forward" raytracing closer to the realm of plausibility by shooting volumes of light rather than individual rays. Not to go into too much background, but for the uninitiated, traditional CG lighting isn't simulating light at all, just using virtual light locations and directions to determine how to color a polygon. Modern computers are fully capable of creating a virtual ray of light from a source and running all the optical calculations to determine where it goes and how it interacts with various surfaces, but there are an infinite number of light rays emminating from any given light source, and only a tiny fraction will get to a given viewer's eye. Computing every single ray will, in short, be impossible for the foreseeable future, not to mention hugely wasteful. Predicting which rays will go somewhere relevant to the viewer without actually computing the rays is equally infeasible. Hence, for the history of 3D computer graphics, the best renderings have involved throwing a few random rays from a light source to get a general feel for the scene illumination, but doing most of the work by tracing rays of vision from the viewer "backwards" towards objects and light sources, perhaps multiple times from multiple directions, and postprocessing the resulting images. The results can be spectacular, but some effects are still mostly out of reach- accurate light-source refraction is tricky, and I don't think I've ever seen a convincing difraction of a light source into a spectrum, to name a couple. The gist of my idea is to do forwards, from-light tracing, but rather than shoot an arbitrary numbe of rays, fully span the desired area by casting triangular pyramids or frustra. A triangular pyramid can be mathematically represented as the volume between 3 planes, and defining and intersecting planes and triangular polygons within planes is reasonably straightforward. Hence, when a frustum of light intersects a polygon in a scene, it should be mathematically straightforward to split it into frusta that refract through the polygon, reflect off the polygon, or pass by the edges of the polygon without interacting. The pseudocode for such a frustum-tracer might be as follows (working knowledge of ray-tracing & rendering is assumed): - Create a triangular Frustum object definition including the bounding side-planes, virtual light source (effective convergence point of the frustum taper) and distance of the top of the frustum from the virtual light source. Also include any optical parameters of the light (color/frequency, more on this later). - For each light source -- Insert into array [Frustra] the narrowest frustum needed to contain the portion of the scene to be lit, as seen from the light source. This frustum will have its dip at the light source and start a distance of 0 away from the source. - Create a second array, [NewFrusta], empty. - While [Frusta] is not empty: -- For each [Frustum] in [Frusta]: --- Use an occlusion camera and/or the same sort of clipping math that the traditional view frustum uses to fill an array [Tris] with a depth-sorted list of triangles and triangular fragments visible within [Frustum]. These triangles should strictly not occlude eachother as seen from the tip of [Frustum], which may require some additional projection and fragmentation. --- For each scene geometry [Tri] in [Tris] that is beyond the start-distance of [Frustum]: ---- Use the light source of [Frustum] and the vertices of [Tri] to define a [NewBaseFrustum] passing exactly through [Tri] ---- Calculate the rays comprising the edges of [NewBaseFrustum] ---- For each frequency represented in the light source of [NewBaseFrustum]: ----- Use the optical properties of the object [Tri] is a part of to determine the proper refraction of each of the previously calculated edge rays (if [Tri] will even refract light at this frequency) ----- Use those refracted rays to define 3 new planes, with a new convergence point (virtual light source) ----- Append to [NewFrusta] a new Frustum with the above-calculated geometry and optical content (be sure to account for inverse-squared intensity falloff) ----- Use the optical properties of the object [Tri] is a part of to determine the proper reflection of each of the previously calculated edge rays (if [Tri] will even reflect light at this frequency) ----- Use those reflected rays to define 3 new planes, with a new convergence point (virtual light source) ----- Append to [NewFrusta] a new Frustum with the above-calculated geometry and optical content (be sure to account for inverse-squared intensity falloff) --- For each viewer image plane [Tri] in [Tris] that is beyond the start-distance of [Frustum]: ---- accumulate the contribution of this [Frustum] to the image buffer (may require a little math to go from a frequency/spectrum color representation back to RGB) -- Clear [Frusta] and replace it with the contents of [NewFrusta] -- Clear [NewFrusta] So that's it in a nutshell. The Frusta arrays will fill up exponentially, yes, but you only keep working with light that is still doing stuff in the scene, and it's markedly less memory-intensive than trying to handle each and every one of an infinite number of rays that would otherwise comprise each frustum. If you add a threshold at which you decide not to throw additional reflections/refractions, that will make things peter out more quickly, but barring pathological cases of opposing perfect mirrors, all light should in theory find its way to be absorbed somewhere (the "If this material even reflects/refracts this frequency" clauses come into play). I'd start with a single frequency of light and render it as white when it hits the image plane just to get an idea of how the system works. From there, try just using red, green and blue as your 'frequencies' and see if the result is acceptable. I'm not highly trained in optics, but I could believe that if red, green and blue are a minimal set required to generate all colors, you may be able to get by with only red, green and blue frusta. Otherwise, and generally for more accurate results, the more frequencies you build in, the better. If there's a mathematician in the house, you might even be able to come up with volumes much more convoluted than frusta, but still mathematically precise enough to intersect, which can encompass integral distributions of light across the entire spectrum, but that would make my own head explode, so I don't encourage it. Likewise with procedurally-defined non-polygonal surfaces that would yield mathematically precise but ugly non-frusta reflections and refractions. You may also need to think about intensity gradients across frusta to account for triangles which aren't face-on to the frusta light sources and which consequently receive more inverse-squared-falloff light at their near edges than their far edges. Since we're intersecting with strictly planes, these gradients ought to be fundamentally linear, but they could still get ugly. Participating media and subsurface diffusion would be tricky in this method, but it may be possible to log a list of volumes where light frustra intersect blocks of media and do some backwards ray-tracing or other postprocessing to composite clouds and whatnot into a final image. Likewise, if it is possible to detect such intersections, the distance a frustum passes through such a volume could easily plug into and reduce the intensity of the frustum at the next recasting calculation. Also, texture mapping. Hm. Since everything is linear, it should be possible to point each frustum at one or more textures and log the UVs of the regions the frustum has passed through or bounced off of and composite only the color components of those textures that the frustum's color frequency reacts to into the final image plane. But I just winged that theory while typing, so it may have a couple holes. |
|