Rigid registration of 3D point clouds is a fundamental process in computer graphics, computer vision and robotics. A widely used approach for registering two point clouds is the Iterative Corresponding Point (ICP). Over the years, ICP algorithms have been intensively studied for improving their robustness and versatility. With modern acquisition devices, it becomes common to acquire geometries with fast motion while most of the acquisition systems rely on a rolling shutters technology: within a frame, acquisition is performed at different times for each location. In case of fast motion or relatively-low frame-rate, this leads to motion distortions that are not directly handled by classical frame-to-frame registration. Our contribution is a new formulation of the ICP, denoted General Temporal Iterative Closest Point ( GT-ICP ), that simultaneously solves the registration and the motion compensation problems between successive LiDAR frames. In contrast to previous work, we explicitly take into account the acquisition time of each individual point in the ICP frame-to-frame optimization. We demonstrate and compare our reformulation on several variants of the ICP algorithm and motion distortion correction techniques, applied both on simulated and acquired data.

Automatic layout optimisation allows users to arrange augmented reality content in the real-world environment without the need for tedious manual interactions. This optimisation is often based on modelling the intended content placement as constraints, defined as cost functions. Then, applying a cost minimization algorithm leads to a desirable placement. However, such an approach is limited by the lack of user control over the optimisation results. In this paper we explore the concept of user-driven constraints for augmented reality layout optimisation. With our approach users can define and set up their own constraints directly within the real-world environment. We first present a design space composed of three dimensions: the constraints, the regions of interest and the constraint parameters. Then we explore which input gestures can be employed to define the user-driven constraints of our design space through a user elicitation study. Using the results of the study, we propose a holistic system design and implementation demonstrating our user-driven constraints, which we evaluate in a final user study where participants had to create several constraints at the same time to arrange a set of virtual contents.

In the past decades, Monte Carlo methods have shown their ability to solve PDEs, independently of the dimensionality of the integration domain and for different use-cases (e.g. light transport, geometry processing, physics simulation). Specifically, the path-space formulation of transport equations is a key ingredient to define tractable and scalable solvers, and we observe nowadays a strong interest in the definition of simulation systems based on Monte Carlo algorithms. We also observe that, when simulating combined physics (e.g. thermal rendering from a heat transfer simulation), there is a lack of coupled Monte Carlo algorithms allowing to solve all the physics at once, in the same path space, rather than combining several independent MC estimators, a combination that would make the global solver critically sensitive to the complexity of each simulation space. This brings to our proposal: a coupled, single path-space, Monte Carlo algorithm for efficient multi-physics problems solving. In this work, we combine our understanding and knowledge of Physics and Computer Graphics to demonstrate how to formulate and arrange different simulation spaces into a single path space. We define a tractable formalism for coupled heat transfer simulation using Monte Carlo, and we leverage the path-space construction to interactively compute multiple simulations with different conditions in the same scene, in terms of boundary conditions and observation time. We validate our proposal in the context of infrared rendering with different thermal simulation scenarios: e.g., room temperature simulation, visualization of heat paths within materials (detection of thermal bridges), heat diffusion capacity of thermal exchanger. We expect that our theoretical framework will foster collaboration and multidisciplinary studies. The perspectives this framework opens are detailed and we suggest a research agenda towards the resolution of coupled PDEs at the interface of Physics and Computer Graphics.

Abstract When rendering images using Spherical Harmonics (SH), the projection of a spherical function on the SH basis remains a computational challenge both for high‐frequency functions and for emission functions from complex light sources. Recent works investigate efficient SH projection of the light field coming from polygonal and spherical lights. To further reduce the rendering time, instead of computing the SH coefficients at each vertex of a mesh or at each fragment on an image, it has been shown, for polygonal area light, that computing both the SH coefficients and their spatial gradients on a grid covering the scene allows the efficient and accurate interpolation of these coefficients at each shaded point. In this paper, we develop analytical recursive formulae to compute the spatial gradients of SH coefficients for spherical light. This requires the efficient computation of the spatial gradients of the SH basis function that we also derive. Compared to existing method for polygonal light, our method is faster, requires less memory and scales better with respect to the SH band limit. We also show how to approximate polygonal lights using spherical lights to benefit from our derivations. To demonstrate the effectiveness of our proposal, we integrate our algorithm in a shading system able to render fully dynamic scenes with several hundreds of spherical lights in real time.

