Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

An algorithm for polyhedron modelling and its implementation Yeung, Kwai-Biu Ricky 1984

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

Item Metadata

Download

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

Full Text

AN ALGORITHM FOR POLYHEDRON MODELLING AND I T S I M P L E M E N T A T I O N by K W A I - B I U R I C K Y YEUNG B . S c , T h e U n i v e r s i t y o f T e x a s a t A r l i n g t o n , 1979 M . S c , S t a n f o r d U n i v e r s i t y , 1980 A T H E S I S SUBMITTED IN P A R T I A L F U L F I L M E N T OF THE REQUIRMENTS FOR THE DEGREE OF MASTER OF S C I E N C E i n THE F A C U L T Y OF GRADUATE S T U D I E S ( D e p a r t m e n t o f C o m p u t e r S c i e n c e ) We a c c e p t t h i s t h e s i s a s c o n f o r m i n g t o t h e r e q u i r e d S t a n d a r d THE U N I V E R S I T Y OF B R I T I S H COLUMBIA A p r i l , 1984 © K w a i - b i u R i c k y Y e u n g , 1984 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements fo r an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y a v a i l a b l e for reference'and study. I further agree that permission for extensive copying of t h i s t h e s i s f o r s c h o l a r l y purposes may be granted by the head of my department or by h i s or her representatives. I t i s understood that copying or p u b l i c a t i o n of t h i s t h e s i s for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of Computer Science The University of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date A p r i l 25, 1984 A B S T R A C T T h i s t h e s i s d e s c r i b e s an a l g o r i t h m f o r c a l c u l a t i n g t h e t h e o r e t i c s e t o p e r a t i o n s u n i o n , i n t e r s e c t i o n , a n d d i f f e r e n c e o f two p o l y h e d r a . T h e p o l y h e d r a a r e i n t h e E u l e r i a n s u r f a c e d e s c r i p t i o n f o r m a t , s p e c i f i e d by t h e i r v e r t i c e s , e d g e s , a n d f a c e s . T h e r e p r e s e n t a t i o n o f p o l y h e d r a i s b a s e d on t h e u n a m b i g u o u s B o u n d a r y R e p r e s e n t a t i o n s c h e m e . T h e d o m a i n o f t h i s a l g o r i t h m i n c l u d e s a l l f l a t - s u r f a c e d p o l y h e d r a ; h o w e v e r , n e s t e d h o l e s a n d c u r v e d s u r f a c e s a r e n o t p e r m i t t e d . T h e t h e s i s i s d i v i d e d i n t o t h r e e p a r t s . T h e f i r s t p a r t p r e s e n t s some m a t h e m a t i c a l d e f i n i t i o n s a n d t h e r e p r e s e n t a t i o n scheme f o r p o l y g o n s a n d p o l y h e d r a . S i n c e t h e r e a r e many s i m i l a r i t i e s b e t w e e n 2-D p o l y g o n m o d e l l i n g a n d 3-D p o l y h e d r o n m o d e l l i n g , t h e 2-D p o l y g o n m o d e l l i n g a l g o r i t h m i s p r e s e n t e d n e x t , f o l l o w e d by t h e 3-D p o l y h e d r o n m o d e l l i n g a l g o r i t h m . TABLE OF CONTENTS CHAPTER 1. Introduction ' 1 CHAPTER 2. D e f i n i t i o n s and Representations 5 2. 1 Polygon 5 2.1.1 D e f i n i t i o n 5 2.1.2 Representation 5 2 . 2 Polyhedron 6 2.2.1 D e f i n i t i o n . .- 6 2.2.2 Representation 6 2.3 Regularity • 6 2.4 Set Membership C l a s s i f i c a t i o n 8 CHAPTER 3. 2-D Polygon Modelling Algorithm 13 3.1 Domain of Algorithm 13 3.2 Data Structure 13 3 . 3 2-D Algorithm ' 15 3.4 Discussion and Result 18 CHAPTER 4. 3-D Polyhedron Modelling Algorithm 21 4.1 Domain of Algorithm 21 4.2 Data Structure 21 4.3 3-D Algorithm 25 4.4 Discussion and Result '. 38 CHAPTER 5. Future Work and Conclusion 41 REFERENCES 4 2 APPENDIX A: 2-D Polygon Modelling Algorithm 44 APPENDIX B: Decision Algorithm "FindOnType" 46 APPENDIX C: 2-D Example 47 APPENDIX D: 3-D Example 50 i v L I S T OF FIGURES AND TABLE F i g u r e 1: W i r e f r a m e a m b i g u i t y 1 F i g u r e 2: A p l a n a r , s i m p l e and s t r a i g h t p o l y g o n 5 F i g u r e 3: N o n - r e g u l a r o b j e c t 7 F i g u r e 4: C o n v e n t i o n a l v e r s u s r e g u l a r i z e d i n t e r s e c t i o n o f two r e g u l a r s e t s 8 F i g u r e 5: M e m b e r s h i p c l a s s i f i c a t i o n f u n c t i o n 9 F i g u r e 6: M e m b e r s h i p c l a s s i f i c a t i o n e x a m p l e : L i n e / p o l y g o n c l i p p i n g 9 F i g u r e 7: M e m b e r s h i p c l a s s i f i c a t i o n e xample: P o l y g o n i n t e r s e c t i o n 10 F i g u r e 8: On/on a m b i g u i t y 10 F i g u r e 9: P o l y g o n s w h i c h t o u c h a t one p o i n t 13 F i g u r e 10: Segment and i n t e r s e c t i o n p o i n t l i s t s i l l u s t r a t i o n • 16 F i g u r e 1 1 : 2-D example 20 F i g u r e 12: C u t - l i n e s and c u t - p o i n t s on a f a c e 28 F i g u r e 13: Example of an o p e r a t i o n t h a t g e n e r a t e s an o b j e c t w i t h a h o l e i n i t 39 F i g u r e 14: 3-D example 40 T a b l e I : E d g e / F a c e segments t o be i n c l u d e d i n t h e d e s i r e d r e g u l a r i z e d s e t o p e r a t i o n s 11 ACKNOWLEDGEMENTS v I would l i k e t o thank my wi s u p p o r t and a f f e c t i o n a t e c a r e wh g r a t e f u l t o my s u p e r v i s o r , Dr and c o n s i s t e n t g u i d a n c e . f e f o r h e r c o n t i n u e d s p i r i t u a l i l e I s t u d i e d a t UBC. I am a l s o . G. F. S c h r a c k , f o r h i s a d v i c e 1 CHAPTER 1 INTRODUCTION T h r e e - d i m e n s i o n a l s o l i d g e o m e t r y - p l a y s an i m p o r t a n t r o l e i n t h e d e s i g n a n d p r o d u c t i o n o f m e c h a n i c a l p a r t s a n d o t h e r d i s c r e t e o b j e c t s . T h e a p p l i c a t i o n o f c o m p u t e r s t o s o l v e c o m p u t a t i o n a l g e o m e t r y p r o b l e m s i s w i d e l y r e c o g n i z e d . Many o f t h e c u r r e n t C o m p u t e r A i d e d D e s i g n (CAD) s y s t e m s a n d g r a p h i c p r o g r a m s do n o t h a v e a g o o d r e p r e s e n t a t i o n scheme f o r s o l i d s . M o s t c u r r e n t CAD s y s t e m s g e n e r a t e s o l i d s by u s i n g t h e w i r e f r a m e m e t h o d . A l t h o u g h t h i s a p p r o a c h i s q u i t e u s e f u l i n r e p r e s e n t i n g o b j e c t s , i t h a s s e v e r a l d e f i c i e n c i e s . T h e most o b v i o u s one i s t h a t w i r e f r a m e s a r e a m b i g u o u s . F i g u r e 1 i l l u s t r a t e s a f r ame t h a t d o e s n o t r e p r e s e n t a u n i q u e p o l y h e d r o n . O t h e r a m b i g u o u s f r a m e e x a m p l e s a r e p r o v i d e d by M a r k o w s k y a n d W e s l e y [ 8 ] . F u r t h e r m o r e , R e q u i c h a o u t l i n e d s e v e r a l o t h e r d e f i c i e n c i e s [ 1 2 ] . F i g u r e 1. W i r e f r a m e a m b i g u i t y . 2 T h e L I G 6 l a n g u a g e a n d p r o g r a m m i n g s y s t e m [13 ] d e v e l o p e d a t The U n i v e r s i t y o f B r i t i s h C o l u m b i a u s e s t h e p r i m i t i v e " f a c e " t o c o n s t r u c t s o l i d s . T h i s p r o g r a m , h o w e v e r , c a n n o t d e t e c t t h e s i t u a t i o n o f two s o l i d s c o l l i d i n g w i t h e a c h o t h e r . H e n c e , a b e t t e r r e p r e s e n t a t i o n scheme i s d e s i r e d t o s o l v e s u c h a m b i g u i t i e s . S o l i d m o d e l l i n g i s a t h e o r y f o r t h e r e p r e s e n t a t i o n o f s o l i d s p r e f e r a b l e t o w i r e f r a m e s b e c a u s e i t i s u n a m b i g u o u s a n d c o m p l e t e . T h e r e a r e s i x d i f f e r e n t s chemes a s c a t e g o r i z e d by R e q u i c h a [ 1 1 ] : (1) p r i m i t i v e i n s t a n c i n g ; (2) s p a t i a l e n u m e r a t i o n ; (3) c e l l d e c o m p o s i t i o n ; (4) c o n s t r u c t i v e s o l i d g e o m e t r y ; (5) b o u n d a r y r e p r e s e n t a t i o n ; a n d (6) s w e e p i n g . O v e r t h e p a s t t e n y e a r s , s e v e r a l g e o m e t r i c m o d e l l i n g s y s t e m s (GMS) h a v e b e e n d e v e l o p e d w h i c h were b a s e d on t h e s o l i d m o d e l l i n g t h e o r i e s a b o v e , u s i n g t h e t e c h n o l o g y o f t h e 1 9 7 0 ' s . C o n s t r u c t i v e S o l i d G e o m e t r y (CSG) a n d B o u n d a r y R e p r e s e n t a t i o n ( B - R e p ) h a v e b e e n t h e most p o p u l a r s chemes among t h e s e s y s t e m s . CSG r e p r e s e n t s a s o l i d by a t r e e o f s e t o p e r a t i o n s a n d r i g i d m o t i o n s . On t h e o t h e r h a n d , B - R e p d e f i n e s a s o l i d by a c o l l e c t i o n o f v e r t i c e s , e d g e s , a n d f a c e s a n d t h e i r n e i g h o u r h o o d r e l a t i o n s h i p s . H o w e v e r , more r e c e n t l y , t h e r e i s a new scheme u s i n g a d i f f e r e n t a p p r o a c h . I t i s t h e O c t r e e scheme [9 ] w h i c h r e c o r d s t h e r e g i o n s o f s p a c e o c c u p i e d by a s o l i d a t a f i x e d m a x i m a l r e s o l u t i o n [ 5 ] . M o s t s y s t e m s u se C S G , B - R e p o r a c o m b i n a t i o n s o f s chemes as t h e i r p r i m a r y r e p r e s e n t a t i o n scheme f o r i n p u t a n d o u t p u t . F o r e x a m p l e , t h e s y s t e m P A D L - 2 [ 2 ] , d e v e l o p e d a t t h e U n i v e r s i t y 3 o f R o c h e s t e r , u s e s CSG as i t s p r i m a r y r e p r e s e n t a t i o n scheme w h i l e G M S o l i d [ 1 ] , d e v e l o p e d a t G e n e r a l M o t o r s , u s e s a h y b r i d C S G / i s B - R e p s c h e m e . A n o t h e r s y s t e m i s B U I L D - 2 [ 3 ] , d e v e l o p e d by a g r o u p f r o m C a m b r i d g e U n i v e r s i t y , i t u s e s B - R e p a s i t s p r i m a r y r e p r e s e n t a t i o n s c h e m e . T h e d o m a i n o f t h i s t h e s i s w i l l be u s i n g t h e B - R e p a s t h e r e p r e s e n t a t i o n scheme a s w e l l . B - R e p was c h o s e n a s t h e p r i m a r y r e p r e s e n t a t i o n scheme b e c a u s e a l l r e c t i l i n e a r p o l y h e d r a c a n be r e p r e s e n t e d by t h i s s c h e m e . B e s i d e s , i t i s one o f t h e u n a m b i g u o u s s c h e m e s f o r r e p r e s e n t i n g 3 - d i m e n s i o n a l s o l i d o b j e c t s . F u r t h e r m o r e , i t c o v e r s a r i c h s e t o f d o m a i n s a s i n t h e s c h e m e s o f c e l l d e c o m p o s i t i o n o r C S G . F i n a l l y , t h e a v a i l a b l e r e p r e s e n t a t i o n s o f v e r t i c e s , e d g e s , a n d . f a c e s e a s e t h e g e n e r a t i o n o f l i n e d r a w i n g s a n d g r a p h i c o b j e c t s , t o s u p p o r t g r a p h i c i n t e r a c t i o n a n d o t h e r p u r p o s e s a s w e l l [1 1 ] . GMSs u s i n g t h e s o l i d m o d e l l i n g t e c h n i q u e h a v e many a p p l i c a t i o n s . In g r a p h i c s , i t c a n g e n e r a t e w i r e f r a m e d r a w i n g s , d r a w i n g s w i t h r e m o v e d h i d d e n l i n e s a n d i t c a n p r o v i d e s h a d e d r e n d e r i n g s a s w e l l . In d e s i g n a n a l y s i s , mass p r o p e r t i e s c a n be c a l c u l a t e d e a s i l y ; i n t e r f e r e n c e d e t e c t i o n , s u c h a s w h e t h e r two p a r t s a r e o c c u p y i n g t h e same s p a c e when f i t t i n g them t o g e t h e r , i s p o s s i b l e . In m a n u f a c t u r i n g , i t c a n be u s e d f o r NC v e r i f i c a t i o n , f o r i n s t a n c e , f i n d i n g o u t t h e v o l u m e o f a p a r t t h a t i s c u t o f f f r o m a s o l i d . O t h e r a p p l i c a t i o n s s u c h a s t h e a u t o m a t i c g e n e r a t i o n o f meshes f o r f i n i t e - e l e m e n t a n a l y s i s , a n d t h e a u t o m a t i c g e n e r a t i o n o f NC p r o g r a m s a r e i n t h e r e s e a r c h s t a g e [ 1 2 ] . 4 The o b j e c t i v e o f t h i s t h e s i s i s t o i m p l e m e n t an a l g o r i t h m f o r s o l i d m o d e l l i n g where t h e d o m a i n c o v e r s a l l p o l y h e d r a whose f a c e s a r e c o n v e x a n d / o r c o n c a v e p o l y g o n s a s . d e f i n e d i n C h a p t e r Two. 5 CHAPTER 2 D E F I N I T I O N S AND R E P R E S E N T A T I O N S 2 . 1 P o l y g o n 2 . 1 . 1 D e f i n i t i o n A p o l y g o n ( F i g u r e 2 ) i s t h e f i g u r e f o r m e d by c h o o s i n g a s e q u e n c e o f n d i s t i n c t p o i n t s A ( 1 ) , . . . , A ( n ) , j o i n i n g a d j a c e n t p o i n t s w i t h a l i n e s e g m e n t , a n d j o i n i n g t h e l a s t p o i n t w i t h t h e f i r s t o n e . T h e p o i n t s A ( 1 ) , . . . , A ( n ) a r e t h e v e r t i c e s o f t h e p o l y g o n , a n d t h e s e g m e n t s A ( 1 ) A ( 2 ) , . . . , A ( n ) A ( 1 ) a r e i t s s i d e s (a v e r t e x b o u n d s e x a c t l y two s i d e s ) [ 7 ] . A ( l ) A ( 2 ) F i g u r e 2 . A p l a n a r , s i m p l e a n d s t r a i g h t p o l y g o n . In t h i s t h e s i s , i t i s a s s u m e d t h a t a p o l y g o n i s p l a n a r ( t h a t i s , a l l i t s s i d e s l i e i n one p l a n e ) , s i m p l e ( t h a t i s , i t s s i d e s i n t e r s e c t o n l y a t common b o u n d i n g v e r t i c e s ) , a n d s t r a i g h t ( t h a t i s , a l l i t s s i d e s a r e s e g m e n t s o f s t r a i g h t l i n e s . ) 2 . 1 . 2 R e p r e s e n t a t i o n A p l a n a r , s i m p l e , a n d s t r a i g h t p o l y g o n P c a n be r e p r e s e n t e d by a s e t o f d i s t i n c t p o i n t s , ( A ( 1 ) , . . . , A ( n ) ) w h e r e t h e p o i n t s a r e o r d e r e d i n a c y c l i c manner a n d t h e 6 v e r t i c e s a r e g i v e n by i t s x , y , a n d z c o o r d i n a t e s . The s e t o f t h e b o u n d i n g e d g e s o f t h e p o l y g o n i s ( A ( 1 ) A ( 2 ) , . . . , A ( n ) A ( 1 ) ) . 2 . 2 P o l y h e d r o n 2 . 2 . 1 D e f i n i t i o n A p o l y h e d r o n i s a s e t o f s i m p l e p o l y g o n s ( a s d e f i n e d a b o v e ) w i t h t h e p r o p e r t y t h a t e v e r y s i d e o f a p o l y g o n i s a l s o a s i d e o f e x a c t l y one o t h e r p o l y g o n i n t h e s y s t e m . T h e p o l y g o n s a r e c a l l e d t h e f a c e s o f t h e p o l y h e d r o n , t h e i r s i d e s a r e i t s e d g e s , a n d t h e i r v e r t i c e s a r e i t s v e r t i c e s . The s y s t e m a s a w h o l e i s c a l l e d t h e s u r f a c e o f t h e p o l y h e d r o n [ 7 ] . In a d d i t i o n , i n t h i s t h e s i s , w e l l - f o r m e d n e s s i s a s s u m e d t o be a g l o b a l c h a r a c t e r i s t i c o f t h e p o l y h e d r o n ; t h a t i s , p o l y h e d r a s u r f a c e s a r e made o f c o n n e c t e d a n d o r i e n t a b l e f a c e s , a n d t h e p o i n t s s h a r e d by a n y p a i r o f t h e i r . , f a c e s a r e o n l y t h o s e common e d g e s o r v e r t i c e s ; t h e y do n o t s 'el f - i n t e r s e c t . 2 . 2 . 2 R e p r e s e n t a t i o n A w e l l - f o r m e d p o l y h e d r o n S i s r e p r e s e n t e d by a s e t o f f a c e s ( F ( 1 ) , . . . , F ( n ) ) . E a c h f a c e F ( i ) , i = 1 , . . . , n , i s r e p r e s e n t e d by an o r d e r e d s e t o f e d g e s E , e a c h i n t u r n c o n s t i t u t i n g a c y c l e on F ( i ) . E a c h e d g e E ( j ) o f S , j = 1 , . . . , r , i s d e f i n e d by two e n d p o i n t s P ( k 1 ) a n d P ( k 2 ) w h e r e P ( k ) = ( X ( k ) , Y ( k ) , Z ( k ) ) , k = 1 , . . . , m , i s a v e r t e x o f S . 2 . 3 . R e g u l a r i t y T h i s t h e s i s p r i m a r i l y d e a l s w i t h o b j e c t s t h a t a r e . s u b s e t s o f E u c l i d e a n s p a c e s o f o n e , t w o , a n d t h r e e d i m e n s i o n s . T i l o v e 7 [ 1 5 ] g a v e t h e f o l l o w i n g t o p o l o g i c a l d e f i n i t i o n s o f i n t e r i o r , c l o s u r e , b o u n d a r y , a n d r e g u l a r i t y : A p o i n t p i s an e l e m e n t o f t h e i n t e r i o r o f a s e t X , i X , i f t h e r e e x i s t s a n e i g h o u r h o o d o f p ( e . g . , an o p e n b a l l a b o u t p) t h a t i s c o n t a i n e d i n X ; p i s an e l e m e n t o f t h e c l o s u r e o f X , k X , i f e v e r y n e i g h o u r h o o d o f p c o n t a i n s a p o i n t o f X ; p i s an e l e m e n t o f t h e b o u n d a r y o f X , b X , i f p i s an e l e m e n t o f b o t h kX a n d k ( c X ) , where c X d e n o t e s t h e u s u a l c o m p l e m e n t o f X ; a n d a s e t X i s s a i d t o be r e g u l a r i f f X = k i X . An o b j e c t f r o m a r e g u l a r s e t must n o t h a v e d a n g l i n g f a c e s o r d a n g l i n g e d g e s . F i g u r e 3 - shows an o b j e c t w h i c h i s n o t i n t h e r e g u l a r s e t . F u r t h e r m o r e , t h e r e g u l a r i z a t i o n o f a s e t i s d e f i n e d a s r X = k i X . F i g u r e 3 . N o n - r e g u l a r o b j e c t . U n d e r c o n v e n t i o n a l s e t o p e r a t o r s i n t e r s e c t i o n ( I ) , u n i o n ( U ) , a n d d i f f e r e n c e ( - ) , r e g u l a r s e t s a r e n o t c l o s e d . H o w e v e r , t h e r e g u l a r i z e d s e t o p e r a t o r s , I * , U * , a n d - * , do p r e s e r v e r e g u l a r i t y . U s i n g t h e a b o v e t o p o l o g i c a l n o t i o n s , i f X a n d Y a r e 8 two r e g u l a r s e t s , t h e r e g u l a r i z e d s e t o p e r a t i o n s o f X a n d Y c a n be d e f i n e d a s f o l l o w s : X I * Y = k i ( X I Y ) , X U * Y = k i ( X U Y ) , X - * Y = k i ( X - Y ) , c * X = k i c X . I t c a n be shown t h a t t h e r e g u l a r s e t s a n d t h e r e g u l a r i z e d s e t o p e r a t o r s f o r m a B o o l e a n a l g e b r a . F i g u r e 4 i l l u s t r a t e s an e x a m p l e t h a t shows t h e d i f f e r e n c e b e t w e e n c o n v e n t i o n a l a n d r e g u l a r i z e d i n t e r s e c t i o n [ 1 1 ] , [ 1 5 ] . F i g u r e 4 . C o n v e n t i o n a l v e r s u s r e g u l a r i z e d i n t e r s e c t i o n o f two r e g u l a r s e t s ( s e t s shown i n o r t h o g r a p h i c p r o j e c t i o n ) . 2 . 4 . S e t M e m b e r s h i p C l a s s i f i c a t i o n T i l o v e [ 1 5 ] d e f i n e s a m e m b e r s h i p c l a s s i f i c a t i o n f u n c t i o n ( F i g u r e 5) a s f o l l o w s : M [ X , S ] = ( X i n S , X o n S , X o u t S ) w h e r e X i n S = X I * ' i S = k ' i ' ( X I i S ) XonS = X I * ' bS X o u t S = X I * ' cS 9 a n d S i s a r e f e r e n c e r e g u l a r s e t i n a s u b s p a c e W o f E 3 (W may be E 3 o r a s u b s e t o f E 3 ) , a n d X i s a c a n d i d a t e r e g u l a r s e t i n a s u b s p a c e W o f W t o be c l a s s i f i e d w i t h r e s p e c t t o S. N o t e : p r i m e d s y m b o l s ( e . g . , k ' , a n d I * ' ) d e n o t e o p e r a t i o n s i n W , a n d u n p r i m e d s y m b o l s d e n o t e o p e r a t i o n s i n W. F i g u r e 5 . M e m b e r s h i p c l a s s i f i c a t i o n f u n c t i o n . He a l s o p r o v i d e d e x a m p l e s f o r d i f f e r e n t c a s e s o f t h i s f u n c t i o n as shown i n F i g u r e 6 a n d F i g u r e 7 a n d c l a i m e d t h a t t h e t h e o r y i s v a l i d f o r a n y c h o i c e o f W a n d W . M [L,P] = (L inP, LonP, LoutP) X F i g u r e 6 . M e m b e r s h i p c l a s s i f i c a t i o n e x a m p l e : L i n e / p o l y g o n c l i p p i n g . 1 0 A M[P,R] = (PinR, i, PoutR) A PoutR PinR-F i g u r e 7 . Member s h i p - c l a s s i f i c a t i o n e x a m p l e P o l y g o n i n t e r s e c t i o n . R e s u l t s f r o m t h e c l a s s i f i c a t i o n f u n c t i o n w i l l s e p a r a t e t h e c a n d i d a t e s e t i n t o t h r e e q u a s i - d i s j o i n t d e c o m p o s i t i o n p a r t s , X i n S , X o n S , a n d X o u t S . T h a t m e a n s , t h e u n i o n o f t h e t h r e e p r o d u c e s t h e c a n d i d a t e s e t , w h i l e t h e r e g u l a r i z e d i n t e r s e c t i o n o f t h e t h r e e i s n u l l [ 1 5 ] . S = A U* B A B X ^ XonA XonB ==> XonS / XonA v d  =-) > XinS XonB ' F i g u r e 8 . O n / o n a m b i g u i t y . H o w e v e r , t h e r e e x i s t . s an " O n / o n " a m b i g u i t y i n c l a s s i f i c a t i o n as i l l u s t r a t e d i n F i g u r e 8 . T h e O n / o n a m b i g u i t y c a n be r e s o l v e d i n t o two d i f f e r e n t " O n " t y p e s by t e s t i n g t h e 11 n e i g h b o u r h o o d s o f a p o i n t p on X ( s e e A p p e n d i x B f o r an a l g o r i t h m ) . I t i s n e c e ' s s a r y t o d i s t i n g u i s h t h e two d i f f e r e n t t y p e s a s f o l l o w s : X t y p e1 o n S i s t h a t p o r t i o n o f s p a c e on X w i t h t h e r e g u l a r s e t s c o n t a i n i n g X on t h e same s i d e o f t h e s p a c e . X t y p e 2 o n S i s t h a t p o r t i o n o f s p a c e on X w i t h t h e r e g u l a r s e t s c o n t a i n i n g X on o p p o s i t e s i d e s o f t h e s p a c e . H e n c e , t h e " o n " edge o f t h e o b j e c t t o t h e l e f t o f F i g u r e 8 i s a " X t y p e l o n S " w h i l e t h e r i g h t h a n d o b j e c t i s o f t y p e " X t y p e 2 o n S " . R e g u l a r ' i z e d s e t or: a e r a t i o n s de isired S e g m e n t s A I * B A U * B A - * B B - * A X i n B + + X i n A + X t y p e1 o n B + X t y p e 2 o n B + + X o u t B X o u t A + + -j- : d e n o t e s i n c l u d e d T a b l e I . E d g e / F a c e s e g m e n t s t o be i n c l u d e d i n t h e d e s i r e d r e g u l a r i z e d s e t o p e r a t i o n s . T h u s , t h e c l a s s i f i c a t i o n f u n c t i o n M [ X , S ] c a n be a u g m e n t e d a s M ' [ X , S ] = ( X i n S , X t y p e l o n S , X t y p e 2 o n S , X o u t S ) f o r s e t s f o r w h i c h " O n / o n " a m b i g u i t i e s c a n o c c u r . T a b l e I shows t h e r e l a t i o n s h i p b e t w e e n t h e m e m b e r s h i p c l a s s i f i c a t i o n f u n c t i o n a n d t h e r e g u l a r i z e d s e t o p e r a t i o n s o f two p o l y g o n s / p o l y h e d r a A a n d 1 2 B [ 5 ] . D e p e n d i n g on t h e d e s i r e d o p e r a t i o n , a p p r o p r i a t e s u b s e t s o f e d g e / f a c e s e g m e n t s a r e c h o s e n . N o t e t h a t X t y p e l o n A i s e q u a l t o X t y p e l o n B , a s i s X t y p e 2 o n A e q u a l t o X t y p e 2 o n B . I t f o l l o w s t h a t t h e r e a r e s i x s e t s o f s e g m e n t s , n a m e l y , X i n A , X i n B , X t y p e l o n A , X t y p e 2 o n B , X o u t A , a n d X o u t B . 1 3 CHAPTER 3 2-D POLYGON MODELLING ALGORITHM 3 . 1 Doma i n- o f A l q o r i thm The d o m a i n o f t h i s P o l y g o n M o d e l l i n g A l g o r i t h m i s t h e s e t o f a l l 2 - d i m e n s i o n a l p l a n a r , s i m p l e , a n d s t r a i g h t p o l y g o n s . M o r e o v e r , two p o l y g o n s w h i c h t o u c h a f a p o i n t a r e c o n s i d e r e d t o be two d i s t i n c t p o l y g o n s ( F i g u r e 9). F i g u r e 9. P o l y g o n s w h i c h t o u c h a t one p o i n t . 3.2 D a t a S t r u c t u r e T h e f o l l o w i n g P a s c a l T Y P E s i l l u s t r a t e t h e d a t a s t r u c t u r e o f a. p o l y g o n a n d a l i s t o f p o l y g o n s : X Y p o i n t = RECORD x , y : R e a l E N D ; { ( x , y ) p o i n t } P o i n t L i s t = @ V e r t e x ; { o r d e r l i s t o f p o i n t s } V e r t e x = RECORD p : X Y p o i n t ; n e x t : P o i n t L i s t E N D ; 1 4 a P o l y g o n = ^ p o l y g o n ; { a p o l y g o n } p o l y g o n = RECORD num : i n t e g e r ; { number o f v e r t i c e s } p o i n t : P o i n t L i s t { p o i n t s o f p o l y g o n } E N D ; P o l y g o n s = d L i n e s ; { a l i s t o f p o l y g o n s } L i n e s = RECORD num : i n t e g e r ; { number o f v e r t i c e s } n e x t : P o l y g o n s ; { l i n k t o n e x t one } p t : P o i n t L i s t { p o i n t s o f p o l y g o n } E N D ; P o l y g o n i s a r e c o r d o f two c o m p o n e n t s . The f i r s t c o m p o n e n t o f t h e r e c o r d , num, r e c o r d s t h e number o f v e r t i c e s i n t h e p o l y g o n ; t h e s e c o n d c o m p o n e n t , p o i n t , i s a l i n k e d l i s t o f ( x , y ) v e r t i c e s o f t h e p o l y g o n . T h u s , a s e t o f p o l y g o n s i s a l i n k e d l i s t o f p o l y g o n s . A l i n e i s r e p r e s e n t e d by i t s e n d p o i n t s . A l i s t o f l i n e s e g m e n t s f o r t h e c l a s s i f i c a t i o n s X i n B , X t y p e l o n B , X t y p e 2 o n B , a n d X o u t B i s r e p r e s e n t e d a s f o l l o w s : L i n e L i s t = @ V e r t i c e s ; { a l i s t o f l i n e s } V e r t i c e s = RECORD p , q : X Y p o i n t ; { e n d p o i n t s } n e x t : L i n e L i s t { l i n k t o n e x t one } E N D ; R e g u l a r i z e d s e t o p e r a t i o n s b e t w e e n two p o l y g o n s A a n d B a r e p a s s e d a s a s t r i n g o f c h a r a c t e r s , t h e y h a v e t h e d a t a s t r u c t u r e 1 5 O p C o d e = PACKED A R R A Y [ 1 . . 6 ] OF C H A R ; { A Op B } T h e s e t o f v a l i d O p c o d e i s : ' A I * B ' , ' A U * B ' , ' A - * B ' , a n d ' B - * A ' . 3 . 3 2-D A l g o r i t h m F o r a b e t t e r u n d e r s t a n d i n g o f t h e d e t a i l e d a l g o r i t h m w h i c h f o l l o w s , an i n f o r m a l d e s c r i p t i o n o f t h e a l g o r i t h m i s p r o v i d e d f i r s t : 1. { I n p u t p o l y g o n s } R e a d i n t h e p o l y g o n s A a n d B ; 2 . { I n i t i a l i z a t i o n } I n i t i a l i z e t h e s e g m e n t l i s t s X i n B , X t y p e l o n B , X t y p e 2 o n B , a n d X o u t B t o n i l ; 3 . { M e m b e r s h i p c l a s s i f i c a t i o n f u n c t i o n M ' [ A , B ] } S e p a r a t e i n t o d i s j o i n t s u b - s e g m e n t s e a c h edge o f P o l y g o n A a c c o r d i n g t o t h e c l a s s i f i c a t i o n f u n c t i o n , t h e n a d d e a c h s u b - s e g m e n t s t o t h e a p p r o p r i a t e l i s t ; 4 . { M e m b e r s h i p c l a s s i f i c a t i o n f u n c t i o n M ' [ B , A ] } R e v e r s e t h e r o l e s o f p o l y g o n s A a n d B a n d r e p e a t s t e p s 2 a n d 3; 5 . {A Op B} D e p e n d i n g on w h i c h r e g u l a r i z e d s e t o p e r a t i o n i s d e s i r e d , f e t c h e d g e s e g m e n t l i s t s a c c o r d i n g t o T a b l e I ; 6 . { G e n e r a t e r e s u l t s } M e r g e t h e l i s t s a n d t r a v e r s e t h e l i s t t o g e n e r a t e p o l y g o n s ( t h e r e may be n o n e , o n e , o r s e v e r a l p o l y g o n s ) . T h e s e p o l y g o n s a r e t h e d e s i r e d r e s u l t o f t h e o p e r a t i o n . In d e t a i l , t h e 2-D P o l y g o n M o d e l l i n g A l g o r i thm i s t h e f o l l o w i n g : S t e p 0 . { D e c l a r a t i o n } D e c l a r e X i n B , X i n A , X t y p e l o n B , X t y p e 2 o n B , 1 6 X t y p e l o n A ' , X t y p e 2 o n A , X o u t B , a n d X o u t A as T Y P E L i n e L i s t a n d i n t P o i n t s ( i n t e r s e c t i o n p o i n t s ) a s T Y P E a P o l y g o n as d e f i n e d i n s e c t i o n 3 . 2 ; S t e p 1. { I n p u t p o l y g o n s ] R e a d i n t h e two p o l y g o n s A a n d B ; S t e p 2 . { I n i t i a l i z a t i o n ] I n i t i a l i z e t h e edge segment l i s t s X i n B , X t y p e l o n B , X t y p e 2 o n B , a n d X o u t B t o n i l ( F i g u r e 10 i l l u s t r a t e s t h e u s a g e o f t h e s e l i s t s ) ; Xtype2onA " i n t e r s e c t i o n points" A F i g u r e 10. Segment a n d i n t e r s e c t i o n p o i n t l i s t s i l l u s t r a t i o n . S t e p 3 . {Get p o l y g o n w i n d o w ] G e t t h e m i n i m a l e n c l o s i n g window of p o l y g o n B ; S t e p 4 . {For e a c h edge o f A ] F e t c h an edge ( v 1 , v 2 ) o f p o l y g o n A where v 1 , v2 a r e e n d p o i n t s o f t h e e d g e ; S t e p 5 . { I n i t i a l i z e v a l u e ] I n i t i a l i z e t h e i n t e r s e c t i o n p o i n t l i s t i n t P o i n t s t o n i l ; S t e p 6 . {Check c l i p p i n g ] I f edge ( v 1 , v 2 ) i s e n t i r e l y o u t s i d e t h e e n c l o s i n g window o f B , t h e n a d d t h e edge t o X o u t B l i s t , a n d go t o s t e p 19 , e l s e c o n t i n u e ; S t e p 7 . {Add " e n d p o i n t s t o i n t P o i n t s ] A d d t h e e n d p o i n t s v.1 a n d 1 7 v2 t o i n t P o i n t s ; S t e p 8 . {For e a c h edge o f B} G e t an edge ( c l , c 2 ) o f p o l y g o n B ; S t e p 9 . I f t h e two e d g e s a r e p a r a l l e l , t h e n go t o s t e p 11 , e l s e c o n t i n u e ; S t e p 10 . { I n t e r s e c t i o n c a s e } I f t h e two e d g e s i n t e r s e c t a t a p o i n t , t h e n a d d t h a t p o i n t t o l i s t i n t P o i n t s ; go t o s t e p 13; S t e p 11 . { P a r a l l e l c a s e } I f t h e two e d g e s a r e n o t c o l l i n e a r , t h e n go t o s t e p 13, e l s e c o n t i n u e ; S t e p 12. { C o l l i n e a r c a s e } I f t h e two e d g e s h a v e a common s u b -s e g m e n t , t h e n t e s t t h e s e g m e n t f o r " o n " t y p e : i f i t i s " T y p e 1", t h e n a d d t h a t s egment t o t h e l i s t X t y p e l o n B , e l s e a d d i t t o t h e l i s t X t y p e 2 o n B ( s e e s e c t i o n 2 . 4 f o r d e f i n i t i o n s o f X t y p e l o n B a n d X t y p e 2 o n B a n d s ee A p p e n d i x B f o r a 3-D a l g o r i t h m f o r d e c i d i n g " T y p e 1" o r " T y p e 2 " " o n " c a s e s ) ; i n e i t h e r c a s e , a d d t h e e n d p o i n t s o f t h e common segment t o t h e l i s t i n t P o i n t s ; S t e p 13 . U n l e s s a l l e d g e s f o r p o l y g o n B h a v e b e e n e x a m i n e d , f e t c h t h e n e x t edge o f p o l y g o n B , rename i t t o ( c 1 , c 2 ) a n d go t o s t e p 9 ; e l s e c o n t i n u e ; S t e p 14. { S o r t p o i n t s } S o r t a l l p o i n t s o f t h e i n t P o i n t s l i s t a l o n g e d g e ( v l , v 2 ) a n d e l i m i n a t e a n y d u p l i c a t e v e r t i c e s ; t h e r e s u l t i n g s o r t e d l i s t i s a s s i g n e d b a c k t o i n t P o i n t s ; S t e p 15 . { F e t c h p o i n t s w h i c h r e p r e s e n t a segment} F e t c h t h e f i r s t p a i r o f p o i n t s ( t 1 , t 2 ) f r o m t h e l i s t i n t P o i n t s ; S t e p 16 . . { F i n d X i n B a n d X o u t B } I f (11 , 1 2 ) i s e i t h e r i n t h e X t y p e l o n B l i s t o r X t y p e 2 o n B l i s t , t h e n go t o s t e p 18, e l s e c o n t i n u e ; S t e p 17 . I f t h e m i d p o i n t o f ( t 1 , t 2 ) l i e s i n s i d e p o l y g o n B , t h e n 18 a d d t h e segment ( 1 1 , 1 2 ) t o X i n B l i s t , e l s e a d d t h e segment t o X o u t B l i s t (a p o i n t i n c l u s i o n t e s t i s r e q u i r e d h e r e , s ee [6 ] [ 1 4 ] f o r an a l g o r i t h m ) ; S t e p 18 . I f t2 was t h e l a s t p o i n t i n t h e i n t P o i n t s l i s t , t h e n go t o s t e p 19, e l s e f e t c h t h e n e x t p a i r o f p o i n t s ( e . g . , t h e s e q u e n c e t ( 1 ) , t ( 2 ) , . . , t ( n ) w i l l g e n e r a t e t h e p a i r s t ( 1 ) t ( 2 ) , t ( 2 ) t ( 3 ) , . . . , t ( n - 1 ) t ( n ) ) a n d rename i t ( t 1 , t 2 ) , go t o s t e p 16 ; S t e p 19 . U n l e s s a l l e d g e s f o r p o l y g o n A h a v e b e e n e x a m i n e d , f e t c h t h e n e x t edge o f p o l y g o n A , rename i t t o ( v 1 , v 2 ) a n d go t o s t e p 5 ; e l s e c o n t i n u e ; S t e p 2 0 . ( R e v e r s e A a n d B a n d r e p e a t e n t i r e a l g o r i t h m ] R e v e r s e t h e r o l e s o f p o l y g o n s A a n d B a n d r e p e a t s t e p s 2 t o 19 w i t h X i n B , X t y p e l o n B , X t y p e 2 o n B , X o u t B . , a n d p o l y g o n s A a n d B b e i n g r e p l a c e d by X i n A , X t y p e l o n A , X t y p e 2 o n A , X o u t A , a n d p o l y g o n s B a n d A r e s p e c t i v e l y ; S t e p 2 1 . ( F e t c h a l l l i n e s e g m e n t s ] D e p e n d i n g on t h e d e s i r e d r e g u l a r i z e d s e t o p e r a t i o n , s e l e c t t h e l i n e segment l i s t s a c c o r d i n g t o T a b l e I ; S t e p 2 2 . ( M e r g i n g ] M e r g e a l l s egment l i s t s t o one l i s t ; S t e p 2 3 . ( G e n e r a t e r e s u l t ] T r a v e r s e t h e s e g m e n t s a n d g e n e r a t e c l o s e d p o l y g o n s ( t h e r e may be n o n e , o n e , o r s e v e r a l p o l y g o n s ) , t h e s e p o l y g o n s , a r e t h e r e s u l t o f t h e d e s i r e d o p e r a t i o n . 3 .4 D i s c u s s i o n a n d R e s u l t T h e C o h e n - S u t h e r l a n d c l i p p i n g a l g o r i t h m [4 ] i n s t e p 6 was u s e d f o r e f f i c i e n c y p u r p o s e s [ 1 5 ] . The a l g o r i t h m r e j e c t s a l l 1 9 e d g e s t h a t a r e n o t i n s i d e t h e w i n d o w . In o t h e r w o r d s , t h e s e e d g e s w i l l n o t be i n t e r s e c t i n g w i t h any edge o f t h e p o l y g o n ; h e n c e , t h e e x t r a c a l c u l a t i o n o f c o m p a r i n g t h e edge w i t h e a c h edge o f t h e p o l y g o n i s a v o i d e d . T h e p o i n t - i n - p o l y g o n i n c l u s i o n t e s t [6 ] [14 ] i n s t e p 17 i s i m p o r t a n t b e c a u s e i t d e c i d e s w h e t h e r a p o i n t p i s i n s i d e o r o u t s i d e t h e p o l y g o n . T h e P a s c a l c o d i n g o f a most p a r t s o f t h e 2-D p o l y g o n m o d e l l i n g a l g o r i t h m c a n be f o u n d i n A p p e n d i x A . A p p e n d i x C c o n t a i n s an e x a m p l e f o r w h i c h i n t e r m e d i a t e r e s u l t s fo r . most s t e p s a r e l i s t e d a n d t h e r e s u l t s o f t h e f o u r o p e r a t i o n s b e t w e e n two p o l y g o n s A a n d B a r e g e n e r a t e d a s p o i n t l i s t s . F i g u r e 11 shows t h e r e s u l t s o f t h e e x a m p l e i n A p p e n d i x C . T h e p r o g r a m h a s b e e n r u n on s e v e r a l s e t s o f d a t a a n d t h e r e s u l t s o b t a i n e d a r e c o r r e c t . T h e o u t p u t o f an o p e r a t i o n c a n s e r v e a s i n p u t f o r a n o t h e r o p e r a t i o n . H o w e v e r , t h e a l g o r i t h m c a n g e n e r a t e s e t s t h a t a r e n o t i n i t s d o m a i n , f o r e x a m p l e , p o l y g o n s w i t h h o l e s . The r e s u l t o f t h e r e g u l a r i z e d u n i o n o p e r a t i o n i n t h e 2-D e x a m p l e o f A p p e n d i x C i s a p o l y g o n w i t h a h o l e . Due t o t h e r e p r e s e n t a t i o n s c h e m e , o n l y two p o l y g o n s were g e n e r a t e d a s a r e s u l t , w i t h o u t i d e n t i f y i n g t h e h o l e a s s u c h . A B - * A F i g u r e 1 1 . 2-D e x a m p l e . 21 CHAPTER 4 3-D POLYHEDRON MODELLING ALGORITHM 4 . 1 Doma i n o f A l g o r i t h m T h e d o m a i n o f t h e P o l y h e d r o n M o d e l l i n g A l g o r i t h m i s t h e s e t o f a l l 3 - d i m e n s i o n a l w e l l - f o r m e d p o l y h e d r a whose f a c e s a r e c o m p o s e d o f p o l y g o n s a s d e f i n e d i n C h a p t e r T w o . H o w e v e r , p o l y h e d r a w i t h h o l e s i n i t a r e n o t i n i t s d o m a i n . two p o l y h e d r a w h i c h t o u c h a t one p o i n t o r w h i c h h a v e o n l y a common s u b - s e g m e n t o f an edge a r e c o n s i d e r e d t o be two d i s t i n c t p o l y h e d r a . 4 . 2 D a t a S t r u c t u r e T h e d a t a s t r u c t u r e o f a p o l y h e d r o n i s i l l u s t r a t e d by t h e f o l l o w i n g P a s c a l T Y P E s : X Y Z p o i n t = RECORD x , y , z : r e a l E N D ; { ( x , y , z ) p o i n t } V e r t e x L i s t = © V e r t e x ; { v e r t e x l i s t } V e r t e x = RECORD v : X Y Z p o i n t ; n e x t : V e r t e x L i s t E N D ; E d g e L i s t = @ E d g e s ; { edge l i s t } E d g e s = RECORD e 1 , e2 : i n t e g e r ; { e n d p o i n t s o f edge } n e x t : E d g e L i s t E N D ; 22 N u m b e r L i s t = @Numbers ; { number l i s t } N u m b e r s = RECORD n : i n t e g e r ; { an edge } n e x t : N u m b e r L i s t E N D ; F a c e L i s t = ( sFaces ; { f a c e l i s t } F a c e s = RECORD fnum : i n t e g e r ; { number o f e d g e s } f : N u m b e r L i s t ; { s e t o f e d g e s } n e x t : F a c e L i s t E N D ; P o l y h e d r o n = @ S o l i d ; { a p o l y h e d r o n } S o l i d = RECORD v n u m , { n u m b e r o f v e r t i c e s } enum, { number o f e d g e s } snum : i n t e g e r ; { number o f f a c e s } v e r t : V e r t e x L i s t ; { v e r t e x l i s t } ed : E d g e L i s t ; { edge l i s t } s u r f : F a c e L i s t { f a c e l i s t } E N D ; A p o l y h e d r o n o r s o l i d i s a r e c o r d o f s i x c o m p o n e n t s . The number o f v e r t i c e s o f t h e p o l y h e d r o n i s g i v e n by v n u m , enum i s t h e number o f e d g e s o f t h e p o l y h e d r o n , a n d snum r e p r e s e n t s t h e number o f f a c e s c o n t a i n e d i n t h e p o l y h e d r o n . V e r t e x L i s t c o n t a i n s a l l t h e v e r t i c e s o f t h e p o l y h e d r o n . E a c h v e r t e x i s u n i q u e a n d i s g i v e n by i t s ( x , y , z ) c o o r d i n a t e s . E d g e L i s t i s a p o i n t e r v a r i a b l e t h a t p o i n t s t o a r e c o r d o f 23 t h r e e c o m p o n e n t s . The f i r s t two c o m p o n e n t s ( e 1 , e 2 ) r e p r e s e n t an edge by t h e e n d p o i n t s o f t h a t e d g e . The e n d p o i n t s a r e i n t e g e r n u m b e r s w h i c h t e l l s t h e l o c a t i o n o f v e r t i c e s i n t h e V e r t e x L i s t . The l a s t c o m p o n e n t , n e x t , i s a p o i n t e r t o t h e n e x t e d g e . F a c e L i s t i s a p o i n t e r v a r i a b l e t h a t p o i n t s t o a r e c o r d w i t h t h r e e c o m p o n e n t s . The f i r s t c o m p o n e n t , f n u m , g i v e s t h e number o f e d g e s o f a f a c e w h i l e t h e s e c o n d c o m p o n e n t , f_, i s a l i n k e d N u m b e r L i s t w h i c h i s a l i s t o f " f n u m " i n t e g e r n u m b e r s . E a c h number i n t h e N u m b e r L i s t t e l l s t h e l o c a t i o n o f t h e edge i n t h e E d g e L i s t . The l a s t c o m p o n e n t , n e x t , i s a p o i n t e r t o t h e n e x t f a c e . A l i n e i s r e p r e s e n t e d by i t s e n d p o i n t s . A l i s t o f l i n e s e g m e n t s i s r e p r e s e n t e d a s f o l l o w s : L i n e L i s t = © V e r t i c e s ; { a l i s t o f l i n e s } V e r t i c e s = RECORD l i , 12 : X Y Z p o i n t ; { e n d p o i n t s } n e x t : L i n e L i s t { l i n k t o n e x t one } E N D ; E d q e S e q m e n t i s a p o i n t e r v a r i a b l e t h a t p o i n t s t o a r e c o r d o f f i v e c o m p o n e n t s . I t c o n t a i n s t h e m e m b e r s h i p i n f o r m a t i o n o f a l l e d g e s o f a p o l y h e d r o n . The f i r s t c o m p o n e n t , enurn, i s t h e number a s s i g n e d t o t h i s e d g e . E a c h edge i s s e p a r a t e d i n t o d i s j o i n t s u b - s e g m e n t s a s d e f i n e d by t h e m e m b e r s h i p c l a s s i f i c a t i o n f u n c t i o n . H e n c e , t h e c o m p o n e n t s , i n l , o n l , a n d , o u t l , c o n t a i n t h e c l a s s i f i e d s u b - s e g m e n t s o f t h i s e d g e . The l a s t c o m p o n e n t , n e x t , i s a p o i n t e r t o t h e n e x t E _ s e g m e n t s . The f o l l o w i n g T Y P E S r e p r e s e n t t h e d a t a s t r u c t u r e o f E d g e S e g m e n t a n d 2 4 F a c e S e g m e n t : E d g e S e g m e n t = E s e g m e n t s F a c e S e g m e n t = F _ s e g m e n t s @ E _ s e g m e n t s ; = RECORD enum i n l o n l o u t l n e x t E N D ; @ F _ s e g m e n t s ; { a edge s e g m e n t } i n t e g e r ; { edge number } L i n e L i s t ; { " i n " s egment } L i n e L i s t ; { " o n " s egment } L i n e L i s t ; { " o u t " s egment } E d g e S e g m e n t { a f a c e segment } RECORD fnum : i n t e g e r ; { f a c e number } f l i n e s : . L i n e L i s t ; { a f a c e } n e x t : F a c e S e g m e n t END ; F a c e S e g m e n t i s a p o i n t e r v a r i a b l e t h a t p o i n t s t o a r e c o r d o f t h r e e c o m p o n e n t s . I t c o n t a i n s t h e m e m b e r s h i p i n f o r m a t i o n o f a l l f a c e s o f a p o l y h e d r o n . T h e f i r s t c o m p o n e n t , fnum, g i v e s t h e number a s s i g n e d t o t h i s f a c e . T h e s e c o n d c o m p o n e n t , f 1 i n e s , c o n t a i n s a l l t h e e d g e s t h a t c o n s t i t u t e t h i s f a c e . The l a s t c o m p o n e n t , n e x t , i s a p o i n t e r t o t h e n e x t F _ s e g m e n t s . P o i n t L i s t = @ P o i n t ; { a l i s t o f p o i n t s } P o i n t = RECORD num : i n t e g e r ; p : V e r t e x L i s t END ; C u t _ P o i n t s _ L i s t = ( i C u t P o i n t s ; { a l i s t o f c u t - p o i n t s } 25 C u t P o i n t S = RECORD c : P o i n t L i s t ; n e x t : C u t _ P o i n t s _ L i s t E N D ; C u t P o i n t s L i s t i s a p o i n t e r v a r i a b l e t h a t p o i n t s t o a r e c o r d o f two c o m p o n e n t s a n d i t s d a t a s t r u c t u r e i s r e p r e s e n t e d a b o v e . T h e f i r s t c o m p o n e n t , c , i s a p o i n t e r v a r i a b l e t h a t p o i n t s t o a r e c o r d o f two f i e l d s . T h e f i r s t f i e l d , num, g i v e s t h e edge number a n d t h e s e c o n d f i e l d , p_, i s t h e s e t o f a l l c u t -p o i n t s a l o n g t h e e d g e . T h e l a s t c o m p o n e n t , n e x t , i s a p o i n t e r t o t h e n e x t l i s t o f C u t P o i n t s . As i n t h e 2 - D d a t a s t r u c t u r e , t h e r e g u l a r i z e d s e t o p e r a t i o n s b e t w e e n two p o l y h e d r a a r e p a s s e d a s a s t r i n g o f c h a r a c t e r s t o a p r o c e d u r e ; t h e y h a v e t h e d a t a s t r u c t u r e aOpCode = PACKED A R R A Y [ 1 . . 6 ] OF CHAR; T h e s e t o f v a l i d aOpCode i s : " A I * B " , " A U * B " , " A - * B " , a n d "B - * A " . .4 . 3 3-D A l g o r i t h m F o r a b e t t e r u n d e r s t a n d i n g o f t h e d e t a i l e d a l g o r i t h m w h i c h f o l l o w s , an i n f o r m a l d e s c r i p t i o n o f t h e a l g o r i t h m i s p r o v i d e d f i r s t : 1. { I n p u t p o l y h e d r a } R e a d - i n t h e p o l y h e d r a A a n d B ; 2 . { I n i t i a l i z a t i o n } I n i t i a l i z e X i n B , X t y p e l o n B , X t y p e 2 o n B , a n d X o u t B t o n i l ; 3 . { M e m b e r s h i p c l a s s i f i c a t i o n f u n c t i o n M ' [ A , B ] } S e p a r a t e i n t o d i s j o i n t s u b - s e g m e n t s e a c h f a c e o f p o l y h e d r o n A 26 a c c o r d i n g t o t h e c l a s s i f i c a t i o n f u n c t i o n , t h e n a d d e a c h s u b - s e g m e n t s t o t h e a p p r o p r i a t e l i s t ; 4 . { M e m b e r s h i p c l a s s i f i c a t i o n f u n c t i o n M ' [ B , A ] } R e v e r s e t h e r o l e s o f p o l y h e d r a A a n d B a n d r e p e a t s t e p s 2 a n d 3; 5 . {A Op B} D e p e n d i n g on w h i c h r e g u l a r i z e d s e t o p e r a t i o n i s d e s i r e d , f e t c h f a c e s egment l i s t s a c c o r d i n g t o T a b l e I ; 6 . { G e n e r a t e r e s u l t s } M e r g e t h e l i s t s a n d t r a v e r s e t h e l i s t t o g e n e r a t e p o l y h e d r a ( t h e r e may be n o n e , o n e , o r s e v e r a l p o l y h e d r a ) . T h e s e p o l y h e d r a a r e t h e d e s i r e d r e s u l t o f t h e o p e r a t i o n . T h e d e t a i l e d 3-D P o l y h e d r o n M o d e l l i n g A l g o r i t h m i s d i v i d e d i n t o f i v e p a r t s . P a r t I r e a d s i n t h e two p o l y h e d r a A a n d B . P a r t I I c l a s s i f i e s t h e s e l f e d g e s (a s e l f edge i s an edge o f a p o l y h e d r o n [ 1 0 ] ) o f t h e two p o l y h e d r a by u s i n g a l i n e / s o l i d c l a s s i f i c a t i o n . P a r t I I I c r e a t e s a l l t h e c r o s s e d g e s (a c r o s s edge i s t h e l i n e o f i n t e r s e c t i o n o f two f a c e s o f two d i s t i n c t p o l y h e d r a where t h e i n t e r s e c t e d l i n e i s n o t an s e l f edge o f e i t h e r p o l y h e d r o n [ 1 0 ] ) b e t w e e n t h e two p o l y h e d r a by u s i n g a f a c e / f a c e i n t e r s e c t i o n m e t h o d . P a r t I V u s e s t h e r e s u l t s f r o m P a r t I I a n d P a r t I I I a n d c l a s s i f i e s t h e f a c e s o f t h e two p o l y h e d r a . P a r t V g e n e r a t e s p o l y h e d r a o u t p u t d e p e n d i n g on t h e d e s i r e d r e g u l a r i z e d s e t o p e r a t i o n . T h e d e t a i l e d a l g o r i t h m i s r t h e f o l l o w i n g : S t e p 0 . { G l o b a l d e c l a r a t i o n } D e c l a r e X i n A , X t y p e l o n A , X t y p e 2 o n A , X o u t A , X i n B , X t y p e l o n B , X t y p e 2 o n B , X o u t B , A F a c e L i s t , B F a c e L i s t , A C r o s s L i s t , B C r o s s L i s t a s T Y P E F a c e S e g m e n t ; 27 A E d g e L i s t a n d B E d g e L i s t a s T Y P E E d g e S e g m e n t ; A _ E d g e _ i n t P o i n t s , B _ E d g e _ i n t P o i n t s a s T Y P E C u t _ P o i n t s _ L i s t ; a n d A l l _ C u t _ L i n e s a s T Y P E L i n e L i s t ; PART I_ INPUT POLYHEDRA S t e p 1. { I n p u t p o l y h e d r a } R e a d i n t h e two p o l y h e d r a A a n d B ; PART II_ S E L F EDGE C L A S S I F I C A T I O N S t e p 2 . { G l o b a l i n i t i a l i z a t i o n } I n i t i a l i z e A l l _ C u t _ L i n e s t o n i l ; S t e p 3 . { I n i t i a l i z a t i o n } I n i t i a l i z e B _ E d g e _ i n t P o i n t s , B F a c e L i s t , A E d g e L i s t l i s t s t o n i l ; S t e p 4 . {Get p o l y h e d r o n v o l u m e } G e t t h e m i n i m a l e n c l o s i n g v o l u m e o f p o l y h e d r o n B ; S t e p 5 . {For e a c h edge o f A} F e t c h an edge ( v 1 , v 2 ) o f p o l y h e d r o n A where v 1 , v2 a r e e n d p o i n t s o f e a c h e d g e ; S t e p 6 . { A s s i g n edge number} A s s i g n e a c h edge a number a c c o r d i n g t o t h e o r d e r i t was f e t c h e d ( t h a t i s , t h e f i r s t edge g e t s number 1, t h e s e c o n d 2 , a n d so o n ) ; S t e p 7 . { I n i t i a l i z e v a l u e } I n i t i a l i z e t h e i n t e r s e c t i o n p o i n t l i s t i n t P o i n t s ( T Y P E P o i n t L i s t ) t o n i l a n d s e t I n L i s t , O n L i s t , a n d O u t L i s t ( T Y P E L i n e L i s t ) t o n i l ; S t e p 8 . {Check c l i p p i n g } I f edge ( v 1 , v 2 ) i s e n t i r e l y o u t s i d e 28 t h e e n c l o s i n g v o l u m e o f B , t h e n a d d t h e edge t o O u t L i s t , a n d go t o s t e p 2 6 , e l s e c o n t i n u e ; S t e p 9 . {For e a c h f a c e o f B] G e t a f a c e o f p o l y h e d r o n B ; S t e p 10 . { A s s i g n f a c e n u m b e r ] A s s i g n t h e f a c e a number a c c o r d i n g t o t h e o r d e r i t was f e t c h e d ( t h a t i s , t h e f i r s t f a c e g e t s number 1, t h e s e c o n d 2 , a n d so o n ) ; S t e p 1 1 . { I n i t i a l i z e v a l u e ] I n i t i a l i z e C u t L i s t o f T Y P E L i n e L i s t t o n i l ; S t e p 12 . I f t h e edge i s p a r a l l e l t o t h e f a c e , t h e n go t o s t e p 14, e l s e c o n t i n u e ; S t e p 13 . { I n t e r s e c t i o n c a s e ] I f t h e edge c u t s t h e f a c e a t a p o i n t , t h e n a d d t h a t p o i n t t o l i s t i n t P o i n t s ; go t o s t e p 17 ; S t e p 14. { P a r a l l e l c a s e ] I f t h e e d g e d o e s n o t l i e on t h e p l a n e d e f i n e d by t h e f a c e , t h e n go t o s t e p 17, e l s e c o n t i n u e ; F i g u r e 12. C u t - l i n e s a n d c u t - p o i n t s on a f a c e . F o r t h e n e x t s t e p , t h e f o l l o w i n g t e r m s a r e n e e d e d . A C U T - L I N E i s d e f i n e d as a l i n e t h a t l i e s i n s i d e a f a c e a n d a C U T - POINT i s an e n d p o i n t o f a c u t - l i n e a n d a p o i n t on t h e e d g e o f t h e f a c e a s w e l l . F i g u r e 12 i l l u s t r a t e s e x a m p l e s o f c u t - l i n e s a n d c u t - p o i n t s . N o t e : t h e e n d p o i n t s o f a c u t - l i n e n e e d n o t s t o p 29 a t an edge o f a f a c e , i t may s t o p a t a p o i n t t h a t i s i n s i d e t h e f a c e [ 5 ] . S t e p 15 . {Add c u t - l i n e s } D e t e r m i n e t h e c u t - l i n e s o f t h e e d g e , i . e . , t h o s e p a r t s o f t h e edge t h a t f a l l w i t h i n t h e f a c e . ( T h i s i s s i m i l a r t o s t e p s 2 t o 19 o f t h e 2-D p o l y g o n m o d e l l i n g a l g o r i t h m i n s e c t i o n 3 . 3 o f f i n d i n g X i n B . B a s i c a l l y , t h e edge i s t e s t e d a g a i n s t a l l e d g e s o f t h e f a c e . F i r s t a l l i n t e r s e c t i o n p o i n t s a r e l o c a t e d , t h e n t h e p o i n t s a r e o r d e r e d a l o n g t h e edge a n d a n y d u p l i c a t e p o i n t s a r e e l i m i n a t e d , f i n a l l y , t h e p o i n t s a r e t a k e n i n p a i r s t o f o r m a s e g m e n t a n d a r e t e s t e d w h e t h e r t h e s e g m e n t l i e s on t h e f a c e by u s i n g a p o i n t i n c l u s i o n t e s t ) . S t o r e a l l c u t - l i n e s i n b o t h O n L i s t a n d C u t L i s t l i s t s ; S t e p 16 . {Add c u t - p o i n t s } S t o r e a l l e n d p o i n t s o f c u t - l i n e s i n i n t P o i n t s ; S t e p 17 . {Add f a c e l i s t } I f t h e r e i s a r e c o r d w i t h a f a c e number t h a t m a t c h e s t h e c u r r e n t f a c e number i n t h e B F a c e L i s t , t h e n merge t h e C u t L i s t w i t h t h e e x i s t i n g c u t - l i n e s l i s t , e l s e c r e a t e a new r e c o r d ( T Y P E F _ s e g m e n t s ) o f t h r e e c o m p o n e n t s , f n u m , f l i n e s , a n d n e x t , a n d s t o r e t h e v a l u e o f f a c e n u m b e r , C u t L i s t , a n d n i l t o f n u m , f l i n e s , a n d n e x t r e s p e c t i v e l y ; a p p e n d t h e r e c o r d t o B F a c e L i s t ; S t e p 18. U n l e s s a l l f a c e s f o r p o l y h e d r o n B h a v e b e e n e x a m i n e d , f e t c h t h e n e x t f a c e o f p o l y h e d r o n B a n d go t o s t e p 10; e l s e c o n t i n u e ; S t e p 19 . {Make copy} Make a c o p y o f t h e l i s t i n t P o i n t s t o i n t V e r t i c e s ; S t e p 2 0 . {Add e n d p o i n t s } A d d e n d p o i n t s o f e d g e ( v 1 , v 2 ) t o 30 i n t V e r t i c e s i f t h e y a r e n o t i n t h a t l i s t ; S t e p 21 . { S o r t p o i n t s } S o r t a l l p o i n t s o f t h e i n t V e r t i c e s l i s t a l o n g edge ( v 1 , v 2 ) a n d e l i m i n a t e any d u p l i c a t e v e r t i c e s ; t h e r e s u l t i n g s o r t e d l i s t i s a s s i g n e d b a c k t o i n t V e r t i c e s ; S t e p 2 2 . { F e t c h p o i n t s w h i c h r e p r e s e n t a s egment } F e t c h t h e f i r s t p a i r o f p o i n t s (11 ,1 2 ) f r o m t h e l i s t i n t V e r t i c e s ; S t e p 2 3 . { F i n d " i n " a n d " o u t " t y p e l i n e s egment s } I f ( t 1 , t 2 ) i s n o t i n t h e O n L i s t , t h e n c o n t i n u e , e l s e go t o s t e p 2 5 ; S t e p 2 4 . I f t h e m i d p o i n t o f (11 ,1 2 ) l i e s i n s i d e p o l y h e d r o n B , t h e n a d d t h e s egment ( t 1 , t 2 ) t o I n L i s t , e l s e a d d t h e s egment ( t 1 , t 2 ) t o O u t L i s t (a p o i n t i n c l u s i o n t e s t i s r e q u i r e d h e r e , s e e [ 7 ] f o r an a l g o r i t h m ) ; S t e p 2 5 . I f t 2 was t h e l a s t p o i n t i n t h e i n t V e r t i c e s l i s t , t h e n go t o s t e p 2 6 , e l s e f e t c h t h e n e x t p a i r o f p o i n t s ( e . g . , t h e s e q u e n c e t ( 1 ) , t ( 2 ) , . . , t ( n ) w i l l g e n e r a t e t h e p a i r s t ( 1 ) t ( 2 ) , t ( 2 ) t ( 3 ) , . . . , t ( n - 1 ) t ( n ) ) a n d rename i t ( t 1 , t 2 ) , go t o s t e p 2 3 ; S t e p 2 6 . {Add edge l i s t } C r e a t e a r e c o r d ( T Y P E E _ s e g m e n t s ) a n d s t o r e t h e l i s t s I n L i s t , O n L i s t , a n d O u t L i s t a n d t h e a s s o c i a t e d e d g e number t o t h i s r e c o r d . T h i s r e c o r d i s t h e n i n s e r t e d a t t h e e n d o f t h e A E d g e L i s t l i s t ; S t e p 2 7 . { E l i m i n a t e d u p l i c a t e p o i n t s } E l i m i n a t e a n y d u p l i c a t e p o i n t s o f i n t P o i n t s a n d t h e r e s u l t i n g l i s t i s a s s i g n e d b a c k t o i n t P o i n t s ; S t e p 2 8 . C r e a t e a r e c o r d a n d s t o r e i n t P o i n t s a n d t h e c u r r e n t edge number t o t h i s r e c o r d . T h i s r e c o r d i s t h e n i n s e r t e d a t t h e e n d o f t h e B _ E d g e _ i n t P o i n t s l i s t ; 31 S t e p 2 9 . {Append l i s t s } A p p e n d I n L i s t , O n L i s t , a n d O u t L i s t i n t o A l l _ C u t _ L i n e s l i s t ; S t e p 3 0 . U n l e s s a l l e d g e s f o r p o l y h e d r o n A h a v e b e e n e x a m i n e d , f e t c h t h e n e x t edge o f p o l y h e d r o n A , rename i t t o ( v 1 , v 2 ) a n d go t o s t e p 6 ; e l s e c o n t i n u e ; S t e p 3 1. { R e v e r s e A a n d B a n d r e p e a t e n t i r e a l g o r i t h m } R e v e r s e t h e r o l e s o f p o l y h e d r a A a n d B a n d r e p e a t s t e p s 3 t o 30 w i t h B _ E d g e _ i n t P o i n t s , B F a c e L i s t , A E d g e L i s t , a n d p o l y h e d r a A a n d B b e i n g r e p l a c e d by A _ E d g e _ i n t P o i n t s , A F a c e L i s t , B E d g e L i s t , a n d p o l y h e d r a B a n d A r e s p e c t i v e l y ; PART I I I  CROSS EDGE C L A S S I F I C A T I O N S t e p 3 2 . { I n i t i a l i z e v a l u e s } I n i t i a l i z e A _ C r o s s _ E d g e s a n d B _ C r o s s _ E d g e s ( T Y P E F a c e S e g m e n t ) t o n i l ; S t e p 3 3 . { F o r e a c h f a c e o f A} G e t a f a c e o f p o l y h e d r o n A ; S t e p 3 4 . { A s s i g n f a c e number} A s s i g n t h e f a c e a number a c c o r d i n g t o t h e o r d e r i t was f e t c h e d ( t h a t i s , t h e f i r s t f a c e g e t s number 1, t h e s e c o n d 2 , a n d so o n ) ; S t e p 3 5 . {Get a l l c u t - p o i n t s o f f a c e } I n i t i a l i z e A _ F a c e _ c u t P o i n t s ( T Y P E V e r t e x L i s t ) t o n i l ; S t e p 3 6 . {For e a c h e d g e o f t h e f a c e } F e t c h an edge o f t h e f a c e ; S t e p 3 7 . { F e t c h c u t - l i n e s } G e t t h e . a s s o c i a t e d c u t - p o i n t s l i s t o f t h i s e d g e f r o m A _ E d g e _ i n t P o i n t s ; S t e p 3 8 . {Make c o p y } Make a c o p y o f t h e e d g e ' s c u t - p o i n t s l i s t ; S t e p 3 9 . { M e r g i n g } M e r g e t h i s l i s t w i t h A _ F a c e _ c u t P o i n t s a n d 32 a s s i g n t h e v a l u e b a c k t o A _ F a c e _ c u t P o i n t s ; S t e p 4 0 . U n l e s s a l l e d g e s f o r t h e c u r r e n t f a c e f r o m p o l y h e d r o n A h a v e b e e n f e t c h e d , g e t t h e n e x t edge o f t h e f a c e a n d go t o s t e p 3 7 , e l s e c o n t i n u e ; S t e p 4 1 . { E l i m i n a t e d u p l i c a t e p o i n t s } E l i m i n a t e a n y d u p l i c a t e p o i n t s o f A _ F a ' c e _ c u t P o i n t s , t h e r e s u l t i n g l i s t i s a s s i g n e d b a c k t o A _ F a c e _ c u t P o i n t s ; S t e p 4 2 . {For e a c h f a c e o f B} G e t a f a c e o f p o l y h e d r o n B ; S t e p 4 3 . { A s s i g n f a c e number} A s s i g n t h e f a c e a number a c c o r d i n g t o t h e o r d e r i t . w a s f e t c h e d ( t h a t i s , t h e f i r s t f a c e g e t s number 1, t h e s e c o n d 2, a n d so o n ) ; S t e p 4 4 . { I n i t i a l i z e v a l u e } I n i t i a l i z e C r o s s O n E d g e s ( T Y P E L i n e L i s t ) t o n i l ; S t e p 4 5 . I f t h e two f a c e s a r e p a r a l l e l , t h e n go t o s t e p 5 9 , e l s e c o n t i n u e ; S t e p 4 6 . { L i n e o f i n t e r s e c t i o n } D e t e r m i n e t h e l i n e o f i n t e r s e c t i o n o f t h e two p l a n e s c o n t a i n i n g t h e two f a c e s ; S t e p 4 7 . {Get a l l c u t - p o i n t s o f f a c e } r e p e a t s t e p s 35 t o 41 w i t h t h e l i s t A _ F a c e _ c u t P o i n t s r e p l a c e d by B _ F a c e _ c u t P . o i n t s a n d u s i n g t h e f a c e f r o m p o l y h e d r o n B i n s t e p 42 t h i s t i m e ; S t e p 4 8 . { F i l t e r a l l c u t - p o i n t s } I n i t i a l i z e O n L i n e P o i n t s ( T Y P E V e r t e x L i s t ) t o n i l ; S t e p 4 9 . F e t c h a v e r t i c e f r o m A _ F a c e _ c u t P o i n t s ; S t e p 5 0 . I f t h e v e r t i c e s i s a p o i n t on t h e l i n e o f i n t e r s e c t i o n , t h e n a d d t h e v e r t i c e t o O n L i n e P o i n t s l i s t ; S t e p 5 1 . U n l e s s a l l v e r t i c e s o f t h e A _ F a c e _ c u t P o i n t s l i s t h a v e b e e n e x a m i n e d , f e t c h t h e n e x t v e r t e x a n d go t o s t e p 5 0 , e l s e 33 c o n t i n u e ; S t e p 5 2 . [ F i l t e r a l l c u t - p o i n t s } R e p e a t s t e p s 49 t o 51 w i t h A _ F a c e _ c u t P o i n t s r e p l a c e d by B _ F a c e _ c u t P o i n t s ( i f t h e v e r t i c e s t h a t a r e on t h e l i n e o f i n t e r s e c t i o n , c o n t i n u e t o a d d t o O n L i n e P o i n t s l i s t ) ; S t e p 5 3 . I f number o f v e r t i c e s i n O n L i n e P o i n t s i s l e s s t h a n t w o , t h e n go t o s t e p 5 9 , e l s e c o n t i n u e ; S t e p 5 4 . { S o r t p o i n t s } S o r t a l l p o i n t s o f t h e O n L i n e P o i n t s l i s t a l o n g t h e l i n e o f i n t e r s e c t i o n a n d e l i m i n a t e a n y d u p l i c a t e v e r t i c e s ; t h e r e s u l t i n g s o r t e d l i s t i s a s s i g n e d b a c k t o O n L i n e P o i n t s ; S t e p 5 5 . { F e t c h p o i n t s w h i c h r e p r e s e n t a segment} F e t c h t h e f i r s t p a i r o f p o i n t s ( t 1 , t 2 ) f r o m t h e l i s t O n L i n e P o i n t s ; S t e p 5 6 . { F i n d c r o s s edges } I f (11 , 1 2 ) i s n e i t h e r i n t h e C r o s s O n E d g e s l i s t n o r A l l _ C u t _ L i n e s l i s t , t h e n c o n t i n u e , e l s e go t o s t e p 5 8 ; S t e p 5 7 . I f t h e m i d p o i n t o f ( t 1 , t 2 ) l i e s on t h e t h e c u r r e n t e x a m i n e d f a c e s o f p o l y h e d r a A a n d B, t h e n a d d t h e s egment ( t 1 , t 2 ) t o C r o s s O n E d g e s ; S t e p 5 8 . I f t 2 was t h e l a s t p o i n t i n t h e O n L i n e P o i n t s l i s t , t h e n go t o s t e p 5 9 , e l s e f e t c h t h e n e x t p a i r o f p o i n t s ( e . g . , t h e s e q u e n c e t ( 1 ) , t ( 2 ) , . . , t ( n ) w i l l g e n e r a t e t h e p a i r s t ( 1 ) t ( 2 ) , t ( 2 ) t ( 3 ) , . . . , t ( n - 1 ) t ( n ) ) a n d rename i t ( t 1 , t 2 ) , go t o s t e p 5 6 ; S t e p 5 9 . I f C r o s s O n E d g e s i s e q u a l . t o n i l , t h e n go t o s t e p 62 , e l s e c o n t i n u e ; S t e p 6 0 . { S t o r e c r o s s edges } I f t h e r e i s a r e c o r d w i t h a f a c e 34 number t h a t m a t c h e s t h e c u r r e n t p o l y h e d r o n B f a c e ' s f a c e number i n t h e B _ C r o s s _ E d g e s , t h e n merge t h e C r o s s O n E d g e s w i t h t h e e x i s t i n g c u t - l i n e s l i s t , e l s e c r e a t e a new r e c o r d ( T Y P E F _ s e g m e n t s ) o f t h r e e c o m p o n e n t s , f n u m , f l i n e s , a n d n e x t , a n d s t o r e t h e v a l u e o f f a c e n u m b e r , C r o s s O n E d g e s , a n d n i l t o f n u m , f l i n e s , a n d n e x t r e s p e c t i v e l y ; a p p e n d t h e r e c o r d t o B _ C r o s s _ E d g e s ; S t e p 6 1 . { S t o r e c r o s s edges } R e p e a t s t e p 60 w i t h B _ C r o s s _ E d g e s a n d p o l y h e d r o n B ' s f a c e number b e i n g r e p l a c e d by A _ C r o s s _ E d g e s a n d p o l y h e d r o n A ' s f a c e number r e s p e c t i v e l y ; S t e p 6 2 . U n l e s s a l l f a c e s f o r p o l y h e d r o n B h a v e b e e n e x a m i n e d , f e t c h t h e n e x t f a c e o f p o l y h e d r o n B a n d go t o s t e p 4 3 ; e l s e c o n t i n u e ; S t e p 6 3 . U n l e s s a l l f a c e s f o r p o l y h e d r o n A h a v e b e e n e x a m i n e d , f e t c h t h e n e x t f a c e o f p o l y h e d r o n A a n d go t o s t e p 3 4 ; e l s e c o n t i n u e ; PART I V MEMBERSHIP C L A S S I F I C A T I O N S t e p 6 4 . { I n i t i a l i z a t i o n } I n i t i a l i z e X i n A , X t y p e l o n A , X t y p e 2 o n A , a n d X o u t A t o n i l ; S t e p 6 5 . {For e a c h f a c e o f A} G e t a f a c e o f p o l y h e d r o n A ; S t e p 6 6 . { I n i t i a l i z e v a l u e s } I n i t i a l i z e I n E d g e s , O n E d g e s , a n d O u t E d g e s ( T Y P E L i n e L i s t ) t o n i l ; S t e p 6 7 . { F e t c h c u t - l i n e s } F e t c h t h e c u t - l i n e l i s t c o r r e s p o n d i n g t o t h i s f a c e f r o m t h e A F a c e L i s t ; 35 S t e p 6 8 . {Make copy} Make a c o p y o f t h e c u t - l i n e l i s t ; S t e p 6 9 . {Merge l i s t s } M e r g e t h e c o p i e d l i s t i n t o O n E d g e s l i s t ; S t e p 7 0 . R e p e a t s t e p s 67 t o 69 w i t h A F a c e L i s t b e i n g r e p l a c e d by A C r o s s L i s t ( N o t e : t h e r e may n o t be any c r o s s e d g e s - a s s o c i a t e d w i t h t h i s f a c e , i n t h i s c a s e , n i l i s r e t u r n e d a s v a l u e ) ; S t e p 7 1. Rename t h e c u t - l i n e l i s t f r o m A C r o s s L i s t t o a L i s t ; S t e p 7 2 . {For e a c h edge o f t h e f a c e } F e t c h an edge o f t h e c u r r e n t f a c e ; S t e p 7 3 . { F e t c h c u t - l i n e s } F e t c h t h e edge r e c o r d c o r r e s p o n d i n g t o t h i s e d g e f r o m A E d g e L i s t ; S t e p 7 4 . {Make c o p i e s } Make c o p i e s o f t h e s egment l i s t s i n l , o n l , a n d o u t l ; S t e p 7 5 . {Merge l i s t s } M e r g e t h e c o p y o f i n l i n t o I n E d g e s , t h e c o p y o f o n l i n t o O n E d g e s , a n d t h e c o p y o f o u t l i n t o O u t E d g e s r e s p e c t i v e l y ; S t e p 7 6 . U n l e s s a l l t h e e d g e s o f t h e f a c e h a v e b e e n f e t c h e d , g e t t h e n e x t edge a n d go t o s t e p 7 4 , e l s e c o n t i n u e ; S t e p 7 7 . { G e n e r a t e h o l e s } T r a v e r s e t h e c r o s s e d g e s l i s t , a L i s t , a n d g e n e r a t e c l o s e d p o l y g o n s ( ther . e may be n o n e , o n e , o r s e v e r a l p o l y g o n s ) , t h e s e p o l y g o n s a r e t h e n s t a c k e d i n l i s t H o l e L i s t ( T Y P E F a c e S e g m e n t ) ; S t e p 7 8 . {Unmarked s egment s } Unmark a l l I n E d g e s , O n E d g e s , a n d O u t E d g e s ; S t e p 7 9 . { G e n e r a t e X i n A } I f I n E d g e s i s e q u a l t o n i l , t h e n go t o s t e p 8 7 , e l s e f e t c h an u n m a r k e d edge f r o m I n E d g e s ; S t e p 8 0 . T r a v e r s e t h e I n E d g e s a n d O n E d g e s l i s t s t o g e n e r a t e a c l o s e d p o l y g o n , m a r k i n g e a c h edge t h a t c o n s t i t u t e s a p a r t o f 36 t h e p o l y g o n ; S t e p 8 1 . I f t h e H o l e L i s t i s e q u a l t o n i l , t h e n go t o s t e p 85, e l s e c o n t i n u e ; S t e p 82. F e t c h a p o l y g o n from t h e H o l e L i s t ; S t e p 83. [Check p o s s i b l e h o l e s } I f t h e p o l y g o n f r o m t h e H o l e L i s t i s i n s i d e t h e g e n e r a t e d p o l y g o n , t h e n merge t h e edges l i s t s t o g e t h e r t o form one p o l y g o n , and d e l e t e t h e p o l y g o n from t h e H o l e L i s t ; S t e p 84. U n l e s s a l l t h e p o l y g o n s f o r t h e H o l e L i s t have been e x a m i n e d , f e t c h t h e n e x t p o l y g o n and go t o s t e p 83, e l s e c o n t i n u e ; S t e p 85. I n s e r t t h e ( r e s u l t i n g ) p o l y g o n t o t h e end of X i n A l i s t ; . S t e p 86. U n l e s s a l l t h e I n E d g e s e d g e s have been marked, f e t c h a n o t h e r unmarked edge and go t o s t e p 80, e l s e c o n t i n u e ; S t e p 87. { G e n e r a t e XoutA} R e p e a t s t e p s 79 t o ' 8 6 w i t h X i n A and I n E d g e s b e i n g r e p l a c e d by X o u t B and O u t E d g e s r e s p e c t i v e l y ( N o t e : t h e OnEdges l i s t may be p a r t i a l l y m a r k e d ) ; S t e p 88. { G e n e r a t e X t y p e l o n A and Xtype2onA} I f OnEdges i s e i t h e r e q u a l t o n i l o r a l l have been marked, t h e n go t o s t e p 93, e l s e f e t c h an unmarked edge f r o m OnEdges ( i n h e r i t e d from a b o v e , may be p a r t i a l l y m a r k e d ) ; S t e p 89. T r a v e r s e t h e OnEdges l i s t s t o g e n e r a t e a c l o s e d p o l y g o n , m a r k i n g e a c h edge t h a t c o n s t i t u t e s a p a r t o f t h e p o l y g o n ; S t e p 90. I f one o f t h e e d g e s o f t h e p o l y g o n i s a s u b s e t of a L i s t , t h e n add t h e p o l y g o n t o X i n A l i s t a nd go t o s t e p 92, 37 e l s e c o n t i n u e ; S t e p 9 1 . { D e c i d e t y p e } I f t h e p o l y g o n ( f a c e s e g m e n t ) i s " T y p e 1", t h e n a d d t h e p o l y g o n t o t h e l i s t X t y p e l o n A , e l s e a d d i t t o t h e l i s t X t y p e 2 o n A ( s e e s e c t i o n 2 . 4 f o r d e f i n i t i o n s o f X t y p e l o n A a n d X t y p e 2 o n A a n d see A p p e n d i x -B f o r an a l g o r i t h m f o r d e c i d i n g " T y p e l " o r " T y p e 2 " " o n " c a s e s ) ; S t e p 9 2 . U n l e s s a l l t h e e d g e s f r o m t h e O n E d g e s l i s t h a v e b e e n m a r k e d , f e t c h t h e n e x t u n m a r k e d e d g e a n d go t o s t e p 8 9 , e l s e c o n t i n u e ; S t e p 9 3 . U n l e s s a l l t h e f a c e s o f p o l y h e d r o n A h a v e b e e n f e t c h e d , g e t t h e n e x t f a c e a n d go t o s t e p 6 6 , e l s e c o n t i n u e ; S t e p 9 4 . R e p e a t s t e p s 64 t o 93 w i t h X i n A , X t y p e l o n A , X t y p e 2 o n A , X o u t A , a n d p o l y h e d r a A a n d B b e i n g r e p l a c e d by X i n B , X t y p e l o n B , X t y p e 2 o n B , X o u t B , a n d p o l y h e d r a B a n d A r e s p e c t i v e l y ; PART V G E N E R A T I N G THE R E S U L T S t e p 9 5 . { F e t c h a l l l i n e s e g m e n t s } D e p e n d i n g on t h e d e s i r e d r e g u l a r i z e d s e t o p e r a t i o n , s e l e c t t h e f a c e s egment l i s t s a c c o r d i n g t o T a b l e I ; S t e p 9 6 . { M e r g i n g } M e r g e a l l s e g m e n t l i s t s t o one l i s t ; S t e p 9 7 . { J o i n f a c e s egment s } F o r t h o s e f a c e s t h a t h a v e a common edge a n d l i e on t h e same p l a n e , merge them i n t o one f a c e ; S t e p 9 8 . { J o i n l i n e s egment s } F o r t h o s e e d g e s e g m e n t s o f a f a c e t h a t h a v e t h e same s p a c e d i r e c t i o n , j o i n them t o g e t h e r t o one 38 l i n e s e g m e n t ; S t e p 9 9 . { G e n e r a t e r e s u l t } T r a v e r s e t h e s e g m e n t s a n d g e n e r a t e c l o s e d p o l y h e d r a ( t h e r e may be n o n e , o n e , o r s e v e r a l p o l y h e d r a ) , t h e s e p o l y h e d r a a r e t h e r e s u l t o f t h e d e s i r e d o p e r a t i o n . 4 . 4 D i s c u s s i o n a n d R e s u l t A l t h o u g h t h e r e a r e many s i m i l a r i t i e s b e t w e e n t h e 2-D a l g o r i t h m a n d t h e 3-D a l g o r i t h m , t h e 3-D v e r s i o n i s more c o m p l i c a t e d . As i n 2 - D , t h e C o h e n - S u t h e r l a n d c l i p p i n g a l g o r i t h m [4] i s u s e d a g a i n i n t h e 3-D a l g o r i t h m f o r e f f i c i e n c y p u r p o s e s . K a l a y ' s [ 7 ] a l g o r i t h m i s u s e d i n d e t e r m i n i n g t h e s p a t i a l c o n t a i n m e n t o f a p o i n t i n a p o l y h e d r o n . The a l g o r i t h m , d e n o t e d " t h e p r o j e c t i o n m e t h o d " , i s o f c o m p l e x i t y 0 ( n ) . In g e n e r a l , t h i s a l g o r i t h m i s an e x t e n s i o n o f t h e 2-D p o i n t - i n - p o l y g o n i n c l u s i o n a l g o r i t h m , a l t h o u g h i t i s more c o m p l i c a t e d . In P a r t I I , t h e s e l f e d g e s o f t h e p o l y h e d r a a r e c l a s s i f i e d f i r s t , a n d t h e s e s e l f e d g e s a r e u s e d t o i n f e r t h e c r o s s edge c l a s s i f i c a t i o n i n P a r t I I I . R e q u i c h a [10 ] c l a i m s t h a t a l l v e r t i c e s o f a l l c r o s s e d g e s l i e i n s e l f e d g e s ; he g i v e s an i n f o r m a l p r o o f f o r t h a t c l a i m . B a s e d on t h i s c l a i m , a l l i n t e r s e c t i o n p o i n t s o f t h e s e l f e d g e s were s a v e d . H e n c e , r e c o m p u t i n g t h e v e r t i c e s was a v o i d e d i n f i n d i n g c r o s s e d g e s . The c r o s s e d g e s a r e o b t a i n e d by u s i n g a f a c e / f a c e i n t e r s e c t i o n c o m p a r i s o n . S i m i l i a r f o r t h e 2-D c a s e , t h e p r o g r a m h a s b e e n r u n on 39 s e v e r a l s e t s o f d a t a a n d by v i s u a l i n s p e c t i o n , t h e r e s u l t s o b t a i n e d a r e c o r r e c t . T h e o u t p u t o f an o p e r a t i o n c a n s e r v e a s i n p u t f o r a n o t h e r o p e r a t i o n . H o w e v e r , t h e a l g o r i t h m c a n g e n e r a t e s e t s t h a t a r e n o t i n i t s d o m a i n , f o r e x a m p l e , p o l y h e d r a w i t h h o l e s . F i g u r e 13 shows a t e s t e d e x a m p l e w i t h an o p e r a t i o n t h a t w o u l d g e n e r a t e a h o l e . A p p e n d i x D c o n t a i n s an e x a m p l e f o r w h i c h i n t e r m e d i a t e r e s u l t s f o r most s t e p s a r e l i s t e d and t h e r e s u l t s o f t h e f o u r o p e r a t i o n s b e t w e e n two p o l y h e d r a A a n d B a r e i l l u s t r a t e d i n F i g u r e 14. B A A - * B F i g u r e 13 . E x a m p l e o f an o p e r a t i o n t h a t g e n e r a t e s an o b j e c t w i t h a h o l e i n i t . A U* B A I * B A - * B F i g u r e 14 . 3-D e x a m p l e . B - * A 41 CHAPTER 5 FUTURE WORK AND CONCLUSION T h e d o m a i n o f t h e p o l y h e d r o n m o d e l l i n g a l g o r i t h m p r e s e n t e d i n t h i s t h e s i s i s n o t r i c h e n o u g h t o c o v e r most m e c h a n i c a l p a r t s a n d t o o l s i n m a n u f a c t u r i n g . H e n c e , t h e r e i s a n e e d t o e x t e n d t h e d o m a i n o f t h i s a l g o r i t h m t o i n c o r p o r a t e h o l e s a n d c u r v e d s u r f a c e s i n o b j e c t s . S u c h an e x t e n s i o n w i l l be p o s s i b l e by u s i n g a b e t t e r r e p r e s e n t a t i o n scheme f o r s o l i d s , w h i l e s t i l l r e t a i n i n g a l a r g e p a r t o f t h e p r e s e n t e d a l g o r i t h m . N u m e r i c a l a c c u r a c y i s o b v i o u s l y p o o r i n t h e c u r r e n t i m p l e m e n t a t i o n due t o memory l i m i t a t i o n s . F o r e x a m p l e , t h e p r o g r a m c a n n o t d i s t i n g u i s h b e t w e e n a l i n e t h a t i s l e v e l a n d an i n c l i n e d l i n e t h a t i s a l m o s t l e v e l . I t may be t r i v i a l i n t h e c u r r e n t i m p l e m e n t a i o n , b u t i n i n d u s t r y , i t i s v e r y i m p o r t a n t b e c a u s e p r e c i s i o n i s c r u c i a l i n d e s i g n a n d m a n u f a c t u r i n g . D u r i n g t h e d e s i g n o f t h e a l g o r i t h m s a n d t h e i r i m p l e m e n t a t i o n , l i t t l e c o n s i d e r a t i o n was g i v e n t o t h e i r o v e r a l l e f f i c i e n c y a n d c o m p l e x i t y . T h u s , t h e s e q u e s t i o n s were n o t e x p l i c i t l y a d d r e s s e d i n t h i s t h e s i s . T h e t h e s i s h a s shown t h a t an ' a l g o r i t h m f o r s o l i d m o d e l l i n g , where t h e d o m a i n c o v e r s a l l p o l y h e d r a c o m p o s e d o f c o n v e x a n d / o r c o n c a v e p o l y g o n s , i s i m p l e m e n t a b l e . 42 R E F E R E N C E S [ 1] B o y s e , J . W . a n d J . E . G i l c h r i s t , " G M S o l i d : I n t e r a c t i v e m o d e l i n g f o r d e s i g n a n d a n a l y s i s o f s o l i d s , " I E E E  C o m p u t e r G r a p h i c s a n d A p p l i c a t i o n s , V o l . 2 , N o . 2 , M a r . 1982 , p p . 2 7 - 4 0 . [ 2] B r o w n , C M . , " P A D L - 2 : A t e c h n i c a l s u m m a r y , " I E E E C o m p u t e r  G r a p h i c s a n d A p p l i c a t i o n s , V o l . 2 , N o . 2 , M a r . 1982, p p . 6 9 - 8 4 . [ 3] H i l l y a r d , R . C . , " T h e b u i l d g r o u p o f s o l i d m o d e l e r s , " I E E E  C o m p u t e r G r a p h i c s a n d A p p l i c a t i o n s , V o l . 2 , N o . 2 , M a r . 1982, p p . 4 3 - 5 2 . [ 4] F o l e y , J . D . a n d A . V a n Dam, " F u n d a m e n t a l s o f I n t e r a c t i v e  C o m p u t e r G r a p h i c s , " A d d i s o n W e s l e y , M e n l o P a r k , 1982 . [ 5] F r a n k l i n , W . R . , " E f f i c i e n t p o l y h e d r o n i n t e r s e c t i o n a n d u n i o n , " P r o c . G r a p h i c s I n t e r f a c e ' 8 2 , p p . 7 3 - 8 0 , T o r o n t o , C a n a d a , May 17-2 1, T 9 8 2 . [ 6] H a c k e r , R . , " C e r t i f i c a t i o n o f a l g o r i t h m 112 : P o s i t i o n o f p o i n t r e l a t i v e t o p o l y g o n , " Comm. C A M , V o l . 5 , A u g . 1962 , p p . 6 0 6 . [ 7] K a l a y , Y . E . , " D e t e r m i n i n g t h e s p a t i a l c o n t a i n m e n t o f a p o i n t i n g e n e r a l p o l y h e d r a , " C o m p u t e r G r a p h i c s & Image  P r o c e s s i n g , V o l . 19, N o . 4, p p . 3 0 3 - 3 3 4 , A u g u s t 1982 . [ 8] M a r k o w s k y , G . a n d M . A . W e s l e y , " F l e s h i n g o u t w i r e f r a m e s , " IBM J . R e s e a r c h a n d D e v e l o p m e n t , V o l . 2 4 , N o . 5 , S e p t . 1980 , p p . 5 9 2 - 5 9 7 . [ 9] M e a g h e r , D . , " G e o m e t r i c m o d e l l i n g u s i n g o c t r e e e n c o d i n g , " C o m p u t e r G r a p h i c s & Image P r o c e s s i n g , V o l . 19, N o . 2 , J u n e 1982 , p p . 1 2 9 - 1 4 7 . [10 ] R e q u i c h a , A . A . G . , " B o o l e a n o p e r a t i o n s on s o l i d s " , A d v a n c e d T o p i c s i n S o l i d M o d e l l i n g , T u t o r i a l N o t e s , S IGGRAPH ' 8 3 , D e t r o i t , M i c h i g a n , J u l y 2 6 , 1983 . 43 [11 ] R e q u i c h a , A . A . G . , " R e p r e s e n t a t i o n s f o r r i g i d s o l i d s : t h e o r y , m e t h o d s , a n d s y s t e m s , " ACM C o m p u t e r S u r v e y s , V o l . 12, N o . ' 4 , D e c . 1980 , p p . 4 3 7 - 4 6 4 . [12] R e q u i c h a , A . A . G . a n d H . B . V o e l c k e r , " S o l i d m o d e l l i n g : A h i s t o r i a l summary a n d c o n t e m p o r a r y a s s e s s m e n t " , I E E E  C o m p u t e r G r a p h i c s & A p p l i c a t i o n s , V o l . 2 , N o . 2, p p . 9-24 , M a r c h 1982 . [13 ] R o s s , R . , " L I G 6 : L a n g u a g e f o r I n t e r a c t i v e G r a p h i c s , U s e r ' s M a n u a l , " D e p a r t m e n t o f E l e c t r i c a l E n g i n e e r i n g , The U n i v e r s i t y o f B r i t i s h C o l u m b i a , V a n c o u v e r , B . C . , 1982 . [ 1 4 ] S h i m r a t , M . , " A l g o r i t h m 112 : P o s i t i o n o f p o i n t r e l a t i v e t o p o l y g o n , " Comm. A C M , V o l . 5 , A u g . 1962 , p p . 4 3 4 . [ 1 5 ] T i l o v e , R . B . , " S e t m e m b e r s h i p c l a s s i f i c a t i o n : A u n i f i e d a p p r o a c h t o g e o m e t r i c i n t e r s e c t i o n p r o b l e m s , " I E E E T r a n s .  C o m p u t e r s , V o l . C - 2 9 , N o . 10, O c t . 1980 , p p . 8 7 4 - 8 8 3 . 44 A P P E N D I X A 2-D POLYGON MODELLING ALGORITHM PROCEDURE A l g o r i t h m 2 D ( r e f e r e n c e , c a n d i d a t e : a P o l y g o n ; VAR I n _ l i s t , O u t _ l i s t , O n _ l i s t 1 , O n _ l i s t 2 : L i n e L i s t ) ; { B a s i c a l g o r i t h m f o r p o l y g o n m o d e l l i n g } VAR v 1 , v 2 , p t 1 , p t 2 , d , c2 : X Y p o i n t ; i n t P o i n t s : a P o l y g o n ; Xmax, X m i n , Ymax, Ymin : R e a l ; c o u n t C a n d , c o u n t R e f : i n t e g e r ; B E G I N { A l g o r i t h m 2 D } G e t P o l y g o n W i n d o w ( r e f e r e n c e , Xmax, X m i n , Ymax, Ymin ) ; { i n i t i a l i z e v a l u e s } I n _ l i s t := n i l ; O u t _ l i s t := n i l ; 0 n _ l i s t 1 := n i l ; 0 n _ l i s t 2 := n i l ; { f o r e a c h edge o f c a n d i d a t e p o l y g o n do t h e f o l l o w i n g } FOR c o u n t C a n d := 1 TO c a n d i d a t e ® . n u m DO B E G I N i n t P o i n t s •:= n i l ; W R I T E L N ; WRITELN( ' P o l y g o n L i n e # c o u n t C a n d : 3 ) ; G e t V e r t i c e s ( c o u n t C a n d , v i , v 2 , c a n d i d a t e ) ; { c h e c k w h e t h e r e d g e c l i p s t h e window o r n o t } IF C l i p p e d ( v 1 . x , v l . y , v 2 . x , v 2 . y , Xmax, X m i n , Ymax, Ymin ) THEN BEGIN { s t o r e e n d p o i n t s o f e d g e ( v l , v 2 ) t o i n t P o i n t s } S t o r e P o i n t ( v 1 , i n t P o i n t s ) ; S t o r e P o i n t ( v 2 , i n t P o i n t s ) ; { F i n d i n t e r s e c t i o n p o i n t s . C o m p a r e t h e c a n d i d a t e edge w i t h e a c h r e f e r e n c e edge } FOR c o u n t R e f := 1 TO r e f e r e n c e @ . n u m DO B E G I N G e t V e r t i c e s C c o u n t R e f , c l , c 2 , r e f e r e n c e ) ; { c h e c k w h e t h e r t h e two e d g e s a r e p a r a l l e l } I F n o t P a r a l l e K c l , c 2 , v 1 , v2 ) THEN { l o c a t e i n t e r s e c t i o n p o i n t } I F L i n e l n t e r s e c t ( c l , c 2 , v i , v 2 , p t1 ) THEN S t o r e P o i n t ( p t 1 , i n t P o i n t s ) E L S E { do n o t h i n g } 45 .{ c h e c k w h e t h e r t h e two e d g e s a r e c o l l i n e a r a n d h a v e a common segment } E L S E IF L i n e O n L i n e ( c i , c 2 , v 1 , v 2 , p t 1 , p t 2 ) THEN { c h e c k on t y p e } IF O n T y p e ( p t 1 , p t 2 , r e f e r e n c e , c a n d i d a t e ) { F o r m on l i s t } THEN F o r m O n L i s t ( p t 1 , p t 2 , O n _ l i s t 1 , i n t P o i n t s ) E L S E F o r m O n L i s t ( p t 1 , p t 2 , O n _ l i s t 2 , i n t P o i n t s ) E N D ; { FOR c o u n t R e f } { F o r m I n _ l i s t a n d 0 . u t _ l i s t } F o r m I n _ O u t L i s t ( r e f e r e n c e , i n t P o i n t s , I n _ l i s t , O u t _ l i s t , O n _ l i s t 1 , O n _ l i s t 2 ) END E L S E { edge t o t a l l y o u t s i d e window => o u t edge } F o r m O u t L i s t ( v 1 , v 2 , O u t _ l i s t ) { I F C l i p p e d } END { FOR c o u n t C a n d } E N D ; { A l g o r i t h m 2 D } A P P E N D I X B D E C I S I O N ALGORITHM " F I N D O N T Y P E " PROCEDURE F i n d O n T y p e ( aSegment : L i n e L i s t ; s o l i d l , s o l i d 2 : P o l y h e d r o n ; VAR O n T y p e l , O n T y p e 2 : F a c e S e g m e n t ) { D e t e r m i n e t h e O n T y p e o f a f a c e segment } VAR p : X Y Z p o i n t ; i n s i d e l , i n s i d e 2 : b o o l e a n ; BEGIN { F i n d O n T y p e } { F i n d a p o i n t t h a t i s s l i g h t l y o f t h e f a c e s e g m e n t } O n e P o i n t ( p , aSegment ) ; { C h e c k i f p i s i n s i d e s o l i d l } IF P t _ i n s i d e _ s o l i d ( p , s o l i d l ) { C h e c k i f p I F P t i n s i d e i s i n s i d e s o l i d C p , s o l i d 2 s o l i d 2 a b o v e t h e s u r f a c e 2 on THEN E L S E THEN E L S E c a s e s i n s i d e 1 i n s i d e 1 i n s i d e 2 i n s i d e 2 } { d e t e r m i n e t y p e 1 o r t y p e I F ( i n s i d e 2 AND i n s i d e l ) OR NOT ( i n s i d e 2 THEN BEGIN { same s i d e => T y p e 1 } S t a c k R e s u l t ( a S e g m e n t , O n T y p e l ) ; WRITELN( ' A d d t o 0 n 1 _ S u r f a c e ' ) END E L S E BEGIN { o p p o s i t e s i d e s => T y p e 2 } S t a c k R e s u l t ( a S e g m e n t , 0 n T y p e 2 ) ; WRITELN( ' A d d t o O n 2 _ S u r f a c e ' ) E N D ; { IF } { P r i n t o u t a S e g m e n t } P r i n t a l K aSegment ) = t r u e = f a l s e ; = t r u e = f a l s e ; OR i n s i d e l E N D ; { F i n d O n T y p e } 47 APPENDIX C 2-D EXAMPLE * * * * * * * * * * * * * * * * * * * * * * * * ECHO INPUT ************************ @@@@@(a@@@@(3(a(a(a@@@@(a(a@@(a(a POLYGON A @@@(a@@@@@@@@@(a(a@@@<a(a(a(a(a(a V e r t i c e s o f p o l y g o n r e a d i n a s f o l l o w s : 0 . 0 0 . 0 1 0 . 0 0 0 . 0 1 0 . 0 0 6 . 0 0 5 . 0 0 6 . 0 0 5 . 0 0 3 . 0 0 6 . 0 0 3 . 0 0 6 . 0 0 2 . 0 0 3 . 0 0 2 . 0 0 3 . 0 0 3 . 0 0 0 . 0 3 . 0 0 @@@@@@@@@@@@(a(a@@@(a(a(a(a(a(3(a POLYGON B @@@@@@@@(a@(i(a(a(a(a(a(a(a@@(a(a@@ V e r t i c e s o f p o l y g o n r e a d i n a s f o l l o w s : 1.50- 3 . 0 0 7 . 5 0 3 . 0 0 7 . 5 0 8 . 0 0 1 . 5 0 8 . 0 0 **************** LINE/POLYGON CLASSIFICATION **************** * * * * * * * * * * * * * * * * * * * * R e f e r e n c e ( A ) * * * * * * * * * * * * * * * * * * * * * * * P o l y g o n L i n e # 1 A d d e d O u t l i n e >>> 0 . 0 0 . 0 1 0 . 0 0 0 . 0 P o l y g o n L i n e # 2 A d d e d O u t l i n e >>> 1 0 . 0 0 0 . 0 1 0 . 0 0 6 . 0 0 P o l y g o n L i n e # 3 A d d e d In L i n e >>> 5 . 0 0 6 . 0 0 7 . 5 0 6 . 0 0 A d d e d Out l i n e >>> 7 . 5 0 6 . 0 0 1 0 . 0 0 6 . 0 0 P o l y g o n L i n e # 4 A d d e d In L i n e >>> 5 . 0 0 3 . 0 0 5 . 0 0 6 . 0 0 P o l y g o n L i n e # 5 A d d e d On l i s t >>> 5 . 0 0 3 . 0 0 6 . 0 0 3 . 0 0 48 P o l y g o n A d d e d L i n e # Out l i n e 6 >>> 6 . 0 0 2 . 0 0 6 . 0 0 3 . 0 0 P o l y g o n A d d e d L i n e # O u t l i n e 7 >>> 6 . 0 0 2 . 0 0 3 . 0 0 2 . 0 0 P o l y g o n A d d e d L i n e # O u t l i n e 8 >>> 3 . 0 0 2 . 0 0 3 . 0 0 3 . 0 0 P o l y g o n A d d e d A d d e d L i n e # On l i s t Out l i n e 9 >>> >>> 1 . 50 0 . 0 3 3 . 0 0 . 0 0 3 . 0 0 1 .50 3 .00 3 . 0 0 P o l y g o n A d d e d L i n e # Out l i n e 1 0 >>> 0 . 0 3 . 0 0 0 . 0 0.0. * * * * * * * * * * * * * * * * L I N E / P O L Y G O N C L A S S I F I C A T I O N * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * C a n d i d a t e ( B ) * * * * * * * * * * * * * * * * * * * * * * P o l y g o n L i n e # 1 A d d e d On l i s t » > 5 . 0 0 3 . 0 0 6 . 0 0 3 . 0 0 A d d e d On l i s t >>> 3 . 0 0 3 . 0 0 1.50 3 . 0 0 A d d e d Out l i n e >>> 3 . 0 0 3 . 0 0 5 . 0 0 3 . 0 0 A d d e d In L i n e >>> 6 . 0 0 3 . 0 0 7 . 5 0 3 . 0 0 P o l y g o n L i n e # 2 A d d e d In L i n e >>> 7 . 5 0 3 . 0 0 7 . 5 0 6 . 0 0 A d d e d Out l i n e >>> 7 . 5 0 6 . 0 0 7 . 5 0 8 . 0 0 P o l y g o n L i n e # 3 A d d e d O u t l i n e >>> 7 . 5 0 8 . 0 0 1.50 8 . 0 0 P o l y g o n L i n e # 4 A d d e d O u t l i n e >>> 1.50 3 . 0 0 1.50 8 . 0 0 * * * * * * * * * * * * * * * * * * * * O P E R A T I O N R E S U L T * * * * * * * * * * * * * * * * * * * * * * @@@@@@(a@<a@(a(a@@@@(a(a(a(a(a(a@@@ A I * B @@@@<a@@@@@@(a@@@@(a(a(a(a(a(a(a(a@ P o l y g o n w i t h v e r t i c e s a s f o l l o w s > > 5 . 0 0 6 . 0 0 5 . 0 0 3 . 0 0 6 . 0 0 3 . 0 0 7 . 5 0 3 . 0 0 7 . 5 0 6 . 0 0 @@@@(a@@@@@@@@@(a@@@(a(a(a(a(a(a(a A U * B @@@@@@@@@@@@(a@@@@(a(a(a(a(a(a(a(a cn © CH) <H> CH* <S) CS) CS> CS) CS) cs> CS* cs) cs> CH) <S) cs) cs) cs) cs> CS) CS) cs) cs) cs* cs* A A A A in cn ? * O o 1 r-l rH rH I—1 o o '4-J CS> tn cn CS* (0 crj cs* cs* cn in CS) CD cu CS) u o cs) •r-l cs) •4-> -U cs* V-J l-l cs) CU <1J CS) > > cs) cs) •C X cs) - P O O O O O O O O •rH • O O O O O O • ? o o 00 ro CO CD CD CD c o cno o o o o o o o >i • • LO LO in in o o rH o o o «- *- r-~ r- o o CU — — 4-) o o o o o cs* • r H o o o o o cs* > cs* CN CM CO CO CO CS) C CS) o cs* Cno o o o o cs* >iO o o o o cs* rH CS) O CD CO CO LO CD CH) QJ CS* A A tn o cs* cs» CS) CS* cs; cs* cs) cs) CH) CS> CH) cs> CH) cs> cs> cs* cs* cs* cs) CS) cs* CSJ cs> cs) CS) I A A in o in co tn cu u u cu > - U O O O O O O O O O O O •rH - o o o o o o o o o • S O o COCOCOCMCNICOCOCDVD c o cno o o o o o o o o o o >i • • i n o o o o i n i n o o r H O O o r - n t o v o w h h o o CS) cs* cs* cs* cs* CSJ cs) cs* cs* CS) CH) cs) CS) CS) CH) CS) CS* CS) CH) cs* CH) CH) CH* CH) CH) Ul fO in cu U In CU > 4 - 1 0 0 0 0 0 0 0 • H O O O O O O O * CO CO CO CO CO VD CO c o cno o o o o o o >iO LO LO LO in o o O co •— Cu. r- r- in in A P P E N D I X D 3-D EXAMPLE * * * * * * * * * * * * * * * * * * * * * * * ECHO INPUT * * * * * * * * * * * * * * * * * * * * * * * ################## SOLID R e f e r e n c e ( A ) ################### V e r t i c e s o f s o l i d r e a d i n a s f o l l o w s : 0- 0 0 1 0 . 0 0 0 0 1 0 . 0 0 5 . 0 0 0 4 . 50 5 . 0 0 0 4 . 50 3 . 0 0 0 6 . 0 0 3 . 0 0 0 6 . 0 0 2 . 5 0 0 3 . 0 0 2 . 5 0 0 3 . 0 0 3 . 0 0 0 0 3 . 0 0 0 0 0 6 . 0 0 1 0 . 0 0 0 6 . 0 0 1 0 . 0 0 5 . 0 0 6 . 00 4 . 5 0 5 . 0 0 6 . 0 0 4 . 5 0 3 . 0 0 6 . 0 0 6 . 0 0 3 . 0 0 6 . 0 0 6 . 00 2 . 5 0 6 . 0 0 3 . 0 0 2 . 5 0 6 . 0 0 3 . 0 0 3 . 0 0 6 . 0 0 0 3 . 0 0 6 . 0 0 E d g e s o f s o l i d r e a d i n a s f o l l o w s : 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1 0 10 1 1 1 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 20 51 11 12 12 13 13 14 1-4 1 5 15 16 16 17 17 18 18 19 19 20 20 1 1 F a c e s o f s o l i d r e a d i n a s f o l l o w s : 1 2 3 4 5 6 7 8 9 1 0 21 22 23 24 25 26 27 28 29 30 1 11 21 12 2 12 22 13 3 13 23 14 4 14 24 15 5 15 25 16 6 16 26 17 7 17 27 18 8 ^ 1 8 28 19 9 19 29' 20 10 20 3 0 1 1 # # # # # # # # # # « # # # # # # S O L I D C a n d i d a t e ( B ) ################### V e r t i c e s o f s o l i d r e a d i n a s f o l l o w s : 2 . 0 0 3 . 0 0 0 7 . 5 0 3 . 0 0 0 7 . 50 4 . 0 0 0 7 . 0 0 4 . 0 0 0 7 . 0 0 6 . 0 0 0 7 . 5 0 6 . 0 0 0 7 . 5 0 8 . 0 0 0 2 . 0 0 8 . 0 0 0 2 . 0 0 3 . 00 4 . 0 0 7 . 5 0 3 . 0 0 4 . 0 0 7 . 5 0 4 . 0 0 •4..00 7 . 0 0 4 . 0 0 4 . 0 0 7 . 0 0 6 . 0 0 4 . 0 0 7 . 5 0 6 . 0 0 4 . 0 0 7 . 5 0 8 . 0 0 4 . 0 0 2 . 0 0 8 . 0 0 4 . 0 0 E d g e s o f s o l i d r e a d i n a s f o l l o w s : 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1 9 1 0 10 1 1 1 1 1 2 12 13 13 14 14 15 15 16 1 6 9 1 9 2 10 3 1 1 4 12 5 13 6 14 7 1 5 8 16 F a c e s o f s o l i d r e a d i n a s f o l l o w s 5 6 7 8 13 14 15 16 1 2 3 4 9 10 1 1 1 2 1 1 7 9 18 2 18 1 0 19 3 1 9 1 1 20 4 20 1 2 21 5 21 1 3 22 6 22 1 4 23 7 23 15 • 24 8 24 1 6 17 ****************** LINE/SOLID COMPARISON ***************** * * * * * * * * * * * * * * * * * * * * * * * R e f e r e n c e * * * * * * * * * * * * * * * * * * * * * * * S o l i d L i n e # 1 A d d e d O u t L i n e > 0 0 0 1 0 . 0 0 0 0-S o l i d L i n e # 2 A d d e d Out L i n e > 1 0 . 0 0 0 0 1 0 . 0 0 5 . 0 0 0 S o l i d L i n e # 3 A d d e d On L i n e > 7 . 0 0 5 . 0 0 0 4 . 5 0 5 . 0 0 0 A d d e d O u t L i n e > 1 0 . 0 0 5 . 0 0 0 7 . 0 0 5 . 0 0 0 S o l i d L i n e # 4 A d d e d On L i n e > 4 . 5 0 5 . 0 0 0 4 . 5 0 3 . 0 0 0 S o l i d L i n e # 5 A d d e d On L i n e > 4 . 5 0 3 . 0 0 0 6 . 0 0 3 . 0 0 0 S o l i d L i n e # 6 A d d e d O u t L i n e > 6 . 0 0 3 . 0 0 0 6 . 0 0 2 . 5 0 0 S o l i d L i n e # 7 A d d e d O u t L i n e > 6 . 0 0 2 . 5 0 0 3 . 0 0 2 . 5 0 0 S o l i d L i n e # 8 A d d e d O u t L i n e > 3 . 0 0 2 . 5 0 0 3 . 0 0 3 . 0 0 0 S o l i d L i n e # 9 53 A d d e d On L i n e > 3 . 0 0 3 . 0 0 0 2 . 0 0 3 . 0 0 0 A d d e d O u t L i n e > 2 . 0 0 3 . 0 0 0 0 3 . 0 0 0 -S o l i d L i n e # 10 A d d e d O u t L i n e > 0 3 . 0 0 0 0 0 0 S o l i d L i n e # 11 A d d e d O u t L i n e > 0 0 0 0 0 6 . 0 0 S o l i d L i n e # 12 A d d e d Out L i n e > 1 0 . 0 0 0 0 1 0 . 0 0 0 6 . 0 0 S o l i d L i n e # 1 3 A d d e d O u t L i n e > 1 0 . 0 0 5 . 0 0 0 1 0 . 0 0 5 . 0 0 6 . 0 0 S o l i d L i n e # 1 4 A d d e d I n L i n e > 4 . 5 0 5 . 0 0 0 4 . 5 0 5 . 0 0 4 . 0 0 A d d e d Out L i n e > 4 . 5 0 5 . 0 0 4 . 0 0 4 . 5 0 5 . 0 0 6 . 0 0 S o l i d L i n e # 15 A d d e d On L i n e > 4 . 5 0 3 . 0 0 0 4 . 5 0 3 . 0 0 4 . 0 0 A d d e d Out L i n e > 4 . 5 0 3 . 0 0 4 . 0 0 4 . 5 0 3 . 0 0 6 . 0 0 S o l i d L i n e # 16 A d d e d On L i n e > 6 . 0 0 3 . 0 0 0 6 . 0 0 3 . 0 0 4 . 0 0 A d d e d Out L i n e > 6 . 0 0 3 . 0 0 4 . 0 0 6 . 0 0 3 . 0 0 6 . 0 0 S o l i d L i n e # 17 A d d e d Out L i n e > 6 . 0 0 2 . 5 0 0 6 . 0 0 2 . 5 0 6 . 0 0 S o l i d L i n e # 18 A d d e d Out L i n e > 3 . 0 0 2 . 5 0 0 3 . 0 0 2 . 5 0 6 . 0 0 S o l i d L i n e # 19 A d d e d On L i n e > 3 . 0 0 3 . 0 0 0 3 . 0 0 3 . 0 0 4 . 0 0 A d d e d Out L i n e > 3 . 0 0 3 . 0 0 4 . 0 0 3 . 0 0 3 . 0 0 6 . 0 0 S o l i d L i n e # 20 A d d e d Out L i n e > 0 3 . 0 0 0 0 3 . 0 0 6 . 0 0 S o l i d L i n e # 21 A d d e d Out L i n e > 0 0 6 . 0 0 1 0 . 0 0 0 6 . 0 0 S o l i d L i n e # 22 A d d e d O u t L i n e > 1 0 . 0 0 0 6 . 0 0 1 0 . 0 0 5 . 0 0 6 . 0 0 S o l i d L i n e # 23 A d d e d O u t L i n e > 1 0 . 0 0 5 . 0 0 6 . 0 0 4 . 5 0 5 . 0 0 6 . 0 0 S o l i d L i n e # 24 A d d e d Out L i n e > 4 . 5 0 5 . 0 0 6 . 0 0 4 . 5 0 3 . 0 0 6 . 0 0 S o l i d L i n e # 25 A d d e d Out L i n e > 4 . 5 0 3 . 0 0 6 . 0 0 6 . 0 0 3 . 0 0 6 . 0 0 54 S o l i d L i n e # 26 A d d e d Out L i n e > 6 .00 3 . 0 0 6 . 0 0 6 . 0 0 2 . 50 6 . 00 S o l i d L i n e # 27 A d d e d Out L i n e > 6 .00 2 .50 6 . 0 0 3 . 00 2 . 50 6 . 00 S o l - i d L i n e # 28 A d d e d O u t L i n e > 3 .00 2 . 5 0 6 . 0 0 3 . 0 0 3 . 0 0 6 . 00 S o l i d L i n e # 29 A d d e d O u t L i n e > 3 .00 3 . 0 0 6 . 0 0 0 3 . 0 0 6 . 00 S o l i d L i n e # 30 A d d e d O u t L i n e > 0 3 . 0 0 6 . 0 0 0 0 6 . 00 ****************** . L I N E / S O L I D COMPARISON ***************** *********************** C a n d i d a t e *********************** S o l i d L i n e # 1 A d d e d On L i n e > 4 . 50 3 . 0 0 0 6 . 0 0 3 . 0 0 0 A d d e d On L i n e > 2 .00 3 . 0 0 0 3 . 0 0 3 .00 0 A d d e d On L i n e > 6 .00 3 . 0 0 0 7 . 50 3 .00 0 A d d e d Out L i n e > 3 .00 3 . 0 0 0 - 4 . 50 3 . 0 0 0 S o l i d L i n e # 2 A d d e d On L i n e > 7 . 50 3 . 0 0 0 7 . 50 4 . 0 0 0 S o l i d L i n e # 3 A d d e d On L i n e > 7 . 50 4 . 0 0 0 7 . 00 4 .00 0 S o l i d L i n e # 4 A d d e d On L i n e > 7 . 00 4 . 00 0 7 . 00 5 .00 0 A d d e d Out L i n e > 7 .00 5 . 0 0 0 7 . 0 0 6 .00 0 S o l i d L i n e # 5 A d d e d Out L i n e > 7 . 0 0 6 . 0 0 0 7 . 50 6 .00 0 S o l i d L i n e # 6 A d d e d Out L i n e > 7 .50 6 . 0 0 •0 7 . 50 8 . 0 0 0 S o l i d L i n e # 7 A d d e d Out L i n e > 7 . 50 8 . 00 0 2 . 0 0 8 . 0 0 0 S o l i d L i n e # 8 A d d e d O u t L i n e > 2 . 0 0 8 . 0 0 0 2 . 0 0 3 . 0 0 0 S o l i d L i n e # 9 A d d e d On L i n e > 4 .50 3 . 0 0 4 . 0 0 6 . 0 0 3 .00 4 . 00 A d d e d On L i n e > 2 . 0 0 3 . 0 0 4 . 0 0 3 .00 3 .00 4 . 00 A d d e d Out L i n e > 3 .00 3 .00 4 . 0 0 4 .50 3 .00 4 . 00 A d d e d In L i n e > 6 .00 3 .00 4 . 0 0 7 . 50 3 .00 4 . 00 S o l i d L i n e # 10 55 A d d e d I n L i n e > 7 . 5 0 3 . 0 0 4 . 0 0 7 . 5 0 4 . 0 0 4 . 0 0 S o l i d L i n e # 11 A d d e d I n L i n e > 7 . 5 0 4 . 0 0 4 . 0 0 S o l i d L i n e # 12 A d d e d I n L i n e > A d d e d O u t L i n e > S o l i d L i n e # 13 A d d e d O u t L i n e > S o l i d L i n e # 14 A d d e d O u t L i n e > S o l i d L i n e # 1 5 A d d e d O u t L i n e > S o l i d L i n e # 16 A d d e d O u t L i n e > S o l i d L i n e # 17 A d d e d On L i n e > S o l i d L i n e # 18 A d d e d I n L i n e > S o l i d L i n e # 19 A d d e d I n L i n e > S o l i d L i n e # 20 A d d e d I n L i n e > S o l i d L i n e # 21 A d d e d O u t L i n e > S o l i d L i n e # 22 A d d e d O u t L i n e > S o l i d L i n e # 23 A d d e d O u t L i n e > S o l i d L i n e # 24 A d d e d O u t L i n e > 7 . 0 0 4 . 0 0 4 . 0 0 7 . 0 0 5 . 0 0 4 . 0 0 7 . 0 0 6 . 0 0 4 . 0 0 7 . 5 0 6 . 0 0 4 . 0 0 7 . 5 0 8 . 0 0 4 . 0 0 2 . 0 0 8 . 0 0 4 . 0 0 2 . 0 0 3 . 0 0 0 7 . 5 0 3 . 0 0 0 7 . 5 0 4 . 0 0 0 7 . 0 0 - 4 . 0 0 0 7 . 0 0 6 . 0 0 0 7 . 5 0 6 . 0 0 0 7 . 5 0 8 . 0 0 0 2 . 0 0 8 . 0 0 0 7 . 0 0 4 . 0 0 4 . 0 0 7 . 0 0 5 . 0 0 4 . 0 0 7 . 0 0 6 . 0 0 4 . 0 0 7 . 5 0 6 . 0 0 4 . 0 0 7 . 5 0 8 . 0 0 4 . 0 0 2 . 0 0 8 . 0 0 4 . 0 0 2 . 0 0 3 . 0 0 4 . 0 0 2 . 0 0 3 . 0 0 4 . 0 0 7 . 5 0 3 . 0 0 4 . 0 0 7 . 5 0 4 . 0 0 4 . 0 0 7 . 0 0 4 . 0 0 4 . 0 0 7 . 0 0 6 . 0 0 4 . 0 0 7 . 5 0 6 . 0 0 4 . 0 0 7 . 5 0 8 . 0 0 4 . 0 0 2 . 0 0 8 . 0 0 4 . 0 0 * * * * * * * * * * * * * * * * * * * * F IND CROSS EDGES * * * * * * * * * * * * * * * * * * * * A d d e d On L i n e > A d d e d On L i n e > A d d e d On L i n e > 7 . 0 0 5 . 0 0 4 . 0 0 4 . 5 0 3 . 0 0 4 . 0 0 7 . 0 0 5 . 0 0 0 4 . 5 0 5 . 0 0 4 . 0 0 4 . 5 0 5 . 0 0 4 . 0 0 7 . 0 0 5 . 0 0 4 . 0 0 ******************** ********************* GENERATING F A C E S * * * * * * * * * * * * * * * * * * * * * * R e f e r e n c e * * * * * * * * * * * * * * * * * * * * * * * F a c e # 1 A d d t o Out S u r f a c e 0 0 0 10. 00 0 0 1 0 . 0 0 0 0 10 . 00 5 . 00 0 1 0 . 0 0 5 . 0 0 0 7 . 00 5 . 00 0 7 . 0 0 4 . 0 0 0 7 . 00 5 . 00 0 7 . 5 0 4 . 0 0 0 7 . 00 4 . 00 0 7 . 5 0 3 . 0 0 0 7 . 50 4 . 00 0 6 . 0 0 3 . 0 0 0 7 . 50 3 . 00 0 6 . 0 0 3 . 0 0 0 6 . 00 2 . 50 0 6 . 0 0 2 . 5 0 0 3 . 00 2 . 50 0 3 . 0 0 2 . 5 0 0 3 . 00 3 . 00 0 3 . 0 0 3 . 0 0 0 2 . 00 3 . 00 0 2 . 0 0 3 . 0 0 0 0 3 . 00 0 0 3 . 0 0 0 • 0 0 0 A d d t o On1 S u r f a c e 7 . 0 0 5 . 0 0 0 4 . 50 5 . 00 0 4 . 5 0 5 . 0 0 0 4 . 50 3 . 00 0 4 . 50 3 . 0 0 0 6 . 00 3 . 00 0 6 . 0 0 3 . 0 0 0 7 . 50 3 . 00 0 7 . 5 0 3 . 0 0 0 7 . 50 4 . 00 . 0 7 . 5 0 4 . 0 0 0 7 . 00 4 . 00 0 7 . 0 0 4 . 0 0 0 7 . 00 5 . 00 0 F a c e # 2 A d d t o Out S u r f a c e 0 0 6 . 0 0 10. 00 0- 6 . 00 1 0 . 0 0 0 6 . 0 0 10. 00 5 . 00 6 . 00 1 0 . 0 0 5 . 0 0 6 . 0 0 4 . 50 5 . 00 6 . 00 4 . 5 0 5 . 0 0 6 . 0 0 4 . 50 3 . 00 6 . 00 4 . 5 0 3 . 0 0 6 . 0 0 6 . 00 3 . 00 6 . 00 6 . 0 0 3 . 0 0 6 . 0 0 6 . 00 2 . 50 6 . 00 6 . 0 0 2 . 5 0 6 . 0 0 3 . 00 2 . 50 6 . 00 3 . 0 0 2 . 5 0 6 . 0 0 3 . 00 3 . 00 6 . 00 3 . 0 0 3 . 0 0 6 . 0 0 0 3 . 00 '6. 00 0 3 . 0 0 6 . 0 0 0 0 6 . 00 F a c e # 3 A d d t o O u t S u r f a c e 0 0 0 10 . 00 0 0 1 0 . 0 0 . 0 0 10 . 00 0 6 . 00 0 0 6 . 0 0 10 . 00 0 6 . 00 0 0 0 0 0 6 . 00 F a c e # 4 A d d t o Out S u r f a c e 1 0 . 0 0 0 0 10 . 00 5 . 00 0 1 0 . 0 0 5 . 0 0 0 10. 00 5 . 00 6 . 00 1 0 . 0 0 0 6 . 0 0 10. 00 5 . 00 6 . 00 1 0 . 0 0 0 0 10 . 00 0 6 . 00 F a c e # 5 A d d t o I n S u r f a c e 4 . 5 0 5 . 0 0 0 4 . 50 5 . 00 4 . 00 7 . 0 0 5 . 0 0 4 . 0 0 4 . 50 5 . 00 4 . 00 7 . 0 0 5 . 0 0 0 7 . 00 5 . 00 4 . 00 7 . 0 0 5 . 0 0 0 4 . 50 5.' 00 0 A d d t o Out S u r f a c e 1Q.00 5 . 0 0 0 7 . 00 5 . 00 0 7 . 0 0 5 . 0 0 0 7 . 00 5 . 00 4 . 00 7 . 0 0 5 . 0 0 4 . 0 0 4 . 50 5 . 00 4. 00 4 . 50 5 . 0 0 4 . 0 0 4 . 50 5 . 00 6. 00 1 0 . 0 0 5 . 0 0 6 . 0 0 4 . 50 5 . 00 6 . 00 1 0 . 0 0 5 . 0 0 0 10. 00 5 . 00 6. 00 F a c e # 6 A d d t o In S u r f a c e 4 . 50 5 . 0 0 0 4 . 50 5 . 00 4. 00 4 . 5 0 3 . 0 0 4 . 0 0 4 . 50 5 . 00 4. 00 4 . 50 3 . 0 0 0 4 . 50 3 . 00 4. 00 4 . 5 0 5 . 0 0 0 4 . 50 3 . 00 0 A d d t o Out S u r f a c e 4 . 5 0 5 . 0 0 4 . 0 0 4 . 50 5 . 00 6 . 00 4 . 5 0 5 . 0 0 6 . 0 0 4 . 50 3 . 00 6. 00 4 . 50 3 . 0 0 4 . 0 0 4 . 50 3 . 00 6 . 00 4 . 50 3 . 0 0 . 4 . 0 0 4 . 50 5 . 00 4 . 00 F a c e # 7 • A d d t o O u t S u r f a c e 4 . 5 0 3 . 0 0 4 . 0 0 4 . 50 3 . 00 6 . 00 4 . 5 0 3 . 0 0 6 . 0 0 6 . 00 3 . 00 6. 00 6 . 0 0 3 . 0 0 4 . 0 0 6 . 00 3 . 00 6 . 00 4 . 5 0 3 . 0 0 4 . 0 0 6 . 00 3 . 00 4 . 00 A d d t o On 1 S u r f a c e „ 4 . 5 0 3 . 0 0 0 6 . 00 3 . 00 0 6 . 0 0 3 . 0 0 0 6 . 00 3 . 00 4 . 00 4 . 5 0 3 . 0 0 4 . 0 0 6 . 00 3 . 00 4 . 00 4 . 5 0 3 . 0 0 0 4 . 50 3 . 00 4. 00 F a c e # 8 A d d t o O u t S u r f a c e 6 . 0 0 3 . 0 0 0 6 . 00 . 2 . 50 0 6 . 0 0 2 . 5 0 0 6 . 00 2 . 50 6 . 00 6 . 0 0 3 . 0 0 6 . 0 0 6 . 00 2 . 50 6 . 00 6 . 0 0 3 . 0 0 ' 4 . 0 0 6 . 00 3 . 00 6 . 00 6 . 0 0 3 . 0 0 0 6 . 00 3. 00 4 . 00 F a c e # 9 A d d t o O u t S u r f a c e 6 . 0 0 2 . 5 0 0 3 . 00 2 . 50 0 3 . 0 0 2 . 5 0 0 3 . 00 2 . 50 6. 00 6 . 0 0 2 . 5 0 6 . 0 0 3 . 00 2 . 50 6 . 00 6 . 0 0 2 . 5 0 0 6. 00 2 . 50 6 . 00 F a c e # 1 0 A d d t o Out S u r f a c e 3 . 0 0 2 . 5 0 0 3 . 00 3 . 00 0 3 . 0 0 3 . 0 0 0 3 . 00 3 . 00 4. 00 3 . 0 0 3 . 0 0 4 . 0 0 3 . 0 0 2 . 5 0 6 . 0 Q 3 . 0 0 2 . 5 0 0 3 . 0 0 3 . 0 0 6 . 0 0 3 . 0 0 3 . 0 0 6 . 0 0 3 . 0 0 2 . 5 0 6 . 0 0 F a c e # 11 A d d t o O u t S u r f a c e 2 . 0 0 3 . 0 0 0 0 3 . 0 0 0 0 3 . 0 0 0 0 3 . 0 0 6 . 00 3 . 0 0 3 . 0 0 6 . 0 0 0 3 . 0 0 6 . 00 3 . 0 0 3 . 0 0 4 . 0 0 3 .00 3 . 0 0 6 . 00 2 . 0 0 3 . 0 0 4 . 0 0 3 . 0 0 3 . 0 0 4 . 00 2 . 0 0 3 . 0 0 0 2 . 00 3 . 0 0 4 . 00 A d d t o On2 S u r f a c e 3 . 00 3 . 00 0 2 . 00 3 . 0 0 0 2 . 0 0 3 .00 0 2 . 00 3 .00 4 . 00 , 2 . 0 0 3 . 0 0 4 . 0 0 3 . 0 0 3 . 0 0 4 . 00 3 . 0 0 3 . 0 0 0 3 . 0 0 3 .00 4 . 00 F a c e # 12 A d d t o O u t _ S u r f a c e 0 3 . 0 0 0 0 0 0 0 0 0 0 0 6 . 0 0 0 3 . 0 0 6 . 0 0 0 0 6 . 0 0 0 3 . 0 0 0 0 3 . 0 0 6 . 0 0 * * * * * * * * * * * * * * * * * * * * G E N E R A T I N G F A C E S * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * C a n d i d a t e * * * * * * * * * * * * * * * * * * * * * * * F a c e # 1 ' A d d t o O u t S u r f a c e 3 . 0 0 3 . 00 0 4 . 5 0 3 . 0 0 0 4 . 5 0 5 . 0 0 0 4 . 5 0 3 . 00 0 7 . 00 5 . 0 0 0 4 . 5 0 5 . 0 0 0 7 . 0 0 5 . 0 0 0 7 . 0 0 6 . 0 0 0 7 . 0 0 6 . 0 0 0 7 . 5 0 6 . 0 0 0 7 . 5 0 6 . 0 0 0 7 . 5 0 8 . 0 0 0 7 . 5 0 8 . 0 0 0 2 . 0 0 8 . 0 0 0 2 . 0 0 8 . 0 0 0 2 . 0 0 3 . 0 0 0 2 . 0 0 3 . 0 0 0 3 . 0 0 3 . 0 0 0 A d d t o On1 : S u r f a c e 4 . 5 0 3 . 0 0 0 6 . 0 0 3 . 0 0 0 6 . 0 0 3 . 0 0 0 7 . 5 0 3 . 0 0 0 7 . 5 0 3 . 0 0 0 7 . 5 0 4 . 0 0 0 7 . 50 4 . 0 0 0 7 . 0 0 4 . 0 0 0 7 . 0 0 4 . 0 0 0 7 . 0 0 5 . 0 0 0 7 . 0 0 5 . 0 0 0 4 . 5 0 5 . 0 0 0 4 . 5 0 5 . 0 0 0 4 . 5 0 3 . 0 0 0 F a c e # 2 A d d t o I n _ S u r f a c e 6 . 0 0 3 .00 . 4 . 0 0 7 . 5 0 3 . 0 0 4 . 0 0 7 . 5 0 4 . 0 0 4 . 0 0 7 . 0 0 4 . 0 0 4 . 0 0 7 . 5 0 3 . 0 0 4 . 0 0 7 . 5 0 4 . 0 0 4 . 0 0 7 . 0 0 4 . 0 0 4 . 0 0 7 . 0 0 5 . 0 0 4 . 0 0 7 . 0 0 5 . 0 0 4 . 0 0 4 . 50 5 . 00 4 . 00 4 . 5 0 3 . 0 0 4 . 0 0 4. 50 5 . 00 4 . 00 4 . 50 3 . 0 0 4 . 0 0 6 . 00 3 . 00 4 . 00 A d d t o Out S u r f a c e 3 . 0 0 3 . 0 0 4 . 0 0 4 . 50 3 . 00 4 . 00 4 . 5 0 3 . 0 0 4 . 0 0 4 . 50 5 . 00 4 . 00 7 . 0 0 5 . 0 0 4 . 0 0 4 . 50 5 . 00 4 . 00 7 . 0 0 5 . 0 0 4 . 0 0 7 . 00 6 . 00 4 . 00 7 . 0 0 6 . 0 0 4 . 0 0 7 . 50 6 . 00 4 . 00 7 . 5 0 6 . 0 0 4 . 0 0 7 . 50 8 . 00 4 . 00 7 . 50 8 . 0 0 4 . 0 0 2 . 00 8 . 00 4 . 00 2 . 0 0 8 . 0 0 4 . 0 0 2 . 00 3 . 00 4 . 00 2 . 0 0 3 . 0 0 4 . 0 0 3 . 00 3 . 00 4 . 00 F a c e # 3 A d d t o In S u r f a c e 6 . 0 0 3 . 0 0 4 . 0 0 7 . 50 3 . 00 4 . 00 7 . 50 3 . 0 0 0 7 . 50 3 . 00 4 . 00 6 . 0 0 ' 3 . 0 0 0 7 . 50 3 . 00 0 6 . 0 0 3 . 0 0 0 6 . 00 3 . 00 4 . 00 A d d t o O u t S u r f a c e 3 . 0 0 3 . 0 0 0 4 . 50 3 . 00 0 4 . 5 0 3 . 0 0 0 4 . 50 3 . 00 4 . 00 3 . 0 0 3 . 0 0 4 . 0 0 4 . 50 3 . 00 4 . 00 3 . 00 3 . 0 0 0 3. 00 3 . 00 4 . 00 A d d t o O n l S u r f a c e 4 . 5 0 3 . 0 0 0 >6. 00 3 . 00 0 6 . 0 0 3 . 0 0 0 6 . 00 3 . 00 4 . 00 4 . 50 3 . 0 0 4 . 0 0 6 . 00 3 . 00 4 . 00 4 . 50 3 . 0 0 0 - 4 . 50 3 . 00 4 . 00 A d d t o On2 S u r f a c e 2 . 0 0 3 . 0 0 0 3 . 00 3 . 00 0 3 . 0 0 3 . 0 0 0 3 . 00 3 . 00 4 . 00 2 . 0 0 3 . 0 0 4 . 0 0 3 . 00 3 . 00 4. 00 2 . 0 0 3 . 0 0 0 2 . 00 3 . 00 4 . 00 F a c e # 4 A d d t o I n S u r f a c e 7 . 5 0 3 . 0 0 0 7 . 50 3 . 00 4 . 00 7 . 50 3 . 0 0 4 . 0 0 7 . 50 4 . 00 4 . 00 7 . 5 0 4 . 0 0 0 7 . 50 4 . 00 4 . 00 7 . 5 0 3 . 0 0 0 7 . 50 4 . 00 0 F a c e # 5 A d d t o In S u r f a c e 7 . 5 0 4 . 0 0 0 7 . 50 4 . 00 4 . 00 7 . 5 0 4 . 0 0 4 . 0 0 7 . 00 4 . 00 4 . 00 7 . 0 0 4 . 0 0 0 7 . 00 4 . 00 4 . 00 7 . 5 0 4 . 0 0 0 7 . 00 4 . 00 0 F a c e # 6 A d d t o I n S u r f a c e 7 . 0 0 4 . 0 0 0 7 . 00 4 . 00 4 . 00 7 . 0 0 4 . 0 0 4 . 0 0 7 . 00 5 . 00 4 . 00 60 7 . 0 0 5 . 0 0 0 7 . 00 5 . 00 4 .00 7 . 0 0 4 . 0 0 0 • 7 . 00 5 . 00 0 A d d t o O u t S u r f a c e 7 . 0 0 5 . 0 0 0 7 .00 6 . 00 0 7 . 0 0 6 . 0 0 0 7 . 00 6 . 00 4 .00 7 . 0 0 5 . 0 0 4 . 0 0 7 .00 6 . 00 4 .00 7 . 0 0 5 . 0 0 0 7 . 00 5 . 00 4 .00 F a c e # 7 A d d t o O u t S u r f a c e 7 . 0 0 6 . 0 0 0 7 . 50 6 . 00 0 7 . 5 0 6 . 0 0 0 7 . 50 6 . 00 4 .00 7 . 0 0 6 . 0 0 4 . 0 0 7 . 50 6 . 00 4 .00 7 . 0 0 6 . 0 0 0 7 . 00 6 . 00 4 .00 F a c e # 8 A d d t o Out S u r f a c e 7 . 5 0 6 . 0 0 0 7 . 50 8 . 00 0 7 . 50 8 . 0 0 0 7 . 50 8 . 00 4 .00 7 . 5 0 6 . 0 0 4 . 0 0 7 . 50 8 . 00 4 . 00 7 . 5 0 6 . 0 0 0 7 . 50 6 . 00 4 .00 F a c e # 9 A d d t o Out S u r f a c e -7 . 5 0 8 . 0 0 0 2 . 0 0 8 . 00 0 2 . 0 0 8.00- 0 2 . 00 8 . 00 4 .00 7 . 5 0 8 . 0 0 4 . 0 0 2 . 0 0 8 . 00 4 .00 7 . 5 0 8 . 0 0 0 7 . 50 8 . 00 4 .00 F a c e # 10 A d d t o O u t S u r f a c e 2 . 0 0 8 . 0 0 0 2 . 00 3 . 00 0 2 . 0 0 3 . 0 0 0 2 . 0 0 3 . 00 4 .00 2 . 0 0 8 . 0 0 4 . 0 0 2 . 00 3 . 00 4 .00 2 . 0 0 8 . 0 0 0 2 . 00 8 . 00 4 .00 * * * * * * * * * * * * * * * * * * * * O P E R A T I O N R E S U L T * * * * * * * * * * * * * * * * * * * * ######################### A I * B ######################### 1 2 4 . 5 0 3 . 0 0 4 . 0 0 7 . 5 0 3 . 0 0 4 . 0 0 7 . 5 0 4 . 0 0 4 . 0 0 7 . 0 0 4 . 0 0 4 . 0 0 7 . 0 0 5 . 0 0 4 . 0 0 4 . 5 0 5 . 0 0 4 . 0 0 7 . 5 0 3 . 0 0 0 4 . 5 0 3 . 0 0 0 7 . 5 0 4 . 0 0 0 7 . 0 0 4 . 0 0 0 7 . 0 0 5 . 0 0 0 4 . 5 0 5 . 0 0 0 18 - ' to NJOWCTiOOOMKJ-J^I^I'gOAuJLJ o o o o o o o o o o o o c n c n o o o o o o o o o o o o WWWWUlOOWCDCBC^CriUlljOOJ OOUIUIO o o o o o o o o o o o o o o o o o o o o o k C » O O O 0 O O O 0 0 0 O O 0 O O o =8= =8= =8= =8= =8= =t= 41= =8= =8= =8= =8= =8= =8= =8= =»= * =8= =8= =8= =8= =8= =8= =8= =8= =8= a * 03 =8= =8= =8= =tt= =8= =«= =8= =8= =t4= =8= =8= =8= =8= =8= =8= =8= =8= =8= =8= =8= =8= =t= =8= =8= - J cr\ o~\ ro o -» co —* —» —» —» _» _ . <Ti ip» ip» it=. if* it* 4=. CTi M—'MO^iX)0^iJjCDCX>-^-*tn>fc»toro—' c x > c n c n * > - c o r o ~ j r o c o v D i f ^ i f ^ r o o c o o o — ' co tn to ^ ix> >£» to tn tn cn W W I\) —» M N > N ) t O — — — — — — ^ _. _ cn C D - v j c r i M - ' O c i i i i j ^ u i i ^ c o c r i o i N J ^ o i i D v j ^ c r i y D i ^ w w M W U i m o o w w w o o o o o i o i u i u i w o o c n c n o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o cn o o o o o o o o c n o o o c n c n o o c n c n o o o o o o o o o o c o r o c o - ^ o o o - ^ i c r i c n ^ r o cncncricr\cnchcncncr\o^ o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 28 29 24 30 31 32 33 1 0 9 1 1 1 7 1 2 1 3 1 1 4 23 1 5 18 1 4 1 8 1 5 6 1 4 2 4 3 4 4 4 5 4 6 1 0 34 4 7 4 8 6 9 4 46 4 1 0 4 1 1 4 1 2 6 1 3 4 1 4 29 25 30 31 32 33 26 27 26 28 29 30 31 32 33 32 23 2 3 4 5 6 7 8 16 17 18 19 20 21 22 23 24 25 26 27 28 18 29 30 19' 28 31 20 30 32 21 31 33 22 32 35 36 37 27 38 39 40 43 34 44 45 35 43 29 17 46 36 45 37 26 16 47 38 25 48 39 47 49 40 48 50 41 51 52 33 44 42 50 41= =41= -» =tt= i*=> — " VO —' O r O — . 4 1 = .!> 4=> CO 00 W 0 0 s l C T \ i ^ 0 1 ^ r 0 0 > 0 1 i ^ 0 J N ) N ) O U ) 0 0 v l ^ 0 ^ =41= 44= - - - - - - o o i o i o o u i o i o o u i m o o u i u i o =44= VO O W O O O O O O O O O O O O O O O O =H= - . - . ^ ^ ^ - ^ ^ ^ - ^ . ^ - ^ ^ ^ ^ - - O M n ^ w w i o o v o o v e n ^ O J ^ - ' O - O O V I C T I O I O J W N ) =44= —- —• =44= t O VD —* CO =41= rocDmcTiononojwooroo^moi =«= =tt= r o — -» 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 =«= o o o r o ^ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 =41= =14= =tt= — =44= CO ui • =4t= rf=,rf^i(i.ji.*i^a^rfi.oooooooo =«= =44= —- O O O O O O O O =44= M ^ C T i O O O O O O O O =44= =14= c n ^1 > I —' * cn co 03 =44= =44= =44= =rt= =44= =41= =44= =4t= =41= =4t= =44= =44= =41= =44= =44= =44= =14= =14= =44= =14= =41= =«= =41= =14= =41= cn >p=. o cn m o cn cn o o o o o o o o o o o o u i u i o o o o o o o o o o O O O O U I U I O O O O O O O O O O O O O O UD-~JCTiUl>'>tf=-<jOK> fr^UWUUlWUUWNWWCnWOOUUWNUUiP^OltllOO O O O O O O O O O U I U I O O O O O O O O O O O O O O O O O O O o o c n u i o o o o o o O O O O O O O O O O > * = » > 4 = » ^ i i > ^ i * = » i * = » C T ^ o ^ o ^ o ^ c h o ^ c n o ^ o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o =tt= =44= =tt= =44= =(4= =8= =4t= =4t= =B= 44= =44= =44= =44= =44= =44= =44= =44= =44= =44= =44= =44= =44= =4t= =44= =44= ro r o »4> 4=» co —i u i >f=» >(=» >t=> >£=• ip» -» oo o O l t o CO r o CO Ul r o ro ro r o r o ro — VO to I * > =44= =44= =44= =44= =4t= =44= =44= =14= =44= =44= =14= =44= =44= =44= =tt= =44= =4t= =44= =44= =14= =44= =44= =44= =44= =44= Ul 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 20 21 22 2 1 3 4 23 24 25 25 26 25 9 8 1 0 1 1 1 2 25 27 28 29 26 7 8 6 • 5 1 7 1 2 1 1 0 1 3 4 1 4 2 6 3 4 28 4 29 4 1 0 1 1 1 2 1 1 4 1 5 1 6 1 7 18 1 9 20 21 22 1 3 1 4 1 3 1 5 23 24 1 6 17 24 18 26 1 9 18 20 21 22 27 28 29 23 27 27 26 28 29 2 3 4 14 15 16 23 13 24 25 14 23 26 27 28 16 29 30 17 31 32 5 6 7 18 7 8 9 10 9 20 21 22 15 25 8 33 18 34 4 9 35 19 33 4 10 36 20 35 4 11 37 21 36 4 12 24 22 37 6 38 39 40 41 4 42 43 7 44 ' 4 43 39 45 6 4 45 40 46 5 4 46 41 26 4 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items