flat assembler
Message board for the users of flat assembler.

Index > DOS > Circle algorithm

Goto page 1, 2  Next
Author
Thread Post new topic Reply to topic
Bimas



Joined: 28 Jan 2005
Posts: 2
Bimas
Hi

I've been testing codes for circles, square roots and programming the VGA so I've created a program that draws a circle on the screen in mode 13h. But I'm just wondering why it isn't perfectly round... Does anyone know ?

The sqrt function works well.


Description:
Download
Filename: circulo.asm
Filesize: 943 Bytes
Downloaded: 485 Time(s)


_________________
"Aquele que luta com monstros deve acautelar-se, para não se tornar também um monstro." Nietzsche, Além do Bem e do Mal

RCBS-2002
Post 28 Jan 2005, 02:46
View user's profile Send private message Reply with quote
Octavio



Joined: 21 Jun 2003
Posts: 366
Location: Spain
Octavio
Bimas wrote:
Hi

I've been testing codes for circles, square roots and programming the VGA so I've created a program that draws a circle on the screen in mode 13h. But I'm just wondering why it isn't perfectly round... Does anyone know ?

The sqrt function works well.

Perhaps because in mode 13h pixels are not perfectly square.
Post 28 Jan 2005, 12:34
View user's profile Send private message Visit poster's website Reply with quote
bubach



Joined: 17 Sep 2004
Posts: 340
Location: Trollhättan, Sweden
bubach
Use ModeX (320*240*256), or modify the circle code so that it doesn't look funny.
Maybe this can help you?
http://atrevida.comprenica.com/atrtut09.html
Post 28 Jan 2005, 12:37
View user's profile Send private message Reply with quote
vid
Verbosity in development


Joined: 05 Sep 2003
Posts: 7105
Location: Slovakia
vid
ModeX is shiiiiiiiiiiiiiiit for doing things like drawing lines/circles. It is good for cleaning/filling screen and for scrolling.
Post 28 Jan 2005, 13:35
View user's profile Send private message Visit poster's website AIM Address MSN Messenger ICQ Number Reply with quote
bubach



Joined: 17 Sep 2004
Posts: 340
Location: Trollhättan, Sweden
bubach
Ok. Never did much in ModeX.
Post 28 Jan 2005, 14:35
View user's profile Send private message Reply with quote
Matrix



Joined: 04 Sep 2004
Posts: 1171
Location: Overflow
Matrix
Octavio wrote:
Bimas wrote:
Hi

I've been testing codes for circles, square roots and programming the VGA so I've created a program that draws a circle on the screen in mode 13h. But I'm just wondering why it isn't perfectly round... Does anyone know ?

The sqrt function works well.

Perhaps because in mode 13h pixels are not perfectly square.

hello,
monitor cathode tube visible screen aspect ratio is 4:3
320x200 is 4.8:3
320x240 is 4:3
400:300 is ... Smile
so if you want a perfect circle you have to add an y correction (aspect ratio, and/or dimension correction) if i have a litle time i will make one, because writing a simple PCB CAD software, this needs it.
and some anti aliasing is nice to round the squares in case little circles.
Post 02 Feb 2005, 20:35
View user's profile Send private message Visit poster's website Reply with quote
Matrix



Joined: 04 Sep 2004
Posts: 1171
Location: Overflow
Matrix
hello,
my circle routine will soon be completed, but if someone can make it faster than me go on Smile
here 's the first version displaying 90 dots
i'm currently on making it automatically etect the stair angle, this could fairly speed up the little circle drawing.
Code:
;Circle 001F by Z - MATRIX
org 256

mov   al,13h ; ah=0 so -1 bytes
int   10h
push $a000
pop es

finit ; init FPU

call set320x200x256

mov ax,160
mov bx,100
mov ch,100
mov dx,99
call cicle001f

call breadkey

call set80x25t
int 20h ;exit

cicle001f: ; ax=x bx=y ch=col dx=radius
mov [x12],ax
mov [y12],bx
xor bx,bx
mov [rad],dx
fld1 
fld dword [rad]
fadd st0,st0
fdiv st1,st0
fld st0         
fmul st,st0   
fld1      
fsubrp st1,st 
fsqrt           
fpatan        
;ret
;fstp qword [cirad]

