Following a discussion of line drawing in the 16-bit forum here, I put together a little testbed to see how a routine I wrote quite some time ago (ca. 2006) to draw lines works. Attached is the executable.
It doesn't use Bresenham's or any other "classic" line-drawing algorithm. It's something I cooked up on my own, and it works fine with any line. I had to add a couple things to the original to get it to work universally:
- I handle lines where y1 < y0 by just swapping the two endpoints and drawing the line "backwards" (basically mirroring it)
- I handle horizontal and vertical lines specially (two easy cases)
Other than that, it can draw in any "quadrant" (or octant if you prefer) with no problems.
You can play with the program to see how it works. One thing worth mentioning: you might wonder what that "
Enable sparse fill-in" thing is. To see how it works, leave it unchecked and draw a line that's very steep. You'll notice that there are hardly any points plotted. Then, without changing the coordinates, check this item and redraw the line. That enables the part of the line-drawing routine that fills in "sparse" lines like that (an essential part of the routine if you want decent-looking lines).
Here's the line-drawing code:
;====================================
; DrawLine (hDC)
; Draws a line from (x0, y0) to (x1, y1)
;====================================
DrawLine PROC hDC:HDC
LOCAL xDist:DWORD, negFlag:DWORD, deltaY:DWORD, deltaYsign:DWORD, yAccum:DWORD
LOCAL x0:DWORD, y0:DWORD, x1:DWORD, y1:DWORD, currX:DWORD, currY:DWORD, lastY:DWORD
; Move global coords. to locals:
MOV EAX, X0
MOV x0, EAX
MOV EAX, X1
MOV x1, EAX
MOV EAX, Y0
MOV y0, EAX
MOV EAX, Y1
MOV y1, EAX
; Null case, everything = 0:
OR EAX, X0
OR EAX, X1
OR EAX, Y0
JZ exit99
; Figure out which case this is:
MOV EAX, X0
CMP EAX, X1
JE vline
JA swap
MOV x0, EAX
MOV EAX, Y0
CMP EAX, Y1
JE hline
MOV y0, EAX
MOV EAX, X1
MOV x1, EAX
MOV EAX, Y1
MOV y1, EAX
JMP SHORT @F
swap: MOV EAX, x0
XCHG x1, EAX
MOV x0, EAX
MOV EAX, y0
XCHG y1, EAX
MOV y0, EAX
; Get rise, run:
@@: MOV EAX, x1
SUB EAX, x0
MOV xDist, EAX
MOV EAX, y1
SUB EAX, y0
MOV ECX, EAX
; Determine if slope positive or negative:
; TEST AX, 8000h
JNC dl_pos
MOV EAX, -1 ;Slope negative.
MOV negFlag, 1
NEG ECX
JMP SHORT drw2
;***** Draw horizontal line: *****
; Normalize x-coords:
hline: MOV EAX, x1
CMP EAX, x0
JA @F
XCHG EAX, x1
MOV x0, EAX
@@: MOV ECX, x1
SUB ECX, x0
hloop: PUSH ECX
INVOKE SetPixel, hDC, x0, y0, LineColor
INC x0
POP ECX
LOOP hloop
JMP exit99
;***** Draw vertical line: *****
; Normalize y-coords:
vline: MOV EAX, y1
CMP EAX, y0
JA @F
XCHG EAX, y1
MOV y0, EAX
@@: MOV ECX, y1
SUB ECX, y0
vloop: PUSH ECX
INVOKE SetPixel, hDC, x0, y0, LineColor
INC y0
POP ECX
LOOP vloop
JMP exit99
dl_pos: MOV EAX, 1
MOV negFlag, 0
drw2: MOV deltaYsign, EAX
MOV EAX, ECX ;Get Ydistance back.
; Calculate slope (y1-y0/x1-x0):
MOV EDX, $slopeFactor
IMUL EDX
IDIV xDist
MOV deltaY, EAX ;This is amount (fractional) to add to Y each time.
; Draw line:
drw5: MOV yAccum, 0
MOV ECX, xDist
MOV EAX, x0
MOV currX, EAX
MOV EAX, y0
MOV currY, EAX
dl_loop:
PUSH ECX
INVOKE SetPixel, hDC, currX, currY, LineColor
MOV EAX, currY
MOV lastY, EAX
; Move 1 notch on x-axis, determine new y-position:
INC currX ;Next X increment.
MOV EAX, deltaY
ADD yAccum, EAX ;Add increment to accumulator.
MOV EAX, yAccum
XOR EDX, EDX
IDIV SlopeFactor
CMP negFlag, 1
JNE drw20
SUB currY, EAX
JMP SHORT drw22
drw20: ADD currY, EAX
; Adjust accumulator:
drw22: IMUL SlopeFactor
SUB yAccum, EAX ;Take out whole-number part.
; Fill in "sparse" lines if called for:
drw30: CMP SparseFillOn, TRUE
JNE drw40
MOV EAX, currY
SUB EAX, lastY
JNC @F
NEG EAX
@@: CMP EAX, 1
JBE drw40 ;If increment <= 1, no need to fill in.
MOV EAX, lastY
ADD EAX, deltaYsign ;Add or subtract 1, depending on slope sign.
MOV lastY, EAX
PUSH currY
MOV currY, EAX
DEC currX ;Fill in behind where we are now.
INVOKE SetPixel, hDC, currX, currY, LineColor
POP currY
INC currX
JMP drw30
drw40: POP ECX
DEC ECX
JNZ dl_loop
exit99: RET
DrawLine ENDP
Except for the device context all the variables are in globals--
(X0,Y0) and
(X1,Y1).
I have isometric x,y,z <> Cartesian x,y coordinates proc's which uses GDI moveto /lineto
Also other console program that line drawing onto bitmap in memory before writing it to 1 bit bitmap file
To make write pixels to allocated memory fast and simple, I only write byte size pixels
Well, to my chagrin I realize my routine will never be a speed contender. I had forgotten about this:
; Calculate slope (y1-y0/x1-x0):
MOV EDX, $slopeFactor
IMUL EDX
IDIV xDist
MOV deltaY, EAX ;This is amount (fractional) to add to Y each time.
Very un-Bresenham (which only uses adds and shifts).
Oh well.
test program works nice :thumbsup:
dont worry about speed when its not IDIV or IMUL thats slow,its setpixel taking milliseconds
but using it in mode 13in DOS 16bit write directly to screenmemory,ddraw api(I used it),SDL2 api(Hector used it) makes it possible to draw directly to screenmemory
now I got idea to change conversion proc between isometric ->cartesian to macros inside line algo,possible to use SIMD to do 2 conversion ,the line startpoint and endpoint
Quote from: daydreamer on May 24, 2024, 02:51:34 AMdont worry about speed when its not IDIV or IMUL thats slow,its setpixel taking milliseconds
Yes, true that.
Another way to draw would be to create a bitmap in memory, then use
BitBlt() or one of its cousins to zap the image into the DC. I would think that might be faster than using
SetPixel() for each pixel.
QuoteSetPixelV is faster than SetPixel because it does not need to return the color value of the point actually painted.
Of course it depends on what it means by "faster".
Quote from: sinsi on May 24, 2024, 07:09:35 AMQuoteSetPixelV is faster than SetPixel because it does not need to return the color value of the point actually painted.
Of course it depends on what it means by "faster".
Who are you quoting, or where is that quote from? I don't see SetPixelV anywhere in the thread.
Yeah, I was wondering that too.
Anyhoo, I looked at the docs for
SetPixelIV() (https://learn.microsoft.com/en-us/windows/win32/api/wingdi/nf-wingdi-setpixelv?redirectedfrom=MSDN). One thing bothers me when they say
QuoteThe SetPixelV function sets the pixel at the specified coordinates to the closest approximation of the specified color.
What the hell does that mean? Why wouldn't it be able to set the exact color? I suppose this would have been an issue on some ancient devices (hey, VGA, here's looking at you!), but modren displays? Pfffft.
(
SetPixel() has no such caveat.)
Quote from: NoCforMe on May 24, 2024, 08:19:55 AMWhat the hell does that mean? Why wouldn't it be able to set the exact color?
Probably in the era of 16 or 256 indexed colors?
Yes, that's what I was getting at when I mentioned VGA, which used a limited palette of colors.
Quote from: NoCforMe on May 24, 2024, 08:19:55 AM(SetPixel() has no such caveat.)
It does say something similar, though
Quote from: MSDN SetPixelIf the function succeeds, the return value is the RGB value that the function sets the pixel to. This value may differ from the color specified by crColor; that occurs when an exact match for the specified color cannot be found.
Quote from: NoCforMe on May 24, 2024, 08:19:55 AMWhy wouldn't it be able to set the exact color?
This function goes back (according to MSDN) to Windows 2000 (but we know it was around for Windows 95), and even now there are embedded systems that don't have a fancy 32-bit display mode.
instead of IDIV ,replace with faster rcpss /mulss combo,dont know if convert from real4 to integer is slow?
anybody dare to test their line code is "fastest in the galaxy" in laboratory?
if rules are everyone write to an allocated memorybuffer?
Quote from: daydreamer on May 25, 2024, 02:17:04 AMinstead of IDIV ,replace with faster rcpss /mulss combo
Or just use Bresenham's like everyone else does. Simple and effective.
Quote from: NoCforMe on May 25, 2024, 04:41:37 AMQuote from: daydreamer on May 25, 2024, 02:17:04 AMinstead of IDIV ,replace with faster rcpss /mulss combo
Or just use Bresenham's like everyone else does. Simple and effective.
No,directx is also capable of hardware accelerated linelist, pointlist besides trianglelist,trianglestrip
I Mostly use GDI moveto,lineto,like your sigline asm programming for fun,my kind of fun is SSE /SSE 2
Forgot I made linedrawing "- - - - " in middle of the road drawing a racetrack code
Antialiased line much easier in win32 than mode 13h you have to set palette to many different shades of red,for a red line
Anyone already have antialiased line code ? Plot one darker to left of line and one darker right of the line ?
With 320x200 resolution and 256 colours any antialiasing would be a waste of time :biggrin:
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 (https://masm32.com/board/index.php?topic=5469.msg58613#msg58613).
Steve
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.
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.
QuoteQuoteDid 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 (https://observablehq.com/@infowantstobeseen/antialiasing-lines-and-triangles-ii-wus-algorithm) 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 (https://www.bookfinder.com/search/?ac=sl&st=sl&ref=bf_s2_a1_t1_1&qi=fmtS3nE2erKoKMRrJbWsO5uEkPE_1717114236_1:9711:18304&bq=author%3Dmichael%2520abrash%26title%3Dmichael%2520abrash%2527s%2520graphics%2520programming%2520black%2520book%2520special), the best resource for locating stuff printed on dead trees.)
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 (https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm)
Tim
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.
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.
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/ (https://medusa.teodesian.net/docs/computing/gpbb/)
Regards,
Steve
I found the two relevant chapters in that repository:
Bresenham is Fast, and Fast is Good (https://medusa.teodesian.net/docs/computing/gpbb/gpbb35.pdf)
Wu'ed in Haste; Fried, Stewed at Leisure (https://medusa.teodesian.net/docs/computing/gpbb/gpbb42.pdf)
@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!
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!
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.
Hi Professor
That's fine for a 1 pixel wide line, but what about, say, a 10 pixel wide line?
Biterider
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.
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.
This thread was rather nostalgic for me! I took a look at some old line-drawing code that I wrote circa 1993-94 for an animation of my IBM PS/2 computer, which ran on the MCGA graphics card of that computer. That code didn't draw anti-aliased lines, but it was some pretty tight, optimized code in less than 100 lines of 8086 assembler.
You could post that code in our 16-bit forum if you like.
Quote from: Professor on August 02, 2024, 08:01:21 AMQuote 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.
But 10 pixel wide,isnt it definition of polygon instead ?
Quote from: daydreamer on August 02, 2024, 03:14:02 PMBut 10 pixel wide,isnt it definition of polygon instead ?
Theoretically, yes. Practically, no.