ISPRS Commission III, Vol.34, Part 3A , Photogrammetric Computer Vision‘, Graz, 2002 
  
Lidar Data 
Initial Terrain Surface Model Generation 
Y 
| 
Downward | 
Divide-and-Conquer Triangulation | 
| 
4 NS 
Model Upgraded | Current 18 current = 
— — — —— M | Model Stack &.. model stack ~ 
| ; re ad 2. empty? ^ 
4 T * No n pty? 
| Yes Y Yes 
ls buffer. TN 
< terrain space »-«4— — — — — ——4 ) 
[7 5 S i \ ó h 
AS : empty? 
| Triangulation | 
Plane Terrain Prior 
   
     
  
  
Tetrahedral Terrain Surface Model 
Hypothesizing 
  
  
A — pt A 
4 | Plane 
| Terrain Prior 
  
  
  
  
  
  
1s on-terrain’ > 
“stack empty?” 
Y 
D 
EE RS ETES = 
Termination ) 
| || On-Terrain ie Noi... 
meet Point Stack | SA EET = 
Figure 4. Overall strategy implemented in our terrain surface 
reconstruction algorithm. 
4.1 Initial Terrain Surface Model Preparation 
À terrain surface model y is initialized with a rectangle, which 
has four corner points assigned as on-terrain points. These 
corner points can be easily computed by the use of the domain 
information of the LIDAR dataset. First, a rectangle that covers 
the entire LIDAR points S is generated and the x and y 
coordinates of its four vertices are computed from the given 
domain information of S. A TIN is constructed using the entire 
S and the four vertices of the rectangle generated. Then, z values 
of neighbouring points connected to each corner point are 
averaged, and this value is assigned to the z values for the four 
vertices of the rectangle generated. These corner points are 
labelled as on-terrain points; hence the initial terrain surface 
model is prepared (see the top of Figure 5). 
Since neighbouring points connected to the corner points are 
explicitly considered as on-terrain points for the computation of 
z values of the corner points, these may include errors. However, 
the size of a local terrain surface model reconstructed by the use 
of these corners gets smaller through our recursive divide-and- 
conquer triangulation process, hence its modelling error can be 
minimized. 
4.2 Downward Divide-and-Conquer 
We use two propositions for the downward divide-and-conquer 
triangulation process; 1) any point cannot be located underneath 
a reconstructed terrain surface model, and 2) if proposition 1 is 
A - 340 
not valid within a local terrain surface model @,, a point with 
the maximum negative distance measured from 6, is selected as 
the most reliable terrain point. 
An initial terrain surface model is given as a rectangle 
iU Y where k=1. The first proposition is investigated over the 
individual ÿ, . If any negative point located underneath a model 
¢, is found, its distance is measured from ÿ, and stored in a 
sequential data list. When this process is completed over ¢, , a 
point with the maximal negative distance is selected from the 
sequential list and assigned as an on-terrain point according to 
the second proposition. This investigation process to look for 
the negative points is made over the entire model space {g,} . 
Then, a TIN is constructed by these newly found on-terrain 
points and the ones used for a previous terrain model. Hence, 
the dimension k of the reconstructed terrain model increases. 
This downward divide-and-conquer triangulation process 
continues until no negative point is found within the entire 
model {g,} (see Figure 4 & 5). 
  
Figure 5. Illustration of the downward divide-and-conquer 
triangulation process. 
4.3 Upward Divide-and-Conquer 
A set of the planar terrain surface models {¢,} reconstructed by 
the downward divide-and-conquer triangulation is stored in the 
form of TIN in the “current model stack”, from which a model 
¢, is selected. A set of member points 5; located within 9, is 
obtained and its relative vertical heights measured from 6, are 
computed. Then, a condition for terrain fragmentation 
mentioned in the previous section is investigated over 9, when 
ó, is given; if the buffer terrain space generated by J, is not 
empty, the upward divide-and-conquer triangulation is 
triggered; otherwise, this process does not continue for ÿ, and 
the next model is selected from the “current model stack", over 
which the triggering condition for terrain fragmentation is 
reinvestigated (see Figure 4). 
When the upward divide-and-conquer triangulation is triggered, 
a new on-terrain point is found through a series of processes, 
which will be discussed in the following sections and then this 
newly found on-terrain point is stored in the “on-terrain point 
stack" (see Figure 4). This process continues until all models 
stored in the “current model stack” are investigated. Then, if 
any new on-terrain point is found from the “on-terrain point 
stack”, this is added up to the on-terrain points stored in the 
“current model stack”. Using this new set of on-terrain points, 
the current terrain surface model is upgraded by the Delaunay