Kaj zdaj gledaš? Če niste iz vzporedno vesolje, kjer vsi sedijo za vektorskimi monitorji, nato pa pred vami rastrska slika. Poglej ta trak: /. Če se približate monitorju, lahko vidite pikselirane korake, ki se poskušajo pretvarjati, da so vektorska črta. Za ta namen obstaja cel kup različnih rastrskih algoritmov, rad pa bi spregovoril o algoritmu Bresenham in algoritmu Y, ki najdeta aproksimacijo vektorskega segmenta v rastrskih koordinatah.

Pri delu na proceduralnem generatorju gradbenih načrtov sem naletel na problem rastrizacije. Moral sem predstaviti stene sobe kot celice dvodimenzionalnega niza. Podobne težave se lahko pojavijo pri fizikalnih izračunih, algoritmih za iskanje poti ali izračunih osvetlitve, če se uporablja razdelitev prostora. Kdo bi si mislil, da bo poznavanje algoritmov za rastriranje nekoč lahko prišlo prav?

Princip delovanja Bresenhamovega algoritma je zelo preprost. Vzemite segment in njegovo začetno koordinato x. K x v ciklu dodamo eno za drugo proti koncu segmenta. Pri vsakem koraku se izračuna napaka - razdalja med realno koordinato l na tej lokaciji in najbližjo mrežno celico. Če napaka ne presega polovice višine celice, je zapolnjena. To je celoten algoritem.

To je bilo bistvo algoritma, v resnici je vse videti tako. Najprej se izračuna naklon (y1 - y0)/(x1 - x0). Vrednost napake na začetni točki segmenta (0,0) sprejeto enako nič in prva celica je zapolnjena. V naslednjem koraku se napaki prišteje naklon in analizira njegova vrednost, če je napaka manjša 0.5 , potem je celica napolnjena (x0+1, y0), če je več, je celica zapolnjena (x0+1, y0+1) in ena se odšteje od vrednosti napake. Na spodnji sliki rumena prikazana je linija pred rastrizacijo, zelena in rdeča - razdalja do najbližjih celic. Naklon je enak eni šestini, pri prvem koraku napaka postane enaka naklonu, ki je manjši 0.5 , kar pomeni, da ordinata ostane enaka. Proti sredini črte napaka prečka črto, ena se od nje odšteje, nova piksel pa se dvigne višje. In tako naprej do konca odseka.

Še en odtenek. Če je projekcija segmenta na os x manjša projekcija na os l ali sta začetek in konec segmenta zamenjana, potem algoritem ne bo deloval. Da se to ne bi zgodilo, morate preveriti smer vektorja in njegov naklon, nato pa po potrebi zamenjati koordinate segmenta, zavrteti osi in na koncu vse zmanjšati na enega ali vsaj dva primera. Glavna stvar je, da med risanjem ne pozabite vrniti osi na svoje mesto.

Za optimizacijo izračunov uporabite trik množenja vseh delnih spremenljivk z dx = (x1 - x0). Nato se bo na vsakem koraku napaka spremenila v dy = (y1 - y0) namesto naklon in naprej dx namesto enega. Lahko tudi malo spremenite logiko, "premaknete" napako tako, da je meja na nič, in lahko preverite predznak napake; to je lahko hitreje.

Koda za risanje rastrske črte z algoritmom Bresenham bi lahko izgledala nekako takole. Psevdokoda iz Wikipedije, pretvorjena v C#.

void BresenhamLine(int x0, int y0, int x1, int y1) ( var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // Preverite rast segmenta vzdolž osi x in vzdolž osi y / / Odseva črto diagonalno, če je kot naklona prevelik, če (strmo) ( Zamenjaj(ref x0, ref y0); // Premeščanje koordinat se izvede v ločena funkcija za zamenjavo lepote (ref x1, ref y1); ) // Če črta ne raste od leve proti desni, zamenjamo začetek in konec segmenta, če (x0 > x1) ( Zamenjaj(ref x0, ref x1); Zamenjaj(ref y0, ref y1); ) int dx = x1 - x0; int dy = Math.Abs(y1 - y0); int napaka = dx / 2; // To uporablja optimizacijo z množenjem z dx, da se znebi dodatnih ulomkov int ystep = (y0< y1) ? 1: -1; // Выбираем направление роста координаты y int y = y0; for (int x = x0; x <= x1; x++) { DrawPoint(steep ? y: x, steep ? x: y); // Не забываем вернуть координаты на место error -= dy; if (error < 0) { y += ystep; error += dx; } } }

Bresenhamov algoritem ima modifikacijo za risanje krogov. Tam vse deluje po podobnem principu, na nek način celo bolj preprosto. Izračun je narejen za en oktant, vsi ostali deli kroga pa so narisani po simetriji.

Primer kode za risanje kroga v C#.

void BresenhamCircle(int x0, int y0, int polmer) ( int x = polmer; int y = 0; int radiusError = 1 - x; medtem ko (x >= y) ( DrawPoint(x + x0, y + y0); DrawPoint (y + x0, x + y0); DrawPoint (-y + x0, x + y0); DrawPoint (x + x0, -y + y0); DrawPoint(y + x0, -x + y++);< 0) { radiusError += 2 * y + 1; } else { x--; radiusError += 2 * (y - x + 1); } } }

