【光线追踪】Segment Tracing:一种可能加速距离场求交的实时光线追踪方案

ycz

计算机图形学民科

本文将讲述对

Segment Tracing Using Local Lipschitz Boundshal.archives-ouvertes.fr

一文的理解，以及从该论文的思路进行延申，探讨一种加速储存在体素中距离场求交的可能性。

本文很长，里面描述了鄙人对该论文的不成熟的思考。为了读者能够流畅阅读，就不为了阅读量分开写了直接把全部内容写在这一篇文章里面。

我的b站账号

哔哩哔哩 ( ゜- ゜)つロ乾杯~ Bilibilispace.bilibili.com

不定期更新独立游戏制作以及渲染方面的视频，求关注一波(♥ó㉨ò)ﾉ♡

零.写在前面

一.基本概念/数学基础铺垫

1. $C^{n}$ 函数

2.Lipschitz连续

3.“Tracing”的数学意义

4.“Tracing”和Lipschitz的关系

二.论文的实现

1.论文的思路

2.Segment，Local Lipschitz Bound ，安全Step距离，增强系数

3.Distance falloff function（距离衰减函数）

4.Field Function

5.Lipschitz bound

6.距离场的变形

三.本文的实现

1.Field Function

2.Lipschitz bound

四.渲染管线概述

1.SDF的生成

2.Packing

3.Instacing

4.渲染

五.参考文献

零.写在前面

鄙人一开始在shadertoy里按照自己的理解从example code改写了一个阉割版的Segment Tracing,把论文里的Distance Falloff Function砍掉了：

Segment Tracingwww.shadertoy.com

trace的step数是减少了但是为了求出距离场的gradient，要取距离场的值3~6次（单边双边求导），导致最后速度未必比原始的Sphere tracing更快。

然后论文原作者应该是看我做的效果太差忍不住吐槽我然后自己做了一个新的版本：

(等等他好像没看我的描述，我就是把Distance Falloff砍掉了为了能方便求任意一个距离场的Gradient)

好吧可能他一开始也考虑到了，不然这个论文也诞生不了了。但是没有关系，鄙人还是会继续按照个人理解来把这篇文章写下去。

顺便悄悄再吐槽一下，他的shadertoy的official实现只比原来的enhanced sphere tracing快2~3倍，而且这个优化是未定的，根据最后的threshold和物体表达式/导数表达式的复杂度有较大的变化（说白了就是未必真的优化了）。而在他的youtube上说的是gpu上同样是shadertoy是10倍的效率。

youtube上演示的是几十个球，而最后公开的是3个球。虽然有c++的cpu版本，速度确实快了很多。但是我对他gpu环境下的速率这点是十分存疑的。

但是当然，这篇论文无论从数学上的推导还是现实中的实现，无可置疑地减少了距离场函数的Query的数量。而且这篇论文还提供了其他距离场变形的解决方案。因此，还算是比较实用。

Query次数：左边Segment Tracing，右边Sphere Tracing采样次数：左边Segment Tracing，右边Sphere TracingOfficial版本的Segment Tracing，使用了Falloff Function

一.基本概念/数学基础铺垫

1. $C^{n}$ 函数

0到n阶导数都连续的函数就是 $C^{n}$ 函数， $C^{\infty}$ 则是光滑函数

这篇论文一直强调 $C^{2}$ 连续是因为其在Distance Falloff函数一次求导后得到 $g'$ ,而为了求 $g'$ 的min max bound则需要求一个二阶导数。如果不是 $C^{2}$ 连续推导就不成立了。

2.Lipschitz连续

$\forall a,b \in S, \left| f(a)-f(b) \right| \leq \lambda\left| a-b \right|$

, $\lambda$ 存在且其最小值为Lipschitz Constant。

$\lambda=1$ 时称为1-Lipschitz

这个定义可以先放着，后面会用到

3.“Tracing”的数学意义

如今有许多的Tracing，随着RTX各种Tracing都开始兴起。那么何为Tracing，Trace的是什么呢。结合论文内容，以下是我个人理解。

对于常见的metaball和shadertoy上各种酷炫的场景，他们都是trace的隐式表面。其中有密度场的隐式表面，也有距离场的隐式表面。这里面的隐式表面是等值面的一种，定义如下

