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

spatial and object partitioning

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

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

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

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