Class Clip_Line


  • public class Clip_Line
    extends Object
    Clip a (projected) LineSegment that sticks out of the view rectangle in the image plane. Interpolate Vertex color from any clipped off Vertex to the new Vertex.

    This clipping algorithm is a simplification of the Liang-Barsky Parametric Line Clipping 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

    
          -1 <= x <= +1  and
          -1 <= y <= +1.
       

    If a line segment's projected vertex 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.

    Recursively process each line segment, 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 true.

    
                   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, y = -1). If so, then return false (so the line segment will not be rasterized into the framebuffer).

    Notice that a line like the following one is trivially rejected because it is on the "wrong" side of the line 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 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).
    
                               x=1
                                |          v1
                                |         /
                     +----------+        /
                     |          |       /
                     |          |      /
                     |          |     /
                     |          |    /
                     |          |   /
                     +----------+  /
                                | /
                                |/
                                /
                               /|
                              / |
                            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, to determine if the line segment crosses one of those lines. 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.

    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.

    
                                 x=1
                             v1   |
                               \  |
                                \ |
                                 \|
                                  \
                                  |\
                                  | \
                                  |  \
                                  |   v0
            
    Represent points p(t) on the line segment between v0 and v1 with the following parametric equation.
    
                      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). Then the above parametric equation becomes the two component equations
    
                     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 x(t) = 1 for t. So we need to solve
    
                      1 = (1-t) * x0 + t * x1
            
    for t. Here are a few algebra steps.
    
                      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.

    
                                 x=1
                            v1    |
                              \   |
                               \  |
                                \ |
                                  p(t0)=(1, y(t0))
                                  |
                                  |
                                  |
             
    Here is the algebra.
    
                      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.
    • Method Detail

      • clip

        public static Optional<Primitiveclip​(Model model,
                                               LineSegment ls)
        If the LineSegment sticks out of the view rectangle, then return a clipped version that is contained in the view rectangle. The new, clipped LineSegment object is returned wrapped in an Optional object.

        At least one new clipped Vertex will be added to the Model's vertex list (and as many as four new vertices may be added to the Model's vertex list).

        If the LineSegment is completely outside of the view rectangle, then return an empty Optional object to indicate that the LineSegment should be discarded.

        Parameters:
        model - Model that the LineSegment ls comes from
        ls - LineSegment to be clipped
        Returns:
        a clipped version of ls wrapped in an Optional object