Как нарисовать линию в трехмерном пространстве через сетку с начальной точкой и вектором направления

Я работаю над 3D-игрой от первого лица. Уровни полностью основаны на кубах, стены/полы/и т. д. - все просто плиточные кубы (1x1x1).

В настоящее время я создаю луч, используя положение камеры и вращение камеры, чтобы получить направление. Я хочу затем вывести луч на первый куб, который не пуст (или когда луч падает с сетки). Довольно часто это векторы направления, такие как 0,0,1 или 1,0,0.

Мне не очень повезло найти алгоритм рисования линии Брезенхема, который работает с вектором направления, а не с начальной/конечной точкой. Особенно учитывая, что вектор направления не будет содержать только целые числа.

Итак, для конкретного вопроса, я думаю, я спрашиваю, может ли кто-нибудь объяснить, приближаюсь ли я к тому, чтобы сделать это правильно, и может ли кто-нибудь подробно рассказать о том, как это должно быть сделано независимо.


c# line raytracing bresenham
person Mythics    schedule 28.11.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Боюсь, Брезенхэм вам здесь не поможет... вам нужны алгоритмы пересечения Ray/Line-Plane:

В очень грубом мати-псевдокоде:

(предостережение: я давно не занимался 3D-графикой)

// Ray == origin point + some distance in a direction
myRay = Porg + t*Dir;

// Plane == Some point on cube face * normal of cube face (facing out),
// at some distance from origin
myPlane = Pcube * Ncubeface - d;

// Straight shot: from ray origin to point on cube direction
straightTo = (Pcube - Porg);

С этими двумя уравнениями вы можете сделать некоторые выводы:

  • Если скалярное произведение 'rightTo' и нормали к плоскости равно нулю (назовем это "angA"), ваша исходная точка находится внутри грани куба.

  • Если скалярное произведение направления луча и нормали к плоскости близко к 0 (назовем это "angB"), луч проходит параллельно грани куба, то есть не пересекается (если только вы не считаете, что начало координат находится в грань куба выше).

  • Если (-angA / angB) ‹ 0, ваш луч направлен в сторону от грани куба.

Есть и другие вещи, но я уже исчерпал пределы своей скудной памяти. :)

РЕДАКТИРОВАТЬ: может быть "ярлык", теперь, когда я думаю, что это немного... все это предполагает, что вы используете структуру, подобную трехмерному массиву, для своей "карты".

Хорошо, так что потерпите меня здесь, думая и печатая на моем телефоне - что, если вы использовали стандартный старый алгоритм дельта-ошибки Брезенхема, но «исправили» его в 2D?

Итак, скажем:

  • Мы находимся на позиции (5, 5, 5) в "коробке" (10x10x10).
  • Мы указываем (1 0 0) (т.е. ось +X)
  • Луч, отбрасываемый из верхнего левого угла пирамиды обзора, по-прежнему остается линией; определения для "x" и "y" меняются, это все
  • «X» в этом случае будет (мысленная визуализация)… скажем, вдоль оси, параллельной линии глаз, но на уровне линии заброса; то есть, если бы мы смотрели на 2D-изображение, которое было (640x480), «центр» был (0,0) и верхний левый угол был (-320,-240), эта «линия оси X» была бы линией бросаем через точку (-320,0) в бесконечность.
  • «Y» также будет проекцией нормальной оси «Y», так что… почти то же самое, если только мы не наклоним голову.
  • Итак, математика станет чертовски сложной при попытке вычислить, каким будет следующее значение deltaX, но как только вы разберетесь с формулой, это будут в основном вычисления с постоянным временем (и теперь, когда я думаю об этом, «Ось X» будет просто вектором ‹1 0 0>, спроецированным через любую проекцию вашей камеры, верно?

Извините за бессвязность, я еду домой на поезде. ;)

person JerKimball    schedule 28.11.2012
comment
При повторном прочтении я, вероятно, должен был назвать angA и angB cosAngA и cosAngB, если я правильно помню свою математику... - person JerKimball; 29.11.2012
comment
В основе лежит предложение перебрать все кубы во всем мире игры, чтобы найти, на какой из них смотрит игрок, сравнивая расстояния столкновения? Простой тест ray to aabb звучит проще, если это так. Я думаю, я мог бы просто смотреть на кубы на расстоянии X, используя технику заливки из плеера, но я действительно думал, что будет простой алгоритм 3D raycast, который не требует совершенно другой структуры данных или чего-то еще. - person Mythics; 29.11.2012
comment
@TimWinter - Есть несколько оптимизаций, которые вы могли бы сделать. Например, разделить ваши кубы на мегакубы и выяснить, в какой мегакуб он попал, а затем углубиться. Это очень обширная тема. Трассировка лучей Google, если у вас есть время. - person System Down; 29.11.2012
comment
@TimWinter - Да, это в значительной степени основной вариант использования Quadtrees и подобных схем разбиения ближайших соседей. - person JerKimball; 29.11.2012