Menger Sponge

The Menger Sponge is a fairly simple three dimensional fractal. The basic idea is that you have a cube, you split it into a 3x3x3 lattice of cubes, and take away the cubes in the centre of each face, and the centre of the cube. You then take each smaller cube, and do exactly the same thing.

Each time you do this you get to another “iteration” of the Menger Sponge, and you get a bunch of even smaller holes appearing on each face.

There’s a couple of ways of rendering this in a raytracer. The simplest of course is to actually build it out of little cubes. The algorithm for this really couldn’t be simpler and looks like this…

BuildMenger(Vector3 min, Vector3 max, int iterations)
{
 // If I've recursed enough, output a cube
 if (iterations==0)
  MakeCube(min, max);

 for (z=0; z<3; z++)
  for (y=0; y<3; y++)
   for (x=0; x<3; x++)
   {
    int centres = (z==1?1:0) + (y==1?1:0) + (X==1?1:0);
    if (centres<=1)
    {
     // Recursively build sponge structure
     BuildMenger(
      Vector3(min.x + x*(max.x-min.x)/3,
       min.y + y*(max.y-min.y)/3,
       min.z + z*(max.z-min.z)/3),
      Vector3(min.x + (x+1)*(max.x-min.x)/3,
       min.x + (x+1)*(max.x-min.x)/3,
       min.x + (x+1)*(max.x-min.x)/3),
      iterations-1);
    }
   }
}

So that’s your simple code for building a sponge. The only bit that probably needs a tincey bit of explanation is int centres = (z==1.... This is a simple mathematical way of describing which cubes within the lattice are going to be removed. We’re only on the edge of the lattice if we’re in the middle of 1 or less axes. If we’re in the middle of two axes then we must be in the middle of a face of the cube. If we’re in the middle of three axes then we’re at the centre of the cube.

The output from this is physically not too bad at all…

But there is a problem. Each time we recurse we generate new cubes for 20 of the cubes in this iteration. That means the number of cubes grows with order O(20^x), in layman’s terms the number of cubes is 20^x where x is the number of iterations.

Iterations Cubes
0 1
1 20
2 400
3 8 000
4 160 000
5 3 200 000
6 64 000 000
7 1 280 000 000
14 1 638 400 000 000 000 000

Now my raytracer can handle the fourth iteration with 160000 cubes, but it’s not hugely fast at rendering this. Actually, under a minute isn’t bad, but compared to iteration 0 at 1.1 seconds it’s not particularly great. The XML to describe this scene also gets pretty mad. Each cube has a description of about 600 bytes. That means the scene description is now taking 80MB! Iteration 5 is going to be 1.6GB…

So we need a better way of raytracing the Menger Sponge if we want to get up to the 5th or 6th iteration, let alone the 14th. And preferably this better algorithm won’t store everything in memory.

In fact, with a raytracer it’s relatively simple to do this type of intersection test recursively. Imagine a ray hitting the outer cube. If the hit point is one of the holes we step through the hole and check the cube behind. When we find a solid cube, we recurse. i.e. we zoom into that cube and do the test again. If the second hit point is in one of the holes we step through the hole and check the smaller cube behind. When we find a solid smaller cube, we zoom into the smaller cube we recurse; and do the test again.

The pseudo-code for this is relatively straightforwards..

if (ray hits outer cube)
{
 RecursiveIntersectCube();
}

RecursiveIntersectCube(iterations)
{
 if (iterations==0)
  return intersection point;

 while (x, y and z within the cube)
 {
  int x, y, z = position of minicube I hit;

  if (IsSolid(x,y,z))
  {
   // hit a solid cell, see if I hit it's sub cell, if so return hit point
   if (RecursiveIntersectCube(x,y,z,iterations-1))
   {
    return true;
   }
   else
   {
    // not solid, so I can't of hit it, find next cell
    IntersectBackOfCube(ray, x, y, z)

    x, y, z = increment based on which backface I hit
   }
 }
}

While the pseudo is easy, the real code is a fiddly pain in the arse…

Menger sponge early render

Menger sponge early render

Menger sponge early render

Menger sponge failing at next iteration

Eventually I got the main intersection tests working.. and then I realised it still didn’t work if the ray started inside the outer cube. This doesn’t seem like a big deal until you realise that all shadow and reflection vectors start inside the outer cube… sigh…

After a further 3 days of scraping time together I finally fixed that, and started getting some decent results. Of course, the only real way to test this is to render the recursive primitive code and compare the result to the bruteforce sponge described above.

And here we go…

Menger sponge brute force

Brute force Menger sponge raytrace

Menger sponge recursive algorithm

Menger sponge recursive primitive raytrace

So back to where I started, but this is now significantly faster to raytrace. The iteration 4 cube I did the bruteforce way is now raytracing in 1.5-2 seconds. Even at iteration 8 it’s only gone up to 3.5-4 seconds.

So now I can switch global lighting back on…

Menger sponge and global light

Menger sponge with multi-sampled global lighting

And finally, fluffed up with some Depth of field…

8th iteration menger sponge

Menger sponge 8th iteration raytraced with depth of field

You may also like...

2 Responses

  1. Sam Swain says:

    They are a pain in the arse aren’t they. My procedural Menger Sponge in action:
    https://plus.google.com/photos/101847136544348139473/albums/5888338227291925585/5899477963081729058?authkey=CJ-flerK0Z-Qag&pid=5899477963081729058&oid=101847136544348139473
    Here, detail is added as you approach a cube by re-evaluating the previous instance at a higher detail level. It runs out of (geometry) memory at the max level shown if you move around much. :)

  2. Dom Penfold says:

    Ahhh. I can see these images. Very nice! You’ve reminded me that I need to integrate the menger cube primitive into wooscript. So what’s your geometry limit? Some of the screenies reminded me a bit of those early totality shots.

Leave a Reply

Your email address will not be published. Required fields are marked *

Spam Protection *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>