Построение 2D Shadows обрезаемых прямоугольником.

[moka]

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

Построение двух мерных теней, ограниченных прямоугольником, от линий.
Фокус был пока на твёрдые тени.

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


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


1. Самый простой вариант, caster отбрасывает тень на одну из граней. 2 триангла.
2. Caster бросает тень на угол. Посредственная точка нужна для избежания артефакта где образуется "дырка", между 2, 3 и 4 вершинами. 3 триангла.
3. Caster бросает тень на 2 противоположные стороны, и полностью охватывает одну из сторон прямоугольника. Это очень популярный случай, когда источник света близок к отрезку. 4 триангла.


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


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


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


4. Также весьма редкий сценарий, но будет "популярен" в indoor условиях. Тень полностью охватывает 2 грани прямоугольника и три вершины. 4 триангла.


Теперь рассмотрим последний сценарий, когда вершины отрезка находятся вне прямоугольника, но отрезок пересекает прямоугольник.


1. Отрезок пересекает две грани, которые имеют общий угол, и тень отбрасывается на этот угол. 1 триангл.
2. Аналогичный сценарий, но тень отбрасывается в противоположную сторону, охватывая две грани и три вершины прямоугольника. 3 триангла.


3. Самый распространённый вариант, будет популярен в indoor условиях, или при описи больших объектов. Отрезок пересекает две противоположные грани прямоугольника. 2 триангла.

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

Почему мы ограничиваем прямоугольником? Ответ прост: в первую очередь источник света имеет ограниченный радиус, таким образом нам не нужно вычислять тени от отрезков, которые находятся дальше, чем источник света может осветить. Во вторых, эта форма наиболее простая, нежели более сложные, такие как окружность, что в конечном итоге была бы многогранной формой похожей на окружность. Это бы привело к более сложным вычислениям и большому полигонажу теней при пересечении с гранями.
Также мы обсуждаем прямоугольник а не квадрат, что могло бы показаться более подходящей формой в описи окружности (источник света с радиусом), потому что дальнейшие оптимизации могут быть применены. Во первых, вычислять тени нужно только те что попадают в экран, таким образом прямоугольник не должен заходить за грани экрана. Также например в сценарии 4 из первого типа отрезков, можно передвинуть верхнюю и левую грани на границу что граничит со второй и шестой вершинами. Также сценарий 3, второй тип, можно передвинуть левую грань прямоугольника. А в типе 3, сценарий 3, будет ещё больше перемещение. Ну и т.п. оптимизации, которые будут весьма уместны, если вычисление теней будет производиться начиная от самых близких отрезков, таким образом многие отрезки будут отсечены перемещением граней на основе уже вычисленных теней. Т.к. тут не обсуждается алгоритм сортировки и вычисления "видимых" отрезков с учётом загораживания.

Тут описывалось построение "твёрдых" теней, при построении мягких теней, будет необходимость дополнительных трианглов от вершин отрезков, что ведёт ещё к вычислениям и учёту сценариев.

[pax]

Статья интересная, но рассмотрен слишком простой вариант - препятствие отрезок. Все будет не так просто, если вместо отрезка будет произвольная не выпуклая фигура.

[moka]

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

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

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