基于环链的多面体剖分快速算法研究

利用环链提出了一种对任意多面体不添加顶点的凸剖分快速方法 ,它对多面体的剖分个数接近最少 .该方法首先从多面体的棱和对角棱所构成的所有环中 ,以最小周长选取一个最好的环 ,然后利用这个环的各个边所形成的一系列面 ,对多面体进行一次剖分 .实验证明 ,这种方法可找到对多面体不添加顶点剖分的最好剖分面 ,使剖分的次数接近最少 ,具有较好的实用价值和广泛的应用前景 .

A Fast Algorithm of Decomposing Polyhedrons by Using Loop-chain

Based on loop chain, a fast algorithm is presented for decomposing arbitrary polyhedron into convex polyhedrons without adding new vertexes, in which the final number of convex polyhedrons is close to the least. A loop is consist of several vertices that start from one vertex go to next adjacent vertex can come back this vertex, all vertices in a loop is consist of a partition plane. The least perimeter loop chain is selected from all the loops consisted of edges and diagonal edges of the polyhedron, and decomposes the polyhedron with a series of planes consisted of all edges of the loop. Experiments show that this method can decomposing arbitrary polyhedron into the least number convex polyhedrons without adding new vertexes, can process most kinds of polyhedrons (e.g. a polyhedron with a inner hole), and has low cost in calculation. The algorithm of convex decomposing 3D objects has been a research direction of computer geometry for a period and is widely used in fields of pattern identifying, animation and CAD.