Methods and systems for generating 3-dimensional computer images

• US 20090066694A1
• Filed: 11/21/2007
• Published: 03/12/2009
• Est. Priority Date: 09/12/2007
• Status: Active Grant

• Current Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Original Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Inventors: Redshaw, Jonathan, Yang, Xile
• Granted Patent: US 8,723,860 B2
• Time in Patent Office: Days
• US Class Current: 345/423
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

There are provided methods and apparatus for generating a 3-dimensional computer image. The image comprises a number of objects and is divided into separate areas. In a first aspect, control data to link to object data stored in a memory for each object is derived for two objects at a time. This improves processing and memory usage. In a second aspect, two or more separate areas can be processed in parallel by deriving control data for the two separate areas at a time. This improves processing time. To avoid fetching data for both areas, that is actually only applicable to one area, encoding is used in the control data. In a third aspect, object data can be stored on one or across two memory pages, and the control data includes one memory page address in the former case and two memory page addresses in the latter case. This improves memory usage. In a fourth aspect, object data can be stored across two non-contiguous memory pages, by using a look-up table with contiguous portions allocated for each object'"'"'s object data. This also improves memory usage. In a fifth aspect, when partial rendering is used, and partial depth data is stored and subsequently updated, the depth data can be stored across two memory pages using link portions in the memory pages to either indicate the end of data storage or point to the next memory page. This also improves memory usage.

Claims

1. A method for generating a 3-dimensional computer image, the image to be generated comprising a plurality of objects, each object comprising at least one shape, the method comprising the steps of:

a) subdividing the image into a plurality of rectangular areas and each rectangular area into a plurality of smaller areas;

b) for at least some of the objects in the image, storing object data in a memory, the object data comprising surface data and vertex data for each shape in the object, and pointers between the surface data and the vertex data;

c) for each smaller area in the image, deriving control data to link to the object data for each object in the smaller area by;

i) extracting object data for two or more objects from the object data stored at step b);

ii) computing which of the smaller areas in the image include one or all of the objects for which object data has been extracted at step i);

iii) for each of the smaller areas computed at step ii), deriving a set of control data, the set of control data linking to object data for the or each of the objects included in the smaller area;

iv) repeating steps i) to iii) until control data for all objects at b) has been derived;

d) deriving depth data for each rectangular area from the control data and the object data; and

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

2. A method according to claim 1, wherein, at the final memory location for each set of control data derived at step iii), a pointer is provided to the next set of control data for the smaller area and the final memory location is stored in a cache.

3. A method according to claim 1, wherein step b) comprises storing object data in a memory for every object in the image.

4. A method according to claim 1, wherein step b) comprises storing object data in a memory for a predetermined number of objects in the image and the method further comprises, before step e), repeating steps b), c) and d) until object data has been stored for all the objects in the image.

5. A method according to claim 1, wherein step i) comprises extracting object data for two objects from the object data stored at step b).

6. Apparatus for generating a 3-dimensional computer image, the image to be generated comprising a plurality of objects, each object comprising at least one shape, the apparatus comprising:

a) means for subdividing the image into a plurality of rectangular areas and each rectangular area into a plurality of smaller areas;

b) means for storing object data in a memory, for at least some of the objects in the image, the object data comprising surface data and vertex data for each shape in the object, and pointers between the surface data and the vertex data;

c) deriving means for deriving control data, for each smaller area in the image, the control data linking to the object data for each object in the smaller area, the deriving means being arranged to;

i) extract object data for two or more objects from the object data stored by the means for storing,

ii) compute which of the smaller areas in the image include one or all of the objects for which object data has been extracted,

iii) for each of the smaller areas computed at ii), derive a set of control data, the set of control data linking to object data for the or each of the objects included in the smaller area, and

iv) repeat i) to iii) until control data for all objects at b) has been derived;

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

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

7. A method for generating a 3-dimensional computer image, the image to be generated comprising a plurality of objects, the method comprising the steps of:

