8086汇编中的中点椭圆算法

huangapple go评论154阅读模式
英文:

Midpoint ellipse algorithm in 8086 Assembly

问题

我正在尝试使用8086汇编在VGA(320x200)模式下实现椭圆绘制算法,但对于较大的半径,形状绘制不正确。

如图所示,形状是凹陷的,而不是椭圆形状。当轴的长度较小时,例如(10,15),我得到了可接受的结果,但超过这个范围后,它停止呈现椭圆形状。我使用FPU计算所有值。

SCREEN_WIDTH = 320
SCREEN_HEIGHT = 200
HALF_SCREEN_WIDTH = SCREEN_WIDTH / 2
HALF_SCREEN_HEIGHT = SCREEN_HEIGHT / 2

x_radius dw 40   ;椭圆宽度
y_radius dw 50   ;椭圆高度

x_derivative dw ?    ;由椭圆方程计算的导数
y_derivative dw ?

x_squared dw ?    ;为方便起见的平方值
y_squared dw ?

decision_param dw ?    

four dw 4    ;一些表达式中使用的整数值
two dw 2    ;存储它们以便将它们加载到FPU

calc_x_derivative:
    ;x_derivative = 2 * y_squared * x
    ;RPN: 2 y_squared x * *
    
calc_y_derivative:
    ;y_derivative = 2 * x_squared * y
    ;RPN: 2 x_squared y * *

ellipse:
    ;初始化x为0,y为y_radius
    ;...

calc_decision_param_1:
    ;d1 = y_squared - (x_squared * ry) + (1/4 * x_squared)  
    ;RPN: y_squared x_squared ry * - x_squared 4 / +
    ;...

region_1_loop:
    ;...

calc_decision_param_2:
    ;decision_param = (y_squared * (x + 1/2) * (x + 1/2)) + (x_squared * (y - 1) * (y - 1)) - (x_squared * y_squared)
    ;RPN: y_squared x 1 2 / + * x 1 2 / + * x_squared y 1 - * y 1 - * + x_squared y_squared * -
    ;...

region_2_loop:
    ;...
    
end_program:
    ;...

clear_screen:
    ;...

我尝试了许多不同版本的相同算法,但都没有成功。我认为问题可能出在我的变量上(特别是导数和决策参数),可能是溢出的问题。我尝试通过使用double words而不是words声明变量来修复它,但后来在算法中比较它们时遇到了问题,即使成功编译程序,它仍然不能按预期工作。

英文:

I'm trying to implement an ellipse drawing algorithm with 8086 Assembly in VGA (320x200) mode, but the shape is not drawing properly for bigger radii.

8086汇编中的中点椭圆算法

As you can see the shape is concave or straight not elliptical. I get acceptable result when the axis have small lengths i.e (10, 15) but any more then that and it stops resembling an ellipse. I used an FPU to calculate all values.

    .387

SCREEN_WIDTH = 320
SCREEN_HEIGHT = 200
HALF_SCREEN_WIDTH = SCREEN_WIDTH / 2
HALF_SCREEN_HEIGHT = SCREEN_HEIGHT / 2

stack1 segment stack
            dw 300 dup(?)
stack_top   dw ?    ;stack_top pointer

stack1 ends

code1 segment
start1:
    mov ax,seg stack1 
	mov ss,ax								; initialize stack
	mov sp, offset stack_top

    mov al, 13h     
    mov ah, 0       ; change mode
    int 10h         ; enter graphics mode

    mov byte ptr cs:[color], 10
    
start_draw:
    call clear_screen
    call ellipse

wait_key:
    in  al, 60h ;take keyboard input
    cmp al, 1   ;if ESC end
    je end_program
    jmp wait_key

;-------------------------------------------------------------
;-------------------------------------------------------------
x_radius            dw 40   ;width of the ellipse
y_radius            dw 50   ;height of the ellipse

x_derivative        dw ?    ;derivates calculated from ellipse equation
y_derivative        dw ?

x_squared           dw ?    ;squared values for convenience
y_squared           dw ?

