ضدهم‌پوشانی، رنگ، گاما، دیترینگ و تمرین‌های فصل ششم

دو وضعیت دشوار دیگر در Depth Sort باقی می‌ماند. اگر سه یا چند چندضلعی مانند شکل ۶٫۵۷ به‌صورت چرخه‌ای روی یکدیگر هم‌پوشانی داشته باشند، هیچ ترتیب درستی برای رسم کامل آن‌ها وجود ندارد. بهترین کار این است که دست‌کم یکی از چندضلعی‌ها را به دو بخش تقسیم کنیم و سپس تلاش کنیم برای مجموعهٔ جدید ترتیبی بیابیم.

شکل ۶٫۵۷ — هم‌پوشانی چرخه‌ای چندضلعی‌ها.

حالت مشکل‌ساز دوم زمانی رخ می‌دهد که یک چندضلعی بتواند از میان چندضلعی دیگر عبور کند، مانند شکل ۶٫۵۸. اگر بخواهیم همچنان از Depth Sort استفاده کنیم باید جزئیات تقاطع را محاسبه کنیم؛ محاسبه‌ای که عملاً معادل برش یک چندضلعی در برابر دیگری است. اگر چندضلعی‌های متقاطع رأس‌های زیادی داشته باشند، ممکن است بهتر باشد الگوریتم دیگری با هزینهٔ محاسباتی کمتر انتخاب شود.

شکل ۶٫۵۸ — چندضلعی‌هایی که یکدیگر را قطع می‌کنند.

تحلیل کارایی Depth Sort دشوار است، زیرا جزئیات کاربرد تعیین می‌کند حالت‌های دشوار با چه فراوانی رخ دهند. برای مثال، اگر چندضلعی‌ها سطوح اشیای جامد را توصیف کنند، دو چندضلعی مستقل نباید از یکدیگر عبور کنند. با این حال، روشن است که به علت مرتب‌سازی اولیه، پیچیدگی دست‌کم (O(k\log k)) است که k تعداد اشیاست.

۶٫۱۲ ضدهم‌پوشانی

پاره‌خط‌ها و یال‌های چندضلعی پس از رسترسازی دندانه‌دار دیده می‌شوند. حتی روی نمایشگری با وضوحی مانند (1024\times1280) نیز این نقص‌ها قابل مشاهده‌اند. چنین خطایی هر زمان رخ می‌دهد که بخواهیم نمایش پیوستهٔ یک شیء با وضوح نامتناهی را به تقریب نمونه‌برداری‌شده‌ای با وضوح محدود تبدیل کنیم. به دلیل ارتباط این پدیده با Aliasing در پردازش سیگنال دیجیتال، نام Aliasing برای آن به کار می‌رود.

خطاهای Aliasing از سه محدودیت مرتبط با ماهیت گسستهٔ بافر فریم ناشی می‌شوند. نخست، در بافر (n\times m) تعداد پیکسل‌ها ثابت است و فقط الگوهای معینی برای تقریب پاره‌خط می‌توان ساخت. پاره‌خط‌های پیوستهٔ متفاوت بسیاری ممکن است با یک الگوی یکسان پیکسل تقریب زده شوند؛ یعنی همهٔ آن‌ها به همان دنبالهٔ پیکسلی Alias می‌شوند و از روی دنبالهٔ پیکسل نمی‌توان پاره‌خط اولیه را به‌طور یکتا تشخیص داد. دوم، مکان پیکسل‌ها روی شبکه‌ای یکنواخت ثابت است و نمی‌توان آن‌ها را در مکان دلخواه قرار داد. سوم، اندازه و شکل پیکسل‌ها نیز ثابت است.

در نگاه نخست شاید به نظر برسد کاری از دست ما برنمی‌آید. الگوریتم‌هایی مانند Bresenham از این نظر بهینه‌اند که نزدیک‌ترین مجموعهٔ پیکسل‌ها را برای تقریب خط و یال انتخاب می‌کنند. اما اگر نمایشگر بیش از دو رنگ پشتیبانی کند، امکان‌های دیگری داریم. خط ریاضی یک موجودیت یک‌بعدی با طول و بدون عرض است، ولی خط رستری برای دیده‌شدن باید عرض داشته باشد. فرض کنید هر پیکسل به صورت مربع (1\times1) نمایش داده شود. می‌توان خط ایده‌آل رستری را نواری با عرض یک پیکسل دانست، مانند شکل ۶٫۵۹.

شکل ۶٫۵۹ — خط رستری ایده‌آل با عرض یک پیکسل.

این خط ایده‌آل را نمی‌توان دقیقاً با پیکسل‌های مربعی ساخت و Bresenham در واقع روشی برای تقریب آن است. برخی بافرهای فریم از طریق Multisampling امکان عملیات در واحدهایی کوچک‌تر از یک پیکسل را فراهم می‌کنند.

اگر خط ایده‌آل یک‌پیکسلی را دقیق نگاه کنیم، بسیاری از جعبه‌های هم‌اندازهٔ پیکسل را فقط به‌طور جزئی می‌پوشاند. الگوریتم تبدیل پیمایشی معمول برای خط با شیب کمتر از ۱ مجبورمان می‌کند برای هر x دقیقاً یک پیکسل را انتخاب کنیم. اگر به جای این تصمیم صفر/یک، شدت هر جعبه را متناسب با درصد سطحی قرار دهیم که خط ایده‌آل از آن عبور کرده است، تصویر نرم‌تر شکل ۶٫۶۰(ب) به دست می‌آید. این روش ضدهم‌پوشانی با میانگین‌گیری سطحی (Area Averaging) نامیده می‌شود و محاسبهٔ آن شباهت زیادی به برش چندضلعی دارد.

