Gjengivelse av skanning - Scanline rendering
Gjengivelse av skanning (også skanning av gjengivelse og gjengivelse av skannelinjer ) er en algoritme for bestemmelse av synlig overflate , i 3D-datagrafikk , som fungerer rad-for-rad-basis snarere enn en polygon- av-polygon eller piksel- av-piksel basis. Alle polygonene som skal gjengis, sorteres først etter den øverste y-koordinaten der de først vises, deretter beregnes hver rad eller skannelinje i bildet ved hjelp av skjæringspunktet mellom en skannelinje og polygonene foran på den sorterte listen, mens den sorterte listen oppdateres for å forkaste polygoner som ikke lenger er synlige ettersom den aktive skannelinjen avanseres nedover i bildet.
Den største fordelen med denne metoden er at sortering av hjørner langs normal for skanningsplanet reduserer antall sammenligninger mellom kanter. En annen fordel er at det ikke er nødvendig å oversette koordinatene til alle hjørnene fra hovedminnet til arbeidsminnet - bare hjørner som definerer kanter som skjærer den gjeldende skannelinjen, må være i aktivt minne, og hvert toppunkt blir lest inn bare en gang. Hovedminnet er ofte veldig tregt i forhold til koblingen mellom sentralbehandlingsenheten og hurtigminneminnet , og det kan dermed gi en betydelig hastighet å unngå å få tilgang til hjørnene igjen i hovedminnet.
Denne typen algoritme kan enkelt integreres med mange andre grafiske teknikker, for eksempel Phong-refleksjonsmodellen eller Z- bufferalgoritmen.
Algoritme
Den vanlige metoden starter med kanter av projiserte polygoner satt inn i bøtter, en per skannelinje; rasterizer har et aktivt kantbord ( AET ). Oppføringer opprettholder sorteringskoblinger, X-koordinater, graderinger og referanser til polygonene de bundet. For å rastere neste skannelinje fjernes ikke lenger kantene. nye kanter fra gjeldende scanlines Y-bøtte legges til, settes inn sortert etter X-koordinat. De aktive kanttabelloppføringene har X og annen parameterinformasjon inkrementert. Aktive kanttabelloppføringer opprettholdes i en X-sortert liste etter boblesortering , noe som medfører en endring når to kanter krysser. Etter oppdatering av kanter krysses den aktive kanttabellen i X for å kun avgi de synlige spennene, vedlikeholde en Z-sortert aktiv span-tabell, sette inn og slette overflatene når kantene krysses.
Varianter
En hybrid mellom denne og Z-buffringen fjerner den aktive kanttabellsorteringen, og rasteriser i stedet en skannelinje om gangen til en Z-buffer, og opprettholder aktive polygon-spenn fra en skannelinje til den neste.
I en annen variant rastreres en ID-buffer i et mellomtrinn, slik at utsatt skyggelegging av de resulterende synlige pikslene tillates .
Historie
Den første publikasjonen av scanline-gjengivelsesteknikken var sannsynligvis av Wylie, Romney, Evans og Erdahl i 1967.
Andre tidlige utviklinger av scanline-gjengivelsesmetoden var av Bouknight i 1969, og Newell, Newell og Sancha i 1972. Mye av det tidlige arbeidet med disse metodene ble gjort i Ivan Sutherlands grafikkgruppe ved University of Utah og i Evans & Sutherland- selskap i Salt Lake City .
Brukes i sanntid gjengivelse
Den tidlige Evans & Sutherland ESIG-linjen med bildegeneratorer (IG-er) benyttet teknikken innen maskinvare 'on the fly', for å generere bilder en rasterlinje om gangen uten rammebuffer , noe som sparer behovet for deretter kostbart minne. Senere varianter brukte en hybrid tilnærming.
The Nintendo DS er den nyeste maskinvaren til å gjengi 3D-scener på denne måten, med mulighet for caching det rastrerte bilder til VRAM.
Den sprite maskinvare utbredt i 1980 spill maskiner kan betraktes som en enkel 2D form av avsøkningslinje-gjengivelse.
Teknikken ble brukt i den første Quake-motoren for gjengivelse av programvare for miljøer (men objekter i bevegelse ble Z-bufret over toppen). Statisk landskap brukte BSP- avledet sortering for prioritet. Det viste seg bedre enn Z-buffer / malers typealgoritmer ved håndtering av scener med høy dybdekompleksitet med kostbare pikseloperasjoner (dvs. perspektivkorrekt teksturkartlegging uten maskinvareassistanse). Denne bruken gikk foran den utbredte adopsjonen av Z-bufferbaserte GPUer som nå er vanlige i PC-er.
Sony eksperimenterte med programvarescanline-renderere på en annen Cell- prosessor under utviklingen av PlayStation 3 , før de slo seg ned på et konvensjonelt CPU / GPU-arrangement.
Lignende teknikker
Et lignende prinsipp er brukt i flislagt gjengivelse (mest kjent PowerVR 3D-brikken); det vil si at primitiver blir sortert på skjermplass, og deretter gjengitt i raskt on-chip-minne, en flis om gangen. Den Dreamcast gitt en modus for rastrering en rad med fliser på et tidspunkt for direkte raster avsøkningsprosedyre, sparer behovet for en komplett framebuffer, noe i ånden av maskinvare scanline gjengivelse.
Noen programvare rasterizers bruker 'span buffering' (eller 'dekning buffering'), der en liste over sorterte, klippte spenn er lagret i scanline bøtter. Primitiver vil bli suksessivt lagt til i denne datastrukturen, før de bare synliggjør de synlige pikslene i en sluttfase.
Sammenligning med Z-buffer algoritme
Den største fordelen med scanline-gjengivelse fremfor Z-buffering er at antall ganger synlige piksler behandles holdes til det absolutte minimum, som alltid er en gang hvis ingen transparenseffekter brukes - en fordel for høyresolus eller dyre skyggeberegninger .
I moderne Z-buffersystemer kan lignende fordeler oppnås gjennom grov front-to-back-sortering (nærmer seg 'reverse malere-algoritmen'), tidlig Z-avvisning (i forbindelse med hierarkisk Z) og mindre vanlige utsatte gjengivelsesteknikker mulig på programmerbare GPUer.
Scanline-teknikker som arbeider på rasteren har den ulempen at overbelastning ikke håndteres elegant.
Teknikken anses ikke å skalere godt ettersom antallet primitiver øker. Dette er på grunn av størrelsen på mellomliggende datastrukturer som kreves under gjengivelse - som kan overstige størrelsen på en Z-buffer for en kompleks scene.
Derfor, i moderne interaktive grafiske applikasjoner, har Z-bufferen blitt allestedsnærværende. Z-bufferen lar større volumer av primitiver krysse lineært, parallelt, på en måte som er vennlig mot moderne maskinvare. Transformerte koordinater, attributtgraderinger osv. Trenger aldri å forlate grafikkbrikken. bare de synlige pikslene og dybdeverdiene er lagret.
