Hallo,

wie der Titel andeutet suche ich einen Algorithmus um festzustellen ob ein Dreieck aus Sicht eines bestimmten Punktes vollständig durch davorliegende Dreiecke verdeckt ist.
Feststellen ob ein Dreieck durch ein anderes Dreieck verdeckt wird, ist nicht so schwer. Wenn es verdeckt ist, müssen alle Strecken von den Eckpunkten des zu verdeckenden Dreiecks zum Punkt, aus dessen Sicht das Dreieck verdeckt sein soll, das zweite Dreieck schneiden.
Für mehrere Dreiecke ist das aber was gänzlich anderes da die auch konkave Formen bilden können.

Ein paar Besonderheiten die meine Dreiecke erfüllen:

-Die Dreiecke schneiden sich nicht
-Die Dreiecke haben eine durchsichtige Rückseite, wie es bei 3D-Grafik oftmals der Fall (Backface Culling)

Ich hab' im Moment keine Ahnung wie ich das lösen soll. Vielleicht fällt da jemanden was ein.

3d oder 2d?

_________________
Klar Soweit?

Hallo,
ich glaube, es macht kaum Sinn, die einzelnen Dreiecke durchzutesten, ob sie ein anderes Verdecken. Die Performance wird dabei in den Keller gehen. Stattdessen nimm Bounding-Volumes, oder wenige große Dreiecke / konvexe Polygone an Stellen, wo du richtg viel "wegcullen" kannst. Man gibt der Grafikkarte ja auch nicht Dreieck für Dreieck, sondern gleich ganze VBOs.

Gruß mrtrain

3D


Ich hätte wohl doch noch bischen mehr drum herum erzählen sollen: Ich will das sowieso nur beim Start des Programms benutzen, d.h. es würde sich nur die Ladezeit verändern.
Konkret möchte ich damit Schattenvolumen erstellen die aus möglichst wenig Dreiecken bestehen. z.B. würde ein Stuhl im Zimmer immernoch einen Schatten für das Licht im Flur werfen, auch wenn da noch eine Wand dazwischen ist. Und das kostet sinnloserweise Füllrate.
Außerdem sind die Lichter dazu statisch, wodurch auch die Volumen nicht aktualisiert werden müssen. Vielleicht mach ich das später auch noch so das die Volumen auf die Festplatte gespeichert werden, sodass ich sie sogar nur dann neu berechnen müsste, wenn ich was am Licht oder an der Levelgeometrie ändere.

Hallo Schläfer,

die einfachste Variante wäre wahrscheinlich die Szene einmal aus der Sicht des Lichtes zu rendern und mithilfe von Occlusion Queries bestimmen, ob sich deine Dreiecke hinter der Wand befinden.

Viele Grüße
dj3hut1

_________________
Wenn Gauß heute lebte, wäre er ein Hacker.
Peter Sarnak, Professor an der Princeton University