News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests
NB: Posting URL's See here: Posted URL Change

Main Menu

Line-drawing routine

Started by NoCforMe, May 22, 2024, 02:08:47 PM

Previous topic - Next topic

sinsi

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

FORTRANS

Hi,

Quote from: daydreamer on May 29, 2024, 04:07:34 PMAnyone 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.
Assembly language programming should be fun. That's why I do it.

FORTRANS

#18
Hi,

Quote from: NoCforMe on May 30, 2024, 09:42:36 AMSteve, saw the images; interesting.
Thanks.

QuoteDid you post code for that?
Nobody replied to that post, so I assume not.

Quoteor 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

Quote
QuoteDid you post code for that?
Nobody replied to that post, so I assume not.
Quoteor 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.)
Assembly language programming should be fun. That's why I do it.

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

#21
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.
Assembly language programming should be fun. That's why I do it.

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

#24
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!
Assembly language programming should be fun. That's why I do it.

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

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

Biterider

NoCforMe

Quote from: Professor on August 01, 2024, 07:01:56 PMJust 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.
Assembly language programming should be fun. That's why I do it.

Professor

Quote from: Biterider on August 01, 2024, 07:34:16 PMThat'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.