Assignment 2: Geometry

Cecilia Zhang

In this project I experimented with mesh geometries, mainly through the concepts of Bezier surface and halfedge structure. Surface is first tessellated into triangles, then subdivided using loop division with mesh split and flip. The level of subdivision determines the smoothness of the tessellated surface. Next step is to add shading to the mesh object. Phong shading and environment map reflection shading are added in GLSL. Eventually, the modeling software blender is used to create more customized meshes.

Part 1: Fun with Bezier Patches

The goal of this part is to tesselate the Bezier surface into triangles. Surface is controlled by 16 (4 by 4) control points in 3D space. Control points are grouped by 4, and each of the 4 points form a Bezier curve, thus a bicubic tessellation. To tesselate the Bezier surface uniformly on a 8 by 8 grid in parameter space, we need to calculate the 3D coordinates for each point on the parameter space, using Bernstein polynomials and tensor product Bezier patch:

b^{m,n}(u, v) = \sum_{i=0}^{m}\sum_{j=0}^{n}b_{i,j}B_i^{m}(u)B_j^{n}(v)\\

Where B_i^{m}(u), B_j^{n}(v) are Bernstein polynomials with m, n being the degree of Bezier curve (here it's bicubic tessellation and thus m = n = 3), and u, v are the coordinates in the parameter space. What returns by this equation is the 3D coordinates of each point in the parameter space.

Tessellate a Bezier surface into triangles. Resulting mesh of a teapot

Part 2: Average normals for half-edge meshes

In this part, per-vertex normal vector is calculated for each vertex. More specifically, normals of neighboring faces are calculated and accumulated with a weight proportional to the face area. Looping through all neighboring faces require the use of half-edge structure, where twin() and next() in half edge object are used to point to target edges that could then point to target faces.

There is a big difference using smoothed averaged normals when we add shading (here using OpenGL default shading) to the object, as seen from the below comparison. Using per-vertex normals that consider all the neighboring face orientations results in much more smooth surface.

Comparing shading with and without smoothed normals. (left) face normals (right) average vertex normals

Part 3: Edge Flip

Edge flip is very useful when we later do subdivision to have more uniformly distributed triangular meshes. Below I show an illustration of using half edge structure for edge flipping. 'v' are vertex structures, 'h' are half-edge structures, 'f' are face structures and 'e' are edge structures. Each of the element is numbered so that we are able to observe their position/connection change after edge flipping. In the implementation, we initialize all the elements by pointing them to their connected elements, and update all elements according to their changes after edge flipping. There are elements that change connections, while there are also elements that stay the same. For example, e3 originally have half-edges of h8 and h4; after flipping, it has half-edges h8 and h2. h4 and h2 change their edge pointer while h8 doesn't.

Illustration of all mesh elements before and after edge flipping

Below I show the mesh before and after I flip some of its edges.

Before and after some edge flipping in the mesh (some edges on the center of teapot surface are flipped)

Part 4: Edge Split

Edge splitting is similar with edge flipping, in a slightly more complicated way since there are new elements created after splitting edges, e.g a new vertex and some new half-edges are created. I also found it helpful to first draw an illustration of before and after edge splitting. We can observe that v4 is a newly created vertex after edge splitting, together with 6 new half-edge structures, 3 new face structures and 3 new edge structures. Note that the newly created vertex should point to an half-edge that is along the edge it splits, instead of along the newly created edge direction.

Illustration of all elements in mesh before and after edge splitting

Below I show the mesh before and after I flip and split some of its edges.

Before and after some edge flipping and splitting in the mesh

It doesn't make sense to flip boundary edges, but makes sense to split boundary edges. Thus I also considered handling with boundary edge splitting. An illustration of boundary edge splitting is shown below.

Illustration of splitting boundary edges using "virtual boundary face"

For boundary conditions, I show the beetle mesh for illustration:

Splitting for boundary edges using "virtual boundary face"

Part 5: Upsampling via Loop Subdivision

Loop subdivision is to upsample the triangular mesh to make the surface more smooth. New position of old vertices and new vertices are calculated, then edges are split and flipped to have more uniform structure. During the last step of flipping selected edges, we only flip new edges that connect to one old vertex and one new vertex. In order to distinguish among different edge conditions (either new or old, or connected to old/new vertices), we have to keep track of whether each vertex and edge is new or old, by setting the member function isNew() accordingly at each previous step. For example, during the first iteration of all original mesh vertices, we can set all vertices to 'old'; and during splitting edges, we can set all newly created vertices as 'new'.

Subdivision on quadball

Below is the subdivision of a cube.

Subdivision on cube (record every two subdivision steps)

Below I show the sharp corner of the cube after subdivision. We observe that the sharp edge subdivides into non-symmetric triangles that have different surface areas (marked in the red box). The subdivided sharp edges has C0 continuity but don't satisfy collinearity. Therefore if we keep splitting the mesh, the corner will not be smoothed into the surface, as can be seen later.

Subdivision on sharp corners (Left) sharp corner after subdivision (right) pre-splitting on sharp corner after subdivision

Resulting from sharp edges and corners, the subdivided cube mesh is not symmetric, and thus the subdivision results in a non-symmetric mesh. In order to make the subdivision ends in a symmetric mesh, we can pre-split the edges to make the mesh have a symmetric structure (shown in the left figure). Particularly for this cube, we can split all edges on all the six faces, resulting in a symmetric mesh structure. The resulting symmetric cube is also shown below on the right:

Symmetric subdivision on cube with pre-splitting edges (left) pre-splitting edges (right) subdivision results in a smooth and symmetric cube mesh

Part 6: Fun with Shaders

In this part, phong shading and environment map shading are implemented in GLSL.

For phong shading, we have control over the ambient shading, specular shading and diffuse shading. Ambient shading is constant in the scene independent of light source and viewing position. Diffuse shading (Lambertian shading) is independent of viewing position but dependent on light source position. And the specular shading is dependent on both light source and viewing position.

For environment map shading, we have a pre-loaded environment map as the texture to our mesh. Since we are mapping a 2D texture to a 3D mesh, we have to also map the coordinate from a 3D position to a 2D coordinate. Spherical coordinate is used to access the environment map in this case.

Different shaders (left) phong shading (right) environment map shading

I also tried out bump mapping. The idea is to perturb the mesh norm with a given normal map. However, since there is no texture coordinate loaded within the program, I have to use the vertex coordinates as the texture coordinates. This can be intuitively understand as projecting the normal map from the top onto the mesh surface (if I use xy of vertices). Basic pipeline of adding bump mapping is as follows:

Within frag, I created a shadeBump function that combines bump mapping with phong shading. In order to perturb the normal, I need to

bump mapping to a quadball, upper right is the normal map used for perturbation
bump mapping to a teapot, upper right is the normal map used for perturbation

Part 7: Design your own mesh!

To practice using blender, I first created the simple man mesh object.

Subdivision on the man mesh created from blender. Figures are shown every two steps of subdivision
Add shaders to the subdivided man mesh

After getting more familiar with using blender, I create my own diamond mesh

Notice that diamond is an example when we don't want to subdivide our mesh, as the object is supposed to have non-smooth surface. When we subdivide the diamond, it looks more and more like a Gyro.

Subdivision on the diamond mesh created from blender

Add environment map shaders to the subdivided diamond mesh