HLFX.Ru Forum
профиль •  правила •  регистрация •  календарь •  народ •  FAQ •  поиск •  новое •  сутки •  главная •  выход  
HLFX.Ru Forum HLFX.Ru Forum > Наш форум > Флуд > Сплющить BSP-дерево в список
Страницы (2): [1] 2 »   Предыдущая тема   Следующая тема
Автор
Тема Новая тема    Ответить
nemyax
Нёмыч

Дата регистрации: Jul 2011
Проживает: (void)
Сообщений: 4242

Рейтинг



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

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

code:

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

Сообщить модератору | IP: Записан
Сообщение: 126016
Старое сообщение 11-10-2013 13:24
- За что?
 XaeroX
Crystice Softworks

Дата регистрации: Oct 2005
Проживает: Торонто
Сообщений: 35062
Нанёс повреждений: 514 ед.
Возраст: 39

Рейтинг



Награды
 
[1 награда]

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

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

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

__________________

Сообщить модератору | IP: Записан
Сообщение: 126017
Старое сообщение 11-10-2013 13:28
-
nemyax
Нёмыч

Дата регистрации: Jul 2011
Проживает: (void)
Сообщений: 4242

Рейтинг

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

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

Сообщить модератору | IP: Записан
Сообщение: 126018
Старое сообщение 11-10-2013 13:37
- За что?
 XaeroX
Crystice Softworks

Дата регистрации: Oct 2005
Проживает: Торонто
Сообщений: 35062
Нанёс повреждений: 514 ед.
Возраст: 39

Рейтинг



Награды
 
[1 награда]

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

__________________

Сообщить модератору | IP: Записан
Сообщение: 126019
Старое сообщение 11-10-2013 14:23
-
 Дядя Миша
racing for fish

Дата регистрации: Oct 2005
Проживает: Кубань
Сообщений: 33064
Нанёс повреждений: 392 ед.

Рейтинг

Цитата:
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'

Сообщить модератору | IP: Записан
Сообщение: 126023
Старое сообщение 11-10-2013 16:01
-
nemyax
Нёмыч

Дата регистрации: Jul 2011
Проживает: (void)
Сообщений: 4242

Рейтинг

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

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

Сообщить модератору | IP: Записан
Сообщение: 126024
Старое сообщение 11-10-2013 16:29
- За что?
 Дядя Миша
racing for fish

Дата регистрации: Oct 2005
Проживает: Кубань
Сообщений: 33064
Нанёс повреждений: 392 ед.

Рейтинг

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

Добавлено 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'

Сообщить модератору | IP: Записан
Сообщение: 126025
Старое сообщение 11-10-2013 17:15
-
nemyax
Нёмыч

Дата регистрации: Jul 2011
Проживает: (void)
Сообщений: 4242

Рейтинг

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

Сообщить модератору | IP: Записан
Сообщение: 126028
Старое сообщение 11-10-2013 18:45
- За что?
 Дядя Миша
racing for fish

Дата регистрации: Oct 2005
Проживает: Кубань
Сообщений: 33064
Нанёс повреждений: 392 ед.

Рейтинг

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

__________________
My Projects: download page

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

Цитата:

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

Сообщить модератору | IP: Записан
Сообщение: 126029
Старое сообщение 11-10-2013 19:01
-
Government-Man
Призрак

Дата регистрации: Apr 2006
Проживает: N/A
Сообщений: 3507

Рейтинг



Награды
 
[1 награда]

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


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

Сообщить модератору | IP: Записан
Сообщение: 126036
Старое сообщение 12-10-2013 02:20
- За что?
 Дядя Миша
racing for fish

Дата регистрации: Oct 2005
Проживает: Кубань
Сообщений: 33064
Нанёс повреждений: 392 ед.

Рейтинг

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

__________________
My Projects: download page

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

Цитата:

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

Сообщить модератору | IP: Записан
Сообщение: 126038
Старое сообщение 12-10-2013 06:41
-
ONeiLL
CrazyUkrainian

Дата регистрации: Dec 2011
Проживает: Украина, Житомир
Сообщений: 562
Возраст: 27

Рейтинг

Обычная топологическая сортировка. Делается поиском в глубину
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 )
2
{
3
  List.push_back( node );
4
  dfs( node->left );
5
  dfs( node->right );
6
}


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

Сообщить модератору | IP: Записан
Сообщение: 126040
Старое сообщение 12-10-2013 08:07
- За что?
nemyax
Нёмыч

Дата регистрации: Jul 2011
Проживает: (void)
Сообщений: 4242

Рейтинг

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

Сообщить модератору | IP: Записан
Сообщение: 126041
Старое сообщение 12-10-2013 08:39
- За что?
 XaeroX
Crystice Softworks

Дата регистрации: Oct 2005
Проживает: Торонто
Сообщений: 35062
Нанёс повреждений: 514 ед.
Возраст: 39

Рейтинг



Награды
 
[1 награда]

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

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

__________________

Сообщить модератору | IP: Записан
Сообщение: 126042
Старое сообщение 12-10-2013 09:27
-
nemyax
Нёмыч

Дата регистрации: Jul 2011
Проживает: (void)
Сообщений: 4242

Рейтинг

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

Сообщить модератору | IP: Записан
Сообщение: 126043
Старое сообщение 12-10-2013 09:42
- За что?
Тема: (Опционально)
Ваш ответ:



Переводчик транслита

[проверить длину сообщения]
Опции: Автоматическое формирование ссылок: автоматически добавлять [url] и [/url] вокруг интернет адресов.
Уведомление по E-Mail: отправить вам уведомление, если кто-то ответил в тему (только для зарегистрированных пользователей).
Отключить смайлики в сообщении: не преобразовывать текстовые смайлики в картинки.
Показать подпись: добавить вашу подпись в конец сообщения (только зарегистрированные пользователи могут иметь подписи).

Временная зона GMT. Текущее время 21:49. Новая тема    Ответить
Страницы (2): [1] 2 »   Предыдущая тема   Следующая тема
HLFX.Ru Forum HLFX.Ru Forum > Наш форум > Флуд > Сплющить BSP-дерево в список
Версия для печати | Отправить тему по E-Mail | Подписаться на эту тему

Быстрый переход:
Оцените эту тему:

Правила Форума:
Вы not можете создавать новые темы
Вы not можете отвечать в темы
Вы not можете прикреплять вложения
Вы not можете редактировать ваши сообщения 		HTML Код ВЫКЛ
vB Код ВКЛ
Смайлики ВКЛ
[IMG] Код ВКЛ
 

< Обратная связь - HLFX.ru >

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