您需要 登录 才可以下载或查看，没有账号？注册
x
Hello . 大家好 今天分享一个快速计算到三角形距离的方法
在3D中计算到三角形的距离不难，但我经常看到太复杂的代码，有太多的平方根和分支。下面是我自己的实现，并在Shadertoy的射线追踪实验中使用过。
距离的计算是根据测试点相对于三角形的位置，计算到三角形边缘或三角形平面的距离。如果测试点位于通过三角形法线方向延伸三角形形成的棱柱内部，则点到三角形的最近距离是到三角形所在平面的距离。否则，如果点在外部，则最近距离将是到三个边中最近的一条边的距离。
计算到平面的距离很简单，只需计算点与三角形的一个角以及平面的法线（归一化）的点积。例如，如果v1、v2和v3是三角形的顶点（nor是两条边的叉积，通常是v2-v1和v1-v3），距离可以表示为d = dot(p - v1, nor) / length(nor)。
通过将点相对于边的一个顶点投影到边本身上，可以计算到边的距离，并确保投影不会超过第一个顶点或超过第二个顶点。例如，对于从顶点v1到顶点v2的边，点p到边的距离可以表示为d = length(p - v1 - v21 * clamp(dot(p - v1, v2 - v1) / dot(v2 - v1, v2 - v1), 0, 1))。
在将这两个表达式结合之前，我们需要确定评估点是在三角形的延伸棱柱内部还是外部。我们可以通过查看点是在每条边的内部还是外部半空间来判断。例如，dot(cross(v2-v1,nor),p2-v1)的符号可以测量这一点（你可以将其视为行列式或体积，或将其视为法线的方向与点到顶点和边的叉积的比较）。如果三个比较都给出正数，那么在三角形内部。如果任何一个比较有负号，就不在内部。
快速检查三个比较结果是否都为正数的一种方法是首先将这三个结果相加。如果所有结果都为负数，那么总和将为-3。如果其中一个为正数，总和将为-1。如果两个为正数，总和将为1。如果所有三个都为正数，总和将为3。因此，将总和与2进行比较将分离我们的两种情况——全部在内部或不在内部。
有了所有这些信息，我们现在可以以更或多或少有点优化的方式计算到三角形的距离：
float dot2( in vec3 v ) { return dot(v,v); }
float udTriangle( in vec3 v1, in vec3 v2, in vec3 v3, in vec3 p ){ // prepare data vec3 v21 = v2 - v1; vec3 p1 = p - v1; vec3 v32 = v3 - v2; vec3 p2 = p - v2; vec3 v13 = v1 - v3; vec3 p3 = p - v3; vec3 nor = cross( v21, v13 );
return sqrt( // inside/outside test (sign(dot(cross(v21,nor),p1)) + sign(dot(cross(v32,nor),p2)) + sign(dot(cross(v13,nor),p3))<2.0) ? // 3 edges min( min( dot2(v21*clamp(dot(v21,p1)/dot2(v21),0.0,1.0)-p1), dot2(v32*clamp(dot(v32,p2)/dot2(v32),0.0,1.0)-p2) ), dot2(v13*clamp(dot(v13,p3)/dot2(v13),0.0,1.0)-p3) ) : // 1 face dot(nor,p1)*dot(nor,p1)/dot2(nor) );}
注意最好预先计算大部分这些数据，例如v21、v32、v12、nor、cross(v21,nor)、cross(v32,nor)、cross(v13,nor)、1.0/dot2(v21)、1.0/dot2(v32)、1.0/dot2(v13)和1.0/dot2(nor)。
还要注意，我将边距离所需的平方根移到了分支外部。这样做的好处是，如果我们要计算到一个由许多三角形组成的网格的距离，我们可以将平方根移动到更全局的范围内，并迭代所有涉及的三角形而不进行平方根计算，取得最小的平方距离，并在最后一次仅进行一次平方根计算。
shadertoy链接：https://www.shadertoy.com/view/4sXXRN
- End -
|
评分
