3D графикада көрінетін беттерді анықтау алгоритмі: «Суретші алгоритмі» қалай жұмыс істейді, тереңдік бойынша полигондарды қалай реттейді, жасырылған беттерді қалай жояды?
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
3D графикада көрінетін бетті анықтау алгоритмі
Algorithm for visible surface determination in 3D graphics
Суретшінің алгоритмі (сонымен қатар тереңдік бойынша сұрыптау алгоритмі және басымдықпен толтыру) – 3D компьютерлік графикада көрінетін бетті анықтау алгоритмі. Бұл алгоритм басқа жасырын беттерді жою алгоритмдерінен айырмалы, пиксель бойынша, қатар бойынша немесе аудан бойынша емес, көпбұрыш бойынша жұмыс істейді. Суретшінің алгоритмі суретті жасау үшін, суреттегі көпбұрыштарды тереңдігі бойынша сұрыптап, ең алыс объектіден ең жақын объектіге дейін реттейді. Суретшінің алгоритмі алғаш рет 1972 жылы Мартин Ньюэлл, Ричард Ньюэлл және Том Санча CADCentre-де жұмыс істеген кезде жасырын бетті анықтау мәселесін шешудің қарапайым әдісі ретінде ұсынылды. "Суретшінің алгоритмі" деген атау көптеген суретшілер қолданатын техникаға сілтеме жасайды, олар көріністің алыс бөліктерін жақын бөліктерге дейін суреттейді, соның салдарынан алыс бөліктердің кейбір бөліктерін жабады. Сол сияқты, суретшінің алгоритмі сахнадағы барлық көпбұрыштарды тереңдігі бойынша сұрыптап, содан кейін оларды осы ретпен, ең алыс нүктеден ең жақын нүктеге дейін "бояйды". Бұл әдетте көрінбейтін бөліктерді жабады, осылайша көріну мәселесін шешеді, бірақ алыстағы объектілердің көрінбейтін бөліктерін бояудың құнына. Алгоритм қолданатын рет "тереңдік тәртібі" деп аталады және көріністің бөліктеріне сандық қашықтықты қатаң сақтаудың қажеті жоқ: осы тәртіптің ең маңызды қасиеті – егер бір нысан екінші нысанның бөлігін жасыратын болса, онда бірінші нысан жасырылған нысаннан кейін боялады.
The painter's algorithm (also depth sort algorithm and priority fill) is an algorithm for visible surface determination in 3D computer graphics that works on a polygon by polygon basis rather than a pixel by pixel, row by row, or area by area basis of other Hidden Surface Removal algorithms. The painter's algorithm creates images by sorting the polygons within the image by their depth and placing each polygon in order from the farthest to the closest object. The painter's algorithm was initially proposed as a basic method to address the Hidden surface determination problem by Martin Newell, Richard Newell, and Tom Sancha in 1972, while all three were working at CADCentre. The name "painter's algorithm" refers to the technique employed by many painters where they begin by painting distant parts of a scene before parts that are nearer, thereby covering some areas of distant parts. Similarly, the painter's algorithm sorts all the polygons in a scene by their depth and then paints them in this order, farthest to closest. It will paint over the parts that are normally not visible — thus solving the visibility problem — at the cost of having painted invisible areas of distant objects. The ordering used by the algorithm is called a 'depth order' and does not have to respect the numerical distances to the parts of the scene: the essential property of this ordering is, rather, that if one object obscures part of another, then the first object is painted after the object that it obscures.
Уақыт күрделілігі
Суретшінің алгоритмінің уақыт күрделілігі көпбұрыштарды реттеуге қолданылатын сұрыптау алгоритміне тікелей байланысты. Ең оңтайлы сұрыптау алгоритмі қолданған жағдайда, суретшінің алгоритмінің ең нашар жағдайдағы күрделілігі O(n log n + m*n) болады, мұнда n – көпбұрыштардың саны, ал m – толтырылатын пиксельдердің саны.
The painter's algorithm's time complexity is heavily dependent on the sorting algorithm used to order the polygons. Assuming the use of the most optimal sorting algorithm, painter's algorithm has a worst case complexity of O(n log n + m*n), where n is the number of polygons and m is the number of pixels to be filled.
Ғарыштық күрделілік
Суретшінің алгоритмінің ең нашар жағдайдағы жадтың күрделілігі O(n+m) тең, мұнда n – көпбұрыштар саны, ал m – толтырылатын пиксельдер саны.
The painter's algorithm's worst case space complexity is O(n+m), where n is the number of polygons and m is the number of pixels to be filled.
Артықшылықтар
Суретшінің алгоритмін қолдануға ыңғайлы екі маңызды техникалық шарттар бар.
There are two primary technical requisites that favor the use of the painter's algorithm.
Негізгі графикалық құрылым
Суретшінің алгоритмі басқа тереңдік бойынша сұрыптау алгоритмдерімен салыстырғанда құрылысы жағынан күрделі емес. Суретшінің алгоритмінде қолданылатын тереңдікке негізделген рендеринг тәртібі сияқты компоненттер – графикалық өндіріс ретін анықтаудың ең оңай жолдарының бірі. Бұл бағдарламалардың үлкен тапсырмаларды орындау үшін жадты мүмкіндігінше тиімді басқаруын қажет етті, сондайынша құлап түспесін. Суретшінің алгоритмі жадты тиімді пайдалануға басымдық береді, бірақ барлық суреттердің барлық бөліктерін көрсету қажет болғандықтан, бұл жоғары өңдеу қуатының қажеттілігіне әкеледі. Мұндай жүйелерде де суретшінің алгоритмінің түрі кейде қолданылады. Z-буферді іске асыру көбінесе аппараттық құралдардағы белгілі бір дәлдіктегі тереңдік буферлік тіркегіштерге сүйенгендіктен, дөңгелектеу қатесінен туындаған көріну проблемалары болуы мүмкін. Бұл көпбұрыштардың бірігіп тұрған жерлерінде қабаттасулар немесе кеңістіктер тудыруы мүмкін. Мұны болдырмау үшін кейбір графикалық қозғалтқыштар "артық рендерингті" (over rendering) іске асырады, суретшінің алгоритмімен көрсетілген тәртіпте екі көпбұрыштың зардап шеккен жиектерін салады. Бұл кейбір пиксельдердің екі рет салынуын білдіреді (толық суретшінің алгоритміндегідей), бірақ бұл тек суреттің шағын бөліктерінде ғана болады және өнімділікке елеусіз әсер етеді.
The painter's algorithm is not as complex in structure as its other depth sorting algorithm counterparts. Components such as the depth based rendering order, as employed by the painter's algorithm, are one of the simplest ways to designate the order of graphical production. This required programs to manage memory as efficiently as possible to conduct large tasks without crashing. The painter's algorithm prioritizes the efficient use of memory but at the expense of higher processing power since all parts of all images must be rendered. Even in such systems, a variant of the painter's algorithm is sometimes employed. As Z buffer implementations generally rely on fixed precision depth buffer registers implemented in hardware, there is scope for visibility problems due to rounding error. These are overlaps or gaps at joints between polygons. To avoid this, some graphics engines implement "over rendering", drawing the affected edges of both polygons in the order given by the painter's algorithm. This means that some pixels are actually drawn twice (as in the full painter's algorithm), but this happens on only small parts of the image and has a negligible performance effect.