Voxel Space Automata

by Alerk Amin

Table of Contents

Figures


INTRODUCTION

Throughout nature, there is a delicate balance between order and randomness. From mountains to oceans to plants, the seemingly random shapes of objects are actually based on a extremely ordered foundation. The driving force behind computer graphics is to create realistic scenes, from the largest objects down to the smallest subtleties of the texture. Nowhere is this more important than in scenes involving nature.

Just as people decorate their homes with plants, graphic scenes look better with touch of nature in them. Whether the purpose is to add a splash of color, or prevent a corner from looking empty, plants can enhance any scene, whether indoors or outdoors. But to truly add to the image, the plant should look real. This means that the balance between order and randomness must be found in the structure of the plant.

The purpose of my Masters Project in Computer Graphics is to automatically create realistic plants for use in computer generated pictures. Using the methods outlined by Greene in
[1], along with some personal additions, realistic plants can be created and included in images.

GOALS

The goal of this project is to create a C module for Data Explorer 2.0
[2]. This module takes a number of parameters as input, including the size of the plant, as well as parameters that adjust the shape of the plant. It returns as output a field, consisting of lines, that make up the plant. Existing Data Explorer modules can then place the plant inside a scene and render it.

Another goal of the project is to enhance the module by making it multithreaded for parallel machines. Large plants with many branches can take lots of CPU time to create, so splitting up the work and distributing it among a few processors can significantly reduce the time required to construct the plants. The module uses PVM3 [3] to run on a network of workstations.

APPROACH

The approach described by Greene involves starting a with a large, empty, 3 dimensional voxel space. Then, starting with one or more seeds, grow the plant by changing voxels from unoccupied to occupied. The plant is created by repeating a basic process:

At each node, try to grow a short distance. Test a few directions, and pick the best one based upon the amount of light and sky reaching the node, as wells as the distance from other occupied voxels (to avoid collisions). At some random nodes, create a new branch, using the same process. If a node hits the edge of the allocated space, the node stops growing.

Although this method works well, it is extremely time consuming. A great deal of effort is taken in finding the best direction to grow, when a good direction will do. In addition, leaves are extremely difficult to place on the branches, and Greene's paper doesn't address them at all. Also, the plants become tiny blocks, and although they may look fine from a distance, a closer view of the plant would look jagged.

Another concern is that part of my project involves making this run in parallel. Splitting up a 3-d region among a group of processor is an extremely difficult task. The load should be balanced between processor, which is difficult for plant, since most plants have more branches near the top. Also, as the plants grow into other regions, a great deal of overhead will be wasted in synchronizing the processors, and checking neighboring regions for collisions.

To combat these issues, I decided to take advantage of Data Explorer's ability to render line segments. By constructing the plant as a field consisting of many line segments, the jagged edges are eliminated. In addition, by keeping a list of the nodes that need to be grown, the work can easily be split among processors. Each processor takes a node off the list, grows it by one iteration, possibly branching as well. Then, it inserts the new node(s) onto the list, and repeats the process. This will ensure a good load balance, with very little communication between processes. In addition, leaves can be constructed with small polygons placed at the ends of line segments.

GROWTH MODULE DESIGN

The Growth module, written for DX 2.0, was written increments. First, a single stem was grown. Then, additional features such as attractors and collision avoidance were added. This section describes the features in the order they were added to the module, as well as the issues the brought up, and how the issues were resolved. Every parameter described in this section is an input to the Growth module, and can be set by the user.

Basic Stem Growth

The plant starts with a single stem, located at the origin (0, 0, 0), growing towards the positive z axis. The stem is grown by first offsetting the direction of growth a tiny bit, then growing a fixed distance GROWTH_SIZE (the default is 5, but this can be changed) in that direction. When the stem hits the edge of the bounding box, the stem stops growing.

A small direction adjustment is made by first finding a random vector within a narrow cone. This is achieved by first creating a vector (0 ,0, GROWTH_SIZE). The vector is rotated between 0 and 10 degrees about the y-axis, and then rotated between 0 and 360 degrees about the z-axis. This gives a vector with length GROWTH_SIZE, almost parallel to the z-axis. The rotations required to make the z-axis point in the previous direction of growth are determined, then applied to the offset vector. The result is a vector that points at a small angle (less than 10 degrees) from the previous direction. The plant is grown in this direction, and the process is repeated.

The result is a stem that is grown in almost the original direction, but contains the small bends that make it look real.

Branches

In dealing with branches, I also kept in mind the parallelism I would be adding later. To satisfy both of these problems, I added a queue of branches to be grown. The queue starts with a single node, the seed. The program dequeues an entry, grows it using the Basic Stem Growth algorithm, and computes a new node, which it then enqueues, and repeats the process. However, for each node, it computes a function that is true BRANCH_PROBABILITY per cent of the time. If the function returns false, no branch is created. However, if the function is true, it creates a branch. Using a similar algorithm to the Basic Stem Growth, it computes a direction that is between 40 and 60 degrees from the original direction. It then grows in this direction, and enqueues this new node. The queue can become fairly long, if many branches are created, resulting in a long list of nodes to be grown.

