Суреттегі бояу және текстураны толтыру алгоритмі

Кіріспе

Компьютерлік графикада түс немесе текстура қосу алгоритмі. Топан су арнау, сондай-ақ тұқым арнау деп аталатын бұл алгоритм, көп өлшемді массивтегі белгілі бір түйінге байланысты, сәйкес келетін қасиеттері бар аймақты анықтап, өзгертеді. Ол бояу бағдарламаларындағы "шелек" құралы арқылы байланысты, ұқсас түсті аймақтарды басқа түспен толтыруға, сондай-ақ Go және Minesweeper сияқты ойындарда қандай элементтерді тазалау керектігін анықтауға қолданылады. Шекара арнау деп аталатын түрінде де сол алгоритмдер қолданылады, бірақ ол белгілі бір қасиеті жоқ, берілген түйінге байланысты аймақ ретінде анықталады. Топан су арнау толтырылған көпбұрыштарды салуға қолайлы емес екенін ескеріңіз, себебі ол өткір бұрыштардағы кейбір пиксельдерді жіберіп алады. Оның орнына, Жұп-тақ ережесі мен Нөлдік ережесін қараңыз.

Алгоритмнің параметрлері

Дәстүрлі топан су толтыру алгоритмі үш параметрді қабылдайды: бастапқы түйін, мақсатты түс және алмастыру түсі. Алгоритм массивтегі бастапқы түйінге мақсатты түс арқылы байланысқан барлық түйіндерді іздейді және оларды алмастыру түсіне өзгертеді. Шекараны толтыру үшін мақсатты түс орнына шекара түсі беріледі. Алгоритмді жалпылау үшін, келесі сипаттамаларда екі процедура қолжетімді болады. Біреуі – Inside, ол толтырылмаған және түсі бойынша толтырылатын аймақ ішінде болатын нүктелер үшін true мәнін қайтарады, екіншісі – Set, ол пикселді/түйінді толтырады. Set шақырылған кез келген түйін енді Inside-те болмауы керек. Түйіндер бұрыштарынан жанасқанда байланысқан деп есептесек, екі нұсқасы бар: сегіз және төрт бағытты.

Қосымша оңтайландырулар

Қатарға/кезекке қосу алдында әрбір түйіндің пикселдік түсін тексеріп, орнатыңыз, соның арқасында қатардың/кезектің көлемін азайтыңыз. Шығыс/батыс бағыттары үшін цикл қолданыңыз, сол бағытта жоғарыдағы/төмендегі пиксельдерді кезекке қосыңыз (бұл аралықты толтыру алгоритмдеріне ұқсас болады). Ретсіз процессорларға көбірек параллельдеу мүмкіндігін беру үшін, қосымша стектермен/кезектермен кодтың екі немесе одан да көп көшірмесін біріктіріңіз. Ең тиімді нәтиже үшін, әртүрлі келу ретімен бірнеше жіпті пайдаланыңыз (сол арқылы олар бір аймақта тоқтап қалмайды).

Артықшылықтар

Өте қарапайым алгоритм, оны қатесіз жасау оңай.

Кемшіліктер

Жадыны көп пайдаланады, әсіресе стек қолданғанда. Толыққан пикселдердің көп бөлігін барлығы төрт рет тексереді. Үлгімен толтыруға қолайлы емес, себебі пикселдік тест нәтижелерінің өзгеруі қажет. Кезекке қою түрі үшін жадқа жылдам қол жеткізуге мүмкіндік бермейді. Көп пикселдік сөздерді немесе биттік жазықтықтарды оңай оңтайландыруға болмайды.

Артықшылықтар

Пикселдік рекурсивті алгоритмнен 2-ден 8 есеге дейін жылдам. Деректерге қолжеткізу үлгісі кэш және биттік жазықтар үшін қолайлы. Жеке пикселдерді орнатудың орнына көлденең сызық салу мүмкіндігі бар.

Кемшіліктер

Ол бұрын толтырған пикселдерді қайта қарастырады. (Танымал алгоритм үшін пикселдердің көпшілігі 3 рет сканерленеді. Ал соңғы сканерлеу кезінде, тек толтырылған аймақтағы тесіктерге ғана қосымша сканерлеу жасалады.) Үлгімен толтыруға қолайсыз, себебі пикселдерді тексеру нәтижелерінің өзгеруі қажет.

Үлгі толтыруды қолдау құралын қосу

Спан мен пикселге негізделген алгоритмдерге үлгімен толтыру мүмкіндігін қосудың екі кең таралған жолы бар: бірегей түсті қарапайым толтыру ретінде пайдаланып, кейін оны үлгімен алмастыру, немесе қандай пикселдерге барылғанын (2D логикалық массивте немесе аймақтар түрінде) есте сақтап, осы арқылы пикселдердің енді толтырылмайтынын белгілеу. Мұндай пикселдер үшін Inside функциясы false мәнін қайтаруы тиіс.

Графикалық теориялық толтыру

Кейбір теоретиктер проблеманы шешу үшін нақты графтар теориясын қолданды, пиксельдер аралықтарын немесе олардың жиынтығын түйіндер ретінде қарастырып, олардың байланысын зерттеді. Алғаш рет жарияланған графтар теориясының алгоритмі жоғарыдағы аралықты толтыру сияқты жұмыс істеді, бірақ аралықтарды қайталап толтыруды анықтау мүмкіндігі болды. Алайда, ол кейбір толтыруларды аяқтамайтын қателерге ие болды. Кейін түзетілген алгоритм графтар теориясының ұқсас негізінде жарияланды; алайда, ол бағдарламалық интерфейсті қиындата отырып, ықтимал циклдарды уақытша тоқтату үшін суретті өзгертеді. Басқа бір алгоритм, кейін жарияланған, шекараның кескіндегі барлық басқа элементтерден ерекше болуына тәуелді болды, сондықтан көптеген жағдайларда қолдануға қолайлы емес; сонымен қатар, оған есеп жүргізу үшін пикселге қосымша бит қажет.

Артықшылықтар

Үлгілерді толтыруға қолайлы, себебі толтырылған пикселдерді қайта тексермейді. Қарапайым толтырулар үшін бастапқы аралық алгоритмінен екі есе жылдам. Паттернге қолжетімділік кэш және биттік жазылымға ыңғайлы.

Кемшіліктер

Тұрақты түрде, аралық кезектегі әрбір "алдыңғы" бөлікпен салыстырылуы керек, бұл күрделі тапсырыстарды едәуір баяулатады. Граф теориясы мен пиксельдік кеңістік арасындағы жиі ауысу түсінуді қиындатады. Код жеткілікті күрделі, бұл қателердің пайда болу ықтималдығын арттырады.

Жүгіру арқылы толтыру (Тұрақты жады әдісі)

Бұл әдіс төрт аймақты байланыстыру үшін жадыны іс жүзінде пайдаланбайды. Ол суретші рөліндегі алгоритмді көзге елестетіп, өзін бұрышқа тіремей аймақты бояуға тырысады. Бұл лабиринттерді шешудің де бір жолы. Негізгі шекараны құрайтын төрт пикселге қарап, қандай әрекет жасау керектігі анықталады. Суретші бірнеше жағдайдың бірінде болуы мүмкін:

Барлық төрт шекаралық пиксел толтырылған. Шекаралық пиксельдердің үшеуі толтырылған. Шекаралық пиксельдердің екеуі толтырылған. Бір шекаралық пиксел толтырылған. Шекаралық пикселдердің бірі де толтырылмаған. Жол немесе шекараны бағыттап өту қажет болғанда, оң қол ережесі қолданылады. Суретші оң қолын қабырғаға (аймақтың шекарасына) қойып, қолын шешірмей аймақтың шетімен жүреді. 1-ші жағдайда суретші өзі тұрған пикселді бояп (толтырып), алгоритмді тоқтатады. 2-ші жағдайда аумақтан шығатын жол бар. Суретші өзі тұрған пикселді бояп, ашық жолға қарай жылжиды. 3-ші жағдайда екі шекаралық пиксел жолды анықтайды. Егер ағымдағы пикселді боясақ, ол жолдың екінші жағына өтуге кедерілдіруі мүмкін. Біз қайда екенімізді және қай бағытта қозғалып жатқанымызды білу үшін «белгі» қою қажет, сонда ғана дәл сол пикселге қайта оралу мүмкіндігін анықтай аламыз. Егер мұндай «белгі» қойылса, бұрынғы белгі сақталады және оң қол ережесі бойынша келесі пикселге өтіледі. Алғашқы 2 пикселдік шекарада жолдың қайдан басталғанын және суретшінің қозғалыс бағытын есте сақтау үшін белгі қолданылады. Егер белгі қайтадан кездесіп, суретші сол бағытта қозғалса, онда белгі қойылған пикселді бояу және сол бағытта жалғастыру қауіпсіз екенін біледі. Себебі белгінің екінші жағындағы пиксельдерге (біреуі белгісіз жолмен) қол жеткізіп, болашақта бояуға болады. Белгі кейін пайдалану үшін алынып тасталады. Егер суретші белгіге тап болса, бірақ басқа бағытта қозғалса, цикл пайда болған деген сөз. Бұл циклді жою қажет. Белгі алынып, суретші бұрын белгі көрсеткен бағытта сол қол ережесін қолдана отырып (оң қол ережесіне ұқсас, бірақ суретшінің сол қолымен) қозғалады. Бұл үш немесе одан көп ашық шекаралық пиксельдері бар қиылысқан жерге дейін жалғасады. Осы екі пикселдік шекараны тапқаннан кейін, пиксел боялады. Бұл циклді бұзады және алгоритмді жалғастыруға мүмкіндік береді. 4-ші жағдайда 8 көршілес бұрыштың толтырылғандығы тексерілуі керек. Егер біреуі немесе екеуі де толтырылса, онда көптеген жолдардың қиылысы пайда болады және оны толтыру мүмкін емес. Егер екеуі де бос болса, ағымдағы пикселді бояп, оң қол ережесі бойынша қозғалуға болады. Алгоритм жадты уақытқа айырбастайды. Қарапайым пішіндер үшін өте тиімді. Бірақ пішін күрделі және көптеген ерекшеліктері болса, алгоритм барлық пикселдерді бояуға болатынына көз жеткізу үшін аймақтың шеттерін іздеуге көп уақыт жұмсайды. Бұл алгоритм алғаш рет 1981 жылы Vicom Systems, Inc. компаниясы шығарған Vicom Image Processing жүйесінде коммерциялық түрде қолжетімді болды. 1994 жылы жүріп-тұру алгоритмі жарияланды. Классикалық рекурсивті топан су алгоритмі де Vicom жүйесінде қолжетімді болды.

All four boundary pixels are filled. Three of the boundary pixels are filled. Two of the boundary pixels are filled. One boundary pixel is filled. Zero boundary pixels are filled. Where a path or boundary is to be followed, the right hand rule is used. The painter follows the region by placing their right hand on the wall (the boundary of the region) and progressing around the edge of the region without removing their hand. For case #1, the painter paints (fills) the pixel the painter is standing upon and stops the algorithm. For case #2, a path leading out of the area exists. Paint the pixel the painter is standing upon and move in the direction of the open path. For case #3, the two boundary pixels define a path which, if we painted the current pixel, may block us from ever getting back to the other side of the path. We need a "mark" to define where we are and which direction we are heading to see if we ever get back to exactly the same pixel. If we already created such a "mark", then we preserve our previous mark and move to the next pixel following the right hand rule. A mark is used for the first 2 pixel boundary that is encountered to remember where the passage started and in what direction the painter was moving. If the mark is encountered again and the painter is traveling in the same direction, then the painter knows that it is safe to paint the square with the mark and to continue in the same direction. This is because (through some unknown path) the pixels on the other side of the mark can be reached and painted in the future. The mark is removed for future use. If the painter encounters the mark but is going in a different direction, then some sort of loop has occurred, which caused the painter to return to the mark. This loop must be eliminated. The mark is picked up, and the painter then proceeds in the direction indicated previously by the mark using a left hand rule for the boundary (similar to the right hand rule but using the painter's left hand). This continues until an intersection is found (with three or more open boundary pixels). Still using the left hand rule the painter now searches for a simple passage (made by two boundary pixels). Upon finding this two pixel boundary path, that pixel is painted. This breaks the loop and allows the algorithm to continue. For case #4, we need to check the opposite 8 connected corners to see whether they are filled or not. If either or both are filled, then this creates a many path intersection and cannot be filled. If both are empty, then the current pixel can be painted and the painter can move following the right hand rule. The algorithm trades time for memory. For simple shapes it is very efficient. However, if the shape is complex with many features, the algorithm spends a large amount of time tracing the edges of the region trying to ensure that all can be painted. This algorithm was first available commercially in 1981 on a Vicom Image Processing system manufactured by Vicom Systems, Inc. A walking algorithm was published in 1994. The classic recursive flood fill algorithm was available on the Vicom system as well.

Артықшылықтар

Тұрақты жадты пайдалану.

Кемшіліктер

Кіру үлгісі кэш немесе биттік жазылымға қолайлы емес. Циклдарды жабу алдында көп уақытты оларды аралап шығуға жұмсау мүмкін.

Векторлық іске асырулар

Inkscape-тің 0.46 нұсқасында, кәдімгі растрлік операцияларға ұқсас нәтиже беретін және осылай жұмыс істейтін, бояу құймасы (bucket fill) құралы енгізілді: кенеп суреттеледі, таңдалған аймаққа су тасқынымен толтыру операциясы қолданылады, содан кейін нәтиже векторлық контурға түрлендіріледі. Бұл шекаралық шарттар қағидасын пайдаланады.