flat assembler
Message board for the users of flat assembler.

Index > DOS > Line drawing

Author
Thread Post new topic Reply to topic
me239



Joined: 06 Jan 2011
Posts: 200
me239
Hello, I recently came across a simple line drawing routine much shorter than Bresenham, but there is one part I don't quite understand. Here is the complete routine:
Code:
les DI, Screen.Buffer
  mov BX, Y1
  add BX, BX
  add DI, WORD [BX+Screen.YTable]  { DI := Y1*320+X1 }
  add DI, X1

  mov AX, X2   { DeltaX := X2-X1+1 }
  mov BX, Y2   { DeltaY := Y2-Y1+1 }
  sub AX, X1
  sub BX, Y1
  inc AX
  inc BX

  { ShortLen := DeltaX DIV DeltaY
    Rem := DeltaX MOD DeltaY }

  xor DX, DX  { Clear upper word       }
  div BX      { AX = ShortLen DX = Rem }
  mov CX, AX   { CX = ShortLen }

  xor AX, AX   { Rem is already SHL 16 }
  div BX       { Incr := (LONGINT(Rem) SHL 16) DIV DeltaY }

  mov SI, AX   { SI := Incr }

  mov DX, CX             { DX = ShortLen                               }
  mov AH, BL             { AH = DeltaY                                 }
  mov AL, Color
  xor CX, CX             { Initialize CX to zero                       }
  mov BX, 32768          { BX = 0.5 SHL 16                             }
