基于边长的三维形状插值

doi:10.11996/JG.j.2095-302X.2023010158

图学学报 ›› 2023, Vol. 44 ›› Issue (1): 158-165.DOI: 10.11996/JG.j.2095-302X.2023010158

• 计算机图形学与虚拟现实 • 上一篇下一篇

基于边长的三维形状插值

刘振晔(), 陈仁杰(), 刘利刚

中国科学技术大学数学科学学院，安徽合肥 230022

收稿日期:2022-06-16 修回日期:2022-08-06 出版日期:2023-10-31 发布日期:2023-02-16
通讯作者: 陈仁杰
作者简介:刘振晔(1997-)，男，硕士研究生。主要研究方向为数字几何处理。E-mail：lzy1997@mail.ustc.edu.cn
基金资助:
国家自然科学基金项目(62072422);国家自然科学基金项目(62025207);安徽省自然科学基金项目(2008085MF195)

Edge length based 3D shape interpolation

LIU Zhen-ye(), CHEN Ren-jie(), LIU Li-gang

School of Mathematical Sciences, University of Science and Technology of China, Hefei Anhui 230022, China

Received:2022-06-16 Revised:2022-08-06 Online:2023-10-31 Published:2023-02-16
Contact: CHEN Ren-jie
About author:LIU Zhen-ye (1997-), master student. His main research interest covers digital geometry processing. E-mail：lzy1997@mail.ustc.edu.cn
Supported by:
National Natural Science Foundation of China(62072422);National Natural Science Foundation of China(62025207);Natural Science Foundation of Anhui Province(2008085MF195)

摘要/Abstract

摘要：

形状插值在计算机图形学和几何处理中是一个极其重要而基础的问题，在计算机动画等领域有着广泛应用。注意到在平面三角网格和三维四面体网格插值问题中，对边长平方插值等价于对回拉度量进行插值，因此具有等距扭曲和共形扭曲同时有界的良好性质。通过将其推广至曲面三角网格，提出了一种完全基于边长的曲面三角网格插值算法。给定边长，在重建网格阶段，使用牛顿法对边长误差能量进行优化。并且给出了其海森矩阵的解析正定化形式，从而避免了高代价的特征值分解步骤。注意到四面体网格的边长平方插值结果具有极低曲率，意味着只需少许修改即可将其压平从而嵌入三维空间。因此提出先将曲面三角网格四面体化，再从四面体网格的插值结果提取表面。然后将这表面作为初始化用于边长误差能量的牛顿迭代，从而使得收敛结果更加接近全局最优。在一系列三角网格上进行了实验，结果说明了本文方法比之前方法的边长误差更小，且得到的结果还是有界扭曲的。

关键词: 变形, 形状插值, 计算机图形学, 曲面三角网格

Abstract:

Shape interpolation is of important and fundamental significance to computer graphics and geometry processing, which is widely employed in computer animation and other fields. It is noted that for planar triangular meshes and 3D tetrahedral meshes, interpolating squared edge lengths is equivalent to interpolating pullback metric. Therefore, it has the good property that isometric distortion and conformation distortion are bounded simultaneously. A triangular mesh interpolation algorithm based on edge lengths was proposed by extending that to triangular meshes. Given the edge lengths, the edge length error energy was optimized using Newton's method in the stage of mesh reconstruction. In addition, the costly eigenvalue decomposition could be avoided by giving the analytic positive definite form of its Hessian matrix. It was noted that the interpolation of squared edge lengths of the tetrahedral meshes resulted in very low curvature, meaning that it could be flattened and embedded in 3D space with only a few modifications. Therefore, we proposed to first convert the triangular meshes into tetrahedral meshes, and then extract the surface from the interpolation result of the tetrahedral meshes. After that the surface served as an initialization on the Newton iteration of the edge length error energy, thus bringing the convergence result closer to the global optimum. Experiments performed on a series of triangular meshes show that the proposed method leads to smaller edge length error than that of previous edge length-based methods, and that the results obtained have bounded distortion.

Key words: morphing, shape interpolation, computer graphics, triangular mesh

中图分类号:

TP391

刘振晔, 陈仁杰, 刘利刚. 基于边长的三维形状插值[J]. 图学学报, 2023, 44(1): 158-165.

LIU Zhen-ye, CHEN Ren-jie, LIU Li-gang. Edge length based 3D shape interpolation[J]. Journal of Graphics, 2023, 44(1): 158-165.

