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

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

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

источник

2015-03-26 paniq

Прямая линия, не так ли? –

Да. Сначала я написал прямую линию, затем подумал, что это, вероятно, лишнее упоминать. – paniq

O (n) кажется немного оптимистичным для меня; с какой сложностью вам будет комфортно? –

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

Следующий алгоритм работает отлично, если его реализовать хорошо, поскольку вы собираетесь работать с локальными координатами внутри куба, любые преобразования самого куба будут автоматически применяться 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

источник

2015-03-29 08:44:34

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

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

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

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

источник

2015-04-20 03:32:11 starmole

Боюсь, я не понимаю, что вы подразумеваете под «исходным кубом» и «целевым кубом», ни открытыми, ни закрытыми дочерними узлами. Если вы подходите к этому с помощью угла трассировки лучей, вам все равно нужно проверить каждый пиксель на целевой стороне куба для света, идущего с любого угла, то есть любого пикселя на стороне источника куба. Мне кажется O (n^4) мне ... –

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

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

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

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

...и это, безусловно, можно:

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

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

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

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

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

источник

2016-01-25 08:47:19

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

ответ

Смежные вопросы