Image processing system enabling real-time output of image signal based on polygon image information

• US 5,448,690 A
• Filed: 02/17/1994
• Issued: 09/05/1995
• Est. Priority Date: 02/19/1993
• Status: Expired due to Term

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Shiraishi, Naoto, Nakajima, Tatsuya, Fujii, Tatsuya, Fukushima, Masanobu, Izawa, Yasuhiro
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/197,976
• Time in Patent Office: 565 Days
• Field of Search: 395/119-121, 395/126-128, 395/133, 395/134, 395/141, 395/143, 395/155, 395/160, 395/161
• US Class Current: 715/853
• CPC Class Codes: G06T 15/405 using Z-buffer

Abstract

A polygon extracting unit divides a screen image into n-level hierarchy in a scan-line shifting direction. The polygon extracting unit then accesses the sort memory and then reads data, from the screen memory, concerning the end points of the polygon corresponding to the value obtained as a result of the sort memory access. Then, the same unit, in the highest-level regions of the hierarchy, extracts the polygon edge-pairs overlapping the highest-level region. Then, the same unit, based on polygon edge-information, calculates the information concerning the corresponding edge pair to appear on the scan line. A polygon-edge-pair memory stores data concerning the starting point and ending point of the polygon on the scan line. A transfer unit determines whether or not the extracted polygon edge-pair overlaps with the relevant region. The same unit then transfers the polygon edge-pair to the lower-level regions if the polygon edge-pair overlaps. A polygon-edge-pair data transfer unit, in the lowest-level region, determines whether or not the polygon edge-pair overlaps with the lowest-level region. The same unit then transfers a parameter required for vertical interpolation from the polygon-edge-pair memory, for the polygon edge-pair, if the polygon edge-pair overlaps. A vertical-interpolation operation unit calculates the gradient of the relevant polygon edge-pair based on the relevant data. The same unit then calculates so as to interpolate between the right crossing point and the left crossing point on the scan line. An output unit outputs dot data synchronized to the scan line associated with display unit for displaying the relevant polygon figure.

Claims

1. An image processing system, comprising:

a) hierarchical division means for dividing a relevant image into a multiple-level hierarchy of regions; and

b) polygon edge-pair extracting means for extracting polygon edge-pairs to be displayed, wherein;

1) each edge-pair of said polygon edge-pairs includes a pair of sides among sides which constitute a relevant polygon;

2) the extraction is performed on regions among the multi-level hierarchy of regions;

3) the extraction is performed for each level of the multi-level hierarchy; and

4) the polygon edge-pairs to be extracted include polygon edge-pairs which are included in or overlap with the respective regions.

2. The image processing system of claim 1, wherein:

a) the multiple-level hierarchy of regions includes;

1) top-level regions obtained by dividing the relevant image;

2) at least one level of middle-level regions obtained by dividing each of the top-level regions; and

3) bottom-level regions obtained by dividing each of the middle-level regions; and

b) the polygon edge-pair extracting means includes;

1) top-level extracting means for performing the extracting on respective top-level regions;

2) middle-level extracting means for, while the top-level extracting means performs the extracting process on one of the top-level regions, performing the extracting on respective middle-level regions constituting the one of the respective top-level regions; and

3) bottom-level extracting means for, while the middle-level extracting means performs the extracting on one of the middle-level regions, performing the extracting process on respective bottom-level regions constituting the one of the middle-level regions.

3. The image processing system of claim 1, wherein the hierarchical dividing means constitutes:

means for geometrically dividing the relevant image into the multiple-level hierarchy of regions.

4. An image processing system comprising:

a) a screen memory for storing X and Y end point information constituting polygons;

b) a sort memory for storing polygon numbers sorted according to a priority value associated with each polygon;

c) a polygon extracting means including;

1) means for dividing a screen image into an n-level hierarchy in a scan-line shifting direction, wherein n is a natural number;

2) means for then accessing the sort memory;

3) means for then reading data from the screen memory, concerning the end points of the polygon corresponding to the value obtained as a result of the sort memory access;

4) means for then, in highest-level regions of the hierarchy, extracting polygon edge-pairs which overlap with the highest-level region, each edge-pair of the polygon edge-pairs including a pair of sides which are among sides constituting a relevant polygon; and

5) means for then, based on polygon-edge information, obtaining the edge pairs to be displayed on a relevant scan line;

d) a polygon-edge-pair memory for storing data concerning a starting point and an ending point in a polygon on the relevant scan line;

e) transfer means for determining whether or not the extracted polygon-edge pair overlaps with the relevant regions, and for then transferring the polygon edge-pair to lower-level regions if the polygon edge-pair overlaps;

f) polygon-edge-pair data transfer means for, in a lowest-level region, determining whether or not the polygon-edge pair overlaps with the lowest-level region, and for then transferring a parameter required for vertical interpolating from the polygon-edge-pair memory, for the polygon-edge-pair, if the polygon edge-pair overlaps;

g) vertical-interpolation operation means for calculating a gradient of the relevant polygon-edge pair based on the relevant data, and for then calculating so as to interpolate between a right crossing point and a left crossing point on the scan line; and

h) output means for outputting dot data in synchronization to the scan line associated with display means for displaying the relevant polygon figure.

5. The image processing system of claim 4, wherein the polygon-edge extracting means includes:

means for obtaining a direction of a line vector of each edge constituting the polygon based on the X and Y end point information and polygon-edge information;

means for separating, in accordance with obtained directions of the line vectors, respective edges into two groups including a right edge group and a left edge group;

a left edge counter to be incremented each time one of the separated edges belongs to the left edge group;

a left edge memory for storing edge information concerning the left edges;

a right edge counter to be incremented each time one of the separated edges belongs to the right edge group;

a right edge memory for storing edge information concerning the right edges; and

means for sorting the edges stored in the left edge memory and the right edge memory according to scan line, and for then calculating the edge pairs corresponding to the relevant polygon based on values of the left edge counter and right edge counter.

6. The image processing system of claim 4, further comprising:

determination processing means for determining, based on the right crossing point and the left crossing point, whether the relevant polygon constitutes a polygon to be displayed or a polygon not to be displayed; and

a line memory for storing the right crossing point and left crossing point on the scan line of only the polygon that is to be displayed.

7. The image processing system of claim 6, wherein the determination processing means includes:

dot-data output means for outputting dot data for each scan line based on the right crossing point and the left crossing point on the scan line, which were calculated by the vertical-interpolating operation means;

a flag memory for storing the dot data associated with the polygons previously determined as ones that are to be displayed;

determination means for comparing the dot data output by the dot-data output means with the dot data stored by the flag memory, and for then determining whether the relevant polygon is a polygon to be displayed or a polygon not to be displayed; and

rewriting means for performing a logical OR operation on the dot data associated with the polygons determined by the determination means as ones that are to be displayed and the dot data stored in the flag memory, and for then rewriting the contents of the flag memory with the data resulting from the logical OR operation.