Siden en LCD-skjerm kan sees på som en matrise av diskrete elementer (piksler), som hver kan være bakgrunnsbelyst, er det ikke mulig å tegne en linje direkte fra ett punkt til et annet. Pikseldeteksjonsprosess den beste måtenå tilnærme et gitt segment kalles rasterdekomponering. Når det kombineres med prosessen med linje-for-linje-gjengivelse av et bilde, er det kjent som rasterskanningskonvertering. For horisontal, vertikal og skråstilt i en vinkel på 45°. segmenter, er valget av rasterelementer åpenbart. Med en hvilken som helst annen orientering er det vanskeligere å velge de nødvendige pikslene, som vist i fig. 1.
Figur 1. Rasterdekomponering av linjestykker.
De generelle kravene til algoritmer for å tegne segmenter er som følger: Segmentene skal se rett ut, begynne og slutte på gitte punkter, lysstyrken langs segmentet skal være konstant og uavhengig av lengde og helning, og skal tegnes raskt.
Konstant lysstyrke langs hele segmentet oppnås bare når du tegner horisontale, vertikale og skrå linjer i en vinkel på 45°. For alle andre orienteringer vil rasterisering resultere i ujevnhet i lysstyrken, som vist i fig. 1.
De fleste linjetegningsalgoritmer bruker trinn-for-trinn algoritme. Her er et eksempel på en slik algoritme:
Enkel steg-for-steg-algoritme
posisjon = start
trinn = økning
1. hvis stilling - slutt< точность deretter 4
hvis posisjon > slutt deretter 2
hvis posisjon< конец deretter 3
2. posisjon = posisjon - trinn
3. posisjon = posisjon + trinn
4. bli ferdig
Bresenhams algoritme.
Selv om Bresenhams algoritme opprinnelig ble utviklet for digitale plottere, er den det likt Egnet for LCD-skjerm. Algoritmen velger optimale rasterkoordinater for å representere segmentet. Under drift er en av koordinatene enten x eller y (avhengig av skråningen) - endres med én. Å endre en annen koordinat (til 0 eller 1) avhenger av avstanden mellom den faktiske posisjonen til segmentet og de nærmeste rutenettkoordinatene. Vi vil kalle denne avstanden en feil.
Algoritmen er konstruert på en slik måte at kun tegnet på denne feilen må kontrolleres. I fig. 2 er dette illustrert for segmentet i den første oktanten, dvs. for et segment med en helning fra 0 til 1. Fra figuren kan du se at hvis helningen til segmentet fra punktet (0,0) er større enn 1/2, så vil skjæringspunktet med linjen x = 1 være plassert nærmere linjen y = 1 enn den rette linjen y = 0. Følgelig tilnærmer rasterpunktet (1,1) seg bedre forløpet til segmentet enn punktet (1,0). Hvis helningen er mindre enn 1/2, så er det motsatte sant. for en helning på 1/2 er det ikke noe foretrukket valg. I i dette tilfellet Algoritmen velger punktet (1,1).
Ris. 2. Hovedideen til Bresenham-algoritmen.
Ikke alle segmenter går gjennom rasterpunkter. Lignende situasjon illustrert i fig. 3, hvor et segment med en helning på 3/8 først passerer gjennom rasterpunktet (0,0) og sekvensielt skjærer tre piksler. Beregningen av feilen ved representasjon av et segment med diskrete piksler er også illustrert.
Fig.3. Graf over feilen i Bresenhams algoritme.
Siden det er ønskelig å sjekke bare tegnet på feilen, settes den i utgangspunktet til -1/2. Således, hvis vinkelkoeffisienten til segmentet er større enn eller lik 1/2, kan feilverdien ved neste rasterpunkt med koordinater (1,0) beregnes som
e= e + m
Hvor m- vinkelkoeffisient. I vårt tilfelle, når Opprinnelig verdi feil -1/2
e = 1/2 + 3/8 = -1/8
Fordi e negativ, vil segmentet passere under midten av pikselen. Derfor er en piksel på samme horisontale nivå bedre tilnærmet posisjonen til segmentet, så påøker ikke. Vi beregner feilen på samme måte
e= -1/8 + 3/8 = 1/4
ved neste rasterpunkt (2,0). Nå e positiv, noe som betyr at segmentet vil passere høyere midtpunkt. Rasterelement (2,1) med nest største koordinat på bedre tilnærmet posisjonen til segmentet. Derfor påøker med 1. Før du vurderer neste piksel, er det nødvendig å korrigere feilen ved å trekke 1 fra den
e = 1/4 - 1 = -3/4
Merk at skjæringspunktet mellom en vertikal linje x= 2 s gitt segment ligger 1/4 under den rette linjen på= 1. Flytter vi segmentet 1/2 ned, får vi nøyaktig verdien -3/4. Fortsetter beregningene for neste piksel gir
e = -3/4 + 3/8 = -3/8
Fordi e er negativ, så øker ikke y. Av alt som er sagt, følger det at feilen er intervallet avskåret langs aksen på betraktet segment i hvert rasterelement (i forhold til -1/2).
La oss presentere Bresenhams algoritme for den første oktanten, dvs. for tilfelle 0 =< y =< x.
Bresenhams algoritme for å dekomponere et segment til et raster for den første oktanten
Heltall- konverteringsfunksjon til heltall
x, y, x, y - heltall
e - ekte
initialisering av variabler
Halvpikselkorrigert initialisering
start av hovedsyklusen
mens (e => 0)
Blokkskjemaet til algoritmen er vist i fig. 4.
Fig.4. Blokkdiagram over Bresenhams algoritme.
Et eksempel på Bresenhams algoritme.
Tenk på et segment tegnet fra punkt (0,0) til punkt (5,5). Å dekomponere et segment til et raster ved hjelp av Bresenham-algoritmen fører til følgende resultat:
innledende innstillinger
e = 1 - 1/2 = 1/2
Resultatet er vist i fig. 5 og sammenfaller med det som var forventet. Merk at rasterpunktet med koordinater (5,5) ikke er aktivert. Dette punktet kan aktiveres ved å endre for-neste sløyfe til 0 til x. Aktiveringen av punktet (0,0) kan elimineres ved å plassere en Plot-setning rett før neste i-linje.
Ris. 5. Resultatet av Bresenham-algoritmen i den første oktanten.
Generell algoritme Bresenham.
For at implementeringen av Bresenham-algoritmen skal være komplett, er det nødvendig å behandle segmenter i alle oktanter. Modifikasjonen er enkel å gjøre, og tar i algoritmen hensyn til nummeret på kvadranten der segmentet ligger og dets vinkelkoeffisient. Når absolutt verdi helningen er større enn 1, på endres stadig med én, og Bresenham-feilkriteriet brukes til å bestemme om verdien skal endres x. Valget av en konstant skiftende (med +1 eller -1) koordinat avhenger av kvadranten (fig. 6.). Den generelle algoritmen kan formuleres som følger:
Generalisert heltalls Bresenham kvadrantalgoritme
det antas at endene på segmentet (x1,y1) og (x2,y2) ikke faller sammen
alle variabler regnes som heltall
Skilt- en funksjon som returnerer -1, 0, 1 for henholdsvis et negativt, null og positivt argument
initialisering av variabler
x = abs(x2 - x1)
y = abs(y2 - y1)
s1 = Skilt(x2 - x1)
s2 = Skilt(y2 - y1)
utveksling av x- og y-verdier avhengig av helningen til segmentet
hvis y< x deretter
slutt hvis
initialisering e justert med en halv piksel
hovedsløyfe
til i=1 til x
Plott(x,y)
samtidig som(e =>0)
hvis Bytte = 1 deretter
slutt mens
hvis Bytte = 1 deretter
Fig.6. Analyse av tilfeller for den generaliserte Bresenham-algoritmen.
Eksempel. Generalisert Bresenham-algoritme.
For illustrasjon, vurder et segment fra punkt (0,0) til punkt (-8, -4).
innledende innstillinger
resultater av trinn-for-trinn-syklusen
Fig.7. Resultatet av den generaliserte Bresenham-algoritmen i tredje kvadrant.
I fig. 7 viser resultatet. Sammenligning med fig. 5 viser at resultatene av de to algoritmene er forskjellige.
Den neste delen diskuterer Bresenhams algoritme for å generere en sirkel.
Bresenhams algoritme for å generere en sirkel.
Det er nødvendig å dekomponere til et raster ikke bare lineært, men også annet, mer komplekse funksjoner. Dekomponering kjeglesnitt, det vil si sirkler, ellipser, parabler, hyperbler, et betydelig antall verk ble viet. Mest oppmerksomhet, selvfølgelig, er gitt til sirkelen. En av de mest effektive og lettfattelige sirkelgenereringsalgoritmene er på grunn av Bresenham. Først, merk at du bare trenger å generere en åttendedel av sirkelen. De gjenværende delene kan oppnås ved suksessive refleksjoner, som vist i fig. 8. Hvis den første oktanten genereres (fra 0 til 45° mot klokken), så kan den andre oktanten oppnås ved speilrefleksjon i forhold til den rette linjen y = x, som til sammen gir den første kvadranten. Den første kvadranten reflekteres i forhold til linjen x = 0 for å oppnå den tilsvarende delen av sirkelen i den andre kvadranten. Den øvre halvsirkelen reflekteres i forhold til den rette linjen y = 0 for å fullføre konstruksjonen. I fig. Figur 8 viser todimensjonale matriser for de tilsvarende transformasjonene.
Ris. 8. Generasjon full sirkel fra buen i den første oktanten.
For å utlede algoritmen, betrakt den første fjerdedelen av en sirkel med sentrum i origo. Merk at hvis algoritmen starter på punktet x = 0, y = R, deretter når du genererer en sirkel med klokken i første kvadrant på er en monotont avtagende funksjon av argumentene (fig. 9). På samme måte hvis Utgangspunktet er y = 0, X = R, deretter når du genererer en sirkel mot klokken X vil være en monotont avtagende funksjon av argumentet u. I vårt tilfelle velges generering med klokken, og starter ved punktet X = 0, y = R. Det antas at sentrum av sirkelen og utgangspunktet er nøyaktig ved rasterpunktene.
For alle gitt poeng på en sirkel, når du genererer med klokken, er det bare tre muligheter for å velge neste piksel som best tilnærmer sirkelen: horisontalt til høyre, diagonalt ned og til høyre, vertikalt ned. I fig. 10 er disse retningene betegnet henholdsvis m H, m D, m V . Algoritmen velger en piksel der kvadratet på avstanden mellom en av disse pikslene og sirkelen er minimal, dvs. minimum av
m H = |(xi + 1) 2 + (y i) 2-R2 |
m D = | |
mV = |(xi)2+ (yi-1)2-R2|
Beregningene kan forenkles hvis vi legger merke til at i nærheten av punktet (xi, yi,) er bare fem typer skjæringspunkter mellom sirkelen og rasternettet mulig, vist i fig. elleve.
Ris. 11. Skjæringspunktet mellom en sirkel og et rasternett.
Forskjellen mellom kvadratiske avstander fra sentrum av sirkelen til den diagonale pikselen (x i, + 1, y i - 1) og fra sentrum til et punkt på sirkelen R 2 er lik
d i = (xi + 1) 2 + (y i -1) 2 -R 2
Som i Bresenham-algoritmen for et segment, er det tilrådelig å bare bruke tegnet på feilen, og ikke dens størrelse, for å velge den tilsvarende pikselen.
Når d i< 0 диагональная точка (x i , + 1, у i - 1) er plassert inne i en reell sirkel, det vil si at dette er tilfelle 1 eller 2 i fig. 11. Det er klart at i denne situasjonen bør du velge enten piksel (x i, + 1, på Jeg) , dvs. m H, eller piksel (x i, + 1, på Jeg - 1), dvs. mD. For å gjøre dette, vurder først tilfelle 1 og kontroller forskjellen i kvadratiske avstander fra sirkelen til pikslene i horisontal og diagonal retning:
d = |(xi + 1) 2 + (y i) 2-R2 | - |(xi + 1)2+ (yi-1)2-R2 |
Ved d< 0 расстояние от окружности до диагонального пикселя больше, чем до горизонтального. Tvert imot, hvis d > 0, avstanden til den horisontale pikselen er større. Dermed,
ved d<= 0 выбираем m H в (x i , + 1, у i - 1)
for d > 0, velg m D in (x i, + 1, y i - 1)
Ved e = 0, når avstanden fra sirkelen til begge piksler er den samme, velger vi det horisontale trinnet.
Antallet beregninger som kreves for å estimere verdien av e kan reduseres ved å merke seg at i tilfelle 1
(xi + 1) 2 + (y i) 2-R2 >= 0
(xi + 1) 2 + (y i -1) 2 -R 2< 0
siden diagonal piksel (x i, + 1, på Jeg - 1) ligger alltid innenfor sirkelen, og horisontalt (x i, + 1, på Jeg) - utenfor den. Dermed kan e beregnes ved hjelp av formelen
d = (xi + 1) 2 + (y i) 2 -R 2 + (xi + 1) 2 + (y i -1) 2 -R 2
Tillegg til full firkant ledd (y i) 2 ved hjelp av addisjon og subtraksjon - 2y i + 1 gir
d = 2[(xi + 1) 2 + (y i -1) 2 -R 2 ] + 2y i - 1
I firkantede parenteser står per definisjon e i og dens substitusjon
d = 2(e i + y i) - 1
forenkler uttrykket betraktelig.
Tenk på tilfelle 2 i fig. 11 og merk at her må den horisontale pikselen (xi, + 1, y i) velges, siden y er en monotont avtagende funksjon. Kontroll av komponentene e viser det
(xi + 1) 2 + (y i) 2-R 2< 0
(xi + 1) 2 + (y i -1) 2 -R 2< 0
siden i tilfelle 2 ligger de horisontale (xi, + 1, y i) og diagonale (xi, + 1, y i -1) piksler innenfor sirkelen. Derfor d< 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел (x i , + 1, у i).
Hvis e i > 0, er diagonalpunktet (xi, + 1, y i -1) utenfor sirkelen, dvs. dette er tilfellene 3 og 4 i fig. 11. I denne situasjonen er det klart at enten pikselen (xi, + 1, y i -1) eller (xi, y i -1) må velges . I likhet med analysen av det forrige tilfellet, kan seleksjonskriteriet oppnås ved først å vurdere tilfelle 3 og sjekke forskjellen mellom de kvadratiske avstandene fra sirkelen til diagonalen m D og vertikale m V piksler,
dvs. d " = |(xi+1)2+(yi-1)2-R2 | - |(xi)2+ (yi-1)2-R2 |
Klokken d " < 0 er avstanden fra sirkelen til den vertikale pikselen (xi, y i -1) større, og du bør velge et diagonalt trinn til pikselen (xi, + 1, y i -1). Tvert imot, i saken d " > 0, er avstanden fra sirkelen til den diagonale pikselen større, og du bør velge en vertikal bevegelse til pikselen (x i, y i -1). Dermed,
ved d " <= 0 velg m D in (x i +1, y i -1)
ved d " > 0 velg m V in (x i, y i -1)
Her i tilfelle d " = 0, dvs. når avstandene er like, velges diagonaltrinnet.
Kontroll av komponenter e " viser at
(x i) 2 + (y i -1) 2-R2 >= 0
(xi + 1) 2 + (y i -1) 2 -R 2< 0
fordi for tilfelle 3 er den diagonale pikselen (x i +1, y i -1) utenfor sirkelen, mens den vertikale pikselen (xi, y i -1) er innenfor den. Dette lar oss skrive f.eks " som
d " = (xi +1) 2 + (y i -1) 2 -R 2 + (x i) 2 + (y i -1) 2 -R 2
Å fullføre det perfekte kvadratet av leddet (x i) 2 ved å legge til og trekke fra 2x i + 1 gir
d " = 2[(x i +1) 2 + (y i -1) 2 -R 2 ] - 2x i - 1
Å bruke definisjonen d i bringer uttrykket til formen
d " = 2 (e dvs - x i )- 1
Nå, med tanke på tilfelle 4, merker vi igjen at vi bør velge den vertikale pikselen (xi, y i -1), siden y er en monotont avtagende funksjon når den øker X.
Kontroll av komponenter d " for tilfelle 4 viser det
(xi+1)2+ (yi-1)2-R2 > 0
(x i) 2 + (y i -1) 2-R2 > 0
siden begge pikslene er utenfor sirkelen. Derfor, e " > 0 og ved bruk av kriteriet utviklet for case 3, oppstår riktig valg av m V .
Det gjenstår å sjekke bare tilfelle 5 i fig. 11, som oppstår når den diagonale pikselen (xi, y i -1) ligger på sirkelen, dvs. d i = 0. Kontroll av e-komponentene viser at
(xi+1)2+ (yi)2-R2 > 0
Derfor er d > 0 og den diagonale pikselen (x i +1, y i -1) valgt. På samme måte estimerer vi komponentene d " :
(xi+1)2+ (yi-1)2-R2 = 0
(xi+1)2+ (yi-1)2-R2< 0
og d " < 0, что является условием выбора правильного диагонального шага к (x i +1 , у i -1) . Таким образом, случай d i = 0 подчиняется тому же критерию, что и случай d i < 0 или d i >0. La oss oppsummere resultatene som er oppnådd:
d<= 0 выбираем пиксел (x i +1 , у i) - m H
d > 0 velg en piksel (x i +1, y i -1) - m D
d " <= 0 выбираем пиксел (x i +1 , у i -1) - m D
d " > 0 velg piksel (x i, y i -1)- m V
d i = 0 velg piksel (x i +1, y i -1) - m D
Det er lett å utvikle enkle gjentaksrelasjoner for å implementere en trinnvis algoritme. Vurder først det horisontale trinnet m H til pikselen (x i + 1, y i) . La oss betegne denne nye pikselposisjonen som (i + 1). Da er koordinatene til den nye pikselen og verdien e i like
d i +1 = (x i +1 +1) 2 + (y i +1 -1) 2 -R 2 dd i + 2x i +1 + 1
Tilsvarende er koordinatene til den nye pikselen og verdien di for trinnet mD til pikselen (xi + 1, y i -1) som følger:
d i+1 = di + 2x i+1 - 2y i+1 +2
Det samme for trinn m V til (x i, y i -1)
d i+1 = di - 2y i+1 +1
En implementering av Bresenhams algoritme i pseudokode for en sirkel er gitt nedenfor.
Bresenhams trinnvise algoritme for å generere en sirkel i første kvadrant
alle variabler er heltall
initialisering av variabler
Grense = 0
1 Plott(x i, y i )
hvis y jeg<= Пределderetter 4
Velge tilfelle 1 eller 2, 4 eller 5, eller 3
hvis D i< 0deretter 2
hvis D > 0deretter 3
hvis Di = 0 deretter 20
kasusdefinisjon 1 eller 2
2 d = 2d i + 2у i - 1
hvis d<= 0deretter 10
hvis d > 0 deretter 20
kasusdefinisjon 4 eller 5
3 d = 2D i + 2x i - 1
hvis d <= 0deretter 20
hvis d > 0 deretter 30
utføre trinn
10 x i = x i + 1
Di = Di + 2x i + 1
gOtil 1
20 x i = x i + 1
Di = D i + 2х i - 2у i + 2
gå til 1
4 avslutning
Grensevariabelen settes til null for å avslutte algoritmen på den horisontale aksen, noe som resulterer i at en sirkel genereres i første kvadrant. Hvis bare én av oktantene er nødvendig, kan den andre oktanten oppnås ved å bruke innstillingen Limit = Heltall(R/sqrt(2)), og den første - ved å bruke refleksjonen av den andre oktanten i forhold til den rette linjen y = x (fig. 8). Blokkskjemaet til algoritmen er vist i fig. 12.
Ris. 12. Blokkdiagram over Bresenhams trinnvise algoritme for å generere en sirkel i første kvadrant.
Bezier-kurve og dens geometriske algoritme.
Bezier-kurver ble utviklet uavhengig på 60-tallet av 1900-tallet av Pierre Bezier fra bilfirmaet Renault og Paul de Casteljau fra Citroen-selskapet, hvor de ble brukt til å designe bilkarosserier.
Til tross for at de Castelliers oppdagelse ble gjort noe tidligere enn Bézier (1959), ble hans forskning ikke publisert og ble skjult av selskapet som en forretningshemmelighet frem til slutten av 1960-tallet.
Kurver ble først introdusert for allmennheten i 1962 av den franske ingeniøren Pierre Bézier, som, etter å ha utviklet dem uavhengig av de Castellier, brukte dem til datastøttet design av bilkarosserier. Kurvene ble oppkalt etter Bezier, og den rekursive metoden han utviklet for å bestemme kurver (de Casteliers algoritme) ble oppkalt etter de Castellier.
Deretter ble denne oppdagelsen et av de viktigste verktøyene i datastøttede designsystemer og datagrafikkprogrammer.
Bezier-kurve – parametrisk kurve gitt av uttrykket
, 0 < t <1
hvor er funksjonen til komponentene til vektorene til støttepunktene, og – basisfunksjoner Bezier-kurver, også kalt Bernstein polynomer.
hvor n er graden av polynomet, i er ordinaltallet til referansepunktet.
Typer Bezier-kurver
Lineære kurver
Når n = 1, er kurven et rett linjesegment, referansepunktene P0 og P1 definerer begynnelsen og slutten.
Kurven er gitt av ligningen:
,
Kvadratiske kurver
(n = 2) er spesifisert av 3 referansepunkter: P0, P1 og P2.
Kvadratiske Bezier-kurver som en del av splines brukes til å beskrive formen til tegn i TrueType-fonter og SWF-filer.
Kubiske kurver
(n = 3) er beskrevet med følgende ligning:
Fire referansepunkter P0, P1, P2 og P3, definert i 2- eller 3-dimensjonalt rom, bestemmer formen på kurven.
Linjen starter fra punkt P0 mot P1 og slutter ved punkt P3 som nærmer seg den fra P2. Det vil si at kurven ikke går gjennom punktene P1 og P2, de brukes til å angi retningen. Lengden på segmentet mellom P0 og P1 avgjør hvor raskt kurven vil dreie mot P3.
I matriseform er en kubisk Bezier-kurve skrevet som følger:
,
hvor heter det basismatrise Bezier:
Moderne grafikksystemer som PostScript, Metafont og GIMP bruker Bezier-splines som består av kubiske kurver for å representere buede former.
Applikasjon i datagrafikk
På grunn av den enkle definisjon og manipulering, er Bezier-kurver mye brukt i datagrafikk for modellering av glatte linjer. Kurven ligger helt i det konvekse skroget til referansepunktene. Denne egenskapen til Bezier-kurver, på den ene siden, forenkler oppgaven med å finne skjæringspunktene til kurvene (hvis de konvekse skrogene ikke krysser hverandre, krysser ikke kurvene seg selv), og på den annen side lar den deg for å visualisere kurven ved hjelp av kontrollpunktene. I tillegg kan affine kurvetransformasjoner (translasjon, skalering, rotasjon) også implementeres ved å bruke passende transformasjoner til kontrollpunktene.
De viktigste er Bezier-kurver av andre og tredje grad (kvadratisk og kubikk). Kurver av høyere grader krever flere beregninger når de behandles og brukes sjeldnere for praktiske formål. For å konstruere linjer med komplekse former, kan individuelle Bezier-kurver kobles sekvensielt til hverandre for å danne en Bezier-spline. For å sikre en jevn linje ved krysset mellom to kurver, må tilstøtende kontrollpunkter for begge kurvene ligge på samme linje. I vektorgrafikkprogrammer som Adobe Illustrator eller Inkscape er disse fragmentene kjent som "baner".
Geometrisk algoritme for Bezier-kurve
Denne algoritmen lar deg beregne koordinatene (x, y) til et punkt på en Bezier-kurve basert på parameterverdien t.
1. Hver side av konturen til polygonen som går gjennom landemerkepunktene er delt proporsjonalt med verdien t.
2. Delingspunktene er forbundet med rette segmenter og danner en ny polygon. Antall noder i den nye konturen er én mindre enn antall noder i den forrige konturen.
3. Sidene av den nye konturen deles igjen i forhold til verdien t. Og så videre. Dette fortsetter til et enkelt delingspunkt er oppnådd. Dette punktet vil være punktet på Bezier-kurven.
Her er et opptak av den geometriske algoritmen i C++:
for (i = 0;Jeg< = m;i + +)
R[i] =P[Jeg]; // lag en hjelpematriseR
for (j = m; i > 0; i – –)
for (i = 0; i< j; i + +)
R[i] =R[i] +t*(R[i + 1] –R[Jeg]);
Resultatet av algoritmen - koordinatene til ett punkt på Bezier-kurven er skrevet i R.
Modeller for å beskrive overflater. Analytisk modell.
En analytisk modell er en beskrivelse av en overflate ved hjelp av matematiske formler:
z = f(x,y) – beskrivelse ved hjelp av en funksjon,
F(x,y,z) = 0 – beskrivelse ved hjelp av en implisitt ligning.
En parametrisk form for overflatebeskrivelse brukes ofte:
hvor s og t er parametere som endres innenfor et visst område, og funksjonene Fx, Fy og Fz bestemmer overflatens form.
Fordel parametrisk form ligger i det enkle å beskrive overflater som tilsvarer tvetydige funksjoner og lukkede overflater.
Parametrisk beskrivelse kan settes på en slik måte at formelen ikke vil endre seg vesentlig (bli mer komplisert) når overflaten roteres eller skaleres.
Som et eksempel kan du vurdere den analytiske beskrivelsen av overflaten til en ball.
er en eksplisitt funksjon av to argumenter,
- implisitt ligning,
x = R sin s cos t, y = R sin s sin t, z = R cos s – i parametrisk form.
Den analytiske modellen er best egnet for mange overflateanalyseoperasjoner.
Fordeler modeller (fra CGs ståsted):
- enkelt å beregne koordinatene til hvert overflatepunkt og normal;
- en liten mengde data for å beskrive ganske komplekse former.
Feil:
- kompleksiteten til beskrivelsesformler som bruker funksjoner som sakte beregnes på en datamaskin reduserer hastigheten på visningsoperasjoner;
- I de fleste tilfeller er det umulig å bruke denne formen for beskrivelse direkte på overflatebildet - overflaten vises som et polyeder, hvor koordinatene til toppunktene og flatene beregnes under visningsprosessen, noe som reduserer hastigheten sammenlignet med polygonal beskrivelsesmodell.
Overflatemodell "uniform mesh".
Denne modellen beskriver koordinatene til individuelle overflatepunkter på følgende måte. Hver rutenettnode med indekser (i, j) er tildelt en høydeverdi zij. Indeksene (i, j) tilsvarer visse koordinatverdier (x, y). Avstanden mellom nodene er den samme - dx langs x-aksen, dy langs y-aksen. Faktisk er en slik modell en todimensjonal matrise, raster, matrise, hvor hvert element lagrer en høydeverdi.
Ikke alle overflater kan representeres av denne modellen. Hvis kun én høydeverdi registreres ved hver node (i, j), betyr dette at overflaten er beskrevet av en enkeltverdifunksjon z = f (x, y). Dette er med andre ord en overflate som hver vertikal krysser kun én gang. Vertikale ansikter kan heller ikke modelleres. Det skal bemerkes at rutenettet kan spesifiseres ikke bare i kartesiske koordinater. For eksempel, for å beskrive overflaten til en ball med en unik funksjon, kan du bruke polare koordinater. Ved hjelp av et enhetlig rutenett beskrives ofte relieffet av jordoverflaten.
Positive trekk ved et enhetlig rutenett:
- enkel beskrivelse av overflater;
- muligheten til raskt å finne ut høyden til ethvert punkt på overflaten ved enkel interpolering.
Ulemper med ensartet mesh:
- overflater som tilsvarer en tvetydig høydefunksjon ved rutenettpunkter kan ikke modelleres;
- For å beskrive komplekse overflater kreves det et stort antall noder, som kan være begrenset av mengden dataminne.
"Ujevn mesh" overflatemodell.
En ujevn maske er en modell for å beskrive en overflate i form av et sett med individuelle punkter ((x0, y0, z0), (x1, y1, z1), ..., (xn – 1, yn – 1, zn – 1)) som tilhører overflaten. Disse punktene kan oppnås for eksempel som et resultat av å måle overflaten til et objekt ved hjelp av bestemt utstyr. Denne modellen kan betraktes som en generalisering for noen av modellene diskutert ovenfor. For eksempel kan en vektorpolygonmodell og et uniformt nett betraktes som variasjoner av det ikke-uniforme nettet.
La oss vurdere en overflatemodell i form av et sett med punktverdier som er logisk ikke relatert til hverandre. Ujevnheten i å definere referansepunkter kompliserer bestemmelsen av koordinater for andre overflatepunkter som ikke sammenfaller med referansepunktene. Spesielle romlige interpolasjonsteknikker kreves.
La oppgaven være å beregne verdien av z-koordinaten fra kjente koordinater (x, y). For å gjøre dette må du finne flere av de nærmeste punktene, og deretter beregne ønsket z-verdi basert på den relative plasseringen av disse punktene i projeksjonen (x, y). For et enhetlig rutenett løses dette problemet ganske enkelt - det er praktisk talt ingen søk, indeksene til de nærmeste referansepunktene beregnes umiddelbart.
Den andre oppgaven er å vise (visualisere) overflaten. Dette problemet kan løses på flere måter. En av de vanligste er triangulering.
Trianguleringsprosessen kan representeres som følger:
- vi finner de tre første punktene nærmest hverandre - vi får ett flatt trekantet ansikt;
- vi finner punktet nærmest dette ansiktet og danner et tilstøtende ansikt, og så videre, til det ikke er et eneste punkt igjen.
Bresenham-algoritmen ble foreslått av Jack E. Bresenham i 1962 og er beregnet på å tegne figurer med punkter på et plan. Denne algoritmen er mye brukt i datagrafikk for å tegne linjer på skjermen. Algoritmen bestemmer hvilke punkter i et todimensjonalt raster som må males.
En grafisk tolkning av Bresenhams algoritme er presentert i figuren.
For å tegne rette segmenter på et plan ved å bruke Bresenham-algoritmen, skriver vi likningen til en rett linje i generell form
f(x,y)=Ax+By+C=0
hvor er koeffisientene EN Og B uttrykt gjennom koeffisienter k Og b ligninger av en rett linje. Hvis en linje går gjennom to punkter med koordinater ( x1;y1) Og ( x2;y2), så bestemmes koeffisientene til den rette linjeligningen av formlene
A=y2-y1
B=x1-x2
C=y1∙x2-y2∙x1
For ethvert rasterpunkt med koordinater ( xi;yi) verdifunksjon
- f(xi,yi)=0 hvis punktet ligger på en linje
- f(xi,yi)>0 hvis punktet ligger under linjen
- f(xi,yi) Hvor Jeg– nummeret til det viste punktet.
Dermed en metode for å bestemme hvilket punkt P eller Q(se figur) vil vises i neste trinn, er sammenligningen av midten av segmentet |P-Q| med funksjonsverdi f(x,y). Hvis verdien f(x,y) ligger under midtpunktet av segmentet |P-Q|, så vil det neste punktet som skal vises være punktet P, ellers - pek Q
.
La oss skrive ned økningen til funksjonen
∆f=A∆x+B∆y
Etter å ha vist et punkt med koordinater (xi,yi) det tas en beslutning om neste punkt som skal vises. For å gjøre dette sammenlignes trinnene Δx Og Δy, som karakteriserer tilstedeværelsen eller fraværet av bevegelse langs den tilsvarende koordinaten. Disse inkrementene kan ta verdiene 0 eller 1. Derfor, når vi beveger oss fra et punkt til høyre,
når vi beveger oss fra et punkt til høyre og ned, da
∆f=A+B,
når vi beveger oss fra et punkt ned, da
Vi kjenner koordinatene til begynnelsen av segmentet, det vil si et punkt som åpenbart ligger på ønsket linje. Vi legger det første punktet der og aksepterer f= 0 . Du kan ta to trinn fra gjeldende punkt - enten vertikalt (horisontalt) eller diagonalt med én piksel.
Bevegelsesretningen vertikalt eller horisontalt bestemmes av tiltvinkelkoeffisienten. Hvis helningsvinkelen er mindre enn 45º, og
|A|<|B|
Med hvert trinn skjer bevegelse horisontalt eller diagonalt.
Hvis helningsvinkelen er større enn 45º, er bevegelsen vertikal eller diagonal for hvert trinn.
Dermed er algoritmen for å tegne et skrå segment som følger:
Implementering i C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#inkludere
bruker navneområde std;
void Brezenhem(char **z, int x0, int y0, int x1, int y1)
{
int A, B, tegn;
A = y1 - y0;
B = x0 - xl;
hvis (abs(A) > abs(B)) tegn = 1;
annet tegn = -1;
int signa, signb;
hvis en< 0) signa = -1;
annet signa = 1;
hvis (B< 0) signb = -1;
annet tegnb = 1;
int f = 0;
z = "*" ;
int x = x0, y = y0;
if (tegn == -1)
{
gjør (
f += A*signa;
hvis (f > 0)
{
f -= B*tegnb;
y += signa;
}
x -= tegnb;
z[y][x] = "*" ;
}
ellers
{
gjør (
f += B*tegnb;
hvis (f > 0) (
f -= A*signa;
x -= tegnb;
}
y += signa;
z[y][x] = "*" ;
) mens (x != x1 || y != y1);
}
}
int main()
{
const int STØRRELSE = 25; // feltstørrelse
int xl, x2, y1, y2;
char**z;
z = nytt tegn *;
for (int i = 0; i< SIZE; i++)
{
z[i] = ny char ;
for (int j = 0; j< SIZE; j++)
z[i][j] = "-" ;
}
cout<<
"x1 = "
; cin >> x1;
cout<<
"y1 = "
; cin >> y1;
cout<<
"x2 = "
; cin >>x2;
cout<<
"y2 = "
; cin >> y2;
Brezenhem(z, xl, y1, x2, y2);
for (int i = 0; i< SIZE; i++)
{
for (int j = 0; j< SIZE; j++)
cout<<
z[i][j];
cout<<
endl;
}
cin.get(); cin.get();
returner 0;
}
Utførelsesresultat
Bresenhams algoritme kan også brukes i kontrollproblemer, som kraft- eller hastighetskontroll. I dette tilfellet er den horisontale aksen tidsaksen, og den angitte verdien setter koeffisienten for helningsvinkelen til den rette linjen.
Bresenhams algoritme er en algoritme som bestemmer hvilke punkter på et todimensjonalt raster som må skyggelegges for å få en nær tilnærming av en rett linje mellom to gitte punkter.
Segmentet er tegnet mellom to punkter - (x0,y0) og (x1,y1), hvor i disse parene er henholdsvis kolonnen og raden indikert, hvor tallene øker til høyre og ned. Først vil vi anta at linjen vår går ned og til høyre, og den horisontale avstanden x1 − x0 overstiger den vertikale avstanden y1 − y0, dvs. helningen til linjen fra horisontalen er mindre enn 45°. Målet vårt er for hver kolonne x mellom x0 og x1, bestemme hvilken rad av y som er nærmest linjen og tegne et punkt (x,y).
Den generelle formelen for en linje mellom to punkter er:
Siden vi kjenner kolonne x, oppnås rad y ved å avrunde følgende verdi til et heltall:
Det er imidlertid ikke nødvendig å beregne den nøyaktige verdien av dette uttrykket. Det er nok å merke seg at y vokser fra y0 og for hvert trinn legger vi en til x og legger til stigningsverdien til y
som kan beregnes på forhånd. Dessuten gjør vi en av to ting ved hvert trinn: enten beholder vi den samme y, eller så øker vi den med 1.
Hvilken av disse to som skal velges kan avgjøres ved å holde styr på feilverdien, som betyr den vertikale avstanden mellom gjeldende y-verdi og nøyaktig y-verdi for gjeldende x. Hver gang vi øker x, øker vi feilverdien med mengden av helningen s gitt ovenfor. Hvis feilen er større enn 0,5, er linjen nærmere neste y, så vi øker y med én mens vi reduserer feilverdien med 1. I implementeringen av algoritmen nedenfor tegner plot(x,y) et punkt og abs returnerer den absolutte verdien av tallet:
funksjon linje(x0, x1, y0, y1)
int deltax:= abs(x1 - x0)
int deltay:= abs(y1 - y0)
ekte feil:= 0
ekte deltaerr:= deltay / deltax
int y:=y0
til x fra x0 til x1
error:= error + deltaerr
hvis feil >= 0,5
error:= feil - 1.0
La begynnelsen av segmentet ha koordinater (X 1,Y 1), og slutten (X 1,X 2). La oss betegne
Dx=(X2-X1),dy=(Y2-Y1). Uten tap av generalitet, vil vi anta at begynnelsen av segmentet faller sammen med opprinnelsen til koordinatene, og den rette linjen har formen
Hvor. Vi antar at utgangspunktet er til venstre. La ved (i-1) trinn det nåværende punktet til segmentet være P i -1 =(r,q) . Valget av neste punkt Si eller T i avhenger av forskjellens fortegn (s-t). Hvis (s-t)<0 , то P i =T i =(r+1,q) и тогда
Xi+1 =i+1;Yi+1 =Yi, hvis (s-t)≥0, så Pi =Ti =(r+1,q+1) og så Xi+1 =i+1; Yi+1 =Yi+1;
dx=(s-t)=2(rdy-qdx)+2dy –dx
Siden fortegnet for dx=(s-t) sammenfaller med fortegnet for differansen, vil vi sjekke fortegnet til uttrykket d i =dx(s-t). . Siden r=X i -1 og q=Y i -1, da
d i +1 = di +2dy -2dx(y i -y i -1) .
La ved forrige trinn 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)
Det gjenstår å finne ut hvordan du beregner d i. Siden for i=1
Prosedyre Bresenham(x1,y1,x2,y2,Farge: heltall);
dx,dy,incr1,incr2,d,x,y,xend: heltall;
dx:= ABS(x2-x1);
dy:= Abs(y2-yl);
d:=2*dy-dx; (startverdi for d)
incr1:=2*dy; (økning for d<0}
incr2:=2*(dy-dx); (økning for d>=0)
hvis x1>x2 da (start fra punktet med den minste x-verdien)
PutPixel(x,y,Farge); (første punkt i segmentet)
Mens x d:=d+incr1 (velg bunnpunktet) d:=d+inkr2; (velg topppunktet, y øker) PutPixel(x,y,Farge); 26. Generell Bresenham-algoritme.
Algoritmen velger optimale rasterkoordinater for å representere segmentet. Den største av inkrementene, enten Δx eller Δy, velges som rasterenhet. Under drift endres en av koordinatene - enten x eller y (avhengig av helningen) - med en. Å endre en annen koordinat (til 0 eller 1) avhenger av avstanden mellom den faktiske posisjonen til segmentet og de nærmeste rutenettkoordinatene. Denne avstanden er en feil. Algoritmen er konstruert på en slik måte at du bare trenger å vite tegnet på denne feilen. Følgelig tilnærmer rasterpunktet (1, 1) seg bedre forløpet til segmentet enn punktet (1, 0). Hvis helningen er mindre enn ½, er det motsatte sant. For en helning på ½ er det ikke noe foretrukket valg. I dette tilfellet velger algoritmen punktet (1, 1). Siden det er ønskelig å sjekke bare tegnet på feilen, settes den i utgangspunktet til -½. Således, hvis helningen til segmentet er større enn eller lik ½, kan feilverdien ved neste rasterpunkt beregnes som e = -½ + Δy/Δx. For at implementeringen av Bresenham-algoritmen skal være komplett, er det nødvendig å behandle segmenter i alle oktanter. Dette er enkelt å gjøre, og tar i algoritmen hensyn til nummeret på kvadranten der segmentet ligger og dets vinkelkoeffisient. Når den absolutte verdien av helningen er større enn 1, endres y konstant med én, og Bresenham-feilkriteriet brukes til å bestemme om verdien av x skal endres. Valget av en konstant skiftende (+1 eller -1) koordinat avhenger av kvadranten
var x,y,sy,sx,dx,dy,e,z,i: Heltall; 27. Bresenham-algoritme for å generere en sirkel
Rasteret må utvides som lineære og andre, mer komplekse funksjoner. Fordelingen av terminale kutt, som kjøl, ellipser, parabler, hyperbler, ble tildelt antall roboter. Med den største respekt, forståelig nok, er det lagt til en innsats. En av de mest effektive og enkleste å forstå sirkelgenereringsalgoritmene er Bresenham. For kolben er det viktig å generere bare en åttendedel av en innsats. Disse delene kan fjernes ved påfølgende slag. Når den første oktanten er generert (fra 0 til 45 ° av anti-år-pilen), kan den andre oktanten uttrykkes som et speilbilde av den rette linjen y = x, som sammen gir den første kvadranten. Den første kvadranten slås rett x = 0 for å fjerne den støttende delen av staven fra den andre kvadranten. Den øverste blir slått ned rett ved = 0 for å fullføre oppgaven. For å vise algoritmen, la oss se på en fjerdedel av en innsats sentrert på koordinatkolben. Vær oppmerksom på at siden algoritmen starter ved punktet x = 0, y = R, så når du genererer en sirkel bak årspilen i det første kvadratet, er y en monotont synkende funksjon av argumentene. På samme måte, hvis utgangspunktet er y = 0, x == R, vil x være en monotont avtagende funksjon av argumentet y når du genererer en sirkel på motsatt side av pilen. I vårt tilfelle er generasjonen bak årspilen med kolben i punktet x = 0, y = R valgt. Det overføres at senteret på staken og kolbepunktet er nøyaktig ved rasterpunktene. For et gitt punkt på sirkelen når du genererer bak årspilen, er det bare tre muligheter for å velge neste piksel, den nærmeste sirkelen: horisontalt til høyre, diagonalt ned og til høyre, vertikalt ned. Algoritmen velger en piksel der minimumkvadraten er mellom en av disse pikslene og sirkelen. 28. Konseptet med en fraktal. Historien om fraktal grafikk
I hverdagen kan du ofte observere bilder (mønstre) som, ser det ut til, ikke kan beskrives matematisk. Eksempel: vinduene fryser om vinteren, du kan ende opp med å observere bildet. Slike sett kalles fraktal. Fraktaler ligner ikke på kjente figurer fra geometri, og de er bygget etter visse algoritmer som kan implementeres på en datamaskin. Enkelt sagt er en fraktal et bilde som er et resultat av en transformasjon gjentatte ganger på den opprinnelige formen. En fraktal er en geometrisk figur som består av deler og som kan deles inn i deler som hver vil representere en mindre kopi av helheten. Hovedegenskapen til fraktaler er selvlikhet, dvs. ethvert fragment av en fraktal på en eller annen måte reproduserer dens globale struktur. Fraktaler er delt inn i geometriske, algebraiske, stokastiske og systemer med iterable funksjoner. 29. Dimensjonsbegrepet og dets beregning
I vårt daglige liv møter vi hele tiden dimensjoner. Vi anslår lengden på veien, finner ut området til leiligheten, etc. Dette konseptet er ganske intuitivt, og det ser ut til at det ikke krever avklaring. Linjen har dimensjon 1. Dette betyr at ved å velge et referansepunkt, kan vi definere et hvilket som helst punkt på denne linjen ved å bruke 1 tall - positivt eller negativt. Dessuten gjelder dette alle linjer - sirkel, firkant, parabel osv. Dimensjon 2 betyr at vi unikt kan definere et hvilket som helst punkt med to tall. Ikke tro at todimensjonal betyr flat. Overflaten til en kule er også todimensjonal (den kan defineres ved hjelp av to verdier - vinkler som bredde og lengdegrad). Hvis vi ser på det fra et matematisk synspunkt, bestemmes dimensjonen som følger: for endimensjonale objekter fører dobling av deres lineære størrelse til en økning i størrelse (i dette tilfellet lengde) med en faktor på to (2^ 1). For todimensjonale objekter resulterer dobling av lineære dimensjoner i en økning i størrelse (for eksempel arealet til et rektangel) med fire ganger (2^2). For 3-dimensjonale objekter fører dobling av de lineære dimensjonene til en åttedobling i volum (2^3) og så videre. Geometriske fraktaler Det var med disse fraktalene historien om utviklingen av fraktaler generelt begynte. Denne typen fraktal oppnås gjennom enkle geometriske konstruksjoner. Vanligvis, når du konstruerer geometriske fraktaler, brukes følgende algoritme: Eksempler på geometriske fraktaler: Peanokurve, Koch snøfnugg, bregneblad, Sierpinski-trekant, Algebraiske fraktaler Fraktal- en kompleks geometrisk figur som har egenskapen til selvlikhet, det vil si sammensatt av flere deler, som hver er lik hele figuren Algebraiske fraktaler har fått navnet sitt fordi de er bygget på grunnlag av algebraiske funksjoner. Algebraiske fraktaler inkluderer: Mandelbrot-sett, Julia-sett, Newton-bassenger, biomorfer. -Mandelbrot sett: Mandelbrot-settet ble først beskrevet i 1905 av Pierre Fatou. Fatou studerte rekursive prosesser av formen Starter med et punkt på det komplekse planet, kan du oppnå nye poeng ved å bruke denne formelen suksessivt på dem. En slik sekvens av punkter kalles en bane under transformasjon Fatou fant at banen under denne transformasjonen viser ganske kompleks og interessant oppførsel. Det er et uendelig antall slike transformasjoner - en for hver verdi. (kalt Mandelbrot fordi han var den første som utførte det nødvendige antallet beregninger ved hjelp av en datamaskin). -Julia sett: Julia sett av en rasjonell kartlegging -Newton bassenger: Regioner med fraktalgrenser vises når røttene til en ikke-lineær ligning tilnærmet finnes av Newtons algoritme på et komplekst plan (for en funksjon av en reell variabel kalles Newtons metode ofte tangentmetode, som i dette tilfellet er generalisert til det komplekse planet). La oss bruke Newtons metode for å finne null av en funksjon av en kompleks variabel ved å bruke prosedyren: Valget av innledende tilnærming er av spesiell interesse. Fordi en funksjon kan ha flere nuller, og i forskjellige tilfeller kan metoden konvergere til forskjellige verdier. -biomorfer: en forkortet form av Julia-settet, beregnet med formelen z=z 3 +c. Den har fått navnet sitt på grunn av sin likhet med encellede organismer. Stokastiske fraktaler En typisk representant for denne typen fraktal er det såkalte plasmaet. For å konstruere det, ta et rektangel og bestemme en farge for hvert av hjørnene. Deretter finner du det sentrale punktet i rektangelet og maler det med en farge som er lik det aritmetiske gjennomsnittet av fargene i hjørnene av rektangelet + et tilfeldig tall. Jo større dette tilfeldige tallet, jo mer revet vil tegningen bli. Naturlige gjenstander har ofte en fraktal form. Stokastiske (tilfeldige) fraktaler kan brukes til å modellere dem. Eksempler på stokastiske fraktaler: bane av Brownsk bevegelse på flyet og i rommet; grensen for banen til Brownsk bevegelse på et fly. I 2001 beviste Lawler, Schramm og Werner Mandelbrots hypotese om at dens dimensjon er 4/3. Schramm-Löwner-evolusjoner er konformt invariante fraktale kurver som oppstår i kritiske todimensjonale modeller av statistisk mekanikk, for eksempel Ising-modellen og perkolering. ulike typer randomiserte fraktaler, det vil si fraktaler oppnådd ved bruk av en rekursiv prosedyre der en tilfeldig parameter introduseres i hvert trinn. Plasma er et eksempel på bruken av en slik fraktal i datagrafikk. Fractal monotype, eller stochatypy, er en trend innen kunst som innebærer å få et bilde av en tilfeldig fraktal. Relatert informasjon. Hva ser du på nå? Med mindre du er fra et parallelt univers hvor alle sitter bak vektormonitorer, så er dette et rasterbilde. Se på denne stripen: /. Hvis du beveger deg nærmere skjermen, kan du se pikselerte trinn som prøver å utgi seg for å være en vektorlinje. Det finnes en hel haug med forskjellige rasteriseringsalgoritmer for dette formålet, men jeg vil gjerne snakke om Bresenham-algoritmen og Y-algoritmen, som finner en tilnærming av et vektorsegment i rasterkoordinater. Jeg møtte problemet med rasterisering mens jeg jobbet med en prosedyregenerator for byggeplaner. Jeg trengte å representere veggene i rommet som celler i en todimensjonal matrise. Lignende problemer kan oppstå i fysikkberegninger, banesøkende algoritmer eller belysningsberegninger hvis rompartisjonering brukes. Hvem hadde trodd at kjennskap til rasteriseringsalgoritmer en dag kunne komme godt med? Dette var essensen av algoritmen, i virkeligheten ser alt slik ut. Først beregnes helningen (y1 - y0)/(x1 - x0). Feilverdi ved startpunktet for segmentet (0,0)
tas lik null og den første cellen er fylt. Ved neste trinn legges helningen til feilen og verdien analyseres hvis feilen er mindre 0.5
, så er cellen fylt (x0+1, y0), hvis mer, er cellen fylt (x0+1, y0+1) og en trekkes fra feilverdien. På bildet under er linjen før rasterisering vist i gult, og avstanden til nærmeste celler er vist i grønt og rødt. Helningen er lik en sjettedel, ved første trinn blir feilen lik helningen, som er mindre 0.5
, som betyr at ordinaten forblir den samme. Mot midten av linjen krysser feilen linjen, en trekkes fra den, og den nye pikselen stiger høyere. Og så videre til slutten av segmentet. En nyanse til. Hvis projeksjonen av et segment på aksen x mindre projeksjon på aksen y eller begynnelsen og slutten av segmentet byttes, så vil ikke algoritmen fungere. For å forhindre at dette skjer, må du sjekke retningen til vektoren og dens skråning, og deretter, om nødvendig, bytte koordinatene til segmentet, rotere aksene og til slutt redusere alt til ett eller minst to tilfeller. Det viktigste er ikke å glemme å returnere øksene til deres plass mens du tegner. For å optimalisere beregninger, bruk trikset med å multiplisere alle brøkvariabler med dx = (x1 - x0). Deretter vil feilen ved hvert trinn endres til dy = (y1 - y0) i stedet for skråningen og forbi dx i stedet for en. Du kan også endre litt på logikken, "flytte" feilen slik at grensen er på null, og du kan sjekke fortegnet for feilen. Koden for å tegne en rasterlinje ved hjelp av Bresenham-algoritmen kan se omtrent slik ut. Pseudokode fra Wikipedia konvertert til C#. void BresenhamLine(int x0, int y0, int x1, int y1) ( var steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // Sjekk veksten av segmentet langs x-aksen og langs y-aksen / / Reflekter linjen diagonalt hvis helningsvinkelen er for stor hvis (bratt) ( Swap(ref x0, ref y0); // Blanding av koordinater er inkludert i en egen funksjon for skjønnhet Swap(ref x1, ref y1 ) // Hvis linjen ikke vokser fra venstre til høyre, bytter vi begynnelsen og slutten av segmentet hvis (x0 > x1) ( Swap(ref x0, ref x1); ref y1); int dx = x1 - x0; (y1 - 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;
}
}
}
Eksempelkode for å tegne en sirkel i C#. void BresenhamCircle(int x0, int y0, int radius) ( int x = radius; int y = 0; int radiusError = 1 - x; mens (x >= y) ( DrawPoint(x + x0, y + y0); DrawPoint (y + x0, x + y0; DrawPoint(-x + x0, y + y0, x + y0); -y + y0); DrawPoint(y + x0, -x + y++);< 0)
{
radiusError += 2 * y + 1;
}
else
{
x--;
radiusError += 2 * (y - x + 1);
}
}
} På bildet over viser røde og grønne farger avstandene til to nabopiksler. For å beregne feilen kan du bruke en flyttallsvariabel og ta feilverdien fra brøkdelen. Eksempelkode for Wu Xiaolins glatte linje i C#. privat 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) ); Bytt(ref x1, ref y1 ) if (x0 > x1) (Swap(ref x0, ref x1); Denne funksjonen endrer automatisk koordinatene avhengig av variabelen bratt DrawPoint(steep, x1, y1, 1); ; 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;
}
}
Det er i dag vanskelig å finne en person som ikke har møtt datagrafikk i en eller annen form. Hvis en person begynner å bli interessert i algoritmene som ligger til grunn, vil Bresenhams algoritmer være en av de første. Det eneste problemet er at jeg fortsatt ikke har kommet over en enkel og forståelig beskrivelse av disse algoritmene, langt mindre en implementering. I denne artikkelen vil jeg prøve å snakke så enkelt som mulig om Bresenham-familien av algoritmer, og vil også gi klar-til-bruk kode i JavaScript, som praktisk talt ikke er forskjellig fra kode i C/C++. Koden kan tas og brukes ved først å skrive et takkebrev til forfatteren. Så formålet med Bresenhams algoritmer er å tegne en linje på en rasterenhet, vanligvis en monitor. Som du kan se i figur 1, ligger ikke alle piksler som er inkludert i linjebildet på denne linjen, det vil si at algoritmens oppgave er å finne de nærmeste pikslene. Hovedfordelen med Bresenhams algoritme er at den ikke bruker en kostbar multiplikasjonsoperasjon i en loop. Algoritmen egner seg for rette linjer eller andreordenskurver*. Det er modifikasjoner av algoritmen for fire-koblede (dvs. punkter som avviker med 1 i en koordinat anses som nabo) og åtte-koblede (dvs. punkter anses som nabo hvis begge koordinatene ikke skiller seg med mer enn 1) linjer. Her er det andre alternativet - mer komplekst, men gir også et bedre resultat. Hovedideen med algoritmen er at linjen som skal tegnes deler planet i to deler. Ligningen til kurven skrives som Z = f (x,y) . På alle punkter av kurven Z = 0, i punkter som ligger over kurven Z > 0, og i punkter under kurven Z< 0 . Нам известны координаты начала отрезка, то есть точки,
заведомо лежащей на искомой кривой. Ставим туда первый пиксель и принимаем
Z = 0 . От текущего пикселя можно сделать два шага — либо
по вертикали (по горизонтали), либо по диагонали на один пиксель. Конкретные
направления шагов выбираются в зависимости от типа линии, которую надо нарисовать.
Делая шаг, мы мы вычисляем, как изменятся значение Z: ΔZ = Z" x Δx + Z" y Δy Ved ett av de mulige trinnene øker Z, i det andre reduseres det. Hvert trinn er valgt slik at Z-verdien for den nye pikselen er så nær 0 som mulig. Dermed vil vi bevege oss langs linjen og skape bildet. La oss umiddelbart bli enige om at algoritmen for en rett linje ikke tegner horisontale og vertikale linjer. Dette er fordi å tegne slike linjer kan implementeres på en mye enklere måte, ofte på BIOS- eller drivernivå. De resterende segmentene er delt inn i to grupper: horisontal og vertikal. Hvis vi representerer ligningen til en rett linje på formen y = kx, vil segmentene som |k| ≤ 1 , og vertikale - for hvilke |k| > 1. Ved å tilordne et segment til en av gruppene, kan vi bytte koordinatene til endene slik at horisontale segmenter alltid tegnes fra venstre mot høyre, og vertikale segmenter alltid tegnes fra topp til bunn. For horisontale segmenter vil hver ny piksel være 1 til høyre for den forrige, og den kan også være høyere (lavere), dvs. to trinn er mulig - til høyre og til høyre diagonalt. For vertikale segmenter er mulige trinn ned og ned diagonalt. Hvis koordinatene til endene av segmentet er henholdsvis (x 1 ,y 1) og (x 2 ,y 2), endres Z med 1 med hvert trinn langs x-aksen og langs y-aksen - med (x) 2-x1)/(y2-y1). For ikke å håndtere divisjon og holde oss innenfor grensene for heltallsaritmetikk, vil vi endre variabelen Z til henholdsvis y2-y1 og x2-x1. Det er all matematikken, resten kan forstås fra koden. Algoritmen for å tegne en bue vil forbli utenfor rammen av artikkelen, men algoritmen for å tegne en sirkel viste seg å være mye enklere enn for en rett linje. Dette skyldes mange årsaker. For det første tegner vi bare en åttendedel av sirkelen - fra π/2 til π/4, og i motsatt retning, det vil si med klokken. Resten av sirkelen oppnås ved å reflektere denne delen i forhold til sentrum av sirkelen, de horisontale og vertikale aksene, samt de rette linjene y = x + b og y = -x + b som går gjennom sentrum av sirkelen . For det andre, på grunn av symmetri, er avvik fra en linje fra en sirkel ikke like merkbare som avvik fra en rett linje, så Z kan sammenlignes med null uten å beregne maksimalt tillatt avvik. Gyldige trinn er høyre og høyre-diagonale, og endringen i Z avhenger av verdiene til x og y, men forholdet er lineært, så ingen multiplikasjonsoperasjon er nødvendig. Det er alt, faktisk. Nedenfor finner du et skript som demonstrerer driften av de beskrevne algoritmene, og for å forstå hvordan det fungerer, se bare på kildeteksten til siden. Lykke til! Hvis du ønsker å se en demonstrasjon av algoritmene i nettleservinduet, vennligst aktiver JavaScript!
endre: boolsk;
begynne
x:=xl; y:=y1;
dx:=abs(x2-x1); dy:=abs(y2-yl);
sx:=tegn(x2-x1); sy:=tegn(y2-yl);
e:= 2*dy-dx;
hvis dy
ellers begynne
z:=dx;
dx:=dy; dy:=z;
endring:=sant
slutt;
for i:=1 til dx+dy begynner
hvis dy< dx then begin
hvis endre så y:=y+sy
ellers x:=x+sx;
e:=e+2*dy;
ende annet
hvis endre så x:=x+sx
annet y:=y+sy;
e:=e-2*dx
slutt;
Form1.Canvas.Pixels:=clblack; // skrive ut et punkt, for eksempel
slutt;
De første ideene om fraktal geometri oppsto på 1800-tallet. Cantor, ved hjelp av en enkel rekursiv prosedyre, gjorde linjen til en samling av usammenhengende punkter, som senere ble kalt "Cantor Dust." Han ville ta en linje og fjerne den sentrale tredjedelen og deretter gjenta det samme med de resterende delene. Peano trakk en spesiell type linje. For å tegne den brukte Peano følgende algoritme:
Han tok en rett linje og erstattet den med segmenter som er tre ganger kortere enn den opprinnelige linjen. Så gjentok han den samme handlingen med hvert av segmentene. Dens egenart er at den fyller hele flyet, dvs. for hvert punkt på flyet kan du finne et punkt som tilhører Peano-linjen.
Grunnleggeren av fraktal geometri er vurdert Benoit Mandelbrot. Mandelbrot introduserte konseptet "fraktal".
Ris. Snøfnugg Koch
Ris. Ark
Ris. Sierpinski trekant
- et sett med punkter, hvis dynamikk i nærheten er, i en viss forstand, ustabil med hensyn til små forstyrrelser i utgangsposisjonen. Hvis f- et polynom, anser vi også et fylt Julia-sett - et sett med punkter som ikke har en tendens til uendelig. Det vanlige Julia-settet er grensen.
Driftsprinsippet til Bresenhams algoritme er veldig enkelt. Ta et segment og dets første koordinat x. Til x-en i syklusen legger vi en om gangen mot slutten av segmentet. Ved hvert trinn beregnes feilen - avstanden mellom den virkelige koordinaten y på dette stedet og den nærmeste rutenettcellen. Hvis feilen ikke overstiger halve høyden på cellen, er den fylt. Det er hele algoritmen.
Bresenhams algoritme har en modifikasjon for å tegne sirkler. Alt der fungerer på et lignende prinsipp, på noen måter enda enklere. Beregningen gjøres for en oktant, og alle andre deler av sirkelen er tegnet etter symmetri.
Nå om Wu Xiaolins algoritme for å tegne glatte linjer. Det skiller seg ved at det ved hvert trinn utføres en beregning for de to piksler som er nærmest linjen, og de males med forskjellige intensiteter, avhengig av avstanden. Nøyaktig å krysse midten av en piksel gir 100 % intensitet, hvis pikselen er 0,9 piksler unna, så vil intensiteten være 10 %. Med andre ord er hundre prosent av intensiteten delt mellom pikslene som begrenser vektorlinjen på begge sider. 
Hvis du noen gang finner deg selv i å jobbe med meshes i fremtiden, tenk et øyeblikk, kanskje du finner opp hjulet på nytt og du faktisk jobber med piksler, selv om du ikke vet det. Modifikasjoner av disse algoritmene kan brukes i spill for å søke etter celler foran en enhet på kartet, beregne nedslagsområdet til et skudd eller vakkert arrangere objekter. Eller du kan ganske enkelt tegne linjer, som i programmet fra lenkene nedenfor. Jeg vil gjerne uttrykke mine dype og oppriktige følelser overfor utviklerne av www-standarder og de som implementerer dem. En variant av JavaScript-kode som fungerer i alle tilgjengelige nettlesere, dvs. IE 6.0, NN 7.0 og Opera 6.0x utmerker seg ikke ved sin skjønnhet og raffinement. Imidlertid, "dette har ingenting å gjøre med vitenskapen jeg representerer for øyeblikket."
Tegne et linjestykke
Tegner en sirkel
x1: y1:
x2: y2:
x0: y0:
R: