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.LineSegment; 011import renderer.framebuffer.*; 012import static renderer.pipeline.PipelineLogger.*; 013 014import java.awt.Color; 015 016/** 017 Rasterize a clipped {@link LineSegment} into shaded pixels 018 in a {@link FrameBuffer}'s viewport and (optionally) 019 anti-alias and gamma-encode the line at the same time. 020<p> 021 This pipeline stage takes a clipped {@link LineSegment} 022 with vertices in the {@link Camera}'s view rectangle and 023 rasterizezs the line segment into shaded, anti-aliased 024 pixels in a {@link FrameBuffer}'s viewport. This rasterizer 025 will linearly interpolate color from the line segment's two 026 endpoints to each rasterized (and anti-aliased) pixel in 027 the line segment. 028<p> 029 This rasterization algorithm is based on 030<pre> 031 "Fundamentals of Computer Graphics", 3rd Edition, 032 by Peter Shirley, pages 163-165. 033</pre> 034<p> 035 This rasterizer implements a simple version of Xiaolin_Wu's 036 anti-aliasing algorithm. See 037 <a href="https://en.wikipedia.org/wiki/Xiaolin_Wu's_line_algorithm" target="_top"> 038 https://en.wikipedia.org/wiki/Xiaolin_Wu's_line_algorithm</a> 039*/ 040public class Rasterize_AntiAlias_Line 041{ 042 /** 043 Rasterize a clipped {@link LineSegment} into anti-aliased, shaded pixels 044 in the {@link FrameBuffer.Viewport}. 045 046 @param model {@link Model} that the {@link LineSegment} {@code ls} comes from 047 @param ls {@link LineSegment} to rasterize into the {@link FrameBuffer.Viewport} 048 @param vp {@link FrameBuffer.Viewport} to hold rasterized pixels 049 */ 050 public static void rasterize(final Model model, 051 final LineSegment ls, 052 final FrameBuffer.Viewport vp) 053 { 054 // Get the viewport's background color. 055 final Color bg = vp.bgColorVP; 056 057 // Make local copies of several values. 058 final int w = vp.getWidthVP(); 059 final int h = vp.getHeightVP(); 060 061 final int vIndex0 = ls.vIndexList.get(0); 062 final int vIndex1 = ls.vIndexList.get(1); 063 final Vertex v0 = model.vertexList.get(vIndex0); 064 final Vertex v1 = model.vertexList.get(vIndex1); 065 066 final int cIndex0 = ls.cIndexList.get(0); 067 final int cIndex1 = ls.cIndexList.get(1); 068 final float[] c0 = model.colorList.get(cIndex0).getRGBComponents(null); 069 final float[] c1 = model.colorList.get(cIndex1).getRGBComponents(null); 070 float r0 = c0[0], g0 = c0[1], b0 = c0[2]; 071 float r1 = c1[0], g1 = c1[1], b1 = c1[2]; 072 073 // Transform each vertex to the "pixel plane" coordinate system. 074 double x0 = 0.5 + w/2.001 * (v0.x + 1); // x_pp = 0.5 + w/2 * (x_p+1) 075 double y0 = 0.5 + h/2.001 * (v0.y + 1); // y_pp = 0.5 + h/2 * (y_p+1) 076 double x1 = 0.5 + w/2.001 * (v1.x + 1); 077 double y1 = 0.5 + h/2.001 * (v1.y + 1); 078 // NOTE: Notice the 2.001 fudge factor in the last two equations. 079 // This is explained on page 142 of 080 // "Jim Blinn's Corner: A Trip Down The Graphics Pipeline" 081 // by Jim Blinn, 1996, Morgan Kaufmann Publishers. 082 083 if (Rasterize.debug) 084 { 085 logMessage(String.format("(x0_pp, y0_pp) = (%9.4f, %9.4f)", x0,y0)); 086 logMessage(String.format("(x1_pp, y1_pp) = (%9.4f, %9.4f)", x1,y1)); 087 } 088 089 // Round each vertex to the nearest logical pixel. 090 // This makes the algorithm a lot simpler, but it can 091 // cause a slight, but noticeable, shift of the line segment. 092 x0 = Math.round(x0); 093 y0 = Math.round(y0); 094 x1 = Math.round(x1); 095 y1 = Math.round(y1); 096 097 // Rasterize a degenerate line segment (a line segment 098 // that projected onto a point) as a single pixel. 099 if ( (x0 == x1) && (y0 == y1) ) 100 { 101 // We don't know which endpoint of the line segment 102 // is in front, so just pick v0. 103 final int x0_vp = (int)x0 - 1; // viewport coordinate 104 final int y0_vp = h - (int)y0; // viewport coordinate 105 106 if (Rasterize.debug) logPixel(x0, y0, 107 x0_vp, y0_vp, 108 r0, g0, b0, 109 vp); 110 // Log the pixel before setting it so that an array out- 111 // of-bounds error will be right after the pixel's address. 112 113 vp.setPixelVP(x0_vp, y0_vp, new Color(r0, g0, b0)); 114 115 return; 116 } 117 118 // If abs(slope) > 1, then transpose this line so that 119 // the transposed line has slope < 1. Remember that the 120 // line has been transposed. 121 boolean transposedLine = false; 122 if (Math.abs(y1 - y0) > Math.abs(x1 - x0)) // if abs(slope) > 1 123 { 124 // Swap x0 with y0. 125 final double temp0 = x0; 126 x0 = y0; 127 y0 = temp0; 128 // Swap x1 with y1. 129 final double temp1 = x1; 130 x1 = y1; 131 y1 = temp1; 132 transposedLine = true; // Remember that this line is transposed. 133 } 134 135 if (x1 < x0) // We want to rasterize in the direction of increasing x, 136 { // so, if necessary, swap (x0, y0) with (x1, y1). 137 // Swap x0 with x1. 138 final double tempX = x0; 139 x0 = x1; 140 x1 = tempX; 141 // Swap y0 with y1. 142 final double tempY = y0; 143 y0 = y1; 144 y1 = tempY; 145 // Swap the colors too. 146 final float tempR = r0; 147 final float tempG = g0; 148 final float tempB = b0; 149 r0 = r1; 150 g0 = g1; 151 b0 = b1; 152 r1 = tempR; 153 g1 = tempG; 154 b1 = tempB; 155 } 156 157 // Compute this line segment's slopes. 158 final double m = (y1 - y0) / (x1 - x0); 159 final double slopeR = (r1 - r0) / (x1 - x0); 160 final double slopeG = (g1 - g0) / (x1 - x0); 161 final double slopeB = (b1 - b0) / (x1 - x0); 162 163 if (Rasterize.debug) 164 { 165 final String inverseSlope = (transposedLine) 166 ? " (transposed, so 1/m = " + 1/m + ")" 167 : ""; 168 logMessage("Slope m = " + m + inverseSlope); 169 logMessage("Slope mRed = " + slopeR); 170 logMessage("Slope mGrn = " + slopeG); 171 logMessage("Slope mBlu = " + slopeB); 172 logMessage(String.format("(x0_vp, y0_vp) = (%9.4f, %9.4f)", x0-1,h-y0)); 173 logMessage(String.format("(x1_vp, y1_vp) = (%9.4f, %9.4f)", x1-1,h-y1)); 174 } 175 176 // Rasterize this line segment in the direction of increasing x. 177 // In the following loop, as x moves across the logical horizontal 178 // (or vertical) pixels, we will compute a y value for each x. 179 double y = y0; 180 for (int x = (int)x0; x < (int)x1; x += 1, y += m) 181 { 182 // Interpolate this pixel's color between the two endpoint's colors. 183 float r = (float)Math.abs(r0 + slopeR*(x - x0)); 184 float g = (float)Math.abs(g0 + slopeG*(x - x0)); 185 float b = (float)Math.abs(b0 + slopeB*(x - x0)); 186 // We need the Math.abs() because otherwise, we sometimes get -0.0. 187 188 if (Rasterize.doAntiAliasing) 189 { 190 // y must be between two vertical (or horizontal) logical pixel 191 // coordinates. Let y_low and y_hi be the logical pixel coordinates 192 // that bracket around y. 193 int y_low = (int)y; // the integer part of y 194 int y_hi = y_low + 1; 195 if (!transposedLine && y == h) y_hi = h; // test for the top edge 196 if ( transposedLine && y == w) y_hi = w; // test for the right edge 197 198 // Let weight be the fractional part of y. We will use 199 // weight to determine how much emphasis to place on 200 // each of the two pixels that bracket y. 201 final float weight = (float)(y - y_low); 202 203 // Interpolate colors for the low and high pixels. 204 // The smaller weight is, the closer y is to the lower 205 // pixel, so we give the lower pixel more emphasis when 206 // weight is small. 207 float r_low = (1 - weight) * r + weight * (bg.getRed() /255.0f); 208 float g_low = (1 - weight) * g + weight * (bg.getGreen()/255.0f); 209 float b_low = (1 - weight) * b + weight * (bg.getBlue() /255.0f); 210 float r_hi = weight * r + (1 - weight) * (bg.getRed() /255.0f); 211 float g_hi = weight * g + (1 - weight) * (bg.getGreen()/255.0f); 212 float b_hi = weight * b + (1 - weight) * (bg.getBlue() /255.0f); 213/* 214 // You can try replacing the above anti-aliasing code with this 215 // code to see that this simple idea doesn't work here (as it 216 // did in the previous renderer). This code just distributes the 217 // line's color between two adjacent pixels (instead of blending 218 // each pixel's color with the back ground color). This code ends 219 // up having pixels fade to black, instead of fading to the back 220 // ground color. 221 float r_low = (1 - weight) * r; 222 float g_low = (1 - weight) * g; 223 float b_low = (1 - weight) * b; 224 float r_hi = weight * r; 225 float g_hi = weight * g; 226 float b_hi = weight * b; 227*/ 228 if (Rasterize.doGamma) 229 { 230 // Apply gamma-encoding (gamma-compression) to the colors. 231 // https://www.scratchapixel.com/lessons/digital-imaging/digital-images 232 // http://blog.johnnovak.net/2016/09/21/what-every-coder-should-know-about-gamma/ 233 final double gammaInv = 1.0 / Rasterize.GAMMA; 234 r_low = (float)Math.pow(r_low, gammaInv); 235 r_hi = (float)Math.pow(r_hi, gammaInv); 236 g_low = (float)Math.pow(g_low, gammaInv); 237 g_hi = (float)Math.pow(g_hi, gammaInv); 238 b_low = (float)Math.pow(b_low, gammaInv); 239 b_hi = (float)Math.pow(b_hi, gammaInv); 240 } 241 242 // Set this (anti-aliased) pixel in the framebuffer. 243 if ( ! transposedLine ) 244 { 245 final int x_vp = x - 1; // viewport coordinate 246 final int y_vp_low = h - y_low; // viewport coordinate 247 final int y_vp_hi = h - y_hi; // viewport coordinate 248 249 if (Rasterize.debug) logPixelsAA(x, y, 250 x_vp, y_vp_low, y_vp_hi, 251 r_low, g_low, b_low, 252 r_hi, g_hi, b_hi, 253 vp); 254 255 vp.setPixelVP(x_vp, y_vp_low, new Color(r_low, g_low, b_low)); 256 vp.setPixelVP(x_vp, y_vp_hi, new Color(r_hi, g_hi, b_hi)); 257 } 258 else // a transposed line 259 { 260 final int x_vp_low = y_low - 1; // viewport coordinate 261 final int x_vp_hi = y_hi - 1; // viewport coordinate 262 final int y_vp = h - x; // viewport coordinate 263 264 if (Rasterize.debug) logPixelsAA(y, x, 265 x_vp_low, x_vp_hi, y_vp, 266 r_low, g_low, b_low, 267 r_hi, g_hi, b_hi, 268 vp); 269 270 vp.setPixelVP(x_vp_low, y_vp, new Color(r_low, g_low, b_low)); 271 vp.setPixelVP(x_vp_hi, y_vp, new Color(r_hi, g_hi, b_hi)); 272 } 273 } 274 else // No anti-aliasing. 275 { 276 if (Rasterize.doGamma) 277 { 278 // Apply gamma-encoding (gamma-compression) to the colors. 279 // https://www.scratchapixel.com/lessons/digital-imaging/digital-images 280 // http://blog.johnnovak.net/2016/09/21/what-every-coder-should-know-about-gamma/ 281 final double gammaInv = 1.0 / Rasterize.GAMMA; 282 r = (float)Math.pow(r, gammaInv); 283 g = (float)Math.pow(g, gammaInv); 284 b = (float)Math.pow(b, gammaInv); 285 } 286 287 // The value of y will almost always be between 288 // two vertical (or horizontal) pixel coordinates. 289 // By rounding off the value of y, we are choosing the 290 // nearest logical vertical (or horizontal) pixel coordinate. 291 if ( ! transposedLine ) 292 { 293 final int x_vp = x - 1; // viewport coordinate 294 final int y_vp = h - (int)Math.round(y); // viewport coordinate 295 296 if (Rasterize.debug) logPixel(x, y, 297 x_vp, y_vp, 298 r, g, b, 299 vp); 300 // Log the pixel before setting it so that an array out- 301 // of-bounds error will be right after the pixel's address. 302 303 vp.setPixelVP(x_vp, y_vp, new Color(r, g, b)); 304 } 305 else // a transposed line 306 { 307 final int x_vp = (int)Math.round(y) - 1; // viewport coordinate 308 final int y_vp = h - x; // viewport coordinate 309 310 if (Rasterize.debug) logPixel(y, x, 311 x_vp, y_vp, 312 r, g, b, 313 vp); 314 315 vp.setPixelVP(x_vp, y_vp, new Color(r, g, b)); 316 } 317 } 318 // Advance (x,y) to the next pixel (delta_x is 1, so delta_y is m). 319 } 320 // Set the pixel for the (x1,y1) endpoint. 321 // We do this separately to avoid rounding errors. 322 if ( ! transposedLine ) 323 { 324 final int x_vp = (int)x1 - 1; // viewport coordinate 325 final int y_vp = h - (int)y1; // viewport coordinate 326 327 if (Rasterize.debug) logPixel(x1, y1, 328 x_vp, y_vp, 329 r1, g1, b1, 330 vp); 331 332 vp.setPixelVP(x_vp, y_vp, new Color(r1, g1, b1)); 333 } 334 else // a transposed line 335 { 336 final int x_vp = (int)y1 - 1; // viewport coordinate 337 final int y_vp = h - (int)x1; // viewport coordinate 338 339 if (Rasterize.debug) logPixel(y1, x1, 340 x_vp, y_vp, 341 r1, g1, b1, 342 vp); 343 344 vp.setPixelVP(x_vp, y_vp, new Color(r1, g1, b1)); 345 } 346 } 347 348 349 350 // Private default constructor to enforce noninstantiable class. 351 // See Item 4 in "Effective Java", 3rd Ed, Joshua Bloch. 352 private Rasterize_AntiAlias_Line() { 353 throw new AssertionError(); 354 } 355}