شکل ۶٫۶۰ — خط Aliasشده در برابر خط ضدهم‌پوشانی‌شده، همراه با بزرگ‌نمایی هر دو.

روش‌های دیگری نیز برای Antialiasing وجود دارند و می‌توان الگوریتم‌های ضدهم‌پوشانی را به بدوی‌های دیگر مانند چندضلعی‌ها تعمیم داد.

مسئله‌ای مرتبط نیز از شکل سادهٔ استفادهٔ ما از z-Buffer ناشی می‌شود. طبق الگوریتم پایه، رنگ یک پیکسل فقط از سایهٔ یک بدوی تعیین می‌شود. پیکسلی را در نظر بگیرید که سه چندضلعی شکل ۶٫۶۱ در آن سهم دارند. اگر هر چندضلعی رنگ متفاوتی داشته باشد، فقط رنگ چندضلعی نزدیک‌تر به بیننده به پیکسل اختصاص می‌یابد. تصویر دقیق‌تر زمانی به دست می‌آید که رنگ بر اساس میانگین وزن‌دار سطحی رنگ هر سه مثلث تعیین شود. چنین الگوریتم‌هایی را می‌توان با Fragment Shader روی سخت‌افزار دارای بافر فریم ممیز شناور پیاده‌سازی کرد.

شکل ۶٫۶۱ — سه چندضلعی که در یک پیکسل مشترک سهم دارند.

تا اینجا فقط Aliasing حوزهٔ مکانی را بررسی کرده‌ایم. هنگام تولید دنبالهٔ تصاویر، مانند پویانمایی، باید به Aliasing حوزهٔ زمانی نیز توجه کنیم. شیء کوچکی را در نظر بگیرید که مقابل صفحهٔ تصویر حرکت می‌کند و صفحه به واحدهای هم‌اندازهٔ پیکسل تقسیم شده است. اگر رندر برای هر پیکسل فقط یک پرتو از مرکز آن بفرستد، گاهی پرتو به شیء برخورد می‌کند و گاهی—وقتی تصویر شیء بسیار کوچک است—از کنار آن می‌گذرد. در نتیجه شیء هنگام حرکت به شکل ناخوشایندی چشمک می‌زند و ظاهر و ناپدید می‌شود.

یک راه‌حل استفاده از بیش از یک پرتو برای هر پیکسل است؛ روشی رایج در رهگیری پرتو. وجه مشترک همهٔ تکنیک‌های ضدهم‌پوشانی این است که نسبت به رندر بدون Antialiasing محاسبهٔ بسیار بیشتری نیاز دارند. در عمل، برای تصاویر با وضوح بالا گاهی Antialiasing به‌صورت آفلاین و فقط برای تصویر نهایی انجام می‌شود.

شکل ۶٫۶۲ — Aliasing حوزهٔ زمانی؛ شیء کوچک در برخی نمونه‌های زمانی دیده و در برخی از دست می‌رود.

۶٫۱۳ ملاحظات نمایش

در بیشتر کاربردهای تعاملی، برنامه‌نویس لازم نیست نگران شیوهٔ نمایش محتوای بافر فریم باشد. از دید برنامه‌نویس، تا زمانی که از Double Buffering استفاده شود، فرایند نوشتن در بافر فریم از فرایند خواندن آن برای نمایش جداست. سخت‌افزار محتوای فعلی بافر فریم را با نرخی کافی برای جلوگیری از Flicker—معمولاً حدود ۶۰ تا ۸۵ هرتز—بازنمایش می‌کند و نگرانی برنامه‌نویس فقط این است که آیا برنامه می‌تواند با سرعت کافی اجرا و بافر فریم را پُر کند یا نه. همان‌طور که در فصل ۲ دیدیم، Double Buffering اجازه می‌دهد نمایش به‌نرمی تغییر کند حتی اگر نتوانیم بدوی‌ها را با سرعت دلخواه از سامانه عبور دهیم.

عوامل متعدد دیگری نیز بر کیفیت نمایش اثر می‌گذارند. برای مثال، دو مانیتور ممکن است وضوح اسمی یکسانی داشته باشند اما اندازهٔ فیزیکی پیکسل‌هایشان متفاوت باشد.

شاید بزرگ‌ترین منبع مشکل، ویژگی‌های فیزیکی خود نمایشگر باشد: دامنهٔ رنگ‌هایی که می‌تواند تولید کند و نحوهٔ نگاشت رنگ‌های تعریف‌شده در نرم‌افزار به مقادیر رنگ‌های اصلی نمایشگر. Color Gamut نمایشگرهای مختلف می‌تواند بسیار متفاوت باشد. همچنین چون رنگ‌های اصلی در سامانه‌های متفاوت یکسان نیستند، حتی اگر دو مانیتور توان تولید یک رنگ ظاهری مشترک را داشته باشند ممکن است برای ایجاد آن به مقادیر متفاوتی از Primaryها نیاز داشته باشند. افزون بر این، نگاشت میان مقدار روشنایی تعریف‌شده توسط برنامه و روشنایی واقعاً نمایش‌داده‌شده غیرخطی است.

OpenGL مستقیماً این مسائل را حل نمی‌کند، زیرا رنگ‌ها را به صورت مقادیر RGB مستقل از ویژگی‌های نمایشگر مشخص می‌کند. همچنین چون مؤلفه‌های RGB به بازهٔ ۰٫۰ تا ۱٫۰ محدودند، بازنمایی کامل دامنهٔ رنگ و روشنایی قابل درک توسط دستگاه بینایی انسان دشوار است. با گسترش بحث رنگ و بینایی انسانی فصل ۲، می‌توان کنترل بیشتری بر رنگ در OpenGL به دست آورد.