In recent years, Convolutional Neural Networks (CNN) have proven to be efficient analysis tools for processing point clouds, e.g., for reconstruction, segmentation, and classification. In this article, we focus on the classification of edges in point clouds, where both edges and their surrounding are described. We propose a new parameterization adding to each point a set of differential information on its surrounding shape reconstructed at different scales. These parameters, stored in a Scale-Space Matrix (SSM) , provide a well-suited information from which an adequate neural network can learn the description of edges and use it to efficiently detect them in acquired point clouds. After successfully applying a multi-scale CNN on SSMs for the efficient classification of edges and their neighborhood, we propose a new lightweight neural network architecture outperforming the CNN in learning time, processing time, and classification capabilities. Our architecture is compact, requires small learning sets, is very fast to train, and classifies millions of points in seconds.

Abstract Point clouds are now ubiquitous in computer graphics and computer vision. Differential properties of the point‐sampled surface, such as principal curvatures, are important to estimate in order to locally characterize the scanned shape. To approximate the surface from unstructured points equipped with normal vectors, we rely on the Algebraic Point Set Surfaces (APSS) [GG07] for which we provide convergence and stability proofs for the mean curvature estimator. Using an integral invariant viewpoint, this first contribution links the algebraic sphere regression involved in the APSS algorithm to several surface derivatives of different orders. As a second contribution, we propose an analytic method to compute the shape operator and its principal curvatures from the fitted algebraic sphere. We compare our method to the state‐of‐the‐art with several convergence and robustness tests performed on a synthetic sampled surface. Experiments show that our curvature estimations are more accurate and stable while being faster to compute compared to previous methods. Our differential estimators are easy to implement with little memory footprint and only require a unique range neighbors query per estimation. Its highly parallelizable nature makes it appropriate for processing large acquired data, as we show in several real‐world experiments.

Pervasive interfaces can present relevant information anywhere in our environment, and they are thus challenged by the non rectilinearity of the display surface (e.g. circular table) and by the presence of objects that can partially occlude the interface (e.g. a book or cup on the table). To tackle this problem, we propose a novel solution based on two core contributions: the decomposition of the interface into deformable graphical units, called Dynamic Decals, and the control of their position and behaviour by a constraint-based approach. Our approach dynamically deforms the interface when needed while minimizing the impact on its visibility and layout properties. To do so, we extend previous work on implicit deformations to propose and experimentally validate functions defining different decal shapes and new deformers modeling decal deformations when they collide. Then, we interactively optimize the decal placements according to the interface geometry and their interrelations. Relations are modeled as constraints and the interface evolution results from an easy and efficient to solve minimization problem. Our approach is validated by a user study showing that, compared to two baselines, Dynamic decals is an aesthetically pleasant interface that preserves visibility, layout and aesthetic properties.

The 3-D information collected from sample plots is significant for forest inventories. Terrestrial laser scanning (TLS) has been demonstrated to be an effective device in data acquisition of forest plots. Although TLS is able to achieve precise measurements, multiple scans are usually necessary to collect more detailed data, which generally requires more time in scan preparation and field data acquisition. In contrast, mobile laser scanning (MLS) is being increasingly utilized in mapping due to its mobility. However, the geometrical peculiarity of forests introduces challenges. In this article, a test backpack-based MLS system, i.e., backpack laser scanning (BLS), is designed for forest plot mapping without a global navigation satellite system/inertial measurement unit (GNSS-IMU) system. To achieve accurate matching, this article proposes to combine the line and point features for calculating transformation, in which the line feature is derived from trunk skeletons. Then, a scan-to-map matching strategy is proposed for correcting positional drift. Finally, this article evaluates the effectiveness and the mapping accuracy of the proposed method in forest sample plots. The experimental results indicate that the proposed method achieves accurate forest plot mapping using the BLS; meanwhile, compared to the existing methods, the proposed method utilizes the geometric attributes of the trees and reaches a lower mapping error, in which the mean errors and the root square mean errors for the horizontal/vertical direction in plots are less than 3 cm.

Abstract Modern acquisition techniques generate detailed point clouds that sample complex geometries. For instance, we are able to produce millimeter‐scale acquisition of whole buildings. Processing and exploring geometrical information within such point clouds requires scalability, robustness to acquisition defects and the ability to model shapes at different scales. In this work, we propose a new representation that enriches point clouds with a multi‐scale planar structure graph. We define the graph nodes as regions computed with planar segmentations at increasing scales and the graph edges connect regions that are similar across scales. Connected components of the graph define the planar structures present in the point cloud within a scale interval. For instance, with this information, any point is associated to one or several planar structures existing at different scales. We then use topological data analysis to filter the graph and provide the most prominent planar structures. Our representation naturally encodes a large range of information. We show how to efficiently extract geometrical details (e.g. tiles of a roof), arrangements of simple shapes (e.g. steps and mean ramp of a staircase), and large‐scale planar proxies (e.g. walls of a building) and present several interactive tools to visualize, select and reconstruct planar primitives directly from raw point clouds. The effectiveness of our approach is demonstrated by an extensive evaluation on a variety of input data, as well as by comparing against state‐of‐the‐art techniques and by showing applications to polygonal mesh reconstruction.

Being able to duplicate published research results is an important process of conducting research whether to build upon these findings or to compare with them. This process is called "replicability" when using the original authors' artifacts (e.g., code), or "reproducibility" otherwise (e.g., re-implementing algorithms). Reproducibility and replicability of research results have gained a lot of interest recently with assessment studies being led in various fields, and they are often seen as a trigger for better result diffusion and transparency. In this work, we assess replicability in Computer Graphics, by evaluating whether the code is available and whether it works properly. As a proxy for this field we compiled, ran and analyzed 151 codes out of 374 papers from 2014, 2016 and 2018 SIGGRAPH conferences. This analysis shows a clear increase in the number of papers with available and operational research codes with a dependency on the subfields, and indicates a correlation between code replicability and citation count. We further provide an interactive tool to explore our results and evaluation data.

Color palettes are widely used by artists to define colors of artworks and explore color designs. In general, artists select the colors of a palette by following a set of rules, e.g. contrast or relative luminance. Existing interactive palette exploration tools explore palette spaces following limited constraints defined as geometric configurations in color space e.g. harmony rules on the color wheel. Palette search algorithms sample palettes from color relations learned from an input dataset, however they cannot provide interactive user edits and palette refinement. We introduce in this work a new versatile formulation enabling the creation of constraint-based interactive palette exploration systems. Our technical contribution is a graph-based palette representation, from which we define palette exploration as a minimization problem that can be solved efficiently and provide real-time feedback. Based on our formulation, we introduce two interactive palette exploration strategies: constrained palette exploration, and for the first time, constrained palette interpolation. We demonstrate the performances of our approach on various application cases and evaluate how it helps users finding trade-offs between concurrent constraints.

The advent of low cost scanning devices and the improvement of multi-view stereo techniques have made the acquisition of 3D geometry ubiquitous. Data gathered from different devices, however, result in large variations in detail, scale, and coverage. Registration of such data is essential before visualizing, comparing and archiving them. However, state-of-the-art methods for geometry registration cannot be directly applied due to intrinsic differences between the models, e.g., sampling, scale, noise. In this paper we present a method for the automatic registration of multi-modal geometric data, i.e., acquired by devices with different properties (e.g., resolution, noise, data scaling). The method uses a descriptor based on Growing Least Squares, and is robust to noise, variation in sampling density, details, and enables scale-invariant matching. It allows not only the measurement of the similarity between the geometry surrounding two points, but also the estimation of their relative scale. As it is computed locally, it can be used to analyze large point clouds composed of millions of points. We implemented our approach in two registration procedures (assisted and automatic) and applied them successfully on a number of synthetic and real cases. We show that using our method, multi-modal models can be automatically registered, regardless of their differences in noise, detail, scale, and unknown relative coverage.

