Posts In: XNA

Procedural Trees, Part 1

Finally, after having thought about the automatic creation of tree models for many months, I implemented my ideas with the help of XNA and HLSL.  The results were absolutely fantastic, far better than I could have imagined:

Yes, admittedly, it's just a trunk.  But it sure is a good-looking trunk!

The trunk is actually just a basic primitive that's being displaced in the vertex shader in real time, which means that the tree model can be changed almost instantly by making changes to the handful of maps that are controlling the vertex shader.  As with terrains, I can generate trees - well, tree trunks, at least - nearly instantly.

The next step is to hammer out branches and leaves.  Considering how well the trunk turned out, I'm confident that the rest of the procedural tree system will turn out nicely!

Long live procedural content.

Real-Time Morphing of Dynamic Procedural Terrain

This is just plain cool.  Instead of approaching terrains by creating a set of vertices based on heightmap data and shoving them through a draw call, why not let the GPU do the work?

When I asked Victor Porof how he achieved such fantastic speeds in his procedural terrain video, he explained that, instead of actual translating heightmaps to vertex data on the CPU, he was using a vertex shader to displace the vertices dynamically based on the loaded heightmap texture.  The implications of this?  Any changes to the heightmap could be immediately visualized with no hiccups and no load on the CPU.

Now, at first I thought "WHAT!? You can't do texture lookups in vertex shaders!!"  Thankfully, I was wrong!  Vertex Shader Model 3.0 and above supports VTF (Vertex Texture Fetch), which allows texture lookups within the vertex shader.  I yelped with joy when I learned this.

At first, I implemented the method using just a static heightmap to observe the performance difference.  Indeed, the method is fast.  More importantly, however, it's possible to generate new terrains very, very quickly thanks to the immediate response from the GPU and the lack of CPU workload.  How quickly, you ask?  I decided to find out.

After modifying the Perlin multifractal shader code to add some continuity (i.e. make the noise function less sensitive to seed such that adding .0001f would only make a small change to the overall terrain), I threw in some code to increment the seed and update the heightmap every frame.  The results?  Unreal.  I had before me a dynamic, morphing terrain based off of a complex Perlin multifractal shader running at roughly 70 fps.  It looked really, really cool.

Let's take a moment to reflect on the implications of such speed.  The ability to generate new heightmaps at 70fps means that, really, we can generate 70 completely unique terrains in one second (by simply setting the noise function back to normal, where a tiny change in seed value gives you a completely new terrain).  Now, I'll be the first to admit, Perlin multifractal isn't enough for a beautiful terrain by itself.  But, theoretically, I could generate a terrain of 70x the complexity, as far as shader instructions are concerned, and still only require roughly one second per terrain.

If those numbers don't really sink in, I'll put it this way: beautiful, complex, procedural planets are looking really feasible.  In fact, at those speeds, I don't think it would even be necessary to save assets to the HD when exiting from the virtual could just recreate all of the procedural assets (or at least the terrain) at runtime.  Incredible!

Unfortunately, I don't have any screenshots of this epic triumph, since they really wouldn't show the action.  If I can dig up Camtasia sometime this week, I'll try to upload a video so I will always be able to remember the day that I learned how to create 70 unique terrains per second!

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.

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: