Efficient parallel execution of the program requires the load balancing of the work among component processes [1]. Because the scene graph is an irregular and dynamic data structure, it cannot be partitioned for parallel traversing by multiple processes. In parallel programming paradigm, problems with irregular and dynamic data structure, such as the scene graph of a synthetic environment, can be solved by the partition of the program (also called partition in the control domain). The program must be divided into a number of processes, and each process must perform a sub-set of operations from the entire operations set of the program. A balanced partitioning of the image generation program can be accomplished by dividing the scene graph traversing operation into a sequence of traversing operations, each of then executing a subset of the operation set needed in each node of the graph. Every traversing operation is an execution stage of the program and is implemented as a separate process. All processes are connected in a simple directed graph, a linear array, which is known as the task dependence graph of the program. The typical stages in image generation are: update objects position in synthetic environment, culling the objects towards the viewing frustum, draw the surfaces, etc (Figure 3). The stages of the program are executed as corresponding processes on available processors of the image generator, in a pipeline mode. 
A constant frame rate is obtained if the image generation processes are triggered with a given frequency which, usually is an integer sub-multiplier of the display vertical synchronization rate, in order to allow double frame-buffer swapping during vertical retrace time. The optimal solution for program partition into stages, (each stage executed as a process), and the assigning of processes to available processors in a multiprocessor station depend on the number of processors and the relative amount of computational time required for each stage [2], [3]. Figure 4 shows a partition of image generation program into three stages, pipelined executed as three processes on the same number of processors. Successive images (denoted frames) are obtained after all stages are executed for each of them.
Each process is activated synchronously with the update frame rate but the actual process execution time is not constant and depends on the current frame. The condition for real-time execution is that the maximum execution time (worst case execution time) of processes for frame generation, to be less then the frame duration.

With a limited size of physical memory, only a limited number of virtual segments of a virtual scene can be present in memory at any given instance. Let M be the set of physical memory addresses allocated to store the input data of the program (scene graph), and V the set of virtual segments of the scene. The physical memory is dynamically allocated to different segments of the scene, depending on the relative position of the segment towards the observer position. The virtual memory management demands the implementation of the following mapping: ft:V® MÈ{Æ }
In other words, the mapping ft translates a virtual segment into a memory address, if the segment is present in the memory, and ft = Æ if the segment is not present in memory. Dynamic mapping of virtual segments to physical memory is partially similar with virtual memory mechanism included in almost all operating systems, but there are some different requirements. The first requirement is that in real-time image generation it is not acceptable a memory miss, because the absence of an object needed for rendering would produce an artifact in the generated image. Therefore, we cannot expect a memory miss interrupt in order to swap virtual segments, and we must prevent a memory miss situation by repeatedly execution of the following mapping function:

mapping_function () {
   for (i = 0; i < p; i++) {
      Compute the dist. D of the segm. Vi
       if (LSCB[i].status > 0) {
           if (D > switchOut) { 
                     /* Segment detachment */
                     Disconnect segm. Vi from the scene
                     Delete the segment Vi
                     LSCB[i].status = 0;
       else if (D < switchIn) {
           /* Segment attachment */
          Load the segment Vi
         Connect segm. Vi in the scene 
         LSCB[i].status = 1;
The program maintains a list of control blocks, for all virtual segments of the scene (the list LSCB). Every segment control block stores information needed for dynamic segment switch, which are:
  • The spatial dimension and the position in the scene of the segment;
  • The backing store file name of the segment;
 Previous Page                                                                                                                                                      Next Page