Parametrizations over abstract quad-mesh domain

A graph of separatricesGover meshQpartitions the surface ofQinto rectangular patches.

Each patch can be easily parameterized over a flat, axis aligned rectangleDi. LetDbe the collection of all D₁, D₂,· · ·D_n, letf :D→Qbe the global parameterization, and φ=f⁻¹ be its inverse.

As we will discuss, D is very appealing in terms of simplicity; moreover, f is aligned by construction to the cross field C⁰ associated with G. These two facts constitute our main motivation for the graph-simplification algorithm of the previous section.

This Section discusses the properties of a parametrization domain of this kind, and shows the operations that can be performed over it, including global smoothing. The operations discussed in this section have the following aim: remove jagged artifacts introduced by the algorithm in 3.2.2; compute a smooth cross field overM (whereas tracing separatrices only defines it along these lines); optimize the placement of singularities and cross points (to comply with the new graph); optionally, recover of lost feature lines.

Even if Q is a quad mesh, in this section it is easier to consider the triangle mesh M obtained from Q by means of diagonal splits. This is no limitation however, because the connectivity of Q is unaffected: edges of M which are quad diagonals ofQ can be tagged as such and the quad connectivity of Q can be recovered at any time.

3.2.3.1 Construction of initial parameterization

As commonplace, a parametrization over M is defined by discretely sampling its inverse, e.g., by assigning an explicit parametric position pi = φ(vi), pi ∈ D to each vertex vi of M. This per-vertex assignment can be propagated, by linear interpolation, over the entire

M, because D allows for interpolations, even for triangles whose vertices are scattered in different patches. The only necessary assumption is that, for a triangle t in M, φ(t) is not so large to span a set of several different domains of D not sharing a vertex (see Sec. 3.2.3.2).

Vertices of M are separated in disjoint groups surrounded by four arcs of the graph G.

Within each group, all vertices are assigned to a different rectangular domainD_i, and each arc surrounding the group is assigned to a corresponding edge of Di.

A vertex v_i is considered a “border” vertex if it shares an edge with any vertex v_j, such thatp_i and p_j belong to different domains. When this happens, the edge separatingp_i and p_j is identified, as well as a parametric position within that edge. Positions p_i and p_j are determined inside their respective domainD_k andD_h, at the corresponding position of the appropriate border of D_k and D_h, respectively.

When parametric positions of all border vertices are set, they are fixed and the positions of non-border vertices are found by applying a single-patch energy-minimization parametriza-tion technique inside every patch. We use [JSW05], but many other methods could be used in its place. This method tends to produce conformal mapping but, due to the shape and size similarities between the D_i and φ(D_i), it also delivers a certain degree of isometry.

The dimensions of Di in parametric space are determined using a separate procedure, described in Sec. 3.2.3.5.

3.2.3.2 Transition functions and interpolation domains

A transition function is associated to each edgej of each domainD_i, consisting of a rotation by a multiple of π/2 and a translation. We call the domain D abstract in the sense that, even if it is endowed with a manifold connectivity (including face-face connectivity and shared vertices), it is not embedded in Euclidean space. Similarly to what is done in [PTC10] for triangular domains, interpolation-domains can be easily defined over D, and they can be employed to allow interpolation between points inDlying in different patches.

An interpolation domainE_iis a 2D region where a set ofkcontiguous patchesD_a1, D_a2,· · ·D_ak are mapped by into one bigger patch, and it is associated with an invertible function g_Ei :∪_j∈(1..k)D_aj →E_a. Functionsg are expressed in closed forms and are easy to evaluate in both ways, mapping each domainD_ai into E_a.

“Edge” interpolation domainsE_i^e unify two adjacent patches ofD over the shared border;

“Vertex” interpolation domainsE_i^v, unifyn patches around a vertex (see Fig. 3.8 left). For domains around edges and regular vertices, the associated function g_i is simply an appro-priate rigid roto-translation. For irregular vertices of valency k, g includes an exponential map (with exponent k/4), which is conformal (see Fig. 3.8 right). For completeness, we

