走两个点之间的线在三维体元空间来访所有单元

问题描述

予有视线的问题，我需要通过访问所有可能的细胞的三维体元空间2（非格栅对齐）点之间来解决。

I have a line-of-sight problem I need to solve by visiting all possible cells in a 3D voxel space between two (non-grid-aligned) points.

我使用3D Bresenham算法已经考虑，但是它会跳过一些细胞

I have considered using a 3D Bresenham algorithm, but it will skip out some cells.

一个幼稚的做法是只检查点沿线在更高的分辨率比素格，但我希望一个更智能的解决方案。

A naive implementation might be to just check points along the line at a higher resolution than the voxel grid, but I was hoping for a more intelligent solution.

任何人有什么线索？

推荐答案

想出了这个，或者参阅：的http：// jsfiddle.net/wivlaro/mkaWf/6/

Came up with this, or see: 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);
}

这篇关于走两个点之间的线在三维体元空间来访所有单元的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！