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