Zdaj o Wu Xiaolinovem algoritmu za risanje gladkih linij. Razlikuje se v tem, da se na vsakem koraku izvede izračun za dve piksli, ki sta najbližji črti, in sta pobarvani z različno intenzivnostjo, odvisno od razdalje. Točno prečkanje sredine slikovne pike daje 100 % intenzivnost, če je slikovna pika oddaljena 0,9 slikovne pike, bo intenzivnost 10 %. Z drugimi besedami, sto odstotkov intenzivnosti je razdeljeno med slikovne pike, ki omejujejo vektorsko črto na obeh straneh.

Na zgornji sliki v rdeči in zelena prikazane so razdalje do dveh sosednjih slikovnih pik.

Za izračun napake lahko uporabite spremenljivko s plavajočo vejico in vzamete vrednost napake iz delnega dela.

Vzorčna koda za gladko črto Wu Xiaolina v C#.

private void WuLine(int x0, int y0, int x1, int y1) ( var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); if (steep) ( Swap(ref x0, ref y0) ); Swap(ref x1, ref y1); if (x0 > x1) (Swap(ref x0, ref y1); ) DrawPoint(steep, x0, y0, 1); / Ta funkcija samodejno spremeni koordinate glede na spremenljivko steep DrawPoint(steep, x1, y1, 1); // Zadnji argument je intenzivnost v delih float dx = x1 - x0; float dy = y1 - y0; ; float y = y0 + gradient; for (var x = x0 + 1; x<= x1 - 1; x++) { DrawPoint(steep, x, (int)y, 1 - (y - (int)y)); DrawPoint(steep, x, (int)y + 1, y - (int)y); y += gradient; } }

Če boste kdaj v prihodnosti delali z mrežami, za trenutek pomislite, morda na novo odkrivate kolo in dejansko delate s piksli, čeprav tega ne veste. Spremembe teh algoritmov se lahko uporabljajo v igrah za iskanje celic pred enoto na zemljevidu, izračun udarne površine strela ali lepo razporejanje predmetov. Lahko pa preprosto narišete črte, kot v programu iz spodnjih povezav.

Precejšen del šolskega tečaja geometrije je posvečen konstrukcijskim problemom. Vprašanja, povezana z algoritmi za konstrukcijo geometrijskih likov, so zanimala starodavne matematike. Kasnejše študije so pokazale njihovo tesno povezavo s temeljnimi vprašanji matematike (dovolj je, če se spomnimo klasičnih problemov o trisekciji kota in kvadraturi kroga). Pojav računalnikov je pred matematike postavil bistveno nova vprašanja, ki se niso mogla pojaviti v predračunalniški dobi. Sem spadajo naloge konstruiranja elementarnih grafičnih objektov – črt in krogov.

Vsako geometrijsko figuro lahko definiramo kot množico točk na ravnini. V geometriji je ta množica praviloma neskončna; tudi odsek vsebuje neskončno veliko točk.

V računalniški grafiki je situacija drugačna. Osnovna komponenta vseh likov - točka - pridobi realne fizične razsežnosti in vprašanja, kot je "koliko točk vsebuje ta lik?" nihče ni presenečen. Znašli smo se v končnem svetu, kjer je vse mogoče primerjati, izmeriti, prešteti. Tudi sama beseda "točka" se redko uporablja. Nadomešča ga izraz pixel (piksel - od element slike - element slike). Če na zaslon pogledate skozi povečevalno steklo, lahko vidite, da delček slike, ki se s prostim očesom zdi trden, dejansko sestoji iz diskretnega niza slikovnih pik. Vendar pa je na zaslonih z nizko ločljivostjo to mogoče opaziti brez povečevalnega stekla.

Piksla ni mogoče razdeliti, ker je najmanjši element slike - "dva in pol piksla" ne obstajata. Tako imamo v računalniški grafiki dejansko celoštevilsko koordinatno mrežo, v vozliščih katere so postavljene točke. Vsi algoritmi, ki služijo računalniški grafiki, morajo to okoliščino upoštevati.

Obstaja še en vidik problema. Recimo, da želite pojesti jabolko. Vam je vseeno ali pojeste celo jabolko ali ga razdelite na 2 polovici in pojeste vsako posebej? Najverjetneje, če je jabolko dovolj okusno, se boste z veseljem strinjali z obema možnostma. Toda z vidika programerja, če razdelite lepo celo jabolko na pol, naredite veliko napako. Navsezadnje se morate namesto čudovitega celega števila ukvarjati z dvema ulomkoma, in to je veliko slabše. Iz istega razloga bo programer izmed obeh enakosti 1 + 1 = 2 in 1,5 + 0,5 = 2 vedno izbral prvo - ker ne vsebuje teh neprijetnih ulomkov. Ta izbira je povezana z vidika povečanja učinkovitosti programov. V našem primeru, ko gre za algoritme za gradnjo elementarnih grafičnih objektov, ki zahtevajo večkratno uporabo, je učinkovitost obvezna zahteva. Večina mikroprocesorjev ima samo celoštevilsko aritmetiko in nima vgrajenih zmožnosti za operacije nad realnimi števili. Seveda se takšne operacije izvajajo, vendar se zgodi, da ena operacija zahteva, da računalnik izvede do ducat ali več ukazov, kar bistveno vpliva na čas izvajanja algoritmov.

