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 Ross, Robert Vaughan 1982

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

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
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
Original Record: 1.0095574 +original-record.json
Full Text
1.0095574.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 U n i v e r s i t y  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 E n g i n e e r i n g )  We accept t h i s t h e s i s as conforming to the r e q u i r e d  standard  THE UNIVERSITY OF BRITISH COLUMBIA June 1982 ©  Robert Vaughan Ross, 1982  In p r e s e n t i n g  t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of  requirements f o r an advanced degree at the  the  University  o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make it  f r e e l y a v a i l a b l e f o r reference  and  study.  I  further  agree t h a t p e r m i s s i o n f o r e x t e n s i v e copying o f t h i s t h e s i s f o r s c h o l a r l y purposes may department or by h i s or her  be granted by  the head o f  representatives.  my  It is  understood t h a t copying or p u b l i c a t i o n o f t h i s t h e s i s f o r f i n a n c i a l gain  s h a l l not be  allowed without my  permission.  Department O f  E l e c t r i c a l Engineering  The U n i v e r s i t y o f B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date  DE-6  (3/81)  July 22,  1982  written  ABSTRACT  High-level expressed  graphical  programming  constructs  for  the  languages  definition,  provide  manipulation,  e x t e r n a l r e p r e s e n t a t i o n of g r a p h i c a l data. Such languages used to c r e a t e e f f e c t i v e and thesis  investigates  the  simply  can  and be  readable a p p l i c a t i o n programs. T h i s  value  of  allowing  the  inquiry  of  g r a p h i c a l data i n a g r a p h i c a l language.  Major design goals of an  implementation  these  of  a  language  presented. A data base model and The  classification  of  with  capabilities  implementation  graphical  primitives  are  are  discussed.  as a b s t r a c t data  types i s presented. Examples are given of s e v e r a l areas i n which a language i n c l u d i n g g r a p h i c a l i n q u i r y may concluded  that  of a r b i t r a r y implementation  be  applied.  i n q u i r y permits the d e f i n i t i o n and  models  of  graphical  objects,  so  It  is  manipulation enabling  of s o p h i s t i c a t e d g r a p h i c a l a l g o r i t h m s .  the  iii  TABLE OF CONTENTS Page  LIST OF FIGURES  v  ACKNOWLEDGEMENTS  vii  Chapter 1. INTRODUCTION  1  2. LANGUAGE DESIGN GOALS  4  2 . 1 Inquiry  4  2.2  L e v e l s Of Usage  5  2.3  F o r t r a n Consistency  8  2.4  Separate  P r e p r o c e s s i n g And  Compilation i  3. DATA BASE SYSTEM  10 12  3.1  Data Base Model  14  3.2  Data Base Implementation  22  4. GRAPHICAL OUTPUT PRIMITIVES  28  4.1  P r i m i t i v e s As A b s t r a c t Data Types  28  4.2  Programmer Defined P r i m i t i v e s  30  4.3  G r a p h i c a l Functions Versus  35  5. GRAPHICAL DOMAINS  G r a p h i c a l P r i m i t i v e s ...  38  5.1  Construction Tools  38  5.2  Systematic  40  5.3  Graphical Editing  45  5.4  Data S t r u c t u r e s  52  6. NEW  Manipulation  LANGUAGE FEATURES  59  iv  0* 6.1 V e c t o r D a t a Type 6.2 Map O p e r a t o r 6.3 S t r o k e P r e c i s i o n 6.4 S t r u c t u r e d  '  59 61  Text  65  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 - I m p l e m e n t a t i o n  86  Notes  V  LIST OF FIGURES  Figure  1  Data Base Model  15  Figure 2  VALUE And SUPER Functions  16  Figure 3  Nested G r a p h i c a l Expressions  18  Figure 4  Copy Assignment  20  Figure 5  Value Assignment  20  Figure 6  Super Assignment  21  Figure 7  G r a p h i c a l Node S t r u c t u r e  23  Figure 8  P r i m i t i v e Record Header  24  Figure 9  P r i m i t i v e Record Storage  26  Figure  10  Integer  E x t e r n a l Representation  Figure  11  Allowable  Figure  12  Square P r i m i t i v e  32  Figure  13  Parallelogram Primitive  33  Figure  14  Sphere P r i m i t i v e  36  Figure  15  G r a p h i c a l Ductwork C o n s t r u c t i o n Tools  40  Figure  16  A r b i t r a r y Pipe Model  41  Figure  17  Second View Of Pipe  41  Figure  18  H e l i x Constructed  42  Figure  19  Second View Of H e l i x  42  F i g u r e 20  Deep Replace Algorithm  44  F i g u r e 21  Graphical Substitution  45  F i g u r e 22  O r i g i n a l Model Image  47  F i g u r e 23  O r i g i n a l Tree S t r u c t u r e  48  P r i m i t i v e Template Grammar Productions  With REVOLV  30 33  vi  F i g u r e 24  Graphical Editing Addition  48  F i g u r e 25  Viewing E d i t i n g Result  49  F i g u r e 26  E d i t i n g L e v e l Change  49  F i g u r e 27  Subobject M o d i f i c a t i o n  50  F i g u r e 28  O r i g i n a l Root Redrawn  50  F i g u r e 29  Structure A l t e r a t i o n  51  F i g u r e 30  Graphical E d i t i n g Result  51  F i g u r e 31  Grammar Storage Data Types And V a r i a b l e s  54  Figure  O r i g i n a l Grammar I n t e r n a l Representation  55  32  F i g u r e 33  Manipulated  Grammar I n t e r n a l Representation  F i g u r e 34  Sample Input Grammar  57  F i g u r e 35  Sample Syntax D i r e c t e d Diagram  58  F i g u r e 36  Vector Operators  60  F i g u r e 37  Vector Data Type Usage  61  F i g u r e 38  Vector  61  F i g u r e 39  Map Operator Examples  62  F i g u r e 40  Z-Rotation  Matrix  63  F i g u r e 41  Map Operator Implementation  64  F i g u r e 42  Text  66  F i g u r e 43  Stroke  F i g u r e 44  S t r u c t u r e d Statements Grammar  F i g u r e 45  S t r u c t u r e d Statements Examples  Component Access  Precision P r e c i s i o n Text  .... 56  67 68 ' 69  vi i  ACKNOWLEDGEMENTS  I  would  Schrack my  like  t o e x p r e s s my s i n c e r e a p p r e c i a t i o n  f o rh i s invaluable help  parents  for their  support  w o u l d n o t have been p o s s i b l e support Council.  of  the  National  and guidance.  I am  t o D r . Gunther grateful  and encouragement. T h i s  were  i t not  Science  and  to  research  f o r the  financial  Engineering  Research  1  Chapter 1 INTRODUCTION There  has  presentation applied  always  been  considerable  of i n f o r m a t i o n i n p i c t o r i a l  interest  in  the  form. As computers are  i n an i n c r e a s i n g number of areas and more information i s  s t o r e d i n machine-readable form, the demand generation  of  graphical  images  computer g r a p h i c s i s concerned  also with  for  the  automatic  i n c r e a s e s . The f i e l d of the  generation  of  such  images. Most programmers' i n i t i a l involves  graphical  experience  subroutine  graphical  input  and  graphics  systems. The major task of these  systems i s to a c t as an i n t e r f a c e between and  with computer  output  g e n e r a l l y do not provide modelling  application  devices.  The  functions, this  programs  subroutines is left  as  a  task of the a p p l i c a t i o n program. Modelling  functions  programming ' languages. information constructs GRAPHICAL.  are These  provided languages  consider  graphical  to be values of an a b s t r a c t data type. They provide which  define  High-level  advantages over  subroutine  and  manipulate  graphics  data  languages  of  the  possess  type  several  systems: high p o r t a b i l i t y of programs  and programmers, ease of l e a r n i n g readability  by h i g h - l e v e l g r a p h i c s  the  language,  and  improved  of a program. T h i s t h e s i s d i s c u s s e s some aspects of  the design and implementation  of such a language.  The  name  of  2  this  language  6).  It  is  i s LIG6 the  (Language  most  [Schr76,Mann80], w i t h During have  the past  been  in  y e a r s , many h i g h - l e v e l or proposed,  et  [McLe78]  languages d i f f e r  discusses widely  The  modelling  explicit  definition  objects.  This permits  constructs  graphics.  of  the  It  be  applied  is  et a l . [Bart8l]. a  survey.  The  as w e l l as  these  languages  of  models  allow the  of  graphical  programs t o perform  of  p a s s i v e or  f o r programs  models  nature  of  these  i n these  graphical  objects  models. T h i s  i n w h i c h a g r a p h i c s programming  when a f o r m a l  recently,  and s e m a n t i c s ,  difficult  arbitrary  diverse  i n v e s t i g a t e s areas  of  application  in  more  implementation.  manipulation  languages t o manipulate because  languages  for their  and  and B a r t h  syntax  languages  i n p a p e r s by K u l s r u d  [ S m i t 7 l ] , and,  37  i n both  graphics  notably  a l . [Magn8l],  the approaches taken  interactive  v e r s i o n of a f a m i l y of languages  [Newm7l], S m i t h  Magnenat-Thalmann  Version  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 .  described  [ K u l s 6 8 ] , Newman  McLean  recent  f o r I n t e r a c t i v e Graphics  thesis  language  model s t r u c t u r e and i n q u i r y  into  can such  structures are provided. LIG6  i s i m p l e m e n t e d a s an e x t e n s i o n  FORTRAN. programs  A  preprocessor,  into  translated These to  standard  into  subroutines  be  output  Only  implementation  the  to  a  host  PASCAL,  subroutines  in  details  deck  extension  i n a run-time  produced  conjunction of  the  which a r e p e r t i n e n t t o the  language,  converts  i n FORTRAN. When a LIG6  object  i s run  those  in  FORTRAN p r o g r a m s w i t h  a r e coded  executed,  preprocessor library.  calls  written  to  LIG6  elements library.  program  is  by c o m p i l i n g t h e  with  language points  the and  run-time of i t s  discussed  in  3  this in  t h e s i s are  the  LIG6 U s e r ' s Manual  Chapter The  o u t l i n e d ; more c o m p l e t e  overall  language  2  presents  style  and  compilation  of  the  partitioning  of  is available  [Ross82]. t h e major d e s i g n  the  language  importance  of modules  information  with  of  Aspects  constructs  of  respect  separate  i s considered.  language  goals  into  the  language.  to  the  host  preprocessing  and  of  i n q u i r y and  the  a  hierarchy  are  addressed. The 3.  The  are  concept  of a d a t a  b e n e f i t s of programmer  d i s c u s s e d . A model of  implementation Chapter primitives  are  as  true  define  presented graphical graphical  to  6.  An  effective  support text  is  abstract of  for  the  is described,  graphical  objects  the  i d e a of  in  b a s e and  data  a  implementation  summary  which f o r the  of  its  graphical  The  and  output  method by the  which  differences  can  be  applied  are  c o n s t r u c t i o n of m o d e l s  of  d i s c u s s e d . The  systematic  of  defined.  concept  The  i s presented.  ideas  is  type the  manipulation  of  Employing  interactively graphical  data  introduced.  transformation  and  types.  LIG6  features provided  data  regarding  primitives  Tools  graphical objects  sample  data  system  in Chapter  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 .  5.  o b j e c t s are objects  the  such  areas  in Chapter  represent A  of  knowledge of  abstract  between p r i m i t i v e s and Examples  i s presented  given.  4 introduces  programmers can  editing  base s y s t e m  i n LIG6  operator  i s given is  in Chapter  introduced,  the  VECTOR i s o u t l i n e d , s t r o k e p r e c i s i o n ability  is discussed.  to  save and  r e s t o r e models  of  4  Chapter  2  LANGUAGE DESIGN GOALS  2 . 1 Inqui ry Usually, algorithms control  depends  are  of  variables  must  and  be  able  expressions  o p e r a t i o n s have o c c u r r e d . For i n t e r e s t i n g to  be  where  the  flow  of  on 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 . To make  c o n t r o l d e c i s i o n s , a program values  implemented  to and  inquire  about  determine  graphical  what  algorithms  implemented, the r e s u l t s of g r a p h i c a l o p e r a t i o n s must be  a c c e s s i b l e to c o n t r o l s t r u c t u r e s . Thus, one of the design of L I G 6 was to support Information  information  recovery  goals  recovery.  i s the a b i l i t y t o access the r e s u l t s  of a c t i o n s and thereby determine what o p e r a t i o n o c c u r r e d . I t i s supported  by p r o v i d i n g methods of o b t a i n i n g such access f o r a l l  g r a p h i c a l o p e r a t i o n s . Two forms of access are used i n LIG6. I f a natural, consistent syntactical construct used. Otherwise, a  subprogram  i s possible,  system subprograms are p r o v i d e d . A c a l l  r e s u l t s i n the d e s i r e d i n f o r m a t i o n being  i t is to such returned  in the r o u t i n e ' s parameters. In LIG6, l o g i c a l e x p r e s s i o n s have been extended to the  include  comparison of models of g r a p h i c a l o b j e c t s . In t h i s way, the  5  results  of  program's  graphical  assignment  execution.  Similarly,  statements  and  content  control  i t can be determined  v a r i a b l e ' s value i s a p r i m i t i v e and, structure  can  if  so,  whether a  which  type.  transformations  statements inquiry  and  attribute  are a l s o a c c e s s i b l e . A  has  been  established:  2.2  to  in  between  possess  appeal may  action  and  f o r every o p e r a t i o n there i s a r e s u l t of i t s a c t i o n .  different  features  tend  l e v e l s of s o p h i s t i c a t i o n r e l a t e d to t h e i r  and a b i l i t y . A programming language i s most u s e f u l i f of  all  levels.  This  general  be obtained by d i v i d i n g the language i n t o l e v e l s  each l e v e l a superset of that d i r e c t l y below i t . The are  arranged  to  l e v e l s . This p a r t i t i o n i n g benefit  of  obtain  results  be  be  i s one  level  which the language can quickly  assignment  L e v e l s of Usage  i s a t t r a c t i v e to programmers  Another  results  i s true f o r most occupations, computer programmers  experience it  settings  dualism  method to determine the nature and  As  The  of p r i m i t i v e records are a c c e s s i b l e , so  e n a b l i n g c o n t r o l d e c i s i o n s and automated m o d e l l i n g . The of  a  independent  learned. using  low  level  of those at higher  of the design  partition  lower  with  goals  of  LIG6.  i s the r e l a t i v e ease with Programmers level  are  able  c o n s t r u c t s and  to then  advance n a t u r a l l y , as t h e i r needs i n c r e a s e . Programming languages i n g e n e r a l , and LIG6  in  particular,  can be v i s u a l i z e d as having three l e v e l s of usage. Each of  these  l e v e l s i s i d e n t i f i e d by the s t y l e s of tasks performed. The  first  level  is  a subset of the second which i s , in t u r n , a subset  of  6  the  last. The  little  first  level  i s c h a r a c t e r i z e d by e x p l i c i t  interactive  activity.  In  a  conventional  language, programs which generate t a b l e s or mathematical level.  and  corresponding  solve  in  LIG6  is  image, on a  well-defined  representation  graphical  of that  model,  are  four  in LIG6. The  first  construct  simple  assignment  consists  statement  graphical p r i m i t i v e s . Modelling settings  are  performed  last construct the  results  with  of  graphical  of  activity  processes and  results.  iterative  the  this  various  i s performed  with the and  standard attribute  programs  At  this  level,  e x p l i c i t l y c r e a t i n g the d e s i r e d  and A  fashion  parameters s u p p l i e d LIG6  an  the m o d i f i c a t i o n c o n s t r u c t s .  i s c h a r a c t e r i z e d by a high  The  typical  program  in  a  s t a r t i n g values  i n t e r a c t i v e l y by the user.  e x p l i c i t l y modify models and  At  image. of  earlier  conventional  in which r e s u l t s are  with new  the  level  the e x p l i c i t m o d i f i c a t i o n of  language of t h i s type would be one an  and  transformations  modelling.  second l e v e l of use  interactive  in  i.e.  i s the d i s p l a y statement which produces images of  programmer i s the a r t i s t , The  object  independent c o n s t r u c t s which support  methods of d e c l a r i n g g r a p h i c a l v a r i a b l e s . Modelling the  by  device.  There  with  this  represented  which e x p l i c i t l y model a w e l l - d e f i n e d  d i s p l a y an e x t e r n a l  level  level  and  programming  problems such as numerical i n t e g r a t i o n are of  The  programs  commands  obtained  and  process  this  level,  images of  graphical  objects.  by  In LIG6 programs, models of g r a p h i c a l  objects  assignment  using  statements  are  modified  constructed the  deletion  7  statement.  Images p r o d u c e d  modified  using  two  by  types  the  of  display  erasure  statement  statements.  may  be  Interactive  a c t i v i t i e s a r e supported  by t h e i d e n t i f i c a t i o n  programmer  one s t e p f r o m t h e u s e o f t h e p r o g r a m a t  this  i s removed  l e v e l ; he c r e a t e s a p p l i c a t i o n p r o g r a m s w h i c h a r e  by u s e r s  third  and  highest  u s i n g knowledge of t h e i r r e s u l t s of p r e v i o u s  control. A typical at  The  then  run  t o c r e a t e t h e images t h e y d e s i r e .  The  the  constructs.  this  level  equations. programs  level  own d a t a  i s c h a r a c t e r i z e d by p r o g r a m s  bases and w h i c h use i n q u i r y o f  operations  to  determine  the  flow  problem i n c o n v e n t i o n a l programming  of  languages  m i g h t be a s e a r c h i n g a l g o r i t h m f o r t h e r o o t s o f  The  corresponding  which  level  in  LIG6  i s typified  by  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 o r c r e a t e new m o d e l s b a s e d on t h e  results  of  previous  modelling. This  level  is  c o n s t r u c t s . A data set  of m o d e l l i n g  supported  base d e f i n i t i o n  operators  ability  to  provided  t o a l l p a r t s of  Programmers use  of  precisely  at  the  this  a  a p p l i c a t i o n programmers then  Without programs  with  Sophisticated separate  data  this the  final  modify  programmer  models.  f o r information  create  the  program  the  Access  is  retrieval. from t h e  tools  incorporate i n application  create  which  programs  images.  level,  ability  graphics  giving a  a r e o f t e n removed two s t e p s  They  finally  and  model  level  and i n q u i r y  model i s p r o v i d e d . A c o m p l e t e  i s provided  define  program.  w i t h which users  i n LIG6 by m o d e l l i n g  to  programs  i t isdifficult make would  intelligent be  t o implement decisions.  forced to maintain  b a s e s , d e f e a t i n g one o f t h e p r i m a r y  purposes of  a  8  high-level  g r a p h i c s language. An idea of the importance of t h i s  l e v e l can be obtained by computer  programs  considering  the  IF  statement.  c o n t a i n such c o n d i t i o n a l statements  that they are at the t h i r d available  i n the f i r s t  ability  to  level.  No  inquiry  Most  implying  constructs  are  two l e v e l s . A g r a p h i c a l language with the  perform  inquiry  on  the  results  of  graphical  o p e r a t i o n s 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 F o r t r a n  Consistency  V i r t u a l l y a l l graphics programming languages are extensions to  existing  application constructs  high-level program  computer  will  languages.  generally  A  require  graphics  non-graphics  f o r support. When these c o n s t r u c t s are i d e n t i c a l to  those of a language already known to a programmer, the time effort  required  t o become f l u e n t with the g r a p h i c s language i s  reduced. Any gains made with t h i s lessened host  i f the  approach,  language extension  however,  will  be  i s not c o n s i s t e n t with the  language. Each i n d i v i d u a l c o n s t r u c t of a given computer language  rules  governing  which  i t shares  operations  identifier with  possible  o v e r l a p as much as i s ignored  when  a  names,  the  with  other  constructs.  In  addition,  d i f f e r e n t data types are arranged to  feasible.  language  has  reserved words, and format  If  these  general  rules  i s extended and a d i f f e r e n t  used f o r new c o n s t r u c t s , a programmer w i l l be and  and  forced  r e t a i n twice as much i n f o r m a t i o n regarding s t y l e ;  are  style i s to  learn  confusion  9  w i l l occur over the c h o i c e of s t y l e f o r a p a r t i c u l a r It  is  with  language  was  this  in  construct.  mind that one of the design goals of the  to make a l l extensions as c o n s i s t e n t  with  FORTRAN  as p o s s i b l e . The  most  important  features  of  the format of a FORTRAN  program are that blanks are not d e l i m i t e r s , and that no  reserved  words. A l l syntax  i s determined  FORTRAN one of the more d i f f i c u l t  The  DO DO  10 I = 5 10 I = 5,9  first  statement  expression  5  integer  statement  where the i n t e g e r  i s coerced i n t o a r e a l e x p r e s s i o n and a s s i g n e d to second  statement  i s a DO  statement  with  index I ranging i n value from 5 to 9 and an o b j e c t  whose statement  has the l a b e l  between the two  statements  Such  to parse. A  statements  i s an assignment  the v a r i a b l e DO10I. The the  are  by c o n t e x t , making  computer languages  c l a s s i c example of t h i s i s the two  there  input  10. A  until  format  parser  cannot  distinguish  i t reaches the comma.  conventions  remain  in  LIG6.  extensions do not introduce reserved words, and blanks are ignored. Some upwards compatible  cards are s t i l l  may  the use of a c o n t i n u a t i o n c a r d , although  such  statements  per l i n e are allowed, provided they are separated by  semicolons.  Comments e n c l o s e d i n braces may  l e n g t h of a  has  been  extended  recognized.  now  Multiple  line  p e r m i t t e d and  still  freedoms have been added to the  format of both host and extension statements. Statements span l i n e s without  The  from  appear anywhere. The  72 to 255 c h a r a c t e r s and column  p o s i t i o n s are not important  r e g a r d i n g statement  beginning  None  of  statements.  of  these  labels  extensions  and  the  restrict  10  p r e v i o u s l y c o r r e c t format;  ANSI standard  FORTRAN  programs  are  a c c e p t a b l e LIG6 programs. In  FORTRAN,  there  is a  v a r i e t y of r u l e s and o p e r a t i o n s  which apply to data types g e n e r a l l y . I d e n t i f i e r s are to  a  length  of  six characters.  i d e n t i f i e r s may be typed e x p l i c i t l y , a i d of the IMPLICIT statement. statements  which  can  variable: explicit statement,  and  and  function  or e l s e i m p l i c i t l y  with the  There  determine  Variables  are  the  type d e c l a r a t i o n  no  less  dimensions  statements,  the COMMON statement.  than of  the  three  an a r r a y DIMENSION  E x p r e s s i o n s may be passed  as arguments to subprograms. A l l of these r u l e s the extension data  restricted  also  apply  to  types.  The extension type GRAPHICAL i s e s s e n t i a l l y a p o i n t e r type. Some  of  therefore, variables  the  declarations  are may  not  possible  permissible  with  this  type.  a  common  block  i s a l s o r e f e r e n c e d by a n o n - g r a p h i c a l v a r i a b l e .  statement  types,  Graphical  not be i n i t i a l i z e d , as i n a DATA statement.  may not be equivalenced or placed i n which  f o r non-pointer  f u n c t i o n s are not allowed  2.4 Separate  for this  They  position Finally,  type.  P r e p r o c e s s i n g and Compilation  In computer s c i e n c e , there i s always the  question  of the  e f f e c t a programming s t y l e has on the a b i l i t y t o e a s i l y  generate  correct,  maintainable  modularization solving:  solutions  [Dijk76] has i t s  splitting  a  to problems. A s t y l e known as  origins  in  classical  problem  problem so that when a l l of the subparts  are s o l v e d , the o v e r a l l . s o l u t i o n  has  been  obtained.  Modular  11  programs a r e w r i t t e n Being  able  i n FORTRAN with the a i d of subprograms.  to  create  and i n d i v i d u a l l y t e s t modules of a  program has at l e a s t two b e n e f i t s . The f i r s t easier it  to  i s that  i t i s much  i s o l a t e e r r o r s i n a s m a l l , uncomplicated module than  i s i n a complete program. The second i s that once a module i s  complete and c o r r e c t , i t can  be  used  requires  to  be  a  similar  problem  in  any  solved.  program  In t h i s  which  fashion,  problems need only be solved once. To  promote  libraries  of  modular  useful  subprogram i s f u l l y subprograms variables  of and  are  type  local  to evolve  the  creation  of  g r a p h i c a l r o u t i n e s , the FORTRAN module or  GRAPHICAL  function  i n i t i a l i z e d upon entry libraries  and  supported as a design  subprogram. C o n s i s t e n t parameters  programming  are  identifiers  with FORTRAN, to  a  goal of L I G 6 .  included, may  be  variables  subprogram  and  Function graphical  parameters which  are not  and a r e a u t o m a t i c a l l y  to the r o u t i n e . The c r e a t i o n and  of e f f e c t i v e g r a p h i c a l r o u t i n e s w i l l allow i n t o a powerful design  of a  use of  the system  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 h i g h - l e v e l programming language over  an  assembly-level  language.  has These  several  advantages  p o r t a b i l i t y of programs and programmers, ease language, detail  improved  irrelevent  evident  when  advantages  of  include  learning  the  r e a d a b i l i t y of programs, and the removal of  to  an  application.  comparing  a  Similar  high-level  advantages  graphics  are  language with  subprogram packages such as CORE [GSPC79] or IG [ M a i r 8 l ] . The data  lower  l e v e l c o n s t r u c t s of LIG6 preserve the concept  abstraction  programming  with regard t o g r a p h i c a l data. A c o n v e n t i o n a l  language  allows  the  natural  definition  manipulation of numbers and l o g i c a l values without programmer  to  know  about  a l l o c a t i o n of these data c o n s t r u c t s permit fashion  the  types.  the treatment  internal  Similarly,  and  r e q u i r i n g the  representation lower  level  or  LIG6  of g r a p h i c a l data i n an a b s t r a c t  v i a the simple d e f i n i t i o n and p r e s e n t a t i o n of models of  graphical  objects.  especially  those  the implementation  Use  of  involving  the  advanced  conventional  constructs,  of the language and of i t s data base.  programming  languages  some knowledge of implementation a  level  i n q u i r y , r e q u i r e some knowledge of  To some extent, the use of lower  example,  of  programmer  level constructs  of  both  and LIG6 a l s o r e q u i r e s that  be a c q u i r e d .  In  FORTRAN,  for  must be aware of the q u a n t i t y of memory  13  allocated  f o r v a r i o u s data types when using COMMON b l o c k s and of  the storage mechanism f o r multi-dimensioned  a r r a y s . In LIG6, the  data type GRAPHICAL must be recognized as being a so  that  recursive  definitions  produce s o p h i s t i c a t e d programs knowledge of  are  not  increases  type  made. The a b i l i t y with  the  amount  to of  implementation.  Knowledge  of  how  character  data  is  FORTRAN data types enables the user to make using  pointer  integer  arithmetic.  packed string  in various comparisons  E x p l o i t a t i o n of the v a r i a n t part of  s t r u c t u r e d records of PASCAL allows c o e r c i o n between data types. One  of the reasons assembly languages  programmer  has  implementation  for  implementations.  a  i s the freedom  the use of the advanced l e v e l LIG6 c o n s t r u c t s i n f o r m a t i o n about the implementation  be p r o v i d e d f o r him. T h i s i n f o r m a t i o n i n c l u d e s a base  and  the  model  of  base  by must the  e f f e c t s of g r a p h i c a l m o d e l l i n g on the data  base. Advanced l e v e l c o n s t r u c t s are e x p l a i n e d i n terms of data  the  best q u a l i f i e d to use i t .  programmer, c e r t a i n  data  a  Being the designer of an  which can be t a i l o r e d to f i t the a p p l i c a t i o n ,  programmer i s the one To enable  are used  effects  as  well  their  as t h e i r g r a p h i c a l e f f e c t s . These  c o n s t r u c t s are complete i n the sense that a l l p o s s i b l e data base values may  be c r e a t e d with t h e i r use. T h e i r a v a i l a b i l i t y  that a programmer may  p r e c i s e l y model and  objects  bounds  within  implementation.  the  manipulate  ensures  graphical  of the c a p a b i l i t y of the data base  I t i s to the advantage of programmers using  the  advanced l e v e l c o n s t r u c t s to view LIG6 as a data base management system with g r a p h i c a l s i d e - e f f e c t s . There  is  no  degrading  of the system from  i t s high-level  14  graphics  programming language s t a t u s when t h i s  view  i s taken.  Lower l e v e l c o n s t r u c t s do not r e q u i r e knowledge of the data model data  and  advanced  base. New  interfaces the data  base  l e v e l users are not r e q u i r e d t o manage the  elements  are taken  automatically,  system  care o f , the g r a p h i c a l i n t e r p r e t a t i o n of  base i s b u i l t the  are a l l o c a t e d  i n , and d i s c a r d e d elements  system.  By  providing  are  the  garbage-  collected  by  implementation  information  t o programmers, the most e f f e c t i v e use of the system  becomes p o s s i b l e .  3.1 Data Base Model G r a p h i c a l data is  reflected  i s i n h e r e n t l y h i e r a r c h i c a l i n nature.  i n the  implementation of the data  purpose of using the advanced graphical  level  constructs  This  base. For the of  LIG6,  the  data base can be v i s u a l i z e d as a b i n a r y t r e e . T h i s i s  a dynamically  a l t e r a b l e n - l e v e l h i e r a r c h i c a l data  Leaves of the t r e e are g r a p h i c a l transformations  and  nodes of the t r e e .  attribute  This  model  output  [FOLE82].  primitives.  definitions of  base  the data  are  Modelling  s t o r e d i n the  base  system  is  i l l u s t r a t e d by the f o l l o w i n g synonym assignment statements where means  assignment  and  "+"  means  superposition.  Their  r e s u l t i n g t r e e s t r u c t u r e i s d i s p l a y e d i n F i g u r e 1. A B C D E  :::::-  LINE FROM (X1,Y1 ,Z1) TO POLY FROM (P1,Q1 ,R1) TO 'HI THERE' < MOD 0 > A < MOD 1 > + B < MOD 2 D < MOD 3 > + C < MOD 4  (X2,Y2,Z2) TO (X3,Y3,Z3) (P2,Q2,R2) TO (P3,Q3,R3) >  > + LINE FROM (T1,U1,V1) TO (T2,U2,V2)  In the r e p r e s e n t a t i o n of the b i n a r y t r e e i n F i g u r e pointer  to  the r i g h t of each node i s c a l l e d the value  1, the pointer.  15  LINE X1,Y1,Z1 X2,Y2,Z2 X3,Y3,Z3  B  <4>  <  <2>  <  <0>  STRING HI THERE  LINE T1,U1,V1 T2,U2,V2  >  Figure  The  value  of  a node  refers  to, modified  value  pointer  tree.  Leaves  pointer  from  graphical effects pointer  POLY P1,Q1,R1 P2,Q2,R2 P3,Q3,R3  >  can are  of  the  Data  object  by  transformations  the  point  to  graphical  the new  is  Base Model  i s the  model w h i c h  another output  e a c h node i s c a l l e d  object are  1  superimposed  i t s value  stored  node o r  i n the  The  super p o i n t e r .  on  another,  following:  create  a  node t o t h e  superimposing  node. A  to a leaf  primitives.  the  pointer  the  node, d i r e c t object,  of  the  downward Whenever a modelling the store  value any  16  modifications  s p e c i f y i n g the instance  node, a n d d i r e c t new  type  object  of the o r i g i n a l  i n t h e new  node  to  the  node. For  are  the super p o i n t e r  of that  access  provided  appropriate  (which  pointer in  type d e c l a r e d , example  subobjects,  two g r a p h i c a l  system  - VALUE a n d SUPER. They e a c h t a k e one  graphical  functions  to  of  FORTRAN, either  of t h e i r  is  a  that these  implicitly  pointer  type)  argument's system  argument  and  node.  return  As  f u n c t i o n s must  or e x p l i c i t l y ,  functions  before  of the  for a l l have  their  use.  An  use i s  GRAPHICAL A,B,C,D,E,F,VALUE,SUPER A :- B + C D :- E + A F The  last F  :-  VALUE(SUPER(VALUE(SUPER(D))))  statement  i s equivalent  to  :- C  The c o r r e s p o n d i n g  tree  D  representation  i s presented  E  A  B  C  Figure  2  VALUE and SUPER  Functions  in Figure  2.  17  Use  of  the  VALUE  and  SUPER f u n c t i o n s  r e q u i r e s that  programmer knows the t r e e s t r u c t u r e of a p a r t i c u l a r structure,  however,  is  known  assignment statements he has light  of  this,  nested  model.  The  because i t i s determined by  used  to  graphical  specify  the  expressions  object.  take  the  on a  the In new  mean i n g . For  simple  expressions  merely  transformation LIG6  external  of  the  provide  language,  an  to more than one  programmer  precisely  use  specify  can  use  the  representation.  easy  method  for  expressions,  structure two  of  graphical applying  g r a p h i c a l o b j e c t . An  nested  The  nested  a  experienced  however,  to  h i s model as w e l l as i t s  groups of  statements  A 1 : - B + C + D + E DISPLAY A1 A2 :- (B + (C + D) DISPLAY A2 w i l l cause the  same image  structure  the  of  + ((E))) to  models w i l l  model can  convey information  contents  of  the  appear  on  the  screen  be d i f f e r e n t . The  structure's  nodes. The  two  To enable a programmer to exert maximum  s t r u c t u r e of a  They are  the  assignment, and  synonym  assignment,  the super assignment  Synonym assignment has  s t r u c t u r e s of  the  3.  control  over  already  copy  his  assignment,  statements.  been i n t r o d u c e d .  This  only g r a p h i c a l assignment statement needed by a programmer simple  the  four types of g r a p h i c a l assignment statements have been  provided. value  the  to a program as e f f e c t i v e l y as  above assignment statements are shown in F i g u r e  models,  but  level  language  constructs.  i s the using  Such a programmer does not  need to know the e f f e c t of t h i s assignment on t r e e s t r u c t u r e s or  18 A1  A2  B  3  Figure  even  that  of  The  node  superposition  form  the v a l u e and and  expression  assignments.  The  production  creates  statement  to the r i g h t  of  allows  the  ::=  ::=  <graphfactor>  expression  Backus-Naur  <graphprimary>  <graphterm> | <graphexpress>  <graphfactor> | <graphfactor>  ::=  form  |  the  symbol  the contents  new  nodes  + <graphterm>  <graphvariable> <graphfunction>  )  most  can  definition  <modificationlist>  <graphprimitive> <graphprimary> ( <graphexpress>  ::=  is  tree  for  general  i t s o p e r a t o r of a l l of the  is  <graphexpress> <graphterm>  The  type  as a  level.  production for this  <graphexpress>.  be m o d e l l e d  s u p e r p o i n t e r s and  automatically  a t the top  can  operator for t h i s  synonym a s s i g n m e n t  of  Graphical Expressions  implementation  assignment  redefines  the  The  Nested  t h e d a t a base  structure. It  B  be for  called this  19  The a  copy assignment statement a l s o r e d e f i n e s a l l aspects of  node.  I t s operator  i s simply  i s ":=". The e f f e c t of such an assignment  to copy the p o i n t e r s and t r a n s f o r m a t i o n s  stored  i n the  node s p e c i f i e d on the r i g h t hand s i d e i n t o the node s p e c i f i e d on the  l e f t hand s i d e . Subsequent  yield be  display  of  either  i d e n t i c a l v i s u a l r e s u l t s . The expression  a  <graphprimary>, that  with no m o d i f i c a t i o n s  node  would  on the r i g h t must  i s , a g r a p h i c a l v a r i a b l e or f u n c t i o n  or s u p e r p o s i t i o n s .  Consider the  following  statements. B A A A  i) ii) iii) iv) If  :::= :=  each  statement  structures The  C + (D + E) B B VALUE(SUPER(A)) were  in Figure  value  executed  not  effect not  assignment statement a f f e c t s the value  affected.  The  value  i s to change the i n i t i a l  any  objects  expression  the corresponding  4 would be generated.  a node and the t r a n s f o r m a t i o n s is  i n order,  which  have  stored  i n i t . The  p o i n t e r of  super  assignment operator  pointer  i s ":>". I t s  value  d e f i n i t i o n of a node,  been  superimposed  on the r i g h t must be a <graphterm>, that  as a <graphexpress> except that no s u p e r p o s i t i o n  but  upon i t . The i s , the same  i s allowed. The  f o l l o w i n g statements generate the t r e e s t r u c t u r e s of F i g u r e 5. i) ii)  A :- B + C A :> (D + E)<COLOUR 120> The  of  a  super assignment statement r e d e f i n e s  node. The value  p o i n t e r and the t r a n s f o r m a t i o n s  the node are not a f f e c t e d . I t s operator to  replace  initially  a l l objects  defined  the super  object  that  have  pointer stored in  i s ":<". I t s e f f e c t been  superimposed  by a new o b j e c t . The expression  is  on an on  the  B  D  (ii)  i)  (iv) Figure  4  Copy  Assignment  B  E — >  (iv)  (i) Figure  5  Value  Assignment  21  right  must  <graphterm>  be but  a no  statements y i e l d i) ii) iii) iv)  A D A D  <graphfactor>, modifications  the  :- B + C :- E + B :< SUPER(D) :< (B<COLOUR  that are  +  the  allowed.  structures depicted  120>  is,  same  The  in Figure  as  a  following  6.  (C))  B  B  (i)  (ii)  B  E  B  B  •  >  (iii)  (iv)  Figure  The set  of  tree  operators. structure  provided output  preceding  four  6  Super  assignment  statements  form a  They e n a b l e programmers t o c r e a t e they  desire.  which enable o p e r a t i o n s  primitives.  Assignment  Additionally, on  the  leaves  of  any  complete binary  constructs the  tree,  are the  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  the  information  implementation constructs.  about  are To  the  not  fine  needed  reinforce  details  by  this  of  users  of  point,  a  data base  advanced summary  level of the  implementation w i l l now be given. The variety  nodes d e p i c t e d of  methods:  as  groups of l i n e s i n d i s k acquired  virtual  i n Figure  1  arrays  files,  memory.  could  be  stored  using  a  i n common b l o c k s , as l i n e s or  or  as  records  in  dynamically  The f i r s t approach f i x e s the s i z e of  the data base. Small programs would pay the p r i c e of high memory charges f o r the unused p o r t i o n s  required  for larger  The  overhead  in  second  execution  method  has  high  disk  time. The l a s t method uses only as much  program  requires  storage  involves.  programs.  charges memory  but does not have the overhead that It  is  the  approach  and as. a  secondary  chosen  for  the  implementation of the LIG6 data base. Each node r e q u i r e s 24 four byte words of contiguous memory. The  fields  of each node are of three d i f f e r e n t  types:  fullword  REAL, f u l l w o r d INTEGER, and halfword INTEGER. Because the are and  stored  i n v i r t u a l memory, access t o them i n v o l v e s  a. system subroutine  types  c a l l . Access to the f i e l d s of  i s accomplished by passing  different illustrate  the p o i n t e r  type d e c l a r a t i o n f o r each. this.  The  three  following  nodes  pointers different  times with a statements  23  EXTERNAL ACCESS CALL CALLER(ACCESS,POINTR,POINTR,POINTR) SUBROUTINE ACCESS(REALA,INTA,INT2A) REAL REALA(24) INTEGER INTA(24),INT2A*2(48) The  fields  of  a  node store the modelling  a t t r i b u t e s e t t i n g s and the graphical given  assignment  instance  statements.  transformations  definitions The  and  specified  structure  of a node i s  i n F i g u r e 7.  Position fword Fullword 1-12 13 14 15 16 17 18  Name TRMAT COLOUR LITNES SATUTN PATERN BCOLOR BLITNS BSATUN BPATRN STYLE WIDTH FONT VALUE SUPER INSTAN GARBGE  19  20 21  43 44 45 46 47 48  Figure  7  Type  Use  REAL REAL REAL REAL INTEGER REAL REAL REAL INTEGER INTEGER I NT* 2 I NT* 2 I NT* 2 I NT* 2 I NT* 2 I NT* 2  t r a n s f o r m a t i o n matrix i n t e r i o r hue a t t r i b u t e interior lightness attr. interior saturation a t t r . i n t e r i o r pattern a t t r i b u t e border hue a t t r i b u t e border l i g h t n e s s a t t r i b u t e border s a t u r a t i o n a t t r . border p a t t e r n a t t r i b u t e line style attribute l i n e width a t t r i b u t e t e x t s t r i n g font number value p o i n t e r superposition pointer instance p o i n t e r garbage c o l l e c t o r storage  Graphical  Node  Structure  Every g r a p h i c a l v a r i a b l e i s an i n t e g e r halfword p o i n t e r a  by  node.  These  pointers  addresses of the nodes pointer  storage),  are  (which  not would  the  actual  require  v i r t u a l memory a  fullword  but i n d i c e s i n t o an array of nodes. T h i s  is  organized  as blocks of 42 nodes. Each block  one  page (4096 bytes) of  virtual,  memory.  As  to  for array  i s approximately more  nodes  are  24  r e q u i r e d , the array Each Due  block  i s dynamically  expanded one block at a time.  i s r e f e r e n c e d by an element i n an a r r a y of p o i n t e r s .  to p o i n t e r p r e c i s i o n , the maximum number of blocks  This  represents  three megabytes of storage. As the maximum s i z e  of the array of p o i n t e r s to blocks dynamically The  large  i s thus  for primitive  records  f a s h i o n . Each r e c o r d i s a  one-dimensioned  negative,  array.  i t represents  When  the negative  organized  as  blocks  of  necessary.  A  record  consists  information,  of  1024  a index  is  in a of  pointer  of the s t a r t  a is  of the  i s a l s o dynamic; i t i s  which  of  header,  a  section  graphical  words  primitive  are a c q u i r e d when the  primitive  follows,  garbage  collection  and the l e n g t h of the r e c o r d . The word o r g a n i z a t i o n i s i n F i g u r e 8.  cd  gb  cd - P r i m i t i v e s t y l e i n d i c a t o r 01 = POLYLINE 02 = POLYGON 03 = TEXTSTRING 04 = USER DEFINED PRIMITIVE Figure 8  The  array  and a t r a i l e r . The header c o n s i s t s of one word; i t  c o n t a i n s what type  depicted  the  i s organized  contiguous  p r i m i t i v e r e c o r d i n the a r r a y . T h i s array  storage,  780,  kept i n v i r t u a l memory as w e l l .  storage  different  i s 780.  nnnn  gb - Garbage c o l l e c t o r  storage  nnnn - Length of record  P r i m i t i v e Record Header  p r i m i t i v e i n f o r m a t i o n depends on the type of p r i m i t i v e .  For p o l y l i n e s and polygons, i t c o n s i s t s of groups of x,y, and  z  25  coordinates.  For t e x t s t r i n g s , i t c o n s i s t s of bytes  data. For u s e r - d e f i n e d p r i m i t i v e s , i t c o n s i s t s representation trailer end  an  external The  i s e i t h e r a c o n t i n u a t i o n or an end command. If i t i s  an  that  is  p o i n t e r and a l i s t  character  of parameters.  command,  procedure  of  of  the  end  of  the p r i m i t i v e . If i t i s a  c o n t i n u a t i o n command, i t c o n t a i n s a p o i n t e r to the p a r t  of  array  records  where the p r i m i t i v e i s continued.  l a r g e r than 1024  words and  following  program  LIG6  presented  for  concatenation  would  i n F i g u r e 9 which was  This allows  create  the  produced  by  for  the  assignment. primitive the  The  storage  system  debug  dump, LIGDPH. GRAPHICAL A,B,C A :- POLY FROM (1,2,3) TO (4,5,6) DELTA (3,3,3) B :- 'Line a t ' C :- A + LINE FROM (-1,2) TO (3,-4) B :+ ADDSTRING IVALUE(9+7,5) CALL LIGDPH STOP END Free areas.  lists  Whenever  acquisition appropriate collector  kept  of  storage,  free l i s t .  are  the  executed  storage  If the f r e e l i s t  is is  storage),  p r i m i t i v e record  which  require  acquired empty,  If the amount of storage  i s l e s s than a set amount (42 nodes or  primitive  from  the  the  garbage  recovered 256  the  by  the  words  of  another page of v i r t u a l memory i s a c q u i r e d  initialized. The  garbage  subprogram  is  collector entered,  in  virtual  operates  as  follows.  Whenever  a  a l l l o c a l g r a p h i c a l v a r i a b l e s used are  a l l o c a t e d nodes and a l i s t list  f o r both nodes and  statements  i s invoked.  collector  and  are  memory.  of those The  nodes i s kept in  execution  a  protect  of a RETURN statement  26  Heap space dump - Page 1 Address Contents E x p l a n a t i o n 1 02000003 Polygon 3 vertices 2 41100000 x-component 0 . 1000000E+01 3 41200000 y-component 0.2000000E+01 4 41300000 z-component 0.3000000E+01 5 41400000 x-component 0.4000000E+01 y-component 6 41500000 0 . 5000000E+01 z-component 7 41600000 0.6000000E+01 8 41700000 x-component 0.7000000E+01 9 41800000 y-component 0.8000000E+01 10 41900000 z-component 0.9000000E+01 • 11 00000000 End 12 03000008 S t r i n g 8 characters Text - Line 13 D3899585 14 4081A340 Text - at C o n t i n u a t i o n l o c a t e d at 15 05000018 24 Line 16 01000002 2 vertices 17 C1100000 x-component -0.1000000E+01 18 41200000 y-component 0.2000000E+01 19 00000000 z-component 0.0 20 41300000 x-component 0.3000000E+01 21 C1400000 y-component -0.4000000E+01 22 00000000 z-component 0.0 23 00000000 End String 24 03000004 4 characters 25 4040F1F6 Text 16 26 00000000 End 27 07E50101 Free space 229 words, continued 257 07FF0201 Free space 255 words, continued 513 07FF0301 Free space 255 words, continued 769 07FF0000 Free space 255 words, continued Figure 9  P r i m i t i v e Record  causes those nodes to be removed garbage  collector  from  the  protect  s t a r t s from the p r o t e c t l i s t  i s completed,  257 513 769 0  Storage  marks the nodes which are d e f i n e d by the l i s t . phase  at at at at  list.  The  and r e c u r s i v e l y When  this  mark  a l l of the node and p r i m i t i v e storage i s  swept through with unmarked areas being added t o the a p p r o p r i a t e free  list. The d e t a i l s of the implementation  operations  which  The model of effectively  the model  manage data and  of the data base and the  i t are hidden  base  provides  manipulate  from a LIG6 programmer. enough  information  to  g r a p h i c a l o b j e c t s using the  advanced l e v e l  constructs.  28  Chapter 4 GRAPHICAL OUTPUT PRIMITIVES Four g r a p h i c a l output BLANK,  POLYLINE,  primitives  POLYGON,  and  are  supplied  by  LIG6:  TEXT. T h e o r e t i c a l l y , any image  which can be d i s p l a y e d on an output d e v i c e of  finite  precision  can be c r e a t e d using these p r i m i t i v e s , thus they form a complete set of atomic g r a p h i c a l o b j e c t s . As a convenience, however, LIG6 also  permits  programmer-defined  p r i m i t i v e s . T h i s can s i m p l i f y  m o d e l l i n g of w e l l - d e f i n e d g r a p h i c a l  objects.  4.1 P r i m i t i v e s as A b s t r a c t Data Types In e a r l i e r v e r s i o n s of LIG [Schr76], p r i m i t i v e s were viewed as c o n s t a n t s of the data primitives  type  GRAPHICAL.  Six  two-dimensional  were d e f i n e d : BLANK, LINE, TRIANGLE, SQUARE, CIRCLE,  and SCIRCLE ( s e m i - c i r c l e ) . Only the f i r s t r e s t c o u l d be c o n s t r u c t e d from  the  two were r e q u i r e d ; the  primitive  LINE.  p r i m i t i v e was d e f i n e d as a l i n e segment from the p o i n t to  the p o i n t  applying  transformations  view  (0.0,0.5)  taken  by  to  this  constant.  transformed l i n e the  current  Polylines  by a language,  were  segments. version,  LIG6, i s that  p r i m i t i v e s a r e data types i n t h e i r own r i g h t . For any data supported  LINE  (1.0,0.5). A l l other l i n e segments were c r e a t e d by  c r e a t e d by superimposing The  The  type  r u l e s e x i s t which d e f i n e how constants  29  of  that  type  legitimate  also,  of  that  operators type  a r e s u p p l i e d which produce  are  external  which  form  specified,  and  representations  values of that type. Consider  is  expressed,  expressions  procedures of  are  the data type COMPLEX. I t s standard  implementation  a r e c o r d c o n s i s t i n g of a r e a l and an imaginary  type REAL. A FORTRAN complex constant parenthesis field,  followed  a comma,  field,  a  by  real  consists  a r e a l constant constant  field  of  each of  an  opening  r e p r e s e n t i n g the r e a l  representing  the  imaginary  and a c l o s i n g p a r e n t h e s i s . When o p e r a t i o n s are performed  on t h i s type, the contents of the i n d i v i d u a l f i e l d s are used determine the r e s u l t . S p e c i f i c a l l y the imaginary The  the r e a l p a r t and  p a r t are p r i n t e d s i d e by s i d e .  primitive  has a l l of  f o r output,  to  the  POLYLINE of the language L I G 6 , f o r example,  features  of  an  abstract  data  type.  It i s  implemented by a record with a v a r i a b l e number of f i e l d s of type VECTOR. Each f i e l d is  accessed  output for  to  represents a vertex i n a l i n e and, on output, generate  g r a p h i c a l commands given to the  d e v i c e . While there are no d i r e c t v a r i a b l e s or  t h i s type, the type GRAPHICAL (which  o p e r a t o r s ) can be reference The types  to  supports v a r i a b l e s and  contain  a  e x t e r n a l r e p r e s e n t a t i o n procedures  generally  recursive  considered  operators  field  which  can  polylines.  have the same  of c o n v e n t i o n a l data  produce symbols on p r i n t e r s or t e r m i n a l s which  representation PASCAL  as  procedure  r e p r e s e n t a t i o n s of unsigned it  the  constants for  of  that  generating  i n t e g e r s i s presented  type.  A  external  i n Figure  10;  has the above c h a r a c t e r i s t i c . T h i s p r a c t i c e r e s u l t s from the  30  e x i s t e n c e of a standard r e p r e s e n t a t i o n which can be used both i n the s p e c i f i c a t i o n of a program and executing  that  program.  i n the r e s u l t s  There  is  no  r e p r e s e n t a t i o n s must be the same; i n t e g e r s are in  generated  rule  that  often  alphanumeric external  c h a r a c t e r s using representations  d e v i c e s . The  latter  definite  are  lines  both  expressed  other bases or even as Roman numerals. T h i s i s the case  the type POLYLINE; such c o n s t a n t s are expressed  by  with  i n programs with  syntactic  rules  while  generated  on  graphical  r e p r e s e n t a t i o n would probably  be  used  for  constants i f i t were a v a i l a b l e . PROCEDURE e x t _ r e p _ i n t e g e r ( n : INTEGER ) ; BEGIN IF n < 10 THEN w r i t e ( CHR( n + ORD C O ' ) ) ELSE BEGIN e x t _ r e p _ i n t e g e r ( n DIV 10 ); w r i t e ( CHR( n MOD 10 + ORD('O') ) ) END END; Figure  The  10  records  )  Integer E x t e r n a l Representation  of the data types POLYLINE, POLYGON, and TEXT  can have a v a r i a b l e number of f i e l d s ;  such data types are  as  are  dynamic.  Dynamic  programming languages  do  data not  types support  not  them.  common Both  as  SNOBOL  known most and  BASIC, however, have dynamic s t r i n g data types.  4.2  Programmer Defined  The d e f i n i t i o n of a p r i m i t i v e of  an  abstract  data type. The  Primitives  i s e q u i v a l e n t to the c r e a t i o n  treatment  of p r i m i t i v e s by LIG6  31  requires  that  a  specification  data  rules,  type  definition  internal  creates  a  constant  representation information,  e x t e r n a l r e p r e s e n t a t i o n procedures. programmer  includes  The  c o n s t r u c t with  and  which  a  LIG6 p r i m i t i v e i s a p r i m i t i v e d e f i n i t i o n  unit. A primitive d e f i n i t i o n unit First  a  symbolic  definition c ons ta nt s  name  is  has  a  specified  r u l e must f o l l o w i n the  and  for  form  of that type w i l l match. The  declarations  of  of  representation definition  a  primitive. template  using a n o t a t i o n  which  values  similar  of  that  producing  an  external  primitive.  The  internal  is  derived  automatically  are  a  variety  of methods used to d e f i n e grammars;  Backus-Naur forms and  from  the  constant  syntax d i r e c t e d diagrams are two  examples.  Wirth's n o t a t i o n provides a general d e s c r i p t i o n mechanism i t e r a t i o n , a l t e r n a t i o n , o p t i o n , and  to be expressed. definition only  The  unit  grammar  template  alternation  allowable  and  production uses a subset  option  grammar productions  grammar; t h i s  i s presented  constructs can  of  templates  parentheses. brackets  separated  An option  optionally  recursion constructs  in  a  LIG6  primitive  of t h i s n o t a t i o n s i n c e are  The  themselves be represented  by a  11 using Wirth's n o t a t i o n .  an a l t e r n a t i o n c o n s t r u c t  by v e r t i c a l bars and  construct  which  permitted.  in Figure  In a LIG6 p r i m i t i v e template, list  type  rule.  There  allows  A  remainder of the subprogram c o n s i s t s of  statements which d e f i n e a procedure f o r representation  the  structure.  template c o n s i s t s of  a grammar p r o d u c t i o n  to Wirth's [Wirt77]. The  prescribed  is  a  template  followed by the e x p l i c i t  is a  enclosed enclosed  setting  by by  construct  32  production  = primitive_identifier  "::=" s u b t e m p l a t e l i s t ";"  s u b t e m p l a t e l i s t = subtemplate { subtemplate } alternation explicit_setting  subtemplate = ( t e r m i n a l option nonterminal terminal = ( l i t e r a l _ s t r i n g literal_string  | field_identifier  = '"" { ( c h a r a c t e r  alternation = " ( " subtemplatelist option = " [ " s u b t e m p l a t e l i s t explicit_setting  | " " " ) } '"" { "|" s u b t e m p l a t e l i s t  " ] " [ explicit_setting ]  "="  expression  nonterminal = p r i m i t i v e _ i d e n t i f i e r 11  } ")"  = "<" s e t t i n g { "," s e t t i n g } ">"  setting = f i e l d _ i d e n t i f i e r  Figure  )  Allowable  " ( " { character  P r i m i t i v e Template Grammar  }  ")"  Productions  which d e f i n e s the d e f a u l t . The nonterminal c o n s t r u c t allows  the  i n s e r t i o n .of the template of a p r e v i o u s l y d e f i n e d p r i m i t i v e . The characters all  i n the l i s t  of the f i e l d  f o l l o w i n g the i d e n t i f i e r are appended to  i d e n t i f i e r s of the p r e v i o u s l y d e f i n e d p r i m i t i v e  when i t i s i n s e r t e d . T h i s allows m u l t i p l e use of in  a  template.  A  and  primitive  template which demonstrates a l t e r n a t i o n and  o p t i o n c o n s t r u c t s and constants Figure  the  which match i t are presented  in  12. A template which demonstrates the use of nonterminals  constants The  which match i t are shown i n F i g u r e 13.  body  of  the  primitive  definition  external  representation  procedure  consists  of  which,  statements  f i e l d s of the data body  may  with  graphical  excluded  type,  u n i t d e f i n e s the  f o r that  based  data  upon  type.  the values  produce images on output  It  of the  devices.  The  c o n t a i n any type of statement except those which d e a l  because  modelling  or  display.  they d e a l with  These  information  statements  at a higher  are  level.  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 SQUARE SQUARE SQUARE SQUARE  FILLED AT (5.1,5,0) FILLED SIDE 3.0 AT (3,2.7,6), SIDE 0.5 FILLED SIDE 3*PI, AT (V1#V2) Figure  12  PRIMITIVE ONEARG INTEGER OPT VECTOR V ONEARG ::= ( <OPT=1> NW <OPT=4> 'SW <OPT=7> 'S' '=' V ;  Square P r i m i t i v e  <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  t o occur, the  DRAW and DRAW WITH statements. The by  form of the draw statement i s the keyword DRAW followed  a p r e v i o u s l y d e f i n e d p r i m i t i v e , e i t h e r one of the four b a s i c  p r i m i t i v e s or  one which  primitive definition  was  programmer-defined.  A  complete  u n i t f o r a square p r i m i t i v e f o l l o w s .  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 primitive  a  whose  specification  i n c l u d e s a SQUARE  i s d i s p l a y e d , the e x t e r n a l r e p r e s e n t a t i o n procedure i s  invoked. A l l of settings  model  of  the m o d e l l i n g  the model  transformations  affect  the procedure.  and  attribute  In a d d i t i o n to  p r i m i t i v e s , a p p r o p r i a t e c o n c a t e n a t i o n e x p r e s s i o n s may f o l l o w the DRAW keyword. An example of t h i s usage i s  20  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)) CONTINUE RETURN END Concatenation  DRAW statement  e x p r e s s i o n s may only be executed  executed  i f the l a s t  was a c o n c a t e n t a t i o n or p r i m i t i v e of the  same type. A t t r i b u t e s of the draw statement DRAW  WITH statement.  by a l i s t attribute  of a t t r i b u t e which  I t s form  may be  changed  with the  i s the keyword DRAW WITH f o l l o w e d  s e t t i n g s e n c l o s e d i n angle b r a c k e t s . Any  has not been s p e c i f i e d  i n the m o d e l l i n g may be  set by such a statement. Programmer-defined p r i m i t i v e s permit e f f i c i e n t modelling  of  regular  or  example of a p r i m i t i v e which  parameterized models  and c o n c i s e  g r a p h i c a l o b j e c t s . An  spheres  constructed  with  35  arbitrary  resolution  and  illuminated  by  an  arbitrary  light  source i s presented i n F i g u r e 14.  4.3 G r a p h i c a l Strictly of  F u n c t i o n s Versus G r a p h i c a l  Primitives  speaking, the c a p a b i l i t y of programmer  graphical  output p r i m i t i v e s i s not necessary. Any g r a p h i c a l  e f f e c t which such a p r i m i t i v e can produce can a l s o by  a  function  primitives  and  functions  of  type  GRAPHICAL.  The  functions  are  graphical  be  produced  differences  between  subtle.  Graphical  a r e executed as soon as they are invoked, r e t u r n i n g a  model of a g r a p h i c a l o b j e c t . for  definition  storage  and  have  Such models  structures  and  require values  memory which  space can  be  subsequently manipulated. An result  invocation  and i t i s not u n t i l  displayed  that the e x t e r n a l  the value of that p r i m i t i v e i s to be representation  d e c i s i o n whether to use  function,  therefore,  should  a be  g u i d e l i n e s . I f the r e s u l t i n g object i f i t . contains  parameterized, considered. and  not  procedure i s invoked.  r e s u l t s i n savings i n both memory and execution time. The  or  does  i n execution of code. The parameters of the p r i m i t i v e are  stored  This  of a p r i m i t i v e , on the other hand,  then  curves a  I f an object  or  function  made  or  using  a  graphical  the  following  i s always t r e a t e d as a  unit  subobjects which can be e a s i l y  primitive  implementation  should  be  has a d e f i n i t e s t r u c t u r e and h i e r a r c h y  subparts of i t w i l l be accessed  graphical  primitive  and  possibly  implementation should be  modified,  considered.  a  36  10  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 = P I 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 = P I + 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) P I = P2 P3 = P4 CONTINUE RETURN END Figure  14a Sphere P r i m i t i v e D e f i n i t i o n  Figure  14b Sphere P r i m i t i v e Output  37  Programmer-defined used i n other  languages  emphasis.  Earlier  graphical  function  arguments and only was  when  a  versions  that  the  by  LIG6. upon  implementation  of  of  could  six  their  was  a reference  of  a  and  The  lines,  actual  not  was  This  differs  f u n c t i o n which i s are  return  executed  a  f u n c t i o n s were  programmer-defined  draw  the  function  functions  invocation  store  to the  executed.  concept  graphical  to  called a  model of a in  fact  an  p r i m i t i v e s although they  implementation. They had  all  structure,  previously  syntax d e f i n i t i o n provided  a  defined  by LIG6  was  permitted. The  language MIRA allows  tThal79,Magn81].  The  i n c l u d e s modelling  The  is  invoked  implementation  with  declaration type  the d e f i n i t i o n of g r a p h i c a l  language  however, i s more in l i n e  via  graphical  a  modelling storage  process  and  actually  procedural  facility  In  constants  addition,  of LIG6 i s not a v a i l a b l e .  The  construct, of  the  time; i t i s not delayed u n t i l an  displayed.  types, type  not d i s p l a y commands.  occurs immediately upon i n v o c a t i o n  execution  types  of these  functions.  operations,  assignment statements c o n t a i n i n g  is  a construct  and  in the data base. It  was  early version  terminology  parameters, were invoked by a f i x e d  only  primitives. not  function  function  LIG6  had effect  the g e n e r a l i t y of the c u r r e n t  maximum and  LIG Its  standard  g r a p h i c a l o b j e c t . The  lacked  of  p r i m i t i v e s have been  different  model which contained  the  immediately  output  with  [Schr78].  from  supported  but  a p o i n t e r to the  displayed  markedly  graphical  the  pattern  not  type.  by The  requiring instance matching  38  Chapter 5 GRAPHICAL DOMAINS There are languages  many  may  be  domains applied,  in but  which  graphical  programming  use of a p a r t i c u l a r g r a p h i c a l  programming language w i l l be l i m i t e d i f the domains i n which i t can  be  applied  provide  simply-expressed  external allow  are r e s t r i c t e d . H i g h - l e v e l  representation  constructs of  graphical  f o r the  graphical  data.  such languages to be a p p l i e d to domains  languages  definition These  at  and  constructs  the d r a f t i n g  systems l e v e l . More s o p h i s t i c a t e d a p p l i c a t i o n s , however, r e q u i r e the  analysis  which provide the  of  a r b i t r a r y g r a p h i c a l data. The  i n q u i r y and manipulation of g r a p h i c a l data  language t o be a p p l i e d  permit  i n a v a r i e t y of i n t e r e s t i n g domains;  four of these w i l l be d i s c u s s e d  using a  5.1 C o n s t r u c t i o n Due  constructs  LIG6  to the l a r g e q u a n t i t y  example f o r each.  LIG6  Tools  of data i n v o l v e d  a p p l i c a t i o n s , the e x p l i c i t d e f i n i t i o n  of  i n most  graphical  o f t e n tedious and time consuming. G r a p h i c a l  graphics  objects  is  a p p l i c a t i o n programs  must capture as much r e g u l a r i t y of the input data as p o s s i b l e to allow  economy  achieved  of gesture i n the modelling  with the a i d of  construction  process.  tools  in  T h i s can be  the  form  procedures which c r e a t e models of complex g r a p h i c a l o b j e c t s  of with  39  minimal  i n p u t . An example of two  c o n s t r u c t i o n t o o l s which would  be u s e f u l in a ductwork a p p l i c a t i o n i s given could  find  generation The  a p p l i c a t i o n in other  contexts  15.  where r e g u l a r  Both  surface  i s required.  procedure EXTRUD takes as  section  in F i g u r e  and  a  d i r e c t i o n and  input  an  arbitrary  cross-  l e n g t h s p e c i f i e d as a v e c t o r .  The  cross-section  i s extruded as s p e c i f i e d by the v e c t o r ,  generating  a column. The  procedure  arbitrary  cross-section,  REVOLV  takes  as  an a x i s s p e c i f i e d by two  input  an  p o i n t s , an angle,  and  a  step parameter. The  c r o s s - s e c t i o n i s revolved around the a x i s by  the angle s p e c i f i e d  i n the given  3-D  number of steps,  f i g u r e . Three system procedures are  the number of v e r t i c e s LINPNT  returns  the  of  a  invoked. PRILEN  polyline  specified  vertex  generating  or  polygon  a  returns  primitive,  of a l i n e p r i m i t i v e , and  APLYMD a p p l i e s the t r a n s f o r m a t i o n s  s t o r e d i n a g r a p h i c a l node to  a p o i n t , r e t u r n i n g the transformed  value.  Other c o n s t r u c t i o n t o o l s which would complement two  would be procedures to j o i n two  to  compute s o l i d  analyze  d i s s i m i l a r c r o s s - s e c t i o n s or  any  models  manipulation  generated  and  metal c o n s t r u c t i o n of the p i p i n g . F i g u r e s  show  two  views each of two  procedure  16  through  graphical objects constructed  REVOLV procedures.  which  produce p a t t e r n s  sheet  the EXTRUD and  above  i n t e r s e c t i o n s . A complete ductwork a p p l i c a t i o n  program might i n c l u d e a systematic would  the  for 19  using  40  10  10  20  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 CONTINUE RETURN END 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 (OLD) TO (NEW) TO (NEW1) TO (OLD1) 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 Figure  15  G r a p h i c a l Ductwork C o n s t r u c t i o n T o o l s  5.2 Systematic M a n i p u l a t i o n Systematic m a n i p u l a t i o n of g r a p h i c a l o b j e c t s by  procedures  which  process  a  graphical  i s performed  model of a r b i t r a r y  41  Figure  17  Second View of Pipe  Figure  18  Figure  H e l i x Constructed With REVOLV  19  Second View of H e l i x  43  structure  and content.  programs  t o perform  example of systematic subobject  Such  procedures  permit  modelling a t v a r i o u s manipulation i s the  f o r another  i n an  application  l e v e l s of d e t a i l . An substitution  arbitrary  g r a p h i c a l o b j e c t . To  demonstrate LIG6's a b i l i t y t o implement systematic procedures, a deep replace a l g o r i t h m The  problem  recursion models  i s divided  i n t o two p a r t s . A general  objects.  which i s t o be manipulated. graphical  function  double  manipulation  of  The parameter TREE i s the model  The parameter  which  manipulation  i s presented i n F i g u r e 20.  subroutine RECURS performs r e c u r s i v e  of g r a p h i c a l  of one  controls  FIRST  the f i r s t  specifies  a  r e c u r s i o n . The  parameter WORK s p e c i f i e s a subroutine which performs the d e s i r e d manipulation whenever FIRST r e t u r n s parameter  SECOND  the  recursion.  second The  a  stopping  specifies a graphical  The  f u n c t i o n which c o n t r o l s  second part comprises four r o u t i n e s which s e t up RECURS  to perform deep replacement. The g r a p h i c a l DEEP2  condition.  correspond  t o FIRST  functions  and SECOND,  r e s p e c t i v e l y . The  subroutine SWAP  corresponds  invokes  s p e c i f y i n g the above parameter assignments. The  RECURS  r e s u l t of a c a l l object  a shift  f l o p s were replaced  Due  The subroutine  t o DREPLC i s shown i n F i g u r e  representing  RS f l i p  t o WORK.  DEEP1 and  21. In a g r a p h i c a l  r e g i s t e r , the g r a p h i c a l by t h e i r l o g i c gate  symbols f o r  representations.  t o the h i e r a r c h i c a l nature of g r a p h i c a l data,  manipulation extension permitted.  of models  to FORTRAN, This  i s desirable. however,  can be  Because  recursive  recursive  LIG6  routines  overcome e a s i l y with r o u t i n e s  RECURS. Other examples of uses  of RECURS  DREPLC  a r e copying  i s an are  not  such as trees,  44  10  20  SUBROUTINE RECURS(TREE,WORK,FIRST,SECOND) GRAPHICAL TREE,FIRST,SECOND,STACK(25),VALUE,SUPER INTEGER POINT POINT = 1 STACK(1) :- TREE 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) 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 F i g u r e 20  Deep Replace A l g o r i t h m  45  SHIFT REGISTER  Figure  flattening any  trees,  21  and  Line  file  text.  modified  by  the  Graphical  Editing  used to  structure  editor An  graphical An  the  reversing  e d i t o r s are  The  information. on  Substitution  order  of  superposition  at  level.  5.3  and  Graphical  and  commands  analogous  structure  of  programs,  the  delete,  data  in a  alter,  f o r m of m a n i p u l a t i o n  can  or be  data, file  is  insert  performed  data.  ability The  content  which  interactive graphical  objects.  manipulate  of  e d i t o r has  LIG6 t o a n a l y z e and  representation  content  of  i s analogous  the  implemented  m o d i f y m o d e l s of  program g e n e r a t e s a v i s u a l and  been  model  to a l i s t i n g  representation being of  a  using  graphical of  the  generated.  The  file.  With the  aid  46  of the  representation,  the model can  be manipulated using  editor  commands. The  v i s u a l representation  s t r u c t u r e of the model. The  produced i s a drawing of the  branches of the t r e e  the p o i n t e r s of the model. Within of  i t s g r a p h i c a l value  the t e r m i n a l , the specifying  model  modelling  d e l e t i n g nodes, and manipulated, occur. The Figures  manipulated  transformations  other  audit t r a i l  22 through  of  22  the  p o r t i o n of graphical  at  moving  nodes,  editing functions.  As  the  model  is  representation is  image of the o r i g i n a l model and The  result  s t r u c t u r e i s shown i n Figure model  value  pointers,  given  in  Figure  23  30.  i s the  the  of  i n s e r t i n g or  of a sample e d i t i n g s e s s i o n  i t s tree structure representation.  part  by  to  image  l o c a t o r input  corresponding changes in the v i s u a l  Figure is  is  correspond  each node of the tree an  i s d i s p l a y e d . Using the  tree  can  be  displayed  of the previous  of  24.  At any  in  full  adding  to  time,  any  size.  addition i s displayed  The  in Figure  25. The  tree representation  and  breadth. Any  by  moving  This  a  p o r t i o n of the model can  leaf  of the  v i s i b l e . Figure  the  26,  structure  part,of was  root  depth  however,  the model to  previously  subobject  A f t e r e d i t i n g at t h i s l e v e l  s t r u c t u r e i n c l u d i n g the o r i g i n a l 28.  which  limited  to the root p o s i t i o n .  27 shows the s t r u c t u r e of the  been m o d i f i e d .  Figure  enabling  of  a  be d i s p l a y e d ,  representation  i s demonstrated i n F i g u r e  be manipulated,  has  i s shown only to  after i t  i s complete,  i s redrawn,  not  resulting  the in  47  Altering Figure 29. together  the  Two so  structure  top  that  p a r a l l e l . The f i n a l  level  of  the  model i s demonstrated by  superimposed  modelling  objects  are  grouped  t r a n s f o r m a t i o n s can be a p p l i e d i n  r e s u l t of the  manipulation  by  editing  is  shown i n F i g u r e 30. The  e d i t i n g process i s independent of the g r a p h i c a l  being manipulated. E l e c t r i c a l or that  diagrams, a r c h i t e c t u r a l  artwork can be e d i t e d by the same program programs  in  various  manipulated by a l i n e  file  F i g u r e 22  languages  or  drawings,  i n the same manner  data  editor.  O r i g i n a l Model  object  Image  files  can  be  48  F i g u r e 23  O r i g i n a l Tree S t r u c t u r e  49  F i g u r e 26  E d i t i n g L e v e l Change  F i g u r e 27  Subobject M o d i f i c a t i o n  F i g u r e 28  O r i g i n a l Root Redrawn  F i g u r e 29  F i g u r e 30  Structure  Alteration  Graphical Editing  Result  52  5.4 Data S t r u c t u r e s PASCAL data  types  practice  allows and  structures.  because  involved in  a  definitions.  programmers  an  This  promotes  understanding  problem.  LIG6  to e x p l i c i t l y d e f i n e t h e i r own  FORTRAN  permits  is  does  explicit  good  programming  required not  of  permit  definition  the data  data  type  of data  types  belonging to the c l a s s g r a p h i c a l output p r i m i t i v e , but a r b i t r a r y data types cannot the  be e x p l i c i t l y d e f i n e d . The t r e e  structure  of  g r a p h i c a l 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 s t r u c t u r e s i n a s i m i l a r  f a s h i o n as  the  language  LISP. Data types and s t r u c t u r e s can be i m p l i c i t l y d e f i n e d i n LISP by  interpreting  the  structure  of  a  list  as i t s data type.  D i f f e r e n t data types can be s p e c i f i e d by the l e n g t h of a l i s t of that type, which elements  of the l i s t  what  element i s i n t e r p r e t e d to be. The t r e e  data  type  a  list  s t r u c t u r e s of LIG6 can be used structures  of  in  are  the  atoms  same  or  way  as  lists,  the  or  list  LISP to d e f i n e data types i m p l i c i t l y . An example  which uses the g r a p h i c a l data base  of  LIG6  to  represent  the  a b s t r a c t data of a grammar w i l l now be presented. The  goal  of the program i s to take a grammar s p e c i f i e d i n  Backus-Naur form and produce in  an e q u i v a l e n t grammar  the form of syntax d i r e c t e d diagrams.  storing  the  grammar,  manipulating  This  specification  i s achieved  by  i t s r e p r e s e n t a t i o n , and  g e n e r a t i n g an e x t e r n a l r e p r e s e n t a t i o n i n the form of a diagram. Grammar d r i v e n often  compiler  writing  systems  [McKe70,Leca74]  do not allow i t e r a t i o n , a l t e r n a t i o n , or o p t i o n c o n s t r u c t s  53  in  the  grammar  implemented  by  specification. the  top  level  Such  constructs  alternation  construct  r e c u r s i v e d e f i n i t i o n , a l l o w i n g the grammar to two  types  of  restriction  symbols:  i s enforced  however,  is  analyzed  diagrams  have  terminals by  the  and  iteration,  must  consist  manipulated low-level  The so  and by of  and non-terminals.  program.  be  only  The same  input  grammar,  that the r e s u l t i n g  alternation,  and  option  storage  of the  structures. Three  data  types  are  required  grammar: t e r m i n a l s , non-terminals, graphical  data  representing the  two  base  to  allow  and s t r u c t u r a l elements.  structures  which  are  these types are shown i n F i g u r e  variables  TRMLST  and  NTRLST  The  interpreted  31.  In  as  addition,  are used to maintain a  r e c o r d of a l l of the t e r m i n a l s and non-terminals of the grammar, r e s p e c t i v e l y . The s t r u c t u r e s of t h e i r values  are a l s o  given  in  F i g u r e 31. As the grammar i s read TRMLST,  i n , an i n t e r n a l r e p r e s e n t a t i o n  NTRLST, and the three data  input grammar i s the simple <subprogramlist>  types i s c o n s t r u c t e d .  using If the  definition  ::= <subprogram> | <subprogramlist> <subprogram>  then  the  internal  constructed. equivalent  representation  This structure  does  given not  implement i t e r a t i o n . The i n i t i a l  i n F i g u r e 32 would be  represent  grammar because the d e f i n i t i o n  ,  the  i s using  simplest  r e c u r s i o n to  internal representation  of  any  grammar w i l l have to be manipulated to produce a s t r u c t u r e which utilizes  iteration,  alternation,  and  option  i n t e r n a l r e p r e s e n t a t i o n a f t e r manipulation  c o n s t r u c t s . The  of the above  grammar  54 Type  Type STRUCTURAL ELEMENT I s d e f i n e d by —terminals,nonterminals, or elements  Type  NON-TERMINAL TEXT  Pointed at by these elements  Pointed at by these elements  Followed by these elements  Is defined by these elements  TEXT  is  given Once  it  31  Grammar  i n Figure the  33.  desired  object,  t e r m i n a 1 s  S t o r a g e D a t a T y p e s and V a r i a b l e s  grammar r e p r e s e n t a t i o n  i s f u r t h e r m a n i p u l a t e d so t h a t  graphical  n o n  t e r m i n a 1 s  Pointed at by these elements  Figure  NTRLST  TRMLST  TERMINAL  the  syntax  i t  becomes  directed  h a s been a  model  d i a g r a m . The  created, of  the  literals  55  NTRLST  | *•  *  <subprogramlist>  <subprogram>  ••-3  •+-4  ->2 Figure  representing with  lines  32  O r i g i n a l Grammar  t h e grammar  Internal  symbols a r e  Representation  positioned  and  a n d a r r o w s a s s p e c i f i e d by t h e d e f i n i t i o n  connected pointers. A  56  NTRLST <subprogramlist>  J  Figure  more  33  grammar  34 a n d 35,  The  graphical  where dynamic would  M a n i p u l a t e d Grammar  complete  Figures  be  -*-2  <subprogram>  and  Internal Representation  i t s resulting  diagram  respectively. d a t a base  o f LIG6 l e n d s  itself  to  data s t r u c t u r e s a r e i n v o l v e d . Another  the  i s shown i n  implementation produce  of a minimal LISP  LIG6 w h i c h  could  visual  expressions  i n the s t a n d a r d cons c e l l  problems  p o s s i b l e use  interpreter in  representations format of LISP.  of  any  s-  <program>  ::=  <subprogramlist> <subprogramlist> <main> <subprogramlist> <main> <main> <main> <subprogramlist>  <subprogramlist> <subprogram> ::=  <subroutine>  ::= <subprogram> | <subprogramlist>  <subprogramlist>  <subprogram>  <subroutine> <function> <primitivedef> <blockdata>  ::= <subhead> <block> | <subhead> <parameterlist> <block>  <function> <subhead>  ::= <funchead> <parameterlist> <block> ::= SUBROUTINE < i d e n t i f i e r >  <funchead> <type>  ::= FUNCTION < i d e n t i f i e r > | <type> FUNCTION < i d e n t i f i e r > ::= INTEGER REAL COMPLEX LOGICAL GRAPHICAL VECTOR F i g u r e 34  Sample Input Grammar  58  subprogranllst  program  naln  subprogranllst  » i subprogram  TJ  subprogranllst  subprogran  subroutine —1  Function  M  prisiltivedef  '—4  biockdata  M  s u b r o u t i n e —(  SUBROUTINE  )—•  function  type  FUNCTIONj-*| I d e n t i f i e r pH  M—(  identifier  — I — paraiieterllst  —L("block  parameterllst H  type —r-< INTEGER") -{ RERL ) - ( COHPLEX ) — - ( LOGICBL ) — ( GRAPHICAL )-*| ( VECTOR )  Figure  35  Sample S y n t a x D i r e c t e d  Diagram  —  blockf^  59  Chapter  6  NEW LANGUAGE FEATURES Apart  from  the  shift  data base i s completely system  of emphasis from a system where the  hidden  from users to a data  base  and the a d d i t i o n of programmer-defined p r i m i t i v e s ,  have been a language  number  LIG6.  originality;  of  other  These  new  features  features  some were not a v a i l a b l e  have  included  varying  published  include  or  graphical  implemented operators,  there  i n the  degrees  of  i n e a r l i e r LIG v e r s i o n s but  were a v a i l a b l e elsewhere to some extent, while others been  model  previously.  The  interpretation  have  not  new f e a t u r e s  decisions,  and  of e x p r e s s i o n when d e a l i n g with  three  language c o n s t r u c t s .  6.1 To  provide  dimensional Simple  Vector Data Type  economy  data, the data type VECTOR  was  included  v a r i a b l e s , s i n g l e and multi-dimensioned  in  LIG6.  array variables,  f u n c t i o n subprograms, and statement  f u n c t i o n s of type VECTOR are  p e r m i t t e d . Vector v a r i a b l e s may be  typed  implicitly  with  the  a i d of  e x p r e s s i o n s may be passed variables  the  explicitly,  IMPLICIT  as arguments  to  or  else  statement.  Vector  subprograms.  Vector  may be equivalenced and p l a c e d i n COMMON b l o c k s . They  may not be i n i t i a l i z e d i n  a  type  declaration  or  in  a  DATA  60  statement  nor  may  or READ statements. where X, Y, and parentheses missing,  are  they be output  Vector constants are  mandatory.  Vector v a r i a b l e s may  | | * / .EQ. '.NE.  The  and  i s optional; i f  which  are  vector  RESULT TYPE  vector a d d i t i o n vector s u b t r a c t i o n vector c r o s s product vector dot product vector magnitude m u l t i p l i c a t i o n by s c a l a r d i v i s i o n by s c a l a r vector comparison vector comparison Vector  program fragment presented  of  the  arithmetic  expression  OPERATION  The  nested  (X,Y,Z)  36.  F i g u r e 36  use  Z  be assigned values  V1 + V2 V1 - V2 VI # V2 V1 . V2 |V| A * V V / A V1 .EQ. V2 V1 .NE. V2  #  form  0.0.  EXAMPLE  +  the  operators which are d e f i n e d f o r the type VECTOR  are summarized in F i g u r e OPERATOR  of  Z represent a r i t h m e t i c expressions and where the  i t d e f a u l t s to  e x p r e s s i o n s . The  or input as a u n i t with WRITE  Operators  i n F i g u r e 37 i l l u s t r a t e s  VECTOR data type. While the  expressions allow c o n c i s e algorithms,  VECTOR VECTOR VECTOR REAL REAL VECTOR VECTOR LOGICAL LOGICAL  i n c l u s i o n of  implementation  the  operators of  vector  the major use of t h i s data type w i l l  be  in g r a p h i c a l p r i m i t i v e s . Access to the i n d i v i d u a l components of v e c t o r s i s  provided  by  the three LIG6 system f u n c t i o n s , COORDX, COORDY, and COORDZ.  The  individual  identifiers access  components  using  may  be  assigned  using  the  above  an assignment statement c o n s t r u c t . Component  i s demonstrated i n the program fragment of F i g u r e  The VECTOR data type was  not supported  in  earlier  38. 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 V2(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))) r  F i g u r e 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  versions  38  Vector  Component Access  of LIG. I t i s p o s s i b l e to d e c l a r e a PASCAL vector  in  the LIG/P implementation, but o p e r a t o r s  in  graphical p r i m i t i v e s are  supports  the data  not  possible.  and n a t u r a l i n c l u s i o n The  language  type v e c t o r , but the only o p e r a t o r s  are a d d i t i o n and dot product  type  MIRA  permitted  [Magn8l],  6.2 Map Operator In scale,  addition  the  standard  graphical  r o t a t e , and translate-, LIG6 p r o v i d e s  transformation of s c a l i n g , the  to  operator  transformations  a map o p e r a t o r .  can be used t o perform any combination  r o t a t i o n , t r a n s l a t i o n , and s h e a r i n g .  keyword MAP followed by a l i s t  I t s syntax  of p o i n t s . The two l i s t s of  must  length.  have  the  same  is  of 1, 2, 3, or 4 p o i n t s , the  keyword TO, and another l i s t each  This  points  Each p o i n t may be a v e c t o r  62  constant  or  a  vector  expression  which  is  enclosed  in  parentheses. The  implementation  of  the  map  operator  s t r a i g h t f o r w a r d as i t s i n v o c a t i o n : the operator transformation those  which maps the p o i n t s  i n the f i r s t  into  need not have any  this  i s one form of the o p e r a t o r ' s  C a r e f u l c h o i c e of the p o i n t s i n the l i s t s of the standard provides  a  any  g r a p h i c a l t r a n s f o r m a t i o n s . The map operator  also  concise  method  for  transformations  facilitates  expressing with  the c o n s t r u c t i o n  t r a n s f o r m a t i o n s . Examples of the map operator these p o i n t s are given  will  use.  create  t r a n s f o r m a t i o n s . Combining the map operator  iii) iv)  list  t o c o o r d i n a t e s of the model to which the t r a n s f o r m a t i o n  i s a p p l i e d , although  i) ii)  as  creates a linear  i n the second. The p o i n t s i n the l i s t s  relation  is  shearing  the of  which  standard  interesting demonstrate  i n F i g u r e 39.  <MAP ( 0 , 0 ) , ( 1 , 0 ) TO (0,0),(COS(THETA),SIN(THETA))> <MAP ( V 1 ) , ( V 2 ) TO (V1),(V1 + S*(V2-V1))>  <MAP ( 1 , 0 ) , ( 0 , 0 ) , ( 0 , 1 ) TO ( 1 , 0 ) , ( 0 , 0 ) , ( - C O S ( T ) , S I N ( T ) ) > < MAP ( V 1 ) , ( V 2 ) TO ( 0 , 0 ) , ( | V 1 - V 2 | , 0 ) ,  ROTX THETA ,  MAP  (0,0),(|V1-V2|,0)  F i g u r e 39  In  Map Operator Examples  ( i ) produces  a  e q u i v a l e n t t o a r o t a t i o n about the z - a x i s by  an  Example  Figure  TO ( V 1 ) , ( V 2 ) >  39, example  ( i i ) performs  s c a l i n g with  by a q u a n t i t y S. Example  shearing  angle  an  T  about  amount  THETA.  respect t o the p o i n t V1  the d i r e c t i o n V2-V1 by  transformation  ( i i i ) will  the z - a x i s .  i l l u s t r a t e s compounding t r a n s f o r m a t i o n  operators.  in  cause  Example ( i v ) Its effect, i s  63  to r o t a t e o b j e c t s by an amount THETA about the a x i s s p e c i f i e d by the l i n e p a s s i n g through All  LIG6  the p o i n t s V1 and V2.  transformations  use  matrices  to  produce  the  d e s i r e d e f f e c t . The c o o r d i n a t e t r i p l e s of an o b j e c t which i s to be  transformed  [Roge76]  and  coordinates  are  then  converted  multiplied  represent  the  into by  homogeneous  a  matrix;  transformed  t r a n s f o r m a t i o n s are c r e a t e d by m u l t i p l y i n g which  rotates  objects  coordinates  the  resulting  object.  Compounded  matrices.  about the z - a x i s i s presented  A  matrix  in Figure  40.  cos(a)  sin(o) 0 0  The  the  X y z  1  1  0 0  F i g u r e 40  Z-Rotation  1  0  p Q R  -  1  Matrix  l i n e a r t r a n s f o r m a t i o n which implements the map  i s the s o l u t i o n of a matrix is  0 0 0  -sin(a) cos(a) 0 0  equation. The matrix  operator  A of F i g u r e  41  t r a n s f o r m a t i o n which implements the map operator of the  same f i g u r e . The  matrix A i s found  by s o l v i n g an equation B  of the type  (1 )  One s o l u t i o n i s -i-l  X however, t h i s  (2)  i n v o l v e s f i n d i n g the i n v e r s e of a matrix  and  then  64 <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) >  L  JL ' ' ' J  multiplying.  Map Operator  Another  solution  P  s  V  n  q  t  w  o  r  u  X  I'  1  F i g u r e 41  m  Implementation  i s to take the transpose  s i d e s of equation  1 y i e l d i n g equation  then  f o r by using a LU decomposition  be  solved  shown to i n v o l v e fewer o p e r a t i o n s p  -,  X There  T  the  [Fors67], T  A  I-  B  =  a  unique  objective, in  points  solution.  but  the not  they  plane on  the  v a r i a n t , or p o i n t s other than member one  variant.  that minimizes  two  space  to  another  set.  The  the  achieve  the  i n t h e i r e f f e c t on p o i n t s  specified  by  the  three  member  l i n e s p e c i f i e d by the two member the  one  specified  by  the one  s o l u t i o n chosen f o r these v a r i a n t s i s the  the d i s t o r t i o n of g r a p h i c a l o b j e c t s . map  operator,  the  choice  is  e q u i v a l e n t t r a n s l a t i o n t r a n s f o r m a t i o n i s used. The  and three member v a r i a n t map o p e r a t o r s  choosing  (3)  A l l solutions  differ  For the one member v a r i a n t simple:  -] T  other v a r i a n t s of the map operator are used, however,  which are not variant,  which has been  i s a unique l i n e a r t r a n s f o r m a t i o n which maps a given  there i s not mapping  of both  3. The transpose of A can  set of four p o i n t s i n three-dimensional When  J  1 1 1  additional  appropriate  are  implemented  by  p o i n t s and s o l v i n g as f o r the  65  four member v a r i a n t . The  three p o i n t s i n a l i s t  of a three member v a r i a n t d e f i n e  an o r i g i n and two v e c t o r s . The f o u r t h p o i n t chosen i s the product  of  the  perpendicular Its  length  two  vectors.  to the plane i s determined  to  both l i s t s ,  generates  d e f i n e d by the p o i n t s by  v e c t o r s . When the same process applied  This  a third in  cross vector  the  list.  the lengths of the two o r i g i n a l  of f o u r t h p o i n t s p e c i f i c a t i o n  any s c a l i n g or shearing  is  i n the plane i s  a p p l i e d n a t u r a l l y to p o i n t s o f f the plane. The origin  two p o i n t s i n a l i s t and  of a two member v a r i a n t d e f i n e  a vector. A t h i r d point  generates a v e c t o r which i s of the perpendicular  i s a r b i t r a r i l y chosen which same  magnitude  as  and i s  to the o r i g i n a l v e c t o r . The same procedure as f o r  the three member v a r i a n t i s then  6.3 Stroke There  an  are  three  levels  followed.  P r e c i s i o n Text of  text  appearance  precision:  s t r i n g , c h a r a c t e r , and stroke p r e c i s i o n text [GSPC79]. In s t r i n g precision  text,  only  the p o s i t i o n of the f i r s t c h a r a c t e r of a  s t r i n g may be s p e c i f i e d ; the s i z e and o r i e n t a t i o n of the  string  i s hardware dependent. In c h a r a c t e r p r e c i s i o n t e x t , the p o s i t i o n of  every  but  the s i z e and o r i e n t a t i o n of the  still  c h a r a c t e r of the s t r i n g  hardware  dependent. Stroke  as i f each c h a r a c t e r were transformations  apply  i s a f f e c t e d by t r a n s f o r m a t i o n s individual  characters  are  p r e c i s i o n text t r e a t s s t r i n g s  constructed  from  short  lines; a l l  t o such s t r i n g s . The d i f f e r e n c e s between  the p r e c i s i o n s are summarized i n F i g u r e 42.  66 DIAGONAL  D  <V  X  1  O  N A L  string  character Figure  The models  use of s t r i n g of  results.  generators  are capable  43 g i v e s an example  stroke  precision text.  6.4 As s o f t w a r e is  costs  made  years  which  yields  increase  poor  of  languages  such  create  relative  most  possibilities  of  t o h a r d w a r e c o s t s , more  these  qualities  a considerable  Programming  programs  i n that  constructs  PASCAL  a r e most style  easily  i s used. A  f o l l o w i n g i n recent  on t h e s t y l e i n  language.  FORTRAN  languages;  available  [Jens76].  readable,  [Dahl72].  h i g h - l e v e l programming  control as  the  because  precision text.  o f a l a n g u a g e have an e f f e c t  the o r i g i n a l  structured  of  string  c o n s i s t e n t programming  Structured  w h i c h programmers  of only  software  capability.  t h a t programs a r e c o r r e c t ,  developed  The c o n s t r u c t s  LIG6 has t h i s  using  some  Programs w i t h  has  is called  of  to ensure  maintainable.  style  objects  i n images o f  S t r u c t u r e d Statements  p r o d u c e d when a r i g o r o u s  the  graphical  images o f s t r i n g s a r e g e n e r a t e d  effort  precision text  precision capability;  Figure  one  Precision  or c h a r a c t e r  three-dimensional  stroke  hardware  and  Text  The p r e c i s e p o s i t i o n i n g a n d o r i e n t a t i o n o f t e x t s t r i n g s  requires All  42  stroke  in  Structured  more  is  i t lacks modern  programming i n  67  A 8 V ,o<3.  Dodecahedron  0  Figure  FORTRAN  has  statements statement a  been  as  by  structures  interpreting and r e s t r i c t i n g  l a b e l s and t h e GOTO s t a t e m e n t .  implementations [Frie82]  LIG6 e x t e n d s addition  Stroke P r e c i s i o n Text  accomplished  control  structured,  WATFIV/S  43  of four  modular of  FORTRAN  have  included  as  style, FORTRAN'77  structured  control  the c o n t r o l c o n s t r u c t s  of  structured constructs.  These  of  t h e usage o f  I n an e f f o r t  programming such  groups  t o promote  more  modern  [Meis77]  or  constructs.  FORTRAN  with  constructs  the  a r e an  68  IF-THEN-ELSE s t r u c t u r e , a REPEAT s t r u c t u r e , a and  a  CASE  s t r u c t u r e . The  syntactic  structure,  r u l e s of these c o n s t r u c t s  are f o r m a l l y d e f i n e d by the grammar presented of  WHILE  in Figure 4 4 .  Use  these c o n s t r u c t s i s demonstrated i n the program fragments i n  Figure  45.  <statementblock> ::= BEGIN <statementlist> END <statementlist> ::= <statement> <statseparator> | <statementlist> <statement> <statseparator> <structuredif>  ::= ::=  <statseparator>  <eol> I ;  <truepart> | <truepart>  <falsepart>  <truepart> ::= IF ( <logicalexpr> ) THEN <statementblock> <falsepart> ::= ELSE <statementblock> <repeat>  ::=  <while> ::=  REPEAT <statementlist> UNTIL ( <logicalexpr> ) WHILE ( <logicalexpr>  ) DO  <case> ::=  CASE <expression>  <caseexpr>  ::= < t r u e l i s t > <truelist> <falselist> <falselist>  <truelist>  ::=  <statementblock>  : <type> OF  <caseexpr>  <success> | < t r u e l i s t > <success>  <falselist> <success>  ::=  <exprlist>  All  '<>'  : <statementblock>  < e x p r l i s t > : <statementblock>  ::=  <expression> | < e x p r l i s t > <expression> F i g u r e 44 S t r u c t u r e d Statements Grammar  s t r u c t u r e d c o n s t r u c t s may  requirement ensures  ::=  of statement  that  all  be nested to any  depth.  l i s t s being bracketed by BEGIN and  syntactic  structures  are  The END  completely  69 IF(X.LT.Y) THEN BEGIN T=X; X=Y; Y=T; 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) 2,3 : BEGIN  END  : INTEGER OF  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 A r c h i v a t i o n Graphical interactively  application  programs  i n order to c o n s t r u c t  are  often  executed  models of g r a p h i c a l  objects.  T h i s process i s u s u a l l y 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 e x a c t l y . To c r e a t e menus  or  to continue modelling begun i n p r e v i o u s executions of a program, it  i s , necessary  retrieved. This Archivation  that  arbitrary  models  can  be  stored  and  i s implemented i n LIG6 by a r c h i v a t i o n . i s the saving  on and r e s t o r i n g  from  secondary  70  storage  models  of  graphical  objects.  models between d i f f e r e n t programs or to for  a  subsequent  statements  which  statement,  are  of  are  save  generated  models  the  same  program. There are three  involved  with  archivation:  the POSITION statement,  There of  run  I t can be used to pass  and the LOAD  the  STORE  statement.  two forms of the s t o r e statement.  Some examples  t h i s type of statement are  STORE STORE STORE STORE  ON ON ON ON  UNIT UNIT UNIT UNIT  7,BIRD N+2,FOWL 3, VALUE(LAST(A)) 3,. IDENTIFICATION 7.5, A  STORE ON UNIT 3, IDENTIFICATION 3*R, A The the  i n t e g e r valued e x p r e s s i o n f o l l o w i n g the keyword UNIT i s  logical  I/O  u n i t on which the model i s s t o r e d . I t must be  assigned t o a d i s k f i l e  on the run command or with a FORTRAN I/O  subprogram. The r e a l valued IDENTIFICATION  expression  i s 0.0. The  of  the  file  The a r c h i v a t i o n additional  the  in  order  random access  i s t o s t o r e at the  file  object  item.  i s i n the form of a  in can  which be  sequential  tape.  i s p l a c e d a t the end of the tape. When  they a r e l a t e r loaded, the l o a d i n g w i l l occur as  item  a header and codes which represent the model  which i s the value of the l a s t  Each  last  i s a g r a p h i c a l v a r i a b l e or f u n c t i o n i n v o c a t i o n whose  value i s a node. The e f f e c t of the statement end  keyword  so that i t can be i d e n t i f i e d l a t e r . The  d e f a u l t value f o r the i d e n t i f i c a t i o n list  the  i s a number which i s p l a c e d i n the header of the  s t o r e d model i n the f i l e  the  following  i n the same  order  they were s t o r e d . A c e r t a i n degree of  obtained,  however,  with  the  position  statement. The  position  statement  i s used to p o s i t i o n an a r c h i v a t i o n  71  f i l e at the d e s i r e d model storage. t h i s statement POSITION POSITION POSITION POSITION POSITION  UNIT UNIT UNIT UNIT UNIT  The  follow. 2 N+3,5.5 3,4.*Q 3,7.2,2 3,,2  first  a r i t h m e t i c expression  keyword i s the u n i t e x p r e s s i o n ; has  the  same  expression valued.  meaning  as  i s the i d e n t i f i c a t i o n  be i n t e g e r valued.  The  i n the l i s t  i t must be  in  The t h i r d expression  expression  Examples of p o s s i b l e forms of  f o l l o w i n g the  integer  valued  the s t o r e statement. The second expression;  i t must  be  i s the v e r s i o n e x p r e s s i o n ;  default  and  value  i s 0.0. The d e f a u l t value  f o r the  real  i t must  identification  f o r the v e r s i o n  expression  i s 0. The e f f e c t of the statement i s tp p o s i t i o n the file  attached  identification  to  the  unit  at  instance  of a model being  version  number  default  file  is  s p e c i f i e d v e r s i o n of the  the  model  storage  s t o r e d with 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  values,  value  of  0.0  second  7.2. I f the  will  match  all  thus the l a s t statement w i l l p o s i t i o n the  t o the l a s t model  statement  i n the a r c h i v a t i o n f i l e at i t s present  model.  The  model  p o s i t i o n i s loaded  i n t o the g r a p h i c a l v a r i a b l e s p e c i f i e d . An example i s LOAD FROM UNIT N+2, BIRD  will  stored.  The load statement i s used to r e s t o r e a stored  the  i s p o s i t i o n e d . The  to the second model s t o r e d , while the f i r s t  p o s i t i o n the f i l e  of  0, the l a s t model s t o r e d with the s p e c i f i e d  identification  identification  the  v a l u e . The f o u r t h statement i n the examples above  w i l l p o s i t i o n the f i l e  identification  at  archivation  72  Chapter  7  CONCLUSIONS E a r l i e r v e r s i o n s of LIG p r e p r o c e s s o r s d i d not host  language statements  analyze  the  of a program. LIG6, the r e s e a r c h t o p i c  of t h i s t h e s i s , analyzes both the FORTRAN and language extension statements.  The primary  constructs  of  LIG6  reason  for this  cannot be e a s i l y  are s t r i c t l y FORTRAN and those which There  i s considerable  overlap  i s that split  are  between  language  up i n t o those which  strictly  extensions.  the c o n s t r u c t s , as i s  evident by the number of FORTRAN statements extension  the  which  may  contain  elements.  Several  benefits  are  realizable  when-all  statements are  analyzed. There i s no need t o demarcate extension statements the  use  of  a  special  c h a r a c t e r i n a designated column or by  other means. I t i s p o s s i b l e to mix host and e x t e n s i o n on a s i n g l e l i n e . Any s y n t a c t i c statements  which  preprocessor moved  one  generation  would  output step  not  to  in  the  be  detected  statements  host  language u n t i l the  are trapped. The preprocessor i s  being  a  compiler;  object  code  i s only p o s s i b l e when complete p a r s i n g i s performed.  Another  difference  i s the implementation  between LIG6 and p r e v i o u s LIG v e r s i o n s  of the p r e p r o c e s s o r . The LIG6 preprocessor  does not make use of a Compiler written  errors normally  i s compiled  closer  by  completely  in  Writing  PASCAL.  There  System are  (CWS); several  i t is factors  73  supporting t h i s choice. systems  Currently  [McKe70,Leca74]  conventions required.  of  do  FORTRAN;  With  a CWS,  not  a  LIG6  and  writing  f r e e form input  reserved  programmers.  original  words  primitives  which  affect  must be able to handle  the  extensions  generated  include  parsers  specifications. the d e f i n i t i o n of  parser.  The  of as a load and  s p e c i f i c grammar. A preprocessor  created  without  ad hoc  concentrated been  i n t h i s way;  techniques which p r o v i d e more e f f i c i e n t  Current  expended  systems  research in  two  in  computer  graphics  the  standards  [GSPC79,Fole76].  Such  for  systems  c r e a t i o n of r e a l i s t i c  The  The  research  in  appears  a n a l y z i n g scenes,  to  area  is  be has  graphical  subroutine  are  to  used  create  not  images. T h i s area c o n t a i n s hidden  this  of  execution.  provide  other area of intense i n t e r e s t  s u r f a c e removal, shadowing, shading, and  a  utilize  d i s t i n c t a r e a s . A great d e a l of e f f o r t  regarding  features.  of use  i t can  p o r t a b l e g r a p h i c s a p p l i c a t i o n programs but they do modelling  CWS.  general grammars, i t cannot characterstics  a i d s i s not l i m i t e d  LIG6 go  exploit  driven  are  language  which  grammar  preprocessors  Such  grammar  i t s e l f can thus be thought  Because a CWS generate  by  s o l e l y by the  constructs  preprocessor  the  a l t e r a b l e p a r s e r ; CWS  programmer-defined  syntactic  compiler  i t i s not p o s s i b l e to c a r r y out  dynamically  are determined  support  delimiters  extensions which are d e f i n e d require  available  texturing  concerned  i s the  line  and  algorithms.  with the process of  not with the models on which the  analysis  is  based. H i g h - l e v e l g r a p h i c a l programming languages are an to  graphical  subroutine  extension  systems. They provide a data base and  74  the c a p a b i l i t y to n a t u r a l l y model g r a p h i c a l o b j e c t s . I t i s with  the a d d i t i o n of i n q u i r y , however, that such a language can  form a bridge between the two level  language  objects,  but  can  areas  facilitate  constructs  of c u r r e n t  the  must  be  r e s e a r c h . A high-  modelling available  of  graphical  which  allow  a n a l y s i s of those models i f complex g r a p h i c a l a l g o r i t h m s be  are  the to  implemented. The  data  base  approach  of  LIG6 permits  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 . Use experiments with g r a p h i c a l algorithms to  only  be  modelled  naturally.  Any  of  the a n a l y s i s of  LIG6  to  perform  allows the scenes r e q u i r e d  algorithms  implemented are then a v a i l a b l e f o r use  so  in a l l  devised  LIG6  and  application  programs. A  language  facility example MAX  is of  can be considered  provided such  which  a facility  was  to have been expanded when a previously  These  facilities  are  variable  usually  number  implemented  systems programmer because the language c o n s t r u c t s do not their direct has  no  implementation. T h i s i s e x e m p l i f i e d by MAX:  method  An  f o r FORTRAN i s the system f u n c t i o n  which r e t u r n s the maximum value of i t s  parameters.  unavailable.  of . s p e c i f y i n g  a  variable  number  of  by  of a  permit FORTRAN formal  parameters. I t i s p o s s i b l e f o r non-systems programmers to expand a  language, however, i f the language's c o n s t r u c t s form a k e r n e l  which i s complete in i t s a b i l i t y  to  manipulate  the  language's  data s t r u c t u r e s . The  language c o n s t r u c t s of LIG6 provide  p o s s i b l e data base values  can  assignment  a l l modelling  statements and  be  created  such a k e r n e l . A l l using  the  various  r e s u l t s can be  accessed  75  and m o d i f i e d . The s u r f a c e generation c o n s t r u c t i o n t o o l s and the editing  u t i l i t y d e s c r i b e d i n Chapter 5 form language  extensions  which use only LIG6 modules. The  ability  implies  that  of  the  non-systems  system  programmers  will  be  augmented by any person  used f a c i l i t i e s can s t i l l improve  efficiency;  fluent  a  task  e x i s t i n g a l g o r i t h m implementation The  general  applications  systems  will  be  programmer  to  s i m p l i f i e d by the  i n the h i g h - l e v e l c o n s t r u c t s .  a b i l i t i e s of LIG6 compare f a v o r a b l y with those of other  high-level  graphics  functions  of  LIG6  from the use of provide  a  pictorial permit  LIG6  i n the language. H e a v i l y  be coded by a  such  expand  be able to evolve much f a s t e r .  L i b r a r i e s of r o u t i n e s which are u s e f u l i n can  to  languages. have  previous  natural  and  The  analysis  and  display  b e n e f i t t e d from the experience versions  of  the  human-oriented  i n f o r m a t i o n . The advanced  the  modelling  of p i c t o r i a l  LIG  method  level  gained  family. of  They  displaying  constructs  of  LIG6  information; t h i s a b i l i t y i s  not a v a i l a b l e with any other g r a p h i c s language  using  graphical  constructs. An of  evaluation  of LIG6 can be d e r i v e d from the experiences  a summer student.  electrical graphics  engineering  the  programming  computer  science  the student  of  1982,  was  a  hired  second-year to  create a  a n a l y s i s program. T h i s  experience  consisted  of  a  student's first-year  course d e a l i n g with FORTRAN and ASSEMBLER and  j o b - r e l a t e d experience previous  summer  undergraduate  i n t e r f a c e to a c i r c u i t  previous  no  In  u s i n g a microcomputer and BASIC.  graphics experience.  He  had  A f t e r a short p e r i o d i n which  became f a m i l i a r with g r a p h i c a l terms  and  concepts,  76  he was  e a s i l y able to produce g r a p h i c a l output  The  task f o r which the student was  using LIG6.  h i r e d , however, e n t a i l s  more than the generation of images. I t i n v o l v e s the c r e a t i o n  of  a m a i n t a i n a b l e , expandable program using the g r a p h i c a l data base to  generate  both  an  image  of  an  arbitrary  s p e c i f i c a t i o n of that c i r c u i t  which can  analysis  encouraging  program.  Although  t h i s work proceeded Two minimal  be  understood  programming experience  advanced  sophisticated manipulation lists  is  level  algorithms. of  from  dynamic  especially  is  the  b e n e f i c i a l . The point and work  where  run-time to  constructs Experience  this  of with  useful.  Such  are  only  required  LIG6  to  the  experience  is  to  implement  design  PASCAL and  and linked  common  in  LISP.  case with most p r o j e c t s , f u r t h e r work would be implementation  it  of  LIG6  has  proceeded  i s a u s e f u l g r a p h i c a l system. The  improve  to  the  preprocessor  l i b r a r y are complete and have been t e s t e d .  Further  the system i n v o l v e s i n c r e a s i n g the number and language  LIG6  assumes  a l l d e v i c e s have the same, high q u a l i t y c a p a b i l i t i e s . T h i s  i s f a r from the case. I t i s the task of the approximate  or  which are l a c k i n g the  experience:  data s t r u c t u r e s , p o i n t e r s , and  c a p a b i l i t i e s of the device d r i v e r s . The that  the  i s needed to use LIG6 to produce  programmers f a m i l i a r with the languages As  by  more s l o w l y .  c o n c l u s i o n s can be drawn  the  and a  r e s u l t s were obtained,  g r a p h i c a l output, but more programming s k i l l s use  circuit  drivers  the system.  simulate  those  features  device expected  drivers  by LIG6 but  i n the d e v i c e addressed. At the present  support  to  time,  only a subset of the f e a t u r e s expected  by  77  The is  a  only c o l o u r t e r m i n a l p r e s e n t l y connected to the  Tektronix  4027.  This  terminal  system  i s capable of d i s p l a y i n g . 0  e i g h t of a p o s s i b l e s i x t y - f o u r c o l o u r s eight  colours  yellow,  currently  green,  realistic  cyan,  results  and  black.  two  colours.  perceives green  can  This  orthogonal  An  approach  intended  yielding  more eight  image.  i s to devise a metric  research  possible model  of equal  so  that  into  metric  and  the  i s to use  assume  the  way  the  a  the red,  colour  eye blue,  axes  are  l e n g t h . Once the p a l e t t e , of c o l o u r s  been determined, the metric the  The  be a s s o c i a t e d with the d i f f e r e n c e between  A  colour and  first  requires  colour.  (RBG)  time.  d i s t i n c t problems i n v o l v e d i n using a v a r y i n g  p a l e t t e of c o l o u r s . The value  one  be f o r the driver- to choose the  c o l o u r s which best matched the  numerical  any  chosen are white, b l u e , magenta, red,  would  There are two  at  i s used to choose  which  has  colour  of  p a l e t t e best approximates the c o l o u r an a p p l i c a t i o n program  wishes to d i s p l a y . The screen  second problem i s the c h o i c e of p a l e t t e members a f t e r a  r e f r e s h . At that time, a l l  appear  on  the one  where the sum  involved  the  is  screen  the  of  the  are known. The  of the  distance  errors between  colours  which  optimum p a l e t t e choice is  minimized.  The  an exhaustive  search  to  each  consider  (roughly  the c o l o u r d e s i r e d and  the  there  4.4*10 ) p o s s i b l e p a l e t t e s , 9  i s not p r a c t i c a l . A p o s s i b l e palette  is  error  c l o s e s t c o l o u r of the p a l e t t e as d e f i n e d by the m e t r i c . As are s i x t y - f o u r choose e i g h t  will  heuristic  c o l o u r as a data c o n c e n t r a t o r ,  d e s i r e d c o l o u r as a t e r m i n a l , the metric  value  between  is each  colours  78  as  the  terminal-concentrator  Drop a l g o r i t h m s concentrator  be  the  to  monochromatic  LIG6  are  devices.  Tektronix  Two  such  devices  4010 s e r i e s t e r m i n a l s and a d i s p l a y s a l l c o l o u r s i n the  c o l o u r of these d e v i c e s . A p o s s i b l e improvement would  approximation  of c o l o u r on these d e v i c e s by the use of  hatching. Several options could  be  could  space  be  [Schw77] to determine  location / palette colour.  p l o t t e r . The c u r r e n t implementation foreground  cost and to use the Add or  from communications theory  There a r e many interfaced  link  performed  in  image  images of s u r f a c e s with the same orientation  and  spacing  implemented.  hatching  with the r e s u l t that a l l  colour  of  The  would  hatch  have  lines.  the  same  Secondly,  the  o r i e n t a t i o n of the s u r f a c e s  of  the  model  determine  of  the  hatching of the image. The  the  orientation  hatching c o u l d a l s o be performed i n object both  the  orientation  and  spacing  of  could  space the  be  used  resulting  hatch  lines  a f f e c t e d . The l a s t two implementations would p r o v i d e the with  additional  information  to  in  being viewer  regarding depth and the modelling  process. The more  p o r t r a y a l of three-dimensional  meaningful  i f hidden  LIG6 i s concerned with dimensional  objects,  the  information  l i n e s and s u r f a c e s are removed. As modelling  and  p o s s i b l e t o place these algorithms  system because such a l g o r i t h m s output can  display  the a d d i t i o n of a hidden  removal c a p a b i l i t y would be an important be  i s usually  are  of  l i n e and surface  improvement.  used  with  raster  usually  terminals  It  would  i n the d r i v e r part of the dependent  d e v i c e . For example, a p r i o r i t y b u f f e r a l g o r i t h m  be  three-  on  the  [Fole82]  but not with d i r e c t view  79  storage  tubes or  Most  terminal  information. object depth. for  plotters.  Interacting  is difficult It  locators  because  provide  with  an  there  only  two-dimensional  image of a  three-dimensional  is  no  method  to  i s p o s s i b l e to implement a three-dimensional  a vector  r e f r e s h t e r m i n a l using  three v a l u a t o r  inputs.  system through a point  determined  Experiments c o u l d be c a r r i e d out  by  locator  i n p u t s . Three  c r o s s - h a i r s would be drawn p a r a l l e l to the axes of the coordinate  indicate  the  modelling valuator  to determine i f f i n i t e  l e n g t h c r o s s - h a i r s or c r o s s - h a i r s which i n c l u d e marks are r e q u i r e d to a s s i s t a user's depth  measuring  perception.  tick  80  BIBLIOGRAPHY  [ B a r t 8 l ] Barth, W., J . D i r n b e r g e r , and W. Purgathofer, The h i g h level graphics programming language PASCAL/GRAPH, Proc. Eurographics 81, Amsterdam, North-Holland, 1981, 1511 64. [Dahl72] Dahl O-J., Dijkstra, E. W. , Hoare, C., Programming, Academic Press, New York, '1972.  Structured  [Dijk76] D i j k s t r a , E. W., A D i s c i p l i n e of Programming, P r e n t i c e H a l l , Inc., Englewood C l i f f s , New J e r s e y , 1976. [Fole76] F o l e y , J . D., Picture Naming and M o d i f i c a t i o n : an Overview, Computer Graphics 10, Spring 1976, pp. 49-53. [Fole82] F o l e y , J . D., Van Dam, A., Fundamentals of Interactive Computer Graphics, Addison-Wesley, Reading, Massachusetts, 1 982. [Fors67] F o r s y t h e , G. E., Moler, C. B., Computer S o l u t i o n s of Linear A l g e b r a i c Systems, P r e n t i c e - H a l l , Inc., Englewood C l i f f s , New J e r s e y , 1967. [ F r i e 8 2 ] Friedman, F. L., Koffman, E. B., Problem Solving and Structured Programming i n WATFIV, Addison-Wesley, Reading, Massachusetts, 1982. [GSPC79] Heilman, R., Herzog, B. ( E d s . ) , Status Report of the Graphics Standards Planning Committee, Computer Graphics 13, No. 3, August 1979. [Jens76] Jensen, K., Wirth, N., PASCAL: User Manual and S p r i n g e r - V e r l a g , New York, 1976. [Kuls68] Kulsrud, H.E., A general Comm. ACM, 11 (1968), 247-254.  purpose  graphic  Report, language,  [Leca74] Lecarme, 0., and G.V. Bochmann, A (truly) usable portable compiler writing system, Information P r o c e s s i n g 74, Amsterdam, North-Holland, 2(1974), 218-221. [Magn8l] Magnenat-Thalmann, N., and D. Thalmann, A g r a p h i c a l Pascal extension based on g r a p h i c a l types, Software — P r a c t i c e and Experience, 11 (1981), 53-62.  81  [ M a i r 8 l ] Mair, S. G. (Ed.), UBC IG: The I n t e g r a t e d Graphics System, Computing Centre, The U n i v e r s i t y of B r i t i s h Columbia, 1982. [Mann80] Mannhardt, Ch., and G.F. Schrack, M o d e l l i n g and d i s p l a y concepts i n a h i g h - l e v e l g r a p h i c s programming language, C.E. Vandoni, Ed., E u r o g r a p h i c s 80, Amsterdam, NorthH o l l a n d 1980, 225-236. [McKe70] McKeeman, W.M., J . J . Horning, and D.B. Wortman, A Compiler Generator, Englewood C l i f f s , P r e n t i c e - H a l l , 1970. [McLe78] McLean, M.J., A survey of i n t e r a c t i v e software, A u s t r a l . Comput. J . , 10 (1978), 11-22. [Meis77] Meissner, L. P., FORTRAN 77, SIGPLAN Not. 12, no. 1 (Jan. 1977), pp. 93-94.  graphics  (USA), v o l .  [Newm7l] Newman, W.M., D i s p l a y procedures, Comm. ACM, 14 (1971), 651-660. [Roge76] Rogers, D. F., Adams, J . A., Mathematical Elements f o r Computer G r a p h i c s , McGraw-Hill, New York, 1976. [Ross82] Ross, R., LIG6; Language f o r I n t e r a c t i v e Graphics, User's Manual, Department of E l e c t r i c a l E n g i n e e r i n g , The U n i v e r s i t y of B r i t i s h Columbia, 1982, 55 pp. [Schr76] Schrack, G.F., Design, implementation and experiences with a high-level g r a p h i c s language for interactive computer-aided design purposes, Computer G r a p h i c s , 10 (Spring 1976) and SIGPLAN N o t i c e s , 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 E n g i n e e r i n g and Computer S c i e n c e , The U n i v e r s i t y of B r i t i s h Columbia, 1978, 50 pp. [Schw77] Schwartz, M., Computer-Communicat ion Network Design and A n a l y s i s, Prentice-Hall, I n c . , Englewood C l i f f s , New J e r s e y , 1977. [ S m i t 7 l ] Smith, D.N., GPL/l — A PL/I e x t e n s i o n f o r computer g r a p h i c s , AFIPS Conf. Proc. 38 (1971: SJCC), 511-528. [Thal79] Thalmann, D., Magnenat-Thalmann, N., Design and Implementation of A b s t r a c t Graphical Data Types, Proc. COMPSAC'79, Chicago, IEEE Press, 1979, pp. 519-524. [Wirt77] Wirth, N., What can we do about the unnecessary diversity of notation for syntactic definitions?, Comm. ACM, 20 (1977), 822-823.  82  APPENDIX A  A Sample P r o g r a m  The the  L I G 6 p r o g r a m shown on t h e f o l l o w i n g p a g e s d e m o n s t r a t e s  ability  algorithms. priority It  of the language t o implement The  graphical  buffer hidden surface  returns  appear.  graphical  HIDDEN i s an e x a m p l e o f a  removal algorithm  a model w h i c h i s e q u i v a l e n t  s t r u c t u r e h a s been m o d i f i e d raster  function  interesting  implementation.  t o i t s a r g u m e n t b u t whose  so t h a t when i t i s  displayed  r e f r e s h t e r m i n a l , t h e h i d d e n l i n e s and s u r f a c e s  on  will  a not  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  10  20  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| 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| 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  The  language LIG6  British  Columbia  is  implemented  Computing  under t h e M i c h i g a n T e r m i n a l following time  MTS  library  Notes  Centre's System  commands w i l l  on  the  Amdahl  University  of  470 V/8 computer  (MTS) o p e r a t i n g  system.  The  g e n e r a t e t h e p r e p r o c e s s o r and r u n -  a n d e x e c u t e a LIG6 p r o g r a m c o n t a i n e d  in  the  file  PROG.S. $RUN $RUN $RUN $RUN $RUN  *PASCAL SCARDS=LIG6.P SPUNCH=LIG6.0 *FTN SCARDS=LIG6.LIB.F SPUNCH=LIG6.LIB.O LIG6.0 SCARDS=PROG.S SPRINT=PROG.L SPUNCH=PROG.F *FTN SCARDS=PR0G.F SPUNCH=PROG.0 PR0G.0+LIG6.LIB.0 The  following  e t a l . [McKe70],  LIG6  LIG6  "T" d i a g r a m s , u s i n g  represent  the notation  t h e same p r o c e s s .  LIG6  PREPROCESSOR  -->  FORTRAN PASCAL  PASCAL  PASCAL  o f McKeeman  PREPROCESSOR  LIG6  -->  ML  ML  COMPILER  —>  ML  FORTRAN  87  LIG6  LIG6  LIBRARY  LIBRARY FORTRAN COMPILER FORTRAN  ML  ML  -->  FORTRAN  ML  Program  Program  Program  FORTRAN COMPILER  LIG6 PREPROCESSOR —>  LIG6  LIG6  - ->  FORTRAN  FORTRAN  FORTRAN  ML  ML  Several have  been  consists  disk  statistics obtained.  regarding  represents  file  preprocessor  was w r i t t e n  168  18,100  of over  pages  code r e s u l t i n g  source  implementation  totalling  a listing  containing  b y t e s ) . The o b j e c t  the  The p r e p r o c e s s o r  o f 328 p r o c e d u r e s  code. T h i s  (each  disk  from t h e  requires a disk  examples  of  s e c o n d s o f CPU t i m e a n d  file  analyze  the  program,  a l l syntactic cost create  $1.08 an  of  LIG6  i n PASCAL; i t  lines  of  source  300 p a g e s and o c c u p i e s  for  page c o n t a i n s  compilation  of  a  4096 the  o f 84 p a g e s . I t t a k e s  0.413 s e c o n d s o f CPU t i m e t o l o a d . A 650 l i n e containing  ML  ML  LIG6 t e s t  constructs the  equivalent  program  took  preprocessor 1660 l i n e  3.449 to  FORTRAN  88  program, and produce a listing  listing.  In  comparison,  the  cost  the same program was $0.50.  The  translation  of  a  LIG6  program  into  an e q u i v a l e n t  FORTRAN program i n v o l v e s the replacement of extension with c a l l s t o subroutines graphical  information  in a  in  a  run-time  library.  constructs  The  concise  LIG6 statement g e n e r a l l y  requires  more than one subroutine  c a l l to be e q u i v a l e n t l y expressed.  actual  occurs  expansion  preprocessed.  that  depends  equivalent  the its  FORTRAN  code,  structure  equivalent  the  is  145  section  to  automatically  generate  diagrams of t h i s t h e s i s i s 197 l i n e s  FORTRAN code i s 364 l i n e s y i e l d i n g  l i n e s long;  being  was 134 l i n e s long. The  an  f a c t o r of 1.85. The hidden surface removal a l g o r i t h m A  The  was 530 l i n e s , an expansion f a c t o r of  A LIG6 program which was used data  upon the program  In the t e s t program mentioned above,  d e a l i n g with p u r e l y g r a p h i c a l extensions  3.96.  of  i t s equivalent  long;  expansion of Appendix  FORTRAN code i s 428 l i n e s  y i e l d i n g an expansion f a c t o r of 2.95. The 339  run-time l i b r a r y was w r i t t e n  procedures t o t a l l i n g  represents pages. and  a listing  The  10,232  i n FORTRAN; i t c o n s i s t s of  lines  of  source  of 166 pages and occupies  resulting  code.  This  a disk f i l e  of 95  object code r e q u i r e s a 70 page d i s k  takes 0.402 seconds of CPU time to l o a d .  file  

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 9 28
United States 8 0
Japan 4 0
Australia 1 0
Armenia 1 0
France 1 0
India 1 0
City Views Downloads
Beijing 5 0
Shenzhen 4 28
Tokyo 4 0
Ashburn 3 0
Unknown 2 24
Mountain View 2 0
Mumbai 1 0
Montgomery 1 0
Melbourne 1 0
Albuquerque 1 0
Wilmington 1 0

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

Share

Embed

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

Comment

Related Items