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}