Title: Active region determination for line generation in regionalized rasterizer displays
Abstract: In one embodiment, selecting a screen region on a screen of a monitor of a computer graphics display system to activate in rendering a straight line segment. Steps of aligning a rectangular grid to screen region boundaries, wherein the screen includes a screen space divided into at least one screen region, locating a first and second endpoints of the straight line segment on the screen space, defining a rectangular bounding box in the screen space having vertices at the first and second endpoints, identifying each screen region that at least partially overlaps the bounding box, and selecting each identified screen region through which the straight line segment passes to activate for rendering the straight line segment on the screen are disclosed.
Patent Number: 6,992,670 Issued on 01/31/2006 to Thrasher, et al.
| Inventors:
|
Thrasher; Thomas L. (Ft. Collins, CO);
Larson; Ronald D. (Fort Collins, CO)
|
| Assignee:
|
Hewlett-Packard Development Company, L.P. (Houston, TX)
|
| Appl. No.:
|
746787 |
| Filed:
|
December 23, 2003 |
| Current U.S. Class: |
345/443; 345/419; 703/1 |
| Current Intern'l Class: |
G06T 11/20 (20060101); G06T 15/00 (20060101); G06F 17/50 (20060101) |
| Field of Search: |
345/441- 43,619,582,419,443
703/1
|
References Cited [Referenced By]
U.S. Patent Documents
Other References
Foley et al., "Computer Graphics: Principles and Practice— Second Edition
in C", Reading, Massachusetts: Addison-Wesley Publishing Company (1996), pp. 71-79.
Segal et al., "The OpenGL Graphics System: A Specification (Version 1.3)", Aug.
14, 2001, pp. 58-78.
|
Primary Examiner: Bella; Matthew C.
Assistant Examiner: Blackman; Anthony J.
Parent Case Text
This is a Continuation of copending application Ser. No. 09/982,352, filed on
18 Oct. 2001, now U.S. Pat. No. 6,753,861 the entire disclosure of which is incorporated
herein by reference.
Claims
What is claimed is:
1. A method for selecting screen regions to activate in rendering a straight
line segment on a monitor screen of a computer graphics display system, comprising:
conceptually dividing a screen space on the screen into multiple, non-overlapping,
screen regions, wherein the multiple screen regions fill the screen space;
locating first and second endpoints of the straight line segment on the screen space;
defining a rectangular bounding box in the screen space having vertices at the
first and second endpoints, wherein the bounding box is overlapped by at least
part of at least two of the screen regions;
identifying each screen region that at least partially overlaps the bounding
box; and
from the screen regions so identified, selecting those screen regions through
which the straight line segment passes as those screen regions to activate in rendering
the straight line segment on the screen.
2. The method as recited in claim 1, wherein a locus of the straight line segment
is specified by equation A*x+B*y+C=0, wherein A, B, and C are respectively a first,
second, and third constants, wherein x and y are respectively Cartesian coordinate
system x-axis and y-axis values, and wherein the method step of selecting each
identified screen region through which the straight line segment passes further comprises:
marking the overlapping screen region as not selected;
setting a control variable equal to a preselected value;
for each corner of the overlapping screen region,
while the overlapping screen region is marked as not selected,
multiplying the first constant by the x-axis coordinate of the corner;
multiplying the second constant by the y-axis coordinate of the corner;
adding the third constant, the result of the method step of multiplying the first
constant by the x-axis coordinate of the corner, and the result of the method step
of multiplying the second constant by the y-axis coordinate of the corner; and
when the control variable is equal to the preselected value,
storing in a memory the algebraic sign of the result of the method step adding
the third constant; and
setting the control variable to a value other than the preselected value;
otherwise, when the algebraic sign of the result of the method step adding the
third constant differs from the stored algebraic sign,
marking the screen region as selected.
3. The method as recited in claim 1, further comprising:
activating the screen regions selected in the selecting method step.
4. The method as recited in claim 3, further comprising:
rendering the straight line segment in the screen regions activated in the activating
method step, wherein rendering of the straight line segment in each activated screen
region is effected by the rasterizer controlling that screen region.
5. A computer-readable medium having computer-executable instructions for performing
a method for selecting screen regions to activate in rendering a straight line
segment on a monitor screen of a computer graphics display system, comprising:
conceptually dividing a screen space on the screen into multiple, non-overlapping,
screen regions, wherein the multiple screen regions fill the screen space;
locating first and second endpoints of the straight line segment on the screen space;
defining a rectangular bounding box in the screen space having vertices at the
first and second endpoints, wherein the bounding box is overlapped by at least
part of at least two of the screen regions;
identifying each screen region that at least partially overlaps the bounding
box; and
from the screen regions so identified, selecting those screen regions through
which the straight line segment passes as those screen regions to activate in rendering
the straight line segment on the screen.
6. The program storage medium as recited in claim 5, providing a locus of the
straight line segment is specified by equation A*x+B*y+C=0, wherein A, B, and C
are respectively a first, second, and third constants, wherein x and y are respectively
Cartesian coordinate system x-axis and y-axis values, and wherein the method step
for selecting each identified screen region through which the straight line segment
passes further comprises:
marking the overlapping screen region as not selected;
setting a control variable equal to a preselected value;
for each corner of the overlapping screen region,
while the overlapping screen region is marked as not selected,
multiplying the first constant by the x-axis coordinate of the corner;
multiplying the second constant by the y-axis coordinate of the corner;
adding the third constant, the result of the method step multiplying the first
constant by the x-axis coordinate of the corner, and the result of the method step
multiplying the second constant by the y-axis coordinate of the corner; and
when the control variable is equal to the preselected value,
storing in a memory the algebraic sign of the result of the method step adding
the third constant; and
setting the control variable to a value other than the preselected value;
otherwise, when the algebraic sign of the result of the method step adding the
third constant differs from the stored algebraic sign,
marking the screen region as selected.
7. The program storage medium as recited in claim 5, further comprising:
activating the screen regions selected by the selecting method step.
8. The program storage medium as recited in claim 7, further comprising:
rendering the straight line segment in the screen regions activated in the activating
method step, wherein rendering of the straight line segment in each activated screen
region is effected by the rasterizer controlling that screen region.
9. A method for selecting screen regions to activate in rendering a straight
line segment on a monitor screen of a computer graphics display system, comprising:
conceptually dividing a screen space on the screen into multiple, non-overlapping,
screen regions, wherein each screen region is controlled by one of at least two
rasterizers wherein each rasterizer controls at least one screen region, and wherein
the multiple screen regions fill the screen space;
locating first and second endpoints of the straight line segment on the screen space;
defining a rectangular bounding box in the screen space having vertices at the
first and second endpoints, wherein the bounding box is overlapped by at least
part of at least two of the screen regions;
identifying each screen region that at least partially overlaps the bounding
box; and
from the screen regions identified in the identifying method step, selecting
those screen regions through which the straight line segment passes as those screen
regions to activate in rendering the straight line segment on the screen.
10. The method as recited in claim 9, wherein a locus of the straight line segment
is specified by equation A*x+B*y+C=0, wherein A, B, and C are respectively a first,
second, and third constants, wherein x and y are respectively Cartesian coordinate
system x-axis and y-axis values, and wherein the method step of selecting each
identified screen region through which the straight line segment passes further comprises:
marking the overlapping screen region as not selected;
setting a control variable equal to a preselected value;
for each corner of the overlapping screen region,
while the overlapping screen region is marked as not selected,
multiplying the first constant by the x-axis coordinate of the corner;
multiplying the second constant by the y-axis coordinate of the corner;
adding the third constant, the result of the method step of multiplying the first
constant by the x-axis coordinate of the corner, and the result of the method step
of multiplying the second constant by the y-axis coordinate of the corner; and
when the control variable is equal to the preselected value,
storing in a memory the algebraic sign of the result of the method step adding
the third constant; and
setting the control variable to a value other than the preselected value;
otherwise, when the algebraic sign of the result of the method step adding the
third constant differs from the stored algebraic sign,
marking the screen region as selected.
11. The method as recited in claim 9, further comprising:
activating the screen regions selected in the selecting method step.
12. The method as recited in claim 11, further comprising:
rendering the straight line segment in the screen regions activated in the activating
method step, wherein rendering of the straight line segment in each activated screen
region is effected by the rasterizer controlling that screen region.
13. A computer-readable medium having computer-executable instructions for performing
a method for selecting screen regions to activate in rendering a straight line
segment on a monitor screen of a computer graphics display system, comprising:
conceptually dividing a screen space on the screen into multiple, non-overlapping,
screen regions, wherein each screen region is controlled by one of at least two
rasterizers, wherein each rasterizer controls at least one screen region, and wherein
the multiple screen regions fill the screen space;
locating first and second endpoints of the straight line segment on the screen space;
defining a rectangular bounding box in the screen space having vertices at the
first and second endpoints, wherein the bounding box is overlapped by at least
part of at least two of the screen regions;
identifying each screen region that at least partially overlaps the bounding
box; and
from the screen regions so identified, selecting those screen regions through
which the straight line segment passes as those screen regions to activate in rendering
the straight line segment on the screen.
14. The program storage medium as recited in claim 13, providing a locus of the
straight line segment is specified by equation A*x+B*y+C=0, wherein A, B, and C
are respectively a first, second, and third constants, wherein x and y are respectively
Cartesian coordinate system x-axis and y-axis values, and wherein the method step
for selecting each identified screen region through which the straight line segment
passes further comprises:
marking the overlapping screen region as not selected;
setting a control variable equal to a preselected value;
for each corner of the overlapping screen region,
while the overlapping screen region is marked as not selected,
multiplying the first constant by the x-axis coordinate of the corner;
multiplying the second constant by the y-axis coordinate of the corner;
adding the third constant, the result of the method step multiplying the first
constant by the x-axis coordinate of the corner, and the result of the method step
multiplying the second constant by the y-axis coordinate of the corner; and
when the control variable is equal to the preselected value,
storing in a memory the algebraic sign of the result of the method step adding
the third constant; and
setting the control variable to a value other than the preselected value;
otherwise, when the algebraic sign of the result of the method step adding the
third constant differs from the stored algebraic sign,
marking the screen region as selected.
15. The program storage medium as recited in claim 13, further comprising:
activating the screen regions selected by the selecting method step.
16. The program storage medium as recited in claim 15, further comprising:
rendering the straight line segment in the screen regions activated in the activating
method step, wherein rendering of the straight line segment in each activated screen
region is effected by the rasterizer controlling that screen region.
17. A computer graphics display system for rendering a straight line segment, comprising:
a central processing unit;
at least two rasterizers;
a monitor, wherein a screen space of the monitor is conceptually divided into
multiple, non-overlapping, screen regions, wherein each screen region is controlled
by one of the at least two rasterizers, wherein each rasterizer controls at least
one screen region, and wherein the multiple screen regions fill the screen space; and
a computer program, wherein the central processing unit is capable of running
the computer program and wherein the computer program has instructions for performing
method steps for locating first and second endpoints of the straight line segment
on the screen space, defining a rectangular bounding box in the screen space having
vertices at the first and second endpoints, wherein the bounding box is overlapped
by at least part of at least two of the screen regions, identifying each screen
region that at least partially overlaps the bounding box, and from the screen regions
so identified, selecting those screen regions through which the straight line segment
passes as those screen regions to activate in rendering the straight line segment
on the screen.
18. The computer graphics display system as recited in claim 17, wherein a locus
of the straight line segment is specified by equation A*x+B*y+C=0, wherein A, B,
and C are respectively a first, second, and third constants, wherein x and y are
respectively Cartesian coordinate system x-axis and y-axis values, and wherein
the method step of selecting each identified screen region through which the straight
line segment passes further comprises:
marking the overlapping screen region as not selected;
setting a control variable equal to a preselected value;
for each corner of the overlapping screen region,
while the overlapping screen region is marked as not selected,
multiplying the first constant by the x-axis coordinate of the corner;
multiplying the second constant by the y-axis coordinate of the corner;
adding the third constant, the result of the method step of multiplying the first
constant by the x-axis coordinate of the corner, and the result of the method step
of multiplying the second constant by the y-axis coordinate of the corner; and
when the control variable is equal to the preselected value,
storing in a memory the algebraic sign of the result of the method step adding
the third constant; and
setting the control variable to a value other than the preselected value;
otherwise, when the algebraic sign of the result of the method step adding the
third constant differs from the stored algebraic sign,
marking the screen region as selected.
19. The computer graphics display system as recited in claim 17, wherein the
method steps of the computer program instructions further comprise:
activating the screen regions selected in the selecting method step.
20. The computer graphics display system as recited in claim 19, wherein the
method steps of the computer program instructions further comprise:
rendering the straight line segment in the screen regions activated in the activating
method step, wherein rendering of the straight line segment in each activated screen
region is effected by the rasterizer controlling that screen region.
Description
FIELD OF THE INVENTION
The present invention relates generally to computer graphics displays, and particularly
to the display of straight line segments on computer graphics displays.
BACKGROUND OF THE INVENTION
Computer graphics systems are commonly used to display graphical representations
of two-dimensional or three-dimensional objects on a two-dimensional display screen.
The display screen is typically a cathode ray tube (CRT) device and is divided
into arrays of elements referred to as pixels which can be stimulated to emit a
range of visual light. The stimulation of the pixels is performed sequentially
in some regular order and is repeated typically 50 to 80 times a second in order
to maintain a screen image whose intensity does not noticeably change with time.
Typical CRT devices for use with graphics workstations are "raster scan"
display devices. Modern raster scan display devices generate images comprising
a multiplicity of parallel, non-overlapping bands of pixels comprising sets of
parallel lines.
In typical computer graphics systems, an object to be represented on the display
screen is broken down into a plurality of graphics primitives. Primitives are the
basic components of a graphics picture and may include points, lines, vectors,
and polygons, such as triangles. Typically, a hardware/software scheme is implemented
to render, or draw, on the two-dimensional display screen, the graphics primitives
that represent a particular view of one or more objects being represented on the screen.
As display systems have increased in complexity to meet an ever-increasing demand
for a larger display area and a greater fidelity in the representation of objects
on the display screen, the load on the hardware and software required to process
the image has also increased. An increase in object representation fidelity has
been accomplished, in part, by a decrease in pixel size with a corresponding increase
in the number of pixels. The total number of pixels required has also increased
as the size of the screen used for display has increased.
To improve performance with the increasing demands upon the rendering system,
designers are employing varying techniques to add parallelism in the rendering
process. One such technique divides the display's screen space into multiple regions.
If a primitive or any portion of a primitive lies within a region, then that region
is selected for further processing by a rasterizer that will ultimately render
the image contained in that region. Parallelism can now be obtained by having multiple
rasterizers available which can be independently assigned to the screen regions
that have objects to be rendered, thus allowing multiple objects to be simultaneously rendered.
Typical systems render a straight line segment via a stepping algorithm.
A starting point on the display for the line is determined with the pixel corresponding
to that point being illuminated. The next pixel to be illuminated is determined
by stepping along the major axis one pixel position and then computing the value
of the pixel in the minor axis direction. The major axis is defined as that axis
to which the line to be rendered forms an included angle of less than or equal
to 45 degrees. The minor axis then is the other axis of a Cartesian coordinate
system. For example, if the line to be rendered forms an included angle of 37 degrees
to the x-axis, then the x-axis is considered to be the major axis and the y-axis
the minor axis. In like manner, the next pixel to be illuminated is determined
by again stepping one pixel position along the major axis, which is the x-axis
in the example, and then computing the corresponding minor axis position, the y-axis
in the example, of the pixel on the line to be rendered. This process is repeated
until the end of the line is reached. In a region-based rasterizer system, what
is desired is a technique that focuses only on the portion of the line within the
region currently being processed rather than a traditional technique of starting
at the beginning of the line segment and processing to the end, crossing potentially
many different regions.
SUMMARY OF THE INVENTION
As noted earlier, previous methods for rendering straight line segments have
typically
used a single rasterizer to generate all the pixels for a given line from the start
of the line to the end of the line without regard to regions or region boundaries.
With region-based rasterization however, it is possible that a single line might
have several rasterizers generating pixels for that line, each operating within
its assigned screen region. By identifying which regions the line passes thru,
only rasterizers assigned to those regions need to be activated to process the
line, freeing rasterizers assigned to the other regions to process primitives appearing
in their regions. Techniques disclosed herein limit the area of the screen that
must be considered in drawing the straight line segment providing for more computationally-efficient
techniques. In the following detailed description and in the several figures of
the drawings, like elements are identified with like reference numerals.
In one embodiment of the invention, a method for selecting a screen region on
a screen of a monitor of a computer graphics display system to activate in rendering
a straight line segment is disclosed. The method includes the steps of aligning
a rectangular grid to screen region boundaries, wherein the screen includes a screen
space divided into at least one screen region, locating a first and second endpoints
of the straight line segment on the screen space, defining a rectangular bounding
box in the screen space having vertices at the first and second endpoints, identifying
each screen region that at least partially overlaps the bounding box, and selecting
each identified screen region through which the straight line segment passes to
activate for rendering the straight line segment on the screen.
BRIEF DESCRIPTION OF THE DRAWINGS
The accompanying drawings provide visual representations which will be used to
more fully describe the invention and can be used by those skilled in the art to
better understand it and its inherent advantages. In these drawings, like reference
numerals identify corresponding elements.
FIG. 1A is a drawing of a computer graphics display system as described in various
representative embodiments consistent with the teachings of the invention.
FIG. 1B is a drawing of the screen space of the computer graphics display system
as described in various representative embodiments consistent with the teachings
of the invention.
FIG. 2 is a drawing of another screen space of the computer graphics display
system as described in various representative embodiments consistent with the teachings
of the invention.
FIG. 3A-3C are various representations of a screen region of the computer graphics
display system as described in illustrative embodiments consistent with the teachings
of the invention.
FIG. 4 is an illustrative flow chart of a method for selecting screen regions
to activate in rendering a straight line segment as described in various representative
embodiments consistent with the teachings of the invention.
FIG. 5 is a drawing of a portion of the screen space of the computer graphics
display system as described in various representative embodiments consistent with
the teachings of the invention.
FIG. 6A-6J are various representations of one pixel of the screen space of the
computer graphics display system as described in illustrative embodiments consistent
with the teachings of the invention.
FIG. 7 is an illustrative flow chart of a method for selecting pixels to activate
in rendering a straight line segment as described in various representative embodiments
consistent with the teachings of the invention.
FIG. 8 is a drawing of yet another screen space of the computer graphics display
system as described in various representative embodiments consistent with the teachings
of the invention.
FIG. 9 is a drawing of adjacent screen regions in the screen space of the computer
graphics display system as described in various representative embodiments consistent
with the teachings of the invention.
FIG. 10 is another drawing of adjacent screen regions in the screen space of
the computer graphics display system as described in various representative embodiments
consistent with the teachings of the invention.
FIG. 11 is an illustrative flow chart of a method for selecting auxiliary screen
regions to activate in rendering the straight line segment having widths greater
than one pixel as described in various representative embodiments consistent with
the teachings of the invention.
FIG. 12 is an illustrative flow chart of another method for selecting auxiliary
screen regions to activate in rendering the straight line segment having widths
greater than one pixel as described in various representative embodiments consistent
with the teachings of the invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
As shown in the drawings for purposes of illustration, novel techniques are shown
in a computer graphics display system for selecting regions of a screen to activate
in rendering a straight line segment, for selecting pixels to activate in rendering
the straight line segment, and for selecting pixels to activate in rendering an
auxiliary area of the straight line segment required in cases wherein the straight
line segment has a width of greater than one pixel. In existing region-based rasterizers,
every line primitive is processed in every region to determine whether any pixels
are active in that region. By selecting regions to activate or consider, techniques
disclosed herein limit the area of the screen that must be considered in drawing
the straight line segment, thereby providing for more computationally-efficient
techniques. In the following detailed description and in the several figures of
the drawings, like elements are identified with like reference numerals.
In representative embodiments, the following paragraphs disclose methods for
(1)
selecting regions of the screen to activate in rendering a straight line segment
in a computer graphics display system, (2) selecting pixels to activate in rendering
the straight line segment in the computer graphics display system, and (3) selecting
screen regions to activate in rendering the auxiliary area of a straight line segment
required in cases wherein the straight line segment has a width in a computer graphics
display system.
FIG. 1A is a drawing of a computer graphics display system
100 as described
in various representative embodiments consistent with the teachings of the invention.
The computer graphics display system
100 of FIG. 1 comprises a computer
monitor
105, a central processing unit (CPU)
106, a memory
108,
and a graphics control system
107. The monitor
105 comprises a screen
110 conceptually having a screen space
115. The graphics control
system
107 comprises at least one rasterizer
120.
FIG. 1B is a drawing of the screen space
115 of the computer graphics
display system
100 as described in various representative embodiments consistent
with the teachings of the invention. The screen space
115 is conceptually
divided into at least one screen region
125, also referred to herein as
region
125, by vertical and horizontal grid lines
131,
132,
respectively, which together form a rectangular grid
130. While thirty screen
regions
125 are shown in the example of FIG. 1B, for clarity of illustration,
only one is shown with its associated identifying numeral.
Graphics systems are computationally intensive systems. As such, a valuable
increase in system performance can be obtained via dividing the screen space
115
into multiple regions
125 and ignoring certain regions
125 in the
rendering of primitives such as a line segment. Additional increases in system
performance can be obtained via the parallel processing afforded by the use of
multiple rasterizers
120. Graphics systems which divide screen space
115
into multiple regions
125 with specified rasterizers
120 assigned
to perform rasterization for specified regions of the screen space
115 are
referred to as multiple region or tile-based rasterizer systems. In the representative
embodiment of FIG. 1B, each screen region
125 can be associated with one
of the rasterizers
120. In another representative embodiment, a given rasterizer
120 could be responsible for the processing of more than one region
125.
The assignment of rasterizers
120 to regions
125 could be either
statically or dynamically performed.
FIG. 2 is a drawing of another screen space
115 of the computer graphics
display system
100 as described in various representative embodiments consistent
with the teachings of the invention. In the example of FIG. 2, the screen space
115 is once again shown conceptually divided into thirty screen regions
125 by vertical and horizontal grid lines
131,
132, respectively,
which together form rectangular grid
130. While thirty screen regions
125
are shown in the example of FIG. 2, again for clarity of illustration, only one
is shown with its associated identifying numeral. Screen space
115 is shown
divided horizontally into first, second, third, fourth, and fifth region columns
C
1 . . . C
5 and vertically into first, second, third, fourth, fifth,
and sixth region rows R
1 . . . R
6 with individual screen regions
125 of the first region row R
1 being indicated as R
1,C
1
. . . R
1,C
5.
A straight line segment
205 is drawn in screen space
115 of FIG.
2. The straight line segment
205 has a first end point P
1 having
x and y coordinates (X
1,Y
1) of a Cartesian coordinate system and
a second end point P
2 having x and y coordinates (X
2,Y
2).
A bounding box
210 which identifies the extent of the screen
110
region that is of concern in displaying the straight line segment
205 is
conceptually defined on the screen space
115 by the first and second end
points P
1,P
2 wherein the bounding box has a first and second corners
215,
220. The first corner
215 of the bounding box
210
is defined by the coordinates (min(X
1,X
2), min(Y
1,Y
2)),
and the second corner
220 of the bounding box
210 is defined by the
coordinates (max(X
1,X
2), max(Y
1,Y
2)), where min(a,b)
returns the minimum of the two values a and b, and max(a,b) returns the maximum
of the two values a and b. The rectangular grid
130 is located on the boundaries
of the screen regions
125. The extent of this grid
130 should be
large enough to include the bounding box
210. Any part of the screen space
115 outside of this extent is guaranteed not to have any part of the straight
line segment
205 contained within it.
Note that in the example of FIG. 2, first end point P
1 and first corner
215 are coincident, and second end point P
2 and second corner
220
are coincident. However, had the slope of the straight line segment
205
been negative instead of positive as in FIG. 2, the first corner
215 would
have still been at the lower left hand corner of the bounding box
210, and
the second corner
220 would have still been at the upper right hand corner
of the bounding box
210 while the first and second end points P
1,P
2
would have been located respectively at the upper left hand corner and lower right
hand corners of the bounding box
210. Other designations are also possible
in defining the bounding box
210.
A first objective is to determine which of the screen regions
125 will
be
activated in displaying the straight line segment
205 on the screen
110
of the monitor
105. Only those screen regions
125 through which the
straight line segment
205 passes will need to be activated. All other screen
regions
125 can be ignored in the display of that straight line segment
205. As a first step, select all screen regions that are contained wholly
or in part within the bounding box identified above. The following discussion is
preferably independently applied to each of the identified screen regions.
The general equation of a straight line is A*x+B*y+C=0, which for the example
of the straight line segment
205 of FIG. 2 results in A=(Y
2-Y
1),
B=(X
1-X
2), and C=-(A*X
1+B*Y
1).
FIG. 3A-3C are various representations of a screen region
125 of the
computer graphics display system
100 as described in illustrative embodiments
consistent with the teachings of the invention. FIG. 3A shows a single screen region
125 of the thirty shown in FIG. 2. The particular screen region
125
of FIG. 3A has the straight line segment
205 passing below the screen region
125 and its lower right hand corner, similar to that for the screen region
125 identified in FIG. 2 by region row R
2 and region column C
2.
To determine mathematically whether or not the straight line segment
205
passes through the screen region
125 of FIG. 3A, it is only necessary to
evaluate the expression A*x+B*y+C at each of the four corners of the screen region
125 of FIG. 3A where the constants A, B, and C are determined as indicated
above for the straight line segment
205. For FIG. 3A, this expression is
positive for each corner as indicated by the "(+)" symbol shown at each corner
in FIG. 3A. For this case, each of the four corners of the screen region
125
of FIG. 3A lies above the straight line segment
205 indicating that the
straight line segment
205 does not pass through this screen region
125,
and therefore this screen region
125 is not selected for further processing
in displaying the straight line segment
205 on the screen
110.
FIG. 3B shows a single screen region
125 of the thirty shown in FIG.
2. The particular screen region
125 of FIG. 3B has the straight line segment
205 passing above the screen region
125 and its upper left hand corner,
as it does for the screen region
125 identified in FIG. 2 by region row
R
4 and region column C
3. To determine mathematically whether or not
the straight line segment
205 passes through the screen region
125
of FIG. 3B, it is only necessary to evaluate the expression A*x+B*y+C at each of
the four corners of the screen region
125 of FIG. 3B where the constants
A, B, and C are determined as indicated above for the straight line segment
205.
For FIG. 3B, this expression is negative for each corner as indicated by the "(-)"
symbol shown at each corner in FIG. 3B. For this case, each of the four corners
of the screen region
125 of FIG. 3B lies below the straight line segment
205 indicating that the straight line segment
205 does not pass through
this screen region
125, and therefore this screen region
125 is not
selected for further processing in displaying the straight line segment
205
on the screen
110.
FIG. 3C shows a single screen region
125 of the thirty shown in FIG.
2. The particular screen region
125 of FIG. 3C has the straight line segment
205 passing through the lower right hand section of the screen region
125,
as it does for the screen region
125 identified in FIG. 2 by region row
R
3 and region column C
2. To determine mathematically whether or not
the straight line segment
205 passes through the screen region
125
of FIG. 3C, it is only necessary to evaluate the expression A*x+B*y+C at each of
the four corners of the screen region
125 of FIG. 3C where the constants
A, B, and C are determined as indicated above for the straight line segment
205.
For FIG. 3C, this expression is positive for three of the corners as indicated
by the "(+)" symbol near the lower left hand corner, the upper left hand corner,
and the upper right hand corner of this screen region
125 and negative for
one corner of this screen region
125 as indicated by the "(-)" symbol shown
at the lower right hand corner. For this case, three of the four corners of the
screen region
125 of FIG. 3B lies above the straight line segment
205
and one lies below indicating that the straight line segment
205 does indeed
pass through this screen region
125, and therefore this screen region
125
is selected for further processing, or activated in displaying the straight line
segment
205 on the screen
110.
Whenever evaluating the expression A*x+B*y+C at all four corners of any
given screen region
125, produces results that have the same algebraic signs,
the straight line segment
205 does not pass through that screen region
125,
and the corresponding screen region
125 will preferably not be activated
in displaying the straight line segment
205 on the screen
110. Whenever
evaluating the expression A*x+B*y+C at all four corners of any given screen region
125, produces results that have at least one algebraic sign that differs
from the others, the straight line segment
205 does pass through that screen
region
125, and the corresponding screen region
125 will be activated
in displaying the straight line segment
205 on the screen
110.
FIG. 4 is an illustrative flow chart of a method for selecting screen regions
125 to activate in rendering a straight line segment
205 as described
in various representative embodiments consistent with the teachings of the invention.
This method would be preferably applied in turn against each screen region selected
to test.
In block
405, a control variable is set equal to a preselected value,
which
could be for example the number "0". Block
405 then transfers control to
block
410.
In block
410, the overlapping screen region
125 is marked as other
than selected. Block
410, then transfers control to block
415.
In block
415, when the overlapping screen region
125 is marked
as
other than selected, block
410 transfers control to block
420. Otherwise,
block
415 terminates the process.
In block
420, the expression A*x+B*y =C is computed for a corner of one
of the identified overlapping screen regions
125. Block
420, then
transfers control to block
425.
In block
425, when the control variable is equal to the preselected value,
block
425 transfers control to block
430. Otherwise, block
425
transfers control to block
440.
In block
430, the algebraic sign of the result of the computation of the
expression A*x+B*y+C obtained in block
420 is stored. Block
430 then
transfers control to block
435.
In block
435, the value of the control variable is changed from its preselected
value to something else, which could be for example the number "1". Block
435
then transfers control to block
450.
In block
440, when the algebraic sign of the result of the computation
of the expression A*x+B*y+C obtained in block
420 differs from that stored
in block
430, block
440 transfers control to block
445. Otherwise,
block
440 transfers control to block
450.
In block
445, the overlapping screen region
125 is marked as selected.
Block
445 then transfers control to block
450.
In block
450, when there are remaining corners of the overlapping screen
region
125 for which in block
420 the expression A*x+B*y+C have not
been computed, block
450 transfers control to block
415. Otherwise,
block
450 terminates the process.
A second objective is to determine which pixels in displaying the straight line
segment
205 on the screen
110 of the monitor
105 are illuminated
within each of the activated screen regions
125. Only those pixels through
which the straight line segment
205 passes may need to be illuminated. All
others can be ignored in the display of that straight line segment
205.
FIG. 5 is a drawing of a portion of the screen space
115 of the computer
graphics display system
100 as described in various representative embodiments
consistent with the teachings of the invention. In the example of FIG. 2, the portion
of the screen space
115 shown is that occupied by a single screen region
125. The screen region
125 of FIG. 5 is divided into multiple pixels
505. While twenty-five pixels
505 are drawn in the example of FIG.
5, for clarity of illustration, only one is shown with its associated identifying
numeral. The screen region
125 of FIG. 5 is shown conceptually divided into
pixels
505 by vertical and horizontal grid lines
531,
532,
respectively, which together form a finer gradation of the rectangular grid
130.
The rectangular grid
130 is aligned to the boundaries of the pixels
505.
The screen space
115 occupied by the screen region
125 of FIG. 5
is shown divided horizontally into pixel first, second, third, fourth, and fifth
columns c
1 . . . c
5 and vertically into first, second, third, fourth,
and fifth pixel rows r
1 . . . r
5 with individual pixels
505
of the first pixel row r
1 being indicated as r
1,c
1 . . . r
1,c
5.
FIG. 6A-6J are various representations of one pixel
505 of the screen
space
115 of the computer graphics display system
100 as described
in illustrative embodiments consistent with the teachings of the invention. The
pixel
505 has a width
640 and a height
645 as its dimensions.
A center
650 of the pixel
505 is located at a distance equal to one-half
that of the width
640 from a left edge
660 and at a distance equal
to one-half that of the height
645 from a lower edge
665. In other
words, the lines of the rectangular grid
130 lie half way between the centers
650 of the pixels
505.
In FIG. 6B, a vertical offset-grid line
670 passes through the center
650
of the pixel
505. The vertical offset-grid line
670 is formed by
offsetting a left grid line
680 of the pixel
505 to the right from
its nominal position by ½ its width
640. This movement is shown by
first offset
672. The left grid line
680 is co-linear with the left
edge
660 of the pixel
505. The vertical offset-grid line
670
intersects the pixel
505 boundaries at upper and lower intersection points
V
1 and V
2. In order to determine mathematically whether or not to
illuminate the pixel
505, it is only necessary to evaluate the expression
A*x+B*y+C at each of the two points V
1 and V
2. FIGS. 6C-6E illustrate
the results for three separate conditions of straight line segments
205
passing through the pixel
505.
Evaluating the expression A*x+B*y+C at the two points V
1 and V
2
results in a positive value for each point as indicated by the "(+)" symbol shown
adjacent to the points. Since both points have the same algebraic sign for the
expression A*x+B*y+C, the pixel
505 in question is preferably not illuminated
for the straight line segment
205 shown in FIG. 6C.
Evaluating the expression A*x+B*y+C at the two points V
1 and V
2
results in a positive value for point V
1 as indicated by the "(+)" symbol
shown adjacent to point V
1 and in a negative value for point V
2 as
indicated by the "(-)" symbol shown adjacent to point V
2. Since the points
have different algebraic signs for the expression A*x+B*y +C, the pixel
505
in question is illuminated for the straight line segment
205 shown in FIG. 6D.
Evaluating the expression A*x+B*y+C at the two points V
1 and V
2
results in a negative value for each point as indicated by the "(-)" symbol shown
adjacent to the points. Since both points have the same algebraic sign for the
expression A*x+B*y+C, the pixel
505 in question is preferably not illuminated
for the straight line segment
205 shown in FIG. 6E.
In FIG. 6F, a horizontal offset-grid line
675 passes through the center
650 of the pixel
505. The horizontal offset-grid line
675
is formed by offsetting a lower grid line
685 of the pixel
505 up
from its nominal position by ½ its height
645. This movement is shown
by second offset
677. The lower grid line
685 is co-linear with the
lower edge
665 of the pixel
505. The horizontal offset-grid line
675 intersects the pixel
505 boundaries at lower and upper points
V
3 and V
4. In order to determine mathematically whether or not to
illuminate the pixel
505, it is only necessary to evaluate the expression
A*x+B*y+C at each of the two points V
3 and V
4 if the decision had
not already been to illuminate the pixel
505 in the steps described in connection
with FIGS. 6C-6E. FIGS. 6G-6I illustrate the results for three separate conditions
of straight line segments
205 passing through the pixel
505.
Evaluating the expression A*x+B*y+C at the two points V
3 and V
4
results in a positive value for each point as indicated by the "(+)" symbol shown
adjacent to the points. Since both points have the same algebraic sign for the
expression A*x+B*y+C, the pixel
505 in question is preferably not illuminated
for the straight line segment
205 shown in FIG. 6G.
Evaluating the expression A*x+B*y+C at the two points V
3 and V
4
results in a positive value for point V
3 as indicated by the "(+)" symbol
shown adjacent to point V
3 and in a negative value for point V
4 as
indicated by the "(-)" symbol shown adjacent to point V
4. Since the points
have different algebraic signs for the expression A*x+B*y +C, the pixel
505
in question is illuminated for the straight line segment
205 shown in FIG. 6H.
Evaluating the expression A*x+B*y+C at the two points V
3 and V
4
results in a negative value for each point as indicated by the "(-)" symbol shown
adjacent to the points. Since both points have the same algebraic sign for the
expression A*x+B*y+C, the pixel
505 in question is preferably not illuminated
for the straight line segment
205 shown in FIG. 6I.
In any of the above cases, if the evaluation of the expression A*x+B*y+C results
in opposite algebraic signs whether in an evaluation for the pair of points V
1
and V
2 or the pair of points V
3 and V
4, the pixel
505
in question is illuminated regardless of the results of the evaluation of the other
pair of points. Thus, if one pair of points is evaluated and found to have differing
algebraic signs, it is not necessary to evaluate the two remaining points.
If any two of the points V
1, V
2, V
3, V
4 are found
to have different algebraic points, the pixel
505 in question is illuminated.
Computation of algebraic signs for successive points does not need to continued
after one differing sign is found. The situation of FIG. 6J corresponds to the
straight line segment
205 crossing any part of the area of the pixel
505
enclosed by the dotted lines connecting points V
1, V
2, V
3, V
4.
FIG. 7 is an illustrative flow chart of a method for selecting pixels
505
to activate in rendering a straight line segment
205 as described in various
representative embodiments consistent with the teachings of the invention.
In block
705, a control variable is set equal to a preselected value,
which
could be for example the number "0". Block
705 then transfers control to
block
710.
In block
710, the pixel
505 is marked as other than selected. Block
710, then transfers control to block
715.
In block
715, when the pixel
505 is marked as other than selected,
block
710 transfers control to block
720. Otherwise, block
715
terminates the process.
In block
720, the expression A*x+B*y+C is computed for one of the pixel
grid mid-points V
1, V
2, V
3, V
4. Block
720, then
transfers control to block
725.
In block
725, when the control variable is equal to the preselected value,
block
725 transfers control to block
730. Otherwise, block
725
transfers control to block
740.
In block
730, the algebraic sign of the result of the computation of the
expression A*x+B*y+C obtained in block
720 is stored. Block
730 then
transfers control to block
735.
In block
735, the value of the control variable is changed from its preselected
value to some other value, which could be for example the number "1". Block
735
then transfers control to block
750.
In block
740, when the algebraic sign of the result of the computation
of the expression A*x+B*y+C obtained in block
720 differs from that stored
in block
730, block
740 transfers control to block
745. Otherwise,
block
740 transfers control to block
750.
In block
745, the pixel
505 is marked as selected. Block
745
then transfers control to block
750.
In block
750, when there are remaining pixel grid points V
1, V
2,
V
3, V
4 for which in block
720 the expression A*x+B*y+C have
not been computed, block
750 transfers control to block
715. Otherwise,
block
750 terminates the process.
A third objective is to identify which screen regions
125 will be activated
in displaying the straight line segment
205 on the screen
110 of
the monitor
105 for cases in which the line has a width. Some pixels may
be illuminated within adjoining screen regions
125 due to the width of the
line. However, only those screen regions
125 through which the straight
line segment
205 including the width of the line passes will need to be
activated. All others can be ignored in the display of that straight line segment
205. It should be noted that while the following discussion is in terms
of straight line segments, the techniques disclosed are also applicable to points
that are displayed with a width. Further, all references to width refer to dimensions
in the minor axis direction.
FIG. 8 is a drawing of yet another screen space
115 of the computer graphics
display system
100 as described in various representative embodiments consistent
with the teachings of the invention. The straight line segment
205 of FIG.
8 has first and second end points P
1,P
2 and a width which is indicated
by upper and lower line boundaries
811,
812.
In FIG. 8, the bounding box
210 is defined similar to that defined with
respect to FIG. 2. The straight line segment
205 is conceptually defined
on the screen space
115 by the first and second end points P
1,P
2
wherein the bounding box has first and second corners
215,
220. The
first corner
215 of the bounding box
210 is defined by the coordinates
(min(X
1,X
2), min(Y
1,Y
2)) and (max(X
1,X
2),
max(Y
1,Y
2)), where min(a,b) returns the minimum of the two values
a and b, and max(a,b) returns the maximum of the two values a and b. The bounding
box
210 is aligned with a major and a minor axis
821,
822 wherein
the major axis
821 is identified as parallel to the longer of two adjacent
sides of the bounding box
210 and the minor axis
822 is identified
as parallel to the other side of the bounding box
210. The rectangular grid
is located on the boundaries of the screen regions
125. The extent of this
grid should be large enough to include the bounding box
210.
Note that in the example of FIG. 8, first end point P
1 and first corner
215 are coincident, and second end point P
2 and second corner
220
are coincident. However, had the slope of the straight line segment
205
been negative instead of positive as in FIG. 8, the first corner
215 would
have still been at the lower left hand corner of the bounding box
210, and
the second corner
220 would have still been at the upper right hand corner
of the bounding box
210 while the first and second end points P
1,P
2
would have been located respectively at the upper left hand corner and lower right
hand corners of the bounding box
210.
Due to the width of the straight line segment
205 in FIG. 8, the bounding
box
210 just obtained above will not include the screen region
125
in region column C
1 and region row R
5, the screen region
125
in region column C
2 and region row R
5, the screen region
125
in region column C
3 and region row R
2, nor the screen region
125
in region column C
4 and region row R
2. Thus, if some adjustment is
not made, those screen regions
125 will not be activated and the line
205
will not be displayed appropriately.
FIG. 9 is a drawing of adjacent screen regions
125 in the screen space
115 of the computer graphics display system
100 as described in various
representative embodiments consistent with the teachings of the invention. This
figure is a magnified view of a portion of FIG. 8 comprising the screen regions
125 located at region row/column R
2,C
3; region row/column
R
2,C
4; region row/column R
3,C
3; and region row/column
R
3,C
4. A line-width
931 of the straight line segment
205
is shown in FIG. 9, as well as a one-half-line width
932. Line-upper and
line-lower boundaries
811,
812 are shown around the centerline
950
of straight line segment
205. As can be seen from FIG. 9, the width of straight
line segment
205 extends the straight line segment
205 into screen
regions
125 located at region row/column R
2,C
3 and region
row/column R
2,C
4.
FIG. 10 is another drawing of adjacent screen regions
125 in the screen
space
115 of the computer graphics display system
100 as described
in various representative embodiments consistent with the teachings of the invention.
FIG. 10 shows the same area of the screen space
115 as found in FIG. 9 which
once again is a magnified view of a portion of FIG. 8 comprising the screen regions
125 located at region row/column R
2,C
3; region row/column
R
2,C
4; region row/column R
3,C
3; and region row/column
R
3,C
4. In FIG. 10, the rectangular grid
130 around pixels
505 is moved downward along the minor axis
822 by an amount equal
to that of one-half-line-width
932 as shown by dotted lines indicated as
horizontal grid lines
132.
The expression A*x+B*y+C is then computed for region row/column R
2,C
4
at each of the shifted rectangular grid corners SG
1, SG
2, SG
3,
and SG
4 one at a time for the new rectangular grid
130 location to
determine the algebraic sign of the expression. Should the sign of one of the results
of this computation differ from one of those previously computed, the computation
is terminated and the screen region
125 is marked as activated in creating
the straight line segment
205. Should all four corners have the same algebraic
signs, unless otherwise activated the screen region
125 will preferably
not be active in displaying the straight line segment
205. For the example
of FIG. 10, the expression A*x+B*y+C has negative algebraic signs at shifted rectangular
grid corners SG
2 and SG
4, whereas it has positive algebraic signs
at shifted rectangular grid corders SG
1 and SG
3. Thus, the screen
region
125 at region row/column R
2,C
4 is activated in rendering
the straight line segment
205.
Repeating the computation of the expression A*x+B*y+C for region row/column
R
2,C
3 at each of the shifted rectangular grid corners SG
1,
SG
3, SG
5, and SG
6 one at a time for the new rectangular grid
130 location to determine the algebraic sign of the expression. Should the
sign of one of the results of this computation differ from one of those previously
computed, the computation is terminated and the screen region
125 is marked
as activated in creating the straight line segment
205. Should all four
corners have the same algebraic signs, unless otherwise activated the screen region
125 will preferably not be active in displaying the straight line segment
205. For the example of FIG. 10, the expression A*x+B*y+C has positive algebraic
signs at shifted rectangular grid corners SG
1, SG
2, SG
3, and
SG
4. Thus, the screen region
125
