Posts In: Algorithmic Art

Terraced Multifractals

Yes, it's official, I'm now severely addicted to HLSL. The raw power that it opens up for Project: A New Reality is simply mind-blowing. Experimentation with all sorts of random ideas has led to some pretty cool-looking terrains, though I'm going to spare the blog from any further screenshot explosions until I have something really draw-dropping.

Here's an interesting example of a neat heightmap shader. The algorithm is as follows:

  1. Generate a Perlin Multifractal [1]
  2. Generate a Perlin Multifractal [2]
  3. Reduce the bit depth of (1) by using the function y = a * floor(y/a), where a is the number of discrete levels to allow [3]
  4. Generate a final heightmap by blending [1] and [3] with [2] as the blending function

Basically, that's a complicated way of saying take a heightmap, force it into discrete levels, then blend it back on itself with another fractal function.  This way, natural-looking terraces appear but blend smoothly back into the terrain.

This example heightmap is a little too aggressive with the terraces, but that can, of course, be easily modified by fooling with the blending function.

A Long Way

I've sure come a long way in one week. Again, I think the picture speaks for itself.

Everything written from scratch in XNA, including shaders. Last week, I didn't even know what a pixel shader or index buffer was.

Multifractals: Beautiful Terrains

Here it is...a rendering of a terrain using a multifractal heightmap. I think the beauty of the terrain speaks for itself!

Notice the juxtaposition of the extremely flat region near the camera with the mountains in the background. Such extreme features can only happen in multifractals!

Multifractals: Great Success!

In a rather old textbook I read recently (Texturing and Modeling: A Procedural Approach; though note that I actually have the 1991 edition), the author mentioned briefly at the end of the book a type of fractal called the multifractal.  The idea of a multifractal is to actually vary the fractal dimension of the fractal at each point based on, guess what, another fractal map!  In a sense, it adds another level of recursion within the fractal.

So why should we care? Well, if perlin noise makes good terrains, multifractal perlin noise makes them 100x better!  The explanation for it is simple.  In real terrain, we see features like mountains, but we also see features like plains.  Mountains have a high fractal dimension, while plains have a low fractal dimension.  Perlin noise, in and of itself, has a relatively constant fractal dimension.  Multifractal noise doesn't.  For this reason, it serves much better for the purpose of generating terrains!

Here's a sample multifractal perlin noise heightmap generated with a home-brewed HLSL shader:

Notice that, in comparison to previous heightmaps, this terrain is far more varied - we can clearly see mountainous features as well as low features.

Perlin Noise Shader

I did it!!

After hours and hours of reading tutorials on HLSL coding, I finally managed to write a perlin noise shader. The result? Unbelievable speed. At least 100x faster than the CPU-based implementation I coded a few months ago. It can easily display a new 512 by 512 heightmap at 60 FPS. Yes, that's 60 unique heightmaps in one second.

With this kind of raw power now available to me for procedural content generation, I know that great things lie ahead in terms of my work with virtual worlds.

For reference (since I lost the old one and had to rewrite from scratch), here's the noise function I used:

float Noise2D(float x,float y)
{
float a = acos(cos(((x+SEED*9939.0134)*(x+546.1976)+1)/(y*(y+48.9995)+149.7913)) + sin(x+y/71.0013))/PI;
float b = sin(a*10000+SEED) + 1;
return b*.5;
}

QuadTree CLOD Engine

Recently I've gotten detoured once more from algorithmic composition by Microsoft XNA, the first 3D engine I've found that I really, really feel comfortable with.  Unlike the previous one, it won't do much of the work for me - no easy bloom/HDR, no easy model management.  But it DOES expose powerful core functionality without having to jump through all the complicated hoops of D3D in c++.

In developing a terrain engine from scratch for my work in algorithmic world synthesis, I've begun testing different continuous level-of-detail (CLOD) systems.  The easiest and most obvious CLOD system that comes to mind is quadtree-based terrain.

My initial quadtree CLOD engine is working pretty well, and can cut polys by 10 to 100 times, making decent framerates possible even with 1024x1024 heightmaps.  Some problems with the quadtree engine:

  • As with most CLOD engines, tiles experience tearing when they are adjacent to tiles of lower or higher detail; many fixes are known, but I have yet to implement one
  • The quadtree structure is pretty huge (considering the recursion), I'm not sure just how much memory it takes up but I'm concerned that it may be too much
  • Lots of overhead because of recursive processing
  • Terrain must be a square with 2^n+1 vertices per side (perfect power of two plus one)

I'm thinking that some of the processing could be done in a shader to speed things up.  If I can wrap my head around a few more HLSL tutorials, I may be able to try such a technique in the near future.

For now, a simple screenshot:

An Original, Realistic Algorithm for Terrain Erosion

February 23, 2010 Algorithmic Art 0 Comments

Yes, another non-music digression. I can't stand not to write about this though, considering the fact that I've had a serious breakthrough today with a new algorithm.

Here's the problem: erosion algorithms tend to produce a sort of homogeneous soup of terrain without recreating some of the more true-to-life effects such as fractal coastlines and such.  The solution? A terrain density map.  As far as I know, this is a completely original algorithm.  I've seen nothing like it in the literature, so I'm quite excited about having invented it.  The initial test runs also produced exciting results!

Here's the basic concept: real terrains are not homogeneous.  Not all dirt is created equal. So, along with a 2-dimensional array representing the heightmap of a terrain, we should also create an equally-sized 2-dimensional array representing the density (or integrity, if the term is preferred) of the terrain at each given point. The density array can be filled with a low-octave perlin noise function (I found two to three octaves to give optimal results, with a persistence of between 1.5 and 2).

