HLFX.Ru Forum - Сплющить BSP-дерево в список

Показать все 20 сообщений этой темы на одной странице

HLFX.Ru Forum (https://hlfx.ru/forum/index.php)
- Флуд (https://hlfx.ru/forum/forumdisplay.php?forumid=11)
-- Сплющить BSP-дерево в список (https://hlfx.ru/forum/showthread.php?threadid=4123)

Отправлено nemyax 11-10-2013 в 13:24:

Сплющить BSP-дерево в список

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

code:
        1
       / \
      /   \
nil--2     3--nil
    /       \
   /         \
 nil          4

Отправлено XaeroX 11-10-2013 в 13:28:

Обходишь дерево в нужном порядке и перевязываешь ноды в динамический список. В чём проблема-то?

Цитата:

nemyax писал:
Например, какой список получился бы из такого дерева?

Зависит от способа обхода дерева.

__________________

Отправлено nemyax 11-10-2013 в 13:37:

Цитата:

XaeroX писал:
Зависит от способа обхода дерева.

Ну а какой алгоритм обычно юзают в подобном случае?

Отправлено XaeroX 11-10-2013 в 14:23:

Для отрисовки обычно обходят от ближних к дальним.
Если на твоей картинке ближние слева, а дальние справа, то список будет таким:
nil-2-nil-4-nil-3-1

__________________

Отправлено Дядя Миша 11-10-2013 в 16:01:

Цитата:

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

Да хардварным рендерерам как бы пливать на порядок отрисовки, они всё равно через depth-buffer определяют что поверх чего рисовать. Это для софтварного такая полезная оптимизация была.
А вообще при наличии BSP-дерева всегда существует способ его не использовать. BSP - это как каталог в библиотеке, который позволяет быстро найти искомое в несколько шагов. Но никто ж тебе не запретит перешерстить библиотеку пошагово для достижения той же цели.
Вот только зачем?

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено nemyax 11-10-2013 в 16:29:

Цитата:

Дядя Миша писал:
Да хардварным рендерерам как бы пливать на порядок отрисовки, они всё равно через depth-buffer определяют что поверх чего рисовать.

Ну тут попался особо ламирский хардварный рендерер: Dark Engine.

Отправлено Дядя Миша 11-10-2013 в 17:15:

Ух ты с сорсами Будем поизучать.

Добавлено 11-10-2013 в 21:15:

Да не, ерунда какая-то.
Ну вот это что такое?

C++ Source Code:

1	typedef struct JointInfo {

2	short num_polys; /// Number of polygons

3	short start_poly; /// Start poly

4	short num_vertices; /// Number of vertices

5	short start_vertex; /// Start vertex

6	float jflt; /// I suppose this is a blending factor for the bone

7	short sh6; /// Flag (?) - there are few places for TG this is not zero, but either 1,2 or 3

8	short mapper_id; /// ID of the mapper struct

9	} AIJointInfo;

Кто же привязывает полигоны к костям?

Это каждый вертекс должен знать, к какой кости он принадлежит, а не наоборот.

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено nemyax 11-10-2013 в 18:45:

Дядя Миша
Не, это ж ты про OPDE. А я про оригинал:
www.southquarter.com/thief_2_service_release.7z
Вернее про то, что с ним сделали крайне анонимные погромисты после утечки.

Отправлено Дядя Миша 11-10-2013 в 19:01:

Кадаж уже голдсорс размякнет и утечёт?
Уже у всех всё утекло, а тут ничего подобного.

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено Government-Man 12-10-2013 в 02:20:

Цитата:

Отрисовка полигонов поверх уже отрисованных - пустая трата ресурсов. Ну конечно для древних движков, вроде Source Engine, это не имеет значения - там можно хоть всю карту рисовать, не заботясь ни о порядке отрисовки (за исключением конечно прозрачности), ни об удалении невидимых частей. Но для всяких Крузисов, с многомегабайтными пиксельными шейдерами и километровыми пейзажами, это может быть критично.

Отправлено Дядя Миша 12-10-2013 в 06:41:

В Сорсе оно и так уже отсортировано через дерево.

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено ONeiLL 12-10-2013 в 08:07:

Обычная топологическая сортировка. Делается поиском в глубину
http://ru.wikipedia.org/wiki/%D0%9F...%B8%D0%BD%D1%83

Добавлено 12-10-2013 в 11:07:

Псевдокод

C++ Source Code:

1	void dfs( CNode *node )

3	List.push_back( node );

4	dfs( node->left );

5	dfs( node->right );

Только всунешь проверку, есть ли у ноды дети

Отправлено nemyax 12-10-2013 в 08:39:

Спасибо за ответы. Я всё надеялся, что пронесёт и не придётся говнокодить bsp-резак, а получится обойтись какой-нибудь примитивной недосортировкой. Но по ходу дела надо действительно строить дерево. Как я это буду делать петоном без рекурсии, хрен его знает =(

Отправлено XaeroX 12-10-2013 в 09:27:

Цитата:

nemyax писал:
Как я это буду делать петоном без рекурсии, хрен его знает

Любую рекурсию можно заменить итерацией.

__________________

Отправлено nemyax 12-10-2013 в 09:42:

Конечно можно, но сколько возни. Где-нибудь в ерланге положил сверху паттернов да насовал снизу самовызовов — вот тебе и дерево. А тут ещё в голову думать.

Отправлено Дядя Миша 12-10-2013 в 13:10:

nemyax делаешь BSP-дерево с одним листом и ога.

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Отправлено XaeroX 12-10-2013 в 13:14:

nemyax
Я, видимо, так и не уловил суть - для чего ты это делаешь.
Ты хочешь нарисовать модельку, которая хранится в виде двоичного дерева?
Ну так и рисуй, обходя дерево. Хоть с рекурсией, хоть с итерацией - оба варианта довольно просто реализуются.

__________________

Отправлено nemyax 12-10-2013 в 13:53:

XaeroX
Я делаю экспорт из блендера в ихний формат статик-мешей .bin. Пока на объекте нет текстуры с альфа-каналом, всё рендерится нормально с тем порядком фейсов, который был в блендере. Но если такую текстуру подключить, начинаются проблемы с сортировкой по глубине.
По-старинке люди гонят меши в этот формат через утилиту bsp.exe, которая делает понятно что. Если импортировать такой бин в блендер и экспортировать заново (Дядя Миша, именно откашляв всё в одну ноду), то там всё сортируется корректно. Я поэтому и сделал вывод, что достаточно дать фейсы в ожидаемом порядке.
По сути в блендере мне требуется только переиндексировать фейсы. Но без дерева это вряд ли получится. Или получится?

Отправлено XaeroX 12-10-2013 в 14:38:

Цитата:

nemyax писал:
По сути в блендере мне требуется только переиндексировать фейсы. Но без дерева это вряд ли получится. Или получится?

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

В принципе, и карты под хл1 компилировать в уме можно, а потом сразу нужные байты в бсп-файл вписывать.

__________________

Отправлено Дядя Миша 12-10-2013 в 14:55:

Цитата:

XaeroX писал:
В принципе, и карты под хл1 компилировать в уме можно, а потом сразу нужные байты в бсп-файл вписывать.

И компакт диск можно не слушать, а самому спеть

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Цитата:

C:\DOCUME~1\C4C5~1\LOCALS~1\Temp\a33328if(72) : see declaration of 'size_t'

Временная зона GMT. Текущее время 19:42.

Показать все 20 сообщений этой темы на одной странице

На основе vBulletin версии 2.3.0
Авторское право © Jelsoft Enterprises Limited 2000 - 2002.
Дизайн и программирование: Crystice Softworks © 2005 - 2024