Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A high-level graphics programming language supporting the inquiry of graphical objects 1982

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
UBC_1982_A7 R68.pdf [ 7.02MB ]
Metadata
JSON: 1.0095574.json
JSON-LD: 1.0095574+ld.json
RDF/XML (Pretty): 1.0095574.xml
RDF/JSON: 1.0095574+rdf.json
Turtle: 1.0095574+rdf-turtle.txt
N-Triples: 1.0095574+rdf-ntriples.txt
Citation
1.0095574.ris

Full Text

A HIGH-LEVEL GRAPHICS PROGRAMMING LANGUAGE SUPPORTING THE INQUIRY OF GRAPHICAL OBJECTS by ROBERT VAUGHAN ROSS .A.Sc., The University of B r i t i s h Columbia, 198 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED.SCIENCE in THE FACULTY OF GRADUATE STUDIES (Department of E l e c t r i c a l Engineering) We accept th i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA June 1982 © Robert Vaughan Ross, 1982 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y available for reference and study. I further agree that permission for extensive copying of t h i s thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. I t i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department O f Electrical Engineering The University of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date July 22, 1982 DE-6 (3/81) ABSTRACT High-level graphical programming languages provide simply expressed constructs for the d e f i n i t i o n , manipulation, and external representation of graphical data. Such languages can be used to create e f f e c t i v e and readable application programs. This thesis investigates the value of allowing the inquiry of graphical data in a graphical language. Major design goals of an implementation of a language with these c a p a b i l i t i e s are presented. A data base model and implementation are discussed. The c l a s s i f i c a t i o n of graphical primitives as abstract data types is presented. Examples are given of several areas in which a language including graphical inquiry may be applied. It is concluded that inquiry permits the d e f i n i t i o n and manipulation of a r b i t r a r y models of graphical objects, so enabling the implementation of sophisticated graphical algorithms. i i i TABLE OF CONTENTS Page LIST OF FIGURES v ACKNOWLEDGEMENTS v i i Chapter 1. INTRODUCTION 1 2. LANGUAGE DESIGN GOALS 4 2 . 1 Inquiry 4 2.2 Levels Of Usage 5 2.3 Fortran Consistency 8 2.4 Separate Preprocessing And Compilation 10 3. DATA BASE SYSTEM i 12 3.1 Data Base Model 14 3.2 Data Base Implementation 22 4. GRAPHICAL OUTPUT PRIMITIVES 28 4.1 Primitives As Abstract Data Types 28 4.2 Programmer Defined Primitives 30 4.3 Graphical Functions Versus Graphical Primitives ... 35 5. GRAPHICAL DOMAINS 38 5.1 Construction Tools 38 5.2 Systematic Manipulation 40 5.3 Graphical Editing 45 5.4 Data Structures 52 6. NEW LANGUAGE FEATURES 59 i v 0* 6.1 Vector Data Type ' 59 6.2 Map Operator 61 6.3 Stroke P r e c i s i o n Text 65 6.4 S t r u c t u r e d Statements 66 6.5 A r c h i v a t i o n 69 7. CONCLUSIONS 72 BIBLIOGRAPHY 80 APPENDIX A - A Sample Program 82 APPENDIX B - Implementation Notes 86 V LIST OF FIGURES Figure 1 Data Base Model 15 Figure 2 VALUE And SUPER Functions 16 Figure 3 Nested Graphical Expressions 18 Figure 4 Copy Assignment 20 Figure 5 Value Assignment 20 Figure 6 Super Assignment 21 Figure 7 Graphical Node Structure 23 Figure 8 Primitive Record Header 24 Figure 9 Primitive Record Storage 26 Figure 10 Integer External Representation 30 Figure 11 Allowable Primitive Template Grammar Productions 33 Figure 12 Square Primitive 32 Figure 13 Parallelogram Primitive 33 Figure 14 Sphere Primitive 36 Figure 15 Graphical Ductwork Construction Tools 40 Figure 16 Arbitrary Pipe Model 41 Figure 17 Second View Of Pipe 41 Figure 18 Helix Constructed With REVOLV 42 Figure 19 Second View Of Helix 42 Figure 20 Deep Replace Algorithm 44 Figure 21 Graphical Substitution 45 Figure 22 Origi n a l Model Image 47 Figure 23 Origi n a l Tree Structure 48 v i Figure 24 Graphical Editing Addition 48 Figure 25 Viewing Editing Result 49 Figure 26 Editing Level Change 49 Figure 27 Subobject Modification 50 Figure 28 Origi n a l Root Redrawn 50 Figure 29 Structure Alteration 51 Figure 30 Graphical Editing Result 51 Figure 31 Grammar Storage Data Types And Variables 54 Figure 32 Or i g i n a l Grammar Internal Representation 55 Figure 33 Manipulated Grammar Internal Representation .... 56 Figure 34 Sample Input Grammar 57 Figure 35 Sample Syntax Directed Diagram 58 Figure 36 Vector Operators 60 Figure 37 Vector Data Type Usage 61 Figure 38 Vector Component Access 61 Figure 39 Map Operator Examples 62 Figure 40 Z-Rotation Matrix 63 Figure 41 Map Operator Implementation 64 Figure 42 Text Precision 66 Figure 43 Stroke Precision Text 67 Figure 44 Structured Statements Grammar 68 Figure 45 Structured Statements Examples ' 69 v i i ACKNOWLEDGEMENTS I would l i k e to express my s i n c e r e a p p r e c i a t i o n to Dr. Gunther Schrack f o r h i s i n v a l u a b l e h e l p and guidance. I am g r a t e f u l to my parents f o r t h e i r support and encouragement. T h i s research would not have been p o s s i b l e were i t not f o r the f i n a n c i a l support of the N a t i o n a l Science and En g i n e e r i n g Research C o u n c i l . 1 Chapter 1 INTRODUCTION There has always been considerable interest in the presentation of information in p i c t o r i a l form. As computers are applied in an increasing number of areas and more information i s stored in machine-readable form, the demand for the automatic generation of graphical images also increases. The f i e l d of computer graphics i s concerned with the generation of such images. Most programmers' i n i t i a l experience with computer graphics involves graphical subroutine systems. The major task of these systems i s to act as an interface between application programs and graphical input and output devices. The subroutines generally do not provide modelling functions, this i s l e f t as a task of the application program. Modelling functions are provided by high-level graphics programming ' languages. These languages consider graphical information to be values of an abstract data type. They provide constructs which define and manipulate data of the type GRAPHICAL. High-level graphics languages possess several advantages over subroutine systems: high p o r t a b i l i t y of programs and programmers, ease of learning the language, and improved re a d a b i l i t y of a program. This thesis discusses some aspects of the design and implementation of such a language. The name of 2 t h i s language i s LIG6 (Language f o r I n t e r a c t i v e Graphics V e r s i o n 6). I t i s the most recent v e r s i o n of a f a m i l y of languages [Schr76,Mann80], with new f e a t u r e s and c h a r a c t e r i s t i c s . During the past y e a r s , many h i g h - l e v e l g r a p h i c s languages have been d e s c r i b e d or proposed, notably i n papers by Ku l s r u d [ K u l s 6 8 ] , Newman [Newm7l], Smith [ S m i t 7 l ] , and, more r e c e n t l y , Magnenat-Thalmann et a l . [Magn8l], and Barth et a l . [ B a r t 8 l ] . McLean [McLe78] d i s c u s s e s 37 languages i n a survey. The languages d i f f e r widely i n both syntax and semantics, as w e l l as in the approaches taken f o r t h e i r implementation. The m o d e l l i n g c o n s t r u c t s of these languages allow the e x p l i c i t d e f i n i t i o n and manipulation of models of g r a p h i c a l o b j e c t s . T h i s permits a p p l i c a t i o n programs to perform p a s s i v e or i n t e r a c t i v e g r a p h i c s . I t i s d i f f i c u l t f o r programs i n these languages to manipulate a r b i t r a r y models of g r a p h i c a l o b j e c t s because of the d i v e r s e nature of these models. T h i s t h e s i s i n v e s t i g a t e s areas i n which a g r a p h i c s programming language can be a p p l i e d when a formal model s t r u c t u r e and i n q u i r y i n t o such s t r u c t u r e s are pr o v i d e d . LIG6 i s implemented as an extension to a host language, FORTRAN. A pr e p r o c e s s o r , w r i t t e n i n PASCAL, converts LIG6 programs i n t o standard FORTRAN programs with e x t e n s i o n elements t r a n s l a t e d i n t o c a l l s to subrout i n e s i n a run-time l i b r a r y . These subrou t i n e s are coded i n FORTRAN. When a LIG6 program i s to be executed, the o b j e c t deck produced by co m p i l i n g the prepr o c e s s o r output i s run i n c o n j u n c t i o n with the run-time l i b r a r y . Only those d e t a i l s of the language and of i t s implementation which are p e r t i n e n t to the p o i n t s d i s c u s s e d i n 3 t h i s t h e s i s are o u t l i n e d ; more complete i n f o r m a t i o n i s a v a i l a b l e i n the LIG6 User's Manual [Ross82]. Chapter 2 presents the major design goals of the language. The o v e r a l l s t y l e of the language with respect to the host language and the importance of separate p r e p r o c e s s i n g and c o m p i l a t i o n of modules i s c o n s i d e r e d . Aspects of i n q u i r y and the p a r t i t i o n i n g of language c o n s t r u c t s i n t o a h i e r a r c h y are addressed. The concept of a data base system i s presented i n Chapter 3. The b e n e f i t s of programmer knowledge of system implementation are d i s c u s s e d . A model of the data base and a summary of i t s implementation are given. Chapter 4 i n t r o d u c e s the idea of regarding g r a p h i c a l output p r i m i t i v e s as true a b s t r a c t data types. The method by which programmers can d e f i n e such p r i m i t i v e s and the d i f f e r e n c e s between p r i m i t i v e s and g r a p h i c a l f u n c t i o n s are o u t l i n e d . Examples of areas i n which LIG6 can be a p p l i e d are presented i n Chapter 5. T o o l s f o r the c o n s t r u c t i o n of models of g r a p h i c a l o b j e c t s are d i s c u s s e d . The systematic manipulation of g r a p h i c a l o b j e c t s i s d e f i n e d . The concept of i n t e r a c t i v e l y e d i t i n g g r a p h i c a l o b j e c t s i s presented. Employing g r a p h i c a l data to represent a b s t r a c t ideas i s i n t r o d u c e d . A sample of f e a t u r e s p r o v i d e d i n LIG6 i s given i n Chapter 6. An e f f e c t i v e t r a n s f o r m a t i o n operator i s i n t r o d u c e d , the support f o r the data type VECTOR i s o u t l i n e d , stroke p r e c i s i o n t e x t i s d e s c r i b e d , and the a b i l i t y to save and r e s t o r e models of g r a p h i c a l o b j e c t s i s d i s c u s s e d . 4 Chapter 2 LANGUAGE DESIGN GOALS 2 . 1 Inqui ry Usually, algorithms are implemented where the flow of control depends on the results of previous operations. To make control decisions, a program must be able to inquire about values of variables and expressions and determine what operations have occurred. For interesting graphical algorithms to be implemented, the results of graphical operations must be accessible to control structures. Thus, one of the design goals of L IG6 was to support information recovery. Information recovery i s the a b i l i t y to access the results of actions and thereby determine what operation occurred. It is supported by providing methods of obtaining such access for a l l graphical operations. Two forms of access are used in LIG6. If a natural, consistent s y n t a c t i c a l construct i s possible, i t is used. Otherwise, system subprograms are provided. A c a l l to such a subprogram results in the desired information being returned in the routine's parameters. In LIG6, l o g i c a l expressions have been extended to include the comparison of models of graphical objects. In this way, the 5 results of graphical assignment statements can control a program's execution. S i m i l a r l y , i t can be determined whether a variable's value i s a primitive and, i f so, which type. The structure and content of primitive records are accessible, so enabling control decisions and automated modelling. The results of transformations and attribute settings in assignment statements are also accessible. A dualism between action and inquiry has been established: for every operation there i s a method to determine the nature and result of i t s action. 2 . 2 Levels of Usage As is true for most occupations, computer programmers tend to possess d i f f e r e n t l e v e l s of sophistication related to their experience and a b i l i t y . A programming language i s most useful i f i t i s a t t r a c t i v e to programmers of a l l l e v e l s . This general appeal may be obtained by dividing the language into levels with each l e v e l a superset of that d i r e c t l y below i t . The lower l e v e l features are arranged to be independent of those at higher l e v e l s . This p a r t i t i o n i n g is one of the design goals of LIG6. Another benefit of l e v e l p a r t i t i o n i s the r e l a t i v e ease with which the language can be learned. Programmers are able to quickly obtain results using low l e v e l constructs and then advance naturally, as t h e i r needs increase. Programming languages in general, and LIG6 in p a r t i c u l a r , can be v i s u a l i z e d as having three lev e l s of usage. Each of these leve l s i s i d e n t i f i e d by the styles of tasks performed. The f i r s t l e v e l i s a subset of the second which i s , in turn, a subset of 6 the l a s t . The f i r s t l e v e l is characterized by e x p l i c i t commands and l i t t l e i nteractive a c t i v i t y . In a conventional programming language, programs which generate tables or solve well-defined mathematical problems such as numerical integration are of t h i s l e v e l . The corresponding l e v e l in LIG6 is represented by programs which e x p l i c i t l y model a well-defined graphical object and display an external representation of that model, i . e . an image, on a device. There are four independent constructs which support this l e v e l in LIG6. The f i r s t construct consists of the various methods of declaring graphical variables. Modelling i s performed with the simple assignment statement and with the standard graphical primitives. Modelling transformations and a t t r i b u t e settings are performed with the modification constructs. The l a s t construct i s the display statement which produces images of the results of graphical modelling. At this l e v e l , the programmer i s the a r t i s t , e x p l i c i t l y creating the desired image. The second l e v e l of use is characterized by a high l e v e l of interactive a c t i v i t y and the e x p l i c i t modification of e a r l i e r processes and r e s u l t s . A t y p i c a l program in a conventional language of t h i s type would be one in which results are obtained in an i t e r a t i v e fashion with new starting values and process parameters supplied i n t e r a c t i v e l y by the user. At t h i s l e v e l , LIG6 programs e x p l i c i t l y modify models and images of graphical objects. In LIG6 programs, models of graphical objects constructed by assignment statements are modified using the deletion 7 s t a t e m e n t . Images produced by the d i s p l a y statement may be m o d i f i e d u s i n g two t y p e s of e r a s u r e s t a t e m e n t s . I n t e r a c t i v e a c t i v i t i e s a r e s u p p o r t e d by the i d e n t i f i c a t i o n c o n s t r u c t s . The programmer i s removed one s t e p from the use of the program a t t h i s l e v e l ; he c r e a t e s a p p l i c a t i o n programs which a re then run by u s e r s t o c r e a t e the images they d e s i r e . The t h i r d and h i g h e s t l e v e l i s c h a r a c t e r i z e d by programs u s i n g knowledge of t h e i r own da t a bases and which use i n q u i r y of the r e s u l t s of p r e v i o u s o p e r a t i o n s t o det e r m i n e the f l o w of c o n t r o l . A t y p i c a l problem i n c o n v e n t i o n a l programming languages at t h i s l e v e l might be a s e a r c h i n g a l g o r i t h m f o r the r o o t s of e q u a t i o n s . The c o r r e s p o n d i n g l e v e l i n LIG6 i s t y p i f i e d by programs which i m p l i c i t l y modify a r b i t r a r y models of g r a p h i c a l o b j e c t s or c r e a t e new models based on the r e s u l t s of p r e v i o u s m o d e l l i n g . T h i s l e v e l i s s u p p o r t e d i n LIG6 by m o d e l l i n g and i n q u i r y c o n s t r u c t s . A d a t a base d e f i n i t i o n model i s p r o v i d e d . A complete s e t of m o d e l l i n g o p e r a t o r s i s p r o v i d e d g i v i n g a programmer the a b i l i t y t o p r e c i s e l y d e f i n e and modify models. Access i s p r o v i d e d t o a l l p a r t s of a model f o r i n f o r m a t i o n r e t r i e v a l . Programmers a t t h i s l e v e l a r e o f t e n removed two s t e p s from the use of the program. They c r e a t e the program t o o l s which a p p l i c a t i o n programmers then i n c o r p o r a t e i n a p p l i c a t i o n programs w i t h which u s e r s f i n a l l y c r e a t e images. Without t h i s f i n a l l e v e l , i t i s d i f f i c u l t t o implement programs w i t h the a b i l i t y t o make i n t e l l i g e n t d e c i s i o n s . S o p h i s t i c a t e d g r a p h i c s programs would be f o r c e d t o m a i n t a i n s e p a r a t e d a t a bases, d e f e a t i n g one of the p r i m a r y purposes of a 8 high-level graphics language. An idea of the importance of this l e v e l can be obtained by considering the IF statement. Most computer programs contain such conditional statements implying that they are at the t h i r d l e v e l . No inquiry constructs are available in the f i r s t two l e v e l s . A graphical language with the a b i l i t y to perform inquiry on the results of graphical operations c l e a r l y has a d i s t i n c t advantage over one which does not. 2.3 Fortran Consistency V i r t u a l l y a l l graphics programming languages are extensions to existing high-level computer languages. A graphics application program w i l l generally require non-graphics constructs for support. When these constructs are i d e n t i c a l to those of a language already known to a programmer, the time and e f f o r t required to become fluent with the graphics language is reduced. Any gains made with t h i s approach, however, w i l l be lessened i f the language extension is not consistent with the host language. Each individual construct of a given computer language has rules governing i d e n t i f i e r names, reserved words, and format which i t shares with the other constructs. In addition, operations possible with d i f f e r e n t data types are arranged to overlap as much as i s fe a s i b l e . If these general rules are ignored when a language is extended and a d i f f e r e n t style is used for new constructs, a programmer w i l l be forced to learn and retain twice as much information regarding s t y l e ; confusion 9 w i l l occur over the choice of style for a p a r t i c u l a r construct. It i s with t h i s in mind that one of the design goals of the language was to make a l l extensions as consistent with FORTRAN as possible. The most important features of the format of a FORTRAN program are that blanks are not delimiters, and that there are no reserved words. A l l syntax i s determined by context, making FORTRAN one of the more d i f f i c u l t computer languages to parse. A c l a s s i c example of t h i s i s the two statements DO 10 I = 5 DO 10 I = 5,9 The f i r s t statement is an assignment statement where the integer expression 5 i s coerced into a real expression and assigned to the variable DO10I. The second statement i s a DO statement with the integer index I ranging in value from 5 to 9 and an object whose statement has the label 10. A parser cannot di s t i n g u i s h between the two statements u n t i l i t reaches the comma. Such input format conventions remain in LIG6. The extensions do not introduce reserved words, and blanks are s t i l l ignored. Some upwards compatible freedoms have been added to the format of both host and extension statements. Statements may now span lines without the use of a continuation card, although such cards are s t i l l permitted and recognized. Multiple statements per l i n e are allowed, provided they are separated by semicolons. Comments enclosed in braces may appear anywhere. The length of a l i n e has been extended from 72 to 255 characters and column positions are not important regarding statement labels and the beginning of statements. None of these extensions r e s t r i c t 10 previously correct format; ANSI standard FORTRAN programs are acceptable LIG6 programs. In FORTRAN, there i s a variety of rules and operations which apply to data types generally. I d e n t i f i e r s are r e s t r i c t e d to a length of six characters. Variables and function i d e n t i f i e r s may be typed e x p l i c i t l y , or else i m p l i c i t l y with the aid of the IMPLICIT statement. There are no less than three statements which can determine the dimensions of an array variable: e x p l i c i t type declaration statements, the DIMENSION statement, and the COMMON statement. Expressions may be passed as arguments to subprograms. A l l of these rules also apply to the extension data types. The extension type GRAPHICAL i s e s s e n t i a l l y a pointer type. Some of the declarations possible for non-pointer types, therefore, are not permissible with t h i s type. Graphical variables may not be i n i t i a l i z e d , as in a DATA statement. They may not be equivalenced or placed in a common block position which i s also referenced by a non-graphical variable. F i n a l l y , statement functions are not allowed for this type. 2.4 Separate Preprocessing and Compilation In computer science, there is always the question of the effe c t a programming style has on the a b i l i t y to e a s i l y generate correct, maintainable solutions to problems. A style known as modularization [Dijk76] has i t s origins in c l a s s i c a l problem solving: s p l i t t i n g a problem so that when a l l of the subparts are solved, the overall . solution has been obtained. Modular 11 programs are written in FORTRAN with the aid of subprograms. Being able to create and i n d i v i d u a l l y test modules of a program has at least two benefits. The f i r s t i s that i t is much easier to isol a t e errors in a small, uncomplicated module than i t i s in a complete program. The second i s that once a module is complete and correct, i t can be used in any program which requires a similar problem to be solved. In this fashion, problems need only be solved once. To promote modular programming and the creation of l i b r a r i e s of useful graphical routines, the FORTRAN module or subprogram i s f u l l y supported as a design goal of LIG6. Function subprograms of type GRAPHICAL are included, and graphical variables and function i d e n t i f i e r s may be parameters of a subprogram. Consistent with FORTRAN, variables which are not parameters are l o c a l to a subprogram and are automatically i n i t i a l i z e d upon entry to the routine. The creation and use of l i b r a r i e s of e f f e c t i v e graphical routines w i l l allow the system to evolve into a powerful design and v i s u a l i z a t i o n t o o l . 12 Chapter 3 DATA BASE SYSTEM A high-level programming language has several advantages over an assembly-level language. These advantages include p o r t a b i l i t y of programs and programmers, ease of learning the language, improved readability of programs, and the removal of d e t a i l irrelevent to an app l i c a t i o n . Similar advantages are evident when comparing a high-level graphics language with subprogram packages such as CORE [GSPC79] or IG [Mair8l]. The lower l e v e l constructs of LIG6 preserve the concept of data abstraction with regard to graphical data. A conventional programming language allows the natural d e f i n i t i o n and manipulation of numbers and l o g i c a l values without requiring the programmer to know about the internal representation or al l o c a t i o n of these data types. S i m i l a r l y , lower l e v e l LIG6 constructs permit the treatment of graphical data in an abstract fashion via the simple d e f i n i t i o n and presentation of models of graphical objects. Use of the advanced l e v e l constructs, especially those involving inquiry, require some knowledge of the implementation of the language and of i t s data base. To some extent, the use of lower l e v e l constructs of both conventional programming languages and LIG6 also requires that some knowledge of implementation be acquired. In FORTRAN, for example, a programmer must be aware of the quantity of memory 1 3 allocated for various data types when using COMMON blocks and of the storage mechanism for multi-dimensioned arrays. In LIG6, the data type GRAPHICAL must be recognized as being a pointer type so that recursive d e f i n i t i o n s are not made. The a b i l i t y to produce sophisticated programs increases with the amount of knowledge of implementation. Knowledge of how character data is packed in various FORTRAN data types enables the user to make str i n g comparisons using integer arithmetic. Exploitation of the variant part of structured records of PASCAL allows coercion between data types. One of the reasons assembly languages are used i s the freedom a programmer has for implementations. Being the designer of an implementation which can be t a i l o r e d to f i t the application, the programmer i s the one best q u a l i f i e d to use i t . To enable the use of the advanced le v e l LIG6 constructs by a programmer, certain information about the implementation must be provided for him. This information includes a model of the data base and the effects of graphical modelling on the data base. Advanced le v e l constructs are explained in terms of their data base effects as well as their graphical e f f e c t s . These constructs are complete in the sense that a l l possible data base values may be created with their use. Their a v a i l a b i l i t y ensures that a programmer may precisely model and manipulate graphical objects within the bounds of the c a p a b i l i t y of the data base implementation. It is to the advantage of programmers using the advanced l e v e l constructs to view LIG6 as a data base management system with graphical s i d e - e f f e c t s . There i s no degrading of the system from i t s high-level 1 4 graphics programming language status when t h i s view i s taken. Lower l e v e l constructs do not require knowledge of the data base model and advanced le v e l users are not required to manage the data base. New elements are allocated automatically, system interfaces are taken care of, the graphical interpretation of the data base i s b u i l t in, and discarded elements are garbage- c o l l e c t e d by the system. By providing the implementation information to programmers, the most e f f e c t i v e use of the system becomes possible. 3.1 Data Base Model Graphical data i s inherently h i e r a r c h i c a l in nature. This is r e f l e c t e d in the implementation of the data base. For the purpose of using the advanced l e v e l constructs of LIG6, the graphical data base can be vi s u a l i z e d as a binary tree. This is a dynamically alterable n-level h i e r a r c h i c a l data base [FOLE82]. Leaves of the tree are graphical output pri m i t i v e s . Modelling transformations and attribute d e f i n i t i o n s are stored in the nodes of the tree. This model of the data base system i s i l l u s t r a t e d by the following synonym assignment statements where means assignment and "+" means superposition. Their r e s u l t i n g tree structure is displayed in Figure 1. A : - LINE FROM (X1,Y1 ,Z1) TO (X2,Y2,Z2) TO (X3,Y3,Z3) B : - POLY FROM (P1,Q1 ,R1) TO (P2,Q2,R2) TO (P3,Q3,R3) C : - 'HI THERE' < MOD 0 > D : - A < MOD 1 > + B < MOD 2 > E : - D < MOD 3 > + C < MOD 4 > + LINE FROM (T1,U1,V1) TO (T2,U2,V2) In the representation of the binary tree in Figure 1, the pointer to the right of each node is c a l l e d the value pointer. 15 LINE X1,Y1,Z1 X2,Y2,Z2 X3,Y3,Z3 B <2> < > POLY P1,Q1,R1 P2,Q2,R2 P3,Q3,R3 <4> <0> STRING HI THERE < > LINE T1,U1,V1 T2,U2,V2 Fig u r e 1 Data Base Model The value of a node i s the o b j e c t model which i t s value p o i n t e r r e f e r s t o , m o d i f i e d by the t r a n s f o r m a t i o n s s t o r e d i n the node. A value p o i n t e r can p o i n t to another node or to a l e a f of the t r e e . Leaves are g r a p h i c a l output p r i m i t i v e s . The downward p o i n t e r from each node i s c a l l e d the super p o i n t e r . Whenever a g r a p h i c a l o b j e c t i s superimposed on another, the modelling e f f e c t s are the f o l l o w i n g : c r e a t e a node, d i r e c t the value p o i n t e r of the new node to the superimposing o b j e c t , s t o r e any 16 m o d i f i c a t i o n s s p e c i f y i n g the in s t a n c e of that o b j e c t i n the new node, and d i r e c t the super p o i n t e r of the o r i g i n a l node to the new node. For access to subo b j e c t s , two g r a p h i c a l system f u n c t i o n s are p r o v i d e d - VALUE and SUPER. They each take one argument of type g r a p h i c a l (which i s a p o i n t e r type) and r e t u r n the a p p r o p r i a t e p o i n t e r of that argument's node. As f o r a l l f u n c t i o n s i n FORTRAN, these system f u n c t i o n s must have t h e i r type d e c l a r e d , e i t h e r i m p l i c i t l y or e x p l i c i t l y , before use. An example of t h e i r use i s GRAPHICAL A,B,C,D,E,F,VALUE,SUPER A :- B + C D :- E + A F :- VALUE(SUPER(VALUE(SUPER(D)))) The l a s t statement i s e q u i v a l e n t to F :- C The co r r e s p o n d i n g t r e e r e p r e s e n t a t i o n i s presented i n F i g u r e 2 . D E A B C Fi g u r e 2 VALUE and SUPER Functions 17 Use of the VALUE and SUPER functions requires that the programmer knows the tree structure of a p a r t i c u l a r model. The structure, however, i s known because i t i s determined by the assignment statements he has used to specify the object. In l i g h t of t h i s , nested graphical expressions take on a new mean ing. For simple use of the language, nested graphical expressions merely provide an easy method for applying a transformation to more than one graphical object. An experienced LIG6 programmer can use nested expressions, however, to precisely specify the structure of his model as well as i t s external representation. The two groups of statements A 1 : - B + C + D + E DISPLAY A1 A2 :- (B + (C + D) + ((E))) DISPLAY A2 w i l l cause the same image to appear on the screen but the structure of the models w i l l be d i f f e r e n t . The structure of a model can convey information to a program as e f f e c t i v e l y as the contents of the structure's nodes. The two structures of the above assignment statements are shown in Figure 3 . To enable a programmer to exert maximum control over his models, four types of graphical assignment statements have been provided. They are the synonym assignment, copy assignment, value assignment, and the super assignment statements. Synonym assignment has already been introduced. This i s the only graphical assignment statement needed by a programmer using simple l e v e l language constructs. Such a programmer does not need to know the effect of this assignment on tree structures or 18 A1 B A2 B F i g u r e 3 Nested G r a p h i c a l E x p r e s s i o n s even that the data base implementation can be modelled as a t r e e s t r u c t u r e . The assignment operator f o r t h i s type i s the symbol I t r e d e f i n e s the value and super p o i n t e r s and the contents of the node and a u t o m a t i c a l l y c r e a t e s new nodes f o r s u p e r p o s i t i o n at the top l e v e l . The synonym assignment statement a l l o w s the most general form of e x p r e s s i o n to the r i g h t of i t s operator of a l l of the assignments. The production f o r t h i s e x p r e s s i o n can be c a l l e d <graphexpress>. The Backus-Naur form d e f i n i t i o n f o r t h i s p r o d u c t i o n i s <graphexpress> ::= <graphterm> | <graphexpress> + <graphterm> <graphterm> ::= <graphfactor> | <graphfactor> < m o d i f i c a t i o n l i s t > <graphfactor> ::= <graphprimitive> <graphprimary> ( <graphexpress> ) <graphprimary> ::= <graphvariable> | <graphfunction> 19 The copy assignment statement also redefines a l l aspects of a node. Its operator i s ":=". The effect of such an assignment is simply to copy the pointers and transformations stored in the node sp e c i f i e d on the right hand side into the node specified on the l e f t hand side. Subsequent display of either node would y i e l d i d e n t i c a l v i s u a l r e s u l t s . The expression on the right must be a <graphprimary>, that i s , a graphical variable or function with no modifications or superpositions. Consider the following statements. i) B :- C + (D + E) i i ) A :- B i i i ) A := B iv) A := VALUE(SUPER(A)) If each statement were executed in order, the corresponding structures in Figure 4 would be generated. The value assignment statement affects the value pointer of a node and the transformations stored in i t . The super pointer is not affected. The value assignment operator i s ":>". Its effe c t i s to change the i n i t i a l value d e f i n i t i o n of a node, but not any objects which have been superimposed upon i t . The expression on the right must be a <graphterm>, that i s , the same as a <graphexpress> except that no superposition is allowed. The following statements generate the tree structures of Figure 5. i) A :- B + C i i ) A :> (D + E)<COLOUR 120> The super assignment statement redefines the super pointer of a node. The value pointer and the transformations stored in the node are not affected. Its operator i s ":<". Its effect is to replace a l l objects that have been superimposed on an i n i t i a l l y defined object by a new object. The expression on the D B ( i i ) i ) ( i v ) F i g u r e 4 Copy Assignment B E — > ( i ) F i g u r e 5 ( i v ) Value Assignment 21 r i g h t must be a <graphfactor>, that i s , the same as a <graphterm> but no m o d i f i c a t i o n s are allowed. The f o l l o w i n g statements y i e l d the s t r u c t u r e s d e p i c t e d i n F i g u r e 6. i ) A :- B + C i i ) D :- E + B i i i ) A :< SUPER(D) i v ) D :< (B<COLOUR 120> + (C)) B B ( i ) B B ( i i ) E • B > ( i i i ) ( i v ) F i g u r e 6 Super Assignment The p r e c e d i n g four assignment statements form a complete set of o p e r a t o r s . They enable programmers to c r e a t e any b i n a r y t r e e s t r u c t u r e they d e s i r e . A d d i t i o n a l l y , c o n s t r u c t s are p r o v i d e d which enable o p e r a t i o n s on the leaves of the t r e e , the output p r i m i t i v e s . 22 3.2 Data Base Implementation The previous section discussed the model of the data base of LIG6. The use of the word model i s important; i t emphasizes that information about the fine d e t a i l s of the data base implementation are not needed by users of advanced l e v e l constructs. To reinforce t h i s point, a summary of the implementation w i l l now be given. The nodes depicted in Figure 1 could be stored using a variety of methods: as arrays in common blocks, as li n e s or groups of li n e s in disk f i l e s , or as records in dynamically acquired v i r t u a l memory. The f i r s t approach fixes the size of the data base. Small programs would pay the price of high memory charges for the unused portions required for larger programs. The second method has high overhead in disk charges and execution time. The last method uses only as much memory as. a program requires but does not have the overhead that secondary storage involves. It i s the approach chosen for the implementation of the LIG6 data base. Each node requires 24 four byte words of contiguous memory. The f i e l d s of each node are of three d i f f e r e n t types: fullword REAL, fullword INTEGER, and halfword INTEGER. Because the nodes are stored in v i r t u a l memory, access to them involves pointers and a. system subroutine c a l l . Access to the f i e l d s of di f f e r e n t types i s accomplished by passing the pointer three times with a di f f e r e n t type declaration for each. The following statements i l l u s t r a t e t h i s . 23 EXTERNAL ACCESS CALL CALLER(ACCESS,POINTR,POINTR,POINTR) SUBROUTINE ACCESS(REALA,INTA,INT2A) REAL REALA(24) INTEGER INTA(24),INT2A*2(48) The f i e l d s of a node store the modelling transformations and attribute settings and the instance d e f i n i t i o n s s p e c i f i e d by graphical assignment statements. The structure of a node i s given in Figure 7. Position Name Type Use fword Fullword 1-12 TRMAT REAL transformation matrix 13 COLOUR REAL in t e r i o r hue attribute 1 4 LITNES REAL in t e r i o r lightness a t t r . 1 5 SATUTN REAL in t e r i o r saturation a t t r . 1 6 PATERN INTEGER in t e r i o r pattern attribute 1 7 BCOLOR REAL border hue attribute 18 BLITNS REAL border lightness attribute 19 BSATUN REAL border saturation a t t r . 20 BPATRN INTEGER border pattern attribute 21 STYLE INTEGER lin e style attribute 43 WIDTH I NT* 2 l i n e width at t r i b u t e 44 FONT I NT* 2 textstring font number 45 VALUE I NT* 2 value pointer 46 SUPER I NT* 2 superposition pointer 47 INSTAN I NT* 2 instance pointer 48 GARBGE I NT* 2 garbage c o l l e c t o r storage Figure 7 Graphical Node Structure Every graphical variable i s an integer halfword pointer to a node. These pointers are not the actual v i r t u a l memory addresses of the nodes (which would require a fullword for pointer storage), but indices into an array of nodes. This array is organized as blocks of 42 nodes. Each block i s approximately one page (4096 bytes) of vir t u a l , memory. As more nodes are 24 required, the array is dynamically expanded one block at a time. Each block i s referenced by an element in an array of pointers. Due to pointer precision, the maximum number of blocks is 780. This represents three megabytes of storage. As the maximum size of the array of pointers to blocks i s thus 780, the array is dynamically kept in v i r t u a l memory as well. The storage for primitive records i s organized in a dif f e r e n t fashion. Each record is a contiguous section of a large one-dimensioned array. When a graphical pointer i s negative, i t represents the negative index of the start of the primitive record in the array. This array is also dynamic; i t i s organized as blocks of 1024 words which are acquired when necessary. A record consists of a header, the primitive information, and a t r a i l e r . The header consists of one word; i t contains what type of primitive follows, garbage c o l l e c t i o n storage, and the length of the record. The word organization i s depicted in Figure 8. cd gb nnnn cd - Primitive style indicator 01 = POLYLINE 02 = POLYGON 03 = TEXTSTRING 04 = USER DEFINED PRIMITIVE gb - Garbage c o l l e c t o r storage nnnn - Length of record Figure 8 Primitive Record Header The primitive information depends on the type of primitive. For polylines and polygons, i t consists of groups of x,y, and z 25 coordinates. For textstrings, i t consists of bytes of character data. For user-defined primitives, i t consists of an external representation procedure pointer and a l i s t of parameters. The t r a i l e r i s either a continuation or an end command. If i t i s an end command, that is the end of the p r i m i t i v e . If i t i s a continuation command, i t contains a pointer to the part of the array where the primitive i s continued. This allows for records larger than 1024 words and for concatenation assignment. The following LIG6 program would create the primitive storage presented in Figure 9 which was produced by the system debug dump, LIGDPH. GRAPHICAL A,B,C A :- POLY FROM (1,2,3) TO (4,5,6) DELTA (3,3,3) B :- 'Line at' C :- A + LINE FROM (-1,2) TO (3,-4) B :+ ADDSTRING IVALUE(9+7,5) CALL LIGDPH STOP END Free l i s t s are kept for both nodes and primitive record areas. Whenever statements are executed which require the acqu i s i t i o n of storage, the storage is acquired from the appropriate free l i s t . If the free l i s t is empty, the garbage c o l l e c t o r i s invoked. If the amount of storage recovered by the c o l l e c t o r i s less than a set amount (42 nodes or 256 words of primitive storage), another page of v i r t u a l memory i s acquired and i n i t i a l i z e d . The garbage c o l l e c t o r operates as follows. Whenever a subprogram i s entered, a l l l o c a l graphical variables used are allocated nodes and a l i s t of those nodes is kept in a protect l i s t in v i r t u a l memory. The execution of a RETURN statement 26 Heap space dump - Address Contents 1 02000003 2 41100000 3 41200000 4 41300000 5 41400000 6 41500000 7 41600000 8 41700000 9 41800000 10 41900000 • 11 00000000 12 03000008 13 D3899585 14 4081A340 15 05000018 16 01000002 17 C1100000 18 41200000 19 00000000 20 41300000 21 C1400000 22 00000000 23 00000000 24 03000004 25 4040F1F6 26 00000000 27 07E50101 257 07FF0201 513 07FF0301 769 07FF0000 Page 1 Explanation Polygon x-component y-component z-component x-component y-component z-component x-component y-component z-component End String Text - Line Text - at Continuation Line x-component y-component z-component x-component y-component z-component End String Text - 16 End Free space Free space Free space Free space 3 vertices 0 . 1000000E+01 0 .2000000E+01 0 .3000000E+01 0 .4000000E+01 0 . 5000000E+01 0 .6000000E+01 0 .7000000E+01 0 .8000000E+01 0 .9000000E+01 8 characters located at 24 2 vertices -0.1000000E+01 0.2000000E+01 0.0 0.3000000E+01 -0.4000000E+01 0.0 4 characters 229 words, continued at 257 255 words, continued at 513 255 words, continued at 769 255 words, continued at 0 Figure 9 Primitive Record Storage causes those nodes to be removed from the protect l i s t . The garbage c o l l e c t o r starts from the protect l i s t and recursively marks the nodes which are defined by the l i s t . When t h i s mark phase is completed, a l l of the node and primitive storage is swept through with unmarked areas being added to the appropriate free l i s t . The d e t a i l s of the implementation of the data base and the operations which manage i t are hidden from a LIG6 programmer. The model of the data base provides enough information to e f f e c t i v e l y model and manipulate graphical objects using the advanced l e v e l constructs. 28 Chapter 4 GRAPHICAL OUTPUT PRIMITIVES Four graphical output primitives are supplied by LIG6: BLANK, POLYLINE, POLYGON, and TEXT. Th e o r e t i c a l l y , any image which can be displayed on an output device of f i n i t e precision can be created using these primitives, thus they form a complete set of atomic graphical objects. As a convenience, however, LIG6 also permits programmer-defined primitives. This can simplify modelling of well-defined graphical objects. 4.1 Primitives as Abstract Data Types In e a r l i e r versions of LIG [Schr76], primitives were viewed as constants of the data type GRAPHICAL. Six two-dimensional primitives were defined: BLANK, LINE, TRIANGLE, SQUARE, CIRCLE, and SCIRCLE (semi-circle). Only the f i r s t two were required; the rest could be constructed from the primitive LINE. The LINE primitive was defined as a l i n e segment from the point (0.0,0.5) to the point (1.0,0.5). A l l other l i n e segments were created by applying transformations to t h i s constant. Polylines were created by superimposing transformed l i n e segments. The view taken by the current version, LIG6, i s that primitives are data types in their own rig h t . For any data type supported by a language, rules exist which define how constants 29 of that type are expressed, also, operators which form legitimate expressions of that type are specified, and procedures are supplied which produce external representations of values of that type. Consider the data type COMPLEX. Its standard implementation is a record consisting of a real and an imaginary f i e l d each of type REAL. A FORTRAN complex constant consists of an opening parenthesis followed by a real constant representing the real f i e l d , a comma, a real constant representing the imaginary f i e l d , and a closing parenthesis. When operations are performed on t h i s type, the contents of the individual f i e l d s are used to determine the re s u l t . S p e c i f i c a l l y for output, the real part and the imaginary part are printed side by side. The primitive POLYLINE of the language LIG6, for example, has a l l of the features of an abstract data type. It is implemented by a record with a variable number of f i e l d s of type VECTOR. Each f i e l d represents a vertex in a l i n e and, on output, is accessed to generate the graphical commands given to the output device. While there are no direc t variables or operators for t h i s type, the type GRAPHICAL (which supports variables and operators) can be considered to contain a f i e l d which can reference p o l y l i n e s . The external representation procedures of conventional data types generally produce symbols on printers or terminals which have the same representation as constants of that type. A recursive PASCAL procedure for generating external representations of unsigned integers i s presented in Figure 10; i t has the above c h a r a c t e r i s t i c . This practice results from the 30 existence of a standard representation which can be used both in the s p e c i f i c a t i o n of a program and in the results generated by executing that program. There i s no rule that both representations must be the same; integers are often expressed in other bases or even as Roman numerals. This is the case with the type POLYLINE; such constants are expressed in programs with alphanumeric characters using d e f i n i t e syntactic rules while external representations are lines generated on graphical devices. The l a t t e r representation would probably be used for constants i f i t were av a i l a b l e . PROCEDURE ext_rep_integer( n : INTEGER ) ; BEGIN IF n < 10 THEN write ( CHR( n + ORD C O ' ) ) ) ELSE BEGIN ext_rep_integer( n DIV 10 ); write( CHR( n MOD 10 + ORD('O') ) ) END END; Figure 10 Integer External Representation The records of the data types POLYLINE, POLYGON, and TEXT can have a variable number of f i e l d s ; such data types are known as dynamic. Dynamic data types are not common as most programming languages do not support them. Both SNOBOL and BASIC, however, have dynamic s t r i n g data types. 4.2 Programmer Defined Primitives The d e f i n i t i o n of a primitive is equivalent to the creation of an abstract data type. The treatment of primitives by LIG6 31 requires that a data type d e f i n i t i o n includes constant s p e c i f i c a t i o n rules, internal representation information, and external representation procedures. The construct with which a programmer creates a LIG6 primitive i s a primitive d e f i n i t i o n unit. A primitive d e f i n i t i o n unit has a prescribed structure. F i r s t a symbolic name i s s p e c i f i e d for the primitive. A d e f i n i t i o n rule must follow in the form of a template which constants of that type w i l l match. The template consists of type declarations and a grammar production using a notation similar to Wirth's [Wirt77]. The remainder of the subprogram consists of statements which define a procedure for producing an external representation of values of that primitive. The internal representation is derived automatically from the constant d e f i n i t i o n rule. There are a variety of methods used to define grammars; Backus-Naur forms and syntax directed diagrams are two examples. Wirth's notation provides a general description mechanism which allows i t e r a t i o n , alternation, option, and recursion constructs to be expressed. The grammar production in a LIG6 primitive d e f i n i t i o n unit template uses a subset of t h i s notation since only alternation and option constructs are permitted. The allowable grammar productions can themselves be represented by a grammar; thi s i s presented in Figure 11 using Wirth's notation. In a LIG6 primitive template, an alternation construct i s a l i s t of templates separated by v e r t i c a l bars and enclosed by parentheses. An option construct i s a template enclosed by brackets optionally followed by the e x p l i c i t setting construct 32 production = p r i m i t i v e _ i d e n t i f i e r "::=" subtemplatelist ";" subtemplatelist = subtemplate { subtemplate } terminal = ( l i t e r a l _ s t r i n g | f i e l d _ i d e n t i f i e r ) l i t e r a l _ s t r i n g = '"" { ( character | " " " ) } '"" alternation = " ( " subtemplatelist { "|" subtemplatelist } " ) " option = " [ " subtemplatelist " ] " [ e x p l i c i t _ s e t t i n g ] e x p l i c i t _ s e t t i n g = "<" setting { "," setting } ">" setting = f i e l d _ i d e n t i f i e r "=" expression nonterminal = p r i m i t i v e _ i d e n t i f i e r " ( " { character } " ) " Figure 11 Allowable Primitive Template Grammar Productions which defines the default. The nonterminal construct allows the insertion .of the template of a previously defined primitive. The characters in the l i s t following the i d e n t i f i e r are appended to a l l of the f i e l d i d e n t i f i e r s of the previously defined primitive when i t i s inserted. This allows multiple use of the primitive in a template. A template which demonstrates alternation and option constructs and constants which match i t are presented in Figure 12. A template which demonstrates the use of nonterminals and constants which match i t are shown in Figure 13. The body of the primitive d e f i n i t i o n unit defines the external representation procedure for that data type. It consists of statements which, based upon the values of the f i e l d s of the data type, produce images on output devices. The body may contain any type of statement except those which deal with graphical modelling or display. These statements are excluded because they deal with information at a higher l e v e l . subtemplate = ( terminal option nonterminal alternation e x p l i c i t _ s e t t i n g 33 PRIMITIVE SQUARE LOGICAL FILL REAL SIDE VECTOR CENTRE SQUARE ::= 'SQUARE' [ 'FILLED' <FILL=.TRUE.> ]<FILL=.FALSE.> [ ( 'AT' CENTRE [ ',SIDE' SIDE ]<SIDE=1.0> | 'SIDE' SIDE [ ',AT' CENTRE ]<CENTRE=(0,0,0)> ) ] <CENTRE=(0,0,0),SIDE=1,0> ; SQUARE SQUARE FILLED SQUARE AT (5.1,5,0) SQUARE FILLED SIDE 3.0 SQUARE AT (3,2.7,6), SIDE 0.5 SQUARE FILLED SIDE 3*PI, AT (V1#V2) Figure 12 Square Primitive PRIMITIVE ONEARG INTEGER OPT VECTOR V ONEARG ::= ( <OPT=1> <OPT=4> 'SW <OPT=7> 'S' ' = ' V ; NW <OPT=2> 'NE' <OPT=5> 'N' <OPT=8> 'W <OPT=3> 'SE* <OPT=6> 'E' <OPT=9> 'C PRIMITIVE PARALL INTEGER OPT1, OPT2, OPT3 VECTOR V1, V2, V3 PARALL ::= 'PARALLELOGRAM' ONEARG(1) ',' ONEARG(2) ',' ONEARG(3) ; PARALLELOGRAM N=(2,3,4),C=(5,2,2),SE=(X,Y,Z) PARALLELOGRAM NW=(1,1,1),NE=(5,2,2),SW=(X,Y,Z) Figure 13 Parallelogram Primitive Two statements are provided which cause output to occur, the DRAW and DRAW WITH statements. The form of the draw statement is the keyword DRAW followed by a previously defined primitive, either one of the four basic primitives or one which was programmer-defined. A complete primitive d e f i n i t i o n unit for a square primitive follows. 34 PRIMITIVE SQUARE REAL SIDE SQUARE ::= 'SQUARE' SIDE ; DRAW LINE FROM ( 0 , 0 ) TO (0,SIDE) TO (SIDE,SIDE) TO (SIDE ,0) TO ( 0 , 0 ) RETURN END Whenever a model whose s p e c i f i c a t i o n includes a SQUARE primitive i s displayed, the external representation procedure i s invoked. A l l of the modelling transformations and attribute settings of the model affect the procedure. In addition to primitives, appropriate concatenation expressions may follow the DRAW keyword. An example of thi s usage is PRIMITIVE CIRCLE CIRCLE ::= 'CIRCLE' ; REAL PI/3. 1 41 593/ DRAW LINE FROM (1,0) DO 20 I = 1,100 THETA = I*Pl/50 DRAW ADDLINE (COS(THETA),SIN(THETA)) 20 CONTINUE RETURN END Concatenation expressions may only be executed i f the last DRAW statement executed was a concatentation or primitive of the same type. Attributes of the draw statement may be changed with the DRAW WITH statement. Its form i s the keyword DRAW WITH followed by a l i s t of attribute settings enclosed in angle brackets. Any attribute which has not been spec i f i e d in the modelling may be set by such a statement. Programmer-defined primitives permit e f f i c i e n t and concise modelling of regular or parameterized graphical objects. An example of a primitive which models spheres constructed with 35 arbitrary resolution and illuminated by an arb i t r a r y l i g h t source i s presented in Figure 14. 4.3 Graphical Functions Versus Graphical Primitives S t r i c t l y speaking, the c a p a b i l i t y of programmer d e f i n i t i o n of graphical output primitives i s not necessary. Any graphical effect which such a primitive can produce can also be produced by a function of type GRAPHICAL. The differences between primitives and graphical functions are subtle. Graphical functions are executed as soon as they are invoked, returning a model of a graphical object. Such models require memory space for storage and have structures and values which can be subsequently manipulated. An invocation of a primitive, on the other hand, does not result in execution of code. The parameters of the primitive are stored and i t i s not u n t i l the value of that primitive i s to be displayed that the external representation procedure is invoked. This results in savings in both memory and execution time. The decision whether to use a primitive or a graphical function, therefore, should be made using the following guidelines. If the resulting object i s always treated as a unit or i f it. contains curves or subobjects which can be eas i l y parameterized, then a primitive implementation should be considered. If an object has a d e f i n i t e structure and hierarchy and subparts of i t w i l l be accessed and possibly modified, a graphical function implementation should be considered. 36 PRIMITIVE SPHERE INTEGER RES,PATERN VECTOR LIGHT,LSORCE,P1,P2,P3,P4,TX,TY,TZ,NORM SPHERE ::= 'SPHERE' RES ',* LIGHT ; PI = ATAN(1.)*4 ARC = PI/RES LSORCE = LIGHT/|LIGHT| TX = (1,0,0) TY = (0,COS(ARC),SIN(ARC)) TZ = (0,-SIN(ARC),COS(ARC)) DO 10 I = 1,RES PI = (1,0,0) P3 = PI DO 10 J = 1,RES P2 = (COS(J*ARC),SIN(J*ARC)*COS(l*ARC), SIN(J*ARC)*SIN(I*ARC)) P4 = ((P2.TX),(P2.TY),(P2.TZ)) NORM = PI + P2 + P3 + P4 COSANG = (NORM.LSORCE)/|NORM| PATERN = 0 IF(COSANG.GT.O) PATERN = 24.*COSANG + 1.5 DRAW WITH <PATTERN PATERN> DRAW POLY FROM (P1) TO (P2) TO (P4) TO (P3) PI = P2 P3 = P4 10 CONTINUE RETURN END Figure 14a Sphere Primitive D e f i n i t i o n Figure 14b Sphere Primitive Output 37 Programmer-defined graphical output primitives have been used in other languages but with d i f f e r e n t terminology and emphasis. E a r l i e r versions of LIG had a construct c a l l e d a graphical function [Schr78]. Its effect was to store the arguments and a pointer to the function in the data base. It was only when a model which contained a reference to the function was displayed that the function was executed. This d i f f e r s markedly from the standard concept of a function which i s supported by LIG6. LIG6 graphical functions are executed immediately upon their invocation and return a model of a graphical object. The early version functions were in fact an implementation of programmer-defined primitives although they lacked the generality of the current implementation. They had a maximum of six parameters, were invoked by a fixed structure, and could only draw l i n e s , not a l l previously defined pri m i t i v e s . The actual syntax d e f i n i t i o n provided by LIG6 was not permitted. The language MIRA allows the d e f i n i t i o n of graphical types tThal79,Magn81]. The language implementation of these types, however, i s more in l i n e with graphical functions. The type declaration includes modelling operations, not display commands. The type i s invoked via a procedural construct, not by assignment statements containing constants of the type. The modelling process occurs immediately upon invocation requiring storage and execution time; i t i s not delayed u n t i l an instance is actually displayed. In addition, the pattern matching f a c i l i t y of LIG6 i s not available. 38 Chapter 5 GRAPHICAL DOMAINS There are many domains in which graphical programming languages may be applied, but use of a pa r t i c u l a r graphical programming language w i l l be limited i f the domains in which i t can be applied are r e s t r i c t e d . High-level graphical languages provide simply-expressed constructs for the d e f i n i t i o n and external representation of graphical data. These constructs allow such languages to be applied to domains at the drafting systems l e v e l . More sophisticated applications, however, require the analysis of ar b i t r a r y graphical data. The L I G 6 constructs which provide inquiry and manipulation of graphical data permit the language to be applied in a variety of interesting domains; four of these w i l l be discussed using a L I G 6 example for each. 5.1 Construction Tools Due to the large quantity of data involved in most graphics applications, the e x p l i c i t d e f i n i t i o n of graphical objects is often tedious and time consuming. Graphical application programs must capture as much regularity of the input data as possible to allow economy of gesture in the modelling process. This can be achieved with the aid of construction tools in the form of procedures which create models of complex graphical objects with 39 minimal input. An example of two construction tools which would be useful in a ductwork application is given in Figure 15. Both could find application in other contexts where regular surface generation i s required. The procedure EXTRUD takes as input an a r b i t r a r y cross- section and a d i r e c t i o n and length specified as a vector. The cross-section i s extruded as s p e c i f i e d by the vector, generating a column. The procedure REVOLV takes as input an a r b i t r a r y cross-section, an axis sp e c i f i e d by two points, an angle, and a step parameter. The cross-section i s revolved around the axis by the angle specified in the given number of steps, generating a 3-D figure. Three system procedures are invoked. PRILEN returns the number of vertices of a polyline or polygon primitive, LINPNT returns the sp e c i f i e d vertex of a l i n e primitive, and APLYMD applies the transformations stored in a graphical node to a point, returning the transformed value. Other construction tools which would complement the above two would be procedures to join two d i s s i m i l a r cross-sections or to compute s o l i d intersections. A complete ductwork application program might include a systematic manipulation procedure which would analyze any models generated and produce patterns for sheet metal construction of the piping. Figures 16 through 19 show two views each of two graphical objects constructed using the EXTRUD and REVOLV procedures. 40 GRAPHICAL FUNCTION EXTRUD(XSECT,DIREC) GRAPHICAL XSECT VECTOR DIREC,OLD,NEW INTEGER ORDER,PRILEN EXTRUD :- BLANK ORDER = PRILEN(XSECT) CALL LINPNT(XSECT,1,OLD) DO 10 I=2,ORDER CALL LINPNT(XSECT,I,NEW) EXTRUD :- EXTRUD + POLY FROM (OLD) TO (OLD+DIREC) TO (NEW+DIREC) TO (NEW) OLD = NEW 10 CONTINUE RETURN END 10 20 GRAPHICAL FUNCTION REVOLV(XSECT,AXIS1,AXIS2,DEGRES,STEPS) GRAPHICAL XSECT,MODSTR,ONEARC,MDSTR1 VECTOR AXIS1 ,AXIS 2,OLD,NEW,OLD1 ,NEW1 REAL DEGRES INTEGER STEPS,ORDER,PRILEN MODSTR :- BLANK < MAP (AXIS1),(AXIS2) TO (0,0,0),(0,0,1) , ROTZ DEGRES/STEPS 'DEG' , MAP (0,0,0),(0,0,1) TO (AXIS1),(AXIS2) > ONEARC :- BLANK ORDER = PRILEN(XSECT) CALL LINPNT(XSECT,1,OLD) CALL APLYMD(MODSTR,OLD,OLD1) DO 10 I = 2,ORDER CALL LINPNT(XSECT,I,NEW) CALL APLYMD(MODSTR,NEW,NEW1) ONEARC :- ONEARC + POLY FROM TO OLD = NEW OLD1 = NEW1 CONTINUE REVOLV :- BLANK MDSTR1 :- BLANK DO 20 I = 1,STEPS REVOLV :- REVOLV + ONEARC < MODIFICATION(MDSTR1) MDSTR1 :- MDSTR1 < MODIFICATION(MODSTR) > CONTINUE RETURN END (OLD) TO (NEW) (NEW1) TO (OLD1) Figure 15 Graphical Ductwork Construction Tools 5.2 Systematic Manipulation Systematic manipulation of graphical objects i s performed by procedures which process a graphical model of arbit r a r y 41 Figure 17 Second View of Pipe Figure 18 Helix Constructed With REVOLV Figure 19 Second View of Helix 43 structure and content. Such procedures permit application programs to perform modelling at various levels of d e t a i l . An example of systematic manipulation i s the substitution of one subobject for another in an arb i t r a r y graphical object. To demonstrate LIG6's a b i l i t y to implement systematic manipulation procedures, a deep replace algorithm i s presented in Figure 20. The problem is divided into two parts. A general double recursion subroutine RECURS performs recursive manipulation of models of graphical objects. The parameter TREE i s the model which i s to be manipulated. The parameter FIRST sp e c i f i e s a graphical function which controls the f i r s t recursion. The parameter WORK speci f i e s a subroutine which performs the desired manipulation whenever FIRST returns a stopping condition. The parameter SECOND specifies a graphical function which controls the second recursion. The second part comprises four routines which set up RECURS to perform deep replacement. The graphical functions DEEP1 and DEEP2 correspond to FIRST and SECOND, respectively. The subroutine SWAP corresponds to WORK. The subroutine DREPLC invokes RECURS specifying the above parameter assignments. The result of a c a l l to DREPLC i s shown in Figure 21. In a graphical object representing a s h i f t r e g i s t e r , the graphical symbols for RS f l i p flops were replaced by their logic gate representations. Due to the h i e r a r c h i c a l nature of graphical data, recursive manipulation of models i s desirable. Because LIG6 i s an extension to FORTRAN, however, recursive routines are not permitted. This can be overcome ea s i l y with routines such as RECURS. Other examples of uses of RECURS are copying trees, 44 SUBROUTINE RECURS(TREE,WORK,FIRST,SECOND) GRAPHICAL TREE,FIRST,SECOND,STACK(25),VALUE,SUPER INTEGER POINT POINT = 1 STACK(1) :- TREE 10 POINT = POINT + 1 STACK(POINT) :- FlRST(STACK(POINT-1)) IF ( .NOT. PRIMITIVE(VALUE(STACK(POINT))) .AND. POINT .NE. 25 ) GOTO 10 POINT = POINT - 1 CALL WORK(STACK,POINT) 20 STACK(POINT) :- SECOND(STACK(POINT)) IF ( .NOT. PRIMITIVE(VALUE(STACK(POINT))) ) GOTO 10 POINT = POINT - 1 IF ( POINT .NE. 0 ) GOTO 20 RETURN END GRAPHICAL FUNCTION DEEP 1 (NODE) GRAPHICAL NODE,REPLAC,WITH,VALUE,SUPER COMMON /$REPL$/ REPLAC,WITH DEEP1 = VALUE(VALUE(NODE)) IF ( VALUE(NODE) .NE. VALUE(REPLAC) ) RETURN DEEP 1 = BLANK RETURN END GRAPHICAL FUNCTION DEEP2(NODE) GRAPHICAL NODE,REPLAC,WITH,VALUE,SUPER COMMON /$REPL$/ REPLAC,WITH DEEP2 = SUPER(VALUE(NODE)) IF ( VALUE(NODE) .NE. VALUE(REPLAC) ) RETURN DEEP2 = BLANK RETURN END SUBROUTINE SWAP(STACK,POINT) GRAPHICAL STACK(25),REPLAC,WITH,VALUE,SUPER INTEGER POINT COMMON /$REPL$/ REPLAC,WITH IF ( POINT .EQ. 1 ) RETURN IF ( VALUE(STACK(POINT)) .NE. VALUE(REPLAC) ) RETURN VALUE(STACK(POINT-1)) :> VALUE(WITH) RETURN END SUBROUTINE DREPLC(TREE,OUT,IN) GRAPHICAL TREE,OUT,IN,REPLAC,WITH,DEEP1,DEEP2 COMMON /$REPL$/ REPLAC,WITH EXTERNAL SWAP,DEEP1,DEEP2 REPLAC :- OUT WITH :- IN CALL RECURS(TREE,SWAP,DEEP1,DEEP2) RETURN END Figure 20 Deep Replace Algorithm 45 SHIFT REGISTER F i g u r e 21 G r a p h i c a l S u b s t i t u t i o n f l a t t e n i n g t r e e s , and r e v e r s i n g the order of s u p e r p o s i t i o n at any l e v e l . 5.3 G r a p h i c a l E d i t i n g L i n e f i l e e d i t o r s are used to manipulate programs, data, and t e x t . The s t r u c t u r e and content of the data i n a f i l e i s m o d i f i e d by e d i t o r commands which d e l e t e , a l t e r , or i n s e r t i n f o r m a t i o n . An analogous form of m a n i p u l a t i o n can be performed on g r a p h i c a l data. An i n t e r a c t i v e g r a p h i c a l e d i t o r has been implemented using the a b i l i t y of LIG6 to analyze and modify models of g r a p h i c a l o b j e c t s . The program generates a v i s u a l r e p r e s e n t a t i o n of the s t r u c t u r e and content of the model being generated. The r e p r e s e n t a t i o n i s analogous to a l i s t i n g of a f i l e . With the a i d 46 of the representation, the model can be manipulated using editor commands. The v i s u a l representation produced i s a drawing of the tree structure of the model. The branches of the tree correspond to the pointers of the model. Within each node of the tree an image of i t s graphical value is displayed. Using the locator input of the terminal, the model i s manipulated by moving pointers, specifying modelling transformations at nodes, inserting or deleting nodes, and other editing functions. As the model is manipulated, corresponding changes in the v i s u a l representation occur. The audit t r a i l of a sample editing session i s given in Figures 22 through 30. Figure 22 i s the image of the o r i g i n a l model and Figure 23 is i t s tree structure representation. The result of adding to part of the structure i s shown in Figure 24. At any time, any portion of the model can be displayed in f u l l s i z e . The graphical value of the previous addition i s displayed in Figure 25. The tree representation i s shown only to a limited depth and breadth. Any portion of the model can be displayed, however, by moving a leaf of the representation to the root position. This i s demonstrated in Figure 26, enabling part,of the model to be manipulated, the structure of which was previously not v i s i b l e . Figure 27 shows the structure of the subobject after i t has been modified. After editing at t h i s l e v e l is complete, the structure including the o r i g i n a l root is redrawn, resulting in Figure 28. 47 Al t e r i n g the structure of the model i s demonstrated by Figure 29. Two top le v e l superimposed objects are grouped together so that modelling transformations can be applied in p a r a l l e l . The f i n a l result of the manipulation by editing i s shown in Figure 30. The editing process is independent of the graphical object being manipulated. E l e c t r i c a l diagrams, a r c h i t e c t u r a l drawings, or artwork can be edited by the same program in the same manner that programs in various languages or data f i l e s can be manipulated by a l i n e f i l e editor. Figure 22 Original Model Image 48 Figure 23 Original Tree Structure 49 Figure 26 Editing Level Change Figure 27 Subobject Modification Figure 28 Original Root Redrawn Figure 29 Structure Alt e r a t i o n Figure 30 Graphical Editing Result 52 5.4 Data Structures PASCAL allows programmers to e x p l i c i t l y define their own data types and structures. This promotes good programming practice because an understanding is required of the data involved in a problem. FORTRAN does not permit data type d e f i n i t i o n s . LIG6 permits e x p l i c i t d e f i n i t i o n of data types belonging to the class graphical output primitive, but ar b i t r a r y data types cannot be e x p l i c i t l y defined. The tree structure of the graphical data base, however, allows i m p l i c i t d e f i n i t i o n of data types and structures in a similar fashion as the language LISP. Data types and structures can be i m p l i c i t l y defined in LISP by interpreting the structure of a l i s t as i t s data type. Different data types can be spec i f i e d by the length of a l i s t of that type, which elements of the l i s t are atoms or l i s t s , or what data type a l i s t element i s interpreted to be. The tree structures of LIG6 can be used in the same way as the l i s t structures of LISP to define data types i m p l i c i t l y . An example which uses the graphical data base of LIG6 to represent the abstract data of a grammar w i l l now be presented. The goal of the program i s to take a grammar specified in Backus-Naur form and produce an equivalent grammar s p e c i f i c a t i o n in the form of syntax directed diagrams. This is achieved by storing the grammar, manipulating i t s representation, and generating an external representation in the form of a diagram. Grammar driven compiler writing systems [McKe70,Leca74] often do not allow i t e r a t i o n , alternation, or option constructs 53 in the grammar s p e c i f i c a t i o n . Such constructs must be implemented by the top le v e l alternation construct and by recursive d e f i n i t i o n , allowing the grammar to consist of only two types of symbols: terminals and non-terminals. The same r e s t r i c t i o n i s enforced by the program. The input grammar, however, i s analyzed and manipulated so that the resulting diagrams have i t e r a t i o n , low-level alternation, and option structures. Three data types are required to allow storage of the grammar: terminals, non-terminals, and str u c t u r a l elements. The graphical data base structures which are interpreted as representing these types are shown in Figure 31. In addition, the two variables TRMLST and NTRLST are used to maintain a record of a l l of the terminals and non-terminals of the grammar, respectively. The structures of their values are also given in Figure 31. As the grammar i s read in, an internal representation using TRMLST, NTRLST, and the three data types i s constructed. If the input grammar i s the simple d e f i n i t i o n <subprogramlist> ::= <subprogram> | <subprogramlist> <subprogram> , then the internal representation given in Figure 32 would be constructed. This structure does not represent the simplest equivalent grammar because the d e f i n i t i o n i s using recursion to implement i t e r a t i o n . The i n i t i a l internal representation of any grammar w i l l have to be manipulated to produce a structure which u t i l i z e s i t e r a t i o n , alternation, and option constructs. The internal representation after manipulation of the above grammar 54 Type STRUCTURAL ELEMENT Is d e f i n e d by — t e r m i n a l s , n o n - t e r m i n a l s , or elements P o i n t e d at by these elements Followed by these elements Type NON-TERMINAL TEXT Poi n t e d at by these elements Is d e f i n e d by these elements Type TERMINAL TEXT TRMLST NTRLST Po i n t e d at by these elements t e r m i n a 1 s n o n t e r m i n a 1 s F i g u r e 31 Grammar Storage Data Types and V a r i a b l e s i s given i n F i g u r e 33. Once the d e s i r e d grammar r e p r e s e n t a t i o n has been c r e a t e d , i t i s f u r t h e r manipulated so that i t becomes a model of the g r a p h i c a l o b j e c t , the syntax d i r e c t e d diagram. The l i t e r a l s 55 NTRLST | *• * <subprogramlist> <subprogram> ••-3 •+-4 ->2 F i g u r e 32 O r i g i n a l Grammar I n t e r n a l R e p r e s e n t a t i o n r e p r e s e n t i n g the grammar symbols are p o s i t i o n e d and connected with l i n e s and arrows as s p e c i f i e d by the d e f i n i t i o n p o i n t e r s . A 56 NTRLST <subprogramlist> J <subprogram> -*-2 F i g u r e 33 Manipulated Grammar I n t e r n a l R e p r e s e n t a t i o n more complete grammar and i t s r e s u l t i n g diagram i s shown i n F i g u r e s 34 and 35, r e s p e c t i v e l y . The g r a p h i c a l data base of LIG6 lends i t s e l f to problems where dynamic data s t r u c t u r e s are i n v o l v e d . Another p o s s i b l e use would be the implementation of a minimal LISP i n t e r p r e t e r i n LIG6 which c o u l d produce v i s u a l r e p r e s e n t a t i o n s of any s- ex p r e s s i o n s i n the standard cons c e l l format of LISP. <program> ::= <subprogramlist> <subprogramlist> <main> <subprogramlist> <main> <subprogramlist> <main> <main> <subprogramlist> <subprogramlist> ::= <subprogram> | <subprogramlist> <subprogram> <subprogram> ::= <subroutine> <function> <primitivedef> <blockdata> <subroutine> ::= <subhead> <block> | <subhead> <parameterlist> <block> <function> ::= <funchead> <parameterlist> <block> <subhead> ::= SUBROUTINE <identifier> <funchead> ::= FUNCTION <identifier> | <type> FUNCTION <identifier> <type> ::= INTEGER REAL COMPLEX LOGICAL GRAPHICAL VECTOR Figure 34 Sample Input Grammar 58 program s u b p r o g r a n l l s t naln s u b p r o g r a n l l s t subprogranllst » i subprogram TJ s u b p r o g r a n —1 F u n c t i o n s u b r o u t i n e M prisiltivedef M '—4 b i o c k d a t a s u b r o u t i n e —( S U B R O U T I N E )—• i d e n t i f i e r — I — p a r a i i e t e r l l s t —L("block — function type —r-< INTEGER") type M—( FUNCTIONj-*| I d e n t i f i e r pH parameterllst H b l o c k f ^ -{ RERL ) - ( COHPLEX ) — - ( LOGICBL ) — ( GRAPHICAL )-*| ( VECTOR ) F i g u r e 3 5 Sample S y n t a x D i r e c t e d D i a g r a m 59 Chapter 6 NEW LANGUAGE FEATURES Apart from the s h i f t of emphasis from a system where the data base is completely hidden from users to a data base model system and the addition of programmer-defined primitives, there have been a number of other new features included in the language LIG6. These features have varying degrees of o r i g i n a l i t y ; some were not available in e a r l i e r LIG versions but were available elsewhere to some extent, while others have not been published or implemented previously. The new features include graphical operators, interpretation decisions, and language constructs. 6.1 Vector Data Type To provide economy of expression when dealing with three dimensional data, the data type VECTOR was included in LIG6. Simple variables, single and multi-dimensioned array variables, function subprograms, and statement functions of type VECTOR are permitted. Vector variables may be typed e x p l i c i t l y , or else i m p l i c i t l y with the aid of the IMPLICIT statement. Vector expressions may be passed as arguments to subprograms. Vector variables may be equivalenced and placed in COMMON blocks. They may not be i n i t i a l i z e d in a type declaration or in a DATA 60 statement nor may they be output or input as a unit with WRITE or READ statements. Vector constants are of the form (X,Y,Z) where X, Y, and Z represent arithmetic expressions and where the parentheses are mandatory. The Z expression i s optional; i f missing, i t defaults to 0.0. Vector variables may be assigned values which are vector expressions. The operators which are defined for the type VECTOR are summarized in Figure 36. OPERATOR EXAMPLE OPERATION RESULT TYPE + V1 + V2 vector addition VECTOR V1 - V2 vector subtraction VECTOR # VI # V2 vector cross product VECTOR V1 . V2 vector dot product REAL | | |V| vector magnitude REAL * A * V m u l t i p l i c a t i o n by scalar VECTOR / V / A d i v i s i o n by scalar VECTOR .EQ. V1 .EQ. V2 vector comparison LOGICAL '.NE. V1 .NE. V2 vector comparison LOGICAL Figure 36 Vector Operators The program fragment presented in Figure 37 i l l u s t r a t e s the use of the VECTOR data type. While the inclusion of operators and nested expressions allow concise implementation of vector arithmetic algorithms, the major use of this data type w i l l be in graphical primitives. Access to the individual components of vectors i s provided by the three LIG6 system functions, COORDX, COORDY, and COORDZ. The individual components may be assigned using the above i d e n t i f i e r s using an assignment statement construct. Component access i s demonstrated in the program fragment of Figure 38. The VECTOR data type was not supported in e a r l i e r FORTRAN 61 VECTOR FUNCTION CROSS(X,Y,N) IMPLICIT VECTOR(V,X-Z) VECTOR A,B(5),T(2,3),Y(N),FUNC GRAPHICAL D DIMENSION A(3) COMMON V1 rV2(3,4) EQUIVALENCE ( B ( 3 ) , A ( D ) VFUNC(XV,YV,ZV) = XV.YV#ZV A(1) = (FUNC(3,Q) + X)/(5.+Q) CALL TEST(3*A(2)#V2) IF(X#Y(1).EQ.Y(2)#Z/4) CROSS = (COS(R),SIN(R)) D :- LINE FROM (1.5,3.2) TO (V2(2,I)#(Y(1)+Y(3))) Figure 37 Vector Data Type Usage VECTOR V,V1 RVAL = COORDX(V) + 3*COORDZ(V) COORDY(V) = 3.2 + COORDX(V1#(P,Q,R) + V) Figure 38 Vector Component Access versions of LIG. It is possible to declare a PASCAL vector type in the LIG/P implementation, but operators and natural inclusion in graphical primitives are not possible. The language MIRA supports the data type vector, but the only operators permitted are addition and dot product [Magn8l], 6.2 Map Operator In addition to the standard graphical transformations scale, rotate, and translate-, LIG6 provides a map operator. This transformation operator can be used to perform any combination of scaling, rotation, t r a n s l a t i o n , and shearing. Its syntax i s the keyword MAP followed by a l i s t of 1, 2, 3, or 4 points, the keyword TO, and another l i s t of points. The two l i s t s of points must each have the same length. Each point may be a vector 62 constant or a vector expression which i s enclosed in parentheses. The implementation of the map operator i s as straightforward as i t s invocation: the operator creates a linear transformation which maps the points in the f i r s t l i s t into those in the second. The points in the l i s t s need not have any relation to coordinates of the model to which the transformation is applied, although this i s one form of the operator's use. Careful choice of the points in the l i s t s w i l l create any of the standard graphical transformations. The map operator also provides a concise method for expressing shearing transformations. Combining the map operator with the standard transformations f a c i l i t a t e s the construction of interesting transformations. Examples of the map operator which demonstrate these points are given in Figure 39. i) <MAP ( 0 , 0 ) , ( 1 , 0 ) TO (0,0),(COS(THETA),SIN(THETA))> i i ) <MAP (V1),(V2) TO (V1),(V1 + S*(V2-V1))> i i i ) <MAP (1 , 0 ) , ( 0 , 0 ) , ( 0 , 1 ) TO (1,0) , (0 ,0),(-COS(T),SIN(T))> iv) < MAP (V1),(V2) TO ( 0 , 0 ) ,(|V1-V2| , 0 ) , ROTX THETA , MAP ( 0 , 0 ) ,(|V1-V2| , 0 ) TO (V1),(V2) > Figure 39 Map Operator Examples In Figure 39, example (i) produces a transformation equivalent to a rotation about the z-axis by an amount THETA. Example ( i i ) performs scaling with respect to the point V1 in the d i r e c t i o n V2-V1 by a quantity S. Example ( i i i ) w i l l cause shearing by an angle T about the z-axis. Example (iv) i l l u s t r a t e s compounding transformation operators. Its effect, i s 63 to rotate objects by an amount THETA about the axis sp e c i f i e d by the l i n e passing through the points V1 and V2. A l l LIG6 transformations use matrices to produce the desired e f f e c t . The coordinate t r i p l e s of an object which i s to be transformed are converted into homogeneous coordinates [Roge76] and then multiplied by a matrix; the resulting coordinates represent the transformed object. Compounded transformations are created by multiplying matrices. A matrix which rotates objects about the z-axis i s presented in Figure 40. cos ( a ) -sin ( a ) 0 0 X p sin ( o ) cos ( a ) 0 0 y - Q 0 0 1 0 z R 0 0 0 1 1 1 Figure 40 Z-Rotation Matrix The linear transformation which implements the map operator i s the solution of a matrix equation. The matrix A of Figure 41 i s the transformation which implements the map operator of the same figure. The matrix A is found by solving an equation of the type B (1 ) One solution i s - i - l X (2) however, this involves finding the inverse of a matrix and then <MAP (a,b,c),(d,e,f),(g,h,i),(j,k,l) TO (m,n,o),(p,q,r),(s,t,u),(v,w,x) > 64 m P s V n q t w o r u X L JL 1 ' ' ' J I ' 1 1 1 J Figure 41 Map Operator Implementation multiplying. Another solution i s to take the transpose of both sides of equation 1 yie l d i n g equation 3. The transpose of A can then be solved for by using a LU decomposition which has been shown to involve fewer operations [Fors67], p -, T T I- -] T X A = B (3) There i s a unique linear transformation which maps a given set of four points in three-dimensional space to another set. When the other variants of the map operator are used, however, there i s not a unique solution. A l l solutions achieve the mapping objective, but they d i f f e r in their effect on points which are not in the plane s p e c i f i e d by the three member variant, points not on the l i n e s p e c i f i e d by the two member variant, or points other than the one spec i f i e d by the one member variant. The solution chosen for these variants is the one that minimizes the d i s t o r t i o n of graphical objects. For the one member variant map operator, the choice i s simple: the equivalent translation transformation i s used. The two and three member variant map operators are implemented by choosing additional appropriate points and solving as for the 65 four member variant. The three points in a l i s t of a three member variant define an o r i g i n and two vectors. The fourth point chosen i s the cross product of the two vectors. This generates a t h i r d vector perpendicular to the plane defined by the points in the l i s t . Its length is determined by the lengths of the two o r i g i n a l vectors. When the same process of fourth point s p e c i f i c a t i o n i s applied to both l i s t s , any scaling or shearing in the plane i s applied naturally to points off the plane. The two points in a l i s t of a two member variant define an or i g i n and a vector. A t h i r d point is a r b i t r a r i l y chosen which generates a vector which i s of the same magnitude as and i s perpendicular to the o r i g i n a l vector. The same procedure as for the three member variant i s then followed. 6.3 Stroke Precision Text There are three lev e l s of text appearance precision: s t r i n g , character, and stroke precision text [GSPC79]. In str i n g precision text, only the position of the f i r s t character of a stri n g may be specified; the size and orientation of the str i n g i s hardware dependent. In character precision text, the position of every character of the st r i n g i s affected by transformations but the size and orientation of the individual characters are s t i l l hardware dependent. Stroke precision text treats strings as i f each character were constructed from short l i n e s ; a l l transformations apply to such str i n g s . The differences between the precisions are summarized in Figure 42. 66 DIAGONAL D <V 1 X O N A L s t r i n g c h a r a c t e r s t r o k e F i g u r e 42 Text P r e c i s i o n The use of s t r i n g or c h a r a c t e r p r e c i s i o n t e x t i n images of models of three-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 y i e l d s poor r e s u l t s . The p r e c i s e p o s i t i o n i n g and o r i e n t a t i o n of t e x t s t r i n g s r e q u i r e s s t r o k e p r e c i s i o n c a p a b i l i t y ; LIG6 has t h i s c a p a b i l i t y . A l l images of s t r i n g s are generated using software because most hardware generators are capable of only s t r i n g p r e c i s i o n t e x t . F i g u r e 43 g i v e s an example of some of the p o s s i b i l i t i e s of str o k e p r e c i s i o n t e x t . 6.4 S t r u c t u r e d Statements As software c o s t s i n c r e a s e r e l a t i v e to hardware c o s t s , more e f f o r t i s made to ensure that programs are c o r r e c t , readable, and m a i n t a i n a b l e . Programs with these q u a l i t i e s are most e a s i l y produced when a r i g o r o u s c o n s i s t e n t programming s t y l e i s used. A s t y l e which has developed a c o n s i d e r a b l e f o l l o w i n g i n recent years i s c a l l e d S t r u c t u r e d Programming [Dahl72]. The c o n s t r u c t s of a language have an e f f e c t on the s t y l e i n which programmers c r e a t e programs i n that language. FORTRAN i s one of the o r i g i n a l h i g h - l e v e l programming languages; i t l a c k s the s t r u c t u r e d c o n t r o l c o n s t r u c t s a v a i l a b l e i n more modern languages such as PASCAL [Jens76]. S t r u c t u r e d programming i n 67 Dodecahedron A 8 V ,o<3. 0 F i g u r e 43 Stroke P r e c i s i o n Text FORTRAN has been accomplished by i n t e r p r e t i n g groups of statements as c o n t r o l s t r u c t u r e s and r e s t r i c t i n g the usage of statement l a b e l s and the GOTO statement. In an e f f o r t to promote a s t r u c t u r e d , modular programming s t y l e , more modern implementations of FORTRAN such as FORTRAN'77 [Meis77] or WATFIV/S [ F r i e 8 2 ] have i n c l u d e d s t r u c t u r e d c o n t r o l c o n s t r u c t s . LIG6 extends the c o n t r o l c o n s t r u c t s of FORTRAN with the a d d i t i o n of four s t r u c t u r e d c o n s t r u c t s . These c o n s t r u c t s are an 68 IF-THEN-ELSE structure, a REPEAT structure, a WHILE structure, and a CASE structure. The syntactic rules of these constructs are formally defined by the grammar presented in Figure 4 4 . Use of these constructs is demonstrated in the program fragments in Figure 4 5 . <statementblock> ::= BEGIN <statementlist> END <statementlist> ::= <statement> <statseparator> | <statementlist> <statement> <statseparator> <statseparator> ::= <eol> I ; <structuredif> ::= <truepart> | <truepart> <falsepart> <truepart> ::= IF ( <logicalexpr> ) THEN <statementblock> <falsepart> ::= ELSE <statementblock> <repeat> ::= REPEAT <statementlist> UNTIL ( <logicalexpr> ) <while> ::= WHILE ( <logicalexpr> ) DO <statementblock> <case> ::= CASE <expression> : <type> OF <caseexpr> <caseexpr> ::= <truelist> <truelist> <falselist> <falselist> <truelist> ::= <success> | <truelist> <success> <falselist> ::= '<>' : <statementblock> <success> ::= <exprlist> : <statementblock> <exprlist> ::= <expression> | <exprlist> <expression> Figure 44 Structured Statements Grammar A l l structured constructs may be nested to any depth. The requirement of statement l i s t s being bracketed by BEGIN and END ensures that a l l syntactic structures are completely 69 IF(X.LT.Y) THEN BEGIN T=X; X=Y; Y=T; END IF(3**J.GT.2**K) THEN BEGIN J=0; K=1 END ELSE BEGIN K=0; J=1 END REPEAT READ(5,10)1 CALL DUM(I*3) UNTIL(I.GT.32) WHILE(J.LT.10) DO BEGIN END CASE R*T/(5.+Q) : INTEGER OF 2,3 : BEGIN END <> : BEGIN CASE 5*Q : REAL OF R/Q : BEGIN END END { REAL CASE } END END { INTEGER CASE } Figure 45 Structured Statements Examples unambiguous. 6.5 Archivation Graphical application programs are often executed i n t e r a c t i v e l y in order to construct models of graphical objects. This process i s usually time-consuming and i t i s d i f f i c u l t for a user to repeat model s p e c i f i c a t i o n s exactly. To create menus or to continue modelling begun in previous executions of a program, i t is, necessary that a r b i t r a r y models can be stored and retrieved. This i s implemented in LIG6 by archivation. Archivation i s the saving on and restoring from secondary 70 storage models of graphical objects. It can be used to pass models between di f f e r e n t programs or to save generated models for a subsequent run of the same program. There are three statements which are involved with archivation: the STORE statement, the POSITION statement, and the LOAD statement. There are two forms of the store statement. Some examples of this type of statement are STORE ON UNIT 7,BIRD STORE ON UNIT N+2,FOWL STORE ON UNIT 3, VALUE(LAST(A)) STORE ON UNIT 3,. IDENTIFICATION 7.5, A STORE ON UNIT 3, IDENTIFICATION 3*R, A The integer valued expression following the keyword UNIT i s the l o g i c a l I/O unit on which the model is stored. It must be assigned to a disk f i l e on the run command or with a FORTRAN I/O subprogram. The real valued expression following the keyword IDENTIFICATION i s a number which i s placed in the header of the stored model in the f i l e so that i t can be i d e n t i f i e d l a t e r . The default value for the i d e n t i f i c a t i o n i s 0.0. The last item in the l i s t i s a graphical variable or function invocation whose value i s a node. The effect of the statement i s to store at the end of the f i l e a header and codes which represent the model which i s the value of the last item. The archivation f i l e i s in the form of a sequential tape. Each additional object is placed at the end of the tape. When they are la t e r loaded, the loading w i l l occur in the same order as the order in which they were stored. A certain degree of random access can be obtained, however, with the position statement. The position statement i s used to position an archivation 71 f i l e at the desired model storage. Examples of possible forms of this statement follow. POSITION UNIT 2 POSITION UNIT N+3,5.5 POSITION UNIT 3,4.*Q POSITION UNIT 3,7.2,2 POSITION UNIT 3,,2 The f i r s t arithmetic expression in the l i s t following the keyword i s the unit expression; i t must be integer valued and has the same meaning as in the store statement. The second expression i s the i d e n t i f i c a t i o n expression; i t must be real valued. The t h i r d expression i s the version expression; i t must be integer valued. The default value for the i d e n t i f i c a t i o n expression i s 0.0. The default value for the version expression is 0. The ef f e c t of the statement i s tp position the archivation f i l e attached to the unit at the spec i f i e d version of the i d e n t i f i c a t i o n value. The fourth statement in the examples above w i l l position the f i l e at the model storage of the second instance of a model being stored with i d e n t i f i c a t i o n 7.2. If the version number i s 0, the last model stored with the spec i f i e d i d e n t i f i c a t i o n i s the point at which the f i l e i s positioned. The default i d e n t i f i c a t i o n value of 0.0 w i l l match a l l i d e n t i f i c a t i o n values, thus the l a s t statement w i l l position the f i l e to the second model stored, while the f i r s t statement w i l l position the f i l e to the last model stored. The load statement i s used to restore a model. The model stored in the archivation f i l e at i t s present position i s loaded into the graphical variable s p e c i f i e d . An example i s LOAD FROM UNIT N+2, BIRD 72 Chapter 7 CONCLUSIONS E a r l i e r versions of LIG preprocessors did not analyze the host language statements of a program. LIG6, the research topic of t h i s thesis, analyzes both the FORTRAN and language extension statements. The primary reason for thi s i s that the language constructs of LIG6 cannot be ea s i l y s p l i t up into those which are s t r i c t l y FORTRAN and those which are s t r i c t l y extensions. There i s considerable overlap between the constructs, as i s evident by the number of FORTRAN statements which may contain extension elements. Several benefits are rea l i z a b l e when-all statements are analyzed. There i s no need to demarcate extension statements by the use of a special character in a designated column or by other means. It is possible to mix host and extension statements on a single l i n e . Any syntactic errors in the host language statements which would not normally be detected u n t i l the preprocessor output i s compiled are trapped. The preprocessor i s moved one step closer to being a compiler; object code generation i s only possible when complete parsing i s performed. Another difference between LIG6 and previous LIG versions i s the implementation of the preprocessor. The LIG6 preprocessor does not make use of a Compiler Writing System (CWS); i t i s written completely in PASCAL. There are several factors 73 supporting t h i s choice. Currently available compiler writing systems [McKe70,Leca74] do not support the free form input conventions of FORTRAN; delimiters and reserved words are required. With a CWS, i t i s not possible to carry out language extensions which are defined by programmers. Such extensions require a dynamically a l t e r a b l e parser; CWS generated parsers are determined solely by the o r i g i n a l grammar s p e c i f i c a t i o n s . LIG6 programmer-defined primitives include the d e f i n i t i o n of syntactic constructs which aff e c t the parser. The LIG6 preprocessor i t s e l f can thus be thought of as a load and go CWS. Because a CWS must be able to handle general grammars, i t cannot generate preprocessors which exploit characterstics of a s p e c i f i c grammar. A preprocessor created without the use of grammar driven aids i s not limited in this way; i t can u t i l i z e ad hoc techniques which provide more e f f i c i e n t execution. Current research in computer graphics appears to be concentrated in two d i s t i n c t areas. A great deal of e f f o r t has been expended regarding standards for graphical subroutine systems [GSPC79,Fole76]. Such systems are used to create portable graphics application programs but they do not provide modelling features. The other area of intense interest i s the creation of r e a l i s t i c images. This area contains hidden l i n e and surface removal, shadowing, shading, and texturing algorithms. The research in this area is concerned with the process of analyzing scenes, not with the models on which the analysis i s based. High-level graphical programming languages are an extension to graphical subroutine systems. They provide a data base and 74 the c a p a b i l i t y to naturally model graphical objects. It i s only with the addition of inquiry, however, that such a language can form a bridge between the two areas of current research. A high- l e v e l language can f a c i l i t a t e the modelling of graphical objects, but constructs must be available which allow the analysis of those models i f complex graphical algorithms are to be implemented. The data base approach of LIG6 permits the analysis of a r b i t r a r y models of graphical objects. Use of LIG6 to perform experiments with graphical algorithms allows the scenes required to be modelled naturally. Any algorithms so devised and implemented are then available for use in a l l LIG6 application programs. A language can be considered to have been expanded when a f a c i l i t y i s provided which was previously unavailable. An example of such a f a c i l i t y for FORTRAN is the system function MAX which returns the maximum value of i t s variable number of parameters. These f a c i l i t i e s are usually implemented by a systems programmer because the language constructs do not permit their d i r e c t implementation. This i s exemplified by MAX: FORTRAN has no method of . specifying a variable number of formal parameters. It is possible for non-systems programmers to expand a language, however, i f the language's constructs form a kernel which i s complete in i t s a b i l i t y to manipulate the language's data structures. The language constructs of LIG6 provide such a kernel. A l l possible data base values can be created using the various assignment statements and a l l modelling results can be accessed 75 and modified. The surface generation construction tools and the editing u t i l i t y described in Chapter 5 form language extensions which use only LIG6 modules. The a b i l i t y of non-systems programmers to expand LIG6 implies that the system w i l l be able to evolve much faster. L i b r a r i e s of routines which are useful in general applications can be augmented by any person fluent in the language. Heavily used f a c i l i t i e s can s t i l l be coded by a systems programmer to improve e f f i c i e n c y ; such a task w i l l be s i m p l i f i e d by the exist i n g algorithm implementation in the high-level constructs. The a b i l i t i e s of LIG6 compare favorably with those of other high-level graphics languages. The modelling and display functions of LIG6 have benefitted from the experience gained from the use of previous versions of the LIG family. They provide a natural and human-oriented method of displaying p i c t o r i a l information. The advanced l e v e l constructs of LIG6 permit the analysis of p i c t o r i a l information; t h i s a b i l i t y i s not available with any other graphics language using graphical constructs. An evaluation of LIG6 can be derived from the experiences of a summer student. In the summer of 1982, a second-year e l e c t r i c a l engineering undergraduate was hired to create a graphics interface to a c i r c u i t analysis program. This student's previous programming experience consisted of a f i r s t - y e a r computer science course dealing with FORTRAN and ASSEMBLER and job-related experience using a microcomputer and BASIC. He had no previous graphics experience. After a short period in which the student became familiar with graphical terms and concepts, 76 he was e a s i l y able to produce graphical output using LIG6. The task for which the student was hired, however, e n t a i l s more than the generation of images. It involves the creation of a maintainable, expandable program using the graphical data base to generate both an image of an a r b i t r a r y c i r c u i t and a s p e c i f i c a t i o n of that c i r c u i t which can be understood by the analysis program. Although encouraging results were obtained, th i s work proceeded more slowly. Two conclusions can be drawn from t h i s experience: only minimal programming experience i s needed to use LIG6 to produce graphical output, but more programming s k i l l s are required to use the advanced l e v e l constructs of LIG6 to implement sophisticated algorithms. Experience with the design and manipulation of dynamic data structures, pointers, and linked l i s t s i s especially useful. Such experience is common in programmers familiar with the languages PASCAL and LISP. As i s the case with most projects, further work would be b e n e f i c i a l . The implementation of LIG6 has proceeded to the point where i t i s a useful graphical system. The preprocessor and run-time l i b r a r y are complete and have been tested. Further work to improve the system involves increasing the number and c a p a b i l i t i e s of the device d r i v e r s . The language LIG6 assumes that a l l devices have the same, high quality c a p a b i l i t i e s . This is far from the case. It i s the task of the device drivers to approximate or simulate those features expected by LIG6 but which are lacking in the device addressed. At the present time, the drivers support only a subset of the features expected by the system. 77 The only colour terminal presently connected to the system is a Tektronix 4027. This terminal is capable of displaying. 0 eight of a possible sixty-four colours at any one time. The eight colours currently chosen are white, blue, magenta, red, yellow, green, cyan, and black. An approach y i e l d i n g more r e a l i s t i c results would be for the driver- to choose the eight colours which best matched the intended image. There are two d i s t i n c t problems involved in using a varying palette of colours. The f i r s t is to devise a metric so that a numerical value can be associated with the difference between two colours. This requires research into the way the eye perceives colour. A possible metric is to use the red, blue, green (RBG) colour model and assume the colour axes are orthogonal and of equal length. Once the palette, of colours has been determined, the metric is used to choose which colour of the palette best approximates the colour an application program wishes to display. The second problem i s the choice of palette members after a screen refresh. At that time, a l l of the colours which w i l l appear on the screen are known. The optimum palette choice is the one where the sum of the errors is minimized. The error involved i s the distance between the colour desired and the closest colour of the palette as defined by the metric. As there are sixty-four choose eight (roughly 4.4*109) possible palettes, an exhaustive search i s not p r a c t i c a l . A possible h e u r i s t i c i s to consider each palette colour as a data concentrator, each desired colour as a terminal, the metric value between colours 78 as the terminal-concentrator link cost and to use the Add or Drop algorithms from communications theory [Schw77] to determine concentrator location / palette colour. There are many monochromatic devices. Two such devices interfaced to LIG6 are Tektronix 4010 series terminals and a p l o t t e r . The current implementation displays a l l colours in the foreground colour of these devices. A possible improvement would be the approximation of colour on these devices by the use of hatching. Several options could be implemented. The hatching could be performed in image space with the result that a l l images of surfaces with the same colour would have the same orientation and spacing of hatch l i n e s . Secondly, the orientation of the surfaces of the model could be used to determine the orientation of the hatching of the image. The hatching could also be performed in object space resulting in both the orientation and spacing of the hatch l i n e s being affected. The last two implementations would provide the viewer with additional information regarding depth and the modelling process. The portrayal of three-dimensional information i s usually more meaningful i f hidden l i n e s and surfaces are removed. As LIG6 is concerned with the modelling and display of three- dimensional objects, the addition of a hidden l i n e and surface removal c a p a b i l i t y would be an important improvement. It would be possible to place these algorithms in the driver part of the system because such algorithms are usually dependent on the output device. For example, a p r i o r i t y buffer algorithm [Fole82] can be used with raster terminals but not with dir e c t view 79 storage tubes or p l o t t e r s . Most terminal locators provide only two-dimensional information. Interacting with an image of a three-dimensional object i s d i f f i c u l t because there is no method to indicate depth. It i s possible to implement a three-dimensional locator for a vector refresh terminal using three valuator inputs. Three cross-hairs would be drawn p a r a l l e l to the axes of the modelling coordinate system through a point determined by the valuator inputs. Experiments could be c a r r i e d out to determine i f f i n i t e length cross-hairs or cross-hairs which include measuring t i c k marks are required to a s s i s t a user's depth perception. 80 BIBLIOGRAPHY [Bart8l] Barth, W., J. Dirnberger, and W. Purgathofer, The high- le v e l graphics programming language PASCAL/GRAPH, Proc. Eurographics 81, Amsterdam, North-Holland, 1981, 151- 1 64. [Dahl72] Dahl O-J., D i j k s t r a , E. W. , Hoare, C., Structured Programming, Academic Press, New York, '1972. [Dijk76] D i j k s t r a , E. W., A D i s c i p l i n e of Programming, Prentice- H a l l , Inc., Englewood C l i f f s , New Jersey, 1976. [Fole76] Foley, J. D., Picture Naming and Modification: an Overview, Computer Graphics 10, Spring 1976, pp. 49-53. [Fole82] Foley, J. D., Van Dam, A., Fundamentals of Interactive Computer Graphics, Addison-Wesley, Reading, Massachusetts, 1 982. [Fors67] Forsythe, G. E., Moler, C. B., Computer Solutions of Linear Algebraic Systems, Prentice-Hall, Inc., Englewood C l i f f s , New Jersey, 1967. [Frie82] Friedman, F. L., Koffman, E. B., Problem Solving and Structured Programming in WATFIV, Addison-Wesley, Reading, Massachusetts, 1982. [GSPC79] Heilman, R., Herzog, B. (Eds.), Status Report of the Graphics Standards Planning Committee, Computer Graphics 13, No. 3, August 1979. [Jens76] Jensen, K., Wirth, N., PASCAL: User Manual and Report, Springer-Verlag, New York, 1976. [Kuls68] Kulsrud, H.E., A general purpose graphic language, Comm. ACM, 11 (1968), 247-254. [Leca74] Lecarme, 0., and G.V. Bochmann, A (truly) usable portable compiler writing system, Information Processing 74, Amsterdam, North-Holland, 2(1974), 218-221. [Magn8l] Magnenat-Thalmann, N., and D. Thalmann, A graphical Pascal extension based on graphical types, Software — Practice and Experience, 11 (1981), 53-62. 81 [Mair8l] Mair, S. G. (Ed.), UBC IG: The Integrated Graphics System, Computing Centre, The University of B r i t i s h Columbia, 1982. [Mann80] Mannhardt, Ch., and G.F. Schrack, Modelling and display concepts in a high-level graphics programming language, C.E. Vandoni, Ed., Eurographics 80, Amsterdam, North- Holland 1980, 225-236. [McKe70] McKeeman, W.M., J. J . Horning, and D.B. Wortman, A Compiler Generator, Englewood C l i f f s , Prentice-Hall, 1970. [McLe78] McLean, M.J., A survey of interactive graphics software, Austral. Comput. J., 10 (1978), 11-22. [Meis77] Meissner, L. P., FORTRAN 77, SIGPLAN Not. (USA), v o l . 12, no. 1 (Jan. 1977), pp. 93-94. [Newm7l] Newman, W.M., Display procedures, Comm. ACM, 14 (1971), 651-660. [Roge76] Rogers, D. F., Adams, J. A., Mathematical Elements for Computer Graphics, McGraw-Hill, New York, 1976. [Ross82] Ross, R., LIG6; Language for Interactive Graphics, User's Manual, Department of E l e c t r i c a l Engineering, The University of B r i t i s h Columbia, 1982, 55 pp. [Schr76] Schrack, G.F., Design, implementation and experiences with a high-level graphics language for interactive computer-aided design purposes, Computer Graphics, 10 (Spring 1976) and SIGPLAN Notices, 11(June 1976), 10-17 (joint issue). [Schr78] Schrack, G.F., LIG User's Manual, Departments of E l e c t r i c a l Engineering and Computer Science, The University of B r i t i s h Columbia, 1978, 50 pp. [Schw77] Schwartz, M., Computer-Communicat ion Network Design and Analysi s, Prentice-Hall, Inc., Englewood C l i f f s , New Jersey, 1977. [Smit7l] Smith, D.N., GPL/l — A PL/I extension for computer graphics, AFIPS Conf. Proc. 38 (1971: SJCC), 511-528. [Thal79] Thalmann, D., Magnenat-Thalmann, N., Design and Implementation of Abstract Graphical Data Types, Proc. COMPSAC'79, Chicago, IEEE Press, 1979, pp. 519-524. [Wirt77] Wirth, N., What can we do about the unnecessary d i v e r s i t y of notation for syntactic d e f i n i t i o n s ? , Comm. ACM, 20 (1977), 822-823. 82 APPENDIX A A Sample Program The LIG6 program shown on the f o l l o w i n g pages demonstrates the a b i l i t y of the language t o implement i n t e r e s t i n g g r a p h i c a l a l g o r i t h m s . The g r a p h i c a l f u n c t i o n HIDDEN i s an example of a p r i o r i t y b u f f e r h idden s u r f a c e removal a l g o r i t h m i m p l e m e n t a t i o n . I t r e t u r n s a model which i s e q u i v a l e n t t o i t s argument but whose s t r u c t u r e has been m o d i f i e d so t h a t when i t i s d i s p l a y e d on a r a s t e r r e f r e s h t e r m i n a l , the hidden l i n e s and s u r f a c e s w i l l not appear. 83 GRAPHICAL FUNCTION HIDDEN(TREE) GRAPHICAL TREE,ROOT,STACK(25),TRAVRS,VALUE,SUPER INTEGER POINT VECTOR VUPNT,AIMPNT,VIEWUP REAL VUANGL COMMON /HID$/ VUPNT CALL CAMPRM(VUPNT,AlMPNT,VIEWUP,VUANGL) ROOT :- BLANK <COLOUR -1E35> POINT = 1 STACK(1) :- TREE REPEAT IF(VALUE(STACK(POINT)).EQ.BLANK) THEN BEGIN POINT = POINT - 1; END ELSE BEGIN IF(PRIMITIVE(VALUE(STACK(POINT)))) THEN BEGIN CALL INSERT(ROOT,STACK(POINT)) POINT = POINT - 1 END ELSE BEGIN IF(POINT.EQ.25) THEN BEGIN STACK(POINT) :- SUPER(VALUE(STACK(POINT))) <MODIFI CATION(STACK(POINT))> END ELSE BEGIN STACK(POINT+1) :- VALUE(VALUE(STACK(POINT))) <MODIFICATION(VALUE(STACK(POINT))), MODIFICATION(STACK(POINT))> STACK(POINT) :- SUPER(VALUE(STACK(POINT))) <MODIFICATION(STACK(POINT))> POINT = POINT + 1 END END END UNTIL (POINT.EQ.O) HIDDEN = TRAVRS(ROOT) RETURN END SUBROUTINE INSERT(ROOT,NODE) GRAPHICAL ROOT,NODE,POINTR,FATHER,COPY,VALUE,SUPER REAL AVERGE,DEPTH POINTR :- ROOT FATHER :- BLANK DEPTH = AVERGE(NODE) WHILE(DEPTH .LT. COLOUR(VALUE(POINTR))) DO BEGIN FATHER :- VALUE(POINTR) POINTR :- SUPER(VALUE(POINTR)) END IF(VALUE(FATHER) .EQ. BLANK) THEN 84 BEGIN ROOT :< COPY(ROOT) ROOT :> COPY(NODE)<COLOUR DEPTH> END ELSE BEGIN VALUE(FATHER) :< (COPY(NODE) <COLOUR DEPTH>) SUPER(VALUE(FATHER)) :< VALUE(POINTR) END RETURN END GRAPHICAL FUNCTION COPY(NODE) GRAPHICAL NODE COPY := NODE RETURN END REAL FUNCTION AVERGE(NODE) GRAPHICAL NODE,VALUE INTEGER ORDER,PRILEN VECTOR VUPNT,POINT,POINT1 COMMON /HID$/ VUPNT AVERGE = 0 . 0 IF(VALUE(NODE).EQ.BLANK) RETURN IF(POLYLINE(VALUE(NODE))) THEN BEGIN ORDER = PRILEN(NODE) DO 10 I = 1,ORDER CALL LINPNT(NODE,I,POINT) CALL APLYMD(NODE,POINT,POINT1) AVERGE = AVERGE + |VUPNT-POINT1| 10 CONTINUE AVERGE = AVERGE/ORDER END ELSE BEGIN IF(POLYGON(VALUE(NODE))) THEN BEGIN ORDER = PRILEN(NODE) DO 20 I = 1,ORDER CALL POLPNT(NODE,I,POINT) CALL APLYMD(NODE,POINT,POINT1) AVERGE = AVERGE + |VUPNT-POINT1| 20 CONTINUE AVERGE = AVERGE/ORDER END ELSE BEGIN POINT = ( 0 ,0 ) CALL APLYMD(NODE,POINT,POINT1) AVERGE = |VUPNT-POINT 1 | END END RETURN 85 END GRAPHICAL FUNCTION TRAVRS(ROOT) GRAPHICAL ROOT,POINTR,VALUE,SUPER TRAVRS = VALUE(ROOT) IF(TRAVRS .EQ. BLANK) RETURN POINTR :- ROOT WHILE(VALUE(VALUE(POINTR)) .NE. BLANK) DO BEGIN VALUE(VALUE(POINTR)) :< VALUE(SUPER(VALUE(POINTR))) POINTR :- SUPER(VALUE(POINTR)) END RETURN END 86 APPENDIX B Implementation Notes The language LIG6 i s implemented on the U n i v e r s i t y of B r i t i s h Columbia Computing Centre's Amdahl 470 V/8 computer under the Michigan Terminal System (MTS) o p e r a t i n g system. The f o l l o w i n g MTS commands w i l l generate the pr e p r o c e s s o r and run- time l i b r a r y and execute a LIG6 program c o n t a i n e d i n the f i l e PROG.S. $RUN *PASCAL SCARDS=LIG6.P SPUNCH=LIG6.0 $RUN *FTN SCARDS=LIG6.LIB.F SPUNCH=LIG6.LIB.O $RUN LIG6.0 SCARDS=PROG.S SPRINT=PROG.L SPUNCH=PROG.F $RUN *FTN SCARDS=PR0G.F SPUNCH=PROG.0 $RUN PR0G.0+LIG6.LIB.0 The f o l l o w i n g "T" diagrams, u s i n g the n o t a t i o n of McKeeman et a l . [McKe70], represent the same proc e s s . LIG6 PREPROCESSOR LIG6 PREPROCESSOR LIG6 --> FORTRAN LIG6 --> FORTRAN PASCAL COMPILER PASCAL PASCAL — > ML ML ML 87 LIG6 LIBRARY LIG6 LIBRARY FORTRAN COMPILER FORTRAN FORTRAN --> ML ML ML Program Program Program LIG6 PREPROCESSOR FORTRAN COMPILER LIG6 LIG6 — > FORTRAN FORTRAN FORTRAN - - > ML ML ML ML S e v e r a l s t a t i s t i c s r e g a r d i n g the implementation of LIG6 have been o b t a i n e d . The prep r o c e s s o r was w r i t t e n i n PASCAL; i t c o n s i s t s of 328 procedures t o t a l l i n g 18,100 l i n e s of source code. T h i s r e p r e s e n t s a l i s t i n g of over 300 pages and occupies a d i s k f i l e c o n t a i n i n g 168 pages (each d i s k page c o n t a i n s 4096 b y t e s ) . The o b j e c t code r e s u l t i n g from the c o m p i l a t i o n of the pre p r o c e s s o r source r e q u i r e s a d i s k f i l e of 84 pages. I t takes 0.413 seconds of CPU time t o l o a d . A 650 l i n e LIG6 t e s t program c o n t a i n i n g examples of a l l s y n t a c t i c c o n s t r u c t s took 3.449 seconds of CPU time and c o s t $1.08 f o r the preprocessor to analyze the program, c r e a t e an e q u i v a l e n t 1660 l i n e FORTRAN 88 program, and produce a l i s t i n g . In comparison, the cost of l i s t i n g the same program was $0.50. The translation of a LIG6 program into an equivalent FORTRAN program involves the replacement of extension constructs with c a l l s to subroutines in a run-time l i b r a r y . The concise graphical information in a LIG6 statement generally requires more than one subroutine c a l l to be equivalently expressed. The actual expansion that occurs depends upon the program being preprocessed. In the test program mentioned above, the section dealing with purely graphical extensions was 134 lines long. The equivalent FORTRAN code, was 530 l i n e s , an expansion factor of 3.96. A LIG6 program which was used to automatically generate the data structure diagrams of thi s thesis i s 197 lines long; i t s equivalent FORTRAN code i s 364 li n e s y i e l d i n g an expansion factor of 1.85. The hidden surface removal algorithm of Appendix A i s 145 l i n e s long; i t s equivalent FORTRAN code i s 428 lines y i e l d i n g an expansion factor of 2.95. The run-time l i b r a r y was written in FORTRAN; i t consists of 339 procedures t o t a l l i n g 10,232 l i n e s of source code. This represents a l i s t i n g of 166 pages and occupies a disk f i l e of 95 pages. The resulting object code requires a 70 page disk f i l e and takes 0.402 seconds of CPU time to load.

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 7 28
Japan 4 0
United States 2 0
France 1 0
City Views Downloads
Beijing 5 0
Tokyo 4 0
Shenzhen 2 28
Unknown 1 18
Mountain View 1 0
Ashburn 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}

Share

Share to:

Comment

Related Items