基于边/面遮挡关联性的多面体凸剖分方法

• 作者: WANG Wen-Cheng 吴恩华 李静
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 遮挡 凸剖分 多面体 四面体 多边形
• 年，卷（期）: 2008,（7）
• 所属期刊栏目: 计算机图形学与计算机辅助设计
• 页码范围: 1766-1782
• 页数: 17页
• 分类号: TP391
• 字数: 14292字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2008.01766

摘要

提出一种多面体凸剖分的方法,与国际上已有的工作相比,在计算速度、空间需求和新增顶点等方面均降低了复杂度,有大幅的效率提高,且在处理凹边很多的多面体时具有更大的优越性.其工作步骤是根据多面体的面、边沿某些方向正投影时面与面之间、边与边之间的遮挡关系进行局部化操作,以渐进地凸剖分多面体.它对应用中的常见模型表现出的时间复杂度、空间复杂度皆近似为O(n),而新点数不超过O(r+n0.5),这里,n为模型的点数,r为凹边数.实验结果表明,与目前国际上常用的"切割分裂"方法相比,新方法的速度提高了14～120倍,空间下降至"切割分裂"方法的1/2.3～1/7.4,而新增加的点数则最多为"切割分裂"方法的1/28,甚至有些情况下无须增加新点就能完成凸剖分.新方法剖分出的凸多面体绝大多数是四面体,多于"切割分裂"方法所得凸多面体数量.但是,很多应用是要求多面体被剖分为四面体的.如果进一步将凸多面体四面体化,则新方法的结果个数将明显少于"切割分裂"方法,因为新方法的剖分过程中所增加的新点要少很多.新方法还能方便地处理包含空洞的多面体,甚至是包含孤立面、孤立边和孤立点的非流形多面体.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴恩华	中国科学院软件研究所计算机科学国家重点实验室	114	2335	25.0	44.0
2	李静	中国科学院软件研究所计算机科学国家重点实验室	238	2528	23.0	40.0