-
Concurrent Binary Trees for Large-Scale Game Components
Authors:
Anis Benyoub,
Jonathan Dupuy
Abstract:
A concurrent binary tree (CBT) is a GPU-friendly data-structure suitable for the generation of bisection based terrain tessellations, i.e., adaptive triangulations over square domains. In this paper, we expand the benefits of this data-structure in two respects. First, we show how to bring bisection based tessellations to arbitrary polygon meshes rather than just squares. Our approach consists of…
▽ More
A concurrent binary tree (CBT) is a GPU-friendly data-structure suitable for the generation of bisection based terrain tessellations, i.e., adaptive triangulations over square domains. In this paper, we expand the benefits of this data-structure in two respects. First, we show how to bring bisection based tessellations to arbitrary polygon meshes rather than just squares. Our approach consists of mapping a triangular subdivision primitive, which we refer to as a bisector, to each halfedge of the input mesh. These bisectors can then be subdivided adaptively to produce conforming triangulations solely based on halfedge operators. Second, we alleviate a limitation that restricted the triangulations to low subdivision levels. We do so by using the CBT as a memory pool manager rather than an implicit encoding of the triangulation as done originally. By using a CBT in this way, we concurrently allocate and/or release bisectors during adaptive subdivision using shared GPU memory. We demonstrate the benefits of our improvements by rendering planetary scale geometry out of very coarse meshes. Performance-wise, our triangulation method evaluates in less than 0.2ms on console-level hardware.
△ Less
Submitted 2 July, 2024;
originally announced July 2024.
-
Sampling Visible GGX Normals with Spherical Caps
Authors:
Jonathan Dupuy,
Anis Benyoub
Abstract:
Importance sampling the distribution of visible GGX normals requires sampling those of a hemisphere. In this work, we introduce a novel method for sampling such visible normals. Our method builds upon the insight that a hemispherical mirror reflects parallel light rays uniformly within a solid angle shaped as a spherical cap. This spherical cap has the same apex as the hemispherical mirror, and it…
▽ More
Importance sampling the distribution of visible GGX normals requires sampling those of a hemisphere. In this work, we introduce a novel method for sampling such visible normals. Our method builds upon the insight that a hemispherical mirror reflects parallel light rays uniformly within a solid angle shaped as a spherical cap. This spherical cap has the same apex as the hemispherical mirror, and its aperture given by the angle formed by the orientation of that apex and the direction of incident light rays. Based on this insight, we sample GGX visible normals as halfway vectors between a given incident direction and directions drawn from its associated spherical cap. Our resulting implementation is even simpler than that of Heitz and leads to up to systematic speed-ups in our benchmarks.
△ Less
Submitted 12 June, 2023; v1 submitted 8 June, 2023;
originally announced June 2023.
-
Htex: Per-Halfedge Texturing for Arbitrary Mesh Topologies
Authors:
Wilhem Barbier,
Jonathan Dupuy
Abstract:
We introduce per-halfedge texturing (Htex) a GPU-friendly method for texturing arbitrary polygon-meshes without an explicit parameterization. Htex builds upon the insight that halfedges encode an intrinsic triangulation for polygon meshes, where each halfedge spans a unique triangle with direct adjacency information. Rather than storing a separate texture per face of the input mesh as is done by p…
▽ More
We introduce per-halfedge texturing (Htex) a GPU-friendly method for texturing arbitrary polygon-meshes without an explicit parameterization. Htex builds upon the insight that halfedges encode an intrinsic triangulation for polygon meshes, where each halfedge spans a unique triangle with direct adjacency information. Rather than storing a separate texture per face of the input mesh as is done by previous parameterization-free texturing methods, Htex stores a square texture for each halfedge and its twin. We show that this simple change from face to halfedge induces two important properties for high performance parameterization-free texturing. First, Htex natively supports arbitrary polygons without requiring dedicated code for, e.g, non-quad faces. Second, Htex leads to a straightforward and efficient GPU implementation that uses only three texture-fetches per halfedge to produce continuous texturing across the entire mesh. We demonstrate the effectiveness of Htex by rendering production assets in real time.
△ Less
Submitted 12 July, 2022;
originally announced July 2022.
-
Anchor Prediction: A Topic Modeling Approach
Authors:
Jean Dupuy,
Adrien Guille,
Julien Jacques
Abstract:
Networks of documents connected by hyperlinks, such as Wikipedia, are ubiquitous. Hyperlinks are inserted by the authors to enrich the text and facilitate the navigation through the network. However, authors tend to insert only a fraction of the relevant hyperlinks, mainly because this is a time consuming task. In this paper we address an annotation, which we refer to as anchor prediction. Even th…
▽ More
Networks of documents connected by hyperlinks, such as Wikipedia, are ubiquitous. Hyperlinks are inserted by the authors to enrich the text and facilitate the navigation through the network. However, authors tend to insert only a fraction of the relevant hyperlinks, mainly because this is a time consuming task. In this paper we address an annotation, which we refer to as anchor prediction. Even though it is conceptually close to link prediction or entity linking, it is a different task that require developing a specific method to solve it. Given a source document and a target document, this task consists in automatically identifying anchors in the source document, i.e words or terms that should carry a hyperlink pointing towards the target document. We propose a contextualized relational topic model, CRTM, that models directed links between documents as a function of the local context of the anchor in the source document and the whole content of the target document. The model can be used to predict anchors in a source document, given the target document, without relying on a dictionary of previously seen mention or title, nor any external knowledge graph. Authors can benefit from CRTM, by letting it automatically suggest hyperlinks, given a new document and the set of target document to connect to. It can also benefit to readers, by dynamically inserting hyperlinks between the documents they're reading. Experiments conducted on several Wikipedia corpora (in English, Italian and German) highlight the practical usefulness of anchor prediction and demonstrate the relevancy of our approach.
△ Less
Submitted 1 June, 2022; v1 submitted 29 May, 2022;
originally announced May 2022.
-
Bringing Linearly Transformed Cosines to Anisotropic GGX
Authors:
Aakash KT,
Eric Heitz,
Jonathan Dupuy,
P. J. Narayanan
Abstract:
Linearly Transformed Cosines (LTCs) are a family of distributions that are used for real-time area-light shading thanks to their analytic integration properties. Modern game engines use an LTC approximation of the ubiquitous GGX model, but currently this approximation only exists for isotropic GGX and thus anisotropic GGX is not supported. While the higher dimensionality presents a challenge in it…
▽ More
Linearly Transformed Cosines (LTCs) are a family of distributions that are used for real-time area-light shading thanks to their analytic integration properties. Modern game engines use an LTC approximation of the ubiquitous GGX model, but currently this approximation only exists for isotropic GGX and thus anisotropic GGX is not supported. While the higher dimensionality presents a challenge in itself, we show that several additional problems arise when fitting, post-processing, storing, and interpolating LTCs in the anisotropic case. Each of these operations must be done carefully to avoid rendering artifacts. We find robust solutions for each operation by introducing and exploiting invariance properties of LTCs. As a result, we obtain a small $8^4$ look-up table that provides a plausible and artifact-free LTC approximation to anisotropic GGX and brings it to real-time area-light shading.
△ Less
Submitted 24 March, 2022; v1 submitted 22 March, 2022;
originally announced March 2022.
-
Document Network Embedding: Coping for Missing Content and Missing Links
Authors:
Jean Dupuy,
Adrien Guille,
Julien Jacques
Abstract:
Searching through networks of documents is an important task. A promising path to improve the performance of information retrieval systems in this context is to leverage dense node and content representations learned with embedding techniques. However, these techniques cannot learn representations for documents that are either isolated or whose content is missing. To tackle this issue, assuming th…
▽ More
Searching through networks of documents is an important task. A promising path to improve the performance of information retrieval systems in this context is to leverage dense node and content representations learned with embedding techniques. However, these techniques cannot learn representations for documents that are either isolated or whose content is missing. To tackle this issue, assuming that the topology of the network and the content of the documents correlate, we propose to estimate the missing node representations from the available content representations, and conversely. Inspired by recent advances in machine translation, we detail in this paper how to learn a linear transformation from a set of aligned content and node representations. The projection matrix is efficiently calculated in terms of the singular value decomposition. The usefulness of the proposed method is highlighted by the improved ability to predict the neighborhood of nodes whose links are unobserved based on the projected content representations, and to retrieve similar documents when content is missing, based on the projected node representations.
△ Less
Submitted 6 December, 2019;
originally announced December 2019.
-
Perfect Prediction Equilibrium
Authors:
Ghislain Fourny,
Stéphane Reiche,
Jean-Pierre Dupuy
Abstract:
In the framework of finite games in extensive form with perfect information and strict preferences, this paper introduces a new equilibrium concept: the Perfect Prediction Equilibrium (PPE).
In the Nash paradigm, rational players consider that the opponent's strategy is fixed while maximizing their payoff. The PPE, on the other hand, models the behavior of agents with an alternate form of ration…
▽ More
In the framework of finite games in extensive form with perfect information and strict preferences, this paper introduces a new equilibrium concept: the Perfect Prediction Equilibrium (PPE).
In the Nash paradigm, rational players consider that the opponent's strategy is fixed while maximizing their payoff. The PPE, on the other hand, models the behavior of agents with an alternate form of rationality that involves a Stackelberg competition with the past.
Agents with this form of rationality integrate in their reasoning that they have such accurate logical and predictive skills, that the world is fully transparent: all players share the same knowledge and know as much as an omniscient external observer. In particular, there is common knowledge of the solution of the game including the reached outcome and the thought process leading to it. The PPE is stable given each player's knowledge of its actual outcome and uses no assumptions at unreached nodes.
This paper gives the general definition and construction of the PPE as a fixpoint problem, proves its existence, uniqueness and Pareto optimality, and presents two algorithms to compute it. Finally, the PPE is put in perspective with existing literature (Newcomb's Problem, Superrationality, Nash Equilibrium, Subgame Perfect Equilibrium, Backward Induction Paradox, Forward Induction).
△ Less
Submitted 29 January, 2021; v1 submitted 22 September, 2014;
originally announced September 2014.