FAST CLIPPING A L G O R I T H M S FOR C O M P U T E R GRAPHICS by CHAN-HUNG TRAN B. Eng., Chiba University (Japan), 1977 A THESIS SUBMITTED IN PARTIAL F U L F I L M E N T O F T H E REQUIREMENTS F O R T H E D E G R E E O F MASTER OF. APPLIED SCIENCE in T H E F A C U L T Y O F G R A D U A T E STUDIES D E P A R T M E N T O F E L E C T R I C A L ENGINEERING We accept this thesis as conforming to the required standard T H E UNIVERSITY O F BRITISH C O L U M B I A April 1986 ..7 e Chan-Hung Tran, 1986 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the The University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the Head of my Department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. D E P A R T M E N T O F E L E C T R I C A L ENGINEER TNG The University of British Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Date: April 1986 AhsiEaci Interactive computer graphics allow achieving a high bandwidth man-machine communication only if the graphics system meets certain speed requirements. Clipping plays an important role in the viewing process, as well as in the functions zooming and panning; thus, it is desirable to develop a fast clipper. In this thesis, the intersection problem of a line segment against a convex polygonal object has been studied. Adaption of the the clip algorithms for parallel processing has also been investigated. Based on the conventional parametric clipping algorithm, two families of 2 - D generalized line clipping algorithms are proposed: the t-para method and the s-para method. Depending on the implementation both run either linearly in time using a sequential tracing or logarithmically in time by applying the numerical bisection method. The intersection problem is solved after the sector locations of the endpoints of a line segment are determined by a binary search. Three-dimensional clipping with a sweep-defined object using translational sweeping or conic sweeping is also discussed. Furthermore, a mapping method is developed for rectangular clipping. The endpoints of a line segment are first mapped onto the clip boundaries by an interval-clip operation. Then a pseudo window is-defined and a set of conditions is derived for trivial acceptance and rejection. The proposed algorithms are implemented and compared with the Liang-Barsky algorithm to estimate their practical efficiency. Vectorization of the 2 - D and 3 - D rectangular clipping algorithms on an array processor has also been attempted. ii Table of Contents Abstract ii list of Figures vii List of Tables x Acknowledgement 1. INTRODUCTION 1 1.1 General 1 1.2 Why is clipping important? 2 1.3 Aims of the clipping algorithm development 5 1.3.1 Computational complexity 6 1.3.2 Regularity and compactness 6 1.3.3 Parallel processing executability 6 Thesis outline 7 1.4 2. 3. xi N O T A T I O N A N D PREVIOUS W O R K 8 2.1 Assumptions and Notation 8 2.1.1 Line and line segment 8 2.1.2 Clipping window 9 2.1.3 Line segment and convex polygon 10 2.1.4 Visibility classification 11 2.2 Previous work and preliminary results 11 2.3 Discussion 13 T H E T W O - DIMENSIONAL T - PARA CLIPPING A L G O R I T H M 15 3.1 Partition of 2 - D space 15 3.2 Specific cases 17 3.3 The t-para method 19 3.3.1 Properties of the parameters A(i) and B(i) 19 3.3.2 The visibility of a line segment 20 3.3.3 Trivial rejection „ iii 23 3.4 3.5 4. 25 3.3.5 Outline of the t-para algorithm 25 T-para sequential tracing method 27 3.4.1 Tracing direction 27 3.4.2 Termination of tracing 29 3.4.3 Simplified version of t-para sequential method 30 3.4.4 Time complexity 30 Bisection t-para method 31 3.5.1 The algorithm 31 3.5.2 Time complexity 32 T H E T W O - DIMENSIONAL S- PARA CLIPPING A L G O R I T H M 33 4.1 Introduction 33 4.2 The algorithm , - 33 4.2.1 Notation 34 4.2.2 Initial conditions 35 4.2.3 Determination of intersection 36 4.3 S-para sequential method 36 4.4 S-para bisection method 37 4.4.1 The algorithm 37 4.4.2 Time complexity 42 Comparison of the s-para and the t-para methods 43 4.5 5. 3.3.4 The hill and the dale of t-para T H R E E - DIMENSIONAL CLIPPING WITH A SWEEP- D E F I N E D OBJECT 45 5.1 Introduction 45 5.2 Sweep- defined objects 46 5.2.1 Local coordinate system 46 5.2.2 Translational sweeping 46 5.2.3 Conic sweeping 49 iv 5.3 6. 50 The 3 - D clipping algorithm 51 5.3.1 Overview 51 5.3.2 Intersections with side planes 52 R E C T A N G U L A R CLIPPING 55 6.1 Introduction 55 6.2 Classifications for the 2 - D case 58 6.3 Mapping technique 61 6.3.1 Region code 61 6.3.2 2 - D mapping 62 6.3.3 Properties of 2 - D mapping 63 Pseudo window 65 6.4.1 Definition 65 6.4.2 Parameters t for pseudo window 66 6.4.3 Conditions for intersection using pseudo window 69 6.4.4 Trivial rejections 70 6.5 The 2 - D rectangular clipping algorithm 71 6.6 Time complexity and parallelism analysis 72 6.7 3 - D extension 74 6.4 7. 5.2.4 The t'-t transform EXPERIMENTAL ALGORITHMS ESTIMATION OF T H E EFFCIENCY OF T H E PROPOSED 77 7.1 Introduction 77 7.2 Experimental results of the 2 - D generalized clipping algorithm 78 7.2.1 Experiment 1: Varying area ratio 79 7.2.2 Experiment 2: With different categories of line segments 80 Vectorization of rectangular clipping 86 7.3.1 Overview 86 7.3.2 Vector version of the rectangular clipping algorithm 91 7.3 v 7.4 7.5 8. Some notes on the AP implementation 91 7.4.1 Vector codes in APs 91 7.4.2 The division problem in the AP 92 7.4.3 Memory limitation of the AP 93 Experimental results of rectangular clipping 94 CONCLUSIONS 105 8.1 Summary 105 8.2 Concluding remarks 106 8.3 Future work 106 BIBLIOGRAPHY 108 APPENDIX A Ill APPENDIX B 116 APPENDIX C 119 APPENDIX D 128 vi List of Figures Figure 1.1. Page Three-dimensional line-clipping examples: (a) interior clipping and (b) exterior clipping (from [Roge85]) 1.2 3 Three-dimensional polygon-clipping examples: (a) interior clipping and (b) exterior clipping (from [Roge85]) 4 1.3 Viewing pipeline and coordinate systems (from [Artw]) 5 2.1 Clip polygon and entry/exit boundaries 10 2.2 Basis of the Cyrus-Beck algorithm 12 3.1 Partition of 2 - D plane 16 3.2 Binary tree BT 16 3.3 Classification of general 2 - D clipping 18 3.4 All cases of A ( / ) and B ( / ) 21 3.5 Examples of Aim(uv,Lj) true 21 3.6 Trivial rejections 24 3.7 t (/) vs. / (this example assumes &f0 3.8 Examples of tracing clirections 28 4.1 Basis of s-para method (this example assumes c is on the right to L) 34 4.2 Parameter values G and F of entry and exit boundaries 37 4.3a G . vs. / and F . vs. / (this example assumes G_<0 or incr= +1) 39 4.3b G . vs. / and F . vs. / (this example assumes G _>0 or incr= -1) 40 u uv uv i or incr— +1) i 26 t 4.4 Examples of visibility testing using G or F parameter 41 5.1 The clip volume with translational sweeping 47 5.2 The clip volume with conic sweeping 48 5.3 Intersections with the side planes of a clip volume with translational sweeping 53 5.4 Intersections with the side planes of a clip volume with conic sweeping 53 6.1 The clip window and nine regions 56 vii 6.2 The region codes in 2 - D 62 6.3 Classfied cases and determining conditions 64 6.4 Shrunk image 65 6.5 Examples of pseudo window (shaded region) 67 6.6 Parameters tpX, t^x, tpy, and tqy for the pseudo window 68 6.7 Special t values when N R * 0 or N R * 0 69 6.8 Trivial reject cases 71 6.9 Execution tree of 2 - D rectangular clipping 73 6.10 Region codes in 3 - D 75 6.11 Orthogonal projections of the clip volume and a line segment 75 7.1 C P U times for three types of 2 - D generalized clipping algorithms where the area ratio of window polygons is 2 7.2 81 C P U times for three types of 2 - D generalized clipping algorithms where the area ratio of window polygons is 10 7.3 82 C P U times for three types of 2 - D generalized clipping algorithms where the area ratio of window polygons is 20 7.4 83 C P U times for three types of 2 - D generalized clipping algorithms where the area ratio of window polygons is 40 7.5 84 C P U times for three types of 2 - D generalized clipping algorithms where all line segments are entirely visible to the window polygons with area ratio=2 7.6 C P U times for three types of 2 - D generalized clipping algorithms where all line segments are entirely invisible to the window polygons with area ratio=2 7.7 87 88 C P U times for three types of 2 - D generalized clipping algorithms where all line segments are partially visible to the window polygon of 100 sides with area ratio=2 7.8 89 C P U times for three types of 2 - D generalized clipping algorithms which are the average times of Figs. 7.6 and 7.7 viii 90 7.9 C P U times for 2 - D rectangular clipping of the Liang-Barsky algorithm where the area ratio varies from 1 to 200 7.10 96 C P U times for 2 - D rectangular clipping of the scalar version of the mapping method where the area ratio varies from 1 to 200 7.11 97 C P U times for 2 - D rectangular clipping of the vector version of the mapping method where the area ratio varies from 1 to 200 7.12 98 C P U times for 3 - D rectangular clipping of the Liang-Barsky algorithm where the volume ratio varies from 1 to 400 7.13 99 C P U times for 3 - D rectangular clipping of the scalar version of the mapping method where the volume ratio varies from 1 to 400 7.14 100 C P U times for 3 - D rectangular clipping of the vector version of the mapping method where the volume ratio varies from 1 to 400 101 7.15 Improvements of the 2 - D mapping method vs. area ratio 102 7.16 Improvements of the 3 - D mapping method vs. volume ratio 103 7.17 Improvements of the vector version of the 2 - D and 3 - D mapping method vs. number of line segments 104 A.1 Case u = v 115 A. 2 Case uv parallel to ow'or (t' = v / ( v - u ) „aj__L u * \ ) B. Classified cases for determining a • 0 ^ 0 and | a| £ 101 C. 1 Classified cases for determining a,/3, m have the same sign and | a\^ | m| ^| 01 C.2 Case Ax* 0 and A y * 0 125 C.3 CaseAx=0orA=0 126 C.4 Case t y = y c and t x=tpy x ; c and u^=v^, z q 2 z z z 115 118 121 127 q ix List of Tables Table Page 3.1 Visibility and E parameters 23 6.1 Classifications according to regions in which the endpoints lie 59 6.2 Description of classified cases 60 7.1 Division results of the AP 93 7.2 Improvement of the mapping algorithm over the Liang-Barsky algorithm in 2 - D and 3 - D rectangular clipping ; x 95 Acknowledgement I would like to express my grateful thanks to my supervisor Dr. G.F. Schrack, whose continuous guidance and encouragement throughout the research work of this thesis is sincerely appreciated. The financial support received in form of a Teaching Assistanceship from the Department of Electrical Engineering at the University of British Columbia is also gratefully acknowledged. I am also grateful for the encouragement and support of my wife, Phuong, for this thesis could never have been done without her enduring understanding and patience. xi 1 Chapter 1 INTRODUCTION 1.1 General Panning and graphics. They are zooming are two important functions in interactive computer effective only, however, if they can be performed in real-time. In general, real-time operations can be achieved with expensive hardware, or, alternatively, with priced moderately Embedded in the hardware which limits the functionality functions, clipping algorithms which are of the operations. fast to run in software and are easy to implement in hardware or firmware are also desirable. While clipping is a well-known term in Computer Graphics, intersection is a related problem discussed in Computational Geometry. Both deal with efficient ways to find the union, intersection, and difference of two objects in a wide sense. The operations usually consist of three steps: 1. 2. 3. detecting whether two objects intersect, finding the points of intersection, if they intersect with each other, constructing their union, intersection, or difference, depending on the application. In Computer Graphics, clipping is, mostly, referred to finding the intersection or the difference of an image with a defined region called the clip window in 2 - D or the clip volume in 3 - D . The clipping process is to remove the exterior portion (interior clipping) or the interior portion (exterior clipping) of an image to the clip window or the clip volume. If an image is composed of straight line segments, the type of clipping is called line clipping (Fig. 1.1). e.g. in vector graphics, then The extention of line clipping is 2 then called polygon clipping such that the resulting polygon can be filled (Fig. 1.2). In this thesis, the intersection of line segments with a convex polygonal window or volume is considered. algorithm The intersection mentioned earlier. problem is the The intersection second step operation of the is performed complete clipping after it has been determined that the two objects are possibly interfering using one of the algorithms in [Maru72], [Chaz80], and [Dobk83]. Then, the resulting intersection points of this step are used to outline the real shapes of polygonal objects which are inside or outside the clip region such as in the Weiler-Atherton algorithm [Weil77] or the Weiler algorithm [Weil80]. 1.2 Why is clipping important? Clipping plays an important (see details in [Newm] coordinate in the The viewer displayed and a viewport, the window contents viewing pipeline in computer graphics and [Fole]). The object to be viewed is described by geometric data in world coordinates. wishes to have the role are mapped (Fig. can specify a portion of the 1.3). Mapping clip region view surface points which are which he into which outside the window may produce undefined values, resulting in attemps to address locations beyond the physical limits of the Furthermore, clipping leads display device. Such situations can be prevented by clipping. to a substantially smaller amount of work for the display hardware to process. To improve the update rate for real-time identify program, where it time was is being spent found multiplication operations, that only while the mostly. 5% of In the graphics applications, it is important to a time time analysis was largest block of time spent (23%) of a on flight simulation performing matrix was spent on clipping ([Artw, p. 142]). The high percentage implies that a significant saving in processing time Fig. 1.1 Three-Dimensional line-clipping examples: (a) interior clipping (b) exterior clipping (from [Roge85]). Fig. 1.2 Three-dimensional polygon-clipping examples: (a) (b) exterior clipping (from [Roge85]). interior clipping and can be achieved by improving the clipping operation. In addition to the hidden viewing process, computer graphics: line/surface ray/beam tracing ([Suth74], [Weil77], clipping removal, is useful shading, [Catm78], [Dado82], for texture, several anti-aliasing, and [Carl85]. of and [Dado84]). It also contributes to solid modeling using Constructive Solid Geometry (CSG) and oct-tree [Roth82] aspects representations Besides computer graphics, clipping has been exploited in many other disciplines, e.g. robotics (object interference problems) [Boys79], [Ahuj80], and VLSI design (rectangular intersection). 5 1.3 Aims of the clipping algorithm development A clipping algorithm may be implemented in software or hardware, or may be executed has in scalar been ([Spro68], processors implemented [Clar80], in or parallel processors. hardware [Mehl84]). Thus, rather the For example, the clipping algorithm than algorithm software for interactive should be simple graphics enough for hardware implementation. Secondly, algorithms which can be implemented in high-speed parallel processing aim to improve execution speed. Therefore, the following considerations must be taken into account for the algorithm development: 1. '2. 3. the computational complexity of the algorithm, the regularity and compactness of the algorithm, the parallel executability of the algorithm. Fig. 13 Viewing pipeline and coordinate systems (from [Artw]). 6 1.3.1 Computational complexity Although Geometry are the logarithmic asymptotically detection fast, the and intersection algorithms in Computational efficiency might not be achieved due to a large constant factor of proportionality or due to their algorithmical complexity, especially for those algorithms using complicated data structures in pursuit of theoretical efficiency (see more discussion in Chapter 15 of [Pavl]). In 2-D, let M be the number of line segments to be clipped and let N be the number of sides of the window polygon. In computer graphics applications, N is often small and M is large. A brute-force algorithm consists of an inner loop (N iterations) and an outer loop (M iterations); thus it will be executed M « N times. Because N is fixed, it is desirable to preprocess the window polygon in order to obtain an O(MlogN) 1 algorithm. However, care must be taken if the investment overhead is fairly large. 1.3.2 Regularity and The hardware compactness algorithm should implementation. formulation of the exhibit Therefore, problem is reject or accept a line segment the clipping algorithm elegant, regularity a simple important Since for intersections tradeoffs between and be data the are as compact structure inherent is as possible desired branching for and the conditions to always the limiting factor to make extensive mathematical calculations and decision-making are sometimes necessary. 1.3.3 Parallel processing executability Because the line segments to be clipped are independent of each other, it is likely that the clipping process is suitable for parallel processing. Moreover, because the 'The expression "log" denotes logarithm base 2. 7 number of line segments M is large, it should be possible to vectorize the computations in order visibility to improve of a the line execution segment speed. against a The clip main concern window with is how to detect the N and how the large intersection tests can be processed in parallel. 1.4 Thesis outline This • thesis is divided into eight chapters. In Chapter 2, we will review previous work and some preliminary results, after establishing the notation and conventions which are used throughout the thesis. algorithm, called a t-para bisection method are In Chapter 3, a generalized 2-D parametric clipping method, will be discussed. A sequential tracing method and a explained. Another variation of 2 - D parametric clipping, called a s-para method, will be described in Chapter 4. The extended 3 - D version of parametric clipping techniques will be exploited in Chapter 5. The clip volume is restricted sweep-defined rectangular mapping intersection object 2-D created and operation. 3-D Here, computation. In by translational clipping a is described in Chapter 3, 4, and 6 7, will conic presented. pseudo-window Chapter or results is The sweeping. clipping introduced from for experiments be discussed. Finally, In Chapter 6, process relies fast rejection with the to a the on a and algorithms in Chapter 8, concluding remarks will be made and further avenues for research will be suggested. 8 Chapter 2 N O T A T I O N A N D PREVIOUS WORK 2.1 Assumptions and Notation It is useful to introducing the notation begin by establishing which will be used some throughout fundamental the thesis. here is restricted to 2-dimensions, but it can be extended assumptions and The notation given to 3-dimensions easily. 2.1.1 Line and line segment A line segment is represented by uv, where u ( u , u^,) and v(v , v ) are its x x two endpoints. While the direction vector D = v-u denotes the directed from a point u to a point v, L denotes the directed line segment uv straight line of infinite extent which contains uv and has the same direction as uv. The inner normal vector D of D is defined in terms of its coordinates (v^-u^,, -(v^-u^)). 1. An arbitrary point in 2 - D space i(z , z) x y is said to lie to the left of (right of, on) L if T = zu • JQ = (u^-ZjXv^-up - (u -z )(\ -u ) y y x ... (2.1) x is positive (negative, zero). 2. If lies z on JL, then T = 0. We have t = (z -u )/(\' -\i ) the line x x x x = (z -\i )/(v -u ). y For y y y every value parameterized z = of t, a corresponding point on is defined in form as t[u,v] 4 ii + t(v-u) ... (2.2) or i = n + tD ... (2.3) 9 The coordinates of point z are z x = u + x The parameter values t=0 and t = l t(v -u ) x x t, called the ... (2.4) t-para, determines where the point lies on L The correspond to the endpoints u and >, respectively. If te[0,l] then the line segment uv is traced out; tc^o , ) generates the infinite line L. 0 00 2.1.2 Clipping window We assume that the clip window P is a single convex polygon, which consists of a sequence of straight-line edges such that they form a cycle and such that no two edges intersect, except at their endpoints. We represent the polygon by a circular list of its vertices P (Wi,w .... viflVi edges are are the w^), where the points Wi.w, 2 sides or the not collinear. Each w^(/)) and each boundary edges. are the vertices and i T ^ , We also assume vertex is defined by its x- edge is' represented that two consecutive and y-coordinates by its two endpoints e.=vx. + ^ w.(w 2.1). (/), Note that index addition and subtraction is taken modulo N . The directed infinite straight-line containing the edge e^. is called its boundary line and is denoted by L.. L. has the same direction as e^.. Convention 1 A point p is said to be interior to side of L. pifl^), or on the otherwise line L. exterior if it lies on the right (i.e. pflflL^. is considered to be (pxmlip. The expressions nu, in. and out are bon-owed from [Tilo80]. Convention 2 The vertices of a polygon are linked in a clockwise (CW) direction such that the interior of the polygon is always to the right during a positive traversal. 10 w w note: Chainl = Fig. 2.1 {c 7 14 7 — e i 3 }, Chain2 = { - * 6 )• Clip polygon and entry/exit boundaries. By this convention, the inner normal vector of the edge e., viz., JE ( y['+l)-w^(/), i ~[w (/+l)-w (/)]), w J| Jt always points to the interior of the polygon P. 2.1.3 Line segment and convex polygon Consider the relative position of a line segment uv can draw two lines of support parallel to L and passing through a pair of antipodal points R and S of the clip polygon (Fig. 2.1). the interior of L., points from the If L points from the exterior of L. to then the boundary edge e^. is called an entry boundary to uv; if L interior of L. to the exterior of L., called an exit boundary. Two chains of boundaries are by chain! and a clip polygon P. We consisting of all entry boundaries and an then the boundary edge is formed: an entry chain denoted exit chain denoted by chain2 11 consisting of all exit boundaries (see Fig. 2.1). 2.1.4 Visibility classification In interior this of invisible, the or considered thesis, only exterior clip window. A partially visible clipping is line segment to the considered. is classified clip polygon. The to be visible to the polygon: the The as visible region entirely is the visible, entirely following degenerate cases are line segment touches the polygon at one point or eitheT a portion or the whole of the line segment coincides with a boundary edge of the polygon. Convention 3 Any part of an image that lies on the clipping boundary is considered to be inside the clip window. 2.2 Previous work and preliminary results Two considerations of a line [Cyrus78] equivalent (2) for algorithms and (3) intersection representing proposed of Section 1.3. testing and Liang and Barsky interpretation are the in the literature which The idea of using a parametric were independently [Lian83, parameter Lian84]. value proposed by Cyrus and Beck for intersection of satisfy representation Cyrus use a a the and Beck geometrical particular line segment and a boundary line, while Liang and Barsky describe it in an algebraic form. Both described the inequalities. conditions for detecting Determining the programming problem. We will intersections appropriate . intersections decribe the above as a set reduces method of minimum/maximun to a classical linear differently, which is adapted to our notation. The problem of a line segment intersecting finding the intersections with a convex polygon is solved by of the line segment and all boundaries of infinite extent, then 12 imposing a parametric range restriction. Let f be any point on the extended line J L of an edge e^. (Fig. 2.2). The intersection of L and L. is determined by: V(ttu.*]-f) = - 0 <-) 2 5 Substituting t[u,v] = u + t(v-u) into (2.5), we have t (z) = uv A (z) / B (/) u ... (2.6) UV Where A (/) = £ / .(f-u), B £ / -(v-u). U UV (/)= (2.7) For simplicity, assume f is w „ We have: A (/) = m B (/) = E (/) - U uv where E(/) =&.•it., E (/) - U V U E (/)=£ .«u, u (2.8) E (/) / E (/)=£ «v. v / «i • (t[u,v]- f ) t[u,v]- S.i • (t[u,v] - f ) > 0: visible £ i • (t[u,v] - f ) = o : intersect £ i • (t[u,v] - f ) < 0: invisible exterior Fig. 2.2 interior Basis of the Cyrus-Beck algorithm. 13 The properties of the parameters A ( / ) u 3.3.1 and 3.3.2. The notation t parametric line L from [Cyru78, Lemma 1 containing (/) uv and B ( / ) will be discussed in Sections uv denotes the t-value and the boundary of the intersection point of the line if B ( / ) * 0 . uv The results Lian84] can be summarized in the following lemmas: The set of values t such that 1. te[0.1], 2. £ .'(t[u,v]-f) > 0, | completely determines respect to L (Fig. i lenaaiLJL Let max_tO = the visible portion of line segment uv 2.2). max( U ( / ) | B (/)>0 , ie[l,N]} U {0} uv uv ) 2 or max( Jt (/)|e.echainl or u v V / e ^ ie[l,N]J U {0} uv min_tl = with min( {t (/)|B (/)<0 ie[l,N]} U 11} ) min( i?\i)ejecbam2, ). UV uv /e[l,N]} U {1} ), or The necessary and sufficient condition for a line segment uv to be at least partially visible with respect to the polygon P is: max_t0 < Lemma 3 If uv min_tl is partially visible with respect to P, then the endpoints of the visible segment are max_t0[u,v] and min_tl[u,v]. 2.3 Discussion The Cyrus- Beck/Liang- Barsky and three-dimensional algorithm line-clipping" algorithm is a "powerful, [Roge85]. efficient, Performance general two- tests showed that For the B ( / ) = 0 case (line segment parallel to the corresponding boundary line), t (/) is defined as [Lian84] © 0 = + « if ( B ™ ( i ) = 0 ^nd. A (/)>0), t ( / ) = - » if (B (/)=0 jo± A (/)<0). In the implementation, however, the B (/)=0 case is treated separately by testing the sign of A ( / ) : if positive then the line segment is invisible, else visible. 2 uv uv u u v u uv u 14 36, 40, 79 percent Sutherland-Cohen respectively but also Lemma 2 algorithm [Lian84]. is improvements used for 2-D, have 3-D before to helps to compute the determine coordinates quickly if a subdivision technique rejecting and gained 4-D it Since of the the conventional coordinates) to determine intersection line segment early points cases, rejection if accepted. diagonally bypasses the clip the Sutherland-Cohen algorithm [Roge] or the [Spro68]) performs the over (homogeneous The parameter t not only contributes window, while the conventional test (e.g. midpoint been parameters t a are significant amount independent with of computation respect to the of the boundaries, they can be computed in parallel. However, the conventional parametric algorithms clipping polygon is large. Since it must compute in the worst case, O(N) operations are slow if 'the size t-para's with respect to all boundaries are required. The key observation is the following: if the location of the endpoints u and v can be identified, much effort can be saved in computing the t-para set because a large number of boundaries is eliminated from consideration. In this thesis, we concentrate on the problems of 1. how to identify the location of the endpoints of line segments, 2. how to utilize the location information to reject quickly the line segment invisible as well as partially visible. to detect quickly the if it is boundaries which it intersects if it is 15 Chapter 3 T H E T W O - D I M E N S I O N A L T - P A R A CLIPPING A L G O R I T H M In this chapter, two variations of the 2-dimensional t-para clipping algorithm are proposed. angular Unlike by polygons; Shamos can conventional sectors for detecting proposed M-gon the Shamos to 2-D space is divided into location of endpoints. This approach solve 0(M+N) the the intersection algorithm to find problem the clipped except that applicable to clip non-convex the intersection endpoints, testing 75% (see they are formed by line of intersection with a convex N-gon. Since we do not restrict the shape be contain quickly the [Sham75] gave an parametric algorithm convex of a convex our objects that algorithm is objects to a convex region. By knowing the sectors which of Section the boundaries 3.4.4). Thus, a are, on small the average, investment eliminated results in computational saving if the number of window polygon sides is moderately 3.1 two of the segments, was first from considerable large. Partition of 2 - D space Let c be any point interior to the window polygon P (e.g. P), then the semi-infinite rays emanating from c and drawn through the vertices of P partition the plane into N angular sectors as shown in Fig. 3.1. no sectors or regions the mass center of will overlap. This assures the Because P is convex, uniqueness of the sector belonging to an arbitary point in the 2 - D plane. To simplify the discussion, we assume that the points of interest do not coincide with the center c. tree (BT) is generated which stores the slopes of the As shown in Fig. 3.2, a binary semi-infinite rays cw^., /e[l,N]. Then the sector containing a point can be found by a binary search. The binary search will cost segment O(logN) uv lies after in the O(N) sector preprocessing formed by time the [Sham75]. boundary The e, endpoint (see Fig. u 3.2), of line if the 16 Fig. 3.1 Partition of 2 - D plane. the sector belonging to point u In Fig. 3.1. Fig. 3.2 Binary tree BT. 17 successful search of the slope is obtained as slope( cw*£ 2 ) < slope( cu ) ^ + slope( cw^ ). Then we can easily determine whether u is exterior or interior to P by testing whether j_£«uw£ is positive or negative/zero. The edge corresponding to the endpoint v will be similarly identified. During preprocessing, the necessary polygon data (e.g. s.^ and E(/)) are also precomputed and stored. The generation time of the binary tree as well as the polygon data precomputation time is an overhead operation whose percentage of the total processing time drops to nearly zero as the data base of clipped line segments grows. Therefore, if we consider clipping a large set of line segments, the overhead time for each line segment is negligible. This approach only yields advantages if the polygon data can be precalculated and reused for each line segment The time complexity now becomes the space complexity of O(N). 3.2 Specific cases We now polygon P after consider the intersection problem of a line segment uv and the the regions belonging to its endpoints have been identified. As shown in Fig. 3.3, there are five cases: Case 1 Points u and v lie within the polygon P, no intersection in the with the boundaries of P occurs. Case 2 Points u and v lie on the outside of P same sector, no intersection occurs. Case 3 One of the points u, v is inside and the other is outside of P in the same sector, uv intersects a bounding edge. Case 4 Both u and v are outside P in different sectors, uv may or may not (a) Case 1 (b) Case 2 V (e) Case 5 Fig. 3.3 Classification of general 2 - D dipping. 19 intersect with P. Case 5 One of the points u and v is inside and the other is outside in a different sector of P, uv intersects a bounding edge. Cases 1 polygon P at to 3 are straight-forward. one point, we only In case need to determine 5 since uv where the must intersect intersection point is. Case 4 is the worst case consideration: we need to determine first whether uv P and, if it does, which boundaries it intersects. location of the Because the the intersects solution determining the intersection points for case 4 and case 5 is similar, case 4 is more difficult than case 5. Thus we need to concentrate on case 4 where u and v lie in exterior sectors bounded by edges e^. and e^, respectively. In this thesis we propose two visibility testing methods utilizing parametric line representations 4). Both called the t-para methods can be method (Chapter 3) executed linearly in time and the s-para by tracing method (Chapter edges sequentially or logarithmically in time by applying a numerical bisection method. 3.3 The t-para method 3.3.1 Properties of the parameters A(i) and B(i) The treatment [Lian84]. of A ( / ) u Nevertheless, they and B ( / ) are is only mentioned briefly in [Cyru78] uv very useful in determining the segment uv with respect to an arbitary boundary line A (/) u The A (/) u sign is the of A ( / ) u dot product of vector indicates the is positive (negative, boundary line L.. uF visibility of the and line of P. and the inner normal vector £ . of e „ half plane of J L on which zero), point u lies to the exterior the endpoint u lies. If of (interior of, on) the The absolute value of A (z) is not the minimum distance from u to u 20 L. but is proportional to it. Since B ( / ) is the dot product of uv and the inner normal vector £.., Its sign uv denotes the aiming direction of L with respect to L.. If B ( / ) is positive (negative, uv zero), L is aiming from the exterior to the interior of (from the interior to the exterior of, is parallel or collinear to) L.. Alternatively stated, uv is aiming towards L. if B (/)>0 or uv is aiming away from L. if B (/)<0. uv uv 3.3.2 The visibility of a line segment First, we will discuss the visibility of a line segment uv against an arbitary boundary line L. of polygon P.. It is convenient to establish some useful predicates to explain the problem. Utilizing the parameters A ( / ) and B (/), u the predicates interior, uv aim, and cross can be defined as follows: 1. interior{vi,L^ is true if A ( / ) £ 0 ; otherwise false. ... (3.1) 2. a/m(uv,L.) is true if (A (/)>0 .and. B (z)>0) sx. (A (/)<0 ,and. B (/)<0); u u uv u uv otherwise false. 3. cro5i<uv,L.) is true ... (3.2) if (0<A (/)<B (/)) ,oj. (B (/)<A (/)<0); u uv UV u otherwise false. ... (3.3) interior(u,L^ expresses the relative location of point u with respect to L., while c/m(uv,Lp expresses the direction of uv with respect to L.. If aim(uv,L^) is false (Fig.3.4 cases b, c, e, f, and g) then the line segment uv is entirely visible or entirely invisible with respect to L.. However, if «'m(uv,Z.p is true (Fig. 3.4 cases a and d), a further test is necessary to determine whether or not uv intersects L.. Predicate cross is used for this purpose. If crossiw^j) is true then uv intersects L . and a portion of the line segment is visible, for which te[t (.),l] or te[0,t (/)] uv depending on whether point u lies in the exterior or the interior half plane of L.; otherwise uv is entirely visible uv 21 Li exterior interior exterior interior. j : (b)y> <dy ' u V ei ei V (a) (c) A (i )<0 A (i )>0 A (i )<0 A (i )>0 u u u u B (i)>0 B (U<0 U V U V (e^ is entry boundary) ( is exit boundary ) Li exterior (e) interior * 1 (g) 3 A (i )>0 U A (i )<0 U B (i)=0 is parallel or col linear to uv ) U V Fig- 3.4 All cases of A ( / ) and B (/). u uv Li : a^u v iv Note: The predicate CrossiwM) is true for segments a, b and c only. / r Fig. 3.5 Examples of Aim{u\,L ) true. i 22 or entirely invisible because uv terminates on the way pointing towards L. but does not uv cross it (see Fig. 3.5). Note that the predicates aim and cross assure Q^t (/') and t (/*l. w Combining all predicates, the visibility of the line segment uv the boundary L. with respect to can be defined by a new predicate v/s/We(uv,Lp as described in the procedure Line_Visible (see Algorithm 3.1) . 3 Embedded in the predicates interior, aim, and cross, the relationships among E(/), E (/), and E (/') can be tested for saving the u u calculation of A (/), uv B (/), v uv and t (i) (Table 3.1). these E parameters is described in Algorithm 3.2. A more efficient visibility test using It should be noted that the visibility test results of uv and vu against L. are related by visible{u\,Lp = vu/We(vu,Lp and t (/) = uv l-A/). Let us consider the visibility "problem of a line segment with respect to the polygon P. By convexity, each boundary line supports the polygon. Therefore, the visible region defined by the polygon P is the intersection of the interior half planes of all L., ie[l,N]. A line segment uv is said to be visible (entirely or partially) with respect to P, if N .and. visible{a\,L) = i=l true. This implies that the visibility of a line segment against a polygon can be determined by a set of Line_Visible procedures invoked in a loop. ' A l l algorithms appear in Appendix D . 23 3.3.3 Trivial rejection Since the sectors e^, e^ corresponding to endpoints n, v, respectively, a trivial rejection can be established. are known, For both u, v lying in the exterior of P, the condition for trivial rejection is defined by if jiQi. [visible(u\,L£ .and. v/«'We(uv,L ) .and. t (it)--t (/)] then J uv uv reject uv. Recall shown that chainl and chain2 in Fig. 3.6, ik,/echain2, ... (3.4) condition (3.4) are the chains of entry trivially rejects and exit boundaries. As all segments with because one of the visibility test against the boundaries Furthermore, it rejects the cases where t (k)£t (l) uv uv E (i)<E (i) E (i)<E (i)<E(i) E (i)<E(i)^E (i) E(i)<_E(i)<E(i) 0<B (i) (kB (i)<A (i) 0<A (i)^B (i) A (i)_sO<B (i) B (i)<0 B (i)<0<A (i) B (i)<A (i)_sO A(i)__;B (i)<0 E«(i)=E (i) E (i)=E (i)<E(i) E(i)r^E (i)=E (i) B (i)=0 0=B (i)<A (i) A (i)<_B (i)=0 u u v v u v u v v v u u v u v u v u v u v u u uv u uv false false true true true false false true false u uv u u uv false true true false true true false true false false true true exit boundary entirely invisible partially visible entirely visible false true parallel boundary entirely invisible entirely visible uv uv u u uv Table 3.1 false true false false false false visibility entry boundary entirely invisible partially visible entirely visible uv uv fails. false true true uv uv and or even though the segment is visible Interior Aim Cross Visible E (i)<E (i) E (i)<E (i)<E(i) E (i)<E(i)_$E(i) E(i)^E (i)<E (i) k,le chainl Visibility and E parameters. 24 7 note: line segments (a) and (b) are rejected by visible(uv,e|<)=false, line segments (c) and (d) are rejected by visible(uv,ei )=false, line segment (e) is rejected by t (k)>t (i). Uv Fig. 3.6 Trivial rejections. uv 25 for both 3.3.4 and Ly The hill and the dale of t-para Based on t-para's of uv the ordering with respect to the unimodal functions with a Lemma 2, uv properties intersects hill for P if assured entry the convexity considerations, the boundaries and exit boundaries generate two chainl and by and only if a dale for chain2 the maximun (see t-para Fig. 3.7). against the By entry boundaries does not exceed the minimum t-para against the exit boundaries. If so, uv intersects P at two points corresponding to max_tO and min_tl by Lemma and d indicate the boundary indices corresponding to the hill and the dale, 3. Let h respectively. Then, uv intersects P at the boundaries e, and e ,. h d If it is possible to find the minimum/maximum values of the t-para quickly, it will speed up the detection lies in the combined and intersection sector which is problem. By knowing that the segment uv bounded by the intervening chain, a naive algorithm can be established the range [k,l] the t intervening it runs faster than the called the to calculate the t-para's within and to eliminate the edges out of range. computations, edges, As a consequence, conventional parametric by saving algorithms which calculate all t-para's in the worst case. 3.3.5 Outline of the t-para algorithm The outline Algorithm 3.3. mentioned in of the However, the algorithm the previous actual sections, is implementation since compact and elegant In the next sections, method, the sequential tracing described method the in is t-para high-level pseudo different from algorithm can the be code in description made more we will discuss two variations of the t-para and the bisection method, one of which will 26 (boundary index) B (i)>0 B (i)<0 uv uv B (i)=0 uv (a) accepted case: 0<max_tO<min_t 1< 1 max_tO min_t1 i (boundary index) B (i)>0 uv B (i)<0 uv B (i)=0 uv (b) Fig. 3.7 rejected case: 0<min_t1 <max_t0<1 UV t (/) vs. / (this example assumes G <0 or incr= + l). 27 replace step 4.2 of the main procedure. 3.4 T-para sequential tracing method 3.4.1 Tracing direction As mentioned earlier, we only need to compute the t-para's of the edges within the intervening chain. The searching process of the minimax values of the t-para's can be performed sequentially either from e^ to e^ or from e^ to e^. compute the t-para's of the entry/exit ej ), (e, , . l-mcr" k+2'incr , 61 . ), 1-2-incr' v It is convenient to boundaries, in pairs, such as (e^, e^), ( £ e + z n c -» etc. so that we can quickly detect t . > t ..for entry exit fast rejection, where incr might be +1 M J (front trace: trace in C W direction) or - 1 (back trace: trace in C C W direction). The tracing directions depend on the relative location of c with respect to L. A tracing rule is established as follows: G c if G = D-(u-c); < else if G else endif endif; 0 then incr = +1 > 0 then incr = -1 { c is on the right to L } { front trace entry boundaries, back trace exit boundaries } i c is on the left to L } { back trace entry boundaries, front trace exit boundaries } { no boundary tracing is necessary: vu intersects with e^ and e^ } The algorithm maintains two edge pointers for tracing chainl and chain2. These pointers are advanced clockwise or counterclockwise around the polygon P according to the tracing rule such that the edges in chainl and chain2 are search "chased" one by one to the intersection points. Examples of boundary tracing are shown in Fig. 3.8. should be noted that in case 5 only one direction of tracing is necessary: It if u«T then entry tracing otherwise exit tracing with the same tracing direction as case 4. L back tracing front tracing (b) c is on the left to L (incr=-1 ) Fig. 3.8 Examples of tracing directions. 29 3.4.2 Termination of tracing An the important consideration for an algorithm intervening chain is bounded by [&,/], the are the tracing stopping rules. First, can not since exceed these extrema. We also define a tighter bound for each direction of tracing. To simplify the discussion, assume that c is on the right to L. Entry tracing stops when it traces from chainl and passes an antipodal vertex, i.e. B UV (/) changes sign from positive to negative/zero (see UV Fig. 3.7 again). Similiarly, exit tracing terminates if B postive/zero. Recall that the purpose of tracing is (/) changes sign from negative to to find of t-para's. The entry boundaries are traced uphill such that ^ from e^. and reversely the exit boundaries approaching min_tl from e^. The entry are tracing traced the e n t r y minimax values is approaching downdale such that stops when it just passes over max_tO t ^ is the hill UV of t-para and begins to face downhill (t (/) turns terminates when it just passes over the dale of t-para 1 turns to [d-incrj] increase). Therefore, tracing only occurs to decrease); the exit tracing and begins to face uphill (t (/) within and the inner boundaries [h + 2-incr, d-2-incr] uv the ranges [k,h + incr] and corresponding to the hill and the dale of t-para are eliminated from tracing. This indicates the significant saving of t computations if the sectors belonging to the endpoints of a line segment are known. It should be noted that although both boundary tracings start at the same time from e^. and respectively, one might terminate earlier than the other during the race to reach max_tO or min_tl. The entire tracing process ends when both have or the reject condition (t >t .) has been satisfied. terminated 30 3.4.3 Simplified version of t-para Instead sequential method of exit tracing, we can replace tested with chain2 for intersections max_q0 = l-min_t0. Then, it by an entry tracing such that vu is rather using uv. Note that t ^ / ) instead of searching min_tl = l-t (/). we can search the maximum value (max_q0) during the entry tracing of vu starting from e^ and following the direction. The tracing procedure shown in Algorithm 3.4a. can The be simplified to t-para sequential deal only with entry tracing algorithm Let uv is -incr tracing as described in Algorithm 3.4b. 3.4.4 Time complexity The tracing time is O(N). Because is difficult to approximated analyse circle the average the shape of the clip polygon is arbitrary, it case. If we assume with sides of equal length and c the clip polygon as the center, then the range is equal to half of the polygon (circle) perimeter for the worst,case. infinite line parallel to the line segment uv and passing through c. is an tracing Imagine an This line will divide the circle into two half planes one of which contains the segment uv. It is easy to see that at most half of the circle perimeter needs to be traced. Thus, for the worst case 50% of the polygon edges are needed to determine intersection. Therefore, on the average the t-paxa sequential tracing method needs only an evaluation of 25% the parameters L However, the time complexity is still O(N) because complexity parametric eliminates the multiplicative factors. clipping algorithms always compute On the other hand, of the computational the conventional all t-para's (N times) in order to find the minimax t-values for intersection points. Let us consider the possible use of parallel processing for the t-para clipping algorithm. There are sequential two levels of parallel executability. The entry tracing and 31 exit tracing They are independently update suitable for the parallel global variables implementation. max_tO and min_tl, Furthermore, each respectively. t-para needs two E-computations (E (/) and E (/)) which can be done in parallel. u v 3.5 Bisection t-para method 3.5.1 The algorithm uv We know that the t-para function ( t (/") minimum value (min_tl) discussion we bounding suppose vs. /' ) is a bimodal function with a and a maximum value (max_tl) within [k,l]. To simplify k<l edge e^. of the for incr= + l. .Because intervening chain is not uv t (/) the corresponding the to the known, it is possible to apply an uv appropriate numerical method logarithmic approach, called well-known bisection equations the hill by some and the to find the method the minimax bisection t-para in numerical are t (/). Here, method, which methods "interval-halving" iterations dale of t-para of [Gera]. to find Recall h and d, respectively. we is based solutions the propose of on a the nonlinear boundary indices of The algorithm consists of three steps: 1. First, we find the boundary range [k,m] of the entry chain (B (/)>0) such that uv the boundary with max_tO lies within it, i.e. he[k,m]. Similiarly, [n,l] contains the corresponding exit boundary with min_tl, i.e. de[n,l]. 2. Knowing the half the boundaries in each from both range pair, ends on the an interval-halving iteration iteration to eliminate such that the range is alternately narrowed way finding the is performed maximum or minimum value. In iteration, the mid-boundary of the range is found and the first derivative t' 1 mid+incr~ mid * l S c o m P u t e c ^- ^ l 'mid * S P° ^ s v e ( 8 ne auve ) > then the the mid-boundary to the next boundary faces uphill (downdale). each = walk from Since we assume 32 that consecutive boundaries are bisection process, is determined as O ^ / j ^ ^ O is identified as (^/_ uv line segment otherwise the - "d- t'^O) a if max_tO>min_tl uv is invisible; In the 0 -and. t'^>0). Comparing max_tO (i.e. t (A)) and min_tl (i.e. t (d)), the zero. m the hill of the t-para and the dale of the t-para 3. not collinear, no ^ ' ^ is equal to intersection coordinates then are computed 3.5b, and 3.5c. using these minmax values. A formal description of the algorithm is given in Algorithm 3.5a, From the discussion in Section 3.4.3, the "find-minimum" of t-para be replaced by the "find-maximum" of t-para in exit tracing can using max_qO=l-min_tl to simplify the implementation. 3.5.2 Time complexity Since after each iteration half of the edges are eliminated, the algorithm runs in time O(logN). However, compute two t-para's this to approach determine has whether a large t (/) constant is factor, increasing or because i t , must decreasing. The expensive l-para calculations result in a reduced efficiency of this algorithm, despite its logarithmic character. Because they can the ranges be computed [k/n] and the two t-para's iX j mi( and t m i ^ + i n c r ) ^ independent, in parallel to speed up the processing time. Furthermore, [nj] have been identified, the operation finding the once minimax values within these ranges can be implemented in parallel. The interval-halving operation might be expensive in software implementation but it is fast when implemented in hardware using a shift operation instead of a divide-by-2 operation. A similar approach has been taken in the midpoint subdivision technique which was implemented in Sproull and Sutherland's Clipping Divider [Spro68] and Clark's Geometry Engine [Clar80]. 33 Chapter 4 T H E T W O - D I M E N S I O N A L S-PARA CLIPPING ALGORITHM 4.1 Introduction In this chapter, a new 2 - D clipping algorithm called the s-para method will be described. This method is based on the segment-line intersection technique in which the idea that if two endpoints of a line segment lie in opposite sides of a line then the line segment intersects this line is employed. We test the edges within the intervening chain to see whether they intersect performed only for the cost for intersecting Similar are to the line segments edges t-para the infinite line L which contains uv. This test is which- can not be trivially rejected. of this method is lower than method, both sequential search applicable; nevertheless, this method is more that of the t-para and bisectional search promising for the The search method. techniques development of a logarithmatic algorithm based on the numerical bisection method. 4.2 The algorithm The s-para algorithm case". Thus, it is necessary case occurs either is a variation of the t-para algorithm for the "worst to replace step 4.2 in Algorithm 3.3. Recall that the worst when an endpont lies inside P and the other lies outside or when both endpoints lie outside P with e^echainl and e^echain2. By exchanging the role of (u\,L.) with (e^-.L), we consider in this section the intersection problem of edges of the intervening chain with the infinite line L. 34 4.2.1 Notation To avoid confusion with the notation which was used for the t-para method, we introduce more notation. __>(v - u , -(v - u ) ) . y y ~ v A inner representation of the infinte line Wj. + s.j(Wj-Wj). The parametric of the Fig. intersection normal vector of L is defined by Let g be any point on L and Wm. be a boundary edge of P. i j r A parametric The point of L containing » » . is given by s^.w^.w.] value s.j is called the s-para in short and L. is defined by the The s-para following equation (see also ... (4.1) 4.1) where G . = _Q-(g-w), H l l = D « ( w . - w . ) . Let F IJ J l 6 = D-g, F. I = J}»w.. F I = J}«w j J then g i H.. = ij F . - F.. = J ... 14 £(g Wj)>0 c(g (4.2) G. - LS L g Wi)<0 LR 7 Fig. 4.1 Basis of s-para method (this example assumes c is on the right to L) 35 Since g can be any point on L, we assume g=u by convention. the parameter A ( / ) in the t-para u method, G . determines f Similarly to in which half plane the vertex w. lies with respect to L. We also use G = r j * ( u - c ) as a reference value to identify the location of w^. such that G ' 0 0 : w. lies on the same side of c with respect to L, G «G .<0: yt. lies on the opposite side of c with respect to L, G •G.=0: w. lies on L (G>0, G.=0). / c Notice that the case where c lies on L ( G = 0 ) does not occur here, c because this case has been accepted in an early stage of Algorithm 3.3. 4.2.2 Initial Let respectively. conditions w f l and be the starting According to the tracing and ending vertices of the intervening chain, direction rule defined in Section 3.4.1, indices a and b can be defined by the indices k and / corresponding to the starting and ending edges and of the intervening chain as follows: if incr= + l then { GXO } a = k b — l+incr { G >0 } else c a — k-incr b = I endif; Points w and correspond to endpoints u and v, respectively (see Fig. 4.1). If fl point u lies outside of P then point w lies on the same side of c with respect to L. fl A similar argument applies for point v and point w^. Ignoring the case where both points u and v lie interior to P, the initial conditions are summarized as follows: 1. i f u * P then G -G >0 else G -G <0 2. i f vtfP then G -G >0 else G - G < 0 sa. f l f e c c fl fl /; 6 JOJ. G G fl+/|IC/ a . - G <0 ' b-incr-° G 6 endif; e n d i f ; 36 3. if u.vt/P then G .G >0 else G .G <0 a { case 4 in Section 3.2 } b fl f c { case 5 in Section 3.2 } o2I. (G .G >0 f l .and. G f c a + t M r ( G . G > 0 and. f l -G Z0) b ss. G.-G^ZO) f c endif; In summary, if u.ve'P then a further test is needed to determine whether uv intersects P at two points or whether it bypasses P; otherwise there is exactly one intersection. 4.2.3 Determination of intersection Let us assume that two adjacent vertices m. and w^. are found to be G. • Gj£ 0. Then the infinite line L intersects edge wlv. at a point z = ° i j v w.+ s..(w -w.), given s.. i ij j by (4.1). This case occurs when line L lies inside the slab formed by L^ Since the chain2 cases where have been intersect the edge both endpoints fall trivially rejected WjHj (see in the Fig. 3.6 exterior again), ij i and L^. region of either chainl or the line segment uv must at exactly the same intersection point, In contrast, if all vertices in the intervening chain satisfy G ^ « G > 0 , c uv) is entirely invisible because ke[a,b], then the line L (i.e. the segment all vertices of the intervening chain fall in the same half plane of point c with respect to L. 4.3 S-para sequential method The naive s-para chain within tracing, the [a,b] method is sequentially tracing the entry chain and/or the exit according to the tracing condition is monitored as vertices change sign. If G.-GSO entry tracing or J=hincr directions defined in Section 3.4.1. During to whether then the edge « x the G-values corresponding to the intersects uv, where j=i+incr for for exit tracing; otherwise the tracing continues. The tracing is terminated if either the intersection edges (one or two) have been found or the entry 37 and exit tradng have met each other. Because the quick reject condition ( is no longer applicable to the s-para method due to the different t e n f r ^- nature > t e X j ^ t of the parameters, all G-values within the intervening chain must be computed and their signs must be tested in order to reject uv. This is the major demerit of this algorithm The formal description of this sequential method has been omitted because of its simplicity. 4.4 S-para 4.4.1 bisection method The algorithm Since the s-para employ the bisection sequential method method is slow in rejecting invisible edges, we to identify the antipodal point R or S which is within [a,b] where G « G ^ > 0 . To simplify the discussion, we assume c is on the right to L f l (incr= + 1 ) as shown in Fig. 4.2, so that we trace the boundaries in the C W direction. A boundary is represented by W J W . , where j=i+incr. In this case, all entry edges are 7 Fig. 4.2 Parameter values G and F of entry and exit boundaries. 38 aiming away from L (H^.<0), all exit edges are aiming towards L (H„>0). If the edge is parallel to L then H^.=0. Therefore, we have G > G ^ . ( F . < F \ ) for entry edges because H..<0 and G . < G . ( F . > F . ) j ij i J i for exit edges because H..>0. 6 Due to this fact ij the parameters G^. and F . are unimodal functions with respect to the vertex indices (see Fig. 4.3a). It is easy to determine whether an edge belongs to the entry chain or the exit chain by comparing the parameter values G or F of its endpoints. The same arguement is applied for the case where c lies on the left to L. that in the former case the parameters value, while in the latter case the G (resp. parameters It should be noted F) has a maximum (resp. minimum) G (resp. F) has a minimum (resp. maximum) value (Figs. 4.3a and 4.3b). The numerical bisection technique is employed in determining intersections based on the unimodality of the function G. vs. / or F . vs. /, ie[a,b]. The algorithm consists of two major steps: Find-podal-point and Find-intersection-edge. intervening chain and check the mid-vertex w^.^ to see different sign intervening than chain G . If c is divided so, the into find-podal-point [a,mid] and First, we halve the whether its G value has a process [mid,b] for terminates intersection and the searching (find-intersection-edge). Otherwise, we check the mid-vertex and its next adjacent vertex w.j,. to see how their G or F values change. Assume c is on the right to L. If nud+incr c c the G (resp. F) values increase (resp. decrease) then the edge e we replace the starting vertex w increase) *rnid' rejected then the edge e -^ m/ o t n e r w (see vertices w fl in Fig. 4.4). * s e tw by W T O -^; if the G (resp. F) values decrease belongs to chain2, we replace the ending (resp. vertex w^, by is parallel to the corresponding boundary edge and thus is trivially Fig. 4.3a and Q belongs to chainl, again). The process iterates shifting both starting closer and closer to L towards the antipodal point R If no intersecting edge is detected and ending (see examples during the halving iterations, then the Fi<F (Gi>0) f l Fi= F ( G i = 0) fl Fi>F ( Gi< 0 ) 0 Fi decreases Gi increases (a) Fi increases Gi decreases accepted case. Fi<F (Gi>0) f l Fi=F 0 (Gi=0) Fi>F (Gi<0) f l Fi decreases Gi increases (b) Fig. 4.3a Fi increases Gi decreases rejected case. G . vs. i and F, vs. / (This example assumes G - < 0 or incr= +1) > Chainl Chain2 } Fi<F ( Gi> 0 ) fl Fi decreases Fi i n c r e a s e s Gi increases Gi decreases incr=-1 i o a b F 0 Fi= F ( G i = O ) 0 exit Fi>F f l J (Gi<0) /\ H\ DOint entry point \ Fi (a) accepted case. Chainl Chain2 Fi decreases' Gi i n c r e a s e s Fi i n c r e a s e s i decreases G F i < F ( Gj > 0 ) g Fi = F fl Fi>F f l (Gi=0) (Gi<0) (b) Fig. 4.3b r e j e c t e d case. G . vs. / a n d F . vs. / {This example assumes G_>0 1 1 or incr=- mid C a s e (a): edge i n t e r s e c t s L ( Gi • Gj < o ). Ranges [e,mid] and [mid,b] are found for intersections. C a s e (b): edge e i does not i n t e r s e c t s L ( Gi • Gj > 0 ). Antipodal point R has been found by moving the v e r t i c e s according to the steps 1, 2 end 3. Fig. 4.4 Examples of visibility testing using G or F parameter. 42 antipodal point R is finally found and uv is rejected because all vertices within the intervening chain including R lie on the same side with c. Find-intersection-edge is to find the zero crossing of the parameter .G after two vertices straddling the line L have been found (their G-values have opposite signs). We can apply a binary search each iteration, partially the visible [mid,b] are to sign again to find the intersection edge w i j of the line segment be searched. Find-intersection-edge G with search parameter two However, is of the intersection for performed the for midpoint is points, case w of two one [ajb]. Even ith C.'CSO. In monitored. For ranges [a,mid] and intersection, though we only might one have G • G / . X ) , the binary search is still valid since G , . - G t ^ O or G _ * G . . <0 a b ' a+incr o a b-incr J always assured in this case. A formal description of the algorithm a is given is in Algorithms 4.1a and 4.1b. 4.4.2 Time complexity Since each iteration eliminates half of the vertices from consideration, the time complexity is O(logN) for both Find-podal-point and Find-intersection-edge It should be F-computations. noted For that an each invisible iteration segment, of Find-podal-point a total of needs procedures. two G- or 2\og(b-d) computations of parameters G or F are required in the Find-podal-point process. For a partially visible segment with two Find-intersection-edge intersection are points, both operations Find-podal-point needed. However, only Find-intesection-edge the case of one intersection point is necessary and for 43 4.5 Comparison of the s-para and the t-para methods Recall that the tests which are s-para methods are different for sequential t- para's corresponding to the the used to identify intersections tracing. boundaries within the minimax values, while the s-para method The t-para in the t-para and method computes the intervening chain and searches for does not need to compute the actual s-para's. Rather, the G—values corresponding to the vertices are tested for a change of sign. We consider the computational cost of the E and F parameters, which require two multiplications and one subtraction, to be equivalent For two adjacent edges e^. and e^., we only need to compute F., F . and F , l calculate E (/), E (/), u v J to obtain G . and G . , while we need to K E (y") and E (y) u to u I obtain t (/) and t (y) (more uv and divisions are required). It is obvious that the than sequential the s-para method in J determining faster than the latter in determining rejections. uv t-para subtractions sequential method is slower intersections, while the former is Hence, it is difTicult to evaluate which one is superior. Despite very expensive employing the due to the binary search technique, fact that two t-computations searching the hill or the dale. On the other to calculate two G parameter finding the intersection parameter is attractive. In less edge than addition, to the that are t-para bisection method is used for each hand, the s-para iteration of bisection method needs values in finding a podal point and one G parameter in for each of achieve the iteration. t-para, faster speed Since the computational cost of the G the we s-para can use bisection the method parameter is F more in the implementation instead of the parameter G . Moreover, the t-computaion needs E(z) and while the s-computation does not need these values. However, the coordinates of the polygon vertices are still needed for the s-para method. 45 Chapter 5 T H R E E - D I M E N S I O N A L CLIPPING WITH A S W E E P - D E F I N E D OBJECT 5.1 Introduction In this chapter, the parametric clipping algorithms mentioned in Chapter 3 and Chapter 4 will be exploited for 3 - D clipping. If the clip volume in 3 - D clipping is a sweep-defined object, then the line-solid intersection problem is easy because of the geometric and topological properties of sweep-defined objects. The 3 - D clipping problem can be reduced to 2 - D clipping in which line segments onto the contour plane which contains the segments are compared with the 2-D in 3 - D clip window. Then, window polygon using any space are projected the projected line standard 2-D clipping algorithm. The technique which reduces the intersection problem is not new, in [Kaji83] ray with sweep-defined objects solved the 3-D ray tracing has 3-D intersection and [Wijk84] problem translational the 2-D the intersection problem of a been discussed for ray casting problem for to applications. Kajiya sweeping (prisms) sweeping (surfaces of revolution) in which the plane curves are and rotational represented by a strip tree. On the other hand, van Wijk introduced rectangle tests for improving detection of a ray with an object defined by translational, conic or rotational sweeping with a cubic spline contour. Here, we will limit the contour to be a convex polygon so that the clip volume is a polyhedron defined by sweeping. Instead of rays of infinite extent we deal with the intersection problem of line, segments with the clip sweeping are treated: translational sweeping and conic sweeping. volume. Two kinds of 46 5.2 Sweep-defined objects 5.2.1 Local coordinate system A section sweep-defined object of an object, can be defined by sweeping a 2-D a a along trajectory (as defined by contour, linear or the cross rotational transformation, or along a space curve). In this thesis, the line contour is described by a convex polygon (clip window); translational sweeping and conic sweeping are employed to create a clip volume. As suggested by Roth, it is convenient to define the clip volume in a local coordinate system such that the objects to be clipped are transformed into its local local-to-scene coordinate axis frame by a transformation to system [Roth82]. In transformed; the scene-to-local which have been detected sweep-defined objects so-called transform this scene-to-local transformation and the clipped object back clip volumes are approach, transformations are to the never by a global explicitly used only to transform those objects to be possibly intersecting with the clip volume. Note that play an important role as primitive objects in Constructive Solid Geometry (CSG)-based solid-modeling systems. Let (x,y,z) be the local coordinate embedded in a plane known as the system. For convenience, the contour plane which is parallel to the contour x-y with z = l . The contour is described as a convex polygon P in terms of its vertices w 2 w^y) by local (x',y')-coordinates coincide with the x- on the contour plane where the x'- and y-axes (Fig. 5.1 and is plane (w,, and y'-axes 5.2). 5.2.2 Translational sweeping In translational sweeping, the plane with plane equation z = z , w contour is assumed to lie initially on the hither to be translated to the yon plane with plane equation 47 z=Zy (Fig. 5.1). By convention, 0 < z ^ < Z y . The sweep thickness h = Z j - - z ^ is called the height of the clip volume. With translational sweeping, the size of the cross section is constant as it is swept parallel to the x-y plane. The clip volume is then defined as the union of the hither plane, the yon plane and the side planes which are described by the set of quadrilaterals (sides of the clip volume) given by the locus of the clip window. In translational sweeping, the position of a point (x,y,z) can be defined in the (x'.y')-coordinates by A x = x\ line segment uv y = ... (5.1) y\ is defined by its two endpoints u(u , u , Fig. 5.1 JC y u) z and v(v , The clip volume with translational sweeping. x v v ) z c l i p window contour plane 2=1 c l i p volume yon plane z=z Y h i t h e r plane z=z H (a) (b) Fig. 5.2 C c o i n c i d e s w i t h 0'. C does not c o i n c i d e w i t h 0*. The clip volume with conic sweeping. 49 after the scene-to-local containing uv transformation. An arbitrary point w(w , w^,, w ) x is parametrically defined by w = and w are projected where u'=u on the line L (l-t)u + tv. The points u, v onto the contour plane to give the two-dimensional representation u'(u' u'), v'(v' v ' ) , and w'(w', w ' ) •* y •* y •* y u' = t[u,v] A z u, v' = denotes the 3-D v, as follows: w' = to 2-D w, ... vector assignment such (5.2) that u ' = u u'=u • * •* y y similarly for v' and w\ By the property of affine transformation, the line L passing through u and v is transformed to become Hence,, the projected a line L passing through their points point w' of the point w is also on the projected point w' is designated by a parameter value t' as w' = local projected (x'.y')- coordinate system. Because of the t'.u'.v*] A orthogonal iT and v'. line L\ The (l-t')u'+ t'v' in the projection property, the ... (5.3) of the following relationship is evident: t = 5.2.3 Conic sweeping The contour: basic idea of conic sweeping is to combine two transformations scaling and translation. The standard scaling of the cross section is defined by multiplying shape t\ the x- and y-coordinates of the cross section is the by same as its the z-coordinate. With original contour conic sweeping, the (clip winodw) but its size is proportional to its z-coordinate. Assuming z>0, the position of a point (x,y,z) is defined in (x',y')-coordinates x = zx', by y = zy\ or xy' Then, = the projected yx\ points u \ ... v' and w' of the points u, v and w are, (5.4) respectively, 50 defined by: u' where = u / u . v' = v / v , w' = w / w , u'=u/u z z ... (5.5) 2 z denotes u' —u /u , x x uy=Uy/u ; z similarly for v' and w\ From (5.4), z we have or [(l-t^+tvj v/' = [(l-tjiy-tv^ k l ^ z + t'v /v , y w' , x then we find ^ t = Substituting parameter w =(l-t')u /u x x l ... , ( x z w* =(l-t')u / u z + t'v / v z into 6 ) (5.6), the t can be computed from t' by t = V v n-f) + u,f ... (5.7) . Equations (5.6) and (5.7) are discussed further in Appendix A. 5.2.4 The t ' - t transform Given a point on the projected line L\ we can transform it back to the original line L by using Equation (5.3) or (5.7) depending on which kind of sweeping is employed. Each point on the line L or the line L' value t or f. This transformation only performed if the intersection is called the t'-t is designated by a transform. point of the projected The t'-t line segment parameter transform is and the cross section has been identified. A detailed proof and discussion of the properties of the t'-t transform are given in Appendix A . Important properties of the t'-t transformed are 51 summarized as follows: 1. if f = 0 then t=0, 2. if t' = l then t=l, 3. if t'e[0,l] then te[0,l], 4. dt/df > 0. Because parameter the First derivative dt/dt' is positive, the parameter t varies with the t* in the same direction (increasing or decreasing). Hence, the minimax values of t nicely correspond to the minimax values of t' if we apply Lemma 2 and 3 in Chapter 2 to the 3-dimensional intersection problem in which the line segment uv tested with the side planes. The properties of the t'-t transform assure that the is 3-D intersection problem can be reduced to the 2 - D intersection problem. 5.3 The 3-D clipping algorithm 5.3.1 Overview In general, the 3 - D clipping algorithm consists of the following steps: 1. transform the line segment (scene-to-local 2. to the local coordinates defined by the clip volume transformation), find the visible segment confined within the hither and yon planes by determining intersections with them, 3. determine intersections with side planes, a. project the visible segment down onto the contour plane, b. determine the visibility of the projected segment with the window polygon, c. find their intersection points and project them back to the local coordinates using the t'-t 4. transform, if visible, transform the results back to the global coordinates (local-to-scene transformation). 52 Steps translating 1, 2 and 4 are the clip volume is achieved segment through scene-to-local straightforward. The effect by scaling, rotating of scaling, rotating and and translating the line transformations. In the geometric modeling system, many primitives have the same shape within a particular type but only the sizes differ from one to another. It is more convenient to normalize them such that "parallelepipeds are all the same unit block in their local coordinate system, arbitrary elliptic cylinders are all the same a right circular cylinder at the origin with unit radius and length, and elliptic cones are all the same right circular cone with unit radius and unit length" in a CSG-based system [Roth82]. For the sake of convenience, we assume ijf=0, in translational sweeping, and z # = £ Z y = l in conic sweeping where 0 < / < l z,y = l such that the contour plane and the yon plane are identical. 5.3.2 Intersections with side planes If the projected line L' intersects the window polygon P at w' then the line L will intersect the corresponding side plane at w by the properties of the t'-t transform. We can identify the position of the intersection point w if we know its projection w\ Let I F be the visible segment within the hither and yon planes. We project the endpoints a and b onto the contour plane to yield the projected line segment jpb' (Fig. 5.3 and 5.4). Determine whether a^b' intersects the t-para with the window polygon P using either method or the s-para method. If they intersect with each other then project their intersection points back to the local coordinates using equation (5.3) or (5.7). It should be noted that the 2 - D clipping algorithm does not actually find the coordinates of the intersection points, but rather know, furthermore, that the line parameterizations their t-para's that designate them. We are independent of coordinate systems after the linear transformations between local and global coordinate systems. For example, 53 Fig. 5.3 Fig. 5.4 Intersections with the side planes of a clip volume with translational sweeping Intersections with the side planes of a clip volume with conic sweeping 54 the midpoint transformation. of a line segment is still This fact implies that step 4 utilizing t-para to designate is given in Algorithms 5. the midpoint in Section 5.3.1 after can the be local-to-scene eliminated when the intersection point A formal description of the algorithm 55 Chapter 6 RECTANGULAR CLIPPING In this chapter, a new rectangular clipping algorithm, called the mapping method, will be presented. In rectangular clipping, the clipping boundaries (lines or planes) are axis-aligned such that the clip window is a rectangle in 2 - D and the clip volume is a rectangular parallelpiped in 3 - D . The mapping method is general and can be extended to higher dimensions. We will describe the 2 - D rectangular clipping in detail and then explain the 3 - D clipping as its extension. 6.1 Introduction In 2 - D rectangular clipping, the clip window is a rectangle coplanar with the input polygon. We can assume, without loss of generality, that the sides of the rectangle are parallel to the x- and y-axes. The interior of the clip window is defined by two pairs of parallel edges ( W ^ , W^) and (W^,, W ^ ) . The interior of the window can be expressed by two inequalities as follows: x. < x < x L x^, ... R H where ff ~ x^, y * y^, (6.1) T y y^, are the x- and y-coordinates top of the window boundaries, respectively. of the left, right, bottom, and The equal sign indicates that the points on the boundary are included within the window. Each of the partitioning the region R is the g 2-D four space interior boundary into of the edges is nine regions extended as window. More to illustrated a in line Fig. of infinite extent, 6.1. The shaded formally, assuming u(u , point in the 2 - D space, the nine regions are defined as follows: x u^) is any 56 4 4 4 ,and. (u >y ) } { u | ( x < u - - x - ) ,and. (u >y ) } { u|(u >x -) -and- (u >y ) } R 4 { u|(u <x ) ,and. (y^<u ,<y ,) } { R 4 4 R a b R c R d R e / R g R. 4 4 4 { n|(u <x ) JC L £ JC ;c y / i J t T y T y L T > 7 { u\(n >x ) jmd. (y <u Zy ) { u\(\x <x ) ,and. (u <y ) { u | ( x < u < x ) .and. (u <y ) { u|(u >x^) (u <y ) x R x L x line segment uv B L ;t i? ,and. y y y y T } B B B to be clipped may be located in any one of these regions or may straddle two or more of them. Depending on the relative locations of its two endpoints, the segment may be entirely invisible (the line segment bypasses the window), Fig. 6.1 The dip window and nine regions. 57 entirely visible (the line segment resides in the window), or partially visible (if the line segment intersects the window at pierces the By touching window). a boundary boundary is taken or one convention which point, it 3, the passes a into account for thrusts into the line segment window vertex intersection window; otherwise which or has coincides one with or is partially visible. For it endpoint a window example, if both endpoints of uv lie on a boundary, then it must be output to the clipped image. In many cases the large majorities or entirely whether of line segments are either visible to the clip window. Therefore, it is important line is for a segment rejected or accepted entirely invisible to quickly determine intersections for improving the algorithm's efficiency. The classical line clipping algorithm due to Sutherland and Cohen uses a four-bit code (outcode) to indicate which of nine regions contains the endpoint of a line segment They utilize the logical "and" operation to reject those line segments which lie entirely in one of the following four groups of blocks: (R , fl R <3" R g^' Newman /' P' R and Sproull R significant amount bypass the which computes rather R ^ c' R [Newm]). of computation window corner. than / i ' R a set explicitly Sutherland-Cohen P^ ee d e t a i l s o f However, before To resolve the of parametric values calculates algorithm. the Liang and dgonthm c (R , Q algorithm performs a those line segments which diagonally Liang and Barsky to R ), Chapter 5 of i n Sutherland-Cohen rejecting this, ^ R^, introduced a technique fast reject line segments of this kind intersection Barsky points reported for a 36 each iteration in percent improvement the of their 2 - D clipping algorithm over the Sutherland-Cohen algorithm [Lian84]. Here, operation we followed propose by a mapping parameter algorithm checking similar which to utilizes the an "interval clipping" Liang-Barsky algorithm to trivially reject invisible line segments for all cases. In the latter sections, we will analyse the 2-D classifications first, then describe the mapping technique and pseudo window, 58 and discuss the t-para conditions for rejection. Finally, the 3-D version of the new algorithm will be presented. 6.2 Classifications for the 2 - D case There are two approaches to solve the clipping problem: to solve individual cases directly or to homogenize the problem, i.e. to formulize a set of cases and solve all in a consistent manner. The first approach can be fast for particular implementation is awkward and error prone, as for degeneracies. version is preferred, particularly in view of possible establish A complete nine regions the its as, e.g., class analysis in order the to a new algorithm which runs fast for the large majority of classes and keeps the regularity and compactness which but Therefore, a generalized compactness Liang-Barsky algorithm. Here, we will elaborate on the 2 - D cases are number enumeration yields C(l) relevant denotes of the implementation. + to the the 9 of the = 45 intersection relative locations two endpoints in the combinations, consisting of six significant classes analysis (see Tables 6.1 case number which corresponds endpoints of a line segment of the fall. Table 6.1 to and 6.2). the regions In Table 6.1, in which the illustrates only half of the combinations due to the symmetric property of the endpoints. The total number of combinations and the percentage out of all combinations of each case are examples of all cases are illustrated in Fig. 6.3. shown in Table 6.2. In cases 1 and 6.b, the line segment is entirely invisible, while in case 2 it is entirely visible. There are classes (cases 3 and 4, cases 5 and 6.a) depending on the simplicity to compute 6 is the most "complex class", In addition, which are two pairs of similar partially visible and are the coordinates of the intersection classified points. Case because it needs further tests to determine whether the line segment bypasses the clip window or pierces the window. 59 It will be assumed that the number of line segments is asymptotically large and that their endpoints probability V are uniformly ° f a line segment m n distributed at random in the 2-D space. whose endpoint falls into region m and the The other falls into region n is defined as: p _ m (area of region m)« (area of region n) (total area of the 2 - D space) n -2 For the sake of simplicity, we can assume that the scene is mapped to Normal Device Coordinates (NDC) prior to the clipping process so that the total area of 2 - D space is 1. In this case, all points are located in a square of unit size ( 1 X 1 ) and the area of a subregion is less than 1. Although this asymptotic analysis shows the probability of all classes for any arbitrary clip window, it is impractical since the probability P definite; it varies region i h 6 6 ^5 1 6 6 6 4 3 1 6 1 1 1 1 1 a b c d e f g h i Table depending on the 6.1 window size and the relative g i 1 6 6 6 6^1 1^ 5 ^ 4 3 e 4 3 4 3 2 ^ d 6 6 1 c 1 1 1 location of the clip D 1 is not 1 1 symmetry case where one endpoint lies in region f and the other lies in region g. Classifications according to regions in which the endpoints he (the number denotes the case number). 60 1 number percentage of of combinations combinations relative location of endpoints case no. two endpoints lie outside the window. 20 description of classified cases the line segment bypasses the window. 44.44% two endpoints lie inside the window. 2.22% the line segment resides in the window. one endpoint lies outside, the other inside. 8.89% the line segment thrusts into the window (simple). same as 3. 8.89% the line segment thrusts into the window (complex). two endpoints lie outside the window. 4.44% the line segment pierces the window (simple). same as 5. 14 31.11% total 45 100.00% Table 6.2 6.a the line segment pierces the window (complex), or 6.b me line segment bypasses the window (complex). Description of classified cases. window in the 2 - D space. Instead of using this analysis, we took the percentages out of combinations shown in Table classified cases. Clearly, the 6.2 as a quick projection for the occurrence mtrinsic nature of the scene greatly of the influences the classification analysis. As an example, for fractal curves which consist of a large number of short vectors, case 6 occurs seldom. 61 From Table 6.2, case 1 and case 6 are two large majorities 44.44 and 31.11 percent cases, Sutherland of the combinations, and Cohen developed respectively. other which cases were ignored. It should be noted the endpoints of a line Dealing with an elegant identification while Liang and Barsky developed a quick rejection segment these technique special for case 1, algorithm for case 6. However, the that once the regions belong, which account for cases are identified to 1 to 5 are trivial to solve, especially for case 2. On the other hand, because case 6 is the worst case, a technique efficiently solving it is of great of interest 6.3 Mapping technique 6.3.1 Region code First, a test is needed segment belongs. which determines Classifications can be achieved endpoints. Instead of the "outcode" the region which represented conclusively class the line by identifying the regions of its two used in the Sutherland-Cohen algorithm, we define by the region code (colour) as follows: { uKx^u^x^) ,and. (y <u<y ) B { u\(x <u<x ) } - R, i v\{y <u <y ) } - R. L R B 2D - ( R where to which y 7 T T }, 3 3 + R +R ), the subscript of the regions J J denotes the region code and 2D denotes the entire 2 - D space. Because of the symmetry 2, and 3 which can be represented of the regions, the region codes are simply 0, 1, by 2 bits in hardware (Fig. 6.2). 62 63.2 2 - D mapping In this section, the mapping technique is described for 2 - D cases. However, it is general and can be extended to higher dimensions. The region code can be easily generated by two interval clipping operations where the endpoints of a line segment are mapped onto the clipping window. Interval clipping is a 1 - D operation defined as: procedure IntervaLClip ( coord, min, max, location_factor; var map_coord, region_code ) begin if coord < min then map_coord = min else if coord > max then map_ coord = max else map_coord = coord region_code = region_code + location_factor endif endif end; where the location.factor is taken as 2 1 , n is the dimension. For example, the YT V B X R Note: the binary number of the r e g i o n code Is represented by t w o b i t s (a MSB and a LSB). Fig. 6.2 Region codes in 2 - D . 63 location_factor p(p , p^) x is 2° for the x-axis, 2 for the y-axis, 1 be the mapped point of a point etc. for higher dimensions. Let u ( u , u^). The 2 - D mapping simply x performs the interval clipping twice, as follows: procedure 2D_Map ( u; var p, N R ) begin NR = u 0; call IntervaLClip ( u , x^, x^, x 1, p , N R ); x call IntervaLClip ( u ^ , y ^ , y ^ , 2, p y N R ^ ); end; The outside returned region codes are those illustrated in Fig. 6.2. If a point the window, it will operation, otherwise W j. or W , be projected the window boundary it remains unchanged. The points within while the points B onto within R will 2 addition, the points within R ^ will be projected while the points within R ^ remain segment can correspond be classified to its endpoints by will be projected onto into the corner resides by the mapping be projected W^ onto or W ^ . In vertex of the window, unchanged. Utilizing the mapping technique, a line the (Fig. 6.3). region codes Examples and/or the mapped points which of mapped points are shown in Fig. 6.4. 6.3.3 Properties of 2 - D mapping The 2 - D mapping has the following properties: 1. The mapping is a projection, hence is not reversable. 2. The mapping eliminates formed by the all invisible' line mapped segments. segments In particular, and returns a polygon a shrunk enclosing image the clip window is shrunk to the window (Fig. 6.4(a)), while a polygon within the window is projected onto itself (Fig. 6.4(b)). 3. The mapping orthogonal generates projection, some if a of line the intersection segment coordinates: enters the because x-boundaries of the (resp. case no. classification conditions 64 N R u * 3 and N R * 3 V case bypass (trivially rejected") 7 i. u#-—• c a s e 2. /u case 3. case case reside u y V «s^ thrust (simple) u thrust (complex) 4. pierce (simple) 5. 6.b c a s e 6. 6.a pierce (complex) 6.b bypass (complex) and { . u * P x [u x = q * py = q y x y x * v x ] o r Vy ] ) NR =NR =3 U V {NR = 3 and [ N R = 1 or 2 ]) or <NR =3and [NR = 1 or 2 ] ) U V v U { NR =3 and [ N R = 0 ] } or <NR = 3 and [ N R = 0 ] ) U v V u {NRu=NR = 1 and P y * q } v y or { NR =NRu=2 a n d p * q v NRu*3 x x ) and N R * 3 V and {\$\< M<l«l> u 6.a Fig. 6.3 NRu*3 and N R * 3 V and (|m|< \$\ or |oc|<|m| } Classified cases and determining conditions. 65 y-boundaries), the x- (resp. y-) coordinate of the intersection point is equal to that of the mapped point of its starting point. 4. The mapped segment of a line segment defines a pseudo window, a portion of the clip window, which will be discussed in the next section. We determine the visibility of a line segment with the pseudo window rather with the clip window. 6.4 Pseudo window 6.4.1 Definition The pseudo window of a clip window formed by the by the 2-D the diagonal resulting from the projection mapping operation. Let p(p , x endpoints n(u , up JC defined by (jp , x paqb (see line segment is an axes-parallel q) y and v(v , \ ) x y and (q^, p^). p^) and q ( q , q ) x y subrectangle of the of the line segment be the mapped points of of a line segment uv. Let points a and b be Then, the pseudo window of uv is the rectangle Fig. 6.5). Both a and b he on the lines passing through p and parallel to (b) (a) o r i g i n a l endpoint. o mapped point. ® c o i n c i d i n g original and mapped endpoint. Fig. 6.4 Shrunk image. 66 the x- and y-axes, respectively. containing the line segments and (5 satisfies a=/3 Let m, a , j3 be the slopes uv, ua, ub, respectively. of the straight line A slope comparison between a or a>/3^0 or O>0>a for all cases (see proof in Appendix B). 6.4.2 Parameters t for pseudo window Let A x = v - u , &y=Vy-\i . x x As shown in Fig. 6.6, a set of t-para's are defined y for the entry boundaries and the exit boundaries of the pseudo window as follows: entry: exit: tpX = (p^-u^) / Ax if Ax*0, tpY (Py-Uy) / A y if Ay*0, tqX = (q -u ) / Ax if Ax*0, ty (q -u ) I Ay if Ay*0. q = = x y x y Notice that the starting point is projected onto the entry boundaries and the terminating point is projected onto the exit boundaries of the pseudo window (Le. the mapped point p is on the entry boundaries and the mapped point q is on the exit boundaries of the pseudo window, respectively). The entry and exit parameters have the form t=A/B. Dealing with the special cases (A=0 and/or B=0), a rule is established as follows: t= + ° ° 4 t The y entr , =0 . =1 exit ^ if (A<0 ^ n d . B=0), t=-» t if (A>0 and- B=0), if A=0, ...(6.2) if A=0. cases B = 0 are considered as if B is approaching G\. These rules are needed for calculating the entry/exit parameters which are compared in order to determine intersections based on Lemma 5 in Section 6.4.3. In fact, t is not necessary to be + » or - » but it must not be inclusive to [0,1], i.e. any value t<0 or t > l is sufficient 4 67 Fig. 6.5 The case B=0 Examples of pseudo window (shaded region). and A * 0 occurs if and only if the line segment is invisible such that the line segment lies in the group of blocks ( R in the group of blocks (R , Q be eliminated if the line R , R) y Q segments 0 > R^, R ) 0 parallel to x-axis or parallel to y-axis. The special treatment (6.1) of this case are identified and rejected can before perforating the t computations (see Section 6.4.4). On the other hand, it should be noted that A = 0 occurs if and only if the endpoint lies in the slabs confined by the extended infinite lines of edge pair ( W ^ , Wj-,) or ( W j . , W ^ ) (i.e. the region code con-esponding to endpoints u and v is not zero). In this case, assuming A x * 0 and Ay#0 (i.e. B#0) the parameters are as follows 68 (rejected) Fig. 6.6 Parameters t p X , t q X , t p V , and t^y for the pseudo window, (see Fig. 6.7): tpx=0 since since since since The cases in (6.2) are a general case of this category, if we consider B=CV rather than B=0. The equations in (6.2) become evident for both cases B*0 and B=0 from this consideration. Note that the case where A=0 for exit boundaries occurs only when the segment u =\ =v =q x x x uv is parallel to xx or u =\ =v =q . y y y y or y-axis (i.e. B=0). In this case we have Therefore, we have b =0 entry ,and. ^ = 1 e x H ) f o r starting endpoint 69 p= u (a) x ; t x =0 x (b) p Py = U y ; t y=0 p termination endpoint • • (c) q = v ; t x = 1 x x Fig. 6.7 the case A = 0 t . entry =t and B=0. . = + » exit q = vy:tqU = 1 (d) q y Special t values when N R ^ O or NR *0. v This is different from the case A * 0 and B=0 in (6.1) giving or 6.4.3 Conditions for intersection using pseudo window Using the pseudo window, the visibility determination of a line segment against a rectangular window can be summarized by the following lemmas: Lemma 4 If a,j3,m have the same sign and |a|£|m|£|/3| uv is at least partially visible to the invisible except that the case 0 = m = a Lemma 5 5 If (t y£tpX q ,and. This expression excludes the special case t^x^y) 6 then the entirely is uncertain. line segment 'This expression excludes the special case (t y = t p X ,and. t x = tpy). q then the line segment clip window, otherwise m=0=a. q s uv is at least 70 partially visible to the that the case (t y = t p X q clip window, otherwise entirely .and. t x = tpy) is uncertain. q The proofs and a detailed discussion of both lemmas are Lemma invisible except 5 is a variation of Lemma 4 using the given in Appendix C. entry/exit parameters rather than slopes. The pair of equalities in both Lemma 4 and Lemma 5 lead to uncertain for cases where m = a = /3. For normal cases when o*/3, occur when only one equality is satisfied (e.g. m=p\ the results the degenerate intersection may |m|<|a|). In general, the t-para comparison method is superior to the slope comparison method due to the fact that the t-para's contribute to the coordinate calculation of the intersection points using Lemma 3. 6.4.4 Trivial rejections Although almost Lemma 5 is general all .cases, i t is still expensive performance, cases which can be and effective to reject invisible line segments of because of the t • computation. To obtain a better trivially rejected should be identified before applying Lemma 5. The line segment which lies in the group of blocks (R^, Rj, R^, R^) RQ) can be easily rejected by knowing that the entry parameters t p X , t p y > l or (R^, or the exit parameters t q X , t y < 0 (i.e. the line segment does not reach the entry boundaries or q the line segment begins after the either mapped window (see into a Fig. 6.8). ( p =o> x x ( Py=^ y The exit boundaries). clip window vertex or By observation, mapped onto a this line segment is boundary of the clip The trivial reject conditions are easily established as follows: a,nd v *u <and x and. x Vy*u y inequalities assure that the q^v^ and. ) sn. q *v y y ) endpoints u and v do not lie in the interior of the clip window including the boundary edges. These conditions are complicated for hardware implementations. A variation of the outcode's boolean-and-operation technique in the 71 Sutherland-Cohen Algorithm can be applied here to form a simple circuitry. Recall that the region code has two bits: second bit from the right). If the boolean is 1 then ( p * u x result a LSB (the first bit from the of the otherwise x and. q * v ) MSB's x of x NR y is false; and "or" result of the LSB's of NR otherwise NR v is 1 true. then Similarly, if the boolean y y q *\ ) y y is "or" false; rectangular clipping algorithm and y-axes. The algorithm algorithm. First, the endpoints are technique. use these compute .and. (p ±Vi Consider the problem of clipping a line segment uv x- and NR true. 6.5 The 2-D the right) and a MSB (the We the corresponding special case of the family t-para's clipping mapped to points p and q using the mapped entry is a to a rectangle aligned with points, and which lie exit parameter on values the window ( t p X , tpy, 2 - D mapping boundaries, t^x and to t^y). Although we can distinguish all classes using the region code and/or the mapped point's coordinates (see Fig. 6.3 again) and handle them individually, it is not the best choice (Px=qx and p * u x o r . (Py=q and P y * u y t t x=tqx g(0,1) p .or. t y = t y e (0,1) p Fig. 6.8 q Trivial reject cases. x and q * v ) y and q * v ) x y x y 72 because an increase in the length of the algorithm decreases the average execution time. Therefore, we divide the six classes into two groups: cases 1 and 2 and cases 3 to 6. The former cases are trivially determined and the computed. We generalize to determine the other intersection coordinates need not be cases by using the entry t-para's and exit t-para's the visibility of the line segment based on Lemma 5 and using them to compute the coordinates of the intersection points, if any. At first glance, one might think the generalized version is slow to deal with the simple intersection intersection appropriate of uv. cases 3 coordinates coordinate can (x- However, this Because the and be where easily or y-) approach parameter 5, a visibility and directly test is not computed necessary by and substituting the of the mapped points into the line equation y = f(x) is not values can adopted here by the be initialized to reason zero or one, mentioned the above. t-computation skipped for the cases where the region code corresponding to u and v is not zero Fig. 6.7 the is (see again). This saves some computations, while determining t values for cases 3, 4 and 5. By this formulization, the algorithm runs fast for case 1 and 2 and is compact for cases 3 to 6. A formal description of the algorithm is given in Algorithm 6. 6.6 Time complexity and parallelism analysis The proposed rectangular clipping algorithm is linear with the number of the line segments to be clipped, since the clipping operation for each line segment runs in constant time for the worst case. In order to explore parallel processing using the mapping method, an execution tree of the algorithm is used. As shown in the Fig. 6.9, pairs of operations are nicely linked in a pipeline. From Fig. 6.9, the regularity and the simplicity of the algorithm also become obvious. The percentages of data flows are adopted form our classification in Section 6.2 for an average analysis. The percentage of 73 interval-clip of point u interval-clip of point v t r i v i a l acceptance parameters t calculation parameters t calculation coordinates calculation 100.00X note: i ) B l o c k s A and B, C and D can be implemented e i t h e r in p a r a l l e l o r in pipelined f a s h i o n . 2) The percentages i n d i c a t e the p r o b a b i l i t i e s of data f l o w s in T a b l e 6.2. Fig. 6.9 Execution tree of 2-D rectangular clipping. 74 trivial the acceptance and rejection line segments are 2.22% and 44.44%, respectively. Assuming of case 6 (15.55%) are rejected on the average, each t that half parameter comparison rejects 7.77% of the total number of line segments. An important observation is that nearly 60% of the line segments are rejected and that it is necessary to perform the coordinate calculations of intersection points on only 40% of line segments. 6.7 3-D extension The clipping 2-D three-dimensions. The clip utilizing the volume is mapping an technique axes-aligned is easy to extend parallelepiped defined by to an additional inequality: Zfj where z^ the 2-D < Z < and Zy ... (6.3) Zy denotes the z-coordinate of the hither and yon planes. Similar mapping, the mapped points p of u and the region code N R the following 3-D y are to found by mapping procedure: procedure 3D_Map begin NR = 0; ( u, p; var NR call IntervaLClip ( u^, x^, call IntervaLClip ( u , y ) x^, 1, p , x N R ^ ); y ^ , y ^ , 2, p^, N R ^ ); call IntervaLClip ( u , z ^ , z , z y 4, p , N R x y ); end; The region code and its corresponding locations are illustrated in Fig. 6.10. After finding the mapped points p and q of the endpoints of line segment uv, the slope conditions are no longer suitable for determining intersections. However, if we project clipping the line segment down onto the x-y problem reduces to two 2-D plane and the y - z plane, then the clipping subproblems by the properties orthogonal projections (see Fig. 6.11). Two sets of conditions for intersection are: 3-D of 75 0 1 0 4 5 4 0 1 0 z* 0 Fig. 6.10 6„ 4 1/1 center=? 1/ 1/ Region codes in 3 - D . Fig. 6.11 Orthogonal projections of the clip volume and a line segment 76 t y>tpX, t x > t p y (x-y plane) t y>tpZ, t z > t p y ( y - z plane) q and q q q where = A* z ( p - u ) / Az if Az#0, = ( q - u ) / Az if Az#0. q formal z tpZ = tz The v -u , z z z z description of the 3-D axes-aligned omitted because of its analogy to Algorithm 6. parallelepiped clipping algorithm is 77 Chapter 7 EXPERIMENTAL ESTIMATION O F T H E EFFICIENCY O F T H E PROPOSED ALGORITHMS 7.1 Introduction The clipping algorithms which were presented in Chapter 3, 4, and 6 have been implemented in F O R T R A N 77 on a V A X 11/750 running V M S at the Department of Electrical Engineering, the University of British Columbia. Since it seemed for us to obtain theoretical veTy difficult estimates for the efficiency in the average case, we decided to estimate the efficiency of our proposed algorithms with the conventional Liang-Barsky clipping algorithm by computational The 1. experiments. efficiency of a 2 - D clipping algorithm depends on the following factors: The nature of the image that is to be clipped: for example, an image consisting of fractal curves. 2. The relative location of the clip window to the image. 3. The relative size of the clip window with respect to the image, e.g. the area ratio being small, medium, or large. 4. The shape of the clip window, e.g. regular or irregular. A scene is normally formed by irregularly distributed line segments and points over the 2 - D or 3 - D space. To simplify the experiments, a non-convex we assume that the scene is polygon with endpoints uniformly distributed at random in the 2 - D or 3 - D space which is defined in a N D C system, i.e. the coordinates are within the range [0,1]. For the 2 - D generalized clipping algorithms, the clip window is a convex polygon with equal sides of length; it approximates location of the center a circle as the number of sides grows. The c of the clip window is located at (0.5,0.5). For rectangular 78 clipping, a square and a cube centered in the N D C space are used for the clip window and the clip volume. The input to the algorithm are the coordinate polygon vertices and its output is the coordinate The C P U times recorded in all experiments array do not arrays of the subject and clip of the clipped polygon vertices. include the time to input the subject and clip polygons, since we assume the data of those polygons are available in storage. They do include, however, the polygon vertices to the output array. time For to the setup 2-D the coordinates of the clipped generalized clipping algorithms, the C P U times include both the preprocessing time and the search time of sector locations. It should be pointed out that the C P U times vary a few percent as the program is run with different loads on the computer. 7.2 Experimental results of the 2-D The sequential t-para generalized clipping algorithms method and the bisection s-para method are the two implemented algorithms which we have used for efficiency estimations. They are simple and efficient bisection for t-para computation clipping method with is of parameters a very t, the polygon of slow a compared bisection t-para efficiency evaluations. For example, in clipping 100 20 sides, the only 0.31 C P U time spent is 0.69 seconds large to number these method is due sides. to eliminated line segments for the of the Since the expensive from further to a clip window of bisection t-para method, while seconds axe needed for the sequential t-para method. Four categories of line segments are used for the efficiency evaluations: 1. Entirely visible: All line segments lie in the clip window and they are totally output 2. Entirely invisible: All line segments are entirely invisible and no output is 79 generated. 3. Partially visible: All line segments have both endpoints outside the clip window and the intersection points with the clip window are output This is a worst case consideration: randomly the line segments which intersect a clip window of 100 sides are generated as the test data. It should be pointed out that for the clip window with small number of sides, e.g. triangular, a large fraction (22%) line segments becomes invisible. However, the data are of the sufficient for testing the clip windows with number of sides greater than 20 since the experimental results showed that only 0.1% of the total number of line segments are invisible for these windows. 4. Normal case: Combination of all cases. We now show computational results of the experiments by varying the area ratio of the clip window and using different categories of line segments each experiment a non-convex polygon consisting of 1000 clipped and the C P U times vs. the Figs. 7.1 to outlined above. In sides (line segments) is to be number of sides of clip windows are shown in 7.8. 7.2.1 Experiment 1: Varying area ratio Area ratio for the 2 - D generalized clipping is defined as the ratio of the area of the circumscribed circle of the clip window to the 2 - D space of the N D C system. The results of the experiments to clip 1000 line segments of normal case for the area ratio 2, 10, 20, and 40 are shown in Fig. 7.1, time 7.2, 7.3 for Liang-Barsky's algorithm is linear with the polygon, while the proposed methods algorithms) realize asymptotic (the complexities: and 7.4, number of sides of the window sequential t-para linear respectively. The C P U and and the logarithmic, bisection respectively. s-para Both 80 t-para sides and s-para is large methods run faster than Liang-Barsky's method when the number of (greater than 50). It is observed that the execution time Liang-Barsky algorithm reduces significantly when the area ratio increases window becomes smaller), while the both new methods run comparatively for the (i.e. the clip in constant time. As a result, the relative improvement of the new methods over the conventional Liang-Barsky method reduces for small clip windows. One of the most important observation is that the search time for the sectors into which the endpoints fall accounts for a large portion (50% to 80%) of the total execution time, while the actual clipping process requires very little time. Therefore, one might think that F O R T R A N is not an adequate language for implementing a binary search. In fact, we simulated a recursive binary search by using a static array as stack and calling two subroutines alternately. If the search time can be reduced by another implementation, e.g. a specialized hardware, the new methods will run much faster. Another observation is that if the area ratio increases, the bisection method becomes more efficient than the sequential t-para method (see Figs. 7.1 s-para to 7.4). It can be explained that if the window is small, there is less chance for line segments to intersect with the the bisection s-para clip window and thus most of line segments method runs faster than the sequential t-para are invisible. Since method for invisible line segments but slower for partially visible line segments (as will be discussed below), the former becomes superior to the latter for clip windows with a large area ratio. 7.2.2 Experiment 2: With differnt categories In this experiment, we tested area ratio (=2). of line segments different categories of line segments with a fixed CPU T i m e 81 VS. N u m b e r of Sides Normal case: area ratio=2 • O "b" LEGEND Liang-Barskv Bisection S-para _ Sequential. T-para Search lime — o 20 40 60 80 100 120 140 160 180 Number of Sides of Window Polygon Fig. 7.1 C P U times for three types of 2 - D generalized clipping algorithms where the area ratio of the window polygons is 2. 200 CPU T i m e 82 VS. u m b e r of Sides Normal case: area ratio=10 LEGEND Liang-Barskv Bisection S-para o _ Sequential. T-para "b" Search lime • o cvj -I 20 40 60 80 100 120 140 160 180 Number of Sides of Window Polygon Fig. 7.2 C P U times for three types of 2 - D generalized clipping algorithms where the area ratio of the window polygons is 10. 200 CPU T i m e 83 VS. N u m b e r of Sides N o r m a l case: area r a t i o = 2 0 LEGEND Lian£-Barskv Bisection S-para O . Sequential. T-jDara " 6 " Search time • o oi —I - 20 40 60 80 100 120 140 160 180 N u m b e r of Sides of W i n d o w P o l y g o n Fig. 7.3 C P U times for three types of 2 - D generalized clipping algorithms where the area ratio of the window polygons is 20. 200 CPU T i m e 84 VS. u m b e r of Sides Normal case: area ratio=40 LEGEND Liane-Barskv Bisection S-para o _ Sequential, T—.para "b" Search time • o -©- w - 20 40 i 60 80 100 120 140 160 180 Number of Sides of Window Polygon Fig. 7.4 C P U times for three types of 2 - D generalized dipping algorithms where the area ratio of the window polygons is 40. 200 85 1. All segments are visible (Fig. Due to the 7.5). fact that the inclusion test of a point against the clip window is simple after the sector to which it belongs is known, the proposed methods fast compared to the Liang-Barsky efficient for clipping an image algorithm. with a large It implies that the new window such that most run very methods are of line segments are entirely visible. It should be noted that this is a best case of consideration and the C P U times of both methods are the same. 2. All segments are invisible (Fig. 7.6). In this case, the experimental show a results indicated that the bisection s-para method slightly better performance than the sequential t-para method. The antipodal point is found efficiently by the find-podal-point operation using the bisection technique in Section 4.4, effective even though one might think the and powerful in the sequential still efficient; as seen in Fig. 7.5, t-para rejection test based on Lemma 2 is method. In fact, this rejection test is the Liang-Barsky runs fast for a large range (N=0 to 80) of number of sides. 3. All segments are partially visible to the clip window of 100 sides (Fig. The results of this case are contrary to the previous experiment: 7.7). the sequential t-para method is somehow faster than the bisection s-para method. It can be explained that the overhead caused by the halving operation is large. For the worst case, N/2 the boundaries are necessary addition to and find a traced in sequence both entry and division of integers, or a total of 2(log(N/4)) halving operations exit it points. is not Each halving operation inexpensive. This consists causes the of of are an bisection method to be less efficient in the software implementation. However, both new methods surpass 40. Liang-Barsky's method for the case where the number of sides is greater than 86 In summary, the proposed methods run faster than the Liang-Barsky algorithm if the number of sides is large. In general, performance than the bisection s-para experimental results bisection s-para of sides is of Figs. 7.6 the sequential t-para than 120. and 7.7 into Fig. 7.8 and the Since convex polygons with computer graphics applications are rare, the sequential t-para In addition, because of its shows better method in our implementation. We combined the method is faster than the sequential t-para greater method algorithmical simplicity the results show that the method when the number large number of sides in method is a good choice. sequential t-para method is suitable for hardware implementaion. 7.3 Vectorization of rectangular clipping 7.3.1 Overview Significant speedup results from the vectorization of computer graphics algorithms [Zago83], [Plun85], and vectorized computer architecture, can [Tran84]. clipping algorithm be segment or each parameter it In order is necessary implemented in to to parallel improve develop due to execution a speed suitable the fact using a algorithm. The that each can be processed independently. Due to the iterative line nature of the clipping algorithm, it is suitable to Single Instruction Multiple Data (SIMD)-type parallel processing, e.g. multiple microprocessor in the supercomputers system G - P S Y C O instruction can be performed on several needed. processors attached processors However, have as this become peripherals and cost kind of [Kubo80]. supercomputer much conventional less than and others, e.g. the In SIMD-type processing, the same data elements, yet only one instruction cycle is available recently, to Cray-1, Cyber 205 is very expensive. Fortunately, called array processors (APs), scalar processors. supercomputers. They The are array vector which can be faster than processors scalar can be CPU T i m e * VS. Number of Sides q 20 40 60 80 100 120 140 160 180 Number of Sides of Window Polygon Fig. 7.5 C P U times for three types of 2 - D generalized clipping algorithms where all line segments are entirely visible to the window polygons with area ratio=2. 200 CPU T i m e 88 VS. u m b e r of Sides o CD . CVJ o A l l s e g m e n t s i n v i s i b l e : area r a t i o = 2 CO. o • CO • O "6" 20 LEGEND Liane-Barskv Bisection S - p a r a _ Sequential. T—jgara Search " l i m e 40 60 80 100 120 140 160 180 N u m b e r of Sides of W i n d o w P o l y g o n Fig. 7.6 C P U times for three types of 2 - D generalized clipping algorithms where all line segments are entirely invisible to the window polygons with area ratio=2. 200 CPU Time 89 VS. umber of Sides All segments partially visible: area r a t i o n • A O b" LEGEND Liane-Barskv Bisection S-nara _ ]3equential_ T-jJara Search time o cvi - 0 20 40 60 80 100 120 140 160 180 Number of Sides of Window Polygon Fig. 7.7 C P U times for three types of 2 - D generalized clipping algorithms where all line segments are partially visible to the window polygon of 100 sides with area ratio=2. 200 CPU T i m e 90 VS. N u m b e r of Sides o d . o invisible or partially visible: area ratio=2 CO . o CD • O LEGEND Lian£-Barskv A Bisection S-nara O . S_e_quentia_l. T-para ~b~ Search lime • 20 40 60 80 100 120 140 160 180 Number of Sides of Window Polygon Fig. 7.8 C P U times for three types of 2 - D generalized clipping algorithms which are the average times of Figs. 7.6 and 7.7. 200 91 controlled by the host computer e.g. vector arithmetic to execute the routines requiring repetitive and logical operations, while scalar operations, operations still take place in the host computer. 7.3.2 Vector version of the rectangular clipping algorithm We have array processor implemented the rectangular clipping algorithm in Chapter 6 on an FPS-100 which is connected to the host V A X computer. Since the AP executes the operations in a pipelined manner, it is efficient for processing a large data array. Furthermore, it is more efficient to force the whole array to perform the same operation rather than to distinguish a small portion of the array to perform a specified task. This indicates that one of the best ways to exploit vectorization is to homogenize the problem, treatment for Algorithm 6 eliminating as the trivial should be many rejection eliminated. special (case cases 1) The and as the formulation minimax value searching of the t parameters like the posssible. trivial of Therefore, acceptance the clipping the special (case 2) in problem into Liang-Barsky method is suitable to vectorization. The coordinate calculation of all valid and invalid intersection points is performed in the AP. Despite the fact that the vector version requires more arithmetic computations than its scalar counterpart, the actual execution time can be less. 7.4 7.4.1 Some notes on the AP implementation Vector codes in APs Supercomputers provide very efficient codes (FORTRAN-like) and conditional branching. For example, addition of two vectors for both arithmetic A and B, with the results stored in vector C, all vectors with N elements, is written in vector code of a 92 Cyber 205 as [Plun85] Q1;N) The vector = A(1;N) + equivalent code of B(1;N). an IF_THEK_ELSE statement is easily converted to vector code as follows: where (C(1;N) .EQ. 0.0) A(1;N) = otherwise A(1;N) = end where On A(1;N) + A(1;N) - B(1;N) B(1;N) the other hand, the AP offers a mathematics library which contains a large number of subroutines for vector/matrix arithmetic and vector logical operations [Apma]. The same vector codes of a FPS-100 call V A D D (AA for the previous examples are: B,b, C,c, N ) { a,b,c are the address increments in the A . B . C vector memorv. CX1;N) = A(1;N) + B(1;N) call V N E G (B,b, D.d, N) call V L M E R G (D.d, B.b, C,c, D.d, N) { D(1;N) = -B(1;N) { where (C(1;N) .EQ. 0.0) D(1;N) = B(1;N) } 1 otherwise D(1;N) = D(1;N) endwhere call VADD (A,a, D,d, A,a, N) { A(1;N) = ) A(1;N) + D(1;N) } From this example , we know the difficulty to convert a scalar code into a vector code for the branching conditions in the AP. It implies that we should eliminate as many conditional branches as possible in the clipping algorithm. 7.4.2 The division problem in the AP Unlike the conventional scalar processors, the AP does not abort a job when an arithmetical error occurs. For example, while the scalar processor is interrupted when attempting to divide a number by zero, the AP actually stores an indefinite number as answer. Table 7.1 shows the division results when using the AP as follows: 93 A B t=A/B 1. *0 *0 A/B 2. >0 =0 + 00 3. <0 =0 —CD 4. =0 *0 0 5. =0 =0 0 Table 7.1 Division results of the AP. Except for case 5 in Table 7.1 the results of all cases agree with rules (6.1) and (6.2). For case 5, the division result is zero for entry parameters t p X or tpy but it is 1 for tqX and t^y. Therefore, a special treatment is needed which converts t q X and t y to 1 q when A = 0 and B=0. 7.4.3 Memory limitation of the AP Note that all the data are input into the A P before processing begins and all results are returned to the host computer after processing ends. The run time of an AP is the sum of the I/O time and computation must store intermediate results time. To save the I/O time, the AP in the AP memory for later use. The memory for intermediate results grows fast according to the amount of the input data. The required space is not insignificant In the rectangular for the intersection test and coordinate clipping algorithm, the memory requirement calculation dimensions and M is the number of line segments is 5nM (words), where n is the to be clipped. Since the FPS-100 has 64K words of main memory in our configuration, it was estimated that a maximum of 6540 and 4360 clipping, respectively. line Note segments can be vectorized that in the FPS-100, for 2 - D and 3 - D rectangular a word is 38-bits long including a 10-bit bias binary exponential and a 28-bit 2's complement mantissa. 94 7.5 Experimental results of rectangular clipping The Figs. 7.9 experimental to Liang-Barsky method, are were tested: 7.17. results of First, algorithm, the the 2-D linear scalar medium, to and 3-D complexities version confirmed in Figs. 7.9 small, and and 7.14. large. of the the Three In rectangular clipping are implemented vector version groups of the each group, four shown in algorithms: of the the mapping clip window/volume sizes of the clip window/volume were used. The area (resp. volume) ratio is defined as the area (resp. volume) ratio of the space. If the clip window (resp. clip volume) to the NDC 2-D (resp. ratio increases, the clip window/volume reduces its size compared 3-D) to the scene. For large clip windows/volumes, the mapping algorithm compared to the medium and small clip windows/volumes (see gained Figs. 7.15 efficiency and 7.16). The large improvement was obtained by the trivial acceptance condition in which the region codes of the endpoints are tested instead of computing t parameters. On the average, the scalar version and the vector version of the mapping algorithm showed a 36 percent and 55 percent improvement percent improvement 3-D for mapping algorithm 3-D for 2 - D clipping, respectively, clipping, respectively. is caused by the overhead and a 26 percent and 49 The decrease in efficiency for the of the for the mapping operation trivially rejected line segments. Since the trivial reject conditions can be tested in pairs with the modified boundary version. mapping The in sequence, improvements algorithm are summarized in Table 7.2. of the the performance mapping will method be over improved the by this Liang-Barsky 95 varying the clip window/volume size 2-D scalar version vector version 3-D scalar version vector vesrion overall best worst averagef maxf 36% 55% 63% 64% 61% 69% 29% 51% 60% average! maxf 26% 49% 58% 61% 58% 63% 17% 40% 51% "{"varying the number of line segments. Table 7.2 Improvement of the mapping algorithm over Liang-Barsky algorithm in 2 - D and 3 - D rectangular clipping. In the vectorization, if the the number of line segments is very large so that the FPS-100's performance is maximized, a significant overall improvement of 63 percent and 58 that percent the against has been gained improvements the number percentages seem to of for the 2-D 2-D of line be converging and 3 - D and segments at 3-D to be around clipping. version clipped 70% An interesting showed a (Fig. 7.17) The number of if the observation is similar characteristic improvement line segments increases (assuming the AP has sufficient memory). This implies that more APs running in parallel are necessary to obtain a higher performance. CPU T i m e % VS. N u m b e r of L i n e Segments o Liang-Barsky's 2-D clipping algorithm c\i • • o A 4 = = = = Area Ratio 1.0 x = 4.0 * 1.5 o = 6.0 * 2.0 v = 10.0 © 2.5 a = 15.0 s 2000 = 25.0 = 50.0 = 100.0 = 200.0 3000 4000 6000 5000 Number of Line Segments Fig. 7.9 C P U times for 2 - D rectangular clipping of the Liang-Barsky algorithm where the area ratio varies from 1 to 200. CPU T i m e 97 vs. u m b e r of Line Segments o 2-D mapping method: scalar version in c\i • • 0 A + = = = = Area Ratio 1.0 x = 4.0 * 1.5 0 = 6.0 * 2.0 v = 10.0 e 2.5 H = 15.0 " 2000 = 25.0 = 50.0 = 100.0 = 200.0 3000 4000 5000 Number of Line Segments Fig. 7.10 C P U times for 2 - D rectangular clipping of the scalar version of the mapping method where the area ratio varies from 1 to 200. 6000 CPU T i m e 98 VS. N u m b e r of Line Segments o 2-D mapping method: vector version in c\i- A r e a Ratio x = 4.0 * = 25.0 o = 1.5 o = 6.0 * = 50.0 A — 2.0 v = 10.0 © = 100.0 + = 2.5 a = 15.0 " = 200.0 • = 1.0 1000 2000 3000 N u m b e r of L i n e 4000 Segments Fig. 7.11 CPU times for 2-D rectangular clipping of the vector version of the mapping method where the area ratio varies from 1 to 200. 6000 CPU T i m e 99 vs. u m b e r of Line Segments Liang-Barsky's 3-D clipping algorithm • 0 A 4 = = = = Volume Ratio 1.0 x = 10.0 * = 100.0 1.5 o = 20.0 * = 160.0 2.0 * = 40.0 © = 200.0 5.0 a = 60.0 = = 400.0 1000 2000 3000 4000 5000 Number of Line Segments Fig. 7.12 C P U times for 3 - D rectangular clipping of the Liang-Barsky algorithm where the volume ratio varies from 1 to 400. 6000 CPU T i m e 10o VS. u m b e r of Line Segments o co • 3 - D mapping method: scalar version Volume Ratio in • o A + = = = = 1.0 1.5 2.0 5.0 1000 x = IO.O 20.0 v = 40.0 H = 60.0 o = 2000 * = 100.0 * = 160.0 ffi = 200.0 a = 400.0 3000 4000 5000 Number of Line Segments Fig. 7.13 C P U times for 3 - D rectangular clipping of the scalar version of the mapping method where the volume ratio varies from 1 to 400. 6000 CPU T i m e VS. N u m b e r of Line Segments 3 - D m a p p i n g m e t h o d : vector = = = •+ = • o A Volume Ratio 1.0 * = 10.0 1.5 o = 20.0 2.0 * = 40.0 5.0 a = 60.0 1000 version 2000 x = 100.0 • = 160.0 © = 200.0 a = 400.0 3000 4000 5000 N u m b e r of L i n e Segments Fig. 7.14 C P U times for 3 - D rectangular clipping of the vector version of the mapping method where the volume ratio varies from 1 to 400. 6000 I m p r o v e m e n t Percentage 102 VS. Area Ratio 1 Pro posed 2-D rect angu lar c lippii ig alj>oritll m LEGEND • Scalar Version A Vector Version: average o Vector Version: max 0) CU) 1 1 i «> k 0* «, 4 A CD E O 11 OH £ 20 40 60 80 100 120 140 160 180 Area Ratio Fig. 7.15 Improvements of the 2 - D mapping method vs. area ratio. 200 Improvement Percentage 103 VS. V o l u m e Ratio 1 1 Proposed 3 - D rect angullar c] ippir ig al|>oritrl m F LEGEND • Scalar Version A Vector Version: average o Vector Version: max CD 1 i, OH «• """"-•< « 4> K CD £ O u ) 20 40 60 80 1 100 120 i 140 I 160 180 Volume Ratio Fig. 7.16 ratio. Improvements of the 3 - D mapping method vs. volume 200 I m p r o v e m e n t Percentage 104 VS. u m b e r of Line Segments o Vector version of rectangular clipping b. 05 o d . CD D A LEGEND 2 - D Clipping 3 - D Clipping 1000 2000 3000 4000 5000 Number of Line Segments Fig. 7.17 Improvements of the vector versions of the 2 - D and 3 - D mapping method vs. number of line segments. 6000 105 Chapter 8 CONCLUSIONS 8.1 Summary The studied. intersection First, parametric method. to solve the of 2-D a line segment generalized line with methods techniques. can be Their convex object problem, two t-para implemented using the computational a clipping clipping algorithms have been proposed: the Both bisection problem are tracing linear been families method and the sequential complexities has of s-para or numerical and logarithmic, respectively. The parallel executability of these methods has also been examined. As an extension, sweep-generated a 3-D clipping against this technique, a truncated can be applied as a a object has been discussed. Using pyramid, which. is often used in the viewing transformation, clip volume. However, the clipping for homogeneous coordinate system with perspective depth transformation is needed to explore. Secondly, to deal with rectangular clipping where the boundaries are axes-aligned, a mapping method so-called conditions pseudo (Lemma was proposed to window rather with 4 and Lemma test the the 5) visibility actual has been clip of a line segment window. established. A The set with of possible the rejection parallel processing and the regularity of the 2 - D rectangular clipping algorithm is shown by the execution tree. Finally, implemented the sequential t-para and their practical and the efficiency has bisection been s-para evaluated methods have by comparison been with the Liang-Barsky algorithm by varying the area ratio or clipping different categories of line segments. For the rectangular clipping methods, a scalar version and a vector version 106 have been applied to implemented. The vectorization implement the estimate the performance vector technique version. Practial of the scalar on an array experiments and vector windows/volumes. Furthermore, the efficiency of the have processor has been been performed to versions with different sizes of clip vector versions on the number of line segments has also been estimated. 8.2 Concluding remarks The computational experiments showed that the sequential t-para bisection s-para method seem to be practical for clipping with a convex number of sides greater than 40. The number of sides can time of sector location is reduced. The bisection s-para method and the polygon of be smaller if the search method is efficient when the number of sides is very large (greater than 120). For showed a rectangular and 36 improvement for 3-D, clipping, 55 percent the scalar and vector improvement for version of the mapping method 2-D and a 26 and 49 percent respectively. The vectorization of the clipping algorithm can take advantage of a cost-effective array processor. 8.3 Future work Based on the proposed t-para or s-para methods, several modifications are possible which deal with the clipping problem for which a non- convex polygon is used for the clip window. First, if the clip window is a star-shaped an interior point c located in its kernel (a collection polygon P, we choose of points which can see all interior points of P) so that the uniqueness of the sector belonging to an arbitary point is assured by the properties of the kernel. Then the visibility of a line segment can be tested by tracing the intervening chain in sequential manner. Since Lemma 2 is no 107 longer effective for trivial rejections, the s-para method should be used because of the less expensive G or F computation. The second approach is to find the convex hull of an image (a concave polygon), then the intersection problem of a line segment with the convex hull can be solved by using the parametric clipping algorithms. If it is possible to find the intervening edge chain of the visible line segment with the convex hull, a similar tracing technique can be applied. A rectangular fast clipper can be obtained by conbining both the generalized and the clipping algorithms. We first clip the image with the circumscribed rectangle of the clip polygon. The invisible segments are easily rejected and a generalized clipping algorithm can be used to detect the visibility of the line segments within the rectangle to construct the actual clipped image. Furthermore, the hardware implemention of the proposed line clipping algorithms using VLSI technology deserves future attention. Finally, the vectorization of the and s-para method on an AP is an interesting topic for future research. t-para 108 BIBLIOGRAPHY [Ahuj80] Ahuja, N . , R.T. Chien, R. Yen, and N . Bridwell, "Interference Detection and Collision Avoidance among Three Dimensional Objects," Proc. of First Annual National Conf. on Artificial Intelligence, Stanford, C A . , 1980, pp. 44-48. [Apma] APMATH38, 1982. [Artw] Artwick, B.A., Applied Concepts in Micro Englewood Cliffs, N.J., 1984. [Blin78] Blinn, J.F. and M . E . Newell, "Clipping Using Homogeneous Coordinates," Computer Graphics (Proc. Siggraph 78), 12(3), August 1978, pp. 245-251. [Boys79] Boyse, J.W., "Interference Detection ACM, 22(1), Jan. 1979, pp. 3-9. [Carl85] Carlbom, I.B., I. Chakravarty, and D . Vanderschel, " A Hierarchical Structure for Representing the Spatial Decomposition of 3 - D Objects," Comput. Graphics and Appl., 5(4), April 1985, pp. 24-31. [Catm78] Catmull, E , " A Hidden-Surface Algorithm with Anti-Aliasing," Computer Graphics (Proc. Siggraph '78), 12(3), August 1978, pp. 6-11. [Chaz80] Chazelle, B. and D.P. Dobkin, "Detection is Easier than Computation," Proc. of the Twelfth Annual ACM Symp. on Theory of Computing, Los Angeles, 1980, pp. 164-153. [Clar80] Clark, J.H., " A VLSI Geometry 13(7), July 1980, pp. 59-68. [Cyru78] Cyrus, M . and J. Beck, "Generalized Two- and ThreeClipping," Comput. and Graphics, 3(1), 1978, pp. 23-28. [Dado82] Dadoun, N . , D . G . Kirkpatrick, and J.P. Walsh, "Hierachical Approaches to Hidden Surface Intersection Testing," Proc. Graphics Interface '82, Toronto, May 1982, pp. 49-56. [Dado84] Dadoun, N . and D . G . Kirkpatrick, "The Geometry of Beam Tracing," Proc. of the First Intern. Sump, on Comput. Geometry, Baltimore. 1985, pp. 55-61. [Dobk83] Dobkin, D.P. and D . G . Kirkpatrick, "Fast Detection of Polyhedral Intersection," Theoretical Computer Science, 27(3), Dec. 1983, pp. 241-253. [Fole] Foley, J.D. and A . van Dam, Fundamentals Graphics, Addison-Wesley, N.Y., 1983. [Gera] Gerald, C.F., Applied Numerical Analysis, 2nd. Ed., Addison-Wesley, N.Y., 1983. AP Math Library Manual, Floating Systems Inc., July Computer Graphics, Prentice-Hall, Among Processor Point Solids and Surfaces," for Graphics," of Comm. Data IEEE IEEE Computer Dimensional Interactive Computer 109 [Kaji83] Kajiya, J.T., "New Techniques for Ray Tracing Procedurally Defined Objects," Comput. Graphics (Proc. Siggraph '83), 17(3), July 1983, pp. 91-102. [Kubo80] Kubo, K., Y. Taguchi, K. Agusa, and Y . Ohno, "Multi- Microprocessor System for Three-Dimensional Color Graphics," Information '80, 1980, pp. 145-150. [Lian83] Liang, Y . - D . and B.A. Barsky, " A n Analysis and Algorithm Clipping," Comm. ACM, 3(1), 1983, pp. 868-877. [Lian84] Liang, Y . - D . and B.A, Barsky, " A New Concept and Method Clipping," ACM Trans. Graphics, 3(1), 1984, pp. 1-22. [Maru72] Maruyama, K., " A Procedure to Determine Intersections Between Polyhedral Objects," Intern. Journal of Comput. and Inform. ScL, 1(3), 1972, pp. 255-265. [Mehl84] Mehl, M . E and S.J. Noll, " A VLSI Support for G K S , " IEEE Graphics and Appl., 4(8), August 1984, pp. 52-55. [Newm] Newman, W . M . and R.F. Sproull, Principles Graphics, 2nd Ed., McGraw-Hill, N.Y., 1979. [Pavl] Pavlidis, T., Algorithms for Graphics and Image Processing, Computer Science Press, Rockville, M d , 1982. [Plun84] Plunkett, D.J. and M.J. Bailey, "The Vectorization of a Ray-Tracing Algorithm for Improved Execution Speed," IEEE Comput. Graphics and Appl., 5(8), August 1985, pp. 52-60. [Roge] Rogers, D.F., Procedural Elements for Computer N.Y., 1985. [Roge85] Rogers, D . F . and L . M . Rybak, " A Note on an Efficient General Line-Clipping Algorithm," IEEE Comput. and Appl, 5(1), Jan. 1985, pp. 82-86. [Roth82] Roth, S.D., "Ray Casting for Modeling Solids," Comput. Graphics and Image Process., 18(2), Feb. 1982, pp. 109-144. [Sham75] Shamos, M.I., "Geometric Complexity," Proc. of the Seventh Annual ACM Symp. on Theory of Computing, 1975, pp. 224-233. [Spro68] Sproull, R.F. and I.E Sutherland, " A Clipping Divider," AFIPS Vol. 33, 1968 F J C C , pp. 765-775. [Suth74] Sutherland, I.E., R.F. Sproull and R.A. Shumacker, " A Characterization of Ten Hidden Surface Algorithms," ACM Computing Surveys, 6(1), March 1974, pp. 1-55. [Tilo80] Tilove, R.B., "Set Membership Classification: of A for Polygon for Line Comput. Interactive Computer Graphics, Unified McGraw-Hill, Conf Proc. Approach to no Geometric Intersection 1980, pp. 874-883. Problems," IEEE Trans. Computers, C-29(10), Oct [Tran84] Tran, C.H., " A n Implementation of an Algorithm for Array Processing: Curve and Surface Definition with Q-Splines," E L E C 593 course project report, Department of Electrical Engineering, the University of British Columbia, June 1984. [Weil77] Weiler, K. and P. Atherton, "Hidden Surface Removal using Polygon Area Sorting," Computer Graphics (Proc. Siggraph '77), 11(2), Summer 1977, pp. 214-222. [Weil80] Weiler, K.., "Polygon Comparison Using a Graph Representation," Graphics (Proc. Siggraph '80), 14(3), July 1980, pp. 10-18. [Wijk84] van Wijk, J.J., "Ray Tracing Objects Defined by Sweeping Splines," ACM Trans. Graphics, 3(3), July 1984, pp. 223-235. [Zago83] Zogorsky, J., "Real Time Graphics with an Array Processors," Digital Design, April 1983, pp. 51-55. Computer Planar Cubic Ill APPENDIX A The parameters t and t' designate the point w and w' where w lies on the infinite line L containing uv and w' lies on the infinite line L\ the projection of L onto the contour plane with the translational or conic sweeping defined in Section 5.2.2 and 5.2.3. The t and t' relationship is shown in Equations (5.3) and (5.7), respectively. In this appendix, the properties of the t-t' transform will be discussed. 1. Assumption We assume that both endpoints are visible to the hither and yon planes due to the fact that the segment which straddles either/both of the hither and yon planes can be shortened the case to a segment where entirely visible to these planes. This assumption eliminates the segment is invisible but is projected the contour plane intersecting the clip window. Therefore, u , v e[z^,Zj,] is assumed and we have u >0 z and onto z z v >0. z 2. Translational sweeping By Equation translational sweeping (5.3), the is simply relationship between t=t\ the properties Then the parameters t of the t-t' and t' for transform is proved straight-forward as follows: 1. if t'=0 2. if t' = l then t = l , 3. if t'e[0,l] then te[0,l], 4. dt/dt'>0 since dt/dt'=l. The projected then t=0, third property assures the point w lies point w' lies on the projected on the line segment uv, if its line segment Irv.' Because the first derivative 112 (dt/dt') is accordingly. projected the positive, Thus, if t' if f increases (resp. is the minimax segment u V with the minimax value for the decreases) value for then the increases 2-D window polygon P, then 3-D t the (resp. entry/exit decreases) point corresponding of the t designates entry/exit point of the original segment uv with the side planes created by sweeping the polygon P. 3. Conic sweeping Let point w' be the "valid" intersection point of line segment uv and window polygon P in the contour plane. The parameter t designating point w can be computed from the coordinates of point w' using the following equation: t = ... This equation is not valid for the v *u z z case v = u and v =u Y then the parameter t can be computed by t^= t computation is needed the former case w z line segment uv By = (w ~u )/(v -u ); z z v z z Fig. A.1). u„z /w' if w' * 0 and w' * 0; y Y y x y v v w' = ( l - ? ) \ i / u x x the right side of Equation (5.6) otherwise, no Note that in otherwise, A / + z t'v^/v.,, w'^= ( l - t ' ) u ^ / u + z t'v / v z and assuming u > 0 and v >0, we have z z B, where A = u ,[(l-t')u /u J JC = ( *V *V v B = if the is parallel or collinear to ow' and point w' is an invalid intersection. substituting t = . In this case, however, because point u and v coincide (see u z /w' = x Y x (5.6) u z t , / v +fv /v ]-x 2 u [(l-t')u ,/u + x > z t'vyv ] z z- (V^UjUl-VUy/^+t'Vy/Vj - (Wy-Uy)[(l-OU /U + x z t'W^V^ into 113 = (v^-u^vpf (l-t')/u z + t7v ]. z Dividing the numerator A by the denominator B yields t ... = v (l-f) + z Equation (5.7) (5.7) u t' z denotes the correspondence divide-by-zero errors if t'= v / ( v - u ) z z between parameters t and t'. It causes and v # u , i.e. the line segment uv is parallel z z z to ow' as shown in Fig. A.2. By assumption u > 0 and v >0, the parameter value t' is z greater than one if v > u , z otherwise less than zero. In both cases, point w' is not a z valid intersection point and, therefore, the t-t' In summary, both Equations (5.6) transform once the "valid" transform (5.7) and (5.7) intersection treatment is needed for (5.6) Equation (5.7) z point w' is not performed. can be used for the t-w' is identified, except that a or t-t' special when uv is parallel to z-axis. In the implementation, only is used. Its properties are examined as follows: 1. if t' = 0 then t=0, 2. if t' = l then t = l , 3. if t'e[0,l] then te [0,1], Proof. By assumption u > 0 and v >0, the numerator and the denominator of the z z right side of Equation (5.7) are greater than or equal to zero. So we have teO. Dividing both the numerator and the denominator by u t', we have z t = 1 / [ v (l-t')/u t' • + z Since v ( l - t ' ) / u t ' £ 0 , we have z 4. if u = v 5. dt/dt* > z z z then t=t' 0. z 1 ]. Ul. (equivalent to translational sweeping), Q.E.D. 114 Proof. The first derivative is dt _ u [(u -v )t' + v ] z z z dt' z z intersection z translational point w' designates z planes of the clip volume. z sweeping, the + z z v ] z z 2 v 0 since u > 0 and v > 0 to 2 z z [(u -v )f Similar (u -v )u f [(u -v )f u dt/dt' > - z + v ] z 2 are assumed. the entry/exit parameter Q.E.D. t corresponding point of line segment uv to the with the valid side 115 1 Z=Zy w' v' u" t = w - "2 z vz - u z where w =u zy/ w' z x x = u z / Wy y Y x or y Fig. A.1 Z=Z Case u =v and u =v V" Y •1 \ • / ••t •. / •• v• t • • // • / u" J X/ y u : • Fig. A.2 x or y Case uv parallel to ow* or ( f = v / ( v - u ) z z z And- u * v z z ). 116 APPENDIX B Given a line segment defined by two endpoints u(u_ , u^) x the mapping technique, respectively. q ) y v points u and v are mapped The pseudo window defined by the and b(q , p ) *• y r such that pa v to p(p , x and v(v , \ ). P) q(q , x y and diagonal pq has other Using y x q^), vertices aCp^., is vertical and pb* is horizontal. We assume that the vertical line has positive/negative infinite slope and the horizontal line has zero slope by convention. Here, we intend to prove valid for all cases, where a ua and 0 that a,/3 have the same sign and |a|^||3| is aie the slopes of the lines containing the segment and ub respectively. Proof. Let A x = v - u x segment uv Ay = v y - v ; r x Ax^q^-p^, Ay' = q ^ - p ^ . The is defined by m=Ay/Ax. The possible relations of a slope and 0 in Fig. B. It is necessary to classify and verify all cases for values a £as£_L: \a\*\fi\ is a vertical line are illustrated and /3. (AxVO and AyVO) A key observation is that sign(Ax)=sign(Ax') pa of the positive vector if Ay>0, and sign(Ay)=sign(Ay'). otherwise negative; analogously, Therefore pF is a horizontal positive vector if Ax>0, otherwise negative. The slope comparisons are based on the decomposition of the vector ua = u p + p a , iirJ = up+pF. Case l.a: N R = 3 (point u lies within the clip window). U In this case, because slope(ua)= +<*> or - » Case Lb: As m>0 shown p=u thus ua=pa (vertical) and uF=pF (horizontal), and slope(uF)=0. Therefore, we have |a|>|/?|. (Ax>0 and Ay>0). in Fig. slope(ua)=slope(up) = + o ° B, because if u =p , x x pa otherwise is vertical and positive, slope(ua)>slope(up)>0; similarly 117 pb is horizontal and positive, slope(up) =slope(ub) =0 if u =p , y y otherwise slope(up)>slope(uF)>0. Combining all of these, we have slope(ua)>slope(uH)^0 or a>/3^0. Case l.c: m>0 (Ax<0, Ay<0). Similiar to case Lb, we have a>/3^0. Case l.d: m<0 (Ax>0, Ay<0). Similiar to case Lb, we have 0^j3>a. Case I.e: m<0 (Ax<0, Ay>0). Similar to case Lb, we have 0^/3 > a . CaS£_2: \a\*\0\ (Ax' = 0 or Ay' = 0). This case occurs when both u and v lie on the left of W ^ , on the right of W^, undeT W ^ , or over W j , . The vector decomposition is similar to cases L b to I.e except that pF or pa is a null vector because Ax' = 0 or Ay'=0. The slope comparisons can be summmaried as: slope(ua )^slope(uF)^0 or a^j3^0. or 0^slope(ub ^slope(ua ) or 0>/3>a. Case 3: a = /3 (Ax'=0 or Ay'=0). These special cases occur either in case 3.a: when p=q (Ax' = 0 and Ay'=0) or in cases 3.b and 3.c: when pq is vertical (Ax' = 0) or horizontal (Ay' = 0). In both cases ua and uF coincide with each other, hence a=P In summary, we have a = /3 or-a>/3>0 is easily found (see Fig. B). or 0^/3>a from all cases presented above. The inequalities can be combined into the simple form a * 0 ^ 0 and |a|^|/J| for all cases. Q.E.D 118 iA Q (cose l.o) NR =3 U |oc| > 1 ^ | (cose l.b) (cose l.c) Ax>0,Ay>0 Ax<0,Ay<0 : b b "7pi|||| l«|>|£| l«l>l$l (cose l.d) (cose I.e) Ax>0, Ay<0: * locf >|^| a loci > 1^ 1 q q«a C 'a v (cose 3.0) Note: Ax=0,Ay=0: a = £ ^ m. x y Ax=0, Ay'^o « =A B Ax = v - u A y = Vy - Uy Ax'= q - p Ay"= q - P =m x x (cose 3.b) Fig. Ax<0,Ay>0: ^ Sr—©T ® Classified cases for determining a * 0 ^ 0 x y (cose 3-C) v Ax'^Ay'sO ^ ^_ and |a|£|0|. oc = £ = m 119 APPENDIX C Lemma 4: If a,/3,m have the same sign and |a|>|m|^|/3|\ then the line segment uv is at least partially visible to the clip window; otherwise entirely invisible, except that the case m=a=|3 is uncertain. Here m, a , 0 are the slopes of the straight line containing the line segments uv, ua and ub, respectively. Proof. From Appendix B, we know that a* 0^0 Ignoring the special case a=/3, and |a|^|/3| is valid for all cases. let us consider the angle 6 defined by two vectors ua and ub". It is clear that if the vector uv lies in the sector with angle 6 (i.e. m«a>0 and |a|^|m|^|/3|), it must intersect the pseudo window and intersect the clip window as a consequence. In fact because the endponts u and v are located in diagonally opposite regions (see Fig. B cases La to I.e), the line segment uv must reside in or intersect with the pseudo window. On the other hand, if the vector uv sector with the angle 6 (i.e. m « a < 0 or { m « a > 0 lies in the outside the and (|m|>|a| or |m|<|/3|)} ), then no intersections occur. In this case, the line segment is exterior to the pseudo window and consequently it is invisible to the clip window. All classes (as defined in Table 6.2) are tested and verified in Fig. C . l . In the case a = p\ both up and uq coincide with each other. If m * a = 0 , line segment uv does not he on either up or uq. Therefore line entirely invisible (see Case 3.a containing through the points p and q which does not uv passes in Fig. B). However, m=a=/3 the uv implies that the line guarantee is L that uv intersects the clipping window (see m=a=/3 is not a sufficient condition for intersection testing. This case must be treated 'This expression excludes m = a = p \ Cases 3.b and 3.c segment in Fig. B). Thus, the condition 120 separately. Q.E.D Lemma 5: If ( t ^ y ^ t p X and- t q X > t p y ) , then the line segment uv 2 is at least partially visible to the clip window; otherwise, entirely invisible, except that the case (tqy = t p X and. t q X = tpy) is uncertain. Here t p X , tpy, t q X and t^y are defined as in Section 6.4.2. Proof. 1. accepted First, for we consider intersections the slope m, a, Ax*0 and A y * 0 . if a,/3,m have the From Lemma 4 the line same sign and |a|£|m|>|0|. segment is Notice that j3 can be written as follows: m = Ay / Ax, a = fy-iip P = (Vy-u ) / (jp -u ), x i y x (q -u ) x x The intersect condition of Lemma 4 can be rewritten as > Ay > Ax Vx~ x u We separate them into two inequalities as follows: > Ax Ay > Ax Vy-»y Ay then we have 'This expression excludes both equalities. ... (C.1) 121 m*oc=£ u (rejected) case 1 m=a=£(rejected) case 2 l«| 2|m|> |£| accepted. a>£>m (rejected) £( accepted) case 3 M2|m|2|£l accepted. case 5(a) M2|<m|2|*l accepted. case 4 W2|m|>|^l accepted. e. JI * case 5(b) kx|>|m|> |£| oc case 6(a) |m|2kx| or i^U|m| rejected. accepted. V case 6(b) W>|m|>l^l accepted. J v. CI " ' Classified cases for determining a , p \ m nave the same sign and M * M * | * | . 122 and Since I V I* Iy | Iv * V 1 a,0,m 1 have the same determining intersections. without using absolute ... sign, in and q t^x-tpV^O to simplify (C.3) should to the be tested for following inequalities expressions: (C.4) are ... (C.4) ) q inequalities t y»tpX>0 However, we try ( t y^tpx and. y^y The (C.3) 1 verified for all cases: if the line segment is partially visible (intersect) or entirely visible (reside) to the clip window, then the inequalities are true; otherwise, • false. Case p*q: We know all the intersect or reside the inequalities t-parameters cases (see in (C.3) eliminated given t y > t p X q must we 0 t x<0 q have are positive, R , 0 If ; the range [0,1] for both left and right sides absolute expressions can be tpy*t ye[0,1] q to contradict t x £ t p V q (see Fig. C.2b). (resp. t y ^ t p X ) . q Then, if The same line segment lying in the group of blocks R ). 0 line L q containing uv passes through the mapped points, we q t x#tpy for the q reject of R n and q leads lies in the group of blocks ( R , t y = t p X and t x = t p V for the uncertain case (m=a=/3); otherwise, or the q argument can be applied to the (R , the the and t x £ t p y . tpX=t x*[0,l] (resp. t p X > l ) within Fig. C.2a). Since For the reject cases, assuming uv R ) be case then contradicts t y=tpy. q reject case ( m * a = / J ) . t y>tpX, q t x>tpy, q and have t y * tpX q Assuming (C.4) is true for tpX=t x t y>tpy q leads q the which 123 2. Now, lei us consider the case Ax = 0 or y-axis). uv lies or Ay = 0 (i.e. uv" is parallel to 3 Assuming Ax=0, to avoid division by zero we assign t p X = 0 in the slab or - » tpX = t q X = + ° ° formed (see by the Section 6.4.2 extended lines of (W ^ , x- and t^x=l if W ^ ), otherwise for details). To simplify the discussion, only +°> value is used. • Case p*q: (see Fig. C.3a). The p line segment resides in or intersect with the window, the mapped point and q must t x> t^y knowing tpX=0 given t^y, tqy e[0,l]. leads line segment lies outside the clip window. We have t p X = t q X = + = > Case p=q: We have t p X = t q X and This The tpy,tqye[0.1]; therefore t q y ^ t p X = + ° ° • uv t^x q by segment t y^ q and lie within the tqX=l. and can not be satisfied. and tpy=tqy (see Fig. C.3b). u and v lie in region 1. It is easy to find that L passes through p and q vertically. In contradicting The this case tqX>tpy; if if it lies mapped point behind then lies ahead tqy<l uv then contradicting tpy>l tqy^tpX. accept condition for this case is tpy = tqy=0 or 1. v and u lie in region 0. tqy^tpX The the is Since we know t p X = t q X = + ° ° and t^y =tqy«'[0,l], false. discussion on the case Ay = 0 is omitted because of its analogy to the case Ax=0. In summary, we have proved that the conditions tqy^ t p X and t q X > tpy determine the visibility of line segments for all cases except that (tqy = t p X ,and. t q X = t p y ) yield uncertain results. Q.E.D. 3 The case A x = A y = 0 is not considered here. 124 Discussion Observe that the conditions in Lemma 5 agree with that in Lemma 2: 0 < max( t p X , for intersections. Note merit of this method), (see Fig. C.2a). property y ) < min( t x, t y ) < 1 q that range checking q of these t-para's is eliminated (the major because for the visible cases they are explicitly inclusive to [0,1] Furthermore, t x > tpX and t y ^ tpy q q are assured as the line segment crosses the window boundaries: visible to W ^ and then t x>tpX q or is visible to by the mapping if the line segment is and W ^ , then t y^tpy. q Then, all these properties and the inequalities in (C.4) satisfy the conditions in Lemma 2. Lemma 5 provides an efficient testing segment with only two evaluations which can reject a diagonally bypassing line of t for the best case, while Lemma 2 needs at least three evaluations of L The uncertainty of the case where t y = t p X = p q by range checking: if p = ae[0,l} then and t x = tpy=o can be clarified q max_tO=min_tl e[0,l] and uv touches the clip window at a point, otherwise uv is invisible (see Fig. C.4). However, we are trying not to test the t-para's with the range [0,1] algorithms but to fully use the properties as in the Cyrus-Beck and the Liang-Barsky of the 2 - D mapping. In fact, we trivially reject the invisible line segments of this case before applying Lemma 5 by using other simple conditions (see Section 6.4.4). 125 a q Ax<0,Ay<0 Ax>0,Ay>0 tpx,tqxe[0,1] i h t p y , t y e[o,1] b Ax>0, A y < 0 t x,tqxe[o,1] d p tpy,t y e [ o j ] q q Ax<0,Ay>0 tpX,tqXE[o,1] tpy,t y6[o,1] * q la t x,tqXE[o,1] tpy,t yG[o,1] p q q Fig. C.2a p*q, A x * 0 , A y x O (acceptcases) Note: tpx=tqx<0 t y,t y e [ 0 J ] p tpx=t x>i q q t y , t y e[o,H p Fig. C.2b p*q, q Ax*0,Ay*0 (reject cases). p=<* e[o,i] u note: (rejected) t q y * t x or p tqxxtpy (rejected) tqy=t x=p tqx=t y=a p p p=tf e [0,1] (accepted) Fig. C.2c P=q, A x * 0 , A y * 0 (uraertaiii cases). Fig. C.2 Case A x * 0 and A y * 0 . Ax = v - u Ay = V y - U x x y u f t y<t x or q tpx=tqx=+oo t. p I tqx<t y p tpy=tqy^[Ojr" (rejected) (rejected) Note: Ax = v x Ay = v y tqy=t x=0 p tpy=tqx=1 (accepted) (accepted) Ax=0 t p y = t q X = 0 (accepted) V t q y < t x or Y t q y=tp X= p t x<t y q - p tpy=t y=+oo q (rejected) tpx=tqxg[0,1] (rejected) Ay=o Fig. C.3a Case p * q , A x = 0 tpy,t q y G orAy=0. [0,1], tpx=0, tqx=1. - 4 + — tpx =tq x =+oo .../IT® ® tpy,tqye[o,l] u Ax=0 tpx,t xe q [o,1], tpy=0, t y = 1 . q '* ®—® l py =tqy=+oo^ Fig. C.3b Fig. C.3 1 (accepted) Cose p=q, Ax=0 or Ay =0. Case A x = 0 or A y =0. o x y final i l tpx tpy i tqx • i tqy mi3x_tO 1 miri_t1 1 • mex_tO=max ( t x , t y ) p min_t1=min tqx > tpx if t y p C.4 (t x,t y) q q and t q y > t p y are assured, = t x .and t y q p = q Fig. p q and t x p max_tO=min_t1 • Case t y = t p X q r and t x=tpy. q then t 128 APPENDIX D LISTING O F A L G O R I T H M S This Chapters 3 appendix to 6. contains The clipping a listing of algorithms algorithms are which described by have one been or discussed in more procedures which are written in PASCAL-like high-level pseudo codes. Algorithm Page 3.1 Line_visible (using predicates interior, aim, and cross) 129 3.2 Line_visible (using E parameters) 130 3.3 T_clip 131 3.4a Trace_boundary 132 3.4b T_sequential 133 3.5a Find_range 134 3.5b Find_max_t 136 3.5c T_bisection 137 4.1a Find_intersecUon 138 4.1b S_bisection 139 5 3D_clip (clipping sweep-defined objects) 141 6 2D_clip (rectangular 143 clipping) 129 Algorithm 3.1 Procedure Line_Visible (u,v,i; var visible(uvJLj), tO,tl) { function: this procedure tests the visibility of a line segment uv w.r.t a boundary Lj using predicates Interior, Aim, and Cross. input* the endpoints u(u ,Uy) and v(v ,v ); boundary index i. output tO and tl corresponding to the endpoints of the visible segment visible(uv,Lj)=true if visible, otherwise false. } x x y begin 1. initialization visible(uv,Lj)=true, t0=0, tl=l; 2. compute E (i) and E (i) E (i)= fii'U E (i)=£rv u v u v 3. determine the visibility of the line segment uv with respect to the boundary Lj. A (i) = E(i) -E (i); B (i) = E (i)-E (i); u u uv v u if aim (uv,Lj) .and, cross (uv,Lj) then t (i) = A (i) / B (i) { partially visible } if interior (u, Lj) then tl=t (i) { exit point } uv u uv uv else else endif uv { entry point } if .noi. interior (u, Lj) then visible(uv, Lj)=false else endif endif end; tO = t (i) { entirely invisible } { entirely visible } { end of procedure Line-Visible } Algorithm 3.2 130 Procedure Line_VisibIe (u,v,i; var visible(uv.Lj), tO.tl) { function: this procedure tests the visibility of a line segment uv w.r.L a boundary Lj using E parameters. input: the endpoints u(u ,Uy) and v(v ,v ); boundary index i. output: tO and tl corresponding to the endpoints of the visible segment; visible(uv,Li)=true if visible, otherwise false. } begin 1. initialize visible(uvj-^)=true, t0=0, tl=l; 2. compute E (i) and E (i) E (i)=fii«u, E (i)=e. v; x u x y v u v r 3. determine the visibility of the line segment uv with respect to the boundary Lj. if { B (i)>0 } { cross=false: E (i)<E (i)<E(i) { entirely invisible E (i)<E (i) then if E (i)<E(i) then visible(uv,Lj) = false else ifE (i)<E(i) then u uv v u v v { cross=true: E (i)<E(i)<E (i) { partially visible tO = (E(i)-E (i)) / (E (i)-E (i)) else { A (i)<0: E(i)<E (i)<E (i) { entirely visible endif endif { end of entry or parallel boundary } else { E (i)<E (i) or B (i)<0 if E (i)<E(i) then { A (i)>0: E (i)<E (i)<E(i) visible(uv,Lj)=false { entirely invisible else if E (i)<E(i) then { cross=true: E (i)<E(i)<E (i) { partially visible tl = (E(i)-E (i))/ (E (i)-E (i)) else { cross=false: E(i)^E (i)< E (i) { entirely visible endif endif { end of exit boundary } endif { end of all cases } end; { end of procedure Line-Visible } u u u v v u u v u u v u u v uv v u v u v u u v u Algorittaa 3.3 Procedure T-clip (u,v; var max_tO, mintl, accept) { function: this procedure outlines the t-para clipping algorithms, input the endpoints u(u ,u ) and v(v ,v ). output: max_tO,min_tl corresponding to the intersection points; accept=true if visible, otherwise false, note: the clip polygon data BT, Table(£j), TablefEj) are pregenerated and stored. } x v x v begin 1. compute the slopes of cu and cv, then identify the sectors e^ and e| corresponding to u and v by a binary search of BT. 2. initialization accept=false, u_interior=false, v_interior=false, max_tO=0, min_tl=l, max_qO=0; 3. trivial rejection call Trace_boundary (u,v,k,max_tO,l,accept,u_mterior) call Trace_boundary (v,u,l,max_qO,l-max_tO,accept,v_interior) min_tl=l-max_qO 4. if accept .and. k*l .and, .not (u_interior .and. v_interior) then 4.1 determine tracing direction G = D.(u-c) case of G <0: incr = +1 >0: incr = -1 =0: goto 5 endcase c c 4.2 tracing process call T-sequential (u,v,incr4c,l,u_interior,v_interior, max_tO,min_tl, accept) or call T-bisection ( u,v,incr,k,l,u_interior,v_interior, max_tO,min_t 1 .accept) endif; end; { end of procedure T-clip } Algoriilhim 3.4 a Procedure Trace-boundary (u,v4; var maxtO, min_tl,accept,terminate) { function: this procedure tests the visibility of a line segment uv w.r.L an entry or parallel boundary Lj. input: the endpoints u(u ,u ) and v(v ,v ); maxtO, min_tl. output max_tO corresponding to the intersection point; accept=true if visible, otherwise false; tenninate=true if the entry tracing is to be terminated, otherwise false, note: this procedure is called if accept=true and terrninate=false; assume E (i)<E (i) for entry tracing (uv aims towards ej). } x u v x v v begin 1. compute E (i) = £j • u ; 2. if E(i)<E (i) then terminate = true u { u is interior to Lj: entirely visible } u else compute E (i) = £j • v if E (i)<E(i) then accept = false v { cross is v else t (i) = (E(i)-E (i)) / (E (i)-E (i)) { ^ntry^xit ) if t (i)>min_tl then accept = false if t (i)<max_tO then { t-para: decreasing or equal } terminate = true { t-para: increasing } else max_tD = t (i) uv u v u uv uv uv endif endif endif endif end; false: entirely invisible } { end of procedure Trace-boundary } Algoritihumi 3.4 b Procedure T-sequential (u,v,incr,k,l; var entry_term, exit_term, max_tO, min tl, accept) { function: this procedure sequentially traces entry boundaries from e^ according to +incr direction and exit boundaries from e| according to -incr direction input: the endpoints u(u ,u ) and v(v ,v ); entry_term,exit_term; k, 1 and incr. output: max_tO,min_tl correspond to the entry and exit points ; accept=true if visible, otherwise false, note: this procedure is applicable to case 4 and case 5 in Section 3.2 } x v x v begin 1. max_qO = 1 - min_tl; 2. while accept .and- l*k+incr .and- -not (entry_term .and- exit_term) then 2.1 entry tracing if (.not. entry_term) then k=k+incr call Trace__boundary (u,vJc,max_tO,l-max_qO,accept,entry_term) endif; "" 2.2 exit tracing if (.ncl. exitjerm) .and, accept then 1=1-incr call Tracejboundary (v,u,l,max_qO,l-max_tO,accept,exit_term) endif; ~ endwhile; 3. mintl = 1 - maxjqO; end; { end of procedure T-sequential } Algorithm 3.5 & Procedure Find_range (u,v,incr, var k,l,tjr,tj_, m.n.tjjjjtj,, entry_term, exit_term, accept) { function: this procedure bisectionaUy finds the range [k,m] containing the hill and the range [n,l] containing the dale of the t-para. input: the endpoints u(u ,Uy) and v(v ,v ); entry_term,exit_term; [k,l] with [tfc.tjj and incr. output the entry range [k,m] with [t^,^] and the exit range [n,l] with [t^]; accept=true if visible, otherwise false. } x x v begin 1. while accept .and- (l-k)mcr>l .and.not, (entry term .and. exit_term) then mid = (k+l)/2 ~ compute B (mid), A (mid) if B (mid)=0 then { e ^ is parallel to uv } if A(mid)>0 then { rejected } accept=false uv u uv u else m=mid-mcr, t =t (m), entry_term=true { range [k,mid-incr] } n=mid+incr, t =t (n), exit_term=true { range [mid+mcr,l] } uv m uv endif goto 3 endif n t (mid)= A (mid) / B (mid) uv u uv 1.1 shifting entry boundaries if B (mid)>0 .and- entry_term k=mid, t =t (mid), goto 2 uv uv then k endif 1.2 shifting exit boundaries if B (mid)<0 .and- exit_term then l=mid, tx= t (mid), goto 2 uv uv endif 1.3 halving iteration midl=mid+incr compute B (midl), A (midl) if B (midl)=0 then { e , ^ is parallel to uv } if A (midl)>0 then { rejected } accept=false uv u uv u else m=mid, t =t (mid), entry_term=true { range [k,mid] } n=midl+mcr, tn=t (n), exit_term=true { range [midl+mcr,l] } uv m uv endif goto 3 endif t (midl)= A (midl) / B (midl) ifB (rnid)-B (midl)<0 then m=mid, t =t (mid), entry_term=true { range [k,mid] for entry chain } n=midl, t^t^Cmidl), exit_term=true { range [midl,l] for exit chain } else { B (mid)-B (midl)>0 } if t (mid)<t (midl) then { t-para turns to decreasing } if B (mid)>0 .and. t (mid)% then m=mid, t =t (mid), entry_term=true { range [k.mid] for entry chain } else if B (mid)<0 .and- t (mid)<t then n=midl, t^t^Onidl), exit_term=true { range [mid 1,1] for exit chain } else accept=false endif endif else { t-para is increasing } if B (mid)>0 .sod. ^^mid)^! then k=mid, t^=t (mid) { shifting entry boundary } else if B (mid)<0 .and. t (midl)<t then l=mid, t =t (mid) { shifting exit boundary } else accept=false endif endif endif endif uv u uv uv uv uv m uv uv uv uv uv uv uv m uv uv k uv uv uv uv k uv 1 endwhile end; { end of procedure Find_range } AJgorittam 3.5 b Procedure Find_max_t (u,v; vark.m, t^,^, ) { function: this procedure bisectionally finds the maximum value of t-para within the entry range [k,m] containing the hill, input: endpoints u(u ,u ) and v(v ,v ); the range [k,m] with [t^t^]. output the updated range [k,m] with [tj ,t l and the maximum value t^^note: this procedure assumes incr=+l and k<m. } x y x y c m begin maxtfound = false while .not. max_t_found then case of 1. m-k>2: mid = (k+m)/2 , compute t^a=tuv(mid) midl = mid + 1, WdPWd i f t n e n compute tj^^^t^midl) i ^P increasing } 30 k=mid, t =t else tmidl^d ('"P " deceasing } m=midl, t ^ t ^ ! else {equal t-para } Wx rnid> max_t_found=true endif endif k mid i f t h e n =t 2. m-k=l: { neighbouring edges } t =max(t ,t ), max_t_found=true max k m endcase endwhile end; { end of procedure Find_max_t } 8 1 Algorithm 3.5 c Procedure T_bisection ( u,v, incr, ~ var k,l, t^.tp max_tO,min_tl .entry_term, exit_term,accept) { function: this procedure bisectionally finds the minimax values of t-para within the range [k,l] of the intervening chain, input: endpoints u(u ,u ) and v(v ,v ), the range [k,l] with [t^,t ] and incr; interior flags entry_term and exit_term of u and v. output: the maximin values max_tO and min_tl; accept=true if visible, otherwise false. } x v x y 1 begin 1. find ranges containing the hill and/or the dale of t-para. call Find_range (u,v,incr, k, 1 , 1 ^ , m.n.tju.tjj, entryJerm,exit_term,accept) 2. find minimax values of the t-para if accept=true. if accept then if .not. entry_term then { find entry point if u is not interior to P } if m>k then call F i n d m a x t (u,v, k,m, t^, maxtO) else call Find_max_t (u,v, m,k, t ^ t^, max_tO) endif endif if .nd. exit_term then { find exit point if v is not interior to P } if l>n then call Find_max_t (v,u, n,l, l-t^ l - t max_qO) l t else call Find_max_t (v,u, 1A l-t lP l-t„, maxqO) endif min_tl = 1 - max_qO endif if inax_tO>min_tl then accept=false endif endif end; { end of procedure T_bisection } { check reject conditions } AJgorittai 4.1a Procedure Find_Intersection ( a, b, incr, F , F , Fg, var z ) { function: this procedure performs a binary search within the range [a,b] to find the intersection point of segment uv and polygon P. input: range [a,b], incr and the F_parameters F , F and Fg. output* intersection points z ( z , Z y ) . note: assume that w and w are on opposite sides of L; w lies on the same side of c and w lies on the opposide side : G G >0 and G G <0 } - a b a x a b a a b c b c begin 1. if F =F then z=w, goto 6 endif; { w liesonL } 2. if F =F z=w , endif; { waliesonL } a a g a 5 then goto 6 g b 3. initialization term=false 4. while b*a+/ncr .and, term then i=(a+b)/2, Fpn-Wj; case of (Fg-Fj)incr <0: a=i, F =Fj >0: b=i, F =Fj =0: z=Wj, term=false endcase; endwhile; a b { Gj G >0 } { G G <0 } { Gj G =0 } c d c c 5. compute the coordinates of the intersection point ab = ( g - a ) ( b - a ) ; z = w + s (w -w ); s F a 6. end; F ab / b F F a { end of procedure Find_intersection } b Algorithm 4. lb Procedure S_bisection { function: input (u,\,incr, k,l, u_interior, v_interrior; varz, w, accept) this procedure halves the intervening chain iteratively until the line segment is rejected or its intersection(s) with the polygon have been determined. the endpoints u(u ,u ) and v(v ,v ); incr, range [k,l]; interior flags of endpoints u and v. intersection points z(z ,Zy), w(w ,w ); accept=true if visible, otherwise false, if G <0 then incr=+1, otherwise incr=-l. } x output v x x note: 1 3 9 v x v c begin 1. if u_interior .and. v_interior then z=u, w=v, accept=true, goto 6 endif; 2. initialization accept=true, term=false, find the starting and ending vertices of the intervening chain if incr=+l then a=k, else b=l+incr &=k-incr, b=l endif; F =I2u; F = D w , F =J2 w ; g a b a b 3. if u_interior then { u is interior to P } z=u, call Find_Intersect (b, a, -incr, F , F , F , w), goto 6 endif; b a g 4. if v_interior then { v is interior to P } call Find__Intersect (a, b, incr, F , F , F , z), w=u, goto 6 endif; a b g 5. worst case : w and w lie on the same half plane of c w.r.t L { G G >0 and G G >0 } while accept .and. (.not, term) then a a c b b c i= (a+b)/2; F D w if (Fg-Fj) r i; <0 then if b=a+incr then accept=false else incr { GjG >0 : Wj and c lie on the same side } { reach the antipodal point} c 140 j=i+incr, Fj= H • WJ; if (Fg-Fj) incr <0 then { Gj G > 0 : wj and c lie on the same side } { WjWj does not intersect with P } c case of (Fj-Fj) incr <0: a = i, F =Fj, >0: b = i, F =Fj, =0: accept=false, endcase { WjWj is entry edge } { WjWj is exit edge } { WjWj is parallel to L } a D else { GjG < 0: Wj lies on L or Wj lies on the opposite side of c } { WjWj intersects with P } call Find_Intersect (i, j, incr, Fj, Fj,Fg, z), call Find_Intersect ( b, j, -incr, Fjj, Fj, Fg, w ), term = true endif endif else c { GjG < 0 : wj lies on L or Wj lies on the opposite side of c } { WjWj intersects with P } call FindJLntersect (a, i, incr, F , Fj, Fg, z), call Find_Intersect (b, i, -incr, F , Fj, F , w), term=true endif endwhile c a D 6. end; { end of procedure S_bisection } g 141 AlgorittaBi 5 Procedure 3D_clip (U,V, M, P, CI; var max_tO, min_tl, Z, W, accept) { function: this procedure clips a line segment uv against a sweep-defined object input: the endpoints U(U ,U ,U ) and V(V ,V ,V ); M: (4 X 4) linear transformation matrix; P: window polygon defined by its vertices; CI: 0 for translational sweeping or 1 for conic sweeping, output either the t_para's (max tO, min_tl) or the coordinates corresponding to the visible segment ZCZ ,Zy,Z ), W(W ,W W ), accept=true if visible, otherwise false, note: ^hither ^yon' ^ ^P dow P's coordinates are global variables. } x y z x x C y z z x y> z wm begin 1. initialization accept=true, max_tO=0, min_tl=l; 2. scenetolocal transformation (u , Uy, u , 1) = (U , U , U , 1) • M (v ,v ,v ,l) = ( V , V , V , l ) M x z x y x z y x z y z Find the visible segment ceaoeb w.r.t. the hither and yon planes { The detail of this procedure is not shown } call Intersect_Hither_Yon (u, v, a, b, accept) if .JM- accept then goto 7 endif; project the segment ceaoeb onto the contour plane case of CI 0: a' = a, b' = b; { translational sweep} 1: a* = a/a , b'= b/b ; {conic sweep } endcase z z 5. 2_D clipping of the segment aV with the clip window call 2D_CHp (a , b\P, max_tO', min_tl', accept) if .not accept then goto 7 endif; 1 6. output t_para's or the coordinates of the entry and exit point 6.1 find the tjpara's corresponding to the entry point and the exit point case of CI 0: max_t0=max_t0', min_tl=min_tr; 1: max_t0 = a max_t0' / [ b (l-max_t0') + maxtO' ], min_tl = a min_tr / [ b (l-min_tl') + min_tl' ] ; endcase; z z z z 6.2 compute the coordinates of the entry point and exit point if max t0=0 then Z = Tj else Z = U + max_tO (V - U) endif; if min tl=l vr=v then else W = U + min_tl (V-U) endif; end; { end of procedure 3D_clip } Algorithm 6 Procedure 2D_Clip (u,v; var max_tO, miri_tl, z, w, accept) { function: ~ this procedure clips a line segment uv against a rectangular window, input the endpoints u(u ,u ) and v(v ,v ). output either the t_para's (max_tO, min_tl) or the coordinates corresponding to the endpoint of the visible segment z ( z Z y ) , w(w ,w ); accept=true if visible, otherwise false, note: using trivial acceptance and rejection for improving speed } x v x v x> x v begin 1. map u and v to p and q using 2-D mapping technique call 2D_Map( u, p, NR ); U call 2D_Map( v, q, NR ); 2. initialization max_tO=tpX=tpy=0; min_tl= t^x=tqy=l; accept=false; V 3. trivial acceptance and rejection. ifNR =3 .and.NR =3 then goto5 endif; {case2: trivially accepted } i f (p *q .and. p *u .and- qx^x) i * trivially rejected } (Py^y and- Py^Uy .and- q * V y ) then goto 7 endif; U V c x x x a s e : x y 4. determining reject conditions. Ax=v -u , Ay=Vy-Uy-, x x 4.1 check first pair of t-para's. i f p *u then tpX=(p -u )/Ax ifq *Uy then tqy=(q-Uy)/Ay i f tpX>tqy then goto 7 x x x x y y 4.2 check second pair of t-para's. i f Py*Uy then tpy=(Py-u )/Ay ifq *v then tqX=(q -u )/Ax i f tpy>tqX then goto 7 y x x x x endif; endif; endif; { rejected } endif; endif; endif; { rejected } 5. output t-para's or coordinates of the entry/exit points. 5.1 entry point if NR =3 then { u is interior to P then u is output} U z x x» y =u else z s=u y if tpX>tpy then { find max_tO=max(tpX, t p y ) } max_tO=tpX z x Px = Zy=Uy + tpX-Ay else max_tO=tpy endif endif; 5.2 exit point ifNR =3then { v is interior to P then v is output } else if tqX<t y then { find mmJl=rnin(tqX, t q y ) v q min_tl=tqX w x lx =c w =Uy + tqX-Ay y else min_tl=tqy w =u + tqy-Ax x x w =q endif y y endif; 6. accept=true 7. end; { end of procedure 2D_clip } }
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Fast clipping algorithms for computer graphics
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Fast clipping algorithms for computer graphics Tran, Chan-Hung 1986
pdf
Page Metadata
Item Metadata
Title | Fast clipping algorithms for computer graphics |
Creator |
Tran, Chan-Hung |
Publisher | University of British Columbia |
Date Issued | 1986 |
Description | Interactive computer graphics allow achieving a high bandwidth man-machine communication only if the graphics system meets certain speed requirements. Clipping plays an important role in the viewing process, as well as in the functions zooming and panning; thus, it is desirable to develop a fast clipper. In this thesis, the intersection problem of a line segment against a convex polygonal object has been studied. Adaption of the the clip algorithms for parallel processing has also been investigated. Based on the conventional parametric clipping algorithm, two families of 2-D generalized line clipping algorithms are proposed: the t-para method and the s-para method. Depending on the implementation both run either linearly in time using a sequential tracing or logarithmically in time by applying the numerical bisection method. The intersection problem is solved after the sector locations of the endpoints of a line segment are determined by a binary search. Three-dimensional clipping with a sweep-defined object using translational sweeping or conic sweeping is also discussed. Furthermore, a mapping method is developed for rectangular clipping. The endpoints of a line segment are first mapped onto the clip boundaries by an interval-clip operation. Then a pseudo window is-defined and a set of conditions is derived for trivial acceptance and rejection. The proposed algorithms are implemented and compared with the Liang-Barsky algorithm to estimate their practical efficiency. Vectorization of the 2-D and 3-D rectangular clipping algorithms on an array processor has also been attempted. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-07-11 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0096928 |
URI | http://hdl.handle.net/2429/26336 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1986_A7 T72.pdf [ 6.19MB ]
- Metadata
- JSON: 831-1.0096928.json
- JSON-LD: 831-1.0096928-ld.json
- RDF/XML (Pretty): 831-1.0096928-rdf.xml
- RDF/JSON: 831-1.0096928-rdf.json
- Turtle: 831-1.0096928-turtle.txt
- N-Triples: 831-1.0096928-rdf-ntriples.txt
- Original Record: 831-1.0096928-source.json
- Full Text
- 831-1.0096928-fulltext.txt
- Citation
- 831-1.0096928.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0096928/manifest