Mittpunktscirkelalgoritm

  Rasterisera en cirkel med radie 23 med Bresenhams mittpunktscirkelalgoritm. Endast den gröna oktanten beräknas faktiskt, den speglas helt enkelt åtta gånger för att bilda de andra sju oktanterna.

En cirkel med radie 23 ritad av Bresenham-algoritmen

I datorgrafik är mittpunktscirkelalgoritmen en algoritm som används för att bestämma de punkter som behövs för att rastrera en cirkel . Bresenhams cirkelalgoritm härleds från mittpunktscirkelalgoritmen. Algoritmen kan generaliseras till koniska sektioner .

Algoritmen är relaterad till arbete av Pitteway och Van Aken.

Sammanfattning

Denna algoritm ritar alla åtta oktanterna samtidigt, med början från varje kardinalriktning (0°, 90°, 180°, 270°) och sträcker sig åt båda hållen för att nå närmaste multipel av 45° (45°, 135°, 225°, 315°) ). Den kan bestämma var den ska stanna för när y = x har den nått 45°. Anledningen till att använda dessa vinklar visas i bilden ovan: När x ökar, hoppar eller upprepar det inte något x -värde förrän det når 45°. Så under while-slingan ökar x med 1 varje iteration och y minskar med 1 ibland, aldrig över 1 i en iteration. Detta ändras vid 45° eftersom det är den punkt där tangenten stiger=körs. Medan stiga>springa före och stiga<springa efter.

Den andra delen av problemet, bestämningsfaktorn, är mycket svårare. Detta avgör när y ska minskas . Det kommer vanligtvis efter att pixlarna har ritats i varje iteration, eftersom det aldrig går under radien på den första pixeln. Eftersom i en kontinuerlig funktion, funktionen för en sfär är funktionen för en cirkel med radien beroende av z (eller vad den tredje variabeln är), är det naturligt att algoritmen för en diskret (voxel) sfär också skulle förlita sig på denna mittpunktscirkelalgoritm. Men när man tittar på en sfär är heltalsradien för vissa intilliggande cirklar densamma, men den förväntas inte ha samma exakta cirkel intill sig själv på samma halvklot. Istället behöver en cirkel med samma radie en annan determinant, för att kurvan ska komma in något närmare mitten eller sträcka sig längre ut.

• Hundra femtio koncentriska cirklar ritade med mittpunktscirkelalgoritmen.
• 

  Till vänster är alla cirklar svarta.

• 

  Till höger används rött, svart och blått tillsammans för att visa cirklarnas koncentricitet.

Algoritm

Syftet med algoritmen är att approximera kurvan $x^{2}+y^{2}=r^{2}$ med hjälp av pixlar; i lekmannatermer bör varje pixel vara ungefär lika långt från mitten. Vid varje steg utökas sökvägen genom att välja den intilliggande pixeln som uppfyller $x^{2}+y^{2}\leq r^{2}$ men maximerar $x^{2}+y^{2}$ . Eftersom kandidatpixlarna är intilliggande, förenklas aritmetiken för att beräkna det senare uttrycket, vilket endast kräver bitskiftningar och tillägg. Men en förenkling kan göras för att förstå bitförskjutningen. Tänk på att en vänster bitförskjutning av ett binärt tal är detsamma som att multiplicera med 2. Ergo, en vänster bitförskjutning av radien ger bara diametern som definieras som radien gånger två.

Denna algoritm börjar med cirkelekvationen . För enkelhetens skull, anta att cirkelns mittpunkt är vid $\displaystyle (0,0)}$ . Betrakta först endast den första oktanten och rita en kurva som börjar vid punkten $(r,0)$ och fortsätter moturs och når vinkeln 45.

Den snabba riktningen här ( basvektorn med den större värdeökningen) är $y$ -riktningen. Algoritmen tar alltid ett steg i den positiva $y$ -riktningen (uppåt), och tar ibland ett steg i den långsamma riktningen (den negativa $x$ -riktningen).

Från cirkelekvationen erhålls den transformerade ekvationen $x^{2}+y^{2}-r^{2}=0$ , där $r^ {2}$ beräknas endast en gång under initieringen.

Låt punkterna på cirkeln vara en sekvens av koordinater för vektorn till punkten (på vanligt sätt). Poängen numreras i den ordning de ritas, med $n=1$ tilldelad den första punkten $(r,0)$ .

För varje punkt gäller följande:

${\begin{aligned}x_{n}^{2}+y_{n}^{2}=r^{2}\end{aligned}}$

Detta kan ordnas om så här:

${\begin{aligned}x_{n}^{2}=r^{2}-y_{n}^{2}\end{aligned}}$

Och likaså för nästa punkt:

${\begin{aligned}x_{n+1}^{2}=r^{2}-y_{n+1}^{2} \end{aligned}}$

Eftersom nästa punkt för den första oktanten alltid kommer att vara minst 1 pixel högre än den sista (men också högst 1 pixel högre för att bibehålla kontinuiteten), är det sant att:

${\begin{aligned}y_{n+1}^{2}&=(y_{n}+ 1)^{2}\\&=y_{n}^{2}+2y_{n}+1\end{aligned}}$

${\begin{aligned}x_{n+1}^{2}=r^{2}-y_{n}^{2}-2y_{n}-1\end{aligned}}$

Så omarbeta nästa punkts ekvation till en rekursiv genom att ersätta $x_{n}^{2}=r^{2}-y_{n}^{2 }$ :

${\begin{aligned}x_{n+1}^{2}=x_{n}^{2}-2y_{n}-1 \end{aligned}}$

På grund av kontinuiteten i en cirkel och eftersom maxima längs båda axlarna är desamma, kommer den helt klart inte att hoppa över x punkter när den avancerar i sekvensen. Vanligtvis stannar den på samma x -koordinat, och ibland går den fram med ett.

Den resulterande koordinaten översätts sedan genom att lägga till mittpunktskoordinater. Dessa frekventa heltalstillägg begränsar inte prestandan mycket , eftersom dessa kvadratiska (root) beräkningar kan sparas i den inre slingan i sin tur. Återigen ersätts nollan i den transformerade cirkelekvationen med feltermen.

Initieringen av feltermen härleds från en offset på ½ pixel vid starten. Fram till skärningen med den vinkelräta linjen leder detta till ett ackumulerat värde på $r$ i feltermen, så att detta värde används för initiering.

De frekventa beräkningarna av kvadrater i cirkelekvationen, trigonometriska uttryck och kvadratrötter kan återigen undvikas genom att lösa upp allt i enstaka steg och använda rekursiv beräkning av de kvadratiska termerna från föregående iterationer.

Variant med heltalsbaserad aritmetik

Precis som med Bresenhams linjealgoritm kan denna algoritm optimeras för heltalsbaserad matematik. På grund av symmetri, om en algoritm kan hittas som bara beräknar pixlarna för en oktant, kan pixlarna reflekteras för att få hela cirkeln.

Vi börjar med att definiera radiefelet som skillnaden mellan den exakta representationen av cirkeln och mittpunkten för varje pixel (eller någon annan godtycklig matematisk punkt på pixeln, så länge den är konsekvent över alla pixlar). För alla pixlar med mittpunkten $(x_{i},y_{i})$ definieras radiefelet som:

$RE(x_{i},y_{i})=\left\vert x_{i}^{2}+y_{i}^{2}-r^{2}\right\vert$

För tydlighetens skull är den här formeln för en cirkel härledd från ursprunget, men algoritmen kan modifieras för vilken plats som helst. Det är användbart att börja med punkten $(r,0)$ på den positiva X-axeln. Eftersom radien kommer att vara ett helt antal pixlar, kommer radiefelet helt klart att vara noll:

$RE(x_{i},y_{i})=\left\vert x_{i}^{2}+0^{2}-r^{2}\right\vert =0$

Eftersom den börjar i den första moturs positiva oktanten, kommer den att gå i den riktning som har störst rörelse , Y-riktningen, så det är tydligt att $y_{i+1} =y_{i}+1$ . Eftersom det bara gäller denna oktant, X -värdena bara två alternativ: att förbli samma som föregående iteration, eller minska med 1. En beslutsvariabel kan skapas som avgör om följande är sant:

$RE(x_{i}-1,y_{i}+1)<RE(x_{i },y_{i}+1)$

Om denna olikhet gäller, plotta $(x_{i}-1,y_{i}+1)$ ; om inte, plotta sedan $(x_{i},y_{i}+1)$ . Så hur avgör man om denna ojämlikhet håller? Börja med en definition av radiefel:

${\begin{aligned}RE(x_{i}-1,y_{i}+1)&<RE(x_{i},y_{i}+1)\\\left\vert (x_{ i}-1)^{2}+(y_{i}+1)^{2}-r^{2}\right\vert &<\left\vert x_{i}^{2}+(y_{ i}+1)^{2}-r^{2}\right\vert \\\left\vert (x_{i}^{2}-2x_{i}+1)+(y_{i}^{ 2}+2y_{i}+1)-r^{2}\right\vert &<\left\vert x_{i}^{2}+(y_{i}^{2}+2y_{i}+ 1)-r^{2}\right\vert \\\end{aligned}}$

Absolutvärdesfunktionen hjälper inte, så kvadrera båda sidorna, eftersom en kvadrat alltid är positiv:

${\begin{aligned}\left[(x_{i}^{2}-2x_{i}+1)+(y_{i}^{2} +2y_{i}+1)-r^{2}\right]^{2}&<\left[x_{i}^{2}+(y_{i}^{2}+2y_{i}+ 1)-r^{2}\höger]^{2}\\\vänster[(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+ 1)+(1-2x_{i})\höger]^{2}&<\vänster[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i }+1\höger]^{2}\\\vänster(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\höger)^{ 2}+2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{ i})^{2}&<\vänster[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\höger]^{2}\ \2(1-2x_{i})(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i} )^{2}&<0\\\end{aligned}}$

Eftersom x > 0, termen $(1-2x_{i})<0$ , så att dividera får:

${\begin{aligned}2\left[(x_{i}^{2}+y_{i}^{2}-r^{2})+(2y_{i}+1)\right ]+(1-2x_{i})&>0\\2\vänster[RE(x_{i},y_{i})+Y_{\text{Ändra}}\höger]+X_{\text{Ändra }}&>0\\\end{aligned}}$

Sålunda ändras beslutskriteriet från att använda flyttalsoperationer till enkel heltalsaddition, subtraktion och bitförskjutning (för att multiplicera med 2 operationer). Om ${\displaystyle 2(RE+Y_{\text{Change}})+X_{\text{Change}}>0} ,$ minska sedan x - värdet. Om ${\displaystyle 2(RE+Y_{\text{Change}})+X_{\text{Change}}\leq 0}, behåll sedan$ samma x- värde. Återigen, genom att reflektera dessa punkter i alla oktanterna, resulterar en hel cirkel.

Vi kan minska beräkningen genom att endast beräkna deltat mellan värdena för denna beslutsformel från dess värde i föregående steg. Vi börjar med att tilldela $E$ som $3-2r$ vilket är startvärdet för formeln vid $(x_{0}, y_{0})=(r,0)$ , sedan som ovan vid varje steg om $E>0$ uppdaterar vi det som $E=E+2(5-2x+2y)$ (och minska X ), annars $E=E+2(3+2y)$ därifrån öka Y som vanligt .

Rita ofullständiga oktanter

Implementeringarna ovan ritar alltid endast hela oktanter eller cirklar. För att bara rita en viss båge från en vinkel $\alpha$ till en vinkel $\beta$ måste algoritmen först beräkna $x$ och $y$ -koordinaterna för dessa slutpunkter, där det är nödvändigt att tillgripa trigonometriska eller kvadratrotsberäkningar (se Metoder för att beräkna kvadratrötter ) . Sedan körs Bresenham-algoritmen över hela oktanten eller cirkeln och ställer in pixlarna endast om de faller inom det önskade intervallet. Efter att ha avslutat denna båge kan algoritmen avslutas i förtid.

Om vinklarna anges som lutningar behövs ingen trigonometri eller kvadratrötter: kontrollera helt enkelt att $y/x$ är mellan de önskade lutningarna.

Generaliseringar

Det är också möjligt att använda samma koncept för att rastrera en parabel , ellips eller någon annan tvådimensionell kurva .

externa länkar

• Rita cirklar - En artikel om att rita cirklar, som härrör från ett enkelt schema till ett effektivt
• Midpoint Circle Algoritm i flera programmeringsspråk