A Linear Method to Consistently Orient Normals of a 3D Point Cloud

Correctly and consistently orienting a set of normal vectors associated with a point cloud sampled from a surface in 3D is a difficult procedure necessary for further downstream processing of sampled 3D geometry, such as surface reconstruction and registration. It is difficult because correct orientation cannot be achieved without global considerations of the entire point cloud. We present an algorithm to orient a given set of normals of a 3D point cloud of size N , whose main computational component is the least-squares solution of an O (N ) linear system, mostly sparse, derived from the classical Stokes' theorem. We show experimentally that our method can successfully orient sets of normals computed locally from point clouds containing a moderate amount of noise, representing also 3D surfaces with non-smooth features (such as corners and edges), in a fraction of the time required by state-of-the-art methods.