Tree structures are very central in the paradigm of global terrain visualizations, regardless of how many dimensions the application displays. We touched the Quad Tree briefly in section 2.1. “The Fundamentals of Level of Detail”, and saw a conceptual model of one in figure 1.
Since tree structures are going to be essential in all implementations later in this thesis, we need to give a thoroughfare on how to incorporate Quad Trees in an application for
visualizing topography. Structuring terrain models in a Quad Tree structure, allows us to experience terrain models in a highly optimized manner. This is possible because the virtual environment is represented by a set of tiles that each can recursively be exchanged with four more detailed ones. Nothing prevents one part of the model from being very detailed while other parts are displayed with low level of detail. As such, it is possible to examine important parts of the model in great detail, since less important parts are kept at low level of detail.
Often, but not necessarily, the parts of the environment being considered important, are those being close to the user.
In this thesis, we are going to use a character naming convention for the tiles in a Quad Tree Structure, in addition to the standard terms used for trees in mathematics. When four tiles together represent the same topographical area as a single tile, the four tiles are said to be the children tiles of the single tile. The single tile, on the other hand, is said to be the parent tile of the four others. The four children tiles get the names A, B, C, and D respectively, starting with the lower left tile (when the tile is seen from above), moving counter clockwise. Each of these four children can have their own set of children. These children will inherit their
parent’s name, but will get an additional character at the end of it. The top-level tile that represents the entire model (at a very low level of detail) is called the root tile. This uniform division of tiles is highly predictable, and one can easily calculate the size or position of any given tile just by knowing its name and the size and position of the entire model. Let us start out by finding a general recipe for calculating the size of an arbitrary Quad Tree tile.
2.4.1 Calculating the Size of a Quad Tree Tile
The Tile Builder is able to calculate both size and position of any tile in the model by looking at the tile ID and the by knowing the size and position of the entire model (the root tile). This derives from the fact that every children tile has an ID with one more character than its parent.
At the same time, the children tile is 1/4 of its parent's size (all edges of a children tile are half the length of those of its parent's). Therefore, a tile with an ID containing n characters, has edges that are 1/2n of the length of the root tile's edges. In figure 9 we can use this formula to calculate the length of the edges of tile DDD. Three characters in the tile ID gives edge length LDDD = (1/23) * LROOT = (1/8) * LROOT. We can see from the figure below that this is correct; It takes 8 lengths of DDD (LDDD) to cover the length of ROOT (LROOT).
Figure 9 – Illustration of Quad Tree Tile Proportions
2.4.2 Calculating the Position of a Quad Tree Tile
In order to calculate the position of a tile, we need to know three things: The size of the root tile, the position of the root tile, and the unique name of the tile (ID). Let us take the
coordinate of the root tile as a point of departure. We define origo to be the "upper left" corner of the root tile (see figure 10). Then we define Lx(n)= Lx(0) / 2n to be the length of a level n tile (a tile with name/ID made up of n characters) in the x-direction, and Lz(n)= Lz(0) / 2n to be the length of a level n tile in the z-direction.
Figure 10 – Illustration of Quad Tree Tile Positions
If we now traverse the tile ID, character for character, left from right, each character specifies a relative, cumulative movement (offset) away from origo. The character's position in the ID denotes the length of the movement, and which character is used denotes the direction of the movement. This is summarized in table 1.
Charpos x-offset: z-offset:
An 0 Lz(0) / 2n
Bn Lx(0) / 2n Lz(0) / 2n
Cn Lx(0) / 2n 0
Dn 0 0
Table 1 - The Cumulative Movement Associated With Each Character in the Tile ID
2.4.3 Example - Size and Position of a Quad Tree Tile
Let us now show the calculation of size and position of a tile with an example: The root tile of a model is located (has its upper left corner) at (x=100, y=100, z=100). The size of the root tile is (x=64, z=64). Let us try to find the size and position of tile ABCD.
Since the ID of the tile has length 4, we know that the length of tile ABCD in the x-direction is Lx(4) = Lx(0) / 24 = 64 / 16 = 4. The same equation, only inserting the z-length of the root tile instead of the x-length will give the same result for the length in the z-direction (Lz(4) = 4). We now know that the size of tile ABCD in this model is (x=4, z=4).
In order to find the position of tile ABCD, we start out by looking at the offset in the x-axis.
According to table 1, we see that an 'A' in position 1 tells us that tile A has the same
x-position as the root tile (offset = 0). The 'B' in x-position 2 tells us that tile AB has an additional offset Lx(0) / 22 = 64/4 = 16 in the x-direction. The character 'C' in the third position gives an additional offset Lx(0) / 23 = 64/8 = 8 in the x-direction. Since the fourth character, which is a
'D', gives no offset in the x-direction, we can add the cumulative offsets in the x-direction.
The tile ABCD has a total offset ∆x = 0 + 16 + 8 + 0 = 24. The absolute x-position of tile ABCD is: ABCDx = rootx + ∆x = 100 + 24 = 124. We then perform the same calculation once more, now using the last column in table 1, to find the offset in the z-direction. It should give the z-offset ∆z = 32 + 16 + 0 + 0 = 48. The absolute z-position of tile ABCD is then:
ABCDz = rootz + ∆z = 148. We have now found the absolute position of tile ABCD: (x=124, z=148).
2.4.4 Finding Parent and Children Tiles in a Quad Tree Model
Finding a tile's parent- or children tile is a trivial task. Every tile T has a parent Tparent with the same tile name (tile ID) minus the last character (needless to say, the root, having no
characters in its tile name, has no parent). In addition, every tile T has potentially four children with the same tile name, where the characters 'A', 'B', 'C', and 'D' are appended.
2.4.5 Finding Neighboring Tiles in a Quad Tree Model
Finding neighboring tiles is slightly more complicated than calculating size and position. First of all, we need a definition of a tile that is positioned on the border of the model. A tile with an ID containing only the characters 'A' and 'B' (or just one of them) belongs to a tile
positioned on the southern border. A tile with ID containing only the characters 'B' and 'C' (or just one of them) is positioned on the eastern border. A tile to the north only contains 'C' and/or 'D', whereas a tile to the west only contains 'A' and/or 'D' (see figure 11).
Let us now start out by making a recipe for finding the given tile T's closest neighbor to the south (positive z-direction). The first step is to find the latest occurrence of either character 'C' or 'D'. Since we just defined a tile with an ID not containing the characters 'C' and 'D' as a southern border tile, we know that every tile with a neighbor to the south must have a tile ID with at least one 'C' or 'D'. Then we replace this character with the character specified in the column "South" in the Quad Tree Neighbor Matrix (table 2). Next, we swap all the
subsequent characters in the ID with the characters specified in the same column. Using this approach to find the tile DDA's closest neighbor to the south, we find that the second
character in the tile name is the latest occurrence of either 'C' or 'D'. We see in the column called "South" in the Quad Tree Neighbor Matrix that a 'D' should be converted to an 'A' and the subsequent characters, being a single 'A', should be converted to a 'D'. We can see from the complete level 3 Quad Tree that the tile DAD is in fact tile DDA's closest neighbor to the south.
When finding the tile to the east we search for the latest occurrence of either the character 'A' or 'D'. To find the tile to the north, we search for the latest occurrence of either the character 'A' or 'B', whereas we search for the latest occurrence of the character 'B' or 'C' when finding the tile to the west. Finding Tile T's closest neighbor to the north-east is simply solved by dividing the task into finding the tile that is east to the tile that is north of T.
Figure 11 – A Complete Level 3 Quad Tree Table 2 - The Quad Tree Neighbor Matrix
2.4.6 Calculating the Number of Levels Needed in a Quad Tree
The depth of the Quad Tree is not a result of the model's size only. Two other factors play an equally important role, viz. the resolution of each tile and the desired accuracy. The formula is shown in figure 12, where the nearest positive number greater or equal to n is the number of levels required. Model Area is the total area of the root tile of the model. We saw in section 2.4.1. "Calculating the Size of a Quad Tree Tile" that the edges of the tiles are halved each time we move to a higher level of detail. Since all tiles, regardless of level, has a constant dimension, or resolution, we know that the precision is doubled for every new level added to the Quad Tree. Calculating the number of times we must double the precision before it suits our needs is narrowed down to the logarithmic equation below.
Figure 12 – The Three Factors Deciding the Depth of a Quad Tree
As an example, let us calculate how many levels we need to reproduce the topography of a 100 x 100 meter area with centimeter precision, using meshes consisting of 101 x 101 vertices. The square root of 1002 is 100, and the dimension of the meshes is 100 x 100, of which the square root is 100. This gives us the following equation: n = 1 + log2
(100/(100/0.01)), which gives n = 7.644. Rounding this number up gives us 8, which is the number of levels we need in order to make the described model more accurate than one centimeter.
3 Related Work
In this chapter I will represent some existing projects which all approach the paradigm of modelling global 3D topography, although from different angles. The military has,
historically, been an impetus in the research of large 3D models, utilizing them for combat simulations or major incident drills. In the latter years, however, due to the increased capacity of personal computers, the special field of terrain modeling has gradually become more common as desktop applications; or even as internet applications.