We consider the problem of 3D shape recovery from ultra-fast motion-blurred images. While 3D reconstruction from static images has been extensively studied, recovering geometry from extreme motion-blurred images remains challenging. Such scenarios frequently occur in both natural and industrial settings, such as fast-moving objects in sports (e.g., balls) or rotating machinery, where rapid motion distorts object appearance and makes traditional 3D reconstruction techniques like Multi-View Stereo (MVS) ineffective. In this paper, we propose a novel inverse rendering approach for shape recovery from ultra-fast motion-blurred images. While conventional rendering techniques typically synthesize blur by averaging across multiple frames, we identify a major computational bottleneck in the repeated computation of barycentric weights. To address this, we propose a fast barycentric coordinate solver, which significantly reduces computational overhead and achieves a speedup of up to$4.57 \times$, enabling efficient and photorealistic simulation of high-speed motion. Crucially, our method is fully differentiable, allowing gradients to propagate from rendered images to the underlying 3D shape, thereby facilitating shape recovery through inverse rendering. We validate our approach on two representative motion types: rapid translation and rotation. Experimental results demonstrate that our method enables efficient and realistic modeling of ultra-fast moving objects in the forward simulation. Moreover, it successfully recovers 3D shapes from 2D imagery of objects undergoing extreme translational and rotational motion, advancing the boundaries of vision-based 3D reconstruction.

Given a collection of points in $\mathbb {R}^{3}$R3, KD-Tree and R-Tree are well-known nearest neighbor search (NNS) algorithms that rely on spatial partitioning and indexing techniques. However, when the query point is far from the data points or the data points inherently represent a 2-manifold surface, their query performance may degrade. To address this, we propose a novel dynamic programming technique that precomputes a Directed Acyclic Graph (DAG) to encode the proximity structure between data points. More specifically, the DAG captures how the proximity structure evolves during the incremental construction of the Voronoi diagram of the data points. Experimental results demonstrate that our method achieves a speed increase of 1-10x. Furthermore, our algorithm demonstrates significant practical value in diverse applications. We validated its effectiveness through extensive testing in four key applications: Point-to-Mesh Distance Queries, Iterative Closest Point (ICP) Registration, Density Peak Clustering, and Point-to-Segments Distance Queries. A particularly notable feature of our approach is its unique ability to efficiently identify the nearest neighbor among the first $k$k points in the point cloud, a capability that enables substantial acceleration in low-dimensional applications like Density Peak Clustering. As a natural extension of our incremental construction process, our method can also be readily adapted for farthest-point sampling tasks. These experimental results across multiple domains underscore the broad applicability and practical importance of our approach.

3D shape segmentation is an essential task in computer graphics and is widely used in many applications. It plays a critical role in understanding the structure and semantics of 3D models. Traditional approaches to 3D shape segmentation primarily rely on geometric features to partition models into meaningful components. However, these methods often struggle when the geometric characteristics of different parts are similar, resulting in ambiguous segmentation outcomes. To address this fundamental limitation, we introduce a novel text-driven multi-modal framework that systematically integrates textual semantics with geometric analysis for enhanced 3D shape segmentation. Our approach leverages a pre-trained language model with prefix tuning to bridge the semantic granularity gap between part-level annotations and face-level segmentation, while a specialized mesh self-attention module captures contextual relationships among neighboring faces. We design an attention-based text-driven integration mechanism that dynamically weights multimodal features, complemented by a Laplace-Adaptive Attention Module (LAAM) that better handles the distributions of geometric features. Through contrastive learning, we align textual and geometric representations in a shared semantic space, enabling effective disambiguation of geometrically similar but semantically distinct parts. We also contribute the Fine-grained HumanBody benchmark for comprehensive evaluation. Extensive experiments on Princeton Segmentation Benchmark, COSEG, ShapeNetCore, and our proposed benchmark demonstrate that our method significantly outperforms existing approaches, achieving superior segmentation accuracy while effectively resolving geometric ambiguities through semantic understanding.

The medial axis, a lower-dimensional descriptor that captures the extrinsic structure of a shape, plays an important role in digital geometry processing. Despite its importance, computing the medial axis transform robustly from diverse inputs, especially point clouds with defects, remains a challenging problem. In this article, we propose a new implicit method that deviates from traditional explicit medial axis computation. Our key technical insight is that the difference between the signed distance field (SDF) and the medial field (MF) of a solid shape relates to the unsigned distance field (UDF) of the shape’s medial axis. This observation allows us to formulate medial axis extraction as an implicit reconstruction problem. By employing a modified double covering strategy, we recover the medial axis as the zero level-set of the UDF. Extensive experiments demonstrate that our method achieves higher accuracy and robustness in learning compact medial axis transforms from challenging meshes and point clouds, outperforming existing approaches.

The Medial Axis Transform (MAT) is a complete shape descriptor capable of reconstructing the geometry of the original domain. A high-quality MAT should not only facilitate high-fidelity reconstruction but also capture structural features—for instance, by aligning the MAT boundary with the locus of rolling ball centers within fillet regions. However, computing such an ideal MAT remains a significant challenge, particularly when the input is a discrete triangle mesh. In this paper, we follow the established technical pipeline of initializing the MAT via a 3D Voronoi diagram of surface samples and subsequently simplifying the Voronoi structure through a QEM-like scheme. Our key insight is to explicitly track the correspondence between MAT vertices and surface regions throughout the progressive simplification process, ensuring that the resulting MAT triangles accurately reflect the intrinsic symmetries between surface patches. We translate these geometric requirements into a suite of priority control strategies that govern the sequencing of edge collapses. Through extensive evaluation against state-of-the-art MAT algorithms, we validate the strong performance of our approach regarding runtime efficiency, structural alignment, boundary regularity, triangle quality, and robustness to noise. Our resulting MATs remain highly expressive for both articulated shapes and CAD models, even under extreme simplification—effectively capturing the global structure of complex geometries with only a few hundred vertices. Finally, we showcase the utility of our approach through two potential applications: capturing the locus of rolling ball centers within fillet regions, a structural capability not previously demonstrated in the existing literature, and surface extraction from unsigned distance fields, where the medial axis of the є -isosurface naturally yields a clean single-layer result. Source code is available at https://github.com/sssomeone/structural-mat.

k -nearest neighbor ( k -NN) search is a fundamental primitive in geometry processing and computer graphics. While spatial partitioning structures such as kd -trees are standard, they are often manifold-blind, failing to exploit the intrinsic low-dimensional structure of points sampled from 2-manifolds. Recent advances in dynamic programming-based nearest neighbor search (DP-NNS) leverage incrementally constructed Voronoi diagrams to accelerate queries, where each site p maintains a list of successors that progressively refine its Voronoi cell. However, DP-NNS is restricted to single nearest neighbor ( k = 1) searches, precluding their adoption in applications that require local neighborhood statistics. In this paper, we generalize the DP-NNS framework to support arbitrary k -NN queries for manifold-aligned data. Our approach is founded on the geometric observation that if p i is the nearest neighbor of a query q in P , then the second nearest neighbor of q must reside either within the prefix set P 1: i -1 = [ p 1 , ..., p i-1 } or within p i 's successor list. By recursively extending this principle, we introduce Manifold k -NN, a recursive algorithmic scheme that significantly outperforms conventional kd -trees for manifold-aligned data. Our method achieves a 1×-10× speedup in volume-to-surface query scenarios and inherently supports dynamic prefix queries—enabling k -NN searches within any subset P 1: m ( m ≤ n ) with zero overhead. Furthermore, we extend the framework to support point deletion via local Delaunay updates, providing a complete suite of dynamic operations for point set modification. Comprehensive experiments on diverse geometric datasets demonstrate the efficiency and broad applicability of our approach for modern graphics pipelines. Source code is available at https://github.com/sssomeone/manifold-knn.

Cages are fundamental structures in computer graphics, serving as versatile proxies for a wide range of applications. A high-quality cage must balance two competing objectives: minimizing the face count to ensure simplicity, and maximizing tightness to maintain high geometric fidelity to the input mesh. In this paper, we propose PR-Cage, a nested optimization framework for automated cage generation. For the outer control layer, we introduce a thickness parameter τ that defines a feasibility region; the evolving cage is guided by the τ -offset surface. We observe that an optimal balance between simplicity and tightness is achievable by progressively relaxing the parameter τ via a staircase schedule. For the inner iterations, we extend the traditional Quadric Error Metric (QEM) framework by incorporating rigorous linear inequality constraints to suppress triangle degeneration and prevent normal flips. Our algorithm relies exclusively on the atomic operations of edge collapses and edge flips, resulting in high computational efficiency and robustness. Comparative experiments on public datasets demonstrate that PR-Cage consistently outperforms existing methods, achieving extreme simplification while maintaining high adherence to the underlying geometry; see the teaser figure. Due to these favorable properties, we demonstrate the utility of our method in several downstream applications, such as contact simulation and deformation, where PR-Cage exhibits significant advantages in both quality and performance.

In this paper, we study an under-explored but important factor of diffusion generative models, i.e., the combinatorial complexity. Data samples are generally high-dimensional, and for various structured generation tasks, additional attributes are combined to associate with data samples. We show that the space spanned by the combination of dimensions and attributes can be insufficiently covered by existing training schemes of diffusion generative models, potentially limiting test time performance. We present a simple fix to this problem by constructing stochastic processes that fully exploit the combinatorial structures, hence the name ComboStoc. Using this simple strategy, we show that network training is significantly accelerated across diverse data modalities, including images and 3D structured shapes. Moreover, ComboStoc enables a new way of test time generation which uses asynchronous time steps for different dimensions and attributes, thus allowing for varying degrees of control over them. Our code is available at: https://github.com/Xrvitd/ComboStoc.

In recent years, encoding explicit mesh surfaces into compact neural representations has emerged as a prominent research direction. Compression ratio and representation accuracy present a fundamental trade-off for evaluating such algorithms. Traditional approaches typically decompose the input mesh into two components: a simplified base mesh and a neural displacement field. However, this paradigm faces inherent limitations. First, employing triangles or quadrilaterals as geometric primitives necessitates the explicit storage of vertex connectivity, incurring substantial memory overhead. Second, existing approaches typically treat base mesh generation as a decoupled preprocessing step, failing to fully leverage automatic differentiation frameworks to optimize the distribution of the base mesh. To address these issues, we propose RTF2Mesh, a method that achieves compact representation using only unstructured point clouds with feature vectors and network parameters. At its core, our approach leverages a meshless vertex-normal representation derived from the Restricted Tangent Face (RTF). Furthermore, we employ the Kolmogorov-Arnold Network (KAN) to encode both the displacement information and the normals of the vertex-normal representation. The KAN is chosen for its superior parameter efficiency compared to traditional Multi-Layer Perceptrons (MLPs). These two improvements enable RTF2Mesh to achieve a more compact neural representation while eliminating the need for explicit storage of vertex connectivity. During decoding, surface normals are reconstructed from the input point cloud using the KAN's learned weights to generate a base surface. The KAN-based network then predicts the displacements of the subdivided base surface, producing a high-resolution triangle mesh. Compared to current state-of-the-art (SOTA) methods, RTF2Mesh achieves highly competitive performance at equivalent compression rates.

