Inverse Procedural Modelling of Trees

Procedural tree models have been popular in computer graphics for their ability to generate a variety of output trees from a set of input parameters and to simulate plant interaction with the environment for a realistic placement of trees in virtual scenes. However, defining such models and their parameters is a difficult task. We propose an inverse modelling approach for stochastic trees that takes polygonal tree models as input and estimates the parameters of a procedural model so that it produces trees similar to the input. Our framework is based on a novel parametric model for tree generation and uses Monte Carlo Markov Chains to find the optimal set of parameters. We demonstrate our approach on a variety of input models obtained from different sources, such as interactive modelling systems, reconstructed scans of real trees and developmental models.     

Variational Tree Synthesis

Modelling trees according to desired shapes is important for many applications. Despite numerous methods having been proposed in tree modelling, it is still a non‐trivial task and challenging. In this paper, we present a new variational computing approach for generating realistic trees in specific shapes. Instead of directly modelling trees from symbolic rules, we formulate the tree modelling as an optimization process, in which a variational cost function is iteratively minimized. This cost function measures the difference between the guidance shape and the target tree crown. In addition, to faithfully capture the branch structure of trees, several botanical factors, including the minimum total branches volume and spatial branches patterns, are considered in the optimization to guide the tree modelling process. We demonstrate that our approach is applicable to generate trees with different shapes, from interactive design and complex polygonal meshes.     

Interactive Large‐Scale Procedural Forest Construction and Visualization Based on Particle Flow Simulation

Interactive visualization of large forest scenes is challenging due to the large amount of geometric detail that needs to be generated and stored, particularly in scenarios with a moving observer such as forest walkthroughs or overflights. Here, we present a new method for large‐scale procedural forest generation and visualization at interactive rates. We propose a hybrid approach by combining geometry‐based and volumetric modelling techniques with gradually transitioning level of detail (LOD). Nearer trees are constructed using an extended particle flow algorithm, in which particle trails outline the tree ramification in an inverse direction, i.e. from the leaves towards the roots. Reduced geometric representation of a tree is obtained by subsampling the trails. For distant trees, a new volumetric rendering technique in pixel‐space is introduced, which avoids geometry formation altogether and enables visualization of vast forest areas with millions of unique trees. We demonstrate that a GPU‐based implementation of the proposed method provides interactive frame rates in forest overflight scenarios, where new trees are constructed and their LOD adjusted on the fly.     

Large and Small Eddies Matter: Animating Trees in Wind Using Coarse Fluid Simulation and Synthetic Turbulence

Animating trees in wind has long been a problem in computer graphics. Progress on this problem is important for both visual effects in films and forestry biomechanics. More generally, progress on tree motion in wind may inform future work on two‐way coupling between turbulent flows and deformable objects. Synthetic turbulence added to a coarse fluid simulation produces convincing animations of turbulent flows but two‐way coupling between the enriched flow and objects embedded in the flow has not been investigated. Prior work on two‐way coupling between fluid and deformable models lacks a subgrid resolution turbulence model. We produce realistic animations of tree motion by including motion due to both large and small eddies using synthetic subgrid turbulence and porous proxy geometry. Synthetic turbulence at the subgrid scale is modulated using turbulent kinetic energy (TKE). Adding noise after sampling the mean flow and TKE transfers energy from small eddies directly to the tree geometry. The resulting animations include both global sheltering effects and small scale leaf and branch motion. Viewers, on average, found animations, which included both coarse fluid simulation and TKE‐modulated noise to be more accurate than animations generated using coarse fluid simulation or noise alone.     

Modeling Trees with Hypertextures

In the paper, a new method for modelling trees at medium detail is presented. The method is based on a volumetric representation of trees, generated by an iterated function system (IFS). Alleviating the modeling restrictions of fractal techniques, extensions to the standard IFS are introduced. Practical aspects of modeling and rendering of trees, such as data structures and bounding volumes, are discussed. The advantages of the new method are described at the end together with some results.     

Inverse Modelling of Incompressible Gas Flow in Subspace

