حذف خط پنهان

بندانگشتی|200x200پیکسل|یک تصویر قاب سیمی با استفاده از حذف خط پنهان
در گرافيک کامپيوتری سه بعدی ، اشياُء در هندسه فضايی معمولا با چندوجهی‌ها مدل‌سازی می‌شوند. يک وجه چندوجهی، چندضلعی مسطحی‌ست که توسط پاره‌خط‌های مستقيم که ضلع ناميده می‌شوند، محدود شده است. سطوح منحنی معمولاً با شبکه‌ای از چندضلعی‌ها تقريب زده می‌شوند. برنامه‌های کامپيوتری برای رسم خطوط اشياء مات بايد قادر باشند تصميم بگيرند که کدام ضلع يا کدام قسمت از ضلع‌ها توسط خود شیء يا اشياء ديگر پنهان شده‌اند تا بتوانند آن لبه‌ها را در هنگام رندر کردن برش دهند. اين مشکل به عنوان **حذف خطوط پنهان** شناخته می‌شود.

اولين راه‌ حل شناخته شده برای مساله حذف خطوط پنهان توسط ال.جی.رابرتز  در سال 1963 ابداع شد. اما به شدت مدل را محدود می‌کرد زیرا لازم بود که تمام اشياُء محدب باشند. Ruth A. Weiss از آزمايشگاه Bell  راه حل 1964 خود را در سال 1965 در روزنامه ثبت کرد. ایوان سادرلند (Ivan E. Sutherland)در سال 1966، 10 مساله غيرقابل حل گرافيک کامپيوتری را ليست کرد. مساله هفتم "*حذف خطوط پنهان*" بود. از لحاظ پيچيدگی محاسباتی ، اين مساله توسط فرانک دوای (Frank Devai) در سال 1986 حل شد.

مدل‌ها ، به عنوان مثال در طراحی به کمک رايانه ، می‌توانند هزاران يا ميليون‌ها ضلع داشته باشند. پس رویکرد پيچيدگی محاسباتی که نيازهای منابع (مانند زمان و حافظه) را به عنوان تابعی از اندازه مساله بيان می‌کند خيلی مهم است. نيازهای زمانی به‌ويژه در سيستم‌های تعاملی مهم هستند.

اندازه‌های مساله برای حذف خطوط پنهان ،n  تعداد کل ضلع‌های مدل و v تعداد کل بخش‌های پديدار ضلع‌هاست. پديداری می‌تواند در نقاط تقاطع تصوير ضلع‌ها تغيير کند. فرض می‌کنيم k تعداد کل نقطه‌های برخورد تصوير ضلع‌ها است. هردوی *k* = Θ(*n*2) و *v* = Θ(*n*2) در بدترين حالت هستند ، اما معمولا *v* 2) بخش خط در مقابل Θ(*n*) وجه ، در بدترين حالت Θ(*n*3) زمان می‌برد. الگوريتم اپل (Appel) هم ناپايدار است ، چون يک خطا در پديداری به نقاط انتهايی بخش‌های بعدی منتقل می‌شود.

اوتمن و ويدماير (Ottmann , Widmayer) و اوتمن ، ويدماير و وود (Wood) الگوريتمی با پيچيدگی زمانی *O*((*n* + *k*) log2 *n*) مطرح کردند. سپس نورمی (Nurmi) با زمان اجرا *O*((*n* + *k*) log *n*) آن را بهبود بخشيد. اين الگوريتم‌ها در بدترين حالت Θ(*n*2 log2 *n*) و Θ(*n*2 log *n*) زمان نياز دارند ، اما اگر *k* کمتر از مرتبه درجه دو باشد ، می‌تواند در عمل کمتر باشد.

هر الگوريتم حذف خطوط پنهان بايد اجتماع Θ(*n*) فاصله‌های پنهان روی n ضلع را در بدترين حالت تعيين کند. از آنجايی که Ω(*n* log *n*) کمترين حد برای تعيين اجتماع فاصله‌‌هاست ، خوش‌بينانه‌ترين زمان در بدترين حالت ، Θ(*n*2 log *n*) است و بنابراين الگوريتم نورمی بهينه است.

اگرچه ضريب log *n*  توسط دوای حذف شد ، که مسئله باز را مطرح کرد که آيا همان حد بالای بهينه *O*(*n*2) برای حذف سطح پنهان وجود دارد يا خير. اين مساله توسط مک‌کنا (McKenna) در سال 1987 حل شد.

