پرش به محتوا

حذف خط پنهان

از ویکی‌پدیا، دانشنامهٔ آزاد
یک تصویر قاب سیمی با استفاده از حذف خط پنهان

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

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

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

اندازه‌های مساله برای حذف خطوط پنهان ،n  تعداد کل ضلع‌های مدل و v تعداد کل بخش‌های پديدار ضلع‌هاست. پديداری می‌تواند در نقاط تقاطع تصوير ضلع‌ها تغيير کند. فرض می‌کنيم k تعداد کل نقطه‌های برخورد تصوير ضلع‌ها است. هردوی k = Θ(n2) و v = Θ(n2) در بدترين حالت هستند ،[۴] اما معمولا v < k است.

الگوریتم ها

[ویرایش]

الگوريتم‌ حذف خطوط که تا قبل از 1984 منتشر شده بود ،[۵][۶][۷][۸] ضلع‌ها را  با استفاده از نقاط برخورد تصويرشان به مجموعه‌ای از پاره‌خط‌ها تقسيم می‌کرد ، و بعد هربخش را برای پديداری در مقابل هروجه مدل تست می‌کرد. با فرض اينکه يک مدل مجموعه‌ای از چندوجهی‌هاست که مرز هرکدام از نظر توپولوژيکی معادل يک کره و وجه‌هايشان هم معادل ديسک‌ها هستند ، مطابق فرمول اويلری ، Θ(n) وجه وجود دارد. تست کردن Θ(n2) بخش خط در مقابل Θ(n) وجه ، در بدترين حالت Θ(n3) زمان می‌برد.[۴] الگوريتم اپل (Appel)[۵] هم ناپايدار است ، چون يک خطا در پديداری به نقاط انتهايی بخش‌های بعدی منتقل می‌شود.[۹]

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

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

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

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

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

الگوریتم های موازی

[ویرایش]

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

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

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

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

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

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

[ویرایش]

منابع

[ویرایش]
  1. ↑ L. G. Roberts. Machine perception of three-dimensional solids. PhD thesis, Massachusetts Institute of Technology, 1963.
  2. ↑ Ruth A. Weiss BE VISION, A Package of IBM 7090 FORTRAN Programs to Draw Orthographic Views of Combinations of Plane and Quadric Surfaces
  3. ↑ I. E. Sutherland. Ten unsolved problems in computer graphics. Datamation, 12(5):22–27, 1966.
  4. ↑ ۴٫۰ ۴٫۱ ۴٫۲ ۴٫۳ ۴٫۴ F. Devai. Quadratic bounds for hidden line elimination. In Proc. 2nd Annual Symp. on Computational Geometry, SCG ’86, pp. 269–275, New York, NY, USA, 1986.
  5. ↑ ۵٫۰ ۵٫۱ A. Appel. The notion of quantitative invisibility and the machine rendering of solids. In Proc. 22nd National Conference, ACM ’67, pp. 387–393, New York, NY, USA, 1967.
  6. ↑ R. Galimberti and U. Montanari. An algorithm for hidden line elimination. Commun. ACM, 12(4):206–211, April 1969.
  7. ↑ Ch. Hornung. An approach to a calculation-minimized hidden line algorithm. Computers & Graphics, 6(3):121–126, 1982.
  8. ↑ P. P. Loutrel. A solution to the hidden-line problem for computer-drawn polyhedra. IEEE Trans. Comput., 19(3):205–213, March 1970.
  9. ↑ J. F. Blinn. Fractional invisibility. IEEE Comput. Graph. Appl., 8(6):77–84, November 1988..
  10. ↑ ۱۰٫۰ ۱۰٫۱ Th. Ottmann and P. Widmayer. Solving visibility problems by using skeleton structures. In Proc. Mathematical Foundations of Computer Science 1984, pp. 459–470, London, UK, 1984. Springer-Verlag.
  11. ↑ ۱۱٫۰ ۱۱٫۱ Th. Ottmann, P. Widmayer, and D. Wood. A worst-case efficient algorithm for hidden-line elimination. Internat. J. Computer Mathematics, 18(2):93–119, 1985.
  12. ↑ ۱۲٫۰ ۱۲٫۱ O. Nurmi. A fast line-sweep algorithm for hidden line elimination. BIT, 25:466–472, September 1985..
  13. ↑ M. L. Fredman and B. Weide. On the complexity of computing the measure of U[ai, bi]. Commun. ACM, 21:540–544, July 1978.
  14. ↑ M. McKenna. Worst-case optimal hidden-surface removal. ACM Trans. Graph., 6:19–28, January 1987.
  15. ↑ Sh. Ghali. A survey of practical object space visibility algorithms. SIGGRAPH Tutorial Notes, 1(2), 2001.
  16. ↑ F. Devai. An O(log N) parallel time exact hidden-line algorithm. Advances in Computer Graphics Hardware II, pp. 65–73, 1988.
  17. ↑ Reif, J. H.; Sen, S. (1988). "An efficient output-sensitive hidden surface removal algorithm and its parallelization". Proceedings of the fourth annual symposium on Computational geometry - SCG '88. New York, New York, USA: ACM Press. doi:10.1145/73393.73413.
  18. ↑ F. Devai. An optimal hidden-surface algorithm and its parallelization. In Computational Science and Its Applications, ICCSA 2011, volume 6784 of Lecture Notes in Computer Science, pp 17–29. Springer Berlin/Heidelberg, 2011.
  19. ↑ Cook, Stephen; Dwork, Cynthia; Reischuk, Rüdiger (1986-02). "Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes". SIAM Journal on Computing. 15 (1): 87–97. doi:10.1137/0215006. ISSN 0097-5397. {{cite journal}}: Check date values in: |date= (help)

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

[ویرایش]
برگرفته از «https://fa.wikipedia.org/w/index.php?title=حذف_خط_پنهان&oldid=39759255»