- Forward


Rasterization of 2D Shapes
An Introduction with Examples in Java


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back Forward
  • 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
Discretization
Back Forward

Two Approaches

images/discretizations-2d.gif
Line Segments: Scanning
Back Forward
  • 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
    • images/linesegment2d-scanning.gif
Line Segments: Scanning (cont.)
Back Forward
  • 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
Line Segments: Discrete Differences
Back Forward
  • The Idea:
    • Use \(\Delta x\) and \(\Delta y\) to determine step sizes and move from one end-point to the other
  • An Example:
    • images/linesegment2d-differences1.gif
Line Segments: Discrete Differences (cont.)
Back Forward
  • Problem Situations:
    • When the absolute value of the slope is large or small
  • The Problem:
    • Gaps
  • The Problem with the Obvious Fix:
    • Overfilling
Line Segments: Discrete Differences (cont.)
Back Forward
  • "Overfilling" - Horizontal then Vertical:
    • images/linesegment2d-differences2.gif
  • "Overfilling" - Vertical then Horizontal:
    • images/linesegment2d-differences3.gif
Line Segments: Discrete Differences (cont.)
Back Forward
  • 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:
    • images/linesegment2d-differences4.gif
Line Segments: Discrete Differences (cont.)
Back Forward

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

Line Segments: Parametric Algorithm
Back Forward
  • 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
Line Segments: Parametric Algorithm (cont.)
Back Forward
  • 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}}\)
Line Segments: Parametric Algorithm (cont.)
Back Forward

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)) }
Line Segments: Parametric Algorithm (cont.)
Back Forward
  • 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\)
Line Segments: Parametric Algorithm (cont.)
Back Forward
  • 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; }
Line Segments: Parametric Algorithm (cont.)
Back Forward
  • 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
Line Segments: Other Algorithms
Back Forward
  • 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)
Line Segments: Antialiasing
Back Forward
  • The Problem:
    • The "jaggies"
  • The Conceptual (Though Impossible) Solution:
    • Partially fill pixels
  • The Solution:
    • "Blended" colors
Triangles: Getting Started
Back Forward
  • 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:
    • images/barycentriccombinations2d-3points.png
  • 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)
Triangles: Getting Started (cont.)
Back Forward
  • 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
Triangles: Getting Started (cont.)
Back Forward

Points Inside the Triangle

images/triangle2d-inside.gif
  • 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)
Triangles: Getting Started (cont.)
Back Forward

Points Outside the Triangle

images/triangle2d-outside.gif
  • 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)
Triangles: Pointwise Fill
Back Forward
  • 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:
    • images/triangle2d-translated.gif
Triangles: Pointwise Fill (cont.)
Back Forward
  • 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
Triangles: Pointwise Fill (cont.)
Back Forward

Reduce the Search Space Using the Bounding Rectangle

images/triangle2d-boundingrectangle.gif

Only test points in the bounding rectangle.

Triangles: Search-Based Scan Line Fill
Back Forward

Testing Fewer Points

images/triangle2d-improvedfill.gif

Don't test points that must be inside.

Triangles: Closed-Form Scan Line Fill
Back Forward
  • 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
Convex Polygons: Getting Started
Back Forward

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

images/polygon-inside.gif
Convex Polygons: Pointwise Fill
Back Forward
  • 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
Convex Polygons: Pointwise Fill (cont.)
Back Forward
  • 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
Convex Polygons: Pointwise Fills (cont.)
Back Forward
  • 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)
Convex Polygons: Scan Line Fills
Back Forward
  • 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
There's Always More to Learn
Back -