Sunday, February 1, 2015

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.