Memory management for systems for generating 3-dimensional computer images

A method for managing memory in a system for generating 3-dimensional computer images, the method comprising the steps of:

• a) subdividing the image into a plurality of rectangular areas;
• b) providing a memory having, at any one time, a first portion or portions for storing object data for each rectangular area and a second portion or portions for storing depth data derived from the object data;
• c) storing the object data in the first portion or portions of the memory;
• d) deriving the depth data for each rectangular area, from the object data;
• e) storing the depth data for each rectangular area in the second portion or portions of memory;
• f) loading further object data into one or more of the first portion or portions of the memory to replace at least part of the existing contents;
• g) retrieving the stored depth data;
• h) deriving updated depth data for each picture element of each rectangular area from the new object data and the stored depth data, and storing the updated depth data to replace the previously stored depth data;
• i) repeating steps e), f), g) and h) until there is no further object data to load into the memory;
• and
• j) deriving image data and shading data from the depth data, for display.

A memory management system for use with systems for generating 3-dimensional computer images, comprising:

• a) means for subdividing the image into a plurality of rectangular areas;
• b) a memory for storing object data pertaining to objects in the image which fall in each rectangular area, the memory comprising i) at least one portion allocated to each rectangular area for storing object data pertaining to objects in the respective rectangular area and ii) at least one portion allocated as a global list for storing object data pertaining to objects falling in more than one rectangular area;
• c) means for storing the object data in the memory;
• d) deriving means for deriving image data and shading data for each rectangular area, from the object data;
• e) means for supplying object data for each rectangular area from the respective portion of the memory and, if the rectangular area contains objects also falling in at least one other rectangular area, also from the global list, to the deriving means;
• and
• f) means for storing the image data and shading data derived by the deriving means, for display.

A method for managing memory in a system for generating 3-dimensional computer images comprising the steps of:

• a) subdividing the image into a plurality of rectangular areas;
• b) storing object data pertaining to objects in the image which fall in each rectangular area in a memory by i) allocating at least one portion of the memory to each rectangular area and storing in that portion object data pertaining to objects in the respective rectangular area, and ii) allocating at least one portion of the memory as a global list and storing in the global list object data pertaining to objects falling in more than one rectangular area;
• c) supplying object data for each rectangular area from the respective portion of the memory and, if the rectangular area contains objects also falling in at least one other rectangular area, also from the global list, to deriving means for deriving image data and shading data for each rectangular area;
• d) deriving the image data and shading data in the deriving means;
• and
• e) storing the image data and shading data for display.

A memory for use with a system for generating 3-dimensional computer images, the image to be generated being divided into a plurality of rectangular areas and each rectangular area being divided into a plurality of smaller areas, the memory comprising:

• a portion for storing object data for objects falling in each rectangular area;
• a portion for pointers from each smaller area to the object data for objects falling in that smaller area;
• objects in the image to be generated being divided into triangles, the object data comprising triangle data, vertex data and pointers between the triangle data and the vertex data;
• the memory being arranged such that, when the system processes a smaller area to generate the portion of the image in that smaller area, the system is able to fetch the vertex data for that smaller area in one fetch by using the pointer from each smaller area to the triangle data for objects falling in that smaller area and the pointer between that triangle data and the vertex data.

A method for generating 3-dimensional computer images, the method comprising the steps of:

• a) subdividing the image into a plurality of rectangular areas MTn;
• b) providing a memory having, at any one time, a first portion or portions for storing object data and a second portion or portions for storing depth data, derived from the object data;
• c) loading object data for each rectangular area MTn into the first portion or portions of the memory, each rectangular area MTn using a respective block Pn of the first portion or portions of the memory, until the total size of the first portion or portions of the memory used exceeds a predetermined threshold;
• d) selecting a block Pn of the first portion or portions of the memory, deriving depth data for the respective rectangular area MTn from the object data of MTn, and storing the derived depth data for MTn in the second portion or portions of memory,
• the block Pn selected being such that, after step d) is performed, it is possible to either i) load further object data into the block Pn to replace all or part of the existing contents or ii) select a further block Pm of the first portion or portions of memory and derive depth data for the respective rectangular area MTm from the object data of MTm and store the derived depth data for MTm in the second portion or portions of memory;
• e) if i) at step d) is satisfied, repeating steps c) and d) until there is no further object data to load into the memory or, if ii) at step d) is satisfied, repeating step d) until there is no further object data to load into the memory;
• and
• f) deriving image data and shading data for each rectangular area MTn from the depth data for each rectangular area MTn stored in the second portion or portions of memory;
• and
• e) storing the image data and shading data, for display.

A memory management system for use with systems for generating 3-dimensional computer images in a plurality of applications running concurrently, the system comprising:

• a) means for subdividing the image of each application into a plurality of rectangular areas;
• b) at least one memory for storing object data and depth data derived from the object data for each rectangular area for each application;
• c) means for storing the object data of each application in the at least one memory;
• d) means for deriving the depth data for each rectangular area, from the object data, for each application;
• e) means for storing the depth data for each rectangular area for each application in the at least one memory;
• f) means for loading further object data for each application into the at least one memory, to replace the existing contents for the respective application;
• g) means for retrieving the stored depth data for each application;
• h) means for deriving updated depth data for each picture element of each rectangular area for each application from the new object data and the stored depth data for the respective application, and storing the updated depth data for each application to replace the previously stored depth data for the respective application;
• i) means for causing features e), f) g) and h) to repeatedly perform the functions until there is no further object data for any application to load to the at least one memory;
• j) means for deriving image data and shading data from the depth data, for each application, for display;
• and
• k) means for storing and updating the progress made by features c), d), e), f), g), h) and i) for each application.

A method of generating 3-dimensional computer images in a plurality of applications running concurrently, the method comprising, for each application, the steps of:

• a) subdividing the image into a plurality of rectangular areas;
• b) providing at least one memory for storing object data and depth data derived from the object data for each rectangular area;
• c) storing the object data in the at least one memory;
• d) deriving the depth data for each rectangular area, from the object data;
• e) storing the depth data for each rectangular area in the at least one memory;
• f) loading further object data for each application into the at least one memory, to replace the existing contents;
• g) retrieving the stored depth data;
• h) deriving updated depth data for each picture element of each rectangular area from the new object data and the stored depth data, and storing the updated depth data to replace the previously stored depth data;
• i) causing steps e), f), g) and h) to perform repeatedly until there is no further object data top load to the at least one memory;
• and
• j) deriving image data and shading data from the depth data, for display;
• wherein the steps of the method are performed by one system, for all the plurality of applications, the system sharing its time between the plurality of applications and storing and updating the progress of steps c), d), e), f), g), h) and i) for each application.