Graphics - Bresenham's Line Drawing Algorithm, in MASM

[OceanJeff32]

I will post a complete file after this, but I don't have time tonight, I'm at work, and it's super busy.

I will also TEST this, because I haven't done that yet either.  This is based on Bresenham's Algorithm for line drawing, as described in Michael Abrash's Book: Zen of Graphics Programming. (VGA)

Take a look, let me know what you all think, and if it can be faster. (or if it will even work...i will log on again during this weekend.)

LineDrawing
mov   edi, bitmap   ; edi points to 0,0 on bitmap

mov   eax, maxx   ; load length of row
imul   maxy      ; times by length of column
shl   eax, 2      ; multiply by 4 (32-bits per pixel)
push   eax      ; store bitmap size at ESP+4 (see next push)

mov   eax, maxx   ; load length of row
shl   eax, 2      ; multiply by 4 (32-bits per pixel)
push   eax      ; store ROW size at ESP

here:

mov   eax, 0      ; x0
add   edi, eax   ; edi points to (x0,0)
mov   ebx, 0      ; y0
pop   eax      ; restore
push   eax      ; and save row length
imul   ebx      ; row length * row of beginning point (ebx = y0)
add   edi, eax   ; edi points to (x0,y0)
mov   eax, 0      ; restore x0
mov   ecx, maxx   ; x1
mov   edx, maxy   ; y1
         ; note that x0,y0,x1,y1 are normally parameters passed in
         ; or set to variables and then whatever...

cmp   ebx, edx   ; compare y0 & y1
jle   noxchg      ; if ebx <= edx jump to avoid xchgs
xchg   eax, ecx   ; swap x0 & x1
xchg   ebx, edx   ; swap y0 & y1

noxchg:

sub   edx, ebx   ; dy = y1-y0
sub   ecx, eax   ; dx = x1-x0
         ; note: here eax,ebx are not needed...

mov   ebx, 1      ; XDIR set to one
cmp   ecx, 0      ; if dx is <= 0 jumps to avoid change
jle   xdirfound   ; jump here
neg   ebx      ; XDIR to negative one

xdirfound:

; Variables at this point:
; eax = free      ; ebx = XDIR (+or-1)   ; ecx = DX   ; edx = DY
; EDI points to (x0,y0)   ; ESP = ROW SIZE in bytes
; ESP+4 = BITMAP SIZE in bytes

cmp   ecx, edx
jle   xloopx

; yloop (if we needed a label)...

shl   edx, 1      ; EDX = DY*2 (DY2)
movd   MM3, edx   ; MM3 = DY2
sub   edx, ecx   ; EDX = DY2 - DX
movd   MM2, edx   ; MM2 is set to DY2 - DX (Error of line)
sub   edx, ecx   ; EDX = DY2 - (DX*2) DY2mDX2
movd   MM0, edx   ; MM0 = DY2mDX2

mov   eax, 00FF00FFh   ; purple hex color
movd   MM1, eax   ; MM1 = color of pixel
stosd         ; since it's already in EAX, draw eax color to es:edi (stosd)

beginwhiley:

sub   ecx, 1      ; while (deltaX--)
jz   afterlinexy   ; if zero jump to end of while loop
movd   eax, MM2   ; set eax to ERROR
cmp   eax, 0      ; compare ERROR to ZERO
jl   thiselsey   ; if less than 0 jump to thiselsey
         ; otherwise continue

add   edi, [esp]   ;OR ;pop eax ;push eax ;add edi, eax

paddd   MM2, MM0   ; ADD DY2mDX2 to ERROR or line
jmp   afterelsey   ; skip next step

thiselsey:

paddd   MM2, MM3   ; ADD DY2 to ERROR of line.

afterelsey:

add   edi, ebx   ; ADD XDIR to Pixel point
movd   eax, MM1   ; set color in EAX for stosd
stosd         ; copy eax to es:edi
jmp beginwhiley      ; LOOP UP

xloopx:

shl   ecx, 1      ; ECX = DX*2 (DX2)
movd   MM3, ecx   ; MM3 = DX2
sub   ecx, edx   ; ECX = DX2 - DY
movd   MM2, ecx   ; MM2 = DX2-DY (Error)
sub   ecx, edx   ; ECX = DX2 - (DY*2)
movd   MM0, ecx   ; MM0 = DX2mDY2

mov   eax, 00FF00FFh   ; purple hex color
movd   MM1, eax   ; MM1 = color of pixel
stosd         ; since it's already in EAX, draw eax color to es:edi (stosd)

beginwhilex:

sub   edx, 1      ; while (deltaY--)
jz   afterlinexy   ; if zero jump to end of line drawing
movd eax, MM2
cmp   eax, 0      ; if Error >= 0
jl   thiselsex   ; otherwise jump to thiselsex

add   edi, ebx   ; add ebx (xdir to edi)
paddd   MM2, MM0   ; add DX2mDY2 to ERROR

jmp   afterelsex

thiselsex:

paddd   MM2, MM3   ; just add to error

afterelsex:

add   edi, [esp]   ; ADD ROW to Pixel point
movd   eax, MM1   ; set color in eax for stosd
stosd         ; copy eax to es:edi
jmp beginwhilex      ; LOOP UP

afterlinexy:      ; LINE COMPLETE

Later guys,

Jeff C
:8)

[OceanJeff32]

