Line-drawing routine

[sinsi]

With 320x200 resolution and 256 colours any antialiasing would be a waste of time 

[FORTRANS]

Hi,

Anyone already have antialiased line code ?

   I have used Michael Abrash's Wu antialiased line drawing
code.  I posted some results inhttps://masm32.com/board/index.php?topic=5469.msg58613#msg58613.

Steve

[NoCforMe]

Steve, saw the images; interesting. Did you post code for that? or if not, can you? I'm curious to see how that antialising works.

[FORTRANS]

Hi,

Steve, saw the images; interesting.

Thanks.

Did you post code for that?

Nobody replied to that post, so I assume not.

or if not, can you? I'm curious to see how that antialising works

Okay.  The code was copied from a PDF using OCR and editing.
References should be mentioned both in the code and that other
ZIP.  Some errors may exist and I altered some comments.  You
should read the original text by Abrash.  If a moderator is
worried that it's not original code by me: croak it.

  I am also assuming you are not concerned about the gamma
correction mentioned in the prior post.

Cheers,
Steve N.

[NoCforMe]

Did you post code for that?

Nobody replied to that post, so I assume not.

or if not, can you? I'm curious to see how that antialising works

Okay.  The code was copied from a PDF using OCR and editing.
References should be mentioned both in the code and that other
ZIP.  Some errors may exist and I altered some comments.  You
should read the original text by Abrash.

I did find this explanation of antialiasing online. It uses the midline algorithm instead of Bresenham's, but other than that will work.
Unfortunately, it's written by a mathematician, not a programmer, and is therefore full of a certain amount of hand-waving, which isn't helpful. Plus the nomenclature (not all of it explained) makes my head hurt.
Basically you find the distance (an error term) between the actual line being drawn (pixels) and the theoretical line if you weren't drawing pixels, then shade the pixels according to the distance from the virtual line. That much I understand.
I wish there were some common-sense, nuts-and-bolts explanation of antialiasing. Maybe in that book you mentioned (but I looked that up: do you realize that copies of that book are selling starting at $182 and go up to $980? It's ridiculous. Check it out on bookfinder.com, the best resource for locating stuff printed on dead trees.)

[tda0626]

Thought about trying my hand at the pseudo code here of Wu's algorithm, see link below. It looks doable and doesn't include any fancy math speak.

Wu's AA Line


Tim

[NoCforMe]

Not a fan of Wikipedia (in fact, I pretty much hate it), but I'll admit I've gotten working pseudocode from them before.
That example seems to use floating-point math, so probably not usable.

[FORTRANS]

Hi,

   I got a PDF of the book from the internet way back when.
It is a scanned version of the book and has a rough look to
it.  And I just looked for it and did not find it.  Drat.
I did find a set of text programs in GRAPHPRO.LZH.  I will
try to find my copy of the book and see if I can get a better
name to search for it.

  Google gets a lot of hits for the PDF.  I have not looked
at those though.  Oh well.

Regards,

Steve N.

[FORTRANS]

Hi,

   This link has the same sort of files that I downloaded a
long while back.  It is not where I got them.  And the file
dates are wrong.

https://medusa.teodesian.net/docs/computing/gpbb/

Regards,

Steve

[NoCforMe]

I found the two relevant chapters in that repository:
Bresenham is Fast, and Fast is Good
Wu'ed in Haste; Fried, Stewed at Leisure
@Steve: Just want to let you know that these are exactly the kind of explanations I was looking for. Clear, cogent, well-written, explaining the concept first (with pictures!), then implementation details with both C and assembly-language examples. Excellent stuff!

[Professor]

An anti-aliased line routine should be easy enough to describe in plain English.

Assume a "blank" screen contains all zeros (0,0,0) and thus is totally black.

Assume we're drawing a white line (255,255,255) starting at upper-left and sloping at a shallow angle to the lower-right. For example, from (10,0) to (49,7), giving a total "Run" of +39 and "Rise" of -7.

Begin by setting the top-left pixel to a "Shade" of solid white. At each horizontal step, calculate the new Shade. Simplistically, we can use: Shade = Shade plus Rise/Run*255. Using the example, the "change" at each step is -7/39*255. If the new Shade is still above zero, set the pixel in the current row. When the Shade falls below zero, add 255, skip to the next row down, then set that pixel.

By the time you've moved 39 columns across you'll have moved 7 rows down. However, you'll only have completed the "top" half of the anti-aliased line (the parts shaded from white to black). To finish the job, we need one tiny additional step: At each pixel, set the pixel immediately below to (255 minus Shade). This forms the "bottom" half of the anti-aliased line (the parts shaded from black to white).

For "steep" lines, you'll use a "change" value of Run/Rise*255, move down (or up) at each step, then move right (or left) when the Shade falls below zero.

I don't want to delve too deeply into optimization. Obviously, pre-computing the "change" at the start of the algorithm would help. Better still would be to use integer math rather than floating point numbers. Obviously horizontal and vertical lines require much simpler algorithms without anti-aliasing.

I also didn't want to delve into drawing over the top of existing lines, which would require using a computed "Transparency" rather than a computed "Shade". I'm only really focusing on the anti-aliasing aspects.

Finally, in the OPs code, I note the "early exit" when all entry values are 0. This falls down when one attempts to plot a line from (0,0) to (0,0) – which should at the very least plot a single pixel!

[Professor]

Just for fun, here's a spreadsheet that visually demonstrates the anti-aliasing described above. It uses values from 0-15 rather than 0-255 to show more dramatic differences from one "pixel" to the next.

[Biterider]

Hi Professor
That's fine for a 1 pixel wide line, but what about, say, a 10 pixel wide line?

Biterider

[NoCforMe]

Just for fun, here's a spreadsheet that visually demonstrates the anti-aliasing described above. It uses values from 0-15 rather than 0-255 to show more dramatic differences from one "pixel" to the next.

Request: could you maybe post that in .xls format for those of us who don't have a recent enough copy of Excel to open .xlsx files?
Nevermind; remembered I have Open Office and got it to open there.

[Professor]

That's fine for a 1 pixel wide line, but what about, say, a 10 pixel wide line?

Good point, Biterider. I've never really experimented with drawing thick lines. I guess my point was just demonstrating simple anti-aliasing. A wider line would presumably compute two lines, with the "fade-in" anti-aliasing only performed on the "top" line and the "fade-out" anti-aliasing only performed on the "bottom" line.