Wie finde ich die Umgebung eines Tetraeders?

9

Ich suche nach der am wenigsten minimierten Gleichung, um die Mittelkoordinaten und den Radius einer Tetraeder-Umkreiskugel bei vier 3D-Punkten zu finden.

Was ich im Internet gefunden habe, befasst sich hauptsächlich mit der Umfangskugel eines flachen 3D-Dreiecks oder einigen groben mathematischen Definitionen oder einem sehr einzelnen Fall wie regulären Tetraedern. Wie auch immer, ich habe es geschafft, die folgende Gleichung zu finden, aber ich habe etwas verpasst:

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

Mein Wissen auf diesem Gebiet hat seine Grenzen, aber ich denke, ich kann mit Matrizen und Vektoroperationen umgehen. Aber ist der rechte Teil der Gleichung das Quadrat der Norm jedes Vektors? (die in einen Vektor sind). Ist die Gleichung gültig? Ist es nur der Schriftsteller, der träge vergessen hat, | d1 | ^ 2 zu schreiben? Oder ist es eine übliche Methode, eine mathematische Eigenschaft zu definieren?

PS: Es ist für eine Delaunay Triangulation-Implementierung. Die Gleichung (Nummer 9) befindet sich unter folgendem Link: https://www2.mps.mpg.de/homes/daly/CSDS/t4h/tetra.htm

herme5
quelle
4
Versuchen Sie Mathe StackExchange.
Majte
Danke, ich habe einen Weg gefunden, die Umgebung dort zu berechnen!
Herme5
1
@JamesAMD Der Link lautet www2.mps.mpg.de/homes/daly/CSDS/t4h/tetra.htm .
Herme5
3
@ herme5, zögern Sie nicht, hier Ihre eigene Antwort zu posten, wie Sie die Antwort berechnen. Viele Menschen werden möglicherweise in Zukunft hierher kommen, um die Antwort zu finden, und wenn Sie sie teilen, ist dies für sie wertvoll. Es ist völlig akzeptabel, eine eigene Antwort zu posten und diese sogar zu akzeptieren.
Tim Holt
2
Danke für den Hinweis @TimHolt. Ich werde es tun ! Trotzdem bin ich mir nicht mehr sicher, wie ich es gemacht habe, es war vor mehr als 2 Jahren! Lassen Sie mich einfach meine alte Implementierung finden und ansehen
herme5

Antworten:

2

Obwohl dies ein uralter Thread ist, dachte ich, dass es für die Nachwelt schön sein könnte, ein bisschen zu referenzieren. Die Quelle der Formel stammt von Geometric Tools for Computer Graphics von Philip J. Schneider und David H. Eberly. Laut Text etwas zu beachten

Das Tetraeder V0, V1, V2, V3 ist so angeordnet, dass es isomorph zu dem kanonischen (0, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1) ist ).

Nach meinem Verständnis des Isomorphismus kann es in der Geometrie verschiedene Bedeutungen geben. Wenn er in Bezug auf die Graphentheorie isomorph bedeutet, sollte sich der folgende Code korrekt verhalten, da die Topologie eines Tetraeders dieselbe ist (K4, ein vollständiger Graph). Ich habe die Ergebnisse der Funktion gegen Wolfram Alpha unter Verwendung verschiedener Permutationen in der Reihenfolge der kanonischen Eckpunkte getestet und keinen Unterschied im Ergebnis festgestellt. Wenn sich die Reihenfolge als Problem herausstellt, schlage ich vor, die Normalen des Dreiecks, das durch die Eckpunkte V1, V2, V3 bei Eingabe dieser Funktion gebildet wird, zu untersuchen und die Punkte wie einen Halbraum mit einem Punktprodukttest zu behandeln, um dies herauszufinden wenn dieses Dreieck in die richtige Richtung zeigt. Wenn nicht, einfachstd::swapvon zwei beliebigen Eckpunkten des Dreiecks wird die Richtung der Normalen umgekehrt, und Sie können fortfahren. Aber wie gesagt, ich sah keinen Unterschied bei verschiedenen Permutationen.

Hier ist der übersetzte Code ohne Verwendung von Matrizen, um Implementierungsverwirrungen zu vermeiden. Er ist ziemlich einfach.

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
quelle