ডেটা স্ট্রাকচরে BSP ট্রি

কম্পিউটার সাইয়েন্সে, একটি মেথড যেনে বাইনারি স্পেস পার্টিশনিং (BSP) রিকার্সিভলি একটি স্পেসকে দুটি কনভেক্স সেটে সাবডিভাইড করতে বাস্তবায়িত হয় হাইপারপ্লেন ব্যবহার করে পার্টিশন হিসেবে। এই সাবডিভাইডিং প্রসেসের ফলাফল হলো একটি ট্রি ডেটা স্ট্রাকচার যেনে BSP ট্রি যা রিজনে অবজেক্টের রিপ্রেজেন্টেশন দেয়।

বাইনারি স্পেস পার্টিশনিং ১৯৬৯ সালে ৩ডি কম্পিউটার গ্রাফিক্স-এ আবিষ্কৃত হয়েছিল, যেখানে BSP ট্রির স্ট্রাকচার অবজেক্টের স্পেশিয়াল ইনফরমেশন এক্সেস করতে দেয় একটি সিনে-এ যা রেন্ডারিং-এ ইউজফুল, যেমন অবজেক্টগুলো অর্ডার করা হয় ফ্রন্ট-টু-ব্যাক একটি ভিউয়ারের লোকেশন সম্পর্কে। BSP-এর অন্যান্য অ্যাপ্লিকেশন: জ্যামিতিক অপারেশন শেপস (কন্সট্রक्टিভ স olid জ্যামিতি) CAD-এ, কলিশন ডিটেকশন ৩ডি ভিডিও গেম এবং রোবটিক্স-এ, রে ট্রেসিং, এবং অন্যান্য অ্যাপ্লিকেশন যারা কমপ্লেক্স স্পেশিয়াল সিনে হ্যান্ডলিং ইনভল্ভ করে।

ওভারভিউ

বাইনারি স্পেস পার্টিশনিং বিবেচিত হয় একটি জেনেরিক প্রসেস রিকার্সিভলি একটি সিনকে দুটি ভাগ করার যতক্ষণ না পার্টিশনিং এক বা অধিক রিকোয়ারমেন্ট স্যাটিসফাই করে। এটিকে ভিউ করা যায় অন্যান্য স্পেশিয়াল ট্রি স্ট্রাকচার যেমন k-d ট্রি এবং কোয়াডট্রি এর জেনারেলাইজেশন হিসেবে, যেখানে হাইপারপ্লেন যারা স্পেস পার্টিশন করে সেগুলোর যেকোনো অরিয়েন্টেশন থাকতে পারে, কোঅর্ডিনেট এক্সিসের সাথে অ্যালাইনড থাকার বদলে যেন k-d ট্রি বা কোয়াডট্রিতে থাকে। কম্পিউটার গ্রাফিক্স-এ রেন্ডারিং সিন কমপোজড অফ প্ল্যানার পলিগন-এর জন্য বাস্তবায়ন করা হলে, পার্টিশনিং প্লেনগুলো প্রায়ই সিলেক্ট করা হয় কোইন্সাইড করতে পলিগন-ডিফাইনড প্লেনসহ সিনে-এ। পার্টিশনিং প্লেনের স্পেসিফিক চয়েস এবং কমপ্লিশনের জন্য ক্রাইটেরি BSP ট্রির উদ্দেশ্যের ওপর ভিন্ন হয়। উদাহরণস্বরূপ, কম্পিউটার গ্রাফিক্স রেন্ডারিং-এ, সিন বিভক্ত হয় যতক্ষণ না BSP ট্রির প্রতিটি নোড শুধু সেই পলিগন নিয়ে গঠিত থাকে যারা আربিট্রারি অর্ডারে রেন্ডার করা যায়। যখন ব্যাক-ফেস কালিং বাস্তবায়িত হয়, তখন প্রতিটি নোড একটি কনভেক্স সেট অফ পলিগন নিয়ে গঠিত, যখন ডাবল-সাইডেড পলিগন রেন্ডার করা হয়, তখন BSP ট্রির প্রতিটি নোড শুধু একটি প্লেনে থাকা পলিগন নিয়ে গঠিত। কলিশন ডিটেকশন বা রে ট্রেসিং-এ, একটি সিন কিছু প্রিমিটিভে ভাগ করা যায় যারা কলিশন বা রে ইন্টারসেকশন টেস্ট সহজ।

জেনারেশন (Generation)

BSP ট্রির ক্যানোনিক্যাল বাস্তবায়ন হলো পলিগন রেন্ডার করা (যারা ডাবল-সাইডেড, অর্থাৎ ব্যাক-ফেস কালিং ছাড়া) পেইন্টারস অ্যালগরিদমের সাহায্যে। প্রতিটি পলিগন একটি ফ্রন্ট সাইড এবং একটি ব্যাক সাইড দিয়ে ডেজিগনেট করা হয় যেটি আর্বিট্রেরিলি চয়েন করা যায় এবং শুধু ট্রির স্ট্রাকচারকে এফেক্ট করে কিন্তু রিকোয়ার্ড রেজাল্টকে নয়। এখান থেকে একটি ট্রি বিল্ট হয় একটি আনসর্টেড লিস্ট অফ সকল পলিগন ইন এ সিন। BSP ট্রি বিল্ড করার রিকার্সিভ অ্যালগরিদম সেই লিস্ট অফ পলিগন থেকে:

• একটি পলিগন A সিলেক্ট করা হয়, লিস্ট থেকে।
• BSP ট্রিতে একটি নোড N বিল্ড করা হয়, এবং A অ্যাড করা হয় পলিগন লিস্টে সেই নোডে।
• লিস্টের প্রতিটি অন্য পলিগনের জন্য
• যদি সেই পলিগন সম্পূর্ণরূপে A-র কন্টেইনিং প্লেনের ফ্রন্টে থাকে, সেই পলিগন মুভ করা হয় A-র ফ্রন্টের নোড লিস্টে।
• যদি সেই পলিগন সম্পূর্ণরূপে A-র কন্টেইনিং প্লেনের পিছনে থাকে, সেই পলিগন মুভ করা হয় P-র পিছনের নোড লিস্টে।
• যদি সেই পলিগন A-র কনসিস্টিং প্লেন দ্বারা ইন্টারসেক্ট করা হয়, তাকে দুটি পলিগনে স্প্লিট করা হয় এবং সেগুলো রেসপেক্টিভলি মুভ করা হয় পিছনের এবং ফ্রন্টের পলিগন লিস্টে।
• যদি সেই পলিগন A-র কন্টেইনিং প্লেনের মধ্যে অবস্থান করে, সেটি নোড N-এ পলিগন লিস্টে অ্যাড করা হয়।
• এই অ্যালগরিদম অ্যাপ্লাই করা হয় A-র ফ্রন্টের পলিগন লিস্টে।
• এই অ্যালগরিদম অ্যাপ্লাই করা হয় A-র পিছনের পলিগন লিস্টে।