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}