
3. Improved Line Clipping
=========================

If a line segment is partly inside and partly outside of the camera's
view volume, then we should clip off from the line segment that part
of it which is not in the view volume.

If a line segment is entirely outside of the camera's the view volume,
then we should discard it from any further processing by the renderer.

We have three choices for when we can clip line segments.

1. before projection (in 3D camera coordinates),<br>
      clip -> project -> viewport transformation -> rasterize
2. after projection (in the 2D image-plane),<br>
      project -> clip -> viewport transformation -> rasterize
3. after viewport transformation (in the 2D pixel-plane)<br>
      project -> viewport transformation -> clip -> rasterize

In the first option, we clip line segments in camera space so that they
are within the camera's view volume. In the second option we clip
projected line segments in the image-plane so that they are within the
image-plane's view rectangle. In the third option, we clip pixels in the
pixel-plane so that we keep only those pixels that are within the
pixel-plane's logical viewport.

In the previous renderer we used the third option. We clipped line
segments during rasterization by not putting into the framebuffer's
viewport any line segment fragment that is outside of the pixel-plane's
logical viewport. But this clipping algorithm requires that we compute
every fragment of every line segment and then check if it fits in the
framebuffer's viewport (that is, is the fragment inside of the logical
viewport). This could be a big waste of CPU time. If a line segment
extends from within the viewport to billions of pixels outside the
viewport, then we would be needlessly computing a lot of fragments
to discard. Even worse, if no part of the line segment is in the view
volume, we would still be rasterizing, pixel by pixel, the whole line
segment. As we saw in the demonstration program
```text
     renderer_1\clients_r1\SomethingWrong_1.java
```
clipping while rasterizing can cause the renderer to become unresponsive
while it is "clipping" a line that has billions of fragments outside of
the pixel-plane's logical viewport.

The first option, clipping line segments in camera coordinates before
projection, is awkward because we need to clip against the perspective
view volume differently than against the orthographic view volume. Also,
we would need to clip against slanted planes for the perspective projection.
Because of this awkwardness, most renderers do not clip before projection.

The best approach is to clip projected line segments in the image-plane.
We should clip a line segment so that both of its end points are within
the view rectangle. If both endpoints of a line segment are within the
view rectangle, then all the rasterized fragments of the line segment
will be within the pixel-plane's logical viewport.


3.1 Renderer source code
========================

The Java source code for this renderer is publicly available as a zip file.

Here is a link to the renderer's source code.

* <http://cs.pnw.edu/~rlkraft/cs45500/for-class/renderer_3.zip>

Download and unzip the source code to any convenient location in your
computer's file system. The renderer does not have any dependencies
other than the Java 11 (or later) JDK. Once you have downloaded and
unzipped the distribution, you are ready to compile the renderer and
run the renderer's (interactive) example programs.

This renderer has three new files in the `pipeline` package,

* `Clip.java`,
* `Clip_Line.java`,
* `Clip_Point.java`.

The files `Pipeline.java` and `Pipeline2.java` are modified to put the
new clipping stage into the rendering pipeline. The rasterizing stage
is modified to remove the previous clipping code. All of the other
files in the renderer are unchanged, including the clients.


3.2 Pipeline
============

Our pipeline has the following five stages.

```text
       v_0 ... v_n     A Model's list of Vertex objects
          \   /
           \ /
            |
            | model coordinates (of v_0 ... v_n)
            |
        +-------+
        |       |
        |   P1  |    Model-to-camera transformation (of the vertices)
        |       |
        +-------+
            |
            | camera coordinates (of v_0 ... v_n)
            |
        +-------+
        |       |
        |   P2  |    Projection transformation (of the vertices)
        |       |
        +-------+
            |
            | image plane coordinates (of v_0 ... v_n)
            |
           / \
          /   \
         /     \
        |   P3  |   Clipping (of each primitive)
         \     /
          \   /
           \ /
            |
            | image plane coordinates (of the clipped vertices)
            |
        +-------+
        |       |
        |   P4  |    Viewport transformation (of the clipped vertices)
        |       |
        +-------+
            |
            | pixel-plane coordinates (of the clipped vertices)
            |
           / \
          /   \
         /     \
        |   P5  |   Rasterization & anti-aliasing (of each clipped primitive)
         \     /
          \   /
           \ /
            |
            |  shaded pixels (for each clipped, anti-aliased primitive)
            |
           \|/
    FrameBuffer.ViewPort
```