۶٫۱۳٫۱ سامانه‌های رنگ

فرض بنیادی ما دربارهٔ رنگ، که نظریهٔ سه‌رنگی بینایی انسان از آن پشتیبانی می‌کند، این است که سه مقدار رنگی تعیین‌شده برای هر پیکسل متناظر با مقادیر Tristimulus فصل ۲ هستند. بنابراین یک رنگ نقطه‌ای در مکعب رنگ شکل ۶٫۶۳ است و می‌توان آن را نمادین نوشت:

شکل ۶٫۶۳ — مکعب رنگ و نمایش یک رنگ با سه مؤلفهٔ Tristimulus.

با این حال میان سامانه‌های RGB تفاوت‌های مهمی وجود دارد. فرض کنید OpenGL رنگ زردی را با سه‌تایی RGB برابر ((0.8,0.6,0.0)) نمایش دهد. اگر همین مقادیر را هم به یک CRT و هم به ثبت‌کنندهٔ تصویر فیلم بدهیم، رنگ‌های متفاوتی دیده می‌شوند؛ با اینکه در هر دو مورد قرمز ۸۰ درصد بیشینه، سبز ۶۰ درصد و آبی صفر است. علت آن است که رنگدانه‌های فیلم و فسفرهای CRT توزیع طیفی متفاوت دارند و در نتیجه دامنهٔ رنگ قابل نمایش آن‌ها یکسان نیست.

تأکید تاریخی جامعهٔ گرافیک بر گرافیک مستقل از دستگاه بوده است و به همین دلیل بیشتر APIها تفاوت‌های واقعی خواص نمایشگر را مستقیماً مدل نمی‌کنند. خوشبختانه ادبیات Colorimetry اطلاعات لازم را در اختیار می‌گذارد و برای بسیاری از سامانه‌های رنگ استانداردهایی وجود دارد. برای مثال، CRTها بر پایهٔ سامانهٔ RGB استاندارد NTSC مدل می‌شوند.

می‌توان تفاوت سامانه‌های رنگ را مانند تفاوت دستگاه‌های مختصات برای نمایش یک بردار Tristimulus دید. اگر (C_1=[R_1,G_1,B_1]^T) و (C_2=[R_2,G_2,B_2]^T) نمایش یک رنگ واحد در دو سامانه باشند، ماتریس تبدیل رنگ (3\times3)ای به نام M وجود دارد که:

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

حتی این رویکرد نیز مشکلات بالقوه‌ای دارد. نخست، Color Gamut دو سامانه ممکن است برابر نباشد؛ بنابراین پس از تبدیل Tristimulus نیز ممکن است رنگی در یکی از سامانه‌ها اصولاً قابل تولید نباشد. دوم، صنعت چاپ و هنرهای گرافیکی از سامانهٔ کاهشی چهاررنگی CMYK استفاده می‌کند که سیاه (K) را به‌عنوان Primary چهارم اضافه می‌کند. تبدیل میان RGB و CMYK اغلب به تجربه و تخصص انسانی نیاز دارد. سوم، نظریهٔ خطی رنگ محدودیت‌هایی دارد: فاصلهٔ هندسی دو رنگ در مکعب رنگ الزاماً بیانگر فاصلهٔ ادراکی آن‌ها نیست. برای مثال، انسان نسبت به تغییرات رنگ در برخی نواحی طیف حساسیت بیشتری دارد. سامانه‌هایی مانند YUV و CIE Lab برای پرداختن به این مسائل ایجاد شده‌اند.

بیشتر سامانه‌های RGB بر Primaryهای سامانه‌های واقعی مانند فسفر CRT یا رنگدانهٔ فیلم متکی‌اند و هیچ‌کدام نمی‌توانند تمام رنگ‌های قابل رؤیت انسان را تولید کنند. بسیاری از استانداردهای رنگ بر سامانهٔ نظری سه‌Primary به نام XYZ بنا شده‌اند که در آن مؤلفهٔ Y متناظر با Luminance است. در سامانهٔ XYZ همهٔ رنگ‌ها را می‌توان با مقادیر Tristimulus مثبت مشخص کرد. برای تبدیل نمایش XYZ به سامانه‌های استاندارد، از ماتریس‌های (3\times3) استفاده می‌شود.

متخصصان رنگ اغلب ترجیح می‌دهند به جای مقادیر Tristimulus با مختصات Chromaticity کار کنند. Chromaticity یک رنگ از نسبت سهم سه Primary تشکیل می‌شود. اگر مقادیر Tristimulus یک رنگ RGB برابر (T_1,T_2,T_3) باشند:

از جمع سه رابطه داریم:

بنابراین می‌توان در فضای دوبعدی (t_1,t_2) کار کرد و فقط هنگام نیاز (t_3) را محاسبه نمود. اطلاعاتی که در Chromaticity نسبت به Tristimulus حذف می‌شود مجموع (T_1+T_2+T_3) است؛ مقداری مرتبط با شدت رنگ. در بسیاری از مسائل تطبیق رنگ بین سامانه‌ها، این شدت عامل اصلی نیست.

چون سهم هر Primary باید نامنفی باشد، مختصات Chromaticity در بازهٔ زیر قرار می‌گیرند:

همهٔ رنگ‌های قابل تولید باید داخل مثلث شکل ۶٫۶۴ قرار گیرند.

شکل ۶٫۶۴ — مثلث رنگ‌های قابل تولید در مختصات Chromaticity.

