На трехмерной местности, учитывая трехмерную линию, найдите точку пересечения между линией и местностью

Question

У меня есть сетка трехмерной местности, где каждая из координат (x,y,z) каждой сетки известна. Теперь у меня есть монотонно увеличивающаяся / уменьшающаяся линия, начальная точка которой также известна. Я хочу найти точку, где местность и линия встречаются. Какой алгоритм это сделать?

Я могу думать о том, чтобы сохранить координату трехмерного рельефа в матрице nxn. И тогда я бы сегментировал линию на основе сетки на местности. Затем я бы начал с сетки, ближайшей к линии, и затем попытался бы вычислить, пересекает ли эта плоскость линию, если да, то получить координату и выйти. Если нет, то я перейду к следующему сегменту.

Но мой алгоритм лучший или самое оптимальное решение? Или есть какие-нибудь библиотеки, которые уже делают это?

Answer 1

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

Очевидно, вам нужно выполнить некоторые оптимизации, например, проверять только те грани, которые пересекают ограничивающую рамку линии. Вы можете сделать довольно дешевую / быструю проверку граничного прямоугольника от грани до линии, которая очень быстро сбрасывает со счетов большинство треугольников на местности.

Если вы расположите свои треугольники в октрее (как предложено @ sum1stolemyname, но для точек), тогда эту проверку можно выполнить сверху вниз, и вы сможете сделать скидку на целые участки местности одним расчет.

Answer 2

Не напрямую, а оптимизация, всего несколько советов:

Если ваша сетка большая, возможно, стоит построить октре из вашей местности, чтобы быстро уменьшить количествоузлы сетки вы должны проверить свою линию.Это может быть более эффективным в огромной сетке (например, 512 * 512 шагов), поскольку необходимо учитывать только те узлы, через которые проходит ваш луч.

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

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

Однако, если вы не планируете изменять свою сетку после ее созданияоктрие будет полезно.

ОБНОВЛЕНИЕ

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

Нахождение ближайшего соседа линейно имеет сложность времени выполнения O (N), в то время как подходы разделения пространства имеют среднюю сложность времени выполнения, если O (log N).

Answer 3

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

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

Однако есть хороший прием, позволяющий сэкономить время. Это описано здесь соотв. здесь . Он использует некоторую структуру оптимизации для ландшафта, то есть он строит несколько уровней детализации следующим образом: Самый прекрасный уровень детализации - это просто сама местность. Следующий (более грубый) уровень детализации содержит только четвертую часть количества оригинальных «пикселей» в текстуре ландшафта и объединяет 4 пикселя в один, что позволяет получить максимум. Следующий уровень детализации построен аналогично:

     .             .       .    .
    ... .         ...     ..    .
  .......        ....     ..    .
 ........    =>  ....  => .. => .

 01234567        0246     04    0
                 1357     26    4

   fine   =>  =>   =>   =>  =>  coarse

Если теперь выполняется приведение лучей, в первую очередь проверяются более грубые уровни детализации:

   /
  / 
 /.
  .
  .
  .

Если луч уже пропускает грубый уровень детализации, более тонкий уровень проверять не нужно. Это просто очень грубая идея, как работает оптимизация. Но это работает довольно хорошо. Реализация этого довольно сложная работа, но статья - хорошая помощь.