Memory management for systems for generating 3-dimensional computer images

Abstract

A 3-dimensional computer generated image is generated by subdividing the image into a plurality of rectangular areas. Object data for each rectangular area is loaded into a display list memory ( 4 ) until that memory is substantially full. Image data and shading data for each picture element of each rectangular area is derived by an image synthesis processor ( 6 ) from the object data. Image data is then stored in a local memory ( 16 ) and further object data loaded into the display list memory ( 4 ) and replaces the existing contents. Once this has happened, the stored image data and shading data is retrieved and additional image data and shading data derived for each picture element by the image synthesis processor ( 6 ) using the new object data and the previously derived image and shading data. When there is no further object data to load to the display list memory the shading data is provided for display for the rectangular areas by a frame buffer 11. The memory may be managed by allocating at least one block of storage from the display list memory to each rectangular area and then storing in that block of memory, data which pertains to surfaces which intersect that rectangular area. A determination is made as to when a predetermined number of blocks have been used for a rectangular area. When this number is reached, the system starts to derive shading data for the rectangular areas, thereby releasing blocks of storage to be allocated to further rectangular areas in the display list memory.

1 . A method for generating 3-dimensional computer images comprising the steps of: 
 a) subdividing the image into a plurality of rectangular areas;    b) loading object data for each rectangular area into a display list memory until that memory is substantially full;    c) deriving image data and shading data for each picture element of each rectangular area from the object data;    d) storing the image data and the shading data;    e) loading further object data into the display is list memory to replace the existing contents;    f) retrieving the stored image data and shading data;    g) deriving additional image data and shading data for each picture element of each rectangular area from the new object data and the previously derived image data and shading data;    h) repeating steps d), e), f) and g) until there is no further object data to load to the display list memory; and    I) providing the shading data for display.    
     
     
         2 . A method according to  claim 1  in which the image data comprises object identification data and depth data.  
     
     
         3 . A method according to  claim 1  or  2  including the steps of compressing the image data prior to step d) and decompressing the compressed image data prior to step g).  
     
     
         4 . Apparatus for generating 3-dimensional computer images comprising: 
 a) means for subdividing the image into a plurality of rectangular areas;    b) means for loading object data for each rectangular area into a display list memory until the memory is substantially full;    c) means for deriving image data and shading data for each picture element of each rectangular area from the object data;    d) mans for storing the image data and shading data for each rectangular areas    e) means for loading further object data into the display list memory to reduce the existing contents;    f) means for retrieving the stored image data and shading data;    g) means for deriving further image data shading data for each picture element of each rectangular area from the new object data and the stored image data and shading data;    h) means for causing features d), e), f) and g) to repeatedly perform the functions until there is no further object data to load to the display list memory, and    I) providing the shading data for display.    
     
     
         5 . Apparatus according to  claim 4  in which the image data comprises object identification and depth data.  
     
     
         6 . Apparatus according to  claim 4  or  5  including mans to compress the image data before it is stored and means to decompress the compressed image data after it is retrieved.  
     
     
         7 . A memory management system for use with systems for generating 3-dimensional computer images comprising means for subdividing the image data into a plurality of substantially rectangular areas, means for storing data pertaining to surfaces making up the image in a display list memory, means for allocating at least one block of storage from the display list memory to each rectangular area and means for storing in that block of memory data pertaining to surfaces which intersect that rectangular area, means for supplying data for each rectangular area from the display list to a means for deriving shading data for each picture element of the rectangular area, and frame store means for storing the shading data for display characterised in that each rectangular area comprises a plurality of smaller rectangular areas and the means for deriving shading data derives the data for each smaller rectangular area in turn.  
     
     
         8 . A memory management system according to  claim 7  in which the means for allocating blocks of storage from the display list determines when a predetermined number of blocks have been used and, in dependence on the determination, causes the means for supplying data to the means for deriving shading data to commence operation, thereby releasing blocks of storage for further object data.  
     
     
         9 . A memory management system according to claims  7  or  8  in which the image data comprises a sequence of frames of data.  
     
     
         10 . A method for managing memory for a system for generating 3-dimensional computer images comprising the steps of subdividing the image into a plurality of rectangular areas, storing data pertaining to surfaces in the image which intersect each rectangular area in a display list memory, allocating at least one block of the display list memory to each rectangular area, storing in that block data pertaining to surfaces intersecting the respective rectangular area, supplying data for each rectangular area to a shading means whereby shading data is derived from each picture element making up the rectangular area, and storing the shading data for display characterised in that the step of subdividing the image further comprises subdividing each rectangular area into a plurality of smaller rectangular areas and the shading means shades each smaller rectangular area in turn.  
     
     
         11 . A method for managing memory according to  claim 10  including the step of determining when a predetermined number of blocks of the display list memory have been allocated to rectangular areas, and commences the supply of data to the shading means in dependence on the determination, thereby releasing blocks of storage for further object data.  
     
     
         12 . A memory management system for use with systems for generating 3-dimensional computer images comprising means for subdividing the image data into a plurality of substantially rectangular areas, means for storing data pertaining to surfaces making up the image in a display list memory, means for allocating at least one block of storage from the display list memory to each rectangular area, means for storing in that block of memory data pertaining to surfaces which intersect that rectangular area, means for supplying data for each rectangular area from the display list to a means for deriving shading data for each picture element of the rectangular area, and frame store means for storing the shading data for display, characterised in that the means for allocating blocks of storage from the display list memory determines when a predetermined number of blocks have been used and, in dependence on the determination, causes the means for supplying data to the means for deriving shading data to commence operation, thereby releasing blocks of storage for further rectangular areas.  
     
     
         13 . A method for managing memory for a system for generating 3-dimensional computer images comprising the steps of subdividing the image into a plurality of rectangular areas, storing data pertaining to surfaces in the image which intersect each rectangular area in a display list memory, allocating at least one block of the display list memory to each rectangular area, storing in that block data pertaining to surfaces intersecting the respective rectangular area, supplying data for each rectangular area to a shading means whereby shading data is derived from each picture element making up the rectangular area, and storing the shading data for display, characterised by the step of determining when a predetermined number of blocks of the display list memory have been allocated to rectangular areas, and commencing the step of supplying data to the shading means in dependence on the determination, thereby releasing blocks of storage for further object data.  
     
     
         14 . A memory management system for use with systems for shading 3-dimensional computer generated images substantially as herein described.  
     
     
         15 . A method for managing memory for a system for shading 3-dimensional computer generated images substantially as herein described.