Članek je posvečen obravnavi ene od mojstrovin umetnosti programiranja - algoritma za konstrukcijo kroga, ki ga je predlagal Brezenham. Potrebno je razviti metodo za konstrukcijo kroga na celoštevilski koordinatni mreži z uporabo koordinat središča in polmera. Prav tako moramo čim bolj skrajšati čas izvajanja algoritma, ki nas sili, da operiramo s celimi števili, kadar je le mogoče. Katera grafična orodja imamo na voljo? Skoraj nič. Seveda pa moramo znati postaviti piko (pixel) na pravo mesto na zaslonu. Na primer, programski jeziki Borland vsebujejo postopek putpixel, s katerim lahko pustite točko na zaslonu z želenimi koordinatami in barvo. Barva nam ni pomembna, če smo natančni, naj bo bela.

1. Čemu se boste morali odpovedati ...

Predstavljajmo si, da nismo omejeni s sredstvi. Da ne moremo samo delati z ulomki, ampak tudi uporabljati transcendentalne trigonometrične funkcije (to je, mimogrede, povsem mogoče na strojih, opremljenih z matematičnim koprocesorjem, ki prevzame takšne izračune). Naloga je še vedno enaka - zgraditi krog. Kaj bomo storili? Verjetno se bomo spomnili formul, ki parametrično določajo krog. Te formule so precej preproste in jih je mogoče dobiti neposredno iz definicije trigonometričnih funkcij. Po njihovem mnenju krog polmera R s središčem v točki ( x 0 , l 0) lahko definiramo kot množico točk M(x, l), katerih koordinate zadoščajo sistemu enačb

x = x 0 + R ker a

l = l 0 + R sina,

kjer je O = 2 x 2 jaz+1 +2l 2 jaz+1 +4x jaz+1 -2l jaz+1 +3-2R 2 = 2(x i+1) 2 +2y i 2 +4(x i+1)-2y i+3-2R 2 = D jaz +4x jaz +6.

D jaz+1 [z l jaz+1 = y i-1] = 2x 2 jaz+1 +2l 2 jaz+1 +4x jaz+1 -2l jaz+1 +3-2R 2 = 2(x i+1) 2 +2(y i-1) 2 +4(x i+1)-2(y i-1)+3-2R 2 = D jaz +4(x i-y i)+10.

Zdaj, ko smo dobili ponavljajoči se izraz za D jaz+1 prek D jaz, ostane še pridobitev D 1 (kontrolna vrednost na začetni točki.) Ni je mogoče pridobiti ponavljajoče, ker prejšnja vrednost ni definirana, vendar jo je mogoče zlahka najti neposredno

x 1 = 0, l 1 = R Yu D 1 1 = (0+1) 2 +( R-1) 2 -R 2 = 2-2R,

D 1 2 = (0+1) 2 + R 2 -R 2 = 1

D 1 = D 1 1 + D 1 2 = 3-2 R.

Tako algoritem za konstrukcijo kroga, implementiran v bres_circle, temelji na zaporedni izbiri točk; odvisno od predznaka kontrolne vrednosti D jaz izbrana je naslednja točka in sama kontrolna vrednost se po potrebi spremeni. Postopek se začne na točki (0, r), prva točka, ki jo postavi postopek sim, pa ima koordinate ( xc, yc+r). pri x = l postopek se konča.

Če prostor ni diskreten, zakaj potem Ahil prehiti želvo? Če je prostor diskreten, kako potem delci izvajajo Bresenhamov algoritem?

Dolgo sem razmišljal o tem, kakšno je vesolje kot celota in še posebej zakonitosti njegovega delovanja. Včasih so opisi nekaterih fizikalnih pojavov na Wikipediji precej zmedeni, da ostanejo nerazumljivi tudi za človeka, ki ni prav daleč od tega področja. Poleg tega nisem imel sreče z ljudmi, kot sem jaz - tistimi, ki so bili vsaj zelo daleč od tega območja. Vendar se kot programer skoraj vsak dan srečujem z nekoliko drugačno ravnino - algoritmi. In nekega dne, v procesu implementacije nekakšne 2D fizike v konzolo, sem pomislil: "Toda Vesolje je v bistvu ista konzola neznane dimenzije. Ali obstaja kakšen razlog za domnevo, da za linearno gibanje na zaslonu te konzole tako rekoč delci ne bi smeli izvajati Bresenhamovega algoritma? In zdi se, da ni razloga.