3.3 Clipping a `LineSegment`
===========================

This renderer uses a clipping algorithm that is a simplification of the
Liang-Barsky Parametric Line Clipping algorithm.

* <https://en.wikipedia.org/wiki/Liang%E2%80%93Barsky_algorithm>

This algorithm assumes that all `Vertex` objects have been projected onto
the camera's image-plane, z = -1. This algorithm also assumes that the
camera's view rectangle in the image-plane is
```text
   -1 <= x <= +1  and
   -1 <= y <= +1.
```

If a projected vertex from a line segment has an `x` or `y` coordinate
with absolute value greater than 1, then that vertex "sticks out" of the
view rectangle. This algorithm will clip the line segment so that both
of the line segment's vertices are within the view rectangle.

Here is an outline of the clipping algorithm for line segments.

Recursively process each `LineSegment` object, using the following steps.

1) Test if the line segment no longer needs to be clipped, i.e., both of
its vertices are within the view rectangle. If this is the case, then
return the `LineSegment` object wrapped in an `Optional` object.

```text
          x = -1     x = +1
            |          |
            |          |
        ----+----------+----- y = +1
            |     v1   |
            |    /     |
            |   /      |
            |  /       |
            | v0       |
        ----+----------+----- y = -1
            |          |
            |          |
```


2) Test if the line segment should be "trivially rejected". A line segment
is "trivially rejected" if it is on the wrong side of any of the four lines
that bound the view rectangle (i.e., the four lines x = 1, x = -1, y = 1,
and y = -1). If so, then return an empty `Optional` object indicating that
the line segment should not be rasterized into the viewport.

Notice that a line like the following one is trivially rejected because it
is on the "wrong" side of the line x = 1.

```text
          x = -1     x = +1
            |          |              v1
            |          |             /
        ----+----------+----        /
            |          |           /
            |          |          /
            |          |         /
            |          |        /
            |          |       /
        ----+----------+----  /
            |          |     /
            |          |   v0
```

But the following line is NOT trivially rejected because, even though it
is completely outside of the view rectangle, this line is not entirely on
the wrong side of any one of the four lines x = 1, x = -1, y = 1, or
y = -1. The line below will get (recursively) clipped at least one time
(either on the line x = 1 or the line y = -1) before it is (recursively)
a candidate for "trivial rejection". Notice that the line below could even
be clipped twice, first on y = 1, then on x = 1, before it can be trivially
rejected by being on the wrong side of y = -1.

```text
          x = -1     x = +1
            |          |            v1
            |          |           /
 y = +1 ----+----------+----------/---
            |          |         /
            |          |        /
            |          |       /
            |          |      /
            |          |     /
 y = -1 ----+----------+----/--
            |          |   /
            |          |  /
                       | /
                       |/
                       /
                      /|
                     / |
                   v0  |
```

3) If the line segment has been neither accepted nor rejected, then it needs
to be clipped. So we test the line segment against each of the four clipping
lines, x = 1, x = -1, y = 1, and y = -1 (in that order), to determine which
line the line segment crosses (it must cross at least one of them, why?). We
clip the line segment against the first line which we find that it crosses.
Then we recursively clip the resulting clipped line segment. Notice that we
only clip against the first clipping line which the segment is found to cross.
We do not continue to test against the other clipping lines. This is because
it may be the case, after just one clip, that the line segment is now a
candidate for trivial accept or reject. So rather than test the line segment
against several more clipping lines (which may be useless tests) it is more
efficient to recursively clip the line segment, which will then start with
the trivial accept or reject tests.



3.4 Computing the Clipped `Vertex`
==================================

When we clip a line segment against a clipping line, it is always the case
that one endpoint of the line segment is on the "right" side of the clipping
line and the other endpoint is on the "wrong" side of the clipping line. In
the following picture, assume that `v0` is on the "wrong" side of the clipping
line (x = 1) and `v1` is on the "right" side. So `v0` needs to be clipped off
the line segment and replaced by a new vertex.

```text
                        x=1
                         |
         (x1, y1) = v1   |
                      \  |
                       \ |
                        \|
                         \
                         |\
                         | \
                         |  \
                         |   v0 = (x0, y0)
```

