This technique of line rasterization is O(n) which is obviously better than the naive O(n^2), but it also has the drawback that it's very sequential. Are there any methods that can break the line up into sections (especially for high resolution outputs)?
shhhh
Can't you just tweak the algorithm to work in parallel?
Something along the lines of:
for ( i = 0; i < u2-u1; i++ )
{
draw ( u1+i, round(v1+(i*s)) )
}
keenan
Are there any methods that can break the line up into sections (especially for high resolution outputs)?
Can't you just tweak the algorithm to work in parallel? Something along the lines of: for ( i = 0; i < u2-u1; i++ ) { draw ( u1+i, round(v1+(i*s)) ) }
Yes, in fact a modern way to render lines (strange as it may seem at first) is to render a quadrilateral, which itself is actually drawn by the graphics hardware as a pair of triangles---imagine splitting the quad along its diagonal. From there, the triangles are efficiently rendered in parallel via an algorithm like the ones we'll look at when we talk about rasterization.
Of course that leaves the question: why do all the work of rendering a line as two triangles, when it seems much simpler to have a specialized algorithm for lines? The answer is: because if you can decompose all of your draw operations into one atomic operation (in this case, drawing triangles), then you can make the hardware much simpler. And from there, you can really make things fly (e.g., by duplicating the units that draw triangles many times, and optimizing the heck out of them). If you need specialized algorithms for each type of primitive, you have to share space on the chip with lots of different algorithms, many of which may not be used much (lines are far less common than triangles in modern applications).
The other answer for why you might use triangles to draw lines is something called "mitering", which is an important part of high-quality illustration. Miters only complicate specialized line-drawing algorithms, but are fairly easy to do with quads/triangles. Here's a terrific page with some fun JavaScript illustrating mitering. Something like this could make a nice final project, if you get interested in 2D illustration.
This technique of line rasterization is O(n) which is obviously better than the naive O(n^2), but it also has the drawback that it's very sequential. Are there any methods that can break the line up into sections (especially for high resolution outputs)?
Can't you just tweak the algorithm to work in parallel? Something along the lines of: for ( i = 0; i < u2-u1; i++ ) { draw ( u1+i, round(v1+(i*s)) ) }
Yes, in fact a modern way to render lines (strange as it may seem at first) is to render a quadrilateral, which itself is actually drawn by the graphics hardware as a pair of triangles---imagine splitting the quad along its diagonal. From there, the triangles are efficiently rendered in parallel via an algorithm like the ones we'll look at when we talk about rasterization.
Of course that leaves the question: why do all the work of rendering a line as two triangles, when it seems much simpler to have a specialized algorithm for lines? The answer is: because if you can decompose all of your draw operations into one atomic operation (in this case, drawing triangles), then you can make the hardware much simpler. And from there, you can really make things fly (e.g., by duplicating the units that draw triangles many times, and optimizing the heck out of them). If you need specialized algorithms for each type of primitive, you have to share space on the chip with lots of different algorithms, many of which may not be used much (lines are far less common than triangles in modern applications).
The other answer for why you might use triangles to draw lines is something called "mitering", which is an important part of high-quality illustration. Miters only complicate specialized line-drawing algorithms, but are fairly easy to do with quads/triangles. Here's a terrific page with some fun JavaScript illustrating mitering. Something like this could make a nice final project, if you get interested in 2D illustration.