Grid

We've seen how we can model a single quadrilateral with two triangles. Quadrilaterals are useful for modeling walls or floors, but what if we want a surface that isn't so flat? Or that has many colors? Only by introducing more vertices can we add finer detail. We need to subdivide that quadrilateral into a grid of quadrilaterals.

Step through the following sequence to see how we programmers view the subdivided grid:

1. A quadrilateral has only four vertices at which we can define attributes like position and color.
2. Subdividing the quadrilateral into a grid gives us more vertices and finer detail.
3. We describe locations on the grid just like on a globe. Latitude is the vertical measure.
4. Longitude is the horizontal measure.
5. We need the index of each vertex, which we'll compute using the longitude and latitude indices.
6. The indices will be used to form triangles that fill the grid.

⭠ ⭢

The grid's vertex positions can be generated with nested loops that iterate through each latitude-longitude pair:

export class Prefab {
  static grid(width: number, height: number, longitudeCount: number, latitudeCount: number) {
    const positions: Vector3[] = [];

    for (let lat = 0; lat < latitudeCount; ++lat) {
      const y = lat / (latitudeCount - 1) * height;
      for (let lon = 0; lon < longitudeCount; ++lon) {
        const x = lon / (longitudeCount - 1) * width;
        positions.push(new Vector3(x, y, 0));
      }
    }

    // ...
  }
}

export class Prefab {
  static grid(width: number, height: number, longitudeCount: number, latitudeCount: number) {
    const positions: Vector3[] = [];

    for (let lat = 0; lat < latitudeCount; ++lat) {
      const y = lat / (latitudeCount - 1) * height;
      for (let lon = 0; lon < longitudeCount; ++lon) {
        const x = lon / (longitudeCount - 1) * width;
        positions.push(new Vector3(x, y, 0));
      }
    }

    // ...
  }
}

The latitude and longitude indices are turned into proportions in [0, 1] and then applied to the grid's dimensions to compute the actual x- and y-coordinates. The z-coordinate is set to 0 for the time being to produce a flat grid.

Place the Prefab code in a file named lib/prefab.ts. Grid will be one of several prefabricated meshes that we'll generate.

We also need to generate the list of the triangles' indices. Let's externalize our thinking about how to do this by revisiting the image in step 6 above, which is reproduced here for easy reference:

What is the index of the vertex whose longitude is 0 and latitude is 0? That's vertex 0. How about the one whose longitude is 1 and latitude is 0? That's vertex 1. How about the one whose longitude is 0 and whose latitude is 1? That's vertex 4.

In general, we determine the index from the latitude and longitude by counting how many vertices land in the two rectangles that precede the vertex in question. Suppose we want the index of the vertex whose longitude is 2 and latitude is 3. These are the two rectangles that precede the vertex:

The bottom rectangle contains lat * longitudeCount vertices, which in this case is 12. The top rectangle contains lon vertices, which in this case is 2. The vertex therefore has index 14. This local helper function captures this logic and will simplify the code we're about to write:

const index = (lon: number, lat: number) => {
  return lat * longitudeCount + lon;
};

const index = (lon: number, lat: number) => {
  return lat * longitudeCount + lon;
};

Now we iterate through the grid again to generate the index triplets. Triangles fill the space between vertices. Let's only visit a vertex if it's the bottom-left corner of a cell. We'll emit that cell's two triangles. The loops won't touch the right or top edges of the grid since no cells start on those edges. The code has this rough shape:

class Prefab {
  static grid(width: number, height: number, longitudeCount: number, latitudeCount: number) {
    // ...

    const faces: number[][] = [];
    for (let lat = 0; lat < latitudeCount - 1; ++lat) {
      for (let lon = 0; lon < longitudeCount - 1; ++lon) {
        const nextLon = lon + 1;
        const nextLat = lat + 1;

        faces.push(/* TODO: bottom-left triangle */);
        faces.push(/* TODO: top-right triangle */);
      }
    }

    return new Trimesh(positions, faces);
  }
}

class Prefab {
  static grid(width: number, height: number, longitudeCount: number, latitudeCount: number) {
    // ...

    const faces: number[][] = [];
    for (let lat = 0; lat < latitudeCount - 1; ++lat) {
      for (let lon = 0; lon < longitudeCount - 1; ++lon) {
        const nextLon = lon + 1;
        const nextLat = lat + 1;

        faces.push(/* TODO: bottom-left triangle */);
        faces.push(/* TODO: top-right triangle */);
      }
    }

    return new Trimesh(positions, faces);
  }
}

Once we have the positions and faces, we have all we need to create a Trimesh instance, which we return.

When we render this as triangles, our grid is nicely filled—but it looks just like a simple quadrilateral. We could add some extra details to the internal vertices, like random colors. Our Trimesh class doesn't currently support any attributes beyond position. (Feel free to add more state and getters.) We could also set the z-coordinate to something besides 0 to produce a rugged terrain, but we don't yet have a way of rotating the mesh in three dimensions to see its roughness.

The grid itself may not be very exciting, but we can bend it into more interesting shapes.