Détection de collision point-triangle en 3D

Question

Comment corriger l'erreur de virgule flottante dans la simulation physique suivante:

• Point d'origine (x, y, z),
• Point souhaité (x ', y', z ') après l'application des forces.
• Deux triangles (A, B, C) et (B, C, D) qui partagent le bord BC

J'utilise cette méthode pour détecter les collisions:

For each Triangle
    If the original point is in front of the current triangle, and the desired point is behind the desired triangle:
        Calculate the intersection point of the ray (original-desired) and the plane (triangle's normal).
        If the intersection point is inside the triangle edges (!)
            Respond to the collision.
        End If
    End If
Next Triangle

Le problème que je rencontre est que parfois le point tombe dans la zone grise des calculs en virgule flottante, où il est si proche de la ligne BC qu'il n'entre pas en collision avec l'un des triangles, même si, techniquement, il devrait toujours se heurter à un l'autre depuis qu'ils partagent un avantage. Lorsque cela se produit, le point passe juste entre les deux triangles de partage des arêtes. J'ai marqué (!) sur une ligne du code, car je pense que c'est là que je devrais apporter un changement.

Une idée qui fonctionne dans des situations très limitées consiste à ignorer les tests de bords. Transformer efficacement les triangles en plans. Cela ne fonctionne que lorsque mes mailles sont des coques convexes, mais je prévois de créer des formes convexes.

J'utilise spécifiquement les normales du produit scalaire et du triangle pour tous mes tests avant / arrière.

Answer 1

C’est un problème inévitable lors de la prise de vue d’un rayon sur une géométrie avec des arêtes et des sommets. C'est incroyable de voir comment les simulations physiques semblent rechercher la plus petite des inexactitudes numériques!

Certaines des explications et solutions proposées par d’autres répondants ne fonctionneront pas. En particulier:

• L’imprécision numérique peut réellement faire en sorte qu’un rayon "tombe à travers l’espace". Le problème est que nous coupons le rayon avec le plan ABC (obtenant le point P, disons) avant de tester contre la ligne BC. Ensuite, nous intersectons le rayon avec le plan BCD (obtenant le point Q, disons) avant de tester contre la ligne BC. P et Q sont tous deux représentés par l'approximation en virgule flottante la plus proche; il n’ya aucune raison de s’attendre à ce que ceux-ci se trouvent exactement sur les avions sur lesquels ils sont censés se trouver, et donc toute possibilité que vous puissiez avoir les deux P à gauche de BC et Q à droite de BC.

• L'utilisation de tests inférieurs ou égaux ne vous aidera pas; c'est l'inexactitude à l'intersection du rayon et de l'avion qui pose problème.

• Les racines carrées ne sont pas le problème; vous pouvez effectuer tous les calculs nécessaires à l'aide de produits scalaires et de la division en virgule flottante.

Voici quelques solutions authentiques:

• Pour les maillages convexes, vous pouvez simplement tester sur tous les plans et ignorer les arêtes et les sommets, comme vous le dites (en évitant ainsi totalement le problème).

• Ne croisez pas le rayon avec chaque triangle. Utilisez plutôt le produit triple scalaire . (Cette méthode effectue exactement la même séquence de calculs pour le rayon et le bord BC en considérant chaque triangle, en veillant à ce que toute inexactitude numérique soit au moins cohérente entre les deux triangles.)

• Pour les maillages non convexes, donnez de la largeur aux arêtes et aux sommets. Autrement dit, placez une petite sphère à chaque sommet du maillage et placez un mince cylindre le long de chaque bord du maillage. Intersectez le rayon avec ces sphères et cylindres ainsi qu'avec les triangles. Ces figures géométriques supplémentaires empêchent le rayon de passer à travers les arêtes et les sommets du maillage.

Permettez-moi de recommander vivement le livre Détection de collisions en temps réel de Christer Ericson. Vous trouverez une analyse de ce problème aux pages 446 et 828; 448, ainsi qu'une explication de la méthode du triple produit scalaire consistant à intersecter un rayon avec un triangle aux pages 184 et 1889.

Answer 2

On dirait que vous n'incluez pas les tests si c'est sur le bord (vous écrivez "bords du triangle intérieur"). Essayez de remplacer le code par "inférieur ou égal à". (à l'intérieur ou se chevauchant).

Answer 3

Je trouve quelque peu improbable que votre rayon tombe exactement entre les triangles de telle sorte que la précision de la virgule flottante prenne effet. Etes-vous absolument convaincu que c'est bien le problème?

Quoi qu’il en soit, une solution possible est de ne pas tirer sur un seul rayon mais sur trois rayons très proches les uns des autres. Si l’un se situe exactement entre ces deux atleast, il est garanti que l’un des deux autres tombe sur un triangle.

Ceci vous permettra au moins de tester si le problème est vraiment une erreur en virgule flottante ou quelque chose de plus probable.

Answer 4

@Statement: J'utilise déjà déjà un "supérieur ou égal à". comparaison dans mon code, merci pour la suggestion. +1

Ma solution actuelle consiste à ajouter une petite quantité de décalage au test de bord. Fondamentalement, lorsque chaque triangle est testé, ses arêtes sont repoussées d'une très petite quantité pour compenser l'erreur en virgule flottante. En quelque sorte, tester si le résultat d'un calcul en virgule flottante est inférieur à 0,01 plutôt que de tester l'égalité avec zéro.

Est-ce une solution raisonnable?

Answer 5

Si vous effectuez des mesures de distance, faites attention aux racines carrées. Ils ont la mauvaise habitude de jeter la moitié de votre précision. Si vous empilez quelques-uns de ces calculs, vous pouvez avoir de gros problèmes rapidement. Voici une fonction de distance que j'ai utilisée.

double Distance(double x0, double y0, double x1, double y1)
{
  double a, b, dx, dy;

  dx = abs(x1 - x0);
  dy = abs(y1 - y0);

  a = max(dx, dy));
  if (a == 0)
    return 0;
  b = min(dx, dy);

  return a * sqrt( 1 + (b*b) / (a*a) );
}

La dernière opération n'étant pas une racine carrée, vous ne perdez plus la précision.

J'ai découvert cela dans un projet sur lequel je travaillais. Après l’avoir étudié et compris ce qui s’est passé, j’ai retrouvé le programmeur qui, selon moi, était responsable de le féliciter, mais il ne savait pas de quoi je parlais.