@InnerLoop:
  add BX, SI             { Update our fraction...                      }
  adc CX, DX             { If it overflows, then draw a long line!     }
  rep stosb              { Draw the run (Sets CX to zero)              }
  add DI, Screen.Width   { Next Y!                                     }

  dec AH
  jnz @InnerLoop         { Try again                                   
    

And this is the part I don't understand
Code:
mov BX, 32768          { BX = 0.5 SHL 16                             }
@InnerLoop:
  add BX, SI             { Update our fraction...                      }
  adc CX, DX             { If it overflows, then draw a long line!     }
    

I understand that is is a overflow catcher, but the part that makes no sense to me is the .5 shl 16. Why does shifting .5 right 16 times and then adding SI to it work?
Oh and one more problem. Why does this work and what does it produce?
Code:
xor AX, AX   { Rem is already SHL 16 }
  div BX       { Incr := (LONGINT(Rem) SHL 16) DIV DeltaY }
    
Post 25 Mar 2011, 04:38
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17350
Location: In your JS exploiting you and your system
revolution
It is adding one half (0.5) using fixed point (16 bit integer and 16 bit fraction) arithmetic.
Post 25 Mar 2011, 04:44
View user's profile Send private message Visit poster's website Reply with quote
me239



Joined: 06 Jan 2011
Posts: 200
me239
revolution wrote:
It is adding one half (0.5) using fixed point (16 bit integer and 16 bit fraction) arithmetic.
Well could you explain how it works? Thanks Smile
Post 25 Mar 2011, 21:13
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17350
Location: In your JS exploiting you and your system
revolution
me239 wrote:
Well could you explain how it works? Thanks Smile
http://en.wikipedia.org/wiki/Fixed-point_arithmetic
Post 25 Mar 2011, 23:11
View user's profile Send private message Visit poster's website Reply with quote
me239



Joined: 06 Jan 2011
Posts: 200
me239
revolution wrote:
me239 wrote:
Well could you explain how it works? Thanks Smile
http://en.wikipedia.org/wiki/Fixed-point_arithmetic
Thanks Very Happy one last thing though, why when AX is empty and DX has a value the DIV command returns a number in AX.
Post 26 Mar 2011, 02:07
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17350
Location: In your JS exploiting you and your system
revolution
me239 wrote:
... one last thing though, why when AX is empty and DX has a value the DIV command returns a number in AX.
Weel as the Intel/AMD manual will tell you, DIV returns the quotient in AX and the remainder in DX.
Post 26 Mar 2011, 02:42
View user's profile Send private message Visit poster's website Reply with quote
me239



Joined: 06 Jan 2011
Posts: 200
me239
revolution wrote:
me239 wrote:
... one last thing though, why when AX is empty and DX has a value the DIV command returns a number in AX.
Weel as the Intel/AMD manual will tell you, DIV returns the quotient in AX and the remainder in DX.
Yes I know that, but AX is empty. So why does AX have a value AFTER the div command. Here is an example
Code:
mov dx, 2 ; DX = 2 
    xor ax, ax ; AX = 0
    mov bx, 10d ; BX = 0Ah
    div bx ; Now AX hold 3333h?!?
    int 20h
    
Post 26 Mar 2011, 04:48
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17350
Location: In your JS exploiting you and your system
revolution
DX:AX == 0002:0000
BX == 000A

DX:AX / BX = 20000h / 0Ah = 3333h (in AX) + 2 remainder (in DX).
Same as: 131072 / 10 = 13107.2
Post 26 Mar 2011, 04:54
View user's profile Send private message Visit poster's website Reply with quote
me239



Joined: 06 Jan 2011
Posts: 200
me239
revolution wrote:
DX:AX == 0002:0000
BX == 000A

DX:AX / BX = 20000h / 0Ah = 3333h (in AX) + 2 remainder (in DX).
Same as: 131072 / 10 = 13107.2
Thanks man! I'm still trying to decipher what the .5 shl 16 is really for with respect to the code, but thanks anyway Very Happy
Post 26 Mar 2011, 05:19
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17350
Location: In your JS exploiting you and your system
revolution
me239 wrote:
I'm still trying to decipher what the .5 shl 16 is really for with respect to the code, but thanks anyway Very Happy
To get good visual results one usually starts half way through the slope when rasterising the lines. Consider a long horizontal line that rises only one pixel vertically. If you start your rasterising at zero offset then you see the line as mostly being drawn on the lower horizontal and only get one pixel in the upper horizontal line at the very end. Whereas if you start at the halfway point then you get a half length lines in both the two horizontal pixel lines. Remember you are quantising a non-integer X/Y values into integer pixel display memory.

Anyhow, I suggest you try it with a zero value in BX instead of the 0.5 value and watch what happens to lines of various slopes. And then try with 3/4, or some other value, and see the results.
Post 26 Mar 2011, 12:26
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2917
Location: [RSP+8*5]
bitRAKE
Think about it in binary.

0001 in binary is one. If you divide this number by two (i.e. shift right by one) the answer is one half. We can represent this as 0000.1000 -- requiring a fractional register with the high bit set. Each position to the right of the decimal represents negative powers of two: 2^-1, 2^-2, 2^-3, ... Work through smaller examples in binary until you are fully convinced as this is a very useful technique.
Post 28 Mar 2011, 05:38
View user's profile Send private message Visit poster's website Reply with quote
me239



Joined: 06 Jan 2011
Posts: 200
me239
bitRAKE wrote:
Think about it in binary.

0001 in binary is one. If you divide this number by two (i.e. shift right by one) the answer is one half. We can represent this as 0000.1000 -- requiring a fractional register with the high bit set. Each position to the right of the decimal represents negative powers of two: 2^-1, 2^-2, 2^-3, ... Work through smaller examples in binary until you are fully convinced as this is a very useful technique.
I'm understanding the fixed point math using DX:AX, but I'm still confused as to why adding 32768(.1) make an accurate line.
Post 28 Mar 2011, 23:05
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17350
Location: In your JS exploiting you and your system
revolution
me239 wrote:
I'm understanding the fixed point math using DX:AX, but I'm still confused as to why adding 32768(.1) make an accurate line.
32768 is 1/2, not 0.1.

Did you try it with a zero value yet? When you see the results then you will understand why.
Post 28 Mar 2011, 23:09
View user's profile Send private message Visit poster's website Reply with quote
me239



Joined: 06 Jan 2011
Posts: 200
me239
revolution wrote:
me239 wrote:
I'm understanding the fixed point math using DX:AX, but I'm still confused as to why adding 32768(.1) make an accurate line.
32768 is 1/2, not 0.1.

Did you try it with a zero value yet? When you see the results then you will understand why.
Yes I tried it with a zero value and I understand that it works, but why it works is still beyond me. PS we are talking about xor'ing out BX right? Just wanted to make sure we're on the same page. Also I now see that it isn't .1. I had been looking at it from a binary viewpoint Razz. Anyways thanks!
Post 29 Mar 2011, 01:37
View user's profile Send private message Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2917
Location: [RSP+8*5]
bitRAKE
Adding 1/2 centers the overflow. Look at a steep/shallow line and compare different starting values for BX - the steps will move, 1/2 gives the most esthetically pleasing line - symmetric steps.
Post 29 Mar 2011, 05:45
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on YouTube, Twitter.

Website powered by rwasa.