﻿ 基于顶点法向量约束的Catmull-Clark细分插值方法
 计算机系统应用  2018, Vol. 27 Issue (11): 211-217 PDF

Catmull-Clark Subdivision Interpolation Based on Vertex Normal Vector Constraint
LIN Chuan-Luan
Computer & Cultural Innovation Department, Fuzhou Melbourne Polytechnic, Fuzhou 350108, China
Foundation item: Natural Science Foundation of Fujian Province (2010J01318)
Abstract: A new scheme for constructing a two steps Catmull-Clark subdivision surface with the vertex normal vector constraint interpolates the vertices of a quadrilateral mesh with arbitrary topology. Firstly, the new mesh is generated by the modified Catmull-Clark subdivision. Secondly, the new mesh is adjusted through vertex normal vector constraints. The two-phase scheme makes the limit surface interpolate all vertices and normal vector in the original mesh by applying the progressive iterative method and the Lagrange multiplier method respectively. The experimental examples are given to show that the method is effective both in interpolating initial control points and normal vector, the limit surface has good modeling effect.
Key words: Catmull-Clark subdivision     interpolation     normal vector     progressive iterative     Lagrange multiplier

1 顶点法向量插值条件

 {S_4} = \left[ {\begin{aligned} 9&\quad {\displaystyle\frac{3}{2}}&{\displaystyle\frac{3}{2}}&\quad {\displaystyle\frac{3}{2}}&{\displaystyle\frac{3}{2}}&\quad {\displaystyle\frac{1}{4}}&{\displaystyle\frac{1}{4}}&\quad {\displaystyle\frac{1}{4}}&{\displaystyle\frac{1}{4}} \\ 6&\quad 6&1&\quad 0&1&\quad 1&0&\quad 0&1 \\ 6&\quad 1&6&\quad 1&0&\quad 1&1&\quad 0&0 \\ 6&\quad 0&1&\quad 6&1&\quad 0&1&\quad 1&0 \\ 6&\quad 1&0&\quad 1&6&\quad 0&0&\quad 1&1 \\ 4&\quad 4&4&\quad 0&0&\quad 4&0&\quad 0&0 \\ 4&\quad 0&4&\quad 4&0&\quad 0&4&\quad 0&0 \\ 4&\quad 0&0&\quad 4&4&\quad 0&0&\quad 4&0 \\ 4&\quad 4&0&\quad 0&4&\quad 0&0&\quad 0&4 \end{aligned}} \right]*\frac{1}{{16}}

Halstead通过对Doo-Sabin细分进行分析获得细分矩阵 ${S_n}$ 与极限曲面的性质, 可以推广到Loop细分与Catmull-Clark细分, 同时给出了 ${S_n}$ 的左特征向量与极限法向量的关系, 从而推导出极限顶点法向量的计算方法.

Catmull-Clark细分中细分矩阵 ${S_n}$ 的主特征值 ${\lambda _1} = 1$ , 相对应的左特征向量 ${l_1} = \left[ {{n^2},4,\cdots,4,1,\cdots,1} \right]/$ $[n(n + 5)]$ , 则:

 ${v^\infty } = \displaystyle\frac{{{n^2}v + 4\displaystyle\sum\limits_j {{e_j}} + 4\sum\limits_j {{f_j}} }}{{n(n + 5)}}$ (1)

 \begin{aligned}{l_2} = &(0,{A_n}\cos \displaystyle\frac{{2\pi }}{n},{A_n}\cos \frac{{2\pi *2}}{n},\cdots,{A_n}\cos \frac{{2\pi *n}}{n},\\&\cos \displaystyle\frac{{2\pi }}{n} + \cos \frac{{2\pi *2}}{n},\cos \frac{{2\pi *2}}{n} + \cos \frac{{2\pi *3}}{n},\cdots,\\& \cos \displaystyle\frac{{2\pi *n}}{n} + \cos \frac{{2\pi *(n + 1)}}{n}\\ {l_3} = &(0,{A_n}\sin \displaystyle\frac{{2\pi }}{n},{A_n}\sin \frac{{2\pi *2}}{n},\cdots,{A_n}\sin \frac{{2\pi *n}}{n},\\& \sin \displaystyle\frac{{2\pi }}{n} + \sin \frac{{2\pi *2}}{n},\sin \frac{{2\pi *2}}{n} + \sin \frac{{2\pi *3}}{n},\cdots,\\& \sin \frac{{2\pi *n}}{n} + \sin \frac{{2\pi *(n + 1)}}{n}\end{aligned}

 \begin{aligned}& {n^\infty } = \Bigg\{ \displaystyle\sum\nolimits_j {\Bigg[{A_n}} \cos \frac{{2\pi j}}{n}{e_j} + \left(\cos \frac{{2\pi j}}{n} + \cos \frac{{2\pi (j + 1)}}{n}\right){f_j}\Bigg]\Bigg\} \\ &\quad \quad \times \Bigg\{ \sum\nolimits_j {\Bigg[{A_n}} \sin \frac{{2\pi j}}{n}{e_j} + \left(\sin \frac{{2\pi j}}{n} + \sin \frac{{2\pi (j + 1)}}{n}\right){f_j}\Bigg]\Bigg\}\end{aligned} (2)
2 两步Catmull-Clark细分插值方法

1) 拓扑规则与传统的Catmull-Clark细分方法保持不变;

2) 几何规则中, 新边点和新面点与传统的Catmull-Clark细分方法保持不变. 新顶点的取法修改为:

 ${v^1} = \lambda {v^0} + (1 - \lambda )[\alpha { E} + (1 - \alpha ){ F}]$ (3)

 $v_\infty ^1 = \displaystyle\frac{{({n^2}\lambda + 7n/4){v^1} + {\beta _n}\displaystyle\sum\nolimits_{i = 1}^n {e_i^1 + \frac{3}{{10}}{\beta _n}\sum\nolimits_{i = 1}^n {f_i^1} } }}{{n(n + 5)}}$

 \begin{aligned}{d^{k + 1}} & = {v^0} - v_\infty ^{k + 1} = {v^0} - \displaystyle\frac{{\left({n^2}\lambda + \displaystyle\frac{7}{4}n\right){v^{k + 1}} + \left[n\left(1 - \lambda \right)\displaystyle\frac{{10}}{{13}} + \displaystyle\frac{5}{2}\right]\sum\nolimits_i {e_i^{k + 1}} + \left[n\left(1 - \lambda \right)\displaystyle\frac{3}{{13}} + \displaystyle\frac{3}{4}\right]\sum\nolimits_i {f_i^{k + 1}} }}{{n\left(n + 5\right)}}\\ & = {d^k} -\displaystyle\frac{{\left({n^2}\lambda + \displaystyle\frac{7}{4}n\right){d^k} + \left[n\left(1 - \lambda \right)\displaystyle\frac{{10}}{{13}} + \displaystyle\frac{5}{2}\right]\sum\nolimits_i {d_{e_i^k}^k} + \left[n\left(1 - \lambda \right)\displaystyle\frac{3}{{13}} + \displaystyle\frac{3}{4}\right]\sum\nolimits_i {d_{f_i^k}^k} }}{{n\left(n + 5\right)}} = 0\end{aligned}

3 插值法向量分析

 $\begin{array}{l}{C_2} = \displaystyle\sum\nolimits_{i = 1}^n {\Bigg[{A_n}\cos \frac{{2\pi i}}{n}} e_i^1 + \left(\cos \frac{{2\pi i}}{n} + \cos \frac{{2\pi (i + 1)}}{n}\right)f_i^1\Bigg]\\{C_3} = \displaystyle\sum\nolimits_{i = 1}^n {\Bigg[{A_n}\sin \frac{{2\pi i}}{n}} e_i^1 + \left(\sin \frac{{2\pi i}}{n} + \sin \frac{{2\pi (i + 1)}}{n}\right)f_i^1\Bigg]\end{array}$

 \begin{aligned}\widetilde N &= \{ 0*{v^1} + \sum\nolimits_{i = 1}^n {\left[ {{A_n}\cos \frac{{2\pi i}}{n}\left(e_i^1 + {\delta _i}\right) + \left(\cos \frac{{2\pi i}}{n} + \cos \frac{{2\pi (i + 1)}}{n}\right)} \right.} \Bigg.\Bigg. {\left(f_i^1 + {\delta _i}\right)} \Bigg]\Bigg\} \\&\;\;\;\;\times\Bigg\{ 0*{v^1} +\sum\nolimits_{i = 1}^n {\left[ {{A_n}\sin \frac{{2\pi i}}{n}\left(e_i^1 + {\delta _i}\right) } \right.} + \left(\sin \frac{{2\pi i}}{n} + \sin \frac{{2\pi (i + 1)}}{n}\right) \left. {\left. {\left(f_i^1 + {\delta _i}\right)} \right]} \right\} \\&=\Bigg\{ {C_2} + \sum\nolimits_{i = 1}^n {\left. {{A_n}\cos \frac{{2\pi i}}{n}{\delta _i}} \right]} \Bigg\} + \left(\cos \frac{{2\pi i}}{n} + \cos \frac{{2\pi (i + 1)}}{n}\right){\delta _i}\times\Bigg\{ {C_3} + \sum\nolimits_{i = 1}^n {\Bigg[{A_n}\sin \frac{{2\pi i}}{n}{\delta _i} + \left(\sin \frac{{2\pi i}}{n} + \sin \frac{{2\pi (i + 1)}}{n}\right){\delta _i}\Bigg]} \Bigg\} \\&= \Bigg({C_2} + \sum\nolimits_{i = 1}^n {{a_i}{\delta _i}\Bigg) \times } \Bigg({C_3} + \sum\nolimits_{i = 1}^n {{b_i}{\delta _i}\Bigg)} \\ &{a_i} = \sum\nolimits_{i = 1}^n {\Bigg[{A_n}\cos \frac{{2\pi i}}{n} + \Bigg(\cos \frac{{2\pi i}}{n} + \cos \frac{{2\pi (i + 1)}}{n}\Bigg)\Bigg]} ,\; {b_i} = \sum\nolimits_{i = 1}^n {\Bigg[{A_n}\sin \frac{{2\pi i}}{n} + \Bigg(\sin \frac{{2\pi i}}{n} + \sin \frac{{2\pi (i + 1)}}{n}\Bigg)\Bigg]} \end{aligned} (4)

 $({C_2} + \sum\nolimits_{i = 1}^n {{a_i}} {\delta _i}) \bot {N^\infty }$ (5)
 $({C_3} + \sum\nolimits_{i = 1}^n {{b_i}} {\delta _i}) \bot {N^\infty }$ (6)

 $\min \;\;\; \sum\nolimits_{i = 1}^n {{\delta _i}*} {\delta _i}$ (7)

s.t.

 $({C_2} + \sum\nolimits_{i = 1}^n {{a_i}} {\delta _i})*{N^\infty } = 0$ (8)
 $({C_3} + \sum\nolimits_{i = 1}^n {{b_i}} {\delta _i})*{N^\infty } = 0$ (9)

 $\begin{gathered} F = \sum\nolimits_{i = 1}^n {{\delta _i}*{\delta _i} + {\omega _1}} ({C_2} + \sum\nolimits_{i = 1}^n {{a_i}} {\delta _i})*{N^\infty } \hfill \\ \quad + {\omega _1}({C_3} + \sum\nolimits_{i = 1}^n {{b_i}} {\delta _i})*{N^\infty } \hfill \\ \end{gathered}$

$\displaystyle\frac{{dF}}{{d{\delta _i}}} = 0$ , 因此有:

 $\frac{{dF}}{{d{\delta _k}}} = 2{\delta _k} + {\omega _1}{a_k}{N^\infty } + {\omega _2}{b_k}{N^\infty } = 0,(k = 1,2,\cdots,n)$ (10)

 ${\delta _k} = - \frac{1}{2}({\omega _1}{a_k}{N^\infty } + {\omega _2}{b_k}{N^\infty })$ (11)

 $2{C_2}*{N^\infty } - {\omega _1}\sum\nolimits_{i = 1}^n {a_i^2} {N^{\infty 2}} - {\omega _2}\sum\nolimits_{i = 1}^n {{a_i}{b_i}} {N^{\infty 2}} = 0$
 $2{C_3}*{N^\infty } - {\omega _1}\sum\nolimits_{i = 1}^n {{a_i}{b_i}} {N^{\infty 2}} - {\omega _2}\sum\nolimits_{i = 1}^n {b_i^2} {N^{\infty 2}} = 0$

 ${\omega _1} = \frac{{2{C_2}*{N^\infty }}}{{\displaystyle\sum\nolimits_{i = 1}^n {a_i^2} {N^{\infty 2}}}}$
 ${\omega _2} = \frac{{2{C_3}*{N^\infty }}}{{\displaystyle\sum\nolimits_{i = 1}^n {b_i^2} {N^{\infty 2}}}}$

 ${\delta _k} = - \frac{1}{2}\left(\frac{{2{C_2}*{N^\infty }}}{{\displaystyle\sum\nolimits_{i = 1}^n {a_i^2} {N^{\infty 2}}}}{a_k} + \frac{{2{C_3}*{N^\infty }}}{{\displaystyle\sum\nolimits_{i = 1}^n {b_i^2} {N^{\infty 2}}}}{b_k}\right){N^\infty }$
