Procedural Trees

The acron.proctree module is the native half of procedural trees: growing a tree’s skeleton from a species’ parameters, meshing it, and reducing it to levels of detail. It is the part that has to be fast – a forest grows about a dozen prototypes per species at load, and the Python generator this replaces took about a second for far fewer – and the part that has to be exact: the same parameters and seed give a byte-identical tree on every run on the same platform. (Across operating systems and C libraries, sin, cos, atan2 and pow may round differently in the last place, so a tree may differ there: ship or cache the result, rather than regrow it, where peers on different platforms must agree.) Rendering (instancing, wind, seasons, impostors, shadows) lives in the Python tier, acron.trees, over public engine API (see Trees and Forests); this module is what it calls. It is CPU code with no graphics dependency, so a C++ game, a tool or a server can grow and mesh trees with it directly.

All randomness lives in the skeleton. Everything after it – the mesh, the LODs, the impostor bake – is a pure function of the skeleton (the split ez-tree 2.0 made).

Where the trees of a forest stand – species by altitude and moisture, clusters, clearings, edges, the understory – is Ecosystems and Ground Cover’s ecosystem simulator; its plants feed ForestCells through acron.trees.

The classes

TreeParams

The shape of a species: Weber & Penn’s parameters, read and written by name, so a JSON preset maps onto it key for key. Scalars (shape 0-8, scale, base_size, ratio, flare, lobes, attraction_up, the pruning envelope prune_*, leaves – negative for a fan at the tip – and leaf_*) hold one value; per-level parameters (length, taper – nTaper 0-3 –, seg_splits and split_angle for clones, curve/curve_back/curve_v, branches, down_angle, rotate) one per level, index 0 the trunk and index levels the leaves. SeedThree’s extensions are there too: force_* (a growth force, bending thin wood more than thick), trunk_fork_* (a low fork into joined leaders), tip_cluster (children at the parent’s tip: forks), whorl_size (opposite or whorled branching), twist. get_doc(name) documents each; get_hash() digests them all.

TreeRecipe and TreeOp

An ordered list of growth ops over one TreeParams (MTree’s pipeline): T_trunk, T_weber_penn (the branch levels), T_space_colonization (Runions et al. 2007: attraction points in a crown envelope pull new wood out of the existing stems, radii by the pipe model), T_roots, T_leaves and T_prune. Each op draws from its own stream, splitmix64(seed, op id), and each stem from one keyed by its place in the tree, parent before children – so editing one op, or a twig, leaves everything else where it was. grow(seed) is BLOCKING.

TreeSkeleton

The grown tree as three struct-of-arrays tables – nodes, branches (depth first: a branch’s subtree is [i, subtree_end)) and leaf cards – each array a PTA (flat: three floats a node for positions), readable without a copy through the buffer protocol (memoryview). Nodes carry a rotation-minimising frame (double reflection, continued from the parent at a fork), arc length, distance from the root and a wind weight that a child starts at its parent’s value where it grows from.

TreeMesher

One Geom per tree: bark tubes whose ring sides follow the radius, stitched by a zipper where the count changes (no gaps, MTree’s gap fill), closed to a point at the tips; V along the wood from the root, continuous across forks; trunk lobes, bark noise and a flare where a child leaves its parent; leaf cards (single, crossed or a cluster of three) with normals bent out of the crown ellipsoid; for conifers a spray card folded down along its middle (layout 3), so needle fronds keep their volume close up. Columns: vertex, normal, texcoord, color (ambient occlusion), wind0 (bend weight, phase, flutter, level), wind1 (pivot – the stem’s centreline point, or the leaf’s anchor – and stiffness), leaf (random, kind, sprite, layout), tangent (U’s direction and the bitangent’s sign, for bark and leaf normal maps), wind2 (the bend weight split over the trunk’s, the level-1 ancestor’s and the level-2 ancestor’s modes, and the damping ratio) and wind3 (those modes’ natural frequencies in Hz and the flutter frequency); 132 bytes a vertex, 32-bit indices. count_triangles counts without building (the LOD ladder’s question). Its settings are properties: min_sides / max_sides / edge_length (ring sides from the radius), ring_stride, radial_scale and min_radius (what the LODs change), bark_tile, lobes / lobe_depth, bark_noise, junction_flare, bark and leaves (either half alone), leaf_normal_card, leaf_layout (0 single, 1 crossed, 2 cluster, 3 folded spray) and leaf_tile. make_geom and make_node build; get_format() is the registered vertex format.

