Z-Buffer for row addressable graphics memory with flash fill

• US 5,933,156 A
• Filed: 12/03/1997
• Issued: 08/03/1999
• Est. Priority Date: 12/03/1997
• Status: Expired due to Fees

• Current Assignee: Foothills IP LLC
• Original Assignee: Jed Margolin
• Inventors: Margolin, Jed
• Primary Examiner(s): Tung, Kee M.
• Application Number:
  US08/984,170
• Time in Patent Office: 608 Days
• Field of Search: 345/422, 345/507-509, 345/515, 345/516
• US Class Current: 345/545
• CPC Class Codes: G09G 5/393 Arrangements for updating the contents of the bit-mapped memory

Abstract

A Z-Buffer is added to a Row Addressable Graphics Memory With Flash Fill so that a Z (or Depth) value is supplied with each Start and End address. The Z value is calculated for each pixel between the Start and End address. This value is compared to the existing Z value for that pixel stored in the Z-Buffer. Values less than the existing value replace the Z value for that pixel in the Z-Buffer and allow the new pixel to be written into the display memory. The Z data are read, modified, and written back to the Z-Buffer in parallel thereby requiring a maximum of three memory cycles to operate on a line segment independent of the length of the line.

Claims

1. A Z-Buffer for a Row Addressable Graphics Memory with Flash Fill comprising:

(a) a row addressable Z Memory Array for storing a plurality of rows of a plurality of Z values, wherein each Z value is associated with a pixel stored in said Row Addressable Graphics Memory;

(b) a New Z Values unit having inputs for at least a first Z value data for a start address for a line segment and a second Z value data for an end address for said line segment, and comprising a plurality of units for calculating a new Z value for each stage in a selected row, wherein each said new Z value in said New Z Values unit is calculated substantially simultaneously, and wherein said New Z Values unit comprises for said each stage a Subtractor, a Multiplier, and an Adder to perform the equation Zn=ZSm+(n-ZSm)*dz, wherein

m is the number of said selected row,

n is the number of said stage,

Zn is the Z value at the nth stage,

ZSm is the Z value at the start of said line segment for row m,

ZEm is the Z value at the end of said line segment for said row m,

XSm is the X value at the start of said line segment for said row m,

XEm is the X value at the end of said line segment for said row m,

space="preserve" listing-type="equation">dz=(ZEm-ZSm)/(XEm-XSm);

(c) a plurality of Z Comparators for comparing each said Z value from said each stage in said selected row of said Z Memory Array with each associated said new Z value from said New Z Values unit, wherein said plurality of Z Comparators operate simultaneously;

(d) a Z Preset Register for storing a preset value for presetting said Z values in said Z Memory Array;

(e) an Address Compare Unit having inputs for said start address and said end address of said line segment to be drawn for determining for said each stage whether said stage is within the range of said start address and said end address and further determining whether each said new Z value is to replace each associated old Z value from said Z Memory Array and whether data representing a new pixel is to replace data representing an old pixel;

(f) a Z Select Unit for selecting for each of its outputs one of the following according to the output of each of the corresponding said Z Comparators, said Address Compare Unit, and also according to a control input signal;

(i) said old Z value from said Z Memory Array;

(ii) said new Z value from said New Z Values unit;

(iii) said preset value from said Z Preset Register;

(g) a Latch means for storing the data output from said Z Select Unit, wherein said data output from said Z Select Unit is to be written into said Z Memory Array.

2. A Z-Buffer for a Row Addressable Graphics Memory with Flash Fill comprising:

(a) a row addressable Z Memory Array for storing a plurality of rows of a plurality of Z values, wherein each Z value is associated with a pixel stored in said Row Addressable Graphics Memory;

