Moving the frame from 2D to 3D, we will now utilize the concept of meshes, a network of vertices, edges, and faces in the 3D space, to model 3D objects with polygons. To handle meshes, we will use the halfedge data structure that can helps us conveniently and consistently iterate through each polygon. Here, while the halfedge data structure can be used for any polygon mesh, we will focus only on triangle meshes. With a 3D object made of triangles, we can implement and perform various mesh operations, such as Phong shading with area-weighted vertex normals, edge flipping, edge splitting, and mesh upsampling with loop subdivision.
We also touch on Bezier curves (2D) and surfaces(3D) with 1D de Casteljau Subdivision to model smooth and infinitely scalable curves and surfaces through linear interpolation.
In this section, polygon orientation and pointer chasing are essential and powerful. One may find interesting that the halfedge data structure heavily relies on consistency and minimalistic structure that maintains elegant connectivity: counterclockwise/clockwise orientation, halfedge "glues", iterators/pointers with object-oriented programming, boundaries, etc. One may ponder what geometries of a polygon constitutes a good overall mesh, how we can operate exhaustive mesh operations faster, or what is required to downsample a model. Perhaps there are ways to prevent my computer from exploding everytime I run a detailed mesh model!
With de Casteljau's algorithm, we can easily evaluate Bezier curves.
A Bezier curve of degree N-1 is a parametric curve defined by N control points.
de Casteljau's algorithm utilizes successive linear interpolation (lerps) and "corner cutting" recursive ratio subdivision to evaluate a point on a representative curve in respect to t by interpolating between neighboring points. Given a list of points of size N and a ratio t, we would need to lerp two consecutive points and gain N-1 intermediate points with N given points on the kth lerp level. After successive lerps, we will identify one point that lies on the overall curve of the initial N points. With a helper function to evaluate on one lerp level, implementing this is as simple as an iteration on N control points (finding an intermediate point in respect to t between each pair of consecutive points) on the kth level. We thus successively call this helper function until one point is left. This is the point on the Bezier curve.
For example, given 6 control points, we can evaluate a point on their Bezier curve with t = 0.5
|
|
|
|
|
|
Similarly, if we change the positions of the 6 control points (all points are slightly moved and one is dramatically moved), these points will create a new Bezier curve. As one may expect, de Casteljau's algorithm will continue to correctly evaluate one point on the curve as planned. Also, changing t will only give us another point on the curve (much like sliding across the curve)!
With de Casteljau's algorithm, we are able to evaluate Bezier curves in the 2D space. Using this fundamental building block, we can similarly move to 3D Bezier surfaces. Given a N×M grid of original control points and parameters u and v (much like t), we can evaluate N Bezier curves (using Part 1's recursive algorithm!), each curve evaluated under M control points parameterized by u. With these N points evaluated at their respective Bezier curves, we can do evaluate these points parameterized by v to get a point that lies on the Bezier surface.
In the implementation, with the helper function evaluate1D(std::vector
|
|
|
|
|
|
When shading, it is better to utilize Phong shading than flat shading to get a smooth look to a 3D object. To do this, we need to implement area-weighted normal vectors at all vertices.
This is when the halfedge data structure can be very useful! The data structure helps us maintain consistency in our polygon mesh, as well as provide an elegant way to traverse across vertices, faces, edges, halfedges, and triangles. Below is the implementation of the halfedge data structure.
Thus with this data structure, we will simply compute and sum all areas of neighboring triangles by finding the cross product of the two vectors moving outwards from the input vertex and divide the product vector by 2 [Definition: area of parallelogram / 2 = area of triangle]. To do this, we will need to find the positions of all 3 vertices per triangle and create these two vectors to be repurposed. With this, we can achieve Phong shading.
|
|
|
|
|
|
|
|
|
|
In our triangle mesh, we may find useful to implement a mesh operation: flipping any given edge in a mesh. Thus, given a shared edge between two triangles in a mesh, we will simply relocate the same edge (pointers!) to connect to two other vertices of the triangles. Keep in mind that flipping "boundary edges" of a model would not make sense as it will disconnect our halfedge data structure.
Given the halfedge data structure and its heavy reliability for connectivity, aside from simply flipping an edge object, we will also need to relocate and reconnect associated elements (vertices, halfedges, faces) of the two triangles that may be affected by this edge movement. Here, it is recommended to draw a state diagram (2 states: before and after flipping) and reconnect everything by hardcoding the arrangements. This works due to consistency and the fact that the mesh will continue to be connected with little consequences. Below is the state diagram used to implement an edge flip.
With this state diagram and careful hardcoding, there are hardly any bugs to deal with. Just be careful! After this extensive implementation, we can optimize by removing some redundancies, as some elements, like edges, outside halfedges, and vertices, do not actually change orientation!
|
|
|
|
|
|
|
|
|
|
Similarly with flipping edges, we can create another useful mesh operation: edge splitting! With careful documentation and extensive hardcoding, we can also split edges. To split an edge, keep in mind that new need to create new elements! To split, we will need to create 1 new vertex at the selected edge's midpoint, 2 new triangle faces, 3 new edges, and 6 new halfedges. Then we would need to reassign pointers as needed. Below is the state diagram to implement the hardcode. Circled in the second state are the new elements we need to make.
Pay in mind that what is implemented has no support for boundary edges (corner case), although you very well can with similar concepts since a mesh allows us to identify boundary edges easily.
|
|
|
|
|
|
With that, we have two mesh operations at our disposals. Below is a demo of combining the two, which prepares us for loop subdivision.
|
|
|
|
|
|
Huzzah! We made it to the last mesh operation that combines flipping and splitting: loop subdivision for mesh upsampling. This upsampling mesh operation assists us to turn coarse polygon mesh into a higher-resolution one for better display, more accurate simulation, and etc. This function will mainly approximate original mesh vertices and interpolate more triangles onto our mesh.
To implement this function, we are required follow these steps:
[1] Preprocess "updated vertice positions" and store these values in a variable in either an original edge (for new vertex positions) or original vertex (for original vertex's updated position). These updated vertice positions are the weighted average of neighboring vertex positions.
[2] 4-1 subdivision: subdivide each triangle in the mesh into four by splitting all ORIGINAL mesh edges, and then flipping all NEW edges that connects an old vertex and a new vertex. This is jsut using our implemented functions and conditionally iterating over our edges.
[3] Update ALL (original and new) vertex positions through standard vertex iteration.
Visually, we can describe [2] 4-1 subdivision and [3] updating all vertices below:
|
|
|
With our halfedge data structure, iteration is simple. Interestingly, when implementing, I found it easier to create a new list of original edges (pointers), which takes an additional O(N) in space and time. Generally, this doesn't affect our overall linear runtime very much (slower by just a factor). With this list, I can split only original edges easily, as the ORIGINAL list of edges in the mesh would consequently increase due to the fact that splitting edges creates 3 new edges and adds them to the list; distinguishing old and new edges in this list would not be worth the trouble. Sometimes a little extra (space and time usage) can go a long way!
After implementing our loop subdivision, meshes will now look smoother and higher-resolution after loop subdivision.
|
|
|
|
|
|
|
Now our teapot looks a lot better and smoother! By upsampling with loop subdivision, we create more triangles in estimated positions in our mesh. With more samples, this means a higher quality and smoother object with better transitions at sharp corners and edges (such as the spout's base of the teapot); no longer will our objects be blocky! The effects are best seen in the Phong shading of the teapot as shading with area-weighted normal vectors are visually better with more vertices! However, let's check on some corner cases. We may sometimes come across a problem in symmetry. Consider upsampling a cube with loop subdivision below:
|
|
|
|
Unfortunately, the cube becomes slightly asymmetric after repeated subdivisions. The cube ends up asymmetrical due to the way we made the cube with our mesh; we have one edge split each cube face in an asymmetrical manner. Fortunately, we can pre-process the cube with edge flips and splits so that the cube subdivides symmetrically! To do that, we will split each edge on all cube faces to allow our 4-1 subdivision to interpolate triangles equally on a cube face. By creating 4 symetrical triangles on each face, we can process the cube quite nicely.
|
|
|
|