decision_param      dw ?    

four                dw 4    ;int values used in some of the expressions
two                 dw 2    ;storing them so I can load them to the FPU
;----------------------
calc_x_derivative:
;x_derivative = 2 * y_squared * x
;RPN: 2 y_squared x * *
    finit
    fild    word ptr cs:[y_squared]
    fimul   word ptr cs:[two] ;instead of multiplying by 2 
    fimul   word ptr cs:[x]
    fistp   word ptr cs:[x_derivative]
    ret
    
calc_y_derivative:
;y_derivative = 2 * x_squared * y
;RPN: 2 x_squared y * *
    finit
    fild    word ptr cs:[x_squared]
    fimul   word ptr cs:[two] 
    fimul   word ptr cs:[y]
    fistp   word ptr cs:[y_derivative]
    ret

ellipse:
    ;initialize x as 0 and y as y_radius
    mov     word ptr cs:[x], 0
    mov     ax, word ptr cs:[y_radius]
    mov     word ptr cs:[y], ax

x_radius_squared:
    finit 
    fild    word ptr cs:[y_radius]
    fimul   word ptr cs:[y_radius]
    fistp   word ptr cs:[y_squared]

y_radius_squared:
    finit
    fild    word ptr cs:[x_radius]
    fimul   word ptr cs:[x_radius]
    fistp   word ptr cs:[x_squared]

derivatives:
    call calc_x_derivative
    call calc_y_derivative
    
calc_decision_param_1:
;d1 = y_squared - (x_squared * ry) + (1/4 * x_squared)  
;RPN: y_squared x_squared ry * - x_squared 4 / +
    finit
    fild    word ptr cs:[y_squared]
    fild    word ptr cs:[x_squared]
    fild    word ptr cs:[y_radius]
    fmul
    fsub
    fild    word ptr cs:[x_squared]
    fidiv   word ptr cs:[four]
    fadd
    fistp   word ptr cs:[decision_param]

region_1_loop:
    call color_all_symmetries

    inc word ptr cs:[x] 
    call calc_x_derivative

    cmp word ptr cs:[decision_param], 0 ;compare decision_param to 0
    jge region_1_alternative_next       ;if its lower decrement y and calculate alternative decision_param

region_1_next:
;decision_param = decision_param + x_derivative + (y_squared)
;RPN: decision_param x_derivative + y_squared +
    finit
    fild word ptr cs:[decision_param]
    fild word ptr cs:[x_derivative]
    fadd
    fild word ptr cs:[y_squared]
    fadd
    fistp word ptr cs:[decision_param]
    jmp region_1_loop_end

region_1_alternative_next:
;decision_param = decision_param + x_derivative - y_derivative + (y_squared)
;RPN: decision_param x_derivative + y_derivative - y_squared +
    dec word ptr cs:[y]
    call calc_y_derivative
    finit
    fild word ptr cs:[decision_param]
    fild word ptr cs:[x_derivative]
    fadd
    fild word ptr cs:[y_derivative]
    fsub
    fild word ptr cs:[y_squared]
    fadd
    fistp word ptr cs:[decision_param]

region_1_loop_end:
    mov ax, word ptr cs:[x_derivative]
    cmp ax, word ptr cs:[y_derivative]     ;check if x_derivative < y_derivative
    jge calc_decision_param_2              ;if it is we are done with region 1
    jmp region_1_loop

calc_decision_param_2:
;decision_param = (y_squared * (x + 1/2) * (x + 1/2)) + (x_squared * (y - 1) * (y - 1)) - (x_squared * y_squared)
;RPN: y_squared x 1 2 / + * x 1 2 / + * x_squared y 1 - * y 1 - * + x_squared y_squared * -
    fild word ptr cs:[y_squared]
    fild word ptr cs:[x]
    fld1
    fidiv word ptr cs:[two]
    fadd
    fmul
    fild word ptr cs:[x]
    fld1
    fidiv word ptr cs:[two]
    fadd
    fmul
    fild word ptr cs:[x_squared]
    fild word ptr cs:[y]
    fld1
    fsub
    fmul
    fild word ptr cs:[y]
    fld1
    fsub
    fmul
    fadd
    fild word ptr cs:[x_squared]
    fimul word ptr cs:[y_squared]
    fsub
    fistp word ptr cs:[decision_param]

