All

Fast 3D Triangle-Box Overlap Testing

http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/tribox_tam.pdf

 
 

A fast routine for testing whether a triangle and a box are overlapping in three dimensions is presented. The test is derived using the separating axis theorem, where after the test is simplified and the code is optimized for speed. It can be used for faster collision detection and faster voxelization in interactive ray tracers. 【提出了一种快速例程,用于测试三角形和方框是否在三维空间中重叠。 根据分离轴定理做了实现,然后做了简化并且优化了代码执行速度。 它可用于交互式光线跟踪器中更快的碰撞检测和更快的体素化。】

 
 

简介:

 
 

Testing whether a triangle overlaps a box is an important routine to have in a graphics programmer’s toolbox. For example, the test can be used to voxelize triangle meshes in ray tracers, and it can be used in collision detection algorithms that are based on boxes. Gottschalk et al’s collision detection framework only used OBB/OBB tests and triangle-triangle tests. However, it has been noted that both memory and speed can be gained by not having an OBB around each triangle, and instead test a triangle against an OBB.【测试三角形是否与框重叠是图形程序员工具箱中的一个重要例程。 例如该测试可用于对光线跟踪器中的三角形网格进行体素化,并且可用于基于Box的碰撞检测算法。 Gottschalk等人的碰撞检测框架仅使用 OBB-OBB 和 triangle-triangle。 然而 ObBB-triangle 可以获得更好的存储和速度效率。】

 
 

Previously, Voorhies has presented code for testing a triangle against a unit cube centered at the origin [8]. His test tries to eliminate work by doing some simple acceptance/rejection tests early on, and then testing each triangle edge for intersection with the cube faces. Finally, he checks whether the interior of the triangle is penetrated by the cube. Green and Hatch [4] improve on the efficiency of Voorhies’ work and generalize it to handle arbitrary polygons as well. They also use fast acceptance/rejectance tests, but recast the testing of an edge against the cube into testing a point against a skewed rhombic dodecahedron, which is more robust. Finally, they test whether one diagonal of the cube intersect the polygon, which further improves the efficiency.【先前,Voorhies已经提出了针对以原点为中心的单位立方体测试三角形的代码。 他的做法是通过先进行一些简单的接受/拒绝测试来消除工作,然后测试每个三角形边缘与立方体面的交叉点,最后他检查三角形的内部是否被立方体穿透。 GreenHatch 提高了Voorhies工作的效率,并将其推广到处理任意多边形。 他们还使用快速接受/拒绝测试,但重新测试边缘对立方体的测试,以测试针对倾斜的菱形十二面体的点,这更加强大。 最后,他们测试立方体的一个对角线是否与多边形相交,这进一步提高了效率。】

 
 

 
 

 
 

Derivation and Optimization 【推倒优化】

 
 

Our test is derived from the separating axis theorem (SAT). The theorem states that two convex poly hedra, A and B, are disjoint if they can be separated along either an axis parallel to a normal of a face of either A or B, or along an axis formed from the cross product of an edge from A with and edge from B.【我们的测试原理来自分离轴定理(SAT)。 该定理指出,如果两个凸多面体AB可以沿着平行于AB面的法线的轴分开,或者沿着由A的边缘与来自B的边缘的叉积形成的轴分开,则它们是不相交的。 】

 
 

We focus on testing an axis-aligned bounding box (AABB), defined by a center c, and a vector of half lengths, h, against a triangle ∆u0u1u2. To simplify the tests, we first move the triangle so that the box is centered around the origin, i.e., vi = ui − c, i ∈ {0, 1, 2}. To test against an oriented box, we would first rotate the triangle vertices by the inverse box transform, then use the presented test. Based on SAT, we test the following 13 axes:

【我们设定 Cube 中心是 c
,边长 2h,它是轴对齐(AABB)的;三角形顶点是 u0u1u2。 】

【为了简化测试,我们首先移动三角形,使盒子以原点为中心,即 vi = ui – ci{0,1,2}。 要针对定向框进行测试,我们首先通过逆框变换旋转三角形顶点,然后使用呈现的测试。 基于SAT,我们测试以下13个轴:】

 
 

 
 

1. [3 tests] e0 = (1, 0, 0), e1 = (0, 1, 0), e2 = (0, 0, 1) (the normals of the AABB). Test the AABB against the minimal AABB around the triangle.

3次测试,AABB的法线,针对三角形周围的最小AABB测试AABB。】

 
 

2. [1 test] n, the normal of ∆. We use a fast plane/AABB overlap test [5, 6], which only tests the two diagonal vertices, whose direction is most closely aligned to the normal of the triangle.

1次测试,三角形的法线。 我们使用 fast plane/AABB 重叠测试。】

 
 

3. [9 tests] aij = ei × fj , i, j ∈ {0, 1, 2}, where f0 = v1 − v0, f1 = v2 − v1, and f2 = v0 − v2. These tests are very similar and we will only show the derivation of the case where i = 0 and j = 0 (see below).

