Войти
ПрограммированиеФорумОбщее

Введение в BSP деревья или BSP для самых «маленьких». Часть первая, теоретическая. (Комментарии к статье) (3 стр)

Страницы: 1 2 3 4 5 6 7 Следующая »
#30
0:05, 12 мая 2004

capgreen
>"Функция cp() вычисляет скалярное произведение векторов" - видимо имелосm в
>виду векторное произведение, судя по коду функции cp()

закрался злобный очепятк...


#31
21:38, 12 мая 2004

jm
Насчёт соавторства.
Как тут у вас статьи публикуют : через что, через кого ? Я думаю, к 24.05.04 всё будет готово.

#32
1:08, 13 мая 2004

Zloy
Через меня. Но если вы что-то согласовываете на пару, то сперва сами объединяйте текст, а потом уже мне засылайте.

#33
10:43, 13 мая 2004

jm
>> ...некоторые источники в Интернет анализировавшие код украденной альфа версии Дум 3 предполагают...

Речь идет о исполняемом коде или исходниках?

#34
18:34, 13 мая 2004

jm
Есть ещё один вопрос по поводу статьи:
На второй странице фраза:

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

Имеется ввиду, что в процессе построения дерева баллы для каждого полигона на своём подмножестве не пересчитываются ?

#35
19:12, 13 мая 2004

Zloy

То что  ты сейчас заметил - это NP-полная задача. Известный метод - это брутальный перебор. Как думаешь, на сколько месяцев ? ... если пространство хоть сколь-нибудь большое классифицируется.  Есть метод ветвей и границ (спасибо IronPeter, он мне подсказал), который _может_ помочь _более_ оптимально сделать разбиение, но и это не панацея.

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

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

#36
20:10, 13 мая 2004

Практически, greedy почти ничем не уступает другим методам. Дебалансировать удастся только синтетическим тестом, а количество сплитов регулируется.

#37
22:01, 13 мая 2004

Одного не понимаю:
Для Leaf BSP и просто BSP Z-Buffer для прорисовки уровня не нужен, но как тогда прорисовывать персонажей?

#38
8:22, 14 мая 2004

Padawan
Задача-то, конечно, NP-полная, но только до тех пор, пока к её оптимизации не приложить голову. Я здесь, к сожалению, не смогу описать метод, который я применяю, но разговор про месяцы - это точно перебор, максимум часы :)

Чуть не забыл, если не жалко, дайте, пожалуйста, нормальный линк на greedy-метод.

#39
22:20, 14 мая 2004

FLashM
По поводу прорисовки персонажей - их можно вставлять в дерево (то бишь в листы), спускать то есть, а не просто вставлять. Путаница возникает, когда bbox персонажа пересекается каким-нибудь сплиттером. Вобщем, вынесу эту тему в общий форум, дабы не сорить где попало.
Ну а в целом - динамика в BSP - это тема для отдельной статьи.

#40
23:45, 14 мая 2004

2Zloy
Это чтож получается? Для каждой картинки приходится немного перестраивать дерево?

#41
23:49, 14 мая 2004

FLashM
Нет, фишка не в этом - в каждом кадре нужно персонажа опускать в лист. Но на практике он будет находиться в нескольких листах. Так вот - рендерить его надо с использованием z-buffer'а в том листе, в котором он при рендеринге BSP-дерева появляется в последний раз.

#42
8:34, 15 мая 2004

Хочу вот спросить, многоуважаемую аудиторию. Кто-нибудь действительно делал BSP-компилятор? Полностью и до конца.
А то я бьюсь с одной проблемкой и никак решить не могу. Вот в статье написано:
В этом случае полигон нужно "распилить", чем и займется функция Split_Polygon(). Реализация этой функции будет домашним заданием читателю.
Чесно говоря, я другого увидель и не ожидал. И я НИГДЕ в И-нете не нашел реализации этой функции (хотя я долго не искал, правда).
Короче. Представьте есть пятиугольник. Делящая плоскость проходит ЧЕРЕЗ ЕГО 1-Ю И 4-Ю вершину. Вершины хранятся в массиве, а полигоны (которые нужно растолкать по BSP и при необходимости распилить -- списки индексов вершин).
У меня вначале был глюк: данный пятиугольник делился на 4-х-угольник и пятиугольник (как точно не помню), да это не важно, вобщем НЕ НА 3-х и 4-х угольники. А суть в том что создавалась новая вершина (такая же как и 1-я, но с другим индексом) И у первого 4-угольника у первой стороны НАЧАЛО И КОНЕЦ БЫЛИ ОДНОЙ ВЕРШИНОЙ (хотя индексы вершин разные, но позиция одна и та же). Вроде бы ничего страшного -- рендерится чуть дольше будет и места занимать, НО при дальнейшем создании BSP-дерева, КОГДА ЭТОТ 4-УГОЛЬНИК ВЫСТУПАЕТ В КАЧЕСТВЕ ДЕЛЯЩЕЙ ПЛОСКОСТИ нормаль его найти..конечно можно, но.... В обще проблема я думаю ясна.
Да и вот что. Этот глюк я исправил, усложнив ф-ю деления полигонов, но где-то остался еще какой-то глюк, при котором полсцены иногда просто "откусывается". Вот его-то я победить так и не смог.

#43
11:58, 15 мая 2004

tav, код этой функции находится в BSP FAQ, том же откуда jm взял код рендеринга BSP.
Поищи немножко и найдешь. Просто функция довольно большая и jm наверное решил не приводить её в этой части статьи.

#44
14:06, 15 мая 2004

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

Страницы: 1 2 3 4 5 6 7 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.