Many non-photorealistic rendering (NPR) styles, such as feature lines and hatching, are defined by image-space structure inherited from hand-drawn media. While recent path-space formulations like the stylized rendering equation (SRE) enable stylization to interact naturally with light transport, they provide no mechanism for enforcing image-space consistency. We present a conceptual framework for lifting image-space stylizations into path-space in a principled, SRE-compatible manner. Our key observation is that image-space consistency can be achieved by establishing geometrically-driven mappings from image-space to path-space. We demonstrate this through two complementary stylizations: feature lines and tone. For feature line rendering, we introduce a conditional lifting based on partial path-space variation, where a geometric path parametrization is combined with parallel transport to preserve image-space structure under distribution effects. This enables a curvature-aware, stochastic, geometry-driven formulation of line detection that generalizes prior ray-based methods. For tone-based styles, such as hatching and halftone, we propose a canonical lifting anchored to a material-independent mapping, motivated by stationary-phase arguments from wave optics. Its locally invertible approximation enables evaluation of image-space tone fields at arbitrary path vertices while preserving image-space structure under complex light transport. Both methods are implemented as ordinary style functions under the SRE and work with existing estimation and sampling strategies; demonstrating how image-space structure can be preserved within path-space rendering, enabling a broader class of expressive, physically-grounded NPR styles.
论文检索
输入标题、作者或关键词，从 1,694 篇学术成果中精准定位
College of Computing and Data Science, Nanyang Technological University, Singapore Multi-layer perceptrons (MLPs) are a standard tool for learning and function approximation, but they inherently produce globally smooth outputs. Consequently, they struggle to represent functions that are continuous yet intentionally non-differentiable (i.e., functions with prescribed C0 sharp features) without ad hoc post-processing. We present SharpNet, a modified MLP architecture that encodes user-specified sharp features by augmenting the network with an auxiliary feature function defined as the solution to Poisson's equation with jump Neumann boundary conditions. This feature function is evaluated via an efficient local integral and is fully differentiable with respect to the feature locations, allowing us to jointly optimize both the feature locations and the MLP parameters to recover the target function or geometry. This construction provides precise control over where non-differentiability occurs, enforcing the desired C0 behavior at feature locations while preserving smoothness elsewhere. We validate SharpNet on 2D problems and 3D CAD reconstruction, and compare it with several state-of-the-art baselines. In both settings, SharpNet accurately recovers sharp edges and corners while remaining smooth away from them, whereas existing methods tend to blur gradient discontinuities. Qualitative and quantitative results demonstrate the effectiveness of our approach. Our project page, code and models are publicly available at https://sharpnettech.github.io.
Freeform surfaces are popular in architectural design for their expressive aesthetics, yet they remain challenging to fabricate. A common strategy is to approximate them with assemblies of planar polygonal panels in a process we term panelization, enabling cost-effective fabrication from sheet materials such as wood, metal, or glass. Our goal is to compute panelizations that are both geometrically faithful and structurally robust. A two-stage pipeline, i.e. geometric panelization followed by structural optimization, can be effective, but joint optimization may yield better outcomes by letting mechanics influence the panelization itself. The challenges are that the panelization task is inherently combinatorial, and structural objectives depend on stresses that have a complex, global dependence on the geometry and are costly to evaluate. Moreover, improving structural performance must be balanced against preserving the input surface's design intent. To address these challenges, we formulate panelization as a continuous surface flow coupled to stress analysis, by modeling candidates as creased elastic shells. We define a global objective by integrating an arbitrary function of stress over the shell and derive efficient gradients with respect to the surface shape to enable optimization. We further introduce flow terms that better preserve the input shape and show that running BFGS in a Sobolev space substantially outperforms standard BFGS and Sobolev gradient descent. We evaluate our method on architectural models, showing that incorporating stress during panelization yields substantial stress reductions and more robust designs compared to optimizing stress after fixing the panelization.
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 describe a method for computing signed distance to point clouds that allows fast pointwise evaluation at arbitrary spatial resolution. As input, our method takes a point cloud with normals; as output, it provides an analytical parameterization that allows queries of signed distance to the approximate underlying surface at arbitrary points — simultaneously providing reconstruction and distance. Our key idea is to reconstruct shapes by locally fitting point clouds with tori, which have closed-form signed distance functions. Tori are fitted in a feed-forward manner, using a pre-trained network to output per-point curvature and shift parameters. Importantly, our method does not require costly global optimization or spatial discretization, and is easily parallelizable. Underlying our method is a new theory that unifies signed distance with the classic reconstruction methods of winding numbers and Poisson surface reconstruction. We use our method to compute signed distance to point clouds arising from photogrammetry, meshes, 3D Gaussians, and neural implicits. Our method allows point clouds to be used directly in applications, without explicit surface reconstruction: as examples, we take offsets of point clouds, apply morphological and Boolean operations, and directly visualize offset surfaces using sphere tracing.
Representing complex geometry as a displacement function defined over a coarse base mesh enables compact storage and accelerated rendering. The core challenge in converting detailed triangle meshes into this representation is computing base meshes that have as few triangles as possible, while also supporting displacement functions that accurately approximate the input. Accurate approximation requires the supported displacement functions to bijectively map the input surface onto the base with low parametric distortion. We observe that this distortion can be measured by evaluating the pointwise Jacobian of the displacement functions. Our new DJM (Displacement Jacobian Metric)-based base-mesh construction method uses the Jacobian of the displacement functions to guide base mesh computation, enabling us to outperform prior approaches in terms of accuracy to size trade-off. We achieve this goal by proposing a variant of the QEM-based simplification scheme that constrains the displacement mapping between the input and the base to be bijective and low distortion (defined as satisfying a lower bound on the mapping Jacobian). When evaluating and encoding the displacement maps, we avoid unreliable ray-mesh intersections by explicitly storing the mapping between the input mesh and the base throughout the construction process, and use this mapping within a robust inverse barycentric displacement solver to obtain dense base-to-mesh correspondences to assist all computations. We demonstrate DJM to outperform alternative schemes in terms of reconstruction accuracy to size trade-off, and demonstrate its robustness and usability for micromesh based rendering and neural encoding.
Negative sampling plays a critical role in sequential recommendation, providing contrastive signals that enable the model to distinguish between preferred and non-preferred items. Existing methods commonly sample items with top prediction scores from a randomly selected candidate set as hard negatives. However, such methods suffer from: (1) early-stage training failure since introducing hard negatives too early; (2) the lack of a global item view due to scoring only a small candidate subset; and (3) the failure of fine-grained control of learning difficulty due to the fixed top-ranking strategy. To address the above challenges, we propose recall and re-ranking of negative samples for sequential recommendation, i.e., R2NS. The proposed method comprises three phases, including warm-start, global recall, and curriculum re-ranking. Firstly, in the warm-start phase, the recommender is trained with naive uniform negative sampling to establish fundamental capability and avoid introducing hard negatives too early. Then, in the global recall phase, candidate negatives are selected from the whole item space through an efficient max-index approximation method to introduce contrastive signals from a global perspective. Finally, in the curriculum re-ranking phase, a curriculum top-ranking strategy is introduced to dynamically adjust the difficulty of negative samples. Extensive experiments on four real-world datasets, five sequential recommendation backbone models, and two commonly adopted loss functions demonstrate that R2NS significantly outperforms state-of-the-art negative sampling approaches, validating both the effectiveness and generalization capability of R2NS. Our code is available at https://github.com/Lyz103/R2NS.
Real-world temporal graphs are largely driven by sequential dynamics, and edge repetitions are rare. This characteristic has spotlighted a key limitation of existing temporal graph neural networks (T-GNNs): on such graphs, state-of-the-art T-GNNs often achieve less than 70% MRR on link prediction. Two factors drive this shortfall: (1) Memory modules and neighbor co-occurrence encodings in existing T-GNNs often fail since they rely on memorizing exact neighbor identities and on the co-occurrence assumption. (2) Existing T-GNNs are sensitive to abrupt events, which are common in sequential settings that can exceed ten million updates, thereby compromising generalization. To tackle the challenges of sequential dynamics, we propose SeqFilter, a simple yet robust neural network that functions as a composite filter for link prediction on temporal graphs. SeqFilter comprises two modules: a node rhythm memory and a frequency-selective structure encoder. The node rhythm memory shifts the focus from who interacts to when, modeling absolute timestamps with recency awareness to capture each node's interaction rhythm. To model temporal structures in complex sequential dynamics, we propose a frequency-selective structure encoder that amplifies or suppresses specific frequencies in the neighbor spectrum, enabling the effective modeling of local structure correlations. Theoretically, this encoder functions as a cascade of three learnable filters that approximate the optimal linear denoiser, helping capture the underlying structural patterns. Last, SeqFilter fuses the outputs of two modules to generate high-quality node embeddings. Extensive experiments across eight sequential dynamic datasets show that SeqFilter outperforms 11 baselines by an average improvement of 15.82% in MRR while achieving an order of magnitude speedup compared to the frequency-enhanced baseline.
Data powers almost everything we experience on the web today---from the recommendations and ads we see to the AI systems and online marketplaces that shape our digital interactions. The increasing demand for high-quality data has given rise to platforms that facilitate the buying and selling of data. A key practical challenge in such markets is determining how to price data. Competitive equilibrium (CE), a foundational concept in classical market economics, determines prices for rivalrous goods by matching their supply and demand. In this work, we initiate the study of CE in data markets, explicitly incorporating the role of data in improving predictive performance in buyers' utility functions, and the non-rival nature of data by adapting the standard market-clearing condition to allow the simultaneous allocation of data records to multiple buyers. We analyze the existence, structure, and computation of CE in such data markets. We establish that CE always exists, and almost all instances admit a unique and rational equilibrium price vector. In general, however, there could be a non-convex set of prices, which rules out convex-programming approaches for finding a CE. Despite these challenges, we design an FPTAS for computing approximate equilibria using a Walrasian-style price adjustment algorithm. Our framework opens avenues for studying richer buyer utilities under correlated data sellers, and deeper structural and algorithmic aspects of data markets.
We study non-atomic congestion games on parallel-link networks with polynomial latencies. We investigate the power of machine-learned predictions in the design of coordination mechanisms aimed at minimizing the impact of selfishness. Our main results demonstrate that enhancing coordination mechanisms with simple advice on the input rate can optimize the social cost whenever the advice is accurate (consistency ), while only incurring minimal losses even when the predictions are arbitrarily inaccurate (bounded robustness ). Moreover, we provide a full characterization of consistent mechanisms, which holds for all monotone cost functions, and show that our proposed mechanism is optimal with respect to robustness. We further explore the notion of error-tolerance within this context, i.e., we provide an approximation guarantee that degrades smoothly as a function of the prediction error, up to a predetermined threshold, while achieving a bounded robustness.
Online advertising platforms must decide how to allocate multiple ads across limited screen real estate, where each ad's effectiveness depends not only on its own placement but also on nearby ads competing for user attention. Such spatial externalities — arising from proximity, clutter, or crowding — can significantly alter welfare and revenue outcomes, yet existing auction and allocation models typically treat ad slots as independent or ordered along a single dimension. We introduce a new framework for spatial externalities in online advertising, in which the value of an ad depends on both its slot and the configuration of surrounding ads. We model ad slots as points in a metric space, and model an advertiser's value as a function of both their bid and a discount factor determined by the configuration of other displayed ads. Within this framework, we analyze two natural models. For the Nearest-Neighbor model, where the value suppression depends only on the closest neighboring ad, we present a polynomial-time algorithm that achieves a constant approximation for the general case. We show that the allocation rule is monotone and can be implemented as a truthful mechanism. For a structured setting of 2D Euclidean space, we provide a PTAS. In contrast, for the Product-Distance model, where interference is aggregated multiplicatively across all neighbors, we establish a strong (and nearly-tight) hardness of approximation -- no polynomial-time algorithm can achieve any polynomial-factor approximation unless P=NP, via a reduction from Max-Independent-Set. Our results provide a foundation for reasoning about spatial externalities in ad allocation and for designing efficient, truthful mechanisms under such interactions.
We study the problem of fairly allocating m indivisible chores among n agents with additive cost functions. While the maximin share (MMS) is a prominent fairness criterion in theory, exact MMS allocations do not always exist. This has motivated relaxation that guarantees MMS fairness for only a subset of agents, aiming to maximize the number of satisfied agents. However, for chore allocation, guaranteeing most agents their full MMS is trivial but highly unsatisfactory, e.g., overburdening a single agent, which is undesirable in real-world platforms aiming for user retention and satisfaction. To address this, we propose a stronger and more practical notion called α-approximate all-but-one MMS (α-AMMS), which guarantees that n-1 agents receive their full MMS value, while the remaining agent receives an α-approximation. This model reflects common platform design goals, where satisfying the vast majority of users is critical, and near-fairness for the rest is acceptable. We show that there exist α-AMMS allocations, with α = 9/8 for three agents; α = 4/3 for four agents; and α = (n+1)2/4n for n ≥ 5 agents.
Bayesian optimization is widely employed for optimizing complex black-box functions but struggles with the curse of dimensionality. Random embedding, as a dimension reduction strategy, simplifies tasks that possess the effective dimension by optimizing within a low-dimensional subspace. However, determining the effective dimension of a task in advance remains a significant challenge, which influences the selection of the subspace dimensionality and the optimization performance. Traditional methods use fixed subspace dimensions provided by experts or rely on trial and error to estimate subspace dimensions with resources consumed. To this end, this paper proposes an automated random embedding for high-dimensional Bayesian optimization with unknown effective dimension, called Dynamic Shared Embedding Bayesian Optimization (DSEBO). DSEBO starts with a low dimension and switches to a higher subspace if the solutions in the current subspace show preliminary convergence. DSEBO dynamically determines the dimension of the next subspace based on the quality of the solutions in different subspaces and shares the queried solutions with the new subspace for a better initialization. Theoretically, we derive a regret bound for DSEBO and demonstrate that DSEBO can better balance approximation and optimization errors. Extensive experiments on functions with dimensionality of varying magnitudes and real-world tasks with unknown effective dimensions reveal that, compared with state-of-the-art methods, alternating optimization across different subspaces results in significant improvements in high-dimensional optimization, both in terms of optimization regret and time.
We study the optimal design of a self-financing event, a problem that requires balancing the recruitment of costly, positive-value participants with revenue-generating agents who may impose negative values on the event. We introduce a novel two-sided mechanism design framework with plus agents equipped with private costs and positive impact, and minus agents with private values and negative impact upon inclusion in the event, to maximize the overall quality of the event under a budget-balanced (BB) constraint so that the designer does not run a deficit. We conduct a comprehensive study on the theory of optimal event curation on various utility functions. For additive utility, we fully characterize the optimal incentive-compatible Bayesian mechanism under both the ex-ante and ex-post BB constraints. For submodular utility, we propose an ex-ante BB mechanism that achieves a constant-factor approximation to the optimal Bayesian mechanism.
In heuristic search, a well-known technique to speed up search while providing a suboptimality guarantee is to multiply the heuristic function by a weight w > 1. In this paper, we study the theoretical and practical implications of using such a technique in bi-objective heuristic search, a natural academic exercise that has remained unexplored. We introduce Weighted BOA∗ϵ (WBOA∗ ϵ ), a weighted version of the BOA* algorithm, which uses two real parameters: a weight w for the heuristic and an approximation factor ϵ. Higher values of w and ϵ allow for faster computation of approximate Pareto-optimal solution sets. We prove that WBOA∗ ϵ returns a representative solution set containing (w − 1, ϵ)-approximate solutions. We empirically compare it to A*pex, the state-of-the-art approximate bi-objective search algorithm. We find that WBOA∗ ϵ is competitive with A*pex: when using perfect heuristic functions, in road maps WBOA∗ϵ is faster for higher approximation factors, while in grid maps WBOA∗ϵ dominates A*pex. With imperfect heuristic functions, WBOA∗ϵ performs better than A*pex for lower approximation factors, while the opposite is true for larger approximation factors.
It has been shown that a neural network's Lipschitz constant can be leveraged to derive robustness guarantees, to improve generalizability via regularization or even to construct invertible networks. Therefore, a number of methods varying in the tightness of their bounds and their computational cost have been developed to approximate the Lipschitz constant for different classes of networks. However, comparatively little research exists on methods for exact computation, which has been shown to be NP-hard. Nonetheless, there are applications where one might readily accept the computational cost of an exact method. These applications could include the benchmarking of new methods or the computation of robustness guarantees for small models on sensitive data. Unfortunately, existing exact algorithms restrict themselves to only ReLU-activated networks, which are known to come with severe downsides in the context of Lipschitz-constrained networks. We therefore propose a generalization of the LipBaB algorithm to compute exact Lipschitz constants for arbitrary continuous piecewise linear neural networks and p-norms. With our method, networks may contain traditional activations like ReLU or LeakyReLU, activations like GroupSort or the related MaxMin and FullSort, which have been of increasing interest in the context of Lipschitz-constrained networks, or other piecewise linear functions like MaxPool.
We introduce missingness-MDPs (miss-MDPs), a novel subclass of partially observable Markov decision processes (POMDPs) that incorporates the theory of missing data. A miss-MDP is a POMDP whose observation function is a missingness function, specifying the probability that individual state features are missing (i.e., unobserved) at a time step. The literature distinguishes three canonical missingness types: (1) missing completely at random (MCAR), (2) missing at random (MAR), and (3) missing not at random (MNAR). The problem is to compute near-optimal policies for a miss-MDP with an unknown missingness function, given a dataset of action-observation histories. Achieving such optimality guarantees for policies requires learning the missingness function from data, which is infeasible for general POMDPs. To overcome this challenge, we exploit the structural properties of different missingness types to derive probably approximately correct (PAC) algorithms for learning the missingness function. These algorithms yield an approximate but fully specified miss-MDP that we solve using off-the-shelf planning methods. We prove that, with high probability, the resulting policies are ε-optimal in the true miss-MDP. Empirical results confirm the theory and demonstrate superior performance of our approach over two model-free methods.
Fairness k-submodular maximization has attracted increasing interest due to its broad relevance in artificial intelligence and machine learning. However, most existing works are limited to monotone objectives or simple size constraints, while non-monotone settings with richer constraints remain largely unexplored. In this paper, we first introduce a constant-factor approximation algorithm for the problem with a general non-monotone objective function under a matroid constraint. Our approach is built upon a two-stage algorithmic framework. Specifically, we first develop an algorithm that guarantees feasibility with respect to upper fairness bounds only. We then show how this algorithm can be systematically extended to simultaneously enforce fairness bounds, while preserving provable approximation guarantees. Comprehensive experiments on standard benchmark datasets demonstrate that our algorithm achieves competitive objective values while maintaining a favorable balance between fairness guarantees and query complexity efficiency compared to existing state-of-the-art methods.
Accurate estimation of time-varying treatment effects is crucial for optimizing interventions in personalized medicine. However, observational data often contains complex confounding bias and temporal complexities, making counterfactual estimation challenging. We propose Counterfactual Estimation via Temporal-Aware Intervention Networks (TAIN), a novel model that introduces an Intervention-aware Functional Convolution kernel to emphasize the role of treatments and capture complex temporal treatment interactions. TAIN addresses confounding bias from a domain generalization perspective, approximating the unknown target domain using adversarial examples and incorporating Sharpness-Aware Minimization to derive a generalization bound. This approach is more suitable for longitudinal settings compared to existing methods inspired by domain adaptation techniques due to inherent differences between static and longitudinal contexts. Experiments on simulated datasets demonstrate TAIN's superior performance compared to state-of-the-art models for counterfactual estimation over time.
When solving optimization problems under uncertainty with contextual data, utilizing machine learning to predict the uncertain parameters' values is a popular and effective approach. Decision-focused learning (DFL) aims at learning a predictive model such that decision quality, instead of prediction accuracy, is maximized. Common practice is to predict a single scenario representing the uncertain parameters, implicitly assuming that there exists a deterministic problem approximation (proxy) that allows for optimal decision-making. The opposite has also been considered, where the underlying distribution is estimated with a parameterized distribution. However, little is known about when either choice is valid. This paper investigates for the first time problem properties that justify using a certain decision proxy. Using this, we present alternative decision proxies for DFL, with little or no compromise on the complexity of the learning task. We show the effectiveness of presented approaches in experiments on continuous and discrete problems, as well as problems with uncertainty in the objective function and in the constraints.