কম্পিউটার বিজ্ঞানে, বাইনারি স্পেস পার্টিশনিং (BSP) নামে পরিচিত একটি পদ্ধতি প্রয়োগ করা হয় একটি স্পেসকে পার্টিশন হিসেবে হাইপারপ্লেন প্রয়োগ করে দুটি উত্তল সেটে পুনরাবৃত্তভাবে উপবিভাজন করার জন্য। উপবিভাগের এই প্রক্রিয়াটি একটি বিএসপি ট্রি নামে পরিচিত একটি ট্রি ডেটা স্ট্রাকচারের আকারে অঞ্চলের মধ্যে বস্তুর উপস্থাপনা তৈরি করে।
বাইনারি স্পেস পার্টিশনিং 1969 সালে 3D কম্পিউটার গ্রাফিক্সের প্রেক্ষাপটে উদ্ভাবিত হয়েছিল, যেখানে একটি BSP গাছের কাঠামো এমন একটি দৃশ্যের বস্তু সম্পর্কে স্থানিক তথ্যের জন্য অনুমতি দেয় যা রেন্ডারিংয়ের জন্য দরকারী, যেমন বস্তুগুলি সামনে থেকে পিছনের সাথে অর্ডার করা হয়। একটি প্রদত্ত অবস্থানে একটি দর্শকের প্রতি সম্মান, দ্রুত অ্যাক্সেস করা। BSP-এর অন্যান্য অ্যাপ্লিকেশন অন্তর্ভুক্ত:CAD-তে আকার (গঠনমূলক কঠিন জ্যামিতি) সহ জ্যামিতিক ক্রিয়াকলাপ সম্পন্ন করা, 3D ভিডিও গেমস এবং রোবোটিক্সে সংঘর্ষ সনাক্তকরণ, রে ট্রেসিং এবং অন্যান্য অ্যাপ্লিকেশন যা জটিল স্থানিক দৃশ্য পরিচালনার সাথে জড়িত।
ওভারভিউ
বাইনারি স্পেস পার্টিশনিং একটি দৃশ্যকে পুনরাবৃত্তিমূলকভাবে দুই ভাগে ভাগ করার একটি সাধারণ প্রক্রিয়া হিসাবে বিবেচিত হয় যতক্ষণ না পার্টিশনিং এক বা একাধিক প্রয়োজনীয়তা পূরণ করে। এটি কে-ডি ট্রি এবং কোয়াডট্রির মতো অন্যান্য স্থানিক বৃক্ষের কাঠামোর সাধারণীকরণ হিসাবে দেখা যেতে পারে, যেখানে হাইপারপ্লেন যেগুলি স্থানকে বিভাজন করে তাদের কোন অভিযোজন থাকতে পারে, স্থানাঙ্ক অক্ষগুলির সাথে সারিবদ্ধ হওয়ার পরিবর্তে যেগুলি k-d গাছ বা চতুর্গাছে রয়েছে। প্ল্যানার বহুভুজ দ্বারা গঠিত দৃশ্য রেন্ডার করার জন্য কম্পিউটার গ্রাফিক্সে প্রয়োগ করা হলে, দৃশ্যের বহুভুজ দ্বারা সংজ্ঞায়িত প্লেনের সাথে মিলিত হওয়ার জন্য পার্টিশনিং প্লেনগুলি প্রায়শই নির্বাচন করা হয়। বিএসপি ট্রির উদ্দেশ্যের উপর নির্ভর করে পার্টিশনিং প্লেনের নির্দিষ্ট পছন্দ এবং পার্টিশন প্রক্রিয়া সম্পূর্ণ করার জন্য মাপদণ্ড পরিবর্তিত হয়। উদাহরণস্বরূপ, কম্পিউটার গ্রাফিক্স রেন্ডারিং-এ, দৃশ্যটি বিভক্ত করা হয় যতক্ষণ না BSP গাছের প্রতিটি নোডে শুধুমাত্র বহুভুজ থাকে যা নির্বিচারে রেন্ডার করতে পারে। যখন ব্যাক-ফেস কুলিং প্রয়োগ করা হয়, তখন প্রতিটি নোডে বহুভুজের একটি উত্তল সেট থাকে, যেখানে দ্বিমুখী বহুভুজ রেন্ডার করার সময়, BSP গাছের প্রতিটি নোড একটি একক সমতলে শুধুমাত্র বহুভুজ নিয়ে গঠিত। সংঘর্ষ সনাক্তকরণ বা রশ্মি সনাক্তকরণে, একটি দৃশ্যকে কিছু আদিম অংশে বিভক্ত করা যেতে পারে যার উপর সংঘর্ষ বা রশ্মি ছেদ পরীক্ষা করা সহজ।
প্রজন্ম
চিত্রকরের অ্যালগরিদমের সাহায্যে একটি বিএসপি ট্রির ক্যানোনিকাল বাস্তবায়ন হল বহুভুজ (যেটি দ্বি-পার্শ্বযুক্ত, অর্থাৎ পিছনের মুখ কাটা ছাড়া) রেন্ডার করার জন্য। প্রতিটি বহুভুজ একটি সামনের দিক এবং একটি পিছনের দিক দিয়ে মনোনীত করা হয়েছে যা নির্বিচারে বেছে নেওয়া যেতে পারে এবং শুধুমাত্র গাছের গঠনকে প্রভাবিত করে কিন্তু প্রয়োজনীয় ফলাফল নয়। এই ধরনের একটি গাছ একটি দৃশ্যের সমস্ত বহুভুজের একটি সাজানো তালিকা থেকে তৈরি করা হয়েছে। বহুভুজের সেই তালিকা থেকে একটি BSP ট্রি তৈরির জন্য পুনরাবৃত্ত অ্যালগরিদম হল
- তালিকা থেকে একটি বহুভুজ A নির্বাচন করুন।
- BSP গাছে একটি নোড N তৈরি করুন এবং সেই নোডে বহুভুজের তালিকায় A যোগ করুন।
- তালিকার একে অপরের বহুভুজের জন্য
- যদি সেই বহুভুজটি A সমতলের সম্পূর্ণ সামনে থাকে, তাহলে সেই বহুভুজটিকে A-এর সামনের নোডের তালিকায় নিয়ে যান।
- যদি সেই বহুভুজটি A সম্বলিত সমতলের সম্পূর্ণ পিছনে অবস্থিত থাকে, তাহলে সেই বহুভুজটিকে P এর পিছনের নোডের তালিকায় নিয়ে যান।
- যদি সেই বহুভুজটি A দ্বারা গঠিত সমতল দ্বারা ছেদ করা হয়, তবে এটিকে দুটি বহুভুজে বিভক্ত করুন এবং P এর পিছনে এবং সামনে অবস্থিত বহুভুজের সংশ্লিষ্ট তালিকায় নিয়ে যান।
- যদি সেই বহুভুজটি A সমতলের মধ্যে থাকে, তাহলে এটিকে N নোডে বহুভুজের তালিকায় যোগ করুন।
- A এর সামনে অবস্থিত বহুভুজের তালিকায় এই অ্যালগরিদমটি প্রয়োগ করুন।
- A এর পিছনে অবস্থিত বহুভুজের তালিকায় এই অ্যালগরিদমটি প্রয়োগ করুন।