(b) a New Z Values unit having inputs for at least a first Z value data for a start address for a line segment and a second Z value data for an end address for said line segment, and comprising a plurality of units for calculating a new Z value for each stage in a selected row, wherein each said new Z value in said New Z Values unit is calculated substantially simultaneously, and wherein said New Z Values unit comprises for each kth stage a Subtractor, a Multiplier, and an Adder to perform the equation Zn=ZSm+(n-ZSm)*dz, wherein

m is the number of said selected row,

n is the number of said stage,

Zn is the Z value at the nth stage,

ZSm is the Z value at the start of said line segment for row m,

ZEm is the Z value at the end of said line segment for said row m,

XSm is the X value at the start of said line segment for said row m,

XEm is the X value at the end of said line segment for said row m,

space="preserve" listing-type="equation">dz=(ZEm-ZSm)/(XEm-XSm),

and further comprises for every said stage which is not a multiple of k an Adder for adding dz to the output of the previous stage;

(c) a plurality of Z Comparators for comparing each said Z value from said each stage in said selected row of said Z Memory Array with each associated said new Z value from said New Z Values unit, wherein said plurality of Z Comparators operate simultaneously;

(d) a Z Preset Register for storing a preset value for presetting said Z values in said Z Memory Array;

(e) an Address Compare Unit having inputs for said start address and said end address of said line segment to be drawn for determining for said each stage whether said stage is within the range of said start address and said end address and further determining whether each said new Z value is to replace each associated old Z value from said Z Memory Array and whether data representing a new pixel is to replace data representing an old pixel;

(f) a Z Select Unit for selecting for each of its outputs one of the following according to the output of each of the corresponding said Z Comparators, said Address Compare Unit, and also according to a control input signal;

(i) said old Z value from said Z Memory Array;

(ii) said new Z value from said New Z Values unit;

(iii) said preset value from said Z Preset Register;

(g) a Latch means for storing the data output from said Z Select Unit, wherein said data output from said Z Select Unit is to be written into said Z Memory Array.

3. A Z-Buffer for a Row Addressable Graphics Memory with Flash Fill comprising:

(a) a row addressable Z Memory Array for storing a plurality of rows of a plurality of Z values, wherein each Z value is associated with a pixel stored in said Row Addressable Graphics Memory;

(b) a New Z Values unit having inputs for at least a first Z value data for a start address for a line segment and a second Z value data for an end address for said line segment, and comprising a plurality of units for calculating a new Z value for each stage in a selected row, wherein each said new Z value in said New Z Values unit is calculated substantially simultaneously, and wherein said New Z Values unit comprises for each kth stage a Subtractor and at least one Adder to perform the equation Zn=KZ+Wn, wherein

m is the number of said selected row,

n is the number of said stage,

Zn is the Z value at the nth stage,

ZSm is the Z value at the start of said line segment for row m,

ZEm is the Z value at the end of said line segment for said row m,

XSm is the X value at the start of said line segment for said row m,

XEm is the X value at the end of said line segment for said row m,

space="preserve" listing-type="equation">KZ=ZSm-XSm*dz,

space="preserve" listing-type="equation">dz=(ZEm-ZSm)/(XEm-XSm),

space="preserve" listing-type="equation">Wn=w0*1*dz+w1*2*dz+w2*4+dz+w3+8*dz+ . . . +wj*bj*dz,

wherein

bj is a binary power of 2 (1,2,4,8,16,32, . . . ),

wj is either 0 or 1, such that

space="preserve" listing-type="equation">w0*1 +w1*2+w2*4+w3*8+ . . . +wj*bj=n,

and further comprises for every said stage which is not a multiple of k an Adder for adding dz to the output of the previous stage;

(c) a plurality of Z Comparators for comparing each said Z value from said each stage in said selected row of said Z Memory Array with each associated said new Z value from said New Z Values unit, wherein said plurality of Z Comparators operate simultaneously;

(d) a Z Preset Register for storing a preset value for presetting said Z values in said Z Memory Array;

