4 ms·

An even larger speedup could be realized by performing "solid guessing" like Fractint: Render at 1/2 resolution (that's 1/4 the number of pixels), then take a s

An even larger speedup could be realized by performing "solid guessing" like Fractint: Render at 1/2 resolution (that's 1/4 the number of pixels), then take a second pass only in areas where there's a color boundary. This cuts render times down to less than half.

Jtsummers 9y ago
When I was in grad school I (briefly) worked on a rendering engine based on this concept. It was trying to do ray tracing for an entire scene in real-time (original work would've been circa 2003, mine around 2006). With dynamic content. The algorithm was, roughly, to render 16x16 pixels at random in the scene. If the variance in colors was low, you're done. If it's high, you cut it in half (kd-tree). Pick a region at random and a random 16x16 pixels and render them. If it's low variance you're good, otherwise split. Eventually things like a wall would have maybe 4 regions describing it, though taking up a large portion of the final image. You repeat this random selection and rendering continuously. There was also a way to merge regions should the scene change and they have a similar color though I've forgotten the details. It was quite fast on commodity hardware from 2004/2005.
- specialist 9y ago
  Coolness. My buddy Roy created AccuRender, a plugin for AutoCAD and others. He did something similiar, back in the day; I'd have to ask him about the details. Strategy went from a scanline to a progressive rendering. While slower overall, the quick results enabled quick sanity checks, a huge UI productivity boon. Now I have to ask him, relive the glory years. :)
azinman2 9y ago
A long time ago someone from Google Maps told me they did something like this with their tiles when everything was a pre-rendered image.
- zeckalpha 9y ago
  Raster pyramids!
kens 9y ago
Well, I already ported Fractint to X Windows so I'm not looking to port it to the Alto too :-)
duskwuff 9y ago
IIRC, there's an even more powerful trick available: render the edges of a rectangle. If there are no color boundaries on the edges, you can usually assume it'll be solid-colored and skip rendering any of the contents. Some exceptions apply.
- hhmc 9y ago
  An enhancement to this method which I've seen is to check the edges of the rectangle for colour boundaries, and also check single random point inside. Presumably you can extend to n x n rectangles and k points inside as a function of n.
- deleted 9y ago
  [deleted]
- tetraodonpuffer 9y ago
  what are the exceptions? I thought that Mandelbrot was always guaranteed to be ok for this optimization (unlike, say, Julia)
  - duskwuff 9y ago
    The exception I'm aware of is when the rectangle is so large that it surrounds the entire set.
  - hhmc 9y ago
    If you are doing colouring based on escape iterations this technique can elide detail.
skykooler 9y ago
Could this be improved even further by starting with 1/512 resolution (or whatever divides well) and making more passes only where there's a boundary - basically as a quadtree?

Jtsummers 9y ago

When I was in grad school I (briefly) worked on a rendering engine based on this concept. It was trying to do ray tracing for an entire scene in real-time (original work would've been circa 2003, mine around 2006). With dynamic content. The algorithm was, roughly, to render 16x16 pixels at random in the scene. If the variance in colors was low, you're done. If it's high, you cut it in half (kd-tree). Pick a region at random and a random 16x16 pixels and render them. If it's low variance you're good, otherwise split. Eventually things like a wall would have maybe 4 regions describing it, though taking up a large portion of the final image. You repeat this random selection and rendering continuously. There was also a way to merge regions should the scene change and they have a similar color though I've forgotten the details. It was quite fast on commodity hardware from 2004/2005.

specialist 9y ago
Coolness. My buddy Roy created AccuRender, a plugin for AutoCAD and others. He did something similiar, back in the day; I'd have to ask him about the details. Strategy went from a scanline to a progressive rendering. While slower overall, the quick results enabled quick sanity checks, a huge UI productivity boon. Now I have to ask him, relive the glory years. :)

azinman2 9y ago

A long time ago someone from Google Maps told me they did something like this with their tiles when everything was a pre-rendered image.

zeckalpha 9y ago
Raster pyramids!

kens 9y ago

Well, I already ported Fractint to X Windows so I'm not looking to port it to the Alto too :-)

duskwuff 9y ago

IIRC, there's an even more powerful trick available: render the edges of a rectangle. If there are no color boundaries on the edges, you can usually assume it'll be solid-colored and skip rendering any of the contents. Some exceptions apply.

hhmc 9y ago
An enhancement to this method which I've seen is to check the edges of the rectangle for colour boundaries, and also check single random point inside. Presumably you can extend to n x n rectangles and k points inside as a function of n.
deleted 9y ago
[deleted]
tetraodonpuffer 9y ago
what are the exceptions? I thought that Mandelbrot was always guaranteed to be ok for this optimization (unlike, say, Julia)
- duskwuff 9y ago
  The exception I'm aware of is when the rectangle is so large that it surrounds the entire set.
- hhmc 9y ago
  If you are doing colouring based on escape iterations this technique can elide detail.

skykooler 9y ago

Could this be improved even further by starting with 1/512 resolution (or whatever divides well) and making more passes only where there's a boundary - basically as a quadtree?