001package pipeline; 002import scene.*; 003 004/** 005 Clip any (projected) line segment that sticks out of the view rectangle 006 in the view plane. Interpolate vertex color from the clipped off vertex 007 to the new vertex. 008 009 This clipping algorithm is a simplification of the Liang-Barsky Parametric 010 Line Clipping algorithm. 011 012 This algorithm assumes that all LineSegment objects have been projected onto 013 the camera's view plane, z = -1. This algorithm also assumes that the camera's 014 view rectangle in the view plane is 015 -1 <= x <= +1 and 016 -1 <= y <= +1. 017 018 If a line segment's projected vertex has an x or y coordinate with absolute 019 value greater than 1, then that vertex "sticks out" of the view rectangle. 020 This algorithm will clip the line segment so that both of the line segment's 021 vertices are within the view rectangle with -1 <= x <= +1 and -1 <= y <= +1. 022 023 024 Here is an outline of the clipping algorithm. 025 026 Recursively process each line segment, using the following steps. 027 028 1) Test if the line segment no longer needs to be clipped, i.e., both of 029 its vertices are within the clipping rectangle. If this is the case, 030 then return true. 031 032 2) Test if the line segment should be "trivially rejected". A line segment 033 is "trivially rejected" if it is on the wrong side of any of the four 034 lines that bound the view rectangle (i.e., the four lines x = 1, x = -1, 035 y = 1, y = -1). If so, then return false (so the line segment will not 036 be rasterized into the framebuffer). 037 038 Notice that a line like the following one is trivially rejected because it 039 is on the "wrong" side of the line x=1. 040 041 x=1 042 | v1 043 | / 044 +----------+ / 045 | | / 046 | | / 047 | | / 048 | | / 049 | | / 050 +----------+ / 051 | / 052 | v0 053 054 But the following line is NOT trivially rejected because, even though it 055 is completely outside of the view rectangle, this line is not entirely on 056 the wrong side of any one of the four lines x = 1, x = -1, y = 1, or y = -1. 057 The line below will get clipped at least one time (either on the line x = 1 058 or the line y = -1) before it is (recursively) a candidate for "trivial rejection". 059 Notice that the line below could even be clipped twice, first on y = 1, then 060 on x = 1, before it can be trivially rejected (by being on the wrong side 061 of y = -1). 062 x=1 063 | v1 064 | / 065 +----------+ / 066 | | / 067 | | / 068 | | / 069 | | / 070 | | / 071 +----------+ / 072 | / 073 | / 074 / 075 / 076 v0 | 077 | 078 079 3) If the line segment has been neither accepted nor rejected, then it needs 080 to be clipped. So we test the line segment against each of the four clipping 081 lines, x = 1, x = -1, y = 1, and y = -1, to determine if the line segment 082 crosses one of those lines. We clip the line segment against the first line 083 which we find that it crosses. Then we recursively clip the resulting clipped 084 line segment. (Notice that we only clip against the first clipping line which 085 the segment is found to cross. We do not continue to test against the other 086 clipping lines. This is because it may be the case, after just one clip, that 087 the line segment is now a candidate for trivial accept or reject. So rather 088 than test the line segment against several more clipping lines (which may be 089 useless tests) it is more efficient to recursively clip the line segment, 090 which will then start with the trivial accept or reject tests.) 091 092 When we clip a line segment against a clipping line, it is always the case that 093 one endpoint of the line segment is on the "right" side of the clipping line and 094 the other endpoint of the line segment is on the "wrong" side of the clipping 095 line. In the following picture, assume that v0 is on the "wrong" side of the 096 clipping line (x = 1) and v1 is on the "right" side. So v0 needs to be clipped 097 off the line segment and replaced by a new endpoint. 098 099 x=1 100 | 101 v1 | 102 \ | 103 \ | 104 \ 105 | \ 106 | \ 107 | v0 108 109 Represent points p(t) on the line segment between v0 and v1 with the 110 following parametric equation. 111 p(t) = (1-t) * v0 + t * v1 with 0 <= t <= 1 112 Notice that this equation parameterizes the line segment starting with v0 113 at t=0 (on the "wrong side") and ending with v1 at t=1 (on the "right side"). 114 We need to find the value of t when the line segment crosses the clipping 115 line x = 1. Let v0=(x0, y0) and let v1=(x1, y1). Then the above parametric 116 equation becomes the two component equations 117 x(t) = (1-t) * x0 + t * x1, 118 y(t) = (1-t) * y0 + t * y1, with 0 <= t <= 1. 119 Since the clipping line in this example is x = 1, we need to solve the 120 equation x(t) = 1 for t. So we need to solve 121 (1-t) * x0 + t * x1 = 1 122 for t. Here are a few algebra steps. 123 x0 - t * x0 + t * x1 = 1 124 x0 + t * (x1 - x0) = 1 125 t * (x1 - x0) = 1 - x0 126 t = (1 - x0)/(x1 - x0) 127 We get similar equations for t if we clip against the other clipping lines 128 (x = -1, y = 1, or y = -1) and we assume that v0 is on the "wrong side" and 129 v1 is on the "right side". With the above value for t, the new point p(t) 130 that replaces v0 can easily be computed. 131 132 x=1 133 | 134 v1 | 135 \ | 136 \ | 137 v0=p( (1 - x0)/(x1 - x0) ) 138 | 139 | 140 | 141 142 Finally, the new line segment between v1 and the new v0 is recursively 143 clipped so that it can be checked once again to see if it can be trivially 144 accepted, trivially rejected, or clipped again. 145*/ 146public class Clip 147{ 148 /** 149 If the line segment sticks out of the view rectangle, then 150 clip it so that it is contained in the view rectangle. 151 152 @param ls LineSegment to be clipped 153 @return a boolean that indicates if this line segment is within the view rectangle 154 */ 155 public static boolean clip(LineSegment ls) 156 { 157 // make local copies of several values 158 Vertex v0 = ls.v[0], v1 = ls.v[1]; 159 double x0 = v0.x, x1 = v1.x; 160 double y0 = v0.y, y1 = v1.y; 161 162 // 1. Check for trivial accept. 163 if ( ! ( Math.abs( x0 ) > 1 164 || Math.abs( y0 ) > 1 165 || Math.abs( x1 ) > 1 166 || Math.abs( y1 ) > 1 ) ) 167 { 168 //System.err.println("Trivial accept."); 169 return true; 170 } 171 // 2. Check for trivial delete. 172 else if ( (x0 > 1 && x1 > 1) // to the right of the line x = 1 173 || (x0 < -1 && x1 < -1) // to the left of the line x = -1 174 || (y0 > 1 && y1 > 1) // above the line y = 1 175 || (y0 < -1 && y1 < -1) ) // below the line y = -1 176 { 177 //System.err.println("Trivial delete."); 178 return false; 179 } 180 // 3. Need to clip this line segment. 181 if (x0 > 1 || x1 > 1) // ls crosses the line x = 1 182 { 183 if (x1 > 1) // clip off v1 184 { 185 // create a new Vertex between v[0] and v[1] 186 Vertex v_new = interpolateNewVertex(v0, v1, 1); 187 // modify the LineSegment to contain v[0] and the new Vertex 188 ls.v[1] = v_new; 189 } 190 else // (x0 > 1) // clip off v0 191 { 192 // create a new Vertex between v[1] and v[0] 193 Vertex v_new = interpolateNewVertex(v1, v0, 1); 194 // modify the LineSegment to contain v[1] and the new Vertex 195 ls.v[0] = v_new; 196 } 197 } 198 else if (x0 < -1 || x1 < -1) // ls crosses the line x = -1 199 { 200 if (x1 < -1) // clip off v1 201 { 202 // create a new Vertex between v0 and v1 203 Vertex v_new = interpolateNewVertex(v0, v1, 2); 204 // modify the LineSegment to contain v0 and the new Vertex 205 ls.v[1] = v_new; 206 } 207 else // (x0 < -1) // clip off v0 208 { 209 // create a new Vertex between v1 and v0 210 Vertex v_new = interpolateNewVertex(v1, v0, 2); 211 // modify the LineSegment to contain v1 and the new Vertex 212 ls.v[0] = v_new; 213 } 214 } 215 else if (y0 > 1 || y1 > 1) // ls crosses the line y = 1 216 { 217 if (y1 > 1) // clip off v1 218 { 219 // create a new Vertex between v0 and v1 220 Vertex v_new = interpolateNewVertex(v0, v1, 3); 221 // modify the LineSegment to contain v0 and the new Vertex 222 ls.v[1] = v_new; 223 } 224 else // (y0 > 1) // clip off v0 225 { 226 // create a new Vertex between v1 and v0 227 Vertex v_new = interpolateNewVertex(v1, v0, 3); 228 // modify the LineSegment to contain v1 and the new Vertex 229 ls.v[0] = v_new; 230 } 231 } 232 else if (y0 < -1 || y1 < -1) // ls crosses the line y = -1 233 { 234 if (y1 < -1) // clip off v1 235 { 236 // create a new Vertex between v0 and v1 237 Vertex v_new = interpolateNewVertex(v0, v1, 4); 238 // modify the LineSegment to contain v0 and the new Vertex 239 ls.v[1] = v_new; 240 } 241 else // (y0 < -1) // clip off v0 242 { 243 // create a new Vertex between v1 and v0 244 Vertex v_new = interpolateNewVertex(v1, v0, 4); 245 // modify the LineSegment to contain v1 and the new Vertex 246 ls.v[0] = v_new; 247 } 248 } 249 else 250 { // should never get here 251 System.err.println("Clipping error!"); 252 System.exit(-1); 253 } 254 return clip(ls); // recursively clip this line segment again 255 } 256 257 258 /** 259 This method takes in two vertices, one that is on the "right" side 260 of a clipping line and the other that is on the "wrong" side of the 261 clipping line, and an integer which specifies which clipping line 262 to use, where 263 eqn_number == 1 means the clipping line x = 1 264 eqn_number == 2 means the clipping line x =-1 265 eqn_number == 3 means the clipping line y = 1 266 eqn_number == 4 means the clipping line y =-1 267 268 This method returns the vertex that is the intersection point 269 between the given line segment and the given clipping line. 270 271 This method solves for the value of t for which the parametric 272 equation 273 p(t) = (1-t) * v_outside + t * v_inside 274 intersects the given clipping line (notice that the equation 275 is parameterized so that we move from the outside vertex towards 276 the inside vertex as t increases from 0 to 1). The solved for 277 value of t is then plugged into the parametric formula to get 278 the coordinates of the intersection point. 279 280 @param v_inside the Vertex that is inside the view rectangle 281 @param v_outside the Vertex that is outside the view rectangle 282 @param eqn_number the identifier of the view rectangle edge crossed by the line segment 283 @return a Vertex object that replaces the clipped off vertex 284 */ 285 private static Vertex interpolateNewVertex(Vertex v_inside, 286 Vertex v_outside, 287 int eqn_number) 288 { 289 //System.err.println("Create new vertex."); 290 // make local copies of several values 291 double vix = v_inside.x; // "i" for "inside" 292 double viy = v_inside.y; 293 double vox = v_outside.x; // "o" for "outside" 294 double voy = v_outside.y; 295 // interpolate between v_outside and v_inside 296 double t = 0.0; 297 if (1 == eqn_number) // clip to x = 1 298 t = (1 - vox) / (vix - vox); 299 else if (2 == eqn_number) // clip to x = -1 300 t = (-1 - vox) / (vix - vox); 301 else if (3 == eqn_number) // clip to y = 1 302 t = (1 - voy) / (viy - voy); 303 else if (4 == eqn_number) // clip to y = -1 304 t = (-1 - voy) / (viy - voy); 305 306 Vertex v_new = new Vertex(); 307 308 // use the value of t to interpolate the coordinates of the new vertex 309 v_new.x = (1-t) * vox + t * vix; 310 v_new.y = (1-t) * voy + t * viy; 311 // use the value of t to interpolate the color of the new vertex 312 v_new.r = (1-t) * v_outside.r + t * v_inside.r; 313 v_new.g = (1-t) * v_outside.g + t * v_inside.g; 314 v_new.b = (1-t) * v_outside.b + t * v_inside.b; 315 316 return v_new; 317 } 318 319}