Extracting high-fidelity mesh surfaces from Signed Distance Fields (SDFs) has become a fundamental operation in geometry processing. Despite significant progress over the past decades, key challenges remain-namely, how to automatically capture the intricate geometric and topological structures encoded in the zero level set of SDFs. In this paper, we present a novel isosurface extraction algorithm that introduces two key innovations: 1) An incrementally constructed power diagram through the addition of sample points, which enables repeated updates to the extracted surface via its dual-regular Delaunay tetrahedralization; and 2) An adaptive point insertion strategy that identifies regions exhibiting the greatest discrepancy between the current mesh and the underlying continuous surface. As Fig. 1 shows, our framework progressively refines the extracted mesh with minimal computational cost until it sufficiently approximates the underlying surface. Experimental results demonstrate that our approach outperforms state-of-the-art methods, particularly for models with intricate geometric variations and complex topologies.

Gaussian Splatting demonstrates impressive results in multi-view reconstruction based on Gaussian explicit representations. However, the current Gaussian primitives only have a single view-dependent color and an opacity to represent the appearance and geometry of the scene, resulting in a non-compact representation. In this paper, we introduce a new method called SVGS (Spatially Varying Gaussian Splatting) that utilizes spatially varying colors and opacity in a single Gaussian primitive to improve its representation ability. We have implemented bilinear interpolation, movable kernels, and tiny neural networks as spatially varying functions. SVGS employs 2D Gaussian surfels as primitives, which significantly enhances novel-view synthesis while maintaining high-quality geometric reconstruction. This approach is particularly effective in practical applications, as scenes combining complex textures with relatively simple geometry occur frequently in real-world environments. Quantitative and qualitative experimental results demonstrate that all three functions outperform the baseline, with the best movable kernels achieving superior novel view synthesis performance on multiple datasets, highlighting the strong potential of spatially varying functions.

Offset surfaces, defined as the Minkowski sum of a base surface and a rolling ball, play a crucial role in geometry processing, with applications ranging from coverage motion planning to brush modeling. While considerable progress has been made in computing constant-radius offset surfaces, computing variable-radius offset surfaces remains a challenging problem. In this paper, we present OffsetCrust, a novel framework that efficiently addresses the variable-radius offsetting problem by computing a power diagram. Let ${\mathcal {R}}$R denote the radius function defined on the base surface $\mathcal {S}$S. The power diagram is constructed from contributing sites, consisting of carefully sampled base points on $\mathcal {S}$S and their corresponding off-surface points, displaced along ${\mathcal {R}}$R-dependent directions. In the constant-radius case only, these displacement directions align exactly with the surface normals of $\mathcal {S}$S. Moreover, our method mitigates the misalignment issues commonly seen in crust-based approaches through a lightweight fine-tuning procedure. We validate the accuracy and efficiency of OffsetCrust through extensive experiments, and demonstrate its practical utility in applications such as reconstructing original boundary surfaces from medial axis transform (MAT) representations.

In redirected walking techniques, curvature gain and bending gain, which are referred to as curvature manipulation, are important redirection gains. The applied gains can differ when multiple paths are mapped, and sudden changes in gain may cause discomfort. This study proposes quadratic curvature manipulation (QCM) based on the habituation mechanism to effectively reduce discomfort. This method quadratically adjusts the path curvature, thereby reducing user's perception of curvature changes. Furthermore, we introduce the segmented curvature change (SCC) mode that combines QCM with linear curvature manipulation to facilitate more natural gain transitions, thereby reducing discomfort. Two experiments were conducted. Experiment 1 examined the relationship between QCM parameters and gains at which users felt discomfort. Experiment 2 further examined the effects of different curvature change modes on discomfort. The results indicate that using the SCC mode in curvature manipulations is more effective than other methods in reducing discomfort.

Abstract Point cloud denoising task aims to recover the clean point cloud from the scanned data coupled with different levels or patterns of noise. The recent state‐of‐the‐art methods often train deep neural networks to update the point locations towards the clean point cloud, and empirically repeat the denoising process several times in order to obtain the denoised results. It is not clear how to efficiently arrange the iterative denoising processes to deal with different levels or patterns of noise. In this paper, we propose an adaptive and iterative point cloud denoising method based on the score‐based diffusion model. For a given noisy point cloud, we first estimate the noise variation and determine an adaptive denoising schedule with appropriate step sizes, then invoke the trained network iteratively to update point clouds following the adaptive schedule. To facilitate this adaptive and iterative denoising process, we design the network architecture and a two‐stage sampling strategy for the network training to enable feature fusion and gradient fusion for iterative denoising. Compared to the state‐of‐the‐art point cloud denoising methods, our approach obtains clean and smooth denoised point clouds, while preserving the shape boundary and details better. Our results not only outperform the other methods both qualitatively and quantitatively, but also are preferable on the synthetic dataset with different patterns of noises, as well as the real‐scanned dataset.

Abstract Swept volume computation—the determination of regions occupied by moving objects—is essential in graphics, robotics, and manufacturing. Existing approaches either explicitly track surfaces, suffering from robustness issues under complex interactions, or employ implicit representations that trade off geometric fidelity and face optimization difficulties. We propose a novel inversion of motion perspective: rather than tracking object motion, we fix the object and trace spatial points backward in time, reducing complex trajectories to efficiently linearizable point motions. Based on this, we introduce a multi‐field tetrahedral framework that maintains multiple distance fileds per element, preserving fine geometric details at trajectory intersections where single‐field methods fail. Our method robustly computes swept volumes for diverse motions, including translations and screw motions, and enables practical applications in path planning and collision detection.

The rapid evolution of digital orthodontics has highlighted a critical need for automated treatment planning systems that balance computational efficiency with clinical reliability. However, existing methods still suffer from several limitations, including excessive clinician involvement (accounting for over 35% of treatment planning time), reliance on empirically defined key frames, and limited biomechanical plausibility, particularly in cases of severe dental crowding. This paper proposes a novel collision-free optimization framework to address these issues simultaneously. Our method defines a total movement energy function evaluated over each tooth’s pose at intermediate time frames. This energy is minimized iteratively using a steepest descent strategy. A rollback mechanism is employed: if inter-tooth penetration is detected during an update, the step size is halved repeatedly until collisions are eliminated. The framework allows flexible control over the number of intermediate frames to enforce a strict constraint on per-tooth displacement, limiting it to 0.2 mm translation or 2 ° rotation every 10 to 14 days. Clinical evaluations show that the proposed algorithm can generate desirable and clinically valid tooth movement plans, even in complex cases, while significantly reducing the need for manual intervention.

3D shape segmentation is a crucial task in the field of multimedia analysis and processing, and recent years have seen a surge in research on this topic. However, many existing methods only consider geometric features of 3D shapes and fail to explore the potential connections between faces, limiting their segmentation performance. In this paper, we propose a novel segmentation approach that mines and enhances the potential consistency of 3D shapes to overcome this limitation. The key idea is to mine the consistency between different partitions of 3D shapes and to use the unique consistency enhancement strategy to continuously optimize the consistency features for the network. Our method also includes a comprehensive set of network structures to mine and enhance consistent features, enabling more effective feature extraction and better utilization of contextual information around each face when processing complex shapes. We evaluate our approach on public benchmarks through extensive experiments and demonstrate its effectiveness in achieving higher accuracy than existing methods.

Quadrilateral mesh generation plays a crucial role in numerical simulations within Computer-Aided Design and Engineering (CAD/E). Producing high-quality quadrangulation typically requires satisfying four key criteria. First, the quadrilateral mesh should closely align with principal curvature directions. Second, singular points should be strategically placed and effectively minimized. Third, the mesh should accurately conform to sharp feature edges. Lastly, quadrangulation results should exhibit robustness against noise and minor geometric variations. Existing methods generally involve first computing a regular cross field to represent quad element orientations across the surface, followed by extracting a quadrilateral mesh aligned closely with this cross field. A primary challenge with this approach is balancing the smoothness of the cross field with its alignment to pre-computed principal curvature directions, which are sensitive to small surface perturbations and often ill-defined in spherical or planar regions. To tackle this challenge, we propose NeurCross , a novel framework that simultaneously optimizes a cross field and a neural signed distance function (SDF), whose zero-level set serves as a proxy of the input shape. Our joint optimization is guided by three factors: faithful approximation of the optimized SDF surface to the input surface, alignment between the cross field and the principal curvature field derived from the SDF surface, and smoothness of the cross field. Acting as an intermediary, the neural SDF contributes in two essential ways. First, it provides an alternative, optimizable base surface exhibiting more regular principal curvature directions for guiding the cross field. Second, we leverage the Hessian matrix of the neural SDF to implicitly enforce cross field alignment with principal curvature directions, thus eliminating the need for explicit curvature extraction. Extensive experiments demonstrate that NeurCross outperforms the state-of-the-art methods in terms of singular point placement, robustness against surface noise and surface undulations, and alignment with principal curvature directions and sharp feature curves.

Cross fields play a critical role in various geometry processing tasks, especially for quad mesh generation. Existing methods for cross field generation often struggle to balance computational efficiency with generation quality, using slow per-shape optimization. We introduce CrossGen , a novel framework that supports both feed-forward prediction and latent generative modeling of cross fields for quad meshing by unifying geometry and cross field representations within a joint latent space. Our method enables extremely fast computation of high-quality cross fields of general input shapes, typically within one second without per-shape optimization. Our method assumes a point-sampled surface, also called a point-cloud surface , as input, so we can accommodate various surface representations by a straightforward point sampling process. Using an auto-encoder network architecture, we encode input point-cloud surfaces into a sparse voxel grid with fine-grained latent spaces, which are decoded into both SDF-based surface geometry and cross fields (see the teaser figure). We also contribute a dataset of models with both high-quality signed distance fields (SDFs) representations and their corresponding cross fields, and use it to train our network. Once trained, the network is capable of computing a cross field of an input surface in a feed-forward manner, ensuring high geometric fidelity, noise resilience, and rapid inference. Furthermore, leveraging the same unified latent representation, we incorporate a diffusion model for computing cross fields of new shapes generated from partial input, such as sketches. To demonstrate its practical applications, we validate CrossGen on the quad mesh generation task for a large variety of surface shapes. Experimental results demonstrate that CrossGen generalizes well across diverse shapes and consistently yields high-fidelity cross fields, thus facilitating the generation of high-quality quad meshes.

Hand-drawn vector sketches often contain implied lines, imprecise intersections, and unintended gaps, making it challenging to identify closed regions for colorization. These challenges become more pronounced as the number of strokes increases. In this paper, we present KISSColor, a novel method for inferring users' intended closed regions. Specifically, we propose intuitive stroke stretching by extending open strokes along tangent isolines of winding-number fields, which provably form geometrically aligned closed regions. Extending all open strokes can lead to overly fragmented regions due to redundant intersections. While a Mixed Integer Programming (MIP) formulation helps reduce redundancy, it is computationally expensive. To improve efficiency, we introduce kinetic stroke stretching, which grows all strokes simultaneously and prioritizes early intersections using a kinetic data structure. This approach preserves stylistic ambiguity for lines requiring long extensions. Based on the growth results, redundant regions are suppressed to minimize fragmentation. We conduct extensive experiments demonstrating the effectiveness of KISSColor, which generates more intuitive partitions, especially for imprecise sketches (see teaser figure). Our code and data will be released upon publication.

