Looking back in time it is possible to understand how fast technology is being developed and improved. With new technologies being developed also new objectives are desired to achieve. Computer Graphics is not exception and it is using all the technology available to be as accurate as possible. There is still much room for improvement as new technologies are developed. With the development of more powerful technologies like programmable graphic processors (GPUs), advanced techniques for creating better computer graphics are also developed. “Most of these advanced modeling techniques can be considered procedural modeling techniques: code segments or algorithms are used to abstract and encode the detail of the model instead of explicitly storing vast number of low-level primitives.” [Advanced Modeling Techniques for Computer Graphics]

This means that in the example of a game some math algorithms are used to create some objects instead of storing all the required objects as images. Storing all these objects would take too much storage space and the same rendering speed would not be possible.

 

“Traditionally when we think of procedural computer graphics, we think of techniques such as fractals for modeling terrain, Lsystems for modeling plants and trees, rigid and elastic body dynamics for modeling hard and soft collisions between objects, and particle systems for modeling water, fire, and smoke.” [AL: A Language for Procedural Modeling and Animation]

These and other techniques will be looked in more detail.

But what is in fact a Procedural Technique? As Texturing & Modeling book defines it is a “code segment or algorithm that specifies some characteristic of a computer-generated model or effect.” Procedural techniques are a fast and effective way of getting good quality models rendered.

 

When developing a realistic model it is important to make a good use of appropriate textures. It makes it more realistic and perfect. “Texturing is a method of varying the surface properties from point to point in order to give the appearance of surface detail that is not actually present in the geometry of the surface.” [Texturing & Modeling]

Procedural Textures were created taking into account that a realistic scene can have hundreds or even thousands of different textures. This way, as for modelling objects, also for textures it is possible to use algorithms instead of storing all the different patterns.

“Procedural texture allows an algorithm to describe how a texture surface should appear.” [Image-Driven Procedural Texture Specification]

So, a single procedure can specify a wide range of textures being then a great advantage to use procedural texturing. Characteristics like “abstraction, parameterization, resolution independence, and a compact representation” are also great advantages of using procedural texturing. [Image-Driven Procedural Texture Specification]

 

There are many different procedural texture techniques. One of them published in the proceeding of ACM SIGGRAPH 2003 Symposium on Interactive 3D Graphics is the Pattern Based Procedural Texture. It is based in an “algorithm which procedurally determines the texture value at any surface location by aperiodically combining provided patterns according to user-defined controls such as a probability distribution (possibly non stationary).” [Pattern Based Procedural Textures]

Another Procedural Texture technique starts as a “way of finding which one of a set of points was closest to a given point. If a plane is mapped so that its colour at any place represents which of the set of points was closest, the pattern resulting looks like the walls of joined soap bubbles. If one modifies the part of the algorithm which determines which point is chosen as closest, different and more interesting patterns appear.” [A Simple, Versatile Procedural Texture]

 

The use of procedural texturing is not new. Since texture mapping was introduced to computing different techniques started being used specially by researchers. Fourier synthesis is the first known synthetic texture modelling technique and it was developed by Blinn and Newell in 1976. During that time many different ones were developed like grammar based and stochastic subdivision (“fractal”) techniques.

In 1984 it started being important to generate procedural textures during rendering and so the “shade trees” was created being the first system with this characteristic. “Shade trees enable the use of a different shading model for each surface as well as for light sources and for attenuation through the atmosphere.” [Texturing & Modeling] This happens because it is possible to manipulate procedurally the inputs to the shading models. With this method it is possible to control any part of the shading calculation. There are many more procedural texture techniques. Some of these techniques are known as procedural “solid” texturing and they differ from “surface” techniques for being compact and possible to be synthesized dynamically on demand. “Solid texturing is also easier than surface texturing because it does not require a surface parameterization.” [Texturing & Modeling]

