我有一个视线问题我需要通过访问两个（非网格对齐）点之间的3D体素空间中的所有可能单元来解决。
我考虑过使用3D Bresenham算法，但它会跳过一些细胞。
一个天真的实现可能是以比体素网格更高的分辨率检查沿线的点，但我希望有一个更智能的解决方案。
有人有任何线索吗？
想出这个，或者看看：http://jsfiddle.net/wivlaro/mkaWf/6/
function visitAll(gx0, gy0, gz0, gx1, gy1, gz1, visitor) {
var gx0idx = Math.floor(gx0);
var gy0idx = Math.floor(gy0);
var gz0idx = Math.floor(gz0);
var gx1idx = Math.floor(gx1);
var gy1idx = Math.floor(gy1);
var gz1idx = Math.floor(gz1);
var sx = gx1idx > gx0idx ? 1 : gx1idx < gx0idx ? -1 : 0;
var sy = gy1idx > gy0idx ? 1 : gy1idx < gy0idx ? -1 : 0;
var sz = gz1idx > gz0idx ? 1 : gz1idx < gz0idx ? -1 : 0;
var gx = gx0idx;
var gy = gy0idx;
var gz = gz0idx;
//Planes for each axis that we will next cross
var gxp = gx0idx + (gx1idx > gx0idx ? 1 : 0);
var gyp = gy0idx + (gy1idx > gy0idx ? 1 : 0);
var gzp = gz0idx + (gz1idx > gz0idx ? 1 : 0);
//Only used for multiplying up the error margins
var vx = gx1 === gx0 ? 1 : gx1 - gx0;
var vy = gy1 === gy0 ? 1 : gy1 - gy0;
var vz = gz1 === gz0 ? 1 : gz1 - gz0;
//Error is normalized to vx * vy * vz so we only have to multiply up
var vxvy = vx * vy;
var vxvz = vx * vz;
var vyvz = vy * vz;
//Error from the next plane accumulators, scaled up by vx*vy*vz
// gx0 + vx * rx === gxp
// vx * rx === gxp - gx0
// rx === (gxp - gx0) / vx
var errx = (gxp - gx0) * vyvz;
var erry = (gyp - gy0) * vxvz;
var errz = (gzp - gz0) * vxvy;
var derrx = sx * vyvz;
var derry = sy * vxvz;
var derrz = sz * vxvy;
do {
visitor(gx, gy, gz);
if (gx === gx1idx && gy === gy1idx && gz === gz1idx) break;
//Which plane do we cross first?
var xr = Math.abs(errx);
var yr = Math.abs(erry);
var zr = Math.abs(errz);
if (sx !== 0 && (sy === 0 || xr < yr) && (sz === 0 || xr < zr)) {
gx += sx;
errx += derrx;
}
else if (sy !== 0 && (sz === 0 || yr < zr)) {
gy += sy;
erry += derry;
}
else if (sz !== 0) {
gz += sz;
errz += derrz;
}
} while (true);
}
据我所知，原始的Bresenham算法假设允许沿着对角线移动，在你的情况下，有理由不允许它。
但主要观点是相同的 - 每个体素都回答“下一步是什么？”的问题。
每个体素都有6个面孔，每个面孔通向不同的邻居。只需检查哪个体素比其他体素更接近线的中心。这是下一个体素。
注意：这假设体素沿每个轴具有相同的大小，如果不是这样，则应计算修改的距离（每个组件应除以相应轴的体素大小）
我认为3D Bresenham是要走的路，只是稍微调整一下。作为问题的第一个过程，继续作为Bresenham，但是当你要迈出一步，或者你只是采取了一步时要小心，因为这些线路可以穿过额外的细胞。
为简单起见，让我们假设z占主导地位，这意味着z每一步都会增加。 3d Bresenham的问题是：“我们什么时候在x或y增加/减少？”答案是当x中的累积误差达到.5时，或者当y中的误差发生时，或两者都有。
对于您的情况，我认为您需要有一个次要阈值，使用slopeY = deltaY/deltaZto决定该线是否即将进入相邻的单元格。如果stepZ是每个像素沿着线的z变化，那么像error > .5 - slopeY/stepZ这样的测试应该告诉你在y中获取线的两侧的细胞。类似的测试告诉你是否必须在x中获得额外的单元格。如果你必须在x和y中获得额外的单元格，那么你必须让细胞对角线到Bresenham单元格。
如果您在增量之前检测到在y中添加了一个单元格，则不会在之后添加单元格。如果您之前没有添加过y细胞，那么除非您碰巧穿过细胞角落，否则您将不得不这样做。你如何处理这取决于你的用例。
这些是我对这个问题的想法，我没有测试任何东西，但它应该有用。
这是从我的体素射线的最近端口到Cavascript到javascript的公共链接：
https://github.com/jeremykentbgross/EmpathicCivGameEngine/blob/master/engine/public/scripts/Ray2D.js
注意：端口当前在四叉树上是2D（而不是在八叉树上的3D），但仅仅因为我的2D javascript引擎注释了一个维度。它在我的3D C ++引擎（我移植它）中工作正常，所以如果取消注释Z轴线它将起作用。该文件还有很多关于数学运算方式的内联注释。
您还应该引用RayTracer2D.js（在同一目录中），它使用光线按照命中的顺序查找所有相交的对象及其交叉点。
作为参考，它所追踪的四叉树结构也在同一个文件夹中：QuadTree.js
请注意，您还可以通过限制在跟踪期间遍历到树中的深度来光线跟踪较低的LOD。
希望有所帮助。