Ray casting - Ray casting
Ray casting er det metodologiske grundlag for 3D-CAD/CAM solid modellering og billedgengivelse. Det er i det væsentlige det samme som strålesporing til computergrafik, hvor virtuelle lysstråler "støbes" eller "spores" på deres vej fra et kameras brændpunkt gennem hver pixel i kamerasensoren for at bestemme, hvad der er synligt langs strålen i 3D-scene. Udtrykket "Ray Casting" blev introduceret af Scott Roth, mens han var på General Motors Research Labs fra 1978-1980. Hans papir, "Ray Casting for Modeling Solids", beskriver modellerede faste objekter ved at kombinere primitive faste stoffer, såsom blokke og cylindre, ved hjælp af sætoperatørernes forening (+), skæringspunkt (&) og forskel (-). Den generelle idé om at bruge disse binære operatører til solid modellering skyldes i høj grad Voelcker og Requichas geometriske modelleringsgruppe ved University of Rochester. Se Solid modellering for en bred oversigt over solide modelleringsmetoder. Denne figur til højre viser en U-Joint modelleret efter cylindre og blokke i et binært træ ved hjælp af Roths ray casting system, omkring 1979.
Inden stråling (og strålesporing) projicerede computergrafikalgoritmer overflader eller kanter (f.eks. Linjer) fra 3D-verden til billedplanet, hvor der skulle anvendes synlighedslogik. Verden-til-billede-planprojektionen er en 3-D homogen koordinatsystemtransformation (aka: 3D-projektion , affin transformation eller projektiv transformation ( Homografi )). At gengive et billede på den måde er svært at opnå med fjernelse af skjult overflade/kant. Plus, silhuetter af buede overflader skal eksplicit løses for, mens det er et implicit biprodukt af strålingstøbning, så det er ikke nødvendigt eksplicit at løse det, når udsigten ændrer sig.
Ray casting meget forenklet billedgengivelse af 3D-objekter og scener, fordi en linje omdannes til en linje. Så i stedet for at projicere buede kanter og overflader i 3D-scenen til 2-D billedplanet, skæres transformerede linjer (stråler) med objekterne i scenen. En homogen koordinattransformation er repræsenteret ved 4x4 matrix. Den matematiske teknik er fælles for computergrafik og geometrisk modellering. En transformation omfatter rotationer omkring de tre akser, uafhængig skalering langs akserne, oversættelser i 3-D og endda skævvridning. Transformer er let sammenkædet via matrix -aritmetik. Til brug med en 4x4 -matrix repræsenteres et punkt med [X, Y, Z, 1], og en retningsvektor repræsenteres af [D x , D y , D z , 0]. (Det fjerde udtryk er for oversættelse, og det gælder ikke for retningsvektorer.)
Selvom matematikken forenkles, er ray casting-algoritmen meget computerbehandlingskrævende. Pixar har store render -gårde, bygninger med tusindvis af CPU'er, til at lave deres animationer ved hjælp af ray tracing [alias "ray casting"] som en kerneteknik.
Koncept
Ray støbning er den mest grundlæggende af mange computergrafik rendering algoritmer, der bruger geometriske algoritme ray tracing . Strålesporingsbaserede gengivelsesalgoritmer fungerer i billedrækkefølge for at gengive tredimensionelle scener til todimensionale billeder. Geometriske stråler spores fra observatørens øje for at prøve lyset ( udstråling ), der bevæger sig mod observatøren fra stråleretningen. Hastigheden og enkelheden ved strålekastering kommer fra at beregne lysets farve uden rekursivt at spore yderligere stråler, der prøver strålingshændelsen på det punkt, som strålen ramte. Dette eliminerer muligheden for nøjagtigt at gengive refleksioner , brydninger eller det naturlige fald af skygger ; men alle disse elementer kan falskes til en vis grad ved kreativ brug af teksturkort eller andre metoder. Den høje beregningshastighed gjorde ray casting til en praktisk gengivelsesmetode i tidlige 3D-videospil i realtid .
Ideen bag strålekastning er at spore stråler fra øjet, en pr. Pixel, og finde det nærmeste objekt, der blokerer denne stråles vej-tænk på et billede som en skærmdør, hvor hver firkant på skærmen er en pixel. Dette er så det objekt, øjet ser gennem den pixel. Ved hjælp af materialegenskaberne og effekten af lysene i scenen kan denne algoritme bestemme skyggen af dette objekt. Den forenklede antagelse antages, at hvis en overflade står over for et lys, vil lyset nå denne overflade og ikke blive blokeret eller i skygge. Skyggen af overfladen beregnes ved hjælp af traditionelle 3D computergrafik skygge modeller. En vigtig fordel ved strålingstøbning, der tilbydes i forhold til ældre scanlinealgoritmer, var dens evne til let at håndtere ikke-plane overflader og faste stoffer, såsom kegler og kugler . Hvis en matematisk overflade kan skæres af en stråle, kan den gengives ved hjælp af stråling. Udførlige objekter kan oprettes ved hjælp af solide modelleringsteknikker og let gengives.
Fra abstraktet til papiret "Ray Casting for Modeling Solids": For at visualisere og analysere de modellerede sammensatte faste stoffer støbes virtuelle lysstråler som sonder. I kraft af sin enkelhed er strålestøbning pålidelig og udvidelig. Det vanskeligste matematiske problem er at finde skæringspunkter for linje-overflade. Så overflader som fly, kvadriker, tori og sandsynligvis endda parametriske overfladeplaster kan binde de primitive faste stoffer. Strålestøbningens tilstrækkelighed og effektivitet er spørgsmål, der behandles her. En hurtig billedgenereringsevne til interaktiv modellering er den største udfordring.
Lysstråler og kameraets geometri danner grundlaget for al geometrisk begrundelse her. Denne figur viser en pinhole -kameramodel til perspektiveffekt i billedbehandling og en parallel kameramodel til masseanalyse. Den enkle pinhole -kameramodel består af et brændpunkt (eller øjenpunkt) og en firkantet pixel array (eller skærm). Lige lysstråler passerer gennem pixelarrayet for at forbinde fokuspunktet med scenen, en stråle pr. Pixel. For at skygge billeder måles strålernes intensitet og gemmes som pixels. Den reflekterende overflade, der er ansvarlig for en pixels værdi, skærer pixelens stråle.
Når brændvidden, afstanden mellem brændpunktet og skærmen, er uendelig, så kaldes udsigten "parallel", fordi alle lysstråler er parallelle med hinanden, vinkelret på skærmen. Selvom perspektivvisningen er naturlig til at lave billeder, har nogle applikationer brug for stråler, der kan fordeles ensartet i rummet.
For at gøre det lettere at modellere har et typisk standardkoordinatsystem for kameraet skærmen i XY -planet, scenen i +Z -halvrummet og fokuspunktet på -Z -aksen.
En stråle er simpelthen en lige linje i kameramodellens 3D-rum. Det defineres bedst som en retningsvektor i parameteriseret form som et punkt (X 0 , Y 0 , Z 0 ) og en retningsvektor (D x , D y , D z ). I denne form bestilles og tilgås punkter på linjen via en enkelt parameter t. For hver værdi af t defineres et tilsvarende punkt (X, Y, Z) på linjen:
X = X0 + t · Dx Y = Y0 + t · Dy Z = Z0 + t · Dz
Hvis vektoren er normaliseret, er parameteren t afstanden langs linjen. Vektoren kan let normaliseres med følgende beregning:
Dist = √(Dx2 + Dy2 + Dz2) Dx = Dx / Dist Dy = Dy / Dist Dz = Dz / Dist
I betragtning af geometriske definitioner af objekterne, hver afgrænset af en eller flere overflader, er resultatet af beregning af en stråles skæringspunkt med alle afgrænsede overflader på skærmen defineret af to arrays,
Ray parameters: t[1], t[2], ..., t[n] Surface pointers: S[1], S[2], ..., S[n]
hvor n er antallet af stråleoverfladekrydsninger. Den ordnede liste over stråleparametre t [i] betegner indgangs- og udgangspunkterne. Strålen kommer ind i et fast stof ved punkt t [1], forlader ved t [2], går ind i et fast stof ved t [3] osv. Punkt t [1] er tættest på kameraet og t [n] er længst. I forbindelse med stråleparametrene indeholder overfladepegene en unik adresse til den skærede overflades information. Overfladen kan have forskellige egenskaber såsom farve, specularitet, gennemsigtighed med/uden brydning, gennemskinnelighed osv. Det faste stof, der er forbundet med overfladen, kan have sine egne fysiske egenskaber, såsom densitet. Dette kan f.eks. Være nyttigt, når et objekt består af en samling af forskellige materialer, og det overordnede massecenter og inertimomenter er af interesse.
Anvendelse af oplysningerne
Tre algoritmer, der anvender strålingstøbning, er at lave stregtegninger, lave skyggefulde billeder og beregne mængder og andre fysiske egenskaber. Hver algoritme, givet en kameramodel, kaster en stråle pr. Pixel i skærmen. For computervolumen afhænger opløsningen af den pixelskærm, der skal bruges, af den ønskede nøjagtighed af løsningen. Ved stregtegninger og billedskygning bestemmer opløsningen billedets kvalitet.
LINE TEGNINGER . For at tegne de synlige kanter af et fast stof skal du generere en stråle pr. Pixel, der bevæger sig ovenfra og ned, til venstre og højre på skærmen. Evaluer hver stråle for at identificere den synlige overflade S [1], den første overflademarkør i den sorterede liste over stråleoverfladekryds. Hvis den synlige overflade ved pixelplacering (X, Y) er forskellig fra den synlige overflade ved pixel (X-1, Y), skal du derefter vise en lodret linje, en pixel lang centreret ved (X-½, Y). På samme måde, hvis den synlige overflade ved (X, Y) er forskellig fra den synlige overflade ved pixel (X, Y-1), skal du derefter vise en vandret linje, en pixel lang centreret ved (X, Y-½). Den resulterende tegning vil kun bestå af vandrette og lodrette kanter, der ser ujævn ud i kursopløsninger.
Roths ray casting system genererede billederne af faste objekter til højre. Kasseindkapslinger, dynamisk afgrænsning og sammenhæng blev brugt til optimering. For hvert billede blev skærmen prøvetaget med en densitet på ca. 100x100 (f.eks. 10.000) stråler, og nye kanter blev lokaliseret via binære søgninger. Derefter blev alle kanter fulgt af støbning af yderligere stråler i trin på et pixel på de to sider af kanterne. Hvert billede blev tegnet på et Tektronix -rør med en opløsning på 780x780.
SKUGGET BILLEDER . For at lave et skraveret billede skal du igen kaste en stråle pr. Pixel på skærmen. Denne gang skal du dog bruge den synlige overflademarkør S [1] ved hver pixel for at få adgang til beskrivelsen af overfladen. Ud fra dette beregnes overfladen normal på det synlige punkt t [1]. Pixelens værdi, den synlige lysintensitet, er proportional med cosinus af den vinkel, der dannes af overfladens normale og lyskilden-til-overfladevektoren. Behandling af alle pixels på denne måde giver et raster-billede af scenen.
BEREGNINGSMÆSSIGHED OG TRYGMOMENTER . Volumen (og lignende egenskaber) af et fast stof, der er afgrænset af buede overflader, beregnes let ved hjælp af integrationsmetoden "omtrentlige summer" ved at tilnærme det faste stof med et sæt rektangulære parallelepipeder. Dette opnås ved at tage et "dybtgående" billede af det faste stof i en parallel visning. Kaster stråler gennem skærmen ind i de faste partitioner det faste stof i volumenelementer. To dimensioner af parallelepipederne er konstante, defineret af 2-D-afstanden mellem stråler i skærmen. Den tredje dimension er variabel, defineret af det beregnede enter-exit-punkt. Hvis den vandrette og lodrette afstand mellem strålerne på skærmen specifikt er S, er volumen "detekteret" af hver stråle
S × S × (t[2]-t[1] + t[4]-t[3] + ∙∙∙ + t[n]-t[n-1]) / L
hvor L er defineret som længden af retningsvektoren. (Hvis det allerede er normaliseret, er dette lig med 1.)
L = √(Dx2 + Dy2 + Dz2)
Hver ( t [ i ] - t [ i -1])/L er en længde af et strålesegment, der er inde i det faste stof.
Denne figur viser parallelepipeds for et modelleret fast stof ved hjælp af stråle -støbning. Dette er en brug af parallel-projektion kamera model.
In-Out stråleklassificering
Denne figur viser et eksempel på de binære operatorer i et sammensætningstræ ved hjælp af + og - hvor en enkelt stråle evalueres.
Strålestøbningsproceduren starter øverst på det faste sammensætningstræ, falder rekursivt ned til bunden, klassificerer strålen i forhold til de primitive faste stoffer og vender derefter tilbage til træet, der kombinerer klassifikationerne af venstre og højre undertræ.
Denne figur illustrerer kombinationen af venstre og højre klassifikationer for alle tre binære operatører.
Realistiske skyggefulde billeder
Ray casting er et naturligt modelleringsværktøj til at lave skyggefulde billeder. Det gråtonestrålingssystem, der blev udviklet af Scott Roth og Daniel Bass på GM Research Labs, producerede billeder på et Ramtek-farve raster-display omkring 1979. For at komponere billeder forsynede systemet brugeren med følgende betjeningselementer:
View
• Viewing direction and position
• Focal length: width-angle perspective to parallel
• Zoom factor
Illumination
• Number of light sources
• Locations and intensities of lights
• Optionally shadow
• Intensities of ambient light and background
Surface Reflectance
• % reflected diffusely
• % reflected specularly
• % transmitted
Denne figur viser en bordscene med skygger fra to punktlyskilder.
Skygge -algoritmer, der implementerer alle de realistiske effekter, er beregningsmæssigt dyre, men relativt enkle. For eksempel viser den følgende figur de ekstra stråler, der kan støbes for en enkelt lyskilde.
For at en enkelt pixel i billedet skal gengives, kaster algoritmen en stråle, der starter ved brændpunktet og bestemmer, at den skærer et halvgennemsigtigt rektangel og en skinnende cirkel. En yderligere stråle skal derefter støbes fra det tidspunkt i den retning symmetrisk modsat overfladen, der er normal ved skæringspunktet for stråleoverfladen, for at bestemme, hvad der er synligt i den spejlede refleksion. Denne stråle skærer trekanten, som er uigennemsigtig. Endelig testes hvert stråleoverflade-skæringspunkt for at afgøre, om det er i skygge. "Shadow feeler" -strålen støbes fra stråleoverfladeens skæringspunkt til lyskilden for at afgøre, om en anden overflade blokerer denne vej.
Turner Whitted kalder de sekundære og ekstra stråler "Recursive Ray Tracing". [Et rum med spejle ville være dyrt at gengive, så det er forsigtigt at begrænse antallet af recursioner.] Whited modelleret brydning for transparenter ved at generere en sekundær stråle fra det synlige overfladepunkt i en vinkel bestemt af faststoffets brydningsindeks. Den sekundære stråle behandles derefter som en spekulær stråle. For refraktionsformlen og billedeksempler, se Whitted's paper.
Kabinetter og effektivitet
Ray casting kvalificerer sig som en brute force metode til at løse problemer. Den minimale algoritme er enkel, især i betragtning af dens mange applikationer og brugervenlighed, men applikationer kaster typisk mange stråler. Millioner af stråler kan støbes for at gengive et enkelt billede af en animationsfilm. Computerens behandlingstid øges med skærmens opløsning og antallet af primitive faste stoffer/overflader i sammensætningen.
Ved at bruge minimale afgrænsningsbokse omkring de faste stoffer i sammensætningstræet ligner den udtømmende søgning efter et strålefast skæringspunkt en effektiv binær søgning. Brute force-algoritmen foretager en udtømmende søgning, fordi den altid besøger alle knuderne i træet-omdanner strålen til primitivers lokale koordinatsystemer, tester for kryds-overfladekryds og kombinerer klassifikationerne-selv når strålen klart savner det faste stof. For at opdage en "klar glip" bruger en hurtigere algoritme det binære sammensætningstræ som en hierarkisk fremstilling af det rum, den faste sammensætning indtager. Men alle oplysninger om position, form og størrelse gemmes på træets blade, hvor primitive faste stoffer opholder sig. De øverste og mellemliggende noder i træet angiver kun mejetærskeroperatorer.
Karakteriserer med kabinetter det rum, som alle faste stoffer fylder, giver alle knuder i træet et abstrakt resumé af positions- og størrelsesinformation. Derefter styrer de hurtige "stråle skærer kabinet" -tests søgningen i hierarkiet. Når testen mislykkes ved en mellemliggende node i træet, vil strålen garanteret klassificeres som ude af kompositmaterialet, så det er unødvendigt at tilbagekalde dens undertræer for yderligere undersøgelse.
Det er svært at vurdere omkostningsbesparelserne ved brug af kabinetter nøjagtigt, fordi det afhænger af primitivernes rumlige fordeling (kompleksitetsfordelingen) og sammensætningstræets organisering. De optimale betingelser er:
- Ingen primitive indhegninger overlapper hinanden i rummet
- Sammensætningstræ er afbalanceret og organiseret, så sub-faste stoffer i nærheden af rummet også er i nærheden i træet
I modsætning hertil er den værste tilstand:
- Alle primitive kabinetter overlapper hinanden
Følgende er diverse ydelsesforbedringer foretaget i Roths papir om stråling, men der er efterfølgende foretaget betydelige forbedringer af andre.
- Tidlige outs . Hvis operatøren på en sammensat knude i træet er-eller & og strålen klassificeres som ud af komposittets venstre underfaste stof, klassificeres strålen som ude af kompositmaterialet uanset stråleklassificering med hensyn til det højre under- solid. Så det er unødvendigt at klassificere strålen med hensyn til det rigtige sub-fast stof og bør undgås for effektivitet.
- Transformationer . Ved i første omgang at kombinere skærm-til-scene-transformationen med primitivets scene-til-lokale transformation og lagre de resulterende skærm-til-lokale transformationer i primitivens datastrukturer, elimineres en stråeltransformation pr. Stråleoverfladekryds.
- Rekursion . I betragtning af et dybt sammensætningstræ kan rekursion være dyr i kombination med tildeling og frigørelse af hukommelse. Rekursion kan simuleres ved hjælp af statiske arrays som stakke.
- Dynamisk afgrænsning . Hvis kun de synlige kanter af det faste stof skal vises, kan strålestøbningsalgoritmen dynamisk binde strålen til at afbryde søgningen. Det vil sige, efter at have fundet ud af, at en stråle skærer et sub-fast stof, kan algoritmen bruge skæringspunktet tættest på skærmen til at stramme den dybde, der er begrænset til "stråle skæringsboksen" -testen. Dette fungerer kun for + delen af træet, der starter øverst. Med - og & kan nærliggende “in” dele af strålen senere blive “ude”.
- Sammenhæng . Princippet om sammenhæng er, at de overflader, der er synlige ved to nabopixel, mere sandsynligt er de samme end forskellige. Udviklere af computergrafik og vision -systemer har anvendt denne empiriske sandhed for effektivitet og ydeevne. For stregtegninger er billedområdet, der indeholder kanter, normalt meget mindre end det samlede billedareal, så stråleudstøbning bør koncentreres omkring kanterne og ikke i de åbne områder. Dette kan effektivt implementeres ved sparsom prøveudtagning af skærmen med stråler og derefter lokalisere, når nabostråler identificerer forskellige synlige overflader, kanterne via binære søgninger.
Anti-aliasing
De hakkede kanter forårsaget af aliasing er en uønsket effekt af teknikker til punktsampling og er et klassisk problem med raster -displayalgoritmer. Lineære eller jævnt buede kanter vil virke ujævne og er især stødende i animationer, fordi bevægelse af billedet får kanterne til at virke uklare eller ligne små rulletrapper i bevægelse. Også detaljer i scenen, der er mindre end afstanden mellem stråler, kan gå tabt. De takkede kanter i en stregtegning kan udglattes ved at følge kant. Formålet med en sådan algoritme er at minimere antallet af linjer, der er nødvendige for at tegne billedet inden for en pixelnøjagtighed. Glatte kanter resulterer. Ovenstående stregtegninger blev tegnet på denne måde.
For at udglatte de kantede kanter i et skraveret billede med subpixelnøjagtighed, bør der støbes yderligere stråler for information om kanterne. (Se Supersampling for en generel fremgangsmåde.) Kanter dannes ved skæringspunktet mellem overflader eller ved profilen af en buet overflade. Anvendelse af "kohærens" som beskrevet ovenfor via binær søgning, hvis den synlige overflade ved pixel (X, Y) er forskellig fra den synlige overflade ved pixel (X+1, Y), kan der dannes en stråle midt imellem dem ved (X+ ½, Y) og den synlige overflade der identificeres. Afstanden mellem prøvepunkter kan yderligere underinddeles, men søgningen behøver ikke være dyb. Den primære søgedybde til glatte spidsede kanter er en funktion af intensitetsgradienten på tværs af kanten. Da (1) billedområdet, der indeholder kanter, normalt er en lille procentdel af det samlede areal, og (2) de ekstra stråler, der støbes i binære søgninger, kan begrænses i dybden - det for de synlige primitiver, der danner kanterne - omkostningerne for udjævning af takkede kanter er overkommelig.
Historien om ray casting
For historien om ray casting, se ray tracing (grafik), fordi begge stort set er det samme. Scott Roth opfandt udtrykket "ray casting", før han havde hørt om "ray tracing". Scott Roths udvikling af ray casting på GM Research Labs skete samtidig med Turner Whitted's ray tracing arbejde på Bell Labs.
Ray casting i tidlige computerspil
I tidlige førstepersonsspil blev raycasting brugt til effektivt at gengive en 3D-verden fra et 2D-spillefelt ved hjælp af en simpel endimensionel scanning over skærmens vandrette bredde. Tidlige førstepersonsskydere brugte ray casting som en teknik til at skabe en 3D-effekt fra en 2D-verden. Selvom verden fremstår 3D, kan spilleren ikke se op eller ned eller kun i begrænsede vinkler med forskydningsforvrængning, fordi dette gør det muligt at gøre 2D -spillefeltet hurtigere.
Wolfenstein 3D
Det verdensberømte videospil Wolfenstein 3D blev bygget af et firkantet net af ensartede højdevægge, der møder ensfarvede gulve og lofter. For at tegne verden blev der sporet en enkelt stråle for hver kolonne af skærmpixel, og et lodret stykke vægtekstur blev valgt og skaleret efter, hvor i verden strålen rammer en væg, og hvor langt den bevæger sig, før den gør det.
Formålet med de netbaserede niveauer var todelt-ray-wall-kollisioner kan findes hurtigere, da de potentielle hits bliver mere forudsigelige, og hukommelsesomkostningerne reduceres. Kodning af vidåbne områder tager dog ekstra plads.
ShadowCaster
Den Raven Software spil ShadowCaster bruger en forbedret Wolfenstein-baserede motor med tilsatte gulve og lofter teksturering og variable væg højder.
Comanche serie
Den Voxel Space motor udviklet af NovaLogic for Comanche spil spores en stråle gennem hver kolonne af billedpunkter og testet hver stråle mod punkter i en heightmap . Derefter transformerede det hvert element i højdekortet til en kolonne med pixels, bestemt hvilke der er synlige (det vil sige ikke er blevet tilstoppet af pixels, der er blevet tegnet foran), og trak dem med den tilsvarende farve fra teksturkortet.
Ud over raycasting
Senere beholdt DOS -spil som id Softwares DOOM mange af raycasting 2.5D -begrænsningerne for hastighed, men skiftede til alternative gengivelsesteknikker (som BSP ), hvilket gjorde dem ikke længere til raycasting -motorer.
Beregningsgeometri indstilling
I beregningsmæssig geometri er strålestøbningsproblemet også kendt som stråleoptagelsesproblemet og kan angives som følgende forespørgselsproblem: givet et sæt objekter i d -dimensionalt rum, forarbejd dem i en datastruktur, så for hver forespørgselsstråle, det første objekt, der blev ramt af strålen, kan hurtigt findes. Problemet er blevet undersøgt for forskellige indstillinger: rumdimension, objekttyper , begrænsninger på forespørgselsstråler osv. En teknik er at bruge et sparsomt voxeloktret .
