3D TREE MODELING ALGORITHM

Full Text

Introduction. Modeling of trees is actively used in solving forecasting problems. Thus, in [1] the forecast of forest recovery after a fire is built, in [2] the calculation of forest survival in the long term is carried out, the authors [3] build a forecast of grape harvest using a model of vine growth. At the same time, the features of the growth of the tree depend not only on the breed, but also on the growing conditions. That is, when building a model of a particular tree, it is necessary to take into account climatic features and the influence of the terrain. Realistic models of trees can be built on the basis of data obtained from aircraft using active optical systems [4-6]. Also, tree models are used in many computer games. The paper [7] proposes a growth model of larch Ruprecht (Larix princi- pis-rupprechtii) for forest management planning tasks. Such tasks often do not require a high level of detail. The coarsened tree model is represented by three primitives: two cones and a cylinder (fig. 1). Fig. 1 parameters: H - tree height; D - diameter of tree trunk at chest level; CW - maximum width of the crown; CL - total crown height; CH - height to the widest part of the crown; h1, h2, h3, h4 - is the height of the lower part of the trunk, the height of the top of the cone, the height of the bottom cone and the height of the cylinder respectively; R2 - is the radius of the base of the upper cone; R3 and R4 - are the radii of the bases of the lower cone; R5 - is the radius of the cylinder. Two cones imitate a coarsened crown, a cylinder - barrel. The proposed methods establish changes in the diameter of the bases and the height of the cone, as well as changes in the di- ameter and height of the cylinder, depending on the age and degree of dominance of the tree in the plantation. The paper [8] proposes methods for modeling vegetation and landscape scenes based on a combination of three- dimensional laser scanning data and two-dimensional digital image data. For inventory methods based on indi- vidual trees, such features as the height of the tree, the shape and volume of the crown, diameter of the trunk are calculated. The paper [9] suggests the interactive way of model- ing of a tree which is based on the interaction of the user with the system. At the first stage, the system creates sev- eral pretending models from the contour of the tree cre- ated by the user. From these models the user selects the most suitable trees. These selected trees are then automatically proc- essed by the system to create new candidate models. A typical example is shown in fig. 2. Thus, the tasks that require modeling of trees can be very diverse: from computer games to modeling the growth of trees in plantations. Depending on the problem to be solved, one or another method of tree modeling and its level of detail are chosen [10-13]. An algorithm for constructing a tree in three- dimensional space. The tree model is described as a clas- sical tree-like dynamic structure of data representation. Each node of this structure describes one element of the tree and contains a number of parameters: a reference to the parent node; type; coordinates of the beginning and end of the node; its thickness. It is possible to extend this structure for different tree species and categories. Model- ing of tree growth is similar to the two-dimensional case with the correction for three-dimensionality [14]. Construction of a three-dimensional model of the tree takes place in several stages: 1. The construction of the tree frame: - modeling tree growth; - adding new nodes. 2. Building a tree on the frame and applying textures. Fig. 1. Larix principis-rupprechtii model Рис. 1. Представление модели Larix principis-rupprechtii Fig. 2. Stages of tree modeling procedure Рис. 2. Этапы процедуры моделирования дерева Fig. 3. Wireframe tree model Рис. 3. Каркас дерева Under the tree frame we understand a set of threedimensional vectors with the attribute data for each vector (fig. 3). 1) turn about an axis 2) turn about an axis uur OY through an angle of q ; uur OZ through an angle of φ. The algorithm for constructing a tree model is itera- tive. Each iteration is a stage of tree growth (fig. 4). Thus, the tree is gradually grown to the required level. When constructing a three-dimensional frame of the The matrix of rotation of the coordinate system through angles q and φ has the form: M (q, j) = Mz (j)× M y (q) = æ cosq × cosj -sinj sinq×cosjö tree, at the time of adding new nodes, it is convenient to = ç cosq× sin j cosj sinq×sinj ÷. (1) use a spherical coorrdinate system. ç ÷ So a new node v is created by deflecting from the par- ç -sinj 0 cosq ÷ u ent node r è ø by an angle q and turning around it by an angle φ (fig. 5). Right-handed coordinate system is used Let (qv , jv ) - the rotation angles of the new node v in this case. relative to the parent node u . But the node r u , in its turn, The rotation of the coordinate system by angles q is also rotated by some angles, denoting them (qu , ju ) and φ is obtained from the composition of rotations relative to the axis uur uuur uuur OZ in the base coordinate system. around the OY and OZ following: axes. The order of turns is the They are calculated by formulas of transition from spheri- cal coordinate system to Cartesian. Fig. 4. Tree growth modeling algorithm Рис. 4. Алгоритм моделирования роста дерева Fig. 5. New node creating stage Рис. 5. Построение нового узла каркаса дерева Fig. 6. Cone performance in X3D Рис. 6. Представление конуса в X3D Thus, the resulting rotation matrix will be calculated by the formula: The <Coordinate> section lists the coordinates of these vertex points as follows: M = M (qu , ju )× M (qv , jv ) . (2) x1 y1 z1, x2 y2 z2 , ... x2 N -1 y2 N -1 z2 N -1 . (5) Accordingly, the coordinates of the new node v in the base Cartesian coordinate system can be calculated by the formula: æ xv ö æ 0 ö The following sequence of steps is used to construct the cone: 1. The coordinates of the bases are calculated, the center of the lower base lies at the point (0, 0, 0), and the top at the point (0, 0, L), where L is the length of the ç y ÷ = M × ç 0 ÷ , (3) tree node. ç v ÷ ç ÷ z L ç ÷ ç ÷ è v ø è ø where L is the length of the new tree node. To visualize a three-dimensional tree model based on the constructed framework, we will use the VRML three- dimensional image description language or its descendant X3D [15]. A straight truncated cone is constructed on the basis of the frame of each node. Radii of bases - the arithmetic mean between the parameters of the width of the current node and the neighbor on this base. The axis of the cone is the vector of the node. A straight truncated cone in X3D, from a mathe- matical point of view, is a regular truncated pyramid (fig. 6). Such a pyramid is described as follows: The <IndexedFaceSet> section lists the order of the vertex points that make up the faces and bases of the pyramid. The upper base of such a pyramid will have a description: 2. The angles q and φ for the node vector are calcu- lated. 3. The coordinates of the cone are recalculated taking into account the rotation matrix M (q, j) according to the statement (1). An example of a tree based on this algorithm is shown in fig. 7. Thus, using the considered approach to modeling trees, you can build a tree model with any degree of de- tail. For example, for coniferous trees, you can model a tree up to each needle. Conclusion. The paper proposes an algorithm for con- structing a tree model, which is iterative and each itera- tion is a stage of tree growth. The algorithm is based on the idea of modeling a tree by its gradual “growing” to the required level. The trunk and branches of the simu- lated tree are approximated by truncated cones, the axes of which are the frame vectors. For visualization of the constructed three-dimensional model of a tree the lan- guage of the description of three-dimensional images of 0 1 2 ... N - 2 N -1 -1 , (4) 3D is used. Using the developed approach it is possible to model trees with any degree of detail and different catewhere -1 is the face description separator. gories of state. Fig. 7. 3D tree with textures Рис. 7. Трехмерное дерево с наложенными текстурами

About the authors

A. S. Pyataev

Reshetnev Siberian State University of Science and Technologies

Email: pyataev.alex@gmail.com
31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

References

Supplementary files