Jakob, JohannesBuchenau, ChristophGuthe, MichaelBommes, David and Huang, Hui2019-07-112019-07-1120191467-8659https://doi.org/10.1111/cgf.13797https://diglib.eg.org:443/handle/10.1111/cgf13797A mandatory component for many point set algorithms is the availability of consistently oriented vertex-normals (e.g. for surface reconstruction, feature detection, visualization). Previous orientation methods on meshes or raw point clouds do not consider a global context, are often based on unrealistic assumptions, or have extremely long computation times, making them unusable on real-world data. We present a novel massively parallelized method to compute globally consistent oriented point normals for raw and unsorted point clouds. Built on the idea of graph-based energy optimization, we create a complete kNN-graph over the entire point cloud. A new weighted similarity criterion encodes the graph-energy. To orient normals in a globally consistent way we perform a highly parallel greedy edge collapse, which merges similar parts of the graph and orients them consistently. We compare our method to current state-of-the-art approaches and achieve speedups of up to two orders of magnitude. The achieved quality of normal orientation is on par or better than existing solutions, especially for real-world noisy 3D scanned data.Computing methodologiesShape analysisTheory of computationComputational geometryMassively parallel algorithms10.1111/cgf.13797163-173