001/* 002 * Renderer 7. The MIT License. 003 * Copyright (c) 2022 rlkraft@pnw.edu 004 * See LICENSE for details. 005*/ 006 007package renderer.pipeline; 008 009import renderer.scene.*; 010import renderer.scene.primitives.*; 011import static renderer.pipeline.PipelineLogger.*; 012 013import java.awt.Color; 014import java.util.Optional; 015 016/** 017 Clip a (projected) {@link LineSegment} that sticks out of the 018 view rectangle in the image plane. Interpolate {@link Vertex} 019 color from any clipped off {@code Vertex} to the new {@code Vertex}. 020<p> 021 This clipping algorithm is a simplification of the Liang-Barsky 022 Parametric Line Clipping algorithm. 023<p> 024 This algorithm assumes that all {@code Vertex} objects have been 025 projected onto the {@link renderer.scene.Camera}'s image plane, 026 {@code z = -1}. This algorithm also assumes that the camera's view 027 rectangle in the image plane is 028 <pre>{@code 029 -1 <= x <= +1 and 030 -1 <= y <= +1. 031 }</pre> 032<p> 033 If a line segment's projected vertex has an {@code x} or {@code y} 034 coordinate with absolute value greater than 1, then that vertex 035 "sticks out" of the view rectangle. This algorithm will clip the 036 line segment so that both of the line segment's vertices are within 037 the view rectangle. 038<p> 039 Here is an outline of the clipping algorithm. 040<p> 041 Recursively process each line segment, using the following steps. 042<p> 043 1) Test if the line segment no longer needs to be clipped, i.e., 044 both of its vertices are within the view rectangle. If this is 045 the case, then return true. 046 <pre>{@code 047 x=-1 x=+1 048 | | 049 | | 050 ----+----------+----- y = +1 051 | v1 | 052 | / | 053 | / | 054 | / | 055 | v0 | 056 ----+----------+----- y = -1 057 | | 058 | | 059 }</pre> 060<p> 061 2) Test if the line segment should be "trivially rejected". A line 062 segment is "trivially rejected" if it is on the wrong side of any 063 of the four lines that bound the view rectangle (i.e., the four 064 lines {@code x = 1}, {@code x = -1}, {@code y = 1}, {@code y = -1}). 065 If so, then return {@code false} (so the line segment will not be 066 rasterized into the framebuffer). 067<p> 068 Notice that a line like the following one is trivially rejected 069 because it is on the "wrong" side of the line {@code x = 1}. 070 <pre>{@code 071 x=1 072 | v1 073 | / 074 +----------+ / 075 | | / 076 | | / 077 | | / 078 | | / 079 | | / 080 +----------+ / 081 | / 082 | v0 083 }</pre> 084 But the following line is NOT trivially rejected because, even 085 though it is completely outside of the view rectangle, this line 086 is not entirely on the wrong side of any one of the four lines 087 {@code x = 1}, {@code x = -1}, {@code y = 1}, or {@code y = -1}. 088 The line below will get clipped at least one time (either on the 089 line {@code x = 1} or the line {@code y = -1}) before it is 090 (recursively) a candidate for "trivial rejection". Notice that 091 the line below could even be clipped twice, first on {@code y = 1}, 092 then on {@code x = 1}, before it can be trivially rejected (by 093 being on the wrong side of {@code y = -1}). 094 <pre>{@code 095 x=1 096 | v1 097 | / 098 +----------+ / 099 | | / 100 | | / 101 | | / 102 | | / 103 | | / 104 +----------+ / 105 | / 106 |/ 107 / 108 /| 109 / | 110 v0 111 }</pre> 112<p> 113 3) If the line segment has been neither accepted nor rejected, then 114 it needs to be clipped. So we test the line segment against each 115 of the four clipping lines, {@code x = 1}, {@code x = -1}, 116 {@code y = 1}, and {@code y = -1}, to determine if the line segment 117 crosses one of those lines. We clip the line segment against the 118 first line which we find that it crosses. Then we recursively clip 119 the resulting clipped line segment. Notice that we only clip against 120 the first clipping line which the segment is found to cross. We do 121 not continue to test against the other clipping lines. This is 122 because it may be the case, after just one clip, that the line 123 segment is now a candidate for trivial accept or reject. So rather 124 than test the line segment against several more clipping lines 125 (which may be useless tests) it is more efficient to recursively 126 clip the line segment, which will then start with the trivial accept 127 or reject tests. 128<p> 129 When we clip a line segment against a clipping line, it is always 130 the case that one endpoint of the line segment is on the "right" 131 side of the clipping line and the other endpoint is on the "wrong" 132 side of the clipping line. In the following picture, assume that 133 {@code v0} is on the "wrong" side of the clipping line ({@code x = 1}) 134 and {@code v1} is on the "right" side. So {@code v0} needs to be 135 clipped off the line segment and replaced by a new vertex. 136 <pre>{@code 137 x=1 138 v1 | 139 \ | 140 \ | 141 \| 142 \ 143 |\ 144 | \ 145 | \ 146 | v0 147 }</pre> 148 Represent points {@code p(t)} on the line segment between {@code v0} 149 and {@code v1} with the following parametric equation. 150 <pre>{@code 151 p(t) = (1-t) * v0 + t * v1 with 0 <= t <= 1 152 }</pre> 153 Notice that this equation parameterizes the line segment starting 154 with {@code v0} at {@code t=0} (on the "wrong side") and ending 155 with {@code v1} at {@code t=1} (on the "right side"). We need to 156 find the value of {@code t} when the line segment crosses the 157 clipping line {@code x = 1}. Let {@code v0 = (x0, y0)} and let 158 {@code v1 = (x1, y1)}. Then the above parametric equation becomes 159 the two component equations 160 <pre>{@code 161 x(t) = (1-t) * x0 + t * x1, 162 y(t) = (1-t) * y0 + t * y1, with 0 <= t <= 1. 163 }</pre> 164 Since the clipping line in this example is {@code x = 1}, we need 165 to solve the equation {@code x(t) = 1} for {@code t}. So we need 166 to solve 167 <pre>{@code 168 1 = (1-t) * x0 + t * x1 169 }</pre> 170 for {@code t}. Here are a few algebra steps. 171 <pre>{@code 172 1 = x0 - t * x0 + t * x1 173 1 = x0 + t * (x1 - x0) 174 1 - x0 = t * (x1 - x0) 175 t = (1 - x0)/(x1 - x0) 176 }</pre> 177 We get similar equations for {@code t} if we clip against the other 178 clipping lines ({@code x = -1}, {@code y = 1}, or {@code y = -1}) 179 and we assume that {@code v0} is on the "wrong side" and {@code v1} 180 is on the "right side". 181<p> 182 Let {@code t0} denote the above value for {@code t}. With this value 183 for {@code t}, we can compute the y-coordinate of the new vertex 184 {@code p(t0)} that replaces {@code v0}. 185 <pre>{@code 186 x=1 187 v1 | 188 \ | 189 \ | 190 \ | 191 p(t0)=(1, y(t0)) 192 | 193 | 194 | 195 }</pre> 196 Here is the algebra. 197 <pre>{@code 198 y(t0) = (1-t0) * y0 + t0 * y1 199 = y0 + t0 * (y1 - y0) 200 = y0 + (1 - x0)*((y1 - y0)/(x1 - x0)) 201 }</pre> 202 Finally, the new line segment between {@code v1} and the new 203 vertex {@code p(t0)} is recursively clipped so that it can be 204 checked to see if it should be trivially accepted, trivially 205 rejected, or clipped again. 206*/ 207public class Clip_Line 208{ 209 /** 210 If the {@link LineSegment} sticks out of the view rectangle, 211 then return a clipped version that is contained in the view 212 rectangle. The new, clipped {@link LineSegment} object is 213 returned wrapped in an {@link Optional} object. 214 <p> 215 At least one new clipped {@link Vertex} will be added to the 216 {@link Model}'s vertex list (and as many as four new vertices 217 may be added to the {@link Model}'s vertex list). 218 <p> 219 If the {@link LineSegment} is completely outside of the view 220 rectangle, then return an empty {@link Optional} object to 221 indicate that the {@link LineSegment} should be discarded. 222 223 @param model {@link Model} that the {@link LineSegment} {@code ls} comes from 224 @param ls {@link LineSegment} to be clipped 225 @return a clipped version of {@code ls} wrapped in an {@link Optional} object 226 */ 227 public static Optional<Primitive> clip(final Model model, 228 final LineSegment ls) 229 { 230 // Make local copies of several values. 231 final int vIndex0 = ls.vIndexList.get(0); 232 final int vIndex1 = ls.vIndexList.get(1); 233 final Vertex v0 = model.vertexList.get(vIndex0); 234 final Vertex v1 = model.vertexList.get(vIndex1); 235 236 final double x0 = v0.x, y0 = v0.y; 237 final double x1 = v1.x, y1 = v1.y; 238 239 // 1. Check for trivial accept. 240 if ( ! ( Math.abs( x0 ) > 1 241 || Math.abs( y0 ) > 1 242 || Math.abs( x1 ) > 1 243 || Math.abs( y1 ) > 1 ) ) 244 { 245 if (Clip.debug) logMessage("-- Trivial accept."); 246 return Optional.of(ls); // better than "return ls" 247 } 248 // 2. Check for trivial delete. 249 else if ( (x0 > 1 && x1 > 1) // to the right of the line x = 1 250 || (x0 < -1 && x1 < -1) // to the left of the line x = -1 251 || (y0 > 1 && y1 > 1) // above the line y = 1 252 || (y0 < -1 && y1 < -1) ) // below the line y = -1 253 { 254 if (Clip.debug) logMessage("-- Trivial delete."); 255 return Optional.empty(); // better than "return null" 256 } 257 // 3. Need to clip this line segment. 258 else 259 { 260 // Recursively clip a new (clipped) line segment. 261 return clip(model, clipOneTime(model, ls)); 262 } 263 } 264 265 266 /** 267 This method takes in a line segment that crosses one of the four 268 clipping lines. This method returns a new LineSegment that uses 269 a new, interpolated, Vertex that is the intersection point between 270 the given LineSegment and the crossed clipping line. 271 <p> 272 This method solves for the value of {@code t} for which the 273 parametric equation 274 <pre>{@code 275 p(t) = (1-t) * v_outside + t * v_inside 276 }</pre> 277 intersects the crossed clipping line. (Notice that the equation 278 is parameterized so that we move from the outside vertex towards 279 the inside vertex as {@code t} increases from 0 to 1.) The solved 280 for value of {@code t} is then plugged into the parametric formula 281 to get the coordinates of the intersection point. 282 <p> 283 The new interpolated Vertex is added to the end of the vertex list 284 from the given Model. 285 286 @param model {@link Model} that the {@link LineSegment} {@code ls} comes from 287 @param ls the {@link LineSegment} being clipped 288 @return a new clipped {@link LineSegment} object 289 */ 290 private static LineSegment clipOneTime(final Model model, 291 final LineSegment ls) 292 { 293 // Make local copies of several values. 294 final int vIndex0 = ls.vIndexList.get(0); 295 final int vIndex1 = ls.vIndexList.get(1); 296 final Vertex v0 = model.vertexList.get(vIndex0); 297 final Vertex v1 = model.vertexList.get(vIndex1); 298 299 final double x0 = v0.x, y0 = v0.y; 300 final double x1 = v1.x, y1 = v1.y; 301 302 final String equation; // keep track of which edge is crossed 303 final int vOutside; // keep track of which vertex is on the outside 304 final double vOx, vOy; // "O" for "outside" 305 final double vIx, vIy; // "I" for "inside" 306 final double t; // when we cross the clipping line 307 final double x; // x-coordinate of where we cross the clipping line 308 final double y; // y-coordinate of where we cross the clipping line 309 final int vIndexNew; // index for the new, interpolated, vertex 310 311 if (x0 > 1) // ls crosses the line x = 1 312 { 313 equation = "x = +1"; 314 vOutside = 0; 315 vOx = x0; vOy = y0; 316 vIx = x1; vIy = y1; 317 t = (1 - vOx) / (vIx - vOx); 318 x = 1; // prevent rounding errors 319 y = (1 - t) * vOy + t * vIy; 320 final Vertex newVertex = new Vertex(x, y, 0); 321 // Modify the Model to contain the new Vertex. 322 vIndexNew = model.vertexList.size(); 323 model.vertexList.add(newVertex); 324 } 325 else if (x1 > 1) // ls crosses the line x = 1 326 { 327 equation = "x = +1"; 328 vOutside = 1; 329 vIx = x0; vIy = y0; 330 vOx = x1; vOy = y1; 331 t = (1 - vOx) / (vIx - vOx); 332 x = 1; // prevent rounding errors 333 y = (1 - t) * vOy + t * vIy; 334 final Vertex newVertex = new Vertex(x, y, 0); 335 vIndexNew = model.vertexList.size(); 336 model.vertexList.add(newVertex); 337 } 338 else if (x0 < -1) // ls crosses the line x = -1 339 { 340 equation = "x = -1"; 341 vOutside = 0; 342 vOx = x0; vOy = y0; 343 vIx = x1; vIy = y1; 344 t = (-1 - vOx) / (vIx - vOx); 345 x = -1; // prevent rounding errors 346 y = (1 - t) * vOy + t * vIy; 347 final Vertex newVertex = new Vertex(x, y, 0); 348 vIndexNew = model.vertexList.size(); 349 model.vertexList.add(newVertex); 350 } 351 else if (x1 < -1) // ls crosses the line x = -1 352 { 353 equation = "x = -1"; 354 vOutside = 1; 355 vIx = x0; vIy = y0; 356 vOx = x1; vOy = y1; 357 t = (-1 - vOx) / (vIx - vOx); 358 x = -1; // prevent rounding errors 359 y = (1 - t) * vOy + t * vIy; 360 final Vertex newVertex = new Vertex(x, y, 0); 361 vIndexNew = model.vertexList.size(); 362 model.vertexList.add(newVertex); 363 } 364 else if (y0 > 1) // ls crosses the line y = 1 365 { 366 equation = "y = +1"; 367 vOutside = 0; 368 vOx = x0; vOy = y0; 369 vIx = x1; vIy = y1; 370 t = (1 - vOy) / (vIy - vOy); 371 x = (1 - t) * vOx + t * vIx; 372 y = 1; // prevent rounding errors 373 final Vertex newVertex = new Vertex(x, y, 0); 374 vIndexNew = model.vertexList.size(); 375 model.vertexList.add(newVertex); 376 } 377 else if (y1 > 1) // ls crosses the line y = 1 378 { 379 equation = "y = +1"; 380 vOutside = 1; 381 vIx = x0; vIy = y0; 382 vOx = x1; vOy = y1; 383 t = (1 - vOy) / (vIy - vOy); 384 x = (1 - t) * vOx + t * vIx; 385 y = 1; // prevent rounding errors 386 final Vertex newVertex = new Vertex(x, y, 0); 387 vIndexNew = model.vertexList.size(); 388 model.vertexList.add(newVertex); 389 } 390 else if (y0 < -1) // ls crosses the line y = -1 391 { 392 equation = "y = -1"; 393 vOutside = 0; 394 vOx = x0; vOy = y0; 395 vIx = x1; vIy = y1; 396 t = (-1 - vOy) / (vIy - vOy); 397 x = (1 - t) * vOx + t * vIx; 398 y = -1; // prevent rounding errors 399 final Vertex newVertex = new Vertex(x, y, 0); 400 vIndexNew = model.vertexList.size(); 401 model.vertexList.add(newVertex); 402 } 403 else // if (y1 < -1) // ls crosses the line y = -1 404 { 405 equation = "y = -1"; 406 vOutside = 1; 407 vIx = x0; vIy = y0; 408 vOx = x1; vOy = y1; 409 t = (-1 - vOy) / (vIy - vOy); 410 x = (1 - t) * vOx + t * vIx; 411 y = -1; // prevent rounding errors 412 final Vertex newVertex = new Vertex(x, y, 0); 413 vIndexNew = model.vertexList.size(); 414 model.vertexList.add(newVertex); 415 } 416 417 // Use the value of t to interpolate the color of the new vertex. 418 final int cIndexI = ls.cIndexList.get(1 - vOutside); 419 final int cIndexO = ls.cIndexList.get( vOutside); 420 float cI[] = model.colorList.get(cIndexI).getRGBColorComponents(null); 421 float cO[] = model.colorList.get(cIndexO).getRGBColorComponents(null); 422 final float t_ = (float)t; 423 final float r = (1 - t_) * cO[0] + t_ * cI[0]; 424 final float g = (1 - t_) * cO[1] + t_ * cI[1]; 425 final float b = (1 - t_) * cO[2] + t_ * cI[2]; 426 427 // Modify the Model to contain the new Color. 428 final Color newColor = new Color(r, g, b); 429 final int cIndexNew = model.colorList.size(); 430 model.colorList.add(newColor); 431 432 if (Clip.debug) 433 { 434 final String vOut = (0==vOutside) ? "v0" : "v1"; 435 logMessage( 436 String.format("-- Clip off %s at %s", vOut, equation)); 437 logMessage( 438 String.format("-- t = % .25f", t)); 439 logMessage( 440 String.format("-- <x_i, y_i> = <% .24f, % .24f>", vIx, vIy)); 441 logMessage( 442 String.format("-- <x_o, y_o> = <% .24f, % .24f>", vOx, vOy)); 443 logMessage( 444 String.format("-- <x_c, y_c> = <% .24f, % .24f>", x, y)); 445 logMessage( 446 String.format("-- <r_i, g_i, b_i> = <% .15f, % .15f, % .15f>", 447 cI[0], cI[1], cI[2])); 448 logMessage( 449 String.format("-- <r_o, g_o, b_o> = <% .15f, % .15f, % .15f>", 450 cO[0], cO[1], cO[2])); 451 logMessage( 452 String.format("-- <r_c, g_c, b_c> = <% .15f, % .15f, % .15f>", 453 r, g, b)); 454 } 455 456 // Return a new LineSegment using the new Vertex and Color and 457 // keeping the old LineSegment's inside Vertex and Color. 458 final LineSegment newLS; 459 if (1 == vOutside) 460 { 461 newLS = new LineSegment(vIndex0, vIndexNew, 462 cIndexI, cIndexNew); 463 } 464 else 465 { 466 newLS = new LineSegment(vIndexNew, vIndex1, 467 cIndexNew, cIndexI); 468 } 469 return newLS; 470 } 471 472 473 474 // Private default constructor to enforce noninstantiable class. 475 // See Item 4 in "Effective Java", 3rd Ed, Joshua Bloch. 476 private Clip_Line() { 477 throw new AssertionError(); 478 } 479}