  Estimating a consistently oriented normal vector field for an unoriented
point cloud enables a number of important downstream applications in computer
graphics. While normal estimation for a small patch of points can be done with
simple techniques like principal component analysis (PCA), orienting these
normals to be globally consistent has been a notoriously difficult problem.
Some recent methods exploit various properties of the winding number formula to
achieve global consistency with state-of-the-art performance. Despite their
exciting progress, these algorithms either have high space/time complexity, or
do not produce accurate and consistently oriented normals for imperfect data.
In this paper, we derive a novel property from the winding number formula to
tackle this problem: the normal consistency property of the winding number
formula. We refer to this property as the winding number normal consistency
(WNNC). The derived property is based on the simple observation that the
normals (negative gradients) sampled from the winding number field should be
codirectional to the normals used to compute the winding number field. We
further propose to turn the WNNC property into a normal update formula, which
leads to an embarrassingly simple yet effective iterative algorithm that allows
fast and high-quality convergence to a globally consistent normal vector field.
Furthermore, our proposed algorithm only involves repeatedly evaluating the
winding number formula and its derivatives, which can be accelerated and
parallelized using treecode-based approximation algorithms due to their special
structures. Exploiting this fact, we implement a GPU-accelerated treecode-based
solver. Our GPU (and even CPU) implementation can be significantly faster than
the recent state-of-the-art methods for normal orientation from raw points.
