FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Menger Sponge: An Exercise in Optimization

 
Post new topic   Reply to topic     Forum Index -> Stacy
View previous topic :: View next topic  
Author Message
FeepingCreature



Joined: 24 Aug 2007
Posts: 3

PostPosted: Tue May 05, 2009 5:00 am    Post subject: Menger Sponge: An Exercise in Optimization Reply with quote



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.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic     Forum Index -> Stacy All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
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


Powered by phpBB © 2001, 2005 phpBB Group