Index
> DOS > Circle algorithmGoto page 1, 2 Next |
| Author |
|
|
Bimas 28 Jan 2005, 02:46
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.
_________________ "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 |
|||||||||||
28 Jan 2005, 02:46 |
|
|
bubach 28 Jan 2005, 12:37
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 |
|||
|
28 Jan 2005, 12:37 |
|
|
vid 28 Jan 2005, 13:35
ModeX is shiiiiiiiiiiiiiiit for doing things like drawing lines/circles. It is good for cleaning/filling screen and for scrolling.
|
|||
|
28 Jan 2005, 13:35 |
|
|
bubach 28 Jan 2005, 14:35
Ok. Never did much in ModeX.
|
|||
|
28 Jan 2005, 14:35 |
|
|
Matrix 02 Feb 2005, 20:35
Octavio wrote:
hello, monitor cathode tube visible screen aspect ratio is 4:3 320x200 is 4.8:3 320x240 is 4:3 400:300 is ... 
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. |
|||
|
02 Feb 2005, 20:35 |
|
|
Matrix 04 Mar 2005, 06:35
hello,
my circle routine will soon be completed, but if someone can make it faster than me go on
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 ?
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 |
|||
|
04 Mar 2005, 06:35 |
|
|
Octavio 04 Mar 2005, 12:25
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. |
|||
|
04 Mar 2005, 12:25 |
|
|
Dilshod 10 Mar 2005, 09:32
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? |
|||
|
10 Mar 2005, 09:32 |
|
|
Matrix 10 Mar 2005, 12:17
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 |
|||
|
10 Mar 2005, 12:17 |
|
|
bogdanontanu 10 Mar 2005, 12:31
Dilshod
What you have above look like a Taylor version for circles. Bresenham might be slightly faster or similar. |
|||
|
10 Mar 2005, 12:31 |
|
|
Dilshod 10 Mar 2005, 13:49
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. |
|||
|
10 Mar 2005, 13:49 |
|
|
bogdanontanu 10 Mar 2005, 19:22
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 
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. |
|||
|
10 Mar 2005, 19:22 |
|
|
Matrix 11 Mar 2005, 00:44
let's compare them,
what do you say? |
|||
|
11 Mar 2005, 00:44 |
|
|
Dilshod 11 Mar 2005, 07:46
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. |
|||
|
11 Mar 2005, 07:46 |
|
|
Dilshod 11 Mar 2005, 08:04
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 |
|||
|
11 Mar 2005, 08:04 |
|
|
Dilshod 11 Mar 2005, 08:22
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. |
|||
|
11 Mar 2005, 08:22 |
|
|
Matrix 11 Mar 2005, 11:36
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. |
|||
|
11 Mar 2005, 11:36 |
|
|
Dilshod 11 Mar 2005, 13:07
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? |
|||
|
11 Mar 2005, 13:07 |
|
|
Octavio 11 Mar 2005, 15:25
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. |
|||
|
11 Mar 2005, 15:25 |
|
| Goto page 1, 2 Next < Last Thread | Next Thread > |
Forum Rules:
|