are 
ya 
m 
nd 
tal 
er, 
ed. 
ne 
ge 
bes 
the 
rise 
bed 
à 
1). 
the 
ject 
are 
a 
€ 
nto 
ine. 
de", 
t of 
jest 
ane 
ints 
the 
‘ace 
two 
| by 
face 
‘ace 
ly. 
the 
ore, 
the 
‘the 
the 
] at 
it is 
dex 
tion 
the 
  
  
  
  
  
  
  
  
  
  
  
  
  
X 8 
Object 
Original Plane A / 
x ML 4 V1 ‘ 
AL S 
e 22 À vl Z 
ry [ P d Ray 
| / 
  
  
  
Figure 7. Building the original octant by ray tracing technique. 
of the calculated segments parallel to the Z-direction on the 
ray inside the object are set to one. After generating the ray on 
the original plane, voxels that are inside the object or on the 
object surface have the value 1. As a result, the information 
about the solid object is presented in discrete form in the 
original box where voxels with value 1 represent the object 
and complementary voxels with value 0 describe the 
background. 
The original box is further extended to the original octant with 
dimensions 2"x2"x2". Here, n is determined by the defined 
resolution of octree and the dimensions of the object. Voxels 
in the extended part of the original octant are filled with value 
0. So far, the control as to whether a voxel belongs to the 
object is simplified to check whether or not the voxel has the 
value 1. Actually, the solid information of the object is not 
saved in the way that every voxel is registered, because this 
would need a memory of an array with the dimension of 
2"x2"x2" The memory requirement increases rapidly as n 
rises. Therefore, the run length coding technique is applied in 
the algorithm. For every ray coming from the original plane, 
only those segments on the ray with value 1 are saved. 
Suppose a segment begins at (x,y,z,) and ends at (x,y,z,). Its 
run length is RL=z,-z,+1. Instead of storing RL voxel 
elements, only the coordinates (x,y,z,) and the run length RL 
are registered. Thus, the algorithm does not need to use 
enormous amount of memory to code every voxel 
(proportional to the object's volume), but only to record run 
length parameters (proportional to the object's surface). 
The following functions and subroutines are programmed and 
applied to generate an octree from the original octant: 
UNIDEF: defining an original octant 
SUBDIV: subdividing an octant into its eight 
suboctants 
CLAOCT: classifying an octant to one of the three 
categories (F, E and P) 
OCTCOD: generating octree codes. 
After the octree is coded, objects are represented by their 
octree codes and saved in the data base of octree 
representation. This data base may be used for the further data 
base conversions or directly for geometric processing and 
simulations. 
4. EXPERIMENTS 
Programs for measuring primitives of B-rep and CSG, and 3D 
surface reconstruction from digital images by digital image 
matching and the interface for conversion from digital surface 
models to octree representations have been written in 
FORTRAN on a VAX/VMS system. The following example 
demonstrates the method presented. 
Figure 8(a) and (b) illustrate a stereo image pair of a test 
model which simulates a discontinuous surface. The test area 
has a dimension of about 0.70x0.55 m and consists of objects 
with different shapes including a box, a wedge and a free form 
object. Eleven marked control points were measured 
geodetically. The mean square error of points was 0.15 min. 
The model was photographed by a video camera (Sony 
AVC-3200 CE) with a depth distance of aboutl.5 m. The 
distance between the two camera positions was about 0.3 m. 
In order to obtain more image texture for area based image 
matching, an artificial texture pattern was built by spraying 
color spots on the model. Area based image matching 
produced an approximate surface model. From this first 
surface model, the least square image matching in object space 
was started to refine surface points in relative flat regions. The 
processing of the surface discontinuity began with a 
Sobel-Filtering. Figure 8(c) shows that a lot of small spots 
remain after the filtering, which make edge following more 
difficult. For better edge detection, a median filtering was 
performed prior to edge enhancement (Figure 8(d)), so that the 
small spots and a part of image noise were filtered out. Figure 
8(e) shows the result of the edge extraction by using a Sobel 
operator on the image of Figure 8(d). Obviously, the 
preprocessing by median filtering improves the edge 
extraction. The extracted edge elements were then processed 
by edge following and edge based image matching. 
The combination of results from area and edge based image 
matching provides a digital surface model with extracted 
discontinuities. In order to obtain fine surface structures, two 
more photographs were taken at different locations. With these 
images, the area and edge based image matching were also 
carried out. Figure 8(f) is the reconstructed 3D digital surface 
model made from the combination of results from these two 
stereo-image pairs. 
To generate an octree representation of the test model, an 
original octant with a dimension of 64x64x64 was defined. A 
ground Z value was added to the digital surface model in 
figure 8(f). Therefore, the digital surface model became a 
digital solid description of the test model and was transformed 
into the original octant. After the subdivision of the original 
octant and octree coding, a linear octree representation was 
built. Figure 9(a), (b) and (c) show octants of 2nd, 4th and 6th 
level. Figure 9(d) displays a wire frame model of the final 
octree representation. In this figure, the meaning of octant is 
extended, i.e. octants can have different dimensions in the 
three directions of the Cartesian coordinate system. From the 
data structure of octree representation in figure 9, we can see 
that objects are partitioned hierarchically into octants of 
different sizes. At first, an object is approximated by large 
octants for a rough description, and then by smaller octants for 
finer structure of the object. These characteristics can be used 
especially in the simulation of manufacturing processes, 
collision control for industrial robots and for path planning of 
mobile robots. 
In order to generate a B-rep of the test model dimensions and 
parameters of shapes and locations of regularly shaped objects 
were measured interactively on a monitor by using least 
squares image matching. In addition, 36 surface points of the