Çfarë po shikoni tani? Nëse nuk jeni nga univers paralel, ku të gjithë janë ulur prapa monitorëve vektorë, pastaj përballë jush imazh raster. Shikoni këtë shirit: /. Nëse i afroheni monitorit, mund të shihni hapa të pikseluar që përpiqen të pretendojnë të jenë një vijë vektoriale. Ekzistojnë një grup i tërë algoritmesh të ndryshme rasterizimi për këtë qëllim, por unë do të doja të flisja për algoritmin Bresenham dhe algoritmin Y, të cilët gjejnë një përafrim të një segmenti vektori në koordinatat rasterike.
Problemin e rasterizimit e kam hasur gjatë punës në një gjenerator procedural të planeve të ndërtesave. Më duhej të përfaqësoja muret e dhomës si qeliza të një grupi dydimensional. Probleme të ngjashme mund të hasen në llogaritjet e fizikës, algoritmet e gjetjes së shtigjeve ose llogaritjet e ndriçimit nëse përdoret ndarja e hapësirës. Kush do ta kishte menduar se njohja me algoritmet e rasterizimit një ditë mund të vinte në ndihmë?
Parimi i funksionimit të algoritmit të Bresenhamit është shumë i thjeshtë. Merrni një segment dhe koordinatat e tij fillestare x. X në ciklin i shtojmë një nga një drejt fundit të segmentit. Në çdo hap, llogaritet gabimi - distanca midis koordinatës reale y në këtë vendndodhje dhe në qelizën më të afërt të rrjetit. Nëse gabimi nuk kalon gjysmën e lartësisë së qelizës, atëherë ai plotësohet. Ky është i gjithë algoritmi.
Ky ishte thelbi i algoritmit, në realitet gjithçka duket kështu. Së pari, llogaritet pjerrësia (y1 - y0)/(x1 - x0). Vlera e gabimit në pikën fillestare të segmentit (0,0) pranuar e barabartë me zero dhe qeliza e parë është e mbushur. Në hapin tjetër, pjerrësia i shtohet gabimit dhe vlera e tij analizohet nëse gabimi është më i vogël. 0.5 , atëherë qeliza është e mbushur (x0+1, y0), nëse më shumë, atëherë qeliza është e mbushur (x0+1, y0+1) dhe një zbritet nga vlera e gabimit. Në foton më poshtë të verdhë tregohet linja para rasterizimit, jeshile dhe e kuqe - distanca deri në qelizat më të afërta. Pjerrësia është e barabartë me një të gjashtën, në hapin e parë gabimi bëhet i barabartë me pjerrësinë, që është më pak 0.5 , që do të thotë ordinata mbetet e njëjtë. Kah mesi i rreshtit, gabimi e kalon vijën, i zbritet një dhe piksel i ri ngrihet më lart. Dhe kështu me radhë deri në fund të segmentit.
Një nuancë më shumë. Nëse projeksioni i një segmenti në bosht x më pak projeksion në bosht y ose fillimi dhe fundi i segmentit ndërrohen, atëherë algoritmi nuk do të funksionojë. Për të parandaluar që kjo të ndodhë, duhet të kontrolloni drejtimin e vektorit dhe pjerrësinë e tij, dhe më pas, nëse është e nevojshme, ndërroni koordinatat e segmentit, rrotulloni akset dhe, në fund të fundit, zvogëloni gjithçka në një ose të paktën dy raste. Gjëja kryesore është të mos harroni të ktheni sëpatat në vendin e tyre gjatë vizatimit.
Për të optimizuar llogaritjet, përdorni trukun e shumëzimit të të gjitha variablave thyesore me dx = (x1 - x0). Pastaj në çdo hap gabimi do të ndryshojë në dy = (y1 - y0) në vend të shpat dhe me radhë dx në vend të një. Ju gjithashtu mund të ndryshoni pak logjikën, "lëvizni" gabimin në mënyrë që kufiri të jetë zero dhe mund të kontrolloni shenjën e gabimit.
Kodi për të vizatuar një vijë raster duke përdorur algoritmin Bresenham mund të duket diçka e tillë. Pseudokodi nga Wikipedia u konvertua në C#.
void BresenhamLine(int x0, int y0, int x1, int y1) ( var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // Kontrollo rritjen e segmentit përgjatë boshtit x dhe përgjatë boshtit y / / Reflektoni vijën diagonalisht nëse këndi i prirjes është shumë i madh nëse (i pjerrët) ( Ndërroni (ref x0, ref y0); // Përzierja e koordinatave kryhet në funksion të veçantë për bukurinë Swap (ref x1, ref y1);< 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;
}
}
}
) // Nëse rreshti nuk rritet nga e majta në të djathtë, atëherë ne ndërrojmë fillimin dhe fundin e segmentit nëse (x0 > x1) (Swap(ref x0, ref x1); Swap(ref y0, ref y1); ) int dx = x1 - x0;
int dy = Math.Abs(y1 - y0);
gabim int = dx / 2; // Kjo përdor optimizimin me shumëzim me dx për të hequr qafe thyesat shtesë int ystep = (y0< 0) { radiusError += 2 * y + 1; } else { x--; radiusError += 2 * (y - x + 1); } } }
Tani në lidhje me algoritmin e Wu Xiaolin për vizatimin e linjave të lëmuara. Ai ndryshon në atë që në çdo hap bëhet një llogaritje për dy pikselët më të afërt me vijën, dhe ato pikturohen me intensitet të ndryshëm, në varësi të distancës. Pikërisht kalimi i mesit të një piksel jep 100% intensitet, nëse piksel është 0.9 piksele larg, atëherë intensiteti do të jetë 10%. Me fjalë të tjera, njëqind për qind e intensitetit ndahet midis pikselëve që kufizojnë vijën vektoriale në të dy anët.
Në foton e mësipërme me të kuqe dhe jeshile tregohen distancat me dy piksele fqinje.
Për të llogaritur gabimin, mund të përdorni një variabël me pikë lundruese dhe të merrni vlerën e gabimit nga pjesa fraksionale.
Shembull i kodit për linjën e qetë të Wu Xiaolin në C#.
zbrazëti private WuLine(int x0, int y0, int x1, int y1) ( var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); nëse (pjerrët) ( Swap(ref x0, ref y0 Ndrysho (ref x1, ref y1 ) if (x0 > x1) (Swap (ref x0, ref x1); Ky funksion ndryshon automatikisht koordinatat në varësi të ndryshores së pjerrët DrawPoint (pjerrët, x1, y1, 1). float y = y0 + gradient për (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;
}
}
Nëse ndonjëherë e gjeni veten duke punuar me rrjeta në të ardhmen, mendoni për një moment, ndoshta po rishpikni timonin dhe në të vërtetë po punoni me pikselë, megjithëse nuk e dini. Modifikimet e këtyre algoritmeve mund të përdoren në lojëra për të kërkuar qeliza përpara një njësie në hartë, për të llogaritur zonën e ndikimit të një goditjeje ose për të rregulluar bukur objektet. Ose thjesht mund të vizatoni vija, si në program nga lidhjet më poshtë.
Një pjesë e konsiderueshme e lëndës së gjeometrisë shkollore i kushtohet problemeve të ndërtimit. Pyetjet në lidhje me algoritmet për ndërtimin e figurave gjeometrike ishin me interes për matematikanët e lashtë. Studimet e mëvonshme treguan lidhjen e tyre të ngushtë me pyetjet themelore të matematikës (mjafton të kujtojmë problemet klasike të treprerjes së një këndi dhe katrorit të një rrethi). Ardhja e kompjuterëve shtroi pyetje thelbësisht të reja për matematikanët që nuk mund të kishin lindur në epokën para kompjuterit. Këto përfshijnë detyrat e ndërtimit të objekteve elementare grafike - linja dhe rrathë.
Çdo figurë gjeometrike mund të përkufizohet si një grup pikash në një plan. Në gjeometri ky grup është, si rregull, i pafund; edhe një segment përmban pafundësisht shumë pika.
Në grafikën kompjuterike situata është ndryshe. Komponenti elementar i të gjitha figurave - pika - merr dimensione reale fizike dhe pyetje si "sa pikë përmban kjo figurë?" askush nuk habitet. Ne e gjejmë veten në një botë të fundme ku gjithçka mund të krahasohet, matet, numërohet. Edhe vetë fjala "pikë" përdoret rrallë. Ai zëvendësohet me termin pixel (piksel - nga elementi i figurës - elementi i figurës). Nëse shikoni ekranin e ekranit përmes një xham zmadhues, mund të shihni se një fragment i imazhit që duket i fortë me syrin e lirë përbëhet në të vërtetë nga një grup diskrete pikselësh. Megjithatë, në ekranet me rezolucion të ulët kjo mund të vërehet pa një xham zmadhues.
Një piksel nuk mund të ndahet sepse është elementi minimal i një imazhi - nuk ka gjë të tillë si "dy piksel e gjysmë". Kështu, në grafikën kompjuterike në fakt kemi një rrjet koordinativ me numra të plotë, në nyjet e të cilit vendosen pikat. Të gjithë algoritmet që shërbejnë grafikë kompjuterike duhet ta marrin parasysh këtë rrethanë.
Ekziston një aspekt tjetër i problemit. Le të themi se dëshironi të hani një mollë. A ka rëndësi për ju nëse e hani të gjithë mollën apo e ndani në 2 gjysma dhe e hani secilën veç e veç? Me shumë mundësi, nëse molla është mjaft e shijshme, do të pajtoheni me dëshirë për të dyja opsionet. Por nga këndvështrimi i një programuesi, nëse ndani një mollë të bukur të plotë në gjysmë, po bëni një gabim të madh. Në fund të fundit, në vend të një numri të plotë të mrekullueshëm, duhet të merreni me dy fraksione, dhe kjo është shumë më keq. Për të njëjtën arsye, nga dy barazitë 1 + 1 = 2 dhe 1,5 + 0,5 = 2, programuesi do të zgjedhë gjithmonë të parin - sepse nuk përmban këta numra thyesorë të pakëndshëm. Kjo zgjedhje lidhet me konsideratat e rritjes së efikasitetit të programeve. Në rastin tonë, kur bëhet fjalë për algoritme për ndërtimin e objekteve elementare grafike që kërkojnë përdorim të përsëritur, efikasiteti është një kërkesë e detyrueshme. Shumica e mikroprocesorëve kanë vetëm aritmetikë me numra të plotë dhe nuk kanë aftësi të integruara për operacione në numra realë. Natyrisht, operacione të tilla zbatohen, por ndodh që një operacion kërkon që kompjuteri të ekzekutojë deri në një duzinë ose më shumë komanda, gjë që ndikon ndjeshëm në kohën e ekzekutimit të algoritmeve.
Artikulli i kushtohet shqyrtimit të një prej kryeveprave të artit të programimit - algoritmi i ndërtimit të rrethit të propozuar nga Brezenham. Kërkohet të zhvillohet një metodë për ndërtimin e një rrethi në një rrjet koordinativ me numra të plotë duke përdorur koordinatat e qendrës dhe rrezes. Ne gjithashtu duhet të zvogëlojmë kohën e ekzekutimit të algoritmit sa më shumë që të jetë e mundur, gjë që na detyron të operojmë me numra të plotë sa herë që është e mundur. Çfarë mjetesh grafike kemi në dispozicion? Praktikisht asnjë. Sigurisht, ne duhet të jemi në gjendje të vendosim një pikë (piksel) në vendin e duhur në ekran. Për shembull, gjuhët e programimit Borland përmbajnë një procedurë putpixel, me të cilën mund të lini një pikë në ekran me koordinatat dhe ngjyrën e dëshiruar. Ngjyra nuk ka rëndësi për ne që të jetë specifike, le të jetë e bardhë.
1. Çfarë do të duhet të heqësh dorë...
Le të imagjinojmë se nuk jemi të kufizuar në fonde. Që ne jo vetëm që mund të operojmë me numra thyesorë, por edhe të përdorim funksione trigonometrike transcendentale (kjo, meqë ra fjala, është mjaft e mundur në makinat e pajisura me një bashkëprocesor matematikor që merr përsipër llogaritje të tilla). Detyra është ende e njëjtë - të ndërtosh një rreth. Çfarë do të bëjmë? Ndoshta do të kujtojmë formulat që përcaktojnë parametrikisht një rreth. Këto formula janë mjaft të thjeshta dhe mund të merren drejtpërdrejt nga përkufizimi i funksioneve trigonometrike. Sipas tyre, rrethi i rrezes R me qendër në pikë ( x 0 , y 0) mund të përkufizohet si një grup pikash M(x, y), koordinatat e të cilit kënaqin sistemin e ekuacioneve
| m | x = x 0 + R cos a y = y 0 + R sina, |
ku një O = 2 x 2 i+1 +2y 2 i+1 +4x i+1 -2y i+1 +3-2R 2 = 2(x i+1) 2 +2y i 2 +4(x i+1)-2y i+3-2R 2 = D i +4x i +6.
D i+1 [me y i+1 = y i-1] = 2x 2 i+1 +2y 2 i+1 +4x i+1 -2y i+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 i +4(x i-y i)+10. Tani që kemi marrë shprehjen e përsëritur për D i+1 nëpërmjet D i, mbetet për të marrë D 1 (vlera e kontrollit në pikën fillestare.) Nuk mund të merret në mënyrë periodike, sepse vlera e mëparshme nuk është e përcaktuar, por mund të gjendet lehtësisht drejtpërdrejt. x 1 = 0, y 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. Kështu, algoritmi i ndërtimit të rrethit i zbatuar në bres_circle bazohet në përzgjedhjen sekuenciale të pikave; në varësi të shenjës së vlerës së kontrollit D i zgjidhet pika tjetër dhe sipas nevojës ndryshohet vetë vlera e kontrollit. Procesi fillon në pikën (0, r), dhe pika e parë e vendosur nga procedura sim ka koordinata ( xc, yc+r). Në x = y procesi përfundon. Nëse hapësira është jodiskrete, atëherë përse Akili e kapërcen breshkën? Nëse hapësira është diskrete, atëherë si e zbatojnë grimcat algoritmin e Bresenhamit? Unë kam qenë prej kohësh duke menduar se si është Universi në tërësi dhe ligjet e punës së tij në veçanti. Ndonjëherë përshkrimet e disa fenomeneve fizike në Wikipedia janë mjaft konfuze për të mbetur të pakuptueshme edhe për një person që nuk është shumë larg kësaj fushe. Për më tepër, isha i pafat me njerëz si unë - ata që ishin të paktën shumë larg kësaj zone. Megjithatë, si programues, ndeshem me një plan paksa të ndryshëm - algoritme - pothuajse çdo ditë. Dhe një ditë, në procesin e zbatimit të një lloji të fizikës 2D në tastierë, mendova: "Por Universi është në thelb e njëjta tastierë me dimension të panjohur. A ka ndonjë arsye për të menduar se për lëvizjen lineare në ekranin e kësaj tastierë, si të thuash, grimcat nuk duhet të zbatojnë algoritmin Bresenham? Dhe duket se nuk ka asnjë arsye. Kushdo që është i interesuar se çfarë është algoritmi Bresenham, si mund të lidhet me fizikën dhe si mund të ndikojë kjo në interpretimin e tij - mirë se vini në mace. Ndoshta aty do të gjeni konfirmim indirekt të ekzistencës së Universeve paralele. Ose edhe Universe të folezuara brenda njëri-tjetrit. Algoritmi i BresenhamitMe fjalë të thjeshta, për të vizatuar një vijë të trashë një qelizë në një fletë fletore me kuadrate, do t'ju duhet të pikturoni mbi qeliza të njëpasnjëshme që qëndrojnë në një rresht. Le të supozojmë se rrafshi i fletës së fletores është diskret në qeliza, domethënë, nuk mund të pikturosh dy gjysma ngjitur të qelizave ngjitur dhe të thuash se e keni pikturuar një qelizë me një zhvendosje prej 0,5, sepse diskrete do të thotë që një veprim i tillë nuk lejohet. Kështu, duke pikturuar në mënyrë sekuenciale qelizat në një rresht, do të merrni një segment të gjatësisë së dëshiruar. Tani imagjinoni që ju duhet ta rrotulloni atë 45 gradë në çdo drejtim - tani do t'i pikturoni qelizat diagonalisht. Në thelb, ky është përdorimi i aplikuar nga truri ynë i dy funksioneve të thjeshta:F(x) = 0 F(x) = x F(x) = x * tan(55) Ky agloritëm u zhvillua nga Jack Bresenham në vitin 1962, kur ai punoi në IBM. Përdoret ende për të implementuar grafikë virtuale në shumë sisteme aplikacionesh dhe sistemesh, nga pajisjet e prodhimit te OpenGL. Duke përdorur këtë algoritëm, është e mundur të llogaritet përafrimi më i përshtatshëm për një vijë të caktuar në një nivel të caktuar të diskretitetit të planit në të cilin ndodhet kjo linjë. Zbatimi në Javascript për rastin e përgjithshëm var barazim = (x, y) => ( ... ); // funksioni për vizatimin e një pike var bresenham = (xs, ys) => ( // xs, ys janë vargje dhe, në përputhje me rrethanat, le të deltaX = xs - xs, deltaY = ys - ys, gabim = 0, deltaGabim = deltaY, y = ys për (le x = xs; x<= xs; x++) {
draw(x, y);
error += deltaError;
if ((2 * error) >= deltaX) ( y -= 1; gabim -= deltaX; ); ); ); Tani imagjinoni që hapësira që na rrethon është ende diskrete. Për më tepër, nuk ka rëndësi nëse është e mbushur me asgjë, grimca, bartës, fusha Higgs apo diçka tjetër - ekziston një koncept i caktuar sasi minimale hapësirë, më pak se e cila asgjë nuk mund të jetë. Dhe nuk ka rëndësi nëse është relative dhe nëse teoria e relativitetit është e vërtetë në lidhje me të - nëse hapësira është e lakuar, atëherë lokalisht ku është e lakuar, ajo do të jetë prapë diskrete, edhe nëse nga një pozicion tjetër mund të duket sikur ka ishte një ndryshim në të njëjtën gjë pragu minimal në çdo drejtim. Me këtë supozim, rezulton se një fenomen, ose entitet, ose rregull duhet të zbatojë algoritmin Bresenham për çdo lloj lëvizjeje të grimcave të materies dhe bartësve të ndërveprimeve. Në një farë mase, kjo shpjegon kuantizimin e lëvizjes së grimcave në mikrobotë - ato në thelb nuk mund të lëvizin në mënyrë lineare pa "teleportuar" nga një pjesë e hapësirës në një pjesë tjetër, sepse atëherë rezulton se hapësira nuk është aspak diskrete. Një tjetër konfirmim indirekt i diskretitetit të hapësirës mund të jetë një gjykim i bazuar në sa më sipër: nëse, me një ulje të caktuar të shkallës së vëzhguar, humbet aftësinë për t'u përshkruar duke përdorur gjeometrinë Euklidiane, atëherë është e qartë se kur distanca minimale pragu është kapërcyer, metoda duhet të ketë ende një temë. Në një gjeometri të tillë, një drejtëz paralele mund të korrespondojë me më shumë se një drejtëz tjetër që kalon nëpër një pikë që nuk i përket vijës origjinale, ose në një gjeometri të tillë nuk ekziston fare koncepti i paralelizmit të drejtëzave apo edhe koncepti i vijave, por ekziston ndonjë metodë hipotetike e imagjinueshme për përshkrimin e gjeometrisë së një objekti më të vogël se gjatësia minimale. Dhe, siç e dini, ekziston një teori që pretendon se është në gjendje të përshkruajë një gjeometri të tillë brenda një pragu minimal të njohur. Kjo është teoria e fijeve. Ai presupozon ekzistencën diçka, atë që shkencëtarët i quajnë vargjet ose branes, në dimensione 10/11/26 njëherësh, në varësi të interpretimit dhe modeli matematik. Mua personalisht më duket se gjërat janë përafërsisht kështu dhe për të vërtetuar fjalët e mia, do të bëj një eksperiment mendimi me ju: në një plan dydimensional, me gjeometrinë e tij plotësisht "Euklidiane", funksionon rregulli i përmendur tashmë: përmes një pikë mund të vizatoni vetëm një vijë të drejtë paralele me atë të dhënë. Tani ne e shkallëzojmë këtë rregull me hapësirë tredimensionale dhe marrim dy rregulla të reja që dalin prej saj:
Universe paralele dhe të mbivendosura?Mund të rezultojë se filozofët e lashtë që panë sjelljen në modelin atomik trupat qiellorë dhe, përkundrazi, ishin, le të themi, jo shumë më larg nga e vërteta sesa ata që pretendonin se ishte absurditet i plotë. Në fund të fundit, nëse e çlironi veten nga të gjitha llojet e njohuri dhe arsyetoni logjikisht - teorikisht, kufiri i poshtëm nuk është gjë tjetër veçse një trillim, i shpikur nga ne për të kufizuar veprimin e gjeometrisë Euklidiane të njohur për ne. Me fjalë të tjera, gjithçka që është më e vogël se gjatësia e Planck-ut, ose më saktë, të thuash kështu gjatësia reale e Plankut, thjesht nuk mund të llogaritet me metodat e gjeometrisë Euklidiane, por kjo nuk do të thotë se nuk ekziston! Mund të rezultojë se çdo branë është një grup multiversesh dhe ndodh që në rangun nga gjatësia e Plankut në X të panjohur, gjeometria e realitetit është Euklidiane, nën gjatësinë e Plankut - për shembull, gjeometria Lobachevsky ose gjeometria sferike. , ose ndonjë tjetër, dominon, pa e kufizuar fluturimin tonë në asnjë mënyrë fantazinë, dhe mbi kufirin X - për shembull, si gjeometria jo-desargeziane, ashtu edhe ajo sferike. Të ëndërrosh nuk është e dëmshme - mund të thuash, nëse jo për faktin se edhe për lëvizje kuantike, për të mos përmendur atë linear (i cili është ende i kuantizuar në nivelin e mikrobotës), grimcat duhet të zbatojnë algoritmin Bresenham nëse hapësira është diskrete.Me fjalë të tjera, ose Akili nuk do ta arrijë kurrë breshkën, ose ne jemi në Matricë, në të gjithë Universin e vëzhgueshëm dhe fizika e famshme, ka shumë të ngjarë - vetëm një pikë në oqeanin e madh të diversitetit të mundshëm të realitetit. Algoritmi i Bresenhamit është një algoritëm që përcakton se cilat pika në një raster dydimensionale duhet të hijezohen në mënyrë që të arrihet një përafrim i ngushtë i një vije të drejtë midis dy pikave të dhëna. Segmenti vizatohet ndërmjet dy pikave - (x0,y0) dhe (x1,y1), ku në këto çifte tregohen përkatësisht kolona dhe rreshti, numrat e të cilave rriten djathtas dhe poshtë. Së pari do të supozojmë se vija jonë shkon poshtë dhe djathtas, dhe distanca horizontale x1 − x0 e kalon distancën vertikale y1 − y0, d.m.th. pjerrësia e vijës nga horizontali është më pak se 45°. Qëllimi ynë është që, për secilën kolonë x midis x0 dhe x1, të përcaktojmë se cili rresht i y është më afër vijës dhe të vizatojmë një pikë (x,y). Formula e përgjithshme linjat midis dy pikave: Meqenëse e dimë kolonën x, rreshti y fitohet duke rrumbullakosur në një numër të plotë vlerën tjetër:
Megjithatë, nuk ka nevojë të llogaritet vlera e saktë e kësaj shprehjeje. Mjafton të theksohet se y rritet nga y0 dhe për çdo hap shtojmë një në x dhe shtojmë vlerën e pjerrësisë në y
të cilat mund të llogariten paraprakisht. Për më tepër, në çdo hap bëjmë një nga dy gjërat: ose mbajmë të njëjtin y, ose e rrisim atë me 1. Cila nga këto të dyja për të zgjedhur mund të vendoset duke ndjekur vlerën e gabimit, që do të thotë distancën vertikale ndërmjet vlera aktuale y dhe vlerën e saktë y për rrymën x. Sa herë që rrisim x, e rrisim vlerën e gabimit me sasinë e pjerrësisë s të dhënë më sipër. Nëse gabimi është më i madh se 0,5, vija është më afër y-së së ardhshme, kështu që ne e rrisim y me një ndërsa e zvogëlojmë vlerën e gabimit me 1. Në zbatimin e algoritmit më poshtë, grafiku (x,y) vizaton një pikë dhe abs kthehet vlerë absolute numrat: funksionin rreshti (x0, x1, y0, y1) ndër deltax:= abs (x1 - x0) ndër deltay:= abs (y1 - y0) reale gabim: = 0 reale deltaerr:= deltay / deltax ndër y:=y0 për x nga x0 te x1 gabim:= gabim + deltaerr nëse gabim >= 0.5 gabim:= gabim - 1.0 Le të ketë fillimi i segmentit koordinata (X 1,Y 1), dhe fundi (X 1,X 2). Le të shënojmë Dx=(X 2 -X 1),dy=(Y 2 -Y 1) . Pa humbur përgjithësinë, do të supozojmë se fillimi i segmentit përkon me origjinën e koordinatave, dhe vija e drejtë ka formën Ku. Ne besojmë se pikënisjeështë në të majtë. Le të jetë në hapin (i-1)-të pika aktuale e segmentit P i -1 =(r,q) . Zgjedhja e pikës tjetër S i ose T i varet nga shenja e diferencës (s-t). Nëse (s-t)<0 , то P i =T i =(r+1,q) и тогда X i +1 =i+1;Y i +1 =Y i , nëse (s-t)≥0, atëherë P i =T i =(r+1,q+1) dhe pastaj X i +1 =i+ 1 ; Y i +1 =Y i +1 ; dx=(s-t)=2(rdy-qdx)+2dy –dx Meqenëse shenja e dx=(s-t) përkon me shenjën e ndryshimit, do të kontrollojmë shenjën e shprehjes d i =dx(s-t). . Meqenëse r=X i -1 dhe q=Y i -1, atëherë d i +1 = d i +2dy -2dx(y i -y i -1) . Le në hapin e mëparshëm 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) Mbetet për të gjetur se si të llogaritet d i. Meqenëse për i=1 Procedura Bresenham(x1,y1,x2,y2,Ngjyra: numër i plotë); dx,dy,incr1,incr2,d,x,y,xend: numër i plotë; dx:= ABS (x2-x1); dy:= Abs(y2-y1); d:=2*dy-dx; (vlera fillestare për d) incr1:=2*dy; (rritje për d<0} incr2:=2*(dy-dx); (rritje për d>=0) nëse x1>x2 atëherë (filloni nga pika me vlerën më të vogël x) PutPixel (x, y, Ngjyra); (pika e parë e segmentit) Ndërsa x d:=d+incr1 (zgjidhni pikën e poshtme) d:=d+incr2; (zgjidhni pikën e sipërme, y-rritet) PutPixel (x, y, Ngjyra); 26. Algoritmi i Përgjithshëm Bresenham.
Algoritmi zgjedh koordinatat optimale raster për të përfaqësuar segmentin. Më i madhi i rritjeve, ose Δx ose Δy, zgjidhet si njësi raster. Gjatë funksionimit, një nga koordinatat - ose x ose y (në varësi të pjerrësisë) - ndryshon me një. Ndryshimi i një koordinate tjetër (në 0 ose 1) varet nga distanca midis pozicionit aktual të segmentit dhe koordinatave më të afërta të rrjetit. Kjo distancë është një gabim. Algoritmi është ndërtuar në atë mënyrë që ju duhet të dini vetëm shenjën e këtij gabimi. Rrjedhimisht, pika raster (1, 1) përafron më mirë rrjedhën e segmentit sesa pika (1, 0). Nëse pjerrësia është më e vogël se ½, atëherë e kundërta është e vërtetë. Për një pjerrësi prej ½, nuk ka zgjedhje të preferuar. Në këtë rast, algoritmi zgjedh pikën (1, 1). Meqenëse është e dëshirueshme të kontrollohet vetëm shenja e gabimit, fillimisht është vendosur në -½. Kështu, nëse pjerrësia e segmentit është më e madhe ose e barabartë me ½, atëherë vlera e gabimit në pikën tjetër raster mund të llogaritet si e = -½ + Δy/Δx. Në mënyrë që zbatimi i algoritmit Bresenham të jetë i plotë, është e nevojshme të përpunohen segmentet në të gjitha oktantet. Kjo është e lehtë për t'u bërë, duke marrë parasysh në algoritëm numrin e kuadrantit në të cilin shtrihet segmenti dhe koeficientin e tij këndor. Kur vlera absolute e pjerrësisë është më e madhe se 1, y ndryshohet vazhdimisht me një, dhe kriteri i gabimit Bresenham përdoret për të vendosur nëse do të ndryshohet vlera e x. Zgjedhja e një koordinate që ndryshon vazhdimisht (+1 ose -1) varet nga kuadranti
var x,y,sy,sx,dx,dy,e,z,i: Integer; 27. Algoritmi Bresenham për gjenerimin e një rrethi
Rasteri duhet të zgjerohet si funksione lineare dhe të tjera, më komplekse. Shpërndarja e prerjeve terminale, të tilla si keels, elipses, parabola, hiperbola, iu caktua numrit të robotëve. Me respektin më të madh, kuptohet, është shtuar një aksion. Një nga algoritmet më efikase dhe më të lehta për t'u kuptuar është ai i Bresenham. Për kallirin, është e rëndësishme të gjenerohet vetëm një e teta e një kunji. Këto pjesë mund të hiqen me rrahje të njëpasnjëshme. Pasi të krijohet oktanti i parë (nga 0 në 45 ° të shigjetës anti-vit), atëherë oktanti tjetër mund të shprehet si një imazh pasqyrë i vijës së drejtë y = x, e cila së bashku jep kuadrantin e parë. Kuadranti i parë goditet drejt x = 0 për të hequr pjesën mbështetëse të kunjit nga kuadrati tjetër. Pjesa e sipërme rrëzohet drejt në = 0 për të përfunduar detyrën. Për të treguar algoritmin, le të shohim një të katërtën e një kunji të përqendruar në kallirin e koordinatave. Ju lutemi vini re se meqenëse algoritmi fillon në pikën x = 0, y = R, atëherë kur gjenerohet një rreth prapa shigjetës së vitit në katrorin e parë, y është funksion zbritës monoton i argumenteve. Në mënyrë të ngjashme, nëse pika e daljes është y = 0, x == R, atëherë kur gjenerohet një rreth përballë shigjetës x do të jetë një funksion monotonik në rënie të argumentit y. Në rastin tonë, zgjidhet gjenerata pas shigjetës së vitit me kalli në pikën x = 0, y = R Transferohet që qendra e kunjit dhe pika e kallirit janë pikërisht në pikat raster. Për çdo pikë të caktuar në rreth kur gjenerohet pas shigjetës së vitit, ekzistojnë vetëm tre opsione për zgjedhjen e pikselit tjetër, rrethit më të afërt: horizontalisht në të djathtë, diagonalisht poshtë dhe në të djathtë, vertikalisht poshtë. Algoritmi zgjedh një piksel për të cilin katrori minimal është ndërmjet njërit prej atyre pikselëve dhe rrethit. 28. Koncepti i një fraktali. Historia e grafikës fraktal
Në jetën e përditshme, shpesh mund të vëzhgoni imazhe (modele) që, me sa duket, nuk mund të përshkruhen matematikisht. Shembull: dritaret ngrijnë në dimër, mund të përfundoni duke vëzhguar figurën. Komplete të tilla quhen fraktal. Fraktalet nuk janë të ngjashme me figurat e njohura nga gjeometria dhe ato ndërtohen sipas algoritmeve të caktuara që mund të zbatohen në kompjuter. E thënë thjesht, një fraktal është një imazh që rezulton nga disa transformime të aplikuara në mënyrë të përsëritur në formën origjinale. Një fraktal është një figurë gjeometrike e përbërë nga pjesë dhe e cila mund të ndahet në pjesë, secila prej të cilave do të përfaqësojë një kopje më të vogël të së tërës. Vetia kryesore e fraktaleve është vetëngjashmëria, d.m.th. çdo fragment i një fraktali në një mënyrë ose në një tjetër riprodhon strukturën e tij globale. Fraktalet ndahen në sisteme gjeometrike, algjebrike, stokastike dhe të funksioneve të përsëritura. 29. Koncepti i dimensionit dhe llogaritja e tij
Në jetën tonë të përditshme ne vazhdimisht hasim dimensione. Ne vlerësojmë gjatësinë e rrugës, zbulojmë sipërfaqen e banesës, etj. Ky koncept është mjaft intuitiv dhe, me sa duket, nuk kërkon sqarime. Linja ka dimensionin 1. Kjo do të thotë se duke zgjedhur një pikë referimi, ne mund të përcaktojmë çdo pikë në këtë vijë duke përdorur 1 numër - pozitiv ose negativ. Për më tepër, kjo vlen për të gjitha linjat - rrethi, katrori, parabola, etj. Dimensioni 2 do të thotë që ne mund të përcaktojmë në mënyrë unike çdo pikë me dy numra. Mos mendoni se dydimensionale do të thotë e sheshtë. Sipërfaqja e një sfere është gjithashtu dy-dimensionale (ajo mund të përcaktohet duke përdorur dy vlera - kënde si gjerësia dhe gjatësia). Nëse e shikojmë nga një këndvështrim matematikor, dimensioni përcaktohet si më poshtë: për objektet njëdimensionale, dyfishimi i madhësisë së tyre lineare çon në një rritje të madhësisë (në këtë rast, gjatësisë) me një faktor prej dy (2^ 1). Për objektet dy-dimensionale, dyfishimi i dimensioneve lineare rezulton në një rritje të madhësisë (për shembull, sipërfaqja e një drejtkëndëshi) me katër herë (2^2). Për objektet 3-dimensionale, dyfishimi i dimensioneve lineare çon në një rritje tetëfish të vëllimit (2^3) e kështu me radhë. Fraktale gjeometrike Pikërisht me këto fraktale filloi historia e zhvillimit të fraktaleve në përgjithësi. Ky lloj fraktali fitohet nëpërmjet konstruksioneve të thjeshta gjeometrike. Në mënyrë tipike, kur ndërtohen fraktale gjeometrike, përdoret algoritmi i mëposhtëm: Shembuj të fraktaleve gjeometrike: kurba Peano, fjolla e borës Koch, gjethe fieri, trekëndëshi i Sierpinskit, Fraktale algjebrike Fraktal- një figurë gjeometrike komplekse që ka vetinë e vetëngjashmërisë, domethënë e përbërë nga disa pjesë, secila prej të cilave është e ngjashme me të gjithë figurën. Fraktalet algjebrike e kanë marrë emrin e tyre sepse janë ndërtuar në bazë të funksioneve algjebrike. Fraktalet algjebrike përfshijnë: grupin Mandelbrot, grupin Julia, pellgjet e Njutonit, biomorfet. -Kompleti Mandelbrot: Kompleti Mandelbrot u përshkrua për herë të parë në 1905 nga Pierre Fatou. Fatou studioi proceset rekursive të formës Duke filluar me një pikë në planin kompleks, ju mund të merrni pika të reja duke aplikuar në mënyrë të njëpasnjëshme këtë formulë për to. Një sekuencë e tillë pikash quhet një orbitë nën transformim Fatou zbuloi se orbita nën këtë transformim tregon sjellje mjaft komplekse dhe interesante. Ekziston një numër i pafund i transformimeve të tilla - një për secilën vlerë. (i quajtur Mandelbrot sepse ishte i pari që kreu numrin e kërkuar të llogaritjeve duke përdorur një kompjuter). -set Julia: Julia grup i një harte racionale -Pishinat e Njutonit: Rajonet me kufij fraktal shfaqen kur rrënjët e një ekuacioni jolinear gjenden afërsisht nga algoritmi i Njutonit në një plan kompleks (për një funksion të një ndryshoreje reale, metoda e Njutonit shpesh quhet metoda tangjente, e cila, në këtë rast, përgjithësohet në rrafshin kompleks). Le të zbatojmë metodën e Njutonit për të gjetur zeron e një funksioni të një ndryshoreje komplekse duke përdorur procedurën: Zgjedhja e përafrimit fillestar është me interes të veçantë. Sepse një funksion mund të ketë zero të shumta dhe në raste të ndryshme metoda mund të konvergojë në vlera të ndryshme. -biomorfe: forma e shkurtuar e bashkësisë Julia, e llogaritur me formulën z=z 3 +c. Ajo mori emrin e saj për shkak të ngjashmërisë së saj me organizmat njëqelizore. Fraktale stokastike Një përfaqësues tipik i këtij lloji të fraktalit është i ashtuquajturi plazma. Për ta ndërtuar atë, merrni një drejtkëndësh dhe përcaktoni një ngjyrë për çdo cep të tij. Më pas, gjeni pikën qendrore të drejtkëndëshit dhe lyejeni atë me një ngjyrë të barabartë me mesataren aritmetike të ngjyrave në qoshet e drejtkëndëshit + një numër të rastësishëm. Sa më i madh ky numër i rastësishëm, aq më i grisur do të jetë vizatimi. Objektet natyrore shpesh kanë një formë fraktale. Për modelimin e tyre mund të përdoren fraktale stokastike (të rastësishme). Shembuj të fraktaleve stokastike: trajektorja e lëvizjes Brownian në aeroplan dhe në hapësirë; kufiri i trajektores së lëvizjes Brownian në një aeroplan. Në vitin 2001, Lawler, Schramm dhe Werner vërtetuan hipotezën e Mandelbrot se dimensioni i tij është 4/3. Evolucionet e Schramm-Löwner janë kthesa fraktale konformale të pandryshueshme që lindin në modelet kritike dy-dimensionale të mekanikës statistikore, për shembull, modeli Ising dhe perkolimi. lloje të ndryshme fraktalesh të rastësishme, domethënë fraktale të marra duke përdorur një procedurë rekursive në të cilën futet një parametër i rastësishëm në çdo hap. Plazma është një shembull i përdorimit të një fraktal të tillë në grafikën kompjuterike. Monotipi fraktal, ose stokatipia, është një prirje në artin e bukur që përfshin marrjen e një imazhi të një fraktali të rastësishëm. Informacione të lidhura. |
- një grup pikash, dinamika në afërsi të të cilave është, në një farë kuptimi, e paqëndrueshme në lidhje me shqetësimet e vogla të pozicionit fillestar. Në rast f- një polinom, ne konsiderojmë gjithashtu një grup të mbushur Julia - një grup pikash që nuk priren në pafundësi. Seti i zakonshëm Julia është kufiri i tij.
