Diamond-Square-algoritmen är en metod för att generera höjdkartor för datorgrafik .
Idén introducerades först av Fournier , Fussel och Carpenter vid siggraph- konferensen 1982 [1] . Det analyserades senare av Gavin Miller på siggraph-1986-konferensen [2] , Miller beskrev ett antal brister i algoritmen, såsom "veck" som uppstår vid kartans kanter.
Algoritmen börjar med ett 2D- rutnät och genererar sedan, från fyra initiala värden, slumpmässigt en höjdkarta ordnad som ett rutnät av punkter så att hela planet täcks av rutor.
Diamant-kvadratalgoritmen börjar med en tvådimensionell array med storleken 2 n + 1. Inledande höjder sätts vid de fyra hörnpunkterna i arrayen. Diamant- och kvadratstegen exekveras växelvis tills alla arrayvärden har ställts in.
steg diamant. För varje kvadrat i arrayen sätts en mittpunkt, som ges det aritmetiska medelvärdet av de fyra hörnpunkterna plus ett slumpmässigt värde.
steg kvadrat. Mittpunkterna på ytorna på samma rutor tas, där medelvärdet sätts från fyra punkter intill dem längs axlarna, plus ett slumpmässigt värde.
Ett slumptal väljs vanligtvis i intervallet [-Ri , R i ], där R är grovhetsfaktorn mellan 0 och 1, och i är iterationstalet (rutsteg och kvadratsteg är en iteration). Följaktligen, med varje iteration, minskar det slumpmässiga värdet som läggs till mittpunkterna.
I diamantsteg kommer punkter som ligger vid kanterna av den gemensamma arrayen bara att ha tre närliggande värden, inte fyra (den fjärde punkten kommer att vara utanför arraydimensionen). Det finns flera sätt att hantera detta – det enklaste är att ta medelvärdet av de tre extrempunkterna. När den används konsekvent med vanliga initiala värden, tillåter denna metod att "sy" de genererade höjdkartorna.
Bilden nedan visar stegen som tas av diamantkvadratalgoritmen med en 5x5-array som exempel.
Steg 1. Initiering av hörnpunkter. Tilldela höjdvärden till dem (till exempel genom att välja slumpmässiga siffror).
STEG 2. Steg diamant. Hitta mittpunkten, tilldela ett värde till den, baserat på medelvärdet av hörnen, plus ett slumpmässigt tal.
Steg 3. Steg kvadrat. Hitta mittpunkter för romber markerade med svarta prickar (i det här steget går en punkt på varje romb bortom matrisen). Plus ett slumptal.
STEG 4. Steg diamant. För varje ruta (det finns 4 i detta steg), upprepa steg #2.
Steg 5. Steg kvadrat. Upprepa steg #3 för varje diamant. För romber som har punkter på kanten av arrayen, går en av punkterna utanför arrayen.
Denna algoritm kan användas för att skapa realistiska landskap . Olika implementeringar används i datorgrafikprogram som terragen .