## 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:

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

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}$$:

\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}

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.