Как рассчитывают освещение и тени 3d движки?

Question

[Даниил]

К примеру карта км на км, и 100ни объектов, и однин источник света где-то в 100 на 100 метров области на карте( где всего объектов 10), как движки считают освещёние и видимость объекта (перегораживают ли его), этот источник света и все другие 100 бессмысленных объектов обходит???
Знаю про метод конкурирующих точек, но не пойму каким образом эти лучи определяющие видимость могут знать что в определенной точке пространства есть объект, если только не каждый из 100 объектов по каждой стороне проверять?

Answer 1

[Станислав Макаров]

этот источник света и все другие 100 бессмысленных объектов обходит???

Матчасть: https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D... . Это не сколько про тени, сколько про вопрос обхода "бессмысленных объектов".

Comments

[Даниил]

Есть еще вопрос, как по точкам построить контур, вроде что то знаю, но опять же лучше 0(n*n) не могу получить.

К примеру любой отображаемый объект, должен унаследовать класс Component, и реализовать метод getPoints() который вернет точки, и их уже надо соединить как то(читал про очень похожие метод как вот вы мне скинули за что спасибо большое).

[Станислав Макаров]

@daniil14056

как по точкам построить контур

Нужно конкретнее, пока не понимаю. Вам нужно соединить входное множество точек на плоскости непересекающимися отрезками?

[Даниил]

да, именно не пересекающими

Answer 2

[rPman]

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

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

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

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

Answer 3

[Deniskin Rediskin]

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

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

Но это прямые тени от источника света, кроме них есть еще и глобальное освещение (затенение), SSAO, реализуемое анализом карты глубин текущего кадра (в 2D пространстве кадра, что довольно быстро).

Более подробно, наверное, можно нагуглить таким образом:
по первому пункту: octree scene graphs, frustum culling, occlusion culling,
об освещении: shadow buffers, SSAO.