La partición del espacio binario es un método de partición recursiva del espacio euclidiano en conjuntos convexos e hiperplanos . Como resultado, los objetos se representan como una estructura de datos denominada árbol BSP .
El árbol BSP se utiliza para realizar eficientemente las siguientes operaciones en gráficos 3D por computadora :
Los árboles BSP fueron utilizados por primera vez por LucasArts a principios de los años 80. Ganaron popularidad entre los desarrolladores gracias a id Software , que desarrolló los motores Doom ( 1993 ) y Quake ( 1996 ).
En un árbol BSP, cada nodo está asociado con una línea o plano de división en el espacio 2D o 3D, respectivamente. En este caso, todos los objetos que se encuentran en la parte frontal del plano pertenecen al subárbol frontal, y todos los objetos que se encuentran en la parte posterior del plano pertenecen al subárbol posterior. Para determinar si un objeto pertenece al anverso o al reverso de una línea o plano de división, es necesario examinar la posición de cada uno de sus puntos. La posición de un punto con respecto al plano está determinada por el producto escalar de la normal del plano y las coordenadas del punto en coordenadas homogéneas . Tres casos son posibles:
Si para todos los puntos del objeto el producto escalar es mayor que 0, entonces pertenece al subárbol frontal. Si para todos los puntos del objeto el producto escalar es menor que 0, entonces pertenece al subárbol inverso. Si para todos los puntos de un objeto el producto escalar es igual a 0, entonces no importa a qué subárbol pertenezca. Si los productos escalares de los puntos de un objeto tienen un signo diferente, el plano de división lo corta, de modo que los objetos resultantes se encuentran solo en el frente o solo en el reverso. Para cada subnodo del árbol BSP , la declaración anterior es verdadera, con la excepción de que solo aquellos objetos que pertenecen al lado frontal o posterior del plano de división del nodo principal están sujetos a consideración.
La definición anterior solo describe las propiedades de un árbol BSP , no dice cómo construirlo. Como regla general, un árbol BSP se construye para un conjunto de segmentos en un plano o polígonos en el espacio, que representan una determinada figura o escena. Considere el algoritmo para construir un árbol BSP para un conjunto de polígonos en el espacio:
El plano de división se elige de tal manera que equilibre el árbol, es decir, de modo que el número de polígonos en los subárboles delantero y trasero sea aproximadamente el mismo:
min(|N(Fi) - N(Bi)|)
donde N(Fi) es el número de polígonos en el lado frontal de algún plano de división i, N(Bi) es el número de polígonos en el lado posterior del plano de división i.
Al clasificar objetos en orden de eliminación del observador, utilizando el árbol BSP, se examinan las posiciones relativas del vector y el punto de observación ( POV ) y las normales de los planos de ruptura. Si la normal del plano de división y el vector de observación están codirigidos , entonces el subárbol frontal está más alejado del observador que el inverso; de lo contrario, el subárbol inverso está más alejado del observador que el frontal. En este caso, si el plano de división está detrás del observador, es posible que el propio plano, así como el subárbol frontal o posterior, no sean completamente visibles. El algoritmo recursivo para ordenar polígonos usando un árbol BSP es el siguiente:
Procedimiento BypassNode(Nodo) Si el nodo <> NULLPointer Si los vectores están codirigidos (vector de observación, nodo.Normal de SplitPlane) Si DotProduct(ObservationPoint, Node.Normal of SplitPlane) >= 0 // El plano está detrás del observador, el observador solo ve el subárbol frontal TraverseNode(Node.FrontSubtree); De lo contrario // El avión está frente al observador, // el subárbol delantero está más lejos que el subárbol trasero TraverseNode(Node.FrontSubtree); AddPolygonToDisplayList(Node.Polygon); TraverseNode(Nodo.ReverseSubtree); Terminara si; De lo contrario Si DotProduct(ObservationPoint, Node.Normal of SplitPlane) >= 0 // El avión está frente al observador, // el subárbol trasero está más lejos que el subárbol delantero TraverseNode(Nodo.ReverseSubtree); AddPolygonToDisplayList(Node.Polygon); TraverseNode(Node.FrontSubtree); De lo contrario // El avión está detrás del observador, el observador solo ve el subárbol inverso TraverseNode(Nodo.ReverseSubtree); Terminara si; Terminara si; Terminara si; Final;Este algoritmo se puede optimizar si tenemos en cuenta que para un determinado conjunto de polígonos el árbol tiene una estructura degenerada, en el caso de que para cada polígono de este conjunto todos los polígonos restantes se encuentren solo en el frente o solo en el reverso. Esto es exactamente lo que hizo John Carmack en el motor de DOOM . .
El algoritmo para acelerar de recursivo se puede convertir a iterativo.
El recorte de superficies invisibles se implementa introduciendo información adicional en el árbol BSP , como marcos (cuadros delimitadores, esferas delimitadoras). Los marcos son rectángulos o paralelepípedos, círculos o esferas que limitan el área donde se ubican los polígonos de un determinado subárbol. Por lo tanto, cada nodo tiene dos marcos. Se garantiza que el subárbol es invisible a menos que la pirámide visual se cruce con el objeto delimitador. Lo opuesto no es verdad. Sin embargo, una declaración directa es suficiente para cortar el procesamiento de un número significativo de objetos.
La elección de objetos geométricos que representan marcos proviene de la simplicidad del algoritmo para verificar la intersección de la pirámide visual con el marco.
Al buscar colisiones, el árbol BSP se usa para encontrar el plano más cercano al objeto. La mayoría de las veces, los límites de un objeto vienen dados por una esfera (o círculo) delimitante para simplificar los cálculos. El árbol BSP se recorre desde la raíz hasta el plano más cercano al objeto. En este caso, si no se detectan intersecciones de la esfera delimitadora con ningún plano, entonces no hay colisión; de lo contrario, la hay.
Ejemplo:
Procedimiento del buscador de colisiones (nodo, objeto) Si el nodo <> NULLPointer Si Distancia(Nudo.Plano, Objeto.BoundingSphereCenter) > Objeto.BoundingSphereRadius Si DotProduct(Object.BoundingSphereCenter, SplitPlaneNode.Normal) >= 0 // El objeto está en el lado frontal del plano de rotura, // atravesar solo el subárbol frontal FindCollision(Node.FrontSubtree, Object); De lo contrario // El objeto está en la parte posterior del plano de división, // atravesar solo el subárbol inverso FindCollision(Node.ReverseSubtree, Object); Terminara si; De lo contrario El retorno es colisión; Terminara si; De lo contrario retorno sin colisión; Terminara si; Final;El algoritmo para acelerar de recursivo se puede convertir a iterativo.
| Árbol (estructura de datos) | |
|---|---|
| Árboles binarios | |
| Árboles binarios autoequilibrados |
|
| árboles B |
|
| árboles de prefijo |
|
| Partición binaria del espacio | |
| Árboles no binarios |
|
| Rompiendo el espacio |
|
| Otros árboles |
|
| Algoritmos | |