图/表 9

图1 2个长条之间的插值结果

Fig. 1 Interpolation result between two bars ((a) t=0; (b) t=0.1; (c) t=1.0)

表1 在t=0.5时刻不同初始化方法得到的结果的L值(10-3)

Table 1 L of the results obtained by different initialization methods when t=0.5 (10-3)

Method	Airplane	Armadillo	Bar	Bird	Bust	Camel	Cat
FFMP	2.50	0.86	4.59	0.18	3.44	1.45	3.85
ARAP	3.58	4.17	7.46	1.50	2.43	2.21	5.51
GE	0.65	0.16	9.62	0.16	2.21	0.48	2.09
ABF	0.59	0.18	13.80	0.23	2.70	0.74	7.50
SQP	0.29	0.15	8.74	0.10	1.24	0.38	0.81

图2 表1中的Airplane模型的能量变化情况

Fig. 2 Energy change of the Airplane model in table 1

图3 当t=0.5时Airplane网格的插值结果

Fig. 3 Interpolation results of the Airplane model when t=0.5 ((a) Source; (b) FFMP; (c) ARMP; (d) GE; (e) ABF; (f) SQP; (g) Target)

图4 部分模型的插值结果

Fig. 4 Interpolation results of some models ((a) t=0.00; (b) t=0.25; (c) t=0.50; (d) t=0.75; (e) t=1.00)

图5 在t=0.5时不同方法得到的插值结果的比较

Fig. 5 Comparison of interpolation results obtained by different methods when t=0.5 ((a) Source; (b) Ours; (c) ELI; (d) MSGI; (e) LSRDF; (f) Target)

图6 不同方法在图5的模型下得到的插值结果的误差

Fig. 6 Errors of interpolation results obtained by different methods under the models in Fig. 5 ((a) Armadillo; (b) Bird)

图7 不同方法在图5的模型下得到的插值结果的扭曲

Fig. 7 Distortions of interpolation results obtained by different methods under the models in Fig. 5 ((a) Armadillo; (b) Bird)

表2 当插值100帧时4种方法的时间对比(s)

Table 2 Time Comparison of four methods when interpolating 100 frames (s)

Method	Armadillo	Bar	Cat
Ours	4367	366	4270
ELI	6239	416	4253
MSGI	16528	315	13477
LSRDF	388	37	355

参考文献 18

[1]	金小刚, 鲍虎军, 彭群生. 计算机动画技术综述[J]. 软件学报, 1997, 8(4): 241-251.
	JIN X G, BAO H J, PENG Q S. A survey of computer animation[J]. Journal of Software, 1997, 8(4): 241-251 (in Chinese).
