between the observer and the midpoint of the legion, which can 
be obtained easily during frustum-culling test, is used by LOD 
management mechanism to prevent duplication. Occlusion 
culling could also be useful. Some topographic features like 
high hills or deep valleys may block objects behind or inside 
them. We have not implemented this control yet. It is also 
another future work for this study. 
2.2.2 Moving Over Terrain: Rendering of bipeds or 
quadrupeds that are moving on non-flat surfaces is a 
challenging issue. On rough terrain segments where slope is 
high, feet of virtual characters may seem to sink or rise unless 
exact actions of the alive are modeled. This problem is 
inevitable when key-framed animations prepared for flat 
surfaces are used as in our case. Shifting few centimeters above 
from ground level considering the degree of slope may decrease 
the effect of this problem since V-eye cannot easily perceive 
little rise from ground. Sink/rise problem is tolerable when the 
degree of slope is small even if no precautions are taken. 
sum 
   
  
    
Os \ 
few centimeters 
m 
a P 
  
  
Figure 4. Sink/rise problem 
In order to model actions such as walking, it is necessary to 
calculate the actual three-dimensional position of each foot. The 
exact height of a point on terrain model can be calculated by 
using plane geometry. Choosing triangles as a primitive to 
construct terrain model simplifies the calculation of height of 
the point on terrain. Below is the method that can be used to get 
height of a point on terrain model when horizontal coordinate 
pair is provided. 
e Find the triangle on which the point lies. 
e Get vertex coordinates of the triangle. 
e Calculate the normal vector of the triangle by using 
the Equation 1. 
e Calculate the plane-shift constant value of the triangle 
by using the Equation 2. 
e (Calculate the height value by using the Equation 3. 
NUE UF) (1) 
Ds NV, NEN, Q) 
P eQN.P CNAP ODUN, (3) 
where N-normal vector of the plane 
Vi, V5. V3=vertices of the triangle in vector form 
D=plane-shift constant 
Py, Py, P,=3D coordinates of the point 
     
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
In order to decrease the computational cost we calculated the 
normal vectors and plane-shift constants of every triangle of the 
terrain model and kept these pre-calculated values in memory. 
During an animation it is also necessary to calculate the new 
position of the virtual character in every frame. We used 
Equation 4 to calculate step distance for every animation frame. 
For faster operation pre-calculated slope values of the triangles 
should be better kept in computer memory. Equation 5 is used 
for getting new horizontal position of the virtual character, 
Finally by using Equation 3 vertical coordinate can be 
extracted. This operation is conducted only for objects inside 
viewing frustum. 
  
; 1000 AS 
SD = .cos a (4) 
3600 FR 
n 0 
P. =P, +8SD cosf £ 
n 0 C 
P; ZZ Pr SD sin fj 
where a=slope angle 
SD= step distance 
AS=average speed in km/hour 
FR=frame rate in 1 second 
B=heading angle 
P^, P?-new and old position. 
2.2.3 Behavior Simulation: Simulation of crowd 
behaviors is a popular research area since more and more 
crowded scenes are being included in real-time animation 
applications. Autonomous agents in VE increase the level of 
realism. When we examine the conceptual and technical 
requirements of multi-agent systems we can see that we are 
facing a task that is not straightforward. First of all variety of 
individual agents’ visualizations and behaviors such as variety 
of individual trajectories for the group traveling along the same 
path, variety of the animations for agents having same behavior 
or different reactions of individuals facing the same situations is 
needed. This prevents monotony of the scenes that include same 
individuals with the same behaviors. Multi agent models require 
more computational sources, which linearly (agent-environment 
interaction) or quadratically (agent-agent interaction) increase 
with the number of simulated agents (Ulincy & Thallman, 
2001). In our study we did not focus on the AI of virtual crowds 
since our primary aim is achieving high frame rates at crowded 
scenes. Collision has avoided by assigning same average speed 
and direction to each group. Virtual characters are arranged to 
have the same motion type: walk, idle, wait etc. The user can 
also externally guide the total crowd or sub groups by changing 
motion type, direction and average speed. Our implementation 
is crowd animation rather than crowd simulation. 
2.2.4 Sample Scene: We generated a VE to measure the 
rendering performance of the study. In this VE 10.000 animated 
soldiers walk in groups of 100 legions over non-flat terrain 
model which consists of 524288 triangles. Each soldier model 
is made up of 700-1000 triangles. Test PC configurations and 
rendering results are given in Table 1 and Table 2 respectively. 
Number of soldiers in the viewing frustum is rounded. 
  
  
     
   
   
    
   
   
   
   
       
   
   
    
     
   
   
   
    
    
     
    
    
   
   
   
   
   
   
   
    
   
   
    
     
  
  
  
    
   
   
   
  
    
  
  
oe 
  
Le 
Sy 
th