computer graphics engineers

Abstract: The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring? In our previous paper [FOCS'26], we presented a simple combinatorial algorithm to 4-color planar graphs in $O(n\log n)$ time. We improve it here to $O(n)$ time, which is optimal. The algorithm from our previous paper is based on proving that every planar triangulation has a linear number of reducible configurations or obstructing cycles. The bottleneck for the algorithm is that we need $O(\log n)$ Kempe changes to extend a recursive 4-coloring to the reducible configurations. Each Kempe change can involve a constant fraction of the graph and takes linear time. Here we show that all $O(\log n)$ Kempe changes can be identified and implemented in $O(n)$ time. The idea is to spend $O(n)$ time to preprocess the graph so that we can identify and simulate each good Kempe change in $O(n/\log n)$ amortized time. Thus, we implement all $O(\log n)$ Kempe changes in $O(n)$ total time. Based on this, we implement the whole 4-coloring in linear time. We note that creating such a representation for fast identification and simulation of the right Kempe changes is a challenge of data structures, unlike the previous paper that builds on a new graph theoretic understanding of reducible configurations.

Abstract: The spatial chromatic model (SCM) is a novel entity-oriented spatial data model proposed in recent years. Spatial tessellations formed by SCM have been applied in preliminary analyses of spatial point pattern recognition,spatial topology, and Voronoi diagram generation. Unlike previous spatial tessellation models, a key feature of SCM is that each subspace (cell) possesses a chromatic code, which serves as the foundation for various theoretical analyses and applications of SCM. The uniqueness of cell cluster codes in SCM constitutes an important property of the model. Previous studies have demonstrated the uniqueness of the chromatic codes of 2-cell and 3-cell connected disjoint clusters. Building on this analysis of connected cluster code characteristics, this paper proves the uniqueness of the chromatic codes of 4-cell connected disjoint clusters. The proof results and the new concepts introduced in this study help further refine the spatial chromatic model and provide a theoretical foundation for its subsequent applications.

Abstract: Symmetric polyconvexity provides a sufficient condition for weak lower semicontinuity in small-strain elasticity and a tractable lower bound for the relaxation of non-(quasi)convex energies. Since classical algorithms for computing such functions can be computationally expensive, neural network approximations have recently emerged as an alternative. A central difficulty with establishing such neural network based approaches for symmetric polyconvexity is the additional monotonicity property. As we show, the corresponding weight restrictions on ReLU-based input-convex networks do not yield universal approximation of the lifted representers. Here, we introduce symmetric polyconvex neural networks (SPCNNs) for constitutive modeling and approximation of symmetric polyconvex envelopes. The deep architecture combines convexity with the monotonicity required of a representer in the space of minors. We prove a universal approximation theorem for symmetric polyconvex energies, without requiring isotropy, and quantify the number of affine pieces attainable by the lifted network and derive reduced architectures for isotropic energies. Numerical examples illustrate stress-based regression and approximation of the symmetric polyconvex envelope of a double-well potential. Symmetric polyconvexity is guaranteed by construction, while the accuracy of the fitted energies and envelopes is assessed numerically.

Abstract: Autoregressive (AR) video diffusion has emerged as a leading paradigm for efficient video generation, yet its practical deployment remains bottlenecked by the trade-off between generation quality and inference efficiency. We attribute this bottleneck to three error sources in AR rollouts: the base model error, the train-inference distribution mismatch, and the upstream error propagation. Building on this decomposition, we derive closed-form upper bounds on the per-step and cumulative errors, providing a principled basis for jointly optimizing generation quality and inference efficiency. Guided by this analysis, we propose TriTD, a Tri-Partite Trajectory-Distribution co-optimized distillation framework with three complementary modules. First, for ODE initialization, we adopt a Next-Node Trajectory Distillation (NTD) objective, which shortens the supervision horizon and admits a lower regression-error floor. Second, we introduce Chunk-Graded Noising (CGN), a monotonically non-decreasing per-chunk noising schedule that helps narrow the expected train-inference noise mismatch and removes redundant KV-cache updates, yielding substantial speedups at no quality cost. Third, we propose Orthogonal-Parallel DMD (OP-DMD), a distribution-matching loss that retains the original DMD supervision while introducing an additional regression constraint in the orthogonal subspace to suppress off-axis drift, improving both training stability and final generation quality. Extensive experiments show that TriTD consistently surpasses existing baselines in visual quality while reaching a real-time throughput of 26.8 FPS on a single H100 GPU, delivering a balanced quality-efficiency solution for interactive streaming video generation.

Abstract: Wang et al.(Computer-Aided Design 40 (2008) 999-1008) proposed a knot-subsequence characterization of full row rank for rectangular B-spline collocation matrices. We identify an incorrect inequality in their Appendix proof, which invalidates the argument as written, and make explicit the endpoint and multiplicity conventions on which the criterion depends. The defect lies in the proof, not in the underlying result, which is valid under suitably stated hypotheses; in the lofting construction of Wang et al. these hypotheses are implicitly satisfied, so the lofted curves are unaffected. We state the corrected result and give a new proof, independent of the disputed argument, for clamped B-splines of arbitrary degree with continuous interior multiplicities. In our proof, sufficiency follows from inclusion of spline spaces and knot insertion; necessity selects independent columns and builds the reduced knot vector from them. The proof uses no recursive column-selection construction.

Abstract: We study the geometric set cover problems of covering and partitioning a polygon into a minimum number of triangles. While the decision version of the covering problem is known to be APX-hard and $\exists\mathbb R$-complete (even for polygons without holes and vertices in general position), the computational complexity of partitioning a simple polygon into a minimum number of triangles is open. Our main result refutes a 40 year old conjecture by Asano, Asano, and Pinter stating that the triangle vertices of a minimum partition lie on intersection points of special lines, which are iteratively generated by the polygon vertices and the intersection points. In particular, we show that there exist polygons where all minimum triangle partitions need Steiner points with irrational coordinates. This indicates that the problem might be more complex than previously expected. Complementarily, we provide a simple constant factor approximation to compute a minimum triangle partition of a given polygon (possibly with holes). In the context of coverings, we devise the first constant factor approximation for computing a minimum triangle cover of a simple polygon. For general polygons, an $O(\log n)$-approximation follows by close inspection of previous work.

Abstract: Given a set $S$ of $n$ points in general position in the plane, we define the $C$-set $C(p,q)$ of an oriented edge $(p,q)$ as the set of extreme points of the visibility set $V(p,q)$ facing $(p,q)$. Since every point of $V(p,q)$ that is not in $C(p,q)$ gives rise to an empty convex pentagon having $(p,q)$ as a boundary edge, it is natural to study the properties of $C$-sets in order to bound the number of empty convex pentagons of $S$. We prove tight bounds on the intersection size and union complexity of $C$-sets sharing an endpoint. We also consider the problem of bounding the number of empty pentagons and hexagons in terms of the number of interior and boundary points of $S$. While the hexagon bound is weak, it offers a potential step toward a superlinear lower bound. On the other hand, the two-parameter bound for pentagons, combined with the structural results on $C$-sets, yields a simple proof of an $Ω(n^{3/2})$ bound for the number of pentagons. While this is a significant improvement over previously published bounds, a recent preprint \cite{Astudillo2026} attains a better bound using completely different methods. Thus, the primary contribution of this paper lies in the structural results about $C$-sets and the two-parameter bounds for empty pentagons and hexagons.

Abstract: Feed-forward Gaussian reconstruction builds 3D scenes directly from input images for novel view rendering, but learning Gaussian attributes from predicted geometry for high-quality rendering under large viewpoint changes remains challenging. We analyze limitations in Gaussian attribute learning and introduce InfiniSplat v2, which improves rendering quality through architectural and training changes. Our method decouples geometry and attribute prediction with a frozen geometry branch, aligns predicted Gaussians using ground-truth camera poses during training, and adopts large-angle target view supervision. Across six datasets, the feed-forward outputs of the same trained model achieve state-of-the-art mean LPIPS and DISTS among the evaluated methods in both pose-conditioned and pose-free settings. In the pose-conditioned setting, mean LPIPS and DISTS decrease by 25.8% and 32.9%, respectively, compared with the strongest evaluated baselines. We further find that opacity learned with only image reconstruction supervision suppresses geometrically inconsistent points. Project page: https://zju3dv.github.io/InfiniSplat2/

Abstract: Learning world models across diverse domains calls for a unified control space, yet ac- tion interfaces vary across domains and action annotations are often scarce. Latent ac- tions learned directly from videos offer a promising way to establish such a space without explicit action supervision. However, learning shared latent actions across domains re- mains challenging, as variations in appearance, embodiment, and dynamics can entangle domain-specific visual cues with transferable transition structure. To this end, we intro- duce OneLA, a simple framework that learns continuous latent actions through a shared orthogonal dictionary and a common predictive objective, without task-specific designs or cross-domain alignment losses during latent action pretraining. These latent actions pro- vide a shared conditioning interface for world models, with lightweight adapters mapping native control commands into the same space. Conditioned on latent actions and the cur- rent visual state, the world model predicts context-dependent transitions for controllable rollout. OneLA improves action readout across domains and reduces action cycle-transfer rotation error by 24.8% over the strongest evaluated baseline. A joint-training comparison further shows a 20.5% improvement in Human Preference Score v3 (HPSv3) for real- scene generation. These results suggest a path toward general-purpose world models that learn from diverse videos and support flexible control through latent action space.

Abstract: Modeling 3D hair strands is challenging due to complex hairstyle geometry, scarce high-quality training data, and incomplete or noisy input observations. Foundation models offer broader hairstyle priors, but their outputs are not directly usable for strand-based rendering and simulation. Existing approaches require costly per-instance optimization to fit hair priors to meshes from foundation models and 2D orientations from specialized predictors trained on limited hair data, restricting efficiency and generalization. We present HairFlow, a multimodal conditioned diffusion framework for efficient and controllable hair strands modeling. HairFlow conditions strand generation on two complementary representations: a coarse mesh that constrains global shape and multi-view sketches that specify local strand flow. HairFlow combines an Orientation VAE with a conditioned diffusion transformer to generate volumetric fields that are traced into explicit strands. To overcome the lack of paired sketch-strand training data, we introduce an automatic synthesis pipeline that generates geometrically aligned multi-view sketches with diverse styles representative of inference-time inputs. Experiments show that HairFlow generates plausible 3D strands that faithfully follow the input conditions across diverse hairstyles, substantially reduces inference time, and supports flexible multimodal control.

Abstract: Differentiable renderers expose the derivative of any scalar objective with respect to every scene parameter, yet unlike the primal image, which decades of arbitrary output variables (AOVs) have taught us to decompose, inspect, and composite, these derivatives have no established representation for human inspection. We introduce the sensitivity AOV, a render output carrying the sensitivity of an objective to the scene parameters that influence it. A single reverse-mode pass populates a sensitivity buffer over the scene's parameter hierarchy, from which many views are read rather than re-differentiated, in direct analogy to deferred shading: image-space sensitivity at object and parameter-type granularity, projections onto a freely navigable scene from any inspection viewpoint, and, for spatially varying parameters, per-texel fields carried to the surface through texture coordinates. We separate the fixed camera that defines the objective from the free camera used to inspect the result, and position reverse-mode attribution against its forward-mode dual. Our aim is not a single algorithm but a scaffolding that establishes derivative outputs as first-class render products alongside the primal image.

Abstract: We study $\varepsilon$-relative approximation of mixed volumes of a fixed number $k$ of full-dimensional convex bodies in $\mathbb{R}^n$, given membership oracles and a known bound $B_n\subseteq K_i\subseteq R_0B_n$. We present a randomized algorithm that estimates any prescribed mixed volume within relative error $\varepsilon$ with probability at least $1-δ$, using polynomially many oracle calls and bit operations in $n$, $\log R_0$, $\varepsilon^{-1}$, and $\logδ^{-1}$ for fixed $k$.

Abstract: This paper presents a novel effective Gaussian Splatting (GS) sequence Compression method that utilizes the Video codec (GSCV). Existing video-based GS sequence compression relies on the Parallel Linear Assignment Sorting (PLAS) and tracked primitive information to convert GS into smooth 2D videos. However, tracked information is not available for most practical applications, and without it, using the vanilla PLAS can generate images exhibiting weak inter-frame correlation, due to its stochastic nature. GSCV incorporates a simple yet efficient Inter-PLAS method to produce close images between the I- and P-frames of GS, enhancing the inter-frame performance of video codec greatly. GSCV also realizes a new pipeline based on the state-of-the-art video codecs with high bit-depth GS images, achieving higher compressibility while simultaneously providing a higher quality upper bound. Experimental results show that the proposed GSCV exhibits obviously improved performance over MPEG video and point cloud-based anchors in GS sequence compression. The code is available at https://github.com/Qi-Yangsjtu/GSCV.

Abstract: Flow matching is central to 3D generation, yet in practice its reinforcement learning (RL) methods are largely adapted from 2D visual generation. Representative DPO-, GRPO-, and NFT-style objectives, when applied to negative trajectories, mainly steer predicted velocities away from the corresponding directions without explicitly specifying a target velocity field toward preferred samples. In 3D generation, constrained by pretrained model capabilities, rollout diversity, and reward-distribution complexity, directly applying these RL methods yields limited gains in geometric quality. We introduce a forward-process RL method \textbf{Dynamic Homing Optimization (DHO)}, which reformulates negative-trajectory optimization as positive-sample attraction-guided dynamic homing. Specifically, Minimum-Cost Attractive Matching (MAM) assigns each negative sample a distinct positive target, and Time-Aware Dynamic Correction (TDC) then redirects its trajectory toward the target using a remaining-time-aware corrective velocity. Building on asynchronous online DHO, we develop \textbf{Flow3D-Pro}, an image-to-3D geometry generation framework. Experiments show that DHO outperforms representative DPO-, GRPO-, and NFT-style objectives in 3D generation, while Flow3D-Pro produces higher-quality 3D geometry than existing mesh generation methods.

Abstract: Distribution matching distillation (DMD) provides a general framework for few-step diffusion generation, but its modern text-to-image instantiations have been developed primarily around latent diffusion. It therefore overlooks key properties and design opportunities of native RGB. We revisit two DMD interfaces for pixel-space teachers. On the teacher-matching side, diagnostics show low-noise RGB matching is dominated by a local-texture cue, motivating a fixed high-noise matching band. On the real-data side, native clean-RGB outputs allow guidance from an external visual representation without traversing a decoder or sharing the heavy fake-score critic. DINO-Adv removes this critic from the adversarial gradient path and supplies local parametric patch guidance. For distribution-level guidance, we introduce AF-Loss, a parameter-free auxiliary semantic distribution-field objective designed for text-to-image DMD. It operates on detached rolling real and generated supports in the shared DINOv2 space while preserving prompt-conditioned teacher supervision. AF-Loss adds no learnable parameters or inference-time computation. Together these designs form DMA$^2$. Across DPG-Bench, GenEval, VQAScore, and COCO30K, the four-step DMA$^2$ student performs better than the 25-step teacher and evaluated few-step distillers.

Abstract: Agricultural robotics is advancing rapidly, yet progress remains constrained by limited field access, lack of control over field conditions, geographic variability, and seasonal crop cycles. These factors make it difficult and costly to acquire diverse agricultural datasets, resulting in limited evaluation and reduced system robustness. While other robotics domains have scaled learning and evaluation through high-fidelity simulation, agricultural robotics still lacks comparably capable tools. In this paper, we present a ROS-integrated framework, built on Isaac Sim, for large-scale procedural generation of agricultural environments. The framework supports photorealistic rendering, physics simulation, and domain randomization at scales relevant to robotics research, with built-in support for row crops, orchards, and vineyards and straightforward extensibility to additional crop categories. Project Page: https://baj31415.github.io/agrigen/

Abstract: The mathematics of Origami have been well studied and shown to develop several interesting results. We use Lean 4 tactics and build on Mathlib to redefine the 7 Huzita operations as theorems instead of axioms and prove their existence. We develop proofs for important origami constructions (such as trisecting an angle), implement origami-constructible numbers and prove the associated Cardano's formula, and formalize Haga's theorem. A Crease Pattern Inspector explores physical folding by providing a full pipeline to create and visualize models constrained by the Huzita formalism. The Lean codebase brings 100+ theorems and lemmas.

Abstract: We prove that every configuration of four through eight points in three-dimensional space, with no four points coplanar, has a connected full geometric flip graph under $2 \leftrightarrow 3$ flips. Every point remains fixed and present throughout the sequence. The proof brings each tetrahedralization into placing form at a convex hull vertex: the tetrahedra not incident to that vertex fill the convex hull of the remaining points. This reduction allows us to establish connectivity by induction, using the connectivity of regular tetrahedralizations. The main geometric tool is radial projection, which turns the tetrahedra incident to a hull vertex into a planar triangulation. When this planar triangulation is regular, varying its lifting heights produces legal spatial flips that progressively shrink the region occupied by the incident tetrahedra and reach placing form. Planar lifting criteria and compatibility constraints between the projections at different hull vertices resolve the remaining small cases. For eight points, at most 35 flips are needed to reach placing form.

Abstract: We present the Variational Incompressible Optimal Transport (VIOT) operator, a generative neural operator for amortized incompressible density transport. Given a new source-target density pair, VIOT predicts a divergence-free velocity field and generates the full transport trajectory by feed-forward inference, replacing the hour-scale per-pair optimization used by adjoint fluid solvers and differentiable simulation baselines. The system consists of three components: a stream-function or vector-potential representation that enforces incompressibility by construction, a regularized incompressible transport objective that balances endpoint accuracy and flow smoothness, and a Fourier Neural Operator backbone that amortizes the solve across new pairs and grid resolutions. Together, these components make incompressible transport a reusable neural operator that facilitates various transport processes. Further, the generative capability extends beyond the training distribution, with VIOT producing incompressible transports for user-drawn source-target pairs in a real-time interactive system. We demonstrate VIOT on 2D and 3D density-transport benchmarks. Both 2D and 3D rollouts complete in seconds per pair, while per-instance baselines in our 2D comparisons optimize each new pair from scratch and require on the order of an hour, a roughly $10^4\times$ online speedup.

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.

Abstract: Diffusion models have shown remarkable performance on diverse generation tasks. Recent work finds that imposing representation alignment on the hidden states of diffusion networks can both facilitate training convergence and enhance sampling quality, yet the mechanism driving this synergy remains insufficiently understood. In this paper, we investigate the connection between self-supervised spectral representation learning and diffusion generative models through a shared perspective on perturbation kernels. On the diffusion side, samples (e.g., images, videos) are produced by reversing a stochastic noise-injection process specified by Gaussian kernels; on the spectral representation side, spectral embeddings emerge from contrasting positive and negative relations induced by random perturbation kernels. Motivated by this, we propose a self-supervised spectral representation alignment method to facilitate diffusion model training. In addition, we clarify how joint spectral learning can benefit diffusion training from a geometric perspective. Furthermore, we find that the optimization of the spectral alignment objective is in an equivalent form of diffusion score distillation in the representation space. Building on these findings, we integrate a spectral regularizer into diffusion training objectives to improve the performance of diffusion models on multiple datasets. Experiments across images and 3D point clouds show consistent gains in generation quality. Code is released at https://github.com/yuehaowang/spectral-reg-diffusion.