$

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.

## No comments:

Post a Comment