//****************************************************************************//
//************* Intro to Rasterization - January 30th, 2019 *****************//
//**************************************************************************//
- So, waaaaaaaaaaaaaay back before the non-snowday (the *shudder* before times), we were talking about how to write out equations of line, implicitly and parametrically
- Now, let's see some code for actually drawing a line:
void line(x0, y0, x1, y1):
dx = x1 - x0
dy = y1 - y0
// this is the maximum number of pixel "steps" we have to take to get to
// the end, not the actual line's length
length = max(float_abs(dx), float_abs(dy))
xinc = (float)dx / length
yinc = (float)dy / length
x = x0
y = y0
for (i = 0; i < length; i++):
//since we can't put a pixel in a fractional location, just round
// to the nearest pixel
gtWritePixel(round(x), round(y), someColor)
x += xinc
y += yinc
- So, if we run this code on (say) a 6x6 grid (the smallest monitor in the world), and we try to draw a line from (1,3) to (5,5):
- We end up with the following initial values:
- dx = 5 - 1 = 4
- dy = 5 - 3 = 2
- length = 4
- xinc = 4/4 = 1
- yinc = 2/4 = 0.5
- This leads to a sort of stair-stepping line
- "If we only have black and white pixels to deal with, this line will look pretty jaggedy, or ALIASED - fortunately, almost all displays these days let us have a variety of shades, which means we can soften this line to look smoother using ANTI-ALIASING techniques"
- We might not get to this in class, but it's in the textbook if you're interested
- So, what kind of line equation is this function using? It's parametric!
- ...but where's the "t" value here? Well, it's "i"! It's a bit hidden, but we're basically using our incremented i value in place of t
- There are more complicated line drawing algorithms if you want to use them, but we won't really bother with them in this class
- Now, here's some context for where we're going in this class:
- On the screen right now is a "shutterbug" image of 3 different orthographic views of a wireframe scene (lines only) - it looks pretty primitive, and is similar to what we're trying to do in class right now
- If we jump to perspective projection, it'll look a bit more jumbled (since it's only lines, and we can see through them!), but the perspective is clearly more lifelike now
- If we jump to the next image, we see that there are now "hidden surfaces" in the rendering - objects that are behind another object are no longer drawn!
- Then, the next image has surfaces on the objects - there's COLOR on the objects, but there's no shading, so the image looks pretty flat
- In the next image, there's some basic shading, and now it looks like the objects have depths!
- Still further on, there are multiple light sources in the scene, and then objects casting shadows and having reflections, and then objects having textures and images!
- "So, that's where we're headed in the not-too-distant future for this class - but for now, let's get back to the present and keep working towards this stuff!"
- So, let's talk about our next step: POLYGON RASTERIZATION!
- Let's start off with the humble rectangle: how do we fill in a rectangle with a solid color on our screen?
- Let's assume we already know where the corners of the rectangle are going to be drawn on our screen; (xmin, ymin) is the lower-left corner, (xmax, ymax) is 1 pixel BEFORE the top-right row/column
- Why stop 1 pixel early? Because if 2 objects were right next to each other, they would overlap and "fight" over who fills in the column/row of pixels where they're touching; if we do it this way, then who "owns" which row is now well-defined (it's just taken by the left/bottom row of the object to the right/top)
- This isn't a big problem now, but it becomes a much bigger issue when dealing with transparency, or techniques like "XOR drawing"
- For the time being, let's also assume our rectangle isn't rotated, and is lying flat against the screen
- So, with that knowledge, filling in the rectangle on our grid would look something like this:
for (y = ymin; y < ymax; y++):
for (x = xmin; x < xmax; x++):
gtWritePixel(x, y, color)
- So, doing this with rectangles isn't too difficult - but what about for general polygons?
- As I'm sure you remember, a POLYGON is just some region of space that's enclosed by a set of straight lines
- These can be CONVEX (i.e. any infinitely-long line can intersect the shape at at most 2 points) or CONCAVE (there's a "cave"/inset in the object where they can be hit multiple times)
- "Concave polygons tend to be the more ugl-...well, I shouldn't say ugly. They're, um, different."
- Some graphics libraries will let you draw polygons with "features," i.e. holes (like a triangle with a star-shaped hole in the middle) - these are tricky to deal with if you have to write the drawing functions from scratch
- This isn't really a focus of this course, but it's something to be aware of out there in the wild
- To rasterize ANY polygon, we're going to fill in one "scanline" (i.e. row of pixels) of the polygon at a time, from bottom to top, maxing sure to fill between INTERSECTIONS
- What intersections? We'll get there in a second, but it's basically where the lines of the polygon intersect the edges of our pixels in the grid
- As for bottom-to-top, it's just an arbitrary convention that's become pretty standard
- So, if we had some rotated triangle overlaid on our tiny monitor grid again:
- We find the points in the row where the lines are intersecting with the pixel grid
- Fill in all the pixels in the row that're in-between those points
- Move up to the next row
- In pseudocode:
for (y = ymin; y < ymax; y++):
find x intersections with polygon edges
sort intersections on x-values
fill between pairs of intersections (from left-to-right)
- ...of course, there're some unanswered questions here, including a pretty big one: how do we find these intersection points quickly?
- Fortunately, it's pretty easy once we have the first intersection point
- For now, suppose we know where the leftmost intersection point in the row is
- We know where the closest point of the POLYGON (not the intersection) to our left is, and the next point of the polygon to the right; knowing this, we can make a right triangle (3rd point is just (x1, y0)
- If we then scale that triangle so its height is 1 pixel, we'll have a similar triangle whose base's length is how much we need to step to the right for every scanrow (i.e. 1 pixel) we go up to stay on the polygon's edge!
- So, if we know where 1 point is, we can figure out where the edges of the polygon are really easily/quickly! Go efficiency!
- We'll keep talking about rasterization on Friday - 'til then, keep working on your projects, etc.