We present a new method for simplifying the topology of a 3D shape. Unlike existing methods that either remove all topological features or offer indirect control over the target topology, our method aims at exactly preserving the user-prescribed numbers of topological features of each type (e.g., components, handles, and voids), while making minimal geometric changes. Guided by persistent homology, our method removes features with low persistence by performing either cutting or filling. This is achieved by an algorithm for computing candidate cuts and fills that remove only low-persistence features, an efficient algorithm for selecting an optimal subset of candidates by computing a weighted independent set, and an iterative framework that alternates between candidate computation and selection. Our method is shown to be highly successful in achieving the prescribed topology on a large test suite involving many complex 3D shapes and target topologies.
论文检索
输入标题、作者或关键词，从 14,945 篇学术成果中精准定位
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.
We introduce an implicit representation of continuous, bijective, orientation-preserving maps between genus zero surfaces with or without boundary. The distortion of these maps can easily be minimized by optimizing the Ginzburg-Landau functional—a ubiquitous model in physics and differential geometry—leading to a simple algorithm for computing bijective correspondences using only standard tools of the tangent vector field toolbox. The method avoids combinatorial mesh modifications and does not require barrier functions to enforce bijectivity making it more robust to noise and simpler to implement. Moreover, the algorithm does not assume a bijective initialization and can untangle non-bijective correspondences generated by computationally cheaper methods such as functional maps. It supports the use of both landmark points and landmark curves to guide the correspondence. The key idea is that a bijection between surfaces defines a two-dimensional mapping surface sitting inside the four-dimensional product space of the two inputs, and this mapping surface can be stored implicitly as the zero set of a complex section—essentially a complex function defined on the product space. Now the distortion of the map can be optimized by minimizing the area of this mapping surface, which amounts to minimizing the Ginzburg-Landau functional of the complex section. We demonstrate the practical benefits of our method by comparing to state-of-the-art correspondence algorithms and show that our implicit representation offers improved stability and naturally supports constraints that are difficult to enforce with explicit map representations.
The appearance of simulated natural phenomena heavily depends on the way surfaces are textured. However, applying texture maps to dynamic deformable surfaces presents a significant challenge, due to ever-shifting differences in length scales involved. When these surfaces move and advect the texture along with them, their final appearance degrades as deformed regions dramatically distort their texture map. Modifications to the texture directly at the pixel level in response to the deformation may introduce ghosting artifacts and look unnatural. In the real world, the appearance of surface details on a deforming material changes through the interplay of physical processes such as rupturing, exposure of internal structure, or wrinkling. Motivated by these behaviors, in this work we explore how physical principles can guide the texturing methods based on the measure of surface deformation. We present two novel wave-based procedural texturing algorithms which reproduce common physical properties like advection and self-similarity, enabling the plausible animation of deforming objects with extreme texture map distortions. Our algorithms are fully procedural, require no actual physics simulation, and store no state or history of deformation besides the input UV map, making them highly parallelizable on the GPU and efficient enough for real-time applications. We show the versatility of the method by animating physical phenomena with extreme deformations such as flowing lava, stretching putty and outpouring sludge.
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.
We present an algorithm that produces high quality tetrahedral meshes conforming with input polyhedra. Our meshing algorithm is based on Ruppert's Delaunay refinement where convergence is guaranteed thanks to a novel chamfering approach that removes all acute angles from the input. On such a modified input Delaunay refinement produces a Delaunay tetrahedrization where all the faces have bounded angles. The input portions that were removed by the chamfering are re-inserted in this tetrahedrization to achieve exact conformance at the cost of a small number of bad-shaped tetrahedra near the formerly acute input angles. Numerical robustness is guaranteed along all the phases thanks to a clever use of modern indirect geometric predicates and the definition of a new type of implicit point to represent Steiner vertices on the input faces. In practice, our prototype implementation produces meshes having a quality comparable to the state-of-the-art tetgen software: while tetgen fails on 37% of the 3942 valid models in the Thingi10k dataset, our method succeeds on all of them.
We present an algorithm for global knit structure planning that leverages a generalization of power diagrams to triangulated surfaces. This generalization is based on modified geodesic heat kernels and is used to quantize the curl measure of a normalized knitting time function gradient. Knit singularity positions are optimized jointly in a global fashion via an iterative Lloyd-type algorithm, leading to faster and more optimal placement of singularities than prior work, allowing for practical creation of denser knit graphs. In this denser setting, we present singularity ordering constraints that more robustly achieve helix-free knit graphs. The speed and robustness of the method is demonstrated via a diverse array of knits, and a virtual gallery of helix-free knit graphs. We also provide further demonstration of user constraints for knit singularity masking, level set alignment constraints, and apparent seam placement via curl boosting.
3D shapes from scanning, reconstruction, or AI-generated content often lack simple quad mesh layouts—critical for efficient editing and modeling. Existing quad-remeshing techniques typically produce complex layouts with irregular loops, leading to tedious manual cleanup and extensive algorithm tuning. We introduce SQUADGEN, a diffusion-based generative framework that leverages Chart Distance Fields (CDF) to synthesize simple quad layouts on 3D shapes. Our approach addresses two key challenges: (1) the discrete nature of mesh connectivity, which hinders learning, and (2) the scarcity of large-scale datasets with simple quad meshes. To overcome the first, we propose CDF, a continuous surface-based representation enabling effective learning and synthesis of quad layouts. To address the second, we define loop-aware simplicity metrics and construct a large-scale dataset of high-quality quad layouts recovered from public 3D repositories through a robust quad-recovery pipeline. Extensive evaluations across diverse 3D inputs show that SQUADGEN consistently outperforms existing methods, producing robust, artist-friendly simple quad layouts.
Continuous Collision Detection is essential in simulation and modeling for accurately identifying object collisions. While robust CCD techniques have matured for triangle meshes, ensuring floating-point robustness for parametric surfaces remains an open challenge due to their representational complexity and heightened algorithmic sensitivity. In this paper, we present the first floating-point-robust CCD framework for parametric surfaces. Built on the Time-Dependent Inclusion-Based Method (TDIBM), our approach introduces a novel error decomposition strategy that separates coefficient and arithmetic errors, enabling structured analysis and safety guarantees. To rigorously benchmark robustness, we develop a rational-arithmetic-based dataset by inverting the CCD process: we generate exact ground-truth datasets from prescribed collision outcomes. Our construction captures both typical scenarios and near-degenerate cases. We evaluate several CCD algorithms using this benchmark to provide an in-depth analysis. Together, our method and dataset establish a comprehensive foundation for analyzing, benchmarking, and improving floating-point robustness in parametric surface CCD. Code and dataset will be published upon acceptance.
Differentiable path tracing offers a principled route to recovering physical material and lighting parameters, but the combination of high variance and poor numerical conditioning often makes it too brittle to use in practice. This is especially the case when lighting is altogether unknown, or when the scene contains complex light transport effects. Prior work recently showed that the variance reduction provided by a radiance cache can alleviate these challenges. We revisit the combination of inverse rendering and radiance caching with a twist, by introducing a spatial blending field that locally interpolates between the cache and standard unbiased estimators. Recursive application of this idea yields a rich design space of evaluation strategies and inter-estimator consistency losses; we map this space and identify effective components. A surprising property of the resulting algorithm is that it can accurately recover material parameters even when the lighting is not uniquely identifiable from the observations. Our experiments demonstrate significant improvements in speed and robustness over prior work, making a strong case for including radiance caching as a standard component of future physically based inverse rendering systems.
Discrete X-ray tomography reconstructs the internal structure of an object from X-ray projections, assuming that the volume is composed of a discrete set of known materials (e.g., steel, aluminum, and air). This is generally straightforward when many projections are available but becomes increasingly ill-posed as their number decreases. Discrete tomography has been extensively studied over the past five decades, resulting in a range of mature reconstruction algorithms. In this work, we introduce a new reconstruction method that draws inspiration from both classical computed tomography and recent advances in inverse rendering, demonstrating that a remarkably simple gradient-based inversion can significantly surpass the reconstruction quality of standard methods such as SIRT, DART, and TVR-DART. Our method represents each 3D location as a probability distribution over the set of known materials and minimizes a volumetric loss that encourages consistency with the measured projections. It supports nonlinear effects such as volumetric scattering and is simple to optimize and parallelize on compute accelerators. We evaluate our method on challenging 2D and 3D benchmarks, demonstrating superior performance particularly in sparse and limited-angle scenarios, where traditional techniques struggle with ambiguity.
The Walk on Spheres (WoS) algorithm is a mesh-free and highly flexible Monte Carlo method for solving partial differential equations, but its practical applicability is limited by slow O (N-1/2) convergence. While prior variance reduction techniques exploit spatial correlations through integral properties of the PDE, they do not fully utilize the intrinsic Markov structure of the WoS process. We introduce a new variance reduction framework based on reusing intermediate states along each random walk. Leveraging the Markov property, we show that every point visited by a WoS trajectory provides a valid unbiased estimator, but its direct use is hindered by the complex distribution induced by dynamically generated spheres. To resolve this, we propose the Walk on Probes (WoP) algorithm, which replaces dynamic spheres with a set of fixed, pre-distributed spherical probes inside the domain. This converts the intractable distribution of path points into samples on fixed boundaries, enabling efficient evaluation through the Poisson integral formula. We further develop a specialized method that combines control variates with self-normalization to further reduce variance. Together, these components substantially improve sample efficiency while preserving the flexibility of WoS. Code and data for this paper are at https://github.com/USTCGCL-WoS/Walk-on-Probes.
Providing haptic feedback in virtual reality (VR) remains challenging, with active haptic systems often being bulky and expensive, while passive haptics typically require pre-fabricated objects or extensive real-world setup. We present ProXeek, an LLM-based multi-agent system that opportunistically leverages real-world objects as haptic proxies for VR experiences. During VR development, the designers could annotate the virtual interactables with emphasized haptic characteristics using our node-based editing interface. On the user side, end users capture environmental snapshots via commodity VR headset, and the system employs LLM-based multimodal reasoning and multi-objective optimization to match virtual objects with viable physical proxies. Our technical evaluation demonstrates that ProXeek effectively identifies viable proxies, confirming the effectiveness of the algorithmic constraint design in our matching pipeline. Our user study further reveals that the ProXeek-selected physical objects could deliver significantly higher haptic fidelity and enhance presence compared to 3D-printed replicas and visual-only interaction.
JGS2 is a Jacobi-like GPU simulation algorithm. It avoids the overshooting issue by augmenting each subproblem with a perturbation subspace that predicts the global influence of the local solve. The efficiency of JGS2 is due to Cubature-based subspace integration at each subproblem. Being a data-driven method, Cubature requires a set of representative deformed poses that cover deformations likely to occur in the simulation. This requirement is unlikely for high-resolution deformation with rich local details. Therefore, simulation performance and convergence degenerate when Cubature extrapolates. This paper proposes a training-free subspace integration algorithm based on classic Gaussian quadrature (GQ). We leverage the fact that the subproblem's subspace bases can be well-approximated by a low-degree multivariable polynomial, which suggests GQ an excellent candidate for Cubature substitute. To this end, we introduce a novel algorithm that adaptively generates the integration region for each subproblem. As a result, GQ integration can be analytically retrieved without cumbersome data generation and training. We also show how to handle frictional contact by modifying the pre-computed perturbation subspace. The resulting JGS2-GQ framework is more versatile than the vanilla JGS2 method. It is more stable for large and novel deformations, and is free of data generation and expensive training, while maintaining a near second-order convergence that is comparable to Newton. Performance-wise, JGS2-GQ is as efficient as JGS2, which is three orders faster than classic CPU methods and up to two orders faster than classic GPU algorithms. When novel deformation occurs, JGS2-GQ outperforms JGS2 over 50%.
We introduce a high-performance framework for solving nonconvex optimization problems arising in simulation and geometry processing applications. Our framework especially benefits high-dimensional problems whose unknowns are spatial coordinates in ℝd and whose objectives are expressed as a sum of element energies over small stencils. The Hessians of these problems have a block-sparse structure, where the nonzero entries are grouped into dense d × d blocks. Many works have exploited this structure to speed up the Hessian-vector products and nodal smoothers of iterative solvers. In contrast, accelerating direct sparse linear solvers, preferred for applications requiring high accuracy on unstructured grids, has been less explored. Our framework leverages block structure to accelerate all phases of a Newton-type minimization algorithm, from sparsity pattern construction to system assembly, matrix factorization, and solves. A fundamental piece of the framework is BlockCatamari, our highly tuned, block-accelerated multifrontal sparse Cholesky code that achieves significantly faster factorizations than existing direct solvers on shared-memory systems. We combine this solver with our fast parallel Hessian assembly routine, heuristics for conditionally enabling per-element Hessian projections, and strategies for minimizing symbolic factorization re-computations. We show that this leads to dramatic speedups on a large suite of benchmark problems involving injective surface parametrization and elasticity simulation with contact, and we further demonstrate the ease with which new energies can be defined at the different levels of abstraction offered by our framework.
We introduce a spatially discrete formulation of the Schrödinger bridge problem on meshes and grids that enables structure-preserving and scalable interpolation between probability distributions. Our approach builds on the duality between entropy-regularized optimal transport and the log-heat equation, deriving a discrete theory that is compatible with mesh-based finite element discretizations. The resulting Sinkhorn algorithm alternates application of the heat kernel with multiplicative updates to enforce marginal constraints. Compared to interpolation via Wasserstein barycenters, our formulation produces sharper interpolants for a given level of regularization and enforces exact endpoint marginals, in addition to enjoying faster computation. It also scales to high-resolution meshes and finer temporal discretizations, avoiding the prohibitive cost of directly discretizing dynamical transport. We demonstrate our approach across mesh- and grid-based applications, including displacement interpolation, shape interpolation, and color histogram manipulation, highlighting its ability to achieve geometric fidelity with computational efficiency.
We propose a system for differentiating through solutions to geometry processing problems. Our system differentiates a broad class of geometric algorithms, exploiting existing fast problem-specific schemes common to geometry processing, including local-global and ADMM solvers. It is compatible with machine learning frameworks, opening doors to new classes of inverse geometry processing applications. We marry the scatter-gather approach to mesh processing with tensor-based workflows and rely on the adjoint method applied to user-specified imperative code to generate an efficient backward pass behind the scenes. We demonstrate our approach by differentiating through mean curvature flow, spectral conformal parameterization, geodesic distance computation, and as-rigid-as-possible deformation, examining usability and performance on these applications. Our system allows practitioners to differentiate through existing geometry processing algorithms without needing to reformulate them, resulting in low implementation effort, fast runtimes, and lower memory requirements than differentiable optimization tools not tailored to geometry processing.
We present an efficient B-spline finite element method (FEM) for cloth simulation. While higher-order FEM has long promised higher accuracy, its adoption in cloth simulators has been limited by its larger computational costs while generating results with similar visual quality. Our contribution is a full algorithmic pipeline that makes cloth simulation using quadratic B-spline surfaces faster than standard linear FEM in practice while consistently improving accuracy and visual fidelity. Using quadratic B-spline basis functions, we obtain a globally C1-continuous displacement field that supports consistent discretization of both membrane and bending energies, effectively reducing locking artifacts and mesh dependence common to linear elements. To close the performance gap, we introduce a reduced integration scheme that separately optimizes quadrature rules for membrane and bending energies, an accelerated Hessian assembly procedure tailored to the spline structure, and an optimized linear solver based on partial factorization. Together, these optimizations make high-order, smooth cloth simulation competitive at scale, yielding an average 2× speedup over linear FEM in our tests. Extensive experiments demonstrate improved accuracy, wrinkle detail, and robustness, including contact-rich scenarios, relative to linear FEM and recent higher-order approaches. Our method enables realistic wrinkling dynamics across a wide range of material parameters and supports practical garment animation, providing a new promising spatial discretization for high-quality cloth simulation.
While thin shells have ubiquitous applications and have been studied inside and outside computer graphics for decades, there is little consensus on how to best discretize them. We systematically study models for simulating bending of Kirchhoff-Love shells, with the goal of making practical recommendations, backed by careful numerical experiments, of when and how these models should be used. We analyze ten of the most popular discrete bending models in computer graphics for thin-shell simulation, along with new variants that we propose ourselves. We first verify all models on an analytic test benchmark to probe convergence under refinement and mesh-dependence, and then stress-test with a second benchmark that considers behavior at sharp bends. Finally, we test benchmark leaders on a practical suite of challenging large-scale equilibrium and dynamic shell modeling problems, analyzing both full solution behavior and comparative compute costs. We identify leading existing models and their tradeoffs in terms of accuracy and performance. During this analysis we also identify some issues and modeling gaps in the best-performing discrete bending models. We construct new energy model variants to address some of these gaps, as well as formulas and algorithmic tools for their practical simulation, and finally recommend best practices for modeling thin-shell bending.
Simulating heterogeneous multibody systems with both deformable and stiff components remains a challenge for GPU solvers. While Newton-Krylov methods are popular for their matrix-free nature and good GPU compatibility, they often suffer from severe ill-conditioning and slow convergence when handling stiff contacts and material disparities in deformable multibody systems. In this paper, we present Heterogeneous Subspace Corrections (HSC), a novel Newton-CG variant to efficiently simulate such complex systems. HSC decouples the system into two Krylov iterations: a Newton-CG procedure for deformable bodies and a Neumann-based iteration for the affine subsystem. We introduce a GPU-based Adaptive Cross Approximation (ACA) algorithm to exploit the low-rank nature of the coupling matrices, which manages to reduce the overhead of sparse matrix-vector multiplications substantially on the GPU. For the affine subsystem, we propose a dedicated data structure for fast assembling contact Hessians in parallel. A variety of experimental results demonstrate that our framework consistently outperforms existing GPU simulators, achieving convergence rates comparable to direct solvers even in scenes with high-resolution models and extensive stiff contacts.