Real-Time GPU Tree Generation

We choose the Weber-Penn model [WP95] as our basis; It efficiently maps to GPU work graphs and produces convincing 3D models of arbitrary complexity. Further, we find it more accessible to artists than grammars for which GPU implementations exist [LWW10, MBG*12, SKK*14a]. It does not suffer from high memory requirements [KS14, KSvK19] or from additionally generating a volume [KS18]. Finally, it natively supports animations.

Weber and Penn model their trees with up to four levels of stems: One level 0 stem is the trunk of the tree. A level $i$ stem has child branches of level $i\; +\; 1$, which protrude from their parent. The last level of stems has leaves as children. Each level is associated with user configurable parameters regarding its curvature, length, radius and taper, or number and placement of children. In addition to this level hierarchy, the model also supports stems splitting into multiple clones with the same set of parameters. Clones continue their growth where their clone template left off, but with a different trajectory each. The trajectory of a stem level is defined by generated transformations, consisting of a position and an orientation each. Each transformation forms a ring. In the original implementation, for the stem geometry, two succeeding rings are then connected by a truncated cone, called a segment. One of the user-configurable parameters altering a stems trajectory is the upwards attraction. A positive upward attraction causes branches to grow towards the sun. A negative one models gravity pulling stems down. Leaf shapes are selected from a predefined list and are not procedural. See Fig. 2 for an example of a two-level Weber-Penn tree.

We call a GPU program a shader, which is executed in thread groups. A thread group consists of one or multiple single instruction, multiple data (SIMD) waves of usually 32 threads. A GPU work graph [Mic24] is a directed graph of shader nodes. Each node can create work records for other nodes. Record execution scheduling is handled by the hard/firmware itself. While being previously limited to compute shaders, new mesh nodes allow for direct output of geometry to the rasterizer. Mesh nodes may not create work records and are thus leaf nodes. A mesh node contains a mesh shader, an optional pixel shader, and all other state associated with a rendering pipeline, like viewport and culling settings. The mesh launch node spawns a grid of thread groups, similar to a mesh shader draw call.

The (Level0-3) nodes receive an initial stem transformation, compute the stem trajectory, write segment records for drawing that stem, and create records for children branching away from them.

Thread Allocation Implementing the stems splitting into clones could be solved by outputting new work records at each split, but early experiments showed that the work graph launch overhead is too high. Instead, we propose to perform the splitting between the threads of a wave, thus we launch one group of 32 threads per [S] using the broadcasting launch mode. Consider the wave in Tab. 1 simplified to eight threads instead of 32 for brevity. Initially, all threads of our example wave belong to the only clone 0. On each split into s clones, we separate the t threads into blocks, where a block receives $\backslash lfloor\; \backslash frac\{t\}\{s\}\; \backslash rfloor$ threads each. In a block, the thread with the lowest index is responsible for writing the record for drawing the segments of that clone. Child record writing is distributed among the threads of the respective block. This approach can be extended to multiple waves to support more than 32 clones, but we did not model a tree type where this is required.

Hierarchical Generation Culling Writing of a child record is omitted, if a conservative bounding capsule lies outside the view and shadow frustum. This way, generation only runs for children that have the chance to generate visible geometry. Similar culling applies to writing the [D] or [L] records.

The (DrawStem) node is a mesh node that receives one [D] as input, containing two stem transformations $\backslash tilde\{P\}\_\{\backslash text\{from\}\}\; \backslash in\; \backslash mathbb\{R\}^3,\; \backslash tilde\{R\}\_\{\backslash text\{from\}\}\; \backslash in\; \backslash text\{SO\}(3)$ and $\backslash tilde\{P\}\_\{\backslash text\{to\}\}\; \backslash in\; \backslash mathbb\{R\}^3,\; \backslash tilde\{R\}\_\{\backslash text\{to\}\}\; \backslash in\; \backslash text\{SO\}(3)$. To smooth out the coarse cone geometry from the original Weber-Penn model, we interpret a stem as a cubic Hermite spline tube, where a stem segment is also a spline segment. The spline control points of the segment are the positions $P\_\{\backslash text\{from\}\},\; P\_\{\backslash text\{to\}\}$. For the Hermite spline tangents, we extract the forward axis of the quaternions $R\_\{\backslash text\{from\}\},\; R\_\{\backslash text\{to\}\}$ and scale them by the distance $\backslash |P\_\{\backslash text\{to\}\}\; -\; P\_\{\backslash text\{from\}\}\backslash |$. When writing a [D] record, the nodes (Level0-3) compute the following quantities:

