رندر حجمی، Marching Cubes، سادهسازی مش و رندر مبتنی بر تصویر
شکل ۱۱.۲۴ — نمونهای از رندر Sort-Last. (الف) تا (ج) رندرهای جزئی؛ (د) تصویر composited نهایی. (با اجازهٔ Ge Li، دانشگاه نیومکزیکو)
شکل ۱۱.۲۵ — Compositing بهصورت درخت دودویی.
برای ساخت تصویر نهایی در معماری sort-last باید برای هر پیکسل، دادهای را انتخاب کنیم که به نزدیکترین نقطهٔ هندسی نسبت به بیننده تعلق دارد.⁴ خوشبختانه در خط لولهٔ استاندارد OpenGL این اطلاعات در z-buffer وجود دارد. کافی است برای هر پیکسل عمقهای متناظر در z-bufferهای مختلف را مقایسه کنیم و رنگ پردازندهای را در frame buffer بنویسیم که کمترین عمق، یعنی نزدیکترین نقطه، را دارد. دشواری اصلی این است که وقتی این اطلاعات میان تعداد زیادی پردازنده توزیع شدهاند، مقایسه را چگونه بهصورت کارآمد انجام دهیم.
از نظر مفهومی سادهترین روش که گاهی binary-tree compositing نامیده میشود این است که پردازندهها دوبهدو اطلاعات خود را ترکیب کنند. در شکل ۱۱.۲۵ چهار خط لولهٔ geometry/raster با شمارههای ۰ تا ۳ داریم. پردازندههای ۰ و ۱ میتوانند همزمان با پردازندههای ۲ و ۳ دادههای خود را ترکیب کنند و برای هندسهای که دیدهاند یک تصویر صحیح بسازند. فرض کنیم تصاویر ترکیبی جدید روی پردازندههای ۱ و ۳ ساخته شوند؛ در این صورت پردازندههای ۰ و ۲ باید هم color buffer و هم z-buffer خود را به همسایهٔ متناظرشان، یعنی ۱ و ۳، بفرستند. سپس همین فرایند میان پردازندههای ۱ و ۳ تکرار میشود و تصویر نهایی در frame buffer پردازندهٔ ۳ شکل میگیرد.
کد این روش بسیار ساده است. هر جفت geometry/raster یک رندر عادی انجام میدهد و مرحلهٔ compositing فقط خواندن پیکسلها و چند مقایسهٔ ساده را میخواهد. بااینحال در هر مرحلهٔ بعدی compositing فقط نیمی از پردازندههای مرحلهٔ قبل موردنیازند؛ بنابراین در پایان همهٔ کار روی یک پردازنده جمع میشود و بقیه بیکار میمانند.
روش دیگری به نام binary-swap compositing مشکل بیکارشدن پردازندهها را رفع میکند. در این روش هر پردازنده مسئول بخشی از تصویر نهایی است؛ بنابراین برای آنکه compositing درست باشد، هر پردازنده باید در نهایت دادهٔ مرتبط با تمام هندسه را برای بخش خودش ببیند.
پاورقی ۴. برای سادگی فرض میکنیم همهٔ اشیای هندسی کدر هستند.
شکل ۱۱.۲۶ — Binary-swap compositing.
اگر در compositing تعداد n پردازنده داشته باشیم، میتوان آنها را مانند شکل ۱۱.۲۶ بهصورت round-robin سازمان داد. compositing در n گام انجام میشود، نه در log n گامی که در tree compositing لازم بود. در گام نخست، پردازندهٔ ۰ بخش ۰ از frame buffer خود را به پردازندهٔ ۱ میفرستد و بخش n را از پردازندهٔ n دریافت میکند. سایر پردازندهها نیز قسمتهای متناظر color buffer و depth buffer همسایههای خود را ردوبدل میکنند.
در این نقطه هر پردازنده میتواند یک ناحیهٔ نمایش را بهگونهای بهروزرسانی کند که برای دادههای دو پردازنده صحیح باشد. برای پردازندهٔ ۰ این ناحیه، ناحیهٔ n است. در دور دوم، پردازندهٔ ۰ از پردازندهٔ n دادههای ناحیهٔ n-1 را میگیرد؛ این دادهها از قبل برای پردازندههای n و n-1 صحیحاند. پردازندهٔ ۰ همزمان دادههای ناحیهٔ n را میفرستد و بقیهٔ پردازندهها نیز همین کار را برای بخش خود انجام میدهند. اکنون هر پردازنده ناحیهای دارد که برای دادههای سه پردازنده صحیح است. با استقرا روشن است که پس از n-1 گام، هر پردازنده 1/n تصویر نهایی را در اختیار دارد. تعداد گامها بیشتر است، اما مقدار دادهٔ منتقلشده بسیار کمتر از tree compositing است و در هر گام همهٔ پردازندهها فعال میمانند.
۱۱.۷.۳ رندر Sort-First
یکی از جذابیتهای sort-last آن است که میتوان geometry processor و raster processor را جفت کرد و از رایانهها و کارتهای گرافیک استاندارد استفاده کرد. حال فرض کنید بتوانیم پیش از رندر مشخص کنیم هر primitive در کدام بخش نمایش نهایی قرار خواهد گرفت. در این صورت میتوان ناحیهای مستقل از نمایش را به هر جفت geometry/raster اختصاص داد و شبکهٔ compositing را حذف کرد. شکل ۱۱.۲۷ چنین پیکربندیای را نشان میدهد؛ یک پردازنده در front end وظیفه دارد primitiveها را به پردازندههای مناسب اختصاص دهد.
این sort اولیه کلید کارکرد این راهبرد است. در نگاه اول ناممکن به نظر میرسد، چون گویی پیش از عبور از geometry pipeline باید پاسخ مسئله، یعنی محل primitive روی صفحه، را بدانیم. اما در بسیاری از مسائل ساختار داده بهگونهای است که این اطلاعات از قبل تقریباً معلوم است. همچنین میتوان با glGetFloatv اطلاعات نگاشت مختصات شیء به مختصات صفحه را از خط لوله بازخوانی کرد.
شکل ۱۱.۲۷ — رندر Sort-First.
حتی لازم نیست sort اولیه همیشه کاملاً دقیق باشد. اگر primitive بیش از یک ناحیهٔ نمایش را قطع کند، میتوان آن را به چند geometry processor فرستاد. اگر primitive به پردازندهٔ اشتباه برسد، آن پردازنده نیز ممکن است بتواند آن را به پردازندهٔ صحیح منتقل کند. چون هر geometry processor مرحلهٔ clipping دارد، تصویر نهایی همچنان میتواند صحیح باقی بماند.
sort-first مشکل load balancing را خودبهخود حل نمیکند؛ اگر بعضی نواحی صفحه primitiveهای بسیار کمی داشته باشند، پردازندههای متناظر بار کمی خواهند داشت. بااینحال نسبت به sort-last یک مزیت بسیار مهم دارد: برای تولید نمایشگرهای با تفکیک بالا ایدهآل است. نمایشگرهای معمول CRT یا LCD در حدود ۱ تا ۳ میلیون پیکسل دارند، درحالیکه برای بررسی دادههایی با بیش از ۱۰۰ میلیون primitive هندسی ممکن است به وضوح بسیار بیشتری نیاز داشته باشیم.
یک راه، ساخت tiled display یا power wall از آرایهای از نمایشگرهای استاندارد است. هر tile میتواند CRT، پنل LCD یا خروجی یک پروژکتور باشد. از دید رندر، هدف ساخت تصویری با وضوح کل آرایه است که میتواند از 4000 × 4000 پیکسل فراتر رود. چنین نمایشگرهایی معمولاً با خوشهای از PCهای دارای کارت گرافیک عمومی راهاندازی میشوند؛ بنابراین دو گزینهٔ اصلی sort-first و sort-last هستند.
sort-last در این وضعیت مناسب نیست، زیرا هر جفت geometry/raster باید frame bufferای به اندازهٔ کل تصویر نهایی داشته باشد و در compositing حجم بسیار بزرگی از داده میان پردازندهها جابهجا شود. در sort-first این مشکل وجود ندارد؛ هر جفت geometry/raster تنها مسئول قسمت کوچکی از تصویر نهایی است.
معمولاً اندازهٔ آن قسمت تقریباً همان اندازهٔ یک frame buffer استاندارد است.
۱۱.۸ رندر حجمی
توسعهٔ گرافیک رایانهای ما تاکنون عمدتاً بر نمایش سطحها متمرکز بوده است. حتی وقتی شیئی را طوری رندر میکنیم که سهبعدی به نظر برسد، آن را مجموعهای از سطحهای دوبعدی در فضای سهبعدی مدل میکنیم و سپس این سطحها را رندر میکنیم. این رویکرد برای دادهای مناسب نیست که در آن هر مقدار، مقداری را در نقطهای داخل یک ناحیهٔ سهبعدی بیان میکند.
تابع f را در ناحیهای از فضای سهبعدی در نظر بگیرید. در هر نقطه مقدار اسکالر f(x,y,z) داریم و میگوییم f یک scalar field (میدان اسکالر) تعریف میکند. این مقدار میتواند چگالی داخل یک جسم، میزان جذب پرتو X در بدن انسان که با CT اندازهگیری شده، یا شفافیت یک قطعه شیشه باشد.
visualization میدانهای اسکالر سهبعدی از مسائل قبلی دشوارتر است. نخست، دادهٔ سهبعدی بسیار حجیمتر است و کارهای عادی روی دادهٔ دوبعدی، مانند خواندن فایل و تبدیل، از نظر عملی پرهزینه میشوند. دوم، در مسئلهای با دو متغیر مستقل میتوانستیم از بعد سوم برای نمایش مقدار اسکالر استفاده کنیم؛ اما با سه متغیر مستقل بعد اضافیای برای نمایش نداریم. بااینحال با دقت میتوان بسیاری از روشهای قبلی را به میدانهای اسکالر سهبعدی تعمیم داد.
حوزهٔ volume rendering (رندر حجمی) با این مسائل سروکار دارد. بیشتر روشهای visualization دادههای حجمی توسعهای از تکنیکهای پیشیناند. در بخشهای بعد چند روش را مرور میکنیم و جزئیات بیشتر در منابع پیشنهادی پایان فصل آمده است.
۱۱.۸.۱ مجموعهدادههای حجمی
از مجموعهای گسسته از داده آغاز میکنیم که ممکن است حاصل اندازهگیری یک فرایند فیزیکی، مانند CT پزشکی، باشد. یا ممکن است با ارزیابی/نمونهبرداری تابع f(x,y,z) در مجموعه نقاط {xi, yi, zi} یک مجموعهدادهٔ حجمی ساخته باشیم.
فرض کنید نمونهها با فاصلههای مساوی در سه محور گرفته شدهاند، همانگونه که در شکل ۱۱.۲۸ میبینیم. این فرض برای سادگی است و الزامی نیست:
x_i=x_0+i\Delta x,\qquad y_j=y_0+j\Delta y,\qquad z_k=z_0+k\Delta z.
و میتوانیم تعریف کنیم:
شکل ۱۱.۲۸ — یک مجموعهدادهٔ حجمی.
f_{ijk}=f(x_i,y_j,z_k).
هر fijk را میتوان میانگین مقدار میدان اسکالر درون یک متوازیالسطوح قائم با ابعاد Δx، Δy و Δz و مرکز (xi,yj,zk) در نظر گرفت. این عنصر حجمی را volume element یا voxel (وکسل) مینامیم.
آرایهٔ سهبعدی مقادیر voxel که از نمونههای با فاصلهٔ مساوی ساخته میشود structured data set (مجموعهدادهٔ ساختیافته) نام دارد، زیرا لازم نیست محل فضایی هر نمونه را جداگانه ذخیره کنیم. در عمل اصطلاحهای «مجموعهدادهٔ ساختیافته» و «مجموعهٔ voxelها» اغلب مترادف بهکار میروند.
در دادههای پراکنده باید علاوه بر مقدارهای اسکالر، محل نمونهها نیز ذخیره شود؛ چنین مجموعهای unstructured است. visualization دادهٔ unstructured پیچیدهتر است، اما میتوان همان ایدههای کلی دادهٔ structured را برای آن بهکار برد؛ بنابراین این موضوع را ادامه نمیدهیم.
برای نمایش این دادهها روشهای فراوانی وجود دارد، اما دو خانوادهٔ اصلی عبارتاند از direct volume rendering و isosurface. در direct volume rendering همهٔ voxelها میتوانند در تصویر سهم داشته باشند؛ روش isosurface فقط از زیرمجموعهای از voxelها استفاده میکند. برای تابع f(x,y,z)، isosurface سطحی است که معادلهٔ ضمنی زیر را ارضا میکند:
f(x,y,z)=c.
ثابت c مقدار isosurface است. در مسئلهٔ گسسته که از مجموعهٔ voxelها آغاز میکنیم، هدف یافتن تقریبهایی از چنین سطحهایی است.
۱۱.۸.۲ Visualization تابعهای ضمنی
visualization isosurface تعمیم طبیعی contour به سه بعد است و بنابراین با نمایش تابعهای ضمنی ارتباط دارد. تابع ضمنی سهبعدی زیر را در نظر بگیرید:
g(x,y,z)=0,
که g بهصورت تحلیلی معلوم است. اگر نقطهای این معادله را ارضا کند، تابع یک یا چند سطح را توصیف میکند. نمونههای ساده شامل کره، صفحه، quadricهای عمومی و torus با شعاع r و مقطع a است:
(x^2+y^2+z^2-r^2-a^2)^2-4a^2(r^2-z^2)=0.
همانگونه که در فصل ۱۰ دیدیم، g یک membership function است و میتوان با آن آزمود نقطهای روی سطح قرار دارد یا نه، اما روش عمومیای برای یافتن نقاط سطح وجود ندارد. پس برای یک g مشخص به تکنیک visualization نیاز داریم تا سطح را «ببینیم».
یک روش، شکل سادهای از ray tracing است که ray casting نام دارد. شکل ۱۱.۲۹ تابع، بیننده و صفحهٔ تصویر را نشان میدهد. هر projector را میتوان به شکل پارامتری نوشت:
p(t)=p_0+td.
و مؤلفههای آن عبارتاند از:
x(t)=x_0+td_x,\qquad y(t)=y_0+td_y,\qquad z(t)=z_0+td_z.
با جایگذاری در معادلهٔ ضمنی، یک معادلهٔ اسکالر بر حسب t بهدست میآوریم:
f(x_0+td_x,y_0+td_y,z_0+td_z)=u(t)=0.
شکل ۱۱.۲۹ — Ray casting یک تابع ضمنی.
ریشههای این معادله نقاطی را مشخص میکنند که projector یا ray وارد isosurface میشود یا از آن خارج میشود. اگر f ساده باشد، مانند quadric یا torus، ممکن است u(t) مستقیماً حل شود؛ مشابه آنچه در بحث ray tracing بخش ۱۱.۳ دیدیم.
پس از یافتن تقاطعها میتوان یک مدل shading ساده روی سطح اعمال کرد. نرمال لازم در نقطهٔ تقاطع از مشتقهای جزئی بهدست میآید:
\mathbf n=\begin{bmatrix}
\partial f/\partial x\\partial f/\partial y\\partial f/\partial z
\end{bmatrix}.
معمولاً ملاحظات global illumination را وارد نمیکنیم و shadow ray یا پرتوهای بازتابی/رهگیریشده محاسبه نمیشوند. برای صحنههای متشکل از اشیای ساده مانند quadricها، ray casting علاوه بر نمایش، تعیین سطح مرئی را نیز انجام میدهد و اغلب با مدلهای CSG استفاده میشود. برای تابعهایی پیچیدهتر از quadric، محاسبهٔ تقاطع بسیار پرهزینه میشود و باید روش دیگری برگزید.
اکنون مسئله را از دیدن سطح به دیدن حجم تعمیم میدهیم. بهجای سطح g(x,y,z)=0، میدان اسکالر f(x,y,z) را در نظر بگیرید. اگر فقط مقدار c از f اهمیت داشته باشد، مسئله visualization همان نمایش isosurface زیر است:
g(x,y,z)=f(x,y,z)-c=0.
گاهی نمایش یک isosurface برای مقدار مشخص c کافی است؛ مثلاً در دادهٔ CT میتوان c را برابر چگالی پرتو X بافتی انتخاب کرد که میخواهیم ببینیم. در مسائل دیگر ممکن است چند isosurface همزمان نمایش داده شود.
یافتن isosurface معمولاً با نسخهٔ گسستهٔ مسئله انجام میشود؛ تابع پیوسته با نمونههای روی یک grid جایگزین میشود. روش اصلی ما marching cubes است؛ نسخهٔ سهبعدی marching squares.
۱۱.۹ Isosurface و Marching Cubes
فرض کنید مجموعه دادهٔ {fijk} داریم که هر مقدار voxel نمونهای از میدان اسکالر f(x,y,z) است و نمونهها روی یک grid منظم گرفته شدهاند. هدف ساخت یک isosurface تقریبی به شکل polygonal mesh است. برای یک c ممکن است هیچ سطح، یک سطح یا چند سطح وجود داشته باشد. ازآنجاکه مثلثهای سهبعدی را بسیار خوب رندر میکنیم، marching cubes سطح را با مجموعهای از مثلثها تقریب میزند که هرکدام بخشی از isosurface را نمایش میدهند.
شکل ۱۱.۳۰ — سلول voxel.
فرض کردهایم مقدارهای voxel روی grid منظم سهبعدی قرار دارند که از مرکز voxelها عبور میکند. اگر چنین نباشد، با interpolation میتوان مقدارها را روی چنین gridی بهدست آورد. هشت نقطهٔ مجاور grid یک سلول سهبعدی میسازند، مانند شکل ۱۱.۳۰. به رأس (i,j,k) مقدار fijk نسبت داده میشود. سپس میتوان فقط بر اساس مقدار رأسهای هر سلول، بخشهایی از isosurface را که از سلول عبور میکنند جستوجو کرد.
برای مقدار isosurface برابر c، رأس هر سلول را بسته به اینکه مقدار آن بزرگتر یا کوچکتر از c است سیاه یا سفید میکنیم. در ظاهر 2^8=256 رنگآمیزی ممکن وجود دارد، اما با درنظرگرفتن تقارنها فقط ۱۴ حالت یکتای شکل ۱۱.۳۱ باقی میماند.⁵
با سادهترین تفسیر داده، نقاط تقاطع سطح با لبههای مکعب را با linear interpolation میان مقدارهای دو رأس لبه بهدست میآوریم. سپس با مثلثها این تقاطعها را tessellate میکنیم و قطعاتی از یک triangular mesh که از سلول میگذرد میسازیم.
شکل ۱۱.۳۱ — رنگآمیزیهای رأس.
پاورقی ۵. مقالهٔ اصلی Lorensen و Cline [Lor87] و بسیاری از مقالههای بعدی از ۱۵ حالت سخن میگویند، اما دو مورد از آنها متقارناند.
شکل ۱۱.۳۲ — Tessellationهای مورد استفاده در marching cubes.
همانند سلولهای contour plot، هر سلول سهبعدی را میتوان مستقل پردازش کرد. در دادهٔ نمونهبرداریشده، هر voxel داخلی در هشت سلول سهم دارد. میتوان داده را سطربهسطر و سپس صفحهبهصفحه پیمایش کرد. هنگام پیمایش، محل isosurface در هر سلول با مقایسهٔ هشت مقدار رأس با c تعیین و triangleهای متناظر تولید میشود.
این روش بسیار سریع است و بهسادگی موازی میشود، اما یک مسئلهٔ ابهام دارد. بعضی الگوهای سیاه/سفید را میتوان به بیش از یک شکل از نظر توپولوژیک معتبر tessellate کرد. اگر سلولهای مجاور تفسیرهای ناسازگار انتخاب کنند، ممکن است شکاف یا اتصال نادرست در سطح ایجاد شود. این همان نوع ابهامی است که در marching squares نیز دیده میشود. برای حل همیشهصحیح آن به اطلاعاتی بیش از مقادیر نمونهشدهٔ موجود نیاز است.
شکل ۱۱.۳۳ — مسئلهٔ ابهام در marching cubes. (الف) سلول؛ (ب) یک تفسیر؛ (ج) تفسیر دوم.
درست مانند contour plotها، برای رفع قطعی همهٔ ابهامها باید اطلاعات بیشتری از آنچه در دادهٔ نمونهبرداریشده وجود دارد در اختیار داشته باشیم.
۱۱.۱۰ سادهسازی مش
marching cubes را میتوان روشی برای ساخت قطعات کوچک مثلثی از isosurface دانست؛ بهطور معادل خروجی آن یک یا چند triangular mesh است. این مشها با وجود آنکه فقط از مثلث ساخته شدهاند، معمولاً بسیار نامنظماند.
یکی از ضعفهای marching cubes این است که میتواند بسیار بیشتر از تعداد لازم برای نمایش isosurface مثلث تولید کند. علت آن است که تعداد مثلثها بیشتر به وضوح مجموعهداده وابسته است تا نرمی واقعی سطح. بنابراین اغلب میتوان مشی جدید با مثلثهای بسیار کمتر ساخت که از دید بصری هنگام رندر تقریباً از مش اولیه قابل تشخیص نباشد. برای این mesh simplification روشهای مختلفی وجود دارد.
یکی از روشهای محبوب triangle decimation است که با حذف برخی لبهها و رأسها مش را ساده میکند. در مش شکل ۱۱.۳۴، اگر رأس A را به محل رأس B منتقل کنیم، دو مثلث حذف میشوند و مش سادهشدهٔ شکل ۱۱.۳۵ را بهدست میآوریم. تصمیم دربارهٔ حذف مثلثها میتواند بر معیارهایی مانند نرمی موضعی سطح یا شکل triangleها استوار باشد. معیار دوم مهم است، زیرا triangleهای بسیار باریک و کشیده کیفیت رندر خوبی ندارند.
شکل ۱۱.۳۴ — مش اولیه.
شکل ۱۱.۳۵ — مش پس از سادهسازی.
روشهای دیگری سطح تولیدشده از مش اولیه را دوباره resample میکنند و مجموعهای تازه از نقاط واقع بر سطح میسازند. این نقاط unstructured هستند و connectivity مش اولیه را ندارند، پس آزادیم آنها را به روشی بهینه به یکدیگر متصل کنیم. یکی از متداولترین روشها Delaunay triangulation فصل ۱۰ است.
روش دیگر برای resampling آن است که نقاطی را روی مش اولیه قرار دهیم یا زیرمجموعهای از رأسها را انتخاب کنیم و سپس با یک particle system محل نهایی نقاط/ذرات را کنترل کنیم. نیروهای دافعه میان ذرات آنها را به موقعیتهایی میرانند که در نهایت مش مناسبی شکل میگیرد.
۱۱.۱۱ Direct Volume Rendering
ضعف رندر isosurface این است که همهٔ voxelها در تصویر نهایی سهم ندارند. در نتیجه با انتخاب isovalue نامناسب ممکن است مهمترین بخش داده را از دست بدهیم. Direct volume rendering تصویرهایی میسازد که در آن همهٔ voxelها امکان مشارکت دارند. این تکنیکها معمولاً یا توسعهای از روشهای compositing فصل ۷ هستند یا کاربردی از ray tracing.
چون voxelها معمولاً روی grid مستطیلی قرار دارند، با معلومشدن محل بیننده یک ترتیب فضایی برای رندر front-to-back یا back-to-front داریم.
روشهای ابتدایی direct volume rendering هر voxel را مکعب کوچکی فرض میکردند که یا کاملاً شفاف یا کاملاً کدر بود. در رندر front-to-back، ray تا نخستین voxel کدر دنبال میشد و پیکسل متناظر سیاه میشد؛ اگر هیچ voxel کدری روی ray نبود پیکسل سفید میشد. در رندر back-to-front از painter’s algorithm برای رسم فقط voxelهای کدر استفاده میشد. هر دو تکنیک به دلیل تصویرکردن هر voxel بهعنوان یک مکعب، aliasing شدید تولید میکردند و اطلاعات همهٔ voxelها را نیز نشان نمیدادند. با استفاده از رنگ و opacity میتوان این مسائل را کاهش داد.
شکل ۱۱.۳۶ — Histogram دادهٔ CT.
۱۱.۱۱.۱ تخصیص رنگ و Opacity
ابتدا به هر voxel یک رنگ و میزان شفافیت نسبت میدهیم. مثلاً برای CT سر انسان میتوان رنگ را بر اساس چگالی جذب پرتو X انتخاب کرد: بافت نرم با چگالی کم قرمز، چربی با چگالی متوسط آبی، بافت سخت با چگالی زیاد سفید و فضای خالی سیاه باشد.
این تخصیصها اغلب با بررسی توزیع مقدار voxelها، یعنی histogram داده، انجام میشوند. شکل ۱۱.۳۶ histogramی با چهار قله نشان میدهد. میتوان به هر قله رنگی اختصاص داد؛ در indexed color نیز مؤلفههای red، green و blue را با جدولهایی که از منحنیهای شکل ۱۱.۳۷ بهدست میآیند به indexها نسبت داد. در CT، مثلاً یک قله ممکن است به جمجمه و رنگ سفید و قلهٔ دیگری به فضای خالی و رنگ سیاه متناظر شود.
opacity بر اساس voxelهایی تعیین میشود که میخواهیم در تصویر برجسته شوند. اگر بخواهیم مغز دیده شود ولی جمجمه نه، میتوان opacity مقدارهای متناظر با جمجمه را صفر کرد. تعیین رنگ و opacity خود یک مسئلهٔ pattern recognition است و در اینجا دنبال نمیشود. معمولاً رابط کاربری اجازه میدهد این مقدارها تعاملی تنظیم شوند. مسئلهٔ ما این است که پس از این تخصیص چگونه تصویر دوبعدی ساخته شود.
۱۱.۱۱.۲ Splatting
پس از تعیین رنگ و opacity میتوان به هر voxel یک شکل هندسی نسبت داد و تکنیکهای compositing فصل ۷ را اعمال کرد. یکی از روشها painting بهصورت back-to-front است. در شکل ۱۱.۳۸، «front» نسبت به بیننده تعریف میشود. برای مجموعهدادهٔ سهبعدی، پس از تعیین محل بیننده ترتیب پردازش آرایهٔ voxelها مشخص میشود. همانطور که در فصل ۸ دیدیم، octree میتواند سازوکاری کارآمد برای ذخیرهٔ دادهٔ voxel باشد و موقعیت بیننده ترتیب پیمایش octree را تعیین میکند.
یک روش بسیار ساده برای ساخت تصویر splatting است. به هر voxel شکلی ساده میدهیم و تصویر آن را روی image plane میاندازیم. شکل ۱۱.۳۹ یک voxel کروی و splat یا footprint متناظر را نشان میدهد.
شکل ۱۱.۳۷ — منحنیهای رنگ برای دادهٔ CT.
شکل ۱۱.۳۸ — حجمی از voxelها.
شکل ۱۱.۳۹ — Splat یا footprint یک voxel.
اگر parallel projection داشته باشیم و همهٔ voxelها شکل یکسانی بگیرند، splatها فقط در رنگ و opacity تفاوت دارند. بنابراین لازم نیست برای هر voxel projection جداگانه انجام دهیم؛ میتوان footprint را بهصورت bitmap نگه داشت و آن را با عملیات bitblt در frame buffer کپی کرد.
انتخاب شکل voxel یک مسئلهٔ sampling از همان نوع فصل ۷ است. در حالت ایدهآل هر splat باید تصویر یک sinc سهبعدی باشد. استفاده از splat ششضلعی یا بیضوی مبتنی بر تقریب voxel با parallelepiped یا ellipsoid است، نه بر بخش reconstruction قضیهٔ sampling. تقریب بهتر استفاده از Gaussian splat است که تصویر تقریب Gaussian سهبعدی برای sinc محسوب میشود.
موضوع اصلی در ساخت تصویر splatted آن است که splatها چگونه در تصویر composited شوند. چون داده روی grid قرار دارد، از نظر فاصله تا بیننده یا projection plane از قبل مرتب است. میتوان داده را back-to-front پیمایش کرد و سهم هر voxel را از طریق splat آن افزود. کار با تصویر پسزمینه آغاز میشود و splatهای بعدی یکییکی blend میشوند.
۱۱.۱۱.۳ Volume Ray Tracing
روش دیگر direct volume rendering، رندر front-to-back با ray tracing است (شکل ۱۱.۴۰). با همان فرمولهای compositing مورد استفاده در splatting، در امتداد ray جلو میرویم؛ هنگامی که به voxel کدر برسیم رهگیری همان ray را فوراً متوقف میکنیم. دشواری این است که هر ray از sliceهای متعدد داده میگذرد و بنابراین باید دادهٔ حجمی موردنیاز را در دسترس نگه داریم.
شکل ۱۱.۴۰ — Volume ray casting. (الف) نمای سهبعدی؛ (ب) نمای بالا.
مسائل انتخاب میان رندر back-to-front و front-to-back مشابه انتخاب میان image-oriented renderer و object-oriented renderer است؛ تنها opacity را به فرایند افزودهایم. volume ray tracer میتواند تصویری سهبعدی بسازد و از تمام داده استفاده کند، اما هر بار که شرایط مشاهده تغییر کند یا تبدیلی روی داده اعمال شود تصویر ray-traced باید از ابتدا محاسبه شود.
روشی که بیشتر در volume ray tracing استفاده میشود اغلب ray casting نام دارد، زیرا معمولاً فقط shading در تقاطع ray با voxelها نمایش داده میشود و shadow rayها محاسبه نمیشوند. در سالهای اخیر راهبردهای مختلفی برای انجام بخش بزرگی از این محاسبات روی GPU بررسی شده است.
۱۱.۱۱.۴ Texture Mapping حجمها
پشتیبانی سختافزاری و نرمافزاری texture mapping پایهٔ روش دیگری برای direct volume rendering با texture سهبعدی است. فرض کنید texture memory کافی برای نگهداری کل مجموعهداده داریم. مجموعهای از صفحههای موازی با بیننده تعریف میکنیم و texture coordinateها را چنان به world coordinateها نگاشت میکنیم که این صفحهها texture memory را قطع کنند و مجموعهای از polygonهای موازی مانند شکل ۱۱.۴۱ بسازند. سپس voxelها را روی این polygonها texture map میکنیم.
ازآنجاکه در بیشتر مسائل فقط چندصد polygon برای سازگاری با تعداد دادهها لازم است، بار کمی به سختافزار رندر تحمیل میشود. برخلاف سایر روشهای volume rendering، این تکنیک آنقدر سریع است که میتوان بیننده را بلادرنگ حرکت داد و visualization تعاملی داشت.
شکل ۱۱.۴۱ — برش texture memory سهبعدی با polygonها.
این روش در عین سرعت یک مشکل aliasing دارد که به زاویهٔ polygonها نسبت به texture array وابسته است.
۱۱.۱۲ رندر مبتنی بر تصویر
در سالهای اخیر توجه زیادی به روشهایی شده است که از مجموعهای از تصویرهای دوبعدی آغاز میکنند و یا اطلاعات سهبعدی را از آنها استخراج میکنند یا تصویرهای جدیدی میسازند. شکلهای قدیمی و مهم این مسئله عبارتاند از:
- استخراج اطلاعات terrain از عکسهای هوایی؛
- ساخت تصویر سهبعدی از توالی X-rayهای دوبعدی در CT؛
- استخراج مدل هندسی از دوربینها در robotics؛
- warp کردن یک تصویر به تصویر دیگر، یعنی morphing.
کاربردهای جدید بیشتر بر ساخت تصویر تازه از توالی تصویرهایی تمرکز دارند که با دقت جمعآوری شدهاند. فرض کنید از یک شیء ــ انسان، ساختمان یا مدل CAD ــ مجموعهای عکس گرفتهایم و میخواهیم آن را از دیدگاه دیگری ببینیم. اگر مدل سهبعدی داشتیم، فقط بیننده یا شیء را جابهجا و تصویر جدید را رندر میکردیم. اما وقتی فقط دادهٔ دوبعدی داریم باید از روشهای image-based rendering استفاده کنیم؛ حوزهای که عناصری از computer graphics، image processing و computer vision را ترکیب میکند.
۱۱.۱۲.۱ یک مثال ساده
شکل ۱۱.۴۲ دو دوربین را نشان میدهد که یک نقطه را تصویر میکنند. در سمت چپ دوربین perspective در p1 و در سمت راست دوربین دوم در p2 قرار دارد. نقطهٔ q در هر دو تصویر دیده میشود. اگر مکان، جهتگیری و field of view هر دو دوربین را بدانیم، آیا میتوان q را از این دو تصویر بهدست آورد؟
شکل ۱۱.۴۲ — دو دوربین که یک نقطه را تصویر میکنند.
شکل ۱۱.۴۳ نمای بالای حالت سادهشده را نشان میدهد؛ هر دو دوربین روی محور x قرار دارند و image planeهای آنها در z=d موازیاند. با معادلات استاندارد projection داریم:
\frac{x_1-x_{p1}}{d}=\frac{x_1-x}{z},\qquad
\frac{x_2-x_{p2}}{d}=\frac{x_2-x}{z}.
اینها دو معادلهٔ خطی در مجهولهای x و z هستند و میتوان آنها را حل کرد. اگر
\Delta x=x_2-x_1,\qquad \Delta x_p=x_{p2}-x_{p1},
آنگاه:
z=\frac{d\,\Delta x}{\Delta x-\Delta x_p},
و با جایگذاری در یکی از معادلهها، x نیز بهدست میآید. بنابراین نقطهٔ q را از دو تصویر تعیین کردهایم. این نتیجه به مکان خاص دوربینها محدود نیست؛ جابهجایی دوربینها فقط معادلات را پیچیدهتر میکند. پس از یافتن q میتوان آن را از هر دیدگاه دیگری تصویر کرد.
شکل ۱۱.۴۳ — نمای بالای دو دوربین.
اما در عمل مشکلاتی وجود دارد. نخست مشکل عددی: خطای کوچک در اندازهگیری محل دوربین میتواند خطای بزرگی در برآورد q بسازد. این مسئله بسیاری از کاربردهای سنتی مانند اندازهگیری terrain را دشوار کرده است. یک راه کاهش خطا استفاده از بیش از دو اندازهگیری و یافتن بهترین برآورد برای موقعیت موردنظر است.
مسئلهٔ جدی دیگر یافتن نقاط متناظر در دو تصویر است. با داشتن دو تصویر باید تشخیص دهیم کدام نقاط در تصویر اول و دوم به یک نقطهٔ فیزیکی تعلق دارند. این یکی از مسائل بنیادی computer vision است و راهحل کامل و عمومی ندارد. اگر occlusion وجود داشته باشد، ممکن است یک نقطه اصلاً در هر دو تصویر حضور نداشته باشد، همانگونه که شکل ۱۱.۴۴ نشان میدهد.
شکل ۱۱.۴۴ — تصویرسازی در حضور occlusion.
بسیاری از روشهای اولیه کاملاً image-based بودند و با روشهای آماری نقاط متناظر را پیدا میکردند. روشهای دیگر تعاملی بودند و از کاربر میخواستند نقاط متناظر را مشخص کند. در جامعهٔ computer graphics نیز راهکارهای تازهای ارائه شده است.
یک راه دورزدن مشکلات روشهای صرفاً تصویری استفاده از مدلهای هندسی بهجای نقاط منفرد برای registration است. مثلاً در یک محیط واقعی ممکن است بدانیم بسیاری از اشیا از parallelepipedهای قائم تشکیل شدهاند. این اطلاعات اضافی میتواند برای تعیین بسیار دقیق موقعیت استفاده شود.
یکی از کاربردهای image-based technique ساخت دیدهای تازه برای یک بیننده از توالی تصویرهاست؛ نمونههای آن در صنعت فیلم، virtual reality مانند Apple QuickTime VR و مشاهدهٔ اشیای دوردست دیده میشود.
گروه دیگری رابطهٔ ریاضی میان تصویرهای دوبعدی و توزیع نور در محیط سهبعدی را بررسی کردهاند. هر تصویر دوبعدی نمونهای از یک light field چهاربعدی است. مشابه بازسازی تصویر سهبعدی از projectionهای دوبعدی در CT، میتوان از projectionهای چند دوربین جهان سهبعدی را بازسازی کرد. دو روش معروف lumigraph و light-field rendering هستند. چون همهٔ اطلاعات صحنه در light field نهفته است، اندازهگیری آن اهمیت روبهرشد دارد؛ کاری که به دلیل حجم عظیم داده تا سالهای اخیر عملی نبود. یکی از کاربردهای جالب، relighting است: نور موجود در صحنه حذف میشود و صحنه با light field حاصل از منابعی در مکانهای دیگر دوباره روشن میشود.
جمعبندی و نکتهها
این فصل نشان داد که راههای زیادی برای رندر وجود دارد. پایهٔ فیزیکی رندر با global illumination در rendering equation نهفته است. متأسفانه این معادله برای حالت عمومی متغیرهای بسیار زیادی دارد و حتی با روشهای عددی نیز بهطور کامل حلپذیر نیست. radiosity و ray tracing هرکدام میتوانند برخی اثرهای global را پوشش دهند، اما دربارهٔ نوع سطحهای صحنه فرضهای تقریباً متضادی دارند. با قدرتمندترشدن GPUها، بخش بزرگی از محاسبات روشهای رندر جایگزین را میتوان روی آنها انجام داد؛ بنابراین ممکن است در کاربردهای بلادرنگ مرز میان رویکرد خط لولهای و روشهای دیگر کمتر شود.
افزایش سرعت و کاهش قیمت رایانهها امکان ray tracing و radiosity صحنههایی را فراهم کرده که چند سال پیش عملی نبود، اما هیچیک بهتنهایی پاسخ همهٔ مسائل گرافیک نیستند. صنعت فیلم، تلویزیون و بازی نشان میدهد تصاویر photorealistic را میتوان با مجموعهای بزرگ از روشهای مدلسازی و rendererهای تجاری یا shareware ساخت. در عین حال این دیدگاه پذیرفتهتر شده که photorealism هدف نهایی نیست؛ بنابراین علاقه به ترکیب رندر واقعگرایانه و مدلسازی رایانهای با پویانمایی دستی سنتی افزایش یافته است. روشهای image-based نیز با این کاربردها سازگاری خوبی دارند.
در سمت مصرفکننده، بخش زیادی از پیشرفت گرافیک را بازیهای رایانهای هدایت میکنند. هرقدر پردازندهها سریعتر و ارزانتر شوند، تقاضای بازیهای پیچیدهتر توسعهدهندگان را به ساخت پردازندههای سریعتر با قابلیتهای تازه سوق میدهد. با فراگیرشدن HDTV نیز نمایشگرهای با تفکیک بالاتر و قیمت مناسبتر بیشتر میشوند.
در کاربردهای علمی، جایگزینی supercomputerهای سنتی با clusterهای رایانههای عمومی اثر بزرگی بر scientific visualization خواهد داشت. مجموعهدادههای عظیم تولیدشده روی این clusterها توسعهٔ برنامههای گرافیکی را پیش میبرند. این برنامهها هم به تصویرهای مناسب نمایشگرهای با وضوح بالا نیاز دارند و هم به دلیل دشواری ذخیرهٔ داده، باید تا حد امکان داده را همزمان با تولید آن visualization کنند.
آیندهٔ معماری رایانه و اثر آن بر گرافیک روشنتر نیست. رایانههای عمومی مانند Apple MacPro چند bus برای چند کارت گرافیک و چند پردازندهٔ چندهستهای دارند. کنسولهای بازی نیز از اجزای متفاوتی مانند پردازندهٔ Cell شرکت IBM در Sony PlayStation 3 استفاده میکنند. بهترین روش استفاده از این اجزا هنوز مسئلهای باز است؛ اما تقریباً قطعی است که در گرافیک رایانهای کارهای فراوانی باقی مانده است.
منابع پیشنهادی
ray tracing را Appel [App68] معرفی کرد و Whitted [Whi80] آن را رواج داد. بسیاری از مقالههای اولیه در مجموعهٔ Joy و همکاران [Joy88] گردآوری شدهاند. کتاب Glassner [Gla89] برای کسانی که میخواهند ray tracer خود را بنویسند بسیار مفید است. آزمونهای تقاطع فراوانی در فصل Haines در [Gla89] و مجموعهٔ Graphics Gems [Gra90, Gra91, Gra92, Gra94, Gra95] آمدهاند. همچنین [Suf07] و [Shi03] را ببینید؛ ray tracerهای بسیار خوبی نیز در دسترساند، برای نمونه [War94].
Rendering Equation از Kajiya [Kaj86] است. radiosity بر روشی استوار است که نخست در انتقال حرارت [Sie81] بهکار رفت و Goral و همکاران [Gor84] آن را وارد computer graphics کردند.
پس از معرفی radiosity، پژوهشهای زیادی برای افزایش کارایی آن [Coh85, Coh88, Coh93] و واردکردن جملههای specular [Sil89] انجام شد. روش استفاده از point light source برای یافتن form factor در [Kel97] آمده و photon mapping را Jensen [Jen01] رواج داده است.
RenderMan Interface در [Ups89] توضیح داده شده و معماری Reyes نخست در [Coo87] ارائه شد. Maya [Wat02] اجازهٔ استفاده از چند نوع renderer را میدهد.
طبقهبندی sort برای parallel rendering را Molnar و همکاران [Mol94] پیشنهاد کردند. مزیتهای sort-middle در workstationهای سطح بالای SGI مانند Infinite Reality Graphics [Mon97] بهکار رفت. معماری sort-last بخشی از Pixel Flow [Mol92] بود و binary-swap compositing در [Ma94] پیشنهاد شد. نرمافزار sort-last روی clusterهای رایانهٔ عمومی در [Hum01] و power wallها در [Her00, Che00] بحث شدهاند.
marching squares حالت ویژهای از marching cubes است که Lorensen و Cline [Lor87] آن را رواج دادند. این روش چندبار مستقل از نو کشف شده است. مسئلهٔ ambiguity در [Van94] بررسی میشود. از کارهای اولیهٔ visualization حجم میتوان [Her79] و [Fuc77] را نام برد. volume ray tracing در [Lev88]، splatting در [Wes90] و استفاده از particle برای visualization در [Wit94a, Cro97] آمدهاند. روشهای دیگر در [Gal95, Nie97] و رویکرد toolkit شیءگرا در [Schr06] بحث شده است.
image-based rendering با warp کردن frameها بخشی از سختافزار Microsoft Talisman [Tor96] بود. Apple QuickTime VR [Che95] با panorama ۳۶۰ درجه از یک viewpoint، viewهای جدید میساخت. Debevec و همکاران [Deb96] نشان دادند با مدل هندسی میتوان از تعداد کمی تصویر، دیدهای جدید از viewpointهای مختلف ساخت. روشهای warp دیگر در [Sei96] و مبانی ریاضی lumigraph و light field در [Gor96, Lev96] آمدهاند. کاربردهای image-based lighting در [Rei05] بررسی شده است.
تمرینها
۱۱.۱ آزمونی طراحی کنید که مشخص کند یک نقطه داخل یک polygon محدب قرار دارد یا نه، با استفاده از این ایده که polygon را میتوان تقاطع مجموعهای از خطها در یک صفحه دانست.
۱۱.۲ الگوریتم تمرین ۱۱.۱ را به polyhedronهایی تعمیم دهید که از تقاطع صفحهها ساخته میشوند.
۱۱.۳ معادلهٔ ضمنی torus با مرکز مبدأ را استخراج کنید. راهنما: صفحهای که torus را قطع میکند دو دایرهٔ همشعاع نشان میدهد.
۱۱.۴ با نتیجهٔ تمرین ۱۱.۳ نشان دهید میتوان torus را ray trace کرد و با حل معادلهٔ مناسب تقاطعها را یافت.
۱۱.۵ rayای را در نظر بگیرید که از یک sphere عبور میکند. نزدیکترین نقطهٔ روی ray به مرکز sphere را پیدا کنید. راهنما: خطی از مرکز sphere عمود بر ray در نظر بگیرید. چگونه میتوان این نتیجه را برای آزمون تقاطع استفاده کرد؟
۱۱.۶ میتوان با rayهای بیشتر دقت ray tracer را افزایش داد. فرض کنید برای هر pixel یک ray از مرکز و چهار ray از گوشههای pixel بفرستیم. نسبت به ray tracer تک-ray-بهازای-هر-pixel چه مقدار کار بیشتری لازم است؟
۱۱.۷ در sort-middle parallel rendering چه نوع اطلاعاتی باید میان geometry processorها و raster processorها منتقل شود؟
۱۱.۸ اگر اشیای translucent را مجاز کنیم، چه تغییرهایی باید در راهبردهای parallel rendering ایجاد شود؟
۱۱.۹ یکی از روشهای طبقهبندی parallel computerها این است که memory میان processorها shared باشد یا distributed، بهگونهای که هر processor memory مستقل و غیرقابلدسترسی برای دیگران داشته باشد. این تفاوت چه اثری بر راهبردهای رندر بررسیشده دارد؟
۱۱.۱۰ مثال سادهٔ تصویرسازی یک نقطه از دو viewer را به حالت عمومی تعمیم دهید که دو viewer بتوانند در مکانهای دلخواه فضای سهبعدی باشند.
۱۱.۱۱ یک ray tracer ساده بسازید که فقط plane و sphere را پردازش کند. مجموعهدادههای جالب فراوانی برای آزمون چنین کدی وجود دارد.
۱۱.۱۲ تابع جبریای را در نظر بگیرید که بالاترین جملهٔ آن x^i y^j z^k است. درجهٔ polynomial لازم برای یافتن تقاطع ray با سطح تعریفشده توسط این تابع چیست؟
۱۱.۱۳ در همان تابع جبری، اگر i=j=k باشد، وقتی سطح را با ray پارامتری قطع میکنیم polynomial حاصل چند جمله دارد؟
۱۱.۱۴ برای یک یا چند پیادهسازی OpenGL تعداد triangle قابل رندر در ثانیه را پیدا کنید. سهم زمان hidden-surface removal، shading، texture mapping و rasterization را تعیین کنید. اگر کارت گرافیک عمومی استفاده میکنید، کارایی اندازهگیریشده با مشخصات اعلامشدهٔ کارت چه تفاوتی دارد؟
۱۱.۱۵ کارایی pixel کارت گرافیک خود را اندازهگیری کنید: چند pixel در ثانیه قابل خواندن یا نوشتن است؟ سرعت read و write متفاوت است؟ نوشتن texture map تفاوتی دارد؟
۱۱.۱۶ یک sort-last renderer بسازید که در هر processor از OpenGL استفاده کند. برای آزمون کارایی میتوانید برنامههایی تولیدکنندهٔ triangle یا triangular mesh بهکار ببرید.
۱۱.۱۷ توضیح دهید چرا با افزودن processorهای بیشتر، کارایی sort-first rendering در نهایت بدتر میشود.
۱۱.۱۸ تابع ضمنی دوبعدی f(x,y)=c را در نظر بگیرید. برای هر c، منحنیهای حاصل contourهای تابعاند. میتوان آنها را با marching squares، نسخهٔ دوبعدی marching cubes، نمایش داد. یک سلول مستطیلی و مقدار contour را در نظر بگیرید و هر گوشه را بسته به بیشتر یا کمتر بودن مقدار از c سیاه یا سفید کنید.
چند رنگآمیزی ممکن برای سلول وجود دارد؟ آیا در نحوهٔ عبور contourها از سلول ambiguity وجود دارد؟
۱۱.۱۹ یک برنامهٔ OpenGL برای اجرای marching squares بنویسید.