错误使用 Signed Distance Function (SDF) 的方式
错误使用 Signed Distance Function (SDF) 的方式
免责声明：以这种方式使用 SDF 并没有什么错误。
最近，我的好朋友 Mike Brondbjerg 在 Twitter 上发布了以下内容：
Dark Matter: 50,000 particles passing through a field until they hit a hidden sphere. By varying the distance travelled each step, the collisions are more / less accurate, so creating a nice fuzziness around the spheres. #generative #design #creativecommuting #creativecoding pic.twitter.com/gmFEV7fCwk — Mike Brondbjerg (@mikebrondbjerg) January 15, 2020
你可以关注他，看看这个想法是如何演变成他标志性的美丽、优雅的线条画的。
Dark Matter: random walk obstacle avoidance… nice random output. #creativecoding #generative #design #processing pic.twitter.com/DTzy7H2G6Z — Mike Brondbjerg (@mikebrondbjerg) January 26, 2020
球体
Mike 的帖子给了我一个想法，一种介绍我在一些作品中喜欢使用的概念的方式：signed distance functions（SDF）。SDF 通常与光线追踪和着色器相关联，而学习这方面知识的最佳来源无疑是 Shadertoy 的 Inigo Quilez：https://iquilezles.org/。
但是有一种非常错误的使用 SDF 的方式。它们在光线追踪和着色器中的主要用途是定义无网格几何体。例如，一种绘制平滑球体而无需生成大量三角形的方法。我在这里展示的用法恰恰相反：生成几何体，实际上是点云。几何体在屏幕上渲染之前需要以传统方式进行处理。
假设我们想要处理类似于推文中的东西：粒子与球体碰撞。一种方法是计算粒子到球体中心的距离，我们将其保持在原点。对于位置 (x,y,z)(x,y,z)(x,y,z) 的粒子 p⃗ \vec{p} p, 这个距离由下式给出：d(p⃗)=x.x+y.y+z.z {d( \vec{p} )=\sqrt{x.x+y.y+z.z}}d(p)=x.x+y.y+z.z。如果该距离 ddd 大于球体的半径 r rr，则粒子在球体外部，如果小于则在内部，如果完全相同，则在表面上。
{d(p⃗)<r,if p⃗ is insided(p⃗)=r,if p⃗ is on sphered(p⃗)>r,if p⃗ is outside\begin{cases} d( \vec{p} )<r, & \text{if } \vec{p}\text{ is inside} \\ d( \vec{p} )=r , & \text{if } \vec{p}\text{ is on sphere}\\ d( \vec{p} )>r, & \text{if } \vec{p}\text{ is outside} \end{cases}⎩⎪⎪⎨⎪⎪⎧d(p)<r,d(p)=r,d(p)>r,if p is insideif p is on sphereif p is outside
使用这个，我们可以每一步检查粒子。只要它们到球体的距离大于半径，它们就没事。如果一个粒子走了一步，它的距离变得小于或等于半径，它就撞到了球体。
一个粒子网格飞入一个球体。一些粒子与球体发生了碰撞，其余的粒子正在冲向无限远。
如果球体不在原点，而是以点 c⃗(cx,cy,cz) \vec{c} (cx,cy,cz) c(cx,cy,cz) 为中心，则距离函数变为 d(p⃗,c⃗)=(x−cx).(x−cx)+(y−cy).(y−cy)+(z−cz).(z−cz) {d( \vec{p} , \vec{c} )=\sqrt{(x-cx).(x-cx)+(y-cy).(y-cy)+(z-cz).(z-cz)}}d(p,c)=(x−cx).(x−cx)+(y−cy).(y−cy)+(z−cz).(z−cz)。通常，这被解释为从 p⃗ \vec{p} p 到 c⃗ \vec{c} c 的向量的长度。另一种看待它的方式（这将对我们有所帮助）是想象我们将球体移动到原点，c⃗→0⃗ \vec{c}\to\vec{0} c→0，整个空间随之移动。然后我们的粒子被移动 p⃗→p⃗−c⃗ \vec{p}\to\vec{p}-\vec{c} p→p−c。检查 p⃗ \vec{p} p 处的粒子是否与中心在 c⃗ \vec{c} c 的球体碰撞，与检查 p⃗−c⃗ \vec{p}-\vec{c} p−c 处的粒子是否与原点的球体碰撞相同。
由于我们可以将球体放置在任何我们想要的位置，因此我们可以添加多个球体。然后针对不同的球体逐个测试每个粒子。
一个粒子网格飞入一堆球体。
Distance Fields
在创意编码中，拥有多个视角来观察事物通常很有用。上面的等式可以重构：
{d(p⃗)−r<0,if p⃗ is insided(p⃗)−r=0,if p⃗ is on sphered(p⃗)−r>0,if p⃗ is outside\begin{cases} d( \vec{p} )-r<0, & \text{if } \vec{p}\text{ is inside} \\ d( \vec{p} )-r=0 , & \text{if } \vec{p}\text{ is on sphere}\\ d( \vec{p} )-r>0, & \text{if } \vec{p}\text{ is outside} \end{cases}⎩⎪⎪⎨⎪⎪⎧d(p)−r<0,d(p)−r=0,d(p)−r>0,if p is insideif p is on sphereif p is outside
实际上没有任何变化，等式仍然相同。但是它们描述的是一个函数 d(p⃗)−r {d( \vec{p} )-r}d(p)−r，它将空间分为三个区域：球体外部的一个区域，具有正值；球体内部的一个区域，具有负值；以及球体本身的表面，该函数等于零。这是半径为 r rr 的原点球体的 signed distance function。
在每个步骤中测试粒子本质上是相同的评估：计算 p⃗ \vec{p} p 处的函数并查看它如何分类。以这种方式看待它的优点是 signed distance function 可以轻松替换，并且我们突然检查与盒子、圆环或任何具有明确定义的 SDF 的形状（例如 Inigo 维护的列表）的碰撞。
一个粒子网格飞入一堆盒子。
就其本身而言，没有什么可以阻止我们使用第一种方法来计算点到某些特定几何体的距离。但我发现 SDF 使它更加直观，特别是当我们开始修改和组合它们时。
并非每个函数都是 signed distance function，都有一定的要求。我不会详细介绍严格的数学细节，主要是因为我没有足够的资格来完成它。从本质上讲，它的变化率必须与您对距离的期望相对应。如果我们沿着函数的斜率向下，我们期望最终到达表面。如果我们朝着它迈出小步，距离应该以小步递减，而不是突然改变斜率或开始增加。
作为一名创意编码员，我们首先想到的事情之一是“添加噪声”，这不是一个数学上有效的距离函数。向球体的 SDF 添加噪声并不能为我们提供嘈杂球体的 SDF。幸运的是，作为创意编码员，我们可以选择放弃严格性，让混乱给我们带来惊喜。
噪声可能不是有效的距离函数，但仍然很有趣。
Tracer 类
尽管可以在网上找到大量信息和函数，但可能并不立即清楚如何在 Processing 中使用其中的任何一个。通常，代码以 OpenGL Shading Language (GLSL) 给出，并且使用的函数并不总是显而易见的。GLSL 的创建是为了以统一的方式处理数字和向量。像 max(v,0.0) 这样的函数看起来很熟悉，但在 GLSL 中也可以在向量上按组件工作，这是 Processing 无法处理的。当不熟悉 GLSL 时，转录 SDF 函数可能会令人困惑。
在本节中，我们将创建用于上述图像的代码。最后，我们将拥有一个简陋的框架，可以用来构建更复杂的作品。让我们从一些方便的类开始，Point 和 Vector。
Java
class Point {
float x, y, z;
Point(float x, float y, float z) {
this.x=x;
this.y=y;
this.z=z;
}
}
---|--- Java
class Vector {
float x, y, z;
Vector(float x, float y, float z) {
this.x=x;
this.y=y;
this.z=z;
}
}
---|---
两者都只是坐标的容器。没有真正的理由说明我们为什么不能为此使用 Processing 的 PVector，或者为什么我们同时拥有 Point 和 Vector。但对于本教程，以尽可能少的抽象来谈论点和向量更容易。
另一个派上用场的类是 Ray，一条从 Point origin 开始的半线，方向由 Vector direction 给出。创建时，direction 被归一化，其长度被重新缩放到 1.0。函数 get(t) 将返回射线上的一个新 Point，距离其原点 t。
Java
class Ray {
Point origin;
Vector direction;
Ray(Point origin, Vector direction) {
this.origin=new Point(origin.x, origin.y, origin.z);
float mag=direction.x*direction.x+direction.y*direction.y+direction.z*direction.z;
assert(mag>0.000001);
mag=1.0/sqrt(mag);
this.direction=new Vector(direction.x*mag, direction.y*mag, direction.z*mag);
}
//Get point on ray at distance t from origin
Point get(float t) {
return new Point(origin.x+t*direction.x, origin.y+t*direction.y, origin.z+t*direction.z);
}
}
---|---
对于我们的小型框架，我们需要 signed distance functions。我们可以将函数硬连接到 sdf(Point p) 函数中，并在每次都更改该代码。但是，一点结构可以帮助进行探索。首先，我们需要告诉 Processing/JAVA 什么是 signed distance function：
Java
//Interface that implements a signed distance function
interface SDF {
float signedDistance(Point p);
}
---|---
如果关于 interface 是什么的细节不清楚，请不要担心。我们可以将其视为对 Processing 的承诺：我们标识为 SDF 的所有内容都将具有此函数 signedDistance(Point p)，该函数返回一个 float。 它是哪个类，我们如何创建该类的对象，该对象如何计算距离，这些都不重要，只要我们告诉 Processing 它是 SDF，它就可以调用该函数。 interface 可以用于定义变量，将对象传递给函数，几乎可以在任何我们可以使用类的地方使用。 我们不能做的是使用 new SDF() 创建一个新对象。
我们已经遇到一个 signed distance function，即半径为 r 且位于原点的球体的 d(p⃗)−r {d( \vec{p} )-r}d(p)−r。 我们现在可以实现一个封装它的类。
Java
/*
GLSL code
https://iquilezles.org/www/articles/distfunctions/distfunctions.htm
float sdSphere( vec3 p, float s )
{
return length(p)-s;
}
*/
class SphereSDF implements SDF {
float radius;
SphereSDF(float r) {
radius=r;
}
float signedDistance(Point p) {
return sqrt(sq(p.x)+sq(p.y)+sq(p.z))-radius;
}
}
---|---
我们告诉 Processing 这个类实现了 SDF。 作为回报，我们需要履行我们的承诺并实现 signedDistance(Point p)。 现在，在 Processing 期望 SDF 的任何地方，我们都可以传递一个 SphereSDF，它将正常工作。
类似地，我们可以定义大小为 X、Y 和 Z 的原点处的盒子的 SDF。
Java
/*
GLSL code
https://iquilezles.org/www/articles/distfunctions/distfunctions.htm
float sdBox( vec3 p, vec3 b )
{
vec3 q = abs(p) - b;
return length(max(q,0.0)) + min(max(q.x,max(q.y,q.z)),0.0);
}
*/
class BoxSDF implements SDF {
float X, Y, Z;
BoxSDF(float x, float y, float z) {
X=x;
Y=y;
Z=z;
}
float signedDistance(Point p) {
float qx=abs(p.x)-X;
float qy=abs(p.y)-Y;
float qz=abs(p.z)-Z;
return sqrt(sq(max(qx, 0.0))+sq(max(qy, 0.0))+sq(max(qz, 0.0)))+min(max(qx, qy, qz), 0.0);
}
}
---|---
缺少一个部分，粒子。我们将沿着直线路径将粒子（Tracer）射入场景。当它们撞到某些东西时，它们会停止。否则，它们会在一定距离后停止。如果我们的碰撞几何体由网格定义，我们可以尝试将粒子的光线与几何体的面相交。然而，在这种情况下，毕竟是本教程的重点，我们通过 signed distance functions 定义了几何体。因此，我们将使用另一种寻找碰撞的技术：球体追踪。
想象一下，我们有一个由 SDF 定义的任意碰撞几何体，并假设我们有一些粒子从该几何体外部开始。我们知道在空间中的每个点，我们可以计算 signed distance sdf(p⃗) {sdf( \vec{p} )} sdf(p)。该距离（我们称之为 d d d）告诉我们几何体与该点有多接近，但它没有给我们一个方向。我们唯一能说的是，粒子可以在任何方向上安全地移动一段距离 d d d。换句话说，我们知道在该点我们可以放置一个半径为 d d d 的球体，并确保几何体不在该球体中。在极端情况下，如果粒子直接朝着几何体移动，它可能会直接在表面上结束，但它永远不会穿过它或进入内部。
以下图为例。我们从 P0 P_{0} P0 开始，选择的方向沿着蓝线。黑色三角形和矩形是我们的碰撞几何体。 sdf(P0) sdf( P_{0}) sdf(P0) 告诉我们，在以 P0 P_{0} P0 为中心的绿色圆圈中移动是安全的。
https://demosceneacademy.wordpress.com/
如果我们沿着蓝线走一大步，即最大安全距离，我们最终会到达 P1 P_{1} P1。 sdf(P1) sdf( P_{1}) sdf(P1) 不为零。我们的运动方向不是到达表面的最短路径。我们继续前进，这次步长为 sdf(P1) sdf( P_{1}) sdf(P1)，粒子最终到达 P2 P_{2} P2。我们可以重复此操作，直到返回的距离接近零，或者如果我们从未到达表面，则在到达截止距离之后。在图中，第四步将我们带到 P4 P_{4} P4，在表面上。
这项技术的好处是我们不必猜测步长。没有采取太多小步并浪费时间，或者采取太大步并超过碰撞的风险。SDF 通过动态调整步长自动处理此问题。
我们的 Tracer 粒子类如下所示：
Java
class Tracer {
Ray ray;
float cutoff;
float precision;
float t;
float closestDistance;
int steps;
int MAXSTEPS=10000;
Point p;
Tracer(Point origin, Vector direction, float cutoff, float precision) {
ray=new Ray(origin, direction);
this.cutoff=cutoff;
this.precision=precision;
initialize();
}
void initialize(){
closestDistance= Float.POSITIVE_INFINITY;
t=0;
steps=0;
p=ray.get(0);
}
void trace(SDF sdf) {
p=null;
t=0.0;
steps=0;
do {
traceStep(sdf);
steps++;
}
while (!onSurface() && t<cutoff && steps<MAXSTEPS);
if (t>cutoff) t=cutoff;
p=ray.get(t);
}
void traceStep(SDF sdf){
float d=sdf.signedDistance(ray.get(t));
if (d<closestDistance) closestDistance=d;
t+=d;
}
boolean onSurface(){
return closestDistance<=precision;
}
void reset() {
initialize();
}
}
---|---
每个 Tracer 都从 Point origin 开始，沿着 Vector direction。由于我们的粒子只沿直线移动，我们将它们存储为 Ray。我们还需要定义何时停止追踪粒子。数值舍入使得我们不太可能得到精确的 0.0 距离，因此我们检查距离是否变得小于某个值 precison。如果 tracer 没有击中，我们希望在一定距离（称为 cutoff）后停止。为了安全起见，我们限制了 tracer 可以采取的最大步数 MAXSTEPS。
Tracer 的当前状态保存在 4 个变量中：
t：沿射线行进的当前距离closestDistance：到目前为止粒子最接近表面的距离steps：到目前为止采取的步数p：粒子沿射线的当前位置
在每个步骤中，都会检查 signed distance function，并将粒子沿射线向前移动该距离。一旦满足以下三个条件之一，追踪就会停止：
closestDistance < precision：粒子已经比我们的精度阈值更接近表面：碰撞。t>=cutoff：沿射线行进的距离超过截止距离：没有碰撞。steps>=MAXSTEPS：采取的步数超过允许的最大数量。 这应该只在我们代码中犯了错误时才会发生。
无论如何，在追踪结束时，粒子要么在表面上，要么超出我们的感兴趣区域。
整合在一起
要重现此图像，我们需要创建一个 SDF，创建一些粒子并运行追踪。可以在此处找到包含类的脚本。
Java
float emitterX, emitterY, emitterZ;
ArrayList<Tracer> tracers;
SDF sdf;
void setup() {
size(900, 900, P3D);
smooth(16);
noCursor();
createTracers();
createSDF();
trace();
}
void createTracers() {
tracers=new ArrayList<Tracer>();
float x, y;
emitterZ=500;
float cutoff=2*emitterZ;
int resX=50;
emitterX=600.0;
int resY=50;
emitterY=600.0;
for (int i=0; i<resX; i++) {
x=map(i, 0, resX-1, -emitterX*0.5, emitterX*0.5);
for (int j=0; j<resY; j++) {
y=map(j, 0, resY-1, -emitterY*0.5, emitterY*0.5);
tracers.add(new Tracer(new Point(x, y, emitterZ), new Vector( 0, 0, -1), cutoff, 0.1));
}
}
}
void createSDF() {
SphereSDF ssdf=new SphereSDF(120);
sdf=ssdf;
}
void trace(){
for (Tracer tracer : tracers) {
tracer.trace(sdf);
}
}
void draw() {
background(15);
//setup perspective
translate(width/2, height/2, 0);
rotateY(0.8*QUARTER_PI);
translate(0, 0, 200);
//draw sphere
fill(0);
noStroke();
sphere(119);
//draw limiting plane
pushMatrix();
translate(0, 0, -emitterZ-1.0);
rect(-emitterX*0.5, -emitterY*0.5, emitterX, emitterY);
popMatrix();
//draw tracers
strokeWeight(2);
stroke(240);
for (Tracer tracer : tracers) {
point(tracer.p.x, tracer.p.y, tracer.p.z);
}
}
---|---
为了设置 tracer，我们创建了一个发射器，一个规则的 600*600 正方形网格，包含 50×50 个点。 此发射器位于原点“上方”的某个位置，即上图中的右侧。 每个点定义一个 Tracer，目标是沿负 Z 轴。 在此示例中，SDF 是位于原点的单个球体。 为了显示错过球体的 tracer，我们在截止距离处绘制了一个限制平面。
展望
这仅仅是开始。在下一部分中，我们将探讨如何扩展代码来操纵和组合 signed distance functions。
在 2017 年，我使用 tracer、SDF 和着色器效果的不同组合创建了一系列图像，展示了一些可能性。