Antonio Ruiz
inserted in the bucket PR-quadtree. Duplicated points and crossing edges are detected during insertion. Vertices closer
than a minimum to an existing vertex are not allowed. Vertex and edges have attributes that identify them as topographic
objects. For example, we distinguish required edges as belonging to a road, a railway, a river, etc.
The data is stored in the commercial database O». AIl the programming is done as if all the data was in memory. O» takes
care of recovering data from external storage as needed, maps the database pointers and the C++ program pointers and
updates the information on disk at commit time. O» provides us with the standard properties of a transactional database:
atomicity, consistency, isolation and durability.
4 CURRENT STATE OF DEVELOPMENT AND FUTURE WORK
In order to reduce the insertion overhead the edges are not stored in the QT at this stage of development. During the
insertion of the data corresponding to a region, edges are destroyed almost at the same speed as they are created and it is
a waste of time to store them in the QT. This has the bad consequence that performance decreases when a lot of data has
been inserted on the database because there is no bucketing on the edges. We rather would store the edges in the QT when
we close the transaction and no more updatings are expected for the region. Our insertion transactions correspond usually
to the insertion of all the vertices of a sheet map.
The development of the software started on an old Unix machine with 64 Mb of RAM. Up to 2.8 million vertices where
triangulated and then the performance decreased significantly. Now we are completing the migration of the application to
a PC with Windows NT operating system.
One possibility to improve the edges storage is to made use of the clustering facilities that O» database provides. We can
create a spatial index on the edges to instruct the database manager to keep closer in disk those objects with closer index
values. A valid spatial index is the Morton code of the leaf containing the edge origin.
A big source of trouble in computer programming with C or C++ is freeing program memory and garbage collection. We
never free program memory directly because we do not know if an object will be needed later again or not. Instead, when
we are short of memory we close database and reopen it. This operation frees all the program memory. When one object
is requested again, it is recovered from O» buffers and recreated in program memory by the database services. All the
data that comes from a photogrammetric model or one 1:5000 sheet map can be inserted into the database without closing
for freeing memory but to insert different sheet maps, we employ separate runs of the insertion program.
Another weakness of the current state of development is the TIN traversal method. We use process bits to indicate
wheather a vertex or an edge have been traversed and a stack to hold the set of edges to be traversed in the iterator classes.
This has the bad consequence that any recovery of data from the database is a read and write transaction because the state
bits change their values from unprocessed to processed and after the traversal has been completed another traversal is
required to change the state bit values again to the unprocessed state. For this reason some transactions are more complex
than they should be and multiuser access for reading of the one region is not available. To solve this problem we have
to rewrite iterator methods to perform the traversal without process bits and without stacks (Gold and Cormack, 1986,
de Berg et al., 1996).
The internal nodes of the quadtree can store generalizations of the surface stored in the leaves. A simple grid model of
fixed step interpolated from the TIN can be stored in the internal nodes inmediatly over the leaves that contain the TIN.
The internal nodes of lower resolution can hold low pass filtered models of decreasing resolution but this generalized
models have to be developed.
5 CONCLUDING REMARKS
We have shown the main difficulties to build a large TIN model and we have presented our proposed solution. We also
have shown some extensions to the TIN polyhedrical model that are interesting for terrain modelling.
We have tested a preliminary version of the software with nearly 2.8 million vertices in an old Unix machine. Now we
have moved the software to another platform and operating system but more performance improvements are still required
until we can say that the system is operational.
REFERENCES
Bernal, J., 1988. On constructing Delaunay triangulations for a set of constrained line segments. Tech Note 1252, National
Institute of Standards and Technology. Department of Commerce.
790 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.
Chen.
Data |
Davis
de Be
storag
de Fk
Mode
Fortui
Gold,
Spatia
Good
IEEE
Guiba
diagra
Lawsc
Press,
Lee, I
93), 1
Meyeı
Nelsoi
pp. 19
Paul C
Prepai
Ruiz,
In: VI
Samet
Samet
Seidel
TU Gr
Shewc
Geom
Shewc
on app