%0 Journal Article
%T Convex Decomposition of Polyhedrons Using Occlusion Relations Among Edges/Facets<br>基于边/面遮挡关联性的多面体凸剖分方法
%A LI Jing
%A WANG Wen-Cheng
%A WU En-Hua
%A <br>李 静
%A 王文成
%A 吴恩华
%J 软件学报
%D 2008
%I 
%X 提出一种多面体凸剖分的方法,与国际上已有的工作相比,在计算速度、空间需求和新增顶点等方面均降低了复杂度,有大幅的效率提高,且在处理凹边很多的多面体时具有更大的优越性.其工作步骤是根据多面体的面、边沿某些方向正投影时面与面之间、边与边之间的遮挡关系进行局部化操作,以渐进地凸剖分多面体.它对应用中的常见模型表现出的时间复杂度、空间复杂度皆近似为O(n),而新点数不超过O(r n~(0.5)),这里,n为模型的点数,r为凹边数.实验结果表明,与目前国际上常用的"切割分裂"方法相比,新方法的速度提高了14～120倍,空间下降至"切割分裂"方法的1/2.3～1/7.4,而新增加的点数则最多为"切割分裂"方法的1/28,甚至有些情况下无须增加新点就能完成凸剖分.新方法剖分出的凸多面体绝大多数是四面体,多于"切割分裂"方法所得凸多面体数量.但是,很多应用是要求多面体被剖分为四面体的.如果进一步将凸多面体四面体化,则新方法的结果个数将明显少于"切割分裂"方法,因为新方法的剖分过程中所增加的新点要少很多.新方法还能方便地处理包含空洞的多面体,甚至是包含孤立面、孤立边和孤立点的非流形多面体.
%K occlusion
%K convex decomposition
%K polyhedron
%K tetrahedron
%K polygon<br>遮挡
%K 凸剖分
%K 多面体
%K 四面体
%K 多边形
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=45B4B6F1193AE8F5BF2F84CF3DEC71E6&yid=67289AFF6305E306&vid=2A8D03AD8076A2E3&iid=DF92D298D3FF1E6E&sid=7B9ECDE662C67650&eid=FAF71E26421EE61B&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=18