Про думчик, bsp-деревья и порталы

В Думе сектора — выпуклые многоугольники.

gamedev.ru

Окном ошибся.

О как! Ну для рендеринга bsp всё равно не нужен, или я не прав?

Так что объясните пожалуйста, если уровень не имеет никаких разрывов, сектора - все прямоугольники, то нафиг нужны какие-то BSP деревья, если отсечение невидимых секторов и cd можно сделать и без них?

А что ты предлагаешь вместо них? Полный перебор всего подряд? Так это просто неэффективно.

Ты читал? Я же сказал - лучи пускаешь под определенным углом, и проецируешь на плоскость с картой. Так естественным образом ты отсекаешь лишнее

При рендеринге BSP дерево нужно для эффективного выполнения front-to-back сортировки видимых секторов, и отсечения заведомо невидимых ветвей (находящихся вне поля зрения игрока).

ЕМНИП, рейкастинг требует своего луча для каждой точки. Когда у тебя viewport измеряется в миллионах пикселей, выйдет слайдшоу. Сравни, например, с BSP, которое за O(log n) даёт тебе готовые непересекающиеся многоугольники в экранных координатах, останется натянуть текстуры только. По этой причине Кармак сотоварищи и отказались после wolf3d от рейкастинга.

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

В wolf3d, кстати, рейкастинг проходил всего для 320 вертикальных полос по одному лучу, а текстурирование (в силу фактической двумерности игры) заключалось в отрисовке нужного сканлайна текстуры.

ЕМНИП, рейкастинг требует своего луча для каждой точки

Не-не. они называют это рейтрейсингом. Так получена приложенная картинка.

Про многоугольники не ясно. Они там только вершины многоугольников получают или как? Если только вершины - тогда я могу понять, нафиг BSP нужно - получаем вершины текущего сектора, потом видимых более дальних по дереву. Правда тогда для меня секрет как текстурировать.

Я тут фигнёй воксельно-ландшафтной страдал - вышло 145 fps на 800x600 точек)

ведь в думе уровень поделен на сектора-прямоугольники

нафиг нужны какие-то BSP деревья

Вот как раз при компиляции карты и происходит деление уровня на сектора методом бинарного разделения пространства (Binary Space Partitioning — BSP).

Рейкастинг работает и без секторов

рейтрейсингом

Грамотный рейтрейсинг будет очень долго работать на современных мощностях.

Ну я знаю, как povray работает. Но это смотря что ты называешь грамотным. Я вот ещё всё в сторону вокселей смотрю. Вон как у Кена Сильвермана всё круто и быстро! И он вроде использует рейкастинг. Я, правда, не могу перейти от ландшафтов к наиболее общему 3d. Вот всё, что у меня вышло:

http://pastebin.com/UgRbD7xh

На 800x600 точек - всего 35 fps. Проблема с качеством картинки и определением уже нарисованных точек (это надо знать, чтобы не рисовать лишнее, рисует от ближнего к дальнему).

Картинко:

http://img827.imageshack.us/img827/5937/201208232322331280x1024.png

Я же сказал - лучи пускаешь под определенным углом, и проецируешь на плоскость с картой. Так естественным образом ты отсекаешь лишнее

И по какому алгоритму ты лучи проецируешь на плоскость с картой высот?

Вообще, забудь про 3Д. У тебя есть статичный массив объектов и тебе нужно найти в нём один конкретный объект по какому-то заранее известному признаку. Какой вариант будет быстрее в общем случае: перебор в лоб или спуск по дереву?

Обьясните нубу, какой еще спуск по дереву имеется в виду тут? Для статичного неупорядоченного массива разве есть способы в общем случае работающие быстрее простого перебора?

Для статичного неупорядоченного массива разве есть способы в общем случае работающие быстрее простого перебора?

Из статичного неупорядоченного массива можно заранее построить дерево. В случае 3D, BSP - это один из вариантов организации такого дерева.

И по какому алгоритму ты лучи проецируешь на плоскость с картой высот?

Почитай по рейкастинг.

Какой вариант будет быстрее в общем случае: перебор в лоб или спуск по дереву?

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

И по какому алгоритму ты лучи проецируешь на плоскость с картой высот?

Почитай по рейкастинг.

Ладно, уточню вопрос: как ты находишь пересечение луча с картой высот? Перебираешь все точки в цикле или у тебя всё такие карта как-то заранее организована для ускорения поиска пересечения?

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

Почитай про BSP. И про бинарные деревья.

Почитай про BSP. И про бинарные деревья.

Понятно, ты злой. BSP - способ разбиения пространства на видимые/невидимые части с учётом удаленности, так? И как это ответит на мой вопрос?

Ладно, уточню вопрос: как ты находишь пересечение луча с картой высот? Перебираешь все точки в цикле или у тебя всё такие карта как-то заранее организована для ускорения поиска пересечения?

Ни то, ни это. Луч проецируется на карту высот. Для этого, как правило, надо откинуть координату высоты.

http://www.flipcode.com/archives/Realtime_Voxel_Landscape_Engines-Part_2_Rend...

Тут применительно к картам высот, но можно применить это хоть и к секторам.

Тут применительно к картам высот, но можно применить это хоть и к секторам.

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

То что я реализовал, я знаю как работает, то что нет - не знаю. Не можешь помочь - разговор окончен.

Чтобы тебе было яснее, выдержка из википедии. Там, оказывается, неплохо про дум написано

Start at the root node.
Draw the child nodes of this node recursively. The child node closest to the camera is drawn first using a Scanline algorithm. This can be found from looking at which side of the node's dividing line the camera is on.
When a subsector is reached, draw it.[5]

Соответственно, про этот scanline algorithm мне и надо почитать. Тут товарищь упомянул что-то такое, но я не обратил внимания

Scanline - это алгоритм растеризации треугольников (в основном). К отсечению невидимых объектов он сам по себе отношения почти не имеет.

То что я реализовал, я знаю как работает, то что нет - не знаю.

Сомнительно. Ты пишешь бред. Вот например:

Так вот при этом способе нет какой-то дополнительной нужды отсекать невидимые области. Куда луч не спроецируется - там и не видно.

Это работает, только если у тебя сцена состоит из одного единственного ландшафта. Как только появится что-то ещё - тебе придётся использовать дополнительные алгоритмы. Иначе у тебя поиск пересечения луча со сценой будет перебирать все объекты.

С заслонением объектами друг-друга тоже можно справиться, если запоминать, насколько далеко линия на экране уже зарисована.

А тут ты сам описал простейший алгоритм отсечения. Впрочем, в таком виде он тоже не сильно эффективен.

Зная, в каком секторе мы находимся, мы должны сделать всего 4 операции сравнения (2 для x и 2 для y), чтобы определить, можно ли находиться в данной точке.

Вот у тебя есть координаты игрока (x и y, без высоты). И как ты собрался узнавать «в каком секторе мы находимся»? Перебором, ага? 8)

Ну и так далее, не вижу смысла разбирать.

если они тут есть

тонко

Ты пишешь бред. Вот например:

Или ты не понимаешь

Это работает, только если у тебя сцена состоит из одного единственного ландшафта. Как только появится что-то ещё - тебе придётся использовать дополнительные алгоритмы. Иначе у тебя поиск пересечения луча со сценой будет перебирать все объекты.

А ты не думал, что при рендеринге ландшафт может оказаться самоперекрытиями?

А тут ты сам описал простейший алгоритм отсечения. Впрочем, в таком виде он тоже не сильно эффективен.

Хорошо, описал. Но заметь, как легок этот «алгоритм», что я даже не посчитал его таковым.

Вот у тебя есть координаты игрока (x и y, без высоты). И как ты собрался узнавать «в каком секторе мы находимся»? Перебором, ага? 8)

Можно прилегающие сектора объеденить в сетку. Для каждого запомнить соседей.

Ответь, пожалуйста, вот на что:

После того, как ты выстроил объекты по удалению от камеры, как происходит рендеринг?

После того, как ты выстроил объекты по удалению от камеры, как происходит рендеринг?

Это зависит от того, какие именно объекты и какой используется алгоритм собственно рендеринга.

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

Вообще ты начал с этого:

А что ты предлагаешь вместо них? Полный перебор всего подряд? Так это просто неэффективно.

Если запихать карту уровня (высоты секторов) в массив по x и y («горизонтальным» координатам), то при рейкастинге не нужен перебор «всего подряд». Это отнюдь не бред, и нефиг спорить. Объекты сами выстраиваются по удалению от камера, пока ты идешь по лучу всё дальше

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

В думе вроде этого всего нет. Если начать с простого, есть идеи как быть дальше? Идеи, ключевые слова, ссылки...

Если запихать карту уровня (высоты секторов) в массив по x и y («горизонтальным» координатам), то при рейкастинге не нужен перебор «всего подряд».

Обрати внимание, что «запихать карту уровня (высоты секторов) в массив по x и y» - это уже организация данных, сильно отличающаяся от просто кучи точек (x, y, z).

Если начать с простого, есть идеи как быть дальше? Идеи, ключевые слова, ссылки...

Если у тебя в программе будет что-то кроме одного большого ландшафта, то тебе в любом случае понадобится как-то организовать пространство сцены. Кроме BSP есть и другие структуры. Quadtree или octree (выбор зависит от сцены) например.

Обрати внимание, что «запихать карту уровня (высоты секторов) в массив по x и y» - это уже организация данных, сильно отличающаяся от просто кучи точек (x, y, z).

Согласен, но это само напрашивается, так как в думе можно только высоту пола и потолка указать для сектора. Даже наклона нельзя сделать

А алгоритмы непосредственно рендеринга?

Если запихать карту уровня (высоты секторов) в массив по x и y («горизонтальным» координатам), то при рейкастинге не нужен перебор «всего подряд». Это отнюдь не бред, и нефиг спорить. Объекты сами выстраиваются по удалению от камера, пока ты идешь по лучу всё дальше

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

Вот например с твоей картой высот. Отсечение у тебя происходит дважды:

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

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

Ясно, спасибо. Кстати, я там выкинул исходник на pastebin, где рендерятся простые геометрические фигуры. Там действительно отсечения невидимых граней происходит очень фиговым способом. Для каждого столбца на экране я храню координаты отрезков, которые уже зарисовались. Массивы, в которых это хранится называются minsytop и maxsybottom, если интересно.

Ты, похоже, продолжаешь мыслить вокселями. В Думе и далее пространство - полигонально. Вот примерно так работает отображение:

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

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

Вообще, doom code review и велосипедированием BSP движков не занимался только ленивый, гугли. Целесообразность и область применения BSP тебе уже пояснили. Решай сам, надо оно тебе или ты всё-таки занимаешься воксельными движками с рей(каст|трейс)ингом.

Спасибо за пояснение. Теперь концепция вроде ясна

есть книга про doom, там рассписаны основы BSP дерева и то как они работают в doom, всместе с отсечениями итд, найдите и почитайте вообщем