(e) an Address Compare Unit having inputs for said start address and said end address of said line segment to be drawn for determining for said each stage whether said stage is within the range of said start address and said end address and further determining whether each said new Z value is to replace each associated old Z value from said Z Memory Array and whether data representing a new pixel is to replace data representing an old pixel;

(f) a Z Select Unit for selecting for each of its outputs one of the following according to the output of each of the corresponding said Z Comparators, said Address Compare Unit, and also according to a control input signal;

(i) said old Z value from said Z Memory Array;

(ii) said new Z value from said New Z Values unit;

(iii) said preset value from said Z Preset Register;

(g) a Latch means for storing the data output from said Z Select Unit, wherein said data output from said Z Select Unit is to be written into said Z Memory Array.

4. A Z-Buffer for a Row Addressable Graphics Memory with Flash Fill comprising:

(a) a row addressable Z Memory Array (10);

(b) a New Z Values (11) unit;

(c) a Z Comparators (12);

(d) a Z Preset Register (15);

(e) an Address Compare Units (14);

(f) a Z Select Unit (13);

(g) a Z Latch (16);

whereby

(i) said row addressable Z Memory Array (10) stores a plurality of rows of a plurality of Z values, and each Z value is associated with a pixel stored in said Row Addressable Graphics Memory;

(ii) said New Z Values (11) unit has inputs for at least a first Z value data for a start address for a line segment and a second Z value data for an end address for said line segment and comprises a plurality of units for calculating a new Z value for each stage in a selected row, wherein each said new Z value in said New Z Values (11) unit is calculated substantially simultaneously, and wherein said New Z Values (11) unit comprises for said each stage a Subtractor, a Multiplier, and an Adder to perform the equation

space="preserve" listing-type="equation">Zn=ZSm+(n-ZSm)*dz,

wherein

m is the number of said selected row,

n is the number of said stage,

Zn is the Z value at the nth stage,

ZSm is the Z value at the start of said line segment for row m,

ZEm is the Z value at the end of said line segment for said row m,

XSm is the X value at the start of said line segment for said row m,

XEm is the X value at the end of said line segment for said row m,

space="preserve" listing-type="equation">dz=(ZEm-ZSm)/(XEm-XSm);

(iii) said Z Comparators (12) compares each said Z value from said each stage in said selected row of said Z Memory Array (10) with each associated said new Z value from said New Z Values (11) unit, wherein said each stage in said selected row of said Z Memory Array (10) is compared simultaneously with each associated said new Z value from said New Z Values (11) unit;

(iv) said Z Preset Register (15) stores a preset value for presetting said Z values in said Z Memory Array (10);

(v) said Address Compare Units (14) has inputs for said start address and said end address of said line segment to be drawn and determines for said each stage whether said stage is within the range of said start address and said end address and further determines whether each said new Z value is to replace each associated old Z value from said Z Memory Array (10) and whether data representing a new pixel is to replace data representing an old pixel;

(vi) said Z Select Unit (13) selects for each of its outputs one of the following according to the output of each of the corresponding comparators in said Z Comparators (12), said Address Compare Units (14), and also according to a control input signal;

(a) said old Z value from said Z Memory Array (10);

(b) said new Z value from said New Z Values (11) unit;

(c) said preset value from said Z Preset Register (15);

(vii) said Z Latch (16) stores the data output from said Z Select Unit (13), wherein said data output from said Z Select Unit (13) is written into said Z Memory Array (10).

5. A Z-Buffer for a Row Addressable Graphics Memory with Flash Fill comprising:

(a) a row addressable Z Memory Array (10);

(b) a New Z Values (11) unit;

(c) a Z Comparators (12);

(d) a Z Preset Register (15);

(e) an Address Compare Units (14);

(f) a Z Select Unit (13);

(g) a Z Latch (16);

whereby

(i) said row addressable Z Memory Array (10) stores a plurality of rows of a plurality of Z values, and each Z value is associated with a pixel stored in said Row Addressable Graphics Memory;

