Method and apparatus for rendering a computer generated image

• US 20100289809A1
• Filed: 05/17/2010
• Published: 11/18/2010
• Est. Priority Date: 05/18/2009
• Status: Active Grant

• Current Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Original Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Inventors: Fenney, Simon
• Granted Patent: US 8,654,146 B2
• Time in Patent Office: Days
• US Class Current: 345/581
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

A method and apparatus for rendering a computer generated image using a stencil buffer is described. The method divides an arbitrary closed polygonal contour into first and higher level primitives, where first level primitives correspond to contiguous vertices in the arbitrary closed polygonal contour and higher level primitives correspond to the end vertices of consecutive primitives of the immediately preceding primitive level. The method reduces the level of overdraw when rendering the arbitrary polygonal contour using a stencil buffer compared to other image space methods. A method of producing the primitives in an interleaved order, with second and higher level primitives being produced before the final first level primitives of the contour, is described which improves cache hit rate by reusing more vertices between primitives as they are produced.

Claims

1. A method for rendering a computer generated image using a stencil buffer, comprising:

receiving an arbitrary closed polygonal contour, the contour having N vertices;

dividing the arbitrary closed polygonal contour into primitives, each primitive being a polygon having at least 3 and at most P vertices where 2<

P<

N; and

using a stencil buffer to render the primitives to produce a computer generated image;

wherein dividing comprises;

i) selecting a vertex of the arbitrary closed polygonal contour as a first index vertex and setting the source contour as the arbitrary closed polygonal contour;

ii) outputting a primitive of Q vertices using the index vertex and (Q−

1) contiguous vertices of the source contour;

iii) forming a reduced source contour by removing from the source contour the (Q−

2) vertices between the index vertex and the end vertex of the outputted primitive;

iv) setting the end vertex of the outputted primitive as the index vertex;

v) repeating steps (ii) to (iv) until all vertices of the source contour have been included in at least one of the generated primitives;

vi) selecting a vertex of the reduced source contour as an index vertex and setting the source contour as the reduced source contour;

vii) repeating steps (ii) to (v) until either the reduced source contour is outputted as a primitive or until the reduced source contour has trivially zero area.

6. A method according to claim 1, wherein an offset is added modulo N to all the vertex indices in the arbitrary closed polygonal contour prior to dividing the contour into primitives.

7. A method according to claim 1, wherein using the stencil buffer to render the primitives further comprises comparing the winding order of each primitive to the overall winding order of the arbitrary closed polygonal contour and using only those primitives whose winding order is the same as the overall winding order in the colour and/or texture filling process.

8. A method according to claim 1, wherein a complex arbitrary polygon comprising multiple closed polygonal contours is received, the method additionally comprising separating the complex arbitrary polygon into its constituent closed polygonal contours, division into primitives then proceeding on each constituent closed polygonal contour and the resulting primitives of each constituent closed contour being concatenated before rendering using the stencil buffer.

9. A method according to claim 1, wherein substantially all primitives are triangles.

10. Apparatus for rendering a computer generated image comprising an input for receiving an arbitrary closed polygonal contour;

means for dividing the arbitrary N vertex closed polygonal contour into primitives, each primitive being a polygon having at least 3 and at most P vertices where 2<

P<

N, and outputting the primitives; and

a stencil buffer for rendering the primitives to produce a computer generated image;

wherein the means for dividing the arbitrary closed polygonal contour into primitives is configured to implement the method of claim 1.

11. Apparatus according to claim 10, wherein the means for dividing the arbitrary closed polygonal contour into primitives comprises:

vertex stack means comprising first and second portions, the first portion containing P stack entries, the vertex stack means configured to allow pushing and popping of stack data between the first and second portions;

primitive output means, coupled to the first portion of the vertex stack means and to state machine means, for outputting primitives from the data on the first portion of the vertex stack means;

state machine means, coupled to the vertex stack means, configured to manage the data on the first and second portions of the vertex stack means to provide interleaving of primitive levels in the output of the primitive output means.

2. A method for rendering a computer generated image using a stencil buffer, comprising:

receiving an arbitrary closed polygonal contour, the contour having N vertices;

dividing the arbitrary closed polygonal contour into primitives, each primitive being a polygon having at least 3 and at most P vertices where 2<

P<

N; and

using a stencil buffer to render the primitives to produce a computer generated image;

wherein dividing comprises;

(i) storing data representative of a partial contour from the closed polygonal contour;

(ii) outputting a first level primitive using the stored data, the first level primitive corresponding to contiguous vertices of the closed polygonal contour;

(iii) updating the stored data;

(iv) whilst the stored data represents higher level primitives outputting a higher level primitive using the stored data, an (i+1)th higher level primitive corresponding to the end vertices of consecutive ith level primitives, and updating the stored data;

(v) whilst the stored data represents a further first level primitive outputting the further first level primitive and updating the stored data;

(vi) repeating steps (i) to (v) until the closed polygonal contour has been divided into primitives or the remaining partial contour has substantially zero area.

3. A method according to claim 2, wherein step (i) comprises storing data to represent at least Q contiguous vertices of the closed polygonal contour where Q is the number of vertices of the first level primitive to be output.

4. A method according to claim 2, wherein updating the stored data in step (iii) comprises overwriting data representative of the (Q−

2) central vertices of the first level primitive.

5. A method according to claim 2, wherein updating the stored data in step (iv) comprises overwriting data representative of the (Q−

2) central vertices of the higher level primitive.

12. Apparatus for rendering a computer generated image comprising:

an input for receiving an arbitrary closed polygonal contour;

means for dividing the arbitrary closed polygonal contour into primitives, each primitive being a polygon having at least 3 and up to P vertices, and outputting the primitives;

a stencil buffer, coupled to the means for dividing the arbitrary closed polygonal contour, for rendering the primitives to produce a computer generated image;

wherein

the means for dividing the arbitrary closed polygonal contour into primitives comprises;

vertex stack means comprising first and second portions, the first portion containing P stack entries, the vertex stack means configured to allow pushing and popping of stack data between the first and second portions;

primitive output means, coupled to the first portion of the vertex stack means and to state machine means, for outputting primitives from the data on the first portion of the vertex stack means;

state machine means, coupled to the vertex stack means, configured to manage the data on the first and second portions of the vertex stack means to provide interleaving of primitive levels in the output of the primitive output means.