The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B5. Beijing 2008 
701 
in the object space using the original vertices, the intersecting 
points and the points of triangle B which are inside of triangle 
A. A Delaunay triangulation algorithm with an additional 
constraint to preserve the original border of the triangle A is 
applied. The subdivision of triangle A replaces the original 
triangle A in the dataset. In the following the new triangles are 
handled like the original triangle. After the whole processing all 
the triangles are sorted or subdivided in fully visible and fully 
invisible triangles. Figure 2 shows the basic principle of the 
visibility analysis algorithm. 
During the implementation different special degeneration cases 
like identical points, lines as well as triangles (in object and in 
image space) had to be considered to enable a fully automatic 
procedure. 
The algorithm has a complexity of O 2 . To reduce the processing 
time, the base dataset is reduced by determination of the visible 
part of the original dataset in each image using the projection of 
the image boundaries into the object space. In case of an 
ordered triangle vertex definition, an additional back-face 
elimination can be conducted for a further reduction of triangles. 
It has to be pointed out that this step is not compulsory. 
Nevertheless, it can reduce the amount of processing time 
significantly, depending on the dataset. 
The algorithm requires a small amount of memory. It only 
stores the triangles in the RAM with 76 byte per point plus 24 
byte for each triangle. For example, the required memory for a 
closed surface of 1 million triangles is around 95 MB. 
Figure 3 shows an example of the result of the visibility 
analysis of the dataset. Corresponding datasets are available for 
all camera positions. The colours of the triangles in this 
visualization are defined random wise in order to make it easy 
to recognize single triangles and to visualize the complexity of 
the TIN. 
3.3 Triangle to Image Assignment (TtIA) 
The Triangle to Image Assignment combines the separate lists 
of visible triangles together to achieve a complete textured 
model. In general, two ways are available to combine multiple 
data or images. 
The first is to combine all available or suitable texture datasets 
using an averaging procedure for each pixel. The result of this 
algorithm is a model with a very smooth visual impression. 
Colour and brightness differences are eliminated. On the other 
hand this smoothing eliminates the high frequency information 
and introduces errors, caused by erroneous image orientations 
(El-Hakim, 2003). 
o 
© 
f Projection centre 
Intersecting points and vertex 
of the upper triangle inside the 
lower triangle in image space 
Re-projected intersection 
points and vertex in object 
space 
Figure 2. Visibility Analysis 
Figure 3. Result of the visibility analysis (image 8) 
(a) View from camera position 
(b) Side view 
The second method avoids averaging to reduce the loss of high 
frequency information or details as much as possible. Therefore 
only one data source for each triangle is used. Consequently 
high frequent information is preserved. This method is used in 
the presented workflow. To determine the best texture for each 
triangle, parameters to evaluate the quality of the texture have 
to be introduced (Frueh, 2004). The two main parameters, 
distance and viewing direction, were used for our datasets. The 
distance is defined by the distance between the triangle and the 
projection centre of the camera. The angle is defined by the 
viewing direction of the camera and the surface normal of the 
triangle. The combination of both parameters finally leads to 
the resolution of the image data on the object. 
For each triangle, lists of available data sources (images) are 
generated using the results of the visibility analysis. Afterwards 
the above mentioned texture quality parameters are calculated 
for each triangle to find the source with the highest resolution. 
After processing of each triangle, the TtIA is finished. Finally, 
the texture (uv-) coordinates for each vertex are determined by 
re-projecting the object coordinates onto the particular image. 
Figure 4 shows the result of this procedure for two camera 
positions. 
Figure 4. Result of the TtIA for two camera positions