From: cn1@irz301.inf.tudresden.de (Nguyen, D.C.)
Subject: What's wrong w/ MonteCarlo methods?
To: globillum@imag.fr (Global Illumination List)
Date: Mon, 28 Oct 1996 15:50:34 +0200 (MESZ)
I often ask myself : MonteCarlo raytracing, is this the way to do
globillum in the future? After reading a lot of papers aboud MCmethods, i still get
confused w/ their terminologies. I can't see any advantage of these methods
over traditional methods (radiosity), except the fact that meshing is not
needed, and that you can do referenceimages for RMSbenchmark(!)
For me, the most important feature of a rendering method is not its
physicalcorrectness, but its efficiency and visualastheticpossibilty.
With MCrendering, i must spend lot of works to develope specific sampling
shemes and reasonable 'good' estimators. Even w/ that, i still get useless
images (too noisy!), or i must increase the sampling rate and wait forever...
It is not always true that most people find noises less obsevable than aliasing.(
i.e white pixels in a darkcorner vesus aliased darklines) .
Especially for the direct lighting computation, MCmethods are definitely
*NOT* the way to go. : The most regions of an image are not in shadow, so why
should we cast so many shadowrays to the lightsource ? In fact, we dont
need to cast any
shadowrays, if the visibilities are known a priory ( w/ shaftculling) and
the radiance comming from the light can be easly computed (analytically).
Only for the case, that complexshadow occurs, MCsampling would be
helpfull. Also for this case, the softshadow generated w/ them can be much
better without increasing the sampling rate ( We simple smooth the
shadowregions, visualaesthetic, not physicalcorrect!).
Of course, i could be wrong:)
JuHu
From: shirley@facility.cs.utah.edu
Subject: Re: What's wrong w/ MonteCarlo methods?
To: cn1@irz301.inf.tudresden.de (Nguyen D.C.)
Date: Mon, 28 Oct 1996 08:31:22 0700 (MST)
Cc: globillum@imag.fr, shirley@facility.cs.utah.edu (Peter Shirley)
Wow we may actually get a discussion going! Is this allowed? :^)
> I often ask myself : MonteCarlo raytracing, is this the way to do
> globillum in the future? After reading a lot of papers aboud MCmethods, i still get
> confused w/ their terminologies. I can't see any advantage of these methods
> over traditional methods (radiosity), except the fact that meshing is not
> needed, and that you can do referenceimages for RMSbenchmark(!)
There is a lot of confusion on this because we all overhype our
methods in papers (me included) and as reviewers and authors we
are sloppy about making people carefully characterize their methods.
Here I will make up four scenes:
1. Lambertian Cornell box
2. Lambertian Cornell box w/smooth metal box
3. Lambertian Cornell box w/glass sphere instead of short block
4. Semimatte (direction diffuse) Cornell box
5. Semimatte (direction diffuse) Cornell box with "real object (10^6 patches)
1. Traditional worldspace FE will work easily and we can do a walkthrough.
RADIANCE will also work easily, but will not in practice allow a
walkthrough the viewindependent info is there, but it is not
easily accessible. MCPT (Monte Carlo path tracing) will take all day,
but will give an unbiased image (so what?).
2. Now radiosity has problems. We can add a virtual world, or
use particletracing based radiosity with a density estimation
postprocess, but then doing the walktrhough is a problem.
RADIANCE does fine for a given viewpoint, and we can reuse the
irradiance map. MCPT will have LOTS of noise on the ceiling
unless very good importance sampling is used.
3. Uhoh particle tracing based radiosity works. RADIANCE and
MCPT will have a very noisy caustic under the ball (although
RADIANCE will not have this problem for the important
glass case windows!).
4. Ouch. Sillionstyle FE works, as does Jensen's photon map.
MCPT is so dumb, it doesn't realize that this case is
harder than Lambertian. RADIANCE will not work because it
caches irradiance, so it will degenerate to MCPT (really, you
can treat secondary bounces as Lambertian I believe this
is a good move in almost all scenes, but it is hard to
quantitatively justify).
5. Ouch^2. FE runs out of memory FAST. MCPT works no worse
than 4. Jensen's photon map also works, but will be
storageintensive if the object is not very smooth. Radiance will
perform as in 4.
In summary, pure MCPT has only two advantages it is so dumb
that it doesn't get hit by big scenes, and it is easy to implement.
If you want an interactive walkthrough, then you are currently
limited to radiosity (I use that term for all world space
irradiance calculating alg's), and that limits you to
a relatively small scene (100k initial polygons will kill
almost all radiosity implementations).
> For me, the most important feature of a rendering method is not its
> physicalcorrectness, but its efficiency and visualastheticpossibilty.
> With MCrendering, i must spend lot of works to develope specific sampling
> shemes and reasonable 'good' estimators. Even w/ that, i still get useless
> images (too noisy!), or i must increase the sampling rate and wait forever...
> It is not always true that most people find noises less obsevable than aliasing.(
> i.e white pixels in a darkcorner vesus aliased darklines) .
I agree with the above, and I think the solution is hybrid methods
add bias! (This is blasphemy in MC circles :^) ). I do want to
keep the good parts of MC methods they are damned robust and
are possible to implement correctly my MC code does not
bomb on wierd untweaked inputs tell me with a straight face
that is true of most nonMC implementations. However, you
are right that the results are too noisy!!! We can keep these benefits
and reduce noise if we add bias the right way (not that I know what
that right way is).
> Especially for the direct lighting computation, MCmethods are definitely
> *NOT* the way to go. : The most regions of an image are not in shadow, so why
> should we cast so many shadowrays to the lightsource ? In fact, we dont
> need to cast any
> shadowrays, if the visibilities are known a priory ( w/ shaftculling) and
> the radiance comming from the light can be easly computed (analytically).
> Only for the case, that complexshadow occurs, MCsampling would be
> helpfull. Also for this case, the softshadow generated w/ them can be much
> better without increasing the sampling rate ( We simple smooth the
> shadowregions, visualaesthetic, not physicalcorrect!).
I welcome you to implement shaftculling on scene 5 above. Slower
than MC, and will usually coredump even with a year
of implementation I'll bet. Now shaft culling
on simplified geometries (which it sounds like you might be suggesting)
sounds like a very good idea. Only use MC when needed yes, definitely smart.
Overall, this has got me to again reflect on the state of our field.
It is VERY hard to get a rendering paper into SIGGRAPH, even with
good reviews. It is easy to get toys based on lowhanding fruit into SIGGRAPH.
Clearly we are doing something very wrong (you could rightly argue SIGGRAPH is
doing something wrong, but that wont change anything we have to figure
out where our share of the blame is). I think this is partially because most
graphics people think TOY STORY graphics is good enough. I, however, want
virtual reality that looks REAL and is predictive I don't want
a virtual cartoon world. We are very far from getting things
to look real, and from understanding our algorithms' behaviors.
No working program gives useful error estimates. We have
totally inadequate local reflection models. Most algorithms
are memory hogs and don't parallelize. Most algorithms
do a very poor job with dielectrics (water, glass). I think
we need to make our own "grand challenge" models, and publicize
that they can't currently be done (e.g, a human at a desk illuminated
through a skylight), so that our field wont dry up and blow away.
Pete
(InterLock SMTP Gateway 3.0 for globillum@imag.fr);
Mon, 28 Oct 1996 11:09:49 0500
Mon, 28 Oct 1996 11:09:49 0500
Date: Mon, 28 Oct 96 11:09:48 0500
From: swestin@ford.com (Stephen Westin )
To: globillum@imag.fr
Subject: Re: What's wrong w/ MonteCarlo methods?
Why do folks bother at all with Monte Carlo methods for global
illumination? Complexity.
Think of the problem of computing the irradiance at a given point. Do
you want to go around the whole environment, calculating the
irradiance from every object, regardless of occlusion or distance from
the point? Or do you want to probe the environment, spending similar
effort for every incident direction? This is the basic choice between
meshbased methods and Monte Carlo calculations. For simple
environments, the meshbased methods are excellent; they give no noise
artifacts, and computation is tractable. For extremely complex
environments, meshbased algorithms tend to get inefficient.
Actually, the meshbased world and Monte Carlo are working toward each
other. Hierarchical meshing is basically a way to make a meshbased
algorithm behave more like Monte Carlo, spending effort for irradiance
contributions rather than for geometric complexity. And any
welldesigned Monte Carlo calculation uses deterministic methods
wherever practical, and attempts to take advantage of spatial
coherence. The ultimate global illumination method will probably be a
hybrid of Monte Carlo and meshbased methods.
Stephen H. Westin
swestin@ford.com
The information and opinions in this message are mine, not Ford's.
From: cn1@irz301.inf.tudresden.de (Nguyen, D.C.)
Subject: Re: What's wrong w/ MonteCarlo methods?
To: shirley@facility.cs.utah.edu
Date: Mon, 28 Oct 1996 18:23:19 +0200 (MESZ)
Cc: cn1@irz301.inf.tudresden.de, globillum@imag.fr
>
> > Especially for the direct lighting computation, MCmethods are definitely
> > *NOT* the way to go. : The most regions of an image are not in shadow, so why
> > should we cast so many shadowrays to the lightsource ? In fact, we dont
> > need to cast any
> > shadowrays, if the visibilities are known a priory ( w/ shaftculling) and
> > the radiance comming from the light can be easly computed (analytically).
> > Only for the case, that complexshadow occurs, MCsampling would be
> > helpfull. Also for this case, the softshadow generated w/ them can be much
> > better without increasing the sampling rate ( We simple smooth the
> > shadowregions, visualaesthetic, not physicalcorrect!).
>
> I welcome you to implement shaftculling on scene 5 above. Slower
> than MC, and will usually coredump even with a year
> of implementation I'll bet.
I've actually implemented shaftculling for complexscenes in GX/GENERIC.
Not really shaftculling, but a combined version of Arvo's hyperoctree and
Haines's lightbuffer. It's definitely faster than pur MC, because the cost
for collisiontest between a beam and a bbox is quite the same between a ray and
a bbox.
JuHu
From: Eric Veach
Subject: Re: What's wrong w/ MonteCarlo methods?
To: globillum@imag.fr
Date: Mon, 28 Oct 1996 12:36:11 0800 (PST)
One of the big advantages of MC algorithms is that they let you
model the scene you actually want to use. Sure, radiosity
algorithms can be efficient  if we limit ourselves to diffuse
surfaces, with maybe a few mirrors or whatever that are handled
in a raytracing pass. But flat polygons and diffuse reflectors
do not go very far in modeling the real world, and finiteelement
algorithms don't seem to be practical for much more than this.
(Memory usage blows up for complex scenes, or when there are lots
of glossy surfaces.)
This is an important issue in graphics, since often the biggest
source of error is the scene model itself. What good is an
accurate solution to the wrong scene model? At least MC
algorithms start with the desired input. Even if you aren't
interested in physically correct results, diffuse surfaces lead
to that wonderful "computer graphics look" we all know and love.
It's no wonder that radiosity algorithms tend to be faster, since
they are solving a much simpler problem: the solution is only a
twodimensional function rather than a fourdimensional one. To
me, the amazing thing is that radiosity algorithms need to be so
*complicated* to be efficient. By the time you implement
discontinuity meshing, hierarchical basis functions, clustering,
shaft culling, etc., how many lines of code are we talking about?
And can you actually trust it not to coredump, and to compute a
reasonable result in a reasonable amount of time?
And let's not kid ourselves that an algorithm is "general" just
because it can handle a few mirrors or glossy surfaces. The real
test of generality is how an algorithm performs when there are
*no* diffuse surfaces, since that's how it is in the real world.
Another reason to use MC algorithms is scene complexity. Finite
element algorithms work with explicit representations of the
scene and its properties. They are strongly affected by the size
and complexity of the scene representation. On the other hand,
Monte Carlo algorithms are based on sampling, which means that
the scene model is accessed through a small set of queries (e.g.
what is the first surface point intersected by this ray?) This
hides the scene complexity behind a layer of abstraction, and can
mean that rendering times are only loosely coupled to the scene
representation (e.g. it may affect the time required to cast a
ray). In effect, Monte Carlo algorithms can sample the scene to
determine the information they actually need, while deterministic
algorithms examine every detail, whether it is relevant or not.
That's not to say that MC algorithms need to sample *everything*.
It's perfectly reasonable to embed deterministic calculations
within a Monte Carlo framework, especially for lowdimensional
integration problems (e.g.\ direct lighting from a small number
of uniform, diffuse, polygonal luminaires). Sometimes this
introduces bias, but often this is okay, especially when we can
bound the errors or at least characterize them.
Ideally, rendering algorithms should not depend on the details of
the scene representation, but only on the underlying mathematical
model. For example, a square area light source can be simulated
fairly well with a ten by ten array of point sources, but many
rendering algorithms would have a much worse performance in the
second case. Similarly, if we replace the square light source by
two flourescent bulbs covered by a diffusely transmitting panel,
why should it make a huge difference to our algorithms? The same
comments apply to geometric complexity: if we represent an indoor
plant as a thousand polygons or a million Bezier patches, how
much should the rendering time go up?
I can't say that MC algorithms have achieved this level of
isolation from the scene representation, but at least it seems
that the opportunity is there. There has been a lot of emphasis
on rendering algorithms that exploit special properties of the
input scene, e.g. that lighting is direct rather than through a
diffusing panel or bouncing off the ceiling. It would be nice to
see more work on algorithms whose performance does not go down
the tubes when these conditions are not met, i.e. algorithms that
are more *robust*. It seems that this should be possible without
resorting to the level of "dumbness" found in MCPT (as Pete
Shirley put it).
I guess the last major issue for MC algorithms is the correctness
of the results. Here it is important to distinguish between
unbiased, biased, and consistent estimators. Intuitively, an
unbiased estimator computes the right answer, on average. A
biased estimator computes the wrong answer, on average. A
consistent estimator also computes the wrong answer, on average,
but the error can be made arbitrarily small by increasing the
number of samples. Most of the "biased" algorithms in graphics
are in fact consistent, otherwise we wouldn't have any confidence
at all in their results.
The main advantage of unbiased algorithms is that they make it
far easier to estimate the error in a solution. For unbiased
algorithms, this error can be estimated by the sample variance,
since any error is guaranteed to show up as random variation
among the samples. Thus, if an unbiased image is not noisy, we
can be reasonably sure that it is correct. For scene of
realistic complexity, this seems to be the only practical way to
generate correct images.
For algorithms which are merely consistent, however, we must also
bound the bias. In general this is difficult to do; we cannot
estimate bias by simply drawing a few more samples. Bias shows
up as results that are not noisy, but in fact are incorrect. In
graphics algorithms, this error is often noticeable visually, in
the form of discontinuities, excessive blurring, or surface
shading that just looks wrong.
Other things being equal, it is clear that we should prefer an
unbiased algorithm. If these algorithms were also robust and
efficient, then why would we want to use anything else? However,
conventional wisdom says that unbiased methods are "too expensive",
and that we can achieve an acceptable image in less time by making
approximations.
But where is the research to support this claim? There has been
a huge amount of effort on approximate methods in graphics, while
there has been hardly any work on unbiased algorithms. Some
people seem to think that "unbiased" is a synonym for "pure Monte
Carlo path tracing". Until we have thoroughly explored this type
of algorithm, we can hardly make judgements on their
capabilities. I would like to see more results on what can and
cannot be achieved by unbiased methods, so that we can make
better decisions on these issues.
(Can you tell that I'm writing a thesis? :)
Eric
From: "Holly Rushmeier"
To: shirley@facility.cs.utah.edu
cc: cn1@irz301.inf.tudresden.de, globillum@imag.fr
Date: Tue, 29 Oct 1996 08:11:58 0400
Subject: Re: What's wrong w/ MonteCarlo methods?
I would take issue with one of Pete's statements:
>In summary, pure MCPT has only two advantages it is so dumb
>that it doesn't get hit by big scenes, and it is easy to implement.
>If you want an interactive walkthrough, then you are currently
>limited to radiosity (I use that term for all world space
>irradiance calculating alg's), and that limits you to
>a relatively small scene (100k initial polygons will kill
>almost all radiosity implementations).
The big deal about imagebased rendering, i.e. QuickTimeVR
(or PanoramIX :) ), or the more advanced Light Field Rendering or
Lumigraph is that we can interactively walkthrough scenes
precomputed with Monte Carlo  the same way you can walk
through a scene precomputed with radiosity.
 Holly
From: shirley@facility.cs.utah.edu
Subject: Re: What's wrong w/ MonteCarlo methods?
To: HOLLY@watson.ibm.com (Holly Rushmeier)
Date: Tue, 29 Oct 1996 06:23:45 0700 (MST)
Cc: shirley@facility.cs.utah.edu, cn1@irz301.inf.tudresden.de,
globillum@imag.fr
Holly is of course right! As a MCPT fan (maybe you couldn't tell
that from my note it is my favorite rendering alg, because
although it is flawed, I think its flaws are easier to
fix than other alg's flaws see Eric Veach's note), I was
very happy to see that imagebased stuff get big where
will those images come from? :^)
Also, my comments really apply to "naive" MCPT if you
add bias or good importance sampling, it may end
up being practical even without Imagebased stuff.
Pete
>
> I would take issue with one of Pete's statements:
>
> >In summary, pure MCPT has only two advantages it is so dumb
> >that it doesn't get hit by big scenes, and it is easy to implement.
> >If you want an interactive walkthrough, then you are currently
> >limited to radiosity (I use that term for all world space
> >irradiance calculating alg's), and that limits you to
> >a relatively small scene (100k initial polygons will kill
> >almost all radiosity implementations).
>
> The big deal about imagebased rendering, i.e. QuickTimeVR
> (or PanoramIX :) ), or the more advanced Light Field Rendering or
> Lumigraph is that we can interactively walkthrough scenes
> precomputed with Monte Carlo  the same way you can walk
> through a scene precomputed with radiosity.
>
>  Holly
>
>
>
>
>
>
To: "Holly Rushmeier"
cc: shirley@facility.cs.utah.edu, cn1@irz301.inf.tudresden.de,
globillum@imag.fr, jnimerof@graphics.cis.upenn.edu
Subject: Re: What's wrong w/ MonteCarlo methods?
Date: Tue, 29 Oct 1996 11:23:38 0500
From: "Jeffry S. Nimeroff"
>
> The big deal about imagebased rendering, i.e. QuickTimeVR
> (or PanoramIX :) ), or the more advanced Light Field Rendering or
> Lumigraph is that we can interactively walkthrough scenes
> precomputed with Monte Carlo  the same way you can walk
> through a scene precomputed with radiosity.
>
>  Holly
>
Well, I have to take exception with this statement, at least for now
(sorry Holly :)). The lumigraph and light fields are for the space
around convex regions of the environment (inside the "slabs") or for a
free space region inside an interior scene. Freedom of movement
(quick indexing of the data structure) can be done using hardware
texturing which is nice, but the method is not applicable for any
environments I would consider outstanding. Being able to orbit around
or pan near a small cluster of objects is not much more novel than the
capabilities supplied in Quicktime VR and I don't know of many
interior scenes that have lots of free space (pathways without
occlusions like columns, or furniture).
There is a simple modification of lightfields that allows full range
of motion within computerrendered scenes that is equally as efficient
as the original implementation, but you'll have to wait for my newest
work to be done :).
And if you want moving objects in your scene (a sense of time)...
Jeff
Date: Tue, 29 Oct 1996 09:35:57 0800
From: Alain Fournier
To: HOLLY@watson.ibm.com, jnimerof@graphics.cis.upenn.edu
Subject: Re: What's wrong w/ MonteCarlo methods?
Cc: cn1@irz301.inf.tudresden.de, globillum@imag.fr,
shirley@facility.cs.utah.edu
Quick remark (and boy, have I been wrong before): I think the light field
techniques are very interesting and valuable, but not as primary rendering
techniques (if they were ever intended that way). They will be especially
useful when merged with CG scenes rendered from models (with global
illum, natch, also merging with real scenes won't hurt).
Paper at 11:00.
From: Henrik Wann Jensen
Subject: Re: What's wrong w/ MonteCarlo methods?
To: ericv@cs.stanford.edu (Eric Veach)
Date: Tue, 29 Oct 1996 21:38:43 +0100 (MET)
Cc: globillum@imag.fr
Eric Veach wrote:
> MC is better than FE...
I agree :)
> Other things being equal, it is clear that we should prefer an
> unbiased algorithm.
I vote for consistent MCmethods since they really are significantly faster
than the unbiased methods we have seen so far. Just take the irradiance
gradient caching scheme by Greg Ward and the photon map :)
> The main advantage of unbiased algorithms is that they make it
> far easier to estimate the error in a solution.
It's true that the error can be estimated for unbiased methods but
this estimate is probabilistic which in my opinion makes it less useful
since you cannot really trust your result but only be "reasonably sure"
that it is correct.
> I would like to see more results on what can and
> cannot be achieved by unbiased methods, so that we can make
> better decisions on these issues.
You can solve all rendering problems using unbiased techniques such
as path tracing and bidirectional path tracing. But for certain problems
these methods are *very* inefficient. Path tracing is not practical for
rendering caustics. Bidirectional path tracing is much better at visualizing
caustics but it fails when it comes to rendering the mirror reflection
of caustics (created by a small light source). Consider for example a glass
of cognac on a procedural surface :) Even bidirectional path tracing would
have a hard time computing the illumination of the surface just below
the glass and it would be very costly (and timeconsuming) computing
billions of intersection points with a complex procedural surface.
This problem is much easier to solve if you allow storing illumination
information in the model (=bias).
 Henrik
From: Eric Veach
Subject: Re: What's wrong w/ MonteCarlo methods?
To: henrik@mental.com (Henrik Wann Jensen)
Date: Tue, 29 Oct 1996 17:58:01 0800 (PST)
Cc: ericv@cs.stanford.edu, globillum@imag.fr
Henrik Wann Jensen writes:
 > MC is better than FE...
Hey, I didn't say that. Finite element methods also have
advantages, I just didn't mention them.
 > Other things being equal, it is clear that we should prefer an
^^^^^^^^^^^^^^^^^^^^^^^^
 > unbiased algorithm.

 I vote for consistent MCmethods since they really are significantly faster
 than the unbiased methods we have seen so far. Just take the irradiance
 gradient caching scheme by Greg Ward and the photon map :)
The point is that you can't judge the whole class of unbiased
algorithms based on a couple of examples. If you had an
unbiased algorithm that was just as fast, wouldn't you use it?
Such an algorithm doesn't exist yet, but we haven't seen any
solid evidence that this goal is impossible. It's going to take
more research before we know what can be achieved.
 It's true that the error can be estimated for unbiased methods but
 this estimate is probabilistic which in my opinion makes it less useful
 since you cannot really trust your result but only be "reasonably sure"
 that it is correct.
Well, that's still better than no error estimates at all, which
is what you get with biased or consistent algorithms.
For example, let's consider your photon map. I like this
algorithm, and I think it's a great practical tool. But like
many consistent algorithms, it can make large errors that are
difficult to characterize (as I'm sure you are aware). Let's
look at some of the situations where this happens.
For some scenes, the results can be wrong by an arbitrary amount.
The cognac glass sitting on a fractal surface is a perfect
example. Given some point "x" to be shaded, you find the
smallest sphere centered at "x" that encloses N photon hits.
Then you estimate irradiance by assuming that the scene is
locally planar, i.e. its intersection with the interior of the
sphere is approximately a flat *disc*. Thus to get irradiance,
the power carried by each photon is divided by (Pi * r^2).
This obviously doesn't make any sense for a fractal surface. The
area of the surface within a sphere of radius "r" is much larger
than Pi * r^2 (for a true fractal, the area would be infinite,
but even for the reasonably fine subdivisions you are using, it
would be significantly higher). So, the caustics in your images
are probably much brighter than they should be.
Similarly, the disc estimate will be substantially wrong near
corners, or for narrow objects (dangling power cords, wire cages,
blades of grass), or for parallel surfaces that are close
together (e.g. a slide tray, or vertical blinds). The errors are
not small  we're talking about factors of two, or ten, or even
a hundred. The error depends on the ratio of the true surface
area over which the photons are distributed, vs. the area of the
approximating disc.
Now, the photon map is a consistent estimator, so these errors
will get smaller as the number of photons is increased. But for
these examples, it would take incredible numbers of photons to
get a reasonable error. Let's consider the handle on my coffee
mug. It has a diameter of about 1cm. For the disc estimate to
be reasonable (say within 20%), the diameter of the corresponding
sphere must be a couple of millimeters at most. This sphere is
supposed to enclose N=50 or so photons, according to your rules
of thumb, so this implies a density of about ten million photon
hits per square meter. Since all of these photons are stored in
a search tree, the memory requirements would be ridiculous for
typical scenes.
These kinds of errors are typical of many rendering algorithms
that are only claim consistency. I have just been using the
photon map as an example. In fact, it would be my first choice
for some applications. Let's face it, we are stuck with consistent
algorithms for many problems (until something better comes along).
However, I don't think it's fair to compare the photon map with
an unbiased algorithm like bidirectional path tracing. Sure,
there are situations where bidirectional path tracing does not
work well either, but at least the errors can be detected and
estimated by means of the sample variance.
Eric
From: Henrik Wann Jensen
Subject: Re: What's wrong w/ MonteCarlo methods?
To: ericv@cs.stanford.edu (Eric Veach)
Date: Wed, 30 Oct 1996 10:12:19 +0100 (MET)
Cc: globillum@imag.fr
Thus spoke Eric Veach:
>
> Henrik Wann Jensen writes:
>  > MC is better than FE...
>
> Hey, I didn't say that. Finite element methods also have
> advantages, I just didn't mention them.
I were just abbreviating your intro ;)
> If you had an unbiased algorithm that was just as fast, wouldn't you use it?
I sure would. In my examples I was simply refering to the two wellknown
examples of unbiased path tracing based algorithms and they are very
slow.
> For the disc estimate to
> be reasonable (say within 20%), the diameter of the corresponding
> sphere must be a couple of millimeters at most. This sphere is
> supposed to enclose N=50 or so photons, according to your rules
> of thumb, so this implies a density of about ten million photon
> hits per square meter. Since all of these photons are stored in
> a search tree, the memory requirements would be ridiculous for
> typical scenes.
I agree that the basic photon map implementation can give large errors.
These errors can be reduced by using different filtering techniques but
still, I agree, if you want absolute confidence in your result you may
need a large number of photons.
The same does, however, apply to path tracing. A student of mine recently
investigated the error estimates for unbiased path tracing. His results
indicate that just having a confidence of 15% (five percent) that you
are within 1% of the correct result required for most pixels thousands
of sample rays and for some pixels (such as the edges of light sources)
the number of rays exploded.
But I must admit that I really like the unbiased path tracing algorithms
and they would be my choice if I wanted to have absolute confidence in the
result. They are, however, not very practical for everyday rendering.
 Henrik
