1. Introduction

There exist a variety of methods used to make a user feel more immersed in a virtual environment. Some of these methods rely on making the experience more immersive through providing the user with more means of interacting with the environment while other methods focus on doing this through making the environment more realistic visually. The rest of this document will concentrate on the latter methods.

In recent years, a number of rendering techniques have emerged in order to make the virtual environment more 'real'. These include techniques such as texture mapping, perspective projection, realistic lighting and shadows. What all these methods have in common is that they are all applied to geometry that needs to be defined prior to rendering.

Lindenmayer Systems (L-Systems) and Fractals provide us with interesting methods to generate geometry that can further be enhanced through the application of the techniques mentioned in the previous paragraph.

At this point I would like to introduce the reader to Lindenmayer systems (L-Systems). L-systems are a mathematical formalism proposed by the biologist Aristid Lindenmayer in 1968 as a foundation for an axiomatic theory of biological development [1]. Alternatively, L-systems represent a mathematical model for the simulation of biological growth. Recent research indicates that L-systems have found a great deal of uses in computer graphics. Prusinkiewicz [2] used turtle graphics to interpret the L-Systems and so obtain their graphical representation. This spawned new interest in the field of L-Systems as the work of Prusinkiewicz allowed the systems to be visualized.

Further research in the field has led to many extended capabilities of L-Systems. These are among others Parametric L-Systems where numerical attributes are assigned to the components of the L-System and Stochastic L-Systems where the elements of randomness and probability are introduced. These developments allowed more control of the L-System and so it allowed the L-Systems to generate more predictable geometry. Further work by Prusinkiewicz led to the development of L-Systems that allow a plant to react to environmental constraints such as walls. His work also allowed for more accurate modeling of plants not only in terms of geometry but also in terms of the life cycle of a plant. It made possible the modeling of a plant that will grow, evolve and eventually die.

The capabilities of L-Systems make them well suited to virtual environments. Since the goal of a virtual environment is to make the environment resemble the outside world as closely as possible, and since L-Systems provide us with a method to describe natural phenomena, they have a lot of potential in making the virtual environment more immersive.

Their most extensive use is, of course to generate vegetation. Bruce Damer, Stuart Gold, Karen Marcelo, Frank Revi use L-Systems in their 'Nerve Garden' [4] project to allow users to plant trees in inhabited virtual worlds. The user generates a L-system consisting of an axiom (start state) and a set of rules or productions. The axiom and productions are generated through an interactive java applet. The resulting grammar of the tree is then sent to the virtual world and the tree is grown. L-Systems have also been used extensively in virtual environments for the purpose of animation. The interaction between vector fields and L-Systems has been studied in [3]

2. Problem Statement

A great deal of research in the field of L-System is directed at finding ways of extending the capabilities of the systems in order to make the systems capable of modeling the different forms of life in nature [2] (e.g. Parametric Systems, Stochastic Systems, Context Free Systems). In light of this and with Virtual Environments in mind it will be interesting to investigate how applicable L-systems are in comparison to other generative techniques when it comes to rendering certain components of virtual environments.

The components of which are worth investigating are: terrain, plants, water runoff systems, clouds, humans. The research will consist of identifying and studying methods employed by other researchers and experts of generating the above mentioned components. These methods will then be implemented for research purposes and compared with the L-System approach of generating the same component.

For example, in the case of generating trees, one might look at methods like the simple construction of the tree using a 3D modeling package and then importing it into the virtual environment, or one might take some recursive approach to generating the tree, one might even use a fractal approach. All these methods will be put up against the L-system approach and then evaluated using certain criteria.

The criteria that come to mind are:

· Appearance

· Control

· System resource use

· Abilities

I will briefly explain each of these in the following paragraphs.

2.1 Appearance

In this regard I would like to pay attention to how closely each of the methods employed, including L-systems resemble the feature being modeled. The results of the methods excluding L-systems will also be contrasted against the result obtained using the L-System approach

2.2 Control

This measure will deal with the effort needed to get as close to the desired result as possible. In other words, how much tweaking do each of the methods require before they generate the expected geometry as opposed to L-systems. Also under this heading will be the question of how many 'knobs and buttons' does the method let us control in order to define the final result.

2.3 System resource use

All techniques that can be employed in order to render elements of the environment will use up system resources, especially generative techniques that constantly grow and evolve. This criterion will attempt to evaluate how much system resources, such as memory and processing time the technique requires. From this I expect to be able to make recommendations as to which method to use. For example, while an L-System might cause a drop in frame rate over another method, the improvement it adds to the landscape visually may be well worth the loss in performance.

2.4 Abilities

Under this topic I would like to investigate how many abilities each of the techniques have. By abilities I mean the 'features' a particular technique presents. It might be easy to achieve a certain goal using one technique but far more difficult to do so using another. The abilities of each technique will be identified and weighed against each other.

3. Literature Survey

The literature for this research project will in its majority be in the form of research papers found in journals, libraries and the World Wide Web. Use will also be made of the findings of other researchers in the VRSIG group. A fair amount of elementary material in the form of tutorials downloadable from the web will also be used in the initial programming phases. A number of papers and articles have been reviewed for this proposal, some of these are listed at the end of the document.

4. Design Considerations

Development of applications needed for the completion of the research will be done in Java. The operating system used will be Linux. Extensive use will be made of the OpenGL graphics library.

5. Goals

· To gain a firm understanding of L-Systems and other generative techniques.

· To gain knowledge in the way L-Systems differ form other generative techniques.

· Implement some of the available generative techniques, including L-Systems for research purposes.

6. End result

· An understanding of L-Systems and other generative techniques.

· An evaluation of L-Systems as opposed to other generative techniques.

· An implementation of L-Systems and other generative techniques under the Rhodes Virtual Environment. · Recommendations as to what generative techniques to use under certain circumstances.

· A document on the findings

References:

[1] Ochoa G An Introduction to Lindenmayer Systems Available at: http://www.cogs.susx.ac.uk/users/gabro/lsys/lsys.html#OLR

[2] Przemyslaw Prusinkiewicz, Mark Hammel, Radomir Mech, and Jim Hanan. The artificial life of plants. In Artificial life for graphics, animation, and virtual reality, volume 7 of SIGGRAPH '95 Course Notes, pages 1-1 - 1-38. ACM SIGGRAPH, 1995.

[3] Noser H, Turner R, Thalmann D (1992) Animation Based on the Interaction of L-Systems with Vector Force Fields

[4] Damer B, Marcelo K, Revi F Nerve Garden: a Public Terrarium in Cyberspact available at:http://www.biota.org/papers/ngalife.htm