Mike Stark

Final Radiosity Project

Approximate Discontinuity Meshing

Description

"Standard" discontinuity meshing, wherein the mesh for a radiosity solution is constructed so that certain known discontinuities of the radiance functions all along mesh boundaries. The most obvious discontinuities are created by shadows of polygonal objects cast by polygonal emitters; it can be shown that such a shadow is in fact a piecewise smooth function, consisting of polygonal regions. The actual structure of the shadow regions is, however very complicated geometrically, even for fairly simple objects, and rapidly becomes unmanageable for all but the simplest of scenes. But this is mitigated somewhat by the fact that many of the region boundaries (i.e. the discontinuities) can probably be ignored.

My idea for a final project was originally to devise a method of approximating the important shadow regions, using polygon algebra. I devised an algorithm for doing so, which goes roughly as follows, for a single emitter

  1. For each surface S, compute the union of the penumbras of all objects O on the plane of S, then intersect the resulting polygon with the polygon of the surface. Do the same for the umbras (again, use the union, not the intersection)
  2. Simplify the resulting "super" penumbra and umbra using close-point and oblique angle heuristics.
  3. Triangulate the umbra, and also the complement of the umbra in the penumbra.
  4. Construct a mesh based on the triangulations, and proceed with hierarchical radiosity solution.
(By "polygon", I mean a collection of possibly disconnected oriented contours.) I had two hopes for this method: first, that the resulting polygons could be simplified fairly significantly without losing too much of their inherent shapes; and second, that the penumbra/umbra triangulation would tend to reproduce some of the other discontinuities.

I also wanted to apply this method to the case of multiple light sources, at the expense of seriously complicating the algorithm. The penumbra and umbra polygons would be calculated as above, but independently for each emitter. More involved polygon intersections would then be applied to construct the regions: a separate region would be used for the umbra, penumbra, and totally illuminated regions of each surface for each emitter. This actually makes the number of polygons exponential in the number of emitters, but in practice they could be clustered, for example, into the overhead lights (having the same color) and light coming from a window, resulting only in two effective emitters. Such a configuration was in fact what got me thinking along these lines in the first place.

As it turns out, formulating the penumbra and umbra as polygons is not difficult, and while polygon algebra can be tricky, I actually have working code for this, which is general enough to handle all the polygons which would result from the above algorithm. However, the third step in the algorithm was my stumbling block. While I did come up with what I though was a reasonable method (based on tree-structured polygon contours, and using convex hulls to "punch holes" in the penumbras) I didn't come close to getting it to work in practice. It appears there too many hard cases to deal with.

What I actually did

Because the original algorithm turned out to be too hard I decided to try a simpler approach, based on the same idea (using only the penumbra and umbra) to drive the meshing. The algorithm works as follows:
  1. For each occluder, compute an approximate penumbra and umbra and "clip" to each surface, then split the surface according the the line segments in the umbra and penumbra. After the refinement, the original surface is deleted and the new sub-surfaces are added to the model.
  2. Repeat step 1 for each emitter
  3. Apply standard mesh refinement using the hierarchical algorithm, and render.
The primary shortcoming of this revised method to the original is that because once a surface is split, it remains split, the simplifications I had hoped for cannot be accomplished.

Results

I should say at the outset that success of my project could be described as "marginal" at best, but I learned a fair amount in the process so I am not terribly disappointed. I should also add that I put little effort into image reconstruction; the images you see below show only the constant-radiosity patches. If I had a bit more time, I would like to have explored some display meshing techniques.

Basics of the method

We can obtain a fairly simple picture of what I tried to do, but using replacing the two blocks in the Cornell Box configuration with a single triangular occluder, placed parallel to the floor about halfway up. The shadow cast on the floor drives the meshing approach. If two of the edges of the triangle are axis-aligned, the penumbra is a square with a truncated corner, and the umbra is a small triangle. In the images below, the penumbra is represented by a blue polygon, and a red polygon shows an approximation to the umbra. (When I made these images I was experimenting with umbra approximations that might keep the mesh simpler. It didn't work.)

The first image shows the meshing of the floor based on the penumbra. Notice the long, thin triangles that result. Unfortunately, this problem seems to go with the method. I though perhaps splitting in random order might help a little, but it really doesn't seem to.

Next is the same idea, but the splitting is done with the umbra line segments instead.

Now both...

The thin, nearly degenerate triangles come from the face that the sloped side of the "umbra" almost lines up with the outer penumbra points, but doesn't quite.

The lesson

I guess the moral of the story is that even seemingly simple occluder/emitter configurations can get very messy very quickly. Notice how much better a human (or even a less naive triangulation algorithm) could have done with this configuration! As it happens, if the occluder is rotated slightly, the resulting mesh is significantly better.

Ironically, the full shadow structure gives a much better and simpler mesh than this! However, if one just uses the mesh resulting from the umbra, it's not so bad. In fact, this is exactly what I did in the most recent implementation.

Images

If the triangulation I got looks as ugly as it does, imagine what the images look like!

A Room near Vega--the model

When I started this, I wanted to have some clear discontinuities, so I put together a model based on the Cornell box, with with a "window" in the left wall, the overhead light dropped down a bit, and the blocks replaced by a little table, of sorts. A distance away out the window there is a bluish light source. It's not a point source (this would not work well with the form factor estimate I used) but it is far enough away and small enough that it should cast a blurry image of the window panes of the floor, roughly under the table. Below is the model with standard-grid hierarchical solution.

The solution isn't fine enough to see any detail, but at least the colors are approximately right.

An image

I say this with deep optimism, because I'm waiting for it to finish as I'm writing this! It is constructed using the method described above, using only the umbras for the discontinuity meshing. Initially there are 25 elements in the scene. The result of the first refinement, which is done using the overhead light as the emitter, is 184 objects. After the second refinement, with the off-screen blue light as the emitter, there are 434 objects, which means a minimum of what, 160,000 links? I guess it's not much of a surprise that it's been running for over an hour, on my PC. Incidentally, it only took about two seconds to construct the mesh.

It could be worse I guess, but I'm not very satisfied with the result, particularly after then 18 hours I waited for this. The basic shadow lines are there, but they don't help the smoothness of the radiance approximation much. (I wonder how it would look after being "reconstructed.") But I was hoping for more definition in the shadows of the window panes. Again, the lines are visible, but the image really isn't. Maybe the source was too close, I don't know. Even so, it was probably too bright, thus causing extra bluish light elsewhere in the scene.

After some optimizations, I tried the computation again, without the extra blue light. Here is the image.

Conclusions

My idea didn't work so well. Although, in my defense, the of the obvious problem with the meshing scheme is largely due to the "simpler" method I tried. I think the problem is that the meshing scheme results long thin "sliver" polygons, which aren't reprentative of the general behavior of the radiance function. I think the trouble is that once a surface has been split, the geometry of the scene is irreversibly altered. The first idea was to keep track of the polygons throughout the entire shadow line computation, and then decide on the meshing. Sliver polygons could be avoided in the final triangulation, for example.

Possible improvements

One fairly simple improvement might be to subdivide each surface into fixed-sized regions before the meshing starts. That would at least put a bound on the length of the slivers, but would of course complicate the geometry unnecesarily. Although some clustering might help this some, after the meshing is finished.