Алгоритм расчёта области видимости и линии взгляда в играх

Привет, Вы узнаете о том , что такое эффективный расчёт области видимости, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое эффективный расчёт области видимости, линии взгляда в играх , настоятельно рекомендую прочитать все из категории Разработка компьютерных игр.

В стратегических играх обычно требуется знать область видимости NPC, чтобы игрок мог продумывать стратегию и делать следующий ход. Мы рассмотрим математику и реализацию рациональной модели, не просаживающей скорость игры при большом количестве NPC на карте. Если вы хотите увидеть готовое интерактивное демо модели, перейдите сюда и играйте прямо в браузере! Вот скриншот демонстрации:



Имея параметры видимости наблюдателя (направление взгляда, расстояние видимости и угол поля зрения), нам нужно найти видимую для него область, т.е. определить область видимости (field of view, FoV). Если препятствия отсутствуют, это будет сектор круга, состоящий из двух граней (радиусов) и соединяющей их дуги (см. Рис. 1). Кроме того, имея заданную точку мира, мы должны быстро определить, видима ли она для наблюдателя, т.е. необходимо обрабатывать запросы линии взгляда (line of sight, LOS) для заданной точки. Обе эти операции можно выполнить достаточно эффективно для использования при рендеринге в реальном времени.


Рис. 1

Положение наблюдателя представлено красной точкой, стрелкой указано направление взгляда, r — это расстояние видимости, а θ — половина угла поля зрения.

1 Входные данные

• Набор полигонов, в том числе и границы мира
• Параметры FoV
  
  • Положение наблюдателя
  • Направление взгляда, V
  • Угол поля зрения, 2θ < 180°
  • Расстояние видимости, r

Примечание: здесь и ниже буквы в нижнем регистре обозначают скалярные значения, а в верхнем — векторные.

1.1 Полигоны и ребра

При описании мира в 2D здания естественным образом разбиваются на полигоны и таким образом становятся входными данными алгоритма. Однако технически область зрения ограничивается стенами, т.е. ребрами полигонов. Кроме того, работа с ребрами полигонов обеспечивает улучшенные детализацию и контроль, потому что при проверке пересечений мы в основном будем иметь дело с геометрическими примитивами. Поэтому в большинстве случаев алгоритм работает непосредственно с ребрами и не касается абстракций более высокого уровня (полигонов).

2 Базовый алгоритм

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


Рис. 2

В реальном мире мы видим объекты, когда световые лучи беспрепятственно попадают в глаз. Интуитивно понятно, что видимость можно определить обратной операцией, т.е. испусканием лучей из глаза в мир. В случае источника света лучи испускаются во всех направлениях. В практической реализации лучи испускаются радиально с заданным интервалом, например, один луч через каждые 5° и 72 луча для всей окружности. Луч должен двигаться, пока он не будет заблокирован ребром. Испускание лучей на все 360° и определение освещенной источником света области в 2D является решенной проблемой [1]. Точность этого способа зависит от интервала между испускаемыми лучами. Меньшие интервалы обеспечивают большую плотность распределения лучей.


Рис. 3

Испускание лучей — это, иными словами, проверка на пересечение лучей с отрезками прямых. Для заданного луча при m отрезках выполняется m проверок для определения ближайшего к лучу ребра, блокирующего его. Поэтому в любом алгоритме отслеживания лучей для испускания n лучей на m ребер необходимо выполнить n × m проверок. Однако, какой бы малой ни была ресурсоемкость проверки пересечения лучей и отрезков прямых (ребер), в огромном мире со множеством источников света такой подход может стать слишком затратным.

Давайте назовем блокирующее луч ребро блокирующим ребром. На Рис. 3 они выделены красным. Точку, в которой луч пересекает блокирующее ребро, назовем точкой попадания. После нахождения всех точек попадания их необходимо кругообразно соединить, т.е. все точки попадания упорядочиваются по углу и соединяются по линиям для определения области, освещенной источником света. Результатом будет неправильный замкнутый контур. Следует заметить, что при соединении точек пересечения таким образом некоторые углы или части полигонов отсекаются, что приводит к неверной или менее точной освещенной области. Ее можно улучшить, уменьшив интервал испускания лучей. Чем меньше интервал, тем больше лучей и лучше покрытие. Результат улучается, но за счет снижения производительности.

С помощью этой проблемы определения области освещенности мы рассмотрели основной подход, который мы будем использовать для решения нашей проблемы: метод отслеживания лучей (ray casting). Заметьте, что лучи света исходят из источника света во всех направлениях, пока не пересекутся с препятствием. Отсутствие ограничений делает проблему более простой по сравнению с нашей проблемой, в которой ограничены угол и расстояние видимости. Мы обсудим, почему это так, позже, в разделе 3.

2.1 Оптимизация

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


Рис. 4

Мы будем называть эти концы ребер, дающие нам угол испускания лучей, угловыми точками. Это название вместо может показаться избыточным и бессмысленным, но позже оно нам пригодится. Угловые точки — это точки, в которые испускаются лучи видимости. На Рис. 4 угловые точки отмечены красным, синим и черным. Лучи испускаются во все эти точки. Точки, расположенные ближе всего к лучу, преобразуются в точки попаданий, отмеченные красным. Точки, которых не достигает их луч, отмечены черным. Эти лучи пересекаются с более близкими ребрами и создают точки попаданий, отмеченные синим.

2.2 Зрение без углов

Хотя испускание лучей только в концы ребер нас устраивает, у него есть небольшой недостаток. Заметьте, на Рис. 4 луч, испущенный к углу полигона, пересекает одно из ребер, создающих угол, и не двигается дальше. Однако видимость должна в некоторых случаях быть дальше угла. Умный подход к решению этой проблемы показан в интерактивной статье [2].

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


Рис. 5

Вспомогательные лучи выделены оранжевым. Угол отклонения (между оранжевым и черным лучом) здесь намеренно преувеличен для ясности, но он должен быть намного меньше, скажем, полградуса.

Простой оптимизацией стало бы определение того, видны ли оба ребра, формирующие угол, или одно из них скрыто другим. Если видны оба, то вспомогательные лучи не требуются, ведь видимость не может распространяться дальше. На Рис. 4 вершина треугольника — это видимый угол, вспомогательные лучи здесь не нужны, ведь видимость не может распространяться дальше. Вспомогательные лучи нужны только когда одно из двух ребер скрыто от наблюдателя. Оба ребра не могут быть скрыты, потому что мы смотрим на каждый угол полигона в отдельности — на два ребра и точку, в которой они соединяются (см. Рис. 6, черные стрелки и синяя точка). Даже если одно из ребер скрыто, испускание двух вспомогательных лучей избыточно; одного можно избежать, потому что только один может беспрепятственно пройти за угол. На Рис. 5 вспомогательный луч, созданный вращением первичного по часовой стрелке, избыточен.


Рис. Об этом говорит сайт https://intellect.icu . 6

Для определения того, блокирует ли одно из ребер другое, можно использовать теорему о разделяющейся оси. Проецирование векторов обоих ребер на вектор, перпендикулярный первичному лучу, даст результаты с разными знаками, если одно из ребер блокирует другое. Также в зависимости от знака проекции первого ребра мы можем узнать, какой из двух вспомогательных лучей необходим. На Рис. 6 сверху показаны три возможные ситуации, а внизу — результаты проецирования. Черная точка обозначает позицию наблюдателя, из которой испускается первичный луч (красный). Векторы ребер (черные) проецируются на перпендикулярный первичному вектор (зеленый). Если вспомогательные лучи не требуются, обе проекции дают отрицательные значения, потому что оба вектора ребер находятся в отрицательном полупространстве перпендикуляра. В двух других случаях, где нужны вспомогательные лучи (оранжевые), знаки проекций отличаются от знаков векторов; если знак отрицателен для вектора более длинного ребра, то достаточно повернутого по часовой стрелке вспомогательного луча, а если он положителен, достаточно луча, повернутого против часовой стрелки.

3 Блокирующие ребра и угловые точки

В рассматриваемой нами задаче видимость ограничена углом и расстоянием; это приводит нас к интересным ситуациям.

• Угловыми точками становятся не все концы ребер, а только находящиеся в области сектора видимости.
  
  • Это как минимум вдвое снижает количество испускаемых лучей. n теперь становится еще меньше.
  • Чтобы воспользоваться этим преимуществом, следует приложить усилия для отделения угловых точек от концов ребер. Используемая для этого техника должна быть достаточно быстрой, чтобы само отделение не занимало слишком много времени.
• Кроме того, большинство ребер потенциально не будут блокирующими; для нас важны только те, которые содержатся в секторе или отсекаются им.
  
  • Это позволяет снизить количество необходимых проверок пересечений. Значение m должно снизиться.
  • Для этой цели нам также следует придумать быстрый алгоритм отсечения ненужных ребер.

Основное отличие или отклонение от базового алгоритма, объясненного в разделе 2, заключается в том, что могут существовать угловые точки, не входящие в множество концов ребер. Может потребоваться определение большего количества угловых точек. См. конфигурации на Рис. 7 и 8. Концы ребер находятся за пределами сектора видимости, поэтому бесполезны в качестве угловых точек. Все угловые точки, необходимые для правильного определения области видимости (отмеченные черным, синим и красным) не совпадают с концами ребер. Необходима каждая из них, невозможность испускания луча в любую из них приведет к неправильному определению области видимости. В чем они отличаются и как их определить?

Поскольку зрение ограничено углом видимости, две угловые точки необходимы и должны безусловно приниматься вне зависимости от наличия ребра. Они являются крайними точками на ребрах сектора. В них испускаются лучи и определяются точки попадания. На Рис. 7 черным показана одна из этих подразумеваемых угловых точек: угловая точка, возникшая из-за точки правого ребра сектора. Испущенный в нее луч заблокирован ребром, что привело к появлению синей точки. Другой луч, испущенный в угловую точку левого ребра, проходит беспрепятственно. Поэтому точкой попадания становится сама угловая точка, выделенная синим. Итак, синие точки определять просто, они не требуют проверок. Их положение постоянно и зависит от положения и направления сектора видимости.

Рассмотрим красную угловую точку (превратившуюся в точку попадания, потому что луч ничем не заблокирован) в пересечении дуги и ребра сектора. Она требует еще одной проверки пересечения: проверки пересечения дуги и отрезка прямой. Эти угловые точки необходимы, когда ребро пересекает дугу сектора.


Рис. 7

Луч показан острием стрелки, а ребро имеет конечные точки.


Рис. 8

С учетом этого мы перечислим случаи возникновения угловых точек:

• Любая конечная точка ребра, находящаяся в секторе видимости
• Любая точка дуги сектора, в которой ее пересекает ребро

Кроме того, потенциально блокирующими ребрами являются ребра, полностью или частично находящиеся в секторе.

Теперь проблема становится задачей получения множества угловых точек (поиска новых и отбрасывания ненужных конечных точек) и множества потенциально блокирующих ребер (отсечение неблокирующих ребер). Эту задачу необходимо выполнять быстро, как можно раньше отбрасывая неправильные элементы, чтобы не обременять циклы обработки результатами, которые потом будут отброшены. Цель заключается в снижении значений n (количество испущенных лучей = количество угловых точек) и m (количество отрезков для проверки пересечения с лучом = количество потенциально блокирующих ребер), обеспечивающем быстрый алгоритм для определения FoV.

3.1 Отсечение

В [3] предполагается, что идеальный алгоритм отсечения (в реальности он будет ресурсоемким и осложненным проблемами точности чисел с плавающей запятой) оставляет только множество видимых точек, а достаточно хороший алгоритм отбрасывает большинство невидимых, оставляя точно видимые и потенциально видимые. Он будет консервативен при отбрасывании потенциально видимых точек. Другими словами, если он не может быть совершенно уверен, что ребро не мешает видимости, он не будет отбрасывать его.

3.1.1 Этап раннего, тривиального отбрасывания

Простейшая идея для отбрасывания неподходящих конечных точек и ребер — проверять только конечные точки ребер, находящиеся внутри сектора. Это подходит для угловых точек, но недостаточно для блокирующих ребер, потому что не сработает в конфигурациях, где конечные точки ребер не находятся в секторе, но ребро блокирует видимость (см. Рис. 7 и 8). Прежде чем переходить к более детальному анализу, проверку конечных точек, если мы можем отбросить ребро, можно полностью пропустить.

3.1.1.1 Пересечение ребра с ограничивающей окружностью

Если ближайшая к центру окружности точка отрезка находится внутри окружности, то он либо находится в нем, либо пересекает его. Этот подход подробно описан в [4]. С помощью ребра и ограничивающей окружности сектора мы можем отбросить все ребра, не входящие в ограничивающую окружность. После этого этапа все ребра, не находящиеся в окружности, не рассматриваются. Поскольку это не проверка для поиска точек пересечения, а просто отсечение лишних ребер, то результат представляется в булевой форме и получается довольно быстро. Для реализации этой проверки нам нужна только пара операций векторного вычитания (дающих вектор) и скалярные произведения: одно для нахождения ближайшей точки (проецированием), а другое для расчета квадрата расстояния от нее до центра окружности.

Результаты этой проверки показаны на Рис. 9. Ограничивающая окружность сектора видимости отмечена пунктиром. Синяя точка на каждом ребре обозначает ближайшую к центру окружности точку. Зеленые ребра сохраняются для дальнейших расчетов. Сиреневые тоже сохраняются, но являются ложноположительными. Красные отбрасываются. Ребро, касающееся ограничивающей окружности, тоже отбрасывается, потому что не препятствует видимости.


Рис. 9

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

3.1.1.2 Точка относительно сектора

Имея точку и сектор, можно быстро определить

1. находится ли точка за наблюдателем
2. перед наблюдателем и
   
   1. за пределами расстояния видимости
   2. в пределах расстояния видимости и
      
      1. внутри сектора
      2. за пределами сектора, но внутри ограничивающей полуокружности

с помощью только скалярных и векторных произведений. Поскольку векторное произведение не определено в 2D, мы переносим векторы в 3D, принимая z = 0. Результаты векторного произведения являются вектором, но так как z = 0, элементы, относящиеся к x и y будут равны 0, и ненулевой будет только величина z (если векторы непараллельны). Таким образом мы получим из этого векторного произведения скалярный результат. См. различные определения векторного произведения в 2D в [5].

Пусть вектор из центра окружности к точке будет (U), а векторы ребер сектора — E1, E2. У нас уже есть направление взгляда V.

1. Если U ⋅ V < 0, то точка находится за наблюдателем.
2. иначе если U ⋅ U = ‖U‖² > r², то точка находится за пределами видимости.
3. иначе если sign(E1 × U) = sign(U × E2), то точка находится в секторе.
4. иначе она в окружающей полуокружности, но за пределами сектора.

Мы использовали две оптимизации, требующие объяснений. Мы сравниваем квадраты длин (2) вместо сравнения длин, потому что нахождение длины означает использование sqrt (квадратного корня). Мы избегаем этого и применяем оптимизацию, привычную для работы с компьютерной графикой ([7]). Для проверки того, находится ли точка внутри сектора (3), мы можем найти угол, противолежащий первому ребру сектора и проверить, находится ли он внутри допустимого угла видимости (2θ). Однако для этого нужно воспользоваться тригонометрической функцией acos (арккосинус), что может быть затратнее, чем расчет пары векторных произведений, в котором используются только арифметические операции.

Если ребро «пережило» предыдущую проверку, мы проверяем его конечные точки, чтобы определить, где они расположены. На Рис. 10 показана текущая ситуация: серые точки за наблюдателем (1), красные — за пределами сектора (2), зеленые конечные точки — внутри сектора (3), а сиреневая находится внутри ограничивающей полуокружности, но за пределами сектора (4).


