შემომსაზღვრელი ყუთების იერარქია

BVH

მარცხენა მხარეს ნაჩვენებია პრიმიტივები(სამკუთხედები) და მასზე აგებული BVH ვიზუალურად, მარჯვენა მხარეს ნაჩვენებია იგივე BVH ხის სახით

        როგორც სახელწოდებიდან ჩანს, შემომსაზღვრელი ყუთების იერარქია წარმოადგენს ისეთ ხეს, რომელშიც შემომსაზღვრელი ყუთები არის ჩალაგებული იერარქიულად, ხოლო ფოთლებში მოთავსებულია ერთი ან რამდენიმე პრიმიტივი. შემოკლებით ხშირად BVH-ს უწოდებენ, რაც ინგლისური სახელწოდების აბრევიატურას წარმოადგენს, სიმარტივისათვიშ შემდგომში ამ სახელს გამოვიყენებთ.
BVH-ის აგების პროცესში ხდება პრიმიტივების გადანაწილება ყუთებში, რის გამოც ერთი პრიმიტივი ერთ რომელიმე ყუთში ხვდება.
        სანამ ხის აგებაზე გადავალთ, განვიხილოთ ერთი მნიშვნელოვანი საკითხი. ვთქვათ გვაქვს რაიმე ევრისტიკული ფუნქცია f(i,j), რომელიც კვანძების ნებისმიერი (i,j) წყვილისთვის, სადაც i≠j, ახდევს მათი დაჯგუფების ხარისხის შეფასებას. ასეთ შემთხვევაში ჩვენ შეგვიძლია განვიხილოთ დაჯგუფების სხვადასხვა ვარიანტი, მოვახდინოთ მათი ევრისტიკული შეფასება და ამოვირჩიოთ ევრისტიკულად ყველაზე მომგებიანი ვარიანტი(ის, რომელიც ყველაზე მაღალი ხარისხის ხეს მოქვცემს).
        არსებობს მეთოდი, რომელიც ხეს აგებს ქვემოდან ზემოთ: ჯერ ქმნის ფოთლებს არსებული პრიმიტივებით, შემდეგ აჯგუფებს მათ და ქმნის მათ მშობელ შიდა კვანძებს, და ასე სანამ არ მიიღებს ხის ძირს. როგორც ზემოთ ვთქვით, იმისათვის რომ მოვახდინოთ კვანძების დაჯგუფება, დაჯგუფების სხვადასხვა ვარიანტებიდან უნდა შევარჩიოთ ევრისტიკულად ყველაზე მომგებიანი. აგების ეს მეთოდი არის O(n^3) სირთულის, სადაც n პრიმიტივების რაოდენობაა. კუბური სირთულიდან გამოყვანა შესაძლებელია თუ გამოვიყენებთ გროვებს, თუმცა მეთოდი მაინც იმდენად რთულია, რომ პრაქტიკაში მისი გამოყენება თითქმის არ ხდება მისი გამოთვლითი სირთულის გამო.
        ახლა განვიხილოთ მეთოდები, რომლებიც ხეს აგებენ ზემოდან ქვემოთ: ჯერ აგებენ ხის ძირს, შემდეგ შვილობილ, შიდა კვანძებს და ჩადიან ფოთლებამდე. ხის აგების რამოდენიმე, ასეთი მეთოდი არსებობს, მოვიყვანოთ მაგალითი: საწყის ეტაპზე ყველა პრიმიტივი მოვათავსოთ ერთ ყუთში, შემდეგ განვსაზღვროთ ყუთის ყველაზე გრძელი მხარე და შესაბამისი ღერძის გასწვრივ დავალაგოთ პრიმიტივები მათი ცენტრის კოორდინატების მიხედვით. ამის შემდგომ დალაგებული პრიმიტივების პირველი ნახევარი მოვათავსოთ ერთ შვილობილ კვანძში, ხოლო მეორე ნახევარი მეორეში. ეს პროცესი გავიმეოროთ რეკურსიულად, სანამ ფოთლებში სასურველი რაოდენობის პრიმიტივები არ დაგვრჩება. ასეთი სახით აგებული ხე სრულად ბალანსირებულია, რადგან ყოველი კვანძისთვის შვილობილ კვანძებში პრიმიტივების რაოდენობის ნახევარ-ნახევარს ვათავსებთ, თუმცა თავად აგების პროცესი საკმაოდ რთულია, რადგან გვიწევს პრიმიტივების დალაგებები შუაზე გასაყოფად.
        განვიხილოთ კიდევ ერთი მეთოდი: წინასგან განსხვავებით ეს მეთოდი თავიდან იცილებს პრიმიტივების დალაგებას. ამის მაგივრად მას შემოაქვს გამყოფი სიბრტყე(ყველაზე მარტივ შემხვევაში შეიძლება ავიღოთ ის სიბრტყე, რომელიც შუაზე ყოფს ყუთს მისი გრძელი გვერდის მიმართ) და ის პრიმიტივები, რომელთა ცენტრის კოორდინატებიც მოექცევიან გამყოფის ერთ მხარეს მოვათავსოთ ერთ შვილში, ხოლო დანარჩენები მეორეში. პრიმიტივის ცენტრის კოორდინატი სიბრტყის ან ერთ მხარეს ექცევა, ან მეორე, განსხვავებით თავად პრიმიტივისაგან, რომელიც შეიძლება თანაიკვეთოს კიდეც. ამ მეთოდით აგებული ხე გამოვა არაბალანსირებული, რადგან გამყოფის სხვადასხვა მხარეს სხვადასხვა რაოდენობის პრიმიტივები შეიძლება მოექცნენ. რაც შეეხება თავად აგების პროცესის სირთულეს წინა მეთოდთან შედარებით ბევრად სწრაფად ხდება, რადგან ყოველ კვანძში პრიმიტივებზე ერთი გარბენით ვახდენთ მათ გადასანაწილებლად შვილობილ კვანძებში.