Filleting is a fundamental operation in CAD systems, akin to a ball rolling between two adjacent surface patches, resulting in a seamless connection. The reverse process, which we refer to as DeFillet in this paper, is crucial for CAE analysis and secondary design phases. However, it presents significant challenges, particularly when the input data originates from surface reconstruction or discretization processes. Our DeFillet algorithm is inspired by the observation that the rolling-ball center defines an osculating sphere, while the Voronoi diagram of surface samples provides sufficiently many rolling-ball center candidates. By leveraging this insight, we compute a transformation between the Voronoi vertices and the surface samples, enabling the efficient identification of fillet regions. Subsequently, we formulate the reconstruction of sharp features as a quadratic optimization problem. Our method's effectiveness has been validated through extensive testing using self-constructed models and 100 filleted models selected from the Fusion 360 Gallery dataset. The code for this paper is publicly available at https://github.com/xiaowuga/DeFillet.

This article presents Diffusing Winding Gradients (DWG) for reconstructing watertight surfaces from unoriented point clouds. Our method exploits the alignment between the gradients of the screened generalized winding number (GWN) field—a robust variant of the standard GWN field—and globally consistent normals to orient points. Starting with an unoriented point cloud, DWG initially assigns a random normal to each point. It computes the corresponding screened GWN field and extracts a level set whose iso-value is the average of GWN values across all input points. The gradients of this level set are then utilized to update the point normals. This cycle of recomputing the screened GWN field and updating point normals is repeated until the screened GWN level sets stabilize and their gradients cease to change. Unlike conventional methods, DWG does not rely on solving linear systems or optimizing objective functions, which simplifies its implementation and enhances its suitability for efficient parallel execution. Experimental results demonstrate that DWG significantly outperforms existing methods in terms of runtime performance. For large-scale models with 10 to 20 million points, our CUDA implementation on an NVIDIA GTX 4090 GPU achieves speeds 30 to 120 times faster than iPSR, the leading sequential method, tested on a high-end PC with an Intel i9 CPU. Furthermore, by employing a screened variant of GWN, DWG demonstrates enhanced robustness against noise and outliers and proves effective for models with thin structures and real-world inputs with overlapping and misaligned scans. For source code and additional results, visit our project webpage: https://dwgtech.github.io/ .

Neural implicit shape representation has drawn significant attention in recent years due to its smoothness, differentiability, and topological flexibility. However, directly modeling the shape of a neural implicit surface, especially as the zero-level set of a neural signed distance function (SDF), with sparse geometric control is still a challenging task. Sparse input shape control typically includes 3D curve networks or, more generally, 3D curve sketches, which are unstructured and cannot be connected to form a curve network, and therefore more difficult to deal with. While 3D curve networks or curve sketches provide intuitive shape control, their sparsity and varied topology pose challenges in generating high-quality surfaces to meet such curve constraints. In this paper, we propose NeuVAS, a variational approach to shape modeling using neural implicit surfaces constrained under sparse input shape control, including unstructured 3D curve sketches as well as connected 3D curve networks. Specifically, we introduce a smoothness term based on a functional of surface curvatures to minimize shape variation of the zero-level set surface of a neural SDF. We also develop a new technique to faithfully model G 0 sharp feature curves as specified in the input curve sketches. Comprehensive comparisons with the state-of-the-art methods demonstrate the significant advantages of our method.

Boolean operations for Boundary Representation (B-Rep) models are among the most commonly used functions in Computer Aided Design (CAD) systems. They are also one of the most delicate soft modules, with challenges arising from complex algorithmic flows and efficiency and accuracy issues, especially in extreme cases. Common issues encountered in processing complex models include low efficiency, missing results, and non-watertightness. In this paper, we propose a novel algorithm for efficient and accurate Boolean operations on B-Rep models. This is achieved by establishing a bijective mapping between B-Rep models and the corresponding triangle meshes with controllable approximation error, thus mapping B-Rep Boolean operations to mesh Boolean operations. By using conservative intersection detection on the mesh to locate all surface intersection curves and carefully handling degeneration and topology errors, we ensure that the results are consistently watertight and correct. We demonstrate the superior efficiency of the proposed method using the open-source geometry engine OCCT, the commercial engine ACIS, and the commercial software Rhino as benchmarks.

Invisible orthodontics, commonly known as clear alignment treatment, offers a more comfortable and aesthetically pleasing alternative in orthodontic care, attracting considerable attention in the dental community in recent years. It replaces conventional metal braces with a series of removable, and transparent aligners. Each aligner is crafted to facilitate a gradual adjustment of the teeth, ensuring progressive stages of dental correction. This necessitates the design for teeth motion. Here we present an automatic method and a system for generating collision-free teeth motion planning while avoiding gaps between adjacent teeth, which is unacceptable in clinical practice. To tackle this task, we formulate it as a constrained optimization problem and utilize the interior point method for its solution. We also developed an interactive system that enables dentists to easily visualize and edit the paths. Our method significantly speeds up the clear aligner planning process, creating the desired motion paths for a full set of teeth in under five minutes-a task that typically requires several hours of manual work. Our experiments and user studies confirm the effectiveness of this method in planning teeth movement, showcasing its potential to streamline orthodontic procedures.

We propose a new method for computing smooth and integrable cross fields on 2D and 3D surfaces. our approach first computes smooth cross fields by minimizing the Dirichlet energy. Unlike existing optimization-based methods, our technique determines the singularity configuration-i.e., the number, locations, and indices of singularities-by iteratively adjusting them. Singularities can move, merge and split, akin to the behavior of like charges repelling and unlike charges attracting. Once all singularities stop moving, we obtain a cross field with (locally) the lowest Dirichlet energy. In simply connected domains, this cross field is guaranteed to be integrable. However, this property does not hold in multiply connected domains. To make a smooth cross field integrable, we construct a vector field $\bf c$c that characterizes the deviation of the cross field from a curl-free field. We then optimize the locations of singularities by moving them along the field lines of $\bf c$c. Our method is fundamentally different from existing integer programming-based approaches, as it avoids combinatorial optimization. It is fully automatic and includes a parameter to control the number of singularities. Our method is well suited for smooth models where exact boundary alignment and sparse hard directional constraints are desired, and can guide seamless conformal parameterization and T-junction-free quadrangulation.

While tooth alignment is crucial for digital dentistry, especially in orthodontic treatment, existing computer-aided methods mainly focus on the 3D dental crown but overlook the entire teeth, which is essential for applications in orthodontics. Besides, clinical orthodontic rules are not fully considered in these methods, i.e., there should be no collisions and gaps between teeth, the upper jaw and lower jaw should have correct occlusion relationships, the teeth should comply with a reasonable dental arch curve, etc. To generate optimal tooth alignment results, we propose a rule-based optimization method for solving the tooth alignment problem that takes into consideration the clinical rules functionally and aesthetically. We optimize rule-driven objective functions by adjusting the 6-DoF transformations of each tooth. Besides, our optimization formulation supports customization for different clinical scenarios by specifying the various energy terms. Extensive experiments, ablation studies, and user studies have been conducted to validate the effectiveness of our method. Quantitative and qualitative comparisons demonstrate that our method generates better tooth alignments than previous methods.

In the field of 3D point cloud generation, numerous 3D generative models have demonstrated the ability to generate diverse and realistic 3D shapes. However, the majority of these approaches struggle to generate controllable 3D point cloud shapes that meet user-specific requirements, hindering the large-scale application of 3D point cloud generation. To address the challenge of lacking control in 3D point cloud generation, we are the first to propose controlling the generation of point clouds by shape structures that comprise part existences and part adjacency relationships. We manually annotate the adjacency relationships between the segmented parts of point cloud shapes, thereby constructing a StructureGraph representation. Based on this StructureGraph representation, we introduce StrucADT, a novel structure-controllable point cloud generation model, which consists of StructureGraphNet module to extract structure-aware latent features, cCNF Prior module to learn the distribution of the latent features controlled by the part adjacency, and Diffusion Transformer module conditioned on the latent features and part adjacency to generate structure-consistent point cloud shapes. Experimental results demonstrate that our structure-controllable 3D point cloud generation method produces high-quality and diverse point cloud shapes, enabling the generation of controllable point clouds based on user-specified shape structures and achieving state-of-the-art performance in controllable point cloud generation on the ShapeNet dataset.

The task of 3D shape captioning occupies a significant place within the domain of computer graphics and has garnered considerable interest in recent years. Traditional approaches to this challenge frequently depend on the utilization of costly voxel representations or object detection techniques, yet often fail to deliver satisfactory outcomes. To address the above challenges, in this paper, we introduce Diff-3DCap, which employs a sequence of projected views to represent a 3D object and a continuous diffusion model to facilitate the captioning process. More precisely, our approach utilizes the continuous diffusion model to perturb the embedded captions during the forward phase by introducing Gaussian noise and then predicts the reconstructed annotation during the reverse phase. Embedded within the diffusion framework is a commitment to leveraging a visual embedding obtained from a pre-trained visual-language model, which naturally allows the embedding to serve as a guiding signal, eliminating the need for an additional classifier. Extensive results of our experiments indicate that Diff-3DCap can achieve performance comparable to that of the current state-of-the-art methods.

Identifying points of interest (POIs) on the surface of 3D shapes is a significant challenge in geometric processing research. The complex connection between POIs and their geometric descriptors, combined with the small percentage of POIs on the shape, makes detecting POIs on any given 3D shape a highly challenging task. Existing methods directly detect POIs from the entire 3D shape, resulting in low efficiency and accuracy. Therefore, we propose a novel multi-modal POI detection method using a coarse-to-fine approach, with the key idea of reducing data complexity and enabling more efficient and accurate subsequent POI detection by first identifying and processing important regions on the 3D shape. It first obtains important areas on the 3D shape through 2D projected images, then processes points within these regions using attention mechanisms. Extensive experiments demonstrate that our method outperforms existing POI detection techniques.

This paper presents GaussEdit, a framework for adaptive 3D scene editing guided by text and image prompts. GaussEdit leverages 3D Gaussian Splatting as its backbone for scene representation, enabling convenient Region of Interest selection and efficient editing through a three-stage process. The first stage involves initializing the 3D Gaussians to ensure high-quality edits. The second stage employs an Adaptive Global-Local Optimization strategy to balance global scene coherence and detailed local edits and a category-guided regularization technique to alleviate the Janus problem. The final stage enhances the texture of the edited objects using a sophisticated image-to-image synthesis technique, ensuring that the results are visually realistic and align closely with the given prompts. Our experimental results demonstrate that GaussEdit surpasses existing methods in editing accuracy, visual fidelity, and processing speed. By successfully embedding user-specified concepts into 3D scenes, GaussEdit is a powerful tool for detailed and user-driven 3D scene editing, offering significant improvements over traditional methods.

