Patch Decomposition for Efficient Mesh Contours Extraction
Patch Decomposition for Efficient Mesh Contours Extraction
Computer Graphics Forum (EGSR), 2024, 43 (4)
- 1Ubisoft
- 2Univ. Bordeaux, CNRS, Bordeaux INP, Inria, LaBRI
Our method decomposes the edges of the “Stanford Bunny” (62k edges) into (a) 3584 patches colored by a palette of 64 colors and bounded by spatialized normal cones, optimized to maximize culling efficiency over arbitrary camera viewpoints. For a given side viewpoint, we show the remaining edges after patch culling in (b) and the extracted mesh contours in (c).
Abstract
Object-space occluding contours of triangular meshes (a.k.a. mesh contours) are at the core of many methods in computer graphics and computational geometry. A number of hierarchical data-structures have been proposed to accelerate their computation on the CPU, but they do not map well to the GPU for real-time applications, such as video games. We show that a simple, flat data-structure composed of patches bounded by a normal cone and a bounding sphere may reach this goal, provided it is constructed to maximize the probability for a patch to be culled over all viewpoints. We derive a heuristic metric to efficiently estimate this probability, and present a greedy, bottom-up algorithm that constructs patches by grouping mesh edges according to this metric. In addition, we propose an effective way of computing their bounding sphere. We demonstrate through extensive experiments that this data-structure achieves similar performance as the state-of-the-art on the CPU but is also perfectly adapted to the GPU, leading to up to x5 speedups.
Paper
Video
Additional Results
Bibtex
@article{tsiapkolis:hal-04620165,
title = {{Patch decomposition for efficient mesh contours extraction}},
author = {Tsiapkolis, Panagiotis and B{\'e}nard, Pierre},
journal = {{Computer Graphics Forum}},
publisher = {{Wiley}},
volume = {43},
number = {4},
year = {2024},
doi = {10.1111/cgf.15154}
}