HLFX.Ru Forum (https://hlfx.ru/forum/index.php)
- Компьютерные игры (https://hlfx.ru/forum/forumdisplay.php?forumid=19)
-- Source 2 (https://hlfx.ru/forum/showthread.php?threadid=4469)
Отправлено Government-Man 18-08-2014 в 20:56:
Цитата:
XaeroX писал:
Расскажи, как ты себе представляешь алгоритм разбиения
Да что там представлять-то? Сам BSP прост как два пальца - выбираешь полигон для разбиения и разбиваешь пространство пополам, затем повторяешь для каждой половины, так до тех пор, пока не кончатся полигоны.
Собственно оптимальность дерева как раз зависит от выбора полика для разбиения. В UE например есть параметр Balance от 0 до 100, в зависимости от него он старается либо минимизировать разбиения поликов, либо сбалансировать дерево чтобы число поликов с одной и с другой стороны было примерно одинаковым, либо делает что-то среднее.
Отправлено XaeroX 18-08-2014 в 21:57:
Цитата:
Government-Man писал:
Сам BSP прост как два пальца
Разумеется. Пока читаешь про него в книжках. Чюдеса начинаются, когда ты его начинаешь к реальным картам применять - арканосам там всяким.
Цитата:
Government-Man писал:
разбиваешь пространство пополам
А вот этот момент опиши поподробнее. Что именно разбиваешь и по какому алгоритму? 
Цитата:
Government-Man писал:
В UE например есть параметр Balance от 0 до 100, в зависимости от него он старается либо минимизировать разбиения поликов, либо сбалансировать дерево чтобы число поликов с одной и с другой стороны было примерно одинаковым, либо делает что-то среднее.
Вот забавно. Компилятор волатилы всё сам прекрасно балансирует. Китайский VHLT тоже сам балансирует. И только в UE параметр оставлен на совесть юзера. И ведь правда - разработчика не упрекнёшь, на это всегда есть ответ "да ты параметр неверно подобрал".
Цитата:
Government-Man писал:
либо делает что-то среднее
Дай угадаю. 99,99999% юзеров выберут именно этот вариант. Причём по очевидным причинам. __________________
Отправлено Government-Man 20-08-2014 в 04:37:
Цитата:
XaeroX писал:
И только в UE параметр оставлен на совесть юзера.
Вовсе нет - это аргумент который передается в функцию. Движок сам туда передает значения от 0 до 15, при том что 0 означает только минимизацию сплитов, а 100 - только баланс дерева.
Цитата:
XaeroX писал:
А вот этот момент опиши поподробнее. Что именно разбиваешь и по какому алгоритму?
Ну анрыл делает так:
1. Считает минимальное и максимальное расстояние от вершин полика до плоскости (оно может быть отрицательным, зависит от того, с какой стороны точка)
2. Если расстояния всех точек лежат в пределах некого порогового значения, то полигон объявляется копланарным и оставляется в покое. Причем порог этот равен 0.25 юнита, что по дефолту равняется двум с половиной миллиметрам.
3. Полигон делится на два.
4. Если один из двух полученных поликов получился каким-то слишком маленьким, то он отбрасывается. Емнип, квакохалфовские компилеры для этой цели считают площадь полика, а вот анрыл - расстояния между вершинами.
Отправлено XaeroX 20-08-2014 в 09:25:
Цитата:
Government-Man писал:
Движок сам туда передает
А, то есть там искусственный интеллект, который принимает решения? Ясно.
Цитата:
Government-Man писал:
Считает минимальное и максимальное расстояние от вершин полика до плоскости
Ага, у меня это называется VWinding::calcPlaneSide.
Цитата:
Government-Man писал:
Если расстояния всех точек лежат в пределах некого порогового значения, то полигон объявляется копланарным и оставляется в покое
Так. У меня порог равен 0.01, ну да ладно. Тут я ещё буду крутить, тестировать.
Цитата:
Government-Man писал:
Полигон делится на два.
Всё прекрасно. VWinding::split. Но вот тут-то и зарыта самая мякотка, связанная с ошибками округления и тем, что аксиальные разбиения оказываются предпочтительными.
Цитата:
Government-Man писал:
Если один из двух полученных поликов получился каким-то слишком маленьким, то он отбрасывается.
А это - результаты этих ошибок. Ну сам посуди - если calcPlaneSide вернула SIDE_CROSS (да ещё с таким конским эпсилоном, как 0.25), а после split откуда ни возьмись взялся очень маленький полигон - о чём это говорит? Ошибки накапливаются при нарезке поликов вдоль дерева. Это притом, что компилятор мой работает исключительно в двойной точности. С одинарной вообще жесть получается.
Цитата:
Government-Man писал:
Емнип, квакохалфовские компилеры для этой цели считают площадь полика, а вот анрыл - расстояния между вершинами.
Я тоже считаю расстояния между вершинами, т.е. длины ребёр. Вечно ты воображаешь, что в унреале изобрели что-то новое... Ну с чего бы? Если бы там было что-то новое, я бы, наверное, его изучал, а не кваки, логично же? 
__________________
Отправлено Whistler 20-08-2014 в 09:39:
Нет, спасибо. Мы старичком-джеком и ксашем в два счета уделаем этот Source 2
__________________
Pentium MMX, два гигабайта жесткий диск. Видеокарта S3Trio
Вот что значит жить красиво!
Отправлено Government-Man 20-08-2014 в 12:08:
Цитата:
XaeroX писал:
да ещё с таким конским эпсилоном, как 0.25
Ну по идее ведь чем больше эпсилон, тем больше вероятность, что полик разбиваться не будет?
Цитата:
XaeroX писал:
А, то есть там искусственный интеллект, который принимает решения?
Ну если только захардкоденные константы у них придумывает искуственный интеллект. Только его сорцы судя по всему не лицензируются... %)
Цитата:
XaeroX писал:
Вечно ты воображаешь, что в унреале изобрели что-то новое...
Вот ведь глупость...
Я просто констатировал факт того, что вот в халфе так, а тут эдак. А так-то конечно - длины ребер треугольников помнится еще некий Герон любил измерять задолго до появления унреала... %)
Цитата:
XaeroX писал:
Если бы там было что-то новое, я бы, наверное, его изучал, а не кваки, логично же?
Хм, а что есть в кваках, чего нет в анриле?
Цитата:
XaeroX писал:
VWinding::calcPlaneSide
С каких это пор ты пишешь имена функций вотВТакомСтиле?
Отправлено XaeroX 20-08-2014 в 12:28:
Цитата:
Government-Man писал:
Ну если только захардкоденные константы у них придумывает искуственный интеллект.
Тогда я не понимаю сути выпендрёжа. В любом компиляторе есть захардкоденные константы для балансировки дерева. См. тот же VHLT.
Цитата:
Government-Man писал:
Я просто констатировал факт того, что вот в халфе так, а тут эдак.
Да ничего в халфе не так. Не проверяет она размеры после сплита - ни рёбра, ни площадь. Говорю же - любишь ты фантазировать.
Цитата:
Government-Man писал:
Хм, а что есть в кваках, чего нет в анриле?
Простота кода. И вообще его наличие (если говорить про старые анрилы).
Цитата:
Government-Man писал:
С каких это пор ты пишешь имена функций вотВТакомСтиле?
У меня нет единого стиля. Для каждого конкретного проекта и/или класса стиль выбирается в зависимости от того, что красивее будет смотреться. Программистам не чуждо чувство прекрасного. Хотя, конечно, есть и общие соображения - например, за "i++" в счётчике цикла мне иногда хочется убить. __________________
Отправлено Government-Man 20-08-2014 в 13:12:
Цитата:
XaeroX писал:
Тогда я не понимаю сути выпендрёжа
Да что за желание везде видеть выпендрёж?
Цитата:
XaeroX писал:
Да ничего в халфе не так. Не проверяет она размеры после сплита - ни рёбра, ни площадь.
Гм, разве? Сейчас аж сорцы ZHLT скачал да глянул - а ведь и правда не проверяет! А на что там тогда Winding::getArea? Ах да, он же с его помощью фейсы брашей отбрасывает. Тьфу ты! Эх, всего на свете не запомнишь... =)
Цитата:
XaeroX писал:
Простота кода
Это да, согласен.
Отправлено XaeroX 20-08-2014 в 13:15:
Цитата:
Government-Man писал:
Да что за желание везде видеть выпендрёж?
То есть это был флуд?
Цитата:
Government-Man писал:
Ах да, он же с его помощью фейсы брашей отбрасывает.
Ну да, это в hlcsg.__________________
Отправлено Government-Man 20-08-2014 в 13:21:
Цитата:
XaeroX писал:
То есть это был флуд?
Ну почему же, я описал работу алгоритма на примере. Одним из входных параметров у него был тот самый Balance. А откуда он берется - от юзера или из константы - дело вторичное.
