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

作者：李静; 王文成; 吴恩华

来源：软件学报, 2008, (07): 1766-1782.

• 遮挡
• 凸剖分
• 多面体
• 四面体
• 多边形 occlusion
• convex decomposition
• polyhedron
• tetrahedron
• polygon

提出一种多面体凸剖分的方法,与国际上已有的工作相比,在计算速度、空间需求和新增顶点等方面均降低了复杂度,有大幅的效率提高,且在处理凹边很多的多面体时具有更大的优越性.其工作步骤是根据多面体的面、边沿某些方向正投影时面与面之间、边与边之间的遮挡关系进行局部化操作,以渐进地凸剖分多面体.它对应用中的常见模型表现出的时间复杂度、空间复杂度皆近似为O(n),而新点数不超过O(r+n~(0.5)),这里,n为模型的点数,r为凹边数.实验结果表明,与目前国际上常用的"切割分裂"方法相比,新方法的速度提高了14～120倍,空间下降至"切割分裂"方法的1/2.3～1/7.4,而新增加的点数则最多为"切割分裂"...

• 单位
  计算机科学国家重点实验室; 澳门大学; 中国科学院软件研究所