4.4 Recommended Methods for Hole Generation

4.4 Recommended Methods for Hole Generation

Two methods will be proposed to determine holes position in a tree trunk.

4.4.1 Hole’s Position Based Upon Complex Trunk Surface

This proposed method for the generation of a hole begins by creating a list of all vertices of a trunk model. In a standard 3d model each vertex is connected to the other vertex by an edge. Typically one vertex has three or four connections, meaning three or four edges are connecting it to the other vertex. If we have a list of vertexes and their spacial positions in a 3d coordinate system, we can calculate angles that makes those connections. In order to know the angle we have first to have two edges that directly connect to the vertex we are discussing. Now following the same procedure we can make a list in which all vertices would be sorted out by their edge angular values. The lowest values are a good candidate for the position of a crack in a tree surface or hole.

As figure 32 illustrates the angles are measured on the outside surface of a trunk. In this example angles are calculated only between horizontal edges and not vertical for sake of simplicity. A fully functional approach should be able to handle vertices which have only 3 or another irregular number of connections as opposed to four connections.


Fig 32. Proposals visualization.

The list of vertices and their edges value are sorted, according to their angular value. The lower the value the better a candidate for a hole vertex. In the example described in Figure 32, vertices 5 and 14 have the lowest angular values.

The next step is to determine groups of vertices with low angular values. According to this solution the closer two vertices with low angular values are the better candidates they are for a hole. Priority of a proposed algorithm would be not isolated vertices but instead groups of vertices with low angular values. This method would be one way to determine a possible crack and hole start position.

There are other situations when holes appear, and different methods are still to be found to determine the position of holes. The next section focuses not only on groups of vertices for hole generation but also on the location of these holes and where they might be more appropriate.


You can visit my web page here

dont like english? u can (try) readig it in lithuanian or anny other language here! alternative, has no lithuanian :(


4.3.1 Tools for Automatic Tree Hole Generator

here some tools will be presented which are in 3dmax. the same tools are probably in all 3d modeling programs but sins i am familiar with max, i will kind of talk in its terms.


In order to describe this aspect of hole generation as part of a proposal for an automatic tree generator it is important to introduce some tools related to this process.
These tools are available in almost all 3d modeling applications and are called insert polygon, connect, extrude and chamfer.
The Insert polygon tool shrinks a selected polygon along its plane, and adds four additional polygons. Using this strategy, there is an original polygon as a boundary, and five new polygons inside. The middle one has exactly the same outline as first one, onto which we applied the tool, and others are made by connecting edges of the original polygon and new one which is smaller. This tool works not only with quadrilaterals, but also with any given polygons or polygon groups. To better understand the way this tool works please look at figure 29

Fig 29. screenshots from 3d studio max.
The Chamfer tool works with vertices. This tool can be applied on a selected single vertex or multiple vertices. In order to understand the chamfer tool, imagine a situation where one vertex is connected to four other vertices by four edges. After the chamfer tool is applied four new vertices are created on edges connecting the first original vertex to its surrounding vertices’s. The distance is always specified by the user and then the newly created vertices are connected with new edges. The original vertex which was selected in a first place is
erased. For clarification see figure 30.

Fig 30. screenshots from 3d studio max.
fig 30. shows selected 4 vertices (top) and resulting mesh structure after chamfer operation (bottom)
The Connect tool connects selected vertices by creating new edges. The Extrude (Landrenau 2005) is a tool which moves a selected polygon or polygons along a normal and creates new polygons that form the sides of the extrusion, connecting the selection to the object. For clarification see figure 31.

Fig 31. Picture taken from: Eric Landrenau. 2005. Crystal-Like Geometric Modeling. Thesis of Master of Science. Texas A&M University

Now that you are familiar with the tools necessary for a proposed automatic hole generator, what follows will be two approaches for the detection of where a hole a could be generated. Once this is described the proposed steps for the generation of a hole will be outlined.

dont like english? u can (try) readig it in lithuanian or anny other language here! alternative, has no lithuanian :(

and some real life trees from flickr users

Ok so I was looking around in flickr for some examples of a situations where automatrick tree generator is not suficient, and i fund lots of good pictures. Some depict tree holes, while others depict tree roots or other parts. The funny thing is that I contacted flicker users who uploaded pictures, and asked theyr permision to use images in this blog,. … guess what 100% of people who replyed to me sead ok… that was a nice surprice actualy. So here we go: flickr-trees

please click on it to enelarge… (i increased contrast in moust of images, i hope authors will not get too angry, its all about showing tree details, not art… well who knows about that :) and if there are any erors wiyh titles names or links, write me, it will be corrected.)


1. Tree with hole through it, Martin LaBar / Martin LaBar, http://www.flickr.com/people/martinlabar/

2. Tree Hole, Cryodigital, http://www.flickr.com/people/cryodigital/

3. Tree Hole Entry, Minnie Wong, http://www.flickr.com/people/26133907@N00/

4. Tree and hole ,Adventurer Dustin Holmes / Dustin Holmes, http://www.flickr.com/people/dustinholmes/

5. Tree holes, Opa Schoch / Shok the German, http://www.flickr.com/people/opaschoch/

6. Hole in the Tree, Kent Sandvik, http://www.flickr.com/people/kentsandvik/

7. Tree with Hole, brents pix’s, http://www.flickr.com/people/brentspix/

8. Baobab tree with a hole through its trunk, tommyimages_com’s, http://www.flickr.com/people/cuba_photos/

9. Hole-y Tree, Kuzeyli48’s, http://www.flickr.com/people/21915247@N07/

and, not saying that its best or anything like that, my manualy hand modeled tree…

medis / tree

and a wiki entry on a matter here :


and some copy paste from this article: (aka interesting fackts (if we trust wiki :) ) )

