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.
(https://i.postimg.cc/87xLSxPq/Capture.jpg) (https://postimg.cc/87xLSxPq)
.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
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...
dec cx
jmp DrawLine
that jump should be jnz maybe, rather than jmp???
Then you wouldnt need the
cmp cx, 0
je EndLine further up in the code.
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.
Quote from: NoCforMe on May 19, 2024, 06:57:57 AMHint: 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.
Remember high-school algebra?
Given 2 points, (x
1,y
1) & (x
2, y
2):
m = y2 - y1 / x2 - x1
m is the slope.
Quote from: NoCforMe on May 19, 2024, 08:32:10 AMRemember high-school algebra?
Given 2 points, (x1,y1) & (x2, y2):
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.
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.
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 (x0, y0). 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.
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.
$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
@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
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!
.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:
(https://i.postimg.cc/SJM60k8p/Capture.jpg) (https://postimg.cc/SJM60k8p)
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
Quote from: tda0626 on May 20, 2024, 12:56:11 AMAfter 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
mov ax, y ; Calculate offset in video memory
mov bx, 320 ; Y * 320 + X
mul bx
you can get rid of an instruction:
mov ax, 320
mul y
since
mul multiplies whatever is in AX by the multiplier (
y in this case).
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.)
Quote from: NoCforMe on May 20, 2024, 03:36:27 AMBTW, 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
Quote from: tda0626 on May 20, 2024, 07:18:05 AMIt 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.
If you do, the formula would be really simple:
Yactual = -YCartesian + Ymax
Hi Tim,
Quote from: tda0626 on May 20, 2024, 07:18:05 AMIn any case, I think my next step is to treat each quadrant in its own routine and to get that working.
The last time I tried coding a general purpose line drawing routine,
I wrote code for the four quadrants, horizontal lines, vertical lines,
and the two diagonal lines. Those last four could be coded up rather
easily, and could be faster than a general purpose line drawing routine.
Regards,
Steve
Edit: With the four special case lines, it should be eight octants, not
four quadrants.
SRN
Steve try port your old code to 32 bit using ddraw or SDL interface to access Max hires screen memory in win32 coding ?
I tried bresenham circle algo and pixelshader approach to use sqrt( x^2+y^2 )
Quote from: FORTRANS on May 20, 2024, 10:19:28 PMThe last time I tried coding a general purpose line drawing routine,
I wrote code for the four quadrants, horizontal lines, vertical lines,
and the two diagonal lines.
I understand everything except why you deal differently with "diagonal" lines (I assume by this you mean lines where the slope is exactly 1 or -1, right?) Why would you need to do that?
I checked with my old DIY line-drawing routine and it works fine with "diagonal" lines.
Hi,
Quote from: NoCforMe on May 21, 2024, 01:27:31 PMI understand everything except why you deal differently with "diagonal" lines (I assume by this you mean lines where the slope is exactly 1 or -1, right?) Why would you need to do that?
It has been a while since I last looked at it, but it was either
for increased speed or reduced "bookkeeping". For either it allows
for not updating variables and testing for when to update things.
Just run a loop to its end.
Regards,
Steve N.
Hi,
Looked at some old notes, not any actual code. I was
trying to get the fastest code possible. Mostly in mode
6 screen format (640x200x1). Also mode 13 and some VESA
modes. It looks as if I spent way too much time and effort
for what I finally ended up using.
I looked at line drawing code by Abrash, Wilton, and the
Waite Group. And tried out some different algorithms with
my own code. Including drawing from both ends to meet in
the middle.
The slow mode 6 code that started the whole exercise was
more flexible and useful in the end. Speeded it up a little
bit, but not as much as I had wanted. Basically, I needed
a routine that allowed for differing pixel types for drawing
things like fat lines or XORed lines. All the faster line
drawing routines had only one type of pixel, direct writing
to the screen.
Cheers,
Steve N.
Cheers,
Steve N.
Quote from: FORTRANS on May 22, 2024, 03:55:08 AMLooked at some old notes, not any actual code. I was
trying to get the fastest code possible. Mostly in mode
6 screen format (640x200x1). Also mode 13 and some VESA
modes. It looks as if I spent way too much time and effort
for what I finally ended up using.
Steve, have a look at what I posted on the subject in the Workshop (https://masm32.com/board/index.php?topic=11960.0).
I can't for the life of me figure why your code was so complicated. Mine has exactly 4 cases:
o Horizontal and vertical lines are drawn separately, since the general drawing code would fail on them;
o Lines where
Y0 > Y1 are simply mirrored (the endpoints are swapped) and drawn "backwards";
o Otherwise, all line drawing is handled by the same code, regardless of quadrant/octant.
So instead of caring about quadrants/octants, I only care about what I guess you could call left or right vertical halves (regarding that
Y0 > Y1 business).
Now I'm certainly not claiming any speed records, but it seems to be reasonably fast, and not overly complicated.
Hi,
Quote from: NoCforMe on May 22, 2024, 02:25:02 PMI can't for the life of me figure why your code was so complicated. Mine has exactly 4 cases:
I was trying every and any thing. It got complicated in an attempt
to speed things up by special casing things and trying to optimize the
specific routines separately. Essentially lots of special code to
replace general purpose code. If you try every thing, most will end up
being rather bad. Throw the bad out and try using what's left over.
It was interesting at the time. And may have taught me something.
But not useful in general, I suppose.
Regards,
Steve N.
Well, don't feel too bad. Even our most abject failures tend to teach us something useful.
I was going to implement this from the Bresenham Algo wiki. Looks like it checks for 4 cases. What other cases would there be?
plotLine(x0, y0, x1, y1)
if abs(y1 - y0) < abs(x1 - x0)
if x0 > x1
plotLineLow(x1, y1, x0, y0)
else
plotLineLow(x0, y0, x1, y1)
end if
else
if y0 > y1
plotLineHigh(x1, y1, x0, y0)
else
plotLineHigh(x0, y0, x1, y1)
end if
end if
Can your plotLineXXX() routines handle horizontal and vertical lines? Those would be the other two cases to check for, I would think. (If the plot routine can handle horiz. & vert., no need to check for them.)
Remember: horizontal: slope = 0. Vertical: slope = ∞
Don't think it will be an issue.
I have been at this for awhile now and can't figure this problem out so I am asking for some help.
I am trying to get this new line drawing program to work where it draws the different types of lines except vertical and horizontal ones, which will be taken care of later. When drawing from top-right to bottom-left or vice versa, it does not draw correctly, see the picture attached and the source code to this post . This has me stumped! If someone could look over my code and let me know if they see what the issue is, it would be appreciated. Thanks!
(https://i.postimg.cc/WFw0xR55/Capture.jpg) (https://postimg.cc/WFw0xR55)
Quote from: tda0626 on May 28, 2024, 06:32:33 AMI am trying to get this new line drawing program to work where it draws the different types of lines except vertical and horizontal ones, which will be taken care of later. When drawing from top-right to bottom-left or vice versa, it does not draw correctly, see the picture attached and the source code to this post . This has me stumped! If someone could look over my code and let me know if they see what the issue is, it would be appreciated. Thanks!
I also once implemented the Bresenham thing. Your algorithm for PCorrect was definitely wrong.
Attached is your modified sample. It should work. I also added an implementation of mine, which is now deactive, but may be activated.
Quote from: _japheth on May 28, 2024, 11:34:28 AMI also once implemented the Bresenham thing. Your algorithm for PCorrect was definitely wrong.
Thank you for all you do!
Would you mind going into more detail why PCorrect is wrong? I got the PCorrect calculation from the Bresenham Line Algo page:
plotLineLow(x0, y0, x1, y1)
D = (2 * dy) - dx
plotLineHigh(x0, y0, x1, y1)
D = (2 * dx) - dy
Also, what is
@f in the code? I have never seen that.
Tim
Quote from: tda0626 on May 28, 2024, 08:51:21 PMAlso, what is
@f in the code? I have never seen that.
it means jump forward to the next (anonymous) label.
@@: is an anonymous label --- Its kind of a shortcut. if you ever need a quick label and cant come up with a good name.
you can jump forward to it " jxx @f" or jump backward to it "jxx @b" with any of the jxxx jumps
The @f and @b can be either case, upper or lower. short example of usage:
jnz @f
some code here
@@: <---- anonymous label
some other code
jmp @bMistakes can happen if used multiple times, without taking care where the next anonymous label is located - resulting in jumping to wrong anonymous label, or worse getting stuck in endless loop. Best to use named labels if that happens to you too often. (from experience
:tongue: )
Quote from: tda0626 on May 28, 2024, 08:51:21 PMWould you mind going into more detail why PCorrect is wrong? I got the PCorrect calculation from the Bresenham Line Algo page:
Ok, I cannot comment the "Bresenham Line Algo page" - what I coded is about 28 years old, but IMO it's pretty straitforward:
For a flat line ( dx > dy ), the "PCorrect" is initialized with "-dx". Then a loop is entered, where
- x is incremented
- dy is added to PCorrect
- if PCorrect "overflows" ( meaning the total of dy's exceeds dx ), y is incremented/decremented and dx is subtracted from PCorrect.
That seems intuitively correct to me and - as an aside - it works.
@Sudoku Thanks for explanation.
@_japheth I will have to study your code when I get a chance. Thanks for offering it!
I found what was wrong with my code. I knew it was something to do with the PlotLineLow routine and the PCorrect calculation because that would be the routine it would be using. The negative deltay was not playing nicely with my PCorrect calculation so I added an ABS(deltay) in the code with the conditional statements when determining which branch it should take depending on the value of PCorrect. Now it seems to be drawing correctly from right-top to bottom-left and vice versa, see picture attached to this thread.
Tim
(https://i.postimg.cc/ZvWd1HMq/Capture.jpg) (https://postimg.cc/ZvWd1HMq)
Quote from: tda0626 on May 28, 2024, 08:51:21 PMAlso, what is
@f in the code? I have never seen that.
Easy one, I can answer that:
@@: creates an "anonymous" jump target label so you don't have to scratch your head to come up with a name.
@F (or
@f, doesn't matter) used with a jump instruction jumps
forward to the next
@@: label.
@B jumps
back to the next previous label:
CMP AX, -1
JE @F
. . .
@@: NEG AX
. . .
CMP AX, -1
JE @B
BTW, I second what sudoku said above. Anonymous jump labels are really useful but can easily get you into trouble. My general rule is to only use them when the jump instruction and the target are within just a few lines of each other. Otherwise use a named target.
Quote from: tda0626 on May 29, 2024, 08:15:26 AMNow it seems to be drawing correctly from right-top to bottom-left and vice versa, see picture attached to this thread.
(https://i.postimg.cc/ZvWd1HMq/Capture.jpg) (https://postimg.cc/ZvWd1HMq)
Now all you need is some anti-aliasing code ...
Quote from: NoCforMe on May 29, 2024, 09:23:41 AMQuote from: tda0626 on May 29, 2024, 08:15:26 AMNow it seems to be drawing correctly from right-top to bottom-left and vice versa, see picture attached to this thread.
(https://i.postimg.cc/ZvWd1HMq/Capture.jpg) (https://postimg.cc/ZvWd1HMq)
Now all you need is some anti-aliasing code ...
Surely you jest :cool: . I don't even know where to start with that. :joking:
It draws vertical and horizontal lines as is so I didn't have to do a separate routine for those. However, I found another problem. For deltay > deltax, it will draw them from top to bottom fine but not the other way around. It should swap the values if the deltay is negative but for some reason that is not happening so there is something up in my PlotLineHigh routine or so I suspect.
This is odd. I was having trouble with one case in my line drawing program that didn't make sense to me. If the deltay > deltax (steep slope) but the deltax was negative, it would not draw the line correctly. Right before the conditional code to determine which line to draw and to either swap the x and y values, I had NoCforMe's ABS() code that I used to convert the negative to a positive.
mov ax, deltax
cwd
xor ax, dx
sub ax, dx
Fired up DOS debug and got to that part of code that does that ABS() routine but it does not sign extend to DX after the CWD instruction. Anyone know why? As far as I know, that instruction is supported on 386 and higher. The DX register contents are zero after the instruction is executed.
In the meantime, I just used this bit of code to convert it and now it works but still curious to why CWD isn't working because that is a pretty good method if you ask me to get the ABS().
mov ax, deltax
.if ax & 08000h
neg ax
.endif
Tim
CWD was supported way back from the beginning, on the 8086.
What was the value of AX before CWD? Are you sure it was negative?
Quote from: NoCforMe on May 30, 2024, 09:41:44 AMCWD was supported way back from the beginning, on the 8086.
What was the value of AX before CWD? Are you sure it was negative?
Wish I took a screen shot of it. I can't remember unfortunately but my conditional statement code fixed it. I will add your bit of code back in there and test for that condition again but this time I will take screenshots of it and let you know.
Made a loop to test for all cases and it appears to draw everything correctly now, see picture.
(https://i.postimg.cc/gn1R8Fbs/Capture.jpg) (https://postimg.cc/gn1R8Fbs)
Kewl, psychedelic.