koplanaren Dreieck Kreuzung Olivier Devillers, Philippe Guigue

Question

Ich denke, es fehlen einige Tests in https://hal.inria.fr/inria-00072100/document

Dieses Dokument beschreibt die Kreuzung von zwei Dreiecken in 3D-Raum beschreibt. Es gibt zwei Tests: einen für das Überqueren von Dreiecken und einen für koplanare Dreiecke.

9 zeigt alle erforderlichen Tests für koplanare Dreiecke, wenn p1 in der Region R11 ist:

Test I: [r2, p2, q1], überprüfen q1 in R11?

Wenn nicht: Test IIa: [r2, p1, q1], q1 in R12 prüfen?

Wenn nicht: Test IIIa: [p1, p2, q1], q1 in R13 prüfen?

Wenn ja: Kreuzung r2p2 mit p1q1. Aber in diesem Fall gibt es keine weiteren Überprüfungen. r1 ist nicht geprüft! r1 könnte in R11, R12 oder R13 sein. Wenn r1 in Region R13 ist, müssen Sie r2p2 mit p1r1 schneiden. Und schließlich müssen Sie einige Schnittpunkte von q1r1 mit p2q2 oder q2r2 machen.

Haben Devillers und Guigue diese Tests vergessen ??

Answer 1

OK, ich fand die Antwort. Dieser Algorithmus prüft nur, ob 2 Dreiecke sich schneiden. Das Ergebnis ist kein neues Polygon, Dreieck oder Eckpunkt, das Ergebnis ist nur ein Wahr oder ein Falsch. Sobald der Algorithmus eine Kreuzung erkannt hat, hört er auf, nach weiteren Kreuzungen zu suchen. Deshalb wird r1 in diesem speziellen Fall nicht mehr überprüft.

Answer 2

Dieses Programm ist wirklich verwirrend.

Wenn Dreiecke koplanar sind, wird im 2D-Raum geprüft, ob sich die Dreiecke überschneiden.

Wenn sie nicht koplanar sind, wird nicht nur im 3D-Raum geprüft, sondern auch die Schnittpunkte berechnet.