Virtual coordinate to linear physical memory address converter for computer graphics system

• US 5,745,739 A
• Filed: 02/08/1996
• Issued: 04/28/1998
• Est. Priority Date: 02/08/1996
• Status: Expired due to Term

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Chia, Wei-Kuo, Wang, Erh-Chiao, Cheng, Chun-Yang
• Primary Examiner(s): Tung, Kee M.
• Application Number:
  US08/598,522
• Time in Patent Office: 810 Days
• Field of Search: 395/501, 395/507, 395/513, 395/515, 395/516, 395/525, 395/412, 395/413, 345/200, 345/191, 345/189, 345/185
• US Class Current: 345/569
• CPC Class Codes: G06F 12/0207 with multidimensional access, e.g. row/column, matrix
• CPC Class Codes: G09G 5/393 Arrangements for updating the contents of the bit-mapped memory

Abstract

An address generator is disclosed for performing 2-D virtual coordinate to linear physical memory address conversion. The address generator has an edge walking circuit which receives a 2-D virtual coordinate of a first pixel on a first edge of an object displayed on the display screen. The edge walking circuit selectively outputs a 2-D virtual coordinate of a second pixel which intercepts the first edge of the object at an adjacent pixel row or column to the first pixel. The address generator also has a span expansion circuit which receives the 2-D virtual coordinate of the second pixel. The span expansion circuit selectively expands the 2-D virtual coordinate of the second pixel, according to the number of bits used to represent each pixel and the amount of information which can be accessed at a time from memory. This produces first and second expanded coordinates of the second pixel. Furthermore, the address generator has a linear address circuit which receives the first and second expanded coordinates of the second pixel. The linear address circuit outputs a linear physical address of the second pixel in memory.

Claims

1. An address generator for converting a two dimensional virtual coordinate, on a display screen of a display device, of a pixel to a linear physical address, in a memory, comprising:

an edge walking circuit, receiving a two-dimensional virtual coordinate of a first pixel on a first edge of an object displayed on said display screen, and selectively outputting a two dimensional virtual coordinate of a second pixel which intercepts said first edge of said object at an adjacent row to that of said first pixel,

a span expansion circuit, receiving said two-dimensional virtual coordinate of said second pixel, and selectively expanding said two-dimensional virtual coordinate of said second pixel, according to the number of bits used to represent each pixel and the amount of information which can be accessed at a time from said memory, to produce first and second expanded coordinates of said second pixel, and

a linear address circuit, receiving said first and second expanded coordinates of said second pixel and outputting a linear physical address of said second pixel in a memory,

wherein pixels displayed on said screen are sequentially stored in said memory at linear addresses beginning with the lowest two-dimensional virtual coordinate of said display screen and ending with the highest two-dimensional virtual coordinate of said display screen.

2. The address generator of claim 1 wherein said edge walking circuit comprises:

a first adder circuit for adding a first slope component of said first edge to a first one of said two-dimensional virtual coordinates of said first pixel,

a second adder circuit for adding a second slope component of said first edge to a second one of said two-dimensional virtual coordinates of said first pixel,

a first multiplexer, for selecting as a first one of said two-dimensional virtual coordinates of said second pixel either said first coordinate of said first pixel or a sum outputted by said first adder circuit, and

a second multiplexer, for selecting as a second one of said two-dimensional virtual coordinates of said second pixel either said second coordinate of said first pixel or a sum outputted by said second adder circuit.

3. The address generator of claim 2 wherein said edge walking circuit further comprises:

a first plurality of registers for storing said first coordinate of said second pixel outputted by said first multiplexer,

a second plurality of registers for storing said second coordinate of said second pixel outputted by said second multiplexer,

a third multiplexer for selecting said first coordinate stored in one of said first plurality of registers for output from said edge walking circuit, and

a fourth multiplexer for selecting said second coordinate stored in one of said second plurality of registers for output from said edge walking circuit.

4. The address generator of claim 2 wherein span expansion circuit comprises:

a swapping circuit, receiving said first and second coordinates of said second pixel from said edge walking circuit and a control signal, for swapping said first and second coordinates depending on said control signal,

a first multiplier for multiplying a first factor, which depends on said number of bits used to represent each pixel, with either said first coordinate or said second coordinate, depending on said swapping of said swapping circuit, to produce a first product,

a second multiplier for multiplying said first factor with either said second coordinate or said first coordinate, depending on said swapping of said swapping circuit, to produce a second product as a second expanded coordinate,

a third adder circuit for adding a second factor, which depends on said amount of information which can be accessed at a time from said memory, to said first product, and

fifth multiplexer for selecting, as a first expanded coordinate, either said first product or the output of said third adder.

5. The address generator of claim 4 wherein said span expansion circuit further comprises:

a third plurality of registers, for storing the output of said fifth multiplexer,

a fourth plurality of registers, for storing said second product,

a sixth multiplexer, for selecting the value stored in one of said third plurality of registers for output from said span expansion circuit, and

a seventh multiplexer, for selecting the value stored in one of said fourth plurality of registers for output from said span expansion circuit.

6. The address generator of claim 4 wherein said linear address circuit comprises:

a calculator circuit for multiplying said second expanded coordinate by the number of pixels in a particular direction between opposing edges of said display screen to produce a third product and adding to said third product said first expanded coordinate and a base address to produce said linear physical address of said second pixel.

7. A method for drawing a line on a display screen given the starting point and ending point two-dimensional virtual coordinates of said line on said display screen comprising the steps of:

(a) storing first and second coordinate values as first and second coordinates of said two-dimensional virtual coordinate of said starting point of said line to be drawn on a display screen in first and second registers, respectively, of an edge walking circuit,

(b) using a linear address circuit, determining a linear address of said starting point of said line in a physical memory from said first and second coordinates,

(c) until an ending point of said line is reached;

(c)(1) until a last point that intercepts said line, having said second coordinate value stored in said second register as said second coordinate, is reached;

(c)(1)(i) using a first adder, adding said first coordinate to a first slope component to produce a modified first coordinate,

(c)(1)(ii) storing said modified first coordinate in said first register, and

(c)(1)(iii) using a linear address circuit, determining a linear address of said modified first coordinate and said second coordinate in a physical memory,

(c)(2) using a second adder, adding said second coordinate to a second slope component to produce a modified second coordinate, and

(c)(3) storing said modified second coordinate in said second register,

wherein pixels displayed on said screen are sequentially stored in said memory at linear addresses beginning with the lowest two-dimensional virtual coordinate of said display screen and ending with the highest two-dimensional virtual coordinate of said display screen.

8. A method for moving a source rectangle of pixels to a destination rectangle of pixels comprising the steps of:

(a) storing in first and second registers of a span expansion circuit, first and second values which depend on an amount of data used to represent each pixel and first and second virtual coordinates of a starting point of a near edge of source rectangle on a display screen,

(b) until a far edge, opposite to said near edge of said source rectangle is reached;

(b)(1) using said first and second values stored in said first and second registers, determining a linear address in a memory,

(b)(2) reading out the bits of at least one pixel from said linear address in said memory,

(b)(3) using an adder of said span expansion circuit, adding the amount of data read out by said step (b)(2) to said first value and storing the output of said adder as said first value in said first register,

(c) if the endpoint of the source rectangle is not reached, storing in said second register, a value which depends on the second virtual coordinate of the point adjacent to said source rectangle starting point on said near edge of said source rectangle,

wherein pixels displayed on said screen are sequentially stored in said memory at linear addresses beginning with the lowest two-dimensional virtual coordinate of said display screen and ending with the highest two-dimensional virtual coordinate of said display screen.

9. The method of claim 8 further comprising the steps of:

performing a block transfer to read out a predefined amount of data for more than one pixel if the amount of data of said pixels between the pixel corresponding to said linear address, and a pixel on said far edge to be read out is less than said predefined amount of data, and

otherwise, reading out a second predefined amount of data which is less than or equal to the total amount of data per pixel.

