对于我的一个项目，我需要可靠地检测 3D 空间中两个四面体之间的交叉点。我不需要点/线/面来知道是否存在交叉点。触摸也被认为是交叉点，但普通的三角形面不被认为是交叉点。经过一番努力以尽可能快地实现这一目标，我的解决方案变得如此可怕：
让有四面体
v0,v1每个四面体有 4 个三角形
t[4]，每个三角形有 3 个点p0,p1,p2和法向量n。计算两个四面体所有 4 个面的平面
所以平面上的任何点
p都由方程给出dot(p,n) + d = 0n飞机的法线在哪里。众所周知，这归结为计算dD0[i] = -dot(v0.t[i].p0,v0.t[i].n) D1[i] = -dot(v1.t[i].p0,v1.t[i].n) i = { 0,1,2,3 }对于每个四面体的每个三角形
测试 v0,v1 之间三角形与三角形交点的任意组合
所以只需在所有 16 种组合之间循环并使用三角形与三角形相交。
三角形v0.t[i]与三角形的v1.t[j]交点归结为：
计算平面之间的交点
这显然是光线（对于非平行平面），所以平面法线的简单叉积将给出光线方向
dir = cross(v0.t[i].n,v1.t[j].n)现在只需找到属于两个平面的交点。直接从法线的叉积利用行列式计算，光线计算如下：
// determinants det=vector_len2(dir); d0=D0[i]/det; d1=D1[j]/det; // position pos = d0*cross(dir,v1.t[j].n) + d1*cross(v0.t[i].n,dir);有关更多信息，请参阅：
编译每个三角形的三角形射线交点的有符号距离间隔
所以简单地计算射线和三角形的每条边线之间的交点，记住最小和最大距离
pos。我们不需要实际点，只需要pos线/射线相交返回的参数的标量距离。检查两个三角形的范围是否重叠
如果重叠而不是
v0,v1相交...如果所有 16 个测试都没有发生重叠，v0,v1则不相交。
如您所见，需要计算很多东西。我的线性代数和矢量数学知识仅限于我使用的东西，所以很有可能有更好的方法。我尝试了很多方法来缓解这个问题，但没有任何运气（比如使用 bbox、bsphere、使用更简单的测试，利用光线和三角形边缘都在同一平面上等），但结果要么更慢，甚至错误（不算数）边缘情况正确）。
这是我实际的C++实现：
//---------------------------------------------------------------------------
bool tetrahedrons::intersect_lin_ray(double *a0,double *a1,double *b0,double *db,double &tb)
{
int i0,i1;
double da[3],ta,q;
vector_sub(da,a1,a0); ta=0.0; tb=0.0; i0=0; i1=1;
if (fabs(da[i0])+fabs(db[i0])<=_zero) i0=2;
else if (fabs(da[i1])+fabs(db[i1])<=_zero) i1=2;
q=(da[i0]*db[i1])-(db[i0]*da[i1]);
if (fabs(q)<=_zero) return 0; // no intersection
// intersection ta,tb parameters
ta=divide(db[i0]*(a0[i1]-b0[i1])+db[i1]*(b0[i0]-a0[i0]),q);
tb=divide(da[i0]*(a0[i1]-b0[i1])+da[i1]*(b0[i0]-a0[i0]),q);
if ((ta<0.0)||(ta>1.0)) return 0; // inside line check
return 1;
}
//---------------------------------------------------------------------------
bool tetrahedrons::intersect_vol_vol(_vol4 &v0,_vol4 &v1) // tetrahedron v0 intersect tetrahedron v1 ?
{
int i,j,_ti,_tj;
_fac3 *f0,*f1;
double pos[3],dir[3],p[3],det,D0[4],D1[4],d0,d1,t,ti0,ti1,tj0,tj1;
// planes offset: dot(p,v0.t[i].n)+D0[i] = 0 , dot(p,v1.t[j].n)+D1[j] = 0
for (i=0;i<4;i++)
{
D0[i]=-vector_mul(pnt.pnt.dat+fac.dat[v0.t[i]].p0,fac.dat[v0.t[i]].n);
D1[i]=-vector_mul(pnt.pnt.dat+fac.dat[v1.t[i]].p0,fac.dat[v1.t[i]].n);
}
// plane plane intersection -> ray
for (i=0;i<4;i++)
for (j=0;j<4;j++)
{
f0=fac.dat+v0.t[i];
f1=fac.dat+v1.t[j];
// no common vertex
if ((f0->p0==f1->p0)||(f0->p0==f1->p1)||(f0->p0==f1->p2)) continue;
if ((f0->p1==f1->p0)||(f0->p1==f1->p1)||(f0->p1==f1->p2)) continue;
if ((f0->p2==f1->p0)||(f0->p2==f1->p1)||(f0->p2==f1->p2)) continue;
// direction
vector_mul(dir,f0->n,f1->n);
det=vector_len2(dir);
if (fabs(det)<=_zero) continue; // parallel planes?
d0=D0[i]/det;
d1=D1[j]/det;
// position
vector_mul(p,dir,f1->n); vector_mul(pos,p,d0);
vector_mul(p,f0->n,dir); vector_mul(p,p,d1);
vector_add(pos,pos,p);
// compute intersection edge points
_ti=1; _tj=1;
if (intersect_lin_ray(pnt.pnt.dat+f0->p0,pnt.pnt.dat+f0->p1,pos,dir,t)){ if (_ti) { _ti=0; ti0=t; ti1=t; } if (ti0>t) ti0=t; if (ti1<t) ti1=t; }
if (intersect_lin_ray(pnt.pnt.dat+f0->p1,pnt.pnt.dat+f0->p2,pos,dir,t)){ if (_ti) { _ti=0; ti0=t; ti1=t; } if (ti0>t) ti0=t; if (ti1<t) ti1=t; }
if (intersect_lin_ray(pnt.pnt.dat+f0->p2,pnt.pnt.dat+f0->p0,pos,dir,t)){ if (_ti) { _ti=0; ti0=t; ti1=t; } if (ti0>t) ti0=t; if (ti1<t) ti1=t; }
if (intersect_lin_ray(pnt.pnt.dat+f1->p0,pnt.pnt.dat+f1->p1,pos,dir,t)){ if (_tj) { _tj=0; tj0=t; tj1=t; } if (tj0>t) tj0=t; if (tj1<t) tj1=t; }
if (intersect_lin_ray(pnt.pnt.dat+f1->p1,pnt.pnt.dat+f1->p2,pos,dir,t)){ if (_tj) { _tj=0; tj0=t; tj1=t; } if (tj0>t) tj0=t; if (tj1<t) tj1=t; }
if (intersect_lin_ray(pnt.pnt.dat+f1->p2,pnt.pnt.dat+f1->p0,pos,dir,t)){ if (_tj) { _tj=0; tj0=t; tj1=t; } if (tj0>t) tj0=t; if (tj1<t) tj1=t; }
if ((_ti)||(_tj)) continue;
if ((ti0>=tj0)&&(ti0<=tj1)) return 1;
if ((ti1>=tj0)&&(ti1<=tj1)) return 1;
if ((tj0>=ti0)&&(tj0<=ti1)) return 1;
if ((tj1>=ti0)&&(tj1<=ti1)) return 1;
}
return 0;
};
//---------------------------------------------------------------------------
它是一个更大的计划的一部分。这_zero只是基于最小细节大小的零阈值。_fac3是三角形，_vol4是四面体。pnt.pnt.dat[]点和三角形都从fac.dat[]动态列表中索引。我知道这很奇怪，但它背后有很多事情要做（比如空间细分到片段等等，以加速它用于的过程）。
是和产品（这取决于它vector_mul(a,b,c)是否是向量）。a=cross(b,c)a=dot(b,c)c
我宁愿避免每个三角形/四面体的任何预先计算的值，因为即使现在这些类已经拥有相当多的信息（如父级、使用计数等）。而且由于我绑定到 Win32，因此内存仅限于左右1.2 GB，因此任何额外的东西都会限制可用网格的最大大小。
所以我正在寻找的是这些中的任何一个：
- 如果可能的话，一些数学或编码技巧来加速当前的方法
- 不同的更快的方法
我绑定到BDS2006 Win32 C++，宁愿避免使用第 3 方库。
[Edit1] 样本数据
这是四面体点云作为测试的样本数据：
double pnt[192]= // pnt.pnt.dat[pnt.n*3] = { x,y,z, ... }
{
-0.227,0.108,-0.386,
-0.227,0.153,-0.386,
0.227,0.108,-0.386,
0.227,0.153,-0.386,
0.227,0.108,-0.431,
0.227,0.153,-0.431,
-0.227,0.108,-0.431,
-0.227,0.153,-0.431,
-0.227,0.108,0.429,
-0.227,0.153,0.429,
0.227,0.108,0.429,
0.227,0.153,0.429,
0.227,0.108,0.384,
0.227,0.153,0.384,
-0.227,0.108,0.384,
-0.227,0.153,0.384,
-0.023,0.108,0.409,
-0.023,0.153,0.409,
0.023,0.108,0.409,
0.023,0.153,0.409,
0.023,0.108,-0.409,
0.023,0.153,-0.409,
-0.023,0.108,-0.409,
-0.023,0.153,-0.409,
-0.318,0.210,0.500,
-0.318,0.233,0.500,
0.318,0.210,0.500,
0.318,0.233,0.500,
0.318,0.210,-0.500,
0.318,0.233,-0.500,
-0.318,0.210,-0.500,
-0.318,0.233,-0.500,
-0.273,-0.233,0.432,
-0.273,0.222,0.432,
-0.227,-0.233,0.432,
-0.227,0.222,0.432,
-0.227,-0.233,0.386,
-0.227,0.222,0.386,
-0.273,-0.233,0.386,
-0.273,0.222,0.386,
0.227,-0.233,0.432,
0.227,0.222,0.432,
0.273,-0.233,0.432,
0.273,0.222,0.432,
0.273,-0.233,0.386,
0.273,0.222,0.386,
0.227,-0.233,0.386,
0.227,0.222,0.386,
-0.273,-0.233,-0.386,
-0.273,0.222,-0.386,
-0.227,-0.233,-0.386,
-0.227,0.222,-0.386,
-0.227,-0.233,-0.432,
-0.227,0.222,-0.432,
-0.273,-0.233,-0.432,
-0.273,0.222,-0.432,
0.227,-0.233,-0.386,
0.227,0.222,-0.386,
0.273,-0.233,-0.386,
0.273,0.222,-0.386,
0.273,-0.233,-0.432,
0.273,0.222,-0.432,
0.227,-0.233,-0.432,
0.227,0.222,-0.432,
};
struct _fac3 { int p0,p1,p2; double n[3]; };
_fac3 fac[140]= // fac.dat[fac.num] = { p0,p1,p2,n(x,y,z), ... }
{
78, 84, 96, 0.600,-0.800,-0.000,
72, 84, 96, -0.844,-0.003,-0.537,
72, 78, 84, -0.000,1.000,-0.000,
72, 78, 96, -0.000,-0.152,0.988,
6, 84, 96, -0.859,0.336,-0.385,
6, 78, 96, 0.597,-0.801,0.031,
6, 78, 84, 0.746,-0.666,0.000,
6, 72, 96, -0.852,-0.006,-0.523,
6, 72, 84, -0.834,0.151,-0.530,
78, 84,147, 0.020,1.000,-0.000,
72, 84,147, -0.023,-1.000,-0.015,
72, 78,147, -0.000,1.000,0.014,
78, 96,186, 0.546,-0.776,0.316,
6, 96,186, -0.864,0.067,-0.500,
6, 78,186, 0.995,0.014,-0.104,
78, 84,186, 0.980,-0.201,0.000,
6, 84,186, -0.812,0.078,-0.578,
72, 96,186, -0.865,-0.011,-0.501,
6, 72,186, -0.846,0.071,-0.529,
6, 84,147, -0.153,-0.672,-0.724,
6, 72,147, -0.222,-0.975,-0.024,
84,135,147, 0.018,1.000,-0.013,
78,135,147, -0.311,0.924,0.220,
78, 84,135, 0.258,0.966,-0.000,
72,135,147, -0.018,1.000,0.013,
72, 78,135, -0.000,0.995,0.105,
96,132,186, -0.000,-1.000,-0.000,
78,132,186, 0.995,-0.087,-0.056,
78, 96,132, 0.081,-0.256,0.963,
84,132,186, 0.976,-0.209,-0.055,
78, 84,132, 0.995,-0.101,0.000,
84,147,186, -0.190,-0.111,-0.975,
6,147,186, -0.030,-0.134,0.991,
0, 96,186, -0.587,-0.735,-0.339,
0, 72,186, 0.598,0.801,-0.031,
0, 72, 96, -0.992,-0.087,-0.092,
72,147,186, -0.675,-0.737,-0.044,
135,147,189, 0.000,1.000,-0.000,
84,147,189, -0.018,0.980,-0.197,
84,135,189, 0.126,0.992,-0.007,
81, 84,135, -0.183,0.983,-0.023,
78, 81,135, -0.930,-0.000,0.367,
78, 81, 84, 1.000,-0.000,0.000,
105,135,147, -0.000,1.000,0.000,
72,105,147, -0.126,0.992,0.007,
72,105,135, 0.018,0.980,0.197,
72, 81,135, -0.036,0.996,-0.082,
72, 78, 81, -0.000,-0.000,1.000,
96,120,132, -0.000,-1.000,-0.000,
78,120,132, 0.685,-0.246,0.685,
78, 96,120, -0.000,-0.152,0.988,
132,180,186, -0.000,-1.000,0.000,
84,180,186, 0.000,-0.152,-0.988,
84,132,180, 0.995,-0.101,-0.000,
147,150,186, 0.101,0.010,0.995,
84,150,186, -0.100,-0.131,-0.986,
84,147,150, -0.190,-0.019,-0.982,
96,114,186, 0.000,-1.000,0.000,
0,114,186, -0.584,-0.729,-0.357,
0, 96,114, -0.991,0.134,0.000,
0,147,186, -0.144,-0.058,-0.988,
0, 72,147, -0.926,-0.374,-0.052,
72, 96,114, -0.995,-0.101,0.000,
0, 72,114, -0.993,-0.077,-0.093,
75,147,189, -0.001,1.000,-0.012,
75,135,189, 0.018,1.000,-0.001,
75,135,147, -0.016,-1.000,0.012,
147,159,189, -0.000,1.000,-0.000,
84,159,189, -0.000,0.985,-0.174,
84,147,159, -0.025,-0.999,-0.025,
81,135,189, -0.274,0.962,0.015,
81, 84,189, 0.114,0.993,-0.023,
75,105,147, -0.115,-0.993,0.006,
75,105,135, 0.017,-0.983,0.181,
72, 75,147, -0.999,-0.000,-0.051,
72, 75,105, 0.599,-0.000,0.801,
81,105,135, -0.009,0.996,-0.093,
72, 81,105, -0.036,0.991,0.127,
120,126,132, -0.000,-1.000,-0.000,
78,126,132, 0.995,-0.101,-0.000,
78,120,126, -0.000,-0.152,0.988,
0,150,186, 0.101,-0.000,0.995,
0,147,150, -0.000,-0.000,1.000,
144,150,186, 0.000,-1.000,0.000,
84,144,186, -0.091,-0.133,-0.987,
84,144,150, -0.000,0.249,0.968,
147,150,159, -0.705,-0.071,-0.705,
84,150,159, -0.125,-0.100,-0.987,
114,150,186, 0.000,-1.000,0.000,
0,114,150, -0.998,-0.000,-0.059,
72,114,147, -0.995,-0.088,-0.052,
0,114,147, -0.906,-0.365,-0.215,
93,147,189, -0.009,-0.996,-0.093,
75, 93,189, 0.020,1.000,0.000,
75, 93,147, -0.237,-0.971,-0.000,
75, 81,189, -0.000,1.000,-0.012,
75, 81,135, -0.000,-0.995,0.096,
93,159,189, -0.000,-0.987,-0.160,
93,147,159, -0.069,-0.995,-0.069,
84, 93,189, 0.036,0.991,-0.127,
84, 93,159, -0.036,-0.993,-0.113,
84, 87,189, -0.599,-0.000,-0.801,
81, 87,189, -0.120,0.993,-0.000,
81, 84, 87, 1.000,0.000,0.000,
75, 81,105, -0.000,-0.987,0.160,
72, 93,147, -0.183,-0.983,-0.023,
72, 75, 93, -1.000,0.000,-0.000,
72, 75, 81, 0.000,-0.000,1.000,
114,147,150, -0.993,-0.100,-0.059,
144,162,186, 0.000,-1.000,0.000,
84,162,186, -0.000,-0.152,-0.988,
84,144,162, -0.600,0.800,0.000,
144,150,159, 0.000,0.101,0.995,
84,144,159, -0.125,-0.087,-0.988,
144,147,159, -0.707,0.000,-0.707,
144,147,150, -0.000,0.000,1.000,
93,114,147, 0.732,-0.587,-0.346,
72, 93,114, -0.995,-0.100,-0.002,
81, 93,189, 0.022,1.000,-0.014,
75, 81, 93, -0.000,1.000,0.000,
93,144,159, 0.582,-0.140,-0.801,
93,144,147, -0.930,0.000,0.367,
87, 93,189, -0.000,0.987,0.160,
84, 87, 93, -0.000,0.000,-1.000,
84, 93,144, -0.009,-0.238,-0.971,
81, 87, 93, -0.000,1.000,0.000,
114,144,150, -0.000,-1.000,-0.000,
114,144,147, -1.000,0.000,-0.000,
93,144,162, -0.995,-0.096,0.000,
84, 93,162, -0.005,-0.145,-0.989,
93,114,144, -0.995,-0.096,0.000,
72,114,144, -0.995,-0.101,-0.000,
72, 93,144, -0.995,-0.097,-0.002,
90,144,162, -0.995,-0.101,0.000,
90, 93,162, 0.834,0.000,-0.552,
90, 93,144, -0.930,0.000,0.367,
84, 90,162, 0.000,-0.152,-0.988,
84, 90, 93, 0.000,0.000,-1.000,
72, 90,144, -0.995,-0.101,-0.000,
72, 90, 93, -1.000,0.000,-0.000,
};
struct _vol4 { int p0,p1,p2,p3,t[4]; double s[4]; };
_vol4 vol[62]= // vol.dat[vol.num] = { p0,p1,p2,p3,t[0],t[1],t[2],t[3],s[0],s[1],s[2],s[3], ... }
{
72, 78, 96, 84, 0, 1, 2, 3, 1,1,1,1,
78, 84, 96, 6, 4, 5, 6, 0, 1,1,1,-1,
72, 84, 96, 6, 4, 7, 8, 1, -1,1,1,-1,
72, 78, 84,147, 9, 10, 11, 2, 1,1,1,-1,
6, 78, 96,186, 12, 13, 14, 5, 1,1,1,-1,
6, 78, 84,186, 15, 16, 14, 6, 1,1,-1,-1,
6, 72, 96,186, 17, 13, 18, 7, 1,-1,1,-1,
6, 72, 84,147, 10, 19, 20, 8, -1,1,1,-1,
78, 84,147,135, 21, 22, 23, 9, 1,1,1,-1,
72, 78,147,135, 22, 24, 25, 11, -1,1,1,-1,
78, 96,186,132, 26, 27, 28, 12, 1,1,1,-1,
78, 84,186,132, 29, 27, 30, 15, 1,-1,1,-1,
6, 84,186,147, 31, 32, 19, 16, 1,1,-1,-1,
72, 96,186, 0, 33, 34, 35, 17, 1,1,1,-1,
6, 72,186,147, 36, 32, 20, 18, 1,-1,-1,-1,
84,135,147,189, 37, 38, 39, 21, 1,1,1,-1,
78, 84,135, 81, 40, 41, 42, 23, 1,1,1,-1,
72,135,147,105, 43, 44, 45, 24, 1,1,1,-1,
72, 78,135, 81, 41, 46, 47, 25, -1,1,1,-1,
78, 96,132,120, 48, 49, 50, 28, 1,1,1,-1,
84,132,186,180, 51, 52, 53, 29, 1,1,1,-1,
84,147,186,150, 54, 55, 56, 31, 1,1,1,-1,
0, 96,186,114, 57, 58, 59, 33, 1,1,1,-1,
0, 72,186,147, 36, 60, 61, 34, -1,1,1,-1,
0, 72, 96,114, 62, 59, 63, 35, 1,-1,1,-1,
135,147,189, 75, 64, 65, 66, 37, 1,1,1,-1,
84,147,189,159, 67, 68, 69, 38, 1,1,1,-1,
84,135,189, 81, 70, 71, 40, 39, 1,1,-1,-1,
105,135,147, 75, 66, 72, 73, 43, -1,1,1,-1,
72,105,147, 75, 72, 74, 75, 44, -1,1,1,-1,
72,105,135, 81, 76, 46, 77, 45, 1,-1,1,-1,
78,120,132,126, 78, 79, 80, 49, 1,1,1,-1,
147,150,186, 0, 81, 60, 82, 54, 1,-1,1,-1,
84,150,186,144, 83, 84, 85, 55, 1,1,1,-1,
84,147,150,159, 86, 87, 69, 56, 1,1,-1,-1,
0,114,186,150, 88, 81, 89, 58, 1,-1,1,-1,
0, 72,147,114, 90, 91, 63, 61, 1,1,-1,-1,
75,147,189, 93, 92, 93, 94, 64, 1,1,1,-1,
75,135,189, 81, 70, 95, 96, 65, -1,1,1,-1,
147,159,189, 93, 97, 92, 98, 67, 1,-1,1,-1,
84,159,189, 93, 97, 99,100, 68, -1,1,1,-1,
81, 84,189, 87, 101,102,103, 71, 1,1,1,-1,
75,105,135, 81, 76, 96,104, 73, -1,-1,1,-1,
72, 75,147, 93, 94,105,106, 74, -1,1,1,-1,
72, 75,105, 81, 104, 77,107, 75, -1,-1,1,-1,
0,147,150,114, 108, 89, 91, 82, 1,-1,-1,-1,
84,144,186,162, 109,110,111, 84, 1,1,1,-1,
84,144,150,159, 112, 87,113, 85, 1,-1,1,-1,
147,150,159,144, 112,114,115, 86, -1,1,1,-1,
72,114,147, 93, 116,105,117, 90, 1,-1,1,-1,
75, 93,189, 81, 118, 95,119, 93, 1,-1,1,-1,
93,147,159,144, 114,120,121, 98, -1,1,1,-1,
84, 93,189, 87, 122,101,123, 99, 1,-1,1,-1,
84, 93,159,144, 120,113,124,100, -1,-1,1,-1,
81, 87,189, 93, 122,118,125,102, -1,-1,1,-1,
114,147,150,144, 115,126,127,108, -1,1,1,-1,
84,144,162, 93, 128,129,124,111, 1,1,-1,-1,
93,114,147,144, 127,121,130,116, -1,-1,1,-1,
72, 93,114,144, 130,131,132,117, -1,1,1,-1,
93,144,162, 90, 133,134,135,128, 1,1,1,-1,
84, 93,162, 90, 134,136,137,129, -1,1,1,-1,
72, 93,144, 90, 135,138,139,132, -1,1,1,-1,
};
来自is normal的p?点索引是正常的符号（如果三角形是共享的，所以法线指向相同的方式）并且是来自的三角形的索引。这里有一个示例测试：0,3,6,9...pntnst[4]0,1,2,3,...fac
bool tetrahedrons::vols_intersect() // test if vol[] intersects each other
{
int i,j;
for (i=0;i<vol.num;i++)
for (j=i+1;j<vol.num;j++,dbg_cnt++)
if (intersect_vol_vol(vol.dat[i],vol.dat[j]))
{
linc=0x800000FF;
if (intersect_vol_vol(vol.dat[j],vol.dat[i])) linc=0x8000FFFF;
lin_add_vol(vol.dat[i]);
lin_add_vol(vol.dat[j]);
return 1;
}
return 0;
}
dbg_cnt交叉测试的计数器在哪里。对于这个网格，我得到了这个结果：
tests | time
------+-------------
18910 | 190-215 [ms]
我调用了vols_intersect10 次测试以使测量时间足够长。在这个数据集中放置的四面体都不会相交（导致最高时间）。在导致此网格的实际过程（太大而无法发布）中，计数如下：
intersecting 5
non intersecting 1766
all tests 1771