Subdivisió recursiva

Subdivisió Recursiva

Aqui podeu trobar informació i links sobre diferents algorismes

Algorisme de subdivisió de Doo i Sabin

Aquest algorisme parteix d'un poliedre P (que suposarem que no té anells i que per tant R=0. A més, suposarem que té una sola component connexa, S=1) i genera un nou objecte (poliedre) de sortida, treballant en tres fases:

Observeu que si el poliedre P tenía C cares, A arestes i V vèrtexs, el nou poliedre tindrà C+A+V cares i un total de 2*A vèrtexs. El nombre de cares és obvi; pel que fa al nombre de vèrtexs, cal observar que són el de les cares encongides i que el seu nombre és el de semiarestes de P, ja que en el procés d'encongiment de cares veines, les semiarestes es desdoblen. Si P no té forats passants l'equació d'Euler és C+V=A+2, i el nombre d'arestes del nou poliedre és C+3*A+V-2 . Si les cares de P són convexes, les cares del nou poliedre també ho són.

Un cop hem acabat aquests tres passos, tenim un nou poliedre amb R=0, subdividit respecte l'inicial. Podem repetir el proces de subdivisió amb aquest nou poliedre, per anar-lo suavitzant.

L' únic que resta és saber com encongir una cara. Doo i Sabin demostren que, per tal de maximitzar la suavitat del resultat (de fet, demostren que en les zones en que els vèrtexs tenen quatre cares veines, la superficie tendeix a un B-Spline biquadràtic), en una cara amb n vèrtexs v1.. vn,

 v'k = ( Suma ( Alfak-i * vi ) ) / n

On la suma s'estén a tots els n vèrtexs de la cara. 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. El coeficient Alfa0 és igual a  Alfa0 = (1/4 + 5/(4*n)) i els altres es calculen com Alfak-i = ( 3 + 2 * cos ( 2*pi*(k-i)/n) ) / (4*n) .