Now, we perform an erosion algorithm as usual, except that we use the density of the terrain at each point as the threshold value for erosion. That is, if the amount of potential erosion at a point is less than the density of the terrain at that point, then the point will resist erosion. Ideally, this algorithm erodes terrain in a more coherent, less uniform way than typical thermal erosion algorithms. For example, coasts display some fractal dimension now since some areas of the terrain erode more easily than others.

A sample heightmap using the new algorithm:

The difference is most notable around the rivers, where the coasts clearly display some fractal coherence absent in thermal erosion algorithms. Notice that "noise" of the coastlines is clearly more coherent than single-octave noise, thanks to the perlin-based density map.

I am still trying to work out how to make the features appear larger (that is, make the coast even more jagged), since the heightmap, although nice, isn't drastically different from previous ones. I am quite confident, however, that there's a lot of potential in this new density erosion algorithm. Who knows, maybe this will be the future choice algorithm for procedural terrain erosion!

Techniques for Heightmap Synthesis: II

February 14, 2010 Algorithmic Art 0 Comments

I have made a great deal of progress today in my work with virtual terrains!

In the last post I mentioned bucket fill algorithms and how they could contribute to realism by creating isocontours on the heightmap. I have successfully written and applied my own tolerance bucket fill algorithm. Unlike most such algorithms, however, my version actually preserves a set amount of the original surface variation, so as not to create a completely flat contour - which, of course, would be unrealistic.

I have also written a perlin noise generator to give variation to the heightmaps. Perlin noise is simply a linear combination of noise functions with varied frequencies and amplitudes. In practice, perlin noise generators often use a coherent noise function, such as a high-frequency sinusoid. I chose, however, to use only a simple rand() function. By mapping each point on the heightmap to a point on the (increasingly large) noise maps and performing 2-dimensional linear interpolation, one can achieve the desired effect without having to use trigonometric functions.

Now, using an additive combination of Brownian random deposition walks, bucket fills, perlin noise, and softening, I am able to create much more realistic terrains.

Below are a few sample heightmaps created with the aforementioned methods:

A quick summary of what's going on in these heightmaps:

  • Random deposition walks create long, winding rivers and mountain ranges
  • Bucket fills level out parts of the terrain to create isocontours, which give the appearance of defined features like plateaus
  • Perlin noise randomizes the space in between features with coherent noise
  • Softening passes remove rough spots created by deposition and bucket fills

Techniques for Heightmap Synthesis

February 13, 2010 Algorithmic Art 1 Comment

And now, for another deviation from algorithmic music.  As part of my research in building virtual worlds, I am exploring effective methods of creating interesting and detailed heightmaps for procedural terrain.

My earlier posts showed off some landscapes that were created using spectral synthesis and terrain deposition. I am now exploring methods that I hope will bring greater realism to the heightmaps. Having developed a set of algorithms that use Brownian motion (random walks) as well as certain erosion techniques to create features in the land, I began testing various heightmaps by walking over the resulting terrains.

Brownian random-walking deposition seems to create much more believable terrains than spectral synthesis or particle deposition alone.  Application of erosion and smoothing algorithms then reduces the sharpness of the terrains appropriately.

Below are a few of the heightmaps that were generated by my algorithms (note that the colors were chosen arbitrarily by the program):


All of the heightmaps were generated using custom-built random walk, erosion, and smoothing algorithms with varied parameters.  A "randomize" filter was then applied by a third-party texturing program, which helped create isocontours (plateaus, essentially) for added realism.  Though the filter is very nondescript, from what I can tell, it uses a technique much like a tolerance bucket-fill to "randomize" the image.  I will try to write my own version of this algorithm so that it can be applied automatically to the heightmaps.

While these heightmaps represent a great step forward in creating believable terrains (personally, I love number 4), they are still far from realistic.  Real land has far more intricacy and fractal dimension.  I will continue looking for new and better algorithms to create more realistic worlds.

A Shift in Tone: Algorithmic Art

January 19, 2010 Algorithmic Art 0 Comments

I am afraid that the day has come that I can no longer restrain my creativity to a single field of algorithmic art. As faithful as I have been over the past two years to algorithmic composition, my love for music is not strong enough to keep my imagination from wanting to run boundlessly through the possibilities of other fields of algorithmic art. It is with this acceptance that I now broaden the scope of this blog. No longer will A New Music represent only the field of algorithmic composition.

From here on, any topic of algorithmic art will be open for contemplation and posting. From generative modeling to procedural worlds, algorithmic painting to virtual reality, and, of course, full-blown artificial intelligence.

Now, in broadening anything, one risks the loss of precision and quality in a single area. I do not intend for my work in algorithmic composition to diminish in any way. In order to counteract the broadening of the project's scope, I will extend the project's lifetime. I no longer expect to finish by this summer, nor do I even expect to finish by the end of college. No, my work in algorithmic art will take me nothing short of a lifetime. It will take me years and years to explore all territory of the beautiful landscapes of algorithms and still, I will never reach every crevice. I have no doubts, however, that I will someday arrive at the level of quality of which I currently dream.

For now, much of my effort has been diverted to algorithmically creating worlds.  In particular, I have turned my focus to procedural terrain generation using methods such as spectral synthesis, midpoint displacement, and particle deposition.  I hope to explore generative modeling in the near future.  Naturally, contour grammar is still in the back of my mind.  Wait...what if grammar could be applied to landscapes as well?  Oh the possibilities!

Henceforth, A New Music is no longer A New Music.  It is now A New Reality, an exploration of algorithmic art.

Here's to a bright future for algorithmic art.  I'll celebrate it with a beautiful world, created today by none other than my own computer: