پارتیشن بندی فضای دودویی

الگو:توضیحات کوتاه خطاب به K-d tree، Octree و Quadtree: الگو:به نقل‌قول‌های بیشتری نیاز است thumb|300x300px|فرایند ساخت درخت BSP در علوم کامپیوتر، ""پارتیشن بندی فضای دودویی"" ("BSP") روشی برای پارتیشن بندی فضا است که به صورت بازگشتی یک فضای اقلیدسی را تقسیم می کند. با استفاده از hyperplanes به عنوان پارتیشن به دو مجموعه محدب ثانیه تبدیل شود. این فرآیند تقسیم بندی، نمایشی از اشیاء درون فضا را در قالب یک ساختار داده درختی که به عنوان ""درخت BSP"" شناخته می شود، ایجاد می کند.

پارتیشن بندی فضای باینری در زمینه گرافیک کامپیوتری سه بعدی در سال 1969 توسعه یافت. ساختار درخت BSP در رندر زیرا می تواند به طور موثر اطلاعات فضایی در مورد اشیاء در یک صحنه ارائه دهد، مانند اشیایی که از جلو به عقب با توجه به بیننده در یک مکان معین سفارش داده می شوند. سایر کاربردهای BSP عبارتند از: انجام عملیات هندسی با شکلها (هندسه جامد سازنده) در CAD، تشخیص برخورد در رباتیک و بازی‌های ویدیویی سه بعدی، ردیابی پرتو، و سایر برنامه‌هایی که شامل مدیریت پیچیده هستند صحنه های فضایی

نمای کلی

پارتیشن بندی فضای دودویی یک فرآیند عمومی برای تقسیم یک صحنه به دو قسمت است تا زمانی که پارتیشن بندی یک یا چند نیاز را برآورده کند. می‌توان آن را به‌عنوان تعمیم ساختارهای درختی فضایی دیگر مانند k-d trees و quadtrees در نظر گرفت، جایی که ابرصفحه‌هایی که فضا را تقسیم می‌کنند ممکن است هر جهتی داشته باشند. نسبت به تراز شدن با محورهای مختصات همانطور که در درختان k-d یا چهار درخت هستند. هنگامی که در گرافیک کامپیوتری برای ارائه صحنه های متشکل از مسطح چند ضلعی استفاده می شود، صفحات پارتیشن بندی اغلب به گونه ای انتخاب می شوند که با صفحات تعریف شده توسط چندضلعی ها در صحنه منطبق باشند.

انتخاب خاص صفحه پارتیشن بندی و معیار برای پایان دادن به فرآیند پارتیشن بندی بسته به هدف درخت BSP متفاوت است. به عنوان مثال، در رندر گرافیک کامپیوتری، صحنه تا زمانی تقسیم می شود که هر گره درخت BSP فقط شامل چند ضلعی باشد که می توانند به ترتیب دلخواه رندر شوند. هنگامی که قطع کردن پشت چهره استفاده می شود، بنابراین هر گره حاوی مجموعه ای محدب از چند ضلعی ها است، در حالی که هنگام ارائه چند ضلعی های دو طرفه، هر گره درخت BSP فقط شامل چند ضلعی ها در یک صفحه واحد است. در تشخیص برخورد یا ردیابی پرتو، یک صحنه ممکن است به primitives تقسیم شود که در آن آزمایش‌های برخورد یا تقاطع پرتو ساده هستند.