This paper advocates a novel method for modelling physically realistic flow from captured incompressible gas sequence via modal analysis in frequency‐constrained subspace. Our analytical tool is uniquely founded upon empirical mode decomposition (EMD) and modal reduction for fluids, which are seamlessly integrated towards a powerful, style‐controllable flow modelling approach. We first extend EMD, which is capable of processing 1D time series but has shown inadequacies for 3D graphics earlier, to fit gas flows in 3D. Next, frequency components from EMD are adopted as candidate vectors for bases of modal reduction. The prerequisite parameters of the Navier–Stokes equations are then optimized to inversely model the physically realistic flow in the frequency‐constrained subspace. The estimated parameters can be utilized for re‐simulation, or be altered toward fluid editing. Our novel inverse‐modelling technique produces real‐time gas sequences after precomputation, and is convenient to couple with other methods for visual enhancement and/or special visual effects. We integrate our new modelling tool with a state‐of‐the‐art fluid capturing approach, forming a complete pipeline from real‐world fluid to flow re‐simulation and editing for various graphics applications.     

Woodification: User‐Controlled Cambial Growth Modeling

We present a botanical simulation of secondary (cambial) tree growth coupled to a physical cracking simulation of its bark. Whereas level set growth would use a fixed resolution voxel grid, our system extends the deformable simplicial complex (DSC), supporting new biological growth functions robustly on any surface polygonal mesh with adaptive subdivision, collision detection and topological control. We extend the DSC with temporally coherent texturing, and surface cracking with a user‐controllable biological model coupled to the stresses introduced by the cambial growth model.     

Matrix Trees

We propose a new data representation for octrees and kd‐trees that improves upon memory size and algorithm speed of existing techniques. While pointerless approaches exploit the regular structure of the tree to facilitate efficient data access, their memory footprint becomes prohibitively large as the height of the tree increases. Pointerbased trees require memory consumption proportional to the number of tree nodes, thus exploiting the typical sparsity of large trees. Yet, their traversal is slowed by the need to follow explicit pointers across the different levels. Our solution is a pointerless approach that represents each tree level with its own matrix, as opposed to traditional pointerless trees that use only a single vector. This novel data organization allows us to fully exploit the tree's regular structure and improve the performance of tree operations. By using a sparse matrix data structure we obtain a representation that is suited for sparse and dense trees alike. In particular, it uses less total memory than pointer‐based trees even when the data set is extremely sparse. We show how our approach is easily implemented on the GPU and illustrate its performance in typical visualization scenarios.     

Boundary Constrained Swept Surfaces for Modelling and Animation

Due to their simplicity and intuitiveness, swept surfaces are widely used in many surface modelling applications. In this paper, we present a versatile swept surface technique called the boundary constrained swept surfaces. The most distinct feature is its ability to satisfy boundary constraints, including the shape and tangent conditions at the boundaries of a swept surface. This permits significantly varying surfaces to be both modelled and smoothly assembled, leading to the construction of complex objects. The representation, similar to an ordinary swept surface, is analytical in nature and thus it is light in storage cost and numerically very stable to compute. We also introduce a number of useful shape manipulation tools, such as sculpting forces, to deform a surface both locally and globally. In addition to being a complementary method to the mainstream surface modelling and deformation techniques, we have found it very effective in automatically rebuilding existing complex models. Model reconstruction is arguably one of the most laborious and expensive tasks in modelling complex animated characters. We demonstrate how our technique can be used to automate this process.     

Linkless Octree Using Multi‐Level Perfect Hashing

The standard C/C++ implementation of a spatial partitioning data structure, such as octree and quadtree, is often inefficient in terms of storage requirements particularly when the memory overhead for maintaining parent‐to‐child pointers is significant with respect to the amount of actual data in each tree node. In this work, we present a novel data structure that implements uniform spatial partitioning without storing explicit parent‐to‐child pointer links. Our linkless tree encodes the storage locations of subdivided nodes using perfect hashing while retaining important properties of uniform spatial partitioning trees, such as coarse‐to‐fine hierarchical representation, efficient storage usage, and efficient random accessibility. We demonstrate the performance of our linkless trees using image compression and path planning examples.     

Visual simulation of botanical trees based on virtual heliotropism and dormancy break

Realistic image synthesis of botanical trees has many applications. Since the generation of ‘tree skeletons’ having natural visual impressions is essential to realistic image synthesis, various methods of modelling skeletons, especially growth models, have been presented. However, no one has succeeded in simulating natural tree features which appear in a growth process, such as generation of a round tree crown, a weeping bough, an irregular branching pattern, or regeneration of a crown. This paper demonstrates, by showing several simulated examples, that a growth model having the abilities of heliotropism and dormancy break, which produces shapes of trees adapted to changes in the light environment, is effective in the CG simulation of realistic tree skeletons.     

