AlgoHex Publications
-
Quad Mesh Quantization Without a T-Mesh
Grid preserving maps of triangulated surfaces were introduced for quad meshing because the 2D unit grid in such maps corresponds to a sub-division of the surface into quad-shaped charts. These maps can be obtained by solving a mixed integer optimization problem: Real variables define the geometry of the charts and integer variables define the combinatorial structure of the decomposition. To make this optimization problem tractable, a common strategy is to ignore integer constraints at first, then to enforce them in a so-called quantization step. Actual quantization algorithms exploit the geometric interpretation of integer variables to solve an equivalent problem: They consider that the final quad mesh is a sub-division of a T-mesh embedded in the surface, and optimize the number of sub-divisions for each edge of this T-mesh. We propose to operate on a decimated version of the original surface instead of the T-mesh. It is easier to implement and to adapt to constraints such as free boundaries, complex feature curves network etc.
@article{quantization-without-tmesh, author = {Coudert-Osmont, Yoann and Desobry, David and Heistermann, Martin and Bommes, David and Ray, Nicolas and Sokolov, Dmitry}, title = {Quad Mesh Quantization Without a T-Mesh}, journal = {Computer Graphics Forum}, doi = {https://doi.org/10.1111/cgf.14928}, } -
Min-Deviation-Flow in Bi-directed Graphs for T-Mesh Quantization
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} }
