ბრტყელი სივრცის ანალოგია
ედვინ აბოტის „ბრტყელი სივრცე“ (1884): ორგანზომილებიანი სიბრტყის მკვიდრები. ისინი აღიქვამენ სიგრძესა და სიგანეს. სიღრმე: მესამე განზომილება მათ ზემოთ, უხილავი. მათ არ შეუძლიათ მისი აღქმა, გამოყენება ან მისით აშენება. მათი სამყაროს გეომეტრია შეიცავს განზომილებას, რომელსაც ისინი სტრუქტურულად გაუქმებენ.
MOAD-0007 იგივე პრინციპით მუშაობს. 3D სივრცეში ობიექტები ატარებენ პოზიციას, ბრუნვასა და შემოსაზღვრელ მოცულობას: მდიდარი გეომეტრიული სტრუქტურა. წრფივი სკანირება მათ ბრტყელ სიად მიიჩნევს. სივრცითი სტრუქტურა: არსებობს, მაგრამ გამოუყენებელია, გაუქმებულია. ყველა გადაკვეთის ტესტი სკანირებს მთელ სიას, თითქოს ობიექტებს არ ჰქონდეთ არც გეომეტრია და არც პოზიცია.
Three.js-ის მაგალითი
Three.js Raycaster.intersectObjects(): მოცემულია სხივი (პოზიცია და მიმართულება 3D სივრცეში), იპოვე ყველა ობიექტი, რომელსაც სხივი კვეთს. იმპლემენტაცია: გაიარე ყველა N სცენის ობიექტი, შეამოწმე თითოეული სხივთან. O(N) თითო გამოძახებაზე.
Hover-ის მოვლენის დამმუშავებელი იძახებს intersectObjects()-ს თითო კადრზე 60 კადრს წამში. N=100 ობიექტის შემთხვევაში: 6,000 კვეთის ტესტი წამში. N=10,000 ობიექტის შემთხვევაში: 600,000 ტესტი წამში. ღირებულება: პროპორციულია N-ის, არა იმ ობიექტების რაოდენობის, რომლებსაც სხივი რეალურად კვეთს.
N=100-ზე: უხილავი. კადრის ბიუჯეტი (16.7ms 60fps-ზე) შთანთქავს ღირებულებას საჩივრის გარეშე.
N=10,000-ზე: დომინანტური. 600,000 კვეთის ტესტი წამში აჯერებს მთავარ ძაფს. კადრის სიხშირე ეცემა. სცენა, რომელიც მუშაობდა N=100-ზე, ჩუმად იშლება, როცა N გადაკვეთს ზღვარს.
სტრუქტურა, რომელსაც წრფივი სკანირება უგულებელყოფს
ობიექტები იკავებენ პოზიციებს სივრცეში. ობიექტი პოზიციაზე (1000, 0, 0) ვერ კვეთს სხივს, რომელიც მიმართულია მიმართულებით (-1, 0, 0) პოზიციიდან (0, 0, 0): ობიექტი საპირისპირო მიმართულებაშია. წრფივი სკანირება მაინც ამოწმებს მას.
ობიექტებს აქვთ შემზღუდავი მოცულობები: სფერო ან ყუთი, რომელიც მოიცავს მთელ ობიექტს. სხივი, რომელიც არ კვეთს ობიექტის შემზღუდავ მოცულობას, ვერ კვეთს თავად ობიექტს. წრფივი სკანირება მაინც ითვლის სრულ კვეთის ტესტს.
გეომეტრია კოდირებს, რომელი ობიექტები უნდა გამოტოვო. წრფივი სკანირება უგულებელყოფს გეომეტრიას. ეს არის გამოტოვება.
რას ნიშნავს „სტრუქტურის გადაგდება“
Flatland-ის ანალოგია: აბოტის მაცხოვრებლებს არ შეეძლოთ სიღრმის აღქმა. Flatland-ის დეფექტი გადაყრის მონაცემებში არსებულ გეომეტრიულ სტრუქტურას, რომელიც ალგორითმში არასოდეს შედის.
რატომ ვერ ასწორებს ჰეშ-სეტი MOAD-0007-ს
MOAD-0001 გამოსწორება: თანმიმდევრული წევრობის შემოწმების ჩანაცვლება ჰეშ-სეტით. list.contains(x): O(N). set.has(x): O(1). წევრობის კითხვა: „არის თუ არა x ამ კოლექციაში?“ სივრცითი გეომეტრია არ მონაწილეობს.
MOAD-0007 გამოსწორება: წრფივი სივრცითი სკანირების ჩანაცვლება სივრცითი ინდექსით (BVH, ოქტოხე, k-d ხე, R-ხე). სივრცითი კითხვა: „რომელი ობიექტები ამ კოლექციაში იკვეთება ამ სხივთან/სფეროსთან/ფრუსტუმთან?“ საჭიროა სივრცითი სიახლოვე.
ჰეშ-სეტი პასუხობს წევრობის კითხვას: „არის თუ არა ეს ზუსტი ობიექტი?“ O(1). მას არ შეუძლია პასუხი სიახლოვის კითხვაზე: „რომელი ობიექტებია ამ სხივთან ახლოს?“ ჰეშ-სეტს არ აქვს მანძილის ან სივრცითი მოცულობის ცნება. ჰეშირება ისევე საფუძვლიანად უარყოფს გეომეტრიას, როგორც წრფივი სკანირება.
BVH პასუხობს სიახლოვის კითხვას: „რომელი ობიექტები მოხვდება ამ სივრცით მოთხოვნაში?“ O(log N + k). იგი აწყობს ობიექტებს პოზიციის მიხედვით, ამიტომ სიახლოვის მოთხოვნები გამოტოვებს გეომეტრიულად დაშორებულ ობიექტებს.
| კითხვა | სწორი სტრუქტურა | არასწორი სტრუქტურა |
|---|---|---|
| არის თუ არა ობიექტი X ამ სეტში? | HashSet (O(1)) | წრფივი სია (O(N)) |
| რომელი ობიექტები იკვეთება ამ სხივთან? | BVH/ოქტოხე/k-d ხე (O(log N)) | წრფივი სკანირება ან HashSet (O(N) ან O(N)) |
MOAD-0001 & MOAD-0007: ორივე O(N) ოპერაცია ჩანაცვლდა უფრო სწრაფი რამით. სხვადასხვა სტრუქტურებია საჭირო, რადგან კითხვები განსხვავებულია.
როდის ავაშენოთ, როდის გამოვტოვოთ
BVH-ის აშენება ღირს O(N log N). მოთხოვნა ღირს O(log N + k). წყვეტის წერტილი: როდესაც მოთხოვნების რაოდენობა აღემატება აშენების რაოდენობას იმდენად, რომ მოთხოვნების დაზოგვა აღემატება აშენების ღირებულებას.
N=100-ზე: წრფივი სკანირება იღებს მიკროწამებს. BVH-ის აშენება ამატებს დამატებით ხარჯებს. გამოტოვეთ BVH.
N=10,000-ზე 60Hz-ზე: წრფივი სკანირება დომინირებს კადრის ბიუჯეტში. BVH მოთხოვნები ღირს წრფივი სკანირების 1/1,000-ე ნაწილი. ავაშენოთ BVH ერთხელ; მოვითხოვოთ 60-ჯერ წამში. წყვეტის წერტილი მიიღწევა პირველ კადრამდე.
წესი: ავაშენოთ როდესაც N * Q > N log N, სადაც Q = მოთხოვნები თითო აღდგენის ციკლზე. ინტერაქტიული 3D სცენებისთვის: Q = 60 წამში, N ზღვარი = რამდენიმე ასეული ობიექტი.
დაადგინეთ და გამოასწორეთ 3D სცენა
3D ვიზუალიზაციის აპლიკაცია აჩვენებს 5,000 გეომეტრიულ ობიექტს. Hover-ის დამმუშავებელი იწვევა 60-ჯერ წამში. ყოველ hover მოვლენაზე, დამმუშავებელი იძახებს scene.intersectObjects(ray, objects), რომელიც გადის ყველა 5,000 ობიექტზე და ამოწმებს თითოეულს სხივთან. კადრის სიხშირე დაეცა 60fps-დან 8fps-მდე.
თანაგუნდელი გვთავაზობს: 'მოათავსე ყველა ობიექტი Set-ში O(1) მოძებნისთვის.'