Improving Memory Space Efficiency of Kd‐tree for Real‐time Ray Tracing

Compared with its competitors such as the bounding volume hierarchy, a drawback of the kd‐tree structure is that a large number of triangles are repeatedly duplicated during its construction, which often leads to inefficient, large and tall binary trees with high triangle redundancy. In this paper, we propose a space‐efficient kd‐tree representation where, unlike commonly used methods, an inner node is allowed to optionally store a reference to a triangle, so highly redundant triangles in a kd‐tree can be culled from the leaf nodes and moved to the inner nodes. To avoid the construction of ineffective kd‐trees entailing computational inefficiencies due to early, possibly unnecessary, ray‐triangle intersection calculations that now have to be performed in the inner nodes during the kd‐tree traversal, we present heuristic measures for determining when and how to choose triangles for inner nodes during kd‐tree construction. Based on these metrics, we describe how the new form of kd‐tree is constructed and stored compactly using a carefully designed data layout. Our experiments with several example scenes showed that our kd‐tree representation technique significantly reduced the memory requirements for storing the kd‐tree structure, while effectively suppressing the unavoidable frame‐rate degradation observed during ray tracing.     

A Survey of Physically Based Simulation of Cuts in Deformable Bodies

Virtual cutting of deformable bodies has been an important and active research topic in physically based modelling and simulation for more than a decade. A particular challenge in virtual cutting is the robust and efficient incorporation of cuts into an accurate computational model that is used for the simulation of the deformable body. This report presents a coherent summary of the state of the art in virtual cutting of deformable bodies, focusing on the distinct geometrical and topological representations of the deformable body, as well as the specific numerical discretizations of the governing equations of motion. In particular, we discuss virtual cutting based on tetrahedral, hexahedral and polyhedral meshes, in combination with standard, polyhedral, composite and extended finite element discretizations. A separate section is devoted to meshfree methods. Furthermore, we discuss cutting‐related research problems such as collision detection and haptic rendering in the context of interactive cutting scenarios. The report is complemented with an application study to assess the performance of virtual cutting simulators.     

DYVERSO: A Versatile Multi‐Phase Position‐Based Fluids Solution for VFX

Many impressive fluid simulation methods have been presented in research papers before. These papers typically focus on demonstrating particular innovative features, but they do not meet in a comprehensive manner the production demands of actual VFX pipelines. VFX artists seek methods that are flexible, efficient, robust and scalable, and these goals often conflict with each other. In this paper, we present a multi‐phase particle‐based fluid simulation framework, based on the well‐known Position‐Based Fluids (PBF) method, designed to address VFX production demands. Our simulation framework handles multi‐phase interactions robustly thanks to a modified constraint formulation for density contrast PBF. And, it also supports the interaction of fluids sampled at different resolutions. We put special care on data structure design and implementation details. Our framework highlights cache‐efficient GPU‐friendly data structures, an improved spatial voxelization technique based on Z‐index sorting, tuned‐up simulation algorithms and two‐way‐coupled collision handling based on VDB fields. Altogether, our fluid simulation framework empowers artists with the efficiency, scalability and versatility needed for simulating very diverse scenes and effects.     

Mixing Fluids and Granular Materials

Fluid animations in computer graphics show interactions with various kinds of objects. However, fluid flowing through a granular material such as sand is still not possible within current frameworks. In this paper, we present the simulation of fine granular materials interacting with fluids. We propose a unified Smoothed Particle Hydrodynamics framework for the simulation of both fluid and granular material. The granular volume is simulated as a continuous material sampled by particles. By incorporating previous work on porous flow in this simulation framework we are able to fully couple fluid and sand. Fluid can now percolate between sand grains and influence the physical properties of the sand volume. Our method demonstrates various new effects such as dry soil transforming into mud pools by rain or rigid sand structures being eroded by waves.     

Structure from silhouettes: a new paradigm for fast sketch-based design of trees

