Simulación Barnes-Hut

En una simulación de N-cuerpos tridimensional, el algoritmo Barnes-Hut divide recursivamente los N cuerpos en grupos, almacenándolos en un octree (o en un quadtree en una simulación 2D). Cada nodo en este árbol representa una región del espacio tridimensional. El nodo superior representa todo el espacio, y sus ocho hijos representan los ocho octantes del espacio, cada uno de los cuales se pueden dividir nuevamente en ocho octantes. El espacio se subdivide en octantes de forma recursiva hasta que cada subdivisión contiene 0 o 1 cuerpos (algunas regiones no tienen cuerpos en todos sus cuadrantes). Hay dos tipos de nodos en un octree: nodos internos y externos. Un nodo externo no tiene hijos, y está vacío o representa un solo cuerpo. Cada nodo interno representa un grupo de cuerpos contenidos en su interior, y almacena el centro de la masa y la masa total de todos los cuerpos hijos.

• 
  Distribución de partículas que se asemeja a la de dos galaxias vecinas
• 
  Árbol Barnes-Hut completo. (Los nodos que no contienen partículas no están dibujados)
• 
  Los nodos del árbol Barnes-Hut utilizados para calcular la fuerza que actúa sobre una partícula situada en el origen.
• Simulación de N-cuerpos basada en el algoritmo Barnes-Hut.

Para calcular la fuerza neta sobre un cuerpo en particular, los nodos del árbol son recorridos desde la raíz. Si el centro de masas de un nodo interno está lo suficientemente lejos del cuerpo, los cuerpos contenidos en esa parte del árbol se tratan como un solo cuerpo, cuya posición y masa son, respectivamente, el centro de masa y la masa total del nodo interno. Si el nodo interno no está lo suficientemente lejos del cuerpo, el proceso se repite para cada una de sus ramificaciones.

Si un nodo está o no lo suficientemente lejos de un cuerpo, depende del cociente s / d, donde s es el ancho de la región representada por el nodo interno, y d es la distancia entre el cuerpo y el centro de masas del nodo. El nodo está suficientemente lejos cuando esta relación es menor que un valor umbral θ. El parámetro θ determina la exactitud de la simulación, valores más grandes de θ aumentan la velocidad de la simulación, pero disminuyen su exactitud. Si θ = 0, ningún nodo interno es tratado como un solo cuerpo y el algoritmo degenera a un algoritmo de suma directa.