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

Next Page »

Follow

Get every new post delivered to your Inbox.