算法简介
蓝噪声（Blue Noise）是一种特殊的随机分布模式，其功率谱能量主要集中在高频区域，低频区域几乎没有能量。直观上，蓝噪声采样点具有均匀分布但又不规则的特性：任意两个采样点之间保持最小距离，同时在整个区域内尽可能均匀覆盖。这与完全随机采样（白噪声）的聚集现象和规则网格采样的周期性 artifacts 形成鲜明对比。
蓝噪声在计算机图形学中有广泛应用：纹理抖动、半色调打印、渲染采样、植被分布、物体放置等场景都需要这种”既随机又均匀”的采样特性。
本文用Java实现蓝噪声生成，重点讲解泊松盘采样和Bridson快速算法。
核心算法设计
1. 基础数据结构
public class BlueNoiseGenerator {
private double width; // 采样区域宽度
private double height; // 采样区域高度
private double minDist; // 最小点间距
private int k; // Bridson算法参数：每个点的尝试次数
private List<double[]> points; // 已生成的采样点
private List<double[]> activeList; // 活跃列表（Bridson算法使用）
private Random random;
public BlueNoiseGenerator(double width, double height,
double minDist, int k) {
this.width = width;
this.height = height;
this.minDist = minDist;
this.k = k;
this.points = new ArrayList<>();
this.activeList = new ArrayList<>();
this.random = new Random();
}
/**
* 计算两点之间的欧氏距离
*/
private double distance(double[] p1, double[] p2) {
double dx = p1[0] - p2[0];
double dy = p1[1] - p2[1];
return Math.sqrt(dx * dx + dy * dy);
}
/**
* 判断点p是否在采样区域内
*/
private boolean inBounds(double[] p) {
return p[0] >= 0 && p[0] < width && p[1] >= 0 && p[1] < height;
}
/**
* 打印所有采样点坐标
*/
public void printPoints() {
System.out.println("共生成 " + points.size() + " 个采样点：");
for (int i = 0; i < Math.min(points.size(), 20); i++) {
double[] p = points.get(i);
System.out.printf(" 点%d: (%.3f, %.3f)%n", i, p[0], p[1]);
}
if (points.size() > 20) {
System.out.println(" ... 共 " + points.size() + " 个点");
}
}
}
2. 朴素的拒绝采样法
最直观的泊松盘采样思路是拒绝采样：随机生成候选点，如果它与所有已有点的距离都大于minDist，则接受；否则拒绝。
public class BlueNoiseGenerator {
/**
* 朴素拒绝采样法生成泊松盘采样
* 简单但效率低，随着点密度增加，接受率急剧下降
* @param maxAttempts 最大尝试次数
*/
public void generateNaive(int maxAttempts) {
points.clear();
// 第一个点随机放置
points.add(new double[]{
random.nextDouble() * width,
random.nextDouble() * height
});
int attempts = 0;
while (attempts < maxAttempts) {
double[] candidate = new double[]{
random.nextDouble() * width,
random.nextDouble() * height
};
boolean valid = true;
for (double[] p : points) {
if (distance(candidate, p) < minDist) {
valid = false;
break;
}
}
if (valid) {
points.add(candidate);
attempts = 0; // 重置尝试计数
} else {
attempts++;
}
}
}
}
3. Bridson快速泊松盘采样算法
Robert Bridson于2007年提出的算法是工业标准方案，核心思想是：
1. 维护一个”活跃列表”，存放最近生成但尚未处理完毕的点
2. 对活跃列表中的每个点，在以其为中心的环形区域（[minDist, 2*minDist]）内随机尝试k个候选点
3. 如果某个候选点与所有已有点的距离都≥minDist，则加入采样点和活跃列表
4. 如果一个点尝试了k次都失败，则将其从活跃列表移除
5. 使用背景网格加速邻居查询：将空间划分为cellSize = minDist/√2 的网格
public class BlueNoiseGenerator {
// 背景网格，用于加速邻居查询
private double cellSize; // 网格单元尺寸
private int gridWidth; // 网格列数
private int gridHeight; // 网格行数
private double[][] grid; // 网格：每个cell最多存储一个点
/**
* 初始化背景网格
* cellSize = minDist / sqrt(2) 保证每个cell最多一个点
*/
private void initGrid() {
this.cellSize = minDist / Math.sqrt(2.0);
this.gridWidth = (int) Math.ceil(width / cellSize);
this.gridHeight = (int) Math.ceil(height / cellSize);
this.grid = new double[gridWidth * gridHeight][];
}
/**
* 将坐标映射到网格索引
*/
private int gridIndex(double x, double y) {
int gx = (int) (x / cellSize);
int gy = (int) (y / cellSize);
gx = Math.max(0, Math.min(gx, gridWidth - 1));
gy = Math.max(0, Math.min(gy, gridHeight - 1));
return gy * gridWidth + gx;
}
/**
* 将点加入网格
*/
private void addToGrid(double[] p) {
int idx = gridIndex(p[0], p[1]);
grid[idx] = p;
}
/**
* 检查候选点是否与邻近网格中的点距离过近
* 只需检查周围5x5邻域的网格
*/
private boolean isValidCandidate(double[] candidate) {
int gx = (int) (candidate[0] / cellSize);
int gy = (int) (candidate[1] / cellSize);
// 检查周围5x5邻域（实际上因为cellSize的选取，只需检查3x3就够了）
for (int dy = -2; dy <= 2; dy++) {
for (int dx = -2; dx <= 2; dx++) {
int nx = gx + dx;
int ny = gy + dy;
if (nx < 0 || nx >= gridWidth || ny < 0 || ny >= gridHeight) {
continue;
}
int idx = ny * gridWidth + nx;
double[] neighbor = grid[idx];
if (neighbor != null && distance(candidate, neighbor) < minDist) {
return false;
}
}
}
return true;
}
/**
* 在指定点附近生成环形区域内的随机候选点
* @param center 中心点
* @return 候选点坐标
*/
private double[] randomPointInAnnulus(double[] center) {
// 随机角度
double angle = random.nextDouble() * 2 * Math.PI;
// 随机半径：[minDist, 2*minDist]
double radius = minDist * (1 + random.nextDouble());
return new double[]{
center[0] + radius * Math.cos(angle),
center[1] + radius * Math.sin(angle)
};
}
/**
* Bridson快速泊松盘采样算法
* 时间复杂度近似O(N)，N为生成的点数
*/
public void generateBridson() {
points.clear();
activeList.clear();
initGrid();
// 步骤1：随机放置第一个点
double[] first = new double[]{
random.nextDouble() * width,
random.nextDouble() * height
};
points.add(first);
activeList.add(first);
addToGrid(first);
// 步骤2：主循环
while (!activeList.isEmpty()) {
// 随机选择一个活跃点（也可以顺序选择）
int activeIdx = random.nextInt(activeList.size());
double[] activePoint = activeList.get(activeIdx);
boolean found = false;
// 尝试k个候选点
for (int i = 0; i < k; i++) {
double[] candidate = randomPointInAnnulus(activePoint);
// 候选点必须在边界内，且与已有邻居保持距离
if (inBounds(candidate) && isValidCandidate(candidate)) {
points.add(candidate);
activeList.add(candidate);
addToGrid(candidate);
found = true;
break;
}
}
// 如果k次尝试都失败，将该点从活跃列表移除
if (!found) {
activeList.remove(activeIdx);
}
}
}
}
4. 质量评估与可视化辅助
为了验证生成的采样是否具有良好的蓝噪声特性，我们可以计算最近邻距离分布和均匀性指标。
public class BlueNoiseGenerator {
/**
* 计算每个点到其最近邻的距离
* @return 所有点的最近邻距离数组
*/
public double[] nearestNeighborDistances() {
double[] distances = new double[points.size()];
for (int i = 0; i < points.size(); i++) {
double minD = Double.MAX_VALUE;
for (int j = 0; j < points.size(); j++) {
if (i == j) continue;
double d = distance(points.get(i), points.get(j));
if (d < minD) {
minD = d;
}
}
distances[i] = minD;
}
return distances;
}
/**
* 评估采样质量：计算最近邻距离的平均值和标准差
* 高质量的蓝噪声应该具有较小的标准差（距离均匀）
*/
public void evaluateQuality() {
double[] nnd = nearestNeighborDistances();
double sum = 0;
for (double d : nnd) sum += d;
double mean = sum / nnd.length;
double variance = 0;
for (double d : nnd) {
variance += (d - mean) * (d - mean);
}
variance /= nnd.length;
double stdDev = Math.sqrt(variance);
System.out.printf("采样质量评估：%n");
System.out.printf(" 总点数: %d%n", points.size());
System.out.printf(" 最小距离要求: %.3f%n", minDist);
System.out.printf(" 平均最近邻距离: %.3f%n", mean);
System.out.printf(" 标准差: %.3f (越小越均匀)%n", stdDev);
System.out.printf(" 变异系数: %.3f%%%n", (stdDev / mean) * 100);
// 统计距离分布
int[] buckets = new int[10];
for (double d : nnd) {
int bucket = (int) ((d - minDist) / (minDist * 0.5));
if (bucket >= 0 && bucket < 10) {
buckets[bucket]++;
}
}
System.out.println(" 最近邻距离分布（相对于minDist）：");
for (int i = 0; i < 5; i++) {
double low = minDist + i * minDist * 0.5;
double high = low + minDist * 0.5;
System.out.printf(" [%.2f, %.2f): %d 点%n", low, high, buckets[i]);
}
}
/**
* 生成ASCII艺术风格的采样可视化
* 将采样区域划分为字符网格，有点的位置显示'*'
*/
public void visualizeASCII(int charWidth, int charHeight) {
char[][] canvas = new char[charHeight][charWidth];
for (char[] row : canvas) {
Arrays.fill(row, ' ');
}
for (double[] p : points) {
int cx = (int) (p[0] / width * (charWidth - 1));
int cy = (int) (p[1] / height * (charHeight - 1));
cx = Math.min(cx, charWidth - 1);
cy = Math.min(cy, charHeight - 1);
canvas[charHeight - 1 - cy][cx] = '*';
}
System.out.println("采样分布可视化：");
for (char[] row : canvas) {
System.out.println(new String(row));
}
}
}
5. 应用示例：游戏场景中的树木分布
蓝噪声最典型的应用之一是在游戏场景中自然地分布物体（如树木、石头、草丛），既避免规则排列的人工感，又防止完全随机导致的过度聚集。
public class BlueNoiseGenerator {
/**
* 游戏场景物体类型
*/
public static enum GameObject {
TREE("树", 0.3),
ROCK("岩石", 0.2),
BUSH("灌木", 0.15),
FLOWER("花朵", 0.1);
final String name;
final double radius; // 物体占据的半径
GameObject(String name, double radius) {
this.name = name;
this.radius = radius;
}
}
/**
* 使用蓝噪声在游戏地图上分布多种物体
* 不同物体类型使用不同的minDist参数
* @param objects 要分布的物体类型列表
* @return 分布结果：(x, y, 物体类型)
*/
public List<Object[]> distributeGameObjects(List<GameObject> objects) {
List<Object[]> placed = new ArrayList<>();
// 为每种物体类型分别生成蓝噪声采样
for (GameObject obj : objects) {
// 使用物体半径作为最小间距
BlueNoiseGenerator subGen = new BlueNoiseGenerator(
width, height, obj.radius * 2.5, 30);
subGen.generateBridson();
for (double[] p : subGen.getPoints()) {
// 检查是否与已放置的物体重叠
boolean valid = true;
for (Object[] existing : placed) {
double ex = (Double) existing[0];
double ey = (Double) existing[1];
double er = ((GameObject) existing[2]).radius;
double dist = Math.sqrt((p[0]-ex)*(p[0]-ex) + (p[1]-ey)*(p[1]-ey));
if (dist < obj.radius + er) {
valid = false;
break;
}
}
if (valid) {
placed.add(new Object[]{p[0], p[1], obj});
}
}
}
return placed;
}
public List<double[]> getPoints() {
return new ArrayList<>(points);
}
}
6. 完整演示程序
public class BlueNoiseGenerator {
public static void main(String[] args) {
System.out.println("=== 蓝噪声泊松盘采样演示 ===\n");
double width = 50.0;
double height = 50.0;
double minDist = 3.0;
int k = 30;
// 1. 朴素拒绝采样
System.out.println("--- 朴素拒绝采样 ---");
BlueNoiseGenerator naive = new BlueNoiseGenerator(width, height, minDist, k);
long start = System.currentTimeMillis();
naive.generateNaive(10000);
long naiveTime = System.currentTimeMillis() - start;
System.out.println("耗时: " + naiveTime + "ms");
naive.evaluateQuality();
naive.visualizeASCII(50, 20);
System.out.println();
// 2. Bridson算法
System.out.println("--- Bridson快速算法 ---");
BlueNoiseGenerator bridson = new BlueNoiseGenerator(width, height, minDist, k);
start = System.currentTimeMillis();
bridson.generateBridson();
long bridsonTime = System.currentTimeMillis() - start;
System.out.println("耗时: " + bridsonTime + "ms");
bridson.evaluateQuality();
bridson.visualizeASCII(50, 20);
System.out.println();
// 3. 对比分析
System.out.println("--- 性能对比 ---");
System.out.printf("朴素法: %d 点, %dms%n", naive.getPoints().size(), naiveTime);
System.out.printf("Bridson: %d 点, %dms%n", bridson.getPoints().size(), bridsonTime);
// 4. 游戏物体分布示例
System.out.println("\n--- 游戏场景物体分布 ---");
BlueNoiseGenerator scene = new BlueNoiseGenerator(100, 100, 2.0, 30);
List<GameObject> objects = Arrays.asList(
GameObject.TREE, GameObject.ROCK, GameObject.BUSH
);
List<Object[]> placed = scene.distributeGameObjects(objects);
System.out.println("共放置 " + placed.size() + " 个物体：");
for (int i = 0; i < Math.min(placed.size(), 15); i++) {
Object[] o = placed.get(i);
System.out.printf(" %s at (%.1f, %.1f)%n",
((GameObject)o[2]).name, (Double)o[0], (Double)o[1]);
}
}
}
算法复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 实际性能 |
|---|---|---|---|
| 朴素拒绝采样 | O(N² × maxAttempts) | O(N) | 慢，接受率随密度下降 |
| Bridson算法 | O(N) | O(N) | 快，线性时间 |
其中N为生成的采样点数。Bridson算法之所以高效，关键在于背景网格将每次邻居查询的时间从O(N)降为O(1)（只需检查固定数量的邻域网格）。
扩展方向
- 渐进式蓝噪声：在已有采样点的基础上增量添加新点，适用于动态场景和流式数据。
- 有界约束采样：在复杂多边形区域或带权区域内进行蓝噪声采样，需要结合拒绝采样和距离场计算。
- 3D蓝噪声：将算法扩展到三维空间，用于体积渲染中的采样点分布和3D打印中的支撑结构优化。
- 瓦片化蓝噪声：生成可无缝拼接的蓝噪声纹理瓦片，用于实时渲染中的重复纹理。
小结
蓝噪声是一种兼具随机性和均匀性的理想采样分布。Bridson泊松盘采样算法通过”活跃列表+环形候选+背景网格加速”的三重策略，将原本指数级耗时的拒绝采样优化到了近似线性时间。这种”既随机又规则”的分布特性，使其成为游戏开发、计算机图形学和科学计算中不可或缺的工具——无论是场景中的树木分布、渲染中的采样点布局，还是纹理抖动中的像素排列，蓝噪声都能提供比白噪声更优的视觉效果。
