International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
and the last layer corresponding to the DTM of least resolution.
Therefore, vertical indexing can be seen as sorting data
according to the pyramid layer position (index).
The vertical resolution for each layer is relative to the full
resolution DTM. The number of layers in a pyramid, and each
layer's (relative) resolution, are up to the user to define.
Generally speaking, the more the layers, the smoother the
transition between these layers. Unlike image pyramid layers,
increasing the number of layers in a Terrain pyramid will not
result in more data to be created, duplicated, and stored. It
merely increases the number of classifications. However, it does
increase the preprocessing time, and potentially the number of
multi-points when points within the same tile are further divided
into subgroups based on their vertical indices (to be discussed
later).
Pyramid layers can be built by deriving a DTM of lower
resolution from the full resolution one, through generalization
(Weibel, 1992; Peng et al., 1996). A number of algorithms have
been published in the literature, such as DTM filtering (Loon,
1978; Zoraster et al, 1984), DTM compression (Gottshalk,
1972; Heller, 1990), and structure or skeleton line
generalization (Wu, 1981; Yoeli, 1990; Wolf, 1988; Weibel,
1989). An evaluation of these three types of methods can be
found in (Weibel, 1992). Other algorithms are also available in
the area of computer graphics, mainly to serve real time
visualization (Kalvin, 1996; Hoppe, 1998; Lee, 1998; Reinhard,
1998). This design adopts the DTM compression (or point
decimation) approach for point features.
Line and area features require a generalization approach that
takes into account topological relationships and the vertical
dimension. Unfortunately, there is still no good algorithm
available for automated generalization of line and area features.
Furthermore, different applications may have different
generalization requirements and criteria. Based on these
considerations, this design introduces three mechanisms to
index line and area features: 1) use user provided multiple
versions of pre-generalized terrain measurements, and associate
each version with a corresponding layer in a DTM pyramid; 2)
adopts Line Generalization Tree (Johns and Abraham, 1987),
but supports more algorithms; 3) uses on-the-fly automated
generalization of the original measurements.
The Line Generalization Tree has a limitation that only
selection of vertices can be performed. This project will focus
next on developing algorithms for on-the-fly automated
generalization, and the enhancement of the Line Generalization
Tree.
Verucal indexing adds another control for grouping data within
the same tile. Instead of putting all the points within the same
tile into one group, only those points that share the same vertical
index will be grouped into a single multi-point. Because points
are organized according to their corresponding tiles and vertical
indices, spatial queries can retrieve data efficiently.
3.3 Updating Data
Requirements for terrain update come from two aspects: the
measurements, and the rules. Any changes regarding these two
will require the internal vertical indexing to be updated.
Because rules are private to the terrain dataset, updating rules is
simple and straightforward. Measurements, on the other hand,
284
are shared by other applications, and can be modified without
going through terrain datasets. In order to keep terrain datasets
- and measurements in sync, some mechanisms are required that
keep the datasets informed whenever an update is performed on
the measurements. This is done through Events and Invalidated-
Area. An Invalidated-Area is a region where changes of
measurements have occurred. It allows an outdated terrain
dataset to be updated locally.
When an update to a measurement is committed, an Event is
broadcast. Those terrain datasets that are affected will update
their Invalidated-Areas upon receiving the Event. Users will
then decide when to update the affected terrain dataset.
4. APPLICATION EXAMPLES —SPATIAL QUERY
AND SURFACE ANALYSIS
Spatial query and surface analysis are Terrain's two most
important applications. A typical spatial query takes an area of
interest 4O/ and a (relative) vertical resolution AZ, and outputs
a TIN or GRID DTM (specified by the user, Figure 4). The
output can be an (transient) object that will be persisted only if
requested by the user. Area of interest AOZ may contain
multiple regions. In this case, there will be a list of AHs, each of
which corresponds to a region in AOL A multi-region AO! will
result in a multi-resolution (continuous) DTM, while a single-
region AOI will produce a single-resolution one. With all the
indexing support, the system can quickly allocate those multi-
points that contribute to AH but are also within the query area
AOI. Line and area measurements can also be quickly identified
Terrain Query (A OI, AH)
DTM .
(TIN/GRID
Figure 4: Examples of Terrain application.
using vertical indices.
An interesting example of this dynamic query is surface
rendering. The zoom in and zoom out operations represent a
typical scenario of multi-resolution queries (Figure 5). The
shaded area in Figure 5a shows the center part of the state of
Massachusetts in the US. The full resolution model
corresponding to the area contains about 16 million points,
covering an area of 8800 square kilometers (110km x 80km).
Obviously, it is a waste to apply all the points when zoomed to
full extent, as many of them may be mapped onto the same
pixels of the screen. In this case, a well-calculated, simplified
version of the DTM may suffice to provide a good overview of
the terrain. This also reduces the time used in DTM generation
and rendering.
Internati
Are LUE
Æ Æ cntyspl
m
[oes k
The DI
and wa
sub-are
provide
extent (
higher
sized) I
5c, anc
calcula
this prc
to use
layer ir
Users «
perforn
a DTM
can haj
require
contoui
