رندر پیشرفته، رهگیری پرتو، معادلهٔ رندرینگ، رادیوسیتی و رندر موازی
فصل ۱۱ — رندر پیشرفته
در این فصل پایانی، مجموعهای از رویکردهای جایگزین برای راهبرد استاندارد رندر خط لولهای را بررسی میکنیم که تاکنون برای کاربردهای تعاملی بهکار بردهایم. چند انگیزه برای معرفی این رویکردها داریم. میخواهیم بتوانیم اثرهایی مانند global illumination (نورپردازی سراسری) را وارد تصویر کنیم که معمولاً رندر بلادرنگ آنها ممکن نیست. همچنین میخواهیم تصاویر بسیار باکیفیتی تولید کنیم که تفکیکپذیری آنها فراتر از نمایشگرهای رایانهای استاندارد باشد. برای نمونه، یک فریم واحد از یک فیلم دیجیتال ممکن است بیش از ۱۰ میلیون پیکسل داشته باشد و رندر آن چند ساعت طول بکشد.
۱۱.۱ فراتررفتن از رندر خط لولهای
تقریباً همهٔ کارهایی که تا اینجا انجام دادهایم این تصور را تقویت کردهاند که اگر توصیفی از صحنه شامل اشیای هندسی، دوربینها، منابع نور و ویژگیها داشته باشیم، میتوانیم با سختافزار و نرمافزار موجود صحنه را تقریباً بلادرنگ رندر کنیم. این دیدگاه ما را به استفاده از رندرکنندهای خط لولهای از نوع معماری OpenGL و سختافزارهای گرافیکی سوق داد.
اگرچه مجموعهٔ نسبتاً بزرگی از تکنیکها ساختهایم که بیشتر کاربردها را پوشش میدهند و بسیاری از پیامدهای استفاده از مدل نورپردازی محلی این رندرکنندهها را دور میزنند، هنوز محدودیتهایی وجود دارد. برای مثال بسیاری از وضعیتهای نورپردازی سراسری را نمیتوان با رندرکنندهٔ خط لولهای بهخوبی تقریب زد. همچنین مایلیم تصاویری با تفکیک بالاتر از یک ایستگاه کاری استاندارد و با آرتیفکتهای aliasing کمتر تولید کنیم. در بسیاری از کاربردها حاضر هستیم برای این اهداف با سرعت کمتر رندر کنیم یا چند رایانه را همزمان بهکار بگیریم. این فصل مجموعهای از تکنیکها را معرفی میکند که هم برای پژوهشگران و هم برای متخصصان عملی اهمیت روز دارند.
ابتدا راهبردهای دیگری برای رندر را بررسی میکنیم که بر فیزیک تشکیل تصویر استوارند. بحث اولیهٔ ما دربارهٔ تشکیل تصویر بر دنبالکردن پرتوهای نور بنا شده بود. همان مدل فیزیکی ساده به پارادایم ray tracing (رهگیری پرتو) برای رندر منجر شد. این مدل را با جزئیات بیشتری از فصلهای قبل بررسی میکنیم و نشان میدهیم چگونه میتوان نوشتن یک ray tracer را آغاز کرد.
همچنین رویکردهای فیزیکی دیگری غیر از ray tracing وجود دارند. یکی از آنها بر پایستگی انرژی و یک معادلهٔ انتگرالی ــ معادلهٔ رندرینگ ــ استوار است که محیطی بسته با منابع نور و سطحهای بازتابنده را توصیف میکند.
اگرچه معادلهٔ رندرینگ در حالت کلی حلپذیر نیست، میتوان رویکردی به نام radiosity (رادیوسیتی) ساخت که وقتی همهٔ سطحها بازتابندههای کاملاً پخشکننده باشند، این معادله را ارضا کند.
دو رویکرد دیگر را نیز میبینیم که میان رندرکنندههای کاملاً فیزیکی و رندرکنندههای بلادرنگ قرار میگیرند. یکی رویکرد RenderMan است. دیگری رندر را از خود تصویرها آغاز میکند. با وجود تفاوت زیاد، هر دو روش در صنعت پویانمایی مهم شدهاند.
سپس به مسئلهٔ مجموعهدادههای بزرگ و نمایشگرهای با تفکیک بالا میپردازیم. این دو مسئله به هم مرتبطاند، زیرا مجموعهدادههای بزرگ جزئیاتی دارند که برای نمایش آنها به تفکیکپذیری فراتر از دستگاههای عمومی مانند پنل LCD نیاز است. راهحلهایی را بررسی میکنیم که با بهرهگیری از مؤلفههای عمومی، هم پردازندهها و هم کارتهای گرافیکی، از پردازش موازی استفاده میکنند.
در پایان image-based rendering (رندر مبتنی بر تصویر) را معرفی میکنیم؛ روشی که از چند تصویر دوبعدی یک صحنهٔ سهبعدی آغاز میکند و میکوشد از آنها تصویری از یک دیدگاه دیگر بسازد.
۱۱.۲ Ray Tracing (رهگیری پرتو)
از بسیاری جهات، ray tracing گسترشی منطقی برای رندر با مدل نورپردازی محلی است. مبنا همان مشاهدهٔ قبلی ماست: از میان پرتوهای نوری که یک منبع منتشر میکند، فقط پرتوهایی در تصویر سهم دارند که وارد عدسی دوربین مصنوعی میشوند و از مرکز تصویرسازی عبور میکنند.
شکل ۱۱.۱ چند تعامل ممکن میان یک منبع نقطهای و سطحهای کاملاً آینهای را نشان میدهد. پرتوها ممکن است مستقیماً از منبع وارد عدسی دوربین شوند، پس از برخورد با سطحی که دوربین میبیند به دوربین برسند، پس از چند بازتاب از سطحها وارد دوربین شوند، یا پس از عبور از یک یا چند سطح به دوربین برسند.
شکل ۱۱.۱ — پرتوهای خارجشده از منبع.
شکل ۱۱.۲ — مدل Ray Casting (پرتوافکنی).
بیشتر پرتوهایی که از منبع خارج میشوند وارد عدسی نمیشوند و در تصویر سهمی ندارند. پس دنبالکردن همهٔ پرتوها از یک منبع نور اتلاف زمان است. اگر جهت پرتوها را معکوس کنیم و فقط پرتوهایی را در نظر بگیریم که از مرکز تصویرسازی آغاز میشوند، میدانیم این پرتوهای افکندهشده باید در تصویر سهم داشته باشند. بنابراین ray tracer را مانند شکل ۱۱.۲ آغاز میکنیم.
در شکل، صفحهٔ تصویر را نیز قرار داده و آن را به نواحی هماندازهٔ پیکسل تقسیم کردهایم. چون باید به هر پیکسل یک رنگ اختصاص دهیم، لازم است دستکم یک پرتو از هر پیکسل عبور دهیم. هر پرتو افکندهشده یا با یک سطح یا منبع نور برخورد میکند، یا بدون برخورد به چیزی تا بینهایت ادامه مییابد. پیکسلهای حالت آخر را میتوان با رنگ پسزمینه پر کرد.
پرتوهایی که به سطح برخورد میکنند ــ فعلاً فرض میکنیم همهٔ سطحها کدرند ــ نیازمند محاسبهٔ سایهروشن در نقطهٔ تقاطع هستند. اگر فقط با مدل Phong اصلاحشده مقدار shade را در نقطهٔ برخورد محاسبه کنیم، همان تصویری را میسازیم که رندرکنندهٔ محلی تولید میکند. اما ray tracing امکانهای بیشتری دارد.
فرایندی که تا اینجا توصیف شد همان گامهای رندرکنندهٔ خط لولهای را نیاز دارد: مدلسازی شیء، تصویرسازی و تعیین سطح مرئی. تفاوت در ترتیب انجام محاسبات است. همانطور که در فصل ۶ دیدیم، رندرکنندهٔ خط لولهای رأسبهرأس کار میکند؛ ray tracer پیکسلبهپیکسل.
در ray tracing، بهجای آنکه بلافاصله مدل بازتاب را اعمال کنیم، ابتدا بررسی میکنیم نقطهٔ تقاطع پرتو و سطح واقعاً روشن است یا خیر. از نقطهٔ سطح به سوی هر منبع، shadow ray یا پرتو آزمون سایه میفرستیم. اگر shadow ray پیش از رسیدن به منبع با سطح دیگری برخورد کند، نور آن منبع به نقطهٔ موردنظر نمیرسد و نقطه ــ دستکم نسبت به آن منبع ــ در سایه است. برای منابعی که از دید نقطه مسدودند هیچ محاسبهٔ نورپردازی لازم نیست.
اگر همهٔ سطحها کدر باشند و پراکندگی نور از سطحی به سطح دیگر را در نظر نگیریم، نتیجه همان تصویر قبلی است با سایههای واقعی افزودهشده.
شکل ۱۱.۳ — پرتوهای سایه.
هزینهٔ این قابلیت آن است که برای هر نقطهٔ تقاطع میان یک پرتو افکندهشده و سطح، نوعی محاسبهٔ سطح پنهان انجام میشود. شکل ۱۱.۳ shadow rayها را با خط پیوسته برای دو پرتو افکندهشده با خطچین نشان میدهد که به مکعب و کره برخورد میکنند. یکی از shadow rayهای مکعب با استوانه برخورد میکند؛ بنابراین نقطهٔ برخورد پرتو اصلی با مکعب فقط توسط یکی از دو منبع روشن میشود.
فرض کنید بعضی سطحها مانند شکل ۱۱.۴ بسیار بازتابنده و شبیه آینه باشند. میتوان پرتو را هنگام جهش از سطحی به سطح دیگر دنبال کرد تا یا به بینهایت برود یا به یک منبع برسد.
شکل ۱۱.۴ — رهگیری پرتو با یک آینه.
شکل فقط دو مسیر را نشان میدهد. پرتو سمت چپ با آینه برخورد میکند و shadow ray آن به منبع نور سمت چپ مسدود نیست؛ پس اگر آینه جلوی منبع دوم باشد، نقطهٔ برخورد فقط توسط یک منبع روشن میشود.
شکل ۱۱.۵ — رهگیری پرتو با بازتاب و عبور.
پرتوی افکندهشدهٔ سمت راست با کره برخورد میکند. در این حالت یک پرتو میتواند از آینه به منبع سمت چپ بازتاب شود و افزون بر آن، نقطهٔ برخورد مستقیماً توسط منبع سمت چپ روشن شود.
چنین محاسباتی معمولاً بهصورت بازگشتی انجام میشوند و جذب نور در سطحها نیز در آنها لحاظ میشود.
ray tracing بهویژه برای سطحهایی مناسب است که هم نور را بازتاب میدهند و هم با شکست از خود عبور میدهند. بر اساس پارادایم اصلی، یک پرتو افکندهشده را تا سطح دنبال میکنیم (شکل ۱۱.۵). اگر پرتویی از منبع به آن نقطه برسد، بخشی از نور در سطح جذب میشود و بخشی در جملهٔ بازتاب پخشی سهم میگذارد. باقی نور ورودی میان یک پرتو عبوری و یک پرتو بازتابی تقسیم میشود.
از دید پرتو افکندهشده، اگر منبع نور در نقطهٔ برخورد قابل مشاهده باشد، سه کار انجام میدهیم. نخست سهم منبع نور را در آن نقطه با مدل بازتاب استاندارد محاسبه میکنیم. دوم پرتویی در جهت بازتاب کامل میفرستیم. سوم پرتویی در جهت پرتو عبوری ارسال میکنیم. دو پرتو جدید دقیقاً مانند پرتو اصلی پردازش میشوند: ممکن است با سطحهای دیگر برخورد کنند، به منبع برسند یا به بینهایت بروند. در هر سطحی که برخورد رخ دهد، ممکن است بر اثر بازتاب و عبور، پرتوهای جدید دیگری ایجاد شوند.
شکل ۱۱.۶ — محیطهای سادهٔ ray tracing.
شکل ۱۱.۶ یک پرتو افکندهشده و مسیر احتمالی آن را در یک محیط ساده نشان میدهد. شکل ۱۱.۷ درخت پرتو متناظر را نشان میدهد. این درخت مشخص میکند کدام پرتوها باید رهگیری شوند و بهصورت پویا در طول فرایند ray tracing ساخته میشود.
شکل ۱۱.۷ — درخت پرتو متناظر با شکل ۱۱.۶.
اگرچه ray tracer ما برای واردکردن جملهٔ پخشی در محل برخورد پرتو با سطح از مدل Blinn-Phong استفاده میکند، نوری که در این نقطه بهصورت پخشی پراکنده میشود نادیده گرفته میشود. اگر بخواهیم چنین نوری را نیز دنبال کنیم، تعداد پرتوها آنقدر زیاد میشود که ممکن است ray tracer هرگز پایان نیابد. ازاینرو ray tracerها بیش از همه برای محیطهای بسیار بازتابنده مناسباند. لوح رنگی ۱۵ با یک ray tracer متنباز/عمومی رندر شده است؛ با وجود آنکه صحنه فقط چند شیء دارد، بازتابها و شکستها جلوهای بسیار غنی ایجاد میکنند.
با وجود آنکه صحنهٔ لوح رنگی ۱۵ فقط چند شیء دارد، سطحهای بازتابنده و شفاف بدون ray tracer نمیتوانستند واقعگرایانه رندر شوند. همچنین پیچیدگی سایههای صحنه را ببینید؛ این اثر نیز در ray tracing بهصورت طبیعی ایجاد میشود. تصویر نشان میدهد که ray tracer میتواند texture mapping را با دشواریای نه بیشتر از رندرکنندهٔ خط لولهای وارد محاسبه کند.
۱۱.۳ ساخت یک Ray Tracer ساده
سادهترین راه توصیف ray tracer، تعریف بازگشتی آن با یک تابع واحد است که یک پرتو را دنبال میکند و برای پرتوهای بازتابی و عبوری خودش را فراخوانی میکند. بخش عمدهٔ کار در ray tracing صرف محاسبهٔ تقاطع پرتوها با سطحها میشود. یکی از دلایل دشواری ساخت ray tracer برای اشیای متنوع این است که با پیچیدهترشدن اشیا، محاسبهٔ تقاطع نیز دشوار میشود. بنابراین بیشتر ray tracerهای پایه فقط سطحهای تخت و quadricها را پشتیبانی میکنند.
ملاحظات اصلی فرایند را دیدیم. ساخت یک ray tracer بازگشتی ساده که بتواند اشیای ساده، یعنی quadricها و چندوجهیها، را پردازش کند نسبتاً آسان است. در این بخش ساختار پایه و تابعهای لازم را بررسی میکنیم. جزئیات بیشتر در منابع پیشنهادی پایان فصل آمده است.
به دو تابع اصلی نیاز داریم. تابع بازگشتی raytrace پرتویی را که با یک نقطه و یک جهت مشخص شده دنبال میکند و رنگ نخستین سطحی را که پرتو با آن برخورد میکند برمیگرداند. این تابع از intersect برای یافتن نزدیکترین سطحی که پرتو مشخصشده با آن برخورد میکند استفاده میکند.
۱۱.۳.۱ رهگیری پرتو بازگشتی
رویهٔ trace را به صورت شبهکد در نظر بگیرید. نقطهٔ شروع p و جهت d را میدهیم و تابع رنگ c را برمیگرداند. برای آنکه ray tracer تا بینهایت بازگشت نکند، بیشینهٔ تعداد گامها را با max تعیین میکنیم. برای سادگی فرض میکنیم فقط یک منبع نور داریم و ویژگیهای آن، همراه با توصیف اشیا و ویژگیهای سطحی، بهصورت سراسری در دسترساند. در صورت وجود منابع بیشتر، سهم هرکدام به روشی مشابه منبع واحد افزوده میشود:
color c = trace(point p, vector d, int step)
{
color local, reflected, transmitted;
point q;
normal n;
if (step > max) return(background_color);
q = intersect(p, d, status);
if (status == light_source) return(light_source_color);
if (status == no_intersection) return(background_color);
n = normal(q);
r = reflect(q, n);
t = transmit(q, n);
local = phong(q, n, r);
reflected = trace(q, r, step+1);
transmitted = trace(q, t, step+1);
return(local + reflected + transmitted);
}
محاسبهٔ رنگهای بازتابی و عبوری باید مقدار انرژی جذبشده در سطح را پیش از بازتاب و عبور در نظر بگیرد. اگر از بیشینهٔ تعداد گامها عبور کرده باشیم، رنگ پسزمینهٔ از پیش تعیینشده بازگردانده میشود. در غیر این صورت با intersect نزدیکترین شیئی را پیدا میکنیم که پرتو با آن برخورد دارد. این تابع باید به کل پایگاه دادهٔ اشیا دسترسی داشته باشد و بتواند تقاطع پرتو را با همهٔ انواع اشیای پشتیبانیشده پیدا کند. بنابراین بیشتر زمان اجرای ray tracer و بخش بزرگی از پیچیدگی کد در همین تابع پنهان است. برخی مسائل تقاطع را در بخش ۱۱.۳.۲ بررسی میکنیم.
اگر پرتو با هیچ شیئی برخورد نکند، intersect میتواند وضعیت مناسب را برگرداند و trace رنگ پسزمینه را برگرداند. اگر پرتو با منبع نور برخورد کند، رنگ منبع بازگردانده میشود. اگر برخوردی با سطح پیدا شود، رنگ نقطه سه مؤلفه دارد: رنگ محلی که با مدل Phong اصلاحشده یا هر مدل دیگر محاسبه میشود، رنگ بازتابی و ــ در صورت نیمهشفافبودن سطح ــ رنگ عبوری.
پیش از محاسبهٔ این رنگها، نرمال نقطهٔ تقاطع و جهت پرتوهای بازتابی و عبوری، همانند فصل ۵، محاسبه میشوند. پیچیدگی محاسبهٔ نرمال به نوع اشیای پشتیبانیشده بستگی دارد و این محاسبه میتواند بخشی از trace باشد.
برای محاسبهٔ رنگ محلی باید بررسی کنیم آیا منبع نور از نزدیکترین نقطهٔ تقاطع دیده میشود یا نه. از این نقطه به سوی منبع یک feeler/shadow ray میفرستیم و میآزماییم آیا با شیئی برخورد میکند. این فرایند نیز میتواند بازگشتی باشد، زیرا shadow ray ممکن است به سطحی بازتابنده مانند آینه یا سطحی نیمهشفاف مانند شیشه برخورد کند. همچنین اگر shadow ray به سطحی برخورد کند که خودش روشن است، بخشی از آن نور نیز باید در رنگ نقطهٔ (q) سهم داشته باشد. معمولاً این سهمها نادیده گرفته میشوند، چون محاسبه را بهطور چشمگیری کند میکنند. ray tracing عملی ناگزیر از مصالحه است و هرگز کاملاً فیزیکی نیست.
در ادامه دو گام بازگشتی با trace سهم پرتوهای بازتابی و عبوری را که از (q) آغاز میشوند محاسبه میکنند. همین بازگشتها کد را به یک ray tracer واقعی تبدیل میکنند، نه یک ray-caster ساده که فقط نخستین برخورد را پیدا میکند و در همان نقطه مدل نورپردازی را اعمال میکند.
در پایان سه رنگ را با هم جمع میکنیم تا رنگ نقطهٔ (p) بهدست آید.
۱۱.۳.۲ محاسبهٔ تقاطعها
بخش عمدهٔ زمان یک ray tracer معمولی در محاسبهٔ تقاطعهای تابع intersect صرف میشود. بنابراین باید اشیای صحنه را تا حد امکان به انواعی محدود کنیم که تقاطع آنها ساده محاسبه میشود.
مسئلهٔ عمومی تقاطع با نمایش ضمنی اشیا بهصورت بسیار تمیزی بیان میشود. اگر شیء با سطح یا سطحهای
f(x,y,z)=f(p)=0
تعریف شود و پرتویی از (p_0) در جهت (d) با فرم پارامتری
p(t)=p_0+td
نمایش داده شود، تقاطعها برای مقادیر (t)ای رخ میدهند که
f(p_0+td)=0
را ارضا کنند. این رابطه یک معادلهٔ اسکالر بر حسب (t) است. اگر (f) سطحی جبری باشد، مجموعی از جملههای چندجملهای (x^iy^jz^k) است و (f(p_0+td)) نیز چندجملهای بر حسب (t) خواهد بود. بنابراین یافتن تقاطعها به یافتن همهٔ ریشههای یک چندجملهای تقلیل مییابد. متأسفانه فقط چند حالت وجود دارد که به روش عددی نیاز ندارند.
یکی از این حالتها quadricها هستند. در فصل ۱۰ دیدیم که هر quadric را میتوان به صورت فرم درجهٔ دوم
p^TAp+b^Tp+c=0
نوشت. با جایگذاری معادلهٔ پرتو، یک معادلهٔ اسکالر درجهٔ دوم برای (t) باقی میماند که صفر، یک یا دو تقاطع تولید میکند. چون حل معادلهٔ درجهٔ دوم فقط یک جذر نیاز دارد، ray tracerها quadricها را بهسادگی پردازش میکنند. افزون بر آن، پیش از محاسبهٔ جذر میتوان پرتوهایی را که quadric را از دست میدهند یا فقط مماس آن هستند تشخیص داد و محاسبه را سادهتر کرد.
برای مثال، کرهای با مرکز (p_c) و شعاع (r) را در نظر بگیرید:
(p-p_c)\cdot(p-p_c)-r^2=0.
با جایگذاری پرتو
p(t)=p_0+td
معادلهٔ درجهٔ دوم زیر حاصل میشود:
(d\cdot d)t^2+2(p_0-p_c)\cdot d\,t+(p_0-p_c)\cdot(p_0-p_c)-r^2=0.
صفحهها نیز سادهاند. معادلهٔ پرتو را در معادلهٔ صفحه
p\cdot n+c=0
جایگذاری میکنیم و یک معادلهٔ اسکالر بهدست میآوریم که فقط به یک تقسیم نیاز دارد. برای
p=p_0+td
داریم:
t=-\frac{p_0\cdot n+c}{n\cdot d}.
اما خود صفحههای نامتناهی در مدلسازی صحنه کاربرد محدودی دارند. معمولاً یا به تقاطع چند صفحه برای تشکیل اشیای محدب، یعنی چندوجهیها، نیاز داریم یا به بخشی از صفحه که یک چندضلعی تخت را تعریف میکند. برای چندضلعی باید تعیین کنیم نقطهٔ برخورد داخل یا خارج چندضلعی است. دشواری آزمون به محدببودن چندضلعی و، در صورت نامحدببودن، سادهبودن آن بستگی دارد. این مسائل مشابه مباحث رندر چندضلعی در فصل ۶ هستند. برای چندضلعیهای محدب آزمونهای بسیار سادهای وجود دارد که شبیه آزمون تقاطع پرتو با چندوجهی است.
اگرچه میتوان چندوجهی را با وجههایش تعریف کرد، میتوان آن را شیء محدبی نیز دانست که از تقاطع صفحهها ساخته شده است. بنابراین یک متوازیالسطوح با شش صفحه و یک چهاروجهی با چهار صفحه تعریف میشود. مزیت این تعریف برای ray tracing آن است که میتوان از معادلهٔ سادهٔ تقاطع پرتو و صفحه، آزمون تقاطع پرتو و چندوجهی را استخراج کرد.
فرض کنید نرمال همهٔ صفحههای تعریفکنندهٔ چندوجهی رو به بیرون باشد. پرتو شکل ۱۱.۸ را در نظر بگیرید که با چندوجهی برخورد میکند. این پرتو فقط یک بار وارد و یک بار خارج میشود. باید از صفحهای وارد شود که رو به پرتو است و از صفحهای خارج شود که در جهت پرتو قرار دارد. با این حال، پرتو با همهٔ صفحههای تشکیلدهندهٔ چندوجهی ــ بهجز صفحههای موازی با آن ــ تقاطع خواهد داشت.
تقاطع پرتو با همهٔ صفحههای رو به جلو را در نظر بگیرید، یعنی صفحههایی که نرمالشان به سوی نقطهٔ آغاز پرتو است. نقطهٔ ورود همان دورترین تقاطع در امتداد پرتو است. به همین ترتیب، نقطهٔ خروج نزدیکترین تقاطع با صفحههایی است که پشت به مبدأ پرتو هستند و نقطهٔ ورود باید از نقطهٔ خروج به مبدأ نزدیکتر باشد.
برای پرتویی که همان چندوجهی را از دست میدهد، مانند شکل ۱۱.۹، دورترین تقاطع با صفحهٔ رو به جلو از نزدیکترین تقاطع با صفحهٔ پشتبهپرتو دورتر است. پس آزمون ما این است که نقاط ورود و خروج ممکن را با محاسبهٔ تقاطع پرتو با صفحهها، به هر ترتیبی، پیدا و در حین کار بهروزرسانی کنیم. اگر هر زمان نقطهٔ خروج ممکن از نقطهٔ ورود فعلی نزدیکتر شود، یا نقطهٔ ورود ممکن از نقطهٔ خروج فعلی دورتر شود، میتوان آزمون را متوقف کرد.
شکل ۱۱.۸ — پرتویی که یک چندوجهی با نرمالهای رو به بیرون را قطع میکند.
شکل ۱۱.۹ — پرتویی که یک چندوجهی با نرمالهای رو به بیرون را از دست میدهد.
شکل ۱۱.۱۰ — تقاطع پرتو با یک چندضلعی محدب.
مثال دوبعدی شکل ۱۱.۱۰ آزمون تقاطع پرتو با چندضلعی محدب روی صفحه را نشان میدهد. در اینجا خطها جای صفحهها را گرفتهاند، اما منطق همان است. فرض کنید تقاطع با خطها به ترتیب ۱، ۲، ۳ و ۴ محاسبه شود. خط ۱ رو به نقطهٔ آغاز است؛ این موضوع از علامت ضرب داخلی نرمال خط با جهت پرتو مشخص میشود. تقاطع با خط ۱ یک نقطهٔ ورود ممکن میدهد. خط ۲ پشت به نقطهٔ آغاز است و یک نقطهٔ خروج ممکن میدهد که از برآورد فعلی ورود دورتر است. خط ۳ نقطهٔ خروج نزدیکتری تولید میکند، ولی هنوز از نقطهٔ ورود دورتر است. خط ۴ نقطهٔ خروج دورتری میدهد که میتوان نادیدهاش گرفت. پس از آزمون همهٔ خطها نتیجه میگیریم پرتو از چندضلعی عبور میکند.
شکل ۱۱.۱۱ — پرتویی که چندضلعی محدب را از دست میدهد.
در شکل ۱۱.۱۱ همان خطها و همان چندضلعی محدب وجود دارند، اما پرتو از چندضلعی عبور نمیکند. تقاطع با خط ۱ همچنان یک نقطهٔ ورود ممکن میدهد. خطهای ۲ و ۳ نقاط خروجی میدهند که از نقطهٔ ورود دورترند. اما تقاطع با خط ۴ نقطهٔ خروجی نزدیکتر از ورود به دست میدهد و همین نشان میدهد پرتو حتماً چندضلعی را از دست میدهد.
۱۱.۳.۳ گونههای مختلف Ray Tracing
بیشتر ray tracerها چند روش را همزمان برای تعیین زمان توقف فرایند بازگشتی بهکار میبرند. یک روش ساده آن است که همهٔ پرتوهایی را که از فاصلهٔ معینی فراتر میروند نادیده بگیریم و فرض کنیم به بینهایت میروند. این آزمون را میتوان با فرض اینکه همهٔ اشیا داخل یک کرهٔ بزرگ با مرکز مبدأ قرار دارند پیادهسازی کرد.
پس اگر این کرهٔ بزرگ را شیئی با رنگ پسزمینهٔ مشخص در نظر بگیریم، هرگاه محاسبهٔ تقاطع نشان دهد این کره نزدیکترین شیء است، بازگشت برای پرتو پایان مییابد و رنگ پسزمینه بازگردانده میشود.
راهبرد سادهٔ دیگر برای پایان، بررسی سهم انرژی باقیمانده در پرتو است. وقتی پرتو از مادهای نیمهشفاف عبور میکند یا از سطحی براق بازتاب میشود، میتوان تخمین زد چه کسری از انرژی ورودی در پرتوهای خروجی باقی مانده و چه مقدار در سطح جذب شده است. اگر پارامتر انرژی را به ray tracer اضافه کنیم:
trace(point p, vector d, int steps, float energy);
فقط یک خط کد برای آزمون کافیبودن انرژی باقیمانده جهت ادامهٔ رهگیری لازم است.
برای افزایش سرعت یا دقت ray tracer بهبودهای بسیاری ممکن است. برای نمونه جایگزینکردن بازگشت با تکرار نسبتاً ساده است. بخش زیادی از محاسبات تقاطع را میتوان با bounding box یا bounding sphere حذف کرد، چون تقاطع پرتو با این حجمهای مرزی بسیار سریع محاسبه میشود. حجمهای مرزی اغلب برای گروهبندی مؤثر اشیا نیز مناسباند؛ همانطور که در فصل ۸ درختهای BSP را معرفی کردیم.
چون ray tracing یک روش نمونهبرداری است، به خطاهای aliasing حساس است. در فصل ۷ دیدیم aliasing زمانی رخ میدهد که نمونهٔ کافی نداشته باشیم. اما در ray tracer پایه، مقدار کار تقریباً متناسب با تعداد پرتوهاست. بسیاری از ray tracerها از نمونهبرداری تصادفی استفاده میکنند؛ محل پرتو بعدی بر اساس نتایج پرتوهایی که تاکنون فرستاده شدهاند تعیین میشود. اگر پرتوها در ناحیهای با هیچ شیئی برخورد نکنند، پرتوهای اضافی کمتری به آن ناحیه فرستاده میشوند؛ برعکس، در جهتی که پرتوها با اشیای زیادی برخورد دارند نمونهبرداری متراکمتر میشود. همین راهبرد در RenderMan نیز بهکار میرود (بخش ۱۱.۶).
نمونهبرداری تصادفی فقط از نظر احتمالاتی تضمین میدهد و ممکن است اشیای کوچکی در نواحی کمنمونه از دست بروند؛ با این حال مزیت مهم آن این است که تصاویر حاصل معمولاً الگوهای moiré مشخصهٔ نمونهبرداری یکنواخت را نشان نمیدهند.
ray tracing ذاتاً موازی است، زیرا هر پرتو را میتوان مستقل از پرتوهای دیگر فرستاد. دشواری این است که هر پرتو بالقوه میتواند با هر شیئی برخورد کند، پس رهگیری هر پرتو باید به همهٔ اشیا دسترسی داشته باشد. افزون بر آن، وقتی پرتوهای بازتابی و عبوری را دنبال میکنیم، locality احتمالی که میتوانست از جابهجایی زیاد داده جلوگیری کند از بین میرود. بنابراین ray tracerهای موازی بیشتر برای معماریهای موازی با حافظهٔ مشترک مناسباند. با وجود پردازندههای چندهستهای و آدرسدهی ۶۴ بیتی، رایانههای عمومی امروز میتوانند حافظهٔ کافی برای کاربرد عملی ray tracing در بسیاری از برنامهها فراهم کنند.
۱۱.۴ معادلهٔ رندرینگ
بیشتر قوانین فیزیک را میتوان به صورت قوانین پایستگی، مانند پایستگی تکانه و انرژی، بیان کرد. چون نور شکلی از انرژی است، رویکرد مبتنی بر انرژی میتواند جایگزینی برای ray tracing باشد.
محیط بستهٔ شکل ۱۱.۱۲ را در نظر بگیرید. چند سطح محیط بسته را تعریف میکنند، چند شیء و یک منبع نور نیز درون آن قرار دارند. از نظر فیزیکی، همهٔ این سطحها ــ حتی سطح منبع نور ــ را میتوان به یک روش مدل کرد. هرکدام پارامترهای متفاوتی دارند، اما همگی از قوانین فیزیکی یکسان پیروی میکنند. هر سطح میتواند بخشی از نور را جذب و بخشی را بازتاب کند و هر سطح بالقوه میتواند گسیلکنندهٔ نور باشد.
شکل ۱۱.۱۲ — محیط بسته با چهار شیء و یک منبع نور.
از دید ray tracing میتوان گفت رنگهایی که میبینیم حاصل تعداد نامتناهی پرتویی هستند که در محیط جهش میکنند، از منبعها آغاز میشوند و تا زمانی که همهٔ انرژی جذب نشده ادامه مییابند. اما وقتی به صحنه نگاه میکنیم، حالت پایدار را میبینیم: هر سطح رنگ و روشنایی نهایی خود را دارد. مسیرهای جهش پرتوها را نمیبینیم، فقط نتیجهٔ نهایی را مشاهده میکنیم. رویکرد انرژی اجازه میدهد این حالت پایدار را مستقیماً حل کنیم و از رهگیری تعداد بسیار زیادی پرتو و بازتاب پرهیز شود.
سطح واحدی مانند شکل ۱۱.۱۳ را در نظر بگیرید. پرتوهای نور از جهتهای گوناگون وارد میشوند و پرتوهای دیگری نیز ممکن است در همهٔ جهتها خارج شوند. نور خروجی دو مؤلفه دارد. اگر سطح منبع نور باشد، بخشی از نور خروجی از گسیل خود سطح میآید. باقی نور، بازتاب نور ورودی از سطحهای دیگر است. پس نور ورودی نیز متشکل از گسیل و بازتاب سایر سطحهاست.
شکل ۱۱.۱۳ — یک سطح ساده.
تحلیل را با دو نقطهٔ دلخواه (p) و (p') مطابق شکل ۱۱.۱۴ ساده میکنیم. اگر نور ورودی و خروجی در (p) را بررسی کنیم، انرژی باید متعادل باشد. گسیل انرژی در صورت وجود منبع در (p)، بهعلاوهٔ انرژی نور بازتابی، باید با نور ورودی از همهٔ نقاط ممکن (p') سازگار باشد.
شکل ۱۱.۱۴ — نور خارجشده از (p') و رسیده به (p).
فرض کنید (i(p,p')) شدت نوری باشد که از (p') خارج میشود و به (p) میرسد.¹ معادلهٔ رندرینگ را به صورت مفهومی مینویسیم:
i(p,p')=\nu(p,p')\left(\epsilon(p,p')+\int \rho(p,p',p'')\,i(p',p'')\,dp''\right).
شدت خروجی از (p') دو بخش دارد. اگر (p') گسیلکنندهٔ نور باشد، جملهٔ (\epsilon(p,p')) در جهت (p) وجود دارد. جملهٔ دوم سهم بازتاب نور از همهٔ نقاط ممکن (p'') است که در (p') به سوی (p) بازتاب میشوند. تابع بازتاب (\rho(p,p',p'')) ویژگی ماده در (p') را مشخص میکند.
تابع (\nu(p,p')) دو حالت دارد. اگر میان (p) و (p') یک سطح کدر باشد، (p') از دید (p) پوشانده میشود و نوری از آن به (p) نمیرسد، پس (\nu(p,p')=0). در غیر این صورت باید اثر فاصله را نیز لحاظ کنیم:
\nu(p,p')=\frac1{r^2},
که (r) فاصلهٔ دو نقطه است.
پاورقی ۱. برای پرهیز از ورود به واحدها و اصطلاحات کامل radiometry، کتاب از «شدت نور» صحبت میکند. انرژی انتگرال شدت روی زمان است؛ اما وقتی منابع نور تغییر نمیکنند و در حالت پایدار هستیم، این تفاوت در بحث حاضر تعیینکننده نیست. بیشتر منابع از انرژی یا شدت بر واحد سطح، یعنی شار انرژی، استفاده میکنند.
با وجود فرم بسیار ساده و زیبای معادلهٔ رندرینگ، حل آن آسان نیست. مشکل اصلی تعداد ابعاد است. چون (p) و (p') نقاطی در فضای سهبعدیاند، (i(p,p')) شش متغیر و (\rho) نه متغیر دارد. افزون بر آن، متغیر طول موج نور را که برای کار با رنگ لازم است وارد نکردهایم.
تلاشهایی برای حل عددی فرم عمومی معادلهٔ رندرینگ انجام شده است. بیشتر این روشها Monte Carlo بودهاند و شباهتی به نمونهبرداری تصادفی دارند. در سالهای اخیر photon mapping (نگاشت فوتون) نیز به روشی عملی تبدیل شده است. photon mapping فوتونهای منفرد، یعنی حاملهای انرژی نور، را از زمان تولید در منابع تا جذب نهایی در سطحهای صحنه دنبال میکند. فوتونها معمولاً پیش از جذب نهایی چندین بازتاب و عبور را تجربه میکنند. مزیت بالقوه این روش آن است که میتواند نورپردازی پیچیدهٔ صحنههای دنیای واقعی را مدل کند.
پیشتر در بحث ray tracing گفتیم چون درصد بسیار کمی از نور منتشرشده از منابع به بیننده میرسد، دنبالکردن پرتو از منبع ناکارآمد است. photon mapping با راهبردهای هوشمندانهٔ بسیاری این فرایند را از نظر محاسباتی ممکن میکند. بهویژه، پایستگی انرژی با روشهای Monte Carlo ترکیب میشود.
برای مثال، وقتی نور به سطحی پخشی میرسد، نور بازتابی در همهٔ جهتها پخش میشود. در photon mapping وقتی فوتون با یک سطح پخشی برخورد میکند، ممکن است بازتاب یا جذب شود. اینکه فوتون جذب شود یا خیر و در صورت بازتاب، زاویهٔ آن چه باشد، بهصورت تصادفی اما با توزیعی تعیین میشود که میانگین نتایج فیزیکی صحیح باشد. در نتیجه رفتار دو فوتونی که دقیقاً در یک نقطه و با زاویهٔ برخورد یکسان به سطح میرسند میتواند کاملاً متفاوت باشد. هرچه تعداد فوتونهای تولیدشده از منابع بیشتر باشد، دقت نیز بیشتر میشود، اما هزینهٔ رهگیری بالا میرود.
شرایط خاصی وجود دارند که معادلهٔ رندرینگ را ساده میکنند. برای سطحهای کاملاً آینهای، تابع بازتاب فقط زمانی ناصفر است که زاویهٔ تابش با زاویهٔ بازتاب برابر باشد و بردارها در یک صفحه قرار گیرند. در این شرایط میتوان ray tracing را روشی برای حل معادلهٔ رندرینگ دانست.
حالت خاص دیگر زمانی است که همهٔ سطحها کاملاً پخشی باشند. در این حالت مقدار نور بازتابی در همهٔ جهتها یکسان است و تابع شدت فقط به (p) وابسته میشود. این حالت را در بخش بعد بررسی میکنیم.
۱۱.۵ Radiosity (رادیوسیتی)
یکی از راههای سادهسازی معادلهٔ رندرینگ، در نظرگرفتن محیطی است که همهٔ سطحهایش بازتابندهٔ کاملاً پخشیاند. چون سطح کاملاً پخشی برای همهٔ بینندگان یکسان دیده میشود، BRDF متناظر بسیار سادهتر از حالت عمومی معادلهٔ رندرینگ است.
با این حال توجه کنید که حتی اگر یک سطح پخشی کاملاً تخت باشد، میتواند تغییرات shade نشان دهد که هنگام رندر با مدل Phong اصلاحشده دیده نمیشوند.
شکل ۱۱.۱۵ — صحنهای ساده با سطحهای پخشی.
فرض کنید صحنهٔ سادهٔ شکل ۱۱.۱۵ را داریم و همهٔ سطحها کاملاً پخشیاند. اگر صحنه را با یک منبع نور دوردست رندر کنیم، هر سطح چندضلعی با یک رنگ ثابت رندر میشود. اما در یک صحنهٔ واقعی، بخشی از بازتاب پخشی دیوار قرمز روی دیوار سفید میافتد و به نور سفید بازتابی قسمتهای نزدیک دیوار سفید، مقداری نور قرمز اضافه میکند. نور پخشی بازتابشده از دیوار سفید نیز اثری متقابل روی دیوار قرمز دارد. مدل سادهٔ سایهزنی ما این تعاملهای پخشی-پخشی را در نظر نگرفته است.
یک رندرکنندهٔ سراسری ایدهآل باید این تعاملها را ثبت کند. روش radiosity میتواند آنها را با دقت خوبی و با رویکردی مبتنی بر انرژی تقریب بزند؛ رویکردی که در اصل برای حل مسائل انتقال حرارت توسعه یافته بود.
روش پایهٔ radiosity صحنه را به چندضلعیهای تخت کوچک یا patchها تقسیم میکند. هر patch را میتوان کاملاً پخشی فرض کرد و آن را با یک shade ثابت رندر کرد. ابتدا باید این shadeها را پیدا کنیم. پس از تعیین آنها، عملاً به هر patch رنگی مستقل از موقعیت بیننده دادهایم. در نتیجه مجموعهای از patchهای چندضلعی رنگشده در محیط سهبعدی داریم و میتوان بیننده را هرجا قرار داد و صحنه را به روش متعارف و با یک رندرکنندهٔ خط لولهای رسم کرد.
۱۱.۵.۱ معادلهٔ Radiosity
فرض کنید صحنه از (n) patch شمارهگذاریشده از ۱ تا (n) تشکیل شده باشد. radiosity وصلهٔ (i)، یعنی (b_i)، شدت نور ــ انرژی بر واحد زمان ــ بر واحد سطح است که از patch خارج میشود. معمولاً radiosity با واحدی مانند وات بر متر مربع اندازهگیری میشود. چون شدت را در یک طول موج ثابت در نظر میگیریم، میتوان تابع (b_i(\lambda)) را تعیینکنندهٔ رنگ patch (i) دانست.
فرض کنید مساحت patch (i) برابر (a_i) باشد. چون هر patch کاملاً پخشی است، شدت کل خروجی از آن (b_i a_i) است. با استدلالی مشابه استخراج معادلهٔ رندرینگ، شدت خروجی از یک مؤلفهٔ گسیلی ــ که آن هم روی patch ثابت فرض میشود ــ و یک مؤلفهٔ بازتابی ناشی از نور همهٔ patchهای دیگری که به patch (i) میرسند تشکیل میشود:
b_i a_i=e_i a_i+\rho_i\sum_{j=0}^{n}f_{ji}b_j a_j.
جملهٔ (f_{ij}) form factor (ضریب شکل) میان patchهای (i) و (j) نام دارد. این ضریب کسری از انرژی خروجی patch (i) را نشان میدهد که به patch (j) میرسد. form factor به جهتگیری دو patch نسبت به هم، فاصلهٔ آنها و وجود یا نبود patchهای دیگری که نور را میپوشانند بستگی دارد. محاسبهٔ این ضریبها در زیربخش بعد بررسی میشود. ضریب بازتاب patch (i) برابر (\rho_i) است.
میان (f_{ij}) و (f_{ji}) رابطهٔ سادهای به نام رابطهٔ تقابل وجود دارد:
f_{ij}a_i=f_{ji}a_j.
با جایگذاری این رابطه در معادلهٔ شدت patchها داریم:
b_i a_i=e_i a_i+\rho_i\sum_{j=0}^{n}f_{ij}b_j a_i.
با تقسیم بر (a_i):
b_i=e_i+\rho_i\sum_{j=0}^{n}f_{ij}b_j.
این نتیجه معادلهٔ radiosity نام دارد.
اگر form factorها را محاسبه کرده باشیم، دستگاهی شامل (n) معادلهٔ خطی برای (n) radiosity مجهول داریم. در مقایسه با معادلهٔ رندرینگ، اگر patchها کوچکتر و کوچکتر شوند، در حد به بینهایت patch میرسیم؛ جمع به انتگرال تبدیل میشود و معادلهٔ radiosity به حالت خاصی از معادلهٔ رندرینگ برای سطحهای کاملاً پخشی تبدیل خواهد شد.
معادلات را میتوان با تعریف ماتریس ستونی radiosityها
b=[b_i],
ماتریس ستونی گسیل patchها
e=[e_i],
ماتریس قطری ضرایب بازتاب
R=[r_{ij}],\qquad
r_{ij}=
\begin{cases}
\rho_i,&i=j,\0,&\text{در غیر این صورت,}
\end{cases}
و ماتریس form factorها
F=[f_{ij}]
به صورت ماتریسی نوشت.
اکنون دستگاه معادلات radiosity به صورت
b=e+RFb
درمیآید و جواب رسمی آن را میتوان چنین نوشت:
b=[I-RF]^{-1}e.
۱۱.۵.۲ حل معادلهٔ Radiosity
اگرچه میتوان نشان داد معادلهٔ radiosity حتماً جواب دارد، دشواری اصلی عملی است. یک صحنهٔ معمولی هزاران patch دارد؛ بنابراین حل مستقیم دستگاه، مثلاً با حذف Gaussian، معمولاً امکانپذیر نیست. بیشتر روشها از این واقعیت استفاده میکنند که ماتریس (F) تنک است. بیشتر عناصر آن عملاً صفرند، زیرا اغلب patchها آنقدر از هم دورند که تقریباً هیچیک از نور گسیلشده یا بازتابشدهٔ یک patch به بیشتر patchهای دیگر نمیرسد.
حل دستگاههای شامل ماتریس تنک بر روشهای تکراری استوار است که به ضرب این ماتریسها نیاز دارند؛ عملیاتی که برای ماتریس تنک کارآمد است. از معادلهٔ patchها تکرار زیر را میسازیم:
b^{k+1}=e+RFb^k.
هر تکرار ضرب (RFb^k) را نیاز دارد که با فرض تنکبودن (F)، بهجای (O(n^2)) در حالت عمومی، حدود (O(n)) عملیات میطلبد. برای radiosityهای منفرد:
b_i^{k+1}=e_i+\sum_{j=1}^{n}\rho_i f_{ij}b_j^k.
این روش، روش Jacobi، برای این مسئله مستقل از نقطهٔ شروع (b^0) همگرا میشود.
در حالت عمومی patchها خودبازتاب نیستند، پس (f_{ii}=0). اگر بهمحض در دسترسبودن هر مقدار جدید آن را بهروزرسانی کنیم، به روش Gauss-Seidel میرسیم:
b_i^{k+1}=e_i+
\sum_{j=1}^{i-1}\rho_i f_{ij}b_j^{k+1}
+
\sum_{j=i+1}^{n}\rho_i f_{ij}b_j^k.
یک تکرار دیگر نیز وجود دارد که دید فیزیکی بیشتری میدهد. فرمول اسکالر
\frac1{1-x}=\sum_{i=0}^{\infty}x^i
برای (|x|<1) برقرار است.
فرم ماتریسی این رابطه برای (RF) چنین است:²
[I-RF]^{-1}=\sum_{i=0}^{\infty}(RF)^i.
بنابراین
b=\sum_{i=0}^{\infty}(RF)^ie
یا
b=e+(RF)e+(RF)^2e+(RF)^3e+\cdots.
میتوان این سری را در نقطهای قطع کرد و از آن برای تقریب (b) استفاده کرد. هر جمله تعبیر فیزیکی روشنی دارد. جملهٔ اول (e) نور مستقیم گسیلشده از هر patch است؛ اگر فقط همین جمله را نگه داریم، تصویر تقریبی فقط منابع را نشان میدهد. جملهٔ دوم ((RF)e) نور ناشی از دقیقاً یک بازتاب از منابع به patchهای دیگر را اضافه میکند. جملهٔ بعدی سهم بازتابهای دوگانه را میافزاید و این روند برای جملههای بعدی ادامه دارد.
پاورقی ۲. سری زمانی همگراست که قدرمطلق همهٔ مقادیر ویژهٔ (RF) کمتر از ۱ باشد؛ شرطی که برای معادلهٔ radiosity باید برقرار باشد.
۱۱.۵.۳ محاسبهٔ Form Factorها
اکنون روشهایی نسبتاً کارآمد برای حل radiosity patchها داریم، اما هنوز محاسبهٔ form factorها را بررسی نکردهایم. ابتدا معادلهای عمومی برای form factor میان دو patch استخراج میکنیم و سپس روشهای تقریبی عملی را بررسی خواهیم کرد.
دو patch تخت و کاملاً پخشی (P_i) و (P_j) را مانند شکل ۱۱.۱۶ در نظر بگیرید. در شکل patch دیگری که باعث پوشیدگی شود وجود ندارد. هر patch یک نرمال دارد که جهتگیری آن را مشخص میکند.
شکل ۱۱.۱۶ — دو patch.
اگرچه هر patch نور را در همهٔ جهتها بهطور یکنواخت گسیل میکند، مقدار نوری که از دو نقطهٔ متفاوت روی (P_j) به نقطهای روی (P_i) میرسد به دلیل تفاوت فاصله یکسان نیست. بنابراین برای جمعکردن کل نوری که از (P_j) به (P_i) میرسد باید روی همهٔ نقاط (P_j) انتگرال بگیریم. همین استدلال دربارهٔ دو نقطه روی (P_i) نیز برقرار است: مقدار نور دریافتی آنها از یک نقطهٔ روی (P_j) متفاوت خواهد بود، پس برای تعیین نور واردشده به (P_i)، روی همهٔ نقاط (P_i) نیز باید انتگرال گرفته شود.
دو سطح کوچک (da_i) و (da_j) را روی دو patch در نظر بگیرید. هرکدام را میتوان یک بازتابندهٔ پخشی ایدهآل دانست (شکل ۱۱.۱۷). فاصلهٔ آنها (r) است، که فاصلهٔ نقاط مرکزی (p_i) و (p_j) است.
شکل ۱۱.۱۷ — کوتاهشدگی هندسی میان دو patch کوچک.
نور خروجی از (da_j) در جهت (d=p_i-p_j) حرکت میکند، اما شدت آن با ضریب (\cos\phi_j) کاهش مییابد؛ (\phi_j) زاویهٔ نرمال patch (j) با بردار (d) است. نور واردشده به (da_i) نیز با (\cos\phi_i) کوتاه میشود.
برای بهدستآوردن form factor مطلوب (f_{ij})، علاوه بر جهتگیری باید فاصله و امکان پوشیدگی را نیز در نظر بگیریم. ابتدا تابع دیدپذیری را تعریف میکنیم:
o_{ij}=
\begin{cases}
1,&\text{اگر }p_j\text{ از }p_i\text{ قابل مشاهده باشد،}\0,&\text{در غیر این صورت.}
\end{cases}
سپس با میانگینگیری روی مساحت کل patch، معادلهٔ form factor بهدست میآید:
f_{ij}=\frac1{a_i}
\int_{a_i}\int_{a_j}
o_{ij}\frac{\cos\phi_i\cos\phi_j}{\pi r^2}
\,da_i\,da_j.
فرم انتگرال ساده است، اما فقط برای چند حالت ویژه جواب تحلیلی دارد. در صحنههای واقعی به روشهای عددی نیاز است. چون (n^2) form factor وجود دارد، بیشتر روشها سازشی میان دقت و زماناند.
دو رویکرد را مرور میکنیم. روش نخست از ایدهٔ نگاشت دومرحلهای در texture mapping فصل ۷ آغاز میشود. دو patch را دوباره در نظر بگیرید، این بار نیمکرهای میان آنها قرار داده شده است (شکل ۱۱.۱۸). فرض کنید میخواهیم نور رسیده از (P_i) به (P_j) در نقطهٔ (p_i) را محاسبه کنیم. نیمکره را در این نقطه قرار میدهیم و patch را طوری جهت میدهیم که نرمال رو به بالا باشد. حال (P_j) را روی نیمکره تصویر میکنیم و میتوانیم بهجای patch اصلی از تصویرش برای محاسبهٔ form factor استفاده کنیم. اگر به مختصات قطبی تبدیل شویم، معادله برای patch تصویرشده سادهتر میشود. اما برای هر ناحیهٔ کوچک (P_i) باید نیمکره را جابهجا و سهم هر ناحیه را اضافه کنیم.
شکل ۱۱.۱۸ — تصویرکردن یک patch روی نیمکره.
برای بیشتر کاربردهای گرافیکی، استفاده از یک hemicube (نیممکعب) سادهتر از نیمکره است؛ شکل ۱۱.۱۹. نیممکعب در همان نقطه مرکز میشود، اما سطح آن به مربعهای کوچکی به نام پیکسل تقسیم میشود. مقدار نوری که به patch (i) میرسد به نوع سطح واسط وابسته نیست. مزیت نیممکعب این است که سطحهایش یا با (P_i) موازیاند یا بر آن عمود.
شکل ۱۱.۱۹ — تصویرکردن patch روی نیممکعب و سپس روی patch دیگر.
در نتیجه تصویرکردن (P_j) روی نیممکعب و محاسبهٔ سهم هر پیکسل نیممکعب در نوری که به (p_i) میرسد سرراست است. اگر سطح نیممکعب به (m) پیکسل شمارهگذاریشده از ۱ تا (m) تقسیم شود، میتوان سهم پیکسلهایی را که تصویر (P_j) روی آنها افتاده و از (p_i) قابل مشاهدهاند محاسبه و جمع کرد. حاصل delta form factor برای (f_{ij}) است، یعنی سهم (P_j) در ناحیهٔ کوچک (da_i) در مرکز نیممکعب. form factor نهایی با جمعکردن سهم همهٔ delta form factorها بهدست میآید.
سهم هر پیکسل پس از مشخصشدن اینکه (P_j) روی آن تصویر میشود یا نه، بهصورت تحلیلی قابل محاسبه است. این کار شبیه محاسبهٔ ray tracing برای تشخیص دیدهشدن یک شیء از منبع نور است. جزئیات در منابع پیشنهادی پایان فصل آمدهاند.
روش دیگر برای محاسبهٔ form factorها از توانایی سامانهٔ گرافیکی در تولید سریع رندرهای ساده استفاده میکند. فرض کنید میخواهیم (f_{ij}) را حساب کنیم. اگر (P_i) را فقط با مقدار معلوم نور از (P_j) روشن کنیم، اندازهگیری تجربیای از form factor مطلوب خواهیم داشت. این اندازهگیری را میتوان با قرار دادن منابع نور نقطهای روی (P_j) و رندر صحنه با رندرکنندهٔ موجود تقریب زد. چون ممکن است patch دیگری (P_i) را از (P_j) بپوشاند، رندرکننده باید توانایی محاسبهٔ سایه را داشته باشد.
۱۱.۵.۴ اجرای Radiosity در عمل
در عمل رندر radiosity سه مرحلهٔ اصلی دارد. ابتدا صحنه را مانند شکل ۱۱.۲۰ به مشی از patchها تقسیم میکنیم. این مرحله به مهارت نیاز دارد، زیرا patch بیشتر یعنی form factorهای بیشتری باید محاسبه شوند. در عین حال همین تقسیم سطحها به patchهاست که به radiosity امکان میدهد تعاملهای ظریف پخشی-پخشی را در تصویر نشان دهد.
ساخت مش اولیه اغلب میتواند تعاملی انجام شود تا در نواحیای مانند گوشهٔ میان سطحها که انتظار تعامل پخشی-پخشی داریم patchهای بیشتری قرار داده شوند.
شکل ۱۱.۲۰ — تقسیم سطحها به patch. (با اجازهٔ A. Van Pernis، K. Rasche و R. Geist، Clemson University)
رویکرد دیگر بر این مشاهده استوار است که radiosity یک سطح بزرگ برابر مجموع radiosity بخشهای هر تقسیمبندی از آن، با وزندهی بر اساس مساحت، است. بنابراین میتوان با مشی نسبتاً خشن شروع کرد و بعداً آن را پالایش کرد؛ این روش progressive radiosity (رادیوسیتی پیشرونده) نام دارد. پس از داشتن مش، form factorها محاسبه میشوند که پرهزینهترین بخش محاسباتی فرایند است.
وقتی مش و form factorها آماده شدند، معادلهٔ radiosity را حل میکنیم. آرایهٔ گسیل (e) را از مقادیر منابع نور صحنه میسازیم و با اختصاص رنگ به سطحها، (R) را تشکیل میدهیم. سپس معادله حل میشود تا (b) بهدست آید.
مؤلفههای (b) به رنگهای جدید patchها تبدیل میشوند. حال میتوان بیننده را در صحنه قرار داد و با یک رندرکنندهٔ متعارف تصویر را تولید کرد.
تصویر لوح رنگی ۱۶ با radiosity رندر شده است. کار از مش اولیهٔ شکل ۱۱.۲۰ آغاز شد و سپس برای دستیابی به مجموعهٔ بهتری از patchها با یک particle system تغییر داده شد. تصویر قدرت radiosity را برای رندر فضاهای داخلی متشکل از بازتابندههای پخشی نشان میدهد.
۱۱.۶ RenderMan
رویکردهای دیگری به رندر از نیازهای صنعت پویانمایی پدید آمدهاند. اگرچه تعامل در طراحی یک پویانمایی لازم است، رندر بلادرنگ الزام نهایی تولید نیست؛ بنابراین میتوان زمان بیشتری برای رسیدن به کیفیت بالاتر صرف کرد.
هنگام تولید تصاویر نهایی، رندر بلادرنگ لازم نیست. مهمتر آن است که تصویر از آرتیفکتهایی مانند دندانهدارشدن و الگوهای moiré ناشی از aliasing خالی باشد. با این حال، تعداد عظیم فریمهای یک فیلم بلند را نمیتوان صرفاً با ray tracer یا رندرکنندهٔ radiosity تولید کرد، حتی اگر از تعداد زیادی رایانه در قالب render farm (مزرعهٔ رندر) استفاده شود که وظیفهٔ اصلیشان رندر صحنهها در تفکیک مطلوب است. افزون بر این، ray tracing یا radiosity بهتنهایی لزوماً کیفیت هنری مطلوب را تولید نمیکنند.
رابط RenderMan بر پارادایم مدلسازی–رندر استوار است که در فصل ۱ معرفی شد. طراحی صحنه بهصورت تعاملی و با رندرکنندههای ساده از نوع فصل ۶ انجام میشود. پس از کاملشدن طراحی، اشیا، نورها، خواص مواد، دوربینها، توصیف حرکت و بافتها در فایلی ذخیره میشوند که میتوان آن را به یک رندرکنندهٔ باکیفیت یا render farm فرستاد.
در اصل این رندرکنندهٔ آفلاین میتواند از هر نوعی باشد. اما با توجه به نیازهای ویژهٔ صنعت پویانمایی، Pixar هم رابط RenderMan و هم رندرکنندهای به نام Reyes را توسعه داد که برای تولید تصاویر موردنیاز فیلمهای تجاری طراحی شده بود. مانند ray tracer، Reyes نیز پیکسلبهپیکسل کار میکند؛ اما برخلاف ray tracer، برای واردکردن اثرهای global illumination طراحی نشده است.
Reyes با کارکردن در مقیاس پیکسل، نور همهٔ اشیا را با تفکیکی جمع میکند که از مشکلات aliasing جلوگیری کند. این رندرکننده اشیای چندضلعی و منحنی را dice میکند؛ یعنی آنها را به micropolygonهای چهارضلعی کوچکی تقسیم میکند که تصویرشان تقریباً نصف یک پیکسل است. چون هر micropolygon ناحیهٔ بسیار کوچکی را میپوشاند، میتوان آن را با flat shading رندر کرد و محاسبه را ساده نگه داشت. نرم دیدهشدن سطح با رنگدهی دقیق micropolygonها هنگام dicing حاصل میشود.
Reyes تکنیکهای جالب دیگری نیز دارد. برای کاهش aliasing قابل مشاهده بهجای نمونهبرداری نقطهای از نمونهبرداری تصادفی استفاده میکند. معمولاً هر بار روی ناحیههای کوچک فریم کار میکند تا استفاده از بافتها کارآمد باشد. حتی با این طراحی دقیق، رندر یک صحنه با اشیای زیاد و اثرهای پیچیدهٔ نورپردازی ممکن است ساعتها طول بکشد.
رندرکنندههای فراوانی از این نوع وجود دارند که برخی عمومی یا shareware هستند. بعضی محصولات اجازه میدهند چند سبک رندر در یک صحنه ترکیب شود؛ مثلاً ray tracing فقط برای زیرمجموعهای از اشیای براق و radiosity برای گروه دیگری از سطحها. در حالت کلی این رندرکنندهها مجموعهٔ بزرگی از اثرها را پشتیبانی میکنند و به کاربر اجازه میدهند میان زمان رندر، پیچیدگی و کیفیت تصویر تعادل ایجاد کند.
۱۱.۷ رندر موازی
در بسیاری از کاربردها، بهویژه visualization علمی مجموعهدادههای هندسی بزرگ، ممکن است با بیش از ۵۰۰ میلیون نقطهٔ داده کار کنیم و بیش از ۱۰۰ میلیون چندضلعی تولید شود. این وضعیت دو چالش فوری ایجاد میکند. نخست، اگر قرار است این تعداد چندضلعی نمایش داده شود، چگونه آن را روی نمایشگری انجام دهیم که حتی بهترین مدلهای عمومی فقط حدود دو میلیون پیکسل دارند؟
دوم، اگر چند فریم برای نمایش داشته باشیم ــ چه از دادههای جدید و چه بر اثر تبدیل مجموعهدادهٔ اصلی ــ باید این حجم عظیم هندسه را سریعتر از توان یک سامانهٔ تکگرهی رندر کنیم.
راهحل رایج برای مشکل تفکیک نمایش، ساخت power wall است؛ سطح تصویری بزرگی که آرایهای از پروژکتورها آن را روشن میکنند (شکل ۱۱.۲۱). هر پروژکتور میتواند وضوحی مانند (1024\times1280) یا در مدلهای HD، (1920\times1080) داشته باشد. معمولاً شدت نور در لبههای تصویر هر پروژکتور کاهش داده و تصویرها کمی روی هم همپوشانی داده میشوند تا خروجی یکپارچه به نظر برسد. همچنین میتوان آرایهای از پنلهای LCD استاندارد ساخت، هرچند در این حالت فاصلههای باریک بین پنلها دیده میشوند و تصویر شبیه پنجرهای چندتکه خواهد بود.
شکل ۱۱.۲۱ — یک power wall با شش پروژکتور.
یکی از پاسخهای مشترک به هر دو مشکل استفاده از خوشهای از رایانههای استاندارد است که با شبکهای پرسرعت به هم متصلاند. هر رایانه ممکن است کارت گرافیک عمومی خود را داشته باشد. این پیکربندی بخشی از تحول بزرگ رایانش کاراییبالا است. در گذشته ابررایانهها از پردازندههای گرانقیمت و سریع ساخته میشدند که معمولاً موازیسازی زیادی در طراحی داشتند. این پردازندهها سفارشی بودند و رابطها، تجهیزات جانبی و محیطهای خاص خود را لازم داشتند، در نتیجه فقط آزمایشگاههای دولتی و شرکتهای بزرگ توان خریدشان را داشتند. در سالهای اخیر پردازندههای عمومی بسیار سریع و ارزان شدهاند.
همچنین روند طراحی به سمت قراردادن چند پردازنده در یک CPU یا GPU رفته و انواع مختلف موازیسازی را ممکن کرده است: یک CPU با چند کارت گرافیک، تعداد زیادی CPU چندهستهای، یا GPUهایی با صدها پردازندهٔ برنامهپذیر.
در نتیجه راههای متعددی برای توزیع کار رندر صحنه میان پردازندهها وجود دارد. سادهترین راه اجرای همان برنامهٔ کاربردی روی هر پردازنده است، با این تفاوت که هرکدام پنجرهای متفاوت را که متناظر با محل نمایش آن پردازنده در آرایهٔ خروجی است استفاده کند. با سرعت CPU و GPUهای جدید و حافظهٔ زیاد، این روش در بسیاری موارد کاملاً عملی است.
سه امکان دیگر را بررسی میکنیم. تفاوت کلیدی این طبقهبندی آن است که primitiveها را در کدام مرحله از فرایند رندر به ناحیهٔ درست نمایش اختصاص یا sort میکنیم. محل این مرحله سه نام sort first، sort last و sort middle را ایجاد میکند.
فرض کنید تعداد زیادی پردازنده از دو نوع داریم: geometry processor و raster processor. این تفکیک متناظر با دو فاز خط لولهٔ رندر در فصل ۶ است. پردازندههای هندسی محاسبات ممیزشناور بخش جلویی را انجام میدهند، از جمله تبدیل، clipping و shading. پردازندههای raster بیتها را دستکاری میکنند و عملیاتهایی مانند scan conversion را برعهده دارند. CPU و GPUهای عمومی امروز میتوانند هر دو نوع کار را انجام دهند، پس راهبردهای زیر هم برای CPU و هم برای GPU قابل استفادهاند. موازیسازی میتواند میان گرههای جدا، میان هستههای یک تراشه، یا داخل GPU رخ دهد. پارادایم sort کمک میکند این امکانهای معماری را منظم کنیم.
۱۱.۷.۱ رندر Sort-Middle
گروهی از geometry processorها با برچسب G و raster processorها با برچسب R را در پیکربندی شکل ۱۱.۲۲ در نظر بگیرید. فرض کنید برنامه تعداد زیادی primitive هندسی تولید میکند. میتوان چند geometry processor را به دو روش ساده بهکار گرفت. برنامه میتواند روی یک پردازنده اجرا شود و بخشهای مختلف هندسه را به geometry processorهای متفاوت بفرستد. یا خود برنامه روی چند پردازنده اجرا شود و هر پردازنده فقط بخشی از هندسه را تولید کند. در این مرحله مهم نیست هندسه دقیقاً چگونه به geometry processorها میرسد ــ بهترین روش اغلب به برنامه وابسته است ــ بلکه سؤال این است که چگونه از پردازندههای موجود بیشترین استفاده را ببریم.
فرض میکنیم هر primitive را میتوان به هر geometry processor فرستاد و هر پردازنده مستقل کار میکند. در پردازش موازی، load balancing (توازن بار) مسئلهای اساسی است: میخواهیم هر پردازنده تقریباً به یک اندازه کار انجام دهد تا هیچکدام برای مدت قابل توجهی بیکار نماند.
یک راه ظاهراً ساده تقسیم مساوی فضای مختصات شیء میان پردازندههاست. متأسفانه این روش اغلب توازن بار ضعیفی دارد، چون در بسیاری کاربردها هندسه در فضای شیء یکنواخت توزیع نشده است. روش جایگزین آن است که هنگام تولید اشیا، بدون توجه به محل آنها، هندسه را یکنواخت میان پردازندهها پخش کنیم.
شکل ۱۱.۲۲ — رندر Sort-Middle.
برای (n) پردازنده میتوان entity هندسی اول را به پردازندهٔ اول، دوم را به پردازندهٔ دوم، (n)-ام را به پردازندهٔ (n)-ام و ((n+1))-ام را دوباره به پردازندهٔ اول فرستاد و همین چرخه را ادامه داد.
اکنون raster processorها را در نظر بگیرید. میتوان هرکدام را به ناحیهای متفاوت از frame buffer یا، بهطور معادل، ناحیهای متفاوت از نمایش اختصاص داد. بنابراین هر raster processor بخش ثابتی از فضای صفحه را رندر میکند.
مسئله این است که خروجی geometry processorها چگونه به raster processor درست اختصاص داده شود. هر geometry processor ممکن است شیئی را پردازش کند که در هر جای نمایش ظاهر شود. پس باید خروجیها sort شوند و primitiveهای خارجشده از geometry processorها به raster processor متناظر با ناحیهٔ صفحه ارسال شوند. بنابراین sort پیش از مرحلهٔ raster انجام میشود و معماری sort middle نام میگیرد.
این پیکربندی چند سال پیش در workstationهای گرافیکی سطح بالا محبوب بود؛ زمانی که برای هر وظیفه سختافزار ویژه و برای انتقال داده در مرحلهٔ sort باسهای داخلی بسیار سریع وجود داشت. GPUهای جدید خود چند geometry processor و چند fragment processor دارند و از این دید میتوان آنها را sort-middle دانست.³ در ادامه، برای سادگی یک کارت گرافیک با یک GPU را ترکیبی از یک geometry processor و یک raster processor در نظر میگیریم و موازیسازی داخلی GPU را تجمیعشده فرض میکنیم. حال مسئله استفاده از گروهی از کارتها یا GPUهای عمومی است.
پاورقی ۳. برخی GPUهای جدید تعداد زیادی پردازنده دارند که میتوان هرکدام را بهعنوان vertex processor یا fragment processor استفاده کرد.
اگر بتوان CPU یا GPU را هم بهعنوان geometry processor و هم raster processor بهکار برد و آنها را با شبکهای استاندارد متصل کرد، مرحلهٔ sort در sort-middle ممکن است به گلوگاه تبدیل شود. دو رویکرد دیگر سادهتر هستند.
۱۱.۷.۲ رندر Sort-Last
در sort-middle تعداد geometry processor و raster processor میتوانست متفاوت باشد. اکنون فرض کنید هر geometry processor به raster processor خودش متصل باشد، همانطور که در شکل ۱۱.۲۳ دیده میشود. چنین پیکربندیای در مجموعهای از PCهای استاندارد با کارت گرافیک مستقل، یا در برخی کارتهای جدید با چند vertex/fragment processor یکپارچه، وجود دارد.
شکل ۱۱.۲۳ — رندر Sort-Last.
باز هم نحوهٔ رسیدن دادهٔ برنامه به هر پردازنده را کنار میگذاریم و روی پردازش هندسه تمرکز میکنیم. مانند sort-middle میتوان بار geometry processorها را با ارسال primitiveها به ترتیبی که محل نهایی آنها روی نمایش را نادیده میگیرد متعادل کرد. اما دقیقاً به دلیل همین نوع تخصیص هندسه و نبود sort در میانه، هر raster processor باید frame bufferای به اندازهٔ کل نمایش داشته باشد. چون هر جفت geometry/raster یک خط لولهٔ کامل است، هر جفت برای بخشی از هندسه تصویری صحیح با حذف سطح پنهان تولید میکند.
شکل ۱۱.۲۴ سه تصویر جزئی صحیح را نشان میدهد و تصویر چهارم نشان میدهد چگونه باید آنها را ترکیب کرد تا تصویر نهایی شامل کل هندسه بهدست آید.
این تصویرهای جزئی در مرحلهای به نام compositing با هم ترکیب میشوند. برای compositing علاوه بر color bufferهای پردازندهها به اطلاعات depth نیز نیاز داریم، زیرا برای هر پیکسل باید بدانیم کدام raster processor پیکسلی متناظر با نزدیکترین هندسه را در اختیار دارد.