El algoritmo de 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 conoce como fractal de desplazamiento de punto medio aleatorio , fractal de nube o fractal de plasma , debido al efecto de plasma que se produce cuando se aplica.
La idea fue presentada por primera vez por Fournier , Fussell y Carpenter en SIGGRAPH 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 de semilla dispuestos en una cuadrícula de puntos para que todo el plano esté cubierto de cuadrados.
Descripción
El algoritmo de rombo cuadrado comienza con una matriz cuadrada bidimensional de ancho y alto 2 n + 1. Los cuatro puntos de esquina de la matriz deben establecerse primero en los valores iniciales. Los pasos de diamante y cuadrado se realizan alternativamente hasta que se hayan establecido todos los valores de la matriz.
- El paso de 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 de la matriz, establezca el punto medio de ese diamante como el promedio de los cuatro puntos de las esquinas más un valor aleatorio.
En cada iteración, se debe reducir la magnitud del valor aleatorio.
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.
Visualización
La siguiente imagen muestra los pasos necesarios para ejecutar el algoritmo de diamante cuadrado en una matriz de 5 × 5.
Aplicaciones
Este algoritmo se puede usar para generar paisajes de apariencia realista , y se usan diferentes implementaciones en software de gráficos por computadora como Terragen . También es aplicable como componente común en texturas procedimentales .
Artefactos y extensiones
El algoritmo de diamante cuadrado fue analizado por Gavin SP Miller en SIGGRAPH 1986 [2], 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 en un algoritmo generalizado introducido por JP Lewis. [3] 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, [4] aunque se pierde la posibilidad de un refinamiento adaptativo. El algoritmo del cuadrado del diamante y sus refinamientos se revisan en el libro. [4]
Referencias
- ^ Fournier, Alain; Fussell, Don; Carpenter, Loren (junio de 1982). "Representación informática de modelos estocásticos". Comunicaciones de la ACM . 25 (6): 371–384. doi : 10.1145 / 358523.358553 .
- ^ Miller, Gavin SP (agosto de 1986). "La definición y renderización de mapas del terreno". Gráficos por computadora ACM SIGGRAPH . 20 (4): 39–48. doi : 10.1145 / 15886.15890 .
- ^ Lewis, JP (1 de julio de 1987). "Subdivisión estocástica generalizada". Transacciones ACM en gráficos . 6 (3): 167-190. CiteSeerX 10.1.1.21.3719 . doi : 10.1145 / 35068.35069 .
- ^ a b Peitgen, Heinz-Otto, Dietmar Saupe (1988). La ciencia de las imágenes fractales . Nueva York: Springer-Verlag. ISBN 978-0-387-96608-3.
enlaces externos
- Módulo de mapa de altura de código abierto simple para Lua usando algoritmo de diamante cuadrado
- Generación de terreno fractal aleatorio: el algoritmo de diamante-cuadrado de GameProgrammer.com
- Plasma Fractal de la página web de Justin Seyster
- Fractales de plasma de la página de inicio de Patrick Hahn
- Tutorial de terreno de Lighthouse3d.com
- Desplazamiento aleatorio del punto medio con lienzo
- Método de desplazamiento de punto medio aleatorio
- Algoritmo Diamond And Square en Github (PHP)
- Un ejemplo de prueba de manejo de una implementación del algoritmo de tío Bob 's Blog Clean Coder
- Implementación X11 de desplazamiento lateral clásico de Xmountains . Detalles del algoritmo .