Back to search

University of British Columbia

Discrete optimization problems in geometric mesh processing

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Vining, Nicholas William Edward
Contributors dc:contributor
  • Sheffer, Alla

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/86347

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Vining, Nicholas William Edward. Discrete optimization problems in geometric mesh processing. doctoral thesis, University of British Columbia, 2023. http://hdl.handle.net/2429/86347