a) subdividing the image into a plurality of separate areas;

b) for at least some of the objects in the image, storing object data in a memory;

c) for two separate areas at a time, deriving control data to link to the object data in the two separate areas;

d) generating the 3-dimensional computer image in the two separate areas by, in parallel;

i) deriving depth data for the first separate area from the control data and the object data, and deriving image data and shading data for the first separate area from the depth data for display; and

ii) deriving depth data for the second separate area from the control data and the object data, and deriving image data and shading data for the second separate area from the depth data for display; and

e) repeating steps c) and d) until an image has been generated for all the separate areas.

8. A method according to claim 7, wherein each object includes a plurality of shapes having a plurality of vertices, and the control data derived at step c) includes, for each object, an indication of which shapes of the object fall in which of the separate areas and an indication of which vertices of the object fall in which of the separate areas.

9. A method according to claim 8, wherein the control data comprises a header portion and a payload portion.

10. A method according to claim 9, wherein the header portion comprises the indication of which vertices of the object fall in which of the separate areas.

11. A method according to claim 9, wherein, if some of the shapes of the object fall in each of the separate areas, or all of the shapes of the object fall in only one of the separate areas, the payload comprises the indication of which shapes of the object fall in which of the separate areas.

12. Apparatus for generating a 3-dimensional computer image, the image to be generated comprising a plurality of objects, the apparatus comprising:

a) means for subdividing the image into a plurality of separate areas;

b) means for storing object data in a memory, for at least some of the objects in the image;

c) deriving means for deriving, for two separate areas at a time, control data to link to the object data in the two separate areas; and

d) an image generator for generating a 3-dimensional computer image in the two separate areas, the image generator comprising a first image generator in parallel with a second image generator, the first image generator being arranged to derive depth data for the first separate area from the control data and the object data, and derive image data and shading data for the first separate area from the depth data for display, the second image enerator being arranged to derive depth data for the second separate area from the control data and the object data, and derive image data and shading data for the second separate area from the depth data for display.

13. A method for generating a 3-dimensional computer image, the image to be generated comprising a plurality of objects, the method comprising the steps of:

a) subdividing the image into a plurality of separate areas;

b) for at least some of the objects in the image, a first engine storing object data in a memory, the memory being divided into memory pages;

c) for each object for which object data has been stored at b), if the object data is stored on one memory page, the first engine sending that memory page address to a second engine or, if the object data is stored on two memory pages, the first engine sending those memory page addresses to the second engine;

d) for each separate area in the image, the second engine deriving control data to link to the object data for each object in the smaller area, the control data including the one memory page address if the object data stored at b) is stored on one memory page, and including the two memory page addresses if the object data stored at b) is stored on two memory pages;

e) deriving depth data for each separate area from the control data and the object data; and

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

14. A method according to claim 13, further comprising the step of:

a memory manager allocating pages of the memory to the objects in the image.

15. A method according to claim 14, wherein the memory manager automatically allocates two pages of memory to each object.

16. A method according to claim 13, wherein step e) of deriving depth data comprises determining whether the control data linking to object data for each object in the separate area includes one or two memory page addresses.

17. Apparatus for generating a 3-dimensional computer image, the image to be generated comprising a plurality of objects, the apparatus comprising:

a) means for subdividing the image into a plurality of separate areas;

b) a first engine for storing object data in a memory for at least some of the objects in the image;

c) a second engine for deriving control data to link to the object data for each object in the separate area;

d) means for deriving depth data for each separate area from the control data and the object data; and

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

wherein

the memory is divided into memory pages,

the first engine is arranged, for each object for which object data has been stored, i) if the object data is stored on one memory page, to send that memory page address to the second engine or, ii) if the object data is stored on two memory pages, to send those memory page addresses to the second engine, and

the control data includes the one memory page address if the object data stored by the first engine is stored on one memory page, or includes the two memory page addresses if the object data stored by the first engine is stored on two memory pages.

18. Apparatus according to claim 17, further comprising a memory manager for allocating pages of the memory to the objects in the image.

19. Apparatus according to claim 17, wherein the memory manager is arranged to automatically allocates two pages of memory to each object.

20. Apparatus according to claim 17, wherein means for deriving depth data is arranged to determine whether the control data linking to object data for each object in the separate area includes one or two memory page addresses.

21. A method for generating a 3-dimensional computer image, the image to be generated comprising a plurality of objects, the method comprising the steps of:

a) subdividing the image into a plurality of separate areas;

b) providing a memory divided into memory pages and comprising a look-up table;

c) a memory manager allocating two or more contiguous portions in the look-up table to each separate area, each allocated portion in the look-up table pointing to a memory page available for storing object data for that separate area;

d) for at least some of the objects in the image, a first engine storing object data, for each separate area, in the memory pages allocated at step c) to that separate area;

e) for each separate area, the first engine sending to a second engine, memory addresses of the two or more allocated portions in the look-up table;

f) for each separate area in the image, the second engine using the memory addresses sent from the first engine, to derive control data to link to the object data for each object in the smaller area;

g) for each separate area in the image, using the memory addresses sent from the first engine to derive depth data from the control data and the object data; and

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

22. Apparatus for generating a 3-dimensional computer image, the image to be generated comprising a plurality of objects, the apparatus comprising:

a) means for subdividing the image into a plurality of separate areas;

b) a memory divided into memory pages and comprising a look-up table;

c) a memory manager for allocating two or more contiguous portions in the look-up table to each separate area, each allocated portion in the look-up table pointing to a memory page available for storing object data for that separate area;

d) a first engine arranged to store object data, for at least some of the objects in the image, for each separate area, in the memory pages allocated by the memory manager to that separate area;

e) a second engine arranged to receive from the first engine, memory addresses for each separate area, of the two or more allocated portions in the look-up table and arranged to use the memory addresses to derive control data to link to the object data for each object in the separate area;

g) means for using the memory addresses to derive depth data from the control data and the object data for each separate area in the image; and

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

23. A method for generating a 3-dimensional computer image, the image to be generated comprising a plurality of objects, the method comprising the steps of:

a) subdividing the image into a plurality of separate areas;

b) for at least some of the objects in the image, storing object data in a first memory;

c) deriving depth data for each separate area, from the object data;

d) providing a second memory for storing the depth data, the second memory comprising a plurality of memory pages, each memory page including a portion allocated as a link portion;

e) storing the depth data for each separate area in the second memory, wherein, if the depth data for a separate area is stored on one memory page, indicating as such in the link portion of that memory page, or, if the depth data for a separate area is stored on more than one memory page, using the link portion of each memory page for that separate area to point to the next memory page for that separate area;

f) loading further object data into the first memory to replace at least part of the existing contents;

g) retrieving the stored depth data for each separate area, by reading the link portion of the or each memory page for that separate area;

h) deriving updated depth data 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.

24. Apparatus for generating a 3-dimensional computer image, the image to be generated comprising a plurality of objects, the apparatus comprising:

a) means for subdividing the image into a plurality of separate areas;

b) a first memory for storing object data for at least some of the objects in the image;

c) means for deriving depth data for each separate area, from the object data;

d) a second memory for storing the depth data, the second memory comprising a plurality of memory pages, each memory page including a portion allocated as a link portion;

e) means for storing the depth data for each separate area in the second memory, wherein, if the depth data for a separate area is stored on one memory page, indicating as such in the link portion of that memory page or, if the depth data for a separate area is stored on more than one memory page, using the link portion of each memory page for that separate area to point to the next memory page for that separate area;

f) means for loading further object data into the first memory to replace at least part of the existing contents;

g) means for retrieving the stored depth data for each separate area, by reading the link portion of the or each memory page for that separate area;

h) means for deriving updated depth data from the new object data and the stored depth data, and storing the updated depth data to replace the previously stored depth data; and

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