دانلود مقاله ترجمه شده الگوریتم های پیمایش و معماری سخت افزاری کارآمد ،برای نگاشت تغییر مکان معکوس هرمی

در این مقاله، الگوریتمی کارآمد به منظور پیمایش، و همچنین یک معماری سخت افزاری به منظور تشریح نگاشت تغییر مکان معکوس ارائه شده است. این معماری، شامل مجموعه ای از تکنیک هایی است که برای کاهش تعداد مراحل تکراری در طول نگاشت تغییر مکان معکوس کاربرد دارد. به منظور دستیابی به این هدف، دو الگوریتم به منظور کاهش تعداد مراحل، و همچنین دو الگوریتم به منظور بهبود پروسه ی افزایش سطح ارائه  شده است. تمامی این تکنیک ها با هم ترکیب شده اند؛ در مقایسه با سایر الگوریتم های موجود در زمینه ی نگاشت تغییر مکان معکوس، ما یک کاهش 66 درصدی را در تعداد مراحل تکراری با استفاده از این الگوریتم مشاهده کردیم. همچنین یک معماری سخت افزاری نگاشت تغییر مکان را که مبتنی بر تکنیک های جدیدی می­باشد، ارائه داده ایم. نتایج آزمایشی بدست آمده از ارزیابی ASCI و FPGA نشان داده است که معماری ما، مزایای زیادی را بر حسب ناحیه ی تراشه، مصرف انرژی و دسترسی به حافظه ی بیرون از تراشه برای GPU های سیال به همراه داشته است.

واژگان کلیدی: پردازنده های گرافیکی، معماری سخت افزاری، نگاشت تغییرمکان، هرم تصویر

نگاشت تغییر مکان، یکی از تکنیک های گرافیک کامپیوتری بوده که در مقیاس زیادی مورد استفاده قرار گرفته و تأثیر حرکت واقعی نقاط هندسی را بر اساس یک فیلد ارتفاع (Height Filed) داده شده نشان داده است. GPU  های مدرن، از تکنیک نگاشت تغییر مکان پشتیبانی می­کنند[1-3] . این تکنیک در مقیاس زیادی برای حمل عمق با جزئیات کامل مورد استفاده قرار گرفته است. از آنجایی که نگاشت تغییر مکان  با علوم هندسه ی زیادی سرو کار داشته و سربار محاسباتی بالایی را نیز تحمیل می­کند، آنرا نسبت به سایر تکنیک های نگاشت، گرانتر می­دانند.

الگوریتم نگاشت تغییرمکان معکوس[4]، مانند نگاشت انطباق[5]، نگاشت انسداد انطباق[6,7]، نگاشت برجسته[8,9] و نگاشت تغییر مکان هرمی[10,12] نیز برای بهبود کارائی نگاشت تغییر مکان پیشنهاد شده اند. این روش ها می­توانند نقطه ی قطع کننده ی بین یک شعاع و فیلد ارتفاع را به وسیله ی قرار دادن شعاع بر روی فیلد ارتفاع و بدون تغییر هندسه را تعیین کنند. علاوه بر این، نگاشت تغییر مکان معکوس در مقیاس زیادی در پیاده سازی های GPU و CPU مورد استفاده قرار گرفته است[13].

جدیدترین متد های نگاشت تغییر مکان معکوس را می­توان در دو کلاس دسته بندی کرد[12,13]: الگوریتم های تخمین(غیرایمن) و صحیح(ایمن). الگوریتم های تخمین، مانند نگاشت انسداد انطباق و نگاشت برجسته، سریع بوده ولی میزان صحت پایینی دارند: هیچ تضمینی وجود ندارد که این الگوریتم ها برخورد صحیحی را پیدا کنند. یک الگوریتم صحیح تری  در [10-12,14,15] پیشنهاد شده است، که  یک تکنیک پیگیری به ازای هر پیکسل  با یک هرم تصویر می­باشد. نگاشت تغییرمکان هرمی، شامل سطوحی از زیر پنداره ها می­باشد. با نزول تدریجی از سطح ریشه به سطح برگ در این نگاشت، نقطه ی برخورد صحیح بین یک شعاع و فیلد ارتفاع را می­توان محاسبه کرد. در [10]، ملاقات یک گره ی یک سطح پایین تر یا ملاقات یک گره ی همسایه با استفاده از قطع گره در طول پیمایش یک هرم تصویر روی می­دهد. Tevs[12] و Drobot[15]، تکنیک های نزولی را پیشنهاد دادند که از فضاهای خالی به صورت کارآمد عبور می­کند، که این باعث کاهش تعداد مراحل تکرار برای پیمایش در زوایای چرخش در مقایسه با [10] می­شود. Dick[16]  نیز از تکنیک Mipmap  هرمی برای انتشار شعاع GPU به منظور رِندر یک ناحیه استفاده کرد....