From: cn1@irz301.inf.tu-dresden.de (Nguyen, D.C.) Subject: What's wrong w/ Monte-Carlo methods? To: globillum@imag.fr (Global Illumination List) Date: Mon, 28 Oct 1996 15:50:34 +0200 (MESZ) I often ask myself : Monte-Carlo ray-tracing, is this the way to do globillum in the future? After reading a lot of papers aboud MC-methods, 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 reference-images for RMS-benchmark(!) For me, the most important feature of a rendering method is not its physical-correctness, but its efficiency and visual-asthetic-possibilty. With MC-rendering, 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 dark-corner vesus aliased dark-lines) . Especially for the direct lighting computation, MC-methods are definitely *NOT* the way to go. : The most regions of an image are not in shadow, so why should we cast so many shadow-rays to the light-source ? In fact, we dont need to cast any shadow-rays, 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 complex-shadow occurs, MC-sampling would be helpfull. Also for this case, the soft-shadow generated w/ them can be much better without increasing the sampling rate ( We simple smooth the shadow-regions, visual-aesthetic, not physical-correct!). Of course, i could be wrong:) --JuHu From: shirley@facility.cs.utah.edu Subject: Re: What's wrong w/ Monte-Carlo methods? To: cn1@irz301.inf.tu-dresden.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 : Monte-Carlo ray-tracing, is this the way to do > globillum in the future? After reading a lot of papers aboud MC-methods, 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 reference-images for RMS-benchmark(!) There is a lot of confusion on this because we all over-hype 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. Semi-matte (direction diffuse) Cornell box 5. Semi-matte (direction diffuse) Cornell box with "real object (10^6 patches) 1. Traditional world-space FE will work easily and we can do a walkthrough. RADIANCE will also work easily, but will not in practice allow a walkthrough-- the view-independent 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 particle-tracing based radiosity with a density estimation post-process, but then doing the walktrhough is a problem. RADIANCE does fine for a given viewpoint, and we can re-use the irradiance map. MCPT will have LOTS of noise on the ceiling unless very good importance sampling is used. 3. Uh-oh-- 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. Sillion-style 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 storage-intensive 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 > physical-correctness, but its efficiency and visual-asthetic-possibilty. > With MC-rendering, 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 dark-corner vesus aliased dark-lines) . 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 non-MC 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, MC-methods are definitely > *NOT* the way to go. : The most regions of an image are not in shadow, so why > should we cast so many shadow-rays to the light-source ? In fact, we dont > need to cast any > shadow-rays, 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 complex-shadow occurs, MC-sampling would be > helpfull. Also for this case, the soft-shadow generated w/ them can be much > better without increasing the sampling rate ( We simple smooth the > shadow-regions, visual-aesthetic, not physical-correct!). I welcome you to implement shaft-culling on scene 5 above. Slower than MC, and will usually core-dump 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 low-handing 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/ Monte-Carlo 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 mesh-based methods and Monte Carlo calculations. For simple environments, the mesh-based methods are excellent; they give no noise artifacts, and computation is tractable. For extremely complex environments, mesh-based algorithms tend to get inefficient. Actually, the mesh-based world and Monte Carlo are working toward each other. Hierarchical meshing is basically a way to make a mesh-based algorithm behave more like Monte Carlo, spending effort for irradiance contributions rather than for geometric complexity. And any well-designed 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 mesh-based methods. -Stephen H. Westin swestin@ford.com The information and opinions in this message are mine, not Ford's. From: cn1@irz301.inf.tu-dresden.de (Nguyen, D.C.) Subject: Re: What's wrong w/ Monte-Carlo methods? To: shirley@facility.cs.utah.edu Date: Mon, 28 Oct 1996 18:23:19 +0200 (MESZ) Cc: cn1@irz301.inf.tu-dresden.de, globillum@imag.fr > > > Especially for the direct lighting computation, MC-methods are definitely > > *NOT* the way to go. : The most regions of an image are not in shadow, so why > > should we cast so many shadow-rays to the light-source ? In fact, we dont > > need to cast any > > shadow-rays, 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 complex-shadow occurs, MC-sampling would be > > helpfull. Also for this case, the soft-shadow generated w/ them can be much > > better without increasing the sampling rate ( We simple smooth the > > shadow-regions, visual-aesthetic, not physical-correct!). > > I welcome you to implement shaft-culling on scene 5 above. Slower > than MC, and will usually core-dump even with a year > of implementation I'll bet. I've actually implemented shaft-culling for complex-scenes in GX/GENERIC. Not really shaft-culling, but a combined version of Arvo's hyperoctree and Haines's light-buffer. It's definitely faster than pur MC, because the cost for collision-test 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/ Monte-Carlo 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 ray-tracing pass. But flat polygons and diffuse reflectors do not go very far in modeling the real world, and finite-element 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 two-dimensional function rather than a four-dimensional 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 core-dump, 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 low-dimensional 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.tu-dresden.de, globillum@imag.fr Date: Tue, 29 Oct 1996 08:11:58 -0400 Subject: Re: What's wrong w/ Monte-Carlo 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 image-based 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/ Monte-Carlo 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.tu-dresden.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 image-based 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 Image-based 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 image-based 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.tu-dresden.de, globillum@imag.fr, jnimerof@graphics.cis.upenn.edu Subject: Re: What's wrong w/ Monte-Carlo methods? Date: Tue, 29 Oct 1996 11:23:38 -0500 From: "Jeffry S. Nimeroff" > > The big deal about image-based 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 light-fields that allows full range of motion within computer-rendered 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/ Monte-Carlo methods? Cc: cn1@irz301.inf.tu-dresden.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/ Monte-Carlo 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 MC-methods 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 time-consuming) 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/ Monte-Carlo 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 MC-methods 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/ Monte-Carlo 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/ Monte-Carlo 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/ Monte-Carlo 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 Z-1 Subject: Re: What's wrong w/ Monte-Carlo 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 anti-aliasing in "A Statistical Method for Adaptive Sampling" in Computers and Graphics, 1987, pp. 157-162. 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 0-255) and a requiring an 80% confidence level gives a minimum sampling rate of 16094 (see Rushmeier & Ward, "Energy Preserving Non-Linear 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/ Monte-Carlo 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 anti-aliasing in "A Statistical Method for Adaptive > Sampling" in Computers and Graphics, 1987, pp. 157-162. > > 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 0-255) and a requiring an 80% confidence > level gives a minimum sampling rate of 16094 (see Rushmeier & Ward, > "Energy Preserving Non-Linear 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/ Monte-Carlo 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/ Monte-Carlo 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 0-255) and a requiring an 80% confidence > level gives a minimum sampling rate of 16094 (see Rushmeier & Ward, > "Energy Preserving Non-Linear 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 Non-Linear 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/ Monte-Carlo 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/ Monte-Carlo 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 well-defined even for a fractal surface. And we do not need the normal if the reflection model for the fractal is Lambertian :) - Henrik