Рис. 10

Угловые точки и блокирующие ребра можно определить из результатов:

1. Если оба конца за наблюдателем (1), они не мешают видимости; отбрасываем их и больше не обрабатываем.
2. Если оба конца внутри сектора (3), помечаем оба как угловые точки, а ребро — как блокирующее. Прекращаем дальнейшую обработку.
3. Если одна из них внутри сектора (3), а другая нет — (1), (2), (4) — помечаем одну внутри как угловую точку, а ребро — как блокирующее. Это ребро может пересекать дугу сектора и создать новую угловую точку.
4. Если обе за пределами сектора — (2), (4) — конечные точки не являются угловыми, но ребро может пересекать дугу сектора, создавая новые угловые точки. Ребро может быть блокирующим, если пересекает дугу или ребра сектора.

В случаях 3 и 4 нам требуются дополнительные проверки для нахождения угловых точек, не являющихся конечными точками, содержащихся внутри ребер и блокировки видимости ребрами. Это приводит нас к этапу сужения отсечения.

3.2 Этап сужения

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

Однако перед выполнением немного затратной проверки пересечения отрезка и дуги (в ней используется квадратный корень и больше трех операций ветвления) мы можем использовать результаты предыдущей проверки, чтобы убедиться в необходимости проверки. Проверка нужна только когда ребро имеет возможность пересечь дугу. Если обе конечные точки находятся внутри ограничивающей окружности, ребро не сможет пересечь окружность. Ребро может пересечь дугу сектора только если одна из его конечных точек находится перед наблюдателем, а другая — за пределами ограничивающей окружности (случай 2.1 в разделе 3.1.1.2).

Таблица 1. Возможные положения и состояния конечных точек ребер

№	Конец А	Конец Б	Состояние
1	Внутри	Внутри (2.2.1)	Угловые точки: A, Б • блокирует
2	Внутри	Сзади (1)	Угловая точка: A • блокирует
3	Внутри	В полуокружности (2.2.2)	Угловая точка: A • блокирует
4	Внутри	За пределами (2.1)	Угловая точка: A • блокирует • может пересекать дугу
5	Сзади	Сзади	Отбрасывается
6	Сзади	За пределами	Может пересекать дугу • может блокировать
7	Сзади	В полуокружности	Может блокировать
8	В полуокружности	В полуокружности	Может блокировать
9	В полуокружности	За пределами	Может пересекать дугу • может блокировать
10	За пределами	За пределами	Может пересекать дугу • может блокировать

С пунктами 1, 2, 3 и 5 мы уже имели дело на этапе раннего отбрасывания и с ними ничего уже делать не нужно. Для пункта 4 требуется проверка пересечения ребра с дугой, чтобы убедиться, что не нужна дополнительная угловая точка. На раннем этапе мы уже пометили одну из его конечных точек как угловую точку, а ребро — как блокирующее. Пункты 6-10 — самые интересные на этапе сужения. Для пунктов 6, 9 и 10 нужна проверка пересечения ребра с дугой, чтобы знать, возникают ли угловые точки при пересечении. Если это так, то ребро должно быть помечено как блокирующее. Если эти пункты не проходят проверку, они присоединяются к пунктам 7 и 8. Они не могут иметь угловых точек, но все равно должны пройти проверку пересечения ребра и ребра, чтобы знать, блокируют ли они видимость.

3.2.1 Пересечение ребра и дуги сектора

Для пунктов 4, 6, 9 и 10 Таблицы 1 мы с помощью проверки пересечения отрезка и дуги проверяем, пересекает ли ребро дугу сектора [6]. Если это так, то помечаем точки пересечения как угловые точки, а ребро — как блокирующее. Дальнейшая обработка не требуется. Если это не так, ребро не может иметь угловых точек, но ребро должно пройти следующую проверку на блокировку видимости.

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


Рис. 11

