Rasterisering af linjer

Den rasterisering af linier er en elementær opgave for computergrafik , hvor en linje trukket ( rasteriseres ) på punktet gitter af en raster grafik eller en rastergrafik enhed . Til dette formål er disse punkter eller pixels farvet, der tilnærmer den ideelle rute så tæt som muligt.

Grundlæggende algoritmer rasteriserer kun linjer i en farve. Et bedre display med flere farvegraderinger opnås med avancerede metoder, der understøtter anti-aliasing (kantudglatning).

Da mere komplekse geometriske figurer som polygoner og eventuelle kurver ofte er sammensat af linjesegmenter i computergrafik, danner rasterisering af linjer også udgangspunktet for deres rasterisering. En anden applikation, der ofte kræver, at der trækkes et stort antal linjer, er visning af trådrammemodeller .

To rasteriserede linjer. De farvede pixels vises som cirkler. Ovenfor: monokrom rasterisering; nedenfor: Gupta-Sproull antialiasing, den ideelle linje betragtes her som en overflade.

Monokrom halvtone

Enkeltfarvet rasterisering tegner linjer med en enkelt forgrundsfarve på en baggrund. Den er velegnet til enheder med monokrom skærm, f.eks. Laserprintere .

Start- og slutpunkterne for den linje, der skal rasteriseres, specificeres normalt i heltalskoordinater, dvs. de ligger direkte på rasterens punkter. Derfor er de fleste af metoderne kun formuleret til sådanne start- og slutpunkter. Der er flere muligheder for rasterisering af tykke linjer, som også er velegnede til andre kurver, se artiklen Screening .

Enkle metoder

Naiv screeningmetode ved hjælp af afrunding

Den enkleste måde at rastere på er at implementere ligningen, der definerer linjen direkte. Hvis ( x _en , y _en ) er startpunktet og ( x _e , y _e ) slutpunktet for den linje, de punkter på linjen tilfredsstille den rette linje ligning , hvor er den skråning . ${\ displaystyle y = m (x-x_ {a}) + y_ {a}}$${\ displaystyle \ textstyle m = {\ frac {\ Delta y} {\ Delta x}} = {\ frac {y_ {e} -y_ {a}} {x_ {e} -x_ {a}}}}$

Linjen trækkes ved at beregne den tilsvarende værdi i en løkke for hver fra til værdi i henhold til denne formel og afrunde den til nærmeste heltal. Pixel ( x , y ) farves derefter. ${\ displaystyle x}$${\ displaystyle x_ {a}}$${\ displaystyle x_ {e}}$${\ displaystyle y}$

Denne metode er unødvendigt langsom, fordi der udføres en multiplikation inden i sløjfen, hvilket på de fleste computere kræver betydeligt mere beregningstid end en tilføjelse eller subtraktion. En hurtigere metode er at overveje forskellen mellem to på hinanden følgende trin:

${\ displaystyle y_ {i + 1} -y_ {i} \!}$	${\ displaystyle = (m (x_ {i + 1} -x_ {a}) + y_ {a}) - (m (x_ {i} -x_ {a}) + y_ {a}) \!}$
	${\ displaystyle = m (x_ {i + 1} -x_ {i}) \!}$
	${\ displaystyle = m \!}$.

Følgelig er det tilstrækkeligt at starte med ( x _a , y _a ) og øge hver gang sløjfen køres igennem . Denne metode er også kendt som en Digital Differential Analyzer (DDA). ${\ displaystyle y}$${\ displaystyle m}$

Da afrunding af til nærmeste heltal svarer til afrunding af en yderligere kontrol variabel kan også anvendes, som initialiseres med 0,5 og hvortil der er sat med hver sløjfe pass. Hver gang kontrolvariablen når eller overstiger 1,0, øges den med 1 og trækker 1,0 fra kontrolvariablen. Det betyder, at afrunding ikke længere er nødvendig. Denne metode kan omformuleres til kun at bruge hurtigere heltaloperationer og kan implementeres elegant på samlingssprog . Imidlertid er en langsom opdeling ( ) stadig nødvendig i starten, som ikke kan kompenseres for med den hurtige sløjfe i tilfælde af korte linjer. ${\ displaystyle y}$${\ displaystyle y + 0 {,} 5}$${\ displaystyle m}$${\ displaystyle y}$ ${\ displaystyle \ Delta y / \ Delta x}$

Generalisering i alle retninger

Rasterisering af alle linjer ved hjælp af symmetriegenskaber. Det tilladte område af den oprindelige procedure er vist i farve; de ​​tre ændringer i algoritmen åbner også de andre områder.

De netop beskrevne metoder fungerer kun med liniehældninger mellem 0 og 1, hvilket svarer til en vinkel på 0 ° til 45 ° i forhold til vandret. Linjen er ikke trukket eller trukket forkert for andre skråninger. Det er dog tilstrækkeligt kun at beskrive en algoritme for skråninger mellem 0 og 1, da andre linjer kan vises korrekt ved hjælp af symmetrier. Dette gøres gennem følgende tre ændringer:

