1. 问题描述
先抛出算法提出背景,如下图所示,现在有三个单位向量(用橙色箭头表示)X,Y,Z,以立方体的中心点为起点,分别垂直于正方体的某个面,某条边以及指向某个顶点,这里给出的面,边以及顶点可以根据后面待考虑的向量(浅蓝色箭头)进行调整,现在任意给定的一个向量(以图中浅蓝色箭头表示)Q,希望能够给定一组系数A,B,C,使得:
而(A, B, C)也可以看成是向量Q在XYZ非正交基空间下的坐标。

这个问题可以进一步归纳为,给定任意三个不共面的单位向量,对于这三个向量所组成的非正交基空间内的任一向量,如何计算这个向量在这个空间中的坐标。

2. 2D空间算法
出于简化考虑,我们先来看一下2D空间中的相应问题,如下图所示,给出两个不共线的单位向量X,Y,对于这两个向量组成的2D空间中的任一向量,如何求得其在这两个非正交基上的坐标。

如上图所示,直观上来看,只需要从此向量的尾端向着两个方向引平行线,这两条平行线与另一方向轴的交点几维此方向上的坐标。那么公式上是怎么计算的呢?这里需要借助一点三角函数的知识,如下图所示:

其中P点为Q在X方向上的投影点,I为Q点在X方向上的正交投影点,如图中标注
假设X,Q,Y都是单位向量,那么这里就有:
也就是说向量Q在X向量上的坐标为,同理可求得Q在Y向量上的坐标为
当然,上面给出的是其中的一种解法,除此之外,还可以通过如下算法进行求取:
-
保留其中一个向量基,另外找一个与之正交的单位向量作为另一个向量基并用最初的XY向量表示出来,之后在这个的基础上就可以求出Q的坐标
-
考虑OQ实际上是OX在固定O点后朝着OY进行扫射后的结果,OQ在OX与OY上的投影坐标应该与扫过的角度存在一定的关系,根据函数的递增规律,这里使用
作为权重函数进行计算
不论采用哪种方法,结论并不会发生变化,这里就不详细介绍了。
3. 3D空间解法
2D空间算法给出的结论比较简洁,那么这个算法要如何扩展到3D空间呢?其实我们可以将问题拆分成两个2D空间的投影来看。

如上图所示,首先将Q投影到XY 2D空间,得到,注意为了满足前面的计算条件,这里
的长度应该要是1。之后先求取
在XY上的坐标,之后再求取Q在
上的坐标即可。
假设,就可以得到
的坐标为
再假设,就可以得到
的坐标为
本着一般性原则,由于XYZ三向量并没有特殊性,那么最终的坐标应该是对称的,也就是向2D解一样,但是我们可以看到XY坐标是两个sin除法之积,而Z坐标则仅仅是单个sin除法,因此对前面的算法做一下顺序调整,最终的结论应该是如下形式的,假设
这里的一个问题是,如何求取跟
,毕竟这里不是正交投影(即ZQ组成的平面可能与XY平面不是垂直的),不能直接通过对两个向量叉乘来得到投影方向。其实问题可以转换为如何求得
,由于
同时落在
与
平面上,那么肯定会与这两个平面的法线垂直,而由于这两个平面不平行,那么就可以通过两平面的法线叉乘得到
。
4. 近似解
前面给出的是准确解,但是其计算过程消耗有点高,尤其是3D空间,需要做大量的叉乘与点乘,如果是在PS中进行这项计算,就会导致大量的浪费,因此我们这里尝试给出一个近似解。
4.1 2D空间近似
精确解需要计算三个sin值+两个除法,而每个sin值的计算则包括一个点乘得到cos,之后使用sqrt求得,因此整个过程包含如下一些计算逻辑:
- dot * 3
- mul * 3
- add * 3
- sqrt * 3
- div * 2
由于XYQ都是单位向量,实际上Q就相当于固定X向量的起点朝着Y向量进行圆周转动,而转动的比例应该就近似于Q在XY上的投影坐标。正常求取这个转动比例需要使用arccos求得,或者计算其sin值(这种做法得到的恰恰就是精准解,其消耗也并无变化),但是这两种对于性能都没有什么优化,这里直接考虑使用余弦的倒数作为权重,那么其消耗仅仅包含以下几项:
- dot * 2
- div * 2
但是这种做法在精确度上存在较大误差,比如当OQ与OX重合时,由于OY与OX不垂直,此时OQ在OY上还有一定的投影权重,且这个权重与XY之间的夹角有着较大关系,当夹角较小时,这个值就会比较大,使得误差进一步变大。为了降低误差,这里考虑对余弦的倒数做一下处理,比如使用smoothstep对其数值进行限定,使得当OQ与OX重叠时,其权重在OY上为0(通过将作为smoothstep的max输入,1作为min输入即可做到),经过这种做法得到的结果与精确解之间的差异(diff = abs(diff_x)+abs(diff_y))如下图所示:

可以看到,在一些输入数据处,结果还是存在较大的偏差,不过优点在于两端位置具有较好的平滑性(即可以保证当某个向量权重为1时,其他向量的权重肯定为0),这种做法下的消耗为:
- dot * 2
- div * 2
- smoothstep * 2
3.1 add * 3 * 2
3.2 div * 2
3.3 mul * 3 * 2
看起来似乎是没有多大的提升。
如果直接使用clamp((x-a)/(b-a), min, max)取代smoothstep(min, max, x),得到的误差也并没有进一步增大,结果如下图所示:

在这种情况下,消耗就小得多了:
- dot * 2
- div * 2
- clamp * 2
3.1 add * 2 * 2
3.2 div * 2
4.2 3D空间近似
上面给出的算法在2D空间中具有非常简单的形式,但是如果放到3D空间中就无从下口了,因为这个时候,OQ在三个非正交基上面有三个投影,而虽然在每个非正交基上面对应的投影长度最小是等于1,最大则存在三个值(对应两两非正交基的夹角的余弦的倒数),这种情况下就很难使用前面2D的方法来求取当前向量OQ在每个非正交基上的近似权重了。
这个地方可以借助三角形插值的相关知识,如下图所示:

当前向量OQ在三个向量基OX,OY,OZ上的权重,可以参考文章三角形插值技术,比如可以直接以Q到XYZ三个顶点的距离的倒数作为权重,但是这里需要注意,前面2D中说过,如果不做特殊处理,当Q与X重叠时,使用这种方法在YZ上依然会有权重,这与事实不符,且容易导致结果跳变,因此这里需要对权重做一次smoothstep之类的过渡,保证当某个向量的权重为1时,其他向量的权重肯定为0。比如Q在X上的权重为1,那么就要使得其在Y/Z上的权重为0。
而由于这里有两个需要兼顾的向量Y&Z,因此需要分别各进行一次smoothstep,最终的结果应该是两个smoothstep结果的一个乘积才对。因为时间关系,这里只给出理论介绍,就不做实际测试了,后面如果有需要,再将相关数据补充进来。
网友评论