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

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

Step 1:检测孔洞边界

  三角网格是由同文山会海顶点(V)以及由于这些极所结合的三角面片(F)所构成,由三角面片可以抱网格的边(E)。通常一漫漫边连接两单三角形面片,这种边称为网格中界限,而设某条边仅连接一个三角形面片,那么称这漫漫边也网格边界边,所有的境界边按梯次连接之后就形成了网格的孔洞。

图片 1

Step 2:初始化网格

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

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

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

  (3)找来有最小夹角的边界点,计算其的少个相邻边界点的离开s,判断s <
l是否成立:若建立,则按下图所著增加一个三角,若未树立则增加有限单三角形。

  (4)更新边界点消息。

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

图片 2

图片 3

Step 3:最小二趁网格

  初始化补洞得到的网格质量未是异常好,我们要优化网格顶点的职,优化的条件是:

图片 4

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

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

0**,其中L是Laplace矩阵,具体形式也图片 5,矩阵L的秩等于n

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

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

图片 6

  能量函数的第一片段凡是使网格顶点尽量光滑,即每个终端位于该1围邻域顶点的骨干,第二部分是为控制顶点的职位满足要求。

  最小二随着网格的优势是能够非常成胜质量之滑网格,生成过程只是用网格的拓扑连接关系及少数控制点的坐标信息。

图片 7

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

  径向基函数是一个不过靠让距离控制点c距离的函数,即h(x,c)
= h(||x –
c||),距离通常是欧式距离,也可是任何花样距离。径向基函数网是一个叔重叠BP网络,其得以象征也多只基函数的线性组合:

图片 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),如下:

图片 9,其中:图片 10

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

图片 11

  控制点xi不过分为三类:

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

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

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

  计算时我们选取的基函数为h(r) =
r3,其实这隐式曲面函数满足Δ3f =
0,将基函数代表入后收获隐式曲面的表达式如下:

图片 12

图片 13

图片 14图片 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:牛顿插值

  为了取插值隐式曲面的网格,我们需要将极小二随着网格的顶峰投射到隐式曲面上,这里我们使用牛顿迭代法:

图片 16

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

图片 17

图片 18

图片 19

效果:

图片 20

图片 21

图片 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.

发表评论

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