Real-Time Procedural Solid Texturing Algorithm is one of the methods used for procedural solid texturing. It is based in a Renderman technique. Renderman is a technology developed by Pixar that will be explained later in this report. This Real-Time Algorithm is run in three phases. Rasterization, Procedural Evaluation and Texture Mapping.

 

Another and maybe the more important technique is the Fractal. “Fractals models can be used to construct scenes with good realism and high degree of visual complexity, but they effectively address only a limited range of phenomena.” [Texturing & Modeling]

Fractal geometry is a user friendly form of mathematics. It can also be considered as a new form of symmetry. It is “a rough or fragmented geometric shape that can be subdivided in parts, each of which is (at least approximately) a reduced-size copy of the whole” [The Fractal Geometry of Nature]

 

There are also volumetric textures. It can be defined as: “A texture that is described in three dimensions. It can be created as a "stack" of 2D bitmapped textures or as a 3D procedural texture. When an object with volumetric texture is sliced in half, the texture would still be rendered accurately on the inside.”

[computing-dictionary.thefreedictionary.com]

The use of procedural texture techniques in 3D (volumetric) objects has a vast range of advantages as it has for 2D techniques. The speed of the rendering, making it possible to render in real time and the quality of definition are some of them but in this case there are also some new effects that can be created like explosions or clouds. One of the few disadvantages is the need for more rendering power in order to better process the volumetric textures.

Patterns can be found in the real world all around us. It is from these patterns that volumetric texturing techniques as other procedural techniques are developed. In the images below it is possible to see some patterns.

 

2D Texture Images.

Images from: [3-D (volumetric) Texture Analysis]

 

Procedural textures are being used in many games already and the future reserves much more for this technique. One example of a game using it is Oblivion. “Oblivion uses a system called Speedtree to generate the game's apparently never-ending trees and foliage. Speedtree is middleware that uses procedural synthesis to randomly generate realistic foliage, guaranteeing that no one will ever see the exact same trees in two different games of Oblivion.” [About.com]

Oblivion Game Screen

Image from – [About.com]

 

Other game using Procedural techniques is Darwinia. “It also uses Procedural Synthesis to generate the landscapes you find in the game.” [About.com]

Darwinia Game Screen

Image from – [About.com]

 

There is also a game that won a German Developer Awards. It is only 96 Kilobytes big. It is called .kkrieger and it looks great as it can be seen in the image below.

 

.kkriege Game Screen

Image from - [About.com]

 

 

But there is not only in games that procedural techniques are used. Architecture is one of the examples where it can be used as seen on the example below.

 

Example of Procedural Modeling in Architecture

Image from - [Procedural Modeling of Buildings]

 

The technique used is shape grammar (called CGA shape).

“First, the grammar generates procedural variations of the building mass model using volumetric shapes and then proceeds to create facade detail consistent with the mass model. Context sensitive rules ensure that entities like windows or doors do not intersect with other walls, that doors give out on terraces or the street level, that terraces are bounded by railings, etc.” [Procedural Modeling of Buildings]

With this method entire cities can be created in a way that to model it in the conventional way it would take years of many people modelling it to get the same result. Procedural Modeling of Buildings is an article where it is possible to understand better and see more examples of this technique. One of the examples can be seen below.

 

City built using CGA shape technique

Image from - [Procedural Modeling of Buildings]

 

Procedural techniques can also be found in Film. Films like King Kong used procedural techniques in some part of it. “…and the first pass of shading and lighting used procedural techniques”. [FXGuide]

Harry Potter is another example. As Tim Webber, Director of Visual Effects said in an interview at VFXTalk.com:

“We looked at a lot of reference photos of underwater scenes and spent a long time developing procedural techniques to cover objects. We had a number of different affects that were procedural but that we could control with painted maps - short moss, long moss, various small plants and ocassionally we added barnacles into texture and displacment maps.” [VFXTalk]

 

One of the more common procedural techniques is Tessellation. It is used to create textures giving a material property to an object modelled. Tessellation can be found in the real world in examples like Art or Nature. The bee honey combs are one of the examples. Basically what this technique does is to divide datasets of polygons into suitable structures for rendering. It is common that in real time rendering the division is made in triangles what can also be called as triangulation.

 

