Algoritmo de diamante-cuadrado

El algoritmo diamante-cuadrado es un método para generar mapas de altura para gráficos por computadora . Es un algoritmo ligeramente superior a 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 presentada por primera vez por Fournier , Fussell y Carpenter en SIGGRAPH en 1982. ^{[ 1 ]}

El algoritmo 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 manera que todo el plano quede cubierto de cuadrados.

El algoritmo diamante-cuadrado comienza con una matriz cuadrada bidimensional de ancho y alto 2 ⁿ + 1. Primero, se deben establecer los valores iniciales de los cuatro vértices de la matriz. Luego, se realizan alternativamente los pasos de diamante y cuadrado hasta que se hayan establecido todos los valores de la matriz.

• El paso del diamante: Para cada cuadrado de la matriz, establezca el punto medio de ese cuadrado como el promedio de los cuatro puntos de las esquinas más un valor aleatorio.
• El paso cuadrado: Para cada diamante en la matriz, establezca el punto medio de ese diamante como el promedio de los cuatro puntos de las esquinas más un valor aleatorio.

Cada valor aleatorio se multiplica por un multiplicador de escala, que disminuye en 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, en lugar de cuatro. Existen varias maneras de abordar esta complicación; la más sencilla consiste en calcular el promedio de los tres valores adyacentes. Otra opción es realizar un "envolvimiento", tomando el cuarto valor del otro lado de la matriz. Cuando se utiliza con valores iniciales de esquina consistentes, este método también permite unir fractales generados sin discontinuidades.

La imagen que aparece a continuación 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 emplean diferentes implementaciones en software de gráficos por computadora como Terragen . También es aplicable como un componente común en texturas procedimentales .

El algoritmo diamante-cuadrado fue analizado por Gavin SP Miller en SIGGRAPH 1986 ^{[ 3 ]} , quien lo describió como defectuoso debido a que produce "pliegues" verticales y horizontales notables, ya que la perturbación más significativa ocurre 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 basado en la teoría de la 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 oceánicas. 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 diamante-cuadrado y sus refinamientos se revisan en el libro de Peitgen y Saupe , "The Science of Fractal Images" ^{[ 5 ] .}

• Módulo sencillo de código abierto para mapas de altura en Lua que utiliza el algoritmo diamante-cuadrado.
• Generación de terreno fractal aleatorio: El algoritmo diamante-cuadrado de GameProgrammer.com
• Fractal de plasma de la página web de Justin Seyster
• Fractales de plasma de la página principal de Patrick Hahn
• Tutorial de terrenos de Lighthouse3d.com
• Desplazamiento aleatorio del punto medio con lienzo
• método de desplazamiento aleatorio del punto medio
• Algoritmo Diamante y Cuadrado en Github (PHP)
• Un ejemplo de cómo probar una implementación del algoritmo se encuentra en el blog Clean Coder del tío Bob.
• Implementación clásica de desplazamiento lateral de Xmountains para X11. Detalles del algoritmo .
• Una implementación en Python , breve y sencilla. Admite condiciones de contorno tanto fijas como periódicas.