Method and filling a polygon and recording medium

Details Method and filling a polygon and recording medium Method and filling a polygon and recording medium

1997-10-08

2001-04-10

Nguyen, Phu K. (Department: 2772)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

Reexamination Certificate

active

06215501

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for filling a polygon to be displayed in computer graphics based on the information stored in a display memory.
2. Description of the Background Art
Filling of a polygon in computer graphics has been implemented by using a scan line method and the like in the background art. This is a method in which a polygon is scanned from top to bottom with a horizontal line called a scan line to draw according to the following steps:
1. Take the scan line at the top of a polygon,
2. Repeat the following steps until the scan line reaches the bottom;
2-1. Obtain sides which intersect the scan line,
2-2. Obtain points of intersection of the scan line and these sides,
2-3. Sort the points of intersection according to x-coordinate,
2-4. Make pairs of two points of intersection in ascending order of x-coordinate and fill the two through,
2-5. Move to a lower scan line by one,
3. End.
In the step 2-2 of obtaining points of intersection of the scan line and these sides, when a point of intersection is a vertex of a polygon and the vectors of two sides have upward and downward directions, an exceptional process is performed, assuming that there are two points of intersection at the vertex. With respect to an object of
FIG. 59
, the exceptional process is performed on the points at the coordinates (S
1
, H
4
), (S
2
, H
11
), (S
5
, H
8
), (S
6
, H
7
), (S
8
, H
5
) and (S
10
, H
11
).
For example, when the line segments in the object of
FIG. 59
are selected in a counterclockwise rotation as shown in
FIG. 60
, as the line-segment vector A
1
(H
4
-H
8
, S
1
-S
5
) is in an upward direction (which makes an upward vertical-coordinate variation) and the line-segment vector A
2
(H
1
-H
4
, S
4
-S
1
) is in a downward direction (which makes a downward vertical-coordinate variation), it is assumed that there are two points of intersection at the coordinate (H
4
, S
1
) having two sides of the vectors A
1
and A
2
.
On the other hand, another method for filling a polygon is an outline font method, using a drawing work memory of 1 bit/pixel. This is a method in which the bits for the line segments of a polygon and in their right directions are inverted in a work memory (1 bit/pixel) having a minimum rectangular which surrounds an area to be drawn to make a drawing in the area of 1 bit/pixel and the drawing information in the work memory is transferred with extension to a display memory to draw a filled polygon thereon.
In the outline font method, based on outline information defining line segments constituting the outline of a polygon to be filled, selecting a line segment in a predetermined rotation, all the bits for the selected line segment and in its right direction on horizontal coordinate on the work memory are inverted to draw a filled object on the work memory. This process is performed according to the following conditions A) to G):
A) When both a line segment to be now subjected to the bit inversion and a line segment to be next have upward vectors (which makes an upward vertical-coordinate variation), the bits in the right direction of the line segment inclusive of the initial point and not inclusive of the terminal point are inverted.
B) When both a line segment to be now subjected to the bit inversion and a line segment to be next have downward vectors (which makes a downward vertical-coordinate variation), the bits in the right direction of the line segment inclusive of the initial point and not inclusive of the terminal point are inverted.
C) When a line segment to be now subjected to the bit inversion has an upward vector and a line segment to be next has a downward vector, the bits in the right direction of the line segment inclusive of the initial point and the terminal point are inverted.
D) When a line segment to be now subjected to the bit inversion has a downward vector and a line segment to be next has an upward vector, the bits in the right direction of the line segment inclusive of the initial point and the terminal point are inverted.
E) When a line segment to be now subjected to the bit inversion has a downward vector and a line segment to be next has a horizontal vector (which makes no vertical-coordinate variation), the bits in the right direction of the line segment inclusive of the initial point and not inclusive of the terminal point are inverted.
F) When a line segment to be now subjected to the bit inversion has an upward vector and a line segment to be next has a horizontal vector (which makes no vertical-coordinate variation), the bits in the right direction of the line segment inclusive of the initial point and not inclusive of the terminal point are inverted.
G) When a line segment to be now subjected to the bit inversion has a horizontal vector and a line segment to be next has a downward vector, the bits in the right direction of the line segment inclusive of the initial point and not inclusive of the terminal point are inverted.
H) When a line segment to be now subjected to the bit inversion has a horizontal vector and a line segment to be next has an upward vector, the bits in the right direction of the line segment inclusive of the initial point and not inclusive of the terminal point are inverted.
The outline font method will be discussed below, taking a triangle to be filled having the outline shown in
FIG. 61
as an example. First, the coordinates of three vertices {P
1
(H
8
, S
2
), P
2
(H
2
, S
15
), P
3
(H
16
, S
11
)} are obtained as the outline information.
With respect to a triangle to be filled, the line-segment vectors L
1
(H
2
-H
8
, S
15
-S
2
), L
2
(H
16
-H
2
, S
11
-S
15
) and L
3
(H
8
-H
16
, S
2
-S
11
) are selected in this order in a counterclockwise rotation as shown in
FIG. 62. A
plane work area on the work memory is blank (nothing is drawn) in an initial state.
First, the line segment L
1
is obtained from the coordinates of the vertices P
1
and P
2
given as the outline information, using an already-existing linear algorithm such as Bresenham algorithm, as shown in
FIGS. 63 and 64
, and all the bits in the right direction of the line segment L
1
on the horizontal coordinate on the plane work area (1 bit/pixel) of the work memory are inverted for drawing.
FIG. 63
shows a halfway state of the bit inversion of the line segment L
1
and
FIG. 64
shows the final result of the bit inversion. As the line segment L
1
is in the downward direction and the line segment L
2
is in the upward direction, according to the condition D), the bits in the right direction of the line segment L
1
inclusive of the initial point and the terminal point are inverted.
Secondly, the line segment L
2
is obtained from the coordinates of the vertices P
2
and P
3
given as the outline information, using the already-existing linear algorithm such as Bresenham algorithm, as shown in FIG.
65
and all the bits in the right direction of the line segment L
2
on the horizontal coordinate on the plane work area (1 bit/pixel) of the work memory are inverted. As a result, some of the already-drawn bits of
FIG. 64
are inverted again to be back in blank.
FIG. 65
shows a halfway state of the bit inversion of the line segment L
2
. As the line segments L
2
and L
3
are both in the upward direction, according to the condition A), the bits in the right direction of the line segment L
2
inclusive of the initial point and not inclusive of the terminal point are inverted.
Similarly, the line segment L
3
is obtained from the outline information, and all the bits in the right direction of the line segment L
3
on the horizontal coordinate on the plane work area (1 bit/pixel) of the work memory are inverted, to complete the triangle which is filled inside as shown in FIG.
66
. As the line segment L
3
is in the upward direction and the line segment L
1
is in the downward direction, according to the condition C), the bits in the right direction of the line segment L
3
inclusive of the initial point and the terminal point are inverted.
After that, the drawing i

Affiliated with

Also associated with

Rating

Method and filling a polygon and recording medium does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and filling a polygon and recording medium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and filling a polygon and recording medium will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2529708