UCT CS Research Document Archive

Real-time Generation of Procedural Forests

Kenwood, Julian (2014) Real-time Generation of Procedural Forests. MSc, Department of Computer Science, University of Cape Town.

Full text available as:
PDF - Requires Adobe Acrobat Reader or other PDF viewer.


The creation of 3D models for games and simulations is generally a time-consuming and labour intensive task. Forested landscapes are an important component of many large virtual environments in games and film. To create the many individual tree models required for forests requires a large numbers of artists and a great deal of time. In order to reduce modelling time procedural methods are often used. Such methods allow tree models to be created automatically and relatively quickly, albeit at potentially reduced quality. Although the process is faster than manual creation, it can still be slow and resource-intensive for large forests.

The main contribution of this work is the development of an efficient procedural generation system for creating large forests. Our system uses L-Systems, a grammar based procedural technique, to generate each tree. We explore two approaches to accelerating the creation of large forests. First, we demonstrate performance improvements for the creation of individual trees in the forest, by reducing the computation required by the underlying L-Systems. Second, we reduce the memory overhead by sharing geometry between trees using a novel branch instancing approach.

Test results show that our scheme significantly improves the speed of forest generation over naive methods: our system is able to generate over 100, 000 trees in approximately 2 seconds, while using a modest amount of memory. With respect to improving L-System processing, one of our methods achieves a 25% speed up over traditional methods at the cost of a small amount of additional memory, while our second method manages a 99% reduction in memory at the expense of a small amount of extra processing.

EPrint Type:Electronic Thesis or Dissertation
Keywords:Procedural forest generation
Subjects:J Computer Applications: J.3 LIFE AND MEDICAL SCIENCES
I Computing Methodologies: I.m MISCELLANEOUS
I Computing Methodologies: I.3 COMPUTER GRAPHICS
I Computing Methodologies: I.6 SIMULATION AND MODELING
ID Code:941
Deposited By:Marais, Patrick
Deposited On:15 July 2014