Title: Potential Optimizations for DE based Stepping Post by: hobold on February 09, 2010, 04:11:12 PM As I am working on my own rendering code, I keep reinventing various wheels. However, some of them don't seem to be part of the standard literature yet. So I decided to present them here, either to be used, or to be shot down, or to be recognized as a derivative of prior art. They are untested as of yet, because in the context of my own rendering paradigm, DE is just a fast lookup. Extra sophistication is likely to cost more time than it can save. But when every DE sample is being computed on demand, these things could well be worth it.
Idea number one concerns the standard practice of using distance estimates to step along a ray through a series of unbounding volumes. Typically, every next sample point is chosen to be at border of the current unbounding sphere (fudge factors notwithstanding). It seems to me that this algorithm is simple and elegant, but does not reap the largest possible benefit from each DE sample. That's because every DE sample, by its nature as an isotropic value, not only looks forward along the ray, but backward, too. In other words, if we carefully overstep a bit, the next DE sample could be centered outside the current unbounding sphere, as long as the next unbounding sphere is large enough to touch or intersect the current one. This would not always succeed, but if the next unbounding sphere is too small, we can reliably detect that. In such a case, I would remember the two recently computed DEs for later, and compute a third one centered at the midpoint of the ray interval that was just skipped. If that third DE can close the gap: fine! If not, the third DE takes on the role of "next" DE and we recurse. So how to choose the intentional overstepping in a meaningful way? I think a first order approximation model might do. Basically, I'd pretend that the ray is headed for an infinite plane that it eventually intersects (because we tend to aim the camera where there is something to see, and because we render smoothed surfaces, that appear flatter and flatter the closer we approach). So the DE values linearly grow or shrink as we move along the ray. The last two DEs would lead us to an "estimate of the estimate", i.e. a guess how far we can overstep for the next DE sample. That was idea number one: a method that can potentially halve the number of steps along a ray, hence halve the number of DE computations. Idea number two arises from the isotropic quality of distance estimates as well. Whenever we compute a distance estimate, we don't just learn something about the distance along the direction of the one ray we are computing. Instead, we learn something about a volume of space around the center point of the distance estimate. So we could do the following: rather than compute each ray in isolation, we could regard bundles of nearby rays, centered around a "main ray" that we are currently stepping along as usual. Whenever we compute a DE for the main ray, we are really carving an unbounding sphere away from the unknown space around the fractal shape. The union of unbounding spheres along the main ray will effectively be a solid tunnel. We could intersect the secondary rays (i.e. the immediate neighbours of the main ray) with that tunnel. Probably by intersecting them with one unbounding sphere after the other. Sooner or later the unbounding spheres become too small to intersect the secondary rays. But by then, the secondary rays will have skipped a (hopefully!) considerable portion of the empty space around the fractal object, and we saved ourselves the effort to compute quite a few DE values. That was idea number two: a method that can advance several rays towards the surface in parallel, without computing more DE values. I repeat: these ideas are untested. Their usefulness greatly depends on the actual cost of computing a DE value, and the overhead that arises from the extra sophistication/complexity. Is anybody aware of prior experiments with the above algorithmic tricks? Title: Re: Potential Optimizations for DE based Stepping Post by: JosLeys on February 09, 2010, 08:30:47 PM I use the secondary rays to calculate the normal. What I do is to start along the secondary rays just a small distance back as measured by the main ray.
In other words, if the main ray gives a distance d from the viewpoint, I start the process for the secondary ray at d minus something small. This avoids running the secondary rays as 'fresh' ones. The other thing is that I just use the DE found at that point, although this does not work for all cases. In the cases where it does, I only need one calculation per secondary ray.. Title: Re: Potential Optimizations for DE based Stepping Post by: knighty on February 09, 2010, 09:36:20 PM Hi,
Cool ideas but, Nowadays, it's hard to find new ones. ;) Something similar to your first idea is described in this article: http://graphics.cs.uiuc.edu/~jch/papers/hyper.pdf (http://graphics.cs.uiuc.edu/~jch/papers/hyper.pdf) See title 3.4: Overshooting. Same thing for the second: http://graphics.cs.uiuc.edu/~jch/papers/zeno.pdf (http://graphics.cs.uiuc.edu/~jch/papers/zeno.pdf) See title 2.5.1: Image coherence. (2nd paragraph) These articles are from the inventor of sphere tracing himself so... he devised other improvements :) The coolest is perhaps antialiasing with unbounding spheres! Sometime ago I had an idea similar to your second one and have tested it using evaldraw. Thre are two stages: 1- (edit) 2- improve the result using raytracing. The script follows: Code: () //press F1 for help It's also possible to do coarse to fine rendering. Say... begin with 1/16 resolution with min unbounding sphere apparent radius >= 16x16 pixels then 1/4 resolution begining at previously reached distance... etc. Title: Re: Potential Optimizations for DE based Stepping Post by: hobold on February 10, 2010, 09:09:13 AM Nowadays, it's hard to find new ones. ;) Thank you for the links! I didn't expect my ideas to be really new, when the basic algorithm is over ten years old and many significant minds have had the opportunity to spend brain cycles on it. It's just the usual problem of not knowing the right buzzwords to google for, until you reinvented most of the details. And by then, it's really too late for googling ...Title: Re: Potential Optimizations for DE based Stepping Post by: knighty on February 10, 2010, 09:26:21 PM It's just the usual problem of not knowing the right buzzwords to google for, until you reinvented most of the details. And by then, it's really too late for googling ... This has already happend to me too... More than once ;D |