L E Z I O N E " L E O N A R D O F I B O N A C C I ,, 1 9 6 6 : (*)

C O B [ P U T E R G R A P H I C S

M. V. WILKES The University Mathematical Laboratory - CAMBaIDGE (England)

I f i r s t saw a c o m p u t e r d i s p l a y s o m e t i m e in t h e ea r ly 1950 ' s a t P r o j e c t

W h i r l w i n d , M. I. T ; t h e y h a d w h a t has s ince become c ommon , na me ly , a

c a t h o d e r a y t u b e whose X a n d Y p l a t e s were c o n n e c t e d to a p a i r of' dig-

i t a l - t o - a n a l o g u e c o n v e r t e r s w h i c h cou ld be fed w i th n u m b e r s from t h e

W h i r l w i n d c o m p u t e r . I well r e m e m b e r t he d e m o n s t r a t i o n b e c a u s e i t exhib i .

t e d v e r y c l ea r l y the t y p e of m i s t a k e t h a t a p r o g r a m m e r can so e a s i l y make .

/ ": v

Fig. 1

Mr. Cha r l e s & d a m s (who has s ince b e c o m e wel l k n o w n as t he f o u n d e r of A d a m s

A s s o c i a t e s , a n d the p r o p r i e t o r of K e y Da ta ) was s h o w i n g me the dev ice

and , t o g e t h e r , we wro te a s h o r t p r o g r a m which w o u l d p lo t t he t r a j e c t o r y of

a b a l l p r o j e c t e d f rom a p o i n t a b o v e a p lane . VVhat we saw on the sc reen

is s h o w n in F i g . 1. La t e r , we b e c a m e more a m b i t i o u s ; we m a d e a l i t t l e

hole in t h e p l ane a n d a l t e r e d the p r o g r a m so t h a t t he c o m p u t e r would

(~) I1 Consiglio Direttivo del CSCE ha deciso di istituire una lezione annnale iuti- tolaba alPinsigne algebrista pisano Leonardo Fibonacci. A svolgere tale lezione saranno chiamati ogni anno illustri studiosi nel campo della Scienza dei Calcolatori. I1 prof. M. V. Wilkes ha tenuto la prima lezione Fibonacci (1966).

260 ~I. V. WILKES: Computer

adjust the angle of project ion unti l the ball went th rough the hole. We were, of cours% expect ing to see i~ fall r ight through, bu t wha t in fact happened is shown in Fig. 2. I have often quoted this example as the ar-

chetype of a mis take made in p rogramming .

- . ~'-._~ o% ]

Fig 2

In the demons t ra t ion I have j u s t described~ there was a s imple p ic tu re presented to the user with no quest ion of the user in te rac t ing with it. The work led~ however~ ve ry shor t ly af terwards to the use of d isplays wi th a ligh~pen (known at the t ime as a l ight gun) in a U . S . Defence P ro j ec t known as SAGE. I shall describe la ter how a l ightpen enables the user to draw on the surface of a cathode ray tube.

S K E T C H P A D

The event tha t drew at tent ion to the use of cathode ray d isplays and l ightpens in general scientific work was the publ icat ion of an M. I. T. docto- ral thesis by I v a n Suther land. Su ther land described a sys tem tha t he cal led Sketchpad which, among other things, enabled sketches, mechanical d r a w i n g s and the like, to be d rawn on the screen and stored in the compute r . Ske tchpad lent i tself to the giving of very s t r ik ing demons t ra t ions which created a good deal of exc i tment among people in teres ted in eng inee r ing design. Some of them, who had not up to tha t momen t been v e r y enthu- siastic about computers , suddenly became convinced tha t all the p rob lems involved in us ing them had been solved. I t is impor t an t to stress~ however ,

graphics 261

a point well made by Suther land in the sub-ti t le of his thesis, which was <( A man-machine graphical communica t ion sys tem >>; in other words, one mus t th ink of the display with the l ightpen as a way of communica t ing with the computer . The job of mak ing the computer do what it is required to do still remains.

There were several ideas implici t in the Sketchpad development . One was the idea tha t a machine is good at doing things very precisely, whereas a human being is good at indicat ing roughly what he wants . I f a line is sketched on the surface of the cathode ray tube in a s l ight ly wavy manner , Ske tchpad will make it s t ra ight . I f the operator s tar ts drawing a line near to the intersect ion of two other lines, Ske tchpad will a ssume tha t it was in tended to s t a r t exact ly from the intersect ion. We thus have a way in which man and machine can cooperate, the man doing someth ing approxi- mately, and the machine pu t t i ng it exact ly r ight . The same principle leads to the idea of const ra in ts ; i f the opera tor draws two lines, roughly at r ight

ang l e s , he can indicate to Ske tchpad tha t they are in tended to be exact ly at r ight angles. Ske tchpad will act on this information, and however the lines are moved about af terwards they will remain exact ly at r ight angles.

Ske tchpad provides an ideal combinat ion of analogue display and digital accuracy. The data are stored quite independent ly of the display, and it is possible at a g iven t ime either to display the whole of the information with the omission of detail or to display a small par t of it in full detail. This is done b y changing the scale of the picture. I f the opera tor turns the magnificat ion up as far as possible, then he sees a detail 20 cm. square taken out of a drawing which, on tha t scale, would be 400 met res squa re ; on the other hand, by turn ing the magnificat ion down, he can compress the whole drawing into a square of 20 cm. Thus we avoid the l imitat ions of content or accuracy tha t are associated with drawings on a piece of paper of ordi- na ry size.

There are other ideas in Sketchpad. For example, one can draw an object, such as a r ivet or a bolt, and file it away as a master drawing, One can then br ing up as m a n y instances of this d rawing as are required for incorporat ion in a larger drawing. In other words, having d rawn a compo- nen t once, i t is not necessary to draw it again every t ime it is needed; this is t rue even if it is necessary to change the size or or ienta t ion of some of the instances.

The technical p rog ramming means whereby all this was achieved was the use in the computer of a da ta s t ruc ture hav ing the form of a genera- lized l inked list. I shall have something to say about such da ta s t ruc ture later, since this is an area in which in tens ive work is be ing done.

262 .~I. V. W~LKES: Com2Juter

I N T E R A C T I O N W I T H A D I S P L A Y

I n its s imples t form~ a l ightpen consists of a small photocell on the end of a rod. W h e n placed near the spot of l ight on the cathode r ay tube screen~ the photocell emits a pulse ; when this happens , the compu te r pro- gram is in te r rup ted and the sequence changed.

From the p rog rammer ' s point of view~ the l ightpen serves two d is t inc t purposes. In the first place it can be used to draw.

For this purpose the t racking program mus t cause a small c r o s s - - known as a tracking c r o s s - to be displayed on the screen. When the l i gh tpen is point ing at the centre of the cross there exists a symmet r i ca l s i tua t ion which is recognized as such by the t rack ing program and the t rack ing cross re- mains at rest. I f the pen is moved slightly~ then the t rack ing p rog ram takes the necessary action to re-centre the cross. The effect is tha t the t r ack ing cross follows the pen across the screen. The other th ing tha t you can do with a l ightpen is to use it to point at some object be ing displayed to in- dicate tha t you are about to give ins t ruc t ions re la t ing to tha t pa r t i cu la r object. P r o g r a m m i n g for this is ve ry s imple since the l ightpen will see the pulse of light~ and cause the program to be interrupted~ when the object in quest ion is being t raced out. There is thus no difficulty in ident i fy ing the par t icu la r object be ing pointed at.

There are other ways of in te rac t ing with a display. One is the obvious way of typ ing on a keyboard messages which the compute r i n t e rp re t s as ins t ruct ions re la t ing to the display. A more direct compet i tor wi th the light- pen is a joys t i ck tha t can be moved in two dimensions and controls a spot displayed on the screen independent ly of the main display. A j o y s t i c k has the d i sadva tange tha t you cannot easi ly write or draw wi th it. A be t t e r device is one inven ted a t the Rand Corporat ion and known as the R a n d tablet . This has a f la t wr i t ing surface under which are two or thogonal se ts of parallel conductors , spaced very close together . These conductors are fed with pulses which give the X and Y coordinates of any point on the t ab le t in Gray code. A metall ic pen placed on the table t will then pick up~ t h rough capaci ty coupling, pulses which represen t the coordinates of the po in t at which it is placed. These pulses are fed into the compute r and cause a spot to be displayed. The Rand table t is ve ry nice for wr i t ing once you have got used to the fact tha t the wr i t ing does not appea r under the pen bu t on the screen.

Unless some addit ional hardware is provided, however~ the R a n d ta. b l e t - or for tha t ma t t e r a j o y s t i c k - is not ve ry good for point ing, since~ every t ime the spot is displayed in the course of t rac ing out a picture~ a

gra_ph~cs 263

test mus t be made to see whether it is being displayed a t a point whose coordinates are those being pointed at. This is effective bu t t ime consuming. In order to make the Rand table t equivalent to the l ightpen as far as poin- t ing is concerned, it would be necessary to provide two ex t ra registers which a lways hold the coordinates of the pen and two sets of coincidence circuits l inking these registers to the X and Y registers of the display. I t would~ incidental ly, be be t te r not to associate these ex t ra regis ters perm't- nent ly wi th the Rand table t but to make them avai lable to the program- mer so tha t he could put any th ing there he l i k e d - - m o s t often, of course,

he would put the coordinates of the pen. E x t r a hardware of the k ind j u s t ment ioned can pay good dividends

if it enables the display to be speeded up and the complexi ty of what can be displayed wi thout flicker increased . Another example is the provision of circuits for au tomat ic edge detect ion which will i n t e r rup t the computer

whenever the spot reaches the edge of the screen. As displays get fas ter and faster - - I am th ink ing now of the speed at

which the spot moves - - the amount of l ight enter ing the l ightpen gets less and less, and this may eventua l ly lead us into design difficulties. Al ready the best l ightpens do not consist of a photocell on the end of a rod as I described j u s t hOWl instead, the photocell is located inside the cabinet and the l ight is conveyed to it along a flexible fibre-optic l ight guide. The ad- van tage of this is tha t it is possible to use a highly sensi t ive pho tomul - t ipl ier tube which would be too big to accommodate at the end of the pea itself. Expe r imen t s have been made - - not~ I think~ so far with ent i re success - - w i t h a pen depending for its operat ion on electrostat ic pickup. Anyone who r emembers the old Wil l iams tube memory will be aware tha t behind the visual spot there is a pa t t e rn of e lect ros ta t ic charge bui l t up by the electrons sprayed on to the screen; with sui table a r rangements , the electro- stat ic field from the charge can be detected ex terna l ly by means of a probe. One can thus make a pen very similar in operat ion to a l ightpen, but de- pending on electrostat ic p ickup ins tead of on optical pickup.

U S E OF D I S P L A Y S

Eve ryone who has worked with compute r displays agrees tha t they are very good fun for the programmer . W e do not ye t know how useful they are going to be. They are obviously useful in cer ta in contexts and appear to have grea t potent ia l i ty in others, a l though we have not enough experience at the momen t to make a t rue evaluat ion.

A n appl icat ion in which displays have an obvious value is communi- cation between a computer and the ope ra to r s ; this is par t i cu la r ly so in

264 M. V. WILKES: Computer

connection with the large multiple-access systems now coming into operat ion. When many people are using a machine independent ly and simultaneously, it is clearly desirable tha t the machine supervisor or manager should be able to tell what is going on. The Systems Development Corporat ion have demonstra ted a system in which there appears on a cathode ray tube a list of the users who are working at the moment, what their s ta tus is~ and what kind of service they are being given by the scheduling algori thm. I f the operator feels tha t the system is overloaded~ and tha t one of the users should be got rid of, he can take a l ightpea and cross out the name of the person concerned, who is for thwith logged out.

Another obvious use of a display is for the provision of (( soft ~) copy for use in circumstances when pr inted copy is not necessary. Examples are text editing and file inspection. For such purposes the abili ty to display characters ra the r than diagrams is usually sufficient.

In a number of organizations, displays are already being used experi- mental ly as input devices in connect ion with the preparat ion of tapes for numerical ly controlled machine tools. These applications are so far l imited to the descript ion of two-dimensional (or perhaps two-and-half-dimensional) objects. The operator draws the object on the screen and the computer ge- nerates the control tape for the machine tool. A similar method can be ap- plied to the manufacture of masks for deposited or etched circuits.

Among more speculat ive and exper imental applications of displays, is the drawing of flow diagrams as an input to a computer . W. R. Su the r l and has demonst ra ted at the Lincoln Labora tory how it is possible to draw the flow diagram of a computer program and have the program automat ica l ly generated. In another type of demonstra t ion an electronic circuit con ta in ing a number of t ransis tors and other components is drawn. The computer sets up the equat ions for the circuit, and it becomes possible to use the light- pen as though it were the probe of an oscil loscope; tha t is~ by point ing the pen at a par t icular point in the circuit one can cause the waveform existing at tha t point to be displayed. An area in which such methods are expected to have a practical application is in the design of chemical plants (flow sheeting).

T H R E E - D I M E N S I O N A L D E S I G N

I have left unti l last the most challenging application of all, namely the representat ion of three-dimensional objects. This takes us into the whole subject of computer-aided des ign; how~ for example, can we represen t a bridge, or par t of an aircraft~ in a computer and do design work on it.

graphics 265

The display of a three-dimensional object br ings one up agains t the fundamenta l difficulty tha t one mus t somehow represent the three-dimen- sional object on the two-dimensional screen. The first work in this field was by T. Johnson who adopted the form of represen ta t ion familiar in mechanical engineering~ namely project ions on to three or thogonal planes supp lemented by perspect ive views. Project ions will a lways have their value, but it appears l ikely tha t perspec t ive views will become more impor tan t as

t ime goes on. I t is not a lways easy to see the three-dimensional effect in a perspec-

t ive view~ par t icu la r ly if curved surfaces are involved, and here a very in te res t ing psychological effect has been noticed. The three-dimensional na ture of the object being displayed immedia te ly becomes appa ren t if the point of view of the observer is gradual ly changed~ so tha t to anyone looking at the screen it is as though the object were ro ta t ing in space. The effect is even more marked if the observer himself can control the movement~ for example by opera t ing a joyst ick. There is one effect tha t it is, unfortunately~ very ha rd to produce iu a computer display, namely the b lanking out of' the hidden par t s of a solid object. This is usual ly referred to as hidden line suppression and the difficulty is not tha t it cannot be done~ but tha t for any th ing like a complicated d iagram the computa t ion t ime becomes very great . I f one wants rotat ion as well~ so tha t the display has cont inual ly to be re -computed for a different point of view of the observer~ exist ing computers are not fast enough to d isplay any th ing more complicated than

a simple cube. The use of stereo displays in which sl ightly differing p ic tures are pre-

sented to the two eyes of the observer does not seem to be as a t t rac t ive in pract ice as the method jus t described. I t is possible that~ in the future~ displays as we know them will be replaced by ent i re ly original devices based on the pr inciples of holography. The s t r ik ing resul ts tha t have been obtained by the use of these principles in photography are well-known. One feels tha t i t should be possible to app ly them to the genera t ion of compu- ter displays, bu t so far no proposals tha t appea r at all p rac t icable have been made.

D A T A S T R U C T U R E S

I would like now to say someth ing about data s t ruc tures and the way in which they are constructed. We have~ of course~ very litt le experience so far in this subject. Everyone is familiar with the big advances in com- puter p rog ramming tha t have come with the in t roduct ion of list s t ruc tures

266 M. V. WrLKES: Computer

such as are used in I P L and LISP . These s t ruc tures m o d e l v e r y closely the bracketed expressions tha t are used in mathemat ics . I t would be possible to use them to represent geometr ical objects, bu t the process ing t ime would be long. People are~ therefore, beginning to exper iment wi th s t ruc tures which cor- respond much more closely to the s t ruc tu re of objects in the physical world.

In ord inary list s t ruc tures , the basic e lement is a single m e m o r y re- g is ter into which are packed two pointers and possibly, also, a few bi t s of information. In the type of s t ruc ture tha t I am about to describe, the basic element is a block containing a n u m b e r of consecut ive memory r e g i s t e r s ; these are divided into two groups, one conta ining informat ion and the o ther containing pointers . Such a block may be drawn as in Fig. 3. The words

~ i - I NFORIHATION

Fig. 3

POINTERS

above the heavy line contain the information, which may be a lphanumer i c or numeric or a mix tu re of the two. The words below the heavy l ine con- tain pointers. Each pointer is to be though t of as po in t ing to a word in

some other block of registers . As an example, take a data s t ruc tu re in tended to const i tu te a model

of a te t rahedron and to represent correct ly the re la t ionships tha t ex i s t be- tween the four vert ices, the four faces, and the six sides. The s t r u c t u r e is shown in Fig. 4. The top block represen ts the ent i re object and, in the par t g iven over to data , there is the word <( t e t r ahedron )) coded into as m a n y computer words as are necessary. There migh t also be in this section some numer ica l information about the par t icu la r t e t r ahed ron in

g~'aphics 267

b

I

I

I I i I I

A I I I

F I i r I I r . . . . . .

I 1 I I

I I I t

I . . . . . r ' - - - - T - - I t

J r" . . . . . V'-

' I 1 I

I I I r I 1

L _ . I . _ _ . J

I I I I

Ji

i j i I r . . . . I i l

N

. . . . . . . . J L

I I I I I ! I I I I

i I

I t

' I f i I I I I I I I I I I I I

' I

268 ~I. V, WILKES'. GO?Y~01$1~e~"

question~ for example its volume. The four lower blocks represen t the ver- t ices A, B, C, 1). These are l inked together and l inked to the block r e p r e s e n t ing the whole t e t rahedron by a chain of pointers . Such a chain I shall te rm a ring, and by going round this par t i cu la r r ing one visi ts the four points tha t make up the te t rahedron. The blocks represent ing the ver t i ces are l inked in groups of three by four other r ings. Each of these r ings represents a face since by going round it one visi ts the three po in t s tha t lie on a par t icu lar face. The blocks represen t ing the vert ices con ta in the names of those ver t ices and could contain other information such as their car tes ian coordinates. I t will be seen t ha t wi th the data s t ruc tu re j u s t described~ one can move from face to face by going up and down in a g iven block, and from ver tex to ver tex by moving round a pa r t i cu la r ring.

A more elaborate data s t ruc ture is shown in :Fig. 5. This r ep re sen t s a spade which is regarded as be ing made up of a handle~ a shaft , and a blade as shown. Here the data s t ruc tu re contains informat ion a b o u t each part , for example its name, catalogue number , and price~ and s imi la r ly for the entire object. Connected to each pa r t there is a r ing conta in ing infor- mat ion tha t will enable a p ic ture of tha t pa r t to be drawn on the screen. The blocks on these la t ter r ings have in thei r information sections the name of the segment to be drawn (a line or an arc), and in addi t ion (but not shown in Fig. 5) the size of the segment~ and a reference to a sub rou t ine tha t will do the actual drawing.

W h e n problems of memory space al location and dynamic g rowth are t aken into account, the subject of da ta s t ruc tu res becomes quite complica- ted~ and it is one tha t is advanc ing rap id ly a t the presen t time.

Da ta s t ruc tu res are merely ways of s tor ing information. In order tha t they may be used, there mus t be a lgor i thms which will ex t rac t the neces- sa ry data and perform the actions required. For example~ there migh t be an a lgor i thm which would go round the r ing represen t ing the en t i re object and make a list of its par t s together wi th their prices. Ano the r a lgor i thm would also go round, bu t would make a detour in each block to go round the subs id ia ry r ing defining the p ic ture and display it on the screen. Pro- g r amming languages are now being developed to faci l i ta te the cons t ruc t ion of data s t ruc tures and the wri t ing of a lgor i thms for man ipu la t ing them.

D I S P L A Y S I N A T I M E - S H A R I N G E b T V I R O ~ M E N T

The s impler appl icat ions of displays t ha t I ment ioned above are possible with a small compute r fitted with a display. The others need a la rge com- puter and could only be justified economical ly if the display were a termi-

grapldcs

r I I

I I I I_

Q Z t..~

I m p " lj

!

!

I

II1 l

A , _ . 1

!

A

J

/

A i t - - - - - - -I

I ,

J

I I I

I i

i

II

D

D

269

W 0

_1

ILl

0 Z

mr

I-" I1.

W ,'-I

270 ~I. V, WII,KES: Computer

nal on a mult iple-access t ime-sharing system. Most of the other users on such a sys tem would be people working with ord inary t e le type consoles.

Each user on a multiple-access sys tem only receives service in te rmi t - t en t ly since he has to wait for his tu rn with all the other users . A user with a display, however, requires tha t for cer ta in services he shall receive ins tan taneous r e sponse ; for example, the display i tself mus t be an imated , tha t is repea ted ly t raced out on the tube, and there mus t be ins t an t response to the l ightpen, whe ther it is used for drawing or point ing. Ro t a t i on of the display to give a three-dimensional effect also requires ins tan t response. One is therefore led to the ideu tha t there should be a small digi tal compu- ter associated with the display, and tha t this compute r should be responsi- ble for the an imat ion of the display and for g iv ing the immedia te response of the k ind j u s t mentioned. Suggest ions have been made as to ways in which l ightpen response and image ro ta t ion could be achieved b y ana logue means. I n the long run, it is possible, bu t by no means certain, t h a t these will p rove a t t r ac t ive on the grounds of cost, bu t the problem of a n i m a t i n g the d isplay will still remain.

I would now like to say something about the problems of connec t ing a small compute r to a large one in such a way tha t it can be run under t ime shar ing. The two computers mus t be connected by a da ta channel capable of pass ing da ta in ei ther direction. There mus t also be a pa i r of in t e r rup t channels, one of which is used by the large compu te r to send an in te r rup t signal to the small computer , and one by the small compute r to send an in te r rup t s ignal to the large computer . In other words, e i ther computer mus t be able to in te r rup t the other. The large compute r can ex- pect an immedia te response from the small one, bu t the large one may take some t ime to reply.

The large compute r runs under the control of a supervisor which p r o - vides the t ime-shar ing service, and is, in par t icular , responsible for the shar ing out of t ime between the var ious users. The small compu te r also needs a superv i sor and, in order to avoid confusion, I will refer to this as the executive. The funct ions of the execut ive are three-fold ; in the first place it has to cause the picture to be displayed r epe t i t i ve ly ; secondly, i t has to respond to in te r rup t s which can come from var ious sources , for example from the large computer , from the l ightpen, or from the opera to r ' s keys or j o y s t i c k ; thirdly~ it has to handle communica t ions wi th the large computer .

Since there is no point in the small compute r being any la rger than is absolute ly necessary , it is of in teres t to discuss what are the minimal communica t ion facilities tha t mus t be provided b y the execut ive rout ine . These are :

graphics 271

(1) To accept from the supervisor an address in the memory of the

small machine to which a block of binary information later to be sent along

the data link is to go. (2) To accept the block of information and put it in a specified place.

(3) To accept from the supervisor an address in the memory of the

small machine and to send control t o that address. I f the supervisor had occasion to send a block of data over to the small

machine~ then it would on completion of the operation send control back

to the executive. If, on the other hand~ the block of information sent over were a program, it would send control to the beginning of tha t program.

I f data in the small machine have to be sent to the large machine~ the

supervisor first sends over a program which will~ when executed~ cause the required transfer to take place. I t then sends control to tha t program~ and

when the program has finished control reverts to the executive. We have here a situation iu which the supervisor may be said to be

in overall charge of everything that goes on ; the small machine is allowed, as it were~ no life of its own. I f a program has to be executed in the small

machine~ that program is first prepared in the large machine and then sent over~ in b inary form, ready for running. All the software necessary for running programs in the small machine - - compilers, assemblers~ loaders,

etc. - - are~ in fact to be found in the large one. The supervisor keeps a

storage map for the small computer so that information is constant ly available to it about everything that is in the memory of tha t computer

and where it is located.

D I S P L A Y T A B L E S

A picture on the screen is built up from points and short lines

drawn by the moving spot. Ideally, the whole picture should be drawn a sufficient number of times a second for there to be no apparent flicker

but~ in practice~ with exist ing displays some flicker must be tolerated when the screen is full. The use of an after-glow tube makes it possible

to work~ al though with some discomfort for the operator~ even when there

is severe flicker. Detailed information for the drawing of the individual points and lines

tha t make up the display is held in the memory of the small computer in

the form of a display table. Since the number of memory access cycles available in a given time is a l imiting factor, a paramount consideration in the design of a display system is that information should be efficiently

packed in the display table. This is a matter for the hardware designer primarily, a l though of course the programmer is expected to make the best

use that he can of the facilities with which he is provided.

272 .~I. V, W I L K E S : Computer

The display table is something which is computed special ly each t ime a picture is to be displayed. I t is thus quite different from the data s t ruc ture . The data s t ruc ture contains a descr ip t ion of an ent i re object, t oge the r with all re levant in fo rma t ion ; a t any par t i cu la r t ime only a small pa r t of the information contained in the da ta s t ruc tu re is to be d isplayed on the screen. Suppose, for example, tha t the user is des igning a b r idge and will, therefore, have a data s t ruc tu re which represen t s the s t r u c t u r e of the bridge. The data s t ruc ture could, and p robab ly would, r ep re sen t the s t ruc tu re of the br idge in very grea t detail down to the ind iv idua l g i rders and even the single nuts and bolts. A t any g iven time, the user would not be able to d isplay all this informat ion on the screen, even if he wan ted to. H e would, however, be able to display, for example, an out l ine d rawing of the entire br idge or a detail of one small piece. I t would be necessary , therefore, to have a p rogram which wou ld opera te on the da ta s t r u c t u r e ex t rac t from it the re lewmt informat ion (for the outl ine d rawing or for the detail as the case may be), and const ruct the appropr ia te d i sp lay table.

In the case of a stat ic display, the display table can be gene ra t ed in the large compute r and sent to the small compute r in a form su i tab le for immediate use. This cannot, however, be done if the object to be d isp layed is a three-dimensional one, and is to be ro ta ted under the control of the operator . In this case~ an appropr ia te ex t rac t from the da ta s t r u c t u r e mus t be sent over to the small computer and the final s tages of p r e p a r i n g the d i s p l a y table completed in tha t computer .

Immed ia t e response for such purposes as t r ack ing the l i gh tpen and ro ta t ing the display is provided by the small computer , bu t any subs t an t i a l piece of work mus t be done in the large computer , and here, of course, the user of the display mus t be p repared to wai t his turn . H e m u s t be provided with some way in which he may indicate t ha t he wants a t ask done. I n the j a rgon tha t has grown up, he sets up or~ s t r ic t ly speaking , causes the execut ive to set up, an a t ten t ion . Suppose~ for example, he wishes to delete a line f rom the display and to make the cor responding delet ion in the data s t ruc ture . He points to the line wi th a l ightpen and t y p e s an appropr ia te charac te r or set of characters . An a t t en t ion is then set up b y the execut ive and, when in due course the user ' s p rogram in t h e large computer receives an allocation of time~ the a t t en t ion is serviced a n d the appropr ia te act ion taken. A n u m b e r of a t t en t ions m a y be set up b y the user of the d isp lay while he is wai t ing for service from the large c o m p u t e r ; these are stored and dealt with in tu rn when the t ime comes. I t is desira- ble tha t some indicat ion should appear on the screen when an a t t en t ion is set up. For example, i f the user has set up an a t t en t ion to cause a line to be deleted, then perhaps the le t ter D migh t appea r on the screen

graphics 273

by tha t line to show that the a t tent ion has been set up. As soon as the a t tent ion had been serviced, the le t ter would disappear .

I t will be apprecia ted fl'om what I have said tha t there is a good deal of traffic be tween the two computers , t ha t is be tween the execut ive and the supervisor . This does not ma t t e r if the small compute r is located phy- sically very close to the large computer~ bu t problems arise when they are separa ted by a significant distance. I f a data channel with a narrow band- width is used, then the rate of t ransmiss ion may be too low for the user to be g iven a good service. On the other hand, a channel of wide bandwidth , while per fec t ly feasible~ is very costly. W e do not, at the presen t time~ know very much about the op t imum way to make use of a channel of restr icted bandwidth~ nor do we know how much bandwid th is real ly necessary to give a useful service to the user. These, and similar problems~ are l ikely to receive much a t ten t ion in the immedia te future .

Acknowledgements

The main pioneer work in computer graphics has been done at M. I. T., both a t Pro jec t MAC and at the Lincoln Labora tory , and I owe much to conversa t ions with my friends there. I am also indebted to m y colleagues in Cambridge, par t icular ly to Mr. Charles Lung who gave me val.uable advice on the p repara t ion of this lecture. The example in :Fig. 5 is due to Mr. Lang and, in the section on displays in a t ime-shar ing envi ronment , I have drawn heavi ly on unpubl ished work at present in progress under his di- rection.

274 M. V. WILKES: Comzvuter

B I B L I O G R A P H Y

SUTHERLAND, I. E. (~ Sketch~ad : a man.machine graphical communication system. >) Tech. Report No. 296, Lincoln Laboratory, M . I . T . 1963.

SUTHERLAND, I. ~E. (~Sketchpad: a man.machine graphical communication system ~>. AFIPS SJCC Conference Proceedings, Vol. 23, p. 329, Spar tan Books. 1963.

SUTHERLAND~ W . R . (( On-line graphical specification o f comp~ter procedures ~. Tech. Repor t No. 405, Lincoln Laboratory, M. I .T . May 1966.

ROBERTS, L. G. (( Machine perception o f three-dimensional solids ,~. Tech. Report No. 315, Lincoln Laboratory, M . I . T . 1963.

JOHNSON~ T. E. (~ Sketchpad I I I , 3 - D graphical communication with a digital com~puter ~).

Tech. Report No. ESL-TM-173. ESL, M . I . T . May 1963. HArtlNG, D. R. ~ The Beam Pen : a novel high-speed~ imput/outlgut device f o r cathode ray t~tbe

dis2iay systems ~). AFIPS FJCC Conference Proceedings, Vol. 27~ Pt. 1, p. 84:7, 1965. D.4.vIs, M. R. & ELLIS, T.O. ~ The R A N D tablet: a man-machine graphical communicatiou

device ~. AFIPS FJCC Conference Proceedings, Vol. 26, p. 325. 1964. Ross, D. T. <~ General descri2tion o f the A E D - 1 processor and the display interface system )~,

Memorandum MAC-M-No. 312, M. I. T. 1966.