Проблема с усечением Frustum области другим Frustumом / Графика / Форум / Программирование игр / GameDev.ru

Пишу новый рендер для Build Engine, результаты такие:
https://youtu.be/yHKBdoQ6yi0

Хочу решить проблему с отсечением невидимых областей и практически ее решил, но нет...

Добавление:
В кратце суть проблемы такая:

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

Опишу методы с которыми работаю:

Мой алгоритм состоит из нескольких частей - проверка видимости порталов, проверка видимости остальных стен через порталы, и потом raycast, чтобы отсекать всю невидимую область (самая медленная часть алгоритма, но сейчас не об этом)

На данном этапе решил переписать первую часть алгоритма. Сейчас реализована проверка видимости стен по осям X, Y (т.е. в 2D) с помощью фрустума, состояща из левой и правой поверхности, строится и обрабатывается очень просто:

float x1 = wal.x - globalposx;
float y1 = wal.y - globalposy;
WALL wal2 = wall[wal.point2];
float x2 = wal2.x - globalposx;
float y2 = wal2.y - globalposy;

setPlane(0, x1, y1, 0); // left
setPlane(1, -x2, -y2, 0); // right

где globalposx, y - это положение камеры
wal.x, y - первая точка стены (портала)
wal2 - вторая точка стены

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

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

Еще одним нюансом является отсечение фрустума с помощью проверяемого фрустума. Метод получился довольно громоздким, основан на dot-продуктах нормали одной поверхности фрустума с направлением противоположной поверхности фрустума (в итоге, вроде бы получается cross-продукт двух нормалей противоположных поверхностей)

Основан на различных проверка этих формул

// frustum left testPoint by plane right
    float dot1 = planes[1].normal.x * frustum.planes[0].normal.y - planes[1].normal.y * frustum.planes[0].normal.x;
    // frustum right testPoint by plane left
    float dot2 = planes[0].normal.y * frustum.planes[1].normal.x - planes[0].normal.x * frustum.planes[1].normal.y;
    // frustum left testPoint by plane left
    float dot3 = planes[0].normal.x * frustum.planes[0].normal.y - planes[0].normal.y * frustum.planes[0].normal.x;
    // frustum right testPoint by plane right
    float dot4 = planes[1].normal.y * frustum.planes[1].normal.x - planes[1].normal.x * frustum.planes[1].normal.y;

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

Верхнюю и нижнюю поверхность строю так:

int dx = wal2.x - wal.x;
    int dy = wal2.y - wal.y;
    float z3 = x1 * dy - y1 * dx;

    float nz = (cz - globalposz) / 16.0f;
    setPlane(2, nz * dx, nz * dy, z3); // up

    nz = (fz - globalposz) / 16.0f;
    setPlane(3, -nz * dx, -nz * dy, -z3); // down

fz и cz - это высота пола и потолка сектора, по-сути Z координаты точек стены (портала)

На этом этапе расчеты пеерходят в 3D...

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

формулы подобно этим тут уже не работают

float dotv1 = planes[3].normal.x * frustum.planes[2].normal.x - planes[3].normal.y * frustum.planes[2].normal.z
        + planes[3].normal.z * frustum.planes[2].normal.y;

float dotv2 = planes[2].normal.x * frustum.planes[3].normal.x + planes[2].normal.y * frustum.planes[3].normal.z
        - planes[2].normal.z * frustum.planes[3].normal.y;

Например в 2D, если dot1 и dot2 отрицательный, значит проверяемый фрустум находятся вне поле видения проверяющего фрустума и там это условие работает всегда.

Но в 3D...я начал писать таки проверки и они даже умудрялись работать...до тех пор пока я не развернул камеру на 180 градусов....и вроде бы оба фрустума находятся в одном направлении и знаки у их компонентов одинаковые, но значения dot1 и dot2 инвертируются, т.е. уже где-то нужно учитывать dx и dy между камерой и порталом.

И на выходе получается такая дичь

На картинке представлен сектор с порталом, портал смотрит на кучу маленьких секторов-кубиков.

Вот так этот баг выглядит сверху

Если убрать клипирование по Z поверхностям, то все рисуется как надо, ну и соответственно алгоритм определяет самую дальнуюю стену, которую по факту не видно

Хочу добить этот алгоритм до-конца, помогите :)

GLoom
Постоялец

#1
13:54, 8 дек 2020

Я правильно понимаю что тебе надо построить отсекающую фигуру (я не уверен что всегда будет получаться frustum) которая была бы пересечением объёма двух frustum'ов (текущего и образованного порталом)?

В вопросе много математики специфичной для твоего проекта и без остального кода проекта в этом сложно разбираться. Например почему у тебя там деление на 16 вдруг откуда то не понятно.

