Students: Francisco Unai Caja López, Shalom Abebaw Bekele and Sara Ansari
Directed by Jorg Peters and Kyle Lo
1. Introduction
The goal of this project is to design a layout simplification procedure. Following [2], we define an integer-linear programming model to find a set of collapsable arcs, and merge sets of arcs to simplify the layout. The algorithm is part of a bigger research project that is currently carried out by Kyle Lo and Jorg Peters. In said project surfaces are approximated using splines and piece-wise Bezier surfaces [7].
1.1 What is a layout and why do we care about layouts?
Definitions. Consider a graph M = (V,E) of a triangle mesh. For us, a layout is defined as another graph G = (N,A) where N is a subset of V called nodes and A is the set of arcs. Each arc a ∈ A is a polyline that connects two nodes via a sequence of edges from the original triangle mesh. For each node n ∈ N, we define its valence as the number of arcs incident to n. Also, a node is said to be a singularity if it has valence different than 4. Singularities are particularly important in quad layouts, that is, layouts in which all patches are 4-sided. This is because singularities usually lie near important regions and features of the surface. In the following figure you can see an example of a quad layout.
Another important concept in this project is that of a trace. Traces are polylines that begin at a singularity and travel through the layout until they reach another singularity. If we are building a trace and encounter a regular node n, the trace will continue through the opposite arc of n. The following figure shows 5 traces that originate at a particular singularity.
Layouts can describe the global structure of the mesh while also defining a partition. Moreover, layouts play a crucial role in tasks such as quadrangulation and embedding Bezier, or NURBS surfaces.
1.2 Layout generation and the objective of this project
There are various methods for generating quad mesh layouts, such as finding a set of separatrix candidates (i.e. paths connecting pairs of prescribed singularities) in topologically distinct ways, from which a subset is chosen to define a full layout [6]. Another method involves computing a cross-field from a given set of linear PDEs based on an imposed set of singularities. These singularities can occur naturally, for example, by minimizing Ginzburg-Landau energy, or as a user-defined singularity pattern [5]. The interested reader can learn more about layouts and quad meshes in [3].
In this project we are given layouts generated by a modified version of Quadwild [1]. These layouts are generated from triangle meshes. The goal is to find a subgraph of the layout with as few partitions as possible while ensuring that each pair of singularities is separated.
2. Finding collapsable arcs via integer programming
In order to simplify a layout, we first need to figure out which elements are removable. Precisely, we want to know when an arc can be collapsed. To do this, for each arc a ∈ A we define an integer variable qa. We define an integer programming model following [2]. In the paper the layouts are allowed to have T-junctions which makes it so that the variables qa can take any non negative value 0,1,2,… However, this doesn’t happen with the layouts we are working with so, just for this project, we can assume qa is binary and defined as
\(q_a =
\begin{cases}
1 & \text{if arc } a \text{ is collapsable} \\
0 & \text{otherwise}
\end{cases}.\)
2.1. Constraints to enforce properties of the resulting layout
We have two main restrictions.
The resulting layout must be a quad layout
Suppose that we want to collapse arc a in the following figure, then we must also collapse all the arcs a’, a”, … Otherwise, we would have a three sided patch and the result would not be a quad layout.
More generally, if arcs a and a’ lie in the same patch and are opposite to each other, then we must have qa = qa’.
Singularities must remain separate
In general, singularities tend to appear near important features of the mesh or in regions with high curvature. Thus, it makes sense that we try to preserve their locations. We make sure that different singularities aren’t merged together regardless of the number of collapsed arcs. This is done by forcing that any pair of singularities are at a ”positive Manhattan distance”. More precisely, consider two singularities n1, n2 and traces t1, t2 with origin in n1 and n2 respectively. Assume that both traces go through mid node nm, then we must have
\(\sum_{a\in t_1}q_{a} + \sum_{a\in t_2}q_{a} \geq 1.\)
In the following figure we can see an example of a pair of intersecting traces t1 and t2.
And in the following figure we have the set of arcs that links the origin of each trace to the mid node.
One possibility to avoid collapsing two singularities together would be, for each pair of nodes n1, n2, finding intersections of all possible traces t1, t2 and add the previous restriction to the model. In that case, the number of restrictions would be quadratic in the number of nodes. However, the same result can be achieved with far fewer restrictions as is stated in [2].
Notation. For every pair of intersecting traces ti, tj, we denote the first common node as nij. The set of arcs that link the origin on ti with nij is represented by Sij and the total length of those arcs is denoted by lij. Finally, given a trace ti, we define ni* as the intersecting node which is closest to the origin of ti and verifies li* > l*i. The set of arcs that link the origin of ti with ni* will be denoted Si*.
Lemma 1 of [2] asserts that the family of restrictions
\(\sum_{a\in S_{i*}} q_a \geq 1, \quad \text{for every trace }t_i\)
implies the inequality we previously mentioned. Therefore, we can enforce the desired property using O(⎮N⎮) restrictions where ⎮N⎮ is the number of nodes.
Finally, if we just want to collapse as many arcs as possible, we could set the objective function as ∑aqa where the sum is over all arcs. This yields the following linear integer programming model
\(\begin{cases}
\min & \sum_{a}q_a\\
\text{s.t.} & q_a = q_{a’} \text{ whenever } a,a’ \text{ are oposites in the same patch} \\
& \sum_{a\in S_{i*}} q_a \geq 1 \quad \text{for every trace }t_i\\
& q_a\in{0,1} \quad \text{ for every arc } a
\end{cases}\)
Said model will be optimized by Gurobi, a comercial solver. The output is a set of arcs that can be collapsed while maintaining the properties we desire. In the following figure we have in red the collapsable arcs according to an optimal solution to the model
We can see that many of the original arcs are collapsable.
2.2. How do we simplify a layout?
Suppose we have chosen to collapse an arc a, then we will need to collapse a whole set of arcs in order to preserve the quad structure of the layout. This collapse will be done by merging two sets of arcs together. In the following figure we see an example with the arcs to collapse in red and the arcs to merge in purple.
In this project we have chosen to ”move one of the arcs on top of the other” although there are many other choices to do this. In the following figure you can see the simplification procedure.
3. Results and future work
In this project we have learned about layouts and developed a procedure to simplify them iteratively. In addition, solving the integer programming problem has proved to be quite fast (under 0.05 seconds for the examples tested), as the model wasn’t too big. In the following figures you can see the result of applying the simplification several times on two different layouts.
Of course, there are a lot of aspects that can be improved and directions to continue the work
- The code we developed is far from finished. For instance, we run into problems when some of the arcs to collapse are incident to singularities. All of these special cases should be considered and dealt with appropriately.
- Weights could be added to variables in the objective function of the integer programming model. The objective function would look like ∑awaqa. For instance, we could define
where R denotes a set of vertices close to arc a and krp is the principal curvature at vertex r that better aligns with the direction vector of the arc. Then, we could define
\(\qquad \qquad \qquad \qquad \qquad \qquad \qquad w_{b}=\frac{\max_{a}\overline k_{a}-\overline k_{b}}{\max_{a}\overline k_{a}-\min_{a}\overline k_{a}}
\)
The motivation is that we want to preserve arcs that lie in sections with very high curvature. Having a really big patch in the layout that contains very different and intricate details is undesirable. For example, if we wanted to approximate them with splines, then we would need to use a very high degree. Such weighting scheme could be helpful to prevent the creation of such patches.
3. When merging two different arcs, we have chosen to place the new arc in the location of one of the arcs to be merged. Other strategies may be more successful, for instance, we could create a new arc that passes through a region of high curvature. This could help align arcs with features.
4. After the layout simplification, a smoothing procedure like [8] could be applied on all arcs to improve the quality of the results.
Finally, we would like to thank Justin Solomon for giving us such a wonderful opportunity by organizing SGI 2023 as well as Jorg Peters and Kyle for guiding us through this project.
References
[1] Pietroni, N., Nuvoli, S., Alderighi, T., Cignoni, P., & Tarini, M. (2021). Reliable feature-line driven quad-remeshing. ACM Transactions on Graphics (TOG), 40(4), 1-13.
[2] Lyon, M., Campen, M., & Kobbelt, L. (2021). Quad layouts via constrained t-mesh quantization. Computer Graphics Forum, 40(5), 305-314.
[3] Campen, M. (2017). Partitioning surfaces into quadrilateral patches: A survey. Computer Graphics Forum, 36(2), 567-588.
[4] Schertler, N., Panozzo, D., Gumhold, S., & Tarini, M. (2018). Generalized motorcycle graphs for imperfect quad-dominant meshes. ACM Transactions on Graphics (TOG), 37(6), 1-14.
[5] Jezdimirovic, J., Chemin, A., Reberol, M., Henrotte, F., & Remacle, J. F. (2021). Quad layouts with high valence singularities for flexible quad meshing. Retrieved from https://internationalmeshingroundtable.com/assets/papers/2021/08-Jezdemirovic.pdf
[6] Razafindtazaka, F. H., Reitebuch, U., & Polthier, K. (2015). Perfect matching quad layouts for manifold meshes. Computer Graphics Forum, 34(5), 219-228.
[7] Peters, J., Lo, K., & Karčiauskas, K. (2023). Algorithm 1032: Bi-cubic splines for polyhedral control nets. ACM Transactions on Mathematical Software (TOMS), 49(1), 1-12.
[8] Field, D. A. (1988). Laplacian smoothing and Delaunay triangulations. Communications in Applied Numerical Methods, 4(6), 709-712.