Jethro Warnett, B.Sc.

Student assistant

AlgoHex Publications

• 

  Min-Deviation-Flow in Bi-directed Graphs for T-Mesh Quantization

  ACM Transactions on Graphics (SIGGRAPH 2023)
  Martin Heistermann, Jethro Warnett, David Bommes

  • Project page
  • Abstract
  • BibTeX

  Subdividing non-conforming T-mesh layouts into conforming quadrangular meshes is a core component of state-of-the-art (re-)meshing methods. Typically, the required constrained assignment of integer lengths to T-Mesh edges is left to generic branch-and-cut solvers, greedy heuristics, or a combination of the two. This either does not scale well with input complexity or delivers suboptimal result quality. We introduce the Minimum-Deviation-Flow Problem in bi-directed networks (Bi-MDF) and demonstrate its use in modeling and efficiently solving a variety of T-Mesh quantization problems. We develop a fast approximate solver as well as an iterative refinement algorithm based on graph matching that solves Bi-MDF exactly. Compared to the state-of-the-art QuadWild implementation on the authors' 300 dataset, our exact solver finishes after only 0.49% (total 17.06s) of their runtime (3491s) and achieves 11% lower energy while an approximation is computed after 0.09% (3.19s) of their runtime at the cost of 24% increased energy. A novel half-arc-based T-Mesh quantization formulation extends the feasible solution space to include previously unattainable quad meshes. The Bi-MDF problem is more general than our application in layout quantization, potentially enabling similar speedups for other optimization problems that fit into the scheme, such as quad mesh refinement.

  @article{Heistermann:2023:BiMDF,
    author = {Heistermann, Martin and Warnett, Jethro and Bommes, David},
    title = {Min-Deviation-Flow in Bi-directed Graphs for T-Mesh Quantization},
    journal = {ACM Transactions on Graphics},
    volume = {42},
    number = {4},
    year = {2023},
    publisher = {ACM},
    address = {New York, NY, USA},
    doi = {10.1145/3592437}
  }