Language selection

Search

Patent 1312683 Summary

Third-party information liability

Some of the information on this Web page has been provided by external sources. The Government of Canada is not responsible for the accuracy, reliability or currency of the information supplied by external sources. Users wishing to rely upon this information should consult directly with the source of the information. Content provided by external sources is not subject to official languages, privacy and accessibility requirements.

Claims and Abstract availability

Any discrepancies in the text and image of the Claims and Abstract are due to differing posting times. Text of the Claims and Abstract are posted:

  • At the time the application is open to public inspection;
  • At the time of issue of the patent (grant).
(12) Patent: (11) CA 1312683
(21) Application Number: 586151
(54) English Title: METHOD OF DRAWING IN GRAPHICS RENDERING SYSTEM
(54) French Title: METHODE DE DESSIN POUR SYSTEME GRAPHIQUE
Status: Deemed expired
Bibliographic Data
(52) Canadian Patent Classification (CPC):
  • 375/21
(51) International Patent Classification (IPC):
  • G09G 1/16 (2006.01)
  • G06T 11/20 (2006.01)
  • G09G 5/393 (2006.01)
(72) Inventors :
  • KELLEHER BRIAN (United States of America)
  • FURLONG, THOMAS C. (United States of America)
(73) Owners :
  • DIGITAL EQUIPMENT CORPORATION (United States of America)
  • KELLEHER BRIAN (Not Available)
  • FURLONG, THOMAS C. (Not Available)
(71) Applicants :
(74) Agent: SMART & BIGGAR
(74) Associate agent:
(45) Issued: 1993-01-12
(22) Filed Date: 1988-12-16
Availability of licence: N/A
(25) Language of filing: English

Patent Cooperation Treaty (PCT): No

(30) Application Priority Data:
Application No. Country/Territory Date
135,773 United States of America 1987-12-18

Abstracts

English Abstract




ABSTRACT OF THE INVENTION

Method and means for drawing a convex geometric
figure to framebuffer storage sequentially
addressable as a plurality of update arrays of
determined origins which tile the framebuffer. An
array comprises pixel storage sites, each specifiable
by an offset from array origin. The sites are
concurrently updatable. A figure is specified as a
set of directed lines; the line segments between
mutual intersections comprise the figure boundary;
the segments perambulate the boundary in a single
sense.

For an update array, concurrently for each pixel
site, and concurrently for each directed line, the
sidedness of the pixel is evaluated with respect to
the line to derive a one-bit line discriminant
signal. For each site, the line discriminant signals
are ANDed to derive a result discriminant signal; a
first value specifying outsidedness of the pixel with
respect to the figure prevents writing to the site.
The process is repeated for further arrays to tile
the figure to be drawn.


Claims

Note: Claims are shown in the official language in which they were submitted.


- 23 -
61051-2245

THE EMBODIMENTS OF THE INVENTION IN WHICH AN EXCLUSIVE
PROPERTY OR PRIVILEGE IS CLAIMED ARE DEFINED AS FOLLOWS:

1. In a graphics system having framebuffer storage organized for
storing signals specifying an array of pixels (x,y) of an X x Y rester framebuffer,
said storage being sequentially addressable as a plurality of framebuffer pixel
update arrays which tile the framebuffer,
each said update array having a determined origin with respect to said
framebuffer and comprising storage sites for specifications of a plurality of
contiguously positioned framebuffer pixels, each said storage site being
specifiable by an offset with respect to said update array origin, the pixel
specifications of a said update array being concurrently updatable In a parallelmemory transaction,
a method of selecting framebuffer pixels for writing while drawing a
geometric figure to said framebuffer, comprising the steps:
(1) specifying a directed line with respect to said framebuffer,
wherein at least a segment of said directed line defines a boundary of
said figure;
(2) accessing a said update array,
(3) concurrently for all pixel sites of said accessed update array,
(3a) evaluating the relative position of the framebuffer pixel
whose specification is stored at said pixel site with respect to said
directed line to derive a one-bit discriminant signal for each said
accessed array pixel site, and
(3b) using a first value of said discriminant signal to
prevent writing to said accessed array pixel site.

2. The method of claim 1, including repeating steps 1-3 for further update
arrays to tile said figure to be drawn.

61051-245

3. The method of claim 1,
said step (1 ) including specifying said figure to be drawn to said
framebuffer storage by specifying with respect to said framebuffer a set of
directed lines such that the segments of said lines between their mutual
intersections comprise the boundary of said figure, the directions of said linesbeing specified such that said segments perambulate said boundary in a single
sense,
said evaluating step (3a) being performed concurrently for all pixel sites
of said accessed update array, concurrently for each directed line of said set,
to derive for each accessed update array pixel site a discriminant signal
corresponding to each directed line of said set;
said step (3b) including, concurrently for all pixel sites of said accessed
update array, ANDing said discriminant signals for said set of directed lines toderive a result discriminant signal, and using a first value of said result
discriminant signal, indicating that the framebuffer pixel is outside the figure to
be drawn, to prevent writing to said accessed array pixel site.

4. The method of claim 3, including repeating steps 1-3 for further update
arrays to tile said figure to be drawn.