Greene uses a parameter called branch_age_range, which contains the number of iterations before a stem branchs, picked at random for each stem. However, the percentage approach allows finer control over the overall number of branches in the plant. In addition, it provides a basis for multiple branches at the same node, which is describe later.

This approach supports parallelism well, because each processor can grow the nodes independent of the other processors. The queue and output field must be shared between the processors, but nothing else. Each processor can simply take an element off the queue, process it, update the output field, enqueue the new nodes, and repeat the process. The processing stage, where the direction of growth is jittered and new branches may be grown, depends only on data contained at local processor.

The main problem with branching is that multiple branches can run into each other. Since intersecting branches doesn't happen to real plants, steps to avoid this were taken. But intersection isn't the only problem. If a group of branches all grow into the same area, the plant is dense in this area, and sparse in other areas. This also makes the picture look bad, since plants usually fill the available space rather evenly.

Greene solves these problems by testing a bunch of directions, and picking the best one. If a good direction cannot be found, the stem is not grown. This has the effect of creating short branches in the middle of plants that look bad. My approach is to try and spread out the branches, so there is a smaller chance of them entering the same region. My solutions to both of the problems are branch avoidance and attractors.

Branch Avoidance

If a new branch is created along a stem, the next branch shouldn't point in the same direction. This is the basic premise of branch avoidance in my design. Each stem keeps track of the direction of the previous branch. It the stem creates another branch, the branch will be at least 90 degrees from the previous branch. This is accomplished by saving the degrees the new branch was rotated about the z-axis in the Basic Stem Growth algorithm. Then, when a new branch is created, the new z-axis rotation is some value within a 180 degrees arc centered in a direction opposite to the previous rotation.

Attractors

An attractor is a single point, usually outside the bounding box, that the plant has a tendency to grow towards. In nature, the sun is an attractor. Since the branches of a plant are attracted towards the sun, they grow upwards, and therefore do not collide with the lower branches of the plant. Without attractors, using all the algorithms given above results in a direction that is independent of the location of the node. Attractors use the location of the point to choose a direction.

Two of the inputs to the Growth module are the attractor_location, a Point, and the attractor_strength, a number between 0 and 1. Using all the algorithms above, the module computes a direction growth_dir to grow a branch. But before it grows the branch, it adjusts the direction based on the attractor. From the current location of the node, it computes a vector attractor_dir of length GROWTH_SIZE, pointing to the attractor. It then computes a new growth direction as a linear combination of these two vectors: (attractor_strength)*attactor_dir + (1 - attractor_strength)*growth_dir. It normalizes this vector to length GROWTH_SIZE, and then grows it. Note that for a small attractor strength, the the result vector points closer to growth_dir, while for a higher attractor strength, it points towards attractor_dir.

Segmenting & Multiple Branches

Segmenting is a tricky technique that puts significantly more control of the plant's structure in the hands of the user. Rather than setting a single branch probability for the entire plant, the user can divide the plant into 3 parts, and set the probability for each part. With the addition of multiple branches, plants such as clovers, which have a single stem that breaks off into 3 or 4 branches, can be created.

The three segments are called the trunk, which consists of the part of the plant near the seed, the limbs, in the middle, and the twigs, which are at the end. The user can specify the number iterations required for each part, and thus divide the plant into 1, 2, or 3 segments.

For each segment, the user can define the maximum number of branches at each node and the branch probability. The branch probability is the probability for a single branch. For example, if a node has maximum number of branches = 2 and branch probability = 50%, there is a 25% chance of no branches, 50% chance of one branch, and 25% chance of two branches.

In the hands of a skillful user, segmenting and multiple branches allows a extremely wide variety of plants to be created. However, it can also be very dangerous. It is very easy to create an extremely large number of branches, making the Growth module run very slowly.

Parallelism

Because each node grows independent of the other nodes in the tree, fine grain parallelism can be achieved. With more than one processor, each processor can be working on a single node simultaneously, greatly reducing the amout of time required to produce a plant.

The parallel version of the module uses PVM3
[3] for communication between processes. When the module is executed, the process that interfaces with Data Explorer registers with PVM and becomes the "master" node. It then spawns a user-specifiable number of "slave" processes. PVM distributes these processes among the available machines.

The master process becomes a server for the other slave processes, which do the actual computation. The master starts by broadcasting the basic tree information, such as branch probabilities, sizes, and attractor location, to the slave processes. In addition, it initializes the queue to the first node.

Each slave process requests a node from the master. The master receives these requests, and sends nodes from the queue back to the slave processes. The slave processes use the node information, as wells as the basic tree information, and compute a set of new nodes, including any new branches. It then sends this information back to the master. The master enqueues the new nodes, adding them to the appropriate field, and the process repeats.

When all nodes have been processed, the master sends a "dummy" node to the slave processes, which are still requesting nodes. When the slaves get this node, they exit. The master then outputs the plant.