Pixel Space Dimensions Different tessellation factors between segments would lead to cracks. To have the same vertices between segments, we define the factor for each ring in-between. For this, we project the radius of a ring into the pixel space. If both radii $r\_\{\backslash text\{from/to\}\}$ of a segment are smaller than a user defined threshold, e.g., one pixel, we cull the segment. In addition, we project the two ring centers of one segment into pixel space and compute their distance in pixels $l$ as a sufficient estimation of the spline arc length.

Opening Angle To mitigate the generation of back-facing triangles, we approximate the required tessellation opening angle $\backslash theta$ for each ring. See Fig. 4 for reference. Let $r$ be the ring radius and $z$ the rate in growth direction in world units. Then, $\backslash frac\{dr\}\{dz\}$ is the change of radius at the ring. Given the cosine $x$ of the angle between the camera direction and the growth direction, the required opening angle

As we assume orthographic projection, $\backslash theta$ is slightly more conservative than needed for perspective projection. We also neglect the radius variations caused by procedural displacements, but did not find a case where this is a problem.

Tessellation Factors For stem tessellation, we employ fractional odd spacing as shown in Figs. 4c and d. In the simplest case, a stem is represented by a quad of four vertices and two triangles, where we force $\backslash theta\; =\; \backslash frac\{\backslash pi\}\{2\}$. Going finer, two more vertices get smoothly interpolated into the edge. A segment requires four tessellation factors: For the axis around the stem radius, the two outer tessellation factors $f(\backslash text\{rom\})$ and $t(\backslash text\{to\})$ at the rings, and the inner tessellation factor for this axis $u$. For the other axis along the stem only the factor $v$ is

required, as no neighboring patch exists. With a user-defined constant pixels per triangle $\backslash Delta$, the opening angles $\backslash theta\_\{\backslash text\{from/to\}\}$ in radians, the radii at the rings $r\_\{\backslash text\{from/to\}\}$, the tessellation factors are:

Displacement At close viewing distance, we blend in a procedural bark displacement map, see Fig. 3 for details. In the pixel shader we also evaluate the displacement as a normal map, together with other procedural physically based rendering (PBR) maps.

Leaves grow from the last level of stems offset by a parameterized leaf stem length. Our leaf model is inspired by Garg [Gar11], who describes the shape of leaves with quadratic B-spline curves. We prefer it over other models [RFL*05, HSVG05, KK17], because of its speed and artistic expressiveness. For fast and pixel-perfect evaluation of smooth leaf edges, we use the pixel shader inside/outside test for quadratic Bézier curves proposed by Loop and Blinn [LB05]. If a pixel falls outside the quadratic Bézier curve defined by the triangle, we discard it, similar to opacity mapping.

Geometry A leaf consists of one or multiple lobes. The user defines one half of the shape of a lobe per tree type with the parameters shown in Fig. 5a. From that we compute vertices $\backslash vec\{v\}\_i\; \backslash in\; \backslash mathbb\{R\}^2$. $\backslash vec\{v\}\_0,\; \backslash vec\{v\}\_4,\; \backslash vec\{v\}\_8$ are set as in Fig. 5a. We compute in-between vertices $\backslash vec\{v\}\_1$ to $\backslash vec\{v\}\_3$ of Fig. 5b from a weighted sum:

where the tangent scale $l\; =\; \backslash frac\{\backslash |\backslash vec\{v\}\_4\; -\; \backslash vec\{v\}\_0\backslash |\_2\}\{2\}$. $\backslash vec\{v\}\_5$ to $\backslash vec\{v\}\_7$ are computed analogously. Note that the number of inner triangles increases when a Bézier segment is not convex. Multiple lobes are determined with the parameters of Fig. 5c. As the vertices and triangles of one leaf do not adequately fill the output of a mesh shader group, we need to combine multiple. Similar to the work graph instancing [KOF*24], we use (BundleLeaves) in coalescing launch mode to combine up to 256 small draw records of leaves [L] into one big leaf bundle [LB].

Level of Detail For a continuous leaf LOD, we reduce the amount of geometry per leaf at increasing distance as shown in Fig. 5d to f. As soon as the lower LOD is reached, we use a different mesh node (DrawLeavesLow). This is implemented with a work graph node array for (BundleLeaves). For multi-lobe leaves, we shrink the rotation angle $\backslash sigma$ to merge all lobes into one at higher distances. In addition, we employ the common trick to remove leaves at large distances and compensate by increasing the scale of the remaining ones. To make this continuous, disappearing leaves slowly shrink.

Material and Needles For more leaf detail, our pixel shader adds a line strand in the center and parabolic strands to either side of the leaf, affecting the base color, normal, and roughness of the surface. The strand count, spacing, curvature, and thickness are further leaf parameters shown in Fig. 6a. At very close distances as in Fig. 6b, we add cellular detail with Worley noise [Wor96]. In case of a needle leaf in Fig. 6c, we use the same strands for opacity mapping.

We specify a season parameter $S\; \backslash in\; [0,\; 4]$, where 0 corresponds to full winter, 1 to spring, etc. We also support in-between values, resulting in the continuous changes of Fig. 7. Tree species do not necessarily respond to seasonal changes simultaneously. To model this, we introduce a seasonal offset parameter per tree type. We consider summer as the default season. Next, we describe what we change to obtain other seasons:

Snow For winter of Fig. 1a, we omit rendering of leaves. Needles receive a white frosty outline. To model snow on stems, we increase the displacement from Fig. 3 for stem portions pointing upwards. These extruded regions receive snow material properties. We also decrease the vertical stem attraction to make stems bend down with increasing snow load.

Blossoms In spring, the leaves in Fig. 1b grow back. We add blossoms rendering them like leaves with lobes arranged in a circle.

Fruits In summer, a random fraction of blossoms grows into fruits of Fig. 1c. We use a cubic Bézier curve to model one side of a fruit profile. This profile is then rotated around the fruit's vertical axis and tessellated in a mesh shader. Fruits decrease the vertical attraction of their father stem.

Shedding In fall, leaf colors of Fig. 1d change from yellow to red to brown. Later, leaves shed and disappear. Each leaf has a seasonal offset, making leaves vanish gradually.

The Weber-Penn model describes basic wind animation but ignores wind direction. We incorporate wind direction during stem generation, by rotating each segment away from the wind source. The amount of rotation chaotically oscillates with the current timestamp using Perlin noise: We scale the amplitude by the segment radius and the frequency by the inverse square-root of the stem length. The succeeding segments and children are generated with the animated transformation of the current segment. This implicitly gives us a highly detailed skeleton with one bone per segment without the need for explicitly storing it. For the Sassafras tree of Tab. 2 this would amount for 16.5 k bones. Thus, we obtain the highly detailed animations shown in Fig. 8 and the supplemental video. If more control over the animation is required, we suggest adding an additional density parameter to adjust the elasticity of a stem.

To add better real-time editing capabilities, we extend the stem trajectory computation of (Level0-3).

Custom Spline Editing We can bias the stem transformations of a tree trunk towards $b$ user-defined transformations. Let $c$ be the number of stem segments. The $i$-th segment transformation with is biased towards the relative next user transformation $j\; =\; \backslash left\backslash lfloor\; \backslash frac\{ib\}\{c\}\; \backslash right\backslash rfloor$, . We use this feature in Sec. 4 with two custom transformations to model hedge arches of our park test scene.

