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:
- nothing;
- material:
- memory needed for material definition is not uniform;
- at least information about optical properties,
hardness, permeability and distribution of cracks must be stored;
- height field:
- size is various;
- at least resolution, orientation,
height field data, material below height field, another
information like about water, objects on it etc. must be stored;
- structured grid:
- size is various;
- resolution and the cells must be stored.
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:
- array of cells contains heads of lists;
- if the head is equal to NULL, the cell is void;
- there is an (global) array of materials; if the head points somewhere
into this array, the cell is entirely filled with appropriate material;
- in other cases it is true head of list:
- items of list are of different type; all of them are based on
struct type;
- each item contains a pointer to the next item and type of current
item;
- if the type is HF, it is a height field and struct
contains extra information: resolution of height field, material below
height field, orientation, information in what sides of cell continuity
must be solved (only for speedup, it is not necessary), pointer to an array
of heights;
- if the type is GRID, it is structured grid and struct
contains extra information: resolution of the grid and pointer to an array
of cells;
- another information like objects, textures etc. are described in other
items of the list; at this time only specification is done
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
- 0x0000 - the smallest visible height (0)
- 0x4000 - center of interval of visibility (0.5)
- 0x8000 - the highest visible height (1)
- 0x8001 - the smallest height above the cell (approx. 1.000030518)
- 0xbfff - the highest height above the cell (approx. 1.499969482)
- 0xc000 - the smallest height below the cell (-0.5)
- 0xffff - the highest height below the cell (approx. -0.000030518)
In this code visibility is easily checked; in linear ordering it is better
to do comparsions.
Previous chapter
Main Page
Next chapter