To the user of the module, the only difference is the addition of an input for the number of processors. This parameter is the number of slave processes that are started. The optimal number of slaves is usually the number of machines specified in the PVM hostfile, though not always.

Due to the nature of the parallel algorithm, the slaves may get nodes in different orders on different executions of the module. Therefore, running the module twice with the same inputs will usually result in different outputs. To make a sequence of images with the same plant, it is better to use the serial version.

RESULTS


Figure 1. A basic tree

This basic tree shows many of the feature of the Growth module. The trunk segment is the thick line at the bottom. No branches are allowed for this portion. The limbs segment allows branching, and usew a smaller radius for the tube module. The twig segment is rendered in green, and has a depth of 1. It also has a very high number of branches, and a high branch probability, to give the bursts of green at the ends of the limbs.


Figure 2. A fern

This fern is created by having a very small trunk and limb depth, with many branches. Then, the twigs are given a large depth, but no branches. By placing the attractor below the origin, the plant grows downward. This makes the long, hanging vines that distinguish ferns. All the fields are colored green, with small tube radii.


Figure 3. A palm tree

This palm tree exemplifies segmenting. The trunk is made rather long, with no branches. Then, the limbs are given a depth of one, with a high number of branches. This causes the burse of limbs at the end of the trunk. Then, the twigs are given large depths, with no branches. Once again, the attractor is placed below the origin, causing the twigs to bend downward. The trunk is made thick and brown, while the limbs and twigs are thin and green.

Figure 4. A sequence of images with a moving attractor

This sequence shows the benefit of the attractor. In the first image, the attractor is to the right of the plant. In the second image, it is directly above the plant. In the third image, it is to the left of the plant. The result is the plant "follows" the attractor. By creating many more frames, it is easy to construct a movie of a plant following the sun across the sky.

GETTING THE MODULES

For both versions of the modules, it will be necessary to edit the Makefiles to reflect the locations of libraries on your system. Makefile, queue.c, queue.h, and user.mdf are different between the two versions. Be sure to get the right one.

Serial Version

The required files for the Serial Version are:

Parallel Version

The required files for the Parallel Version are:

USING THE MODULES & EXAMPLES

The main point to keep in mind is that it is easy to create thousands and thousands of branches, which will take most computer a very long time to computer. For each segment, the number of nodes at the end of the segment is approximately
(1 + max_number_of_branches * branch_probability)^depth
So the number of nodes at the tip of the tree is
number_of_nodes(trunk) * number_of_nodes(limbs) * number_of_nodes(twigs)
And the interior of the tree is even more nodes.

Each input of the Growth modules is either an integer or a float. The only difference between the Serial and Parallel version is the Parallel has an extra parameter for the number of slave processes. The three outputs correspond to the trunk, limb, and twig segments. To make them into a single field, use the Group module. See the user.mdf files for more information on inputs and outputs.

For each of these examples, there are control panels to easily change the attractor strength and location, the parameters for each segment, and the random seed. Use the "Open Control Panels" menu option in DX to get access to these.

Serial Examples

The serial examples all correspond to the images shown in the results section of this document.

Parallel Examples

Because the parallel version can produce different results for the same input, based on the order the slaves receive nodes, no sample picture is given. The example uses 2 slave processes, and there is no control panel to change the number of slaves, but it can be added.

CONCLUSIONS & FUTURE WORK

The Growth modules are an attempt to create realistic plants and trees, using some simple algorithms. There are a number of options that could be added to give the user more control over the look of the plants.

One option that could be added to both the Serial and Parallel versions is having different attractors for each segment. This would allow the palm tree's trunk to be attracted upwards, and the twigs downwards. Another option is having branches be their own segment, rather than having segments based on depth. This would allow for a thick trunk segment all the way to the top of the tree, then have thinner limbs off the trunk, and even thinner twigs off the limbs.

A feature that could be added to the parallel version are syncronizing on the random number generator, to make the parallel version produce the same tree with the same inputs. Another addition would be to allow slaves to grow more than just one iteration, to reduce communication. The load could still be balanced well if slaves grew out an entire segment, rather than just one iteration.

Of course, leaves can be added to make the plants look much better. The procedure to calculate a direction of growth for leaves has already be implemented, and it remains to just add the leaf polygons to the field. More than any other feature, leaves would make the plants more real.

The Growth module can serve as a basis for a great deal of future work in other types of growth, such as crystal growth. With some more additions, the module can become faster and produce better plants. But as it stands, plants can easily be included in Data Explorer images.

References

[1] Greene, Ned "Voxel Space Automata: Modeling With Stochastic Growth Processes In Voxel Space" Computer Graphics, July 1989. pp. 175-184

[2] IBM Data Explorer 2.0. For more information, click here

[3] Parallel Virtual Machine 3.0, Oak Ridge National Laboratory. To get PVM, send email to netlib@ornl.gov with the message: send index from pvm3. You will receive a list of available files and further instructions.