Figure 3.7: Leftmost image: mesh M is partitioned into f(D₁),(D₂),· · · ,(D_n) (each vertex v is coded according to domain φ(v), but triangles connecting fixed vertices are darkened). Other images: the same is repeated using four different set of domains E₁, E₂· · · ,(E_m), partitioning of D. Note that each vertex of M is not a fixed vertices in at least one of the four partitions.

also define a trivial “Face” interpolation domains E_i^f which is identical to a single patch D_i; the associated function g_i is the identity. There is exactly one Edge domain for each shared edge of D, one Face domain for each patch of D, and one Vertex domain for each shared vertex of D.

An interpolation domain allows to interpolate, in parameter space, between a pair of points p₀, p₁ ∈ D, as long as they belong to two domains D₀ and D₁ which share at least one vertex. The interpolation can be computed asg⁻¹_a (I(ga(p0), ga(p1))), whereIis the common interpolation operator (see Fig. 3.8 top).

3.2.3.3 Global smoothing of the parametrization

Another natural use of interpolation domains is the global smoothing of a given parameter-ization. This is done in a sequence of passes. The idea is that, at each pass, some vertices are kept fixed and their positions will not be optimized, but these will be necessarily optimized in subsequent passes.

At each pass, we adopt a different set S={E₀, E₁..E_i}of interpolation domains such that each patch D_i belongs to exactly one interpolation domain. A simple heuristic is adopted to determine set S. Starting from an empty set S, vertex domains E₀^V are inserted into S, only if they are composed by patches not already included in any E_k ∈S. The process is repeated for Edge domains, and finally the isolated domains D_i still not included in an E_k ∈S are inserted as Face domains. Before each pass, we keep a count, for each edge and each vertex of D, of the number of consecutive passes that element lies on the boundary of the interpolation domain embedding it. Such count is used as a priority to select the vertex and face domains.

D

Figure 3.8: Middle: a domainsD composed of patches D₁· · ·D_n, marked by calligraphic uppercase letters. Left, from top: an example of a Vertex, Edge and Face interpolation domain, and associated functions g. Right, from top: other examples of Vertex domain for vertices of D with valency 3 and 5 respectively. Top right: an interpolation domain used to define the interpolation between the two red dots ∈D. The result of the interpolation is the green dot in D.

Figure 3.9: Two semi-regular meshes obtained by resampling the parametric domain Left: parametric domain resulting from the simplification of Fig. 3.4: patches are separated by visibly jagged lines. Right, after multiple session of global smoothing (see Sec. 3.2.3.3), the jagged lines are gone, and irregular points moved to aligned, optimized positions.

For a vertexv_i with associated parametric positionp_i insideD_j, a positionp⁰_i into oneE_k is found byp⁰_i =g_k(p_i). Again, vertices ofM connected by edges of M to vertices in different interpolation domain are fixed, and the other are smoothed locally inside the respective interpolation domain. After the smoothing, vertices are remapped intoDby the functions g_Ei of respective domain, and a new pass is started.

A formal demonstration is omitted for space reasons. A trace is that, at each pass, functions g and their inverse preserve conformal energy, and the smoothing operation monotonically decreases it. Results of this smoothing process is depicted in Fig. 3.10 and 3.9.

3.2.3.4 Recovering lost feature lines

As mentioned in Section 3.2.1, we can choose not to preserve creases in Q (and therefore in M) during the graph simplification. When this is the case, we can demand to the smoothing phase the task of realigning patch borders to the geometric feature of M. Specifically, this can be done when the parametrization is being optimized over a interpo-lation domain. Edges of M tagged as feature edges can be snapped, and then constrained to lie on a 2d straight internal line l=g(e),e being the set of points inDwhich lie on the border of the appropriate patch Di.

3.2.3.5 Isometry

Each 2d rectangle in the domain D is assigned to an extension in each dimension. The dimensions can be chosen to maximize the isometry of mapping f, by solving a system with just two variables. For better results, this process is interleaved to the smoothing passes (Sec. 3.2.3.3), because, during the smoothing, the portion ofM mapped inside each patch of D can vary.