Home       About Me       Contact       Downloads       Part 78    Part 80   

Part 79: Trees Again

April 18, 2013

I was working on the DontHitMe demo (honest!) and decided I wanted to add something else to the world. There aren't really enough interesting obstacles to route the track around. So I thought I'd add some giant vines escaping from the crashed ship to cover the world.

Back in Part 26, I implemented an algorithm for growing tree branches. I got an OK demo out of it, but it had some problems. The algorithm had a bug that kept it from stopping and it was too slow. I've fixed that up and dealt with a couple of other minor issues.


Trees Demo

Use the WASD or cursor keys to move, and you can start, stop and step the animation with the buttons at bottom-right.

The Stopping Bug

Fig 1: Failed branch

The algorithm works by creating a cloud of "leaf" points in the shape to be filled, and an initial set of branch segments. The leaves then "pull out" new branch segments from the existing set. When a branch gets near a leaf point, the leaf is eliminated. Iterate on this and you'll get a nice set of branches.

The problem is when there are just two points left pulling on a nearby branch segment. They will pull it exactly between them, and then get stuck (Figure 1). The new segment does not get closer to either point. On the next pass, the leaves will pull the same unproductive segment out, creating an infinite loop (and a lot of bad branches!)

Back in Part 26, I tried biasing the growth in various ways to avoid this condition, but never found anything I liked. This time I tried detecting the situation and keeping it from happening, but it requires a bit of extra checking to see that I've created an unproductive branch, and the algorithm is too slow already.

I ended up just counting the children off each branch point and limiting them to three children. This prevents the infinite loop and doesn't seem to produce too many obvious evil looking branches.

Performance

The algorithm is slow because every leaf point (thousands, in my original demo) is compared to every branch point (also thousands by the end of a run) each cycle of colonization. Fortunately, there's a maximum distance for comparisons, so we don't need to compare every leaf to every branch. To speed this up, you'd need some nifty 3d data structure to hold all the points and eliminate the distant ones from consideration.

I started to implement this with an Octree, but once I built it I realized the maximum distance is a pretty large fraction of the entire tree size. That meant there were only a few cells. Rather than convert the Octree code to Javascript, I just did it with a table of cells. Each cell contains a linked list of the branch points in that cell. This cuts out the distant comparisons and is simple to implement.

Of course, since we are comparing each leaf to something like 30% of the branch points, the optimization doesn't save much time either.

Drawing Branches

Fig 2: Finding Branches
In my old demo, I had drawn each branch segment as a cylinder. Months ago, I switched to drawing an entire branch at a time. I don't remember if I mentioned this anywhere on the blog, although I did update the demo.

The only trick to this is identifying a branch. The algorithm really has no concept of "branch" -- just a lot of little segments linked together. Each segment has a parent though, and working back from the tips to the root, I can find an entire branch. The problem is which child to take when a branch splits.

In Figure 2, you can see that one child is considered the continuation of the branch, and the other will start a new branch. I had first thought of looking at the angle the child makes with the parent, to keep branches from twisting around a lot. But a simpler approach seems to work.

I'm already setting the size of branches using a "water pipe" model. The tips are set to "twig" size, and each parent gets the sum of all its children, as if the parent had to carry water to them. To pick the correct continuation of the parent branch segment, I just pick the largest child. This seems to work well.

Pine Trees

Fig 3: Pine Trees
One of the things I'd wanted to try was different kinds of trees. I need to do a lot more on this, but I did try one simple experiment.

The normal tree is a sphere of leaf points above an initial trunk. The branches then grow up and find all the leaf points. I wanted something like a pine tree, where branches grow out more or less level from a central trunk.

To get this, I initialized the trunk to the full height of the tree, and created leaf points in a cone around that. Branches tend to be horizontal, since the leaves pull out the nearest point on the trunk. See Figure 3.

I think this needs a denser cloud of points and a shorter attraction distance to work. I'll play around with it some more later. The demo randomly generates a ball-shaped tree or a pine tree.

16-Bit Index Buffers

Now for some problems!

This demo didn't work at all in the first version, due to a restriction in WebGL. The standard only allows 16-bit index buffers. That means if there are more than 64K vertexes, you can't create an index buffer to use them. This is incredibly annoying, since it's not something I can hide in my code. It would need to create multiple vertex and index buffers to draw any mesh with more than 64K points. My trees were larger than that and failed.

Right now, I've just limited the number of leaf points to keep the branches from having too many points. I'm not sure how I want to handle this. There's a WebGL extension that will support 32-bit indexes if your browser implements them. I could just use that and ignore any more limited devices. But one of the main reasons to write WebGL demos was to run anywhere, so I don't really want to start doing that.

Slow Vertexes

You'll notice that the code is really slow, even on a fast desktop machine. This has nothing to do with the colonization algorithm. It's due to the way I build the vertex buffer.

In C++, you have a class that defines your vertex:

class Vertex
{
public:
  // point
  float px;
  float py;
  float pz;

  // normal
  float nx;
  float ny;
  float nz;

  // texture
  float tx;
  float ty;
};

To create a vertex buffer with 100 vertexes, you allocate memory for 100 copies of this structure, and copy your data into it. I could write code like:

  Vertex* buffer = new Vertex[100];
  ...
  Vertex* v = &buffer[i];
  v->px = 10;
where buffer is my vertex memory and i is the index of the vertex.

In Javascript/WebGL, I can't really do that. I can allocate the buffer using the ArrayBuffer object, but then I have to write it. I can either create "view" objects that point into it, making it look like an array of integers, floats, etc., or I can use methods to write a number directly to a byte offset.

Both of these are a nuisance. When I convert the code from C++ to Javascript, I want to use some kind of Vertex object, so that I write "v.px" for the x coordinate, not some index in an array.

On top of that, in principle you might have a vertex with a mix of datatypes. To access that, you'd have several views on the underlying ArrayBuffer. You'd use a Float32Array to write floating point values, and a Uint16Array to write integer values. Since these both point at the same buffer, you'd need to double the indexes in the Uint16Array to skip over the parts that are really floats. Ick.

What I did when I converted my mg3D library was allow the programmer to define a vertex with an array of fields, each with a datatype. Then there's an "add" method of "mgVertexBuffer" that loops through the specification and pulls out each field, writing it to the correct offset in the buffer. That allows me to write code like this:

var buffer = new mgVertexBuffer(Vertex.ATTRIBS, 100);
...
var v = new Vertex();
v.px = 10;
buffer.add(v);

For the other demos, where I just build vertex buffers at startup and then draw them, this worked fine. In this demo, where I'm rebuilding the vertex buffer each animation cycle, it stinks.

I'm not sure how to fix this without exposing the WebGL idea of a buffer to my code. It's a nuisance.

Emscripten

This demo didn't take much of the last two weeks. What I've really been doing is playing with Emscripten, which together with the Clang C++ compiler, can convert C++ code to Javascript. That would allow me to keep working in C++ and just treat WebGL as another platform, along with Windows, Linux and Mac.

I'll write more about that in another part.

Home       About Me       Contact       Downloads       Part 78    Part 80   

blog comments powered by Disqus