松弛算法

松弛算法只考虑理想的几何刚体颗粒,不考虑重力和摩擦力等作用,不保证生成阻塞或力学稳定的填充结构,但是它能快速生成某种密填充构型。
算法简介:先在区域内生成各颗粒随机的位置和随机的方向 (对球体只需要生成随机的位置),这样形成的初始状态 中各颗粒之间存在大量的重叠,反复使用松弛算法迭代 以逐步减少重叠量并逐渐缩小颗粒本身,通过对颗粒的 平动和转动最终完全消除重叠并获得填充结果

  • 球形颗粒的松弛过程只有平动
  • 非球体的松弛过程包括平动和转动两部分
  • 以下详述该算法的各个步骤:
    img

    首先在边界区域内随机生成该非球体基点的坐标以确定其位置 , 再随机生成一空间矢量并将非球体以该矢量为轴旋转 一个随机角度,颗粒的初始粒径由设定的初始填充密度`φ_0`决定,其粒径放缩尺度`L`由下式决定:
    `L=((φ_0*V_b)/V_p)^(1/d)`
    其中`V_b`是边界区域的体积(非多面体面接该体积为转换为STL三角片边界后体积)
    其中`V_p`是颗粒的总体积

    非球体的松弛过程包括平动和转动两部分 , 分别 由推斥作用 ( 由重叠引起 ) 产生的位移和转矩引起。如 上图所示 , 球 i 是非球体 ( 图中为椭圆 ) 组合球模型中 的一个球 , 球 j 是相邻非球体组合球模型中与球 i 有 重叠的一个球。将松弛算法中球 j 对球 i 的推斥作用 改写为增量形式
    `R_(ij) = R_i + P_(ij)`
    `` 其中 `R_i` 为球 `i` 的球心矢量 , `R_(ij)``P_(ij)` 分别为球 `j` 对球 `i` 作用后球 `i` 的球心矢量和位移矢量
    `P_(ij)=(R_i - R_j )((r_i + r_j)/d_(ij)- 1)`
    `r_i``r_j`为球半径 , `d_(ij)`为两球心之间的距离。所有与球 `i` 重叠的球对其产生的位移取平均值即得球`i` 的位移矢量 `P_i`
    `P_i =1/n∑_(j = 1)^(n_i)P_(ij)`
    其中 `n_i` 为与球`i` 相重叠的球的个数
    对非球体组合球模型内所有球的位移取平均值即得非球体的平动位移矢量 P,
    `P=1/n∑_(i=1)^(n_a)(P_i)`
    其中 `n_a`为组合球模型中球的个数
    非球体在推斥作用下其基点由 `C`平动到`C^′`, 增量为`P`,
    `C^′= C + P . `
    非球体的转矩矢量
    `M=1/n_a∑_(i=1)^(n_a)(V_i × P_i)`
    其中 `V_i ( i = 1 , ⋯ , n_a )`为组合球模型中基点到各球心的矢量
    非球体的转角`θ`
    `θ=α‖ M ‖_2`
    确定 , 其中`α`为转角松弛系数 . 对于密填充情形 , 理想的转角松弛系数 应使松弛迭代中的重叠率平稳下降(不跳动) ,从而得到高填充率 . 但`α`的 取值范围与非球体的形状有关 , 须经试算选。引入非球体转动后 , 在“自锁”现象发生时 , 虽然组合球的合位移为零 , 但其合转矩并不为零 , 非球体由此产生转动而离开“自锁” 位置 。 数值实验表明 , 只要`α`的取值适当 , 就可以完全消除“自锁”现象。
    对所有非球体松弛一定次数 ( 循环周期为 T) ,即迭代一次后 , 每个颗粒进行收缩 , 其收缩量`ΔR`
    `ΔR=βR_0 sqrt(e_(mean))`
    计算 , 其中 `e_(mean)` 为平均重叠率,`β`为收缩系数。组合 球模型内球之间的重叠不计入重叠率的计算。当所有球的最大重叠率小于 `R_(max)2.0e^(-4)` 迭代终止。

    RSA算法

    随机序列添加算法 (RSA)应用广泛,在生物、化学、物理等多个领域,都有较多的应用价值。由于 RSA 算法不用迭代计算颗粒的变形、移动,因此其填充效率较高。
    算法简介:在一个周期边界的正方形/立方体边界内随机生成一个试探颗粒,其具有随机位置和随机方向。如果该颗粒不与其他任何已生成的颗粒相交,则将这个 试探颗粒加入已生成的颗粒集合。否则,将该颗粒删除。当这个系统中无法添加任何一个颗粒的时候,我们称得到的填充结构为饱和填充结构。