Recursive subdivision

Recursive subdivision

Here you can find information and links on different algorithms

Doo and Sabin's subdivision algorithm

This algorithm is based on a polyhedron P. Suppose that it has no rings, so R=0. Additionally, suppose that it has one shell alone, so S=1. The algorithm generates a new object (a polyhedron) as output, performing three steps:

• For each face f of polyhedron P, we generate a new shrunken face with respect to the original face, and we add it to the new object. If face f had halfedges e₁ .. e_n and vertices v₁ .. v_n, we say that shrunken face has halfedges e'₁ .. e'_n and vertices v'₁.. v'_n, where e'_k = Shrunken(e_k) i v'_k = Shrunken(v_k) .

• For each edge e of polyhedron P corresponding with two halfedges re, le, we generate a new 4-edged face joining the two halfedges Shrunken(re) and Shrunken(le), which have been obtained after the shrunk process on the two faces contiguous to edge e in the previous step. 

• For each vertex v of polyhedron P, we generate a new face, joining all resulting vertices of v shrunk process: Shrunken(v) for all faces of P that where neighboring vertex v.

Note that if polyhedron P had F faces, E edges and V vertices, the new polyhedron will have F+E+V faces and a total of 2*E vertices. The number of faces is obvious; regarding the number of vertices, we note that they all belong to shrunken faces, so their number exactly equals the number of halfedges of P, because in the shrunk process of neighboring faces, the halfedges split. If P has no handles, then Euler's formula is F+V=E+2, and the number of edges of the new polyhedron is F+3*E+V-2 . If P faces are convex, faces of the new generated polyhedron are convex too.

Once these three steps have been completed, we have a new polyhedron with R=0, which is a subdivision with respecto to the original object. We can repeat iteratively this process on this new object, in order to smooth it.

The only thing remaining is to know how the shrink process of a face works. Doo and Sabin give a proof that, in order to maximize the smoothness of the result (actually they give a proof that areas containing vertices with four neighboring faces converge to a biquadratic B-spline surface), a face with n vertices v₁.. v_n satisfies

 v'_k = ( Sum ( Alpha_k-i * v_i ) ) / n

Where the sum is extended along all n vertices belonging to that face. C Els coeficients Alfa són tots positius i sumen la unitat, de manera que els vèrtexs encongits són una mena de ponderació dels vèrtexs inicials de la cara. Coefficient alpha Alpha₀ equals  Alpha₀ = (1/4 + 5/(4*n)) and the rest is calculated as Alpha_k-i = ( 3 + 2 * cos ( 2*pi*(k-i)/n) ) / (4*n) .