teaching machines

Grid

May 18, 2021 by . 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:

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:

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:

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!

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *