Line Drawing

[tda0626]

I got a basic line drawing routine but I want it to stop it from wrapping around like in the image below if the slope value starts increasing.

Code Select Expand

.model small


Stack SEGMENT STACK
DW 256 DUP(?)
Stack ENDS

.data

red db 028h
x DW ?
y  DW ?
slope DW ?

.code

_main proc

mov ax, @data
mov ds, ax

mov ax, 0A000h ;video memory
mov es, ax
xor di, di

mov ah, 0 ; 320 x 200
mov al, 013h
int 10h

mov x, 0 ; Starting Coordinates
mov y, 0
mov cx, 100 ; 100 pixel line
mov slope, 3 ; Slope of the line

DrawLine:

mov ax, y ; Calculate offset in video memory
mov bx, 320 ; Y * 320 + X
mul bx
add ax, x

mov di, ax ; Set DI to our offset value
mov al, red
mov es:[di], al ; Write a red pixel to memory


cmp cx, 0
je EndLine

mov ax, y ; Add the slope to the line
add ax, slope
mov y, ax
inc x

dec cx
jmp DrawLine

EndLine:

mov ah, 0 ; wait for key press
int 16h

mov ax, 04c00h ; exit
int 21h

_main endp
end _main


[zedd151]

Once you have clearly defined boundaries, you must tell the program what to do once a boundary is met.
Change direction, stop, start at a new x,y position, etc.
I don't know how to do it in 16 bit and as you have coded it, but it shouldn't be very difficult to implement.
You should be able to draw the lines as if it were a bouncing ping pong ball (staying within the boundaries), is that what you had in mind? (Where the lines appear to be bouncing off the 'walls'?).

After looking at the code again...

Code Select Expand

        dec cx
        jmp DrawLine
that jump should be jnz maybe, rather than jmp???
Then you wouldnt need the

Code Select Expand

cmp cx, 0
je EndLine further up in the code.

[NoCforMe]

Your "slope" isn't really the slope of the line (your actual slope is negative), but let's not worry about that for the moment: it's really the offset to the next y-position down for the next drawn pixel.