region_2_loop:
    call color_all_symmetries

    dec word ptr cs:[y]
    call calc_y_derivative

    cmp word ptr cs:[decision_param], 0 ;check if decision_param < 0
    jge alternative_region_2_next

region_2_next:
;decision_param = decision_param + x_squared - y_derivative
;RPN: decision_param x_squared + y_derivative -
    finit
    fild word ptr cs:[decision_param]
    fild word ptr cs:[x_squared]
    fadd
    fild word ptr cs:[y_derivative]
    fsub
    fistp word ptr cs:[decision_param]
    jmp region_2_loop_end


alternative_region_2_next:
    inc word ptr cs:[x]
    call calc_x_derivative

region_2_alternative_decision_param:
;decision_param = decision_param + x_derivative - y_derivative + (x_squared)
;RPN: decision_param x_derivative + y_derivative - x_squared +
    finit
    fild word ptr cs:[decision_param]
    fild word ptr cs:[x_derivative]
    fadd
    fild word ptr cs:[y_derivative]
    fsub
    fild word ptr cs:[x_squared]
    fadd
    fistp word ptr cs:[decision_param]

region_2_loop_end:
;y_derivative = y_derivative - (2 * x_squared)
;RPN: y_derivative 2 x_squared * -
    finit
    fild word ptr cs:[y_derivative]
    fild word ptr cs:[two]
    fild word ptr cs:[x_squared]
    fmul
    fsub
    fistp word ptr cs:[y_derivative]

    cmp word ptr cs:[y], 0      ; check if y <= 0
    jg region_2_loop       

end_ellipse:
    ret

;-------------------------------------------------------------
;---------------------  color_pixel  -------------------------

x       dw ?
y       dw ?

temp_y  dw ?
temp_x  dw ?

color   db ?
;---------------------
color_all_symmetries:
    ; Coloring points (xc + x, yc + y), (xc - x, yc + y), (xc + x, yc - y), (xc - x, yc - y)
    push ax

    ;Point (xc + x, yc - y)
    mov ax, HALF_SCREEN_HEIGHT
    sub ax, word ptr cs:[y]
    mov word ptr cs:[temp_y], ax
    mov ax, word ptr cs:[x]
    add ax, HALF_SCREEN_WIDTH
    mov word ptr cs:[temp_x], ax
    call color_pixel

    ;Point (xc - x, yc - y)
    mov ax, HALF_SCREEN_HEIGHT
    sub ax, word ptr cs:[y]
    mov word ptr cs:[temp_y], ax
    mov ax, HALF_SCREEN_WIDTH
    sub ax, word ptr cs:[x]
    mov word ptr cs:[temp_x], ax
    call color_pixel

    ;Point (xc + x, yc + y)
    mov ax, HALF_SCREEN_HEIGHT
    add ax, word ptr cs:[y]
    mov word ptr cs:[temp_y], ax
    mov ax, word ptr cs:[x]
    add ax, HALF_SCREEN_WIDTH
    mov word ptr cs:[temp_x], ax
    call color_pixel

    ;Point (xc - x, yc - y)
    mov ax, HALF_SCREEN_HEIGHT
    add ax, word ptr cs:[y]
    mov word ptr cs:[temp_y], ax
    mov ax, HALF_SCREEN_WIDTH
    sub ax, word ptr cs:[x]
    mov word ptr cs:[temp_x], ax
    call color_pixel

    pop ax
    ret

color_pixel:
    push ax
    push es
    ;position needs to be in a format y*320 + x
    mov ax, 0a000h
    mov es, ax
    mov ax, word ptr cs:[temp_y]    ;selecting a row
    mov bx, SCREEN_WIDTH            
    mul bx                          ;ax multiplying y by 320 to get proper position
    mov bx, word ptr cs:[temp_x]    ;selecting a column
    add bx, ax                      ;adding to the pixel position
    mov al, byte ptr cs:[color]     ;adding a color
    mov byte ptr es:[bx], al

    pop es
    pop ax
    ret
