三维网格补洞算法(Radial Basis Function)

  在逆向工程被,由于配备或者模型的由来,我们得得到的老三维模型数据往往并无完,从而让生成的网格模型有漏洞,这对准接轨之模子解析会导致影响。下面介绍一种植基于径向基函数(RBF:Radial
Basis Function)的三角网格补洞方法。

Step 1:检测孔洞边界

  三角网格是由同样系列顶点(V)以及由于这些极端所成的三角形面片(F)所结合,由三角面片可以落网格的边(E)。通常一漫长边连接两只三角面片,这种边称为网格内界限,而要某条边仅连接一个三角面片,那么称这漫长边也网格边界边,所有的分界边按顺序连接之后便形成了网格的窟窿。

766游戏网官网 1

Step 2:初始化网格

  为了使孔洞填充简单、健壮,可以利用最小角度法开展网格修补,具体步骤如下:

  (1)得到孔洞边界点信息,计算边界边长度的平均值l

  (2)计算每个边界点的片长条相互邻边的夹角大小。

  (3)找有装有极其小夹角的边界点,计算其的蝇头单相邻边界点的相距s,判断s <
l是不是建:若建立,则仍下图所出示增加一个三角,若无成立则增加有限单三角。

  (4)更新边界点消息。

  (5)判断孔洞是否修补完,若未完全,转(2),否则结束。

766游戏网官网 2

766游戏网官网 3

Step 3:最小二乘胜网格

  初始化补洞得到的网格质量无是可怜好,我们要优化网格顶点的职位,优化的原则是:

766游戏网官网 4

其中di为顶点vi的1环邻域顶点数。

  上式可以据此一个线性方程组来描述:**LV

0**,其中L是Laplace矩阵,具体形式也766游戏网官网 5,矩阵L的秩等于n

k,n为网格顶点的多少,k为网格连通区域的个数,如果网格是全连通的,那么矩阵L的秩是n
– 1。因此如果我们如果如方程有解,需要加入m(m ≥
k)个控制顶点坐标vs作方程的疆界条件,在实质上中我们以初始化网格的境界顶点作为控制顶点。

  其实上述线性方程组的求解等价于如下能量函数最小化的求解:

766游戏网官网 6

  能量函数的首先有些凡是教网格顶点尽量光滑,即每个终端位于该1缠绕邻域顶点的核心,第二局部凡是为控制顶点的岗位满足要求。

  最小二乘机网格的优势是能够好成高质量的滑网格,生成过程仅需网格的拓扑连接关系及少数控制点的坐标信息。

766游戏网官网 7

Step
4:径向基函数(RBF)隐式曲面

  径向基函数是一个不过凭借让距离控制点c距离的函数,即h(x,c)
= h(||x –
c||),距离通常是欧式距离,也足以是别花样距离。径向基函数网络是一个叔重合BP网络,其得以代表也多只基函数的线性组合:

766游戏网官网 8

  下面列有2个顶常用之基函数形式:

  (1)Gaussian:h(r) =
e-(εr)2

  (2)Polyharmonic spline:h(r) =
rk,k = 1、3、5、… 或h(r) = rkln(r),k =
2、4、6、…

  用为基函数网并透过为一定控制点xi以及相应的值fi后,可以求解得到网络被的系数λi,因此于基函数大网会缓解空间杂乱无章数据点的平滑插值问题,函数的零等值面就是咱要求的曲面。

  以事实上求解时函数f(x)表达式中便会多一个均等蹩脚多项式P(x),如下:

766游戏网官网 9,其中:766游戏网官网 10

  将控制点位置xi和值fi替入函数f(x)可以获取如下方程,求解之后即可确定隐式曲面f(x)。

766游戏网官网 11

  控制点xi唯独分为三类:

  (1)边界控制点:曲面通过之触发,f(xi)
= 0

  (2)外部控制点:将边界控制点沿法向正要方向走一小截距离要收获的控制点,取f(xi)
= -1

  (3)内部控制点:将边界控制点沿法向负方向移动一稍微截距离要博的控制点,取f(xi)
= 1

  计算时我们挑选的基函数为h(r) =
r3,其实此时隐式曲面函数满足Δ3f =
0,将基函数替入后拿走隐式曲面的表达式如下:

766游戏网官网 12

766游戏网官网 13

766游戏网官网 14766游戏网官网 15

function options = RBF_Create(x, y, type)
    % x: input data; y: input data value
    options = [];
    options.nodes = x;
    switch type
        case 'linear'
            options.phi = @rbfphi_linear;
        case 'cubic'
            options.phi = @rbfphi_cubic;
    end    

    [n, dim] = size(x);
    A = zeros(n,n);
    for i = 1:n
        r = normrow(bsxfun(@minus, x(i,:), x));
        temp = feval(options.phi, r);
        A(i,:) = temp';
        A(:,i) = temp;
    end
    % Polynomial part
    P = [ones(n,1) x];
    A = [ A      P
          P' zeros(dim+1, dim+1)];
    B = [y; zeros(dim+1, 1)];

    coeff = A\B;
    options.coeff = coeff;
end

% Radial Base Functions
function u = rbfphi_linear(r)
    u = r;
end
function u = rbfphi_cubic(r)
    u = r.*r.*r;
end

View Code

Step 5:牛顿插值

  为了赢得插值隐式曲面的网格,我们得将最好小二就网格的巅峰投射到隐式曲面上,这里我们下牛顿迭代法:

766游戏网官网 16

  最小二随着网格的极限位置作迭代初始标准,当||xk+1
– xk|| <
ε时,迭代住,ε为设定的误差。上式中梯度表达式如下:

766游戏网官网 17

766游戏网官网 18

766游戏网官网 19

效果:

766游戏网官网 20

766游戏网官网 21

766游戏网官网 22

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

 

 

参考文献:

[1] Olga Sorkine and Daniel Cohen-Or.

  1. Least-Squares Meshes. In Proceedings of the Shape Modeling
    International 2004 (SMI ’04). IEEE Computer Society, Washington, DC,
    USA, 191-199.

[2] Greg Turk and James F. O’Brien.

  1. Shape transformation using variational implicit functions. In
    Proceedings of the 26th annual conference on Computer graphics and
    interactive techniques (SIGGRAPH ’99). ACM Press/Addison-Wesley
    Publishing Co., New York, NY, USA, 335-342.

[3] 袁天然.
三角网格模型光顺简化和补技术之研讨以及下[D]. 南京航空航天大学,
2007.

发表评论

电子邮件地址不会被公开。 必填项已用*标注