rysowanie okregu

[cosmogirl3]

mam pytanie znalazlam na stronie przykładowy algorytm rysowania okregu i nie
bardzo rozumiem dlaczego okrag dziela na 8 czesci aby odbic symetrycznei
punkty putpixel(x0-x, y0-y) itd
po co to robia? i dlaczego akurat na 8 a nie na np 16?
wklejam ten linka www.republika.pl/wmula/prog/bresenham.html#t3
putpixel(x0-x, y0-y)
putpixel(x0-x, y0+y)
putpixel(x0+x, y0-y)
putpixel(x0+x, y0+y)
putpixel(x0-y, y0-x)
putpixel(x0-y, y0+x)
putpixel(x0+y, y0-x)
putpixel(x0+y, y0+x)

[arturkosmal]

Widzialem ten program wiele lat temu w innym miejscu. Bodajze PCKurier z 97/98 roku. W tym podziale chodzilo o to, ze rysowanie calego okregu stosujac wyliczenie ze wzoru jest powolne. Wyliczenie osemki i pozniej symetryczne rysowanie jest szybszym algorytmem. Nie wiem dlaczego na 8 (kaprys autora ?). Mozesz sprobowac na 16 i porownac szybkosc dzialania.

[libb]

Aby algorytm przedstawiony w tym linku działał poprawnie dla danej krzywej, musi
ta krzywa spełniać pewne założenia, w szczególności jej nachylenie w każdym
punkcie (kąt między styczną a osią X) nie może przekraczać 45 stopni. Działanie
tego algorytmu można w przybliżeniu opowiedzieć w ten sposób: idziemy wzdłuż
jednej osi zwiększając współrzędną x piksela o 1 - musimy więc określić
współrzędną y - albo jest ona taka sama albo o 1 większa (lub mniejsza jeżeli
funkcja jest nierosnąca), w zależności od tego bliżej którego piksela wypadłaby
rzeczywista wartość funkcji. Gdyby nachylenie fukcji mogło być większe niż 45
stopni to mogłoby się okazać, że będzie dziura w linii na ekranie - współrzędna
y mogłaby skoczyć o więcej niż 1. Jeżeli więc mamy krzywą, która ma nachylenie
zawsze większe niz 45 stopni to odbijamy ją wzdłuż linii o nachyleniu 45 stopni,
tak by spełniała to założenie. Dlatego też do rysowania krzywych o zróżnicowanym
nachyleniu musimy podzielić krzywą na części w których będą spełnione założenia
albo dla danej części, albo dla jej odbicia.
W przypadku rysowania okręgu mamy dodatkowo ułatwione zadanie, ze względu
właśnie na symetrię, jedna ósma tego okręgu idealnie spełnia nam założenia,
ponadto bardzo łatwo jest obliczyć współrzędne dla pozostałych siedmiu punktów z
odbić, więc obliczenia wykonujemy jedynie dla tego kawałka, a rysujemy za każdym
razem 8 punktów korzystając z cytowanych wzorów.
Należy zauważyć, że algorytm ten nie używa żadnych funkcji trygonometrycznych,
dla których obliczenie wartości jest znacznie wolniejsze niż dodawanie czy
mnożenie, bo tylko takie działania w tym algorytmie są wykorzystywane.

[ktosktomafajnegomisiaczka]

eee... a po co trygonometryczne..? rownanie okregu to (x-x0)^2+(y-y0)^2=r^2..
mozna to bardzo ladnie i szybko przerobic na funkcje przy zalozeniu ze bedziemy
rysowac tylko polowe okregu

zakladajac ze chcemy uzyskac funkcje y=f(x,r,x0,y0) i y>=y0:

r^2 - (x-x0)^2 = (y-y0)^2 // obie strony >=0 wiec //pierwiastek
sqrt(r^2 - (x-x0)^2) = y-y0
y = sqrt( r^2 - (x-x0)^2 )
oczywiscie zaby dostac y sensowne trzeba podawac x sensowne, tzn, z zakresu x0-
r..x0+r, ale to chyba logiczne ze sie nie daje wiekszej odchylki od srodka niz
promien okregu?:)

oczywiscie, pierwiastek tez sie liczy wzglednie dlugo w porownaniu z algorytmem
parametrycznym, ale z kolei duzo szybcej niz fkcje trygonometryczne i wzor
wyprowadzasz sobie w 15s:)

a.. no i rysowanie calego okregu to nic innego jak

for(i=x0-r;i<=x0+r;++i)
{y=f(x,r,x0,y0);
putpix(x,y0+y);
putpix(x,y0-y);
}

