| 基于边/面遮挡关联性的多面体凸剖分方法 |
| |
| 引用本文： | 李 静,王文成,吴恩华.基于边/面遮挡关联性的多面体凸剖分方法[J].软件学报,2008,19(7):1766-1782. |
| |
| 作者姓名： | 李 静 王文成 吴恩华 |
| |
| 作者单位： | 1. 中国科学院软件研究所,计算机科学国家重点实验室,北京,100190
2. 中国科学院软件研究所,计算机科学国家重点实验室,北京,100190;澳门大学,科技学院,计算机与信息科学系,澳门 |
| |
| 基金项目： | the National Natural Science Foundation of China under Grant No.60773026
,
the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z306 (国家高技术研究发展计划
,
the National Basic Research Program of China under Grant No.2002CB312102 (国家重点基础研究发展计划 |
| |
| 摘 要： | 提出一种多面体凸剖分的方法,与国际上已有的工作相比,在计算速度、空间需求和新增顶点等方面均降低了复杂度,有大幅的效率提高,且在处理凹边很多的多面体时具有更大的优越性.其工作步骤是根据多面体的面、边沿某些方向正投影时面与面之间、边与边之间的遮挡关系进行局部化操作,以渐进地凸剖分多面体.它对应用中的常见模型表现出的时间复杂度、空间复杂度皆近似为O(n),而新点数不超过O(r n~(0.5)),这里,n为模型的点数,r为凹边数.实验结果表明,与目前国际上常用的"切割分裂"方法相比,新方法的速度提高了14～120倍,空间下降至"切割分裂"方法的1/2.3～1/7.4,而新增加的点数则最多为"切割分裂"方法的1/28,甚至有些情况下无须增加新点就能完成凸剖分.新方法剖分出的凸多面体绝大多数是四面体,多于"切割分裂"方法所得凸多面体数量.但是,很多应用是要求多面体被剖分为四面体的.如果进一步将凸多面体四面体化,则新方法的结果个数将明显少于"切割分裂"方法,因为新方法的剖分过程中所增加的新点要少很多.新方法还能方便地处理包含空洞的多面体,甚至是包含孤立面、孤立边和孤立点的非流形多面体.
|
| 关 键 词： | 遮挡 凸剖分 多面体 四面体 多边形 |
| 收稿时间： | 2007/10/9 0:00:00 |
| 修稿时间： | 2007/12/28 0:00:00 |
Convex Decomposition of Polyhedrons Using Occlusion Relations Among Edges/Facets |
| |
| LI Jing,WANG Wen-Cheng and WU En-Hua.Convex Decomposition of Polyhedrons Using Occlusion Relations Among Edges/Facets[J].Journal of Software,2008,19(7):1766-1782. |
| |
| Authors: | LI Jing WANG Wen-Cheng and WU En-Hua |
| |
| Abstract: | |
| |
| Keywords: | occlusion convex decomposition polyhedron tetrahedron polygon |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
