Tree Placement

Generated tree models will be integrated into terrain meshes to create comprehensive 3D urban models. To ensure precise integration into the terrain mesh (especially for large areas), the tree models' GPS coordinates (latitude, longitude) will be converted to Cartesian coordinates (x, y) using a Mercator projection.

mercator
Figure 1. Mercator projection (source)

This is the most common way to represent the Earth’s surface on a plane and has the advantage of being conformal, meaning that it preserves angles locally (hence its usage in sailings).

In a Mercator projection, parallels and meridians are represented by straight orthogonal lines, with the equator being the horizontal line placed at the center of the map. The other parallels must necessarily be stretched (east-west stretching). This stretching is accompanied by a corresponding north-south stretching, so that the north-south scale is equal to the east-west scale everywhere.

Mathematically, the Mercator projection is defined as follows: if a point on the sphere has a latitude φ and longitude λ (with λ0 placed at the center of the map), then its projection on the Mercator map will have coordinates:

\[x = \lambda - \lambda_0\]
\[y = \ln\left(\tan\left(\frac{\pi}{4} + \frac{\phi}{2}\right)\right)\]

To achieve this while taking into account that the Earth is not a perfect sphere, we will assume the Earth is a geodesic defined as WGS84 and use the WGS84toCartesian open-source header-only library to convert the coordinates.

The scaled foliage will be placed with the top of the bounding box at the height of the tree. The trunk will be on the ground at the position of the tree while taking the terrain elevation into account. To make sure the trunk is always at the right height, we will use an abnormally long trunk that will be cut to the right height. This will allow us to avoid having either the trunk floating in the air below the foliage or poking through it.

trunk cut
Figure 2. 3D model of a tree with a trunk that is too long

We will then need to place the whole tree at the correct altitude. To do this, we will need to retrieve the terrain elevation at the tree’s position. There are multiple approches possible to achieve this, the most naive one would be to iterate over all the vertices of the terrain mesh and find the closest one to the tree. This is of course very inefficient. A better approach could be to use a raycasting algorithm to find the intersection between the terrain mesh and a ray. The range we could use for this ray could be from -400m (Deep Sea, located at the border of Israel and Jordan) to 6000m (the highest plants discovered growing 6km above sea level). To be more efficient, we could use the min and max altitude of the terrain mesh we are working on.

raycasting
Figure 3. Raycasting of a tree in Grenoble, France

It is important to note that in order to avoid to compute the possible intersection will all the triangles of the terrain mesh, raycasting techniques often use a spatial data structure to accelerate the search. For example, a bounding volume hierarchy (bvh) or a K-d tree could be used.

Example of bounding volume hierarchy
Figure 4. Example of a bounding volume hierarchy (source)

To precisely compute the z coordinate of the tree we can use a barycentric interpolation on the triangle of the terrain mesh that contains the tree. This will allow us to compute the z coordinate of the tree with a high precision especially if the triangle we land on is not flat and/or is very large.

triangle bary coord
Figure 5. Barycentric coordinates of points in a triangle

Next: Mesh Merging

References