7. Implementation

Hierarchical data structure is always based on dynamic data types and so it is not good to implement this data structure in a language without support of pointers or dynamical arrays or something like this. Due to the thing that items of structured grid can be of various character, language with strong type checking would at least complicate the implementation. So it seems that C language should be suitable. Abilities that gives C++ are hard to use in this case, mainly due to effectivity. Thanks to these reasons it was chosen ANSI C as the best language for the implementation of this data structure. Let us summarize information that can be stored in one cell: It is obvious that we cannot store data of this variability in an array, so we have to work with pointers. As a good compromise this approach was chosen:

Now we must notice a property that was still only quietly assumed, it was not anywhere explicitly said. Solving continuity ``on the sides'' with height fields of the same orientation we assumed that resolution of adjacent sides are the same or the samples of the one are a subset of the second. One way how this can be always fulfilled is that we will require the resolution of structured grid to be of type 2^i x 2^j x 2^k, resolution of height field of type (2^m+1) x (2^n+1) (due to splitting we need center element). Doing this we can store only numbers i, j, k (m, n, resp.). Then it is more than sufficient to store one dimension in one byte.

An interesting part is implementation of type for one height of height field. It follows from practice that 8 bits is too small resolution, 16 bits gives good results. We need to represent numbers that lie both inside and outside of the cell. It is not good choice to define global coordinates of height because with increasing depth in hierarchy the accuracy of details does not increase, too. Next, to find if a height lies outside of the cell needs an information where this cell lies in the space and how big it is. Due to these reasons local coordinates inside the cell were chosen. As a good choice it seems to reserve one bit for information if the height lies inside or outside the cell, other 15 bits will denote heights between 0 (including) and 1 (excluding) in fixed point representation (in fact type like int is used). One half of the range lies outside; dividing symetricaly this range we get that we can represent numbers approximately between -0.5 and 1.5 (in cell local coordinates). It remains to decide how to represent intervals above and below the cell.

Sometimes it is necessary to have linear ordered heights. Interval of visible heights then should lie between 0x4000 to 0x8000 (hexadecimal notation; now we assume that height 1 is visible), interval below the cell 0x000 to 0x3fff, above the cell 0x8001 to 0xffff. If we notice that summing in two-byte unsigned arithmetic is a commutative (Abel) group we can do conversion from linear representation to special one by adding number 0x8000 (by subtracting 0x4000, resp.). In this way we get a special code with moved zero, where is

In this code visibility is easily checked; in linear ordering it is better to do comparsions.

Previous chapter Main Page Next chapter