Open Collections

Abstract

Many geometry processing tasks in computer graphics reduce geometric problems to numerical optimization problems by minimizing an energy that captures the geometric properties we seek. These methods often encounter challenges in the presence of complex global geometric constraints that cannot be easily expressed as numerical optimizations. In this work, we augment these approaches with a different class of algorithmic techniques - discrete and combinatorial optimization algorithms - to solve diverse, challenging problems in geometry processing and computer graphics. We first show how generating PolyCube base-complexes for meshes can be expressed as a labeling problem, and how embedding a graph-cut multi-label optimization within a classical hill-climbing local search framework can find suitable labelings that both minimize a local cut energy and satisfy complex geometric constraints. We demonstrate the applicability of this method, PolyCut, to hexahedral meshing, and include a local-global optimization approach for untangling deformed hexahedral elements with minimal or negative scaled Jacobian. We then consider the problem of generating video game levels from a graph description of the level and a set of candidate building blocks, and show how another numerical optimization technique, simulated annealing, can be embedded within a combinatorial backtracking framework to generate valid game level layouts satisfying design requirements. Finally, we consider the problem of texture-space shading, which enables decoupled shading on existing GPU hardware, facilitating amortization of shading over space and time. Existing texture-space shading methods segment input meshes into fixed charts, and generate atlases spanning all or some of these charts; this introduces visible texture seams and perspective distortion, and wastes texture space. We introduce ViewParam, which solves these problems by generating per-frame atlases in real time. We achieve real-time performance entirely on the GPU by formulating chart finding and packing as discrete and combinatorial problems. We compute seamless charts by employing a GPU-based implementation of the classical union-find algorithm, and find approximate solutions to the NP-hard box packing problem by employing a relaxation strategy based on prefix sums and exploiting GPU parallelism. We validate the quality and robustness of ViewParam by shading and rendering challenging scenes with significantly better shading quality than prior methods.