Hello,

I'm kinda new here, but not new to Pov-Ray.

I'm interested in rendering a menger scene, but up until now I'm stuck by at a
Menger Sponge of level 7.

Level 0 to Level 6 together in one scene so far is no problem (takes 1 Gig of
RAM, and 1,5 hour to render a 3200x2400 AA 0.3 scene, with shiny floor and
texture), but at level 7 I keep getting Out Of Memory errors.

So my question is: Since Menger Sponges are recursive (in fact it's only one
single cube, copied millions of times), is there a possibility, to save RAM by
"telling" Pov-Ray to use the same object over and over again, instead of
creating different copies of the same cube?

Thanks in advance for any help,

Terabyte

Post a reply to this message

"Terabyte" <nomail@nomail> wrote:
> Hello,
>
> I'm kinda new here, but not new to Pov-Ray.
>
> I'm interested in rendering a menger scene, but up until now I'm stuck by at a
> Menger Sponge of level 7.
>
> Level 0 to Level 6 together in one scene so far is no problem (takes 1 Gig of
> RAM, and 1,5 hour to render a 3200x2400 AA 0.3 scene, with shiny floor and
> texture), but at level 7 I keep getting Out Of Memory errors.
>
> So my question is: Since Menger Sponges are recursive (in fact it's only one
> single cube, copied millions of times), is there a possibility, to save RAM by
> "telling" Pov-Ray to use the same object over and over again, instead of
> creating different copies of the same cube?
>
> Thanks in advance for any help,
>
> Terabyte

Povray only does that for polygon meshes, sadly.  It's called mesh instancing.
Thankfully, a cube is pretty simple to write as a mesh.

Post a reply to this message

"Terabyte" <nomail@nomail> wrote:
> Hello,
>
> I'm kinda new here, but not new to Pov-Ray.
>
> I'm interested in rendering a menger scene, but up until now I'm stuck by at a
> Menger Sponge of level 7.
>
> Level 0 to Level 6 together in one scene so far is no problem (takes 1 Gig of
> RAM, and 1,5 hour to render a 3200x2400 AA 0.3 scene, with shiny floor and
> texture), but at level 7 I keep getting Out Of Memory errors.

When I work with recursive objects I run into this same issue. Given the number
of objects you are dealing with, there will always be a ceiling at relatively
low iteration counts, but there are a few ways to increase this a bit.

> So my question is: Since Menger Sponges are recursive (in fact it's only one
> single cube, copied millions of times), is there a possibility, to save RAM by
> "telling" Pov-Ray to use the same object over and over again, instead of
> creating different copies of the same cube?

Are you currently are creating new cubes within your loop, or #declaring a cube
and translate/scaling it?

Here are a few ideas that might help you get to a higher ceiling [some may be
better than others]:
1) Use mesh instead of cube
2) Use backface/hidden object culling
4) Alter your method to be non-recursive [this works in c# when stack size is
the issue, but may not have great effect in SDL..I'm not sure]
5) Export data to a file, them perform operations on that file [such as #2], or
use it as a "save point", so you can calculate iterations 1-6 and dump to file,
then on a second run, start the loop at 6 and go to N.
6) Some combination of 1-5, or all of them.

Which of these may be better for you depends on how pov allocates memory for a
given task/object.

Sadly, I am not yet familiar enough with pov memory allocation to provide a
better answer or narrow my suggestions down, and thus must defer to one of our
many other fine members here for such information.

Hopefully you at least have some useful ideas now.

Ian

Post a reply to this message

Terabyte wrote:

> So my question is: Since Menger Sponges are recursive (in fact it's only one
> single cube, copied millions of times), is there a possibility, to save RAM by
> "telling" Pov-Ray to use the same object over and over again, instead of
> creating different copies of the same cube?

You can provide it as a recursive function and render as isosurface.

See, for example, this thread:

http://news.povray.org/povray.advanced-users/thread/%3Cweb.46e8c494ee0a3a9a54585d60@news.povray.org%3E/?ttop=365989&toff=200

Post a reply to this message

Just another thought, I have some c# code that generates a sierpenski carpet
using IFS (and gives you x,y coords). Maybe you can extrapolate to 3d? Ill send
it if you like. IFS might not give you as clean an object as how you are doing
it now, but it renders pretty deep all at once.

ian

Post a reply to this message

On 8/11/2011 8:40 PM, Terabyte wrote:
> I'm interested in rendering a menger scene, but up until now I'm stuck by at a
> Menger Sponge of level 7.
>
> Level 0 to Level 6 together in one scene so far is no problem (takes 1 Gig of
> RAM, and 1,5 hour to render a 3200x2400 AA 0.3 scene, with shiny floor and
> texture), but at level 7 I keep getting Out Of Memory errors.
>
> So my question is: Since Menger Sponges are recursive (in fact it's only one
> single cube, copied millions of times), is there a possibility, to save RAM by
> "telling" Pov-Ray to use the same object over and over again, instead of
> creating different copies of the same cube?

For a Menger Sponge, each level of recursion increases the number of 
cubes by 20x.  So by level 7 (if level 0 is 1 cube) you would be 
specifying 20^7 cubes or 1.28 billion cubes.  Even though the cubes are 
simple, each one has to be located in 3D space and may even have 
associated texture info etc.

