FAST CLIPPING ALGORITHMS FOR COMPUTER GRAPHICS by CHAN-HUNG TRAN B. Eng., Chiba University (Japan), 1977 A THESIS SUBMITTED IN PARTIAL FULFILMENT O F T H E REQUIREMENTS FOR 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 DEPARTMENT O F ELECTRICAL ENGINEERING We accept this thesis as conforming to the required standard T H E UNIVERSITY O F BRITISH COLUMBIA 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 ELECTRICAL 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 xi 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 1.4 Thesis outline 7 2. NOTATION 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 3. 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 „ 23 iii 3.3.4 The hill and the dale of t-para 25 3.3.5 Outline of the t-para algorithm 25 3.4 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 3.5 Bisection t-para method 31 3.5.1 The algorithm 31 3.5.2 Time complexity 32 4. 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 4.5 Comparison of the s-para and the t-para methods 43 5. T H R E E - DIMENSIONAL CLIPPING WITH A SWEEP- DEFINED 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.2.4 The t'-t transform 50 5.3 The 3 - D clipping algorithm 51 5.3.1 Overview 51 5.3.2 Intersections with side planes 52 6. 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 6.4 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 7. EXPERIMENTAL ESTIMATION O F T H E EFFCIENCY O F T H E PROPOSED ALGORITHMS 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 7.3 Vectorization of rectangular clipping 86 7.3.1 Overview 86 7.3.2 Vector version of the rectangular clipping algorithm 91 v 7.4 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 7.5 Experimental results of rectangular clipping 94 8. CONCLUSIONS 105 8.1 Summary 105 8.2 Concluding remarks 106 8.3 Future work 106 BIBLIOGRAPHY 108 APPENDIX A I l l APPENDIX B 116 APPENDIX C 119 APPENDIX D 128 vi List of Figures Figure Page 1.1. Three-dimensional line-clipping examples: (a) interior clipping and (b) exterior clipping (from [Roge85]) 3 1.2 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 u ( /) and B u v ( /) 21 3.5 Examples of Aim(uv,Lj) true 21 3.6 Trivial rejections 24 3.7 tu v(/) vs. / (this example assumes &f0 or incr— +1) 26 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 i i 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 81 7.2 CPU times for three types of 2 - D generalized clipping algorithms where the area ratio of window polygons is 10 82 7.3 C P U times for three types of 2 - D generalized clipping algorithms where the area ratio of window polygons is 20 83 7.4 C P U times for three types of 2 - D generalized clipping algorithms where the area ratio of window polygons is 40 84 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 87 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 88 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 89 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 90 viii 7.9 CPU times for 2 - D rectangular clipping of the Liang-Barsky algorithm where the area ratio varies from 1 to 200 96 7.10 CPU times for 2 - D rectangular clipping of the scalar version of the mapping method where the area ratio varies from 1 to 200 97 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 98 7.12 CPU times for 3 - D rectangular clipping of the Liang-Barsky algorithm where the volume ratio varies from 1 to 400 99 7.13 CPU times for 3 - D rectangular clipping of the scalar version of the mapping method where the volume ratio varies from 1 to 400 100 7.14 CPU 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 x = v ; c and u^=v^, 115 A. 2 Case uv parallel to ow'or (t' = v z / ( v 2 - u z ) „aj__L u z * \ z ) 115 B. Classified cases for determining a • 0 ^ 0 and | a| £ 101 118 C. 1 Classified cases for determining a,/3, m have the same sign and | a\^ | m| ^| 01 121 C.2 Case Ax* 0 and Ay* 0 125 C.3 CaseAx=0orA=0 126 C.4 Case t q y = y c and tqx=tpy 127 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 ; 95 x 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 zooming are two important functions in interactive computer graphics. They are 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 moderately priced hardware which limits the functionality of the operations. Embedded in the functions, clipping algorithms which are 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. detecting whether two objects intersect, 2. finding the points of intersection, if they intersect with each other, 3. 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, e.g. in vector graphics, then the type of clipping is called line clipping (Fig. 1.1). 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. The intersection problem is the second step of the complete clipping algorithm mentioned earlier. The intersection operation is performed 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 role in the viewing pipeline in computer graphics (see details in [Newm] and [Fole]). The object to be viewed is described by geometric coordinate data in world coordinates. The viewer can specify a clip region which he wishes to have displayed and a viewport, the portion of the view surface into which the window contents are mapped (Fig. 1.3). Mapping points which are outside the window may produce undefined values, resulting in attemps to address locations beyond the physical limits of the display device. Such situations can be prevented by clipping. Furthermore, clipping leads to a substantially smaller amount of work for the display hardware to process. To improve the update rate for real-time graphics applications, it is important to identify where time is being spent mostly. In a time analysis of a flight simulation program, it was found that only 5% of the time was spent on performing matrix multiplication operations, while the largest block of time (23%) 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) interior clipping and (b) exterior clipping (from [Roge85]). can be achieved by improving the clipping operation. In addition to the viewing process, clipping is useful for several aspects of computer graphics: hidden line/surface removal, shading, texture, anti-aliasing, and ray/beam tracing ([Suth74], [Weil77], [Catm78], [Dado82], [Dado84]). It also contributes to solid modeling using Constructive Solid Geometry (CSG) and oct-tree representations [Roth82] and [Carl85]. 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 in scalar processors or parallel processors. For example, the clipping algorithm has been implemented in hardware rather than software for interactive graphics ([Spro68], [Clar80], [Mehl84]). Thus, the algorithm should be simple 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. the computational complexity of the algorithm, '2. the regularity and compactness of the algorithm, 3. the parallel executability of the algorithm. Fig. 13 Viewing pipeline and coordinate systems (from [Artw]). 6 1.3.1 Computational complexity Although the logarithmic detection and intersection algorithms in Computational Geometry are asymptotically fast, the 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 compactness The algorithm should exhibit regularity and be as compact as possible for hardware implementation. Therefore, a simple data structure is desired and the formulation of the problem is important Since the inherent branching conditions to reject or accept a line segment for intersections are always the limiting factor to make the clipping algorithm elegant, tradeoffs between 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 to improve the execution speed. The main concern is how to detect the visibility of a line segment against a clip window with large N and how the 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. In Chapter 3, a generalized 2 - D parametric clipping algorithm, called a t-para method, will be discussed. A sequential tracing method and a bisection method are 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 to a sweep-defined object created by translational or conic sweeping. In Chapter 6, the rectangular 2 - D and 3 - D clipping is presented. The clipping process relies on a mapping operation. Here, a pseudo-window is introduced for fast rejection and intersection computation. In Chapter 7, results from experiments with the algorithms described in Chapter 3, 4, and 6 will be discussed. Finally, in Chapter 8, concluding remarks will be made and further avenues for research will be suggested. 8 Chapter 2 NOTATION AND PREVIOUS WORK 2.1 Assumptions and Notation It is useful to begin by establishing some fundamental assumptions and introducing the notation which will be used throughout the thesis. The notation given here is restricted to 2-dimensions, but it can be extended to 3-dimensions easily. 2.1.1 Line and line segment A line segment is represented by uv, where u(u x , u ,^) and v(v x, v ) are its two endpoints. While the direction vector D = v-u denotes the directed line segment uv from a point u to a point v, L denotes the directed 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(zx, zy) is said to lie to the left of (right of, on) L if T = zu • JQ = ( u ^ - Z j X v ^ - u p - (uy-zy)(\x-ux) ... (2.1) is positive (negative, zero). 2. If z lies on JL, then T = 0. We have t = (zx-ux)/(\'x-\ix) = (zy-\iy)/(vy-uy). For every value of t, a corresponding point on the line is defined in parameterized form as z = t[u,v] 4 ii + t(v-u) ... (2.2) or i = n + tD ... (2.3) 9 The coordinates of point z are ... (2.4) zx = ux + t ( v x -u x ) The parameter t, called the t-para, determines where the point lies on L The values t=0 and t=l correspond to the endpoints u and >, respectively. If te[0,l] then the line segment uv is traced out; tc^o0,0 0) generates the infinite line L. 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,w2 w^), where the points Wi.w, are the vertices and i T ^ , .... viflVi are the sides or the boundary edges. We also assume that two consecutive edges are not collinear. Each vertex is defined by its x- and y-coordinates w.(w (/), w^(/)) and each edge is' represented by its two endpoints e.=vx.+ ^ 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 if it lies on the right side of L. or on the line L. (i.e. pflflL^. is considered to be p i f l ^ ) , otherwise exterior (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 14 w 7 note: Chainl = { c 7 — e i 3 }, Chain2 = { - * 6 )• Fig. 2.1 Clip polygon and entry/exit boundaries. By this convention, the inner normal vector of the edge e., viz., JE i(wy['+l)-w^(/), ~[w J |(/+l)-w J t(/)]), 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 and a clip polygon P. We 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). If L points from the exterior of L. to the interior of L., then the boundary edge e^ . is called an entry boundary to uv; if L points from the interior of L. to the exterior of L., then the boundary edge is called an exit boundary. Two chains of boundaries are formed: an entry chain denoted by chain! consisting of all entry boundaries and an exit chain denoted by chain2 11 consisting of all exit boundaries (see Fig. 2.1). 2.1.4 Visibility classification In this thesis, only exterior clipping is considered. The visible region is the interior of the clip window. A line segment is classified as entirely visible, entirely invisible, or partially visible to the clip polygon. The following degenerate cases are considered to be visible to the polygon: the 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 equivalent algorithms are proposed in the literature which satisfy the considerations (2) and (3) of Section 1.3. The idea of using a parametric representation of a line for intersection testing were independently proposed by Cyrus and Beck [Cyrus78] and Liang and Barsky [Lian83, Lian84]. Cyrus and Beck use a geometrical interpretation representing the parameter value for intersection of a particular line segment and a boundary line, while Liang and Barsky describe it in an algebraic form. Both described the conditions for detecting intersections as a set of minimum/maximun inequalities. Determining the appropriate . intersections reduces to a classical linear programming problem. We will decribe the above method differently, which is adapted to our notation. The problem of a line segment intersecting with a convex polygon is solved by finding the intersections 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 ( t t u . * ] - f ) = 0 - <2-5) Substituting t[u,v] = u + t(v-u) into (2.5), we have tu v(z) = Au(z) / BUV(/) ... (2.6) Where AU(/) = £ / . ( f - u ) , BU V(/)= £ / - ( v - u ) . For simplicity, assume f is w„ We have: AU(/) = m - EU(/) B u v ( /) = EV(/) - EU(/) where E(/) =&.•it., E u ( / ) = £ / . « u , E v ( / ) = £ / « v . (2.7) (2.8) «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 interior Fig. 2.2 Basis of the Cyrus-Beck algorithm. 13 The properties of the parameters A u ( /) and B u v(/) will be discussed in Sections 3.3.1 and 3.3.2. The notation t (/) denotes the t-value of the intersection point of the parametric line L containing uv and the boundary line if B u v (/)*0. The results from [Cyru78, Lian84] can be summarized in the following lemmas: Lemma 1 The set of values t such that 1. te[0.1], 2. £ | . ' ( t [u ,v] - f ) > 0, completely determines the visible portion of line segment uv with respect to Li (Fig. 2.2). lenaaiLJL Let max_tO = max( U u v ( / )| Buv(/)>02, ie[l,N]} U {0} ) or max( Jtu v(/)|e.echainl or uvV/e^ ie[l,N]J U {0} ), min_tl = min( {tUV(/)|Buv(/)<0 ie[l,N]} U 11} ) or min( i?\i)ejecbam2, /e[l,N]} U {1} ). 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 < min_tl Lemma 3 If uv 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 algorithm is a "powerful, efficient, general two-and three-dimensional line-clipping" algorithm [Roge85]. Performance tests showed that 2For the B u v(/)=0 case (line segment parallel to the corresponding boundary line), tu v(/) is defined as [Lian84] © 0 = + « if ( B ™ ( i ) = 0 ^nd. Au(/)>0), t u v ( / ) = - » if (Bu v(/)=0 jo± Au(/)<0). In the implementation, however, the B (/)=0 case is treated separately by testing the sign of A u ( /) : if positive then the line segment is invisible, else visible. 14 36, 40, 79 percent improvements have been gained over the conventional Sutherland-Cohen algorithm for 2-D, 3 -D and 4 - D (homogeneous coordinates) cases, respectively [Lian84]. The parameter t not only contributes to determine early rejection but also is used to compute the coordinates of the intersection points if accepted. Lemma 2 helps to determine quickly if a line segment diagonally bypasses the clip window, while the conventional test (e.g. the Sutherland-Cohen algorithm [Roge] or the midpoint subdivision technique [Spro68]) performs a significant amount of computation before rejecting it Since the parameters t are independent with respect to the boundaries, they can be computed in parallel. However, the conventional parametric algorithms are slow if 'the size of the clipping polygon is large. Since it must compute t-para's with respect to all boundaries in the worst case, O(N) operations 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 if it is invisible as well as to detect quickly the boundaries which it intersects if it is partially visible. 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. Unlike the conventional parametric algorithm the 2 - D space is divided into angular sectors for detecting quickly the location of endpoints. This approach was first proposed by Shamos [Sham75] to solve the intersection problem of two convex polygons; Shamos gave an 0(M+N) algorithm to find the intersection of a convex M-gon with a convex N-gon. Since we do not restrict the shape of the objects that can be clipped except that they are formed by line segments, our algorithm is applicable to clip non-convex objects to a convex region. By knowing the sectors which contain the endpoints, 75% of the boundaries are, on the average, eliminated from intersection testing (see Section 3.4.4). Thus, a small investment results in considerable computational saving if the number of window polygon sides is moderately large. 3.1 Partition of 2 - D space Let c be any point interior to the window polygon P (e.g. the mass center of 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. Because P is convex, no sectors or regions will overlap. This assures the 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. As shown in Fig. 3.2, a binary tree (BT) is generated which stores the slopes of the 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 O(logN) after O(N) preprocessing time [Sham75]. The endpoint u of line segment uv lies in the sector formed by the boundary e, (see Fig. 3.2), 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 consider the intersection problem of a line segment uv and the polygon P after 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 with the boundaries of P occurs. Case 2 Points u and v lie on the outside of P in the 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 to 3 are straight-forward. In case 5 since uv must intersect the polygon P at one point, we only need to determine where the intersection point is. Case 4 is the worst case consideration: we need to determine first whether uv intersects P and, if it does, which boundaries it intersects. Because the solution determining the location of 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 called the t-para method (Chapter 3) and the s-para method (Chapter 4). Both methods can be executed linearly in time by tracing 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 of A u ( / ) and B u v (/) is only mentioned briefly in [Cyru78] and [Lian84]. Nevertheless, they are very useful in determining the visibility of the line segment uv with respect to an arbitary boundary line of P. A u (/) is the dot product of vector uF and the inner normal vector £ . of e „ The sign of A u ( / ) indicates the half plane of J L on which the endpoint u lies. If A u ( / ) is positive (negative, zero), point u lies to the exterior of (interior of, on) the boundary line L.. The absolute value of Au(z) is not the minimum distance from u to 20 L. but is proportional to it. Since B u v (/) is the dot product of uv and the inner normal vector £.., Its sign denotes the aiming direction of L with respect to L.. If B u v (/) is positive (negative, 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 u v(/)>0 or uv is aiming away from L. if Bu v(/)<0. 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 u (/) and B u v(/), the predicates interior, aim, and cross can be defined as follows: 1. interior{vi,L^ is true if A u ( / ) £ 0 ; otherwise false. ... (3.1) 2. a/m(uv,L.) is true if (Au(/)>0 .and. Bu v(z)>0) sx. (Au(/)<0 ,and. Bu v(/)<0); otherwise false. ... (3.2) 3. cro5i<uv,L.) is true if (0<Au(/)<Bu v(/)) ,oj. (BUV(/)<Au(/)<0); 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[tu v(.),l] or te[0,tuv(/)] depending on whether point u lies in the exterior or the interior half plane of L.; otherwise uv is entirely visible exterior interior. : (b)y> ei (a) V A u(i )>0 A u(i )<0 B U V ( i )>0 (e^ is entry boundary) Li exterior interior (e) 3 * 1 (g) A U(i )<0 AU(i )>0 B U V ( i )=0 Li 21 exterior interior j < d y u ' V ei (c) A u(i )>0 A u(i )<0 is parallel or col linear to uv ) Fig- 3.4 B U V (U<0 ( is exit boundary ) All cases of A u (/) and B u v(/). Li : a^u v i v / r Note: The predicate CrossiwM) is true for segments a, b and c only. Fig. 3.5 Examples of Aim{u\,Li) true. 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 w ( / * l . Combining all predicates, the visibility of the line segment uv with respect to the boundary L. 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 u(/), and Ev(/') can be tested for saving the u uv uv calculation of A (/), B (/), and t (i) (Table 3.1). A more efficient visibility test using these E parameters is described in Algorithm 3.2. It should be noted that the visibility test results of uv and vu against L. are related by and visible{u\,Lp = vu/We(vu,Lp tu v(/) = 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) = true. i = l 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. 'Al l algorithms appear in Appendix D. 23 3.3.3 Trivial rejection Since the sectors e^, e^ corresponding to endpoints n, v, respectively, are known, a trivial rejection can be established. 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,LJ) .and. tuv(it)--tuv(/)] then reject uv. ... (3.4) Recall that chainl and chain2 are the chains of entry and exit boundaries. As shown in Fig. 3.6, condition (3.4) trivially rejects all segments with k,le chainl or ik,/echain2, because one of the visibility test against the boundaries and fails. Furthermore, it rejects the cases where tuv(k)£tuv(l) even though the segment is visible Interior Aim Cross Visible visibility Eu(i)<Ev(i) Eu(i)<Ev(i)<E(i) Eu(i)<E(i)_$Ev(i) E(i)^ Eu(i)<Ev(i) 0<Buv(i) (kBuv(i)<Au(i) 0<Au(i)^Buv(i) Au(i)_sO<Buv(i) false false true true true false false true false false true true entry boundary entirely invisible partially visible entirely visible Ev(i)<Eu(i) Ev(i)<Eu(i)<E(i) Ev(i)<E(i)^ Eu(i) E(i)<_Ev(i)<Eu(i) Buv(i)<0 Buv(i)<0<Au(i) Buv(i)<Au(i)_sO Au(i)__;Buv(i)<0 false true true false true true false true false false true true exit boundary entirely invisible partially visible entirely visible E«(i)=Ev(i) Eu(i)=Ev(i)<E(i) E(i)r^ Eu(i)=Ev(i) Buv(i)=0 0=Buv(i)<Au(i) Au(i)<_Buv(i)=0 false true false false false false false true parallel boundary entirely invisible entirely visible Table 3.1 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 U v(k)>t u v(i). Fig. 3.6 Trivial rejections. 25 for both and Ly 3.3.4 The hill and the dale of t-para Based on the ordering properties assured by the convexity considerations, the t-para's of uv with respect to the entry boundaries and exit boundaries generate two unimodal functions with a hill for chainl and a dale for chain2 (see Fig. 3.7). By Lemma 2, uv intersects P if and only if the maximun t-para against the 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 3. Let h and d indicate the boundary indices corresponding to the hill and the dale, 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 and intersection problem. By knowing that the segment uv lies in the combined sector which is bounded by the intervening edges, called the intervening chain, a naive algorithm can be established to calculate the t-para's within the range [k,l] and to eliminate the edges out of range. As a consequence, by saving the t computations, it runs faster than the conventional parametric algorithms which calculate all t-para's in the worst case. 3.3.5 Outline of the t-para algorithm The outline of the algorithm is described in high-level pseudo code in Algorithm 3.3. However, the actual implementation is different from the description mentioned in the previous sections, since the t-para algorithm can be made more compact and elegant In the next sections, we will discuss two variations of the t-para method, the sequential tracing method and the bisection method, one of which will 26 (a) B u v(i)>0 B u v(i)<0 B u v(i)=0 accepted case: 0<max_tO<min_t 1< 1 (boundary index) max_tO min_t1 (b) B u v(i)>0 B u v(i)<0 B u v(i)=0 rejected case: 0<min_t1 <max_t0<1 i (boundary index) UV Fig. 3.7 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^. It is convenient to compute the t-para's of the entry/exit boundaries, in pairs, such as (e^, e )^, ( e £ + z n c - » e j ), (e, , . , 61 . ), etc. so that we can quickly detect t . > t . . f o r l-mcr" v k+2'incr 1-2-incr' M J entry exit fast rejection, where incr might be +1 (front trace: trace in CW direction) or -1 (back trace: trace in CCW direction). The tracing directions depend on the relative location of c with respect to L. A tracing rule is established as follows: G c = D-(u-c) ; if G < 0 then { c is on the right to L } incr = +1 { front trace entry boundaries, back trace exit boundaries } else if G > 0 then i c is on the left to L } incr = -1 { back trace entry boundaries, else endif endif; 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 "chased" one by one to search the intersection points. Examples of boundary tracing are shown in Fig. 3.8. It should be noted that in case 5 only one direction of tracing is necessary: 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 important consideration for an algorithm are the stopping rules. First, since the intervening chain is bounded by [&,/], the tracing can not 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 UV passes an antipodal vertex, i.e. B (/) changes sign from positive to negative/zero (see UV Fig. 3.7 again). Similiarly, exit tracing terminates if B (/) changes sign from negative to postive/zero. Recall that the purpose of tracing is to find the minimax values of t-para's. The entry boundaries are traced uphill such that ^ e n t r y is approaching max_tO from e^ . and reversely the exit boundaries are traced downdale such that t ^ is approaching min_tl from e^ . The entry tracing stops when it just passes over the hill UV of t-para and begins to face downhill (t (/) turns to decrease); the exit tracing terminates when it just passes over the dale of t-para1 and begins to face uphill (tuv(/) turns to increase). Therefore, tracing only occurs within the ranges [k,h + incr] and [d-incrj] and the inner boundaries [h + 2-incr, d-2-incr] 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 terminated or the reject condition (t >t .) has been satisfied. 30 3.4.3 Simplified version of t-para sequential method Instead of exit tracing, we can replace it by an entry tracing such that vu is tested with chain2 for intersections rather using uv. Note that t ^ / ) = l-t u v ( /) . Let max_q0 = l-min_t0. Then, instead of searching min_tl we can search the maximum value (max_q0) during the entry tracing of vu starting from e^ and following the -incr direction. The tracing procedure can be simplified to deal only with entry tracing as shown in Algorithm 3.4a. The t-para sequential tracing algorithm is described in Algorithm 3.4b. 3.4.4 Time complexity The tracing time is O(N). Because the shape of the clip polygon is arbitrary, it is difficult to analyse the average case. If we assume the clip polygon is an approximated circle with sides of equal length and c as the center, then the tracing range is equal to half of the polygon (circle) perimeter for the worst,case. Imagine an infinite line parallel to the line segment uv and passing through c. 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% of the parameters L However, the time complexity is still O(N) because the computational complexity eliminates the multiplicative factors. On the other hand, the conventional parametric clipping algorithms always compute 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 sequential clipping algorithm. There are two levels of parallel executability. The entry tracing and 31 exit tracing independently update the global variables max_tO and min_tl, respectively. They are suitable for parallel implementation. Furthermore, each t-para needs two E-computations (Eu(/) and E v(/)) which can be done in parallel. 3.5 Bisection t-para method 3.5.1 The algorithm uv We know that the t-para function ( t (/") vs. /' ) is a bimodal function with a minimum value (min_tl) and a maximum value (max_tl) within [k,l]. To simplify the uv discussion we suppose k<l for incr= + l. .Because the t (/) corresponding to the bounding edge e^ . of the intervening chain is not known, it is possible to apply an uv appropriate numerical method to find the minimax of t (/). Here, we propose a logarithmic approach, called the bisection t-para method, which is based on the well-known bisection method in numerical methods to find solutions of nonlinear equations by some "interval-halving" iterations [Gera]. Recall the boundary indices of the hill and the dale of t-para are h and d, respectively. The algorithm consists of three steps: 1. First, we find the boundary range [k,m] of the entry chain (Bu v(/)>0) such that 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 range pair, an interval-halving iteration is performed to eliminate half the boundaries in each iteration such that the range is alternately narrowed from both ends on the way finding the maximum or minimum value. In each iteration, the mid-boundary of the range is found and the first derivative t' = 1 mid+incr~l mid * S c o m P u t e c ^ - ^ l'mid *S P ° s ^ v e ( n e8 a u v e)> then the walk from the mid-boundary to the next boundary faces uphill (downdale). Since we assume 32 that consecutive boundaries are not collinear, no ^ ' m ^ is equal to zero. In the bisection process, the hill of the t-para is determined as O ^ / j ^ ^ O - a "d- t ' ^ O ) and the dale of the t-para is identified as (^ /_ 0 -and. t'^>0). 3. Comparing max_tO (i.e. t u v(A)) and min_tl (i.e. tuv(d)), if max_tO>min_tl then the line segment is invisible; otherwise the intersection coordinates are computed using these minmax values. A formal description of the algorithm is given in Algorithm 3.5a, 3.5b, and 3.5c. From the discussion in Section 3.4.3, the "find-minimum" of t-para in exit tracing can be replaced by the "find-maximum" of t-para 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, this approach has a large constant factor, because it , must compute two t-para's to determine whether t (/) is increasing or decreasing. The expensive l-para calculations result in a reduced efficiency of this algorithm, despite its logarithmic character. Because the two t-para's iXmi(j and t m i ^ + i n c r ) ^ independent, they can be computed in parallel to speed up the processing time. Furthermore, once the ranges [k/n] and [nj] have been identified, the operation finding the 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 TWO-DIMENSIONAL 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 the infinite line L which contains uv. This test is performed only for the line segments which- can not be trivially rejected. The search cost for intersecting edges of this method is lower than that of the t-para method. Similar to the t-para method, both sequential search and bisectional search techniques are applicable; nevertheless, this method is more promising for the development of a logarithmatic algorithm based on the numerical bisection method. 4.2 The algorithm The s-para algorithm is a variation of the t-para algorithm for the "worst case". Thus, it is necessary to replace step 4.2 in Algorithm 3.3. Recall that the worst case occurs either 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. The inner normal vector of L is defined by __>(v - u v , -(v - u r ) ) . Let g be any point on L and Wm. be a boundary edge of P. y y ~ i j A parametric representation of the infinte line containing » » . is given by s^.w^.w.] A Wj. + s.j(Wj-Wj). The parametric value s.j is called the s-para in short The s-para of the intersection point of L and L. is defined by the following equation (see also Fig. 4.1) where G . = _Q-(g-w), H = D«(w. -w. ) . Let F = D - g , F . = J }»w.. F = J}«w l l IJ J l 6 I I J j then ... (4.1) i g H . . = F . -ij J ... (4.2) F.. = G . -14 LS £(g c(g Wi)<0 Wj)>0 g LR L 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. Similarly to the parameter A u ( /) in the t-para method, Gf. determines in which half plane the vertex w. lies with respect to L. We also use G=rj* (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 c«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). Notice that the case where c lies on L ( G c =0 ) does not occur here, because this case has been accepted in an early stage of Algorithm 3.3. 4.2.2 Initial conditions Let w f l and be the starting and ending vertices of the intervening chain, respectively. According to the tracing 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 { G X O } a = k b — l+incr else { G c >0 } a — k-incr b = I endif; Points wf l and correspond to endpoints u and v, respectively (see Fig. 4.1). If point u lies outside of P then point wfl lies on the same side of c with respect to L. 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. if u*P then G f l -G c > 0 else G f l-G / ; <0 JOJ. G f l + / | I C / . - G 6<0 endif; 2. if vtfP then G f e -G c >0 else G f l -G 6 <0 sa. Ga'Gb-incr-° e n d i f ; 36 3. if u.vt/P then { case 4 in Section 3.2 } Ga.Gb>0 else { case 5 in Section 3.2 } G f l . G f c <0 o2I. ( G f l . G f c > 0 .and. G a + t M r - G b Z 0 ) ss. ( G f l . G f c > 0 and. G.-G^ZO) 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 = w.+ s..(w -w.), given s.. ° i j v i ij j i ij by (4.1). This case occurs when line L lies inside the slab formed by L^ and L^. Since the cases where both endpoints fall in the exterior region of either chainl or chain2 have been trivially rejected (see Fig. 3.6 again), the line segment uv must intersect the edge WjHj at exactly the same intersection point, In contrast, if all vertices in the intervening chain satisfy G^«G c >0, ke[a,b], then the line L (i.e. the segment uv) is entirely invisible because 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 method is sequentially tracing the entry chain and/or the exit chain within [a,b] according to the tracing directions defined in Section 3.4.1. During tracing, the condition is monitored as to whether the G-values corresponding to the vertices change sign. If G.-GSO then the edge « x intersects uv, where j=i+incr for entry tracing or J=hincr 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 ( t e n f r ^ - > t e X j t ^ is no longer applicable to the s-para method due to the different nature 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 bisection method 4.4.1 The algorithm Since the s-para sequential method is slow in rejecting invisible edges, we employ the bisection method to identify the antipodal point R or S which is within [a,b] where G f l « G ^ > 0 . To simplify the discussion, we assume c is on the right to L (incr= +1) as shown in Fig. 4.2, so that we trace the boundaries in the CW 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 . ) for exit edges because H..>0. Due to this fact ij j i J i 6 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. It should be noted that in the former case the parameters G (resp. F) has a maximum (resp. minimum) value, while in the latter case the parameters 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. First, we halve the intervening chain and check the mid-vertex w^.^ to see whether its G value has a different sign than G c . If so, the find-podal-point process terminates and the intervening chain is divided into [a,mid] and [mid,b] for intersection 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 belongs to chainl, we replace the starting vertex wQ by W T O - ^ ; if the G (resp. F) values decrease (resp. increase) then the edge em /-^ belongs to chain2, we replace the ending vertex w ,^ by *rnid' o t n e r w * s e tw is parallel to the corresponding boundary edge and thus is trivially rejected (see Fig. 4.3a again). The process iterates shifting both starting and ending vertices w f l and closer and closer to L towards the antipodal point R (see examples in Fig. 4.4). If no intersecting edge is detected during the halving iterations, then the F i < F f l ( G i > 0 ) Fi= F f l(Gi = 0) Fi>F0 ( Gi< 0 ) Fi decreases Gi increases Fi increases Gi decreases (a) accepted case. F i < F f l ( G i > 0 ) Fi=F0 ( G i = 0 ) F i>F f l (G i<0 ) Fi decreases Gi increases Fi increases Gi decreases (b) rejected case. Fig. 4.3a G . vs. i and F, vs. / (This example assumes G-<0 or incr= +1) > Chain2 Chainl F i<F f l ( Gi> 0 ) incr=-1 i F o b } Fi decreases Gi increases Fi increases Gi decreases J a Fi= F 0 ( G i = O ) F i > F f l ( G i < 0 ) Fi 0 H exit \ DOint \ /\ entry point (a) accepted case. F i < F g ( Gj >0 ) Fi = F f l ( G i = 0 ) F i > F f l ( G i < 0 ) Chain2 Fi decreases' Gi increases Chainl Fi increases G i decreases (b) re jected case. Fig. 4.3b G . vs. / and F. vs. / {This example assumes G_>0 or incr=-1 1 mid C a s e (a): edge intersects L ( Gi • Gj < o ). Ranges [e,mid] and [mid,b] are found for intersections. C a s e (b): edge e i does not intersects L ( Gi • Gj > 0 ). Antipodal point R has been found by moving the vert ices 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 again to find the intersection edge w i j w ith C.'CSO. In each iteration, the sign of the G parameter of the midpoint is monitored. For a partially visible line segment with two intersection points, two ranges [a,mid] and [mid,b] are to be searched. However, for the case of one intersection, only one Find-intersection-edge search is performed for [ajb]. Even though we might have G • G / . X ) , the binary search is still valid since G , . - G t ^ O or G _ * G . . <0 is a b ' J a+incr o a b-incr always assured in this case. A formal description of the algorithm is given 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 procedures. It should be noted that each iteration of Find-podal-point needs two G - or F-computations. For an invisible segment, a total of 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 intersection points, both operations Find-podal-point and Find-intersection-edge are needed. However, only Find-intesection-edge is necessary for the case of one intersection point 43 4.5 Comparison of the s-para and the t-para methods Recall that the tests which are used to identify intersections in the t-para and s-para methods are different for sequential tracing. The t-para method computes the t- para's corresponding to the boundaries within the intervening chain and searches for the minimax values, while the s-para method 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 , to obtain G . and G . , while we need to l J K I J calculate Eu(/), Ev(/), Eu(y") and Eu(y) to obtain tu v(/) and tu v(y) (more subtractions and divisions are required). It is obvious that the t-para sequential method is slower than the s-para sequential method in determining intersections, while the former is faster than the latter in determining rejections. Hence, it is difTicult to evaluate which one is superior. Despite employing the binary search technique, the t-para bisection method is very expensive due to the fact that two t-computations are used for each iteration of searching the hill or the dale. On the other hand, the s-para bisection method needs to calculate two G parameter values in finding a podal point and one G parameter in finding the intersection edge for each iteration. Since the computational cost of the G parameter is less than that of the t-para, the s-para bisection method is more attractive. In addition, to achieve faster speed we can use the parameter F 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 THREE-DIMENSIONAL CLIPPING WITH A SWEEP-DEFINED 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 in 3 - D space are projected onto the contour plane which contains the 2 - D clip window. Then, the projected line segments are compared with the window polygon using any standard 2 - D clipping algorithm. The technique which reduces the 3 - D intersection problem to the 2 - D intersection problem is not new, in [Kaji83] and [Wijk84] the intersection problem of a ray with sweep-defined objects has been discussed for ray casting applications. Kajiya solved the 3 - D ray tracing problem for translational sweeping (prisms) and rotational sweeping (surfaces of revolution) in which the plane curves are 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 volume. Two kinds of sweeping are treated: translational sweeping and conic sweeping. 46 5.2 Sweep-defined objects 5.2.1 Local coordinate system A sweep-defined object can be defined by sweeping a 2 - D contour, the cross section of an object, along a trajectory (as defined by a linear or 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 axis frame by a so-called scene-to-local transformation and by a local-to-scene transformation to transform the clipped object back to the global coordinate system [Roth82]. In this approach, clip volumes are never explicitly transformed; the scene-to-local transformations are used only to transform those objects which have been detected to be possibly intersecting with the clip volume. Note that sweep-defined objects play an important role as primitive objects in Constructive Solid Geometry (CSG)-based solid-modeling systems. Let (x,y,z) be the local coordinate system. For convenience, the contour is embedded in a plane known as the contour plane which is parallel to the x-y plane with z = l . The contour is described as a convex polygon P in terms of its vertices (w,, w2 w y^) by local (x',y')-coordinates on the contour plane where the x'- and y'-axes coincide with the x- and y-axes (Fig. 5.1 and 5.2). 5.2.2 Translational sweeping In translational sweeping, the contour is assumed to lie initially on the hither plane with plane equation z = z w , to be translated to the yon plane with plane equation 47 z=Zy (Fig. 5.1). By convention, 0 < z^<Zy. 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 x = x\ y = y\ ... (5.1) A line segment uv is defined by its two endpoints u(uJC, uy, uz) and v(v x, v v z ) Fig. 5.1 The clip volume with translational sweeping. contour plane 2=1 yon plane z = z Y hither plane z = z H cl ip window cl ip volume (a) C coincides with 0'. (b) C does not coincide with 0*. Fig. 5.2 The clip volume with conic sweeping. 49 after the scene-to-local transformation. An arbitrary point w(wx, w ,^, w z ) on the line L containing uv is parametrically defined by w = t[u,v] A (l-t)u + tv. The points u, v and w are projected onto the contour plane to give the two-dimensional representation u'(u' u'), v'(v' v ' ) , and w'(w', w') as follows: •* y •* y •* y u' = u, v' = v, w' = w, ... (5.2) where u'=u denotes the 3 - D to 2 - D vector assignment such 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 a line L passing through their projected points iT and v'. Hence,, the projected point w' of the point w is also on the projected line L\ The point w' is designated by a parameter value t' as w' = t'.u'.v*] A (l-t')u'+ t'v' in the local (x'.y')- coordinate system. Because of the orthogonal projection property, the following relationship is evident: t = t\ ... (5.3) 5.2.3 Conic sweeping The basic idea of conic sweeping is to combine two transformations of the contour: scaling and translation. The standard scaling of the cross section is defined by multiplying the x- and y-coordinates by its z-coordinate. With conic sweeping, the shape of the cross section is the same as the original contour (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 by x = zx', y = z y \ or xy' = y x \ ... (5.4) Then, the projected points u \ v' and w' of the points u, v and w are, respectively, 50 defined by: u' = u / u z . v' = v / v 2 , ... (5.5) w' = w / w z , where u ' = u / u z denotes u'x—ux/uz, u y = U y / u z ; similarly for v' and w\ From (5.4), we have or [ ( l - t ^ + t v j v/'y = [ ( l - t j i y - t v ^ w'x, then we find t = ^ k l ^ l ... ( , 6 ) Substituting w x = ( l - t ' ) u x / u z + t ' v x / v z , w* =(l-t')u / u z + t'v / v z into (5.6), the parameter t can be computed from t' by V t = ... (5.7) v n - f ) + u , f . 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' is designated by a parameter value t or f. This transformation is called the t'-t transform. The t'-t transform is only performed if the intersection point of the projected line segment 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 the First derivative dt/dt' is positive, the parameter t varies with the parameter 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 is tested with the side planes. The properties of the t'-t transform assure that the 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 to the local coordinates defined by the clip volume (scene-to-local transformation), 2. 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 transform, if visible, 4. transform the results back to the global coordinates (local-to-scene transformation). 52 Steps 1, 2 and 4 are straightforward. The effect of scaling, rotating and translating the clip volume is achieved by scaling, rotating and translating the line segment through scene-to-local 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, z,y = l in translational sweeping, and z # = £ Zy = l in conic sweeping where 0< /< 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 with the window polygon P using either the t-para 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 their t-para's that designate them. We know, furthermore, that the line parameterizations are independent of coordinate systems after the linear transformations between local and global coordinate systems. For example, 53 Fig. 5.3 Intersections with the side planes of a clip volume with translational sweeping Fig. 5.4 Intersections with the side planes of a clip volume with conic sweeping 54 the midpoint of a line segment is still the midpoint after the local-to-scene transformation. This fact implies that step 4 in Section 5.3.1 can be eliminated when utilizing t-para to designate the intersection point A formal description of the algorithm is given in Algorithms 5. 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 f f L R ... (6.1) H ~ y * yT where x^, x^, y ^ , y^, are the x- and y-coordinates of the left, right, bottom, and top of the window boundaries, respectively. The equal sign indicates that the points on the boundary are included within the window. Each of the four boundary edges is extended to a line of infinite extent, partitioning the 2 - D space into nine regions as illustrated in Fig. 6.1. The shaded region R g is the interior of the window. More formally, assuming u(u x , u^) is any point in the 2 - D space, the nine regions are defined as follows: 56 R a 4 { n|(u J C <x L ) ,and. (uy>yT) } Rb 4 { u|(x £ <u J C - -x / - ) ,and. (uy>yT) } R c 4 { u|(u ; c >x i - ) -and- (uy>yT) } Rd 4 { u | ( u J t < x L ) ,and. (y^<u >,<y 7,) } R e 4 { R / 4 { u\(nx>xR) jmd. (yB<uyZyT) } R g 4 { u\(\xx<xL) ,and. (uy<yB) 4 { u|(x L <u ; t <x i ? ) .and. (uy<yB) R. 4 { u | ( u x > x ^ ) ,and. (uy<yB) line segment uv 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 one point, it thrusts into the window; otherwise it pierces the window). By convention 3, the line segment which has one endpoint touching a boundary or which passes a window vertex or coincides with a window boundary is taken into account for intersection or is partially visible. For 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 of line segments are either entirely invisible or entirely visible to the clip window. Therefore, it is important to quickly determine whether a line segment is rejected or accepted for 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 f l , R^, R c ) , (R Q , R <3" Rg^' ^ R c ' R/' RP' R / i ' RP ^ee detai l s o f ^ dgonthm i n Chapter 5 of Newman and Sproull [Newm]). However, the Sutherland-Cohen algorithm performs a significant amount of computation before rejecting those line segments which diagonally bypass the window corner. To resolve this, Liang and Barsky introduced a technique which computes a set of parametric values to fast reject line segments of this kind rather than explicitly calculates the intersection points for each iteration in the Sutherland-Cohen algorithm. Liang and Barsky reported a 36 percent improvement of their 2 - D clipping algorithm over the Sutherland-Cohen algorithm [Lian84]. Here, we propose a mapping algorithm which utilizes an "interval clipping" operation followed by parameter checking similar to the 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 cases but its implementation is awkward and error prone, as for degeneracies. Therefore, a generalized version is preferred, particularly in view of possible compactness as, e.g., the Liang-Barsky algorithm. Here, we will elaborate on the 2 - D class analysis in order to establish a new algorithm which runs fast for the large majority of classes and keeps the regularity and compactness of the implementation. A complete enumeration of the relative locations of the two endpoints in the nine regions yields C(l) + 9 = 45 combinations, consisting of six significant classes which are relevant to the intersection analysis (see Tables 6.1 and 6.2). In Table 6.1, the number denotes the case number which corresponds to the regions in which the endpoints of a line segment fall. Table 6.1 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 shown in Table 6.2. In addition, examples of all cases are illustrated in Fig. 6.3. In cases 1 and 6.b, the line segment is entirely invisible, while in case 2 it is entirely visible. There are two pairs of similar classes (cases 3 and 4, cases 5 and 6.a) which are partially visible and are classified depending on the simplicity to compute the coordinates of the intersection points. Case 6 is the most "complex class", 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 are uniformly distributed at random in the 2 - D space. The probability V m n ° f a line segment whose endpoint falls into region m and the other falls into region n is defined as: p _ (area of region m)« (area of region n) m n (total area of the 2 - D space)-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 (1X1) 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 is not definite; it varies depending on the window size and the relative location of the clip region i h a 6 b 6 ^5 c 1 6 d 6 6 e 4 3 f 1 6 g 1 1 h 1 1 i 1 g i e d c D 1 6 4 1 1 1 6 6 3 6 1 1 6 ^ 1 4 6 1 1 ^ 5 ^ 3 1 4 3 2 ^ symmetry case where one endpoint lies in region f and the other lies in region g. Table 6.1 Classifications according to regions in which the endpoints he (the number denotes the case number). 60 relative case location no. of endpoints number percentage of of combinations combinations description of classified cases 1 two endpoints lie 20 outside the window. 44.44% the line segment bypasses the window. two endpoints lie inside the window. 2.22% the line segment resides in the window. one endpoint lies outside, the other inside. same as 3. 8.89% 8.89% the line segment thrusts into the window (simple). 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. total 14 45 31.11% 100.00% 6.a the line segment pierces the window (complex), or 6.b me line segment bypasses the window (complex). Table 6.2 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 6.2 as a quick projection for the occurrence of the classified cases. Clearly, the mtrinsic nature of the scene greatly 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 which account for 44.44 and 31.11 percent of the combinations, respectively. Dealing with these special cases, Sutherland and Cohen developed an elegant identification technique for case 1, while Liang and Barsky developed a quick rejection algorithm for case 6. However, the other cases were ignored. It should be noted that once the regions are identified to which the endpoints of a line segment belong, cases 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 which determines conclusively to which class the line segment belongs. Classifications can be achieved by identifying the regions of its two endpoints. Instead of the "outcode" used in the Sutherland-Cohen algorithm, we define the region which represented by the region code (colour) as follows: where the subscript of the regions denotes the region code and 2D denotes the entire 2 - D space. Because of the symmetry of the regions, the region codes are simply 0, 1, 2, and 3 which can be represented by 2 bits in hardware (Fig. 6.2). { uKx^u^x^) ,and. (yB<u<yT) }, { u\(xL<u<xR) } - R3, i v\{yB<uy<yT) } - R3. 2D - ( R 7 + R J + R J ) , 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 N o t e : the binary number of the region code Is represented by two bits (a MSB and a LSB). Fig. 6.2 Region codes in 2 -D. 63 location_factor is 2° for the x-axis, 21 for the y-axis, etc. for higher dimensions. Let p (p x , p^) be the mapped point of a point u(u x , u^). The 2 - D mapping simply performs the interval clipping twice, as follows: procedure 2D_Map ( u; var p, NR ) begin N R u = 0; call IntervaLClip ( ux, x^, x^, 1, p x , N R y ); call IntervaLClip ( u^, y^, y^ , 2, p NR^ ); end; The returned region codes are those illustrated in Fig. 6.2. If a point resides outside the window, it will be projected onto the window boundary by the mapping operation, otherwise it remains unchanged. The points within will be projected onto W j. or W B , while the points within R 2 will be projected onto W ^ or W ^ . In addition, the points within R^ will be projected into the corner vertex of the window, while the points within R^ remain unchanged. Utilizing the mapping technique, a line segment can be classified by the region codes and/or the mapped points which correspond to its endpoints (Fig. 6.3). Examples 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 all invisible' line segments and returns a shrunk image formed by the mapped segments. In particular, a polygon enclosing 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 generates some of the intersection coordinates: because of the orthogonal projection, if a line segment enters the x-boundaries (resp. case no. case i . 7 u#-—• classification conditions bypass (tr iv ia l ly rejected") 64 NRu*3 and NR V *3 and { . u x * P x = q x * v x ] o r [u y * py = q y x Vy ]) c a s e 2. u reside y c a s e 3. / u V thrust « s ^ u (simple) NR U =NR V =3 {NRU= 3 and [NR V= 1 or 2 ]) or <NRv=3and [NRU= 1 or 2]) c a s e 4. c a s e 5. thrust (complex) pierce (simple) { NRU=3 and [NR v =0] } or <NRV = 3 and [NR u =0] ) {NRu=NR v= 1 and Py* q y} or { NR v=NRu=2 a n d p x * q x ) 6.b c a s e 6. u 6.a 6.a pierce (complex) 6.b bypass (complex) NRu*3 and NR V *3 and {\$\< M<l«l> NRu*3 and NR V *3 and (|m|< \$\ or |oc|<|m| } Fig. 6.3 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 line segment is an axes-parallel subrectangle of the clip window formed by the diagonal resulting from the projection of the line segment by the 2-D mapping operation. Let p(p x , p^) and q(q x , qy) be the mapped points of the endpoints n(uJC, up and v(v x, \ y ) of a line segment uv. Let points a and b be defined by (jpx, qy) and (q^, p^). Then, the pseudo window of uv is the rectangle paqb (see Fig. 6.5). Both a and b he on the lines passing through p and parallel to (a) (b) original endpoint. o mapped point. ® coinciding original and mapped endpoint. Fig. 6.4 Shrunk image. 66 the x- and y-axes, respectively. Let m, a, j3 be the slopes of the straight line containing the line segments uv, ua, ub, respectively. A slope comparison between a and (5 satisfies a=/3 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 x - u x , &y=Vy-\iy. As shown in Fig. 6.6, a set of t-para's are defined for the entry boundaries and the exit boundaries of the pseudo window as follows: entry: t p X = (p^-u^) / Ax if Ax*0, tpY = (Py-Uy) / Ay if Ay*0, exit: t q X = (qx-ux) / Ax if Ax*0, tqy = (qy-uy) I Ay if Ay*0. 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 if (A>0 and- B=0), ^ t = - » if (A<0 ^ n d . B=0), t , =0 if A=0, entry ...(6.2) t . =1 if A=0. exit The 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. 4In 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 67 Fig. 6.5 Examples of pseudo window (shaded region). The case B=0 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 0 > R^, R 0 ) parallel to x-axis or in the group of blocks (RQ, R y , RQ) parallel to y-axis. The special treatment (6.1) can be eliminated if the line segments of this case are identified and rejected 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 Ax*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 uv is parallel to x- or y-axis (i.e. B=0). In this case we have ux=\x=vx=qx or uy=\y=vy=qy. Therefore, we have bentry=0 ,and. ^ e x H = 1 ) f o r starting endpoint (a) p x= u x ; t p x = 0 termination endpoint (b) Py =U y ; t p y=0 • • (c) qx= v x ; t q x = 1 (d) qy= v y:tqU = 1 69 Fig. 6.7 Special t values when N R ^ O or N R v * 0 . the case A=0 and B=0. This is different from the case A*0 and B=0 in (6.1) giving t . =t . = + » or entry exit 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|s then the line segment uv is at least partially visible to the clip window, otherwise entirely invisible except that the case 0 =m=a is uncertain. Lemma 5 If ( t q y £ t p X ,and. t ^ x ^ y ) 6 then the line segment uv is at least 5This expression excludes the special case m=0=a . 'This expression excludes the special case (t qy = t p X ,and. tqx = tpy). 70 partially visible to the clip window, otherwise entirely invisible except that the case (tqy = t pX .and. tqx = tpy) is uncertain. The proofs and a detailed discussion of both lemmas are given in Appendix C. Lemma 5 is a variation of Lemma 4 using the entry/exit parameters rather than the slopes. The pair of equalities in both Lemma 4 and Lemma 5 lead to uncertain results for cases where m=a = /3. For normal cases when o*/3, the degenerate intersection may occur when only one equality is satisfied (e.g. m=p\ |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 Lemma 5 is general and effective to reject invisible line segments of almost all .cases, i t is still expensive because of the t • computation. To obtain a better performance, cases which can be trivially rejected should be identified before applying Lemma 5. The line segment which lies in the group of blocks (R^, R^, R^) or (R^, Rj, RQ) can be easily rejected by knowing that the entry parameters t p X , t p y > l or the exit parameters t qX , t q y < 0 (i.e. the line segment does not reach the entry boundaries or the line segment begins after the exit boundaries). By observation, this line segment is either mapped into a clip window vertex or mapped onto a boundary of the clip window (see Fig. 6.8). The trivial reject conditions are easily established as follows: ( px=o>x ,and vx*ux and. q ^ v ^ ) sn. ( Py=^y <and Vy*uy and. qy*vy ) The inequalities assure that the 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: a LSB (the first bit from the right) and a MSB (the second bit from the right). If the boolean "or" result of the LSB's of NR and NR is 1 then ( p x * u x and. q x * v x ) is false; otherwise true. Similarly, if the boolean "or" result of the MSB's of N R y and NR v is 1 then (py±Viy .and. qy*\y) is false; otherwise true. 6.5 The 2-D rectangular clipping algorithm Consider the problem of clipping a line segment uv to a rectangle aligned with the x- and y-axes. The algorithm is a special case of the family t-para's clipping algorithm. First, the endpoints are mapped to points p and q using the 2 - D mapping technique. We use these mapped points, which lie on the window boundaries, to compute the corresponding entry and exit parameter values ( t p X , tpy, t^ x and 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 x * u x and q x * v x ) or. (Py=q y and P y * u y and q y * v y ) t t p x=tqx g(0,1) .or. t p y = t q y e (0,1) Fig. 6.8 Trivial reject cases. 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 intersection coordinates need not be computed. We generalize the other cases by using the entry t-para's and exit t-para's to determine 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 cases 3 and 5, where a visibility test is not necessary and the intersection coordinates can be easily and directly computed by substituting the appropriate coordinate (x- or y-) of the mapped points into the line equation y = f(x) of uv. However, this approach is not adopted here by the reason mentioned above. Because the parameter values can be initialized to zero or one, the t-computation is skipped for the cases where the region code corresponding to u and v is not zero (see Fig. 6.7 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 in terva l -c l ip of point u in terva l -c l ip of point v t r iv ia l acceptance parameters t ca lculat ion parameters t ca lculat ion coordinates ca lculat ion 73 100.00X n o t e : i ) Blocks A and B, C and D can be implemented either in parallel or in pipelined fashion. 2) The percentages indicate the probabi l i t ies of data f l ows in Table 6.2. Fig. 6.9 Execution tree of 2-D rectangular clipping. 74 trivial acceptance and rejection are 2.22% and 44.44%, respectively. Assuming that half the line segments of case 6 (15.55%) are rejected on the average, each t 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 2-D clipping utilizing the mapping technique is easy to extend to three-dimensions. The clip volume is an axes-aligned parallelepiped defined by an additional inequality: Zfj < Z < Zy ... (6.3) where z^ and Zy denotes the z-coordinate of the hither and yon planes. Similar to the 2-D mapping, the mapped points p of u and the region code N R y are found by the following 3-D mapping procedure: procedure 3D_Map ( u, p; var NR ) begin NR = 0; call IntervaLClip ( u^, x^, x^, 1, px, NR^ ); call IntervaLClip ( uy, y^ , y^ , 2, p^, NR^ ); call IntervaLClip ( u z , z ^ , z y , 4, p x , N R 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 the line segment down onto the x-y plane and the y-z plane, then the 3-D clipping problem reduces to two 2-D clipping subproblems by the properties of orthogonal projections (see Fig. 6.11). Two sets of conditions for intersection are: z * 0 0 1 0 4 5 4 0 1 0 6„ 4 1/1 1/ 1/ 75 center=? Fig. 6.10 Region codes in 3-D. Fig. 6.11 Orthogonal projections of the clip volume and a line segment 76 and where t qy>tpX, t qx>tpy (x-y plane) t qy>tpZ, t q z>tpy (y-z plane) A* = v z - u z , tpZ = ( p z - u z ) / Az if Az#0, t q z = ( q z - u z ) / Az if Az#0. The formal description of the 3 - D axes-aligned parallelepiped clipping algorithm is omitted because of its analogy to Algorithm 6. 77 Chapter 7 EXPERIMENTAL ESTIMATION OF T H E EFFICIENCY OF 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 VMS at the Department of Electrical Engineering, the University of British Columbia. Since it seemed veTy difficult for us to obtain theoretical 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 experiments. The efficiency of a 2 - D clipping algorithm depends on the following factors: 1. 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, we assume that the scene is a non-convex 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 a circle as the number of sides grows. The location of the center 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 arrays of the subject and clip polygon vertices and its output is the coordinate array of the clipped polygon vertices. The CPU times recorded in all experiments do not 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 time to setup the coordinates of the clipped polygon vertices to the output array. For the 2 - D generalized clipping algorithms, the CPU 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 generalized clipping algorithms The sequential t-para method and the bisection s-para method are the two implemented algorithms which we have used for efficiency estimations. They are simple and efficient for clipping with a polygon of a large number of sides. Since the bisection t-para method is very slow compared to these due to the expensive computation of parameters t, the bisection t-para method is eliminated from further efficiency evaluations. For example, in clipping 100 line segments to a clip window of 20 sides, the CPU time spent is 0.69 seconds for the bisection t-para method, while only 0.31 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: the line segments which intersect a clip window of 100 sides are randomly 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%) of the line segments becomes invisible. However, the data are 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 outlined above. In each experiment a non-convex polygon consisting of 1000 sides (line segments) is to be clipped and the CPU times vs. the number of sides of clip windows are shown in Figs. 7.1 to 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, 7.2, 7.3 and 7.4, respectively. The CPU time for Liang-Barsky's algorithm is linear with the number of sides of the window polygon, while the proposed methods (the sequential t-para and the bisection s-para algorithms) realize asymptotic complexities: linear and logarithmic, respectively. Both 80 t-para and s-para methods run faster than Liang-Barsky's method when the number of sides is large (greater than 50). It is observed that the execution time for the Liang-Barsky algorithm reduces significantly when the area ratio increases (i.e. the clip window becomes smaller), while the both new methods run comparatively 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 s-para method becomes more efficient than the sequential t-para method (see Figs. 7.1 to 7.4). It can be explained that if the window is small, there is less chance for line segments to intersect with the clip window and thus most of line segments are invisible. Since the bisection s-para method runs faster than the sequential t-para 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 of line segments In this experiment, we tested different categories of line segments with a fixed area ratio (=2). CPU Time VS. Number of Sides 81 Normal case: area ratio=2 • LEGEND Liang-Barskv Bisection S-para O " b " _ Sequential. T-para Search lime — o 20 40 60 80 100 120 140 160 180 Number of Sides of Window Polygon 200 Fig. 7.1 CPU times for three types of 2 - D generalized clipping algorithms where the area ratio of the window polygons is 2. CPU T ime 82 VS. umber of Sides Normal case: area ratio=10 • LEGEND Liang-Barskv Bisection S-para o "b" _ Sequential. T-para Search lime o cvj -I 20 40 60 80 100 120 140 160 180 Number of Sides of Window Polygon 200 Fig. 7.2 CPU times for three types of 2 - D generalized clipping algorithms where the area ratio of the window polygons is 10. CPU T ime 83 VS. Number of Sides N o r m a l case: area r a t i o=20 • LEGEND L i a n £ - B a r s k v Bisection S - p a r a O " 6 " . Sequential. T-jDara Search t i m e o oi —I -20 40 60 80 100 120 140 160 180 N u m b e r of Sides of Window Polygon 200 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. CPU Time 84 VS. umber of Sides Normal case: area ratio=40 • LEGEND Liane-Barskv Bisection S-para o "b" _ Sequential, T—.para Search time o w --©-i 20 40 60 80 100 120 140 160 180 200 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. 85 1. All segments are visible (Fig. 7.5). Due to the 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 run very fast compared to the Liang-Barsky algorithm. It implies that the new methods are efficient for clipping an image with a large window such that most of line segments are entirely visible. It should be noted that this is a best case of consideration and the CPU times of both methods are the same. 2. All segments are invisible (Fig. 7.6). In this case, the experimental results indicated that the bisection s-para method show a 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, even though one might think the rejection test based on Lemma 2 is effective and powerful in the sequential t-para method. In fact, this rejection test is still efficient; as seen in Fig. 7.5, 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. 7.7). The results of this case are contrary to the previous experiment: 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 of the boundaries are traced in sequence or a total of 2(log(N/4)) halving operations are necessary to find both entry and exit points. Each halving operation consists of an addition and a division of integers, it is not inexpensive. This causes the bisection method to be less efficient in the software implementation. However, both new methods surpass Liang-Barsky's method for the case where the number of sides is greater than 40. 86 In summary, the proposed methods run faster than the Liang-Barsky algorithm if the number of sides is large. In general, the sequential t-para method shows better performance than the bisection s-para method in our implementation. We combined the experimental results of Figs. 7.6 and 7.7 into Fig. 7.8 and the results show that the bisection s-para method is faster than the sequential t-para method when the number of sides is greater than 120. Since convex polygons with large number of sides in computer graphics applications are rare, the sequential t-para method is a good choice. In addition, because of its algorithmical simplicity the 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 [Tran84]. In order to improve execution speed using a vectorized computer architecture, it is necessary to develop a suitable algorithm. The clipping algorithm can be implemented in parallel due to the fact that each line segment or each parameter can be processed independently. Due to the iterative nature of the clipping algorithm, it is suitable to Single Instruction Multiple Data (SIMD)-type parallel processing, e.g. in the supercomputers Cray-1, Cyber 205 and others, e.g. the multiple microprocessor system G - P S Y C O [Kubo80]. In SIMD-type processing, the same instruction can be performed on several data elements, yet only one instruction cycle is needed. However, this kind of supercomputer is very expensive. Fortunately, vector processors have become available recently, called array processors (APs), which can be attached as peripherals to conventional scalar processors. They are faster than scalar processors and cost much less than supercomputers. The array processors can be CPU T ime * V S . Number of Sides q 20 40 60 80 100 120 140 160 180 200 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. CPU T ime 88 V S . umber of Sides o CD . CVJ o CO. o CO • A l l segments invisible : area ra t io=2 • LEGEND L i a n e - B a r s k v Bisection S - p a r a O " 6 " _ Sequential. T—jgara Search " l i m e 20 40 60 80 100 120 140 160 180 N u m b e r of Sides of Window Polygon 200 Fig. 7.6 CPU 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. CPU Time V S . umber of Sides 89 All segments partially visible: area rat ion • LEGEND Liane-Barskv A Bisection S-nara O b " _ ]3equential_ T-jJara Search time o cvi -0 20 40 60 80 100 120 140 160 180 Number of Sides of Window Polygon 200 Fig. 7.7 CPU 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. CPU T ime 90 V S . Number of Sides o d . o CO . o CD • O invisible or partially visible: area ratio=2 • LEGEND Lian£-Barskv A Bisection S-nara O ~ b ~ . S_e_quentia_l. T-para Search lime 20 40 60 80 100 120 140 160 180 Number of Sides of Window Polygon 200 Fig. 7.8 CPU times for three types of 2 - D generalized clipping algorithms which are the average times of Figs. 7.6 and 7.7. 91 controlled by the host computer to execute the routines requiring repetitive operations, e.g. vector arithmetic and logical operations, while scalar operations still take place in the host computer. 7.3.2 Vector version of the rectangular clipping algorithm We have implemented the rectangular clipping algorithm in Chapter 6 on an array processor 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, eliminating as many special cases as posssible. Therefore, the special treatment for the trivial rejection (case 1) and the trivial acceptance (case 2) in Algorithm 6 should be eliminated. The formulation of the clipping problem into minimax value searching of the t parameters like the 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 Some notes on the AP implementation 7.4.1 Vector codes in APs Supercomputers provide very efficient codes (FORTRAN-like) for both arithmetic and conditional branching. For example, addition of two vectors 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) = A(1;N) + B(1;N). The vector equivalent code of an IF_THEK_ELSE statement is easily converted to vector code as follows: where (C(1;N) .EQ. 0.0) A(1;N) = A(1;N) + B(1;N) otherwise A(1;N) = A(1;N) - B(1;N) end where On 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 for the previous examples are: call VADD (AA 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 VNEG (B,b, D.d, N) { D(1;N) = -B(1;N) 1 call V L M E R G (D.d, B.b, C,c, D.d, N) { where (C(1;N) .EQ. 0.0) D(1;N) = B(1;N) 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. 2. 3. 4. 5. *0 >0 <0 =0 =0 *0 = 0 = 0 *0 =0 —CD A / B 0 0 + 00 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 q y to 1 when A = 0 and B=0. 7.4.3 Memory limitation of the AP Note that all the data are input into the AP 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 time. To save the I/O time, the AP must store intermediate results 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 clipping algorithm, the memory requirement for the intersection test and coordinate calculation is 5nM (words), where n is the dimensions and M is the number of line segments 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 line segments can be vectorized for 2 - D and 3-D rectangular clipping, respectively. Note that in the FPS-100, 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 experimental results of 2 - D and 3 -D rectangular clipping are shown in Figs. 7.9 to 7.17. First, the linear complexities of the implemented algorithms: the Liang-Barsky algorithm, the scalar version and the vector version of the mapping method, are confirmed in Figs. 7.9 to 7.14. Three groups of the clip window/volume were tested: small, medium, and large. In each group, four sizes of the clip window/volume were used. The area (resp. volume) ratio is defined as the area (resp. volume) ratio of the clip window (resp. clip volume) to the N D C 2 - D (resp. 3-D) space. If the ratio increases, the clip window/volume reduces its size compared to the scene. For large clip windows/volumes, the mapping algorithm gained efficiency compared to the medium and small clip windows/volumes (see Figs. 7.15 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 for 2 -D clipping, respectively, and a 26 percent and 49 percent improvement for 3 - D clipping, respectively. The decrease in efficiency for the 3 - D mapping algorithm is caused by the overhead of the mapping operation for the trivially rejected line segments. Since the trivial reject conditions can be tested in pairs with the boundary mapping in sequence, the performance will be improved by this modified version. The improvements of the mapping method over the Liang-Barsky algorithm are summarized in Table 7.2. 95 varying the clip window/volume size overall best worst 2-D scalar version vector version 36% 55% 63% 64% 61% 69% 29% 51% 60% averagef maxf 3-D scalar version vector vesrion 26% 49% 58% 61% 58% 63% 17% 40% 51% average! maxf "{"varying the number of line segments. Table 7.2 Improvement of the mapping algorithm over the Liang-Barsky algorithm in 2 - D and 3 - D rectangular clipping. In the vectorization, if 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 percent has been gained for 2 - D and 3 -D clipping. An interesting observation is that the improvements of the 2 - D and 3 - D version showed a similar characteristic against the number of line segments to be clipped (Fig. 7.17) The improvement percentages seem to be converging at around 70% if the number of 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 ime % V S . Number of Line Segments o Liang-Barsky's 2-D clipping algorithm c\i • Area Ratio • = 1.0 x = 4.0 * = 25.0 o = 1.5 o = 6.0 * = 50.0 A = 2.0 v = 10.0 © = 100.0 4 = 2.5 a = 15.0 s = 200.0 2000 3000 4000 Number of Line Segments 5000 6000 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 ime 97 vs. umber of Line Segments o 2-D mapping method: scalar version in c\i • Area Ratio • = 1.0 x = 4.0 * = 25.0 0 = 1.5 0 = 6.0 * = 50.0 A = 2.0 v = 10.0 e = 100.0 + = 2.5 H = 15.0 " = 200.0 2000 3000 4000 Number of Line Segments 5000 6000 Fig. 7.10 CPU times for 2 - D rectangular clipping of the scalar version of the mapping method where the area ratio varies from 1 to 200. CPU T ime 98 VS. Number of Line Segments o 2 - D m a p p i n g m e t h o d : v e c t o r v e r s i o n in c\i-Area Ratio • = 1.0 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 1000 2000 3000 4000 N u m b e r of Line Segments 6000 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. CPU Time vs. 99 u m b e r of Line Segments Liang-Barsky's 3-D clipping algorithm Volume Ratio • = 1.0 x = 10.0 * = 100.0 0 = 1.5 o = 20.0 * = 160.0 A = 2.0 * = 40.0 © = 200.0 4 = 5.0 a = 60.0 = = 400.0 1000 2000 3000 4000 5000 Number of Line Segments 6000 Fig. 7.12 CPU times for 3 - D rectangular clipping of the Liang-Barsky algorithm where the volume ratio varies from 1 to 400. CPU Time 10o V S . u m b e r of Line Segments o co • 3 - D mapping method: scalar version in Volume Ratio • = 1.0 x = IO.O * = 100.0 o = 1.5 o = 20.0 * = 160.0 A = 2.0 v = 40.0 ffi = 200.0 + = 5.0 H = 60.0 a = 400.0 1000 2000 3000 4000 Number of Line Segments 5000 6000 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. CPU Time V S . N u m b e r of Line Segments 3 - D m a p p i n g m e t h o d : vec tor v e r s i o n V o l u m e Ratio • = 1.0 * = 10.0 x = 100.0 o = 1.5 o = 20.0 • = 160.0 A = 2.0 * = 40.0 © = 200.0 •+ = 5.0 a = 60.0 a = 400.0 1000 2000 3000 4000 5000 6000 N u m b e r of Line 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. I m p r o v e m e n t Percentage 102 V S . Area Ratio Pro 1 posed 2-D 1 rect angu 1 lar c lippii ig alj >oritl l m LEGEND • Scalar Version A Vector Version: average o Vector Version: max i «> k A 4 «, 11 0) CU) 0* CD E O OH £ 20 40 60 80 100 120 Area Ratio 140 160 180 200 Fig. 7.15 Improvements of the 2-D mapping method vs. area ratio. I m p r o v e m e n t Percentage 103 V S . V o l u m e Ratio 1 Proposed 3 - D rect angul 1 lar c] ippir ig al| >oritr lm F LEGEND • Scalar Version A Vector Version: average o Vector Version: max i, 1 «• """"-•< « K 4> ) 1 i I CD OH CD £ O u 20 40 60 80 100 120 140 Volume Ratio 160 180 200 Fig. 7.16 Improvements of the 3 - D mapping method vs. volume ratio. I m p r o v e m e n t Percentage 104 V S . u m b e r of Line Segments o b. 05 o d . CD Vector version of rectangular clipping LEGEND D 2 - D Clipping A 3 - D Clipping 1000 2000 3000 4000 5000 Number of Line Segments 6000 Fig. 7.17 Improvements of the vector versions of the 2 - D and 3-D mapping method vs. number of line segments. 105 Chapter 8 CONCLUSIONS 8.1 Summary The intersection problem of a line segment with a convex object has been studied. First, to solve the 2 - D generalized line clipping problem, two families of parametric clipping algorithms have been proposed: the t-para method and the s-para method. Both methods can be implemented using the sequential tracing or numerical bisection techniques. Their computational complexities are linear and logarithmic, respectively. The parallel executability of these methods has also been examined. As an extension, a 3 - D clipping against a sweep-generated object has been discussed. Using this technique, a truncated pyramid, which. is often used in the viewing transformation, can be applied as a 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 was proposed to test the visibility of a line segment with the so-called pseudo window rather with the actual clip window. A set of rejection conditions (Lemma 4 and Lemma 5) has been established. The possible parallel processing and the regularity of the 2 -D rectangular clipping algorithm is shown by the execution tree. Finally, the sequential t-para and the bisection s-para methods have been implemented and their practical efficiency has been evaluated by comparison 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 implemented. The vectorization technique on an array processor has been applied to implement the vector version. Practial experiments have been performed to estimate the performance of the scalar and vector versions with different sizes of clip windows/volumes. Furthermore, the efficiency of the 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 method and the bisection s-para method seem to be practical for clipping with a convex polygon of number of sides greater than 40. The number of sides can be smaller if the search time of sector location is reduced. The bisection s-para method is efficient when the number of sides is very large (greater than 120). For rectangular clipping, the scalar and vector version of the mapping method showed a 36 and 55 percent improvement for 2-D and a 26 and 49 percent improvement for 3-D, 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 polygon P, we choose an interior point c located in its kernel (a collection 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 fast clipper can be obtained by conbining both the generalized and the rectangular 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 t-para and s-para method on an AP is an interesting topic for future research. 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, AP Math Library Manual, Floating Point Systems Inc., July 1982. [Artw] Artwick, B.A., Applied Concepts in Micro Computer Graphics, Prentice-Hall, 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 Among Solids and Surfaces," Comm. ACM, 22(1), Jan. 1979, pp. 3-9. [Carl85] Carlbom, I.B., I. Chakravarty, and D. Vanderschel, "A Hierarchical Data Structure for Representing the Spatial Decomposition of 3 -D Objects," IEEE 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 Processor for Graphics," IEEE Computer 13(7), July 1980, pp. 59-68. [Cyru78] Cyrus, M . and J. Beck, "Generalized Two- and Three- Dimensional Clipping," 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 of Interactive Computer Graphics, Addison-Wesley, N.Y., 1983. [Gera] Gerald, C.F., Applied Numerical Analysis, 2nd. Ed., Addison-Wesley, N.Y., 1983. 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, "An Analysis and Algorithm for Polygon Clipping," Comm. ACM, 3(1), 1983, pp. 868-877. [Lian84] Liang, Y . - D . and B.A, Barsky, "A New Concept and Method for Line 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 GKS," IEEE Comput. Graphics and Appl., 4(8), August 1984, pp. 52-55. [Newm] Newman, W.M. and R.F. Sproull, Principles of Interactive Computer Graphics, 2nd Ed., McGraw-Hill, N.Y., 1979. [Pavl] Pavlidis, T., Algorithms for Graphics and Image Processing, Computer Science Press, Rockville, Md, 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 Graphics, McGraw-Hill, 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 Conf Proc. 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: A Unified Approach to no Geometric Intersection Problems," IEEE Trans. Computers, C-29(10), Oct 1980, pp. 874-883. [Tran84] Tran, C.H., "An 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," Computer Graphics (Proc. Siggraph '80), 14(3), July 1980, pp. 10-18. [Wijk84] van Wijk, J.J., "Ray Tracing Objects Defined by Sweeping Planar Cubic 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. I l l 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 to a segment entirely visible to these planes. This assumption eliminates the case where the segment is invisible but is projected onto the contour plane intersecting the clip window. Therefore, u z , v ze[z^,Zj,] is assumed and we have u z > 0 and v z >0. 2. Translational sweeping By Equation (5.3), the relationship between the parameters t and t' for translational sweeping is simply t=t\ Then the properties of the t-t' transform is proved straight-forward 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,l], 4. dt/dt'>0 since dt/dt'=l. The third property assures the point w lies on the line segment uv, if its projected point w' lies on the projected line segment Irv.' Because the first derivative 112 (dt/dt') is positive, if t' increases (resp. decreases) then t increases (resp. decreases) accordingly. Thus, if f is the minimax value for the 2 - D entry/exit point of the projected segment u V with the window polygon P, then the corresponding t designates the minimax value for the 3 - D 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 = ... (5.6) This equation is not valid for the case v = u Y and v =u . In this case, however, if v z * u z then the parameter t can be computed by t^= ( w z ~ u z ) / ( v z - u z ) ; otherwise, no t computation is needed because point u and v coincide (see Fig. A.1). Note that in the former case w = u v z v / w ' = u „ z v / w ' if w' * 0 and w' * 0; otherwise, the z x Y x y Y y x y line segment uv is parallel or collinear to ow' and point w' is an invalid intersection. By substituting w'x = ( l - ? ) \ i x / u z + t'v^/v.,, w'^= ( l - t ' )u^/u z + t'v / v z into the right side of Equation (5.6) and assuming u z >0 and vz>0, we have t = A / B, where A = u J , [ ( l - t ' )u J C /u z +fvx/v2]-- u x [ ( l - t ' )u > , /u z + t'vyvz] = ( v * V u * V t , / v z -B = (V^UjUl-VUy/^+t'Vy/Vj - (Wy-Uy)[(l-OUx/Uz+ t'W^V^ 113 = (v^-u^vpf (l-t')/uz + t7v z ] . Dividing the numerator A by the denominator B yields ... (5.7) t = v z ( l - f ) + u z t ' Equation (5.7) denotes the correspondence between parameters t and t'. It causes divide-by-zero errors if t'= v z / ( v z - u z ) and v z #u z , i.e. the line segment uv is parallel valid intersection point and, therefore, the t-t' transform (5.7) is not performed. In summary, both Equations (5.6) and (5.7) can be used for the t-w' or t-t' transform once the "valid" intersection point w' is identified, except that a special treatment is needed for (5.6) when uv is parallel to z-axis. In the implementation, only Equation (5.7) 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 z >0 and v z>0, the numerator and the denominator of the 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 zt', we have to ow' as shown in Fig. A.2. By assumption u z >0 and v z>0, the parameter value t' is greater than one if v z >u z , otherwise less than zero. In both cases, point w' is not a 4. t = 1 / [ v z ( l - t ' ) /u z t ' • + 1 ]. Since v z ( l - t ' ) /u z t ' £ 0 , we have Ul. if u z = v z then t=t' (equivalent to translational sweeping), Q.E.D. 5. dt/dt* > 0. 114 Proof. The first derivative is dt _ u z [ (u z -v z ) t ' + v z] - ( u 2 - v z ) u z f dt' [ ( u z - v z ) f + v z ] 2 u z v z [ ( u z - v z ) f + v z ] 2 dt/dt' > 0 since u z > 0 and v z > 0 are assumed. Q.E.D. Similar to translational sweeping, the parameter t corresponding to the valid intersection point w' designates the entry/exit point of line segment uv with the side planes of the clip volume. 115 Z=Zy 1 v' w' u" t = w z - " 2 vz - uz where w z =u xzy/ w' x =u y z Y / Wy x or y Fig. A.1 Case u =v and u =v Z=ZY V" u" • 1 \ • • t • • • • • / •. / • / J • t y vX / • • : • / / u x or y Fig. A.2 Case uv parallel to ow* or ( f = v z / ( v z - u z ) And- u z * v z ). 116 APPENDIX B Given a line segment defined by two endpoints u(u_x, u^) and v(v x, \ y ) . Using the mapping technique, points u and v are mapped to p(p x , Py) and q(q x , q^), respectively. The pseudo window defined by the diagonal pq has other vertices aCp^ ., q v ) and b(q r , p v ) such that pa is vertical and pb* is horizontal. We assume that the y *• y vertical line has positive/negative infinite slope and the horizontal line has zero slope by convention. Here, we intend to prove that a,/3 have the same sign and |a|^ ||3| is valid for all cases, where a and 0 aie the slopes of the lines containing the segment ua and ub respectively. Proof. Let A x = v x - u r Ay = v y - v x ; A x ^ q ^ - p ^ , Ay' = q^-p^. The slope of the line segment uv is defined by m=Ay/Ax. The possible relations of a and 0 are illustrated in Fig. B. It is necessary to classify and verify all cases for values a and /3. £as£_L: \a\*\fi\ (AxVO and AyVO) A key observation is that sign(Ax)=sign(Ax') and sign(Ay)=sign(Ay'). Therefore pa is a vertical positive vector if Ay>0, otherwise negative; analogously, pF is a horizontal positive vector if Ax>0, otherwise negative. The slope comparisons are based on the decomposition of the vector ua =up+pa, iirJ = up+pF. Case l.a: NR U =3 (point u lies within the clip window). In this case, because p=u thus ua=pa (vertical) and uF=pF (horizontal), slope(ua)= +<*> or - » and slope(uF)=0. Therefore, we have |a|>|/?|. Case Lb: m>0 (Ax>0 and Ay>0). As shown in Fig. B, because pa is vertical and positive, slope(ua)=slope(up) = + o ° if ux=px, otherwise slope(ua)>slope(up)>0; similarly 117 pb is horizontal and positive, slope(up) =slope(ub) =0 if uy=py, 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 Lb 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 is easily found (see Fig. B). In summary, we have a = /3 or-a>/3>0 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 i A Q 118 (cose l.o) NR U =3 |oc| > 1^| (cose l.b) Ax>0,Ay>0 b l«l>l$l "7pi|||| b a q (cose l.d) Ax>0, Ay<0: locf >|^| (cose l.c) Ax<0,Ay<0 : l«|>|£| (cose I.e) * Ax<0,Ay>0: loci > 1^ 1 q«a C 'a v (cose 3.0) Ax=0,Ay=0: a = £ ^ m. Note: A x = v x - u x Ay = Vy - Uy Ax'= q x - p x Ay"= q y - P y (cose 3.b) Ax=0, Ay'^o « = A = m ^ (cose 3-C) Sr—©T v A x ' ^ A y ' s O ® ^ ^_ oc = £ = m Fig. B Classified cases for determining a * 0 ^ 0 and |a|£|0|. 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 and |a|^|/3| is valid for all cases. Ignoring the special case a=/3, 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 lies in the outside the sector with the angle 6 (i.e. m « a < 0 or { m « a > 0 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 the line segment uv is entirely invisible (see Case 3.a in Fig. B). However, m=a=/3 implies that the line L containing uv passes through the points p and q which does not guarantee that uv intersects the clipping window (see Cases 3.b and 3.c in Fig. B). Thus, the condition m=a=/3 is not a sufficient condition for intersection testing. This case must be treated 'This expression excludes m=a=p\ 120 separately. Q.E.D Lemma 5: If ( t ^ y ^ tpX and- tqX>tpy) 2 , then the line segment uv is at least partially visible to the clip window; otherwise, entirely invisible, except that the case (tqy = t pX and. t q X = tpy) is uncertain. Here tpX , tpy, t qX and t^y are defined as in Section 6.4.2. Proof. 1. First, we consider Ax*0 and Ay*0. From Lemma 4 the line segment is accepted for intersections if a,/3,m have the same sign and |a|£|m|>|0|. Notice that the slope m, a, j3 can be written as follows: m = Ay / Ax, a = fy-iip / (jpx-ux), P = (Vy-uy) i ( q x - u x ) The intersect condition of Lemma 4 can be rewritten as > Ay > Vx~ux Ax ... (C.1) We separate them into two inequalities as follows: > Ay Ax > Vy-»y Ax Ay then we have 'This expression excludes both equalities. m*oc=£ u (rejected) a>£>m (rejected) case 1 m=a=£(rejected) £( accepted) case 3 M2|m|2|£l accepted. case 5(a) M2|<m|2|*l accepted. case 6(a) |m|2kx| or i^U|m| rejected. v. 121 case 2 l«| 2|m|> |£| accepted. case 4 W2|m|>|^l accepted. e. J I* oc case 5(b) kx|>|m|> |£| accepted. case 6(b) V W>|m|>l^ l accepted. J C I Classified cases for determining a , p \ m nave the same sign and " ' M * M * | * | . 122 and I V I * I y | I v 1 * 1 V 1 ... (C.3) Since a ,0 ,m have the same sign, t q y»tpX>0 and t ^ x - t p V ^ O should be tested for determining intersections. However, we try to simplify (C.3) to the following inequalities without using absolute expressions: The inequalities in (C.4) are 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 t-parameters must be within the range [0,1] for the intersect or reside cases (see Fig. C.2a). Since both left and right sides of the inequalities in (C.3) are positive, the absolute expressions can be ( tqy^tpx and. y^y ) ... (C.4) eliminated given t q y > t p X and t q x£tpy. For the reject cases, assuming uv lies in the group of blocks (R n , R R 0 ) we have tpX=t qx*[0,l] and tpy*tqye[0,1] (see Fig. C.2b). Then, if tqx<0 (resp. t p X > l ) leads to contradict t q x £ t p V (resp. t q y ^ t p X ) . The same argument can be applied to the line segment lying in the group of blocks (R 0 , R ; , R 0 ) . If the line L containing uv passes through the mapped points, we have tqy = t p X and tqx = t p V for the uncertain case (m=a=/3); otherwise, t q y * t p X or tqx#tpy for the reject case ( m * a = / J ) . Assuming (C.4) is true for the reject case then t q y > t p X , tqx>tpy, and t p X = t q x leads t q y > t p y which contradicts tqy=tpy. 123 2. Now, lei us consider the case Ax = 0 or Ay = 03 (i.e. uv" is parallel to x-or y-axis). Assuming Ax=0, to avoid division by zero we assign t p X = 0 and t^x=l if uv lies in the slab formed by the extended lines of (W ^ , W ^ ), otherwise t p X = t q X = + ° ° or - » (see Section 6.4.2 for details). To simplify the discussion, only +°> value is used. • Case p*q: (see Fig. C.3a). The line segment resides in or intersect with the window, the mapped point p and q must lie within the segment uv given t^y, tqy e[0,l]. This leads t qy^ t^ x and tqx> t^y by knowing tpX=0 and t q X = l . The line segment lies outside the clip window. We have t p X = t q X = + = > and tpy,tqye[0.1]; therefore t q y ^ t p X = + ° ° can not be satisfied. • Case p=q: We have t p X = t q X 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 this case if the mapped point lies ahead uv then tpy>l contradicting tqX>tpy; if it lies behind then tqy<l contradicting tqy^tpX. The accept condition for this case is tpy = tqy=0 or 1. v and u lie in region 0. Since we know t p X = t q X = + ° ° and t^y =tqy«'[0,l], t q y ^ t p X is false. The 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. 3The case Ax=Ay=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 , y ) < min( tqx, tqy ) < 1 for intersections. Note that range checking of these t-para's is eliminated (the major merit of this method), because for the visible cases they are explicitly inclusive to [0,1] (see Fig. C.2a). Furthermore, tqx > t p X and tqy ^ tpy are assured by the mapping property as the line segment crosses the window boundaries: if the line segment is visible to W ^ and then t q x > t p X or is visible to and W^, then tqy^tpy. Then, all these properties and the inequalities in (C.4) satisfy the conditions in Lemma 2. Lemma 5 provides an efficient testing which can reject a diagonally bypassing line segment with only two evaluations of t for the best case, while Lemma 2 needs at least three evaluations of L The uncertainty of the case where tqy = t p X = p and tqx = tpy=o can be clarified by range checking: if p = ae[0,l} then 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] as in the Cyrus-Beck and the Liang-Barsky algorithms but to fully use the properties 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 h Ax>0,Ay>0 tpx,tqxe[0,1] tpy,t q y e[o,1] i b l a q Ax>0, Ay<0 tpX,tqXE[o,1] tpy,t qy6[o,1] Ax<0,Ay<0 d t p x , t q x e[o , 1 ] t p y , t q y e [ o j ] Ax<0,Ay>0 * t p x,tqXE[o ,1] tpy,t q yG[o,1] F i g . C .2a p*q, A x * 0 , Ayx O (acceptcases) tpx=tqx<0 t p y , t q y e [ 0 J ] Note: t px= t q x> i t p y , t q y e[o ,H F i g . C.2b p*q, A x * 0 , A y * 0 (reject cases). A x = v x - u x Ay = V y - U y p=<* e [ o , i ] n o t e : tqy=tpx=p tqx=t py=a u (rejected) p=tf e [0,1] (accepted) tqy* t p x or tqxxtpy (rejected) F i g . C .2c P=q, A x * 0 , A y * 0 (uraertaiii cases). Fig. C.2 Case Ax*0 and Ay*0. tpx=tqx=+oo t. tpy=tqy^[Ojr" (rejected) u f t qy<t px or I tqx<tp y t q y = t p x = 0 (accepted) (rejected) Note: Ax = v x Ay = v y Ax=0 tpy=tqx=1 (accepted) V Y tqy<t px or t q x< t p y -(rejected) Ay=o t p y = t q X=0 (accepted) t q y=tp X= 1 (accepted) tpy=t q y=+oo tpx=tqxg[0,1] (rejected) Fig. C.3a Case p*q, A x = 0 o r A y=0. tpy , t q y G [ 0 , 1 ] , tpx=0, tqx=1. tpx =tq x =+oo tpy, tqye[o , l ] - 4 + — . . . / I T ® ® u Ax=0 t p x , t q x e [o,1], tpy=0, t q y = 1 . '* l p y = t q y = + o o ^ ® — ® Fig. C.3b Cose p=q, Ax=0 or Ay =0. Fig. C.3 Case Ax=0 or Ay =0. x o tpx tqx i t y tpy tqy i • f inal i l mi 3x_tO mir i_t1 1 1 • mex_tO=max ( t p x , t p y ) min_t1=min ( t q x , t q y ) tqx > tpx and tqy > tpy are assured, i f t p y = t q x .and t q y r t p x then p = q and max_tO=min_t1 • Fig. C.4 Case t q y = t p X and t q x = t p y . 128 APPENDIX D LISTING OF ALGORITHMS This appendix contains a listing of algorithms which have been discussed in Chapters 3 to 6. The clipping algorithms are described by one or 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 clipping) 143 Algorithm 3.1 129 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(ux,Uy) and v(vx,vy); boundary index i. output tO and tl corresponding to the endpoints of the visible segment visible(uv,Lj)=true if visible, otherwise false. } begin 1. initialization visible(uv,Lj)=true, t0=0, tl=l; 2. compute Eu(i) and Ev(i) Eu(i)= fii'U E v(i)=£rv 3. determine the visibility of the line segment uv with respect to the boundary Lj. Au(i) = E(i) -Eu(i); Buv(i) = Ev(i)-Eu(i); if aim (uv,Lj) .and, cross (uv,Lj) then tuv(i) = Au(i) / Buv(i) { partially visible } if interior (u, Lj) then tl=tuv(i) { exit point } else tO = tuv(i) { entry point } endif else if .noi. interior (u, Lj) then visible(uv, Lj)=false { entirely invisible } else { entirely visible } endif endif end; { 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(ux,Uy) and v(vx,vy); 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 Eu(i) and Ev(i) Eu(i)=fii«u, Ev(i)=e.rv; 3. determine the visibility of the line segment uv with respect to the boundary Lj. if Eu(i)<Ev(i) then if Ev(i)<E(i) then visible(uv,Lj) = false else ifEu(i)<E(i) then { Buv(i)>0 } { cross=false: Eu(i)<Ev(i)<E(i) { entirely invisible { cross=true: Eu(i)<E(i)<Ev(i) { partially visible tO = (E(i)-Eu(i)) / (Ev(i)-Eu(i)) else { Au(i)<0: E(i)<Eu(i)<Ev(i) { entirely visible endif endif { end of entry or parallel boundary } else { Ev(i)<Eu(i) or Buv(i)<0 if Eu(i)<E(i) then { Au(i)>0: Ev(i)<Eu(i)<E(i) visible(uv,Lj)=false { entirely invisible else if Ev(i)<E(i) then { cross=true: Ev(i)<E(i)<Eu(i) { partially visible tl = (E(i)-Eu(i))/ (Ev(i)-Eu(i)) else { cross=false: E(i)^ Ev(i)< Eu(i) { entirely visible endif endif { end of exit boundary } endif { end of all cases } end; { end of procedure Line-Visible } 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(ux,uv) and v(vx,vv). 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. } 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 c = D.(u-c) case of G c <0: incr = +1 >0: incr = -1 =0: goto 5 endcase 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(ux,uv) and v(vx,vv); 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 Eu(i)<Ev(i) for entry tracing (uv aims towards ej). } begin 1. compute Eu(i) = £j • u ; 2. if E(i)<Eu(i) then terminate = true else compute Ev(i) = £j • v if Ev(i)<E(i) then accept = false else tuv(i) = (E(i)-Eu(i)) / (Ev(i)-Eu(i)) if tuv(i)>min_tl then accept = false if tuv(i)<max_tO then terminate = true else max_tD = tuv(i) endif endif endif endif { u is interior to Lj: entirely visible } { cross is false: entirely invisible } { ^ntry^xit ) { t-para: decreasing or equal } { t-para: increasing } end; { 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(ux,uv) and v(vx,vv); 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 } 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(ux,Uy) and v(vx,vv); 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. } begin 1. while accept .and- (l-k)mcr>l .and-.not, (entry term .and. exit_term) then mid = (k+l)/2 ~ compute Buv(mid), Au(mid) if Buv(mid)=0 then { e ^ is parallel to uv } if Au(mid)>0 then { rejected } accept=false else m=mid-mcr, tm=tuv(m), entry_term=true { range [k,mid-incr] } n=mid+incr, tn=tuv(n), exit_term=true { range [mid+mcr,l] } endif goto 3 endif tuv(mid)= Au(mid) / Buv(mid) 1.1 shifting entry boundaries if Buv(mid)>0 .and- entry_term then k=mid, tk=tuv(mid), goto 2 endif 1.2 shifting exit boundaries if Buv(mid)<0 .and- exit_term then l=mid, tx= tuv(mid), goto 2 endif 1.3 halving iteration midl=mid+incr compute Buv(midl), Au(midl) if Buv(midl)=0 then { e,^ is parallel to uv } if Au(midl)>0 then { rejected } accept=false else m=mid, tm=tuv(mid), entry_term=true { range [k,mid] } n=midl+mcr, tn=tuv(n), exit_term=true { range [midl+mcr,l] } endif goto 3 endif tuv(midl)= Au(midl) / Buv(midl) ifBuv(rnid)-Buv(midl)<0 then m=mid, tm=tuv(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 { Buv(mid)-Buv(midl)>0 } if tuv(mid)<tuv(midl) then { t-para turns to decreasing } if Buv(mid)>0 .and. tuv(mid)% then m=mid, tm=tuv(mid), entry_term=true { range [k.mid] for entry chain } else if Buv(mid)<0 .and- tuv(mid)<tk 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 Buv(mid)>0 .sod. ^^mid)^! then k=mid, t^ =tuv(mid) { shifting entry boundary } else if Buv(mid)<0 .and. tuv(midl)<tk then l=mid, t1=tuv(mid) { shifting exit boundary } else accept=false endif endif endif endif 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(ux,uy) and v(vx,vy); the range [k,m] with [t^ t^ ]. output the updated range [k,m] with [tjc,tml and the maximum value t^^-note: this procedure assumes incr=+l and k<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, compute tj^^^t^midl) i f WdPWd t n e n i ^P 3 0 increasing } k=mid, tk=tmid else i f t m i d l ^ d t h e n ('"P8"1 deceasing } m=midl, t ^ t ^ ! else {equal t-para } Wx=trnid> max_t_found=true endif endif 2. m-k=l: { neighbouring edges } tmax=max(tk,tm), max_t_found=true endcase endwhile end; { end of procedure Find_max_t } 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(ux,uv) and v(vx,vy), the range [k,l] with [t^ ,t1] 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. } 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, entry Jerm,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 l t max_qO) else call Find_max_t (v,u, 1A l - t l P l-t„, maxqO) endif min_tl = 1 - max_qO endif if inax_tO>min_tl then { check reject conditions } accept=false endif endif end; { end of procedure T_bisection } AJgorittai 4.1a Procedure Find_Intersection ( a, b, incr, Fa, Fb, 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 Fa, F b and Fg. output* intersection points z(z x ,Zy). note: assume that wa and wb are on opposite sides of L; wa lies on the same side of c and wb lies on the opposide side : GaGc>0 and GbGc<0 } begin 1. if Fa=Fg then z=wa, goto 6 endif; 2. if F5=Fg then z=wb, goto 6 endif; { waliesonL } { waliesonL } 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, Fa=Fj >0: b=i, Fb=Fj =0: z=Wj, term=false endcase; endwhile; { Gj Gc>0 } { Gd Gc<0 } { Gj Gc=0 } 5. compute the coordinates of the intersection point sab = ( F g- F a) / ( F b- F a); z = wa + sab(wb-wa); 6. end; { end of procedure Find_intersection } Algorithm 4. lb 1 3 9 Procedure S_bisection (u,\,incr, k,l, u_interior, v_interrior; varz, w, accept) { function: this procedure halves the intervening chain iteratively until the line segment is rejected or its intersection(s) with the polygon have been determined. input the endpoints u(ux,uv) and v(vx,vv); incr, range [k,l]; interior flags of endpoints u and v. output intersection points z(zx,Zy), w(wx,wv); accept=true if visible, otherwise false, note: if Gc<0 then incr=+1, otherwise incr=-l. } 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, b=l+incr else &=k-incr, b=l endif; Fg=I2u; F a = D w a , Fb=J2 w b ; 3. if u_interior then { u is interior to P } z=u, call Find_Intersect (b, a, -incr, Fb, Fa, Fg, w), goto 6 endif; 4. if v_interior then { v is interior to P } call Find__Intersect (a, b, incr, Fa, Fb, Fg, z), w=u, goto 6 endif; 5. worst case : wa and wb lie on the same half plane of c w.r.t L { GaGc>0 and GbGc>0 } while accept .and. (.not, term) then i= (a+b)/2; F r D wi; if (Fg-Fj) incr <0 then { GjGc >0 : Wj and c lie on the same side } if b=a+incr then { reach the antipodal point} accept=false else 140 j=i+incr, Fj= H • WJ; if (Fg-Fj) incr <0 then { Gj G c > 0 : wj and c lie on the same side } { WjWj does not intersect with P } case of (Fj-Fj) incr <0: a = i, Fa=Fj, { WjWj is entry edge } >0: b = i, FD=Fj, { WjWj is exit edge } =0: accept=false, { WjWj is parallel to L } endcase else { GjGc < 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 { GjGc < 0 : wj lies on L or Wj lies on the opposite side of c } { WjWj intersects with P } call FindJLntersect (a, i, incr, Fa, Fj, Fg, z), call Find_Intersect (b, i, -incr, FD, Fj, F g, w), term=true endif endwhile 6. end; { end of procedure S_bisection } AlgorittaBi 5 141 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(Ux,Uy,Uz) and V(Vx,Vy,Vz); 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 ZCZx,Zy,Zz), W(Wx,Wy>Wz), accept=true if visible, otherwise false, note: h^ither y^on' ^ C^P wmdow P's coordinates are global variables. } begin 1. initialization accept=true, max_tO=0, min_tl=l; 2. scenetolocal transformation (ux, Uy, uz, 1) = (Ux, U y, Uz, 1) • M (v x,v y,v z,l) = (V x,V y,V z,l) 5. M 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/az, b'= b/bz; {conic sweep } endcase 2_D clipping of the segment aV with the clip window call 2D_CHp (a1, b\P, max_tO', min_tl', accept) if .not accept then goto 7 endif; 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 = az max_t0' / [ bz(l-max_t0') + maxtO' ], min_tl = az min_tr / [ bz(l-min_tl') + min_tl' ] ; endcase; 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 then v r = v 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(ux,uv) and v(vx,vv). output either the t_para's (max_tO, min_tl) or the coordinates corresponding to the endpoint of the visible segment z(z x > Zy) , w(wx,wv); accept=true if visible, otherwise false, note: using trivial acceptance and rejection for improving speed } begin 1. map u and v to p and q using 2-D mapping technique call 2D_Map( u, p, NRU); call 2D_Map( v, q, NRV ); 2. initialization max_tO=tpX=tpy=0; min_tl= t^ x=tqy=l; accept=false; 3. trivial acceptance and rejection. ifNRU=3 .and.NRV=3 then goto5 endif; {case2: i f (p x*q x .and. p x*u x .and- qx^x) i c a s e * : (Py^y and- Py^Uy .and- q y * V y ) then goto 7 endif; 4. determining reject conditions. Ax=vx-ux, Ay=Vy-Uy-, trivially accepted } trivially rejected } 4.1 check first pair of t-para's. i f p x*u x then tpX=(px-ux)/Ax i f q y * U y then tqy=(qy-Uy)/Ay i f tpX>tqy then goto 7 4.2 check second pair of t-para's. i f Py*Uy then tpy=(Py-uy)/Ay i f q x * v x then tqX=(qx-ux)/Ax i f tpy>tqX then goto 7 endif; endif; endif; endif; endif; endif; { rejected } { rejected } 5. output t-para's or coordinates of the entry/exit points. 5.1 entry point if NRU=3 then { u is interior to P then u is output} z x = u x» z y s = u y else if tpX>tpy then { find max_tO=max(tpX, tpy) } max_tO=tpX zx=Px Zy=Uy + tpX-Ay else max_tO=tpy endif endif; 5.2 exit point ifNRv=3then { v is interior to P then v is output } else if tqX<tqy then { find mmJl=rnin(tqX, tqy) } min_tl=tqX wx= clx w y=Uy + tqX-Ay else min_tl=tqy wx=ux + tqy-Ax wy=qy endif 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 |
AggregatedSourceRepository | 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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0096928/manifest