Variational blue noise sampling

Isotropic Surface Remeshing without Large and Small Angles

We introduce a novel algorithm for isotropic surface remeshing which progressively eliminates obtuse triangles and improves small angles. The main novelty of the proposed approach is a simple vertex insertion scheme that facilitates the removal of large angles, and a vertex removal operation that improves the distribution of small angles. In combination with other standard local mesh operators, e.g., connectivity optimization and local tangential smoothing, our algorithm is able to remesh efficiently a low-quality mesh surface. Our approach can be applied directly or used as a post-processing step following other remeshing approaches. Our method has a similar computational efficiency to the fastest approach available, i.e., real-time adaptive remeshing [1]. In comparison with state-of-the-art approaches, our method consistently generates better results based on evaluations using different metrics.

A Density-Driven Method for the Placement of Biological Cells Over Two-Dimensional Manifolds

We introduce a graphical method originating from the computer graphics domain that is used for the arbitrary placement of cells over a two-dimensional manifold. Using a bitmap image whose luminance provides cell density, this method guarantees a discrete distribution of the positions of the cells respecting the local density. This method scales to any number of cells, allows one to specify arbitrary enclosing shapes and provides a scalable and versatile alternative to the more classical assumption of a uniform spatial distribution. The method is illustrated on a discrete homogeneous neural field, on the distribution of cones and rods in the retina and on the neural density of a flattened piece of cortex.

A Simple Push-Pull Algorithm for Blue-Noise Sampling

We describe a simple push-pull optimization (PPO) algorithm for blue-noise sampling by enforcing spatial constraints on given point sets. Constraints can be a minimum distance between samples, a maximum distance between an arbitrary point and the nearest sample, and a maximum deviation of a sample's capacity (area of Voronoi cell) from the mean capacity. All of these constraints are based on the topology emerging from Delaunay triangulation, and they can be combined for improved sampling quality and efficiency. In addition, our algorithm offers flexibility for trading-off between different targets, such as noise and aliasing. We present several applications of the proposed algorithm, including anti-aliasing, stippling, and non-obtuse remeshing. Our experimental results illustrate the efficiency and the robustness of the proposed approach. Moreover, we demonstrate that our remeshing quality is superior to the current state-of-the-art approaches.

Non-Obtuse Remeshing with Centroidal Voronoi Tessellation

We present a novel remeshing algorithm that avoids triangles with small (acute) angles and those with large (obtuse) angles. Our solution is based on an extension of Centroidal Voronoi Tesselation (CVT). We augment the original CVT formulation with a penalty term that penalizes short Voronoi edges, while the CVT term helps to avoid small angles. Our results show significant improvements in remeshing quality over the state of the art.

Surface Mosaic Synthesis with Irregular Tiles

Mosaics are widely used for surface decoration to produce appealing visual effects. We present a method for synthesizing digital surface mosaics with irregularly shaped tiles, which are a type of tiles often used for mosaics design. Our method employs both continuous optimization and combinatorial optimization to improve tile arrangement. In the continuous optimization step, we iteratively partition the base surface into approximate Voronoi regions of the tiles and optimize the positions and orientations of the tiles to achieve a tight fit. Combination optimization performs tile permutation and replacement to further increase surface coverage and diversify tile selection. The alternative applications of these two optimization steps lead to rich combination of tiles and high surface coverage. We demonstrate the effectiveness of our solution with extensive experiments and comparisons.

Unbiased Sampling and Meshing of Isosurfaces

In this paper, we present a new technique to generate unbiased samples on isosurfaces. An isosurface, F(x; y; z) = c, of a function, F, is implicitly defined by trilinear interpolation of background grid points. The key idea of our approach is that of treating the isosurface within a grid cell as a graph (height) function in one of the three coordinate axis directions, restricted to where the slope is not too high, and integrating / sampling from each of these three. We use this unbiased sampling algorithm for applications in Monte Carlo integration, Poisson-disk sampling, and isosurface meshing.

Low-Resolution Remeshing Using the Localized Restricted Voronoi Diagram

A big problem in triangular remeshing is to generate meshes when the triangle size approaches the feature size in the mesh. The main obstacle for Centroidal Voronoi Tessellation (CVT)-based remeshing is to compute a suitable Voronoi diagram. In this paper, we introduce the localized restricted Voronoi diagram (LRVD) on mesh surfaces. The LRVD is an extension of the restricted Voronoi diagram (RVD), but it addresses the problem that the RVD can contain Voronoi regions that consist of multiple disjoint surface patches. Our definition ensures that each Voronoi cell in the LRVD is a single connected region. We show that the LRVD is a useful extension to improve several existing mesh-processing techniques, most importantly surface remeshing with a low number of vertices. While the LRVD and RVD are identical in most simple configurations, the LRVD is essential when sampling a mesh with a small number of points and for sampling surface areas that are in close proximity to other surface areas, e.g., nearby sheets. To compute the LRVD, we combine local discrete clustering with a global exact computation.

An intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces

Poisson disk sampling has excellent spatial and spectral properties, and plays an important role in a variety of visual computing. Although many promising algorithms have been proposed for multidimensional sampling in euclidean space, very few studies have been reported with regard to the problem of generating Poisson disks on surfaces due to the complicated nature of the surface. This paper presents an intrinsic algorithm for parallel Poisson disk sampling on arbitrary surfaces. In sharp contrast to the conventional parallel approaches, our method neither partitions the given surface into small patches nor uses any spatial data structure to maintain the voids in the sampling domain. Instead, our approach assigns each sample candidate a random and unique priority that is unbiased with regard to the distribution. Hence, multiple threads can process the candidates simultaneously and resolve conflicts by checking the given priority values. Our algorithm guarantees that the generated Poisson disks are uniformly and randomly distributed without bias. It is worth noting that our method is intrinsic and independent of the embedding space. This intrinsic feature allows us to generate Poisson disk patterns on arbitrary surfaces in IR(n). To our knowledge, this is the first intrinsic, parallel, and accurate algorithm for surface Poisson disk sampling. Furthermore, by manipulating the spatially varying density function, we can obtain adaptive sampling easily.