Кіріспе

Компьютерлік графика үшін биіктік карталарын жасау әдісі

Алмаз-квадрат алгоритмі – компьютерлік графика үшін биіктік карталарын жасау әдісі. Бұл, екі өлшемді ландшафттарды құратын орта нүктені ығыстыру алгоритмінің үш өлшемді нұсқасынан сәл жақсырақ алгоритм. Ол сондай-ақ, кездейсоқ орта нүктені ығыстыру фракталы, бұлт фракталы немесе плазма фракталы деп те аталады, себебі қолданғанда плазма эффектісі пайда болады. Бұл идея алғаш рет 1982 жылы SIGGRAPH конференциясында Fournier, Fussell және Carpenter есімді ғалымдар тарапынан ұсынылған. Алмаз-квадрат алгоритмі екі өлшемді тордан басталады, содан кейін төрт бастапқы мәнді кездейсоқ түрде пайдаланып жердің биіктігін жасайды, бұл мәндер нүктелер торында орналасқан, нәтижесінде бүкіл жазықтық квадраттармен жабылады.

Сипаттама

Алмаз квадраты алгоритмі ені мен биіктігі 2n + 1 болатын екі өлшемді квадрат массивтен басталады. Массивтің төрт бұрыштық нүктелері бастапқы мәндерге орнатылуы керек. Алмаз және квадрат қадамдары барлық массивтік мәндер орнатылғанға дейін кезектесіп орындалады. Алмаз қадамы: Массивтегі әр квадрат үшін, сол квадраттың орта нүктесі төрт бұрыштық нүктелердің орташа мәніне және кездейсоқ мәнге тең болады. Квадрат қадамы: Массивтегі әр алмаз үшін, сол алмаздың орта нүктесі төрт бұрыштық нүктелердің орташа мәніне және кездейсоқ мәнге орнатылады. Әр кездейсоқ мән масштаб тұрақтысымен көбейтіледі, ол әр итерацияда 2−h еселімен азаяды, мұнда h – 0.0 мен 1.0 арасындағы мән (кішкентай мәндер дөңгелек жерді жасайды). Квадрат қадамдары кезінде, массивдің жиектеріндегі нүктелерде тек үш жақын мән болады, төрт емес. Бұл қиындықпен шегудің бірнеше жолы бар – ең оңайы үш жақын мәннің орташасын алу. Басқа нұсқа – массивдің екінші жағынан төртінші мәнді алып, «айналдыру». Бұл әдіс тұрақты бастапқы бұрыштық мәндермен қолданылғанда, жасалған фракталдарды үздіксіз тігіп қосуға мүмкіндік береді.

Көрнекілендіру

Төмендегі сурет 5 × 5 массивінде алмаз квадратты алгоритмін іске қосу қадамдарын көрсетеді.

Қолданбалар

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

Артефактілер мен кеңейтулер

Алмаз шаршы алгоритмін Gavin S. P. Miller 1986 жылғы SIGGRAPH конференциясында талдап, оны кемшіліктері бар деп сипаттаған, себебі алгоритм төртбұрышты торда ең маңызды өзгерістер болатындықтан көзге көрінетін тік және көлденең "бұрыштарды" тудырады. Желілік артефактілерді J. P. Lewis ұсынған жалпыланған алгоритммен шешті. Бұл нұсқада көршілес нүктелердің салмағы белгілі бір шама емес, бағалау теориясымен негізделген шағын сызықтық жүйені шешу арқылы анықталады. Льюис алгоритмі фракталды емес биіктік карталарын, мысалы, төбелерді немесе мұхит толқындарын жасауға да мүмкіндік береді. Фурье синтезімен де ұқсас нәтижелерге тиімді қол жеткізуге болады, бірақ бейімделу мүмкіндігі жоғалады. Алмаз шаршы алгоритмі және оның жетілдірілген түрлері Peitgen және Saupe-ның "Фракталдық бейнелер ғылымы" кітабында қарастырылған.