Irakli Koiava

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

Metropolis Algorithm სურათი უჩვენებს მეტროპოლისის ალგორითმის მიერ ლოკალური კვლევის პროცესში გავლილი დზის ტრაექტორიას         მეტროპოლისის მეთოდი გვეხმარება მოვახდინოთ მნიშვნელოვნობით შერჩევა უცნობ განაწილებაში და მივიღოთ სასურველი განაწილების პროპორციული განაწილება ისე, რომ ამავდროულად დავრჩეთ მიუკერძოებელი. მეთოდის სახელი უკავშირდება ბერძნული წარმოშობის ამერიკელი მეცნიერის ნიკოლას მეტროპოლისის  გვარს, რომელიც 50-იან წლებში მეთაურობდა მკვლევარების ჯგუფს, რომლებმაც ამ პერიოდში შეიმუშავეს მონტე კარლოს ინტეგრირების გამოთვლითი მეთოდი. მეტროპოლისი მეორე მსოფლიო ომის შემდგომ ასევე ხელმძღვანელობდა ჯგუფს რომელიც ახდენდა MANIAC I -ისთეორიულ დამუშავებას.         მეტროპოლისის მეთოდი წარმოადგენს შერჩევის მეთოდს რომელიც დაფუძნებულია მარკოვის ჯაჭვებზე. მარკოვის ჯაჭვი არის შერჩევების მიმდევრობა რომელშიც თითოეული შერჩევა დამოკიდებულია მის წინა შერჩევაზე(და არა მთელ მიმდევრობაზე). მეტროპოლისის მეთოდის დახმარებით ჩვენ ვქმნით შერჩევების ასეთ კორელაციუ...

Bezier Curve         ბეზიეს წირები ფართოდ გამოიყენება კომპიუტერული მეცნიერების სხვადასხვა მიმართულებებში  CAD  სისტემებში, კომპიუტერულ გრაფიკაში და ა.შ. ისისნი პოპულარობით სარგებლობენ მისი სიმარტივის, ინტუიტიურობის და მოსახერხებულობის გამო.         მათემატიკურად ბეზიეს წირი არის ფუნქცია რომელსაც გადაეცემა ერთი პარამეტრი t(0-დან 1-მდე) და ის გვიბრუნებს წერტილს წირზე. ფუნქციის მნიშვნელობა დამოკიდებულია შემავალ t პარამეტრზე და n ცალ წერტილზე, რომლიდანაც პირველ და ბოლო წერტილს ვუწოდებთ კვანძებს(knots), ხოლო დანარჩენებს საკონტროლო წერტილებს(Control points). როდესაც t=0 ფუნქცია გვიბრუნებს პირველ კვანძს, როდესაც t=1 ფუნქცია გვიბრუნებს მეორე კვანძს, დანარჩენ მნიშვნელობებზე ფუნქცია გვიბრუნებს წირის სხვა წერტილებს. გამოდის რომ წირი იწყება პირველი კვანძში დამოკიდებულია საკონტროლო წერტილებზე,თუმცა არ გადის მათზე და სრულდება მეორე კვანძში. მათემატიკურად ნებისმიერ ბეზიეს წირს შეესაბამება პოლინომი რომლის ხარისხიც არის მოცემული წერტილების რაოდენობ...

Importance Sampling         სტატისტიკაში მნიშვნელოვნობით შერჩევა არის კონკრეტული განაწილების მახასიათებლების შეფასების მეთოდი, მაშინ როდესაც გვაქვს ელემენტები მხოლოდ სხვადასხვა განაწილებებიდან და არა იქიდან რომელიც გვაინტერესებს. კომპიუტერულ გრაფიკაში, როდესაც ჩვენი ინტერესია "რენდერის" განტოლებაში ინტეგრალის ამოხსნა, რაც თავის მხრივ გულისხმობს ყველა იმ განათების დათვლას რომელიც ხვდება ზედაპირის კონკრეტულ წერტილში გარემოდან(ნახევარსფეროდან) ვახდენთ მონტე კარლოს ინტეგრირებას ნახევარსფეროში( BRDF -ის პროპორციულად) და რაც უფრო ვზრდით შერჩეული ელემენტების რაოდენობას მით უფრო ვუახოვდებით შედეგს. თუმცა ჩვენს შემთხვევაში როდესაც რეალურად ჯამს ვითვლით და როდესაც სხვადასხვა მიმართულებიდან სხვადასხვა ინტენსიობით მოდის სინათლე, ჯამის დათვლის დროს განაწილების ის ელემნტები რომლებიც პოულობენ დიდი ინტენსიობის მქონე განათებას მნიშვნელოვნად ცვლიან ჯამს, ხოლო დაბალი ინტენსიობის ნაკლებადმნიშვნელოვნად. შერჩევა მნიშვნელოვნობით გულისხმობს რომ ნაცვლად თანაბარი შერჩევისა მოვახდინოთ შ...

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

Heap Sort         დალაგება გროვებით როგორც სათაურიდანაც კარგად ჩანს დაფუძნებულია გროვებზე . გროვებით სორტირების პრინციპი შემდეგია: პირველ რიგში ჩვენ ვაგებთ გროვას, რასაც ჭირდება O(n) დრო. შემდეგ ვაგდებთ მაქსიმუმს(გროვის ძირს) გროვიდან, გადაგვაქვს დალაგებული მასივის თავში(ამას ჭირდება O(log()) დრო) და ამ პროცესს ვიმეორებთ მანამ, სანამ გრობვა არ დაცარიელდება. პრაქტიკულად გროვის დალაგება ხდება იგივე მასივის ბოლოში რომელშიც მოწესრიგებულია თავად გროვა. დროის ეს შეფასება არის ბევრად უფრო სტაბილური ვიდრე ჩქარი დალაგებისას სადაც უარეს შემთხვევაში დრო O(n^2)-მდეც კი ადის, რაც გროვებში არასდროს ხდება. თუმცა შემთხვევითი რიცხვებისათვის ის უფრო ნელია ჩქარ დალაგებასთან შედარებით. ქვემოთ მოცემულ სურათზე ნაჩვენებია გროვებით დალაგების ალგორითმის მუშაობის პროცესი ანიმაციურად.         მოვიყვანოთ ალგორითმის განხორციელების კონკრეტული მაგალითი. პროგრამული კოდი დაწერილია C -ზე: void  Heapify (  int  k ,  int  a [],  i...

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