Contrôle de distance 3D très rapide?

Question

Y a-t-il un moyen de faire une vérification rapide et sale de la distance 3D lorsque les résultats sont approximatifs, mais très très rapide? J'ai besoin de faire du tri en profondeur. J'utilise STL sort comme ceci:

 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));
}
 

Est-il possible de le faire sans racine carrée ou éventuellement sans multiplication?

Answer 1

Vous pouvez laisser de côté la racine carrée parce que, pour toutes positives (ou vraiment, non-négatif) nombre x et y, si sqrt(x) < sqrt(y) alors x < y. Puisque vous êtes en additionnant les carrés des nombres réels, le carré de tout nombre réel non négatif, et la somme de tous les nombres positifs est positif, la racine carrée condition est vraie.

Vous ne pouvez pas éliminer la multiplication, cependant, sans modification de l'algorithme. Voici un contre-exemple: si x est (3, 1, 1) et y (4, 0, 0), |x| < |y| car sqrt(1*1+1*1+3*3) < sqrt(4*4+0*0+0*0) et 1*1+1*1+3*3 < 4*4+0*0+0*0, mais 1+1+3 > 4+0+0.

Depuis les Processeurs modernes peuvent calculer un produit scalaire plus rapidement qu'ils peuvent charger les opérandes de la mémoire, il est peu probable que vous auriez tout à gagner à l'élimination de la multiplier, de toute façon (je pense que les plus récents Processeurs ont une instruction spéciale qui peut calculer un produit scalaire tous les 3 cycles!).

Je ne voudrais pas envisager une modification de l'algorithme sans profilage de la première. Votre choix de l'algorithme dépendra fortement de la taille de votre base de données (correspond-t-il dans le cache?), combien de fois, vous devez l'exécuter, et ce que vous faites avec les résultats (détection de collision? proximité? l'occlusion?).

Answer 2

Ce que j'ai l'habitude de le faire est d'abord de filtrer par une distance 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
}

En fait, vous pouvez optimiser cette plus loin si vous en savez plus sur votre environnement. Par exemple, dans un environnement où il existe un motif comme un simulateur de vol ou à la première personne jeu de tir, l'axe horizontal est beaucoup plus grand que l'axe vertical. Dans un tel environnement, si deux objets sont éloignés, ils sont très probablement plus séparés par l'axe x et y, plutôt que de l'axe des z (dans un jeu de tir première personne, la plupart des objets partagent le même axe z). Donc, si vous avez d'abord comparer x et y, vous pouvez revenir au début de la fonction et éviter de faire des calculs supplémentaires:

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
}

Désolé, je ne savais pas que la fonction est utilisée pour le tri. Vous pouvez toujours utiliser la distance Manhattan afin d'obtenir une très rugueux premier tri:

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;
}

Après la rudesse de la première sorte que vous pouvez alors prendre le plus haut des résultats, disons le top 10 le plus proche des joueurs, et re-trier selon les calculs de distance.

Answer 3

Voici une équation qui pourrait vous aider à vous débarrasser des deux sqrt et de se multiplier:

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

Cela vous procure une fourchette d'estimation de la distance qui les broches vers le bas à l'intérieur d'un facteur de 3 (limites inférieure et supérieure peuvent différer d'au plus 3 fois). Vous pouvez ensuite trier, par exemple, le nombre inférieur. Vous devez ensuite les processus de la matrice jusqu'à ce que vous atteindre un objet qui est 3x plus loin que la première obscurcissement de l'objet. Ensuite, vous êtes garanti de ne pas trouver n'importe quel objet qui est plus proche, plus loin dans le tableau.

Par la manière, le tri est exagéré ici. Un moyen plus efficace serait de faire une série de compartiments avec différentes estimations de distances, dire [1-3], [3-9], [9-27], .... Puis mettre chaque élément dans un seau. Processus de seaux à partir de la plus petite à la plus grande jusqu'à ce que vous atteignez un obscurcissement de l'objet. Processus 1 seau juste pour être sûr.

Par la façon dont, à virgule flottante multiplier assez rapide aujourd'hui. Je ne suis pas sûr de gagner beaucoup en le convertissant en valeur absolue.

Answer 4

Je suis déçu que le grand vieux jeux mathématiques semblent se perdre. Voici la réponse que vous me demandez. La Source est Paul Hsieh est un excellent site web: http://www.azillionmonkeys.com/qed/sqroot.html . Notez que vous ne se soucient pas de distance; vous sera parfait pour votre tri avec le carré de la distance, qui sera beaucoup plus rapide.

---

En 2D, on peut obtenir une approximation plus grossière de la distance métrique sans une racine carrée à la formule:

distanceapprox (x, y) =

qui va s'écarter de la vraie réponse au plus à 8% environ. Une semblable dérivation pour 3 dimensions conduit à:

distanceapprox (x, y, z) =

avec une erreur maximale de l'ordre de 16%.

Cependant, une chose qui doit être souligné, c'est que souvent, la distance n'est nécessaire que pour des fins de comparaison. Par exemple, dans le classique de l'ensemble de mandelbrot (z←z2+c) le calcul, l'ordre de grandeur d'un nombre complexe est généralement comparée à une limite de rayon la longueur de 2. Dans ces cas, on peut simplement déposer la racine carrée, pour l'essentiel par la quadrature des deux côtés de la comparaison (depuis les distances sont toujours non-négatif). C'est-à-dire:

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

Je devrais aussi mentionner que le Chapitre 13.2 de Richard G. Lyon de la "Compréhension de Traitement Numérique du Signal" a une collection incroyable de la 2D à distance des algorithmes (.k.un nombre complexe ampleur des approximations). À titre d'exemple:

Max = x > y ? x : y;

Min = x < y ? x : y;

if ( Min < 0.04142135 Max )

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

d'autre

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

qui a une erreur maximale de 1,0% par rapport à la distance réelle. La peine est bien sûr que vous êtes en train de faire quelques branches.

Answer 5

Notez que pour 2 distances (non négatives) A et B , si sqrt(A) < sqrt(B) , alors A < B . Créez une version spécialisée de Get3DDistance() ( GetSqrOf3DDistance() ) qui n’appelle pas sqrt () et ne serait utilisée que pour les sortfunc() .