División de árbol KD

Actualmente estoy escribiendo un KDTree para un motor de física (proyecto Hobby).

El KDTree no contiene puntos. En su lugar, contiene cuadros delimitadores alineados por eje que unen los diferentes objetos del entorno.

Mi problema es decidir cómo dividir los nodos KDTree cuando se llenan. Estoy probando 2 métodos:

Método 1: siempre divida el nodo exactamente por la mitad en el eje más grande.

Esto tiene la ventaja de un árbol bastante uniformemente espaciado.Gran desventaja: si los objetos se concentran en un área pequeña del nodo, se crearán subdivisiones redundantes. Esto se debe a que todos los volúmenes se dividen exactamente a la mitad.

Método2: Encuentre el área del nodo que contiene objetos. Divida el nodo en el plano que divide esa área por la mitad en su eje más grande. Ejemplo: si todos los objetos se concentran en la parte inferior del nodo, entonces se divide longitudinalmente dividiendo así la parte inferior en dos.

Esto resuelve el problema con el método anteriorAl indexar algo que existe en el mismo plano (terreno, por ejemplo), crea nodos largos y estrechos. Si debo agregar otros objetos más tarde que no están en el mismo plano, estos nodos alargados proporcionan una indexación muy pobre.

Entonces, lo que estoy buscando aquí es una mejor manera de dividir mi nodo KD-Tree. Teniendo en cuenta que este será un motor de física, la decisión debe ser lo suficientemente simple como para tomarla en tiempo real.

Respuestas a la pregunta(2)

Su respuesta a la pregunta