Image processing apparatus

• US 5,455,900 A
• Filed: 10/14/1993
• Issued: 10/03/1995
• Est. Priority Date: 10/20/1992
• Status: Expired due to Term

• Current Assignee: Canine Acquisition Company, Inc.
• Original Assignee: Ricoh Company Limited
• Inventors: Shiraishi, Naoto, Fujii, Tatsuya
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/135,614
• Time in Patent Office: 719 Days
• Field of Search: 395/141, 395/139, 395/133, 395/119, 395/122, 395/162, 395/164, 345/113, 345/118
• US Class Current: 345/441
• CPC Class Codes: G06T 1/60 Memory management

Abstract

An image processing apparatus which can be operated using a small memory capacity and at a high speed. A screen memory for storing X and Y coordinate data for edge points of polygons and a sort memory for storing polygon numbers are provided. A polygon side computing unit computes data for sides of each of the polygons corresponding to each of the polygon numbers. A side pair computing unit computes side pair data in accordance with the data of sides of polygons, the side pair data comprising data of a pair of sides located on the scan lines of the screen. An inclination computing unit computes an inclination of each side of the side pair. A side pair memory stores inclination data and start and end point data of each side of the side pair, each data being stored in a position having a predetermined address. A frame memory stores data for the address of the side pair memory. An interpolation computing unit computes right and left intersection data on each of the scan lines. A processing unit processes the right and left intersection data so as to obtain dot data for the polygons, and outputs the dot data by synchronizing the dot data with the scan lines of the screen on the display unit.

Claims

1. An image processing apparatus which processes image data of a picture consisting of polygons to be displayed on a screen comprising scan lines of a display unit, the image processing apparatus comprising:

screen memory means for storing at least X and Y coordinate data for edge points of the polygons;

sort memory means for storing polygon numbers, which numbers are arranged in an order of priority in which the polygon having the highest priority is arranged first in the order;

polygon side computing means, connected to said screen memory means and said sort memory means, for computing, from the data for edge points stored in said screen memory means, data for sides of each of the polygons corresponding to each of said polygon numbers stored in said sort memory means;

side pair computing means for computing side pair data in accordance with the data of sides of polygons supplied by said polygon side computing means, said side pair data comprising data of a pair of sides located on the scan lines of the screen;

inclination computing means for computing an inclination of each side of said side pair;

side pair memory means for storing inclination data computed by said inclination computing means and start point and end point data of each side of said side pair, each data being stored in a position having a predetermined address;

frame memory means for storing data of the address of said side pair memory means;

interpolation computing means for computing, by means of an interpolation method, right intersection data and left intersection data on each of the scan lines, said right intersection data corresponding to an intersection of each of the scan lines and a right side of each of the polygons, and said left intersection data corresponding to an intersection of each of the scan lines and a left side of each of the polygons; and

processing means for processing said right intersection data and said left intersection data supplied by said interpolation computing means so as to obtain dot data for the polygons, and for outputting said dot data of the polygons by synchronizing said dot data with the scan lines of the screen on the display unit.

2. The image processing apparatus as claimed in claim 1, wherein said side pair computing means comprises:

vector computing means for computing a line vector of each side of each of the polygons in accordance with the data for edge points supplied by said screen memory means and the data for the sides of each of the polygons, and for determining a direction of said line vector;

classifying means for classifying each side of the polygons as either a left side or a right side in accordance with said direction of said line vector; and

side pair extracting means for extracting said side pair data in accordance with a number of said sides classified as left sides and a number of said sides classified as right sides.

3. The image processing apparatus as claimed in claim 2, wherein said side pair extracting means comprises:

a left side counter, a count value of which is incremented each time a side is classified as a left side;

a left side memory which stores data for each side classified as a left side;

a right side counter, a count value of which is incremented each time a side is classified as a right side; and

a right side memory which stores data for each side classified as a right side.