Point cloud completion is a vital task focused on reconstructing complete point clouds and addressing the incompleteness caused by occlusion and limited sensor resolution. Traditional methods relying on fixed local region partitioning, such as $k$k-nearest neighbors, which fail to account for the highly uneven distribution of geometric complexity across different regions of a shape. This limitation leads to inefficient representation and suboptimal reconstruction, especially in areas with fine-grained details or structural discontinuities. This paper proposes a point cloud completion framework called Degree-Flexible Point Graph Completion Network (DFG-PCN). It adaptively assigns node degrees using a detail-aware metric that combines feature variation and curvature, focusing on structurally important regions. We further introduce a geometry-aware graph integration module that uses Manhattan distance for edge aggregation and detail-guided fusion of local and global features to enhance representation. Extensive experiments on multiple benchmark datasets demonstrate that our method consistently outperforms state-of-the-art approaches.

Extraction of a high-fidelity 3D medial axis is a crucial operation in CAD. When dealing with a polygonal model as input, ensuring accuracy and tidiness becomes challenging due to discretization errors inherent in the mesh surface. Commonly, existing approaches yield medial-axis surfaces with various artifacts, including zigzag boundaries, bumpy surfaces, unwanted spikes, and non-smooth stitching curves. Considering that the surface of a CAD model can be easily decomposed into a collection of surface patches, its 3D medial axis can be extracted by computing the Voronoi diagram of these surface patches, where each surface patch serves as a generator. However, no solver currently exists for accurately computing such an extended Voronoi diagram. Under the assumption that each generator defines a linear distance field over a sufficiently small range, our approach operates by tetrahedralizing the region of interest and computing the medial axis within each tetrahedral element. Just as SurfaceVoronoi computes surface-based Voronoi diagrams by cutting a 3D prism with 3D planes (each plane encodes a linear field in a triangle), the key operation in this paper is to conduct the hyperplane cutting process in 4D, where each hyperplane encodes a linear field in a tetrahedron. In comparison with the state-of-the-art, our algorithm produces better outcomes. Furthermore, it can also be used to compute the offset surface.

This paper presents a novel non-rigid point set registration method that is inspired by unsupervised clustering analysis. Unlike previous approaches that treat the source and target point sets as separate entities, we develop a holistic framework where they are formulated as clustering centroids and clustering members, separately. We then adopt Tikhonov regularization with an$\ell_{1}$-induced Laplacian kernel instead of the commonly used Gaussian kernel to ensure smooth and more robust displacement fields. Our formulation delivers closed-form solutions, theoretical guarantees, independence from dimensions, and the ability to handle large deformations. Subsequently, we introduce a clustering-improved Nyström method to effectively reduce the computational complexity and storage of the Gram matrix to linear, while providing a rigorous bound for the low-rank approximation. Our method achieves high accuracy results across various scenarios and surpasses competitors by a significant margin, particularly on shapes with sub-stantial deformations. Additionally, we demonstrate the versatility of our method in challenging tasks such as shape transfer and medical registration. [Code release]

Given the rapid advancements in geometric deep-learning techniques, there has been a dedicated effort to create mesh-based convolutional operators that act as a link between irregular mesh structures and widely adopted backbone networks . Despite the numerous advantages of Convolutional Neural Networks (CNNs) over Multi-Layer Perceptrons (MLPs), mesh-oriented CNNs often require intricate network architectures to tackle irregularities of a triangular mesh. These architectures not only demand that the mesh be manifold and watertight but also impose constraints on the abundance of training samples . In this paper, we note that for specific tasks such as mesh classification and semantic part segmentation, large-scale shape features play a pivotal role . This is in contrast to the realm of shape correspondence, where a comprehensive understanding of 3D shapes necessitates considering both local and global characteristics. Inspired by this key observation, we introduce a task-driven neural network architecture that seamlessly operates in an end-to-end fashion. Our method takes as input mesh vertices equipped with the heat kernel signature (HKS) and dihedral angles between adjacent faces . Notably, we replace the conventional convolutional module, commonly found in ResNet architectures, with MLPs and incorporate Layer Normalization (LN) to facilitate layer-wise normalization. Our approach, with a seemingly straightforward network architecture, demonstrates an accuracy advantage. It exhibits a marginal 0.1% improvement in the mesh classification task and a substantial 1.8% enhancement in the mesh part segmentation task compared to state-of-the-art methodologies. Moreover, as the number of training samples decreases to 1/50 or even 1/100, the accuracy advantage of our approach becomes more pronounced. In summary, our convolution-free network is tailored for specific tasks relying on large-scale shape features and excels in the situation with a limited number of training samples, setting itself apart from state-of-the-art methodologies.

Abstract We introduce Coverage Axis++, a novel and efficient approach to 3D shape skeletonization. The current state‐of‐the‐art approaches for this task often rely on the watertightness of the input [LWS*15; PWG*19; PWG*19] or suffer from substantial computational costs [DLX*22; CD23], thereby limiting their practicality. To address this challenge, Coverage Axis++ proposes a heuristic algorithm to select skeletal points, offering a high‐accuracy approximation of the Medial Axis Transform (MAT) while significantly mitigating computational intensity for various shape representations. We introduce a simple yet effective strategy that considers shape coverage, uniformity, and centrality to derive skeletal points. The selection procedure enforces consistency with the shape structure while favoring the dominant medial balls, which thus introduces a compact underlying shape representation in terms of MAT. As a result, Coverage Axis++ allows for skeletonization for various shape representations (e.g., water‐tight meshes, triangle soups, point clouds), specification of the number of skeletal points, few hyperparameters, and highly efficient computation with improved reconstruction accuracy. Extensive experiments across a wide range of 3D shapes validate the efficiency and effectiveness of Coverage Axis++. Our codes are available at https://github.com/Frank-ZY-Dou/Coverage_Axis .

The segmentation of 3D shapes is a critical aspect of shape analysis. However, most existing methods for 3D shape segmentation treat each face of the original mesh model with equal importance. This uniform approach becomes problematic in areas where the faces are smaller but denser, especially around the junctions of different segments. In such regions, greater importance should be assigned compared to the flatter areas. To address this issue, this paper proposes a novel 3D shape segmentation method that incorporates attentive nonuniform sampling into the segmentation pipeline. By leveraging a transformer-based mechanism, our method adaptively identifies the intricate details of 3D shapes, calculating varying degrees of attention to each face. Consequently, the mesh model is downsampled by eliminating faces with lower attention, thereby optimizing the segmentation process. Our approach outperforms most state-of-the-art methods on multiple public datasets, making it a promising avenue for future research.

3D shape segmentation is a fundamental and crucial task in the field of image processing and 3D shape analysis. To segment 3D shapes using data-driven methods, a fully labeled dataset is usually required. However, obtaining such a dataset can be a daunting task, as manual face-level labeling is both time-consuming and labor-intensive. In this paper, we present a semi-supervised framework for 3D shape segmentation that uses a small, fully labeled set of 3D shapes, as well as a weakly labeled set of 3D shapes with sparse scribble labels. Our framework first employs an auxiliary network to generate initial fully labeled segmentation labels for the sparsely labeled dataset, which helps in training the primary network. During training, the self-refine module uses increasingly accurate predictions of the primary network to improve the labels generated by the auxiliary network. Our proposed method achieves better segmentation performance than previous semi-supervised methods, as demonstrated by extensive benchmark tests, while also performing comparably to supervised methods.

With the fast development of the 5G wireless communications, the Internet of Things (IoT) becomes a hot research topic. Unmanned aerial vehicles (UAVs), due to the high mobility and low labor cost, have a big potential to be applied in the future IoT communication networks, e.g., data collection in remote areas. In this paper, we take a UAV as a monitor and an IoT device as an agent, and study how to utilize UAVs to establish network coverage and enhance the overall performance. Given ground agents and aerial monitors, each agent needs to be supervised by one monitor that can at most take charge of certain amount, while such assignment should guarantee the required service quality. This is much different from the conventional assumption that each monitor owns exactly a fixed number of agents without considering sensing quality under limited transmit power. Suppose that a monitor supervises an agent with a cost as the negative value of transmission rate in Rician fading, we then maximize the sum of transmission induced by every monitor-agent connection constrained with workload capacity for each monitor. To achieve the above goals, we first present a fast algorithm to report the least-cost assignment plan. Then, we seek for the minimum number of monitors to maintain the required service quality. Last, we discuss the assignment problem in the scenario of dynamic agents and dynamic monitors. We also give a set of strategies on how to initialize assignment, optimize monitor locations and manage power consumption. Extensive experimental results on both simulated datasets and real-life traffic data demonstrate our effectiveness and high performance.

Despite recent advances in reconstructing an organic model with the neural signed distance function (SDF), the high-fidelity reconstruction of a CAD model directly from low-quality unoriented point clouds remains a significant challenge. In this paper, we address this challenge based on the prior observation that the surface of a CAD model is generally composed of piecewise surface patches, each approximately developable even around the feature line. Our approach, named NeurCADRecon , is self-supervised, and its loss includes a developability term to encourage the Gaussian curvature toward 0 while ensuring fidelity to the input points (see the teaser figure). Noticing that the Gaussian curvature is non-zero at tip points, we introduce a double-trough curve to tolerate the existence of these tip points. Furthermore, we develop a dynamic sampling strategy to deal with situations where the given points are incomplete or too sparse. Since our resulting neural SDFs can clearly manifest sharp feature points/lines, one can easily extract the feature-aligned triangle mesh from the SDF and then decompose it into smooth surface patches, greatly reducing the difficulty of recovering the parametric CAD design. A comprehensive comparison with existing state-of-the-art methods shows the significant advantage of our approach in reconstructing faithful CAD shapes.

Surface offsetting is a crucial operation in digital geometry processing and computer-aided design, where an offset is defined as an iso-value surface of the distance field. A challenge emerges as even smooth surfaces can exhibit sharp features in their offsets due to the non-differentiable characteristics of the underlying distance field. Prevailing approaches to the offsetting problem involve approximating the distance field and then extracting the iso-surface. However, even with dual contouring (DC), there is a risk of degrading sharp feature points/lines due to the inaccurate discretization of the distance field. This issue is exacerbated when the input is a piecewise-linear triangle mesh. This study is inspired by the observation that a triangle-based distance field, unlike the complex distance field rooted at the entire surface, remains smooth across the entire 3D space except at the triangle itself. With a polygonal surface comprising n triangles, the final distance field for accommodating the offset surface is determined by minimizing these n triangle-based distance fields. In implementation, our approach starts by tetrahedralizing the space around the offset surface, enabling a tetrahedron-wise linear approximation for each triangle-based distance field. The final offset surface within a tetrahedral range can be traced by slicing the tetrahedron with planes. As illustrated in the teaser figure, a key advantage of our algorithm is its ability to precisely preserve sharp features. Furthermore, this paper addresses the problem of simplifying the offset surface's complexity while preserving sharp features, formulating it as a maximal-clique problem.

In mesh simplification, common requirements like accuracy, triangle quality, and feature alignment are often considered as a trade-off. Existing algorithms concentrate on just one or a few specific aspects of these requirements. For example, the well-known Quadric Error Metrics (QEM) approach [Garland and Heckbert 1997] prioritizes accuracy and can preserve strong feature lines/points as well, but falls short in ensuring high triangle quality and may degrade weak features that are not as distinctive as strong ones. In this paper, we propose a smooth functional that simultaneously considers all of these requirements. The functional comprises a normal anisotropy term and a Centroidal Voronoi Tessellation (CVT) [Du et al. 1999] energy term, with the variables being a set of movable points lying on the surface. The former inherits the spirit of QEM but operates in a continuous setting, while the latter encourages even point distribution, allowing various surface metrics. We further introduce a decaying weight to automatically balance the two terms. We selected 100 CAD models from the ABC dataset [Koch et al. 2019], along with 21 organic models, to compare the existing mesh simplification algorithms with ours. Experimental results reveal an important observation: the introduction of a decaying weight effectively reduces the conflict between the two terms and enables the alignment of weak features. This distinctive feature sets our approach apart from most existing mesh simplification methods and demonstrates significant potential in shape understanding. Please refer to the teaser figure for illustration.

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

Geometric deep learning has sparked a rising interest in computer graphics to perform shape understanding tasks, such as shape classification and semantic segmentation. When the input is a polygonal surface, one has to suffer from the irregular mesh structure. Motivated by the geometric spectral theory, we introduce Laplacian2Mesh, a novel and flexible convolutional neural network (CNN) framework for coping with irregular triangle meshes (vertices may have any valence). By mapping the input mesh surface to the multi-dimensional Laplacian-Beltrami space, Laplacian2Mesh enables one to perform shape analysis tasks directly using the mature CNNs, without the need to deal with the irregular connectivity of the mesh structure. We further define a mesh pooling operation such that the receptive field of the network can be expanded while retaining the original vertex set as well as the connections between them. Besides, we introduce a channel-wise self-attention block to learn the individual importance of feature ingredients. Laplacian2Mesh not only decouples the geometry from the irregular connectivity of the mesh structure but also better captures the global features that are central to shape classification and segmentation. Extensive tests on various datasets demonstrate the effectiveness and efficiency of Laplacian2Mesh, particularly in terms of the capability of being vulnerable to noise to fulfill various learning tasks.

Surface reconstruction is a challenging task when input point clouds, especially real scans, are noisy and lack normals. Observing that the Multilayer Perceptron (MLP) and the implicit moving least-square function (IMLS) provide a dual representation of the underlying surface, we introduce Neural-IMLS, a novel approach that directly learns a noise-resistant signed distance function (SDF) from unoriented raw point clouds in a self-supervised manner. In particular, IMLS regularizes MLP by providing estimated SDFs near the surface and helps enhance its ability to represent geometric details and sharp features, while MLP regularizes IMLS by providing estimated normals. We prove that at convergence, our neural network produces a faithful SDF whose zero-level set approximates the underlying surface due to the mutual learning mechanism between the MLP and the IMLS. Extensive experiments on various benchmarks, including synthetic and real scans, show that Neural-IMLS can reconstruct faithful shapes even with noise and missing parts. The source code can be found at https://github.com/bearprin/Neural-IMLS.

We propose a novel and efficient method for reconstructing manifold surfaces from point clouds. Unlike previous approaches that use dense implicit reconstructions or piecewise approximations and overlook inherent structures like quadrics in CAD models, our method faithfully preserves these quadric structures by assembling primitives. To achieve high-quality primitive extraction, we use a variational shape approximation, followed by a mesh arrangement for space partitioning and candidate primitive patches generation. We then introduce an effective pruning mechanism to classify candidate primitive patches as active or inactive, and further prune inactive patches to reduce the search space and speed up surface extraction significantly. Finally, the optimal active patches are computed by a binary linear programming and assembled as manifold and watertight surfaces. We perform extensive experiments on a wide range of CAD objects to validate its effectiveness.

The Signed Distance Function (SDF), as an implicit surface representation, provides a crucial method for reconstructing a watertight surface from unorganized point clouds. The SDF has a fundamental relationship with the principles of surface vector calculus. Given a smooth surface, there exists a thin-shell space in which the SDF is differentiable everywhere such that the gradient of the SDF is an eigenvector of its Hessian matrix, with a corresponding eigenvalue of zero. In this paper, we introduce a method to directly learn the SDF from point clouds in the absence of normals. Our motivation is grounded in a fundamental observation: aligning the gradient and the Hessian of the SDF provides a more efficient mechanism to govern gradient directions. This, in turn, ensures that gradient changes more accurately reflect the true underlying variations in shape. Extensive experimental results demonstrate its ability to accurately recover the underlying shape while effectively suppressing the presence of ghost geometry.

Shape manipulation is a central research topic in computer graphics. Topology editing, such as breaking apart connections, joining disconnected ends, and filling/opening a topological hole, is generally more challenging than geometry editing. In this paper, we observe that the saddle points of the signed distance function (SDF) provide useful hints for altering surface topology deliberately. Based on this key observation, we parameterize the SDF into a cubic trivariate tensor-product B-spline function F whose saddle points {si} can be quickly exhausted based on a subdivision-based root-finding technique coupled with Newton’s method. Users can select one of the candidate points, say si, to edit the topology in real time. In implementation, we add a compactly supported B-spline function rooted at si, which we call a deformer in this paper, to F, with its local coordinate system aligning with the three eigenvectors of the Hessian. Combined with ray marching technique, our interactive system operates at 30 FPS. Additionally, our system empowers users to create desired bulges or concavities on the surface. An extensive user study indicates that our system is user-friendly and intuitive to operate. We demonstrate the effectiveness and usefulness of our system in a range of applications, including fixing surface reconstruction errors, artistic work design, 3D medical imaging and simulation, and antiquity restoration. Please refer to the attached video for a demonstration.

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.

Voronoi diagrams on triangulated surfaces based on the geodesic metric play a key role in many applications of computer graphics. Previous methods of constructing such Voronoi diagrams generally depended on having an exact geodesic metric. However, exact geodesic computation is time-consuming and has high memory usage, limiting wider application of geodesic Voronoi diagrams (GVDs). In order to overcome this issue, instead of using exact methods, we reformulate a graph method based on Steiner point insertion, as an effective way to obtain geodesic distances. Further, since a bisector comprises hyperbolic and line segments, we utilize Apollonius diagrams to encode complicated structures, enabling Voronoi diagrams to encode a medial-axis surface for a dense set of boundary samples. Based on these strategies, we present an approximation algorithm for efficient Voronoi diagram construction on triangulated surfaces. We also suggest a measure for evaluating similarity of our results to the exact GVD. Although our GVD results are constructed using approximate geodesic distances, we can get GVD results similar to exact results by inserting Steiner points on triangle edges. Experimental results on many 3D models indicate the improved speed and memory requirements compared to previous leading methods.

Neural implicit representation is a promising approach for reconstructing surfaces from point clouds. Existing methods combine various regularization terms, such as the Eikonal and Laplacian energy terms, to enforce the learned neural function to possess the properties of a Signed Distance Function (SDF). However, inferring the actual topology and geometry of the underlying surface from poor-quality unoriented point clouds remains challenging. In accordance with Differential Geometry, the Hessian of the SDF is singular for points within the differential thin-shell space surrounding the surface. Our approach enforces the Hessian of the neural implicit function to have a zero determinant for points near the surface. This technique aligns the gradients for a near-surface point and its on-surface projection point, producing a rough but faithful shape within just a few iterations. By annealing the weight of the singular-Hessian term, our approach ultimately produces a high-fidelity reconstruction result. Extensive experimental results demonstrate that our approach effectively suppresses ghost geometry and recovers details from unoriented point clouds with better expressiveness than existing fitting-based methods.

Estimating normals with globally consistent orientations for a raw point cloud has many downstream geometry processing applications. Despite tremendous efforts in the past decades, it remains challenging to deal with an unoriented point cloud with various imperfections, particularly in the presence of data sparsity coupled with nearby gaps or thin-walled structures. In this paper, we propose a smooth objective function to characterize the requirements of an acceptable winding-number field, which allows one to find the globally consistent normal orientations starting from a set of completely random normals. By taking the vertices of the Voronoi diagram of the point cloud as examination points, we consider the following three requirements: (1) the winding number is either 0 or 1, (2) the occurrences of 1 and the occurrences of 0 are balanced around the point cloud, and (3) the normals align with the outside Voronoi poles as much as possible. Extensive experimental results show that our method outperforms the existing approaches, especially in handling sparse and noisy point clouds, as well as shapes with complex geometry/topology.

Most of the existing point-to-mesh distance query solvers, such as Proximity Query Package (PQP), Embree and Fast Closest Point Query (FCPW), are based on bounding volume hierarchy (BVH). The hierarchical organizational structure enables one to eliminate the vast majority of triangles that do not help find the closest point. In this paper, we develop a totally different algorithmic paradigm, named P2M , to speed up point-to-mesh distance queries. Our original intention is to precompute a KD tree (KDT) of mesh vertices to approximately encode the geometry of a mesh surface containing vertices, edges and faces. However, it is very likely that the closest primitive to the query point is an edge e (resp., a face f ), but the KDT reports a mesh vertex υ instead. We call υ an interceptor of e (resp., f ). The main contribution of this paper is to invent a simple yet effective interception inspection rule and an efficient flooding interception inspection algorithm for quickly finding out all the interception pairs. Once the KDT and the interception table are precomputed, the query stage proceeds by first searching the KDT and then looking up the interception table to retrieve the closest geometric primitive. Statistics show that our query algorithm runs many times faster than the state-of-the-art solvers.

Detecting points of interest is a fundamental problem in 3D shape analysis and can be beneficial to various tasks in multimedia processing. Traditional learning-based detection methods usually rely on each vertex’s geometric features to discriminate points of interest from other vertices. Observing that points of interest are related to not only geometric features on themselves but also the geometric features of surrounding vertices, we propose a novel context-aware 3D points of interest detection algorithm by adopting the spatial attention mechanism in this article. By designing a context attention module, our approach presents a novel deep neural network to simultaneously pay attention to the geometric features of vertices and their local contexts during extracting points of interest. To obtain satisfactory extraction results, our method adaptively assigns different weights to those features in a data-driven way. Extensive experimental results on SHREC 2007, SHREC 2011, and SHREC 2014 datasets show that our algorithm achieves superior performance over existing methods.

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.

Abstract In this paper, we present a simple yet effective formulation called Coverage Axis for 3D shape skeletonization. Inspired by the set cover problem, our key idea is to cover all the surface points using as few inside medial balls as possible. This formulation inherently induces a compact and expressive approximation of the Medial Axis Transform (MAT) of a given shape. Different from previous methods that rely on local approximation error, our method allows a global consideration of the overall shape structure, leading to an efficient high‐level abstraction and superior robustness to noise. Another appealing aspect of our method is its capability to handle more generalized input such as point clouds and poor‐quality meshes. Extensive comparisons and evaluations demonstrate the remarkable effectiveness of our method for generating compact and expressive skeletal representation to approximate the MAT.

