Is there any faster algorithm for drawing a triangle since in this method all the points in and next to the triangle are checked for whether they lie in these three lines? I think, probably, take the points along the edges of the triangle and fill the point inside the lines drawn by the previous step is a faster way, since it takes less calculation for those points inside the triangle.
elenagong
Can anyone probably explain more about incremental update? From the equation, when would we know that we have finished checking one line and need to go to the upper line? Thx!
chenj
Just wondering: with GPU, are we potentially "lightening up" the pixel and doing the checking in parallel for all the pixels available?
motoole2
All triangle traversal procedures should produce the same result (turn on the same set of pixels), but there are all sorts of different triangle traversal methods used for rasterization (including those cited at the bottom of the slide). And a GPU may provide yet more new ways to complete this task efficiently, by parallelizing this procedure (as briefly discussed in the following slide).
Task 3 of Assignment 1 will provide you an opportunity to explore and implement your own triangle traversal procedure, where the goal is to implement a procedure that is far faster than the naive approach of testing all samples on the screen as to whether or not they lie inside the triangle.
The traversal algorithm here follows a backtrack strategy: traverse potential samples in the triangle from left to right, and down to up. Perhaps one could potentially use a incremental line rasterization algorithm (a.k.a. Bresenham's line algorithm) as a basis for determining how to update each line of this triangle. (I'm being intentionally vague here, as this is a good exercise to go through for your assignment. :-) )
How is "outside" versus "inside" of an edge defined? I feel like these terms depend on which edge of the triangle is being evaluated but the calculation only involves one edge.
motoole2
@yyn19951228 You're right; nice catch!
@Phlip9 The function E_i(x,y) is a line equation. And more specifically, it is related to the cross product of two 3D vectors: one vector defined by (X_{i+1}-X_{i},Y_{i+1}-Y_{i},0), and the other defined by (x-X_{i},y-Y_{i},0). When the point (x,y) is on the line, the cross product is zero since both vectors are pointing in the same direction. When the point (x,y) is on either side of the line, the cross product produces a vector that either points in the positive or negative direction on the z-axis.
The sign of E_i(x,y) (or the result of this cross product) tells us what side the point falls. However, the "inside" and "outside" regions depend on how you orient the line's vertices. If you swap the order of the vertices, the "inside" and "outside" regions flip. I comment on this in more detail here. The slides assume vertices are arranged in a counter-clockwise order.
Is there any faster algorithm for drawing a triangle since in this method all the points in and next to the triangle are checked for whether they lie in these three lines? I think, probably, take the points along the edges of the triangle and fill the point inside the lines drawn by the previous step is a faster way, since it takes less calculation for those points inside the triangle.
Can anyone probably explain more about incremental update? From the equation, when would we know that we have finished checking one line and need to go to the upper line? Thx!
Just wondering: with GPU, are we potentially "lightening up" the pixel and doing the checking in parallel for all the pixels available?
All triangle traversal procedures should produce the same result (turn on the same set of pixels), but there are all sorts of different triangle traversal methods used for rasterization (including those cited at the bottom of the slide). And a GPU may provide yet more new ways to complete this task efficiently, by parallelizing this procedure (as briefly discussed in the following slide).
Task 3 of Assignment 1 will provide you an opportunity to explore and implement your own triangle traversal procedure, where the goal is to implement a procedure that is far faster than the naive approach of testing all samples on the screen as to whether or not they lie inside the triangle.
The traversal algorithm here follows a backtrack strategy: traverse potential samples in the triangle from left to right, and down to up. Perhaps one could potentially use a incremental line rasterization algorithm (a.k.a. Bresenham's line algorithm) as a basis for determining how to update each line of this triangle. (I'm being intentionally vague here, as this is a good exercise to go through for your assignment. :-) )
Is the
dE_i(x, y + 1) = E_i(x, y) + dX_i = E_i(x, y) + B_i
be
dE_i(x, y + 1) = E_i(x, y) - dX_i = E_i(x, y) + B_i ?
since the B_i = -dX_i
How is "outside" versus "inside" of an edge defined? I feel like these terms depend on which edge of the triangle is being evaluated but the calculation only involves one edge.
@yyn19951228 You're right; nice catch!
@Phlip9 The function
E_i(x,y)is a line equation. And more specifically, it is related to the cross product of two 3D vectors: one vector defined by(X_{i+1}-X_{i},Y_{i+1}-Y_{i},0), and the other defined by(x-X_{i},y-Y_{i},0). When the point(x,y)is on the line, the cross product is zero since both vectors are pointing in the same direction. When the point(x,y)is on either side of the line, the cross product produces a vector that either points in the positive or negative direction on the z-axis.The sign of
E_i(x,y)(or the result of this cross product) tells us what side the point falls. However, the "inside" and "outside" regions depend on how you orient the line's vertices. If you swap the order of the vertices, the "inside" and "outside" regions flip. I comment on this in more detail here. The slides assume vertices are arranged in a counter-clockwise order.