Topological operators

The most common pattern for uniform subdivision of quad meshes is quadrisection: each face is subdivided into four new faces by splitting each edge with a new vertex, and con-necting each such vertex with another new vertex at the center of the face. In the following, a vertex that splits an edge will be said to be of type E, while a vertex inserted in the middle of a face will be said to be of type F.

Figure 4.6: The diagram of patterns for adaptive subdivision of a quad. Types of faces and patterns are denoted by labels placed inside and beside them, respectively. Transitions between adjacent patterns are labeled with the corresponding refinement and coarsening operators.

Since quadrisection splits all edges of a face, it cannot be applied selectively while main-taining the mesh conforming. In order to support transitions between different levels of subdivision, we devise alternative patterns that split one edge at a time. Figure 4.6 illus-trates such a set of patterns, and related operators. These patterns produce quad-dominant meshes containing some triangular and pentagonal faces, which preserve the flow of lines of the base mesh (see Section 4.2.4 for a discussion). Other patterns, e.g. containing just quads and triangles could be also used with straightforward modifications of the method described below.

A key idea is that local operators subdivide a mesh by splitting one edge at a time, they always produce conforming triangulations, and they can be controlled just on the basis of attributes of local entities, i.e., types and levels of vertices, edges and faces. All rules that control operators are purely topological. Just for the sake of clarity, in the figures we

will use fixed shapes to depict the different types of faces that may appear in our adaptive meshes: squares (type 0); rectangles(type 3); diamonds (type 4); right triangles (type 2); and pentagons with three collinear vertices, having the shape of either a square or a rectangle (type 1 and 5, respectively).

Consider a quad mesh Γ0, called the base mesh. We assign level zero to all its vertices and edges, and type standard to all its edges. A selectively refined mesh will also contain vertices and edges labeled according to their level of subdivision; edges will be labeled with either type standard or type extra. The only extra edges are those internal to patterns P2a and P2b, which have the same level l of their parent face (i.e., face 0 in pattern P0);

the remaining edges are standard and they have level either l or l+ 1, as in the standard subdivision. The level of a face in a mesh Γ is defined to be the lowest among the levels of its edges. Note that the type of a face is uniquely defined by the types and levels of its edges, and the type of a pattern is also uniquely defined by levels of edges in its boundary, as follows:

• Type 0 (also called standard) is a quad with all four edges at the same level (and of standard type);

• Type 1 is a pentagon with three consecutive (standard) edges at level l and two consecutive (standard) edges at level l+ 1;

• Type 2 is a triangle (with one standard edge at level l, one standard edge at level l+ 1 and one extra edge at levell);

• Type 3 is a quad with two non-consecutive edges at level l (one of which is an extra edge) and the other two (standard) edges at levell+ 1;

• Type 4 is a quad with two consecutive (extra) edges at level l and the other two (standard) edges at level l+ 1;

• Type 5 is a pentagon with four (standard) edges at level l and one (standard) edge at levell+ 1.

4.2.1.1 Refinement operators

According to definitions above, all faces in the base mesh are standard at level zero. Local subdivision operators can be applied iteratively to Γ₀ to generate a conforming mesh Γ composed of faces of the six types illustrated in Figure 4.6.

We say that an edgeeat levell ≥0 isrefinable(i.e., it can split) if and only if it is standard and its two adjacent faces f₀ and f₁ are both at level l. In case of a boundary edge, only one such face exists. We split an edgeeat levell, by inserting at its midpoint a new vertex v at level l + 1. The edges generated by the two halves of e are standard at level l + 1.

Note that levels of vertices and standard edges comply with the standard subdivision.

Splitting an edge e at level l may affect an area as large as that of the standard faces incident at e at level l. Tessellations on the two sides of e can be treated independently and each of them depends on the type of the facef incident ate and on its configuration, as explained in the following, and depicted in Figure 4.6:

• 0-split: if f is of type 0, then it is changed into a face of type 1, having its edges of level l+ 1 at the two halves ofe incident at the new vertex v.

• 1a-split: if f is of type 1 and both its edges adjacent to e are at level l, then two faces of type 2 are generated by connectingv to the vertex off opposite to e(which is at level l+ 1). The edge shared by the two new faces is extra and at levell.

• 1b-split: if f is of type 1 and one edgee⁰ adjacent toe is at levell+ 1, then another vertex v⁰ is inserted inside the face and a tessellation composed of one face of type 4 at levell and two faces of type 3 at levell is created; for the sake of brevity, we refer to the figure to describe how this tessellation is made; the new edges inserted inside the face are extra at level l.

• 2a-split: if f is of type 2, then it is necessarily adjacent to another face f⁰ of type 2 through an extra edge opposite to e. Another vertex v⁰ is inserted that splits the extra edge between f and f⁰; f is decomposed into two standard faces at level l+ 1 by connecting v tov⁰; and f⁰ is changed into a face of type 5. The new edges are all standard at level l+ 1.

• 2b-split: if f is of type 3, then it is necessarily part of a tessellation of a standard face at levell, formed byf as well as of another facef⁰ of type 3 and a facef⁰⁰of type 4 placed between f and f⁰. Such three faces are removed and the hole is tessellated with the same pattern described in the previous case;

• 3-split: if f is of type 5, then it is split into two standard faces at level l + 1 by connecting v to the vertex opposite to e with a standard edge at level l+ 1.

