Cuando se utiliza un octree para la detección de colisiones en un juego, ¿debería reconstruirse el árbol en cada cuadro o hay una manera mejor asumiendo que la mitad de los objetos se mueven en un marco?¿Se debería reconstruir un octárbol en cada cuadro?
Si la escena cambia con cada fotograma, debe volver a hacer el árbol.
Si tiene mucha geometría estática en sus escenas, considere construir octrees por separado. También podría expresar la misma idea teniendo nodos de hoja más complicados que diferencien entre geometría estática y no estática.
Conclusión: solo regenere lo que tenga que hacer.
Si tiene datos muy dinámicos moviendo cada fotograma y aún necesita acelerar la detección de colisiones, en realidad recomiendo usar una red 3D fija para ello. equivalente de 2 dimensiones:
También puede duplicar el control como una lista libre para permitir el traslado a tiempo constante, al igual que (utilizando el índice next ya sea como un índice para el siguiente elemento en la misma celda de la cuadrícula o el siguiente elemento libre para que aparezca fuera de la pila libre si se ha eliminado):
Otro ejemplo:
Ahora en 3 dimensiones, esto podría parecer que requeriría memoria explosiva. Sin embargo, el truco consiste en hacer que cada célula almacene un índice de 32 bits en una matriz y, básicamente, sirva como una lista de índices vinculados individualmente. Eso reduce el tamaño de cada celda a 32 bits. Ahora, si almacena una cuadrícula de 100x100x100 (1 millón de celdas), eso tomaría menos de 4 megabytes.
Cuando los elementos se mueven, puede eliminarlos de las celdas que ocupan, moverlos e insertarlos en las celdas nuevas. Todo lo que tiene que hacer para hacer esto es manipular algunos índices de 32 bits (sin asignación/desasignación de memoria para transferir elementos de un conjunto de celdas a otros). Esto es todo de tiempo constante y no requiere reequilibrar árboles o dividir octantes que se llenen demasiado o algo por el estilo.
También puede usar una jerarquía de grillas (esto puede sonar como un octárbol pero diferente). Lo que quiero decir con eso es que podrías tener una grilla gruesa para objetos de malla completa en tu escena. Entonces, cada objeto de malla puede almacenar una grilla gruesa, digamos, 10x10x10, para cada una de sus partes. Luego, cada parte almacena una cuadrícula fina o un octárbol para cada uno de sus polígonos. Esto permite mallas no orgánicas que son, por ejemplo, rígidas con partes que giran como un robot para evitar tener que actualizar la cuadrícula fina/octárbol de polígonos y simplemente actualizar su propia grilla gruesa de partes y la gruesa grilla de objetos del mundo cuando comienza a girar sus piernas y brazos, por ejemplo Solo los modelos orgánicos necesitan actualizar sus redes finas cuando se deforman con huesos, p.
El octree que mantendría para sus elementos completamente estáticos/partes que nunca necesitan ser actualizadas por cuadro y usaría un bonito octárbol, escaso con tal vez un poco de procesamiento posterior para el acceso a la memoria de caché. Tiene un poco más de tiempo disponible para acelerar las búsquedas y minimizar el uso de la memoria si puede suponer que el octárbol no necesita actualizarse una vez que se haya construido.
Si la escena cambia con cada fotograma, entonces debe actualizar el árbol. No siempre es necesario "rehacer" todo el árbol. Mi propia implementación puede actualizarse según sea necesario cuando los objetos se mueven.El tiempo que puede hacer eso o no depende de cómo lo implemente. – phkahler
rehacer == actualización; Los considero sinónimos. Pero su punto es correcto: es casi como si necesitaras una bandera sucia para marcar las piezas que cambiaron. – duffymo