از رأسها تا قطعهها: راهبردهای پیادهسازی و برش
فصل ۶ — از رأسها تا قطعهها
اکنون به مراحل بعدی خط لوله میپردازیم: برش (Clipping)، رسترسازی (Rasterization) و حذف سطح پنهان. با اینکه هنوز برخی بخشهای مهم OpenGL در دسترس برنامهنویس کاربردی را بررسی نکردهایم—از جمله بدویهای گسسته، نگاشت بافت، و منحنیها و سطوح—چند دلیل وجود دارد که این موضوعات را در همین نقطه بررسی کنیم. نخست، ممکن است بخواهید بدانید برنامههای شما در سامانهای که استفاده میکنید چگونه پردازش میشوند: خطوط چگونه روی صفحه رسم میشوند، چندضلعیها چگونه پر میشوند، و با بدویهایی که خارج از حجمهای دید تعریفشده در برنامه قرار دارند چه اتفاقی میافتد. دوم، دیدگاه ما این است که برای استفادهٔ کارآمد از یک سامانهٔ گرافیکی، باید درک عمیقتری از فرایند پیادهسازی داشته باشیم: کدام مراحل سادهاند و کدام مراحل سختافزار و نرمافزار را بیشتر درگیر میکنند. سوم، بحث پیادهسازی راه را برای قابلیتهای تازهای که سختافزارهای جدید پشتیبانی میکنند باز میکند.
یادگیری پیادهسازی مستلزم مطالعهٔ الگوریتمهاست. همانند بررسی هر الگوریتم دیگری، باید میان کارایی نظری و عملی، پیادهسازی سختافزاری و نرمافزاری، و ویژگیهای خاص یک کاربرد تمایز قائل شویم. میتوانیم بررسی کنیم که یک پیادهسازی OpenGL از این نظر درست کار میکند که پیکسلهای صحیح را روی صفحه تولید کند، اما برای الگوریتمهای مورد استفاده انتخابهای متعددی وجود دارد. ما بر عملیات پایهای تمرکز میکنیم که هم برای پیادهسازی یک API استاندارد ضروریاند و هم مستقل از این هستند که رندر با معماری خط لوله انجام شود یا با روشی دیگر، مانند رهگیری پرتو. بنابراین برای هر یک از وظایف اصلی پیادهسازی، مجموعهای از الگوریتمهای بنیادی را معرفی میکنیم.
در این فصل، الگوریتمهای پایهٔ پیادهسازی خط لولهٔ رندری را بررسی میکنیم که OpenGL از آن بهره میگیرد. تمرکز ما بر سه موضوع است: برش، رسترسازی و حذف سطح پنهان. برش شامل حذف اشیایی است که خارج از حجم دید قرار دارند و در نتیجه نمیتوانند در تصویر دیده شوند. رسترسازی از اشیای باقیمانده قطعهها (Fragments) را تولید میکند. این قطعهها میتوانند در تصویر نهایی سهم داشته باشند. حذف سطح پنهان تعیین میکند کدام قطعهها متناظر با اشیای قابل مشاهدهاند؛ یعنی اشیایی که در حجم دید قرار دارند و توسط اشیای نزدیکتر به دوربین پوشانده نشدهاند.
۶٫۱ راهبردهای بنیادی پیادهسازی
شکل ۶٫۱ — نمای سطحبالا از فرایند گرافیک: برنامهٔ کاربردی، رأسها و حالتها را به سامانهٔ گرافیکی میدهد و سامانهٔ گرافیکی پیکسلهای حاصل را در بافر فریم قرار میدهد.
از یک نمای سطحبالا آغاز میکنیم. در گرافیک رایانهای، کار را با یک برنامهٔ کاربردی شروع میکنیم و با یک تصویر به پایان میرسانیم. میتوان این فرایند را دوباره مانند یک جعبهٔ سیاه در نظر گرفت که ورودیهایش رأسها و حالتهای تعریفشده در برنامه—اشیای هندسی، ویژگیها و مشخصات دوربین—هستند و خروجی آن آرایهای از پیکسلهای رنگی در بافر فریم است.
درون این جعبهٔ سیاه باید کارهای متعددی انجام شود؛ از جمله تبدیلها، برش، سایهزنی، حذف سطح پنهان و رسترسازی بدویهایی که ممکن است روی نمایشگر ظاهر شوند. این وظایف را میتوان به شیوههای گوناگون سازمان داد، اما صرفنظر از راهبرد انتخابی همیشه باید دو کار انجام دهیم: هر شیء هندسی باید از سامانه عبور کند، و برای هر پیکسل از بافر رنگی که نمایش داده میشود باید یک رنگ تعیین شود.
فرض کنید آنچه درون جعبهٔ سیاه رخ میدهد را به صورت یک برنامهٔ واحد در نظر بگیریم که کل فرایند را انجام میدهد. ورودی این برنامه مجموعهای از رأسهای مشخصکنندهٔ اشیای هندسی است و خروجی آن پیکسلهای بافر فریم. از آنجا که این برنامه باید برای تکتک پیکسلها مقداری تعیین کند و هر بدوی هندسی (و هر منبع نور) را پردازش کند، انتظار داریم دستکم دو حلقه داشته باشد که روی این متغیرهای پایه تکرار شوند.
اگر بخواهیم چنین برنامهای بنویسیم، بلافاصله باید پاسخ دهیم که کدام متغیر حلقهٔ بیرونی را کنترل میکند. پاسخ این پرسش، جریان کل فرایند پیادهسازی را تعیین میکند. دو راهبرد بنیادی وجود دارد که معمولاً رویکرد تصویرمحور و رویکرد شیءمحور نامیده میشوند.
در رویکرد شیءمحور، حلقهٔ بیرونی روی اشیا اجرا میشود. میتوان برنامه را با حلقهای از این شکل تصور کرد:
for (each_object) render(object);
یک رندرکنندهٔ خط لولهای با این توصیف سازگار است. رأسها در برنامه تعریف میشوند و از مجموعهای از ماژولها عبور میکنند که آنها را تبدیل و رنگآمیزی میکنند و تعیین میکنند آیا قابل مشاهدهاند یا نه. یک چندضلعی ممکن است از مراحل نشاندادهشده در شکل ۶٫۲ عبور کند. پس از پردازش هندسی یک چندضلعی، رسترسازی آن از نظر بالقوه میتواند هر پیکسلی در بافر فریم را تحت تأثیر قرار دهد. بیشتر پیادهسازیهای این رویکرد بر ساخت خط لولهٔ رندر متکیاند که برای هر وظیفه ماژولهای سختافزاری یا نرمافزاری دارد. دادهها—یعنی رأسها—در سامانه رو به جلو جریان مییابند.
شکل ۶٫۲ — رویکرد شیءمحور: شیء بهترتیب از برش، تصویرسازی و رسترسازی عبور میکند و نتیجه به بافر فریم میرسد.
در گذشته، محدودیتهای اصلی رویکرد شیءمحور، حافظهٔ زیاد مورد نیاز و هزینهٔ بالای پردازش مستقل هر شیء بودند. هر بدوی هندسی که از پردازش هندسی خارج میشود بالقوه میتواند هر مجموعهای از پیکسلهای بافر فریم را تحت تأثیر قرار دهد؛ بنابراین کل بافر رنگی—و بافرهای دیگر مانند بافر عمق مورد استفاده برای حذف سطح پنهان—باید به اندازهٔ نمایشگر باشند و همیشه در دسترس قرار گیرند. پیش از آنکه حافظه هم ارزان و هم متراکم شود، این نیاز یک مشکل جدی به شمار میرفت. امروزه پردازندههای هندسی خط لولهای مختلفی وجود دارند که میتوانند دهها میلیون چندضلعی را در ثانیه پردازش کنند. در واقع دقیقاً چون عملیات یکسانی روی هر بدوی انجام میشود، سختافزار لازم برای ساخت سامانهٔ شیءمحور سریع و نسبتاً ارزان است و بسیاری از توابع آن با تراشههای ویژهمنظوره پیادهسازی میشوند.
امروزه محدودیت اصلی پیادهسازیهای شیءمحور این است که بیشتر محاسبات سراسری را نمیتوانند بهطور مستقیم مدیریت کنند. چون هر بدوی هندسی مستقل و با ترتیبی دلخواه پردازش میشود، جلوههای پیچیدهٔ سایهزنی که چند شیء هندسی را درگیر میکنند—مانند بازتابها—جز با روشهای تقریبی قابل انجام نیستند. استثنای اصلی، حذف سطح پنهان است که در آن از بافر z برای نگهداری اطلاعات سراسری استفاده میشود.
رویکردهای تصویرمحور روی پیکسلها یا ردیفهای پیکسلی موسوم به خطوط پیمایش (Scanlines) که بافر فریم را میسازند حلقه میزنند. شبهکد حلقهٔ بیرونی چنین برنامهای به شکل زیر است:
for (each_pixel) assign_a_color(pixel);
برای هر پیکسل، بهصورت معکوس پیش میرویم تا مشخص کنیم کدام بدویهای هندسی میتوانند در رنگ آن سهم داشته باشند. مزیت این رویکرد آن است که در هر لحظه فقط مقدار محدودی حافظهٔ نمایش لازم داریم و میتوان امیدوار بود پیکسلها با نرخ و ترتیبی تولید شوند که برای نوسازی نمایشگر مورد نیاز است. چون نتیجهٔ بیشتر محاسبات از یک پیکسل به پیکسل بعدی—یا از یک خط پیمایش به خط بعدی—تفاوت زیادی ندارد، میتوان از این همدوسی (Coherence) برای توسعهٔ شکلهای افزایشی بسیاری از مراحل پیادهسازی استفاده کرد. عیب اصلی این رویکرد این است که مگر آنکه ابتدا از دادههای هندسی یک ساختار داده بسازیم، نمیدانیم کدام بدویها بر کدام پیکسلها اثر میگذارند. چنین ساختاری ممکن است پیچیده باشد و میتواند ایجاب کند تمام دادههای هندسی در سراسر فرایند رندر در دسترس باشند. برای مسائل دارای پایگاههای دادهٔ بسیار بزرگ، حتی یک نمایش دادهٔ خوب نیز ممکن است نتواند مشکل حافظه را برطرف کند.
با این حال، چون رویکردهای فضای تصویر برای هر پیکسل به همهٔ اشیا دسترسی دارند، برای مدیریت اثرهای سراسری مانند سایهها و بازتابها بسیار مناسباند. رهگیری پرتو که در فصل ۱۱ بررسی میشود نمونهای از رویکرد تصویرمحور است.
ما بیشتر به رویکرد شیءمحور متمایل هستیم، هرچند نمونههایی از الگوریتمهای مناسب هر دو رویکرد را بررسی میکنیم.
۶٫۲ چهار وظیفهٔ اصلی
شکل ۶٫۳ — وظایف پیادهسازی: مدلسازی → پردازش هندسی → رسترسازی → پردازش قطعه → بافر فریم.
بلوکهای خط لوله را مرور میکنیم و بهویژه بر بلوکهایی تمرکز داریم که هنوز با جزئیات بررسی نشدهاند. هر سامانهٔ گرافیکی برای رندر یک موجودیت هندسی مانند یک چندضلعی سهبعدی، از زمان تعریف آن در برنامهٔ کاربر تا نمایش احتمالی روی دستگاه خروجی، باید چهار وظیفهٔ اصلی را انجام دهد:
- مدلسازی
- پردازش هندسی
- رسترسازی
- پردازش قطعه
شکل ۶٫۳ نشان میدهد این وظایف چگونه میتوانند در یک پیادهسازی خط لولهای سازمان یابند. مستقل از رویکرد انتخابی، هر چهار وظیفه باید انجام شوند.
۶٫۲٫۱ مدلسازی
نتیجهٔ معمول فرایند مدلسازی، مجموعههایی از رأسهاست که گروهی از اشیای هندسی پشتیبانیشده توسط بقیهٔ سامانه را مشخص میکنند. پیشتر نمونههایی دیدهایم که به مقداری مدلسازی توسط کاربر نیاز داشتند، مانند تقریب کرهها در فصل ۵. در فصلهای ۸ و ۹ روشهای مدلسازی دیگری را بررسی خواهیم کرد.
میتوان مدلساز را جعبهٔ سیاهی دانست که اشیای هندسی را تولید میکند و معمولاً همان برنامهٔ کاربر است. با این حال، مدلساز میتواند وظایف دیگری نیز انجام دهد. برای نمونه، برش را در نظر بگیرید: فرایند حذف بخشهایی از اشیا که چون خارج از حجم دید قرار دارند نمیتوانند روی نمایشگر ظاهر شوند. کاربر میتواند اشیای هندسی را در برنامه تولید کند و امیدوار باشد باقی سامانه بتواند آنها را با همان نرخ تولید پردازش کند؛ یا مدلساز میتواند با حداقلکردن تعداد اشیایی که تحویل میدهد، بار بخشهای بعدی سامانه را کاهش دهد. رویکرد دوم اغلب به این معناست که مدلساز برخی از همان کارهای بقیهٔ سامانه را، هرچند با الگوریتمهایی متفاوت، انجام دهد.
در مورد برش، مدلساز چون از جزئیات کاربرد آگاهی بیشتری دارد اغلب میتواند با یک روش ابتکاری مناسب، بسیاری—و گاهی بیشتر—بدویها را پیش از ارسال به فرایند استاندارد مشاهده حذف کند.
۶٫۲٫۲ پردازش هندسی
پردازش هندسی با رأسها کار میکند. هدفهای پردازندهٔ هندسی این است که تعیین کند کدام اشیای هندسی میتوانند روی نمایشگر ظاهر شوند و سایه یا رنگی را به رأسهای این اشیا نسبت دهد. چهار فرایند لازم است: تصویرسازی (Projection)، مونتاژ بدوی (Primitive Assembly)، برش و سایهزنی.
معمولاً نخستین گام در پردازش هندسی این است که با استفاده از تبدیل model-view، نمایش را از مختصات شیء به مختصات دوربین یا چشم تغییر دهیم. همانطور که در فصل ۳ دیدیم، تبدیل به مختصات دوربین فقط بخش نخست فرایند مشاهده است. در گام دوم، رأسها با تبدیل تصویرسازی به یک حجم دید نرمالشده تبدیل میشوند که در آن اشیای بالقوه قابل مشاهده داخل مکعبی با مرکز مبدأ قرار میگیرند. رأسها اکنون در مختصات برش (Clip Coordinates) نمایش داده میشوند. این نرمالسازی نهتنها تصویرسازیهای موازی و متعامد را به یک تصویرسازی متعامد ساده در یک حجم ساده تبدیل میکند، بلکه فرایند برش را نیز—چنانکه در بخش ۶٫۷ خواهیم دید—سادهتر میسازد.
اشیای هندسی با دنبالهای از تبدیلها تغییر میکنند؛ این تبدیلها ممکن است شکل و موقعیت آنها را عوض کنند (مدلسازی) یا نمایش مختصاتی آنها را تغییر دهند (مشاهده). در نهایت فقط بدویهایی که درون حجمی مشخص، یعنی حجم دید، قرار میگیرند میتوانند پس از رسترسازی روی نمایشگر ظاهر شوند. با این حال نمیتوانیم صرفاً اجازه دهیم همهٔ اشیا رسترسازی شوند و امیدوار باشیم سختافزار خودش با بدویهای کاملاً یا جزئاً خارج از حجم دید برخورد کند. این کار باید پیش از رسترسازی انجام شود. یک دلیل، ناکارآمد بودن رسترسازی اشیای خارج از حجم دید است، زیرا این اشیا نمیتوانند دیده شوند. دلیل دیگر این است که وقتی رأسها به رسترساز میرسند، دیگر نمیتوان آنها را مستقل پردازش کرد و ابتدا باید در قالب بدویها مونتاژ شوند. بدویهایی که بخشی از آنها داخل حجم دید است میتوانند بدویهای جدیدی با رأسهای جدید ایجاد کنند که باید محاسبات سایهزنی نیز برای آنها انجام شود. بنابراین پیش از برش، رأسها باید طی فرایندی موسوم به مونتاژ بدوی در قالب اشیا گروهبندی شوند.
توجه کنید حتی اگر شیئی داخل حجم دید باشد، اگر توسط اشیای دیگر پوشانده شود قابل مشاهده نخواهد بود. الگوریتمهای حذف سطح پنهان—یا تعیین سطح قابل مشاهده—بر روابط فضایی سهبعدی میان اشیا تکیه دارند. این مرحله معمولاً بخشی از پردازش قطعه است.
همانطور که در فصل ۵ دیدیم، رنگها را میتوان بهازای هر رأس یا هر قطعه تعیین کرد. اگر رنگ بهازای رأس تعیین شود، میتوان آن را از برنامه به صورت ویژگی رأس فرستاد یا در Vertex Shader محاسبه کرد. اگر نورپردازی فعال باشد، رنگ رأس با مدل نورپردازیای محاسبه میشود که میتواند در برنامه یا در Vertex Shader پیادهسازی شده باشد.
پس از برش، رأسهای باقیمانده هنوز در مختصات همگن چهاربعدیاند. تقسیم پرسپکتیو آنها را به نمایش سهبعدی در مختصات نرمالشدهٔ دستگاه تبدیل میکند.
در مجموع، این عملیات چیزی را تشکیل میدهند که پردازش بخش جلویی (Front-End Processing) نامیده شده است. همهٔ آنها محاسبات سهبعدیاند، به حساب ممیز شناور نیاز دارند، الزامات سختافزاری و نرمافزاری مشابهی ایجاد میکنند و همگی رأسبهرأس انجام میشوند. برش، تنها مرحلهٔ هندسی که هنوز بررسی نکردهایم، در بخش ۶٫۳ بحث میشود.
۶٫۲٫۳ رسترسازی
حتی پس از انجام پردازش هندسی، برای حذف سطح پنهان باید اطلاعات عمق را نگه داریم. با این حال، برای تعیین اینکه یک بدوی میتواند کدام پیکسلهای بافر فریم را تحت تأثیر قرار دهد فقط مقادیر x و y رأسها لازماند. برای مثال، پس از تقسیم پرسپکتیو، پارهخطی که در ابتدا با دو رأس سهبعدی تعریف شده بود به پارهخطی تبدیل میشود که با جفتی از رأسهای سهبعدی در مختصات نرمالشدهٔ دستگاه مشخص شده است. برای تولید مجموعهای از قطعهها که مکان پیکسلهای متناظر در بافر فریم را نشان میدهند، فقط مؤلفههای x و y یا، بهطور معادل، نتیجهٔ تصویرسازی متعامد این رأسها را نیاز داریم. این قطعهها طی فرایندی به نام رسترسازی یا تبدیل پیمایشی (Scan Conversion) تعیین میشوند. برای پارهخطها، رسترسازی مشخص میکند کدام قطعهها باید برای تقریب خط بین رأسهای تصویرشده استفاده شوند. برای چندضلعیها، رسترسازی تعیین میکند کدام پیکسلها داخل چندضلعی دوبعدی تعیینشده به وسیلهٔ رأسهای تصویرشده قرار دارند.
رنگهای نسبتدادهشده به این قطعهها میتوانند از ویژگیهای رأس تعیین شوند یا با درونیابی سایههای محاسبهشده در رأسها، همانند فصل ۵، به دست آیند. اشیای پیچیدهتر از پارهخط و چندضلعی معمولاً با چندین پارهخط و چندضلعی تقریب زده میشوند؛ بنابراین بیشتر سامانههای گرافیکی الگوریتم رسترسازی ویژهای برای آنها ندارند. در فصل ۱۰ برای برخی منحنیها و سطوح خاص استثناهایی بر این قاعده خواهیم دید.
رسترساز با رأسها در مختصات نرمالشدهٔ دستگاه آغاز میکند، اما قطعههایی خروجی میدهد که مکانشان بر حسب واحدهای نمایشگر—یعنی مختصات پنجره—است. همانطور که در فصلهای ۲ و ۴ دیدیم، تصویر حجم برش باید در Viewport تعیینشده ظاهر شود. در OpenGL این تبدیل نهایی پس از تصویرسازی و بهصورت دوبعدی انجام میشود. تبدیلهای قبلی حجم دید را نرمال کردهاند، بهگونهای که اضلاع آن طول ۲ دارند و با اضلاع Viewport همراستا هستند (شکل ۶٫۴). بنابراین تبدیل چنین است:
x_v=x_{v\min}+\frac{x+1.0}{2.0}(x_{v\max}-x_{v\min}),
y_v=y_{v\min}+\frac{y+1.0}{2.0}(y_{v\max}-y_{v\min}),
z_v=z_{v\min}+\frac{z+1.0}{2.0}(z_{v\max}-z_{v\min}).
به یاد آورید که در مشاهدهٔ پرسپکتیو، این مقادیر z در نرمالسازی پرسپکتیو بهصورت غیرخطی مقیاس شدهاند. با این حال، ترتیب عمقی اصلی خود را حفظ میکنند و در نتیجه میتوان از آنها برای حذف سطح پنهان استفاده کرد.
شکل ۶٫۴ — تبدیل Viewport: مختصات نرمالشدهٔ دستگاه به محدودهٔ مختصات پنجره نگاشت میشوند.
اصطلاح مختصات صفحه (Screen Coordinates) را برای سامانهٔ دوبعدیای به کار میبریم که همان مختصات پنجره است اما مؤلفهٔ عمق را ندارد.
۶٫۲٫۴ پردازش قطعه
در سادهترین حالت، رسترساز به هر قطعه یک رنگ اختصاص میدهد و این رنگ در محل متناظر با قطعه در بافر فریم قرار میگیرد. با این حال، امکانهای دیگری نیز وجود دارد.
خط لولهٔ جداگانهٔ پیکسل که معماریهایی مانند OpenGL از آن پشتیبانی میکنند، در مرحلهٔ رسترسازی با نتایج خط لولهٔ هندسی ادغام میشود. ببینید هنگام پردازش یک چندضلعی سایهزنیشده و دارای نگاشت بافت چه رخ میدهد. نورپردازی رأس بهعنوان بخشی از پردازش هندسی محاسبه میشود. مقادیر بافت تا پس از رسترسازی لازم نیستند؛ یعنی زمانی که رندرکننده قطعههای متناظر با نقاط داخل چندضلعی را تولید کرده است. در این مرحله، درونیابی رنگهای رأس و مختصات بافت انجام میشود و پارامترهای بافت تعیین میکنند رنگهای بافت و رنگ قطعه چگونه برای تولید رنگهای نهایی بافر رنگی ترکیب شوند.
همانطور که اشاره شد، اشیای داخل حجم دید اگر توسط جسم مات نزدیکتری به بیننده پوشیده شوند قابل مشاهده نخواهند بود. فرایند لازم برای حذف سطح پنهان معمولاً قطعهبهقطعه انجام میشود.
تا اینجا فرض کردهایم همهٔ اشیا ماتاند و جسمی که پشت جسم دیگر قرار دارد دیده نمیشود. همچنین میتوان اشیا را نیمهشفاف در نظر گرفت و اجازه داد بخشی از نور از آنها عبور کند. در این حالت، ممکن است لازم باشد رنگ قطعهها با رنگ پیکسلهایی که از قبل در بافر رنگی هستند ترکیب شود. این امکان را در فصل ۷ بررسی میکنیم.
در بیشتر نمایشگرها، انتقال تصویر از بافر فریم و نمایش آن روی مانیتور بهطور خودکار انجام میشود و برنامهٔ کاربردی درگیر آن نیست. با این حال، مشکلات گوناگونی در کیفیت نمایش وجود دارد؛ از جمله لبههای دندانهدار تصاویر در نمایشگرهای رستری. در فصل ۷ الگوریتمهایی برای کاهش این دندانهدارشدن یا Aliasing معرفی میکنیم و مسائل بازتولید رنگ روی نمایشگرها را نیز بررسی خواهیم کرد.
۶٫۳ برش
اکنون میتوانیم به برش بپردازیم؛ فرایندی که تعیین میکند کدام بدویها یا کدام بخش از بدویها در حجم برش یا حجم دید تعریفشده توسط برنامهٔ کاربردی جای میگیرند. برش پیش از تقسیم پرسپکتیو انجام میشود؛ تقسیم پرسپکتیو زمانی لازم است که مؤلفهٔ w یک رأس برشخورده برابر ۱ نباشد. بخشهای همهٔ بدویهایی که بالقوه امکان نمایش دارند—در این مرحله هنوز حذف سطح پنهان اعمال نشده است—در مکعب زیر قرار میگیرند:
w \ge x \ge -w,
w \ge y \ge -w,
w \ge z \ge -w.
این دستگاه مختصات مختصات نرمالشدهٔ دستگاه نامیده میشود، زیرا نه به واحدهای اولیهٔ برنامه وابسته است و نه به جزئیات دستگاه نمایش؛ با این حال، اطلاعات لازم برای تولید تصویر درست در آن حفظ میشود. توجه کنید که تصویرسازی هنوز فقط بخشی از مسیر را طی کرده است. همچنان باید تقسیم پرسپکتیو و تصویرسازی متعامد نهایی را انجام دهیم.
تمرکز ما بر برش پارهخطها و چندضلعیهاست، زیرا رایجترین بدویهای عبوری از خط لوله هستند. اگرچه خط لولهٔ OpenGL برش را روی اشیای سهبعدی انجام میدهد، سامانههایی نیز وجود دارند که ابتدا اشیا را روی صفحهٔ x,y تصویر میکنند. خوشبختانه بسیاری از کارآمدترین الگوریتمها در دو و سه بعد تقریباً یکساناند و ما بر همین الگوریتمها تمرکز خواهیم کرد.
۶٫۴ برش پارهخط
یک Clipper تعیین میکند کدام بدویها یا کدام بخش از آنها میتوانند بالقوه روی نمایشگر ظاهر شوند و به رسترساز تحویل داده شوند. بدویهایی که کاملاً در حجم دید مشخصشده جا میگیرند از Clipper عبور میکنند یا پذیرفته میشوند. بدویهایی که نمیتوانند روی نمایشگر ظاهر شوند حذف، رد یا Culled میشوند. بدویهایی که فقط بخشی از آنها داخل حجم دید است باید برش بخورند تا هر بخش خارج از حجم حذف شود.
برش میتواند در یک یا چند نقطه از خط لولهٔ مشاهده رخ دهد. مدلساز ممکن است برای کاهش تعداد بدویهایی که سختافزار باید مدیریت کند برش انجام دهد. بدویها همچنین ممکن است پس از تصویرشدن از اشیای سهبعدی به دوبعدی برش داده شوند. در OpenGL، بدویها پیش از رسترسازی در برابر یک حجم دید سهبعدی برش میخورند. مجموعهای از Clipperها را توسعه میدهیم. هم به دلایل آموزشی و هم تاریخی، کار را با دو Clipper دوبعدی پارهخط آغاز میکنیم. هر دو روش مستقیماً به سه بعد و برش چندضلعیها قابل گسترشاند.
۶٫۴٫۱ برش Cohen–Sutherland
مسئلهٔ دوبعدی برش پارهخط در شکل ۶٫۵ نشان داده شده است. فعلاً فرض میکنیم این مسئله پس از تصویرشدن پارهخطهای سهبعدی روی صفحهٔ تصویر رخ میدهد و پنجره بخشی از صفحهٔ تصویر است که به Viewport نمایشگر نگاشت شده است.
شکل ۶٫۵ — برش دوبعدی: پارهخط AB کاملاً قابل نمایش است، CD کاملاً بیرون قرار دارد، و EF و GH باید کوتاه شوند.
همهٔ مقادیر با اعداد حقیقی مشخص میشوند. کل پارهخط AB روی نمایشگر ظاهر میشود، در حالی که هیچ بخشی از CD دیده نمیشود. EF و GH باید پیش از نمایش کوتاه شوند. اگرچه یک پارهخط کاملاً با دو نقطهٔ انتهایی خود تعیین میشود، GH نشان میدهد حتی اگر هر دو انتها بیرون پنجرهٔ برش باشند ممکن است بخشی از پارهخط همچنان قابل نمایش باشد.
میتوانستیم تقاطع خطهای حامل پارهخطها را با اضلاع پنجره محاسبه کنیم و از این راه اطلاعات لازم برای برش را به دست آوریم. اما در صورت امکان میخواهیم از محاسبهٔ تقاطع پرهیز کنیم، زیرا هر تقاطع به یک تقسیم ممیز شناور نیاز دارد. الگوریتم Cohen–Sutherland نخستین الگوریتمی بود که تلاش کرد بیشتر ضربها و تقسیمهای پرهزینهٔ ممیز شناور را با ترکیبی از تفریقهای ممیز شناور و عملیات بیتی جایگزین کند.
الگوریتم با امتداددادن اضلاع پنجره تا بینهایت آغاز میشود و بدین ترتیب فضا را به نه ناحیهٔ شکل ۶٫۶ تقسیم میکند. به هر ناحیه میتوان یک عدد دودویی ۴ بیتی یکتا، یا Outcode به شکل (b_0b_1b_2b_3)، اختصاص داد. فرض کنید ((x,y)) نقطهای در یک ناحیه باشد. آنگاه:
b_0 = \begin{cases}1 & y > y_{max}\\0 & \text{در غیر این صورت}\end{cases}
به همین ترتیب، (b_1) زمانی ۱ است که (y<y_{min}) باشد و (b_2) و (b_3) از رابطهٔ x با اضلاع چپ و راست پنجره تعیین میشوند. کدهای حاصل در شکل ۶٫۶ آمدهاند. برای هر انتهای یک پارهخط، ابتدا Outcode آن را محاسبه میکنیم؛ این مرحله ممکن است برای هر پارهخط به هشت تفریق ممیز شناور نیاز داشته باشد.
شکل ۶٫۶ — تقسیم فضا و Outcodeها: چهار بیت موقعیت نقطه را نسبت به بالا، پایین، چپ و راست پنجرهٔ برش کد میکنند.
پارهخطی را در نظر بگیرید که Outcodeهای دو انتهای آن به صورت (o_1=outcode(x_1,y_1)) و (o_2=outcode(x_2,y_2)) باشند. اکنون میتوان بر پایهٔ این کدها تصمیم گرفت. چهار حالت وجود دارد:
- (o_1=o_2=0). هر دو انتها داخل پنجرهٔ برشاند، مانند AB. کل پارهخط داخل است و مستقیماً برای رسترسازی فرستاده میشود.
- یکی از Outcodeها صفر و دیگری ناصفر است. یک انتها داخل و دیگری بیرون است، مانند CD در شکل ۶٫۷. پارهخط باید کوتاه شود. Outcode ناصفر نشان میدهد پارهخط کدام ضلع یا اضلاع پنجره را قطع میکند. لازم است یک یا دو تقاطع محاسبه شود. پس از محاسبهٔ یک تقاطع، Outcode نقطهٔ تقاطع را میتوان محاسبه کرد تا مشخص شود تقاطع دیگری لازم است یا نه.
شکل ۶٫۷ — حالتهای Outcode در الگوریتم Cohen–Sutherland.
- اگر AND بیتی دو Outcode ناصفر باشد، دو انتها در سمت بیرونی مشترکی از پنجره قرار دارند و پارهخط را میتوان حذف کرد، مانند EF.
- اگر AND بیتی دو Outcode صفر باشد و هر دو انتها بیرون باشند، انتهاها بیرون اضلاع متفاوت قرار دارند. همانطور که پارهخطهای GH و IJ نشان میدهند، تنها از روی Outcodeها نمیتوان تعیین کرد پارهخط باید حذف یا کوتاه شود. بهترین کار این است که تقاطع با یکی از اضلاع پنجره را محاسبه کنیم و Outcode نقطهٔ حاصل را بررسی کنیم.
تمام بررسیهای Outcode فقط عملیات بولی نیاز دارند. محاسبات تقاطع تنها وقتی انجام میشوند که ضروری باشند، مانند حالت دوم، یا وقتی Outcodeها اطلاعات کافی برای تصمیمگیری ندارند، مانند حالت چهارم.
الگوریتم Cohen–Sutherland زمانی بهترین عملکرد را دارد که پارهخطهای زیادی وجود داشته باشند اما تعداد کمی از آنها واقعاً نمایش داده شوند. در این وضعیت بیشتر پارهخطها کاملاً بیرون یکی یا دو امتداد ضلع مستطیل برش قرار دارند و میتوان آنها را صرفاً بر اساس Outcode حذف کرد. مزیت دیگر، قابلیت گسترش الگوریتم به سه بعد است. عیب اصلی این است که الگوریتم باید بهصورت بازگشتی به کار رود. برای نمونه، پارهخط GH در شکل ۶٫۷ باید هم در برابر ضلع چپ و هم ضلع بالا برش بخورد. معمولاً سادهترین روش این است که از Outcodeهای اولیه برای تعیین نخستین ضلع برش استفاده شود. پس از کوتاهکردن اولیه، برای انتهای جدید یک Outcode تازه محاسبه میشود و الگوریتم دوباره اجرا میگردد.
هنوز دربارهٔ نحوهٔ محاسبهٔ تقاطعهای لازم صحبت نکردهایم. شکل محاسبه به روشی وابسته است که برای نمایش پارهخط انتخاب میکنیم، هرچند در هر حالت بیش از یک تقسیم نباید لازم باشد. اگر از فرم صریح استاندارد خط استفاده کنیم:
y=mx+h,
که در آن m شیب و h عرض از مبدأ y است، میتوان m و h را از دو انتهای خط محاسبه کرد. اما خطهای عمودی را نمیتوان با این فرم نمایش داد و این ضعف مهم فرم صریح است.
اگر فقط به الگوریتم Cohen–Sutherland علاقه داشتیم، برنامهنویسی مستقیم همهٔ حالتها نسبتاً ساده بود، زیرا اضلاع مستطیل برش با محورهای مختصات موازیاند. با این حال، هدف ما فراتر از برش است و نمایشهای دیگر خط و پارهخط نیز اهمیت دارند. بهطور خاص، در گرافیک رایانهای تقریباً همیشه از نمایشهای پارامتری استفاده میشود. فرم پارامتری خط را در فصل ۴ دیدهایم و نمایش پارامتری انواع دیگر منحنیها در فصل ۱۰ بررسی خواهد شد.
۶٫۴٫۲ برش Liang–Barsky
اگر از فرم پارامتری خط استفاده کنیم، میتوانیم برش پارهخط را به روشی متفاوت و در نهایت کارآمدتر انجام دهیم. فرض کنید پارهخط با دو انتهای
(p_1=[x_1,y_1]^T) و (p_2=[x_2,y_2]^T) تعریف شده باشد. این دو نقطه خط یکتایی را تعریف میکنند که میتوان آن را به صورت پارامتری، در فرم ماتریسی، نوشت:
p(\alpha)=(1-\alpha)p_1+\alpha p_2,
یا به صورت دو معادلهٔ اسکالر:
x(\alpha)=(1-\alpha)x_1+\alpha x_2,
y(\alpha)=(1-\alpha)y_1+\alpha y_2.
این فرم پایدار است و برای خطهای افقی یا عمودی به هیچ تغییر ویژهای نیاز ندارد. با تغییر (\alpha) از ۰ تا ۱، روی پارهخط از (p_1) به (p_2) حرکت میکنیم. مقادیر منفی (\alpha) نقاطی از خط را در سوی دیگر (p_1) نسبت به (p_2) میدهند و مقادیر (\alpha>1) نقاطی را پس از (p_2) و در امتداد خط تا بینهایت مشخص میکنند.
پارهخط و خط حامل آن را مانند شکل ۶٫۸(الف) در نظر بگیرید. تا زمانی که خط با یکی از اضلاع پنجره موازی نباشد—حالتی که بهسادگی قابل مدیریت است—چهار نقطهٔ تقاطع میان خط و امتداد اضلاع پنجره وجود دارد. این نقاط متناظر با چهار مقدار پارامتر (\alpha_1,\alpha_2,\alpha_3,\alpha_4) هستند. یکی از این مقادیر ورود خط به پنجره و دیگری خروج آن را مشخص میکند.
شکل ۶٫۸ — دو حالت از یک خط پارامتری و پنجرهٔ برش.
فعلاً بدون پرداختن به نحوهٔ محاسبهٔ این تقاطعها، میتوان آنها را مرتب کرد و مشخص نمود کدام تقاطعها برای برش لازماند. در مثال شکل ۶٫۸(الف):
1>\alpha_4>\alpha_3>\alpha_2>\alpha_1>0.
بنابراین هر چهار تقاطع داخل پارهخط اصلی قرار دارند و دو مقدار میانی (\alpha_2) و (\alpha_3) پارهخط برشخورده را تعیین میکنند. این حالت را میتوان از شکل ۶٫۸(ب)، که آن هم چهار تقاطع بین دو انتهای پارهخط دارد، با ترتیب زیر تشخیص داد:
1>\alpha_4>\alpha_2>\alpha_3>\alpha_1>0.
در این حالت، خط پیش از آنکه هیچیک از اضلاع چپ یا راست را قطع کند، هر دو ضلع بالا و پایین پنجره را قطع میکند؛ پس کل پارهخط باید رد شود. حالتهای دیگر ترتیب نقاط تقاطع نیز به همین روش تحلیل میشوند.
پیادهسازی کارآمد این راهبرد مستلزم آن است که تقاطعها را فقط در صورت نیاز محاسبه کنیم. بسیاری از خطها را میتوان پیش از معلومشدن هر چهار تقاطع رد کرد. همچنین میخواهیم تا حد امکان از تقسیم ممیز شناور اجتناب شود. اگر از فرم پارامتری برای یافتن تقاطع با ضلع بالای پنجره استفاده کنیم، داریم:
\alpha=\frac{y_{max}-y_1}{y_2-y_1}.
برای سه ضلع دیگر نیز روابط مشابه برقرار است. به جای انجام مستقیم این تقسیمها، مینویسیم:
\alpha(y_2-y_1)=\alpha\Delta y=y_{max}-y_1=\Delta y_{max}.
تمام آزمونهای مورد نیاز الگوریتم را میتوان بر حسب (\Delta y_{max})، (\Delta y) و عبارات مشابه برای سایر اضلاع پنجره بازنویسی کرد. بنابراین همهٔ تصمیمهای مربوط به برش بدون تقسیم ممیز شناور انجام میشوند. فقط اگر واقعاً به یک تقاطع نیاز باشد—یعنی پارهخط باید کوتاه شود—تقسیم انجام خواهد شد. کارایی این روش نسبت به Cohen–Sutherland از آنجا ناشی میشود که از کوتاهسازی چندبارهٔ پارهخط و اجرای مجدد الگوریتم برش پرهیز میکنیم. الگوریتمهای کارآمد دوبعدی دیگری نیز وجود دارند، اما برخلاف Cohen–Sutherland و Liang–Barsky به سه بعد تعمیم مستقیم ندارند و در اینجا بررسی نمیشوند.
۶٫۵ برش چندضلعی
برش چندضلعی در موقعیتهای گوناگون مطرح میشود. قطعاً لازم است چندضلعیها را برای نمایش در برابر پنجرههای مستطیلی برش دهیم، اما گاهی ممکن است پنجره مستطیلی نباشد. بخشهای دیگری از پیادهسازی، مانند تولید سایه و حذف سطح پنهان، نیز ممکن است نیازمند برش چندضلعی در برابر چندضلعیهای دیگر باشند.
شکل ۶٫۹ — برش چندضلعی در تولید سایه.
برای مثال، شکل ۶٫۹ سایهٔ یک چندضلعی را نشان میدهد که با برش چندضلعی نزدیکتر به منبع نور در برابر چندضلعیهای دورتر ایجاد میشود. بسیاری از روشهای ضدهمپوشانی نیز بر توانایی برش یک چندضلعی در برابر چندضلعی دیگر متکیاند.
میتوان الگوریتمهای برش چندضلعی را مستقیماً از الگوریتمهای برش خط ساخت؛ کافی است یالهای چندضلعی را پیدرپی برش دهیم. اما باید به یاد داشته باشیم که چندضلعی یک شیء دوبعدی دارای ناحیهٔ داخلی است و بسته به شکل آن، برش میتواند بیش از یک شیء چندضلعی تولید کند. چندضلعی نامحدب یا مقعر شکل ۶٫۱۰(الف) را در نظر بگیرید. اگر آن را در برابر پنجرهای مستطیلی برش دهیم، نتیجهٔ شکل ۶٫۱۰(ب) حاصل میشود. بیشتر بینندگان نتیجه را سه چندضلعی جداگانه تلقی میکنند. متأسفانه، پیادهسازی Clipperی که بتواند تعداد اشیا را افزایش دهد میتواند مشکلساز باشد. میتوان نتیجه را مانند شکل ۶٫۱۱ یک چندضلعی واحد با یالهای همپوشان روی اضلاع پنجره در نظر گرفت، اما این انتخاب ممکن است در بخشهای دیگر پیادهسازی دشواری ایجاد کند.
شکل ۶٫۱۰ — برش یک چندضلعی مقعر: (الف) پیش از برش؛ (ب) پس از برش.
چندضلعیهای محدب چنین مشکلی ندارند. برش یک چندضلعی محدب در برابر پنجرهٔ مستطیلی حداکثر یک چندضلعی محدب باقی میگذارد. بنابراین سامانهٔ گرافیکی میتواند استفاده از چندضلعیهای مقعر را ممنوع کند یا چندضلعی دادهشده را به مجموعهای از چندضلعیهای محدب Tessellate کند، همانند شکل ۶٫۱۲. OpenGL 4.1 توابع Tessellation را نیز دربر دارد.
شکل ۶٫۱۱ — تشکیل یک چندضلعی واحد از نتیجهٔ برش.
برای ناحیههای برش مستطیلی، هر دو الگوریتم Cohen–Sutherland و Liang–Barsky را میتوان یالبهیال روی چندضلعیها اعمال کرد. رویکرد دیگری که Sutherland و Hodgeman توسعه دادهاند با معماریهای خط لولهای بهخوبی سازگار است.
میتوان Clipper پارهخط را جعبهٔ سیاهی در نظر گرفت که ورودی آن جفت رأس یک پارهخط و خروجی آن یا جفت رأس متناظر با پارهخط برشخورده است، یا هیچ چیز اگر پارهخط ورودی کاملاً بیرون پنجره باشد (شکل ۶٫۱۳).
به جای اینکه پنجرهٔ برش را چهار پارهخط بدانیم، میتوان آن را شیئی حاصل از تقاطع چهار خط بینهایت در نظر گرفت که اضلاع بالا، پایین، راست و چپ پنجره را مشخص میکنند. سپس میتوان Clipper را به خط لولهای از Clipperهای سادهتر تقسیم کرد که هر کدام در برابر یک خط—امتداد یکی از یالهای پنجره—برش میدهند. برای هر Clipper منفرد نیز میتوان دیدگاه جعبهٔ سیاه را به کار برد.
شکل ۶٫۱۲ — Tessellation یک چندضلعی مقعر به چندضلعیهای محدب.
شکل ۶٫۱۳ — دو دید از برش: (الف) برش در برابر مستطیل؛ (ب) Clipper به صورت جعبهٔ سیاه.
حال فقط برش در برابر ضلع بالای پنجره را در نظر بگیرید. این عملیات را میتوان جعبهٔ سیاهی دانست که ورودی و خروجی آن جفت رأس است و مقدار (y_{max}) بهعنوان پارامتر برای Clipper معلوم است (شکل ۶٫۱۴). از مثلثهای متشابه شکل ۶٫۱۵ میبینیم که اگر تقاطعی وجود داشته باشد، در نقطهٔ زیر قرار دارد:
x_3=x_1+(y_{max}-y_1)\frac{x_2-x_1}{y_2-y_1},
y_3=y_{max}.
شکل ۶٫۱۴ — برش در برابر ضلع بالا: (الف) نمایش هندسی؛ (ب) دید جعبهٔ سیاه.
بنابراین Clipper یکی از سه جفت زیر را بازمیگرداند:
- ({(x_1,y_1),(x_2,y_2)})
- ({(x_1,y_1),(x_i,y_{max})})
- ({(x_i,y_{max}),(x_2,y_2)})
میتوان در برابر خطوط پایین، راست و چپ نیز بهطور مستقل برش انجام داد؛ همان معادلات را با جابهجایی نقش x و y در صورت لزوم و جایگذاری مقادیر اضلاع پنجره استفاده میکنیم. چهار Clipper اکنون میتوانند در خط لولهٔ شکل ۶٫۱۶ مرتب شوند. اگر این ساختار در سختافزار ساخته شود، Clipperی خواهیم داشت که همزمان روی چهار رأس کار میکند. شکل ۶٫۱۷ نمونهای ساده از اثر Clipperهای پیدرپی روی یک چندضلعی را نشان میدهد.
شکل ۶٫۱۵ — تقاطع با بالای پنجره.
شکل ۶٫۱۶ — برش خط لولهای: (الف) مسئلهٔ برش؛ (ب) Clipperهای خط لولهای.
شکل ۶٫۱۷ — نمونهای از برش خط لولهای؛ هر مرحله چندضلعی حاصل از مرحلهٔ قبلی را در برابر یکی از اضلاع برش میدهد.
۶٫۶ برش سایر بدویها
در فصلهای ۱ تا ۵ تأکید ما بر نوشتن برنامههایی بود که اشیای آنها از پارهخطها و مثلثها ساخته میشدند. اشیای منحنی فصل ۱۰ را نیز اغلب با تقسیم آنها به چندضلعیهای کوچک و تقریباً تخت رندر میکنیم. در معماریهای خط لولهای معمولاً گونهای از Clipperهایی که معرفی شد به کار میرود. با این همه، موقعیتهایی وجود دارد که میخواهیم اشیا را پیش از رسیدن به سختافزار برش دهیم یا الگوریتمهایی بهینهشده برای بدویهای دیگر به کار ببریم.
۶٫۶٫۱ جعبهها و حجمهای محاطکننده
شکل ۶٫۱۸ — استفاده از Bounding Box: (الف) چندضلعی و پنجرهٔ برش؛ (ب) چندضلعی، جعبهٔ محاطکننده و پنجرهٔ برش.
فرض کنید چندضلعی پرضلعی شکل ۶٫۱۸(الف) را داریم. میتوان یکی از الگوریتمهای برش را اعمال کرد و تکتک یالهای آن را جداگانه برش داد. اما از شکل پیداست که کل چندضلعی بیرون پنجرهٔ برش قرار دارد. میتوان از این مشاهده با استفاده از جعبهٔ محاطکنندهٔ همراستا با محورها (Axis-Aligned Bounding Box یا AABB) یا Extent چندضلعی بهره برد؛ یعنی کوچکترین مستطیل همراستا با پنجره که کل چندضلعی را دربر میگیرد. محاسبهٔ این جعبه صرفاً به پیمایش رأسها و یافتن کمینه و بیشینهٔ مقادیر x و y نیاز دارد.
پس از در اختیار داشتن Bounding Box، اغلب میتوان از برش دقیق پرهیز کرد. سه حالت شکل ۶٫۱۹ را در نظر بگیرید. برای چندضلعی بالای پنجره هیچ برش دقیقی لازم نیست، زیرا کمینهٔ y جعبهٔ محاطکننده از لبهٔ بالایی پنجره بالاتر است. برای چندضلعی داخل پنجره نیز با مقایسهٔ Bounding Box و پنجره میتوان مستقیماً داخلبودن را تشخیص داد. فقط هنگامی که جعبهٔ محاطکننده مرز پنجره را قطع میکند لازم است برش دقیق با همهٔ یالهای چندضلعی انجام شود.
شکل ۶٫۱۹ — برش با استفاده از Bounding Boxها.
استفاده از Extentها در دو و سه بعد چنان تکنیک قدرتمندی است که سامانههای مدلسازی اغلب برای هر شیء بهطور خودکار یک Bounding Box محاسبه و همراه آن ذخیره میکنند.
AABB هم در دو بعد و هم در سه بعد کار میکند. در سه بعد میتوان در خود برنامه از آن برای برش اولیه و کاهش بار خط لوله بهره گرفت. حجمهای دیگری مانند کره نیز میتوانند مناسب باشند. یکی از کاربردهای مهم حجمهای محاطکننده، تشخیص برخورد است. یکی از عملیات بنیادی در پویانمایی بازیهای رایانهای تعیین برخورد دو موجودیت متحرک است. برای نمونه، دو شخصیت متحرک را در دنبالهای از تصاویر در نظر بگیرید. باید لحظهٔ برخورد آنها را بدانیم تا مسیرشان را تغییر دهیم. این مسئله شباهت زیادی به برش دارد، زیرا میخواهیم بدانیم حجم یکی چه زمانی با حجم دیگری تقاطع پیدا میکند. پیچیدگی اشیا و الزام انجام بسیار سریع این محاسبات مسئله را دشوار میکند. یک راهبرد رایج قرار دادن هر شیء در یک حجم محاطکننده—AABB یا کره—و بررسی تقاطع حجمهاست. فقط در صورت وجود تقاطع است که محاسبات دقیق انجام میشوند.
۶٫۶٫۲ منحنیها، سطوح و متن
شکل ۶٫۲۰ — برش منحنی.
تنوع منحنیها و سطوحی که میتوان بهصورت ریاضی تعریف کرد، یافتن الگوریتمهای عمومی برای پردازش آنها را دشوار میکند. منحنیهای دوبعدی شکل ۶٫۲۰ نمونهای از این دشواریاند. برای منحنی سادهای مانند یک Quadric میتوان نقاط تقاطع را محاسبه کرد، هرچند هزینهٔ آن از خط بیشتر است. برای منحنیهای پیچیدهتر مانند مارپیچ، نهتنها تقاطعها باید با روشهای عددی محاسبه شوند، بلکه حتی تعیین تعداد تقاطعهای مورد نیاز نیز میتواند دشوار باشد. این مشکلات را میتوان با تقریب منحنیها توسط پارهخطها و سطوح توسط چندضلعیهای تخت کاهش داد. Bounding Box نیز بسیار مفید است، بهخصوص در مواردی مثل منحنیهای درجهٔ دو که میتوان تقاطع را دقیق محاسبه کرد اما ترجیح میدهیم پیش از انجام محاسبه مطمئن شویم واقعاً لازم است.
نحوهٔ مدیریت متن بین APIها متفاوت است و بسیاری از APIها به کاربر اجازه میدهند میزان جزئیات رندر متن را مشخص کند. دو حالت حدی وجود دارد. در یک سوی طیف، متن به شکل الگوهای بیتی ذخیره میشود و بدون پردازش هندسی مستقیماً توسط سختافزار رندر میگردد؛ هر برش لازم نیز در بافر فریم انجام میشود. در سوی دیگر، متن مانند هر شیء هندسی دیگری تعریف و سپس از خط لولهٔ استاندارد مشاهده عبور داده میشود. OpenGL با نداشتن یک بدوی جداگانه برای متن، هر دو حالت را امکانپذیر میکند. کاربر میتواند با تعریف نویسههای Bitmap از طریق عملیات پیکسلی یا نویسههای Stroke از طریق بدویهای استاندارد، روش دلخواه را انتخاب کند.
۶٫۶٫۳ برش در بافر فریم
همچنین میتوان برش را تا پس از تصویرشدن اشیا و تبدیلشان به مختصات صفحه به تأخیر انداخت. در بافر فریم، برش با تکنیکی به نام Scissoring انجام میشود. با این حال، معمولاً بهتر است موجودیتهای هندسی پیش از رسیدن رأسها به بافر فریم برش بخورند؛ ازاینرو برش درون بافر فریم عمدتاً برای اشیای رستری مانند بلوکهای پیکسلی لازم است.
۶٫۷ برش در سه بعد
در سه بعد، به جای یک ناحیهٔ محدود روی صفحه، در برابر یک حجم محدود برش میدهیم. سادهترین گسترش برش دوبعدی به سه بعد برای ناحیهٔ برشِ متوازیالسطوح قائم است.
شکل ۶٫۲۱ — برش سهبعدی در برابر یک متوازیالسطوح قائم.
ناحیهٔ برش سهبعدی با قیود زیر تعریف میشود:
x_{min}\le x\le x_{max},
y_{min}\le y\le y_{max},
z_{min}\le z\le z_{max},
و در فضای Clip:
-w\le x\le w,
-w\le y\le w,
-w\le z\le w.
سه الگوریتم برش Cohen–Sutherland، Liang–Barsky و Sutherland–Hodgeman و نیز استفاده از Extentها همگی به سه بعد قابل گسترشاند. در Cohen–Sutherland، Outcode چهار بیتی با Outcode شش بیتی جایگزین میشود. دو بیت اضافه زمانی تنظیم میشوند که نقطه در جلو یا پشت حجم برش باشد (شکل ۶٫۲۲). راهبرد آزمون در دو و سه بعد تقریباً یکسان است.
برای Liang–Barsky معادلهٔ زیر را اضافه میکنیم:
z(\alpha)=(1-\alpha)z_1+\alpha z_2,
تا نمایش پارامتری سهبعدی پارهخط حاصل شود. باید شش تقاطع با سطوح سازندهٔ حجم برش را در نظر بگیریم، اما منطق تصمیمگیری همان منطق حالت دوبعدی است. Clipperهای خط لولهای نیز دو ماژول دیگر برای برش در برابر جلوی و پشت حجم اضافه میکنند.
تفاوت اصلی Clipper دوبعدی و سهبعدی این است که در سه بعد، یا خطها را در برابر صفحهها و یا چندضلعیها را در برابر صفحهها برش میدهیم، نه خط را در برابر خط.
شکل ۶٫۲۲ — ناحیههای Cohen–Sutherland در سه بعد؛ دو بیت افزوده موقعیت جلو/پشت حجم برش را نشان میدهند.
بنابراین محاسبات تقاطع نیز باید تغییر کنند. یک محاسبهٔ معمول را میتوان به صورت تقاطع یک خط پارامتری سهبعدی با یک صفحه بیان کرد (شکل ۶٫۲۳). اگر معادلهٔ خط و صفحه را در فرم برداری بنویسیم، که در آن n بردار نرمال صفحه و (p_0) نقطهای روی صفحه است، باید معادلات زیر حل شوند:
p(\alpha)=(1-\alpha)p_1+\alpha p_2,
n\cdot(p(\alpha)-p_0)=0.
مقدار پارامتر متناظر با نقطهٔ تقاطع برابر است با:
\alpha=\frac{n\cdot(p_0-p_1)}{n\cdot(p_2-p_1)}.
شکل ۶٫۲۳ — تقاطع صفحه و خط.
محاسبهٔ یک تقاطع در حالت عمومی شش ضرب و یک تقسیم نیاز دارد. با این حال، اگر حجمهای استاندارد مشاهده را بررسی کنیم، سادهسازیهایی امکانپذیر است. برای مشاهدهٔ متعامد (شکل ۶٫۲۴)، حجم دید یک متوازیالسطوح قائم است و هر محاسبهٔ تقاطع مانند برش دوبعدی به تنها یک تقسیم کاهش مییابد.
در مشاهدهٔ مایل (شکل ۶٫۲۵)، حجم برش دیگر متوازیالسطوح قائم نیست. ممکن است تصور شود برای برش در برابر اضلاع حجم باید ضرب داخلی انجام دهیم، اما اینجاست که فرایند نرمالسازی فصل ۴ سود خود را نشان میدهد. نشان دادیم تصویرسازی مایل معادل Shear کردن داده و سپس انجام تصویرسازی متعامد است. هرچند تبدیل Shear اشیا را اعوجاج میدهد، این اعوجاج بهگونهای است که تصویرسازی متعامد نتیجهٔ درست را تولید میکند. Shear همچنین حجم برش را از یک متوازیالسطوح عمومی به متوازیالسطوح قائم تبدیل میکند. شکل ۶٫۲۶(الف) نمای بالای حجم مایل و مکعب داخل آن را پیش از Shear نشان میدهد.
شکل ۶٫۲۴ — برش برای مشاهدهٔ متعامد.
شکل ۶٫۲۵ — برش برای مشاهدهٔ مایل.
شکل ۶٫۲۶ — اعوجاج حجم دید بر اثر Shear: (الف) نمای بالا پیش از Shear؛ (ب) نمای بالا پس از Shear.
شکل ۶٫۲۶(ب) حجم و شیء را پس از اعوجاج ناشی از Shear نشان میدهد. از دید تصویرسازی، انجام مستقیم تبدیل مایل یا جایگزینی آن با تبدیل Shear و تصویرسازی متعامد مقدار محاسبهٔ یکسانی میخواهد. اما وقتی برش را نیز اضافه کنیم، روش دوم مزیت آشکاری دارد، زیرا میتوان در برابر متوازیالسطوح قائم برش داد. این نمونه اهمیت درنظرگرفتن ماهیت افزایشی مراحل پیادهسازی را نشان میدهد. تحلیل جداگانهٔ تصویرسازی یا برش نمیتواند اهمیت فرایند نرمالسازی را آشکار کند.
برای تصویرسازی پرسپکتیو نیز استدلال به همان اندازه قوی است. با انجام تبدیل نرمالسازی پرسپکتیو فصل ۴، اما بدون انجام تصویرسازی متعامد نهایی، دوباره یک حجم برش مستطیلی ایجاد میکنیم و همهٔ محاسبات تقاطع بعدی ساده میشوند.