0xc0de
Постоялец

#2
14:04, 8 дек 2020

Самое простое это получить экранные координаты вершин портала, построить по ним 2d aabb и клипать прямоугольники. Затем по ребрам прямоугольника строить фрустум портала.

Можно сделать сложнее - если портал выпуклый многоугольник, то порезать его плоскостями текущего фрустума. По ребрам полученного нового выпуклого прямоугольника построить новый фрустум.

При проходе по порталам завести стековую структуру.

m210
Постоялец

#3
15:33, 8 дек 2020

m210
> В вопросе много математики специфичной для твоего проекта и без остального кода
> проекта в этом сложно разбираться. Например почему у тебя там деление на 16
> вдруг откуда то не понятно.

Математики действительно много, но конктрено, отсящейся к верхним и нижним плоскостям фрустума - нет вообще, потому что не получается. На деление на 16 не обращай внимания, это особенность движка Build Engine, 16 - это масштаб по высоте, т.е. чтобы построить куб 1х1х1 и он выглядел как куб, в мировых координатах движка будет что-то типа 16х16х1.

0xc0de
> Самое простое это получить экранные координаты вершин портала, построить по ним
> 2d aabb и клипать прямоугольники. Затем по ребрам прямоугольника строить
> фрустум портала.

Сначала я так и делал, и это тоже хорошо и быстро работает, пока не наткнулся на подобные косяки - берюзовая дыра:

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

0xc0de
> Можно сделать сложнее - если портал выпуклый многоугольник, то порезать его
> плоскостями текущего фрустума. По ребрам полученного нового выпуклого
> прямоугольника построить новый фрустум.

Я сейчас как раз и пытаюсь это сделать (надеюсь это не будет сильно медленно)
Задачу облегчает то, что порталы всегда имеют 4 вершины - квадраты и прямоугольники.

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

А есть ли какой-нить пример, как резать 4-вершинный полигон 4мя плоскостями?

Еще расскажу про упрощения движка и на чем основаны мои алгоритмы
1. Порталы имеют всегда 4 вершины
2. Фрустум порталов всегда смотрят вперед (поэтому нет неободимости мудрить с наклоном)

Я проводил очень много опытов и могу точно сказать, что определить все видимые секторы и стены можно в 2D, видимость не зависит от того, куда смотрит камера - вверх, вниз или куда-то еще, на этом и основана вся моя математика.

Mirrel
Постоялец

#4
22:29, 8 дек 2020

почему не glScissor? При прорисовке каких-то вырезаемых объёмов?

Aroch
Постоялец

#5
22:58, 8 дек 2020

Mirrel
потому что между:
подать на отрисовку и не отрисовать в результате, и
не подать на отрисовку,
две большие разницы.

не учитывая что scissor это пряоугольная область только.

Mirrel
Постоялец

#6
23:03, 8 дек 2020

Aroch, в данном случае я вижу вырезание из плоскости(стена - две плоскости). Что быстрее сделает видеокарта. Не совсем убедительный ответ. Вырезать можно так же по трафарету (насколько мне память не изменяет).

походу изменяет, не вижу ни где вырезку по трафарету

А каждый раз, когда надо будет сделать окно, городить тонну кода, который не факт, что будет быстрее работать... такое себе занятие.

Я пойму подобное поведение, когда в кадр вообще не попадает фигура.

Mirrel
Постоялец

#7
23:28, 8 дек 2020

Так, нашёл. "OpenGL Суперкнига", Рост, стр. 157. glStencilFunc и сопутствующие.
Конечно там устаревшая информация, не знаю, работает с шейдерами или нет.

В интернете есть примеры, как я понимаю с шейдерами.

Aroch
Постоялец

#8
0:44, 9 дек 2020

Mirrel
еще раз ты говоришь об отсечении на этапе отрисовки (можно и тупо в лоб рисовать и z-buffer сделает своё дело), речь же о том чтобы не доводить до отрисовки совсем.

Mirrel
Постоялец

#9
2:23, 9 дек 2020

Aroch, я о том, что видеокарта занимается подобными вещами быстрее, чем если этим будет заниматься основной процессор.

san
Постоялец

#10
8:37, 9 дек 2020

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

Hartmann
Постоялец

#11
9:16, 9 дек 2020

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

ssa1973
Постоялец

#12
9:38, 9 дек 2020

Алгоритм Сазерленда-Ходжмана режет порталы. Но надо учитывать, что из 4-х угольника, после резки, может получиться пятиугольник.

m210
Постоялец

#13
9:54, 9 дек 2020

