Line-drawing routine

[NoCforMe]

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 y₁ < y₀ 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:

Code Select Expand

;====================================
; 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).

[daydreamer]

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

[NoCforMe]

Well, to my chagrin I realize my routine will never be a speed contender. I had forgotten about this:

Code Select Expand

; 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.

[daydreamer]

test program works nice 
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

[NoCforMe]

dont 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.

[sinsi]

SetPixelV 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".

[sudoku]

SetPixelV 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.

[NoCforMe]

Yeah, I was wondering that too.
Anyhoo, I looked at the docs for SetPixelIV(). One thing bothers me when they say

The 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.)

[sudoku]

What 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?

[NoCforMe]

Yes, that's what I was getting at when I mentioned VGA, which used a limited palette of colors.

[sinsi]

(SetPixel() has no such caveat.)

It does say something similar, though

If 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.

Why 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.

[daydreamer]

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?
 

[NoCforMe]

instead of IDIV ,replace with faster rcpss /mulss combo

Or just use Bresenham's like everyone else does. Simple and effective.

[daydreamer]

instead 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

[daydreamer]

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 ?