扩展八叉树算法在虚拟雕刻几何建模中的应用

基于传统的八叉树模型的基础及特点,引入了带表面边界信息的扩展八叉树模型以及相应的扩展八叉树模型的特殊数据结构,并将它们应用于虚拟雕刻的几何建模系统中；叙述了如何将实体从表面边界模型转换成相应的改进八叉树模型的方法,同时采用了局部更新技术提高模型更新效率；最后通过运行雕刻实例证明算法的有效性和可行性.     

五轴数控渐进成形干涉检测与修正研究

综合考虑干涉检测效率、精确性和可修正性,提出一种高效、精确的基于STL(Sterolithography)数据模型的五轴数控渐进成形挤压工具与工件干涉检测与修正方法。以八叉树分割立方体最小边为基准对STL模型的三角面片细分后再沿边进行离散进而确保离散点云模型的八叉树分割更为均匀,并把离散点八叉树分割模型拓展为一个带有索引序列的八叉树分割模型以便不经过递归查找就能直接检测干涉区域;然后把挤压工具用轴向AABB(Axis-aligned bounding boxes)包围盒进行包围并利用八叉树分割模型粗略检测发生干涉的位置;最后利用八叉树分割模型立方体节点内的离散点和圆柱体形状的挤压工具对可能发生干涉的位置进行细致检测,并在干涉点处沿着挤压工具轴线方向的剖切面上进行干涉修正。算法应用实例表明,该方法能够快速而准确地寻找出干涉点的位置并能予以修正,整个过程运行稳定可靠。     

运用边界状态约束的表面体素加密细分算法

为了平衡体素模型的体素数量与精细度,提出一种实体模型体素加密细化算法。该算法对低分辨率均一体素模型的表面体素进行切分,标记与三角面不相交的体素,并运用边界状态传递判定标记体素的内外位置。通过编码不同八叉树的节点,并进行跨八叉树快速邻居节点搜寻,实现多级加密细分。实验结果表明,该算法可以以低分辨率模型为基础,精确地获得体素单元少的高分辨率模型。     

基于自适应八叉树的三维点云快速拾取方法研究

针对逆向工程中大规模点云数据快速拾取问题,对当前三维图形拾取基本方法进行了研究,对点云拾取的基本流程和点云快速拾取的关键问题进行了分析,提出了一种基于自适应八叉树的三维点云快速拾取方法。当用户在计算机屏幕上给出拾取多边形后,首先基于点云分布密度,对点云数据进行了自适应八叉树划分;然后对八叉树节点进行了投影,在屏幕上形成了八叉树节点的投影多边形,并对拾取多边形建立了矩形包围盒;接着对八叉树投影多边形和拾取多边形的矩形包围盒进行了相交检测,将不与矩形包围盒相交的八叉树节点包含的点云去除,从而缩小了点云拾取所需判断的范围,提升了拾取效率。最后对不同分布密度点云进行了定面积的拾取实验。实验结果表明,该点云拾取方法的点云分布密度越大,拾取时间相对越短,算法具有较高的拾取速度和准确度。     

用于干涉检验的八叉树层次球状模型和相应的快速检验算法

提出了一种运动物体干涉碰撞检测的快速算法，在进行物体的干涉碰撞检测时，可将物体用一种八叉树层次球状模型描述。给出了构造八叉树层次球状模型的方法，在八叉树层次球状模型的基础上，对运动物体的干涉检验，只需要对物体表面上的模型节点进行相交测试。而且，由于模型节点代表的是一个球形区域，所以，不管物体怎样运动，测试节点间的相交性只要计算节点间的距离即可。最后，给出一个例子，分析了算法的效率。     

基于双层次八叉树的STL模型体素化方法

为满足五轴加工仿真系统与CAD系统的模型数据交换需求,提供高效的复杂初始毛坯建模方式,提出一种面向STL模型的体素化方法。改进了传统的八叉树模型,采用外部层次树型和内部线性的双层次结构表达实体空间,并给出了该双层次八叉树模型的编码计算规则。以STL模型三角面片为体素化对象,通过编码规则建立三角面片和STL实体内部空间与体素节点的映射关系,实现表面和内部体素的快速定位。通过实例证明了算法能够保证生成体素模型的26-邻接性,实验结果表明,与传统的八叉树模型相比,该算法具有更好的时间和空间性能。     

供应链物流配送路径优化节约算法改进研究

针对供应链物流配送中的有时间窗约束集送货一体化路径优化问题研究了基于C-W节约算法的改进算法。提出了以集货量和送货量共同作为客户点归并的判断条件,把时间窗约束转化为里程,用里程数来控制客户点的归并、插入和时间窗约束的计算,实现了多个目标(里程、集送货一体、载重、时间窗)的路径优化;算法在实现中对合并点归并位置进行了深入研究,根据归并点的特点和约束条件的不同,进行了分别处理,获得了较好的优化结果。该改进的节约算法有效的减少里程数、用车量,节约了费用、降低了成本。     

五轴数控仿真全局干涉检测算法研究

针对五轴数控加工复杂曲面的全局干涉问题,提出了一种实时干涉初步检测算法.该算法基于分层方向包围盒以及八叉树空间简化法,采用改进的分离轴理论,通过比较空间多面体在特定轴上投影的距离关系来判别多面体之间是否相交.应用简化的方向包围盒及八叉树结构,当某一节点发生干涉时,才对其子节点进行进一步处理.该改进算法有效降低了空间复杂度,提高了效率.该算法已在某型号五轴数控加工中心仿真系统的全局干涉检测模块中得到应用,通过实验比较,证明了该算法的可行性.     

基于法向变化量的变分辨率曲面重建算法

在研究曲面局部法向变化量与高斯曲率关系的基础上,提出了一种基于法向变化量的变分辨率曲面重建算法。该算法首先根据用户给定的法向变化量门限,自适应于曲面曲率对点云数据的最小立方体包围盒进行八叉树分割,并在其有效叶节点内进行局部等值面提取,然后在八叉树中不同级别且空间相邻的有效叶节点内,采用垂直投影法将它们间的缝隙进行拼接。对于给定不同的法向变化量门限,该算法可同时完成曲面重建和网格简化两种功能,从而直接得到点云数据的多分辨率模型。应用实例表明了该算法的有效性。     

基于八叉树的三维干涉检验系统

针对八叉树这一布局基础数据结构，设计了一套基于八叉树的三维干涉检验系统，该系统通过对AutoCAD软件产生的图形交换信息（IGES文件）进行实体信息读取，产生布局实体的几何信息，并将之转换为八叉树数据结构，利用八叉树描述空间几何形体的方法，对布局方案中的几何形体进行了三维干涉检验。此系统可以对AutoCAD产生的任意形状的布局实体进行静态和动态的干涉检验。