The morning sun begs me to venture out of my apartment and enjoy the outside world away from the stale air in my tiny apartment. But, itís a weekend, which means itís a good day for some recreational programming. There is no world away from the glow of the monitor and the clacking of the keyboard.
I think Iíll use Java to procedurally generate a new desktop image. Of course I have access to photo editing and 3D rendering software, but what fun is that? I want to do this from the ground up using only core Java. Iíll post each version of the program as it evolves along with its output image of course.
Iím envisioning an infinite labyrinth stretching to the horizon. The plan is to use a space-filling curve. Check out the following 6 paths.
Each path visits the 25 cells making up the grid exactly once. It always enters a cell through 1 wall and it exits through a different wall. There are 6 possible ways to visit a cell for which Iíve named: −, |, r, L, 7, J. Those symbols somewhat resemble the possibilities. Youíll notice that the paths above are named after the way the center cell is traversed. But, not only that, the path as a whole exhibits the same visitation behavior when you consider the boundaries of the grid. For instance, the L grid scaled to 1/5th its size could replace the center cell of the L grid itself. In this way, the paths above are self-similar. In theory, you could substitute cells at smaller-and-smaller scales indefinitely, creating a space-filling curve.
If you look carefully at the (hastily created by copying, scaling and pasting in a paint program) image above, the center cell is of type L, the center 5×5 cluster of cells is of type L, and the entire path itself is of type L. This means that instead of shrinking paths, you could construct an infinitely large version by building outward. No substitutions are required. It just keeps growing.
To represent a path traversing a cell, Iíll create a 3×3 grid. The tiles of those grids will either be solid or empty.
We can start with any type centered about the origin. Then, we build 2 layers around that to replicate the type that we started with. To build the successive layers, we recursively construct them from the 3×3 grids on up. The important thing is that it is always possible to rapidly figure out if a particular cell is solid or empty without actually building out that far. Instead, you keep subdividing the space around the point of interest until you are down to a single cell.
I got Netbeans open and I created a new class.
I banged out some code to crank out an image.
0 hours, 0 minutes, 0 seconds, 359 milliseconds
Yep. Itís all black. My desktop is 1280×1024. To speed up testing, Iíll render images at half that resolution. The array called
pixels will store pixel RGB values in the range from 0.0 (darkest) to 1.0 (lightest). The
saveImage method applies gamma correction during saving. Actually, the color intensity values in
pixels represents the sum of multiple samples.
saveImage also divides by the sample count.
main method computes the time required to generate the image. I am running this on an Intel i7 920 @ 2.67 GHz under 64-bit Vista. But, right now it is a single-threaded application. Only 1/8th of the potential of this machine is being tapped.
I plugged in the formulas for Fractional Brownian Motion. Now, I have something that resembles white marble.
0 hours, 0 minutes, 1 second, 61 milliseconds
Iím thinking: clouds. Hereís a procedurally generated palette. I sampled cloud white and sky blue from a photograph of the sky.
0 hours, 0 minutes, 0 seconds, 530 milliseconds
Putting the 2 together yields something resembling a cloudy sky.
0 hours, 0 minutes, 1 second, 61 milliseconds
I modified the Fractional Brownian Motion methods to accept 3D coordinates as opposed to just a 2D plane. This version requires more memory because Iím storing many more random numbers. If you run this code, add a JVM argument like:
0 hours, 0 minutes, 2 seconds, 122 milliseconds
To verify that my FBM methods really are producing 3D sky, I modified the program to generate 64 slices through a 3D block. Itís almost like frames of a movie. Itís like a changing cloudscape. Since each successive slice resembles the last, Iíd say itís working.
0 hours, 0 minutes, 2 seconds, 371 milliseconds
Next, Iíll tackle the land. Hereís an Earthy palette.
0 hours, 0 minutes, 1 second, 560 milliseconds
Hereís an Earthy texture based on that palette.
0 hours, 0 minutes, 2 seconds, 91 milliseconds
That looks slimy and dismal. I think I need a greener landscape.
Hereís a first attempt at mapping the sky in 3D.
0 hours, 0 minutes, 5 seconds, 600 milliseconds
Finally, the sky is mapped. This test image uses 25 samples per pixel.
0 hours, 0 minutes, 12 seconds, 823 milliseconds
So, thereís our empty world.
0 hours, 0 minutes, 18 seconds, 876 milliseconds
Now, the rendering routine is multithreaded. On this machine, each thread works on 1/8th of the image. Hereís an image with 100 samples per pixel. Youíll notice that there is less noise on the horizon.
0 hours, 0 minutes, 22 seconds, 666 milliseconds
Too bad I canít take advantage of the GPU from core Java.
I plugged in the space-filling curve algorithm discussed in Step 0. Iím using type r as the seed type. I only made one minor modification from what is discussed above. Instead of covering cells with 3×3 representations of the type, Iím using 5×5 representations. That change provides more empty space around the curve.
0 hours, 0 minutes, 0 seconds, 562 milliseconds
Hereís what happens if you map the ground with the space-filling curve (256 samples per pixel). The path needs to be given some elevation.
0 hours, 0 minutes, 29 seconds, 984 milliseconds
This is a first attempt at making the space-filling curve 3D (256 samples per pixel).
0 hours, 2 minutes, 42 seconds, 318 milliseconds
This version tests for intersections against the space-filling curve, the sky and the ground (256 samples per pixel).
0 hours, 3 minutes, 26 seconds, 545 milliseconds
I added an optimization to this version which seems to have reduced the rendering time (256 samples per pixel). Also, now the path is supported by pillars in an attempt to expose more of the ground.
0 hours, 1 minute, 6 seconds, 768 milliseconds
This is a test with the virtual camera oriented differently.
0 hours, 1 minute, 4 seconds, 874 milliseconds
The pillar lengths have been increased in this version.
0 hours, 1 minute, 22 seconds, 338 milliseconds
Hereís a test with ambient occlusion on the ground. Notice that it is darker around the base of the pillars since less ambient light is able to enter as the corner narrows.
0 hours, 1 minute, 0 seconds, 76 milliseconds
In this version, ambient occlusion has also been applied to the labyrinth (256 samples per pixel).
0 hours, 1 minute, 27 seconds, 635 milliseconds
Here is what happens when you apply diffuse shading and shadows.
0 hours, 1 minute, 6 seconds, 827 milliseconds
This version applies 40% ambient occlusion and 60% diffuse lighting and shadows.
0 hours, 1 minute, 44 seconds, 629 milliseconds
The ground texture is reintroduced in this version.
0 hours, 1 minute, 41 seconds, 416 milliseconds
Next, the labyrinth needs a texture, which in turn needs a palette.
0 hours, 0 minutes, 1 second, 513 milliseconds
Thanks to Perlin Noise, here is a procedurally generated marble texture.
0 hours, 0 minutes, 2 seconds, 293 milliseconds
When the marble texture is applied to the labyrinth, we get this.
0 hours, 2 minutes, 21 seconds, 289 milliseconds
In this version, the marble is 25% reflective.
0 hours, 7 minutes, 10 seconds, 700 milliseconds
I rendered the image in Step 29 at 1280×1024 with 400 samples per pixel. It took:
0 hours, 39 minutes, 17 seconds, 488 milliseconds. You can view the image here and you can download the source here. Itís actually a pretty sweet desktop image.
One final experiment: What if it werenít a labyrinth, but rather an Escheresque cityscape composed of an endless staircase? Nah.
0 hours, 9 minutes, 46 seconds, 224 milliseconds
So, I got my new desktop image. Not bad for a few hours of coding.