[johnsss]

سلام مجدد به دوستان

اين topic در اصل ادامه topic قبلی هست (که متأسفانه در جای درستی نبود) ولی ali جان گفتند که اينها رو با هم تلفيق ميکنند.

جواب يکی از دوستان که پرسيده بود BSP و Grid چی هستند رو ميخواستم بگم. اين مقوله البته يک مقدار پيشرفته هست و با اين چند خط نميتونيد دقيقا بهش پی ببريد. ولی حداقل شروع خوبی خواهد بود (اميدوارم).

BSP, Grid, KD-Tree, BB, AABB و Hierarchical Bounding Boxes (HBB) ها روش هايی برای optimize کردن هستند.اگر تازه داريد يک موتور مينويسيد به شما شديدا توصيه ميکنم که به سمت optimization techniques نريد. ولی دونستن در موردشون بد نيست (optimization در ابتدای کار فقط کار رو سخت تر ميکنه).

حال ببينيم که اينا چی رو optimize ميکنن... در rendering يکی از مشکلات اصلی نداشتن visibility information هست. در ray tracing & global illumination بدون دونستن هيچ چيزی در مورد صحنه و فرض اينکه صحنه 100،000 poly داشته باشه (که خيلی عادی هستش) بايد در هر پيکسل حداقل 100،000 بار چک کنيم که آيا ray ما به هيچ آبجکت اي برخورد ميکنه يا نه و اگه به چند تا آبجکت ميخوره کدوم نزديک تره. بعد از اين بايد (ماکسيمم) 99،999 بار چک کنيم که آيا shadow ray (illumination ray) ما به هيچ آبجکت اي برخورد ميکنه در مسيرش به سمت نور يا نه. در ضمن، اگر آبجکت ما reflective و يا refractive باشه که ديگه بد تر.

حالا اينو بزاريد کنار اين که در ثانيه اگر خيلی هنر کنيم ميتونيم تا 10 ميليون ray-object intersection رو چک کنيم (که خيلی سخته). در ضمن اين رو هم در نظر بگيريد که مقادير بالا برای 1 پيکسل بود. حالا 1 ميليون پيکسل رو در نظر بگيريد!

خوب، برای بهتر کردن performance چی کار بايد کرد؟ راه های مختلفی برای اين کار هست که اينجا چند تا از اونها رو در موردش بحث ميکنيم:



1-bounding volumes:
اينا چی هستند؟ bounding volumes ميتونن box, sphere, torus, cylinder يا هست primitive object ديگه اي باشند. ولی عموما box هستند و شما هم احتملاً با نام bounding box آشنا هستيد.

حال، کار اين bounding volumes چی هست؟ اگر بتونيد صحنه رو به قسمت های مختلف تقسيم کنيد و هر قسمت رو در يک bounding volume بگزاريد، در موقع رندر شما در ابتدا bounding volumes را با ray چک ميکنيد. اگر bounding volume به ray اصابت نکرد (در اصل بر عکس اين)، ديگه لازم نيست که object های درون اين volume را با ray چک کنيم! اين کار خيلی راحت هست و خيلی هم کمک ميکنه (و خيلی سريع هستش).

حالا يک توضيح کوچيک که چرا box رو انتخاب ميکنن به عنوان bounding volume of choice:
1) به راحتی ميتونيم اکثر آبجکت ها رو درون يک box جا بديم
2) پيدا کردن اينکه چه box اي ميتونه آبجکت رو درون خود قرار بده اسونه (کافيه minimum و maximum مختصات آبجکت رو بدست بياريم!
3) الگوريتم های بسيار optimize شده اي برای ray-box intersection calculation وجود داره.



2- Hierarchichal Bounding Boxes (HBB)
در اين روش، ما يک حالت graph از box ها ايجاد ميکنيم. به اين صورت که صحنه رو در ابتدا به چند قسمت نسبتا بزرگ تقسيم کرده و تعداد کمی BB ميسازيم. بعد هر کدوم از اين box ها رو به box های کوچيک تر درون box مادر قرار ميديم. که يک حالت tree structure بوجود مياد.

