UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Fast clipping algorithms for computer graphics Tran, Chan-Hung 1986

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

Item Metadata

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

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

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items