پارتیشن بندی فضای دودویی ناشی از نیاز گرافیک کامپیوتری به ترسیم سریع صحنه های سه بعدی متشکل از چند ضلعی است. یک راه ساده برای ترسیم چنین صحنه‌هایی الگوریتم نقاش است که چند ضلعی‌ها را به ترتیب فاصله از بیننده، پشت به جلو، نقاشی روی پس‌زمینه و چند ضلعی‌های قبلی با هر شی نزدیک‌تر تولید می‌کند. این روش دو عیب دارد: زمان لازم برای مرتب سازی چند ضلعی ها به ترتیب پشت به جلو و احتمال خطا در چند ضلعی های همپوشانی. فوکس و همکارانش نشان دادند که ساخت یک درخت BSP با ارائه روشی سریع برای مرتب‌سازی چندضلعی‌ها با توجه به یک دیدگاه معین (خطی از نظر تعداد چندضلعی‌ها در صحنه) هر دوی این مشکلات را حل کرد. و با تقسیم چند ضلعی های همپوشانی برای جلوگیری از خطاهایی که ممکن است در الگوریتم نقاش رخ دهد. یک نقطه ضعف پارتیشن بندی فضای دودویی این است که تولید یک درخت BSP می تواند زمان بر باشد. به طور معمول، یک بار در هندسه استاتیک، به عنوان یک مرحله پیش محاسبه، قبل از رندر یا سایر عملیات بلادرنگ روی یک صحنه انجام می شود. هزینه ساخت یک درخت BSP، پیاده سازی مستقیم اشیاء متحرک در یک درخت را دشوار و ناکارآمد می کند.

درختان BSP اغلب توسط بازی ویدئوییهای سه بعدی، به ویژه تیراندازی اول شخص و آنهایی که دارای محیط های داخلی هستند استفاده می شوند. موتور بازیهایی که از درخت‌های BSP استفاده می‌کنند شامل Doom (id Tech 1)، Quake (ID Tech 2 نوع)، GoldSrc و [[منبع] (موتور بازی)|منبع]] موتورهای. در آنها، درختان BSP حاوی هندسه ایستا یک صحنه اغلب همراه با یک Z-buffer برای ادغام صحیح اشیاء متحرک مانند درها و کاراکترها در صحنه پس‌زمینه استفاده می‌شوند. در حالی که پارتیشن بندی فضای دودویی راه مناسبی برای ذخیره و بازیابی اطلاعات فضایی در مورد چند ضلعی ها در یک صحنه فراهم می کند، مشکل تعیین سطح قابل مشاهده را حل نمی کند.

نسل

استفاده متعارف درخت BSP برای رندر کردن چند ضلعی ها (که دو طرفه هستند، یعنی بدون قطع کردن پشت صورت) با الگوریتم نقاش است. هر چند ضلعی با یک ضلع جلویی و یک سمت پشتی مشخص می شود که می تواند به طور دلخواه انتخاب شود و فقط بر ساختار درخت تأثیر می گذارد اما بر نتیجه لازم تأثیر نمی گذارد. چند ضلعی ها در یک صحنه الگوریتم بازگشتی برای ساخت یک درخت BSP از آن لیست چند ضلعی ها عبارت است از:

1. یک چند ضلعی "P" از لیست انتخاب کنید.
2. یک گره N در درخت BSP ایجاد کنید، و P را به لیست چند ضلعی های آن گره اضافه کنید.
3. برای یک چند ضلعی دیگر در لیست:
   1. اگر آن چند ضلعی کاملاً جلوی صفحه حاوی P است، آن چند ضلعی را به لیست گره های جلوی P منتقل کنید.
   2. اگر آن چند ضلعی کاملاً پشت صفحه حاوی «P» است، آن چند ضلعی را به لیست گره‌های پشت «P» منتقل کنید.
   3. اگر آن چند ضلعی با صفحه حاوی P قطع شد، آن را به دو چند ضلعی تقسیم کنید و آنها را به لیست های مربوط به چند ضلعی های پشت و جلوی P منتقل کنید.
   4. اگر آن چند ضلعی در صفحه حاوی "P" قرار دارد، آن را به لیست چند ضلعی های گره "N" اضافه کنید.
4. این الگوریتم را در لیست چند ضلعی های جلوی "P" اعمال کنید.
5. این الگوریتم را در لیست چند ضلعی های پشت "P" اعمال کنید.

نمودار زیر استفاده از این الگوریتم را در تبدیل لیستی از خطوط یا چندضلعی ها به درخت BSP نشان می دهد. در هر یک از هشت مرحله (i.-viii.)، الگوریتم بالا به لیستی از خطوط اعمال می شود و یک گره جدید به درخت اضافه می شود.

	با فهرستی از خطوط (یا به صورت چندضلعی سه بعدی) شروع کنید که صحنه را تشکیل می دهند. در نمودارهای درختی، لیست ها با مستطیل های گرد و گره ها در درخت BSP با دایره ها مشخص می شوند. در نمودار فضایی خطوط، جهت انتخاب شده به عنوان "جلو" یک خط با یک فلش نشان داده می شود.	پرونده:نمونه ای از ساخت درخت BSP - مرحله 1.svg
