有效计算视线和一组对象之间的第一个交点的最佳方法是什么？
例如：
一种有效计算视线与一组三个对象（一个球体、一个圆锥体和一个圆柱体（其他 3D 图元））之间的第一个交点的方法。
For instance:
An approach to compute efficiently the first intersection between a viewing ray and a set of three objects: one sphere, one cone and one cylinder (other 3D primitives).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您正在寻找的是空间分区方案。 处理这个问题有很多选择，并且在这个领域也进行了大量的研究。 Christer Ericsson 的实时碰撞检测是一本不错的读物。
该书中介绍的一种简单方法是定义一个网格，将所有对象分配给它相交的所有单元格，然后沿着与该线相交的网格单元格从前到后行走，与与该网格单元格关联的每个对象相交。 请记住，一个对象可能与更多网格单元相关联，因此计算出的交点实际上可能不在当前单元中，而是稍后在当前单元中。
下一个问题是如何定义该网格。 不幸的是，没有一个好的答案，您需要考虑哪种方法最适合您的场景。
其他感兴趣的分区方案是不同的树结构，例如 kd-、Oct- 和 BSP 树。 您甚至可以考虑将树与网格结合使用。
编辑
正如所指出的，如果你的集合实际上是这三个对象，那么你最好只将每个对象相交，然后选择最早的一个。 如果您正在寻找射线球体、射线圆柱体等相交测试，这些并不难，快速谷歌应该可以提供您可能需要的所有数学知识。 :)
What you're looking for is a spatial partitioning scheme. There are a lot of options for dealing with this, and lots of research spent in this area as well. A good read would be Christer Ericsson's Real-Time Collision Detection.
One easy approach covered in that book would be to define a grid, assign all objects to all cells it intersects, and walk along the grid cells intersecting the line, front to back, intersecting with each object associated with that grid cell. Keep in mind that an object might be associated with more grid-cells, so the intersection point computed might actually not be in the current cell, but actually later on.
The next question would be how you define that grid. Unfortunately, there's no one good answer, and you need to consider what approach might fit your scenario best.
Other partitioning schemes of interest are different tree structures, such as kd-, Oct- and BSP-trees. You could even consider using trees combined with a grid.
EDIT
As pointed out, if your set is actually these three objects, you're definately better of just intersecting each one, and just pick the earliest one. If you're looking for ray-sphere, ray-cylinder, etc, intersection tests, these are not really hard and a quick google should supply all the math you might possibly need. :)
“计算效率”取决于集合有多大。
对于一个简单的三个集合，只需依次测试它们中的每一个，确实不值得尝试优化。
对于较大的集合，请查看划分空间的数据结构（例如 KD 树）。 整个章节（实际上是整本书）都致力于解决这个问题。 我最喜欢的参考书是光线追踪简介（ed. Andrew. S .Glassner）
或者，如果我误读了你的问题，而你实际上是在要求特定类型对象的射线对象相交的算法，请参阅同一本书！
"computationally efficient" depends on how large the set is.
For a trivial set of three, just test each of them in turn, it's really not worth trying to optimise.
For larger sets, look at data structures which divide space (e.g. KD-Trees). Whole chapters (and indeed whole books) are dedicated to this problem. My favourite reference book is An Introduction to Ray Tracing (ed. Andrew. S. Glassner)
Alternatively, if I've misread your question and you're actually asking for algorithms for ray-object intersections for specific types of object, see the same book!
嗯，这取决于你真正想做什么。 如果您想生成一个对简单场景中几乎每个像素都正确的解决方案，一种非常快速的方法是通过使用唯一的标识预渲染所有对象来预先计算每个像素的“前面是什么”使用扫描转换（也称为 z 缓冲区）将颜色转换为背景项缓冲区。 这有时称为项目缓冲区。
使用该预计算，您就可以知道您将射入场景的几乎所有光线的可见内容。 因此，光线与环境相交的问题大大简化：每条光线都会击中一个特定的物体。
当我很多年前做这件事时，我正在制作实时光线追踪无可否认的简单场景的图像。 我已经有一段时间没有重新审视该代码了，但我怀疑使用现代编译器和图形硬件，性能会比我当时看到的要好几个数量级。
PS：我第一次读到 item buffer 的想法是在 90 年代初进行文献检索时。 我最初发现（我相信）70 年代末的一篇 ACM 论文中提到了它。 遗憾的是，我没有可用的源参考，但简而言之，这是一个非常古老的想法，并且在扫描转换硬件上非常有效。
Well, it depends on what you're really trying to do. If you'd like to produce a solution that is correct for almost every pixel in a simple scene, an extremely quick method is to pre-calculate "what's in front" for each pixel by pre-rendering all of the objects with a unique identifying color into a background item buffer using scan conversion (aka the z-buffer). This is sometimes referred to as an item buffer.
Using that pre-computation, you then know what will be visible for almost all rays that you'll be shooting into the scene. As a result, your ray-environment intersection problem is greatly simplified: each ray hits one specific object.
When I was doing this many years ago, I was producing real-time raytraced images of admittedly simple scenes. I haven't revisited that code in quite a while but I suspect that with modern compilers and graphics hardware, performance would be orders of magnitude better than I was seeing then.
PS: I first read about the item buffer idea when I was doing my literature search in the early 90s. I originally found it mentioned in (I believe) an ACM paper from the late 70s. Sadly, I don't have the source reference available but, in short, it's a very old idea and one that works really well on scan conversion hardware.
我假设您有一条射线 d = (dx,dy,dz)，从 o = (ox,oy,oz) 开始，您正在找到参数 t，使得交点 p = o+d*t。 （就像这个页面一样，它描述了光线平面相交P2-P1 代表 d，P1 代表 o，u 代表 t）
我要问的第一个问题是“这些对象相交吗”？
如果没有，那么您可以稍微作弊并按顺序检查光线碰撞。 由于您有三个对象，每帧可能会或可能不会移动，因此需要预先计算它们与相机的距离（例如，距它们的中心点）。 按与相机的距离从小到大依次测试每个对象。 尽管空白空间现在是渲染中最昂贵的部分，但这比仅对所有三个进行测试并取最小值更有效。 如果您的图像是高分辨率的，那么这尤其有效，因为您可以通过像素数量分摊成本。
否则，对所有三种方法进行测试并取最小值...
在其他情况下，您可能希望混合使用这两种方法。 如果您可以按顺序测试两个物体，那么就这样做（例如，一个球体和一个立方体沿着圆柱形隧道移动），但测试第三个物体并取最小值来找到最终的物体。
I assume you have a ray d = (dx,dy,dz), starting at o = (ox,oy,oz) and you are finding the parameter t such that the point of intersection p = o+d*t. (Like this page, which describes ray-plane intersection using P2-P1 for d, P1 for o and u for t)
The first question I would ask is "Do these objects intersect"?
If not then you can cheat a little and check for ray collisions in order. Since you have three objects that may or may not move per frame it pays to pre-calculate their distance from the camera (e.g. from their centre points). Test against each object in turn, by distance from the camera, from smallest to largest. Although the empty space is the most expensive part of the render now, this is more effective than just testing against all three and taking a minimum value. If your image is high res then this is especially efficient since you amortise the cost across the number of pixels.
Otherwise, test against all three and take a minimum value...
In other situations you may want to make a hybrid of the two methods. If you can test two of the objects in order then do so (e.g. a sphere and a cube moving down a cylindrical tunnel), but test the third and take a minimum value to find the final object.