Granted Patent B2

US 12,646,217 · App. 18/203,217 · Granted Jun 2, 2026

Inventor: Simon Fenney (St. Albans, GB)

Assignee: Imagination Technologies Limited

G06T9/00G06T15/06G06T2210/21

Abstract

Claims (72)

1 . A method of compressing, into a block of compressed data, a block of sub-primitive presence indications for use in a rendering system, the method comprising:

performing spatial decorrelation on the sub-primitive presence indications in the block of sub-primitive presence indications to determine spatially decorrelated presence indications, said performing spatial decorrelation comprising:

(a) for each of a plurality of lines of presence indications in a first dimension within the block of presence indications:

for one or more of the presence indications in the line: (i) determining a predicted value for the presence indication based on one or more other presence indications in the line, and (ii) replacing the presence indication with a value of a difference between the presence indication and the determined predicted value for the presence indication; and

(b) for each of a plurality of lines of presence indications in a second dimension within the block of presence indications:

for one or more of the presence indications in the line: (i) determining a predicted value for the presence indication based on one or more other presence indications in the line, and (ii) replacing the presence indication with a value of a difference between the presence indication and the determined predicted value for the presence indication;

wherein said replacing the presence indication with a value of a difference between the presence indication and the determined predicted value for the presence indication comprises performing a difference calculation using a modulo-3 operation to determine the value of the difference between the presence indication and the determined predicted value for the presence indication;

performing entropy encoding on the spatially decorrelated presence indications to determine entropy encoded data; and

storing the entropy encoded data in the block of compressed data.

2 . The method of claim 1 , wherein said one or more presence indications in a line in the first dimension for which predicted values are determined are alternate presence indications in that line in the first dimension, and wherein said one or more presence indications in a line in the second dimension for which predicted values are determined are alternate presence indications in that line in the second dimension.

3 . The method of claim 1 , wherein said one or more other presence indications in the line on which the determination of a predicted value is based are adjacent to the presence indication for which the predicted value is determined.

4 . The method of claim 1 , wherein said plurality of lines of presence indications in a first dimension comprises all of the lines of presence indications in the first dimension within the block of presence indications, and wherein said plurality of lines of presence indications in a second dimension comprises all of the lines of presence indications in the second dimension within the block of presence indications.

5 . The method of claim 1 , wherein each of the presence indications indicates a presence state which is one of: (i) fully present, (ii) fully absent, and (iii) partially present.

6 . The method of claim 5 , wherein a partially present presence state is represented by a value of zero in the block of sub-primitive presence indications.

7 . The method of claim 5 , wherein either:

a fully present presence state is represented by a value of one and a fully absent presence state is represented by a value of two in the block of sub-primitive presence indications; or

a fully present presence state is represented by a value of two and a fully absent presence state is represented by a value of one in the block of sub-primitive presence indications.

8 . The method of claim 1 , wherein said determining a predicted value for the presence indication based on one or more other presence indications in the line is performed using a Predict function which operates in accordance with:

Predict

(

L

,

R

)

=