من.	طبق مراحل الگوریتم بالا، یک خط A را از لیست انتخاب می کنیم و... ... آن را به یک گره اضافه کنید. ما خطوط باقیمانده در لیست را به خطوط جلوی A (یعنی B2، C2، D2) و خطوط پشت (B1، C1، D1) تقسیم می کنیم. ابتدا خطوط جلوی A را پردازش می کنیم (در مراحل ii–v)،... ... توسط کسانی که پشت سر هستند دنبال می شوند (در مراحل vi–vii).	پرونده:نمونه ای از ساخت درخت BSP - مرحله 2.svg
ii.	اکنون الگوریتم را به لیست خطوط جلوی A (شامل B2، C2، D2) اعمال می کنیم. یک خط B2 را انتخاب می کنیم، آن را به یک گره اضافه می کنیم و بقیه لیست را به خطوطی که در جلوی B2 قرار دارند (D2) و آنهایی که در پشت آن هستند (C2, D3) تقسیم می کنیم.	پرونده:نمونه ای از ساخت درخت BSP - مرحله 3.svg
iii.	یک خط، D2 را از لیست خطوط جلوی B2 و A انتخاب کنید. این تنها خط در لیست است، بنابراین پس از افزودن آن به یک گره، هیچ کاری دیگر لازم نیست انجام شود.	پرونده:نمونه ای از ساخت درخت BSP - مرحله 4.svg
'IV.	کار ما با خطوط جلوی B2 تمام شده است، بنابراین خطوط پشت B2 (C2 و D3) را در نظر بگیرید. یکی از اینها (C2) را انتخاب کنید، آن را به یک گره اضافه کنید و خط دیگر را در لیست (D3) در لیست خطوط جلوی C2 قرار دهید.	پرونده:نمونه ای از ساخت درخت BSP - مرحله 5.svg
""v."	حالا به لیست خطوط جلوی C2 نگاه کنید. فقط یک خط (D3) وجود دارد، بنابراین آن را به یک گره اضافه کنید و ادامه دهید.	پرونده:نمونه ای از ساخت درخت BSP - مرحله 6.svg
vi.	ما اکنون تمام خطوط جلوی A را به درخت BSP اضافه کرده‌ایم، بنابراین اکنون از لیست خطوط پشت A شروع می‌کنیم. با انتخاب یک خط (B1) از این لیست، B1 را به یک گره اضافه می‌کنیم و باقیمانده را تقسیم می‌کنیم. لیست را به خطوط جلوی B1 (یعنی D1) و خطوط پشت B1 (یعنی C1) تشکیل می دهد.	پرونده:نمونه ای از ساخت درخت BSP - مرحله 7.svg
vii.	ابتدا لیست خطوط جلوی B1 را پردازش کنید، D1 تنها خط در این لیست است، بنابراین این را به یک گره اضافه کنید و ادامه دهید.	پرونده:نمونه ای از ساخت درخت BSP - مرحله 8.svg
viii.	نگاه بعدی به tلیست خطوط پشت B1، تنها خط در این لیست C1 است، بنابراین این را به یک گره اضافه کنید، و درخت BSP کامل می شود.	پرونده:نمونه ای از ساخت درخت BSP - مرحله 9.svg

تعداد نهایی چند ضلعی ها یا خطوط در یک درخت اغلب بزرگتر است (گاهی اوقات بسیار بزرگتر) از لیست اصلی، زیرا خطوط یا چند ضلعی هایی که از صفحه پارتیشن بندی عبور می کنند باید به دو قسمت تقسیم شوند. مطلوب است که این افزایش را به حداقل برسانیم، اما همچنین تعادل معقول را در درخت نهایی حفظ کنیم. انتخاب اینکه کدام چند ضلعی یا خط به عنوان صفحه پارتیشن بندی استفاده می شود (در مرحله 1 الگوریتم) بنابراین در ایجاد یک درخت BSP کارآمد مهم است.

