Simulationen nutzen eine geometrische Diskretisierung des realen oder virtuellen Modells, die sogenannte Triangulierung. So sind z.B. in der Automobilindustrie Fahrzeugoberflächen mit mehreren Millionen Dreiecken üblich. Soll die Wärmestrahlung zwischen den Oberflächen in der Simulation eine Rolle spielen, siehe hier, dann ist für jedes dieser Dreiecke zu entscheiden welche anderen Dreiecke “gesehen” werden. Die mathematische Definition dieser Sichtbarkeitsfunktion (visibility) ist relativ einfach, die Sichtbarkeitsberechnung erfordert jedoch erheblichen Rechenaufwand und viel Speicherplatz.
Sichtbarkeitsproblem
Formal ist die Sichtbarkeit zwischen zwei Punkten wie folgt festgelegt:
Seien $\it \bf x$ und $\it \bf y$ Punkte einer Umhüllung $\it \Gamma=\partial\Omega$. Falls keiner der Punkte $ \it s$ der Geraden $$
\newcommand{\x}{{\bf x}}
\newcommand{\y}{{\bf y}}
\newcommand{\Spro}[2]{\langle {#1},{#2} \rangle}
s = t\, \x + (1-t) \, \y , \qquad t \in (0,1) ,
$$ auf $\it \Gamma$ liegt, dann “sieht” $\it \x$ den Punkt $ \it \y$ (und umgekehrt). $$
vis(\x,\y) := \begin{cases}
1 & \text{ falls } \quad t\, \x + (1-t) \, \y \not\in \Gamma, \quad \forall \, t \in (0,1) \\
0 & \mbox{ sonst}
\end{cases}, \quad \x,\y \in \Gamma .
$$ Diese Definition der Sichtbarkeitsfunktion $vis$ bedeutet, daß für zwei Punkt, die sich sehen, alle inneren Punkte der entsprechenden Geraden im Gebiet $\Omega$ liegen. Die Bestimmung bzw. Auswertung von $vis(\x,\y)$ erfolgt mit einer Variante des ray-triangle-intersection-Algorithm in Verbindung mit einer hierarchischen Datenstruktur zur Indizierung des Raumes (octree). Sichtbarkeiten zwischen zwei Dreiecken, wie sie in einer Diskretisierung benötigt wird, können über ihre Mittelpunkte festgelegt werden: Sind $t$ und $\tau$ Dreiecke der Triangulierung mit den Mittelpunkten ${\bf m_t}$ und ${\bf m_\tau}$, dann sei $$ vis(t,\tau) := vis({\bf m_t}, {\bf m_\tau}). $$
Sichtbarkeitsproblem: Bestimme zu allen Paaren von Dreiecken $(t,\tau)$ die Zahlen $vis(t,\tau)$.
Komplexität
Ist $n$ die Anzahl aller Dreiecke im Modell, dann sind also $n$ Tests für ein Dreieck und für das gesamte Modell $n^2$ Tests notwendig Symmetrie und die Tatsache, dass ein Dreieck sich nicht selbst sehen kann, wird an dieser Stelle der Übersichtlichkeit halber unterschlagen. Der Rechenaufwand, das ist die Anzahl der elementaren Operationen, für den einzelnen Test “sieht Dreieck a Dreieck b?” liegt in der Größenordnung ${\mathcal O}( \log_2 n)$. Für das gesamte Problem hat man die Komplexität ${\mathcal O}(n^2 \log_2 n )$.
Hier ein etwas ausführlicher Beitrag zur Sichtbarkeitsberechnung aus dem Jahr 2022.