حذف خط پنهان کیست؟ توضیح بده.
در گرافیک کامپیوتری سه بعدی ، اشیاُء در هندسه فضایی معمولا با چندوجهی‌ها مدل‌سازی می‌شوند. یک وجه چندوجهی، چندضلعی مسطحی‌ست که توسط پاره‌خط‌های مستقیم که ضلع نامیده می‌شوند، محدود شده است. سطوح منحنی معمولاً با شبکه‌ای از چندضلعی‌ها تقریب زده می‌شوند. برنامه‌های کامپیوتری برای رسم خطوط اشیاء مات باید قادر باشند تصمیم بگیرند که کدام ضلع یا کدام قسمت از ضلع‌ها توسط خود شیء یا اشیاء دیگر پنهان شده‌اند تا بتوانند آن لبه‌ها را در هنگام رندر کردن برش دهند. این مشکل به عنوان حذف خطوط پنهان شناخته می‌شود.اولین راه‌ حل شناخته شده برای مساله حذف خطوط پنهان توسط ال.جی.رابرتز در سال 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" &lt; "k است."الگوریتم ها.الگوریتم‌ حذف خطوط که تا قبل از 1984 منتشر شده بود ، ضلع‌ها را با استفاده از نقاط برخورد تصویرشان به مجموعه‌ای از پاره‌خط‌ها تقسیم می‌کرد ، و بعد هربخش را برای پدیداری در مقابل هروجه مدل تست می‌کرد. با فرض اینکه یک مدل مجموعه‌ای از چندوجهی‌هاست که مرز هرکدام از نظر توپولوژیکی معادل یک کره و وجه‌هایشان هم معادل دیسک‌ها هستند ، مطابق فرمول اویلری ، Θ("n") وجه وجود دارد. تست کردن Θ("n"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" پردازنده برای مسئله خط پنهان به زمان ثابت کاهش‌پذیر است. بنابراین، الگوریتم خط پنهان زمان بهینه دارد.