Min-Deviation-Flow in Bi-directed Graphs for T-Mesh Quantization
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.
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}
}
EUVIMED