Tessellation example

Image from – [Wikipedia]

 

When we talk about creating (modelling) objects using procedural techniques we are talking about Procedural Geometry.

Procedural Geometry is a method created to model natural shapes like plants. Using procedural geometry it is possible to create a tree as it is a whole forest. However procedural geometry is not limited to nature shapes, it can be used in building buildings or even cities as mentioned earlier when talking about CGA shape technique.

 

L-System is the procedural geometry technique more popular. It was invented by Lindenmayer in 1968 but was then developed by Prusinkiewicz to modelling the behaviour of plant growth. “The L-System is a grammar of replacement rules that capture various self-similar aspects of biological shape and development. The grammar operates on a set of turtle graphics symbols that translate the words generated by the grammar into graphical objects.” [Texturing & Modeling]

The L-systems algorithm is similar to the Fibonacci sequence being Fibonacci sequence an addition of each number with the previous one giving the next one.

1 1 2 3 5 8 13 21 34 55 89 ...

The L-systems can be used with letters giving a defined set of rules.

Having A and B as variables, starting with A and using the rule of A turning into AB and B turning into A we have the next sequence:

A AB ABA ABAAB ABAABABA

If instead of having A becoming AB we have A becoming B and B becoming AB the result is going to be:

A B AB BAB ABBAB BABABBAB ABBABBABABBAB

 

The Koch curve is also used as a base for L-Systems. Lets use F to represent drawing a line, + to turn 90º to the left and – to turn 90º to the right. Using the follow as a rule F → F+F−F−F+F we have:

n = 0:

F

n = 1:

F+F-F-F+F

n = 2:

F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F

n = 3:

F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F- F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F+ F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F

Examples from – [Wikipedia] and supported by [Texturing & Modeling]

 

Those examples are the basic ones and so this technique can be used in much more deeper algorithms using the same idea.

 

Another way of creating objects in a procedural way is using points. “Point based rendering methods represent the scene’s geometry as a set of point samples, that is object space position, surface normal and material data. Usually, the point samples are obtained from images of the scene that include depth and material information, but they are rendered and lit as independent small polygons or oriented disks. It has been shown that such point sample representation are well suited both for fast rendering of extremely complex geometry and for high-quality visualisation.” [Interactive Sampling and Rendering for Complex and Procedural Geometry]

 

In this report the word render has been mentioned many times being the rendering one of the most important processes in computer graphics. It is also the one that is important to have in attention during the development process as it is important to think about making it the fastest as possible. “Render is the process of generating an image from a model”. [Wikipedia]

 

 

As mentioned before the rendering time is one of the reasons for the development of procedural techniques. Pixar Animation Studios developed an Application Programming Interface (API) called Renderman to turn three dimension scenes into images with digital photorealistic quality.

“Renderman is first of all a scene description methodology: a comprehensive way to describe objects, scenes, lights and cameras so that a computer can create images from them.” [The Renderman Companion]

“RenderMan is often used in creating digital visual effects for the Hollywood blockbuster movies of today such as Star Wars and The Lord of the Rings.” [Wikipedia]

The use of this application in great part of the films using the more modern and advanced computer graphics images show that it is really a great achievement for the computer graphics world. All these films take enormous amounts of time to render and they are only available when ready. The good point is that everything is fixed and is the same every time it is watched, but the same does not happen with games. In a game the scene is always changing and everything depends on what the player is doing. It is easy to imagine a car game and how a player can drive faster or slower, on the street or outside it. As said previously, it would take an enormous amount of disk space to save all the objects and background details to be displayed during the game. Because of that procedural techniques are a great step for computer graphics in order to create the objects in real time. However there is a need for good hardware in order to render the procedural content in real time and so the use of it in games is increasing at the same time as the hardware is also getting better.

 