شکل ۶٫۶۵ این مثلث را برای سامانهٔ XYZ همراه با منحنی نمایش هر خط طیفی قابل رؤیت نشان می‌دهد. در سامانهٔ XYZ این منحنی باید داخل مثلث قرار گیرد. شکل همچنین دامنهٔ رنگ‌هایی را در مختصات Chromaticity ((x,y)) نشان می‌دهد که یک چاپگر رنگی یا CRT معمولی قادر به تولید آن است. با مقایسهٔ دو ناحیه روشن می‌شود رنگ‌هایی که داخل منحنی طیف قابل رؤیت اما بیرون Gamut دستگاه فیزیکی‌اند، روی آن دستگاه قابل نمایش نیستند.

شکل ۶٫۶۵ — رنگ‌های قابل رؤیت در برابر Color Gamut یک نمایشگر فیزیکی.

یکی از کاستی‌های رویکرد RGB این است که بر نحوهٔ تولید و اندازه‌گیری رنگ بنا شده، نه بر نحوهٔ ادراک آن. انسان هنگام دیدن یک رنگ معمولاً آن را با سه مقدار Primary توصیف نمی‌کند، بلکه از ویژگی‌هایی مانند نام رنگ و میزان روشنایی ادراک‌شده استفاده می‌کند.

سامانهٔ Hue–Lightness–Saturation (HLS) در میان هنرمندان و برخی سازندگان نمایشگر رایج است. Hue نامی است که به رنگ می‌دهیم، مانند قرمز، زرد یا طلایی. Lightness میزان روشن به نظر رسیدن رنگ است. Saturation مشخص می‌کند یک رنگ تا چه اندازه خالص است یا با سفید آمیخته و به سایه‌ای Pastel تبدیل شده است.

این ویژگی‌ها را می‌توان به مکعب RGB مرتبط کرد. برای نقطه‌ای در مکعب رنگ، Lightness معیاری از فاصله از مبدأ یا سیاه است. همهٔ رنگ‌های روی قطر اصلی مکعب از سیاه تا سفید سایه‌های خاکستری و کاملاً Unsaturated هستند؛ بنابراین Saturation را می‌توان معیاری از فاصلهٔ رنگ تا این قطر دانست. Hue نیز جهت بردار رنگ را بیان می‌کند. رنگ‌های HLS معمولاً با مخروط رنگ، یا مخروط دوتایی، نمایش داده می‌شوند. از دید ریاضی، می‌توان HLS را نوعی نمایش قطبی برای رنگ RGB دانست.

شکل ۶٫۶۶ — رنگ Hue–Lightness–Saturation: (الف) تفسیر در مکعب RGB؛ (ب) نمایش مخروطی.

۶٫۱۳٫۲ ماتریس رنگ

رنگ‌های RGB و RGBA مانند هر نوع بردار دیگری قابل دست‌کاری‌اند. به‌ویژه می‌توان مؤلفه‌های آن‌ها را با ضرب در ماتریس رنگ تغییر داد. در نمایش RGBA، تبدیل یک رنگ ([r,g,b,a]^T) به رنگ جدید ([r',g',b',a']^T) با ماتریس C به صورت زیر است:

برای سطوح مات که (A=1) دارند، ماتریس مناسب می‌تواند نمایش افزایشی رنگ را به نمایش کاهشی آن تبدیل کند.

برای نمونه:

۶٫۱۳٫۳ تصحیح گاما

در فصل ۲، روشنایی را شدت ادراک‌شده تعریف کردیم و دیدیم دستگاه بینایی انسان شدت را تقریباً به‌صورت لگاریتمی درک می‌کند (شکل ۶٫۶۷). یکی از پیامدهای این ویژگی آن است که اگر بخواهیم گام‌های روشنایی از نظر ادراکی یکنواخت به نظر برسند، شدت‌هایی که به پیکسل‌ها نسبت می‌دهیم باید به‌صورت نمایی افزایش یابند. این گام‌ها را می‌توان از کمینه و بیشینهٔ شدت قابل تولید نمایشگر محاسبه کرد.

شکل ۶٫۶۷ — رابطهٔ لگاریتمی میان شدت فیزیکی و روشنایی ادراک‌شده.

افزون بر این، شدت I در CRT با ولتاژ V تقریباً رابطهٔ زیر را دارد:

یا:

که در آن (\gamma) و (c_0) ویژگی‌های همان CRT هستند. بنابراین دو مانیتور ممکن است برای یک مقدار یکسان در بافر فریم روشنایی متفاوتی ایجاد کنند. یکی از راه‌های اصلاح، استفاده از Lookup Table قابل تنظیم در مسیر نمایش است که ویژگی‌های همان مانیتور را جبران کند؛ این همان Gamma Correction است.

CRTها مشکل دیگری نیز دارند: نمی‌توان به روشنایی کاملاً صفر رسید حتی وقتی هیچ سیگنالی اعمال نمی‌شود. کمینهٔ شدت نمایش‌داده‌شده Dark Field Value نامیده می‌شود و به‌ویژه در پروژکتورهای مبتنی بر CRT مسئله‌ساز است. نسبت کنتراست نمایشگر نسبت بیشینهٔ روشنایی به کمینهٔ روشنایی است. فناوری‌های جدیدتر نسبت‌های کنتراست بسیار بالاتری دارند.

۶٫۱۳٫۴ Dithering و Halftoning

یک بافر رنگی را با وضوح مکانی—تعداد پیکسل‌ها—و دقت رنگ—تعداد رنگ‌های قابل نمایش—توصیف کرده‌ایم. اگر این دو را ثابت فرض کنیم، چاپگر لیزری سیاه‌وسفید با وضوح بالا فقط پیکسل ۱ بیتی دارد. اما تجربه نشان می‌دهد رسانهٔ سیاه‌وسفید مانند کتاب می‌تواند تصاویر دارای سایه‌های خاکستری متعدد را نمایش دهد. ترفند اصلی، مبادلهٔ بخشی از وضوح مکانی با دقت GrayScale یا رنگ است.

