Concomitant hierarchy construction and rendering of large point clouds

Abstract

Current approaches for rendering large point clouds involve a strenuous preprocessing stage where a hierarchical data-structure is created before rendering. These algorithms do not consider presenting data before the hierarchy construction is finished. In this work we present OMiCroN – Oblique Multipass Hierarchy Creation while Navigating – which is the first algorithm capable of immediately displaying partial renders of the geometry, provided the geometry is made available in Morton order as a stream. By using a pipeline sort algorithm, OMiCroN is capable of parallel data sorting, hierarchy construction, and rendering, which can start as soon as the first sorted prefix of the data is available. In practice, the first partial rendering must only wait for the whole unsorted geometry to be read from disk. OMiCroN is also the first algorithm to implement a bottom-up rendering approach, providing full detail at the beginning, unlike current top-down approaches, which start from an overview of the data, providing full detail later in the process. OMiCroN can also be used to present rendering feedback of the hierarchy creation process. These features are made possible using an “oblique cut”, a novel data structure that separates the renderable from the non-renderable portions of the hierarchy.