(ii) said New Z Values (11) unit has inputs for at least a first Z value data for a start address for a line segment and a second Z value data for an end address for said line segment and comprises a plurality of units for calculating a new Z value for each stage in a selected row, wherein each said new Z value in said New Z Values (11) unit is calculated substantially simultaneously, and wherein said New Z Values (11) unit comprises for each kth stage a Subtractor, a Multiplier, and an Adder to perform the equation

space="preserve" listing-type="equation">Zn=ZSm+(n-ZSm)*dz,

wherein

m is the number of said selected row,

n is the number of said stage,

Zn is the Z value at the nth stage,

ZSm is the Z value at the start of said line segment for row m,

ZEm is the Z value at the end of said line segment for said row m,

XSm is the X value at the start of said line segment for said row m,

XEm is the X value at the end of said line segment for said row m,

space="preserve" listing-type="equation">dz=(ZEm-ZSm)/(XEm-XSm),

and further comprises for every said stage which is not a multiple of k an Adder for adding dz to the output of the previous stage;

(iii) said Z Comparators (12) compares each said Z value from said each stage in said selected row of said Z Memory Array (10) with each associated said new Z value from said New Z Values (11) unit, wherein said each stage in said selected row of said Z Memory Array (10) is compared simultaneously with each associated said new Z value from said New Z Values (11) unit;

(iv) said Z Preset Register (15) stores a preset value for presetting said Z values in said Z Memory Array (10);

(v) said Address Compare Units (14) has inputs for said start address and said end address of said line segment to be drawn and determines for said each stage whether said stage is within the range of said start address and said end address and further determines whether each said new Z value is to replace each associated old Z value from said Z Memory Array (10) and whether data representing a new pixel is to replace data representing an old pixel;

(vi) said Z Select Unit (13) selects for each of its outputs one of the following according to the output of each of the corresponding comparators in said Z Comparators (12), said Address Compare Units (14), and also according to a control input signal;

(a) said old Z value from said Z Memory Array (10);

(b) said new Z value from said New Z Values (11) unit;

(c) said preset value from said Z Preset Register (15);

(vii) said Z Latch (16) stores the data output from said Z Select Unit (13), wherein said data output from said Z Select Unit (13) is written into said Z Memory Array (10).

6. A Z-Buffer for a Row Addressable Graphics Memory with Flash Fill comprising:

(a) a row addressable Z Memory Array (10);

(b) a New Z Values (11) unit;

(c) a Z Comparators (12);

(d) a Z Preset Register (15);

(e) an Address Compare Units (14);

(f) a Z Select Unit (13);

(g) a Z Latch (16);

whereby

(i) said row addressable Z Memory Array (10) stores a plurality of rows of a plurality of Z values, and each Z value is associated with a pixel stored in said Row Addressable Graphics Memory;

(ii) said New Z Values (11) unit has inputs for at least a first Z value data for a start address for a line segment and a second Z value data for an end address for said line segment and comprises a plurality of units for calculating a new Z value for each stage in a selected row, wherein each said new Z value in said New Z Values (11) unit is calculated substantially simultaneously, and wherein said New Z Values (11) unit comprises for each kth stage a Subtractor and at least one Adder to perform the equation Zn=KZ+Wn, wherein

m is the number of said selected row,

n is the number of said stage,

Zn is the Z value at the nth stage,

ZSm is the Z value at the start of said line segment for row m,

ZEm is the Z value at the end of said line segment for said row m,

XSm is the X value at the start of said line segment for said row m,

XEm is the X value at the end of said line segment for said row m,

space="preserve" listing-type="equation">KZ=ZSm-XSm*dz,

space="preserve" listing-type="equation">dz=(ZEm-ZSm)/(XEm-XSm),

space="preserve" listing-type="equation">Wn=w0*1*dz+w1*2*dz+w2*4*dz+w3*8*dz+ . . . +wj*bj*dz,

