ამაჩქარებელი სტრუქტურები

acceleration structures

სურათზე ნაჩვენებია სფეროს მეოთხედი ნაწილი რომელზეც აგებულია რვაობითი ხე(OcTree).

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

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

        არსებული ამაჩქარებელი სტრუქტურებიდან გამოვყოთ ყველაზე გავრცელებული სტრუქტურები. ერთ-ერთი ყველაზე ძლიერი კანდიდატები არიან:

1. k განზომილებიანი ხე (k-d Tree) - ახდენს გეომეტრიის შემომსაზღვრელ ყუთში არსებული სივრცის დანაწევრებას რეკურსიულად და ალაგებს გეომეტრიას ხეში. ხის ყოველ სიმაღლეზე სივრცის დანაწევრება ხდება სხვადასხვა ღერძის მიმართ. 
2. რვაობითი ხე (ocTree) - ახდენს გეომეტრიის შემომსაზღვრელ ყუთში არსებული სივრცის დანაწევრებას 8 თანაბარ ნაწილად შუაზე გაყოფის მეთოდით და ახდენს გეომეტრიის გადანაწილებას ხის შვილობის კვანძებში. შემდეგ ჩადის იმ შვილებში რომლებშიც მოხვდა გეომეტრია და იმეორებს პროცესს მანამ, სანამ ხის ფოთლებში არ დარჩება წინასწარ განსაზღვრული მცირე რაოდენობა პრიმიტივებისა, ან მივაღწევთ წინასწარ განსაზღვრულ მაქსიმალურ სიღრმეს.
3. შემომსაზღვრელი ყუთების იერარქია (BVH) - მოყვანილი ორი ამაჩქარებელი სტრუქტურისგან განსხვავებით შემომსაზღვრელი ყუთების იერარქია განეკუთვნება გეომეტრიის დანაწევრების ჯგუქს. როგორც სახელწოდებიდან ჩანს ის არის შემომსაზღვრელი ყუთების იერარქია და რადგან მისი აგება ხდება გეომეტრიის დანაწევრებით ერთი კონკრეტული გეომეტრიული პრიმიტივი მხოლოდ ერთ ფოთოლში ხვდება. თუმცა მასაც, როგორც ყველა გეომეტრიის დანაწევრების მეთოდს აქვს ყუთების გადაფარვის პრობლემა. არსებობს როგორც ორობითი ასევე მრავლობითი შემომსაზღვრელი ყუთების იერარქიები(MBVH).

        

სურათზე ნაჩვენებია შემომსაზღვრელი ყუთების იერარქია(BVH) როგორც გეომეტრიული სახით ასევე ორობითი ხის სახით.