AlgoHex Publications

Quad Mesh Quantization Without a TMesh
Grid preserving maps of triangulated surfaces were introduced for quad meshing because the 2D unit grid in such maps corresponds to a subdivision of the surface into quadshaped 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 socalled 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 subdivision of a Tmesh embedded in the surface, and optimize the number of subdivisions for each edge of this Tmesh. We propose to operate on a decimated version of the original surface instead of the Tmesh. It is easier to implement and to adapt to constraints such as free boundaries, complex feature curves network etc.
@article{quantizationwithouttmesh, author = {CoudertOsmont, Yoann and Desobry, David and Heistermann, Martin and Bommes, David and Ray, Nicolas and Sokolov, Dmitry}, title = {Quad Mesh Quantization Without a TMesh}, journal = {Computer Graphics Forum}, doi = {https://doi.org/10.1111/cgf.14928}, }

MinDeviationFlow in Bidirected Graphs for TMesh Quantization
Subdividing nonconforming Tmesh layouts into conforming quadrangular meshes is a core component of stateoftheart (re)meshing methods. Typically, the required constrained assignment of integer lengths to TMesh edges is left to generic branchandcut 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 MinimumDeviationFlow Problem in bidirected networks (BiMDF) and demonstrate its use in modeling and efficiently solving a variety of TMesh quantization problems. We develop a fast approximate solver as well as an iterative refinement algorithm based on graph matching that solves BiMDF exactly. Compared to the stateoftheart 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 halfarcbased TMesh quantization formulation extends the feasible solution space to include previously unattainable quad meshes. The BiMDF 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 = {MinDeviationFlow in Bidirected Graphs for TMesh Quantization}, journal = {ACM Transactions on Graphics}, volume = {42}, number = {4}, year = {2023}, publisher = {ACM}, address = {New York, NY, USA}, doi = {10.1145/3592437} }