• An Observation About Analytic Geometry:
  • We almost always use a continuous coordinate system
• An Observation About Visual Output Devices:
  • Most have a discrete display space (i.e., are raster devices) consisting of a grid of pixels
• The Implication:
  • To display shapes we will need to rasterize them
• My First Exposure to These Issues:
  • Writing a cartography program that worked with both a pen plotter and a printer

Two Approaches

• The Idea:
  • We have various methods for determining if a point is on a line segment
  • Scan pixel by pixel and check
• Reducing the Search Space:
  • Use the bounding rectangle
  • 

• One Problem:
  • In general, the integer points are not on the line so rounding is required
• Another Problem:
  • A large number of pixels have to be tested for many line segements

• The Idea:
  • Use \(\Delta x\) and \(\Delta y\) to determine step sizes and move from one end-point to the other
• An Example:
  • 

• Problem Situations:
  • When the absolute value of the slope is large or small
• The Problem:
  • Gaps
• The Problem with the Obvious Fix:
  • Overfilling

• "Overfilling" - Horizontal then Vertical:
  • 
• "Overfilling" - Vertical then Horizontal:
  • 

• Rounding:
  • Suppose \(\Delta x = 4\) and \(\Delta y = 5\)
  • Moving in steps of 1 in each direction doesn't get to the other endpoint
• Filling in at the Endpoint:
  • 

Conclusion - It seems like a good idea but it's hard to get everything to work out properly

• Recall:
  • \(\mathcal{L}(\lambda) = \bs{p} + \lambda (\bs{q} - \bs{p})\)
• Motivation:
  • We could draw the line by incrementing \(\lambda\) from 0 to 1
  • The step size matters

• A Simplifying Assumption:
  • The slope is in [-1, 1]
• Benefit of this Assumption:
  • For any \(x\) (including integer values) we can determine \(\lambda\) as follows:
  • \(\lambda = \frac{x - p_{1}}{q_{1} - p_{1}}\)

Assuming the Slope is in [-1, 1]

  double   y;  
  int      xEnd, xStart;

  if (p_1 <= q_1) {
     xStart = round(p_1); 
     xEnd   = round(q_1); 
  } else {
     xStart = round(q_1); 
     xEnd   = round(p_1); 
  }
    
  for (int x=xStart; x<=xEnd; x++) {
     if (q_1 == p_1) { // Prevent a divide by zero
        y = p_2;
     } else {
        lambda = (x - p_1)/(q_1 - p_1);
        y = p_2 + lambda * (q_2 - p_2);  
     }
    
     // Set the color of pixel (x,round(y))
  }
  

• The Other Case:
  • The slope is not in [-1, 1]
• Handling this Case:
  • Loop from \(p_{2}\) to \(q_{2}\) in steps of 1 and calculate the corresponding \(x\)

• Improving the Performance:
  • Use an incremental approach (i.e., at each iteration, update \(y\) using the previous value and an increment)
• The Original Case Revisited:

  •   double   deltay, y;  
      int      xEnd, xStart;
    
      if (p_1 <= q_1) {
         xStart = round(p_1); 
         xEnd   = round(q_1); 
         y      = p_2;  
    
         if (q_1 == p_1)
            deltay = 0;
         else
            deltay = (q_2 - p_2)/(q_1 - p_1);
      } else {
         xStart = round(q_1); 
         xEnd   = round(p_1); 
         y      = q_2;  
    
         if (p_1 == q_1)
            deltay = 0;
         else
            deltay = (p_2 - q_2)/(p_1 - q_1);
      }
      
      
      for (int x=xStart; x<=xEnd; x++) {
         // Set the color of pixel (x,round(y))
      
         y += deltay;     
      }
    	

• An Observation about the Incremental Version:
  • The increment is the slope (or the inverse of the slope in the other case)
• Some History:
  • This is often called the DDA Algorithm

• Bresenham's Algorithm:
  • Eliminates the floating point addition for each iteration
• The Midpoint Algorithm
  • Uses the implicit form of a line to generate the same pixels as Bresenham's Algorithm (but is a little easier to understand)
• Wu's Algorithm:
  • Selects two pixels at each iteration
• Double-Ended Wu's Algorithm (Rokne and Wyvill):
  • Works from both end-points simultaneously (i.e., at each iteration)

• The Problem:
  • The "jaggies"
• The Conceptual (Though Impossible) Solution:
  • Partially fill pixels
• The Solution:
  • "Blended" colors

• Barycentric Combination of Three Points:
  • Given three points \(\bs{r}\), \(\bs{s}\) and \(\bs{t}\) and three scalars \(\rho\), \(\sigma\), and \(\tau\) with \(\rho + \sigma + \tau = 1\), \(\rho \bs{r} + \sigma \bs{s} + \tau \bs{t}\) is said to be a barycentric combination of the three points
• Visualization:
  • 