Your problem is not that the "slope" is increasing (it's not, it stays constant at 3) but that you're hitting the bottom line and wrapping around in the video buffer. So if you want to stop drawing at the bottom of the screen, then check to see if your y-position is at or past the bottom line, then exit your loop. (I'll leave it up to you to figure out how to determine that.)

Hint: at least two ways to do that:
1. Set your loop counter to a value that you know will only draw pixels to the bottom of the screen and stop.
2. Check the value of y each time through the loop to see if it's at the bottom of the screen.

[tda0626]

Hint: at least two ways to do that:
2. Check the value of y each time through the loop to see if it's at the bottom of the screen.

Thanks, I got it to work. I was overthinking it for some reason when it was simple. I also added checks for the other screen borders.

How would I implement a slope? I want to eventually input start and end coordinates.

[NoCforMe]

Remember high-school algebra?

Given 2 points, (x₁,y₁) & (x₂, y₂):

m = y2 - y1 / x2 - x1

m is the slope.

[tda0626]

Remember high-school algebra?

Given 2 points, (x₁,y₁) & (x₂, y₂):

m = y2 - y1 / x2 - x1

m is the slope.

I know that. Usually the Y values are going to be smaller than the x values so we end up with a fraction but thanks anyway. I will see if I can find something on the Internet that explains it better.

[NoCforMe]

You do end up with fractions. That's one of the problems you have to solve. (See below for one possible solution.)

I think you meant the delta-Y values are going to be smaller than the delta-X values, but that's only true if the slope is less than 1 (45°).

Fractions: since you aren't using floating-point (I'm assuming: you could, but that's another whole ball o'wax), here's a way to deal with fractions: scaling up and scaling down.

Let's say you have a line with a slope of 0.5 (0,0)--> (6,3).
Use a scaling factor of let's say 100. Using the slope formula above, multiply delta-Y (the change in Y) by 100, then divide by delta-X:

(3-0) * 100 / (6-0) = 50

So our "slope" (scaled) is 50.
To plot a point, use the formula above, use 50 as the slope, then divide the result by the scaling factor (100) to calculate the actual coordinates.

[NoCforMe]

Your question is a non-trivial one. I just revisited some of my old line-drawing code which I hadn't looked at in years.

I did use scaling like I explained above. Thing is, since you're dealing with fractional values here, you need to keep an accumulator going to draw a line. Otherwise, let's say the slope is 0.5, you're never going to get any change in Y if you just go pixel-by-pixel since the incremental delta-Y value is less than one, therefore zero in integer arithmetic.

The basic idea is you start at your starting point, let's call it (x₀, y₀). Since you want a solid line and not a dotted one like you drew, we'll set our delta-X at 1, meaning we'll always move 1 pixel to the right.

The problem then becomes one of determining what our Y-position is for each pixel (we know what our X-position is because it increases by 1 each step). That's a matter of using scaling as shown above and calculating each next Y-position.

I'll leave it as an exercise for you. I'd suggest getting out paper and pencil and drawing lines to figure it out. Works for me, anyhow.

Hopefully this makes sense to you.

[NoCforMe]

Here's my line-drawing routine. Not necessarily suggesting you copy and use it (you could if you wanted to), but it does work, so it might tell you something.

It even fills in "sparse" lines (lines with gaps between pixels) to make them look smoother.

The structure passed in in BX contains the starting and ending coordinates.

Code Select Expand

$slopeFactor EQU 100

DrawLine LABEL NEAR
; Draws a line from (x0, y0) to (x1, y1)
;
; On entry,
; ES:BX--> $LineStruct structure

; Get rise, run:
MOV AX, ES:[BX.$$gl_x1]
SUB AX, ES:[BX.$$gl_x0]
MOV Xdistance, AX
MOV AX, ES:[BX.$$gl_y1]
SUB AX, ES:[BX.$$gl_y0]
MOV CX, AX

; Determine if slope positive or negative:
TEST AX, 8000h
JZ dl_pos
MOV AX, -1 ;Slope negative.
MOV NegFlag, 1
NEG CX
JMP SHORT drw2

dl_pos: MOV AX, 1
MOV NegFlag, 0
drw2: MOV DeltaYsign, AX
MOV AX, CX ;Get Ydistance back.

; Calculate slope (y1-y0/x1-x0):
MOV DX, $slopeFactor
IMUL DX
IDIV Xdistance
MOV DeltaY, AX ;This is amount (fractional) to add to Y each time.
; Draw line:
drw5: MOV Y_accum, 0
MOV CX, Xdistance

MOV AX, ES:[BX.$$gl_x0]
MOV CurrX, AX
MOV AX, ES:[BX.$$gl_y0]
MOV CurrY, AX

MOV AL, ES:[BX.$$gl_Color]
MOV CurrColor, AL
dl_loop:
CALL DrawPixel
MOV AX, CurrY
MOV LastY, AX
; Move 1 notch on x-axis, determine new y-position:
INC CurrX ;Next X increment.
MOV AX, DeltaY
ADD Y_accum, AX ;Add increment to accumulator.
MOV AX, Y_accum
XOR DX, DX
IDIV SlopeFactor
CMP NegFlag, 1
JNE drw20
SUB CurrY, AX
JMP SHORT drw22
drw20: ADD CurrY, AX

; Adjust accumulator:
drw22: IMUL SlopeFactor
SUB Y_accum, AX ;Take out whole-number part.

; Fill in "sparse" lines:
drw30: MOV AX, CurrY
SUB AX, LastY
JNC drw33
NEG AX
drw33:
CMP AX, 1
JBE drw40 ;If increment <= 1, no need to fill in.
MOV AX, LastY
ADD AX, DeltaYsign ;Add or subtract 1, depending on slope sign.
MOV LastY, AX
PUSH CurrY
MOV CurrY, AX
DEC CurrX ;Fill in behind where we are now.
CALL DrawPixel ;Fill in line.
POP CurrY
INC CurrX
JMP drw30

drw40: LOOP dl_loop
drw99: RET


[daydreamer]

@sudoku
You are only limited to use 16 bit registers indirect addressing ,you can use 32 bit registers too
Rol eax,16 to get two different ax regs
Fractions without fpu ,check Raymond's fixed point tutorial
Been Curious if use fpu for line drawing produces smallest code ?

When Using es pointing to a000h ,shortest code to write a pixel
Stosb
Dec di
Use di as indirect register is simplest

[tda0626]

After some studying up on the subject, I came across Bresenham's line drawing algorithm so my program uses that to draw the line. However, at this point, it can only do values x1 < x2 & y1 < y2 but I intend to add more functionality to it in the near future.

After I got the code in my source file, it wasn't working. Took me a bit to figure it out but it looked like it wasn't treating PCorrect as a negative number when its value should sometimes be negative. Added a check to see if the most significant bit is set and now it seems to work. If someone would like to look over the code and point out other possible bugs, please do. Thanks!

Code Select Expand

.model small


Stack    SEGMENT STACK
    DW 256 DUP(?)
Stack    ENDS

.data

red    db    028h
x        DW    ?        ; used to keep track of x position for draw routine
y          DW    ?        ; used to keep track of y position for draw routine
x1        DW    ?        ; x1 and x2 are used to calculate deltax value
x2        DW    ?
y1        DW    ?        ; y1 and y2 are used to calculate deltay value
y2        DW    ?
deltax    DW    ?        ; deltax and deltay are used to calculate initial value of PCorrect
deltay    DW    ?        ; also they are used in draw routine for pixel correction calculation
PCorrect    DW    ?    ; Pixel Correction

.code

_main proc

mov ax, @data
    mov ds, ax
   
    mov ax, 0A000h        ;video memory
    mov es, ax
    xor di, di
   
    mov ah, 0            ; 320 x 200 mode
    mov al, 013h
    int 10h
   
    mov x1, 2            ; Coordinates of our line (x1,y1) & (x2,y2)
    mov x2, 300
    mov y1, 2
    mov y2, 20
    mov ax, x1
    mov x, ax            ; set our starting x and y values for draw routine
    mov ax, y1
    mov y, ax
   
    mov ax, x2            ; Calculate X2-X1 and store in delta x
    sub ax, x1
    mov deltax,  ax
   
    mov ax, y2            ; Calculate Y2-Y1 and store in delta y
    sub ax, y1
    mov deltay, ax
   
    mov ax, deltay        ; Set our Pixel Correction Value
    mov bx, 2            ; PCorrect = 2 * delta y - delta x
    imul bx                ; Pixel Correction checks to see which Pixel
    mov bx, deltax        ; is closer out of two pixels when the line intersects two pixels
    sub ax, bx
    mov PCorrect,  ax
   
   
   

   
    DrawLine:
               
        mov ax, x        ; If x==x2 we are done drawing the line
        cmp ax, x2
        je EndLine
   
        mov ax, y        ; Calculate offset in video memory
        mov bx, 320        ; Y * 320 + X
        mul bx
        add ax, x

        mov di, ax        ; Set DI to our offset value
        mov al, red
        mov es:[di], al    ; Write a red pixel to memory
       
        inc x                    ; increment x to draw next position
        mov ax, PCorrect            ; Check to see if Pixel Correction is a negative number
        test ax, 08000h
        js Lessthan
       
       
            mov ax,deltay        ; Pixel Correction = PCorrect + 2 * deltay - 2 * deltax
            mov bx, deltax        ; If line is closer to the pixel in the next row, inc y
            sub ax, bx
            mov bx, 2
            imul bx
            add PCorrect, ax
            mov ax, deltay
            inc y
            jmp DrawLine
        Lessthan:
            mov ax, deltay        ; If the line is closer to the adjacent pixel closest to our current position
            mov bx, 2            ; Pixel Correction = PCorrect + 2 * deltay
            imul bx
            add PCorrect, ax
            jmp DrawLine
       
    Endline:   
   
    mov ah, 0            ; wait for key press
    int 16h
   
    mov ax, 04c00h        ; exit
    int 21h
   
_main endp
end _main


Output:

[daydreamer]

Seen in Bresenham line algo code before it starts with cmp x1,x2 and cmp y1,y2 and exchange coordinates if x1>x2  and y1>y2

[NoCforMe]

After some studying up on the subject, I came across Bresenham's line drawing algorithm so my program uses that to draw the line.

Congrats; that's some pretty fancy stuff.

One tiny improvement: you might want to get into the habit of minimizing instructions when doing things like multiplication and division. Instead of your

Code Select Expand

        mov ax, y        ; Calculate offset in video memory
        mov bx, 320        ; Y * 320 + X
        mul bx
you can get rid of an instruction:

Code Select Expand

        mov ax, 320
        mul y
since mul multiplies whatever is in AX by the multiplier (y in this case).

[NoCforMe]

BTW, I'm sure you've realized that you need to deal with the problem of coordinate systems here. If you ask your user for line coordinates they're going to expect them to be in Cartesian space, where y-values increase going up, whereas your actual coordinates in memory increase going down. (Fortunately x-values are the same in both cases.)

[tda0626]

BTW, I'm sure you've realized that you need to deal with the problem of coordinate systems here. If you ask your user for line coordinates they're going to expect them to be in Cartesian space, where y-values increase going up, whereas your actual coordinates in memory increase going down. (Fortunately x-values are the same in both cases.)

Maybe. It might be a case of inverting the the y by subtracting the y given from the y max value but don't know if I want to go that far. We will see.

In any case, I think my next step is to treat each quadrant in its own routine and to get that working. Unfortunately, due to work, I won't be able to work on it till the end of the week. Out of town...

Tim