;-------------------------------------------------------------


end_program:
    mov al, 3h
    mov ah, 0
    int 10h

    mov ax, 4c00h
    int 21h

clear_screen:
    mov ax, 0a000h
    mov es, ax
    xor ax, ax
    mov di, ax
    mov cx, SCREEN_WIDTH * SCREEN_HEIGHT
    mov al, 0
    cld
    rep stosb   ;while cx != 0, mov byte ptr es:[di], al; di++; cx--
    ret

code1 ends

end start1

I tried many different version of the same algorithm all to no success. I think it might be an issue with my variables(especially the derivatives and decision parameter) overflowing I tried fixing it by using double words instead of words to declare variables but I had trouble comparing them later in the algorithm, and when I did get the program to compile it still did not work as intended.

答案1

得分: 3

你对变量溢出的猜测是正确的。例如,考虑calc_decision_param_1的计算:

;d1 = y_squared - (x_squared * ry) + (1/4 * x_squared)

这个计算的结果是(50 * 50) - (40 * 40 * 50) + (40 * 40 / 4) = -77100。这已经不适合一个有符号字了,因此fistp word ptr cs:[decision_param]指令无法将默认的'IntegerIndefinite value 8000h'存储在字大小的目标中。

你应该将一些变量定义为双字整数:x_derivativey_derivativedecision_param。所有其他变量将保持其当前的字大小。

检查是否 decision_param < 0 的代码应该简单地查看双字变量的符号位:

test byte ptr cs:[decision_param+3], 80h
jz   alternative_region_2_next

而检查是否 x_derivative < y_derivative 的代码可以使用 ficomp 来比较这些有符号双字整数。根据(冲突的)注释(;check if x_derivative < y_derivative;if it is we are done with region 1),它看起来应该是这样的:

fninit
fild    dword ptr cs:[x_derivative]
ficomp  dword ptr cs:[y_derivative]
fnstsw  ax
sahf
jb      calc_decision_param_2   ; done if x_derivative < y_derivative
jmp     region_1_loop

看起来 x_radius_squared:y_radius_squared: 的功能与它们的名称所告诉我们的恰恰相反!

英文:

> I think it might be an issue with my variables(especially the derivatives and decision parameter) overflowing

Your suspicion about variables overflowing is correct.
As an example, consider the computation for calc_decision_param_1:

> ;d1 = y_squared - (x_squared * ry) + (1/4 * x_squared)

The result for this is (50 * 50) - (40 * 40 * 50) + (40 * 40 / 4) = -77100
This doesn't fit a signed word anymore and therefore the fistp word ptr cs:[decision_param] instruction can't but store the default 'IntegerIndefinite value 8000h' in the word-sized destination.

What you should do is defining some of your variables as dword integers: x_derivative, y_derivative, and decision_param. All other variables will fit their current word size.

> but I had trouble comparing them later in the algorithm

The code that checks whether decision_param &lt; 0 should simply look at the sign bit of the dword variable:

test byte ptr cs:[decision_param+3], 80h
jz   alternative_region_2_next

And the code that checks whether x_derivative &lt; y_derivative could use ficomp to compare these signed dword integers. Based on the (conflicting) comments (;check if x_derivative &lt; y_derivative and ;if it is we are done with region 1), it would look like:

  fninit
  fild    dword ptr cs:[x_derivative]
  ficomp  dword ptr cs:[y_derivative]
  fnstsw  ax
  sahf
  jb      calc_decision_param_2   ; done if x_derivative &lt; y_derivative
  jmp     region_1_loop

calc_decision_param_2:

It would seem that x_radius_squared: and y_radius_squared: do exactly the opposite from what their names tell us!

huangapple
  • 本文由 发表于 2023年5月25日 21:10:30
  • 转载请务必保留本文链接:https://go.coder-hub.com/76332665.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定