A tree hollow or tree hole is a semi-enclosed cavity which has naturally formed in the trunk or branch of a tree.

Hollows may form as the result of physiological stress from natural forces causing the excavating and exposure of the heartwood. Forces including wind, fire, heat, lightning, rain, attack from insects (such as termites or beetles), bacteria, or fungi. Also, trees may self-prune, dropping lower branches as they reach maturity, exposing the area where the branch was attached. Many animals further develop the hollows using using instruments such as their beak, teeth or claws.

In Australia, 304 vertebrate species are known to use tree hollows in Australia: 29 amphibians, 78 reptiles, 111 birds, 86 mammals.[2] Approximately 100 of these are now rare, threatened or near-threatened on Australian State or Commonwealth legislation, in part because of the removal of hollow-bearing trees[8][1].


You can visit my web page here

dont like english? u can (try) readig it in lithuanian or anny other language here! alternative, has no lithuanian :(

4.3 Hole Generation

4.3 Hole Generation

Overview: The Origin of “Holes” in Trees

It is rare to find a perfect tree in real life usually the older the tree the more defects it will have. Holes are a common attribute of trees found in the wild as well as trees planted by humans. Usually the holes are not that big and sometimes trees have much bigger empty parts inside the trunk or in big branches. The water collects there and makes a perfect situation for rotting. Also fungus or other animals make use of such holes, usually making them become bigger and bigger. Holes can appear as a result of humidity and dead leaves, which remain in same place for a long period of time. Holes are usually noticeable in tree “forks” this means where the trunk separates and two or more steams grow. This is evident in the connections of big branches, cracks and other complicated shapes of trunks. Usually the tree does not die just from rotting, but the rotting could destroy water circulation and that could lead to the long death of a tree which could take many years. If the wind tears a branch off or if other animals or insects injure the outer layers of tree, the fungus and other kind of bacteria start to live in these places, and that makes the tree rotten (Tree Holes).

Regarding the 3d generation of a hole it should begin by determining where are possible locations for a hole in a tree stem. Detection of possible locations could be done by determining where the trunk surface is not planar. The reason, is that holes in a trunk appear in positions where a tree is injured, or where the tree’s architecture is week. There are many biological reasons for a hole’s appearance, therefore there could be many solutions. So far I have described what a hole in a tree trunk is and I have also gone into details regarding how a hole appearance can be a result of a very old tree trunk injury. In the next section I present tools used as well as two proposals for an automatic hole generation tool which detects the best position of a hole utilizing two possible methods. The first method detects a possible hole’s position based upon a trees surface and where conditions are suitable for rotting to occur. The second method has more to do with the overall structure of a tree.


some pictures from tiergarten in berlin:

tree holes

you can also wisit my portfolio.
dont like english? u can (try) readig it in lithuanian or anny other language here! alternative, has no lithuanian :(

Recommendations for Trunk Generation, part II

4.2.2 Step Two: Circle Creation

As it has been already mentioned a tree trunk model is usually based on simple cylindrical shapes. In order to create a cylinder there must be a central axis, and a circle of a certain radius which would define its outer surface boundaries. Therefore the next step to creating a trunk model is to create circles, whose centers’ have positions where by each point is in line with a guiding curve as discussed above. As each point in this curve has different positions in space, so will the resulting circles.

4.2.3 Step Three: Shape Refinement Curves

The third step in the generation of a tree trunk is to copy a guiding curve. The number of copies can be defined by the user. In example shown in Figure 28 copies have already been made. Copied curves here will be called shape refinement curves. After copying them the shape refinement curves should be off set. Off set values are also definable by the user but the default value should be the same as the radius of circle which was created in step two. The refinement curves should be distributed equally along the circle’s perimeter. For

clarification please look at Figure 28 step 3

4.2.4 Step Four: Shape Refinement Circles

Step four in the trunk generation process is to create shape refinement circles which are generated for each point along the surface of the refinement curves. The radius of the refinement circles are definable by the user yet the default value is one third of first circles’ radius.

4.2.5 Step Five: Outline Generation

In step five the generator deletes all splines since they are no longer needed. Then each circle is combined with refinement circles and all intersections are removed leaving behind only an outline. At this stage the method takes advantage of Boolean operations (see Chapter 3 for further explanation). The shapes are then added together and intersecting parts are removed. The end result being an outline of the circle and refinement circles. For clarification of this step please look at Figure 28 step5.

4.2.6 Step Six: Surface Generation

The final step in the trunk generation process would be the creation of the trunk’s surface. In order to create a surface we need to know where each vertex of our polygon mesh will be located. To obtain this information we first will reduce the quality of the outlines generated in step 5. This means the algorithm for trunk generation has to approximate the outline shapes by describing curves using a pre- defined number of points. This means we would have a list of point positions, which define locations of vertices which could then construct a mesh model of the trunk. For clarification please refer to Figure 28.

So far improvements to overall trunk generation have been presented. What follows in this section will introduce another recommendation to do with the biological origins of a “hole” in a tree trunk and a proposal for this to be included in an automatic tree generator. As a part of this explanation possible tools for this approach will be outlined.

you can also wisit my portfolio.
dont like english? u can (try) readig it in lithuanian or anny other language here! alternative, has no lithuanian :(

4.2 Recommendations for Trunk Generation

4.2 Recommendations for Trunk Generation

These recommendations will be divided into six steps, which are required to achieve a detailed trunk surface.

4.2.1 Step One: Creating a Guiding Curve

In order to understand how to create a complex trunk shape there should be some guidelines which indicate how the geometry of the tree will be generated. For this purpose a simple curve is generated for which the user defines its’ level of detail. This means the curve has to have a start and end point as well as a number pf points in between which the user defines. The points on the curve are generated in random positions in the x and y plane, while points positioned in z axis are fixed, and increase at each proceeding point.

The first point is generated on a “ground” or so called “world origin” meaning its’ position in a 3 dimensional space would be x-0, y-0, z-0. This example uses symbolic measures and does not refer to any measuring system. As shown in Figure 28 step 1 of all of the following points would be higher compared to the previous point’s location in the z coordinate system. The user would be able to define limitations of positions except for the first point in the x and y plane while exact values would be randomly generated within specified limitations. If these limitations are not defined by the user there will be default values which the trunk generator uses. If the first point of the curve is in position x-0,y-0,z-0; the second point should be relatively close to first one. The z value always increases in 10 units for each of the proceeding points in the curve. Therefore x and y values should be smaller than that, and the start point should be half of the z value. This recommendation is based upon observation of natural trees since usually a tree trunk tends to grow upwards, with only slight variations on this. Therefore the values for x and y will not change dramatically. In any case the user will be able to adjust these values based upon his or her taste and desired result. For clarification please look at Figure 28 step1.


side coment. when we talk about step 1, and the guiding curve.

In order to or apply this proposal to existing tree generators, we could get this first spline from our L-system, or whatever algorythm is used in the existing generator . the question would be only how to conect end result of generated tree surface from generator and a trunk generator. One way would be simply to conect resulting polys. ofcourse probably there would still remain a question of tree editing after its creation. or simmple soulution could be to simply generate trunk again after each editing step from existing tree generator, well still some room to think.

you can also wisit my portfolio.
dont like english? u can (try) readig it in lithuanian or anny other language here! alternative, has no lithuanian :(

Proposal for Automatic Tree Trunk Generator

Chapter 4: Proposal for Automatic Tree Trunk Generator

This Chapter outlines a proposal for an automatic tree trunk generator. The first section focuses on the shape of a tree trunk and outlines six steps involved in the process of trunk generation. What follows describes the biological origins of a hole in a tree trunk as well as a proposal for automatic hole generation and possible tools for this approach as part of a trunk generator.

4.1 Overview of Trunk Shape

There are many solutions for increasing a 3 dimensional tree’s complexity so that it reflects the natural complexities we see in nature. For example recently there has been a great deal of research done in bark generation in order to achieve photo realistic results in tree simulation. Yet there is a lack of solutions regarding overall trunk shape. Trees in reality tend to have not only complex bark shapes, but also complex trunk structures and in older trees trunks these structures are much more complex, and harder to describe. Most tree generators create quite simple tree trunk shapes. This can be observed in Figure 26 which is screenshots generated by the application Vue6.

Fig 26. Generated using Vue6 personal learning edition.

Fig 26. Generated using Vue6 personal learning edition.

As we can see from Figure 27 a natural tree’s trunk shape can be much more complex .

Fig 27.  Pictures taken in Berlin 2007.

Fig 27. Pictures taken in Berlin 2007.

In order to achieve a more complex tree trunk surface and shape I propose a new trunk surface simulation strategy. This strategy would increase the speed of this process greatly as well as improve upon current tree generators. The idea follows and expands upon a traditional cylindrical extrusion approach. Tree trunks or branches in 3d tree simulators are usually treated as cylinders. Usually the cylinder begins wider and proceeds to become narrower.

My approach follows the same idea yet generates a more detailed result. The general concept is to combine many cylinders with different properties and shapes to generate one shape. In my proposal the cylinders are slightly off set from the center of the trunk, and the result is created by grouping shapes to create the tree trunk’s outer surface. The defining step is the removal of all inner parts of cylindrical shapes which intersect. The result of this unifies the surface thereby resulting in one trunk shape. The next sections will describe the overall steps in detail.

you can also wisit my portfolio.
dont like english? u can (try) readig it in lithuanian or anny other language here! alternative, has no lithuanian :(

3-dimensional tree generation research and further development. Bark Synthesis

Chapter 3. Related Work

Despite the advanced tools for 3-dimensional tree generation available today, there is still research and further development being done. In this chapter, some recent research results will be reviewed. The reviewed papers are relevant for this thesis as a background. Some discussed papers deal with the generation of a tree or parts of a tree, while others are important from a technological point of view.

3.1 Bark Synthesis.

An important aspect of realistic-looking trees is realistic bark. Current tree generators usually create bark by applying texture maps. These texture maps can be used as bump mapping or displacement mapping to increase the visual quality of a 3-dimensional tree model. The problem of using texture maps arises when two branches have to be connected. This can create visual artifacts at the connection points created by texture differences on each branch. Usually, each branch is assigned a texture map, which is applied using a cylindrical projection. The top of the texture of one branch meets the bottom part of a different texture on another branch. The conjunction of these two textures results in a seam. In real trees, such seams are not present, since bark texture grows seamlessly and organically.

“Automatic tools use tillable textures to represent bark, which give unrealistic results on trees (i.e. No continuity at branching, no control of the features, and stretching depending on the branch size).”(Lefebvre and Neyret 2002). This is reasonable for situations when a tree is rendered from some distance, but it is not sufficient for very close views of a tree.

Another reason is that a tree trunk is usually wider at its base and close to its roots up higher it becomes narrower. The same features can be observed in branches. Applying texture on such an irregular cylinder makes the bark at the top part of the cylinder look compressed. The most straightforward way of dealing with such artifacts is by drawing bark textures manually. This can be a very labor intensive task requiring a great deal of manual work that could be automated.

Sylvain Lefebvre and Fabrice Neyret, in a joint research project, addressed this problem and came up with inspiring results. Their approach generates either a texture or mesh based upon the bark. This proposed method overcomes problems of seams in bark and trunk conjunctions. This method also doesn’t produce a compressed bark look in the places where the diameter of the trunk model is wider. Lefebvre and Neyret’s approach creates a realistic look for fracture-based barks.

Bark is a result of the tree’s growth process, which grows a new layer each year or each rainy season. New layers of bark are placed inwards, meaning the outside of the bark is the oldest layer, and the newest layers are closest to the wood tissue. The older the tree, the more layers grow on top of old ones. As the circumference of outward layers increases, fractures appear. The outer layers crack as a result of the diameter growing and its increased pressure on outer bark layers.

In their paper, the authors suggest to divide the trunk into transverse strips, which could be described in a 1-dimensional space for simplicity. Then the growth of the trunk or branch would be transferred to increase the length of these strips. The cracks are generated in these strips and then the original strips are covered with bark texture and the cracked ones are filled with crack texture. It could be either texture or 3-dimensional models that are inserted. The position of the crack’s appearance is aligned to the same crack in the next strip, this way the cracks are aligned along the trunk’s direction. Since the trunk or the branch has a different radius at different heights, the proposed model must take these differences into consideration. Otherwise the result would be a compressed texture appearance where the trunk or branch width is smaller, and stretched where it is wider. Therefore strips must represent the real circumference of the branch or trunk. In wide trunk areas we have long strips and in narrow areas short ones. Then the generation of cracks takes place.

Sylvain Lefebvre Fabrice Neyret. 2002. Synthesizing Bark.  ACM International Conference Proceeding Series; Vol. 28

Fig 21. Picture taken from: Sylvain Lefebvre Fabrice Neyret. 2002. Synthesizing Bark. ACM International Conference Proceeding Series; Vol. 28

As Figure 21 Illustrates, the bark breaks in its weakest segment in this model. The authors create a weakness map in their approach, and combine it with random position generations. This bark synthesis model achieves convincing results. The bark looks quite realistic compared to previous automating approaches that use simple texture tiling. Figure 22 shows the results of an implemented bark synthesis model.

Sylvain Lefebvre Fabrice Neyret. 2002. Synthesizing Bark.  ACM International Conference Proceeding Series; Vol. 28

Fig 22.Picture taken from: Sylvain Lefebvre Fabrice Neyret. 2002. Synthesizing Bark. ACM International Conference Proceeding Series; Vol. 28

The paper discussed above is very important in tree modeling, since it deals with bark as a 3-dimensional object and tries to simulate realistic-looking bark. This is a promising approach in bark simulation and generation.

you can also wisit my portfolio.
dont like english? u can (try) readig it in lithuanian or anny other language here! alternative, has no lithuanian :(

cg tree simulations = back to origins and, why this blog was created = cg tree simulations.

ok, so long time no new posts, somthing needs to be done uppon this issue :)
ok, i guess i shuld remember the reason i have this blog. I created it in order to get some fead back from people about a topick i am interested,
which is tree generation in 3d. But it happened so that there is not even 1 post on this matter.
time to fix that. Now most of posts which will folow will be regarding the subject, and material which i will use
is based on one master thesis work. Do i have a right to use this material? i guess i do. (if not the owner of thesis shud sue me, that would be a very interesting case i think :)
so the order of posts will  not follow the order of thesis, and i will get rid of chapters on 3d technik, while there is no need to write a content which is easier to find in wiki. .



Virtual tree generators have become more powerful than ever before. Traditionally tree generators are used to create trees and forests in films. Due to their professional quality these tools enable filmmakers to seamlessly blend raw footage with computer generated (CG) material. As a result the audience is not able to distinguish the difference between the two types of footage. Figure 1 shows screenshots taken from the film “Pirates of the Caribbean: Dead Man’s Chest” and shows how the natural environment has been combined with computer enhanced forests which were created by a tree generator. Current automatic tree generators are highly advanced for certain conditions but further extensions and improvements are still possible. For example commercially available tree generators such as Vue, or Xfrog can produce reasonable results when one wants to simulate a forest or a generic tree. Vue and xfrog will be discussed in more detail in Chapter 3.3.5. yet both of these tools have limitations. One of the weaknesses’ of such tools can be observed when a close up or a small detail of a tree trunk or branch is shown since the level of detail in the tree trunk, branches and roots are not always convincing when created by an automatic tree generator. This means that when a very detailed tree model is required it must be created manually instead of modeled via an application which can be very costly and time consuming.

Since many tree generation applications have already focused a lot of research on the creation of branches, and leaves this thesis is focused on research regarding tree trunks and their surface. In traditional tree generators some elements are never considered, for example usually a tree generator does not generate roots. The reason is very simple since usually the roots are under the earth so there is no need to generate them. Yet this is not necessarily true for all scenarios. In Contemporary films whether in the genre of fantasy or fiction there is a great chance that trees will appear as very complex models. This is because the more detailed the tree models are as part of the background of a scene the stronger the overall mood of the film is. For example the more intriguing and scary looking an old tree is the more it adds to the tone of the film. One way of creating this mood is to model old trees and have parts of the tree’s roots visible. The result being a more magical or mysterious characteristic to the film. The same observation could be applied to trunks. When seen in a film an interesting tree is usually very old has numerous diseases, holes, and other interesting surface elements. The branches and leaves are usually part of a large shot. One can argue this is not an attempt to create photorealism but instead to express the complexity of characteristic trees that could be found in nature.

In this thesis I will concentrate on suggesting improvements to existing tree generators. This is because current tree generators are already quite convincing in leaf generation and the structure of branching is currently very realistic. Figure 2 shows a tree generated in Vue6. Therefore the focus of my research will be on older tree trunks, which are currently generated in quite simple fashion. Commercial tree generators use bump and displacement mapping to make a trunk more realistic, but its not this is not a sufficient solution for models which require more detail. Figure 3 is a screenshot from the popular film “Pan’s Labyrinth” directed by Guillermo del Toro (2006). Figure 3 depicts old trees with complicated structures and shapes which are beyond an automatic tree generators’ capabilities.

Current tree generators are concerned with tree generation and not degradation and this is a problem since the most visually interesting trees are dying ones, sick ones or trees which are in some way or another unique.

In the next Chapter I will introduce some biological information about trees, their diseases, possible kinds of injuries and other qualities which are important factors to consider when making recommendations regarding tree generators.

In Chapter two some technical terms are presented which are very important for 3 dimensional (3D) tree creation. All of these important 3D concepts, tools and techniques relate to possible improvements to current tree generators. Chapter four consists of proposals and strategies regarding tree generation improvements. Chapter five will describe the prototype which was the result of my research into the generation tree trunk shape as part of an automatic tree generator. In Chapter six I discuss future work which could be done regarding this area of research.

vue add caribian pirates

Fig. 1 Picture taken from: http://www.e-onsoftware.com/ accessed may 09 2007

Fig. 2 Tree generated in Vue6.

Fig. 2 Tree generated in Vue6.

Fig. 3 Screanshot from film “Pan\'s Labyrinth”

Fig. 3 Screanshot from film “Pan’s Labyrinth” Picture taken from: http://www.panslabyrinth.com/ accessed may 09 2007

you can also wisit my portfolio.
dont like english? u can (try) readig it in lithuanian or anny other language here! alternative, has no Lithuanian :(