在3D体素空间中的两点之间走一条线，访问所有单元格

Question

我有一个视线问题，我需要通过访问两个(非网格对齐)点之间的3D体素空间中的所有可能单元来解决。

我曾考虑使用3D Bresenham算法，但它会跳过一些单元格。

一个天真的实现可能是以比体素网格更高的分辨率检查线上的点，但我希望有一个更智能的解决方案。

有什么线索吗？

Answer 1

想出了这个，或者看看：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);
}

Answer 2

就我所记得的，原始的Bresenham算法假设沿对角线移动是允许的，在你的情况下是有意义的，不允许它。

但主要思想是一样的--对于每个体素，回答问题“下一步是什么？”

每个体素有6个面，每个面指向不同的邻居。只需检查哪个体素的中心比其他体素更靠近直线。这是下一个体素。

注意:这假设体素在每个轴上都有相同的大小，如果不是这样，你应该计算修改后的距离(每个组件应该除以相应轴上的体素大小)

Answer 3

我认为3d Bresenham是未来的发展方向，只是做了一些调整。作为解决问题的第一步，作为Bresenham继续，但是当您要迈出一步或刚刚迈出一步时要怀疑，因为这些都是行可能通过额外单元格的地方。

为了简单起见，让我们假设z占主导地位，这意味着z每一步都会递增。3DBresenham的问题是：“我们什么时候在x或y中增加/减少？”答案是当x中的累积误差达到.5时，或者当y中的误差达到时，或者两者兼而有之。

对于您的情况，我认为您需要有一个二级阈值，它使用slopeY = deltaY/deltaZ来确定这条线是否即将进入相邻的单元格。如果stepZ是每个像素沿线z的变化，那么像error > .5 - slopeY/stepZ这样的测试应该告诉您在y中线的两边都有单元格。一个类似的测试告诉您是否必须在x中获得额外的单元格。如果你必须得到x和y中的额外单元格，那么你也必须得到与Bresenham单元格对角的单元格。

如果您检测到在递增之前在y中添加了一个单元格，则不会在递增之后添加单元格。如果您以前没有添加过y单元格，则必须在添加之后添加，除非您碰巧经过了一个单元格角。如何处理取决于您的用例。

这是我对这个问题的看法，我还没有测试过任何东西，但是类似的东西应该可以工作。