Live data from Hacker News

How to draw ugly lines fast

cohost.org

11–20 of 47 posts

Re: How to draw ugly lines fast

#11
post #9

It would help if he defined what "subpixel accurate" means. I can't figure out why you'd care about subpixels if you're producing a bitmap image? Or is he doing something like cleartype but not antialiased?

The endpoints of the lines have subpixel resolution, so although you’re only drawing whole pixels, the choice of which pixels to draw along the line may change based on the subpixel positions of the endpoints.

Re: How to draw ugly lines fast

#12
post #9

It would help if he defined what "subpixel accurate" means. I can't figure out why you'd care about subpixels if you're producing a bitmap image? Or is he doing something like cleartype but not antialiased?

He's not doing anything like ClearType, but for smooth animation you'd still want your end points to have more than single-pixel accuracy.

Re: How to draw ugly lines fast

#13
post #9

It would help if he defined what "subpixel accurate" means. I can't figure out why you'd care about subpixels if you're producing a bitmap image? Or is he doing something like cleartype but not antialiased?

It becomes important with low resolution framebuffers and once things start to move. Triangle outlines in early 3D games tended to wobble and jitter because the 'math' didn't work at subpixel precision (many PS1 3d games suffered from this).

With subpixel precision (e.g. you do all the math at a higher precision than the framebuffer resolution, and preserve the fractional part of pixel coordinates in all computations until you actually write to the framebuffer), the outlines remain stable even for small movements. IIRC Quake (with the software renderer) was one of the first games which paid proper attention to subpixel accuracy, and they showed this off with a very slight camera movement at the result screen after a multiplayer match. Triangle edges were properly 'crawling' instead of being all jittery.

Re: How to draw ugly lines fast

#14

Is it possible to do a SIMD version? I know compute shaders exist, but I have found that with huge datasets and a wide variety of end-user hardware, it tends to end up with many lines of code and brittleness. So I’m curious about high performance CPU-only implementations.

You'd probably want to process multiple lines at once and use scatter to do the pixel drawing, I guess? But if you have one long line and a bunch of short ones, the perf would tank due to the lanes all dying, like gpu shader divergence.

Re: How to draw ugly lines fast

#15
post #9

It would help if he defined what "subpixel accurate" means. I can't figure out why you'd care about subpixels if you're producing a bitmap image? Or is he doing something like cleartype but not antialiased?

I was confused about this too. What he means is fractionally accurate endpoints of the lines. So it's just about line endings coordinates not being exact integers.

Re: How to draw ugly lines fast

#18
post #16

What's wrong with drawing (possibly resulting in thicker line) pixels everywhere the mathematical line intersects the pixel?

Performance. The point of line drawing algorithms like Bresenham is to not need to do anything like costly floating-point intersection tests for every pixel. Also aesthetics: a single-pixel width line with occasional doubled pixels just looks uglier than one without them. That said, the algorithm for finding every cell in a grid lattice that intersects a line is occasionally useful for purposes other than line drawing.

Re: How to draw ugly lines fast

#19
post #9

It would help if he defined what "subpixel accurate" means. I can't figure out why you'd care about subpixels if you're producing a bitmap image? Or is he doing something like cleartype but not antialiased?

It becomes important with low resolution framebuffers and once things start to move. Triangle outlines in early 3D games tended to wobble and jitter because the 'math' didn't work at subpixel precision (many PS1 3d games suffered from this). With subpixel precision (e.g. you do all the math at a higher precision than the framebuffer resolution, and preserve the fractional part of pixel coordinates in all computations…

Also the death screen in single-player, and I remember being impressed by the effect.

Re: How to draw ugly lines fast

#20

This was wonderful to read. Informative, well explained, and humorous (the reference to "a pixel is not a little square" took me by surprise and made me laugh). I feel like I've gotten a better understanding of things I thought I knew already. The only question left in my mind is "why does he always need to write new subpixel-accurate line drawers?!"

Under his picure, you get the explanation.

    Tom Forsyth
    GPU designer and gfx coder

    Gfx coder and chip designer. Worked at Oculus, Valve, RAD, Muckyfoot, 3Dlabs, now back at Intel. Blade2, Larrabee, TF2, VR and many other atrocities.
Post reply on HN