wherein

bj is a binary power of 2 (1,2,4,8,16,32, . . . ),

wj is either 0 or 1, such that

space="preserve" listing-type="equation">w0*1 +w1*2 +w2*4+w3*8+ . . . +wj*bj=n,

and further comprises for every said stage which is not a multiple of k an Adder for adding dz to the output of the previous stage;

(iii) said Z Comparators (12) compares each said Z value from said each stage in said selected row of said Z Memory Array (10) with each associated said new Z value from said New Z Values (11) unit, wherein said each stage in said selected row of said Z Memory Array (10) is compared simultaneously with each associated said new Z value from said New Z Values (11) unit;

(iv) said Z Preset Register (15) stores a preset value for presetting said Z values in said Z Memory Array (10);

(v) said Address Compare Units (14) has inputs for said start address and said end address of said line segment to be drawn and determines for said each stage whether said stage is within the range of said start address and said end address and further determines whether each said new Z value is to replace each associated old Z value from said Z Memory Array (10) and whether data representing a new pixel is to replace data representing an old pixel;

(vi) said Z Select Unit (13) selects for each of its outputs one of the following according to the output of each of the corresponding comparators in said Z Comparators (12), said Address Compare Units (14), and also according to a control input signal;

(a) said old Z value from said Z Memory Array (10);

(b) said new Z value from said New Z Values (11) unit;

(c) said preset value from said Z Preset Register (15);

(vii) said Z Latch (16) stores the data output from said Z Select Unit (13), wherein said data output from said Z Select Unit (13) is written into said Z Memory Array (10).

7. A method for integrating a Z-Buffer with a Row Addressable Graphics Memory with Flash Fill comprising the steps of:

(a) storing a plurality of rows of a plurality of Z values in a row addressable Z Memory Array, wherein each Z value is associated with a pixel stored in said Row Addressable Graphics Memory;

(b) calculating a new Z value for each stage in a New Z Values unit using at least a first Z value data for a start address for a line segment and a second Z value data for an end address for said line segment, wherein each said new Z value in said New Z Values unit is calculated substantially simultaneously;

(c) comparing each said Z value from said each stage in a selected row of said Z Memory Array with each associated said new Z value in said New Z Values unit, wherein the comparators of said each stage in said selected row operate simultaneously;

(d) storing in a Register means a preset value for presetting said Z values for said Z Memory Array;

(e) determining, in an Address Compare Unit, whether each said stage is within the range of said start address and said end address and further determining whether each said new Z value is to replace each associated old Z value from said Z Memory Array and whether data representing a new pixel is to replace data representing an old pixel;

(f) selecting for each output of a Z Select Unit one of the following according to the output of each of the corresponding said comparators, said Address Compare unit, and also according to a control input signal;

(i) said old Z value from said Z Memory Array;

(ii) said new Z value from said New Z Values unit;

(iii) said preset value from said Z Preset Register;

(g) storing the data output from said Z Select Unit in a Latch means, wherein said data output from said Z Select Unit is to be written into said Z Memory Array.

8. The method of claim 7 wherein the method for calculating said new Z value for each said stage in said New Z Values unit comprises the steps of performing the calculation Zn=ZSm+(n-ZSm)*dz, wherein

m is the number of said selected row,

n is the number of said stage,

n is the Z value at the nth stage,

ZSm is the Z value at the start of said line segment for row m,

ZEm is the Z value at the end of said line segment for said row m,

XSm is the X value at the start of said line segment for said row m,

XEm is the X value at the end of said line segment for said row m,

9. The method of claim 7 wherein the method for calculating said new Z value for each said stage in said New Z Values unit comprises the steps of

(a) for every kth stage performing the calculation

10. The method of claim 7 wherein the method for calculating said new Z value for each said stage in said New Z Values unit comprises the steps of

(a) for every kth stage performing the calculation