Automatic Meshing
Simon Premoze
Introduction
In order to capture radiosity correctly over a surface we need to have
a good error estimation for adaptive subdivision. Many algorithms subdivide
according to a discrete approximation to a certain error norm (in Programming
Assignment #2, I used L1 and Linfinity norms). Vedel and Puech introduced
a system that estimates local error based on a bicubic tensor product interpolant
over rectangular mesh elements. The local error estimate is provided by
the L2 norm of the difference between bilinear and bicubic interpolation
over an element (Cohen and Wallace, p. 161). This approach fails to identify
elements where the radiosity is changing very rapidly (eg. elements containing
sharp shadow boundaries). Vedel and Puech said that the complexity of this
method is not justified. They suggest that a simple node radiosities or
gradients should be used for error metric. Unfortunately, all these node
based methods fails at some point, because they cannot completely characterize
the behaviour of the function over the entire element. A local minimum
or maximum can fall entirely inside the lement without affecting the function
at the nodes. The only solution is to evaluate the function inside the
element. One approach is to evaluate the radiosity equation at points within
the element and compare the results with the interpolated values. Lischinski
et. al. tried this technique for 1D elements, however, the technique can
be extended to higher dimensions by evaluating the radiosity at the centroid
of the element. This is also a method of estimating the Linfinity norm.
Campbell describes a systematic approach to determining the behaviour
of the function in the interior. Campbell does not make an assumption that
the radiosity function is smooth over the element. His criterion for the
subdivision is the difference between minimum and maximum radiosities over
the entire element as opposed to only at the nodes. elements that need
to be subdivided are split perpendicularly to the line connecting the max
and min points. In order to find extreme points, a systematic search needs
to be performed using some kind of optimization techniques.
Campbell 's Algorithm
Shadow boundaries are computed a priori. So, fully lit reagions can be
identified and treated differently from penumbra regions. For fully lit
regions, the gradient is computed analitically by differentiating the point-to-polygon
form factor equation. Also, a fully lit region can only have one local
maximum in the interioir of the element, because light sources have constant
emission (ie diffuse light sources).
Gradient for the penumbra regions cannot be computed analitically. A
grid is laid over the region and the function is randomly evaluated at
points inside each cell. Since we can't make any assumptions about behaviour
of the function in the interior of the penumbra region, a global optimization
has to be performed to find local minimum and maximum. Cells whose neighbours
are all greater (or smaller) than the current cell provides the initial
location for local optimization.
Note that small features are not guaranteed to be found using this method.
Note that techniques such as dicontinuity meshing will work better in this
case, because regions bounded by discontinuities contain radiosity function
that is well behaved.
Implementation
I tried to implement Cambpell's algorithm, but failed miserably. I was
able to find regions of the scene that are fully lit, fully in shadow,
or in the penumbra region using a shadow volume technique developed by
Nishita et al. I was able to compute gradient at nodes for scenes
where there were no occluders. Form factor equation (for point-to-polygon)
is continuous and differentiable in this case. However, analytic evaluation
of the gradient is impossible if there are occluders present in the scene.
Furthermore, gradient is undefined at certain discontinuity boundaries.
Some kind of differencing scheme needs to be used to compute these derivatives
numerically. I have not implemented gradient calculation for scenes containing
occluders, which makes the entire technique rather useless, since it was
designed to work best in penumbra regions.
So, I was able to identify elements that need to be subdivided. The
element needs to be subdivided in order to minimize a local error. The
amount by which the error is reduced depends on how the element is subdivided.
If subdivision is not done properly no error is reduced. I have failed
to implement a good optimization method that will help subdividing elements
and ultimately reduce the error.
Example
This is the mesh I was able to create. It was too messy to use in my
radiosity program, so I couldn't generate any real images. Shadow
volumes were constructed by using BSP library developed by Campbell himself.
I have not computed any radiosity gradients other than those at vertices
of my original mesh. No global or local optimization was done. The bottom
line is, the above mesh does not reduce error since most of the element subdivisions
were done in more or less random fashion.
Conclusion
Finding a good error metric for adaptive mesh subdivision is rather hard
problem. Although, conceptually some techniques sound good they might not
work well in practice (Vedel and Puech), provide only more complicated
expression for Linfinity error norm (Lischinski et al.) or are rather complicated
to implement (Campbell). Even if a better error metric is incorporated
into the radiosity solver, a question remains: "Is it worth the trouble?"
Also, I realized that most of these techniques would work fairly well for
some particular scenes, but fail in others. Furthermore, it is obvious
that most of these methods don't work well in complicated scene with a
number of light sources.
References
1. Cohen, Michael, and Wallace, John. Radiosity and Realistic Image Synthesis
2. Lichinski, D., Tampieri, F., and Greenberg, D.P. Improving sampling
and reconstruction techniques for radiosity. TR91-1202, Cornell University,
1991
3. Campbell, A. Modeling Global Diffuse Illumination for Image Synthesis.
PhD Thesis, University of Texas at Austin, 1991
4. Vedel, C., and Puech, C. A testbed for adaptive subdivision in preogressive
radiosity. In Second Eurographics Workshop on Rendering, May 1991
5. Ward, G. J., Rubinstein F.M., and Clear R.D. A ray tracing solution
for diffuse interreflection. Siggraph '88, pp. 85-92
Simon Premoze
premoze@cs.utah.edu