10. The method of claim 8 further comprising, alternately with said steps (a)-(c), the steps of:

(a) storing in third and fourth registers of a span expansion circuit, third and fourth values which depend on an amount of data used to represent each pixel and first and second virtual coordinates of a starting point of a near edge of a destination rectangle on a display screen,

(b) until a far edge, opposite to said near edge of said destination rectangle is reached;

(b)(1) using said third and fourth values stored in said third and fourth registers, determining a linear address in a memory,

(b)(2) reading out the bits of at least one pixel from said linear address in said memory,

(b)(3) using an adder of said span expansion circuit, adding the amount of data read out by said step (b)(2) to said third value and storing the output of said adder as said third value in said third register,

(c) if the endpoint of the destination rectangle is not reached, storing in said fourth register, a value which depends on the second virtual coordinate of the point adjacent to said destination rectangle starting point on said near edge of said destination rectangle.

11. A method for drawing triangle, which has first, second and third vertices, a first edge between said first and second vertexes, a second edge between said first and third vertices and a third edge between said third and second vertices, said method comprising the steps of:

(a) storing first and second coordinates of said first triangle vertex in first and second registers of an edge walking circuit,

(b) storing first and second values which depend on said first and second coordinates and an amount of data used to represent each pixel in first and second registers of a span expansion circuit,

(c) using a first adder of said span expansion circuit, adding a value which depends on a first slope component of said first edge, and said amount of data used to represent each pixel, to said first value to produce a first sum,

(d) storing said first sum as said first value in said first register of said span expansion circuit,

(e) using a second adder of said span expansion circuit, adding a value which depends on a second slope component of said first edge, and said amount of data used to represent each pixel, to said second value to produce a second sum,

(f) storing said second sum as said second value in said second register of said span expansion circuit,

(g) using a first adder of said edge walking circuit, adding a first slope component of said second edge to said first coordinate to produce a third sum,

(h) storing said third sum as said first coordinate in said first register of said edge walking circuit,

(i) using a second adder of said edge walking circuit, adding a second slope component of said second edge to said second coordinate to produce a fourth sum,

(j) storing said fourth sum as said second coordinate in said second register of said edge walking circuit,

(k) storing in third and fourth registers of said span expansion circuit, third and fourth values which depend on said third and fourth sums and an amount of data used to represent each pixel in first and second coordinates of a span expansion circuit,

(l) until a point on said first edge corresponding to said first and second values stored in said first and second registers of said span expansion circuit is reached;

(l)(1) using said third and fourth values stored in said third and fourth registers of said span expansion circuit, determining a linear address in a memory,

(l)(2) reading out the bits of at least one pixel from said linear address in said memory,

(l)(3) using said first adder of said span expansion circuit, adding the amount of data read out by said step (l)(2) to said third value and storing the output of said adder as said third value in said third register

wherein pixels displayed on said screen are sequentially stored in said memory at linear addresses beginning with the lowest two-dimensional virtual coordinate of said display screen and ending with the highest two-dimensional virtual coordinate of said display screen.

12. A method for converting a two dimensional virtual coordinate, on a display screen of a display device, of a pixel to a linear physical address, in a memory, comprising:

using an edge walking circuit, receiving a two-dimensional virtual coordinate of a first pixel on a first edge of an object displayed on said display screen, and selectively outputting a two dimensional virtual coordinate of a second pixel which intercepts said first edge of said object at an adjacent row to that of said first pixel,

using a span expansion circuit, receiving said two-dimensional virtual coordinate of said second pixel, and selectively expanding said two-dimensional virtual coordinate of said second pixel, according to the number of bits used to represent each pixel and the amount of information which can be accessed at a time from said memory, to produce first and second expanded coordinates of said second pixel, and

using a linear address circuit, receiving said first and second expanded coordinates of said second pixel and outputting a linear physical address of said second pixel in a memory,

wherein pixels displayed on said screen are sequentially stored in said memory at linear addresses beginning with the lowest two-dimensional virtual coordinate of said display screen and ending with the highest two-dimensional virtual coordinate of said display screen.