Vse, ki vas zanima, kaj je Bresenhamov algoritem, kako ga lahko povežemo s fiziko in kako lahko to vpliva na njegovo interpretacijo – dobrodošli v mačkonu. Morda boste tam našli posredno potrditev obstoja vzporednih vesolj. Ali celo vesolja, ugnezdena eno v drugem.

Bresenhamov algoritem

Preprosto povedano, če želite na karirasti list zvezka narisati črto, debelo eno celico, boste morali prebarvati zaporedne celice, ki stojijo v vrsti. Predpostavimo, da je ravnina zvezkovega lista diskretna v celicah, to pomeni, da ne morete pobarvati dveh sosednjih polovic sosednjih celic in reči, da ste pobarvali celico z odmikom 0,5, ker diskretnost pomeni, da tako dejanje ni dovoljeno. Tako boste z zaporednim barvanjem celic v vrsti dobili segment želene dolžine. Zdaj si predstavljajte, da ga morate obrniti za 45 stopinj v katero koli smer - zdaj boste celice pobarvali diagonalno. V bistvu je to uporabna uporaba dveh preprostih funkcij naših možganov:

F(x) = 0
in

F(x) = x
Zdaj pa si predstavljajte, da je treba segment zasukati še za 10 stopinj, na primer. Nato dobimo klasično homogeno linearno funkcijo:

F(x) = x * tan(55)
In risanje grafa te funkcije z običajnim peresom na običajnem listu papirja ni težko za nobenega učenca 7. razreda. Vendar, kaj storiti v primeru našega domnevnega papirčka, ki je diskreten v celicah? Navsezadnje je treba pri risanju črte izbrati, katere celice prebarvati. Tu nam na pomoč priskoči Bresenhamov algoritem.

Ta agloritem je razvil Jack Bresenham leta 1962, ko je delal pri IBM. Še vedno se uporablja za implementacijo virtualne grafike v številnih aplikacijskih in sistemskih sistemih, od proizvodne opreme do OpenGL. Z uporabo tega algoritma je mogoče izračunati najprimernejši približek za dano premico pri dani stopnji diskretnosti ravnine, na kateri se ta premica nahaja.

Implementacija v Javascriptu za splošni primer

var draw = (x, y) => ( ... ); // funkcija za risanje točke var bresenham = (xs, ys) => ( // xs, ys so nizi in v skladu s tem naj bo deltaX = xs - xs, deltaY = ys - ys, napaka = 0, deltaError = deltaY, y = ys; za (naj bo x = xs; x<= xs; x++) { draw(x, y); error += deltaError; if ((2 * error) >= deltaX) ( y -= 1; napaka -= deltaX; ); ); );

Zdaj pa si predstavljajte, da je prostor, ki nas obdaja, še vedno diskreten. Poleg tega ni pomembno, ali je napolnjen z ničemer, delci, nosilci, Higgsovim poljem ali čim drugim - obstaja določen koncept minimalna količina prostor, manjši od katerega ne more biti nič. In ni pomembno, ali je relativno in ali teorija relativnosti glede tega drži - če je prostor ukrivljen, potem bo lokalno, kjer je ukrivljen, še vedno diskreten, četudi se z drugega položaja zdi, kot da obstaja je bila sprememba v tem istem najnižji prag v katero koli smer. S to predpostavko se izkaže, da mora nek pojav, entiteta ali pravilo izvajati Bresenhamov algoritem za kakršno koli gibanje tako delcev snovi kot nosilcev interakcij. To do neke mere pojasni kvantizacijo gibanja delcev v mikrosvetu - načeloma se ne morejo premikati linearno, ne da bi se »teleportirali« iz koščka prostora v drug košček, ker se potem izkaže, da prostor sploh ni diskreten.

Druga posredna potrditev diskretnosti prostora je lahko sodba, ki temelji na zgoraj navedenem: če z določenim zmanjšanjem obsega opazovanega izgubi sposobnost opisa z evklidsko geometrijo, potem je očitno, da ko najmanjša razdalja prag je premagan, metoda geometrijski opisše vedno mora biti predmet. Naj v taki geometriji ena vzporedna premica ustreza več kot eni drugi premici, ki poteka skozi točko, ki ne pripada prvotni premici, ali pa v takšni geometriji ni koncepta vzporednosti premic ali celo koncepta premic sploh, ampak obstaja katera koli hipotetično predstavljiva metoda za opis geometrije predmeta, ki je krajši od minimalne dolžine. In kot veste, obstaja ena teorija, ki trdi, da je sposobna opisati takšno geometrijo znotraj znanega minimalnega praga. To je teorija strun. Predpostavlja obstoj nekaj, kar znanstveniki imenujejo strune ali brane, v dimenzijah 10/11/26 hkrati, odvisno od interpretacije in matematični model. Meni osebno se zdi, da je približno tako, in za utemeljitev svojih besed bom z vami izvedel miselni eksperiment: na dvodimenzionalni ravnini s povsem »evklidsko« geometrijo deluje že omenjeno pravilo: skozi eno točko lahko narišete samo eno črto, vzporedno z dano. Zdaj to pravilo merimo na tridimenzionalni prostor in dobimo dva nova pravila, ki izhajajo iz tega:

Podobno - skozi eno točko lahko narišete samo eno ravno črto, vzporedno z dano
Na določeni razdalji od dane premice je lahko neskončnost-X ravnih črt in ta neskončnost-X je Y-krat manjša od neskončnosti-Z vseh premic, vzporednih z dano premico, ne glede na razdaljo, kjer je Y , grobo rečeno, možna količina debelina ravne črte v prostoru

Preprosto povedano, če dodamo dimenzijo pri konstruiranju črt, ne dodamo pa dimenzije pri izračunu podrejenosti črt pravilom evklidske geometrije, potem namesto dveh možnih vzporednih črt dobimo "cilinder" možnih črt. okoli središča - prvotna črta. Zdaj pa si predstavljajte, da živimo v svetu Super Maria in skušamo takšen valj projicirati na lasten dvodimenzionalni prostor - po izračunih vzporednih črt ne more biti, po opazovanjih pa jih je neskončno - X. Kaj domnevamo? Tako je, uvedli bomo še eno dimenzijo za konstruiranje ravnih črt, vendar je ne bomo dodali za izračun podrejenosti ravnih črt pravilom evklidske geometrije. Pravzaprav, ko bomo videli projekcijo takega valja na naš izvorni dvodimenzionalni prostor, bomo prišli do teorije strun v našem dvodimenzionalnem svetu.

Vzporedna in ugnezdena vesolja?

Lahko se izkaže, da so starodavni filozofi, ki so videli vedenje v atomskem modelu nebesna telesa in, nasprotno, niso bili, recimo, nič dlje od resnice kot tisti, ki so trdili, da je popolna neumnost. Konec koncev, če se osvobodite vseh vrst znanja in razum logično - teoretično spodnja meja ni nič drugega kot fikcija, ki smo si jo izmislili, da bi omejili delovanje nam znane evklidske geometrije. Z drugimi besedami, vse, kar je manjše od Planckove dolžine ali tako rekoč natančneje prava Planckova dolžina, preprosto ni mogoče izračunati z metodami evklidske geometrije, vendar to ne pomeni, da ne obstaja! Lahko se izkaže, da je vsaka brana niz multiverzumov, in tako se zgodi, da je v območju od Planckove dolžine do neznanega X geometrija realnosti evklidska, pod Planckovo dolžino - na primer geometrija Lobačevskega ali sferična prevladuje geometrija ali katera druga, ne da bi kakor koli omejevala naš let fantazije, nad mejo X pa na primer tako nedesarguesova kot sferična geometrija. Sanje niso škodljive – lahko bi rekli, če ne bi tudi za kvantno gibanje, da ne omenjam linearnega (ki je še vedno kvantiziran na ravni mikrosveta), morajo delci izvajati Bresenhamov algoritem, če je prostor diskreten.

Z drugimi besedami, ali Ahil ne bo nikoli dohitel želve ali pa smo v Matriki, celotnem opazljivem vesolju in slavni fizik, najverjetneje - le kapljica v ogromnem oceanu možne raznolikosti resničnosti.

Bresenhamov algoritem je algoritem, ki določa, katere točke na dvodimenzionalnem rastru je treba osenčiti, da dobimo približek ravne črte med dvema danima točkama.

Segment je narisan med dvema točkama - (x0,y0) in (x1,y1), kjer sta v teh parih označena stolpec in vrstica, katerih številke se povečujejo v desno in navzdol. Najprej bomo predpostavili, da gre naša premica navzdol in v desno, vodoravna razdalja x1 − x0 pa presega navpično razdaljo y1 − y0, tj. je naklon črte od vodoravnice manjši od 45°. Naš cilj je za vsak stolpec x med x0 in x1 določiti, katera vrstica y je najbližje črti, in narisati točko (x,y).

Splošna formulačrte med dvema točkama:

Ker poznamo stolpec x, dobimo vrstico y z zaokroževanjem na celo število naslednja vrednost:

Vendar pa ni treba izračunati natančne vrednosti tega izraza. Dovolj je opozoriti, da y raste od y0 in za vsak korak dodamo ena k x in dodamo vrednost naklona k y

ki se lahko izračuna vnaprej. Poleg tega na vsakem koraku naredimo eno od dveh stvari: ali ohranimo isti y ali pa ga povečamo za 1.

Katerega od teh dveh izbrati, se lahko odločite s sledenjem vrednosti napake, ki pomeni navpično razdaljo med trenutna vrednost y in točna vrednost y za trenutni x. Kadarkoli povečamo x, povečamo vrednost napake za zgoraj navedeno količino naklona s. Če je napaka večja od 0,5, je črta bližje naslednjemu y, zato povečamo y za eno, medtem ko zmanjšamo vrednost napake za 1. V izvedbi spodnjega algoritma plot(x,y) nariše točko in abs vrača absolutna vrednostštevilke:

funkcijočrta (x0, x1, y0, y1)

int deltax:= abs(x1 - x0)

int deltay:= abs(y1 - y0)

resnično napaka:= 0

resnično deltaerr:= deltay / deltax

int y:=y0

za x od x0 do x1

napaka:= napaka + deltaerr

če napaka >= 0,5

napaka:= napaka - 1.0

Naj ima začetek segmenta koordinate (X 1,Y 1), konec pa (X 1,X 2). Označimo

Dx=(X 2 -X 1),dy=(Y 2 -Y 1) . Brez izgube splošnosti bomo predpostavili, da začetek segmenta sovpada z izhodiščem koordinat, ravna črta pa ima obliko

Kje. To verjamemo Izhodišče je na levi strani. Naj bo na (i-1) koraku trenutna točka odseka P i -1 =(r,q) . Izbira naslednje točke S i ali T i je odvisna od predznaka razlike (s-t). Če (s-t)<0 , то P i =T i =(r+1,q) и тогда

X i +1 =i+1;Y i +1 =Y i, če (s-t)≥0, potem P i =T i =(r+1,q+1) in nato X i +1 =i+ 1; Y i +1 =Y i +1;

dx=(s-t)=2(rdy-qdx)+2dy –dx

Ker predznak dx=(s-t) sovpada s predznakom razlike), bomo preverili predznak izraza d i =dx(s-t). . Ker je r=X i -1 in q=Y i -1 , potem

d i +1 = d i +2dy -2dx(y i -y i -1) .

Naj pri prejšnjem koraku d i<0 , тогда(y i -y i -1)=0 и d i +1 = d i +2dy . Если же на предыдущем шаге d i ≥0 , тогда(y i -y i -1)=1 и d i +1 = d i +2dx(y i -y i -1)

Še vedno je treba ugotoviti, kako izračunati d i. Ker je za i=1

Postopek Bresenham(x1,y1,x2,y2,Barva: celo število);

dx,dy,incr1,incr2,d,x,y,xend: celo število;

dx:= ABS(x2-x1);

dy:= Abs(y2-y1);

d:=2*dy-dx; (začetna vrednost za d)

incr1:=2*dy; (prirast za d<0}

incr2:=2*(dy-dx); (prirastek za d>=0)

če x1>x2 potem (začnite od točke z manjšo vrednostjo x)

PutPixel(x,y,Barva); (prva točka odseka)

Medtem ko x

d:=d+incr1 (izberite spodnjo točko)

d:=d+incr2; (izberite zgornjo točko, y se poveča)

PutPixel(x,y,Barva);

26. Splošni Bresenhamov algoritem.

Algoritem izbere optimalne rastrske koordinate za predstavitev segmenta. Za rastrsko enoto je izbran večji korak, Δx ali Δy. Med delovanjem se ena od koordinat - bodisi x ali y (odvisno od naklona) - spremeni za eno. Spreminjanje druge koordinate (na 0 ali 1) je odvisno od razdalje med dejanskim položajem segmenta in najbližjimi mrežnimi koordinatami. Ta razdalja je napaka.

Algoritem je sestavljen tako, da morate vedeti le predznak te napake. Posledično rastrska točka (1, 1) bolje približa potek segmenta kot točka (1, 0). Če je naklon manjši od ½, je ravno obratno. Za naklon ½ ni prednostne izbire. V tem primeru algoritem izbere točko (1, 1). Ker je zaželeno preveriti le predznak napake, je na začetku nastavljen na -½. Če je torej naklon segmenta večji ali enak ½, se lahko vrednost napake na naslednji rastrski točki izračuna kot e = -½ + Δy/Δx.

Da bi bila implementacija Bresenhamovega algoritma popolna, je potrebno obdelati segmente v vseh oktantih. To je enostavno narediti, če v algoritmu upoštevamo številko kvadranta, v katerem leži segment, in njegov kotni koeficient. Ko je absolutna vrednost naklona večja od 1, se y nenehno spreminja za ena, za odločanje o spremembi vrednosti x pa se uporablja Bresenhamov kriterij napake. Izbira stalno spreminjajoče se (+1 ali -1) koordinate je odvisna od kvadranta

var x,y,sy,sx,dx,dy,e,z,i: Celo število;
sprememba: boolean;
začeti
x:=x1; y:=y1;
dx:=abs(x2-x1); dy:=abs(y2-y1) ;
sx:=znak(x2-x1); sy:=znak(y2-y1);
e:= 2*dy-dx;
če dy
drugače začni
z:=dx;
dx:=dy; dy:=z;
sprememba:=true
konec;
za i:=1 do dx+dy se začne
če dy< dx then begin
če spremenite, potem y:=y+sy
sicer x:=x+sx;
e:=e+2*dy;
konec drugega
če se spremeni potem x:=x+sx
sicer y:=y+sy;
e:=e-2*dx
konec;
Form1.Canvas.Pixels:=clblack; // izpis točke, na primer
konec;