san
> Драйвер за тебя все отбракует в лучшем виде.
Постоянно читаю подобные ошибочные представления о всемогучести видеокарт...ну смотрите:

Комп на работе (на месте моей работы всмысле) - Celeron J4100

Рендер всей карты: 18fps
Screenshot_20201209_094509 | Проблема с усечением Frustum области другим Frustumом
Рендер с расчетом видимости: 502fps
Screenshot_20201209_093532 | Проблема с усечением Frustum области другим Frustumом

Расчет видимости занимает 0.05мс

Вот другая карта - чтото типа стрестеста, 3000 секторов и значит около 9000 порталов
Моя реализация на Java дает 17fps, расчет видимости занимает 4мс. Если отключить расчет видимости в этом месте, то я получу 18fps вместо 17...т.е. проверка не то чтобы нужна, а необходима.
Screenshot_20201209_093813 | Проблема с усечением Frustum области другим Frustumом

А вот так выглядит eDuke32 (на С++) с рендером Polymer, где применена технология occlusion query, всемогущая видеокарта показывает 7.5fps
Screenshot_20201209_093958 | Проблема с усечением Frustum области другим Frustumом

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

Hartmann
> здесь есть статья на эту тему, там даже код есть как резать портал и как его
> строить новый
> для резки полигона используется алгоритм сазерленда-ходжмана

Да, я ее читал, фрустумы я строю практически также как и в статье, попробую применить обрезку из статьи

glStencilFunc и glScissors это все не то

ssa1973
Постоялец

#14
9:56, 9 дек 2020

//-------------Алгоритм Сазерленда-Ходжмана----------
BOOL ENGCLIP::Sazerlend(ENGPOLIGON* poligon, CONST D3DXVECTOR3* point)
{
UINT temp_count;//кол-во временных вершин
ENGVERTEX* temp_vertex;//временные вершины
FLOAT start_factor;//фактор начала отрезка
FLOAT end_factor;//фактор конца отрезка
ENGVERTEX* end;// указатель на конец отрезка

// цикл отсечения по всем плоскостям
for (UINT i = 0; i<this->countclips; i++)
{
//отсечь плоскостью по алгоритму Сазерленда-Ходжмана
//новый отсеченный полигон
//(может оказаться на 1 вершину больше)
temp_vertex = new ENGVERTEX[poligon->countvertex + 1];
//счетчик вершин попавших в плоскость отсечения
temp_count = 0;
//цикл по всем ребрам полигона
for (UINT j = 0; j<poligon->countvertex; j++)
{
//вычисление фактора начала отрезка
start_factor = D3DXPlaneDotCoord(&this->clips
, &poligon->vertex[j].position);
//определение вершины конца отрезка
if (j + 1 == poligon->countvertex) end = &poligon->vertex[0];
else end = &poligon->vertex[j + 1];
//вычисление фактора конца отрезка
end_factor = D3DXPlaneDotCoord(&this->clips
, &end->position);
//Начало отрезка лежит на плоскости отсечения
if (start_factor == 0.0f)
{
//заносим начало в список вершин нового полигона
temp_vertex[temp_count].position = poligon->vertex[j].position;
temp_count++;//счетчик вершин+1
continue;
}
//начало отрезка попадает в область отсечения
if (start_factor > 0.0f)
{
//заносим начало в список вершин нового полигона
temp_vertex[temp_count].position = poligon->vertex[j].position;
temp_count++;//счетчик вершин+1
//конец отрезка не попадает в область отсечения
// if (end_factor<=0.0f)
if (end_factor < 0.0f)
{
//cчитаем точку пересечения и заносим ее в список вершин
D3DXPlaneIntersectLine(
&temp_vertex[temp_count].position
, &this->clips, &poligon->vertex[j].position
, &end->position);
temp_count++;//счетчик вершин+1
}
}
else
//Начало отрезка не попадает в область отсечения
{

//конец отрезка попадает в область отсечения
if (end_factor>0.0f)
{
//считаем точку пересечения и заносим ее в список вершин
D3DXPlaneIntersectLine(
&temp_vertex[temp_count].position
, &this->clips, &poligon->vertex[j].position
, &end->position);
temp_count++;//счетчик вершин+1
}
}
}
//если меньше трех вершин у отсеченного полигона
if (temp_count<3)
{
delete[] temp_vertex;
return FALSE;
}
//если есть старые вершины стереть их
delete[] poligon->vertex;
//буфер и число вершин отсеченного полигона
poligon->vertex = temp_vertex;
poligon->countvertex = temp_count;
}
return TRUE;
}

Я вот такое реализовал. Только ошибается алгоритм, если порталы имеют общую грань, т.е. соприкасаются сторонами. Не разбирался, отложил...