El algoritmo del diamante cuadrado es un método para generar mapas de altura para gráficos por computadora . Es un algoritmo ligeramente mejor que la implementación tridimensional del algoritmo de desplazamiento del punto medio, que produce paisajes bidimensionales. También se le conoce como fractal de desplazamiento aleatorio del punto medio , fractal de nube o fractal de plasma , debido al efecto de plasma que se produce al aplicarlo.
La idea fue introducida por primera vez por Fournier , Fussell y Carpenter en SIGGRAPH en 1982. [1]
El algoritmo del cuadrado de diamante comienza con una cuadrícula bidimensional, luego genera aleatoriamente la altura del terreno a partir de cuatro valores iniciales dispuestos en una cuadrícula de puntos para que todo el plano quede cubierto de cuadrados.
El algoritmo del diamante cuadrado comienza con una matriz cuadrada bidimensional de ancho y alto 2 n + 1. Los cuatro puntos de las esquinas de la matriz primero deben establecerse en valores iniciales. Luego, los pasos de diamante y cuadrado se realizan alternativamente 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 en 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 maneras de manejar esta complicación; la más sencilla es tomar el promedio de sólo los tres valores adyacentes. Otra opción es 'envolver', tomando el cuarto valor del otro lado de la matriz. Cuando se utiliza 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 de diamante cuadrado en una matriz de 5 × 5.
Este algoritmo se puede utilizar para generar paisajes de apariencia realista y se utilizan diferentes implementaciones en software de gráficos por computadora como Terragen . También es aplicable como componente común en texturas procesales .
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 la perturbación más significativa que tiene lugar en una cuadrícula rectangular. Los artefactos de la cuadrícula se abordaron mediante 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 la estimación, en lugar de ser fijo. El algoritmo de Lewis también permite la síntesis de mapas de altura no fractales, como colinas 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 mejoras se revisan en el libro de Peitgen y Saupe "La ciencia de las imágenes fractales". [5]
{{cite book}}: CS1 maint: multiple names: authors list (link)