Direct Visibility of Point Sets

\(\newcommand{\norm}[1] {\lVert #1 \rVert}
\)
Given a set of points \(P=\{p_i | 1\lt i \lt N\} \in \mathbb{R^{D}}\), and a viewpoint \(C\), the goal is to determine the visible points \(\forall p_i \in P\) with respect to \(C\). The method is based on Sphreical Flipping), where each \(p_i \in P\) is reflected about a sphere, centered at \(C\) and constrained to include all points in \(P\). The flip operator is defined as follows:

\begin{equation}
\hat{p_i} = p_i + 2(R-\norm{p_i})\frac{p_i}{\norm{p_i}}
\end{equation}

Generously, Katz et. al. provide a theoretical proof as well as MATLAB implementation within the paper. We further improve this implementation by applying simplifying \(\hat{p_i}\):

\begin{equation} \label{eq1}
\begin{split}
\hat{p_i} & = p_i + 2(R-\norm{p_i})\frac{p_i}{\norm{p_i}}\\
 & = p_i + \frac{2R}{\norm{p_i}}p_i - 2p_i \\
 & = p_i (\frac{2R}{\norm{p_i}}-1)
\end{split}
\end{equation}
Using this reduction and cpu-friendly optimizations, we could provide a shorter, simpler and more efficient algorithm for the visibility problem. In comparison to the original, our MATLAB implementation runs twice as fast, while significantly reducing the memory usage. Our C implementation is more than \(5\) orders of magnitude faster, easily achieving realtime capability even for very large point clouds.