May 2008


4.4.2 Hole Determination Based Upon Overall Tree Structure

In this method a more advanced hole generator approach is used whereby holes are created at the intersection of big branches. The first potential place is the trunk and first branch intersection. The further the branching is from the trunk the less reason for a highly detailed model, therefore there should be a limit, and intersections between small branches should not generate holes and cracks. Another good position for possible holes could be the beginning of the roots whereby a hole is determined in an area where most of the vertices angles are low also in places where the roots meet the trunk’s surface.

Now that I have described the tools and two possible methods for hole detection I will provide the necessary steps for this process. The proposed process of hole generation is based on 3d studio max 9 work flow and tools, but could be easily implemented in any other 3d modeling application or created as a stand alone solution. For the sake of simplicity random vertices on a polygonal plane will be used, instead of vertices with low angular levels in tree trunk model.

The first step in hole generation is to select a candidate vertices group, which should form a hole. After the selection is done a chamfer tool is applied. The value which describes the distances where new vertices are created, could be half of an average edge length of selected vertices’. The next step would be to connect newly created vertices via the chamfer tool. The connection tool creates new edges between newly created vertices. Edge selection is converted to a polygon selection. See figure 33 where it describes the fourth step.

max hole

Fig 33. Proposals visualization.

Fig 33.first four steps in hole creation. The red dots represent selected vertices, red lines selected edges, and red shaded area represent selected polygons.

As Figure 33 shows the resulting polygon selection is not accurate. This is due to the fact that the edge selection conversion to a polygonal selection includes all neighboring

polygons. Polygonal selection should be shrunken to get the desired result.

max hole

Fig 34. Proposals visualization.

This is shown in Figure 34. The next step is to erase all selected polygons, and select the remaining edge outline and conduct an edge extrusion. The last step shown in Figure 34 represents a subdivision algorithm applied on a mesh.

The subdivision algorithm not only generates more detailed mesh structure, but also softens the edges of it. The steps I have described are rather easy to perform due to the ability of 3d studio max to remember the last used selection and convert vertices selections to edge or polygon selections. This process should be possible in any 3d modeling software, but it might include a different order of steps, or additional steps required to achieve the same result.

Figures 33 and 34 show steps which are very easily preformed manually. But the steps are also simple enough so that the actions could be automated. To manually create a hole as shown in Figures 33 and 34 it took around 5 minutes. But if a real trunk model was used with high mesh density and many holes to generate, this process could be very long.

My recommendations if implemented would decrease the amount of time involved in current tree generation.

————————-

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.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.

