三维网格细分算法（Catmull-Clark subdivision & Loop subdivision）附源码

　　下图描述了细分的基本思想，每次细分都是在每条边上插入一个新的顶点，可以看到随着细分次数的增加，折线逐渐变成一条光滑的曲线。曲面细分需要有几何规则和拓扑规则，几何规则用于计算新顶点的位置，拓扑规则用于确定新顶点的连接关系。下面介绍两种网格细分方法：Catmull-Clark细分和Loop细分。

Catmull-Clark subdivision：

　　Catmull-Clark细分是一种四边形网格的细分法则，每个面计算生成一个新的顶点，每条边计算生成一个新的顶点，同时每个原始顶点更新位置。下图为Catmull-Clark细分格式的细分掩膜，对于新增加的顶点位置以及原始顶点位置更新规则如下：

1.网格内部F-顶点位置：

　　设四边形的四个顶点为v、v、v、v，则新增加的顶点位置为v = 1/4*(v + v + v + v)。

2.网格内部V-顶点位置：

　　设内部顶点v的相邻点为v、v，…，v，则该顶点更新后位置为，其中α、β、γ分别为α = 1 - β - γ。

3.网格边界V-顶点位置：

　　设边界顶点v的两个相邻点为v、v，则该顶点更新后位置为v = 3/4*v + 1/8*(v + v)。

4.网格内部E-顶点位置：

　　设内部边的两个端点为v、v，与该边相邻的两个四边形顶点分别为v、v、v、v和v、v、v、v，则新增加的顶点位置为v = 1/4*(v + v + v + v) = 3/8*(v + v) + 1/16*(v + v + v + v)。

5.网格边界E-顶点位置：

　　设边界边的两个端点为v、v，则新增加的顶点位置为v = 1/2*(v + v)。

效果：

function [VV, FF, S] = CC_subdivision(V, F, iter)

    % Catmull_Clark subdivision

    if ~exist('iter','var')

        iter = ;

    end

    VV = V;

    FF = F;

    for i = :iter

        nv = size(VV,);

        nf = size(FF,);

        O = outline(FF);

        original = :nv;

        boundary = O(:,)';

        interior = original(~ismember(original, boundary));

        no = length(original);

        nb = length(boundary);

        ni = length(interior);

        %% Sv

        Etmp = sort([FF(:,) FF(:,);FF(:,) FF(:,);FF(:,) FF(:,);FF(:,) FF(:,)],);

        [E, ~, idx] = unique(Etmp, 'rows');

        Aeven = sparse([E(:,) E(:,)], [E(:,) E(:,)], , no, no);

        Aodd = sparse([FF(:,) FF(:,)], [FF(:,) FF(:,)], , no, no);

        Aodd = Aodd + Aodd';

        val_even = sum(Aeven,);

        beta = ./(*val_even);

        val_odd = sum(Aodd,);

        gamma = ./(*val_odd);

        alpha =  - beta - gamma;

        Sv = sparse(no,no);

        Sv(interior,:) = ...

            sparse(:ni, interior, alpha(interior), ni, no) + ...

            bsxfun(@times, Aeven(interior,:), beta(interior)./val_even(interior)) + ...

            bsxfun(@times, Aodd(interior,:), gamma(interior)./val_odd(interior));

        Sboundary = ...

            sparse([O(:,);O(:,)],[O(:,);O(:,)],/,no,no) + ...

            sparse([O(:,);O(:,)],[O(:,);O(:,)],/,no,no);

        Sv(boundary,:) = Sboundary(boundary,:);

        %% Sf

        Sf = / .* sparse(repmat((:nf)',1 ,4), FF, 1);

        i0 = no + (:nf)';

        %% Se

        flaps = sparse([idx;idx], ...

                       [FF(:,) FF(:,);FF(:,) FF(:,);FF(:,) FF(:,);FF(:,) FF(:,)], ...

                       );

        onboundary = (sum(flaps,) == );

        flaps(onboundary,:) = ;

        ne = size(E,);

        Se = sparse( ...

                [:ne :ne]', ...

                [E(:,); E(:,)], ...

                [onboundary;onboundary].*/ + ~[onboundary;onboundary].*/, ...

                ne, ...

                no) + ...

                flaps*/;

        %% new faces & new vertices

        i1 = no +   nf + (:nf)';

        i2 = no + *nf + (:nf)';

        i3 = no + *nf + (:nf)';

        i4 = no + *nf + (:nf)';

        FFtmp = [i0 i4 FF(:,) i1; ...

                 i0 i1 FF(:,) i2; ...

                 i0 i2 FF(:,) i3; ...

                 i0 i3 FF(:,) i4];

        reidx = [(:no)'; no+(1:nf)'; no+nf+idx];

        FF = reidx(FFtmp);

        S = [Sv; Sf; Se];

        VV = S*VV;

    end

 end

Loop subdivision：

　　Loop细分是一种三角形网格的细分法则，它按照1-4三角形分裂，每条边计算生成一个新的顶点，同时每个原始顶点更新位置。下图为Loop细分格式的细分掩膜，对于新增加的顶点位置以及原始顶点位置更新规则如下：

1.网格内部V-顶点位置：

　　设内部顶点v的相邻点为v、v，…，v，则该顶点更新后位置为，其中。

2.网格边界V-顶点位置：

　　设边界顶点v的两个相邻点为v、v，则该顶点更新后位置为v = 3/4*v + 1/8*(v + v)。

3.网格内部E-顶点位置：

　　设内部边的两个端点为v、v，相对的两个顶点为v、v，则新增加的顶点位置为v = 3/8*(v + v) + 1/8*(v + v)。

4.网格边界E-顶点位置：

　　设边界边的两个端点为v、v，则新增加的顶点位置为v = 1/2*(v + v)。

效果：

本文为原创，转载请注明出处：http://www.cnblogs.com/shushen。