Browsing by Author "Dupuy, Jonathan"

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    Concurrent Binary Trees (with application to longest edge bisection)
    (ACM, 2020) Dupuy, Jonathan; Yuksel, Cem and Membarth, Richard and Zordan, Victor
    We introduce the concurrent binary tree (CBT), a novel concurrent representation to build and update arbitrary binary trees in parallel. Fundamentally, our representation consists of a binary heap, i.e., a 1D array, that explicitly stores the sum-reduction tree of a bitfield. In this bitfield, each one-valued bit represents a leaf node of the binary tree encoded by the CBT, which we locate algorithmically using a binary-search over the sum-reduction. We show that this construction allows to dispatch down to one thread per leaf node and that, in turn, these threads can safely split and/or remove nodes concurrently via simple bitwise operations over the bitfield. The practical benefit of CBTs lies in their ability to accelerate binary-tree-based algorithms with parallel processors. To support this claim, we leverage our representation to accelerate a longest-edgebisection- based algorithm that computes and renders adaptive geometry for large-scale terrains entirely on the GPU. For this specific algorithm, the CBT accelerates processing speed linearly with the number of processors.
  • Thumbnail Image
    Item
    A Halfedge Refinement Rule for Parallel Catmull-Clark Subdivision
    (The Eurographics Association and John Wiley & Sons Ltd., 2021) Dupuy, Jonathan; Vanhoey, Kenneth; Binder, Nikolaus and Ritschel, Tobias
    We show that Catmull-Clark subdivision induces an invariant one-to-four refinement rule for halfedges that reduces to simple algebraic expressions. This has two important consequences. First, it allows to refine the halfedges of the input mesh, which completely describe its topology, concurrently in breadth-first order. Second, it makes the computation of the vertex points straightforward as the halfedges provide all the information that is needed. We leverage these results to derive a novel parallel implementation of Catmull-Clark subdivision suitable for the GPU. Our implementation supports non-quad faces, extraordinary vertices, boundaries and semi-sharp creases seamlessly. Moreover, we show that its speed scales linearly with the number of processors, and yields state-of-the-art performances on modern GPUs.
  • Thumbnail Image
    Item
    A Halfedge Refinement Rule for Parallel Loop Subdivision
    (The Eurographics Association, 2022) Vanhoey, Kenneth; Dupuy, Jonathan; Pelechano, Nuria; Vanderhaeghe, David
    We observe that a Loop refinement step invariably splits halfedges into four new ones. We leverage this observation to formulate a breadth-first uniform Loop subdivision algorithm: Our algorithm iterates over halfedges to both generate the refined topological information and scatter contributions to the refined vertex points. Thanks to this formulation we limit concurrent data access, enabling straightforward and efficient parallelization on the GPU. We provide an open-source GPU implementation that runs at state-of-the-art performances and supports production-ready assets, including borders and semi-sharp creases.
  • No Thumbnail Available
    Item
    Htex: Per-Halfedge Texturing for Arbitrary Mesh Topologies
    (ACM Association for Computing Machinery, 2022) Barbier, Wilhem; Dupuy, Jonathan; Josef Spjut; Marc Stamminger; Victor Zordan
    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.
  • Thumbnail Image
    Item
    Sampling Visible GGX Normals with Spherical Caps
    (The Eurographics Association and John Wiley & Sons Ltd., 2023) Dupuy, Jonathan; Benyoub, Anis; Bikker, Jacco; Gribble, Christiaan
    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 39% speed-ups in our benchmarks.