Beam Tracing via Algebraic Integration

The official description of my planned Ph.D. topic is on-line as a PostScript document here, or as an HTML version here.

That description is necessarily brief, so I would like to add a bit more detail here. This page will be expanded with some more information and some diagrams shortly, but for now I hope the following discourse will give an impression of what I'm getting at. The reader is assumed to have made their way through the above proposal first...

I remind the reader that this is a Ph.D. topic. If you are already researching in this area, please contact me - even if I cannot provide you with any assistance or your research is complete, I'd still rather hear from you as I start work on this topic than as I finish it. Any research I do will be publicly available as soon as the Ph.D. is complete, so please don't feel the need to set up a competing research group or anything...

I will start with a brief description of the current techniques of beam tracing and ray tracing, and go on to compare these approaches with that of my proposed research.

Traditional beam tracing (for reflective surfaces)

Beam tracing started out as a means of rendering reflective surfaces on polygon rendering hardware. When a reflective (planar) surface is encountered, the scene description is inverted about the plane of the surface to bring the reflected eye point in line with the original one; this inversion will require inverting of the sense of any single sided surfaces in the reflection. The reflected scene is then rendered, clipped to the limits of the reflecting polygon - so the effective view frustum is clipped to an open-ended pyramidal shape with the cross-sectional shape of the reflective polygon, with the origin at the (reflected) viewpoint. The three-dimensional, irregular, open-ended pyramid is referred to as a beam. While effective, the technique has some limitations which has made it uncommon in recent times:

• Because the transformation of the eye space must be linear in order to support the polygon rendering, only planar reflection is supported. Because refraction requires a nonlinear transformation, it is impossible to represent refraction accurately with this technique. Additionally, curved mirrors can be supported only by subdividing them into small planar fragments.
• Each reflective surface requires the whole scene graph to be re-traversed - although hopefully the scene will be radically cropped. With modern models supporting a large polygon count, this approach is feasible only with a small number of large polygons.

Recently, the beam tracing concept has been used explicitly to produce reflective floors and water in interactive rendering. Because the polygons exhibiting this reflective effect tend to be large and small in number, it is reasonable to re-traverse the scene graph; they also do not usually inter-reflect. Once the view of the scene has been rendered is is possible to blend it with the lighting model of the surface description to produce a dim reflection, to permute it to represent ripples in water (for example), and to blend multiple reflections with an accumulation buffer to provide blurred reflection.

For small reflective polygons, this approach has been replaced by environment mapping - a technique which is supported in the newer generations of consumer graphics hardware. However, unless the environment maps are re-rendered for each frame - which can be almost as time consuming as beam tracing some of the polygons directly, allowing for the less accurate clipping - the reflections so produced will not include any dynamic portions of the scene. Additionally, because the environment maps are usually shared by several reflective surfaces but rendered from a single viewpoint, there are small inaccuracies in the reflected view.

Beam tracing for area coverage

In addition to supporting reflections, beams can be used to calculate exact pixel coverage for a polygon (for example, for antialiasing). A pyramidal (usually) beam is passed through a pixel, with the origin at the eye point. As the scene graph is traversed, polygons are clipped against this beam. For each polygon which falls within the three dimensional bounds of this beam, the beam is subdivided into fragments, which are each considered individually against future polygons, and these fragments can be non-convex (or need subdividing). The fragments are either closed beams, capped by the plane of the polygon they intersect, or open beams which have not yet hit anything. Beams can rapidly proliferate and become very small. Traditionally beams are only intersected with planar, convex polygons, because of the difficulty of calculating the shape of the intersected beams under less tight constraints.

(Distributed) ray tracing

Commonly used for non-interactive rendering (and beginning to be used in interactive circumstances), ray tracing passes an infinitesimally thin ray from the eye point and into the scene, and considers only the nearest intersection. More rays (to support reflections, refractions and shadows) are cast from this intersection point, according to the surface definition. To support antialiasing, multiple rays can be cast distributed in five dimensional space (sub-pixel antialiasing, lens position to support depth of field, and time). The surface description returns a value which is representative of the flux from the point on the surface, down the ray. Of course, because the ray is infinitesimally thin, the actual flux is zero - but because all samples are defined in the same way the relative values are appropriate. Characteristics of this approach are:

• Support for refraction and reflection in curved surfaces - because the beam is linear, the nature of the reflection is simplified.
• Once the scene is arranged in a bounding volume hierarchy, the hierarchy is traversed only where intersected with the ray; this is a slightly simpler operation than intersecting the whole viewing frustum with a bounding volume, in order to exclude it from a polygon rendering. Additionally, rays traverse the BVH independently, so the bounds comparisons are tight.
• There can be a large amount of geometry under a pixel; rays intersect with the geometry in a Russian-roulette manner, and only the geometry directly in the path of the ray is considered.
• Because the surface hit by the ray is point sampled, the surface description should, rightly, return only the point value at the intersection location. Since some attempt can often be made to support antialiasing at this stage, the description often makes an approximation to the surface area under a pixel. However, this approximation is often either based on the primary pixel projection - which may not take into consideration adaptive sub-pixel sampling, or based on pencil, cone or ray differential tracing techniques (see Computer Graphics, SIGGRAPH conference proceedings); all these are approximations, and none accurately support partial occlusion of the area being approximated. It is not usually the case that an accurate calculation of light flux from the surface to the pixel is performed, and often the approximation assumes the surface is continuous, and some properties of the view point may be assumed.
• The rays are not usually directed in any way dependent on the scene geometry; that is, object intersection is a purely probabilistic process. This means that ray tracing is inherently poor at supporting small objects which have a high contribution to the resulting image - for example distant, bright stars (which are normally approximated with an environment map instead, restricting the resolution of their representation). Similarly, a small, bright highlight on a curved surface may be missed by a ray - or visible when it should be occluded if coverage approximation is used. Some attempt may be made to associate complex and reusable ray paths for secondary rays with geometry (Photon mapping, Metropolis sampling), but current techniques reconstruct this information based on random ray paths, not directly from the geometry.