اين کار به چه دردی ميخوره؟ فرض کنيد که صحنه رو اول به 100 box تقسيم کرديم. حال هر بار که يک ray رو خواستيم چک کنيم بايد اول با 100 box چک کنيم و ببينيم به کدوم ميخوره. در حالت دوم (HBB) در ابتدا ray رو فقط فرضا به 5 تا box چک ميکنيم. ميبينيم که به 1 box ميخوره. بعد درون اين box 5 تا box ديگه هست که بايد اونها رو چک کنيم. و در نتيجه وقت کمتری از دست ميديم... (10 box به جای 100 box اگر level درخت ما فرضا 2 باشه که اصولا بيشتره.) در ضمن، اين جوری توی box های کوچک (level آخر) تعداد کمتری آبجکت هست که چک بشه.



3-BSP - Binary Space Partitioning
اين روش معمول ترين و بهينه ساز ترين روش برای مديريت صحنه هست. اکثرا در اين روش از روش قبلی هم سود ميبرند. در اين روش ابتدا صحنه رو به 2 قسمت تفسيم ميکنيم (چپ و راست). سپس از سمت چپ شروع کرده و اون رو به 2 قسمت تقسيم ميکنيم. (تصميم ميگيريم که کدام آبجکت ها در کدام قسمت قرار ميگيرند. چپ، راست، بالا، پايين، عقب، جلو) و همينطور پيش ميريم. اين کار تا اونجا پيش ميره که يا تعداد آبجکت ها در يک قسمت از يک حد (مثلا 1000) کمتر باشه يا از max depth گذشته باشيم. توضيح اين که اين الگوريتم چجوری کار ميکنه بيشتر از اين سخت هست. سعی کنيد که دقيقا اين رو در مختصات 2 بعدی مجسم کنيد و بعد اون رو به 3 بعد تعمم بدين. (نميدونم همين لغت هست يا نه).

وقتی هم که خواستيم که ray رو چک کنيم از بالای درخت شروع کرده و ابتدا فرضا (مدل 2 بعدی) با چپ و راست چک ميکنيم.
=> به چپ خورد
=؟ با بالا و پايين چک کن
=>به پايين خورد
=؟ با چاپ و راست (که در مربع پايين-چپ هستند) چک کن
=> به راست خورد
=؟ ادامه تا وقتی که به آخرين level يا در اصل leaf در tree رسيديم که مثلا فقط 1000 poly بود (به جای 100.000 poly حالت اول) و شايد تا به اين 1000 poly برسيم فقط 20 تا box رو چک کرديم. که ميشه:
20 ray-box intersection و 1000 ray-triangle intersection

اگر درست متوجه نشديد در يک post ديگه سعی ميکنم بهتر توضيح بدم.



4-Grid
مثل BSP هستش ولی ساده تر. از همون ابتدای کار شما صحنه رو مثلا به 100 قسمت (10 در 10) تقسيم ميکنيد و ميبينيد که در هر کدام از اين قسمت ها چه آبجکت هايی هستند. در اصل يک تلفيق از HBB و BSP هستش. اين تکنيک بهتر هست وقتی که صحنه خيلی همگون هست استفاده بشه.


5- KD-Tree
يک نمونه پيشرفته تر از BSP, در اين تکنيک شما صفحه جدا شونده رو (splitting plane) بنا به مشخصات صحنه قرار ميديد (ديگه نصف نميکنيم هر قسمت رو بلکه قسمت ها ميتونن کاملا متفاوت باشند).



نکته: در اين جا منظور از آبجکت در اصل triangle ها و polygon ها بود نه آبجکت مثل ميز و صندلی.

نکته 2: با وجود اينکه من ray tracing رو مثال زدم اين تکنيک ها در بازی ها هم به شدت کار برد داره. در يک post ديگه ميگم که چرا بازی ها به اين تکنيک ها احتياج دارند (الان دستم درد گرفت )

اميدوارم که به دردتون خورده باشه اين توضيحات خلاصه.
تا بعد.