رسترسازی، الگوریتم برزنهم و حذف سطح پنهان
۶٫۸ رسترسازی
اکنون آمادهایم آخرین گام مسیر از تعریف موجودیتهای هندسی در برنامهٔ کاربردی تا تشکیل قطعهها را برداریم: رسترسازی بدویها. در این فصل فقط با پارهخطها و چندضلعیها سروکار داریم که هر دو با رأسها تعریف میشوند. فرض میکنیم بدویها قبلاً برش خوردهاند، بهطوریکه هر بدوی باقیمانده داخل حجم دید قرار دارد.
قطعهها را میتوان پیکسلهای بالقوه دانست. هر قطعه یک ویژگی رنگ و یک مکان در مختصات صفحه دارد که به مکانی در بافر رنگی متناظر است. قطعهها اطلاعات عمق نیز حمل میکنند که میتوان از آن برای حذف سطح پنهان استفاده کرد. برای روشنتر شدن بحث، حذف سطح پنهان را تا بخش ۶٫۱۱ کنار میگذاریم و مستقیماً در مختصات صفحه کار میکنیم. چون فعلاً حذف سطح پنهان، قطعههای نیمهشفاف و ضدهمپوشانی را در نظر نمیگیریم، میتوان الگوریتمهای رسترسازی را بر حسب پیکسلهایی که رنگ میکنند توسعه داد.
فرض میکنیم بافر رنگی آرایهای (n\times m) از پیکسلهاست و ((0,0)) گوشهٔ پایین-چپ آن است. درون پیادهسازی گرافیکی میتوان رنگ یک پیکسل را با تابعی از شکل زیر تنظیم کرد:
write_pixel(int ix, int iy, int value);
آرگومان value میتواند در حالت Color-Index یک اندیس یا در حالت RGBA یک اشارهگر به رنگ RGBA باشد. از یک سو، بافر رنگی ذاتاً گسسته است؛ صحبت از پیکسلهایی در مکانهایی غیر از مقادیر صحیح ix و iy معنا ندارد. از سوی دیگر، مختصات صفحه با اینکه در همان بازههای ix و iy قرار میگیرند، عدد حقیقیاند. مثلاً ممکن است مکان قطعهای مانند ((63.4,157.9)) را محاسبه کنیم، اما نزدیکترین پیکسل بسته به اینکه مرکز پیکسلها روی اعداد صحیح یا نیمهصحیح فرض شود، در ((63,158)) یا ((63.5,157.5)) قرار میگیرد.
پیکسلها در بافر رنگی دارای ویژگی رنگاند. نحوهٔ نمایش آنها میتواند بسته به خصوصیات نمایشگر از نظر شکل و اندازه متفاوت باشد. این موضوع در بخش ۶٫۱۳ بررسی میشود. فعلاً فرض میکنیم هر پیکسل به شکل مربعی نمایش داده میشود که مرکز آن در مکان نسبتدادهشده به پیکسل و طول ضلع آن برابر فاصلهٔ بین پیکسلهاست. در OpenGL مرکز پیکسلها در مقادیر نیمواحد بین اعداد صحیح قرار دارد. این انتخاب مزایایی دارد. همچنین فرض میکنیم فرایندی همزمان محتویات بافر رنگی را میخواند و نمایش را با نرخ لازم ایجاد میکند. این فرض، که در بسیاری از سامانههای دارای حافظهٔ Dual-Port برقرار است، اجازه میدهد رسترسازی را مستقل از نمایش محتوای بافر فریم بررسی کنیم.
سادهترین الگوریتم تبدیل پیمایشی برای پارهخطها با نام DDA شناخته میشود؛ نام آن از Digital Differential Analyzer، یک دستگاه الکترومکانیکی قدیمی برای شبیهسازی دیجیتال معادلات دیفرانسیل، آمده است. چون خط معادلهٔ دیفرانسیلی (dy/dx=m) را ارضا میکند که m شیب است، تولید یک پارهخط معادل حل عددی یک معادلهٔ دیفرانسیل ساده است.
فرض کنید پارهخط با نقاط انتهایی ((x_1,y_1)) و ((x_2,y_2)) تعریف شده باشد. چون در بافر رنگی کار میکنیم، فرض میکنیم این مقادیر به اعداد صحیح گرد شدهاند تا پارهخط از یک پیکسل معلوم آغاز و به یک پیکسل معلوم ختم شود.
شیب خط برابر است با:
m=\frac{y_2-y_1}{x_2-x_1}=\frac{\Delta y}{\Delta x}.
فرض میکنیم:
0\le m\le1.
سایر مقادیر m را میتوان با استفاده از تقارن مدیریت کرد. الگوریتم بر این اساس است که هنگامی که x از (x_1) به (x_2) میرود، برای هر مقدار ix یک پیکسل نوشته شود. اگر روی پارهخط باشیم، برای هر تغییر (\Delta x) متناظر داریم:
\Delta y=m\Delta x.
در حرکت از (x_1) به (x_2)، در هر تکرار x را یک واحد افزایش میدهیم؛ بنابراین y باید به اندازهٔ زیر افزایش یابد:
\Delta y=m.
هر x صحیح است، اما y لزوماً صحیح نیست زیرا m عدد ممیز شناور است؛ بنابراین برای یافتن پیکسل مناسب باید y را گرد کنیم. شبهکد الگوریتم چنین است:
for (ix=x1; ix <= x2; ix++)
{
y+=m;
write_pixel(x, round(y), line_color);
}
تابع round یک عدد حقیقی را به عدد صحیح گرد میکند. دلیل محدودکردن شیب به حداکثر ۱ از شکل ۶٫۲۹ روشن میشود. الگوریتم ما در اصل میگوید: «برای هر x، بهترین y را پیدا کن.» برای شیبهای بزرگ، فاصلهٔ پیکسلهای رنگشده زیاد میشود و تقریب نامطلوبی از پارهخط حاصل میگردد. اگر برای شیبهای بزرگتر از ۱ نقش x و y را عوض کنیم، الگوریتم تبدیل میشود به: «برای هر y، بهترین x را پیدا کن.» نتیجه برای همان پارهخطها تقریب مناسب شکل ۶٫۳۰ است. استفاده از تقارن همچنین مشکلات احتمالی خطهای کاملاً عمودی یا افقی را برطرف میکند. حالتهای شیب منفی نیز به همین روش قابل استخراجاند.
از آنجا که پارهخطها با رأسها تعیین میشوند، میتوان با درونیابی برای هر پیکسل تولیدشده رنگی متفاوت تعیین کرد. همچنین با تغییر رنگ در حین تولید پیکسلها میتوان الگوهای خطچین و نقطهچین ساخت.
شکل ۶٫۲۷ — پارهخط در مختصات پنجره.
شکل ۶٫۲۸ — پیکسلهای تولیدشده به وسیلهٔ الگوریتم DDA.
شکل ۶٫۲۹ — پیکسلهای تولیدشده برای خطهای با شیب زیاد و کم.
شکل ۶٫۳۰ — پیکسلهای تولیدشده توسط نسخهٔ اصلاحشدهٔ DDA.
یادداشت: فرض صحیحبودن مختصات دو انتها برای استخراج الگوریتم ضروری نیست. اگر از نمایش Fixed-Point و محاسبات Fixed-Point استفاده شود، مزیت محاسباتی الگوریتم حفظ میشود و رسترسازی دقیقتری نیز به دست میآید.
این اثرهای رنگی ارتباط مستقیمی با هستهٔ الگوریتم رسترسازی ندارند؛ وظیفهٔ اصلی رسترساز فقط تعیین این است که کدام پیکسلها باید رنگ شوند، نه اینکه چه رنگی روی آنها قرار گیرد.
۶٫۹ الگوریتم Bresenham
الگوریتم DDA ظاهراً کارآمد است و بهسادگی کدنویسی میشود، اما برای هر پیکسل تولیدشده یک جمع ممیز شناور لازم دارد. Bresenham الگوریتمی برای رسترسازی خط ارائه کرد که بهطرز قابل توجهی تمام محاسبات ممیز شناور را حذف میکند و به الگوریتم استاندارد رسترسازهای سختافزاری و نرمافزاری تبدیل شده است.
مانند DDA، فرض میکنیم پارهخط بین نقاط صحیح ((x_1,y_1)) و ((x_2,y_2)) قرار دارد و شیب شرط زیر را ارضا میکند:
0\le m\le1.
این شرط برای الگوریتم حیاتی است. فرض کنید در میانهٔ تبدیل پیمایشی قرار داریم و بهتازگی پیکسلی را در ((i+\tfrac12,j+\tfrac12)) قرار دادهایم. خط حامل پارهخط را میتوان نوشت:
y=mx+h.
در (x=i+\tfrac12)، خط باید حداکثر به فاصلهٔ نصف طول پیکسل از مرکز پیکسل ((i+\tfrac12,j+\tfrac12)) عبور کند، وگرنه عمل گردکردن آن پیکسل را انتخاب نمیکرد. اگر یک گام به (x=i+\tfrac32) برویم، شرط شیب نشان میدهد فقط یکی از دو پیکسل ممکن باید انتخاب شود: ((i+\tfrac32,j+\tfrac12)) یا ((i+\tfrac32,j+\tfrac32)).
پس مسئله را میتوان با متغیر تصمیم (d=a-b) بیان کرد، که در آن a و b فاصلههای خط تا دو پیکسل نامزد بالا و پایین در (x=i+\tfrac32) هستند. اگر d مثبت باشد، خط به پیکسل پایین نزدیکتر است و همان را انتخاب میکنیم؛ در غیر این صورت پیکسل بالا انتخاب میشود. میتوان d را با استفاده از (y=mx+h) محاسبه کرد، اما چون m ممیز شناور است ترجیح میدهیم چنین نکنیم.
مزیت محاسباتی الگوریتم Bresenham از دو گام دیگر ناشی میشود. نخست، عملیات ممیز شناور را با عملیات Fixed-Point جایگزین میکنیم. دوم، الگوریتم را بهصورت افزایشی اجرا میکنیم. متغیر تصمیم جدید را تعریف میکنیم:
d=(x_2-x_1)(a-b)=\Delta x(a-b).
شکل ۶٫۳۱ — شرایط هندسی الگوریتم Bresenham.
شکل ۶٫۳۲ — متغیر تصمیم در الگوریتم Bresenham.
این تغییر تعیین پیکسل را عوض نمیکند، زیرا فقط علامت متغیر تصمیم اهمیت دارد. با جایگذاری a و b و استفاده از معادلهٔ خط و روابط
m=\frac{y_2-y_1}{x_2-x_1}=\frac{\Delta y}{\Delta x},
h=y_2-mx_2,
میتوان دید d یک عدد صحیح است. بنابراین محاسبات ممیز شناور حذف شدهاند، هرچند محاسبهٔ مستقیم d هنوز به مقدار قابل توجهی محاسبات Fixed-Point نیاز دارد.
رویکردی اندکی متفاوت انتخاب میکنیم. فرض کنید (d_k) مقدار d در (x=k+\tfrac12) باشد. میخواهیم (d_{k+1}) را بهصورت افزایشی از (d_k) محاسبه کنیم. دو حالت وجود دارد، بسته به اینکه در گام قبلی مکان y پیکسل افزایش یافته باشد یا نه. با توجه به اینکه a فاصلهٔ مکان نامزد بالایی تا خط است، اگر در تصمیم قبلی فقط x افزایش یافته باشد a به اندازهٔ m افزایش مییابد؛ در حالت دیگر به اندازهٔ (m-1) کاهش مییابد. b نیز به شکل متناظر تغییر میکند. با ضرب در (\Delta x)، تغییرهای ممکن d یا (-2\Delta y) و یا (2(\Delta x-\Delta y)) خواهند بود.
شکل ۶٫۳۳ — افزایش مرحلهای مقادیر a و b.
نتیجه را میتوان به صورت زیر بیان کرد:
d_{k+1}=d_k-\begin{cases}
2\Delta y & d_k>0,\2(\Delta y-\Delta x) & \text{در غیر این صورت}.
\end{cases}
محاسبهٔ هر پیکسل بعدی در بافر رنگی فقط به یک جمع و یک آزمون علامت نیاز دارد. این الگوریتم آنقدر کارآمد است که روی برخی تراشههای گرافیکی در قالب یک دستور واحد پیادهسازی شده است. محاسبهٔ مقدار اولیهٔ (d_0) در تمرین ۶٫۱۴ بررسی میشود.
۶٫۱۰ رسترسازی چندضلعی
یکی از مزیتهای مهم نخستین سامانههای رستری، توانایی نمایش چندضلعیهای پُر بود. در آن زمان، رنگآمیزی بلادرنگ هر نقطهٔ داخل چندضلعی با سایهای متفاوت امکانپذیر نبود و اصطلاحهای «رسترسازی چندضلعی» و «تبدیل پیمایشی چندضلعی» عملاً به معنای پُرکردن چندضلعی با یک رنگ بودند. برخلاف رسترسازی خط که یک الگوریتم غالب دارد، روشهای قابل استفادهٔ متعددی برای رسترسازی چندضلعی وجود دارد. انتخاب بهشدت به معماری پیادهسازی وابسته است. ما بر روشهایی تمرکز میکنیم که با رویکرد خط لولهای سازگارند و میتوانند سایهزنی را نیز پشتیبانی کنند. در بخشهای ۶٫۱۰٫۴ تا ۶٫۱۰٫۶ چند رویکرد دیگر را مرور خواهیم کرد.
۶٫۱۰٫۱ آزمون داخل–خارج
چندضلعیهای ساده و تخت دارای ناحیهٔ داخلی کاملاً تعریفشدهاند. اگر محدب نیز باشند، OpenGL و سایر سامانههای گرافیکی رندر درست آنها را تضمین میکنند. با این حال، در عمل چندضلعیهای عمومیتری نیز پدید میآیند و میتوان آنها را به چند روش رندر کرد. برای چندضلعیهای ناتخت میتوان با تصویر آنها کار کرد یا سه رأس نخست را برای تعیین صفحهای بهعنوان مبنای ناحیهٔ داخلی به کار برد. برای چندضلعیهای تخت و غیرساده باید مشخص کنیم چگونه تعیین شود یک نقطهٔ دادهشده داخل چندضلعی است یا خارج آن.
یادداشت: از دید دقیق هندسی، «چندضلعی ناتخت» تعریف حقیقی ندارد زیرا ناحیهٔ داخلی آن بدون تختبودن تعریف نمیشود. اما از منظر برنامهنویسی، میتوان چندضلعی را صرفاً بهصورت فهرستی از رأسها تعریف کرد، خواه همه در یک صفحه باشند یا نه.
نقطهای را داخل یا خارج چندضلعی بدانیم. از نظر مفهومی، پُرکردن داخل چندضلعی با رنگ یا الگو معادل تصمیمگیری دربارهٔ این است که کدام نقاط صفحهٔ چندضلعی نقاط داخلیاند.
پرکاربردترین آزمون برای تصمیم داخل–خارج، آزمون عبور یا فرد–زوج (Odd–Even Test) است. فرض کنید p داخل چندضلعی باشد. هر نیمخطی که از p شروع شود و تا بینهایت ادامه یابد باید تعداد فردی یال را قطع کند. در مقابل، نیمخطی که از نقطهای بیرون چندضلعی شروع میشود و وارد آن میگردد، پیش از رسیدن به بینهایت تعداد زوجی از یالها را قطع میکند. بنابراین میتوان یک نقطه را زمانی داخل تعریف کرد که اگر خطی از آن عبور دهیم و از بیرون به سمت نقطه حرکت کنیم، پیش از رسیدن به آن تعداد فردی یال را قطع کرده باشیم. برای چندضلعی ستارهای شکل ۶٫۳۴، رنگآمیزی داخل طبق این قاعده به صورت نشاندادهشده حاصل میشود. آزمون فرد–زوج بهسادگی پیادهسازی میشود و با الگوریتمهای استاندارد رندر نیز بهخوبی یکپارچه است. معمولاً به جای نیمخطهای دلخواه از Scanlineها استفاده میکنیم و تعداد تقاطع با یالهای چندضلعی را میشماریم.
شکل ۶٫۳۴ — پُرکردن بر پایهٔ آزمون فرد–زوج.
ممکن است بخواهیم چندضلعی ستارهای به جای نتیجهٔ شکل ۶٫۳۴ مانند شکل ۶٫۳۵ پُر شود. آزمون عدد پیچش (Winding Number) چنین امکانی میدهد. در این آزمون، چندضلعی مانند گرهای در نظر گرفته میشود که دور نقطه یا خط پیچیده شده است. برای پیادهسازی، از هر رأس شروع و یالهای چندضلعی را در یک جهت دلخواه دنبال میکنیم تا دوباره به رأس شروع برسیم. سپس برای هر نقطهٔ دلخواه، عدد پیچش تعداد دفعاتی است که مسیر یالها آن نقطه را احاطه میکند. میتوان پیچش ساعتگرد را مثبت و پادساعتگرد را منفی—یا برعکس—شمرد. در شکل ۶٫۳۵، نقاط بیرون ستاره اصلاً احاطه نشدهاند و عدد پیچش ۰ دارند؛ نقاطی که در شکل ۶٫۳۴ پُر شدهاند عدد پیچش ۱ دارند؛ و نقاط مرکزی که در آزمون فرد–زوج پُر نشده بودند عدد پیچش ۲ دارند. اگر قاعدهٔ پُرکردن را چنین تعریف کنیم که «نقطه وقتی داخل است که عدد پیچش آن ناصفر باشد»، داخل چندضلعی مطابق شکل ۶٫۳۵(الف) پُر میشود.
شکل ۶٫۳۵ — پُرکردن با آزمون عدد پیچش.
۶٫۱۰٫۲ OpenGL و چندضلعیهای مقعر
چون OpenGL فقط مثلثها را رندر میکند و مثلث همیشه تخت و محدب است، هنوز مسئلهٔ مدیریت چندضلعیهای عمومیتر باقی میماند. یک راه این است که برنامهٔ کاربردی را ملزم کنیم فقط مثلث تولید کند. راه دیگر فراهمکردن نرمافزاری است که چندضلعی دلخواه را به چندضلعیهای تخت و محدب—معمولاً مثلثها—Tessellate کند. روشهای زیادی برای تقسیم یک چندضلعی به مثلث وجود دارد. یک Tessellation خوب نباید مثلثهای بسیار باریک و کشیده بسازد و در صورت امکان باید مجموعههایی از مثلثها تولید کند که از امکاناتی مانند Triangle Strip و Triangle Fan بهره ببرند.
یک روش برای مثلثبندی چندضلعی سادهٔ دلخواه با n رأس را بررسی میکنیم. از ساختار الگوریتم روشن خواهد شد که دقیقاً (n-2) مثلث تولید میشود. فرض کنید چندضلعی با فهرست مرتب رأسها (v_0,v_1,\ldots,v_{n-1}) تعریف شده است؛ یعنی یالها بهترتیب از (v_0) به (v_1)، از (v_1) به (v_2) و در نهایت از (v_{n-1}) به (v_0) هستند.
نخست چپترین رأس (v_i) را پیدا میکنیم؛ این کار فقط یک پیمایش ساده روی مؤلفهٔ x رأسهاست. دو همسایهٔ آن را (v_{i-1}) و (v_{i+1}) مینامیم که اندیسها پیمانهای نسبت به n محاسبه میشوند. این سه رأس مثلث (v_{i-1},v_i,v_{i+1}) را میسازند. اگر وضعیت مانند شکل ۶٫۳۶ باشد، میتوان (v_i) را از فهرست حذف کرد و بهصورت بازگشتی روی چندضلعی با (n-1) رأس ادامه داد؛ یک مثلث نیز جدا شده است.
شکل ۶٫۳۶ — حذف یک مثلث از چندضلعی.
اما چون چندضلعی ممکن است نامحدب باشد، پارهخط (v_{i-1}v_{i+1}) میتواند یالهای دیگر را قطع کند، مانند شکل ۶٫۳۷. برای تشخیص این حالت بررسی میکنیم آیا رأس دیگری در سمت چپ این پارهخط و داخل مثلث (v_{i-1},v_i,v_{i+1}) قرار دارد یا نه. اگر (v_i) را به چپترینِ این رأسها وصل کنیم، چندضلعی اصلی به دو چندضلعی تقسیم میشود، مانند شکل ۶٫۳۸، که هر کدام دستکم دو رأس کمتر از چندضلعی اصلی دارند. انتخاب چپترین رأس تضمین میکند هر دو چندضلعی ساده باشند. سپس بهصورت بازگشتی روی این دو چندضلعی ادامه میدهیم تا در نهایت فقط مثلثها باقی بمانند.
شکل ۶٫۳۷ — وجود رأس در داخل مثلث.
شکل ۶٫۳۸ — تقسیم چندضلعی به دو چندضلعی.
بدترین کارایی این روش وقتی رخ میدهد که هیچ رأسی داخل مثلث (v_{i-1},v_i,v_{i+1}) نباشد. برای اطمینان از این موضوع (O(n)) آزمون لازم است و در آن صورت فقط یک رأس از چندضلعی اصلی حذف میشود؛ بنابراین بدترین پیچیدگی (O(n^2)) است. اگر از قبل بدانیم چندضلعی محدب است، این آزمونها لازم نیستند و روش (O(n)) میشود. بهترین عملکرد عمومی وقتی است که هر تقسیم دو چندضلعی تقریباً هماندازه ایجاد کند؛ در این حالت اگر چنین تقسیمی در هر مرحله رخ دهد، پیچیدگی (O(n\log n)) خواهد بود. روشهایی با تضمین (O(n\log n)) وجود دارند، اما از روش حاضر پیچیدهترند. در عمل نیز بهندرت با چندضلعیهایی آنقدر پررأس مواجه میشویم که این روشهای پیچیده ضروری باشند.
۶٫۱۰٫۳ پُرکردن و مرتبسازی
رویکرد دیگری به رسترسازی چندضلعی از مفهوم پردازندهٔ چندضلعی آغاز میشود: جعبهٔ سیاهی که ورودی آن رأسهای مجموعهای از چندضلعیهای دوبعدی و خروجی آن بافر فریمی است که پیکسلهای صحیح در آن تنظیم شدهاند.
برای سادهترشدن بحث فرض کنیم هر چندضلعی با یک رنگ ثابت پُر میشود. ابتدا یک چندضلعی را در نظر بگیرید. قاعدهٔ پایهٔ پُرکردن چنین است: اگر نقطهای داخل چندضلعی است، آن را با رنگ داخلی یا Fill Color رنگ کن. این الگوریتم مفهومی نشان میدهد پُرکردن چندضلعی نوعی مسئلهٔ مرتبسازی است؛ یعنی همهٔ پیکسلهای بافر فریم را به دو گروهِ داخل و خارج چندضلعی تقسیم میکنیم. با انتخاب روشهای مختلف برای این تقسیمبندی، الگوریتمهای پُرکردن متفاوتی به دست میآیند. سه امکان را معرفی میکنیم:
- Flood Fill
- Scanline Fill
- Odd–Even Fill
۶٫۱۰٫۴ Flood Fill
میتوان یک چندضلعی توخالی را با رسترسازی یالهایش توسط الگوریتم Bresenham در بافر فریم نمایش داد. فرض کنید فقط دو رنگ داریم: رنگ پسزمینه سفید و رنگ پیشزمینه یا رسم سیاه. یالها را با رنگ پیشزمینه رسترسازی میکنیم و بافری مانند شکل ۶٫۳۹ به دست میآید. اگر یک نقطهٔ آغازین ((x,y)) داخل چندضلعی—یک Seed Point—پیدا کنیم، میتوان همسایههای آن را بهصورت بازگشتی بررسی کرد و اگر پیکسل یال نبودند آنها را با رنگ پیشزمینه رنگ کرد. شبهکد Flood Fill با فرض وجود تابع read_pixel که رنگ پیکسل را بازمیگرداند چنین است:
flood_fill(int x, int y)
{
if (read_pixel(x,y) == WHITE)
{
write_pixel(x,y,BLACK);
flood_fill(x-1,y);
flood_fill(x+1,y);
flood_fill(x,y-1);
flood_fill(x,y+1);
}
}
میتوان گونههای مختلفی از Flood Fill را با حذف بازگشت ساخت. یک روش این است که هر بار یک Scanline را پردازش کنیم.
شکل ۶٫۳۹ — چندضلعی نمایشدادهشده فقط با یالها.
۶٫۱۰٫۵ نقاط تکین
بیشتر الگوریتمهای پُرکردن چندضلعی را با اندکی دقت میتوان به شکلهای دیگر گسترش داد. مزیت ویژهٔ چندضلعیها این است که مکان یالهایشان دقیقاً معلوم است. با این حال، حتی چندضلعیها نیز وقتی رأس روی Scanline قرار میگیرد مشکل ایجاد میکنند. دو حالت شکل ۶٫۴۰ را در نظر بگیرید. اگر از تعریف Odd–Even استفاده کنیم، این دو حالت باید متفاوت مدیریت شوند.
شکل ۶٫۴۰ — تکینگیها: (الف) صفر یا دو عبور یال؛ (ب) یک عبور یال.
در حالت (الف)، تقاطع Scanline با رأس را میتوان صفر یا دو عبور یال شمرد؛ اما در حالت (ب)، تقاطع رأس–Scanline باید دقیقاً یک عبور یال محسوب شود.
دو راه برای اصلاح الگوریتم وجود دارد. میتوان بررسی کرد کدام وضعیت رخ داده و تعداد عبورها را مطابق آن شمرد. یا میتوان اساساً از وقوع حالت ویژهای که رأس دقیقاً روی Scanline قرار میگیرد—یک Singularity—جلوگیری کرد. برای این کار تضمین میکنیم هیچ رأسی مقدار صحیح y نداشته باشد و اگر داشت، مکان آن را اندکی Perturb میکنیم. روش دیگری که هنگام کار مستقیم در بافر فریم بسیار مفید است، تصور یک بافر فریم مجازی با دو برابر وضوح واقعی است؛ در این بافر مجازی، پیکسلها فقط در yهای زوج و رأسها فقط در yهای فرد قرار میگیرند. قرار دادن مرکز پیکسلها در نیمواحد بین اعداد صحیح، همانگونه که OpenGL انجام میدهد، عملاً معادل همین رویکرد است.
۶٫۱۱ حذف سطح پنهان
هرچند هر قطعهٔ تولیدشده در رسترسازی به مکانی در بافر رنگی متناظر است، اگر آن قطعه متعلق به شیئی باشد که پشت جسم مات دیگری قرار دارد نباید با رنگکردن پیکسل متناظر نمایش داده شود. حذف سطح پنهان یا تعیین سطح قابل مشاهده برای کشف این انجام میشود که چه بخشی، اگر اصلاً بخشی وجود داشته باشد، از هر شیء داخل حجم دید برای بیننده قابل مشاهده است و چه بخشی توسط اشیای دیگر پوشیده میشود.
چند تکنیک را برای صحنهای متشکل از چندضلعیهای کاملاً تخت بررسی میکنیم. چون بیشتر رندرکنندهها تا این مرحله سطوح را به چندضلعی تقسیم کردهاند، این انتخاب مناسب است. پارهخطها نیز با اصلاحات جزئی قابل مدیریتاند.
۶٫۱۱٫۱ رویکرد فضای شیء و فضای تصویر
مطالعهٔ الگوریتمهای حذف سطح پنهان بهخوبی تنوع الگوریتمهای موجود، تفاوت کار با اشیا و تصاویر، و اهمیت ارزیابی اثر افزایشی الگوریتمهای پیدرپی در فرایند پیادهسازی را نشان میدهد.
صحنهای شامل k چندضلعی تخت، مات و سهبعدی را در نظر بگیرید که هر یک یک شیء مستقل است. یک رویکرد عمومی فضای شیء را میتوان با مقایسهٔ جفتجفت اشیا از دید مرکز تصویرسازی ساخت. دو چندضلعی A و B چهار حالت دارند:
- A، B را کاملاً از دید دوربین میپوشاند؛ فقط A نمایش داده میشود.
- B، A را میپوشاند؛ فقط B نمایش داده میشود.
- هر دو A و B کاملاً قابل مشاهدهاند؛ هر دو نمایش داده میشوند.
- A و B بخشی از یکدیگر را میپوشانند؛ باید بخشهای قابل مشاهدهٔ هر دو محاسبه شود.
شکل ۶٫۴۱ — چهار رابطهٔ دیدپذیری دو چندضلعی A و B.
برای تحلیل پیچیدگی، تشخیص حالت و هر محاسبهٔ لازم برای بخش قابل مشاهدهٔ یک چندضلعی را یک عملیات در نظر میگیریم. سپس الگوریتم را تکراری اجرا میکنیم: یکی از k چندضلعی را انتخاب و با k−1 چندضلعی دیگر جفتجفت مقایسه میکنیم.
پس از این فرایند میدانیم چه بخشی از چندضلعی انتخابی قابل مشاهده است و همان بخش را رندر میکنیم. کار این چندضلعی تمام است و روی یکی از k−1 چندضلعی باقیمانده ادامه میدهیم. هر مرحله یک چندضلعی را با تمام چندضلعیهای باقیمانده مقایسه میکند تا در پایان فقط دو چندضلعی باقی بمانند و آن دو نیز با هم مقایسه شوند. بهسادگی میتوان دید پیچیدگی این محاسبه (O(k^2)) است. بنابراین حتی بدون ورود به جزئیات یک الگوریتم خاص فضای شیء، انتظار داریم این رویکرد برای صحنههایی با تعداد نسبتاً کم چندضلعی مناسبتر باشد.
رویکرد فضای تصویر از مدل مشاهده و Ray Casting پیروی میکند، همانگونه که در شکل ۶٫۴۲ نشان داده میشود. پرتوئی را در نظر بگیرید که از مرکز تصویرسازی خارج و از یک پیکسل عبور میکند. میتوان این پرتو را با صفحههای تعیینشده توسط k چندضلعی قطع کرد، تشخیص داد در کدام صفحهها نقطهٔ تقاطع واقعاً داخل چندضلعی است، و سپس نزدیکترین تقاطع به مرکز تصویرسازی را انتخاب کرد. پیکسل با سایهٔ همان چندضلعی در نقطهٔ تقاطع رنگ میشود.
عملیات بنیادی، تقاطع پرتو با چندضلعی است. برای نمایشگر (n\times m)، این عملیات حداکثر (nmk) بار انجام میشود و از نظر k پیچیدگی (O(k)) دارد. بنابراین بدون بررسی جزئیات نیز یک کران بالا به دست میآوریم. همین کران (O(k)) یکی از دلایل غالببودن روشهای فضای تصویر است. البته این کران، بدترین حالت است و در عمل الگوریتمهای فضای تصویر اغلب بهتر عمل میکنند. در عوض، چون در سطح قطعه یا پیکسل کار میکنند، دقت آنها به وضوح بافر فریم محدود میشود. برای افزایش دقت میتوان برای هر پیکسل بیش از یک پرتو استفاده کرد.
۶٫۱۱٫۲ مرتبسازی و حذف سطح پنهان
کران (O(k^2)) برای حذف سطح پنهان شیءمحور ممکن است الگوریتمهای مرتبسازی ضعیفتر مانند Bubble Sort را به یاد آورد. هر روش مبتنی بر مقایسهٔ brute-force جفتجفت اشیا پیچیدگی (O(k^2)) دارد. اما ارتباط مستقیمتری نیز وجود دارد: اگر بتوان اشیا را بر پایهٔ فاصلهشان از دوربین سازماندهی کرد، باید بتوان روش مستقیمی برای رندر آنها ساخت.
از قیاس با مرتبسازی میدانیم الگوریتمهای خوب مرتبسازی پیچیدگی (O(k\log k)) دارند؛ بنابراین انتظار داریم روشهای شیءمحور مناسب نیز به همین مرتبه نزدیک شوند.
شکل ۶٫۴۲ — حذف سطح پنهان در فضای تصویر؛ پرتوهای صادرشده از COP به پیکسلها، نزدیکترین سطح را تعیین میکنند.
در عمل همین انتظار درست است و الگوریتمهای متعددی با کرانهای بهتر وجود دارند. علاوه بر حذف سطح پنهان، مسائل مرتبط دیگری مانند تشخیص برخورد نیز در نگاه نخست (O(k^2)) به نظر میرسند اما میتوان آنها را به (O(k\log k)) کاهش داد.
۶٫۱۱٫۳ الگوریتمهای Scanline
جذابیت الگوریتم Scanline این است که میتواند پیکسلها را تقریباً با همان ترتیبی تولید کند که نمایش داده میشوند. چندضلعی شکل ۶٫۴۳ را با یک Scanline در نظر بگیرید. اگر قاعدهٔ Odd–Even را برای تعریف داخل چندضلعی به کار ببریم، سه گروه پیکسل—یا Span—روی این Scanline داخل چندضلعیاند. هر Span را میتوان برای محاسبات نورپردازی یا عمق مستقل پردازش کرد؛ راهبردی که در برخی سختافزارها با پردازندههای Span موازی استفاده شده است. در مثال سادهٔ Fill ثابت، پس از شناسایی Spanها کافی است پیکسلهای داخلی هر Span با رنگ Fill رنگ شوند.
شکل ۶٫۴۳ — چندضلعی و Spanهای حاصل روی یک Scanline.
Spanها از مجموعهٔ تقاطعهای یالهای چندضلعی با Scanlineها تعیین میشوند. رأسها تمام اطلاعات لازم برای یافتن این تقاطعها را دارند، اما نحوهٔ نمایش چندضلعی تعیین میکند تقاطعها با چه ترتیبی تولید شوند. برای مثال، چندضلعی شکل ۶٫۴۳ را که با فهرست مرتب رأسها نمایش داده شده در نظر بگیرید. طبیعیترین راه تولید تقاطع Scanline–یال، پردازش یالهای تعیینشده توسط رأسهای متوالی است. شکل ۶٫۴۴ تقاطعها را با همان ترتیبی نشان میدهد که این روش تولید میکند. این محاسبه را میتوان افزایشی انجام داد. با این حال، برای Fill این ترتیب اصلاً ترتیب مطلوبی نیست. اگر بخواهیم هر بار یک Scanline را پُر کنیم، تقاطعها باید ابتدا بر حسب Scanline و سپس بر حسب مقدار x روی هر Scanline مرتب شوند، مانند شکل ۶٫۴۵.
شکل ۶٫۴۴ — ترتیب تولید تقاطعها بر اساس فهرست رأسها.
شکل ۶٫۴۵ — ترتیب مطلوب تقاطعها برای پردازش Scanline.
یک روش brute-force میتواند تمام تقاطعها را مرتب کند، اما یک چندضلعی بزرگ یا دندانهدار ممکن است آنقدر تقاطع داشته باشد که هزینهٔ (O(n\log n)) مرتبسازی برای پیادهسازی بلادرنگ زیاد شود؛ برای مثال چندضلعیای را در نظر بگیرید که نیمی از Scanlineهای نمایشگر را قطع میکند.
روشهای مختلفی برای حذف جستوجوی عمومی وجود دارد. یکی از آنها که در اصل الگوریتم y–x نام داشت، برای هر Scanline یک Bucket ایجاد میکند. هنگام پردازش یالها، تقاطعهای آنها با Scanlineها در Bucket مناسب قرار میگیرند. سپس درون هر Bucket یک Insertion Sort مقادیر x را روی همان Scanline مرتب میکند. ساختار داده در شکل ۶٫۴۶ نشان داده شده است. بار دیگر میبینیم انتخاب ساختار دادهٔ مناسب میتواند الگوریتم را شتاب دهد. حتی میتوان با بازنگری نحوهٔ نمایش چندضلعیها یک گام فراتر رفت و به روش Scanline معرفیشده در بخش ۶٫۸ رسید.
شکل ۶٫۴۶ — ساختار داده برای الگوریتم y–x؛ هر Scanline فهرستی مرتب از x تقاطعها دارد.
۶٫۱۱٫۴ حذف وجه پشتی
در فصل ۵ دیدیم که در OpenGL میتوان فقط چندضلعیهای Front-Facing را رندر کرد. در موقعیتهایی که وجههای پشتی هرگز دیده نمیشوند—مانند صحنههای متشکل از چندوجهیهای محدب—میتوان با حذف همهٔ چندضلعیهای Back-Facing پیش از اجرای هر الگوریتم دیگر حذف سطح پنهان، مقدار کار را کاهش داد.
آزمون Culling وجه پشتی از شکل ۶٫۴۷ به دست میآید. جلوی چندضلعی زمانی دیده میشود که بردار نرمال خروجی از وجه جلو به سمت بیننده اشاره کند. اگر (\theta) زاویهٔ میان نرمال n و بردار دید v باشد، چندضلعی زمانی رو به جلوست که:
-90^\circ\le\theta\le90^\circ,
یا بهطور معادل:
\cos\theta\ge0.
شرط دوم بسیار سادهتر آزمون میشود، زیرا به جای محاسبهٔ کسینوس میتوان ضرب داخلی را بررسی کرد:
n\cdot v\ge0.
شکل ۶٫۴۷ — آزمون وجه پشتی با بردار نرمال و جهت دید.
این آزمون را میتوان بیشتر ساده کرد، زیرا معمولاً پس از تبدیل به مختصات نرمالشدهٔ دستگاه اعمال میشود. در این دستگاه همهٔ دیدها متعامدند و جهت تصویرسازی در راستای محور z است. بنابراین در مختصات همگن:
v=\begin{bmatrix}0\\0\\1\\0\end{bmatrix}.
اگر چندضلعی در مختصات نرمالشدهٔ دستگاه روی صفحهٔ
ax+by+cz+d=0
قرار داشته باشد، برای تشخیص Front-Facing یا Back-Facing کافی است فقط علامت c را بررسی کنیم. این آزمون در سختافزار یا نرمافزار بسیار ساده پیادهسازی میشود؛ فقط باید مطمئن باشیم حذف وجههای پشتی برای کاربرد مورد نظر صحیح است.
روش جالب دیگری نیز برای تشخیص وجه پشتی وجود دارد که بر مساحت چندضلعی در مختصات صفحه تکیه میکند. برای چندضلعی n رأسی شکل ۶٫۴۸، مساحت علامتدار a برابر است با:
a=\frac12\sum_i (y_{i+1}+y_i)(x_{i+1}-x_i),
که اندیسها پیمانهای نسبت به n هستند. مساحت منفی نشاندهندهٔ چندضلعی Back-Facing است.
شکل ۶٫۴۸ — محاسبهٔ مساحت علامتدار چندضلعی.
۶٫۱۱٫۵ الگوریتم z-Buffer
الگوریتم z-Buffer پرکاربردترین الگوریتم حذف سطح پنهان است. مزیتهای آن، پیادهسازی ساده در سختافزار یا نرمافزار و سازگاری عالی با معماری خط لولهای است؛ بهگونهای که میتواند با همان سرعت عبور قطعهها در خط لوله اجرا شود.
اگرچه الگوریتم در فضای تصویر عمل میکند، روی چندضلعیها حلقه میزند نه روی پیکسلها؛ بنابراین میتوان آن را بخشی از فرایند تبدیل پیمایشی دانست.
شکل ۶٫۴۹ — الگوریتم z-Buffer؛ برای یک پرتو، سطح دارای عمق کمتر از بین تقاطعها دیده میشود.
فرض کنید در حال رسترسازی یکی از دو چندضلعی A و B شکل ۶٫۴۹ هستیم. برای هر نقطهٔ تقاطع میان پرتو صادرشده از مرکز تصویرسازی و یک پیکسل، میتوان رنگی با استفاده از مقادیر درونیابیشدهٔ سایهٔ رأسها محاسبه کرد. افزون بر آن باید بررسی شود نقطه قابل مشاهده است یا نه. نقطه زمانی قابل مشاهده است که نزدیکترین نقطهٔ تقاطع در امتداد همان پرتو باشد. بنابراین اگر B را رسترسازی کنیم، سایهٔ آن فقط وقتی روی صفحه ظاهر میشود که فاصلهٔ (z_2) از فاصلهٔ (z_1) تا A کمتر باشد. برعکس، اگر A رسترسازی شود و B قبلاً نزدیکتر ثبت شده باشد، پیکسل A نمایش داده نمیشود.
چون پردازش چندضلعیبهچندضلعی انجام میشود، هنگام رسترسازی یک چندضلعی اطلاعات تمام چندضلعیهای دیگر را در اختیار نداریم. اما اگر هر قطعه اطلاعات عمق داشته باشد، میتوان همزمان با پردازش قطعهها، اطلاعات عمق هر محل بافر فریم را ذخیره و بهروزرسانی کرد.
فرض کنید بافری به نام z-Buffer با همان وضوح بافر فریم و دقت کافی برای نمایش عمق داریم. مثلاً برای نمایشگر (1024\times1280)، میتوان یک z-Buffer به همان ابعاد با عناصر ۳۲ بیتی داشت. در ابتدا هر عنصر بافر عمق با مقداری متناظر با بیشترین فاصلهٔ ممکن از مرکز تصویرسازی مقداردهی میشود و بافر رنگی با رنگ پسزمینه پر میگردد. اگر نرمالسازی پرسپکتیو قبلاً انجام شده باشد، به جای فاصله از COP میتوان فاصله از هر صفحهٔ مرجع ثابتی مانند (z=0) را سنجید، زیرا ترتیب نسبی عمق حفظ میشود.
در هر لحظه از رسترسازی و پردازش قطعه، هر خانهٔ z-Buffer فاصلهٔ نزدیکترین نقطهٔ تقاطعی را نگه میدارد که تا آن لحظه در امتداد پرتو متناظر پیدا شده است.
محاسبه چنین پیش میرود. چندضلعیها را یکییکی با یکی از روشهای بخش ۶٫۱۰ رسترسازی میکنیم. برای هر قطعهٔ چندضلعی، عمق آن را محاسبه و با مقدار متناظر z-Buffer مقایسه میکنیم. اگر عمق جدید بزرگتر باشد، پیشتر قطعهای نزدیکتر به بیننده پردازش شده و قطعهٔ جدید قابل مشاهده نیست. اگر عمق جدید کمتر باشد، قطعهای نزدیکتر یافتهایم؛ مقدار عمق z-Buffer را بهروزرسانی و رنگ محاسبهشدهٔ قطعه را در محل متناظر بافر رنگی قرار میدهیم.
در دید پرسپکتیو، عمقی که در z-Buffer استفاده میشود همان فاصلهای است که تبدیل نرمالسازی پرسپکتیو فصل ۴ تغییر داده است. اگرچه این تبدیل غیرخطی است، ترتیب نسبی فاصلهها را حفظ میکند. با این حال، غیرخطیبودن میتواند خطاهای عددی ایجاد کند، بهویژه وقتی فاصله تا صفحهٔ برش نزدیک بسیار کوچک باشد.
برخلاف بسیاری از جنبههای رندر که الگوریتم دقیق پیادهسازی ممکن است برای کاربر ناشناخته باشد، OpenGL برای حذف سطح پنهان مشخصاً از z-Buffer بهره میگیرد. علت این استثنا آن است که برنامهٔ کاربردی باید هر بار که تصویر جدیدی تولید میشود z-Buffer را صریحاً مقداردهی اولیه کند.
z-Buffer با رویکردهای تصویرمحور سازگاری خوبی دارد، زیرا کار افزایشی آن اندک است. فرض کنید چندضلعی را Scanline به Scanline رسترسازی میکنیم. چندضلعی بخشی از صفحهای است که میتوان آن را چنین نوشت:
ax+by+cz+d=0.
اگر ((x_1,y_1,z_1)) و ((x_2,y_2,z_2)) دو نقطه روی چندضلعی و صفحه باشند و
\Delta x=x_2-x_1,\quad \Delta y=y_2-y_1,\quad \Delta z=z_2-z_1,
آنگاه معادلهٔ صفحه در فرم تفاضلی به صورت زیر است:
a\Delta x+b\Delta y+c\Delta z=0.
در OpenGL میتوان با glDepthFunc تعیین کرد در حالت برابری فاصلهها چه رفتاری انجام شود.
شکل ۶٫۵۰ — الگوریتم افزایشی z-Buffer.
این معادله در مختصات پنجره نوشته شده است؛ بنابراین هر Scanline با خطی با y ثابت متناظر است و هنگام حرکت روی یک Scanline داریم (\Delta y=0). روی Scanline، x را با گامهای یکواحدی افزایش میدهیم که معادل حرکت یک پیکسل در بافر فریم است؛ پس (\Delta x) ثابت است. بنابراین هنگام حرکت از نقطهای به نقطهٔ بعدی روی Scanline:
\Delta z=-\frac{a}{c}\Delta x.
این مقدار ثابت است و برای هر چندضلعی فقط یک بار باید محاسبه شود.
اگرچه بدترین کارایی یک الگوریتم فضای تصویر با تعداد بدویها متناسب است، کارایی z-Buffer با تعداد قطعههایی متناسب است که رسترسازی تولید میکند؛ این تعداد نیز به مساحت چندضلعیهای رسترسازیشده وابسته است.
۶٫۱۱٫۶ تبدیل پیمایشی همراه با z-Buffer
تقریباً همهٔ اجزای لازم برای رسترسازی چندضلعی را معرفی کردهایم. در بخش ۶٫۱۰٫۱ آزمونهای Odd–Even و Winding را برای تعیین داخلبودن نقطه بررسی کردیم و در فصل ۵ سایهزنی چندضلعی با درونیابی را آموختیم. اکنون کافی است این اجزا را کنار هم بگذاریم و به کارایی توجه کنیم.
بار دیگر خط لوله را دنبال کنید و روی یک چندضلعی متمرکز شوید. رأسها و نرمالها یکییکی از تبدیلهای هندسی عبور میکنند. پیش از مرحلهٔ برش، رأسها باید در قالب چندضلعی مونتاژ شوند. اگر چندضلعی کاملاً حذف نشود، رأسها و نرمالهای آن برای سایهزنی و حذف سطح پنهان منتقل میشوند. در این نقطه با اینکه نرمالسازی تصویرسازی انجام شده، اطلاعات عمق هنوز موجود است. اگر روش سایهزنی درونیابیشونده بخواهیم، میتوان نورپردازی هر رأس را محاسبه کرد.
سه وظیفه باقی میماند: محاسبهٔ تصویرسازی متعامد نهایی، حذف سطح پنهان و سایهزنی. استفادهٔ دقیق از z-Buffer میتواند هر سه را تقریباً همزمان انجام دهد.
شکل ۶٫۵۱ — دو نمایش یک چندضلعی: (الف) مختصات نرمالشدهٔ دستگاه؛ (ب) مختصات صفحه.
شکل ۶٫۵۲ — دو نمایش یک Scanline: (الف) در مختصات نرمالشدهٔ دستگاه؛ (ب) در مختصات صفحه.
راهبرد این است که هر چندضلعی را یک Scanline در هر مرحله پردازش کنیم. در نمایش سهبعدی نرمالشده، Scanlineی که از مختصات صفحه به عقب تصویر شود با خطی با y ثابت متناظر است. فرض کنید همزمان روی Scanline صفحه و Back Projection آن حرکت کنیم. در مختصات صفحه، هر گام یک عرض پیکسل است. از خط مختصات نرمالشده برای محاسبهٔ افزایشی عمق و تعیین این استفاده میکنیم که آیا پیکسل متناظر نقطهای قابل مشاهده روی چندضلعی است یا نه. چون سایهٔ رأسهای چندضلعی قبلاً محاسبه شده، با درونیابی میتوان رنگ درست هر پیکسل قابل مشاهده را به دست آورد.
این فرایند نسبت به مراحل منفردی که قبلاً بررسی کردیم کار اضافهٔ اندکی دارد. نرخ آن با سرعت ارسال چندضلعیها در خط لوله کنترل و محدود میشود. تغییراتی مانند اعمال الگوهای بیتی موسوم به Stipple Pattern یا اعمال بافت به چندضلعیها نیز فقط اصلاحات کوچکی میخواهند.
۶٫۱۱٫۷ Depth Sort و الگوریتم Painter
شکل ۶٫۵۳ — الگوریتم Painter: (الف) دو چندضلعی و بیننده؛ (ب) چندضلعی جلویی بخشی از چندضلعی پشتی را میپوشاند.
گرچه روشهای فضای تصویر به دلیل کارایی و سادگی z-Buffer در سختافزار غالباند، روشهای فضای شیء نیز اغلب در سطح برنامه برای کاهش تعداد چندضلعیها به کار میروند. Depth Sort پیادهسازی مستقیمی از رویکرد فضای شیء برای حذف سطح پنهان است. آن را برای صحنهای از چندضلعیهای تخت معرفی میکنیم، هرچند قابل گسترش به کلاسهای دیگر اشیاست. Depth Sort خود گونهای از الگوریتم سادهتر Painter’s Algorithm است.
فرض کنید مجموعهای از چندضلعیها بر اساس فاصله از بیننده مرتب شدهاند. در شکل ۶٫۵۳(الف) دو چندضلعی داریم و بیننده آنها را مانند شکل ۶٫۵۳(ب) میبیند؛ چندضلعی جلویی بخشی از دیگری را میپوشاند. برای رندر درست میتوان بخش قابل مشاهدهٔ چندضلعی پشتی را محاسبه و فقط همان را در بافر فریم رندر کرد، اما این کار مستلزم برش یک چندضلعی در برابر دیگری است. راه دیگر مشابه روش یک نقاش است: ابتدا چندضلعی پشتی را کامل نقاشی میکنیم و سپس چندضلعی جلویی را روی آن میکشیم؛ در نتیجه بخش نامرئی چندضلعی پشتی بهطور طبیعی پوشانده میشود. هر دو چندضلعی کامل رندر میشوند و حذف سطح پنهان پیامد رندر پشتبهجلو است. در رهگیری پرتو و مصورسازی علمی، گاهی رندر جلوبهپشت نیز به کار میرود.
دو مسئلهٔ اصلی این روش این است که مرتبسازی چگونه انجام شود و در صورت همپوشانی چندضلعیها چه باید کرد. Depth Sort هر دو موضوع را مدیریت میکند، هرچند در بسیاری از کاربردها بهینهسازیهای ویژهٔ بیشتری ممکن است.
فرض کنید Extent هر چندضلعی قبلاً محاسبه شده است. گام بعدی Depth Sort، مرتبکردن همهٔ چندضلعیها بر اساس بیشینهٔ مقدار z آنها نسبت به بیننده است. اگر کمینهٔ عمق یک چندضلعی از بیشینهٔ عمق چندضلعی پشت آن بزرگتر باشد، میتوان چندضلعیها را پشتبهجلو رسم کرد و کار تمام است. برای نمونه، A در شکل ۶٫۵۴ پشت همهٔ چندضلعیهای دیگر است و میتواند نخست رسم شود.
شکل ۶٫۵۴ — Extentهای z چندضلعیها پس از مرتبسازی عمقی.
اما دربارهٔ سایر چندضلعیها فقط با z-Extent نمیتوان ترتیب قطعی داد. اگر z-Extent دو چندضلعی همپوشانی داشته باشد، هنوز ممکن است ترتیبی برای رندر مستقل آنها پیدا شود که تصویر درست را تولید کند. الگوریتم Depth Sort مجموعهای از آزمونهای بهتدریج دشوارتر را اجرا میکند تا چنین ترتیبی پیدا شود.
برای یک جفت چندضلعی با z-Extent همپوشان، سادهترین آزمون بررسی x-Extent و y-Extent است (شکل ۶٫۵۵). اگر حتی یکی از Extentهای x یا y همپوشانی نداشته باشد، هیچیک از دو چندضلعی نمیتواند دیگری را بپوشاند و ترتیب رسم آنها اهمیتی ندارد.
شکل ۶٫۵۵ — آزمون همپوشانی Extentها: (الف) x-Extentهای جدا؛ (ب) y-Extentهای جدا.
حتی اگر این آزمونها رد شوند، باز هم ممکن است ترتیبی برای رسم مستقل چندضلعیها وجود داشته باشد. شکل ۶٫۵۶ چنین حالتی را نشان میدهد: تمام رأسهای یک چندضلعی در یک سمت صفحهٔ تعیینشده توسط چندضلعی دیگر قرار دارند. با پردازش رأسهای دو چندضلعی میتوان تشخیص داد آیا این حالت برقرار است یا خیر.
شکل ۶٫۵۶ — چندضلعیهایی با Extentهای همپوشان که هنوز میتوان رابطهٔ عمقی آنها را از صفحههایشان تعیین کرد.
آزمون x و y در این شکل مستقیماً برای دید موازی معتبر است؛ این یکی دیگر از مزیتهای کار در مختصات نرمالشدهٔ دستگاه پس از نرمالسازی پرسپکتیو است.