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}}
No comments:
Post a Comment