UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Displaying human visual field data as shaded surfaces Jankowski, Richard 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_A7 J35.pdf [ 11.96MB ]
Metadata
JSON: 831-1.0096282.json
JSON-LD: 831-1.0096282-ld.json
RDF/XML (Pretty): 831-1.0096282-rdf.xml
RDF/JSON: 831-1.0096282-rdf.json
Turtle: 831-1.0096282-turtle.txt
N-Triples: 831-1.0096282-rdf-ntriples.txt
Original Record: 831-1.0096282-source.json
Full Text
831-1.0096282-fulltext.txt
Citation
831-1.0096282.ris

Full Text

DISPLAYING HUMAN VISUAL FIELD DATA AS SHADED SURFACES by RICHARD JANKOWSKI B.Eng., M c G i l l U n i v e r s i t y , 1979 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE i n THE FACULTY OF GRADUATE STUDIES 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 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 UNIVERSITY OF BRITISH COLUMBIA A p r i l 1984 © R i c h a r d J a n k o w s k i , 1984 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f t h e r e q u i r e m e n t s f o r an a d v a n c e d d e g r e e a t t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , I a g r e e t h a t t h e L i b r a r y s h a l l make i t f r e e l y a v a i l a b l e f o r r e f e r e n c e and s t u d y . I f u r t h e r a g r e e t h a t p e r m i s s i o n f o r e x t e n s i v e c o p y i n g of' t h i s t h e s i s f o r s c h o l a r l y purposeScjnay be g r a n t e d by t h e Head o f my D e p a r t m e n t o r by h i s o r h e r r e p r e s e n t a t i v e s . I t i s u n d e r s t o o d t h a t c o p y i n g o r p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l g a i n s h a l l n o t be a l l o w e d w i t h o u t my w r i t t e n p e r m i s s i o n . D e p a r t m e n t 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 of B r i t i s h C o l u m b i a 2075 Wesbrook P l a c e V a n c o u v e r , Canada V6T 1W5 D a t e : 2 A p r i l 1984 i i A b s t r a c t Human v i s u a l f i e l d d a t a c o l l e c t e d by k i n e t i c t h r e s h o l d p e r i m e t r y a r e t h r e e - d i m e n s i o n a l , and e a r l y e f f o r t s a t g r a p h i c a l p r e s e n t a t i o n have not been e f f e c t i v e i n c o n v e y i n g t h e b e h a v i o u r of t h e d a t a . The a p p r o a c h t a k e n h e r e i n i m p r o v e s upon t h e s e e a r l i e r r e n d i t i o n s by d i s p l a y i n g v i s u a l f i e l d d a t a as shaded s u r f a c e s . A s y s t e m i s d e v e l o p e d t h a t s y n t h e s i z e s c o n t i n u o u s -t o n e , g r e y - l e v e l images o f a s u r f a c e v i e w e d from, and i l l u m i n a t e d from, any s p e c i f i e d d i r e c t i o n . The o r i g i n a l c o n t o u r d a t a may be s u p e r p o s e d upon any view o f t h e v i s u a l f i e l d s u r f a c e t o enhance i n t e r p r e t a t i o n . A zoom o p e r a t i o n a l l o w s f o r c l o s e r i n s p e c t i o n of s u r f a c e d e t a i l . A memory map t e c h n i q u e i s u s e d t o v a r y s u r f a c e shade i n r e a l t i m e w i t h t h e movement of a l i g h t s o u r c e a b o u t t h e s u r f a c e . I t i s shown t h a t t o e f f e c t i v e l y s i m u l a t e u n r e s t r i c t e d l i g h t s o u r c e movement, frame b u f f e r p i x e l s s h o u l d be a t l e a s t 12 b i t s w i d e . i i i T a b l e o f C o n t e n t s A b s t r a c t i i L i s t o f F i g u r e s v Acknowledgement v i i C h a p t e r I INTRODUCTION 1 1.1 C o n v e y i n g S u r f a c e Shape 4 1.1.1 M o t i o n P a r a l l a x 7 1.1.2 Shaded Imagery 8 1.1.3 C o n t o u r e d , Shaded S u r f a c e s 9 1.1.4 C o l o u r - C o d e d Imagery 9 1.1.5 S t e r e o Imagery 9 1.1.6 L i g h t S o u r c e M o t i o n 10 1.2 Sy s t e m O v e r v i e w 11 1.3 T h e s i s O r g a n i z a t i o n 19 C h a p t e r I I SURFACE REPRESENTATION 20 2.1 D a t a C o l l e c t i o n 20 2.2 The R e c o n s t r u c t i o n P r o b l e m 25 2.3 S u r f a c e R e p r e s e n t a t i o n 27 2.3.1 T r i a n g u l a t i o n C r i t e r i a 31 2.3.2 S u r f a c e C o n s i s t e n c y 33 2.3.3 T r i a n g u l a t i o n P r o c e d u r e 36 2.4 S u r f a c e I n t e r p o l a t i o n 37 2.5 Summary 39 C h a p t e r I I I IMAGE SYNTHESIS 41 3.1 P r o j e c t i o n T r a n s f o r m a t i o n s 41 3.2 H i d d e n S u r f a c e Removal 44 3.3 S u r f a c e S h a d i n g 48 3.4 C o n t o u r S u p e r p o s i t i o n 53 3.5 R e a l - T i m e Movement o f t h e L i g h t S o u r c e 54 3.5.1 O p t i m a l Q u a n t i z a t i o n 58 3.6 Summary 62 C h a p t e r IV RESULTS 64 4.1 V i s u a l F i e l d S u r f a c e s 64 4.2 G r a d i e n t Q u a n t i z a t i o n E x p e r i m e n t 78 C h a p t e r V CONCLUSIONS AND PROPOSALS 86 5.1 C o n c l u s i o n s 86 5.2 P r o p o s a l s f o r F u r t h e r Work 89 iv , BIBLIOGRAPHY ..94 APPENDIX A 97 APPENDIX B 1 0 2 V L i s t o f F i g u r e s 1.1 C o n t o u r map 3 1.2 G r e y - s c a l e map 3 1.3 A s s o c i a t i n g v i s u a l f i e l d d a t a w i t h r e t i n a l n e r v e f i b e r b u n d l e s 5 1.4 O r t h o g r a p h i c l i n e d r a w i n g 6 1.5 W o r l d c o o r d i n a t e s y s t e m 12 1.6 V i e w i n g s p e c i f i c a t i o n 12 1.7 Shaded s u r f a c e v i e w e d from 0 = 1 6 0 ° , 0 = 5 0 ° and i l l u m i n a t e d from 0 = 1 2 0 ° , 0 = 7 0 ° 14 1.8 Shaded s u r f a c e v i e w e d from 0 = 7 0 ° , 0 = 5 0 ° and i l l u m i n a t e d from 0 = 8 0 ° , 0 = 7 0 ° 14 1.9 I n v e r s i o n o f s u r f a c e i n F i g u r e 1.7 15 1.10 I n v e r s i o n o f s u r f a c e i n F i g u r e 1.8 15 1.11 O r i g i n a l c o n t o u r s s u p e r p o s e d on s u r f a c e i n F i g u r e 1.7 16 1.12 O r i g i n a l c o n t o u r s s u p e r p o s e d on i n v e r t e d s u r f a c e i n F i g u r e 1.9 16 1.13 Zoom window s u p e r p o s e d on o v e r h e a d v i e w ( 0 = 1 8 0 ° , 0 = 9 0 ° ) o f s u r f a c e i n F i g u r e 1.7 17 1.14 Windowed s u r f a c e v i e w e d f r o m 6*= 11 0° , 0=50° and i l l u m i n a t e d from 0= 1 30° , 0=70° ."...18 1.15 I n v e r s i o n o f windowed s u r f a c e v i e w e d from 0 = 1 6 0 ° , 0 = 5 0 ° and i l l u m i n a t e d f r o m 0 = 1 2 0 ° , 0 = 7 0 ° 18 2.1 C o n v e r g e n t t a r g e t s c a n 22 2.2 D i v e r g e n t t a r g e t s c a n 22 2.3 S c a n n i n g a c r o s s a v i s u a l d e f e c t 24 2.4 A s s o c i a t i n g s u r f a c e f e a t u r e s w i t h t r i a n g l e e d ges 30 2.5 S u r f a c e i n c o n s i s t e n c y a l o n g c o n t o u r 34 2.6 T r i a n g u l a t i o n c o n s i s t e n t w i t h s u r f a c e c o n t o u r 34 2.7 S u r f a c e i n c o n s i s t e n c y a l o n g r i d g e l i n e 35 2.8 T r i a n g u l a t i o n c o n s i s t e n t w i t h r i d g e l i n e 35 2.9 A t r i a n g u l a t i o n o f v i s u a l f i e l d d a t a 38 3.1 S u r f a c e p r o j e c t i o n 42 3.2 S c a n n i n g a s u r f a c e p r o f i l e i n t h e v i e w i n g d i r e c t i o n ..45 3.3 S c a n n i n g a s u r f a c e p r o f i l e a l o n g a g r i d l i n e ....45 3.4 V i e w i n g geometry 50 3.5 Geometry f o r o r t h o g r a p h i c v i e w i n g 50 3.6 Frame b u f f e r w i t h a t t a c h e d memory map 56 3.7 R e f l e c t a n c e map f o r d i f f u s e s u r f a c e i l l u m i n a t e d from 0 = 6 7 ° , 0 = 5 3 ° 61 4.1 V i s u a l f i e l d 1 65 4.2 V i s u a l f i e l d 2 67 4.3 V i s u a l f i e l d 3 69 4.4 V i s u a l f i e l d 4 71 4.5 V i s u a l f i e l d 5 73 4.6 V i s u a l f i e l d 6 75 4.7 D i f f u s e s u r f a c e r e p r e s e n t e d w i t h 8 - b i t g r a d i e n t s 79 4.8 D i f f u s e s u r f a c e r e p r e s e n t e d w i t h 1 0 - b i t g r a d i e n t s ....79 4.9 D i f f u s e s u r f a c e r e p r e s e n t e d w i t h 1 2 - b i t g r a d i e n t s ....80 4.10 D i f f u s e s u r f a c e r e p r e s e n t e d w i t h 6 4 - b i t g r a d i e n t s ....80 v i 4.11 S p e c u l a r s u r f a c e r e p r e s e n t e d w i t h 1 2 - b i t g r a d i e n t s ...81 4.12 S p e c u l a r s u r f a c e r e p r e s e n t e d w i t h 6 4 - b i t g r a d i e n t s ...81 4.13 G r a p h o f h ( p ) l i n e a r l y i n t e r p o l a t e d from h i s t o g r a m d a t a f o r p 82 4.14 Smoothed p r o b a b i l i t y d e n s i t y f u n c t i o n h ( p ) 84 4.15 Smoothed p r o b a b i l i t y d e n s i t y f u n c t i o n h ( q ) 85 A.1 Node N i n t r o d u c e d i n t o an e x i s t i n g t e s s e l l a t i o n 99 A.2 Node N i n c o r p o r a t e d i n t o a new t e s s e l l a t i o n 99 A. 3 How a t r i a n g l e edge d e f i n e d by v e r t i c e s I a n d J i s r e p r e s e n t e d i n t h e TIN d a t a s t r u c t u r e 101 B. 1 T r i a n g l e t r a n s f o r m a t i o n s 103 v i i Acknowledgement The a u t h o r would l i k e t o thank R o b e r t J . Woodham f o r h i s g u i d a n c e , G u n t h e r F. S c h r a c k f o r h i s s u p p o r t , and James J . L i t t l e f o r h i s e n t h u s i a s m . R o b e r t Woodham p r o v i d e d a w o r k i n g framework from w h i c h t h e s u r f a c e d i s p l a y p r o g r a m was d e v e l o p e d . James L i t t l e c o n t r i b u t e d t h e t r i a n g u l a t i o n and s u r f a c e i n t e r p o l a t i o n p r o g r a m s t o t h e s y s t e m . D r . S t e p h e n D r a n c e p r o v i d e d t h e v i s u a l f i e l d d a t a and v a l u a b l e f e e d b a c k c o n c e r n i n g t h e p r o j e c t . S t e v e Wismath d i g i t i z e d t h e d a t a f r o m t h e v i s u a l f i e l d c h a r t s . D e t l e f H e i s s d e v e l o p e d t h e f i l t e r s u s e d i n t h e p h o t o g r a p h y , and L u i s M a r t i p r o v i d e d a p r o g r a m t h a t e n a b l e d t h e use o f s u b s c r i p t s i n t h e t e x t . The a u t h o r would a l s o l i k e t o thank J i m C l a r k , P a u l Freedman, N i c k J a e g e r , and B r i a n Maranda f o r t h e i r c r i t i c i s m s and s u g g e s t i o n s . T h i s work was s u p p o r t e d by a p o s t g r a d u a t e s c h o l a r s h i p g r a n t e d by t h e N a t u r a l S c i e n c e s and E n g i n e e r i n g R e s e a r c h C o u n c i l (NSERC) o f Canada. Images p r o d u c e d f o r t h i s t h e s i s were d i s p l a y e d u s i n g f a c i l i t i e s of t h e L a b o r a t o r y f o r C o m p u t a t i o n a l V i s i o n i n t h e Department o f Computer S c i e n c e , U n i v e r s i t y o f B r i t i s h C o l u m b i a . The l a b o r a t o r y i s s u p p o r t e d , i n p a r t , by t h e I n t e r d i s c i p l i n a r y G r a d u a t e Program i n Remote S e n s i n g and, i n p a r t , by NSERC g r a n t SMI-51. 1 I . INTRODUCTION T h i s t h e s i s d e a l s w i t h t h e g r a p h i c a l p r e s e n t a t i o n o f human v i s u a l f i e l d d a t a o b t a i n e d by t h r e s h o l d p e r i m e t r y . T h r e s h o l d p e r i m e t r y i s a t e c h n i q u e whereby t h e t h r e s h o l d s e n s i t i v i t y o f a human s u b j e c t ' s eye t o l i g h t s t i m u l a t i o n i s m e a s u r e d . W h i l e s t a r i n g a t a f i x e d r e f e r e n c e p o i n t , t h e s u b j e c t c o n c e n t r a t e s on d e t e c t i n g l i g h t s t i m u l i p r e s e n t e d w i t h i n h i s f i e l d o f v i s i o n . The p o s i t i o n s a t w h i c h t h e s u b j e c t r e s p o n d s t o d i f f e r e n t s t i m u l i a r e r e c o r d e d on a c h a r t . In k i n e t i c p e r i m e t r y , a s i n g l e t a r g e t l i g h t s o u r c e o f f i x e d i n t e n s i t y i s moved a c r o s s t h e s u b j e c t ' s f i e l d o f v i e w . The p o s i t i o n a t w h i c h t h e t a r g e t e i t h e r a p p e a r s o r d i s a p p e a r s b e f o r e t h e s u b j e c t marks a p o i n t o f v i s u a l t h r e s h o l d a t t h a t i n t e n s i t y . I n s t a t i c p e r i m e t r y , t h e i n t e n s i t y o f a t a r g e t l i g h t s o u r c e w i t h i n a r e g u l a r g r i d o f s u c h s o u r c e s i s s l o w l y i n c r e a s e d u n t i l t h e s u b j e c t f i r s t d e t e c t s t h e s t i m u l u s . T h i s i n t e n s i t y marks t h e t h r e s h o l d s e n s i t i v i t y o f t h e s u b j e c t ' s eye a t t h a t t a r g e t p o s i t i o n . The t a r g e t s a r e t u r n e d on, and t h e n o f f , one a t a t i m e i n a random p a t t e r n u n t i l t h e e n t i r e g r i d h as been c o v e r e d . The g r i d need n o t c o v e r t h e e n t i r e v i s u a l f i e l d ; a s m a l l e r g r i d may be p o s i t i o n e d t o c o v e r a f i e l d s e c t o r o f i n t e r e s t t o t h e o p h t h a l m o l o g i s t . I n s t a t i c p e r i m e t r y , t h e t a r g e t s do n o t move but t h e i n t e n s i t y o f e a c h i s v a r i a b l e . The d a t a a r e c o l l e c t e d i n t h e form o f a m a t r i x o f l i g h t i n t e n s i t i e s . In k i n e t i c p e r i m e t r y , t h e i n t e n s i t y o f a t a r g e t i s h e l d f i x e d a s t h e t a r g e t s c a n s 2 a l o n g many t r a j e c t o r i e s a c r o s s t h e v i s u a l f i e l d . The d a t a o b t a i n e d by s c a n n i n g w i t h one t a r g e t a r e s a m p l e s o f an e q u i -i n t e n s i t y c o n t o u r , o r i s o p t e r . S c a n n i n g w i t h a d d i t i o n a l t a r g e t s of d i f f e r e n t i n t e n s i t i e s y i e l d s a c o n t o u r map. E i t h e r d a t a s e t , m a t r i x o r c o n t o u r map, i s s p a r s e . E i t h e r c a n be t h o u g h t o f as a s a m p l i n g o f a s i n g l e - v a l u e d f u n c t i o n o f two i n d e p e n d e n t v a r i a b l e s , where t h r e s h o l d i n t e n s i t y i s a f u n c t i o n of two p o s i t i o n a l c o o r d i n a t e s . I n t e n s i t y v a l u e s between c o n t o u r samples o b t a i n e d from a k i n e t i c p e r i m e t e r may be i n t e r p o l a t e d m a n u a l l y by a m e d i c a l t e c h n i c i a n o r a u t o m a t i c a l l y by a c o m p u t e r . An a u t o m a t e d s y s t e m t h a t p r o d u c e s p i e c e w i s e - l i n e a r c o n t o u r s i s d e s c r i b e d by H a r t ( 1 9 8 1 ) . A c o n t o u r map drawn w i t h l i n e segments i s shown i n F i g u r e 1.1, where c o l o u r i s u s e d t o c o d e a s m a l l s e t o f s t a n d a r d t a r g e t i n t e n s i t i e s and s i z e s . I n t e n s i t y v a l u e s a r e i n t e r p o l a t e d a t p o i n t s between t h e s p a r s e s a m p l e s o b t a i n e d f r o m a s t a t i c p e r i m e t e r t o g e n e r a t e a d e n s e r m a t r i x . T h i s d e n s e m a t r i x may be d i s p l a y e d as a g r e y -s c a l e image, where e a c h sample i s a s s i g n e d a g r e y l e v e l p r o p o r t i o n a l t o i t s v a l u e a n d t h e n mapped i n t o a p i x e l on a s c r e e n o r c h a r t . An example o f a g r e y - s c a l e map i s g i v e n i n F i g u r e 1.2, where d a r k a r e a s i n d i c a t e r e g i o n s o f v i s u a l l o s s . In an a t t e m p t t o improve upon t h e g r e y - s c a l e r e n d i t i o n , and t o o b j e c t i f y t h e i n t e r p r e t a t i o n o f s t a t i c f i e l d d a t a , W i r t s c h a f t e r e t a l . (1982) g r o u p t h e d a t a by r e g i o n s c o r r e s p o n d i n g t o p h y s i o l o g i c a l s t r u c t u r e s i n t h e e y e . They p a r t i t i o n t h e v i s u a l f i e l d domain i n t o f i x e d r e g i o n s t h a t F i g u r e 1.2 G r e y - s c a l e map 4 p r o j e c t o n t o n e r v e f i b e r l a y e r s i n t h e r e t i n a . F i e l d d a t a w i t h i n a r e g i o n a r e a v e r a g e d t o y i e l d a s i n g l e measure f o r t h a t r e g i o n . An example o f t h i s form o f v i s u a l f i e l d p r e s e n t a t i o n i s g i v e n i n F i g u r e 1.3. A d i s a d v a n t a g e w i t h p r e s e n t a t i o n s s u c h a s t h e c o n t o u r map or t h e g r e y - s c a l e map i s t h a t t h e y o f f e r a "view" o f t h e s u r f a c e f r o m above o n l y . R e c o g n i z i n g t h i s , H a r t and H a r t z (1982) employ a t e c h n i q u e t h a t e n a b l e s v i e w i n g o f t h e v i s u a l f i e l d s u r f a c e f r o m an a r b i t r a r y d i r e c t i o n . They r e n d e r t h e v i s u a l f i e l d a s a p e r s p e c t i v e l i n e d r a w i n g o f s u r f a c e p r o f i l e c u r v e s . An example o f an o r t h o g r a p h i c l i n e d r a w i n g o f a v i s u a l f i e l d s u r f a c e i s shown i n F i g u r e 1.4. The t h e s i s i n v e s t i g a t e s a d d i t i o n a l t e c h n i q u e s whereby human v i s u a l f i e l d d a t a c a n be e f f e c t i v e l y c o n v e y e d t o t h e o p h t h a l m o l o g i s t . The d a t a c a n be t h o u g h t of as l y i n g on o r n e a r a s u r f a c e . The i n v e s t i g a t i o n , t h e r e f o r e , f o c u s e s upon e f f e c t i v e methods f o r r e n d e r i n g s u r f a c e s h a p e . 1.1 C o n v e y i n g S u r f a c e Shape When a 3D s u r f a c e i s p r e s e n t e d g r a p h i c a l l y , i t i s p r o j e c t e d o n t o a 2D medium. The r e s u l t i n g l o s s o f i n f o r m a t i o n o f t e n l e a d s t o a m b i g u i t i e s i n t h e image. V i s u a l c u e s a r e i n t r o d u c e d i n t o t h e image t o h e l p t h e v i e w e r b e t t e r r e s o l v e s p a t i a l r e l a t i o n s h i p s . In t h e c u r r e n t a p p l i c a t i o n , a s i n g l e s u r f a c e i s p r e s e n t e d . I t i s i m p o r t a n t t o c o n v e y t h e shape o f t h a t s u r f a c e a s i t v a r i e s from one " l o c a l i t y " t o a n o t h e r , t o d e p i c t t h e s p a t i a l F i g u r e 1.3 A s s o c i a t i n g v i s u a l f i e l d d a t a w i t h r e t i n a l n e r v e f i b e r b u n d l e s [ f r o m W i r t s c h a f t e r e t a l . (1982)3 F i g u r e 1.4 O r t h o g r a p h i c l i n e d r a w i n g 7 r e l a t i o n s h i p s between n e i g h b o u r i n g l o c a l i t i e s . F o r an a b s t r a c t , complex s u r f a c e , t h e s e r e l a t i o n s h i p s may be more s u b t l e and more d i f f i c u l t t o d e p i c t t h a n t h o s e i n a s c e n e composed o f many f a m i l i a r o b j e c t s . V i s u a l c u e s , t h e r e f o r e , become v e r y i m p o r t a n t i n t h e image s y n t h e s i s p r o c e s s . V i s u a l c u e s a r e s o r e l y l a c k i n g i n p r e s e n t a t i o n s s u c h as t h e c o n t o u r map o r t h e g r e y - s c a l e map. In t h e a p p r o a c h o f H a r t and H a r t z , v i s u a l d e p t h c u e s a r e p r o v i d e d by t h e r e m o v a l o f h i d d e n l i n e s . Segments o f s u r f a c e p r o f i l e s o b s c u r e d by p r o f i l e s " c l o s e r " t o t h e v i e w e r a r e n o t drawn, as i l l u s t r a t e d i n F i g u r e 1.4. The p e r s p e c t i v e p r o j e c t i o n makes p a r a l l e l l i n e s " f a r t h e r " away f r o m t h e v i e w e r a p p e a r t o c o n v e r g e t o a v a n i s h i n g p o i n t . T h e s e d e v i c e s p r o v i d e t h e v i e w e r w i t h a n o t i o n o f how one s u r f a c e l o c a l i t y i s c l o s e r o r f a r t h e r t h a n a n o t h e r ; p r o f i l e shape and d e n s i t y c o n v e y s u r f a c e shape w i t h i n l o c a l i t i e s . What f o l l o w s i s a b r i e f r e v i e w o f a d d i t i o n a l t e c h n i q u e s t h a t i n t r o d u c e v i s u a l c u e s i n t o an image o f a 3D s u r f a c e . 1.1.1 M o t i o n P a r a l l a x T h i s t e c h n i q u e h e l p s t o r e s o l v e image a m b i g u i t y by p r o v i d i n g t h e v i e w e r w i t h d i f f e r e n t v i e w s o f t h e same s u r f a c e . A s e q u e n c e o f v i e w s o f t h e s u r f a c e i s g e n e r a t e d where t h e s u r f a c e i s r o t a t e d s l i g h t l y between s u c c e s s i v e v i e w s . In r e a l -t i m e a n i m a t i o n , i n d i v i d u a l f r a m e s a r e d i s p l a y e d r a p i d l y on a s c r e e n and t h e s u r f a c e a p p e a r s t o r o t a t e s m o o t h l y . The e f f e c t o f d e p t h i s p r o d u c e d by t h e d i f f e r e n c e s i n v e l o c i t y a t w h i c h v a r i o u s p a r t s o f t h e s u r f a c e a p p e a r t o move w i t h r e s p e c t t o e a c h 8 o t h e r . The " f a r t h e r " a s u r f a c e e l e m e n t i s f r o m t h e a x i s o f r o t a t i o n , t h e f a s t e r i t a p p e a r s t o be m o v i n g . S u r f a c e e l e m e n t s between t h e a x i s and t h e v i e w e r move i n a d i r e c t i o n o p p o s i t e t o t h a t o f s u r f a c e e l e m e n t s b e h i n d t h e a x i s . T h e r e f o r e , t h e v i e w e r c a n r e s o l v e s p a t i a l r e l a t i o n s h i p s by d e t e c t i n g d i f f e r e n c e s i n r e l a t i v e s p e e d and d i r e c t i o n of s u r f a c e e l e m e n t s , d i f f e r e n c e s w h i c h he c a n a p p r e c i a t e f r o m h i s e x p e r i e n c e w i t h r o t a t i n g o b j e c t s i n t h e r e a l w o r l d . 1.1.2 Shaded Imagery C o n t i n u o u s - t o n e , g r e y - l e v e l images d e p i c t s u r f a c e s t h a t e x h i b i t v a r i a t i o n s i n shade i n a c c o r d a n c e w i t h s u r f a c e shape and s c e n e i l l u m i n a t i o n . The amount o f l i g h t r e f l e c t e d by a s u r f a c e e l e m e n t d epends upon t h e r e f l e c t a n c e p r o p e r t i e s o f t h e s u r f a c e , t h e l i g h t s o u r c e d i s t r i b u t i o n , t h e v i e w p o i n t , and t h e o r i e n t a t i o n o f t h e e l e m e n t . F o r a f i x e d v i e w p o i n t , l i g h t i n g g e o m e t r y , and s u r f a c e r e f l e c t a n c e , t h e shade of a s u r f a c e e l e m e n t d epends o n l y on i t s o r i e n t a t i o n . L o c a l v a r i a t i o n s i n shade t h u s p r o v i d e a v a l u a b l e cue f o r i n f e r r i n g l o c a l v a r i a t i o n s i n s u r f a c e s h a p e , w h i l e p r o d u c i n g a r e a l i s t i c image o f t h e s u r f a c e . 9 1.1.3 C o n t o u r e d , Shaded S u r f a c e s F o r r e s t (1979) o b s e r v e s t h a t even a s h a d e d image o f a s u r f a c e may be d i f f i c u l t t o i n t e r p r e t when t h e s u r f a c e i s a r b i t r a r y and f a l l s b eyond t h e v i e w e r ' s e x p e r i e n c e . He s u g g e s t s t h a t an image d e p i c t i n g c o n t o u r s o v e r l a y e d upon t h e s h a d e d s u r f a c e i s more e f f e c t i v e t h a n j u s t t h e sh a d e d s u r f a c e i t s e l f . The c o n t o u r s l i e a t p r e c i s e l e v e l s on t h e s u r f a c e and p r o v i d e f o r a l e s s ambiguous image. 1.1.4 C o l o u r - C o d e d Imagery F o r r e s t f u r t h e r s u g g e s t s t h a t image p i x e l s be c o l o u r - c o d e d t o d e p i c t t h e m a g n i t u d e o f some l o c a l s u r f a c e p r o p e r t y , s u c h a s c u r v a t u r e . S m a l l s u r f a c e v a r i a t i o n s , s u c h as s u b t l e c o n c a v i t i e s o r c o n v e x i t i e s , w h i c h may be d i f f i c u l t t o d e t e c t i n a g r e y - s c a l e image, c o u l d be r e n d e r e d more p r o m i n e n t w i t h c o l o u r . C o ncave and c o n v e x s u r f a c e e l e m e n t s c o u l d be c o d e d w i t h d i f f e r e n t c o l o u r s , and t h e s a t u r a t i o n o f e a c h c o l o u r c o u l d be made d e p e n d e n t on t h e m a g n i t u d e o f c u r v a t u r e . 1.1.5 S t e r e o Imagery Humans p o s s e s s two e y e s , and t h e s e p r o v i d e a s t e r e o p a i r of images f r o m w h i c h d e p t h i n f o r m a t i o n i s e x t r a c t e d . To t a k e a d v a n t a g e o f human b i n o c u l a r s t e r e o , s p e c i a l h a r d w a r e i s u s e d t o s u p p l y a v i e w e r w i t h two s y n t h e t i c images o f t h e same s c e n e , one g e n e r a t e d f r o m t h e v i e w p o i n t o f t h e l e f t e y e , t h e o t h e r f r o m t h e v i e w p o i n t o f t h e r i g h t . 10 F o l e y and van Dam (1982) d e s c r i b e s e v e r a l t e c h n i q u e s f o r g e n e r a t i n g s t e r e o images. S p e c i a l o p t i c s may c h a n n e l images from two s e p a r a t e CRT s c r e e n s t o t h e v i e w e r ' s e y e s , o r a s i n g l e CRT s c r e e n may a l t e r n a t e l y d i s p l a y e a c h image i n a s t e r e o p a i r r a p i d l y enough t o p r o d u c e a f l i c k e r - f r e e e f f e c t . In t h e s i n g l e -CRT c o n f i g u r a t i o n , two s o l i d - s t a t e s h u t t e r s , one p l a c e d b e f o r e e a c h o f t h e v i e w e r ' s e y e s , a r e e l e c t r o n i c a l l y s y n c h r o n i z e d w i t h t h e CRT so t h a t when one s h u t t e r i s c l o s e d , t h e o t h e r i s o p e n e d t o e x p o s e t h e c o r r e c t image t o t h a t e y e . P o l a r i z e d f i l t e r s , o r c o l o u r f i l t e r s , p o s i t i o n e d a t t h e s c r e e n and b e f o r e t h e v i e w e r ' s e y e s , p r o d u c e a s i m i l a r e f f e c t . 1.1.6 L i g h t S o u r c e M o t i o n Woodham (1980) d e v e l o p e d a t e c h n i q u e c a l l e d p h o t o m e t r i c s t e r e o whereby s u r f a c e o r i e n t a t i o n i s d e t e r m i n e d f r o m m u l t i p l e images o f t h e s u r f a c e v i e w e d from a f i x e d d i r e c t i o n b u t u n d e r d i f f e r e n t i l l u m i n a t i o n c o n d i t i o n s . A l t h o u g h d e v e l o p e d f o r image a n a l y s i s , t h i s i d e a c a n be e x p l o i t e d i n image s y n t h e s i s . V i e w i n g images of t h e same s c e n e , where o n l y a l i g h t s o u r c e has been moved between f r a m e s , i s e f f e c t i v e i n r e s o l v i n g a m b i g u i t i e s p r e s e n t i n a s i n g l e , s h a d e d image. T h i s i s e s p e c i a l l y a t t r a c t i v e i f t h e images can be g e n e r a t e d i n r e a l t i m e w i t h t h e movement o f t h e l i g h t s o u r c e . 11 1.2 System O v e r v i e w An i d e a l way t o examine t h e shape o f an o b j e c t would be t o t o u c h i t s s u r f a c e , t o m a n i p u l a t e i t , a n d t o view i t from d i f f e r e n t d i r e c t i o n s . The p r o b l e m a d d r e s s e d i n t h i s t h e s i s i s t h e p r e s e n t a t i o n o f a 3D o b j e c t by a 2D image. T a c t i l e i n s p e c t i o n i s i m p r a c t i c a l , b u t t h e o b j e c t may be " m a n i p u l a t e d " by g e n e r a t i n g images o f t h e o b j e c t under d i f f e r e n t v i e w i n g and l i g h t i n g c o n d i t i o n s . The images c a n be made r e a l i s t i c by u s i n g some o f t h e v i s u a l c u e s p r e v i o u s l y d i s c u s s e d . A s o f t w a r e s y s t e m was d e v e l o p e d t o s y n t h e s i z e shaded images o f t h e s u r f a c e s u n d e r l y i n g v i s u a l f i e l d d a t a . I t i s d e m o n s t r a t e d t h a t s u r f a c e shape i s more e f f e c t i v e l y c o n v e y e d w i t h s h a d e d i m a g e r y t h a n w i t h t h e l i n e d r a w i n g s o f H a r t and H a r t z . Images show s u r f a c e s i l l u m i n a t e d f r o m a s p e c i f i e d d i r e c t i o n by a s i n g l e , d i s t a n t l i g h t s o u r c e . A g i v e n s u r f a c e i s " m a n i p u l a t e d " by g e n e r a t i n g images o f t h e s u r f a c e v i e w e d from, and i l l u m i n a t e d from, d i f f e r e n t d i r e c t i o n s . V i e w i n g c a n be p e r f o r m e d f r o m anywhere i n t h e h a l f -s p a c e z > 0, where i t i s assumed t h a t b o t h t h e s u r f a c e and t h e v i e w e r a r e b a s e d i n an ( x , y , z ) " w o r l d " c o o r d i n a t e s y s t e m ( s e e F i g u r e 1.5). A v i e w i n g d i r e c t i o n i s s p e c i f i e d by an a z i m u t h a l a n g l e 6 and an e l e v a t i o n a n g l e <j>. The l i g h t i n g d i r e c t i o n i s s p e c i f i e d by i t s own 6 and 0. The a z i m u t h a l a n g l e i s m e a s u r e d c l o c k w i s e f r o m t h e p o s i t i v e y a x i s , and t h e e l e v a t i o n a n g l e i s m e asured above t h e xy p l a n e ( s e e F i g u r e 1.6). A l t h o u g h any e l e v a t i o n between 0° and 90° may be s p e c i f i e d , most o f t h e s u r f a c e s i n t h i s t h e s i s a r e v i e w e d f r o m 0=50° and i l l u m i n a t e d 12 F i g u r e 1.6 V i e w i n g s p e c i f i c a t i o n 13 f r o m 0 = 7 0 ° . The a z i m u t h i s s p e c i f i e d by an a n g l e between 0° and 3 6 0 ° . A s u r f a c e d e p i c t i n g t h e d a t a i n F i g u r e 1.1 i s shown i n F i g u r e 1.7, where t h e view i s from 0 = 1 6 0 ° . F i g u r e 1.8 shows t h e same s u r f a c e , b u t v i e w e d from 0 = 7 0 ° . The p r o m i n e n t f e a t u r e s o f t h i s s u r f a c e a p p e a r t o be " p i t s " w h i c h l i e h i d d e n below t h e v i s i b l e s u r f a c e a r e a . To make t h e s e f e a t u r e s more v i s i b l e , t h e s u r f a c e may be " i n v e r t e d " so t h a t p i t s become " p e a k s " . F i g u r e s 1.9 and 1.10 show i n v e r s i o n s o f t h e s u r f a c e s i n F i g u r e s 1.7 and 1.8, r e s p e c t i v e l y . T h i s i n v e r s i o n f e a t u r e e f f e c t i v e l y p e r m i t s v i e w i n g f r o m t h e lo w e r h a l f - s p a c e z < 0. I n t e r p r e t a t i o n o f t h e s e images i s a i d e d by s u p e r p o s i n g t h e c o l o u r c o n t o u r s o f t h e o r i g i n a l v i s u a l f i e l d c h a r t o n t o t h e sh a d e d s u r f a c e . Examples o f c o n t o u r s u p e r p o s i t i o n a r e f o u n d i n F i g u r e s 1.11 and 1.12. The s y s t e m a l s o p r o v i d e s a zoom f u n c t i o n . A window o f s p e c i f i e d s i z e i s s u p e r p o s e d on an o v e r h e a d v i e w ( 0 = 1 8 0 ° , 0 = 9 0 ° ) of t h e s u r f a c e ( s e e F i g u r e 1.13). The s u r f a c e w i t h i n t h e window i s t h e n blown up t o f u l l s c r e e n r e s o l u t i o n . The windowed s u r f a c e may a l s o be i n v e r t e d and v i e w e d from any d i r e c t i o n . E xamples o f t h e s e o p e r a t i o n s a r e shown i n F i g u r e s . 1.14 and 1.15. F i n a l l y , a memory map a t t a c h e d t o a frame b u f f e r i s u s e d t o s i m u l a t e r e a l - t i m e movement o f a l i g h t s o u r c e a b o u t a s t a t i o n a r y s u r f a c e . T h i s i s done i n an a t t e m p t t o r e s o l v e a m b i g u i t i e s i n a s i n g l e image i n much t h e same way t h a t m u l t i p l e , s h a d e d images a r e u s e d i n p h o t o m e t r i c s t e r e o . F i g u r e 1 .8 Shaded s u r f a c e viewed from 0=70°,0=50° and i l l u m i n a t e d from 0=80°,0=70° F i g u r e 1 . 9 I n v e r s i o n o f s u r f a c e i n F i g u r e 1.7 F i g u r e 1 . 1 0 I n v e r s i o n o f s u r f a c e i n F i g u r e 1 . 8 16 F i g u r e 1.11 O r i g i n a l c o n t o u r s s u p e r p o s e d on s u r f a c e i n F i g u r e 1.7 F i g u r e 1.12 O r i g i n a l c o n t o u r s s u p e r p o s e d on i n v e r t e d s u r f a c e i n F i g u r e 1.9 17 F i g u r e 1.13 Zoom window s u p e r p o s e d on o v e r h e a d ( 0 = 1 8 0 ° , 0 = 9 0 ° ) o f s u r f a c e i n F i g u r e 1.7 view F i g u r e 1.14 Windowed s u r f a c e v i e w e d f r o m 0 = 1 1 0 ° , 0 = 5 0 ° and i l l u m i n a t e d f r o m 0 = 1 3 0 ° , 0 = 7 0 ° 19 1.3 T h e s i s O r g a n i z a t i o n The p r o b l e m o f v i e w i n g 3D human v i s u a l f i e l d d a t a i s d i v i d e d i n t o two p a r t s : t h e f i r s t d e a l i n g w i t h t h e r e c o n s t r u c t i o n o f a c o m p l e t e s u r f a c e from s p a r s e d a t a , and t h e s e c o n d w i t h t h e s y n t h e s i s o f a s h a d e d image o f t h e r e c o n s t r u c t e d s u r f a c e . A c h a p t e r i s d e v o t e d t o e a c h o f t h e s e p a r t s . C h a p t e r 2 ' d i s c u s s e s some o f t h e i s s u e s i n v o l v e d i n r e c o n s t r u c t i n g a c o n s i s t e n t s u r f a c e from t h e s p a r s e d a t a c o l l e c t e d by k i n e t i c p e r i m e t r y . C o n s i d e r a t i o n o f t h e s e i s s u e s g u i d e s t h e s e l e c t i o n o f a s u r f a c e r e p r e s e n t a t i o n and an i n t e r p o l a t i o n scheme. C h a p t e r 3 o u t l i n e s t h e s t e p s i n t h e image s y n t h e s i s p r o c e s s : , v i e w i n g t r a n s f o r m a t i o n s , h i d d e n s u r f a c e r e m o v a l , and s u r f a c e s h a d i n g . The s i m p l e h i d d e n s u r f a c e a l g o r i t h m u s e d 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 i s d e s c r i b e d . Two methods f o r s u p e r p o s i n g c o n t o u r s on a sh a d e d s u r f a c e a r e a l s o d i s c u s s e d , t o g e t h e r w i t h t h e p r o b l e m s i n v o l v e d i n t h e r e a l - t i m e s i m u l a t i o n o f a l i g h t s o u r c e moving a b o u t a s t a t i o n a r y s u r f a c e . C h a p t e r 4 i s m a i n l y p i c t o r i a l . I t c o n t a i n s t h e images o f s u r f a c e s r e c o n s t r u c t e d f r o m s i x v i s u a l f i e l d c h a r t s . The c h a r t s were o b t a i n e d from a s i n g l e p a t i e n t examined s i x t i m e s o v e r a p e r i o d o f a b o u t f o u r y e a r s . Some r e s u l t s f r o m t h e l i g h t s o u r c e movement e x p e r i m e n t a r e a l s o i n c l u d e d . C h a p t e r 5 d i s c u s s e s t h e r e s u l t s o f C h a p t e r 4, a t t e m p t s t o e v a l u a t e t h e c u r r e n t s y s t e m d e s i g n , and makes p r o p o s a l s f o r improvements and f u r t h e r e x p e r i m e n t s . 20 I I . SURFACE RECONSTRUCTION 2.1 D a t a C o l l e c t i o n The v i s u a l f i e l d d a t a d e a l t w i t h i n t h i s t h e s i s a r e o b t a i n e d f r o m a human s u b j e c t examined w i t h a k i n e t i c p e r i m e t e r . T h i s a p p a r a t u s c o n s i s t s o f a l a r g e h e m i s p h e r i c a l bowl and a mechanism f o r p r o j e c t i n g a c i r c u l a r s p o t o f l i g h t anywhere on t h e i n n e r s u r f a c e o f t h e b o w l . The mechanism i s o p e r a t e d by a m e d i c a l t e c h n i c i a n who c o n t r o l s t h e s i z e and i n t e n s i t y o f t h e l i g h t t a r g e t , and t h e t r a j e c t o r y a l o n g w h i c h i t moves on t h e b o wl. The s u b j e c t p l a c e s h i s head a g a i n s t a s u p p o r t a t t h e open end o f t h e bowl and p e e r s i n s i d e . The t e c h n i c i a n s i t s o u t s i d e t h e bowl o p p o s i t e t h e s u b j e c t . I f n o t f o r t h e b o w l , t h e two would be f a c i n g e a c h o t h e r . W i t h one eye c o v e r e d and t h e eye under t e s t f i x e d upon a r e f e r e n c e p o i n t on t h e bowl, t h e s u b j e c t r e s p o n d s whenever t h e t a r g e t a p p e a r s w i t h i n h i s v i s u a l f i e l d o r d i s a p p e a r s f r o m i t . At t h e s e t i m e s t h e t e c h n i c i a n marks t h e t a r g e t p o s i t i o n s on a p a p e r c h a r t a t t a c h e d t o t h e o u t e r s u r f a c e of t h e b o w l . The t a r g e t i s p r o j e c t e d o n t o t h e c h a r t , a s w e l l as o n t o t h e i n n e r s u r f a c e o f t h e bowl, i n o r d e r t o f a c i l i t a t e t h e r e c o r d i n g o f v i s u a l t h r e s h o l d l o c a t i o n s . The d a t a a r e marked a g a i n s t a r e c t a n g u l a r c o o r d i n a t e s y s t e m whose o r i g i n i s t h e p o i n t o f f i x a t i o n . The g r a d u a t i o n s a l o n g t h e a x e s r e p r e s e n t d e g r e e s o f e c c e n t r i c i t y f r o m t h e f i x a t i o n p o i n t . A t a r g e t o f f i x e d s i z e and i n t e n s i t y i s u s e d t o o b t a i n one v i s u a l t h r e s h o l d c o n t o u r . On one s i d e o f t h e c o n t o u r , t h e 21 t a r g e t i s v i s i b l e t o t h e s u b j e c t , and on t h e o t h e r s i d e i t i s i n v i s i b l e . C o n t o u r s a r e o b t a i n e d by m o ving t h e t a r g e t a l o n g t r a j e c t o r i e s a c r o s s t h e s u b j e c t ' s f i e l d o f v i e w . The p o i n t s a t w h i c h t h e s u b j e c t f i r s t d e t e c t s a change i n t h e v i s i b i l i t y o f t h e t a r g e t l i e on a c o n t o u r . D a t a p o i n t s c o l l e c t e d i n t h i s manner a r e c o n s i d e r e d s a m p l e s o f t h e c o n t o u r . The t e c h n i c i a n c o n t r o l s t h e number and s p a c i n g o f t h e t a r g e t s c a n s s u c h t h a t he c a n m a n u a l l y i n t e r p o l a t e between t h e d a t a p o i n t s t o o b t a i n a smooth c o n t o u 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 , v i s u a l f i e l d c o n t o u r s a r e r e c o n s t r u c t e d f r o m t h e raw, d i g i t i z e d d a t a p o i n t s w i t h l i n e a r i n t e r p o l a t i o n , so t h a t e a c h c o n t o u r i s a s e t o f c o n n e c t e d , s t r a i g h t - l i n e s e gments. Some o f t h e c o n t o u r s a r e t r a c e d by moving t h e t a r g e t a l o n g c u r v e s from o u t s i d e t h e s u b j e c t ' s f i e l d o f view t o w a r d s t h e c e n t e r . An i l l u s t r a t i o n o f s u c h p e r i p h e r a l s c a n n i n g , and o f t h e r e s u l t i n g d a t a , i s shown i n F i g u r e 2.1. In t h e a b s e n c e o f a d d i t i o n a l d a t a , s u c h a c o n t o u r may r e p r e s e n t a " p l a t e a u " o f v i s i o n , where v i s u a l s e n s i t i v i t y i s r e d u c e d o u t s i d e t h e p l a t e a u r i m . A n o t h e r s c a n n i n g p a t t e r n i s u s e d t o t r a c e o u t r e g i o n s o f s e n s i t i v i t y l o s s , u s u a l l y n e a r t h e c e n t e r o f t h e f i e l d . The t a r g e t i s p o s i t i o n e d w i t h i n t h e s u s p e c t e d r e g i o n o f l o s s and moved ou t t o w a r d s t h e f i e l d p e r i p h e r y . A c o n t o u r i s o b t a i n e d w i t h a d d i t i o n a l s c a n s r a d i a t i n g o u t i n d i f f e r e n t d i r e c t i o n s f r o m t h e r e g i o n ' s i n t e r i o r . T h i s s c a n n i n g p a t t e r n i s i l l u s t r a t e d i n F i g u r e 2.2. I n t h e a b s e n c e o f a d d i t i o n a l d a t a , s u c h a c o n t o u r may r e p r e s e n t t h e r i m o f a v i s u a l " p i t " . 22 V \ N F i g u r e 2.1 C o n v e r g e n t t a r g e t s c a n \ F i g u r e 2.2 D i v e r g e n t t a r g e t s c a n 23 F i g u r e 2.3 i l l u s t r a t e s a s c a n a c r o s s a v i s u a l f i e l d t h a t e x h i b i t s a c e n t r a l d e f e c t o r a b l i n d s p o t . Assume t h a t t h e t a r g e t f o l l o w s t h e t r a j e c t o r y i n d i c a t e d i n t h e f i g u r e , s t a r t i n g a t t h e t o p . The s u b j e c t f i r s t d e t e c t s t h e t a r g e t a t p o i n t A. He c o n t i n u e s t o see t h e t a r g e t u n t i l p o i n t B, j u s t b e f o r e e n t r y i n t o t h e b l i n d a r e a . The t a r g e t t h e n becomes i n v i s i b l e t o t h e s u b j e c t u n t i l i t has p a s s e d o v e r t h e b l i n d r e g i o n and a r r i v e s a t p o i n t C. I t r e m a i n s v i s i b l e from p o i n t C t o p o i n t D, a t w h i c h t i m e t h e t a r g e t l e a v e s t h e v i s u a l p e r i p h e r y f o r t h a t i n t e n s i t y , and i s l o s t t o s i g h t . P o i n t s A, B, C, and D f a l l on a s i n g l e i s o p t e r , b u t t h e shape o f t h i s c o n t o u r becomes e v i d e n t o n l y a f t e r more s c a n s a r e p e r f o r m e d a c r o s s t h e f i e l d . A f t e r t h i s c o n t o u r i s t r a c e d , t h e c e n t r a l r e g i o n o f v i s u a l l o s s i s p r o b e d w i t h • t a r g e t s o f h i g h e r i n t e n s i t y , so t h a t t h e d e f e c t i s r e p r e s e n t e d i n g r e a t e r d e t a i l . By r e p r e s e n t i n g t h e v i s u a l f i e l d w i t h a c o n t o u r map, an a s s u m p t i o n i s i m p l i c i t l y b e i n g made a b o u t t h e b e h a v i o u r o f t h i s phenomenon: v i s u a l t h r e s h o l d i s a c o n t i n u o u s , s i n g l e - v a l u e d f u n c t i o n o f f i e l d p o s i t i o n . In t h e r e m a i n d e r of t h e t e x t , t h e v i s u a l f i e l d w i l l be e x p r e s s e d as t h e f u n c t i o n z = F ( x , y ) , where z i s a measure o f v i s u a l s e n s i t i v i t y , and x and y a r e p o s i t i o n c o o r d i n a t e s g i v e n i n d e g r e e s . F i n a l l y , t h e e r r o r a r i s i n g f r o m t h e d a t a c o l l e c t i o n p r o c e s s s h o u l d be c o n s i d e r e d . V i s u a l t h r e s h o l d e x a m i n a t i o n by p e r i m e t r y i s h i g h l y s u b j e c t i v e . Two i n d i v i d u a l s a r e i n v o l v e d and, hence , two r e a c t i o n t i m e s d e t e r m i n e t h e a c c u r a c y o f t h e d a t a . T h e r e i s a t i m e d e l a y f r o m t h e moment t h e s u b j e c t f i r s t d e t e c t s a change F i g u r e 2.3 S c a n n i n g a c r o s s a v i s u a l d e f e c t 25 i n t a r g e t v i s i b i l i t y t o t h e moment he communicates t h i s t o t h e t e c h n i c i a n . T h e r e i s an a d d i t i o n a l d e l a y f r o m t h e moment t h e t e c h n i c i a n a c k n o w l e d g e s t h e s u b j e c t ' s r e s p o n s e t o t h e moment he a r r e s t s t a r g e t m o t i o n . D u r i n g t h e s e t i m e i n t e r v a l s , t h e t a r g e t i s moving away f r o m i t s c o r r e c t p o s i t i o n a t t h e i n s t a n t of i n i t i a l d e t e c t i o n . T h e r e f o r e , v i s u a l f i e l d d a t a c o l l e c t e d u s i n g k i n e t i c p e r i m e t r y a r e s u b j e c t t o a s m a l l s y s t e m a t i c e r r o r . 2.2 The R e c o n s t r u c t i o n P r o b l e m The p r o b l e m o f p r e s e n t i n g 3D d a t a c a n be r e g a r d e d a s a s u r f a c e r e c o n s t r u c t i o n p r o b l e m . I n t h e c a s e o f v i s u a l f i e l d d a t a , i t i s one o f s u r f a c e r e c o n s t r u c t i o n f r o m a s e t o f c o n t o u r s . The need t o r e c o n s t r u c t a s u r f a c e f r o m c o n t o u r s i s n o t uncommon i n p r a c t i c a l a p p l i c a t i o n s , a t y p i c a l one b e i n g s o l i d o b j e c t r e c o n s t r u c t i o n f r o m p l a n a r s l i c e s i n m e d i c a l i m a g i n g [Cook e t a l . ( 1 9 8 3 ) ] . A g r a p h - t h e o r e t i c a p p r o a c h t o t h i s p r o b l e m i s o u t l i n e d by F u c h s e t a l . ( 1 9 7 7 ) . E a c h c o n t o u r i n a v i s u a l f i e l d c h a r t i s composed o f a s e t of l i n e segments and t h e s e , i n t u r n , a r e d e f i n e d by t h e i r e n d p o i n t s . The s u r f a c e , t h e n , may be r e c o n s t r u c t e d f r o m a s e t of d a t a p o i n t s ( x , y , z ) , whose p r o j e c t i o n s ( x , y ) a r e s c a t t e r e d i r r e g u l a r l y t h r o u g h o u t a domain i n t h e xy p l a n e . T h i s domain i s t h e i n t e r i o r o f t h e convex h u l l o f t h e s e t o f ( x , y ) p o i n t s . A c t u a l l y , t h e o r i g i n a l raw d a t a , a s c o l l e c t e d by t h e m e d i c a l t e c h n i c i a n , a r e j u s t s c a t t e r e d p o i n t s . I t i s t h e t e c h n i c i a n who p r o d u c e s c o n t o u r s by manual i n t e r p o l a t i o n . A s u r f a c e may be f i t t e d t o a s e t o f d a t a p o i n t s s u c h t h a t 2 6 i t e i t h e r p a s s e s t h r o u g h t h e p o i n t s o r n e a r them. The f o r m e r i s c a l l e d i n t e r p o l a t i o n ; t h e l a t t e r a p p r o x i m a t i o n . A c h o i c e must be made between t h e s e two schemes. I n t e r p o l a t i o n i s p e r f o r m e d when t h e d a t a a r e a c c u r a t e and c o n f i d e n c e i s h i g h t h a t t h e s u r f a c e p a s s e s t h r o u g h t h e d a t a , o r when i t i s d e s i r a b l e f o r o t h e r r e a s o n s t o p r e s e r v e t h e o r i g i n a l d a t a . A p p r o x i m a t i o n i s p e r f o r m e d when t h e d a t a a r e s u b j e c t t o e r r o r , and a s u r f a c e p a s s i n g t h r o u g h them would n o t be a f a i t h f u l r e p r e s e n t a t i o n o f t h e i r b e h a v i o u r . Many methods a r e a v a i l a b l e f o r p e r f o r m i n g e i t h e r i n t e r p o l a t i o n o r a p p r o x i m a t i o n . T h e s e a r e c l a s s i f i e d i n t o two g r o u p s : g l o b a l methods o r l o c a l methods. G l o b a l methods r e c o n s t r u c t t h e s u r f a c e h e i g h t z a t an a r b i t r a r y p o i n t P = ( x , y ) from a l l g i v e n d a t a p o i n t s i n t h e domain. L o c a l methods r e c o n s t r u c t t h e h e i g h t a t P f r o m r e l a t i v e l y n e a r b y d a t a p o i n t s , from p o i n t s whose p r o j e c t i o n s f a l l w i t h i n a s m a l l n e i g h b o u r h o o d a b o u t P. G l o b a l methods a r e b e s t t o a c h i e v e an o v e r a l l s m o o t h i n g o f th e s u r f a c e . L o c a l , s u b t l e s u r f a c e f e a t u r e s c a n be masked by a g l o b a l t r e n d t o w h i c h a l l t h e d a t a p o i n t s c o n t r i b u t e . B e c a u s e l o c a l f e a t u r e s , w h i c h may i n d i c a t e s m a l l o r s u b t l e v i s u a l f i e l d d e f e c t s , a r e o f g r e a t i m p o r t a n c e t o an o p h t h a l m o l o g i s t , a l o c a l method i s u s e d i n t h e r e c o n s t r u c t i o n p r o c e s s . D e s p i t e t h e e r r o r i n h e r e n t i n v i s u a l f i e l d d a t a , an i n t e r p o l a t i o n scheme i s employed so t h a t t h e o r i g i n a l v i s u a l f i e l d c o n t o u r s a r e c o n s i s t e n t w i t h t h e c o n t o u r s o f t h e r e c o n s t r u c t e d s u r f a c e . T h i s w i l l e n a b l e c o r r e c t s u p e r p o s i t i o n 27 o f t h e o r i g i n a l c o n t o u r s o n t o a s y n t h e s i z e d image o f t h e r e c o n s t r u c t e d s u r f a c e . 2.3 S u r f a c e R e p r e s e n t a t i o n S u r f a c e r e c o n s t r u c t i o n by l o c a l i n t e r p o l a t i o n i s p e r f o r m e d by d e t e r m i n i n g t h e s u r f a c e h e i g h t a t an a r b i t r a r y p o i n t P = ( x , y ) i n t h e domain f r o m d a t a p o i n t s t h a t f a l l w i t h i n a s m a l l n e i g h b o u r h o o d a b o u t P. The o r g a n i z a t i o n o f n e i g h b o u r h o o d s i n t h e domain depends upon t h e s e l e c t i o n o f a s u r f a c e r e p r e s e n t a t i o n . Two common r e p r e s e n t a t i o n s f o r s u r f a c e s d e f i n e d o v e r i r r e g u l a r d a t a a r e : a r e g u l a r g r i d o f h e i g h t s o r an i r r e g u l a r network o f p a t c h e s . T h e r e a r e a d v a n t a g e s and d i s a d v a n t a g e s w i t h e i t h e r r e p r e s e n t a t i o n . S u r f a c e h e i g h t s i n a r e g u l a r g r i d a r e s p e c i f i e d a t t h e v e r t i c e s , o r g r i d p o i n t s , o f c o n g r u e n t , p o l y g o n a l t i l e s t h a t c o v e r t h e domain o f t h e s u r f a c e . The t i l e s may be t r i a n g l e s , r e c t a n g l e s , o r h e x a g o n s . The h e i g h t s a t g r i d p o i n t s a r e i n t e r p o l a t e d f r o m h e i g h t s a t g i v e n d a t a p o i n t s , w h i c h g e n e r a l l y do n o t c o i n c i d e w i t h g r i d l o c a t i o n s . In o r d e r t o c a p t u r e q u i c k l y v a r y i n g s u r f a c e f e a t u r e s i n t h i s r e p r e s e n t a t i o n , a f i n e g r i d s p a c i n g must be u s e d , w h i c h f o r c e s d a t a r e d u n d a n c y i n r e g i o n s where t h e s u r f a c e i s v a r y i n g s l o w l y . A r e g u l a r g r i d r e p r e s e n t a t i o n , t h e r e f o r e , i s n o t s t o r a g e e f f i c i e n t . Mark (1978) a r g u e s t h a t a p r o p e r l y d e s i g n e d d a t a s t r u c t u r e s h o u l d r e f l e c t t h e phenomenon b e i n g r e p r e s e n t e d . The phenomenon, i n t h i s c a s e , i s t h e human v i s u a l f i e l d . H a r t and H a r t z (1982) d e s c r i b e t h i s phenomenon w i t h t e r r a i n a t t r i b u t e s . 28 They use d e s c r i p t o r s s u c h a s " c l i f f " , " h i l l o c k " , " p l a t e a u " , and " t r o u g h " . I f t h e v i s u a l f i e l d c a n be c o n c e p t u a l i z e d a s i r r e g u l a r t e r r a i n , t h e n a d a t a s t r u c t u r e c o n s i s t e n t w i t h s u c h a phenomenon s h o u l d be emplo y e d . D e s p i t e s u f f e r i n g f r o m s t o r a g e i n e f f i c i e n c y and m o d e l l i n g i n c o n s i s t e n c y , t h e r e g u l a r g r i d e n j o y s p o p u l a r i t y b e c a u s e o f i t s machine c o m p a t i b i l i t y and programming c o n v e n i e n c e . The m a t r i x s t r u c t u r e i s c o m p a t i b l e w i t h l i n e a r memory o r g a n i z a t i o n , and a c c e s s i n g m a t r i x e l e m e n t s from a p r o g r a m i s b o t h s i m p l e and e f f i c i e n t . A p a t c h r e p r e s e n t a t i o n of a s u r f a c e , on t h e o t h e r hand, c a n be d e v e l o p e d by p a r t i t i o n i n g t h e domain o f s c a t t e r e d d a t a p o i n t s i n a number o f ways. A network o f i r r e g u l a r l y s h a p e d p o l y g o n s c a n be c o n s t r u c t e d s u c h t h a t e a c h d a t a p o i n t l i e s i n t h e i n t e r i o r o f a p o l y g o n , o r s u c h t h a t t h e d a t a p o i n t s c o i n c i d e w i t h p o l y g o n v e r t i c e s . A s i m p l e and common p a r t i t i o n o f a s e t o f s c a t t e r e d p o i n t s i s t r i a n g u l a t i o n . The domain i s p a r t i t i o n e d i n t o a network o f m u t u a l l y d i s j o i n t , i r r e g u l a r l y s h a p e d t r i a n g l e s . By m u t u a l l y d i s j o i n t i s meant t h a t t h e i n t e r i o r s o f any two t r i a n g l e s do n o t o v e r l a p . When a d j a c e n t t r i a n g l e s i n t e r s e c t , t h e y do so o n l y a l o n g an e n t i r e , common edge. The t r i a n g u l a t e d i r r e g u l a r n e t w o r k , o r TIN, a s i t i s sometimes c a l l e d [ P e u c k e r e t a l . ( 1 9 7 8 ) ] , i s r e s o l u t i o n -a d a p t i v e ; t h a t i s , i t c a n be a d a p t e d t o t h e v a r y i n g c o m p l e x i t y o f a s u r f a c e . Many s m a l l t r i a n g l e s a r e n e c e s s a r y t o r e p r e s e n t a s u r f a c e r e g i o n o f f i n e d e t a i l , whereas a few l a r g e t r i a n g l e s a r e 29 s u f f i c i e n t t o c o v e r a u n i f o r m r e g i o n . T h i s a d a p t a b i l i t y o f r e s o l u t i o n makes t h e TIN r e p r e s e n t a t i o n more s t o r a g e e f f i c i e n t t h a n t h e d e n s e , r e g u l a r g r i d s t r u c t u r e . F u r t h e r m o r e , i t i s c o n s i s t e n t w i t h t h e method o f v i s u a l f i e l d d a t a c o l l e c t i o n . The m e d i c a l t e c h n i c i a n i n c r e a s e s t h e t a r g e t s c a n d e n s i t y i n r e g i o n s where t h e v i s u a l f i e l d i s c h a n g i n g r a p i d l y , t h u s g e n e r a t i n g more d a t a p o i n t s i n t h e s e r e g i o n s . In r e g i o n s o f l i t t l e c h a n g e , t h e d a t a i s s p a r s e . The i r r e g u l a r s t r u c t u r e o f t h e t r i a n g u l a t e d n e twork i s a more c o n s i s t e n t r e p r e s e n t a t i o n o f an i r r e g u l a r s u r f a c e t h a n t h e r e g u l a r g r i d . F u r t h e r m o r e , s u r f a c e f e a t u r e s o f h i g h i n f o r m a t i o n c o n t e n t c a n be e n c o d e d i n t o t h e d a t a s t r u c t u r e w i t h o u t a d d i t i o n a l s t o r a g e o v e r h e a d . T r i a n g l e e dges c a n be made t o c o r r e s p o n d t o s u r f a c e b r e a k l i n e s , l i n e s a l o n g w h i c h a s u r f a c e e x h i b i t s sudden c h a n g e s i n s l o p e , s u c h a s r i d g e l i n e s o r s t r e a m l i n e s . In t h i s way, t h e " p h y s i c a l " s t r u c t u r e o f t h e s u r f a c e c a n be m o d e l l e d by t h e a c t u a l d a t a s t r u c t u r e . F o r an i l l u s t r a t i o n o f how t r i a n g l e e dges c a n model s u r f a c e b r e a k l i n e s , see F i g u r e 2.4. B e c a u s e o f i t s m o d e l l i n g c o n s i s t e n c y and r e s o l u t i o n a d a p t a b i l i t y , a TIN s u r f a c e r e p r e s e n t a t i o n i s u s e d 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 . D e s p i t e t h e s e s t r e n g t h s , t h e TIN s u f f e r s one s e r i o u s d i s a d v a n t a g e . I t i s not u n i q u e ; t h e r e a r e many t r i a n g u l a t i o n s o f a g i v e n p o i n t s e t . T h e r e f o r e , a g i v e n d a t a s e t may have many d i f f e r e n t s u r f a c e r e p r e s e n t a t i o n s . The g o a l i s t o c h o o s e a t r i a n g u l a t i o n t h a t p r o d u c e s a s u r f a c e most c o n s i s t e n t w i t h t h e d a t a . How i s t h i s c h o i c e t o be made? 30 F i g u r e 2.4 A s s o c i a t i n g s u r f a c e f e a t u r e s w i t h t r i a n g l e e d g e s [ f r o m H e i l and B r y c h ( 1 9 7 8 ) ] 31 2.3.1 T r i a n q u l a t i o n C r i t e r i a A f i r s t s t e p t o w a r d s p r o d u c i n g a u n i q u e t r i a n g u l a t i o n i s t o s u b j e c t t h e t r i a n g u l a t i o n p r o c e s s t o c o n s t r a i n t . Many c r i t e r i a e x i s t and, i n g e n e r a l , d i f f e r e n t c r i t e r i a may p r o d u c e d i f f e r e n t t r i a n g u l a t i o n s . A c r i t e r i o n may be d e f i n e d l o c a l l y and a p p l i e d t h r o u g h o u t t h e domain w i t h t h e o b j e c t i v e o f a t t a i n i n g some g l o b a l optimum. A few l o c a l c r i t e r i a a r e e x a m i n e d h e r e a s t o t h e i r e f f e c t upon a c o n v e x q u a d r i l a t e r a l , w h i c h c a n be p a r t i t i o n e d i n t o two a d j a c e n t t r i a n g l e s i n two ways. One t r i a n g u l a t i o n c r i t e r i o n n o t e d by B a r n h i l l (1977) employs an e l o n g a t i o n measure g i v e n by t h e r a t i o P 2/A where P i s a t r i a n g l e ' s p e r i m e t e r and A i t s a r e a . The q u a d r i l a t e r a l i s p a r t i t i o n e d s u c h t h a t t h e maximum e l o n g a t i o n measure of t h e r e s u l t i n g t r i a n g l e s i s m i n i m i z e d . The a p p l i c a t i o n o f a max-min a n g l e c r i t e r i o n s e l e c t s t h a t p a r t i t i o n w h i c h m a x i m i z e s t h e minimum i n t e r i o r a n g l e o f t h e two r e s u l t i n g t r i a n g l e s . A p p l i c a t i o n o f a c i r c l e c r i t e r i o n r e q u i r e s t h a t a c i r c l e be p a s s e d t h r o u g h t h r e e o f t h e q u a d r i l a t e r a l v e r t i c e s . I f t h e f o u r t h v e r t e x l i e s w i t h i n t h e c i r c l e , t h e n t h e q u a d r i l a t e r a l i s p a r t i t i o n e d w i t h t h e d i a g o n a l j o i n i n g t h i s v e r t e x t o t h e one o p p o s i t e i t . I f t h e f o u r t h v e r t e x l i e s o u t s i d e t h e c i r c l e , t h e o t h e r d i a g o n a l i s c h o s e n . The same p a r t i t i o n r e s u l t s i r r e s p e c t i v e o f w h i c h s e t o f t h r e e v e r t i c e s i s u s e d t o c o n s t r u c t t h e c i r c l e , u n l e s s a l l f o u r p o i n t s l i e on t h e c i r c l e , i n w h i c h c a s e t h e c h o i c e o f d i a g o n a l i s a r b i t r a r y . Y e t a n o t h e r c r i t e r i o n makes use o f p r o x i m i t y r e g i o n s . E a c h 32 q u a d r i l a t e r a l v e r t e x l i e s w i t h i n a u n i q u e p r o x i m i t y r e g i o n whose i n t e r i o r p o i n t s l i e c l o s e r t o i t t h a n t o any o f t h e o t h e r v e r t i c e s . T h e s e r e g i o n s a r e c a l l e d T h i e s s e n r e g i o n s . I f two o f th e T h i e s s e n r e g i o n s i n t e r s e c t i n a l i n e segment, t h e n t h e v e r t i c e s w i t h i n t h e s e r e g i o n s a r e c o n n e c t e d t o p a r t i t i o n t h e q u a d r i l a t e r a l . The T h i e s s e n r e g i o n s s u r r o u n d i n g t h e o t h e r two v e r t i c e s w i l l i n t e r s e c t i n one p o i n t . I f a l l f o u r T h i e s s e n r e g i o n s meet a t one p o i n t , t h e n t h e i r v e r t i c e s l i e on t h e same c i r c l e and t h e p a r t i t i o n s e l e c t i o n i s a r b i t r a r y . Lawson (1977) shows t h a t t h e max-min a n g l e c r i t e r i o n , t h e c i r c l e c r i t e r i o n , a nd t h e T h i e s s e n r e g i o n c r i t e r i o n a r e e q u i v a l e n t f o r t h e q u a d r i l a t e r a l . When a p p l i e d t o a l l p a i r s o f a d j a c e n t t r i a n g l e s i n a t r i a n g u l a t i o n , e a c h c r i t e r i o n y i e l d s a t r i a n g u l a t i o n t h a t i s u n i q u e e x c e p t f o r t h o s e l o c a l , a r b i t r a r y p a r t i t i o n s r e s u l t i n g f r o m g r o u p s o f f o u r o r more p o i n t s l y i n g on a common c i r c l e . Such a t r i a n g u l a t i o n i s a D e l a u n a y , o r D i r i c h l e t , t r i a n g u l a t i o n , where a l l n e i g h b o u r i n g T h i e s s e n r e g i o n s m e e t i n g i n a l i n e segment have t h e i r d e f i n i n g d a t a p o i n t s c o n n e c t e d . The D e l a u n a y t r i a n g u l a t i o n i s t h e d u a l o f t h e p a r t i t i o n f o r m e d by t h e T h i e s s e n r e g i o n s t h e m s e l v e s . Such a network o f T h i e s s e n r e g i o n s i s c a l l e d a T h i e s s e n t e s s e l l a t i o n o r a V o r o n o i d i a g r a m . 33 2.3.2 S u r f a c e C o n s i s t e n c y The t r i a n g u l a t i o n c r i t e r i a d i s c u s s e d t h u s f a r a r e d e s i g n e d t o c o n s t r u c t a t r i a n g u l a t i o n d e v o i d o f l o n g t h i n t r i a n g l e s . W h i l e t h i s i s d e s i r a b l e , i t does n o t g u a r a n t e e a s u r f a c e r e p r e s e n t a t i o n c o n s i s t e n t w i t h t h e g i v e n v i s u a l f i e l d d a t a . A f t e r an i n i t i a l D e l a u n a y t r i a n g u l a t i o n i s p e r f o r m e d , a d d i t i o n a l c r i t e r i a may be a p p l i e d t o l o c a l l y a l t e r t h e t r i a n g u l a t i o n . A f i r s t s t e p t o w a r d s g r e a t e r c o n s i s t e n c y l i e s i n f o r c i n g t r i a n g l e e d ges i n t h e t r i a n g u l a t i o n t o c o i n c i d e w i t h c o n t o u r l i n e s e gments. An i n c o n s i s t e n c y a r i s i n g when t h i s i s not done i s i l l u s t r a t e d i n F i g u r e 2.5. In t h e f i g u r e , t h e d o t t e d l i n e , w h i c h l i e s a l o n g an o r i g i n a l v i s u a l f i e l d c o n t o u r , w i l l n o t l i e a l o n g a c o n t o u r o f t h e s u r f a c e r e p r e s e n t e d by t h e t r i a n g u l a t i o n shown. The r e p r e s e n t a t i o n i s c o r r e c t e d i n F i g u r e 2.6 where t r i a n g l e e d ges a r e a l i g n e d w i t h c o n t o u r s egments. F u r t h e r c o n s i s t e n c y c a n be a c h i e v e d by f o r c i n g a l i g n m e n t o f t r i a n g l e e d g e s w i t h r i d g e l i n e s and s t r e a m l i n e s , a s p r e v i o u s l y d i s c u s s e d . Even when t h e c o n t o u r c r i t e r i o n i s s a t i s f i e d , an i n c o n s i s t e n t s u r f a c e r e p r e s e n t a t i o n may r e s u l t , a s i l l u s t r a t e d i n F i g u r e 2.7. The d o t t e d l i n e i n t h e f i g u r e l i e s a l o n g a r i d g e l i n e , b u t t h e t r i a n g u l a t i o n a s shown d e s c r i b e s a s u r f a c e t h a t e x h i b i t s t e r r a c i n g a l o n g t h e d o t t e d l i n e . The t r i a n g u l a t i o n i s c o r r e c t e d i n F i g u r e 2.8 where t r i a n g l e edges a r e a l i g n e d w i t h t h e r i d g e l i n e . D e s p i t e t h e s e m e a s u r e s , s u r f a c e c o n s i s t e n c y c a n n o t be g u a r a n t e e d where d a t a a r e few and s p a r s e . Lawson (1977) g i v e s a F i g u r e 2.6 T r i a n g u l a t i o n c o n s i s t e n t w i t h s u r f a c e c o n t o u r F i g u r e 2.7 S u r f a c e i n c o n s i s t e n c y a l o n g r i d g e l i n e F i g u r e 2.8 T r i a n g u l a t i o n c o n s i s t e n t w i t h r i d g e l i n e 36 good example o f how a r t i f a c t s i n a s u r f a c e r e c o n s t r u c t i o n c a n be c r e a t e d by a d a t a d i s t r i b u t i o n c o n t a i n i n g r e g i o n s o f l i t t l e o r no d a t a . The m e d i c a l t e c h n i c i a n c o l l e c t i n g v i s u a l f i e l d d a t a must e n s u r e a t a r g e t s c a n d e n s i t y s u f f i c i e n t t o a l l o w a c c u r a t e r e c o n s t r u c t i o n i n a r e a s o f i n t e r e s t . The v i s u a l f i e l d c h a r t s u s e d i n t h i s t h e s i s t y p i c a l l y c o n t a i n o n l y a b o u t 200 p o i n t s . 2.3.3 T r i a n g u l a t i o n P r o c e d u r e A t r i a n g u l a t i o n a l g o r i t h m , d e v e l o p e d by F o w l e r (1977) and i m p l e m e n t e d i n a computer p r o g r a m , was o b t a i n e d , and i s u s e d 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 . A 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 and t h e d a t a s t r u c t u r e i t c r e a t e s i s c o n t a i n e d i n A p p e n d i x A. A p u b l i s h e d a c c o u n t o f t h e a l g o r i t h m may be f o u n d i n G r e e n and S i b s o n ( 1 9 7 8 ) . A f e a t u r e e x i s t s whereby t h e i n i t i a l D e l a u n a y t r i a n g u l a t i o n p r o d u c e d by t h e p r o g r a m c a n be a l t e r e d . I n p u t i s s p e c i f i e d by l i s t s o f v e r t i c e s t o be j o i n e d a s t r i a n g l e e d ges i n a new t r i a n g u l a t i o n . I f t h e v e r t i c e s a r e n o t a l r e a d y c o n n e c t e d , t h e t r i a n g u l a t i o n i s m o d i f i e d l o c a l l y t o s a t i s f y t h e new c o n s t r a i n t s . S p e c i f i c a t i o n o f c o n t o u r segments t o be a l i g n e d w i t h t r i a n g l e e d g e s i s s t r a i g h t - f o r w a r d , b u t d e t e r m i n a t i o n o f r i d g e l i n e s and s t r e a m l i n e s i s l e s s t r i v i a l . A p o i n t a t w h i c h a c o n t o u r e x h i b i t s h i g h c u r v a t u r e i s a c a n d i d a t e r i d g e p o i n t o r s t r e a m p o i n t . H i g h - c u r v a t u r e c a n d i d a t e s o f t h e same t y p e ( i . e . r i d g e o r s t r e a m ) on a d j a c e n t c o n t o u r s may be c o n n e c t e d t o form a l i n e i f t h e y a r e s u f f i c i e n t l y c l o s e . An example o f h i g h -37 c u r v a t u r e c o n t o u r p o i n t s c o n n e c t e d t o form a r i d g e l i n e i s shown i n F i g u r e 2.8. In t h e c u r r e n t i m p l e m e n t a t i o n , h i g h - c u r v a t u r e c a n d i d a t e s on c o n t o u r s a r e d e t e r m i n e d a u t o m a t i c a l l y and d i s p l a y e d a g a i n s t a v i s u a l f i e l d c o n t o u r map, b u t t h e r i d g e l i n e s and s t r e a m l i n e s a r e e x t r a c t e d by i n s p e c t i o n and e n t e r e d i n t o f i l e s by k e y b o a r d . F u r t h e r work i s r e q u i r e d f o r t h e d e v e l o p m e n t o f a c r i t e r i o n t o e n a b l e a u t o m a t i c e x t r a c t i o n o f b r e a k l i n e s f r o m h i g h - c u r v a t u r e c o n t o u r p o i n t s . A t r i a n g u l a t i o n , s a t i s f y i n g t h e c o n t o u r a n d b r e a k l i n e c r i t e r i a , o f t h e v i s u a l f i e l d d a t a shown i n F i g u r e 1.1 i s i l l u s t r a t e d i n F i g u r e 2.9. 2.4 S u r f a c e I n t e r p o l a t i o n Once a n etwork o f t r i a n g u l a r p a t c h e s has been c o n s t r u c t e d , a f u n c t i o n f o r i n t e r p o l a t i n g s u r f a c e h e i g h t s a t a r b i t r a r y p o i n t s w i t h i n t h e p a t c h e s must be c h o s e n . A n o t h e r a d v a n t a g e o f u s i n g a p a t c h s u r f a c e r e p r e s e n t a t i o n i s t h e o p p o r t u n i t y t o t r y d i f f e r e n t i n t e r p o l a t i n g f u n c t i o n s u n t i l one t h a t y i e l d s a v i s u a l l y a c c e p t a b l e image i s f o u n d . A s u r f a c e composed o f p l a n a r p a t c h e s i s c o n t i n u o u s b u t n o t smooth. To e n s u r e t h a t t h e s u r f a c e i s smooth a c r o s s p a t c h seams, an i n t e r p o l a n t t h a t p r e s e r v e s c o n t i n u i t y o f f i r s t - o r d e r d e r i v a t i v e s a l o n g p a t c h b o u n d a r i e s may be u s e d . A c o m p u t e r p r o g r a m f o r p e r f o r m i n g smooth i n t e r p o l a t i o n o v e r t r i a n g l e s was a l s o o b t a i n e d , and i s u s e d f o r s u r f a c e r e c o n s t r u c t i o n 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 . To s a t i s f y t h e C 1 F i g u r e 2.9 A t r i a n g u l a t i o n o f v i s u a l f i e l d d a t a 39 smoothness c r i t e r i o n , t h e p r o g ram employs a n i n e - p a r a m e t e r , t r i a n g u l a r s u r f a c e e l e m e n t d e v e l o p e d by N i e l s o n ( 1 9 8 0 ) . N i n e p i e c e s o f d a t a a r e r e q u i r e d t o e v a l u a t e t h e c o e f f i c i e n t s o f t h i s i n t e r p o l a n t . They a r e d e r i v e d f r o m t h e f u n c t i o n a l v a l u e s ( o r s u r f a c e h e i g h t s ) a t t h e t r i a n g l e v e r t i c e s , and t h e p a r t i a l d e r i v a t i v e s w i t h r e s p e c t t o x and y a t t h e v e r t i c e s . The f u n c t i o n v a l u e s a t t h e v e r t i c e s a r e known, but t h e d e r i v a t i v e s a r e e s t i m a t e d by t h e l e a s t - s q u a r e s f i t t i n g o f a p l a n e t o e a c h v e r t e x and i t s immediate n e i g h b o u r s . The N i e l s o n i n t e r p o l a n t i s d i s c u s s e d i n more d e t a i l i n A p p e n d i x B. The image s y n t h e s i s p r o c e s s o p e r a t e s on a s e t o f sampled, s u r f a c e p r o f i l e c u r v e s p a r a l l e l t o e i t h e r t h e x o r y a x i s . Such a g r i d o f s u r f a c e s a m p l e s i s o b t a i n e d by i n t e r p o l a t i n g t h e s u r f a c e a t p o i n t s a l o n g a r a s t e r s c a n o f i t s domain, where t h e s c a n l i n e s a r e p r o j e c t i o n s o f t h e s u r f a c e p r o f i l e s o n t o t h e xy p l a n e . A t y p e o f s c a n - l i n e c o h e r e n c e i s employed t o a v o i d r e p e t i t i o n o f p a r a m e t e r c o m p u t a t i o n f o r t r i a n g u l a r p a t c h e s from one s c a n l i n e t o t h e n e x t . The p a r a m e t e r s f o r any t r i a n g u l a r p a t c h a r e not d i s c a r d e d u n t i l t h e r a s t e r s c a n e x i t s t h e p a t c h ' s p r o j e c t i o n i n t h e domain. 2.5 Summary The p r o b l e m o f i l l u s t r a t i n g t h e b e h a v i o u r o f v i s u a l f i e l d d a t a i s c o n s i d e r e d one o f s u r f a c e r e c o n s t r u c t i o n f r o m d a t a s c a t t e r e d i r r e g u l a r l y o v e r a p l a n e . D e s p i t e t h e e r r o r i n h e r e n t i n t h e d a t a c o l l e c t i o n p r o c e s s , an i n t e r p o l a t i o n , a s o p p o s e d t o an a p p r o x i m a t i o n , scheme i s u s e d i n r e c o n s t r u c t i o n . T h i s 40 e n s u r e s t h a t t h e v i s u a l f i e l d c o n t o u r s t r a c e d by t h e m e d i c a l t e c h n i c i a n a r e c o n s i s t e n t w i t h t h e c o n t o u r s o f t h e r e c o n s t r u c t e d s u r f a c e . The i n t e r p o l a t i o n i s p e r f o r m e d l o c a l l y so t h a t any l o c a l , s u b t l e s u r f a c e f e a t u r e s , w h i c h a r e o f i m p o r t a n c e t o t h e o p h t h a l m o l o g i s t , a r e n o t smoothed o v e r by g l o b a l s u r f a c e t r e n d s . The i n t e r p o l a t i o n i s p e r f o r m e d o v e r s m a l l , i r r e g u l a r l y s h aped, t r i a n g u l a r sub-domains i n t h e p l a n e . T h e s e t r i a n g l e s a r e o r g a n i z e d i n t o a u n i q u e network c a l l e d a D e l a u n a y t r i a n g u l a t i o n . To e n s u r e a s u r f a c e . r e p r e s e n t a t i o n t h a t i s a s c o n s i s t e n t as p o s s i b l e w i t h t h e v i s u a l f i e l d d a t a , t h e t r i a n g u l a t i o n p r o c e s s i s c o n s t r a i n e d . T r i a n g l e e d g e s a r e a l i g n e d w i t h c o n t o u r l i n e segments and w i t h s u r f a c e b r e a k l i n e s s u c h as r i d g e l i n e s and s t r e a m l i n e s ; t h e s e b r e a k l i n e s a r e e x t r a c t e d from t h e v i s u a l f i e l d c o n t o u r map. The s u r f a c e r e p r e s e n t a t i o n , t h e n , i s a p a t c h w o r k o f s u r f a c e e l e m e n t s d e f i n e d o v e r i r r e g u l a r t r i a n g l e s . The p a t c h e s a r e s m o o t h l y j o i n e d a t t h e seams so t h a t a v i s u a l l y a c c e p t a b l e image o f t h e s u r f a c e may l a t e r be s y n t h e s i z e d . Smoothness i s e n s u r e d by p r e s e r v i n g c o n t i n u i t y o f f i r s t - o r d e r p a r t i a l d e r i v a t i v e s a c r o s s p a t c h b o u n d a r i e s . A n i n e - p a r a m e t e r s u r f a c e e l e m e n t [ N i e l s o n ( 1 9 8 0 ) ] , w h i c h s a t i s f i e s t h i s C 1 c r i t e r i o n , i s u s e d o v e r e a c h p a t c h . 41 I I I . IMAGE SYNTHESIS A d i s p l a y p r o g ram i s u s e d t o g e n e r a t e images o f s u r f a c e s r e c o n s t r u c t e d f r o m v i s u a l f i e l d d a t a . A l t h o u g h t h e s u r f a c e s a p p e a r i l l u m i n a t e d by a s i n g l e , d i s t a n t l i g h t s o u r c e , more complex l i g h t s o u r c e d i s t r i b u t i o n s may be m o d e l l e d . Images a r e s y n t h e s i z e d by p r o j e c t i n g s u r f a c e e l e m e n t s o n t o p i x e l s i n a s c r e e n p l a n e , and s h a d i n g o n l y t h o s e p i x e l s c o r r e s p o n d i n g t o v i s i b l e s u r f a c e e l e m e n t s . The d i s p l a y p r o c e s s , t h e n , c a n be d i v i d e d i n t o t h r e e p a r t s : p r o j e c t i o n , h i d d e n s u r f a c e r e m o v a l , and s h a d i n g . 3.1 P r o j e c t i o n T r a n s f o r m a t i o n s An image of a s u r f a c e i s s y n t h e s i z e d by p r o j e c t i n g t h e s u r f a c e o n t o a v i e w p l a n e . The s u r f a c e , d e f i n e d i n a r i g h t -handed ( x , y , z ) C a r t e s i a n c o o r d i n a t e s y s t e m , i s f i r s t t r a n s f o r m e d i n t o a l e f t - h a n d e d ^ x v ' v v » z v ^ v i e w e r - c e n t e r e d c o o r d i n a t e s y s t e m , s u c h t h a t t h e l i n e of s i g h t l i e s a l o n g t h e p o s i t i v e z y a x i s . S u r f a c e p o i n t s a r e t r a n s f o r m e d t o t h e v i e w e r c o o r d i n a t e s y s t e m by a s e r i e s o f g e o m e t r i c t r a n s f o r m a t i o n s . These t r a n s f o r m a t i o n s a r e o u t l i n e d i n Newman and S p r o u l l (1979) f o r a g i v e n v i e w p o i n t . In t h e c u r r e n t i m p l e m e n t a t i o n , t h e v i e w p o i n t i s c o n s t r a i n e d t o t h e h a l f - s p a c e z > 0. A f t e r c o o r d i n a t e t r a n s f o r m a t i o n , t h e s u r f a c e p o i n t s a r e p r o j e c t e d o n t o a v i e w p l a n e p e r p e n d i c u l a r t o t h e l i n e o f s i g h t ( s e e F i g u r e 3 . 1 ) . Two common p r o j e c t i o n s a r e t h e p e r s p e c t i v e 42 F i g u r e 3 . 1 S u r f a c e p r o j e c t i o n 4 3 and o r t h o g r a p h i c p r o j e c t i o n s . A l t h o u g h c o m p u t a t i o n a l l y e x p e n s i v e , the p e r s p e c t i v e p r o j e c t i o n i s p o p u l a r because i t produces more r e a l i s t i c images than the o r t h o g r a p h i c p r o j e c t i o n . I f , however, viewed o b j e c t s a r e a l i e n t o human e x p e r i e n c e , such as the a b s t r a c t s u r f a c e s r e p r e s e n t i n g v i s u a l f i e l d d a t a , t h e n , as F o r r e s t (1979) s a y s , " p e r s p e c t i v e i s of l i t t l e use, s i n c e u n l e s s we can r e l a t e a p e r s p e c t i v e image of the s u r f a c e t o a p e r s p e c t i v e image of an o b j e c t of known shape, we cannot t e l l whether we a r e v i e w i n g i n p e r s p e c t i v e or merely v i e w i n g an o r t h o g o n a l p r o j e c t i o n of some d i s t o r t e d shape." For t h i s r e a s o n , as w e l l as f o r s i m p l i c i t y , t h e o r t h o g r a p h i c p r o j e c t i o n i s used 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 . The p r o j e c t i o n i s s i m p l y g i v e n by U = x y and V = y where (U,V) a r e the view p l a n e c o o r d i n a t e s t o which the s u r f a c e p o i n t ( x , y , z ) i s t r a n s f o r m e d . These (U,V) c o o r d i n a t e s a r e then s c a l e d and t r a n s l a t e d t o y i e l d s c r e e n c o o r d i n a t e s ( X , Y ) , which a r e j u s t i n d i c e s i n t o a frame b u f f e r . Many s u r f a c e p o i n t s may p r o j e c t onto the same (X,Y) s c r e e n l o c a t i o n . The problem i s t o determine which of t h e s e p o i n t s appears i n the p i x e l a t t h a t l o c a t i o n so t h a t none of the hidden s u r f a c e p o i n t s i s i n c o r r e c t l y d i s p l a y e d . T h i s , of c o u r s e , i s the c l a s s i c h i dden s u r f a c e problem. A f t e r a s u r f a c e p o i n t i s deemed v i s i b l e , the shade of the c o r r e s p o n d i n g p i x e l must be computed. 44 3.2 Hidden Surface Removal F o l e y and van Dam (1982) survey s e v e r a l hidden s u r f a c e a l g o r i t h m s f o r d i s p l a y i n g s u r f a c e s modelled by p l a n a r p o l y g o n a l patches. Lane et a l . (1980) g e n e r a l i z e polygon-based a l g o r i t h m s to handle s u r f a c e s composed of curved, i n s t e a d of p l a n a r , patches. These algori t h m s are intended to d i s p l a y g e n e r a l 3D o b j e c t s ; however, to d i s p l a y a s u r f a c e r e p r e s e n t a b l e by a s i n g l e - v a l u e d f u n c t i o n of two v a r i a b l e s , simpler a l g o r i t h m s are a v a i l a b l e . Such an a l g o r i t h m i s used i n the c u r r e n t implementation f o r d i s p l a y i n g v i s u a l f i e l d s u r f a c e s . The a l g o r i t h m employs what can be thought of as a r e c e d i n g h o r i z o n . A v e r t i c a l plane p e r p e n d i c u l a r to the view plane i s passed through a column of p i x e l s i n the screen plane. T h i s scan plane i n t e r s e c t s the s u r f a c e i n a p r o f i l e curve, which i s sampled at d i s c r e t e p o i n t s (see F i g u r e 3.2). In the f i g u r e , the c l o s e s t s u r f a c e p o i n t to the viewer i s = ( x ^ y ^ z , ) . T h i s p o i n t i s p r o j e c t e d along the l i n e of s i g h t to the p o i n t P,'- = ( X J Y T ) i n the image pla n e . The v e r t i c a l component Y , i s the i n i t i a l value of the c u r r e n t h o r i z o n l e v e l f o r scan plane X ( i . e . H ( X ) = Y ^ . Since t h i s p o i n t i s the c l o s e s t to the viewer, i t must be v i s i b l e and i s mapped to a p i x e l i n the frame b u f f e r . The next c l o s e s t p r o f i l e p o i n t P2 = ( x 2 , y 2 , z 2 ) i s then examined. T h i s s u r f a c e p o i n t p r o j e c t s to p o i n t P2' = ( X , Y 2 ) i n the image p l a n e . Since Y 2 i s higher than the c u r r e n t h o r i z o n l e v e l H ( X ) , p o i n t P2 i s v i s i b l e and i s mapped to a p i x e l i n the frame b u f f e r . The c u r r e n t h o r i z o n i s updated to t h i s new l e v e l H ( X ) = Y 2 . The next p r o f i l e p o i n t P3 p r o j e c t s to P3' = ( X , Y 3 ) , 45 F i g u r e 3.3 S c a n n i n g a s u r f a c e p r o f i l e a l o n g a g r i d l i n e 46 but b e c a u s e Y 3 i s l o w e r t h a n t h e c u r r e n t h o r i z o n , t h e p o i n t P 3 i s i n v i s i b l e and i s i g n o r e d . T h i s c o n t i n u e s f r o m p o i n t t o p o i n t u n t i l t h e f a r t h e s t p r o f i l e p o i n t has been p r o c e s s e d . The Y c o o r d i n a t e o f e a c h p r o j e c t i o n i s compared w i t h t h e c u r r e n t h o r i z o n l e v e l H ( X ) . I f a p r o j e c t i o n f a l l s above t h e h o r i z o n , t h e p o i n t i s p a i n t e d o n t o t h e image and t h e h o r i z o n l e v e l i s u p d a t e d . I f t h e p r o j e c t i o n f a l l s below t h e h o r i z o n , t h e n e x t p r o f i l e p o i n t i s e x a m i n e d . The p r o c e s s i s p e r f o r m e d f o r e a c h v e r t i c a l p l a n e p a s s i n g t h r o u g h a column o f p i x e l s i n t h e s c r e e n p l a n e . I f t h e r e a r e P p i x e l s i n a h o r i z o n t a l l i n e o f t h e image, t h e n t h e r e a r e P v e r t i c a l s c a n p l a n e s X = X^ . , where i = 1,...,P. At any p o i n t i n t h e p r o c e s s , t h e v e c t o r H ( X . ) , c o n t a i n i n g t h e c u r r e n t h o r i z o n l e v e l s f o r a l l image c o l u m n s , c a n be t h o u g h t o f a s t h e c u r r e n t v i s i b l e h o r i z o n . T h i s h o r i z o n sweeps from f r o n t t o back a c r o s s t h e s u r f a c e , c h a n g i n g whenever t h e s u r f a c e r i s e s above i t . D u r i n g s u r f a c e p r o f i l e s c a n n i n g , p i x e l s a r e s h a d e d from b o t t o m t o t o p i n a column of t h e image. F o r a b r u p t c h a n g e s i n p r o f i l e e l e v a t i o n , gaps may o c c u r w i t h i n a c o l u m n . T h i s c a n be u n d e r s t o o d by a g a i n c o n s i d e r i n g F i g u r e 3.2. I f , i n s c a n n i n g f r o m sample p o i n t P, t o i t s s u c c e s s o r P 2 , t h e p r o j e c t i o n P 2 ' i s more t h a n one p i x e l p o s i t i o n above t h e p r o j e c t i o n P,', a gap o f u n a s s i g n e d p i x e l s e x i s t s between P,' and P 2 ' . I n o r d e r t o f i l l t h i s gap, t h e s u r f a c e must be r e - s a m p l e d a l o n g t h e p r o f i l e between p o i n t s P, and P 2 . An i t e r a t i v e s e a r c h i s made f o r s u r f a c e p o i n t s ( x , y , z ) , whose ( x , y ) c o o r d i n a t e s l i e on t h e l i n e between ( x , , y , ) and ( x 2 , y 2 ) , and t h a t p r o j e c t o n t o a p i x e l 47 l o c a t e d between Y, and Y 2 . F o r c l a r i t y , t h e a l g o r i t h m has been d e s c r i b e d as s c a n n i n g s u r f a c e p r o f i l e s a l o n g t h e v i e w i n g d i r e c t i o n . 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 , t h e d i s p l a y p r o c e s s o p e r a t e s on a r e c t a n g u l a r g r i d o f s u r f a c e h e i g h t s . I n s t e a d of s c a n n i n g i n an a r b i t r a r y d i r e c t i o n a c r o s s t h e s u r f a c e , t h e p r o c e s s s c a n s t h r o u g h a g r i d o f s u r f a c e h e i g h t s a l o n g l i n e s o f c o n s t a n t x o r c o n s t a n t y. P r o j e c t i o n s o f s u r f a c e p o i n t s s c a n n e d a l o n g any one l i n e now s pan more t h a n one p i x e l c olumn i n t h e image ( s e e F i g u r e 3 . 3 ) . A s i m i l a r a l g o r i t h m f o r g e n e r a t i n g 3D p l o t s by g r i d l i n e s c a n n i n g i s d e s c r i b e d by W r i g h t ( 1 9 7 3 ) . The d i s p l a y p r o c e s s o p e r a t e s on a r e c t a n g u l a r g r i d s u r f a c e r e p r e s e n t a t i o n and i s d i v o r c e d f r o m t h e o r i g i n a l TIN model of t h e v i s u a l f i e l d s u r f a c e . B e c a u s e o f t h i s , t h e s u r f a c e must be s c a n n e d t w i c e : once d u r i n g i n t e r p o l a t i o n , and t h e n a g a i n d u r i n g d i s p l a y . F u r t h e r m o r e , i n o r d e r t o f i l l gaps i n image c o l u m n s , s u r f a c e r e - s a m p l i n g must be p e r f o r m e d f r o m e x i s t i n g g r i d s a m p l e s . I n t h e g a p - f i l l i n g p r o c e s s , t h e z v a l u e of an i n t e r m e d i a t e p o i n t i s i n t e r p o l a t e d f r o m t h e f o u r g r i d samples c l o s e s t t o t h a t p o i n t . The s u r f a c e g r a d i e n t a t t h i s i n t e r p o l a t e d p o i n t i s r e q u i r e d f o r t h e s h a d i n g c a l c u l a t i o n , and i s o b t a i n e d f r o m t h e e q u a t i o n o f a b i l i n e a r p a t c h whose c o r n e r s c o i n c i d e w i t h t h e f o u r g r i d n e i g h b o u r s . The s u r f a c e g r a d i e n t a t a v i s i b l e g r i d sample must a l s o be d e t e r m i n e d . S u r f a c e g r a d i e n t must a g a i n be e s t i m a t e d f r o m g r i d s a m p l e s s u r r o u n d i n g t h e v i s i b l e s a m p l e . The g r a d i e n t e s t i m a t o r u s e d 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 i s : 48 p ( x , y ) = [ F ( x + 1 , y ) - F ( x - 1 , y ) ] / 2A q ( x , y ) = [F(x,y+ 1 ) - F ( x , y - 1 ) ] / 2A where [ p ( x , y ) q ( x , y ) ] i s t h e g r a d i e n t a t t h e v i s i b l e s u r f a c e p o i n t ( x , y , F ( x , y ) ) , and where A i s t h e g r i d sample s p a c i n g . O t h e r g r a d i e n t e s t i m a t o r s , w h i c h r e d u c e t h e e f f e c t of l o c a l e r r o r s i n s u r f a c e h e i g h t F ( x , y ) , a r e s u g g e s t e d by Horn ( 1 9 8 1 ) . The e f f e c t o f s u c h g r a d i e n t e s t i m a t o r s on t h e r e s u l t i n g image may w a r r a n t f u r t h e r e x p e r i m e n t a t i o n . The r e c e d i n g - h o r i z o n a l g o r i t h m o p e r a t e s i n image space, and c o n f o r m s t o a s p e c i f i c s c r e e n r e s o l u t i o n . The h o r i z o n v e c t o r c o n t a i n s a t most a s many e l e m e n t s a s a r e p i x e l s i n one h o r i z o n t a l l i n e o f t h e d i s p l a y s c r e e n . The s u r f a c e sample s p a c i n g , t h e r e f o r e , i s bound by t h e s c r e e n r e s o l u t i o n . I t may be a r g u e d t h a t f i n e s u r f a c e f e a t u r e s whose s i z e s a r e o f t h e o r d e r o f t h e sample s p a c i n g may n o t be d e t e c t a b l e i n a low-r e s o l u t i o n image. The zoom f u n c t i o n , , however, a v a i l a b l e 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 , a l l o w s f o r f i n e r s a m p l i n g o v e r s m a l l e r sub-domains of the- s u r f a c e . 3.3 S u r f a c e S h a d i n g A f t e r a s u r f a c e e l e m e n t i s deemed v i s i b l e , t h e p i x e l o n t o w h i c h i t p r o j e c t s must be s h a d e d . The shade o f t h e p i x e l d epends on t h e i n t e n s i t y o f l i g h t r e f l e c t e d f r o m t h e s u r f a c e e l e m e n t . T h i s i n t e n s i t y d e p ends on t h e p o s i t i o n o f t h e l i g h t s o u r c e , t h e t y p e o f l i g h t , t h e p o s i t i o n o f t h e v i e w e r , t h e o r i e n t a t i o n o f t h e s u r f a c e e l e m e n t , an d t h e r e f l e c t a n c e 49 p r o p e r t i e s o f t h e s u r f a c e . S u r f a c e r e f l e c t a n c e d e p e n d s on t h e p h y s i c a l p r o p e r t i e s a n d m i c r o s t r u c t u r e o f t h e s u r f a c e m a t e r i a l , a n d , i n many c a s e s , c a n be s i m p l y m o d e l l e d b y a f u n c t i o n d e p e n d e n t o n l y u p o n t h e g r o s s v i e w i n g g e o m e t r y . T h e o r i e n t a t i o n o f a s u r f a c e e l e m e n t i s g i v e n by i t s n o r m a l v e c t o r o r , e q u i v a l e n t l y , by i t s g r a d i e n t . F o r t h e s u r f a c e z = F ( x , y ) t h e g r a d i e n t a t t h e p o i n t ( x , y ) i s [ F F ] a n d a n x y o u t w a r d ( t o w a r d s t h e p o s i t i v e z a x i s ) n o r m a l t o t h e s u r f a c e a t t h a t p o i n t i s [ - F - F 1 ] , w h e r e F a n d F a r e t h e p a r t i a l c x y x y d e r i v a t i v e s o f t h e f u n c t i o n F w i t h r e s p e c t t o x a n d y . I f F ^ i s d e n o t e d by p , a n d F ^ b y q , t h e n t h e s u r f a c e n o r m a l i s N = [ - p - q 1 ] , P o s i t i v e z c o m p o n e n t s may a l s o be a s s i g n e d t o t h e d i r e c t i o n s V = [ - P V - q 1] t o t h e v i e w e r a n d S = t ~ P 5 n t o t h e l i g h t s o u r c e , s o t h a t t h e s u r f a c e i s i l l u m i n a t e d a n d v i e w e d f r o m " a b o v e " ( i . e . f r o m t h e h a l f - s p a c e z > 0 ) . F o r a v i e w p o i n t a l o n g a n a z i m u t h 6 a n d a n e l e v a t i o n <t>, t h e c o m p o n e n t s o f V a r e : P v = - s i n 0 / tan</> q = - c o s 0 / t a n ^ S i m i l a r r e l a t i o n s e x i s t f o r p a n d q . A n o r t h o g r a p h i c v i e w i s o b t a i n e d w i t h a v i e w i n g d i s t a n c e much g r e a t e r t h a n t h e d i m e n s i o n s o f t h e s u r f a c e . The v e c t o r V , t h e r e f o r e , i s p a r a l l e l t o V - R ( s e e F i g u r e 3.4). A l s o , by p l a c i n g t h e l i g h t s o u r c e a t a g r e a t d i s t a n c e f r o m t h e s u r f a c e , t h e v e c t o r S b e c o m e s p a r a l l e l t o S - R . The v e c t o r s V - R a n d S - R F i g u r e 3.4 V i e w i n g g e o m e t r y F i g u r e 3.5 Geometry f o r o r t h o g r a p h i c v i e w i n g 51 c a n be r e p l a c e d s i m p l y by V and S, r e s p e c t i v e l y . E a c h s u r f a c e e l e m e n t " s e e s " t h e v i e w e r o r t h e l i g h t s o u r c e i n t h e same d i r e c t i o n . O n l y t h e n o r m a l v e c t o r N v a r i e s f r o m e l e m e n t t o e l e m e n t a c r o s s t h e s u r f a c e . The r e s u l t i n g s i m p l i f i e d geometry i s i l l u s t r a t e d i n F i g u r e 3.5, where V and S a r e b o t h d e f i n e d w i t h r e s p e c t t o t h e o r i g i n o f t h e ( x , y , z ) c o o r d i n a t e s y s t e m . The i n c i d e n t a n g l e i i s t h e a n g l e between an i n c i d e n t r a y from t h e l i g h t s o u r c e and t h e s u r f a c e n o r m a l . The emergent a n g l e e i s t h e a n g l e between t h e s u r f a c e n o r m a l and a r a y r e f l e c t e d t o t h e v i e w e r . The i n c i d e n t and emergent r a y s do n o t g e n e r a l l y l i e i n t h e same p l a n e w i t h t h e s u r f a c e n o r m a l , and so a ph a s e a n g l e g i s needed t o d e s c r i b e t h e s e p a r a t i o n between them. The g r o s s v i e w i n g g e o m e t r y , t h e n , i s s p e c i f i e d by t h e v e c t o r s S, V, and N o r by t h e t h r e e a n g l e s i , e, and g. The r e f l e c t a n c e a t any p o i n t on a s u r f a c e c a n be m o d e l l e d by a s i m p l e f u n c t i o n R(p,q) d e p e n d e n t o n l y on t h e a n g l e s i , e, and g, where [-p -q 1] i s t h e s u r f a c e n o r m a l a t t h e p o i n t . A p e r f e c t l y d i f f u s e , o r m a t t e , s u r f a c e a p p e a r s e q u a l l y b r i g h t f r o m any v i e w i n g d i r e c t i o n and has a r e f l e c t a n c e f u n c t i o n o f t h e fo r m : R(p,q) = I c o s ( i ) (3.1) where c o s ( i ) = and where I i s t h e s o u r c e r a d i a n c e (Note t h a t t h e v i e w e r 52 d i r e c t i o n does n o t e n t e r i n t o t h e r e f l e c t a n c e c a l c u l a t i o n ) . A s u r f a c e t h a t e x h i b i t s h i g h l i g h t s can be m o d e l l e d u s i n g t h e o f f - s p e c u l a r a n g l e s between t h e v i e w e r d i r e c t i o n V and t h e d i r e c t i o n M of a s p e c u l a r l y r e f l e c t e d l i g h t r a y ( s e e F i g u r e 3 . 5 ) . The a n g l e i ' between M and t h e s u r f a c e n o r m a l N i s e q u a l t o t h e a n g l e o f i n c i d e n c e i , and t h e v e c t o r s S, N, and M a r e c o p l a n a r . B u i Tuong Phong (1975) d e v e l o p e d t h e f o l l o w i n g r e f l e c t a n c e f u n c t i o n t o s i m u l a t e s u r f a c e h i g h l i g h t s : R(p,q) = I [X c o s ( i ) + ( 1 - X ) c o s " ( s ) ] where n i s a p o s i t i v e i n t e g e r , 0^ X<1, c o s ( s ) = 2 c o s ( i ) c o s ( e ) - c o s ( g ) 1 + p p + q q c o s ( e ) = /1 + P 2 + q 2 /1 + P 2, + q 2 1 + p p + q q c o s ( g ) = — -/ l + p 2 + q 2 /T+ p 2 + q 2 and where c o s ( i ) and I a r e d e f i n e d as f o r E q u a t i o n 3.1. T h i s r e f l e c t a n c e f u n c t i o n i s u s e d t o g e n e r a t e most o f t h e images shown i n t h i s t h e s i s . A l t h o u g h much u s e d , t h i s f u n c t i o n i s e m p i r i c a l l y d e r i v e d and does n o t a d h e r e t o p h y s i c a l law [Horn ( 1 9 8 1 ) ] . A s i m i l a r f u n c t i o n , b u t one w h i c h i s p h y s i c a l l y c o n s i s t e n t , i s g i v e n by: R(p,q) = I [X c o s ( i ) + ( 1 - X ) c o s ( i ) c o s n ( s / 2 ) ] / c o s ( g / 2 ) 53 S p e c u l a r r e f l e c t a n c e i s more s e n s i t i v e t o c h a n g e s i n s u r f a c e g r a d i e n t t h a n m a t t e r e f l e c t a n c e , and t e n d s t o e m p h a s i z e s u r f a c e r e g i o n s o f h i g h c u r v a t u r e . Such r e g i o n s may i n d i c a t e d e f e c t s on a v i s u a l f i e l d s u r f a c e . B e c a u s e t h e s e r e g i o n s a r e o f i n t e r e s t t o t h e o p h t h a l m o l o g i s t , i t i s d e s i r a b l e t h a t t h e y be h i g h l i g h t e d . Shadows c a s t by one p o r t i o n o f t h e s u r f a c e o v e r a n o t h e r a r e n o t r e n d e r e d i n any o f t h e images i n t h i s t h e s i s . C a s t shadows ca n be c a l c u l a t e d by s o l v i n g t h e h i d d e n s u r f a c e p r o b l e m f o r t h e v i e w p o i n t of t h e l i g h t s o u r c e . The argument a g a i n s t u s i n g c a s t shadows i s s i m i l a r t o t h e one a g a i n s t u s i n g t h e p e r s p e c t i v e p r o j e c t i o n , and i s s t a t e d by Horn ( 1 9 8 1 ) : "Shadows c a s t by one c o m p l i c a t e d shape on a n o t h e r a r e h a r d t o i n t e r p r e t ... and a p p a r e n t l y d e t r a c t f r o m t h e v i s u a l q u a l i t y of s h a d e d o v e r l a y s . " 3. 4 C o n t o u r S u p e r p o s i t i o n E a c h o f t h e images, F i g u r e s 1.11 and 1.12 i n C h a p t e r 1, showing o r i g i n a l v i s u a l f i e l d c o n t o u r s s u p e r p o s e d upon t h e s h aded s u r f a c e i s o b t a i n e d by o v e r l a y i n g t h e c o n t o u r s upon t h e s u r f a c e e l e v a t i o n g r i d . The c o n t o u r s a r e f i r s t drawn i n t o a frame b u f f e r . T h i s c o n t o u r map i s t h e n t r a n s l a t e d and s c a l e d s u c h t h a t i t r e g i s t e r s w i t h t h e d ense g r i d g e n e r a t e d by t h e s c a n n i n g - i n t e r p o l a t i o n p r o c e s s . Whenever t h e d i s p l a y p r o c e s s f i n d s a v i s i b l e sample i n t h e g r i d , i t c h e c k s f o r a p o i n t a t t h e c o r r e s p o n d i n g l o c a t i o n i n t h e c o n t o u r map. I f t h e y c o i n c i d e , and t h e h e i g h t o f t h e c o n t o u r p o i n t matches t h a t o f t h e g r i d p o i n t , t h e n t h e c o l o u r a s s o c i a t e d w i t h t h a t h e i g h t i s d i s p l a y e d 54 i n s t e a d o f a g r e y l e v e l . T h i s a p p r o a c h s u f f e r s f r o m t h e d i f f i c u l t y t h a t an e x a c t r e g i s t r a t i o n c a n n o t be e n s u r e d . The m a t c h i n g p r o c e s s i s c o n f o u n d e d by t h e a l i a s i n g o f s t r a i g h t - l i n e segments i n t h e c o n t o u r map. To improve t h e l i k e l i h o o d o f c o r r e c t m a t c h e s , t h e p r o c e s s s e a r c h e s f o r match c a n d i d a t e s w i t h i n s m a l l n e i g h b o u r h o o d s i n t h e c o n t o u r map. Once a p a r t i c u l a r match i s f o u n d , i t i s d e l e t e d from t h e c o n t o u r map so t h a t d i f f e r e n t s e a r c h e s i n o v e r l a p p i n g n e i g h b o u r h o o d s do not a r r i v e a t t h e same c a n d i d a t e . A n o t h e r a p p r o a c h t o t h e c o n t o u r i n g p r o b l e m i s t o e x t r a c t c o n t o u r s d i r e c t l y f r o m t h e g r i d e l e v a t i o n model o f t h e s u r f a c e . A n o i s e - f r e e o p e r a t o r i s r e q u i r e d t o p r o d u c e c o n n e c t e d c o n t o u r c u r v e s o f u n i f o r m w i d t h . Such an o p e r a t o r w o u l d e x t r a c t , i n a d d i t i o n t o t h e o r i g i n a l v i s u a l f i e l d c o n t o u r s , c o n t o u r s o m i t t e d by t h e m e d i c a l t e c h n i c i a n . A l t h o u g h c o r r e c t l y e x t r a c t e d from t h e s u r f a c e model, t h e s e a d d i t i o n a l c o n t o u r s may c o n f u s e t h e o p h t h a l m o l o g i s t who i s c o m p a r i n g t h e o r i g i n a l d a t a w i t h t h e sha d e d s u r f a c e r e p r e s e n t a t i o n . To a v o i d s u c h c o n f u s i o n , t h i s a p p r o a c h i s n o t f o l l o w e d 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 . 3.5 R e a l - T i m e Movement o f t h e L i g h t S o u r c e G i v e n a v i e w i n g s p e c i f i c a t i o n and a l i g h t i n g d i s t r i b u t i o n , an image o f a 3D s u r f a c e i s s y n t h e s i z e d by mapping v i s i b l e s u r f a c e e l e m e n t s i n t o p i x e l s . I f t h e v i e w i n g g e o m e t r y i s f i x e d , t h e n p i x e l g r e y l e v e l s a r e d e p e n d e n t on l i g h t i n g and on s u r f a c e g r a d i e n t . G e n e r a t i n g an image o f t h e same s u r f a c e i l l u m i n a t e d 55 from a d i f f e r e n t d i r e c t i o n does n o t r e q u i r e r e - c o m p u t a t i o n o f v i s i b l e s u r f a c e g r a d i e n t s , a s t h e v i e w p o i n t has n o t c h a n g e d . I f , i n s t e a d o f g r e y l e v e l s , t h e s e u n c h a n g i n g g r a d i e n t s a r e s t o r e d i n a frame b u f f e r , t h e n a l o o k u p t a b l e mapping s u r f a c e g r a d i e n t s i n t o g r e y l e v e l s w o u l d r e s t o r e t h e image. Frame b u f f e r d i s p l a y d e v i c e s t y p i c a l l y p r o v i d e a mapping f e a t u r e i n t h e f o r m o f a u s e r - a c c e s s i b l e memory p l a c e d between t h e frame b u f f e r and t h e e l e c t r o n beam d r i v e r ( s e e F i g u r e 3 . 6 ) . W i t h t h e s w i t c h a t p o s i t i o n A, t h e c o n t e n t s o f t h e frame b u f f e r a r e r a s t e r - s c a n n e d and u s e d t o m o d u l a t e t h e i n t e n s i t y o f t h e e l e c t r o n beam s t r i k i n g t h e s c r e e n . W i t h t h e s w i t c h a t p o s i t i o n B, t h e c o n t e n t s o f t h e frame b u f f e r a r e u s e d t o a d d r e s s new v a l u e s i n t h e memory map, and t h e s e new v a l u e s m o d u l a t e t h e beam i n t e n s i t y . I f s u r f a c e g r a d i e n t s a r e s t o r e d i n t h e frame b u f f e r , and a t a b l e mapping a l l p o s s i b l e g r a d i e n t s i n t o g r e y l e v e l s i s l o a d e d i n t o t h e memory map, t h e n t h e r e c o v e r e d image s h o u l d be i d e n t i c a l t o t h e one o b t a i n e d w i t h j u s t a frame b u f f e r of g r e y l e v e l s . A r e s t r i c t i o n p o s e d by t h i s t e c h n i q u e i s f i n i t e p i x e l s i z e . O n l y a s m a l l s e t o f g r a d i e n t d i r e c t i o n s c a n be e n c o d e d i n t h i s f i n i t e s p a c e . F u r t h e r m o r e , e a c h g r a d i e n t has two components, and t h e s e must be p a c k e d i n t o t h e s p a c e o r d i n a r i l y o c c u p i e d by one g r e y l e v e l . I f e a c h p i x e l o c c u p i e s N b i t s , t h e n a s s i g n i n g N / 2 b i t s p e r g r a d i e n t component i s a r e a s o n a b l e p a r t i t i o n f o r a s u r f a c e whose v a r i a t i o n i s n o t d i r e c t i o n a l l y b i a s e d . W i t h e a c h component e x h i b i t i n g o n l y 2 ' d i s c r e t e v a l u e s , q u a n t i z a t i o n 56 Switch Frame Buffer r — A 1 Memory Map i B To Intensity Modulator F i g u r e 3.6 Frame b u f f e r w i t h a t t a c h e d memory map 57 e r r o r i s i n t r o d u c e d i n t o t h e r e s t o r e d image. S i n c e e a c h g r a d i e n t component i s q u a n t i z e d t o 2 ' v a l u e s , N t h e f u l l g r a d i e n t [p q] i s q u a n t i z e d t o 2 d i r e c t i o n s . To r e c o v e r an image o f t h e s u r f a c e , g r a d i e n t s must be a s s i g n e d g r e y . . N l e v e l s v i a a memory map c o n t a i n i n g 2 e n t r i e s . The v a l u e o f e a c h e n t r y i s d e t e r m i n e d u s i n g a r e f l e c t a n c e f u n c t i o n R ( p , q ) . The s u r f a c e g r a d i e n t s and t h e v i e w e r d i r e c t i o n a r e f i x e d and known. The l i g h t i n g c o n f i g u r a t i o n c o n s i s t s o f a s i n g l e , d i s t a n t s o u r c e , whose d i r e c t i o n i s d e r i v e d f r o m a g r a p h i c a l i n p u t d e v i c e s u c h a s a t r a c k b a l l o r j o y s t i c k . The memory map i s f i l l e d by N a p p l y i n g t h e r e f l e c t a n c e f u n c t i o n t o e a c h o f t h e 2 s u r f a c e o r i e n t a t i o n s r e s u l t i n g f r o m t h e q u a n t i z a t i o n . As t h e g r a p h i c a l i n p u t d e v i c e i s m a n i p u l a t e d , t h e l i g h t s o u r c e i s moved and t h e r e f l e c t a n c e map i s u p d a t e d t o r e f l e c t t h e new l i g h t i n g d i r e c t i o n . S i n c e t h e map i s t y p i c a l l y so much s m a l l e r t h a n t h e frame b u f f e r ( w i t h o n l y 256 e n t r i e s f o r N=8), i t i s q u i c k l y u p d a t e d , a n d s u r f a c e s h a d e s a p p e a r t o v a r y i n r e a l t i m e w i t h t h e movement o f t h e l i g h t s o u r c e . M o v i n g shadows c a n n o t be s i m u l a t e d w i t h t h e memory map b e c a u s e t h e shadow c a l c u l a t i o n r e q u i r e s p o s i t i o n i n f o r m a t i o n a bout s u r f a c e e l e m e n t s , b u t o n l y s u r f a c e g r a d i e n t s a r e e n c o d e d i n t h e frame b u f f e r . T h i s d o e s not r e p r e s e n t a s e r i o u s drawback b e c a u s e , a s s t a t e d b e f o r e , i r r e g u l a r l y s h a p e d shadows c a s t upon a c o m p l i c a t e d s u r f a c e c a n c o n f o u n d t h e v i e w e r . A d i s c u s s i o n of memory map t e c h n i q u e s , i n c l u d i n g r e a l - t i m e s h a d i n g , may be f o u n d i n S l o a n and Brown ( 1 9 7 9 ) . 58 3.5.1 O p t i m a l Q u a n t i z a t i o n F i n i t e p i x e l s i z e r e q u i r e s t h a t t h e g r a d i e n t components be q u a n t i z e d b e f o r e t h e y a r e s t o r e d i n t h e frame b u f f e r . An e f f e c t i v e q u a n t i z a t i o n f u n c t i o n i s one t h a t aims t o r e d u c e t h e d i s c r e p a n c y between t h e o r i g i n a l s i g n a l ( i . e . t h e g r a d i e n t ) and t h e q u a n t i z e d s i g n a l . S u c h a f u n c t i o n s h o u l d t a k e i n t o a c c o u n t t h e p r o b a b i l i t y d e n s i t y f u n c t i o n o f s i g n a l l e v e l s so as t o m i n i m i z e c u m u l a t i v e d i s t o r t i o n , w h i c h r e s u l t s when t h e d i f f e r e n c e between a f r e q u e n t l y o c c u r r i n g s i g n a l v a l u e and i t s q u a n t i z e d l e v e l i s t o o l a r g e . A q u a n t i z e r maps L s i g n a l l e v e l i n t e r v a l s t o L d i s c r e t e o u t p u t l e v e l s . Any s i g n a l l e v e l x i n t h e i n t e r v a l (x^. ,x'.+^) i s o u t p u t a s y. , where i = 1,...,L. The x^.'s a r e o f t e n r e f e r r e d t o a s d e c i s i o n l e v e l s . A common measure f o r e v a l u a t i n g t h e e r r o r p r o d u c e d by a q u a n t i z a t i o n f u n c t i o n i s t h e mean-square d i s t o r t i o n D g i v e n by: where h ( x ) i s t h e p r o b a b i l i t y d e n s i t y f u n c t i o n o f t h e s i g n a l x. Max (1960) shows t h a t an o p t i m a l q u a n t i z e r , w h i c h m i n i m i z e s t h e d i s t o r t i o n D, must s a t i s f y two c o n d i t i o n s : = 2x. - y. , i i ~ 1 i — 2,...,L 59 (3.2) (3.3) The f i r s t c o n d i t i o n s t a t e s t h a t e a c h d e c i s i o n l e v e l i s midway between a d j a c e n t q u a n t i z a t i o n l e v e l s , and t h e s e c o n d s t a t e s t h a t y^ . i s t h e x component o f t h e c e n t r o i d o f t h e a r e a bounded by t h e c u r v e s x = x. , x = y = 0, and y = h ( x ) . Max a l s o d e s c r i b e s an i t e r a t i v e p r o c e d u r e f o r o b t a i n i n g t h e d e c i s i o n l e v e l s x^ . and t h e q u a n t i z a t i o n l e v e l s y^ . , g i v e n t h a t t h e s i g n a l e x t r e m e s x, and XL+J a r e known. Once a g u e s s i s made a t a v a l u e f o r y 1 f a l l s u c c e s s i v e x^.'s and y^ . ' s c a n be g e n e r a t e d f r o m E q u a t i o n s 3.2 and 3.3. I f t h e r e s u l t i n g y ^ i s t h e c e n t r o i d o f t h e a r e a s t r i p u n d e r h ( x ) between x^ and XL+J> t h e n y, was g u e s s e d c o r r e c t l y . I f y ^ i s n o t t h e c e n t r o i d , t h e n a new g u e s s f o r y, i s made. The g u e s s f o r y, i s i t e r a t i v e l y a d j u s t e d u n t i l y ^ i s t h e c e n t r o i d o f t h e l a s t s t r i p . F o r e n c o d i n g s u r f a c e g r a d i e n t s i n a frame b u f f e r , t h e s p e c t r a o f v a l u e s e x h i b i t e d by p and q o v e r a v i s i b l e s u r f a c e a r e t h e s i g n a l s t o be q u a n t i z e d . I f p and q a r e e a c h q u a n t i z e d o p t i m a l l y , t h e n t h e e r r o r i n t h e r e s u l t i n g "image" o f g r a d i e n t s i s m i n i m a l . However, t h e r e c o v e r e d s i g n a l i s an image o f i n t e n s i t i e s o b t a i n e d by t r a n s f o r m i n g t h e g r a d i e n t s w i t h a r e f l e c t a n c e map. B e c a u s e i t i s n o n l i n e a r , t h i s t r a n s f o r m a t i o n may skew t h e e r r o r so c a r e f u l l y m i n i m i z e d d u r i n g q u a n t i z a t i o n . T h e r e f o r e , a q u a n t i z a t i o n t h a t y i e l d s an o p t i m a l g r a d i e n t 60 e n c o d i n g may y i e l d a s u b - o p t i m a l image r e c o n s t r u c t i o n . The r e f l e c t a n c e maps R(p,q) c o n s i d e r e d i n t h i s t h e s i s a r e f u n c t i o n s o f s u r f a c e g r a d i e n t [p q ] , v i e w e r d i r e c t i o n [~P V ~Qi v 1 ] , and l i g h t i n g d i r e c t i o n [-p^ -q^ 1 ] , The e r r o r i n image i n t e n s i t y r e s u l t i n g from g r a d i e n t q u a n t i z a t i o n e r r o r i s p r o p o r t i o n a l t o dR, where dR = R dp + R dq P 1 I t seems r e a s o n a b l e t o q u a n t i z e p and q f i n e l y a b o u t t h o s e v a l u e s where R i s most s e n s i t i v e t o e r r o r s i n p and q, a b o u t t h o s e v a l u e s t h a t m a x i m i z e t h e e r r o r dR. However, t h e s e " c r i t i c a l " v a l u e s of [p q ] a r e , i n g e n e r a l , f u n c t i o n s o f t h e l i g h t s o u r c e d i r e c t i o n [~P^ ~<is 1]« The c r i t i c a l v a l u e s o f [ p q] a r e t h o s e p o i n t s a t w h i c h t h e i s o - b r i g h t n e s s c o n t o u r s o f R(p,q) a r e most d e n s e . A c o n t o u r p l o t o f t h e d i f f u s e r e f l e c t a n c e f u n c t i o n g i v e n by E q u a t i o n 3.1 i s shown i n F i g u r e 3.7. I n t h e f i g u r e , t h e c r i t i c a l p o i n t , o r p o i n t s , o c c u r i n t h e t h i r d q u a d r a n t . As t h e l i g h t i n g d i r e c t i o n c h a n g e s , t h e major a x i s o f t h e e l l i p s e s r o t a t e s a b o u t t h e o r i g i n , and t h e d i s t a n c e o f t h e l i n e R(p,q) = 0 f r o m t h e o r i g i n a l s o c h a n g e s . T h e r e f o r e , a s t h e l i g h t s o u r c e moves, t h e r e g i o n of h i g h r e f l e c t a n c e s e n s i t i v i t y r o t a t e s , a n d t h e d e g r e e o f s e n s i t i v i t y v a r i e s . To s o l v e t h e q u a n t i z a t i o n p r o b l e m f o r e a c h new l i g h t i n g d i r e c t i o n d e f e a t s t h e o r i g i n a l i n t e n t o f p r o v i d i n g s h a d i n g c h a n g e s i n r e a l t i m e u s i n g o n l y a r e f l e c t a n c e t a b l e . I t may be t h e c a s e t h a t t h e c r i t i c a l v a l u e s o f [p q] do not 61 F i g u r e 3.7 R e f l e c t a n c e map f o r d i f f u s e s u r f a c e i l l u m i n a t e d f r o m 9=61°,0=53° [ f r o m Woodham ( 1 9 7 8 ) ] 62 change a p p r e c i a b l y w i t h l i g h t s o u r c e movement, o r w i t h movement c o n f i n e d t o w i t h i n a c e r t a i n a n g l e a b o u t t h e v i e w e r d i r e c t i o n . In t h i s t h e s i s , however, t h e d e p e n d e n c e o f r e f l e c t a n c e s e n s i t i v i t y on l i g h t s o u r c e d i r e c t i o n i s n o t i n v e s t i g a t e d . The f o c u s i s on m i n i m i z i n g g r a d i e n t d i s t o r t i o n , n o t image d i s t o r t i o n , f o r a g i v e n v i e w p o i n t . G i v e n a s u f f i c i e n t number o f g r a d i e n t q u a n t i z a t i o n l e v e l s , a r e l a t i v e l y d i s t o r t i o n - f r e e image s h o u l d be r e c o v e r e d . 3.6 Summary R e c o n s t r u c t e d v i s u a l f i e l d s u r f a c e s a r e p r o j e c t e d o r t h o g r a p h i c a l l y o n t o an image p l a n e . An o r t h o g r a p h i c p r o j e c t i o n i s u s e d b e c a u s e l i t t l e i s g a i n e d f r o m t h e more e x p e n s i v e p e r s p e c t i v e p r o j e c t i o n when r e n d e r i n g u n f a m i l i a r , i r r e g u l a r s u r f a c e s . The s p e c u l a r s u r f a c e r e f l e c t a n c e model o f B u i Tuong Phong (1975) i s u s e d t o h i g h l i g h t r a p i d l y v a r y i n g s u r f a c e f e a t u r e s w h i c h may be o f i n t e r e s t t o t h e o p h t h a l m o l o g i s t . P o r t i o n s o f t h e p r o j e c t e d s u r f a c e t h a t s h o u l d not be v i s i b l e a r e e l i m i n a t e d f r o m t h e image by a r e c e d i n g -h o r i z o n h i d d e n s u r f a c e a l g o r i t h m . The h i d d e n s u r f a c e a l g o r i t h m t a k e s p l a n e s p a r a l l e l t o t h e image p l a n e and i n t e r s e c t s them w i t h t h e s u r f a c e t o c r e a t e p r o f i l e c u r v e s . The a l g o r i t h m " f o c u s e s " on one p l a n e a t a t i m e . The p r o f i l e i n t h e " f o c a l " p l a n e c l o s e s t t o t h e v i e w e r becomes t h e v i s i b l e h o r i z o n a t t h a t f o c a l d e p t h . The f o c u s i s s h i f t e d i n a s y s t e m a t i c manner s u c h t h a t t h e f o c a l p l a n e moves f r o m t h e f r o n t t o t h e back o f t h e s u r f a c e . As t h e f o c a l p l a n e r e c e d e s 6 3 f r o m t h e v i e w e r , t h e v i s i b l e h o r i z o n expands w i t h new s u r f a c e p r o f i l e s , and t h i s e x p a n s i o n i s r e c o r d e d i n t h e image p l a n e . S u r f a c e p r o f i l e segments f a l l i n g below t h e c u r r e n t l y v i s i b l e h o r i z o n do n o t c o n t r i b u t e t o t h e e x p a n d i n g h o r i z o n , and a r e t h u s n o t d i s p l a y e d . As t h e f o c a l p l a n e r e c e d e s a n d t h e h o r i z o n e x p a n d s , an image o f t h e v i s i b l e s u r f a c e u n f o l d s . I n o r d e r t o more e f f e c t i v e l y c o n v e y s u r f a c e shape and t o r e d u c e image a m b i g u i t y , t h e o r i g i n a l , c o l o u r - c o d e d c o n t o u r s a r e s u p e r p o s e d on a shaded, v i s u a l f i e l d s u r f a c e . A n o t h e r way t o i n f e r s u r f a c e shape i s t o move a l i g h t s o u r c e a b o u t t h e s u r f a c e and o b s e r v e how t h e a p p a r e n t b r i g h t n e s s of d i f f e r e n t s u r f a c e r e g i o n s c h a n g e s . By q u a n t i z i n g t h e g r a d i e n t s o f v i s i b l e s u r f a c e e l e m e n t s and p a c k i n g them i n t o a frame b u f f e r , an "image" o f c o d e d s u r f a c e g r a d i e n t s i s o b t a i n e d . An image o f i n t e n s i t y v a l u e s i s r e c o v e r e d by t r a n s f o r m i n g t h e frame b u f f e r c o n t e n t s w i t h a memory mapping. Image i n t e n s i t i e s c a n be made t o v a r y i n r e a l t i m e by u p d a t i n g t h e c o n t e n t s o f t h e r e l a t i v e l y s m a l l memory map a c c o r d i n g t o c h a n g e s i n l i g h t s o u r c e p o s i t i o n . 64 IV. RESULTS 4.1 V i s u a l F i e l d S u r f a c e s R e a l d a t a were o b t a i n e d f r o m s i x v i s u a l f i e l d c h a r t s . The c h a r t s r e c o r d t h e v i s u a l f i e l d o f a g l a u c o m a p a t i e n t s ' s l e f t eye as i t v a r i e s o v e r a p e r i o d o f a b o u t f o u r y e a r s . The d a t a i n e a c h c h a r t were d i g i t i z e d and t r i a n g u l a t e d . A smooth s u r f a c e was i n t e r p o l a t e d o v e r e a c h t r i a n g u l a t e d domain, an d t h e n d i s p l a y e d a s a c o n t i n u o u s - t o n e , g r e y - l e v e l image. The s i x v i s u a l f i e l d c h a r t s , a s s e m b l e d i n c h r o n o l o g i c a l o r d e r , a r e shown i n F i g u r e s 4.1a t o 4.6a. The c o r r e s p o n d i n g s haded s u r f a c e r e n d i t i o n s a r e g i v e n i n F i g u r e s 4.1b t o 4.6b. E a c h s u r f a c e i s v i e w e d f r o m 0 = 1 6 0 ° , 0 = 5 0 ° and i l l u m i n a t e d f r o m 6=120°,0=70°. F i g u r e s 4.1c t o 4.6c show t h e s u r f a c e s i n v e r t e d , but v i e w e d and i l l u m i n a t e d f r o m t h e same d i r e c t i o n s a s t h e non-i n v e r t e d s u r f a c e s . The s h a d e d images a r e d i f f i c u l t t o i n t e r p r e t . I t i s i m p o r t a n t t h a t t h e v i e w e r u n d e r s t a n d what a n o r m a l v i s u a l f i e l d s u r f a c e s h o u l d l o o k l i k e and how v i s u a l d e f e c t s a r e m a n i f e s t a g a i n s t a n o r m a l f i e l d . A n o r m a l v i s u a l f i e l d s h o u l d a p p e a r a s a p l a t e a u g r a d u a l l y r i s i n g t o a low peak a t t h e c e n t e r o f f i x a t i o n . The p h y s i o l o g i c a l b l i n d s p o t , where t h e o p t i c n e r v e i s a t t a c h e d t o t h e r e t i n a , s h o u l d a p p e a r a s a b o t t o m l e s s p i t l o c a t e d on t h e x a x i s and o f f s e t t o e i t h e r s i d e o f t h e f i x a t i o n p o i n t . P a t h o l o g i c a l b l i n d s p o t s a r e a l s o r e n d e r e d a s p i t s . P i t s a r e " t r u n c a t e d " b e c a u s e t h e p e r i m e t e r ' s f i n i t e s e t o f t a r g e t s i mposes an upper l i m i t on p r o b e i n t e n s i t y . B e c a u s e o f F i g u r e 4.1a V i s u a l f i e l d c h a r t 1 (March 1978) F i g u r e 4.1b Shaded s u r f a c e f r o m d a t a i n c h a r t 1 F i g u r e 4.1c I n v e r t e d s u r f a c e f r o m d a t a i n c h a r t 1 g u r e 4.2a V i s u a l f i e l d c h a r t 2 (September 1978) F i g u r e 4.2c I n v e r t e d s u r f a c e f r o m d a t a i n c h a r t 2 F i g u r e 4 . 3 a V i s u a l f i e l d c h a r t 3 ( A p r i l 1979) F i g u r e 4.3c I n v e r t e d s u r f a c e f r o m d a t a i n c h a r t 3 F i g u r e 4.4a V i s u a l f i e l d c h a r t 4 ( O c t o b e r 1979) 72 F i g u r e 4.4c I n v e r t e d s u r f a c e f r o m d a t a i n c h a r t 4 F i g u r e 4.5a V i s u a l f i e l d c h a r t 5 ( J u n e 1981) F i g u r e 4.5c I n v e r t e d s u r f a c e f r o m d a t a i n c h a r t 5 75 F i g u r e 4.6a V i s u a l f i e l d c h a r t 6 (December 1981) F i g u r e 4.6b S haded s u r f a c e f r o m d a t a i n c h a r t 6 F i g u r e 4.6c I n v e r t e d s u r f a c e f r o m d a t a i n c h a r t 6 77 i t s known p r e s e n c e , t h e n o r m a l b l i n d s p o t i s r a r e l y f u l l y p r o b e d i n p r a c t i c e , and o f t e n a p p e a r s as a p i t t h a t i s s h a l l o w e r t h a n t h e p i t s o f p a t h o l o g i c a l b l i n d s p o t s . On i n v e r t e d s u r f a c e s , b l i n d s p o t s a p p e a r a s mesas, o r c l o s e d - r i m m e d p l a t e a u s , s t a n d i n g above t h e p l a i n o f n o r m a l v i s i o n . In F i g u r e s 4.1b t o 4.6b t h e p h y s i o l o g i c a l b l i n d s p o t i s merged w i t h a p a t h o l o g i c a l b l i n d s p o t t o form t h e l a r g e c e n t r a l p i t v i s i b l e on e a c h s u r f a c e . The p a t i e n t ' s c o n d i t i o n a p p e a r s t o improve f r o m F i g u r e 4.1 t o F i g u r e 4.2, and t h e n w o r s e n . . T h i s a p p a r e n t improvement i s c o n v e y e d by a. s h a l l o w e r c e n t r a l d e f e c t and by a p e r i p h e r a l d e f e c t d i m i n i s h e d i n e x t e n t . S u ch c h a n g e s may be c a u s e d by s h o r t - t e r m o r l o n g - t e r m f l u c t u a t i o n s w h i c h o c c u r b e c a u s e o f t h e s u b j e c t i v i t y i n h e r e n t i n p e r i m e t r i c e x a m i n a t i o n [ D r a n c e ( 1 9 8 4 ) ] . F l u c t u a t i o n s o c c u r i n n o r m a l f i e l d s a s w e l l a s i n d i s e a s e d f i e l d s . The f l u c t u a t i o n s a r e more e x t e n s i v e i n t h e f i e l d p e r i p h e r y t h a n n e a r t h e f i e l d c e n t e r , and t h e y a r e more p r o n o u n c e d i n d i s e a s e d f i e l d s t h a n i n n o r m a l f i e l d s . The p r o g r e s s o f a p a t i e n t ' s g l a u c o m a t o u s c o n d i t i o n , t h e r e f o r e , c a n n o t be e v a l u a t e d by c o m p a r i n g t h e v i s u a l f i e l d c h a r t s from two c o n s e c u t i v e e x a m i n a t i o n s . What i s r e q u i r e d f o r a v a l i d d i a g n o s i s i s a s e q u e n c e o f e x a m i n a t i o n s s p a n n i n g a t i m e p e r i o d l o n g enough t o d e f e a t t h e e f f e c t s o f l o n g - t e r m f l u c t u a t i o n s and t o r e v e a l any t r e n d i n t h e t i m e - v a r y i n g v i s u a l f i e l d . 78 4.2 G r a d i e n t Q u a n t i z a t i o n E x p e r i m e n t An e x p e r i m e n t was p e r f o r m e d t o a s c e r t a i n how many b i t s o f s u r f a c e g r a d i e n t i n f o r m a t i o n a r e s u f f i c i e n t t o p r o d u c e a r e l a t i v e l y d i s t o r t i o n - f r e e image o f t h e s u r f a c e . The s u r f a c e u s e d i n t h e e x p e r i m e n t was t h e f u n c t i o n z = ( s i n r ) / r , where r 2 = x 2 + y 2 . The t e s t s u r f a c e i s v i e w e d from 6=160°,0=50° and i l l u m i n a t e d f r o m 0 = 1 8 0 ° , 0 = 7 0 ° . The images o f t h e s u r f a c e i n F i g u r e s 4.7, 4.8, and 4.9 were g e n e r a t e d w i t h g r a d i e n t r e p r e s e n t a t i o n s o f 8, 10, and 12 b i t s , r e s p e c t i v e l y . The image i n F i g u r e 4.9 e x h i b i t s l i t t l e d i s t o r t i o n when compared w i t h t h e c o n t r o l image i n F i g u r e 4.10, where p and q were e a c h a l l o t t e d 32 b i t s . A l l f o u r images were s y n t h e s i z e d w i t h a d i f f u s e s u r f a c e r e f l e c t a n c e f u n c t i o n . To i l l u s t r a t e t h e s e n s i t i v i t y o f r e f l e c t a n c e t o e r r o r s i n g r a d i e n t , t h e g r a d i e n t e n c o d i n g t h a t p r o d u c e d t h e r e s t o r e d image i n F i g u r e 4.9 was t r a n s f o r m e d by a s p e c u l a r s u r f a c e r e f l e c t a n c e f u n c t i o n . The r e s u l t i n g image o f t h e s u r f a c e i l l u m i n a t e d f r o m 0=180°,0=50° i s shown i n F i g u r e 4.11 ( F i g u r e 4.12 c o n t a i n s t h e c o n t r o l image f o r t h i s c a s e ) . I t i s n o t s u r p r i s i n g t h a t q u a n t i z a t i o n e r r o r i s most a p p a r e n t i n h i g h l i g h t e d r e g i o n s where r e f l e c t a n c e v a r i e s q u i c k l y w i t h s m a l l c h a n g e s i n s u r f a c e g r a d i e n t . The q u a n t i z a t i o n a l g o r i t h m u s e d i n t h i s e x p e r i m e n t m i n i m i z e s mean-square g r a d i e n t d i s t o r t i o n by t h e method o f Max ( 1 9 6 0 ) . The p r o b a b i l i t y d e n s i t y f u n c t i o n s h ( p ) and h ( q ) were l i n e a r l y i n t e r p o l a t e d f r o m t h e c o r r e s p o n d i n g h i s t o g r a m s f o r p and q . The f u n c t i o n h ( p ) d e r i v e d i n t h i s manner i s i l l u s t r a t e d F i g u r e 4.7 D i f f u s e s u r f a c e r e p r e s e n t e d w i t h 8 - b i t g r a d i e n t s F i g u r e 4.8 D i f f u s e s u r f a c e r e p r e s e n t e d w i t h 1 0 - b i t g r a d i e n t s F i g u r e 4.9 D i f f u s e s u r f a c e r e p r e s e n t e d w i t h 1 2 - b i t g r a d i e n t s F i g u r e 4.10 D i f f u s e s u r f a c e r e p r e s e n t e d w i t h 6 4 - b i t g r a d i e n t s 81 F i g u r e 4.11 S p e c u l a r s u r f a c e r e p r e s e n t e d w i t h 1 2 - b i t g r a d i e n t s F i g u r e 4.12 S p e c u l a r s u r f a c e r e p r e s e n t e d w i t h 6 4 - b i t g r a d i e n t s 82 F i g u r e 4.13 G r a p h o f h ( p ) l i n e a r l y i n t e r p o l a t e d f r o m h i s t o g r a m d a t a f o r p 83 i n F i g u r e 4.13. T h i s f u n c t i o n was t h e n smoothed by m u l t i p l e a p p l i c a t i o n s o f a t h r e e - p o i n t a v e r a g i n g o p e r a t o r t o p r o d u c e t h e d e n s i t y f u n c t i o n u s e d by t h e q u a n t i z a t i o n a l g o r i t h m . T h i s f u n c t i o n i s r e p r o d u c e d i n F i g u r e 4.14. The p r o b a b i l i t y d e n s i t y f u n c t i o n h ( q ) i s r e p r o d u c e d i n F i g u r e 4.15. o oo o o o in © o" © O o h ( p ) -10 — r -4 F i g u r e 4.14 Smoothed p r o b a b i l i t y d e n s i t y f u n c t i o n h ( p ) 85 F i g u r e 4.15 Smoothed p r o b a b i l i t y d e n s i t y f u n c t i o n h ( q ) 86 V. CONCLUSIONS AND PROPOSALS 5.1 C o n c l u s i o n s Human v i s u a l f i e l d d a t a g a t h e r e d by k i n e t i c p e r i m e t r y a r e commonly r e c o r d e d a s a c o n t o u r map. D i s p l a y i n g t h e d a t a a s a s h a d e d s u r f a c e b e t t e r c o n v e y s t h e b e h a v i o u r o f t h e d a t a t o a human v i e w e r , who s e e s t h e b e h a v i o u r m a n i f e s t by v a r i a t i o n s i n s u r f a c e s h a p e . The d i s p l a y s y s t e m d e s c r i b e d i n t h i s t h e s i s g e n e r a t e s s h a d e d images of v i s u a l f i e l d s u r f a c e s v i e w e d from, and i l l u m i n a t e d f r o m , a r b i t r a r y d i r e c t i o n s . The s y s t e m e n a b l e s s u p e r p o s i t i o n o f o r i g i n a l c o n t o u r d a t a o n t o t h e c o r r e s p o n d i n g s h a d e d s u r f a c e , and a l s o p r o v i d e s a zoom f e a t u r e . A l t h o u g h s u p e r i o r t o c o n t o u r d e p i c t i o n s , s h a d e d images o f a b s t r a c t s u r f a c e s r e m a i n d i f f i c u l t t o i n t e r p r e t . S u p e r p o s i n g t h e o r i g i n a l c o n t o u r s o n t o a s h a d e d , v i s u a l f i e l d s u r f a c e r e d u c e s image a m b i g u i t y . N e v e r t h e l e s s , a p r i o r i knowledge o f how d e f e c t s i n a n o r m a l v i s u a l f i e l d a p p e a r i s s t i l l n e c e s s a r y f o r c o r r e c t i n t e r p r e t a t i o n . A c e n t r a l d e f e c t a p p e a r s as a l a r g e " p i t " i n t h e s u r f a c e , a p i t w h i c h , i n a l l b ut o v e r h e a d v i e w s , i s l a r g e l y o b s c u r e d by t h e " p l a t e a u " o f n o r m a l v i s i o n . I n v e r t i n g t h e s u r f a c e t r a n s f o r m s t h e p i t i n t o a "mesa", o r c l o s e d - r i m m e d p l a t e a u , r i s i n g a bove t h e " p l a i n " o f n o r m a l v i s i o n . The b o t t o m o f t h e p i t becomes v i s i b l e a s t h e t o p o f t h e mesa. A p e r i p h e r a l d e f e c t , a p p e a r i n g as a p i t whose r i m i s n o t c l o s e d , i s e f f e c t i v e l y c o n v e y e d by a 87 n o n - i n v e r t e d s u r f a c e . A view d i r e c t e d i n t o t h e p i t f r o m t h e open end o f t h e r i m r e v e a l s t h e w a l l s and f l o o r o f t h e p i t . The j u d i c i o u s c h o i c e o f a zoom window o v e r a c e n t r a l d e f e c t c a n c r e a t e a p i t w i t h an open r i m . A n o n - i n v e r t e d s u r f a c e a g a i n r e v e a l s d e t a i l s o f t h e p i t i n t e r i o r . The zoom window i n F i g u r e 1.13 p a r t i t i o n s t h e c e n t r a l p i t s u c h t h a t t h e r i m o f t h e p i t i s o p e n e d . The r e g i o n w i t h i n t h i s window i s d i s p l a y e d a s a s h a d e d s u r f a c e i n F i g u r e 1.14 and a s a l i n e d r a w i n g i n F i g u r e 1.4. The s h a d e d s u r f a c e c l e a r l y shows more d e t a i l t h a n t h e l i n e d r a w i n g . D e t a i l i s c o n v e y e d by s h a d i n g h i g h l i g h t s o b t a i n e d w i t h a s p e c u l a r s u r f a c e r e f l e c t a n c e m o d e l . The r e f l e c t a n c e i s s e n s i t i v e t o c h a n g e s i n s u r f a c e c u r v a t u r e and h i g h l i g h t s f e a t u r e s t h a t a r e o f i n t e r e s t t o t h e o p h t h a l m o l o g i s t . W i r t s c h a f t e r e t a l . (1982) t a k e an i n t e r e s t i n g a p p r o a c h t o t h e p r e s e n t a t i o n o f v i s u a l f i e l d d a t a . They p a r t i t i o n t h e v i s u a l f i e l d i n t o r e g i o n s t h a t p r o j e c t o n t o n e r v e f i b e r l a y e r s i n t h e r e t i n a . F i e l d d a t a w i t h i n a r e g i o n a r e r e d u c e d t o a s i n g l e m e asure. S e l e c t i o n o f an a v e r a g i n g t e c h n i q u e t h e n becomes c r i t i c a l , a s d a t a r e p r e s e n t i n g s u b t l e v i s u a l d e f e c t s may be l o s t i n t h e a v e r a g i n g p r o c e s s , l e a v i n g t h e o p h t h a l m o l o g i s t w i t h a 2D a r r a y o f "magic" numbers t o e v a l u a t e . The s t r e n g t h o f t h e a p p r o a c h l i e s , n o t i n d a t a r e d u c t i o n , b u t i n t h e p h y s i o l o g i c a l l y b a s e d c r i t e r i o n u s e d t o p a r t i t i o n t h e v i s u a l f i e l d . I t seems l o g i c a l t o model t h e v i s u a l f i e l d s u r f a c e by p a t c h e s whose b o u n d a r i e s a r e a l i g n e d w i t h t h e b o u n d a r i e s o f t h i s p a r t i t i o n . A l t h o u g h t h e p a r t i t i o n b o u n d a r i e s f o l l o w t h e shape 88 o f r e t i n a l n e r v e f i b e r b u n d l e s , t h e s e l e c t i o n o f w h i c h b u n d l e s t o use a s b o u n d a r i e s i s a r b i t r a r y . T h i s a r b i t r a r i n e s s seems t o c a s t t h e t e c h n i q u e ' s p r o m i s e i n t o d o u b t . A s y s t e m f o r s y n t h e s i z i n g images o f s h a d e d s u r f a c e s , w i t h i t s p r o v i s i o n f o r v i e w e r m o b i l i t y , l i g h t s o u r c e m o b i l i t y , s u r f a c e i n v e r s i o n , c o n t o u r s u p e r p o s i t i o n , a n d zoom, c r e a t e s r e n d i t i o n s o f human v i s u a l f i e l d d a t a s u p e r i o r t o t r a d i t i o n a l c o n t o u r maps, t o t h e l i n e d r a w i n g s of H a r t and H a r t z , and t o t h e c h a r t s o f W i r t s c h a f t e r e t a l . A n o t h e r a t t r a c t i v e t e c h n i q u e f o r c o n v e y i n g s u r f a c e shape i s t o v a r y s u r f a c e shade i n r e a l t i m e w i t h t h e movement of a l i g h t s o u r c e . A g r a d i e n t "image" o f a s u r f a c e i s f o r m e d by e n c o d i n g frame b u f f e r p i x e l s a s g r a d i e n t v e c t o r s i n s t e a d o f s u r f a c e r a d i a n c e v a l u e s . An i n t e n s i t y image o f t h e s u r f a c e i s r e c o v e r e d by t r a n s f o r m i n g s u r f a c e g r a d i e n t s i n t o image i n t e n s i t i e s w i t h a memory map. Images r e c o v e r e d f r o m a frame b u f f e r o f 8 - b i t g r a d i e n t s , where g r a d i e n t components were q u a n t i z e d o p t i m a l l y , were f o u n d t o be h i g h l y d i s t o r t e d . An e x p e r i m e n t t o s i m u l a t e l o n g e r , g r a d i e n t word l e n g t h s was c o n d u c t e d . I t was f o u n d t h a t 12 b i t s p e r g r a d i e n t were a d e q u a t e f o r r e c o n s t r u c t i n g images o f a m a t t e s u r f a c e . S l i g h t d i s t o r t i o n , however, was s t i l l d i s c e r n a b l e upon c l o s e i n s p e c t i o n o f t h e images. G r e a t e r d i s t o r t i o n r e s u l t e d when a s p e c u l a r s u r f a c e model was u s e d b e c a u s e t h e c o r r e s p o n d i n g r e f l e c t a n c e f u n c t i o n i s more s e n s i t i v e t o g r a d i e n t q u a n t i z a t i o n e r r o r . The s i m u l a t i o n was p e r f o r m e d by q u a n t i z i n g s u r f a c e g r a d i e n t s so a s t o m i n i m i z e t h e mean-square d i s t o r t i o n i n t h e 89 r e s u l t i n g g r a d i e n t "image" o f t h e s u r f a c e . A b e t t e r a p p r o a c h t o t h e q u a n t i z a t i o n p r o b l e m i s t o m i n i m i z e d i s t o r t i o n i n t h e i n t e n s i t y image by q u a n t i z i n g f i n e l y a b o u t t h o s e c r i t i c a l g r a d i e n t s t h a t m a x i m i z e t h e r e f l e c t a n c e e r r o r . The p r o b l e m w i t h t h i s a p p r o a c h i s t h a t t h e c r i t i c a l g r a d i e n t s v a r y w i t h t h e p o s i t i o n o f t h e l i g h t s o u r c e . Q u a n t i z i n g a f t e r e a c h l i g h t s o u r c e movement t o c r e a t e a new s u r f a c e g r a d i e n t r e p r e s e n t a t i o n i n t h e frame b u f f e r d e f e a t s t h e p u r p o s e of r e a l - t i m e s h a d i n g w i t h a memory map. I t i s p o s s i b l e t o r e s t r i c t t h e l i g h t i n g d i r e c t i o n t o w i t h i n some a n g u l a r d e v i a t i o n o f t h e v i e w i n g d i r e c t i o n . T h i s w o u ld, i n t u r n , d i m i n i s h t h e l o c u s o f c r i t i c a l g r a d i e n t s and e l i m i n a t e t h e n e e d t o r e - q u a n t i z e a f t e r e a c h l i g h t s o u r c e movement. The g r a d i e n t q u a n t i z a t i o n w o u l d be s u b - o p t i m a l b e c a u s e i t would have t o y i e l d a c c e p t a b l e images f o r a l l p e r m i t t e d l i g h t i n g d i r e c t i o n s . The t i g h t e r t h e c o n s t r a i n t i s made on l i g h t s o u r c e movement, t h e l e s s d i s t o r t i o n t h e r e i s i n t h e r e c o v e r e d i m a g es. I t i s t h e o p i n i o n o f t h e a u t h o r t h a t even by r e s t r i c t i n g l i g h t s o u r c e movement, i t would n o t be p o s s i b l e t o r e c o n s t r u c t r e l a t i v e l y d i s t o r t i o n - f r e e images from a frame b u f f e r o f 8 - b i t g r a d i e n t s . To p e r f o r m e f f e c t i v e r e a l - t i m e s h a d i n g , a frame b u f f e r of 12, o r more, b i t s p e r p i x e l i s r e q u i r e d . 5.2 P r o p o s a l s f o r F u r t h e r Work O t h e r t e c h n i q u e s f o r c o n v e y i n g s u r f a c e shape a r e o u t l i n e d i n t h e I n t r o d u c t i o n , but n o t i m p l e m e n t e d i n t h e c u r r e n t d i s p l a y s y s t e m . T h e s e a r e : s t e r e o p a i r g e n e r a t i o n , c o l o u r - c o d e d s u r f a c e 90 c u r v a t u r e , and r e a l - t i m e movement o f t h e v i e w p o i n t . The c u r r e n t d i s p l a y p r o g r a m c o u l d e a s i l y be m o d i f i e d t o p e r f o r m p e r s p e c t i v e p r o j e c t i o n . I t i s t h e n a s i m p l e t a s k t o g e n e r a t e two images o f t h e same s u r f a c e : one f r o m t h e v i e w p o i n t o f t h e l e f t e y e , t h e o t h e r f r o m t h e v i e w p o i n t o f t h e r i g h t . C o l o u r images c o d e d t o c o n v e y s u r f a c e c u r v a t u r e c o u l d a l s o be p r o d u c e d by a s i m p l e e x t e n s i o n t o t h e d i s p l a y p r o g r a m . The p r o c e d u r e t h a t computes s u r f a c e g r a d i e n t a t a p o i n t would, i n s t e a d , d e t e r m i n e s u r f a c e c u r v a t u r e a t t h e p o i n t . The p r o c e d u r e t h a t computes t h e r a d i a n c e a t a s u r f a c e p o i n t would be c h a n g e d t o map s u r f a c e c u r v a t u r e i n t o c o l o u r . R e a l - t i m e movement o f t h e v i e w p o i n t a b o u t a s u r f a c e r e q u i r e s s p e c i a l h a r d w a r e , b ut t h e e f f e c t c o u l d be d e m o n s t r a t e d w i t h t i m e - l a p s e p h o t o g r a p h y , where a l a p s e w o u l d be t h e t i m e i t t a k e s t h e d i s p l a y p r o c e s s t o g e n e r a t e t h e n e x t frame i n an a n i m a t i o n s e q u e n c e . A u s e f u l t o o l f o r o b s e r v i n g v i s u a l f i e l d c h a n g e s r e c o r d e d a s a t i m e s e q u e n c e o f c h a r t s c o u l d a l s o employ t i m e - l a p s e p h o t o g r a p h y . Frames between two c o n s e c u t i v e c h a r t s c o u l d be i n t e r p o l a t e d f r o m t h e s u r f a c e s c o r r e s p o n d i n g t o t h o s e c h a r t s . An a n i m a t i o n s e q u e n c e c r e a t e d f r o m t h e i n - b e t w e e n f r a m e s would show how s u r f a c e shape v a r i e s s m o o t h l y w i t h t i m e from c h a r t t o c h a r t . I n a d d i t i o n t o t h e above f e a t u r e s , improvements t o t h e e x i s t i n g s y s t e m c o u l d be made. A p a r t o f t h e t r i a n g u l a t i o n p r o c e d u r e r e q u i r e s t h a t t h e u s e r e x t r a c t s u r f a c e b r e a k l i n e s from p o i n t s a t w h i c h v i s u a l 91 f i e l d c o n t o u r s e x h i b i t h i g h c u r v a t u r e , and e n t e r t h e s e i n t o f i l e s by k e y b o a r d . In o r d e r t o f r e e t h e u s e r f r o m t h i s b u r d e n , an a u t o m a t i c p r o c e d u r e t o i d e n t i f y s u r f a c e b r e a k l i n e s f r o m a c o n t o u r map s h o u l d be d e v e l o p e d . Image s y n t h e s i s i s c u r r e n t l y e x e c u t e d i n d e p e n d e n t l y o f s u r f a c e s a m p l i n g and i n t e r p o l a t i o n . An a d v a n t a g e o f t h i s m o d u l a r i t y i s t h e a b i l i t y t o d i s p l a y s u r f a c e s t h a t a r e n o t m o d e l l e d o v e r a t r i a n g u l a t e d i r r e g u l a r n e t w o r k . The t e s t s u r f a c e u s e d i n t h e g r a d i e n t q u a n t i z a t i o n e x p e r i m e n t i s s u c h a s u r f a c e . F o r d i s p l a y i n g s u r f a c e s r e p r e s e n t a b l e by e l e v a t i o n g r i d s , improvements c o u l d be made t o t h e c u r r e n t h i d d e n s u r f a c e module. F o r example, a g r a d i e n t e s t i m a t o r o t h e r t h a n t h e one u s e d m i g h t r e d u c e t h e e f f e c t o f e r r o r s i n s u r f a c e e l e v a t i o n , t h e r e b y i n c r e a s i n g image q u a l i t y . A d i s a d v a n t a g e of t h e c u r r e n t m o d u l a r d e s i g n i s t h a t t h e s u r f a c e i s s c a n n e d t w i c e : o nce d u r i n g i n t e r p o l a t i o n , and t h e n a g a i n d u r i n g image s y n t h e s i s . P e r f o r m i n g i n t e r p o l a t i o n c o n c u r r e n t l y w i t h p r o f i l e s c a n n i n g i n t h e h i d d e n s u r f a c e p r o c e d u r e w o u l d e l i m i n a t e one o f t h e s e s c a n s . In a d d i t i o n , s u r f a c e r e - s a m p l i n g f o r f i l l i n g p i x e l gaps i n image c o l u m n s c o u l d be p e r f o r m e d e x a c t l y u s i n g t h e TIN s u r f a c e r e p r e s e n t a t i o n . Column gaps c o u l d be a v o i d e d a l t o g e t h e r i f t h e p o s i t i o n o f a s u c c e e d i n g sample on a s u r f a c e p r o f i l e c o u l d be a d j u s t e d s u c h t h a t t h e sample p r o j e c t s o n t o t h e n e x t u n a s s i g n e d p i x e l i n an image c o l u m n . Such a d a p t i v e s a m p l i n g c o u l d be a p p l i e d t o a s u r f a c e r e p r e s e n t e d by p l a n a r p a t c h e s . However, i t c o u l d n o t be a p p l i e d t o c u r v e d p a t c h e s , u n l e s s s e a r c h i n g f o r c a n d i d a t e 92 s a m p l e s w i t h i n p a t c h e s i s p e r f o r m e d , o r p a t c h e s a r e p a r t i t i o n e d t o make them s i n g l e - v a l u e d i n z. M e r g i n g o f t h e i n t e r p o l a t i o n and image s y n t h e s i s p r o c e s s e s has a n o t h e r a d v a n t a g e . T h e r e w o u l d no l o n g e r be a need t o e s t i m a t e t h e s u r f a c e g r a d i e n t a t a p o i n t f r o m n e a r e s t g r i d n e i g h b o u r s i n o r d e r t o compute p i x e l s h a d e . The g r a d i e n t c o u l d be d e t e r m i n e d d i r e c t l y from t h e e q u a t i o n o f t h e t r i a n g u l a r p a t c h c o n t a i n i n g t h e p o i n t . The s p e c u l a r s u r f a c e r e f l e c t a n c e model u s e d 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 d o e s not s a t i s f y p h y s i c a l law. The s p e c u l a r model i s d e s i r a b l e b e c a u s e i t h i g h l i g h t s s u r f a c e r e g i o n s e x h i b i t i n g h i g h c u r v a t u r e . A s p e c u l a r model c o n s i s t e n t w i t h p h y s i c a l law s h o u l d be a d o p t e d . The c o n t o u r s u p e r p o s i t i o n p r o g r a m a l s o r e q u i r e s improvement. The c u r r e n t p r o g r a m does n o t g u a r a n t e e c o n t o u r c l o s u r e . T h i s p r o b l e m i s i l l u s t r a t e d i n F i g u r e 1.12 where t h e w h i t e c o n t o u r e x h i b i t s a gap. A p r o g r a m t h a t would e x t r a c t t r u e c o n t o u r s f r o m t h e o r i g i n a l s u r f a c e model, and t h e n a l l o w t h e u s e r t o i n t e r a c t i v e l y d e l e t e e x t r a n e o u s c o n t o u r s m i g h t be d e s i r a b l e . A more r i g o r o u s a p p r o a c h s h o u l d be t a k e n t o t h e d e t e r m i n a t i o n o f s i g n a l l e v e l p r o b a b i l i t y d e n s i t y f u n c t i o n s i n t h e g r a d i e n t q u a n t i z a t i o n e x p e r i m e n t . C o n t i n u o u s d e n s i t y f u n c t i o n s were o b t a i n e d f r o m d i s c r e t e h i s t o g r a m s by l i n e a r i n t e r p o l a t i o n and s m o o t h i n g . The e f f e c t s o f t h e s e a p p r o x i m a t i o n s upon q u a n t i z a t i o n e r r o r and s i g n a l d i s t o r t i o n s h o u l d be i n v e s t i g a t e d , and b e t t e r a p p r o x i m a t i o n s s o u g h t . 93 The a s s e r t i o n was made t h a t a d i s t o r t i o n - f r e e image c o u l d n o t be r e c o n s t r u c t e d f r o m a s u r f a c e r e p r e s e n t e d by 8 - b i t g r a d i e n t s , even f o r l i m i t e d l i g h t s o u r c e movement. An e x p e r i m e n t s h o u l d be p e r f o r m e d t o e i t h e r v e r i f y o r d i s p r o v e t h i s a s s e r t i o n . A l s o , t h e t r a d e o f f between f r e e d o m o f l i g h t s o u r c e movement a n d image q u a l i t y s h o u l d be f u r t h e r i n v e s t i g a t e d . F i n a l l y , a n t i - a l i a s i n g t e c h n i q u e s s h o u l d be emp l o y e d t o smooth o u t j a g g e d , o c c l u d i n g s u r f a c e e d g e s i n i m a g e s . Such e d g e s a r e c o n s p i c u o u s a l o n g t h e o u t e r b o u n d a r y and c e n t r a l peak of t h e t e s t s u r f a c e u s e d i n t h e g r a d i e n t q u a n t i z a t i o n e x p e r i m e n t . 94 BIBLIOGRAPHY The f o l l o w i n g acronyms a r e u s e d i n t h e r e f e r e n c e s : ACM - A s s o c i a t i o n f o r Computing M a c h i n e r y ASP - A m e r i c a n S o c i e t y o f Photogrammetry I E E E - I n s t i t u t e o f E l e c t r i c a l and E l e c t r o n i c s E n g i n e e r s IRE - I n s t i t u t e o f R a d i o E n g i n e e r s SIAM - S o c i e t y f o r I n d u s t r i a l and A p p l i e d M a t h e m a t i c s 1. B a r n h i l l R.E., " R e p r e s e n t a t i o n and a p p r o x i m a t i o n o f s u r f a c e s " , M a t h e m a t i c a l S o f t w a r e I I I ( R i c e J.R., e d . ) , Academic P r e s s , 1977, pp. 69-120. 2. B u i Tuong Phong, " I l l u m i n a t i o n f o r computer g e n e r a t e d p i c t u r e s " , C o m m u n i c a t i o n s o f t h e ACM, v o l . 18, no. 6, June 1975, pp. 311-317. 3. Cook L.T., Dwyer S . J . , B a t n i t z k y S., and Lee K.R., "A t h r e e - d i m e n s i o n a l d i s p l a y s y s t e m f o r d i a g n o s t i c i m a g i n g a p p l i c a t i o n s " , I E E E Computer G r a p h i c s and A p p l i c a t i o n s , v o l . 3, no. 5, Aug. 1983, pp. 13-19. 4. D r a n c e S.M., p e r s o n a l c o m m u n i c a t i o n , 1984. 5. F o l e y J.D. and van Dam A., " 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 Computer G r a p h i c s " , A d d i s o n - W e s l e y , 1982. 6. F o r r e s t A.R., "On t h e r e n d e r i n g o f s u r f a c e s " , Computer G r a p h i c s , v o l . 13, no. 2, Aug. 1979, pp. 253-257. 7. F o w l e r R . J . , "DELTRI: a p r o g r a m f o r i n d u c t i v e l y c o m p u t i n g D e l a u n a y t r i a n g u l a t i o n s " , T e c h n i c a l R e p o r t 18, D e p t . o f G e o g r a p h y , Simon F r a s e r U n i v e r s i t y , B r i t i s h C o l u m b i a , 1977. 8. F u c h s H., Kedem Z.M., and U s e l t o n S.P., " O p t i m a l s u r f a c e r e c o n s t r u c t i o n f r o m p l a n a r c o n t o u r s " , C o m m u n i c a t i o n s o f t h e ACM, v o l . 20, no. 10, O c t . 1977, pp. 693-702. 9. G r e e n P . J . and S i b s o n R., "Computing D i r i c h l e t t e s s e l l a t i o n s i n t h e p l a n e " , The Computer J o u r n a l , v o l . 21, no. 2, May 1978, pp. 168-173. 10. H a r t W.M., "Computer p r o c e s s i n g o f v i s u a l d a t a : a u t o m a t e d p a t t e r n a n a l y s i s o f g l a u c o m a t o u s v i s u a l f i e l d s " , A r c h i v e s o f O p h t h a l m o l o g y , v o l . 99, no. 1, J a n . 1981, pp. 133-136. 95 11. H a r t W.M. and H a r t z R.K., " C o m p u t e r - g e n e r a t e d d i s p l a y f o r t h r e e - d i m e n s i o n a l s t a t i c p e r i m e t r y " , A r c h i v e s o f O p h t h a l m o l o g y , v o l . 100, no. 2, F e b . 1982, pp. 312-318. 12. H e i l R . J . and B r y c h S.M., "An a p p r o a c h f o r c o n s i s t e n t t o p o g r a p h i c r e p r e s e n t a t i o n o f v a r y i n g t e r r a i n " , ASP P r o c e e d i n g s o f t h e D i g i t a l T e r r a i n M o d e l s Symposium, May 1978, pp. 397-411. 13. H o r n B.K.P., " H i l l s h a d i n g and t h e r e f l e c t a n c e map", P r o c e e d i n g s o f t h e I E E E , v o l . 69, no. 1, J a n . 1981, pp. 14-47. 14. Lane J.M., C a r p e n t e r L.C., W h i t t e d T., and B l i n n J . F . , "Scan l i n e methods f o r d i s p l a y i n g p a r a m e t r i c a l l y d e f i n e d s u r f a c e s " , C o m m u n i c a t i o n s o f t h e ACM, v o l . 23, no. 1, J a n . 1980, pp. 23-34. 15. Lawson C.L., " S o f t w a r e f o r C 1 s u r f a c e i n t e r p o l a t i o n " , M a t h e m a t i c a l S o f t w a r e I I I ( R i c e J.R., e d . ) , A cademic P r e s s , 1977, pp. 161-194. 16. Mark D.M., " C o n c e p t s o f ' d a t a s t r u c t u r e ' f o r d i g i t a l t e r r a i n m o d e l s " , ASP P r o c e e d i n g s o f t h e D i g i t a l T e r r a i n M o d e l s Symposium, May 1978, pp. 24-31. 17. Max J . , " Q u a n t i z i n g f o r minimum d i s t o r t i o n " , IRE T r a n s a c t i o n s on I n f o r m a t i o n T h e o r y , v o l . I T - 6 , no. 1, Mar. 1960, pp. 7-12. 18. Newman W.M. and S p r o u l l R.F., " P r i n c i p l e s o f I n t e r a c t i v e Computer G r a p h i c s " , 2nd e d i t i o n , M c G r a w - H i l l , 1979. 19. N i e l s o n G., "Minimum norm i n t e r p o l a t i o n i n t r i a n g l e s " , SIAM J o u r n a l on N u m e r i c a l A n a l y s i s , v o l . 17, no. 1, F e b . 1980, pp. 44-62. 20. P e u c k e r T.K., F o w l e r R . J . , L i t t l e J . J . , and Mark D.M., "The t r i a n g u l a t e d i r r e g u l a r n e t w o r k " , ASP P r o c e e d i n g s o f t h e D i g i t a l T e r r a i n M o d e l s Symposium, May 1978, pp. 516-540. 21. S l o a n K.R. and Brown C M . , " C o l o r map t e c h n i q u e s " , Computer G r a p h i c s and Image P r o c e s s i n g , v o l . 10, no. 4, Aug. 1979, pp. 297-317. 22. W i r t s c h a f t e r J.D., B e c k e r W.L., Howe J.B., a n d Younge B.R., "Glaucoma v i s u a l f i e l d a n a l y s i s by computed p r o f i l e of n e r v e f i b e r f u n c t i o n i n o p t i c d i s c s e c t o r s " , O p h t h a l m o l o g y , v o l . 89, no. 3, Mar. 1982, pp. 255-266. 96 23. Woodham R . J . , " R e f l e c t a n c e map t e c h n i q u e s f o r a n a l y z i n g s u r f a c e d e f e c t s i n m e t a l c a s t i n g s " , T e c h n i c a l R e p o r t 457, A r t i f i c i a l I n t e l l i g e n c e L a b o r a t o r y , M a s s a c h u s e t t s I n s t i t u t e o f T e c h n o l o g y , June 1978. 24. Woodham R . J . , " P h o t o m e t r i c method f o r d e t e r m i n i n g s u r f a c e o r i e n t a t i o n from m u l t i p l e images", O p t i c a l E n g i n e e r i n g , v o l . 19, no. 1, J a n . 1980, pp. 139-144. 25. W r i g h t T . J . , "A tw o - s p a c e s o l u t i o n t o t h e h i d d e n l i n e p r o b l e m f o r p l o t t i n g f u n c t i o n s o f two v a r i a b l e s " , I E E E T r a n s a c t i o n s on Com p u t e r s , v o l . C-22, no. 1, J a n . 1973, pp. 28-33. 97 APPENDIX A - COMPUTING A DELAUNAY TRIANGULATION A 2D T h i e s s e n t e s s e l l a t i o n p a r t i t i o n s a p l a n e i n t o p r o x i m i t y r e g i o n s d e f i n e d a b o u t nodes s c a t t e r e d i n t h e p l a n e . P o i n t s w i t h i n a p r o x i m i t y , o r T h i e s s e n , r e g i o n a r e c l o s e r t o t h e r e g i o n ' s d e f i n i n g node t h a n t o any o t h e r i n t h e node s e t . The b o u n d a r i e s o f t h e T h i e s s e n r e g i o n s a r e conve x p o l y g o n s c a l l e d V o r o n o i p o l y g o n s . Nodes a r e n e i g h b o u r s i f t h e i r V o r o n o i p o l y g o n s s h a r e a common edge. The D e l a u n a y t r i a n g u l a t i o n i s t h e g r a p h d u a l o f t h e V o r o n o i d i a g r a m , and i s f o r m e d by j o i n i n g n e i g h b o u r i n g nodes w i t h l i n e s e gments. T h e s e segments become t r i a n g l e edges and t h e nodes become t r i a n g l e v e r t i c e s . An a l g o r i t h m f o r c o m p u t i n g a D e l a u n a y t r i a n g u l a t i o n may t h e r e f o r e p r o c e e d by f i n d i n g t h e g r a p h of n e i g h b o u r i n g nodes i n a V o r o n o i d i a g r a m , and t r a n s f o r m i n g t h e n e i g h b o u r l i n k s i n t o t r i a n g l e e d g e s . I t i s t h i s a p p r o a c h t h a t i s t a k e n by F o w l e r ( 1 9 7 7 ) . F o w l e r ' s a l g o r i t h m g e n e r a t e s a t e s s e l l a t i o n o f N nodes f r o m an e x i s t i n g t e s s e l l a t i o n o f N-1 nodes s u c h t h a t t h e i n s e r t i o n o f t h e N ' t h node i s p e r f o r m e d l o c a l l y . T h i s i n s e r t i o n i s n o t h i n g more t h a n t h e c o n s t r u c t i o n o f t h e new node's T h i e s s e n r e g i o n f r o m p o r t i o n s o f n e a r b y r e g i o n s i n t h e e x i s t i n g t e s s e l l a t i o n . The n e i g h b o u r l i n k a g e s o f t h e s e d i m i n i s h e d r e g i o n s a r e t h e o n l y ones a f f e c t e d by t h e i n s e r t i o n o f t h e new node. The node NEAR, c l o s e s t t o t h e new node N, d e f i n e s a T h i e s s e n r e g i o n w h i c h c o n t a i n s N. The r e g i o n d e f i n e d by node N a l s o c o n t a i n s N. T h e s e two r e g i o n s must i n t e r s e c t , and t h e i r V o r o n o i p o l y g o n s s h a r e an edge. Nodes NEAR and N a r e t h e r e f o r e n e i g h b o u r s . The l i n e c o n t a i n i n g t h e s h a r e d edge i n t e r s e c t s t h e p o l y g o n s o f two n e i g h b o u r s o f node NEAR. S i n c e V o r o n o i p o l y g o n s a r e c o n v e x , a l i n e i n t e r s e c t s any p o l y g o n i n a t most two p o i n t s . Of t h e two i n t e r s e c t i n g p o i n t s on e a c h p o l y g o n , t h e one c l o s e r t o t h e m i d p o i n t of t h e segment j o i n i n g N t o NEAR i s an e n d p o i n t of t h e s h a r e d e dge. S t a r t i n g w i t h t h e e n d p o i n t t h a t f a l l s t o t h e r i g h t o f t h e d i r e c t e d segment f r o m N t o NEAR, t h e V o r o n o i p o l y g o n of node N may be t r a c e d o u t i n a c l o c k w i s e d i r e c t i o n a b o u t N u n t i l i t c l o s e s upon i t s e l f a t t h e e n d p o i n t t o t h e l e f t of t h e d i r e c t e d segment. The p r o c e d u r e i s o u t l i n e d i n t h e f o l l o w i n g a l g o r i t h m . (1) L o c a t e t h e c l o s e s t node NEAR t o t h e node N, 'and s e t CURRENT := NEAR. The c l o s e s t node i s f o u n d by a w a l k i n g s e a r c h a l o n g t h e l i n k s between n e i g h b o u r i n g nodes i n t h e e x i s t i n g t e s s e l l a t i o n . I f a c a n d i d a t e node i s n o t t h e c l o s e s t t o N, t h e n one o f i t s n e i g h b o u r s i s c l o s e r t o N t h a n i t i s . The s e a r c h a d v a n c e s t o t h i s node. S t a r t i n g a t an a r b i t r a r y node, t h e s e a r c h c o n t i n u e s from node t o node u n t i l one i s f o u n d t h a t i s c l o s e r t o N t h a n any o f i t s n e i g h b o u r s . T h i s i s t h e c l o s e s t node t o N. 98 (2) C o n s t r u c t t h e p e r p e n d i c u l a r b i s e c t o r of t h e l i n e segment between N and CURRENT. (3) The b i s e c t o r i n t e r s e c t s t h e p o l y g o n o f a n e i g h b o u r o f node CURRENT s u c h t h a t t h e p o i n t o f i n t e r s e c t i o n l i e s t o t h e r i g h t o f t h e d i r e c t e d segment f r o m N t o CURRENT. A s s i g n t o NEXT t h e l a b e l o f t h a t n e i g h b o u r . (4) I f NEXT * NEAR, t h e n s e t CURRENT := NEXT and r e p e a t s t e p s 2 t o 4. (5) S t o p . The i n s e r t i o n o f node N c r e a t e s new n e i g h b o u r l i n k a g e s and d e s t r o y s some e x i s t i n g l i n k s . The new node N must be l i n k e d t o t h o s e e x i s t i n g nodes whose new V o r o n o i p o l y g o n s s h a r e an edge w i t h N's p o l y g o n . T h e s e u p d a t e s a r e e a s i l y p e r f o r m e d d u r i n g t h e p r o c e s s o f g e n e r a t i n g t h e V o r o n o i p o l y g o n o f node N. The b i s e c t e d segments d e f i n e new l i n k s between N and t h e e x i s t i n g n o d e s . L i n k s c o r r e s p o n d i n g t o o l d edges t h a t a r e c o m p l e t e l y c o n t a i n e d w i t h i n N's p o l y g o n a r e d e l e t e d . F i g u r e s A . l and A.2 i l l u s t r a t e p a r t o f a T h i e s s e n t e s s e l l a t i o n i n w h i c h t h e d a s h e d l i n e s b e l o n g t o t h e V o r o n o i d i a g r a m and t h e s o l i d l i n e s t o t h e D e l a u n a y t r i a n g u l a t i o n . Node 1 i s t h e c l o s e s t node t o N. The p e r p e n d i c u l a r b i s e c t o r o f t h e segment from N t o node 1 i s f o l l o w e d u n t i l v e r t e x b on t h e p o l y g o n o f node 2 i s r e a c h e d . Node 2 i s l i n k e d t o N and N i s l i n k e d t o node 2. The b i s e c t o r o f t h e segment f r o m N t o node 2 i s t r a c e d t o v e r t e x c , a t w h i c h t i m e nodes 3 and N a r e l i n k e d . The p r o c e s s c o n t i n u e s t h r o u g h v e r t e x d and t h e n e, whereupon t h e p a t h r e t u r n s t o t h e p o l y g o n o f node 1. L i n k a g e s a r e e s t a b l i s h e d between N and node 4, and between N and node 1. The edge y z from t h e o l d V o r o n o i d i a g r a m i s c o n t a i n e d w i t h i n t h e new p o l y g o n of node N, and t h e r e f o r e t h e l i n k between nodes 1 and 3 i s d e l e t e d . The a l g o r i t h m s t a r t s w i t h t h r e e n o n - c o l l i n e a r dummy nodes d e f i n i n g a t r i a n g u l a r r e g i o n t h a t c o n t a i n s t h e co n v e x h u l l o f th e node s e t . A f t e r a l l t h e nodes have been i n s e r t e d , l i n k s t o t h e s e dummy nodes a r e s t r i p p e d f r o m t h e d a t a s t r u c t u r e r e p r e s e n t i n g t h e f i n a l t r i a n g u l a t i o n . The T IN d a t a s t r u c t u r e r e c o r d s a network o f t r i a n g l e v e r t i c e s ( t h e nodes o f t h e V o r o n o i d i a g r a m ) r a t h e r t h a n a network o f t r i a n g l e s . I n s t e a d o f e a c h t r i a n g l e b e i n g l i n k e d t o i t s t h r e e n e i g h b o u r s , e a c h v e r t e x i s l i n k e d t o i t s n e i g h b o u r i n g v e r t i c e s s u c h t h a t t h e l i n k s r e p r e s e n t t r i a n g l e e d g e s . P e u c k e r e t a l . (1978) a r g u e t h a t a network o f t r i a n g l e v e r t i c e s i s more s t o r a g e e f f i c i e n t t h a n a network o f t r i a n g l e s . I n a t r i a n g l e -b a s e d d a t a s t r u c t u r e , e a c h t r i a n g l e r e q u i r e s p o i n t e r s t o i t s 3 v e r t i c e s and i t s 3 n e i g h b o u r s f o r a t o t a l of 6. F o r a d a t a domain c o n t a i n i n g N p o i n t s , B o f w h i c h a r e on t h e boun d a r y , 6(2N-B-2) = 12N-6B-12 p o i n t e r s a r e r e q u i r e d i n a d d i t i o n t o t h e 99 F i g u r e A.1 Node N i n t r o d u c e d i n t o an e x i s t i n g t e s s e l l a t i o n F i g u r e A.2 Node N i n c o r p o r a t e d i n t o a new t e s s e l l a t i o n 100 s p a c e o c c u p i e d by t h e p o i n t c o o r d i n a t e s . F o r a v e r t e x - b a s e d d a t a s t r u c t u r e , o n l y 3(2N-B-2)+B = 6N-2B-6 p o i n t e r s n e e d t o be s t o r e d . T h i s r e p r e s e n t s a s a v i n g s i n s t o r a g e o f a b o u t 50 p e r c e n t . The d a t a s t r u c t u r e i s a l i s t o f v e r t i c e s where e a c h v e r t e x i n t h e l i s t p o i n t s t o a number o f o t h e r v e r t i c e s i n t h e l i s t . The l i s t i s a o n e - d i m e n s i o n a l a r r a y o f r e c o r d s , e a c h c o n t a i n i n g i n f o r m a t i o n a b o u t one t r i a n g l e v e r t e x . A r e c o r d c o n t a i n s t h e ( x , y , z ) c o o r d i n a t e s o f t h e v e r t e x and a l i s t o f i t s n e i g h b o u r i n g v e r t i c e s i n t h e t r i a n g u l a t i o n . I n s t e a d o f r e c o r d i n g a l l v e r t e x n e i g h b o u r s , e a c h r e c o r d c o n t a i n s a n e i g h b o u r c o u n t a n d a p o i n t e r t o where t h e s e n e i g h b o u r s a r e l i s t e d . The n e i g h b o u r s of a l l v e r t i c e s a r e s t o r e d i n a n o t h e r l i s t c a l l e d t h e n e i g h b o u r s l i s t . The n e i g h b o u r s a r e g i v e n by t h e i r i n d i c e s i n t o t h e v e r t e x a r r a y . T h i s d a t a s t r u c t u r e , i l l u s t r a t e d i n F i g u r e A.3, i s f u r t h e r d i s c u s s e d i n P e u c k e r e t a l . ( 1 9 7 8 ) . 101 VERTEX LIST NEIGHBOUR LISTS Coordinates Neighbour Neighbour Count List Pointer J: • • • • X I *I Z I A M • • X J y J Z J 6 N • • • Neighbours ' of node I Neighbours ^ of node J N+B-l: F i g u r e A.3 How a t r i a n g l e edge d e f i n e d by v e r t i c e s I and J i s r e p r e s e n t e d i n t h e T I N d a t a s t r u c t u r e 102 APPENDIX B ~ SMOOTH ( C 1 ) INTERPOLATION IN TRIANGLES The f u n c t i o n v a l u e F a t an i n t e r i o r p o i n t ( x , y ) o f an a r b i t r a r y t r i a n g l e T may be i n t e r p o l a t e d f r o m d a t a a t t h e v e r t i c e s by t h e f o l l o w i n g s t e p s : (1) T r a n s f o r m t h e p o i n t ( x , y ) i n T t o a p o i n t ( s ( x , y ) , t ( x , y ) ) i n a s t a n d a r d t r i a n g l e S w i t h v e r t i c e s a t ( 0 , 0 ) , ( 1 , 0 ) , and ( 0 , 1 ) . (2) P e r f o r m t h e i n t e r p o l a t i o n w i t h i n S t o o b t a i n f ( s , t ) . (3) T r a n s f o r m ( s , t ) back t o i t s p o s i t i o n ( x , y ) i n T s u c h t h a t F ( x , y ) = f ( s , t ) . The a r b i t r a r y t r i a n g l e T w i t h v e r t i c e s V, = ( x , , y , ) , V 2 = ( x 2 , y 2 ) r and V 3 = ( x 3 , y 3 ) i s t r a n s f o r m e d t o t h e s t a n d a r d t r i a n g l e S, s u c h t h a t t h e i n t e r i o r o f T i s mapped t o t h e i n t e r i o r o f S. The t r a n s f o r m a t i o n i s a c o n c a t e n a t i o n o f f o u r g e o m e t r i c t r a n s f o r m a t i o n s : t r a n s l a t i o n , r o t a t i o n , s h e a r i n g , and s c a l i n g . The t r a n s f o r m a t i o n i l l u s t r a t e d i n F i g u r e B.1 mapping V, t o ( 0 , 0 ) , V 2 t o ( 1 , 0 ) , and V 3 t o (0,1) i s : s = ( x - x , ) ( y 3 - y 1 ) - ( x 3 - x , ) ( y - y , ) (B.1) U 2 - x , ) (y 3-y,) - U 3 - x , M y 2 - y , ) t = - ( x - x , ) ( y 2 - y , ) + ( x 2 - x , ) ( y - y , ) ( x 2 - x , ) ( y 3 - y , ) - ( x 3 - x , ) ( y 2 - y , ) The t r a n s f o r m a t i o n c h a n g e s t h e p o s i t i o n o f a p o i n t ( x , y ) b u t not i t s f u n c t i o n v a l u e F ( x , y ) . T h e r e f o r e , f ( s , t ) = F ( x , y ) and f ( 0 , 0 ) = F ( V , ) f ( 1 , 0 ) = F ( V 2 ) f ( 0 , 1 ) = F ( V 3 ) D e r i v a t i v e s , however, a r e n o t p r e s e r v e d and a r e t r a n s f o r m e d t o : 103 F i g u r e B . l T r i a n g l e t r a n s f o r m a t i o n s 104 f = F x + F y s x s y  1 s f . = F x. + F y. t x t y  1  where t h e p a r t i a l d e r i v a t i v e s o f x and y w i t h r e s p e c t t o s and t a r e c o n s t a n t s . T h e s e d e r i v a t i v e s may be o b t a i n e d f r o m t h e i n v e r s e t r a n s f o r m a t i o n by s o l v i n g f o r x and y i n t e r m s o f s and t . The i n v e r s e of t h e t r a n s f o r m a t i o n i n E q u a t i o n s B.I i s : x = ( 1 - s - t ) x , + s x 2 + t x 3 (B.2) y = ( 1 - s - t ) y , + s y 2 + t y 3 N i e l s o n ' s (1980) i n t e r p o l a t i o n f u n c t i o n o v e r t h e s t a n d a r d t r i a n g l e i s : f ( s , t ) = f ( s , 0 ) + f ( 0 , t ) - f ( 0 , 0 ) + t g ( s ) + s g ( l - t ) - 2 ( 1 - s ) 2 ( l - t ) / 1 _ t + ( s t / 2 ) / q(w) - wd-w)h(w) dw (B.3) J s w z ( 1 - w ) 2 where g(w) = f(w,1-w) - f(w,0) - f(0,1-w) + f ( 0 , 0 ) and h(w) = f (w,1-w) + f (w,1-w) - f (w,0) - f (0,1-w). S t 5 t T h i s f u n c t i o n i n t e r p o l a t e s t o t h e b o u n d a r y v a l u e s f ( s , 0 ) , f ( 0 , t ) , and f ( s , 1 - s ) , and t o t h e n o r m a l s f ( s , 1 - s ) + f ( s , 1 - s ) on t h e h y p o t e n u s e o f S. s When f u n c t i o n v a l u e s and d e r i v a t i v e s a r e g i v e n o n l y a t t h e t r i a n g l e v e r t i c e s , t h e n t h e b o u n d a r y c o n d i t i o n s may be i n t e r p o l a t e d f r o m t h e s e d a t a . C u b i c H e r m i t e i n t e r p o l a n t s a r e us e d f o r t h e b o u n d a r y f u n c t i o n s , a n d l i n e a r i n t e r p o l a n t s a r e us e d f o r t h e n o r m a l d e r i v a t i v e s on t h e h y p o t e n u s e . The i n t e r p o l a n t i n E q u a t i o n B.3 i n t e r p o l a t e s t o f u n c t i o n v a l u e s on a l l t h r e e e dges but t o n o r m a l s on o n l y one, t h e h y p o t e n u s e o f S. T h i s means t h a t i n t h e a r b i t r a r y t r i a n g l e T, t h e f u n c t i o n F ( x , y ) i n t e r p o l a t e s t o t h e n o r m a l s o f o n l y one edge as w e l l . To c o r r e c t f o r t h i s , T i s t r a n s f o r m e d t o S t h r e e t i m e s , where e a c h t i m e a d i f f e r e n t edge i n T i s mapped t o t h e h y p o t e n u s e i n S. A w e i g h t e d sum o f t h e t h r e e r e s u l t i n g i n t e r p o l a n t s i n t e r p o l a t e s t o f u n c t i o n v a l u e s and t o f i r s t - o r d e r d e r i v a t i v e s on a l l t h r e e e d g e s o f T. I n t r o d u c t i o n o f b a r y c e n t r i c c o o r d i n a t e s b,, b 2 , and b 3 h e l p s t o keep t r a c k o f t h e d i f f e r e n t t r a n s f o r m a t i o n s . T h e s e c o o r d i n a t e s a r e d e f i n e d by: 105 x = t ^ x , + b 2 x 2 + b 3 x 3 y = b,y, + b 2 y 2 + b 3 y 3 1 « b, + b 2 + b 3 F o r t h e t r a n s f o r m a t i o n i l l u s t r a t e d i n F i g u r e B.1 where V , f V 2 , V 3 a r e mapped t o ( 0 , 0 ) , ( 1 , 0 ) , ( 0 , 1 ) , t h e b a r y c e n t r i c c o o r d i n a t e s b 2 and b 3 t a k e on t h e r o l e s o f s and t , r e s p e c t i v e l y (See E q u a t i o n s B . 2 ) . I f t h e v e r t i c e s o f t h e t r i a n g l e T r e m a i n numbered c o n s e c u t i v e l y i n a c o u n t e r - c l o c k w i s e d i r e c t i o n a r o u n d t h e t r i a n g l e , t h e n t h e two o t h e r t r a n s f o r m a t i o n s map V ^ V ^ V , and V 3 , V , , V 2 t o ( 0 , 0 ) , ( 1 , 0 ) , ( 0 , 1 ) . U s i n g i n d i c e s i , j , and k, t h e t h r e e t r a n s f o r m a t i o n s c a n be c o n v e n i e n t l y e x p r e s s e d a s : V. ==> ( 0 , 0 ) V ==> ( 1 , 0 ) = = > ( 0 , 1 ) where ( i , j , k ) i s a member of t h e s e t I = { ( 1 , 2 , 3 ) , ( 2 , 3 , 1 ) , ( 3 , 1 , 2 ) } . E a c h i n t e r p o l a n t c a n t h e n be w r i t t e n a s : F . ( x , y ) = f ( b ( x , y ) , b f c ( x , y ) ) N i e l s o n shows t h a t t h e w e i g h t e d sum F ( x , y ) = b a b a F ^ x ^ y ) + b ^ F ^ x , ^ ) + b , b 2 F 3 ( x , y ) b 1 b 2 + b 1 b 3 + b 2 b 3 i n t e r p o l a t e s t o F and i t s f i r s t - o r d e r d e r i v a t i v e s on t h e e n t i r e b o u n d a r y o f T. R e p l a c i n g b o u n d a r y f u n c t i o n s w i t h c u b i c H e r m i t e p o l y n o m i a l s and i n t e r p o l a t i n g b o u n d a r y n o r m a l d e r i v a t i v e s l i n e a r l y f r o m t h o s e a t t h e v e r t i c e s , a n i n e - p a r a m e t e r C 1 i n t e r p o l a n t i s o b t a i n e d . T h i s i n t e r p o l a n t i s g i v e n i n t h e f o l l o w i n g , where t h e summation i s o v e r a l l t r i p l e s ( i , j , k ) i n t h e s e t I : F ( x , y ) = Z [ F ( V . ) [ b j 2 ( 3 - 2 b / ) + 6wb f (b^A + b.A. ^ ] + F k { V i ) [ b i b k + w b / ( 3 b * A / y + b y " b i t ) ]  + F ; ( v / ) [ b / b y + v b i i 3 b j k i k + bk ' b y ) ] ] 106 where F ) ( V . ) = (x.-x.) F (V.) + ( y , - y , ) F (V. ), j i j i x i j i y i w = b i b 2 b 3 / ( b 1 b 2 + b 1 b 3 + b 2 b 3 ) , K.. = d e j ' + l e ^ ' - l e * ! 2 ) / ( 2 | e y | 2 ) , and |e. | 2 = U^.-x^) 2 + ( y ^ . - y ^ ) 2 . 

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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0096282/manifest

Comment

Related Items