Эффективный доступ к кругу лучей (поиск ближайших контуров препятствий)

Question

Имейте бинарную сетку (как черные и белые пиксели с черным = пустым и белым = препятствием). Начиная с заданной точки на черном, я хочу испускать «лучи» во всех направлениях. Эти лучи должны прерываться при достижении заданной длины (например, 100) или при попадании на белый пиксель (в этом случае должна быть отмечена позиция этого пикселя, или контур препятствия). Эти отмеченные пиксели приводят к просмотру всех контуров препятствий, которые «видны» из данной точки (не мешаются другими препятствиями).

То, о чем я думал до сих пор, - это просто вызвать достаточное количество линии Брезенхэма. В случае радиуса 100 это означает 100 * 2 * pi = 628 линий, чтобы покрыть все пиксели на самой внешней окружности. Однако это приводит ко многим множественным проверкам одинаковых пикселей ближе к центру. Теперь я могу разделить проверку по нескольким кольцам, каждая из которых имеет разную плотность линий Брезенхэма, но это тоже выглядит неэффективно.

У кого-нибудь есть более эффективная идея алгоритма для этого? Огромное спасибо заранее!

Answer 1

Пусть «квадратное расстояние» между двумя точками (x1, y1) и (x2, y2) будет max (| x1-x2 |, | y1-y2 |), чтобы точки увеличивали «квадратное расстояние» вокруг центр для все более крупных квадратов.

Теперь для каждого расстояния квадрата d от вашей центральной точки в порядке возрастания следите за углами, которые центральная точка может видеть сквозь все препятствия с помощью расстояние <= d. </p>

Вы можете использовать список угловых интервалов, начинающихся с [(0,360)] для d = 0.

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

Этот метод проверяет пиксели только один раз и только те пиксели, которые вы видите. Однако то, как я написал это выше, требует тригонометрии, которая медленная. Для практической реализации вместо фактического использования углов используйте склоны, для которых требуется только простая математика, и обрабатывайте каждый октант отдельно.

Answer 2

К сожалению, намеки на методы обработки графики, хотя и увлекательные, не очень применимы в моем случае, потому что у меня нет доступа к шейдерам или камере и т. Д. c.

На данный момент я нашел достаточно эффективный Решение сам. Основная идея c - запускать лучи от контуров, а не от источника. Кроме того, использовать вспомогательную сетку с именем «достижимая», где отмечены все пиксели, которые успешно видны с начала координат. Таким образом, только несколько пикселей читаются дважды, большинство читается только один раз, а некоторые записываются не более одного раза. Код пока довольно грязный, поэтому здесь только псевдокод:

Have desired origin O.x/O.y
Have obstacle bool grid Obstacle

Define bool grid Reachable[w][h]    
Clear Reachable with false

Reachable[O.x][O.y] = true

For each Point C on all obstacle Contours // if not available, compute contours by finding all pixels adjacent to non-obstacle    
    For all Pixels A on Bresenham line from C to O

        If Obstacle[A.x][A.y]    
            Continue with outer loop on contours // abort this line due to obstacle hit

        If Reachable[A.x][A.y]
            For all Pixels B on Bresenham line from C to A
                Reachable[B.x][B.y] = true // mark all pixels on this line as Reachable
            Mark C as a desired result pixel
            Continue with outer loop on contours