Search

The computation of power diagrams (or weighted Voronoi diagrams) is a fundamental task in computational geometry and computer graphics. To accomplish the computation, we provide a different way from the existing ones for lifting the weighted seeds to a set of points in the space of one dimension higher, then the power cells can be directly obtained by computing the intersections of the Voronoi cells of these lifting points and the original space. This property enables us to apply the method based on the k -nearest neighbors query to the generation of power diagrams. Each power cell is obtained by sequentially clipping the input domain using the bisectors between its seed and the k -nearest neighbors. Experimental results demonstrate that our method outperforms the state-of-the-art one based on regular triangulation in terms of efficiency for general cases in the 2D and 3D spaces. [Display omitted] • We provide a variant for lifting the weighted seeds to higher dimensional points. • We propose an efficient method for power diagram computation based on the kNN query. [ABSTRACT FROM AUTHOR]

Abstract: Recently, a new bivariate simplex spline scheme based on Delaunay configuration has been introduced into the geometric computing community, and it defines a complete spline space that retains many attractive theoretic and computational properties. In this paper, we develop a novel shape modeling framework to reconstruct a closed surface of arbitrary topology based on this new spline scheme. Our framework takes a triangulated set of points, and by solving a linear least-square problem and iteratively refining parameter domains with newly added knots, we can finally obtain a continuous spline surface satisfying the requirement of a user-specified error tolerance. Unlike existing surface reconstruction methods based on triangular B-splines (or DMS splines), in which auxiliary knots must be explicitly added in advance to form a knot sequence for construction of each basis function, our new algorithm completely avoids this less-intuitive and labor-intensive knot generating procedure. We demonstrate the efficacy and effectiveness of our algorithm on real-world, scattered datasets for shape representation and computing. [Copyright &y& Elsevier]

This paper focuses on the problem of generating a line drawing from a given image for fused deposition modeling. The abstracted line drawing, comprising of lines with a single color and thickness, would preserve both tone and edges of the input image. We first partition the image into sub-regions manually. The boundaries of the sub-regions are extracted as the feature lines of the image. Next, a proper number of points are randomly placed on the image plane with a density proportional to the darkness of the image. We use Lloyd’s method to push the sampling points away from each other and the feature lines. The points within each sub-region are then connected by solving a travelling salesman problem (TSP). Finally, we further optimize the fairness and the spacing of the lines by minimizing a tailored objective function. A variety of experimental results are presented to show the effectiveness of our method for generating line drawings for 3D printing. [ABSTRACT FROM AUTHOR]