001package pipeline;
002import scene.*;
003
004/**
005   Clip any (projected) line segment that sticks out of the view rectangle
006   in the view plane. Interpolate vertex color from the clipped off vertex
007   to the new vertex.
008
009   This clipping algorithm is a simplification of the Liang-Barsky Parametric
010   Line Clipping algorithm.
011
012   This algorithm assumes that all LineSegment objects have been projected onto
013   the camera's view plane, z = -1. This algorithm also assumes that the camera's
014   view rectangle in the view plane is
015      -1 <= x <= +1  and
016      -1 <= y <= +1.
017
018   If a line segment's projected vertex has an x or y coordinate with absolute
019   value greater than 1, then that vertex "sticks out" of the view rectangle.
020   This algorithm will clip the line segment so that both of the line segment's
021   vertices are within the view rectangle with -1 <= x <= +1 and -1 <= y <= +1.
022
023
024   Here is an outline of the clipping algorithm.
025
026   Recursively process each line segment, using the following steps.
027
028     1) Test if the line segment no longer needs to be clipped, i.e., both of
029        its vertices are within the clipping rectangle. If this is the case,
030        then return true.
031
032     2) Test if the line segment should be "trivially rejected". A line segment
033        is "trivially rejected" if it is on the wrong side of any of the four
034        lines that bound the view rectangle (i.e., the four lines x = 1, x = -1,
035        y = 1, y = -1). If so, then return false (so the line segment will not
036        be rasterized into the framebuffer).
037
038        Notice that a line like the following one is trivially rejected because it
039        is on the "wrong" side of the line x=1.
040
041                           x=1
042                            |                      v1
043                            |                    /
044                 +----------+                  /
045                 |          |                /
046                 |          |              /
047                 |          |            /
048                 |          |          /
049                 |          |        /
050                 +----------+      /
051                            |    /
052                            |  v0
053
054        But the following line is NOT trivially rejected because, even though it
055        is completely outside of the view rectangle, this line is not entirely on
056        the wrong side of any one of the four lines x = 1, x = -1, y = 1, or y = -1.
057        The line below will get clipped at least one time (either on the line x = 1
058        or the line y = -1) before it is (recursively) a candidate for "trivial rejection".
059        Notice that the line below could even be clipped twice, first on y = 1, then
060        on x = 1, before it can be trivially rejected (by being on the wrong side
061        of y = -1).
062                           x=1
063                            |                      v1
064                            |                    /
065                 +----------+                  /
066                 |          |                /
067                 |          |              /
068                 |          |            /
069                 |          |          /
070                 |          |        /
071                 +----------+      /
072                            |    /
073                            |  /
074                             /
075                           /
076                        v0  |
077                            |
078
079     3) If the line segment has been neither accepted nor rejected, then it needs
080        to be clipped. So we test the line segment against each of the four clipping
081        lines, x = 1, x = -1, y = 1, and y = -1, to determine if the line segment
082        crosses one of those lines. We clip the line segment against the first line
083        which we find that it crosses. Then we recursively clip the resulting clipped
084        line segment. (Notice that we only clip against the first clipping line which
085        the segment is found to cross. We do not continue to test against the other
086        clipping lines. This is because it may be the case, after just one clip, that
087        the line segment is now a candidate for trivial accept or reject. So rather
088        than test the line segment against several more clipping lines (which may be
089        useless tests) it is more efficient to recursively clip the line segment,
090        which will then start with the trivial accept or reject tests.)
091
092        When we clip a line segment against a clipping line, it is always the case that
093        one endpoint of the line segment is on the "right" side of the clipping line and
094        the other endpoint of the line segment is on the "wrong" side of the clipping
095        line. In the following picture, assume that v0 is on the "wrong" side of the
096        clipping line (x = 1) and v1 is on the "right" side. So v0 needs to be clipped
097        off the line segment and replaced by a new endpoint.
098
099                             x=1
100                              |
101                        v1    |
102                          \   |
103                            \ |
104                              \
105                              | \
106                              |   \
107                              |     v0
108
109        Represent points p(t) on the line segment between v0 and v1 with the
110        following parametric equation.
111                  p(t) = (1-t) * v0 + t * v1  with  0 <= t <= 1
112        Notice that this equation parameterizes the line segment starting with v0
113        at t=0 (on the "wrong side") and ending with v1 at t=1 (on the "right side").
114        We need to find the value of t when the line segment crosses the clipping
115        line x = 1. Let v0=(x0, y0) and let v1=(x1, y1). Then the above parametric
116        equation becomes the two component equations
117                 x(t) = (1-t) * x0 + t * x1,
118                 y(t) = (1-t) * y0 + t * y1,  with  0 <= t <= 1.
119        Since the clipping line in this example is x = 1, we need to solve the
120        equation x(t) = 1 for t. So we need to solve
121                  (1-t) * x0 + t * x1 = 1
122        for t. Here are a few algebra steps.
123                  x0 - t * x0 + t * x1 = 1
124                  x0 + t * (x1 - x0) = 1
125                       t * (x1 - x0) = 1 - x0
126                       t = (1 - x0)/(x1 - x0)
127        We get similar equations for t if we clip against the other clipping lines
128        (x = -1, y = 1, or y = -1) and we assume that v0 is on the "wrong side" and
129        v1 is on the "right side". With the above value for t, the new point p(t)
130        that replaces v0 can easily be computed.
131
132                             x=1
133                              |
134                        v1    |
135                          \   |
136                            \ |
137                              v0=p( (1 - x0)/(x1 - x0) )
138                              |
139                              |
140                              |
141
142         Finally, the new line segment between v1 and the new v0 is recursively
143         clipped so that it can be checked once again to see if it can be trivially
144         accepted, trivially rejected, or clipped again.
145*/
146public class Clip
147{
148   /**
149      If the line segment sticks out of the view rectangle, then
150      clip it so that it is contained in the view rectangle.
151
152      @param ls LineSegment to be clipped
153      @return a boolean that indicates if this line segment is within the view rectangle
154   */
155   public static boolean clip(LineSegment ls)
156   {
157      // make local copies of several values
158      Vertex v0 = ls.v[0],  v1 = ls.v[1];
159      double x0 = v0.x,     x1 = v1.x;
160      double y0 = v0.y,     y1 = v1.y;
161
162      // 1. Check for trivial accept.
163      if ( ! ( Math.abs( x0 ) > 1
164            || Math.abs( y0 ) > 1
165            || Math.abs( x1 ) > 1
166            || Math.abs( y1 ) > 1 ) )
167      {
168         //System.err.println("Trivial accept.");
169         return true;
170      }
171      // 2. Check for trivial delete.
172      else if ( (x0 >  1 && x1 >  1)   // to the right of the line x = 1
173             || (x0 < -1 && x1 < -1)   // to the left of the line x = -1
174             || (y0 >  1 && y1 >  1)   // above the line y = 1
175             || (y0 < -1 && y1 < -1) ) // below the line y = -1
176      {
177         //System.err.println("Trivial delete.");
178         return false;
179      }
180      // 3. Need to clip this line segment.
181      if (x0 > 1 || x1 > 1)  // ls crosses the line x = 1
182      {
183         if (x1 > 1)  // clip off v1
184         {
185            // create a new Vertex between v[0] and v[1]
186            Vertex v_new = interpolateNewVertex(v0, v1, 1);
187            // modify the LineSegment to contain v[0] and the new Vertex
188            ls.v[1] = v_new;
189         }
190         else // (x0 > 1)  // clip off v0
191         {
192            // create a new Vertex between v[1] and v[0]
193            Vertex v_new = interpolateNewVertex(v1, v0, 1);
194            // modify the LineSegment to contain v[1] and the new Vertex
195            ls.v[0] = v_new;
196         }
197      }
198      else if (x0 < -1 || x1 < -1)  // ls crosses the line x = -1
199      {
200         if (x1 < -1)  // clip off v1
201         {
202            // create a new Vertex between v0 and v1
203            Vertex v_new = interpolateNewVertex(v0, v1, 2);
204            // modify the LineSegment to contain v0 and the new Vertex
205            ls.v[1] = v_new;
206         }
207         else // (x0 < -1)  // clip off v0
208         {
209            // create a new Vertex between v1 and v0
210            Vertex v_new = interpolateNewVertex(v1, v0, 2);
211            // modify the LineSegment to contain v1 and the new Vertex
212            ls.v[0] = v_new;
213         }
214      }
215      else if (y0 > 1 || y1 > 1)  // ls crosses the line y = 1
216      {
217         if (y1 > 1)  // clip off v1
218         {
219            // create a new Vertex between v0 and v1
220            Vertex v_new = interpolateNewVertex(v0, v1, 3);
221            // modify the LineSegment to contain v0 and the new Vertex
222            ls.v[1] = v_new;
223         }
224         else // (y0 > 1)  // clip off v0
225         {
226            // create a new Vertex between v1 and v0
227            Vertex v_new = interpolateNewVertex(v1, v0, 3);
228            // modify the LineSegment to contain v1 and the new Vertex
229            ls.v[0] = v_new;
230         }
231      }
232      else if (y0 < -1 || y1 < -1)  // ls crosses the line y = -1
233      {
234         if (y1 < -1)  // clip off v1
235         {
236            // create a new Vertex between v0 and v1
237            Vertex v_new = interpolateNewVertex(v0, v1, 4);
238            // modify the LineSegment to contain v0 and the new Vertex
239            ls.v[1] = v_new;
240         }
241         else // (y0 < -1)  // clip off v0
242         {
243            // create a new Vertex between v1 and v0
244            Vertex v_new = interpolateNewVertex(v1, v0, 4);
245            // modify the LineSegment to contain v1 and the new Vertex
246            ls.v[0] = v_new;
247         }
248      }
249      else
250      {  // should never get here
251         System.err.println("Clipping error!");
252         System.exit(-1);
253      }
254      return clip(ls);  // recursively clip this line segment again
255   }
256
257
258   /**
259      This method takes in two vertices, one that is on the "right" side
260      of a clipping line and the other that is on the "wrong" side of the
261      clipping line, and an integer which specifies which clipping line
262      to use, where
263         eqn_number == 1  means the clipping line x = 1
264         eqn_number == 2  means the clipping line x =-1
265         eqn_number == 3  means the clipping line y = 1
266         eqn_number == 4  means the clipping line y =-1
267
268      This method returns the vertex that is the intersection point
269      between the given line segment and the given clipping line.
270
271      This method solves for the value of t for which the parametric
272      equation
273                  p(t) = (1-t) * v_outside + t * v_inside
274      intersects the given clipping line (notice that the equation
275      is parameterized so that we move from the outside vertex towards
276      the inside vertex as t increases from 0 to 1). The solved for
277      value of t is then plugged into the parametric formula to get
278      the coordinates of the intersection point.
279
280      @param v_inside    the Vertex that is inside the view rectangle
281      @param v_outside   the Vertex that is outside the view rectangle
282      @param eqn_number  the identifier of the view rectangle edge crossed by the line segment
283      @return a Vertex object that replaces the clipped off vertex
284   */
285   private static Vertex interpolateNewVertex(Vertex v_inside,
286                                              Vertex v_outside,
287                                              int eqn_number)
288   {
289      //System.err.println("Create new vertex.");
290      // make local copies of several values
291      double vix =  v_inside.x; // "i" for "inside"
292      double viy =  v_inside.y;
293      double vox = v_outside.x; // "o" for "outside"
294      double voy = v_outside.y;
295      // interpolate between v_outside and v_inside
296      double t = 0.0;
297      if (1 == eqn_number)            // clip to x = 1
298         t = (1 - vox) / (vix - vox);
299      else if (2 == eqn_number)       // clip to x = -1
300         t = (-1 - vox) / (vix - vox);
301      else if (3 == eqn_number)       // clip to y = 1
302         t = (1 - voy) / (viy - voy);
303      else if (4 == eqn_number)       // clip to y = -1
304         t = (-1 - voy) / (viy - voy);
305
306      Vertex v_new = new Vertex();
307
308      // use the value of t to interpolate the coordinates of the new vertex
309      v_new.x = (1-t) * vox + t * vix;
310      v_new.y = (1-t) * voy + t * viy;
311      // use the value of t to interpolate the color of the new vertex
312      v_new.r = (1-t) * v_outside.r + t * v_inside.r;
313      v_new.g = (1-t) * v_outside.g + t * v_inside.g;
314      v_new.b = (1-t) * v_outside.b + t * v_inside.b;
315
316      return v_new;
317   }
318
319}