The ROAM algorithm is another of the many algorithms for real time rendering. ROAM stands for Realtime Optimally-Adapting Meshes.

“Real time display of complex surfaces is provided by dynamically computing a multi resolution triangular mesh for each view. The meshes minimize geometric distortions on the screen while maintaining a fixed triangle count. Pop-ups are minimized in several ways, and efficient mesh corrections ensure selected lines of site or object proximity are correctly represented. An incremental priority-queue algorithm uses frame-to-frame coherence to quickly compute these optimal meshes.” [ROAM Algorithm]

 

It does not seem that procedural techniques are going to replace the traditional manual approaches but they are already and will be even more in the future a great help to get better results in terms of rendering time and image quality. They are helping to simplify the developers work getting them to concentrate more in the main aspects of the application and let the procedural techniques do the remaining part. Computer Graphics, as the name says, is a connection between the computer and the graphics. The procedural techniques are more a computer and mathematical part of it allowing the artist do the main objects creating themselves the graphics with traditional methods using software’s like 3D Studio Max or Maya.

 

So, to sum up, procedural techniques are a very important part of computer graphics. This report mentions various procedural techniques from modelling to texturing from all the great number of techniques that exist. The process of writing this report was also a process of learning to the student as at the beginning of it everything regarding procedural techniques where a mystery to him. There are actually a great amount of resources available to get information about the subject and so the reading part of this assignment was even more time consuming than writing it. The student feels that it is very important to have the knowledge acquired with this assignment and it is also important to keep researching about the subject. At the end there is still a feeling that much more is possible to say but these can be a good start to understand what procedural techniques are.

 

 

 

 

References

 

 

Books

 

Akenine-Moller, T., Haines, E. (2002). Real-Time Rendering, Second Edition. A K Peters, LTD.

Ebert, D., Musgrave, F., Peachey, D., Perlin, K., Worley, S. (2003). Texturing and Modeling: A Procedural Approach. Third Edition. Morgan Kaufmann Publishers.

Upstill, S. (1990). The RenderMan Companion: A Programmer´s Guide to Realistic Computer Graphics. Pixar. Addison-Wesley Publishing Company.

 

 

World Wide Web

 

About.com

http://nintendo.about.com/library/procedural/blprocedural4.htm

 

AL - Advanced Models

http://accad.osu.edu/research/misc_htmls/al.htm

 

Computer Dictionary

http://computing-dictionary.thefreedictionary.com/volumetric%20texture

FXGuide

http://www.fxguide.com/fxblog1677-print.html

 

Karim Ratib - Multi-Resolution Volumetric Texture for the Display of Complex

http://www.iro.umontreal.ca/labs/infographie/projects/texels/texels-en.html

R. L. Summerscales (2005) 3-D (volumetric) Texture Analysis http://www.andrews.edu/~summersc/texture3d.html

Pixar – Renderman

https://renderman.pixar.com/

 

Procedural Modeling of Urban Environments

http://theschwartz.wordpress.com/2006/07/30/procedural-modeling-of-urban-environments/

PURPL - Procedural Techniques for Computer Graphics

http://www.ecn.purdue.edu/purpl/projects/PTCG

 

Roam Algorithm

http://www.cognigraph.com/ROAM_homepage/

Speed Tree

http://www.speedtree.com/

VFXTalk

http://www.vfxtalk.com/forum/showthread.php?t=6820

 

Wikipedia

http://en.wikipedia.org/wiki/Fractals

http://en.wikipedia.org/wiki/L-system

http://en.wikipedia.org/wiki/Procedural_modeling

http://en.wikipedia.org/wiki/Procedural_generation

http://en.wikipedia.org/wiki/Procedural_texture

http://en.wikipedia.org/wiki/RenderMan_Interface_Specification

http://en.wikipedia.org/wiki/Rendering_%28computer_graphics%29

http://en.wikipedia.org/wiki/Tessellation

 

 

Articles

Burchil, L. – Graphics Goodies # 2: A Simple, Versatile Procedural Texture

