EEE WEN
M EE ER SE EE
expanded to 3D, now using hierarchically structured boxes
instead of rectangles.
In a 3D model, R-trees would be used to store 3D bounding
boxes (figure 2): At the root level, one gigantic box embraces
the entire city. In this box, several smaller boxes contain
districts of the city. Within these city-boxes, smaller boxes
might be used to build bounding boxes of streets. The next
R-tree level consists of bounding boxes holding buildings or
other elementary objects. Finally, the R-tree concept might
be used to partition buildings into even smaller objects —
roof and body, in the next level windows, doors, chimneys
etc. Thus, R-trees are a data structure that is simple to
manage and yet allow the storing of data of an entire city in
surprisingly few levels.
Notes: The previous paragraph only describes the basic con-
cepts about how R-trees could be used to store 3D graphical
data. In reality, some more levels might be useful to limit
the number of objects within one level. Please note also that
the R-tree is organized in a three dimensional way from the
beginning. Of course the z-coordinate is of little interest in
the higher levels of the R-trees, as most big cities are more or
less flat (e.g. the z-coordinate range is very small when com-
pared to the range of x- and y-coordinates). The z-coordinate
gets more and more important in deeper levels of the R-tree,
where buildings or other objects are split to sub-objects. This
consequent 3D design makes it possible to use the database
for objects other than cities, e.g. to build a VR-model of a
museum, an airport or of a big shopping center.
As the title of this subsection suggests, R-trees can easily
combined with the LOD idea. Each level of the city-R-tree
simply is a level of detail! The only point where the R-tree-
concept must be expanded is the data stored within one box:
While traditional R-trees up to the second lowest level only
contain a list of sub-boxes (or sub-rectangles in 2D), LOD-R-
trees also include some graphical information that is sufficient
to visualize the interior of the box in a coarse quality. If this
quality is not sufficient for a certain point of view, a more
detailed graphical description can be obtained from the sub-
boxes within the current box.
3.5 On our flight to the Stephansdom
The best way to explain this concept is an example: imag-
ine, you are flying in a helicopter towards Vienna. Suddenly,
getting around some hills, you see Vienna for the first time.
You are still quite far away — thus Vienna is only a more or
less flat area covered with buildings and plants and divided
by the Danube. To visualize Vienna from this viewpoint, a
very simple DTM-model of Vienna with some coarse textures
of aerial images is sufficient. This data is stored in the outer-
most R-tree-box; there is (yet) no need to traverse the R-tree
to any deeper level.
As you slowly come nearer, some outstanding objects — per-
haps the radio tower, the UNO city building complex or what-
ever — must be visualized in more detail to preserve a photo-
realistic quality. The graphical data needed for rendering can
be obtained from the R-tree on the next deeper level. On your
flight to the center of Vienna, this process will constantly be
repeated, getting exact graphical models of objects near the
helicopter out of lower R-tree-levels and less exact models of
objects far away form higher R-tree-levels. The amount of
data needed to draw the entire scene will stay approximately
stable; objects near the viewpoint will contribute most of this
R-tree root (whole city)
one district
IN district 1
district 2
block of buildings
block of buildings one building
one building
Figure 2: Examples for some R-tree levels (all levels are
3D, although some are shown only as 2D projections)
data.
When you finally land in front of the Stephansdom (a big
cathedral in the central city), this extraordinary building will
be drawn in the best possible quality. While standing and
staring at the picture it will improve progressively as more
and more data in growing levels of detail is loaded from the
database and used to refine the picture. Technically speaking,
you are now in at the bottom end of a very small sub-tree of
the entire R-tree of Vienna.
3.6 3D spatial access, perspective querying
As the data structure is in a high degree hierarchical, spatial
queries will be organized in a hierarchical way as well. Search-
ing for an object in 3D-space means traversing the R-tree.
As the whole tree is based on bounding boxes, a few small
queries in each level of the R-tree are sufficient to find objects
in 3D-space. (Small means that each box of the R-tree only
contains a rather small number of objects (sub-boxes), e.g.
all houses of one (part of a) street.) Searching in 2D R-trees
for a point or for all objects within a rectangle or box does
not impose any difficulties.
What is really new when compared to traditional R-trees ap-
plications is querying for all points within a pyramid or cone
of vision. It will be that kind of query that will be needed
most frequently while visualizing a scene. A straightforward
realization of a perspective query would result in complex ge-
ometric formulas that cannot possibly handled by any query
language however sophisticated. Besides it would result in
a huge number of objects retrieved, although most of them
would contribute little information actually needed for visu-
alization.
A more intelligent scheme is needed. To simplify the query
the pyramid of vision can be split into axially parallel boxes.
This splitting has an obvious disadvantage: it results in a con-
200
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B2. Vienna 1996
wit
As
pres
the
JPE
mer
use
dat;
get!
whi
To :
bitn
limi
if m
qua
If h
relo;
4.1
The
Cyb
Gray
late
men
(sen
2D (
ima