27. Bresenhamov algoritem za generiranje kroga

Raster je treba razširiti na linearne in druge, bolj kompleksne funkcije. Porazdelitev končnih rezov, kot so kobilice, elipse, parabole, hiperbole, je bila dodeljena številu robotov. Z največjim spoštovanjem, razumljivo, je bil dodan delež. Eden najučinkovitejših in najlažjih za razumevanje algoritmov za ustvarjanje krogov je Bresenhamov. Za storž je pomembno ustvariti le eno osmino deleža. Ti deli se lahko odstranijo z zaporednimi udarci. Ko je ustvarjen prvi oktant (od 0 do 45 ° protiletne puščice), lahko drugega oktanta izrazimo kot zrcalno sliko premice y = x, kar skupaj daje prvi kvadrant. Prvi kvadrant prebijemo naravnost x = 0, da odstranimo podporni del palice iz drugega kvadranta. Zgornjega podremo naravnost pri = 0, da dokončamo nalogo.

Za prikaz algoritma si poglejmo četrtino vložka s središčem na koordinatni storž. Upoštevajte, da ker se algoritem začne na točki x = 0, y = R, je pri generiranju kroga za puščico leta v prvem kvadratu y monotono padajoča funkcija argumentov. Podobno, če je izhodna točka y = 0, x == R, bo pri generiranju kroga nasproti puščice x monotono padajoča funkcija argumenta y. V našem primeru je izbrana generacija za letnico s storžem v točki x = 0, y = R. Prenesemo, da sta središče vložka in storž točno na rastrskih točkah.

Za katero koli dano točko na krogu pri generiranju za puščico letnice obstajajo samo tri možnosti za izbiro naslednje piksle, najbližjega kroga: vodoravno na desno, diagonalno navzdol in na desno navpično navzdol. Algoritem izbere slikovno piko, za katero je najmanjši kvadrat med eno od teh slikovnih pik in krogom.

28. Koncept fraktala. Zgodovina fraktalne grafike

V vsakdanjem življenju lahko pogosto opazite podobe (vzorce), ki jih na videz ni mogoče matematično opisati. Primer: okna pozimi zamrznejo, na koncu lahko opazujete sliko. Takšne množice imenujemo fraktalne. Fraktali niso podobni znanim figuram iz geometrije in so zgrajeni po določenih algoritmih, ki jih je mogoče implementirati na računalniku. Preprosto povedano, fraktal je slika, ki je posledica neke transformacije, ki se večkrat uporablja za prvotno obliko.
Prve ideje o fraktalni geometriji so se pojavile v 19. stoletju. Cantor je s preprostim rekurzivnim postopkom črto spremenil v zbirko nepovezanih točk, ki so jih pozneje poimenovali »Cantorjev prah«. Vzel bi črto in odstranil osrednjo tretjino ter nato isto ponovil s preostalimi deli. Peano je potegnil posebno vrsto črte. Za risanje je Peano uporabil naslednji algoritem:
Vzel je ravno črto in jo nadomestil s trikrat krajšimi segmenti od prvotne črte. Nato je isto dejanje ponovil z vsakim od segmentov. Njegova edinstvenost je v tem, da zapolni celotno ravnino, tj. za vsako točko, ki se nahaja na ravnini, lahko najdete točko, ki pripada Peanovi premici.
Šteje se za utemeljitelja fraktalne geometrije Benoit Mandelbrot. Mandelbrot je uvedel koncept "fraktala".

Fraktal je geometrijska figura, sestavljena iz delov in ki jo lahko razdelimo na dele, od katerih bo vsak predstavljal manjšo kopijo celote. Glavna lastnost fraktalov je samopodobnost, tj. vsak fragment fraktala na tak ali drugačen način reproducira njegovo globalno strukturo. Fraktale delimo na geometrijske, algebraične, stohastične in sisteme iterabilnih funkcij.

29. Pojem dimenzije in njen izračun

V vsakdanjem življenju se nenehno srečujemo z dimenzijami. Ocenimo dolžino ceste, ugotovimo površino stanovanja itd. Ta koncept je precej intuitiven in, kot kaže, ne zahteva pojasnila. Premica ima dimenzijo 1. To pomeni, da lahko z izbiro referenčne točke katerokoli točko na tej premici določimo z 1 številko - pozitivno ali negativno. Poleg tega to velja za vse črte - krog, kvadrat, parabolo itd.

Dimenzija 2 pomeni, da lahko vsako točko enolično definiramo z dvema številoma. Ne mislite, da dvodimenzionalno pomeni ravno. Tudi površina krogle je dvodimenzionalna (definiramo jo lahko z dvema vrednostima - kotoma, kot sta širina in dolžina).

Če pogledamo z matematičnega vidika, je dimenzija določena na naslednji način: pri enodimenzionalnih predmetih podvojitev njihove linearne velikosti povzroči povečanje velikosti (v tem primeru dolžine) za faktor dva (2^ 1).