روش‌های Halftoning در صنعت چاپ با ابزارهای عکاسی سطوح خاکستری را از طریق الگوهای نقاط سیاه با اندازه‌های متفاوت شبیه‌سازی می‌کنند.

دستگاه بینایی انسان نقاط کوچک را با هم ادغام می‌کند و به جای مشاهدهٔ تک‌تک نقاط، شدتی متناسب با نسبت سفید به سیاه در یک ناحیهٔ کوچک می‌بیند.

Halftone دیجیتال متفاوت است، زیرا اندازه و مکان پیکسل‌ها ثابت است. یک بلوک (4\times4) از پیکسل‌های ۱ بیتی را در نظر بگیرید. از فاصلهٔ دور، پیکسل‌های منفرد دیده نمی‌شوند و یک سطح خاکستری بر پایهٔ تعداد پیکسل‌های سیاه ادراک می‌شود. در این مثال با وجود (2^{16}) الگوی ممکن سیاه/سفید، فقط ۱۷ سطح روشنایی بر اساس ۰ تا ۱۶ پیکسل سیاه وجود دارد. الگوریتم‌های متعددی برای تولید الگوهای Halftone یا Dither وجود دارند. ساده‌ترین الگوریتم ۱۷ الگو را انتخاب می‌کند تا به جای دو سطح، ۱۷ سطح خاکستری ایجاد شود؛ البته وضوح مکانی در هر بعد به میزان ۴ کاهش می‌یابد.

شکل ۶٫۶۸ — نمونه‌هایی از الگوهای Halftone دیجیتال.

الگوریتم ساده‌ای که همیشه برای هر سایه از همان آرایه استفاده می‌کند، هنگام نمایش ساختارهای منظم می‌تواند الگوهای Beat یا Moiré ایجاد کند. این الگوها هر زمان دو پدیدهٔ تناوبی روی هم قرار گیرند ظاهر می‌شوند، زیرا مؤلفه‌هایی متناظر با جمع و تفاضل فرکانس‌ها دیده می‌شود. این اثرها با مسائل Aliasing مرتبط‌اند.

بسیاری از روش‌های Dithering بر تصادفی‌کردن Least Significant Bit مؤلفهٔ Luminance یا هر مؤلفهٔ رنگ تکیه دارند. روش‌های پیشرفته‌تر تصادفی‌سازی را به‌گونه‌ای استفاده می‌کنند که ویژگی متوسط درست حفظ شود اما تکرار منظم و در نتیجه Moiré کاهش یابد.

Halftoning یا Dithering اغلب برای رنگ نیز استفاده می‌شود، به‌ویژه در دستگاه‌های Hard-Copy مانند چاپگر جوهرافشان که هر Primary را فقط کاملاً روشن یا خاموش می‌کنند. هر Primary می‌تواند جداگانه Dither شود تا رنگ‌های بصری بیشتری ساخته شوند. OpenGL چنین نمایشگرهایی را پشتیبانی می‌کند و کاربر می‌تواند Dithering را فعال کند:

glEnable(GL_DITHER);

Dithering رنگی به مانیتور اجازه می‌دهد با تعداد محدود بیت در هر مؤلفه، تغییرات رنگ نرم‌تری ایجاد کند و در نتیجه حافظهٔ بافر فریم کاهش یابد. در بسیاری از کاربردها باید با تابع پرس‌وجوی glGetIntegerv تعداد بیت‌های هر رنگ را مشخص کنیم، زیرا هنگام خواندن پیکسل‌ها از بافر فریم مهم است. اگر Dithering فعال باشد، پیکسل‌هایی که با مقادیر RGB یکسان نوشته شده‌اند ممکن است هنگام خواندن مقادیر اندکی متفاوت بازگردانند. اگر این اختلاف‌های کوچک مهم‌اند، Dithering باید پیش از خواندن بافر فریم غیرفعال شود.

جمع‌بندی و یادداشت‌ها

در این فصل نمایی کلی از فرایند پیاده‌سازی همراه با نمونه‌ای از مهم‌ترین الگوریتم‌ها ارائه شد. مستقل از جزئیات پیاده‌سازی—سخت‌افزاری یا نرم‌افزاری بودن وظایف، استفاده از ایستگاه کاری تخصصی یا پایانهٔ ساده، و نوع API—وظایف بنیادین یکسان‌اند: تبدیل‌های هندسی، برش و رسترسازی. رابطهٔ میان سخت‌افزار، نرم‌افزار و API نیز نقش مهمی دارد.

Geometry Engine که پایهٔ بسیاری از ایستگاه‌های کاری Silicon Graphics بود، تراشهٔ VLSIای بود که تبدیل‌های هندسی و برش را در یک خط لولهٔ سخت‌افزاری انجام می‌داد. GL، پیش‌ساز OpenGL، به‌عنوان API کاربران همین ایستگاه‌های کاری توسعه یافت. بخش زیادی از ادبیات OpenGL نیز دیدگاه خط لوله‌ای دارد. با این حال باید به یاد داشت که OpenGL یک API است و دربارهٔ پیاده‌سازی زیرین چیزی الزام نمی‌کند. از نظر اصولی، تصویری تعریف‌شده با برنامهٔ OpenGL حتی می‌تواند به وسیلهٔ یک Ray Tracer تولید شود.

