Procedural Trees.pdf

(1833 KB) Pobierz
White Paper
Intel Software and Services
Group
Hugh Smith
Procedural Trees and
Procedural Fire in a
Virtual World
October 2008
Intel Corporation
Contents
1
2
Introduction ...............................................................................................................................................................................................3
Trees ............................................................................................................................................................................................................5
2.1
2.2
3
3.1
3.2
3.3
4
5
6
Tree Properties and Fire ........................................................................................................................................................... 5
Tree Parser and Grammar ........................................................................................................................................................ 5
Level Grammar ................................................................................................................................................................................ 8
Canopy Grammar ............................................................................................................................................................................ 8
Split Grammar................................................................................................................................................................................... 9
Grammar .....................................................................................................................................................................................................7
Parser ........................................................................................................................................................................................................ 12
Procedural Fire ..................................................................................................................................................................................... 18
Smart Particle Engine ........................................................................................................................................................................ 20
6.1
6.2
6.3
6.4
Spreading Fire: Particles and Emitters ...........................................................................................................................20
6.1.1
Some Examples ......................................................................................................................................................23
Heat Particle Interaction ........................................................................................................................................................27
Fire Interaction .............................................................................................................................................................................28
Heat Particle Behavior.............................................................................................................................................................29
7
8
9
10
11
Future Considerations ....................................................................................................................................................................... 32
Conclusions ............................................................................................................................................................................................. 34
Appendix A Grammar and Parser Details ................................................................................................................................ 35
References and Related Articles.................................................................................................................................................. 39
About the Author ................................................................................................................................................................................ 40
2
White Paper
Procedural Trees and Procedural Fire
1
Introduction
The Tree and Fire Systems are part of the
Intel Smoke Framework,
a multi-threaded game engine.
Procedurally generated trees and procedurally generated fire were inspired by the need to generate a
virtual burning forest.
To animate a burning forest, you must illustrate many natural variables. To be convincing, procedurally
generated content must be predictable and consistent, yet must also have believable variation. This
paper explores the implementation of the Tree and Fire Systems for procedurally generated trees and
the procedurally generated fire. It also describes the creation and implementation of the grammar and
parser used to create the trees, as well as examining the Fire System which uses the Smart Particle
Engine to set the trees on fire.
Figure 1 The Forest
3
Procedural Trees and Procedural Fire
White Paper
Figure 2 The Forest on Fire
4
White Paper
Procedural Trees and Procedural Fire
2
Trees
Trees are naturally complex. Nature has given us what seems to be a never ending array of tree species
and foliage. As a developer, when simulating trees with a procedural methodology, you must consider
what differentiates a tree from a bush and one tree from another. You must also familiarize yourself with
the tree structure including how the branches join the trunk and how the canopy affects the overall
shape of the tree. How do you create algorithms and structures that can capture the essence of trees?
All trees are similar but no two trees are alike, so your algorithm must provide believable variation. How
do you create an algorithm that will procedurally create similar but not identical instances of trees? This
is the world of simulating natural vegetation and this section explores how to create procedurally
generated trees. There are many resources available about graphically simulating natural vegetation, but
one stands out: “The Algorithmic Beauty of Plants” by Przemyslaw Prusinkiewicz and Aristid Lindenmayer
[1]. This paper is recommended for anyone interested in exploring this topic in more depth.
2.1
Tree Properties and Fire
To create a burning tree, you must consider the tree in detail. Creating individual trees in a modeling
program with an artist is one way to get good looking trees, but this method limits the number of trees
you can create and the result is just a basic model of vertices and triangles. A modeled tree looks like a
tree but it does not contain the necessary context or structural data you need to associate it with a
context sensitive fire. If you are going to set your tree ablaze, unless you want to paste a generic fire
particle engine on each tree, you need more information about the tree.
For each tree or group of trees you must consider how the behavior of fire is affected by the structure of
the trees. For example:
fire spreads - it spreads upwards and outwards, and spreads from branch to branch based on fuel
and locality
fire forms to the fuel - it takes the shape of the fuel source, and because each tree is different the
fire should form to it differently
With these properties in mind, the need to generate trees in a procedural manner is apparent.
2.2
Tree Parser and Grammar
To create procedural trees a general tree parser was implemented that when given a grammar describing
a tree species, produces a specimen tree of that grammar type. Using the parser is as simple as sending
the parser a grammar and a random seed; it creates a unique deterministic tree based on your input. Plant
a seed and grow a tree.
The tree parser is a separate external library used by the Tree and Fire Systems projects. This is to
ensure that you can easily use the tree parser library in separate projects as needed or desired.
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin