» Grid

Grid

May 18, 2021 by Chris Johnson. Filed under public, slai-2021.

This post is part of a course on geometric modeling at the Summer Liberal Arts Institute for Computer Science held at Carleton College in 2021.

Earlier we modeled a square using just two triangles. Now we model a rectangle using a dense grid of triangles. A dense grid does not offer many advantages over a simple 2-triangle square, but in later exercises, we’ll form this dense grid into other shapes.

This exercise is a stepping stone to a broader class of 2D parametric surfaces, which are 3D shapes that can be expressed as functions of two variables. Earth is a parametric surface. Any point on its surface can be described using two variables: a latitude-longitude pair.

We will use the idea of latitude and longitude as we build these shapes. Remind yourself of the answers to these questions:

What does latitude measure?
What does longitude measure?

When you’ve successfully remembered, you’re ready to start modeling a grid.

Vertices

Let’s start by computing just the vertex positions of the grid. Connecting them up into triangular faces can wait. Writing code is more pleasant when you aren’t trying to debug two things at once.

Follow these steps to compute the vertices of the grid as displayed in the image above:

Write a function generateGrid in shapes.js.
Have the function accept two parameters: a number of lines of latitude and a number of lines of longitude. The higher these numbers, the more the grid will be subdivided.
Define an empty positions array.
Write a for loop that iterates up to the number of latitudes.
Turn the latitude index into the y-coordinate of any vertex on that line of latitude.
Surround the latitude loop with a similar loop that iterates up to the number of longitudes.
Turn the longitude index into the x-coordinate of any vertex on that line of longitude.
Using the x- and y-coordinates, along with a z-coordinate of 0, push the vertex position of the current latitude-longitude pair into the positions array.

When your render your vertices, they should appear in a grid formation. However, they are probably not centered. Follow these steps to allow the grid to be sized and centered:

Add two parameters to your function to specify the grid’s width and height.
Turn the longitude index into a proportion of the maximum:
```
ilongitude / (nlongitudes - 1)
```
Apply the longitude proportion to the width:
```
ilongitude / (nlongitudes - 1) * width
```

Subtract off half the width to center it:

ilongitude / (nlongitudes - 1) * width - width * 0.5

Use this sizing and centering arithmetic to compute your x-coordinate.
Apply similar arithmetic to compute the y-coordinate.

Now your grid should appear centered.

Faces

To fill in the pixels between these intersections, you need to add triangle indices. Given that a single vertex is shared by as many as six triangles, as you can see in the figure of the grid above, indexed geometry is very helpful here. We need a way to figure out each vertex’s index.

Given the algorithm described above, what is the index of the vertex whose ilatitude is 0 and ilongitude is 0? That’s vertex 0. How about the one whose ilatitude is 1 and ilongitude is 0? That’s vertex 1. How about the one whose ilatitude is 1 and whose ilongitude is 0? That’s vertex 4.

Here’s the complete list of indices for our example:

We need a general formula for computing the index. There is one, though it may not feel intuitive. A vertex’s ilongitude value tells us how many lines of longitude precede it. Each of these lines has nlatitudes vertices in it. So, we can multiply these together to get the number of indices in the rectangular block left of the vertex. Then we need to count the vertices south of the current latitude. That leads to this formula for turning a 2D latitude/longitude pair into a 1D index:

index = ilongitude * nlatitudes + ilatitude

You’ll need to convert to an index a lot. You are encouraged to write this as a function:

function index(...) {
  return ...
}

In this pseudocode, we generate our list of triangles:

initialize triangles list
for each longitude index but the last
  iNextLongitude = ilongitude + 1
  for each latitude index but the last
    iNextLatitude = ilatitude + 1
    
    // Bottom-left triangle
    add index of (ilatitude, ilongitude) to triangles list
    add index of (ilatitude, iNextLongitude) to triangles list
    add index of (iNextLatitude, ilongitude) to triangles list

    // Top-right triangle
    add index of (ilatitude, iNextLongitude) to triangles list
    add index of (iNextLatitude, iNextLongitude) to triangles list
    add index of (iNextLatitude, ilongitude) to triangles list

When you switch back to the solid rendering, you should see a dense grid. You did it!