Dynamics. After Zhao & Barbič (SIGGRAPH 2013) and Habel et al. (EG 2009), each stem is a cantilever clamped where it grows: its stiffness is the tapered tube’s tip compliance, integral of (L - s)^2 / (E I(s)) ds, and its mass is the wood’s plus everything growing on it (child stems whole, leaf cards at 0.02 kg/m^2), weighted by the first mode’s shape (Rayleigh); f = sqrt(k / m) / 2 pi, kept within 0.05-24 Hz. wood_stiffness (GPa), wood_density (kg/m^3, green wood), damping (ratio) and leaf_flutter (Hz for a 1 m card, falling as 1 / sqrt(size)) are the species’ properties. branch_frequencies(skeleton) gives every branch’s frequency (0 for roots), flutter_frequency(size) a card’s, and the static beam_frequency(length, radius, stiffness, density, tip_mass) a uniform rod’s (~0.28 (r / L^2) sqrt(E / rho) when bare). The split is exact at forks: a child starts with its parent’s split, and stems deeper than level 2 ride their level-2 ancestor’s mode. The motion itself is wind_tree_offset in acron.shaderlib’s wind.glsl.

TreeLod

Levels of detail under triangle budgets, each the first step of a fixed ladder (rings skipped along a stem, fewer sides, thin wood pruned on a copy, fewer leaf cards – outer first, nested, scaled to keep the crown’s area up to 1.6x, pulled inwards so the silhouette stays, the sprite repeated rather than magnified) that fits, and coarser than the level before; or a billboard cloud: the leaves clustered (k-means) into a few big crossed cards, each in its cluster’s own plane (principal axes, leaning out of the crown) and sized to it, over the thickest limbs. get_triangles, get_leaf_keep, get_min_radius, get_ring_stride and get_radial_scale report what each level chose; the static reduce and billboard_cloud are the two reductions on their own.

ForestCells

The CPU side of an instanced forest: trees (twelve floats each – the three texels of the instance table the vertex shader reads by gl_InstanceID – plus a species group and a prototype) binned into cells; update(camera, planes, time) culls the cells against the view frustum (frustum_planes from a world-to-clip matrix; cells within keep_radius stay, they cast shadows into view), gives each tree a level by distance with hysteresis, fades a changed level over fade_time seconds of the frame clock (the tree sits in both levels’ runs with a fade code the shader turns into a dither threshold, so a still camera finishes the fade), and rebuilds only the cells whose tables changed; plant() fills in each tree’s defaults (prototype, scale, yaw, tint) from a hash of its position, and write_cell_texture() uploads a cell’s table. About 0.1-0.2 ms a frame for 600-6000 trees (BLOCKING). The module is compiled without fast math or fused multiply-adds (/fp:precise on MSVC), so its floats don’t depend on the compiler’s choices (the tests compare it with a float32-exact Python reference); the yaw’s sin and cos come from the platform’s C library.

TreeAtlas

The no-art default textures: leaf-cluster sprites in several styles (broadleaf, maple, small, bush, willow strands, needle sprays, pine brushes, palm fronds), tiling bark (furrowed, smooth, birch, plates, scaly, palm), their tangent-space normal maps and a leaf mip chain that keeps the alpha-tested coverage (Castano 2010), painted deterministically from a seed (splitmix64) in about 50 ms a species; make_*_texture() uploads them (colour as sRGB).

Using it

Growing a tree is a recipe over a parameter set, grown from a seed; the skeleton is meshed once per level of detail. The shipped species presets of acron.trees are JSON files of exactly these parameters and ops.