Represent points `p(t)` on the line segment between `v0` and `v1` with the
following parametric equation.
```text
       p(t) = (1-t) * v0 + t * v1  with  0 <= t <= 1
```
Notice that this equation parameterizes the line segment starting with `v0`
at t=0 (on the "wrong side") and ending with `v1` at t=1 (on the "right side").
We need to find the value of `t` when the line segment crosses the clipping
line x = 1. Let `v0 = (x0, y0)` and let `v1 = (x1, y1)`. The above parametric
equation can be written in its component form,
```text
       p(t) = ( x(t), y(t) ) = ( (1-t)*x0+t*x1, (1-t)*y0+t*y1 )
```
which give us these two component equations,
```text
       x(t) = (1-t) * x0 + t * x1,
       y(t) = (1-t) * y0 + t * y1,  with  0 <= t <= 1.
```
Since the clipping line in this example is x = 1, we need to solve the
equation 1 = x(t) for `t`. So we need to solve
```text
          1 = (1-t) * x0 + t * x1
```
for `t`. Here are a few algebra steps.
```text
          1 = x0 - t * x0 + t * x1
          1 = x0 + t * (x1 - x0)
     1 - x0 = t * (x1 - x0)
          t = (1 - x0)/(x1 - x0)
```
We get similar equations for `t` if we clip against the other clipping
lines (x = -1, y = 1, or y = -1) and we assume that `v0` is on the
"wrong side" and `v1` is on the "right side".

Let `t0` denote the above value for `t`. With this value for `t`, we can
compute the y-coordinate of the new vertex `p(t0)` that replaces `v0`.

```text
                        x=1
                   v1    |
                     \   |
                      \  |
                       \ |
                         p(t0)=(1, y(t0))
                         |
                         |
                         |
```

Here is the algebra.
```text
        y(t0) = (1-t0) * y0 + t0 * y1
              = y0 + t0 * (y1 - y0)
              = y0 + (1 - x0)*((y1 - y0)/(x1 - x0))
```
Finally, the new line segment between `v1` and the new vertex `p(t0)`
is recursively clipped so that it can be checked to see if it should
be trivially accepted, trivially rejected, or clipped again.



3.5 Creating the Clipped `Vertex`
=================================

We still have one last detail to consider. We need to consider the memory
management of Java objects. When we clip a line segment,

```text
                        x=1
                    v1   |
                      \  |
                       \ |
                        \|
                         \
                         |\
                         | \
                         |  \
                         |   v0
```

we compute a new `Vertex` object, `p(t0)`. In our code, should we mutate the
`Vertex` object referred to by `v0` so that its coordinates are updated to
the values computed in `p(t0)`?
```java
    v0.x = p(t0).x;
    v0.y = p(t0).y;
```
Or should we replace the `Vertex` object referred to by `v0` with a new
`Vertex` object?
```java
    v0 = new Vertex( p(t0) );
```
If we create a new `Vertex` object to represent `p(t0)`, should that `Vertex`
object replace `v0` in the model's vertex list,

```java
    model.vertexList.set(ls.index[0], v0);
```
or should the new `Vertex` object be added to the end of the vertex list and
then mutate the `LineSegment` object to refer to the new `Vertex` object?

```java
    int i = model.vertexList.size();
    model.vertexList.add(v0); // added at the end of the list
    ls.index[0] = i;
```

