CS 488: Lecture 7 – Geometric Modeling
Dear students:
Our goal today is to generate a few models using code. The algorithmic description of shapes is sometimes called geometric modeling. Not all models can be easily generated via algorithms, and we are likely to build most of our models in a 3D modeling program rather than in code. However, programmatically generating shapes is instructive. It helps us develop an intimacy with the structure of a model. Today we will become intimate with a plane, a sphere, and a cylinder.
Plane
We’ve seen how to model a single quadrilateral with two separate triangles or four indexed vertices. Quadrilaterals are useful for modeling walls or floors. But what if we want a surface that isn’t so flat? We need to decimate that quadrilateral into a quilt of quadrilaterals. We’ll call this shape a plane. A mathematical plane goes on forever. Our plane will be bounded.
The table or grid of points of the plane can be generated with a couple of loops:
function generatePlane(width, height, nlatitudes, nlongitudes)
positions = []
for ilongitude through nlongitudes
x = ilongitude / (nlongitudes - 1) * width - width * 0.5
for ilatitude through nlatitudes
y = ilatitude / (nlatitudes - 1) * height - height * 0.5
positions.push(x, y, 0)
return {positions}
}
When we upload these to the GPU and render them as points, we see the intersection points of our grid. To fill in the pixels between these intersections, we have two choices: enumerate separate positions for each triangle, or use indexed geometry. Given that a single vertex may be shared by as many as six triangles, indexed geometry is a better choice.
Let’s externalize our thinking about this grid with this diagram:
Given our algorithm 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.
In general, we can determine the index through this formula:
index = ilongitude * nlatitudes + ilatitude
Here’s the complete list of indices:
We iterate through this table using a fencepost algorithm and issue index-triplets.
function generatePlane(width, height, nlatitudes, nlongitudes)
// generate positions
indices = []
for ilongitude to nlongitudes - 1
iNextLongitude = ilongitude + 1
for ilatitude to nlatitudes - 1
iNextLatitude = ilatitude + 1
// Bottom-left triangle
indices.push([
ilongitude * nlatitudes + ilatitude,
iNextLongitude * nlatitudes + ilatitude,
ilongitude * nlatitudes + iNextLatitude,
])
// Top-right triangle
indices.push([
iNextLongitude * nlatitudes + ilatitude,
iNextLongitude * nlatitudes + iNextLatitude,
ilongitude * nlatitudes + iNextLatitude,
])
return {positions, indices}
When we render this, our grid is nicely filled. But it doesn’t look any different than a simple quadrilateral. We add some extra details to the internal vertices, like random colors:
function generatePlane(width, height, nlatitudes, nlongitudes)
positions = []
colors = []
for ilongitude in nlongitudes
x = ilongitude / nlongitudes * width - width * 0.5
for ilatitude in nlatitudes
y = ilatitude / nlatitudes * height - height * 0.5
positions.push(x, y, 0)
colors.push(random(), random(), random())
// generate faces
return {positions, colors, faces}
Perturbing the positions is also possible. That’s how we’d generate terrain, which seems to be a rite of passage for every budding graphics developer.
To shade the plane, we need a normal at each vertex. Since the plane is flat, the normals all point the same direction. It feels silly to make this uniform normal an attribute, but we do it anyway, to prepare for less flat geometry:
function generatePlane(width, height, nlatitudes, nlongitudes)
positions = []
colors = []
normals = []
for ilongitude in nlongitudes
x = ilongitude / nlongitudes * width - width * 0.5
for ilatitude in nlatitudes
y = ilatitude / nlatitudes * height - height * 0.5
positions.push(x, y, 0)
colors.push(random(), random(), random())
normals.push(0, 0, 1)
// generate faces
return {positions, colors, normals, faces}
Sphere
Generating a sphere is surprisingly like generating a plane. They are shaped very differently, of course, but their faces are not connected differently. We can use very similar code to generate the indices. We start with the positions.
To calculate the positions, we could look up the parametric equations for a sphere, but we’re going to take a different approach that I think feels less like magic. We first sample the right half of a circle in the z = 0 plane, starting at -90 degrees at the bottom of the circle and working our way up to 90 degrees at the top. This gives us a set of seed points at various latitudes:
function generateSphere(nlatitudes, nlongitudes)
seeds = []
for ilatitude to nlatitudes
radians = ilatitude / (nlatitudes - 1) * pi - pi / 2
seeds.append([cos radians, sin radians, 0])
// ...
Then we spin these seed points around the y-axis to produce lines of longitude:
function generateSphere(nlatitudes, nlongitudes)
// generate seeds
positions = []
normals = []
for ilongitude to nlongitudes
degrees = ilongitude / nlongitudes * 360
rotation = Matrix4.rotateY(degrees)
for ilatitude to nlatitudes
position = rotation * seeds[ilatitude]
positions.push(position)
normals.push(position)
return positions
When we render these positions as points, we see what looks like a globe. We can connect these points together exactly as we did for the plane:
function generateSphere(nlatitudes, nlongitudes)
// generate positions
indices = []
for ilongitude to nlongitudes - 1
iNextLongitude = ilongitude + 1
for ilatitude to nlatitudes - 1
iNextLatitude = ilatitude + 1
// Bottom-left triangle
indices.push([
ilongitude * nlatitudes + ilatitude,
ilongitude * nlatitudes + iNextLatitude,
iNextLongitude * nlatitudes + ilatitude,
])
// Top-right triangle
indices.push([
ilongitude * nlatitudes + iNextLatitude,
iNextLongitude * nlatitudes + iNextLatitude,
iNextLongitude * nlatitudes + ilatitude,
])
return {positions, indices}
However, we want the last line of longitude to wrap around connect back to the first. A little modulus can help make that happen:
for ilongitude to nlongitudes iNextLongitude = (ilongitude + 1) % nlongitudes ...
We add these positions and indices to our vertex buffer objects and we have a filled sphere.
Cylinder
A plane is flat. A sphere is round. We now generate a shape that’s both round and flat: a cylinder. Cylinders exhibit the same connectivity as planes and spheres—save for the end caps. Let’s start by generating their positions with a little trigonometry. We’ll walk around the circle again:
function generateCylinder(radius, height, nlatitudes, nlongitudes)
for ilongitude to nlongitudes
radians = ilongitude / nlongitudes * 2 * pi
x = radius * cos radians
z = radius * sin radians
As with the plane and sphere, we walk along each line of longitude at regular latitudes:
function generateCylinder(radius, height, nlatitudes, nlongitudes)
positions = []
for ilongitude to nlongitudes
radians = ilongitude / nlongitudes * 2 * pi
x = radius * cos radians
z = radius * sin radians
for ilatitude to nlatitudes
y = ilatitude / (nlatitudes - 1) * height - 0.5 * height
positions.push(x, y, z)
normals.push(cos radians, 0, sin radians)
// generate faces
return {positions, normals, indices}
As with the sphere, the normals point outward. We zero out the y-coordinate since the normals don’t point up or down as we traverse up the cylinder.
To add end caps, we issue vertices independent of the cylinder wall. The vertices on the end caps have different normals than the ones on the wall, just as we saw with the vertices of the cube. We add the end caps one at a time, sampling the perimeter of each circle. To triangulate this circle, we include a vertex in the middle of the cap. The triangles all converge on this center point like slices of pizza:
function generateCylinder(radius, height, nlatitudes, nlongitudes)
// generate wall positions
// generate wall faces
// Generate top cap.
icenter = positions.length / 3
positions.push(0, height * 0.5, 0)
for ilongitude to nlongitudes
radians = ilongitude / nlongitudes * 2 * pi
x = radius * cos radians
z = radius * sin radians
positions.push(x, height * 0.5, z)
indices.push(icenter, icenter + ilongitude, icenter + (ilongitude + 1) % nlongitudes)
// Generate bottom cap.
icenter = positions.length / 3
for ilongitude to nlongitudes
radians = ilongitude / nlongitudes * 2 * pi
x = radius * cos radians
z = radius * sin radians
positions.push(x, -height * 0.5, z)
indices.push(icenter, icenter + ilongitude, icenter + (ilongitude + 1) % nlongitudes)
return {positions, normals, indices}
Horizon
We’ve picked off shapes whose normals are relatively easy to calculate. Next time we’ll look at how to compute normals for arbitrary shapes using just the geometry itself. This will give us the power to render non-algorithmic models.
TODO
Here’s your TODO list:
- Don’t attend class on Wednesday. It’s a break day.
- Use your break to finish Rastercaster.
- Before lab, have a project ready to go that can render a sphere.
See you next time.
P.S. It’s time for a haiku!
Vote for the best math
Geometry beats them all
‘Cuz the eyes have it