Method for sorting 3D object geometry among image chunks for rendering in a layered graphics rendering system

• US 6,326,964 B1
• Filed: 11/06/1998
• Issued: 12/04/2001
• Est. Priority Date: 08/04/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Snyder, John M., Elliott, Conal M.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US09/187,435
• Time in Patent Office: 1,124 Days
• Field of Search: 345/418, 345/419, 345/420, 345/442, 345/441, 345/427, 345/428
• US Class Current: 345/419
• CPC Class Codes: G06T 11/001 Texturing; Colouring; Generation of texture or colour inpainting G06T5/77
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 13/80 2D [Two Dimensional] animation, e.g. using sprites
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 15/60 Shadow generation

Abstract

A pre-processing method prepares 3D objects for rendering to image layers in a layered graphics rendering pipeline. The method transforms a bounding volume for an object to a 2D bounding box in a 2D view space. It then subdivides the bounding box into blocks of image samples called chunks. To computer the portion of the object that should be rendered to each chunk, it determines which geometric primitives of the object overlap each chunk and generates a list of primitives to the rendered for each chunk.

Claims

1. A method of dividing object geometry of a scene into chunks comprising:

maintaining bounding volumes for objects in the scene;

projecting the bounding boxes into a 2D view space to determine 2D bounding boxes for the objects, where the 2D bounding boxes are not aligned to screen coordinates of a display device;

sub-dividing the 2D bounding boxes into chunks, where the chunks are 2D arrays of image sample coordinates that are not aligned to screen coordinates; and

determining how the object geometry enclosed in the bounding boxes overlaps the chunks of corresponding 2D bounding volumes to produce a list of geometric primitives that overlap corresponding chunks.

2. The method of claim 1 further including:

maintaining scene graphs for each of the objects, each scene graph including object geometry and attribute values;

maintaining a attribute state structure for each chunk; and

processing the object geometry in each of the scene graphs to assign attribute states to the attribute state structure for each chunk for geometric primitives that overlap each chunk.

3. A computer readable medium having instructions for dividing object geometry of a scene into chunks by performing the following:

maintaining bounding volumes for objects in the scene;

projecting the bounding boxes into a 2D view space to determine 2D bounding boxes for the objects, where the 2D bounding boxes are not aligned to screen coordinates of a display device;

sub-dividing the 2D bounding boxes into chunks, where the chunks are 2D arrays of image sample coordinates that are not aligned to screen coordinates; and

determining how the object geometry enclosed in the bounding boxes overlaps the chunks of corresponding 2D bounding volumes to produce a list of geometric primitives that overlap corresponding chunks.

4. A method of dividing object geometry of a scene into chunks comprising:

projecting object geometry to a 2D view space;

progressively subdividing the 2D view space into m by n chunk sub-regions, where m and n are integers;

for each subdivision, culling object geometry not overlapping a subregion so that only geometry that overlaps the subregion is maintained for each subregion; and

continuing the subdivision until the view space is subdivided into chunk-sized subregions of the 2D view space and generating sets of geometric primitives overlapping each chunk.

5. A computer readable medium having instructions for performing the following:

projecting object geometry to a 2D view space;

progressively subdividing the 2D view space into m by n chunk sub-regions, where m and n are integers;

for each subdivision, culling object geometry not overlapping a subregion so that only geometry that overlaps the subregion is maintained for each subregion; and

continuing the subdivision until the view space is subdivided into chunk-sized subregions of the 2D view space and generating sets of geometric primitives overlapping each chunk.