3d 空间中的三角形三角形交点 [英] Triangle Triangle Intersection in 3d-Space
问题描述
我正在处理一些 3D 几何图形.我需要找到三角形与另一个三角形的交点.
I'm working with some 3d geometry. I need to find the intersection of triangle with another triangle.
我可以使用什么算法?
推荐答案
很多人显然依赖于一个实现(link to source code) 2006 年在以下论文 (链接到 PDF):
Many people apparently rely on an implementation (link to source code) of the method described in 2006 in the following paper (link to PDF):
Tropp、Oren、Ayellet Tal 和 Ilan Shimshoni.一个快速的三角形用于碰撞检测的三角形相交测试." 计算机动画和虚拟世界 17.5 (2006): 527-535.
Tropp, Oren, Ayellet Tal, and Ilan Shimshoni. "A fast triangle to triangle intersection test for collision detection." Computer Animation and Virtual Worlds 17.5 (2006): 527-535.
然而,该代码存在一个问题(除了采用旧的编程风格、使用非常规符号和失去基本的几何解释之外):决定性事物"不一定会使您的数学更健壮,如果以错误的方式完成.
There is however a problem with that code (except for adopting an old programming style, using unconventional notations and loosing the underlying geometrical interpretation): "determinant thing" don't necessarily make your math more robust, if done the wrong way.
我建议使用 Moeller 的方法(链接到 PDF)或查看 Delliver 的论文(链接到 PDF),在 CGAL 中实现库(链接,Triangle_3_Triangle_3_do_intersect.h").
I suggest to either use Moeller's method (link to PDF) or take a look at Delliver's paper (link to PDF), implemented in the CGAL library (link, "Triangle_3_Triangle_3_do_intersect.h").
一个例子:上面实现的交集例程告诉三角形 (p0,p1,p2) 和 (q0,q1,q2) 由以下点定义
An example: the intersection routine implemented above tells that the triangles (p0,p1,p2) and (q0,q1,q2) defined by the following points
p0 = (-21, -72, 63)
p1 = (-78, 99, 40)
p2 = (-19, -78, -83)
q0 = (96, 77, -51)
q1 = (-95, -1, -16)
q2 = (9, 5, -21)
不相交.这是三角形的图片:
are not intersecting. Here is a picture of the triangles:
这里是代码片段(附加到原始代码):
And here is the code snippet (append to original code):
#include <iostream>
inline void setPoint(double p[3], const double x, const double y, const double z)
{
p[0] = x; p[1] = y; p[2] = z;
}
inline void computeEdges(double v0[3], double v1[3], const double p0[3], const double p1[3], const double p2[3])
{
v0[0] = p1[0]-p0[0];
v0[1] = p1[1]-p0[1];
v0[2] = p1[2]-p0[2];
v1[0] = p2[0]-p0[0];
v1[1] = p2[1]-p0[1];
v1[2] = p2[2]-p0[2];
}
void main()
{
unsigned int numErrors(0), count(0);
double p0[3], p1[3], p2[3], q0[3], q1[3], q2[3];
double v0[3], v1[3], w0[3], w1[3];
bool res, answer;
int ret;
std::cout << "Testing the correctness of tr_tri_intersect3D" << std::endl;
{
// Non excluding triangles in generic positions, big determinants, intersecting
++count;
setPoint(p0, -21, -72, 63);
setPoint(p1, -78, 99, 40);
setPoint(p2, -19, -78, -83);
setPoint(q0, 96, 77, -51);
setPoint(q1, -95, -1, -16);
setPoint(q2, 9, 5, -21);
answer = true;
computeEdges(v0, v1, p0, p1, p2);
computeEdges(w0, w1, q0, q1, q2);
int ret = tr_tri_intersect3D(p0, v0, v1, q0, w0, w1);
bool res = ( ret != 0 );
if( res != answer )
{
std::cout << "# wrong answer on test " << count << "!
";
++numErrors;
}
}
}
关于算术运算数量的最后说明:由于该方法采用输入预先计算的边缘向量,因此应将 12 个 +/- 运算添加到论文的表 I.中.
A final note on the number of arithmetic operations: since the method takes in input pre-computed edge vectors, 12 +/- operations should be added to Table I. of the paper.
最后但同样重要的是:请自行验证我写的内容,如果您认为我误解了某些内容,请给我反馈!
Last but not least: please verify what I am writing on your own and give me feedback if you think that I misunderstood something!
这篇关于3d 空间中的三角形三角形交点的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!