Fast and Globally Consistent Normal Orientation based on the Winding Number Normal Consistency
DescriptionEstimating consistently oriented normals for point clouds enables a number of important applications in computer graphics such as surface reconstruction. While local normal estimation is possible 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 propose a novel property from the winding number formula, Winding Number Normal Consistency (WNNC), to tackle this problem. 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. Since the WNNC property itself does not resolve the inside/outside orientation ambiguity, we further propose to incorporate an objective function from Parametric Gauss Reconstruction (PGR). We propose to iteratively update normals by alternating between WNNC-based normal updates and PGR-based gradient descents, 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 a treecode-based approximation algorithm 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. Our code is integrated with the popular PyTorch framework to facilitate further research into winding numbers, and is publicly available at https://jsnln.github.io/wnnc/index.html.
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 propose a novel property from the winding number formula, Winding Number Normal Consistency (WNNC), to tackle this problem. 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. Since the WNNC property itself does not resolve the inside/outside orientation ambiguity, we further propose to incorporate an objective function from Parametric Gauss Reconstruction (PGR). We propose to iteratively update normals by alternating between WNNC-based normal updates and PGR-based gradient descents, 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 a treecode-based approximation algorithm 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. Our code is integrated with the popular PyTorch framework to facilitate further research into winding numbers, and is publicly available at https://jsnln.github.io/wnnc/index.html.
Event Type
Technical Papers
TimeWednesday, 4 December 202410:56am - 11:08am JST
LocationHall B5 (1), B Block, Level 5
