9

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

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

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

有人有线索吗？

4

5 回答 5

9

想出了这个，或者看：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);
}
于 2013-05-12T13:10:12.707 回答
3

据我所知，最初的 Bresenham 算法假设允许沿对角线移动，在您的情况下，禁止它是有意义的。

但主要思想是相同的——每个体素都回答“下一步是什么？”这个问题。

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

注意：这假设体素沿每个轴具有相同的大小，如果不是这种情况，则应计算修改后的距离（每个分量应除以沿相应轴的体素大小）

于 2013-05-12T11:03:14.753 回答
2

我认为 3d Bresenham 是要走的路，只是稍微调整了一下。作为解决问题的第一步，使用 Bresenham 进行操作，但当您即将迈出一步或刚刚迈出一步时，请保持怀疑，因为这些是线路可能通过额外单元格的地方。

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

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

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

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

于 2013-05-12T10:11:49.817 回答
1

这是我的体素射线从 C++ 到 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 进行光线跟踪。

希望有帮助。

于 2013-05-16T21:01:59.590 回答
0

https://code.activestate.com/recipes/578112-bresenhams-line-algorithm-in-n-dimensions/

这是 ND bresenham 线图的一个 numpy 实现，以防有人从谷歌搜索“bresenham 3d python”中发现这个线程。

于 2021-03-15T01:27:44.077 回答