ورود

View Full Version : سوال: BSP چیه ؟


AbdolHabib8
شنبه 25 دی 1389, 09:37 صبح
سلام به بچه های انجمن برنامه نویسی گیم :قلب:
کسی میدونه (BSP (Binary Space Partition دقیقا چیه و چطور کار می کنه.
ممنون.
pswin.pooya
شنبه 25 دی 1389, 12:47 عصر
سلام
BSP یک الگوریتم culling (گلچین کردن) برای صحنه های indoor هست. این تکنیک توی بازیهای زیادی مخصوصا بازیهای جان کارمک مثل doom و Quake استفاده شده. این الگوریتم خیلی آسونه. در حقیقت میشه گفت bsp یک شکل مدیریت صحنه هست و هدف اون به حداقل رسوندن پردازشهای گرافیکی و فیزیکی هستش به شکلی که اجسامی که داخل شاخه نباشن نه رسم میشن و نه پردازش:

http://en.wikipedia.org/wiki/Binary_space_partitioning

توی سایت gamedev.net هم مقاله های زیر هستند که میتونن کمکتون بکنند:
http://www.gamedev.net/page/reference/index.html/_/reference/programming/general-programming/data-structures/trees-part-1-r1374

http://www.gamedev.net/page/reference/index.html/_/reference/programming/general-programming/data-structures/trees-part-2-binary-trees-r1433
سپول
شنبه 25 دی 1389, 12:48 عصر
BSP یک نوع ساختار داده درختی دودویی هست که بیشتر برای بهینه سازی گرافیک و scene management استفاده می شه.
اطلاعات و مثلث های یک صحنه سه بعدی رو میاد با یک صفحه مجازی در فضا، به دو قسمت تقسیم می کنه، سپس اون دو قسمت رو دوباره به قسمت های کوچک تر خورد می کنه تا به یک واحد خاص برسه، حالا می تونه این واحد یک مثلث باشه یا یک قسمتی از فضا (convex). در موقع کشیدن صحنه هم میاد اون درخت رو پیمایش می کنه و leaf هاش رو می کشه.

اولین بار توسط John Carmack تو بازی doom استفاده شد، و در اون اوایل برای مرتب کردن مثلث های صحنه بود برای بهینه سازی کشیدن (اون زمان Accelerator گرافیکی نبود). بعداً با اومدن کارت های گرافیک سه بعدی هم در موتور های دیگه به خصوص موتور شرکت idSoftware استفاده می شد برای مواردی مثل scene managemnt و حذف سریع بخش هایی از صحنه که دیده نمی شن (با ترکیب با PVS یا پورتال) ...
در حال حاضر به خاطر پیشرفت تکنولوژی کارت های گرافیک خیلی کمتر استفاده می شه، ولی همچنان در موتور half-life و unreal در جاهایی ازش استفاده می شه. چون پایه کدشون از قدیم بر این اساس بوده.
AbdolHabib8
شنبه 25 دی 1389, 14:39 عصر
BSP یک الگوریتم culling (گلچین کردن) برای صحنه های indoor هست.
پس کاربردی برای صحنه های باز مثل صحنه هایی که توی کرایسیس و آنریل و اساسین می بینیم نداره . درسته ؟

در حال حاضر به خاطر پیشرفت تکنولوژی کارت های گرافیک خیلی کمتر استفاده می شه، ولی همچنان در موتور half-life و unreal در جاهایی ازش استفاده می شه. چون پایه کدشون از قدیم بر این اساس بوده.
پس توی هر بار از حلقه اصلی یاید همه صحنه رو ترسیم کنیم و از این بابت هیچ الگویی برای بهینه سازی بیشتر از سمت CPU نیست. درسته؟
SeganX
شنبه 25 دی 1389, 16:35 عصر
پس توی هر بار از حلقه اصلی یاید همه صحنه رو ترسیم کنیم و از این بابت هیچ الگویی برای بهینه سازی بیشتر از سمت CPU نیست. درسته؟
چرا. معماری صحنه و الگوریتم های زیادی برای بهینه سازی صحنه ها از سمت CPU وجود داره. معمولا در انجین های خفن از ترکیب چند الگوریتم و تکنیک و ... برای بهینه سازیه صحنه استفاده میشه. از استفاده از LOD گرفته تا octree , software occlusion query , pvs , ... و یا hardware occlusion query که با همکاری CPU و GPU محقق میشه و حتی خفن تر اینکه در ورژن های جدید DX یه software occlusion query خفن پیاده شده که جزئیات بیشتر رو سپول می دونه. من خیلی خبر ندارم.
خلاصه اینکه در دنیای گیم سعی کنیم خیلی از کلمات "هیچ" "فقط" "...ترین" زیاد استفاده نکنیم.
AbdolHabib8
یک شنبه 26 دی 1389, 08:20 صبح
از استفاده از LOD گرفته تا octree , software occlusion query , pvs , ... و یا hardware occlusion query که با همکاری CPU و GPU محقق میشه و حتی خفن تر اینکه در ورژن های جدید DX یه software occlusion query خفن پیاده شده که جزئیات بیشتر رو سپول می دونه. من خیلی خبر ندارم.
wow. من تا حالا اسم هیچ کدوم از این ها رو هم نشنیده بودم . می شه لطفا یکی از این الگوریتم ها که کاربرد عمومی داشته باشند (برای همه صحنه ها قابل استفاده باشند) معرفی کنید تا پیگیر بشم. همچنین می شه بدونم خود شما و جناب سپول و pswin.pooya توی معماریتون برای این کار از چه روشی استفاده می کنید؟
seyedof
یک شنبه 26 دی 1389, 12:58 عصر
سلام

الگوریتمهای مدیریت صحنه تعدادشون خیلی زیاد نیست. اینکه کدوم بهتره یا... زیاد مطرح نیست و بستگی به نوع بازی و محیطی که میخواهید رندر کنید داره. مثلا برای محیطهای Indoor یا Outdoor الگوریتمهای مختلفی هست. در اکثر موتورهای بازی بیشتر از ترکیبی از این روشها استفاده میشه. در مورد BSP Tree غیر از Culling میتونه مثلثهای محیط رو sort کنه که شما بتونید از دور به نزدیک یا برعکس اوونها رو ترسیم کنید که این مورد خودش یک بهینه سازی مفید به حساب میاد. در بازیهای جدید به دلیل تعداد بالای مثلث و CPU یی بودن این روش کمتر ازش استفاده میشه و روشهایی مثل Portal و PVS بیشتر کاربرد دارند. این الگوریتم جدید نبوده و نیست و توی بازی DOOM برای اولین بار در یک بازی ازش استفاده شد هر چند خود الگوریتم پیش از اوون وجود داشت، توی اوون بازی چون Software Rendering بود کشیدن صحنه از جلو به عقب با ترتیب صحیح خیلی مهم بود چون چیزی به اسم ZBuffer سخت افزاری وجود نداشت و BSP Tree به خوبی اینکارو میکرد.

دنبال الگوریتمی که برای همه کارها جواب بده نگردید. حتی در مورد بعضی بازیها شاید روشهای دیگه خیلی بهتر و سریعتر باشند. اگه بازی شما Indoor است توصیه میکنم روی Portal و PVS و بعد روی Occlusion Culling کار کنید. اگر هم Outdoor است روشهایی مثل Geo Mipmap خوب جواب میده و GPU Friendly هم هست.

ممنون علی
سپول
یک شنبه 26 دی 1389, 13:16 عصر
سلام
BSP یک الگوریتم culling (گلچین کردن) برای صحنه های indoor هست. این تکنیک توی بازیهای زیادی مخصوصا بازیهای جان کارمک مثل doom و Quake استفاده شده. این الگوریتم خیلی آسونه. در حقیقت میشه گفت bsp یک شکل مدیریت صحنه هست و هدف اون به حداقل رسوندن پردازشهای گرافیکی و فیزیکی هستش به شکلی که اجسامی که داخل شاخه نباشن نه رسم میشن و نه پردازش:


البته BSP "خیلی آسون" نیست. من نمی دونم همچین چیزی رو پیاده کردین یا فقط راجع بهش خوندین.

چند سال پیش که من یک BSP + PVS کامپایلر می ساختم کار بسیار مشکلی بود. خوندن تئوری تا پیاده سازی عملی زمین تا آسمون فرق داره، این الگوریتم مشکلات بزرگی هنگام ساختن درخت BSP از جمله T-Junction ها، بالانس درست درخت، سرعت و تشخیص سوراخ ها در صحنه، خطاهای floating point precision و ...
pswin.pooya
یک شنبه 26 دی 1389, 15:57 عصر
البته BSP "خیلی آسون" نیست. من نمی دونم همچین چیزی رو پیاده کردین یا فقط راجع بهش خوندین.نه فقط راجبش خوندم. من رو octree کار کردم. البته روی octree هم مشکلاتی رو داشتم.

حق با شماست بین تئوری تا عمل خیلی فاصله هستش. البته منظور من الگوریتمش بود. این مورد توی گیم انجین هم سختر میشه.
AbdolHabib8
دوشنبه 27 دی 1389, 08:10 صبح
ممنون از دوستان.
یه ایده هایی اومد به ذهنم مثلا من می تونم توی فیزیکم یه هرم ناقص داشته باشم که همراه دوربین بچرخه و مثلا می تونم تنها اشیائی رو که داخل هرمند (با اون برخورد داشته باشند) رو بفرستم برای ترسیم.به جز این یه الگوریتم Scene Management چه کمک دیگه ای برای بهینگی می تونه به من کنه ؟
seyedof
دوشنبه 27 دی 1389, 09:20 صبح
سلام

این روش هرم که میگین بهش میگن Frustum Culling که ساده ترین روش Culling و حذف اشیاء اضافه خارج از میدان دید دوربینه. البته نباید با فیزیک اینکارو بکنید. اینکه یک شی (Bounding اوون شی) توی هرم دید دوربین هست یا نه رو میشه رو میشه محاسبه کرد و منطقی نیست با فیزیک اینکار رو بکنید.

ممنون علی
kochol
دوشنبه 27 دی 1389, 16:24 عصر
سلام

این روش هرم که میگین بهش میگن Frustum Culling که ساده ترین روش Culling و حذف اشیاء اضافه خارج از میدان دید دوربینه. البته نباید با فیزیک اینکارو بکنید. اینکه یک شی (Bounding اوون شی) توی هرم دید دوربین هست یا نه رو میشه رو میشه محاسبه کرد و منطقی نیست با فیزیک اینکار رو بکنید.

ممنون علی

سلام
شاید هم ایده بدی نباشه که از موتور فیزیک استفاده کنه برای این کار اتفاقا تو داکیومنت های PhysX یه مطلب بود که چه طوری Frustum culling رو با PhysX انجام بدی.
PhysX خودش حداقل این باکس هاشو پارتیشن بندی می کنه