خط زمانی

• 1969 Schumacker et al. گزارشی منتشر کرد که توضیح می‌داد چگونه هواپیماهای با دقت در یک محیط مجازی می‌توانند برای تسریع ترتیب چند ضلعی استفاده شوند. در این تکنیک از انسجام عمق استفاده می‌شود، که بیان می‌کند که یک چند ضلعی در سمت دور صفحه به هیچ وجه نمی‌تواند مانع چند ضلعی نزدیک‌تر شود. این در شبیه سازهای پرواز ساخته شده توسط جنرال الکتریک و همچنین ایوانز و ساترلند استفاده شد. با این حال، ایجاد سازمان داده های چند ضلعی به صورت دستی توسط طراح صحنه انجام شد.

• 1980 Fuchs و همکاران ایده شوماکر را به نمایش اشیاء سه بعدی در یک محیط مجازی با استفاده از صفحاتی که با چند ضلعی ها منطبق هستند برای تقسیم بازگشتی فضای سه بعدی گسترش دادند. این یک تولید کاملاً خودکار و الگوریتمی از یک ساختار داده چند ضلعی سلسله مراتبی به نام درخت تقسیم‌بندی فضایی دودویی (BSP Tree) ارائه کرد. این فرآیند به عنوان یک مرحله پیش پردازش آفلاین انجام شد که یک بار در هر محیط/شیء انجام شد. در زمان اجرا، ترتیب دید وابسته به دید با عبور از درخت ایجاد شد.
• 1981 دکترای نایلور. پایان نامه توسعه کاملی از هر دو درخت BSP و یک رویکرد تئوری گراف با استفاده از اجزای قوی متصل برای مشاهده پیش محاسباتی، و همچنین ارتباط بین دو روش ارائه کرد. درختان BSP به عنوان یک ساختار جستجوی فضایی مستقل از بعد با کاربردهایی برای تعیین سطح قابل مشاهده مورد تاکید قرار گرفتند. این پایان نامه همچنین شامل اولین داده های تجربی بود که نشان می داد اندازه درخت و تعداد چند ضلعی های جدید معقول است (با استفاده از مدل شاتل فضایی).
• 1983 فوکس و همکاران. پیاده سازی میکروکد الگوریتم درختی BSP را بر روی یک سیستم بافر قاب Ikonas توضیح داد. این اولین نمایش تعیین سطح قابل مشاهده بلادرنگ با استفاده از درختان BSP بود.
• 1987 Thibault و Naylor توضیح دادند که چگونه چند وجهی دلخواه ممکن است با استفاده از درخت BSP بر خلاف b-rep سنتی (نمایش مرزی) نمایش داده شود. این یک نمایش جامد در مقابل یک نمایش مبتنی بر سطح ارائه کرد. عملیات مجموعه روی چند وجهی با استفاده از ابزاری توصیف شد که هندسه جامد سازنده (CSG) را در زمان واقعی فعال می‌کند. این پیشرو در طراحی سطح BSP با استفاده از «براش‌ها بود، که در ویرایشگر Quake معرفی شد و در ویرایشگر Unreal انتخاب شد.
• 1990 Naylor، Amanatides و Thibault الگوریتمی برای ادغام دو درخت BSP برای تشکیل یک درخت BSP جدید از دو درخت اصلی ارائه کردند. این مزایا بسیاری از جمله ترکیب اجسام متحرک نشان داده شده توسط درختان BSP با یک محیط ساکن (همچنین با درخت BSP نشان داده می شود)، عملیات CSG بسیار کارآمد در چند وجهی، تشخیص دقیق برخورد در O(log n * log n) و ترتیب صحیح شفاف سطوح موجود در دو جسم متقابل (برای اثر دید اشعه ایکس استفاده شده است).
• 1990 Teller و Séquin تولید آفلاین مجموعه‌های بالقوه قابل مشاهده را برای تسریع در تعیین سطح مرئی در محیط‌های دوبعدی متعامد پیشنهاد کردند.
• 1991 گوردون و چن [CHEN91] یک روش کارآمد برای اجرای رندر جلو به عقب از درخت BSP، به جای رویکرد سنتی پشت به جلو، توصیف کردند. آنها از یک ساختار داده ویژه برای ضبط موثر بخش هایی از صفحه که ترسیم شده اند و آنهایی که هنوز ارائه نشده اند استفاده کردند. این الگوریتم همراه با شرح درختان BSP در کتاب استاندارد گرافیک کامپیوتری آن روز (گرافیک کامپیوتر: اصول و تمرین) توسط John Carmack در ساخت Doom (بازی ویدیویی).
• 1992 Teller's Ph.D. پایان نامه تولید کارآمد مجموعه های بالقوه قابل مشاهده را به عنوان یک مرحله پیش پردازش برای تسریع در تعیین سطح مرئی بلادرنگ در محیط های چند ضلعی دلخواه سه بعدی توصیف کرد. این مورد در Quake استفاده شد و کمک قابل توجهی به عملکرد آن بازی کرد.
• 1993 نیلور به این سوال پاسخ داد که چه چیزی یک درخت BSP خوب را مشخص می کند. او از مدل‌های مورد انتظار (به جای تحلیل بدترین حالت) برای اندازه‌گیری ریاضی هزینه مورد انتظار جستجوی درخت استفاده کرد و از این معیار برای ساخت درخت‌های BSP خوب استفاده کرد. به طور شهودی، درخت یک شی را با وضوح چندگانه (دقیقاً به عنوان درختی از تقریب ها) نشان می دهد. موازی با کدهای هافمن و درختان جستجوی دودویی احتمالی ترسیم شده است.
• 1993 دکترای حیدر رادا. پایان نامه روش های نمایش تصویر (طبیعی) را با استفاده از درختان BSP تشریح کرد. این شامل توسعه یک چارچوب ساخت درخت BSP بهینه برای هر ar استتصویر ورودی بیتی این چارچوب مبتنی بر تبدیل تصویر جدید است که به عنوان تبدیل خط تقسیم‌بندی حداقل مربعات خطا (LSE) شناخته می‌شود. پایان نامه H. Radha همچنین چارچوب فشرده سازی تصویر با نرخ اعوجاج بهینه (RD) و رویکردهای دستکاری تصویر را با استفاده از درختان BSP ایجاد کرد.

