Lib.rs

注意：这是一个持续研究的话题，不提供稳定性保证。

您可以通过以下论文进行介绍： Paul Bourke - 平面的随机空间填充（2011）.
然而，提供的下一个位置的搜索算法效率低下，对分布的控制非常有限^[1]。在这项工作中，我提出了以下方程的两个求解器

sdf_n 是符号距离函数（原语），通过聚合最小值形成一个复杂的距离场 - 进一步称为 "SDF"。

算法的目标是找到一个安全域，保证不会与任何形状相交。实现了通用的并行接口。目前支持

• 用户定义的分布（包括分形和随机分布）
• 任何可以用 SDF 表示的形状：曲线、正多边形、非凸和不相连的区域、分形或任何具有非整数豪斯多夫维度的集合（只要可以近似距离）。

Argmax2D

SDF 存储为离散位图，其内存布局类似于 z-order 曲线。求解器保证始终找到 全局最大值，但提高精度需要二次内存。

GD-ADF

一篇论文 "自适应采样距离场" (doi:10.1145/344779.344899) 提出了一个减少内存消耗的想法，但它非常复杂，没有包含任何实际实现的提示。唯一的一个是 - 使用多项式逼近 k-d 树的每个节点；然而，当前工作采取了不同的路径 - 通过在每个节点（桶）中存储函数原语本身。在桶内执行冗余原语消除使用了 内点法。
ADF 本身实现了 SDF 特性，允许高效地采样由数百万个原语组成的复杂字段——与直接计算相比——其本质上具有二次复杂度。
然而，原语消除尚未完美。一个既精确又足够快的消除算法将是进一步理论研究的话题。

一旦获得表示，优化器的作用就显现出来。为了实际应用，选择了指数收敛的梯度下降——使GD-ADF成为一个 局部极大值 算法；如下公式所述：

由于定义上，距离场的第一阶导数是常数，因此只考虑梯度的方向——消除了GD/IPM中的一些问题；而且作为额外的好处，它们不再直接依赖于场的大小。

与Argmax2D不同，GD-ADF提供了10-100倍的内存减少，以及连续、精确的场表示。提供了各种速度权衡，包括单精度和双精度。

示例

您可以使用以下命令运行示例：
cargo运行 --发布 --功能 "绘图" --示例 <示例名称>
您可以在命令末尾添加 -- -C target=native 以进一步提高速度。

01_fractal_distribution
每个后续圆都插入到距离场的最大值处。

02_random_distribution
给定最大值的 (xy, magnitude)，在半径为 magnitude 且中心为 xy 的域内插入一个新的随机圆。

03_embedded
嵌入在分布中的分布。

04_polymorphic
展示

• 动态分发接口；
• 混合形状的随机分布；
• 随机颜色和纹理填充样式；
• 并行生成和绘制。

05_image_dataset
显示超过10万个图像。
使用以下命令运行：cargo run --release --features "drawing" --example image_dataset -- "<image folder>" -C target-cpu=native

06_custom_primitive
用户定义的原语。

以往的工作

在 src/legacy 中，您可以找到许多值得重新探索的算法，包括四叉树和GPU实现。

未来工作

• 添加更多样本SDFs，以及通用的绘制特性
• 扩展以支持低于2^-16的精度（千兆像素分辨率）
• 重构特性
• 推广到N维

一旦完成以上工作，我将使用这个库来制作我的下一个项目“巴别塔画廊”。

脚注

: J. Shier, "一百万个圆的分形": https://www.d.umn.edu/~ddunham/circlepat.html
「...运行时间为14.7小时。」