CIPA 2005 XX International Symposium, 26 September - 01 October, 2005. Torino, Italy 
804 
elements in different views or scans. Algorithms use 
geometrical information about selected points or, alternately, 
about superimposed geometric primitives such as meshes for 
bottom-up approaches or perspective models for top-down 
approaches. Merging partial clouds is performed by selecting 
manually a number of homologue elements in general position. 
Figure 3: A global view of the textured 3d model 
3. ALGORITHMS DESIGN 
Architectural surveying needs robust software tools for selective 
refinement and grouping around meaningful primitives in 
archaeological or urban surveying. Usual reduction techniques 
for dense information work on superimposed structures 
(meshes, textured surfaces) resulting from the application of 
laser processing, instead of acting directly on clouds of points. 
A crucial difference between the management of digital clouds 
of points in algorithms design is linked to 1) topological 
(proximity), 2) algebraic (local symmetry) or 3) geometric 
notions (fitting to simple geometric primitives). For example, 1) 
laser scanning software tools operate on unordered points which 
can be locally reordered, by applying search criteria around first 
and second levels of proximity; 2) computer vision software 
tools operate by weighted or probabilistic averaging around 
continuities or discontinuities, by extending or breaking local 
symmetries to different levels (from pixel to structural elements 
in perspective models); 3) CAD models privilege some standard 
geometric primitives for linking data to rendered global objects 
and to select optimal geometric primitives to discrete clouds of 
3d points. 
Figure 4: A partial view of walls of the castle with well defined 
depth planes delimiting spaces for different uses 
For 3d rigid scene a minimal choice is given by four non- 
coplanar points which can be interpreted as an affine reference 
tetrahedral. In perspective models for 2D views, all reference 
tetrahedrals are equivalent between them through a projective 
transformation; this well-known fact justifies the choice of a 
tetrahedral containing at least three non-aligned vanishing 
points of each view as vertices. Alternately, if we use 
information about normal vectors to faces lying on meshes, then 
one must take care about changes in orientation of homologue 
faces; in particular, opposite viewpoints induce opposite relative 
orientations for the normal vector to the same face, which could 
give a lack of coherence for global matching. To avoid this 
inconvenient, we have developed a local matching strategy. 
The goal of our volumetric propagation algorithms in a 3d 
model of the scene is the fusion of 2d and 3d information, by 
imposing constraints linked to the automatic identification of 
volumetric primitives and propagation along their boundaries. 
Information fusion has been developed by other experts (see 
[Kampel, Sablatnig, and Tosovic, 2002] for a related approach). 
In our case, we propose a generation of Delaunay 
tetrahedralization similar to the standard in Computational 
Geometry [Berg et al, 2000], but whose facets are adapted to the 
boundaries of architectural objects. It is performed in two steps: 
1) towards the interior of the big tetrahedral of reference T. and 
2) towards the exterior of T. Eventually, a larger number of 
points could be required, depending on the scene complexity. 
Main problems concern to the computer management of 
collapsing/swapping facets on 3d volumetric simplifications 
preserving the global topology of visible objects in the scene. 
To solve them, we develop a geometric search guided by trees 
with recurrent subdivision and grouping. Collapsing/swapping 
processes are allowed in trees, but without breaking the graph 
connectivity, as it is usual in alpha-shapes. 
To avoid an excessive amount of tetrahedral small pieces in 
recursive subdivisions, partial grouping in intermediate cubes is 
developed. The obvious extension to 3d case of flip-flop 
exchange of diagonals in quadrilaterals provides a fitting to the 
simple volumetry. Indeed, every parallelepiped decomposes in 
six 3d simplices. Opposite faces have two pairs of homologue 
diagonals which can be exchanged. Exchange of diagonals in 
opposite sides is extended to an exchange of diagonal planes 
depending on the relative orientation of identified facets, and 
consequently of triangular prisms. In more complex models 
with variable curvature [Martinez et al 2005], 3d-simplices for 
each prismatic component are fitted depending on isosurfaces. 
A coarse model for volumetric propagation is developed from 
an initial small tetrahedral, the only which contains the origin. A 
tetrahedral is adjacent to the initial if they have a triangular 
facet in common. Proximity levels are recursively constructed 
from the initial tetrahedral following a bottom-up approach. An 
adjacent tetrahedral is aggregated to the initial if their facets do 
not cross the identified geometric primitives linked to simplest 
constraints for (coplanar, co-cylindrical) facets. In this case, 
common facets are deleted. Otherwise, query process jumps to 
the next node linked to the next adjacent facet of positively 
oriented tetrahedral. The procedure stops when the boundary a 
“typical volume” (plane, cylinder, in our case) is filled. If the 
list of typical volumes is empty, then a query procedure is 
introduced for identifying coplanar or co-cylindrical facets. 
After merging several scan files, the volumetric propagation can 
be extended to the set of central nodes (one for each scan), and 
to apply a competitive/cooperative algorithm strategy. A 
RANSAC type extension of volumetric propagation based in a 
sparse subcloud is currently under development. Goal of 
volumetric propagation algorithms is the recovery of solid 
structural elements corresponding to walls with architectural 
information by minimizing the computational cost.