Hey, ! Yes, but have you read Andre LaMothe's book? Advanced 3D Graphics Rasterization.

Not all computers have graphics cards.

Mine didn't until I opened the case and put one in...boom $99

Plus, line-drawing is pretty basic, if you can learn how to do that, game graphics are a lot easier!  After all, that's just simple bitmap manipulation and arrangement.

ALSO, this isn't 3d either...that's next. Wish me luck!

Later,

Jeff C
:bdg

P.S. Don't get me wrong, I wish they all did! That would be awesome!  They should all have sound cards, video capture cards, wireless high-speed internet, 2.0 gigs RAM, telephone and cable on-board is next!!! Just wait!!!
:8)

[Mark_Larson]

  I think having labels in your code with the word "SEX" in them is going to offend our one female forum reader.  Capitalization for emphasis.

Code Select Expand


add   edi, ebx   ; add ebx (xdir to edi)
paddd   MM2, MM0   ; add DX2mDY2 to ERROR

jmp   afterelsex

thiselSEX:

paddd   MM2, MM3   ; just add to error

afterelSEX:

add   edi, [esp]   ; ADD ROW to Pixel point
movd   eax, MM1   ; set color in eax for stosd
stosd         ; copy eax to es:edi
jmp beginwhilex      ; LOOP UP

[AeroASM]

I think OceanJeff32 means "this else x" and "after else x".

[OceanJeff32]

Thanks AERO, yeah, that's what I meant...whoops! whoopie! oh well.

Hey hitchhiker, my main point was the average consumer isn't going to pay for a separate video card, they are going to wait for the integrated stuff...guys like us aren't average, we like to spend extra money on our computers.

This code listing is not the skeleton, I have that file available, but didn't bring it to work tonight, so I will upload it tomorrow, for all to assemble and run.  There is a problem with the line drawing, that I'm not sure what's happening...I get a line, and it starts drawing at the correct location, but the error and other term does not point the end to the correct location.  The next step is to optimize for run-slicing, that is: calculating the amount of horizontal pixel runs, and optimizing the runs for each segment of the line.  I may just move onto that and hope the problems fix themselves.  We'll see.  I don't care if this works fast, so much as I want to understand what the code is doing.  I should look into the debugger soon...oh boy

Any suggestions on debugging this one guys?

Eventually all will be assimilated,

Jeff C
:U

[Farabi]

  I think having labels in your code with the word "SEX" in them is going to offend our one female forum reader.  Capitalization for emphasis.

Code Select Expand


add   edi, ebx   ; add ebx (xdir to edi)
paddd   MM2, MM0   ; add DX2mDY2 to ERROR

jmp   afterelsex

thiselSEX:

paddd   MM2, MM3   ; just add to error

afterelSEX:

add   edi, [esp]   ; ADD ROW to Pixel point
movd   eax, MM1   ; set color in eax for stosd
stosd         ; copy eax to es:edi
jmp beginwhilex      ; LOOP UP

I dont know am I made mistake or not, but

mov eax,[esi]
mov edx,[esi+4]

is more fast than mmx instrustion

movq mm0,[esi]

[Mark_Larson]

I think OceanJeff32 means "this else x" and "after else x".

I know.  I am teasing him ;)

[OceanJeff32]

Isn't there a manual that lists the timings of each instruction?  I saw one a long time ago, but the new intel manuals don't have each instruction timed, maybe because of branch prediction, etc.

Later,

Jeff C
:bdg

[Mark_Larson]

Isn't there a manual that lists the timings of each instruction?  I saw one a long time ago, but the new intel manuals don't have each instruction timed, maybe because of branch prediction, etc.

Later,

Jeff C
:bdg

  If you were looking in the Instruction Manual ( book 2), it isn't there.  You have to download the optimization manual.  It's a seperate book.  Let me know if you have trouble finding it on Intel's site. They have timings for all the instructions.  Also Agner Fog has timings on his webpage www.agner.org.  There is a PDF in the assembler section.

[OceanJeff32]

Hitchhikr: Thanks, eliminating that cmp that does what SUB already does, is a good idea!  I need to start thinking more like an ASM programmer.

Mark: Yeah, I brought the optimization reference manual to work today, it's actually pretty good reading...I must be a nerd...lol

I'll get back to this project soon too.  I'm going to explore the Direct X Skeleton...

Later,

Jeff C
:U

[Mark_Larson]

  Good luck with it :)  I always enjoyed doing graphics programming.  I prefer OpenGL over DirectX. 

[MichaelW]

P.S. Don't get me wrong, I wish they all did! That would be awesome!  They should all have sound cards, video capture cards, wireless high-speed internet, 2.0 gigs RAM, telephone and cable on-board is next!!! Just wait!!!

You forgot the dual 20GHz Sexium processors...

[AeroASM]

and the five 200petabyte hard drives

[Farabi]

Hi Jeff, what about the parameter? Can you made it this function without MMX and with parameter? My line algo is about 50xslower compared to the Microsoft line algo.

[OceanJeff32]

Yes, I could have done that, I guess if you PUSH all the variables instead of storing them in MMX registers that saves the registers for other things...including other threads...

Then, you would just reference the stack pointer [esp]

I am working on a particle system first though, I will post code here in a few days or so, I'm getting started with Spring Quarter at the local college.

Later guys,

Jeff C
:bdg