This work presents a continuous level of detail representation of foliage of trees. Multiresolution modeling allows to adapt the number of polygons to render to the relevance of the object in the scene. However, foliage is represented by isolated polygons, so most of the multiresolution modeling methods do not work properly with this part of the tree. This paper presents a multiresolution model that allows to adapt the number of leaves to the relevance of the foliage in the scene. The criterion to select the appropriate leaves to render is based on a previously performed view-driven simpli cation. To adapt this parameter in real time, data structures and the necessary algorithms that allow us to extract the appropriate number of polygons are presented. Some tests have been developed to evaluate the proposed solution and results show the good performance of the presented continuous level of detail.
Vegetation is an essential part of the outdoor environments in applications where realism is a must. However, the vast amount of polygons that are required to represent them makes their inclusion in interactive applications a problem. Level of detail modelling has been con rmed as a solution to adapt the number of polygons of the objects in real-time rendering of scenes. This technique manages object representation while maintaining an adequate frame rate in real-time rendering applications. Nevertheless, foliage of the plants are represented by isolated polygons, so most of the multiresolution models in the literature can not properly manage their representation. This problem does not occur when the solid part of the plants, the trunk and the branches, are considered because they are represented by continuous meshes.
According to Ribelles et al. [
Unreal Engine [
They avoid popping e ects because the change from one resolution to another
one is made in a continuous way. Both groups of multiresolution models are
based on simpli cation methods that have previously processed the geometry
of the object. This simpli cation process is performed o -line and results are
used to build the data structure that form the appropriate multiresolution
models. Simpli cation methods di er in the metrics they are based on. Because of
the fact that foliage is not represented by continuous meshes, the simpli cation
methods have to be adapted to this kind of representation. Some works have
been presented that deal with this part of the plants. They use metrics based on
geometry [
This paper proposes a continuous multiresolution model that allows
representing the foliage and adapting the number of polygons according to their
importance in the scene. The simpli cation method used to build this level of
detail structure is based on the image-based simpli cation presented by Gasch
et al. [
The proposed multiresolution model, as well as its level of detail extraction algorithm, has been developed to be easily included in current game engines in order to facilitate its use. A plug-in to be included in Unity 3D has been implemented, so the test and experiments to evaluate the method have been performed using this game engine. Obtained results show the good performance of the proposed level of detail model.
The paper is organized as follows. Section 2 considers the state of art related to the existing techniques in the multiresolution modelling adapted to the foliage. Section 3 brie y describes the model overview. Section 4 brie y reviews the simpli cation method this multiresolution model is based on and then it describes the data structure that stores the leaves of the whole representation.
Next, Section 5 analyzes the rendering algorithms that perform the extraction of the appropriate number of leaves that form the foliage representation. Section 6 describes the test that have been performed and analyzes the results obtained, and nally, section 7 presents some conclusions and observations related to the future work. 2
Some methods have appeared in the literature addressed to reduce the complexity of the sparse component of the trees and plants. They can be classi ed mainly in three groups, depending on the method they use to represent the foliage: images, points or polygons.
The rst group uses image-based representation to perform real time
rendering of plants [
Methods based onpoint/line representation usually combine polygons to
construct hybrid models for trees. At close distances, the plant is represented by a
polygon. With increasing viewing distance, branch meshes will transform into
lines and leaves into points [
The last group in the classi cation uses the polygons to represent the plants, regardless of the distance of the object to the viewer. However, di erent compression techniques are used to reduce the amount of data to visualize. They usually use di erent metrics to compute the o -line simpli cation that allows to build the level of detail structure. These simpli cation methods can be based on stochastic, geometry or image metrics. They condition the performance of the multiresolution model.
Traditionally, works in the literature perform a level of detail modelling by
means of multiresolution models built from simpli cation methods based on
geometric metrics [
Other works have appeared that apply stochastic simpli cation [
Image based simpli cation has been widely analyzed in literature. However,
most of the works deal with general meshes [
The presented continuous multiresolution model allows to adapt the number of
polygons that form the foliage in real time, according to its importance in the
scene. It is based on the Viewpoint-Driven Simpli cation (VDS) of Plant and
Tree Foliage [
The data structure of the continuous multiresolution model has been conditioned by the results obtained from the VDS simpli cations model. So, a brief overview of this method is exposed next. 4.1
The VDS simpli cation method allows simplifying the sparse part of the trees
and plants. To do this, it uses a metric based on a theoretical measurement of
information called viewpoint mutual information (VMI) [
The quality of the results when obtaining this error depends on the number of points of view. To do this, the method uses a distribution of cameras placed at the vertices of a dodecahedron.
The simpli cation process is based on a pruning operation. To do this, in each iteration, the method searches for the leaf that produces the least error when it is eliminated. Once it is found, this leaf is removed and the process is repeated until the desired level of simpli cation is reached. After determining the leaf to be removed in each iteration, the closest leaf is searched for and scaled based on the error introduced when it is eliminated and on the size of the removed leaf, as shown in Figure 1. In this way the leafy appearance of the foliage is maintained.
The results obtained by this method show that the use of the VMI metric generates a pruning leaf order that prioritizes those leaves that are hidden from any of the view-points used. Resulting from the simpli cation, foliage is emptied from the inside out and the possible gaps that may appear are lled by scaling the nearby leaves of the eliminated one. 4.2
Analyzing the VDS simpli cation method, a data structure has been designed that stores all the data necessary to draw every one of the required level of detail. This structure is shown below.
S t r u c t L e a f f
V e r t e x v e r t i c e s [
The vector leaves stores the list of all the leaves that form the foliage. The order of storing the leaves is conditioned by the results obtained from the VDS algorithm, so it represents the drawing sequence.
All the data required to render a leaf is stored in the struct Leaf. It stores the data required both to render the original size and to render when some resizing is required. It is composed by: { vertices: It stores the vertices that form the leaf. { leafToSplit : The leaf that has to be modi ed by scaling its size when this leaf is added from the current representation. { leafToCollapse: The leaf that has to be modi ed by scaling its size when this leaf is removed from the current representation.
{ scale: The amount that must vary the size of the leaf to be modi ed. 5
Once all the required data are stored in the multiresolution model, the algorithms that extract the appropriate level of detail have to be designed. They take into consideration the distance of the plant to the point of view as well as the size of that plant in the nal rendered frame. The target of the criterion is to improve the quality of the render, so the closer the viewer is, the higher the realism has to be. As the camera moves far from the plant, fewer polygons are required to represent the foliage. The same case happens with the number of pixels used to render the nal representation of the foliage: the importance of the plant in the frame conditions the number of leaves that is required to ensure the good quality of the nal rendering.
These both criteria have been considered and codi ed in the formula shown in Equation 1, that obtained the value LOD. It combines the value distanceToViewer, obtained from the normalized distance (with a value between 0 and 1) between the center of the foliage and the camera position, and projectedArea, that stores the size of the projected area of the foliage in the current frame. Some constants (a, b) have been added to the equation to allow customizing the relevance of every one of the criteria in the equation. In the test, they have been set to 0:8 and 0:2 respectively, so the distance to the viewer has been considered more relevant.
LOD = distanceT oV iewer a + projectedArea b (1)
This LOD value is normalized and allows to obtain the number of leaves to be nally rendered. Then, this number is compared with the one that is currently being rendered, performing di erent actions in the case the number of leaves to render is the same, fewer or higher than the currently number of leaves rendered. The actions to be performed are conditioned by this comparison, so: { Same number of leaves : The level of detail to render is the same that is being currently rendered, so no actions are required to be performed. { Fewer leaves to render : Some leaves have to be removed from the list to be rendered and some of the ones that remain have to be resized. { Higher number of leaves : Some leaves have to be added to the nal representation and some of the ones that are being rendered have to reduce their size in order to undo the scaling.
Algorithm 1 analyzes the process to follow in these cases. Every time the process starts, the algorithm has to evaluate the relevance of the foliage in the scene (LOD ). This value is used to extract the number of leaves to render in this case newLeaf. Once this number has been obtained, it is determined if some leaves have to be added to the current approximation or some leaves have to be removed (collapse).
The scaling process is already calculated by the simpli cation method and saved in the structure used by this model to speed up the process and not have to recalculate the scaling on each leaf. Each leaf, when removed or added, only modi es another leaf (leafToModify), therefore, this model uses the leaves themselves to save the scale values that a ect the other leaf, exchanging them when necessary. First, the model di erentiates whether it is a leafCollapse or a leafSplit. In the rst case, the scale value of the leaf to be modi ed is contained in the leaf to be collapsed. Therefore, both leaves exchange their scales as shown in Figure 2(a).
In the second case, as seen in the gure 2(b), the added leaf retrieves its original scale value from the nearby leaf. Which, in addition, also recovers its scale. When this process has been performed, the algorithm render the list of the leaves that form the current level of detail (Draw(LOD)).
Function Extract(LOD) do newLeaf = totalLeaves LOD; if newLeaf > currentLeaf then for i = 0; i < newLeaf currentLeaf ; i + + do leaf Split(currentLeaf ); currentLeaf + +; end for else for i = 0; i < currentLeaf newLeaf ; i + + do leaf Collapse(currentLeaf ); currentLeaf ; end for end if end function Function leaf Split(currentLeaf ) leaf T oSplit = leaves[currentLeaf ]:leaf T oSplit; aux = leaves[currentLeaf ]:scale; leaves[currentLeaf ]:scale = leaves[leaf T oM odif iy]:scale; leaves[leaf T oM odif iy]:scale = aux; end function Function leaf Collapse(currentLeaf ) do leaf T oCollapse = leaves[leaf ]:leaf T oCollapse; aux = leaves[currentLeaf ]:scale; leaves[currentLeaf ]:scale = leaves[leaf T oCollapse]:scale; leaves[leaf T oCollapse]:scale = aux; end function
Function Draw(LOD) do lastLeave = totalLeaves LOD; for i = 0; i < lastLeave; i + + do
drawLeave(i); end for end function The experiments have been performed using a computer with an Intel Core i73517U 2.40GHz processor with 8 GB RAM and AMD Radeon HD 8500M/8700M graphics card. All the geometric models of plants that have been used in the tests have been modeled using the commercial modeling tool Xfrog [35]. Unity 3D version 2018.2.7 was used to implement the model multiresolution and to view the result.
Three di erent vegetation species have been considered in the experiments:
English oak with 20,146 leaves, Carya illinoinensis with 8,059 leaves and Betula
populifolia with 12,140 leaves. The trunks and branches used have been simpli ed
by the method presented by [
In order to validate the multiresolution model, tests have been carried out with the three plant species separately and with forests formed by these species. The performed test has analyzed each vegetable species individually. Every one of them has been represented and then the camera has been moved away from the model, adapting the level of detail of its representation according the formula previously presented. Then, the temporal cost of performing the visualization of the approximation have been calculated. This has been measured by obtaining the frames per second (FPS) while the camera moves around a circular path that surrounds the model. This circular path has increased the radius for performing the experiments. The results obtained can be seen in Figure 3. As it can be observed in the chart, initially there is a great di erence between the three vegetable species due to the di erent number of leaves. However, as the camera zooms out, and therefore the level of simpli cation increases, this di erence decreases, further increasing the frames per second.
*/
Regarding the time used to extract the appropriate level of detail, it has been measured in milliseconds per every distance. The obtained results can be seen in Figure 4. At the initial point, since the camera is close to the model and therefore there is no simpli cation, the cost is reduced to the render time itself. Then, as the method starts to reduce the detail of the foliage, the di erence between the extraction of required approximation of the three vegetable species is greater. However, as the camera zooms out and the representations considerable reduce their number of leaves, the extraction cost decreases and the three species reduce the di erence between them. 6.2
In order to better analyze the presented model, some tests have been carried out with groups of trees to represent forests. Figure 5 shows the results obtained when analyzing the spacial cost of visualizing them while the number of trees is increased. This cost has been measured by obtaining the frames per second (FPS) while the camera moves around a circular path that point the forest center. Each forest is made up of only one vegetable species that adapt their resolution according to the distance to the camera. However, in order to evaluate the good quality of the results, the forest represented with the vegetable species English oak has been tested twice: one test with all the geometry, without performing reduction English oak geometry, and other one adapting the detail to the criteria English oak.
As it can be seen in the chart, the FPS considerably increases as the detail of the foliage of the rendered plants are adapted to the established criteria. Moreover, it can also be seen that the cost of extracting the appropriate leaves for every frame is not relevant in front of the wide reduction in the visualization time. 6.3
In order to show how the presented multiresolution model allows simplifying the vegetation elements without reducing their visual quality, Figure 6 shows the simpli cation carried out at three di erent distances. For this, a tree with 20,000 leaves has been used, shown in 80% of its leaves, 30% and 15%.
In addition, a view of a small forest is shown in Figure 7. This forest contains nine trees with 20,000 leaves each one. After applying the simpli cation model, the number of total leaves drawn is 49,680 . However, the visual di erence between the close and distant trees is barely appreciated. 7
In this work, a multiresolution model for the foliage of plant elements has been presented, based on the Viewpoint-Driven Simpli cation method. This simplication method establishes a leaf removing order from the most hidden leaves to the outside of the foliage. Also, the method avoids the pruning appearance of the less detailed representation by lling the possible gaps in the foliage by scaling the leaves close to the pruned ones. In this way, the foliage can be highly simpli ed without being barely noticeable by the viewer when the camera is far from the plant. Data structure and the algorithms that allow to extract the appropriate approximation have been presented in the paper.
Also, the multiresolution model have been designed to be easily implemented in game engines. The extraction time of the appropriate level of detail is very low being, as results demonstrate, less than 1 millisecond in models with more than 40,000 polygons. The results obtained demonstrate that the model allows to adapt in a continuous way the detail of the foliage in a scene. Regarding forest visualization, also results support that the rendering cost is signi cantly reduced while maintain the visual quality.
As future work, some animation is going to be applied to the leaves in order to simulate the e ects of wind on them. In this future line of work, also trunk and branches are going to be animated adding some skeleton to the vegetable species.
Acknowledgments This work was supported by the Spanish Ministry of Science and Technology (Project PID2019-106426RB-C32) and the Universitat Jaume I research projects (UJI-B2018-56).