This paper tackles the task of learning to generate signals over triangle meshes in a triangulation-agnostic manner, meaning the trained model can be applied to different meshes and triangulations effectively. Practically, the paper adapts the flow matching (FM) paradigm to a mesh-based, triangulation-agnostic setting. Theoretically, it proposes a specific noise distribution which is triangulation agnostic, to be used inside the FM model's denoising process. While noise distributions are usually trivial to devise for, e.g., images, devising a triangulation-agnostic distribution proves to be a much more difficult task. We formulate a mathematical definition of triangulation agnosticism of distributions, via their spectrum. We then show that a discretization of a specific Gaussian random field called a Matérn process holds these desired properties, and provides a simple and efficient sampling algorithm. We use it as our noise model, and adapt FM to the triangulation-agnostic setting by using a state-of-the-art approach for learning signals on meshes in the gradient domain—PoissonNet—as the denoiser. We conduct experiments on elaborate tasks such as sampling elastic rest states, and generating poses of humanoids. Our method is shown to be capable of producing highly realistic results for meshes of over one million triangles, significantly exceeding the state-of-the-art in quality and diversity.
论文检索
输入标题、作者或关键词，从 14,945 篇学术成果中精准定位
We developed a new data structure for the efficient representation of spatial data, called SCom DAG — Similarity Compressed Directed Acyclic Graph. It subdivides space with an octree and utilizes local data similarities and topology for compact encoding. Our method exploits the fact that many surface and volume areas are similar to each other up to a transformation. We store spatial transformations on the edges of the graph and data transformations on terminal links pointing to data blocks. Compression is achieved mainly by reducing the number of graph nodes and data blocks while maintaining the same number of paths in the graph. Spatial transformations are compact due to the use of hyper-octahedral groups that are relatively small even in 4D space. SCom DAG works with data of different dimensionality, such as 2D textures, 3D meshes and 4D time-varying volumetric data. Thus, it is well suited for volumetric data visualization and rendering large scenes. The proposed algorithm performs lossy compression, creating a compact representation of various data with controlled quality, which is especially valuable for low-end devices and convenient browser use. It provides a balance of compression and quality comparable to state-of-the-art technologies in various domains, such as compact texture and geometry representation, volumetric data, radiance fields, and precomputed 4D volume animations. At the same time, our data structure enables fast sampling and real-time ray tracing, and its hierarchical nature allows for rendering with a continuous level of detail.
Spherical Harmonics (SH) are fundamental mathematical tools for compactly representing low-frequency spherical functions in computer graphics. Evaluating products of SH-represented functions is a core operation in many rendering algorithms and often becomes a major computational bottleneck. Existing SH product methods face two key challenges: insufficient computational efficiency, and the inflexible requirement that all input functions share the same SH order. To overcome these limitations, we introduce the Generalized Spherical Harmonics Product, a novel formulation that supports inputs with different SH orders and allows flexible truncation of the output. We further propose an efficient and practical computation approach based on Spherical Grids (SphGrid). We establish explicit bidirectional conversions between SphGrid representations and SH coefficients, thus enabling SphGrid to serve as an intermediate representation. Under this framework, SH product computation is reduced to simple point-wise multiplications on the grid. We then derive sufficient conditions on the grid resolution to guarantee exact computation. Using lower resolutions yields an approximate variant that provides a favorable trade-off between accuracy and efficiency. Our approach is not only more general but also demonstrates superior performance even for the specialized case of identical input orders. In particular, our accurate method achieves a 3.5–6.0× speedup over the state-of-the-art method in a practical setting for graphics, while our approximate variant yields lower errors and a 2.5–6.5× speedup over the state-of-the-art approximate method. We rigorously analyze the correctness and efficiency of our method and demonstrate its effectiveness in real-time rendering applications.
We introduce the PhaseTree, a novel hierarchical construction-tree representation for compactly modeling volumetric objects composed of multiple phases or materials across scales. An object is defined as a single construction tree that combines phase-aware primitives through composition and warping operators, yielding a unified multiphase signed distance representation that naturally supports complex topologies and interfaces between phases. The PhaseTree is compatible with standard signed distance field workflows: single-phase algorithms can be directly promoted to a PhaseTree, and conversely reduced without loss of information. As a result, our model integrates seamlessly with existing algorithms and rendering pipelines. We extend classical Sphere Tracing to robustly handle multiphase configurations and show that, despite the additional expressiveness, our implementation preserves the compactness and resolution independence of signed distance fields and incurs less than a 25% runtime overhead compared to single-phase Sphere Tracing.
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 pi is the nearest neighbor of a query q in P, then the second nearest neighbor of q must reside either within the prefix set P1:i-1 = [p1, ..., pi-1} or within pi'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 P1: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.
Computing the Hausdorff distance between triangle meshes with guaranteed accuracy is a computationally intensive task. Conventional Branch-and-Bound (B&B) approaches are fundamentally ill-suited for massive parallelism. Their reliance on a global priority queue (PQ) for both best-first scheduling and global termination checks creates a serial bottleneck that prevents scalable performance. We introduce PQ-Free HD, a parallel B&B framework that eliminates this dependency by decoupling the algorithm's termination logic from its scheduling order. This is achieved by relaxing the culling criterion, thereby replacing the priority queue with a contention-free ring buffer, which transforms the execution model from a state-dependent serial search into a high-throughput, asynchronous batch-processing paradigm. The framework consists of four key components: (1) a parallel priority-queue-free B&B paradigm; (2) a hierarchical GPU execution architecture combining batched depth-first scheduling with fused collaborative kernels; (3) a geometrically robust seven-stage culling pipeline featuring novel tests for challenging geometries; and (4) a compact 29-byte procedural task descriptor that achieves an 83.9% memory reduction. Evaluations demonstrate substantial speedups: a median of 71.7× over the state-of-the-art CPU algorithm on general benchmarks, and exceeding 10,000× on challenging CAD models with dense planar structures. The throughput advantage scales super-linearly with problem complexity. We showcase practical value by building a strictly Hausdorff-distance-bounded mesh simplification tool entirely on the GPU. Our work provides a new method for high-throughput, tolerance-controllable B&B-based geometric queries on GPUs. Code and data are available at https://github.com/huzhihao2001/pqfree-hd.
Computing the directed Hausdorff distance between two triangle meshes is a fundamental operation in geometry processing and simulation. While existing certified branch-and-bound (B&B) methods are efficient for well-separated geometry, they can become prohibitively expensive on large models under tight tolerances and near-zero distance configurations where pruning is limited. We present a GPU-accelerated certified B&B algorithm that explicitly maintains enclosing lower and upper bounds on the directed Hausdorff distance and terminates once their normalized gap, measured with respect to the bounding-box diagonal of the source mesh, meets a user-prescribed tolerance. To map the inherently prioritized search to SIMT (single-instruction, multiple-thread) hardware, we replace priority queues and recursion with a sorted, double-buffered wavefront pipeline built from bulk-parallel worklists for bound evaluation, culling, subdivision, and compaction. To mitigate loose bounds on thin primitives while preserving predictable stream behavior, we introduce a fixed-cardinality adaptive subdivision scheme that selectively applies double longest-edge bisection. To remain robust in deep-refinement regimes, we add a resource-aware deferral mechanism that enforces a device-capacity invariant by prioritizing candidates likely to be culled while postponing expensive ones. Finally, we improve numerical robustness under FP32 (single precision) via triangle-local coordinate transforms and other conservative numerical safeguards, and enhance coherence by spatially ordering the active set and traversing the BVH (bounding volume hierarchy) in triangle packets. Under the same stopping tolerance, experiments on an NVIDIA RTX 5090 show that our GPU solver remains numerically consistent with the FP64 CPU baseline, with normalized cross-platform deviation below 0.01% in over 99.9% of cases. Our method achieves millisecond-scale runtimes capable of supporting interactive frame rates, even on models with millions of triangles. Across the comparison set, it delivers throughput speedups of 836× on the Thingi10K/TetWild benchmark (A → B) and 709× on the Thingi10K/Decimation benchmark. Code and data for this paper are available at https://github.com/fhp-transient/gpu-hausdorff.
Generalized winding numbers provide a robust measure of point insidedness for 3D surfaces—whether open, self-intersecting, or non-manifold—and are central to numerous geometry processing tasks. However, existing methods trade off between accuracy and computational efficiency, limiting their use in interactive and large-scale applications. We introduce a new formulation and algorithm for computing generalized winding numbers that is both fast and accurate to arbitrary precision, applicable to meshes and parametric surfaces. Our approach expresses the winding number as the sum of two intuitive geometric quantities: the signed number of ray-surface intersections and a boundary integral over the surface's projection onto the unit sphere. This insight leads to an efficient discretization that avoids expensive surface integrals and spherical arrangements. For meshes, our method achieves average speedups of 22X on a CPU compared to the fastest precise methods and 3X compared to the fastest approximation method, while maintaining full precision. On a GPU, for moderately complex meshes we reach a throughput of 109 queries per second, or 4K generalized winding number slices at 120 FPS (13X faster than a naïve GPU method). For parametric surfaces, our method is on average 5.6X faster than the state-of-the-art method, with the same precision. Our method naturally handles complex topologies and non-manifold inputs. We extensively validate its accuracy, robustness, and time performance. Our code is available at https://github.com/MartensCedric/antipodal.
We revisit the computation of 3D generalized winding numbers, a useful measure for inside-outside classification on triangle meshes with gaps, self-intersections, and open boundaries. At the core of our new method is an analytical reduction of the surface integral that defines the winding number, resulting in a single ray-mesh intersection test and an elementary sum over boundary edges per evaluation. This construction is orders of magnitude more efficient than the state of the art in practice, which we show in an extensive performance benchmark. Conveniently, the method also reduces to the best-available asymptotic complexity in the worst case, and it introduces no approximations apart from floating-point errors. Our algorithm is conceptually simple to understand, straightforward to implement and debug, and it works reliably even on extremely noisy and corrupt input geometry.
Holography offers unique advantages for delivering perceptual realism while preserving compact form factors in VR/AR. Its perceptual quality, however, hinges on encoding rich wavefronts of photorealistic scenes into interference patterns and then incoherently multiplexing the resulting wave fields for perception. Existing CGH paradigms decouple radiance estimation from wave propagation by pre-rendering radiance on discretized scene sectors. This separation between radiometric and wave-optical computation inherently limits the range of focus cues and visual effects that can be faithfully reproduced, including depth- and view-continuity, and physically based material behaviors such as glossy or mirror-like reflection and refraction. We present a physically accurate yet computationally efficient wave optics rendering framework leveraging path tracing to encode full 3D visual cues into phase holograms. Specifically, we employ a Monte Carlo method to solve both the rendering equation and the Rayleigh-Sommerfeld integral simultaneously. Our algorithm is fully compatible with modern graphics techniques and can generate multiple time-multiplexed random holograms with minimal additional time cost via Path Reuse. By employing a fast approximation with an ambient radiance cache, we realize an order of magnitude convergence speed improvement. The resulting coherent wave fields that inherently encode comprehensive visual effects are converted into phase-only holograms under complex-amplitude supervision. Through extensive simulations and experimental validations on a spatial light modulator-based display prototype, we demonstrate faithful holographic reconstructions of natural 3D cues and complex materials, including realistic defocus blur, view-dependent effects, as well as appearance highlights and reflections.
Anisotropic friction is a critical source of propulsion for efficient locomotion of many terrestrial animals. The interplay between animal morphology, control, and anisotropically frictional contact makes designing optimal anisotropic friction for terrestrial locomotion intriguing and challenging. We propose a computational pipeline for co-designing anisotropic friction and controllers of terrestrial robots with diverse morphologies. Our pipeline presents a co-design algorithm that alternates between optimizing direction of anisotropic friction and training a neural network controller to improve the locomotion performance of a given robot morphology. Based on the intuition that controller’s performance does not change significantly when the frictional force differs slightly, we introduce the concept of trust-region into robot co-design, allowing the controller network to continue training from the previous iteration. Our evaluation on various morphologies show that anisotropic friction is critical for terrestrial robot locomotion, and our pipeline is statistically better than current state-of-the-art methods. Furthermore, we reveal that large language models (LLM) constitute a strong baseline for this kind of co-design problems, worth receiving more attention. We demonstrate that co-designing anisotropic friction and control unlocks effective locomotion in various downstream tasks, including locomotion on uneven terrain, navigation in a maze, and object manipulation. To validate our pipeline in the real world, we design and 3D print a variety of scales and systematically measure their anisotropic friction coefficients. Then we construct a multi-link robot with anisotropic scales designed by our pipeline and compare its performance with isotropic scales. Our real-world experiments confirm that isotropic scales are insufficient to support terrestrial robots’ locomotion abilities, and computationally co-designing friction and control enables robots to perform tasks including turning, slithering, and other non-trivial locomotion tasks.
Coordinate-motion assemblies can only be disassembled by the simultaneous motion of multiple parts along distinct paths, providing high structural stability and enabling efficient robotic assembly. Existing examples are largely limited to architectural structures using joint-based connections, or puzzles created through trial-and-error, as the relationship between part geometry and coordinate motion remains poorly understood. Computationally designing such assemblies is challenging because it requires jointly achieving distributed contacts across the entire assembly and a unique coordinate motion for disassembly that rules out other feasible motions. We address this challenge by establishing a theoretical connection between part geometry and unique coordinate motion, enabling us to rigorously verify whether a given assembly admits a unique coordinate motion. Building on this theory, we introduce a two-stage algorithm that optimizes contact interfaces for a target motion and constructs physically feasible part geometries that conform to a user-specified global shape. We demonstrate our approach on models with complex geometries and topologies, including assemblies with large part counts, and validate it through physical fabrication and experiments.
Walk on Spheres algorithms leverage properties of Brownian Motion to create Monte Carlo estimates of solutions to elliptic partial differential equations. We propose a new caching strategy that leverages the continuity of paths of Brownian Motion. Until recently, estimates were constructed pointwise and did not use the relationship between solutions at nearby points within a domain. In the case of Laplace’s equation with Dirichlet boundary conditions, our algorithm has improved asymptotic runtime compared to previous approaches. Our results are achieved by information reuse from a cache of fixed size. We also provide bounds on the performance of our algorithm and demonstrate our approach on example problems of increasing complexity.
We present a fast sparse matrix permutation algorithm tailored to linear systems arising from triangle meshes. Our approach produces nested-dissection-style permutations while significantly reducing permutation runtime overhead. Rather than enforcing strict balance and separator optimality, the algorithm deliberately relaxes these design decisions to favor fast partitioning and efficient elimination-tree construction. Our method decomposes permutation into patch-level local orderings and a compact quotient-graph ordering of separators, preserving the essential structure required by sparse Cholesky factorization while avoiding its most expensive components. We integrate our algorithm into vendor-maintained sparse Cholesky solvers on both CPUs and GPUs. Across a range of graphics applications, including single factorizations and repeated factorizations, our method reduces permutation time and improves the sparse Cholesky solve performance by up to 6.27 ×. Our code is available at https://github.com/BehroozZare/fast-permute.
Gaussian Process Implicit Surfaces (GPIS) represent geometry as a distribution over implicit functions. Modeling an object’s appearance as the expected rendering of a GPIS yields a unified framework that captures diverse light-transport effects including microfacet-like reflections and volumetric scattering. Despite this generality, computing GPIS–ray intersections requires sampling conditional multivariate Gaussian distributions along each ray and remains prohibitively expensive. We introduce an online sampling algorithm that draws these distributions incrementally, and an adaptive marching scheme that takes large steps where the surface is provably absent, minimizing the probability of missed intersections. Together, these ideas reduce rendering MSE by up to 46 × at equal time compared to existing methods.
Photorealistic volume rendering suffers from slow convergence with traditional path tracing algorithms and poses significant challenges for real-time applications. In this paper, we present Multi-feature Radiance Baking Neural Networks (MRBNN), a neural volumetric rendering method that achieves real-time performance by leveraging analytic decomposition of scattering with an efficient learned representation. Our method reformulates in-scattering integral in Volumetric Radiance Transfer Equation to diagonal scaling operator in spherical harmonics spectrum. Building on this formulation, we propose a compact factorized representation with low-rank compression in latent space that replaces costly integration. We then introduce efficient dual-pattern feature sampling and a lightweight neural decoder for fast radiance prediction. With these dedicated designs, MRBNN achieves 4 ∼ 5 × speedup over the state-of-the-art while maintaining high visual fidelity. Moreover, our method addresses key limitations of prior work, including over-illumination artifacts and inability to handle volumes with spatially varying albedo or heterogeneous phase parameters. Extensive experiments demonstrate that our neural baking method can synthesize photorealistic images for complex volumes in a few milliseconds.
We present a training algorithm to mitigate optimization instabilities in small neural networks, like those used in real-time neural shading applications. While large, overparameterized models exhibit predictable convergence, smaller architectures often suffer from high optimization variance: differently initialized models converge to disparate local minima. To reduce these training instabilities, we introduce an optimization approach that utilizes an ensemble of network instances during training. We prune underperforming instances and dynamically resize training batches to maintain wall-clock timings comparable to—or faster than—single-instance training. This strategy allows efficiently exploring the weight space yielding a well-performing model with significantly higher likelihood than optimizing a single instance only. We develop and analyze the algorithm in the context of learning reflectance functions for neural shading. This is a challenging task for small neural models due to the high dynamic range of the target function. In addition to our multi-instance training method, we also revisit the choices of loss functions, activation functions, and input parameterization to further improve quality and training robustness.
This work introduces FilmGPT, an autoregressive transformer designed to address the challenge of video montage – turning a collection of raw, “unwatchable” footage into coherent cinematic sequences. Inspired by language learning in modern LLMs, we train a long-context autoregressive transformer on a large corpus of movies. The aim is to implicitly capture the “grammar” of film directly from data rather than from hand-coded rules. Unlike other generative models, FilmGPT does not generate any new video frames. Instead, at inference time, we introduce a footage-constrained decoding algorithm to select the best next shot from the input raw footage according to the statistical patterns learned from films. We first evaluate these learned statistics directly by using the FilmGPT autoregressive model for next shot prediction on a standard benchmark of shot sequence ordering, outperforming the previous state of the art. We then evaluate our footage-constrained decoding algorithm on the full film editing task via a user study, and find that our FilmGPT-based editing significantly outperforms previous approaches. Finally, we demonstrate the applicability of FilmGPT to a wide range of applications in video montage, from automatic video segment trimming to human-in-the-loop film editing. Please see our supplementary material for qualitative results.
Signed distance fields (SDFs) and their multi-channel variants (MSDFs) are widely recognized as an effective and practical solution for high-quality, real-time vector graphics rendering. However, generating these fields remains a significant CPU-bound bottleneck, limiting their use in dynamic, interactive applications. This paper introduces a novel, GPU-accelerated algorithm that reframes SDF generation as a parallel quadratic stroke rendering problem. By leveraging the GPU’s tessellation and fragment evaluation pipeline, we parallelize distance calculations for every pixel within a stroke’s influence region. We introduce a localized sign-resolution scheme and a shader-based pipeline that merges per-curve distances using efficient atomic operations. Our results demonstrate a substantial speedup over state-of-the-art CPU libraries like MSDFGen and Skia while maintaining comparable visual accuracy. This performance breakthrough enables real-time generation of distance fields for dynamic user interfaces and on-the-fly synthetic data creation.
The Material Point Method (MPM) provides a unified framework for simulating multi-material systems but struggles to allow for the separation of objects. Traditionally, multi-material simulations use a single background grid, which allows for automatic interaction between materials. Since particles of different types receive their velocities by interpolating from a common background grid, they are unable to efficiently separate. This is especially problematic when simulating immiscible fluids such as oil and water; once oil particles and water particles become mixed, they are unable to separate. A common solution is to solve different objects or materials on separate background grids, which allows particles of different materials to move with different velocities and separate. Using separate background grids loses the natural interaction between materials, since materials no longer interact through the background grid. In the case of immiscible fluids, phase separation is driven by thermodynamics and buoyancy. We present a novel method that enables natural buoyancy-driven phase separation in weakly compressible MPM. Our key observation is that compression and pressure do not depend on the type of particle. A local neighborhood of particles is compressed because particles are close together, and they exert pressure because they bump into the particles that are nearby. Correspondingly, we update the deformation gradient from a unified velocity field and use it to compute a unified pressure force. Combined with the use of separate background grids for velocity, this leads to a treatment of immiscible multiphase fluids that naturally separates due to buoyancy forces, even from a fully mixed configuration. We also propose a mixing potential that is capable of driving phase separation caused by thermodynamics even in the absence of gravity. Finally, we propose a novel algorithm for obtaining consistent per-phase level sets for rendering multiphase particle-based fluids.