一个利用法矢的散乱点三角剖分算法.pdf

《一个利用法矢的散乱点三角剖分算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第28卷第6期计算机学报Voi.28No.62005年6月CHINESEJOURNALOFCOMPUTERSJune2005一个利用法矢的散乱点三角剖分算法董辰世汪国昭（浙江大学数学系杭州310027）摘要曲面上散乱点的三角剖分在曲面重建中发挥着重要作用.借助于曲面上的法矢信息和三维Deiaunay三角剖分算法，该文给出了一种新的散乱点三角剖分算法.输入一组散乱点以及所在曲面S在这些散乱点处的一致定向的法矢信息，该算法将产生一张插值散乱点的三角网格曲面M，并且曲面M可以近似地看成是曲面S的三角剖分.算法的主要步骤分为两步：首先通过曲面S的一致定向的法矢信息，在曲面S的同一侧添加辅助

2、点，利用这些辅助点来剔除Deiaunay三角剖分中产生的不需要的三角片；然后将剩余的三角片连接成一张完整的网格曲面.与基于中轴的三角剖分算法相比，该文算法需要更少和更简单的计算.与局部三角剖分算法相比，该文算法可以更有效地避免重建后的曲面产生自交.该文的算法可用于任意拓扑的光滑曲面重建.关键词曲面重建；散乱点；法矢；Deiaunay三角剖分；三角网格曲面中图法分类号TP391AnAlgorithmforTriangulatingUnorganizedPointswithNormalDONGChen-ShiWANGGuo-zhao（DepartmentOfMathematics，Zh

3、ejiangUniuersity，HangzhOu310027）AbstractThetrianguiationofunorganizedpointsonasurfacepiaysaimportantroieforsurfacerecon-struction.Thispaperpresentsanoveitrianguiationaigorithmbasedonthenormaiinformationofthesur-faceandtheDeiaunaytrianguiationaigorithm.Givenagroupofunorganizedpointsandorientedn

4、ormaisampiedfromasurfaceS，theauthorsoutputatrianguiarmeshM，whichpassthroughtheunorganizedpointsandcanbetreatastheapproximationtothetrianguiationofthesurfaceS.Therearetwostagesinthemethod.ThefirststepistousetheorientednormaiinformationtogenerateagroupofauxiiiarypointsononesideofthesurfaceS，whic

5、hisusedtoremovethetriangiesfromtheDeiaunaytrianguiation.Then，theauthorsconnecttheremainedtriangiestoformatrianguiarmesh.Thereisoneprimaryadvan-tageinthemethodversusthemediaiaxis：approximatingthemediaiaxisisadifficuittaskwhereasthemethodherereguiresnosuchcomputation.Incontrastwiththeiocaitriang

6、uiationaigorithm，theaigo-rithminthispaperismorepowerfuitoavoidsurfaceseif-intersection.Thisaigorithmsuittodeaiwiththesmoothsurfacereconstructionwitharbitrarytopoiogy.Keywordssurfacereconstruction；unorganizedpoints；normai；Deiaunaytrianguiation；trianguiarmesh收稿日期：2004-08-13；修改稿收到日期：2005-03-22.本课

7、题得到国家自然科学基金（60473130）、国家“九七三”重点基础研究发展规划项目基金（2004CB318000）资助.董辰世，男，1976年生，博士研究生，研究方向包括计算机辅助几何设计、计算机图形学、逆向工程等.E-maii：DCS@zju.edu.cn.汪国昭，男，1944年生，教授，博士生导师，研究方向包括计算机辅助几何设计、计算机图形学、医学图像处理等.6期董辰世等：一个利用法矢的散乱点三角剖分算法1001小邻域同胚于圆盘这一现象，从散乱点的某一个点!"引"