4. The image processing apparatus as claimed in claim 1, wherein said processing means comprises line memory means for storing dot data corresponding to the left intersection data and the right intersection data supplied by said interpolation computing means, said dot data being read out from said line memory means so as to be output in synchronization with an operation timing of each of said scan lines.

5. An image processing apparatus which processes image data of a picture consisting of polygons to be displayed on a screen comprising scan lines of a display unit, the image processing apparatus comprising:

screen memory means for storing at least X and Y coordinate data for edge points of the polygons;

sort memory means for storing polygon numbers, which numbers are arranged in an order of priority in which the polygon having the highest priority is arranged first in the order;

polygon side computing means, connected to said screen memory means and said sort memory means, for computing, from the data for edge points stored in said screen memory means, data for sides of each of the polygons corresponding to each of said polygon numbers stored in said sort memory means;

side pair computing means for computing side pair data in accordance with the data for sides of polygons supplied by said polygon side computing means, said side pair data comprising data of a pair of sides located on the scan lines of the screen;

inclination computing means for computing an inclination of each side of said side pair;

side pair memory means for storing inclination data computed by said inclination computing means and start point and end point data of each side of said side pair, each data being stored in a position having a predetermined address;

judging means for judging whether or not each of the polygons is to be displayed in accordance with the data received from said side pair memory means;

frame memory means for storing data of the address of said side pair memory means, said address corresponding only to the polygons which said judging means has judged are to be displayed;

interpolation computing means for computing, by means of an interpolation method, right intersection data and left intersection data on each of the scan lines, said right intersection data corresponding to an intersection of each of the scan lines and a right side of each of the polygons, and said left intersection data corresponding to an intersection of each of the scan lines and a left side of each of the polygons; and

processing means for processing said right intersection data and said left intersection data supplied by said interpolation computing means so as to obtain dot data for the polygons, and for outputting said dot data of the polygons by synchronizing said dot data with the scan lines of the screen on the display unit.

6. The image processing apparatus as claimed in claim 5, wherein said judging means comprises:

generating means for generating dot data of polygons for each scan line of the screen in accordance with said inclination data and said start point and end point data supplied by said side pair memory means;

flag memory means for storing said dot data of the polygons judged to be displayed;

determining means for determining whether or not a polygon is to be displayed by comparing dot data of said polygon generated by said generating means with dot data of another polygon stored in said flag memory; and

rewriting means for rewriting said dot data of the polygons stored in said flag memory based on a result of an OR operation on the dot data of the polygon to be displayed, which is output from said determining means, and the data of previously processed dot data for polygons stored in said flag memory means.

7. The image processing apparatus as claimed in claim 5, wherein said side pair computing means comprises:

vector computing means for computing a line vector of each side of each of the polygons in accordance with the data for edge points supplied by said screen memory means and the data for the sides of each of the polygons, and for determining a direction of said line vector;

classifying means for classifying each side of the polygons as either a left side or a right side in accordance with said direction of said line vector; and

side pair extracting means for extracting said side pair data in accordance with a number of said sides classified as left sides and a number of said sides classified as right sides.

8. The image processing apparatus as claimed in claim 7, wherein said side pair extracting means comprises:

a left side counter, a count value of which is incremented each time a side is classified as a left side;

a left side memory which stores data for each side classified as a left side;

a right side counter, a count value of which is incremented each time a side is classified as a right side; and

a right side memory which stores data for each side classified as a right side.

9. The image processing apparatus as claimed in claim 5, wherein said processing means comprises line memory means for storing dot data corresponding to the left intersection data and the right intersection data supplied by said interpolation computing means, said dot data being read out from said line memory means so as to be output in synchronization with an operation timing of each of said scan lines.

10. An image processing apparatus which processes image data of a picture consisting of polygons to be displayed on a screen comprising scan lines of a display unit, the image processing apparatus comprising:

screen memory means for storing at least X and Y coordinate data for edge points of the polygons;

sort memory means for storing polygon numbers, which numbers are arranged in an order of priority in which the polygon having the highest priority is arranged first in the order;

