算法

图形算法

采样

米切尔最佳候选算法（Mitchell’s best-candidate algorithm）

从候选的采样点中选择出最佳采样点。

function sample() {
     var bestCandidate, bestDistance = 0;
     //numCandidates为固定数量候选采样点，这个越少算法运行速度越快，越大速度慢质量高
     for (var i = 0; i < numCandidates; ++i) {
          var c = [Math.random() * width, Math.random() * height],
          d = distance(findClosest(samples, c), c);
          //最佳采样点就是距离固定点最远的那个点
          if (d > bestDistance) {
               bestDistance = d;
               bestCandidate = c;
          }
     }
     return bestCandidate;
}

function distance(a, b) {
     var dx = a[0] - b[0],
     dy = a[1] - b[1];
     return Math.sqrt(dx * dx + dy * dy);
}

泊松圆盘采样算法（Poisson-disc）

比米切尔最佳候选算法（Mitchell’s best-candidate algorithm）效果更好些，方法是利用现有采样点一点点生成新的采样点，best-candidate是在整个采样区里生成新采样点。算法执行过程是使用红色表示活跃点，黑色标识固定采样点，等所有红色采样点都变成黑色算法结束。

确定