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:
- Per cada cara c del
poliedre P, generem una nova
cara encongida respecte la cara original i l'afegim al nou objecte. Si
la cara c tenia les semiarestes
a1 .. an i els vèrtexs v1 .. vn,
direm que la cara encongida té les semiarestes a'1 ..
a'n i els vèrtexs v'1.. v'n, on
a'k = Encongit(ak) i v'k = Encongit(vk)
.
- Per cada aresta a del
poliedre P corresponent a dues
semiarestes ad, ae, generem una nova cara de 4
arestes que uneix les dues semiarestes Encongit(ad) i Encongit(ae), i que s'han obtingut
després d'haver encongit, a la fase anterior, les dues cares
contigües a l'aresta a.
- Per cada vertex v del
poliedre P, generem una nova
cara, que uneix tots els vertexs resultants de l'encongiment de v:
Encongit(v) per totes les cares
de P que eren veines al
vèrtex v.
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 ( Alfa
k-i
* v
i ) ) / 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) .