Previous | Next --- Slide 49 of 78
Back to Lecture Thumbnails
HelloWorld

What do you do if the line goes exactly through one of the vertices of the diamonds? Then two adjacent diamonds would be affected, making the line thicker there.

zyx

I guess we could consider adding a tie-breaking rule to it? If we're allowed to control the intensity of a pixel, perhaps we could even use dimmer pixels for when the line doesn't intersect the square by a lot?

tcl1

Could you potentially attenuate the intensity of the pixel based on the length of the line inside the diamond/pixel?

keenan

@HelloWorld Terrific question. As you might expect, there's a very detailed specification for how to handle all the different edge cases---here's a writeup from Microsoft:

Direct3D line rasterization rules

It's important to have this kind of spec, so that different hardware implementations (e.g., graphics cards from Intel and graphics cards from NVIDIA) produce the same image on different machines. Sadly, however, not everything in modern hardware is a pixel-exact spec, i.e., there may still be very special corner cases that different vendors handle differently. Likewise, when you write your first assignment (A1 - DrawSVG) you may have to make some choices about exactly how to handle different scenarios, which might be slightly different from your classmates. The hope is that everyone figures out some kind of reasonable behavior for these corner cases. :-)

keenan

@zyx Exactly---you have to come up with some rules for breaking ties (such as the Microsoft spec above).

keenan

@zyx Yeah, making pixels brighter/darker depending on how much of the pixel is covered is a totally reasonable strategy for drawing lines, and starts to fall under the heading of something called antialiasing, which we'll talk a lot about in class. For lines in particular, there's a technique called Wu's line algorithm which I think might be extra credit for A1. ;-)

Wu antialiasing

keenan

@tcl Right, this is again a good way to start thinking about drawing "high quality" lines. Another way you could think about this is to imagine that you're not really drawing a line per se, but rather a long, very narrow rectangle. Then you can ask the question, "what fraction of each pixel is covered by the rectangle?" The answer to this question gives you a very principled way of deciding how bright each pixel should be. However, actually computing this coverage information can be expensive to do exactly. We'll take a look at how to compute approximate (but still high-quality) coverage in our lectures on rasterization.

Leslie

It's mentioned that the diamond algorithm works better than the previous square algorithm. I am wondering whether one of the reasons is the diamond covers the smaller area than the square, which means it may have smaller pixel and higher resolution.

By the way, is there any algorithm that calculates the intensity of the pixel based on the distance from the center of squares to the line? I do not think it's going to be expensive since the slope of the line is fixed. Thanks!

keenan

@Leslie Yeah, that might be a good strategy to render antialiased/filtered lines on modern GPUs: compute the distance to the centerline, and compute the intensity as some function of this distance. The reason this makes a lot of sense is that the GPU is effectively computing a closely related value (the barycentric coordinates) for each pixel anyway. As for the genesis of the diamond rule, I'm not really sure: it may simply have been that it corresponds to the classic Bresenham algorithm, but can be easily evaluated in parallel.

BellaJ

In this diamond rule: In some cases, the line touches the edge of a diamond in a square and is lit up while in another case, it is not lit up even though the line touches the edge of diamond in the square. Such is the case with Row 3 Column 6 pixel and Row 3 Column 4 pixel. Is this due to the fact that the computer has a more accurate measure than can be seen with the eye or is it taken on random?

abiagioli

@BellaJ The red line shown here is a bit inaccurate, as it is representing an infinitely-thin line. So, we are coloring pixels in which the thin line intersects each diamond. Here's some more info about the diamond rule as it relates to OpenGL:

https://wiki.allegro.cc/index.php?title=NewAPI/Primitives/al_draw_line/Diamond_Exit_Rule

Edit: This pic is even better, from the above link: Line Raster Rules

mdsavage

Does the Diamond Rule extend well to subpixel antialiasing? A cursory Google search didn't turn up anything pertinent. (Is that even something reasonable to do with lines? I know it's often done with fonts for readability.)

I'd imagine that this topic is at least in part what slide 46 was alluding to.