4 实验结果与分析

 图 1 基于顶点法向量约束的两步Catmull-Clark细分插值方法(正方体形)

 图 2 基于顶点法向量约束的两步Catmull-Clark细分插值方法(圆环形)

 图 3 基于顶点法向量约束的两步Catmull-Clark细分插值方法(圆锥形)

 图 4 基于顶点法向量约束的两步Catmull-Clark细分插值方法(正方体与球形)

5 结语

 [1] 林淑金. 插值逼近融合的曲面造型方法研究与应用[博士学位论文]. 广州: 中山大学, 2008. [2] Hassan MF, Ivrissimitzis IP, Dodgson NA, et al. An interpolating 4-point C2 ternary stationary subdivision scheme. Computer Aided Geometric Design, 2002, 19(1): 1-18. DOI:10.1016/S0167-8396(01)00084-X [3] Shi Z, Lin SJ, Luo XN, et al. Interpolatory and mixed loop schemes. Computer Graphics Forum, 2008, 27(7): 1829-1835. DOI:10.1111/cgf.2008.27.issue-7 [4] 王国瑾, 汪国昭, 郑建民. 计算机辅助几何设计. 北京: 高等教育出版社, 2001. [5] Catmull E, Clark J. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design, 1978, 10(6): 350-355. DOI:10.1016/0010-4485(78)90110-0 [6] Kobbelt L. Interpolatory subdivision on open quadrilateral nets with arbitrary topology. Computer Graphics Forum, 1996, 15(3): 409-420. DOI:10.1111/cgf.1996.15.issue-3 [7] Hoppe H, DeRose T, Duchamp M, et al. Piecewise smooth surface reconstruction. Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques. New York, NY, USA. 1994. 295–302. [8] Nasri AH. Polyhedral subdivision methods for free-form surfaces. ACM Transactions on Graphics, 1987, 6(1): 29-73. DOI:10.1145/27625.27628 [9] Brunet P. Including shape handles in recursive subdivision surfaces. Computer Aided Geometric Design, 1988, 5(1): 41-50. DOI:10.1016/0167-8396(88)90019-2 [10] Halstead M, Kass M, DeRose T. Efficient, fair interpolation using Catmull-Clark surfaces. Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques. Anaheim, CA, USA. 1993. 35–44. [11] Zheng J, Cai Y. Interpolation over arbitrary topology meshes using a two-phase subdivision scheme. IEEE Transactions on Visualization and Computer Graphics, 2006, 12(3): 301-310. DOI:10.1109/TVCG.2006.49 [12] Chen ZX, Luo XN, Tan L, et al. Progressive interpolation based on Catmull-Clark subdivision surfaces. Computer Graphics Forum, 2008, 27(7): 1823-1827. DOI:10.1111/cgf.2008.27.issue-7 [13] 林晓晶, 潘日晶. 一种基于Loop细分的渐进插值方法. 福建师范大学学报(自然科学版), 2014, 30(1): 18-24. [14] 林传銮, 潘日晶, 陈青, 等. 基于形状控制的细分曲面的局部渐进插值方法. 计算机系统应用, 2015, 24(7): 104-110. DOI:10.3969/j.issn.1003-3254.2015.07.019 [15] 郭华源, 秦开怀, 孙丰. 基于渐进插值的Catmull-Clark双正交细分小波及其应用. 计算机辅助设计与图形学学报, 2017, 29(6): 1118-1127. DOI:10.3969/j.issn.1003-9775.2017.06.018 [16] Bénard P, Hertzmann A, Kass M. Computing smooth surface contours with accurate topology. ACM Transactions on Graphics, 2014, 33(2): 19. [17] Wei XD, Zhang YJ, Hughes TJR, et al. Extended truncated hierarchical Catmull-Clark subdivision. Computer Methods in Applied Mechanics and Engineering, 2016, 299: 316-336. DOI:10.1016/j.cma.2015.10.024 [18] Wang JZ, Cheng FH. G2 Interpolation for polar surfaces. Computer-Aided Design and Applications, 2016, 13(5): 610-617. DOI:10.1080/16864360.2016.1150705 [19] 林晓晶. 基于三角网格逼近型细分的插值方法[硕士学位论文]. 福州: 福建师范大学, 2014.