Алгоритм Брезенхэма линии визирования 3D Voxel Grid

Question

Учитывая трехмерную сетку вокселей, где каждый воксел имеет размер SIZE * SIZE * SIZE (ширина * высота * длина) для некоторого целочисленного размера и линии, проходящей через некоторые из вокселей в сетке, существует ли достаточно эффективный способ вычисления линии обзора алгоритм обнаружения всех вокселей, через которые проходит линия?

Ограничения алгоритма:

1. Никакие вокселы не пропущены из-за приблизительной природы оригинального Брезенхэма, как видно из этого 2D-примера:

2. Алгоритм должен быть достаточно эффективным, так как он будет рассчитываться один раз за кадр; пока алгоритм не берет область кубов и вычисляет, пересекает ли линия каждый отдельный куб, все должно быть в порядке.

Answer 1

Во-первых, Брезенхэм не так хорош в зоне прямой видимости: как показывает ваш рисунок, результирующий выбор ячеек / вокселей не позволит источнику "увидеть" цель из-за всех этих зубчатых краев.

Однако, если вы хотите считать, что Брезенхем хорош для вашей задачи в 2d, легко перейти к 3d: учитывая строку от p0 = {x0, y0, z0} до p1 = {x1, y1, z1}, вы можете дважды запустить 2d Bresenham с {x0, y0} до {x1, y1} и с {x0, z0} до {x1, z1}. Используйте значения x и y из первого прогона и значения z из второго прогона.

Кроме того, вы можете просто сделать полное обобщение:

 // adapted from https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
 // expects x to be the fastest-changing dimension; replace
 //   with fastest-changing dimension otherwise, and fix plot() accordingly
 function line(float x0, float y0, float x1, float y1, float z1, float y1) {
   float dx = x1 - x0;
   float dy = y1 - y0;
   float dz = z1 - z0;
   float deltaErrorY := abs(dy / dx);
   float deltaErrorZ := abs(dz / dx);
   float errorY = 0;
   float errorZ = 0;
   int y = y0;
   int z = z0;
   for (int x = x0; x<x1; x++) { 
     plot(x,y,z);
     errorY += deltaErrorY;
     while (errorY >= 0.5) {
         y += sign(dy);
         errorY --;
     }
     errorZ += deltaErrorZ;
     while (errorZ >= 0.5) {
         z += sign(dz);
         errorZ --;
     }
   }
}

Идея, лежащая в основе Brensenham, может быть обобщена на любое измерение: просто отслеживайте накопленные ошибки и прыгайте при необходимости, чтобы держать их под контролем