CS Paper Radar

Fast Construction of Inner Sphere Trees Using Machine Learning

Jianneng Huang, Wenjia Rao

cs.LG cs.RO ·submitted 2026-10-08 03:06 UTC · v1
benchmark

Abstract

Collision detection for complex non-convex objects is a bottleneck in physics simulation, virtual reality, and robotics. Inner sphere trees (ISTs) answer proximity and penetration queries efficiently, but their greedy leaf-sphere construction is sequential and computationally expensive, which limits both large-scale preprocessing and runtime use. In this work, we present ML-IST, a machine-learning-based method that reformulates leaf-sphere generation as a single-shot set-prediction problem: a network predicts a fixed set of inscribed sphere candidates from multichannel voxel geometry, differentiable coverage feedback corrects the coarse prediction and fills residual gaps at finer scales, and a lightweight geometric projection enforces validity. Averaged over the test set, a single-GPU implementation of ML-IST reduces mean leaf-generation time by a factor of $2.0$--$2.6$ over single-core CPU construction across target capacities of 64--512 spheres, and qualitative results on complex models show multiscale sphere distributions that follow principal volumes and slender features. We further integrate ML-IST into the Jolt Physics and Bullet engines; in an alpha-puzzle benchmark it reaches 55.89~FPS, the highest among the compared representations (conventional IST, GImpact, and convex decomposition). These results support learned leaf generation as a practical component for fast, runtime construction of detailed collision representations.

Comment
11 pages, 7 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Low-Latency Mapless ESDF Queries for MAV Reactive Collision Avoidance

cs.RO ·2026-10-09 ·Leonard Freißmuth, Cedric Le Gentil, Helen Oleynikova, Stefan Leutenegger
similarity 0.62
Abstract · 8 pages, 11 Figures

Reactive collision avoidance in unknown, cluttered environments must perceive obstacles and correct motion within milliseconds. Existing methods rely on maps for high-rate collision queries, but their acceleration structures require pre- processing. That cost is amortized in long-horizon planning, where a map serves millions of queries; reactive planning, however, is a near-field, short-horizon problem with potentially only hundreds of queries per measurement, where building a map may not pay off. We propose a mapless, Graphics Processing Unit (GPU)-accelerated Euclidean Signed Distance Field (ESDF) query with negligible pre-processing that operates directly on posed depth images, with resolution set by pooling the image rather than by a voxel size. On an embedded GPU it is simultaneously more accurate and lower in total latency than every voxel-grid configuration we measured between 2 cm and 20 cm, at one to two orders of magnitude less memory at matched resolution. With our query integrated into a Model Predictive Controller (MPC), simulated runs in laser-scanned forests at up to 9 m/s collide in 0.4 % through dense branches, against 5.9 % with the best voxel grid and 5.5 % with the best mapless baseline at our resolution, whose failures we attribute to voxel resolution and total latency respectively. We deploy the system onboard at two forest sites and fly at commanded speeds of up to 4 m/s.

0.32

CollisionSplatting: Collision-Aware Motion Planning in 3DGS Scenes with Image-Conditioned Objectives and Adjustable Conservatism

cs.RO ·2026-09-28 ·R. Khorrambakht, Joaquim Ortiz-Haro, Stephan Weiss, Ludovic Righetti
similarity 0.61
Abstract

Incorporating dense visual information into motion planning remains challenging, as geometric planners rely on abstracted scene representations that discard visual richness, while learned visual models often lack geometric interpretability and computational efficiency. This paper introduces CollisionSplatting, a simple, modular, GPU-accelerated, probability-inspired distance metric with tunable conservatism that operates directly on standard 3D Gaussian Splatting (3DGS) scenes. When combined with learned image-conditioned reward functions, this metric enables joint geometric and visual planning by unifying collision-aware costs with image-space objectives. We integrate the metric into GPU-accelerated Model Predictive Path Integral (MPPI) and Rapidly-Exploring Random Tree (RRT) planners, and show on-par or better collision-classification performance compared to representative baselines while achieving substantially higher collision-checking throughput and significantly lower VRAM usage. Finally, we demonstrate the effectiveness of our metric in real-world vision-guided navigation and manipulation tasks, highlighting 3DGS as a practical bridge between rich perception and real-time motion planning.

0.18

Lodos: A Lightweight Simulator Designed for Contact-Rich Interactions with Detailed Meshes

cs.RO ·2026-11-06 ·Onur Beker, Andreas René Geist, Georg Martius
code/data similarity 0.61
Abstract

In recent years, massively parallelized rigid-body simulation has played a central role in robotics research, enabling rapid progress in areas such as reinforcement learning, stochastic optimal control, and randomized smoothing-based trajectory optimization. Particularly in contact-rich settings, the scalability of such simulations in large part depends on well-optimized representations of collision geometry, often requiring a coarse approximation of the underlying surfaces using primitives such as spheres, capsules, cylinders, and boxes. Whenever the complexity of the surfaces or the precision demands of the application render such approximations insufficient, it is instead necessary to employ mesh-mesh collisions, which impose a significant reduction in throughput. This paper proposes a simulation framework designed from scratch to address this bottleneck, with novel routines for broadphase and narrowphase collision detection as well as the subsequent contact dynamics computation. As experimentally validated, the framework matches existing well-established simulators in terms of physical faithfulness, and can achieve approximately an order of magnitude higher throughput in the detailed mesh-mesh collision setting that it specializes in. The source code is available at https://github.com/martius-lab/lodos.

0.45

CuACD: A Fully GPU-Resident Approximate Convex Decomposition

cs.CG cs.GR ·2026-09-23 ·Ruoxi Shi, Xinyue Wei, Fanbo Xiang, Zexiang Xu, Hao Su
publishedbenchmarkcode/data similarity 0.59
Abstract

Approximate convex decomposition (ACD) converts triangle meshes into small sets of convex parts and is a standard preprocessing step for physics simulation, collision detection, and large-scale robot learning. The majority of modern ACD methods produce high-quality decompositions through an expensive search over candidate cutting planes, with per-mesh runtimes of tens of seconds that force game pipelines into overnight bakes and keep articulated-object datasets on CPU clusters for days. Prior work has accelerated isolated stages, most recently VisACD's GPU-based visibility metric, yet the dominant costs -- search, mesh cutting, and convex hull construction -- have remained on the CPU because their natural decomposition into many small homogeneous phases trails off in a fading last wave at every kernel boundary, and the variable-sized output of each phase forces a host round trip simply to allocate the next launch's input. We address these obstacles by adopting the warp, rather than the thread or thread block, as the unit of algorithm design, an idea introduced in the graph-processing community for a different pathology and which we adapt here to fuse the many heterogeneous phases of a computational-geometry pipeline into single warp-resident kernels, paired with a device-side heap allocator that lets the buffers between fused phases be sized and allocated on the device. Building on this template, we present CuACD (CUDA ACD), the first fully GPU-resident ACD system, together with a suite of reusable GPU components, released as open-source standalone CUDA modules that drop into any search-based ACD pipeline. On the V-HACD benchmark, PartNet-Mobility, and an Objaverse subset, CuACD achieves more than an order of magnitude of speedup over CoACD at matched or better quality.

0.73

Dandelion: A Spherical Flower for Neural Simulation of Planetary Dynamics

cs.LG ·2026-08-27 ·Till Muser, Giovanni Abati, Ivan Dokmanić
benchmark similarity 0.59
Abstract

Many dynamical processes unfold on the sphere but the default scientific machine learning architectures are Euclidean. Applying these architectures on a regular lat-lon grid causes problems: Cartesian convolutions become distorted at high latitude; 2D FFTs in Fourier neural operators incorrectly assume double periodicity; Cartesian positional encodings in ViTs distort spherical geodesic distances. Recent work moves towards natively spherical primitives, including spherical convolutions (e.g., DeepSphere or DISCO), Spherical Fourier Neural Operators (SFNOs), and geodesic attention. Here we propose Dandelion, a spherical version of Flower, a warp-based neural PDE solver. Layers of Dandelion predict a tangent-plane displacement and transport features along great circles. We obtain a U-Net-like structure by implementing hierarchical pooling entirely in the spherical-harmonic domain. There are thus no convolutions: spatial mixing is achieved only through spherical coordinate changes, or warps. To compare Dandelion with existing spherical architectures, we release an evolving benchmark suite of challenging, natively-spherical PDE datasets including a modified Galewsky jet, anomalous chained turbulence, Cahn-Hilliard decomposition, spherical Riemann shocks, Held-Suarez dry atmospheric transport and global ocean dynamics. This new benchmark fills the gap in existing spherical datasets which are either too small and stylized, or much too large (ERA5) for model iteration. Dandelion is best or second-best on every dataset, and the gap to non-warp baselines widens with resolution: at $256\times 512$, Dandelion and Flower2D occupy the top two slots in both single-step prediction and rollout.