پیمایش

درخت BSP پیمایش در یک زمان خطی است، به ترتیبی که توسط تابع خاص درخت تعیین می‌شود. دوباره با استفاده از مثال ارائه چند ضلعی های دو طرفه با استفاده از الگوریتم نقاش، برای ترسیم درست یک چند ضلعی "P" مستلزم این است که ابتدا همه چند ضلعی های پشت صفحه "P" در آن قرار دارد، سپس چند ضلعی "P" ترسیم شوند. "، سپس چند ضلعی های روبروی "P". اگر این ترتیب ترسیم برای همه چند ضلعی ها در یک صحنه برآورده شود، کل صحنه به ترتیب صحیح ارائه می شود. این رویه را می‌توان با پیمایش بازگشتی یک درخت BSP با استفاده از الگوریتم زیر پیاده‌سازی کرد.

1. اگر گره فعلی یک گره برگ است، چند ضلعی ها را در گره فعلی رندر کنید.
2. در غیر این صورت، اگر مکان مشاهده "V" در مقابل گره فعلی باشد:
   1. درخت BSP فرزند حاوی چند ضلعی در پشت گره فعلی رندر کنید
   2. چند ضلعی ها را در گره فعلی رندر کنید
   3. درخت BSP فرزند حاوی چند ضلعی در مقابل گره فعلی رندر کنید
3. در غیر این صورت، اگر مکان مشاهده "V" پشت گره فعلی باشد:
   1. درخت BSP فرزند حاوی چند ضلعی در مقابل گره فعلی رندر کنید
   2. چند ضلعی ها را در گره فعلی رندر کنید
   3. درخت BSP فرزند حاوی چند ضلعی در پشت گره فعلی رندر کنید
4. در غیر این صورت، مکان مشاهده "V" باید دقیقاً در صفحه مرتبط با گره فعلی باشد. سپس:
   1. درخت BSP فرزند حاوی چند ضلعی در مقابل گره فعلی رندر کنید
   2. درخت BSP فرزند حاوی چند ضلعی در پشت گره فعلی رندر کنید

پرونده:نمونه ای از BSP Treversal.svg

اعمال این الگوریتم به صورت بازگشتی به درخت BSP تولید شده در بالا، مراحل زیر را به همراه دارد:

• الگوریتم ابتدا روی گره ریشه درخت، گره A اعمال می شود. "V" جلوی گره "A" است، بنابراین الگوریتم را ابتدا به درخت BSP فرزند حاوی چند ضلعی های پشت "A" اعمال می کنیم.
  • این درخت دارای گره ریشه "B1" است. "V" پشت "B1" است، بنابراین ابتدا الگوریتم را به درخت BSP فرزند حاوی چند ضلعی در جلوی "B1" اعمال می کنیم:
    • این درخت فقط گره برگ D1 است، بنابراین چند ضلعی D1 ارائه می شود.
  • سپس چند ضلعی را B1 ارائه می کنیم.
  • سپس الگوریتم را به درخت BSP فرزند حاوی چند ضلعی های پشت "B1" اعمال می کنیم:
    • این درخت فقط گره برگ C1 است، بنابراین چند ضلعی C1 ارائه می شود.
• سپس چند ضلعی های A را رسم می کنیم
• سپس الگوریتم را به درخت BSP فرزند حاوی چند ضلعی در جلوی "A" اعمال می کنیم.
  • این درخت دارای گره ریشه "B2" است. "V" پشت "B2" است، بنابراین ابتدا الگوریتم را به درخت BSP فرزند حاوی چند ضلعی در جلوی "B2" اعمال می کنیم:
    • این درخت فقط گره برگ D2 است، بنابراین چند ضلعی D2 ارائه می شود.
  • سپس چند ضلعی "B2" را ارائه می کنیم.
  • سپس الگوریتم را به درخت BSP فرزند حاوی چند ضلعی های پشت "B2" اعمال می کنیم:
    • این درخت دارای گره ریشه C2 است. "V" جلوی "C2" است، بنابراین ابتدا الگوریتم را برای درخت BSP فرزند حاوی چند ضلعی در پشت "C2" اعمال می کنیم. با این حال، چنین درختی وجود ندارد، بنابراین ادامه می دهیم.
    • چند ضلعی را C2 ارائه می کنیم.
    • الگوریتم را به درخت BSP فرزند حاوی چند ضلعی در جلوی "C2" اعمال می کنیم.
      • این درخت فقط گره برگ "D3" است، بنابراین چند ضلعی "D3" ارائه می شود.

درخت در زمان خطی پیمایش می‌شود و چند ضلعی‌ها را به ترتیب دور به نزدیک نمایش می‌دهد ("D1"، "B1"، "C1"، "A"، "D2"، B2، C2، D3) مناسب برای الگوریتم نقاش.

همچنین ببینید

• درخت k-d
• اکتبر
• Quadtree
• خوشه‌بندی سلسله مراتبی، روشی جایگزین برای تقسیم داده‌های مدل سه‌بعدی برای ارائه کارآمد.
• برش گیوتین

منابع اضافی

• الگو:به نقل از مجله
• الگو:نقل به پایان نامه
• https://ui.adsabs.harvard.edu/abs/1996ITIP....5.1610R /خلاصه
• الگو:به سند
• الگو:نقل به کتاب الگوریتم نقاش تصادفی شده را توصیف می کند..
• الگو:نقل به کتاب

الگو:بازخوانی

لینک های خارجی

• Naylor, B.F. (2005). "آموزش درختان پارتیشن بندی فضای دودویی".
• ارائه درختان BSP
• یکی دیگر از ارائه درختان BSP
• یک اپلت جاوا که فرآیند تولید درخت را نشان می دهد
• پایان نامه کارشناسی ارشد در مورد تولید BSP
• BSP Trees: Theory and Implementation
• BSP در فضای سه بعدی

الگو:کنترل مرجع

This article "پارتیشن بندی فضای دودویی" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:پارتیشن بندی فضای دودویی. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---

 Facebook Page

 Follow us on Twitter !

Read or create/edit this page in another language

• پارتیشن بندی فضای دودویی in English