text:
Hierarchical approaches to the hidden surface problem
Hierarchical approaches to the hidden surface problem Dadoun, Norm 1982
Title Hierarchical approaches to the hidden surface problem
Creator Dadoun, Norm
Description A general method for performing hidden line/surface elimination in complex domains is presented. This method uses a preprocessed hierarchical organization of the environment features. Convex polyhedra are used as elements of this hierarchy. Each polyhedron forms a convex approximation of the environment features which it contains. This hierarchy is used to provide efficient algorithms for solving the intersection, sorting and clipping subproblems associated with the hidden line/surface problem. Methods for constructing and using this hierarchy are discussed. Recent results from computational geometry are applied to element construction and intersection processing.
Program Computer Science
Computer Science, Department of
831-UBC_1983_A6_7 D34.pdf [ 5.03MB ]
HIERARCHICAL APPROACHES TO THE HIDDEN SURFACE PROBLEM BY NORM DADOUN B.Sc. (Honours) U n i v e r s i t y of Western O n t a r i o 1977 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE IN THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept t h i s t h e s i s as conforming to the r e q u i r e d standard. THE UNIVERSITY OF BRITISH COLUMBIA December, 1982 © Norm Dadoun, 1982 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y available for reference and study. I further agree that permission for extensive copying of t h i s thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. I t i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of CotApUT^fl $ C I £ A / C £ The University of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 DE-6 (3/81) i i HIERARCHICAL APPROACHES TO THE HIDDEN SURFACE PROBLEM Norm Dadoun ABSTRACT A general method for performing hidden l i n e / s u r f a c e e l i m i n a t i o n in complex domains i s presented. T h i s method uses a preprocessed h i e r a r c h i c a l o r g a n i z a t i o n of the environment f e a t u r e s . Convex polyhedra are used as elements of t h i s h i e r a r c h y . Each polyhedron forms a convex approximation of the environment f e a t u r e s which i t c o n t a i n s . T h i s h i e r a r c h y i s used to provide e f f i c i e n t a l g o r i t h m s f o r s o l v i n g the i n t e r s e c t i o n , s o r t i n g and c l i p p i n g subproblems a s s o c i a t e d with the hidden l i n e / s u r f a c e problem. Methods f o r c o n s t r u c t i n g and using t h i s h i e r a r c h y are d i s c u s s e d . Recent r e s u l t s from computational geometry are a p p l i e d to element c o n s t r u c t i o n and i n t e r s e c t i o n p r o c e s s i n g . i i i T able of Contents A b s t r a c t i i Table of Contents i i i L i s t of F i g u r e s v Acknowledgements v i CHAPTER 1: I n t r o d u c t i o n 1 1.1 The Hidden L i n e / S u r f a c e Problem 2 1.2 'Computational A c o u s t i c s ' 3 1.3 R e l a t i n g A c o u s t i c s and Graphics 7 1.4 T h e s i s O u t l i n e 9 CHAPTER 2: D e f i n i t i o n s 11 2.1 Environment Representations 11 2.2 Beam D e f i n i t i o n 13 2.3 Problem D e f i n i t i o n 15 2.4 Approximation S t r u c t u r e D e f i n i t i o n s 1 8 CHAPTER 3: H i e r a r c h i c a l P r o c e s s i n g 23 3.1 Previous Work 23 3.2 Our Approach 25 3.3 P r o c e s s i n g O u t l i n e 26 3.4 P r e p r o c e s s i n g 27 3.4.1 Basic Representation 28 3.4.2 Segmentation 33 3.4.3 Approximation H i e r a r c h i e s 38 CHAPTER 4: Algorithms Which Use The H i e r a r c h y 40 4.1 S o r t i n g 49 4.2 I n t e r s e c t i o n 53 4.3 C l i p p i n g 57 4.3.1 The C l i p p i n g Routine 58 4.3.2 Previous Related Work 64 4.3.3 W e i l e r ' s Method and Suggested Improvements 68 CHAPTER 5: H i e r a r c h y Approximation Elements 75 5.1 Two-Dimensional Approximation Elements 76 5.1.1 C o n s t r u c t i o n 77 5.1.2 Storage 78 5.1.3 I n t e r s e c t i o n 80 5.2 Three-Dimensional Approximation Elements 88 5.2.1 C o n s t r u c t i o n 89 5.2.2 Storage 93 5.2.3 I n t e r s e c t i o n . 94 5.3 General Comparisons 101 5.4 Hyb r i d H i e r a r c h i e s 103 i v CHAPTER 6: Summary, Conclus i o n s and Furth e r Work 106 6. 1 Summary 106 6.2 Conclus i o n s 107 6.3 Furth e r Work 109 6.3.1 Graphics 109 6.3.2 Geometric Modeling and Computer-Aided Design .. 111 6.3.3 Computational Geometry 112 6.3.4 Computational A c o u s t i c s 113 References 114 V L i s t .of F i g u r e s 1 ."1 A c o u s t i c s S i m u l a t i o n 6 2.1 C l i p p i n g a Polygon 17 2.2 Minimum Bounding Polygons 19 3.1 Required P r e p r o c e s s i n g 28 3.2 Converting Sweep to Boundary Re p r e s e n t a t i o n s 30 3.3 Segmentation Using An A r t i c u l a t i o n Point 36 4.1 Proposed Algorithms - Top L e v e l 41 4.2 Proposed Algorithms - Examine 42 4.3 Proposed Algorithms - C l i p p i n g - C l i p 45 4.4 Using I n t e r v a l s f o r S p a t i a l Ordering 51 4.5 Sutherland-Hodgman C l i p p i n g 66 4.6 Precomputed I n t e r s e c t i o n C l i p p i n g 67 5.1 Minimum Rectangle C o n s t r u c t i o n ' 79 5.2 Inner Sequence Representation 81 5.3 Outer Sequence Representation 83 5.4 Monotone Polygonal Chains 84 5.5 Lemma 5.2 Diagram 86 5.6 2D Approximation Summary 88 5.7 Bounding Box C o n s t r u c t i o n Counter-Example 91 5.8 Removing a Vertex 95 5.9 Removing a Bounding Half-Space 97 5.10 3D Approximation Summary 100 v i Acknowledgements Over the long haul many people have helped me out, both i n t e l l e c t u a l l y and s p i r i t u a l l y ; there are f a r too many to mention them a l l in t h i s b r i e f space. Thanks t o John R'adke and the mul t i t u d e of f o l k s I've l i v e d with f o r the wonder and beauty of A r m a d i l l o e s and h e l p i n g me to r e a l i z e that I w i l l never p l a y hockey. To Jimbo' and Iggy (and other department i n h a b i t a n t s ) f o r doing sounding board i m i t a t i o n s and h e l p i n g to generate ideas. To Peg f o r the i n v a l u a b l e use of Bessie Toyota without whom I'd s t i l l be camped out i n my o f f i c e . To my s u p e r v i s o r David K f o r great b r a i n s t o r m i n g s e s s i o n s and the uncanny a b i l i t y to focus a t t e n t i o n on the e s s e n t i a l s . F i n a l l y , to John Walsh f o r combining music, g r a p h i c s , and geometry by dreaming up computational a c o u s t i c s and showing me how much fun i t i s . 1 CHAPTER 1: I n t r o d u c t i o n T h i s t h e s i s d e s c r i b e s ways of s t r u c t u r i n g environment d e s c r i p t i o n s h i e r a r c h i c a l l y - to s o l v e the hidden l i n e / s u r f a c e e l i m i n a t i o n problem e f f i c i e n t l y . T h i s t h e s i s a l s o b r i n g s some of the r e s u l t s and a n a l y t i c techniques i n computational geometry to bear on a computer g r a p h i c s problem. Computational geometry i s a r e l a t i v e l y new f i e l d of r e s e a r c h which takes an a l g o r i t h m i c approach to c l a s s i c a l and modern geometric problems. According to Shamos and Hoey [ShamHoey,76,p.208], two of the e a r l y r e s e a r c h e r s in the f i e l d , "the task of computational geometry i s to r e l a t e the geometric p r o p e r t i e s of f i g u r e s to the complexity of algorithms that manipulate them." The r e s e a r c h i n t h i s area uses the techniques of computational complexity to compare the e f f i c i e n c i e s of d i f f e r e n t a l g o r i t h m s which p r o v i d e a s o l u t i o n to a given geometric problem. By comparing the p r e p r o c e s s i n g , storage, and computation time c o s t s of v a r i o u s geometric a l g o r i t h m s , the 'best' a l g o r i t h m f o r a p a r t i c u l a r problem can o f t e n be i d e n t i f i e d . Although many of the r e s u l t s i n computational geometry are i d e a l l y s u i t e d to p r a c t i c a l a p p l i c a t i o n in computer g r a p h i c s , most work in computer g r a p h i c s has yet to take advantage of them. 2 1.1 The Hidden L i n e / S u r f a c e Problem The hidden l i n e / s u r f a c e problem i s w e l l known i n computer g r a p h i c s [NewSpr,79] [FolVan,82] and a r i s e s from a d e s i r e to compute r e a l i s t i c two-dimensional images from three-dimensional data. In r e n d e r i n g a l i n e drawing, hidden l i n e removal r e f e r s to the i d e n t i f i c a t i o n of v i s i b l e l i n e segments and/or the e x c l u s i o n of l i n e segments occluded or hidden by opaque o b j e c t s . Hidden surface' removal r e f e r s to the c l o s e l y r e l a t e d problem i n doing shaded renderings on a r a s t e r or s c a n - l i n e d i s p l a y . The f i r s t s o l u t i o n of e i t h e r of these problems to appear i n the l i t e r a t u r e was p a r t of L. G. Roberts's [Rob,63] e a r l y work in computational v i s i o n . A survey and c a t e g o r i z a t i o n of e x i s t i n g s o l u t i o n s to these problems was produced in 1974 by Sutherland, S p r o u l l , and Schumacker [SuSprSch,74]. The survey remains a r e l e v a n t e xegesis of approaches to these problems. The a l g o r i t h m s d i s c u s s e d are d i v i d e d i n t o three general approaches: object space a l g o r i t h m s , image space a l g o r i t h m s and l i s t p r i o r i t y a l g o r i t h m s . The o b j e c t space algorithms perform t h e i r computations to a r b i t r a r y p r e c i s i o n without regard to d i s p l a y r e s o l u t i o n l i m i t a t i o n s . The image space a l g o r i t h m s take advantage of known r e s o l u t i o n l i m i t a t i o n s to l i m i t the amount of computation a s s o c i a t e d with a r e n d e r i n g . L i s t p r i o r i t y a l g o r i t h m s do not r e s t r i c t t h e i r computations to o b j e c t space or image space but compute r e l a t i v e p r i o r i t i e s between 3 comparable s u r f a c e s . These p r i o r i t i e s are used to q u i c k l y determine the v i s i b l e components when doing a r e n d e r i n g . We w i l l examine the hidden s u r f a c e and r e l a t e d problems and w i l l p resent a new h i e r a r c h i c a l o r g a n i z a t i o n to a i d i n the s o l u t i o n of these problems. The al g o r i t h m s presented w i l l g e n e r a l l y operate in o b j e c t space but can be m o d i f i e d to take advantage of image r e s o l u t i o n l i m i t a t i o n s . 1.2 'Computat i o n a l Acoust i e s ' A minor d i g r e s s i o n here w i l l serve to e x p l a i n the background of and m o t i v a t i o n f o r our re s e a r c h . Our i n t e r e s t i n t h i s area d i d not come out of c o n v e n t i o n a l work in computer gra p h i c s but arose from an ongoing r e s e a r c h p r o j e c t i n v o l v i n g computer s i m u l a t i o n of concert h a l l a c o u s t i c s [Wal,79] [Wal,80] [WalDad,8l] [WalDad,82]. The system uses a geometric r e p r e s e n t a t i o n of a room or concert h a l l and prov i d e s an a u d i b l e s i m u l a t i o n of the sound f i e l d experienced at any p o s i t i o n w i t h i n t h i s environment. T h i s s i m u l a t i o n i s based on the assumption that the a c o u s t i c a l e f f e c t s w i t h i n a room or con c e r t h a l l can be adequately modeled by a combination of ge o m e t r i c a l a c o u s t i c s and a l o c a l i z e d theory of d i f f r a c t i o n [ P ier,81] [ K e l l , 5 8 ] . Geometrical a c o u s t i c s models sound as emanating from a v i b r a t i n g body i n wavefronts. T h e r e f o r e , a l l a c o u s t i c a l 4 e f f e c t s at a given r e c e i v e r p o s i t i o n can be p r e d i c t e d by t r a c i n g these wavefronts as sound beams (ray bundles or p e n c i l s ) from the source, through r e f l e c t i o n s , to that p o s i t i o n . I t i s e s s e n t i a l to note the d i f f e r e n c e between a 'beam' which i s a s o l i d angle with a f i n i t e c r o s s - s e c t i o n and a 'ray' which i s a zero-width v e c t o r . T h i s model i s fundamentally d i f f e r e n t from other r e s e a r c h models [KrokStrSor,68] [SchrAtal,63] i n that i t uses beams rather than r a y s . A beam when s t r i k i n g a c r o s s an edge w i l l ' s p l i t ' i n t o two r e f l e c t e d beams. A ray, being zero-width, can never ' s p l i t ' . D i f f r a c t i o n i s the phenomenon which allows sound to 'bend' around c o r n e r s . A l o c a l i z e d edge-based model of d i f f r a c t i o n i s i n c o r p o r a t e d by no t i n g when a sound beam s t r i k e s an edge at which d i f f r a c t i o n can occur. That edge then becomes a secondary source p o s i t i o n with a number of beams emanating d i r e c t l y from i t . T h i s model of d i f f r a c t i o n would be d i f f i c u l t to i n c o r p o r a t e i n a r a y - t r a c i n g system because "a ray ... would impinge upon an edge ... with p r o b a b i l i t y z ero" [Wal,79,p.241]. The a u d i b l e s i m u l a t i o n system i s d i v i d e d i n t o three stages (see F i g 1 .1) : a) The c o n s t r u c t i o n of a geometric model of a room using a Computer-Aided A r c h i t e c t u r a l Design (CAAD) system [BaEaHen , 7 7 ] [BaEaHen,79]. The c u r r e n t system uses a boundary r e p r e s e n t a t i o n d e f i n e d by p l a n a r faces, edges and v e r t i c e s . More d e t a i l s about our r e p r e s e n t a t i o n are given in Chapter 2 ; the i s s u e s of d e a l i n g with d i f f e r e n t i n i t i a l r e p r e s e n t a t i o n s are addressed i n Chapter 3 . b) The geometric model i s then used in the sound beam-tracing. A r e c e i v e r p o s i t i o n and s e v e r a l sound source p o s i t i o n s are defined" w i t h i n the- model. Sound can be thought of as emanating s p h e r i c a l l y from each source p o s i t i o n . T h i s expanding sphere i s broken i n t o a number of sound beams or s o l i d a n g l e s , each with a simple polygonal c r o s s - s e c t i o n . Each beam i s t r a c e d through the model (along with r e f l e c t i o n , d i f f r a c t i o n , a b s o r p t i o n , and r e l a t e d e f f e c t s ) to determine whether or not i t w i l l impinge upon the r e c e i v e r p o s i t i o n w i t h i n a given t r a c e l e n g t h . c) The i n f o r m a t i o n c o l l e c t e d d u r i n g the beam t r a c i n g i s used to program a bank of d i g i t a l f i l t e r s . These d i g i t a l f i l t e r s operate on a d i g i t i z e d anechoic r e c o r d i n g , p r o c e s s i n g i t i n the same way the room or concert h a l l being modeled would massage the o r i g i n a l sound. When the processed r e c o r d i n g i s reconverted to an analog s i g n a l and r e p l a y e d under c o n t r o l l e d c o n d i t i o n s , one hopes to p r o v i d e a r e a l i s t i c a u d i b l e s i m u l a t i o n of what the sound would be l i k e i n the room or h a l l being modeled. (a) CAAD Geometric Model of Room source recen ver (b) 'Sound Beam' T r a c i n g A/D • • (c) A u d i b l e S i m u l a t i o n F i g u r e 1.1 A c o u s t i c s S i m u l a t i o n 7 1.3 R e l a t i n g A c o u s t i c s and Graphics The u n d e r l y i n g g e o m e t r i c a l problem, t e s t i n g i n t e r s e c t i o n s r e l a t e d to the beam t r a c i n g , can be formulated as a v a r i a n t of the hidden s u r f a c e e l i m i n a t i o n problem [DadKirkWal,82] with s e v e r a l a d d i t i o n a l c o n s t r a i n t s . A s o l u t i o n to the problem must answer the q u e s t i o n : from a given source p o s i t i o n , which s u r f a c e s i n the room being modeled can be 'seen' w i t h i n the l i m i t a t i o n s of t h i s beam? The most common i n s t a n t i a t i o n of the t r a d i t i o n a l hidden s u r f a c e problem can be c o n s i d e r e d s t a t i c with one viewer p o s i t i o n and one viewing window. Within the a c o u s t i c a l s i m u l a t i o n , the problem can be c o n s i d e r e d dynamic i n that i t has many viewing p o s i t i o n s and many viewing windows. Another kind of dynamic f o r m u l a t i o n of the hidden l i n e / s u r f a c e problem a r i s e s i n c o n s t r u c t i n g an a i r p l a n e f l i g h t s i m u l a t o r . In t h i s s e t t i n g , a s u c c e s s i o n of views may be computed with only small changes i n viewpoint. Thus, most s o l u t i o n s to t h i s problem w i l l take advantage of t h i s 'frame coherence' to help in the computation. On the other hand, views w i t h i n the s i m u l a t i o n c o u l d s u c c e s s i v e l y come from widely d i f f e r i n g viewpoints with widely d i f f e r i n g d i r e c t i o n s . Within the s i m u l a t i o n , a s i n g l e beam s t r i k i n g a c r o s s s e v e r a l s u r f a c e s i s ' s p l i t ' i n t o a number of r e f l e c t i o n s each of which must a l s o be t r a c e d as a 'new* source p o s i t i o n . With 8 s e v e r a l hundred primary ( p r e - r e f l e c t i o n ) source beams and p o t e n t i a l l y e x p o n e n t i a l growth i n the number of secondary ( r e f l e c t e d ) beams, our e f f o r t s have conc e n t r a t e d on segmenting and p r e p r o c e s s i n g the geometric model to f a c i l i t a t e the beam/surface i n t e r s e c t i o n t e s t i n g . We propose a h i e r a r c h i c a l o r g a n i z a t i o n of the room's f e a t u r e s so that given a p a r t i c u l a r sound source (viewing) p o s i t i o n , i t i s p o s s i b l e to e l i m i n a t e q u i c k l y the i r r e l e v a n t p o r t i o n s of the room (environment) r e p r e s e n t a t i o n . In s e a r c h i n g f o r the i n t e r s e c t i o n of the beam with the room, our u n d e r l y i n g s t r a t e g y has been to attempt to e l i m i n a t e n o n - i n t e r s e c t i o n s as q u i c k l y as p o s s i b l e . More e f f o r t can then be expended examining areas w i t h i n which i n t e r s e c t i o n s have occ u r r e d . Our work explores the notion of a h i e r a r c h i c a l r e p r e s e n t a t i o n i n s e v e r a l ways. We examine the d i f f i c u l t y of a u t o m a t i c a l l y segmenting the space in v a r i o u s domains. We compare v a r i o u s s t r u c t u r e s as candidates f o r h i e r a r c h y elements. We apply recent r e s u l t s i n the f i e l d of computational geometry to the c o n s t r u c t i o n , search and c l i p p i n g p r o c e s s e s . We propose and examine an environment r e p r e s e n t a t i o n which we w i l l argue i s u s e f u l not only f o r the a c o u s t i c s beam t r a c i n g but f o r other a p p l i c a t i o n s as w e l l . We have attempted to d e s c r i b e our r e s u l t s i n as g e n e r a l a 9 way as p o s s i b l e . A beam here can be c o n s i d e r e d a sound beam i n our a p p l i c a t i o n or a viewing window i n a t y p i c a l g r a p h i c s a p p l i c a t i o n . S i m i l a r l y , a room can r e f e r to a concert h a l l or any environment i n which the hidden s u r f a c e problem i s to be so l v e d . 1 .4 T h e s i s O u t l i n e Chapter 2 defines- a geometric model and d i s c u s s e s our environment r e p r e s e n t a t i o n . A beam d e f i n i t i o n i s presented which i s general enough to i n c l u d e our sound beam a p p l i c a t i o n and a t y p i c a l g r a p h i c s viewing window. The o v e r a l l hidden l i n e / s u r f a c e problem i s d e f i n e d in terms of our environment and beam d e f i n i t i o n s . Within the problem d e f i n i t i o n , we i d e n t i f y and d e f i n e the i n t e r s e c t i o n , s o r t i n g and c l i p p i n g subproblems. We d e f i n e candidates f o r h i e r a r c h y elements: the convex h u l l , the r e c t i l i n e a r bounding box and the minimum-volume bounding box. Chapter 3 presents p r e v i o u s work on h i e r a r c h i c a l s t r u c t u r e s and d i s c u s s e s how our p r o p o s a l s i n c o r p o r a t e and extend that work. I t then i d e n t i f i e s the steps r e q u i r e d to preprocess a given environment i n t o a h i e r a r c h i c a l s t r u c t u r e . The steps i n c l u d e t r a n s f o r m a t i o n s to the b a s i c r e p r e s e n t a t i o n , segmentation, and a c t u a l c o n s t r u c t i o n of the approximation elements. I t a l s o d i s c u s s e s d e s i r a b l e p r o p e r t i e s of a h i e r a r c h i c a l decomposition and suggests h e u r i s t i c s f o r 10 o b t a i n i n g such a decomposition from d i f f e r e n t forms of input. Chapter 4 proposes a l g o r i t h m s which use the h i e r a r c h i e s to e f f i c i e n t l y s o l v e the i n t e r s e c t i o n , s o r t i n g and c l i p p i n g subproblems i d e n t i f i e d i n Chapter 2. The i n t e r s e c t i o n search i s performed by a r e c u r s i v e ' c l o s e s t - f i r s t ' search i n t o the h i e r a r c h y . The s o r t i n g i s performed by m a i n t a i n i n g an i n t e r v a l o r d e r i n g i n a concatenable queue. The c l i p p i n g i s performed using a polygon-comparison graph r e p r e s e n t a t i o n d e s c r i b e d by Weiler [Weil,80]. The m o t i v a t i o n s and b e n e f i t s of these a l g o r i t h m s are d i s c u s s e d . Chapter 5 examines the c o m p l e x i t i e s of using d i f f e r e n t geometric s t r u c t u r e s as h i e r a r c h y elements. In the s p i r i t of .computational geometry, these approximations are compared as to t h e i r c o n s t r u c t i o n , storage, and i n t e r s e c t i o n c o s t s . A h y b r i d h i e r a r c h y which can use v a r i o u s p o l y h e d r a l s t r u c t u r e s as elements i s d e s c r i b e d . Chapter 6 summarizes our r e s u l t s and d i s c u s s e s other r e l a t e d a p p l i c a t i o n s . Suggestions f o r f u r t h e r work in v a r i o u s d i s c i p l i n e s are presented. 11 CHAPTER 2: Def i n i t i o n s T h i s chapter presents d e f i n i t i o n s of terms and s t r u c t u r e s used i n t h i s t h e s i s . The standard r e p r e s e n t a t i o n used in our r e s e a r c h i s f i r s t d e f i n e d . We then d e f i n e the hidden s u r f a c e problem and i d e n t i f y i t s subproblems. F i n a l l y , the d i f f e r e n t s t r u c t u r e s proposed as c a n d i d a t e s f o r h i e r a r c h y elements are d e f i n e d . T h i s t h e s i s w i l l use the standard 'big 0' order n o t a t i o n f o r d e s c r i b i n g computational complexity. A good i n t r o d u c t i o n to computational complexity in a computer g r a p h i c s s e t t i n g i s p r o v i d e d by T i l o v e [ T i l , 8 l ] . 2.1 Envi ronment Representat ions A geometric model [NewSpr,79] [Req,80] [ReqVoel,82] i s an a b s t r a c t r e p r e s e n t a t i o n of a p h y s i c a l system in which the p h y s i c a l s t r u c t u r e of the system i s d e s c r i b e d by c o o r d i n a t e s embedded in some metric space. We w i l l be c o n s i d e r i n g a geometric model of a s t a t i c envi ronment such as a c o l l e c t i o n of o b j e c t s , a b u i l d i n g , or an outdoor scene. Within a geometric model, i n f o r m a t i o n can be s p e c i f i e d i n a number of r e p r e s e n t a t i o n schemes. Requicha [Req,80] pr o v i d e s an e x c e l l e n t survey of modeling r e p r e s e n t a t i o n schemes and r e l a t e d i s s u e s . 1 2 Our environment d e s c r i p t i o n i s a boundary r e p r e s e n t a t i o n which uses p l a n a r faces to d e s c r i b e the boundaries of the scene being modeled. We assume as input v e r t i c e s , edges and p l a n a r f a c e s , along with face adjacency i n f o r m a t i o n . Edges are s p e c i f i e d as p a i r s of v e r t i c e s . An edge r i n g can be r e f e r r e d to as a p o l y g o n a l contour. A polygon which i s not s e l f - i n t e r s e c t i n g i s simple. A face i s a p o l y g o n which may be1 non-convex and may have- h o l e s . A face i s d e s c r i b e d by a number of simple edge r i n g s : a counter- c l o c k w i s e edge r i n g s p e c i f y i n g the outer contour and a l i s t of c l o c k w i s e edge r i n g s s p e c i f y i n g the c o n t a i n e d h o l e s . The edge d i r e c t i o n s are s p e c i f i e d f o r convenience in l a t e r p r o c e s s i n g ; a c c o r d i n g to these d e f i n i t i o n s the ' i n t e r i o r ' of a face i s always on the l e f t . The face plane equation can be d e r i v e d from any one of these edge r i n g s . If we ignore the m e t r i c space w i t h i n which our environment d e s c r i p t i o n i s embedded, then the v e r t i c e s and edges d e f i n e a symbolic graph r e l a t i o n . T h i s i s what many re s e a r c h e r s in geometric modeling r e f e r to as topology [ E a L i S t , 7 5 ] . We can e x p l o i t t h i s graph r e l a t i o n by a p p l y i n g some graph t h e o r e t i c t o o l s to i t . The face adjacency graph i s the dual graph with nodes in the adjacency graph r e l a t i n g to faces i n the o r i g i n a l graph, and edges corre s p o n d i n g to face a d j a c e n c i e s . An a r t i c u l a t i o n p o i n t in a graph i s one which when removed causes the graph to become d i s c o n n e c t e d . 1 3 Many i n s t a n t i a t i o n s of our r e p r e s e n t a t i o n w i l l have a n a t u r a l ' r e a l - w o r l d ' i n t e r p r e t a t i o n i n which faces w i l l correspond to f a c e t s of w a l l s or s o l i d o b j e c t s . These o b j e c t s can be thought of as d e f i n i n g a s o l i d c o n t a i n e d w i t h i n t h e i r boundary d e s c r i p t i o n . In a s o l i d - m o d e l i n g scheme, t h i s can be r e f e r r e d to as obj e c t coherence. T h i s form of o b j e c t coherence i s not r e q u i r e d i n a boundary ' d e s c r i p t i o n of elements i n a given environment. However, face o r i e n t a t i o n can be i n c o r p o r a t e d to d e s c r i b e the 'ou t s i d e ' of a w a l l or o b j e c t . T h i s may be used to e l i m i n a t e back faces (faces o r i e n t e d away from the viewer) from c o n s i d e r a t i o n . 2 . 2 Beam D e f i n i t i o n Within a geometric model of a scene as d e s c r i b e d above, a viewing window i s d e f i n e d as a viewing (source) p o s i t i o n and an ordered l i s t of rays l e a v i n g t h i s viewing p o s i t i o n d e l i m i t i n g a beam. T h i s beam w i l l have a po l y g o n a l c r o s s - s e c t i o n , which may be non-convex and may have h o l e s . The r e p r e s e n t a t i o n of a beam i s s i m i l a r to that of a face; the beam i s represented by a number of rays, corresponding to v e r t i c e s , which are ordered in c i r c u l a r l i s t s , corresponding to simple edge r i n g s . A beam i s s p e c i f i e d by a c i r c u l a r c o u n t e r - c l o c k w i s e l i s t of rays forming the o u t s i d e contour of the beam and a l i s t of c i r c u l a r c l o c k w i s e ray l i s t s d e f i n i n g holes w i t h i n the beam contour. As i n the face d e s c r i p t i o n , the 1 4 d i r e c t i o n s are s p e c i f i e d f o r convenience i n determining the ' i n t e r i o r ' of the beam. A standard r e c t a n g u l a r viewing screen would be modeled here as four ordered rays l e a v i n g the viewer p o s i t i o n and d e f i n i n g an extended viewing pyramid. The i n t e r i o r of the beam d e f i n e s an unbounded s o l i d so that q u e s t i o n s about p o r t i o n s of the environment i n t e r s e c t i n g the beam are w e l l - d e f i n e d . The i n t e r i o r angles between any two rays i n the s p e c i f i c a t i o n o f a beam w i l l always' be- less' than IT. Thus, i t i s always p o s s i b l e to f i n d a plane such that the i n t e r s e c t i o n of the beam and plane d e f i n e s a bounded beam  polygon. In most gra p h i c s a p p l i c a t i o n s , to a v o i d d i s t o r t i o n problems i n the p r o j e c t i o n , the i n t e r i o r angles are much l e s s than 7T. The beam a x i s i s d e f i n e d as a s e m i - i n f i n i t e ray extending from the viewing (source) p o s i t i o n through an i n t e r n a l p o i n t of a beam polygon. For example, the centre of g r a v i t y of a beam polygon might be used to d e f i n e a beam a x i s . The beam a x i s i s used to d e f i n e a s p a t i a l o r d e r i n g on h i e r a r c h y elements as d e s c r i b e d i n S e c t i o n 4 . 1 . Our d e f i n i t i o n of beam i s extremely g e n e r a l . The beam cou l d be regarded as d e f i n i n g an e n t i r e g r a p h i c s viewing window which a f t e r hidden l i n e removal c o u l d be used as input to a ve c t o r d i s p l a y . At the other extreme, the beam window c o u l d be regarded as a s i n g l e p i x e l ( p i c t u r e element) f o r which a s i n g l e 15 shading value was to be d e r i v e d . Thus the e x t r a c t i o n of v a l u e s fo r a l l p i x e l s c o u l d be used to generate a r a s t e r scan image. One of the reasons f o r i n c l u d i n g non-convex beams and beams with holes i s r e l a t e d to our a c o u s t i c s a p p l i c a t i o n . By d e f i n i n g beams with t h i s g e n e r a l i t y , we can s t a r t with a small number of l a r g e beams and l e t the environment do a n a t u r a l decomposition. The a l t e r n a t i v e to a l l o w i n g non-convex beams i s to do a convex decomposition when- n o n - c o n v e x i t i e s a r i s e . The a l t e r n a t i v e to a l l o w i n g holes i s to ' s p l i t ' the beams around holes i f they a r i s e . E i t h e r of these a l t e r n a t i v e s (when compounded with the beam s p l i t s r e s u l t i n g from the environment) c o u l d cause an unnecessary p r o l i f e r a t i o n of beams. However, a l l o w i n g beams to be non-convex with holes w i l l r e q u i r e a more complex approach to the c l i p p i n g problem d e f i n e d i n the next sect i o n . Another reason f o r a l l o w i n g beams of t h i s g e n e r a l i t y i s to f a c i l i t a t e d e f e r r a l of p r o c e s s i n g h i e r a r c h y elements. T h i s w i l l be f u r t h e r e x p l a i n e d in the c l i p p i n g s e c t i o n of Chapter 4. 2.3 Problem D e f i n i t i o n In terms of the above d e f i n i t i o n s , our problem d e f i n i t i o n i s : f o r a p a r t i c u l a r geometric model, i d e n t i f y q u i c k l y a l l faces or p o r t i o n s of faces v i s i b l e w i t h i n a l a r g e v a r i e t y of beams with s p e c i f i e d source p o s i t i o n s and d i r e c t i o n s . 1 6 In our f o r m u l a t i o n of the' hidden l i n e / s u r f a c e problem, three p r i n c i p a l subproblems can be i d e n t i f i e d . The f i r s t i s to i d e n t i f y which elements l i e w i t h i n the range of v i s i o n by i n t e r s e c t i n g the s p e c i f i e d beam with the elements i n the geometric model. The brute f o r c e s o l u t i o n to t h i s subproblem would t e s t a l l faces f o r containment w i t h i n the viewing window. A more i n t e l l i g e n t approach, which we explore i n some d e t a i l , i s to form rough c l u s t e r s of faces and to t e s t the window a g a i n s t each c l u s t e r 1 . The second subproblem i s to s o r t the elements contained w i t h i n the window to determine a depth o r d e r i n g . T h i s i s done so that once the i n t e r s e c t i o n work has determined the r e l e v a n t i n t e r s e c t i o n s w i t h i n the scene, i t i s p o s s i b l e to determine which are the ' c l o s e s t ' or ' v i s i b l e ' elements w i t h i n those i n t e r s e c t i o n s . If two p o l y h e d r a l elements do not i n t e r s e c t then they are c a l l e d s e p a r a b l e . The t h i r d subproblem i s to i d e n t i f y which p o r t i o n s of co n t a i n e d elements are to appear i n the f i n a l r e n d e r i n g . T h i s can be thought of as c l i p p i n g v i s i b l e elements a g a i n s t other v i s i b l e elements and the window boundary to produce the f i n a l image. A c l i p polygon i s a polygon to be c l i p p e d out of a given beam. A passby beam i s a p o r t i o n of a given beam which does not o v e r l a p with a given c l i p polygon (see F i g u r e 2.1). Other f o r m u l a t i o n s and approaches to t h i s problem may not 17 visible within beam F i g u r e 2.1 C l i p p i n g a Polygon 18 separate these p a r t i c u l a r subproblems. For example, an e a r l i e r approach to s o l v i n g t h i s problem i n the a c o u s t i c s s e t t i n g " combined the i n t e r s e c t i o n and s o r t i n g subproblems by 'stepping' along a beam a x i s and t e s t i n g rough c l u s t e r s f o r i n t e r s e c t i o n at each 'step'. 2.4 Approximation S t r u c t u r e D e f i n i t i o n s Our approaches" make use of geometric s t r u c t u r e s used as s p a t i a l approximations of p o r t i o n s of the given environment. We now d e f i n e some of these approximation s t r u c t u r e s . The two-dimensional convex h u l l of a planar set of p o i n t s P i s the unique minimum-area convex polygon which c o n t a i n s P. The most n a t u r a l r e p r e s e n t a t i o n i s an ordered c i r c u l a r l i s t of v e r t i c e s d e s c r i b i n g the outer contour of the h u l l . A two-dimensional bounding r e c t a n g l e i s a r e c t a n g l e which c o n t a i n s P. T h i s can most e a s i l y be s p e c i f i e d by i t s four corner v e r t i c e s . The minimum-area r e c t i 1 i n e a r bounding  r e c t a n g l e i s the. minimum-area r e c t a n g l e c o n t a i n i n g P and having s i d e s p a r a l l e l to the c o o r d i n a t e axes. A minimum-area bounding  r e c t a n g l e i s a minimum area r e c t a n g l e of a r b i t r a r y o r i e n t a t i o n which c o n t a i n s P (see F i g u r e 2.2). The three-dimensional convex h u l l of a set of p o i n t s i n three-space i s the unique minimum-volume convex polyhedron F i g u r e 2 . 2 Minimum Bounding Polygons 20 which c o n t a i n s that set of p o i n t s . There are s e v e r a l o p t i o n s for r e p r e s e n t i n g the 3D h u l l . For our purposes, the s i m p l e s t i s a graph whose v e r t i c e s are the extreme p o i n t s of the convex set and whose edges denote adjacency on the convex h u l l . Each vertex w i l l have a s s o c i a t e d with i t an ordered r i n g of i t s adjacent v e r t i c e s . Another u s e f u l r e p r e s e n t a t i o n of the 3D convex h u l l i s the doubly-connected edge 1 i s t (DCEL) of M u l l e r and Preperata [MulPrep,78]. In the DCEL, the 3D convex h u l l i s represented by a l i s t of v e r t i c e s , a l i s t of edges, and a l i s t of f a c e s . Each vertex has an ordered r i n g of i n c i d e n t edges a s s o c i a t e d with i t . Each face has an ordered r i n g of i n c i d e n t edges a s s o c i a t e d with i t . Each edge has p o i n t e r s to i t s i n c i d e n t v e r t i c e s and f a c e s . The DCEL can be e a s i l y d e r i v e d from the simpler r e p r e s e n t a t i o n noted e a r l i e r and, although i t r e q u i r e s more storage, i t has the advantage that i n f o r m a t i o n about the faces' i s r e a d i l y a v a i l a b l e . In our cont e x t , convex h u l l s are approximations of the point sets d e f i n i n g faces (2D) or o b j e c t s (3D). In g e n e r a l , convex o b j e c t s have n i c e computational p r o p e r t i e s . In recent years, a wealth of e f f i c i e n t a l g o r i t h m s f o r c o n s t r u c t i n g and using convex h u l l s has been de v i s e d by re s e a r c h e r s i n computational geometry [MulPrep,78] [PrepHong,77] [Sham,78] [DobKirk,82]. For example, there i s an a l g o r i t h m due to Preparata and Hong to c o n s t r u c t the 3D convex h u l l of n p o i n t s 21 i n 0(n l o g n) time [PrepHong,77]. R e l a t i v e to the convex h u l l , a bounding box i s a much cruder approximation with a much simpler r e p r e s e n t a t i o n . Given a set T of p o i n t s in three-space, a bounding box i s a r e c t a n g u l a r p a r a l l e l e p i p e d which c o n t a i n s T. The r e c t i 1 i n e a r bounding box i s a bounding box with s i d e s p a r a l l e l to the xy, xz, and yz p l a n e s . I t i s d e f i n e d by a' 'maximum' and a 'minimum' vertex where the maximum (resp. minimum) i s d e f i n e d by the maximum (resp. minimum) x, y, and z values i n T. The two v e r t i c e s d e f i n e the maximum and minimum corn e r s of the bounding box. T h i s s t r u c t u r e was proposed by Eastman and L i v i d i n i [EaLi,75] f o r s p a t i a l search i n an a r c h i t e c t u r a l database. Reddy and Rubin [RedRub,78] use an a r b i t r a r i l y - o r i e n t e d  bounding box as a compact s p a t i a l r e p r e s e n t a t i o n . T h i s i s a s t r u c t u r e which r e t a i n s the s i m p l i c i t y of the r e c t i l i n e a r bounding box but p o t e n t i a l l y improves the s p a t i a l approximation by f r e e i n g the bounding box from any a x i s dependence. The minimum-volume bounding box i s the next l o g i c a l e x tension of the a r b i t r a r i l y - o r i e n t e d bounding box. Given a set T of p o i n t s i n three-space, a minimum-volume bounding box i s a minimum-volume a r b i t r a r i l y - o r i e n t e d p a r a l l e l e p i p e d which c o n t a i n s T. I t can be s p e c i f i e d as a 4x4 t r a n s f o r m a t i o n matrix 2 2 ( i n t o l o c a l 'box' c o o r d i n a t e s ) and x, y, and z o f f s e t s to d e f i n e the l i m i t of the box. Note that the minimum-volume bounding box of a given set of p o i n t s i s not n e c e s s a r i l y unique. Above and beyond the f a c t that s e v e r a l t r a n s f o r m a t i o n / o f f s e t combinations can d e s c r i b e the same box, d i f f e r e n t boxes may r e s u l t i n the same (minimum) volume. 23 CHAPTER 3: H i e r a r c h i c a l P r o c e s s i n g As part of the hidden l i n e / s u r f a c e problem d e f i n i t i o n , three subproblems ( i n t e r s e c t i o n , s o r t i n g and c l i p p i n g ) were i d e n t i f i e d . We propose using a new geometric h i e r a r c h i c a l o r g a n i z a t i o n of elements w i t h i n a given environment to provide good a l g o r i t h m s f o r s o l v i n g each of these subproblems. T h i s chapter w i l l d e s c r i b e p r e v i o u s work done- on- geometric h i e r a r c h i e s . I t w i l l then d e s c r i b e the m o t i v a t i o n and s t r u c t u r e of our h i e r a r c h y . F i n a l l y , the p r e p r o c e s s i n g necessary to convert b a s i c r e p r e s e n t a t i o n s to h i e r a r c h i c a l o r g a n i z a t i o n s w i l l be d i s c u s s e d . 3.1 Previous Work The use of geometric h i e r a r c h i e s in s t r u c t u r i n g domain in f o r m a t i o n f o r hidden s u r f a c e a l g o r i t h m s was f i r s t suggested by C l a r k [ C l , 7 6 ] , He proposed using h i e r a r c h i e s to l i m i t the amount of i n f o r m a t i o n under c o n s i d e r a t i o n at any p a r t i c u l a r time (borrowing the notion of a 'working s e t ' from o p e r a t i n g system theory) and a l s o d i s c u s s e d g e n e r a l i z i n g the idea of c l i p p i n g to i n c l u d e r e s o l u t i o n c l i p p i n g , motion c l i p p i n g and other o p t i c a l e f f e c t s . He suggested that search a l g o r i t h m s take the form of a r e c u r s i v e descent through the h i e r a r c h y . Eastman and L i v i d i n i [EaLi,75] used r e c t i l i n e a r bounding 2 4 boxes to do crude (minimax) s p a t i a l search t e s t i n g in an a r c h i t e c t u r a l database. In t h e i r e a r l i e s t work, they d i d not d e s c r i b e a h i e r a r c h i c a l o r g a n i z a t i o n but used one subsequently in the BDS ( B u i l d i n g D e s c r i p t i o n System) [ E a L i S t , 7 5 ] . BDS was a r e s e a r c h a r c h i t e c t u r a l design system which concentrated on r e p r e s e n t a t i o n a l and database i s s u e s . The h i e r a r c h i c a l o r g a n i z a t i o n was c a r r i e d over i n t o the design of GLIDE ( G r a p h i c a l Language fo r I n t e r a c t i v e DEsign) [.EaHen,77]. T h i s i s a Computer-Aided A r c h i t e c t u r a l Design system which i s , i n p a r t , the b a s i s of the h i e r a r c h i c a l r e p r e s e n t a t i o n o r i g i n a l l y used i n the a c o u s t i c s modeling system [Wal,79]. Independently, Reddy and Rubin [RedRub,78] developed the idea of a h i e r a r c h i c a l r e p r e s e n t a t i o n f o r 3-dimensional o b j e c t s f o r use i n a r t i f i c i a l i n t e l l i g e n c e a p p l i c a t i o n s . T h i s was l a t e r r e f i n e d and a p p l i e d to computer g r a p h i c s i n a paper by Rubin and Whitted [RubWhit,80]. They used a h i e r a r c h y of a r b i t r a r i l y - o r i e n t e d bounding boxes to segment t h e i r environments and used image space s c a n - l i n e a l g o r i t h m s to render complex shaded scenes. T h e i r h i e r a r c h y elements were c r e a t e d manually using a s t r u c t u r e e d i t o r with no attempt to op t i m i z e s y s t e m a t i c a l l y the volume or o r i e n t a t i o n of t h e i r bounding boxes. 25 3.2 Our Approach In our domain, a given geometric model w i l l be i n t e r r o g a t e d many times. Although many d i f f e r e n t beams may be under c o n s i d e r a t i o n , the search i n g and i n t e r s e c t i o n problems w i l l be e s s e n t i a l l y the same. To reduce the co s t of each search and thereby reduce the o v e r a l l time, our d e s i r e i s to trade search time f o r p r e p r o c e s s i n g time. Our approach i s to use a h i e r a r c h i c a l o r g a n i z a t i o n of approximating- s t r u c t u r e as an a l t e r n a t e r e p r e s e n t a t i o n of the scene. Although t h i s h i e r a r c h i c a l o r g a n i z a t i o n may take d i f f e r e n t forms, f o r b r e v i t y in the f o l l o w i n g d i s c u s s i o n , i t w i l l be r e f e r r e d to as the h i erarchy. The h i e r a r c h y i s composed of p o l y h e d r a l elements, each of which c o n t a i n s a p o r t i o n of the environment.'. Each p o l y h e d r a l element i s a convex approximation of the p o r t i o n of the environment which i t c o n t a i n s . The h i e r a r c h y can be viewed as a d e s c r i p t i o n of the environment at v a r i o u s l e v e l s of d e t a i l . Some que s t i o n s about the o r i g i n a l scene can be answered q u i c k l y by using only a very coarse d e s c r i p t i o n . In a t y p i c a l c o n f i g u r a t i o n , the root of t h i s h i e r a r c h y i s the l a r g e s t element and c o n t a i n s the e n t i r e scene; the l e v e l s below the root are formed by s p l i t t i n g the scene i n t o segments. The segments are f u r t h e r s u b d i v i d e d u n t i l the lea v e s are formed. A l e a f may take one of s e v e r a l forms. A l e a f may be a 2 6 'degenerate' three- d i m e n s i o n a l ( i . e . two-dimensional) convex approximation of one of the planar face elements making up the scene. It i s a l s o p o s s i b l e that a l e a f may be a p r o c e d u r a l d e f i n i t i o n of a p o r t i o n of the environment as d e s c r i b e d i n s e c t i o n 3.4.1. Our work extends that of Rubin and Whitted in s e v e r a l ways. The h i e r a r c h y we d e s c r i b e can use v a r i o u s convex approximation elements and' can a l s o i n c o r p o r a t e p r o c e d u r a l d e f i n i t i o n of p o r t i o n s of the environment. Rubin and Whitted use approximation h i e r a r c h i e s i n a hidden s u r f a c e r a s t e r scan s e t t i n g o n l y . T h i s r a s t e r scan s e t t i n g uses the h i e r a r c h y to d e r i v e p i x e l v a l u e s only and t h e r e f o r e does not . deal with c l i p p i n g p o l y g o n a l elements. To demonstrate the use of a h i e r a r c h y in a hidden l i n e s e t t i n g , we present a way of c l i p p i n g that e x p l o i t s the h i e r a r c h i c a l r e p r e s e n t a t i o n . 3.3 P r o c e s s i n g O u t l i n e The p r o c e s s i n g i n v o l v e d i n s o l v i n g the hidden-surface problem must i n c l u d e the work r e q u i r e d to massage the input data i n t o an a c c e p t a b l e form. Thus a g e n e r a l o u t l i n e might be: 1) take as input some u n s t r u c t u r e d scene r e p r e s e n t a t i o n . 2 ) e x t r a c t from t h i s i n i t i a l r e p r e s e n t a t i o n the necessary plane equations and face adjacency i n f o r m a t i o n . 3) p a r t i t i o n t h i s r e p r e s e n t a t i o n i n t o a segmented h i e r a r c h y . 27 4) r e p l a c e each segment i n the h i e r a r c h y with a c o n t a i n i n g p o l y h e d r a l element. 5 ) input a viewing (source) p o s i t i o n and d e l i m i t i n g rays d e f i n i n g a beam. 6 ) proceed with i n t e r s e c t i o n , s o r t i n g , and c l i p p i n g a l g o r i t h m s . Items 1-4 r e f e r to p r e p r o c e s s i n g the s t r u c t u r e which i s performed once; 5-6 r e f e r to the h i e r a r c h i c a l search which i s to be performed many times. Items 1-4 a r e d e a l t with in the next s e c t i o n ; items 5-6 are examined t h e r e a f t e r . 3.4 P r e p r o c e s s i n g What form might the input data take? On one hand, Rubin and Whitted assume a "point or s u r f a c e r e p r e s e n t a t i o n ... [not] aggregated i n t o any h i e r a r c h i c a l form" [RubWhit,80,p.113]. At the other end of the spectrum, Walsh d e s c r i b e s : "a h i e r a r c h y of w a l l s (and/or w a l l elements), planar f a c e s , [edges,] and v e r t i c e s " [Wal,79,p.236]. Walsh's r e p r e s e n t a t i o n was intended to be the output of a CAAD system and thus would a l r e a d y have much of the s t r u c t u r e we need a s s o c i a t e d with i t . Obviously with t h i s range of p o t e n t i a l u sers, l i t t l e i n the way of p r e d e f i n e d s t r u c t u r e can be assumed. D i f f e r e n t users may be able to step i n t o the stream i n v a r i o u s p l a c e s a c c o r d i n g t o the i n i t i a l s t r u c t u r e of the data but most users w i l l r e q u i r e some 'massaging' of data i n t o a p p r o p r i a t e forms. 2 8 r a w a plane/face b segment c hierarchical representation > adjacency info > groupings > structure F i g u r e 3 .1 Required P r e p r o c e s s i n g A l l of t h i s c o u l d be done manually using s t r u c t u r e e d i t o r s .as Rubin and Whitted d i d . However, the p o t e n t i a l tedium of such an e x e r c i s e combined with the d e s i r e to optimize v a r i o u s a s p e c t s of the f i n a l s t r u c t u r e leads us to i s o l a t e p o r t i o n s of the p r e p r o c e s s i n g and examine ways to deal with each. F i g u r e 3 .1 i d e n t i f i e s the a p p r o p r i a t e p o r t i o n s and l a b e l s the necessary t r a n s f o r m a t i o n s . 3 . 4 . 1 Basic R e p r e s e n t a t i o n With the multitude of r e p r e s e n t a t i o n s i n gen e r a l use [ R e q , 8 0 ] the f i r s t t r a n s f o r m a t i o n (a) would map the input i n t o a geometric v e r t e x boundary s u r f a c e r e p r e s e n t a t i o n . Boundary r e p r e s e n t a t i o n i s the most popular r e p r e s e n t a t i o n scheme i n computer g r a p h i c s although many other schemes e x i s t and are used i n d i f f e r e n t a p p l i c a t i o n s . Some of these schemes are pure j 29 p r i m i t i v e i n s t a n c i n g , s p a t i a l occupancy enumeration, C o n s t r u c t i v e S o l i d Geometry (CSG), and ( t r a n s l a t i o n a l or r o t a t i o n a l ) sweeping. A f u l l d i s c u s s i o n of r e p r e s e n t a t i o n schemes i s beyond the scope of t h i s t h e s i s but as Reguicha suggests " m u l t i p l e r e p r e s e n t a t i o n s [are necessary] fo r a c h i e v i n g a degree of v e r s a t i l i t y and e f f i c i e n c y higher than that of extant modelers" [Req,80,p.461]. E f f i c i e n t exact a l g o r i t h m s do e x i s t f o r performing c o n v e r s i o n s between some representations'. For example, there are exact a l g o r i t h m s f o r c o n v e r t i n g from a sweep to a boundary r e p r e s e n t a t i o n . For other c o n v e r s i o n s , such as CSG to boundary, only approximation al g o r i t h m s are known. The b a s i c t r a n s f o r m a t i o n may i n v o l v e some s o r t of c o n v e r s i o n from 2-dimensional input data to a 3-dimensional r e p r e s e n t a t i o n . For example, the t e s t rooms d e a l t with i n the a c o u s t i c s modeling [WalDad,82] are ' b u i l t ' u s ing two-dimensional d i g i t i z e r input to a sweep program. The sweep or e x t r u s i o n r e p r e s e n t a t i o n i s then converted to the r e q u i r e d boundary r e p r e s e n t a t i o n (see F i g u r e 3.2). For dense g r i d d e d data, the method of Fowler and L i t t l e [FowLit,79] can be used to c o n s t r u c t a T r i a n g u l a t e d I r r e g u l a r Network (TIN). A TIN i s a d i g i t a l t e r r a i n model which i s made up of non-overlapping t r i a n g u l a r f a c e t s of v a r y i n g s i z e . Given a number of p o i n t s d e f i n e d on a g r i d , t h e i r a l g o r i t h m w i l l c o n s t r u c t a u t o m a t i c a l l y a TIN which uni f o r m l y f i t s those p o i n t s F i g u r e 3.2 Converting Sweep to Boundary R e p r e s e n t a t i o n s 31 to any s p e c i f i e d t o l e r a n c e . The a s s o c i a t e d o b j e c t s t r u c t u r e from some r e p r e s e n t a t i o n s ( f o r example, the p r i m i t i v e o b j e c t d e s c r i p t i o n s i n a C o n s t r u c t i v e S o l i d Geometry r e p r e s e n t a t i o n ) can be used to guide the h i e r a r c h i c a l segmentation l a t e r on. In some cases, a non-planar boundary s u r f a c e may have to be approximated by planar f a c e s . Once the boundary r e p r e s e n t a t i o n has been c o n s t r u c t e d , the face adjacency dual graph can be d e r i v e d a u t o m a t i c a l l y . T h i s , f o r many domains, w i l l be u s e f u l i n the segmentation p o r t i o n of the p r e p r o c e s s i n g . Many design systems [BaEaHen,79] have a parameterized o b j e c t d e f i n i t i o n f a c i l i t y . I t i s p o s s i b l e to d e f i n e the d e t a i l s of an o b j e c t only once by t y i n g some f e a t u r e s of the obje c t to parameters to be s p e c i f i e d at i n s t a n t i a t i o n time. Then v a r i o u s i n s t a n t i a t i o n s c o u l d be pl a c e d i n the environment by s p e c i f y i n g p o s i t i o n , o r i e n t a t i o n and s p e c i f i c values f o r the parameters. For example, much storage space (and tedium) c o u l d be saved i n the design of a con c e r t h a l l by s p e c i f y i n g the design of a seat once and then p l a c i n g i n s t a n t i a t i o n s at v a r i o u s p l a c e s i n the h a l l . In t h i s way, not only i s there a saving i n time and space but the parameterized o b j e c t s provide a l e v e l of 32 a b s t r a c t i o n which would a i d the design p r o c e s s . In the above example, i t c o u l d allow the designer to e a s i l y rearrange the s e a t i n g plan without regard to the unimportant d e t a i l s of the geometric consequences of such an a c t i o n . A parameterized o b j e c t d e f i n i t i o n i s one example of a pr o c e d u r a l r e p r e s e n t a t i o n . There i s another form of n o n - e x p l i c i t r e p r e s e n t a t i o n which can a l s o be u s e f u l in our a p p l i c a t i o n of a c o u s t i c s ' s i m u l a t i o n : a p o r t i o n of the environment which i s known to r e f l e c t sound i n a p a r t i c u l a r way can be t r e a t e d as a 'black box' with no e x p l i c i t r e p r e s e n t a t i o n of the d e t a i l s of i t s c o n t e n t s . Whenever a beam enters i t s immediate v i c i n i t y from a given range of angles, ' r e f l e c t e d ' beams with d i r e c t i o n s and p r o p e r t i e s determined by some t a b l e look-up could be generated [Wal,79]. T h i s 'black box' approach c o u l d be used to i n c o r p o r a t e p o r t i o n s of the environment which are rendered p r o c e d u r a l l y a c c o r d i n g to some s t o c h a s t i c process model [FourFuCarp,82]. I f the outer bounds of t h i s 'black box' are s p e c i f i e d then the inner d e t a i l can be s p e c i f i e d by a p o i n t e r to a set of procedures. These procedures when invoked.would compute the r e q u i r e d s u r f a c e d e t a i l s . In the types of p r o c e d u r a l r e p r e s e n t a t i o n schemes d e s c r i b e d above, i t would be unwise, and ( i n some cases) impossible to i n s i s t on p r e p r o c e s s i n g the p r o c e d u r a l l y d e f i n e d 33 p o r t i o n s of the environment i n t o an e x p l i c i t f a c e , edge, vertex form. If the outer bounds of the p r o c e d u r a l l y d e f i n e d p o r t i o n of the environment were s p e c i f i e d , then the i n t e r i o r c o u l d be t r e a t e d as an i n d i v i s i b l e segment w i t h i n the h i e r a r c h y . T h i s ' s p e c i a l ' segment c o u l d be t r e a t e d as being e n t i r e l y s p e c i f i e d by i t s outer boundary f o r purposes of 'wrapping' in an approximation element. The segment would then only be 'unwrapped' or, i n the p r o c e d u r a l s e t t i n g , invoked i f the bounding element were found to l i e w i t h i n some viewing window. 3.4.2 Segmentation Transformation (b) i n v o l v e s the r e c u r s i v e p a r t i t i o n i n g of the faces and edges in the scene i n t o segment groupings. The segmentation/aggregation t r a n s f o r m a t i o n takes the o v e r a l l environment d e s c r i p t i o n as s p e c i f i e d by a boundary r e p r e s e n t a t i o n and produces segmented c l u s t e r s which a c t u a l l y d e f i n e the h i e r a r c h y elements. Each segment grouping w i l l then be wrapped w i t h i n an approximation element as d i s c u s s e d in the next s e c t i o n . O b v i o u s l y , a c i t y s c a p e or concert h a l l d e s c r i p t i o n has a d i f f e r e n t fundamental d e s c r i p t i o n from a d i g i t a l t e r r a i n model of a mountainous scene and i t s segmentation w i l l r e q u i r e d i f f e r e n t h e u r i s t i c s . For example, the c i t y s c a p e d e s c r i p t i o n may be expected to have a r e g u l a r i t y i n the angles between faces which can be e x p l o i t e d . I t i s unreasonable to expect an 3 4 a l g o r i t h m that w i l l p r ovide a good segmentation f o r any given scene r e g a r d l e s s of domain. We can examine t o o l s to use and p r o p e r t i e s to e x p l o i t f o r v a r i o u s domains. The l i s t of h e u r i s t i c s presented i s not meant t o be exhaustive but i s meant to convey the kinds of approaches one might take to a u t o m a t i c a l l y segment an environment d e s c r i p t i o n . There are a number of d e s i r e d p r o p e r t i e s which t h i s segmentation should have to be u s e f u l f o r the hidden s u r f a c e p r o c e s s i n g . U n f o r t u n a t e l y not a l l of these w i l l be p o s s i b l e fo r a l l scenes. In i n t e r s e c t i n g the viewing window with the h i e r a r c h y elements, we wish to e l i m i n a t e as much of the environment as q u i c k l y as p o s s i b l e . T h e r e f o r e , the segmentation should have a f a i r l y low branching f a c t o r from any l e v e l to the c h i l d r e n of that l e v e l . The segmentation should attempt to balance some measure of s i z e (complexity, volume, or aspect r a t i o ) among elements at the same l e v e l of the h i e r a r c h y . The segmentation might be d r i v e n by a r e d u c t i o n in the o v e r a l l volume or the s i z e s of p o i n t s e t s . As w e l l , i t i s d e s i r a b l e to have s e p a r a b i l i t y of i n d i v i d u a l elements so that an o r d e r i n g can be obtained unambiguously and in some cases that a r e l a t i v e o r d e r i n g can be precomputed f o r use i n l a t e r node versus node p r i o r i t y t e s t i n g . T h i s was how the Schumacker p r i o r i t y l i s t a l g o r i t h m used c l u s t e r s [ S u S p r S c h , 7 4 ] . 3 5 For many scenes, segmentation alone w i l l not be s u f f i c i e n t . At v a r i o u s p o i n t s , aggregation w i l l be necessary: sometimes a l a r g e number of d i s j o i n t elements w i l l be input or w i l l r e s u l t from a s i n g l e p a r t i t i o n . Thus, a simple top/down or bottom/up approach w i l l not work; a combination of the two w i l l be necessary. For example, the f i r s t p a r t i t i o n of a room may r e s u l t in many d i s j o i n t elements. To a v o i d a high branching f a c t o r in the h i e r a r c h y , some of these o b j e c t s w i l l have to be' ass o c i a t e d ' together to provide" an intermediate' h i e r a r c h y l e v e l . The connected components of the adjacency (dual) graph can be used as an i n i t i a l p a r t i t i o n of the environment. The r e s u l t i n g segments can then be f u r t h e r decomposed using v a r i o u s h e u r i s t i c s depending on the composition of the scene. The adjacency graph can a l s o be used i n s e v e r a l other ways. An a r t i c u l a t i o n p o i n t i n a graph i s one which when removed causes the graph to become dis c o n n e c t e d . These p o i n t s in the adjacency graph may be used to i d e n t i f y o b j e c t s s i t t i n g on s i n g l e faces (see F i g u r e 3 . 3 ) . In a s i m i l a r way, hig h degree v e r t i c e s i n the dual can be used as ' c l u s t e r p o i n t s ' f o r segmenting. T h i s might correspond to a l a r g e s u r f a c e with many a d j a c e n c i e s , such as a wa l l with many adjacent o b j e c t s . T h i s i s u s e f u l even i f the r e s u l t i n g branching f a c t o r i s s t i l l high because the neighbouring o b j e c t s can be regrouped together by aggregating d i s j o i n t elements. (a) Sample Scene 6 7 (b) Face Adjacency Graph of (a) with A r t i c u l a t i o n Point F i g u r e 3 . 3 Segmentation Using An A r t i c u l a t i o n P o i n t 37 For aggregation another form of adjacency graph can be used to in c l u d e faces (or more complex elements) that are ' c l o s e ' to each other, using s p a t i a l p r o x i m i t y to d e f i n e the graph r e l a t i o n . To segment the scene, Rubin and Whitted suggested that standard s t a t i s t i c a l f e a t u r e d e t e c t i o n techniques be used to l o c a t e a u t o m a t i c a l l y the complex p o r t i o n s of the scene. An example of t h i s i s to search f o r peaks i n a thre e - d i m e n s i o n a l histogram of v e r t i c e s or edges w i t h i n the environment. Another segmentation technique i s to use a plane as a bounding h a l f - s p a c e to p a r t i t i o n a group of elements. T h i s plane c o u l d be formed by a l e a s t - s q u a r e s f i t on the environment v e r t i c e s . The o r i e n t a t i o n of the p a r t i t i o n plane c o u l d be determined by a Hough-transform type v o t i n g scheme [DudaHart,72]. T h i s v o t i n g scheme c o u l d use environment face o r i e n t a t i o n s weighted with s u r f a c e areas. In t h i s scheme, buckets would be set up corresponding to v a r i o u s o r i e n t a t i o n s . The l i s t of faces would be scanned and a face f a l l i n g i n t o an a p p r o p r i a t e o r i e n t a t i o n range would have i t s face area added to the corresponding bucket. Once a l l the faces had been scanned, the maximum would d e f i n e the d e s i r e d o r i e n t a t i o n . When aggregating elements near to the planar face l e v e l , some elements c o u l d be a s s o c i a t e d on the b a s i s of o r i e n t a t i o n as to t h e i r v i s i b i l i t y from a number of d i f f e r e n t v i e w p o i n t s . 38 T h i s c o u l d be thought of as i l l u m i n a t i o n or shadowing from a number of v i e w p o i n t s . 3.4.3 Approximation H i e r a r c h i e s The l a s t p r e p r o c e s s i n g t r a n s f o r m a t i o n (c) from segmented s t r u c t u r e i n t o a c t u a l approximation h i e r a r c h y depends on the approximation being used. Once the segmentation has been completed, each of the segment c l u s t e r s w i l l be r e p l a c e d with an approximation element. These approximation elements can be c o n s i d e r e d as packages surrounding a p o r t i o n of the environment. The p o r t i o n of the environment being packaged can be d e f i n e d e x p l i c i t l y , or p r o c e d u r a l l y . Note that i n the case of a parameterized d e f i n i t i o n of o b j e c t s w i t h i n the environment i t i s sometimes p o s s i b l e to parameterize the approximation element along with the object d e f i n i t i o n . Thus the time and space saving inherent i n the parameterized d e f i n i t i o n can be i n h e r i t e d by the h i e r a r c h y b u i l d i n g . For example, i f a seat w i t h i n a concert h a l l design i s d e f i n e d as a parameterized o b j e c t then the approximation element can be ' b u i l t ' around the parameterized s e a t . An i n s t a n t i a t i o n of the seat would a l s o correspond to an i n s t a n t i a t i o n of the approximation element. The d e s i r a b l e p r o p e r t i e s f o r approximation elements are e f f i c i e n t c o n s t r u c t i o n , compact storage, e f f i c i e n t a l g o r i t h m s 3 9 f o r m a n i p u l a t i o n , a n d a m i n i m u m o f w a s t e d v o l u m e ( w h i c h w i l l b e r e f e r r e d t o a s ' t i g h t n e s s o f f i t ' ) . G i v e n t h e p o r t i o n o f t h e e n v i r o n m e n t t o b e p a c k a g e d , t h e c o n s t r u c t i o n o f t h e g e o m e t r i c a p p r o x i m a t i o n b e i n g u s e d c a n m o s t o f t e n b e d o n e a u t o m a t i c a l l y , a s w i l l b e d i s c u s s e d i n C h a p t e r 5 . 4 0 CHAPTER 4: Algorithms Which Use The H i e r a r c h y T h i s chapter proposes a set of a l g o r i t h m s to s o l v e the hidden l i n e / s u r f a c e problem. These a l g o r i t h m s use the h i e r a r c h y d e s c r i b e d i n Chapter 3 to d e a l with the p r e v i o u s l y i d e n t i f i e d i n t e r s e c t i o n , s o r t i n g and c l i p p i n g subproblems. The a l g o r i t h m s use the preprocessed h i e r a r c h y elements as 'packages' and manipulate them as u n i t s . The b a s i c idea, arid the source of the a l g o r i t h m s ' e f f i c i e n c y , is- that expansion of-these elements i s done i n as ' l a z y ' a way as p o s s i b l e . The g e n e r a l o u t l i n e of the c o n t r o l r o u t i n e s used to search through the h i e r a r c h y and aggregate the a p p r o p r i a t e m a t e r i a l are shown in F i g u r e s 4.1 to 4.3. The a l g o r i t h m s are w r i t t e n i n a pseudo-Pascal with l i b e r t i e s , taken f o r conceptual s i m p l i c i t y . The r o u t i n e s presented assume the e x i s t e n c e of standard l i s t - p r o c e s s i n g r o u t i n e s such as empty, head, t a i l , l i s t , append and o t h e r s . Any r o u t i n e s which are not s e l f - e x p l a n a t o r y w i l l be d e s c r i b e d in the t e x t . The reader i s c a u t i o n e d that although the a l g o r i t h m s are presented i n an e r s a t z programming language, they have not been implemented. Furthermore, the a l g o r i t h m s are p r o p o s a l s f o r ways of using the d e s c r i b e d h i e r a r c h i c a l s t r u c t u r e which we e n v i s i o n as being s u i t a b l e f o r our a p p l i c a t i o n . I t i s q u i t e p o s s i b l e , and e n t i r e l y l i k e l y , that d i f f e r e n t a p p l i c a t i o n s may r e q u i r e d i f f e r e n t approaches to one or more of the i d e n t i f i e d PROGRAM Top_level; VAR ROOT ' { root node of hierarchy, contains entire scene element_list { l i s t of hierarchy nodes under consideration, ordered by closest point to current viewing position interva1_1ist { l i s t of defined intervals for each hierarchy node in element_list, used to order nodes in element l i s t beam_list { l i s t of beams / viewing windows beam {current beam / viewing window under consideration. beam_axis { axis of the current beam. beam_proj_plane { plane orthogonal to current beam axis, used for projecting environment elements. windowed_po1ygori_list { l i s t of clipped visible polygons in the scene passby_list { li s t of beams defining 'background' portion of scene, ie. unimpeded portion of current beam. BEGIN construction(raw_input, ROOT); in i t i a l i ze(beam_list); WHILE NOT empty(beam_list) DO BEGIN beam < head(beam_list); beam_l1st < tai1(beam_list); get_beam_axis(beam. beam_axis, beam_proj_plane) ; element_list < list(ROOT); interyal_list < 1ist(interva1(ROOT)); w i ndowed_po 1 ygon_l ,i st < NIL; passby_list < NIL; examine(beam, e1ement_list, interva1_1ist, w i ndowed_po1ygon_list, passby_list); render(beam, w1ndowed_polygon_list, passby_list); {ref1ections(beam, w1ndowed_polygon_l1st, beam_list)> END END. F i g u r e 4.1 Proposed Algorithms - Top L e v e l PROCEDURE examine(beam, e1ement_list, interval l i s t , w i ndowed_po1ygon_l i st, passby_li st); VAR C 1 i p 1 i s t { l i s t of planar elements to be clipped out of beam / viewing window. c1ip_i n t _ l i s t { ordering on l i s t of planar elements used by clipping routine derived from interva1_1ist sort. >; mid_element { element found by scan_separab1e to be the fi r s t element after the f i r s t separable sequence of elements. Used in SPLIT to partition interval seq.}; beam_passby_list { l i s t of beams resulting from testing current beam against f i r s t (closest) hierarchy node. ): ret_passby_list { returned passby l i s t from recursive call to examine; the passbys on this l i s t have been tested against everything and are truly background. ); passbeam { the beam from passby_list currently under cons i derat i on. } status { contains the result of intersecting the current beam and node } front_list { portion of the environment, which is closest to the viewing position and which can be determined separable by a simple interval test. ) front i nt l i s t { interval l i s t describing interval ordering on elements in front l i s t . } : F i g u r e 4.2 (a) Proposed Algorithms - Examine BEGIN { If all the elements in the element_list are planar then there are no elements to be expanded. The element l i s t is split into separable portions and the closest portion is clipped out of the input beam. The passby portions of the beam are then recursively applied to the remainder of the element l i s t . IF a l l elements in element_list are planar THEN BEGIN scan separable(element_list. interva1_1ist, mid_element): SPLIT(mid_e1ement, element_list, c l i p _ l i s t , e1ement_list); SPLIT(interval(mid_element), interval_list, c1ip_int_list, interva1_1ist): passby_list < NIL; c 1 ipping(beam. c l i p _ l i s t , cl ip_1nt_l 1st. windowed_polygon_list, beam_passby_list); IF NOT empty(element_list) AND NOT empty(beam_passby_list) THEN FOR all passbeams in beam_passby_list DO BEGIN examine(passbeam. e1ement_list, interva1 1 ist, w i ndowed_po1ygon_li st, ret_passby_li st); append(passby_li s t, ret _passby_li s t) END ELSE IF NOT empty(beam_passby_Hst) THEN passby_list < beam_passby_list END F i g u r e 4.2 (b) Proposed Algorithms - Examine (cont.) 44 ELSE { If there exist non-planar elements in the element l i s t then choose the f i r s t non-planar element and DELETE it from the element l i s t . Then expand that node testing each of its subnodes for intersection with the current beam. If the subnode intersects the beam at all and is not a planar back face then reinsert It into the element l i s t . } BEGIN expand_node < first_non_planar(element_1ist); expand_node_interva1 < interva1(expand_node); DE LETE(expand_node, e1ement_li st); DELETE (expand_node_i nterva 1 , i nterva 1_1 i.st) ; FOR al l subnodes of expand_node DO BEGIN intersect(beam, subnode, status); CASE status OF entirely_excluded : (ignore): ent i rely_i nc1uded, par t i a 11y_i nc1uded: IF NOT( planar(subnode) AND backface(subnode) THEN BEGIN INSERT(subnode, element_list); INSERT(interval(subnode), interva1_1ist) END END END; { Use the interval l i s t to SPLIT the element l i s t into 2 separable sublists and recursively examine the closest. If there are passby beams and untested portions of the environment then recursively test them against each other. scan_separable(e1ement_list, interva1_1ist, mid_e1ement); SPLIT(mid_element, element_list, front_list, e1ement_list); SPLIT(interval(mi d_element), interval_list, front_int_list, interva1_1ist); passby_list < NIL; exam 1ne(beam, front_list, front_1nt_list, windowed_polygon_l1st, beam_passby_list); IF NOT empty(element_list) AND NOT empty(beam_passby_list) THEN FOR a l l passbeams in beam_passby_list DO BEGIN exam 1ne(passbeam, element_l1st, interva1_11st, w i ndowed_po1ygon_list, ret_passby_l1st); append(passby_list, ret_passby_list) END ELSE IF NOT empty(beam_passby_1ist) THEN passby_list < beam_passby_list END END; F i g u r e 4.2 (c) Proposed Algorithms - Examine (cone.) PROCEDURE cHpping(beam. c l i p _ l i s t , c1ip_int_l1st, windowed polygon l i s t beam_passby_list ) ; ~ VAR cl1p_poly { Polygon which has been chosen as the polygon to c l i out of the beam window by this call to clipping. Beam is segmented into portion inside clip_poly and portion outside clip_poly. c1i p_po1ygon_ i n_beam { List of windowed polygons resulting from clipping clip_poly against beam. ie. portions of clip_poly visible within beam. } beam_not_in_c1ip_poly { List of passby beams resulting from clipping clip_poly out of beam. ie. portions of beam not s t r i k i ng c1i p_po1y. } status { contains the result of intersecting the beam and the clip_poly. } passbeam { The beam from beam_not_in_c1ip_poly currently under consideration for recursive call to clipping. } BEGIN { Choose clip_poly to be the closest visible polygon and use intersect to make sure that a portion of it lies within the beam area. If it does then call c l i p to slice clip_poly out of beam. Repeat until there is an area clipped out of the beam or there are no more polygons to clip. IF area(beam) > epsilon THEN BEGIN REPEAT c 1 i p_po 1 y < NIL clip_poly_in_beam < NIL beam_not_in_c1ip_po 1 y < NIL IF NOT empty(cl1p_list) THEN BEGIN clip_poly < head(clip_l1st); DELETE(cl1p_po1y, cl1p_list); DELETE(Interval(clip_poly), c1ip_int_list); intersect(beam, cl1p_poly, status): IF status <> entire 1y_exc1uded THEN clip(beam, c l i p _ l i s t , clip_1nt_list, cl1p_poly. clip_poly_in_beam, beam_not_in_clip_poly) END UNTIL (cl1p_poly = NIL) OR NOT empty(cl1p_poly_in_beam); F i g u r e 4 . 3 (a) Proposed Algorithms - C l i p p i n g - C l i p { If we have exhausted the clip l i s t and no clip_poly exists which intersects the input beam then .the whole beam is returned as the passby. If such a clip_poly does exist then c1ip_po1y_in_beam is inserted into the windowed polygon l i s t and the polygons in beam_not_1n_c1ip_po1y define the passby 11st. We can use recursive calIs to clipping to clip the passby beams against the remaining polygons. IF (clip_poly = NIL) THEN beam_passby_list < beam ELSE BEGIN beam_passby_list < NIL; append(windowed_po1ygon_list, c l i p_poly_i n_beam); IF NOT empty(beam_not_in_c1ip_po1y) THEN FOR a l l passbeam in beam_not_in_c1ip_poly DO BEGIN clipping(passbeam, c l i p _ l i s t , c1ip_int_list, w i ndowed_po1ygon_list. tmp_passby_list): append(beam_passby_l1st, tmp_passby_li st) END END END END; PROCEDURE clip(beam, clip_l1st'. c 1 i p_ i n t_ 1 i s t , clip_poly, clip_poly_in_beam, beam_not_in_c1ip_poly); VAR test_ l i s t { List of polygons within beam with intervals which overlap test_poly. P°' v { Polygon under consideration for Insertion Into test_l1st as being Inside beam and having overlapping intervals with clip_poly. intersection_points < The intersection points of a l l the polygons in the test l i s t along with the beam. Used to build the graph represection used for the actual clipping. }: graph { Graph structure of polygon contours and crossings. Defines tesselation of the plane Into regions with l i s t of polygon owners. }; search owner { Constraint passed to traverse_graph defining attributes of regions which are returned. }; igure 4 . 3 (b) Proposed Algorithms - C l i p p i n g - C l i p (cont 4 7 contour l i s t { List of contours returned from traverse graph. The owner l i s t of each contour with satisfy the search owner constraint. contour { Polygon from contour_list currently under consideration. }; BEGIN { Build up the test_list of possibly occluding polygons from the polygons in c l i p _ l i s t with overlapping intervals. } test_!ist < 1 ist(cl'ip_poly) ; FOR all poly in c l i p _ l i s t DO IF overlap) interval(clip_poly) . interva1(po1y)) THEN append(test_list, poly): < Build up Weiler's graph representation for doing generalized clipping. Traverse the graph to determine the areas of clip_poly which lie inside the bean(ie. contours which have clip_poly and beam as owners). Test each of these areas against its other owners for a depth conflict and discard the ones for which clip_poly doesn't win. Then traverse the graph once more for the portion of the beam outside clip_poly. ) intersect_po1ygons(beam. tes t _ l i s t . intersection_points); bui1d_graph_representation(beam. test_list. intersection_points, graph); search_owner_list < owner_1ist(c1ip_po1y AND beam AND any(test_l ist ) ) ; traverse_graph(graph, search_owner_list, contour_list); FOR a l l contour in contour_list DO IF occ1uded(beam, clip_poly, contour) THEN remove_owner(graph, contour, clip_poly); search_owner_list < owner_list(c1ip_po1y AND beam) traverse_graph(graph, search_owner_l1st, clip_po1y_1n_beam); IF NOT empty(clip_poly_in_beam) THEN BEGIN search_owner_list < owner_list(beam AND NOT clip_poly); traverse_graph(graph. search_owner_list. beam_not_i n_c1ip_poly); D ENEND; F i g u r e 4 . 3 (c) Proposed Algorithms - C l i p p i n g - C l i p (cone.) 48 subproblems. a Within the proposed a l g o r i t h m s , the top l e v e l r o u t i n e c o n s t r u c t s the h i e r a r c h y as d i s c u s s e d i n the l a s t s e c t i o n . T h i s r o u t i n e then takes a l i s t of windows i n t o the environment and i d e n t i f i e s the v i s i b l e s u r f a c e s w i t h i n each i n tu r n . In the a c o u s t i c s a p p l i c a t i o n , the l i s t of beams corresponds to a l i s t of sound beams to be t r a c e d . The r e f l e c t i o n s generated are simply new input beams appended to the- l i s t . In a pure gra p h i c s a p p l i c a t i o n , the beam l i s t c o u l d be the suc c e s s i o n of frames f o r a moving viewpoint (such as i n an a v i a t i o n s i m u l a t o r ) or the s u c c e s s i o n of p i x e l windows f o r a r a s t e r d i s p l a y (as i n [RubWhit,80]). In the a c o u s t i c s beam-tracing, a s p e c i a l node d e f i n i n g the r e c e i v e r i s p r o j e c t e d and c l i p p e d with the environment nodes. The d e t e c t i o n of the r e c e i v e r node in a viewing window i s noted as a s t r i k e on the r e c e i v e r p o s i t i o n . The t o t a l path l e n g t h through r e f l e c t i o n s to a h i t on the r e c e i v e r , the r e f l e c t i n g m a t e r i a l s ' e f f e c t s on the frequency response of the path, and the d i r e c t i o n of s t r i k e on the r e c e i v e r p o s i t i o n are other p i e c e s of r e l e v a n t i n f o r m a t i o n . We a l s o i n c o r p o r a t e h e u r i s t i c s fo r the beam t r a c i n g to f u r t h e r e l i m i n a t e extraneous beams whenever p o s s i b l e . For example, c o n s i d e r the p r e d i c t e d d i s t a n c e from a beam's source, through r e f l e c t i o n s , to the r e c e i v e r p o s i t i o n . I f t h i s d i s t a n c e i s g r e a t e r than the predetermined maximum t r a c e l e n g t h then that beam can be 49 d i s c a r d e d . The c o n t r o l r o u t i n e examine i s used to perform a r e c u r s i v e descent search i n t o the h i e r a r c h y to e x t r a c t and aggregate c o l l e c t i o n s of planar faces which are p a r t i a l l y or completely c o n t a i n e d w i t h i n the c u r r e n t beam. I t uses a r o u t i n e c a l l e d i n t e r s e c t to t e s t a p a r t i c u l a r beam f o r i n t e r s e c t i o n with any given h i e r a r c h y node. The s o r t i n g i s performed w i t h i n the examine r o u t i n e by m a i n t a i n i n g a s o r t e d l i s t of h i e r a r c h y element i n t e r v a l s . A f t e r using these i n t e r v a l s to i d e n t i f y two set s of planar faces which are separable, a r o u t i n e c a l l e d c l i p p i n g c l i p s the i d e n t i f i e d faces out of the c u r r e n t beam in the order of t h e i r appearance. 4.1 S o r t i n g The s o r t i n g i n c o r p o r a t e d i n t o t h i s kind of h i e r a r c h i c a l p r o c e s s i n g should be as simple as p o s s i b l e and should attempt to a i d in the ' l a z i n e s s ' of the h i e r a r c h i c a l package p r o c e s s i n g . To t h i s end, the s o r t i n g i s used to i d e n t i f y some of the separable p o r t i o n s of the h i e r a r c h y which have been expanded and d i s c o v e r e d to l i e w i t h i n the c u r r e n t beam. The s o r t i n g uses the beam a x i s and a p r o j e c t i o n plane orthogonal to t h i s a x i s to d e f i n e an o r d e r i n g on the environment elements. To maintain the beam a x i s , and t h e r e f o r e the o r d e r i n g , d u r i n g segmentation of the beam, the beam a x i s i s 50 c a l c u l a t e d only once f o r each top l e v e l c a l l of examine. Each h i e r a r c h y element occupies an i n t e r v a l along the beam a x i s d e f i n e d by the element's minimum and maximum d i s t a n c e from the source (viewing) p o s i t i o n . T h i s minimum and maximum can be the minimum and maximum p o i n t s on the a s s o c i a t e d approximation element r a t h e r than the true minimum and maximum. As w i l l be shown i n Chapter 5, these can be d e r i v e d from a preprocessed 3-dimensional convex h u l l in time l o g a r i t h m i c i n the number of h u l l p o i n t s and from the r e s p e c t i v e bounding boxes in constant t ime. If the endpoints of these i n t e r v a l s are s o r t e d then the non-overlapping c o l l e c t i o n s of i n t e r v a l s can be i d e n t i f i e d by a s i n g l e sweep through the s o r t e d endpoints. T h i s i s done by ma i n t a i n i n g a count while sweeping across the s o r t e d endpoints (see F i g u r e 4.4). S t a r t i n g with zero, add one whenever encountering an 'opening' p o i n t of an i n t e r v a l and s u b t r a c t one whenever encountering a ' c l o s i n g ' p o i n t of an i n t e r v a l . Whenever the count becomes zero, an i n t e r v a l c orresponding to a separable p o r t i o n of the environment has been i d e n t i f i e d . T h i s use of i n t e r v a l s i s e s s e n t i a l l y the o v e r l a p p i n g segments problem d e s c r i b e d by Shamos [Sham,78,p.123]. In Shamos's f o r m u l a t i o n , given m i n t e r v a l s , the o v e r l a p p i n g segments can be d i s c o v e r e d by s o r t i n g the endpoints i n 0(m l o g m) time'and then performing an 0(m) sweep acr o s s the so r t e d endpoints. 51 source (a) D e f i n i n g D i s t a n c e s along Beam Axis H r (b) C o r r e s p o n d i n g I n t e r v a l s F i g u r e 4 . 4 U s i n g I n t e r v a l s f o r S p a t i a l O r d e r i n g 5 2 These i n t e r v a l s w i l l be used to order h i e r a r c h y elements for i n t e r s e c t i o n and c l i p p i n g . The c l i p p i n g must be able to i s o l a t e subsequences of i n t e r v a l s corresponding to separable c o l l e c t i o n s of faces i n the environment. I t must a l s o be able to access the s o r t e d elements i n order. When a h i e r a r c h y element i s expanded i n t o i t s co n t a i n e d sub-elements, the new i n t e r v a l s corresponding to those elements must be i n s e r t e d i n t o the i n t e r v a l l i s t . When an element i s found to l i e o u t s i d e the beam under c o n s i d e r a t i o n , i t s ' i n t e T v a l must be deleted- from the i n t e r v a l l i s t . The o r d e r i n g on the i n t e r v a l s must be maintained dynamically through these i n s e r t i o n s and d e l e t i o n s . A concatenable queue can be implemented using a balanced t r e e scheme [AhHopUll,74] (such as a 2-3 tr e e ) to meet these c r i t e r i a . T h i s data s t r u c t u r e supports INSERT, DELETE, FIND, CONCATENATE and SPLIT i n s t r u c t i o n s while m a i n t a i n i n g i t s leaves in o r d e r . A sequence of k of these i n s t r u c t i o n s can be processed in 0(k l o g k) time. Thus, m i n t e r v a l s can be so r t e d in 0(m l o g m) time using m INSERT i n s t r u c t i o n s and the separable i n t e r v a l s can s t i l l be i d e n t i f i e d i n 0(m) time. In the f o l l o w i n g d i s c u s s i o n , we assume that the i n t e r v a l s w i l l be maintained in such a s t r u c t u r e . The c a p i t a l i z e d INSERT, DELETE and SPLIT i n s t r u c t i o n w i t h i n the a l g o r i t h m o u t l i n e r e f e r to op e r a t i o n s on a s t r u c t u r e of t h i s form. The use of i n t e r v a l s i s an approximation which attempts to reduce a s p a t i a l s o r t i n g problem to a one-dimensional s o r t i n g 5 3 problem. T h i s , i n essence, t r e a t s the beam as a planar wavefront which i s orthogonal to the beam a x i s . A s p h e r i c a l wavefront, while being a more r e a l i s t i c model, i n t r o d u c e s computational d i f f i c u l t i e s . The f a r t h e s t polyhedron p o i n t from a given viewing p o s i t i o n cannot be determined using a unimodal search [AvTouBha,81]. However, the maximal polyhedron p o i n t i n a p a r t i c u l a r d i r e c t i o n can be obtained using a unimodal search. The o r d e r i n g i s obtained by n o t i n g - a t what d i s t a n c e s from the source p o s i t i o n any h i e r a r c h y element enters and leaves the wavefront (see F i g u r e 4.4). T h i s s i m p l i f i c a t i o n does not recognize p a i r s of elements which are separable but which happen to have an o v e r l a p p i n g i n t e r v a l . T h i s c o u l d be d e a l t with by doing more ex t e n s i v e p r e p r o c e s s i n g to precompute s e p a r a t i n g planes between neighbouring segments as in the method due to Schumacker et a l d e s c r i b e d i n [SuSprSch, 74]. These s e p a r a t i n g planes coul'd be used in a d d i t i o n to the i n t e r v a l o r d e r i n g . However, simply g e t t i n g a good h i e r a r c h i c a l decomposition would tend to encourage s e p a r a b i l i t y . Another f a c t o r r e l a t e d to the s e p a r a b i l i t y of h i e r a r c h y elements, which we w i l l r e t u r n to in the next chapter, i s the ' t i g h t n e s s of f i t ' of the h i e r a r c h i c a l approximation element used. 4 .2 I n t e r s e c t ion Examine i s the main c o n t r o l r o u t i n e which decides which elements are to be excluded summarily and which are to be 54 r e t a i n e d and expanded f o r f u r t h e r t e s t i n g (see F i g u r e 4.2). Examine takes as input the s p e c i f i c a t i o n of a beam, a p o r t i o n of the environment d e s c r i b e d in an element l i s t and the i n t e r v a l o r d e r i n g for these elements. I t r e t u r n s as output a l i s t of c l i p p e d polygons corresponding to the planar s u r f a c e s v i s i b l e w i t h i n the beam. I t a l s o r e t u r n s the 'passby' l i s t : a l i s t of beams d e f i n e d by the p o r t i o n s of the beam not i n t e r s e c t i n g any of the p o r t i o n of the environment passed to examine i n the element l i s t . I t i s p o s s i b l e that the viewing p o s i t i o n w i l l be con t a i n e d w i t h i n one or more h i e r a r c h y elements. These elements must be expanded before any others so that the p o r t i o n s 'behind' the viewing p o s i t i o n can be d i s c a r d e d and the p o r t i o n s ' i n f r o n t ' can be i n s e r t e d i n t o the i n t e r v a l l i s t . Here, we can assume that some r o u t i n e invoked before the f i r s t c a l l to examine handles t h i s s p e c i a l case and that, the viewing p o s i t i o n i s not i n t e r n a l to any of the elements i n the element l i s t . At any p a r t i c u l a r time in the search, elements of widely v a r y i n g s i z e s and complexity may be stacked f o r examination. The r e c u r s i o n i s invoked in such a way that the search s t r a t e g y becomes a c l o s e s t - e l e m e n t d e p t h - f i r s t search i n t o the h i e r a r c h y . The use of separable i n t e r v a l s and 'passby' beams i s what allows the e v a l u a t i o n of d i s t a n t elements to be d e f e r r e d . 5 5 The r o u t i n e always s p l i t s the input p o r t i o n of the environment i n t o a ' c l o s e r ' p o r t i o n and a ' f a r t h e r ' p o r t i o n . I t w i l l always f i n i s h d e a l i n g with the ' c l o s e r ' p o r t i o n before i t examines the ' f a r t h e r ' . In t h i s way, i f the ' c l o s e r ' p o r t i o n e n t i r e l y occludes the beam, no time i s wasted i n p r o c e s s i n g the ' f a r t h e r ' . Examine maintains and uses the s o r t e d i n t e r v a l order d e s c r i b e d in the l a s t s e c t i o n to decide where to s p l i t the environment. The i n t e r v a l order i s a l s o used to decide which non-planar elements to expand. If examine i s c a l l e d with a sequence of elements, a l l of which are p l a n a r , then no r e c u r s i o n need be used to expand any of them. Once these elements are c l i p p e d out of the beam, the r o u t i n e t e r m inates. Examine uses the i n t e r v a l s to i s o l a t e the f i r s t s eparable c o l l e c t i o n of planar f a c e s , and SPLITS the element l i s t i n t o two separable subsequences. A c a l l to the c l i p p i n g r o u t i n e , with the c l o s e r subsequence, w i l l then segment the beam in t o the p o r t i o n s s t r i k i n g the pl a n a r faces i n that subsequence and those pass i n g by. The p o r t i o n of the beam which i s not occluded by the given sequence of faces i s returned from the c l i p p i n g r o u t i n e as a ( p o s s i b l y empty) l i s t of 'passby' beams. If such a l i s t of passby beams i s ever re t u r n e d from c l i p p i n g or from a r e c u r s i v e c a l l to examine then each passby beam i s d e a l t with i n a separate r e c u r s i v e c a l l to examine with the remaining sequence of elements. Passby beams which remain a f t e r a l l sequences 56 have been d e a l t with are retu r n e d to the c a l l i n g r o u t i n e . In the event that the scene i s unbounded i n some d i r e c t i o n s , the element sequence w i l l be exhausted before the passby l i s t i s . In t h i s case, the passby l i s t w i l l be ret u r n e d to the main c a l l i n g r o u t i n e which can a s s i g n the p o r t i o n s of the window corresponding to the passby beam l i s t some background v a l u e . I f , i n the i n i t i a l t e s t i n examine, not a l l the nodes correspond to planar elements then the r o u t i n e takes the f i r s t nonplanar element and expands i t i n t o a number of subnodes. Examine uses the r o u t i n e i n t e r s e c t to t e s t the c u r r e n t beam f o r i n t e r s e c t i o n a g a i n s t each given subnode. The i n t e r s e c t i o n a l g o r i t h m used in t h i s r o u t i n e depends on the approximation s t r u c t u r e used i n the h i e r a r c h y and w i l l be d i s c u s s e d i n the next chapter. Examine ignores subnodes which l i e e n t i r e l y o u t s i d e the beam. It INSERTS a l l other subnodes i n t o the element l i s t ordered on t h e i r c l o s e s t - p o i n t p r o x i m i t y to the source p o s i t i o n . I t a l s o INSERTS the i n c l u d e d subnode's i n t e r v a l i n t o the i n t e r v a l l i s t . Examine uses a backface t e s t t o e l i m i n a t e planar elements o r i e n t e d away from the viewing p o s i t i o n . I t then uses the i n t e r v a l l i s t to determine the f i r s t separable i n t e r v a l . In the worst case, t h i s i n t e r v a l l i s t may correspond to the e n t i r e element l i s t . The element l i s t i s then SPLIT 5 7 i n t o two separable p o r t i o n s and each p o r t i o n i s r e c u r s i v e l y 'examined'. 4 . 3 C l i p p i n g One of the b e n e f i t s of the h i e r a r c h i c a l s t r u c t u r e presented i s the a b i l i t y to defer p r o c e s s i n g on p o t e n t i a l l y complex p o r t i o n s of the room. The i n t e r v a l o r d e r i n g on the h i e r a r c h y elements allows us to unwrap the c l o s e s t separable p o r t i o n of the environment and deal e n t i r e l y with i t before c o n t i n u i n g on to elements f a r t h e r away. For example, one l a r g e p o l y g o n a l face may occupy a l l of the beam area. P r o c e s s i n g on the p o t e n t i a l l y complex p o r t i o n s o f the scene behind i t should be avoided u n t i l t h i s face i s c l i p p e d out of the c u r r e n t beam. The c l i p p i n g approach used i s c r i t i c a l to the s u c c e s s f u l use of the h i e r a r c h y f o r d e f e r r i n g p r o c e s s i n g . I t must be able to d e a l with c o l l e c t i o n s of polygons which are not n e c e s s a r i l y s e p a r a b l e . I t must be able to d e f e r p r o c e s s i n g the p o r t i o n s of the window which do not c o n t a i n any of the polygons c u r r e n t l y under c o n s i d e r a t i o n but which may c o n t a i n elements stacked by examine. The h i e r a r c h i c a l approach l i m i t s the number of polygons under c o n s i d e r a t i o n f o r c l i p p i n g so that most of the c a l l s to t h i s r o u t i n e should i n v o l v e a very small number of c l i p - l i s t polygons. However, i t i s p o s s i b l e that i n some scenes a l a r g e 58 number of polygons w i l l remain and the method used for c l i p p i n g should be general enough to handle t h i s as w e l l . The method proposed for c l i p p i n g meets these c r i t e r i a . W e i l e r ' s method for polygon comparison [Weil,80] takes as input a number of polygons to be 'compared' and b u i l d s a graph r e p r e s e n t a t i o n of the polygon contours and t h e i r i n t e r s e c t i o n s . By t r a v e r s i n g t h i s graph r e p r e s e n t a t i o n , i t i s p o s s i b l e to d e r i v e a l i s t of- polygonal contours along'with- t h e i r 'owning' polygons. T h i s method and some suggested improvements w i l l be d e s c r i b e d f u r t h e r i n S e c t i o n 4.3.3. 4.3.1 The C l i p p i n g Routine T h i s s e c t i o n d e s c r i b e s g e n e r a l l y the o u t l i n e of the r o u t i n e s .used for. c l i p p i n g . The c l i p p i n g method i s d e s c r i b e d in more d e t a i l in subsequent s e c t i o n s . The proposed c l i p p i n g r o u t i n e s are presented i n F i g u r e 4.3. The c l i p p i n g r o u t i n e takes as input a beam d e f i n e d by a source (viewing) p o s i t i o n along with d e l i m i t i n g rays emanating from that p o s i t i o n . I t a l s o r e q u i r e s a ' c l i p - l i s t ' sequence of polygons along with an i n t e r v a l l i s t as d e s c r i b e d i n the s o r t i n g s e c t i o n above to s p e c i f y t h e i r r e l a t i v e o r d e r i n g . A l l c l i p p i n g performed by t h i s r o u t i n e takes p l a c e on a p r o j e c t i o n plane chosen to be orthogonal to the beam a x i s . The beam's i n t e r s e c t i o n with t h i s plane d e f i n e s a 'beam polygon' a g a i n s t 5 9 which the other polygons are c l i p p e d . A l l of the d e f i n e d polygons are simple but any can be non-convex with h o l e s . As s t a t e d i n the d e f i n i t i o n i n Chapter 2 , a l l polygon edges are d i r e c t e d so that the i n t e r i o r of the polygon i s on the l e f t . T h i s means that the polygon outer boundaries are s p e c i f i e d in c o u n t e r - c l o c k w i s e order and that the polygon hole boundaries are s p e c i f i e d i n cl o c k w i s e order. T h i s a l s o provides- a way of s p e c i f y i n g the- ' v i s i b l e ' s i d e of a c l i p p i n g boundary. The c 1 i p p i n g r o u t i n e r e t u r n s a l i s t of ' v i s i b l e ' polygons c l i p p e d from the o r i g i n a l c l i p - l i s t polygons. I t a l s o r e t u r n s a l i s t of new passby beams d e f i n e d by the p o r t i o n of the o r i g i n a l beam which d i d not i n t e r s e c t any of the c l i p - l i s t polygons. Each of the polygons i n the output polygon l i s t must correspond to the c l o s e s t s u r f a c e .to the viewing p o s i t i o n f o r i t s p a r t i c u l a r p r o j e c t i o n area on the p r o j e c t i o n plane. The output d e f i n e s a decomposition of the. beam polygon in that the p r o j e c t i o n area of the v i s i b l e polygons p l u s the area of the passby beam polygons equals the area of the o r i g i n a l beam polygon. Note that the entry i n t o the c l i p p i n g r o u t i n e can be t i e d to a t h r e s h o l d ( e p s i l o n ) on the beam area. T h i s does not cause problems i n the gen e r a l case; a complete s o l u t i o n can be formed by s e t t i n g e p s i l o n to zero. However, i n the a c o u s t i c s 6 0 modeling, the e p s i l o n can be used to e l i m i n a t e unnecessary p r o c e s s i n g when a l l but an i n s i g n i f i c a n t p o r t i o n of the beam has been processed. T h i s e p s i l o n may a l s o be u s e f u l i n a r a s t e r scan p i x e l c a l c u l a t i o n where only one value i s to be returned f o r the e n t i r e window. Pr o c e s s i n g of the window c o u l d stop at some f r a c t i o n of the area of the o r i g i n a l window ( f o r example) and a weighted area value c o u l d be r e t u r n e d p o s s i b l y p r o v i d i n g s u b - p i x e l r e s o l u t i o n e f f e c t s . As C l ark [Cl,76] suggested, t h i s uses the h i e r a r c h y scheme to l i m i t p r o c e s s i n g a c c o r d i n g to the r e s o l u t i o n l i m i t a t i o n s of the d i s p l a y . C l a r k r e f e r r e d to t h i s a s . r e s o l u t i o n c l i p p i n g . In expanding the h i e r a r c h y elements in examine, a rough depth s o r t , as d e s c r i b e d i n S e c t i o n 4.1, i s maintained i n the form of i n t e r v a l s . Because of the way the polygons were aggregated in examine for the c a l l to c l i p p i n g , the l i s t of c l i p polygons does not have a separable subsequence of i n t e r v a l s . T h i s does not mean that the c l i p - l i s t polygons do not admit to a t o t a l depth o r d e r i n g but only that the i n t e r v a l approximation c o u l d not determine an o r d e r i n g r e l a t i v e to t h i s viewing p o s i t i o n . Even though there are no separable subsequences in the i n t e r v a l l i s t , the i n t e r v a l s s t i l l p r o vide u s e f u l i n f o r m a t i o n . For example, note that a given polygon can only have a depth 61 c o n f l i c t with other polygons which have o v e r l a p p i n g i n t e r v a l s . Thus i n p r o c e s s i n g the c l i p - l i s t , i t i s s u f f i c i e n t to sweep from f r o n t to back c o n s i d e r i n g polygons one at a time. A polygon i s only t e s t e d f o r a depth c o n f l i c t a g a i n s t the polygons f o l l o w i n g i t in the o r d e r i n g which have an o v e r l a p p i n g i n t e r v a l . The i n i t i a l loop i n c 1 i p p i n g t r i e s to o b t a i n a polygon which i s v i s i b l e w i t h i n the beam. Subsequently, the c l i p r o u t i n e w i l l be used to s l i c e the v i s i b l e p o r t i o n s of t h i s polygon out of the c u r r e n t beam. The f i r s t polygon i n the ordered i n t e r v a l l i s t i s c o n s i d e r e d as a candidate f o r a v i s i b l e polygon. It i s t e s t e d f o r i n t e r s e c t i o n with the beam. If there i s no i n t e r s e c t i o n then t h i s polygon i s d i s c a r d e d and the r o u t i n e loops back to t e s t another. If there i s an i n t e r s e c t i o n with the beam then c l i p i s c a l l e d to p a r t i t i o n the beam i n t o the v i s i b l e p o r t i o n of the c l i p polygon and the passby p o r t i o n of the beam. Even i f the polygon l i e s w i t h i n the beam, i t i s p o s s i b l e that the e n t i r e polygon i s occluded. I f no p o r t i o n of the polygon under c o n s i d e r a t i o n i s v i s i b l e then i t i s d i s c a r d e d and the r o u t i n e loops back to t e s t another polygon f o r v i s i b i l i t y w i t h i n the beam. A f t e r e x i t i n g from t h i s loop, i f no p o r t i o n s of any of the input polygons are v i s i b l e w i t h i n the beam, then the e n t i r e 6 2 beam i s retu r n e d as a passby. Otherwise, some p o r t i o n s of one of the polygons i s v i s i b l e w i t h i n the beam and those p o r t i o n s are appended to the windowed polygon l i s t . If there are p o r t i o n s of the beam o u t s i d e the p a r t i a l l y v i s i b l e polygon ( d e f i n i n g passby beams) then they are handled i n d i v i d u a l l y with r e c u r s i v e c a l l s to c l i p p i n g . C l i p takes as input the c u r r e n t beam, the input polygon l i s t , the corresponding i n t e r v a l l i s t " and' the" current' polygon polygon to be c l i p p e d ( r e f e r r e d to i n the f o l l o w i n g d i s c u s s i o n as the c l i p polygon. I t produces a l i s t of v i s i b l e polygons s l i c e d from the c l i p polygon and a l i s t of polygons which d e f i n e the passby p o r t i o n s of the beam which l i e o u t s i d e the v i s i b l e p o r t i o n s of the c l i p polygon. The c l i p r o u t i n e uses a graph r e p r e s e n t a t i o n due to Weiler [Weil,80] t o p a r t i t i o n the c l i p polygon i n t o v i s i b l e and n o n - v i s i b l e p o r t i o n s . I t i s a l s o used to p a r t i t i o n the beam i n t o the p o r t i o n s which i n t e r s e c t and the p o r t i o n s which passby the c l i p polygon. T h i s graph r e p r e s e n t a t i o n d e f i n e s a t e s s e l a t i o n of the p r o j e c t i o n plane i n t o a l l p o s s i b l e regions d e f i n e d on the p r o j e c t i o n s of the beam and the polygons to be c l i p p e d . Each region has a s s o c i a t e d with i t a l i s t of owning  polygons. I n i t i a l l y , any polygon which c o n t a i n s a p a r t i c u l a r region i s s a i d to be an owning polygon of that r e g i o n . By 63 ' t r a v e r s i n g ' the graph r e p r e s e n t a t i o n , i t i s p o s s i b l e to determine a l i s t of regions s a t i s f y i n g any 'owning polygon' requirements. For example, the l i s t of regions which are owned by the beam and the polygon to be c l i p p e d d e f i n e s the p o r t i o n s of the polygon which are p o t e n t i a l l y v i s i b l e w i t h i n the beam. Since the graph r e p r e s e n t a t i o n i n c l u d e s a l l p o s s i b l e regions d e f i n e d on the polygons under c o n s i d e r a t i o n , w i t h i n each region there i s a t o t a l depth o r d e r i n g of the polygons which own that r e g i o n . Thus, the. s i n g l e polygon which i s v i s i b l e w i t h i n a given region of the graph r e p r e s e n t a t i o n can be determined using the plane equations of that region's owning polygons and any ray from the viewing p o s i t i o n passing through that r e g i o n . W e i l e r ' s graph r e p r e s e n t a t i o n , i t s c o n s t r u c t i o n , and maintenance w i l l be f u r t h e r d i s c u s s e d in S e c t i o n 4.3.3. The c l i p r o u t i n e f i r s t aggregates a l i s t of t e s t polygons which have an o v e r l a p p i n g i n t e r v a l with the c l i p polygon. These polygons are the only polygons in the c l i p l i s t which c o u l d p o s s i b l y occlude any p o r t i o n of the c l i p polygon. W e i l e r ' s graph r e p r e s e n t a t i o n i s c o n s t r u c t e d on t h i s l i s t of t e s t polygons, the c l i p polygon, and the beam polgon. The f i r s t t r a v e r s a l of the graph r e p r e s e n t a t i o n produces the complete l i s t of regions which l i e i n s i d e the beam and the c l i p polygon (and p o s s i b l y o t h e r s ) . The next loop t e s t s each region to see i f the c l i p polygon i s the ' v i s i b l e ' ( c l o s e s t ) polygon c o n t a i n i n g that r e g i o n . If the c l i p polygon i s not the 64 v i s i b l e polygon w i t h i n that r e g i o n then i t is- removed as an owner of that r e g i o n . The graph i s t r a v e r s e d again to o b t a i n the regions d e f i n e d by the v i s i b l e p o r t i o n s of the c l i p polygon. T h i s second t r a v e r s a l i s performed to a v o i d unnecessary segmentation of the v i s i b l e c l i p polygon area. I t produces the minimum number of regions d e f i n i n g the v i s i b l e p o r t i o n s of the c l i p polygon w i t h i n the beam. The f i n a l t r a v e r s a l o b t a i n s the regions which are w i t h i n the beam but not the c l i p polygon. T h i s again produces the minimum number of regions f o r which t h i s i s t r u e . These regions w i l l be used to d e f i n e the passby l i s t f o r t h i s beam. 4.3.2 Previous Related Work The method used f o r c l i p p i n g i s based on an a l g o r i t h m by Weiler [Weil,80]. T h i s was an a b s t r a c t i o n of the method presented by Weiler and Atherton [WeilAth,77]. T h e i r a l g o r i t h m for c l i p p i n g i s , in t u r n , an extension of Sutherland and Hodgman's ree n t r a n t polygon c l i p p i n g a l g o r i t h m [SuHod,74]. I t i s i n s t r u c t i v e to examine these a l g o r i t h m s b r i e f l y before r e t u r n i n g to W e i l e r ' s method i n d e t a i l . S u t herland and Hodgman's a l g o r i t h m [SuHod,74] operates only on windows d e f i n e d by convex polygons. I t t r e a t s each 65 window edge as a bounding h a l f - p l a n e and c l i p s the viewed polygons a g a i n s t one h a l f plane at a time. I t s input i s a r i n g of v e r t i c e s d e f i n i n g a polygon and a l i n e d e f i n i n g a bounding h a l f plane with a ' v i s i b l e ' s i d e s p e c i f i e d . I t s output i s one or more polygon vertex r i n g s . The a l g o r i t h m operates by n o t i n g that the endpoints of a d i r e c t e d polygon edge can r e l a t e to a bounding h a l f - p l a n e i n only four ways. I t c o n s i d e r s each edge in turn and takes a p p r o p r i a t e a c t i o n s f o r each case (see F i g u r e 4.5). These are: a) both endpoints v i s i b l e : output f i r s t endpoint. b) f i r s t endpoint v i s i b l e and second endpoint not v i s i b l e : output v i s i b l e endpoint and i n t e r s e c t i o n of segment with c l i p p i n g boundary. c) f i r s t endpoint not v i s i b l e and second endpoint v i s i b l e : output i n t e r s e c t i o n of segment with c l i p p i n g boundary. d) n e i t h e r endpoint v i s i b l e : output nothing. As Sutherland and Hodgman d i s c u s s , minor changes to the r o u t i n e w i l l allow the c o r r e c t p r o c e s s i n g of polygons which may r e s u l t i n degenerate cases. T h i s i n c l u d e s the c l i p p i n g of concave polygons, polygons with h o l e s , or s e l f - i n t e r s e c t i n g polygons a g a i n s t a bounding h a l f - p l a n e . The viewing window however i s always r e s t r i c t e d to being convex. Note that the p o i n t s at which t r a n s i t i o n s occur are the 66 case (a) F i g u r e 4 . 5 Sutheriand-Hodgman C l i p p i n g i n t e r s e c t i o n p o i n t s of the bounding h a l f - p l a n e d e f i n i n g the c l i p p i n g boundary and the polygon to be c l i p p e d . If these p o i n t s are precomputed then they can be used to t r a c e out the v i s i b l e p o r t i o n of the polygon (see F i g u r e 4 . 5 ) . Weiler and Atherton's c l i p p i n g a l g o r i t h m [ W e i l A t h / 7 7 ] i s an ext e n s i o n of t h i s precomputed i n t e r s e c t i o n polygon c l i p p i n g a l g o r i t h m . Note that i n t r a c i n g the c l i p p e d o b j e c t , the c l i p p i n g boundary may as w e l l have been a polygonal c h a i n as a s t r a i g h t l i n e . The next o b s e r v a t i o n , which motivates t h e i r a l g o r i t h m , i s that the c l i p p i n g boundary can be a c l o s e d polygonal c h a i n . In f a c t , the c l i p p i n g boundary may be as complex as the polygon to be c l i p p e d . Thus, t h i s c l i p p i n g Note that the d i r e c t i o n on the c l i p p i n g boundary i s used to t r a c e v i s i b l e p o r t i o n of the c l i p polygon; the i n t e r i o r i s on the ' l e f t * . F i g u r e 4.6 Precomputed I n t e r s e c t i o n C l i p p i n g 68 a l g o r i t h m i s general enough to c l i p non-convex polygons with holes a g a i n s t other non-convex polygons with h o l e s . T h e i r c l i p p i n g a l g o r i t h m operates by i n t e r s e c t i n g a l l segments in the polygon to be c l i p p e d with a l l the segments in the polygon d e f i n i n g the c l i p boundary. In two passes, i t uses the i n t e r s e c t i o n p o i n t s and the o r i g i n a l p o i n t s to t r a c e out the c l i p p e d polygon and the remaining p o r t i o n s of the window. They note that a d d i t i o n a l p r o c e s s i n g i s necessary to determine s t r i c t l y c o n t a i n i n g r e l a t i o n s h i p s between polygons and/or holes but do not g i v e d e t a i l s of the method which they used. 4.3.3 W e i l e r ' s Method and Suggested Improvements Weiler [Weil,80] a b s t r a c t e d the c l i p p i n g method of Weiler and Atherton i n t o g e n e r a l i z e d 'polygon comparison' by noting that the c l i p p i n g of s e v e r a l polygons c o u l d be 'batched' by c o n s t r u c t i n g a graph r e p r e s e n t a t i o n of t h e i r v e r t i c e s , edges and i n t e r s e c t i o n p o i n t s . T h i s graph r e p r e s e n t a t i o n can be t r a v e r s e d to d e r i v e the union, i n t e r s e c t i o n or d i f f e r e n c e of any combination of the input polygons. T h i s graph r e p r e s e n t a t i o n l i n k s edges at t h e i r i n t e r s e c t i o n p o i n t s as the W e i l e r / A t h e r t o n method d i d . T h i s can be thought of as ' o v e r l a y i n g ' a l l of the polygons to d e f i n e a number of r e g i o n s i n the plane. Each region i s c o n t a i n e d w i t h i n some number of the o r i g i n a l input polygons. These 69 o r i g i n a l polygons are c a l l e d the 'owners' of the r e g i o n . Every edge bounds two regions and has an a s s o c i a t e d l i s t of 'owners' for each. Thus, s t a r t i n g at an i n t e r s e c t i o n p o i n t and f o l l o w i n g the edges with the a p p r o p r i a t e 'owners', i t i s p o s s i b l e to t r a c e out any of the d e s i r e d polygon combinations. T h i s method has the advantage that edge-edge, edge-endpoint, endpoint-endpoint, and c o i n c i d e n t edge i n t e r s e c t i o n s are a l l i n s e r t e d i n t o the graph r e p r e s e n t a t i o n e a s i l y and then handled u n i f o r m l y . A d d i t i o n a l p r o c e s s i n g i s r e q u i r e d to handle n o n - i n t e r s e c t i n g regions a r i s i n g from holes or s t r i c t l y c o n t a i n e d polygons. Weiler d e s c r i b e s a scheme by which contour r e l a t i o n s h i p s can be maintained although he does not s p e c i f y the containment t e s t to be used. To c o n s t r u c t the graph r e p r e s e n t a t i o n , i t i s necessary to compute the i n t e r s e c t i o n s of the polygons which d e f i n e the r e g i o n s . In i n t e r s e c t i n g the polygons, we can continue with the general philosophy of e l i m i n a t i n g n o n - i n t e r s e c t i o n s i f p o s s i b l e . By q u i c k l y d e t e c t i n g that a p a i r of polygon approximations do not i n t e r s e c t , we can a v o i d executing a more complex polygon i n t e r s e c t i o n a l g o r i t h m with the corresponding polygons. The next chapter w i l l d i s c u s s the method and complexity of d e t e c t i n g n o n - i n t e r s e c t ions between the convex approximations of a p a i r of polygons. Up to t h i s p o i n t , a l l i n t e r s e c t i o n t e s t i n g , s o r t i n g and 70 other p r o c e s s i n g has been performed on an approximation of the beam and approximations of the elements ( i n c l u d i n g p o l ygonal faces) i n the h i e r a r c h y . These approximations w i l l be d e s c r i b e d i n the next c h a p t e r . Having used these approximations to q u i c k l y t e s t f o r n o n - i n t e r s e c t i o n s , we can now a f f o r d to spend more time examining in d e t a i l the elements which correspond to the approximations which have passed our t e s t s . Shamos [Sham,78] [ShamHoey,76] presents an a l g o r i t h m f o r computing line-segment i n t e r s e c t i o n s . T h i s a l g o r i t h m has some unusual p r o p e r t i e s . I t may not f i n d a l l i n t e r s e c t i n g p a i r s of l i n e segments but i t i s guaranteed to f i n d the l e f t - m o s t . Thus, i t i s s u i t a b l e as a n o n - i n t e r s e c t ion e l i m i n a t i o n a l g o r i t h m . The a l g o r i t h m proceeds as f o l l o w s : Pick a d i r e c t i o n l i n e (say, the x d i r e c t i o n ) and s o r t the p r o j e c t i o n s " of the endpoints onto t h i s l i n e (the x c o o r d i n a t e s ) . Sweep from l e f t to r i g h t m a i n t a i n i n g a l i s t (ordered on y - c o o r d i n a t e s ) of 'current segments'. Do t h i s by i n s e r t i n g a segment i n t o the l i s t whenever i t s opening endpoint i s encountered and d e l e t i n g i t from the l i s t whenever i t s c l o s i n g endpoint i s encountered. Whenever an i n s e r t i o n or d e l e t i o n o p e r a t i o n i s performed, t e s t the segments which have become adjacent in the o r d e r i n g f o r i n t e r s e c t i o n . 71 For n l i n e segments, the endpoints can be s o r t e d i n 0(n l o g n) time. The sweep has a constant number of o p e r a t i o n s per endpoint f o r an 0(n) time complexity. Thus, the o v e r a l l asymptotic complexity i s 0(n log n ) . In a p r a c t i c a l sense, the s o r t i n g step of the above i n t e r s e c t i o n a l g o r i t h m i s not wasted because i t can be i n c o r p o r a t e d i n t o the a c t u a l i n t e r s e c t i o n t e s t i n g . For n l i n e segments, there may be as many as n 2 i n t e r s e c t i o n s so i n the worst case we cannot do b e t t e r than t h i s . However, the s o r t e d order can be i n c o r p o r a t e d i n an a l g o r i t h m which f i n d s a l l i n t e r s e c t i o n s . An i n t e r s e c t i o n a l g o r i t h m u s i n g the s o r t e d order would operate in b e t t e r expected time than simply i n t e r s e c t i n g a l l p a i r s of segments. In h i s d o c t o r a l t h e s i s [Sham,78,p.140], Shamos poses the q u e s t i o n : "Of N l i n e segments, suppose that k p a i r s i n t e r s e c t . Does there e x i s t an 0(max(N log N,k)) a l g o r i t h m to l i s t them?" To the best of our knowledge, t h i s i s s t i l l an open q u e s t i o n . S e v e r a l improvements to the proposed c l i p p i n g a l g o r i t h m s of F i g u r e 4.3 c o u l d be made by m a i n t a i n i n g W e i l e r ' s graph r e p r e s e n t a t a t i o n through r e c u r s i v e c a l l s to the c l i p p i n g r o u t i n e . T h i s was not i n c o r p o r a t e d i n the o u t l i n e f o r the sake of c l a r i t y . One b e n e f i t would be that i n the p r o c e s s i n g of d i f f e r e n t c l i p polygons the graph s t r u c t u r e would not need to be e n t i r e l y r e b u i l t each time. The graph s t r u c t u r e would have 72 new polygons i n s e r t e d and c l i p p e d polygons d e l e t e d . Another b e n e f i t i s that i f the graph s t r u c t u r e i s to be maintained then i t i s p o s s i b l e to do some p r e p r o c e s s i n g to f a c i l i t a t e the t e s t i n g to be performed on i t . In p a r t i c u l a r , i t i s p o s s i b l e to t r i a n g u l a t e the d e f i n e d r e g i o n s by i n s e r t i n g edges with ' n u l l ' owners i n t o the graph r e p r e s e n t a t i o n . T h i s t r i a n g u l a t i o n can be performed using the method of Garey et a l [Gar JoPrepTar ,78"]. If there are q p o i n t s d e f i n i n g the r e g i o n s , the regions can be t r i a n g u l a t e d i n 0(q l o g q) time. Having been t r i a n g u l a t e d , the regions can be f u r t h e r processed to accommodate the p l a n a r p o i n t l o c a t i o n a l g o r i t h m of K i r k p a t r i c k [ K i r k , 8 l ] . T h i s a l g o r i t h m with O(q) p r e p r o c e s s i n g time and 0(q) i n c r e a s e in space, can l o c a t e the c o n t a i n i n g region of a query p o i n t i n O(log q) time. T h i s i s u s e f u l f o r s e v e r a l reasons. The containment t e s t of n o n - i n t e r s e c t i n g polygons can be performed q u i c k l y . As w e l l , new polygons can be i n s e r t e d f a i r l y q u i c k l y . T h i s can be done by i n s e r t i n g one edge at a time. The endpoints can be p l a c e d in the a p p r o p r i a t e t r i a n g l e s in the t r i a n g u l a t i o n and the edge's i n t e r s e c t i o n s can be d i s c o v e r e d by 'walking' along the edge through the t r i a n g u l a t i o n . As each 'true' edge i s c r o s s e d , the i n t e r s e c t i o n i s updated. When a l l new edges have been i n s e r t e d , only 'contaminated' r e g i o n s need be r e t r i a n g u l a t e d . 7 3 K i r k p a t r i c k ' s method preprocesses the t r i a n g u l a t i o n by c r e a t i n g a ' t r i a n g u l a t i o n h i e r a r c h y ' . T h i s i s a sequence of t r i a n g u l a t i o n s where the i n i t i a l t r i a n g u l a t i o n i s the o r i g i n a l , and each element a f t e r t h i s i s d e r i v e d from i t s predecessor by removing a f i x e d - f r a c t i o n of low-degree independent v e r t i c e s and r e t r i a n g u l a t i n g . T h i s c o n t i n u e s u n t i l the f i n a l element i n the sequence has a constant number of r e g i o n s . K i r k p a t r i c k shows that i f there are i n i t i a l l y q p o i n t s d e f i n i n g the reg i o n s , there w i l l be lo g ( q ) ' element's i n t h i s sequence. The l o c a t i o n of a p o i n t ' s c o n t a i n i n g region i s performed by f i r s t t e s t i n g the query p o i n t f o r l o c a t i o n in the l a s t t r i a n g u l a t i o n i n the sequence. Once the po i n t has been l o c a t e d in one of the constant number of re g i o n s , i t s c o n t a i n i n g region i s r e f i n e d using the f i n e r preceding t r i a n g u l a t i o n i n the sequence. T h i s continues u n t i l the po i n t i s l o c a t e d w i t h i n one of the t r i a n g l e s in the o r i g i n a l t r i a n g u l a t i o n . A constant number of t e s t s f o r each of a l o g a r i t h m i c number of elements produces-the 0 ( l o g q) search r e s u l t . Problems may be i n t r o d u c e d when t r y i n g to maintain t h i s ' t r i a n g u l a t i o n h i e r a r c h y ' d y n a m i c a l l y . As edges are i n s e r t e d , the 'contaminated' regions w i l l be r e t r i a n g u l a t e d and the h i e r a r c h y elements c o n t a i n i n g these regions must be updated. T h i s may be done q u i c k l y i f the changes are l o c a l i z e d i n the t r i a n g u l a t i o n but e x t e n s i v e a l t e r a t i o n s may r e q u i r e r e b u i l d i n g the t r i a n g u l a t i o n h i e r a r c h y e n t i r e l y . 7 4 The h i e r a r c h i c a l refinement technique used in t h i s a l g o r i t h m w i l l reappear in the convex approximation i n t e r s e c t i o n a l g o r i t h m s of the next chapter. 7 5 CHAPTER 5 : H i e r a r c h y Approximation Elements In t h i s chapter, candidates f o r h i e r a r c h y approximation elements are examined. The two-dimensional elements are r e c t i l i n e a r bounding r e c t a n g l e s , minimum-area bounding r e c t a n g l e s , and two-dimensional convex h u l l s . The thre e - d i m e n s i o n a l candidates are r e c t i l i n e a r bounding boxes, minimum-volume bounding boxes, and convex h u l l s . These s t r u c t u r e s have been chosen as' the best convex candidates f o r h i e r a r c h y elements. T h e i r d e f i n i t i o n s and a d i s c u s s i o n of t h e i r r e l e v a n t f e a t u r e s appear i n Chapter 2 . Here, the elements are compared as to c o n s t r u c t i o n time, storage cost and i n t e r s e c t i o n time. In the f i r s t s e c t i o n , the two-dimensional elements are d i s c u s s e d . In the second s e c t i o n , the thr e e - d i m e n s i o n a l candidates f o r h i e r a r c h y elements are compared. In the next s e c t i o n , we present a ge n e r a l comparison of the v a r i o u s elements. We conclude the chapter by arguing f o r a h y b r i d h i e r a r c h y where the approximation element used i s chosen a c c o r d i n g to i t s ' t i g h t n e s s of f i t ' . In s o l v i n g the i n t e r s e c t i o n subproblem d e f i n e d i n Chapter 2 , i t i s necessary to compute which p o l y h e d r a l approximation elements i n t e r s e c t a s p e c i f i e d beam. In s o l v i n g the c l i p p i n g subproblem d e f i n e d in Chapter 2 , i t i s necessary to to determine which polygonal approximations l i e w i t h i n a s p e c i f i e d 76 beam. Although the beam defines a three-dimensional volume, i t is b a s i c a l l y an extrusion of a two-dimensional object. A l l beam cross-sections are congruent, therefore the beam can be considered a two-dimensional object sweeping through space. Since the intersection of a beam with any projection plane orthogonal to the beam dire c t i o n and on the correct side of the viewing position' w i l l always' define- the- same polygon-, i t makes sense to refer to thi s as the beam polygon. As mentioned in the introduction, our underlying philosophy is to eliminate non-intersect ions as quickly as possible. Therefore, to eliminate an approximation element from consideration, i t is s u f f i c i e n t to detect a non-intersect ion between the beam and that element. 5 . 1 Two-Dimensional Approx imat ion Elements As explained above, the beam cross-section can be considered a two-dimensional structure. Therefore, the beam and face polygons are the two-dimensional e n t i t i e s to be wrapped in a convex approximation. As noted e a r l i e r , the two-dimensional objects can be considered degenerate cases of the s i m i l a r l y defined three-dimensional structures. We w i l l consider them separately 77 here because some r e s u l t s , notably the l i n e a r convex h u l l and minimum-area bounding r e c t a n g l e c o n s t r u c t i o n a l g o r i t h m s , b e n e f i t from being embedded in the plane and do not extend to three dimensions. Although a polygon in our scheme may have h o l e s , only the outer contour i s used to c o n s t r u c t an approximation element. T h i s i s because the elements are a l l convex. In the f o l l o w i n g d i s c u s s i o n , n r e f e r s to the' number- of v e r t i c e s d e f i n i n g a polygon. 5.1.1 Construct ion Shamos [Sham,78,p.45] proves an fi(n log n) lower bound on the two-dimensional convex h u l l problem by demonstrating that any s o l u t i o n to t h i s problem can be used to s o r t . However, i t i s p o s s i b l e to do b e t t e r i f the input p o i n t s are d e f i n e d as being ordered on a simple polygonal contour. Graham and Yao [GrYao,8l] present an 0(n) a l g o r i t h m to f i n d the h u l l of an ordered simple p o l y g o n a l contour. The r e c t i l i n e a r bounding box can be c o n s t r u c t e d by performing a s i n g l e pass ac r o s s a l l the p o i n t s and r e c o r d i n g the maximum and minimum x, y and z v a l u e s . Thus, i t i s produced i n 0(n) time. Freeman and Shapira [FrSh,75] prove Lemma 5.1 which leads 78 to Theorem 5.1 ( a f t e r Boyce et a l [BoyDobDryGui,82]). Lemma 5.1 [FrSh,75,P.4 1 1 ]: The r e c t a n g l e of minimum area e n c l o s i n g a convex polygon has a s i d e c o l l i n e a r with one of the edges of the polygon. Theorem 5.J_: The minimum-area bounding r e c t a n g l e of a convex polygon can be c o n s t r u c t e d i n 0(n) time. Proof: The minimum-area r e c t a n g l e can be found by c o n s t r u c t i n g and t e s t i n g the 0(n) p o s s i b i l i t i e s s a t i s f y i n g Lemma 5'. 1 . T h i s can be in 0(n) time by us i n g the f o l l o w i n g a l g o r i t h m : a) Choose an edge on the polygon and c o n s t r u c t the minimal-area bounding r e c t a n g l e which i n c l u d e s that edge using some p r o j e c t i v e technique such as Sloan [SI,80], With respect to t h i s edge, l e t a, b, and c denote the l e f t m o s t , f a r t h e s t o p p o s i t e , and rightmost v e r t i c e s r e s p e c t i v e l y (see F i g u r e 5.1). Record the three v e r t i c e s a, b, and c d e f i n i n g the other r e c t a n g l e s i d e s . b) C o n s t r u c t the next r e c t a n g l e on the next clockwise edge by ' s l i d i n g ' each of a, b, and c in a clockwise d i r e c t i o n u n t i l each has found i t s maximum in i t s p a r t i c u l a r d i r e c t i o n with r e s p e c t to t h i s base edge. c) Repeat b) f o r a l l edges r e c o r d i n g the minimum-area r e c t a n g l e u n t i l a l l edges have been examined. Q.E.D. 5.1.2 Storage The space r e q u i r e d f o r s t o r i n g the two-dimensional convex h u l l may be l i n e a r i n n. In c o n t r a s t , the bounding r e c t a n g l e s can each be s t o r e d i n constant space by s t o r i n g the four corner p o i n t s d e f i n i n g them. These would be st o r e d as v e r t i c e s f o r the p o l y g o n a l face approximations 79 F i g u r e 5 .1 Mini mum Rectangle C o n s t r u c t ion and as rays f o r the beam approximation. 5.1.3 I n t e r s e c t ion F i r s t note that the i n t e r s e c t i o n s of two bounding r e c t a n g l e s can be c a l c u l a t e d in constant time. Next, c o n s i d e r the problem of doing convex h u l l i n t e r s e c t i o n s . C h a z e l l e and Dobkin [ChazDob,80] were the f i r s t to d e s c r i b e convex body i n t e r s e c t i o n d e t e c t i o n a l g o r i t h m s which operate in s u b l i n e a r time. Dobkin and K i r k p a t r i c k [DobKirk,82] u n i f y and extend t h e i r r e s u l t s by p r e s e n t i n g a g e n e r a l approach to convex i n t e r s e c t i o n s i n two and three-dimensions. The key to both approaches i s the l o c a l i z a t i o n of the i n t e r s e c t i o n t e s t i n g and the p r e p r o c e s s i n g of the convex bodies which f a c i l i t a t e s t h i s l o c a l i z a t i o n . A convex polygon of n p o i n t s can be preprocessed i n t o a sequence of s u c c e s s i v e l y simpler convex approximations in 0(n) time. Dobkin and K i r k p a t r i c k [DobKirk,82] d e s c r i b e two d i f f e r e n t sequence r e p r e s e n t a t i o n s with s i m i l a r p r o p e r t i e s : the inner sequence and the outer sequence. The o r i g i n a l polygon i s the f i r s t element of both sequences. Each subsequent element i s a simpler v e r s i o n of i t s predecessor. The o p e r a t i o n s used to form elements in the two sequences are dual; an element, in the inner sequence i s formed by removing v e r t i c e s while an 81 = or ig ina l P F i g u r e 5.2 Inner Sequence Representat ion element i n the outer sequence i s formed by removing bounding h a l f - s p a c e s . E i t h e r sequence can be c o n s t r u c t e d with 0(n) p r e p r o c e s s i n g and w i l l r e q u i r e 0(n) s t o r a g e . The inner sequence r e p r e s e n t a t ion of a polygon P i s a sequence P,,...,P such that the o r i g i n a l polygon P i s the f i r s t element P, of the inner sequence. Each element P i i s a s m a l l e r s i m p l i f i e d v e r s i o n of i t s predecessor P^  . •, formed by removing a l t e r n a t e v e r t i c e s (see F i g u r e 5.2). The l a s t element of the sequence P^ has a constant number of v e r t i c e s . Each polygon i n the inner sequence s t r i c t l y c o n t a i n s i t s succ e s s o r . T h e r e f o r e an i n t e r s e c t i o n with any member of the sequence i m p l i e s an i n t e r s e c t i o n with the o r i g i n a l polygon. Since a f i x e d f r a c t i o n ( i n f a c t , n e a r l y h a l f ) of the v e r t i c e s are removed from any element to i t s su c c e s s o r , there are 0 ( l o g ( n ) ) elements i n the sequence. The outer sequence r e p r e s e n t a t i o n of a polygon P i s a sequence P,,...,P such t h a t the o r i g i n a l polygon i s the k f i r s t element P, of the outer sequence. Each element P i s a l a r g e r s i m p l i f i e d v e r s i o n of i t s predecessor P^.^ formed by removing a l t e r n a t e bounding h a l f - p l a n e s (see Fig u r e 5.3). The l a s t element of the sequence P has a k constant number of v e r t i c e s and bounding h a l f - p l a n e s . Each polygon i n the outer sequence i s s t r i c t l y c o n t a i n e d by i t s s u c c e s s o r . Therefore a n o n - i n t e r s e c t ion with any member of the sequence i m p l i e s an n o n - i n t e r s e c t i o n with the o r i g i n a l polygon. Again, there are O( l o g ( n ) ) elements in the sequence. Dobkin and K i r k p a t r i c k prove the f o l l o w i n g Theorem from which the c o r o l l a r y f o l l o w s immediately. Theorem 5.2 [DobKirk,82]: Given the inner or outer sequence corresponding to a polygon P of n v e r t i c e s and a l i n e L, we can compute in O(log n) o p e r a t i o n s the i n t e r s e c t i o n of L and P. 83 F i g u r e 5.3 Outer Sequence Representat ion F i g u r e 5 . 4 M o n o t o n e P o l y g o n a l Chains 85 C o r o l l a r y : The i n t e r s e c t i o n of a two-dimensional convex h u l l of n v e r t i c e s with a bounding r e c t a n g l e can be computed i n O(log n) o p e r a t i o n s . Dobkin and K i r k p a t r i c k [DobKirk,82] present a "shadowing" technique which can be used to break the h u l l - h u l l i n t e r s e c t i o n problem i n t o two p a i r s of polygonal chain i n t e r s e c t i o n s (see Fi g u r e 5.4). A monotone polygonal chain (MPC) i s a sequence of v e r t i c e s and edges given i n order of i n c r e a s i n g y - c o o r d i n a t e . The bottom and top edges are extended i n t o s e m i - i n f i n i t e rays. A convex polygon can be d e s c r i b e d as a r i g h t MPC and a l e f t MPC. The i n t e r s e c t i o n of two convex h u l l s can be demonstrated by showing the i n t e r s e c t i o n of the r i g h t MPC of one with the l e f t MPC of the other and v i c e - v e r s a . Note that the use of MPCs can a l s o be used to d e t e c t a s t r i c t l y c o n t a i n i n g i n t e r s e c t i o n . T h i s i s done by n o t i n g where on the polygonal contours the i n t e r s e c t i o n occurs. Lemma 5_.2^  Consider 2 MPCs, P^  and QL, the i t h elements of 2 outer sequences. Say they i n t e r s e c t at a p o i n t d. I f the edge on P c o n t a i n i n g d i s r e p l a c e d by the corresponding edge and i t s neighbours on P't . , then Q i n t e r s e c t s P C - i i f f i t i n t e r s e c t s these edges on F;.,. Proof : C a l l the new edges i n P\_. , x1, x2, and x3 (See F i g u r e 5.5). The endpoints of x1 and x3 not on x2 are p o i n t s i n both Pi and P L . i . C a l l them s and t . The edge replacement we are concerned with i n going from PJ, to Pt . , i s r e a l l y r e p l a c i n g one s e r i e s of edges from s to t with 86 P i F i g u r e 5.5 Lemma 5.2 Diagram another s e r i e s of edges from s to t . We d i s t i n g u i s h 2 cases: i ) s and t are on o p p o s i t e s i d e s of . Then Q{ must i n t e r s e c t the new sequence between s and t . i i ) s and t are on the same s i d e of Q l . Then there are e i t h e r 2 or 0 i n t e r s e c t i o n s . I f there are 0 i n t e r s e c t i o n s then by the c o n v e x i t y of Q;, P j . i and Ql do not i n t e r s e c t (as i n F i g u r e 5.3). Q.E.D. Theorem 5.3: Given 2 convex polygons P and Q of p and q v e r t i c e s r e s p e c t i v e l y represented by t h e i r outer sequences, we can determine a point, i n t h e i r i n t e r s e c t i o n or d e t e c t a n o n - i n t e r s e c t i o n i n at worst 0 ( l o g ( p ) * l o g ( q ) ) o p e r a t i o n s . Proof: As mentioned e a r l i e r , the i n t e r s e c t i o n problem can be r e c a s t as a p a i r of MPC i n t e r s e c t i o n problems. We 87 c o n s i d e r PL and QR. The two convex polygonal chains must i n t e r s e c t twice or not at a l l . In the f o l l o w i n g , we r e f e r to PL as P and QR as Q. The a l g o r i t h m d e s c r i b e d maintains the upper i n t e r s e c t i o n while a l t e r n a t e l y stepping through the P sequence and the Q sequence. C a l l the i n t e r s e c t i o n of P t and Q the po i n t g. We s h a l l proceed by f i r s t f i n d i n g the upper i n t e r s e c t i o n of P c . i and Qi then s i m i l a r l y f i n d i n g the i n t e r s e c t i o n of P L i and Q t . i . Choose the segment of P c o n t a i n i n g g. Replace t h i s segment with the corresponding constant number of segments in P i . 1 . By Lemma 5.2, i f Q i n t e r s e c t s P then Q; must i n t e r s e c t one of these segments. Use the a l g o r i t h m of Theorem 5.2 to determine the i n t e r s e c t i o n of these segments with Q\. C a l l t h i s i n t e r s e c t i o n h. T h i s h i s then the i n t e r s e c t i o n p o i n t of P* t.i and Qi . S i m i l a r l y , use the segment c o n t a i n i n g h in Q to f i n d the i n t e r s e c t i o n between Q;., and P L . i . The i n i t i a l i n t e r s e c t i o n between P, and can be found i n constant time. Each 'step' through the sequence r e q u i r e s O(log(p) + l o g ( q ) ) o p e r a t i o n s . There w i l l be MIN(log(p), l o g ( q ) ) steps to be taken f o r O(log(p) * l o g ( q ) ) o p e r a t i o n s o v e r a l l . Q.E.D. It i s worth noting that C h a z e l l e and Dobkin [ChazDob,80] present a convex polygon i n t e r s e c t i o n d e t e c t i o n a l g o r i t h m which o p e r a t e s ' i n at worst O(log(p+q)) time. T h e i r a l g o r i t h m uses l o c a l i z e d t e s t i n g and w i l l terminate e a r l y i f an i n t e r s e c t i o n i s d e t e c t e d . The outer sequence i n t e r s e c t i o n t e s t i n g w i l l terminate e a r l y i f a n o n - i n t e r s e c t i o n i s d e t e c t e d . I f a n o n - i n t e r s e c t i o n i s more probable than an i n t e r s e c t i o n , then the outer sequence a l g o r i t h m i s p r e f e r a b l e . Thus, the O(log(p) * l o g ( q ) ) n o n - i n t e r s e c t i o n d e t e c t i o n r e s u l t of Theorem 5.3 i s of p r a c t i c a l and t h e o r e t i c a l i n t e r e s t . 8 8 Convex H u l l Bounding R e c t a n g l e c o n s t r u c t i on 0(n) 0(n) s t o r a g e 0(n) c o n s t a n t i n t e r s e c t i on 0( l o g m * 1 og n) 0(1og m) w i t h convex hu11 beam i n t e r s e c t i on w i t h r e c t . w i ndow 0( l o g n) c o n s t a n t Notes: n - number of input p o i n t s h - number of p o i n t s i n convex h u l l m - number of r a y s i n h u l l of beam A l l l o g a r i t h m s a r e base 2. F i g u r e 5.6 2D Approx imat ion Summary A t a b l e summarizing the q u a n t i f i a b l e r e s u l t s of t h i s s e c t i o n appears in F i g u r e 5.6. 5.2 Three-Dimensional Approximation Elements The e n t i t i e s to be wrapped i n an approximation element are three-di m e n s i o n a l c o l l e c t i o n s of p l a n a r f a c e s . Note that i n c o n s t r u c t i n g these approximation elements, i f the faces have 8 9 been approximated by t h e i r two-dimensional convex h u l l s then only those h u l l p o i n t s need be c o n s i d e r e d . Although t h i s does not a f f e c t the asymptotic complexity, i t may l e a d to a simpler implementat i o n . In the f o l l o w i n g d i s c u s s i o n , n r e f e r s to the number of v e r t i c e s of the h i e r a r c h y element t o be approximated and h r e f e r s to the number of h u l l p o i n t s on a three-d i m e n s i o n a l convex h u l l under c o n s i d e r a t i o n . 5.2.1 C o n s t r u c t i o n We f i r s t compare the times f o r c o n s t r u c t i o n of a p o l y h e d r a l h i e r a r c h y element of n p o i n t s . The c o n s t r u c t i o n of the three-dimensional convex h u l l of a set of n p o i n t s can be done in time 0(n l o g n) [PrepHong,77]. T h i s a l g o r i t h m e x p l o i t s the f a c t that separable convex h u l l s can be combined i n l i n e a r time. It uses a d i v i d e and conquer technique to b u i l d the convex h u l l by r e c u r s i v e l y h a l v i n g the point s e t , f i n d i n g the h u l l of each h a l f and combining the r e s u l t s in l i n e a r time. Note that in c o n s t r u c t i n g a h i e r a r c h y of convex h u l l s , the cost of b u i l d i n g the h u l l s can be shared i f the c o n s t i t u e n t elements are l i n e a r l y s e p a r a b l e . The r e c t i l i n e a r bounding box can of course be c o n s t r u c t e d in O(n) time by simply examining each vertex and r e c o r d i n g the maximum and minimum x, y, and z v a l u e s . 9 0 I t seems reasonable to expect a three-dimensional analogue to the Freeman and Shapira r e s u l t [FrSh,75] mentioned in the d i s c u s s i o n of the minimum-area bounding r e c t a n g l e c o n s t r u c t i o n i n the l a s t s e c t i o n . T h i s c o n j e c t u r e might be that the minimum-volume bounding box of a set of p o i n t s has at l e a s t one face which i s coplanar with the three-dimensional convex h u l l d e f i n e d on that p o i n t s e t . T h i s might l e a d to an a l g o r i t h m s i m i l a r to the one presented i n Theorem 5.1. U n f o r t u n a t e l y , a counter-example can be e a s i l y c o n s t r u c t e d (see F i g u r e 5.7). Define a planar r e c t a n g l e (ABCD). Above and below the r e c t a n g l e , p l a c e two edges (EF and GH r e s p e c t i v e l y ) which l i e in two planes which are p a r a l l e l to ABCD. Place them such that t h e i r p r o j e c t i o n s onto the ABCD plane are orthogonal, are both contained w i t h i n ABCD, and i n t e r s e c t . Connect the edges to the r e c t a n g l e forming a s o l i d (as i n Fi g u r e 5.5). F i n a l l y , note that i t i s p o s s i b l e to choose the area of ABCD to be so l a r g e as to for c e the d i s t a n c e between EF and GH to be one of the dimensions of the minimum-volume bounding box. Note that i n such a box EF and GH would l i e on opposite faces and that no faces of t h i s convex polyhedron are coplanar with the bounding box. In a sense, the f a c t that EF and GH l i e in p a r a l l e l planes suggest that taken together they d e f i n e a 'supporting plane' analagous to the 'coplanar face' c o n j e c t u r e . T h i s s u p p o r t i n g plane then c o u l d be d e f i n e d by two opposite edges or a face and 9 1 C D F i g u r e 5 . 7 Bounding Box C o n s t r u c t i o n Counter-Example an o p p o s i t e v e r t e x . A v i s et a l [AvTouBha,8 1] prove t h a t the sequence of d i s t a n c e s d e f i n e d on a convex polygon i s not u n i m o d a l . U s i n g t h i s r e s u l t , i t i s easy t o show t h a t i t i s not p o s s i b l e t o choose an edge .and s e a r c h f o r i t s f a r t h e s t o p p o s i t e edge u s i n g a unimodal s e a r c h t e c h n i q u e . Thus, any c o n s t r u c t i v e approach f o r the minimum-volume bounding box analogous t o the minimum-area bounding r e c t a n g l e 9 2 r e s u l t would have to co n s i d e r p a i r s of edges. Even i f the h p o i n t s and 0(h) edges on the convex h u l l are a v a i l a b l e , each edge might have to be p a i r e d with a f i x e d f r a c t i o n of the t o t a l number of edges of the polyhedron producing 0 ( h 2 ) candidates to t e s t . Each candidate c o u l d be c o n s t r u c t e d i n l i n e a r time producing an 0 ( h 3 ) c o n s t r u c t i o n r e s u l t to determine the minimum-volume bounding box. No b e t t e r c o n s t r u c t i v e method i s r e a d i l y a v a i l a b l e . T h i s r e s u l t may seem i n i t i a l l y s u r p r i s i n g because the bounding box i s a 'cruder' approximation than the convex h u l l . The reason that the same ' d i v i d e and conquer' s t r a t e g y used i n c o n s t r u c t i n g the convex h u l l cannot be used f o r the bounding box i s t h a t s u b r e s u l t s cannot be e a s i l y combined. The minimum-volume bounding box of a given p o i n t set may not p r o p e r l y c o n t a i n the minimum-volume bounding boxes of a l l subsets of that s e t . Note that an approximation to the minimum-volume bounding box can be c o n s t r u c t e d reasonably e f f i c i e n t l y . T h i s can be done by using a h i l l - c l i m b i n g o p t i m i z a t i o n r o u t i n e [Win,7 7 ] to f i n d the t r a n s f o r m a t i o n which minimizes the volume of the r e c t i l i n e a r bounding box. The only drawback to t h i s scheme i s that the o p t i m i z a t i o n r o u t i n e may converge on a l o c a l minimum ra t h e r than the g l o b a l minimum d e s i r e d . Another reasonable approximation to the minimum-volume 0 9 3 bounding box c o u l d be c o n s t r u c t e d using p r i n c i p a l components or p r i n c i p a l axes a n a l y s i s [ B a l l B r o , 8 2 ] . Given a set of p o i n t s i n space, t h i s can be used to f i n d a set of orthogonal b a s i s v e c t o r s which would then d e f i n e an o r i e n t a t i o n f o r the bounding box. These b a s i s v e c t o r s d e f i n e the orthogonal d i r e c t i o n s of maximum v a r i a n c e r a t h e r than the d i r e c t i o n s of absolute maximum v a r i a t i o n . T h i s means that given the o r i e n t a t i o n d e f i n e d by the p r i n c i p a l components, we would s t i l l have to do a l i n e a r sweep through the p o i n t s to d e f i n e the a c t u a l approximation to the minimum volume bounding box. The complexity of these bounding box approximation schemes cannot r e a l l y be compared with those of the other c o n s t r u c t i o n a l g o r i t h m s . These algorit h m s use fundamentally d i f f e r e n t approaches than the ones o u t l i n e d e a r l i e r and no immediate i n s i g h t i s to be gained from t h e i r comparison. 5.2.2 Storage The space r e q u i r e d f o r storage of a minimum-volume bounding box i s constant (the t r a n s f o r m a t i o n matrix and the x, y, z o f f s e t s ) r e g a r d l e s s of the s i z e of the input s e t . The space r e q u i r e d f o r storage of the r e c t i l i n e a r bounding box i s a l s o constant, the minimum and maximum x, y, and z v a l u e s . The space r e q u i r e d f o r storage of the convex h u l l (as h u l l p o i n t s and a s s o c i a t e d edges and faces) may be l i n e a r i n n, the number of input p o i n t s . 9 4 5.2.3 I n t e r s e c t i o n As d i s c u s s e d in the i n t r o d u c t i o n to t h i s c hapter, a beam i s r e a l l y a two-dimensional e n t i t y . T h e r e f o r e to do beam/ approximation element i n t e r s e c t i o n t e s t i n g i t i s s u f f i c i e n t to t e s t f o r two-dimensional i n t e r s e c t i o n s on the a p p r o p r i a t e l y chosen p r o j e c t i o n plane as p r e v i o u s l y d e s c r i b e d . The inner and outer sequences of Dobkin and K i r k p a t r i c k [DobKirk,82], as d e s c r i b e d in the l a s t s e c t i o n , can a l s o be d e f i n e d on polyhedra. In the f o l l o w i n g d i s c u s s i o n , an independent set of v e r t i c e s in a polyhedron i s one i n which no two v e r t i c e s are a d j a c e n t . S i m i l a r l y , an independent set of  bounding h a l f - s p a c e s i n a polyhedron i s one i n which no two h a l f - s p a c e s i n t e r s e c t to form an edge of the polyhedron. The inner sequence r e p r e s e n t a t i o n of a polyhedron P i s a sequence P,,...^ such that the o r i g i n a l polyhedron P i s the f i r s t element P, of the sequence. An element i n the inner sequence Pt i s a smal l e r s i m p l i f i e d v e r s i o n of i t s predecessor P ' L . i , formed by removing a number of low-degree independent v e r t i c e s . At each step a f i x e d f r a c t i o n of the t o t a l number of v e r t i c e s i s removed. The l a s t element P K i s a polyhedron with a constant number of v e r t i c e s and f a c e s . As in the two-dimensional inner sequence, each element s t r i c t l y c o n t a i n s i t s s u ccessor. Thus, an i n t e r s e c t i o n with any element of the sequence guarantees an i n t e r s e c t i o n with the o r i g i n a l (a) v i s v e r t e x t o be removed (b) A f t e r removal, new f a c e s a r e formed F i g u r e 5.8 Removing a V e r t e x 96 polyhedron. Note that in removing a low-degree independent vertex i t may be necessary to form a constant number of new faces d e f i n e d on i t s adjacent v e r t i c e s (see F i g u r e 5.8). The outer sequence r e p r e s e n t a t ion of a polyhedron P i s a sequence P,,...,?^ such that the o r i g i n a l polyhedron P i s the f i r s t element P, of the sequence. An element i n the outer sequence P^ i s a s i m p l i f i e d l a r g e r v e r s i o n of i t s predecessor P [ . i formed by removing a number of low-degree independent bounding h a l f - s p a c e s . At each step, a f i x e d f r a c t i o n of the t o t a l number of bounding h a l f - s p a c e s are removed. The l a s t element of the sequence i s a polyhedron with a constant number of faces and v e r t i c e s . As in the two-dimensional case, each element i s s t r i c t l y c o n tained by i t s successor. Thus a n o n - i n t e r s e c t i o n with any element of the sequence guarantees that there w i l l be no i n t e r s e c t i o n with the o r i g i n a l polyhedron. Each bounding h a l f - s p a c e i s a c o n s t r a i n t d e f i n i n g one polyhedron fa c e . Removing a bounding h a l f - s p a c e i n c o n s t r u c t i n g the outer sequence i s r e l a x i n g a c o n s t r a i n t . The adjacent h a l f - s p a c e s i n t e r s e c t to form a constant number of new v e r t i c e s (See F i g u r e 5.9). In a c t u a l l y c o n s t r u c t i n g an outer sequence, care must be taken to ensure that the removal of a bounding h a l f - s p a c e does not produce an unbounded r e s u l t . I t can be shown that t h i s can always be done such that the simplest element of the sequence w i l l have at most s i x s i d e s . 9 7 w i s r e s u l t i n g vertex when bounding h a l f - s p a c e i s removed. Fi g u r e 5.9 Removing a Bounding Half-Space To d e t e c t beam/element n o n - i n t e r s e c t i o n s , we c o n s i d e r the outer sequence r e p r e s e n t a t i o n of the convex h u l l . The outer sequence of a convex polyhedron i m p l i c i t l y r e p r e s e n t s the outer p o l y g o n a l sequences of a l l p r o j e c t i o n s of that polyhedron. Thus, to perform a n o n - i n t e r s e c t i o n d e t e c t i o n using the outer sequence of a polyhedron, we can use a v a r i a n t of the two-dimensional a l g o r i t h m d e s c r i b e d in Theorem 5 . 3 of the l a s t s e c t i o n . 98 The v a r i a t i o n a r i s e s i n that r e p l a c i n g a removed bounding h a l f - p l a n e of a polygon i s not e x a c t l y the same as r e p l a c i n g a bounding h a l f - s p a c e of a polyhedron and reforming the p r o j e c t i o n (see Fi g u r e 5.9). There are new v e r t i c e s formed when a bounding h a l f - s p a c e i s removed. T h i s means t h a t i n moving from one element of the sequence to i t s predecessor, a constant l e n g t h sequence of p r o j e c t i o n v e r t i c e s i s r e p l a c e d by another constant length sequence. The next lemma which p a r a l l e l s Lemma 5.2 deals with t h i s v a r i a t i o n . Lemma 5.3_: Given a p r o j e c t i o n plane A and a p r o j e c t i o n d i r e c t i o n d, con s i d e r 2 MPCs, Q*L , the i t h element of a pol y g o n a l outer sequence, and Pi. , the p r o j e c t i o n of the i t h element of a p o l y h e d r a l outer sequence onto A in the d i r e c t i o n d. Say they i n t e r s e c t at a p o i n t d. If the edge sequence on P: c o n t a i n i n g d i s r e p l a c e d by the corresp o n d i n g edge sequence on P £ . i then Q*L i n t e r s e c t s P L . i i f f i t i n t e r s e c t s these edges on P \.,. Proof : Note that the endpoints of the two edge sequences are the same i n P;. and Pi . , . If these are r e f e r r e d to as s and t, the same argument as i n Lemma 5.2 can be a p p l i e d . Q.E.D. Theorem 5.4: Given a p r o j e c t i o n plane A and a p r o j e c t i o n d i r e c t i o n d, con s i d e r a l i n e L l y i n g i n A and a convex polyhedron Q of q p o i n t s represented by i t s outer sequence. In O(l o g ( q ) ) o p e r a t i o n s i t i s p o s s i b l e to f i n d an i n t e r s e c t i o n p o i n t or detect a n o n - i n t e r s e c t ion between L and p r o j e c t i o n of Q onto A in the d i r e c t i o n d. Proof: Making the a p p r o p r i a t e s u b s t i t u t i o n s i n Theorem 5.2 9 9 [DobKirk,82] f o r the r e s u l t i n Lemma 5.3, the same argument can be a p p l i e d . Q.E.D. C o r o l l a r y : The i n t e r s e c t i o n of a bounding r e c t a n g l e and the p r o j e c t i o n of a three-dimensional convex polyhedron of n v e r t i c e s can be computed in O( l o g ( n ) ) o p e r a t i o n s . Theorem ^ ._5: Given a convex polygon P of p p o i n t s and a convex polyhedron Q of q p o i n t s along with t h e i r outer sequences, then i n O(log(p) * log(q')') o p e r a t i o n s i t i s p o s s i b l e to f i n d an i n t e r s e c t i o n p o i n t or d e t e c t a n o n - i n t e r s e c t i o n between P and the coplanar p r o j e c t i o n of Q. Proof ; Making the a p p r o p r i a t e s u b s t i t u t i o n s i n Theorem 5.3 f o r the r e s u l t i n Lemma 5.3, the same argument can be a p p l i e d . Q.E.D. The i n t e r s e c t i o n of the convex h u l l approximation of a beam with a bounding box can be de t e c t e d by p r o j e c t i n g the 8 p o i n t s d e f i n i n g the box onto a backplane and using the r e s u l t of Theorem 5.2. If the convex h u l l has m v e r t i c e s then t h i s can be done i n O(log(m)) o p e r a t i o n s . Note that the i n t e r s e c t i o n of a bounding r e c t a n g l e and the p r o j e c t i o n of a bounding box can be performed i n constant time. To conclude t h i s s e c t i o n , we present a r e s u l t due to Dobkin and K i r k p a t r i c k [DobKirk,82] r e f e r e n c e d i n the i n t e r v a l s o r t i n g s e c t i o n of Chapter 4: 100 Convex Hul1 Rect i 1 i near Bounding Box Minimum Volume Bounding Box c o n s t r u c t i o n 0(n l o g n) 0(n) 3 0(h ) s t o r a g e 0(n) c o n s t a n t c o n s t a n t i n t e r s e c t i o n w i t h convex h u l l beam 0(log m * lo g n) 0(log m) 0(log m) i n t e r s e c t i on w i t h r e c t . w i ndow 0(log n) c o n s t a n t c o n s t a n t Notes: n - number of input p o i n t s h - number of p o i n t s i n convex h u l l m - number of r a y s i n h u l l of beam A l l l o g a r i t h m s a r e base 2. F i g u r e 5.10 3D Approximat ion Summary Lemma 5.4: Let p- t(d) be the maximal vertex of P; i n the d i r e c t i o n d where P; i s the i t h member of an inner or outer h i e r a r c h y for a polygon or polyhedron. Then, e i t h e r p^.,(d) = p t-(d) or p;.,(d) i s one of the new neighbours of p; (d) i n P'L.,. Theorem 5.6: The maximum vertex i n a given d i r e c t i o n d of a polygon or polyhedron P with p p o i n t s can be d e r i v e d from the inner or outer r e p r e s e n t a t i o n i n O(log p) o p e r a t i o n s . Given a thr e e - d i m e n s i o n a l convex h u l l of h p o i n t s , the maximum po i n t i n a given d i r e c t i o n can be d e r i v e d from an inner or outer sequence i n O ( l o g ( h ) ) o p e r a t i o n s . The maximum 101 bounding box p o i n t in a given d i r e c t i o n ' can be determined i n constant time by t e s t i n g a l l (8) p o s s i b i l i t i e s . The t a b l e i n F i g u r e 5.10 summarizes the q u a n t i f i a b l e r e s u l t s of t h i s s e c t i o n . The f i n a l s e c t i o n d i s c u s s e s s e v e r a l of these r e s u l t s . 5.3 General Comparisons We can now d i s c u s s some gen e r a l comparisons as to the r e l a t i v e m e r i t s of the v a r i o u s approximation c a n d i a t e s . Our d i s c u s s i o n w i l l c oncentrate on the three-dimensional approximations: convex h u l l , r e c t i l i n e a r bounding box and minimum-volume bounding box. The n o t i o n of ' t i g h t n e s s of f i t ' d e f i n e s an o r d e r i n g on approximation elements based on t h e i r r e s p e c t i v e volumes on a given p o i n t s e t . Let CH denote the convex h u l l , MVBB denote the minimum-volume bounding box, and RBB denote the r e c t i l i n e a r bounding box. Given a set X of p o i n t s i n three-space: volume(CH(X)) < volume(MVBB(X)) < volume(RBB(X)). The r e c t i l i n e a r bounding- box w i l l , i n g e n e r a l , form the worst f i t of X because of i t s a r b i t r a r y dependence on a x i s o r i e n t a t i o n . The minimum-volume bounding box i s an improvement because of i t s a x i s independence but may s t i l l d e f i n e much wasted space. The convex h u l l i s the most compact 1 0 2 approximation because i t i s (by d e f i n i t i o n ) the best convex f i t p o s s i b l e . Since the convex h u l l i s a ' t i g h t e r ' f i t than e i t h e r of the bounding boxes, a beam i n t e r s e c t i n g the convex h u l l i s more l i k e l y to i n t e r s e c t the u n d e r l y i n g s t r u c t u r e than a beam i n t e r s e c t i n g one of the bounding boxes. Tig h t n e s s of f i t i s an important c o n s i d e r a t i o n which a f f e c t s not only i n t e r s e c t i o n s but a l s o the a b i l i t y to determine an' ab s o l u t e r e l a t i v e ' ordering- of component's q u i c k l y . The expansion r o u t i n e d e s c r i b e d i n Chapter 4 makes use of separable sequences of components. If t h i s s e p a r a b i l i t y cannot be e a s i l y performed then the b e n e f i t of the h i e r a r c h i c a l s t r u c t u r e i n c o n t r o l l i n g the amount of in f o r m a t i o n under c o n s i d e r a t i o n at any one time i s l o s t . The r e c t i l i n e a r bounding box i s the e a s i e s t of the three to c o n s t r u c t . The convex h u l l seems to be e a s i e r to compute ( e x a c t l y ) than the minimum-volume bounding box. Another advantage of convex h u l l s i s that h u l l s of s e v e r a l s t r u c t u r e s can be e a s i l y aggregated i n t o one l a r g e r c o n t a i n i n g h u l l . Because the minimum-volume bounding box does not p r o p e r l y c o n t a i n a l l minimum-volume bounding boxes d e f i n e d on i t s subsets, t h i s type of aggregation cannot be done f o r bounding boxes. T h i s i s an important c o n s i d e r a t i o n when c o n s t r u c t i n g a h i e r a r c h y of such approximations. The bounding box approximation can be s t o r e d in constant 103 space r e g a r d l e s s of the complexity of the u n d e r l y i n g s t r u c t u r e while the storage of the convex h u l l grows i n d i r e c t p r o p o r t i o n to t h i s complexity. A bounding box a l s o admits to a more e f f i c i e n t i n t e r s e c t i o n a l g o r i t h m . As noted by Rubin and Whitted [RubWhit,80], the s t a n d a r d i z a t i o n of the bounding box data s t r u c t u r e allows the p o s s i b i l i t y of a hardware implementation of the bounding box i n t e r s e c t i o n . Our a p p l i c a t i o n i s space c o n s t r a i n e d , due t o the t y p i c a l l y l a r g e nature of a r c h i t e c t u r a l databases. I t i s a l s o time c o n s t r a i n e d due to the p o t e n t i a l l y e x p o n e n t i a l growth of beam r e f l e c t i o n s . There i s no 'best' approximation scheme over a l l p o s s i b l e p o i n t sets because each approximation element has i t s own r e l a t i v e m e r i t s and w i l l perform b e t t e r on some p o i n t s e t s than the o t h e r s . 5.4 Hybrid H i e r a r c h i e s Some of the b e n e f i t s of both would be obtained by using a h y b r i d h i e r a r c h y . T h i s i s a scheme i n which v a r i o u s approximation elements i n c l u d i n g minimum-volume bounding boxes, th r e e - d i m e n s i o n a l convex h u l l s , and others may be used as h i e r a r c h y elements. One way of s t r u c t u r i n g t h i s h y b r i d c o u l d use bounding boxes near the root where the space savings w i l l be the g r e a t e s t and spurious i n t e r s e c t i o n s , although more probable, 1 04 are i n e x p e n s i v e . Convex h u l l s c o u l d be used f u r t h e r down i n the h i e r a r c h y for t h e i r ' t i g h t e r ' f i t approximation to encourage s e p a r a b i l i t y i n doing i n t e r v a l s o r t i n g and to decrease the amount of work passed to the c l i p p i n g r o u t i n e s . A more systematic and e f f i c i e n t use of a h y b r i d h i e r a r c h y i s to l e t the notion of ' t i g h t n e s s of f i t ' determine which bounding s t r u c t u r e was to be used f o r a p a r t i c u l a r h i e r a r c h y element. T h i s would be i n c o r p o r a t e d by c a l c u l a t i n g the- convex h u l l and minimum-volume bounding box f o r the element to be approximated and c a l c u l a t i n g t h e i r r e s p e c t i v e volumes [LeeReq,80] [LeeReq,82a] [LeeReq,82b]. If the bounding box volume was w i t h i n some f a c t o r of the convex h u l l volume, then the bounding box would be used. T h i s would p r o v i d e us with the b e n e f i t s of the s i m p l i c i t y of the bounding box f o r an o b j e c t that was e s s e n t i a l l y r e c t i l i n e a r . The d i s c u s s i o n of the beam/convex h u l l i n t e r s e c t i o n i n S e c t i o n 5.2.3 i m p l i c i t l y presented the b a s i s f o r another h y b r i d scheme. The elements of the outer sequence r e p r e s e n t a t i o n comprise a f u l l spectrum of f i t s . The f i r s t element i s a polyhedron d e f i n e d on a constant number of v e r t i c e s p r o v i d i n g the s i m p l i c i t y of the bounding box. The l a s t element of the sequence i s the convex h u l l . Any one of the elements in t h i s sequence c o u l d be chosen as the approximation element a c c o r d i n g to how well i t f i t s the u n d e r l y i n g s t r u c t u r e . 1 05 In b u i l d i n g an approximation element, the convex h u l l i s f i r s t c o n s t r u c t e d and then the outer sequence r e p r e s e n t a t i o n of S e c t i o n 5.2.3. i s added. The volume of each element of the sequence can be compared with the volume of the convex h u l l . It i s then easy to t e s t at which element Q i n the sequence the volume i n c r e a s e s past a pre-determined f a c t o r of the convex h u l l volume. A l l elements of the sequence past Q can be d i s c a r d e d and t h e i r storage r e c l a i m e d . The r e s t of the sequence can be r e t a i n e d f o r performing the i n t e r s e c t i o n t e s t i n g as d e s c r i b e d in Theorem 5.4. A s y m p t o t i c a l l y , a h i e r a r c h y of 'truncated' outer sequence r e p r e s e n t a t i o n s takes no longer to b u i l d than the h i e r a r c h y of convex h u l l s . One of i t s advantages i s that the h i e r a r c h y element used, and i t s storage, i s r e l a t e d d i r e c t l y to how w e l l i t f i t s the u n d e r l y i n g s t r u c t u r e being approximated. Since the outer sequence r e p r e s e n t a t i o n of the chosen element i s a v a i l a b l e , the e f f i c i e n t n o n - i n t e r s e c t ion d e t e c t i o n d e s c r i b e d e a r l i e r can be performed. T h i s advantage i s that a crude i n i t i a l t e s t can e l i m i n a t e i t from f u r t h e r c o n s i d e r a t i o n and the amount of e f f o r t expended in performing the i n t e r s e c t i o n only i n c r e a s e s when the chance of a true i n t e r s e c t i o n i n c r e a s e s . T h i s h y b r i d scheme a l s o has the advantage that i t can be a p p l i e d to two dimensions; a polygonal face c o u l d be represented by i t s most a p p r o p r i a t e outer sequence element. 1 06 CHAPTER 6: Summary, Con c l u s i o n s and Further Work 6.1 Summary T h i s t h e s i s presents a h i e r a r c h i c a l approach to the hidden l i n e / s u r f a c e problem which uses approximation elements to package p o r t i o n s of the environment. V a r i o u s ways of c o n s t r u c t i n g and using such a h i e r a r c h i c a l r e p r e s e n t a t i o n are proposed and d i s c u s s e d . D i f f e r e n t convex approximation s t r u c t u r e s are examined as can d i d a t e s f o r elements i n t h i s h i e r a r c h y . We present our a p p l i c a t i o n area of 'computational a c o u s t i c s ' and motivate our re s e a r c h by r e l a t i n g the problems of hidden l i n e / s u r f a c e e l i m i n a t i o n to the problems of a c o u s t i c s modeling beam-tracing. We g e n e r a l i z e the notion of a viewing window to i n c l u d e the standard h i d d e n - l i n e viewing p o r t , -a p i x e l c a l c u l a t i o n in a hid d e n - s u r f a c e r a s t e r scan, and a sound beam i n the a c o u s t i c s modeling. We d i s c u s s the sequence of t r a n s f o r m a t i o n s necessary to preprocess an i n i t i a l r e p r e s e n t a t i o n i n t o the h i e r a r c h y d e s c r i b e d . I t i s shown how d i f f e r e n t i n i t i a l r e p r e s e n t a t i o n s can be transformed i n t o the boundary r e p r e s e n t a t i o n and the a s s o c i a t e d face adjacency i n f o r m a t i o n . We a l s o propose h e u r i s t i c s to use to segment a u t o m a t i c a l l y domain info r m a t i o n fo r v a r i o u s a p p l i c a t i o n areas. 1 07 Algorithms are proposed which show how the approximation h i e r a r c h y can be used to so l v e e f f i c i e n t l y the i n t e r s e c t i o n , s o r t i n g and c l i p p i n g subproblems of the hidden l i n e / s u r f a c e problem. The two-dimensional convex h u l l and the minimum-area bounding r e c t a n g l e are examined as candidates f o r plan a r approximations of environment faces and beam (viewing window) polygons. The three-dimensional convex h u l l , the r e c t i l i n e a r bounding box, and the minimum-volume bounding box are examined as candidates f o r the non-planar elements of the h i e r a r c h y . The c o m p l e x i t i e s of c o n s t r u c t i n g , s t o r i n g and d e t e c t i n g the i n t e r s e c t i o n of these candidates are presented and compared. 6.2 Con c l u s i o n s The h i e r a r c h i c a l r e p r e s e n t a t i o n presented i s u s e f u l f o r s e v e r a l a p p l i c a t i o n s in which i t i s d e s i r a b l e to l i m i t the amount of i n f o r m a t i o n under c o n s i d e r a t i o n . The r e p r e s e n t a t i o n was designed to provide e f f i c i e n t techniques f o r performing a c o u s t i c s beam t r a c i n g , but i t has more gen e r a l a p p l i c a b i l i t y . Although t h i s can only be confirmed with an implementation, i t seems that t h i s r e p r e s e n t a t i o n i s as e a s i l y used f o r the hidden surface e l i m i n a t i o n problem as f o r the a c o u s t i c s beam t r a c i n g problem. T h i s seems evident because the proposed a l g o r i t h m s provide polygonal output which can be used f o r g r a p h i c a l d i s p l a y or genera t i o n of sound r e f l e c t i o n s . 108 The h i e r a r c h y d e f i n i t i o n i s g e n e r a l enough to i n c l u d e many d i f f e r e n t a p p l i c a t i o n areas. For example, the s t r u c t u r e s and a l g o r i t h m s d e s c r i b e d c o u l d be used with only s l i g h t m o d i f i c a t i o n to v e r i f y a proposed path f o r a robot on wheels. The path can be decomposed i n t o a number of e x t r u s i o n s or beams. The a l g o r i t h m s presented can then be used to q u i c k l y determine whether or not any p o r t i o n of the environment i n t e r s e c t s any p o r t i o n of the proposed path. The t r a n s f o r m a t i o n s necessary to preprocess a given environment d e s c r i p t i o n i n t o an approximation h i e r a r c h y are w e l l - d e f i n e d and t r a c t a b l e . It i s u n l i k e l y that any domain independent p r e p r o c e s s i n g can be d e f i n e d to t r a n s f o r m a l l input i n t o a segmented h i e r a r c h y . Domain dependent h e u r i s t i c s , such as the ones proposed in Chapter 3 w i l l be necessary to o b t a i n a good segmentation f o r input to the packaging r o u t i n e s . The a l g o r i t h m s presented can e x p l o i t the h i e r a r c h i c a l s t r u c t u r e of our r e p r e s e n t a t i o n and can make use of recent r e s u l t s i n computational geometry to do so e f f i c i e n t l y . The s t r u c t u r e of the a l g o r i t h m s i s such that many computations can be done independently, suggesting the p o s s i b i l i t y of a p a r a l l e l implementation of the window p r o c e s s i n g . Once the h i e r a r c h y i s c o n s t r u c t e d , none of the a l g o r i t h m s modify i t . Thus, for example, the r e c u r s i v e c a l l s to handle passby beams co u l d set up p a r a l l e l processes f o r that purpose. 109 The h i e r a r c h i c a l s t r u c t u r e can use d i f f e r e n t convex p o l y h e d r a l a p p r o x i m a t i o n s as el e m e n t s . There a r e no a v a i l a b l e c a n d i d a t e s which a re b e s t o v e r a l l i n terms of c o n s t r u c t i o n , s t o r a g e and i n t e r s e c t i o n c o s t s . Thus, a h y b r i d h i e r a r c h y can be used which w i l l i n c o r p o r a t e d i f f e r e n t a p p r o x i m a t i o n s t r u c t u r e s as h i e r a r c h y elements a t d i f f e r e n t p l a c e s i n the h i e r a r c h y a c c o r d i n g t o the s t r u c t u r e ' s s u i t a b i l i t y . 6 . 3 F u r t h e r Work T h i s t h e s i s has been i n many r e s p e c t s an i n t e r d i s c i p l i n a r y study of the hidden l i n e / s u r f a c e problem and i t s a c o u s t i c s c o u n t e r p a r t . The s u g g e s t i o n s f o r f u r t h e r work must i n c l u d e the q u e s t i o n s r a i s e d i n each of the d i s c i p l i n e s of g r a p h i c s , g e o m e t r i c m o d e l i n g and computer-aided d e s i g n , c o m p u t a t i o n a l geometry, and c o m p u t a t i o n a l a c o u s t i c s . 6 . 3 . 1 G r a p h i c s Some r e l a t e d f u r t h e r work i n g r a p h i c s would be t o examine the use of h i e r a r c h i e s t o p r o v i d e p o l y g o n a l o u t p u t as i n p u t t o 'batched' s h a d i n g , shadowing, t r a n s p a r e n c y , and r e f l e c t i v e s u r f a c e p r o c e s s i n g . Most h i d d e n - s u r f a c e s h a d i n g a l g o r i t h m s n o r m a l l y work on a r a s t e r scan p i x e l c a l c u l a t i o n [NewSpr,79]. I f the v i s i b l e p o l y g o n a l s u r f a c e s a r e i d e n t i f i e d b e f o r e hand then a s c a n - l i n e 1 1 0 c o n v e r s i o n c o u l d be p e r f o r m e d on them, c a l c u l a t i n g t h e s h a d i n g v a l u e f o r e a c h p i x e l . T h i s " c o u l d be t h o u g h t o f a s ' b a t c h i n g ' t h e h i d d e n - s u r f a c e e l i m i n a t i o n . Shadows, a s n o t e d by [ W e i l A t h , 7 7 ] , c o u l d e a s i l y be i n c o r p o r a t e d by p e r f o r m i n g t h e h i d d e n - l i n e e l i m i n a t i o n u s i n g t h e l i g h t s o u r c e a s t h e v i e w i n g p o s i t i o n . The v i s i b l e p o l y g o n a l s u r f a c e s w o u l d t h e n be t h e i l l u m i n a t e d o n e s . T r a n s p a r e n c y e f f e c t s c o u l d be i n c o r p o r a t e d ' by c o n t i n u i n g a beam a s a p a s s b y a f t e r i t had h i t a t r a n s p a r e n t s u r f a c e . R e f l e c t i v e s u r f a c e s a r e d e a l t w i t h e x a c t l y a s a c o u s t i c s s o u n d beams a r e . The r e f l e c t i v e s u r f a c e i s u s e d t o d i s p l a y t h e o u t p u t o f t h e r e f l e c t e d beam f r o m t h e image s o u r c e . The h i e r a r c h i c a l s t r u c t u r e c o u l d be i n c o r p o r a t e d i n t o a n i m a t i o n . T h i s c o u l d be done by m o v i n g t h e a p p r o p r i a t e a p p r o x i m a t i o n e l e m e n t w h e n e v e r a f i g u r e w i t h i n i t moved. As l o n g a s t h e c o n t a i n e d o b j e c t s d i d n o t c h a n g e s h a p e t h e c o n t a i n i n g a p p r o x i m a t i o n w o u l d n o t h a v e t o be r e c o m p u t e d . F i n a l l y , f u r t h e r p r o c e s s i n g c o u l d be i n c o r p o r a t e d t o p r e c o m p u t e f a c e p r i o r i t i e s [ S u S p r S c h u , 7 4 ] t o s i m p l i f y t h e c l i p p i n g . Then a g r o u p o f f a c e s w i t h i n a beam c o u l d be o r d e r e d on t h e b a s i s o f t h e i r p r i o r i t y a n d t h e f a c e s c o u l d be c l i p p e d o u t o f t h e beam one a t a t i m e . 1 1 1 6.3.2 Geometric Modeling and Computer-Aided Design The a p p l i c a t i o n area which we have been most c l o s e l y a s s o c i a t e d with through our work i s that of Computer-Aided A r c h i t e c t u r a l Design. T h i s subject area generates i n t e r e s t i n g problems for many d i s c i p l i n e s . For example, a p a r t i c u l a r b u i l d i n g design w i l l be developed as a database of i n f o r m a t i o n . T h i s database might then have the approximation s t r u c t u r e which we have described' superimposed upon i t . The nature of the design process i s dynamic; t h e r e f o r e , the database w i l l almost c e r t a i n l y have to be m o d i f i e d . Under what circumstances can the h i e r a r c h i c a l approximation s t r u c t u r e corresponding to the design database be m o d i f i e d to e f f e c t the e d i t e d change r a t h e r than being recomputed? How can such e d i t i n g be e f f i c i e n t l y i n c o r p o r a t e d ? In the more general f i e l d of Computer-Aided Design, only r e c e n t l y have d i f f e r e n t r e p r e s e n t a t i o n schemes been c a t e g o r i z e d and compared [Req,80]. More ex t e n s i v e work i s needed in examining d i f f e r e n t r e p r e s e n t a t i o n s f o r r e p r e s e n t a t i o n a l adequacy, developing methods of e x t r a c t i n g p r o p e r t i e s from d i f f e r e n t r e p r e s e n t a t i o n s [LeeReq,82a] [LeeReq,82b], and d e v e l o p i n g t r a n s f o r m a t i o n s between e q u i v a l e n t r e p r e s e n t a t i o n s . 1 12 6.3.3 Computational Geometry Furth e r work i s needed on i n t e r s e c t i o n and n o n - i n t e r s e c t i o n d e t e c t i o n for v a r i o u s s t r u c t u r e s . Are the inner and outer sequence r e p r e s e n t a t i o n s [DobKirk,82] powerful enough to provide a l g o r i t h m s to match the best-known i n t e r s e c t i o n d e t e c t i o n r e s u l t s ? The techniques of computational complexity and the t o o l s of computational geometry can provide important c o n t r i b u t i o n s in comparing and improving geometric p r o c e s s i n g i n many a p p l i c a t i o n areas. For example, the K i r k p a t r i c k [Kirk,80] a l g o r i t h m f o r doing p o i n t l o c a t i o n in planar s u b d i v i s i o n s can be used to maintain the polygon comparison r e p r e s e n t a t i o n as d e s c r i b e d i n Chapter 4. This, search s t r a t e g y can a l s o be used to perform scan-conversion of a planar s u b d i v i s i o n r e p r e s e n t i n g a group of polygonal s u r f a c e s to be d i s p l a y e d . The theory of r e p r e s e n t a t i o n schemes being developed i n geometric modeling [Req,80] can b e n e f i t from r i g o r o u s comparison of storage and p r o c e s s i n g c o s t s . The d i s c o v e r y and a p p l i c a t i o n of e f f i c i e n t geometric a l g o r i t h m s f o r p a r t i c u l a r r e p r e s e n t a t i o n s can i n f l u e n c e the c h o i c e of r e p r e s e n t a t i o n s and can make r e p r e s e n t a t i o n c o n v e r s i o n more a t t r a c t i v e . 1 13 6.3.4 Computat i o n a l Acoust i e s Our work w i l l c ontinue in implementing the h i e r a r c h i c a l schemes d e s c r i b e d here and i n c o r p o r a t i n g the r e s u l t s i n t o our e x i s t i n g a c o u s t i c s modeling system [WalDad,82]. The adequacy of our model w i l l be t e s t e d by modeling e x i s t i n g rooms and comparing the s i m u l a t i o n r e s u l t s with a c t u a l room measurements. 1 1 4 References [AhHopUll, 74] Aho, A.V., Hopcroft, J.E., & Ullman, J.D. The Design and A n a l y s i s of Computer Algorithms, Addison-Wesley, 1974. [AvTouBha, 81] A v i s , D., T o u s s a i n t , G.T., & Bhattacharya, B.K. "On the M u l t i - M o d a l i t y of D i s t a n c e s i n Convex Polygons", M c G i l l U n i v e r s i t y T e c h n i c a l Report No. SOCS 81.6, February, 1981. [BaEaHen, 77] Baer, A., Eastman, C , & Henrion, M. "A Survey of Geometric Modeling", I n s t i t u t e of P h y s i c a l Planning Research Report No. 66, Carnegie-Mellon U n i v e r s i t y , P i t t s b u r g h , March, 1977. [BaEaHen, 79] Baer, A., Eastman, C , & Henrion, M. "Geometric Modeling: A Survey" CAD 11, No. 5, 1979, pp.253-272. [ B a l l B r o , 82] B a l l a r d , D.H., & Brown, CM. Computer V i s i o n , P r e n t i c e - H a l l , 1982. [BoyDobDryGui, 82] Boyce, J.E., Dobkin, D.P., Drysdal e , R.L., & Guibas, L . J . "F i n d i n g Extremal Polygons", Fourteenth ACM Symposium on the Theory of Computation, 1982, pp.282-289. [ChazDob, 80] C h a z e l l e , B., & Dobkin, D. "Detection i s E a s i e r Than Computation", Proc. ACM Symposium on Theory of Computing, Los Angeles, May 1980, pp.146-153. [Cl,. 76] C l a r k , J.H. " H i e r a r c h i c a l Geometric Models f o r V i s i b l e Surface A l g o r i t h m s " , CACM 19, No. 10, 1976, pp.547-554. [DadKirkWal, 82] Dadoun, N., K i r k p a t r i c k , D.C, & Walsh, J.P. " H i e r a r c h i c a l Approaches to Hidden Surface I n t e r s e c t i o n T e s t i n g " , Proceedings Graphics I n t e r f a c e 82, NCGA, Toronto, May, 1982. [DobKirk, 82] Dobkin, D.P., & K i r k p a t r i c k , D.K. "Fast D e t e c t i o n of P o l y h e d r a l I n t e r s e c t i o n s " , Proc. of the 9th I n t e r n a t i o n a l Colloquium on Automata, Languages and Programming, J u l y , 1982. [DudaHart, 72] Duda, R.O., & Hart, P.E. "Use of the Hough Transformation to Detect L i n e s and Curves i n P i c t u r e s " , CACM 15, No. 1, January, 1972, pp.11-15. 1 15 [Ea, 77] Eastman, C. "The Concise S t r u c t u r i n g of Geometric Data f o r CAD" i n Data S t r u c t u r e s , Computer Graphics and P a t t e r n  R e c o g n i t i o n , F~ K l i n g e r (ed.T^ Academic, New York, 1977, pp.31-57. [Ea, 80a] Eastman, C. "A Prototype I n t e g r a t e d B u i l d i n g Model", I n s t i t u t e of B u i l d i n g Science Research Report No. 3, Carnegie-Mellon U n i v e r s i t y , January, 1980. [Ea, 80b] Eastman, C. "System F a c i l i t i e s f o r CAD Databases", I n s t i t u t e of B u i l d i n g Science, Carnegie-Mellon U n i v e r s i t y in CACM January, 1980. [EaHen, 77] Eastman, C , & Henrion, M. "GLIDE: A Language f o r Design Information Systems", Proc. SIGGRAPH, Computer Graphics 11, No. 2, Summer 1977, pp.24-33. [ E a L i , 75] Eastman, C , & L i v i d i n i , J . " S p a t i a l Search", I n s t i t u t e of P h y s i c a l Planning Research Report No. 55, Carnegie-Mellon U n i v e r s i t y , P i t t s b u r g h , May, 1975. [ E a L i S t , 75] Eastman, C , L i v i d i n i , J . , & Stoker, D. "A Database f o r Designing Large P h y s i c a l Systems", N a t i o n a l Computer Conference, 1975, pp.603-611. [EaTh, 79] Eastman, C , & Thornton, R. "A Report on the GLIDE2 Language D e f i n i t i o n " , P r e l i m i n a r y D r a f t , I n s t i t u t e of P h y s i c a l Planning Research Report, Carnegie-Mellon U n i v e r s i t y , S p r i n g , 1979. [FolVan, 82] F o l e y , J.D., & Van Dam, A. Fundamentals of I n t e r a c t i v e  Computer Graphics , Addison-Wesley, 1982. [FourFuCarp, 82] F o u r n i e r , A., F u s s e l l , D., & Carpenter, L. "Computer Renderings of S t o c h a s t i c Models", CACM V o l . 25, No. 6, June, 1982, pp.371-384. [FowLit, 79] Fowler, R.J., & L i t t l e , J . J . "Automatic E x t r a c t i o n of I r r e g u l a r Network D i g i t a l T e r r a i n Models", in Proc. SIGGRAPH, Computer Graphics 13, No. 2, August 1979, pp.199-207. 1 1 6 [FrSh, 75] Freeman, H. & Shapira, R% "Determining the 1 Minimum-Area Encasing Rectangle f o r an A r b i t r a r y Closed Curve", CACM V o l . 18, No. 7, J u l y , 1975, pp.409-413. [GraYao, 81] Graham, R.L., & Yao, F.F., " F i n d i n g the Convex H u l l of a Simple Polygon", S t a n f o r d T e c h n i c a l Report No. STAN-CS-81-887, November 1981. [GarJoPrepTar, 78] Garey, M.R., Johnson, D.S., Prep a r a t a , F.P., & T a r j a n , R.E. " T r i a n g u l a t i n g a Simple Polygon", Information P r o c e s s i n g L e t t e r s , V o l . 7, No. 4, June, 1978, pp.175-179. [ R e l l , 58] K e l l e r , J.B. "A Geometrical' Theory of' D i f f r a c t i o n " , i n the American Mathematical S o c i e t y , Proceedings of Symposia i n  A p p l i e d Mathematies, Volume 8: C a l c u l u s of V a r i a t i o n s and  I t s A p p l i c a t i o n s , L.M. Graves (ed.), McGraw-Hill, New York, f o r The American Mathematical S o c i e t y , Providence, 1958. [ K i r k , 81] K i r k p a t r i c k , D.K. "Optimal Search i n Planar S u b d i v i s i o n s " , UBC T e c h n i c a l Report 81-13, 1981. [KrokStrSor, 68] Krokstad, A., Strom, S., & S o r s d a l , S. " C a l c u l a t i n g the A c o u s t i c a l Room Response by the Use of a Ray-Tracing Technique", J . Sound & V i b r a t i o n 8, 1968, pp.1 18-125. [LeeReq, 80] Lee, Y.T., & Requicha, A.A.G. "Algorithms f o r Computing the Volume and Other I n t e g r a l P r o p e r t i e s of S o l i d O b j e c t s " , Production Automation T e c h n i c a l Report No. TM-35, U n i v e r s i t y of Rochester, February, 1980. [LeeReq, 82a] Lee, Y.T., & Requicha, A.A.G. "Algorithms f o r Computing the Volume and Other I n t e g r a l P r o p e r t i e s of S o l i d s . I. Known Methods and Open Issues", CACM V o l . 25, No. 9, September, 1982, pp. 635-641. [LeeReq, 82b] Lee, Y.T., & Requicha, A.A.G. "Algorithms f o r Computing the Volume and Other I n t e g r a l P r o p e r t i e s of S o l i d s . I I . A Family of Algorithms Based on Repres e n t a t i o n Conversion and C e l l u l a r Approximation", CACM V o l . 25, No. 9, September, 1982, pp. 642-650. [MulPrep, 78] M u l l e r , D.E., & Preparata, F.P. " F i n d i n g the I n t e r s e c t i o n of Two Convex Polyhedra", T e c h n i c a l Report, U n i v e r s i t y of 1 1 7 I l l i n o i s , October, 1978. [NewSpr, 79] Newman, W.M., & S p r o u l l , R.F. " P r i n c i p l e s of I n t e r a c t i v e  Computer Graphics", 2nd E d i t i o n , McGraw-Hill, 1979. [ P i e r , 81] P i e r c e , A.D. " A c o u s t i c s : An I n t r o d u c t i o n to I t s P h y s i c a l  P r i n c i p l e s and A p p l i c a t i o n s " , McGraw-Hill, 1981. [PrepHong, 77] Pre p a r a t a , F.P., & Hong, S.J. "Convex H u l l s of F i n i t e Sets of P o i n t s in Two and Three Dimensions", CACM 20, No. 2, 1977, pp.87-93. [RedRub, 78] Reddy, D.R., & Rubin, S. "Representation- of Three Dimensional Objects", Carnegie-Mellon U n i v e r s i t y T e c h n i c a l Report CMU-CS-78-113, 1978. [Req, 80] Requicha, A.A.G. "Representations of R i g i d S o l i d s : Theory, Methods, and Systems", Computing Surveys 12, No. 4, 1980, pp. 437-464. [ReqVoel, 82] Requicha, A.A.G., & V o e l c k e r , H.B. " S o l i d Modeling: A H i s t o r i c a l Summary and Contemporary Assessment", IEEE Computer Graphics and A p p l i c a t i o n s , V o l . 2, No. 2, March, 1982, pp. 9-24. '[Rob, 63] Roberts, L.G. "Machine P e r c e p t i o n of Three-Dimensional S o l i d s " , MIT L i n c o l n Laboratory, TR 315, May, 1963. [RubWhit, 80] Rubin, S.M., & Whitted, T. "A 3-Dimensional Representation f o r Fast Rendering of Complex Scenes", Proc. SIGGRAPH 80, Computer Graphics 14, No. 3, J u l y 1980, pp.110-116. [ S c h r A t a l , 63] Schroeder, M.R., & A t a l , B.S. "Computer S i m u l a t i o n of Sound Transmission i n Rooms", IEEE I n t e r n a t i o n a l Convention Record V I I , part 7, 1963, pp.150-155. [Sham, 78] Shamos, M.I. "Computational Geometry", Ph.D. T h e s i s , Yale, May 1978. [ShamHoey, 76] Shamos, M.I., & Hoey, D. "Geometric I n t e r s e c t i o n Problems", Proc. 17th Annual IEEE Symposium on Foundations of Computer Scien c e , 1976, pp.208-215. 118 [SI, 80] Sloan, R.R. " A n a l y s i s of 'Dot Product Space*' Shape D e s c r i p t i o n s " , U n i v e r s i t y of Rochester T e c h n i c a l Report No. TR74, June 1980. [SuHod, 74] Sutherland, I.E., & Hodgman, G.W. "Reentrant Polygon C l i p p i n g " , CACM 17, No. 1, 1974, pp.32-42. [SuSprSch, 74] Sutherland, I.E., S p r o u l l , R.F, & Schumacker, R.A. "A C h a r a c t e r i z a t i o n of Ten Hidden-Surface Algorithms", ' Computing Surveys 6, No. 1, March 1974, pp.1-55. [ T i l , 81] T i l o v e , R.B. "Line/Polygon C l a s s i f i c a t i o n : A Study of the Complexity of Geometric Computation", IEEE Computer Graphics and A p p l i c a t i o n s , V o l . 1, No. 2, A p r i l , 1981, pp. 75-86. [Wal, 79] Walsh, J . "The Si m u l a t i o n of D i r e c t i o n a l Sound Sources i n Rooms by Means of a D i g i t a l Computer", M.Mus. T h e s i s , U n i v e r s i t y of Western O n t a r i o , London, Canada, 1979. [Wal, 80] Walsh, J . "The Design of Godot: A System f o r Room A c o u s t i c s Modeling and S i m u l a t i o n " , paper E15.3, Proc. 10th I n t e r n a t i o n a l Congress on A c o u s t i c s , Sydney, J u l y , 1980. [WalDad, 81] Walsh, J . , & Dadoun, N. "The Design and Development of Godot: A System f o r Room A c o u s t i c s Modeling and S i m u l a t i o n " , presented at the 101st meeting of the A c o u s t i c a l S o c i e t y of America, Ottawa, May 1981. [WalDad, 82] Walsh, J . , and Dadoun, N. "What Are We Waiting f o r ? The Development of Godot, I I . " presented at the 103rd meeting of the A c o u s t i c a l S o c i e t y of America, Chicago, A p r i l 1982. [Weil, 80] Weil e r , K. "Polygon Comparison Using a Graph Re p r e s e n t a t i o n " , Proc. SIGGRAPH 80, Computer Graphics 14, No. 3, J u l y 1980, pp.10-18. [WeilAth, 77] Weil e r , K., & Atherton, P. "Hidden Surface Removal Using Polygon Area S o r t i n g " , Proc. SIGGRAPH 77, Computer Graphics 11, No. 2, Summer 1977, pp.214-222. [Win,77] Winston, P.H. Art i f i c i a l I n t e l l i g e n c e , Addison-Wesley, 1977.