From: Henrik Wann Jensen
Subject: Re: What's wrong w/ MonteCarlo methods?
To: globillum@imag.fr
Date: Wed, 30 Oct 1996 15:45:49 +0100 (MET)
Henrik Wann Jensen wrote:
> His results indicate that just having a confidence of 15% (five percent)..
This should be 15% and not 5% and btw. the scene was a simple Cornell
box model.
 Henrik
From: "Holly Rushmeier"
To: henrik@mental.com
cc: ericv@cs.stanford.edu, globillum@imag.fr
Date: Wed, 30 Oct 1996 11:11:38 0400
Subject: Re: What's wrong w/ MonteCarlo methods?
To: ericv @ CS.Stanford.EDU
cc: globillum @ imag.fr (bcc: Holly Rushmeier/Watson/IBM Research)
From: henrik @ mental.com
Date: 10/30/96 10:12:19 AM Z1
Subject: Re: What's wrong w/ MonteCarlo methods?
Henrik wrote:
>The same does, however, apply to path tracing. A student of mine
recently investigated the >error estimates for unbiased path tracing. His
results
>indicate that just having a confidence of 15% (five percent) that you
>are within 1% of the correct result required for most pixels thousands
>of sample rays and for some pixels (such as the edges of light sources)
>the number of rays exploded.
Werner Purgathofer did a nice analysis of the number of samples
needed for antialiasing in "A Statistical Method for Adaptive
Sampling" in Computers and Graphics, 1987, pp. 157162.
Using his methodology, and taking into account the dynamic range
of the global illumination problem, assuming simple minded
tone mapping, allowing an error of +/ 10 in
final pixel value (out of 0255) and a requiring an 80% confidence
level gives a minimum sampling rate of 16094 (see Rushmeier & Ward,
"Energy Preserving NonLinear Filters", Siggraph 94, pp 131  138)
The above paper also brings up the notion, that rather than use a
biased algorithm, you can compute a result with an unbiased algorithm, and
then filter the results for consistency based on the values and error
estimates that you get.
 Holly
