libreria - sort algorithm c++

¿Verificación de distancia 3D muy rápida?

Question

¿Hay alguna manera de hacer un control de distancia 3D rápido y sucio donde los resultados son difíciles, pero es muy, muy rápido? Necesito hacer una clasificación en profundidad. Yo uso STL sort esta manera:

bool sortfunc(CBox* a, CBox* b)
{
    return a->Get3dDistance(Player.center,a->center) <
      b->Get3dDistance(Player.center,b->center);
}

float CBox::Get3dDistance( Vec3 c1, Vec3 c2 )
{
    //(Dx*Dx+Dy*Dy+Dz*Dz)^.5 
    float dx = c2.x - c1.x;
    float dy = c2.y - c1.y;
    float dz = c2.z - c1.z;

return sqrt((float)(dx * dx + dy * dy + dz * dz));
}

¿Hay posiblemente una manera de hacerlo sin una raíz cuadrada o posiblemente sin multiplicación?

Answer 1

¿Con qué frecuencia se actualizan los vectores de entrada y con qué frecuencia se ordenan? Dependiendo de su diseño, podría ser bastante eficiente ampliar la clase "Vec3" con una distancia precalculada y ordenarla en su lugar. Especialmente relevante si su implementación le permite usar operaciones vectorizadas.

Aparte de eso, vea el artículo de flipcode.com sobre la aproximación de funciones de distancia para una discusión sobre otro enfoque más.

Answer 2

Aquí hay una ecuación que podría ayudarte a deshacerte tanto de sqrt como de multiplicar:

max(|dx|, |dy|, |dz|) <= distance(dx,dy,dz) <= |dx| + |dy| + |dz|

Esto le permite obtener un rango estimado de la distancia que lo mantiene dentro de un factor de 3 (los límites superior e inferior pueden diferir en un máximo de 3x). Luego puede ordenar, por ejemplo, el número más bajo. Luego debe procesar la matriz hasta llegar a un objeto que está 3 veces más lejos que el primer objeto que oscurece. Entonces se garantiza que no encontrará ningún objeto que esté más cerca más adelante en la matriz.

Por cierto, ordenar es exagerado aquí. Una forma más eficiente sería hacer una serie de cubos con diferentes estimaciones de distancia, digamos [1-3], [3-9], [9-27], ... Luego coloque cada elemento en un cubo. Procese los cucharones de menor a mayor hasta que llegue a un objeto que los oscurezca. Procesa 1 cubo adicional solo para estar seguro.

Por cierto, multiplicar punto flotante es bastante rápido hoy en día. No estoy seguro de que gane mucho convirtiéndolo en valor absoluto.

Answer 3

Dependiendo levemente de la cantidad de puntos con los que se está utilizando para comparar, lo que está más abajo es que se obtiene la lista de puntos en orden aproximado suponiendo que todos los puntos cambian en todas las iteraciones.

1) Reescribe la matriz en una sola lista de distancias de Manhattan sin [i] = abs (posn [i] .x - player.x) + abs (posn [i] .y - player.y) + abs (posn [ i] .z - player.z);

2) Ahora puede usar radix sort en números de punto flotante para ordenarlos.

Tenga en cuenta que, en la práctica, esto será mucho más rápido que ordenar la lista de posiciones 3D porque reduce significativamente los requisitos de ancho de banda de memoria en la operación de clasificación que se va a gastar todo el tiempo y en los que van y escriben impredecibles que se produzca. Esto se ejecutará en el tiempo O (N).

Si muchos de los puntos son estacionarios en cada dirección, existen algoritmos mucho más rápidos, como el uso de KD-Trees, aunque la implementación es bastante más compleja y es mucho más difícil obtener buenos patrones de acceso a la memoria.

Answer 4

Es posible que desee considerar el almacenamiento en caché de la distancia entre el reproductor y el objeto a medida que lo calcula, y luego usarlo en su sortfunc . Esto dependerá de cuántas veces su función de ordenamiento vea cada objeto, por lo que es posible que tenga que hacer un perfil para estar seguro.

Lo que quiero decir es que su función de clasificación podría hacer algo como esto:

compare(a,b);
compare(a,c);
compare(a,d);

y calcularías la distancia entre el jugador y ''a'' cada vez.

Como otros han mencionado, puede omitir el sqrt en este caso.

Answer 5

Estoy decepcionado de que los grandes trucos matemáticos parecen perderse. Aquí está la respuesta que estás pidiendo. Fuente es el excelente sitio web de Paul Hsieh: http://www.azillionmonkeys.com/qed/sqroot.html . Tenga en cuenta que no le importa la distancia; harás bien para tu especie con el cuadrado de distancia, que será mucho más rápido.

En 2D, podemos obtener una aproximación grosera de la métrica de distancia sin una raíz cuadrada con la fórmula:

distanceapprox (x, y) = (1 + 1 / (4-2 * √2)) / 2 * min ((1 / √2) * (| x | + | y ​​|), max (| x |, | y |)) http://i52.tinypic.com/280tbnc.gif

que se desviará de la respuesta verdadera en un 8% como máximo. Una derivación similar para 3 dimensiones conduce a:

distanceapprox (x, y, z) = (1 + 1 / 4√3) / 2 * min ((1 / √3) * (| x | + | y ​​| + | z |), max (| x |, | y |, | z |)) http://i53.tinypic.com/2vlphz8.gif

con un error máximo de aproximadamente 16%.

Sin embargo, algo que debe señalarse es que a menudo la distancia solo es necesaria para fines de comparación. Por ejemplo, en el cálculo clásico del conjunto mandelbrot (z ← z2 + c), la magnitud de un número complejo se compara típicamente con una longitud de radio límite de 2. En estos casos, uno simplemente puede soltar la raíz cuadrada, al cuadrar esencialmente ambos lados de la comparación (ya que las distancias son siempre no negativas). Es decir:

    √(Δx2+Δy2) < d is equivalent to Δx2+Δy2 < d2, if d ≥ 0

También debo mencionar que el Capítulo 13.2 de "Understanding Digital Signal Processing" de Richard G. Lyons tiene una increíble colección de algoritmos de distancia 2D (también conocido como aproximaciones de magnitud de números complejos). Como un ejemplo:

Max = x> y? x: y;

Min = x <y? x: y;

if (Min <0.04142135Max)

|V| = 0.99 * Max + 0.197 * Min;

más

|V| = 0.84 * Max + 0.561 * Min;

que tiene un error máximo de 1.0% de la distancia real. La pena, por supuesto, es que estás haciendo un par de ramas; pero incluso la respuesta "más aceptada" a esta pregunta tiene al menos tres ramas en ella.

Si realmente quiere hacer una estimación de distancia súper rápida con una precisión específica, puede hacerlo escribiendo su propia estimación fsqrt () simplificada utilizando el mismo método básico que usan los proveedores del compilador, pero con una precisión menor, haciendo una número fijo de iteraciones. Por ejemplo, puede eliminar el manejo de casos especiales para números extremadamente pequeños o grandes, y / o también reducir el número de iteraciones de Newton-Rapheson. Esta fue la estrategia clave que subyace a la implementación de la raíz cuadrada inversa llamada "Quake 3": es el clásico algoritmo de Newton con exactamente una iteración.

No asuma que su implementación de fsqrt () es lenta sin una evaluación comparativa y / o leyendo las fuentes. La mayoría de las implementaciones modernas de la biblioteca fsqrt () son sin ramas y realmente condenadamente rápidas. Aquí, por ejemplo, se encuentra una antigua implementación de fsqrt de coma flotante de IBM. La optimización prematura es, y siempre será, la raíz de todo mal.

Answer 6

Lo que suelo hacer es primero filtrar por distancia de Manhattan

float CBox::Within3DManhattanDistance( Vec3 c1, Vec3 c2, float distance )
{
    float dx = abs(c2.x - c1.x);
    float dy = abs(c2.y - c1.y);
    float dz = abs(c2.z - c1.z);

    if (dx > distance) return 0; // too far in x direction
    if (dy > distance) return 0; // too far in y direction
    if (dz > distance) return 0; // too far in z direction

    return 1; // we''re within the cube
}

De hecho, puedes optimizar esto aún más si sabes más sobre tu entorno. Por ejemplo, en un entorno donde hay un terreno como un simulador de vuelo o un juego de disparos en primera persona, el eje horizontal es mucho más grande que el eje vertical. En dicho entorno, si dos objetos están muy separados, es muy probable que estén separados más por los ejes xey en lugar del eje z (en un tirador en primera persona, la mayoría de los objetos comparten el mismo eje z). Entonces, si compara primero xey, puede regresar temprano de la función y evitar hacer cálculos adicionales:

float CBox::Within3DManhattanDistance( Vec3 c1, Vec3 c2, float distance )
{
    float dx = abs(c2.x - c1.x);
    if (dx > distance) return 0; // too far in x direction

    float dy = abs(c2.y - c1.y);
    if (dy > distance) return 0; // too far in y direction

    // since x and y distance are likely to be larger than
    // z distance most of the time we don''t need to execute
    // the code below:

    float dz = abs(c2.z - c1.z);
    if (dz > distance) return 0; // too far in z direction

    return 1; // we''re within the cube
}

Lo siento, no me di cuenta de que la función se usa para ordenar. Todavía puede usar la distancia de Manhattan para obtener un primer tipo muy difícil:

float CBox::ManhattanDistance( Vec3 c1, Vec3 c2 )
{
    float dx = abs(c2.x - c1.x);
    float dy = abs(c2.y - c1.y);
    float dz = abs(c2.z - c1.z);

    return dx+dy+dz;
}

Después de la primera clasificación aproximada, puede obtener los resultados más altos, por ejemplo, los 10 jugadores más cercanos y volver a ordenar usando los cálculos de distancia adecuados.

Answer 7

Puede comparar cuadrados de distancias en lugar de distancias reales, ya que d ² = (x ₁ -x ₂ ) ² + (y ₁ -y ₂ ) ² + (z ₁ -z ₂ ) ² . No elimina la multiplicación, pero elimina la operación de raíz cuadrada.

Answer 8

Puede omitir la raíz cuadrada porque para todos los números positivos (o realmente no negativos) x e y , si sqrt(x) < sqrt(y) entonces x < y . Como está sumando cuadrados de números reales, el cuadrado de cada número real no es negativo, y la suma de los números positivos es positiva, la condición de raíz cuadrada se cumple.

Sin embargo, no puede eliminar la multiplicación sin cambiar el algoritmo. Aquí hay un contraejemplo: si x es (3, 1, 1) e y es (4, 0, 0), |x| < |y| |x| < |y| porque sqrt(1*1+1*1+3*3) < sqrt(4*4+0*0+0*0) y 1*1+1*1+3*3 < 4*4+0*0+0*0 , pero 1+1+3 > 4+0+0 .

Dado que las CPU modernas pueden calcular un producto de puntos más rápido de lo que realmente pueden cargar los operandos de la memoria, es poco probable que tenga algo que ganar eliminando la multiplicación de todos modos (creo que las CPU más nuevas tienen una instrucción especial que puede calcular un producto de punto cada 3 ciclos!).

No consideraría cambiar el algoritmo sin hacer primero un perfil. Su elección de algoritmo dependerá en gran medida del tamaño de su conjunto de datos (¿cabe en la memoria caché?), Con qué frecuencia debe ejecutarlo y qué hace con los resultados (detección de colisión, ¿oclusión de proximidad?).

Answer 9

Si esto es simplemente un valor para la clasificación , entonces puede cambiar el sqrt () por un abs (). Si necesita comparar distancias con valores establecidos, obtenga el cuadrado de ese valor.

Por ejemplo, en lugar de verificar sqrt (...) contra a, puedes comparar abs (...) contra a * a.

Answer 10

Si pudieras centrar tus coordenadas alrededor del jugador, ¿usar coordenadas esféricas? Entonces podrías ordenar por el radio.

Eso es un gran si, sin embargo.

Answer 11

Si su operación ocurre mucho, podría valer la pena colocarla en alguna estructura de datos 3D. Probablemente necesites la clasificación por distancia para decidir qué objeto es visible o alguna tarea similar. En orden de complejidad puedes usar:

1. Subdivisión uniforme (cúbica)

   Divida el espacio utilizado en celdas y asigne los objetos a las celdas. Acceso rápido al elemento, los vecinos son triviales, pero las celdas vacías ocupan mucho espacio.

2. Quadtree

   Dado un umbral, divida el espacio usado recursivamente en cuatro cuadrantes hasta que haya menos cantidad de umbral dentro del objeto. Elemento de acceso logarítmico si los objetos no se apilan uno sobre el otro, los vecinos no son difíciles de encontrar, la solución es eficiente en el espacio.

3. Octree

   Igual que Quadtree, pero se divide en 8, óptimo incluso si los objetos están uno encima del otro.

4. Árbol Kd

   Dada cierta función de costo heurístico, y un umbral, divide el espacio en dos mitades con un plano donde la función de costo es mínima. (Ejemplo: la misma cantidad de objetos en cada lado). Repita recursivamente hasta alcanzar el umbral. Siempre logarítmico, los vecinos son más difíciles de conseguir, más eficientes en el uso del espacio (y funcionan en todas las dimensiones).

Usando cualquiera de las estructuras de datos anteriores, puede comenzar desde una posición e ir de vecino a vecino para enumerar los objetos a mayor distancia. Puede detenerse en la distancia de corte deseada. También puede omitir las celdas que no se pueden ver desde la cámara.

Para la comprobación de la distancia, puede hacer una de las rutinas mencionadas anteriormente, pero en última instancia no escalarán bien con el aumento de la cantidad de objetos. Se pueden usar para mostrar datos que requieren cientos de gigabytes de espacio en el disco duro.

Answer 12

Si te preocupa el rendimiento, también debes ocuparte de la forma en que envías tus argumentos:

float Get3dDistance( Vec3 c1, Vec3 c2 );

implica dos copias de la estructura Vec3. Use referencias en su lugar:

float Get3dDistance( Vec3 const & c1, Vec3 const & c2 );

Answer 13

Tenga en cuenta que para 2 distancias (no negativas) A y B , si sqrt(A) < sqrt(B) , entonces A < B . Cree una versión especializada de Get3DDistance() ( GetSqrOf3DDistance() ) que no llame a sqrt () que se usaría solo para sortfunc() .