• A Consequence:
  • A point \(\bs{p}\) is inside of a triangle formed by three points \(\bs{s}\), \(\bs{t}\) and \(\bs{r}\) if and only if the barycentric coordinates, \(\rho\), \(\sigma\), and \(\tau\) are in \([0,1]\) (i.e., if it is a convex combination of the points)

• A Difficulty:
  • It is not immediately obvious how to find the barycentric coordintes
• An Observation (that we won't prove):
  • The scalars \(\rho\), \(\sigma\), and \(\tau\) are proportional to the signed areas of the triangles formed by the point of interest and the vertices
• A Consequence:
  • We can use the signs of the areas of the triangles to determine if a point is in a triangle

Points Inside the Triangle

• The Vertices of the Original Triangle (in One Appropriate Order):
  • \(\bs{r}, \bs{s}, \bs{t}\) (Counterclockwise)
• The Vertices of the Formed Triangles:
  • \(\bs{r}, \bs{s}, \bs{p}\) (Counterclockwise)
  • \(\bs{s}, \bs{t}, \bs{p}\) (Counterclockwise)
  • \(\bs{t}, \bs{r}, \bs{p}\) (Counterclockwise)

Points Outside the Triangle

• The Vertices of the Original Triangle (in One Appropriate Order):
  • \(\bs{r}, \bs{s}, \bs{t}\) (Counterclockwise)
• The Vertices of the Formed Triangles:
  • \(\bs{r}, \bs{s}, \bs{p}\) (Clockwise)
  • \(\bs{s}, \bs{t}, \bs{p}\) (Counterclockwise)
  • \(\bs{t}, \bs{r}, \bs{p}\) (Counterclockwise)

• Using the Areas:
  • The point is inside if all of the areas have the same sign as the original triangle
• Calculating the Areas:
  • We know that we can use (one half of) the determinant of a 2x2 matrix to get the signed area
• Be Careful:
  • When we discussed determinants of 2x2 matrices one of the vertices was the origin (and we used the other two vertices)
  • In general, you need to move each triangle to the origin by subtracting one vertex from the others (and using the others). For example, the original triangle can be moved as follows:
  • 

• Number of Areas to Calculate:
  • At most four - the three triangles formed by the new point and the original triangle (if it is not stored)
• Operations per Area Calculation:
  • Two vector differences and a 2x2 determinant
  • This requires 4 scalar differences, 2 scalar multiplications, and a scalar difference

Reduce the Search Space Using the Bounding Rectangle

Only test points in the bounding rectangle.

Testing Fewer Points

Don't test points that must be inside.

• An Observation:
  • You don't need to search for the left-most and right-most interior points for each horizontal line, you can find the intersection of the horizontal line with the edges
  • You can then fill all of the points between the intersections
• Finding the Intersections:
  • Recall from the discussion of finding the intersection of lines in parametric form that:
  • \(\phi = \frac{(\bs{g} - \bs{a}) \cdot (\bs{h} - \bs{g})^{\perp}} {(\bs{c} - \bs{a}) \cdot (\bs{h} - \bs{g})^{\perp}}\)
  • \(\sigma = \frac{(\bs{a} - \bs{g}) \cdot (\bs{c} - \bs{a})^{\perp}} {(\bs{h} - \bs{g}) \cdot (\bs{c} - \bs{a})^{\perp}}\)
  • where \(\bs{g}\) and \(\bs{h}\) denote the endpoints of the scan line and \(\bs{a}\) and \(\bs{c}\) denote the endpoints of one edge of the triangle
• Be Careful:
  • You must find the interesection with all three edges, make sure it really is an intersection with the segment (i.e., check \(\phi\) and \(\sigma\)), and identify the left-most and right-most intersections to identify the "from" and "to" points

\(p\) and \(t\) are in the Same Halfspace formed by \(r\) and \(s\)

• A General Algorithm:
  • Perform the halfspace test for each pair of vertices and see if all of the signs are the same
• Efficiency:
  • Each halfspace test requires one dot product for the test point (and one dot product for the other vertex, if it is not stored)
  • If the implicit form of the edge is not stored, a vector difference and \(\perp\) is required to convert

• Preliminary Calculations for Each Edge:
  • Convert to implicit form and store \(\bs{n}\) and \(b\)
  • Calculate and store the sign from the halfspace test for the "next" vertex (which is known to be inside) and the edge in normal form
• For Each Point:
  • For each edge...
    • Calculate the sign from the halfspace test for the point and the stored implicit form of the edge
    • If the sign differs from the stored sign for this edge the point is not inside

• Bounding Rectangles:
  • As with triangles, there is no need to test points outside of the bounding rectangle
• Searching for Intersections:
  • As with triangles, it is possible to search from the left and right (and not test in between)
• Triangles as a Special Case:
  • Since triangles are convex polygons, the halfspace test can be used with them as well (and it is an interesting exercise to compare the efficiency of the two)

• The Algorithm:
  • As with triangles, the intersection of the scan line and the edges can be found in closed form
• Be Careful:
  • Finding the meaningful edges for each scan line is a little more complicated than with triangles