Comment trouver la circonscription d'un tétraèdre?

9

Je recherche l'équation la plus minimisée pour trouver les coordonnées du centre et le rayon d'une circonférence de tétraèdre étant donné quatre points 3D.

Ce que j'ai trouvé sur Internet concerne principalement la sphère circulaire d'un triangle plat en 3D, ou quelques définitions mathématiques approximatives, ou un cas très unique tel que les tétraèdres réguliers. Quoi qu'il en soit, j'ai réussi à trouver l'équation ci-dessous mais j'ai raté quelque chose:

    ->  ->      ->
let d1, d2, and d3 three vectors of any face of the triangle :

    | d1x  d1y  d1z |   | x |   | d1^2 |
2 * | d2x  d2y  d2z | * | y | = | d2^2 |
    | d3x  d3y  d3z |   | z |   | d3^2 |

Mes connaissances dans ce domaine ont leurs limites mais je pense pouvoir gérer des matrices et des opérations vectorielles. Mais la partie droite de l'équation est-elle le carré de la norme de chaque vecteur? (qui sont dans un vecteur). L'équation est-elle valide? Est-ce juste l'écrivain qui a paresseusement oublié d'écrire | d1 | ^ 2? Ou Est-ce une façon courante de définir une propriété mathématique.

PS: C'est pour une implémentation de Delaunay Triangulation. L'équation (numéro 9) se trouve dans le lien suivant: https://www2.mps.mpg.de/homes/daly/CSDS/t4h/tetra.htm

herme5
la source
4
Essayez maths stackexchange.
Majte
Merci, j'ai trouvé un moyen de calculer la circonscription là-bas!
herme5
1
@JamesAMD le lien est www2.mps.mpg.de/homes/daly/CSDS/t4h/tetra.htm .
herme5
3
@ herme5, n'hésitez pas à publier votre propre réponse ici sur la façon dont vous calculez la réponse. Beaucoup de gens peuvent venir ici à l'avenir dans l'espoir de trouver la réponse, et vous la partagerez leur sera précieuse. Il est tout à fait acceptable de publier votre propre réponse et même de l'accepter.
Tim Holt
2
Merci pour l'avis @TimHolt. Je vais le faire ! Néanmoins je ne sais plus comment je l'ai fait, c'était il y a plus de 2 ans! laissez-moi juste trouver et jeter un œil à mon ancienne implémentation
herme5

Réponses:

2

Bien qu'il s'agisse d'un fil ancien, j'ai pensé qu'il pourrait être intéressant pour la postérité d'avoir un peu de référence. La source de la formule provient de Geometric Tools for Computer Graphics par Philip J. Schneider et David H. Eberly. Quelque chose à noter, selon le texte

Le tétraèdre V0, V1, V2, V3 est ordonné de façon à être isomorphe au canon (0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1 ).

Si je comprends bien l'isomorphisme , il peut y avoir plusieurs significations différentes lorsqu'il est utilisé en géométrie. S'il veut dire isomorphe en ce qui concerne la théorie des graphes, alors le code suivant devrait se comporter correctement, car la topologie de tout tétraèdre est la même (K4, un graphe complet). J'ai testé les résultats de la fonction contre le wolfram alpha en utilisant diverses permutations dans l'ordre des sommets canoniques, et je n'ai vu aucune différence dans le résultat. Si l'ordre se révèle être un problème, je suggère d'examiner la normale du triangle formé par les sommets V1, V2, V3 lors de l'entrée dans cette fonction, et de traiter les points comme un demi-espace avec un test de produit scalaire pour comprendre si ce triangle est orienté dans le bon sens. Si ce n'est pas le cas, un simplestd::swapl'un des deux sommets du triangle inversera la direction de la normale et vous pourrez continuer. Mais comme je l'ai dit, je n'ai vu aucune différence avec diverses permutations.

Voici le code traduit sans utiliser de matrices pour éviter toute confusion d'implémentation, c'est assez simple;

void Circumsphere(const Vec3& v0, const Vec3& v1, const Vec3& v2, const Vec3& v3, Vec3* center, float* radius)
{
  //Create the rows of our "unrolled" 3x3 matrix
  Vec3 Row1 = v1 - v0;
  float sqLength1 = length2(Row1);
  Vec3 Row2 = v2 - v0;
  float sqLength2 = length2(Row2);
  Vec3 Row3 = v3 - v0;
  float sqLength3 = length2(Row3);

  //Compute the determinant of said matrix
  const float determinant =   Row1.x * (Row2.y * Row3.z - Row3.y * Row2.z)
                            - Row2.x * (Row1.y * Row3.z - Row3.y * Row1.z)
                            + Row3.x * (Row1.y * Row2.z - Row2.y * Row1.z);

  // Compute the volume of the tetrahedron, and precompute a scalar quantity for re-use in the formula
  const float volume = determinant / 6.f;
  const float iTwelveVolume = 1.f / (volume * 12.f);

  center->x = v0.x + iTwelveVolume * ( ( Row2.y * Row3.z - Row3.y * Row2.z) * sqLength1 - (Row1.y * Row3.z - Row3.y * Row1.z) * sqLength2 + (Row1.y * Row2.z - Row2.y * Row1.z) * sqLength3 );
  center->y = v0.y + iTwelveVolume * (-( Row2.x * Row3.z - Row3.x * Row2.z) * sqLength1 + (Row1.x * Row3.z - Row3.x * Row1.z) * sqLength2 - (Row1.x * Row2.z - Row2.x * Row1.z) * sqLength3 );
  center->z = v0.z + iTwelveVolume * ( ( Row2.x * Row3.y - Row3.x * Row2.y) * sqLength1 - (Row1.x * Row3.y - Row3.x * Row1.y) * sqLength2 + (Row1.x * Row2.y - Row2.x * Row1.y) * sqLength3 );

  //Once we know the center, the radius is clearly the distance to any vertex
  *radius = length(*center - v0);
}
Jon Koelzer
la source