از تأکید بر معماری خط لوله‌ای دو نتیجه مهم می‌گیریم. نخست، این معماری به برنامه‌نویس کاربردی کمک می‌کند فرایند ساخت تصویر را بهتر درک کند. دوم، در معماری‌های امروزی همین دیدگاه می‌تواند به پیاده‌سازی‌های سخت‌افزاری و نرم‌افزاری بسیار کارآمد منجر شود.

z-Buffer نمونهٔ خوبی از رابطهٔ سخت‌افزار و نرم‌افزار است. در گذشته الگوریتم‌های متنوعی برای حذف سطح پنهان استفاده می‌شدند و z-Buffer فقط یکی از آن‌ها بود. فراهم‌شدن حافظهٔ سریع، متراکم و ارزان باعث شد z-Buffer به روش غالب تبدیل شود.

نمونهٔ مرتبط دیگر معماری ایستگاه‌های کاری است که در آن تراشه‌های گرافیکی ویژه‌منظوره پیشرفت خیره‌کننده‌ای داشته‌اند. کارایی گرافیکی حتی سریع‌تر از نرخ سنتی Moore رشد کرده و قابلیت‌های جدید بسیاری به GPUها افزوده شده است. رویکرد کل این کتاب بر همین معماری‌ها تکیه دارد.

در آینده نیز سامانه‌های گرافیکی سریع‌تر و ارزان‌تر خواهند شد و بیش از هر عامل دیگر، پیشرفت سخت‌افزار شکل آن‌ها را تعیین خواهد کرد. در زمان نگارش کتاب، توسعهٔ سخت‌افزار به‌شدت تحت تأثیر صنعت بازی‌های ویدیویی بود؛ کارت گرافیکی ارزان‌قیمت می‌توانست از ایستگاه‌های کاری گرافیکی بسیار گرانِ چند سال قبل سریع‌تر باشد. قابلیت و کارایی این کارت‌ها برای نیازهای بازی بهینه می‌شوند، بنابراین همهٔ توابع گرافیکی به یک نسبت سریع نمی‌شوند و ویژگی‌های جدید سخت‌افزار نیز سریع‌تر از آن ظاهر می‌شوند که APIهای استاندارد بتوانند فوراً آن‌ها را جذب کنند. در عوض همین سرعت پردازنده‌ها جامعهٔ گرافیک و محاسبات علمی را وادار کرده الگوریتم‌های تازه‌ای برای مسائلی پیدا کنند که پیش‌تر فقط با معماری‌های متعارف حل می‌شدند.

در سوی نرم‌افزار، ارزانی و سرعت سخت‌افزار جدید به توسعه‌دهندگان اجازه داده نرم‌افزارهایی بسازند که میان زمان رندر و کیفیت آن مصالحهٔ قابل کنترل ارائه می‌کنند؛ مثلاً کاربر می‌تواند متناسب با زمانی که حاضر است منتظر بماند، تعدادی شیء Ray-Traced به صحنه اضافه کند.

آیندهٔ APIهای استاندارد روشن‌تر نیست. از یک سو کاربران علمی API پایدار می‌خواهند تا کدهای کاربردی عمر طولانی داشته باشند و از سوی دیگر می‌خواهند از ویژگی‌های تازهٔ سخت‌افزار که روی همهٔ سامانه‌ها موجود نیست استفاده کنند. OpenGL تلاش کرده راه میانه‌ای انتخاب کند. تا OpenGL 3.1 انتشارها با نسخه‌های قبل سازگار بودند؛ از OpenGL 3.1 به بعد بسیاری از ویژگی‌های Core قدیمی، از جمله Immediate Mode و بخش بزرگی از رفتار پیش‌فرض Fixed-Function Pipeline، Deprecated شدند. این تغییر فلسفه پیامدهای مهمی برای برنامه‌نویسی OpenGL داشت.

این تغییر به OpenGL اجازه داد ویژگی‌های تازهٔ سخت‌افزاری را سریع‌تر جذب کند. برای اجرای کدهای قدیمی، تقریباً همهٔ پیاده‌سازی‌ها یک Compatibility Extension شامل توابع Deprecated ارائه می‌کنند.

معماری‌های پیشرفتهٔ متعددی که بررسی می‌شوند از موازی‌سازی عظیم استفاده می‌کنند. اینکه چگونه می‌توان Parallelism را مؤثرترین شکل در گرافیک رایانه‌ای به کار گرفت هنوز مسئله‌ای باز است. دو رویکرد رندر ما—شیءمحور و تصویرمحور—به دو روش کاملاً متفاوت برای ساخت رندرکنندهٔ موازی منجر می‌شوند؛ این موضوع در فصل ۱۱ بیشتر بررسی خواهد شد.

در این فصل فقط سطح پیاده‌سازی را خراش داده‌ایم. ادبیات گرافیک برای تقریباً هر بخش از فرایند پیاده‌سازی سرشار از الگوریتم است و منابع پیشنهادی مسیر مطالعهٔ بیشتر را نشان می‌دهند.

منابع پیشنهادی

کتاب Rogers [Rog85] و کتاب Foley و همکاران [Fol90] الگوریتم‌های بسیار بیشتری از آنچه در این فصل می‌گنجد ارائه می‌کنند. مجموعه‌های Graphics Gems [Gra90, Gra91, Gra92, Gra94, Gra95] و GPU Gems [Ngu07, Pha05] نیز منابع مهمی هستند. کتاب‌های Möller و Haines [Mol02] و Eberly [Ebe01] تأثیر پیشرفت‌های سخت‌افزاری جدید را پوشش می‌دهند.

