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

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

0 голосов
/ 24 мая 2018

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

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

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

2D Bresemham

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

1 Ответ

0 голосов
/ 24 мая 2018

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

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

В качестве альтернативы вы можете просто сделать полное обобщение: 

 // 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 --;
     }
   }
}

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

...