First of all, we cannot mutate the vertex `v0`. Here is why. That vertex may
be part of another line segment. In the following picture, `v0` is an endpoint
of two line segments (this means that each line segment object holds the
index into the model's vertex list for the shared vertex, `v0`).

```text
                        x=1
                    v1   |
                      \  |
                       \ |
                        \|
                         \
                         |\
                         | \
                         |  \
                         |   \
                    v2--------v0
                         |
                         |
```

If, while clipping the line segment from `v0` to `v1`, we mutate vertex `v0`
to be the new vertex `p(t0)`, then the picture will become the following,
which incorrectly clips the line segment from `v2` to `v0`.

```text
                        x=1
                    v1   |
                      \  |
                       \ |
                        \|
                         v0
                        /|
                       / |
                      /  |
                    v2   |
                         |
                         |
```

So we cannot mutate a vertex when it needs to clipped off of a line segment.

When we create a new vertex to represent the clipping point `p(t0)`, by the
same reasoning as above, we cannot use that new vertex to replace the
original vertex in the model's vertex list. That would, once again, cause
the line segment from `v2` to `v0` to be incorrectly clipped. So we need to
add a new vertex to the model's vertex list and mutate the line segment
object to refer to that new vertex (called `v3` in the following picture).

```text
                        x=1
                    v1   |
                      \  |
                       \ |
                        \|
                         v3
                         |
                         |
                         |
                    v2--------v0
                         |
                         |
```

Notice that when the line segment from `v2` to `v0` finally gets clipped,
the algorithm will put a new vertex, call it `v4`, in the model's vertex list
and leave vertex `v0` in the list. No matter how many line segments `v0` is
shared with, it will be clipped off of each one, but it will continue to
remain in the model's vertex list.

```text
                        x=1
                    v1   |
                      \  |
                       \ |
                        \|
                         v3
                         |
                         |
                         |
                    v2---v4   v0
                         |
                         |
```



3.6 Color Interpolation While Clipping
======================================

Suppose we have a line segment that extends out of the camera's view
rectangle. Here we have a line segment with vertex `v1`, with color `c1`,
on the "right" side of the clipping line x = 1 and vertex `v0`, with
color `c0`, on the "wrong" side of the clipping line.

```text
                        x=1
                         |
                  v1,c1  |
                     \   |
                      \  |
                       \ |
                        \|
                         \
                         |\
                         | \
                         |  \
                         |   \
                         |  v0,c0
```

Vertex `v0` needs to be clipped off and replaced with a new vertex at the
line x=1. We also need to give the new vertex a new color. Since color
along the line segment will be linearly interpolated by the rasterizer,
the clipping stage should give to the new vertex the same color that the
rasterizer would interpolate to the line segment's pixel at x=1.

```text
                        x=1
                         |
                  v1,c1  |
                     \   |
                      \  |
                       \ |
                        \|
                         \ v2 = (1-t0) * v0 + t0 * v1,
                         | c2 = (1-t0) * c0 + t0 * c1
                         |
                         |
                         |
                         |
```

Once the clipping algorithm has solved for the value `t0` when the x-coordinate
of `p(t) = 1`, then the clipping algorithm can use the following three lerp
equations to calculate the new color, `c(t0)`, for the new vertex `p(t0)`.

```text
   r(t0) = (1-t0) * r0 + t0 * r1
   g(t0) = (1-t0) * g0 + t0 * g1
   b(t0) = (1-t0) * b0 + t0 * b1
```



3.7 Extreme Clipping Example
============================

We mentioned, while describing the clipping algorithm, that we clip a
line segment against the first view rectangle edge which we find that
it crosses and then immediately recurse on the resulting clipped
line segment. This is because it may be the case, after clipping the
line segment, that it becomes a candidate for trivial accept or reject.
An obvious question is how many times might we recurse on a line segment
before it is finally accepted or rejected?

Here is a picture of a line segment, from vertex `v0` to vertex `v1`, that
needs to be clipped four times before we get the final clipped line segment
from vertex `v4` to vertex `v5`. Remember that the clipping algorithm clips
first on the edge x = 1, then on x = -1, then on y = 1, and lastly on y = -1.

```text
                              v0
                              +
                          |  /
                          | /
                          |/
                          + v2
      x = -1             /|
        |               / |
        |              /  |
     ---+-------------+---+----- y = 1
        |            /v4  |
        |           /     |
        |          /      |
        |         /       |
        |        /        |
        |       /         |
        |      /          |
        |     /           |
        |    /            |
     ---+---+-------------+----- y = -1
        |  /v5            |
        | /               |
        |/                |
        + v3            x = 1
       /|
      / |
     +
    v1
```

When the clipping algorithm is finished, it will have added four new
vertices to the vertex list of the model. The clipped line segment in
the model will only use two of the six vertices in the vertex list
that were created for this line segment.

The clipping algorithm does not try to remove vertices like `v0`, `v1`,
`v2` and `v3` which are no longer being used by this line segment. The
vertices `v0` and `v1` cannot be removed because they might still be used
by other line segments in the model. And it is not worth the effort to try
and keep track of vertices like `v2` and `v3` which are created by the
clipping algorithm but end up not being used in the final clipped line
segment.

If you look carefully at the logging output from the renderer while it is
clipping several lines, you can see how the renderer accumulates extra,
un-needed vertices in a Model's vertex list. These extra vertices don't
cause any harm. They just take up some memory space.


Exercise: Suppose that the order of the edges used by the clipping
algorithm is,
```text
    x =  1,
    y = -1,
    x = -1,
    y =  1.
```
(a) How many times would the line in the above example be clipped?
(b) Using this second order for the edges in the clipping algorithm,
find an example of a line that will be clipped four times.


Exercise: The following small program has a bug in it. If you put it in
a file, compile it, and run it, you will see that the rendeerer even
gives you a runtime warning that there is something wrong.

The second line segment refers to a color that does not exist (color index 2).
But the program runs fine, without throwing IndexOutOfBoundsException. Why?

```java
import renderer.scene.*;
import renderer.scene.primitives.*;
import renderer.framebuffer.*;
import renderer.pipeline.*;
import java.awt.Color;
public class Exercise_R3 {
   public static void main(String[] args) {
      final Scene scene = new Scene("Exercise_R3");
      final Model model = new Model("exercise");
      scene.addPosition(new Position(model));
      model.addVertex(new Vertex(0,  0, -1),
                      new Vertex(2,  1, -1),
                      new Vertex(2, -1, -1));
      model.addColor(Color.red, Color.blue);
      model.addPrimitive(new LineSegment(0, 1, 0, 1),
                         new LineSegment(0, 2, 0, 2));
      final FrameBuffer fb = new FrameBuffer(300, 300, Color.white);
      scene.debug = true;
      Clip.debug = true;
      Pipeline.render(scene, fb);
      fb.dumpFB2File("Exercise_R3.ppm");
   }
}
```



3.8 Clipping a `Point`
=====================

There are two stages to clipping a `Point` primitive. If the point's vertex
is outside of the image rectangle, then the point primitive should be rejected
(clipped off). If the point's vertex is inside of the image rectangle, then
the point is accepted, but it still may need to be clipped. Remember that the
`Point` primitive has a "radius" that determines the size of the rasterized
point. A `Point` primitive whose `Vertex` is inside of the image rectangle,
but near one of the edges, may have its radius extend outside of the
`Viewport`. In that case, we need to clip off the rasterized pixels from the
`Point` that extend outside of the `Viewport`.

Remember that in the previous renderers we did clipping in the rasterization
stage but in this renderer we are doing clipping before the rasterization
stage. If the `Vertex` of a `Point` is not inside the image rectangle, then
we clip that `Vertex` before the rasterization stage, in the `Clip_Point.java`
class. If the `Vertex` of a `Point` is inside the image rectangle, then that
`Point` is accepted by the clipping stage and it is not clipped by
`Clip_Point.java`. But what if that `Point` has a radius that makes some of
its raterized pixels extend outside of the `Viewport`? We do not find out
about this until we reach the rasterization stage. So it must be the
rasterizer that clips those pixels from the `Point` that extend outside the
`Viewport`. So the clipping of `Point` primitives is done partially by the
clipping pipeline stage, in the file `Clip_Point.java`, and partially by the
rasterization pipeline stage, in the file `Rasterize_Clip_Point.java`.

This fact that some clipping needs to be done in the rasterizer, even though
we have a distinct clipping stage, is common in modern renderers. An example
of this is something called "guard-band clipping".

* <https://en.wikipedia.org/wiki/Guard-band_clipping>



3.9 The Java Optional class
===========================

This line of code can cause a runtime error because the `indexOf()`
method might return -1, which is not a valid character index.
```java
    str2.charAt( str1.indexOf(c) );  // Bad code, potential error.
```
Here is a modern way to write this line of code using Java's
`Optional` class, which was added to Java 8.

```java
    Optional result = str1.indexOf(c);  // Better code.
    if ( result.isPresent() )           // You SHOULD test for the possible error.
    {
       str2.charAt( result.get() );
    }
    else
    {
       // handle error
    }
```

You can "bypass" the `Optional`,

```java
    Optional result = str1.indexOf(c);
    str.charAt( result.get() );  // May throw NoSuchElementException.
```

but then you are no better off than with the original Java version.

Java's `Optional` is not tied directly enough into the language (into the
type system and the compiler). You are not required to process the `Optional`
in an "exhaustive" manner (using, for example, a pattern match) so you can
ignore the error case. But using `Optional` is better than using error flags
like `-1` or `null`.


* <https://docs.oracle.com/en/java/javase/21/docs//api/java.base/java/util/Optional.html>
* <https://www.baeldung.com/java-optional>


C, and C like languages, are to programming what epicycles are to celestial
mechanics. An early attempt at a system that works, but without a logical
foundation and not able to support further progress.