fldz
fstp qword [degcnt]

.go:
fld  qword [degcnt]
fld  qword [cirad]
faddp st1,st0
fst qword [degcnt]
fsincos

fimul dword [rad] ; (x)
fmul dword [xcorrection] ; ( 1.2 )
fiadd dword [x12] ; ( cos )

fistp dword [xz12]

fimul dword [rad] ; (y)
fiadd dword [y12] ; ( sin )

fistp dword [yz12]

mov     eax,[yz12]
lea edi,[4*eax+eax]
shl di,6
add     di,[xz12]     

mov [es:di],ch

inc bx
cmp bx,90
jb .go

ret

degcnt: dq 0
cirad : dq 0.07
xcorrection : dd 1.2
rad : dd ?
x12 : dd ?
y12 : dd ?
xz12 : dd ?
yz12 : dd ?
tmpx : dq ?

set320x200x256:
mov ax,$13
int $10
ret

set80x25t:
mov ax,$07
int $10
ret

putpixel320x200x256: ; al=color bx=x cx=y
push $a000
pop es
push ax
mov ax,320
mul cx
add ax,bx
mov di,ax
pop ax
stosb
ret

breadkey:  ;returns: AH = BIOS scan code AL = ASCII character note: enhanced
mov ah,$10
int $16
ret
    


its just about complete,
some adjustments may be needed,
see how easy to draw a nice circle ? Smile
it has x correction added for 320x200 ( 1.2 * X )
you can adjust precision, this is able to draw about 200 circles (99 radius) per second (estimated) on my machine, a little slow.
Code:
;Circle 003F by Z - MATRIX
org 256

mov   al,13h ; ah=0 so -1 bytes
int   10h
push $a000
pop es

finit ; init FPU
call set320x200x256

mov ax,160
mov bx,100
mov ch,110
mov dx,49
call cicle001f

call breadkey

call set80x25t
int 20h ;exit

cicle001f: ; ax=x bx=y ch=col dx=radius
mov [x12],ax
mov [y12],bx
xor bx,bx
mov [rad],dx
fldz
fstp dword [degcnt]
fld1
fild dword [rad]
fmul dword [prec]
fdivp st1,st0
fld st0
fmul st,st0
fld1
fsubrp st1,st
fsqrt
fpatan
fstp dword [cirad]
.go:
fld  dword [degcnt]
fld  dword [cirad]
faddp st1,st0
fst dword [degcnt]
fsincos
fimul dword [rad] ; (x)
fmul dword [xcorrection] ; ( 1.2 )
fiadd dword [x12] ; ( cos )
fistp dword [xz12]
fimul dword [rad] ; (y)
fiadd dword [y12] ; ( sin )
fistp dword [yz12]
mov     eax,[yz12]
mov bx,di
lea edi,[4*eax+eax]
shl di,6
add     di,[xz12]
fldpi
fadd st0,st0
fcomp dword [degcnt]
fstsw ax
cmp bx,di
je .skip
mov [es:di],ch
.skip:
and ah,0001b
jz .go
ret
degcnt: dd 0
cirad : dd ? ;0.07
xcorrection : dd 1.2
prec: dd 16.0
rad : dd ?
x12 : dd ?
y12 : dd ?
xz12 : dd ?
yz12 : dd ?

set320x200x256:
mov ax,$13
int $10
ret

set80x25t:
mov ax,$07
int $10
ret

;cls320x200x256:
;push $a000
;pop es
;xor eax,eax
;mov di,ax
;mov cx,$3e80
;rep stosd
;ret

breadkey:  ;returns: AH = BIOS scan code AL = ASCII character note: enhanced
mov ah,$10
int $16
ret
    
Post 04 Mar 2005, 06:35
View user's profile Send private message Visit poster's website Reply with quote
Octavio



Joined: 21 Jun 2003
Posts: 366
Location: Spain
Octavio
there are fasters algorithms that don´t use the fpu,some time ago i found a web page that describes something like middle point algoritm that was able to draw lines and curves using only + - and conditional jumps, but i haven´t found this page now. Another option is the bresenham circle algoritm ,those algoritms can improve speed in all this demos that use
instructions like fsincos.
Post 04 Mar 2005, 12:25
View user's profile Send private message Visit poster's website Reply with quote
Dilshod



