El algoritmo de diamante cuadrado es un método para generar mapas de altura para gráficos de computadora . Es un algoritmo ligeramente mejor que la implementación tridimensional del algoritmo de desplazamiento de punto medio, que produce paisajes bidimensionales. También se lo conoce como fractal de desplazamiento aleatorio de punto medio , fractal de nubes o fractal de plasma , debido al efecto de plasma que se produce cuando se aplica.
La idea fue introducida por primera vez por Fournier , Fussell y Carpenter en SIGGRAPH en 1982. [1]
El algoritmo de diamante-cuadrado comienza con una cuadrícula bidimensional y luego genera aleatoriamente la altura del terreno a partir de cuatro valores semilla dispuestos en una cuadrícula de puntos de modo que todo el plano esté cubierto de cuadrados.
El algoritmo de diamante-cuadrado comienza con una matriz cuadrada bidimensional de ancho y alto 2n + 1. Primero se deben establecer los valores iniciales en los cuatro puntos de las esquinas de la matriz. Luego se realizan los pasos de diamante y cuadrado de manera alternada hasta que se hayan establecido todos los valores de la matriz.
Cada valor aleatorio se multiplica por una constante de escala, que disminuye con cada iteración por un factor de 2 −h , donde h es un valor entre 0,0 y 1,0 (los valores más bajos producen un terreno más accidentado). [2]
Durante los pasos cuadrados, los puntos ubicados en los bordes de la matriz tendrán solo tres valores adyacentes establecidos, en lugar de cuatro. Hay varias formas de manejar esta complicación; la más simple es tomar el promedio de solo los tres valores adyacentes. Otra opción es "envolver", tomando el cuarto valor del otro lado de la matriz. Cuando se usa con valores de esquina iniciales consistentes, este método también permite unir los fractales generados sin discontinuidades.
La siguiente imagen muestra los pasos necesarios para ejecutar el algoritmo diamante-cuadrado en una matriz de 5 × 5.
Este algoritmo se puede utilizar para generar paisajes de aspecto realista y se utilizan diferentes implementaciones en software de gráficos por ordenador como Terragen . También se puede aplicar como componente común en texturas procedimentales .
El algoritmo del diamante cuadrado fue analizado por Gavin SP Miller en SIGGRAPH 1986 [3], quien lo describió como defectuoso porque el algoritmo produce "pliegues" verticales y horizontales notables debido a que la perturbación más significativa tiene lugar en una cuadrícula rectangular. Los artefactos de la cuadrícula se abordaron en un algoritmo generalizado introducido por JP Lewis [4] . En esta variante, los pesos de los puntos vecinos se obtienen resolviendo un pequeño sistema lineal motivado por la teoría de estimación, en lugar de ser fijos. El algoritmo de Lewis también permite la síntesis de mapas de altura no fractales, como colinas onduladas u olas del océano. Se pueden obtener resultados similares de manera eficiente con la síntesis de Fourier [5] , aunque se pierde la posibilidad de refinamiento adaptativo. El algoritmo del diamante cuadrado y sus refinamientos se analizan en el libro de Peitgen y Saupe "La ciencia de las imágenes fractales". [5]
{{cite book}}: CS1 maint: multiple names: authors list (link)