detect

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 :(

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 :(

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.)

credits:

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 :

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

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

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 :(

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

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.

000000000000

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 :(

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 :(

Ok, so we looked at some research done about tree generation.
Now one or two articles about some 3d techniques, which might at first glance be seen as irelevant to trees,
but you will see how it is relevant when I will discus blobmesh (metaballs, implicit surfaces) in tree generation.
So as we all know implicit surfaces solutions result ugly mesh topology, and here is a nice idea how to make topology “right”.

*(if my short overview of this paper is unclear, please have a look at original paper, sins i am not a mathematician, some stuff is hard to understand for me too.)

——————————————

One problem in 3-dimensional modeling for animation and film special defects is mesh topology. In order to correctly animate surfaces which undergo morphing transformations, the topology of the mesh, in other words the structure of polygons and the way they are interconnected, must be correct. This means it must follow certain rules or requirements. One of the requirements is to have a mesh which consist of quads polygons, rather then triangular polygons. This brings up another important term in 3-dimensional animation and modeling which is edge loops. This term is not scientific and used by modelers.

The edge loop is not exactly a technical term, but rather jargon used by artists. It is hard to determine what is an edge loop and what is not. The edge loop is a certain way polygons are arranged together. The idea is that the main visual or underlying structures of an object which is being modeled would be represented in a polygon arrangement. The polygons no longer define only the surface approximation of an object, but also reflect the biological or mechanical underlying structures of the represented object. When an object is animated it deforms, and in order for the object to deform realistically its structures (polygonal in this case) must represent the structures and movement which exist in real object. For example, a correct mesh topology of a human body should contain polygons which represent an approximation of the human body’s volume correctly, and the way the polygons are interconnected should represent the main muscle structures. This method provides more realistic human body animation, due to the more convincing muscle movements.

When 3-dimensional objects are scanned from real life objects and usually outputted from a 3d-scanner, the mesh is irregular and does not form or represent any certain structure. The vertexes in the mesh are distributed more or less equally along the complete surface. In film or animation, such objects are usually modeled manually (Boudon 2006). The scan is used only as a reference, and the modeler has to create an object from scratch, while creating a correct mesh topology. In other words, the scanner scans only the surface without any real ability to interpret inner structures of that object. Figure 25 illustrates this.

The same problem exists with implicit surfaces, since implicit surface polygonisation topology of a mesh is quite messy and it is very hard to animate such surfaces, unless they are polygonised for each and every single frame separately (see section 2.2.4, for a short description of implicit surfaces).

Some very interesting research has been done concerning Anisotropic Polygonal remeshing, or in other words retopologisation of polygonal meshes by Alliez, Cohen-Steiner, Devillers, L’evy and Desburn. In their paper “Anisotropic Polygonal remeshing”, the authors propose a method to correct bad or irregular mesh topology (Alliez et al. 2003).

This method employs natural anisotropy meaning dependent on the direction of a given surface and tries to mimic the way an artist would create a 3 dimensional object by using the minimum number of surface elements to create a detailed surface (Alliez et al. 2003). They developed an algorithm which inputs the existing mesh, and estimates the directional fields of a given surface at each vertex. Then using the calculation of the directional fields, the algorithm estimates the minimum amount of curves necessary. Meanwhile, the algorithm creates curves which are always parallel in order to create an effective mesh topology. In the intersection of the curves, the algorithm then generates vertices. After that algorithm generates a mesh using the created vertices and direction curves as guidelines (Alliez et al. 2003).

Anisotropic Polygonal RemeshingFig 25. Picture taken from: Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Lévy, and Mathieu Desbrun 2003. Anisotropic Polygonal Remeshing. ACM SIGGRAPH 2003 Papers SIGGRAPH ’03, Volume 22 Issue 3

As shown in figure 25, the overall surface shape of the model remains the same, but the number of elements dramatically decreases. Also the topology of the mesh is much better and resembles one which one would expect was created manually. This method is very valuable in 3-dimensional modeling and could potentially serve for re-meshing virtual models generated by 3-dimensional scanners or irregular mesh topologies created by implicit surface polygonisation.

you can also wisit my portfolio.

A very different approach to tree growth simulations has been developed by Colin Smith and Przemyslaw Prusinkiewicz (Colin Smith 2006). It is quite different from most methods where trees are described as a set of modified cylinders. The authors of this paper made an observation that a tree in the process of its growth changes quite a lot. These changes take place at a cellular level. Therefore, the method that they describe tries to mimic misbehaviors of cells in a tree tissue.

The authors developed vertex-to-vertex (vv) formalism to describe cell-like system behavior. This means that the approach is targeted at dynamic systems, which change through time. Vertex-to-vertex formalism is similar to L-systems in that it uses lineage information and context to identify elements of structure. Vertex-to-vertex formalism relies only on local information in contrast to L-system declarative nature, which describes rules for the whole structure. This method allows associating each vertex of a polygonal mesh with a list of its neighboring vertices. The resulting structure is manipulated using vv algebra, which includes a set of various operators.

The form change in vv formalism is a result of tensions introduced to tissues by growth. Each vertex is affected by a sum of forces from neighboring vertices. Also, external forces can be introduced, such as gravity and the pressure of the internal structure layer to its external layer.

Biological Modeling

Fig 24. Picture taken from: Colin Smith. 2006. On Vertex-Vertex Systems and Their Use in Geometric and Biological Modeling. Doctor of philosophy diss., The University of Calgary.

The resulting forces are updated until equilibrium is reached.

The simulated objects are directly represented as polygonal meshes. Each vertex of the polygonal mesh is manipulated according to tension energies from its neighboring vertices, as well as other forces. The final shape of the plant is generated by calculating the local stresses resulted by local growth. This method might be not the best to produce full-grown tree models, but it could be very important in modeling small plants or parts of them.

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 :(

Next Page »

Follow

Get every new post delivered to your Inbox.