5. The method of claim 1,
said step (1) Including decomposing said figure to be drawn into a set
of convex geometric figures, and for each said convex geometric figure, specifying
with respect to said framebuffer a set of directed lines such that the segments
of said lines between their mutual intersections comprise the boundary of said
figure, the directions of said lines being specified such that said segments
perambulate said boundary in a single sense;
said evaluating step (3a) being performed concurrently for all pixel sites
of said accessed update array, concurrently for each directed line of said set,
lo derive for each accessed update array pixel site a discriminant signal
corresponding to each directed line of said set;

- 25 - 61051-2245
said step (3b) including, concurrently for all pixel sites of said accessed
update array, ANDing said discriminant signals for said set of directed lines toderive a result discriminant signal, and using a first value of said result
discriminant signal, indicating that the framebuffer pixel is outside the figure to
be drawn, to prevent writing to said accessed array pixel site;
said method further including the steps of
(4) repeating steps 1-3 for further arrays to tile said convex geometric
figure; and
(5) repeating steps 1-4 for each said convex geometric figure into which
said figure to be drawn was decomposed.

6. The method of claim 1,
each said update array having a determined origin (originx, originy) with
respect to said framebuffer, each said storage site being specifiable by an offset
(offsetx, offsety) with repect to said update array origin;
said step (1) including
(1a) specifying said directed line with respect to said framebuffer
as x1, y1), (x2, y2); and
(1b) calculating for said line (x2 - x1). y1 - (y2 - y1). x1=C;
said step (2) including calculating for said directed line and array update
array (x2 - x1)- originy - (y2 - y1)- originx = B;
said step (3a) including
calculating (x2 - x1). offsety - (y2 - y1).offsetx = A; and
comparing A with (B + C) to derive said one-bit discriminant signal
for each said accessed array pixel site.

7. The method of claim 6, said step (1) including specifying said figure to be
drawn to said framebuffer storage by specifying with respect to said framebuffera set of directed lines such that the segments of said lines between their mutual
intersections comprise the boundary of said figure, the directions of said linesbeing specified such that said segments perambulate said boundary in a single
sense, specifying each line as (x1, y1),(x2, y2);

- 26 -
61051-2245

said step (2) including, for each directed line of said
set, calculating {X2-X1). Y1-{Y2-Y1).X1=C;
said evaluating step (3a) being performed concurrently
for all pixel sites of said accessed update array, concurrently
for each directed line of said set, to derive for each accessed
update array pixel site a discriminant signal corresponding to
each directed line of said set;
said step (3b) including, concurrently for all pixel
sites of said accessed update array, ANDing said discriminant
signals for said set of directed lines to derive a result
discriminant signal, and using a first value of said result
discriminant signal, indicating that the framebuffer pixel is
outside the figure to be drawn, to prevent writing to said
accessed array pixel site.

8. The method of claim 7, including repeating steps 1-3
for further update arrays to tile said figure to be drawn.

9. A graphics system, comprising:
framebuffer storage organized for storing signals
specifying an array of pixels (x,y) of an X x Y raster frame-
buffer; and
pixel selecting means for selecting framebuffer pixels
for drawing a specified geometric figure;
wherein said storage is sequentially addressable as a
plurality of framebuffer pixel update arrays which tile the
framebuffer, each said update array having a determined origin
with respect to said framebuffer and comprising storage sites
for specifications of a plurality of contiguously positioned


- 27 -
61051-2245

framebuffer pixels, each said storage site being specifiable by
an offset with respect to said update array origin, the pixel
specifications of a said update array being concurrently updat-
able in a parallel memory transaction;
said pixel selecting means including:
addressing means for accessing a said update array;
write enable means for enabling and preventing writing
of a said storage site in said accessed update array; and
means for evaluating, concurrently for all pixel sites
of said accessed update array, the relative position of the
framebuffer pixel whose specification is stored at said pixel
site with respect to a directed line specified with respect to
said framebuffer, and for deriving a one-bit discriminant signal
for each said accessed update array pixel site;
said write enable means being responsive to a first
value of said discriminant signal for preventing writing to said
accessed array pixel site.

10. The graphics subsystem of claim 9, wherein said pixel
selecting means includes means for repeatedly accessing further
update arrays to tile said figure to be drawn.

11. The graphics subsystem of claim 9, further including
means for specifying said figure to be drawn to said framebuffer
storage by specifying with respect to said framebuffer a set of
directed lines such that the segments of said lines between
their mutual intersections comprise the boundary of said figure,
the directions of said lines being specified such that said
segments perambulate said boundary in a single sense,


- 28 -
61051-2245


said evaluating means including means for evaluating,
concurrently for all pixel sites of said accessed update array,
concurrently for each directed line of said set, the relative
position of the framebuffer pixel whose specification is stored
at said pixel site with respect to the directed line to derive
for each accessed update array pixel site a discriminant signal
corresponding to each directed line of said set;
said evaluating means further including means for,
concurrently for all pixel sites of said accessed update array,
ANDing said discriminant signals for said set of directed lines
to derive a result discriminant signal;
said write enabling means using a first value of said
result discriminant signal, indicating that the framebuffer pixel
is outside the figure to be drawn, to prevent writing to said
accessed array pixel site.

12. The graphics subsystem of claim 11, wherein said pixel
selecting means includes means for repeatedly accessing further
update arrays to tile said figure to be drawn.

13. The graphics subsystem of claim 9, further including
means for decomposing said figure to be drawn into a set of convex
geometric figures, and for each said convex geometric figure,
specifying with respect to said framebuffer a set of directed
lines such that the segments of said lines between their mutual
intersections comprise the boundary of said figure, the directions
of said lines being specified such that said segments perambulate
said boundary in a single sense;


