Rasterization
Definition: Discretization of a shape, line or polygon specified by continuum of vector coordinates into pixel coordinates used to render it.
Line Rasterization: Bresenham Line Algorithm
Assumption: The start and end point lie on integer pixel coordinate
Problem: Which pixels to render while drawing a line joining $(x_0,y_0)$ and $(x_1,y_1)$
Step 1:
Project the line into first octant such that $(x_0,y_0)$ is projected to origin and $(x_1,y_1)$ is mapped to $(x',y')$ such that
- $x' \geq 0$
- $y' \geq 0$
- $x' \geq y$
Step 2:
$P \rightarrow $ the start pixel
$M \rightarrow $ the first midpoint
$M_{E} \rightarrow $ the next midpoint given we choose to render E
$M_{NE} \rightarrow $ the next midpoint given we choose to render NE pixel
Define $f(x,y) = mx + b - y$ where $y = mx + b$ is the equation of the line projected in first octant.
$f(M) = f(P_x + 1, P_y + \frac{1}{2}) = f(P) + m - \frac{1}{2}$
$f(M_E) = f(M) + m$
$f(M_{NE}) = f(M) + m - 1$
Now, $m = \frac{\Delta y}{\Delta x} \geq 0$. So define
$F(M) = 2 \Delta x f(M)$
$F(M_E) = 2 \Delta x f(M_E) = F + 2 \Delta y $
$F(M_{NE}) = 2 \Delta x f(M_{NE}) = F + 2 \Delta y - 2 \Delta x$
$F(M_{init}) = 2 \Delta y - \Delta x$
Final Algorithm:
$y = y_0$
$F = 2 \Delta y - \Delta x$
for $x=x_0:x_1$
Render $(x,y)$
if$(F \leq 0 )$ \* Take the East *\
$F = F + 2 \Delta y$
else$(F > 0)$ \* Take the North East *\
$F = F + 2 \Delta y - 2 \Delta x$
end
Polygon Rasterization
First enforce consistent set of rules for when does a pixel belong to a polygon. The ambiguous case is when the edge passes through the pixel center. The other case is trivial.
The polygon will be rasterized one scanline at a time where the scanline progressively moves up.
Each edge is represented by coordinates $(x_{lower},y_{lower}),(x_{upper},y_{upper})$.
Maintain an Active Edge data structure with the following three fields
- $x$ coordinate where a scan line intersects the edge
- $\frac{dx}{dy}$
- $y_{upper}$
The entries (basically edges and their properties) in this data structure are sorted in order of $x$ first and $\frac{dx}{dy}$ next.
Algorithm:
- Add edges with $y = y_{lower}$ along with their attributes in the Active Edge data structure
- For every pair $(2i-1,2i)$ render pixels in the range $\lceil x_i \rceil$ to $\lceil x_{i+1} \rceil - 1 $
- Remove edges with $y_{upper} = y$
- Update $x$ by $x = x + \frac{dx}{dy}$
Gouraud Interpolation
While rasterizing polygons, we need to interpolate vertex attributes such as colors to get the colors at the rendered pixels.
To do this:
- Maintain the attribute value along the edges of the polygon in the Active Edge data structure
- Whenever we move the scan line up, update the attribute by $val = val + \frac{val_{upper}-val_{lower}}{y_{upper}-y{lower}}$
- When scanning from left to right the pixels are assigned attributes by $val = val + \frac{val_{right}-val_{left}}{x_{right} - x_{left}}$
Definition: Discretization of a shape, line or polygon specified by continuum of vector coordinates into pixel coordinates used to render it.
Line Rasterization: Bresenham Line Algorithm
Assumption: The start and end point lie on integer pixel coordinate
Problem: Which pixels to render while drawing a line joining $(x_0,y_0)$ and $(x_1,y_1)$
Step 1:
Project the line into first octant such that $(x_0,y_0)$ is projected to origin and $(x_1,y_1)$ is mapped to $(x',y')$ such that
- $x' \geq 0$
- $y' \geq 0$
- $x' \geq y$
Step 2:
$P \rightarrow $ the start pixel
$M \rightarrow $ the first midpoint
$M_{E} \rightarrow $ the next midpoint given we choose to render E
$M_{NE} \rightarrow $ the next midpoint given we choose to render NE pixel
Define $f(x,y) = mx + b - y$ where $y = mx + b$ is the equation of the line projected in first octant.
$f(M) = f(P_x + 1, P_y + \frac{1}{2}) = f(P) + m - \frac{1}{2}$
$f(M_E) = f(M) + m$
$f(M_{NE}) = f(M) + m - 1$
Now, $m = \frac{\Delta y}{\Delta x} \geq 0$. So define
$F(M) = 2 \Delta x f(M)$
$F(M_E) = 2 \Delta x f(M_E) = F + 2 \Delta y $
$F(M_{NE}) = 2 \Delta x f(M_{NE}) = F + 2 \Delta y - 2 \Delta x$
$F(M_{init}) = 2 \Delta y - \Delta x$
Final Algorithm:
$y = y_0$
$F = 2 \Delta y - \Delta x$
for $x=x_0:x_1$
Render $(x,y)$
if$(F \leq 0 )$ \* Take the East *\
$F = F + 2 \Delta y$
else$(F > 0)$ \* Take the North East *\
$F = F + 2 \Delta y - 2 \Delta x$
end
Polygon Rasterization
First enforce consistent set of rules for when does a pixel belong to a polygon. The ambiguous case is when the edge passes through the pixel center. The other case is trivial.
The polygon will be rasterized one scanline at a time where the scanline progressively moves up.
Each edge is represented by coordinates $(x_{lower},y_{lower}),(x_{upper},y_{upper})$.
Maintain an Active Edge data structure with the following three fields
- $x$ coordinate where a scan line intersects the edge
- $\frac{dx}{dy}$
- $y_{upper}$
The entries (basically edges and their properties) in this data structure are sorted in order of $x$ first and $\frac{dx}{dy}$ next.
Algorithm:
- Add edges with $y = y_{lower}$ along with their attributes in the Active Edge data structure
- For every pair $(2i-1,2i)$ render pixels in the range $\lceil x_i \rceil$ to $\lceil x_{i+1} \rceil - 1 $
- Remove edges with $y_{upper} = y$
- Update $x$ by $x = x + \frac{dx}{dy}$
Gouraud Interpolation
While rasterizing polygons, we need to interpolate vertex attributes such as colors to get the colors at the rendered pixels.
To do this:
- Maintain the attribute value along the edges of the polygon in the Active Edge data structure
- Whenever we move the scan line up, update the attribute by $val = val + \frac{val_{upper}-val_{lower}}{y_{upper}-y{lower}}$
- When scanning from left to right the pixels are assigned attributes by $val = val + \frac{val_{right}-val_{left}}{x_{right} - x_{left}}$