Available at: http://delivery.acm.org/10.1145/50000/48159/p29-burchill.pdf?key1=48159&key2=6894733711&coll=GUIDE&dl=GUIDE&CFID=14973304&CFTOKEN=11550811

 

Eck, M., DeRose, T., Duchamp, T. – Multiresolution Analysis of Arbitrary Meshes

Available at: http://research.microsoft.com/~hoppe/mra.pdf

Ebert, D. (1995). Advanced Modeling Techniques for Computer Graphics

Available at: http://coblitz.codeen.org:3125/citeseer.ist.psu.edu/cache/papers/cs/1232/http:zSzzSzwww.cs.umbc.eduzSz~ebertzSzpaperszSzacm_cs_final.pdf/ebert97advanced.pdf

Ebert, D. – Procedural Techniques and Real-Time Graphics

Available at: http://citeseer.ist.psu.edu/cache/papers/cs/30730/http:zSzzSzdynamo.ecn.purdue.eduzSz~ebertdzSzpaperszSzSnowbird_2002.pdf/procedural-techniques-and-real.pdf

and

http://cobweb.ecn.purdue.edu/~ebertd/papers/Snowbird_2002.pdf

Fractals

Available at: http://www.cs.sunysb.edu/~skiena/691/lectures/lecture12.pdf

Hart, E. – 3D Textures and Pixel Shaders

Available at: http://ati.de/developer/shaderx/ShaderX_3DTextures.pdf

 

Hewgill, A., Ross,B. – The Evolution of 3D Procedural Textures

Available at: http://www.cosc.brocku.ca/~bross/research/gen3d_LBP.pdf

Lefebvre, S., Neyret, F. – Pattern Based Procedural Textures

Available at: http://evasion.imag.fr/Publications/2003/LN03/pattern_based_procedural_textures.pdf

M. Isenburg, P. Lindstrom, S. Gumhold, and J. Snoeyink (2003). Large Mesh Simplification using Processing Sequences

Available at: http://www-static.cc.gatech.edu/~lindstro/papers/vis2003/paper.pdf

Mandelbrot, B. B. (1982). The Fractal Geometry of Nature. W. H. Freeman and Company.. ISBN 0-7167-1186-9

May, S., Carlson, W., Phillips, F., Scheepers, F. (1996). AL: A Language for Procedural Modeling and Animation

Available at: http://accad.osu.edu/~smay/al.pdf

 

Muller, P., Wonka, P., Haegler, S., Ulmer, A,. Gool, L. – Procedural Modeling of Buildings

Available at: http://www.public.asu.edu/~pwonka/Publications/mueller.procedural%20modeling%20of%20buildings.SG2006.final-web.pdf

 

Neyret, F. (2003). Advected Textures. Eurographics/SIGGRAPH Symposium on Computer Animation.

Available at: http://www-evasion.imag.fr/Publications/2003/Ney03/neyret161.pdf

 

R.L. Summerscales, (2005), Three-dimensional texture classification using the discrete cosine transform, M.S. Thesis, Pennsylvania State University.

Available at: http://www.andrews.edu/~summersc/msthesis.pdf

 

The RenderMan Interface: Version 3.2 (2000)

Available at: http://local.wasp.uwa.edu.au/~pbourke/dataformats/rib/RISpec3_2.pdf

 

Schoenberg, F. – Tessellations

Available at: http://www.stat.ucla.edu/~frederic/papers/tessellations.pdf

Smith, A. – Plants, Fractals, and Formal Languages

Available at: http://delivery.acm.org/10.1145/810000/808571/p1-smith.pdf?key1=808571&key2=2303812711&coll=portal&dl=ACM&CFID=15071719&CFTOKEN=69932531

Stamminger, M., Drettakis, J. (2004). Interactive Sampling and Rendering for

Complex and Procedural Geometry

Available at: http://www.inf.uni-konstanz.de/cgip/ruggeri/PB3DGSemWS03-04/PBRPapers/StamDret01.pdf