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(-<inf, .6, .6>, <inf, .6, .6>) 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(<inf, 1, 1>) 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. |
|