Memory management for systems for generating 3-dimensional computer images

• US 20080186318A1
• Filed: 02/15/2007
• Published: 08/07/2008
• Est. Priority Date: 09/29/2006
• Status: Active Grant

• Current Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Original Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Inventors: Redshaw, Jonathan, Morphet, Steve
• Granted Patent: US 8,669,987 B2
• Time in Patent Office: Days
• US Class Current: 345/537
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 2200/08 involving all processing steps from image acquisition to 3D model generation

Abstract

Memory management system and method for use with systems for generating 3-dimensional computer generated images. The system includes a) means for subdividing the image into rectangular areas, b) a memory having a first portion(s) for storing object data for each rectangular area and a second portion(s) for storing depth data derived from the object data, c) means for storing the object data in the first memory portion, d) means for deriving the depth data for each rectangular area from the object data, e) means for storing the depth data for each rectangular area in the second memory portion, f) means for loading further object data into the first memory portion to replace part of the existing contents, g) means for retrieving the stored depth data, h) means for deriving updated depth data for each picture element of each rectangular area from the new object and stored depth data, and storing the updated depth data to replace the previously stored depth data, i) means for causing features e), f), g) and h) to repeatedly perform the functions until there is no further object data to load to the memory, and j) means for deriving image data and shading data from the depth data for display.

Claims

1. 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 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) means for storing the object data in the first portion or portions of the memory;

d) means for deriving the depth data for each rectangular area, from the object data;

e) means for storing the depth data for each rectangular area in the second portion or portions of the memory;

f) means for 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) means for retrieving the stored depth data;

h) means for 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) means for causing features e), f), g) and h) to repeatedly perform the functions until there is no further object data to load to the memory; and

j) means for deriving image data and shading data from the depth data, for display.

2. A memory management system according to claim 1, wherein the first portion or portions of the memory and the second portion or portions of the memory are allocated from unused portions of the memory according to requirements, such that the size of the first and second portion or portions and the location of the first and second portion or portions, within the memory, dynamically change as the features c), d), e), f), g), h) and i) perform their functions.

3. A memory management system according to claim 1, wherein a second portion or portions are always reserved for depth data for at least one rectangular area, so that, if there is object data stored in the memory, it is always possible for features d) and e) to perform their functions.

4. A memory management system according to claim 1, wherein the means for storing the object data in the first portion or portions of the memory is arranged to store object data falling in only one rectangular area in a block of memory allocated to that rectangular area, and object data falling in more than one rectangular area in a block of memory allocated as a global list for storing object data falling in more than one rectangular area.

5. 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.

6. 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.

7. A memory management system according to claim 6, wherein the at least one portion of the memory allocated to each rectangular area and the at least one portion of memory allocated as the global list, are allocated from unused portions of the memory according to requirements, such that the size and location of the at least one portion of the memory allocated to each rectangular area and the size and location of the at least one portion of the memory allocated as the global list, dynamically change as features c), d) and e) perform their functions.

8. A memory management system according to claim 6, wherein the deriving means comprises means for deriving depth data for each rectangular area from the object data and shading means for deriving the image data and shading data from the depth data.

9. A memory management system according to claim 6, wherein the global list is arranged to store object data pertaining to objects falling in more than one rectangular area and also object data pertaining to objects falling in a single rectangular area but close to the boundary with another rectangular area.

10. A memory management system according to claim 9, wherein on either side of a boundary between rectangular areas, the number of consecutive elementary areas containing objects falling in a single rectangular area increases as the distance from the boundary increases, and the object data for objects falling between the boundary and the elementary area at which the number of consecutive elementary areas containing objects falling in a single rectangular crosses a predetermined threshold, are stored in the global list.

11. 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.

12. A method according to claim 11, wherein the at least one portion of the memory allocated to each rectangular area and the at least one portion of memory allocated as the global list, are allocated from unused portions of the memory according to requirements, such that the size and location of the at least one portion of the memory allocated to each rectangular area and the size and location of the at least one portion of the memory allocated as the global list, dynamically change as steps c), d) and e) are performed.

13. A method according to claim 11 wherein step d) of deriving the image data and shading data in the deriving means comprises deriving depth data for each rectangular area from the object data and deriving the image data and shading data from the depth data.

14. A method according to claim 11 wherein, once the image data and shading data has been derived for a particular rectangular area, the at least one portion of the memory allocated to that rectangular area is marked as free and, once the image data and shading data has been derived for all the rectangular areas, the at least one portion of the memory allocated as the global list is marked as free.

15. A memory management system according to claim 11, wherein the global list is arranged to store object data pertaining to objects falling in more than one rectangular area and object data pertaining to objects falling in a single rectangular area but close to the boundary with another rectangular area.

16. A memory management system according to claim 15, wherein on either side of a boundary between rectangular areas, the number of consecutive elementary areas containing objects falling in a single rectangular area increases as the distance from the boundary increases, and the object data for objects falling between the boundary and the elementary area at which the number of consecutive elementary areas containing objects falling in a single rectangular crosses a predetermined threshold, are stored in the global list.

17. 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.

18. 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.

19. A method according to claim 18, wherein the first portion or portions of the memory and the second portion or portions of the memory are allocated from unused portions of the memory according to requirements, such that the size of the first and second portion or portions and the location of the first and second portion or portions, within the memory, dynamically change as the steps of the method are carried out.

20. A method according to claim 18, wherein a second portion or portions are always reserved for depth data, so that, if there is object data stored in the memory, it is always possible for step d) to be performed.

21. A method according to claim 20, wherein the reserved second portion or portions is at least sufficient for depth data for each elementary area of one rectangular area to be stored.

22. A method according to claim 20, wherein the reserved second portion or portions is at least sufficient for depth data for each elementary area of two rectangular areas to be stored.

23. A method according to claim 18, wherein step c) comprises loading object data for each rectangular area MTn into the first portion or portions of the memory, object data for objects falling in only one rectangular area being stored in a respective block Pn of the first portion or portions of the memory and object data for objects falling in more than one rectangular area being stored in a block PGl of the first portion or portions of the memory.

24. A method according to claim 18 wherein if, after step c), the blocks of memory Pn are the same size for each rectangular area MTn, step d) is performed for each rectangular area before further object data can be loaded into the first portion or portions of the memory.

25. A method according to claim 18 wherein if, after step c), the blocks of memory Pn are not the same size for each rectangular area MTn, the block Pn of the first portion or portions of memory selected at step d) is the largest block Pn.

26. 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.

27. A memory management system according to claim 26, wherein the at least one memory comprises one memory for each application.

28. A memory management system according to claim 27, wherein each memory comprises a first portion or portions for storing object data for each rectangular area of the respective application and a second portion or portions for storing depth data derived from the object data of the respective application.

29. A memory management system according to claim 26, wherein the at least one memory comprises a single memory, portions of which are allocated to each application as required.

30. A memory management system according to claim 29, wherein a portion of the single memory is always reserved for depth data so that, if there is object data stored in the memory, it is always possible for features d) and e) to perform their functions.

31. A memory management system according to claim 30, wherein the reserved portion is sufficient for depth data for each elementary area of one rectangular area to be stored, irrespective of the number of applications.

32. 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.