$S=\left\{ p\in R^{3} | f(p) = 0 \right\}$ （是点集）

对于密度场0可以变成0.5（或者其他的）

既然是Trace，那么就应该有射线。一条射线的方程可以被定义为

$\delta(t) = \vec{o}+t\vec{u}$

$\vec{o}$ 即使origin，是射线是起点， $\vec{u}$ 是direction，是射线的方向。t是一个一维的数。

Trace的最终目的是找到射线与隐式表面的交点。一个最直接的想法就是，找到射线上所有使 $f$ 都为0的点，即：

$\left\{ \delta(t) | f(\delta(t))=0 \right\}$ （这里我不用复合符号，方便理解理解）

Tracing到这里变成了寻找这个方程的解，换句话说找到这个方程的解便是tracing的目的。

4.“Tracing”和Lipschitz的关系

回想Lipschitz连续的定义，对于一个函数空间里描述场的函数，如果他是Lipschitz连续的，一定有

$\forall p,q\in \Omega,\left| f(p)-f(q) \right| \leq\lambda\left| \left| p-q \right| \right|$

$\Omega$ 可以简单理解为整个三维空间，且这个 $\lambda$ 必定存在

对这个表达式变形：

$\left| f(p)-0 \right| \leq\lambda\left| \left| p-q \right| \right|$

此时 $q$ 变成了前面所提到的等值面(等值为0)上的一点

$\left| \left| p-q \right| \right|$ 形象地来说就是射线上走的一段距离

此时我们需要知道下一步要走多远才是安全的，于是再次变形

$\frac{\left| f(p)-0 \right|}{\lambda} \leq\left| \left| p-q \right| \right|$

只要 $\lambda$ 是Lipschitz Constant，我们可以知道每一步走 $\frac{\left| f(p)-0 \right|}{\lambda}$ 就是安全的

这是我对Tracing的数学意义的理解。

二.论文的实现

1.论文的思路

根据 $\frac{\left| f(p)-0 \right|}{\lambda}$ 可以得知， $\lambda$ 为整个 $f$ 的Lipschitz constant时才成立。这样显然会带来问题，如果某一局部区域的Lipschitz constant十分小，而另外一局部区域的Lipschitz constant十分大，会导致tracing的效率变得异常低下。

因此原文提出了Local Lipschitz Bound的概念。

2.Segment，Local Lipschitz Bound ，安全Step距离，增强系数

定义segment是一段线段，

$e(t,\varepsilon)=\left[ \delta(t),\delta(t + \varepsilon) \right]$

第一个参数t是射线上segment的起点到射线的origin的距离，第二个参数代表segment的长度。

Local Lipschitz Bound：

$\lambda(e(t,\varepsilon))$

从segment计算得来

通常来说， $\varepsilon$ 越大， $\lambda(e(t,\varepsilon))$ 的值也越大。

安全Step距离：

$s(t,\varepsilon)=min(\frac{\left| f(\delta(t)) \right|}{\lambda(e(t,\varepsilon))},\varepsilon)$

定义安全距离的意义是防止线段与等值面相交：

$min(\frac{\left| f(\delta(t) \right|}{\lambda(e(t,\varepsilon))},\varepsilon)\leq\left| \left| \delta(t) -q \right| \right|$

增强系数

其实读到这里会心一笑，寻思前面推导一本正经最后还是回归到调参吗，不过这里先把疑问放一边。

定义增强系数 $\kappa$

用 $\kappa s(t,\varepsilon)$ 来控制下一个候选的 $\varepsilon$

这里不用太纠结了，论文已经得出结论 $\kappa\approx2$ 时效果最好。

3.Distance falloff function（距离衰减函数）

这里引入一个新的函数，Distance falloff function $g$

这个函数描述了沿着距离等值面的线上的密度该如何分布。

比如 $g(d)=d$ ,那就是线性分布，离得越远反而密度越高。

常用的三次衰减（也就是论文里用的）

$g(d)=(1-d^2)^3$

他长这样：

距离衰减函数

离得越远密度越小，而且很平滑（提一下 $C^2$ 连续，忘了的读者可以往前翻康康基础概念）。

4.Field Function

前面稍微铺垫了一下tracing的意义，这里就派上了用场。

首先是不带距离衰减的函数，根据前面的意义很容易得出：

$f(t)=d(\delta(t))$

其中 $d(x)$ 函数是距离场函数，描述到一个图形的距离，iq的个人页面上有很多可以供参考

接下来加上距离衰减：

$f(t)=g(d(\delta(t)))$

这样就得到了一个描述沿着射线的场变化的函数。

5.Lipschitz bound

首先对 $f(t)$ 进行求导

$f'(t)=g'(d(\delta(t)))(\nabla d(\delta(t))\cdot\delta'(t))$

$\delta'(t)$ 恒等于 $\vec{u}$ 方向向量

$\lambda(e)\leq\left| g'(d(\delta(e))) \right|\left| \nabla d(\delta(e))\cdot\ \vec{u} \right|$

我们先看后面的一项Gradient Bound

考虑到 $\left| \left| \nabla d_{\partial\Omega}(x) \right| \right|=1$ ， $d_{\partial\Omega}$ 是1-Lipschitz的

所以有 $\left| \nabla d(\delta(e))\cdot\ \vec{u} \right|\leq1$

如果要获得更精准的范围，可以用解析解，当然这个只有在 $d$ 是简单函数的时候可行。

如果有解析解

如果 $d$ 是储存在体素里的，貌似这个方法就会翻车。

然后再看回来前面的一项Falloff Bound

我觉得前面这项是这篇论文的精髓。

令 $x=d(\delta(e))$

$\left| g'(d(\delta(e))) \right|$ 可被简单地看为 $\left| g'(x) \right|$

要分析 $\left| g'(x) \right|$ 的最大最小值，就要对 $g'$ 再次求导。

之所以前面强调 $C^2$ 连续就是因为这个。

但是对于 $x=d(\delta(e))$ 来说，大部分情况都很难求出解析解

因为 $d$ 是1-Lipschitz的，对于一个segment $e$ 来说，

取中点 $c=\delta(t+0.5\varepsilon)$

$d(c)-d(\delta(t))\leq \left| \delta(t)-\delta(t+0.5\varepsilon) \right|$

$-d(c)+d(\delta(t+\varepsilon))\leq \left| \delta(t+\varepsilon)-\delta(t+0.5\varepsilon) \right|$

$\left| \delta(t)-\delta(t+0.5\varepsilon) \right|=\left| \delta(t+\varepsilon)-\delta(t+0.5\varepsilon) \right|=0.5\varepsilon$

$d(\delta(t))\geq d(c)-0.5\varepsilon$

$d(\delta(t+\varepsilon))\leq d(c)+0.5\varepsilon$

$d(\delta(e))\subset[d(c)-0.5\varepsilon,d(c)+0.5\varepsilon]$

这样就能求得 $\left| g'(d(\delta(e))) \right|$ 的最大最小值

6.距离场的变形

受限于篇幅，这部分略过

三.本文的实现

看了这篇论文之后，对其思路有了更深的认识。思考着对于储存在体素内的距离场，能不能实现类似的加速算法呢。于是我从沿着射线的场函数开始，对论文内容进行了一点修改。

1.Field Function

储存在体素里的距离场是不需要带衰减的，因此衰减项可以简单认为是 $g(d)=d$

因此函数变成了

$f(t)=d(\delta(t))$

2.Lipschitz bound

一样地对Field Function进行求导:

$h(t) = (d(\delta(t)))'=\nabla d(\delta(t))\cdot\delta '(t)$
$\nabla d(\delta(t))\cdot\delta '(t) = \nabla d(\delta(t))\cdot \vec{u}$
$\lambda(e)\leq\left| \nabla d(\delta(e))\cdot\ \vec{u} \right|$

很明显这个表达式就是前面提到的Gradient Bound。

由于距离场储存在体素里，因此要获得这个项的解析解基本不可能。

因此只能采用估算的办法：

对于每一段segment $e$

$\lambda(e)\leq \sup_{\varepsilon_{i}\in [0,\varepsilon]} h(t+\varepsilon_{i})$

因为多算一次就会多一次采样，因此本文的方案只采样初始点和结束点以及中点。

$\lambda(e)\leq max(h(t),h(t+0.5\varepsilon),h(t+\varepsilon))$

3.优化

由于对于每次Query，都要对距离场进行三次（或者以上）的求导。因此有以下优化思路：

a.将距离场的梯度提前计算，并储存在体积里；

b.将每次采样结果暂存，后面query的时候可以复用；

两种方法并不冲突。

对于方法a，储存在体积中的梯度信息会因为分辨率不足以及采样时的插值问题而变得平滑，对此解决方案可以是提高梯度信息的分辨率。同时由于储存多了3倍的数据，这个优化方案是用空间换时间，而且牺牲了一定的精度。为此还可能会占用大部分带宽。可以用一定压缩算法（DXT，ETC）来减少所需空间。

对于方法b，目前还没有好的算法实现，以后想到再说。

四.渲染管线概述

1.SDF的生成

https://github.com/christopherbatty/SDFGengithub.com http://advances.realtimerendering.com/s2015/DynamicOcclusionWithSignedDistanceFields.pdfadvances.realtimerendering.com

在生成SDF的同时，计算Gradient：

$\nabla d(p_{i,j,k})=0.5(d(p_{i+1,j,k})-d(p_{i-1,j,k}),d(p_{i,j+1,k})-d(p_{i,j-1,k}),d(p_{i,j,k+1})-d(p_{i,j,k-1}))^{T}$

将Distance和Gradient同时存到文件里读取。

这里也有Runtime的生成算法，在此不赘述。

2.Packing

要同时渲染多个模型，就一定会有多个体积数据。为了减少Binding本文使用了一种3d bin packing的算法将所有要用到的体积都尽可能地打包在一张体积贴图（DataPool）里。

3d bin packwww.drupal.org

这篇论文的Example Code长这样：

要抄也不容易（汗颜

3.Instancing

为了一些模型可以重复使用，本文写了一个简单的instance pipeline。

这里的指针是指向Datapool的三维坐标信息

M矩阵就是模型的平移旋转缩放矩阵了，在求得局部空间的法线之后需要使用

而M的逆则是将射线变换到局部空间再进行Tracing时可以用上

用对偶四元数说不定可以剩下一点空间，本文不在赘述

如果算上其他信息，Instance的信息会比较爆满。

4.渲染

用的是之前使用Vulkan写的渲染器。关于渲染器的部分可以参考之前的文章：

狮子的大背头Sketchfab里的模型近距离的artifact

本文的演示将Segment Tracing用在了Path Tracing上，可能并不能带来最佳的效果，最明显的一个缺点是因为SDF的分辨率过小导致物体丢失高频的细节，或者是精确求交时会因为采样的插值产生Artifact。

如果Segment Tracing结合Cone Tracing，在mipmap pyramid里进行多层级的求交，来求一些如AO，漫反射全局光照，软阴影等效果可能会更好。

五.参考文献

感谢阅读。

如果这篇文章对你有帮助，不妨点赞留言关注我，我会不定期更新图形学方面的文章，与大家探讨心得。如果文章有纰漏，还请在评论区留言斧正。

【光线追踪】Segment Tracing:一种可能加速距离场求交的实时光线追踪方案

【光线追踪】Segment Tracing:一种可能加速距离场求交的实时光线追踪方案

目录：

零.写在前面

一.基本概念/数学基础铺垫

二.论文的实现

三.本文的实现

四.渲染管线概述

五.参考文献

零.写在前面

一.基本概念/数学基础铺垫

1. 函数

2.Lipschitz连续

3.“Tracing”的数学意义

4.“Tracing”和Lipschitz的关系

二.论文的实现

1.论文的思路

2.Segment，Local Lipschitz Bound ，安全Step距离，增强系数

3.Distance falloff function（距离衰减函数）

4.Field Function

5.Lipschitz bound

6.距离场的变形

三.本文的实现

1.Field Function

2.Lipschitz bound

3.优化

四.渲染管线概述

1.SDF的生成

2.Packing

3.Instancing

4.渲染

五.参考文献

Recommend

About Joyk

1. $C^{n}$ 函数