1 Grids

Many 3D geometries we generate are broadly some variation of a grid. They might be simple grids, as for a terrain or sheet; looped grids, as for a tube or torus; or grids connected by seams, as for clothes or bodies.

Graphics cards generally support only triangles, but humans tend to prefer squares. This leads to two type of grids both being common.

1.1 Rectangular grids

An n \times n rectangular grid of points like this:

can be joined into triangles by one of two ways of splitting the squares;

• either join (i, i+1, i+n) and (i+1, i+n, i+n+1)

• or join (i, i+1, i+n+1) and (i+n+1, i+n, i)

Rectangular grids are easy to define, but because of the longer diagonal compared to shorter edges the chosen axes can be visually noticeable in some situations.

1.1.1 Rectangular grid normals

The diagonals on a rectangular grid mess up direct face-based vertex normal computation. A better way of generating normals is to base it on a subset of its grid-adjacent neighbors.

The simpler way is to take the cross-product of the vector connecting the vertices on either side of it along one grid axis and vector connecting the vertices on either side of it along the other grid axis: (n-s) \times (w-e) If we want to also consider the diagonal neighbors, we can take their cross products and do a weighted average, for example as \dfrac{2\big((n-s) \times (w-e)\big) + 1\big((ne-sw) \times (nw-se)\big)}{3} Either way, any missing vertices that would be off the edge of the mesh can be replaced by the vertices on the edge instead.

Don’t forget to normalize the normal vectors, both in JavaScript and in the fragment shader.

1.2 Triangular grids

Triangular or hexagonal grids can be created by modifying the rectangular grid creation as follows:

1. Move each row over by ½ compared to the row before it
2. Reduce row separation by a factor of \sqrt{3} / 2
3. The result is a sheered rectangle
   • to make it hexagonal, omit a point with row and column indices (r,c) if (r + c) < \frac{n}{2} or (r+c) > \frac{3n}{2}
   • to make it triangular, omit a point with row and column indices (r,c) if (r + c) > n

1.2.1 Triangular grid normals

Vertex normals on a triangular grid are best computed by summing the face normals of each incident face. Generally it is better to sum the face normals before normalizing them so that larger faces have more impact on the resulting vertex normal than smaller faces.

The cross product of any pair of edge vectors of a triangle is (a) normal to the triangle and (b) has a length proportional to the triangle’s area. But depending on which two points you pick, it might be pointing in either direction: either out of or in to the surface the triangle is part of. A reasonable way to compute a vertex normal is as an area-weighted average of the face normals of its adjacent faces: in other words, the sum of those cross-product-generated vectors.

Thus, we can find the vertex normals by

1. Initialize a zero-vector for every vertex

2. Loop over every triangle, and for each

   1. Find two edge vectors, p_2-p_0 and p_1-p_0

   2. Take the cross product of the edge vectors

      What if it points the wrong way? Ideally we’d define the triangles carefully so it never does, but for some special cases we can check and fix this; for example, with terrain if the z component is negative, negate the vector.

   3. Add the vector to all three vertex’s normals

3. Normalize all the resulting normal vectors.

   For best performance, normalize them in JavaScript if they won’t change frame to frame, in the vertex shader if they will.

   Don’t forget to also normalize them in your fragment shader! Normalizing per vertex keeps longer normals from dominating the interpolation; normalizing per fragment corrects for the shortening that happens during interpolation.

2 Subdivision

Subdivision starts with a course mesh and generates a fine mesh from it. Usually subdivision involves two parts: the creation of the new set of vertices and faces and the positioning of the new vertices based on the old. This section talks only about the connectivity, not the placement.

There are many possible subdivision patterns, but three are by far the most common. They don’t have standard names, though, so I’m giving them descriptive titles just for ease of reference.

2.1 Center point

This technique works on any kind of mesh, and runs as follows

• Keep all old vertices
• Add a new vertex in the center of each old edge and the center of each old face
• Replace each old n-sided face with n new 4-sided faces; each is bounded by a new face-center vertex, two new edge-center vertices, and an old vertex.

After a single iteration, this creates a mesh containing only quadrilaterals. Old vertices remain regardless of the number of iterations, and keep their initial number of neighbors; all new non-edge vertices have 4 neighbors.

One of the most popular smooth subdivision surface schemes, Catmull-Clark, uses this style of subdivision. Because it creates quads, it is popular with square grids.

Catmull-Clark subdivision

Edwin Catmull and Jim Clark’s subdivision scheme, published in 1978, says that

• new face points should be placed at the average of the face’s vertex locations

• new edge points should be placed at the edge’s old vertices and the two adjacent new face point locations

• old vertices should be moved to \frac{1}{n}\big(F + 2R + (n-3)P\big) where n is the number of edges incident to the old vertex, F is the average location of the new face points adjacent to the old vertex, R is the average location of the new edge points adjacent to the old vertex, and P is the vertice’s old location.

2.2 Face shrinking

This technique works on any kind of mesh, and runs as follows

• Replace each face with a smaller copy of the face. This means each old vertex is replaced by n new vertices, where n is the number of old faces incident to that vertex; and each old edge is replaced by 2 new edges, one of each of its incident faces.
• Connect the new vertices generated by each old vertex with a polygon.
• Connect the new edges generated by each old edge with a square.

After a single iteration, all vertices have 4 neighbors. Most new faces are quads, but each non-quad face remains and each vertex that had other than 4 neighbors becomes a non-quad face too.

A somewhat popular smooth subdivision surface scheme, Doo-Sabin, uses this style of subdivision. It is also the cantellation polytope operation and the polygonal version of beveling. Because each step removes all old vertices and produces new ones, it has a built-in smoothing effect and is sometimes used in operations that want some smoothing but don’t want to use a standard smoothing subdivision.

Doo-Sabin subdivision

Daniel Doo’s subdivision scheme, published as part of his PhD dissertation in 1978 and expanded on in a paper with Malcom Sabin that same year, says that

• new points should be placed at the average of the center of the face, the center of each nearby edge, and the nearest old vertex.

2.3 Triangular

This technique only works on triangular meshes, and runs as follows

• Keep all old vertices
• Add a new vertex in the center of each old edge
• Replace each old face with four new faces: one connecting each old vertex to its two new edge vertices and one connecting the three new edge vertices.

This always only produces triangles. All new non-edge vertices have 6 neighboring triangles, while the original vertices keep their original neighbor counts.

A somewhat popular smooth subdivision surface scheme, Loop, uses this style of subdivision.

Loop subdivision

Charles Loop’s subdivision scheme, published as part of his Masters Thesis in 1987, says that

• new edge points should be placed at \dfrac{3(a+b) + (c+d)}{8} where a and b are the two points that define its edge and c and d are the two vertices not on its edge but on the triangles its edge connects

• old vertices are moved to a new point equal to \alpha v + (1-\alpha) q where v is its old location, q is the average of its old neighboring vertices locations, and \alpha = \left(\frac{3}{8} + \frac{1}{4}\cos\frac{2\pi}{N}\right)^2 + \frac{3}{8} where N is the number of vertices connected by edges to the vertex.

  \alpha for each N can be computed up front, N can only take on a few values. Other \alpha formulas can also work, provided that when N=6 we get \alpha = \frac{5}{8}. Several online sources recommend using \alpha = \frac{5}{16} when N=3 and \alpha = \frac{5}{8} for all larger N instead of Loop’s original formula.

3 Duplicate vertices

A duplicate vertex is represented by two separate vertices in the data which have the same position. Duplicate vertices are useful if we wish to create a visual seam, a sudden change in normal, texture, color, or other visual effect along the edge of a triangle. But if we don’t wish that, they are inefficient and make geometrical computations such as computing normals and subdividing not work well.

Ideally, when creating a mesh we design the creation so that no duplicate vertices are created. But if we fail to do that, we can manually look for and remove duplicates with an approach like the following:

for every vertex p
  for every other vertex q
    if distance between p and q is very small
      replace every reference to q with a reference to p instead
      delete q

Some notes:

• We want to use distance very small instead of same position because vertices are stored with floating-point numbers that tend to have rounding error.
• replace every reference to q generally means changing edge and/or face definitions.
• delete q might mean reducing the length of the attribute array, and thus changing all larger indices too.