Irakli Koiava

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

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

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

spatial and object partitioning სურათზე ნაჩვენებია შემთხვევა, როდესაც მოცემული 2 სამკუთხედის(პრიმიტივის) დაყოფა ხდება ობიექტებად(მარცხენა) და სივრცულად(მარჯვენა).           ამაჩქარებელი სტრუქტურის (ხის) აგების პროცესი გულისხმობს პრიმიტივების გადანაწილებას ხის შიდა და გარე კვანძებში, მთავარია შევიმუშავოთ გადანაწილების ისეთი მეთოდი რომელიც მოქვცემს უკეთეს შედეგს. განვიხილოთ ხის აგების ორი ტიპის მეთოდი: სივრცული დაყოფა - სივრცული დაყოფის დროს შემოგვაქვს რაიმე სივრცული გამყოფი(მაგალითად სიბრტყე) და იმის მიხედვით, თუ გამყოფის რომელ მხარეს ექცევა პრიმიტივი, ვანაწილებთ შვილობილ კვანძებში. ასეთ შემთხვევაში ერთი პრიმიტივი შეიძლება რამოდენიმე კვანძში მოხვდეს. სხვა სიტყვებით რომ ვთქვათ, ერთ პრიმიტივს შესაძლოა რამოდენიმე კვანძი უთითებდეს. ობიექტების დაყოფა - ობიექტების დაყოფის დროს ხდება პრიმიტივების გადანაწილება შვილობილ კვანძებში ისე, რომ ყოველი პრიმიტივი ხვდება ერთ რომელიმე კვანძში, სხვა სიტყვებით რომ ვთქვათ: ნებისმიერ პრიმიტივს უთუთებს მხილოდ ერთი კვანძი.         ხეები, რომელთა ა