Object Pruning Vegetation growing through solid walls is a common immersion-breaker. We can decide to shorten stems if they collide with certain objects. We use hardware ray-tracing to shoot rays into the growth direction [KOF*24]. If there is a hit, we shorten the length of the stem accordingly.

Mesh Group Coalescing In early experiments, we noticed a drastic performance improvement by combining multiple dispatches to mesh nodes into a single one. Thus, similar to the (BundleLeaves) node, we also employ a bundler node in coalescing launch mode before launching any mesh node. Note that this optimization might not apply to other architectures or driver versions.

Quad Stem Dispatching a full mesh shader group for small stems only consisting of two triangles and four vertices is wasteful. To optimize this, we employ a special bundler and mesh node that renders a bundle of several of these quads per group, similar to the leaves bundling. This is again implemented as a node array. In the future, it could be feasible to employ even more specialized mesh shaders for different tessellation scenarios.

Stem Leaves Mesh Node As described in Sec. 3.2, we omit thin stems for rendering. We extend this idea by creating a special mesh node (DrawStemLeaves) that creates and samples a stem spline to only output the geometry for the leaves. The actual stem geometry is not drawn. With this node, we can skip the generation of the last stem level at far camera distances.

Record Compression To save on memory bandwidth and capacity during work graph execution, we propose to compress work records when submitting them and to decompress again on node launch. Besides using trivial bitfield compression of limited range integers like the tree level or type, we extend the octahedron mapping for unit vectors [MSS*10] to compress the rotational component of the stem transformations, thus a unit quaternion. For compression, we quantize the imaginary parts of the quaternion in L1 norm into 10 bits each and store them, along with the sign bit of the original real component, in 32 bits. This enables storing an entire stem transformation in 4 hardware dwords. While it is often feasible to omit the sign bit of the real component by negating the whole quaternion when , we include it for correct interpolation of the stem tessellation frames.

We use deferred rendering [DWS*88] with shadow mapping [WSP04]. That would typically require a geometry pass to fill the G-buffers, a shadow pass to create a shadow map, and a composition pass to compute lighting. This, however, would force us to store the full generation result, or to generate geometry twice, i.e., once for the geometry and once for the shadow pass. Instead, we propose to fuse geometry and shadow pass and run the inner work graph nodes of our generation only once. For this, we submit to an extra mesh node that creates our shadow map in our graph of (1):

(DrawStem) and (DrawLeaves) are the nodes that fill the G-buffers. We duplicate them to (DrawStemShadow) and

(DrawLeavesShadow) to create our shadow map. For those nodes, we can apply several shadow-map generation optimizations: we create geometry at a lower level-of-detail, evict the pixel shader, and tune pipeline-state and mesh shader. Note that (Level0-3) must execute on the union of the light and the camera frustum.

Shadow nodes and non-shadow nodes must operate on distinct depth buffers. However, we cannot switch depth buffers during a work graph launch. Instead, we create a single depth buffer large enough for both tasks. Then, we partition it into two texture array slices, and set the corresponding slice index in the mesh shaders.

Dynamic resolution scaling (DRS) [Bin11] is a common optimization for video games. Here, the rendering resolution is dynamically reduced for demanding scenes to meet a target frame time. However, sudden resolution changes are conspicuous and can break effects based on temporal accumulation. As our generation runs every frame and changing quality is continuous, we can dynamically adjust the geometric detail of our trees. For each quality parameter, like the pixels per triangle from Sec. 3.2 or the leaf density from Sec. 3.3, the user configures an acceptable range. The parameter ranges are then ordered by priority: the least noticeable parameter gets degraded first if the performance goal was not met in the last frame. If the performance is better than the goal, the parameters are reverted again. Constraining the maximum rate of change of the parameters assures that no sudden quality change occurs.