9次测试, aij = ei×fjij{0,1,2},其中f0 = v1-v0f1 = v2-v1f2 = v0-v2。 这些测试非常相似,我们只展示i = 0j = 0的情况的推导(见下文)。】

 
 

If all tests pass, i.e., there is no separating axis, then the triangle overlaps the box. Also, as soon as a separating axis is found the the algorithm terminates and returns “no overlap”.

【如果所有测试都通过,即没有分离轴,那么三角形与盒子重叠。 此外一旦找到分离轴,算法就会终止并返回无重叠。】

 
 

Next, we derive one of the nine tests, where i = 0 and j = 0, in bullet 3 above. This means that a00 = e0 × f0 = (0, −f0z, f0y). So, now we need to project the triangle vertices onto a00 (hereafter called a):

【上面九个测试中的一个,i = 0j = 0 的时候。 也就是 a00 = e0 × f0 =0-f0zf0y)。 那么,现在我们需要将三角形顶点投影到 a00(以下称为a):】

 
 

 
 

Normally, we would have had to find min(p0, p1, p2) and max(p0, p1, p2), but fortunately p0 = p1, which simplify the computations a lot. Now we only need to find min(p0, p2) and max(p0, p2), which is significantly faster because conditional statements are expensive on modern CPUs.

【通常,我们必须找到 minp0p1p2)和 maxp0p1p2),但幸运的是p0 = p1,这大大简化了计算。 现在我们只需要找到 minp0p2)和 maxp0p2),这运算就更快。】

 
 

After the projection of the triangle onto a, we need to project the box onto a as well. We compute a “radius”, called r, of the box projected on a as

【再将三角形投影到 a 上之后,我们还需要将框投影到 a 上。 我们计算投影在 as 上的框的半径,称为 r

 
 

 
 

where the last step comes from that ax = 0 for this particular axis. Then this axis test becomes:

【最后一步来自该特定轴的 ax = 0。 然后这个轴测试成为:】

 
 

 
 

Now, if all these 13 tests pass, then the triangle overlaps the box

【现在,如果所有这13个测试通过,则三角形与框重叠】

 
 

 
 

 
 

Performance Evaluation【性能评价】

 
 

To evaluate performance, we used the same test as Voorhies [8], i.e., we randomly select the triangle vertices inside a 4 × 4 × 4 cube centered around the origin and the AABB is the unit cube: from (−0.5, −0.5, −0.5) to (0.5, 0.5, 0.5). To get accurate timings we randomly selected 100, 000 triangles and tested these in a sequence 100 times. We verified that our code generated the same result as Green and Hatch [4], and compared runtimes (we did not test against Voorhies code since that was found to be incorrect [2]).

【为了评估性能,我们使用与Voorhies 相同的测试,即我们随机选择以原点为中心的4×4×4立方体内的三角形顶点,AABB是单位立方体:从(-0.5,-0.5,-0.5)至(0.5,0.5,0.5)。 为了获得准确的计时,我们随机选择了100,000个三角形,并按顺序对这些三角形进行了100次测试。 我们验证了我们的代码生成了与GreenHatch相同的结果[4],并比较了运行时(我们没有测试Voorhies代码,因为发现它是不正确的[2])。】

 
 

On a Sun Sparc Ultra 10 at 333 MHz, the presented code was 3.8 times faster on average in this test1. On a Linux PC with a 1333 MHz AMD Athlon, the speed up was found to be 2.32. Also, the best order to perform the tests on the Sun was found to be: 3, 1, and finally 2 (the most expensive). On the PC, the order did not matter significantly.【在333 MHzSun Sparc Ultra 10上,所提供的代码在此测试中平均快了3.81。 在具有1333 MHz AMD AthlonLinux PC上,速度提升为2.32。 此外,在太阳上执行测试的最佳顺序是:3,1,最后2(最昂贵)。 在PC上,订单无关紧要。】

 
 

Note that Green and Hatch’s code handles the more general case of testing a general polygon against a cube, while we only test a triangle against a cube, and hence we can expect some degradation in performance due to this.【请注意,GreenHatch的代码处理了针对多维数据集测试一般多边形的更一般情况,而我们只针对多维数据集测试三角形,因此我们可以预期由于此而导致性能下降。】

 
 

The only place, where there is a robustness issue, is when the normal of the triangle is computed; n = f0 × f1. If the triangle has an area close to zero, then the normal calculation is not robust, and our code does not solve that problem. However, in most applications thin long triangles are best avoided.【唯一存在鲁棒性问题的地方是计算三角形的法线时; n = f0×f1。 如果三角形的面积接近于零,则正常计算不稳健,并且我们的代码无法解决该问题。 但是,在大多数应用中,最好避免使用细长三角形。】

 
 

We have used the code for fast voxelization in a ray tracer, and it has been used in a 3D engine [7].【我们已经在光线跟踪器中使用了快速体素化的代码,并且它已经在3D引擎中使用[7]。】

 
 

 
 

上面讲的是三角形和立方体的实现,但是基本原理没讲清楚,就是那个定理:

https://blog.csdn.net/cgcoder/article/details/7179575

这边讲了定理,以及怎么找分割面,这里的123对应这文章的123.