სხივების მიდევნება

Ray Tracing

        სხივების მიდევნების მეთოდი არის გამოსახულების კომპიუტერულად მიღების ერთ-ერთი გზა რომელიც გულისხმობს ციფრული გამოსახულების თითოეული პიქსელისათვის სხივის მიდევნებას, რომელიც მიმართულია დამკვირვებლიდან შესაბამისი პიქსელის მიმართულებით (ქვემოთ მოცემულ სურათზე შესაბამისი სხივები ნაჩვენებია წითლად).

სურათზე ნაჩვენებია სხივების მიდევნების ილუსტრაციული მოდელი

        ჩვენი მიზანია თითოეული ასეთი სხივისათვის დავადგინოთ ფერი, რა ფერიც უნდა გახდეს საბოლოოდ ამ სხივის შესაბამისი პიქსელი. საინტერესოა ამ ალგორითმის მუშაობის პროცესორული დროის შეფასება. რომ შევძლოთ ალგორითმის დეტალური ანალიზი და შეფასება პირველ რიგში ჩამოვაყალიბოთ თვითონ მეთოდი: 

1. გავირბინოთ გამოსახულების ყველა პიქსელზე.
2. თითოეული პიქსელისთვის მოვძებნოთ მისი შესაბამისი ფერი.

        ადვილი შესამჩნევია რომ ალგორითმის მუშაობის პროცესორული დრო პირდაპირპროპორციულად არის დამოკიდებული ციფრული გამოსახულების პიქსელების რაოდენობაზე(პირველი პუნქტი). მაგალითად HD(1280x720) გამოსახულებისათვის მას მოუწევს 921600 პიქსელზე გარბენა და თითოეუნისთვის ფერის პოვნა. იმისათვის, რომ შევაფასოთ მეორე პუნქტი საჭიროა უფრო ზუსტად ჩამოვაყალიბოთ მისი იმპლემენტაცისს დეტალები. როგორ ვაპირებთ ჩვენ პიქსელისთვის მისი ფერის მოძებნას. მოვიყვანოთ მარტივი მაგალითი. ზემოთ მოცემულ სურათზე ნაჩვენებია შემთხვევა როცა კამერა უღებს სცენას სადაც არის ერთი ყვითელი სფერო. კამერა მიმართულია სფეროს მხარეს ასე რომ სფერო ჩანს გამოსახულების ცენტრში, თუმცა სფეროს გარდა ასევე ჩანს ზედაპირიც, რომელზეც დევს ეს სფერო. ყველაზე მარტივი შეფასება იქნება ასეთი, რომ ის პიქსელები რომლიდან წამოსული სხივებიც მოხვდება სფეროს იქნება ყვითელი(სფეროს ფერი), რომელიც მოხვდება ზედაპირს ზედაპირის ფერი. გამოდის იმისათვის, რომ კონკრეტული პიქსელისთვის მოვძებნოთ მისი შესაბამისი ფერი უნდა დავადგინოთ თუ რომელ ობიექტს მოხვდა ამ პიქსელიდან წამოსული სხივი.  ამის დასადგენად ყველაზე მარტივი და ინტუიტიური გზა არის, გავირბინოთ ყველა ობიექტზე და შევამოწმოთ ხვდება თუ არა ჩვენი სხივი ამ ობიექტს. ასეთი შეფასებით ვიღებთ რომ ფერის პოვნის ამოცანაც არის O(m). თუ გავაერთიანებთ ორივე პუნქტს მივიღებთ რომ ყველა პიქსელზე გარბენას ჭირდება O(n) დრო, სადაც n პიქსელების რაოდენობაა და თითოეული პიქსელისთვის მისი ფერის მოძებნას ჭირდება O(m) დრო, სადაც m სცენაში არსებული პრიმიტივების რაოდენობაა.  საბოლოოდ ალგორითმის შეფასება გამოდის O(nm).

        როგორც ხედავთ ალგორითმი იმდენად მძიმეა რომ მისი იმპლემენტაცია რეალური ამოცანებისთვის, სადაც პრიმიტივების რაოდენობა უსასრულობამდე იზრდება ფაქტიურად შეუძლებელი იქნებოდა. თუმცა აღმოჩნდა რომ შეიძლება ამოცანის ამ სირთულეებიდან გამოყვანა. ამოცანის მეორე პუნქტი, რომელიც რეალურად გულისხმობს სხივის თანაკვეთის პოვნას გეომეტრიულ პრიმიტივებთან კომპიუტერული გრაფიკის მიმართულებით ერთ-ერთი ყველაზე მნიშვნელოვანი საკითხია, ასე რომ ეს ამოცანა განვიხილოთ ცალკე.

        სხივის თანაკვეთა გეომეტრიულ ობიექტთან

        ყველაზე მარტივი გეომეტრიული ობიეტქი, რომელიც აღწერს სიბრტყის რეგიონს და რომელსაც იყენებენ რთული ზედაპირების აღსაწერად არის სამკუთხედი. 

        არსებობს გეომეტრიის აღწერის ალტერნატიული გზები, თუმცა სამკუთხედებით აღწერა არის ყველაზე გავრცელებული. დღევანდელ თამაშებში არსებულ გეომეტრიულ ობიექტებში სამკუთხედების საერთო რაოდენობა ასობით მილიონს აღწევს და რეალურად შეუზღუდავია. ჩვენი ამოცანა კი იმაში მდგომარეობს, რომ ამ კოლოსალური რაოდენობის სამკუთხედებში მოვძებნოთ ისინი რომლებსაც მოხვდა ჩვენი სხივი(ხშირ შემთხვევაში ამოცანა დადის მათში უახლოესის მოძებნაზე). ერთ-ერთი ყველაზე გავრცელებული გზა არის სამკუთხედების ან/და სამკუთხედების ჯგუფების დაჯგუფება. 

განვიხილოთ მარტივი შემთხვევა, როდესაც მოცემულია გეომეტრიული ობიექტი დიდი რაოდენობის სამკუთხედებით და სხივი რომელიც რეალურად ცდება ამ გეომეტრიას. ამ შემთხვევაში ჩვენთვის ბევრად მომგებიანია წინასწარ შევამოწმოთ საერთოდ ხომ არ სცდება ეს სხივი ობიექტს(სამკუთხედების ჯგუფს), ვიდრე გავირბინოთ ობიექტის ყველა სამკუთხედზე და ამოვხსნით სხივის სამკუთხედთან თანაკვეთის ამოცანა. ყველაზე გავრცელებული მიდგომა სამკუთხედების ჯგუფის ზოგადი მდებარეობის შესაფასებლად არის საკოორდინატო სიბრტყეების პარალელური შემომსაზღვრელი ყუთები (Axis Aligned Bounding Box, შემოკლებით AABB). იმისათვის რომ დავადგინოთ AABB საჭიროა გავირბინოთ ყველა პრიმიტივზე და ვიპოვოთ მინიმალური და მაქსიმალური მნიშვნელობები x, y  და z-ის გასწვრივ. თუმცა ამ პროცედურის გავლა არ გვიწევს ყოველი სურათის გამოთვლისას, ან მით უმეტეს არც ყოველი სხივის მიდევნებისას. მისი დათვლა ხდება ერთჯერადად და განახლება ხდება როცა საჭიროა(გეომეტრიის ცვლილებისას/დეფორმაციისას).
        არსებობს მონაცემთა სტრუქტურები გეომეტრიის შესანახად მსგავსი მოსახერხებელი ფორმით. ერთ-ერთი ასეთი მონაცემთა სტრუქტურაა შემომსაზღვრელი ყუთების იერარქია (Bounding Volume Hierarchy შემოკლებით BVH). BVH-ის აგების სამი ძირითადი მეთოდი არსებობს:

1. ზემოდან ქვემოთ (Top Down) გავრბივართ პრიმიტივებზე და მის ჩადალაგებას ვახდენთ წინასწარ განსაზღვრული რაოდენობის ყუთებში. შემდგომ ჩავდივართ ამ ყუთებში რეკურსიულად და ვიმეორებთ იგივე პროცედურას. ეს მეთოდი არის ლოგარითმული რიგის.
2. ქვემოდან ზემოთ (Bottom Up) რაიმე ევრისტიკის საფუძველზე ვაჯგუფებთ წინასწარ განსაზღვრული რაოდენობის სამკუთხედებს ერთად და ვალაგებთ ყუთებში. შემდეგ ამ ყუთებს ვაჯგუფებთ და ასე მანამ, სანამ ერთ დიდ ყუთში არ აღმოჩნდება მთელი გეომეტრია. ეს მეთოდი უფრო რთული განსახორციელებელია და უფრო დიდი დრო ჭირდება თუმცა ხარისხით ჯობნის წინა მეთოდს.
3. შეტანით (Insertion) ხდება ხის შექმნა და პრიმიტივების შეტანა ხეში სათითაოდ.

        იმისათვის რომ დავადგინოთ BVH-ში არსებულ რომელ სამკუთხედს მოხვდა სხივი, ჩავდივართ ხეში და ვამოწმებთ მოხვდა თუ არა ზედა ყუთს სხივი. თუ მოხვდა ვხსნით ყუთს რეკურსიულად და ვამოწმებთ რომელ ყუთს მოხვდა და ასე მანამ, სანამ არ ჩავალთ ფოთლებამდე სადაც ინახება სამკუთხედები. ამ ეტაპზე ხდება სამკუთხედებთან თანაკვეთის შემოწმება. BVH გვეხმარება რომ n რაოდენობის სამკუთხედების გადამოწმების მაგივრად გადავამოწმოთ რამოდენიმე სამკუთხედი, ხოლო მათთან მისასვლელად უნდა ჩავიდეთ log(n) ლიმაღლის მქონე ხის ფოთლებამდე(ლოგარითმის რიგი დამოკიდებულია ხის განშტოების რიგზე). ამრიგად მივიღებთ რომ სხივის სამკუთხედთან თანაკვეთის ამოცანა დადის log(n)-ზე.
        აქედან გამომდინარე სხივების მიდევნების მეთოდის დროითი სირთულე გამოდის n log(m). რეალურად ფერის გამოთვლა მხოლოდ ობიექტის ფერზე დაყრდნობით არ ხდება, აქ დიდ როლს განათების მოდელი თამაშობს. შესაძლებელია ასევე დაცემული ჩრდილის ეფექტის მიღება, ამისთვის იღებენ სხივს რომელიც მიმართულია მოხვედრის წერტილიდან განათების წყაროს მიმართულებით და ხელახლა ამოწმებენ თანაკვეთას, თუ სცენაში არსებულ რომელიმე ობიექტს მოხვდა სხივი მაშინ ეს წერტილი ჩრდილშია. ამ სხივებს ეძახიან ჩრდილის სხივებს(Shadow Rays იხილეთ პირველი სურათი). მეტი სიცხადისათვის, იმისთვის, რომ გავიაზროთ თუ რამდენად მნიშვნელოვანია ამ კონკრეტული ოპერაციის ოპტიმალური გადაწყვეტა დავითვალოთ მინიმუმ რა დროში უნდა გადაჭრას ეს ამოცანა. იმისთვის რომ აპლიკაციამ იმუშაოს რეალურ დროში დავუშვათ, რომ მომხმარებელს ჭირდება 20 კადრი/წამში. ე.ი ერთი კადრისთვის გვაქვს 50 მილიწამი. იმისათვის, რომ გამოსახულება იყოს საკმარისად გარჩევადი დავუშვათ რომ რენდერი ხდება HD გარჩევადობაზე(921600 პიქსელზე). აქედან ვიღებთ, რომ თუ ერთ ნაკადში მიდის გამოთვლები ერთი პიქსელის რენდერისთვის გვაქვს  0.00005425347(2) მილიწამი, რაც ძალიან მცირე დროა და შეუძლებელია დღევანდელი არსებული გამოთვლითი საშუალებებით, ერთი პროცესორით რეალურ დროში ამის დათვლა. სწორედ ამიტომ პიქსელისთვის ან პიქსელების ჯგუფისთვის პარალელურად ახდენენ ფერების გამოთვლას. დღევანდელ გრაფიკულ პროცესორებში ბირთვების რაოდენობა რამოდენიმე ათასსაც კი აღწევს, რაც გვაძლევს საშუალებას, რომ გამოთვლები მასიურად გავაპარალელოთ და სასურველი შედეგი მივიღოთ ბევრად მალე. აქ არ უნდა დაგვავიწყდეს, რომ თუ თამაშს ვწერთ აქ მარტო რენდერი არ არის, საკმაოდ დიდი წარმადობა უნდა დავუთმოთ ფიზიკას, და აუდიო ნაწილს და ა.შ. ასე რომ დღესდღეუბით ეს მეთოდი რეალურ დროში მომუშავე აპლიკაციებში ძალაინ შეზღუდელი რაოდენობით და შესაძლებლობებით გვხვდება. შეუცვლელია ისეთ სფეროებში როგორიცაა მულტიმედია, ტელე/კინო მონტაჟი, რენდერი, ნაწილობრივ და სრულად ანიმაციური ფილმები.