{

L

when

⁢

L

=

R

0

otherwise

and wherein said replacing the presence indication with a value of a difference between the presence indication and the determined predicted value for the presence indication is performed in accordance with:

p 2i+1 :=p 2i+1 −Predict( p 2i ,p 2i+2 )mod 3

wherein p 2i is the (2i) th presence indication in the line, p 2i+1 is the (2i+1) th presence indication in the line, and p 2i+2 is the (2i+2)th presence indication in the line.

9 . The method of claim 8 , wherein if p 2i+1 is the final presence indication in the line, such that p 2i+2 does not exist in the block of presence indications, then the value of p 2i is used in place of p 2i+2 in the Predict function.

10 . The method of claim 1 , wherein the lines of presence indications in the first dimension within the block of presence indications are rows of presence indications within the block of presence indications, and the lines of presence indications in the second dimension within the block of presence indications are columns of presence indications within the block of presence indications.

11 . The method of claim 1 , wherein the lines of presence indications in the first dimension within the block of presence indications are columns of presence indications within the block of presence indications, and the lines of presence indications in the second dimension within the block of presence indications are rows of presence indications within the block of presence indications.

12 . The method of claim 1 , wherein said performing spatial decorrelation further comprises, subsequent to (a) and (b):

(c) deinterleaving the presence indications in the block to thereby group the presence indications which have not been replaced into a sub-block within the block of presence indications;

(d) for each of a plurality of lines of presence indications in the first dimension within the sub-block of presence indications:

for one or more of the presence indications in the line: (i) determining a predicted value for the presence indication based on one or more other presence indications in the line, and (ii) replacing the presence indication with a value of a difference between the presence indication and the determined predicted value for the presence indication; and

(e) for each of a plurality of lines of presence indications in the second dimension within the sub-block of presence indications:

for one or more of the presence indications in the line: (i) determining a predicted value for the presence indication based on one or more other presence indications in the line, and (ii) replacing the presence indication with a value of a difference between the presence indication and the determined predicted value for the presence indication.

13 . The method of claim 1 , wherein said performing entropy encoding on the spatially decorrelated presence indications to determine entropy encoded data comprises:

for each subset of a plurality of subsets of the spatially decorrelated presence indications:

determining a number of bits which can be used to represent the maximum value of the spatially decorrelated presence indications in the subset;

including, in the entropy encoded data, an indication of said determined number of bits; and

including, in the entropy encoded data, encoded data values representing the spatially decorrelated presence indications in the subset, wherein each of the encoded data values has said determined number of bits.

14 . The method of claim 13 , wherein the determined number of bits is a minimum number of bits which can be used to losslessly represent the maximum value of the spatially decorrelated presence indications in the subset.

15 . The method of claim 13 , wherein each of the subsets of spatially decorrelated presence indications is a 2×2 subset of spatially decorrelated presence indications.

16 . The method of claim 1 , wherein said performing entropy encoding on the spatially decorrelated presence indications to determine entropy encoded data comprises performing Huffman encoding or run length encoding.

17 . The method of claim 1 , wherein the rendering system is a ray tracing system or a rasterization system.

18 . A compression unit configured to compress, into a block of compressed data, a block of sub-primitive presence indications for use in a rendering system, the compression unit comprising:

a spatial decorrelation module configured to perform spatial decorrelation on the sub-primitive presence indications in the block of sub-primitive presence indications to determine spatially decorrelated presence indications, said spatial decorrelation comprising:

(a) for each of a plurality of lines of presence indications in a first dimension within the block of presence indications:

for one or more of the presence indications in the line: (i) determining a predicted value for the presence indication based on one or more other presence indications in the line, and (ii) replacing the presence indication with a value of a difference between the presence indication and the determined predicted value for the presence indication; and

(b) for each of a plurality of lines of presence indications in a second dimension within the block of presence indications:

for one or more of the presence indications in the line: (i) determining a predicted value for the presence indication based on one or more other presence indications in the line, and (ii) replacing the presence indication with a value of a difference between the presence indication and the determined predicted value for the presence indication;

wherein said replacing the presence indication with a value of a difference between the presence indication and the determined predicted value for the presence indication comprises performing a difference calculation using a modulo-3 operation to determine the value of the difference between the presence indication and the determined predicted value for the presence indication; and

an entropy encoding module configured to perform entropy encoding on the spatially decorrelated presence indications to determine entropy encoded data and to store the entropy encoded data in the block of compressed data.

19 . A non-transitory computer readable storage medium having stored thereon a computer readable dataset description of an integrated circuit that, when processed in an integrated circuit manufacturing system, configures the integrated circuit manufacturing system to manufacture a compression unit configured to compress, into a block of compressed data, a block of sub-primitive presence indications for use in a rendering system, the compression unit being configured to:

perform spatial decorrelation on the sub-primitive presence indications in the block of sub-primitive presence indications to determine spatially decorrelated presence indications, said performing spatial decorrelation comprising:

(a) for each of a plurality of lines of presence indications in a first dimension within the block of presence indications:

for one or more of the presence indications in the line: (i) determining a predicted value for the presence indication based on one or more other presence indications in the line, and (ii) replacing the presence indication with a value of a difference between the presence indication and the determined predicted value for the presence indication; and

(b) for each of a plurality of lines of presence indications in a second dimension within the block of presence indications:

for one or more of the presence indications in the line: (i) determining a predicted value for the presence indication based on one or more other presence indications in the line, and (ii) replacing the presence indication with a value of a difference between the presence indication and the determined predicted value for the presence indication;

wherein said replacing the presence indication with a value of a difference between the presence indication and the determined predicted value for the presence indication comprises performing a difference calculation using a modulo-3 operation to determine the value of the difference between the presence indication and the determined predicted value for the presence indication;

perform entropy encoding on the spatially decorrelated presence indications to determine entropy encoded data; and

store the entropy encoded data in the block of compressed data.

Assignments (2)

Priority Claims (2)

Continuity (1)

References Cited (24)