Modeling natural elements such as trees in a plausible way, while offering simple and rapid user control, is a challenge. This paper presents a method based on a new structure from silhouettes paradigm. We claim that sketching the silhouettes of foliage at multiple scales is quicker and more intuitive for a user than having to sketch each branch of a tree. This choice allows us to incorporate botanical knowledge, enabling us to infer branches that connect in a plausible way to their parent branch and have a correct distribution in 3D. We illustrate these ideas by presenting a seamless sketch-based interface, used for sketching foliage silhouettes from the scale of an entire tree to the scale of a leaf. Each sketch serves for inferring both the branches at that level and construction lines to serve as support for sub-silhouette refinement. When the user finally zooms out, the style inferred for the branching systems he has refined (in terms of branch density, angle, length distribution and shape) is duplicated to the unspecified branching systems at the same level. Meanwhile, knowledge from botany is again used for extending the branch distribution to 3D, resulting in a full, plausible 3D tree that fits the user-sketched contours. As our results show, this system can be of interest to both experts and novice users. While experts can fully specify all parts of a tree and over-sketch specific branches if required, any user can design a basic 3D tree in one or two minutes, as easily as sketching it with paper and pen.     

Biharmonic Coordinates

Barycentric coordinates are an established mathematical tool in computer graphics and geometry processing, providing a convenient way of interpolating scalar or vector data from the boundary of a planar domain to its interior. Many different recipes for barycentric coordinates exist, some offering the convenience of a closed‐form expression, some providing other desirable properties at the expense of longer computation times. For example, harmonic coordinates, which are solutions to the Laplace equation, provide a long list of desirable properties (making them suitable for a wide range of applications), but lack a closed‐form expression. We derive a new type of barycentric coordinates based on solutions to the biharmonic equation. These coordinates can be considered a natural generalization of harmonic coordinates, with the additional ability to interpolate boundary derivative data. We provide an efficient and accurate way to numerically compute the biharmonic coordinates and demonstrate their advantages over existing schemes. We show that biharmonic coordinates are especially appealing for (but not limited to) 2D shape and image deformation and have clear advantages over existing deformation methods.     

Interactive Modeling and Authoring of Climbing Plants

We present a novel system for the interactive modeling of developmental climbing plants with an emphasis on efficient control and plausible physics response. A plant is represented by a set of connected anisotropic particles that respond to the surrounding environment and to their inner state. Each particle stores biological and physical attributes that drive growth and plant adaptation to the environment such as light sensitivity, wind interaction, and physical obstacles. This representation allows for the efficient modeling of external effects that can be induced at any time without prior analysis of the plant structure. In our framework we exploit this representation to provide powerful editing capabilities that allow to edit a plant with respect to its structure and its environment while maintaining a biologically plausible appearance. Moreover, we couple plants with Lagrangian fluid dynamics and model advanced effects, such as the breaking and bending of branches. The user can thus interactively drag and prune branches or seed new plants in dynamically changing environments. Our system runs in real‐time and supports up to 20 plant instances with 25k branches in parallel. The effectiveness of our approach is demonstrated through a number of interactive experiments, including modeling and animation of different species of climbing plants on complex support structures.     

Rendering Trees with Indirect Lighting in Real Time

High quality lighting is one of the challenges for interactive tree rendering. To this end, this paper presents a lighting model allowing real‐time rendering of trees with convincing indirect lighting. Rather than defining an empirical model to mimic lighting of real trees, we work at a lower level by modeling the spatial distribution of leaves and by assigning them probabilistic properties. We focus mainly on precise low‐frequency lighting that our eyes are more sensitive to and we add high‐frequency details afterwards. The resulting model is efficient and simple to implement on a GPU.     

Embedded Implicit Stand-Ins for Animated Meshes: A Case of Hybrid Modelling

In this paper, we address shape modelling problems, encountered in computer animation and computer games development that are difficult to solve just using polygonal meshes. Our approach is based on a hybrid-modelling concept that combines polygonal meshes with implicit surfaces. A hybrid model consists of an animated polygonal mesh and an approximation of this mesh by a convolution surface stand-in that is embedded within it or is attached to it. The motions of both objects are synchronised using a rigging skeleton. We model the interaction between an animated mesh object and a viscoelastic substance, which is normally represented in an implicit form. Our approach is aimed at achieving verisimilitude rather than physically based simulation. The adhesive behaviour of the viscous object is modelled using geometric blending operations on the corresponding implicit surfaces. Another application of this approach is the creation of metamorphosing implicit surface parts that are attached to an animated mesh. A prototype implementation of the proposed approach and several examples of modelling and animation with near real-time preview times are presented.