Abstract Achieving realistic rendering of 3D scenes in real time using path tracing is challenging due to the high sample count required, with ray tracing as the bottleneck. Focusing on voxels as a geometry representation offers significant opportunities for optimizations, especially for tracing the rays, but also for computing the samples. We propose a novel multilayered spatial structure augmented with in‐cell axis‐aligned distance fields (AADF) operating as caches. Our nested cell structure already accelerates ray tracing 3‐5x compared to the state‐of‐the‐art dense spatial structures, such as variants of directed acyclic graphs (DAG). Using the AADFs (constructed while rendering) inside the cells, we can double the ray throughput again (total 10x). As an application, exploiting nested AADFs (NAADFs) also allows us to double the speed of global illumination computations while significantly reducing artifacts from camera motion, such as flickering, blurring, ghosting, and aliasing, all of which are especially important in voxel worlds with sharp edges. We achieve this by adapting temporal antialiasing (TAA) to retain the last 32 frames rather than a single history buffer to create the final antialiased image, since the discretized voxel structure requires much less memory to store the quantized positions and normals of ray bounces. The sample accumulation for global illumination is optimized by compressing and separating lit/unlit samples, and we apply 8x8 window spatial resampling based on a reservoir‐based spatiotemporal importance resampling (ReSTIR) method. Our proposed NAADFs support editing with quick updates to the acceleration in the background, overlays of non‐aligned dynamic geometry, and can be easily extended to support transform‐aware compression or to represent huge real‐world scans. Retaining many past frames rather than just combining them opens up new opportunities to remove spatial and temporal artifacts in path tracing for global illumination.

International audience

Abstract Reconstructing 2D curves from sample points has long been a critical challenge in computer graphics, finding essential applications in vector graphics. The design and editing of curves on surfaces has only recently begun to receive attention, primarily relying on human assistance, and where not, limited by very strict sampling conditions. In this work, we formally improve on the state‐of‐the‐art requirements and introduce an innovative algorithm capable of reconstructing closed curves directly on surfaces from a given sparse set of sample points. We extend and adapt a state‐of‐the‐art planar curve reconstruction method to the realm of surfaces while dealing with the challenges arising from working on non‐Euclidean domains. We demonstrate the robustness of our method by reconstructing multiple curves on various surface meshes. We explore novel potential applications of our approach, allowing for automated reconstruction of curves on Riemannian manifolds.

Abstract We introduce a Delaunay‐based algorithm for reconstructing the underlying surface of a given set of unstructured points in 3D. The implementation is very simple, and it is designed to work in a parameter‐free manner. The solution builds upon the fact that in the continuous case, a closed surface separates the set of maximal empty balls (medial balls) into an interior and exterior. Based on discrete input samples, our reconstructed surface consists of the interface between Voronoi balls, which approximate the interior and exterior medial balls. An initial set of Voronoi balls is iteratively processed, merging Voronoi‐ball pairs if they fulfil an overlapping error criterion. Our complete open‐source reconstruction pipeline performs up to two quick linear‐time passes on the Delaunay complex to output the surface, making it an order of magnitude faster than the state of the art while being competitive in memory usage and often superior in quality. We propose two variants (local and global), which are carefully designed to target two different reconstruction scenarios for watertight surfaces from accurate or noisy samples, as well as real‐world scanned data sets, exhibiting noise, outliers, and large areas of missing data. The results of the global variant are, by definition, watertight, suitable for numerical analysis and various applications (e.g., 3D printing). Compared to classical Delaunay‐based reconstruction techniques, our method is highly stable and robust to noise and outliers, evidenced via various experiments, including on real‐world data with challenges such as scan shadows, outliers, and noise, even without additional preprocessing.

Abstract Determining connectivity between points and reconstructing their shape boundaries are long‐standing problems in computer graphics. One possible approach to solve these problems is to use a proximity graph. We propose a new proximity graph computed by intersecting the to‐date rarely used proximity‐based graph called spheres‐of‐influence graph (SIG) with the Delaunay triangulation (DT). We prove that the resulting graph, which we name SIGDT, contains the piece‐wise linear reconstruction for a set of unstructured points in the plane for a sampling condition superseding current bounds and capturing well practical point sets' properties. As an application, we apply a dual of boundary adjustment steps from the Connect2D algorithm to remove the redundant edges. We show that the resulting algorithm SIG‐Connect2D yields the best reconstruction accuracy compared to state‐of‐the‐art algorithms from a recent comprehensive benchmark, and the method offers the potential for further improvements, e.g., for surface reconstruction.

Abstract Curve reconstruction from unstructured points in a plane is a fundamental problem with many applications that has generated research interest for decades. Involved aspects like handling open, sharp, multiple and non‐manifold outlines, run‐time and provability as well as potential extension to 3D for surface reconstruction have led to many different algorithms. We survey the literature on 2D curve reconstruction and then present an open‐sourced benchmark for the experimental study. Our unprecedented evaluation of a selected set of planar curve reconstruction algorithms aims to give an overview of both quantitative analysis and qualitative aspects for helping users to select the right algorithm for specific problems in the field. Our benchmark framework is available online to permit reproducing the results and easy integration of new algorithms.

