The latest advancements in Virtual Reality (VR) enable the creation of 3D models within a holographic immersive simulation environment. In this article, we create QuickCSGModeling , a user-friendly mid-air interactive modeling system. We first prepare a dataset consisting of diverse components and precompute the discrete signed distance function (SDF) for each component. During the modeling phase, users can freely design complicated shapes with a pair of VR controllers. Based on the discrete SDF representation, any CSG-like operation (union, intersection, and subtraction) can be performed voxel-wisely. Also, we maintain a single dynamic SDF for the whole scene, whose zero-level set surface exactly encodes the most recent constructed shape. Both SDF fusion and surface extraction are implemented via GPU for a smooth user experience. A total of 34 volunteers were asked to create their favorite models using QuickCSGModeling. With a simple training, most of them can create a fascinating shape or even a descriptive scene quickly. We also discuss how to extend our system to create articulated models with hinges, where an adaptive cube subdivision has to be enforced to improve the reconstruction accuracy around the hinge part, followed by a Dual Contouring-based surface extraction. 1

Given a set of generators, the geodesic Voronoi diagram (GVD) defines how the base surface is decomposed into separate regions such that each generator dominates a region in terms of geodesic distance to the generators. Generally speaking, each ordinary bisector point of the GVD is determined by two adjacent generators while each branching point of the GVD is given by at least three generators. When there are sufficiently many generators, straight-line distance serves as an effective alternative of geodesic distance for computing GVDs. However, for a set of sparse generators, one has to use exact or approximate geodesic distance instead, which requires a high computational cost to trace the bisectors and the branching points. We observe that it is easier to infer the branching points by stretching the ordinary segments than competing between wavefronts from different directions. Based on the observation, we develop an unfolding technique to compute the ordinary points of the GVD, as well as a growth-based technique to stretch the traced bisector segments such that they finally grow into a complete GVD. Experimental results show that our algorithm runs 3 times as fast as the state-of-the-art method at the same accuracy level.

Geodesics measure the shortest distance (either locally or globally) between two points on a curved surface and serve as a fundamental tool in digital geometry processing. Suppose that we have a parameterized path$\gamma (t)=\mathbf {x}(u(t),v(t))$on a surface$\mathbf {x}=\mathbf {x}(u,v)$with$\gamma (0)=p$and$\gamma (1)=q$. We formulate the two-point geodesic problem into a minimization problem$\int _0^1 H(\Vert \mathbf {x}_uu^{\prime }(t)+\mathbf {x}_vv^{\prime }(t)\Vert)\text{d}t$, where$H(s)$satisfies$H(0)=0,H^{\prime }(s)>0$and$H^{\prime \prime }(s)\geq 0$for$s>0$. In our implementation, we choose$H(s)=e^{s^2}-1$and show that it has several unique advantages over other choices such as$H(s)=s^2$and$H(s)=s$. It is also a minimizer of the traditional geodesic length variational and able to guarantee the uniqueness and regularity in terms of curve parameterization. In the discrete setting, we construct the initial path by a sequence of moveable points$\lbrace x_i\rbrace _{i=1}^n$and minimize$\sum _{i=1}^{n} H(\Vert x_i - x_{i+1}\Vert)$. The resulting points are evenly spaced along the path. It’s obvious that our algorithm can deal with parametric surfaces. Considering that meshes, point clouds and implicit surfaces can be transformed into a signed distance function (SDF), we also discuss its implementation on a general SDF. Finally, we show that our method can be extended to solve a general least-cost path problem. We validate the proposed algorithm in terms of accuracy, performance and scalability, and demonstrate the advantages by extensive comparisons.

Motivated by the fact that the medial axis transform is able to encode the shape completely, we propose to use as few medial balls as possible to approximate the original enclosed volume by the boundary surface. We progressively select new medial balls, in a top-down style, to enlarge the region spanned by the existing medial balls. The key spirit of the selection strategy is to encourage large medial balls while imposing given geometric constraints. We further propose a speedup technique based on a provable observation that the intersection of medial balls implies the adjacency of power cells (in the sense of the power crust).We further elaborate the selection rules in combination with two closely related applications. One application is to develop an easy-to-use ball-stick modeling system that helps non-professional users to quickly build a shape with only balls and wires, but any penetration between two medial balls must be suppressed. The other application is to generate porous structures with convex, compact (with a high isoperimetric quotient) and shape-aware pores where two adjacent spherical pores may have penetration as long as the mechanical rigidity can be well preserved.

Abstract Apollonius diagrams, also known as additively weighted Voronoi diagrams, are an extension of Voronoi diagrams, where the weighted distance is defined by the Euclidean distance minus the weight. The bisectors of Apollonius diagrams have a hyperbolic form, which is fundamentally different from traditional Voronoi diagrams and power diagrams. Though robust solvers are available for computing 2D Apollonius diagrams, there is no practical approach for the 3D counterpart. In this paper, we systematically analyze the structural features of 3D Apollonius diagrams, and then develop a fast algorithm for robustly computing Apollonius diagrams in 3D. Our algorithm consists of vertex location, edge tracing and face extraction, among which the key step is to adaptively subdivide the initial large box into a set of sufficiently small boxes such that each box contains at most one Apollonius vertex. Finally, we use centroidal Voronoi tessellation (CVT) to discretize the curved bisectors with well‐tessellated triangle meshes. We validate the effectiveness and robustness of our algorithm through extensive evaluation and experiments. We also demonstrate an application on computing centroidal Apollonius diagram.