Pri dvodimenzionalnih predmetih podvojitev linearnih dimenzij povzroči povečanje velikosti (na primer površine pravokotnika) za štirikrat (2^2).

Pri 3-dimenzionalnih predmetih podvojitev linearnih dimenzij povzroči osemkratno povečanje prostornine (2^3) in tako naprej.

Geometrijski fraktali

S temi fraktali se je začela zgodovina razvoja fraktalov nasploh. To vrsto fraktala dobimo s preprostimi geometrijskimi konstrukcijami. Običajno se pri konstruiranju geometrijskih fraktalov uporablja naslednji algoritem:

Vzame se niz segmentov, na podlagi katerih bo sestavljen fraktal.
Za to množico veljajo določena pravila, ki jo spremenijo v neke vrste geometrijski lik.
Enak sklop pravil velja za vsak del te figure. Z vsakim korakom bo lik postajal vse bolj zapleten in če bomo izvedli neskončno število transformacij, bomo dobili geometrijski fraktal.

Primeri geometrijskih fraktalov: Peanova krivulja, Kochova snežinka, list praproti, trikotnik Sierpinskega,

riž. Snežinka Koch

riž. List

riž. trikotnik Sierpinski

Algebraični fraktali

Fraktal- kompleksna geometrijska figura, ki ima lastnost samopodobnosti, to je sestavljena iz več delov, od katerih je vsak podoben celotni figuri.

Algebrski fraktali so dobili ime, ker so zgrajeni na osnovi algebrskih funkcij. Algebraični fraktali vključujejo: Mandelbrotovo množico, Julijino množico, Newtonove bazene, biomorfe.

-Mandelbrotov komplet: Mandelbrotov niz je leta 1905 prvič opisal Pierre Fatou. Fatou je proučeval rekurzivne procese oblike

Začenši s točko na kompleksni ravnini, lahko pridobite nove točke z zaporedno uporabo te formule zanje. Tako zaporedje točk imenujemo transformirana orbita

Fatou je ugotovil, da orbita pod to transformacijo kaže precej zapleteno in zanimivo vedenje. Takšnih transformacij je neskončno veliko - ena za vsako vrednost. (imenovan Mandelbrot, ker je prvi izvedel zahtevano število izračunov z uporabo računalnika).

-set Julia: Julijin niz racionalnega preslikave - niz točk, katerih dinamika v bližini je v določenem smislu nestabilna glede na majhne motnje začetnega položaja. če f- polinom, obravnavamo tudi napolnjeno Julijino množico - množico točk, ki ne težijo v neskončnost. Običajni niz Julia je njegova meja.

-Newton bazeni: Področja s fraktalnimi mejami se pojavijo, ko so koreni nelinearne enačbe približno najdeni z Newtonovim algoritmom na kompleksni ravnini (za funkcijo realne spremenljivke se Newtonova metoda pogosto imenuje tangentna metoda, ki je v tem primeru posplošena na kompleksno ravnino).

Uporabimo Newtonovo metodo, da poiščemo ničlo funkcije kompleksne spremenljivke s postopkom:

Posebej zanimiva je izbira začetnega približka. Ker funkcija ima lahko več ničel in v različnih primerih lahko metoda konvergira k različnim vrednostim.

- biomorfi: skrajšana oblika Julijeve množice, izračunana po formuli z=z 3 +c. Ime je dobil zaradi podobnosti z enoceličnimi organizmi.

Stohastični fraktali

Tipičen predstavnik te vrste fraktalov je tako imenovana plazma.

Če ga želite sestaviti, vzemite pravokotnik in določite barvo za vsak njegov kot. Nato poiščite osrednjo točko pravokotnika in jo pobarvajte z barvo, ki je enaka aritmetični sredini barv na vogalih pravokotnika + nekaj naključnega števila. Večje kot je to naključno število, bolj raztrgana bo risba.

Naravni predmeti imajo pogosto fraktalno obliko. Za njihovo modeliranje je mogoče uporabiti stohastične (naključne) fraktale. Primeri stohastičnih fraktalov:

trajektorija Brownovega gibanja na ravnini in v prostoru;

meja tirnice Brownovega gibanja na ravnini. Leta 2001 so Lawler, Schramm in Werner dokazali Mandelbrotovo hipotezo, da je njena dimenzija 4/3.

Schramm-Löwnerjeve evolucije so konformno invariantne fraktalne krivulje, ki nastanejo v kritičnih dvodimenzionalnih modelih statistične mehanike, na primer Isingov model in perkolacija.

različne vrste randomiziranih fraktalov, to je fraktalov, pridobljenih z rekurzivnim postopkom, v katerega se na vsakem koraku vnese naključni parameter. Plazma je primer uporabe takega fraktala v računalniški grafiki.

Fraktalna monotipija ali stohatipija je trend v likovni umetnosti, ki vključuje pridobivanje podobe naključnega fraktala.

Povezane informacije.