[2]	WANG Y, LIU B, TONG Y. Linear surface reconstruction from discrete fundamental forms on triangle meshes[J]. Computer Graphics Forum, 2012, 31(8): 2277-2287. DOI URL
[3]	WINKLER T, DRIESEBERG J, ALEXA M, et al. Multi-scale geometry interpolation[J]. Computer Graphics Forum, 2010, 29(2): 309-318. DOI URL
[4]	FRÖHLICH S, BOTSCH M. Example-driven deformations based on discrete shells[J]. Computer Graphics Forum, 2011, 30(8): 2246-2257. DOI URL
[5]	CHEN R J, WEBER O, KEREN D, et al. Planar shape interpolation with bounded distortion[J]. ACM Transactions on Graphics, 2013, 32(4): 108.
[6]	AHARON I, CHEN R J, ZORIN D, et al. Bounded distortion tetrahedral metric interpolation[J]. ACM Transactions on Graphics, 2019, 38(6): 182.
[7]	ROJAS C, TSUI A, HE S, et al. Edge length interpolation[EB/OL]. [2022-03-14]. https://web.cs.ucdavis.edu/-amenta/pubs/eld.pdf.
[8]	SEDERBERG T W, GAO P, WANG G, et al. 2D shape blending: an intrinsic solution to the vertex path problem[EB/OL]. [2022-03-08]. https://dl.acm.org/doi/pdf/10.1145/166117.166118.
[9]	ALEXA M, COHEN-OR D, LEVIN D. As-rigid-as-possible shape interpolation[C]//The 27th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 2000: 157-164.
[10]	GAO L, LAI Y K, HUANG Q X, et al. A data-driven approach to realistic shape morphing[J]. Computer Graphics Forum, 2013, 32(2pt4): 449-457. DOI URL
[11]	AYDINLILAR M, SAHILLIOĞLU Y. Part-based data-driven 3D shape interpolation[J]. Computer-Aided Design, 2021, 136: 103027. DOI URL
[12]	BANSAL S, TATU A. Lie bodies based 3D shape morphing and interpolation[C]//The 15th ACM SIGGRAPH European Conference on Visual Media Production. New York: ACM, 2018: 1-10.
[13]	EISENBERGER M, NOVOTNY D, KERCHENBAUM G, et al. Neuromorph: unsupervised shape interpolation and correspondence in one go[C]//2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 2021: 7473-7483.
[14]	ZHANG F. The schur complement and its applications[M]. Berlin: Springer Science & Business Media, 2006: 34-35.
[15]	KIRCHER S, GARLAND M. Free-form motion processing[J]. ACM Transactions on Graphics, 2008, 27(2): 1-13.
[16]	CHAO I, PINKALL U, SANAN P, et al. A simple geometric model for elastic deformations[J]. ACM Transactions on Graphics, 2010, 29(4): 1-6.
[17]	PAILLÉ G P, RAY N, POULIN P, et al. Dihedral angle-based maps of tetrahedral meshes[J]. ACM Transactions on Graphics, 2015, 34(4): 1-10.
[18]	YANG Y, FU X M, CHAI S, et al. Volume-enhanced compatible remeshing of 3D models[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 25(10): 2999-3010. DOI URL

基于边长的三维形状插值

Edge length based 3D shape interpolation

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 18

相关文章 15

编辑推荐

Metrics

本文评价

[1]	高昂, 梁兴柱, 夏晨星, 张春炯. 一种改进YOLOv8的密集行人检测算法[J]. 图学学报, 2023, 44(5): 890-898.
[2]	王涵 , 朱春钢 . 基于伸缩因子的 toric-Bézier 曲线自由变形[J]. 图学学报, 2022, 43(6): 1070-1079.
[3]	马彦博, 李琳, 陈缘, 赵洋, 胡锐. 基于时空融合的多帧压缩视频增强方法[J]. 图学学报, 2022, 43(4): 651-658.
[4]	李华恩, 赵洋, 陈缘, 张效娟. 基于递归对齐网络的黑白老卡通高清重制[J]. 图学学报, 2022, 43(3): 434-442.
[5]	桂杰, 曹力, 伯彭波, 顾兆光. 面向可展特征的网格模型去噪方法[J]. 图学学报, 2022, 43(3): 453-460.
[6]	沙浩, 刘越. 基于深度学习的图像本征属性预测方法综述[J]. 图学学报, 2021, 42(3): 385-397.
[7]	肖文磊, 林载盛, 熊唱日, 王世平, 魏巍, 赵罡. 基于参数曲面的增材制造保形晶格结构生成方法[J]. 图学学报, 2021, 42(3): 517-524.
[8]	范清 1,沈旭昆 1,2. 基于多个关键点对应性的手部动态重建[J]. 图学学报, 2020, 41(5): 709-715.
[9]	童立靖，李锦，赖裕平，付孝琴 . 基于有界双调和权的人体局部网格变形方法[J]. 图学学报, 2019, 40(6): 1064-1071.
[10]	苏鹏 1，尹梦晓 1,2，王宇攀 3，韩艳茹 1，杨锋 1,2，李桂清 3 . 基于变形图的谱姿态迁移[J]. 图学学报, 2019, 40(2): 282-289.
[11]	邵茂真，寿华好 . 热测地场控制的近似刚性网格变形技术[J]. 图学学报, 2019, 40(1): 1-7.
[12]	邵绪强，景筱竹，刘书刚. 基于完全拉格朗日粒子方法的物理动画模拟[J]. 图学学报, 2017, 38(3): 297-302.
[13]	董兰芳，章恒，陈骏雄. 基于IIF 模型的流体表面张力模拟[J]. 图学学报, 2016, 37(3): 302-307.
[14]	许晓宇，赵晓慈. 夹紧顺序、夹具布局和夹紧力对装夹变形影响与同步优化分析研究[J]. 图学学报, 2016, 37(1): 20-24.
[15]	薛原，黄璐宸，杨若瑜. 不同材质服装的实时动态仿真[J]. 图学学报, 2016, 37(1): 102-109.