Simulationen nutzen eine geometrische Diskretisierung des realen oder virtuellen Modells, die sogenannte Triangulierung. So sind beispielsweise in der Automobilindustrie Fahrzeugoberflächen mit mehreren Millionen Dreiecken üblich. Soll der Wärmestrahlungsaustausch zwischen den Oberflächen in einem Surface-to-Surface-Strahlungsmodell berücksichtigt werden, muss für jedes dieser Dreiecke bestimmt werden, welche anderen Dreiecke sichtbar sind. Die mathematische Definition dieser Sichtbarkeitsfunktion ist vergleichsweise einfach; ihre Berechnung 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 der Sichtbarkeitsberechnung
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.