الگوریتم برش Cohen–Sutherland [Sut63] به سال‌های نخست گرافیک رایانه‌ای بازمی‌گردد، همانند الگوریتم Bresenham [Bre63, Bre87] که در اصل برای Plotterهای قلمی پیشنهاد شد. برای Clipperهای Liang–Barsky و Sutherland–Hodgeman به [Lia84] و [Sut74a] مراجعه کنید.

الگوریتم‌های Triangulation در منابع Computational Geometry یافت می‌شوند؛ برای نمونه de Berg [deB08] که Delaunay Triangulation فصل ۱۰ را نیز بررسی می‌کند. الگوریتم z-Buffer توسط Catmull [Cat75] توسعه یافت و Sutherland [Sut74b] دیدگاه‌های مختلف حذف سطح پنهان را بررسی کرده است.

پرهیز ما از جزئیات سخت‌افزار به معنای ساده یا کم‌اهمیت بودن سخت‌افزار نیست. نرخ نمایش موجودیت‌های گرافیکی در GPU مدرن نیازمند طراحی‌های بسیار پیچیده و هوشمند است [Cla82, Ake88, Ake93]. بحث Molnar و Fuchs در [Fol90] نیز رویکردهای متنوعی نشان می‌دهد.

Pratt [Pra78] ماتریس‌های تبدیل میان سامانه‌های رنگ را ارائه کرده است. Halftone و Dithering نیز در Jarvis [Jar76] و Knuth [Knu87] بحث شده‌اند.

تمرین‌ها

۶٫۱

دو پاره‌خط را در فرم پارامتری در نظر بگیرید:

روشی برای تعیین اینکه آیا دو پاره‌خط با هم تقاطع دارند یا نه پیدا کنید و در صورت وجود تقاطع، نقطهٔ آن را محاسبه کنید.

۶٫۲

استدلال تمرین ۶٫۱ را گسترش دهید و روشی برای تعیین تقاطع دو چندضلعی تخت ارائه کنید.

۶٫۳

اثبات کنید برش یک شیء محدب در برابر شیء محدب دیگر حداکثر یک شیء محدب ایجاد می‌کند.

۶٫۴

رویکردهای تصویرمحور و شیءمحور پیاده‌سازی را به چه روش‌هایی می‌توان موازی کرد؟

۶٫۵

چون نرمال‌ها و رأس‌ها هر دو را می‌توان در مختصات همگن نمایش داد، هر دو تحت تبدیل Model-View قرار می‌گیرند. نشان دهید که نرمال‌ها ممکن است توسط این تبدیل حفظ نشوند.

۶٫۶

تبدیل Viewport را استخراج کنید و آن را بر حسب ماتریس‌های سه‌بعدی Scale و Translation که برای نمایش تبدیل‌های Affine دوبعدی استفاده می‌شوند بیان نمایید.

۶٫۷

سامانه‌های پیشارستری فقط قادر به نمایش خط بودند. برنامه‌نویسان برای ساخت تصویر سه‌بعدی از تکنیک‌های حذف خط پنهان استفاده می‌کردند. بسیاری از APIهای امروزی نیز امکان تولید تصاویر Wireframe شامل فقط خطوط را می‌دهند که خطوط تعریف‌کنندهٔ سطوح نامرئی حذف شده‌اند. این مسئله چه تفاوتی با حذف سطح پنهان چندضلعی دارد؟ الگوریتمی برای حذف خطوط پنهان در اشیایی متشکل از یال‌های چندضلعی‌های تخت استخراج کنید.

۶٫۸

اغلب توابع (y=f(x,z)) را با نمایش یک Mesh مستطیلی تولیدشده از مجموعهٔ ({f(x_i,z_j)}) در فواصل منظم x و z نمایش می‌دهیم. چون برخی بخش‌های سطح می‌توانند بخش‌های دیگر را بپوشانند، حذف سطح پنهان لازم است. دو الگوریتم برای نمایش چنین Meshای ارائه کنید: یکی مبتنی بر حذف سطح پنهان و دیگری مبتنی بر حذف خط پنهان.

۶٫۹

با اینکه استدلال کردیم پیچیدگی رویکرد فضای تصویر برای حذف سطح پنهان با تعداد چندضلعی‌ها متناسب است، مطالعات کارایی اغلب عملکرد تقریباً ثابتی گزارش می‌کنند. علت را توضیح دهید.

۶٫۱۰

صحنه‌ای را در نظر بگیرید که فقط از چندوجهی‌های جامد سه‌بعدی تشکیل شده است. آیا می‌توانید الگوریتم فضای شیء برای حذف سطح پنهان ارائه کنید؟ اگر بدانید همهٔ چندوجهی‌ها محدب‌اند چه مقدار کمک می‌کند؟

۶٫۱۱

رویکردهای فضای شیء حذف سطح پنهان را می‌توان مشابه الگوریتم‌های مرتب‌سازی دانست، اما برای آن‌ها پیچیدگی (O(k^2)) مطرح کردیم، در حالی که بیشتر مرتب‌سازی‌های خوب (O(k\log k)) هستند. آیا نتیجه می‌شود الگوریتم‌های فضای شیء حذف سطح پنهان نیز همین پیچیدگی را دارند؟ پاسخ را توضیح دهید.

۶٫۱۲

روشی برای آزمون اینکه آیا یک چندضلعی تخت کاملاً در یک سمت چندضلعی تخت دیگر قرار دارد طراحی کنید.

۶٫۱۳

تفاوت رویکردهای فضای تصویر حذف سطح پنهان با رهگیری پرتو چیست؟ آیا می‌توان Ray Tracing را به‌عنوان جایگزین حذف سطح پنهان استفاده کرد؟ مزایا و معایب آن چیست؟

۶٫۱۴

