快速三角形搜索AABB-三角形交叉测试 [英] Quick triangle search for AABB-triangle intersection test

问题描述

我给了数以千计的三角形（三维顶点和不同大小）和一个特定的边界框大小...除了对每个三角形进行AABB-三角形交叉测试（当涉及到数百万个三角形时，它非常慢三角），有没有更快的方法来实现这一点，因为最小化交叉测试的数量...？真的需要你的帮助，因为我只是遗漏了这个拼图来解决我的项目...我已经完成了AABB-三角交叉测试的完整代码....只是我想尽量减少测试的数量完成...我没有使用VTK，OpenGL，TetGen，CGAL或任何其他复杂的库....只是基本的C ++软件，它是CodeBlocks。

解决方案

< blockquote>我猜不是。您必须分别测试所有三角形，除了三角形有一些共同点，这样可以通过同时对多个三角形执行其中一个步骤来简化相交测试。



关于你的意见：......是否可以选择最接近边界框的三角形并执行交叉测试？。你怎么定义最近的？如果将其定义为：三角形中心与边界框中心之间的距离：否，这对您没有帮助。您可以轻松地构造两个三角形，并使较近的三角形不相交，而另一个三角形则很好地相交。如果您将距离定义为：三角形曲面的任何点与边界框内的任何点的最近距离，那么您基本上执行与相交测试相同的测试。



所以，简而言之，不，没有捷径。但是你可以研究交叉口测试的速度，你没有在这里展示过。如果您正在处理数百万个三角形，其中大多数三角形在边界框的范围之外，则应该对结构进行测试，以便在最短的时间内处理这些微不足道的情况。例如，您可以先放置沿坐标网格对齐的测试，以便在前几个测试步骤中出现非重叠。

I'm given thousands of triangles (3D vertices & of different sizes) and a particular bounding box size...besides doing AABB-triangle intersection test for "each" triangle (which is very slow when it comes to millions of triangles), is there any quicker way to accomplish this as in minimising the number of intersection test to be done...? Really need your help for this as I just left out this piece of puzzle to solve my project...I've the complete code for the AABB-triangle intersection test....just that I want to minimise the number of test to be done...I'm not using VTK, OpenGL, TetGen, CGAL, or any other complex libraries....just basic C++ software which is CodeBlocks.

解决方案

I guess not. You will have to test all your triangles separately, except you triangles have something in common which would allow to simplify the intersection test by performing one of its steps for multiple triangles at the same time.

As to your comments: "... is [it] possible to select the nearest triangle to the bounding box and perform the intersection test?". How would you define nearest? If you define it as: distance between the triangles center and the bounding box's center: No, that doesn't help you. You can easily construct two triangles and have the nearer one not intersect and the further one do well intersect. If you defined the distance as: The closest distance of any point of the triangle surface to any point inside the bounding box, then you are basically performing the same test as for your intersection test.

So, in a nutshell, no, there is no shortcut. But you could work on the speed of your intersection test, which you haven't shown here. If you are dealing with millions of triangles, most of which fall wide outside the range of the bounding box, your intersection test should be structured, such that these trivial cases are handled in minimum time. For example, you could place the test that are aligned along the coordinate grid up first, so that non-overlaps appear within the first couple of test steps.

这篇关于快速三角形搜索AABB-三角形交叉测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！