We present a simple yet effective method for constructing 3D self-supporting surfaces with planar quadrilateral (PQ) elements. Starting with a triangular discretization of a self-supporting surface, we first compute the principal curvatures and directions of each triangular face using a new discrete differential geometry approach, yielding more accurate results than existing methods. Then, we smooth the principal direction field to reduce the number of singularities. Next, we partition all faces into two groups in terms of principal curvature difference. For each face with small curvature difference, we compute a stretch matrix that turns the principal directions into a pair of conjugate directions. For the remaining triangular faces, we simply keep their smoothed principal directions. Finally, applying a mixed-integer programming solver to the mixed principal and conjugate direction field, we obtain a planar quadrilateral mesh. Experimental results show that our method is computationally efficient and can yield high-quality PQ meshes that well approximate the geometry of the input surfaces and maintain their self-supporting properties.

Detecting points of interest on 3D shapes is a fundamental research problem in geometry processing. Due to the complicated relationship between points of interest and their geometric features, detecting points of interest on any given 3D shape remains challenging. Due to the lack of training data, previous data-driven methods for detecting 3D points of interest mainly focus on utilizing hand-crafted geometric features to predict the probabilities of each point being a POI, which greatly limits detection performance. In this paper, we propose a novel algorithm for detecting 3D points of interest by using projective neural networks. Our method first projects the labeled training 3D shapes into multiple 2D views and then learns the required features from the 2D views in an end-to-end fashion. The points of interest on test 3D shapes are then automatically detected by applying the learned neural network and our improved density peak clustering. Our method relies neither on hand-crafted feature descriptors nor a large quantity of expensive 3D training data to obtain satisfactory results. Experimental results show significantly superior detection performance of our method over the state-of-the-art methods.

Wrapping objects using ropes is a common practice in our daily life. However, it is difficult to design and tie ropes on a 3D object with complex topology and geometry features while ensuring wrapping security and easy operation. In this article, we propose to compute a rope net that can tightly wrap around various 3D shapes. Our computed rope net not only immobilizes the object but also maintains the load balance during lifting. Based on the key observation that if every knot of the net has four adjacent curve edges, then only a single rope is needed to construct the entire net. We reformulate the rope net computation problem into a constrained curve network optimization. We propose a discrete-continuous optimization approach, where the topological constraints are satisfied in the discrete phase and the geometrical goals are achieved in the continuous stage. We also develop a hoist planning to pick anchor points so that the rope net equally distributes the load during hoisting. Furthermore, we simulate the wrapping process and use it to guide the physical rope net construction process. We demonstrate the effectiveness of our method on 3D objects with varying geometric and topological complexity. In addition, we conduct physical experiments to demonstrate the practicability of our method.

The task of explicit surface reconstruction is to generate a surface mesh by interpolating a given point cloud. Explicit surface reconstruction is necessary when the point cloud is required to appear exactly on the surface. However, for a non-perfect input, such as lack of normals, low density, irregular distribution, thin and tiny parts, and high genus, a robust explicit reconstruction method that can generate a high-quality manifold triangulation is missing. We propose a robust explicit surface reconstruction method that starts from an initial simple surface mesh, alternately performs a Filmsticking step and a Sculpting step of the initial mesh, and converges when the surface mesh interpolates all input points (except outliers) and remains stable. The Filmsticking is to minimize the geometric distance between the surface mesh and the point cloud through iteratively performing a restricted Voronoi diagram technique on the surface mesh, whereas the Sculpting is to bootstrap the Filmsticking iteration from local minima by applying appropriate geometric and topological changes of the surface mesh. Our algorithm is fully automatic and produces high-quality surface meshes for non-perfect inputs that are typically considered to be challenging for prior state of the art. We conducted extensive experiments on simulated scans and real scans to validate the effectiveness of our approach.

In this paper, we propose to compute Voronoi diagrams over mesh surfaces driven by an arbitrary geodesic distance solver, assuming that the input is a triangle mesh as well as a collection of sites P = { Pi } m i =1 on the surface. We propose two key techniques to solve this problem. First, as the partition is determined by minimizing the m distance fields, each of which rooted at a source site, we suggest keeping one or more distance triples, for each triangle, that may help determine the Voronoi bisectors when one uses a mark-and-sweep geodesic algorithm to predict the multi-source distance field. Second, rather than keep the distance itself at a mesh vertex, we use the squared distance to characterize the linear change of distance field restricted in a triangle, which is proved to induce an exact VD when the base surface reduces to a planar triangle mesh. Specially, our algorithm also supports the Euclidean distance, which can handle thin-sheet models (e.g. leaf) and runs faster than the traditional restricted Voronoi diagram (RVD) algorithm. It is very extensible to deal with various variants of surface-based Voronoi diagrams including (1) surface-based power diagram, (2) constrained Voronoi diagram with curve-type breaklines, and (3) curve-type generators. We conduct extensive experimental results to validate the ability to approximate the exact VD in different distance-driven scenarios.

Feature lines are important geometric cues in characterizing the structure of a CAD model. Despite great progress in both explicit reconstruction and implicit reconstruction, it remains a challenging task to reconstruct a polygonal surface equipped with feature lines, especially when the input point cloud is noisy and lacks faithful normal vectors. In this paper, we develop a multistage algorithm, named RFEPS , to address this challenge. The key steps include (1) denoising the point cloud based on the assumption of local planarity, (2) identifying the feature-line zone by optimization of discrete optimal transport, (3) augmenting the point set so that sufficiently many additional points are generated on potential geometry edges, and (4) generating a polygonal surface that interpolates the augmented point set based on restricted power diagram. We demonstrate through extensive experiments that RFEPS, benefiting from the edge-point augmentation and the feature preserving explicit reconstruction, outperforms state of the art methods in terms of the reconstruction quality, especially in terms of the ability to reconstruct missing feature lines.

This article addresses the problem of mesh super-resolution such that the geometry details which are not well represented in the low-resolution models can be recovered and well represented in the generated high-quality models. The main challenges of this problem are the nonregularity of 3D mesh representation and the high complexity of 3D shapes. We propose a deep neural network called GDR-Net to solve this ill-posed problem, which resolves the two challenges simultaneously. First, to overcome the nonregularity, we regress a displacement in radial basis function parameter space instead of the vertex-wise coordinates in the euclidean space. Second, to overcome the high complexity, we apply the detail recovery process to small surface patches extracted from the input surface and obtain the overall high-quality mesh by fusing the refined surface patches. To train the network, we constructed a dataset composed of both real-world and synthetic scanned models, including high/low-quality pairs. Our experimental results demonstrate that GDR-Net works well for general models and outperforms previous methods for recovering geometric details.

Segmenting arbitrary 3D objects into constituent parts that are structurally meaningful is a fundamental problem encountered in a wide range of computer graphics applications. Existing methods for 3D shape segmentation suffer from complex geometry processing and heavy computation caused by using low-level features and fragmented segmentation results due to the lack of global consideration. We present an efficient method, called SEG-MAT, based on the medial axis transform (MAT) of the input shape. Specifically, with the rich geometrical and structural information encoded in the MAT, we are able to develop a simple and principled approach to effectively identify the various types of junctions between different parts of a 3D shape. Extensive evaluations and comparisons show that our method outperforms the state-of-the-art methods in terms of segmentation quality and is also one order of magnitude faster.

This article presents a simple yet effective method for computing geodesic distances on triangle meshes. Unlike the popular window propagation methods that partition mesh edges into intervals of varying lengths, our method places evenly-spaced, source-independent Steiner points on edges. Given a source vertex, our method constructs a Steiner-point graph that partitions the surface into mutually exclusive tracks, called geodesic tracks. Inside each triangle, the tracks form sub-regions in which the change of distance field is approximately linear. Our method does not require any pre-computation, and can effectively balance speed and accuracy. Experimental results show that with 5 Steiner points on each edge, the mean relative error is less than 0.3 % for common 3D models used in the graphics community. We propose a set of effective filtering rules to eliminate a large amount of useless broadcast events. For a 1000K-face model, our method runs 10 times faster than the conventional Steiner point method that examines a complete graph of Steiner points in each triangle. We also observe that using more Steiner points increases the accuracy at only a small extra computational cost. Our method works well for meshes with poor triangulation and non-manifold configuration, which often poses challenges to the existing PDE methods. We show that geodesic tracks, as a new data structure that encodes rich information of discrete geodesics, support accurate geodesic path and isoline tracing, and efficient distance query. Our method can be easily extended to meshes with non-constant density functions and/or anisotropic metrics.

Superpixel segmentation, as a central image processing task, has many applications in computer vision and computer graphics. Boundary alignment and shape compactness are leading indicators to evaluate a superpixel segmentation algorithm. Furthermore, convexity can make superpixels reflect more geometric structures in images and provide a more concise over-segmentation result. In this paper, we consider generating convex and compact superpixels while satisfying the constraints of adhering to the boundary as far as possible. We formulate the new superpixel segmentation into an edge-constrained centroidal power diagram (ECCPD) optimization problem. In the implementation, we optimize the superpixel configurations by repeatedly performing two alternative operations, which include site location updating and weight updating through a weight function defined by image features. Compared with existing superpixel methods, our method can partition an image into fully convex and compact superpixels with better boundary adherence. Extensive experimental results show that our approach outperforms existing superpixel segmentation methods in boundary alignment and compactness for generating convex superpixels.

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 3D scanned point cloud data of teeth is popular used in digital orthodontics. The classification and semantic labelling for point cloud of each tooth is a key and challenging task for planning dental treatment. Utilizing the priori ordered position information of tooth arrangement, we propose an effective network for tooth model classification in this paper. The relative position and the adjacency similarity feature vectors are calculated for tooth 3D model, and combine the geometric feature into the fully connected layers of the classification training task. For the classification of dental anomalies, we present a dental anomalies processing method to improve the classification accuracy. We also use FocalLoss as the loss function to solve the sample imbalance of wisdom teeth. The extensive evaluations, ablation studies and comparisons demonstrate that the proposed network can classify tooth models accurately and automatically and outperforms state‐of‐the‐art point cloud classification methods.

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.

Shape segmentation is a fundamental problem in shape analysis. Previous research shows that prior knowledge helps to improve the segmentation accuracy and quality. However, completely labeling each 3D shape in a large training data set requires a heavy manual workload. In this paper, we propose a novel weakly-supervised algorithm for segmenting 3D shapes using deep learning. Our method jointly propagates information from scribbles to unlabeled faces and learns deep neural network parameters. Therefore, it does not rely on completely labeled training shapes and only needs a really simple and convenient scribble-based partially labeling process, instead of the extremely time-consuming and tedious fully labeling processes. Various experimental results demonstrate the proposed method's superior segmentation performance over the previous unsupervised approaches and comparable segmentation performance to the state-of-the-art fully supervised methods.

Abstract Image vectorization is an important yet challenging problem, especially when the input image has rich content. In this paper, we develop a novel method for automatically vectorizing natural images with feature‐aligned quad‐dominant meshes. Inspired by the quadrangulation methods in 3D geometry processing, we propose a new directional field optimization technique by encoding the color gradients, sidestepping the explicit computing of salient image features. We further compute the anisotropic scales of the directional field by accommodating the distance among image features. Our method is fully automatic and efficient, which takes only a few seconds for a 400×400 image on a normal laptop. We demonstrate the effectiveness of the proposed method on various image editing applications.

