CIPA 2003 XIX 11 ' International Symposium, 30 September - 04 October, 2003, Antalya, Turkey 
For instance, an 18-connected line could intersect an 18- 
connected surface without detection. An algorithm for a 6- 
connected line can be found in (Amanatides and Woo, 1987). A 
comparison of the two line types is displayed in figure 6. 
voxel is visible. Whether lying on the backside, or occluded by 
another voxel, the algorithm will correctly tell if the voxel is 
visible or not. 
The basic idea is depicted in Figure 7. 
Figure 6: 6- and 18-connected 3D-lines. 
The algorithm for the 18-connected line can be described by the 
following pseudocode: 
function linetracing (P0=start, Pl=end) 
{ 
let dx = PI.x - PO.x 
let dy = PI.y - PO.y 
let dz = Pl.z - PO.z 
let maxien = MAX[ABS(dx), ABS(dy), ABS(dz)] 
let sx = dx / maxien 
let sy = dy / maxien 
let sz = dz / maxien 
let P = PO 
for (0 ... maxien) 
{ 
call operator with P 
P. x = P.x + sx 
P.y = P.y + sy 
P.z = P.z + sz 
} 
} 
Figure 7: Recovering visibility information 
In Figure 11 on the last page the differences of the projection 
results are displayed, based upon the decision, which voxels are 
excluded from consideration. It can also be seen, that an 
indirect transformation (the image pixel looks up the 
corresponding voxel) delivers by far the best result. 
3.5 Surface Normal Vector 
The surface normal vector can tell us in which direction a voxel 
is facing. It is the normal vector of the tangential surface from 
the voxel of interest. While in polygonal models it is very easy 
to calculate the normal vector (it is simply the cross product of 
two sides of a triangle) it becomes more sophisticated with 
voxel models. 
Our basic approach calculates a least-squares adjustment on a 
specific subset of surface voxels for the plane equation: 
3.4 Visibility Information 
It is often crucial to find out which voxel is visible in which 
image. From polygonal models we know that there are two 
reasons why a point (or a face) is not visible from a certain 
viewpoint. The first and easy case is when the point is lying on 
that side which is facing away from the camera. It is only 
necessary to calculate the triangles normal vector and check if it 
is pointing towards the camera. 
The other case is that a point is occluded by another object in 
between. The major approach creates a depth buffer, which 
stores the distances of the recently projected points. Any point 
further away is just skipped, while the buffer is updated with 
the nearest point at a time. 
As voxel techniques are very different from polygonal models, 
we cannot simply take over their algorithms. The depth buffer 
is flexible enough to apply it here as well, but we will use the 
line tracing to achieve better and faster results. 
Now, when we want to learn about the visibility of a voxel in a 
certain image, a line is defined with the voxel itself as start 
point, and the image projection centre as end point. We will use 
the line tracing algorithm to check each voxel along the line, 
whether it is background (and therefore transparent) or object 
voxel (opaque). As soon as an opaque voxel is encountered, the 
initial voxel can be considered occluded. When the line exits 
the defined voxel cube, it can be stopped, assuming that the 
a-x + b- y + c- z + d = 0 
(2) 
Therefore we define a certain radius within which we take all 
surface voxels (see figure 8) and write them into the matrix A, 
with: 
y\ 
y 2 
Z 1 
z 2 
and the unknown vector: 
a 
n x 
b 
— 
n„ 
y 
c 
U z_ 
(3) 
(4) 
Since only the direction of the tangential surface is of interest, 
not the translation offset d (see equation 3), the unknown vector 
contains only the three elements a, b and c, which directly 
correspond to the elements of the surface normal vector.