jesli zas chodi o szybkosc, to szcerze mowiac zamiast bawic sie per-pixel, duzo
lepiej jest aproksymowac okrag wielokatami foremnymi.. jak narysujesz parunasto
pixelowej srednicy osmiokat foremny to nikt nie zauwazy roznicy.. dla wiekszych
promieni trzeba wiecej wierzcholkow. Dzielisz n-kat na 4 cwiartki, wyliczasz
wierzcholki w cwiartce, rysujesz linie miedzy nimi a potem tylko korzystajac z
juz wyliczonych wspolrzednych cwiartki 'odbijasz lustrzanie' pozostale
cwiartki.. osmiokat wyglada brzydko gdy duzy.. ale juz taki np. stukat ma w
cwiartce raptem 25 wierzcholkow (pozycji pixeli) do wyliczenia, reszta to
rysowanie lini :}

a z racji wspomnianej juz idealnej symetrii, mozna sobie podzielic na 8, na 16
etc, ale to wprowadza potem upierdliwosci z przeliczaniem lustrzanych odbic..
podzial na 8 jeszcze ujdzie, ale dalszych nie radze

[libb]

Pierwiastek? Obliczanie takiego czegoś to całkiem skomplikowana sprawa. I trzeba
by to robić w każdym punkcie. Nie rozumiem też po co mielibyśmy przybliżać
okręgi wielokątami. Przecież tak czy owak trzeba byłoby te boki wielokąta
narysować. To że w danym języku jest funkcja, która rasteryzuje odcinek wcale
nie oznacza że możemy zignorować czas jej wykonania. A gdybyśmy do środka takiej
funkcji zajrzeli to by nas niespodzianka spotkała - otóż robi się to właśnie
przy pomocy algorytmu Bresenhama. Zresztą jeśli jest funkcja do rysowania
odcinka to prawie na pewno jest też do rysowania okręgu, o porównywalnym czasie
wykonania. Autorce wątku chodziło o wyjaśnienie pewnych wątpliwości dotyczących
właśnie algorytmu Bresenhama, konkretnie jego modyfikacji dla rasteryzacji
okręgu, dlaczego więc podajesz swoje własne pomysły algorytmów, które by robiły
to samo, ale dużo wolniej?

[cosmogirl3]

Dzieki za odpowiedzi :)
juz wszysko jasne...programik napisany, punkty zdobyte :)

[ktosktomafajnegomisiaczka]

dziekuje za objechanie, przydalo mi sie.. niedoczytalem postu cosmogirl3,
gdybym wiedzial ze konkretnie chodzi o ten alg to bym siedzial cicho :)

a co do wielokatow to mialem na mysli to, ze mozna bardzo ladnie rysowac
prawieze okregi fragmentami wielokatow.. i to wcale nie zajmuje strasznie duzo
czasu, poniewaz wyliczyc trzeba tak na prawde raptem pare wierzcholkow. to ze
rasteryzacja linii tez trwa, to trudno nie zauwazyc, jednak liczac lacznie nie
trwaja wielokaty znowu tak wiele dluzej niz bresenham.. zas jesli potem chcialo
by sie robic jakies cuda w stylu sprawdzania kolizji itp to jednak kanciaste
okregi ulatwiaja zycie:)

co nie zmienia faktu ze nie doczytalem pytania, przepraszam za zamet:)

[alsor]

Takie ręczne metody są niewiele warte -
zarówno z tym sqrt, czy bez sqrt i podziałem na 8
To było dobre na Atari 800 lub jakimś ZX Spectrum...

Teraz takie rzeczy załatwia sprzęt - okrąg (traktowany jako elipsa o równych
osiach) jest prawdopodobnie rysowany jako cztery (lub więcej) krzywe beziera.
Przynajmniej tak wychodzi mi w sys. Windows, robię tak:
- beginpath
- rysuję okrąg
- closepath
- getpath
i tu dostaję zawsze cztery krzywe beziera.

[ktosktomafajnegomisiaczka]

juz to widze jak windowsowe GDI uzywa akceleracji sprzetowej, nie mowiac o
pascalu ktorego caly czas ucza po gimnazjach i liceach.. :P poza tym skoro mowa
o sprzecie, to raczej pytanie go nei dotyczy, bo raczej w tej chwili z obecnym
sprzetem malo kto implementuje recznie rasteryzacje prostych ksztaltow..

[alsor]

> juz to widze jak windowsowe GDI uzywa akceleracji sprzetowej,

Możesz łatwo to sprawdzić - wejdź do trybu awaryjnego
i zobacz jak windows działa bez wspomagania sprzętowego karty graf. (tam jest
standardowa VGA).

W szkołach uczą głównie tego, w czym dobrze się orientuje przeciętny nauczyciel,
a zdrowy informatyk nie będzie marnował czasu na... gadanie za kilkaset zł/mc.