Abstract Large-scale unstructured point cloud scenes can be quickly visualized without prior reconstruction by utilizing levels-of-detail structures to load an appropriate subset from out-of-core storage for rendering the current view. However, as soon as we need structures within the point cloud, e.g., for interactions between objects, the construction of state-of-the-art data structures requires O(NlogN) time for N points, which is not feasible in real time for millions of points that are possibly updated in each frame. Therefore, we propose to use a surface representation structure which trades off the (here negligible) disadvantage of single-frame use for both output-dominated and near-linear construction time in practice, exploiting the inherent 2D property of sampled surfaces in 3D. This structure tightly encompasses the assumed surface of unstructured points in a set of bounding depth intervals for each cell of a discrete 2D grid. The sorted depth samples in the structure permit fast surface queries, and on top of that an occlusion graph for the scene comes almost for free. This graph enables novel real-time user operations such as revealing partially occluded objects, or scrolling through layers of occluding objects, e.g., walls in a building. As an example application we showcase a 3D scene exploration framework that enables fast, more sophisticated interactions with point clouds rendered in real time.

Abstract We propose an efficient out‐of‐core octree generation method for arbitrarily large point clouds. It utilizes a hierarchical counting sort to quickly split the point cloud into small chunks, which are then processed in parallel. Levels of detail are generated by subsampling the full data set bottom up using one of multiple exchangeable sampling strategies. We introduce a fast hierarchical approximate blue‐noise strategy and compare it to a uniform random sampling strategy. The throughput, including out‐of‐core access to disk, generating the octree, and writing the final result to disk, is about an order of magnitude faster than the state of the art, and reaches up to around 6 million points per second for the blue‐noise approach and up to around 9 million points per second for the uniform random approach on modern SSDs.

Abstract We propose a parameter‐free method to recover manifold connectivity in unstructured 2D point clouds with high noise in terms of the local feature size. This enables us to capture the features which emerge out of the noise. To achieve this, we extend the reconstruction algorithm HNN‐Crust, which connects samples to two (noise‐free) neighbours and has been proven to output a manifold for a relaxed sampling condition. Applying this condition to noisy samples by projecting their k‐nearest neighbourhoods onto local circular fits leads to multiple candidate neighbour pairs and thus makes connecting them consistently an NP‐hard problem. To solve this efficiently, we design an algorithm that searches that solution space iteratively on different scales of k. It achieves linear time complexity in terms of point count plus quadratic time in the size of noise clusters. Our algorithm FitConnect extends HNN‐Crust seamlessly to connect both samples with and without noise, performs as local as the recovered features and can output multiple open or closed piecewise curves. Incidentally, our method simplifies the output geometry by eliminating all but a representative point from noisy clusters. Since local neighbourhood fits overlap consistently, the resulting connectivity represents an ordering of the samples along a manifold. This permits us to simply blend the local fits for denoising with the locally estimated noise extent. Aside from applications like reconstructing silhouettes of noisy sensed data, this lays important groundwork to improve surface reconstruction in 3D. Our open‐source algorithm is available online.

Abstract We consider the problem of sampling points from a collection of smooth curves in the plane, such that the Crust family of proximity‐based reconstruction algorithms can rebuild the curves. Reconstruction requires a dense sampling of local features, i.e., parts of the curve that are close in Euclidean distance but far apart geodesically. We show that ε < 0.47‐sampling is sufficient for our proposed HNN‐Crust variant, improving upon the state‐of‐the‐art requirement of ε < ‐sampling. Thus we may reconstruct curves with many fewer samples. We also present a new sampling scheme that reduces the required density even further than ε < 0.47‐sampling. We achieve this by better controlling the spacing between geodesically consecutive points. Our novel sampling condition is based on the reach, the minimum local feature size along intervals between samples. This is mathematically closer to the reconstruction density requirements, particularly near sharp‐angled features. We prove lower and upper bounds on reach ρ‐sampling density in terms of lfs ε‐sampling and demonstrate that we typically reduce the required number of samples for reconstruction by more than half.

Abstract We present anefficient algorithm for determining an aesthetically pleasing shape boundary connecting all the points in a given unorganized set of 2D points, with no other information than point coordinates. By posing shape construction as a minimisation problem which follows the Gestalt laws, our desired shape is non‐intersecting, interpolates all points and minimizes a criterion related to these laws. The basis for our algorithm is an initial graph, an extension of the Euclidean minimum spanning tree but with no leaf nodes, called as the minimum boundary complex . and can be expressed similarly by parametrizing a topological constraint. A close approximation of , termed can be computed fast using a greedy algorithm. is then transformed into a closed interpolating boundary in two steps to satisfy ’s topological and minimization requirements. Computing exactly is an NP (Non‐Polynomial)‐hard problem, whereas is computed in linearithmic time. We present many examples showing considerable improvement over previous techniques, especially for shapes with sharp corners. Source code is available online.