Title: More efficient generation of Mandelbulbs in voxel environments Post by: Mator on February 09, 2014, 02:25:01 AM Hi there!
You may have seen my introduction topic, if not you can check that out here (http://www.fractalforums.com/meet-and-greet/mator/). I currently have a program written in javascript which generates Menger Sponges and Mandelbulbs in Minecraft, a voxel-based game. This script currently generates these objects while the game/server is running in real-time. I'm eventually going to work my way up to generating other fractals as well. Yesterday I optimized the Menger Sponge generation code by using a recursive function with some cleverly placed continue;'s, so as to make generation more efficient. After this optimization the script could generate an 81x81x81 (level 4) Menger Sponge in under 3 seconds. I felt pretty good about this, as I had come up with the generation code and math all by myself (and it was a great improvement over giant mess of an if statement I was using previously). So now I'm trying to optimize my Mandelbulb generation code. I'd like to be able to tell if a block isn't going to reach the cutoff value of 1024 before going through all 21 iterations of applying the vector formula and all that jazz, but I'm not sure how to do this. I'm pretty certain I should be able to tell by using spherical coordinates to exclude all locations in a certain range, but I'm not entirely certain how to do this safely without accidentally clipping the Mandelbulb in some way. Perhaps I could just shift the origin to the center of the Mandelbulb and close out of the loop if r <= some value? r being the radius in spherical coordiantes: r = sqrt(x^2 + y^2 + z^2)? Edit: Implemented this, I estimate a 16% reduction in execution time. I've now managed to generate 150x150x150 Mandelbulbs. Pretty huge! (295259 blocks) I'd still like to optimize things some more if possible, suggestions are welcome! :) (code updated) Edit 2: I've been thinking a bit more about optimization of Mandelbulb generation. My previous optimization only skipped 16% of the empty blocks. I think, by defining a more complex shape than a sphere using spherical coordinates, I can skip a larger percentage of the empty blocks and optimize things further. I expect that I can skip more like 60% of the air blocks. I also realize that by using these min/max radius values I'm causing the generation to lose some generality; viz., changing the formulas could lead to clipping. I might be able to find a way to use the formulas to generate the min/max radius values if I can identify the theta/phi location of the minimum/maximum radius blocks generally. Until then I'll probably just have a secondary mandelbulb generator which won't use these values. Code: // set global variables Here's a few pictures of some of the fractals I've generated so far. :) (http://i.imgur.com/GGQAKRGl.png) (http://i.imgur.com/jMtdOV3l.png) (http://i.imgur.com/xEIZy6ql.png) (http://i.imgur.com/vLzbLbml.png) (http://i.imgur.com/fpSfoP7l.png) (http://i.imgur.com/CUmOyxYl.png) (http://i.imgur.com/0QcMXyhl.png) (http://i.imgur.com/BMTfMDYl.png) (http://i.imgur.com/E7zOx0tl.png) (http://i.imgur.com/NYptVbFl.png) Title: Re: More efficient generation of Mandelbulbs in voxel environments Post by: Mator on February 10, 2014, 03:01:24 AM Sorry for the double post, but I feel this deserves a separate post. In looking into Mandelbulb generation efficiency I've continued to learn more about how they operate. Essentially, the closer you get to the center of the Mandelbulb the more "chaotic" things become. I've found that the first 2 iterations can't yield a value greater than my cutoff of 1024, and that the third iteration accounts for 33.176% of the volume of the cube. successive iterations account for smaller and smaller amounts of volume. Iterations proceed from the border of the cube inward. e.g. (http://i.imgur.com/4yOM3tM.png) (http://imgur.com/4yOM3tM) gray = iteration 3 (http://i.imgur.com/mftQpPy.png) (http://imgur.com/mftQpPy) black = iteration 4 (http://i.imgur.com/Z19KE3n.png) (http://imgur.com/Z19KE3n) red = iteration 5 (http://i.imgur.com/durIhJS.png) (http://imgur.com/durIhJS) orange = iteration 6 (http://i.imgur.com/yrg44OA.png) (http://imgur.com/yrg44OA) yellow = iteration 7 Like peeling back layers of an onion! :o (This is with a 100x100x100 Mandelbulb in Minecraft with my specified settings, so doesn't apply generally.) Code: the third iteration yields using these data I've learned that the majority of the execution time is being spent on the interior of the Mandelbulb where all 20 iterations are being used up without exceeding the cutoff value. Using a 100x100x100 Mandelbulb I roughly calculated the minimum radius at 100 different theta-phi ranges in the Mandelbulb to range from 0.32*d to 0.37*d (d being the length of a side of the cube containing the Mandelbulb). Storing these values in an array before execution will allow me to cut down execution time even more than I previously had. I'll perform some tests to see how much time this actually saves, but this should be nice for basic Mandelbulb generation in Minecraft. |