EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Martin Heistermann, Jethro Warnett, David Bommes

ACM Transactions on Graphics · 2023-08 · 42 (4) · 1-25

DOI: 10.1145/3592437 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Graphics, online erschienen am 26.07.2023. Verfasst von Martin Heistermann und 2 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 62 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 matching in graphs that solves Bi-MDF exactly. Compared to the state-of-the-art QuadWild [Pietroni et al. 2021] 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.

Förderung

  • European Research Council

Zitieren

APA

Heistermann, M., Warnett, J., & Bommes, D. (2023). Min-Deviation-Flow in Bi-directed Graphs for T-Mesh Quantization. ACM Transactions on Graphics, 42(4), 1-25. https://doi.org/10.1145/3592437

Vancouver

Heistermann M, Warnett J, Bommes D. Min-Deviation-Flow in Bi-directed Graphs for T-Mesh Quantization. ACM Transactions on Graphics. 2023;42(4):1-25. doi:10.1145/3592437

BibTeX
@article{Heistermann2023,
  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},
  year = {2023},
  volume = {42},
  number = {4},
  pages = {1--25},
  doi = {10.1145/3592437}
}
Kostenlos starten →