1. Der skelnes mellem to sager afhængigt af (i form af beløb) eller omvendt. I det første tilfælde køres sløjfen igennem som før og beregnes i sløjfens krop , ellers køres den gennem og beregnes ved hjælp af.${\ displaystyle \ Delta x> \ Delta y}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$${\ displaystyle x}$
2. Inden i sløjfekroppen eller øges ikke med 1, men afhængigt af tegnet på eller tilføjes værdien +1 eller −1.${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle \ Delta y}$${\ displaystyle \ Delta x}$
3. Hvis eller , skal løkken køres bagud.${\ displaystyle \ Delta x <0}$${\ displaystyle \ Delta y <0}$

Ved at anvende disse generaliseringer kan følgende tabel oprettes for et bedre overblik:

Hvor i for m <= 1 værdier mellem 0 og og for m> 1 værdier mellem 0 og . Linjer, der er parallelle med X- eller Y-aksen, er også dækket af denne tabel og behøver ikke at blive betragtet separat. Den angivne retning henviser til grafikken til højre, forudsat at x stiger til højre og y stiger opad. x1 og y1 er koordinaterne for startlinjen for en linje, og x2 og y2 er koordinaterne for slutpunktet. ${\ displaystyle \ Delta x}$${\ displaystyle \ Delta y}$

Desuden kan følgende pseudokode kun oprettes ved at ændre tegnet, der dækker alle de otte beskrevne tilfælde:

  signX = 1;
  signY = 1;

  if x1 > x2
      signX = -1;

  if y1 > y2
      signY = -1;

  if m <= 1
      for i=0; i <= deltaX; i++
          drawPixel( ceil(x1 + i * signX), ceil(y1 + i * m * signY) )
  else
      for i=0; i<= deltaY; i++
          drawPixel( ceil(x1 + i / m * signX), ceil(y1 + i * signY) )

Hvor ceil () er en funktion, der skal afrundes og drawPixel kan være enhver funktion til at indstille en pixel.

Bresenhams algoritme

De ældste publicerede algoritmer til rasterisering af linjer stammer fra begyndelsen af ​​1960'erne. De blev brugt til at kontrollere digitale plottere , hvor pennen kun kunne bevæge sig vandret, lodret eller diagonalt på et gitter med faste intervaller. Dette omfattede også Bresenham-algoritmen præsenteret af Jack Bresenham i 1963 , som kun bruger heltalberegninger . Pitteway gav en ækvivalent afledning af denne algoritme, som har den fordel i forhold til Bresenhams ret geometriske formulering, at den også kan anvendes til andre kurver end linjer. Den resulterende algoritme, undertiden kaldet "midpoint algoritme", er nøjagtig den samme som i Bresenhams papir.

Valg af den næste pixel i Bresenham-algoritmen

Ideen med Bresenham-algoritmen er at vælge mellem de to pixels til højre ("øst") og øverst til højre ("nordøst") for den sidste pixel, der er tegnet ved hvert trin. Den pixel, der er tættere på den ideelle linje, vælges. For at gøre dette skal du se på midtpunktet mellem pixels i midtpunktformuleringen og : hvis det er over den ideelle linje, er det nærmere, ellers . ${\ displaystyle M}$${\ displaystyle O}$${\ displaystyle NO}$${\ displaystyle M}$${\ displaystyle O}$${\ displaystyle NO}$

For at finde positionen modsat linjen anvendes en anden form for ligelinjen: ${\ displaystyle M}$

${\ displaystyle F (x, \, y) = ax + ved + c = \ Delta y \ gange x- \ Delta x \ gange y + c = 0}$.

F ( x, y ) er 0 for punkter på linjen, positiv for punkter under og negativ for punkter over linjen. Hvis koordinaterne for indsættes i denne ligning , opnås værdien ${\ displaystyle M}$

${\ displaystyle \ textstyle d_ {i} = F (x_ {i} +1, \, y_ {i} + {\ frac {1} {2}}) = \ Delta y (x_ {i} +1) - \ Delta x (y_ {i} + {\ frac {1} {2}}) + c}$.

Afhængigt af tegnet på denne kontrolvariabel vælges pixel eller . ${\ displaystyle d_ {i}}$${\ displaystyle O}$${\ displaystyle NO}$

For at opnå en effektiv algoritme beregnes kontrolvariablen trinvist, dvs. øges trin for trin. Hvordan du ændrer det mellem to på hinanden følgende trin, afhænger af, om der er valgt pixels eller . For hvert af disse tilfælde skal du overveje forskellen mellem værdien af ​​kontrolvariablen for den næste, men den ene, og den næste pixel: ${\ displaystyle O}$${\ displaystyle NO}$

${\ displaystyle {\ begin {align} \ textstyle \ Delta _ {O} & = \ textstyle d_ {i + 1} -d_ {i} = F (x_ {i} +2, \, y_ {i} + { \ frac {1} {2}}) - d_ {i} = \ Delta y \\\ tekststil \ Delta _ {NO} & = \ tekststil d_ {i + 1} -d_ {i} = F (x_ {i } +2, \, y_ {i} + {\ frac {3} {2}}) - d_ {i} = \ Delta y- \ Delta x \\\ ende {justeret}}}$

For hvert trin øges kontrolvariablen med eller afhængigt af den valgte pixel . Hvis , så er over den lige linje, hvorfor det er valgt, ellers . ${\ displaystyle \ Delta _ {O}}$${\ displaystyle \ Delta _ {NO}}$${\ displaystyle d_ {i} \ leq 0}$${\ displaystyle M}$${\ displaystyle O}$${\ displaystyle NO}$

Den indledende værdi af kontrolvariablen kan også beregnes effektivt, hvis linjens startpunkt er nøjagtigt på en pixel: ${\ displaystyle d}$${\ displaystyle F (x_ {a}, \, y_ {a}) = 0}$

${\ displaystyle \ textstyle d_ {0} = F \ left (x_ {a} +1, \, y_ {a} + {\ frac {1} {2}} \ right) = \ \ underbrace {\ Delta y \ cdot x_ {a} - \ Delta x \ cdot y_ {a} + c} _ {= F (x_ {a}, \, y_ {a}) = 0} \, + \, \ Delta y - {\ frac {\ Delta x} {2}} = \ Delta y - {\ frac {\ Delta x} {2}}}$

For at eliminere delingen med 2 fordobles alle værdier af kontrolvariablen; det afgørende tegn bevares. Bresenham-algoritmen for linjer med en gradient mellem 0 og 1 kan således udtrykkes i den følgende pseudokode . Algoritmen behøver kun tilføjelser inden for sløjfen; de enkle multiplikationer uden for sløjfen kan også implementeres ved at tilføje.

Ændring i kontrolvariablen i Bresenham-algoritmen

d = 2×Δy – Δx
ΔO = 2×Δy
ΔNO = 2×(Δy − Δx)
y = ya
Pixel (xa, ya) einfärben
Für jedes x von xa+1 bis xeWenn d ≤ 0
        d = d + ΔO
    ansonsten
        d = d + ΔNO
        y = y + 1
    Pixel (x, y) einfärben

En anden fortolkning af algoritmen antager, at den rasteriserede linje indeholder vandrette og diagonale trin. For at "blande" disse to trintyper trækkes hvert trin enten fra kontrolvariablen eller tilføjes. Den tilsvarende trintype udføres, hvor den resulterende mængde af kontrolvariablen er lavere. Dette fremgår også af grafikken ovenfor, hvor kontrolvariablen altid er så tæt på nulaksen som muligt. Thompson beskrev en algoritme baseret på denne formulering i 1964, men diskuterede ikke valget af den korrekte startværdi for kontrolvariablen. Før Bresenham offentliggjorde Fred Stockton en algoritme til rasterisering af linjer i 1963, som også kun bruger heltalberegninger, men er unødvendigt kompliceret.${\ displaystyle m = \ Delta x- \ Delta y}$${\ displaystyle n = \ Delta y}$${\ displaystyle m}$${\ displaystyle n}$

Linjer, hvis slutpunkter er angivet med ikke-heltalskoordinater, kan også rastreres med Bresenham-algoritmen. For at gøre dette skal startværdien af ​​kontrolvariablen beregnes i henhold til dens oprindelige definition; generelle forenklinger er ikke mulige. Resten af ​​algoritmen forbliver gyldig.

Rækker af pixels

Selvom Bresenham-algoritmen er ret effektiv, tegner den kun en pixel pr. Iteration og har brug for en tilføjelse for at gøre det. En metode, der tegner alle pixels i en “række” - det vil sige pixels med samme y- koordinat - blev straks udviklet af Reggiori for første gang. Rækker med kun en pixel blev behandlet separat. Bresenham præsenterede senere en mere generel algoritme, der klarede sig uden test for dette specielle tilfælde.

Med Bresenhams pixelrægealgoritme øges den ikke trinvist, men . Slutningen af ​​den aktuelle række beregnes for hver . Dette gøres ved at se på de punkter, hvor den ideelle linje skærer en vandret løbende gennem midtpunktet mellem to lodret tilstødende pixels. Slutningen af ​​pixelrækken er den afrundede værdi af x- koordinaten for dette kryds: ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$

Slutpunktskoordinaterne for pixelrækkerne kan også beregnes trinvist. Da nogle punkter kan beregnes forkert med visse skråninger, bruger algoritmen en symmetri til den lige hældningslinje ½.

Der kræves ingen tilføjelser i den inderste sløjfe i Bresenhams nye algoritme, fordi alle pixels i en række er farvede på én gang. Opdeling er dog nødvendig for initialisering. Fung erstattede det med en søgningsprocedure og foretog nogle yderligere optimeringer.

N- trin metode

De fire mulige pixelmønstre i metoden med dobbelt trin

En anden måde at rastere på, først introduceret af Wu og Rokne, er at tage trin på flere pixels langs x- aksen og farve alle pixels på linjen imellem på én gang. For at gøre dette foretages der et valg mellem de forskellige mulige "pixelmønstre". Bresenhams algoritme kan ses som et specielt tilfælde af denne metode, hvor kun trin af en pixel er lavet, og hvor kun to “mønstre” (pixels til højre eller øverst til højre) vælges.

For at være i stand til at skelne mellem de fire mulige mønstre i dobbelt-trinsmetoden undersøges den sidste pixelkolonne i mønsteret først. Hvis den pixel, der skal rastreres, er i bunden eller øverst, kan mønstre 1 eller 4 udledes på en triviel måde. Hvis pixlen på den anden side er i midten, er det nødvendigt med en yderligere test af den midterste søjle for at kunne vælge mellem mønster 2 og 3.

Disse tests er forenklet af det faktum, at med en hældning m  ½ mønster 4 og med m  ½ mønster 1 ikke kan forekomme. I lighed med Bresenham-algoritmen kan kontrolvariablen til testene også beregnes trinvist med dobbelttrinsmetoden. I sidste ende klarer algoritmen sig kun med tilføjelser og en simpel multiplikation, som kan implementeres med et hurtigt bitskift .

Der er også udviklet tredobbelt og firdobbelt trinalgoritmer, der fungerer på det samme princip, men er betydeligt mere komplicerede og længere. En anden firetrinsalgoritme bruger en lidt anden formulering, der systematisk undersøger de betingelser, under hvilke et bestemt mønster opstår, og som kan generaliseres til et hvilket som helst antal trin.

Tovejs screening

Ovenfor: En linje rastret fra venstre mod højre ved hjælp af Bresenham-algoritmen; nedenfor: tovejs screening. De hule cirkler angiver de pixels, der vil blive farvet, når den anden pixel er valgt ved d = 0.

For yderligere at øge hastigheden på rasteriseringen er det fornuftigt at trække linjen tovejs, dvs. på samme tid fra start- og slutpunktet til midtpunktet. Her løkker sløjfen kun over halvdelen af ​​linjen; ved hvert trin farves de to involverede pixels på hver side af linjen. Både Bresenham-algoritmen og andre metoder kan ændres på denne måde.

Det skal dog bemærkes, at linjen rasteriseret med de normale metoder ikke nødvendigvis er punkt-symmetrisk i sig selv . Dette skyldes det faktum, at der er tvetydige situationer i rasteriseringen, hvor den ideelle linje løber nøjagtigt gennem midten af ​​to lodret tilstødende pixels, mellem hvilke du frit kan vælge. Bresenham-algoritmen, der er anført ovenfor, vælger f.eks. Altid pixlen med den mindre y- koordinat i sådanne tilfælde ( ) . Når man tegner fra højre til venstre, vælges derimod pixlen med den større y- koordinat på grund af brugen af ​​symmetri . Hvis linjen er trukket tovejs eller fra højre mod venstre, kan udseendet derfor ændre sig i forhold til den normale algoritme, forudsat at de tvetydige tilfælde ikke testes separat. ${\ displaystyle d = 0}$

Andre teknikker

periodicitet

Det kan vises, at værdierne for kontrolvariablen i Bresenham-algoritmen gentages flere gange, hvor a er den største fælles skiller af og . Dette betyder, at værdierne for kontrolvariablen kun skal beregnes for en del af linjen og derefter kan anvendes på de andre dele. Til dette skal dog GCD beregnes. Denne metode kan også kombineres med tovejs screening. ${\ displaystyle \ Delta x}$${\ displaystyle \ Delta y}$

Rækker med pixel i første, anden og tredje ordre

Hierarkiske pixelrækker

Længden af ​​pixelrækkerne i en rasterlinie følger et bestemt mønster. Rosenfeld beviste, at længden af ​​alle rækker af pixels, undtagen muligvis den første og den sidste, adskiller sig ikke med mere end en pixel. Han fandt også, at selve rækkefølgen af ​​pixels i sig selv har denne struktur, ligesom sekvensen af ​​disse sekvenser osv. Rasteriserede linjer er hierarkisk strukturerede fra rækker af " niende rækkefølge", som hver kun kan antage bestemte længder. Stephenson beskrev anvendelige algoritmer, der kan tegne en linje fra rækker af enhver høj orden samt en rekursiv algoritme, der starter fra den højest mulige rækkefølge. Dette generaliserer både Bresenham algoritmen og pixel række algoritmen. Algoritmen til rækker af "nul orden", hvor pixelrækkerne ignoreres, svarer til den sædvanlige Bresenham-algoritme.

Strukturelle algoritmer

Andre algoritmer er blevet foreslået til rasterisering, men de fungerer ikke trinvist, men bruger direkte de strukturelle egenskaber af de rasteriserede linjer. De er baseret på overvejelser fra billedbehandling eller digital geometri og opnår i praksis ikke hastigheden på konventionelle metoder, fordi de manipulerer tegnstrenge eller kræver andre langsomme operationer.

Brons 'algoritme repræsenterer for eksempel den rasteriserede linje med en streng af nuller og ener, hvor 0 står for vandret og 1 for et diagonalt trin. Algoritmen antager en tegnstreng, der repræsenterer en første tilnærmelse af linjen, kombinerer sekvenser af nuller og ener og fordeler dem jævnt. Den samme proces anvendes på den resulterende sekvens. Dette gentages, indtil der ikke kan opnås nogen yderligere forbedring. Linjen rasteriseret på denne måde er dog ikke optimal; For at få den samme linje som med Bresenham-algoritmen er der behov for yderligere justeringer.

Egenskaber og sammenligning

Selvom der er opdaget adskillige algoritmer, der er mindre komplekse end Bresenham-algoritmen, er deres praktiske hastighedsfordel lille. Dette skyldes, at instruktionerne til farvning af pixels på nutidens hardware er meget langsomme sammenlignet med udførelsen af ​​selve rasteralgoritmen. Nogle grafikkort giver dog noget hurtigere funktioner til farvning af flere pixels på én gang, såsom rectwrite- funktionen på SGI- systemer. Dette er en fordel for pixelrægealgoritmer, der hurtigt kan tegne en sådan række.

Udførelseshastigheden for de forskellige algoritmer afhænger af længden af ​​linjen, der skal rastreres. Algoritmer, hvis indre sløjfe er hurtig, men som kræver meget tid at initialisere, kan kun opnå en hastighedsfordel med lange linjer. Det blev derfor foreslået at vælge den mest effektive algoritme i hvert tilfælde som en funktion af længden af ​​linjen. En statistisk analyse af linjelængderne i forskellige applikationer såsom visning af trådrammemodeller, kurvesegmenter og tegn kom til, at næsten tre fjerdedele af alle rasteriserede linjer var mindre end ti pixels lange. Det er derfor umagen værd at optimere til det specielle tilfælde med korte linjer. Algoritmer, der er mere fordelagtige til rasterisering af lange linjer, er bedre egnet til outputenheder med en højere opløsning end skærme og dermed i gennemsnit længere linjer, såsom laserprintere. Med nogle algoritmer afhænger hastigheden også af linjens hældning - pixelrægalgoritmer er for eksempel mindre effektive med diagonale linjer, da kun en pixel pr. Række kan tegnes her.

En anden faktor ved valg af algoritme er programlængde. Producenter af grafikprocessorer, der implementerer rasterisering direkte på hardwareniveau og derfor skal spare plads, foretrækker korte algoritmer som Bresenham-algoritmen. I softwareimplementeringer er denne faktor mindre kritisk.

Problemer

Forskellige lysstyrker afhængigt af hældningen

Alle monokrome screeningsalgoritmer kan forårsage problemer i visse situationer:

Forskellig lysstyrke

Ved rasterisering af linjer med samme længde men forskellige gradienter er det samme antal pixels ikke nødvendigvis farvet. I det modsatte eksempel er den diagonale linje længere end den vandrette, men det samme antal pixels er farvet i begge tilfælde. Som et resultat ser de to linjer forskelligt lys ud på outputenheden. Dette problem kan ikke omgåes med monokrome enheder.

Linjestilarter

Brug af symmetri til at rastere linjer med ethvert start- og slutpunkt kan forårsage uønskede effekter, hvis visse linjestil bruges. Hvis der skal tegnes stiplede eller stiplede linjer, starter det respektive mønster ved linjens startpunkt. Sådanne linjer trækkes forskelligt, hvis start- og slutpunkterne byttes. Hvis stregerne i en linjestil er defineret af et bestemt antal pixels, der skal farves, varierer den faktiske slaglængde også afhængigt af gradienten.

Klipning

Dette klipning er en operation, der begrænser screeningen til et specifikt, normalt rektangulært område. Dette gøres ved at flytte start- og slutpunkterne på linjen, der skal rastreres, til kanterne på det rektangulære område, hvis de stikker ud. Generelt betyder dette, at koordinaterne for disse punkter ikke længere er heltal. Hvis disse koordinater alligevel er afrundede, er resultatet en linje med en anden hældning og dermed muligvis et andet udseende. For at undgå dette er yderligere tests nødvendige efter klipning. Bresenham-algoritmen kan også kombineres med en klippealgoritme.

Antialiasing

Det største problem med monokrome rasteriserede linjer er deres generelt "trappelignende" udseende, også kendt som trappeeffekten . Denne effekt kan modvirkes ved antialiasing på grafiske enheder, der er i stand til at vise flere lysstyrkeniveauer . Linjen, der skal rasteriseres, ses normalt ikke længere som en endimensionel linje, men som en todimensional form, i det enkleste tilfælde som et rektangel med den ønskede tykkelse. Til rasterisering skal farveværdierne på pixelerne i nærheden af ​​rektanglet bestemmes.

Metode til Gupta og Sproull

Illustration af den koniske udjævningskerne. Pixelens intensitet er proportional med lydstyrken V.

Ved antialiasing kan farveværdien af ​​en pixel bestemmes ved at placere en såkaldt udjævningskerne eller rekonstruktionsfilter over pixlen. Gupta og Sproull foreslog en kegle med en radius på en pixel som udjævningskerne . Pixelens farveværdi er proportional med volumenet på den del af keglen, der overlapper linjen, der skal rasteriseres (i dette tilfælde rektanglet, der skal rasteriseres). Denne lydstyrke afhænger igen af ​​afstanden mellem midterlinjen i rektanglet og pixlen. ${\ displaystyle D}$

De tre mulige pixels, der er farvet med en linjetykkelse på en pixel

Gupta-Sproull-algoritmen er baseret på Bresenham-algoritmen, men beregner også for hver af de pixels, hvis udjævningskerne overlapper linjen. Med en linjebredde på en pixel er dette maksimalt tre pixels pr. Kolonne. Af effektivitetshensyn beregnes afstande ikke nøjagtigt, kun 24 mulige afstande overvejes. Intensitetsværdierne svarende til disse afstande blev beregnet på forhånd og lagret i en tabel ( opslagstabel ), så de hurtigt kan kaldes op. ${\ displaystyle D}$

Linjeenderne skal behandles separat, da der er involveret mere end tre pixels, op til seks i alt. Intensiteten af ​​disse pixels afhænger af linjens hældning. De beregnes på forhånd for nogle stigninger og gemmes også i en tabel her. Andre former for linieenderne kan også tænkes, for eksempel afrundede slutpunkter; intensiteten af ​​de involverede pixels ændres i overensstemmelse hermed.

Gupta-Sproull-algoritmen er velegnet til linjer med enhver linjetykkelse, selvom opslagstabellen også ændres. Hvis linjebredden er større end en pixel, skal det bemærkes, at udjævningskerne på mere end tre pixels kan overlappe linjen.

Et problem med Gupta-Sproull-algoritmen er, at screenede linjer ofte ser ud til at have forskellig lethed forskellige steder. Dette "reblignende" udseende skyldes hovedsageligt keglens utilstrækkelighed som en udjævningskerne.

Metode til Wu

Beregning af intensiteterne i Wu-antialiasing

Wu tog en anden tilgang til antialiasing, baseret ikke på brugen af ​​en bestemt udjævningskerne, men på et mål for fejl. I sin grundlæggende form kan metoden kun bruges på ideelle, uendeligt tynde linjer.

Bresenham-algoritmen forsøger at tilnærme den ideelle linje ved at minimere "fejlen", dvs. afstanden mellem den ideelle linje og to mulige pixels. Wu foreslog et andet mål for fejl, der kan anvendes på enhver kurve. Fejlen i betydningen af ​​denne fejlmåling kan elimineres fuldstændigt, hvis nogen farveværdier er tilladt. For at gøre dette skal de to pixels, der er direkte over og under den ideelle linje, antage farveværdier, der er proportionale med den lodrette afstand til den ideelle linje.

Wu gav en særlig hurtig algoritme for linjer. Takket være smarte heltalshandlinger har han kun brug for en kontrolvariabel, som ændres trin for trin og bestemmer både placeringen af ​​de to involverede kolonnepixel og deres intensitet.

Andre teknikker

Forskellige anti-aliasing metoder ved hjælp af eksemplet på en CAD wire grid model. Fra venstre mod højre: Ingen antialiasing (Bresenham), Gupta-Sproull, uvægtet områdescanning og Wu.

En anden mulighed for antialiasing er ikke-vægtet arealprøveudtagning . Farveværdien af ​​en pixel svarer til arealdelen af ​​linjen inden for en firkant med en kantlængde på en pixel omkring den pågældende pixel, så glatningskernen er i dette tilfælde en terning. Hurtige algoritmer er blevet udviklet til denne metode. Ulempen ved ikke-vægtet områdescanning er linjernes slørede udseende.

Som med monokrom screening kan strukturen af ​​pixelrækkerne bruges til at øge screeningshastigheden.

Ud over anti-aliasing-processer, der er specielt optimeret til linjer, kan der også anvendes generelle processer, såsom Whitteds metode, hvor en rastergrafik med høj opløsning flyttes som en "børste" langs linjen.

Specielle optimeringer

Rasterisering af linjer kan gøres endnu mere effektiv gennem tilnærmelsesmetoder, brug af eller direkte implementering i hardware og parallelisering . Dette er nødvendigt, når et meget stort antal linjer skal rastreres i realtid .

Tilnærmelsesmetode

Boyer og Bourdin præsenterede en tilnærmelsesmetode, der altid farver pixelerne direkte under den ideelle linje. En sådan rasteriseret linje har nogle specielle egenskaber, der kan udnyttes. I dette tilfælde er for eksempel ikke kun Bresenham-kontrolvariablen, men også linjesegmenterne periodiske. Sammen med yderligere optimeringer resulterer dette i en algoritme, der er betydeligt hurtigere end den nøjagtige metode, især med længere linjer. En forringelse af kvaliteten kan ses i tilfælde af linjer med meget lav hældning.

Parallelisering

En enkel metode til parallelisering af monokrom rasterisering tillader forskellige algoritmer at køre parallelt, der - hver forskudt let - tegner flere pixels med bestemte intervaller. En anden mulighed er at opdele linjen i flere omtrent lige store dele, som hver er tildelt en processor til rasterisering. Hver del gengives ved hjælp af Bresenham-algoritmen; hovedproblemet er at beregne de korrekte startværdier for variablerne. Det er også muligt at få flere processorer til at beregne slutpunktskoordinaterne for rækkerne ved hjælp af Bresenhams pixelræalgoritme. Algoritmer blev også præsenteret for vektorcomputere, der arbejder massivt parallelt med over 1000 processorer. Hver pixel af rastergrafikken tildeles en processor, der bestemmer, om denne pixel skal være farvet eller ej.

For at fremskynde den langsomme hukommelsesadgang under rasterisering er der udviklet specielle hukommelsesarkitekturer, for eksempel dem, hvor hukommelsen er opdelt i celler, hvor en del af linjen kan tegnes uafhængigt af hinanden. Screeningen med antialiasing kan også understøttes af hardware.

Relaterede problemer

4-koblet gitter. Kvadraterne valgt ud over det 8-tilsluttede gitter vises skraveret.

Linjer kan ikke kun være 8-tilsluttet som normalt er tilfældet, men også 4-tilsluttede (4-tilsluttede) . Dette betyder, at ingen diagonale trin, men kun vandrette og lodrette trin er tilladt. Hvis du tænker på punktgitteret opdelt i firkanter, vælges alle de firkanter, der overlappes af linjen. En generalisering af denne teknik til tre dimensioner anvendes i voxel gitter, en accelerationsteknik til strålesporing . Det bruges til at bestemme de voxels, gennem hvilke en stråle bevæger sig under strålesporing.

I tilfælde af rasteriserede linjer fordeles de diagonale pixeltrin så jævnt som muligt. Algoritmer til rasterisering af linjer kan derfor også bruges til at distribuere punkter med heltalskoordinater jævnt i et bestemt interval . Mulige anvendelser er lineær interpolering eller nedprøve i signalbehandling. Der er yderligere paralleller til den euklidiske algoritme såvel som Farey-serierne og nogle andre matematiske konstruktioner.

litteratur

• James D. Foley, blandt andre: Computer Graphics: Principles and Practice i C . Addison-Wesley, Reading (Massachusetts) 1995, ISBN 978-0-201-84840-3 . (Dækker Bresenhams algoritme, rasteriseringsproblemer og Gupta-Sproull-antialiasing) 

Individuelle artikler:

Denne liste er et valg; en detaljeret bibliografi er inkluderet i Stephensons afhandling.

1. ↑ Se prøve kode i http://www.crbond.com/papers/newline.pdf (250 kB)
2. ^ Algoritme til computerstyring af en digital plotter. IBM Systems Journal 4, 1 (1965): 25-30, ISSN  0018-8670 ( PDF, 220 kB ). Allerede præsenteret i august 1963 som et foredrag på ACM National Conference i Denver.
3. ↑ Mike LV Pitteway: Algoritme til tegning af ellipser eller hyperboler med en digital plotter. Computerjournal 10, 3 (november 1967): 282-289, ISSN  0010-4620
4. ^ JR Thompson: Korrespondance: Lige linjer og grafplottere. Computerjournal 7, 3 (august 1964): 227
5. ↑ Fred G. Stockton: Algoritme 162: XYmove-plotning. Kommunikation af ACM 6, 4 (april 1963): 161, ISSN  0001-0782
6. ↑ Giovanni B. Reggiori: digital computer transformationer for uregelmæssige stregtegninger. Teknisk rapport 403-22, New York University, New York, april 1972
7. ^ Jack E. Bresenham et al .: Kør længdeskiver til trinvise linjer. IBM Technical Bulletin 22-28B (1980): 3744-3747, ISSN  0018-8689
8. ↑ ^{a b} Khun Yee Fung: En algoritme, der kører i længderetning af skivelinjer uden divisionoperationer. Computer Graphics Forum 11, 3 (1992): 267-277, ISSN  0167-7055
9. ↑ Xiaolin Wu, Jon G. Rokne: Dobbelt-trins inkrementel generation af linjer og cirkler. Computersyn, grafik og billedbehandling 37,3 (marts 1987): 331-344, ISSN  0734-189X
10. ↑ Phil Graham, S. Sitharama Iyengar: Dobbelt- og tredobbelt trinvis trinvis generering af linjer. I ACM CSC '93 Forløb: 384-389. ACM Press, Indianapolis 1993, ISBN 0-89791-558-5
11. ^ Paul Bao, Jon G. Rokne: Generering af firdobbelt linie. Computere og grafik 13, 4 (1989): 461-469, ISSN  0097-8493
12. ^ Graeme W. Gill: N-trin inkrementelle lige linjealgoritmer. IEEE computergrafik og applikationer 14, 3 (maj 1994): 66-72, ISSN  0272-1716
13. ↑ ^{a b} Giulio Casciola: Grundlæggende begreber til at fremskynde linjealgoritmer . Computere og grafik 12, 3/4 (1988): 489-502
14. ^ Azriel Rosenfeld: Digital lige linjesegmenter. IEEE-transaktioner på computere C-23, 12 (december 1974): 1264-1269, ISSN  0018-9340
15. ^ ^{A b} Peter Stephenson: Strukturen af ​​den digitaliserede linje: med applikationer til linjetegning og strålesporing i computergrafik. Ph.d.-afhandling, James Cook University of North Queensland, Australien, 1998 ( online ( Memento fra 5. september 2007 i internetarkivet ))
16. ^ Reyer Brons: sproglige metoder til beskrivelse af en lige linje på et gitter. Computergrafik og billedbehandling 3 (1974): 48-62, ISSN  0146-664X
17. ^ Jim X. Chen: Analysen og statistikken over linjefordeling. IEEE computergrafik og applikationer 22, 6 (november / december 2002): 100-107
18. ^ Yevgeny P. Kuzmin: Bresenhams linjegenerationsalgoritme med indbygget klipning. Computer Graphics Forum 14, 5 (1995): 275-280
19. ↑ Satish Gupta, Robert F. Sproull: Filtrering af kanter til gråskalaer. I ACM SIGGRAPH '81 Forløb: 1-5. ACM Press, Dallas 1981, ISBN 0-89791-045-1
20. ^ AR Forrest: Antialiasing i praksis. I RA Earnshaw (red.): Fundamental Algorithms for Computer Graphics (= NATO ASI Series F.17): 113-134. Springer, Berlin 1985, ISBN 3-540-13920-6
21. ↑ Xiaolin Wu: En effektiv antialiasing-teknik. I ACM SIGGRAPH '91 Forløb: 143-152. ACM Press, New York 1991, ISBN 0-89791-436-8
22. ↑ Se for eksempel Vincent Boyer, Jean-Jacques Bourdin: Diskret analyse for antialistiske linjer. Kort præsentation, Eurographics 2000 ( PDF, 230 kB )
23. ↑ Nicholas A. Diakopoulos, Peter D. Stephenson: Anti-aliasede linjer ved hjælp af køremasker. Computer Graphics Forum 24, 2 (juni 2005): 165-172
24. ^ Turner Whitted: Anti-alias stregtegning ved hjælp af penselekstrudering. I ACM SIGGRAPH '83 Forhandlinger: 151-156. ACM Press, Detroit 1983, ISBN 0-89791-109-1
25. ↑ Vincent Boyer, Jean-Jacques Bourdin: Fast Lines: a Span by Span Method. Computer Graphics Forum 18, 3 (1999): 377–384 ( PDF, 400 kB )
26. ^ Robert F. Sproull: Brug af programtransformationer til at udlede algoritmer for stregtegning. ACM-transaktioner på grafik 1,4 (oktober 1982): 259-273, ISSN  0730-0301
27. ^ William E. Wright: Parallelisering af Bresenhams linje- og cirkealgoritmer. IEEE computergrafik og applikationer 10, 5 (september 1990): 60-67
28. ↑ Ivo Považan, Tomáš Hrúz: Parallellinje: en samlet løsning. I WSCG '97 Proceedings: 60-67. University of West Bohemia, Pilsen 1997, ISBN 80-7082306-2 ( online )
29. ↑ Alex T. Pang: Linje-tegning algoritmer for parallelle maskiner. IEEE computergrafik og applikationer 10, 5 (september 1990): 54-59
30. ↑ Se for eksempel Pere Marès Martí, Antonio B. Martínez Velasco: Hukommelsesarkitektur til parallel linjetegning baseret på ikke-inkrementel algoritme. I: Euromicro 2000 Proceedings: Vol. 1, 266-273. IEEE Computer Society Press, Los Alamitos 2000, ISBN 0-7695-0780-8
31. ↑ Se for eksempel Robert McNamara et al.: Forfiltrerede antialiaserede linjer ved hjælp af halvflyvningsfunktioner. I HWWS 2000 Procedurer: 77-85. ACM Press, New York 2000, ISBN 1-58113-257-3
32. ↑ Chengfu Yao, Jon G. Rokne: En integreret lineær interpolation indfaldsvinkel til udformning af enkeltprøver line algoritmer. Journal of Computational and Applied Mathematics 102, 1 (februar 1999): 3-19, ISSN  0377-0427
33. ^ Mitchell A. Harris, Edward M. Reingold: Linjetegning, skudår og Euclid. ACM Computing Surveys 36, 1 (marts 2004): 68–80, ISSN  0360-0300 ( PDF, 270 kB ( Memento fra 16. december 2006 i internetarkivet ))

Weblinks

• Bresenhams algoritme (NIST Dictionary of Algorithms and Data Structures) - Baggrund for Bresenham-algoritmen med original kildekode
• Rasterisering af linjer, cirkler, ellipser (University of Magdeburg, Institute for Simulation and Graphics) - Java-applet for at forstå Bresenham-algoritmen
• Projekt: Linjestatistik (George Mason University Computer Graphics Lab) - Undersøgelse af fordelingen af ​​linjelængder og skråninger
• Skønheden ved Bresenhams algoritme - En simpel implementering til tegning af linjer, cirkler, ellipser og Bézier-kurver

Denne artikel blev tilføjet til listen over fremragende artikler den 4. maj 2007 i denne version .