Joined: 23 Feb 2005
Posts: 23
Location: Uzbekistan, Tashkent
Dilshod
One time I wrote such algorithm. Realy using only +,-,cmp, jumps.
See that example in Basic:
PSET = putpixel
(CentX,CentY) = (160,100)
r - Radius

'''Main:
r = 50

x = 0
y = -r
rd = r * r 'Only one multiple on Begining of procudure
yd = rd: yad = r + r + 1
xd = 0: xad = 1
FOR i = 0 TO r - r / 4
PSET (x + 160, y + 100)
PSET (-x + 160, y + 100)
PSET (x + 160, -y + 100)
PSET (-x + 160, -y + 100)
PSET (y + 160, x + 100)
PSET (-y + 160, x + 100)
PSET (y + 160, -x + 100)
PSET (-y + 160, -x + 100)
x = x + 1: xd = xd + xad: xad = xad + 2
IF rd - xd - yd < y + y - 1 THEN
y = y + 1: yd = yd - yad: yad = yad - 2
END IF
NEXT

Any body knows faster algorithm?
Post 10 Mar 2005, 09:32
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
Matrix



Joined: 04 Sep 2004
Posts: 1171
Location: Overflow
Matrix
Hello,

is this gonna be a perfect circle,
or just fast?

it could be at least 1000 times faster in assembly i think ( i estimated this based on turbo pascal ) , the algorithm may be fast, and i guess it cannot be faster because it already plots 8 pixels at a time.

at first sight, it reminds me of (x-u)^2+(y-v)^2=r^2
Post 10 Mar 2005, 12:17
View user's profile Send private message Visit poster's website Reply with quote
bogdanontanu



Joined: 07 Jan 2004
Posts: 403
Location: Sol. Earth. Europe. Romania. Bucuresti
bogdanontanu
Dilshod

What you have above look like a Taylor version for circles.
Bresenham might be slightly faster or similar.
Post 10 Mar 2005, 12:31
View user's profile Send private message Visit poster's website Reply with quote
Dilshod



Joined: 23 Feb 2005
Posts: 23
Location: Uzbekistan, Tashkent
Dilshod
Hi,
This algorithm, I think not much differs Bresenhams.
Certainly you must write it on assembler. This is just Example.
and of course it reminds you: x^2+y^2=r^2
Here is so stunt:

x | x^2 | Delta(x^2) | Delta[delta(x^2)]
-----------------------------------------------
0 | 0 | - | -
1 | 1 | 1 | -
2 | 4 | 3 | 2
3 | 9 | 5 | 2
4 | 16 | 7 | 2
5 | 25 | 9 | 2
6 | 36 | 11 | 2
...
and so there no necessities to compute x^2 evry cicle.
I think that cant be more faster algorithm than this.
Post 10 Mar 2005, 13:49
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
bogdanontanu



Joined: 07 Jan 2004
Posts: 403
Location: Sol. Earth. Europe. Romania. Bucuresti
bogdanontanu
I know that Taylor derivates are fast in drawing curves.
However Bresenham is slightly faster. No algorithm has to calculate anything like x^2 in the loop. It is all about additions and some compares.

Hovever your algorithm does more additions / substractions that Bresenham's.

Bresenham only has one compare and one addition per loop
It looks like you have a couple of additions and a substraction and of course a compare in your loop.

So at least theoretically Bresenham is faster than your algorithm Very Happy

But of course it depends on the actual implementation. For example making a Call for the Plot_Pixel routine will slow things down a lot and hinder the cache.

For two similar ASM implementations Bresenham will be faster than yours.
Not by huge ammounts but noticeably.
Post 10 Mar 2005, 19:22
View user's profile Send private message Visit poster's website Reply with quote
Matrix



Joined: 04 Sep 2004
Posts: 1171
Location: Overflow
Matrix
let's compare them,
what do you say?
Post 11 Mar 2005, 00:44
View user's profile Send private message Visit poster's website Reply with quote
Dilshod



Joined: 23 Feb 2005
Posts: 23
Location: Uzbekistan, Tashkent
Dilshod
Ok,
where can I find Bresenhams algorithm(Write it here)?
Bogdanontanu, I think you are talking about Bresenhams Line drawing algorithm, whenever there more than one Addition (I think there min two Additions) and two compares.
Cant draw Circle only with one Addition and One Comapre. Its Impossible.
What you think about it?
Will much interesting to see that simular Asm code without any calls.
Post 11 Mar 2005, 07:46
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
Dilshod



Joined: 23 Feb 2005
Posts: 23
Location: Uzbekistan, Tashkent
Dilshod
You can more optimis it:
Now, there no any multiple

r = 50

x = 0
y = -r
yad = r + r + 1
xad = 1
xyd = 1
FOR i = 1 TO r - r/4
PSET (x + 160, y + 100)
PSET (-x + 160, y + 100)
PSET (x + 160, -y + 100)
PSET (-x + 160, -y + 100)
PSET (y + 160, x + 100)
PSET (-y + 160, x + 100)
PSET (y + 160, -x + 100)
PSET (-y + 160, -x + 100)
x = x + 1: xyd = xyd - xad: xad = xad + 2
IF xyd < y THEN
y = y + 1: xyd = xyd + yad: yad = yad - 2
END IF
NEXT
Post 11 Mar 2005, 08:04
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
Dilshod



Joined: 23 Feb 2005
Posts: 23
Location: Uzbekistan, Tashkent
Dilshod
Matrix,
I am shure Your code with FPU using is wrong,
what is [prec] variable, How you compute [cirad],
can you write this code on more understandable language,
such as Python,
Algorithms always writes on HiLevel languages and only after this code translates to LowLevel lang.
And I know, using x^2+y^2=r^2 more better than using SinCos.
Post 11 Mar 2005, 08:22
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
Matrix



Joined: 04 Sep 2004
Posts: 1171
Location: Overflow
Matrix
Smile

Dilshod,

sorry for posting a circle code in circle algorithm thread,
i'm sure my code is right, it is drawing a pixelized perfect circle.
short description:
at start time, it determines the minimum stepping angle in RADians - "cirad", you can alter this angle in a linear way using a precision. minimum = 2, first step is ArcSin (i/(2r)) = alpha ; i = 1
precision:
; ArcSin (i/(precision*r)) = alpha ; i = 1
this was more sympathic to me than reversing c^2=a^2+b^2+2*ab*cos(fi) ...
but since it is not synchronized, you may want to use a higher value to draw a perfect circle(because some pixles may be ~1 pixel misaligned, therefore circle is not symmetric anymore)
"degcnt" is current angle counter
is is also possible to plot 4 or 8 pixles at a time to make it faster.

additionally, it has an X correction of 1.2 added, because of 320X200 mode,
you can use other if preferred.
Post 11 Mar 2005, 11:36
View user's profile Send private message Visit poster's website Reply with quote
Dilshod



Joined: 23 Feb 2005
Posts: 23
Location: Uzbekistan, Tashkent
Dilshod
It is hard for me to write and understanding english.
Your algorithm is draws perfect circles and ovals, but it quite not effectively, because there excess of pixel ploting and small accuracy to correct this. What you think?
Post 11 Mar 2005, 13:07
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
Octavio



Joined: 21 Jun 2003
Posts: 366
Location: Spain
Octavio
this is a small (78b) DOS program that draws a circle.
It uses mode 13h so the circle seems a ellipse
Code:
r=99 
color=100  
rd = r * r
mov ax,13h 
int 10h
push 0a000h
pop ds
xor dx,dx
xor bp,bp
mov ax,r
mov bx,ax 
mov si, 1
mov di,(rd-r)/2-1 
lea cx,[bx+si]

l1:
pusha
sub ax,r 
mov cl,4
l2: 
imul di,ax,320 
mov byte[di+bx],color
xchg ax,bx 
imul di,ax,320 
mov byte[di+bx],color
neg ax
add ax,r*2 
loop l2
popa
add bp,si 
inc si
lea dx,[bp+di-rd/2]
dec bx
cmp dx,ax 
ja l1
sub di,cx 
dec cx
inc ax 
cmp si,cx 
jna l1
int 16h
ret
    

and bresenham algo. is not faster. Smile
Post 11 Mar 2005, 15:25
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:  
Goto page 1, 2  Next

< 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.

Powered by rwasa.