¿Puedo utilizar una list orderada por Morton Code para la detección de colisiones de fase amplia?

Hasta ahora utilicé una list de objects orderados por un solo eje para limitar la cantidad de objects con los que se verifican las colisiones.

La idea es simple: si la coorderada x de dos objects difiere en más de su ancho, es completamente imposible que colisionen. Entonces, si quiero conocer todos los objects posibles dentro de un rectángulo específico, solo necesito verificar aquellos que están dentro de los índices del valor x más pequeño posible y el mayor posible.

Recientemente, aprendí sobre Morton Code como una forma de networkingucir múltiples ejes en un solo valor que preserva la localidad. Sin embargo, las implicaciones para esto no son 100% claras para mí.

¿Puedo determinar algo como "todos los objects con un código morton más pequeño que varA o más grande que varB no puede estar dentro del rectángulo A"? Si es así, ¿cómo determino estos valores?

Visión de set

La técnica de encoding de morton, o curva de order z , genera esencialmente un índice de cuadrícula para una coorderada dada si la cuadrícula se almacena en una matriz de 1 dimensión en order z. Por lo tanto, esto se puede utilizar como una técnica de hashing espacial que puede generar algo similar a un octree / quadtree dentro de una única matriz dimensional.

Entonces, para una determinada forma de colisión arbitraria, si puede determinar el set de códigos morton que abarca esa forma, puede indexar la cuadrícula con estos códigos para ver si hay alguna otra geometry almacenada allí, al igual que con un tree oct / quad .

Al igual que con otras particiones espaciales, encontrar un acierto en uno de estos índices puede implicar directamente que se haya producido una colisión, pero simplemente puede actuar como un método de eliminación selectiva para networkingucir las testings ya que se necesitan más controles de colisión para probar que ocurrió una colisión.

Responder

Lamentablemente, debido a la naturaleza del almacenamiento, no se puede simplemente indicar "un object abarca los índices i a j". Los códigos Morton que abarcan una forma arbitraria probablemente se agrupen en ranges, pero es probable que haya más de 1 range;

Ver esta image (no puedo vincularla ya que es un formatting no compatible).

Una caja; arriba a la izquierda (2.5, 2.5) arriba a la derecha (3.5, 2.5) abajo a la izquierda (2.5, 4.5) abajo a la derecha (3.5, 4.5) – contendría los códigos de Morton; 001111 y 100101 que no son consecutivos.

Normalmente, los objects se indexan traduciendo posiciones de precisión doble / única en un int (a veces se aplica escala a los valores según la escena) que luego se usa para crear el código Morton. Entonces, si quiere encontrar los códigos que abarca un object, debe calcular el set de puntos integers dentro de esa forma y generar los códigos para esas posiciones.

Dado un cuadro delimitador alineado axialmente de un tamaño y position arbitrarios, puede ver cómo esto podría ser bastante directo. En 2d, traduzca las esquinas a la position int más cercana, luego comience desde la parte superior izquierda, incremente x por 1 hasta que golpee el lado derecho x, luego incremente y y repita. Continúe repitiendo hasta y = abajo y (suponiendo que el valor y es positivo en la pantalla);

for (int y = ceiling(top); u <= floor(bottom); ++y { for (int x = ceiling(left); x <= floor(right); ++x { Geometry* geometry; int mortonCode = generateMortonCode(x, y); if ((geometry = geometryArray[mortonCode]) != NULL) { collisionCheck(rectangle, geometry); } } } 

Nota: Para los usuarios de C / C ++, al networkingondear utilizando un molde a int algunas veces se dará un número fuera de la caja, por lo tanto, use el techo y el piso; para el techo de uso superior e izquierdo, para el piso de uso inferior y derecho. De nuevo, esto supone que y es positivo hacia abajo, por lo tanto, abajo> arriba.

Nota: para la detección de colisiones, es posible que desee permitir la generación de códigos que rodean la forma (cambiar el techo y el piso en el código anterior) para proporcionar un set ligeramente mayor de puntos que definitivamente cubrirán un área más grande que la forma que está revisando.