На Рис. 11 проверяется серое ребро с одной конечной точкой за пределами видимости, а другой конечной точкой — за наблюдателем, но обе точки пересечения сзади наблюдателя (сиреневые), а поэтому отбрасываются. Зеленое ребро с обеими точками в полуокружности никогда не проверяется. Красное ребро с одной конечной точкой за пределами видимости проверяется, но единственная найденная точка пересечения (синяя) не находится на дуге. Это ребро не может иметь угловых точек, но отправляется на следующий этап (проверка пересечения ребра и ребра) для проверки на блокировку. Все другие ребра (черные) с одной или обеими конечными точками за пределами ограничивающей окружности, имеющие подходящие (красные) точки пересечения помечаются как блокирующие, а точки пересечения — как угловые точки Каждое такое ребро соответствует одному из пунктов 4, 6, 9 или 10 в Таблице 1.

3.2.2 Пересечение ребра и ребра сектора

Для пунктов 7 и 8, которые ни разу не проходили предыдущую проверку и для пунктов (6, 9 и 10), проходивших проверку, не обнаружившую точек пересечения, на ребре не может быть угловых точек. Обе его конечные точки не находятся внутри сектора, и на дуге не лежат новые угловые точки. Однако такие ребра нельзя отбрасывать, потому что они все равно могут блокировать (см. Рис. 8) или не блокировать (см. Рис. 10; ребро с сиреневой конечной точкой). У нас есть два варианта: подстраховаться и пометить их как блокирующие или для уверенности проверить их на пересечение с ребрами сектора. Выбрав первый вариант, для каждого ложноположительного непересечения с сектором видимости мы платим проверками пересечения отрезка и отрезка n на этапе испускания лучей, потому что каждый луч проверяется на пересечение с каждой потенциально блокирующим ребром. Вместо того, чтобы расплачиваться n раз за ложноположительные результаты, лучшим вариантом будет потратить n + 2 (в худшем случае). Поэтому мы проверяем ребро на пересечение с обоими ребрами сектора. Если ребро пересекает хотя бы одно из них, мы помечаем его как блокирующее.


Рис. 12

Для пунктов 6-10 на Рис. 12 есть два соответствующих ребра: одно положительное (зеленое), другое отрицательное (красное). Из рисунка очевидно, что эта проверка имеет большую вероятность отбрасывания ребер, несоответствующих видимости.

4 Испускание лучей

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

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

Первичные лучи испускаются в отсортированные угловые точки. Если мы знаем, что точка является конечной точкой ребра, а не точкой пересечения, то необходимо испустить еще и вспомогательные лучи (подробнее см. в разделе 2.2). Вспомогательные лучи испускаются только в угловые точки, являющиеся конечными точками ребер, и не испускаются в точки пересечения, потому что те не могут быть углами полигонов, т.е. видимость не может распространяться дальше них.

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


Рис. 13

На Рис. 13 точки попадания (пронумерованные справа налево) 1 и 2 находятся на дуге, и должны быть соединены дугой. То же самое в случае с точками попадания 3 и 4. Однако точки попадания 2 и 3 должны быть соединены отрезком, потому что есть ребро, пересекающее дугу. При обнаружении точки попадания 3 и подтверждении того, что она и предыдущая точка попадания находятся на дуге, перед соединением их дугой нужно проверить, параллельна ли соединяющая их линия ближайшему ребру, на котором лежит точка попадания 3. Соединить их отрезком, если они параллельны.

5 Линия взгляда

Запрос линии взгляда необходим для ответа на вопрос, видима ли определенная точка мира X для наблюдателя при заданных параметрах наблюдателя (см. раздел 1). После нахождения блокирующих ребер и угловых точек сделать это просто. Сначала мы классифицируем X согласно разделу 3.1.1.2. Если точка не внутри сектора, мы возвращаем false. Если она внутри, мы проверяем, пересекает ли какое-нибудь из блокирующих ребер отрезок, образованный соединением X с наблюдателем. Если он не пересекает, мы возвращаем true, потому что линии взгляда или лучу от наблюдателя к объекту ничего не препятствует. Соответственно, объект видим.

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