一种高效空间分割算法

针对三角面元目标提出了一种高效率的空间分割算法.该方法以一种空间点与单位立方体位置关系的判断法则为基础,并逐渐延拓到参数直线、三角形的空间分割上,给出了一种新的三角形面元目标快速分割的解决方法.介绍了该方法在参数曲线、NURBS(Non-Uniform Rational B-Spline)曲面目标的空间均匀分割上的应用,并给出了非均匀分割的处理方法.与计算机图形技术中最常用的BSP(Binary Space Partitioning)技术的比较中发现,对于特定情形,该算法的执行效率优于BSP法.通过实例证明了该算法的有效性和可靠性.

vBSP的算法设计与应用

BSP数据结构已经在大规模的游戏引擎产品中取得了突破性的成功,但是在现实应用中还有许多需要实际改进后才能应用。为此,改进BSP开发出一种简单、灵活的解决方案,即虚拟BSP(vBSP)来解决应用实际应用。通过研究并改进原始的BSP树,意在使BSP树简单化、实用化,并可以减少算法的复杂度,降低其它改进算法的负面影响。基于"空间换时间"的思想,通过开辟引用存储空间而不是直接分割BSP树的方法,最终达到提高算法的实用性。

基于BSP和动态规划的大规模空域扇区划分

为了解决大范围管制空域划分为多扇区时的算法效率和准确性问题,研究了结合二叉空间分割和动态规划的空域扇区优化划分方法。在分析了管制空域结构和交通流量分布的基础上,提出了空域交通流量图模型和扇区边界优化的约束条件。应用二叉空间分割算法实现了扇区间平均流量的均衡,结合动态规划方法提出了逐阶段动态搜索协调流量最小的二叉空间分割算法,解决了算法运行效率低的问题。仿真实例表明,该方法均衡了不同扇区间的平均流量,保证了协调流量最小的优化结果为一个次优解。划设10个扇区时的运行时间约为4 min。

多生理参数管制负荷模型下的扇区BSP划分

为了合理评估管制员的主观(认知)工作负荷,实现均衡管制员工作负荷的空域扇区划设目标,在前期研究基础上,考虑航空器数量、冲突点数量以及进离场航班比例对管制员工作负荷的影响,运用回归分析的方法,建立了基于多生理参数的管制员工作负荷多元回归模型。应用二叉空间分割(BSP)算法实现了空域扇区划分,结合多元回归模型实现了均衡管制工作负荷的扇区最优划设。算例结果验证了管制员工作负荷模型的合理性,BSP法均衡了不同扇区间的管制工作负荷。

基于粒子系统的室内火模型技术研究

对计算机火模拟技术的研究,既具有虚拟现实基础理论研究的意义,又有科学的研究火灾事故的现实意义,因此一直是计算机仿真研究的重点。结合前人的工作成果,初步研究了室内火模型建模所涉及的各种技术,采用粒子系统方法模拟火焰,提出粒子发射面的概念模拟多面体可燃物的燃烧,并采用二叉空间分割树分割室内空间以提高粒子碰撞检测的效率,实现了一个较为完整的模拟系统,在这个模拟系统的基础上就可以进一步探索火灾模拟的各种问题。实验结果表明,该系统生成的火焰具有较好的真实感,而空间分割技术的使用,较好地提升了碰撞检测的效率。最后给出了系统实现的模拟图。

基于无重访NSGA-Ⅱ算法的配电网多目标重构

将基于空间二叉分割理论的无重访机制与基于多目标Pareto最优化思想的第二代非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm-Ⅱ,NSGA-Ⅱ)相结合,构建了无重访NSGA-Ⅱ算法,并应用于求解同时考虑网损降低和供电可靠性提高的多目标配电网络重构问题。所构建的无重访NSGA-Ⅱ算法实现了严格意义上的不重复搜索,避免了重复方案的潮流及可靠性计算,节约了计算资源。IEEE16、IEEE33测试系统的计算结果表明能够在较少的迭代次数下得到每个目标方向上的最优解以及包含若干非支配解的Pareto最优前沿解集。根据网损与可靠性目标之间的关联关系及相应重构方案的拓扑结构分析表明在解空间的全局范围内网损与可靠性目标具有较明显的一致关联性,不论对于网损还是可靠性的优化,网络拓扑都应该接近广度优先树而规避深度优先树。

无重访遗传算法及其在输电网络规划中的应用

将无重访的遗传算法(non-revisiting genetic algorithm,NrGA)应用于求解输电网络规划问题。NrGA通过空间二叉分割(binary space partitioning,BSP)和相应的二叉分割树(BSP tree)数据结构对遗传算法搜索过的历史位置进行记录,能够快速检测遗传操作产生的新解是否在BSP tree的历史存档中,对历史存档中已有的新解使用基于BSP的自适应变异机制进行操作,实现遗传算法的无重访搜索。此外,针对输电网络规划问题的具体特点,从编码、交叉、惩罚方法等方面对算法进行改进。最后通过一个典型算例对所提出的方法进行验证。与普通遗传算法相比,NrGA算法具有参数设定区间宽泛、收敛到最优解的概率高等多方面的优势。

基于改进NrGA的易腐品生产-库存-分销集成优化

为有效解决多周期环境下的易腐品生产-库存-分销集成优化调度难、成本居高不下问题,提出一种改进的无重访遗传算法。该算法利用归一化数据预处理方法进行多维实数编码;在空间二叉分割树数据结构生成规则中,建立多维子空间同时分割机制,形成解的唯一解空间;应用田口实验设计方法调整无重访遗传算法参数,获得近似最佳组合参数。结果表明,该算法可以加快搜索速度,提高求解精度,在不同需求情景下能够有效降低易腐品冷链总成本。

高效鲁棒三维结构化重建

目的结构化重建,即从离散点云或者原始三角网格中提取几何平面并将其拼接成紧凑的参数化3维模型,一直是计算机图形学领域中极具挑战性的问题。现有方法通常面临着两个挑战。一是传统的形状检测方法通常只考虑物体的局部特征,无法保证整体结果的准确性。二是现有的形状拼接算法往往受限于计算复杂度,从而只能处理由一百多个几何平面组成的物体,极大地限制了算法的应用场景。针对这些问题,提出了一种快速、鲁棒的结构化重建算法以自动地生成轻量的多边形网格。方法提出了一种多源区域增长算法,全局地从原始3维数据中提取特征平面。该策略保证了原始数据可以被正确地聚类到所属的平面区域。为了减轻几何平面分割3维空间带来的计算负担,采用了一种基于二叉空间分割树的结构将3维空间切分为凸多面体。提出了一种基于光线射击的马尔可夫能量方程以提取水密、无自相交的多边形网格。结果实验结果表明,本文方法可以在没有并行化方案的标准计算机上处理由上万个几何平面组成的物体。与传统的全相交分割相比,本文方法得到的多面体数目和运行时间都降低了至少两个数量级,总耗时可控制在5 s/万点以内。此外,模型化简前后的均方根误差平均控制在1%以内,面片化简比例控制在1.5%以内。结论本文方法在计算效率以及结果的准确性上均取得了较大的进步,能够恢复有部分缺陷的表面模型,保留重要结构细节,在复杂性和保真度之间提供了一种较好的方案。