基于伞形搜索的树形支撑结构生成算法

Algorithm for generating tree-like supporting structure based on umbrella-shape search

为了节省支撑结构材料,并避免NP难度的最优树形支撑结构生成算法,提出一种基于伞形搜索的树形支撑结构生成算法。通过该算法快速求解满足临界倾角约束条件的支撑节点,并采用贪心算法和迭代的思路逼近最优解。同时,在生成树形支撑结构过程中用体素法对树形枝干与制件实体进行干涉判断,以避免支撑与实体干涉,保证支撑结构的合理性。对比商用软件Meshmixer,所提算法在生成树形支撑结构的合理性及算法生成时间上具有一定优势,且能处理带凸台结构复杂模型的支撑结构问题。

To save material of support structure,and to avoid the NP-hard optimal tree-like support structure generation algorithm,a tree-like support structure generation algorithm based on umbrella-shape search was proposed.The support node satisfying the critical angle constraint was solved quickly by umbrella search algorithm,and the optimal solution was approximated by greedy algorithm and iterative idea.At the same time,in the process of generating tree-like support structure,the voxel method was used to judge the relationship between the tree branches and the parts,so as to avoid the support and the model interference and ensure the rationality of the support structure.Compared with the commercial software Meshmixer,the proposed algorithm had some advantages in generating the tree-like support structure and the generation time of algorithm,and it was able to deal with the structure problems of complex models with convex structure.