Single-pass bounding box calculation

• US 8,217,962 B2
• Filed: 01/29/2009
• Issued: 07/10/2012
• Est. Priority Date: 01/29/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tong, Xin, Li, Chen, Li, Jinyu
• Primary Examiner(s): Wu, Xiao M.
• Assistant Examiner(s): Shin, Andrew
• Application Number:
  US12/361,676
• Publication Number:
  US 20100188404A1
• Time in Patent Office: 1,258 Days
• Field of Search: 345419-427, 345/622
• US Class Current: 345/622
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 2210/12 Bounding box

Abstract

Embodiments for single-pass bounding box calculation are disclosed. In accordance with one embodiment, the single-pass bounding box calculation includes rendering a first target to a 2-dimensional screen space, whereby the first target includes at least six pixels. The calculation further includes producing transformed vertices in a set of geometry primitives based on an application-specified transformation. The calculation also includes generating six new points for each transformed vertex in the set of geometry primitives. The calculation additionally includes producing an initial third coordinate value for each pixel by rendering the at least six new points generate for each pixel to each corresponding pixel. The calculation further includes producing a post-rasterization value for each pixel by rasterizing the at least six new points rendered to each pixel with each corresponding pixel. Finally, the calculation includes computing bounding box information for the set of geometry primitives based on the produced third coordinate values.

Claims

1. A system, comprising:

a plurality of rendering components to render one or more target images to a 2-dimensional screen space based on a set of geometry primitives, the plurality of rendering components including a vertex shader, a rasterizer, a geometry shader, and a pixel shader, the one or more target images including a first target image;

a duplicate rendering component to command the vertex shader render a second target image to the 2-dimensional screen space, the second target image including at least six pixels;

a vertex transformation component to command the vertex shader to produce transformed vertices for the set of geometry primitives of a polygon model to be projected onto the 2-dimensional screen space;

a point generation component to command the geometry shader to generate at least six new points for each of the transformed vertices of the set of geometry primitives;

a point rendering component to command the geometry shader to render the at least six new points generated for each of the transformed vertices to a corresponding pixel from the at least six pixels of the second target image, each rendering to a corresponding pixel producing an initial third coordinate value for the corresponding pixel;

a point rasterization component to command the rasterizer to rasterize the at least six new points rendered to each corresponding pixel for each corresponding pixel, each rasterization to a corresponding producing a post-rasterization third-coordinate value for the corresponding pixel;

a comparison component to store a greater value of the initial third coordinate value and the post-rasterization third coordinate value for each pixel; and

a computation component to compute the bound box information for the set of geometry primitives based on the stored greater values for the at least six pixels.

2. The system of claim 1, further comprising an interface component to provide the computed bounding box information to an application.

3. The system of claim 1, further comprising an interface component to provide the computed bounding box information to an application for at least one of geometry primitive collision detection, geometry primitive occlusion detection, or elimination of redundant rendering.

4. The system of claim 1, wherein the comparison component is to store the greater value in a z-buffer.

5. The system of claim 1, wherein the bounding box computation module is to compute the bounding box information for the set of geometry primitives by representing the greater values as r0, r1, r2, r3, r4, r5, respectively, and calculating the bounding box information as:

x_min=r₀,x_max=x_l−

r₁,y_min=r₂,y_max=y_l−

r₃,z_min=r₄, and z_max=1.0−

r₅

where x_l and y_l are constant values.

6. The system of claim 5, wherein x_l, is a width measurement of the first target image and y_l is a length measurement of the first target image, respectively.

7. The system of claim 1, further comprising an application programming interface (API) to enable one of activate or disable components in a bounding box calculator, the bounding box calculator including the duplicate rendering component, the vertex transformation component, the point rendering component, the point rasterization component, the comparison component, and the bounding box computation components.

8. The system of claim 5, wherein the set of geometry primitives include polygons.

9. A method, comprising:

rendering a target image to a 2-dimensional screen space, the first target image including at least six pixels;

producing transformed vertices in a set of geometry primitives based on an application-specified transformation;

generating at least six new points for each of the transformed vertices in the set of geometry primitives;

producing an initial third coordinate value for each pixel by rendering the at least six new points generate for each pixel to each corresponding pixel of the at least six pixels of the target image;

producing a post-rasterization value for each pixel by rasterizing the at least six new points rendered to each pixel with each corresponding pixel;

storing a greater value of the initial third coordinate value and the post-rasterization third coordinate value for each pixel; and

computing bounding box information for the set of geometry primitives based on the stored greater values for the at least six pixels.

10. The method of claim 9, further comprising providing the computed bounding box information to an application.

11. The method of claim 9, further comprising rendering one or more other target images to the 2-dimensional screen space based on the set of geometry primitives and the application-specified transformations prior to the rendering of the target image, wherein the rendering of the one or more other target images occurs in a same processing pass as the computing bounding box information.

12. The method of claim 9, wherein the storing includes storing the greater value in a z-buffer.

13. The method of claim 11, wherein the computing of the bounding box information for the set of geometry primitives includes representing the greater values as r0, r1, r2, r3, r4, r5, respectively, and calculating the bounding box information as:

x_min=r₀,x_max=x_l−

r₁,y_min=r₂,y_max=y_l−

r₃,z_min=r₄, and z_max=1.0−

r₅

where x_l and y_l are constant values.

14. The method of claim 13, wherein x_l is a width measurement of an additional target image of the one or more images and y_l is a length measurement of the additional target image, respectively.

15. The method of claim 9, wherein the set of geometry primitives include polygons.

16. A computer readable memory storing computer-executable instructions that, when executed, cause one or more processors to perform acts comprising:

rendering a target image to a 2-dimensional screen space, the first target image including at least six pixels;

producing transformed vertices in a set of geometry primitives based on an application-specified transformation;

generating at least six new points for each transformed vertex in the set of geometry primitives;

producing an initial third coordinate value for each pixel by rendering the at least six new points generate for each pixel to each corresponding pixel of the at least six pixels of the target image;

storing the initial third coordinate value for each pixel in a buffer;

producing a post-rasterization value for each pixel by rasterizing the at least six new points rendered to each pixel with each corresponding pixel;

replacing the initial third coordinate value of one or more pixels stored in the buffer if the post-rasterization third coordinate value of each of the one or more pixels is greater than its corresponding initial third coordinate value; and

computing bounding box information for the set of geometry primitives based on the third coordinate values stored in the buffer for the at least six pixels.

17. The computer readable memory of claim 16, the computer-executable instructions, when executed, further cause the one or more processors to perform acts comprising providing the computed bounding box information to an application.

18. The computer readable memory of claim 16, the computer-executable instructions, when executed, further cause the one or more processors to perform acts comprising rendering an additional target image to the 2-dimensional screen space based on the set of geometry primitives and the application-specified transformations, wherein the rendering of the additional target image occurs in a same processing pass as the computing bounding box information.

19. The computer readable memory medium of claim 18, wherein the computing of the bounding box information for the set of geometry primitives includes representing the greater values as r0, r1, r2, r3, r4, r5, respectively, and calculating the bounding box information as:

x_min=r₀,x_max=x_l−

r₁,y_min=r₂,y_max=y_l−

r₃,z_min=r₄, and z_max=1.0−

r₅

where x_l and y_l are constant values.

20. The computer readable memory of claim 19, wherein x_l is a width measurement of the additional target image and y_l is a length measurement of the additional target image, respectively.