- 29 -
61051-2245


said evaluating means including means for evaluating,
concurrently for all pixel sites of said accessed update array,
concurrently for each directed line of said set, the relative
position of the framebuffer pixel whose specification is stored
at said pixel site with respect to the directed line to derive
for each accessed update array pixel site a discriminant signal
corresponding to each directed line of said set;
said evaluating means further including means for,
concurrently for all pixel sites of said accessed update array,
ANDing said discriminant signals for said set of directed lines
to derive a result discriminant signal;
said write enabling means using a first value of said
result discriminant signal, indicating that the framebuffer pixel
is outside the figure to be drawn, to prevent writing to said
accessed array pixel site;
said pixel selecting means including control means for
repeatedly accessing further update arrays to tile said figure
to be drawn and for sequentially processing each said convex
geometric figure into which said figure to be drawn was
decomposed.


Description

Note: Descriptions are shown in the official language in which they were submitted.






METHOD OF DRAWING IN
GRAPHICS RENDERING SYSTEM

This invention relates to single-instruction
multiple-data (SIMD) graphics systems, and in
particular to a method and means of performing
graphics rendering operations in such a system.

BACKGROUND OF THE INVENTION
In a data processing system with graphics capability,
a system processor executing a graphics application
program outputs signals representing matter to be
displayed; this representation is generally abstract
and concise in form. Such form is not suitable for
the direct control of a display monitor; it is
necessary to transform the relatively abstract
representation into a representation which can be
used to control the display. Such transformation is
referred to as graphics rendering; in a system using
a raster display monitor, the information comprising
the transformed representation is referred to as a
framebuffer. Signals specifying tha framebuffer
information ar~ stored in framebuffer storage.

The framebuffer representation must be frequently
updated, by rewriting its stored spPcification in
part or completely, either to reflect dynamic aspects
of the display; or to pro~ide for the display of
images generated from a different application

~ ~26~
--2--
program. Each updating operation requires access to
the memory in which the specification of the
framebuffer is stored; generally a large number of
locations in the framebuf~er storage must be accessed
for each updating operation. The speed of rendering
the display is limited by the requirement for
graphics memory access; the greater the number of
bits in the graphics memory tframebuffer storage)
that can be read or written in a given time period
lo (the "memory bandwidth"), the better the graphics
performance.

Graphics memory bandwidth depends on the number of
memory packages (chips) comprising the graphics
memory, multiplied by the number of i/o pins per
package; the product is the maximum possible number
of bits that can be accessed in ona memory
transaction. Bandwidth is then a function of this
maximum number and of the time required for a memory
transaction.

Many conventional graphics rendering operations are
carried out by a series of steps that are highly
incremental in nature; that is, the value of a
particular framebuffer pixel cannot be updated (and
the framebuffer storage rewritten) until the updated
value of an adjacent framebuffer pixel is known.
Framebuffer updating carried out by means of such
incremental operations reguires frequent memory
transactions, each involving a relatively small
number of bits. The rendering performance of such a
yraphics system can be improved by decreasing the
time reguired for a memory transaction, but will not
be much improved by increasing the number of bits
which can be addressed in a transaction. If
increased memory bandwidth is to improve the graphics
performance, means must be provided for making