0.32

JoVox: Joint Hierarchical Flow Matching for Lightweight Voxel Generation

cs.CV cs.GT ·2026-11-07 ·Xiangjun Tang, Jianqi Chen, Peter Wonka
similarity 0.58
Abstract

Generating high-fidelity voxels while keeping their lightweight nature remains an open problem in computer vision. Current generators are either high-fidelity but computationally heavy, or lightweight but of lower fidelity. Hierarchical methods keep the lightweight nature of voxels. However, their coarse levels, which decide where all finer cells can appear, are generated with the least information about the shape and are never revisited, so they are often plausible but wrong. Our key insight is to let finer cells take part in deciding coarse cells. To this end, we propose JoVox, a discrete flow matching framework that learns the joint distribution of all levels of the voxel hierarchy, instead of a separate distribution for each level, so that coarse cells can be predicted with finer cells already generated nearby. Within this framework, we further introduce a two-level prediction, which outputs the cells two levels finer at once instead of one level finer, halving the number of levels that the network processes and yielding voxels of higher fidelity. We also introduce an unmasking strategy that revisits early decisions once finer cells are generated and corrects inconsistencies in masked diffusion models. Our framework outperforms the baselines on both unconditional and image-conditioned voxel generation. Compared with the current state-of-the-art TRELLIS.2, we achieve 8x higher training throughput, 1/15 of the FLOPs in a forward pass, train on 4 vs. 32 GPUs, and obtain higher quality with an 11% lower Chamfer distance.

0.36

ColNav: Uncertainty-Aware Spacetime Collision Checking with Bounding Volume Hierarchies

cs.RO ·2026-11-08 ·Sanjeev Ramkumar Sudha, Lars Ivar Hatledal, Erlend M. Coates
similarity 0.57
Abstract

Safe navigation for mobile robots in dynamic and uncertain environments requires planning paths that avoid collisions with other moving targets. Typically this involves forward propagating the robot motion and checking for collisions at sampled points in space and time. Such methods can miss collisions between sampled points and are not robust to uncertainty in the state estimates. We propose ColNav, a robust collision check formulation with geometric volumes. The key aspect of our approach is encoding the uncertainty in the targets' and the ego robot's positions and velocities into spacetime tubes, in two variants that consume bounded-set and Gaussian uncertainty descriptions, respectively. The tubes are organised in bounding volume hierarchies, so that a single tree traversal covers the entire horizon, rather than testing sampled time instants, and returns a robust geometric certificate together with an estimate of the time to collision. Static and dynamic obstacles share the same representation. Our approach reaches the goal with a 100% success rate under prediction model mismatch, where the best baseline reaches 65%, and maintains up to three times the clearance in dense traffic. We also validate real-time operation on a physical robot.

0.26

Neural Centroidal Voronoi Tessellations

cs.GR ·2026-09-08 ·Jiacheng Xu, Bo Pang, Rui Xu, Xiaocheng Zhang, Yang Liu +3 more
similarity 0.57
Abstract

Centroidal Voronoi tessellation (CVT) is a fundamental primitive for high-quality surface sampling and isotropic remeshing in computer graphics. However, computing surface CVTs with classical solvers remains expensive: each optimization step repeatedly constructs restricted Voronoi diagrams (RVDs) and integrates quantities over their surface cells. We introduce Neural CVT, a learning-based surface-CVT solver that replaces these costly geometric computations with a recurrent neural optimizer, accelerating CVT optimization by one to two orders of magnitude in our benchmarks while preserving geometric fidelity. Given an input surface, we sample a dense point cloud and extract multi-scale geometric descriptors with a graph neural encoder. A lightweight recurrent optimizer then refines seed positions over a small number of iterations, aggregating interpolated surface features and optimization history to predict per-seed displacements. The framework is trained self-supervised using CVT objectives that promote uniform distributions and, when desired, feature alignment. Across diverse organic and CAD-like shapes, Neural CVT generalizes to unseen geometry, initialization strategies, and seed densities, producing isotropic, feature-preserving remeshes comparable to state-of-the-art offline optimization methods at a fraction of the computational cost. Code and trained models will be released.

0.25