To: "Holly Rushmeier"
cc: henrik@mental.com, ericv@cs.stanford.edu, globillum@imag.fr,
jnimerof@graphics.cis.upenn.edu
Subject: Re: What's wrong w/ MonteCarlo methods?
Date: Wed, 30 Oct 1996 12:38:40 0500
From: "Jeffry S. Nimeroff"
>
> Werner Purgathofer did a nice analysis of the number of samples
> needed for antialiasing in "A Statistical Method for Adaptive
> Sampling" in Computers and Graphics, 1987, pp. 157162.
>
> Using his methodology, and taking into account the dynamic range
> of the global illumination problem, assuming simple minded
> tone mapping, allowing an error of +/ 10 in
> final pixel value (out of 0255) and a requiring an 80% confidence
> level gives a minimum sampling rate of 16094 (see Rushmeier & Ward,
> "Energy Preserving NonLinear Filters", Siggraph 94, pp 131  138)
>
> The above paper also brings up the notion, that rather than use a
> biased algorithm, you can compute a result with an unbiased algorithm, and
> then filter the results for consistency based on the values and error
> estimates that you get.
>
>  Holly
>
I think this brings up the best motivation of all. Unbiased algorithm, then
filtering for results. Not being a MC person myself, has work been done in
this manner. It always seems that the algorithms themselves are either
unbiased (with proponents talking about error bounds and validation), or
biased (with proponents talking about consistency and/or promoting the "look"
of the results). It seems like efficiency increases with error bounds (even
if they are conservative) can best be accomplished by meeting in the middle.
Jeff
Date: Wed, 30 Oct 1996 17:12:57 0500 (EST)
From: Ken Musgrave
To: globillum@imag.fr
Subject: Re: What's wrong w/ MonteCarlo methods?
My two cent's worth on Monte Carlo vs. radiosity:
The former stands up to a shave with Occam's razor
substantially better.
It took years for Mandelbrot to pound a full
appreciation of elegance into my thick head.
Ken
From: Henrik Wann Jensen
Subject: Re: What's wrong w/ MonteCarlo methods?
To: HOLLY@watson.ibm.com (Holly Rushmeier)
Date: Thu, 31 Oct 1996 13:07:24 +0100 (MET)
Cc: globillum@imag.fr
Thus spoke Holly Rushmeier:
> Using his methodology, and taking into account the dynamic range
> of the global illumination problem, assuming simple minded
> tone mapping, allowing an error of +/ 10 in
> final pixel value (out of 0255) and a requiring an 80% confidence
> level gives a minimum sampling rate of 16094 (see Rushmeier & Ward,
> "Energy Preserving NonLinear Filters", Siggraph 94, pp 131  138)
>
> The above paper also brings up the notion, that rather than use a
> biased algorithm, you can compute a result with an unbiased algorithm, and
> then filter the results for consistency based on the values and error
> estimates that you get.
You can also filter an image generated by a consistent Monte Carlo renderer
and obtain "good quality" much faster. I seem to remember that the
"Energy Preserving NonLinear Filters" paper also presented a technique
for filtering images generated by Radiance (= a consistent but biased
MC renderer).
 Henrik
Date: Thu, 31 Oct 1996 16:58:21 0500 (EST)
From: Ken Musgrave
To: globillum@imag.fr
Subject: Re: What's wrong w/ MonteCarlo methods?
From: Eric Veach
Date: Tue, 29 Oct 1996 17:58:01 0800 (PST)

This obviously doesn't make any sense for a fractal surface. The
area of the surface within a sphere of radius "r" is much larger
than Pi * r^2 (for a true fractal, the area would be infinite,
Not to mention the fact that there would exist no surface normal anywhere
for such a fractal, and that therefore light can only be propagated via
diffraction. ;)
Mo Fractal
From: Henrik Wann Jensen
Subject: Re: What's wrong w/ MonteCarlo methods?
To: ericv@cs.stanford.edu
Date: Fri, 1 Nov 1996 11:46:08 +0100 (MET)
Cc: globillum@imag.fr
Thus spoke Eric Veach
> This obviously doesn't make any sense for a fractal surface. The
> area of the surface within a sphere of radius "r" is much larger
> than Pi * r^2 (for a true fractal, the area would be infinite,
The formula actually uses the *projected area* which is welldefined
even for a fractal surface. And we do not need the normal if the
reflection model for the fractal is Lambertian :)
 Henrik