With the proliferation of acquisition devices, gathering massive volumes of 3D data is now easy. Processing such large masses of pointclouds, however, remains a challenge. This is particularly a problem for raw scans with missing data, noise, and varying sampling density. In this work, we present a simple, scalable, yet powerful data reconstruction algorithm. We focus on reconstruction of man-made scenes as regular arrangements of planes (RAP), thereby selecting both local plane-based approximations along with their global inter-plane relations. We propose a novel selection formulation to directly balance between data fitting and the simplicity of the resulting arrangement of extracted planes. The main technical contribution is a formulation that allows less-dominant orientations to still retain their internal regularity, and not become overwhelmed and regularized by the dominant scene orientations. We evaluate our approach on a variety of complex 2D and 3D pointclouds, and demonstrate the advantages over existing alternative methods.

Abstract Data acquisition in large‐scale scenes regularly involves accumulating information across multiple scans. A common approach is to locally align scan pairs using Iterative Closest Point (ICP) algorithm (or its variants), but requires static scenes and small motion between scan pairs. This prevents accumulating data across multiple scan sessions and/or different acquisition modalities (e.g., stereo, depth scans). Alternatively, one can use a global registration algorithm allowing scans to be in arbitrary initial poses. The state‐of‐the‐art global registration algorithm, 4PCS, however has a quadratic time complexity in the number of data points. This vastly limits its applicability to acquisition of large environments. We present S uper 4PCS for global pointcloud registration that is optimal, i.e., runs in linear time (in the number of data points) and is also output sensitive in the complexity of the alignment problem based on the (unknown) overlap across scan pairs. Technically, we map the algorithm as an ‘instance problem’ and solve it efficiently using a smart indexing data organization. The algorithm is simple, memory‐efficient, and fast. We demonstrate that S uper 4PCS results in significant speedup over alternative approaches and allows unstructured efficient acquisition of scenes at scales previously not possible. Complete source code and datasets are available for research use at http://geometry.cs.ucl.ac.uk/projects/2014/super4PCS/ .

Abstract This paper presents a tool that enables the direct editing of surface features in large point‐clouds or meshes. This is made possible by a novel multi‐scale analysis of unstructured point‐clouds that automatically extracts the number of relevant features together with their respective scale all over the surface. Then, combining this ingredient with an adequate multi‐scale decomposition allows us to directly enhance or reduce each feature in an independent manner. Our feature extraction is based on the analysis of the scale‐variations of locally fitted surface primitives combined with unsupervised learning techniques. Our tool may be applied either globally or locally, and millions of points are handled in real‐time. The resulting system enables users to accurately edit complex geometries with minimal interaction.

Abstract We present a novel approach to the multi‐scale analysis of point‐sampled manifolds of co‐dimension 1. It is based on a variant of Moving Least Squares, whereby the evolution of a geometric descriptor at increasing scales is used to locate pertinent locations in scale‐space, hence the name “Growing Least Squares”. Compared to existing scale‐space analysis methods, our approach is the first to provide acontinuoussolution in space and scale dimensions, without requiring any parametrization, connectivity or uniform sampling. An important implication is that we identifymultiple pertinentscales for any point on a manifold, a property that had not yet been demonstrated in the literature. In practice, our approach exhibits an improved robustness to change of input, and is easily implemented in a parallel fashion on the GPU. We compare our method to state‐of‐the‐art scale‐space analysis techniques and illustrate its practical relevance in a few application scenarios.