Skip to main content

Posts

Showing posts with the label ამაჩქარებელი სტრუქტურები

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

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

ზედაპირის ფართობის ევრისტიკა

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

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

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

შემომსაზღვრელი ფიგურები

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

რვაობითი ხე

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

სივრცული დაყოფა და ობიექტებად დაყოფა

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