Given the nature of ray tracing, each of these has to be in existence. 
Note that bounding boxes may not need each ray to be tested against each 
object but in any case they are represented as objects in memory.

Even instancing a cube as a mesh will still result in 1.28 billion 
instances as I understand it.

The isosurface approach suggested by Christian may be your only hope.  I 
dn't know about that.

Now, at the deepest level are the cubes still visible ?  If the starting 
cube was 1000 pixels on a side then at level 7 the cubes would be 1000 / 
3^7 = 1000 / 2187 or about half a pixel in size.  I guess you'd get some 
impression of detail given AA.  More so of course at your stated 
resolution of 3200x2400 and if the view is zoomed in somewhat.

Good luck and do post the result at reduced resolution.

Post a reply to this message

Paul Fuller <pgf### [at] optusnetcomau> wrote:
....
> Now, at the deepest level are the cubes still visible ?  If the starting
> cube was 1000 pixels on a side then at level 7 the cubes would be 1000 /
> 3^7 = 1000 / 2187 or about half a pixel in size.  I guess you'd get some
> impression of detail given AA.  More so of course at your stated
> resolution of 3200x2400 and if the view is zoomed in somewhat.
>
> Good luck and do post the result at reduced resolution.

Hi Paul,

Yes, I think you're right. A level 7 Menger Sponge would probably be too
detailed for a normal screen resolution. Even the level 6 sponge is very
detailed, even at 3200x2400 resolution. But it's just for the challenge.

Just look at the tiny, little Level 0 cube in the image.
Look like a pixel error :-)

I posted the image (3200x2400, jpg, 1MB) under
povray.binaries.images, then "Menger Sponge Scene (Level 6 to 0)". Parsing time
was about 10 seconds, render time with reflection and other cubes about 3 hours.

To all: Thanks for your feedback.

Terabyte

PS: I found this on the internet: (This guy is rendering a Level 9! sponge)
http://www.pure-mirage.com/html/Optimized%20Menger%20Sponges.htm
--> What's procedural texturing? Could it help rendering my sponge?

Post a reply to this message

Am 09.11.2011 07:14, schrieb Paul Fuller:

> For a Menger Sponge, each level of recursion increases the number of
> cubes by 20x. So by level 7 (if level 0 is 1 cube) you would be
> specifying 20^7 cubes or 1.28 billion cubes. Even though the cubes are
> simple, each one has to be located in 3D space and may even have
> associated texture info etc.
>
> Given the nature of ray tracing, each of these has to be in existence.
> Note that bounding boxes may not need each ray to be tested against each
> object but in any case they are represented as objects in memory.
>
> Even instancing a cube as a mesh will still result in 1.28 billion
> instances as I understand it.

Indeed; for such a sponge resolution, just the *index* of all the little 
cubelets would require 4.7 GB on a 32-Bit computer (which is alraedy 
more than such a machine can handle), or 9.5 GB on a 64-Bit computer. 
And that doesn't even include a single bit of data per cubelet.

Here's a helpful trick though: Suppose you /do/ build your sponge out of 
meshes instead of boxes - using multiple instances of one single mesh - 
then each cubelet still requires its own overhead, but the actual shape 
of the mesh instances is only stored once. And here's where the fun 
begins: It doesn't matter much how many triangles you use to define the 
cubelet. It doesn't actually need to be a cube at all; for instance, it 
might be interesting to see how a level 6 menger sponge built out of 
octahedra would look like. Or, just for the sake of it, built out of a 
cube with square holes punched through each face, like a level 1 menger 
sponge...

... Oh, wait... :-)


Fun fact: A simple level 4 menger sponge built out of level 4 menger 
sponge mesh instances will require far less memory than your current 
level 6 menger sponge built out of cubes (I'd expect a factor of roughly 
100).

Of course an isosurface solution would require virtually no memory at 
all in comparison, but the formula might be hard to devise, and possibly 
slow to render. Just saying.


(For the sake of completeness, instead of modeling a menger sponge as a 
compound of multiple smaller menger sponges you could also model it as a 
cube with square holes of various size punched through all faces at 
certain places, which would let you get away with less than 16 million 
boxes for a level 7 sponge. However, mind-bogglingly slow render times 
would be guaranteed, as POV-Ray doesn't cope well with CSG objects 
having lots of holes, so it's not a real option.)

Post a reply to this message

clipka wrote:

> Of course an isosurface solution would require virtually no memory at 
> all in comparison, but the formula might be hard to devise

The last post in the thread I linked seems to contain a
macro to build the function recursively.

Post a reply to this message

Christian Froeschlin wrote:
> clipka wrote:
> 
>> Of course an isosurface solution would require virtually no memory at 
>> all in comparison, but the formula might be hard to devise
> 
> The last post in the thread I linked seems to contain a
> macro to build the function recursively.

Now that I actually tried it it doesn't work as posted,
although the idea is elegant. Probably can be rescued but
now I just dug up the version of David Wallace from the
Internet archive:

http://web.archive.org/web/20080309103235/http://www-inst.eecs.berkeley.edu/~dtw/pov/misc/_povsrc/iso_menger.pov

Appears to be quite usable at level 7 with todays computers
so there goes the rest of the evening ;)

Post a reply to this message