UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Interfacing a high-level graphics language with the GSPC machine model Mannhardt, Christian 1980

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1980_A6_7 M36.pdf [ 7.12MB ]
Metadata
JSON: 831-1.0051807.json
JSON-LD: 831-1.0051807-ld.json
RDF/XML (Pretty): 831-1.0051807-rdf.xml
RDF/JSON: 831-1.0051807-rdf.json
Turtle: 831-1.0051807-turtle.txt
N-Triples: 831-1.0051807-rdf-ntriples.txt
Original Record: 831-1.0051807-source.json
Full Text
831-1.0051807-fulltext.txt
Citation
831-1.0051807.ris

Full Text

INTERFACING A HIGH-LEVEL GRAPHICS LANGUAGE WITH THE GSPC MACHINE MODEL by CHRISTIAN MANNHARDT B . S c , The U n i v e r s i t y of Cape Town, 1976 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE :A i n THE FACULTY OF GRADUATE STUDIES (Department o f Computer S c i e n c e ) We a c c e p t t h i s t h e s i s as conforming to the r e q u i r e d s t a n d a r d THE UNIVERSITY OF BRITISH COLUMBIA May 1980 (c) C h r i s t i a n Mannhardt, 1980 I n p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e a n d s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g o f t h i s t h e s i s f o r s c h o l a r l y p u r p o s e s may be g r a n t e d by t h e Head o f my D e p a r t m e n t o r by h i s r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . D e p a r t m e n t n f C o m p u t e r S c i e n c e T h e U n i v e r s i t y o f B r i t i s h C o l u m b i a 2075 W e s b r o o k P l a c e V a n c o u v e r , C a n a d a V6T 1W5 ABSTRACT Recent e f f o r t s i n computer g r a p h i c s t o d e s i g n a g r a p h i c s s t a n -dard have c o n t r i b u t e d much towards the c o n c e p t u a l c l a r i f i c a -t i o n o f b a s i c o p e r a t i o n s such as m o d e l l i n g , d i s p l a y and t r a n s -f o r m a t i o n f u n c t i o n s . T h i s t h e s i s d i s c u s s e s how such c o n c e p t s are r e f l e c t e d i n a h i g h - l e v e l g r a p h i c s language w i t h the aim of p r o v i d i n g a t o o l t o w r i t e e f f e c t i v e and r e a d a b l e a p p l i c a -t i o n programs. The h i g h - l e v e l language i s a g r a p h i c s e x t e n -s i o n t o P a s c a l . An i n t e r f a c e i s d e s c r i b e d how the m u l t i - l e v e l g r a p h i c s m o d e l l i n g system i s mapped onto a s i n g l e - l e v e l d i s -p l a y system. The p a r t i c u l a r d i s p l a y system c o n s i d e r e d i s the Core System which i s proposed as a g r a p h i c s s t a n d a r d by the SIGGRAPH-ACM G r a p h i c S t a n d a r d s P l a n n i n g Committee (GSPC). i i i CO8TESTS Page LIST OF FIG USES ........ v i ACKNOWLEDGEMENTS . . .;,;V. %V»V .... . . , v i i Chapter 1. IHTEGDOCTION . . i . . . . v . ........ . 1 2. COHFOTEB GSAPHICS SOFTWARE AKD HABBHARE 5 2. 1 H i g h - l e v e l Graphics Languages ;*^.;i-wj.«4-v... ,.„• 6 2. 2 LIG # Concepts and Improvements ........w...... 12 2.3 P o r t a b i l i t y c f Software u s i n g the V i r t u a l Sachine concept 16 2.4 Graphics D i s p l a y P r o c e s s o r s 22 2.1.1 H o s t / S a t e l l i t e C o n f i g u r a t i o n s 22 2.<J.2 Hardware c f D i s p l a y P r o c e s s o r s ........... 23 2.4.3 HicroprcgraiBoed D i s p l a y Processors ....... 26 2 . 5 A c h i e v i n g Device Independence ................ 28 2.(6 Design C r i t e r i a f o r Graphics Packages ........ 31 2.6.1 l e v e l s cf P i c t u r e Naming and flodification ......................... 32 2.6.2 Co an on Graphics Packages .,..,.,.«, . . . v^ - . i 34 2.6.3 S t a n d a r d i z a t i o n c f Graph i c s C a p a b i l i t i e s . 35 2.6.4 Functions of the Core System ............. 36 . LIG/ J E LANGUAGE BiFIBENCE MANUAL ,V,.-,^*^•>*••-=< 3* 1 I n t ted oc t i c D- • . . . • • • *•«,«-• »•..... • »'«>*'.:».'•;•"»••;»• «.«/•.*:•,. •« 3,2 ter m i n o l o g y , Natation and Vocabulary • . 3. 3 Fro9cam St cocture . . . • . » ; ! v « * v « « > » * r * i . ; V W » i ^ » * » ^ i 3.4 Mo d e l l i n g f u n c t i o n s ......................... 3.4.1 Graphics Types 3.4.2 Coordinate .Systems' 3.4.3 Modelling Transformations and A t t r i b u t e s 3.4.4 the Syncnym Assignment Operator ......... 3.4.5 The Copy Assignment Cperatoe 3.4.6 G r a p h i c a l f u n c t i o n s ••.••v**V^'-«!*;<^'*^;*f-*^»i*-3.4.7 The S u p e r p o s i t i o n Operator 3.4.8 She Naming Operator ..»*..;...,...........• 3.4.9 The D e l e t i o n Operator ................... 3.4.10 The I d e n t i f i c a t i o n Statements .......... 3.5 The Dis p l a y F u n c t i o n s ....................... 3.5.1 Device D e f i n i t i o n ....................... 3.5.2 Anonymous and Named Instances 3.5*3 The D i s p l a y Statements .................. 3.5.4 D i s p l a y A t t r i b u t e s , Viewing and Image Transformations ^ ^•^:W/»'%4v*'»:Vw/»-«»>«ii«»-3.5.5 The Erase Statement •3.-6 G r a p h i c a l Input •»..... i W * V f V * V " * * * V M , f V * * : * : f ' * ' f V « ' * 3. 7 C o n t r o l statements' .:»:«^;VV,«r*:*:.:^ 3.8 Device S e t t i n g and Device I n g u i r y ........... 3.8.1 Input Device S e t t i n g .................... 3.8.2 Output Device S e t t i n g 80 3.8.3 Input Device I n g u i r y 81 3.8.4 Output Device I n g u i r y .................... 81 3.9 The A r c h i v a t i c n Statements *......,.,.,......., 82 3.10 T r a n s l a t i n g and Sunning a IIG/I Program 83 4. IHFLEBENTaTION OF TEE LIG/P SYSTEM i»*i,«..V....... 85 4. 1 The LIG/P Preprocessor ....................... 85 4.2 The LIG/P Bun-time L i h r a r y ................... 86 4.2.1 The flodelling Data S t r u c t u r e *w.i».*i.v... 86 4.2.2 The D i s p l a y Data S t r u c t u r e ............... 92 5. COHHBNTS ON TBI COSE SYSTEB „ , 97 6. CONCLUSION 100 EIBXlOGlftfBY , 101 APPENDICES A. The LIG/P Grammar ............................... 106 B. A Sample Program . . w . . , 110 C. The Bun-time System C a l l i n g Graphs .............. 117 v i FIG0BBS Figure V ............ . . . 29 Fig u r e 2- • ..... ............................ .......... .„ 51 Figur e , 3 ..... 51 Fi g u r e 4 ...................... 54 Figure 5 .................*••........................ 54 Fi g u r e 6'............................................ 65 Figure 7 ............................................ 65 Figure 8' ............................................ ., 66 Figur e S 72 Figur e 10 ^ . , » ; M V » * ^ » W W V . ^ . W V . . V ; V M : V . V 4 V ^ . . V , 72 Figure 11 ............... • ,. 88 Fi g u r e .  12- .............. . . . . . . . . . . . . . ' . • , ^ V t ^ « V w ^ i . t V . . : ; 88 Figur e 13......................................... ..... 90 Figure 14 . 91 Figur e . 15 ........ , . . v * . . - . « . ^ . . . i » . « v ; . * « ^ ; f ^ . V f ^ v . > ; ? 91 Fig u r e 16 ................ 95 Figur e 17 .v....y--*i»w.v^^ ,.; 96 Figure 18 .......................... .................. 115 Fi g u re 19 116 AGKNOWLEDGEMENIS I Mould l i k e t o express my s i n c e r e a p p r e c i a t i o n t o Dr. Guenther Schrack f o r h i s v a l u a b l e help and guidance d u r i n g the past two y e a r s , f o r a l l o w i n g me a generous amount o f h i s time, and f o r h i s f i n a n c i a l support. I would a l s o l i k e t o thank Dr. John Feck f o r h i s h e l p f u l s u g g e s t i o n s f o r improving t h i s the-s i s . I am g r a t e f u l t o my wife Evelyn f o r her pat i e n c e and f o r her help i n typi n g and f o r m a t t i n g t h i s s a n u s c r i p t . 1 Chapter 1 IHT80DUCTIGH In the f i e l d of computer g r a p h i c s the design of a Graphics Standard i s c u r r e n t l y r e c e i v i n g much a t t e n t i o n . . An attempt i s nade to f i n d a u n i f y i n g concept f o r c u r r e n t l y a v a i l a b l e g r a p h i c s hardware t o f a c i l i t a t e program p o r t a b i l i t y , device independence and "programmer p o r t a b i l i t y " . Various proposals have been put forward as a Graphics Standard; examples are the German GKS system, the E n g l i s h GXNO-F pack-age, and the Core System proposed by the G r a p h i c s Standards Planning Committee (GSPC) of the S p e c i a l I n t e r e s t Group SIGGBAPH O f the ACH. , T h i s t h e s i s i s an i n v e s t i g a t i o n of how a mapping can be achieved frcm a h i g h - l e v e l g r a p h i c s language to the f u n c t i o n s of the Core System (GSPC79J. The Core System was designed as a s u b r o u t i n e package to a c t as an i n t e r f a c e between an a p p l i -c a t i o n program and graphics hardware; i t s output f u n c t i o n s provide a p p l i c a t i o n - i n d e p e n d e n t f a c i l i t i e s to d i s p l a y a r b i -t r a r y views cf two and t h r e e - d i m e n s i o n a l g r a p h i c a l o b j e c t s ; i t s i n p u t f u n c t i o n s support the i n t e r a c t i o n between the user and an a p p l i c a t i o n program. The h i g h - l e v e l language t h a t was 2 chosen i s LIG >< ".Language f o r I n t e r a c t i v e G r a p h i c s " ) ; t h i s l a n -guage i s an extension t o e x i s t i n g h i g h - l e v e l languages which are used as "host languages". LIG was developed at the U n i v e r s i t y of B r i t i s h Columbia and uses FOfiTBAN as i t s host language £Schr78a]« I t faas been used e x t e n s i v e l y as a r e -search and t e a c h i n g t o o l and i t s b a s i c concepts have been proven s u c c e s s f u l i n terms of ease c f use and " n a t u r a l n e s s " . U G has a l s o found a p p l i c a t i o n s i n areas such as c i r c u i t design and e l e c t r o n i c music comp o s i t i o n . In the Department of E l e c t r i c a l E n gineering i t i s used f o r LSI mask ge n e r a t i o n and e d i t i n g . P a r t of the c u r r e n t t h e s i s i s the implementation of LIG as an ext e n s i o n t c P a s c a l , and the de s i g n of a l a r g e number of new f e a t u r e s f o r the language i n areas where im-provements c c u l d be made., T h i s new v e r s i o n of the language i s c a l l e d LIG/P and supports t h r e e - d i m e n s i o n a l g r a p h i c s i n con-t r a s t to the 2D-fran€«ork of LIG. LIG/P i s a t o c l t o c o n s t r u c t h i e r a r c h i c a l models of g r a p h i c a l o b j e c t s ; i t supports m u l t i - l e v e l naming and m o d i f i -c a t i o n c a p a b i l i t i e s . G r a p h i c a l o b j e c t s are d e f i n e d i n terms c f g r a p h i c a l p r i m i t i v e s , g r a p h i c a l f u n c t i o n s , and other graph-i c a l o b j e c t s ; the language t r e a t s t h e data type GRAPHICAL as a type i n i t s own r i g h t and s u p p l i e s h i g h - l e v e l o p e r a t o r s to manipulate g r a p h i c a l data. The aajor emphasis i n the c u r r e n t work i s cn the design of an a p p r o p r i a t e data s t r u c t u r e f o r the mapping of IIG/P*s m u l t i - l e v e l environment to the core System's s i n g l e - l e v e l environment. (Conceptual l e v e l s are 3 discussed i n d e t a i l i n Section 2.6. 1.) The LIG/P data base stores infornation about the user-defined graphical model; i t s display functions traverse the data structures and generate c a l l s to Core System functions.. The Core System i s based on the concept of one-level segments that are used f o r display purposes only; no modelling functions are provided at that l e v e l . The mapping puts emphasis on the e f f i c i e n t use of Core segments i n terms of creation and deletion to minimize the "segment t r a f f i c " inside the Core System. The current project i s an i n v e s t i g a t i o n cf ho* useful the Core System, i s for the automatic generation cf invocations of i t s functions. Improvements are suggested where ease of use and e f f i c i e n c y can be increased. For the implementation of the LIG/P preprocessor a com-p i l e r writing s y s t e i obtained from the University of Montreal was used [Lecar77 j . This system accepts a formal d e f i n i t i o n cf the language and associated semantic actions f o r each lan-guage construct; a compiler i s generated i n Pascal. The run-time l i b r a r y f o r LIG/P was also written in Pascal, so was the sufcset of the Cere System that was reguired for t h i s project. The output devices supported in the current implementation are a Tektronix 4027 colour graphics terminal, a Tektronix 4014 storage tube and CalCcmp plotters. The IIG/P system i s porta-ble to any i n s t a l l a t i o n supporting Pascal and the proposed Graphics Standard which i s by now commercially available.. The three major parts of this thesis are a discussion of 4 concepts t h a t l e a to the design of L I G / P , a language manual f o r L I G / P , and a d e s c r i p t i o n of the data s t r u c t u r e s r e g u i r e d to i n t e r f a c e L I G / P and the core System. 5 Chapter 2 CCHPUTEE GBAPHICS SOFTMABE AND; S A BP BABE i n a sense computer g r a p h i c s came i n t o e x i s t e n c e with John von Seumann's i d e a t o connect a cathode ray tube to a computer as an output d e v i c e £Taub63]. Another milestone was the design of SKETCHPAD by Ivan Sutherland i n 1963 [Suth63] which broke the i c e f o r i n t e r a c t i v e g r a p h i c s . Since then the i n t e r e s t i n computer g r a p h i c s has continued and made i t a spe-c i a l f i e l d c f r e s e a r c h i n computer s c i e n c e . , I n f o r m a t i o n proc-e s s i n g using p i c t o r i a l data has found many a p p l i c a t i o n s ; these range frc» passive p l o t t i n g , grey s c a l e p i c t u r e p r o c e s s i n g and documenting systems to t h r e e - d i m e n s i o n a l i n t e r a c t i v e design and s y n t h e t i c p i c t u r e g e n e r a t i o n , i n c l u d i n g shading and hidden s u r f a c e techniques. H i t h i n computer g r a p h i c s major develop-ments have taken place with r e s p e c t t o hardware d e s i g n , i n p u t and output d e v i c e s , programming languages and a l g o r i t h m s . Techniques have advanced tc a stage where c o l o u r g r a p h i c s i s a c c e s s i b l e by anyone even on in e x p e n s i v e but r a t h e r powerful and f a s t p e r s o n a l computers. 6 2.1 High L e v e l Graphics Languages As i n ether areas cf programming language design, so f a r no general-purpose g r a p h i c s language has been accepted as a " u n i v e r s a l g r a p h i c s language". Ihe a p p l i c a t i o n s f o r computer gr a p h i c s are too v a r i e d with many conc e p t u a l d i f f e r e n c e s be-tween them; the data m a n i p u l a t i o n f o r geographic data, f o r example, i s very d i f f e r e n t frcm that r e g u i r e d f o r three-dimen-s i o n a l computer-aided d e s i g n , which again i s very d i f f e r e n t from a r t i s t i c d e s i g n . , Another f a c t o r i s t h a t i n past years computer g r a p h i c s has s p l i t i n t o two separate f i e l d s : genera-t i v e computer g r a p h i c s , and c o g n i t i v e g r a p h i c s or image a n a l y -s i s . So f a r no u n i f y i n g concept f o r the two has been found. The d i s c u s s i o n i n t h i s t h e s i s i s about i n t e r a c t i v e g e n e r a t i v e g r a p h i c s , and i n p a r t i c u l a r concerned with concepts f o r computer-aided design with t h r e e - d i m e n s i o n a l data repre-s e n t a t i o n . T h i s s e c t i o n g i v e s an overview of what p r o p e r t i e s h i g h - l e v e l g r a p h i c s languages should possess and what imple-mentations e x i s t . , The survey i s by no means exhaustive but most o f the better-known systems are mentioned. One of the important e a r l y papers on h i g h - l e v e l g r a p h i c s languages was p u b l i s h e d by Kulsrud i n 1968 [ K u l s 6 8 ] ; i t p r e -sents g e n e r a l concepts f o r h i g h - l e v e l g r a p h i c s programming i n a r i g o r o u s and s y s t e m a t i c way. Kulsrud d i v i d e s g r a p h i c a l f u n c t i o n s i n t o f o u r major areas and proposes s e t s of commands f o r data d e s c r i p t i o n , manipulation, r e g i o n a l a n a l y s i s , and 7 t o p o l o g i c a l a n a l y s i s , , I t i s i n t e r e s t i n g t o note that the l a n -guage does net have commands-such as MOVE and DRAB which ac-t u a l l y are low l e v e l d i s p l a y processor i n s t r u c t i o n s . Kulsrud's language d e f i n e s , i n a d d i t i o n to common data types, the f i v e g r a p h i c a l data t y p e s : p o i n t , l i n e segment, p i c t u r e , sube lenient, and r e g i o n . I n c r e a s i n g i n t e r e s t i n computer g r a p h i c s and subsequent work i n the area has brought forward a c l e a r i d e a of d e s i r a b l e f e a t u r e s f o r g r a p h i c s languages. I t has l o n g been r e c o g n i z e d t h a t a g r a p h i c s system should provide more convenience than a simple subroutine package can. A programmer should be able to express a l g o r i t h m s i n as n a t u r a l a way as p o s s i b l e and as c l o s e to h i s problem as p o s s i b l e . , The language must provide f a c i l i t i e s f o r modular design and convenient and readable con-t r o l s t r u c t u r e s . Of p a r t i c u l a r importance are a p p r o p r i a t e data t y p e s , and these are onl y u s e f u l i f corresponding opera-t o r s are d e f i n e d . E x i s t i n g g r a p h i c s systems provide e i t h e r i m p l i c i t l y d e f i n e d data types such as a r r a y s i n APL, or ex-p l i c i t l y d e c l a r e d ones, such as the type GRAPHICAL i n LIG; the l a t t e r i s p r e f e r a b l e with r e s p e c t to w r i t i n g an a l g o r i t h m i n terms of the problem. A g r a p h i c s language most provide p r i m i -t i v e data o b j e c t s from which mere complex o b j e c t s can be b u i l t , and p o s s i b l y a l s o some often-used "advanced p r i m i t i v e s " such as ar c s and polygons. Of p a r t i c u l a r importance i s a l s o t e x t - h a n d l i n g s i n c e almost a l l g r a p h i c r e p r e s e n t a t i o n s r e q u i r e the i n c l u s i o n of t e x t . 8 Graphic i n p u t and output i s c f a d i f f e r e n t nature than that c f programs f o r other a p p l i c a t i o n s and the design of i / o statements must r e c e i v e p a r t i c u l a r a t t e n t i o n , ; Graphics i / o i n v o l v e s s p e c i a l hardware and only very r e c e n t e f f o r t s suc-ceeded i n f i n d i n g a b s t r a c t concepts f o r these s p e c i a l purpose d e v i c e s . H a l l a c e £ Wall76 ] p u b l i s h e d one of the f i r s t papers t h a t d e f i n e s v i r t u a l i n p u t d e v i c e s with the aim of a c h i e v i n g "program p o r t a b i l i t y , human f a c t o r s a d a p t a b i l i t y , economy and maximal use of t e r m i n a l c a p a b i l i t y " . The same t o p i c f o r output p r i m i t i v e s i s addressed i n a paper by Bergeron £Berge76 ]. Host of these i d e a s were i n c o r p o r a t e d i n the d e f i -n i t i o n of the proposed Graphics Standard of the GSPC. , These ideas search f c r computer-independence f o r g r a p h i c s systems; not only should g r a p h i c s a p p l i c a t i o n programs be p o r t a b l e but a l s o the run-time environment should be designed i n such a way •that i t can e a s i l y he taken from one machine t o another, with s m a l l changes only i n the d e v i c e dependent code and the rou-t i n e s i n t e r a c t i n g stith the o p e r a t i n g system. I f a h i g h - l e v e l language i s chosen f o r the implementation, many of these prob-lems are alre a d y p a r t i a l l y s o l v e d . A g r a p h i c s language must he able t o allow a c e r t a i n amount cf f i l e h andling t o f a c i l i t a t e c o n t i n u i t y between ses-s i o n s . / Oser-defined g r a p h i c a l o b j e c t s can then be saved f o r l a t e r a c c e s s or to c r e a t e a l i b r a r y of often-used g r a p h i c a l b u i l d i n g b l o c k s f o r c e r t a i n a p p l i c a t i o n s . -., 9 & language must have the a b i l i t y of imposing a s t r u c t u r e on g r a p h i c a l o b j e c t s ; these o b j e c t s o f t e n have t o be manipu-l a t e d as a whole. They are h i g h l y dynamic e n t i t i e s ( e . g . . i n computer-aided design) uhich are assigned a number of a t t r i b -utes (e.g. c o l o u r , l i n e s t y l e , t e x t s i z e ) • Often there a l s o e x i s t seme i n t e r r e l a t i o n s h i p s between g r a p h i c a l o b j e c t s , i n p a r t i c u l a r i f s i m p l e r ones are used to b u i l d more complex ones. The d e f i n i t i o n of such r e l a t i o n s h i p s must be supported ty c l e a r concepts i n the h i g h - l e v e l language and must adapt i n a n a t u r a l manner to the way i n which g r a p h i c r e p r e s e n t a t i o n s are p e r c e i v e d by the user of the system. G r a p h i c a l data bases bave complex i n t e r c o n n e c t i o n s between data items; o f t e n they are r i n g s t r u c t u r e s , l i n k e d l i s t s , t r e e s , or even combinations c f t h e s e . I n most a p p l i c a t i o n s g r a p h i c a l o b j e c t s are f r e q u e n t l y transformed with respect to s i z e , p o s i t i o n and r o t a t i o n . T r a n sformations c a r be a p p l i e d i n the modelling stage and l a t e r again when an o b j e c t i s d i s p l a y e d . These are c a l l e d modelling t r a n s f o r m a t i o n s and image t r a n s f o r m a t i o n s r e s p e c -t i v e l y and must be i n c o r p o r a t e d i n a h i g h - l e v e l language such as to make t h e i r use c o n s i s t e n t and obey the " p r i n c i p l e of l e a s t s u r p r i s e " . F u nctions of the u n d e r l y i n g g r a p h i c s sytem must a u t o m a t i c a l l y c l a s s i f y and d i s t i n g u i s h between three Kinds of data s t r u c t u r e s as d e s c r i b e d by Posdamer £Posd77]: the "topology s t r u c t u r e " w h i c h d e f i n e s the problem or the en-vironment, the "computation s t r u c t u r e " t o s t o r e data and 10 t r a n s f e r s them, and the " d i s p l a y s t r u c t u r e " f o r an output de-v i c e . A b r i e f survey of h i g h - l e v e l languages shows how some of these i d e a s have a c t u a l l y been iaplemented. The most commonly used g r a p h i c s systems a r e e i t h e r of two kinds:: pore subroutine: packages or h i g h - l e v e l language exten-sions.,, Subroutine packages have the advantage of p o r t a b i l i t y but do not a l l o w the use of data types and o p e r a t o r s . Language e x t e n s i o n s r e g u i r e an extended compiler or a prepro-c e s s o r ; some e x i s t i n g programming languages are more s u i t a b l e than e t h e r s f o r an ex t e n s i o n and are t h e r e f o r e c a l l e d " e x t e n s i b l e , , . , an example i s A l g o l 68 [Den75 ] which a l l o w s o p e r a t i o n s with prcgrammer-defined types and o p e r a t o r s . In g e n e r a l one d i s t i n g u i s h e s between two groups of g r a p h i c s l a n -guages; t h e r e are those f o r l a r g e s c i e n t i f i c programs and those f c r c o n v e r s a t i o n a l use, e.g. p i c t u r e e d i t i n g . The e a r l i e s t language, i n the f i r s t category was an exten-s i o n t o A l g o l 60. A l g o l 60 i s very c l e a n i n i t s program s t r u c t u r i n g f a c i l i t i e s , hut r a t h e r i n c o n v e n i e n t f o r data mani-p u l a t i o n (e.g. no s t r i n g h a n d l i n g f a c i l i t i e s , only a r r a y s to b u i l d data s t r u c t u r e s ) . The g r a p h i c s e x t e n s i o n s t o A l g o l 60 were LEAP, w r i t t e n i n 1968 [Bovn68, Bovn69), and SAIL,' w r i t t e n i n 1971 £Swi71}. ; Attempts to improve on A l g o l 60»s d e f i c i e n -c i e s were made i n PI/1 which uses many of the concepts d e f i n e d f o r A l g c l 60. A d e r i v a t i v e of PL/1 i s XPL with i t s e x t e n s i o n XPLG £Tur75]. The most commonly used language as a b a s i s f o r 11 graphics systems i s FOETBAN; the language i s available on almost every computer and a large variety of special purpose routines e x i s t . . For s c i e n t i f i c computing i t i s also consid-ered run-time e f f i c i e n t . .Graphics extensions f o r F08TSAN are too many to be enumerated here; examples are EXGBAF £ Will72], LIG [Schr76, Schr78a, Schr78fc], and GBIF (Gil78 ]. A very e l e -gant language i s I0LEE, designed by Birt h , for which a power-f u l rand convenient graphics extension c a l l e d EULEB-G [ Newm71 ] was designed. EOLEB-G and XPLG were the f i r s t languages that implemented display procedures. / Some experiments have also been c a r r i e d cut tc extend BCPL for graphics £Bich76J. Languages for conversational use that were extended for graphics include CPL [Ear63], BASIC [ Sharp70.], A PL £Fosd73, S t i l 7 7 ] , and LISP £Jon78]. APL provides convenient means for handling aatxices, which i s e s s e n t i a l for geometric transformations; i t also allows d e f i n i t i o n of functions which makes statements such as "PLACE SPBEBE AT (3,4,5)" a l e g a l APL statement [Posd77]. Future developments f o r graphics languages w i l l be strongly influenced by developments of graphics hardware. Like elsewhere i n the f i e l d of computer science, the advent of microcomputers w i l l have a major impact; in addition to t h i s the constraints of limited and slow memory are removed. New hardware systems w i l l allow implementation of concurrent proc-essing and through language constructs the programmer w i l l have control ever timing of evaluation. Data models w i l l i n -12 i elude f a c e t e d polygons and patch elements t h a t are used to compose free-form s u r f a c e s . V a r i o u s i d e a s e x i s t on how t h r e e -dimensional i n p u t and output can be achieved £Bies78]; the programs f c r such systems w i l l e v e n t u a l l y be w r i t t e n i n high-l e v e l languages. 2.2 1IG. Concepts and Improvements The p a r t i c u l a r h i g h - l e v e l language s t u d i e d more c l o s e l y i n t h i s t h e s i s and used to implement some of the demands made i n S e c t i o n 2. 1 i s IIG ("Language f o r I n t e r a c t i v e G r a p h i c s " ) . I t was o r i g i n a l l y designed i n 1972 at the U n i v e r s i t y of B r i t i s h Columbia; s i n c e then many improvements have been made to the language i t s e l f and i t s run-time environment, and i t has been used f o r many years by graduate and undergraduate s t u d e n t s . For two years now the language has been taught i n an i n t r o d u c t o r y g r a p h i c s course £Schr78a ]. LIG i s an extension t o FGETEAN, and although i t i s de-f i n e d as a language by i t s own i t takes advantage of FOBTBAN•s num e r i c a l , boolean and a l g o r i t h m i c c a p a b i l i t i e s . A preproces-sor t r a n s l a t e s a LIG program i n t o an i n t e r m e d i a t e FOBTRAN pro-gram i n which the c r i g i n a l g r a p h i c s statements appear as sub-r o u t i n e c a l l s . The s u p p o r t i n g LIG subprogram system, w r i t t e n i n FCBTBAK f o r c o n s i s t e n c y , handles g r a p h i c a l i n p u t , output end data base manipulation. LIG's data type GBAPHICAL can represent the kind of i n -13 f o r m a t i o n which two-dimensional l i n e drawings are composed of. LIG uses the a r e a l e x t e r n a l r e p r e s e n t a t i o n model f o r the data type GBAPHICAL (the l i n e a r e x t e r n a l r e p r e s e n t a t i o n i s used f o r example l y the languages POL [ H i l l 6 8 J , E-LINE [Fra68 J and TONA £Berk77 ] ) • T h i s data type i s t r e a t e d c o n s i s t e n t l y as a new type i n i t s own r i g h t ; t hus, language elements such as g r a p h i -c a l v a r i a b l e s , g r a p h i c a l o p e r a t o r s and g r a p h i c a l assignment statements correspond to e g u i v a l e n t elements of other h i g h -l e v e l languages. , The LIG g r a p h i c s system s u p p l i e s s i x g r a p h i -c a l p r i m i t i v e s and a l l o w s i n c l u s i o n of u s e r - d e f i n e d g r a p h i c a l f u n c t i o n s . There are s i x g r a p h i c a l o p e r a t o r s i n LIG; the syntax f o r using these i s s i u i l a r t o t h a t o f EOLEE-G.. A s p e c i a l kind c f g r a p h i c a l assignment i s used which ac-counts f o r storage space e f f i c i e n c y and a l s o i m p l i e s a high interdependence between g r a p h i c a l data., The data base con-s i s t s .of a t r e e s t r u c t u r e . The language c h a r a c t e r i s t i c s are f o r m a l l y d e f i n e d by a syntax i n BNF.. The ; preprocessor i s generated by the XPL T r a n s l a t o r B r i t i n g System by McKeeman et a l . At the O n i v e r s i t y of B r i t i s h Columbia LIG i s implemented cn two computer systems. The preprocessor runs on the comput-ing c e n t r e * s AMDAHL 170; the r e s u l t i n g FOBTBAN programs can be r u n e i t h e r on the same machine or may be t r a n s f e r r e d t o a Data General NOVA 840 ainiccmputer with a l e k t r c n i x 4010 g r a p h i c s t e r m i n a l i n the Department of E l e c t r i c a l E n g i n e e r i n g . LIG»s o r i g i n a l design goals of s i m p l i c i t y and " n a t u r a l n e s s " of use have been met; however, new developments 14 in-computer g r a p h i c s demand an ongoing r e v i s i o n of the l a n -guage., Chapter 3 d e s c r i b e s i n d e t a i l the proposed new syntax f o r the language. An overview of where new language con-s t r u c t s were f e l t t c be necessary i s given here: 1. FCBTBAN as a host language was c o n s i d e r e d outdated and i t i s i n v e s t i g a t e d how P a s c a l can be used i n s t e a d . E x i s t i n g and new language c o n s t r u c t s are s p e c i f i e d with t h i s i n mind. The new d i a l e c t of the language i s c a l l e d LIG/P. •2..-V LIG/P i s a 3B-system i n c o n t r a s t to LIG's 2 D - f a c i l i -t i e s . 3. The e n t i r e LIG/P system i s w r i t t e n i n P a s c a l ; t h i s i n c l u d e s the preprocessor and the run-time environment. The o r i g i n a l data base has been redesigned; e x t e n s i v e changes were r e q u i r e d to accommodate new f e a t u r e s . , 4. New data types were i n t r o d u c e d ; t h i s f i t s w e l l i n t o the framework of P a s c a l . The types SUBPICTURE, INSTANCE, IUP UT d e v i c e , OUTPUT d e v i c e , VIEHVGLOHE and VIEWPORT have been added to the o r i g i n a l data type GRAPHICAL. The con-c e p t o f g r a p h i c a l p r i m i t i v e s and system d e f i n e d f u n c t i o n s was m o d i f i e d . 15 5. . A much improved concept of modelling and d i s p l a y f u n c t i o n s i s i n t r o d u c e d . T h i s i n c l u d e s the a v a i l a b i l i t y of a program defined world c o o r d i n a t e system, of c l i p -p i n g , cf viewing and image t r a n s f o r m a t i o n s . 6;.•. j B u l t i p l e i / o streams combined with viewing o p e r a t i o n s a l l o w mapping ?frcm view volumes i n ^ o viewports on d i f -f e r e n t d e v i c e s , pr m u l t i p l e viewports on;,the same d e v i c e . The s e l e c t i v e erase f u n c t i o n s have: beea r e d e s i g n e d . 7 . Device e n a b l i n g , s e t t i n g and enquiry f u n c t i o n s make the language adaptable to sop h i s t i c j a t e d h j a ^ ^ ments., 8. ,. G r a p h i c a l i n p u t f u n c t i o n s have been r e d e s i g n e d . Text i n p u t , value input and stroke lnpat,:.hia^?v>been:! i n c l u d e d * 9 . .. Hew i d e n t i f i c a t i o n c o n s t r u c t s sallow^-t,logical;::iOperatprs and e x p r e s s i o n s i n the I F HIT C N . s t a t e m e n t , and pro-v i d e a C A S E HITON O F . . . statement. 1 0 . A t t r i b u t e s f o r g r a p h i c a l v a r i a b l e d e f i n i t i o n and d i s p l a y were i n t r o d u c e d . A t t r i b u t e s such as c o l o u r , l i n e s t y l e and polygon f i l l d i d not e x i s t before i n the l a n -guage. 16 11. A number c f new c o n t r o l statements were added; e.g. a FAUSE and EE1L statement. r C o n t r o l over the p h y s i -c a l s i z e c f hardcopy output i s p o s s i b l e s 12. An a r c h i v a t i o n statement a l l o w s the permanent s t o r a g e c f g r a p h i c a l d ata. SAVE and BESTOBE statements f a c i l i t a t e c o n t i n u i t y between s e s s i o n s . 2.3 P o r t a b i l i t y of Software u s i n g -the V i r t u a l Machine Concept A programming language i s d e f i n e d with a c e r t a i n c l a s s of problems i n mind; these are t o be so l v e d c o n v e n i e n t l y using the c o n t r o l and data s t r u c t u r e s p r o v i d e d by the language. The g.uesticn a r i s e s of how the language i s to. be implemented. For a n j i n p l e m e n t a t i o n the i i g h - l e v e l language c o n s t r u c t s have to be broken i n t o simpler c o n f i g u r a t i o n s ; t h i s i s a stepwise process u n t i l the r e s u l t i s a s e r i e s of machine code i n s t r u c -t i o n s . , B i t h i n t h i s process cne can d i s t i n g u i s h between machine-independent and machine-dependent phases and codes. The problem c f software p o r t a b i l i t y has l e d to the development of language t r a n s l a t o r s whose t a r g e t code i s an assembly l a n -guage f o r a simple v i r t u a l machine; t h i s a b s t r a c t machine can be mapped onto a r e a l machine and from the v i r t u a l machine code one can generate code f o r the a c t u a l machine. The two main advantages of t h i s method a r e : 17 1 • The language tr a n s l a t i o n process i s s p l i t into two simpler tasks — generation of v i r t u a l machine code, and generation of actual machine code; i f the interface i s c l e a r l y defined then the two processes are independent of each other, 2 . As already mentioned, p o r t a b i l i t y of a compiler can he achieved e a s i l y because an implementation of a compile er on a new machine reguires that only, the second phase has to be rewritten; t h i s phase i s the simpler of the two and the corresponding translator i s r e l a t i v e l y easy to write. Various projects involving d i f f e r e n t high-level languages using t h i s p r i n c i p l e have provided valuable i n s i g h t i n t o the design of abstract machine codes. This section b r i e f l y men-tions and explains objectives of such projects; Section 2.4 i s an investigation cf hew graphics machines are designed, and Section 2.6 describes the design p r i n c i p l e s of an abstract graphics i / c device. Code generation for high-level language programs can be considered e f f e c t i v e i f the output produced by a language tran s l a t o r i s an e f f i c i e n t and compact representation of the o r i g i n a l language constructs. The c h a r a c t e r i s t i c s of the generated code r e f l e c t the architecture of the target machine. Bow machines are being used i s cf concern to system a r c h i -18 t e c t s , compiler w r i t e r s and language d e s i g n e r s ; among them many h o l d the o p i n i o n t h a t e x i s t i n g machines do not f a c i l i t a t e e f f e c t i v e r e p r e s e n t a t i o n and e x e c u t i o n of h i g h - l e v e l language c o n s t r u c t s . , Bachine a r c h i t e c t s should view the computer as a t o o l to e f f i c i e n t l y run the programs t h a t people w r i t e f o r them. An important c o n t r i b u t i o n to support t h i s i d e a were the experiments by Tanenbaum £Tan78] who proposes a stack machine a r c h i t e c t u r e to execute programs w r i t t e n i n a b l o c k - s t r u c t u r e d high l e v e l language. Tanenbaum bases h i s work on e a r l i e r s t u d i e s by Knuth [Knu71J, Alexander [Alex75 ], S a l v a d o r i , Gordon and C a p s t i c k £Salv75], and Hortman £Wort72]. Hortman s t a t e s : "He took as our design g o a l the development of new design gcaIs to a i d the d e s i g n e r i n b u i l d i n g computers t h a t s a t i s f i e d the a c t u a l r a t h e r than the imagined needs of the programmer.'? The design of computers with h i g h - l e v e l languages i n mind i s c l c s e l y r e l a t e d t c microprogramming. Microprogramming i s i n f a c t one way of inplementing i n t e r m e d i a t e languages. The others are d i r e c t t r a n s l a t i o n to machine code, as a l r e a d y men-t i o n e d , c r i n t e r p r e t a t i o n . , There are two c l a s s e s of interme-d i a t e languages; they can be "machine s p e c i f i c " or "language s p e c i f i c " £ Els79 J. Bachine s p e c i f i c i n t e r m e d i a t e languages are t a y l c r e d t c s u i t a p a r t i c u l a r t a r g e t machine, and a l l com-p i l e r s which t r a n s l a t e programs f o r t h a t machine are r e g u i r e d to t r a n s l a t e h i g h - l e v e l language programs i n t o that p a r t i c u l a r i n t e r m e d i a t e language. T h i s approach has net proven too sue-19 c e s s f u l because c f the d i f f i c u l t y of f i n d i n g s u i t a b l e interme-d i a t e languages f o r d i f f e r e n t h i g h - l e v e l languages. The i n -termediate language mr-st i n t h i s case be a t a r e l a t i v e l y high l e v e l t o a l l c w ccmocn i n t e r m e d i a t e c o n s t r u c t s f o r h i g h - l e v e l languages, and much of the p r o c e s s i n g has t o be done i n the second phase cf the t r a n s l a t i o n . Language s p e c i f i c interme-d i a t e languages have shewn mere succ e s s . In t h i s case a high-l e v e l language i s t r a n s l a t e d i n t o i t s own i n t e r m e d i a t e l a n -guage t h a t i s p a r t i c u l a r l y s u i t a b l e f o r the r e p r e s e n t a t i o n of i t s language s p e c i f i c c o n s t r u c t s . Thus the g r e a t e r p a r t of the t r a n s l a t i o n process i s done i n t h i s phase., A l l t h a t r e -mains t c be done i s t o t r a n s l a t e the simple i n t e r m e d i a t e l a n -guage - i n t o t a r g e t machine code. > The f i r s t phase of t r a n s l a -t i o n i s made e n t i r e l y machine independent., By w r i t i n g the compiler i n the p a r t i c u l a r h i g h - l e v e l language i t s e l f i t i s p o s s i b l e t o bootstrap i t when p o r t i n g i t to a new machine. Examples of s u c c e s s f u l a p p l i c a t i o n s of i n t e r m e d i a t e l a n -guage technigues are BCPL ( t r a n s l a t e d t c OCODE and INTCODE [ Bich7 1 ], 8IHIC0DE £P€Ck75], SLIM £Fox78J) , ALGOL 68 ( t r a n s -l a t e d t c ZCODE £Bour77], ACODE £Els79]) , P a s c a l ( t r a n s l a t e d to I-ccde :£Ncri74 ]) , COBOX £Brcwn77], and SHOBOL £Dew77]. The a b s t r a c t machines def i n e d f o r a language can have i n s t r u c t i o n s of a r e l a t i v e l y high l e v e l , e.g. block s t r u c t u r -ing i n s t r u c t i o n s , procedure c a l l s , case statements; or they can be c l o s e r t c a p a r t i c u l a r machine language and thus o r i e n t e d towards a p a r t i c u l a r c l a s s of r e a l machines. 20 A l o s e r l e v e l i n t e r m e d i a t e language with very simple i n -s t r u c t i o n s can mere e a s i l y be implemented on most machines, but i t a l s o has disadvantages. In most cases the t a r g e t code i s i n e f f i c i e n t , and i f a machine provides h i g h e r l e v e l con-s t r u c t s cne cannot take advantage of these. I t i s a l s o a longer t r a n s l a t i o n process to generate low l e v e l i n t e r m e d i a t e code which may i n p r a c t i c e make the c o m p i l a t i o n too i n e f f i -cient*. . For seme languages, such as A l g o l 68 and P a s c a l , some machine s p e c i f i c i n f o r m a t i o n (e.g. data s i z e s and r e g i s t e r a v a i l a b i l i t y ) i s r e g u i r e d to o b t a i n reasonably e f f i c i e n t code; such data can be fed t o the c o m p i l e r i n advance; the machine dependence i s then "parameterized" and i s not part of the i n -termediate language . i t s e l f . , I f commitment t c any r e a l machine i s t o be avoided then no h i g h - l e v e l p r i m i t i v e s may be decom-posed, e.g., .the s t r u c t u r e of a program may not be l o s t . I t depends on the p a r t i c u l a r p r o j e c t and the c h a r a c t e r i s -t i c s (e.g. .size) of a h i g h - l e v e l language which l e v e l of i n -termediate language should be chosen. A low l e v e l code with parameterized i n f o r m a t i o n i s a p p r o p r i a t e i f one g u i c k i y r e -q u i r e s a t o l e r a b l e implementation cn most machines and a good implementation on few machines; on the other hand, i f the ob-j e c t i v e i s a good implementation on most machines then a higher l e v e l machine independent and language-oriented i n t e r -mediate language should be chosen, a t the expense of a more d i f f i c u l t t r a n s l a t i o n to machine code. 21 In the context of t h i s t h e s i s these r e s u l t s are i n t e r e s t -i n g f o r the f o l l o w i n g reasons: 1. To our Knowledge no i n t e r m e d i a t e language has ever been designed s p e c i f i c a l l y f o r a h i g h - l e v e l g r a p h i c s l a n -guage. The i n v e s t i g a t i o n of a machine a r c h i t e c t u r e f o r LIG programs would be an i n t e r e s t i n g t a s k . Since LIG/P i s an e x t e n s i o n to P a s c a l an i n t e r m e d i a t e language c o u l d be an extended P-code. In Chapter 4 o f t h i s t h e s i s i t i s d e s c r i b e d i n mere d e t a i l what a c t i o n s have to be taken f o r h i g h - l e v e l language statements; t h i s i s a f u r t h e r s t e p towards the d e f i n i t i o n c f a v i r t u a l LIG-machine. 2. In t h i s t h e s i s only the i / o process of g r a p h i c a l data makes use of an a l r e a d y d e f i n e d v i r t u a l g r a p h i c s machine. I t i s i n v e s t i g a t e d how s u i t a b l e t h i s r e l a t i v e l y low l e v e l g r a p h i c s machine i s as part of the complete LIG/P graph-i c s system. 3. The d e f i n i t i o n of g r a p h i c a l o b j e c t s i n v o l v e s to some • extent the encoding of such i n f o r m a t i o n f o r compactness of s t o r a g e ; the c o n c l u s i o n s drawn above provide v a l u a b l e g u i d e l i n e s f o r the design of c e r t a i n p a r t s of the LIG/P da t a base. 22 2• Graphics Display Processors To achieve maximum speed for the execution of graphics functions so-called " i n t e l l i g e n t " terminals have been b u i l t uith a large amount of l o c a l processing power. Several ap-proaches for building such graphics devices w i l l be discussed. 2.<1.1 H o s t / S a t e l l i t e Configurations In recent years much research has been done to build graphics systems i n which a host computer i s connected to sev-e r a l graphics s a t e l l i t e s . , In general the host i s a large time-shared machine and the s a t e l l i t e s are small mini- or micro-computers. The advantage of such a system i s that the host dees net spend any time with t r i v i a l but time-consuming graphics support, yet the user enjoys real-time response at the graphics terminal. , The host can allocate i t s resources more e f f e c t i v e l y cn application program processing and data base functions, another goal i s to reduce communication t r a f -f i c between host and s a t e l l i t e s as much as possible, es p e c i a l -ly i f the connecting link i s , for example, a low-speed t e l e -phone l i n e . Two kinds of graphics s a t e l l i t e s e x i s t . "Fixed-function s a t e l l i t e s " are accessed from the host computer via subroutine c a l l s ; in t h i s case the application program i s completely host-resident. Hhen "programmable s a t e l l i t e s " are used the connection between host and s a t e l l i t e s i s more relaxed. Some 23 of these s a t e l l i t e s have t h e i r own secondary memory and s t o r e a complete g r a p h i c a l package; a d d i t i o n a l f u n c t i o n s can be im-plemented and even p a r t s " of the a p p l i c a t i o n program can be processed t h e r e . I t i s obvious that such a system provides s u p e r i o r f a c i l -i t i e s but i s a l s o much more complex i n terms of o v e r a l l opera-t i n g systems f u n c t i o n s . C o n s i d e r a b l e e f f o r t has been expended to i n v e s t i g a t e s o l u t i o n s to the " d i v i s i o n of l a b o u r " problem. These are g e n e r a l problems of d i s t r i b u t e d p r o c e s s i n g and i n t e r - p r o c e s s communication., Two i n t e r e s t i n g r e f e r e n c e s ad-d r e s s i n g t h i s t o p i c are £Houl76] and £Ccll79 ]. The f o l l o w i n g two s u b s e c t i o n s 2 . 4 . 2 and 2 . 4 . 3 d e s c r i b e i n more d e t a i l what c a p a b i l i t i e s have been c o n s i d e r e d important f o r high-performance g r a p h i c s s a t e l l i t e s and how they have teen implemented. , 2 . 4 . 2 Hardware of D i s p l a y P r o c e s s o r s High-performance d i s p l a y p r o c e s s o r s are s p e c i a l g r a p h i c s computers which need minimal support from a host computer to d i s p l a y p i c t u r e s . They are stand-alone systems with s p e c i a l hardware designed f c r a p p l y i n g t r a n s f o r m a t i o n s to p i c t u r e def-i n i t i o n s and thus being able to d i s p l a y f l i c k e r - f r e e dynamic p i c t u r e s i n r e a l time., The components of a t y p i c a l system are a t r a n s f o r m a t i o n processor and a p i c t u r e generator; the t r a n s f o r m a t i o n proc-24 essor has an i n t e r f a c e to a CPU which sends i t t r a n s f o r m a t i o n parameters and drawing commands. Other i n s t r u c t i o n s s e t c e r -t a i n modes i n the t r a n s f o r m a t i o n p r o c e s s o r , e.g. how c o o r d i -nate p o i n t s are to be connected, whether c o o r d i n a t e data i s two-dimensional, t h r e e - d i m e n s i o n a l or homogeneous., The t r a n s -formation processor may have a DMA l i n k t o the CPU i n which case i t can f e t c h c o o r d i n a t e data while the CPU can execute other cede, e.g. .-.optimize the o r g a n i z a t i o n of c o o r d i n a t e data to speed up the generation of a p i c t u r e frame. An example of such a system i s TEE PICTUBE SXSTEH by Evans and Sutherland Computer C o r p o r a t i o n ( C a l l 7 5 ] , a r e f r e s h v e c t o r d i s p l a y . , The t r a n s f o r m a t i o n processor operates on the c o o r d i n a t e data a p o i n t a t a time and p l a c e s the r e s u l t i n the r e f r e s h b u f f e r ; the data i n the r e f r e s h b u f f e r are read by the p i c t u r e generator, converted f r e s t h e i r d i g i t a l form t o analog s i g n a l s and output on the d i s p l a y s u r f a c e . The s t e p s taken by the t r a n s f c r m a t i c n processor are c o n v e r s i o n of p o i n t c o o r d i n a t e s to a b s o l u t e homogeneous c o o r d i n a t e s , m u l t i p l i c a t i o n by the t r a n s f o r m a t i o n matrix, s c a l i n g , r o t a t i n g and t r a n s l a t i n g , c l i p p i n g t c a window or view volume to remove p a r t s t h a t should net be v i s i b l e , a p p l y i n g depth-cued p e r s p e c t i v e , and f i n a l l y mapping onto; viewport c o o r d i n a t e s . , THE PICTOBE SYSTEM r e g u i r e s between 10 t c 36 microseconds to apply these opera-t i o n s en one p o i n t ; thus on the average i t can process about 3300 p o i n t s i n 1/15 s, the maximum frame time f o r smooth dy-namic output., P i c t u r e update i n the r e f r e s h b u f f e r and p i c -25 t o r e d i s p l a y do net occur a t the same r a t e ; , t h e y are indepen-dent o f each o t h e r . The minimum r e f r e s h r a t e f o r f l i c k e r - f r e e p i c t u r e s i s 30 Hz; some p i c t u r e generators can r e f r e s h at 40 and 60 Hz. The screen r e s o l u t i o n of such systems i s normally 4096 x 4096 addressable p o i n t s ; d i s p l a y r a t e s vary between 1600 and 26000 t e n - i n c h l i n e s f o r a 30 Hz r e f r e s h r a t e , de-pending on the manufacturer. To ensure smooth movements i n dynamic d i s p l a y s the r e f r e s h b u f f e r may be s p l i t i n t o two sec-t i o n s and the technigue cf doubles-buffering i s used. : T h i s can be done i f frames f i t i n t o h a l f the s i z e of the r e f r e s h b u f f e r and a d i s p l a y e d frame i n one s e c t i o n remains i n t a c t u n t i l a new frame has been generated i n the ether s e c t i o n ; then the r e f r e s h s e c t i o n s are switched. Slew software-performed p i c t u r e t r a n s f o r m a t i o n s such as shading and h i d d e n - l i n e removal are normally done by the CPU. In some systems the CP0 can o b t a i n i n f o r m a t i o n from the t r a n s -formation p r o c e s s o r which normally outputs only to the r e f r e s h b u f f e r , and perform the time-consuming p i c t u r e t r a n s f o r m a t i o n s before sending the data back to the t r a n s f o r m a t i o n p r o c e s s o r . Some systems, such as THE PICT0EE SXSTEH, have no o p t i o n s wi t h i n the c e n t r a l processing path. Others are general-pur-pose expandable p r o c e s s o r s where c r i t i c a l d i s p l a y f u n c t i o n s are hardwired, and autonomous asynchronously running proces-s o r s f o r s p e c i a l f u n c t i o n s can be added e x t e r n a l l y . S e v e r a l such p r o c e s s o r s have been b u i l t ; one a t the North C a r o l i n a S t a t e U n i v e r s i t y £Staud75] f o r example, has a very f a s t proc-26 e s s c r t c implement o p e r a t i o n s such as s p e c i f i c a r i t h m e t i c , l i n k e d l i s t h a n d l i n g , f a s t output, Batkins* C l i p p e r s , and d i g -i t a l a r r a y m u l t i p l i c a t i o n . I t i s , part of a c o l o u r s c a n - d i s -play system and has a worst-case i n s t r u c t i o n e x e c u t i o n time of 80 ns.. I t uses p l u g - i n processors f o r s p e c i a l a r i t h m e t i c ; one of the p e r i p h e r a l s i s a f a s t m u l t i p l i e r with a m u l t i p l y time between 24 and 180 ns <for numbers between 4 and 32 b i t s ) . Another p e r i p h e r a l *hich communicates through the i / o bus pro-vid e s g e n e r a l t r i g o n o m e t r i c f u n c t i o n s and c o l o u r m o d i f i c a t i o n s f o r r o t a t e d o b j e c t s . P e r s p e c t i v e p r o j e c t i o n and matrix m u l t i -p l i c a t i o n f o r r o t a t i o n , using homogeneous c o o r d i n a t e s , i s done fey a p e r i p h e r a l which a c c e p t s 16-bit x,y,z and w ( d i s t a n c e from the observer) c o o r d i n a t e s and r e t u r n s the r e s u l t i n 2 microseconds, flaster scan output i s provided by a c o l o u r d i s -p l a y system which r e c e i v e s l i n e and run-length encoded data from the main processor*. 2.4.3 aicroprogrammed D i s p l a y Processors advantages of microprcgrammable g r a p h i c s p r o c e s s o r s are lower c o s t , g r e a t e r f l e x i b i l i t y , b e t t e r m a i n t a i n a b i l i t y through firmware d i a g n o s t i c r o u t i n e s , and of course s u p e r i o r performance compared to the s u b s t i t u t e d software g r a p h i c s f u n c t i o n s . Two implementations of such pr o c e s s o r s are de-s c r i b e d here. a r e s e a r c h p r o j e c t at Brown U n i v e r s i t y rvanDam72] i n v e s -27 t i g a t e d design t r a d e o f f s between hardware, firmware and s o f t -ware.. The goal was to b u i l d a medium-cost i n t e r a c t i v e design system with quick response time and smooth p i c t u r e transforma-t i o n s , e.g. zooming. The system can operate e i t h e r i n stand-alone mode f o r s m a l l problems, or as an i n t e l l i g e n t s a t e l l i t e f o r a host t h a t handles the p i c t u r e s t r u c t u r i n g and data base management.. Hardware components of the system are two Beta 1 microprogrammable p r o c e s s o r s , a mini d i s k , a s p e c i a l arithme-t i c l o g i c u n i t , and a Vector General d i s p l a y . . The f i r s t Beta 1 p r o c e s s o r i s used as a s m a l l s a t e l l i t e computer which handles the i n t e r f a c e to the host machine, l o c a l p e r i p h e r a l s (e.g. a t y p e w r i t e r console and the d i s k f o r l a r g e user d i s p l a y f i l e s ) , and i t c o n t r o l s the second Meta 4.. That machine i s the " d i s p l a y c o n t r o l l e r " and i s microprogrammed to execute i n s t r u c t i o n s i n the d i s p l a y f i l e ; i t performs 3D-transforma-t i o n s and c l i p p i n g and a l s o processes g r a p h i c s device i n t e r -r u p t s . To be ab l e t c process and d i s p l a y at l e a s t 1000 to 2000 v e c t o r s per frame, another microprocessor i s added; t h i s one i s microprogrammed t o execute v e c t o r - m a t r i x m u l t i p l i c a t i o n , s c a l a r - v e c t o r m u l t i p l i c a t i o n , and p e r s p e c t i v e c a l c u l a t i o n s . I t i s a very f a s t p a r a l l e l p r o c e s s i n g computer with an i n -s t r u c t i o n time of about 30 ns. The Vector General d i s p l a y processor generates v e c t o r s and c h a r a c t e r s , performs z - a x i s depth cueing and viewport map-pin g . 28 An example of a commercially available microprogrammed processor i s the Adage GP/400 i n t e r a c t i v e graphics system £Kerr7 5 ]. Ihe design objectives were speed improvement by being able to reduce the overhead of graphics commands, being able tc handle a high degree of image structure, and f l e x i b i l -i t y f o r d i f f e r e n t . a p p l i c a t i o n s through programmability. To increase speed, coordinate-transformation hardware performs vector multiplication and transformation concatena-ti o n . , Hicroprograms have replaced sine and cosine c a l c u l a -tions which are performed i n about 5.6 microseconds compared to about 100 microseconds when executed by software. Overall speed improvements average 10 to 30 times over the execution of functions by software. 2.5 Achieving Eevice Independenee Analogous to the "kernel" concept for operating systems, graphics systems can be organized i n a hierarchy of le v e l s ; each l e v e l has a well-defined interface and higher l e v e l s can access lower ones d i r e c t l y cr through intermediary l e v e l s , figure 1 i l l u s t r a t e s the arrangement. This configuration i s a step towards achieving compati-b i l i t y with ether graphics software and machines. Each layer i s a higher abstraction of the lower ones and provides addi-ti o n a l features. A programmer i s provided with the conceptual model cf a "pseudo-machine" and writes his application in 29 a p p l i c a t i o n s o f t w a r c a p p l i c a t i o n - c r i e n t e d g r a p h i c s support a p p l i c a t i o n - i n d e p e n d e n t m o d e l l i n g f u n c t i o n s ( g r a p h i c a l e x p r e s s i o n e v a l u a t i o n , h i g h - l e v e l language dependent) d i s p l a y f u n c t i o n s (viewing t r a n s f o r m a t i o n s , image t r a n s f o r m a t i o n s ) s p e c i a l o p e r a t i o n s (e.g. hidden l i n e removal) f u n c t i o n l i b r a r y or g r a p h i c s package (e.g. segmentation o f d i s p l a y f i l e s ) output p r i m i t i v e s device d r i v e r g r a p h i c a l output device firm/hardware i n p u t p r i m i t i v e s d e v i c e d r i v e r g r a p h i c a l i n p u t d e v i c e firm/hardware F i g u r e J those terms. fiacy such c o n c e p t u a l models e x i s t , and much e f f o r t has r e c e n t l y gone i n t o d e f i n i n g a standard a b s t r a c t E c d e l f o r g r a p h i c s ; one of the major d e c i s i o n s was t o decide cn an a p p r o p r i a t e l e v e l of a b s t r a c t i o n . S e v e r a l s o l u t i o n s to a c h i e v e device-independence a t lower l e v e l i n t e r f a c e s have been proposed and implemented. Two are b r i e f l y d e s c r i b e d here; one d e a l s with the i n t e r f a c e t o the dev i c e d r i v e r , and the other i s one l e v e l h i g h e r . An example f o r the f i r s t case i s HEGL ("Hewlett Packard Graphic language") £Dan77]. HPGL i s a command language f o r p l o t t e r s , each command c o n s i s t i n g of two ASCII c h a r a c t e r s , f o l l o w e d by numeric parameters and ended by a t e r m i n a t o r c h a r a c t e r . . C a l c u l a t o r s or desk top computers send i n s t r u c -30 t i o n s t c the HE Graphics T r a n s l a t o r which t r a n s l a t e s them by firmware i n t o ASCII-coded HPGL commands and sends them to the p l o t t e r . The p l o t t e r ' s firmware i n t e r p r e t s HPGL., The l a n -guage, i s expandable and new commands are added as r e g u i r e d by new products. An example c f a language used to i n t e r f a c e a t the next higher l e v e l i s L4 ("Linear Low-Level Language") [ G i l 7 8 ] . . T h i s i s an i n t e r m e d i a t e language to serve f o r the communica-t i o n between a host computer and i t s s a t e l l i t e s . , To minimize the data flow, the language i t s e l f i s as c o n c i s e as p o s s i b l e . A l s o , only p i c t u r e e d i t i n g i n f o r m a t i o n i s exchanged, but not e n t i r e d i s p l a y f i l e s — a d i s p l a y f i l e i s generated o n l y once, and s i n c e p i c t u r e e d i t i n g can occur a t e i t h e r the host or the s a t e l l i t e , 14 c a r r i e s i n f o r m a t i o n both ways. The s a t e l l i t e must perform L4 i n t e r p r e t a t i o n and d i s p l a y f i l e management, o b j e c t i d e n t i f i c a t i o n , accept i n p u t from i n p u t d e v i c e s (the alphanumeric keyboard and the f u n c t i o n keyboard), and handle c e r t a i n i n t e r a c t i o n s l o c a l l y . C o n s i d e r i n g the examples above and those i n S e c t i o n 2.4 i t may be c l e a r now t h a t the l e v e l s of a g r a p h i c s system as shown i n F i g u r e 1 are not c l e a r l y d e f i n e d f o r any given imple-mentation. , There i s a great dependency on the p a r t i c u l a r hardware a v a i l a b l e and on the o p e r a t i n g system. Trends i n hardware developments suggest t h a t p o s s i b l y a more l i n e a r r e -p r e s e n t a t i o n (or " p i p e l i n i n g " ) of i n t e r a c t i n g p a r t s i s more adeguate i n the higher l e v e l s . T h i s would b e t t e r i n c o r p o r a t e 3 1 new p l u g - i n processors or programmable s a t e l l i t e s with t h e i r l o c a l f e a t u r e s such as s u r f a c e - g e n e r a t i n g f u n c t i o n s , hidden-l i n e removal or d i s p l a y c f shaded 3D-objects. B i t h r e s p e c t to i n t e r m e d i a t e codes a c o n c l u s i o n s i m i l a r to t h a t mentioned i n the d i s c u s s i o n of high l e v e l languages has been reached; the device d r i v e r (or code generator) of a p a r t i c u l a r d e v i ce has t o make the d e c i s i o n about f a c i l i t i e s a v a i l a b l e i n software, firmware or hardware. For f u n c t i o n s t h a t are a v a i l a b l e i n hardware no software overhead should slow down the performance. A device d r i v e r must, however, have ac c e s s to device independent s i m u l a t i o n software f o r f u n c t i o n s t h a t cannot be provided i n hard o r firmware; t h i s software can be used by a l l device d r i v e r s and may f o r example c o n t a i n s t r o k e p r e c i s i o n c h a r a c t e r d e f i n i t i o n s . To summarize what was s a i d b e f o r e , an i n t e r m e d i a t e cede must t h e r e f o r e con-s i s t c f r e l a t i v e l y h i g h - l e v e l commands so t h a t good implemen-t a t i o n s are p o s s i b l e f o r most d e v i c e s . I t depends on the l e v e l c f a b s t r a c t i o n what form e x a c t l y they should have. 2.6 Design C r i t e r i a f o r Graphics Packages The purpose of t h i s s e c t i o n i s to r e l a t e the Core System tc e s t a b l i s h e d concepts and to other g r a p h i c s packages and t h e i r c a p a b i l i t i e s . , To pr e s e n t the Core System as a standard g r a p h i c s package i t has to be put i n t o the r i g h t p e r s p e c t i v e by viewing i t i n the context of a wider range of design c r i -32 t e r i a . 2.6.1 l e v e l s of P i c t u r e Ranting and M o d i f i c a t i o n G r a p h i c s languages and g r a p h i c s s u b r o u t i n e packages can te c a t e g o r i z e d by the kind of o r g a n i z a t i o n they a l l o w on g r a p h i c a l data. Some systems p r o v i d e f a c i l i t i e s f o r m u l t i p l e l e v e l s or a h i e r a r c h i c a l s t r u c t u r e of d e f i n i n g g r a p h i c a l ob-j e c t s , e t h e r s have a much s i m p l e r concept and permit only a s i n g l e l e v e l . In most systems the v a r i o u s p a r t s forming an ob j e c t can be grouped together i n a "segment"., a segment has a unigue name and has a t t r i b u t e s which can be changed; these changes apply c o l l e c t i v e l y t o a l l p a r t s contained i n the seg-ment. I d e n t i f i c a t i o n and d e l e t i o n a l s o apply t o an e n t i r e segment. ,, \ I n a s i n g l e - l e v e l system a segment c o n t a i n s only output p r i m i t i v e s , and a l l segments are independent of each other with r e s p e c t t c m o d i f i c a t i o n s and naming. In a m u l t i p l e - l e v e l o r g a n i z a t i o n r e f e r e n c e s between segments a r e allowed and a p a r t i c u l a r segment can use another one as a s u b p i c t u r e . By r e f e r e n c i n g a p a r t i c u l a r segment name a l l lower l e v e l segments r e f e r r e d t o by the addressed one are a u t o m a t i c a l l y i n c l u d e d ; I t i s obvious t h a t a m u l t i - l e v e l naming c a p a b i l i t y i s more u s e f u l to serve a v a r i e t y of a p p l i c a t i o n s than a s i n g l e - l e v e l one. L e v e l s c f naming are important i n the way they are t i e d 33 to l e v e l s of m o d i f i c a t i o n because the two need not be i d e n t i -c a l . ..'Modifications are a t t r i b u t e changes and a d d i t i o n or de-l e t i o n of p a r t s . , Hith a z e r o - l e v e l m o d i f i c a t i o n c a p a b i l i t y , a p i c t u r e of uhich a part i s to be d e l e t e d has t o be erased en-t i r e l y and then be redrawn without the unwanted p a r t . A s i n g l e - l e v e l system has one l e v e l of segments and no h i e r a r -c h i c a l s t r u c t u r e a t a l l . A p i c t u r e can c o n s i s t of a number of d i s p l a y e d segments which can s e l e c t i v e l y be erased. I f p a r t of a segment i s to be e rased, the e n t i r e segment has t o be r e d e f i n e d without the d e l e t e d part and i s then r e d i s p l a y e d . M u l t i - l e v e l m o d i f i c a t i o n s are a p p l i e d at some po i n t i n the h i e r a r c h y , or a t some i n t e r n a l t r e e node, and apply to the s t r u c t u r e underneath i n terms of t r a n s f o r m a t i o n s , a d d i t i o n and d e l e t i o n c f p a r t s ; no r e d e f i n i t i o n c f any component i s r e -g u i r e d . ,, As mentioned above, m o d i f i c a t i o n and naming l e v e l s need not be i d e n t i c a l . , Foley [ F o l 7 6 ] s t a t e s t h a t " i t i s d e s i r a b l e t c o r g a n i z e the naming and s t r u c t u r i n g c a p a b i l i t i e s so t h e i r use i s completely o p t i o n a l : the a p p l i c a t i o n programmer should need to understand and use the c a p a b i l i t i e s o n l y i f he t r u l y needs them, otherwise the language becomes a burden, r a t h e r than an a i d , to i t s user". The h i g h - l e v e l g r a p h i c s language LIG f u l f i l l s t h i s r e -quirement. P i c t u r e s t r u c t u r i n g can be done t c any d e s i r e d l e v e l , and p i c t u r e naming can o p t i o n a l l y occur a t any p o i n t i n the h i e r a r c h y . T h i s i s the case f o r the p i c t u r e model or i n -3 4 t e r n a l r e p r e s e n t a t i o n , as w e l l as the d i s p l a y s t r u c t u r e to f a c i l i t a t e s e l e c t i v e e r a s i n g of i n s t a n c e s . 2-6.2 Common Graphics Packages The better-known g r a p h i c s packages i n c l u d e DISSPLA (Integrated Software Systems Corp., San Diego, w r i t t e n i n FORTRAN), TCS/P1GT-10 (Tektronix Terminal c o n t r o l System, w r i t t e n i n FORTRAN) , GPGS ( K a t h o l i c k e U n i v e r s i t e i t , Nijmegen, w r i t t e n i n FORTRAN and assembler), Omnigraph (XEROX P.A.B.C.), GINC-F (Cambridge England, w r i t t e n i n FORTRAN), GCS (U.S. fiilitary Academy, w r i t t e n i n FORTRAN), DIGS ( U n i v e r s i t y of North C a r o l i n a ) , GKS (German Graphics K e r n e l System), IG ( U n i v e r s i t y c f Michigan, w r i t t e n i n IBM 370 assembly language), and the GSPC Core System (many implementations, most o f them i n FORTRAN)..., A more d e t a i l e d d e s c r i p t i o n of each can be found i n £Fcl7,6] and [ E w a l 7 8 j . A l l of the above systems provide f a c i l i t i e s to group output p r i m i t i v e s i n segments; they vary widely, however, with r e s p e c t to the o p e r a t i o n s p o s s i b l e on segments. They are d i f -f e r e n t i n the way naming and m o d i f i c a t i o n l e v e l s are allowed; access to segments when d e f i n i n g g r a p h i c a l o b j e c t s i s a l s o t r e a t e d d i f f e r e n t l y . Here i s a l i s t of p o s s i b l e a c t i o n s on segments, o f which each package provides a l a r g e r or s m a l l e r subset: segments can be c r e a t e d , named, renamed, d e l e t e d , r e f -erenced, extended, transformed, r e d e f i n e d , c o p i e d , and have 35 a t t r i b u t e s . The u s e f u l n e s s and convenience of a g r a p h i c s package depends to a l a r g e e x t e n t on the number of these func-t i o n s i t p r o v i d e s . The more f u n c t i o n s a r e missing the more work i s l e f t t o the a p p l i c a t i o n programmer and the more must he d e f i n e h i s own concept of g r a p h i c a l data and model i t with h i s own data s t r u c t u r e s and o p e r a t i o n s . 2.6.3 S t a n d a r d i z a t i o n of Graphics C a p a b i l i t i e s advantages of the s t a n d a r d i z a t i o n of g r a p h i c s f u n c t i o n s are d e v i c e independence, computer independence and programmer e f f i c i e n c y . , a disadvantage i s the i n a b i l i t y t o take advantage of s p e c i f i c a r c h i t e c t u r a l c h a r a c t e r i s t i c s of a p a r t i c u l a r p r o c e s s o r . . a g r a p h i c s s t a n d a r d with too few f e a t u r e s cannot use e f f e c t i v e l y such high-performance d i s p l a y processors as d e s c r i b e d i n S e c t i o n 2.4. On the other hand, i f there are too many f e a t u r e s i t becomes bulky and expensive t o implement and use. a compromise i s a balanced number of commonly r e g u i r e d f e a t u r e s which can be implemented by hardware or simulated by software. Standardized i n t e r f a c e s can be d e f i n e d at v a r i o u s l e v e l s i n a g r a p h i c s system ( r e f e r r i n g back t o the diagram i n S e c t i o n 2.5). at the h i g h e s t l e v e l an i n t e r f a c e i s a p p l i c a -t i o n o r i e n t e d , and some commonly-used examples are ICES ("Integrated C i v i l E n g i n e e r i n g System") [ Boes68 ], and SYHaP (a s t a t i s t i c a l mapping system) [Symap]. These are more "de f a c t o " standards, though, which r e l y on s t a n d a r d i z e d lower 36 l e v e l support. A few l e v e l s c f i n t e r f a c e s f u r t h e r down are the g r a p h i c s packages. Among these one d i s t i n g u i s h e s between " a p p l i c a t i o n -independent, h i g h - l e v e l g r a p h i c s s u p p o r t " and " b a s i c g r a p h i c s support" £Fcl79]. Examples of the f i r s t group are DISSPLA, GfGS, GINO-F and GCS; a l l of them are d e v i c e - and computer-independent but vary i n the kind of f a c i l i t i e s they o f f e r and towards which a p p l i c a t i o n areas they are bia s e d , e.g. data p l o t t i n g , c a r t o g r a p h i c p r o j e c t i o n s , cr h i e r a r c h i c a l m o d e l l i n g . The proposed GSPC standard belongs to the " b a s i c g r a p h i c s support" group, as does Cmnigraph, which o f f e r s l e s s than the above packages; t h i s was f e l t t o be a p p r o p r i a t e because i t i s u n l i k e l y t h a t a consensus can be reached f o r the i n c l u s i o n of higher l e v e l f u n c t i o n s , and i f a l l of them are i n c l u d e d the r e s u l t i s an enormous system of which r e l a t i v e l y few f u n c t i o n s w i l l be used by most a p p l i c a t i o n s . , 2.6.4 F u n c t i o n s of the Core System The r e l a t i v e l y low l e v e l of the Core System seems t o have some advantages; i t i s based on the compromise of "what i s good f o r most programmers on most e x i s t i n g i n t e r a c t i v e d i s -plays most of the time" £Newm78 3 » , I t i s c o n s i d e r e d f u n c -t i o n a l l y complete such that h i g h e r - l e v e l ; modules can e a s i l y be b u i l t on top c f i t ; a l l f u n c t i o n s must be present which cannot be s u b s t i t u t e d by or b u i l t from other Core f u n c t i o n s . I t i s 37 primarily oriented towards medium-performance i n t e r a c t i v e vector displays and excludes features that are not yet ac-cepted practice — " a standard w i l l cot he accepted i f i t i s too f a r ahead of the state-of-the-art" [Newm78 3 . k b r i e f overview of the Core System i s given here for completeness; detailed discussions can be found i n [GSPC79] and [CS78J. Grouping, naming and modification of 2D- or 3D-output primitives i s done with segments; there are temporary and retained segments, Retained segments can be created, closed, deleted, re ratted, and have t h e i r attributes modified. Segment a t t r i b u t e s are either dynamic or s t a t i c . Dynamic seg-ment attributes are v i s i b i l i t y , highlighting, d e t e c t a b i l i t y , and image transformations, t. These can be modified dynamically afte r the segment i s defined and the e f f e c t w i l l be v i s i b l e immediately. S t a t i c segment attr i b u t e s are image-transformation- type and view-surface-selection.; Segments cannot contain;references to other segments— the Core System i s a si n g l e l e v e l system., Segments cannot be extended and cannot be copied, lay these decisions were made and how one can program without these functions i s discussed i n £Hich78J. Output primitives are moves, l i n e s , polylines, text, mar-kers and polymarkers. There are many att r i b u t e s for output primitives, for example colour, i n t e n s i t y , l i n e s t y l e , charac-ter s i z e and text q u a l i t y . . attributes f o r output primitves are c a l l e d " s t a t i c " because they are assigned once and cannot be changed for the lif e - t i m e of an output primitive. 38 Input p r i m i t i v e s are c l a s s i f i e d as event-generating pseudo-devices and sampled pseudo-devices. The f i r s t group c o n s i s t s of the d e v i c e s PICK, KEYBOABD, BUTTON and STROKE, the second group of LCCAIOB and VALUATOR. Input can be synchro-nous o r asynchronous; the l a t t e r generates event r e p o r t s and places them i n t o an event gueue. Sampled d e v i c e s can be asso-c i a t e d with event devices such that an event r e p o r t from some event device c o n t a i n s data from the a s s o c i a t e d sampled d e v i c e . The Core System provides f u n c t i o n s f o r modelling t r a n s -f o r m a t i o n s , viewing t r a n s f o r m a t i o n s and image t r a n s f o r m a t i o n s . The a p p l i c a t i o n program d e f i n e s segments i n a world c o o r d i n a t e space; modelling t r a n s f o r m a t i o n s are a p p l i e d and a l l c o o r d i -nates are mapped i n t o NDC (Normalized Device Coordinate) space. Viewing t r a n s f o r m a t i o n s are c l i p p i n g , p r o j e c t i o n , and geometric t r a n s f o r m a t i o n s f o r mapping from a programmer-de-f i n e d window onto a viewport. Image t r a n s f o r m a t i o n s are geo-metric t r a n s f o r m a t i o n s a p p l i e d to a v i s i b l e segment on a l l output s u r f a c e s a s s o c i a t e d with i t . A d e v i c e d r i v e r t r a n s -forms Normalized Device C o o r d i n a t e s to p h y s i c a l device c o o r d i -nates when a segment i s d i s p l a y e d on a p a r t i c u l a r output de-v i c e . The Core System provides e x t e n s i v e i n q u i r y f u n c t i o n s , s e t t i n g of i n i t i a l values f o r d e v i c e s and a t t r i b u t e v a l u e s , and s e l e c t i n g d i s p l a y d e v i c e s f o r output. The Core System can be implemented i n s e v e r a l upward com-39 p a t i b l e l e v e l s f o r i n p u t and output and two l e v e l s f o r dimen-s i o n s . . T h i s a l l o w s f o r adjustment to the requirements of a p a r t i c u l a r i n s t a l l a t i o n which can range from simple p l o t t i n g to i n t e r a c t i v e g r a p h i c s with r e f r e s h d i s p l a y s . an important d e c i s i o n f o r the design c r i t e r i a of the Core System was the complete s e p a r a t i o n of modelling and viewing f u n c t i o n s . The Core System c o n s i d e r s m o d e l l i n g the r e s p o n s i -b i l i t y c f the a p p l i c a t i o n program; w h e n a ^ p i c t u r e i s generated from a model, i t s data base i s t r a v e r s e d and geometric t r a n s -formations are a p p l i e d to the g r a p h i c p r i m i t i v e s i t c o n t a i n s . Some g r a p h i c s systems provide general-purpose t r a n s f o r m a t i o n f u n c t i o n s , some provide i n a d d i t i o n f a c i l i t i e s f o r model con-s t r u c t i o n and t r a v e r s a l . . However, every type of a p p l i c a t i o n r e g u i r e s a d i f f e r e n t s e t of model t r a v e r s a l f u n c t i o n s and i t was decided to completely exclude these from the Core System. I t i s p u r e l y a viewing system which reproduces images of the a p p l i c a t i o n program*s "world" on the output s u r f a c e . The d i s -p l a y f i l e i s a h i g h l y temporal e n t i t y and i s not intended to permanently s t o r e any p i c t u r e d e s c r i p t i o n generated w i t h i n the package. no Chapter 3 LIG/P LANGUAGE BEFIBENCE MANUAL 3, 1 Introduction The high-level graphics language LIG/P i s a graphics ex-tension tc Pascal. I t i s intended for the d e f i n i t i o n of three-dimensional objects which are defined in terms of l i n e s and f i l l e d polygon areas. High l e v e l operators allow the aanipulation of graphical objects at the modelling and at the display l e v e l . , Modifications provided for graphical objects are geometric transformations and attribute changes, such as colour and l i n e type. A LIG/P program i s : t r ans1ate d • .^Jt.c* • • Pascalv source cede by a preprocessor, A second t r a n s l a t i o n phase compiles the Pascal program; when executing i t , the LIG/P run-time l i -brary creates and manipulates entries i n the graphics data rase. The LIG/P run-time l i b r a r y was designed such that i t s input and output functions map onto the conceptual framework of the Core System [ G S P C 7 9 ] . The entire LIG/P system thus 41 becomes p o r t a b l e and device-independent. , 3.2 Terminology, n o t a t i o n and Vocabulary The s t r u c t u r e cf a LIG/E program i s e s s e n t i a l l y the same as t h a t c f a P a s c a l program. LIG/P statements are added t c a Pa s c a l program which determines the flow of c o n t r o l . At i n -s t a l l a t i o n s where separate c o m p i l a t i o n s of P a s c a l procedures are p o s s i b l e , the same can be done f o r source code t h a t r e -q u i r e s p r e p r o c e s s i n g . LIG/P i n t r o d u c e s a d d i t i o n a l predefined data types f o r d e f i n i n g and d i s p l a y i n g g r a p h i c a l o b j e c t s . They are r e f e r r e d to by t h e i r name which i s an o r d i n a r y P a s c a l i d e n t i f i e r . , An important d i s t i n c t i o n must be made between the modelling and d i s p l a y phase manipulation of g r a p h i c a l v a r i a b l e s ; s i n c e LIG/P supports a a u l t i - l e v e l m odelling system;and a s i n g l e - l e v e l d i s p l a y system, c e r t a i n o p e r a t i o n s are only allowed on v a r i -a b l e s c f a corresponding type. Tc be able t c d i f f e r e n t i a t e those p a r t s of the g r a p h i c a l data s t r u c t u r e t h a t must be d i s t i n g u i s h e d c o n c e p t u a l l y , the f o l l o w i n g terminology i s used; A g r a p h i c a l v a r i a b l e i s a g r a p h i c a l o b j e c t which i s composed of s u b p i c t u r e s . S u b p i c t u r e s are e i t h e r p r i m i t i v e s , g r a p h i c a l f u n c t i o n y i e l d s or ether g r a p h i c a l v a r i a b l e s . , Subpictures are named or they are anonymous; i f they are named, access to them f c r m o d i f i c a t i o n i s allowed at a l a t e r s t a g e ; they can, f o r 42 example, fee d e l e t e d frcm.a g r a p h i c a l v a r i a b l e . Anonymous sub-p i c t u r e s become p a r t of the " c o n s t a n t " p o r t i o n of a g r a p h i c a l v a r i a b l e and cannot be a l t e r e d u n l e s s the g r a p h i c a l v a r i a b l e i s r e d e f i n e d a l t o g e t h e r . Bhen a g r a p h i c a l v a r i a b l e i s d e f i n e d , i t s r e p r e s e n t a t i o n i n the g r a p h i c s data base i s cons-t r u c t e d . When a g r a p h i c a l v a r i a b l e i s d i s p l a y e d , an i n s t a n c e of i t i s c r e a t e d and output cn a v i e * s u r f a c e . L i k e s u b p i c t u r e s , i n s t a n c e s can be named or can be anonymous: i f -they are named, they can be erased s e l e c t i v e l y from the view s u r f a c e ; anony-mous i n s t a n c e s are only erased when the e n t i r e view s u r f a c e i s e r ased, or when a l l i n s t a n c e s of a g r a p h i c a l v a r i a b l e are e r a s e d . The o p e r a t i o n s that are allowed cn s u b p i c t u r e s are a s m a l l subset o f those a p p l i c a b l e to g r a p h i c a l v a r i a b l e s . Named s u b p i c t u r e s must be d i s t i n g u i s h e d from g r a p h i c a l v a r i -a b l e s even s y n t a c t i c a l l y , although they appear s u p e r f i c i a l l y to be the same. Experience has shown t h a t programming e r r o r s are f r e g u e n t l y made i n the use of named s u b p i c t u r e s , and by making them d i f f e r e n t e n t i t i e s c l a r i f i e s the concept and l e a v e s some e r r o r d e t e c t i o n and p o s s i b l y e r r o r c o r r e c t i o n to the LIG/P system. In the implementation of LIG/P, they are s y n t a c t i c a l l y d i s t i n g u i s h e d . The IIG/P vocabulary c o n s i s t s of s p e c i a l symbols, such as o p e r a t o r s and d e l i m i t e r s , and a number of reserved words, fieserved words are always w r i t t e n i n upper case and may not be 43 used as i d e n t i f i e r s . Comments i n the s o u r c e . t e x t are e n c l o s e d i n braces ( »{" and "}" ). The LIG/P s p e c i a l symbols a r e : 0 t -> <-/ ( ) 3 . ) The r e s e r v e d words a r e : ABB AS AT BEGIN BLANK BUTTON CASE CSIZE CSPACE COL CUESOB DEG DELTA DEVICE DISPLAY DIV ELSE END ERASE E i L L EBOH GBAPHICAL GBINPUT GBOUTPUT BABDCOPY EILIGHT HIT ...HI TON' IE INITIALIZE INSTANCE I NT EN INTO IS LIG LIGHTN LINE L1YPE LWIDTH HOD MOT Of ON OB FATTESN FIBSPECTIVE POLYGON PROCEDURES HEAD EOT SCI SCREEN STBOKB SOBPICTOBE TEXT THEN TO TYPES VALUE VARS VIEWPORT VIEHVOLOHE 81THIN HOBLDCOOBD. The LIG/P preprocessor r e c o g n i z e s g r a p h i c s statements by an a s t e r i s k {"*•") as the c h a r a c t e r i n column 1; a l l other source code l i n e s are c o p i e d immediately t o the output f i l e and a r e not t r a n s l a t e d by the p r e p r o c e s s o r . Except f o r t h i s r e s t r i c t i o n , LIG/P statements can be entered i n any format t h a t would a l s o be acceptable t o a P a s c a l c o m p i l e r . LIG/P and 44 P a s c a l statements nay not be mixed i n the same i n p u t l i n e , ficst LIG/P statements are t r a n s l a t e d i n t o i n v o c a t i o n s o f pro-cedures cf the g r a p h i c s run-time system. The run-time systen t y p e s , v a r i a b l e s and procedures have i d e n t i f i e r s with the p r e f i x " l i g " ; an a p p l i c a t i o n programmer can avoid i n t e r f e r e n c e with these p r e - d e f i n e d e n t i t i e s i f he chooses i d e n t i f i e r s not having M l i g " as t h e i r f i r s t charac-t e r s . 3•3 Program S t r u c t u r e The g e n a r a l format of a P a s c a l program, expressed i n Jsackus-Haur form, i s <prcgram> ::= <program heading> <blcck>. The program heading c o n t a i n s d e c l a r a t i o n s f o r c o n s t a n t s , types, v a r i a b l e s and e x t e r n a l procedures; the items appearing i n the program heading d e f i n e a g l o b a l environment f o r a l l procedures contained i n the procedure b l o c k . To compile a LIG/P program, the graphics t y p e s , g l o b a l v a r i a b l e s and e x t e r -n a l procedures must be made known to the P a s c a l . c ompiler. T h i s i s achieved by i n c l u d i n g type, v a r i a b l e and e x t e r n a l pro-cedure d e f i n i t i o n s i n the preprocessed source code by the pre-p r o c e s s o r . The a p p l i c a t i o n programmer must i n d i c a t e t o the prepr o c e s s o r where to i n s e r t those a d d i t i o n a l d e c l a r a t i o n s . Thus, t c the pr e p r o c e s s o r , a LIG/P program has the ge n e r a l format 45 <1IG/P program> : := <LIG/P program heading> <graphics statements>. <IIG/P program heading> ::= < l i g types> < l i g vars> < l i g procedures> < l i g types> = LIG TYPES; < l i g vars> LIG IkMS; < l i g procedures^ ::= LIG PBOCEDUBES; a complete program heading w i l l t h e r e f o r e look l i k e f o l l o w s : PBCGEAM ligdemc; (Example f o r a program heading} CONST minval = 0.0; maxval = 100.0; TYPE * LIG TXPES; c o o r d i n a t e s = BECCBD x,y,z : SEAL END; v as * LIG VfiBS; p o l y _ f a c e z &fifi&X£ 1....100 ] CF c o o r d i n a t e s ; * LIG PIsOCEDOJBES; PBOCEDOBE g e n _ a r c ( l o c : coordinates) ; FOBWafiD; BEGIN {main routine} The f i r s t LIG/P statement generates p r e - d e f i n e d g r a p h i c s types; the P a s c a l statement f o l l o w i n g i t d e f i n e s the g l o b a l type " c o o r d i n a t e s " . The second LIG/P statement generates the LIG/P system g l o b a l v a r i a b l e s , and the P a s c a l statement f o l -l o wing i t d e c l a r e s the g l o b a l a r r a y " p o l y _ f a c e " . B e f o r e any gra p h i c s o p e r a t i o n s can be performed, the gra p h i c s system has t c be i n i t i a l i z e d . . T h i s i n v o l v e s e s t a b -l i s h i n g a minimal data base and i n i t i a l i z i n g the d e f a u l t i n p u t and output d e v i c e s . I n i t i a l i z a t i o n i s performed by the s t a t e -4 6 Bent INITIALIZE LIG T h i s statement must be the f i r s t to be executed o f a l l graph-i c s statements. LIG/B statements are sepa r a t e d from each other by semico-l o n s . The l a s t LIG/P statement i n a program must be t e r m i -nated by a semicolon, and the e n d - o f - f i l e i s i n d i c a t e d to the preprocessor by a p e r i o d . T h i s p e r i o d may e i t h e r f o l l o w the l a s t LIG/P statement immediately, or be i n s e r t e d on any subse-quent l i n e (which has a i n column 1). 3.4 Modelling F u n c t i o n s The modelling f u n c t i o n s o f LIG/P are invoked by the mod-e l l i n g statements; these allow a programmer t o def i n e g r a p h i -c a l o b j e c t s i n v a r i o u s ways. The system generates a c o r r e -sponding data base which i s t r a v e r s e d by the d i s p l a y f u n c t i o n s to generate v i s i b l e images on an cutput d e v i c e . 3 . 4 . 1 Graphics Types LIG/P i n t r o d u c e s a d d i t i o n a l data types which are pre-de-f i n e d types to the a p p l i c a t i c n program. . These types a r e : {GRAPHICAL, SUBPICTOBE, INSTANCE, GBINPOT, GBOUTPOT, VIEHVOiaME, VIEBF0R1}. The f i r s t two cf t h i s s e t are used t o d e f i n e g r a p h i c a l o b j e c t s , the others are used f o r d i s p l a y i n g such o b j e c t s . 47 V a r i a b l e s are d e c l a r e d i n P a s c a l statements, and f o l l o w the same scope r u l e s as a l l other v a r i a b l e s . G l o b a l v a r i a b l e s c o u l d , f o r example, be d e c l a r e d i n the program heading l i k e t h i s : V A B * LIG VABS; and_gate : GEAPHICAL; ch i p : ABBAY{1.. 10] OP GBAPHICAL; element : AfiBAY£1..10] OP SUBPICTOBE G r a p h i c a l v a r i a b l e s can be passed as parameters to func-t i o n s and procedures., T h i s must be done with c a r e , though. A programmer must keep i n mind that a g r a p h i c a l v a r i a b l e con-t a i n s a p o i n t e r to a complex data s t r u c t u r e i n the g r a p h i c s data base. fthen passing a g r a p h i c a l v a r i a b l e by value, only t h i s p o i n t e r i s being c o p i e d , and n o t the e n t i r e s t r u c t u r e d e f i n i n g the g r a p h i c a l variable.,; To avoid unintended r e s u l t s , g r a p h i c a l v a r i a b l e s should t h e r e f o r e always be passed by r e f -erence, or, i n P a s c a l terminology, as ••variable parameters". G r a p h i c a l v a r i a b l e s are d e f i n e d by a s s i g n i n g them g r a p h i -c a l p r i m i t i v e s , g r a p h i c a l f u n c t i o n y i e l d s , or other g r a p h i c a l v a r i a b l e s , , LIG/P provides f o u r p r e - d e f i n e d output p r i m i t i v e s and f o u r p r e - d e f i n e d f u n c t i o n s . The i d e n t i f i e r s of the output p r i m i t i v e s and p r e - d e f i n e d f u n c t i o n s are/?, r e s e r v e d words and may n o t be r e d e f i n e d . , The output p r i m i t i v e s are BLANK, LINE, POLYGON, and l i t e r a l s t r i n g s . LINE and POLYGON have a b s o l u t e and r e l a t i v e c o o r d i n a t e v e r s i o n s . , •The f u n c t i o n s are Arc, 48 P o l y l i n e , Polygon and l v a l u e . , A d i s t i n c t i o n i s made between p o l y l i n e s and polygons because c e r t a i n a t t r i b u t e s may be used i n c o n j u n c t i o n with polygons but not with p o l y l i n e s . Examples f o r p r i m i t i v e s a r e : BLANK LINE F.BOH x1,y1,z1 30 x2,y2,z2 {single l i n e ] LINE FEOH x1,y1,z1 TO x2,y2,z2 TO x3,y3,z3 TO x4,y4,z4 {polyline} LINE FECH x1,y1,z1 DELTA dx2,dy2,dz2 DELTA dx3,dy3,dz3 DELTA dx4,dy4,dz4 ( r e l a t i v e p o l y l i n e ) PGIYGCK FEOH x1,y 1,z1 TC x2,y2,z2 TO x3,y3,z3 { t r i a n g l e , absolute coordinates} POLYGON FBOH x1,y DELTA dx2,dy2,dz2 DELTA dx3,dy3,dz3 { t r i a n g l e , r e l a t i v e coordinates} • T h i s i s a s t r i n g p r i m i t i v e . • The p r e - d e f i n e d f u n c t i o n s are d e c l a r e d as f o l l o w s : TYPE r e a l a r r a y : A£fiAY£1..200] CF BEAL; c b a r _ a r r a y : ABBAY£1..40 ] OF CHAB; FUNCTION A r c ( x c e n t r € , y c e n t r e , rad, s p a n g l e , f _ a n g l e : BEAL): GRAPHICAL; FUNCTION P o l y l i n e ( x _ a r r a y , y _ a r r a y , z ^ a r r a y : r e a l _ a r r a y ; n: INTEGEB): GBAPHICAL; FONCTION Polygon (x_array, y _ a r r a y , z£array: r e a l _ a r r a y ; n: INTEGEB): GRAPHICAL; FONCTION l v a l u e ( t e x t _ a r r a y : c h a r _ a r r a y ; n: INTEGEB): GRAPHICAL; In a d d i t i o n to the four p r e - d e f i n e d f u n c t i o n s a program-mer can d e f i n e h i s own g r a p h i c a l f u n c t i o n s . . T h i s i s d i s c u s s e d i n more d e t a i l i n S e c t i o n 3.4.6. 4 9 5. 4 . 2 Coordinate Systems LIG/P supports two coor d i n a t e systems: a world c o o r d i n a t e system f o r modelling and a Normalized Device Coordinate (NDC) system f o r d i s p l a y purposes. The range of c o o r d i n a t e s f o r the world c o o r d i n a t e system i s s p e c i f i e d by the a p p l i c a t i o n pro-gram i n an executable statement, i . e . the world c o o r d i n a t e s can be changed dynamically., The statement has the format W0ELDCO0ED xlow.vxhigh, ylow.vyhigh, zlow.,.,zhigh where xlcw,xbigh^ylcw,yhigh,zlow,zhigh are r e a l c onstants or v a r i a b l e s . Parameters f o r output p r i m i t i v e s , e.g. LINE FBOM x t , y 1 , 2 l TO x2,y2,z2, must l i e w i t h i n the range of world coor-d i n a t e s . I f n o w o r l d c o o r d i n a t e range i s e x p l i c i t l y d e f i n e d , i t d e f a u l t s to the range 0..1 f o r a l l three axes. D i s p l a y f u n c t i o n s use the NDC system; normalized d e v i c e c o o r d i n a t e s have the range 0..1 i n a l l t h r e e d i r e c t i o n s . An a p p l i c a t i o n programmer need never be concerned with a c t u a l device c o o r d i n a t e s — the c o n v e r s i o n from NDC to device coor-d i n a t e s i s the task c f the de v i c e d r i v e r s . 3 . 4 . 3 d e l lino, I r a n s f o r mat i o ns and a t t r i b u t e s T r a n s f o r m a t i o n s and a t t r i b u t e s are used t o modify p r i m i -t i v e s , s u b p i c t u r e s , and the value returned by g r a p h i c a l func-t i o n s when these e n t i t i e s d e f i n e a g r a p h i c a l v a r i a b l e . M o d i f i c a t i o n s c o n s i s t of any subset of the a v a i l a b l e m o d i f i c a -t i o n o p e r a t o r s ; those not s p e c i f i e d d e f a u l t t o a p r e - d e t e r -50 mined va l u e . M o d i f i c a t i o n a t t r i b u t e s have the highest prece-dence of a l l LIG/P ope r a t o r s ; t h e i r parameters are i n world c o o r d i n a t e s and are simple c o n s t a n t s , P a s c a l v a r i a b l e s or a r i t h m e t i c e x p r e s s i o n s . , F o r m a l l y , m o d i f i c a t i o n s are d e f i n e d as M o d i f i c a t i o n l i s t > s : = < m o d i f i c a t i p n X ] M o d i f i c a t i o n l i s t > <modification> <modification> z:= t r a n s f o r m a t i o n operator> <parameter_3> | <attribute> <par> <parameter_3> <par>,<par>,<par> <par> zz = <variable> | <constant> | <arithm. expression> A t r a n s f o r m a t i o n operator s p e c i f i e s a geometric t r a n s f o r m a t i o n which can be s c a l i n g , r o t a t i o n or t r a n s l a t i o n . , The s e t of o p e r a t o r s to perform.these m o d i f i c a t i o n s i s {SCL, SOT, AT}. Each has t h r e e parameters which must be of type r e a l ; they d e f i n e the geometric t r a n s f o r m a t i o n s with r e s p e c t to x , y , and z. A g r a p h i c a l v a r i a b l e p may f o r example be assigned a sub-p i c t u r e of the g r a p h i c a l v a r i a b l e unit_cube, but h a l f the s i z e c f u n i t _ c u t e , r o t a t e d and t r a n s l a t e d . . I f unit_cube has as value the g r a p h i c a l o b j e c t as shown i n F i g u r e 2, then the sub-p i c t u r e unit_cuh€ SCL 0.5,0.5,0.5 BOT 30.0,30.0,30.0 DEG assigned to p, would g i v e p the value shown i n Figure 3. The three parameters of BOT may be f o l l o w e d by the keyword DEG i f the three values a r e i n degrees; i f DEG i s omitted, the values are assumed to be r a d i a n s . .. T r a n s l a t i o n parameters are i n world c o o r d i n a t e s . The 51 F i g u r e 2 F i g u r e 3 system generates an e r r o r message i f the values l i e o u t s i d e the c u r r e n t l y d e f i n e d wcrld c o o r d i n a t e range. The o r d e r of t r a n s f o r m a t i o n s i s always s c a l i n g f o l l o w e d by r o t a t i o n f o l l o w -ed by t r a n s l a t i o n with the r e f e r e n c e p o i n t a t the o r i g i n . , The a t t r i b u t e s provided f o r m o d e l l i n g a r e the s e t £COL, XIGBTN, INTFN, LBIMH, LTYPE, CSIZE, CSPACE, PATTERN, FILL}. 2 h e i r use has the f o l l o w i n g e f f e c t s : CCL: T h i s a t t r i b u t e d e f i n e s the c o l o u r of a p r i m i t i v e o r sub-p i c t u r e . One c f e i g h t c o l o u r s may be s e l e c t e d as a pa-rameter: BLACK, BED, GBEEN, BLUE, CYAN, YELLOW, KAGENTA, 8HITE. LIG/P does not allow mixing of c o l o u r s or u s i n g d i f f e r e n t hues c f a c e r t a i n c o l o u r . I f t h i s i s d e s i r e d f o r l a r g e r areas, i . e . , f o r f i l l e d polygons, the PATTERN a t t r i b u t e may achieve the d e s i r e d e f f e c t . The d e f a u l t c o l o u r i s BHITF. LIGHTN: The d e f a u l t l i g h t n e s s of a c o l o u r i s 1.. Any va l u e i n 52 the range 0.,1 i s v a l i d . The parameter defines the lightness cf a corresponding COL-attribute. IKTEN: The intensity of a^graphical object defaults to 0.5; t h i s may be changed by specifying a higher or lower value. Some application programs achieve a depth cue by varying the intensity of output primitives. As with c o l -our, the ef f e c t of t h i s modification i s dependent on the output devices available. 1HIDTHi If a l i n e width other than that produced by a single stroke of the beam cr pen of an output device i s desired, the parameter of LSIDTH in world coordinates may be used to produce a thicker l i n e . , ITXPE: This modification determines what l i n e s t y l e i s to be used tc output a graphical object. The parameter i s an integer value and defaults to 1 for " s o l i d l i n e " . In the current implementation l i n e type 2 i s a short-dashed l i n e and l i n e type 3 i s a lcng-dashed l i n e . CSIZE, CSPACE: For text output primitives the character size and spacing between the characters i n world coordinates may be reset from the default values. Default values use the hardware character generator that most output devices have. , 5 3 PATTEBN: T h i s operator has aa i n t e g e r parameter which s p e c i -f i e s which of a l l a v a i l a b l e p a t t e r n s i s t o be used to f i l l a polygon. The p a t t e r n s a v a i l a b l e a r e i n s t a l l a t i o n dependent and the r e s u l t of using t h i s m o d i f i c a t i o n i s a l s c dependent cn the output d e v i c e . PILL: T h i s m o d i f i c a t i o n has no parameter and a p p l i e s o n l y t o POLYGON p r i m i t i v e s . , I f a polygon i s FILLed then e i t h e r the c u r r e n t PATTEBN m o d i f i c a t i o n determines the shading o f the polygon, o r , i f no p a t t e r n i s s p e c i f i e d , the COL m o d i f i c a t i o n a p p l i e s . . A g r a p h i c a l v a r i a b l e may be d e f i n e d as a h i e r a r c h y of p r i m i t i v e s or s u b p i c t u r e s . , C e r t a i n scope r u l e s must be esta b -l i s h e d t c d e f i n e how a g r a p h i c a l o b j e c t appears on the view s u r f a c e i f t r a n s f o r m a t i o n s and a t t r i b u t e s are a p p l i e d a t d i f -f e r e n t l e v e l s i n the h i e r a r c h y . , F o r t r a n s f o r m a t i o n s the r e s u l t i s obvious. Transformation parameters are concatenated such t h a t the r e -s u l t i n g t r a n s f o r m a t i o n i s the sum of a l l p r e v i o u s transforma-t i o n s higher up i n the h i e r a r c h y . , As an example, l e t the g r a p h i c a l v a r i a b l e p be d e f i n e d i n terms of g, and g be d e f i n e d i n terms of r , where r i s the u n i t cube. A s u b p i c t u r e of g i s r SCL 0.8,0.8,0.8 SOI 20.0,10.0,0.0 DEG I f q i s d i s p l a y e d , the g r a p h i c a l o b j e c t i n F i g u r e 4 i s shown. y t ! 1 y t X F i g u r e 4 F i g u r e 5 Jew l e t p have the suhpicture g SCL 0.25,0.5,0.75 EOT 20.0,0.0,0.0 DEG Displaying p r e s u l t s i n Figure 5. , Attrib u t e s earnest be concatenated i n the same way as transforaatiens can; i f a t t r i b u t e parameters at d i f f e r e n t l e v e l s are s p e c i f i e d , then one w i l l override a l l others. The following rules apply: 1.. I f graphical primitives are assigned a t t r i b u t e s other than by default then they are always displayed with these a t t r i b u t e s . 2. , Ihe non-default a t t r i b u t e s at the highest l e v e l i n the hierarchy are applied, unless Bale 1 overrides t h i s r u l e . . An example shows the e f f e c t of these two r u l e s . To i l -55 l u s t r a t e Bule 2, l e t r te a f i l l e d polygon i n the d e f a u l t c o l o u r white. Let the g r a p h i c a l v a r i a b l e s p, g and r be de-f i n e d i n terms of each other as b e f o r e . I f q has the s u b p i c -t u r e r CCL BLUE then q i s d i s p l a y e d as a b l u e polygon. I f p has as s u b p i c t u r e g COL YELLOW then p i s d i s p l a y e d as a yellow polygon.. I f , however, p has s u b p i c t u r e g {default c o l o u r , i . e . no s p e c i f i c a t i o n } then p i s d i s p l a y e d as a blue polygon, j u s t l i k e g. To i l l u s -t r a t e Bule 1, l e t r be d e f i n e d as the p r i m i t i v e POLYGON COL BEE FILL FBOH ... TO ... TO Then any v a r i a b l e having r as a s u b p i c t u r e w i l l be d i s p l a y e d as a red polygon (and p o s s i b l y other p a r t s ) . 3 . 4 . 4 The Synonym assignment Operator There are two d i f f e r e n t assignment o p e r a t o r s In LIG/P; both are used to d e f i n e g r a p h i c a l v a r i a b l e s , but the v a r i a b l e s 1 i n t e r n a l r e p r e s e n t a t i o n s d i f f e r i f one operator i s used i n s t e a d of the other./ A simple assignment statement has the g e n e r a l format p :- q <modificaticns> where p i s a v a r i a b l e of type GRAPHICAL and g i s a p r i m i t i v e , a g r a p h i c a l f u n c t i o n or a v a r i a b l e of type GRAPHICAL, even p 56 i t s e l f . The syncnyn assignment i s used to b u i l d a h i e r a r c h i -c a l s t r u c t u r e as d e f i n i t i o n of a g r a p h i c a l v a r i a b l e . U n l i k e a nu m e r i c a l assignment such as x :- y, where the value of y i s copied i n t o storage l o c a t i o n x, the synonym assignment does not copy values but merely s e t s p o i n t e r s i n the data base, i n t h i s case from p to g. Thus, p i s now dependent on g and i f q changes, p changes a c c o r d i n g l y . The advantages of t h i s scheme are f l e x i b i l i t y , s a v i n g of st o r a g e space and i n g e n e r a l t a k i n g i n t o account the a c t i o n s t h a t are o f t e n performed cn g r a p h i c s data bases; i n t e r a c t i v e g r a p h i c s uses h i g h l y dynamic e n t i t i e s and data base a c c e s s to them must be f a s t ; removing a s u b p i c t u r e from the d e f i n i t i o n of a g r a p h i c a l v a r i a b l e must be done q u i c k l y and e f f i c i e n t l y , e.g. I n terms of garbage c o l l e c t i o n . , 3 . 9 . 5 The Copy Assignment Operator The second assignment operator i n LIG/P i s the copy-as-signment o p e r a t o r ; the g e n e r a l format c f a ccpy-assignment i s p 2 = g <modifications> where p and q represent the same symbols as i n the p r e v i o u s s e c t i o n . , A copy-assignment t r a v e r s e s the e n t i r e data s t r u c t u r e of g and c r e a t e s a g r a p h i c a l c o n s t a n t frcm the d e f i n i t i o n of g. T h i s c o n s t a n t i s a s s i g n e d t o p. Subseguently, p i s indepen-dent of q and changes t o q do not a f f e c t p. I t i s e v i d e n t 57 t h a t t h i s i s an expensive process i n terms of time and storage space and should be used c a u t i o u s l y . Once a v a r i a b l e i s de-f i n e d i n t h i s say. i t i s not p o s s i b l e t o d e l e t e s u b p i c t u r e s frcm i t . 3•to.6 G r a p h i c a l Functions A g r a p h i c a l v a r i a b l e can be d e f i n e d with g r a p h i c a l func-t i o n y i e l d s as s u b p i c t u r e s . The f u n c t i o n name and a c t u a l par rameter l i s t appear i n an assignment statement j u s t l i k e prim-i f i v e s o r oth e r s u b p i c t u r e s would. I f a f u n c t i o n has no formal parameters;then the s p e c i a l symbol n ( ) " must f o l l o w the f u n c t i o n nase. The ge n e r a l format c f an assignment using a graphica1 f u n c t i o n i s : a :- Fname ( p 1 , p 2 , . ..) ^ m o d i f i c a t i o n s * a :- Fname () <modif i c a t i o n s > a := Fname ( p 1 , p 2 , . . . ) <modificaticns> a s= Pname () <modif i c a t i o n s > G r a p h i c a l f u n c t i o n s may have l o c a l g r a p h i c a l v a r i a b l e s , dn a p p l i c a t i o n programmer should use t h i s f e a t u r e c a u t i o u s l y , though. Each time the f u n c t i o n e x i t s , the p o i n t e r s i n t o the data base to the d e f i n i t i o n of the l o c a l v a r i a b l e s are l o s t and the storage space cannot be re c l a i m e d by the LIG/P garbage c o l l e c t i o n r o u t i n e s . A p a r t i a l remedy would be the assignment to a simple g r a p h i c a l p r i m i t i v e before e x i t i n g the r o u t i n e , e.g. l c c a l _ v a r :- ELAMK, t o l o s e a s l i t t l e space as p o s s i b l e ; 58 a l t e r n a t i v e l y , as many g l o b a l v a r i a b l e s as i s reasonable i n a p a r t i c u l a r program should be used, because each time they are r e d e f i n e d the storage space occupied by t h e i r previous d e f i n i -t i o n i s r e c l a i m e d . G r a p h i c a l f u n c t i o n s are de f i n e d l i k e o ther P a s c a l func-t i o n s ; a f u n c t i o n d e c l a r a t i o n c o n s i s t s of a f u n c t i o n heading, f o l l o w e d by the formal parameter l i s t , f o l l o w e d by the type of o b j e c t r e t u r n e d by the f u n c t i o n . A g r a p h i c a l f u n c t i o n r e t u r n s an o b j e c t of type GRAPHICAL. Formal parameters may i n c l u d e those of type GRAPHICAL (see comments on t h i s i n S e c t i o n 3 . 4 . 1 ) . Before a f u n c t i o n r e t u r n s , a copy-assignment must be executed which a s s i g n s a g r a p h i c a l o b j e c t to the f u n c t i o n name. This o b j e c t i s returned as the y i e l d of the f u n c t i o n . The f o l l o w i n g program s e c t i o n i l l u s t r a t e s the use of g r a p h i c a l f u n c t i o n s : PICGBaH funct_demc; (Example for graphical function} TYPE * LIG TYPES; ¥ AB * LIG VftlS; f i g : GRAPHICAL; * U G PEOCEDOIES; FUBCTICN Circl€_2d{xcent,ycent,rad; HEAL)• GRAPHICAL {Generates a c i r c l e uith radius "rad" and centre (xcent.ycent) i n the 2=0 plane,} CCBSI p i = 3. 141593; z = 0.0; ten_degrees = pi/18.0; VAE angl, x1,y1,x2,y2 , BEAL; gen_circle : GBAEHICAL; B E G I N * gen_circle BLANK; angl := 0.0; x2 := rad; y2 := 0.0; REPEAT x 1 := x2; y1 := y2; angl :=, angl * ten_degrees; x2 z= rad * COS (angl) ; y2 := rad * SIN (angl) ; * gen c i r c l e :- gen.circle *+ LINE FiBGH x1,y1,z * "~ TO x2,y2,z; UNTIL angl >= 2 * p i ; {assign value to function name} * Circle_2d := gen_circle AT xcent,ycent,z; * gen_circle s- BLANK; {release temporary storage} END; BEGIN {aain routine] * INITIALIZE LIG; * HOBLDCOCRB 0.0.. 100. 0, 0.0.. 100. C, 0.0.. 100.0; * f i g :- Circle_2d (20. 0,30. 0,15.0) COL BED; END. * {End LIG/Pf 60 3.4.7 The S u p e r p o s i t i o n Operator The previous s e c t i o n s d e s c r i b e d the d e f i n i t i o n of simple g r a p h i c a l o b j e c t s . The s u p e r p o s i t i o n operator " ++'? i s used t o de f i n e complex g r a p h i c a l o b j e c t s . A g r a p h i c a l v a r i a b l e can c o n s i s t of many p r i m i t i v e s or s u b p i c t u r e s ; a h i e r a r c h y of these i s c r e a t e d by using the synonym assignment operator and the s u p e r p o s i t i o n o p e r a t o r . "-» + " i s a d y a d i c operator with g r a p h i c a l terms as operands t o form g r a p h i c a l e x p r e s s i o n s . A g r a p h i c a l e x p r e s s i o n i s assign e d t o ; a g r a p h i c a l v a r i a b l e . F o r m a l l y , a s s i g n m e n t statement* ::= <gr var* <assign op> <gr e x p r e s s i o n * <assign op* : - J : = <gr e x p r e s s i o n * ::= <gr term* I <gr e x p r e s s i o n * <gr term* <gr term* ::= <gr primary* I <gr primary* M o d i f i c a t i o n l i s t * <gr primary* ::= <gr v a r i a b l e > J <gr p r i m i t i v e * | <gr f u n c t i o n i n v o c a t i o n * For example, l e t a :- U S E FEGH 0.0,0.5,0.0 TO 1.0,0.5,0.0; b a COL BED BOT 0.0,0.0,20.0 DEG; c :- a COL BLUE BOT 0.0,0.0,40.0 DEG; d :- a •* b c The v a r i a b l e d, when d i s p l a y e d , shows a white h o r i z o n t a l l i n e , as w e l l as a red and a blue l i n e r o t a t e d i n c r e m e n t a l l y by 20 degrees about the z - a x i s . When used i n c o n j u n c t i o n with the copy-assignment opera-t o r , a g r a p h i c a l e x p r e s s i o n i s converted to a "constant" and 61 i s assigned t c a g r a p h i c a l v a r i a b l e . The statement d ;= a b c f o r a, b, and c as i n the p r e v i o u s example, w i l l v i s u a l l y pro-duce the same r e s u l t . , The i n t e r n a l r e p r e s e n t a t i o n of d w i l l be d i f f e r e n t , though. The S e c t i o n s 3 .4 .8 and 3 . 4 . 9 d i s c u s s cases where t h i s i s important.. S u p e r p o s i t i o n of a g r a p h i c a l v a r i a b l e onto i t s e l f i s i l -l e g a l ; a statement of the form d :- a <m> b <m> d <m> r e s u l t s i n a r e c u r s i v e d e f i n i t i o n of d and i s not allowed. G r a p h i c a l f u n c t i o n s may be c a l l e d r e c u r s i v e l y , as long as the s u p e r p o s i t i o n does not generate a r e c u r s i v e d e f i n i t i o n of a g r a p h i c a l v a r i a b l e as shown i n the example above. 3 . 4. I The- Naming Operator The naming operator "ftS" i s used to g i v e a s u b p i c t u r e a unigue name by which i t can be r e f e r r e d to ^ f o r d e l e t i o n and i d e n t i f i c a t i o n . For example, C b COL BIDE LTSPE 2 AS b_blue b COL GBEEN LTYPE 3 AS b_green as s i g n s two named s u b p i c t u r e s to c. The v a r i a b l e s b_blue and b_green must be d e c l a r e d of type SOBPICTUBE. The naming operator may not be used i n a g r a p h i c a l ex-p r e s s i o n f o r a ccpy-assignment. As e x p l a i n e d b e f o r e , the s t r u c t u r e o f a g r a p h i c a l v a r i a b l e ' s d e f i n i t i o n i s l o s t i n a 62 copy-assignment and i t i s t h e r e f o r e meaningless to name p a r t s cf i t . Any < g r a p h i c a l primary* may be named to c r e a t e a named s u b p i c t u r e ; i n the example above, b co u l d be a p r i m i t i v e , a f u n c t i o n i n v o c a t i o n , or a v a r i a b l e of type GRAPHICAL. The o p e r a t i o n s allowed on a named s u b p i c t u r e are not the same as those f o r a v a r i a b l e of type GRAPHICAL. The only l e g a l and meaningful o p e r a t i o n s are d e l e t i o n , i d e n t i f i c a t i o n and d i s -p l a y . 3.4.9 The D e l e t i o n Operator T h i s o p e r a t o r , represented by the s p e c i a l symbol " — " , allows the removal of named s u b p i c t u r e s from the d e f i n i t i o n of a g r a p h i c a l v a r i a b l e . The s u b p i c t u r e must have been superim-posed i n a g r a p h i c a l e x p r e s s i o n evaluated; p r e v i o u s l y , o t h e r -wise an e r r o r message i s generated. The g e n e r a l form of a g r a p h i c a l e x p r e s s i o n i n v o l v i n g a d e l e t i o n i s a :- b <m> AS s; a :- a — s or a :- a c <m> — s or a :- a -- s *• c<m> A statement c f the form a :- b — s 63 where s i s a named subpicture of b i s not allowed. Deletion i s allowed only at the highest l e v e l i n a hierarchy of subpic-tures; the named subpicture must have been superimposed ex-p l i c i t l y onto the graphical variable i t i s deleted from. 3.4. 10 The I d e n t i f i c a t i o n Statements In the LIG/P system each named subpicture has associated with i t an " i d e n t i f i c a t i o n area". This i s the z=zmin plane within the range of world coordinates that were v a l i d at the time when the subpicture was defined. The i d e n t i f i c a t i o n area i s transformed with the subpicture and can be "picked" by placing a locator inside the subpicture*s i d e n t i f i c a t i o n area. The application program has to test for a pick of a spe-c i f i c subpicture; this i s i n contrast to many graphics systems where any object can be picked and some i d e n t i f i e r i s returned to the application program. LIG/P avoids t h i s on purpose; i t s high-level constructs avoid the "ambiguity f a l l a c y " discussed by Newman and Sproull [ Newm79 ]: "Systems designers should avoid the ambiguity f a l l a -cy, which postulates that since an item may have several levels of ancestry, i t i s impossible to de-termine to which l e v e l the user i s re f e r r i n g when he points at the item., This problem i s often posed using a c i r c u i t as an example: i f the user points at a r e s i s t o r , i s he trying to indicate the r e s i s t o r , or the c i r c u i t cf which the r e s i s t o r forms a part, or just a certain li n e within the r e s i s t o r ? This s i t u a t i o n should never occur i n a well-constructed program, which should always either know the l e v e l i n which the user i s interested or should ask him to 64 s t a t e the l e v e l . I t i s an i n d i c a t i o n of s e r i o u s d e f i c i e n c i e s i n the command language i f the user i s a b l e t o make an ambiguous p o i n t i n g a c t i o n . " An i d e n t i f i c a t i o n statement c o n s i s t s of the c l a u s e "IF HII CM" or "IF NCI H i t ON" f o l l o w e d by a s u b p i c t u r e name or a p a r e n t h e s i z e d l o g i c a l e x p r e s s i o n i n v o l v i n g s u b p i c t u r e names; the a c t i o n to be taken i s i n d i c a t e d i n a statement group f o l l o w i n g THEN, which i s o p t i o n a l l y f o l l o w e d by ELSE and a statement group. The f o r m a l d e f i n i t i o n of an i d e n t i f i c a t i o n statement i s : i d e n t i f i c a t i o n statement> ::= <simple i d n stmt> | <composite i d n stmt> < s i a p l e i d n stmt> ::= <idn clause> THEN <statement group> <compcsite i d n stmt> ;:= <simple i d n stmt> ELSE <statement group> <idn clause> ::= I I BIT ON <idn expressicn> 1 IF HOT HIT ON <idn expression> <idn expression> zz- <subpicture name> ! | { C l o g i c a l expression> ) < l o g i c a l expression> ::= <subpicture name> <log op> <subpicture name> | C l o g i c a l expression> Clog op> <subpicture name> <log cp> ::= AND 1 OB <statement group> ::= C l i g statement> | BEGIN < l i g statement l i s t > END < l i g statement 3ist> ::= < l i g statement> 1 < l i g statement l i s t > ; < l i g statement> An i d e n t i f i c a t i o n statement must be preceded by the con-t r o l statement "COBSOB ON" (see S e c t i o n 3.7) t o d i s p l a y a .terminal's g r a p h i c s c u r s o r and wait f o r an i n t e r r u p t . The f o l l o w i n g program s e c t i o n and f i g u r e s i l l u s t r a t e the i d e n t i f i c a t i o n p r o c e s s : 65 VAE menu, c o t e , pyramid . GBAPHICAL; B _ i t e s : A££AY£1. . 10 ] OF SDBPICTOBE; BEGIN • 8CELDC00BD 0.0..100.0, 0.0.. 100.0, 0.0..100.0; • cure :- U n i t _ c u t e (0.0,100.0) ; • pyramid :- Pyraaid_4 (0.0, 100.0) ; •menu cube SCL xs, y s , z s AT x,y,z AS m_item£ 1 ] •* p y r a c i d SCL x s , y s , z s AT x,y-dy,z AS m_item£2]; • CDESOE ON; • IF HIT ON (m_item£1] 08 m_item£2 3) THEN <statement grcup> • U S E <statement group> F i g u r e s 6 and 7 show the g r a p h i c a l o b j e c t s cube and pyra-66 I i i I I I i l U 1 0 .100 F i g u r e 8 l i d , assuming t h a t g r a p h i c a l f u n c t i o n s Onit__cube and Pyramid_4 generate these o b j e c t s * The dashed frames i n d i c a t e the un-t r a n s f o r o e d i d e n t i f i c a t i o n areas o f cube and pyramid. F i g u r e 8 shows the g r a p h i c a l o b j e c t menu which c o n s i s t s of the two named s u b p i c t u r e s m_itea[ 1,] and m_item[2]. These two s u b p i c -t u r e s may be picked i n at i d e n t i f i c a t i o n statement; the c u r s o r must l i e i n t h e ; r e s p e c t i v e i d e n t i f i c a t i o n area f o r a h i t to have o c c u r r e d . I t i s e v i d e n t t h a t a r o t a t i o n about the x or y - a x i s may d i s t o r t the i d e n t i f i c a t i o n area to a degree where i t c o u l d become almost i m p o s s i b l e to i d e n t i f y a s u b p i c t u r e . C a r e f u l programming can avoid t h i s and ensure t h a t a named s u b p i c t u r e i s always d e f i n e d i n such a way t h a t a " r e a s o n a b l e " i d e n t i f i -c a t i o n area r e s u l t s . LIG/P a l s o p r o v i d e s a c a s e - c o n s t r u c t t o choose between a l t e r n a t i v e a c t i o n s , depending on the s u b p i c t u r e t h a t was h i t . The case-statement has the g e n e r a l form 67 CASE BITCH Of 3 1,52 : <statement group*; s3 : <statement group>; s4,s5,s6 : <statement group*; « •» • END The f o r m a l d e f i n i t i o n i s : <case stmt* ::= CASE BITON OF <case l i s t * END <case l i s t * ::= <case element* | <case l i s t > ; <case element* <case element* <case l a b e l l i s t * : <statement group* <case l a b e l . l i s t * ::= <subpicture name* | <case l a b e l l i s t * , <subpicture name* <statement group* i s d e f i n e d as before.,, 3.5 The D i s p l a y F u n c t i o n s The d i s p l a y f u n c t i o n s of LIG/P use the d e f i n i t i o n of g r a p h i c a l v a r i a b l e s to generate v i s i b l e images on a view s u r -f a c e . .. The language provides f a c i l i t i e s t o s e l e c t d i f f e r e n t output d e v i c e s , perform c l i p p i n g , a p e r s p e c t i v e transforma-t i o n , mapping from a view volume i n t o a 3D-rviewport, and app-l y i n g image t r a n s f o r m a t i o n s . 68 3.5.1 Geyice D e f i n i t i o n G r a p h i c a l output d e v i c e s are r e f e r r e d to by names d e f i n e d i n the a p p l i c a t i o n program, an output d e v i c e must be d e c l a r e d as a v a r i a b l e and i s of type GfiOOTPOT ( t h i s i s analogous to a P a s c a l f i l e d e c l a r a t i o n using t h e p r e - d e f i n e d type TEXT). In an executable statement the d e c l a r e d device i s a s s o c i a t e d with a p h y s i c a l device through i t s l o g i c a l u n i t number. This number i s s u p p l i e d by the o p e r a t i n g system at a p a r t i c u l a r i n s t a l l a t i o n , a d e vice a s s o c i a t i o n statement has the form DEVICE <device-id> IS <device-lu> a <deyice-lu> i s e i t h e r a named P a s c a l constant of type i n t e -ger, a P a s c a l v a r i a b l e to uhich an i n t e g e r value has been as-s i g n e d , or a P a s c a l f u n c t i o n r e t u r n i n g an i n t e g e r , an example i s : CONST s y s p l o t = 9; t4014 = 2; t4027 = 1; vas p l o t t e r , s t _ t u t e , c c l _ t e r m i n a l : GBOOTPOT; BEGIN ( a s s o c i a t e i n t e r n a l d e v i c e s with p h y s i c a l devices] * DEVICE p l o t t e r IS s y s p l o t ; * DEVICE s t _ t u b e IS t4014; * CIVICB c o l _ t e r m i n a l IS t4027; The d e v i c e s p l o t t e r , s t _ t u b e and c o l _ t e r m i n a l can now be used f o r g r a p h i c a l output. Not a l l of them are enabled at t h i s 69 point, bot.each device H i l l be i f i t i s r e f e r r e d to i n a d i s -play statement. The system p r o v i d e s one master t e r m i n a l and one hardcopy output device by d e f a u l t . , I t i s t h e r e f o r e not mandatory, and at some i n s t a l l a t i o n s net even p o s s i b l e , to d e f i n e and s e l e c t a number of output d e v i c e s . 3.5.2 anonymous and Hamed Instan c e s The value o f g r a p h i c a l v a r i a b l e s , p r i m i t i v e s o r func-t i o n s , when d i s p l a y e d on a view s u r f a c e , i s c a l l e d an i n -stance ; thus, every g r a p h i c a l o b j e c t on the screen of a t e r m i -n a l i s an instance., Many i n s t a n c e s of the same g r a p h i c a l v a r i a b l e , f u n c t i o n or p r i m i t i v e may be d i s p l a y e d at the same time. I n s t a n c e s may be modified by d i s p l a y m o d i f i c a t i o n s . I f many i n s t a n c e s of the same g r a p h i c a l item are d i s p l a y e d they may be d i s t i n g u i s h e d f r o a each other by g i v i n g them names, much l i k e naming s u b p i c t u r e s of the same g r a p h i c a l v a r i a b l e , an i n s t a n c e i s named by using the ope r a t o r "ftS M f o l l o w e d by an i n s t a n c e name. V a r i a b l e s of t j p e ISSTaBCE are d e c l a r e d i n a P a s c a l v a r i -able d e c l a r a t i o n statement.,. Such v a r i a b l e s are used t o s e l e c -t i v e l y erase i n s t a n c e s from a view s u r f a c e . anonymous i n -stances are erased only when a l l i n s t a n c e s of a p a r t i c u l a r g r a p h i c a l v a r i a b l e are erased or when an e n t i r e view s u r f a c e 70 i s e rased. 3.5.3 The D i s p l a y Statements A d i s p l a y statement c o n s i s t s of the keyword DISPLAY or HARDCOPY fo l l o w e d by a l i s t of g r a p h i c a l v a r i a b l e s , p r i m i t i v e s cr f u n c t i o n s . The d i f f e r e n c e between the two statements i s that HARDCOPYed i n s t a n c e s cannot be erased afterwards, and that a t the end of a HARDCOPY statement a new-frame a c t i o n i s performed such t h a t only the i n s t a n c e s i n the same d i s p l a y statement a r e shown superimposed on each other. Each g r a p h i c a l item i n a d i s p l a y statement may be modi-f i e d by d i s p l a y a t t r i b u t e s , viewing t r a n s f o r m a t i o n s and image t r a n s f o r m a t i o n s (described i n S e c t i o n 3.5.4). A s p e c i a l o perator f o l l o w e d by a device name i s used to s p e c i f y on which view s u r f a c e the i n s t a n c e i s to be shown.. I f t h i s i s emitted then the master t e r m i n a l or hardcopy d e v i c e i s used as d e f a u l t . A few examples a r e : DISPLAY a; (on master terminal} DISPLAY a, b, c; DISPLAY a -> c c l _ t e r m i n a l , b -> s t a t u t e ; HARDCOPY a, b -> h i _ r e s o l _ p l c t t e r ; (outputs b on s p e c i a l p l o t t e r } HARDCOPY a, b, c {shows a,b,c super-imposed, then advances paper} 71 3.5.4 D i s p l a y A t t r i b u t e s . Viewing and Image Transformations D i s p l a y e d g r a p h i c a l o b j e c t s may be m o d i f i e d by two d i s -play a t t r i b u t e s , HILIGBT and PEBSPECT1VE. H i g h l i g h t i n g of g r a p h i c a l c b j e c t s i s dependent on the output device; i n many cases i t i s achieved by b l i n k i n g . The a t t r i b u t e PERSPECTIVE has one parameter of type r e a l which d e f i n e s the c e n t r e of p r o j e c t i o n i n world c o o r d i n a t e s . The viewing a x i s i s automat-i c a l l y moved to the centre of the f r o n t plane of the view vo-lume. I f no v i e * volume i s s p e c i f i e d , the z=0 plane d e l i m i t e d by t h e x and y wcrld c o o r d i n a t e s applies.„ The parameter of PERSPECTIVE i s the d i s t a n c e along the z - a x i s from the f r o n t plane to the centre of p r o j e c t i o n . This i s i l l u s t r a t e d i n F i g u r e 9. , For example, the statement DISPLAY unit_cube PERSPECTIVE 1.5 ~> s t _ t u b e produces the output c f F i g u r e 10 (the c o o r d i n a t e axes are drawn only f o r r e f e r e n c e ) . Viewing and image t r a n s f o r m a t i o n s are geometric t r a n s f o r -mations which can be a p p l i e d o n l y f o r d i s p l a y purposes without changing the d e f i n i t i o n of a g r a p h i c a l v a r i a b l e . Viewing t r a n s f o r m a t i o n s i n v o l v e the d e f i n i t i o n of a view volume i n world c o o r d i n a t e s and the d e f i n i t i o n of a 3D-view-port i n NDC. The view volume dimensions determine which parts of a g r a p h i c a l o b j e c t a r e t o be c l i p p e d . I f the p r o j e c t i o n d e f a u l t s to p a r a l l e l , a p a r a l l e l e p i p e d p r o v i d e s the. view volume boundaries; f o r p e r s p e c t i v e p r o j e c t i o n a pyramid d e t e r -72 Figure 9 Figure JO sines these. , Vie* volumes and 3D-viewports are data types i n LIG/P. They have names and are declared as variables, e.g. 73 w e l l , v v c l 2 : VIEW VOLUME; v p o r t l , v p o r t 2 : VIEHPOBT Shear boundaries are d e f i n e d i n executable statements such as VIESVOLUME w e l l IS xmin..xmax, ymin.•ymax, zmin.,zmax; VIEBPOBT v p o r t l IS.xlow..xhigh, ylow..yhigh, zlow..zhigh In a d i s p l a y statement v v o l 1 and v p o r t l may be used i n con-j u n c t i o n with the operat o r s WITHIN and INTO t o d e f i n e the viewing t r a n s f o r m a t i o n , e.g. DISPLAY, p 1 ITH IN v v o l 1 ISTO v p o r t l -> c o l _ t e r m i n a l I f no view volume i s s p e c i f i e d , the d e f a u l t world c o o r d i n a t e range i n which a g r a p h i c a l v a r i a b l e was d e f i n e d i s taken. The viewport d e f a u l t s to NEC i n the x, y and z d i r e c t i o n s . Image t r a n s f o r m a t i o n s are the l a s t t r a n s f o r m a t i o n s ap-p l i e d f o r d i s p l a y i n g g r a p h i c a l o b j e c t s . ^Ihey determine how a 3D-viewport i s transformed before a p a r a l l e l p r o j e c t i o n onto the . .2=0. plane c f the BBC space i s performed.. Image t r a n s f o r -mations i n c l u d e s c a l i n g , r o t a t i o n and t r a n s l a t i o n ; the opera-t o r s SCL, BOT and AT are used, each followed by three operands which have values i n the NDC space. The d e f a u l t values are SCL 1.0 , 1. 0 , 1. 0 BOT 0.0 ,0 .0,0.0 AT 0 . 0,0.0,0.0 i f no image t r a n s f o r m a t i o n s apply. The parameters of the r o -t a t i o n operator aay be f o l l o w e d by the keyword DEG f o r de-grees. Image t r a n s f o r m a t i o n s are u s e f u l i f the same o b j e c t i s to be d i s p l a y e d with s u c c e s s i v e t r a n s f o r m a t i o n s a p p l i e d , f o r 74 example i n dynamic g r a p h i c s . These t r a n s f o r m a t i o n s can o f t e n he performed l o c a l l y by s o p h i s t i c a t e d g r a p h i c s s a t e l l i t e s without access t o the g l o b a l g r a p h i c s data base and with no support from the host computer. 3.5.5 -The- Erase Statement There are two v e r s i o n s c f the erase statement. To erase the e n t i r e screen o f an output d e v i c e , e i t h e r ERASE SCREEN or ERASE SCREEN -> d e v i c e may be used., The f i r s t statement e r a s e s the screen of the master output d e v i c e ; the second erases the s p e c i f i e d d e v i c e . To s e l e c t i v e l y erase i n s t a n c e s , the erase statement con-t a i n s a l i s t of g r a p h i c a l v a r i a b l e or i n s t a n c e names. The statement ERASE p, g, r where p, g and r are g r a p h i c a l v a r i a b l e s , e r a s e s a l l i n s t a n c e s of p, g and r on a l l d e v i c e s . I f named i n s t a n c e s are d e f i n e d as i n DISPLAY p HITBIN w e l l AS i l -> t e r m i n a l . 1, p PERSPECTIVE 10.0 INTO v p c r t l AS ±2, p SCL sx*dsx,sy*dsy,sz AS i 3 then the statement ERASE i 1 , i2 removes i n s t a n c e s i 1 and i2 of p from t h e , d e v i c e s where they 75 are displayed. 3.6 Graphical Input ; Graphical input i n LIG/P i s in the two-dimensional space only. The language provides the l o g i c a l devices keyboard, buttcn, stroke, lecator and valuator. Only synchronous input i s used, i . e . program execution i s suspended when an input statement i s found u n t i l an interrupt occurs. Input devices are given i n t e r n a l names in the same way as output devices are. A graphical input device i s declared as a variable cf type GBINPOT, e.g. VAB t a b l e t , j o y s t i c k : GBINPHT Declared input devices are associated with physical devices i n an executable DEVICE statement i n the same way as output de-vices are. . A set cf default input devices i s i n i t i a l i z e d and only those are enabled i f there are no further s p e c i f i c a t i o n s in the program. Depending on the hardware available these t y p i -c a l l y consist of a terminal keyboard, (programmable) function keys and the terminal cursor controlled by keys or thumb-wheels. For t h i s minimal set the valuator i s simulated by numeric input via the keyboard, and the buttons by available function keys and the keys of the keyboard. I f input i s to be expected from a s p e c i f i c device then the device name preceded by the symbol "<-" i s appended to an 76 input statement, provided t h a t t h i s i s meaningful f o r a spe-c i f i c d e v i c e . The LIG/P i n p u t statements a t e : (i) HEAD COESOB x,y,button SEAL CQ.BSOP x,y,button <- scree n T h i s statement d i s p l a y s the g r a p h i c s c u r s o r on " s c r e e n " and s a l t s f o r a bu t t c n i n t e r r u p t . The c o o r d i n a t e s x and y are world c o o r d i n a t e v a l u e s , and "button" i s an i n t e g e r value r e -turned by the button t h a t was h i t . , I t may be the ASCII or EBCDIC c h a r a c t e r cede i f buttons are simulated by the key-board. ( i i ) BEAD EDTTCR button The buttcn number or c h a r a c t e r code i s ret u r n e d i n "button". i i i i ) BEAD TEXT array,n BEAD TEXT array,n <- keyboard-device The c h a r a c t e r s typed at a keyboard device are packed i n t o " a r r a y " ; the number of c h a r a c t e r s read i s r e t u r n e d i n n. . The oaximum number o f c h a r a c t e r s t h a t can be b u f f e r e d i s i n s t a l l a -t i o n dependent; i f more than t h i s number of c h a r a c t e r s are typed they are i g n o r e d . EEAD VALUE X BEAD VALOE x <- v a l u a t o r - d e v i c e 77 A r e a l value x i s returned by the valuator. (v) BEAD STBCKE x_array,y_array,n BEAD ST8GKI x_array,y_array,h <-r stroke-device A stroke device, e.g. a d i g i t i z e r , reads n coordinate values i n t o r e a l arrays * ,x_array n and My_array". the maximum number cf coordinate pairs that can be read at a time i s i n s t a l l a t i o n dependent. 3.7 Control Statements The following '..-control state seats are provided: (i) CO BSC B ON CUESOB CH -> device These statements display the graphics cursor of an output device and wait f o r an interrupt. An i d e n t i f i c a t i o n statement can subsequently, teet f o r a pick. fi ! ) PAUSE t {seconds} PAUSE t HIS {minute sj Program execution i s suspended for the s p e c i f i e d length of time, then continues automatically. ( i i i ) EE II fiEIL -> device 7 8 To take advantage ot acoustic signals the bell-statement can he used. This corresponds to sending ASCII code 07 to an output device. (iv) The escape statements SEBD iarray,n -> output-device SEUB iaxx.ay.n <- input-device allow a programmer to make use of device c h a r a c t e r i s t i c s which are not provided for i n the higher l e v e l systems. An array of device codes i s sent d i r e c t l y to the device; the codes are stored i n an integer array and the f i r s t n bytes are to be read by the device. 3.8 Device Setting and Device Inguiry A number of input and output device c h a r a c t e r i s t i c s can be set by the application program. This i s done in device setting statements. The program can also ask f o r information about certain devices; t h i s i s done by device inquiry state-ments.. In the following sample statements, the device speci-f i c a t i o n ("-> device", or "<- device") i s optional. 79 3 . 8 . 1 Input Device S e t t i n g F o r i n p u t d e v i c e s , the f o l l o w i n g d e v i c e s e t t i n g s t a t e -ments are p r o v i d e d : <i) IOCECBT xlow.,xbigh, ylcw..yhigh <- d e v i c e T h i s i s analogous to s e t t i n g a viewport f o r output d e v i c e s . The r e c t a n g l e with two corner p o i n t s (xlow,ylow) and (xbigh,yhigh), where x and y are i n cm, i s taken as the range c f NDC Only i n t h i s r e g i o n of the device w i l l i n p u t data be read.. The d e f a u l t low and high values are the lower and upper bounds r e s p e c t i v e l y of the NDC space., ( i i ) VAIBANGE view..vhigh <- v a l u a t o r - d e v i c e T h i s statement s e t s the f u l l range of the v a l u a t o r d e v i c e t o values from vlow to vbigh. A l l a c t u a l values read are mapped i n t o t h i s range by the device d r i v e r . The d e f a u l t s f o r vlow and vhigh are 0 and 1 r e s p e c t i v e l y . ( i i i ) SHORE d,t••<- s t r o k e - d e v i c e A s t r o k e device i s set t c read v a l u e s every t seconds or a f t e r having t r a v e r s e d a d i s t a n c e d i n NDC. D e f a u l t values are 0 .01 seconds and 0 .01 i n NDC. 8 0 3.8.2 Oatpat Device S e t t i n g For output d e v i c e s , there are the f o l l o w i n g d e v i c e s e t -t i n g statements: (i) BACKGBOUHB COL c o l o u r -> device The same c o l o u r scheme as f o r modelling a t t r i b u t e s i s used. a device s c r e e n i s f i l l e d with the background c o l o u r when an EBASE SCEEES statement i s executed. By d e f a u l t the background c o l o u r ct a l l CBT d e v i c e s i s black. ( i i ) aSFECTBailO xa,ya -> device The values xa and ya must be i n the range 0..1 and one of them must be e x a c t l y 1. T h i s e s t a b l i s h e s an aspect r a t i o f o r the s p e c i f i e d d e v i c e ; t h i s f u n c t i o n i s d e s i r a b l e mainly f o r non-square screens and f o r cases where one range (x or y) of program-generated c o o r d i n a t e s i s known not to exceed a c e r t a i n value and one wants to use the f u l l screen t o d i s p l a y the generated g r a p h i c a l o b j e c t s . The device d r i v e r determines a "best f i t " f o r the r e c t a n g l e of r a t i o xa.ya f o r the s p e c i f i e d d e v i c e . 81 3.8.3 Input Device Inquiry Device inquiry statements interrogate the system about certa i n c h a r a c t e r i s t i c s of graphical i / c devices. , For input devices the following statements are available: (i) ASK PBECISIOH p device .The returned value i s the precision of the sp e c i f i e d locator or valuator device. The number cf bi t s of precision i s re-turned i n p. (i i ) ASK STATUS b <•- device The boolean variable b i s set to true or f a l s e , depending on whether the specified input device i s enabled or disabled. ( i i i ) aSK IOCEOBI xh,yh <- device The values of xfa and yh are device constants and are the f u l l h orizontal and v e r t i c a l range of the input device, measured in cm, that can be mapped onto the HDC range 0 . • 1 . 3.8.4 Output Device Inquiry Inguiring about output device c h a r a c t e r i s t i c s i s done with the following statements: (i) ASK BATIO x,y -> device The values cf x and y are device constants i n the range 0..1; 82 one of them i s exactly 1. .. They are used to determine an o p t i -mal aspect r a t i o setting f o r the s p e c i f i e d device. ( i i ) ASK PSIZE x,y -> device The values cf x and y are device constants and are the physi-c a l size of the s p e c i f i e d output surface, measured in cm. This i s useful f c r hardcopy output, for example, where graphi-c a l objects have tc be drawn to a cert a i n scale. ( i i i ) ASK 1 E S O L 0 T I O H x,y -> device The values of x and y are the number of addressable elements per cm cf the specified cut put device. The numbers are a mea-sure of resolution. (iy) ASK STATUS b -> device The boolean variable b i s set to true or f a l s e depending on whether the specified output device i s enabled or disabled. 3.9 The Archivaticn Statements Graphical variables can be saved on f i l e and read back at a l a t e r stage to f a c i l i t a t e continuity between int e r a c t i v e sessions. .  The statement SAVE <gr var l i s t > -> <system f i l e > e.g. SAVE p,g,r -> g r f i l e 8 3 creates a "constant" cf each graphical variable in the l i s t as i f the copy-assignment operator had been used and writes the encoded d e f i n i t i o n onto f i l e , i . e . appends the new information to the end of the f i l e . Graphical objects are retrieved with the statement EESTOBE <gr var l i s t ) <- <system f i l e > e.g. BESTOBE p,g,r,s,t <- g r f i l e The encoded variable d e f i n i t i o n s are read from the current position of the f i l e ( f i l e s should therefore be BESET when the program s t a r t s executing) and "constants" are assigned to the graphical variables i n the l i s t . If an end - o f - f i l e i s encoun-tered before a l l variables have been assigned a value, then the remaining ones are set to BLANK. f A f i l e for storing graphical objects mcst be declared l i k e any Pascal f i l e and have records of type GEEILE, 3.10 Translating and Running a 1IG/P Program The currently implemented version of LIG/P at UBC sup-ports a l l modelling and display functions except f o r 3D-clip-ping and sel e c t i v e erasing. Work i s under way already to com-plete the entire system. 84 a LIG/P source program i s preprocessed by the HIS command $808 ECH2:LIGP SCflBDS=source SPHIHT=listing PAB* CODB=pascal-SOUrce BGNHE1S=ECH:D0NNEES the f i l e p a s c a l - s o u r c e i s compiled by the command IBUH *PASCAL SCABDS=pascal-source SP0NCH=object-code A debugged program should eventually, be compiled with the com-p i l e r o p t i o n s PAB= $de-,op*$. To run the program, the LIG/P run-time l i b r a r y and Core System with d e v i c e d r i v e r s have to be loaded with the o b j e c t code: SB 0 N Ob j€ C t-CO de • EC B : L I G P. IIB. 0 * EC B 2 : COB E. 0+*P A SC AL LIB PaB=ex=40,cew-40 The run-time space a l l o c a t i o n i n the P a B - f i e l d may have to be i n c r e a s e d f o r e l a b o r a t e programs (see the manual UBC PascaL):. LIG/P programs can be run a t T e k t r o n i x 4027 c o l o u r t e r m i -n a l s , T e k t r o n i x 4010/4014 s t o r a g e tube t e r m i n a l s and i n t e r f a c e to the OEC P l o t r o u t i n e s . . 85 Chapter 4 lEPLEHEKTaTION OF TEE LIG/P S Y S T E H 4. 1 The LIG/P Preprocessor The p r e p r o c e s s o r which t r a n s l a t e s LIG/P programs i n t o pure P a s c a l source code i s w r i t t e n i n P a s c a l . I t was generated by a compiler w r i t i n g system (CHS) developed at the U n i v e r s i t y of Montreal [Lecar77 ]• Input to the CHS i s a d e f i -n i t i o n of the language i n BNF form. Each production i n the grammar may have a semantic a c t i o n a s s o c i a t e d with i t i n the form of a P a s c a l procedure. , Symbols i n the grammar may have a t t r i b u t e s a s s o c i a t e d with them which may be of any l e g a l Pascal type., The syntax a n a l y s i s of the generated compiler uses the bottcm-up approach f o r p a r s i n g the source code; i t l o c k s one symbol ahead and up to seven, symbols down i n the stack to decide whether a r u l e i n the grammar a p p l i e s t o make a r e d u c t i o n . , a m b i g u i t i e s which cannot be r e s o l v e d automati-c a l l y by the system are r e s o l v e d by e x p l i c i t i n t e r f e r e n c e i n the r e d u c t i o n process by the BHF programmer. a l i s t i n g of the IIG/P grammar as i n p u t to the CHS can be found i n appendix a. 86 The semantic actions have been omitted for r e a d a b i l i t y of the grammar. a LIG/P program needs the support of the LIG/P run-time l i b r a r y to execute. A set of subroutines builds and manipu-lat e s the graphics data base. the l i b r a r y was written in Pascal and i s based e n t i r e l y on dynamic storage a l l o c a t i o n provided by the Pascal N18 function. The environment for a l l subroutine systems for run-time support (the LIG/P l i b r a r y , the Core System and the three device drivers) i s created by dynamically a l l o c a t i n g a record for each subsystem and passing a pointer to the appropriate record into each subroutine. This method makes independent subroutine systems cut of each major part of the run-time l i -brary; the subsystems do not have to be recompiled with the application program tc create t h e i r proper environment for execution. a.2 .1 The Hodeliing Data Structure The data structure f o r each graphical variable consists of a h i e r a r c h i c a l part and a l i n e a r part. This r e f l e c t s the nature of graphical variables. Some are highly structured and access i s reguired at a l l times tc single e n t i t i e s of a variable's d e f i n i t i o n ; on the other hand, a variable may be 87 d e f i n e d as a sequence of output p r i m i t i v e s .with, no s t r u c t u r e a t a l l , and the only requirement i s t h a t the v a r i a b l e as a whole can be manipulated; an example i s a d i g i t i z e d map i n geographic a p p l i c a t i o n s of g r a p h i c s . a h i e r a r c h i c a l data s t r u c t u r e i s much mere complex than a l i n e a r one and - r e q u i r e s a l a r g e r amount of storage space and computation time. When readin g the source code, the system can d i s t i n g u i s h between the two forms of s t o r a g e r e q u i r e d , t r a n s l a t e a c c o r d i n g l y , and update the data base a p p r o p r i a t e l y when the program i s exe-cuted. The n o t i o n of a segment i s used to i n d i c a t e that p r i m i -t i v e e n t i t i e s are grouped to g e t h e r and some o p e r a t i o n s can be a p p l i e d c o l l e c t i v e l y t o a l l p r i m i t i v e s at once. In the LIG/P system r e f e r e n c e can be made to two kinds of segments: model-l i n g segments (or a b b r e v i a t e d "m-segments") and d i s p l a y seg-ments (or "d-segments? 1) • H-segments are used to s t o r e the u n s t r u c t u r e d p a r t s of a d e f i n e d o b j e c t , fhe h i e r a r c h i c a l part i s s t o r e d i n the modelling t r e e ( c r "m-tree"). When a g r a p h i c a l v a r i a b l e i s d e f i n e d , a " r o o t node" i s c r e a t e d which has the name c f the g r a p h i c a l v a r i a b l e . In the f o l l o w i n g diagrams t h i s i s r e p r e s e n t e d by a shaded block with a name as l a b e l , as shown i n . F i g u r e 11. The r i g h t hand p o i n t -er p o i n t s to the g r a p h i c a l v a r i a b l e * s m-segment; there i s only cne per g r a p h i c a l v a r i a b l e and i t c o n t a i n s the anonymous prim-i t i v e s and evaluated anonymous f u n c t i o n s a s s i g n e d to i t . The bottom p o i n t e r p o i n t s to the m-tree. P o i n t e r s l e a v i n g nodes 88 p q F i g u r e J J a t the bottom are r e f e r e d to as " s u p e r p o s i t i o n p o i n t e r s " be-cause i t i s here t h a t new s t r u c t u r e d p a r t s a r e added t o a v a r i a b l e . . The g r a p h i c a l v a r i a b l e p may t h e r e f o r e be d e f i n e d as p :- LINE FFOfl x 1 , y 1 , z 1 TO x 2 , y 2 , z 2 ' l a b e l 1 g <o> and i s r e p r e s e n t e d as shown i n F i g u r e 1 2 . The e n t r i e s of an p q F i g u r e J 2 B-segment are enccded output p r i m i t i v e s and output d e v i c e s e t -t i n g s . The a v a i l a b l e m-segment commands can be found i n the source code heading of the LIG/P run-time system.. Two s p e c i a l o p e r a t i o n s can apply to m-segments: they can be extended and they can be c o p i e d . New n-segment commands are added f o r c e r t a i n s u p e r p o s i t i o n s ; when anonymous output p r i m i t i v e s c r ancnyaces f u n c t i o n s are superimposed, the system encodes them and adds them to the rn-segment o f a g r a p h i c a l v a r i a b l e . Access to them as an independent u n i t i s l o s t ; they cannot te d e l e t e d frcm the v a r i a b l e nor can t h e i r a t t r i b u t e s 89 be changed. T h i s " c o n s t a n t " p a r t of a g r a p h i c a l v a r i a b l e i s only removed when the e n t i r e v a r i a b l e i s r e d e f i n e d . , The m-tree, as mentioned b e f o r e , i s the s t r u c t u r e d p a r t of a v a r i a b l e ' s d e f i n i t i o n . T h i s s t r u c t u r e d p a r t i s a h i g h l y dynasic data base and f u l l a c cess i s permitted t o e n t r i e s i n terms of d e l e t i o n of p a r t s , s u p e r p o s i t i o n and a t t r i b u t e changes. A node i n the t r e e c o n t a i n s a p o i n t e r to e i t h e r a named s u b p i c t u r e c f a p r i m i t i v e , c f a f u n c t i o n , or of another g r a p h i c a l v a r i a b l e . When a g r a p h i c a l v a r i a b l e i s d i s p l a y e d the t r e e i s t r a v e r s e d and d-segment output p r i m i t i v e s are generated; t r a n s f o r m a t i o n s and a t t r i b u t e s a p p l y i n g to a par-t i c u l a r s u b p i c t u r e are stacked and unstacked as the t r e e i s t r a v e r s e d , and are concatenated to generate the a p p r o p r i a t e f i n a l v a l u e s . As new s t r u c t u r e d p a r t s are added t o a v a r i -a b l e , new m-tree nodes are a l l o c a t e d and l i n k e d i n t o the t r e e . For e f f i c i e n c y they are always put i n t o the t r e e immediately a f t e r the r o o t node. The diagram o f F i g u r e 13 i l l u s t r a t e s t h i s . , I t w i l l become c l e a r i n the next s e c t i o n t h a t the system has t c keep t r a c k of which g r a p h i c a l v a r i a b l e s make s u b p i c t u r e r e f e r e n c e s to o t h e r s . T h i s i s r e q u i r e d to avoid unnecessary repeated t r e e t r a v e r s a l s ; t r e e t r a v e r s a l s are ex-pensive, alone f o r the many matrix m u l t i p l i c a t i o n s when conca-t e n a t i n g t r a n s f o r m a t i o n s . I t i s not known i n advance how many l i n k s t o a g r a p h i c a l v a r i a b l e w i l l be p o i n t i n g from other m-trees; t h e r e f o r e i t i s necessary to "thr e a d " the r e f e r e n c e s to a p a r t i c u l a r v a r i a b l e 90 s u b p i P q p L I 8 E <parameters> • + ' t e x t 1 +* PCLYGCK <parameters> AS subpl .•• g <m> Figure 13 i n a l i n k e d l i s t . The l i s t s t a r t s at the r o o t node of a g r a p h i c a l v a r i a b l e and l i n k s t o g e t h e r a l l t r e e nodes p o i n t i n g to i t . Io q u i c k l y r e t r i e v e the r o o t node t o which a p a r t i c u -l a r t r e e node belongs, a p o i n t e r from each t r e e node t o i t s r o o t node i s s e t . Depending on the implementation, s t o r a g e Bay be saved by l e t t i n g only the l a s t node c f a t r e e p o i n t hack t o the root node. For any g i v e n t r e e node one can then f e l l o w the s u p e r p o s i t i o n p o i n t e r s u n t i l the backward l i n k i s encountered. I n the i l l u s t r a t i o n of F i g u r e s 11 and 15, the " t h r e a d " f o r s u b p i c t u r e s of the g r a p h i c a l v a r i a b l e g i s drawn as a dashed l i n e ; n o t i c e t h a t the l i n k s shown are o n l y those r e l e -vant to q; the o t t e r s u b p i c t u r e r e f e r e n c e s a r e not shown but f o l l o w the same p a t t e r n . When the copy assignment op e r a t o r i s used, an o-segment i s c r e a t e d which c o n t a i n s a l l p a r t s of t r a v e r s e d s u b t r e e s i n a l i n e a r i z e d form. I t i s e v i d e n t t h a t t h i s i s g e n e r a l l y expensive i n terms of time and space.. 91 P r q p 2- q <a1> r <B2> F i g u r e JQ s p r q s :- q <m3> +* r <m4> F i g u r e J 5 Examples a r e : p := g <m> r <a> Trees of q and r are t r a v e r s e d and the output p r i m i t i v e s s t o r e d i n the a-segaent c f p. For the statement p := p g <m> the s u b t r e e s o f p and g are t r a v e r s e d and output p r i m i t i v e s s t o r e d i n the m-segnent cf p. The subtree o f p i s then de-92 s t r o y e d . Ho d e l e t i o n o p e r a t i o n i s p o s s i b l e i n a copy assignment statement, and no d e l e t i o n of s u b p i c t u r e s i s p o s s i b l e once a g r a p h i c a l v a r i a b l e i s d e f i n e d i n t h i s manner. 4.2.2 The D i s p l a y Data S t r u c t u r e F o r the e x e c u t i o n of i t s d i s p l a y f u n c t i o n s , the LIG/P system r e l i e s on the c o r e System which i s proposed as the Computer G r a p h i c s Standard {GSPC79 ]. The Core System p r o v i d e s a s i n g l e - l e v e l s t r u c t u r e of d i s p l a y statements which c o n s i s t of grouped output p r i m i t i v e s . The LIG/P run-time l i b r a r y maps the h i e r a r c h i c a l s t r u c t u r e c f g r a p h i c a l v a r i a b l e s onto s i n g l e -i l e v e i Core segments (or "c-segments"). D i s p l a y i n g and e r a s i n g of g r a p h i c a l o b j e c t s causes a number c f a c t i o n s i n the Core System. For each i n s t a n c e t h a t i s d i s p l a y e d a c-segment i s c r e a t e d . The Core System performs the c l i p p i n g and window-to-viewport t r a n s f o r m a t i o n of c o o r d i -nate data; f o r each i n s t a n c e the LIG/P system s e l e c t s the r e -guested d e v i c e , s e t s the viewing t r a n s f o r m a t i o n s and i n i t i a t e s the c r e a t i o n c f a new c-segment; i t then t r a v e r s e s the g r a p h i -c a l v a r i a b l e ^ data s t r u c t u r e to generate Core System output p r i m i t i v e s . , The m^segment i s scanned through g u i c k l y because i t has a very simple s t r u c t u r e ; then the m-tree i s t r a v e r s e d . The t r e e t r a v e r s a l r o u t i n e i s r e c u r s i v e and "brother nodes" and t h e i r subtrees are e v a l u a t e d before "son nodes" and t h e i r 93 subtrees a r e , , To a v o i d repeated unneccessary c r e a t i o n and d e l e t i o n o f c-segments the f c H e w i n g scheme i s used: any e x i s t i n g c-segment can be v i s i b l e o r i n v i s i b l e , With r e s p e c t to a LIG/P model, i t can be outdated or not. Since the Core System p r o v i d e s image t r a n s f o r m a t i o n s and h i g h l i g h t -i n g as dynamic a t t r i b u t e s f o r complete segments, LIG/P does not have t o d e s t r o y a c-segment as soon as i t i s erased; r a t h -e r , the c-segment i s kept because i t i s assumed t h a t t h e r e i s a good chance t h a t i t w i l l be r e d i s p l a y e d with new image t r a n s f e r m a t i o n s or h i g h l i g h t i n g . Consider t h e f o l l o w i n g se-guence of LIG/P statements: {1} DISPLAY p <imtrans1> -> tek27; {2} DISPLAY p <imtrans2> -> tek27; £3} E£ASI p; (read new parameters} £4} DISPLAY p <imtrans3> -> tek27 Statements 1 and 2 cause the c r e a t i o n of two c-segments which are immediately v i s i b l e . Statement 3 makes these c-segments i n v i s i b l e . Statement 4 i s executed and p*s i n s t a n c e c h a i n i s searched t o see i f there i s any c-segment which can be used, i . e . which r e f e r s t o the s p e c i f i e d d e v i c e and i s c u r r e n t l y i n v i s i b l e , and i s not outdated. In the above example, the segment i s found f o r which a l l these c o n d i t i o n s are t r u e , and cne o f the two segments i s made v i s i b l e again a f t e r the new image t r a n s f o r m a t i o n s have been a p p l i e d , i 94 In two cases t h i s scheme w i l l not work p r o p e r l y : The f i r s t i s the case where viewing t r a n s f o r m a t i o n s have changed and d i f f e r e n t p arts of an o b j e c t are being c l i p p e d . T h e r e f o r e another c o n d i t i o n t h a t has to be checked i s that the c u r r e n t viewing t r a n s f o r m a t i o n s must be the same as the previous ones. Also a p e r s p e c t i v e p r o j e c t i o n must not have changed. I f t h i s i s not the case, a new c-segment l u s t b e ; c r e a t e d . , The second c o n d i t i o n i s t h a t the d e f i n i t i o n of a v a r i a b l e has not changed between the l a s t DISPLAY statement and the c u r r e n t DISPLAY statement. The d e f i n i t i o n of a g r a p h i c a l v a r i a b l e changes as scon as p a r t s are added, or s u b p i c t u r e a t t r i b u t e s or subpic-ture d e f i n i t i o n s are changed. For example: p :- g <m1>; DISPLAY p; g :- g — gpart; FfiASE p; DISPLAY p As soon as g i s changed, a l l v a r i a b l e s using g as a s u b p i c t u r e are f l a g g e d . T h i s i s done very g u i c k i y by scanning through g*s s u b p i c t u r e " t h r e a d " . Therefore p gets f l a g g e d . Then p's i n s t a n c e c h a i n i s t r a v e r s e d and a l l nodes v i s i t e d are f l a g g e d as outdated. The c-segments corresponding to the i n s t a n c e .nodes t h a t are both outdated and i n v i s i b l e are d e s t r o y e d . Other c-segments which a t t h i s p o i n t are s t i l l v i s i b l e are destroyed as scon as they are made i n v i s i b l e . An example: 95 p :- p *+ g <m1>; DISPLAY p <imtransl> AS p _ i n s -> tek27; DISPLAY p -> tek25 Figure 16 shews the c o r r e s p o n d i n g data case e n t r i e s f o r these t e k 2 5 t e k 2 7 p j n s p q F i g u r e J6 statements. The r o o t nodes c f d e v i c e - t r e e s i n the diagram are shaded s i m i l a r l y to those o f m-trees. The a l l o c a t i o n of node (2) and (3) causes the c r e a t i o n c f , say, c-segments number 102 and 103. , Both nodes (2) and (3) are f l a g g e d " v i s i b l e " and "up-to-date". The statement g .- q — gpart causes the f o l l o w i n g changes: node (1) p o i n t s t o g r a p h i c a l v a r i a b l e p as i t s r c c t ncde which has now been modified be-cause g has been modified. F o l l o w i n g the l i n k from p t o node {2) to node (3), these two nodes are now f l a g g e d " v i s i b l e " and "outdated". The statement IBASE p _ i u s f l a g s (2) " i n v i s i b l e " and "outdated" and t h e r e f o r e d e s t r o y s c-segment 102. ,. (3) i s s t i l l " v i s i b l e " and "outdated". . The statement 96 DISPLAY, p -> tek27 causes a new c-segment t c be c r e a t e d , say c-segment number 104. ; A new node i n the d-tree o f d e v i c e tek27, node (4), i s a l l o c a t e d and f l a g g e d "updated" and " v i s i b l e " . The c u r r e n t data base i s shewn i n F i g u r e 17. tek25 . tek27 I V. I 7 (3) * (1) •» \ Figure J 7 I f the next statements are BEASF p; DISPLAY p <iatrans4> -> tek27 then c-segment 103 i s des t r o y e d and node (3) removed, c-seg-sent 104 i s made i n v i s i b l e and then v i s i b l e again with new image t r a n s f o r m a t i o n s a p p l i e d . By now i t should be c l e a r why such a complex s t r u c t u r e o f t r e e s and l i n k e d l i s t s i s used i n LIG/P. The method i s not s p a c e - e f f i c i e n t but i t i s expected t h a t a good d e a l of execu-t i o n t i Be i s saved by not u s i n g a b r u t e - f o r c e method with a s t r a i g h t f o r w a r d scheme of c r e a t i n g and d e s t r o y i n g segments, and by a v o i d i n g t r a v e r s a l o f the model-structure as o f t e n as p o s s i b l e . 97 Chapter 5 CGBKEBTS OH THE COBE SSSTEH One of the g o als c f the i n v e s t i g a t i o n s f o r t h i s t h e s i s was the u s e f u l n e s s of the Core System f o r the automatic g e n e r a t i o n of c a l l s to i t s f u n c t i o n s . When the LIG/P data s t r u c t u r e was designed the o r i g i n a l i n t e n t was to make Core System segments p a r t o f the data base to a v o i d d u p l i c a t i o n c f encoding and decoding of output p r i m i -t i v e s , and to save storage space. I t was d i s c o v e r e d that t h i s was not p o s s i b l e ; LIG/P had t c be given i t s own m-segments which at seme p c i n t would be t r a n s l a t e d i n t o Core System seg-ments f o r d i s p l a y purposes., The reason i s t h a t Core segments cannot be co p i e d and cannot be extended. Although i t i s claimed t h a t a h i e r a r c h i -c a l s t r u c t u r e can be b u i l t on top of the s i n g l e - l e v e l Core segments [ H i c h 7 8 ] , t h i s i s not e a s i l y done and i s i n f a c t very time-consuming and ceguires a l a r g e amount of overhead. LIG/P supports a m u l t i - l e v e l s t r u c t u r e of g r a p h i c a l v a r i -ables and s u b p i c t u r e s : a p a r t i c u l a r v a r i a b l e can serve as a s u b p i c t u r e to many ether v a r i a b l e s . A problem a r i s e s because each s u b p i c t u r e may have d i f f e r e n t modelling t r a n s f o r m a t i o n s . 98 The Core System fie pert [GSPC79] s p e c i f i e s that image transfor-mations may be applied to a segment only once i t has been de-fined; the LIG/P system could imitate modelling transforma-tions by applying these image transformations while displaying a subpicture. However, image transformations i n the Core System are immediately applied to a l l displayed instances of a segment which would r e t r o a c t i v e l y change a l l images of the par t i c u l a r segment. an example i l l u s t r a t e s t h i s point: Let p and g share a Core segment seg(r) which defines r: p :- r <m1>; g :- r <m2>; DISPL&Y r ; (generates the f i r s t image of seg (r)} ..DISPLAY p; (changes image transformations of seg (r) tc <m1>} DISPLAY g; (changes image transformations of seg (r) to <m2>} 8hen the l a s t statement i s executed, r and p are no longer displayed the way they should be. This leads to the conclu-sion that for the representation of a hierarchy, segments cannot be shared; ore needs a copy for each subpicture. The Core System does not allow the generation of i d e n t i c a l copies of segments with a simple command, however.,, a second major drawback of Core segments;is the r e s t r i c -tion that they may not be extended. I f a graphical object i s composed of many output primitives which do not have to be accessed l a t e r (e.g.,for deletion) but a l l of which are not 99 known i n advance because they are added to a v a r i a b l e d u r i n g an i n t e r a c t i v e s e s s i o n , then s u r e l y an extend-segraent i n s t r u c -t i o n would be a reasonable answer t o avoid a l a r g e amount o f overhead. k t h i r d problem a r i s e s due to the f a c t that there i s no a c cess to p r i m i t i v e a t t r i b u t e s w i t h i n a segment. With r e s p e c t to LIG/P t h i s r u l e s out Core segments as p a r t of a h i e r a r c h i -c a l model s t r u c t u r e . , The only advantages t h a t Core segments o f f e r , compared to a simple s e t of unsegmented output p r i m i t i v e s , i s (a) the de-l e t i o n of e n t i r e segments and (b) the a p p l i c a t i o n of dynamic segment a t t r i b u t e s t c e n t i r e segments. The Core segment was not designed t o be part of a g r a p h i c a l data base; g r a p h i c a l data s t r u c t u r e s must be maintained by the a p p l i c a t i o n program i n the form of i t s own data and procedure s t r u c t u r e . k good example t c prove t h i s i s given by Bergeron e t a l . [Berge78] who a n t i c i p a t e freguent c r e a t i o n and, d e l e t i o n of segments, ftichener e t a l . [Mich78j suggest the use of temporary work segments t o achieve the e f f e c t c f copying and extending seg-ments. G r a p h i c s packages such as GIHO-F c r the German Ker n e l System (GKS) provide segnents with more permanent c h a r a c t e r i s -t i c s and may p o s s i b l y be more s u i t a b l e as a subsystem f o r IIG/P. , 100 Chapter 6 CONCLUSION Due t o time c o n s t r a i n t s the f u l l LIG/P system c o u l d not he implemented up to t h i s p o i n t ; the l a r g e s t p a r t of i f , how-ever, has been implemented and t e s t e d and work i s a l r e a d y con-t i n n i n g t c complete the p r o j e c t . LIG/P i s a major improvement over p r e v i o u s v e r s i o n s of LIG i n terms c f programming convenience, p o r t a b i l i t y and g r a p h i c s f e a t u r e s i t p r o v i d e s . I t i s a n t i c i p a t e d t h a t f u r t h e r experiments w i l l d i s c o v e r where more e f f e c t i v e use of the Core System can be made by using i t s f u l l c a p a b i l i t i e s once they are a v a i l a b l e . , At seme stage when the f l e x i b i l i t y of the Compiler B r i t i n g System i s net as e s s e n t i a l any more, i t i s recommended t h a t a preprocessor be w r i t t e n from s c r a t c h ; the c u r r e n t v e r s i o n i s r a t h e r expensive to use. I t i s hoped that LIG/P w i l l i n the near f u t u r e be used as a t e a c h i n g t o o l f o r the undergraduate gr a p h i c s course i n t h i s u n i v e r s i t y . As with LIG, the feedback from users w i l l provide a very v a l u a b l e b a s i s f o r the e v a l u a t i o n of and improvements to the system. 101 BIBLIOGRAPHY [Alex75] Alexander .H.G., Wortman D.B., " S t a t i c and Dynamic C h a r a c t e r i s t i c s c f XPL Programs.'? Computer. 8, 1975, pp. 41-46. y £Bar63] Barron D.f. et a l . , "The Bain Features of CPL,'? Computer J o u r n a l . 6, 1963. £Berge76 ] Eergercn B.D., " P i c t u r e P r i m i t i v e s i n Device Independent Graphics Systems. 1? Computer Graphics, Spring 1976, pp. 57-60. £Berge78] Bergeron B.D., Bono P.B., Foley J.D-, "Programming Using the Core System." ACH Computing Surveys. 10, Ho. 4, December 1978. £Berk77J Berk T.S., " C o o r d i n a t e - f r e e Computer G r a p h i c s . " Computers & Graphics. 2, 1977, pp.. 105-109. £Bour7 7 3 Bourne S.B., 2CODJ, J Simple Machine... Cambridge U n i v e r s i t y Computer La b o r a t o r y , 1977. £Brown77] Brown P.J., "Giant Leaps i n Bic.ro F i e l d s . " Computing. October 1977. £Call75] C a l l a n J.F., "The A r c h i t e c t u r e of The P i c t u r e System. 1? I F E I Computer A r c h i t e c t u r e Symposium. 1975, pp. 13-16. £CS78] Denning P.J. (ed.), Graphics Standards., ACH Computing Surveys ( S p e c i a l I s s u e ) , 10, No. 4, December . 1978. , £Cull79 3 Cullmann N., "Software D i s t r i b u t i o n i n S a t e l l i t e G r a p h i c s Systems." Anqewandte i n f o r m a t i k . 21, 1976, pp. 63-70. £ Dan77 3 D a n i e l s T. H. et a l . , "Easy-to-Dse I n t e r f a c e Language C c n t r c l s HP-IB Plotter.*? Hewlett Packard  J o u r n a l . 29, September 1977, pp. 5-9. 102 £Den75} Desert E. e t a l . , "G8AEHEX68 - G r a p h i c a l Language F e a t u r e s i n A l g o l 68..*» Computers S G r a p h i c s . 1, 1975, pp. 195-202., £D€«77] Dewar H.E.K. , McCann A.B., "MACRO SPITBOL--a SN0B0I4 C o m p i l e r . M .-'SeftMare-7-Practice-:-.:andr; Experience. 7, 1977, pp. 95-113., £Els79] Elsw o r t h E.F., "C o m p i l a t i o n v i a an Intermediate Language." Computer J o u r n a l . 22. So. . 3, 1979. £Ewal78] Ewald R.fl., F r y e r fi., " F i n a l Beport of the GSPC S t a t e - o f - t h e - a r t subcommittee." Computer G r a p h i c s . 12, June 1S78, p p . 1 4 - 3 4 . £FG176 ] F o l e y J.D., " P i c t u r e Saming and M o d i f i c a t i o n : an Overview. 1? , Computer G r a p h i c s . 10, S p r i n g 1976, pp. 49-53. . £Fcl79 3 F o l e y J.D., "A Standard Computer Gra p h i c s Subroutine Package.'! Computers & S t u c t u r e s , 10, 1979, pp. 141-147. £Fox78 ] Fox M.C., Machine A r c h i t e c t u r e and the Programming Language BCPL. H.Sc. T h e s i s , Dept. of Computer S c i e n c e , U n i v e r s i t y of B r i t i s h Columbia, 1978. £Fra68] Frank A.J., "E-LINE, B e l l L i n e Drawing Language.? A FTPS Ccnf . P r e c . 33. 1968. pp. 179-191. £Gil78j G i l c i U.K., i n t e r a c t i v e Computer G r a p h i c s . Englewood C l i f f s : P r e n t i c e - H a l l Inc., 1 9 7 8 . £GSPC79 3 Hellman B., Herzog B. ( e d s . ) , " S t a t u s Beport of the Gra p h i c Standards Planning Committee." Computer G r a p h i c s . 13, 86. 3, August 1979. £ Jon78 J Jones B.. I n t e g r a t e d Graphics i n LISP. T e c h n i c a l Manual TM-23, Department of Computer S c i e n c e , U n i v e r s i t y o f E r i t i s h Columbia, September 1978., £Kerr75 3 Kerr H.D., "A Microprogrammed Processor f o r I n t e r a c t i v e Computer G r a p h i c s . " IEEE P r o c . 2nd Annual Symposiun on Ccmputer A r c h i t e c t u r e . 1 9 7 5 . pp. 28-33. £Knu713 Knuth D.E., "An E m p i r i c a l Study of FORTRAN Programs." S o f t w a r e - — P r a c t i c e and E x p e r i e n c e . 1, 1971, pp. 105-133. £Kuls683 Kulsrud H.E., "A General Purpose Graphic Language." Communications ACM. 11, No. 4, A p r i l 1968, pp. 247-254. £Lecar77] Lecarme O., Bochmann G.V., A Compiler. W r i t i n g 103 System Users Manual. Dept. of Computer S c i e n c e , U n i v e r s i t y of Montreal, December 1S74, £McKeem70 ] McKeeman S.M., Horning J«J«, Wortman D.B., a Compiler Generator. Englewood C l i f f s N.J.: P r e n t i c e -H a l l , 1S70. [Mich78 ] Michener B.C., F o l e y J.C., "Some Major I s s u e s i n the Design c f the Core Graphics System." aCM Computing  Surveys, 10, No. 4, December 1978. £Mill68 3 M i l l e r H.F. , Shaw a.C., " a P i c t u r e C a l c u l u s . «» In: Emerging •Co-ncept-s; i n Computer G r a p h i c s . S e c r e s t D. e t a l . (eds.),New Y o r k : H « a . : Benjamin ihc.,i; 1 1 9 6 8 . £ Boul76 3 floulton S.D., Corman P.J,, "Bemote Programmability o f G r a p h i c I n t e r a c t i o n s i n a H o s t / S a t e l l i t e C o n f i g u r a t i o n . " Computer Graphics. 10, No. 2, Summer 1976, pp. 204-211. £Newm7 13 Newman M.fl., " D i s p l a y Procedures.'? Communications ACH, 14 ,October 1971, pp. 651-660. £Newm7 8 3 Newman ».H., van Dam a . , ''Becent E f f o r t s towards G r a p h i c s S t a n d a r d i z a t i o n . " aCM Computing Surveys. 10, No. 4, December 1978., £Hewm7S3 Newman 8.M., S p r o u l l E.F., P r i n c i p l e s of I n t e r a c t i v e Computer Graphics. New York: McGraw-Hill Book Company, 1979. , £Ncri74 3 N o r i K.V. et a l . , "Ibe Pascal-P C o m p i l e r -Implementation Notes,? B e r i c h t e des.. i n s t i t u t s f u e r  I n f o r m a t i k . 10, E i d g e n o e s s i s c h e Technische Hochschule, Z u e r i c h , 1974. £Peck7 5] Peck J,E.L. e t a l . , Code Compaction f o r Hiniccmputers with INfCODE and HINICODE. . T e c h n i c a l Bepcrt 75-02, Department of Computer Scie n c e , U n i v e r s i t y of B r i t i s h Columbia, 1975. £ Posd7 3 3 Posdamer J.L., .Eiesenfeld B.f., ( ?'The a p p l i c a t i o n of a PL i n Graphics Computation.,'? Proc. of -APL Congress 73, amsterdam: N c r t h - H c l l a n d P r e s s , 1973. £Eosd77 3 Posdamer J.L., "Some C r i t e r i a f o r the E v a l u a t i o n of G r a p h i c s Implementation Languages.'? Computers 5 G r a p h i c s . 2, 1S77, pp. 91-95. £ Bich71 3 B i c h a r d s H., "The P o r t a b i l i t y of the BCPL Compiler." S o f t w a r e — P r a c t i c e and Experience, 1, 1971, pp. 135-146, 104 £8ich76] Bichards M. , "JUMBO—A Demonstration Program to I l l u s t r a t e the Use of BCPL i n a leal-Time Graphics app l i c a t i o n Requiring Scaled Arithmetic," Software— Practice an d E x per ft- eric e. 6, 1976, pp. 255-259. [Bies78] Biesenfeld B.F., "Current Trends in Computer Graphics. ** Computers 6 Graphics. 3, 1978, pp. 115-122. £Boes6 8 3 Boesset J . et a l . , ICES STEPPL I Student Manual. Department of C i v i l Engineering MIT, Cambridge Mass., 1968. [Bovn6 6 ] Bovner P.P.. LEaP Users Manual. Lincoln Laboratory Technical Memorandum 23L-0009, December 1968. £Bovn69] Bovner P.p., Feldman J.A., "The LEAP Language and Data Structure.« Proc. ,1968 If IP Congress. Ho r r e l l A.J.H. , (ed.), Amsterdam: North-Holland Pub. Co., 1969. £Salv75 3 Salvador! A. et a l . , " S t a t i c P r o f i l e of COBOL Programs." ACM Sigplan Notices, 10, 1975, pp. 20-33. £Schr76 3 Schrack G., "Design, Implementation and Experience with a High-level Graphics Language f o r Interactive Ccmputer-Aided Design Purposes." Computer Graphics. 10, 1 976, pp. , 10-17. .. £Schr78a ] Schrack G.F., LIG Osers Manual., Departments of E l e c t r i c a l Engineering and Computer Science, University of E r i t i s h Columbia, 1978. £Schr78b3 Schrack Guenther, Grafische Datenverarbeitung. Mannheim: Bibliographisches I n s t i t u t , 1978. £Sharp703 Sharpe 8.F., Jacob N.L., Jfi Introduction to Computer- Programming Osinq the BASIC Language. New York: Free Press, 1970. £Staud75 3 Staudhammer J., Eastman J.F., England J.H.,. "A Fast Display Oriented Processor." IEEE Computer Architecture Symposium. 1975, pp. 17-22. £Stil77 3 Stillman N.J., Berra P.B,, "A Comparison between Hardware and Software associative Memories i n the Context of Computer Graphics.'! Communications a C M . 20, 1977, pp. 139-150. „ £Swi71J Swinehart D.C., Sproull B.F.. SAIL Manual. , SAILON No. . 57.2, A r t i f i c i a l Intelligence Project, Stanford University, 1971. 105 [Suta6 3 ] Sutherland I.E., "SKETCHPAD: A Man-Machine G r a p h i c a l Communication System.? Prec. „ AFIPS Conference. 23, 1963, pp. , 329-346. [Symap] (anonymous), SXIIAP Osers Reference Manual. L a b o r a t o r y f o r Computer Graphics and S p a t i a l A n a l y s i s , Harvard U n i v e r s i t y , Cambridge Mass, £ Tan78 ] lanenbaum A.S., " I m p l i c a t i o n s of S t r u c t u r e d Programming f o r Machine A r c h i t e c t u r e . " Communications ACJJ, 2 1, No. 3, March 1978, pp. 237-246. LTaub63 3 Saub , (ed.), C o l l e c t e d Works of John von Neumann. 5, London: Macmillan Press, 1963, pp. 34-79. £Thal7S ] Thalmann N., Thalmann D., "A S t r u c t u r e d Approach t o Computer Graphics.'? Proc. 6th Man-Computer Communications Conf.. Ottawa. 1979. £Tur75 3 T u r r i l C.N., Mallgren ; •;;M.^|L4;:,r:j-v;-wXfia-^Bxperiences- i n Implementing an Experimental I n t e r a c t i v e Graphics Programming System." Computers fi G r a p h i c s , 1, 1975, pp. 55-63. £ vanDam72 3 van Dai A., "Microprogramming f o r Computer Graphics.'! ACH Sigmicro Newsletter. 3, No. 1, A p r i l 1972, pp. 3-7. £Ball76 3 Wallace V.L. # "The Semantics of Graphic Input D e v i c e s , ? Computer G r a p h i c s . 10, No. , 1, Spring 1976, pp. 61-65. £811172 3 W i l l i a m s E.A., "A General-Purpose G r a p h i c a l Language,'.' Proc. I EXP Working Conf. on Graphic Languages. P. Nake and A, Rosenfeld ( e d s . ) , Amsterdam: North-Holland, 1972. £Bprt7 2 3 Bortman D.B., A Study c f Language D i r e c t e d Computer Design. , CSBG-20, U n i v e r s i t y of Toronto, 1972. : 106 appendix a THE LIG/P GB&M8&B The grammar i n BSE form shown on the f o l l o w i n g pages i s the i n p u t to the C c a p i l e r W r i t i n g System used t c implement the p r e p r o c e s s o r . , The semantic a c t i o n s have been removed i n t h i s l i s t i n g f o r most p r o d u c t i o n s to i n c r e a s e the r e a d a b i l i t y of the grammar. The a t t r i b u t e s a s s o c i a t e d with many symbols i n the grammar appear as i n the o r i g i n a l v e r s i o n ; t h e i r types are d e f i n e d i n the a u x i l i a r y f i l e GLOBAOX which i s not l i s t e d i n t h i s r e p o r t . 107 tIGP (.H1.11I.IGNE, »»GtlIS,C»BtE?,OP?IOSS, LONUCA3T KS- 25 5 j.; . IEXIGEN ( BLANCSGEQII PES,OPT IONS, Oi>ER AT Ell SS , P REDSKIN IS, LETT BE S = 'a bciief qhi jklmnopqcstuvv>cyz_', OBLC0.1»BMT»< (| >,LONUC:!AIME-M0, !lTILrOENT=2 3, LONGl'DENT=30,RESERVF.S> ; SYNTGEN (AilBIGUI T ES, INSOLUELES, LI MITES, REGIES, TERHIKAIIX,NO!)TEEI.irHAUX„ LONG?ILE=50) ; PROGGEN (ANALYSES,PHRASES) S PSOGRAH INITIALISER: <EG» H0R> = <TYPEDECL> <LIG> <VASDSCL> <PBOCDECL> <LIG ST.1I LIST>= <LIGSTHT> <A7 RABRO»> <OUT?T STBT> <DISPLAY> <HASDCOPY> <0'JIP TERK LIST <PG.1 HD8> <LIG STMT LIST> ';•'.'$ SYKBARRBTf 1 ]:=</*; " /) : SYHBREPRI SE[ 1 ] := (/<PGH HDR>/) ; C0Bna_lit. l i f . e r a l l y [ 1 ] := ',*; c o m i a _ l i t . l e a := 1; l i g e r r s := 0; reset_attr; r e s e t _ t r a n s f ; rewrite(CODE); pascal b u f f e r := NIL; $ <TY?EDECL> <VARDSCL> <PROCDECL> $ <LIG> "TYPES" ' ; " J • LIG* S •LIG" "VA8S" • ; ' $ "LIG" "PROCEDURES" •;».$ <LIGSTHT> $ <LIG STRT LIST> •;• <LIGST.iT> $ "INITIALIZE" 'I.IG" $ <ASSIGN stni> $ •WORLDCOORD" CSUDRNG TSIPL>(c«r t r i p l ) 3 •VIESVOLtJKE" <VV0L ID>(cur_i:l) MS' <S0BRNG TRIPL> ( c u r _ t r i n l ) $ "VIEWPORT- <7P ID>(cur_id) -«IS" <S!JBaNG TBIPL>(cur_tripl) « 'DEVICE' <DEV ID>(cur_id) "IS" <VAR> ( c u r _ v a r , f n c a l l ) J <OBTPT S?i<!T> $ "ERASE" "SCRKEN" $ •ERASE" •SCREEN" <A7 RABROK> <DEV ID>(CUr_id) $ •ERASE" <ERVAR LIST> $ •CCRSOB" "ON" $ •CDRSOH" 'ON' <A7 RARROW> <VAS>(cur.var,fnca11) $ <INPT STMT> $ <IDN ST.1T> $ <CASE STMT> $ •->• $ <DISPLAY> <OriTP TERM LIST> $ <HABDCOPY> <OUTP TERH LIST> $ •DISPLAY" S . . . •HARDCOPY" $ • <GB T E RM > $ <OUTP TER3 LIST> "," <GR TER3> $ <ERVAR> (er..var) $ - <ERVAB LIST> '," <ERVAR> (sr_var) $ <ERVAB> (er_var: l i t _ r e c ) = <VAR>(cur_var,fncall) S O.SGN VAR> <GR ASSIGN OP> <GR EXPRS> $ <VAR>(cur var.fn) * • . $ • : - ' $ • <GR TERM> $ <GR EXPRS> <GR ADDOP> <GB TER>1> $ <GR PP.IHAFY) $ ' <GR PRIMARY) <HODIF LIST> t . . <VAB> (cur_var,fncall) $ = <SiBING> (rlescr) £ - <GR PRIMTIVE> (cur_prim) $ <GK PHIHITIVE>(cur_prim:ligpriraitive) = "BLANK" $ = "LINE' $ - •POLYGON' i «*•• $ $ MODIFICATION) $• = <«ODir LIST) MODIFICATION) * <!iODIFICLTICN) = <RO01 KSi»ORD> (etir_a11r) <.10D PAS> (cur_par) * = <KOD? KEYWORD) (cu r_t r ausf) <MODF A R TRI PL) (cu r _ t r i pi) "DEC $ '"= <J10D2 KE Yt'ORD) (cut~transf) <i10DPAB TRIPL)<cur_triDl) $ * "UILIGHT" $ = "FILL" '5 = "A£" <*aa>(car_var, fneall) $ <HOC1 KEY»ORD>(cur_attr:ligattr7 <E.RVAE LIST> <?.SSIGN STHT) <ASGN VAS> <GB ASSIGN OF> <GR EXPRS> <GB TERH> <GR PBIBARI> <GB ADDOP> <KODIP LIST> • COL" •L1GHTN" • INTEN• •LWXDTH' •LTYPE" •C5IZF.' 'CSPACE' •PATTE 3N' 'PERSPECTIVE" • BITHIM" 1IKTO' •->" • <A8 ilOD P AB) (p2) <IBP? STHT> <INPT DEVICE) <INPTP&8BS> <ION STHT) <INPT ID> •CINPT ID> CISPT ID> $ <BOD2 KBl»OBa>(cur transf:ligtranst) » •AT' $ • 'SOT' S • "SCL* $ « 'FBOH' $ * «TO» S « •DELTA• t <B0DPA3 T B I P L ) ( c u r _ t r i p l : l i t _ r e c ) <= <A8 NOD P A S ) ( p l ) <A8 HOD PAH> (cur_par:lit_rec) = <NOD PAR) (par) S <BOD PAR>(cur_par:lit_cec) = <A2 A3ITH E X F B S ) (cur_arith) S <»2 ABITB. EXPBS>(cur_atith:lit_re=) = <AEITH EXPRS)(arith) $ •8SAD' <IKPT D E V I C E ) CINPTPAR.IS) $ •COBSOR' i •BUTTON' $ •TEXT' $ •VALUE* S •ST50KE' i <IN?T ID> t <IH?T ID> •, • <INPT ID> ' ,' <IKPTPABMS> •<-• <7AB> t <SIHPLB IDN STNT) $ = <COBPOS IDN S T S T ) $ <SIBPLE IDN STHT) = <IDN OP> 'THEN' <IDNSTf1T GBOiJP) S <COHPOS IDN ST!IT> = <A5 S l n P L E IDS STJ!T> <ELSE> <IDNSTMT GBOOP> $ <IDB OP> = ' J ! ' 'HIT' 'ON* <IDN EXPBS) I ' . = ' I F ' 'NOT' 'HIT' 'ON' <IDN E X P E S ) $ <A5 S I B P L E IDN STBT> = <S I B P L E IDN STMT) $ <LIGSTBT> $ <BEGIN> <LIG STMT L I S T > <EHD> $ <VA8) $ <A6 LPAB> <LOG E X P B S ) • ) ' S • (• S <A9 VAa>(corvar1,fn1) <LO^OP> <V AE> (curvar2, fn2) = <LOG EXPBS> <LOGOP> <v»a> (cur_var,fncall) S <A9 VAB> (cur_var: l i t _ r e c ; fncall:BOOLEAN) = <VA8> (curvar.f n) $ •AND' S •OB' S • E L S E ' $ •BEGIN' $ •END' i <SINPLE IDN STHT) : I F FKNETRE. S t f l B = ELSE NACTION := 1 •CASE' 'HITON' 'OP <CASE ELEMENT) $ <CASE LIST> •;' <CASE ELEMENT) $ ' :' <CASEST!1T GROI7P) <MOD PAR> (p3) $ <IDHSTKT GBOOP>= <IDN E X P B S ) <A6 LPAB> <LOG EXPRS) <LOGOP> <ELSE> < BEGIN) <ZND> AHEIG3IIE <CASE SIHT) <CASE LIST) (/'ELSE'/) THEN NACTION := 2 (sinpLe) $ <CAS3 L I S T ) 'END' $ [con posite} <CASE ELEMENT) = <CASE LABEL LIST) <CASE LABEL LIST) = <SDBPICT) $ = <CASE LABEL LIST) = <v»a> $ ',' <SOBPICT> $ <SOEPICT> •CCASESTMT GBODP) = <LIGSTHT> $ = <BEGIH> <LIG STMT LIST) < END) $ <VAB)(cur v a r : l i t _ r e c ; f a c a l l : BOOLEAN) = <ID> $ = <FN IHVOC) (cur_f n_invoc) $ • = <S0BS VAB) (cur_n'Jbs._»ar) I • . <FS IBVOC)(cur fn invoc:lit_rec) ~= <FN ID)(cur_fn_id; <ACT PAa LIST) (cur_act_t>ar) S <SOBS VAB)(cur subs var:lit_rec) "= <AR3AI ID) (cur_array) <SiJ3SCH LIST) (cur_subscr) $ <ACI PAB LIST)(cur l i s t : l i t _ r e c ) = '7' <PAE LIST) (cur_par l i s t ) • ) ' « = ' ( ) • $ <S0BSC8 LIST) (cur l i s t : l i t _ r e c ) = <LBBAC> <?AR LIST)(cur_par_list) <3BRAC> $ <LBBAC> • • = • [ • * ±: • (,' $ <SBSAC> = ' ]• J »*.)•* <P»B LIST)(cur_par_list:lit_rec) ~= <PAB>(Cur_par) $ * <PAR LlST)(cucparlist) ',' <PAR>(cur_par) % <PAB>(cur_par:lit_t€c) » <ABITH KXPES) (cur_arith) I <ABITH EXPBS>(cur_.acith:Ht_rec) = <TEBH> (cur^terni) t ^ » '»• <TEBM> (c!ir_term) $ = <TEB(1) (car'ter*) I 1 0 9 « <»1 ARITH EXPBS>(curarith) <ADDOP> (cur_addop) <TER>1> (cur_t«ri») $ <ADDOP>(cur addop: Ht_rec) - «•• t - •-• $ <TEBB> (cur_ter»:lit_rec) ' <FACTOR>(cur_factor) t « <TERH>(curters) <SULT0P>(cur_«ul*op) <FACT08>(cur_factor) S <B0LTOP> (cuc_»ultop: l i t _ r e c ) ~ . ~ » • »• $ - •/• S * «DIV J = 'BOD' $ <FACT0B> (cur_factor: l i t _ r e c ) = <VAB> (cur_var.fncall) $ = <CONST>(cur const) $ = <AU LPAB> <A3 ARITH EXPRS>(cur.arith) •)• $ <A1 ABITH EXPBS>(cur_arith:lit_rec) = <ARITH £XPRS> (curarith) t <A3 ABITH EXPBS>(cur_arith: lit_rec) = <ABITH EXPBS> ( c u r a r i t h ) i <A« LPAE> = • (' $ AHBIGOITE = <ABITH EXP8S> : IF (FEKETRE.SYMB = (/'•«/)) THEN NACTION := 3 f<A1 ABITH EXPRS>) ELSE IF (FENETBE. STM3 = (/•-•/)) THEN NACTION := 3 {<A1 ARITH EXPRS>) ELSE IF stacksearch( (/<A4 LPAR>/), 200) THEN NACTION := tt (<A3 ARITH FXPRS>} ELSE IF stacksearch ( (/<LBRAC>/) , 2) THEN NACTION := 2 (<PAR>) ELSE IF stacksearch( (/<M0D2 KEYWORD>/) , 200) THEN NACTION := 1 • . {<A2 ARITH FXPRS>) ELSE IF stacksearch ( {/<MOD1 KEY»OBD>/) , 200) THEN NACTION := 1 {<A2 ARITH EXPES>) ELSE NACTION := 2 (<PAB>) $ <S0BBNG TRIPL> (c u r _ t r i p l : l i t _ r e c ) = <SDBBANSE>(cur_s1) *,• <saBBANGE> (cur_s2) ',' <S0BBAHGF>(car_s3) $ <S0BBAHGE>(cur_subr:lit rec) ~= <PAR> (cur_p1) «..' <PAR> (cur_p2) $ <COHST> (cur_const: lit_rec) = <INTEGEB> ( i n t v a l ) $ = <BEAl> ( r e a l v a l ) $ = <STBING> ( s t r d e s c r ) •$ <VYOL ID> ( c u r _ i d : l i t _ r e c ) = <:ID> J <VP ID> ( c u r _ i d : l i t _ r e c ) = <ID> $ <DEV l D > ( c u r _ i d : l i t _ r e c ) = <ID> $ <INPT ID> (c u r _ i d : l i t _ r e c ) = <IO> S <FN ID> ( c u r _ i d : l i t _ r e c ) = <ID> $ <ABBAY ID>(cur_id:lit_rec) = <ID> $ AHBIGUITE = <ID>~; • IF s t a c k s e a r c h ( (/• VIEWV0 L'JME' /) , 2) THEN NACTION := 2 (<WOT. ID>) i ELSE IF s t a c k s e a r c h f (/•VIEWPORT1/), 2) THEN NACTION := 3 {<VP ID>) ELSE IF Stacksearchf (/'DEVICE'/), 2) THEN NACTION := « {<DEV ID>) ELSE IF S t a c k s e a r c h f f/<A7 RARHOW>/) , 2) THEN NACTION := tt {<D3V ID>) ELSE IF s t a c k s e a r c h ( (/<IN?T DEVICE>/) , 6) THEN NACTION :- 5 (<INPT IP>) ELSE IF FENETRE*SYM3= (/' ('/) THEN NACTION := 6 (<FN ID) ELSE IF PENETKE.SYM3= (/' () '/) THEN NACTION : = 6 (<FN ID} ELSE IF FENETRE.SY33 = (/•[ */) THEN NACTION := 7 {ARRAY ID>] ELSE IF PENETBE.SYMB= (/• (. •/) THEN NACTION := 7 {ABHAY ID>) ELSE NACTION : = 1 (<VAR>) $ <ID>(hash:TYPIDENT) = TERMINAL IDENT $ <STBING> ( S t r d e s c r : ELCHA.INE) = TERMINAL CHAINS $ <I«TEGEB> (intval: INTEGEB) = TERMINAL ENTIEB $ <REAL>(realval:BEAL) = TEBMINAl BEEL $ $ • 110 Appendix B A SAMPLE EEOGBAM The LIG/P sample program l i s t e d on the ..following pages was used t o produce the output shown i n F i g u r e s 18 and 19. The output device was a T e k t r o n i x 4027 t e r m i n a l . *«* U3C LIG/P Preprocessor *«* 1 2 ( Program to demonstrate LIG/P; It defines a 3 cube In wire frame representation and i t s 4 sides par t i a l l y f i l l e d by coloured polygons. 5 The cube i s transformed and automatically 6 recreated after each transformation in such 7 a way that a hidden-surface e f f e c t . i s always 8 achieved. } 9 10 PBOGBAn ligdeao; 11 12 CONST 13 iiinv * 0.0; iai> = 1.0; 14 centrv = 0.5; off s t = 0.10; 15 16 TYPE i 17 * LIG TYPES; 18 arrayU = ABRAY[0..3] OF BEAL; 19 aatrix4 = AEBAY[0..15] OF BEAL; 20 xyzface = BECCBD 21 x,y,z : BEAL; 22 faceno : INTEGER 23 END; 21 zface = BECCBD 25 t : BEAL; 26 faceno : INTEGEB 27 END; 28 29 VAB 30 • LIG VA6S; 31 c_frame, 32 c~sidea : GRAPHICAL; 33 vpl, vp2 : VIEWPORT; 34 mtx : matrix!*; 35 i , 36 xangd, yangd, zangd : INTEGER; 37 trn, 38 xang, 7ang, zang, 39 xsc, ysc, zsc, 40 xtr, ytr, z t r , 41 xmove, ymove, zraove : REAL; 02 answer : CP.AR; 43 centrep : ABP.AY[1..6] OF xyzface; 44 t r zcentre : ABBAV[1..6] OF zface; 45 vp~ : ARBAY[1 . . 8 , 1..3] OF BEAL; 46 connect : AHRAY[1..6, 0.. 3 j OF INTEGER; tt7 offace : AERAY[1..6, 1..3J OF BOOLEAN; «8 49 INITIAL 50 vp = array (cube vertex points} 51 (minv,minv,minv), 52 (maxv,minv,minv) , 53 (maxv,maxv,minv), 54 (sinv,maxv,minv) , 55 (maxv , min v, maxv) , 56 (minv, minv, ma.tv) , 57 (ainv, max v, ma xv) , 58 (maiv, maxv, maxv) 59 end; 60 connect = array (vertex connections for faces) 61 (1,2,3,1), 62 (1,2,5,6), 63 (5,6,7,3), 64 (3,4,7 , 8 ) , 65 (1,4,7,6), 6* (2,3 ,8,5) 67 end; 68 centrep = array (centre points of faces) 69 (centrv,centrv,minv, 1) , 70 (centrv,minv,centrv,2), 71 (centrv.centrv,maxv,3 ) , 72 (centrv, maxv,centrv,4) , 73 (minv,centrv,centrv,5) , 74 (maxv,centrv,centrv,6) 75 end; 76 offace = array {offset of f i l l e d area for each face) 77 (true,true,fals?) , 78 (true, false, true) , 79 (true,true,false), 80 (true,false,true), 81 (false, true, true) , 82 (false,true , true) 83 end; 84 answer = 'y*; 85 86 87 « LIG PROCEDURES; 112 » * » DBC LIK/P Preprocessor **« 88 89 90 PBOCSDUBB oaxe_satrix(sx.sy,sz,ax,ay,az.tx,ty,tz : BEAL; VAB »tx : natrixl) ; 91 (Generates a 4x4-transformatioa matrix) 92 VAB 93 sinax, sinay, sinaz, 94 cosai, cosay, cosaz, 95 sinax sinay, cosax sinay : BEAL; 96 97 BEGIH 98 sinax := SIN(ax); cosax := c o s Jax) ; 99 sinay : ~ SIN (ay); cosay := COS (ay); 100 sinaz := SIN (az) ; cosaz := c o s(az) ; 101 sinax_sinay := sinax * sinay; 102 cosax sinay := cosax * sinay; 103 101 mtx[0] := sx * (cosax * cosaz); 105 a tx[ 1 ] := sx * (cosax * sinaz); 106 »tx[2] := -sinax * sx; 107 mtx(3] := 0.0; 108 mtx( 4 ] sy » ((sinax_sina 10S mtx[5] := sy * ((sinax_sinay * sinaz) • (cosax * cosaz)); 110 «tx[ 6 ] := sy * (sinax •* cosay); 111 »tx[7 ] := 0.0; 112 ntx[8] := sz * ((cosax_sinay * cosaz) • (sinax * sinaz)); 113 a t x [ 9 ] := sz * ((cosax_sinay « sinaz) - (sinax « cosaz)); 111 Btx[ 10] := sz * (cosax * cosay) ; 115 Btx[ 11 ) : = 0.0; 116 Btx[ 12 ] := tx; 117 «tx[ 13 ] := t y ; 118 Btx[ 114 ] : = tz; 119 Btx[ 15 ] := 1.0; 120 END; 121 122 123 124 PaoCEDOBE transforn(VAB Btx : matrix'4; x,y,z : SEAL; VAR xtr.ytr.ztr : BEAL); 125 (Transforms a 3D-point according to the 4x4-matrix received} 126 BEGIN 127 xtr := (x * «itx[0]) + (y * mtx[4]) «• (z * ntx[8]) • mtx [ 1 2 1 ; 128 ytr ;= (x * mtx[1]) • (y * mtx[5]) * (z * mtx [ 9 ] ) • Btx[13]; 129 ztr := (x * etx[2]) • (y * mtx[6]) • (z » mtx[10]) • mtz[14]; 130 END; 131 132 133 PBOCEDORE offset(VAR X, y, z: array4; xof f, yof f ,zof f : BOOLEAN); 134 { Kodifies points to achieve offset from cube vertex } 135 VAB i : INTEGER: 136 BEGIN 137 IP xoff THEN 138 BEGIN 139 FOB i:=0 TO 3 DO 140 IF x [ i j = minv THEN x[ i ] := minv + offst 141 ELSE IF x [ i ] = maxv THEN x[ i ] := maxv-offst 142 END; 143 IF yoff THEN 144 BEGIN 145 FOB i:=0 TO 3 DO 146 IF y [ i j = minv THEN y'[ i ] := minv*offst 147 ELSE IF y ( i ] = maxv THEN y[ i ] := maxv-offst 148 END; 149 IF zoff THEN 150 BEGIN 151 FOB i:=0 TO 3 CO 152 IF z [ i ] = minv THEN z[ i ] := minvtoffst 153 ELSE IF z [ i ] = maxv THEN z [ i ] := maxv-offst • 154 END 135 END; 156 157 158 159 FUNCTION faces (level : INTEGEB): GBAPHICAL; 160 J Becursive; generates six cube faces in the right order } 161 VAB 162 cur_face, 163 cur~frame, 164 c u r _ f i l l : GBAPHICAL; 165 laxval ; zface; 166 indx, 167 conindx, 168 polynum, 169 i , mark ; INTEGEB; 170 dist : BEAL; 171 xpoints, 172 yPoints, 173 zpoints : array4; 174 113 *** 11BC LIG/P Preprccassor 175 -BEGIN 176 { find snallest 2-coordinato of centre points ) 177 nark l e v e l ; aaxval := tr_zcentre[level ]; 178 FOR i:=level»1 TO 6 DO 179 IF tr_zcentre[ i j . z < aaxval.z TH3N 180 BEGIN mark :*= i ; aaxval := tr_zcentre[i ] 'END; 181 IP aark > level THEN (• exchange *) 182 BEGIN 183 tr_zcentre[aark ] := tr_zcentre[ level ]; 181 t r zcentre[level ] := aaxval 185 END;-186 { generate polygon face } 187 polynun := tr_zcentre[ level ]. faceno; 188 ( define frane of cube face } 189 FOR 15=0 TO 3 DO 190 BEGIN 191 indx := connectf polynua, i ); 192 xpoints[i] := vp(indx,l]; 193 ypoints[ i ] := vp[indx,2]; 191 zpoints[i] := vp[indx,3] 195 END; 196 * cur_fra«e POLYGON COL RED 197 * FBOS xpoints[0], ypoints[ 0 ], zpoints[ 0 ] 198 * TO xpoints[ 1 ], ypointsfl], zpointsf1 ] 199 * TO xpoints[2], ypoints[2], zpoints[2] 200 * TO xpoints[ 3 j, ypoints[3], zpoints[3J; 201 ( define shaded part of cube face ) 202 offset (xpoints,ypoints,zpoints, of f ace[ polynua, 1 ], 203 of f ace[ polynum, 2 ), off ace[ polynun>,3 ]) ; 204 » c a r _ f i l l :- POLYGON FILL 205 * FBOH xpoints[0], ypoints[0], zpoiuts[0] 206 * TO xpointsf 1 ], ypoints( 1 ], zpoints[ 1 ] 207 * TO xpoints[2], ypoints[2], zpointsf2 ] 208 » TO xpoints[3], ypoints[3], zpoints[3]; 209 CASE polynum OF 210 1 : BEGIN 211 * cur f i l l :- c u r _ f i l l COL BSD; 212 END; 213 2 : BEGIN 214 * c u r _ f i l l c u r _ f i l l COL BLUE; 215 END; 216 3 : BEGIN 217 * c u r _ f i l l :- c u r _ f i l l COL GREEN; 218 END; 219 ii : BEGIN 220 * c a r _ f i l l :- c u r _ f i l l COL YELLOW; 22 1 END; 222 5 : BEGIN 223 * cur f i l l :- cur f i l l COL CYAN; 224 END; 225 6 : BEGIN 226 * cur f i l l :- cur f i l l COL HAGENTA; 227 END 228 END; 229 * cur_face :- cur f i l l •* cur frame; 230 IF l e v e l < 6 THEN 231 BEGIN 232 * cur_face :- cur_face tt faces (level*1); 233 END; 231 * faces := cur_face; 235 (garbage c o l l e c t ! 236 * cur frame :- BLANK; cur f i l l :- BLANK; 237 END; 238 239 240 241 BEGIN ( ligdeao J 242 » INITIALIZE LIG; 293 * VIEWPORT vpl IS 0. 0..0.5, 0.25..0. 75, 0.0. .0.5; 244 • VIEWPORT vp2 IS 0.5.. 1.0, 0.25..0.75, 0.0..0.5; 245 246 WHILE (answer='y'( 03 (answer-'Y") DO 247 P EGIN 248 * ERASE SCREEN; 249 write (• Enter angle of rotation about x-axis in decrees (integer value).'); 250 writeln; read (xangd) ; rang := (xangrl/180.0) * 3.1415; 251 writeC Enter angle of rotation about y-axis.'); 252 writeln; read(yancd); yang := (y ancjd/130.0) * 3.1415; 253 write (' Enter angle of rotation about z-axis.'); 254 writeln; read(zangd); zang := (zangd/180.0) * 3.1415; 255 write(* Enter seals factor w. r. t. x-axis (0.0 <= s c i >= 1.0).?): 256 writeln; read |xsc] ; 257 write (« Enter scale factor w.r. t. y-axis.'); 258 writeln; read(ysc); 259 write (• Enter scale factor w.r.t. z-axis.'); 260 writeln; read (zsc| ; trn := 0.0; 261 aaks^aatrix (xsc,ysc,zsc, xang,yang,zang, trn,trn,trn, ntx) ; »** DBC LIG/P Preprocessor *** 262 FOR i:» 1 TO 6 DO 263 BKGIN 26» transform ( B t x , centrep[ 1 ]. x, centrap[ 1 ]. y, centrep[ i ]. i , 265 xtr, ytr, tr_zcontte[ i J. t) ; 266 tr xcentre[ i].faceno :» 1 267 END;" 268 » c_fr « B 8 :- POLYGON FBOH minv,minv,minv TO maxv,minv,minv 269 • TO maxvrmaxv,minv TO rainv,maxv,minv COL BED 270 • POLYGON FROM maxv,minv,maxv TO ainv,minv,maxv 271 * TO mi nv, maxv, eaxv TO maxv,Baxv,maxv COL RED 272 * LINS FROM minv,minv,minv TO minv,minv,maxv COL RED 273 * •• LINE FROM maxv,minv,minv TO maxv,minv,maxv COL RED 271 • ** LINE PRON maxv,maxv,uinv TO maxv,maxv,maxv COL RED 275 • LINE FRO.I minv,aa xv,«inv TO minv ,maxv ,maxv 276 * COL RED; 277 * c_sides :- faces (1) ; (Graphical function call} 278 ( apply imaqe transformations t o display cube } 279 • c_ f r a B e :- c_frame SCL xsc,ysc,zsc BCT xanqi,yanqd,zangd DEG 260 * AT centrv-xmove,centrv-ymovc,centrv-zmove; 281 » c_sides :- c_sides SCL xsc,ysc,zsc ROT xanqd,yangd,zanqd DEG 282 * AT centrv-xmove,ceatrv-ymov9,centrv-ZBOve; 283 • DISPLAY c_frame INTO v p l , c_sides INTO v p l , 281 » o_frame PERSPECTIVE-!.5 INTO vo2, 285 * c'sides PERSPECTIVE 1.5 INTO vp2; 286 write (' Do you want to continue? (y,n) *) ; writeln; 287 REPEAT read (answer) UNTIL ans»er-.= ' • 288 END 289 END. •290 * (End of LIG/P} . . »*»** No errors detected. 117 Appendix C THE HON-TIHE SYSTEH CALLING GRAPHS The f o l l o w i n g pages show the interdependence of r o u t i n e s o f the LIG/P r u n - t i i e l i b r a r y . , . I b i s l i s t i n g i s p r i m a r i l y i n -tended to a s s i s t f u t u r e work on the system. , The r o u t i n e names cf the Core System have no s p e c i a l p r e f i x and are a l l i n upper case. ., C A L L I N G C 8 k t H (S) lisifiitisl: l i g i n i t i a l SET_0ISPI.AT_flODE SE1~C0L0R_?10DEL ^ • S E T " I S R E O I A T E _ V I S I B I L I T Y S E L E C T _ V I E » S U R F A C E I N I T I A L I 7 . E _ V I E V _ S ' J R F A C E I N C O I B E _ S E L E C T E D _ S N R F A C E I N I T I A L I Z E _ C O B E lignwroot l,iqan_ assign: ligan_assign l i g l i nk_Bnode lignw omode lig r e i n i t _ r o o t ligdtree_outdated ligmtree_garbage ligoseg_garbag ligaseg_garbage lig«a_defl ligtr_def1 lignwroot ligerror l i g e r r o r ljqnwdnode: lignvdnode lignxt_cseg liqsp assign: ligsp_assign liglink_i»node ligmtree_garbage lig»seg_garbage li g r e i n i t _ r o o t ligdtreadout dated lignwcnode lignwroot ligerror liqan blank: ligan_blank l i g i n s e r t lignwmseg ligakndc l i g e r r o r lignwaseg l i g i n t B s e q : l i g i n t a s e g liginsert l i q a bqnline: liga_bgnline ligins_ndc l i g i n s e r t l i g i n t m s e g lignwaseg l i g i n s e r t ligmkndc llaiS.de f: ligredef ligintaseg lignwaseg lignwroot l i g r e i n i t _ r o o t ligdtree_oatdated ligaseg_garbage lig«itree_garbage 2ifla_ad£aw: liga_adraw ligins_nnc liga_rdraw ligics_ndc IXQA aendljne: liga_aendline ligins_ndc ii3a_rendline: liga_rendline ligins_ndc l i q s banline: ligs_bgnline ligsubp_init ligdtree_outdated ligaseg_garbage Iigius_ndc ligintaseg lignwaseg lignvmnode lignwroot liqsi> blank; ligsp_blank ligsnbp_init ligins^ndc ligintaseg lignwaseg l i q s adraw: l i g s a d i a K ligins_ndc l i g e r r o r l i a s rdraw; ligs_rdraw ligins_ndc l i g e r r o r l i q s aeadline: ligs_aeodline ligins_ndc l i g e r r o r l i q s rendline: ligs_rendline ligins_ndc l i g e r r o r liqplabqn; ligplabgn ligins_ndc l i g i n s e r t ligintaseg lignwaseg liqplaend: ligplaend ligins_ndc ligplrend: ligplrend ligins_ndc liqplsban: ligplsbgn ligsnbp_init ligins_ndc ligintaseg lignwaseg ligsplaend: ligsplaead liqins_ndc ligerror iigsplrend ligins_ndc ligerror ligan_string liqir.sert ligcw oseg ligspstriog lignksp l i g s u b p _ i n i l ligan fn: ligan_fn ligsseg_garbage liqsp fn: ligsp_£n ligsnfcp_init l i q a t r dump: lig»tc_dunp ligmtr_duap ligerror ligtraverse: l i g traverse ligtraverse ligmstra verse l i g i n s e r t ligmkntx lig e r r o r l i g i n s e r t ligapplytr liovar mseq: ligvar_nseg ligtraverse ligintsseg lignvasag ligerror liqsasuperfps: ligsasaperpos liglink_nnode lignvmnode li g e r r o r liqsssuperpos: ligsssaperpos lignnroot ligsasu perpos liqssanfn: ligssan£n lignvanode ,1 j.qde letlon: ligdeletion ligerror lig»_append ligerror liqdevjce: llgdevice INITIALIZE_VIEW SHRPACE . ligersmdevi.ee NEV_t'RAME ligdgarbago DKLETS_EETAINED SEGMENT SET_SEG!1ENT_VIsTBILITY JigersdevjLce: ligersdevice ligdgarbage i i a e i s i d : l i g e r s i d SET_SEGI1ENT_ VISIBILITY l i g s e l e c t : l i g s e l e c t SELECT_VIE«_SORFACE DESBLECT_VIEB_SUHPACE ligdeselect: ligdeselect SELECT_VIE»_SURFACE DESELECT_VIEW SOBFACE liqnewfraae: lignewframe NEW_FRAHB SELECT_VIES_S3RFACE DESELECT_ VIEW_SURFACE iiovdisfi: ligvdisp ligdeselect ligmseg_garbage CLOSE_BETAINED_SEG!1ENT l i g c _ p r i s i t i v e s POLYGON_ABS 3 POLYLINE ABS_3 LINE_ABS_3 l i g e r r o r HOVE_AES 3 SET_LINESTYLE SET_FILL_INDEX SET_LINE_INDEX ligtraverse lignwmseq CBEATE RETAINSD_SEGMENT . SET_VIEHPORT_3 SET_BACK_PLANE_CLIPPING" SET~FBONT_PL-ANI_CLIPPING SET!HINDOH_CLIPPING SET_VIEW_BEFERENCE_POINT SET_PBOJECTION SETIVIEW_DEPIH SET~8INDOW SET_IHAGE_TRANSPORMATI0N 3 SET^HIGHLIGHTING lignvdnode ligselect 113 i » a r_disp: l i g i v a r _ d i s p lignuroot ligvdisp 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051807/manifest

Comment

Related Items