A polygon mesh editor in the style of Maya or Blender, written in C++ with Qt and OpenGL. Meshes are stored in a half-edge data structure, which makes it possible to walk across a surface and change its topology directly. On top of that structure, Catmull-Clark subdivision turns a coarse mesh into a smoother one with many more faces.
Each edge is stored as two half-edges, one for each direction. A half-edge points to its next half-edge around the face, its opposite (“sym”), its face, and the vertex it ends at. Vertices and faces each keep a pointer to one half-edge.
Neighbors can then be reached by following pointers, with no searching. For example, repeating next → sym from a half-edge that points to a vertex visits every edge and face around that vertex.
1. Face points. Each face gets a new point at the average of its vertices.
\[ \mathbf{f} = \frac{1}{k}\sum_{i=1}^{k} \mathbf{v}_i \]
2. Edge points. Each edge is split once by a new vertex, placed using its two endpoints and the face points on both sides. The position has to be computed before the split, since splitting changes the pointers it depends on.
\[ \mathbf{e} = \frac{\mathbf{v}_1 + \mathbf{v}_2 + \mathbf{f}_1 + \mathbf{f}_2}{4} \]
3. Smooth the original vertices. Each original vertex moves toward its surroundings. Here \(n\) is the number of edges meeting at the vertex, and the sums run over its \(n\) adjacent edge points and face points.
\[ \mathbf{v}' = \frac{n-2}{n}\,\mathbf{v} + \frac{\sum_i \mathbf{e}_i + \sum_i \mathbf{f}_i}{n^2} \]
4. Quadrangulate. A face with \(k\) sides is rebuilt as \(k\) quads meeting at its face point. Two new half-edges are added per quad, and the half-edges going into and out of the center are saved so that neighboring quads can be paired as opposites once the loop is done.
The first level turns the cow’s triangles into three quads each. After that, every quad becomes four, so the face count grows by a factor of four per level.
Every face, edge, and vertex is handled a fixed number of times per level, and each lookup is either a pointer or a hash map access. A level’s running time should therefore grow in proportion to the mesh size. The measurements on the cow agree: each time the output grows fourfold, the time grows by 4.4 to 4.8 times.
| Faces | Time | Per output face |
|---|---|---|
| 5,804 → 17,412 | 51 ms | 2.9 µs |
| 17,412 → 69,648 | 229 ms | 3.3 µs |
| 69,648 → 278,592 | 1,105 ms | 4.0 µs |
| 278,592 → 1,114,368 | 4,857 ms | 4.4 µs |
All four levels take about 6.2 seconds in total. The cost per face rises slightly as the mesh grows, which may come from memory access as the mesh gets larger, though I did not profile it. Times come from std::chrono around the subdivision call only, excluding the GPU upload, in a debug build without compiler optimizations.
| Tool | Used for |
|---|---|
| C++ | Half-edge structure, OBJ loading, and subdivision |
| OpenGL | Drawing the mesh and highlighting selections |
| Qt | Component lists, edit controls, and buttons |
| Qt Creator, MinGW | Building and running the project |
Built on the course’s base code, which provides the application framework and the cow and cube meshes. Source code is not public, as this is course work.