近似刚性的快速点云变形算法

第2 5卷第 7期 2 0 1 3年 7月

计算机辅助设计与图形学学报 J o u r n a l o f Co mp u t e r— Ai d e d De s i g n& C o mp u t e r Gr a p h i c s

Vo 1 . 2 5 No . 7

J u l y 2 0 1 3

近似刚性的快速点云变形算法 赵勇¨,刘光鹏”,彭群生 ”(中国海洋大学数学科学学院青岛 2 6 6 1 0 0 ) 2 (浙江大学 C AD& C G国家重点实验室 ( z h a o y o n g@c a d . z j u . e d u . c n )

杭州 3 1 0 0 5 8 )

摘要：针对大规模的复杂点云模型，提出了一种非线性变形算法 .通过保持局部邻域的刚性使得点云模型进行近 似刚性的变形，在大尺度变形时有效地保持几何细节和体积；为了保证求解过程的收敛性，对原始点云进行聚类，快速生成其简化点云，进而在稀疏的简化点云上完成变形，并将该变形作用给原始点云以得到合理的初始结果.此外，

还给出一种动态重采样方法，以消除变形造成的冗余点和裂缝 .实验结果和对比数据表明，文中算法简单高效，能够防止几何细节的扭曲和明显的体积变化，获得了令人满意的变形效果 .

关键词：点云模型；近似刚性的变形；快速收敛；动态重采样 中图法分类号： TP 3 9 1

As。。 r i g i d 。 a s。。 p o s s i b l e Ef f i c i e nt De f o r ma t i o n Al g o r i t h m f o r Po i nt Cl o u d s

Z h a o Yo n g”,Li u Gu a n g p e n g¨,a n d P e n g Qu n s h e n g ”( S c h o o l o f Ma t h e ma t i c a l S c i e n c e s, Oc e a n U n i v e r s i t y f o C h i n a Q i n g d a o 2 6 6 1 0 0 ) ’ ( S t a t e Ke y L a b o r a t o r y f o C AD& C G,Z h e j i a n g U n i v e r s i t y.Ha n g z h o u 3 1 0 0 5 8 )

Ab s t r a c t:I t i s a c ha l l e n gi n g p r o bl

e m t o e f f i c i e n t l y d e f o r m c o mpl e x l a r ge po i nt c l o ud s i n c o mput e r

g r a p h i c s .I n t h i s p a p e r,a n o v e l n o n - l i n e a r a l g o r i t h m i s p r e s e n t e d t o a c h i e v e a s— r i g i d— a s— p o s s i b l e d e f or ma t i o n t hr o ug h c o ns t r a i ni n g t he r i g i di t y o f t he l o c a l ne i g hbo r ho o ds,t hus pr e s e r v i n g bo t h de t a i l a nd v o l ume und e r l a r ge d e f or ma t i o ns . To g ua r a n t e e t he c on ve r ge n c e o f t h e nu me r i c a l s o l v e r,t he or i g i na l po i nt c l ou ds i s e f f i c i e nt l y s i mp l i f i e d by c l u s t e r i ng,t h e n t h e d e f o r ma t i o n i s p e r f or me d on t he s i mpl i f i e d po i nt c l ou ds a nd t r a n s f e r r e d t o t he o r i g i na l po i n t c l o uds t o o bt a i n t he i n i t i a l r e s ul t . Fur t he r mo r e,a dy n a mi c r e s a m pl i n g me t h od i s i nt r o d uc e d t o e l i mi n a t e t he r e du nd a nt p oi nt s a nd c r a c ks t ha t o f t e n o c c ur dur i ng de f o r ma t i on s . The e x pe r i me nt d a t a de mo ns t r a t e t ha t o ur a l g or i t hm i s e a s y t o

u s e,e f f i c i e n t a n d e f f e c t i v e i n p r e v e n

t i n g d e t a i l d i s t o r t i o n s a n d v o l u me c h a n g e s .

Ke y wo r d s:p oi n t c l ou ds;a s— r i g i d— a s— p os s i bl e de f o r ma t i o n;f a s t c on v e r ge nc e;d yn a mi c r e s a mp l i n g

近年来，各种三维扫描仪的出现，使得点云模型

点云模型的变形算法一直是研究人员广泛关注的热

成为了复杂三维物体 (如雕塑等 )的主流表示方式之 一

点内容，其在数字娱乐、虚拟现实等诸多方面都有实 际应用价值. 点云变形是指点云模型在用户的指导下实现

.

同时，基于点的图形学也飞速发展起来，已经成

为计算机图形学的一个重要分支；其中，大规模复杂

收稿日期： 2 0 1 2 - 0 6— 0 5;修回日期： 2 0 1 2 - 1 2 - 0 4 .基金项目：国家”九七三”重点基础研究发展计划项目( 2 0 0 9 C B 3 2 0 8 0 2 );山东省优秀中青年

科学家科研奖励基金( B S 2 0 1 2 D X0 4 3 );中央高校基本科研业务费青年教师专项基金项目( 2 0 1 3 1 3 0 0 5 ) .赵勇 ( 1 9 8 2一),男，博士，讲师，主要研 究方向为点云重建与变形、网格编辑、图像处理；刘光鹏( 1 9 9 0一),男，在校学生，主要研究方向为点云重建与变形；彭群生( 1 9 4 7一),男，博士，

教授，博士生导师， C C F高级会员，主要研究方向为点云与网格处理、真实感绘制、图像与视频处理、自然场景建模、虚拟现实、可视化、生物计算.