بخشی از مقاله
چکیده
ردیابی اشعه درصحنههای مجازی راهحل بسیار زیبا و انعطافپذیر برای مسئلهی رندر کردن تصاویر گرافیکی و پزشکی باکیفیت بالا میباشد. برای این منظور اشعه از نقطه چشمی از طریق پیکسلهای یک سطح تصویر منتشر میشوند و با هندسه صحنه قطعشده و از هم میگذرند.کوتاهترین فاصله از تصویر تا یک تقاطع، قابلیت رؤیت صحنه از طریق آن پیکسل را نشان میدهد. روشنی آن پیکسل، تقریبی از پرتو ساطعشده از تقاطعهای یافته شده از طریق آن پیکسل به سمت نقطه چشمی است. یکی از مشکلات عمده این روش محاسبات بالای آن برای پیگیری پرتوها میباشد، از دلایل پیشرفت کارایی ردیابی اشعه استفاده از ساختارهای تسریع بهینهشده برای افزایش سرعت رندر تصاویراست اما زمان ساخت برای صحنههای پیچیده و بزرگ بالاست. در این مقاله روشی پیشنهادشده که بر روی رندر سریع صفحه دید مبتنی بر میانگینگیری نزدیکترین همسایهها یا پیکسلهای همسایهی رندر شده برای یافتن پیکسلهای رندر نشده با روش پیگیری اشعه، که برای صحنههای پیچیده و بزرگ بازمانیتقریباً به نصف کاهش دادهشده و کیفیت عالی به دست میآید.
کلمات کلیدی: ردیابی اشعه ، رندر، میانگینگیری ، صفحه دید
.1 مقدمه
از زمان توسعه ردیابی اشعه، محققین در جستجوی شتاب بخشیدن به ردیابی اشعه با تقریبها و با مخلوط کردن آن با دیگر تکنولوژیها بودهاند. برای کاربردهای زیادی، بازخورد تصویری سریع در مدت محاوره مهمتر از صحت تصویر است. همچنین ردیابی اشعه بهطور مفهومی تکنیک ارائه آسان است که با موفقیت بسیار در کاربردهای ارائهی غیر زمان بلادرنگ استفاده میشود. برای اینکه بتوانیم صحنههای پیچیده را بهصورت منطقی در سنجش فریمهای تعاملی ارائه دهیم، لازم است که ارزش زمان اجرای ردیابی اشعهها را کاهش دهیم. یک رویکرد معمول برای کاهش ارزش زمان اجرا که با ردیابی اشعه مرتبطمیباشد این است که از برخی از انواع ساختار شتابدهنده استفاده شود، مشابه با صف اطلاعات طبقهبندیشده که استفاده از الگوریتم جستجو را با رفتارهای مجانبی تابع خطی ممکن میسازد، ساختارهای شتابدهنده میتواند زمان اجرای مجانبی ردیابی یک اشعه را از O - n - به O - logn - کاهش دهند.
با استفاده از ساختارهای اشعه و رندر صفحه دید باید یک دادوستد میان زمانهای ساخت و دستاوردهای ممکن در اجرای ردیابی اشعه ایجاد شود.هدف الگوریتمهای رندرسازی کمینهسازی زمان ردیابی اشعه در ارائه تصویر است. هنگامیکه صحنههای ایستا ارائه میشوند، بهطورمعمول ساخت یکبار قبل از سنتزتصویر اجرا میشود. بنابراین زمانهای هر فریم فقط با این مسئله تأثیر میپذیرند که ساختار شتاب چقدر خوب، تعداد تستهای تقاطع اشعه مثلث را کاهش میدهند اما وقتیکه با هندسه پویا سروکار داریم، موقعیت مشکلتر میشود. اشکال هندسی اولیه که حرکت میکنند و یا تغییر شکل میدهند، ساختارها شتاب را نامعتبر میکنند، که باید بهروز شوند تا تنظیمات صفحه جدید را منعکس کنند.
در اکثر کاربردها این مورد باید در هر فریم اجرا شود. به خاطر هزینه محاسباتی ذاتاً بالای ردیابی اشعه تا مدتهای زیادی آن را برای رندر بلادرنگ مدنظر قرار نمیدادند. بههرحال، با افزایش قدرت محاسباتی CPUهای امروزی و استفاده از GPU، ردیابی اشعه محاورهای و حتی پرتوهای کلی محاورهای واقعیتی عملی شدهاند و نسبت به rasterization سنتی بر اساس الگوریتمها مزایایی به دست آوردند، البته محاسبه نقاط تقاطع اشعه هندسه بسیار پرهزینه است چوننسبتاً همیشه اتفاق میافتد. تعداد تقاطعهایی که باید محاسبه شود به شفافیت فضایی ساختار جستجو بستگی دارد، هر چه شفافیت بیشتر باشد درخت جستجو عمیقتر خواهد بود.
بهعبارتدیگر همیشه بین تعداد عملیات انتقالی و تعداد محاسبات تقاطع یک موازنه وجود دارد که میتوان آن را با تنظیم کردن حداکثر تعداد نمونههای نخستین هندسی در یک عنصر حجمی از یک ساختار تسریع صحنه کنترل کرد. ساختارهای تسریع فضایی بیشترین تأثیر را بر عملکرد رندر دارند، زیرا آنها مجموعه بالقوه قابلرؤیت برای یک اشعه معین را بهطور مستقل از اندازه صحنه، به یک تعداد بسیار کوچکی از نمونههای نخستین محدود میکند. یک ساختار خاصِ شاخص سازی، یک درخت از وکسلها یا حجمهای محدودکننده است، هر عنصر حجمی در این درخت میتواند شامل تعدادی عنصر فرعی - کهمعمولاً آنها را فرزندان میخوانند - و فهرستی از نمونههای نخستین هندسی و اطلاعات سایه سازی آنها باشد. قطع کردن یک اشعه با صحنه به معنای گذشتن از ساختار تسریع از طریق قطع کردن اشعه با فرزندان یک حجم محدودکننده بهطور مکرراست تا وقتیکه اشعه به یک نمونه نخستین مبهم یا یک برگ خالی از آن درخت برخورد کند.
.2 کارهای مرتبط
کارهای که در این زمینه و بر روی ساختارهای تسریعکننده رندر صورت گرفته ساخت درخت-Kd و بررسی جدید ساختمان الگوریتم بهوسیله Waldو Havran بوده است.[1] درخت-Kd یک ساختار دادهای تقسیمکننده فضا برای سازماندهی اشیاء در یک فضای -kبُعدی است. اینیک حالت ویژه درخت BSP - درخت تقسیم فضایی دوتایی - است. یک درخت - kd تنها از صفحههای دونیم کننده استفاده میکند که بر یکی از محورهای سیستم همپایه عمود هستند. این با درختهای BSP که در آنها میتوان از صفحههای دونیم کننده تصادفی استفاده کرد فرق میکند. ساخت یک درخت-kd ساکن متشکل ازn نقطه، O - nlogn - وقت و جستجوی محدود O - logn - وقت میگیرد که در اینجا n تعداد سلولها در درخت- kd است. همراه با روش مکاشفهای هوشمندانه برای تقسیم فرعی، درختهای-kd بهطور موفقیتآمیزی برای ردیابی اشعه بلادرنگ استفادهشدهاند.
هاروان و دوستان [ 2] مسئله سریع ساختن از ساختارهای سلسلهمراتبی متفاوت بخصوص درخت-Kd را بررسی کردهاند. آنها همچنین یک روش مکاشفهای ناحیه سطحی مبتنی بر ساختارهای تسریع ترکیبی را پیشنهاد دادهاند که سریعاً بهوسیله تشخیص کل محیط سهبعدی ساخته میشود.به خاطر صفحههای دونیم کننده آنکه همراستا با محورند، جستجوی محدوده برای یک اشعه مشخص را میتوان خیلی آسان و خیلی سریع انجام داد. ازآنجاییکه همه نرمالهای صفحهی تقسیم فرعی بر یکی از محورهای همپایه منطبق هستند، محصولات اسکالر و آزمونهای تقاطع عنصر حجمی ازنظر تعداد کافی و مؤثر هستند.علاوه بر آن، بلادرنگ پراکندن اشعه به یک درخت- kd در یک رندر کننده بلادرنگ را میتوان تا اندازه زیادی با ساخت درخت دقیق بهبود بخشید. این ساخت بر اساس یک الگوریتم حریصانه با یک تابع هزینه به نام روش مکاشفهای ناحیه سطحی - SAH - است .
روش مکاشفهای ناحیه سطحی مبتنی بر مدلهای احتمالی است وعموماً برای ساخت ساختارهای تسریع بکار برده میشود . این روش در3]،[10 برای استفاده در ساخت kd-tree مبتنی بر کارگلداسمیت و Wodniok معرفیشده است، قبلاً برای ساخت حجم محدود سلسلهمراتبی از مدل مشابهی استفادهشده است.[4]الگوریتم ساخت بالا به پایین درخت با پیچیدگی زمان اجرای O - nlogn - در [5 ] پیشنهادشده است. این روش از لیست ذخیرهشده از صفحات برش کاندید که در شروع و پایان هر نمونه نخستین مبتنی بر محور مختصات هستند استفاده میکند.با استفاده از یک صفحه برش فضای یک رأس به دو زیر فضا تقسیم میشود که این صفحه با روش مبتنی بر SAH بهدستآمده است، این صفحه برش کمترین هزینه را میان تمام صفحات برش کاندید دارد.
تمام صفحات برش کاندید در دو طرف نمونه نخستینهای موجود در رأس جاری میباشد، اگر نمونه نخستین عمود بر محور باشد آنگاه یک صفحه برش کاندید دارد که از آن نمونه نخستین میگذرد، صفحات برش در دو طرف نمونه نخستین بهعنوان صفحات کاندید انتخاب میشود چون صفحاتی که در بین این دو صفحه قرار میگیرند مقدار تابع هزینه را بهصورت محسوس کاهش نمیدهد. درنهایت صفحهای با کمترین هزینه انتخاب میشود و رأس موردنظر به دو رأس تبدیل میشود و لیست رخدادها به دو لیست تبدیل میشود. برای تصمیمگیری اینکه چه وقتی تقسیمات به روش بازگشتی متوقف شود از معیار خاتمه مبتنی بر روش مکاشفهای ناحیه سطحی استفاده میشود.
روش مکاشفهای ناحیه سطحی سعی میکند بهترین صفحه برش را بهوسیله مینیمم کردن تابع هزینه پیدا کند. تابع هزینه، هزینههای پیمایش ساختار و هزینه برخورد نور را در نظر میگیرد. این تعریف که ساختار را میسازد بهصورت بازگشتی کار میکند. در برگهای درخت نمونه نخستینها قرار دارند که باید برای تداخل نور مورد آزمایش قرار گیرند. هزینههای بررسی تداخل در هر برگ متناسب با تعداد نمونه نخستینها در برگ میباشد. فرمول زیر هزینه تداخل در برگی با N رأس برای پیدا کردن نزدیکترین برخورد در آن برگ را نشان میدهد.که در آن Cintersection هزینه تداخل نور با نمونه نخستین یک است. برای رأسهای درونی هزینه احتمالی پیمایش باید بررسی شود.Ctraversal یک فاکتور ثابت است که هزینه پیمایش را نشان میدهد.
این هزینه در تعین هزینه برخورد نور با رأس محاسبه میشود. تابع هزینه برای رأسهای درونی توسط فرمول زیر با دو رأس فرزند چپ و راست که تعداد نمونه نخستینها موجود در هرکدام از دو فرزند به ترتیبNl وNr است محاسبه میشود.Pl و Pr احتمالات هندسی زیر فضای سمت چپ و زیر فضای سمت راست میباشند: با فرض اینکه اشعهها بهصورت یکنواخت در فضا پراکندهشده باشند، احتمال اینکه یک اشعه از یک زیر فضا عبور کند با شرط اینکه از فضای پدرش عبور کرده باشد برابر است با مساحت سطح - - SA از جعبه محدوده آن رأس بر SA رأس ریشه. با تعویض رأس پدر با رأس ریشه احتمال پیمایش بهصورت رابطهای با پدر به دست میآید و میتواند در حالت بازگشتی تابع هزینه مورداستفاده قرار گیرد. تعریف کاملی از تابع هزینه در زیر آمده است:
