Author Message
FeepingCreature

Joined: 24 Aug 2007
Posts: 3

Posted: Tue May 05, 2009 5:00 am    Post subject: Menger Sponge: An Exercise in Optimization

 Code: camera(<0.48, 0.35, 0.1>, <0, .36, 0.12>, y, fov(60), iters(1 cont), depth(5)   mat(diffuse(checker)) plane(y, 0)   mat(ambient(#abc)) plane(-y, -100)   set("fbox") box(-.5, .5)   setMacro("antimenger", object obj, object root, vec a, vec b, vec c)     boxbound(-, ) scale(1/3) group(       root       translate(-a -b) obj       translate( a -b) obj       translate(-a +b) obj       translate( a +b) obj       translate(-a) obj       translate(-b) obj       translate( a) obj       translate( b) obj     )   set("root") scale() fbox   setMacro("mkmenger", object obj) antimenger(obj, root, y, z, x)   set("antimenger_obj_x") forward_scale(mkmenger(mkmenger(mkmenger(mkmenger(mkmenger(mkmenger(nothing)))))))   set("antimenger_obj_y") rotate(z, 90) antimenger_obj_x   set("antimenger_obj_z") rotate(y, 90) antimenger_obj_x   // translate(<0, .5, 0>) antimenger_obj_x   translate(<0, 0.5, 0>) boxbound(-.5, .5) (fbox and minus (antimenger_obj_x or antimenger_obj_y or antimenger_obj_z)) )

This is the Menger Sponge at depth 5. Due to the insane amount of boxes involved, it only renders at 12Krps on my quadcore box, but that is already a step up from the 6Krps it had before I wrote forward_scale.

Forward_scale is a very specific optimization and as such, not part of the normal optimization framework. What it does is: it takes a hierarchy of box bounds, scales and translates and traverses it, accumulating a transformation matrix as it goes. When it reaches a leaf node (Box or NullObject) or a BoxBound, it applies the matrix to its corner points. That way, large amounts of unneeded transformations could be "flattened", so to speak, practically doubling performance.

In the code above, you can see another trick. Generating a menger sponge usually requires a rising complexity of *20 per depth level.

However, if we turn the problem on its head, and try to generate the boxes we'd need to _cut out_ of a box to get the menger sponge, and furthermore (since the sponge is symmetric) limit ourselves to the X axis, complexity (as can be seen above) only rises with *8 per level.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMT - 6 Hours Page 1 of 1

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum