BVH-ის მშენებლები

BVH Builders

თმის გორგალი მოცემული სამკუთხა მეშის სახით. (2.8 მილიონი სამკუთხედი)

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

Median BVH

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

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

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

Sweep SAH

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

Binned SAH

        როგორც ზემოთ მოყვანილ მეთოდებში ვახსენეთ ზემოდან ქვემოთ ხის აგებისას ვახდენთ მიმდინარე კვანძის გაყოფას 2 ნაწილად, ხშირად გამოიყენება ობიექტებად დაყოფა გამყოფი სიბრტყის მიმართ. MedianBVH ახდენდა AABB-ს შუა სიბრტის მიმათ ელემენტების გადანაწილებას შვილებში, თუმცა ეს რა თქმა უნდა შესაძლოა შორს იყოს ოპტიმალურისაგან. იმის გამო, რომ სცენაში არსებული ელემენტები არათანაბრად შეიძლება იყვნენ გადანაწილებულნი სივრცეში, პრიმიტივების შუა სიბრტით გაყოფა ყოველთვის კარგ შედეგს ვერ მოგვცემს. რეალურად ოპტიმალურად გამყოფი სიბრტყე შეიძლება გადიოდეს ნებისმიერ ადგილზე და ნებისმიერი ღერძის მიმართ. შესაბამისად ადვილი მისახვედრია, რომ მაღალი ხარისხის ხის ასაგებად კარგი იქნება თუ განვიხილავთ სხვადასხვა გამყოფ სიბრტყეებს, შევაფასებთ მათ SAH-ის საშუალებით და მათ შორის ავარჩევთ ყველაზე კარგს.
         მეთოდი თავდაპირველად გამოიყენებოდა k განზომილებიან ხეებში(k-d tree) და შემდგომ მოხდა მისი გამოყენება უკვე BVH-ში. ის ახდენს ერთმანეთისგან თანაბრად დაშორებული ფიქსირებული რაოდენობის გამყოფი სიბრტეების განხილვას, აფასებთ თითოეულ მათგანს SAH-ის საშუალებით და ყოფს კვანძს საუკეთესო გამყოფით. n გამყოფი სიბრტყის შემთხვევაში გვექნება n+1 უჯრა, როგორც ექსპერიმენტები უჩვენებს დაბალი რეოდენობის უჯრების შემთხვევაშიც კი ხარისხის გაუმჯობესება საგრძნობია. როგორც წესი 16 უჯრა უკვე საკმარისად კარგ რეზულტატს იძლევა გამოთველისათვის საჭირო დროსთან მიმართებაში. ხშირად მეთოდს, რომელიც იხილავს და აფასებს SAH-ის საშუალებით სხვადასხვა გამყოფებს ხის აგების სხვადასხვა დონეებზე ეძახიან FullSAH-საც.

BVH Refit

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

SBVH

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

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

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

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

SplitNode() {
    split1 = findBestObjectSplit()
    split2 = findBestSpatialSplit()
    if( split1.SAHcost <= split2.SAHcost )
        PerformSplit( split1 )
    else
        PerformSplit( split2 )
}

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

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

LBVH

        LBVH არის ხის წრფივ დროში აგების მეთოდი (Linear BVH), რომელიც არის ყველაზე სწრაფი მეთოდი დღესდღეობით არსებულ მეთოდებს შორის.

სურათი უჩვენებს თუ როგორ ხდება პრიმიტივების დალაგება და დაჯგუფება მორტონის წირის მიმართ. (წყარო)

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

TrBVH

        BVH-ის თავიდან აგების ყველაზე სწრაფი მეთოდი ამ დროისთვის არის LBVH, რომელიც ფაქტიურად წრფივ დროში ახდენს ხის აგებას. ამ მეთოდით მიღებული ხის ხარისხი რა თქმა უნდა ბევრად უფრო დაბალია ვიდრე SBVH ან თუნდაც Binned SAH, ლაპარაკია ანიმაციურ სცენებზე. მაშინ როდესაც ჩვენ გვსურს ანიმაციური სცენების რენდერი რეალურ დროში საჭიროა როგორც ხის აგების დროის ასევე ხის ხარისხის ოპტიმიზაცია. ამ დროისათვის უახლესი მეთოდი რომელსაც შეიმუშავეს NVidia-ს კვლევითი ჯგუფში, ისევე როგორც LBVH, SBVH და ბევრი სხვა გამოირჩევა სწორედ ორივე ზემოთ ხსებებული მახასიათებლებით. ის გამოირჩევა მუშაობის განსხვავებული მიდგომით სხვა მეთოდებთან შედარებით და კომპანია მოიაზრებს, როგორც მომავალი კვლევების აქტიურ მიმართულებას.
        ხის აგების ამ პროცესს უწოდებენ შთამომავალი კვანძების ქვესიმარავლის რესტრუქტურიზაციას. ეს პროცესი გამოიყურება შემდეგნაირად:

1. ავაგოთ დაბალი ხარისხის BVH.
2. დავაოპტიმიზიროთ მისი კვანძების ტოპოლოგია. გავაკეთოთ ეს პარალელურად.

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

        იმისათვის, რომ გაუმკლავდეს დიდი, არათანაბარი და დიაგონალურად განლაგებული პრიმიტივებით გამოწვეულ პრობლემებს რომელიც განვიხილეთ SBVH-ში მეთოდი ახდენს სამკუთხედების დატოფას(Triangle Splitting) იყენებს ადრეულ სტადიაზე სამკუთხედების დანაწევრების მეთოდს(Early Split Clipping. Ernst and Greiner 2007), რომელიც აანალიზებს სამკუთხედების საწყის სიმრავლეს და მათ ნაწილს აღწერს რამოდენიმე AABB-ს საშუალებით, თავად სამკუთხედის გაორება არ ხდება.

გრაფიკი უჩვენებს BVH-ის აგების სხვადასხვა მეთოდების ეფექტურობას კადრისათვის საჭირო სხივების რაოდენობასთან მიმართებაში. წყარო

***

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