t light, 
ithM,, 
nixing, 
n, NH 
nalysis 
r Pho- 
nmetry 
F) of à 
; Sym- 
BRDF 
Vol. IV, 
, of the 
09 
Areas, 
ings of 
. 1474- 
tion of 
5-163, 
Source: 
ements 
a using 
emote 
an Go- 
venue, 
iety of 
pectral 
ference 
| High- 
Aeeting 
  
Antonio Ruiz 
  
A COUNTRYWIDE TIN ELEVATIONS DATABASE 
Antonio RUIZ 
Institut Cartografic de Catalunya 
Parc de Montjuic. 08038 Barcelona, Spain 
toni @icc.es 
KEY WORDS: Delaunay triangulation, Quadtree, DTM, TIN, Database 
ABSTRACT 
The regular grid elevations database that the Institut Cartografic de Catalunya has since 1987 is insufficient for certain 
applications. For this reason, we started the development of a new database. It is our aim to build a one piece TIN model 
with precision enough to generate cartographic quality contours at 1:5000 scale and smaller for the whole country (32000 
sq. km). We plan to load approximately 300 million points. The model must be dynamic because it has to support 
insertion and deletion, the surface model should be refinable, algorithms have to be robust and data integrity must be 
reserved. 
The chosen triangulation is constrained Delaunay triangulation (CDT) and we employ the incremental construction algo- 
rithm. Its performance is good when the input data are well distributed and is fully dynamic. 
The main difficulty is how to deal with a triangulation in external memory. Common triangulation programs hold all 
the information in core memory and cannot triangulate very large data sets (some million vertices) because the system 
degrades very fast due to the page faults. We use a bucket point region quadtree to help point location and to reduce page 
faults by bucketting. ; 
The surface model is a polyhedral TIN terrain by default but it can be extended in different ways. The use of object- 
oriented technology means that these extensions can be programmed easily and gives the design great flexibility. 
1 INTRODUCTION 
Since 1987 the Institut Cartografic de Catalunya (ICC) has a Digital Terrain Model (DTM) database with a 15 m regular 
step for our country (32000 sq km). The main use of this DTM is the rectification of images and the shadowing and 
hypsometric coloring of maps. 
At the beginning the database was loaded with data compiled with a Gestalt Photomapper IV and analytic stereoplotters. 
At the same time the 1:5000 topographic (MTC 1:5000 v1) maps were produced with contours computed from a TIN 
model. The TIN was build from profiles and breaklines compiled with analogic and analytic stereoplotters and the DTM 
database was completed with regular grid data interpolated from the TIN models. 
The TIN model of Catalonia from the MTC 1:5000 v1 consists of some 75 million vertices and it is not available on-line. 
Now we are producing the second version of the 1:5000 topographic map (MTC 1:5000 v2) and we expect from 5 to 6 
times more points. In this new version almost all the points and lines from the topographic map that lay on the ground 
enter to form the TIN model. The contour lines for the MTC 1:5000 v2 are computed from this TIN model. 
2 REQUIREMENTS TO A NEW DTM DATABASE 
The on-line available grid model is not enough for contouring at large scales or for the orthorectification of large bridges in 
roadways, buildings, etc. We would rather have the TIN model available on-line but with standard programs is not possible 
to build a huge TIN in one piece. Commercial TIN programs are limited by the core memory of the computer because they 
require to have all the information in memory and rely on the standard paging services of the operating system when more 
memory than available by hardware is needed. For that reason, standard programs can hardly triangulate some million 
points and they cannot deal with datasets of the size of ours. The most difficult aim of this project is to build such a large 
TIN model in one piece. The triangulation we have chosen is the constrained Delaunay triangulation (CDT) but this is 
only a subdivision of the surface domain. We plan to extend the commonly used polyhedric surface model to represent 
both the digital elevations model (DEM) and the digital surface model (DSM). The DEM must be accurate enough to 
generate cartographic quality contours at 1:5000 scale for the whole country. The model required for the rectification of 
Images is the DSM. It is the visual surface that follows the top of the buildings and the trees seen from above. Some work 
has been done to extend the surface model to represent buildings, bridges and to give double z values in water covered 
regions (bathimetric depth or heigh of the water surface). The design is flexible enough to improve and extend the surface 
model as needed. The model must be dynamic because it has to support insertion and deletion at any time, algorithms 
have to be robust and data integrity must be preserved. 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 785