polygon side computing means, connected to said screen memory means and said sort memory means, for computing, from the data for edge points stored in said screen memory means, data for sides of each of the polygons corresponding to each of said polygon numbers stored in said sort memory means;

side pair computing means for computing side pair data in accordance with the data of sides of polygons supplied by said screen computing means, said side pair data comprising data of a pair of sides located on the scan lines of the screen;

inclination computing means for computing an inclination of each side of said side pair;

side pair memory means for storing polygon side pair data including inclination data computed by said inclination computing means and start point and end point data of each side of said side pair, each data being stored in a position having a predetermined address;

Y sort memory means for storing Y start point data and Y end point data of the polygon side pair and the address data of said side pair memory means;

sort processing means for rearranging the polygon side pair data in said side pair memory means in an order starting from polygon side pair data having the smallest Y address value of Y start point data, and for writing in said Y sort memory the Y start point data and Y end point data and the address of said side pair memory means corresponding to each polygon side pair;

interpolation computing means for computing, by means of an interpolation method, right intersection data and left intersection data on each of the scan lines upon accessing said side pair memory means and said Y sort memory means, said right intersection data corresponding to an intersection of each of the scan lines and a right side of each of the polygons, and said left intersection data corresponding to an intersection of each of the scan lines and a left side of each of the polygons; and

processing means for processing said right intersection data and said left intersection data supplied by said interpolation computing means so as to obtain dot data of the polygons, and for outputting said dot data of the polygons by synchronizing said dot data with the scan lines of the screen on the display unit.

11. The image processing apparatus as claimed in claim 10, wherein said interpolation computing means comprises:

selecting means for selecting a polygon side pair currently crossed by one of the scan lines, and reading out the data corresponding to said polygon side pair from among data in said Y sort memory means, the data being read out in an order starting from the data having a highest priority with respect to each scan line; and

scan line computing means for computing, by means of an interpolation method, right intersection data and left intersection data on each of the scan lines in accordance with the data supplied by said selecting means.

12. The image processing apparatus as claimed in claim 10, wherein said side pair computing means comprises:

vector computing means for computing a line vector of each side of each of the polygons in accordance with the data for edge points supplied by said screen memory means and the data of the sides of each of the polygons, and for determining a direction of said line vector;

classifying means for classifying each side of the polygons as either a left side or a right side in accordance with said direction of said line vector; and

side pair extracting means for extracting said side pair data in accordance with a number of said sides classified as left sides and a number of said sides classified as right sides.

13. The image processing apparatus as claimed in claim 12, wherein said side pair extracting means comprises:

a left side counter, a count value of which is incremented each time a side is classified as a left side;

a left side memory which stores data for each side classified as a left side;

a right side counter, a count value of which is incremented each time a side is classified as a right side; and

a right side memory which stores data for each side classified as a right side.

14. The image processing apparatus as claimed in claim 10, wherein said processing means comprises line memory means for storing dot data corresponding to the left intersection data and the right intersection data supplied by said interpolation computing means, said dot data being read out from said line memory means so as to be output in synchronization with an operation timing of each of said scan lines.

15. The image processing apparatus as claimed in claim 12, further comprising judging means for judging whether or not each of the polygons is to be displayed in accordance with the left intersection data and the right intersection data computed by said interpolation computing means, the left intersection pair data and the right intersection data corresponding only to the polygons which said judging means has judged are to be displayed being stored in said line memory.

16. The image processing apparatus as claimed in claim 15, wherein said judging means comprises:

generating means for generating dot data of polygons for each scan line of the screen in accordance with the inclination data and the left intersection data and the right intersection data computed by said interpolation computing means;

flag memory means for storing said dot data of the polygons judged to be displayed;

determining means for determining whether or not a polygon is to be displayed by comparing dot data of said polygon generated by said generating means with dot data of another polygon stored in said flag memory; and

rewriting means for rewriting said dot data of the polygons stored in said flag memory means based on a result of an OR operation on the dot data of the polygon to be displayed, which data is output from said determining means, and the data of previously processed dot data of polygons stored in said flag memory means.