Welcome to Fractal Forums

Fractal Math, Chaos Theory & Research => Sierpinski Gasket => Topic started by: twinbee on October 31, 2009, 03:38:45 PM




Title: Revenge of the (half-eaten) menger sponge
Post by: twinbee on October 31, 2009, 03:38:45 PM
Looked around the net - only depth 6 menger sponges seem to exist at most, so I couldn't resist creating a level 7 with over 1.2 billion cubes!

I added a couple of twists too. Here is the full 4 megabyte version (http://www.skytopia.com/project/fractal/new/full/q85/menger2.jpg) (near 4000x4000 !). Below are a couple of previews. I'll be adding some tasty perspective next time.

(http://www.skytopia.com/project/fractal/new/full/q85/menger-city-cut.jpg)

(http://www.skytopia.com/project/fractal/new/full/q50/menger.jpg)


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: David Makin on November 01, 2009, 12:03:14 AM
Granted this isn't as high-resolution and you only get to see part of the sponge in detail, but it does go somewhat more than 6 levels deep:

http://www.youtube.com/user/MakinMagicFractals#p/u/5/YYlpkqPk0i8


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: twinbee on November 01, 2009, 01:53:11 AM
Heh, that is cool - think I saw it before. Gotta be around 20 depth levels I think!

At the moment, rather than using an iterated 'chopping' or 'building' approach to create the object for my menger sponge, it's done entirely through a function. In other words, the function inputs an x,y,z and outputs whether that point is in the set. Not sure how much quicker or slower it is than usual. In theory it should be much slower, because it has to calculate for every pixel. I wonder how much more optimzed the function can be though - could be some shortcuts here and there.

The advantage of course is that the memory used is virtually nil no matter how many iterations are used.

Code:
bool mengerSponge(double x, double y, double z) {

if(x<0 || x>1 || y<0 || y>1 || z<0 || z>1 )     { return 0; } // point is not part of menger sponge

int iterations=8;

double depth=3;

for(int iter=0; iter<iterations; iter++) {
int holex=1;
while(holex<depth) {
int holey=1;
while(holey<depth) {
if(
((x > holex/depth && x< (holex+1) /depth) && (y > holey/depth && y< (holey+1) /depth)) ||
((y > holex/depth && y< (holex+1) /depth) && (z > holey/depth && z< (holey+1) /depth)) ||
((x > holex/depth && x< (holex+1) /depth) && (z > holey/depth && z< (holey+1) /depth))
) { return 0; } // point is not part of menger sponge
holey+=3;
}
holex+=3;
}
depth*=3;
}

return 1; // point is part of menger sponge
}


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: twinbee on November 03, 2009, 10:40:52 PM
Okay it turns out my above function is hopelessly inefficient (it's a miracle I coaxed a giant iteration 7 image out of it). The worst case time complexity is around O( n(9^n) ). Compare that to the one I created below which is O(n). Yep, just a tiny bit faster (!).

The great thing is now, any amount of iterations (even thousands) are trivial to do, and very fast, and eat up next to no memory. I'm in the middle of some giant 3D brot images, but I can't resist a couple more menger sponge renders:

Code:
bool MengerSponge(double x, double y, double z) {
int iterations=7;
if(x<0.0 || x>1 || y<0 || y>1 || z<0 || z>1 )     { return 0; } // Not part of menger sponge
double p=3.0;
for(int m=1; m<iterations; m++) {
double xa = floatmod(x*p, 3);
double ya = floatmod(y*p, 3);
double za = floatmod(z*p, 3);
if(
(xa > 1.0 && xa < 2.0   &&   ya > 1.0 && ya < 2.0) ||
(ya > 1.0 && ya < 2.0   &&   za > 1.0 && za < 2.0) ||
(xa > 1.0 && xa < 2.0   &&   za > 1.0 && za < 2.0)

) {return 0;}  // Not part of menger sponge
p*=3;
}
return 1;  // Is part of menger sponge
}

Full sizes are available here (http://www.skytopia.com/project/fractal/new/full/q85/menger-persp2b.jpg) and here (http://www.skytopia.com/project/fractal/new/full/q85/menger-persp3.jpg) (8000x5000 pixels!). The first one is 9 iterations. No more are needed because the resolution would need to be even larger to contain the tiny holes.

(http://www.skytopia.com/project/fractal/new/q85/menger-persp3-small.jpg)
(http://www.skytopia.com/project/fractal/new/q85/menger-persp2b-small.jpg)


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: cKleinhuis on November 03, 2009, 11:42:06 PM
yeah, a menger castle :D

great one!  :D


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: Dinkydau on November 06, 2009, 02:15:48 PM
Beautiful fractals!


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: twinbee on November 06, 2009, 11:44:32 PM
Thanks both! I'll see if I can work on some stranger variations of the menger with a specially mapped colour surface. Perhaps translucent may look cool.


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: Buddhi on November 21, 2009, 03:55:57 PM
Hi

Daniel White inspired me to render something with logical iteration formula. I made some trials and found some interesting (and very simple) formula:
Code:
for (L = 0; L < N; L++)
{
  double xx = fmod(a * k, 2.0)-1.0;
  double yy = fmod(b * k, 2.0)-1.0;
  double zz = fmod(c * k, 2.0)-1.0;
  if ((xx*xx + yy*yy + zz*zz < 1.03))
  {
     result = 0;
     break;
   }
   k *= 4.0;
   result = 1;
}

(http://www.fractalforums.com/gallery/1/640_21_11_09_3_36_33.jpg)

full size (3200x3200): http://krzysztofmarczak.deviantart.com/art/Fractal-cheese-144292130



Title: Re: Revenge of the (half-eaten) menger sponge
Post by: cKleinhuis on November 21, 2009, 04:00:19 PM
simply awesome !

 :thumbsup1: :thumbsup1:


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: kram1032 on November 21, 2009, 04:09:10 PM
buddhi:
yay it's a menger sphere :D

Really nice stuff :)

twinbee: What ever link I try, all are 404 - not found.... :(


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: David Makin on November 21, 2009, 04:14:41 PM
@Buddhi

That's the most awesome and original fractal I've seen in years !
Now...how to get a distance estimate for it....


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: Buddhi on November 21, 2009, 04:42:25 PM
I haven't used distance estimate. Only binary searching. But I think there is possible to find estimation for this. In formula there is condition:
if ((xx*xx + yy*yy + zz*zz < 1.03))
and I think after last iteration this is distance to nearest spherical surface. I have to try with this.


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: Buddhi on November 21, 2009, 07:27:46 PM
Another view of "menger sphere"

(http://www.fractalforums.com/gallery/1/640_21_11_09_7_25_57.jpg)
http://www.fractalforums.com/gallery/?sa=view;id=1078


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: kram1032 on November 21, 2009, 07:49:33 PM
now I wonder, how effective that would be as a fractal antenna xD
It's great :D

Is it enclosed from outside or can you see inward? (in the first image, I can see a hole which seems to lead outside..)

Any idea of the fractal dimension? Is it just like for the Mengersponge?


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: Buddhi on November 21, 2009, 07:59:34 PM
There is no outside. It is an infinite construction. Last picture it's a view from front of some big sphere into smaller spheres. Camera is inside this sphere.

Is it just like for the Mengersponge?
Yes, it is something like Menger Sponge. Algorithm is nearly the same but for limits I used spheres instead of cubes.


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: twinbee on November 25, 2009, 11:44:58 AM
Hi kram1032, I corrected the file names.

Buddhi, that's fantastic - looks so wooden and complex. Kind of structure/texture that could easily in the real world.


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: kram1032 on November 25, 2009, 10:01:47 PM
ah, nice twinbee :D

Buddhi: Now I wonder about a castle-version of your Menger sphere :)

Also twinbee: What about both a multiperspective (say, three points of infinity (PoI) for three axes) or an inverse perspective (PoI lies on the image plane) or maybe a "central" perspective (PoI in the center of the Menger-sponge...)

Afaik, a lot of paintings used that.

The PoI is the point, where all infinite straight lines meet due to perspective distortion.

Could give interesting twists on the shape :)

Or, also possible maybe, what's about an hyperbolic Menger-sponge, where rather than 27 cubes form a bigger cube, say 84 do so... - I'm not sure right now how that looks like but my idea is, that more cubes can touch in hyperbolic space while still tesselating the plane. basically you could do the same as in euclidean, but instead of letting 1 corner of a cube letting touch 6 other cubes' corners, you could change that to a higher number...
(probably, though, the 2D-case should be done first, before investigating in the 3D-case...)

Oh, and something probably way simpler: Could you please upload pngs or something? especially the colourful castle suffers a lot from the jpeg-compression :)


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: JosLeys on November 25, 2009, 11:12:18 PM
For an idea on what you would see if you are inside a 3D tiling of hyperbolic cubes, look here :
http://www.josleys.com/htmlgalleries/flash/Cube%20hyperbolique.html


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: jehovajah on November 26, 2009, 02:26:23 AM
could rf used as a visualisation of structured space say in a crystal lattice, or a planetary/ gravitational / molecular system.


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: Buddhi on November 29, 2009, 07:03:48 PM
I found incredible 1k intro on scene.org:
http://scene.org/file.php?file=/parties/2009/breakpoint09/in4k/tbc_-_untraceable_partyhack.zip&fileinfo

It consists real-time 3D sierpinski triangle, menger sponge and some other fractals (and nice music in background). Size of exe file is ONLY 1k!!!


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: twinbee on January 04, 2010, 04:59:13 PM
I don't know. I leave the Mandelbulb alone for 5 minutes, and look what it's gone and done to my precious Menger sponge!!  :police: Big 2500x2500 version available here (http://www.skytopia.com/project/fractal/new/MengerEat.jpg):

(http://www.skytopia.com/project/fractal/new/MengerEatS.jpg)

For the curious, this is a simple boolean "AND" to the Menger sponge and Mandelbulb. In other words, each point has to be part of both sets for it to be part of the new hybrid set.

*****EDIT*****
kram1032, those perspective tricks sound good, and probably not too tricky to implement (I've sometimes thought about inverse perspective). I'll see what I can do.

Here's a full PNG of the earlier castle menger sponge btw:
http://www.skytopia.com/project/fractal/new/menger-persp2b.png


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: Buddhi on January 04, 2010, 05:40:59 PM
Fantastic idea and render!!! I think it is impossible to render this with DE :-)


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: kram1032 on January 04, 2010, 06:49:14 PM
heh...

nice half-molten Menger :)
It had some thermite  (http://en.wikipedia.org/wiki/Thermite)for dinner, right?

Already curious about twisted perspectives :)


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: knighty on September 17, 2010, 09:28:14 PM
Sorry for bumping this old thread. I'm working on aperiodic tilings thanks to tomkh's thread (http://www.fractalforums.com/new-theories-and-research/procedural-aperiodic-fractals/) and just think it's related to this dicussion. My objective is to find DE estimate for aperiodic 3D tilings. On the way I remembred this thread and am having answers to a some questions:
Here are the DE for twinbee's Menger sponge and Buddhi's sphere sponge:
Code:
//Derived from twinbee's algorithm
MengerSponge3(x, y, z) {//by recursively digging a box
   x=x*0.5+0.5;y=y*0.5+0.5;z=z*0.5+0.5;//center it by changing position and scale
   
   xx=abs(x-0.5)-0.5;yy=abs(y-0.5)-0.5;zz=abs(z-0.5)-0.5;
   d1=max(xx,max(yy,zz));//distance to the box
   d=d1;//current computed distance
   p=1;
   for(m=1; m<MI ; m++) {

      xa = 3*x*p % 3;
      ya = 3*y*p % 3;
      za = 3*z*p % 3;
      p*=3;

      //we can also translate/rotate (xa,ya,za) without affecting the DE estimate

      xx=0.5-abs(xa-1.5);yy=0.5-abs(ya-1.5);zz=0.5-abs(za-1.5);
      d1=min(max(xx,zz),min(max(xx,yy),max(yy,zz)))/p;//distance inside the 3 axis aligned square tubes
     
      d=max(d,d1);//intersection
   }
   return d*2; //the distance estimate. The "*2" is because of the scaling we did at the begining of the function
}
Code:
//derived from Buddhi's algorithm
SphereSponge3(x, y, z) {//by recursively digging space
   //Same as for the Menger sponge but with spheres
   x+=1;y+=1;z+=1;
   intrad=param1;
   scl=3;mod=4;
   a=x;b=y;c=z;k=2;
   d=-100;
   for (L = 0; L < MI ; L++)
   {
     xx = a * k % mod - 0.5*mod;
     yy = b * k % mod - 0.5*mod;
     zz = c * k % mod - 0.5*mod;
     r2=xx*xx + yy*yy + zz*zz;
     d1=(intrad-sqrt(r2))/k;//distance to the edge of the sphere (positive inside)
     d=max(d,d1);//intersect
     
     k *= scl;
   }
   return d;// distance estimate
}
(needs some optimizations :embarrass: but it is already quite fast O0)
It's possible to use the same technique to other figures (fractals and tilings).

Fantastic idea and render!!! I think it is impossible to render this with DE :-)
It's actually possible (and well known): the intersection is obtained by taking the maximum DE of the two objects. That's what I am using in the codes above. union can also be obtained by taking the minimum DE instead.

BTW: There is another well known trick In distance fied rendering: Blending. Just take a linear (or higher order) interpolation of the DE of the two objects.


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: visual.bermarte on October 23, 2010, 04:24:31 PM
min(DEbox,DEbulb)TEST:
(http://fc09.deviantart.net/fs70/f/2010/296/2/5/zz_2_by_bermarte-d31bxts.png)

(http://fc00.deviantart.net/fs70/f/2010/296/d/0/join_by_bermarte-d31bu5y.jpg)


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: DarkBeam on October 09, 2013, 05:41:39 PM
Found an error in the Fragmentarium implement of NewMenger. :D
The DE is buggy currently; the sponge tends to disappear. :'(
If you replace...

Code:
float DE(vec3 p)
{
p=p*0.5+vec3(0.5);
vec3 pp= abs(p-0.5)-0.5;
float k=1.0;
float d1 = max(pp.x,max(pp.y,pp.z));
float d=d1;
for (int i = 0; i < Iterations ; i++)
{
vec3 pa = mod(3.0*p*k, 3.0);
k *= Scale;

pp = 0.5-abs(pa-1.5)+Offset;
             pp*=rot;
d1=min(max(pp.x,pp.z),min(max(pp.x,pp.y),max(pp.y,pp.z)))/k;//distance inside the 3 axis aligned square tubes
d=max(d,d1);
if (i<ColorIterations) orbitTrap = min(orbitTrap, abs(vec4(pp,dot(pp,pp))));

}

// Use this to crop to a sphere:
//  float e = clamp(length(z)-2.0, 0.0,100.0);
//  return max(d,e);// distance estimate
return d;
}

with...

Code:
float DE(vec3 p)
{
p=p*0.5+vec3(0.5);
vec3 pp= abs(p-0.5)-0.5;
float k=1.0;
float d1 = max(pp.x,max(pp.y,pp.z));
float d=d1;
for (int i = 0; i < Iterations ; i++)
{
vec3 pa = mod(3.0*p*k, 3.0);

pp = 0.5-abs(pa-1.5)+Offset;
             pp*=rot;
d1= (1/k) * min(max(pp.x,pp.z),min(max(pp.x,pp.y),max(pp.y,pp.z)))/k;//distance inside the 3 axis aligned square tubes
            
d=max(d,d1); k *= Scale;
if (i<ColorIterations) orbitTrap = min(orbitTrap, abs(vec4(pp,dot(pp,pp))));

}

// Use this to crop to a sphere:
//  float e = clamp(length(z)-2.0, 0.0,100.0);
//  return max(d,e);// distance estimate
return d;
}

Because d1 must be properly scaled (multiplied by 1/k). Now it renders perfectly! :police: :police: :police:


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: Syntopia on October 13, 2013, 11:46:24 PM
Hi DarkBeam,

The code you posted produce much worse results than the original code on my computer. Are you sure you didn't change something else? Can you post the full fragment?


Title: Re: Revenge of the (half-eaten) menger sponge
Post by: DarkBeam on October 15, 2013, 12:43:58 PM
 :embarrass: me = stuuuupid!!!!!!!!

d1= (1/k) * min(max(pp.x,pp.z),min(max(pp.x,pp.y),max(pp.y,pp.z)))/k;//distance inside the 3 axis aligned square tubes

Is of course wrong because I divided twice!
It should be

d1= (1/k) * min(max(pp.x,pp.z),min(max(pp.x,pp.y),max(pp.y,pp.z)));//distance inside the 3 axis aligned square tubes

sorry but as weird as it sounds; I can not say if it's correct or send the script because my drivers fail to run now :fiery: - btw it works great into Mandelbulb3D :beer: