Кіріспе

2D скалярлы өрісте контур сызықтарын жасау алгоритмі

Компьютерлік графикада, "шерулі квадраттар" алгоритмі екі өлшемді скалярлы өрістің (жеке сандық мәндердің тікбұрышты массиві) контурларын құрады. Осыған ұқсас әдіс 2D үшбұрышты торларды контурлау үшін де қолданылуы мүмкін. Контурлар екі түрлі болуы мүмкін:
Изолиниялар – бір дерек деңгейін (изозначение) бағдарлайтын сызықтар. Изобандалар – изолиниялар арасындағы толтырылған аймақтар. Типтік қолданысқа топографиялық карталардағы контур сызықтары немесе ауа райы карталары үшін изобарларды жасау жатады. "Шерулі квадраттар" алгоритмі 3D "шерулі текшелер" алгоритміне ұқсас тәсілді қолданады:
Тордағы әрбір ұяшықты тәуелсіз өңдеу. Ұяшық бұрыштарындағы дерек мәндерімен контур деңгейін салыстыру арқылы ұяшық индексін есептеу. Ұяшықтың шығыс геометриясын сипаттау үшін ұяшық индексі бойынша кілттелген алдын ала құрастырылған іздеу кестесін пайдалану. Контурдың нақты орнын есептеу үшін ұяшықтың шекаралары бойынша сызықтық интерполяция қолдану.

Седелдің нүктелерінің түсініктілігін арттыру

Контурдың тұтқа нүктелерінде бұлыңғырлық пайда болады. Интерполяцияланған нүктелердің әртүрлі байланыстарын таңдау үшін ұяшықтың ортасындағы орташа дерек мәнін қолдану арқылы бұл бұлыңғырлықты жоюға болады (оң төменгі бұрыштағы төрт сурет):

Үшбұрышты контурлау желіні

Сол негізгі алгоритм үшбұрышты торларға да қолданылуы мүмкін, олар өзара байланысқан үшбұрыштардан тұрады және әр төбесіне деректер тағайындалған. Мысалы, шашыраңқы деректер жиыны Делоне үшбұрыштау арқылы байланыстырылып, деректер өрісінің контурларын жасауға мүмкіндік береді. Үшбұрышты жасуша әрқашан жазық болады, себебі ол 2-симплекс (яғни n өлшемді кеңістікте n+1 төбемен анықталған). Үшбұрыш ішінде әрқашан бірегей сызықтық интерполяция болады және екіұшты нүктелердің пайда болуына орын жоқ.

Өлшемі мен кеңістігі

Marching Squares алгоритмі үшін деректер кеңістігі 2D болып табылады, себебі дерек мәні тағайындалған төбелер олардың көршілерімен 2D топологиялық торда байланысқан, бірақ төбелерге тағайындалған кеңістіктік координаттар 2D, 3D немесе одан жоғары өлшемде болуы мүмкін. Мысалы, үшбұрышты тор 3D кеңістікте орналасқан 2D деректер бетін көрсетуі мүмкін, онда төбелердің және контур бойындағы интерполяцияланған нүктелердің кеңістіктік орналасуының барлығы 3 координатаға ие болады. Квадраттар жағдайы да қайтадан екіұшты екенін ескеріңіз, өйткені 3 өлшемді кеңістікте орналасқан төртбұрыш міндетті түрде жазық болмайды, сондықтан 3D-де жолақты беттерді салу үшін геометриялық интерполяция схемасын таңдау қажет.

Орындаушылық мән-жайлар

Алгоритм өте оңай параллелдеуге болады, себебі барлық жасушалар тәуелсіз өңделеді. Параллель алгоритмді жазу келесі шарттар орындалғанда оңай: ортақ, тек оқуға арналған кіріс скалярлық өріс; ортақ, тек геометрияны қосуға арналған шығыс ағыны. Marching Squares алгоритмінің әрбір жасушаны тәуелсіз өңдейтін қарапайым іске асырылуы әрбір сызықтық интерполяцияны екі рет (изолин үшін) немесе төрт рет (изобанд үшін) орындайды. Сол сияқты, шығыста үзіліс жоқ сызықтар үшін 2D координаталардың 2 көшірмесі (изолин үшін) немесе көпбұрыштар үшін 4 көшірмесі (изобандтар үшін) болады. [Егер тор үлкен болса, сондықтан көптеген жасушалар ішкі болады; және толық, үздіріссіз изобандтар жиынтығы құрылатын болса.] Интерполяция нәтижелерін кэштеу арқылы есептеу жүктемесін азайтуға болады. Мысалы, бір жіпті, тізбектік нұсқаға кіріс торының бір қатары үшін ғана интерполяцияланған нәтижелерді кэштеу жеткілікті. Шығыстың көлемін де индекстелген геометриялық примитивтерді пайдалану арқылы азайтуға болады, яғни 2D координаталар массивін құрып, массивке қысқа бүтін санмен ығыстырылған сызықтар немесе көпбұрыштарды анықтауға болады.