Catmull-Clark Subdivision
Update
The defect mentioned before in the Catmull-Clark subdivision code has been corrected. A cube now correctly approaches a sphere with repeated subdivision.
Ah, much better…
The changes were two in part:
- The algorithm does require quads to be created rather than triangles (not surprising), but the change to quads didn’t work until I realized…
- …the creation of the new face quads must start on an “edge point”; I was originally creating my quads starting with an original vertex – thus ‘rotating’ the quads created from the original face by one vertex, which significantly changes the result.
Both those changes are “obvious” in retrospect since they’re how the Catmull-Clark algorithm is described, however that second bit was not an easy one to pick out from scanning the code.
Original Post
I’ve been working on my Javascript implementation of a half-edge based mesh that supports Catmull-Clark subdivision. The result is below for three levels of subdivision of a cube – and obviously not yet correct. (A cube should subdivide towards a sphere, not the distorted blob below.)
What’s wrong with this picture?
I suspect the problem may be that I am creating triangles rather than quads when subdividing the faces. That would create different updated vertex positions upon multi-level subdivisions, I suspect (the math to prove it one way or the other is certainly possible, but I haven’t attempted that).
The whole experience definitely has me tossing around the pros & cons of implementing functionality in Javascript versus C++. There’s a lot to be said for both and I can’t make up my mind if implementing subdivision and half-edge meshes in Javascript was for the better or worse. (Well, actually I know it was for the better in this instance for the very reason it’s showed me numerous advantages and disadvantages, but I’m thinking of next time.)
Catmull-Clark subdivision is supposed to be part of Tutorial 4, though I wonder why in the world I’ve tried to cram so much new functionality into one new tutorial!