Algebraic integration - the proposed approach

Where ray tracing integrates the flux incoming through a pixel via (largely) undirected point sampling, and (coverage) beam tracing integrates only unweighted coverage from a linear mapping of coordinates, the proposed approach is to construct the integral of the BRDFs under the pixel in an explicit, lazy manner. By manipulating the terms of the integral, it should be possible to support nonlinear effects such as refraction and reflections in curves surfaces. By redefining the surface descriptions to return an integral equation rather than a single value, the integral can be manipulated algebraically prior to evaluation.

Should the mapping of coordinates between spaces become unreasonably complex, the integral can be subdivided and, in the worst case, rays cast as an approximation. It is hoped that a number of known mathematical heuristic approaches can be used to minimize the need to resort to that failure mode, and that when necessary the rays can be directed more intelligently (by examination of the form of the integral) than is the case with a distributed ray tracer. However, the physical nature of light transmission places restrictions on the potential forms of the integral (given some assistance from surface models, and presuming we are talking about realistic scenes); it is hoped that this will simplify the problem to the extent where (at least approximate) direct evaluation will usually be possible.

Using direct manipulation of the integral, I would hope that this approach would capture small but significant surface effects (such as specular highlights) which are hard to capture by point samples; additionally the nature of the explicit beam means that a known area of the surface is examined, rather than an approximated reconstruction as used with conventional techniques.

With regard to beams becoming unmanageably complex, I believe that by producing a more direct relation between geometry and surface description, it would be possible to make substantial use of level of detail techniques. Since beam tracing allows an accurate assessment of the visibility of parts of the scene graph, it should be possible to apply LoD techniques safely, and greatly reduce the complexity of the resulting beams. Further, the proposed integral construction technique would allow the LoD to be varied depending on weighted affecting the portion of the beam containing the geometry, and also according to the geometry affecting the incoming beam (e.g. an object viewed through a lens), the affected area (e.g. a small object casting a large shadow), and the environment (e.g. a bright star behind a small but potentially complex object, which could otherwise be approximated more roughly). Each of these cases would be prone to oversimplification in a less integrated (excuse the pun) system. Once more, ignoring beam fragments, hopefully with some intelligent basis, will help manage complexity as a last resort.

Since most physical scenes will consist of additive light terms and multiplicative surface effects, the integral being constructed is likely to be of limited complexity. It is hoped that this fact will make the problem manageable within the time span of the project. Obviously this topic could be investigated in quite some depth, but it is hoped that it will be possible to find a reasonable and interesting set of results during the course of the Ph.D.

In conclusion it is hoped that the approach being researched will solve the following problems:

Small but significant surface artifacts being missed by sampling

These should be evaluated, and identified, in the construction of the integral, assisted by the form of the surface description.

Surface details which should be obscured being incorrectly included

This is an artifact of pencil or cone tracing, and should be avoided by a genuine beam tracing approach.

Significant pieces of geometry not being sampled

A problem with undirected ray tracing, this approach considers all geometry within the volume of the beam; no features should be missed.

Beam tracing creates unmanageably large numbers of beam fragments

By combining the description of a surface and the beam geometry with an adaptive level of detail hierarchy, the fragments should be restricted in number. The form of the integral allows for intelligent culling.

Beam tracing cannot support refraction or curved surfaces

By allowing a complex integral, not just a linear projection, this approach combines the advantages of retaining geometry with the flexibility of a ray traced approach. The actual limit in capability is likely to be somewhere between the two, falling back to ray tracing if necessary in an intelligent manner.

As a brief explanation to some of the topics the following diagram shows:

1. A conventional ray tracer - a ray passes from the eye, through a pixel, and strikes some geometry. The colour of the surface is used as the colour of that pixel.
2. A beam tracer (intersecting a sphere, unusually). A beam is cast, from the eye, through the square pixel. The projection of this square is sampled on the sphere. Note that the highlight is included.
3. A problem: a complex piece of geometry (a camera) which could normally be approximated, since it is small, is occluding a bright object. The full detail of the camera is needed to calculate an accurate coverage for the final shadowing effect.

More details (and especially some explanatory diagrams) will be on-line shortly. Please excuse any errors in this document as it is developed.

There is a less recent description of my approach here, which may or may not make more sense.

Return to the graphics index.

Return to the Home page.