- wat
- Ведущий
capgreen
>"Функция cp() вычисляет скалярное произведение векторов" - видимо имелосm в
>виду векторное произведение, судя по коду функции cp()
закрался злобный очепятк...
jm
Насчёт соавторства.
Как тут у вас статьи публикуют : через что, через кого ? Я думаю, к 24.05.04 всё будет готово.
Zloy
Через меня. Но если вы что-то согласовываете на пару, то сперва сами объединяйте текст, а потом уже мне засылайте.
jm
>> ...некоторые источники в Интернет анализировавшие код украденной альфа версии Дум 3 предполагают...
Речь идет о исполняемом коде или исходниках?
jm
Есть ещё один вопрос по поводу статьи:
На второй странице фраза:
"Общепринятым способом является последовательный проход по всем потенциальным сплиттер полигонам, и подсчете неких баллов. Причем, мы никоим образом не учитываем дальнейшие попытки разбиения с заново полученными двумя списками входных параметров, а значит, мы не можем гарантировать, что выбор именно этого, на данный момент "оптимального", исходя из наших вычислений, сплиттера, не окажет негативное влияние на построение дерева в дальнейшем."
Имеется ввиду, что в процессе построения дерева баллы для каждого полигона на своём подмножестве не пересчитываются ?
Zloy
То что ты сейчас заметил - это NP-полная задача. Известный метод - это брутальный перебор. Как думаешь, на сколько месяцев ? ... если пространство хоть сколь-нибудь большое классифицируется. Есть метод ветвей и границ (спасибо IronPeter, он мне подсказал), который _может_ помочь _более_ оптимально сделать разбиение, но и это не панацея.
А вообще, даже если влияние и будет негативным, то негативность эта имеет свойство разрежаться, если не планируется целиком рисовать уровень за раз.
Можно попробовать удариться во введение оценочных функций, благодаря которым проводить ту или иную сортировку, после чего только делать разбиение.
Практически, greedy почти ничем не уступает другим методам. Дебалансировать удастся только синтетическим тестом, а количество сплитов регулируется.
Одного не понимаю:
Для Leaf BSP и просто BSP Z-Buffer для прорисовки уровня не нужен, но как тогда прорисовывать персонажей?
Padawan
Задача-то, конечно, NP-полная, но только до тех пор, пока к её оптимизации не приложить голову. Я здесь, к сожалению, не смогу описать метод, который я применяю, но разговор про месяцы - это точно перебор, максимум часы :)
Чуть не забыл, если не жалко, дайте, пожалуйста, нормальный линк на greedy-метод.
FLashM
По поводу прорисовки персонажей - их можно вставлять в дерево (то бишь в листы), спускать то есть, а не просто вставлять. Путаница возникает, когда bbox персонажа пересекается каким-нибудь сплиттером. Вобщем, вынесу эту тему в общий форум, дабы не сорить где попало.
Ну а в целом - динамика в BSP - это тема для отдельной статьи.
2Zloy
Это чтож получается? Для каждой картинки приходится немного перестраивать дерево?
FLashM
Нет, фишка не в этом - в каждом кадре нужно персонажа опускать в лист. Но на практике он будет находиться в нескольких листах. Так вот - рендерить его надо с использованием z-buffer'а в том листе, в котором он при рендеринге BSP-дерева появляется в последний раз.
Хочу вот спросить, многоуважаемую аудиторию. Кто-нибудь действительно делал BSP-компилятор? Полностью и до конца.
А то я бьюсь с одной проблемкой и никак решить не могу. Вот в статье написано:
В этом случае полигон нужно "распилить", чем и займется функция Split_Polygon(). Реализация этой функции будет домашним заданием читателю.
Чесно говоря, я другого увидель и не ожидал. И я НИГДЕ в И-нете не нашел реализации этой функции (хотя я долго не искал, правда).
Короче. Представьте есть пятиугольник. Делящая плоскость проходит ЧЕРЕЗ ЕГО 1-Ю И 4-Ю вершину. Вершины хранятся в массиве, а полигоны (которые нужно растолкать по BSP и при необходимости распилить -- списки индексов вершин).
У меня вначале был глюк: данный пятиугольник делился на 4-х-угольник и пятиугольник (как точно не помню), да это не важно, вобщем НЕ НА 3-х и 4-х угольники. А суть в том что создавалась новая вершина (такая же как и 1-я, но с другим индексом) И у первого 4-угольника у первой стороны НАЧАЛО И КОНЕЦ БЫЛИ ОДНОЙ ВЕРШИНОЙ (хотя индексы вершин разные, но позиция одна и та же). Вроде бы ничего страшного -- рендерится чуть дольше будет и места занимать, НО при дальнейшем создании BSP-дерева, КОГДА ЭТОТ 4-УГОЛЬНИК ВЫСТУПАЕТ В КАЧЕСТВЕ ДЕЛЯЩЕЙ ПЛОСКОСТИ нормаль его найти..конечно можно, но.... В обще проблема я думаю ясна.
Да и вот что. Этот глюк я исправил, усложнив ф-ю деления полигонов, но где-то остался еще какой-то глюк, при котором полсцены иногда просто "откусывается". Вот его-то я победить так и не смог.
tav, код этой функции находится в BSP FAQ, том же откуда jm взял код рендеринга BSP.
Поищи немножко и найдешь. Просто функция довольно большая и jm наверное решил не приводить её в этой части статьи.
tav
А можно и не юзать индексъ при компиляции BSP, а потом их построить.
Потом - надо внимательно обрабатъвать случай, когда пересечение идет через вершинъ, и не создавать ребра нулевой длиннъ, ето глюк.
Тема в архиве.