#include "treeParams.h"
#include "treeRecipe.h"
#include "treeMesher.h"
#include "treeLod.h"
#include "treeAtlas.h"

PT(TreeParams) params = new TreeParams;
params->set("scale", 16);
params->set_level("branches", 1, 40);

PT(TreeRecipe) recipe = TreeRecipe::make_default(params);
TreeOp *roots = recipe->add(TreeOp::T_roots);
roots->set("count", 6);
PT(TreeSkeleton) skeleton = recipe->grow(7);

PTA_float xyz = skeleton->get_node_positions();   // 3 floats a node

PT(TreeMesher) mesher = new TreeMesher;
PT(TreeLod) lod = new TreeLod(mesher);
lod->add_level(16000);
lod->add_level(5000);
lod->add_level(300, 32);
lod->build(skeleton);
PT(Geom) near_geom = lod->get_geom(0);

PT(TreeAtlas) atlas = new TreeAtlas;
atlas->paint_leaves("broadleaf", LVecBase3f(0.22, 0.36, 0.12), 0.12, 1);
atlas->paint_bark("furrowed", LVecBase3f(0.32, 0.27, 0.22), 1);
PT(Texture) leaves = atlas->make_leaf_texture("oak-leaves");

A forest’s cells take the trees as flat arrays. plant() fills in what is left empty from a hash of each position; update() is called once a frame with the camera and the frustum’s planes, and the cells it reports as changed are uploaded and redrawn. Distances are in metres (set_metres_per_unit converts from world units); a run is (lod, group, prototype, first row) of a cell’s table, drawn as one instanced Geom of get_cell_run_count instances.

PT(ForestCells) cells = new ForestCells(64.0f);
cells->set_group_distances(0, LVecBase4f(35, 70, 150, 1500));
cells->set_fade_time(0.6f);

PTA_float positions = PTA_float::empty_array(3 * n);
PTA_float proto_heights = PTA_float::empty_array(1);
proto_heights[0] = 14.0f;
PTA_float none;
cells->plant(positions, 0, proto_heights, none, none, none, none,
             PTA_int(), seed);

// every frame
PTA_float planes = ForestCells::frustum_planes(world_to_clip);
cells->update(camera_pos, planes, now);
for (int i = 0; i < cells->get_num_changed(); ++i) {
  int cell = cells->get_changed(i);
  cells->write_cell_texture(cell, tables[cell]);
  for (int r = 0; r < cells->get_cell_num_runs(cell); ++r) {
    LVecBase4i run = cells->get_cell_run(cell, r);  // lod group proto row
    int count = cells->get_cell_run_count(cell, r);
  }
}

The vertex shader that reads the tables, with the wind, seasons and fades, is acron.trees’ tree.vert; a C++ game takes it from the Python package’s trees/shaders/ folder or writes its own against the layout above.

Sources

The growth model is Weber & Penn, “Creation and Rendering of Realistic Trees” (SIGGRAPH 1995), reimplemented from the paper. With thanks to the projects it learned from (see Third-party Software):

  • SeedThree (https://github.com/SkyeShark/SeedThree): the Weber-Penn extensions, fork-continuous wind weights and the stem-centreline wind phase, the per-op splitmix streams drawn parent before children, the nested shell-first leaf thinning, branch cards;

  • MTree (https://github.com/Warwlock/MTree): the op pipeline, radius-adaptive ring sides with gap-fill bridging, wind vertex colours;

  • ez-tree (https://github.com/dgreenheck/ez-tree): the skeleton/mesh split and the growth force;

  • acronvehicle’s treegen.py (in-house): the behavioural prototype – crown normals, the LOD ladder, the atlas painter now in acron.trees.

Space colonisation is Runions, Lane & Prusinkiewicz, “Modeling Trees with a Space Colonization Algorithm” (2007); billboard clouds Décoret et al. (2003); rotation-minimising frames Wang et al. (2008).