الگوريتم‌های حساس به برخورد بيشتر در مبحث هندسه محاسباتی شناخته شده‌اند. حدود بالای درجه دوم نيز در ادبيات گرافيک کامپيوتری مورد توجه قرار گرفته‌اند : غالی (Ghali) ذکر می‌کند که الگوريتم‌های دواي و مک‌کنا "نقاط عطفی در الگوريتم‌های پديداری هستند" و يک مانع نظری را از *O*(*n*2 log *n*) به *O*(*n*2) برای پردازش صحنه‌ای با *n* ضلع شکستند.

مسئله باز ديگری ، که توسط دواي مطرح شد ، اين است که آيا يک الگوريتم خط پنهان با زمان *O*(*n* log *n* + *v*) وجود دارد يا نه ، که *v* همان‌طور که در بالا ذکر شد، تعداد بخش‌های قابل مشاهده است. اين مساله تا زمان نگارش هنوز حل نشده است.

## الگوریتم های موازی
در سال 1988، دواي يک الگوريتم موازی با زمان *O*(log *n*) با استفاده از *n*2 پردازنده برای مساله خطوط پنهان در مدل محاسباتی ماشين موازی دسترسی تصادفی (PRAM) با خواندن همزمان و نوشتن انحصاری (CREW) مطرح کرد. ز آنجا که حاصل‌ضرب تعداد پردازنده‌ها و زمان اجرا به صورت مجانبی بيشتر از Θ(*n*2) است، پيچيدگی ترتيبی مسئله، الگوريتم از لحاظ کاری بهينه نيست ، اما نشان می‌دهد که مسئله خط پنهان در کلاس پيچيدگی NC است ، يعنی می‌توان آن را در زمان چندلگاری با استفاده از تعداد چندجمله‌ای از پردازنده‌ها حل کرد.

الگوريتم‌های حذف سطوح پنهان را می‌توان برای حذف خطوط پنهان استفاده کرد ، ولی برعکس آن ممکن نيست. ريف(Reif) و سن(Sen) يک الگوريتم با زمان *O*(log4 *n*) برای مسئله سطح پنهان پيشنهاد کردند که از *O*((*n* + *v*)/log *n*) پردازنده‌های CREW PRAM برای مدلی محدود از زمين‌های چندوجهی استفاده می‌کند، که در آن *v* اندازه خروجی است.

در سال 2011، دواي يک الگوريتم سطح پنهان با زمان *O*(log *n*) و يک الگوريتم خط پنهان ساده‌تر و با زمان *O*(log *n*) منتشر کرد. الگوريتم سطح پنهان با استفاده از *n*2/log *n* پردازنده‌های CREW PRAM، در عمل بهينه است.

الگوريتم خط پنهان از *n*2 پردازنده‌های EREW PRAM استفاده می‌کند. مدل EREW نزديک‌ترين نوع PRAM به ماشين‌های واقعی است. الگوريتم خط پنهان *O*(*n*2 log *n*) کار انجام می‌دهد که در عمل حد بالای بهترين الگوريتم‌های ترتيبی مورد استفاده است.

کوک(Cook) ، دورک(Dwork) و ريشکوک(Reischuk) يک حد پايين Ω(log *n*) برای يافتن حداکثر *n* عدد صحيح با استفاده از تعداد بی‌نهايت پردازنده از هر مدلی از PRAM بدون نوشتن همزمان ارائه کردند. يافتن حداکثر *n* عدد صحيح با استفاده از *n* پردازنده برای مسئله خط پنهان به زمان ثابت کاهش‌پذير است. بنابراين، الگوريتم خط پنهان زمان بهينه دارد.

## همچنین ببینید

* حذف پشت صورت

## منابع


## لینک های خارجی

* پایان نامه Patrick-Gilles Maillot ، توسعه الگوریتم خط کشی Bresenham برای حذف خطوط پنهان سه بعدی. همچنین در مقالات MICAD '87 در مورد CAD/CAM و گرافیک کامپیوتری، صفحه 591 منتشر شده است. .
* بردار حذف خط پنهان ، مقاله ای از والتر هگر با توضیحات بیشتر (در مورد موارد پاتولوژیک) و نقل قول های بیشتر.

رده:رندرینگ سه‌بعدی
رده:الگوریتم‌های گرافیک رایانه