The grid subdivision

Mesh Subdivision is like increasing the resolution of an image to make the model have more details. Therefore, mesh subdivision requires various algorithms to introduce more triangles. But if you just break up a big triangle into more triangles, you can’t change the shape of the triangle. Therefore, mesh subdivision is actually two operations: first, increase the number of triangles, that is, divide more triangles; Adjusting the position of the triangle changes the position of the triangle, making the original model smoother.

Have been subdivided

Loop Subdivison is a surface subdivision algorithm for triangular surfaces. Its Name does not really have anything to do with “cycle”, but the Family Name of the inventor of this algorithm is Loop.

Any subdivision should be divided into two steps, roux subdivision only for the triangle face subdivision and update the vertex position operation. Loop subdivision first connects the midpoints of three sides of a triangle to obtain four triangles. Then divide the kinds of vertices of the triangle into new vertices and old vertices. This is because Loop segmentation uses different rules for two different vertices to change their positions.

Update of new vertices

In general there must be two triangles that share an edge (a boundary triangle is a special case). Then the two triangles will intersect at the point PPP. Suppose the collinear edges are called A,BA,BA,B, and the other vertices are called C,DC,DC,D. The four vertices are then weighted and averaged. For example, take 3/83/83/8 of the coordinates of A,BA,BA and B, and 1/81/81/8 of the coordinates of C,DC,DC and D, and add them to obtain the new position of point P. Because we think that vertices closer to P contribute more, and those farther away contribute less.


P = 3 / 8 ∗ ( A + B ) + 1 / 8 ⋆ ( C + D ) P = 3 / 8^{*}(A+B)+1 / 8^{\star}(C+D)

Update of old vertices

In general, an old vertex will connect many triangles (six triangles as shown). Loop subdivision updates old vertices partly by surrounding old vertices and partly by itself. Let the degree of the vertex be NNN, then uuu is a number associated with NNN. The updated old vertices are computed by a series of weights.


( 1 – n ⋅ u ) ⋅ P o + u ⋅ P s u m ( n ) (1-n · u) · P_{o} +\mathrm{u} · P_{sum(n)}

Catmull exemplifies – Clark segmentation

Catmul-clark subdivision can be used if the mesh of the model is not triangular but quadrilateral. In catmul-Clark subdivision, we define the Vertex with Quad Face, non-quad Face and degree not 4 as Extraordinary Vertex.

First of all, catmull-Clark subdivision takes the middle point of each side, and each face also goes to a point, which can be the center of gravity or other stores. Then connect the points on the edges to the points in the center of the surface. We can find that the two singularities with degree 5 remain unchanged after a subdivision, and two new singularities with degree 3 are introduced. If we choose a point in a non-quadrilateral and connect it to all the points on its side (the midpoints), we are bound to get a new singularity. The non-quadrangular surfaces are eliminated after one subdivision, which means that as we subdivide, the singularities are no longer added.

Vertex update

Different from Loop segmentation, catmul-Clark segmentation divides vertices into three categories for updating.

  • A Point in the center of a Face.
  • The Point at the center of the Edge
  • Old Vertex Point

Catmul-clark subdivision and weighted average calculation of three types of vertices in order,

Mesh simplification

For a very complex mesh, we don’t actually need to render such a fine mesh when we are far away. In this case, Mesh Simplification will be needed for the model.

In different cases, we need to choose models of different complexity, similar to the fact that Mipmap divides many levels of fineness. The geometry of a hierarchy has the same meaning as the image of a hierarchy. However, it is difficult to make geometric hierarchy structure, because there is no method like image trilinear interpolation to achieve smooth hierarchy transition when switching geometry of different levels. Therefore, it is necessary to consider whether the switching will affect the look and feel.

Edge collapse

Edge Collapsing is a method of mesh simplification that literally reduces the edges or vertices of a mesh to Collapsing surrounding faces, but Edge Collapsing is not as easy to apply.

Edge collapse needs to determine which edges are important and which are not, so the method of Quadirc Error Metrics needs to be introduced for judgment.

In the one-dimensional case of degenerating a surface into a point as shown in the figure below, there is a shape composed of five vertices and four line segments. We need to simplify it into a blue triangle composed of three vertices, and ensure that the blue triangle is basically consistent with the original shape.

You can see that the new vertices on the triangle have a lot to do with the three vertices to be subtracted, which means that the new vertices should be the result of some kind of weighted average of the old vertices. But if you just take a simple weighted average, you’ll find that the new vertex is one circle smaller than the original bulge anyway.

How to collapse edges

In view of this situation, people introduce the concept of error measure, which adopts quadratic error. We want the new vertex to be in a position that minimizes the error measure, the sum of squares of the distance between the new vertex and the original points.

How to pick edges

Back to the actual three-dimensional space, when edge collapse is to be carried out, we can assume that every edge will be collapsed, and calculate the minimum quadratic metric error of each edge after collapse, and then select the edge with the smallest error from the result to start collapse.

But when one edge collapses, obviously the surrounding edges change too, so the error set needs to be updated. That is, we need a data structure to sort and update the errors dynamically, so the error set can be maintained using a priority queue or heap.

What we need is a simplified contour representation of the global object, but the current algorithm looks for arbitrary local optimal solutions. Obviously, this is a typical greedy algorithm, and there is no guarantee that a global optimal solution can be found.

Grid normalization

For the triangular face mesh, the triangles on the mesh can be large or small, such as long and thin triangles, which will actually cause some inconvenience to rendering.

In this case, we usually apply Mesh Regularization to the model to make the triangular faces more like regular triangles. However, while improving the quality of the triangle, the quality of the model itself should not be lost.