UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Concepts for a high level programming language for regional computer graphics Liu, Bobby Hin Wah 1979

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

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

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

Full Text

CONCEPTS FOR A HIGH LEVEL PROGRAMMING LANGUAGE FOR REGIONAL COMPUTER GRAPHICS "by Bobby Hin Wan L i u B.Eng., McMaster U n i v e r s i t y 1 9 7 7 A THESIS SUBMITTED IN PARTIAL. FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE i n THE FACULTY OF GRADUATE STUDIES Department Of E l e c t r i c a l E ngineering We accept t h i s t h e s i s as conforming t o the r e q u i r e d standard THE UNIVERSITY OF BRITISH COLUMBIA J u l y , 1979 © Bobby Hin Wah L i u , 1979 In presenting th i s thesis in pa r t i a l fu l f i lment of the requirements for an advanced degree at the Univers ity of B r i t i s h Columbia, I agree that the Library shal l make i t f ree ly avai lable for reference and study. I further agree that permission for extensive copying of th i s thesis for scholarly purposes may be granted by the Head of my Department or by his representatives. It i s understood that copying or publ icat ion of th i s thesis for f inanc ia l gain shal l not be allowed without my written permission. Department n f E l e c t r i c a l Engineering The Univers ity of B r i t i s h Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 n . t p J " l y ^  1979-ABSTRACT Researchers developing h i g h - l e v e l graphics languages have, according t o the l i t e r a t u r e , focused t h e i r a t t e n t i o n towards l i n e -drawing g r a p h i c s . L i t t l e e f f o r t has been devoted t o systematic i n v e s t i -gations of languages t h a t handle g r a p h i c a l data r e p r e s e n t i n g l i n e -drawings as w e l l as s o l i d areas. The l a t t e r type of g r a p h i c a l data i s u s u a l l y represented hy o u t l i n e s , and s o l i d area p r o p e r t i e s are v i s u a l -i z e d "by hatching or f i l l i n g techniques. A study of the l i t e r a t u r e on programming languages leads t o the c o n c l u s i o n t h a t g r a p h i c a l data should be t r e a t e d as a data type. Based on the concept of t r e a t i n g g r a p h i c a l data as a data type i n i t s own ri g h t , ' the mathematical and conceptual aspects of t h i s type of data are i n v e s t i g a t e d and e s t a b l i s h e d . Much s c a t t e r e d i n f o r m a t i o n , such as the r e p r e s e n t a t i o n of r e g i o n s , has been u n i f i e d u s i n g formal d e s c r i p t i o n s . Hatching, one of the many ways of a c h i e v i n g e x t e r n a l r e p r e s e n t a t i o n of r e g i o n s , i s a l s o i n v e s t i g a t e d . A hatching a l g o r i t h m i s proposed and implemented t h a t envelops the good f e a t u r e s of o t h e r s , and e s t a b l i s h e s a framework f o r h a t c h i n g a l g o r i t h m s . I t s implementation achieves the expected t a s k s . A proposal f o r a graphics language demon-s t r a t e s the usef u l n e s s and f e a s i b i l i t y of t h i s type of g r a p h i c s . Some of i t s f e a t u r e s have been implemented. F i n a l l y , a f a i r l y complete b i b l i graphy serves as a gateway f o r f u r t h e r r e s e a r c h i n t h i s area.' i i i TABLE OF CONTENTS Page ABSTRACT i x TABLE OF CONTENTS. i i i LIST OF TABLE. v i LIST OF FIGURES. ". v i i ACKNOWLEDGEMENT x 1. INTRODUCTION 1 2. EXTERNAL REPRESENTATION MODELS FOR GRAPHICAL DATA 3 2 . 1 General Concepts 3 2 . 2 E x t e r n a l Representation Models 3 2 . 3 V i r t u e s and L i m i t a t i o n s of the L i n e a l and Regional E x t e r n a l Representation Models 5 3. INTERNAL AND EXTERNAL REPRESENTATIONS OF REGIONS 9 3 . 1 Background 9 3 . 2 I n t e r n a l Representations of Regions 11 3 . 2 . 1 The 'encoding of the boundaries' Scheme 11 3 . 2 . 2 The ' p a r a l l e l coding' Scheme 13 3 . 2 . 3 The 'skeleton' Scheme 15 3 . 3 A Formal Representation of a Region 18 l i . THE CONCEPTS AND TECHNIQUES OF HATCHING . 21 11.1 D e f i n i t i o n s 21 11.2 A Short Review of Hatching Algorithms 22 11.3 General Concepts o f Hatching 25 • .  >• l+,li The Conceptual and Mathematical Elements f o r Hatching Algorithms 26 l i , l i , l Transformations 27 It,li.2 I n t e r s e c t i o n between two l i n e s 28 i v Page U,H,3 T o p o l o g i c a l P r o p e r t i e s , 29 D e f i n i t i o n s f o r S i n g u l a r p o i n t s . 32 h,k.5 Generation of a Hatching L i n e 3^ U. 5 The Developed Hatching A l g o r i t h m 38 h.5.1 . A Formal Representation of a Hatching P a t t e r n i n the Developed Hatching A l g o r i t h m 39 k.5.2. The Al g o r i t h m HATCH . hi h.5-3 A D e s c r i p t i o n of the Developed Hatching A l g o r i t h m . h3 h.5.3.1 A Short Note on the M a n i p u l a t i o n of .. a R e a l i z a t i o n Region h3 ^. 5.3.2 D e s c r i p t i o n of the A l g o r i t h m HATCH . . . . i+5 h.^.h E v a l u a t i o n of the Developed Hatching A l g o r i t h m . . . U6 U. 5. 5 Future work h6 5. A SHORT REVIEW OF TWO GRAPHICS LANGUAGES 52 5.1 Review of Newman and S p r o u l l ' s Work 52 5.2 Comments on Newman and S p r o u l l ' s Work 53 5.3 Review of B r a c c h i and F e r r a r i ' s Work . 5'+ 5-U Comments on B r a c c h i and F e r r a r i ' s Work 56 6/ A PROPOSED REGIONAL GRAPHICS LANGUAGE 58 6.1 A Formal D e s c r i p t i o n of a G r a p h i c a l Object i n the Proposed Regional Graphics Language, u s i n g the Regional E x t e r n a l Representation Model 58 6.2 The Regional Graphics Language LIGE 60 6.2.1 A G r a p h i c a l D e c l a r a t i o n Statement 6 l 6.2.2 A Proposed Set of G r a p h i c a l P r i m i t i v e s f o r LIGE , . 6 l 6.2.3 A Proposed Set of G r a p h i c a l Operators f o r LIGE. . . 66 6,2.1* A t t r i b u t e E x t r a c t i o n Statements f o r LIGE. . . . . . TO V 6.2.5 I/O Statements f o r LIGE 71 6.2.6 A G r a p h i c a l Function f o r LIGE . . . . . . . . . . . 73 7. CONCLUSIONS 75 BIBLIOGRAPHY ' 77 APPENDIX A AREA OF A SIMPLY CLOSED POLYGON 85 APPENDIX B LIGE HOMOGENEOUS TRANSFORMATION MATRICES 86 APPENDIX C THE CALCULATION OF THE AREA OF A GRAPHICAL OBJECT. . . . 87 APPENDIX D THE CONSTRUCTION OF THE LIGE PREPROCESSOR 92 APPENDIX E AUTHORS SORTED BY SUBJECTS 9h V I LIST OF TABLE Table Page C , l G r a p h i c a l p r i m i t i v e s and i t s a s s o c i a t e d k^values, ..' 91 v i i LIST OF FIGURES Figure Page 2.1 The l i n e a l e x t e r n a l r e p r e s e n t a t i o n model. h 2.2 The r e g i o n a l e x t e r n a l r e p r e s e n t a t i o n model< 5 2.3 Examples of g r a p h i c a l o b j e c t s t h a t r e q u i r e e x t r a care i n d e f i n i n g the s t a r t i n g and end p o i n t s v i t h a l i n e a l e x t e r n a l r e p r e s e n t a t i o n model . . . . 6 2.1+ D i g i t s and characters d e s c r i b e d on squares 8 3.1 Examples of d i f f e r e n t types of regions 10 3.2 Examples of d i f f e r e n t types of curves 10 3.3 An example of a boundary s e c t i o n enclosed w i t h i n a boundary s e c t i o n r e c t a n g l e 11 3.1) Freeman's encoding scheme 12 3.5 M e r r i l l ' s scheme Ill 3.6 P f a l t z and Rosenfeld's.scheme 16 3.7 A hatched map obtained through the use of P f a l t z and Rosenfeld's scheme IT 3.8 D i r e c t i o n convention 19 3-9 A convention used f o r d e f i n i n g a r e g i o n 19 3.10 A simply c l o s e d polygon 20 k.l An example of a hatching p a t t e r n 21 li . 2 An example of a r e g i o n t h a t has been f i l l e d 22 k,3 An example of a shaded obj e c t 22 k.k Shading of compound polygon 23 k. 5 Example - P l o t output 2k k.6 Hatching p a t t e r n s obtained v i a the use of a windowing technique 25 1+.7 Conversion of a m u l t i p l y connected r e g i o n t o a simply connected r e g i o n , . 26 v i i i Figure ' Page h.8 Generation of hatching l i n e s , 27 k.9 Two examples s a t i s f y i n g Theorem h.2 29 k,10 Two examples s a t i s f y i n g Theorem h.3 30 h.ll An example of a c r i t i c a l point . 30 k.12 An example of a point of i n f l e c t i o n 31 k.13 Examples of points which are not c r i t i c a l nor points of . . i n f l e c t i o n 31 h.lh A c r i t i c a l point, ( x ^ * y k + ± ) 3 2 U. 15 A point of i n f l e c t i o n , (x, v. _ , , ) . . . . • 32 K + X K + X h.l6 A point of i n f l e c t i o n , (x , y, . 0) 33 1+.17 An example to i d e n t i f y c r i t i c a l p o i n t s , point of i n f l e c t i o n , min-max points 33 h.13 An encasing rectangle associated with a hatching pattern. . 3^ 4.19 An example f o r sets Y k, Y k' , Y k * ' * * 3 5 H .20 An example with each hatching l i n e defined by one or more segments 37 U.21 An example with an in c o r r e c t HL 38 \.22 A hatching pattern composed of 3 r e a l i z a t i o n regions, . V V r 3 - * • ' ' ' k ° 4.23 Manipulation of a r e a l i z a t i o n region kh h.2k A r e a l i z a t i o n region composed of a multiply connected region . . . . . . . kl Complement of a r e a l i z a t i o n region U8 k.26 Hatching patterns with associated sets of hatching l i n e s at d i f f e r e n t i n c l i n a t i o n s , spacings and thickness 50 U..-27 • Manipulation of a r e a l i z a t i o n region. 51 i x F i g u re Page 5.1 A f i l l e d polygon 53 5.2 Geometric p r i m i t i v e s i n CADEP. 55 6.1 A g r a p h i c a l object composed of opaque and line-drawn g r a p h i c a l p r i m i t i v e s 59 6.2 G r a p h i c a l p r i m i t i v e s of LIG 62 6.3 A g r a p h i c a l object 62 6.1+ G r a p h i c a l "• p r i m i t i v e s 61+ 6.5 G r a p h i c a l p r i m i t i v e s . 6 k 6.6 G r a p h i c a l p r i m i t i v e s d e f i n e d i n LIGE but not i n LIG 65 6.7 The e f f e c t s of the complement operator on g r a p h i c a l p r i m i t i v e s 68 6.8 A menu 70 6.9 An example of the e f f e c t of executing the BRUSH statement. . 72 A . l A simply c l o s e d polygon 85 C. l A t r i a n g l e and i t s instance 87 C .2 A t r i a n g u l a t e d polygon and i t s i n s t a n c e • • • • • 89 D. l The c o n s t r u c t i o n of the LIGE preprocessor 93 X ACKNOWLEDGEMENT I am g r a t e f u l t o my parents and members of my f a m i l y f o r t h e i r cons.ta.nt encouragement, 1 "would l i k e t o express my deepest g r a t i t u d e t o Dr. G.F, Schrack, the s u p e r v i s o r of t h i s p r o j e c t , f o r h i s continued i n t e r e s t , encouragement and guidance during t h i s research work and w r i t i n g of t h i s t h e s i s . A l s o , my thanks t o Dr. M. Davies, my coreader, f o r h i s v a l u a b l e comments on the f i r s t d r a f t of my t h e s i s . 1. INTRODUCTION' Computer graphics deals w i t h the ge n e r a t i o n , r e p r e s e n t a t i o n and manipulation of g r a p h i c a l data u s i n g a computer system. In p a r t i c u l a r , the system handles u n i t s of g r a p h i c a l data which are r e f e r r e d t o as g r a p h i c a l o b j e c t s . Progress can be seen i n a l l areas of computer g r a p h i c s , e s p e c i a l -l y i n the f i e l d of r a s t e r g r a p h i c s . One reason f o r the i n c r e a s i n g popu-l a r i t y of r a s t e r - s c a n d i s p l a y devices i s t h e i r a b i l i t y t o d i s p l a y two types of data, s o l i d tone areas as w e l l as l i n e s and t e x t . H e r e a f t e r , graphics t h a t can handle both kinds of data i s r e f e r r e d t o as r e g i o n a l  graphics. In order t o be p r e c i s e , a d e f i n i t i o n i s necessary: r e g i o n a l .graphi cs r e f e r s t o the theory and techniques of the i n t e r n a l and 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 o b j e c t s which are composed of opaque o r , s o l i d areas as w e l l as conventional line-drawings i n a two-dimensional space. Not only i s an opaque g r a p h i c a l o b j e c t more appealing than a line-drawn object i n many s i t u a t i o n s , but many a p p l i c a t i o n s t h a t r e q u i r e r e a l i s t i c d e s c r i p t i o n of an object may be found. Examples of computer-aided a p p l i c a t i o n s are: t e c h n i c a l or n o n - t e c h n i c a l document i l l u s t r a t i o n , b l o c k diagram r e p r e s e n t a t i o n , a r c h i t e c t u r a l d e s i g n , urban p l a n n i n g and layout problems such as i n t e g r a t e d c i r c u i t mask design. Although researchers have recognized the importance and poten-t i a l of r e g i o n a l g r a p h i c s , most work i s s t i l l c o n f i n e d t o the use of e x i s t i n g l i n e - d r a w i n g graphics packages t o achieve the v i s u a l i z a t i o n of regions by f i l l i n g and hatching techniques. L i t t l e e f f o r t i s devoted t o the i n v e s t i g a t i o n of the theory (such as the use of data type) and t e c h -niques of r e g i o n a l graphics. Accepting the u s e f u l n e s s , p o t e n t i a l , and demand f o r r e g i o n a l g r a p h i c s , research to r e f i n e and propose a b e t t e r t h e o r y , t o improve techniques, and t o develop a language f o r r e g i o n a l graphics i s necessary. Such res e a r c h should e s t a b l i s h a base and i n i t i a t e f u r t h e r work i n t h i s area. This i s the purpose of t h i s t h e s i s . 2 . EXTERNAL REPRESENTATION MODELS FOR GRAPHICAL DATA At t h i s p o i n t , the explanations of s e v e r a l terms w i l l h e l p the subsequent d e s c r i p t i o n s and d i s c u s s i o n s , A g r a p h i c a l object i s any g r a p h i c a l datum which i s t r e a t e d as an i n d i v i s i b l e s i n g l e u n i t . A g r a p h i c a l p r i m i t i v e i s a g r a p h i c a l datum whose value i s a g r a p h i c a l o b j e c t t h a t cannot or need not be decomposed any f u r t h e r . I n t e r n a l r e p r e s e n t a t i o n s of g r a p h i c a l data are the storage of data i n a d i g i t a l computer. In p a r t i c u l a r , an i n 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 i s r e l a t e d t o a scheme f o r d e s c r i b i n g the data and an as s o c i a t e d data s t r u c t u r e . E x t e r n a l r e p r e s e n t a t i o n s of g r a p h i c a l data are the ways data are depicte d on a two-dimensional d i s p l a y s u r f a c e . 2 . 1 General Concepts Much e f f o r t has been focused on the i n 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, i . e . the study of the data bases and data s t r u c t u r e s t h a t are r e q u i r e d f o r the implementation of a graphics language. However, l i t t l e r esearch has been done on the i n v e s t i g a t i o n of an e x t e r n a l r e p r e -s e n t a t i o n model f o r g r a p h i c a l data. When d e a l i n g w i t h g r a p h i c a l d a t a , the model chosen f o r the e x t e r n a l r e p r e s e n t a t i o n of a g r a p h i c a l object i s important. The model employed a f f e c t s the type and number of g r a p h i c a l operators r e q u i r e d t o ha.ndle g r a p h i c a l o b j e c t s . I t a l s o a f f e c t s the l a n -guage c o n s t r u c t s and the data s t r u c t u r e s of a graphics language. 2 . 2 E x t e r n a l Representation Models Two types of e x t e r n a l r e p r e s e n t a t i o n models f o r g r a p h i c a l o b j e c t s can be i d e n t i f i e d and are r e f e r r e d t o as the l i n e a l and r e g i o n a l e x t e r n a l r e p r e s e n t a t i o n models. In the l i n e a l e x t e r n a l r e p r e s e n t a t i o n model (Figure 2.1), a g r a p h i c a l object i s considered t o have a s t a r t i n g and an end p o i n t and i s composed of g r a p h i c a l o b j e c t s and/or g r a p h i c a l p r i m i t i v e s . A g r a p h i c a l p r i m i t i v e i s a l i n e segment or a v e c t o r . For convenience, a l i n e segment can be considered t o have a head and a t a i l . The b a s i c o p e r a t i o n i s con-c a t e n a t i o n . Concatenation i s the j o i n i n g of the head or the t a i l of a l i n e segment t o the head or the t a i l of another l i n e segment based on a set of r u l e s . Graphics languages which employ the l i n e a l e x t e r n a l r e p r e -s e n t a t i o n model are GPL [Sm7l], AIDS [ S t 7 l ] , EULER-G [Ne7l], TUNA [Be73], PDL [Ri75,Sh68,Sh69]• g r a p h i c a l o b j e c t i s def i n e d on a f i n i t e , plane area. For convenience, the plane area i s def i n e d t o be a u n i t square, the d e f i n i t i o n frame, on which a reference p o i n t i s defined. The refe r e n c e p o i n t i s a p o i n t about which a l l g r a p h i c a l transformations, and operations are performed. Any p o i n t w i t h i n the d e f i n i t i o n frame belongs t o the a s s o c i a t e d g r a p h i c a l obj-ect and thus the area w i t h i n the frame i s the i d e n t i f i c a t i o n area of the g r a p h i c a l o b j e c t . A g r a p h i c a l p r i m i t i v e i s an element of a convenient set of predefined g r a p h i c a l o b j e c t s . S u p e r p o s i t i o n i s the b a s i c o p e r a t i o n i n v o l v e d . Examples of graphics languages which use the, r e g i o n a l e x t e r n a l r e p r e s e n t a t i o n model are GROAN [Wy7l+], L [ N a 7 l ] , and LIG [Sc76a,Sc76b, a g r a p h i c a l p r i m i t i v e t h F i g u r e 2.1 The l i n e a l e x t e r n a l r e p r e s e n t a t i o n model In the r e g i o n a l e x t e r n a l r e p r e s e n t a t i o n model (Figure 2.2), each Sc78]. d e f i n i t i o n frame ( i d e n t i f i c a t i o n area) reference p o i n t a g r a p h i c a l p r i m i t i v e Figure 2.2 The r e g i o n a l e x t e r n a l r e p r e s e n t a t i o n model 2.3 V i r t u e s and L i m i t a t i o n s of the L i n e a l and Regional E x t e r n a l Repre- s e n t a t i o n Models Some "basic notions of the two e x t e r n a l r e p r e s e n t a t i o n models have been discussed. At t h i s p o i n t , a summary of the v i r t u e s and l i m i t ; t i o n s of each model i s given. The purpose i s t o help c o n s o l i d a t e the understanding of the two models and t o j u s t i f y the choice used i n the work reporte d here. L i n e a l e x t e r n a l r e p r e s e n t a t i o n model V i r t u e s : + This model lends i t s e l f t o s i t u a t i o n s i n which c o n n e c t i v i t y and d i r e c t i o n between g r a p h i c a l o b j e c t s or signs i s important + E x i s t i n g theory and experience w i t h t h i s model f a c i l i t a t e s f u r t h e r research i n the area. L i m i t a t i o n s : + The model can handle only a l i m i t e d c l a s s of g r a p h i c a l o b j e c t care has t o be taken i n d e f i n i n g the s t a r t i n g and end p o i n t s a g r a p h i c a l object w i t h more than one s t a r t i n g or end p o i n t . Examples are shown i n Figure 2.3(a-b). As a r e s u l t , much time and e f f o r t may have t o be spent i n d e f i n i n g such g r a p h i c a l o b j e c t s . Another l i m i t a t i o n i n c o n s t r u c t i n g a g r a p h i c a l object i s t h a t only two p o i n t s of concatenation f o r each p r i m i t i v e are a v a i l a b l e . A (a) (b) Fi g u r e 2.3 Examples of g r a p h i c a l objects t h a t r e q u i r e e x t r a care i n d e f i n i n g the s t a r t i n g and end p o i n t s w i t h a l i n e a l e x t e r n a l r e p r e s e n t a t i o n model + The model cannot handle r e g i o n a l graphics c o n c e p t u a l l y . + The model does not have a w e l l - e s t a b l i s h e d concept of i d e n t i -f i c a t i o n . I d e n t i f i c a t i o n r e f e r s t o the s e l e c t i o n of a g r a p h i c a l object on a t e r m i n a l screen. + The model encourages d i f f e r e n t n o t a t i o n s , and the reader must understand the n o t a t i o n before understanding the concepts. In p a r t i c u l a r , d i f f e r e n t researchers use d i f f e r e n t ways t o parse p i c t u r e s . Regional e x t e r n a l r e p r e s e n t a t i o n model V i r t u e s : + This model provides a n a t u r a l way t o represent g r a p h i c a l o b j e c t s which de p i c t two-dimensional i n f o r m a t i o n . 7 + The model i s s u i t a b l e f o r r e g i o n a l graphics without f u r t h e r m o d i f i c a t i o n . + The model supports operations t h a t are simple and c l e a r . Rules are n a t u r a l t o use and remember. + The model's use of the d e f i n i t i o n frame permits a c o n s i s t e n t concept of i d e n t i f i c a t i o n . + The model f a c i l i t a t e s the c a l c u l a t i o n of the area of a g r a p h i c a l object ( r e f e r t o Appendix C). L i m i t a t i o n s : + The model does not le n d i t s e l f t o e s t a b l i s h c o n n e c t i v i t y between d i f f e r e n t o b j e c t s . + The model r e q u i r e s new concepts and so must be developed from f i r s t p r i n c i p l e s . I t can be concluded t h a t each model has i t s own areas of a p p l i -c a t i o n : the l i n e a l model has i t s use i n the f i e l d of p a t t e r n p i c t u r e r e c o g n i t i o n whereas the r e g i o n a l model has i t s use i n the f i e l d of computer graphics. One can f u r t h e r demonstrate the s u i t a b i l i t y of the r e g i o n a l r e p r e s e n t a t i o n model f o r computer graphics by the f o l l o w i n g a r g -ument : The b a s i c l e a r n i n g of a c h i l d begins w i t h the alphabet and the d i g i t s . alphabet = {a,b,...,y,z) d i g i t s = { 0 , 1 , . . . , 8 , 9 ) From the alphabet (the sm a l l e s t d i v i s i o n i n a language), words are constructed. From words, sentences are constructed. Using the same p r i n c i p l e , a computer graphics language, LIG has been implemented [Sc76a, Sc78]. An analogy can be made between the n a t u r a l language and a computer graphics language: a set of g r a p h i c a l p r i m i t i v e s comparable t o the characters i n the alphabet i s chosen. P r i m i t i v e s and-characters are described on u n i t squares (Figure 2.k). A g r a p h i c a l o b j e c t composed of g r a p h i c a l p r i m i t i v e s corresponds t o a word composed of c h a r a c t e r s . A com-pl e x g r a p h i c a l object composed of g r a p h i c a l o b j e c t s i s analogous t o a sentence composed of words. Hence, t h i s scheme, by the use of a r e g i o n a l e x t e r n a l r e p r e s e n t a t i o n model, achieves good man-machine communication. In the sequel, only g r a p h i c a l o b j e c t s u s i n g the r e g i o n a l e x t e r n a l r e p r e -s e n t a t i o n model are considered. F i g u r e 2.h D i g i t s and char a c t e r s d e s c r i b e d on squares 3. INTERNAL AND EXTERNAL REPRESENTATIONS OF REGIONS The use of the r e g i o n a l e x t e r n a l r e p r e s e n t a t i o n model f o r g r a p h i c a l data f a c i l i t a t e s the d e f i n i t i o n of an opaque g r a p h i c a l o b j e c t . In order t o handle t h i s type of g r a p h i c a l o b j e c t , a thorough understanding of the i n t e r n a l and e x t e r n a l r e p r e s e n t a t i o n s of regions or areas i s r e q u i r e d . A number of d e f i n i t i o n s or r e p r e s e n t a t i o n s of regions have been proposed i n v a r i o u s f i e l d s . U n f o r t u n a t e l y , many of them are only s u i t a b l e f o r the authors' p a r t i c u l a r a p p l i c a t i o n . However, a l l these r e p r e s e n t a t -ions can be c l a s s i f i e d and u n i f i e d w i t h i n a general scheme f o r s o l i d - a r e a g r a p h i c a l o b j e c t s . Towards t h i s end, the d e s c r i p t i o n and c l a s s i f i c a t i o n of the i n t e r n a l r e p r e s e n t a t i o n s of regions i s presented i n the f o l l o w i n g s e c t - . ions and i s f o l l o w e d by a formal d e s c r i p t i o n of a r e g i o n i n order t o u n i f y the concepts. 3.1 Background Cook [C067] has provided a d e f i n i t i o n f o r plane r e g i o n s : a re g i o n means a connected plane area bounded by one or more c l o s e d curves. A mathematical d e s c r i p t i o n of a r e g i o n i s the f o l l o w i n g : a set i s c a l l e d a r e g i o n i f i t i s the union of an open connected set w i t h none, some, or a l l i t s boundary p o i n t s . I f none or some of the boundary p o i n t s are i n c l u d e d , the r e g i o n i s c a l l e d an open r e g i o n . I f a l l the boundary p o i n t s are i n c l u d e d , the r e g i o n i s c a l l e d a c l o s e d r e g i o n (see e.g. A p o s t o l [Ap73]). * A space S i s c a l l e d disconnected i f S = A U B, where A and B are d i s -j o i n t nonempty open sets i n S. We c a l l S connected i f i t i s not d i s c o n -nected [Ap73]. I t i s p o s s i b l e t o d i s t i n g u i s h between two b a s i c types of regions a simply connected r e g i o n (SCR) and a m u l t i p l y connected r e g i o n (MCR). A simply connected r e g i o n [Ja6o] i s de f i n e d t o be a r e g i o n such t h a t any clos e d curve w i t h i n i t can be deformed c o n t i n u o u s l y t o a p o i n t of the reg i o n without l e a v i n g the r e g i o n . A l t e r n a t i v e l y , i t can be def i n e d as a r e g i o n such t h a t no c l o s e d curve l y i n g e n t i r e l y w i t h i n the r e g i o n can enclose a boundary p o i n t of the r e g i o n (Figure 3.1a). A m u l t i p l y connect- ed r e g i o n [Ja6o] i s a r e g i o n which i s not simply connected (Figure 3.1b). (a) a simply connected r e g i o n (b) a m u l t i p l y connected r e g i o n F i g u r e 3.1 Examples of d i f f e r e n t types o f regions The above d e f i n i t i o n s and c l a s s i f i c a t i o n f o r regions are too general f o r the work des c r i b e d here because c l o s e d curves should be s p e c i f i e d t o be simply c l o s e d curves. A simply c l o s e d curve (a Jordan curve, A p o s t o l [Ap73]) i s one which i s c l o s e d and has no s e l f - i n t e r s e c t -ions ( K r e y s z i g [Kr72]). Some examples of d i f f e r e n t types o f curve are given i n F i g u r e 3.2(a-b). (a) a c l o s e d curve (h) a simply c l o s e d curve F i g u r e 3.2 Examples of d i f f e r e n t types o f curves 11 3.2 Internal Representations of Regions In the previous section some definitions and a cla s s i f i c a t i o n of regions have been presented. Numerous techniques for representing regions have been reported in the literature. Basically, there are three major ones: 3.2.1 The 'encoding of the boundaries' Scheme A region can be defined by simply closed curves. Hence the task of representing a region is reduced to that of a curve. Numerous techni-ques for boundary representations have been reported in the literature. Some representations retain a l l of the information about the boundary, vhile others preserve only -what is of interest for a particular applicat-ion. A few of the important references on this subject are given here. segments. Each line segment, called the boundary section (Loomis [L065], Burton [Bu77]), is completely determined by two ordered pairs defining i t s end points (Figure 3.3). Freeman [Fr6la,Fr6lb ,Fr62,Fr7U] was the f i r s t to propose the use of a string of integer code for contour representation (Figure 3-Ma-b)). Detailed discussion on boundary representations and descriptions can be found in Aggarwal [Ag77]. l ) The 'encoding of the boundaries' scheme (the conventional method), 2) the 'parallel coding' scheme, 3) the 'skeleton' scheme. Each simply closed curve is represented by consecutive line boundary section rectangle boundary section a closed polygon Figure 3.3 An example of a boundary section enclosed within a boundary section rectangle 12 3 2 1 r x ^ Pi-< / 1 U2 at 2S3 5 6 T (a) E i g h t p o s s i b l e d i r e c t i o n s , numbered from 0 t o 7 I n i t i u m ( s t a r t i n g p o i n t ) (b) An example of a c o n t o u r - l i n e chain (CHAIN = 0102U353667) Figure 3.h Freeman's encoding scheme 13 3.2.2 The 'parallel coding 1 Scheme Dudani [Du76], M e r r i l l [Me73]» Ram [Ra76] are researchers whose work f a l l into this type of representation scheme for regions. The under-standing of the concepts underlying this scheme can he achieved hy review-ing Merrill's work. A review of Merrill's work which has been augmented by additional points at extrema and inflections according to certain rules. A point of inflection i s defined when three consecutive line segments exist, the centre segment being horizontal, and the other two are pointing in opposite directions. The point of inflection is then the l e f t endpoint of the horizontal segment. The rules are simple: 1) Each horizontal test line must pass through an even number of boundary points at each extremum. It is necessary to dupli-cate the extremum at which this condition is not satisfied (Figure 3.5a). 2) Each horizontal test line must pass through an odd number of boundary points at each inflection. However, i t is necessary to duplicate the point of inflection at which this condition i s not satisfied (Figure 3.5b). Once the TCB is obtained, i t is partitioned into sets so that each set contains the x coordinates of points having the same y coordi-nate. Each of these sets i s then sorted in ascending order of x and is called the y-partition of the TCB. Using the y-partitions of the TCB, a region can then be defined as follows: A tightly closed boundary (TCB) is defined to be a boundary » y, max Y Y ' Il» X2' Y } n where y min is the smallest y-coordinate of the boundary, max is the largest y-coordinate of the boundary, (a) augment an a d d i t i o n a l p o i n t t o each extremum when necessary .duplicate t h i s ' l a s t ' p o i n t t e s t l i n e (t>) augment an a d d i t i o n a l p o i n t t o each p o i n t of i n f l e c t i o n when necessary A——J—•—.—•—,—.—.—,—.— 1 3 5 7 9 1 2 (c) an example t o c l a r i f y n o t a t i o n s used Fi g u r e 3 , 5 M e r r i l l ' s scheme 15 n = y - V . + 1 , max 'mm i s the y - p a r t i t i o n f o r the t e s t l i n e , y^. Y^ can be expressed i n the form: Y = ( i i i i \ ^.r^ , x^, x^, • • • , X j , , . . , x^ ^  ; where r_^ is. the number of x coordinates, (always an even number). x^ are the points of the TCB having y.-coordinates. Example (Figure 3.5c): r± = h, i = 3 Y^ — (-^ 2' ' ^2' ^3' Y 3 = (U, 1, 3, 3, 12) There i s an i m p l i c i t r u l e that has not been discussed by M e r r i l l . Whenever an i n f l e c t i o n i s augmented, the point to be augmented must be the ' l a s t ' point associated with the i n f l e c t i o n ( r e f e r to Figure 3.5b). This i s the so c a l l e d p a r a l l e l coding scheme. The p r i n c i p l e s of t h i s scheme are used, with small modifications, i n many hatching a l g o r i -thms, f i l l i n g algorithms and representations of regions. This scheme i s p a r t i c u l a r l y s u i t a b l e f o r computing areas and i n t e r s e c t i o n p r o p e r t i e s . Besides, i t has reasonable storage requirements and provides an e f f i c i e n t format f or information r e t r i e v a l . 3.2.3 The 'skeleton' Scheme The s k e l e t a l representation of planar regions proposed by P f a l t z and Rosenfeld [Pf6 rf] i s unconventional. B a s i c a l l y , a number of squares are f i t t e d to the i n s i d e of a region i n such a way that every i n s i d e point i s contained i n a square or squares. The square to be f i t t e d must be the lar g e s t possible square i n order to obtain the smallest p o s s i b l e t o t a l 16 number of squares. The centre of each square i s i t s p o s i t i o n and i s assigned a value i n d i c a t i n g the s i z e of the square. The f i n a l form of the f i g u r e has numbers attached at the corresponding p o s i t i o n s ( F i g u r e 3 . 6(a-b)) and i s c a l l e d the s k e l e t o n of the f i g u r e . (a) A r e g i o n d e f i n e d by p o i n t s P, Q, R, S w i t h r a d i i 3,2,1 and 0.[Pf67] ! • • . xxxxxx xxxxxxxxxxxx xxxxxx xxxxxxxxxxxxxx I xxxxxxxxxx xxxxxxxxxxxxxxxx i xxxxxxxxxxxxx xxxx xxxx xxxxx xxxxx XXXI ixx XXXX XXXXX XXXX 3 XXX XXXX xxxx XXX 4 XX) XXXX 3 XXX XXX 5 5 XX XXXI XXX XXXX 66 XX XXX xxx XXX 7 XXX XXX 6 6 XX XX 88 XX XXXX 8 XXX XX B XX XXX 999 XXX XX 8 XX XXX 9 8 XXX XX 7 XX xxxx 8 7 XXX XXX 7 XX xxx 8 5 XXX XXX 6 XX XXX 3 3 XXX XXX 6 XX XXXX xxxx XX 5 XXX XXXX xxxx XXX 5 XX XXXXX xxxxx XX 4 XX xxxxx xxxxxx XX 44 XX xxxxx xxxxxxxxx XX 4 XX xxxxx xxxxxxxxx XXX 4 X XXXXXXXXXXXX X 4 XX XXXXXXX XX 4 X • X 4 XX X 3 XX XX 3 XX X 3 XX X 2 XX XX 2 XX X 2 XX XXI XX X111X I XXXXX (b) Skeletons of two i r r e g u l a r r e g ions (bounded by X's) [pf67] Figure 3,6 P f a l t z and Rosenfeld's scheme 17 Rosenfeld a s s e r t s t h a t t h i s scheme has advantages when i t i s necessary t o t e s t r e p e a t e d l y i f a p o i n t i s i n s i d e or o u t s i d e a r e g i o n . This k i n d of t e s t i s r e q u i r e d i n ha t c h i n g ( F i g u r e 3.7). M u l t i p l y - c o n n e c t e d r e g i o n can he handled without m o d i f i c a t i o n s . Moreover, s e t - t h e o r e t i c operations on regions present no d i f f i c u l t i e s . A c c ording t o P f a l t z and R o s e n f e l d , the s k e l e t o n scheme r e q u i r e s more storage space than does the 'encoding o f the boundaries' method. I n a d d i t i o n , i t i s d i f f i c u l t , i f not i m p o s s i b l e , t o determine the area or the perimeter o f a r e g i o n . F i g u r e 3.7 A hatched map obtained through the use of P f a l t z and Rosenfeld's scheme [Pf67] The s k e l e t o n scheme of P f a l t z and Rosenfeld i s a s p e c i a l i z e d method f o r r e p r e s e n t i n g a r e g i o n . I t does not l e n d i t s e l f r e a d i l y f o r use w i t h h a t c h i n g or f i l l i n g a l g o r i t h m s . 18 3.3 A Formal Representation of a Region A region can be defined by a two-tuple (an ordered p a i r ) : R = <I, E> where I denotes an i n t e r n a l representation of a region R, E denotes a model f o r the external representation of a region R. E can be described by a three-tuple: E = <A, B, F> where A i s a scheme to produce a v i s u a l e f f e c t of the existence of a region (such as hatching, c o l o u r i n g ) , A may be the empty set (Loomis [ L 0 6 5 ] ) , B denotes a set of simply closed curves, F denotes a d e f i n i t i o n frame within which a region i s defined. I f B = {b }, then R e SCR, i f B = {b | i > 1}, then R e MCR, where SCR denotes a set of simply connected regions, MCR denotes a set of mul t i p l y connected regions. For any boundary, b^: b = <K, D, Q> where K = t$s, <£> denotes a simply closed curve formed by a set of consecu-t i v e l i n e segments, {s |k = 1, nthside}.. Mathematically, k = 1, k 2, when k = 1 or 2, a closed polygon of zero area i s formed; thus i n p r a c t i c e , k >= 3. The c i r c l e s associated with the brackets are used to emphasize the f a c t that the curve i s closed, D = {a, c}, denoting a set of two elements s p e c i f y i n g the d i r e c t i o n along which the boundary i s defined; 'a'- denotes an anticlockwise d i r e c t i o n and 'c* denotes a clockwise d i r e c t i o n (Figure 3 -8) , Q = {1, r}, denoting a set of two elements s p e c i f y i n g on which side 19 the region l i e s when moving along the boundary according to the s p e c i f i e d element of D; 1 denotes that the region l i e s to the l e f t of the boundary, r denotes that the region l i e s to the r i g h t of the boundary (Figure 3-9). Each l i n e segment, s can be s p e c i f i e d by two ordered p a i r s : . sk = < ( V yk>> (xk-' J k < ] > k + l when k 4- nthside when k = nthside (Figure 3.10) c clockwise a anticlockwise Figure 3.8 D i r e c t i o n convention curve A curve B To curve A, the region i s on the l e f t , to curve B, the region i s on the l e f t . Figure 3.9 A convention used f o r d e f i n i n g a region Figure 3.10 A simply closed polygon 21 k. THE CONCEPTS AND TECHNIQUES OF HATCHING Hatching i s one way t o achieve an e x t e r n a l r e p r e s e n t a t i o n o f a reg i o n . In a d d i t i o n , the c a p a b i l i t y t o hatch an a r b i t r a r y simply c l o s e d polygon i s found u s e f u l i n many a p p l i c a t i o n s . There has been some confusion i n the use of the terms h a t c h i n g , shading and f i l l i n g . Some researchers use the term 'shading' i n a context f o r which the more p r e c i s e term 'hatching' should have been used. The f o l l o w i n g d e f i n i t i o n s w i l l provide a c l e a r d e s c r i p t i o n of h a t c h i n g , f i l l -i n g and shading. k.l D e f i n i t i o n s Hatching r e f e r s t o the drawing of a set of p a r a l l e l l i n e s of uniform t h i c k n e s s at a given angle and spacing ( c a l l e d the hatching l i n e s ) to g i v e a v i s u a l e f f e c t of the existence of a r e g i o n or t o d i s t i n g u i s h one r e g i o n from another (Figure H . l ) . F i g u r e k.l- An example of a hatching p a t t e r n F i l l i n g r e f e r s t o the a s s i g n i n g of a c e r t a i n g r a y - l e v e l , symbol or colour t o each p i x e l b elonging t o a r e g i o n (Figure k.2). 22 Figure h.2 An example of a reg i o n t h a t has teen f i l l e d Shading r e f e r s t o the f i l l i n g or the hatching of a reg i o n i n order t o dep i c t a three-dimensional object on a two-dimensional display-surface (Figure * K 3 ) . Figure h.3 An example of a shaded object [Ne78] k.2 A Short Review of Hatching Algorithms P a v l i d i s [Pa78a,Pa78b] has given an e x c e l l e n t p r e s e n t a t i o n on various f i l l i n g algorithms f o r r a s t e r g r a p h i c s . However, n e i t h e r he nor others seem t o have i n v e s t i g a t e d hatching algorithms s y s t e m a t i c a l l y . A hatching a l g o r i t h m was implemented by P h i l l i p s [Ph76] u s i n g ideas proposed by Dwyer [Dw67]. An example of an output i s shown i n 2 3 Figure h . h . P h i l l i p s , however, does not g i v e any d e t a i l s o f the a l g o r i t h m . F i g u r e h . h Shading of compound polygons ( P h i l l i p s [Ph76].) Another h a t c h i n g - f i l l i n g a l g o r i t h m , developed hy Ison [Is73], i s o r i e n t e d toward ve c t o r g r a p h i c s . This a l g o r i t h m w i l l be c a l l e d a h a t c h i n g -f i l l i n g a l g o r i t h m because i t i s capable o f drawing p a r a l l e l l i n e s as w e l l as p u t t i n g out d e s i r e d symbols, c a l l e d f i l l i n g symbols, f o r a gi v e n polygon. An example of a p l o t output i s shown i n F i g u r e *4.5, where LABEL 1 and LABEL 2 are hatching p a t t e r n s whereas LABEL 3 i s a f i l l i n g p a t t e r n . As Ison s t a t e s , one of the r e s t r i c t i o n s f o r t h i s a l g o r i t h m i s t h a t a hatc h i n g l i n e which overlaps e x a c t l y w i t h an o u t l i n e segment may not be i n c l u d e d . As i s shown i n LABEL 1 and 2, the o u t l i n e segments are c o n s t r -ucted i n such a f a s h i o n t h a t no hat c h i n g l i n e overlaps w i t h an o u t l i n e segment e x a c t l y . This r e s t r i c t i o n reduces the us e f u l n e s s o f the a l g o r i t h m on many occasions. Furthermore, the more o u t l i n e segments a f i g u r e i s made up o f , t h e h i g h e r t h e chance i s f o r o v e r l a p p i n g . A l s o , when t h e o u t l i n e segments a r e n o t p e r p e n d i c u l a r t o each o t h e r , no t e s t i s g i v e n as t o whether a, f i l l i n g symbol w i l l he p a r t i a l l y o u t s i d e t h e o u t l i n e o r n o t . o 0.00 5.00 10.00 15.00 _ X - A X I S F i g u r e U.5 Example - P l o t o u t p u t ( i s o n [Is73]) 20.00 25.00 25 P f a l t z and Rosenfeld [Pf67] proposed a hatching algorithm f o r an a r b i t r a r y planar region represented i n skeleton form. However, t h e i r work i s focused on the representation of region. D e t a i l s of the algorithm are not given CFigure 3 ,7) . k.3 General Concepts of Hatching Hatching an a r b i t r a r y region defined by a set of simply closed consecutive l i n e segments can be considered to be a r e p e t i t i o n of a three-step task: 1) with a s p e c i f i e d angle, f i n d a l l the i n t e r s e c t i o n s of a l i n e with the ou t l i n e segments describing the region*, 2) with the obtained set of i n t e r s e c t i n g p o i n t s , manipulate i t , i f necess-ary, according to a set of rules to ensure a correct set of points for step 3; 3) with the elements of the set obtained i n step 2, draw l i n e s to produce a hatching l i n e . By r e l a x i n g the d e f i n i t i o n of hatching l i n e s to allow non-p a r a l l e l l i n e s , a broader c l a s s of hatching patterns such as those shown i n Figures l|-.6(a-b) can be i d e n t i f i e d . Thus, hatching can be defined to (a) (b) Figure k.6 Hatching patterns obtained v i a the use of a windowing technique be a set of a r b i t r a r y curves w i t h equal d i s t a n c e from each other. With t h i s d e f i n i t i o n , a hatching p a t t e r n can be obtained by a windowing t e c h -nique. Windowing r e f e r s t o the formation of a domain enclosed by a simply c l o s e d polygon, Here, the boundary of a r e g i o n t o be hatched i s the window. For example a p a t t e r n (Figure l+,6b) can be obtained by a set of c o n c e n t r i c c i r c l e s or a set of a r b i t r a r y d e f i n e d shapes [Pe78,Ve79], expanding out from or s h r i n k i n g t o a p o i n t . Such p a t t e r n s w i l l not be considered here. Most of the hatching algorithms are l i m i t e d t o h a t c h i n g a simply connected r e g i o n . Whenever a m u l t i p l y connected r e g i o n i s t o be hatched, i t has t o be converted t o a simply connected r e g i o n . This can e a s i l y be done by i n t r o d u c i n g i n v i s i b l e cuts or v i r t u a l edges (Figure ^.7). The number of cuts corresponds t o the number of holes i n s i d e the r e g i o n . a m u l t i p l y connected r e g i o n ' a simply connected r e g i o n F i g u r e H.7 Conversion of a m u l t i p l y • c o n n e c t e d r e g i o n . t o a simply connected r e g i o n k.k The Conceptual and Mathematical Elements f o r Hatching Algorithms Before the ..developed, h a t c h i n g a l g o r i t h m i s d i s c u s s e d i n d e t a i l , the f o l l o w i n g s e c t i o n s w i l l be h e l p f u l t o the understanding of both the developed hatching a l g o r i t h m as w e l l as other a l g o r i t h m s . 27 U,U.X Transformations In order t o have simple computations as w e l l as a c o n s i s t e n t a n a l y s i s , t r a n s f o r m a t i o n of a l l coordinates and equations to a new c o o r d i -nate system w i t h i t s a b s c i s s a p a r a l l e l t o the hatching l i n e s i s necessary. Consider an a r b i t r a r y r e g i o n d e f i n e d by a boundary shown i n Figure h,8. A p r e l i m i n a r y step towards the c o n s t r u c t i o n of a h a t c h i n g p a t t e r n i s t o f i n d a l l p o i n t s of i n t e r s e c t i o n of the boundary segments and l i n e s shown. For convenience, these l i n e s , used f o r generating hatching l i n e s , are c a l l e d generative l i n e s . The equation f o r each l i n e L i n the x-y plane i s of the form: y = mx + c where m i s i t s s l o p e , and c i t s y-i n t e r c e p t . The same l i n e L can be d e s c r i b e d , without l o s s of i n f o r m a t i o n , y' = c ' i n the x'-y' plane w i t h i t s a b s c i s s a p a r a l l e l t o L. Computat-ions u s i n g y' = c' r a t h e r than y = mx + c are much e a s i e r and s i m p l e r . Besides, the computations are more c o n s i s t e n t s i n c e a l l generative l i n e s are p a r a l l e l t o the a b s c i s s a and the c a l c u l a t i o n s i n v o l v e d always d e a l w i t h s o l v i n g f o r p o i n t s of i n t e r s e c t i o n s between h o r i z o n t a l l i n e s and b oundary s egment s. Figure k.Q Generation of h a t c h i n g l i n e s 28 The x'-^y' plane i s e f f e c t i v e l y obtained i n two ways; 1) by r o t a t i n g the x-y plane 0 radian about a reference point, or 2) by r o t a t i n g the region defined i n the x-y plane ^0 radian about a reference point. Tn the sequel, a l l manipulations of coordinates are c a r r i e d out i n the rotated plane, the x'-y' plane, unless otherwise stated. A horizon-t a l l i n e r e f e r s to a l i n e p a r a l l e l to the abscissa of the plane associated with a pattern or a l i n e p a r a l l e l to the hatching l i n e s i n the untrans-formed coordinate system. In p a r t i c u l a r , a h o r i z o n t a l generative l i n e i n the rotated plane i s c a l l e d a scanline, or a t e s t l i n e . h.k.2 Intersection between two l i n e s As stated e a r l i e r , a step towards the construction of a hatching pattern i s to obtain points of i n t e r s e c t i o n between boundary segments and generative l i n e s ; for t h i s , the understanding of how a point of i n t e r s e c t -ion i s defined and obtained i s e s s e n t i a l . Mathematically, i n a f i n i t e region two l i n e s can only i n t e r s e c t i n three ways: at no point, at one p o i n t , and at an i n f i n i t e number of points. For the work discussed here, i n f i n i t e number of points of i n t e r -section w i l l be treated as no i n t e r s e c t i o n . To be p r e c i s e , a systematic analysis with one of the l i n e s being h o r i z o n t a l , w i l l be presented. Point of i n t e r s e c t i o n between a l i n e segment and a h o r i z o n t a l l i n e A l i n e segment S i s defined by i t s end points c a l l e d 'head' and ' t a i l ' . Mathematically, S = <(x ,y,),(x ,y, )>. Let the equation of a n TJ • u h o r i z o n t a l l i n e L be y = k. Theorem k . l • • * . * A. point of i n t e r s e c t i o n (x ,y ) between L and S e x i s t s o nly i f : a) f y^ . Cthey are not p a r a l l e l ) b) Jh >= k >= y t or y^ =•< k "=< y (they meet). I t i s then given r e s p e c t i v e l y by: ( k " y t ) ( x h ~ x t } ( k - y>, ) ( xh ~ x + ) ( x + l _ i ! _ k ) o r U + *L_J} L _ , k ) k.k.3 T o p o l o g i c a l P r o p e r t i e s The p r i n c i p l e of most hatching algorithms and r e p r e s e n t a t i o n s f o r regions i s based on two well-known theorems: Theorem h.2 I f a t e s t l i n e i s drawn from a p o i n t o u t s i d e a given r e g i o n d e f i n e d by a c l o s e d polygon t o a p o i n t which i s a l s o o u t s i d e the r e g i o n , then the number of c r o s s i n g s between the l i n e and the segments d e f i n i n g the boundary must be an even number (Figure i * . 9 ( a - b ) ) . (a) (b) Fi g u r e U.9 Two examples s a t i s f y i n g Theorem k.2 Theorem k.3 I f a t e s t l i n e i s drawn from a p o i n t o u t s i d e a given r e g i o n d e f i n e d by a c l o s e d polygon t o a p o i n t which i s i n s i d e the r e g i o n , then the number of c r o s s i n g s between the l i n e and the segments d e f i n i n g the boundary must be an odd number (Figure l+.10(a-b)). For p r o o f s , see Spani.er .[ Sp67j , 3 0 (a) (b) F i g u r e h.10 Two examples s a t i s f y i n g Theorem k.3 I t i s well-known t h a t the above t o p o l o g i c a l p r o p e r t i e s of a c l o s e d polygon always h o l d unless the f o l l o w i n g r e s t r i c t i o n s are v i o l a t e d . 1) A l l boundaries must be simply c l o s e d . 2) The t e s t l i n e does, not pass through any s i n g u l a r p o i n t s . A s i n g u l a r p o i n t can e i t h e r be a c r i t i c a l p o i n t or a p o i n t of i n f l e c t i o n . For an example of a c r i t i c a l p o i n t , consider a polygon com-posed of l i n e segments as shown i n Figure l + . l l . The h o r i z o n t a l l i n e HBH' cuts the s e c t i o n ABC of the boundary at two c o i n c i d i n g p o i n t s of i n t e r -s e c t i o n at B on AB and another at B on BC. P r o v i s i o n has t o be made f o r t h i s k i n d of s i t u a t i o n by ' f u s i n g ' them together. P o i n t B i s the c r i t i c a l p o i n t . F i g u r e h.ll An example of a c r i t i c a l p o i n t 31 For an example of a point of i n f l e c t i o n , consider the polygon shown i n Figure k.12. The h o r i z o n t a l l i n e HBCH' cuts the section ABCD of the boundary at the two points B and C, one point l y i n g on AB and the other on CD. According to the discussion i n Section k.k.2, the i n f i n i t e number of points of i n t e r s e c t i o n on BC w i l l be treated as no i n t e r s e c t i o n . Hence, BC appears to be non-existent and points B, C should be treated as one point by fusing them together. Point B, the l e f t most p o i n t , i s the point of i n f l e c t i o n . Figure lj.l3(a-t>) contains examples, a l l of which s a t i s f y Theorem k.2 and Theorem k.3. However, a more formal examination of c r i t i c a l points and points of i n f l e c t i o n i s necessary. A Figure k.12 An example of a point of i n f l e c t i o n Figure h.13 Examples of points which are not c r i t i c a l nor points of i n f l e c t i o n h.h.h D e f i n i t i o n s f o r S i n g u l a r p o i n t s D e f i n i t i o n : C r i t i c a l p o i n t (Figure U.lUCa-b)) Given two consecutive l i n e segments S. , S of the same bound-k K+X ary. i f Cyv+0 > y v + 1 > y j or Cyk+2 < y k + 1 < yR) then ( x k + 1 , y k + 1 ) i s 'k+2 ? "k+1 ' "k c a l l e d a c r i t i c a l p o i n t . ( x k+2' y k+2 ) ( x k + l ' W k+1 ( V y k ) N 3 t + 1 ( V l ' yk+l } >k+l ( x k+2' y k+2 ) (a) (b) Fig u r e h.lh A c r i t i c a l p o i n t , ( x ^ - ^ y k + l ^ D e f i n i t i o n : P o i n t of i n f l e c t i o n (Figure U.15, h.l6) Given three consecutive l i n e segments S^, ^ k + ^ , S k + ^ of the same boundary. Let P k + 1 = y f c + 1) and P k + 2 = ( x R + 2 , y k + 2 ) I f ( y k +3 > yk+2 a n d y k +2 = y k + l a n d y k + l * yk> or (y. < y. + P and y + p = y and y < y ) then one of the two p o i n t s P. L 1 , P. whichever l i e s on the l e f t , i s a K+X K+d p o i n t of i n f l e c t i o n . ( x k + 3 > y k + 3 ) k+2 °k+l ( xk+2- y k+2 5 ( v r ( X k + 2 ' Y k + 2 ) ak+2 ( x k+3' y k+3 J F i g u r e U.15 A po i n t of i n f l e c t i o n , (xk + 1> y k + 1 ) 33 < V 3 ' W A ' ^ s k + l k k \ / . ^ ^ + 3 ' yk+3 ; Figure h.l6 A point of i n f l e c t i o n , ( x k + 2 > v k + 2 ^ For completeness, the min-max points are defined here. D e f i n i t i o n : Min-Max points Given two consecutive l i n e segments S^, of the same "boundary. I f ( y k + l > y k a n d y k + l > yk+2> t h 6 n ( V l ' y k + l ) i S a m a x i m u m - -I f ( y k + l < y k a n d y k + l < y k + 2 } t h £ n ( xk+l' yk+l ) 1 S a m i n i m U m -Minimum and maximum points are neither c r i t i c a l points nor points of i n f l e c t i o n . An example In order to c l a r i f y the d e f i n i t i o n s f o r c r i t i c a l p o i n t s , points of i n f l e c t i o n and min-max p o i n t s , an example i s given i n Figure U.17. G , F are minimum points. D i s a point of i n f l e c t i o n , A i s a c r i t i c a l point and I , H, B , C , E are none of the above. a scanline v * / " ^ X . A / B C D polygon A I H E D F A \ V / ^ - P o l y g o n B C G B Figure U.17 An example to i d e n t i f y c r i t i c a l p o i n t s , points of i n f l e c t i o n , min-max points i|.'U,'5 Generation of a Hatching Line A hatching p a t t e r n i s a set of hatching l i n e s , each of which i s generated i n a number of steps. Each of these hatching l i n e s i s a s s o c i a t -ed w i t h a s c a n l i n e y running across the r e g i o n t o be hatched. The scan-K. l i n e y w i l l i n t e r s e c t the boundaries at l e a s t two times as long as a l l K. the boundaries are simply c l o s e d and the s c a n l i n e y, l i e s between y . k mm and y (Figure 1 + . 1 8 ) . y . , y are the minimum and maximum y coor-Jmax \ •'mm max J dinates of an encasing r e c t a n g l e f o r the r e g i o n . The encasing r e c t a n g l e i s one w i t h i t s sides p a r a l l e l t o the x and y axes. Using the c o n d i t i o n s f o r the i n t e r s e c t i o n of two l i n e s , a set of x coordinates of a l l p o i n t s of i n t e r s e c t i o n between o u t l i n e segments and the s c a n l i n e y can be deriv e d . Figure h.l8 An encasing r e c t a n g l e a s s o c i a t e d w i t h a hatching p a t t e r n 35 The set Y k Denote Y to be the set.of x-coordinates of a l l points of i n t e r s e c t i o n between the scanline y and the boundaries (.Figure 4 . 1 9 ) . k y = y x 2 x 3 xh x 5 x 6 k k 1 k' 1 Figure 4 ,19 An example for sets Y , Y , Y It can be expressed as: Y k = { V , j x k p q. 1 =< p < q =< 2 , i < j} where the subscripts p, q denote the order i n which the x coordinates are generated, the superscripts i , j denote the p o s i t i o n s of the elements i n the modified sets of Y . i k Note that x should be written as (x ) . Refer to Theorem 4 .1 P P i n Section 4.4.2. In Figure 4 .19, Y = { (x ) 1 , (x ) , (x )^, (x ) }. = { xg> x 5 ' x 0 ' x 0 } The set Y The elements of Y f i r s t have to be sorted i n ascending order of x f o r a hatching algorithm. The sorted set becomes: vk» r i k' - ,• j k' Y = { x , . , x p . q 1 x k ' =< J x k ' , l = < p < q = < 2 , i < j } p q 36 In Figure U.19, I = { (x )^ , (x ) ? , U ) g , (x ) 1 } - f * 0 » x 0 ' x 5 ' x 6 } k" The set Y k< The r e s u l t i n g set Y may s t i l l not he i n the desired form. Now the p r o v i s i o n mentioned e a r l i e r must be made f o r singular points to ensu-re a..correct set of x coordinates for hatching. For each scanline y , there are two i n d e n t i c a l x coordinates describing a c r i t i c a l point. I f k' such a point e x i s t s , one of the coordinates i s removed from the set Y For an i n f l e c t i o n , two consecutive boundary points are involved and the k 1 r i g h t most point i s removed from the set Y . In Figure h.19, i s drop-ped. In both cases, the two x coordinates are e f f e c t i v e l y fused i n t o one and the p r o v i s i o n i s thus r e f e r r e d to as the 'fusing' technique. k' Once the set Y has undergone the process of 'fusing', the set k" Y i s obtained. This set i s of the form: v k " A k" j k " ,- i k" .J k"' „ „ , . . „ .-, Y = { x , x x. < -x , 1 =< p < q. =< 2, i < j i P q. 1 P q. k" The number of elements i n the set Y i s always even. k" 1 * v" ? * k" In Figure h.19, ? = { (x )J , d ( x )* } = {x Q, x,.} The set HL k k" k Once the set Y i s obtained, a hatching l i n e HL associated with the scanline y can be defined. A hatching l i n e i s defined by one or k more segments (Figure h.20). HL i s of the form: U T k , , i k" s , i + l k" x . _ , , , HL = {<( x p , y k ) , ( x , y k)> 1 - 1 , 3 , } V 1 * k" 9 * k" In Figure h.19, HL = {<r(x )J , y k ) , ( d ( x )* >} = « U 0 , y k ) , ( x 5 , y k ) » Figure 4,20 An example with, each hatching l i n e defined by-one or more segments 38 N o t i c e , without f u s i n g , an even number of s i n g u l a r p o i n t s would give an even number of i n t e r s e c t i o n s at the boundaries, r e s u l t i n g i n an i n c o r r e c t hatching line.composed of two zero l e n g t h segments .(Figure h.2l). Thus, an even number of i n t e r s e c t i o n s at the boundaries i s a necessary but not a s u f f i c i e n t c o n d i t i o n f o r generating a c o r r e c t h a t c h i n g l i n e . The process of f u s i n g w i l l guarantee a c o r r e c t h a t c h i n g l i n e . a s c a n l i n e Figure 4.21 An example w i t h an i n c o r r e c t HL: (HL = {<(x y ), (v , y )>, <(x y ), (x yJ>>) a a b b c c d d D i s p l a c i n g s l i g h t l y each v e r t e x t h a t i s e i t h e r a c r i t i c a l p o i n t or a p o i n t of i n f l e c t i o n i s another s o l u t i o n t o t h i s problem. This method i s s a t i s f a c t o r y i f the v e r t i c e s are represented c a r e f u l l y , u s i n g only i n t e g e r a r i t h m e t i c (Newman and S p r o u l l [Ne78]). 4 . 5 The Developed Hatching A l g o r i t h m The f i r s t step i n the development of an a l g o r i t h m f o r a c e r t a i n task i s t o survey the r e l a t e d l i t e r a t u r e . A summary of a l l the weaknesses or r e s t r i c t i o n s i n proposed schemes then may r e s u l t i n a t a b l e of problems t o be r e s o l v e d . This method i s being used i n the development of the algorithm. 39 k.5.1 A Formal Representation of a Hatching P a t t e r n i n the Developed  Hatching A l g o r i t h m (".Figure kt22) A. hatching p a t t e r n , HP i s d e f i n e d by a two-tuple: HP = <R, D> where R i s a set of r e a l i z a t i o n r e g i o n s ; a r e a l i z a t i o n r e g i o n i s a set of regions defined w i t h i n a d e f i n i t i o n frame w i t h the same hat c h i n g p a t t e r n . R = ( r , I i = l , 2 n} w i t h n the maximum number of r e a l i z a t i o n regions d e f i n i n g the h a t c h i n g p a t t e r n . D i s the d e f i n i t i o n plane on which the hatching p a t t e r n i s defined. I t may be considered as a window. A window i s a simple domain enclosed by a set of consecutive edges t h a t form a simply c l o s e d polygon. Hence, D can be expressed as f o l l o w s : D = <$edge I m = 1, . . . , n'<?> m where n* i s the number of edges used t o form the window. The c i r c l e s -a s s o c i a t e d w i t h the brackets emphasize the f a c t t h a t the boundary must be c l o s e d . r ^ , an element of R, i s a r e a l i z a t i o n r e g i o n c o n s i s t i n g of one or more regions defined i n a d e f i n i t i o n frame. Each r e a l i z a t i o n r e g i o n can be described completely by a two-t u p l e : r . = <B, A> 1 where B i s a set of boundaries d e f i n i n g a r e a l i z a t i o n r e g i o n . A i s a t h r e e - t u p l e of a t t r i b u t e s f o r a v i s u a l e f f e c t . Each boundary i s d e f i n e d by a simply c l o s e d curve composed of l i n e segments. Define s. as the k^*1 l i n e segment of the j ^ * 1 boundary of the 1 , j , k t h i r e a l i z a t i o n r e g i o n , Each, l i n e segment, s. can be d e s c r i b e d by i t s 1 , j ,K. head and i t s t a i l : s. . , = <h. . , , t . . >. Both the head and the t a i l i , j , k i , j , k i , j , k ho of the l i n e segment can be described by the x, y coordinates i n the form: h i , j ,k " < x i , j ,k' y i , j ,k > t . , , = <x. . , , v. , , > i , j , k i , J , k ' J i , j . , k where k k + 1 when k does not denote the l a s t l i n e segment 1 when k denotes the l a s t segment <x, y> are the coordinates of a point i n the x-y plane. A i s defined by a three-tuple and s p e c i f i e s the v i s u a l e f f e c t of a r e a l i z a t i o n region. A = <g, d, t'> where g i s the gap or the spacing between the hatching l i n e s , d i s the angle of d i r e c t i o n of the hatching l i n e s , t ' i s the thickness of each hatching l i n e . k.5.2 The Algorithm HATCH  Purpose: To hatch a r e a l i z a t i o n region defined by simply closed polygons and to manipulate (scale, rotate and t r a n s l a t e ) the r e a l i z a t i o n region i f desired. Type of routine: A s e l f contained program written i n FORTRAN. R e s t r i c t i o n s : 1) The polygons are simply closed: a) no s e l f - i n t e r s e c t i o n , b) the s t a r t i n g and end point must be i d e n t i c a l , 2) the i n t e r s e c t i o n of the regions d e f i n i n g the r e a l i z a t i o n reg-ion i s the empty set. How to use: The user can invoke the routine e i t h e r i n a Fortran program or h2 i n an LIG program. The c a l l i n g sequence i s ; CALL HATCH: (NOJ)F_BQUNDARIES, N0J3FJPTSj;NJTACHJBQUNDARY, XCOORS__OF_ALL_PTS, YCOORS_OF_ALL^PTS, HATCH_DIR. HATCH_GAP, WIDTH_OF_HATCH_LN, X_LOC, Y_LOC, XSC, YSC, ORIENT) VARIABLE TYPE NO OF BOUNDARIES DESCRIPTION Integer The number of boundaries d e f i n i n g the r e a l i z a t i o n r e g i o n . NO OF PTS IN EACH BOUNDARY Integer The ar r a y c o n t a i n i n g the number of p o i n t s d e f i n i n g each boundary. XCOORS OF ALL PTS Real The ar r a y c o n t a i n i n g the x coordi-nates of a l l p o i n t s d e f i n i n g the r e a l i z a t i o n r e g i o n . YCOORS OF ALL PTS Real The ar r a y c o n t a i n i n g the y coordi-nates of a l l p o i n t s d e f i n i n g the r e a l i z a t i o n r e g i o n . HATCH DIR Real The d i r e c t i o n of the hat c h i n g l i n e s i n r a d i a n s . HATCH GAP Real The spacing between ha t c h i n g l i n e s . WIDTH OF HATCH LN Integer The m u l t i p l e o f the d e f a u l t width. X LOC Real The x coordinates of the r e a l i z a t -i o n r e g i o n w i t h respect t o (.5,.5)-VARIABLE Y LOC XSC YSC ORIENT TYPE DESCRIPTION Real The y coordinates of the r e a l i z a t -i o n r e g i o n w i t h respect t o (. .5>.5). Real The s c a l e f a c t o r of the a b s c i s s a of the r e a l i z a t i o n r e g i o n w i t h respect t o (.5,-5). Real The s c a l e f a c t o r of the o r d i n a t e of the r e a l i z a t i o n r e g i o n w i t h respect t o (.5, •5) • Real The angle of r o t a t i o n of the r e a l -i z a t i o n r e g i o n about (.5, .5) i n ra d i a n s . h,5«3 A D e s c r i p t i o n of the Developed Hatching A l g o r i t h m U.5.3.1 A Short Note on the M a n i p u l a t i o n o f a R e a l i z a t i o n Region This s e c t i o n w i l l a i d i n the understanding of the d e s c r i p t i o n of the hatching algorithm. Consider the r e a l i z a t i o n r e g i o n shown i n Figure h.2 3a and assume t h a t the hat c h i n g l i n e s are at an angle of HATCH_DIR radians w i t h the x - a x i s . The manipul a t i o n of the r e a l i z a t i o n r e g i o n i s a two-step t a s k : 1) transform the v e r t i c e s d e f i n i n g the r e a l i z a t i o n r e g i o n . This t r a n s f o r m a t i o n i s a s s o c i a t e d w i t h the angle o f r o t a t i o n ORIENT of the r e a l i z a t i o n r e g i o n (Figure H.2 3b), 2) hatch the transformed r e a l i z a t i o n r e g i o n w i t h the gen e r a t i v e l i n e s at the angle of (HATCH_DIR + ORIENT) radians w i t h the x - a x i s (Figure k.23c). kk -> X (a) a r e a l i z a t i o n r e g i o n y (b) t r a n s f o r m a t i o n of the v e r t i c e s d e f i n i n g the r e a l i z a t i o n r e g i o n ! 1 ^ (c) the transformed r e a l i z a t i o n r e g i o n F i g u r e k.23 M a n i p u l a t i o n of a r e a l i z a t i o n r e g i o n h5 4.5.3.2 D e s c r i p t i o n of the Al g o r i t h m HATCH 1) Set HATCHJDIR * HATCHJ3IR.+ ORIENT 2) I f the f i v e a t t r i b u t e s <X_LOC, Y_LOC, XSC, ISC, ORIENT> are not the d e f a u l t v a l u e s , transform the v e r t i c e s t h a t d e f i n e the r e a l i z a t i o n r e g i o n , otherwise no t r a n s f o r m a t i o n i s necessary. 3) Rotate the r e a l i z a t i o n r e g i o n t o a new coordinate system w i t h i t s a b s c i s s a at an angle of HATCH_DIR radians w i t h the x - a x i s : i f HATCH_DIR ^ 0, then r o t a t e the coordinates of a l l data p o i n t s d e f i n i n g the r e a l i z a t i o n r e g i o n by - HATCH_DIR, e l s e ignore and go t o the next step. k) Repeat step 5 f o r j = 1, N0_0F_B0UNDARIES. 5) F i n d the c r i t i c a l p o i n t s and the p o i n t s of i n f l e c t i o n of boundary j : each v e r t e x of the c l o s e d polygon d e f i n e d by the boundary j i s examined to see i f i t i s a c r i t i c a l p o i n t or a p o i n t of i n f l e c t i o n . 6) Determine YMAX and YMIN, the maximum and minimum y-coordinates of the encasing r e c t a n g l e f o r the r e a l i z a t i o n r e g i o n . 7) Compute the number of s c a n l i n e s , NDIV: NDIV = INT ((YMAX - YMIN) / KATCH_GAP) 8) Perform hatching: repeat step 9 f o r k = 1, NDIV. 9) Repeat step 10 t o 11 f o r NW = 1, WIDTH_0F_HATCH_LN. 10) Obtain the general equation f o r y : y = y k = YMAX - k * HATCH_GAP - (NW - l ) * d e f a u l t t h i c k n e s s of a l i n e 11) Compute the s c a n l i n e s ' p o i n t s of i n t e r s e c t i o n w i t h the boundaries t o k k' ob t a i n the set Y , s o r t i t and o b t a i n Y . With the p r o v i s i o n s f o r k" k c r i t i c a l p o i n t s and p o i n t s of i n f l e c t i o n , o b t a i n Y , from which HL i s then d e r i v e d , 12) Rotate the r e a l i z a t i o n r e g i o n back t o the o r i g i n a l coordinate system: i f HATCH_DIR ^ 0 then r o t a t e the coordinates of a l l data p o i n t s d e f i n -i n g the r e a l i z a t i o n by HATCH_DIR, e l s e r e t u r n . k6 U . 5,h E v a l u a t i o n of the Developed Hatching A l g o r i t h m  V i r t u e s : 1) A. r e a l i z a t i o n r e g i o n , composed of one or more m u l t i p l y connected r e g i o n s , can he hatched (Figure h.2h). 2) The complement of a r e a l i z a t i o n r e g i o n can be obtained r e a d i l y by a s s i g n i n g a v i r t u a l u n i t square (Figure h . 2 5 ) . 3) The t h i c k n e s s o f , i n c l i n a t i o n of and the spacing between ha t c h i n g l i n e s are user d e f i n e d (Figure U . 2 6(a-b)). k) A r e a l i z a t i o n r e g i o n can be manipulated ( t r a n s l a t e d , r o t a t e d and s c a l -ed) (Figure k.2T). 5 ) The area of a r e a l i z a t i o n r e g i o n can be c a l c u l a t e d e a s i l y because i t i s d e s c r i b e d by encoding i t s boundaries [Appendix A ] . L i m i t a t i o n s : 1) Although the a l g o r i t h m can e a s i l y be m o d i f i e d i n t o a h a t c h i n g - f i l l i n g one, i t i s s u i t a b l e f o r v e c t o r graphics o n l y . 2 ) The a l g o r i t h m cannot handle polygon c l i p p i n g * . h.5•5 Future work 1) To convert t h i s a l g o r i t h m i n t o a h a t c h i n g - f i l l i n g one i s d e s i r a b l e . 2 ) The e f f i c i e n c y of the a l g o r i t h m should be evaluated and improved i f necessary. 3) The a l g o r i t h m should be m o d i f i e d t o handle polygon c l i p p i n g (see, f o r example Newman and S p r o u l l [Ne78]). * Any p a r t of a polygon t h a t l i e s o u t s ide the screen gets c l i p p e d o f f . This process i s r e f e r r e d t o as polygon c l i p p i n g , Figure h,2h' A realization region composed a multiply connected region Figure h.25 Complement of a r e a l i z a t i o n r e g i o n k9 Ca) hatching l i n e s of the default thickness Figure 4 , 2 6 Hatching patterns with associated sets of-hatching l i n e s at d i f f e r e n t i n c l i n a t i o n s , spacings . and thicknesses 50 Ch) hatching l i n e s of a .multiple of the d e f a u l t t h i c k n e s s Figure k.26 Hatching p a t t e r n s w i t h a s s o c i a t e d sets of hatching l i n e s at d i f f e r e n t i n c l i n a t i o n s , spacings and t h i c k n e s s e s F i g u r e 4 ,27 M a n i p u l a t i o n of a r e a l i z a t i o n r e g i o n 52 5. A SHORT REVIEW OF TWO GRAPHICS LANGUAGES Although researchers have f e l t the need f o r r e g i o n a l g r a p h i c s , most work has been l i m i t e d t o the use of e x i s t i n g l i n e - d r a w i n g graphics packages t o achieve the v i s u a l i z a t i o n of regions by the use of hatching or f i l l i n g techniques. Newman and S p r o u l l ' s [Ne75a] work i s a t y p i c a l example. B r a c c h i [ B r 7 l ] , based on the concept of data t y p e , suggested a language f o r t r e a t i n g geometric p a t t e r n s i n a two-dimensional space. The language constructs arid the c a p a b i l i t y of t h i s h y p o t h e t i c a l language seem t o be reasonably good. However, the e x t e r n a l r e p r e s e n t a t i o n of p a t t e r n s or regions has been overlooked. Nake [Na7l], u s i n g the r e g i o n a l e x t e r n a l r e p r e s e n t a t i o n model, proposed a language, but i t i s l i m i t e d t o g r a p h i c s , w i t h no numerical c a p a b i l i t y . However, the u n d e r l y i n g concept i s good and i t forms the s k e l e t o n of LIG as w e l l as t h a t of the proposed language. In the f o l l o w i n g s e c t i o n s , reviews and comments are given on Newman et a l . and B r a c c h i et a l . ' s work. 5.1 Review of Newman and S p r o u l l ' s Work [Ne75a] Newman and S p r o u l l d i s c u s s the design of g r a y - s c a l e graphics software f o r r a s t e r scan d i s p l a y devices. With t h e i r package, the user can define and d i s p l a y line-drawn as w e l l as s o l i d - a r e a g r a p h i c a l o b j e c t s . B a s i c a l l y , i t i s an extension of the c o n v e n t i o n a l l i n e - d r a w i n g graphics package but w i t h four new f u n c t i o n s , BEGINFILL, ENDFILL, SETCOLOR, UPDATE. The BEGINFILL and ENDFILL are f u n c t i o n s t h a t mark the s t a r t and the end of the f i l l i n g o p e r a t i o n . The SETCOLOR f u n c t i o n i s used f o r a s s i g n i n g a c o l o u r or a gray l e v e l t o a given g r a p h i c a l o b j e c t . A para-meter l i s t i s a s s o c i a t e d w i t h t h i s f u n c t i o n f o r gray l e v e l or c o l o u r s e l e c t i o n . The UPDATE f u n c t i o n i s used f o r updating the p i c t u r e s on the screen i n order t o describe the most recent p i c t u r e s t o r e d i n t e r n a l l y . 53 Consider the c o n s t r u c t i o n of a f i l l e d green polygon shown i n Figure 5-1 hy the f o l l o w i n g i n s t r u c t i o n sequence: BEGINFILL SETCOLOR (GREEN) MOVETO (XA,YA) DRAWTO (XB,YB) DRAWTO (XC,YC) DRAWTO (XD,YD) DRAWTO (XE,YE) DRAWTO (XF,YF) ENDFILL MOvETO ( X i , Y i ) and DRAWTO ( X j , Y j ) are con v e n t i o n a l l i n e - d r a w i n g i n s t r u c t i o n s . They are used t o def i n e the boundary of the object t o be Figure 5.1 A . f i l l e d polygon The UPDATE f u n c t i o n r e q u i r e s an e f f i c i e n t a l g o r i t h m f o r h a n d l i n g the overlapping of opaque o b j e c t s . Two a l g o r i t h m s , d e r i v e d from hidden-surface algorithms are discussed i n d e t a i l i n [Ne75a]-5.2 Comments on Newman and S p r o u l l ' s Work A data type f o r opaque g r a p h i c a l o b j e c t s i s not used i n t h i s package. Rather, the package uses the f u n c t i o n s BEGINFILL and ENDFILL t o produce v i s u a l l y opaque ob j e c t s by f i l l i n g the areas enclosed by the boundaries. Because an opaque object i s not a s s o c i a t e d w i t h a name, the f i l l e d . 54 d i s p l a y of the same obje c t elsewhere on the screen w i l l r e q u i r e a d e f i n i t i o n of the boundary again. 5-3 Review of B r a c c h i and F e r r a r i ' s Work [ B r T l ] CADEP (Computer A s s i s t e d D e s c r i p t i o n of P a t t e r n ) i s the language proposed by B r a c c h i et a l . f o r t r e a t i n g geometric p a t t e r n s i n a two-dimensional space. I t i s a h y p o t h e t i c a l language t h a t has not been implemented. Although i t has been designed f o r automatic mask g e n e r a t i o n , i t i s claimed t o be u s e f u l i n many a p p l i c a t i o n s such as placement . problems, block diagram r e p r e s e n t a t i o n s e t c . The language i s an extension of F o r t r a n w i t h g r a p h i c - o r i e n t e d F o r t r a n compatible statements. There are three b a s i c data type v a r i a b l e s i n CADEP, the conventional F o r t r a n v a r i a b l e s , geometric v a r i a b l e s and graphic v a r i a b l e s . J u s t as each conventional F o r t r a n v a r i a b l e has a v a l u e , so does each geometric v a r i a b l e and graphic v a r i a b l e have a value . However, the value of a geometric or graphic v a r i a b l e i s the e n t i r e data s t r u c t u r e r e p r e s e n t i n g the p a t t e r n a s s o c i a t e d w i t h the v a r i a b l e . A l l v a r i a b l e s except conventional F o r t r a n have t o be decl a r e d (e.g. GEOMETRIC GV1, GV2, . . . ) . Each dec l a r e d geometric v a r i a b l e represents a geometric e n t i t y l y i n g i n the same geometric plane. This plane i s not bounded and p o i n t s on i t are defined by x and y coordinates. Complicated p a t t e r n s can be created on the geometric plane by d e f i n i n g geometric p r i m i t i v e s (defined t o be the smallest geometric v a r i a b l e s ) , by u s i n g geometric expressions and manipulation f u n c t i o n s , and by a l l o w i n g p a t t e r n s t o ove r l a p . There are eleven geometric p r i m i t i v e s i n CADEP. These are l i s t e d i n F i g ure 5.2. A l l p r i m i t i v e s are two-dimensional p a t t e r n s and thus a l i n e i s a r e c t a n g l e of very small width. LNC (XI ,Y1 ,X2 ,Y2 tW ) (XI ,YI) 55 IX2 . Y2) LNP ( XI , Y1 , RHO , THETA , W ) ARC ( X1 , YI ,X2 ,Y2 ,R ,W ) (XI. YD (X2 ,Y2) rxitYD (Terminal points of the arc are assigned in a ccunter-R clockwise order on the arete to which the arc belongs) CRCL (XI , Y1 , R ) SECT ( XI ,Y1 ,R , ALFA1 , ALFA 2) ( X1,Y1) RECT ( X1 ,Y1 ,X2 , Y2) (X1.Y1) 1X2, Y2) RECS (XI ,Y1 ,S1 ,S2) $2 SI (X1,Y1> (S1 and $2 are signed numbers) (XN, YN) POLY (XI ,Y1 ,X2: ,Y2, XN, YN) (Vertices should be listed in a counterclockwise order starling from an arbitrary vertex) FPLANE Tht tntlrt geometric plane H PLANE ( XA ,YA , ALFA) EMPTY The complement of FPLANE F i g u r e 5,2 Geometric p r i m i t i v e s i n CADEP [Br7l] 56 Three operations are allowed i n the geometric p l a n e , i n t e r s e c t -i o n , union and d i f f e r e n c e . In order t o d e s c r i b e ..physical o b j e c t s whose shapes or p a t t e r n s have been defined i n the geometric plane, v a r i a b l e s of type GRAPHIC are necessary. Since CADEP has been designed f o r automatic mask generation and so i s concerned w i t h d i f f e r e n t l e v e l s , the graphic data type i s f u r t h e r subdivided i n t o two data t y p e s , UNILEVEL and MULTILEVEL. V a r i a b l e s of type UNILEVEL represent p h y s i c a l two-dimensional e n t i t i e s l y i n g i n a p a r t i c u l a r graphic plane. V a r i a b l e s of type MULTILEVEL represent the same p h y s i c a l object and are composed of s e v e r a l u n i l e v e l p a t t e r n s l y i n g i n d i f f e r e n t graphic planes. Examples of d e c l a r a t i o n statements f o r u n i l e v e l ( l e v l , lev2) and' m u l t i l e v e l ( m u l t l , mult2) v a r i a b l e s r e s p e c t i v e l y are: LEVEL(i) l e v l , lev2, .... where i denotes a l e v e l and i = 1, 2, 3, ... GRAPHIC m u l t l , mult2, ... U n l i k e the geometric p l a n e , the ove r l a p p i n g of p a t t e r n s i s not allowed i n the graphic plane. The graphic plane i s d e f i n e d by the p h y s i c a l s i z e of the d i s p l a y u n i t . Operators f o r u n i l e v e l and graphic v a r i a b l e s are the union operator (+) and the concatenation operator (*) r e s p e c t i v e -l y -5-U Comments on B r a c c h i and F e r r a r i ' s Work In computer g r a p h i c s , the f e a t u r e s provided f o r t e s t i n g the r e l a t i o n s h i p s (such as d i s t a n c e , i n c l u s i o n , ...) between p a t t e r n s are not important i n p r a c t i c e ( f o r computer-aided design purposes). However, ess-e n t i a l f e a t u r e s such as the use of d e f a u l t values f o r geometric p r i m i t i v e s are not s p e c i f i e d , A SETCOLOR f u n c t i o n or other means of a s s i g n i n g c o l o u r or gray-l e v e l t o a g r a p h i c a l object i s not dis c u s s e d . The d i s t i n c t i o n between 57 p a t t e r n s or g r a p h i c a l o b j e c t s u s i n g c o l o u r s , g r a y - l e v e l s or h a t c h i n g p a t t e r n s i s an important aspect of a r e g i o n a l graphics language, From the i l l u s t r a t i o n of geometric p r i m i t i v e s , i t seems th a t hatching p a t t e r n s may be proposed. I t i s not s t a t e d e x p l i c i t l y whether ha t c h i n g p a t t e r n s are used or how the p a t t e r n s are s p e c i f i e d i n language c o n s t r u c t s . The d i s t i n c t i o n between the two data types: GEOMETRIC and GRAPHIC f o r the d e s c r i p t i o n of p a t t e r n s i s not necessary. I n s t e a d , one data type f o r d e f i n i n g and r e p r e s e n t i n g p a t t e r n s i s adequate. This can be done by a l l o w i n g p a t t e r n s t o be d e f i n e d u s i n g unmodified or m o d i f i e d p r i m i t i v e s i n a plane. This plane i s f i n i t e and d e f i n e d by the p h y s i c a l s i z e o f the d i s p l a y u n i t . Any p a r t or even the e n t i r e p a t t e r n , not f a l l i n g w i t h i n the f i n i t e p lane, are c l i p p e d . The use of t h i s scheme (using the concept of d e f i n i t i o n frame) has been implemented s u c c e s s f u l l y i n LIG. There are a number of good f e a t u r e s i n CADEP. The use of data types f o r d e s c r i b i n g and t r e a t i n g geometric p a t t e r n s as a named u n i t datum i s a p p r o p r i a t e . F u r t h e r , the concept of l e v e l , an important f e a t u r e i n a good r e g i o n a l graphics language, i s found i n CADEP. 58 6. A PROPOSED REGIONAL GRAPHICS LANGUAGE The f i r s t step towards the c r e a t i o n and implementation of a h i g h - l e v e l programming language i s the d e f i n i t i o n of the language i t s e l f . This r e q u i r e s a c l e a r statement of the purpose of the language. Towards t h i s end, a formal d e s c r i p t i o n of a g r a p h i c a l object i n the proposed language i s presented. This i s f o l l o w e d by a proposed set of p r i m i t i v e s , operators and language statements. The conceptual and t e c h n i c a l c h a r a c t -e r i s t i c s are discussed as w e l l . 6.1 A Formal D e s c r i p t i o n of a G r a p h i c a l Object i n the Proposed Regional  Graphics Language, u s i n g the Regional E x t e r n a l Representation Model A g r a p h i c a l object may be def i n e d by the f o u r - t u p l e : <N, D, R, X > where N i s the name of the g r a p h i c a l o b j e c t , D i s the d e f i n i t i o n frame d e f i n e d by a f i v e - t u p l e of p a i r s of coo r d i n a t e s , R i s the coordinate p a i r d e f i n i n g the refe r e n c e p o i n t of the g r a p h i c a l o b j e c t , X i s the set of transformed g r a p h i c a l p r i m i t i v e s used. Let B e X, then B can be described by a two-tuple: B = < P', 0 > where P' i s an element of the set of g r a p h i c a l p r i m i t i v e P, 0 i s a subset of M which i s the set of m o d i f i c a t i o n operators of the form: M = {< ANGLE, parameter! >, < SCALE, parameter2, parameter3 >, <AT, parameter^, parameter5 >, •. .} where ANGLE, SCALE, AT are m o d i f i c a t i o n operators. 59 Example: Consider the d e s c r i p t i o n of the g r a p h i c a l o b j e c t shown i n Figure 6 ,1 . Figure 6.1 A g r a p h i c a l object composed o f opaque and l i n e -drawn g r a p h i c a l p r i m i t i v e s N = G i r l D = {(0. , 0 . ) , ( l . , 0 . ) , ( 1 . , 1 - ) , ( 0 . , 1 . ) , (0 . , 0 . )} R = ( 0 . 5 , 0 . 5 ) X = {B l 5 B 2, B 3, B u, B , Bg, B ?} B l = <DISK, ° 1 > B 2 = <RTRIAWGLE B 3 = <LINE, V Bk = <LINE, V V <LINE, V B 6 = <LINE, V V <LINE, DISK, RTRIANGLE, LINE are g r a p h i c a l p r i m i t i v e s . 0 ^ . . . 5 0^ are sets of m o d i f i c a t i o n operators w i t h a s s o c i a t e d parameters. 60 A graphical p r i m i t i v e P', chosen from P can be described by a four-tuple: P' = <N' , D, R, S, A > vhere W i s the name of the graphical p r i m i t i v e , D i s the d e f i n i t i o n frame, R i s the reference p o i n t , S i s the graphical datum associated with N', A i s a two-tuple of a t t r i b u t e s given by: A = <C, L > where C denotes the colour assigned, L denotes the l e v e l assigned. N' i s an element of set V. V i s a set of reserved names with a defined syntax. 6.2 The Regional Graphics Language LIGE The high l e v e l graphics programming language LIG has been i n operation for many years. During t h i s p eriod, i t has been found by many programmers to be a graphics language which i s easy to le a r n and easy to use. This language, although one of the few graphics languages that u t i l i z e the re g i o n a l external representation model, should be considered as a 'weak' re g i o n a l graphics language. The term 'weak' i s used since the language was designed to handle line-drawing graphics, but has been r e f i n -ed and expanded to handle both line-drawn and s o l i d - a r e a g r a p h i c a l objects. In view of the general acceptance of LIG, a 'weak' r e g i o n a l graphics language, i t i s used as a s t a r t i n g point f o r the proposed region-a l graphics programming language, hereafter c a l l e d LIGE. I t i s an exten-sion of LIG and i s capable of dealing with graphical object such as 61 Figure 6.1. Because LIGE i n c l u d e s LIG, d i s c u s s i o n of f e a t u r e s a v a i l a b l e i n LIG w i l l not be presented. Rather, a t t e n t i o n i s focused on those f e a t u r e s that are a v a i l a b l e i n LIGE only. In the sequel, knowledge of LIG i s assumed. 6.2 .1 A G r a p h i c a l D e c l a r a t i o n Statement The a s s o c i a t i o n of a name w i t h a g r a p h i c a l o b j e c t w i l l be d e f i n e d as a g r a p h i c a l v a r i a b l e . A g r a p h i c a l v a r i a b l e has as i t s value a g r a p h i c a l o b j e c t . A l l g r a p h i c a l v a r i a b l e s i n LIGE are of the same typ e , GRAPHICAL. The data type GRAPHICAL represents the k i n d of two-dimensional i n f o r m a t i o n from which s o l i d areas as w e l l as line-drawings can be composed. A g r a p h i -c a l d e c l a r a t i o n statement c o n s i s t s of the reserved word GRAPHICAL f o l l o w -ed by a l i s t of names or i d e n t i f i e r s . For example: * GRAPHICAL EX_1, EX_2; * GRAPHICAL A, B, BB(lO); 6 . 2 . 2 A Proposed Set of G r a p h i c a l P r i m i t i v e s f o r LIGE Using the r e g i o n a l e x t e r n a l r e p r e s e n t a t i o n model, LIG t r e a t s a l l g r a p h i c a l o b j e c t s as s u r f a c e s . There are s i x g r a p h i c a l p r i m i t i v e s i n LIG (Figure 6 . 2 ) . Each g r a p h i c a l p r i m i t i v e i s d e f i n e d on a planar f i n i t e s urface. For convenience, the surface i s d e f i n e d t o be a u n i t square. Any p o r t i o n ( e x c l u d i n g the u n i t square) t h a t appears b l a c k or opaque belongs t o t h a t p o r t i o n of the g r a p h i c a l p r i m i t i v e t h a t has a c e r t a i n colour assigned. The r a t i o of the areas between the l a t t e r p o r t i o n and the u n i t square i s c a l l e d the opaque value . The opaque value range from 0 (BLANK) t o 1 (TILE). However, although t h i s set of g r a p h i c a l p r i m i t i v e s i s not s u f f i c i e n t t o c o n s t r u c t a g r a p h i c a l o b j e c t such as F i g u r e 6.1, i t i s adequate f o r c o n s t r u c t i n g a wire-frame g r a p h i c a l o b j e c t such as Figure. 6.3 A g r a p h i c a l object 6 3 Figure 6.3. Thus, the set of p r i m i t i v e s i n LIGE must he extended t o i n c l u d e p r i m i t i v e s w i t h higher opaque values than those i n LIG. F u r t h e r -more, si n c e g r a p h i c a l p r i m i t i v e s are f o r the users' convenience, t h e i r choice must come from the user. A g r a p h i c a l p r i m i t i v e such as Figure 6.4a may be more u s e f u l than the one shown i n F i g u r e 6.4b f o r a p a r t i c u l a r user. In g e n e r a l , the f o l l o w i n g two r u l e s may be found u s e f u l i n choosing the set of g r a p h i c a l p r i m i t i v e s . F i r s t , a convenient minimal set of g r a -p h i c a l p r i m i t i v e s i s d e s i r e d . Secondly, the g r a p h i c a l p r i m i t i v e chosen must be the s m a l l e s t component p o s s i b l e . For i n s t a n c e , the g r a p h i c a l p r i m i t i v e such as Figure 6.5a i s more u s e f u l than the one i n F i g u r e 6.5b. The reason i s obvious: F i g u r e 6.5b can be c o n s t r u c t e d u s i n g F i g u r e 6.5a but not v i c e v e r s a . With t h i s i n mind, a proposed set of g r a p h i c a l p r i m i -t i v e s f o r LIGE i s presented. Denote P t o be the set of g r a p h i c a l p r i m i t i v e s f o r LIGE. Then P can be described as: P = { BLANK, LINE, SQUARE, CIRCLE, SCIRCLE, TRIANGLE, DISK, TILE, RTRIANGLE, LSECTOR, QRING} The f i r s t s i x p r i m i t i v e s are i d e n t i c a l t o t h a t of LIG w h i l e the l a s t f i v e p r i m i t i v e s (Figure 6.6) are a v a i l a b l e only i n LIGE. Figure 6 . 5 Graphical p r i m i t i v e s 65 DISK TILE RTRIANGLS Figure 6.6 Graphical p r i m i t i v e s defined i n LIGE hut not i n LIG 66 6.2.3 A Proposed Set of G r a p h i c a l Operators f o r LIGE In the previous s e c t i o n , the g r a p h i c a l p r i m i t i v e s f o r g r a p h i c a l objects are discussed. In t h i s s e c t i o n , the d i s c u s s i o n i s focused on how complex g r a p h i c a l o b j e c t s can be b u i l t up or de f i n e d w i t h the help of g r a p h i c a l operators. There are two kinds of g r a p h i c a l operators i n LIGE, the unary and the b i n a r y g r a p h i c a l operators. The unary g r a p h i c a l operators An unary g r a p h i c a l operator i s one t h a t acts on a s i n g l e g r a p h i -c a l operand only. Each operator has one or more numerical arguments. The unary operators a v a i l a b l e i n LIGE are: 1) the s c a l i n g operator (SCALE), 2) the p o s i t i o n operator (AT), 3) the r o t a t i o n operator (ANGLE), h) the l i n e operator (LINE), 5) the naming operator (AS), 6) the colour operator (COLOUR), 7) the p r i o r i t y operator (LEVEL), Note t h a t the colour and p r i o r i t y operators are not a v a i l a b l e i n LIG. By d e f a u l t , a g r a p h i c a l p r i m i t i v e i s of co l o u r BLACK and of l e v e l 1. L e v e l 1 i s the lowest l e v e l and the next higher i s l e v e l 2, e t c . A g r a p h i c a l object of a higher l e v e l than another i s s a i d t o have a higher p r i o r i t y i n v i s i b i l i t y than the other. The f o l l o w i n g two examples w i l l demonstrate how the operators may be used: 67 Example 1 * GRAPHICAL A; « t « * A TILE COLOUR 'GREEN1 LEVEL 2 ; • « « A i s a g r a p h i c a l object w i t h c o l o u r a t t r i b u t e GREEN and l e v e l a t t r i b u t e 2. Example 2 * GRAPHICAL A, B; * B :- DISK COLOUR 'BLUE' LEVEL 3 <m1> + RTRIANGLE COLOUR 'RED1 LEVEL 2 <m2> ; A :- B COLOUR 'GREEN' LEVEL 2 <m3> ; where <m-^ >> <m2>' <m2> denote m o d i f i c a t i o n s . B i s g r a p h i c a l object composed of two g r a p h i c a l p r i m i t i v e s , DISK and RTRIANGLE, each w i t h d i f f e r e n t c olour and l e v e l a t t r i b u t e s . A i s a g r a p h i c a l object composed of two g r a p h i c a l p r i m i t i v e s DISK and RTRIANGLE both having the same colour (green) and l e v e l (2) a t t r i b u t e s . A complement operator c o u l d a l s o be introduced. I t s e f f e c t i s t o interchange the co l o u r s of the g r a p h i c a l object and the background. Some examples are given i n Fi g u r e 6.7 t o show the e f f e c t s - o f the complement operator on g r a p h i c a l p r i m i t i v e s . Note t h a t g r a p h i c a l o b j e c t s * M o d i f i c a t i o n r e f e r s t o the r e d e f i n i t i o n of the d e f a u l t p o s i t i o n , s c a l -i n g s , o r i e n t a t i o n , c o l o u r and l e v e l of a g r a p h i c a l o b j e c t u s i n g unary operators AT, SCALE, ANGLE, COLOUR, and LEVEL. 68 can "be obtained without the use of the complement operator ( F i g u r e 6.7 (a-b)) s i n c e s u p e r p o s i t i o n of g r a p h i c a l o b j e c t s w i t h d i f f e r e n t l e v e l s and appropriate c o l o u r s can achieve the same v i s u a l e f f e c t as t h a t o f the complement operator (Figure 6 , 7(c-d)). For these reasons, the complement operator i s not i n c l u d e d i n LIGE. F i g u r e 6,7 The e f f e c t s of the complement operator on g r a p h i c a l p r i m i t i v e s 6 9 The b i n a r y g r a p h i c a l operators A b i n a r y g r a p h i c a l operator r e q u i r e s two g r a p h i c a l operands as arguments. An argument can be a m o d i f i e d or unmodified g r a p h i c a l v a r i a b l e . There are two b i n a r y g r a p h i c a l operators i n LIGE, the s u p e r p o s i t i o n (denoted by '+') and the d e l e t i o n (denoted by '-') operators. Example * GRAPHICAL FRUIT, ORANGE, Q; * FRUIT :- FRUIT + ORANGE <m> AS Q ; * FRUIT :- FRUIT - Q ; where <m> denotes one or more m o d i f i c a t i o n s . Before the LIGE language statements are presented, the import-ance and usefulness of the BLANK p r i m i t i v e deserves some d i s c u s s i o n . There are two. common usages of the BLANK p r i m i t i v e s : 1) I n i t i a l i z a t i o n The f o l l o w i n g i s an example comparing a segment of an LIGE program w i t h t h a t of a F o r t r a n program. * GRAPHICAL SAMPLE, A ( l O ) ; REAL SAMPLE, A(lO) • • • * • • * • SAMPLE :- BLANK; SAMPLE = 0. DO 10 I = 1, 10 DO 10 I = 1, 10 * SAMPLE :- SAMPLE + A ( l ) ; SAMPLE = SAMPLE + A ( l ) 10 CONTINUE 10 CONTINUE 2) I d e n t i f i c a t i o n #* Since an ins t a n c e of the BLANK p r i m i t i v e can be i d e n t i f i e d , i t **The value of a g r a p h i c a l v a r i a b l e , which has been m o d i f i e d , i s c a l l e d an instance of th a t g r a p h i c a l ' v a r i a b l e . TO i s u s e f u l t o use the BLANK p r i m i t i v e f o r producing a menu (Figure 6 . 8 ) . t e r m i n a l screen i n v i s i b l e frames Fi g u r e 6.8 A menu 6.2.4 A t t r i b u t e E x t r a c t i o n Statements f o r LIGE XLOC, YLOC, XSCALE, YSCALE, ANGLE are a t t r i b u t e e x t r a c t i o n f u n c t i o n s i n LIG. A number of a d d i t i o n a l statements are a v a i l a b l e i n LIGE language. These are concerned w i t h the p h y s i c a l p r o p e r t i e s of g r a p h i c a l o b j e c t s . Often, the area of a g r a p h i c a l object i s d e s i r e d . The f o l l o w i n g LIGE statement: * GRAPHICAL GRJOBJ ; REAL AOBJ AOBJ = AREA(GR OBJ) •, w i l l a s s i g n the value of the area of GR__OBJ t o the numerical v a r i a b l e AOBJ. The sum of the areas of a l l the g r a p h i c a l o b j e c t s c u r r e n t l y d i s p l a y e d can be obtained by executing the f o l l o w i n g LIGE statement: 71 REAL AOBJ * AOBJ = AREAJDISPLAY j .-/* . AQBJ i s a numerical v a r i a b l e . * / Two f u n c t i o n s , XCG, YCG are a v a i l a b l e f o r f i n d i n g the x - c o o r d i -nate and y-coordinate of the centre of g r a v i t y of a g r a p h i c a l object (always assumed t o be of uniform d e n s i t y ) . 6.2.5 I/O Statements f o r LIGE In LIG, the I/O statements are the DISPLAY, HARDCOPY, DRAW, ERASE, CURSOR and READ CURSOR. The I/O statements f o r LIGE, i n a d d i t i o n to those of LIG, are the PAINT, BRUSH, DISPLAY LEVEL, DISPLAY COLOUR. 1) The PAINT statement When a region on the screen r e q u i r e s s p e c i a l a t t e n t i o n , s t a t e -ments of the form: * PAINT WITH MASK <xcoor>, <ycoor>, <nvertices> ; * PAINT WITH MASK <xcoor>, <ycoor>, <nvertices> COLOUR <string> ; are used where <xcoor> denotes an array t h a t contains the x coordinates of the v e r t i c e s d e f i n i n g the mask, <ycoor> denotes an a r r a y t h a t contains the y coordinates of the v e r t i c e s d e f i n i n g the mask, <nvertices> denotes the number of v e r t i c e s d e f i n i n g the--.mask and <string> denotes a.colour. In the f i r s t example, the d e f a u l t c o l o u r , 'BLACK', i s assumed. The r e g i o n thus obtained cannot be transformed as i t i s not sto r e d i n the data base, 2) The BRUSH statement (Figure 6.9) ~ While a draw statement i s used i n both l i n e and r e g i o n a l graph-i c s , a brush statement i s s p e c i f i c t o r e g i o n a l g r a p h i c s . For example, the execution of the statements * BRUSH FROM xprev, yprev TO x c u r r , y c u r r ; * BRUSH FROM xprev, yprev TO x c u r r , y c u r r WIDTH w ; w i l l have the e f f e c t of producing a l i n e w i t h t h i c k n e s s w u n i t , by d e f a u l t F i g u r e 6 , 9 An example of the e f f e c t of e x e c u t i n g the BRUSH statement (the f i r s t example), w i s 0 . 0 5 . The host language v a r i a b l e s are xprev, yprev, x c u r r , y c u r r and w. The DISPLAY LEVEL and the DISPLAY COLOUR statements The DISPLAY LEVEL and the DISPLAY COLOUR statements w i l l be use-f u l i n a p p l i c a t i o n such as i n t e g r a t e d c i r c u i t mask design. For i n s t a n c e , a l l t r a n s i s t o r s of a p a r t i c u l a r k i n d are represented w i t h a p a r t i c u l a r c o l o u r . Execution of the DISPLAY COLOUR statement w i t h t h a t c o l o u r as an input parameter w i l l e f f e c t i v e l y d i s p l a y a l l t r a n s i s t o r s of t h a t p a r t i c u -l a r k i n d on the screen. 3) The DISPLAY LEVEL statement Only those p a r t s of g r a p h i c a l o b j e c t s w i t h the s p e c i f i e d l e v e l or range of l e v e l s are d i s p l a y e d . * DISPLAY LEVEL L1,L2 ; (a range of l e v e l s ) * DISPLAY LEVEL L I ; (one p a r t i c u l a r l e v e l ) * DISPLAY LEVEL ; ( a l l e x i s t i n g l e v e l s ) L I , L2 denote l e v e l numbers. k) The DISPLAY COLOUR statement Only those p a r t s of g r a p h i c a l o b j e c t s w i t h the s p e c i f i e d colour or set of colours are d i s p l a y e d . * DISPLAY COLOUR C1,C2,C3,... ; (a set of c o l o u r s ) * DISPLAY COLOUR C l ; (one p a r t i c u l a r c o l o u r ) * DISPLAY COLOUR ; ( a l l e x i s t i n g c o l o u r s ) C l , C2, C3 denote colour s t r i n g s . 6.2.6 A Gr a p h i c a l Function f o r LIGE A g r a p h i c a l f u n c t i o n r e f e r s t o a s p e c i a l operator which y i e l d s a r e s u l t whose value i s a g r a p h i c a l o b j e c t . The r e s u l t may be dependent on a set of input parameters a s s o c i a t e d w i t h the f u n c t i o n . Ik REGION i s a g r a p h i c a l f u n c t i o n w i t h a set of input parameters, v i z . arrays (.X and Y) of x-coordinates and y-coordinates of the v e r t i c e s d e f i n i n g the g r a p h i c a l o b j e c t , the number of v e r t i c e s d e f i n i n g the r e g i o n (NVERT) and the colour s p e c i f i e d f o r the g r a p h i c a l o b j e c t . By d e f a u l t , colour i s bla c k . Example * GRAPHICAL GF, GG ; REAL X ( 1 0 ) , Y ( 1 0 ) * GF :- REGION(X, Y,NVERT,'BLACK') SCALE .5,-2 ; * GG :- REGION(X,Y,NVERT) SCALE .5,-2 ; /* D e f a u l t */ * Note th a t the value of the f u n c t i o n REGION i s a g r a p h i c a l object' which i s a simply connected r e g i o n . A f u n c t i o n which can generate a m u l t i p l y connected r e g i o n w i l l r e q u i r e more input parameters such as the number of boundaries d e f i n i n g the r e g i o n and the number of v e r t i c e s d e f i n i n g each of these boundaries. 7. CONCLUSIONS A systematic attempt has been made t o u n i f y the theory and various techniques f o r r e g i o n a l graphics. A r e g i o n a l e x t e r n a l r e p r e s e n t a -t i o n model f a c i l i t a t e s a c o n s i s t e n t d e s c r i p t i o n and provides a convenient means f o r d e a l i n g w i t h both line-drawn and opaque g r a p h i c a l o b j e c t s . In order t o understand how t h i s type of g r a p h i c a l object can be handled, a thorough study of the i n t e r n a l and e x t e r n a l r e p r e s e n t a t i o n s of regions has been c a r r i e d out. A good i n t e r n a l r e p r e s e n t a t i o n scheme f o r a r e g i o n i s one t h a t makes i t easy t o manipulate and e f f i c i e n t l y evaluate the p h y s i c a l p r o p e r t i e s of the r e g i o n . E x t e r n a l r e p r e s e n t a t i o n s of regions r e l y on the type of graphics d i s p l a y system a v a i l a b l e . A ve c t o r graphics system achieves the e x t e r n a l r e p r e s e n t a t i o n of regions by the use of '. hatching p a t t e r n s . A good hatching a l g o r i t h m i s one t h a t i s capable of producing a l a r g e set of d i s t i n c t i v e h a tching p a t t e r n s c o n v e n i e n t l y and e f f i c i e n t l y . A reasonably l a r g e set of t h i s k i n d can be guaranteed i f a hatching a l g o r i t h m allows a user t o d e f i n e the t h i c k n e s s and i n c l i n a t i o n of the hatching l i n e s . The mathematical and conceptual aspects of ha t c h i n g algorithms have been discussed. Through a systematic i n v e s t i g a t i o n , some of the fundamental concepts of hatching algorithms were e s t a b l i s h e d . Eased on these e s t a b l i s h e d concepts, a hatching a l g o r i t h m was then developed. I t has been found t o be s u c c e s s f u l i n a c h i e v i n g the expected t a s k s . Adopting the concept of t r e a t i n g g r a p h i c a l data as a data t y p e , the r e g i o n a l graphics language LIGE has been proposed. Some f e a t u r e s of the language has been implemented w i t h a l l g r a p h i c a l v a r i a b l e s belonging to the type GRAPHICAL. A complete l i s t of the r e q u i r e d f e a t u r e s f o r a language w i l l not be a v a i l a b l e at an e a r l y stage. Thus, f i r s t a proposed language w i l l have t o be t e s t e d i n a c t u a l use. In order t o have the maximum feedback, users from v a r i o u s f i e l d s should attempt w r i t i n g d i f f e r e n t a p p l i c a t i o n programs. The advantages and disadvantages of the language can then be considered, and refinements of the language i n c o r -porated. The improved language w i l l then l e a d t o f u r t h e r improvements. Hence, the proposal of LIGE c o n s t i t u t e s the f i r s t step towards the con-s t r u c t i o n of a h i g h - l e v e l r e g i o n a l graphics programming language. BIBLIOGRAPHY The f o l l o w i n g a b b r e v i a t i o n s are used i n the b i b l i o g r a p h y ; ACM: A s s o c i a t i o n f o r Computing Machinery CAD: Computer-Aided Design CGIP: Computer Graphics and Image Pr o c e s s i n g FJCC: F a l l J o i n t Computer Conference IEEE: The I n s t i t u t e of E l e c t r i c a l and E l e c t r o n i c Engineers IFIP: I n t e r n a t i o n a l F e deration of Information P r o c e s s i n g S o c i e t i e s JACM: J o u r n a l of A s s o c i a t i o n f o r Computing Machinery SJCC: Spring J o i n t Computer Conference AFIPS: American Federation of Information P r o c e s s i n g S o c i e t i e s UAIDE: User of Automatic Information D i s p l a y Equipment SIGGRAPH: ACM S p e c i a l I n t e r e s t Group on Computer Graphics [Ad76a] Adamowicz, M., Albano, A., "A s o l u t i o n of the r e c t a n g l e c u t t i n g -s t o c k i n g problem," IEEE Transactions on Systems, Man, and Cyber-n e t i c s , v o l . SMC-6, no.k, A p r i l 1 9 7 6 , 302 - 3 1 0 . [Ad76b] Adamowicz, M., Albano, A., "Nesting two-dimensional shapes i n r e c t a n g u l a r modules," CAD, v o l . 8 , n o . l , 1 9 7 6 , 2 7 - 3 3 . [Ag77] Aggarwal, R. et a l . , Computer Methods i n Image A n a l y s i s , IEEE, Wiley, 1977. [A175] Albano, A., "Computer-aided design of optimum two-dimensional l a y o u t , " I n t e r a c t i v e Systems. Eurocomp Conference, Online Pub-l i s h e r , 1 9 7 5 , l h 3 - 1 5 h . [Ap73] A p o s t o l , T.M., Mathematical A n a l y s i s , A Modern Approach t o Advan-ced C a l c u l u s , Addison-Wesley, 1 9 7 3 . [Ba75] B a l l a r d , A., The UBC-XPL Manual, Vancouver, B.C., The U n i v e r s i t y of B r i t i s h Columbia, 1 9 7 5 . [Be69] B e h l e r , B., Zajac, E.E., "A g e n e r a l i z e d window-shield r o u t i n e , " Proc. 8 t h UAIDE meeting, Coronado, C a l i f o r n i a , 1969-[Be7l] . Belady, L.A. et a l . , "A computer graphics system f o r b l o c k d i a -gram problems," IBM Systems J o u r n a l , no.2, 1 9 7 1 , 1^3-165. 78 [Be73]' Berk, T.S., "TUNA: A high l e v e l g r a p h i c a l programming language," F l o r i d a I n t e r n a t i o n a l U n i v e r s i t y , Mathematical Science Dept., T e c h n i c a l Report, Feb. 1973. [Br70] B r a c c h i , G., "An i n t e r a c t i v e software system f o r computer-aided design: An a p p l i c a t i o n to c i r c u i t p r o j e c t , " Communications ACM, v o l . 1 3 , no.9, Sept. 1970, 537-5^5. [ B r 7 l ] B r a c c h i , G., F e r r a r i , D., "A language f o r t r e a t i n g geometric p a t t e r n s i n a two-dimensional space," Communications ACM, v o l . 1 4 , n o . l , Jan. 1971, 26-32. [Br78] B r a s s e l , K.E., Utano, J . J . , "Font v a r i a t i o n s i n v e c t o r p l o t t e r l e t t e r i n g , " Computer Graphics (SIGGRAPH), v o l . 1 1 , no.4, March 1978, 67-77. [Bu77] Burton, W., "Representation of many-sided polygons and polygonal l i n e s f o r r a p i d p r o c e s s i n g , " Communications ACM, v o l . 2 0 , no.3, March 1977, 166-171. [Ce79l Cederberg, R.L.T., "A new nethod f o r v e c t o r g e n e r a t i o n , " i n Rosenfeld, A., Freeman, H., Huang, T.S., Van Dam, A., Eds., CGIP, New York and London, Academic P r e s s , v o l . 9 , 1979, 183-195-[Ch75] Chan, B.B., Mathematical Aspects of a G r a p h i c a l Programming Lan-guage and i t s Implementation, Master's t h e s i s . The U n i v e r s i t y of B r i t i s h Columbia, 1976, Vancouver, B.C. [Ch74] Chang, S.K., "A t r i a n g u l a r scanning technique f o r l o c a t i n g bound-ary curves," i n Rosenfeld, A., Freeman, H., Huang, T.S., Van Dam, A., Eds., CGIP, New York and London, Academic P r e s s , v o l . 3 , 197^, 313-317. [Ch77l Chang, S.K. et a l . , "A r e l a t i o n a l database system f o r p i c t u r e s , " P i c t u r e Data D e s c r i p t i o n s and Management Workshop, 1977, 142-149-[Ch78] Chasen, S.H., Geometric P r i n c i p l e s and Procedures f o r Computer Graphic A p p l i c a t i o n s . New York, P r e n t i c e - H a l l , 1978. [C170] Claude, R.B. , Claude, L.F., "Scence a n a l y s i s u s i n g r e g i o n s , " A r t -i f i c i a l I n t e l l i g e n c e , New York and London, Academic P r e s s , 1976, 216-232. [ C 0 6 7 ] Cook, B.G., "A computer r e p r e s e n t a t i o n of plane regions boundar-i e s , " A u s t r a l i a n Computer J o u r n a l , v o l . 1 , n o . l , 1967, 44-50. [Du76] Dudani, S.A., "Region e x t r a c t i o n u s i n g boundary f o l l o w i n g , " i n Chen, C.H., Ed., P a t t e r n R e c o g n i t i o n and A r t i f i c i a l I n t e l l i g e n c e , New York and London, Academic P r e s s , 1976, 216-232. [Dw67] Dwyer, W.C., "Windows, s h i e l d s , and shading," Proc. 6 t h UAIDE meeting, Washington, D.C, 1967. 79 [Ea70] Eastman, CM., "Representations f o r space p l a n n i n g , " Communicat-ions ACM, v o l . 1 3 , no.U, A p r i l 1970, 21+2-250, ~ [Fe78] F e l l e r , A., Koto, R,, "A speed-oriented, f u l l y - a u t o m a t i c l a y o u t program f o r random l o g i c VLSI d e v i c e s , " AFIPS Conference Proceed-i n g s , v o l . i t 7 , 1978, 303-312. [ F r 6 l a ] Freeman, H,, "On the encoding of a r b i t r a r y geometric c o n f i g u r a t -i o n s , " IRE Transactions on E l e c t r o n i c Computers, v o l . E C - 1 0 , no.2, June 1961, 260-268. [ F r 6 l b ] Freeman, H., "Techniques f o r the d i g i t a l computer a n a l y s i s of chain-encoded a r b i t r a r y plane curves," Proceedings of the N a t i o n -a l E l e c t r o n i c s Conference, v o l . 1 7 , 1 9 6 l , ^21-^32. [Fr62] Freeman, H., "On the d i g i t a l computer c l a s s f i c a t i o n of geometric l i n e p a t t e r n s , " Proc. N a t i o n a l E l e c t r o n i c Computers, I 9 6 2 , 312-321+. [Fr67] Freeman, H., L o u t r e l , P.P., "An a l g o r i t h m f o r the s o l u t i o n of the two-dimensional ' h i d d e n - l i n e ' problem," IEEE T r a n s a c t i o n on E l e c -t r o n i c Computers, v o l . E C - l 6 , no.6, Dec. 1 9 6 7 , 7 3 i t - 7 9 0 . [Fr70] Freeman, H., Haims, M. J . , "A m u l t i s t a g e s o l u t i o n of the templa-t e - l a y o u t problem," IEEE Transactions on Systems Science and C y b e r n e t i c s , vol.SSC - 6 , no.2, A p r i l 1 9 7 0 , 11+5-151. [Fr7l(] Freeman, H., "Computer p r o c e s s i n g of l i n e - d r a w i n g images," ACM Computing Surveys, v o l . 6 , n o . l , March 197^, 57-97-[Fr75] Freeman, H., S h a p i r a , R., "Determining the minimum-area encasing r e c t a n g l e f o r an a r b i t r a r y c l o s e d curve," Communications ACM, v o l . 1 8 , no.7, J u l y 1 9 7 5 , 1+09-1+13. [Gi78] G - i l o i , W.K. , I n t e r a c t i v e Computer Graphics, P r e n t i c e - H a l l , I n c . , Englewood C l i f f s , New J e r s e y , 1978. [Ga76] H a l l , J.K., "Algorithms and programs f o r the r a p i d computation of area and centre of mass," Computer & Geosciences, v o l . l , 1 9 7 6 , 203-205. [Ge72] H e r t z , J . C , "Recursive computational procedure f o r two dimen-s i o n a l stock c u t t i n g , " IBM J o u r n a l of Research Development, v o l . 1 6 , Sept. 1 9 7 2 , 1+62-1+69. [H076] Horn, B.K.P., " C i r c l e generators f o r d i s p l a y d e v i c e s , " CGIP 5 , 1 9 7 6 , 2 8 0 - 2 8 8 . [Hu67j Hurwitz, A., C i t r o n , J,P., Yeaton, J.B., "GRAF; Graphic a d d i t i o n s t o F o r t r a n , " AFIPS Conference Proceedings SJCC, v o l . 3 0 , 1 9 6 7 , 553-557. 8o [ I f 7 2 ] IFIP Working Conference on Graphic Languages, i n Nake, F,, Rosen-f e l d , A., Eds., Graphic Languages, Amsterdam; North-Holland P u b l . Co. , 1972. [Is73] Ison, N.T., "An a l g o r i t h m .to shade; a..-,plot ^ "-Computer Graphics CSIGGRAPH), v o l . 7 , 10-23. [Ja6o] James, G. et a l . , Mathematical D i c t i o n a r y , D. Van Nostand company, rev. i 9 6 0 . [Ja75a] J a r v i s , J.F., "Two simple windowing a l g o r i t h m s , " Software P r a c t -i c e and Experience, v o l . 5 , 1975, 115-121. [Ja75b] J a r v i s , J.F., "An area organized data s t r u c t u r e f o r i n t e r a c t i v e g r a p h i c s , " Computer Graphics (SIGGRAPH), v o l . 9 , 1975, 18U - 1 9 0 . [Ki50] K i n d l e , J.H., A n a l y t i c Geometry, Schaum's O u t l i n e S e r i e s , McGraw-H i l l , 1950. [Ki6H] K i r s c h , A.R., "Computer i n t e r p r e t a t i o n of E n g l i s h t e x t and p i c t -ure p a t t e r n s , " IEEE Transactions on E l e c t r o n i c Computers, vol.EC-13, 196kt 3 6 3 - 3 7 6 . [Kr72] K r e y s z i g , E., Advanced Engineering Mathematics, 3 r d e d i t i o n , W iley, 1972. [Ku68] K u l s r u d , H.E., "A general purpose graphic language," Communicat-ions ACM, v o l . 1 1 , no.4, A p r i l 1968, 247-254. [Le6l] Lee, C.Y., "An a l g o r i t h m f o r path connections and i t s a p p l i c a t -i o n s , " IRE Transactions on E l e c t r o n i c Computers, v o l . EC-9, no.3, Sept. 1961, 345-365. [ L i 7 8 ] Lieberman, H., "How t o c o l o r i n a c o l o r i n g book," Computer Graph-i c s (SIGGRAPH), v o l . 1 2 , Aug. 7 8 , 111-116. [ L 0 6 5 ] Loomis, R. G., "Boundary networks," Communications ACM, v o l . 8 , n o . l , Jan. I 9 6 5 , 44-48. [L078] Loosemore, K.J., "IC design-misery or magic," AFIPS Conference Proceedings, v o l . 4 7 , 1978, 285-289. [Ma78] M a i r , S., The UBC-PLOT subroutines and programs, Vancouver, B.C., The U n i v e r s i t y of B r i t i s h Columbia 1971, rev. Sept., 1978. [Ma68] Maurer, W.S., "An improved hash code f o r s c a t t e r storage," Com-munications ACM, v o l . 1 1 , n o . l , Jan. 1968, 35-44. [Ma72.] Maxwell, P.C., "The p e r c e p t i o n and d e s c r i p t i o n of l i n e drawings by computer," i n Rosenfeld, A., Freeman, H., Huang, T.S., Van Dam, A., Eds., CGIP, New York and London, Academic P r e s s , v o l . 1 , 1972, 31 - 4 6 . 81 [Mc70] McKeeman, W.M., Horning, J . J . , Wortman, D.B., A Compiler Generat-o r , P r e n t i c e - H a l l , 1970, [Me73] M e r r i l l , R.D, , "Representation of contours and regions f o r e f f i c -i e n t computer search," Communications ACM, v o l . l 6 , no.2, Feb. 1973, 69-82. [Mi68] M i l l e r , W.F., Shaw, A.C., " L i n g u i s t i c methods i n p i c t u r e process-i n g — A survey," AFIPS Proc. FJCC, 1968, 279-290. [Mo68a] Morse, S.P., "Computer storage of contour-map data," Proc, 23 r d ACM Nat, Conf., 1 9 6 8 , 1*5-51. [Mo68b] Morse, S.P., "A mathematical model f o r the a n a l y s i s o f contour-l i n e data," JACM, v o l . 1 5 , no.2, A p r i l 1968, 205-220. [ M 0 6 9 J Morse, S.P., "Concepts of use i n contour map," Communications ACM, vol . 1 2 , no.3, March 1969, 11+7-152. [Na7l] Nake, F., "A proposed language f o r the d e f i n i t i o n of twodimension-a l s i g n s , " i n Grusser, 0.1., K l i n k e , R., Eds., P a t t e r n Recognit-i o n i n B i o l o g i c a l and T e c h n i c a l Systems, B e r l i n , Springer V e r l a g , 1971, 396-1+02. [Na78] Nan, N., Feuer, M., "A method f o r the automatic w i r i n g of LSI c h i p s , " AFIPS Conference Proceedings, v o l . 1+7, 1978, 297-302. [Ne77] Negroponte, N., "Raster scan approaches t o computer g r a p h i c s , " Computers and Graphics, v o l . 2 , 1977, 179-193. [Ne68] Newman, W.M., "A system f o r i n t e r a c t i v e g r a p h i c a l prograjnming," AFIPS Proc. SJCC, 1968, 1+7-5^. [Ne7l] Newman, W.M. , " D i s p l a y procedures," Communications ACM, v o l . l l + , no.10, Oct. 1971, 651-660. [Ne73] Newman, W.M., S p r o u l l , R.F., P r i n c i p l e s of I n t e r a c t i v e Computer Graphics, McGraw-Hill, 1973. [Ne7h] Newman, W.M., S p r o u l l , R.F., "An approach t o graphics system design," IEEE Proceedings, 62, 1+, A p r i l I97I+, UTI-U83. [Ne75a] Newman, W.M., S p r o u l l , R.F. , "The design of gr a y - s c a l e graphics software," Proceedings of the Conference on Computer Graphics, P a t t e r n Recognition & Data S t r u c t u r e , May ll+ - l 6 , 1975, 18-20. [Ne75b] Newman, W.M., "in s t a n c e r e c t a n g l e s and p i c t u r e s t r u c t u r e , " Pro-ceedings of the Conference on Computer Graphics, P a t t e r n Recog-n i t i o n & Data S t r u c t u r e , May ll+ - l 6 , 1975, 297-301. [Ne78] Newman, W,M., S p r o u l l , R.F,, P r i n c i p l e s of I n t e r a c t i v e Computer Graphics, 2:.nd e d i t i o n , McGraw-Hill, 1978. 82 [Oc72] O'Callaghan, J.F., "Use of a p i c t u r e language t o generate d e s c r i -p t i o n s of l i n e drawings i n an i n t e r a c t i v e system," i n Nake,F., Rosenfeld, A., Eds., Graphic Languages, IFIP Working Conference on Graphic Languages, Amsterdam, North-Holland P u b l . Co., 1972, 123-141. [0c74] O'Callaghan, J.F., "Computing the p e r c e p t u a l boundaries of dot pa t t e r n s " i n Rosenfeld, A., Freeman, H., Huang, R.S.m Van Dam, a., Eds., CGIP, New York and London, Academic P r e s s , v o l . 3 , 1974, 141-162. [Oc75] O'Callaghan, J.F., "An a l t e r n a t i v e d e f i n i t i o n f o r 'neighbour o f a p o i n t ' , " IEEE Transactions on Computers, 13, Nov. 1975, 1121-1125. [Oc76] O'Callaghan, J.F., "A metnod f o r r e p r e s e n t i n g p o i n t data by r e g i -ons," The A u s t r a l i a n Computer J o u r n a l , v o l . 8 , n o . l , March 1976, 7-12. [Pa77l P a t e l , K., "Computer-aided decomposition of geometric contours i n t o s t a n d a r d a r i z e d areas," CAD, v o l . 9 , no.3, J u l y 1977, 199-203. [Pa78a] P a v l i d i s , T., " F i l l i n g algorithms f o r r a s t e r g r a p h i c s , " T e c h n i c a l Report No. 238, Computer Science Laboratory, P r i n c e t o n U n i v e r s i t y , Jan. 1978. [Pa78b] P a v l i d i s , T., " F i l l i n g algorithms f o r r a s t e r g r a p h i c s , " Computer Graphics (SIGGRAPH), 12, Aug. 1978, l 6 l - l 6 5 . [Pe78] Persson, H., "NC machining of a r b i t r a r i l y shaped pockets," CAD, vol . 1 0 , no.3, May 1978, 169-174. [Pf67] P f a l t z , J.L., Rosenfeld, A., "Computer r e p r e s e n t a t i o n of planar regions by t h e i r s k e l e t o n s , " Communications ACM, v o l . 1 0 , no.2, Feb. 1967. [Ph72] P h i l l i p s , R.L., Subroutine Shade, Department of Aerospace Engin-e e r i n g , The U n i v e r s i t y of Michigan, Ann Arbor, Mich., 1972. [Ph76] P h i l l i p s , R.L., "Software t o o l s f o r computer g r a p h i c s , " i n Ortego, J.M., Eds., Computer Science and S c i e n t i f i c Computing, New York, Academic P r e s s , 1976, 205-227-[Ra76] Ram, G., " A n a l y s i s of images s p e c i f i e d by g r a p h l i k e d e s c r i p t i o n s , " i n Rosenfeld, A., Freeman, H., Huang, T.S., Van Dam, A., Eds., v o l . 5 , 1976, 137-148. [Ri75J R i e b e r , J.E., Shaw, A.C., " I n t e r a c t i v e p i c t u r e generation and manipulation through formal d e s c r i p t i o n s , " Computer and Graphics, v o l . 1 , no.2, May 1977, 95-107. 83 [Ro76a] Roger, D.F., Adams, J.A,, Mathematical Elements f o r Computer Graphics, New York, McGraw-Hill, 1976, [ R 0 6 6 J Rosenfeld, A., P f a l t z , J.L,, " S e q u e n t i a l operations i n d i g i t a l p i c t u r e , " JACM, v o l , 1 3 , no.h, Oct, 1966, hll-kgh. [R069] Rosenfeld, A., P i c t u r e P r o c e s s i n g by Computer, Academic P r e s s , New York, 1969. [Ro70] Rosenfeld, A., " C o n n e c t i v i t y i n d i g i t a l p i c t u r e s , " v o l . 1 7 , Jan. 1970, lhO - 1 7 0 . [Ro73] Rosenfeld, A., "A r e g i o n c o l o r i n g technique f o r scene a n a l y s i s , " Communications ACM 16, 1973, 237-2^6. [Ro76b] Rosenfeld, A., " P i c t u r e p r o c e s s i n g : 1975 - Survey," i n Rosenfeld, A., Freeman, H., Huang, T.S., Van Dam, A., Eds., CGIP, New York and London, Academic P r e s s , v o l . 5 , 1976, 215-237-[Sa78] Salomon, K.B., "A F o r t r a n IV program which determine t h a t r e g i o n of a polygon w i t h i n a polygonal boundary," Computer & Geosciences, v o l . h , 1978, 53-63. [Sc76a] Schrack, G.F., "Design, implementation and experiences w i t h a h i g h - l e v e l graphics language f o r i n t e r a c t i v e computer-aided design purposes," Computer Graphics (SIGGRAPH), v o l . 1 0 , n o . l , 1976, 10-17. [Sc76b] Schrack., G.F. , "On the semantics of the assignment of h i g h - l e v e l graphics languages," Computer Graphics (SIGGRAPH),vol.10, no.2, 1976, 173-178. [Sc78] Schrack, G.F., LIG User's Manual. The U n i v e r s i t y of B r i t i s h Columbia, Department of E l e c t r i c a l E n g i n e e r i n g , 1977, rev. J u l y 1978. [Sc68] Shaw, A.C., M i l l e r , W.F., "A p i c t u r e c a l c u l u s , " i n S e c r e s t , D. , N i e v e r g e l t , J . , Eds., Emerging Concepts i n Computer Graphics, New York, Amsterdam, 1968, 101-121. [Sh69] Shaw, A.C., "A formal p i c t u r e d e s c r i p t i o n scheme as a b a s i s f o r p i c t u r e p r o c e s s i n g systems," Information and C o n t r o l , v o l . l h , 1969, 9-52. [Sm7l] Smith, D.N., "GPL/I - A P L / l extension f o r computer g r a p h i c s , " AFIPS Conference Proceedings SJCC, v o l . 3 8 , 1971, 511-528. [Sp67J Spanier, E.H.,Algebraic Topology, McGraw-Hill, New York, 1967-[Sp68a] S p i e g e l , M.R., Mathematical Handbook of Formulas and Tab l e s , Schaum's O u t l i n e S e r i e s , McGraw-Hill Book Company, 1978. [Sp68b] S p r o u l l , F.F., Sutherland, I.E., "A c l i p p i n g d i v i d e r , " Proc. 1968, AFIPS FJCC, v o l . 3 3 , AFIPS P r e s s , 765-775-ISt71] Stack, T.R., Walder, S.R., "Aids-advanced i n t e r a c t i v e d i s p l a y system," AFIPS Conference Proceedings SJCC, v o l . 3 8 , 1971, 113-121. I S t 7 0 j Stanton, R.B., "Plane r e g i o n s : A study i n g r a p h i c a l communicat-i o n , " i n Kaneff, S., Eds., P i c t u r e Language Machines, Academic P r e s s , 1970, 151-187. [St72] Stanton, R.B., "The i n t e r p r e t a t i o n of graphics and graphic l a n g -uages," i n Wake, F., Rosenfeld, A., Eds., Graphic Languages, IFIP Working Conference on Graphic Language, Amsterdam, North-H o l l a n d P u b l . Co., 1972, lUU-159. [Su63] Sutherland, I.E., "SKETCHPAD - A man-machine g r a p h i c a l communicat-io n system," AFIPS Proc. SJCC, 1963. [Su73] Sutherland, I.E., S p r o u l l , R.F., and Schumacker, R.A., " S o r t i n g and the hidden-surface problem," N a t i o n a l Computer Conference, 1973, 685-693. [Su7ha] Sutherland, I.E., Hodgman, F.W., "Reentrant polygon c l i p p i n g , " Communications ACM, v o l . 1 7 , n o . l , Jan. 197^, 32-h2. [Su7hb] Sutherland, I.E., S p r o u l l , R.F., and Schumacker, R.A., "A c h a r a c t -e r i z a t i o n of ten hidden-surface a l g o r i t h m s , " ACM Computing Sur-veys, v o l . 6 , n o . l , March 197^, 1-55-[Ta77l Tamura, H., M o r i , S., "A data management system f o r manipulating l a r g e images," P i c t u r e Data D e s c r i p t i o n and Management Workshop, 1977, h5-5h. [Ve79] V e l e r d a , R., P l o t the s h o r e l i n e s ' Programmer's Manual, Department of C i v i l E n g i n e e r i n g , UBC, March 1979. [ W i 7 l ] W i l l i a m s , R., "A survey of data s t r u c t u r e s f o r computer graphics systems," ACM Computer Surveys, v o l . 3 , March 1971, 1 -21 . [Wi77] W i l l s , P., "A r e a l time hidden surface technique," The Computer J o u r n a l , v o l . 2 0 , no.h, 1977, 335-339-[Wy77l W y v i l l , B.L.M., "PICTURES-68 MK1," Software - P r a c t i c e and Exper-i e n c e , v o l . 7 , 1977, 251-261. [Za69] Zahn, C.T., "A formal d e s c r i p t i o n f o r two-dimensional p a t t e r n s , " Proc. I n t . J o i n t Conference on A r t i f i c i a l I n t e l l i g e n c e , May I 9 6 9 , 621-628. 85 APPENDIX A AREA OF A SIMPLY CLOSED POLYGON G i v e n an a r b i t r a r y s i m p l y c o n n e c t e d n - s i d e d p o l y g o n d e f i n e d b y v e r t i c e s ; U1» y ^ , (x2> y g ) , (x , y f i ) , (x.^  y 1 ) , t h e a r e a o f t h e p o l y g o n ( F i g u r e A . l ) i s g i v e n by: 1 n A = — )• (x v - x y. ) E q u a t i o n A . l 2 - , l k k l c l = 1 v h e r e k = (x,,y,) F i g u r e A . l A s i m p l y c l o s e d p o l y g o n Denote (x, y ) t o be t h e c o o r d i n a t e s o f t h e c e n t r e o f g r a v i t y o f t h e n - s i d e d p o l y g o n . The x, y can be p r o v e d ( H a l l [Ha76]) t o be g i v e n by: _ i n , x = —— _ I _^(x^  + xk) * Cx^ - x ky A) E q u a t i o n A. 2 n y = I {y± + y k) * (x±yk - x^y±) E q u a t i o n A. 3 6A i = 1 where A i s g i v e n by E q u a t i o n A . l .86 APPENDIX B LIGE HOMOGENEOUS-TRANSFORMATION MATRICES The homogeneous t r a n s f o r m a t i o n m a t r i c e s used i n LIGE are i d e n t i -c a l t o those i n LIG, Using these m a t r i c e s , a s e r i e s of t r a n s f o r m a t i o n s : r o t a t i o n , t r a n s l a t i o n , and s c a l i n g i n any o r d e r , can e a s i l y be c a r r i e d out, A systematic i n v e s t i g a t i o n of the advantages of these matrices has been c a r r i e d out i n Chan [Ch753. A p o i n t P I i n m a t r i x form i s transformed t o a corresponding p o i n t P2 ( a l s o i n m a t r i x form) u s i n g the A and B m a t r i c e s , i . e . P2 = A.PI + B (Equation B . l ) , where . denotes m a t r i x m u l t i p l i c a t i o n , A XSCALE * COS0 D * SING - C * SING YSCALE * C0S9 B = (YSCALE w i t h C = I XSCALE r XSCALE w i t h D = I YSCALE XLOC + (D * SIN6 - XSCALE * C0S6) * .5 YLOC - (C * SIN6 + YSCALE * COS6) * .5 i f r o t a t i o n i s not f i r s t i n the t r a n s f o r m a t i o n , otherwise. i f r o t a t i o n i s not f i r s t i n the t r a n s f o r m a t i o n , otherwise. XLOC = the h o r i z o n t a l a x i s x l o c a t i o n YLOC = the v e r t i c a l a x i s y d i r e c t i o n XSCALE = the h o r i z o n t a l a x i s s c a l e f a c t o r YSCALE = the v e r t i c a l a x i s s c a l e f a c t o r 9 = the r o t a t i o n angle i n r a d i a n s . 87 APPENDIX C THE CALCULATION OF THE AREA OF A GRAPHICAL OBJECT (.which i s represented hy the r e g i o n a l e x t e r n a l r e p r e s e n t a t i o n model) K / ^ A ' / G ' E* \ / F 1 (a) (b) F i g u r e C . l A t r i a n g l e and i t s i n s t a n c e I t i s a matter of algebra t o prove t h a t the r a t i o of the areas of the t r i a n g l e ABC and i t s a s s o c i a t e d d e f i n i t i o n frame DEFG i s equal t o t h a t of the modifi e d t r i a n g l e A'B'C and i t s a s s o c i a t e d d e f i n i t i o n frame D'E'F'G' (Figure C . l ( a - b ) ) . This r a t i o depends on the topology of the t r i a n g l e ABC and i s , f o r convenience, c a l l e d the k-value. B e s i d e s , the area of the modifi e d d e f i n i t i o n frame i s always a constant and i s equal t o (S *" S ). S ,,. S are the s c a l e f a c t o r s of the a b s c i s s a and ord-x y x' y i n a t e w i t h respect t o a reference p o i n t . This area i s independent of the order of t r a n s f o r m a t i o n ( r o t a t i o n , t r a n s l a t i o n and s c a l i n g ) . The k-value can be expressed as: 88 Area.of a t r i a n g l e k =• — — , Area of the d e f i n i t i o n frame a s s o c i a t e d w i t h the t r i a n g l e Area of the m o d i f i e d t r i a n g l e Area of the d e f i n i t i o n frame a s s o c i a t e d v i t h the m o d i f i e d t r i a n g l e Area of the modified t r i a n g l e Equation C . l S * S x y The coordinates of a l l p o i n t s i n F i g u r e C . l b , given those i n Figure C . l a , are c a l c u l a t e d u s i n g Equation B . l . The areas of t r i a n g l e s and t h e i r a s s o c i a t e d d e f i n i t i o n frames are computed u s i n g Equation A . l . Each g r a p h i c a l p r i m i t i v e i n LIGE such as the one i n F i g u r e C.2a i s approximated hy a simply c l o s e d n-sided polygon (Figure C.2b). Each n-sided polygon can he t r i a n g u l a t e d i n t o a number of t r i a n g l e s (Figure C.2c). Hence the r e s u l t of the t r a n s f o r m a t i o n s of these t r i a n g l e s d e s c r i b -i n g the polygon i s equivalent t o t h a t of a t r a n s f o r m a t i o n of the polygon (Figure C.2d). Denote A^, A ' t o be the areas of a t r i a n g l e i and t h a t of i t s instance r e s p e c t i v e l y (Figure C.2(c-d)). Let k^ be the k-value of the t r i a n g l e . Using equation C . l : A A • ± _ = _ L _ = k 1 s » s x x y A ' n S * S x y = k 89 (a) a g r a p h i c a l p r i m i t i v e (t>) an n-sided polyg< (c) a t r i a n g u l a t e d polygon (d) an instance of the t r i -angulated polygon Figure C.2 A t r i a n g u l a t e d polygon and i t s i n s t a n c e Hence, A, + A 0 + ,., + A A ' + A ' + .,,+ A ' 1 2 n 1 2 n -i j . i _i_ . r i s * s . n x y or Area of the n-sided polygon _ Area of i t s i n s t a n c e _ 1 S * S x y where k i s a constant which i s r e l a t e d t o the topology of the polygon. Area of a manipulated polygon = S x * S * k Equation C.2 Example Given a g r a p h i c a l p r i m i t i v e DISK and an i n s t a n c e from manipul-a t i o n w i t h s c a l e f a c t o r s S , S and angle o f r o t a t i o n ALFA r a d i a n s . Then x' y the area of the instance of DISK (using Equation C.2) i s equal t o S x * S y * k D I S K ( = S x * S y * ^ 5 3 9 ) . In order t o demonstrate the u s e f u l n e s s of Equation C.2, an example i s given. Example Consider the g r a p h i c a l assignment statement (Figure 6.1): * GIRL :- DISK <m.> + LINE <m> + LINE <m > 6 1 2 * + LINE <m3> + RTRIANGLE <m > + LINE <m^ > * + LINE <m^ >; where <m^ >, <ra.^>, <m > denote m o d i f i c a t i o n s . The area of the g r a p h i c a l object GIRL = Area of [DISK <m^ >] + Area of [RTRIANGLE <m >] + Sum of areas o f a l l i nstances of LINE + v * (S * S <nv> ^TRIANGLE x y - v * f.q * s ) DISK ^ x V <m^ > 5 + J" k T T T O T, * (S * S ) ^ _ 2. x y s Refer t o Table C l <m. > i 91 N o t a t i o n ; (S • S ) x j denotes the S and S a s s o c i a t e d w i t h the <m > x y modifications. <m.>.• Hence, the c a l c u l a t i o n of the area of a g r a p h i c a l object i s r e -duced t o the summation of products. Each product i s given by k * * S , where k i s a constant a s s o c i a t e d w i t h the g r a p h i c a l p r i m i t i v e used, S , S are the s c a l e f a c t o r s a s s o c i a t e d w i t h the m o d i f i e d g r a p h i c a l p r i m i t i v e . y G r a p h i c a l P r i m i t i v e k-value BLANK 0. . LINE 0. TRIANGLE 0. SQUARE 0. CIRCLE 0. SCIRCLE 0. TILE 1. DISK 0.78539 RTRIANGLE . 0.5 QRING 0.14726 LSECT0R 0.19634 Table C . l G r a p h i c a l p r i m i t i v e s and i t s a s s o c i a t e d k-values APPENDIX D THE CONSTRUCTION OF THE LIGE PREPROCESSOR (Figure D.l) Some feat u r e s of LIGE have been implemented u s i n g the compiler w r i t i n g system XPL. With the a i d of the XPL, the c o n s t r u c t i o n of the LIGE preprocessor i s s i m p l i f i e d . More important, use of XPL i n c r e a s e s f l e x i b i -l i t y d u r i n g the experimental design of a language because the syntax and the a s s o c i a t e d semantics can be m o d i f i e d independently of one another. Using the XPL system the language extension LIGE i s being t r e a t e d as an independent and separate language. The Backus-Naur-Form (BNF) n o t a t i o n i s used to define the language syntax f o r LIGE. The syntax i s then checked f o r correctness by a component of the XPL system, the ANALYZER. Once the syntax i s e r r o r f r e e , a t a b l e which i s e s s e n t i a l l y a set of d e c l a r a t i o n s , i s produced. The t a b l e i s i n a format t h a t i s ready t o be i n s e r t e d i n t o a compiler framework, the m o d i f i e d SKELETON. There are two s l o t s i n the m o d i f i e d SKELETON; one f o r the t a b l e mentioned above and the others f o r the LIGE syntax-semantics. The semantics are w r i t t e n i n XPL and the procedure i s c a l l e d SYNTHESIZE. Whenever a grammar r u l e i s a p p l i e d by the parser f o r reducing the input s t r i n g , the procedure SYNTHESIZE i s c a l l e d upon by the SKELETON. The SKELETON w i t h these compon-ents represents the LIGE preprocessor i n source code form. The LIGE pre-processor i s compiled w i t h the XPL compiler. For the preprocessor development at UBC, the EXPL (Extended XPL) compiler [Ba75]» a s l i g h t l y m o d i f i e d v e r s i o n of the XPL c o m p i l e r , i s used. I t i s s u p e r i o r t o the XPL compiler i n t h a t i t permits separate c o m p i l a t i o n of procedure modules, thus a l l o w i n g more e f f i c i e n t debugging. Figure D.l The construction of the LIGE preprocessor APPENDIX E AUTHORS SORTED BY SUBJECTS Ap p l i c a t i o n [AdT6a] [Ea70j [Fr75] [Lo78] [Ad76b] !Fe78] [Ge72] [Na78] [A175] [Fr70] [Le6l] [Ph76] Contour Representation [Bu77] [Fr62] [Mo68a] [Pn7l] [Fr6la] [Frlh] [Mo68b] [Za69] [Fr6lb] [ L 0 6 5 ] [M069] Hatching and/or F i l l i n g [Br78] [Pa78a] [Ph72] [Ve79] [Is73] [Pa78b] [Ph76] [ M 7 8 ] [Pe78] [Pf67] Hidden Surface and/or Line [Fr67] [Wi77] [Su73] [Su7Hb] Memory Consideration [Ch77] [Ja75b] [Ta77] Regional Graphics Language [ B r 7 l J [Ne75a] ISc76b] [Ch75] [Ne78] [Na7l] [Sc76a] 95 Region Representation [C170J [Me?3] [ P f 6 7 L [St70] I C 0 6 7 ] [Oc76] [Ro73] [Du76J [Pa77] [Sa78] Text [Ch78] [Ro76a] [Gi78] [Ke78] Windowing Technique [ B e 6 9 ] [Ph76] [Dw67] [Ja75a] 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0100277/manifest

Comment

Related Items