tag:blogger.com,1999:blog-8350257063773144600.post4637556449659395178..comments2017-05-12T03:42:15.083-07:00Comments on Pete Shirley's Graphics Blog: A neat trick for ray collisions in nonuniform mediaPeter Shirleyhttp://www.blogger.com/profile/17871569418798062417noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-8350257063773144600.post-19099972570642770972016-10-26T13:21:54.543-07:002016-10-26T13:21:54.543-07:00Thanks Oskar Elek! I was unaware of that 2010 pa...Thanks Oskar Elek! I was unaware of that 2010 paper and it is very good. Peter Shirleyhttp://www.blogger.com/profile/08132940649440747040noreply@blogger.comtag:blogger.com,1999:blog-8350257063773144600.post-3251555793496452062011-11-23T03:04:07.148-08:002011-11-23T03:04:07.148-08:00The technique you describe is much older, originat...The technique you describe is much older, originating from neutron tracking techniques in nuclear physics. It is called Woodcock tracking.<br /><br />Check out f.i. this paper:<br /><a href="http://nis-lab.is.s.u-tokyo.ac.jp/~egaku/sigasia10/abstsigasia10.html" rel="nofollow">http://nis-lab.is.s.u-tokyo.ac.jp/~egaku/sigasia10/abstsigasia10.html</a><br />- it contains an explanation of the technique, and a kD-tree-optimized version of it, along with the proof of unbiasedness. And of course, also the references to the relevant previous work.Oskar Elekhttp://www.blogger.com/profile/12541882347950705983noreply@blogger.comtag:blogger.com,1999:blog-8350257063773144600.post-59619095786752430552011-07-07T08:34:50.926-07:002011-07-07T08:34:50.926-07:00I know this is an old post, but great explanation ...I know this is an old post, but great explanation Dave.Brianhttp://www.blogger.com/profile/02049366749792175737noreply@blogger.comtag:blogger.com,1999:blog-8350257063773144600.post-66618549160506014022010-04-20T23:16:06.027-07:002010-04-20T23:16:06.027-07:00Intuitive argument:
I'm sure you already thou...Intuitive argument:<br /><br />I'm sure you already thought of this, but intuitively the method works by treating the medium as uniform with density smax, except that only a fraction of the particles are visible, namely s(x,y,z)/smax.<br /><br />Proof sketch:<br /><br />While not very rigorous, and maybe not that clean either, here's a sketch of a possible proof in three stages: (1) start with the uniform density case, (2) progress to two densities, and (3) inductively extrapolate to arbitrary density:<br /><br />1) The method works for uniform densities as follows: Let's say that the density of the medium is a*smax (where 0 <= a <= 1). Then, if we compute the expected distance to a scatter event, we get a stochastic sum of segment lengths. Each term has the form<br /><br />-log(1-x)/smax<br /><br />with a different x each time (but each term has the same expected value). The probabilities for the terms being added follow a geometric series:<br /><br />P = 1, (1-a), (1-a)^2 ...<br /><br />Thus, the expected sum of the series is the expected value of a term times the sum of the geometric series (1/a):<br /><br />E[-log(1-x)/smax] / a<br /><br />This is exactly what we would get if just performed the standard calculation using density a*smax.<br /><br />2) We can extend this result to a 2 density case fairly readily. Let the density of the medium be a*smax from d=0 to d=d0, and b*smax for d>d0.<br /><br />Clearly the first segment (from 0 to d0) will have the right density of samples, because it is just the uniform<br />case.<br /><br />We can assure the right density in the second segment by gathering up all the samples that make it past d0, restarting them at d0 and computing a new scattering event based on the uniform density method.<br /><br />However, we would not need to gather up the samples and restart them (compute new scattering distances) if the distribution of samples that make it past d0 in the first step is the same as it would be by restarting at d0. Astonishingly, this is the case, regardless of where the samples start from. This remarkable fact is due to the self-similarity of the exponential falloff function. In other words, if we shift and scale the exponential function it remains the same:<br /><br />e^(-d) = (1/e^(-d0)) * e^(-d-d0)<br /><br />3) Since d0 is arbitrary, we can make it as small as we want, and inductively stack more intervals behind it, making an arbitrary density.<br /><br />~Dave Cline<br />clinedav@gmail.comDr. Davehttp://www.blogger.com/profile/00249218559213535603noreply@blogger.comtag:blogger.com,1999:blog-8350257063773144600.post-54741406014887597532010-04-06T03:13:10.831-07:002010-04-06T03:13:10.831-07:00Hey there,
We have been reading the articles on y...Hey there,<br /><br />We have been reading the articles on your website http://psgraphics.blogspot.com/<br /> and are very impressed with the quality of your information.<br /><br />We have a team of copywriters who specialize in writing articles on various topics and would like to write an original article for you to use on your website – this article will not be used anywhere else on the Internet.<br /><br />In exchange all we ask is that we can have one or two links within the body of the article back to one of our sites. You can view a sample of the quality of our articles at http://www.darkhorse.com.au/blog/<br /><br /><br />If you are interested in having us write an article for your website please just let me know and we would be more than happy to have one written for you within two weeks.<br /><br />Kind regards,<br />Papiapapiahttp://www.blogger.com/profile/16910275201846002702noreply@blogger.comtag:blogger.com,1999:blog-8350257063773144600.post-4358207139286971722009-12-01T04:12:45.442-08:002009-12-01T04:12:45.442-08:00That is a very interesting trick! And the simple r...That is a very interesting trick! And the simple restriction on the noise function (that it has some max value) is quite reasonable for those of us who work with volumes that aren't always easily integrable. Thank you for sharing this gem!Alanhttp://www.blogger.com/profile/13974284227144361410noreply@blogger.comtag:blogger.com,1999:blog-8350257063773144600.post-5164330806189701442009-06-10T13:17:44.714-07:002009-06-10T13:17:44.714-07:00X is uniform on [0,1), and log(0) is undefined. T...X is uniform on [0,1), and log(0) is undefined. Taking 1-X gives you a value in (0,1], and that interval is valid for the log function.graphicsmanhttp://www.blogger.com/profile/02049366749792175737noreply@blogger.comtag:blogger.com,1999:blog-8350257063773144600.post-77942022220859271312009-05-20T17:42:54.925-07:002009-05-20T17:42:54.925-07:00It seems strange to take -log(1-X) when X is a uni...It seems strange to take -log(1-X) when X is a uniform random variable on 0..1. (1-X is also a uniform random variable on 0..1). Why not just take -log(X)?Warrenhttp://www.blogger.com/profile/11221832858387858283noreply@blogger.com