We present an autonomous scanning approach which allows multiple robots to perform collaborative scanning for dense 3D reconstruction of unknown indoor scenes. Our method plans scanning paths for several robots, allowing them to efficiently coordinate with each other such that the collective scanning coverage and reconstruction quality is maximized while the overall scanning effort is minimized. To this end, we define the problem as a dynamic task assignment and introduce a novel formulation based on Optimal Mass Transport (OMT). Given the currently scanned scene, a set of task views are extracted to cover scene regions which are either unknown or uncertain. These task views are assigned to the robots based on the OMT optimization. We then compute for each robot a smooth path over its assigned tasks by solving an approximate traveling salesman problem. In order to showcase our algorithm, we implement a multi-robot auto-scanning system. Since our method is computationally efficient, we can easily run it in real time on commodity hardware, and combine it with online RGB-D reconstruction approaches. In our results, we show several real-world examples of large indoor environments; in addition, we build a benchmark with a series of carefully designed metrics for quantitatively evaluating multi-robot autoscanning. Overall, we are able to demonstrate high-quality scanning results with respect to reconstruction quality and scanning efficiency, which significantly outperforms existing multi-robot exploration systems.

Considering the fact that points of interest on 3D shapes can be discriminated from a geometric perspective, it is reasonable to map the geometric signature of a point $p$p to a probability value encoding to what degree $p$p is a point of interest, especially for a specific class of 3D shapes. Based on the observation, we propose a three-phase algorithm for learning and predicting points of interest on 3D shapes by using multiple feature descriptors. Our algorithm requires two separate deep neural networks (stacked auto-encoders) to accomplish the task. During the first phase, we predict the membership of the given 3D shape according to a set of geometric descriptors using a deep neural network. After that, we train the other deep neural network to predict a probability distribution defined on the surface representing the possibility of a point being a point of interest. Finally, we use a manifold clustering technique to extract a set of points of interest as the output. Experimental results show superior detection performance of the proposed method over the previous state-of-the-art approaches.

We propose to synthesize feasible caging grasps for a target object through computing Caging Loops, a closed curve defined in the shape embedding space of the object. Different from the traditional methods, our approach decouples caging loops from the surface geometry of target objects through working in the embedding space. This enables us to synthesize caging loops encompassing multiple topological holes, instead of always tied with one specific handle which could be too small to be graspable by the robot gripper. Our method extracts caging loops through a topological analysis of the distance field defined for the target surface in the embedding space, based on a rigorous theoretical study on the relation between caging loops and the field topology. Due to the decoupling, our method can tolerate incomplete and noisy surface geometry of an unknown target object captured on-the-fly. We implemented our method with a robotic gripper and demonstrate through extensive experiments that our method can synthesize reliable grasps for objects with complex surface geometry and topology and in various scales.

This paper proposes a novel method for decorating 3D surfaces using a new type of vector graphics, called Poisson Vector Graphics (PVG). Unlike other existing techniques that frequently require local/global parameterization, our approach advocates a parameterization-free paradigm, affording decoration of geometric models with any topological type while minimizing the overall computational expenses. Since PVG supports a set of simple discrete curves, it is straightforward for users to edit colors and synthesize geometry details. Meanwhile, the details could be organized by Poisson Region (PR), leading to much smoother decoration than those of Diffusion Curve (DC). Consequently, it is an ideal tool to create smooth relief. It may be noted that, DC is adequate to create sharp or discontinuous results. But PR is superior to DC, supporting level-of-details editing on meshes thanks to its smoothness. To render PVG on meshes efficiently, we develop a Poisson solver based on harmonic B-splines, which could be constructed using geodesic Voronoi diagram . Our Poisson solver is a local solver for rendering with more flexibility and versatility. We demonstrate the efficacy of our approach on synthetic and real-world 3D models.

We present an automatic algorithm for subtractive manufacturing of freeform 3D objects using high-speed machining (HSM) via CNC. A CNC machine operates a cylindrical cutter to carve off material from a 3D shape stock, following a tool path, to "expose" the target object. Our method decomposes the input object's surface into a small number of patches each of which is fully accessible and machinable by the CNC machine, in continuous fashion, under a fixed cutter-object setup configuration. This is achieved by covering the input surface with a minimum number of accessible regions and then extracting a set of machinable patches from each accessible region. For each patch obtained, we compute a continuous, space-filling, and iso-scallop tool path which conforms to the patch boundary, enabling efficient carving with high-quality surface finishing. The tool path is generated in the form of connected Fermat spirals , which have been generalized from a 2D fill pattern for layered manufacturing to work for curved surfaces. Furthermore, we develop a novel method to control the spacing of Fermat spirals based on directional surface curvature and adapt the heat method to obtain iso-scallop carving. We demonstrate automatic generation of accessible and machinable surface decompositions and iso-scallop Fermat spiral carving paths for freeform 3D objects. Comparisons are made to tool paths generated by commercial software in terms of real machining time and surface quality.

We present a new graph-based method, called discrete geodesic graph (DGG), to compute discrete geodesics in a divide-and-conquer manner. Let M be a manifold triangle mesh with n vertices and 𝜀 > 0 the given accuracy parameter. Assume the vertices are uniformly distributed on the input mesh. We show that the DGG associated to M has 𝑂 ⁡ ( 𝑛 √ 𝜀 ) edges and the shortest path distances on the graph approximate geodesic distances on M with relative error 𝑂 ⁡ ( 𝜀 ) . Computational results show that the actual error is less than 0.6 ε on common models. Taking advantage of DGG's unique features, we develop a DGG-tailored label-correcting algorithm that computes geodesic distances in empirically linear time. With DGG, we can guarantee the computed distances are true distance metrics, which is highly desired in many applications. We observe that DGG significantly outperforms saddle vertex graph (SVG) – another graph based method for discrete geodesics – in terms of graph size, accuracy control and runtime performance.

Recent advances in 3D printing have made it easier to manufacture customized objects by ordinary users in an affordable manner, and therefore spurred high demand for more accessible methods for designing and fabricating 3D objects of various shapes and functionalities. In this paper we present a novel approach to model and fabricate surface-like objects composed of connected tiles, which can be used as objects in daily life, such as ornaments, covers, shades or handbags.

Filigrees are thin patterns found in jewelry, ornaments and lace fabrics. They are often formed of repeated base elements manually composed into larger, delicate patterns. Digital fabrication simplifies the process of turning a virtual model of a filigree into a physical object. However, designing a virtual model of a filigree remains a time consuming and challenging task. The difficulty lies in tightly packing together the base elements while covering a target surface. In addition, the filigree has to be well connected and sufficiently robust to be fabricated. We propose a novel approach automating this task. Our technique covers a target surface with a set of input base elements, forming a filigree strong enough to be fabricated. We exploit two properties of filigrees to make this possible. First, as filigrees form delicate traceries they are well captured by their skeleton. This affords for a simpler definition of operators such as matching and deformation. Second, instead of seeking for a perfect packing of the base elements we relax the problem by allowing appearance preserving partial overlaps. We optimize a filigree by a stochastic search, further improved by a novel boosting algorithm that records and reuses good configurations discovered during the process. We illustrate our technique on a number of challenging examples reproducing filigrees on large objects, which we manufacture by 3D printing. Our technique affords for several user controls, such as the scale and orientation of the elements.

This article presents a new method to optimally partition a geometric domain with capacity constraints on the partitioned regions. It is an important problem in many fields, ranging from engineering to economics. It is known that a capacity-constrained partition can be obtained as a power diagram with the squared L2 metric. We present a method with super-linear convergence for computing optimal partition with capacity constraints that outperforms the state-of-the-art in an order of magnitude. We demonstrate the efficiency of our method in the context of three different applications in computer graphics and geometric processing: displacement interpolation of function distribution, blue-noise point sampling, and optimal convex decomposition of 2D domains. Furthermore, the proposed method is extended to capacity-constrained optimal partition with respect to general cost functions beyond the squared Euclidean distance.

Shape description and feature detection are fundamental problems in computer graphics and geometric modeling. Among many existing techniques, those based on geodesic distance have proven effective in providing intrinsic and discriminative shape descriptors. In this article we introduce a new intrinsic function for a three-dimensional (3D) shape and use it for shape description and geometric feature detection. Specifically, we introduce the intrinsic girth function (IGF) defined on a 2D closed surface. For a point p on the surface, the value of the IGF at p is the length of the shortest nonzero geodesic path starting and ending at p . The IGF is invariant under isometry, insensitive to mesh tessellations, and robust to surface noise. We propose a fast method for computing the IGF and discuss its applications to shape retrieval and detecting tips, tubes, and plates that are constituent parts of 3D objects.

In many graphics applications, the computation of exact geodesic distance is very important. However, the high computational cost of existing geodesic algorithms means that they are not practical for large-scale models or time-critical applications. To tackle this challenge, we propose the Parallel Chen-Han (or PCH) algorithm, which extends the classic Chen-Han (CH) discrete geodesic algorithm to the parallel setting. The original CH algorithm and its variant both lack a parallel solution because the windows (a key data structure that carries the shortest distance in the wavefront propagation) are maintained in a strict order or a tightly coupled manner, which means that only one window is processed at a time. We propose dividing the CH's sequential algorithm into four phases, window selection, window propagation, data organization, and events processing so that there is no data dependence or conflicts in each phase and the operations within each phase can be carried out in parallel. The proposed PCH algorithm is able to propagate a large number of windows simultaneously and independently. We also adopt a simple yet effective strategy to control the total number of windows. We implement the PCH algorithm on modern GPUs (such as Nvidia GTX 580) and analyze the performance in detail. The performance improvement (compared to the sequential algorithms) is highly consistent with GPU double-precision performance (GFLOPS). Extensive experiments on real-world models demonstrate an order of magnitude improvement in execution time compared to the state-of-the-art.

Many applications of wireless sensor networks involve monitoring a time-variant event (e.g., radiation pollution in the air). In such applications, fast boundary detection is a crucial function, as it allows us to track the event variation in a timely fashion. However, the problem becomes very challenging as it demands a highly efficient algorithm to cope with the dynamics introduced by the evolving event. Moreover, as many physical events occupy volumes rather than surfaces (e.g., pollution again), the algorithm has to work for 3-D cases. Finally, as boundaries of a 3-D network can be complicated 2-manifolds, many network functionalities (e.g., routing) may fail in the face of such boundaries. To this end, we propose Localized Boundary Detection and Parametrization (LBDP) to tackle these challenges. The first component of LBDP is UNiform Fast On-Line boundary Detection (UNFOLD). It applies an inversion to node coordinates such that a “notched” surface is “unfolded” into a convex one, which in turn reduces boundary detection to a localized convexity test. We prove the correctness and efficiency of UNFOLD; we also use simulations and implementations to evaluate its performance, which demonstrates that UNFOLD is two orders of magnitude more time- and energy-efficient than the most up-to-date proposal. Another component of LBDP is Localized Boundary Sphericalization (LBS). Through purely localized operations, LBS maps an arbitrary genus-0 boundary to a unit sphere, which in turn supports functionalities such as distinguishing interboundaries from external ones and distributed coordinations on a boundary. We implement LBS in TOSSIM and use simulations to show its effectiveness.

