Partición binaria del espacio

En diseño por ordenador es deseable que el dibujo de una escena sea correcta y rápida.La técnica del Z-Buffer puede asegurar que las escenas se dibujarán correctamente y que se eliminará la necesidad de seguir un orden como en el algoritmo del pintor, pero es poco eficiente en términos de memoria.Esto se suele solucionar empleando conjuntamente un Z-Buffer, usándolo para unir correctamente los objetos móviles como puertas y enemigos con el resto de la escena.Por ejemplo, en un árbol BSP empleado para la detección de colisiones el objeto original sería dividido hasta que cada parte sea lo suficientemente sencilla como para ser individualmente comprobada, y en el renderizaje interesa que cada parte sea convexa, de forma que el algoritmo del pintor pueda ser usado.Si la línea de partición se intersecciona con un segmento, o una cara en un modelo tridimensional, el/los segmento/s o cara/s tienen que ser divididas en dos dado que cada partición debe ser un objeto completo e independiente.La mayoría de los algoritmos prueban muchas posibilidades para cada partición hasta que se encuentra un resultado lo suficientemente bueno, y también mantienen la información necesaria en memoria para poder retroceder en caso de que una rama del árbol no sea satisfactoria y probar otras opciones.Inicialmente, esta idea se propuso para los gráficos 3D por ordenador para incrementar la eficiencia de renderizado.Otros usos son el procesamiento geométrico con formas, Constructive Solid Geometry en herramientas CAD, detección de colisiones en robótica y videojuegos 3D, y otras aplicaciones informáticas que incluyen el manejo de estructuras espaciales complejas.