Найдите линию, соединяющую две грани кубического объема

Представьте себе объемный куб разрешения N³, заполненный окклюзионными вокселями. Куб может быть полностью заполнен или содержать пышные "туннели" или стены - или просто несколько бродячих вокселей; Теперь мы выбираем любые две из шести граней ограничивающего куба и пытаемся найти линию, соединяющую эти две грани, не попадая ни в какой воксель внутри него. Если такая линия существует, лица могут видеть друг друга, иначе они полностью закрыты.

Мой вопрос: существует ли алгоритм O (n) (или лучше), чтобы быстро распознать, может ли такая строка быть нарисована? Точные параметры линии не имеют значения.

Ответ 1

A Voxel куб будет выглядеть как Rubik Cube, voxel - это трехмерная матрица блоков, поэтому, чтобы нарисовать линию с одной стороны на другую, нам нужно сделать в каждом связанном блоке строку, соединяющую к следующему, вместе линии образуют одну сплошную линию через куб.

Следующий алгоритм работает отлично, если его реализовать хорошо, так как вы собираетесь работать с локальными координатами внутри куба, любые преобразования самого куба будут автоматически применяться 3D-движком, когда он переведёт его в мировые координаты.

Сложность времени

MATRIX.MAX_Z * (
                   Time(MATRIX.GET_VOXEL(x,y,z))
                 + Time(VOXEL.DRAW-LINE(0,0,0, 0,0,VOXEL_DEPTH))
               )

Алгоритм

FUNCTION DRAW (INTEGER X, INTEGER Y)

    INTEGER VOXEL_X = X / MATRIX.VOXEL_WIDTH
    INTEGER VOXEL_Y = Y / MATRIX.VOXEL_HEIGHT

    FOR i = 0 .. (MATRIX.MAX_Z-1)

        VOXEL V = MATRIX.GET_VOXEL(VOXEL_X, VOXEL_Y, i)

        INTEGER X_0 = X % MATRIX.VOXEL_WIDTH
        INTEGER Y_0 = Y % MATRIX.VOXEL_HEIGHT
        INTEGER Z_0 = 0

        INTEGER X_1 = X_0
        INTEGER Y_1 = Y_0
        INTEGER Z_1 = (MATRIX.VOXEL_DEPTH-1)

        V.DRAW-LINE(X_0,Y_0,Z_0, X_1,Y_1,Z_1)

    END-FOR

END-FUNCTION

Ответ 2

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

Разрешение, при котором вы выполняете
Как быстро вы можете сделать ортогональный, двоичный вид

Теперь для этого двоичного рендеринга единственное, что вам нужно знать, покрывается/не покрывается. Это доходит до двух осей, один для минимума и один для максимума. Минимальные дорожки деревьев "есть ли какой-либо открытый ребенок node (или)" максимальные треки "есть ли какой-либо закрытый дочерний элемент node (и)". Построение этих деревьев - n log (n), но запрос - только log (n).

Для целевого разрешения m должно быть только log (m). Даже если вы подойдете к m = 2 ^ 23 для размера поплавка.

Ответ 3

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

    +-+-+-+          +-+-+-+-+-+
    | |#| |          |#| | | | |
    +-+-+-+          +-+-+-+-+-+
    | |#| |          |#| | |#| |
    +-+-+-+          +-+-+-+-+-+
    | |#| |          |#| | |#| |
    +-+-+-+          +-+-+-+-+-+
                     |#| | |#| |
                     +-+-+-+-+-+
                     | | | |#| |
                     +-+-+-+-+-+

... но это может быть непроницаемо, в зависимости от того, как вы обрабатываете свои углы:

  +-+-+-+-+-+
  |#| | | |/|
  +-+-+-+-+-+
  |#| | |/| |
  +-+-+-+-+-+
  |#| |/|#| |
  +-+-+-+-+-+
  |#|/| |#| |
  +-+-+-+-+-+
  |/| | |#| |
  +-+-+-+-+-+

... и это определенно возможно:

  +-+-+-+-+-+
  |#| | | | |
  +-+-+-+-+-+
  |#| | | | |
  +-+-+-+-+-+
  |#| | | | |
  +-+-+-+-+-+
  | | | |#| |
  +-+-+-+-+-+
  | | | |#| |
  +-+-+-+-+-+

Теперь, если вы можете придумать какой-либо трюк, который может отличить верхние 2D-кубы от нижнего, это может устранить хотя бы некоторые невозможные конфигурации пикселей/вокселей, но я боюсь, что вам нужно протестировать каждый пиксель на ваша целевая сторона для света, проходящего со стороны источника с любого угла, что звучит ужасно, как проблема n-квадрата (2D) или n ^ 4 в 3D.

В 2D, я бы начал в верхней части левой стороны и проверить, удаляет ли линия, соединяющая мой воксельный центр с верхним правом, окклюзионный пиксель: если нет, мы закончили; если это так, вы продвигаете свой угол так, чтобы луч проходил в нижнем левом углу окклюзии и продолжал проверять, пока вы не найдете проход или не дойдете до конца правой стороны.

Продолжайте работу с каждым пикселем на стороне источника, пока вы не закончите - так или иначе.

Но эта грубая сила, и мне было бы интересно увидеть более элегантное решение, возможно, G. Бах...?