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

Convex Decomposition of Polyhedrons Using Occlusion Relations Among Edges/Facets

提出一种多面体凸剖分的方法,与国际上已有的工作相比,在计算速度、空间需求和新增顶点等方面均降低了复杂度,有大幅的效率提高,且在处理凹边很多的多面体时具有更大的优越性.其工作步骤是根据多面体的面、边沿某些方向正投影时面与面之间、边与边之间的遮挡关系进行局部化操作,以渐进地凸剖分多面体.它对应用中的常见模型表现出的时间复杂度、空间复杂度皆近似为O(n),而新点数不超过O(r+n^(0.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.