Проведите линию между двумя точками в трехмерном пространстве вокселей, посетив все ячейки.

Придумал это или посмотрите: 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);
}

Насколько я помню, исходный алгоритм Брезенхема предполагает, что движение по диагоналям разрешено, в вашем случае имеет смысл его запретить.

Но основная идея одна - для каждого вокселя ответить на вопрос «что дальше?»

Каждый воксель имеет 6 лиц, каждое из которых ведет к другому соседу. Просто проверьте, центр какого воксела ближе к линии, чем другие. Это следующий воксель.

Примечание: это предполагает, что воксель имеет одинаковый размер по каждой оси, если это не так, вы должны рассчитать модифицированное расстояние (каждый компонент должен быть разделен на размер вокселя по соответствующей оси)

Я думаю, что 3d Bresenham - это то, что вам нужно, только немного подправили. В качестве первого шага к проблеме действуйте как Брезенхэм, но будьте подозрительны, когда собираетесь сделать шаг или вы только что сделали шаг, так как это места, где линия может проходить через лишние ячейки.

Для простоты предположим, что z является доминирующим, что означает, что z увеличивается на каждый шаг. 3-й вопрос Брезенхема: «когда мы увеличиваем / уменьшаем x или y?» Ответ: когда накопленная ошибка в x достигает 0,5, или когда ошибка в y достигает, либо и то, и другое.

В вашем случае, я думаю, вам нужен вторичный порог, который использует slopeY = deltaY/deltaZ, чтобы определить, собирается ли линия перейти в соседнюю ячейку. Если stepZ - это изменение z вдоль линии для каждого пикселя, то такой тест, как error > .5 - slopeY/stepZ, должен указать вам, что ячейки должны быть по обе стороны от линии в y. Аналогичный тест покажет вам, нужно ли вам получить дополнительную ячейку в x. Если вам нужно получить дополнительную ячейку как в x, так и в y, тогда вы должны также получить диагональ ячейки к ячейке Брезенхема.

Если вы обнаружили, что добавили ячейку в y до приращения, вы не добавите ячейку после. Если вы не добавляли y ячейку раньше, вам придется добавить ее после, если только вы не прошли через угол ячейки. Как вы справитесь с этим, зависит от вашего варианта использования.

Это мои мысли по этому поводу, я ничего не тестировал, но что-то вроде должно работать.

Вот публичная ссылка на недавний перенос моего воксельного луча с 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

Обратите внимание, что вы также можете трассировать лучи с более низким уровнем детализации, просто ограничив глубину проникновения в дерево во время трассировки.

Надеюсь, это поможет.

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

Вот простая реализация для рисования линий N-D bresenham на тот случай, если кто-то наткнулся на эту ветку при поиске в Google 'bresenham 3d python'.