Note: Descriptions are shown in the official language in which they were submitted.
13299~
METHOD AND APPAR~T~l~FOR IMA~E ~IIPUL~
l~a~k~olJn~ Q~th2 lr~entTo~
The present invention relates to apparatus and methods for displaying
5 graphic information. More particularly, the present invention reiates to data
processing apparatus and methods for generating and manipulating images
and data on a display system.
HistQry of îhe Prior Ar~
In the computing industry, it has become quite common to represent and
convey information to a comput0r user through ~raphic representations. These
representations may tak~ a vari~ty of forms such as alphanumeric characters,
cartesian or other coordinate ~raphs, or the shapes of well-known physical
objects. Historically, humans have oommunicated with computers through a
15 series of discrete commands which typically oomprise a combirlation of both
text and mathematioal symbolic characters. The combinations of discrete
commands are usually referred ~o as programming languages. Examples o~
languages using such commands include Fortran, Algol, PL/I, Basic, and
Cobal. These programming languages transform a given s~t of user commands
20 into machine executable "object`' code.
The ease with which a computer user becomes proficien~ in interacting
with a computer system is r~lated to how olosety the operation of th~ system
tollows the logical patterns familiar to the computer user. If the comput~r user is
able to enter commands in an ord~r or form which he finds logically apprepriate
25 rather than having to tral~)spose his d~sired commands into th0 ood~ of a
pro~ramming lan~uage, profici~ncy in the lan~uage is achiev~d at a ~r~ater
rate.
One syst~m which has been developed lto reduce the learning tirne
requir0d ~r a computar user to beoome proficient i~ raferred to as an "obj0ct-
30 oriented~ system. An object ori~ntacl system replaces many common codedprogrammin~ commands with graphic images on a comput~r display.
1 32~9~0
Quantitativ~ly, it has b~en found that since people readily think in terms o~
images, a person.can absorb and manipulate information presented in a visual
context much faster than information represented by text. The particular Iype of~raphic interfac~ by which th~ user interacts with the machin~ may vary for
any given application.
One oommon interfac~ utilizes multiple "windows" displaysd on a
cathode-ray tube to represent individual computer files; in lsach window,
combinations of text and graphics are used to convey inforrnation. For
example, each window may appear as an image having a form similar to the
l O outline of a file folder of the type used in a standard filing cabinet. Each such
folder may overlap other folders with the ~front folder~ c~nstituting the curren~
work file. The us~r may add or delete information from the current file fold~r
window, add new items to the fil~ folder, refile the file folder window in another
location, and, generally, operate on the file folder window as if it were an
I 5 actual file folder in an office.
Thus, by using a graphic image with which the user is familiar to
represent the user's command, and allowing the user to operate on and
manipulate the ima3e in substantially the same way as the familiar object, the
computer becomes easier for the user to operate and becomes so more rapidly.
Although graphic representations have been found to be useful in
computer systems, large amounts of memory are required to ~enerate, store,
and manipulate graphics chsracters. To produce a graphics display on a
eathode ray tube, the screen full of images or text is represented as eith~r a
one (black dot) or a zero (white dot) in a block of memory known as a "bitmapn.
In its simplest form, each picture elflment (pixel) on thc scr~n must be
represented by a memory bit. lf the display screen has 1024 by 1û24 pixels,
then one million bits of memory are necessa~y to represent ~ach ~crsen. To
aocomplish this, a block of memory may be allocated in a da~a proe~ssing
stora~e system wiSh eaeh memory bit (a 1 or 0) mapped onto a corrzspondillg
pixel on th0 display syst0m. S~oh, a on~t~on~ correspond~nc~ betwc~n the
bitmap and ~he eathode-ray tube displ~y rc~uir~s a significant amount of
'
13299~0
storage space within th~ compute~s core memory. In addition, the generation
and manipulation of an image or charact~r requires that vir~ually all bits in the
bitmap be updated afler any modification to an image. This procedure is both
rep0titive and ~ime consuming and significantly hampers ~he practical use of
5 interactive graphic display operating systams.
To reduce the amount of storage necessary to provide the necessary
graphic capabilities for such systems, various methods have baen devised.
However, all such systerns include limitations such as the type of images they
are capable of handling and manipulating.
1329~
S~mmary o~ the Invention
The present invention provides methods and apparatus which are
advantageously us~d in conjunc~ion with a digital computer to provide
S improved ~raphics capability. Thsse ~chniques permit the presentation and
manipulation of any arbitrarily defined region in terms of "shape tables~.
The method and apparatus of this invention allow both ILnear and cu~ed
edges of graphical representations to be defined, rendered, clipped, and
combined.
According to ~h~ invention, the analytical descriptions of both images
and clip regions are converted to shape data structures prior to any clipping orrondering o~ the images. Thareafter, a boolean operator is applied te the shape
data structurss to manipulate one shape against another there~y producing a
new shape which depends upon th0 two source shape data str~ctures. This
output shape may then be rendered or used by subse~uent shape operations.
According to the invention, a shape consists of a sorted list of rectangles
dsfining an area of the screen in device coordinates. This list is de~ined to besorted in ascendin~ order on the Y axis. For each Y range, there is an
associated X range also sorted in ascending order.
As will be seen from the description which follows, stn~cures defined
usin~ tha shape data structure techni~ue may be large and vaned yet utilize
only a relatively few definition points. Consequantly, the amount of memory
nacessary to store th~ graphic structures using the shape data struc~ur~ is
drastically reduced over tha~ used by th~ mo~ usual methods of ~raphic
storag~. Moreover, shap~ data stn~cturas may be manipulat~d easily by
comp~ar systems utilizin~ well known boolean operators.
~ria~ ~escripti n of th~ ~)rawln~
Fl~ure 1 illustrates in block cliagram form a ~aneralized ~mput0r
system whioh may utili7e the inv~ntion.
- 4
1 3 ~
Fl~ure 2 is a first two dim~nsional illustration of a shape data struc~ure
in accordance with the invention.
Fi~ure S is a s~cond two dimensional shape data structure pr~pared in
accordance with ~he invention.
S Fi3ur~ 4 is an illustration of a window utiliz~d in computer graphics
displays rendered by a shape diagram in accordance with the invention.
Flgures ~(a-c) illustrate particulaf generalized boolean operations
which may be accomplished in accordance with the inv~ntion.
Fl~ure 6 is a chart illustrating different possible inlersec~ions of two line
segments in a one-dimensional determination carried on in accordance wi~h
the invention.
Figure 7 is a chart listing the outputs and providing next step segments
in accomplishing the boolean operations raferred to in Fi~ure 5 in practicin~
the invention.
1~ F~ure 8 is an illustration of a yeneralized ~)peration carried ou~ in
accordance with the inven~ion.
Figure 9 is an illustration of a mor~ particularized boolean op0ration
carried out in accordance with the invention.
~IQt~t~Qn ~nd NQmen~l~ure
Ths d~tailed descriptions which follow are prssented largely in terrns of
algorithms and symbolic representations of operations on data bits within a
comput~r mem~ry. These algorithmic descriptions and r~presentations are the
means ussd by those skilled in the data processing arts to most effectively
2~i ~nvey the substance of their work to othars skilled in the art.
An al~orithm is here, and ~enarally, conceiv~d to be a seH~onsist~nt
sequenca of steps leadin~ to a desired result. The steps are those r~quiring
physical manipulations of physical quantities. Usually, though not n~cessarily,
thes~ quantili~s take the form o~ ~lectrical or ma~nstic signals capabla of b0ing
stored, trans~erred, ~mbin~d, comparsd, and oth0rwise manipula~ed. IS has
proven convenisnt at times, principally for reasons of common usa~e, to ref~r
1329~0
to these signals as bits, values, el~ments, symbols, characters, terms,
numbcrs, or the like. It shouid be bom~ in mind, howver, that all of th~se and
similar terrns ara to be associat~d with the appropriate physical quanti~ies andare merely convenient labels applied to th~se quantities.
S Further, the manipula~ions performed are ofSen referred to in terms, such
as adding or comparing, which ar~ commonly associated with mental
operations performed by a human operator. No such capability of a human
operator is necessary or desirable in most oases in any of the operations
described herein which fonn part of the present invention; the operations are
maohine operations. Useful machines for performing the opera~ions of the
present invention include general purpose digital computers or other similar
devices. In all cas~s the distinction betwesn the method operations in
operating a computer and the method o~ computation itself should be borne in
mind. The present inven~ion relates to method steps for opera~ing a computer in
l ~i processing eleetrical or other (e.g. m0chanical, chemical) physical signals to
generate other desired physical signals.
The present invention also relates ~o apparatus for performing these
operations. This apparatus may be specially constructed ~or the requir~d
purposes or it may comprise a general purpose computer as selectively
activated or reconfigured by a oomputer program stored in the compu~er. The
algorithms presented harein are not inherently related to any particular
computsr or other apparatus. In particular, various general purpose rnachines
may be used with programs written in accordance with the teachings herein, or
it may prove more convenient to oonstruct more specialized apparatus to
p0rform the required method steps. Th~ required structur~ for a varie~y of thesemaohines will appear from the dascrTption ~iven below.
Fl~ure 1 shows a typical compu1~r-bas~cl system for g~narating
computor graphic ima~es accor~JTng to th~ present inv~ntion. Shown is a
1329~0
computer 20 which eomprises an inpuVoutput circuit 22 used to communicate
in~ormation in appropriateiy stru~tured form to and ~rom the other parts of
comput~r 20 and associated aquipmen~, a oentral processin~ unit (CPU) 24,
and a memory 26. These components are thos~ typically found in most general
5 and special purpose computers; and the several elements contained within
computer 20 are intended to be representative of this broad eatagory of data
prooessors. Par~icular examples of sui~able data processors to fill the role of
computer 20 included machines manufactured by Sun Microsystems, Inc.,
Mountain View, California. Other oomputers having iike capabilities may of
10 course be adapted in a straight forward manner to perform the several func~ions
described below.
Figure 1 also illustrates an input device 30 shown as a keyboard. It
should ba understood, however, that the input device 3û may actually be a
card reader, a magnetic or paper tape reader, or some other well-known input
15 devioe such as, of course, another computer. A mass memory devioe 32 is
coupled to the inpuVoutput circ~it 22 and provides additional storage
capability for the computer 20. The mass memory device 32 may be used to
store programs, fonts ~or giv~n characters, and the like and may take the form of
a magnetie or paper tape reader or soms other w811 known device. It will be
20 appreciated that the data retained within the mass memory device 32, may, in
appropriate casss, be inco~orated in standard fashion into computer 20 as
part of the memory 26.
In addition, a display monitor 34 is illustratad which is used to display the
images being ~enerated by th~ presen~ invention. Such a display monitor 34
25 may tak0 the ~orm of any o~ s~veral w~ known vari~ti~s of oathods ray tube
displays or soma other well known typ~ of display.
As is wall known, the memo~y 26 may include programs whieh r~pres~nt
a vari~ty of sequences of instructions for ~x~cution by the csn~ral processing
unit 24. For example, the control pro~ram for irnplsm~nting th~ operations and
30 routines dsscr~b~ hsr~in to monitor and control programs, disk operating
systems, and the like may be stored within the memory 26.
. ~ ~
~ 3 ~ 0
11 should, of coursa, be understood by those skilled in the art that the
invention may be practic~d by th~ use of a special purpose digital computer as
well as the general purpose computer illustrated in Fi~ure 1.
Ib~
The present invention represents any arbitrarily defined region in terms
of a shape data stnJcture. Such a structure consists of a iist of rectangles
defining an area o~ the screen of a cathod~ ray tube in device coordinates.
The lis~ of rectangles is sorted in ascending order based on its Y axis. For
l O each Y range, there is an associated X range also sorted in ascending order.Referring now to Fi~ure 2, a structure is illustrated which may be
defined as a shape data structure. Th~ structure shown is de~ined in
generalized terms. Along the lefl side of the structure, a verlical Y axis
proceeds in increasing order from upper point Y~ down through points
l 5 concluding wi~h Y3. Along the upper honzontal axis proc~eding from left to
right in increasing order appear points labelled Xo through X3. Each shape
data strueture is defined by a series of rectan~les which procead along the Y
axis from the uppermost to the lowennost point of the figure. The generalized
configuration shown in Fi~ure 2, 70r instance, is defined by three rectangles.
20 Th~ rectangles used to define the shape data structure ar~ arrived at by
beginnin~ at th~ initial Y point and continuin~ along the Y axis until a change
occurs in the dimensions o~ the structure on the X axis. Thus, for the stnuctureof Fi~ure 2, the first r~ctangie lies between the Y coordinates Yo and Y1 and
between thc X coordinates X1 and X2. The coordinates of this r~ctan~le are
25 listed in Fl~ure 2 in generaliz~d ~orm as (Y~, Y1 ) (X1, X2) on the first line to
the righ~ of the struc~ur~. The second rectar~ bsgins whera the fir~t ~nds at
the change in the X dimsnsion; this rec~anyle has as its Y coordinates Y1 and
Y2 and as i~s X coordinate~ Xo and X3. The coordinates of this rectan~le are
list~d on th~ second line to the ri~ht of the stnuctur~. Th~ ~hird r~ctangle is
30 deflned by the Y coordmates Y2 and Y3 and th0 X coordinat8s Xo and X2
which are Hs~d in th0 lhird line to tl~ right o~ th~ structure. A shape data
132~0
structure can also represent an ar~a o7 a page on a printer device. This
algorithrn can also be appli~d to ~raphics on pnnters.
The entire re~ion dsfined by ths ~eneralized shape clata structure of
Fi~ur~ 2 is the ~enerally rectilinear figure which begins at thG point Yo X1
s ~nd centinues clockwise through the points Yo X2, Y1 X2, Y1 X3. Y2 X3, Y2
X2. Y3X2, Y3 Xo, Y1 xn, and Y1 X1 back to the be~innin~l point Yo X1.
At this point, a bounding box needs also to be defined. Q bounding box
is the least rectangle which encloses an entire configura~ion while just
touchin~ the edges of the configuration. In the configuration of Figure 2, the
10 bounding box is the rectangle enclosed by the reetangle joining the points Yo Xo, Yo X3, Y3 X3 and Y3 and Xo
Fl~ure 3 illustrates a particulariz~d rectilinear figure described by a
shapc data structure having particular d0signated points. In the configuration
of Fi~urs 3, the rectangular shapes describing the region b~gin at the '~fo
I 5 point and proceed downward until a first change is reached in the area defined
alon~ the X axis. This first shape has the coordinates (0,2) along the Y axis
and (0,3) (6,9) along the X axis and is, consequently, defined by a pair of
rectangles having the same Y dimensions but different X dimensions. These
ooordinates are given to the right o~ the structure as (0,2) and (Q,3) ~6,9). The
ZO second rectangular shape has the coordinates (2,5) along the Y ax,s and from
O along the X a~is to 9 along the X axis. The coordinates for this second
rectangle are given to the right of the structure as (2,5) (0,9). The third
~ectangle of the shaps data stnJcture has the coordinates (5,8) along the Y axis~nd (0,4) alon~ the X axis. The eoordinates for this shape are shown in ~he
25 third linc to the ri~ht of th~ stmcture.
A shape data structure ~or a solid rectangle having rounded o~ rs of
the type which mi~ht b~ used for a window is illustrated in Fl~ure 4. Th~
shape data stn~cture ~or the oonfi~uration comprises the rectan~les illustrated
in ~eneralized form in Fl~ur~ 4. Th~ uppermost r~ctangla has ~' coor~inates
30 of Yo, Y1 and X ~oordinates of X6, X7. It should be noted that this first
rectan~l~ would probably comprise a sin~le scan line on 1ha cathode ray 1ube.
~ ~9~
However, this rectangular shape and the other rectangles which define the
curved corners are shown in Fi~ure 4 ais more widely saparated to assist in
understanding the concept. The second r~ctangle has Y coordinates of Y1,
Y2 and X coordinat~s of Xs, Xg. The rectangl~s proce~d in ord~r downwardly
S along the Y axis with each change in ~he X dimension until the point Y6 is
reached; from this point the s~ructure does not vary in the X dimension between
the points Y6 and Y7, and thus the next rectangle has the coordinates Y~, Y7
and Xo, Xl 3. E~eyond the large central rectangle just defined, the shape data
structure continues downwardly with a series of smaller rectangles each
l O essentially defined by a single scan line on a cathode-ray tvbe. These include
the rectan~le with coordinates Y7, Y8 and Xo, X12 through the rectangle with
coordinates Y1 2, Y13 and X6, X7.
As can be seen from the structures deflned to this point using the shape
dala structure technique, large and varied structures may b~ definsd using
15 only a relatively few definition points. Consequently, the amount of memory
necessary to store the graphic structures is drastically reduced over that uisedby the more usual methods of ~raphic storage.
--10--
, ,, j,
. . . ~
.
.
1 329~0
A shape da~a structurs d~n~d ~r a partic~J3ar r~3j~n may b~
manipulated to provide usaful outpu~ by m~ans o~ standard s0t op~rators.
s Fl~ure 5 illustrates three standard set opera~ors which may ba accomplished
upon two r~ctangular shape data stn~ctures which overlap each other.
Figure 5a illustrates th~ logical meaning of the union operator which
produces an output shape describing ihe total region enclosed by the two input
shape d~ta structures. This outshape is produoed even theugh the regions
l o may or may not overlap.
Fl~ure 5b illustrates the logical meaning of the application of the
intersection operator ~o the two rectangles. Thc intersection operator produces
an output shape descnbing the area common to both input shapes. It is
especially uscful for clipping and determining areas of overlap of two rsgions to
1~ be displayed on a cathode ray tube.
Figure 5c illustrates the results of utilizing the di~ference op~rator on
the two rsc~angular regions. llle difference operator produces an output shape
which describes the area contained in one input shape that is not overlapped
(covered~ by any area of the other input shape. It is useful, among o~her things,
20 in computing the visible area of a window which is overl pped by other
windows.
In describin~ the manipulation of shape data structures, algorithms will
be utiiized in order to maka th~ descriptions more succinct. In utilizing these
algorithms, two input shape data struatures are compared at a time; ~hese input
25 shape data structu-es are scanned and compared, rectangls by rectan~ls.
Se~m3nts of each shapa data stnJcturo are processed in pairs; these sagmcnts
are ~he lin~s comprisin~ the X and Y coordinates which define each r~ctan~le
makin~ up each shap3 data structure. A~ any particular tim~, the pair of
segments under considsration ~ntain one s~ment from the first shape da1a
30 stn~cture and one sc0ment ~rom the second shape data struc~ur~. However, as
~he process proco~ds, a s~ment may bs replaced by a new se6~mant dariY2d
132~0
from ~h~ original se~ments which have just been manipulated. When all of the
se~ments in ei~her of the shapes have been processed, the output shape is
eompletc.
In order to determine the output data shape stnJcture which showld be
~en4rated under any of th~ opsrators of unisn, int~rs~c~ion, and difference, an
overlap routine has b~en devised. This overlap routin~ presents all of the
possible conditions under which two line segments may overlap one another
and provid~s output in accordance with ~ach form of overlap depending on the
particular opera~ion. These overlap possibilities are illustra~ed Flgure 6. In
l 0 each case of the overlap routine, the first line segment is definad by points
generalized as P1,1 and P1,2; and the second line segment is defined by
points ~neralized as P2,1 and P2,2. The codes labelled with negativ~
numbers arc thos~ in which the line segments do not, in fact, overlap.
The first example, labelled -1, illustrates a pair of line se~ments in which
l 5 the first line segment lies entir~ly ~o the right o~ the second line segmQnt without
either of th0 two lin0 segments overlapping one ano~her. In the s~cond
example, labelled -2, the first line segment is to the le~t of and do~s not overlap
the second line segment. In the third example, lab~lled 1, th~ two line
segments overlap with the first line segment extending to the right of the second
line segmen~, and the second line segment extending to the left of the first
segment. The tourth sxample, labelled 2 in Fi~ure 6, involves two line
segments in which the ffrst is shor~er than the se~ond, and the second 6xtends
b~yond the first in both directions. The tifth example, labelled 3 in Fl~ure 61
illustrates a first lin~ s~gmsnt which is lon~er than the second and ov~rlaps the
second at both ~nds. The sixth 3xampls, labelled 4 in Fl~ur~ 6, illustrates a
ffr~t line segm~nt which ov~rlaps the second to the i~f~ whil0 the second line
se~ment overlaps th~ flrst to the right. 11~ wlll bs understood that thss~ overlaps
m~y be utilized to repr~sent all of the possibl~ conditions of overlap which may~xist with two parall~l lin~ segm~nts.
In utilizin~ ths algorithms, ~he ov~rlap routin~ shown in Fl~ure 6 may be
us~d to compar~ two lina s~m~nts (~our input points~ and producc an ouSput
~329~a
code indicatin~ the type of overlap. The overlap routines are used for
d~tecting both X and Y overlap conditions.
The output cod~s r~turned by the overlap routines de~ermine not only
what is to bs copied into the outpu~ shape data struc~ure for each operation but5 aiso the next s~gments to be compared in the operation. In proc0ssing sach of
the op~rator algorithms, ths overlap codes are tested in ~ht~ ~ollowing order.
Overlap c~de 2 is first considersd ~o see whe~her ~ is met. If not, overlap oode1 is considered, then overlap code ~ hen overlap code -2, then ov~rlap
code 4, and ~inally overlap code 3. Where either of two codes may be utilized,
10 in most situations, they provid~ both the same output and define th0 same
segments for the next operation.
The tables o~ Fi~urs 7 are utilized with the overlap oodes of Fi~ure 6
to indicate th~ output segment to be copied to the output shape data structure
and the nex~ segments to be compared ~or each of the intersection, difference
l 5 and union op~rations. Fi~ure 7 includes three tables which deflne the outputs
of Ihe three operations. The upper tabie provides the algorithrn ~or output for the
intersection operation. The middle table provides the algorithm for d~termining
the differenca eperation. The lowar ~able provides the algorithm 10r determiningthe union operation. In reading the tables of Figure 7, the titles "Segment 1~
20 and "Segment 2" mean the current values for a segment from shape 1 or shape
2. Mor~ov~r, a r~ferenc~ such as ~next shape 1 segment" means that the next
segm~nt should be ~ched from shape 1 to furnish the current values for the
segment.
Fi~ure 8 illustrates in 3eneraliz~d form the use of the overlap codes of
25 Fi~ure 6 in applying the intars~ction o,oerator t~ overlappin~ rectangles.
The shap~ d~ta stnJctures for th~ two rectanglcs are illustrated by the shapa
aquations to the right and below the rectan~ies. In a~pplyin~ th~ interseCtiQn
opsrator, a l~lrst Y s~m~nt Yo, Y2 from the first shap~ clata structure (the upper
îsfl rectan~le) is oompared 10 a second Y segm~llt Y1, Y3 from the s~oond
30 shap~ data struclur~ ~the lowar ri~ht r~angla~. The flrst segm~nt is shown
b~low th~ data structures usin~ both the gen~ral descfiption P1.1 P1,2 and the
- 13--
1 3~9~0
particular description Yo and Y2 while the second sesment is shown using
both the general description P2,1 P2,2 and the particular description Y1 and
Y3. The hNo segments are arran~ed in their one dimensional positions relative
to the ongin of the Y axis, and a deterrnination of their ~ype of overlap as
S described in Fi~ure 6 is made. For example, the s0gments Yo, Y2 and Y1,
Y3 of Fi~ure 8 overlap as described by code 4 of Fi~ure 6; that is, the point
Yo is to the left of point Y1 while Y2 is to !he lef~ of Y3 but to the ri~h1 of Y1.
The intersection table of Fl~ure 7 shows that a code 4 overlap
produces an output segment of P2,1 P1,2 which is equal to Y1 ,Y2. This output
l O se~ment is recorded, and a comparison is made of the X segments which are
associated with the initial Y se~ments of the two shape data structures. This
involves a comparison of segment Xo, X2 trom Rectangle 1 and X1, X3 from
Rectangle 2. Arranging these in one dimensional positions relatlve to the originof the X axis shows an overlap which in Fi~ure 6 is also defined by code 4;
l 5 this produces an output segment of P2,1 P1,2 or X1, X2. There being no more
X segments for the first Y segments, the next pair of Y segments is chosen.
Since the last Y operation was a overlap code 4 operation, the intersection
table of Figure 7 shows that those segments are the next shape 1 segments
and the segment P1 ,~ P2,2 from the last Y segment comparison. Although the
20 latter is defined, there is no next Y segment in Rectangle 1 so the intersection
operation is complste. The output shape data structure is that defined as
(~1 Y2) (X1 X2), the expected and corrQct r~sult.
R~fcrnng now to Fi~ur~ 9, therc are shown two more complex shapes
whieh may be manipulated utilizing the shape da~a struc~ures of this invention.
25 The first shape shown in Fl~ure 9 is lha~ of a capital U while th~ second shape
is o~ a oapital T. The two shap0s have been plott~d against th~ X and Y ~xes to
provide num~rical points which may be u~ilized to more readily und~rstand the
~sas of the invention. In Fl~ur~ 9, the X axis commsnces with zaro in the
vpper left hand corncr of the U and continues to the ri~ht positively whlb the Y30 a~(is comm~nces with zero at tha upper lef~ com0r and proceeds downwardly in
--14-
1329~
a positive direction. The capital T is ~uperimposed on the capital U at the
posi~ion shown in Fi~ure 9.
INTER~E~:TIQN
The nrst operation to be und~rtaken utilizing the shape data structures is
the intersection of the capital U and the capital T in the positions shown in
Fl~ure 9. As described above, int~rsection produces an output shape which
describes the area common to both input shapes. Such an operation is us~ful
for clipping and determining arsas of overlap in comput~r graphics displays.
The intersect algorithm to be used may be described as follows in
pseudecode ~orm:
Intersect Shape ~shape 1, shape 2)
If either input shape is empty or bounding boxes do not overlap, return the
empty shap~.
I 5 Get initiai Y ranges in Y11. Y12~ Y21. Y22
.. .
For next segment pair
Ycode = Overlap (Y11. Yl2~ Y2l~ Y22)
If Y ranges overlap
Zo Output overlapping Y rang~ ~based on Ycode)
Get initial X ranges in X11~ X12. )~21. X22 - .
For next s0gm~nt pair
Xcod~ = Ov0rlap (X11, X12. X21. ~22)
If X ranges ov~rlap
Output overlapping X range (based on Xcode)
Set X1 1, X12, X21, X22, (bas~d on Xcod~)
Advance shap0 1 Of shape 2 (based on Xcod~)
Exit if eithar X list exhaus)ed.
If no overlappin~ X ranges output, remove previously outpul Y range
Set Y11, Y12. Y21. Y22 (bas~d on Ycode~ :
Advance sh~pe 1 or shapa 2 ~bas~d on Ycode)
- 15-
: - .
13~99 ~
Exit loop if eith~r input shap~ sxhausted.
As illustrat~d in the above algorithm, Y segments are first comparsd to
produce an ou~put which is put into th~ output shape data struc~ure. Then the X
5 ssgments oorresponding to the Y segment pair are scanned in the same
manner. Thos~ that overiap ar~ appended to the ou~put shape. If none o~ the X
ranges for the currer t segm~nt pair overlap, the previously Idetermined Y
output range is removed.
In this description, the U structure is treated as shape 1 and the T as
l O shape 2. In accordance with the algorithm above, the two shapes are first
intersected. Then if either shape is empty or the bounding boxes do not
overlap, the algorithm returns the empty shap~ as the resuit. This initial step
which takes care of the situation in which there is no int~rsection of th~ two
shapes whatsoever, and the algorithm need not be completed. For definitional
l 5 purpo es, an empty input shape is on~ containing no ar~a, whils ~as 2xplained
above) a boundin~ box is the smallest rectangle which may enclose a
particular shape. For exampls, the bounding box for the U in Fi~ure 9 has X
coordinates of 0,10 and Y coordinates of 0,9 while the boundir~ box of the T
shape has X coordinates of 1,9 and Y coor~inates of 2,11. In ~he case of the
20 two shapes shown in Fi0ur~ 9, it is olear that neither condition is met so the
next ~t~p of the algorithm is effected.
Aecordin~ to tha next step of the al~orithm, ths initial Y ranges of the two
shapes are select~d. In ~eneralized ~orm, th~se are Y11~ Y12 and Y21. Y22
while in the aotua1 fisure ~hese are the Y segment 0,6 for ~he first ractangularZS shape of the U and the Y se~ment 2,4 for ~he firs~ r0ctangular shape o7 the T.
Having selected these initiai Y ranges, the algorithm moves to a afor next leop~operation in which th~ output se3ment Y eode is equal ~o tha ovsrlap of the two
Y sesmsnts.
Usin~ the over1ap code table shown in Fl~ure ~ to compara the two
30 se~ments shows th~t the overlap cod~ to be appli~ is ~de 3; and tho output
from t~ e Fl~ur0 7 inters~ction table is P21, P~2 (Y2~ Y22) or th~ Y segrn~nt
-16-
r .~
9 ~ ~
2,4. This is confirmed by the algori~hm which states that if the Y ranges overlap
~whioh they do) the overiappin~ Y ran~ is produced as an output based on
that Y code . A ~raph of the twe Y segments shows ranges from 0 to 6 and 2 to
4 so that the ov~rlap from th~ Y s~gments 0quals 2 to 4~ As the ov~rlapping
5 portion of the two ranges is 2,4, this is the Y segment which is produced as a first output.
The n~xt step of the aigorithm is to output the overlapping )C ranges for
the first Y se~ments. This portion of the algorithm commences with the step "~3et
initial X ranges in X11, X~2 X21, X2~.~ As may be seen from Fi~ure g, the
1 O initial X range ~or shape 1 is 0,3; that is X1 1 is equal to 0 and X1 2 is equal to 3.
The initial X range ~er shap~ 2 ~the T) is 1,9, i.~.i X21 is ~qual to 1 and X22 is
equal to 9.
The program th~n enters a ~for nexta loop with this segment pair and
produces an X code equal to the overlap of th~ first pair of X segments for
l 5 shape 1 and shape 2 . If those X ranges ovarlap, an output is pr~duoed equalto the overlapping X range based on the X code. The output produced may be
determinad from a visual comparison of the X segments in Fl~ur~ 9. The X
rangss of the initial segments overlap in FT~ure 9 are betw~en 1 and 3. This
result may also bs determined by using ihe overlap codes shown in Fi~ure 6;
20 the initial X line segments overlap in the rnanner shown in code 4. Looking up
code 4 in the intersection tabl~ of Fi~ure 7, n may be seen tha~ the output
would be P21 whioh is 1 and P12 which is 3 as was previously determined by
vi~wing the s~gm~nt overlap in Flgure 9.
The nex~ step of th~ algorithm is to set the X segments to new values for
25 X11, X12 and X21. X~2 based on ~he X code. This is done by raference to the
intersection ~able of Fl~ure 7 at the last operation. The code 4 operation
indicates that ~he next s~m~n~ 1 is set to the next shape 1 se~mern (~he X
segment ~-om 7 lo 10~ while segment 2 is set to the P12, P22 from the last X
iteration (which is 3,9). Essentially, this oompares that portion of the X s~gment
30 of the T fi3ure which did not overlap the U fi~ure in 1he previous ~eration with
~h~ r~mainin~ X se~merlt of the first data shapa structur~ ~ormad frwn th~ U
- 17-
~L329~0
figure. The ~or naxt loop~ portion of th~ algorithm is used to d~termine the X
code overlap for these two s~gments; and, if the X ranges overlap1 to produce
an output for the ovfirlappin~ range. As may be seen by viewin~ Fl~ur~ 9,
th~ overlapping portion of the X ranges for these two segments is 7,9. ~eferringto Fi~urc 6, this output may also be determined as a code 1 overlap which in
the interseotion table of Fi~ure 7 shours an output of P11, i-~22 or the same X
values of 7,9.
The next step in the X iteration is to reset tha X segments based on ~he X
code. This may be determined from Figure 7 under code 1 for the cornparison
operation just conducted. Segment 1 is set to P22, P1 ~ or 9,10, while segm~nt
2 is set to the next shape 2 segment. There being no furth0r X segmen1s in
shape 2 to advance (i.e. the X list being ~xhausted for this first rectanglel, the X
portion of the algorithm is exited, and th0 next Y segments are set based on theY code .
l 5 At this point, a revi~w of the outputs already produced shows ~hat a Y
segment from 2 to 4 has be~n generated and associa~ed therewith ars t No X
segments Srom 1 to 3 and ~rom 7 to 9. These intermediate outputs have
gsnera~ed an intermediate shape factor which includes the single line cr~ss-
hatched boxes enclosing those areas on the graph of Figure ~.
To continue with the algorithm, in order to set the Y11 . Y12 and Y21,
Y22 segments based on the Y code, it is nsoessary to re~er back to the last Y
operation (i.e. the comparison of the Y segments 0,6 from the U shape and 2,4
~rorm the T shape. As explained above, that comparison was a code 3
comparison using the overiap cod~s of FiQure 6. The flrst table of Figure 7
shows that the next segmants to be utilized in the Y comparison are a s~gment
1 o~ P22, P21 and a segment 2 which is the naxt shape 2 Y se~ment.
P22, P1~ from the last eomparison of the Y s~ments 0,6 and 2,4 is the Y
sagment 4,6, while the ne~ shape 2 Y segment is the sa~ment4,11.
Conseque~ly,th3se Y se~ments are s~ls~sd;andthe aî~orithm is advanced
tothe n0~ step whsr~the"fornext~loop tor Y comparison b~gins. ~tthisstep,
the Y cods is set equal to Ih~ overîap of the two Y se~ments just Sel or
,
.
132s~a
equal to 4,6. A~ain, this Y valu0 may also be determined by ~he overlap codes
shown in Fi3~ure ~. At this point, it should be remembered ~hat in the case in
which the seyments commence or start at the same X sr Y point, ~he algorithrn
considers the overlap codes in a particular ord~r as follows. Thc code 2
5 overlap is first consider~d to see whether i~ is me~. if not, overlap code -1 is
considered, then code 1, then code -2, then code 4, and finally code 3. In
most situations where ~ither of two codes may be u~ilized, they provide both thesame outpu~ and define the same se~nients for the next operation.
In lhe present case, bo~h segments commence at Y equal to 4; the
l O segment o~ shape 2 is the longer, however, and extends to Y equal to 11.
Consequently, code 2 (the first code to be considered) encompasses this
situation and produces an output of P1 1, P12. It should be noted that overlap
code 4 which could be considered to cover these segments would produce the
same output since the points Y11 and Y21 are identical. Moreover, it should
l 5 be noted that tha next segmants 1 and 2 for each of.codes 2 and 4 are iden~ical.
Consequently, either overlap code 2 or 4 will produce as an output a Y
segment of 4,6.
The next step is to outpu~ the overlapping X ranges for thoss segments.
Since the algorithm is still dealing with the Sirst rectangle of the first shape data
20 stn~cture (the U) while the operation has moved to the second rectangle of the
se:)nd shape data stn~cture (the T), the associated X segments for the U are
still 0,3 while thoss for th~ T are 4,6. Applying the next step (the "for next~
iteration) produces an X code output o~ the overlap o~ these two segments. It
may be determined visually {rom Fi~ure 9 tha~ these ranges do not overlap so
25 no X segment is provided as an output. Th~ same resul~ is reachecl by
applying overlap cede ~2 of Fl~ure 6 and, referrin~ to the first table of Figure7, where no output is shown for the code -2 ease.
Table 7 also lists the next se~ments to be considered as the ncxt shape 1
se~ment and tha same shapa 2 s~m~nt. Th~ ~naxt shap~ 1 s~m~nt" is 7,10
;30 ~or the algorithm is still in the first re~angle of the U data ~hapa stn~cture, while
the ~same se3ment~ of the T data shape is 4,6. Once again, ths iteration of the
- 19-
~ 13~99~
"for next~ code 9iVRS an output i~ there is an overlap. t lowever, these two
segments do not overlap so there is no output of X segments produced
according to eith~r Fl3ure 9 or to the overlap code table o~ ure 6 as
interpreted in the intersection table of Fl~ure 7.
The next step in the "for next" code for the X segment pairs using code -
1 shows that segment 1 is unchanged; ~hat is, the X segment for the da~a shape
1 is 7,10 while the X segment tor shape 2 is the next shape 2 segment. There
being no next shape 2 segment, the "~or next" code of the X segment operation
is exited because the list is exhausted, and the algorithm returns to set the next
l O comparison of Y segments.
In reviewing th~ last sets of X and Y segments last selected, it will be
noted that although an output was produced when comparing the Y se~ments,
no output was produced when comparing either of the sets of X segments.
Consequently, if no X segment is produced where a Y segmsnt is produced
l 5 there is no output whatsoever, and the Y segment is discarded.
At this point, the program sets the next Y segment cornparison based on
the last Y code comparison. The last comparison was of Y(4,6) and Y(4,11)
and was a code 2 comparison under the first table of Figure 7. Referring to
this table, it will bs seen that the next shape 1 segment is Y(6,9~ is to be
compared to P12, P22 from the last comparison. P12 in the last comparison
was 6 while P22 was 11. Cons~quently, ~hs two segments ~o be compar~d are
Y~6,9~ and Y(6,11). For ~his iteration o~ the ~or nextW loop, a Y code output
~qual to the overlap ot ths two segments may be ssen to ba Y(6,9). This same
r~su~ is reached utilizing overlap code 2 of ~l~ur~ 6 which lists an output of
2~i P11, P12 also equal ~o 6,9.
At this point th~ algorithm moves to sst the initial X ran~es for the last Y
segment comparison. These are seen from Fl~ure ~ to be eqlJal ~o X(9,10)
and X(4,7). Th~ Yor next~ loop is then ent0r~d, and an X code output is
prodwc0d equal to the overlap ot these two s~ments or X(4,6). The same
output is shown to be the r~sutl of the overlap code 3 of Fi~ure ~ (an output otP21, P2~). At ~his point, the n0xt X se~ments are set based on the X cod~.
--20--
, .
1 3 ~
C)v~rlap code 3 shows that the next X segment o~ shape 1 is P22, P12 or
X~6,10). However, the next segment of shape 2 according to X code 3 is ths
nex~ shape 2 )( s~gment and there is none. Consequ~ntly, the pro~ram exits
~rom the X ~for next~ loop and returns to select ~he next Y segments. However,
at this point, no more Y segments are available based on the Y eoda since,
under ov~rlap code 2 (the last Y segment comparison), there is no n~xt shape
1 segment. Consequently, the algorithm exits and tha input shape is
~ornpleted.
~t should b~ noted that the last portion of the shape data structure to be
l O generated has a Y se~ment o~ 6,9 and an X segment of 4,6. Consequ0n~1y, a
total intersection output shape has been produced which is th~ araa common to
both input shapes, the total single lin~ cross-hatched area in FTgure 9.
~EE~N~
l 5 Figure 9 may also be utiliz~d to describe the operation of difference
utilizing the two shape data structur~s illustrated therein. As explained above,the difference operator produces an output shape which describes the area
contained in on~ input shape but not in the other. It can be used to comput~ thevisible areas of a window which is overlappad by oth~r windows.
Th~ differ~nce algorithm processes segments in pairs in the mannar of
the intersection algorithm which is d~scribed above. Again, the first two Y
segments ars compared ~or each shape, and an output segmen~ is put into th~
output shape. Than the corresponding X differences are computed. Parts o~
the first inpu~ shape which do not overlap the sec~nd are included in the output2~i shaps. Non-overlapping par~s of the second shapa are discarded. If the
sesmants do not overlap, the current shap~ 1 s~rnent is appended. YVhen the
snd of the second shape is reached, any remainir~ en~ri~s from the first shape
are copied into th0 output shape. Whsn the firs~ shape is exhaust~d, the
pro~ram is ~xited.
~o The difference al~nthm in pseudocode fosm is as follows:
If shape 1 ~s ampty, r0tum th~ ~mpty shape.
-21--
.
, ' ~
1 3 ~ 0
If shap~ 2 is emp~y, return shape 1 .
If boundin~ boxes do not ovarlap, rsturn shaps 1 .
Get initial Y ranges in Y11t Y12, Y21, Y22-
For next ssgment pair
Yoocle = Overlap (Y11~ Y12, Y21~ Y22)
If Y ranges overlap, output difference of Y ranges
If Y output produced, output X ranges from shape 1
Output overlap of Y range
Output difference of X ranges
Get initial X ranges in X11~ X12. X21. X22 .
For next s~gment pair
Xcod~ = Overlap ~X11~ X12. X21. X22)
If X rang~s overlap, eutput diff~renc~ of X range (based
on Xcode)
l S Set X~ 1. X1 ~. X21, X22 (based on Xcod~)
Advance shape 1 or shape 2 (based on )(code)
Exit if either X list exhaust~d
If shape 2 advanced last, Outpu~ X1 1 X12 and remainder of
shape 1 X list.
Set Y1 1, Y12. Y21, Y22 ~based on Ycode)
Advance shape 1 or shape 2 ~based on Ycode)
Exit if eith~r inp~ shap~ exhausted
Output remainder of shape 1
2S Usin~ this algorithm, two types of Y ran~es are appended to th~ output
shape. Whsn the first segment of the pair bsin3 compar~d is to the left o~ its
partner, the Y ran~e which does not overlap is produced as an output. The
cur~nt X l~st from shape 1 is also add~ to the OlltpUt. If the ~gmants overlap,
the ovarlappiny Y r~n~a is then added to lth~ output shap~. The differencs ef
the alrrant X se~ments from shape 1 and shap~ 2 follows. If no X pairs ar~
appended by thTs St9p, th0 prevlous Y tan~ 91~VQd.
--22--
13~9~0
The difference operation for the X dimension is sirnpler ~han the Y
differenoe operation. X se~ments from shape 1 output and segments frorn
shap~ 2 ar~ skippsd until an overiap in X segn ~nts is encountered or the end
of either X list is reached. The ~iff~renoe of the pair of segrnen~s is then
5 produced as an output and scanning continues.
The following briefiy describes tha application of the difference operator
to the two shapes of Fi~ure 9. Those shapes are to be treated as they were in
descripUon o~ the intersection op~rator, that is, the U is c~nsidered to be shape
1 while th~ T is considered to be shape 2.
The first step of the algorithm takes care of the case in which shape 1 is
empty, not the case in this instance. The second step of the algorithm r~turns
tha complete shape 1 when shape 2 is ampty so that th0re is an output of the
complete shape 1 . Step 3 returns shaps 1 wh~re the boundin3 boxas of the
two shapes do not ov~rlap.
l 5 For the more intrioate operation in which the segments oYeriap~ the first
step in the algorithm is to select the initial Y ranges. These of course are Y(0,6)
~rom the U shape and Y(2,4) from the T shape. F~r ~he initial segment pair a Y
eode is detenn3ned d~pending on the overlap. Fi~urf3 6 shows the ov0rlap to
be a code 3 overlap. The difference table of Fl~ure 7 shows tha~ a cod~ 3
20 overlap produces an output of P11, P21 or a Y ssgment of 0,2.
If a Y output has been produced in the first step, the X ranges from shape
1 are also producsd as an outpuS. These ran~es are 0,3 and 7,10. Since a Y
range was produced, this produces two r~ctangular box~s having Y
dimensions ~rom 0 to 2 and X dirnensions from 0 to 3 ar~ 7 to 10.
2~; The next step of the algonthm is to olJtput the overlap ot ~he Y ran~es. It
may be determined from the differ~nce opsratjon proces~in~ t~ble that the
overlap of the Y ranges is a Y segment of 2,4. The algor~hm then outputs th0
differallc~ of the X ranges. Th~ al~orithm s~lacts the initial X ran~s tor tha two
shapes. These X ran~es ar~ X(0,3) tor th0 U shape and X(1,9) tor the T shape.
30 Th~ ~tor next~ loop is then an~0red, and an X code is provid~d which is
d~termined by th0 ovarlap ot th~ two X se~mants. If the X ran~es overlap, th~n
-23-
1 3299~
tha diff~r~nc~ of the X ranges bas~d on this X code is provided as a output. In
this oase, Fl~ure 6 show an overlap code 4 which produces an output of P1 1,
P21 or an X se~m~nt of X(1,2). Th~ n~)~t X segments ar~ set usin~ cod~ 4 to
the next shape 1 segm~nt (7,10) and to P12, P2~ or X(3,9). A new X code
S ~qual to cod~ 1 is determined for ~hese segments from the overiap code of
Fi~ure $. This produces an output which is the difference of th~ X ran~e
based on the X code or, according to code 1 in the difference table ot Figure
7, nothing.
The next X segments are set based on code 1 to P22, P12, or X(9,10)
and the next shape 2 segment. There being no next shape 2 segm~nt, the X
"for n~xt~ loop is exited, and an output is produced whioh is X11, X12 and the
remaincier of the shape 1 X list if no shape 2 segment remains. This being the
case, the X~9,10) is provid~d as an output.
This produces two additionai r0ctangles having Y dimensions of Yt2,4)
1 5 and X dimensions of X(0,1 ) and X(9,1 û). The X portion of the algorithm is
exi~ed, and the n~xt Y segrnents are set based on the last Y code cetting. The
last Y code set~ing was a code 3 comparison ~f Y(0,6) and Y(2,4).
Consequently, the next segment 1 is Y(4,6) and segment 2 is Y(4,11 ) as is
shown by the differenc~ table of Fi0ure 7.
The algorithm loops back to the baginning of the ~for next~ loop and
detemlines a Y code based on th~ overlap of these two segments. The first
comparison to be made is a code 2 comparison to produce an output based on
the overiap of th~ Y segments. The code 2 overiap in the difference table of
Fl~ur~ 7 shows that no output is produced. Consequently, the n~xt -~tep
Z5 (which is to output the X ranges from th~ shape 1~ is omit~ed because ~here is
no Y o~put produced at the prcvious s~ep.
The al~orithm mo~/es to output the overlap of the Y ran~es, a se~ment
havin3 a valu~ of Y(4,6), and then moves to ths X differ~nce d~termination
portion of the algorithm. The initial X ssgments are s~lect~d. These ar~ (0,3)
for the U shap~ and (4,6) for the T shapa. If thesa X ran~es ov~rlap, an output
is pr~duo~d which is th~ diff~r~nce of th~s0 s~gment ranges based on the X
--2~--
~329~
code. The ranges in this case overlap in acoordance with the -2 oode to
produce an output of P~ 1, P12 which is X(0,3). The next X segrnents are set
based on this cod~ to the next shape 1 se~ment or X(7,10) and th~ unchan~ed
shape 2 segment of X(4,6). The ovcrlap is det~rmined from Fi ure 6 to be a -
S 1 code overlap producin~ an output of nothing. The next X se~ments to be setby the -1 code ar~ a segment 1 of X(7,10) and the next shape 2 segment.
There is no next shape 2 segmen~ so the "~or next~ loop is exite~, and X11,
X12, the segmen~ X(7,10) is produced as an output.
At this point two more rectangles have been formed in th~ output shape
10 by sagments Y(4,6) and X(0,3~, )((7,10).
The next set of Y segments are selected based on the last Y comparison
which was of Y(4,6) and Y(4,11), a code 2 comparison. Thùs, the next Y
segments are the next shape 1 Y segment which is Y(6,9) and the shape 2 Y
segm~nt Y(6,11). These two segments produce a Y code based on the oYerla
l 5 code 2 and an output of nothing. There being no ou~put at this step, no X
ranges are produced a~ an output from shape 1. The algorithm moves to ou~pu~
the ov~rlap of the Y range which is Y(4,6) and to ou~put the difference of the Xranges. In the X portion of the loop, the ne~t X segments are chosen. These
s~gments are X~0,10) for the U shape and X(4,6) for the T shape. The overlap
ZO cod0 is code 3 producing an output of P11, P21 or X(0,6~. The X shapes are
advanced to the next segments which ara P22, P12 or X(6,10) and the nex~
shape 2 segment. There being no next shaps ~ segment, an ou~put is
produced which is X11, X12 or X(6,10).
This produces ~wo more rectangular boxes having Y seg~n~nts of Y~6,9)
25 and X s~gments of X~0,6) and X(6,10). The algonthm looks ~or th~ next Y
~gm~nts and ~inds no nex~ shape 1 segment. Consequently it ~xit~ and
producQs as an o.np~ the remainder of shape 1. There is no remaind~r of
shap~ 1; consequently, ~he al~orithm has been complet~d and ffle fi~ur~
~hown in doubls cross hatchin~ of Fi~ur~ 9 is produced as an output shape.
--Z5--
~3~99~
IJNION
Ths application of the union aigorithm will bs treated only bnefly since
the operation should be apparent to those skilled in the art in ViBW of the
complete descriptions ~iven for the int~rsection and difference algorithms.
s The algorithm for union is:
If shaps 1 is empty, return shape 2.
If shape 2 is empty, return shape 1.
Get initial Y ranges in Y11~ Y12~ Y21. Y22
I o For next segment pair
Ycode = Overlap (Y11, Y12. Y21. Y22)
If overlap in Y range
Output the smallest valued Y range of one segment which
does not overlap the other segment (cases shown in
l 5 Table 1 b~low)
Output X ranges of segment corresponding to Y range output
above
Output overlap of Y ranges
Get initial X rang~s in X11~ X12. X21, X22
For next segment pair
Xcode = Ov~rlap (X11, X12. X21, X2)
Output X range (based on X cod~ as shown in
Fl~u~e 7)
Set X11. X12. X21. X22 (based on Xcode)
P~dvance shape 1 or shape 2 (bas~d on Xcode~
Exit if either X list ~xhaust~d
Output r~mainder of X lists
Else
Output the small~st valued ~ range in ei1her segment
--26-
~ .
1329~Q
Output X ranges o~ segment oorresponding to Y ran~e output .
above
S~t Y11. Y12. Y21. Y22 (based on Ycode)
Advance shape 1 or shape 2 ~based on Ycode)
Exit if either input shape exhausted
Output remainder of shapes
Table 1
Y Code Minimum Non-overlapping Shape X List
Y Range Derived From
2 P21 P11 shape 2
-1 P21 P22 shap~ 2
P21 P11 shaps 2
-2 P11 P1~ shap~ 1
4 P11 P21 shap~ 1
3 P1~ P~l shape 1
The algorithm ~or union is similar to the intersection algorithm except that
those paRs of the input shapes which do not overlap are copied to the output
20 shape rather ~han being discarded. When this algorithm is applied to the two
shapes ef Fl~ure 9, th~ rasulting outpu~ shape data structure is ~qual to the
total of th~ two structures shown in Fi~ure 9. The union sement prooessin~ in
completsly described to thos~ skilled in the ar~ by the algarilhm giv0n above,
Fi~ures 6 and 7, and Table 1 above. The union opsrator allows complex
25 shapQs to be built up from simpl~r shapes.
Although th0 inv~ntion has b~en described with r0far0nce to par~icular
arran~emen~s and sys~ems, it will be apparent to thos~ skill~d in tha a~t that tlle
details of thos~ arran~em~nts and systems are used for illustrative purposes
and should not ~e ~a~n as lim-itations of the invention. It will be clear that the
30 methods and apparatus a7 this invention have uUlity in any application wher0
~raphic r0prss~nta~ions on a cathode ray tube or other output devic~ are
--27--
--^` 132~0
d~sired. It is, thus, to be eontemplated that many changes and modifications
may be made by thos~ of ordinary skill in the ar~ without departing from the
scope and spirit of the invention~
--28--
