8086汇编中的中点椭圆算法

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

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:

确定