00001 /** 00002 \file Robots/LoBot/misc/LoClipper.H 00003 \brief Line clipping with the Cohen-Sutherland algorithm. 00004 00005 This file defines a class that implements the Cohen-Sutherland line 00006 clipping algorithm for clipping a line segment to a rectangle 00007 aligned with the principal axes. 00008 */ 00009 00010 // //////////////////////////////////////////////////////////////////// // 00011 // The iLab Neuromorphic Vision C++ Toolkit - Copyright (C) 2000-2005 // 00012 // by the University of Southern California (USC) and the iLab at USC. // 00013 // See http://iLab.usc.edu for information about this project. // 00014 // //////////////////////////////////////////////////////////////////// // 00015 // Major portions of the iLab Neuromorphic Vision Toolkit are protected // 00016 // under the U.S. patent ``Computation of Intrinsic Perceptual Saliency // 00017 // in Visual Environments, and Applications'' by Christof Koch and // 00018 // Laurent Itti, California Institute of Technology, 2001 (patent // 00019 // pending; application number 09/912,225 filed July 23, 2001; see // 00020 // http://pair.uspto.gov/cgi-bin/final/home.pl for current status). // 00021 // //////////////////////////////////////////////////////////////////// // 00022 // This file is part of the iLab Neuromorphic Vision C++ Toolkit. // 00023 // // 00024 // The iLab Neuromorphic Vision C++ Toolkit is free software; you can // 00025 // redistribute it and/or modify it under the terms of the GNU General // 00026 // Public License as published by the Free Software Foundation; either // 00027 // version 2 of the License, or (at your option) any later version. // 00028 // // 00029 // The iLab Neuromorphic Vision C++ Toolkit is distributed in the hope // 00030 // that it will be useful, but WITHOUT ANY WARRANTY; without even the // 00031 // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR // 00032 // PURPOSE. See the GNU General Public License for more details. // 00033 // // 00034 // You should have received a copy of the GNU General Public License // 00035 // along with the iLab Neuromorphic Vision C++ Toolkit; if not, write // 00036 // to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, // 00037 // Boston, MA 02111-1307 USA. // 00038 // //////////////////////////////////////////////////////////////////// // 00039 // 00040 // Primary maintainer for this file: mviswana usc edu 00041 // $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/Robots/LoBot/misc/LoClipper.H $ 00042 // $Id: LoClipper.H 13445 2010-05-21 06:12:57Z mviswana $ 00043 // 00044 00045 #ifndef LOBOT_COHEN_SUTHERLAND_DOT_H 00046 #define LOBOT_COHEN_SUTHERLAND_DOT_H 00047 00048 //----------------------------- NAMESPACE ------------------------------- 00049 00050 namespace lobot { 00051 00052 //----------------------- CLASS DEFINITION ----------------------------- 00053 00054 /** 00055 \class lobot::Clipper 00056 \brief A line clipper. 00057 00058 This class implements the Cohen-Sutherland line clipping algorithm for 00059 clipping lines against rectangles aligned with the principal axes (aka 00060 upright rectangles). 00061 00062 Typical usage of this class is as shown below: 00063 00064 // Create clipper object and specify clipping boundary 00065 Clipper clipper(left, right, bottom, top) ; 00066 00067 // Specify line to be clipped 00068 double line[4] ; // first two elements are (x0,y0); next two (x1,y1) 00069 double clipped_line[4] ; 00070 Clipper::ClipInfo clip_flag = clipper.clip(line, clipped_line) ; 00071 00072 // Examine clip flag returned by line clipper and do whatever is 00073 // required with the clipped line... 00074 */ 00075 class Clipper { 00076 /// This line clipper only works with rectangular clipping boundaries. 00077 /// Furthermore, the clipping boundary must be an upright rectangle, 00078 /// i.e., be aligned with the principal axes. This array stores the 00079 /// clipping rectangle's coordinates like so: 00080 /// 00081 /// m_clip_boundary[0] = left 00082 /// m_clip_boundary[1] = right 00083 /// m_clip_boundary[2] = bottom 00084 /// m_clip_boundary[3] = top 00085 float m_clip_boundary[4] ; 00086 00087 public: 00088 /// When this Cohen-Sutherland line clipper is created, it should be 00089 /// told the clipping boundary to use. 00090 Clipper(float left, float right, float bottom, float top) ; 00091 00092 /// This constructor allows clients to pass the clipping boundary in 00093 /// via an array. The array is expected to have four elements that 00094 /// supply the boundary like so: 00095 /// clip_boundary[0] = left 00096 /// clip_boundary[1] = right 00097 /// clip_boundary[2] = bottom 00098 /// clip_boundary[3] = top 00099 Clipper(const float clip_boundary[4]) ; 00100 00101 /// It is possible to create an instance of this clipper with some 00102 /// clipping boundary and then later change that. These methods allow 00103 /// clients to reset the clipping boundary to new values. 00104 //@{ 00105 void clip_boundary(float left, float right, float bottom, float top) { 00106 m_clip_boundary[0] = left ; 00107 m_clip_boundary[1] = right ; 00108 m_clip_boundary[2] = bottom ; 00109 m_clip_boundary[3] = top ; 00110 } 00111 00112 void clip_boundary(const float clip_boundary[4]) { 00113 m_clip_boundary[0] = clip_boundary[0] ; 00114 m_clip_boundary[1] = clip_boundary[1] ; 00115 m_clip_boundary[2] = clip_boundary[2] ; 00116 m_clip_boundary[3] = clip_boundary[3] ; 00117 } 00118 //@} 00119 00120 /// A line may lie completely or partially inside the clipping 00121 /// boundary. It may also be completely outside the clipping boundary. 00122 /// This implementation of the Cohen-Sutherland algorithm informs 00123 /// clients of what the original situation was using these bit flags. 00124 enum { 00125 COMPLETELY_INSIDE = 1, 00126 COMPLETELY_OUTSIDE = 2, 00127 FIRST_POINT_CLIPPED = 4, 00128 SECOND_POINT_CLIPPED = 8, 00129 BOTH_POINTS_CLIPPED = 12, 00130 } ; 00131 00132 /// This method implements the Cohen-Sutherland line clipping 00133 /// algorithm. It expects its first argument to be an array specifying 00134 /// the input line's end points. The clipped line is passed back to 00135 /// the client via the second parameter. Additionally, the function's 00136 /// return value specifies whether the original line was completely or 00137 /// partially inside the clipping boundary or completely outside of 00138 /// it. 00139 /// 00140 /// The input and output line's end points are stored in arrays of 00141 /// four elements like so: 00142 /// array[0] = x0 array[1] = y0 00143 /// array[2] = x1 array[3] = y1 00144 /// 00145 /// The return value is a set of bit flags that work like so: 00146 /// bit 0 = 1 ==> original line was completely inside 00147 /// bit 1 = 1 ==> original line was completely outside 00148 /// bit 2 = 1 ==> original line was partially inside and the 00149 /// first end-point was clipped 00150 /// bit 3 = 1 ==> original line was partially inside and the 00151 /// second end-point was clipped 00152 /// 00153 /// Bits 0, 1, and the remaining two are mutually exclusive, i.e., if 00154 /// bit 0 is on, then none of the others can be on; if bit 1 is on, 00155 /// all the others will be off. Bits 2 and 3 can be on at the same 00156 /// time; but if either of them is on, then bit 0 and 1 will be off. 00157 /// 00158 /// Rather than check the return code with magic numbers, the caller 00159 /// can use the COMPLETELY_INSIDE, COMPLETELY_OUTSIDE, 00160 /// FIRST_POINT_CLIPPED, SECOND_POINT_CLIPPED and/or 00161 /// BOTH_POINTS_CLIPPED enums defined above. 00162 unsigned char clip(const float end_points[4], 00163 float new_end_points[4]) const ; 00164 00165 private: 00166 /// The Cohen-Sutherland algorithm works by partitioning "space" into 00167 /// nine areas as shown below: 00168 /// 00169 /// | | 00170 /// TTFF | FTFF | FTTF 00171 /// | | 00172 /// ------+------+------ 00173 /// | | 00174 /// TFFF | FFFF | FFTF 00175 /// | | 00176 /// ------+------+------ 00177 /// | | 00178 /// TFFT | FFFT | FFTT 00179 /// | | 00180 /// 00181 /// The input line's end points are assigned a 4-bit code. Each bit in 00182 /// this code corresponds to a side of the clipping rectangle. This 00183 /// enum "de-magic-numbers" these code bits. 00184 enum { 00185 LEFT_BIT = 8, TOP_BIT = 4, RIGHT_BIT = 2, BOTTOM_BIT = 1, 00186 } ; 00187 00188 /// This function examines the point passed in to it and returns a 00189 /// four bit code specifying where the point is w.r.t. the clipping 00190 /// boundary's sides. The point is specified with an array of two 00191 /// elements, wherein the first element is the point's x-coordinate 00192 /// and the second element its y-coordinate. 00193 unsigned char cs_code(const float point[2]) const ; 00194 00195 /// A line lying completely inside the clipping rectangle will have 00196 /// both its end-points' codes zero. OR-ing the two codes will thus 00197 /// yield zero. Therefore, a line lying completely inside the clipping 00198 /// rectangle can be trivially accepted by OR-ing the Cohen-Sutherland 00199 /// codes of its end points and checking if the result is zero. 00200 bool trivial_accept(unsigned char code1, unsigned char code2) const { 00201 return (code1 | code2) == 0 ; 00202 } 00203 00204 /// The Cohen-Sutherland codes for the end points of a line lying 00205 /// completely to one side of the clipping rectangle will have at 00206 /// least one bit on in the same position. Thus, such a line can be 00207 /// trivially accepted by AND-ing its end points' codes and checking 00208 /// if the result is non-zero. 00209 bool trivial_reject(unsigned char code1, unsigned char code2) const { 00210 return (code1 & code2) != 0 ; 00211 } 00212 00213 /// This function checks if a point lies outside the clipping 00214 /// rectangle. The point is specified with an array of two elements; 00215 /// the first element is the point's x-coordinate and the second one 00216 /// its y-coordinate. 00217 bool outside(const float point[2]) const { 00218 return ( point[0] < m_clip_boundary[0] 00219 || point[0] > m_clip_boundary[1] 00220 || point[1] < m_clip_boundary[2] 00221 || point[1] > m_clip_boundary[3]) ; 00222 } 00223 00224 /// If a line cannot be trivially accepted or rejected, we have to do 00225 /// a little geometry to find the line's intersection points with the 00226 /// clipping rectangle and chop it down to size. This method takes 00227 /// care of the math for doing this. 00228 void chop(float point[2], unsigned char code, float dx, float dy) const ; 00229 } ; 00230 00231 //---------------------------------------------------------------------- 00232 00233 } // end of namespace encapsulating this file's definitions 00234 00235 #endif 00236 00237 /* So things look consistent in everyone's emacs... */ 00238 /* Local Variables: */ 00239 /* indent-tabs-mode: nil */ 00240 /* End: */
1.6.3