Project Labyrinth

Step 0

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.

−

|

r




L

7

J

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.

−

|

r

L

7

J

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.

Step 1

I got Netbeans open and I created a new class.

public class Main {

  public static void main(String[] args) {
  }

}

Step 2

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.

The 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.

import java.awt.image.*;
import javax.imageio.*;
import java.io.*;

public class Main {

  public static final int SQRT_SAMPLES = 1;
  public static final int INVERSE_SAMPLES = 1 / (SQRT_SAMPLES * SQRT_SAMPLES);

  public static final int WIDTH = 640;
  public static final int HEIGHT = 512;
  public static final String IMAGE_TYPE = "png";
  public static final String OUTPUT_FILE = "output." + IMAGE_TYPE;

  public static final int RED = 0;
  public static final int GREEN = 1;
  public static final int BLUE = 2;

  public static final double GAMMA = 2.2;
  public static final double INVERSE_GAMMA = 1.0 / GAMMA;

  public static final long SECOND_MILLIS = 1000L;
  public static final long MINUTE_MILLIS = 60 * SECOND_MILLIS;
  public static final long HOUR_MILLIS = 60 * MINUTE_MILLIS;

  private double[][][] pixels = new double[HEIGHT][WIDTH][3];

  private void launch() throws Throwable {

    saveImage();

  }

  private void saveImage() throws Throwable {
    int[] data = new int[WIDTH * HEIGHT];

    for(int y = 0, k = 0; y < HEIGHT; y++) {
      for(int x = 0; x < WIDTH; x++, k++) {
        int value = 0xFF;
        for(int i = 0; i < 3; i++) {
          int intensity = (int)Math.round(255
              * Math.pow(pixels[y][x][i] * INVERSE_SAMPLES, INVERSE_GAMMA));
          if (intensity < 0) {
            intensity = 0;
          } else if (intensity > 255) {
            intensity = 255;
          }
          value <<= 8;
          value |= intensity;
        }
        data[k] = value;
      }
    }

    BufferedImage image = new BufferedImage(
        WIDTH, HEIGHT, BufferedImage.TYPE_INT_ARGB_PRE);
    image.setRGB(0, 0, WIDTH, HEIGHT, data, 0, WIDTH);
    ImageIO.write(image, IMAGE_TYPE, new File(OUTPUT_FILE));
  }

  public static void main(String... args) throws Throwable {
    long startTime = System.currentTimeMillis();

    Main main = new Main();
    main.launch();

    long interval = System.currentTimeMillis() - startTime;
    long hours = interval / HOUR_MILLIS;
    interval %= HOUR_MILLIS;
    long minutes = interval / MINUTE_MILLIS;
    interval %= MINUTE_MILLIS;
    long seconds = interval / SECOND_MILLIS;
    interval %= SECOND_MILLIS;
    System.out.format("%d hour%s, %d minute%s, %d second%s, %d millisecond%s%n",
        hours, hours == 1 ? "" : "s",
        minutes, minutes == 1 ? "" : "s",
        seconds, seconds == 1 ? "" : "s",
        interval, interval == 1 ? "" : "s");
  }

}

Step 3

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
source

Step 4

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
source

Step 5

Putting the 2 together yields something resembling a cloudy sky.


0 hours, 0 minutes, 1 second, 61 milliseconds
source

Step 6

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: -Xmx1024M.


0 hours, 0 minutes, 2 seconds, 122 milliseconds
source

Step 7

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
source

Step 8

Next, I’ll tackle the land. Here’s an Earthy palette.


0 hours, 0 minutes, 1 second, 560 milliseconds
source

Step 9

Here’s an Earthy texture based on that palette.


0 hours, 0 minutes, 2 seconds, 91 milliseconds
source

That looks slimy and dismal. I think I need a greener landscape.

Step 10

Here’s a first attempt at mapping the sky in 3D.


0 hours, 0 minutes, 5 seconds, 600 milliseconds
source

Step 11

Finally, the sky is mapped. This test image uses 25 samples per pixel.


0 hours, 0 minutes, 12 seconds, 823 milliseconds
source

Step 12

So, there’s our empty world.


0 hours, 0 minutes, 18 seconds, 876 milliseconds
source

Step 13

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
source

Too bad I can’t take advantage of the GPU from core Java.

Step 14

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
source

Step 15

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
source

Step 16

This is a first attempt at making the space-filling curve 3D (256 samples per pixel).


0 hours, 2 minutes, 42 seconds, 318 milliseconds
source

Step 17

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
source

Step 18

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
source

Step 19

This is a test with the virtual camera oriented differently.


0 hours, 1 minute, 4 seconds, 874 milliseconds
source

Step 20

The pillar lengths have been increased in this version.


0 hours, 1 minute, 22 seconds, 338 milliseconds
source

Step 21

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
source

Step 22

In this version, ambient occlusion has also been applied to the labyrinth (256 samples per pixel).


0 hours, 1 minute, 27 seconds, 635 milliseconds
source

Step 23

Here is what happens when you apply diffuse shading and shadows.


0 hours, 1 minute, 6 seconds, 827 milliseconds
source

Step 24

This version applies 40% ambient occlusion and 60% diffuse lighting and shadows.


0 hours, 1 minute, 44 seconds, 629 milliseconds
source

Step 25

The ground texture is reintroduced in this version.


0 hours, 1 minute, 41 seconds, 416 milliseconds
source

Step 26

Next, the labyrinth needs a texture, which in turn needs a palette.


0 hours, 0 minutes, 1 second, 513 milliseconds
source

Step 27

Thanks to Perlin Noise, here is a procedurally generated marble texture.


0 hours, 0 minutes, 2 seconds, 293 milliseconds
source

Step 28

When the marble texture is applied to the labyrinth, we get this.


0 hours, 2 minutes, 21 seconds, 289 milliseconds
source

Step 29

In this version, the marble is 25% reflective.


0 hours, 7 minutes, 10 seconds, 700 milliseconds
source

Step 30

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.

Step 31

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
source

Conclusion

So, I got my new desktop image. Not bad for a few hours of coding.

2010.04.03