~ `3 ~ 3
--3--
efficient use of the bandwidth during gr~phics
rendering operations.

It is an object of the present invention to provide,
for framebuffer storage that is accessed as
5 framebuffer pixel arrays, a graphics rendering
operation that makes efficient use of the increased
bandwidth provided by such framebuffer memory
architecture. In particular, it is an object to
provide means and method for selecting from an
addressed pixel array those pixels to which is mapped
a geometric figure to be drawn to the framebuffer.

BRIEF DESCRIPTION OF THE INVENTION
The present invention is employed in a graphics
subsystem having framebuffer storage organized for
storing signals specifying the pixels (x,y) of a
X x Y raster framebuffer. The storage is
segu~ntially addressable as a plurality of
framebuffer pixel update arrays, the set of update
arrays tiling the framebuffer.

Each update array has a determined origin with
respect to the framebuffer and comprises storage
sites for specifications of a plurality of
contiguously positioned framebuffer pixels. Each
storage site is specifiable by an offset with respect
to the update array origin, the pixel specifications
of an update array being concurrently updatable in a
parallel memory transaction.

According to the invention, a method is provided for
selecting framebuffer pixels for drawing, comprising
the steps of specifying a directed line with respect
to the framebuffer; accessing an update array;
concurrently for all pixel sites of the accessed
array (a~ evaluating the sidedness of the

framebuffer pixel whose specification is stored at
the pixel site with respect to the directed line to
derive a one-bit discriminant signal for each
accessed array pixel siter and (b) using a first
value of the discriminant signal tG prevent writing
to the accessed array pixel site.

In preferred embodiments, the update array origin is
specified as (originX, originy) with respect to said
framebuffer, and the storage sites are specified as
(offsetx, offsety) with respect to the update array
origin. A method of drawing a convex geometric
figure to the framebuffer storage comprises the
steps: specifying a figure to be drawn to the
framebuffer storage by specifying with respect to the
framebuffer a set of directed lines such that the
segments of the lines between their mutual
intersections comprise the boundary of the figure,
the directions of the lines being specified such that
the segments perambulate the boundary in a single
sense, speciying each line as (xl, Yl), (x2, Y2);
for each directed line of the set, calculating
(X2 ~ Xl) Yl ~ (Y2 - y1) xl = C; accessing an update
array; calculating for the array and for each line
~X2 ~ Xl)~riginy ~ (Y2~Yl) originX = B; concurrently
for each line, and concurrently for each pixel site
of the accessed array, (a) calculating
(X2 ~ X1) offsety - (Y2 ~ yl)-offsetx = A,
(b) comparing A with (B + C) to derive a one-bit
discriminant signal for each accessed array pixel
site with respect to a line, (c) for each pixel site
ANDing the discriminant signals for the set of
directed lines to derive a result discriminant
signal; (d) using a first value of the result
discriminant signal specifying outsidedness of the
framebuffer pixel with respect to the ~igure to be
drawn to prevent writing of the pixel specification

~ ?~ ?~
--5--
stored at the access array pixel site; and repeating
the previous steps with respect to further update
arrays to tile the figure to be drawn.

Other objects, features and advantages will appear
5 from the following description of a preferred
embodiment, together with the drawing, in which:

BRIEF DESCRIPTION OF THE DR~WING
Fig. 1 is a block diagram of a data processing system
in which the invention is employed;

Fig. 2 is a block diagram of the memory chip bank of
the data processing system of Fig. l;

Fig. 3 is a conceptual showing of a framebuffer
specified in the memory chip bank of Fig. 2, and a
pixel thereof;

Fig. 4 is an illustrative showing of the mapping
between the locations of a memory chip bank and a
conceptual framebuffer;

Fig. 5 is a block diagram of a memory controller
according to the invention;

Fig. 6 illustrates a concept employed in the
addressing means and method of the invention;

Fig. 7 shows a geometric figure represented in terms
of the concept illustrated in Fig. 6;

Fig. 8 shows a geometric figure tiled by a plurality
of seguentially addressed framebuffer pixel arrays;

Fig. 9 shows a geometric figure mapped to a

-6- ~3~3~ ~

particular framebuffer pixel array for generating an
address for a next array;

Fig. 10 shows a geometric figure mapped to a
particular pixel array with an additional addressing
condition imposed;

Fig. 11 is a block diagram of an element of Fig. 5.

DETAILED DESCRIPTION OF THE INVENTION
Referring now to the drawing, and in particular to
Fig. 1, a graphics subsystem 10 (memory module) is
connected by processor bus 14 to port 52 of a
processor 50. Bus 14 carries signals (specifying
data or address) between processor 50 and subsystem
lO,and is connected to subsystem 10 through a bus
interface 12. A subsystem data bus 16 (module bus)
is connected to interface 12. Graphics subsystem 10
provides a memory comprising a bank 20 of K
conventional two-port vidso random access memory
chips 24 desirably arranged in a chip array A x B =
K. Each chip 2~ (memory element) provides an equal
plurality of storage locations, each location being
addressable relative to the chip origin. The random
access ports of the chips of bank 20 are connected
through a controller 18 to subsystem bus 16. The
serial output ports of the chips of bank 20 are
connected by connector 150 to graphics output
circuitry 22, which is of conventional design and
need not be described; signals output from circuitry
22 are connected to a conventional raster color
display monitor 23.

Processor 50 executes a graphics application program,
details of which are not pertinent to the present
invention, which results in the specification of
matter, such as geometric figures, to be displayed.

The images to be displayed are specified by processor
50 in a relatively abstract and concise form, which
cannot be directly used to control the display
monitor. The specification must be converted to a
suitable form, which for a raster display monitor is
referred to as a framebuffer comprising an ordered
array of framebuffer pixels, each corresponding to a
display pixel of the display screen~ Such conversion
is referred to as rendering. In the system of
Fig. 1, the rendering operations are carried out by
graphics subsystem 10.

Still referring to Fig. 1, interface 12 comprises
means for performing the usual functions of a bus
interface, such as bus monitoring and support, and
bus protocol. For the particular function of
interfacing between bus 14 and the graphics subsystem
10, interface 12 additionally provides timing means
for controller 18, for output circuitry 22, for
memory bank ~0, and for the display monitor; means
for controlling subsystem bus 16; and certain
computational means whose purpose will become clear
in what follows.

Memory module addressing means 17, responsive to
signals from controller 18, provid~s location address
signals 27 to bank 20. It should be understood that
although for clarity of description memory module
addressing means is shown in Fig. 1 as separate from
interface 12 and controller 18, this arrangement is
not significant. The necessary addressing functions
may be provided by circuitry otherwise distributed,
for example, distributed between interface 12 and
controller 1~.

The video RAM chips of bank 20 are disposed as a
A x B = K chip array, for example, referring now to

c~
--8--
Fig. 2, a (A = 5) x (B = 4) array of K = 20 chips 24,
each chip 24 (identified ~y its chip array position
as (a,b)) having an 8-bit parallel i/o path to
controller 18. Other chip array dimensions may also
be employed, for example, (A = 4) x (B = 4) with an
8-bit parallel i/o path~ or (A = 20) x (B = 1).
Controller 18 has the capability of accessing in
parallel (path width) x A x B bits, or for the
embodiment of Fig. 2, (8 x 5 x 4) = 160 bits.

The set of corresponding locations in the K chips
(a,b) specified by a location address from module
addressing means 17 comprises an addressed locati~n
array.

In a system using a raster display, the framebuffer
storage (and the corresponding framebuffer, which is
conceptual rather than physical) of a graphics
subsystem is mapped to the display screen in terms of
pixels (picture elements). The xaster display screen
comprises a rectangular array of X x Y display pixels
(x,y). At any particular time, each display pixel
displays a color specified by a color value, signals
specifying the color value are stored in the
framebuffer storage at the (x,y) position of the
framebuffer pixel corresponding to the display pixel.
The display is refreshed by output circuitry such as
circuitry 22 in Fig. 1, which cyclically reads
signals from the framebuffer storage, interprets the
signals, and controls display monitor 23
appropriately to display corresponding colors in the
display pixels, all in a manner well understood in
the art. Changes in the display are made by updating
the specifications of color values in framebuffer
storage; on the next refresh cycle these changes are
represented by corresponding changes on the display
screen.

_9_ ~ 3 ~ J
Conceptually, the bits comprising a framebuffer pixel
x,y (specifying the color value of the display pixel
x, y) are regarded as being all stored at the pixel
position in the framebuffer, which is regarded as a
three-dimensional construct. Referring now to the
conceptual showing of ~iy. 3, a framebuffer 26
comprises an array, X framebuffer pixels across and Y
framebuffer pixels vertically, corresponding to the
X x Y display pixels of the display; at the specific
framebuffer position (x,y) the framebuffer has n bits
comprising a framebuffer pixel. The framebuffer
pixel is said to have depth n.

Module addressing means 17 and controller 18 control
the storage of signals in the A x B video RAM chips
24 of bank 20 in addressed array locations such that
signals specifying certain adjacent framebuffer
pixels can be accessed in bank 20 in parallel through
controller 18 responsive to a single location address
relative to chip origin, supplied in parallel to all
chips from module addressing means 17. In
particular, the framebuffer pixel signals are so
stored that an update array of W x H pixels can be
accessed in parallel, the update array being so
specified that the entire X x Y framebuffer (and
display) can be tiled by a plurality of such W x H
update arrays having determined origins. Each update
array can be identified by an array origin
identifier. The dimensions W, H of the update array
need not be equal to the dimensions A, B of the chip
array, but in the simplest case W = A and H = B.

The connections 150 between the serial output ports
of chips 24 and video output circuitry 22 determine
the mapping between chips 24 and the display screen;
that is, the framebuffer pixels in memory 20, as
located by the mapping between controller 18 and

-10~
chips 24, must be serially accessed in raster order
of (x,y) to refresh the display.

Referring now to Fig. 4, by way of illustration the
mapping is shown between a conceptual three-
dimensional framebuffer and a corresponding physicalchip bank laid out on a plane. (The particular
numbers employed are not those of a real graphics
subsystem but have been chosen to provide a simple
illustrative example.) An exemplary framebuffer 26-E
has 100 framebuffer pixels (X = lO) x (Y = 10) as
shown, each pixel having an exemplary depth of n = 4
bits. The signals representing the framebuffer are
stored physically in chip bank 20-E comprising a
(A = 5) x (B = 5) chip array (K = 25 chips),
controlled by a controller (not shown) to provide
4-bit parallel access from the controller to each
chip (a,b) in chip array 20-E. It is assumed that
four 4-bit pixels can be stored in each chip. Thus
chip (a=1, b=l) of bank 20-E stores the four bits of
pixel (x=1, y=l) in its first location; pixel (x=2,
y=1) is stored in the corresponding first location of
chip (a=2, b=1). These two pixels are in the first
update array, and can be accessed in parallel because
they are in different chips in the chip array and are
in corresponding locations in thP respective chips.
However framebuffer pixel (x=1, y=6) is stored in the
third location of chip (a=1, b=l) of bank 20-E, 50
that it cannot be accessed in parallel with pixel
(x=1, y=l). It is thus seen that framebuffer 26-E is
tiled by four 5x5 update arrays of framebuffer pixels
having array origins at (1,1), (6,1), (1,6) and
(6,6), and that the signals representing all the
framebuffer pixels of an update array, stored in the
graphics subsystem memory, will be concurrently
accessed in parallel in a single memory transaction,
specified by a single location address from

-11- '~3~.2$6~
addressing means 17. In an actual graphics system of
interest, many more than four update arrays are
required to tile the display. The framebuffer pixels
are stored in a set of contiguous storage locations
within chips 24-E.

Referring to Fig. 5, controller 18 provides state
machines 100 for controlling the state of the
controller; state machines 100 receive timing signals
from interface 12 on lines 80. Controller 18 further
provides read/write enable generating means 102,
which outputs to each of chips 24 oE bank 20
read/write enable signals on lines 88, in the course
of a controller graphics rendering operation. In the
embodiment having a (A = 5) x (B = 4) chip bank 20
with 8-bit parallel paths, data is transmitted on 40-
bit parallel path 84 between contro ler 18 and
subsystem bus 16; data is transmitted on 160-bit
parallel path 86 between controller 18 and memory
bank 20.

For each memory chip of bank 20, con~roller 18
provides at 104 an internal logical processor for the
execution of yraphics operations, the processors of
104 operating in parallel (concurrently). Such
graphics operations include, for example, writing a
geometrical figure to the framebuffer, moving a
~igure from one part of the framebuffer to another
part (which reguires both portions of the framebuffer
to be redrawn), drawing a line, and the like. In
addition, three further logical processors 105 are
provided, which operate in parallel with processors
104, as will be described.

The framebuffer is tiled by a number of updatad
arrays having determined origins. A figure to be

$~i
-12-
written to the framebuffer storage in general is
mapped to only a subset of the update arrays.
The operation of writing a line or geometric figure
to the framebuffer comprises two basic steps. First,
it is necessary to determine which update arrays
should be addressed to tile the figure, and to
address each such array in turn; second, it is
necessary to determine which pixel specifications
within an addressed update array must be written and
to write such pixPl specifications. Means and
methods for carrying out each of these steps will now
be described.

The basis of the described operations is the use of a
half-space representation. As seen in Fig. 6, a
directed line divides a plane into left and right
half-spaces. A half-space evaluation decides on
which side of a directed line any point (in a plane)
lies. In Fig. 6 all points shown as "+" are in the
left half-space, all points shown as "-" are in the
right half-space, with respect to the directed line.
The line has infinite length.

For a given point, evaluation of its sidedness with
respect to a given line is based on the general
equation of a line,
(1) y = mx + b
where m is the slope of the line and b is the y-
intercept. Equation (1) is true for values of x and
y on the line; y > mx + b for points on one side of
the line; and y < mx + b for points on the other side
of the line. For a line passing through two
specified points (xl, Y1) and (x2, Y2)~ the constants
for the line equation are m = dy/dx, and b = (Yl ~
(dy/dx~xl), where dy = Y2 ~ Y1~ and dx = x2 - xl.
Therefore, to evaluate a half-space defined by two




.

~ C?~ qr,i ~ ë~

points specifying ~he line, equation (2) mu~t be
evaluated:
~ 2) y = (dy/dx)x -~ Yl - (dy~dx)xl.
The order in which the points (xl, Y1) and (x2, Y2)
are given specifies the direction of the line.

Equation (2) is represented in the real number
system. In the present operation, the equation must
be evaluated for the specific locations of the
framebuffer pixels, to decide whether a specific
pixel is inside or outside a figure to be drawn, the
figure being composed of a plurality of directed
lines. From equation (2) is derived equation (3):
(3) dx-y - dy-x - dx yl + dy xl = 0,
a form which advantageously avoid~ divide operations.

The left side of equation (3) is 0 for (x,y) on the
lin~, positive for (x,y) on one side of the line, and
negative for (x,y) on the other side of the line.
For the purpose of providing circuitry (processors
104, 10~) comprising relatively ~ew components but
capable of performing the evaluation rapidly,
equation (3) is further modified by representing the
locations of the pixels within the update array in
terms of array origin (originX, originy) and pixel
offset (site offset) within the array (offsetx,
offsety; x = originX + offsetx, y = originy +
offsety), to arrive at equation (4):
(4a) dx-offsety - dy offsetx =
(4b) -dx-originy + dy-originx +
(4c) dx y1 ~ dY-X1-

The form of equation (4) is advantageous because it
minimizes computation and therefore minimizes both
circuitry and computation time. Most of its terms
can be calculated either once per half-space
evaluation ~that is, once ~or each directed line of a




-. :

~ 3 ~ )5'31
-14 ~
geometric figure to be written to the framebuffer) or
once per array access. Of the terms in equation (~),
dx, dy, xl and Yl are constant for any particular
half-space, and therefore (4c) nePd only be evaluated
once per half-space. The value of this expression is
unaffected by pixel position within the update array,
or by change to another update array. The expression
(4b) must be calculated once for each update array
access.

Expression (4a) must be evaluated for all sites of
the array. However, the expressions offsetx and
offsety are positive integers specifying the site
position within the array; as this is determined by
hardware design, these values are built in to
controller 18. The value of (4a) can then be easily
found in terms of dx and dy; the result (the "site
value") is calculated by controller 18 for each half-
space (i.e. for each directed line) and stored for
each array site. The site values do not depend upon
the particular accessed array, but are constant for
the particular lines comprising the figure being
drawn. The values of dx, dy are provided by
interface 12.

The sum of (4b) and (4c) is called the l'half-space
constant." A new half-space constant must be
specified for each accessed update array because the
value depends on the origin of the array (originx,
originy). The same value of the half-space constant
is specified to every logical processor of 104. The
sign of the sum of the stored site value and the
half-space constant functions as a discriminant which
gives the sidedness of the pixel with respect to the
line; since the sign bit is the only bit of interest,
a comparator can be used instead of an adder.
Therefore, referring to Fig. 11, each logical



- : .

~ 3 ~

-15-
processor of 104 comprises a register 204 to store
the site value, input at the commencement of a tiling
operation; a magnitude comparator 200, to which the
site value from register 204 is a first input; and a
second input 202, on which the half-space constant
for the array is input to comparator ~00. The
discriminant signal is output on line 206.

The half-space evaluation must be made for each line
bounding the figure to be drawn to the framebuffer.
Referring next to Fig. 7, it is seen that the
interior area of a triangle, for example, can be
represented as the intersection of three hal~-spaces
with respect to the sides, represented as directed
lines. The segments of the lines between their
mutual intersections comprise a closed boundary of a
convex geometric figure. The directions of the lines
must be such that the segments perambulate the
boundary in a single sense; that is, the line
se~ments must all be "nose to tail'l. Ascertaining
whether a pixel is inside the triangle is
accomplished by concurrently evaluating its sidedness
with respect to three directed lines. Thus, for each
pixel, a processor of the kind shown in Fig. 11 must
be provided at 104 for each half-space evaluation to
be made.

A logical AND of the discriminants for all the
bounding lines gives the final result discriminant;
that is, the pixel must be inside with respect to all
the dir~cted line to be inside the triangle. (Pixels
on a line are assign~d to one or the other half-
space, based on considerations not pertinent to this
invention.~

The output of the AND is used to condition the write
enable 88 to the memory chip 24 on which the

~, 3 ~ 3 ~
-16-
specification of the pixel is stored. A first value
of the result discriminant speciEies insidedness of
khe pixel: the second value specifies outsidedness.
A write enable to the pixel site cannot be provided
in the presence of a result discriminant of the
second value. Other conditions may be imposed on the
write enable, for example, as a result of windowing,
clipping and other operations. The method can be
generalized to n-sided convex polygons; more complex
figures can be represented as composed of convex
polygons. Line segments on a raster display can be
modeled as the intersection of four half-spaces.

Data signals specifying the geometric figure to be
drawn (as by giving the (x,y) positions of the
vertices on the display) are transmitted by processor
50 to interface 12, which transmits the necessary
data to controller l~. Such specification must
include, whether explicitly or implicitly in terms of
the order of specifying the line se~ment end points,
direction of each of the line segments, such that a
closed figure is specified by the line segments
between mutual intersections and the figure boundary
is perambulated by the segments in a single sense.
The rendering operation can begin with any arbitrary
location in the figure to be drawn; for example, a
first vertex can be selected and the update array to
which it is mapped Eirst ac~essed. Alternatively, a
preliminary evaluation can be made to find the left-
most (or right-most) point in the figure to be drawn,
after which the update array to which that point is
mapped is first accessed. This latter method offers
certain economies of operation.

As controlled by state machines 100, controller 18
begins operation by accessing the initial update
array. Controller 18 outputs an appropriate address

L 3 ~ ~ ~ ? $ ?~
~17-
request at 94 to interface 17, which provides
corresponding location address signals to memory bank
20. By concurrently performing half-space
evaluations for the pixels of the first update array
s with respect to the corresponding portion of the
figure to be drawn, processors 104 of controller 18
control writ~ enable means 102 to output signals ~n
88 so as to permit the writing of the corresponding
pixels.

A next update array must then be addressed, accessed
and written, and so on until the geometric figure has
been tiled. A tiling operation is illustrated in
Fig. 8 in which a triangle is shown tiled by 53
update arrays. The numbers in each box indicate the
order in which the update arrays are accessed. Array
1 is first accessed. In the method illustrated in
Fig. 8, the initially accessed array is the o~e with
the first vertex. In the alternative method, array
53 would be first accessed, as having the left-most
element of the figure mapped to it.

Controller 1~ stores the address of the initially
accessed update array in storage 115. The pixels of
the initial array are written as described. A test
(to be described) is performed to decide whether the
figure continues to the array below the initially
accessed array; if it does, the stored array address
iS 50 marked ~for example, by a flag). Similarly,
the test is performed to decide whether the figure
continues to the array above the initial array; if
so, the stored array address is so marked. If the
figure to be drawn was not initially evaluated to
find the left-most point in it, the test is performed
to decide whether the figure continues to the array
to the left of the initial array. If it does,
controller 18 outputs address request signal 94,

:~ 3 ~ $ $ ~
-18-
specifying the next ar~ay; in response, addressing
means 17 outputs location address signal 27 to memory
bank 20, addressing the speci~ied next update array.
The pixels of this next array are written as a result
of half-space evaluation operations as previously
described. The tests tdown, up and left) are
performed againO However, if the address of any
array in this row has previously been stored and
flagged for down continuation of the figure, the
address of this array will not be so flagged;
similarly for up continuationO The operation is
repeated until the result of the test indicates that
the figure is not mapped to the next left array. For
example, in Fig. 8, after writing array 1, it is
found from the test that the array to the left of it
is not mapped to the figure.

Controller 18 then (using the specification of the
initial array stored at 115) performs the tests with
respect to the array next on the right of the initial
array. Again, if the figure is mapped to this array,
it is accessed and the pixels are written by means of
parallel half-space evaluation operations as
previously describedO ~s the specification of the
starting point has been saved, no array is accessed
or written twice.

At the end of the operation with respect to a
horizontal row of arrays, every array in that row to
which the figure is mapped has been accessed and
written, and at most one array address has ~een
flagged for up continuation and one for down
continuation.

When no further arrays in the row are found to be
mapped to the figure, controller 18 operates with
respect to the flagged array addresses, to access a

~ 3 .~ 2 ~
-19
downwardly adjacent array. This becomes the initial
array of the next horizontal procedure. When no
further arrays downwardly are found to be mapped to
the figure, the process pops to the first stored
array which has been flagged for upward continuation
of the figure. When no further upward flags are
found, the process has been completed. It will be
understood that the upward flags could be first
exhausted before moving to the downward flags; the
requirement is simply that all arrays to which the
figure is mapped should be accessed and written,
without repeating any operation.

To test whether a figure is mapped to an adjacent
array, referring now to Fig. 9, a border set of
pixels is defined as th~ row or column of pixels in
the previously addressed 4 x 4 array lying closest to
the array in question. (The dimensions 4 x 4 are
exemplary only.) The pertinent half-space
evaluations are performed by sampling each of the two
pixels which bound the border set. However, as will
be noted in Fig. 9, one (0,0) of the sampled pixels
(considered to be located at its origin corner~ i5
within the currently accessed update array, while the
other ~0,4) is outside it. The (0,0) pixel
evaluation is performed by the corresponding logical
processor of 104 in the course of writing the figure
to the update array; the additional three logical
processors 105 are provided to perform the parallel
evaluation of the three pixel locations (4,0), (0,4)
and (4,4) which are all outside the currently
accessed array. As these locations cannot be
accessed concurrently with the locations of the
currently accessed array, the three additional
processors 105 do not control the write enable means.
The processors 105 are otherwise similar to those of
104, as shown in Fig. 11. The outputs of these

~ 3 ~ , 3

-20-
processors 105 are used only for the purpose of
tiling the figure by selecting further update arrays
for access.
A triangle composed of three line segments I, II and
III is shown mapped to a first array. The test is
performed with respect to the decision whether to
address the next array to the left. Each of the
pixels (0,0~ and (0,4) is evaluated with respect to
each of the three line segments.

The criterion for left access is that every half-
space defined by the figure has one of the sample
pixels of the left border set inside. The inside
sample pixel need not be the same for any of the
half-spaces; but no one of the line segments can
exclude both pixels. For line segment I, the sample
pixel ~0,4) is found to be in the inside half-space;
for line segment II, the sample pixel (0,0) is found
to be in the inside half-space; for line segmenk III,
both sample pixels are found to be in the inside
half-space. Since for each half-space at least one
sample pixel is inside, the figure is considered to
be mapped to the next left update array. Controller
18 therefore issues an address request signal 94
specifying such array to addressing means 17, which
provides the corresponding location address signal to
memory bank 20.

A final constraint is imposed. As shown in Fig. 10,
a triangle composed of directed line segments I, II
and III kerminates at a vertex mapped to pixel (1,1)
of the array. However, upon applying the test
described above for deciding whether to address the
array lying horiæontally to the left of the
illustrated array, it is found that the test is met,
although in fact the figure ought not to be drawn
into the next array. To prevent erroneous

~ 3 ~ 3 ~3f

addressing, a specification of a "bounding box" which
encloses the ~igure being drawn (derived from the
vertex information initially transmitted from
processor 50) is stored in 115. Before re~uesting
addressing f the next array, controller 18 compares
the (x,y) position of the array with the bounding box
position. When the result shows that the next array
lies outside the bounding box, the test result is
overridden.

The described operation of selecting a next update
array is particularly advantageous in that the half-
space evaluation for one of the sample pixels is made
in the operation of writing selected pixels within
the accessed framebuffer update array, while the
other is easily made concurrently with such writing
operation. This permits the test to be made quickly
and simply.

In addition, the described operations are equally
useful in the drawing of both lines and polygons to
the framebuffer. This provides economy of design of
the controller, as circuitry need only be provided
for a single mode oE op~ration. In contrast,
incremental operations used in the prior art for
drawing lines generally are quite different ~rom
incremental operations for drawing polygons,
necessitating the provision of additional circuitry
in such incremental rendering systems.

Further, the described operations are directly
carried out with respect to the data, for example
vertex positions in the framebuffer, transmitted from
processor 50. In ~ontrast, in many incremental
rendering operations it is necessary to convert such
data into a form suitable for use in the operation;
this set-up step is made unnecessary in the present

~ 3 ~

-22-
operation, permitting a saving of time for completing
the rendering operations.




- .

Representative Drawing
A single figure which represents the drawing illustrating the invention.
Administrative Status

For a clearer understanding of the status of the application/patent presented on this page, the site Disclaimer , as well as the definitions for Patent , Administrative Status , Maintenance Fee  and Payment History  should be consulted.

Administrative Status

Title Date
Forecasted Issue Date 1993-01-12
(22) Filed 1988-12-16
(45) Issued 1993-01-12
Deemed Expired 1995-07-12

Abandonment History

There is no abandonment history.

Payment History

Fee Type Anniversary Year Due Date Amount Paid Paid Date
Application Fee $0.00 1988-12-16
Registration of a document - section 124 $0.00 1989-10-02
Owners on Record

Note: Records showing the ownership history in alphabetical order.

Current Owners on Record
DIGITAL EQUIPMENT CORPORATION
KELLEHER BRIAN
FURLONG, THOMAS C.
Past Owners on Record
None
Past Owners that do not appear in the "Owners on Record" listing will appear in other documentation within the application.
Documents

To view selected files, please enter reCAPTCHA code :



To view images, click a link in the Document Description column. To download the documents, select one or more checkboxes in the first column and then click the "Download Selected in PDF format (Zip Archive)" or the "Download Selected as Single PDF" button.

List of published and non-published patent-specific documents on the CPD .

If you have any difficulty accessing content, you can call the Client Service Centre at 1-866-997-1936 or send them an e-mail at CIPO Client Service Centre.


Document
Description 
Date
(yyyy-mm-dd) 
Number of pages   Size of Image (KB) 
Description 1993-11-09 22 947
Drawings 1993-11-09 7 172
Claims 1993-11-09 7 287
Abstract 1993-11-09 1 29
Cover Page 1993-11-09 1 15
Representative Drawing 2002-03-18 1 8
Prosecution Correspondence 1992-05-12 8 377
Examiner Requisition 1992-02-03 1 52
Prosecution Correspondence 1992-10-23 1 21
Office Letter 1989-07-03 1 55