主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
李 静,王文成,吴恩华.基于边/面遮挡关联性的多面体凸剖分方法.软件学报,2008,19(7):1766-1782
基于边/面遮挡关联性的多面体凸剖分方法
Convex Decomposition of Polyhedrons Using Occlusion Relations Among Edges/Facets
投稿时间:2007-10-09  修订日期:2007-12-28
DOI:
中文关键词:  遮挡  凸剖分  多面体  四面体  多边形
英文关键词:occlusion  convex decomposition  polyhedron  tetrahedron  polygon
基金项目:Supported by 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 (国家高技术研究发展计划(863)); the National Basic Research Program of China under Grant No.2002CB312102 (国家重点基础研究发展计划(973))
作者单位
李 静 中国科学院软件研究所 计算机科学国家重点实验室,北京 100190 
王文成 中国科学院软件研究所 计算机科学国家重点实验室,北京 100190 
吴恩华 中国科学院软件研究所 计算机科学国家重点实验室,北京 100190
澳门大学 科技学院 计算机与信息科学系,澳门 
摘要点击次数: 2840
全文下载次数: 3095
中文摘要:
      提出一种多面体凸剖分的方法,与国际上已有的工作相比,在计算速度、空间需求和新增顶点等方面均降低了复杂度,有大幅的效率提高,且在处理凹边很多的多面体时具有更大的优越性.其工作步骤是根据多面体的面、边沿某些方向正投影时面与面之间、边与边之间的遮挡关系进行局部化操作,以渐进地凸剖分多面体.它对应用中的常见模型表现出的时间复杂度、空间复杂度皆近似为O(n),而新点数不超过O(r+n0.5),这里,n为模型的点数,r为凹边数.实验结果表明,与目前国际上常用的"切割分裂"方法相比,新方法的速度提高了14~120倍,空间下降至"切割分裂"方法的1/2.3~1/7.4,而新增加的点数则最多为"切割分裂"方法的1/28,甚至有些情况下无须增加新点就能完成凸剖分.新方法剖分出的凸多面体绝大多数是四面体,多于"切割分裂"方法所得凸多面体数量.但是,很多应用是要求多面体被剖分为四面体的.如果进一步将凸多面体四面体化,则新方法的结果个数将明显少于"切割分裂"方法,因为新方法的剖分过程中所增加的新点要少很多.新方法还能方便地处理包含空洞的多面体,甚至是包含孤立面、孤立边和孤立点的非流形多面体.
英文摘要:
      This paper presents a new method for convex decomposition of polyhedrons. In comparison with existing methods, the new method can improve the efficiency greatly with complexities reduced in many aspects of execution time, storage and added new vertices, and it is more advantageous in treating the polyhedrons with reflex edges in higher numbers. Its strategy is to gradually decompose a polyhedron in local operations by the occlusion relationships between facets and edges along certain orthogonal directions. In treating general polyhedrons in practice, the new method has its time and storage complexities both in O(n) approximately, and its produced new vertices are in a number not more than O(r+n0.5), here n is the vertex number and r is the reflex edge number. By testing a large number of complex polyhedrons, it shows that, compared with the popularly used "cutting & splitting" method, this new method can run 14~120 times faster, reduce the storage requirement to 1/2.3~1/7.4, and reduce the new points to at most 1/28, and even needs no new point in some cases. Because most convex polyhedrons decomposed by the method are tetrahedrons, the resulted convex polyhedrons by the new method are more than those by the "cutting & splitting" method. However, if convex polyhedrons are required to be further decomposed to tetrahedrons, the new method can produce much fewer tetrahedrons, due to much fewer added vertices for decomposition by the new method. Besides, the new method can be conveniently used to treat the polyhedrons with holes, or even the non-manifold polyhedrons that contain isolated facets, edges or vertices.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利