برنامه‌ای بنویسید که مکان پیکسل‌های یک پاره‌خط رستری را با الگوریتم Bresenham تولید کند. بررسی کنید برای همهٔ شیب‌ها و همهٔ مکان‌های ممکن دو انتها درست کار کند. مقدار اولیهٔ متغیر تصمیم چیست؟

۶٫۱۵

الگوریتم Bresenham را می‌توان به دایره گسترش داد. با درنظرگرفتن دایره‌ای با مرکز مبدأ این موضوع را بررسی کنید. کدام بخش‌های دایره باید مستقیماً توسط الگوریتم تولید شوند و کدام بخش‌ها از تقارن به دست می‌آیند؟ آیا می‌توانید ناحیه‌ای از دایره پیدا کنید که با دانستن یک نقطهٔ تولیدشده توسط Scan Conversion، تعداد نامزدهای پیکسل بعدی کاهش یابد؟

۶٫۱۶

نشان دهید چگونه می‌توان با Flood Fill هزارتویی مشابه تمرین ۲٫۷ تولید کرد.

۶٫۱۷

فرض کنید Flood Fill را با تبدیل پیمایشی مرز منحنی و سپس اجرای همان الگوریتم پُرکردن چندضلعی به منحنی بستهٔ دلخواه گسترش دهیم. چه مشکلاتی ممکن است رخ دهد؟

۶٫۱۸

یال چندضلعی بین رأس‌های ((x_1,y_1)) و ((x_2,y_2)) را در نظر بگیرید. الگوریتمی کارآمد برای محاسبهٔ تقاطع همهٔ Scanlineها با این یال استخراج کنید. فرض کنید در مختصات پنجره کار می‌کنید.

۶٫۱۹

یال‌های عمودی و افقی می‌توانند برای الگوریتم‌های Polygon Fill مشکل ایجاد کنند. در الگوریتم‌های معرفی‌شده این حالت‌ها را چگونه مدیریت می‌کنید؟

۶٫۲۰

در گرافیک دوبعدی، اگر دو چندضلعی هم‌پوشانی داشته باشند می‌توان با اختصاص Priority به هر چندضلعی تضمین کرد همهٔ پیاده‌سازی‌ها آن‌ها را با ترتیب یکسان رندر کنند. چندضلعی‌ها به ترتیب معکوس Priority رندر می‌شوند؛ یعنی بالاترین Priority در آخر رسم می‌شود. الگوریتم‌های Fill را چگونه باید برای درنظرگرفتن Priority اصلاح کرد؟

۶٫۲۱

یک تکنیک استاندارد Antialiasing در Ray Tracing این است که علاوه بر مرکز هر پیکسل، از چهار گوشهٔ آن نیز پرتو ارسال شود. نسبت به یک پرتو مرکزی، مقدار کار چقدر افزایش می‌یابد؟

۶٫۲۲

پیکسل ایده‌آل مربعی با ضلع یک واحد است، اما بیشتر CRTها پیکسل‌های گرد تولید می‌کنند که می‌توان آن‌ها را دایره‌های شدت یکنواخت تقریب زد. اگر مربع واحد کاملاً پُر شدت ۱٫۰ و کاملاً خالی شدت ۰٫۰ داشته باشد، شدت پیکسل نمایش‌داده‌شده با شعاع دایره چگونه تغییر می‌کند؟

۶٫۲۳

یک نمایشگر Bilevel با پیکسل‌های گرد را در نظر بگیرید. برای پیکسل‌های Foreground استفاده از دایره‌های کوچک بهتر است یا بزرگ؟ پاسخ را توضیح دهید.

۶٫۲۴

چرا Defocus کردن پرتو CRT گاهی «Antialiasing فقرا» نامیده می‌شود؟

۶٫۲۵

فرض کنید نمایشگر تک‌رنگ کمینهٔ شدت (I_{min}) و بیشینهٔ (I_{max}) دارد. با توجه به اینکه شدت را به‌صورت لگاریتمی درک می‌کنیم، k سطح شدت را چگونه انتخاب می‌کنید تا گام‌های روشنایی یکنواخت به نظر برسند؟

۶٫۲۶

الگوریتم Halftoneای بر اساس ایدهٔ زیر بسازید. فرض کنید سطح خاکستری از ۰٫۰ تا ۱٫۰ تغییر می‌کند و مولد عدد تصادفی مقادیری با توزیع یکنواخت در همین بازه می‌دهد. اگر سطح خاکستری g انتخاب شود، نسبت مشخصی از اعداد تصادفی تولیدشده کمتر از g خواهد بود. از این ویژگی برای تولید الگوی مناسب استفاده کنید.

۶٫۲۷

تصاویر روی نمایشگرهایی با تعداد کم رنگ یا سطح خاکستری تمایل به ایجاد اثر Contour دارند، زیرا بیننده اختلاف سایه‌های مجاور را تشخیص می‌دهد. یک روش جلوگیری از این اثر افزودن مقدار کمی نویز یا Jitter به مقادیر پیکسل است. چرا این روش کار می‌کند؟ چه مقدار نویز باید اضافه شود؟ آیا منطقی است تصویر دارای نویز را از نظر ادراکی باکیفیت‌تر از تصویر اصلی بدانیم؟

۶٫۲۸

نشان دهید مساحت چندضلعی دوبعدی مشخص‌شده با رأس‌های ((x_i,y_i)) از رابطهٔ زیر به دست می‌آید:

معنای مساحت منفی چیست؟ راهنما: مساحت ذوزنقه‌های تشکیل‌شده توسط دو رأس متوالی و نقاط متناظر آن‌ها روی محور x را در نظر بگیرید.

این صفحه در نسخهٔ اصلی عمداً خالی گذاشته شده است.