Į ką tu dabar žiūri? Jei nesate iš paralelinė visata, kur visi sėdi už vektorinių monitorių, tada priešais jus rastrinis vaizdas. Pažvelkite į šią juostelę: /. Jei priartėsite prie monitoriaus, pamatysite pikselių pavidalo žingsnius, kurie bando apsimesti vektorine linija. Tam tikslui yra visa krūva įvairių rastrizacijos algoritmų, bet norėčiau pakalbėti apie Bresenham algoritmą ir Y algoritmą, kurie rastro koordinatėse randa vektorinio segmento aproksimaciją.
Su rastravimo problema susidūriau dirbdamas su procedūriniu pastatų planų generatoriumi. Man reikėjo pavaizduoti kambario sienas kaip dvimačio masyvo ląsteles. Panašios problemos gali kilti atliekant fizikinius skaičiavimus, kelio paieškos algoritmus ar apšvietimą, jei naudojamas erdvės padalijimas. Kas galėjo pagalvoti, kad susipažinimas su rastrizacijos algoritmais vieną dieną gali praversti?
Bresenhamo algoritmo veikimo principas labai paprastas. Paimkite atkarpą ir jo pradinę koordinatę x. Prie x ciklo pabaigoje pridedame po vieną. Kiekviename žingsnyje apskaičiuojama paklaida – atstumas tarp realios koordinatės yšioje vietoje ir artimiausiame tinklelio langelyje. Jei paklaida neviršija pusės langelio aukščio, tada ji užpildoma. Tai yra visas algoritmas.
Tai buvo algoritmo esmė, iš tikrųjų viskas atrodo taip. Pirmiausia apskaičiuojamas nuolydis (y1 - y0) / (x1 - x0). Klaidos reikšmė atkarpos pradžios taške (0,0) priimtas lygus nuliui ir pirmoji ląstelė užpildoma. Kitame žingsnyje nuolydis pridedamas prie klaidos ir analizuojama jo reikšmė, jei paklaida mažesnė 0.5 , tada langelis užpildomas (x0+1, y0), jei daugiau, tada langelis užpildomas (x0+1, y0+1) ir vienas atimamas iš klaidos reikšmės. Žemiau esančiame paveikslėlyje geltona rodoma linija prieš rastravimą, žalia ir raudona - atstumas iki artimiausių langelių. Nuolydis lygus vienai šeštajai, pirmame žingsnyje paklaida tampa lygi nuolydžiui, kuris yra mažesnis 0.5 , o tai reiškia, kad ordinatė išlieka ta pati. Link linijos vidurio klaida kerta liniją, iš jos atimama viena, o naujas pikselis pakyla aukščiau. Ir taip iki segmento pabaigos.
Dar vienas niuansas. Jei atkarpos projekcija į ašį x mažesnė projekcija ašyje y arba segmento pradžia ir pabaiga yra sukeisti, tada algoritmas neveiks. Kad taip neatsitiktų, reikia patikrinti vektoriaus kryptį ir jo nuolydį, o tada, jei reikia, sukeisti atkarpos koordinates, pasukti ašis ir galiausiai viską sumažinti iki vieno ar bent dviejų atvejų. Svarbiausia nepamiršti grąžinti kirvių į savo vietą piešimo metu.
Norėdami optimizuoti skaičiavimus, naudokite visus trupmeninius kintamuosius padauginus iš dx = (x1 - x0). Tada kiekviename žingsnyje klaida pasikeis į dy = (y1 - y0) vietoj nuolydis ir toliau dx vietoj vieno. Taip pat galite šiek tiek pakeisti logiką, „perkelti“ klaidą taip, kad riba būtų lygi nuliui, ir galite patikrinti klaidos ženklą.
Rastrinės linijos braižymo naudojant Bresenham algoritmą kodas gali atrodyti maždaug taip. Pseudokodas iš Vikipedijos konvertuotas į C#.
void BresenhamLine(int x0, int y0, int x1, int y1) ( var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // Patikrinkite segmento augimą išilgai x ašies ir išilgai y ašies / / Atspindėkite liniją įstrižai, jei pasvirimo kampas per didelis, jei (status) ( Swap(ref x0, ref y0); // Koordinatės maišomos atskira funkcija for beauty 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;
}
}
}
) // Jei linija neauga iš kairės į dešinę, tada atkarpos pradžią ir pabaigą keičiame, jei (x0 > x1) ( Swap(ref x0, ref x1); Swap(ref y0, ref y1); ) int dx = x1 - x0;
int dy = Math.Abs(y1 - y0);
int klaida = dx / 2; // Tam naudojamas optimizavimas su daugyba iš dx, kad būtų pašalintos papildomos trupmenos int ystep = (y0< 0) { radiusError += 2 * y + 1; } else { x--; radiusError += 2 * (y - x + 1); } } }
Dabar apie Wu Xiaolin algoritmą lygioms linijoms piešti. Jis skiriasi tuo, kad kiekviename žingsnyje apskaičiuojamas du arčiausiai linijos esantys pikseliai ir jie nudažomi skirtingu intensyvumu, priklausomai nuo atstumo. Tiksliai kertant pikselio vidurį gaunamas 100% intensyvumas, jei pikselis yra 0,9 pikselio atstumu, tada intensyvumas bus 10%. Kitaip tariant, šimtas procentų intensyvumo yra padalintas tarp pikselių, kurie riboja vektoriaus liniją iš abiejų pusių.
Aukščiau esančiame paveikslėlyje raudona ir žalias rodomi atstumai iki dviejų gretimų pikselių.
Norėdami apskaičiuoti klaidą, galite naudoti slankiojo kablelio kintamąjį ir paimti klaidos reikšmę iš trupmeninės dalies.
Wu Xiaolin sklandžios linijos pavyzdys C#.
private void WuLine(int x0, int y0, int x1, int y1) ( var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); if (staetus) ( Swap(ref x0, ref y0) ); Ši funkcija automatiškai pakeičia koordinates, priklausomai nuo kintamojo steep DrawPoint(steep, x1, y1, 1) plūduriuoti y = y0 + gradientas (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;
}
}
Jei kada nors ateityje dirbsite su tinkleliu, trumpam pagalvokite, galbūt išradinėjate ratą iš naujo ir iš tikrųjų dirbate su pikseliais, nors to nežinote. Šių algoritmų modifikacijos gali būti naudojamos žaidimuose ieškant langelių prieš vienetą žemėlapyje, apskaičiuoti kadro smūgio plotą arba gražiai išdėstyti objektus. Arba galite tiesiog nubrėžti linijas, kaip nurodyta programoje iš toliau pateiktų nuorodų.
Didelė mokyklos geometrijos kurso dalis yra skirta statybos problemoms spręsti. Senovės matematikus domino klausimai, susiję su geometrinių figūrų konstravimo algoritmais. Vėlesni tyrimai parodė jų glaudų ryšį su esminiais matematikos klausimais (pakanka prisiminti klasikines kampo trišakos ir apskritimo kvadratūros problemas). Kompiuterių atsiradimas matematikams kėlė iš esmės naujų klausimų, kurių negalėjo kilti ikikompiuterinėje eroje. Tai apima elementarių grafinių objektų – linijų ir apskritimų konstravimo užduotis.
Bet kurią geometrinę figūrą galima apibrėžti kaip taškų rinkinį plokštumoje. Geometrijoje ši aibė, kaip taisyklė, yra begalinė; net atkarpoje yra be galo daug taškų.
Kompiuterinėje grafikoje situacija kitokia. Elementarioji visų figūrų sudedamoji dalis – taškas – įgyja realius fizinius matmenis, o tokie klausimai kaip „kiek taškų turi ši figūra? niekas nesistebi. Atsiduriame baigtiniame pasaulyje, kuriame viską galima palyginti, išmatuoti, suskaičiuoti. Net pats žodis „taškas“ vartojamas retai. Jis pakeičiamas terminu pikselis (pikselis – iš paveikslėlio elemento – paveikslo elementas). Jei pažvelgsite į ekraną per didinamąjį stiklą, pamatysite, kad vaizdo fragmentas, kuris plika akimi atrodo vientisas, iš tikrųjų susideda iš atskiro pikselių rinkinio. Tačiau mažos skiriamosios gebos ekranuose tai galima pastebėti be didinamojo stiklo.
Pikselio negalima padalinti, nes tai yra minimalus vaizdo elementas – nėra tokio dalyko kaip „du su puse pikselių“. Taigi kompiuterinėje grafikoje iš tikrųjų turime sveikųjų skaičių koordinačių tinklelį, kurio mazguose dedami taškai. Visi algoritmai, aptarnaujantys kompiuterinę grafiką, turi atsižvelgti į šią aplinkybę.
Yra ir kitas problemos aspektas. Tarkime, kad norite suvalgyti obuolį. Ar jums svarbu, ar valgysite visą obuolį, ar padalinsite jį į dvi dalis ir valgysite kiekvieną atskirai? Greičiausiai, jei obuolys pakankamai skanus, noriai sutiksite su abiem variantais. Tačiau programuotojo požiūriu, jei gražų visą obuolį padalijate per pusę, darote didžiulę klaidą. Galų gale, vietoj nuostabaus sveikojo skaičiaus, jūs turite susidoroti su dviem trupmenomis, o tai yra daug blogiau. Dėl tos pačios priežasties iš dviejų lygčių 1 + 1 = 2 ir 1,5 + 0,5 = 2 programuotojas visada pasirinks pirmąją – nes joje nėra šių nemalonių trupmeninių skaičių. Šis pasirinkimas yra susijęs su programų efektyvumo didinimu. Mūsų atveju, kalbant apie elementarių grafinių objektų, reikalaujančių pakartotinio naudojimo, konstravimo algoritmus, efektyvumas yra privalomas reikalavimas. Dauguma mikroprocesorių turi tik sveikųjų skaičių aritmetiką ir neturi integruotų galimybių operacijoms su realiais skaičiais. Žinoma, tokios operacijos yra įgyvendinamos, tačiau pasitaiko, kad vienai operacijai kompiuteris turi įvykdyti iki keliolikos ar daugiau komandų, o tai labai įtakoja algoritmų vykdymo laiką.
Straipsnis skirtas vienam iš programavimo meno šedevrų – Brezenhamo pasiūlytam apskritimo konstravimo algoritmui – aptarti. Būtina sukurti metodą, kaip sudaryti apskritimą ant sveikųjų koordinačių tinklelio, naudojant centro ir spindulio koordinates. Taip pat turime kiek įmanoma sumažinti algoritmo vykdymo laiką, o tai verčia mus, kai tik įmanoma, veikti su sveikaisiais skaičiais. Kokius grafinius įrankius turime? Praktiškai jokios. Žinoma, turime sugebėti įdėti tašką (pikselį) tinkamoje ekrano vietoje. Pavyzdžiui, „Borland“ programavimo kalbose yra putpixel procedūra, kurios pagalba galite palikti tašką ekrane su norimomis koordinatėmis ir spalva. Spalva mums nesvarbu, kad būtų konkreti, tegul ji būna balta.
1. Ko teks atsisakyti...
Įsivaizduokime, kad mūsų lėšos nėra ribotos. Kad galime operuoti ne tik trupmeniniais skaičiais, bet ir naudoti transcendentines trigonometrines funkcijas (tai, beje, visiškai įmanoma mašinose, kuriose yra matematinis koprocesorius, kuris imasi tokių skaičiavimų). Užduotis vis dar ta pati – sukurti ratą. Ką darysime? Tikriausiai prisiminsime formules, kurios parametriškai nustato apskritimą. Šios formulės yra gana paprastos ir jas galima gauti tiesiogiai iš trigonometrinių funkcijų apibrėžimo. Pagal juos spindulio ratas R su centru taške ( x 0 , y 0) galima apibrėžti kaip taškų rinkinį M(x, y), kurių koordinatės tenkina lygčių sistemą
| m | x = x 0 + R cos a y = y 0 + R sina, |
kur a 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 [su 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. Dabar, kai gavome pasikartojančią D išraišką i+1 per D i, belieka gauti D 1 (kontrolinę reikšmę pradiniame taške.) Jo negalima gauti pakartotinai, nes ankstesnė reikšmė nėra apibrėžta, bet ją galima lengvai rasti tiesiogiai 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. Taigi bres_circle realizuotas apskritimo konstravimo algoritmas pagrįstas nuosekliu taškų parinkimu; priklausomai nuo kontrolinės vertės ženklo D i parenkamas kitas taškas ir pagal poreikį pakeičiama pati valdymo reikšmė. Procesas prasideda taške (0, r), o pirmasis taškas, nustatytas sim procedūra, turi koordinates ( xc, yc+r). At x = y procesas baigiasi. Jei erdvė nėra atskira, kodėl Achilas aplenkia vėžlį? Jei erdvė yra diskreti, tai kaip dalelės įgyvendina Bresenhamo algoritmą? Ilgai galvojau apie tai, kokia yra Visata kaip visuma ir konkrečiai jos veikimo dėsniai. Kartais kai kurių fizinių reiškinių aprašymai Vikipedijoje yra gana painūs, kad liktų nesuprantami net žmogui, kuris nėra labai toli nuo šios srities. Be to, man nepasisekė su tokiais kaip aš – tais, kurie buvo bent jau labai toli nuo šios srities. Tačiau, kaip programuotojas, kone kasdien susiduriu su kiek kitokia plokštuma – algoritmais. Ir vieną dieną, diegdamas kažkokią 2D fiziką konsolėje, pagalvojau: „Bet Visata iš esmės yra ta pati nežinomo matmens konsolė. Ar yra pagrindo manyti, kad linijiniam judėjimui šios konsolės ekrane, taip sakant, dalelės neturėtų įgyvendinti Bresenham algoritmo? Ir atrodo, kad nėra jokios priežasties. Visi, kas domisi, kas yra Bresenham algoritmas, kaip jis gali būti susijęs su fizika ir kaip tai gali paveikti jo interpretaciją – sveiki atvykę į katę. Galbūt ten rasite netiesioginį paralelinių Visatų egzistavimo patvirtinimą. Arba net visatos yra viena kitos viduje. Bresenhamo algoritmasPaprastais žodžiais tariant, norėdami languotame bloknoto lape nubrėžti vienos ląstelės storio liniją, turėsite nupiešti iš eilės stovinčias ląsteles. Tarkime, kad bloknoto lapo plokštuma langeliuose yra diskreti, tai yra, negalima nudažyti dviejų gretimų gretimų langelių pusių ir sakyti, kad nudažėte langelį su poslinkiu 0,5, nes diskretiškumas reiškia, kad toks veiksmas neleidžiamas. Taigi, nuosekliai dažydami ląsteles iš eilės, gausite norimo ilgio segmentą. Dabar įsivaizduokite, kad reikia pasukti 45 laipsnių kampu bet kuria kryptimi – dabar ląsteles dažysite įstrižai. Iš esmės tai yra tai, kad mūsų smegenys naudoja dvi paprastas funkcijas:F(x) = 0 F(x) = x F(x) = x * įdegis (55) Šį aglorytmą sukūrė Jackas Bresenhamas 1962 m., kai dirbo IBM. Jis vis dar naudojamas virtualiai grafikai įdiegti daugelyje programų ir sistemų sistemų, nuo gamybos įrangos iki OpenGL. Naudojant šį algoritmą, galima apskaičiuoti tinkamiausią tam tikros linijos aproksimaciją esant tam tikram plokštumos, kurioje yra ši linija, diskretiškumo lygiu. Įdiegimas Javascript bendruoju atveju var draw = (x, y) => ( ... ); // taško piešimo funkcija var bresenham = (xs, ys) => ( // xs, ys yra masyvai ir atitinkamai tegul deltaX = xs - xs, deltaY = ys - ys, klaida = 0, deltaError = deltaY, y = ys ; for (tegul x = xs; x<= xs; x++) {
draw(x, y);
error += deltaError;
if ((2 * error) >= deltaX) ( y -= 1; klaida -= deltaX; ); ); ); Dabar įsivaizduokite, kad mus supanti erdvė vis dar yra atskira. Be to, nesvarbu, ar jis užpildytas niekuo, dalelėmis, nešikliais, Higso lauku ar dar kažkuo - yra tam tikra koncepcija minimalus kiekis erdvė, už kurios nieko negali būti. Ir nesvarbu, ar tai reliatyvu ir ar reliatyvumo teorija yra teisinga, jei erdvė yra išlenkta, tai lokaliai, kur ji yra išlenkta, ji vis tiek bus diskretiška, net jei iš kitos pozicijos gali atrodyti, kad buvo to paties pokytis minimali riba bet kuria kryptimi. Remiantis šia prielaida, paaiškėja, kad koks nors reiškinys, subjektas ar taisyklė turi įgyvendinti Bresenhamo algoritmą bet kokiam medžiagos dalelių ir sąveikos nešėjų judėjimui. Tam tikru mastu tai paaiškina dalelių judėjimo mikropasaulyje kvantavimą - jos iš esmės negali judėti linijiškai, „neteleportuodamos“ iš erdvės gabalo į kitą, nes tada paaiškėja, kad erdvė visai nėra diskreti. Kitas netiesioginis erdvės diskretiškumo patvirtinimas gali būti sprendimas, pagrįstas tuo, kas išdėstyta aukščiau: jei, tam tikru mastu sumažinus stebimo mastelį, ji praranda galimybę aprašyti naudojant euklido geometriją, tada akivaizdu, kad kai minimalus atstumas slenkstis peržengtas, metodas vis tiek turi būti tema. Tegul tokioje geometrijoje viena lygiagreti tiesė gali atitikti daugiau nei vieną kitą tiesę, einančią per tašką, nepriklausantį pradinei tiesei, arba tokioje geometrijoje nėra tiesių lygiagretumo sampratos ar net tiesių sampratos, bet yra bet koks hipotetiškai įsivaizduojamas metodas mažesnio už minimalų ilgį objekto geometrijai apibūdinti. Ir, kaip žinote, yra viena teorija, kuri teigia galinti apibūdinti tokią geometriją žinomos minimalios ribos ribose. Tai yra stygų teorija. Tai suponuoja egzistavimą kažkas, ką mokslininkai vadina stygomis arba branomis, iš karto 10/11/26 matmenimis, priklausomai nuo interpretacijos ir matematinis modelis. Man asmeniškai atrodo, kad viskas yra maždaug taip, ir, kad pagrįstų savo žodžius, atliksiu su jumis minties eksperimentą: dvimatėje plokštumoje, kurios geometrija yra visiškai „euklidiška“, veikia jau minėta taisyklė: per viename taške galite nubrėžti tik vieną liniją, lygiagrečią nurodytai. Dabar mes padidiname šią taisyklę pagal trimatė erdvė ir gauname du iš to kylančios naujos taisyklės:
Lygiagrečios ir įdėtos visatos?Gali pasirodyti, kad senovės filosofai, matę elgesį atominiame modelyje dangaus kūnai ir, priešingai, buvo, sakykime, ne daug toliau nuo tiesos nei tie, kurie tvirtino, kad taip yra visiška nesąmonė. Juk jei išsivaduoji nuo visokių žinių ir logiškai samprotauti – teoriškai apatinė riba yra ne kas kita, kaip fikcija, kurią mes sugalvojome apriboti mums pažįstamos euklido geometrijos veikimą. Kitaip tariant, viskas, kas yra mažesnė už Plancko ilgį, tiksliau, taip sakant tikras Plancko ilgis, tiesiog negali būti apskaičiuotas euklido geometrijos metodais, bet tai nereiškia, kad jos nėra! Gali pasirodyti, kad kiekviena brana yra multivisatų rinkinys, ir taip atsitinka, kad diapazone nuo Plancko ilgio iki nežinomo X tikrovės geometrija yra euklido, žemiau Plancko ilgio - pavyzdžiui, Lobačevskio geometrija arba sferinė geometrija. , arba koks nors kitas, dominuoja, niekaip neapribodamas mūsų skrydžio fantazijos ir virš ribos X – pavyzdžiui, tiek nedesarguziška, tiek sferinė geometrija. Sapnuoti nekenkia – galima sakyti, jei ne tai, kad net ir už kvantinis judėjimas, jau nekalbant apie linijinį (kuris vis dar kvantuojamas mikropasaulio lygmeniu), dalelės turi įgyvendinti Bresenham algoritmą, jei erdvė yra diskreti.Kitaip tariant, arba Achilas niekada nepasivys vėžlio, arba mes esame Matricoje, visoje stebimoje Visatoje ir garsioji fizika, greičiausiai – tik lašas didžiuliame galimos tikrovės įvairovės vandenyne. Bresenhamo algoritmas yra algoritmas, kuris nustato, kurie dvimačio rastro taškai turi būti užtamsinti, kad būtų galima gauti artimą tiesės tarp dviejų nurodytų taškų aproksimaciją. Atkarpa brėžiama tarp dviejų taškų – (x0,y0) ir (x1,y1), kur šiose porose atitinkamai nurodomas stulpelis ir eilutė, kurių skaičiai didėja į dešinę ir žemyn. Pirmiausia manysime, kad mūsų linija eina žemyn ir į dešinę, o horizontalus atstumas x1 − x0 viršija vertikalųjį atstumą y1 − y0, t.y. linijos nuolydis nuo horizontalės yra mažesnis nei 45°. Mūsų tikslas yra kiekvienam x stulpeliui tarp x0 ir x1 nustatyti, kuri y eilutė yra arčiausiai linijos, ir nubrėžti tašką (x, y). Bendroji formulė linijos tarp dviejų taškų: Kadangi žinome x stulpelį, y eilutė gaunama apvalinant iki sveikojo skaičiaus kitą vertę:
Tačiau nereikia skaičiuoti tikslios šios išraiškos reikšmės. Pakanka pastebėti, kad y auga nuo y0 ir kiekvienam žingsniui pridedame vieną prie x ir nuolydžio reikšmę pridedame prie y
kurią galima apskaičiuoti iš anksto. Be to, kiekviename žingsnyje darome vieną iš dviejų dalykų: arba paliekame y tą patį, arba padidiname jį 1. Kurį iš šių dviejų pasirinkti, galima nuspręsti stebint klaidos reikšmę, o tai reiškia vertikalų atstumą tarp dabartinė vertė y ir tikslią vertę y dabartinei x. Kai padidiname x, padidiname paklaidos reikšmę aukščiau nurodyto nuolydžio s dydžiu. Jei paklaida didesnė nei 0,5, linija yra arčiau kito y, todėl y padidiname vienu, o klaidos reikšmę sumažiname 1. Įgyvendinant žemiau pateiktą algoritmą, plot(x,y) nubrėžia tašką ir abs. grįžta absoliuti vertė skaičiai: funkcija eilutė (x0, x1, y0, y1) tarpt deltax:= abs(x1 - x0) tarpt deltay:= abs(y1 - y0) tikras klaida: = 0 tikras deltaerr:= deltay / deltax tarpt y:=y0 už x iš x0 į x1 klaida:= klaida + deltaerr jeigu klaida >= 0,5 klaida:= klaida – 1.0 Tegul atkarpos pradžia turi koordinates (X 1,Y 1), o pabaiga (X 1,X 2). Pažymėkime Dx=(X2-X1),dy=(Y2-Y1) . Neprarasdami bendrumo, manysime, kad atkarpos pradžia sutampa su koordinačių pradžia, o tiesė turi formą Kur. Mes tuo tikime pradžios taškas yra kairėje. Tegul (i-1) žingsnyje dabartinis atkarpos taškas yra P i -1 =(r,q) . Kito taško S i arba T i pasirinkimas priklauso nuo skirtumo (s-t) ženklo. Jei (s-t)<0 , то P i =T i =(r+1,q) и тогда X i +1 =i+1;Y i +1 =Y i , jei (s-t)≥0, tai P i =T i =(r+1,q+1) ir tada X i +1 =i+ 1 ; Y i +1 =Y i +1 ; dx=(s-t)=2(rdy-qdx)+2dy –dx Kadangi dx=(s-t) ženklas sutampa su skirtumo ženklu, tai patikrinsime reiškinio d i =dx(s-t) ženklą. . Kadangi r=X i -1 ir q=Y i -1 , tai d i +1 = d i +2dy -2dx(y i -y i -1) . Tegul ankstesniame žingsnyje 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) Belieka išsiaiškinti, kaip apskaičiuoti d i. Kadangi i=1 Procedūra Bresenham(x1,y1,x2,y2,Spalva: sveikasis skaičius); dx,dy,incr1,incr2,d,x,y,xend: sveikasis skaičius; dx:= ABS(x2-x1); dy:= Abs(y2-y1); d:=2*dy-dx; (pradinė d vertė) incr1:=2*dy; (padidėjimas už d<0} incr2:=2*(dy-dx); (padidėjimas > = 0) jei x1>x2, tada (pradėkite nuo taško su mažesne x reikšme) PutPixel(x,y,spalva); (pirmas segmento taškas) Nors x d:=d+incr1 (pasirinkite apatinį tašką) d:=d+incr2; (pasirinkite viršutinį tašką, y didėja) PutPixel(x,y,spalva); 26. Bendrasis Bresenham algoritmas.
Algoritmas parenka optimalias rastrines koordinates segmentui pavaizduoti. Didesnis iš žingsnių, arba Δx, arba Δy, pasirenkamas kaip rastro vienetas. Eksploatacijos metu viena iš koordinačių – arba x, arba y (priklausomai nuo nuolydžio) – pasikeičia vienu. Kitos koordinatės keitimas (į 0 arba 1) priklauso nuo atstumo tarp tikrosios atkarpos padėties ir artimiausių tinklelio koordinačių. Šis atstumas yra klaida. Algoritmas sukonstruotas taip, kad jums tereikia žinoti šios klaidos ženklą. Vadinasi, rastro taškas (1, 1) geriau apytiksliai atitinka atkarpos eigą nei taškas (1, 0). Jei nuolydis yra mažesnis nei ½, tada yra priešingai. Jei nuolydis yra ½, nėra pageidaujamo pasirinkimo. Tokiu atveju algoritmas pasirenka tašką (1, 1). Kadangi pageidautina patikrinti tik klaidos ženklą, iš pradžių jis nustatomas į -½. Taigi, jei atkarpos nuolydis yra didesnis arba lygus ½, tada paklaidos reikšmę kitame rastro taške galima apskaičiuoti kaip e = -½ + Δy/Δx. Kad Bresenhamo algoritmas būtų įgyvendintas iki galo, reikia apdoroti segmentus visuose oktantuose. Tai padaryti nesunku, algoritme atsižvelgus į kvadranto, kuriame yra segmentas, skaičių ir jo kampinį koeficientą. Kai absoliuti nuolydžio vertė yra didesnė nei 1, y nuolat keičiamas vienu, o Bresenhamo klaidos kriterijus sprendžiama, ar keisti x reikšmę. Nuolat kintančios (+1 arba -1) koordinatės pasirinkimas priklauso nuo kvadranto
var x,y,sy,sx,dx,dy,e,z,i: sveikasis skaičius; 27. Bresenham algoritmas apskritimui generuoti
Rastrą reikia išplėsti kaip linijines ir kitas sudėtingesnes funkcijas. Galinių pjūvių, tokių kaip kiliai, elipsės, parabolės, hiperbolės, pasiskirstymas buvo priskirtas robotų skaičiui. Su didžiausia pagarba, suprantama, įdėtas kuolas. Vienas iš efektyviausių ir lengviausiai suprantamų apskritimo generavimo algoritmų yra Bresenham. Burbuolei svarbu sugeneruoti tik vieną aštuntąją akcijų paketo dalį. Šios dalys gali būti pašalintos nuosekliais smūgiais. Sugeneravus pirmąjį oktantą (nuo 0 iki 45 ° prieš metus nukreiptos rodyklės), kitą oktantą galima išreikšti kaip veidrodinį tiesės y = x atvaizdą, kuris kartu sudaro pirmąjį kvadrantą. Pirmasis kvadrantas išmušamas tiesia linija x = 0, kad būtų pašalinta atraminė kuolo dalis nuo kito kvadranto. Viršutinė numušama tiesiai ties = 0, kad būtų atlikta užduotis. Norėdami parodyti algoritmą, pažvelkime į ketvirtadalį statymo, kurio centras yra koordinačių burbuliukas. Atkreipkite dėmesį, kad kadangi algoritmas prasideda taške x = 0, y = R, tada generuojant apskritimą už metų rodyklės pirmame kvadrate, y yra monotoniškai mažėjanti argumentų funkcija. Panašiai, jei išvesties taškas yra y = 0, x == R, tada generuojant apskritimą, esantį priešais rodyklę x, bus monotoniškai mažėjanti argumento y funkcija. Mūsų atveju pasirenkama karta už metų rodyklės su burbuole taške x = 0, y = R Perkeliama, kad kuolo centras ir burbuolės taškas yra tiksliai rastro taškuose. Kuriant už metų rodyklės bet kuriame apskritimo taške yra tik trys kito pikselio, artimiausio apskritimo, pasirinkimo parinktys: horizontaliai į dešinę, įstrižai žemyn ir į dešinę, vertikaliai žemyn. Algoritmas parenka pikselį, kurio mažiausias kvadratas yra tarp vieno iš šių pikselių ir apskritimo. 28. Fraktalo samprata. Fraktalinės grafikos istorija
Kasdieniame gyvenime dažnai galima stebėti vaizdinius (raštus), kurių, atrodytų, matematiškai apibūdinti nepavyks. Pavyzdys: žiemą užšąla langai, galite stebėti vaizdą. Tokie rinkiniai vadinami fraktalais. Fraktalai nėra panašūs į gerai žinomas figūras iš geometrijos, be to, jie statomi pagal tam tikrus algoritmus, kuriuos galima įgyvendinti kompiuteryje. Paprasčiau tariant, fraktalas yra vaizdas, atsirandantis dėl tam tikros transformacijos, pakartotinai pritaikytos pradinei formai. Fraktalas yra geometrinė figūra, susidedanti iš dalių ir kurią galima suskirstyti į dalis, kurių kiekviena reprezentuos mažesnę visumos kopiją. Pagrindinė fraktalų savybė yra savęs panašumas, t.y. bet koks fraktalo fragmentas vienaip ar kitaip atkuria jo globalią struktūrą. Fraktalai skirstomi į geometrines, algebrines, stochastines ir kartojamų funkcijų sistemas. 29. Matmenų samprata ir jos skaičiavimas
Kasdieniame gyvenime mes nuolat susiduriame su dimensijomis. Įvertiname kelio ilgį, išsiaiškiname buto plotą ir kt. Ši sąvoka yra gana intuityvi ir, atrodytų, nereikalauja paaiškinimo. Linijos matmuo yra 1. Tai reiškia, kad pasirinkę atskaitos tašką, galime apibrėžti bet kurį šios linijos tašką naudodami 1 skaičių – teigiamą arba neigiamą. Be to, tai taikoma visoms linijoms - apskritimui, kvadratui, parabolei ir kt. 2 matmuo reiškia, kad bet kurį tašką galime vienareikšmiškai apibrėžti dviem skaičiais. Nemanykite, kad dvimatis reiškia plokščią. Sferos paviršius taip pat yra dvimatis (jis gali būti apibrėžtas naudojant dvi reikšmes - kampus, tokius kaip plotis ir ilguma). Jei žiūrėsime iš matematinio taško, matmuo nustatomas taip: vienmačių objektų linijinį dydį padvigubėjus, dydis (šiuo atveju ilgis) padidėja du kartus (2^). 1). Dviejų dimensijų objektų linijinių matmenų padvigubinimas padidina dydį (pavyzdžiui, stačiakampio plotą) keturis kartus (2^2). Trimačių objektų atveju, padvigubėjus linijiniams matmenims, tūris padidėja aštuonis kartus (2^3) ir pan. Geometriniai fraktalai Būtent nuo šių fraktalų apskritai prasidėjo fraktalų raidos istorija. Šio tipo fraktalai gaunami naudojant paprastas geometrines konstrukcijas. Paprastai, statant geometrinius fraktalus, naudojamas toks algoritmas: Geometrinių fraktalų pavyzdžiai: Peano kreivė, Kocho snaigė, paparčio lapas, Sierpinskio trikampis, Algebriniai fraktalai Fraktalas- sudėtinga geometrinė figūra, turinti panašumo savybę, ty sudaryta iš kelių dalių, kurių kiekviena yra panaši į visą figūrą Algebriniai fraktalai gavo savo pavadinimą, nes yra sukurti remiantis algebrinėmis funkcijomis. Algebriniai fraktalai apima: Mandelbroto rinkinį, Julijos rinkinį, Niutono baseinus, biomorfus. -Mandelbroto rinkinys: Pirmą kartą Mandelbroto rinkinį 1905 metais aprašė Pierre'as Fatou. Fatou tyrinėjo rekursinius formos procesus Pradėdami nuo taško kompleksinėje plokštumoje, galite gauti naujų taškų, paeiliui taikydami jiems šią formulę. Tokia taškų seka vadinama transformuojama orbita Fatou nustatė, kad šios transformacijos orbita rodo gana sudėtingą ir įdomų elgesį. Tokių transformacijų yra be galo daug – po vieną kiekvienai reikšmei. (pavadintas Mandelbrotas, nes pirmasis kompiuteriu atliko reikiamą skaičių skaičiavimų). -Julija rinkinys: Julija racionalaus atvaizdavimo rinkinys -Niutono baseinai: Sritys su fraktalinėmis ribomis atsiranda tada, kai Niutono algoritmu kompleksinėje plokštumoje apytiksliai randamos netiesinės lygties šaknys (tikrojo kintamojo funkcijai Niutono metodas dažnai vadinamas tangentinis metodas, kuri šiuo atveju apibendrinta kompleksinei plokštumai). Taikykime Niutono metodą, kad surastume sudėtingo kintamojo funkcijos nulį, naudodami procedūrą: Pradinio aproksimavimo pasirinkimas yra ypač svarbus. Nes funkcija gali turėti kelis nulius, o skirtingais atvejais metodas gali konverguoti į skirtingas reikšmes. -biomorfai: sutrumpinta Julijos aibės forma, apskaičiuojama pagal formulę z=z 3 +c. Jis gavo savo pavadinimą dėl savo panašumo į vienaląsčius organizmus. Stochastiniai fraktalai Tipiškas šio tipo fraktalų atstovas yra vadinamoji plazma. Norėdami jį sukonstruoti, paimkite stačiakampį ir nustatykite kiekvieno jo kampo spalvą. Tada suraskite centrinį stačiakampio tašką ir nudažykite jį spalva, lygia stačiakampio kampuose esančių spalvų aritmetiniam vidurkiui + tam tikram atsitiktiniam skaičiui. Kuo didesnis šis atsitiktinis skaičius, tuo labiau suplyšęs piešinys. Gamtos objektai dažnai turi fraktalinę formą. Jiems modeliuoti galima naudoti stochastinius (atsitiktinius) fraktalus. Stochastinių fraktalų pavyzdžiai: Brauno judėjimo trajektorija plokštumoje ir erdvėje; Brauno judėjimo plokštumoje trajektorijos riba. 2001 m. Lawleris, Schrammas ir Werneris įrodė Mandelbroto hipotezę, kad jos matmuo yra 4/3. Schramm-Löwnerio evoliucijos yra konformiškai nekintamos fraktalinės kreivės, atsirandančios kritiniuose dvimačiuose statistinės mechanikos modeliuose, pavyzdžiui, Ising modelyje ir perkoliacijoje. įvairių tipų atsitiktinių imčių fraktalai, tai yra fraktalai, gauti naudojant rekursinę procedūrą, į kurią kiekviename žingsnyje įvedamas atsitiktinis parametras. Plazma yra tokio fraktalo panaudojimo kompiuterinėje grafikoje pavyzdys. Fraktalų monotipija arba stochatipija yra vaizduojamojo meno tendencija, apimanti atsitiktinio fraktalo atvaizdo gavimą. Susijusi informacija. |
- taškų rinkinys, kurio dinamika tam tikra prasme yra nestabili mažų pradinės padėties perturbacijų atžvilgiu. Tuo atveju f- daugianario, mes taip pat laikome užpildytą Julijos aibę - taškų, kurie nėra linkę į begalybę, rinkinį. Įprastas Julijos rinkinys yra jo riba.
