Staru mešana ir staru—virsmas krustojuma testu izmantošana, lai atrisinātu dažādas problēmas datorgrafikā un skaitļošanas ģeometrijā. Šis termins pirmo reizi tika izmantots datorgrafikā 1982. gada dokumentā, ko iesniedza Skots Ross, lai aprakstītu metodi konstruktīvo cieto ģeometrijas modeļu atveidošanai.[1]

Vienkārša ilustrācija staru mešanā

Staru mešana var attiekties uz dažādām problēmām un paņēmieniem:

  • vispārīga problēma, ar kuru nosaka pirmo objektu, kas krustojas ar staru,[2]
  • slēptās virsmas noņemšanas metode, kas balstīta uz pirmā stara krustpunkta atrašanu no acs caur katru attēla pikseli,
  • nerekursīvo staru izsekošanas algoritmu, kas tikai izstaro primāros starus, vai
  • tiešā tilpuma renderēšanas metode, ko sauc arī par sējuma staru liešanu, kurā starojums tiek “iebīdīts” objektā, un 3D skalārais izpētes laukums tiek ņemts gar attēlu objektā. Šajā metodē netiek nārstoti sekundārie stari.
    [3]

Lai gan "staru mešana" un "ray izsekošana" bieži tika izmantotas agrīnā datorgrafikas literatūrā[4] , jaunākā lietošana mēģina atšķirt abus.[5] Atšķirība ir tāda, ka staru liešana ir renderēšanas algoritms, kas nekad netiek periodiski izsekots sekundārajiem stariem, savukārt citi staru izsekošanas algoritmi var to darīt.

Staru mešana ir lielākā daļa no daudziem datorgrafikas renderēšanas algoritmiem, kas izmanto staru izsekošanas ģeometrisko algoritmu. Staru izsekošanas algoritmi darbojas attēlā, lai renderētu trīsdimensiju ainas divdimensiju attēliem. Ģeometriskie stari tiek izsekoti no novērotāja acīm, lai ņemtu gaismu (gaismu), kas ceļo uz novērotāju no staru virziena. Staru liešanas ātrums un vienkāršība rodas, aprēķinot gaismas krāsu, nereti izsekojot papildu starus, kas parāda starojuma incidentu uz punkta, kas skāris staru. Tas novērš iespēju precīzi atveidot atspulgus, refrakcijas vai ēnu dabisko atblāzmu; tomēr visus šos elementus var notēlot līdz pakāpei, radoši izmantojot faktūras kartes vai citas metodes. Lielais aprēķina ātrums lika stariem raidīt parocīgu renderēšanas metodi agrīnās reālā laika 3D videospēļu laikā.

Dabā, gaismas avots izstaro gaismas stars, kas ceļo, galu galā, arī uz virsmas, kas aptur tā attīstību. Var domāju, ka šīs "ray", kā straume fotoni ceļo pa to pašu ceļu. Šajā brīdī, jebkādu kombināciju no trīs lietām, kas varētu notikt ar šo gaismas stars: absorbcija, pārdomu un refrakcijas. Virsmas var atspoguļot visu vai daļu no gaismas stars, vienā vai vairākos virzienos. Tas varētu arī absorbē daļu gaismas stars, kas rada zaudējumus intensitāte atspoguļoti un/vai atstaro gaismas. Ja virsma ir caurspīdīga vai gaismu caurlaidīga , tad tā atspoguļo daļu no gaismas staru uz sevi citā virzienā, kamēr absorbējot dažas (vai visas) no spektra (un, iespējams, maina krāsu). Starp absorbciju, atspulgu un refrakciju ir jāuzskaita visi ienākošie gaismas stari, un ne vairāk. Piemēram, virsma nevar atspoguļot 66% no ienākošā gaismas stara un samazināt 50%, jo šie divi varētu būt 116%. No šejienes atstarotie un/vai refraktie stari var izraisīt citas virsmas, ja to absorbējošās, refrakcijas un atstarojošās īpašības atkal tiek aprēķinātas, pamatojoties uz ienākošajiem stariem. Daži no šiem stariem ceļo tā, lai tie skartu mūsu aci, izraisot, ka mēs redzam notikuma vietu un veicinām galīgo atveidoto tēlu. Mēģinājums simulēt šo reālo pasaules gaismas staru izsekošanas procesu, izmantojot datoru, var tikt uzskatīts par ārkārtīgi izšķērdīgu, jo tikai sīks staru daļa ainā patiesībā nonāktu acī.

Atveidošanai izmantoto pirmo staru mešanas algoritmu 1968. gadā.[6] prezentēja Artūrs Appelis. Staru liešanas ideja ir izsekot starus no acs, vienu pikseli un atrast tuvāko objektu, kas bloķē šī stara ceļu — iedomāties attēlu kā ekrāna durvis, un katrs kvadrāts ekrānā ir pikselis. Tad tas ir objekts, ko acs redz caur šo pikseli. Izmantojot materiāla rekvizītus un gaismas efektu kadru sērijā, šis algoritms var noteikt šī objekta ēnojumu. Vienkāršošanas pieņēmums ir tāds, ka, ja virsma saskaras ar gaismu, gaisma sasniegs šo virsmu un netiks bloķēta vai ēnā. Virsmas ēnojums tiek aprēķināts, izmantojot tradicionālos 3D datorgrafikas ēnojuma modeļus. Viena svarīga priekšrocība, ko piedāvā vecāki skenēšanas algoritmi, bija spēja viegli tikt galā ar neplanārajām virsmām un cietajām vielām, piemēram, konusiem un sfērām. Ja matemātisko virsmu var krustot ar staru, to var renderēt, izmantojot staru liešanu. Sarežģītus objektus var izveidot, izmantojot cietās modelēšanas metodes un viegli atveidojot.

Appel staru liešanas renderēšanas algoritma agrīna izmantošana bija Matemātikas lietojumu Group, Inc., (MAGI) Elmsford, New York.[7]

Staru mešana datorspēles

labot šo sadaļu

Wolfenstein 3D

labot šo sadaļu

Pasaulē Wolfenstein 3D itiek būvēta no viendabīga augstuma sienu kvadrātveida režģa, kas atbilst cietas krāsas grīdām un griestiem. Lai uzzīmētu pasauli, katrai ekrāna pikseļu kolonnai tiek izsekots viens stars, un vertikālais sienas tekstūras slānis tiek izvēlēts un mērogots atbilstoši tam, kur pasaulē stars atsitas pret sienu un cik tālu tā ceļo pirms tā.[8]

Tīkla līmeņu mērķis ir divkāršs — staru uz sienu sadursmēm var atrast ātrāk, jo potenciālie trāpījumi kļūst prognozējamāki un tiek samazināta atmiņa. Tomēr plaši atvērto zonu kodēšana aizņem papildu vietu.

Comanche sērija

labot šo sadaļu

Voxel Kosmosa dzinējs, ko izstrādājis NovaLogic Comfan spēlēm, izseko staru caur katru ekrāna pikseļu kolonnu un testē katru staru pret punktiem heightmap. Pēc tam katrs heightmap elements pārvēršas par pikseļu kolonnu, nosaka, kas ir redzams (tas ir, nav nosprostots ar priekšpusē uzzīmētiem pikseļiem), un zīmē tos ar atbilstošo krāsu no faktūras kartes.[9]

Skaitļošanas ģeometrijas iestatīšana

labot šo sadaļu

Skaitļošanas ģeometrijā staru liešanas problēma ir zināma arī kā staru šaušanas problēma, un tā var tikt norādīta kā šāda vaicājuma problēma. Ņemot vērā objektu kopu, kas atrodas telpiskā vietā, vispirms tos apstrādā datu struktūra, lai katram vaicājuma staram sākotnējais objekts, ko skāris stars, tiktu ātri atrasts. Problēma ir pētīta dažādiem iestatījumiem: telpas dimensija, objektu veidi, vaicājuma staru ierobežojumi utt.[10] Viens paņēmiens ir izmantot samazināts saudzējošu vokseļu octree.

  1. Roth, Scott D. (February 1982), "Ray Casting for Modeling Solids", Computer Graphics and Image Processing 18 (2): 109–144, doi:10.1016/0146-664X(82)90169-1
  2. Woop, Sven; Schmittler, Jörg; Slusallek, Philipp (2005), "RPU: A Programmable Ray Processing Unit for Realtime Ray Tracing", Siggraph 2005 24 (3): 434, doi:10.1145/1073204.1073211
  3. Daniel Weiskopf. GPU-Based Interactive Visualization Techniques. Springer Science & Business Media, 2006. 21. lpp. ISBN 978-3-540-33263-3.
  4. Foley, James D.; van Dam, Andries; Feiner, Steven K.; Hughes, John F. (1995), Computer Graphics: Principles and Practice, Addison-Wesley, pp. 701, ISBN 0-201-84840-6
  5. Boulos, Solomon (2005), Notes on efficient ray tracing, "ACM SIGGRAPH 2005 Courses on – SIGGRAPH '05", SIGGRAPH 2005 Courses: 10, doi:10.1145/1198555.1198749
  6. "Ray-tracing and other Rendering Approaches" Arhivēts 2018. gada 17. novembrī, Wayback Machine vietnē. (PDF), lecture notes, MSc Computer Animation and Visual Effects, Jon Macey, University of Bournemouth
  7. Goldstein, R. A., and R. Nagel. 3-D visual simulation. Simulation 16(1), pp. 25—31, 1971.
  8. Wolfenstein-style ray casting tutorial Arhivēts 2015. gada 19. maijā, Wayback Machine vietnē. by F. Permadi
  9. Andre LaMothe. Black Art of 3D Game Programming. 1995, pp. 14, 398, 935-936, 941-943. ISBN 1-57169-004-2.
  10. "Ray shooting, depth orders and hidden surface removal", by Mark de Berg, Springer-Verlag, 1993, ISBN 3-540-57020-9, 201 pp.