无限蓝噪声

Question

无限蓝噪声

algorithmpointinfinitenoise

7

我正在寻找一种算法，可以产生类似于蓝噪声的点放置结果。

然而，它需要适用于无限平面。给定一个边界框，它返回所有落在其中的点的位置。任何帮助都将不胜感激。我已经做了很多研究，但没有找到适合我的需求的东西。

- Bryan Brown TheDudeFromCI

这张图片是从 José's Sketchbook 中获取的吗？无论如何，由于正确的图案是由左侧的瓷砖组成的，您只需要手动计算左侧瓷砖中的点数，然后跟踪使用了哪个瓷砖以及使用次数即可。 - Jongware

我第一次听说“蓝噪声”这个术语是在1987年罗伯特·尤利奇尼的书《数字半色调》中。他可能发明了这个术语，但我不确定。无论如何，这本书有一些很好的算法，可以将灰度级转换为蓝噪声模式，整整一章都专门讲述了这个主题。这些算法应该非常高效。 - Mark Ransom

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sve · Accepted Answer

最终我已经成功获得了结果。

一种具有蓝噪声特性的点分布生成方法是通过泊松盘分布实现的。

按照论文《任意维度中的快速泊松盘采样》，Robert Bridson中的算法，我得到了：

论文中提到的步骤如下：

步骤0。初始化一个n维背景网格以存储样本并加速空间搜索。我们选择单元格大小为r / sqrt（n），以便每个网格单元格最多包含一个样本，因此该网格可以实现为简单的n维整数数组：默认值-1表示没有样本，非负整数给出位于单元格中的样本的索引。

步骤1。随机均匀地从域中选择初始样本x0。将其插入到背景网格中，并使用此索引（零）初始化“活动列表”（样本索引数组）。

步骤2。只要活动列表不为空，就从中选择一个随机索引（例如i）。从半径为r和2r之间的球形环之间均匀选择最多k个点。依次检查每个点是否与现有样本距离小于等于r（使用背景网格仅测试附近的样本）。如果一个点与现有样本足够远，则将其作为下一个样本发射并将其添加到活动列表中。如果在k次尝试后没有找到这样的点，则从活动列表中删除i。

请注意，为简单起见，我跳过了步骤0。尽管如此，运行时间仍然合理。它是< .5s。实现此步骤肯定会提高性能。

以下是Processing中的示例代码。它是构建在Java之上的语言，因此语法非常相似。为您的目的翻译它不应该很难。

import java.util.List;
import java.util.Collections;

List<PVector> poisson_disk_sampling(int k, int r, int size) 
{
  List<PVector> samples = new ArrayList<PVector>();
  List<PVector> active_list = new ArrayList<PVector>();
  active_list.add(new PVector(random(size), random(size)));

  int len;
  while ((len = active_list.size()) > 0) {
    // picks random index uniformly at random from the active list
    int index = int(random(len));
    Collections.swap(active_list, len-1, index);
    PVector sample = active_list.get(len-1);
    boolean found = false;
    for (int i = 0; i < k; ++i) {
      // generates a point uniformly at random in the sample's
      // disk situated at a distance from r to 2*r 
      float angle = 2*PI*random(1);
      float radius = random(r) + r;
      PVector dv = new PVector(radius*cos(angle), radius*sin(angle));
      PVector new_sample = dv.add(sample);

      boolean ok = true;
      for (int j = 0; j < samples.size(); ++j) {
        if (dist(new_sample.x, new_sample.y, 
                 samples.get(j).x, samples.get(j).y) <= r) 
        {
              ok = false;
              break;
        }
      }
      if (ok) {
        if (0 <= new_sample.x && new_sample.x < size &&
            0 <= new_sample.y && new_sample.y < size)
        {
          samples.add(new_sample);
          active_list.add(new_sample);
          len++;
          found = true;
        }
      }
    }
    if (!found)
       active_list.remove(active_list.size()-1);
  }

  return samples;
}


List<PVector> samples;
void setup() {
  int SIZE = 500;
  size(500, 500);
  background(255);
  strokeWeight(4);
  noLoop();

  samples = poisson_disk_sampling(30, 10, SIZE);
}

void draw() {
  for (PVector sample : samples)
    point(sample.x, sample.y);

}

然而，它需要适用于无限平面。

您可以使用参数size控制框的大小。 r控制点之间的相对距离。 k控制在拒绝当前样本之前应尝试多少个新样本。该论文建议使用k=30。