It is readily seen from Figure 4.6 that in all cases the type of face f incident at splitting edge e and the levels and labels of edges of f are sufficient to characterize the type of operator to be applied. This fact allows us to pre-compute and store in a lookup table the local tessellations to be deleted from, and to be plugged into a mesh. Note that all split operators affect the whole area covered by a pattern, except for 3-split, which affects just the area covered by face of type 5 in pattern P3. In fact, the other two (standard) faces at level l+ 1 may be actually refined independently at higher levels before this operator is applied.

By simple combinatorial analysis, it is easy to verify that the set of refinement operators is closed with respect to the meshes obtained, i.e.: if we start at a mesh Γ₀ containing all

standard faces at level 0 and we proceed by applying any legal sequence composed of the operators above, the resulting mesh will be composed of faces of the types defined above, and all its refinable edges can be split through the same set of operators. In particular, all vertices of a standard subdivision up to a given level l can be added without adding any vertex of a level higher than l and the same uniform mesh generated from the standard subdivision scheme will be obtained.

If an edge e at level l is of standard type, but it is not refinable, we trigger recursive refinement of each face f incident at e and having a level < l. Recursive refinement is performed by recognizing the type of f and forcing refinement of either two (for pattern P1) or one (for all other patterns) of its edges at level < l.

4.2.1.2 Coarsening operators

Local merge operators invert edge split operators defined above, by removing one vertexv at level l+ 1 that splits an edge e at level l. As before, at most the area spanned by the faces incident at e at level l may be affected, and the tessellations of such two areas are treated independently.

A vertex v at level l+ 1 ispotentially removable if the levels of its incident faces are: l+ 1 for standard faces (type 0), and l otherwise. A potentially removable vertex is removable if it is of type E (i.e., it splits an edge of the previous level) and faces in its neighborhood can be arranged to form two patterns of the diagram, sharing a pair of edges at level l+ 1 incident at v. Vertices of type F (i.e., splitting a face of the previous level) do not trigger any merge operator, because they are removed together with vertices of type E from operators 3a/b-merge. Such vertices are discarded easily because a potentially removable vertex v at level l+ 1 is of type F if and only if either it has exactly four adjacent vertices at levell+ 1, or its star is formed by two standard faces and one face of type 5.

We divide the neighborhood of (internal) vertexv of type E in two halves as follows: there are at most four (standard) edges at levell+ 1 incident at v; among them, only two edges e⁰ and e⁰⁰ have the other end vertex at level ≤l; thus the pair e⁰, e⁰⁰ cover the edge e that was split byv and they divide the neighborhood. For each half neighborhood, we have the following possible cases:

• 4-merge: both faces incident at e⁰ and e⁰⁰ are standard, and the faces adjacent to each of them on the edges opposite to e⁰ and e⁰⁰, respectively, are different; then v is removable and the two faces incident at e⁰ and e⁰⁰ are replaced with a single face of type 5 (note that the region covered by the other two faces of pattern 4 is not affected);

• 3a-merge: both faces incident ate⁰ ande⁰⁰ are standard, and they are both adjacent to the same face (of type 5) along the edges opposite toe⁰ ande⁰⁰; thenv is removable

and a pattern of type 3 is replaced with a pattern of type 2a;

• 3b-merge: one standard face and one face of type 5 are incident at e⁰ and e⁰⁰. Just in this case, we must check that these two faces are both adjacent to another face f of type 0 at levell+ 1 (which completes pattern 3). If this condition is not fulfilled, it means that the third face of pattern 3 (which is not incident atv) has been subdivided further, thereforev is not removable. Otherwise,v is removable and a pattern of type 3 is replaced with a pattern of type 2b.

• 2a-split: both faces incident at e⁰ and e⁰⁰ are of type 2; then v is removable and a pattern of type 2a is replaced with a pattern of type 1;

• 2b-split: one face of type 3 and one face of type 4 are incident at e⁰ and e⁰⁰; then v is removable and a pattern of type 2b is replaced with a pattern of type 1;

• 1-merge: bothe⁰ and e⁰⁰ are incident at the same face of type 1; thenv is removable and a pattern of type 1 is replaced with a pattern of type 0.

For each half neighborhood, we recognize the pattern adjacent to the pair e⁰, e⁰⁰ and we apply the corresponding merge operator, as depicted in Figure 4.6. Operators 1-merge and 2a/b-merge can be applied by checking just the types of faces f⁰ and f⁰⁰ incident ate⁰ and e⁰⁰. In order to discriminate between operators 3a-merge and 4-merge it is also necessary to check the type of face(s) adjacent to f⁰ and f⁰⁰ inside the pattern. Finally, operator 3b-merge needs checking also the other face of type 0 adjacent to the face of type 5 within pattern P3: in fact, v is not removable if such a face has been refined further.

It is easy to verify that the merge operators are consistent with the split operators and they have similar properties: all merge operators affect the whole area covered by a pat-tern, except for 4-merge, which affects just half a pattern; local tessellations to implement operators are precomputed and stored in a lookup table (in fact, the same lookup table that is used for the split operators).

The set of refinement operators is also closed with respect to the meshes obtained. If we start at a mesh Γ obtained from Γ₀ through refinement, we can apply merge operators in any legal order to go back to Γ₀; moreover, any intermediate mesh could be refined through split operators. So we can mix split and merge operators in any order while preserving consistency.