有效计算视线和一组对象之间的第一个交点的最佳方法是什么? [英] What is the best approach to compute efficiently the first intersection between a viewing ray and a set of objects?

问题描述

例如:

一种有效计算视线与一组三个对象之间的第一个交点的方法:一个球体、一个圆锥体和一个圆柱体(其他 3D 基元).

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).

推荐答案

您正在寻找的是空间分区方案.处理这个问题有很多选择，并且在这方面也进行了大量研究.Christer Ericsson 的实时碰撞检测是一本很好的读物.

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.

其他感兴趣的分区方案是不同的树结构，例如kd-，Oct- 和 BSP 树.您甚至可以考虑将树与网格结合使用.

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. :)

这篇关于有效计算视线和一组对象之间的第一个交点的最佳方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！