This paper presents Texture Brush, an interactive interface for texturing 3D surfaces. We extend the conventional exponential map to a more general setting, in which the generator can be an arbitrary curve. Based on our extended exponential map, we develop a local parameterization method which naturally supports anisotropic texture mapping. With Texture Brush, the user can easily specify such local parameterization with a free-form stroke on the surface. We also propose a set of intuitive operations which are mainly based on 3D painting metaphor, including texture painting, texture cloning, texture animation design, and texture editing. Compared to the existing surface texturing techniques, our method enables a smoother and more natural work flow so that the user can focus on the design task itself without switching back and forth among different tools or stages. The encouraging experimental results and positive evaluation by artists demonstrate the efficacy of our Texture Brush for interactive texture mapping.

In this paper, we propose a sketch-based editable polycube mapping method that, given a general mesh and a simple polycube that coarsely resembles the shape of the object, plus sketched features indicating relevant correspondences between the two, provides a uniform, regular, and user-controllable quads-only mesh that can be used as a basis structure for subdivision. Large scale models with complex geometry and topology can be processed efficiently with simple, intuitive operations. We show that the simple, intuitive nature of the polycube map is a substantial advantage from the point of view of the interface by demonstrating a series of applications, including kit-basing, shape morphing, painting over the parameterization domain, and GPU-friendly tessellated subdivision displacement, where the user is also able to control the number of patches in the base mesh by the construction of the base polycube.

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.

Although the problem of k-area coverage has been intensively investigated for dense wireless sensor networks (WSNs), how to arrive at a k-coverage sensor deployment that optimizes certain objectives in relatively sparse WSNs still faces both theoretical and practical difficulties. In this paper, we present a practical algorithm LAACAD (Load balancing k-Area Coverage through Autonomous Deployment) to move sensor nodes toward k-area coverage, aiming at minimizing the maximum sensing range required by the nodes. LAACAD enables purely autonomous node deployment as it only entails localized computations. We prove the convergence of the algorithm, as well as the (local) optimality of the output. We also show that our optimization objective is closely related to other frequently considered objectives. Therefore, our practical algorithm design also contributes to the theoretical understanding of the k-area coverage problem. Finally, we use extensive simulation results both to confirm our theoretical claims and to demonstrate the efficacy of LAACAD.

Computing discrete geodesics on polyhedral surfaces plays an important role in computer graphics. In contrast to the well-studied "single-source, all-destination" discrete geodesic problem, little progress has been reported to the all-pairs geodesic, i.e., computing the geodesic distance between arbitrary two points on the surface. To our knowledge, the existing all-pairs geodesic algorithms have very high computational cost, thus, can not be applied to real-world models, which usually contain thousands of vertices. In this paper, we propose an efficient algorithm to approximate the all-pairs geodesic on triangular meshes. The pre-processing step takes O(mn2 log n) time for the input mesh with n vertices and m samples, where m (≪ n) is specified by the user, usually between a few hundred and several thousand. In the query step, our algorithm can compute the approximate geodesic distance between arbitrary pair of points (not necessarily mesh vertices) in O(1) time. Furthermore, the geodesic path and the geodesic distance field can be approximated in linear time. Both theoretical analysis and experimental results on real-world models demonstrate that our algorithm is efficient and accurate. We demonstrate the efficacy of our algorithm on the interactive texture mapping by using discrete exponential map.

Closed geodesics, or geodesic loops, are crucial to the study of differential topology and differential geometry. Although the existence and properties of closed geodesics on smooth surfaces have been widely studied in mathematics community, relatively little progress has been made on how to compute them on polygonal surfaces. Most existing algorithms simply consider the mesh as a graph and so the resultant loops are restricted only on mesh edges, which are far from the actual geodesics. This paper is the first to prove the existence and uniqueness of geodesic loop restricted on a closed face sequence; it contributes also with an efficient algorithm to iteratively evolve an initial closed path on a given mesh into an exact geodesic loop within finite steps. Our proposed algorithm takes only an O(k) space complexity and an O(mk) time complexity (experimentally), where m is the number of vertices in the region bounded by the initial loop and the resultant geodesic loop, and k is the average number of edges in the edge sequences that the evolving loop passes through. In contrast to the existing geodesic curvature flow methods which compute an approximate geodesic loop within a predefined threshold, our method is exact and can apply directly to triangular meshes without needing to solve any differential equation with a numerical solver; it can run at interactive speed, e.g., in the order of milliseconds, for a mesh with around 50K vertices, and hence, significantly outperforms existing algorithms. Actually, our algorithm could run at interactive speed even for larger meshes. Besides the complexity of the input mesh, the geometric shape could also affect the number of evolving steps, i.e., the performance. We motivate our algorithm with an interactive shape segmentation example shown later in the paper.

A wireless sensor network becomes dynamic if it is monitoring a time-variant event (e.g., expansion of oil spill in ocean). In such applications, on-line boundary detection is a crucial function, as it allows us to track the event variation in a timely fashion. However, the problem becomes very challenging as it demands a highly efficient algorithm to cope with the dynamics introduced by the evolving event. Moreover, as many physical events occupy volumes rather than surfaces (e.g., oil spill again), the algorithm has to work for 3D cases. To this end, we propose UNiform Fast On-Line boundary Detection (UNFOLD) to tackle the challenge. The essence of UNFOLD is to inverse node coordinates such that a "notched" surface is "unfolded" into a convex one, which in turn reduces boundary detection to simple convexity test. UNFOLD is uniform as every node behaves the same (performing coordinate inversion and convexity test), and it is super fast as both computation and communication involve only one-hop neighbors. We prove the correctness and efficiency of UNFOLD; we also use simulations and implementations to evaluate its performance, which demonstrates that UNFOLD is 100 times more time and energy efficient than the most up-to-date proposal.

In this paper we propose an editable polycube mapping method that, given an arbitrary high-resolution polygonal mesh and a simple polycube representation plus optional sketched features indicating relevant correspondences between the two, provides a uniform, regular and artist-controllable quads-only mesh with a parameterized subdivision scheme. The method introduces a global parameterization, based on a divide and conquer strategy, which allows to create polycube-maps with a much smaller number of patches, and gives much more control over the quality of the induced subdivision surface. All this makes it practical for real-time rendering on modern hardware (e.g. OGL 4.1 and D3D11 tessellation hardware). By sketching these correspondence features, processing large-scale models with complex geometry and topology is now feasible. This is crucial for obtaining watertight displaced Catmull-Clark subdivision surfaces and high-quality texturing on real-time applications.

Sampling plays an important role in a variety of graphics applications. Among existing sampling methods, Poisson disk sampling is popular thanks to its useful statistical property in distribution and the absence of aliasing artifacts. Although many promising algorithms have been proposed for multi-dimensional sampling in Euclidean space, very few research studies have been reported with regard to the problem of generating Poisson disks on surfaces due to the complicated nature of the surface. This still remains a challenge due to the following reasons: first, a surface is a two-dimensional manifold that has arbitrary topology and complicated geometry, and is embedded in R3 or even higher dimensional space. Second, the exact geodesic distance should be used to enforce the minimum distance constraint between any pair of samples. Third, the algorithm should be parallelized such that it can make full use of all available threads. Last but not least, the generated samples should be randomly and uniformly distributed on surfaces, and exhibit the blue noise pattern without bias. Wei [2008] pioneered a parallel Poisson disk sampling algorithm by subdividing the sample domain into grid cells and drawing samples concurrently from multiple cells that are sufficiently far apart to avoid conflicts. Bowers et al. [2010] extended Wei's algorithm to 3D surfaces. Their method is highly efficient, allowing sampling on large-scale models at interactive speed. However, the generated distribution is not fully random since the sequence of processing the phase groups follows a predefined order. Moreover, the approximate geodesic computation in their approach results in large errors in models with rich features and thus compromises the sampling quality.

Geodesic plays an important role in geometric computation and analysis. Rather than the widely studied single source all destination discrete geodesic problem, very little work has been reported on the all pairs geodesic distance query So far, the best known result is due to Cook IV and Wenk [2009], who pre-computed the pairwise geodesic between any two mesh vertices in O(n52α(n) logn) time complexity and O(n4) space complexity, where n is the number of mesh vertices and α(n) the inverse Ackermann function. Then the geodesic distance between any pair of points on the mesh edges can be computed in O(m + logn) time, where m is the number of edges crossed by the geodesic path. Although Cook IV and Wenk's algorithm is able to compute the exact geodesic the high computational cost limits its applications to real-world models which usually contain thousands of vertices.

A 3D burr puzzle is a 3D model that consists of interlocking pieces with a single-key property. That is, when the puzzle is assembled, all the pieces are notched except one single key component which remains mobile. The intriguing property of the assembled burr puzzle is that it is stable, perfectly interlocked, without glue or screws, etc. Moreover, a burr puzzle consisting of a small number of pieces is still rather difficult to solve since the assembly must follow certain orders while the combinatorial complexity of the puzzle's piece arrangements is extremely high. In this paper, we generalize the 6-piece orthogonal burr puzzle (a knot) to design and model burr puzzles from 3D models. Given a 3D input model, we first interactively embed a network of knots into the 3D shape. Our method automatically optimizes and arranges the orientation of each knot, and modifies pieces of adjacent knots with an appropriate connection type. Then, following the geometry of the embedded pieces, the entire 3D model is partitioned by splitting the solid while respecting the assembly motion of embedded pieces. The main technical challenge is to enforce the single-key property and ensure the assembly/disassembly remains feasible, as the puzzle pieces in a network of knots are highly interlocked. Lastly, we also present an automated approach to generate the visualizations of the puzzle assembly process.

The computation of geodesic distances or paths between two points on triangulated meshes is a common operation in many computer graphics applications. In this article, we present an exact algorithm for the single-source all-vertices shortest path problem. Mitchell et al. [1987] proposed an O ( n 2 log n ) method (MMP), based on Dijkstra's algorithm, where n is the complexity of the polyhedral surface. Then, Chen and Han [1990] (CH) improved the running time to O ( n 2 ). Interestingly Surazhsky et al. [2005] provided experimental evidence demonstrating that the MMP algorithm runs many times faster, in practice, than the CH algorithm. The CH algorithm encodes the structure of the set of shortest paths using a set of windows on the edges of the polyhedron. Our experiments showed that in many examples over 99% of the windows created by the CH algorithm are of no use to define a shortest path. So this article proposes to improve the CH algorithm by two separate techniques. One is to filter out useless windows using the current estimates of the distances to the vertices, the other is to maintain a priority queue like that achieved in Dijkstra's algorithm. Our experimental results suggest that the improved CH algorithm, in spite of an O ( n 2 log n ) asymptotic time complexity, greatly outperforms the original CH algorithm in both time and space. Furthermore, it generally runs faster than the MMP algorithm and uses considerably less space.