XaeroX писал: Расскажи, как ты себе представляешь алгоритм разбиения
Да что там представлять-то? Сам BSP прост как два пальца - выбираешь полигон для разбиения и разбиваешь пространство пополам, затем повторяешь для каждой половины, так до тех пор, пока не кончатся полигоны.
Собственно оптимальность дерева как раз зависит от выбора полика для разбиения. В UE например есть параметр Balance от 0 до 100, в зависимости от него он старается либо минимизировать разбиения поликов, либо сбалансировать дерево чтобы число поликов с одной и с другой стороны было примерно одинаковым, либо делает что-то среднее.
Government-Man писал: Сам BSP прост как два пальца
Разумеется. Пока читаешь про него в книжках. Чюдеса начинаются, когда ты его начинаешь к реальным картам применять - арканосам там всяким.
Цитата:
Government-Man писал: разбиваешь пространство пополам
А вот этот момент опиши поподробнее. Что именно разбиваешь и по какому алгоритму?
Цитата:
Government-Man писал: В UE например есть параметр Balance от 0 до 100, в зависимости от него он старается либо минимизировать разбиения поликов, либо сбалансировать дерево чтобы число поликов с одной и с другой стороны было примерно одинаковым, либо делает что-то среднее.
Вот забавно. Компилятор волатилы всё сам прекрасно балансирует. Китайский VHLT тоже сам балансирует. И только в UE параметр оставлен на совесть юзера. И ведь правда - разработчика не упрекнёшь, на это всегда есть ответ "да ты параметр неверно подобрал".
Цитата:
Government-Man писал: либо делает что-то среднее
Дай угадаю. 99,99999% юзеров выберут именно этот вариант. Причём по очевидным причинам.
XaeroX писал: И только в UE параметр оставлен на совесть юзера.
Вовсе нет - это аргумент который передается в функцию. Движок сам туда передает значения от 0 до 15, при том что 0 означает только минимизацию сплитов, а 100 - только баланс дерева.
Цитата:
XaeroX писал: А вот этот момент опиши поподробнее. Что именно разбиваешь и по какому алгоритму?
Ну анрыл делает так:
1. Считает минимальное и максимальное расстояние от вершин полика до плоскости (оно может быть отрицательным, зависит от того, с какой стороны точка)
2. Если расстояния всех точек лежат в пределах некого порогового значения, то полигон объявляется копланарным и оставляется в покое. Причем порог этот равен 0.25 юнита, что по дефолту равняется двум с половиной миллиметрам.
3. Полигон делится на два.
4. Если один из двух полученных поликов получился каким-то слишком маленьким, то он отбрасывается. Емнип, квакохалфовские компилеры для этой цели считают площадь полика, а вот анрыл - расстояния между вершинами.
А, то есть там искусственный интеллект, который принимает решения? Ясно.
Цитата:
Government-Man писал: Считает минимальное и максимальное расстояние от вершин полика до плоскости
Ага, у меня это называется VWinding::calcPlaneSide.
Цитата:
Government-Man писал: Если расстояния всех точек лежат в пределах некого порогового значения, то полигон объявляется копланарным и оставляется в покое
Так. У меня порог равен 0.01, ну да ладно. Тут я ещё буду крутить, тестировать.
Цитата:
Government-Man писал: Полигон делится на два.
Всё прекрасно. VWinding::split. Но вот тут-то и зарыта самая мякотка, связанная с ошибками округления и тем, что аксиальные разбиения оказываются предпочтительными.
Цитата:
Government-Man писал: Если один из двух полученных поликов получился каким-то слишком маленьким, то он отбрасывается.
А это - результаты этих ошибок. Ну сам посуди - если calcPlaneSide вернула SIDE_CROSS (да ещё с таким конским эпсилоном, как 0.25), а после split откуда ни возьмись взялся очень маленький полигон - о чём это говорит? Ошибки накапливаются при нарезке поликов вдоль дерева. Это притом, что компилятор мой работает исключительно в двойной точности. С одинарной вообще жесть получается.
Цитата:
Government-Man писал: Емнип, квакохалфовские компилеры для этой цели считают площадь полика, а вот анрыл - расстояния между вершинами.
Я тоже считаю расстояния между вершинами, т.е. длины ребёр. Вечно ты воображаешь, что в унреале изобрели что-то новое... Ну с чего бы? Если бы там было что-то новое, я бы, наверное, его изучал, а не кваки, логично же?
XaeroX писал: да ещё с таким конским эпсилоном, как 0.25
Ну по идее ведь чем больше эпсилон, тем больше вероятность, что полик разбиваться не будет?
Цитата:
XaeroX писал: А, то есть там искусственный интеллект, который принимает решения?
Ну если только захардкоденные константы у них придумывает искуственный интеллект. Только его сорцы судя по всему не лицензируются... %)
Цитата:
XaeroX писал: Вечно ты воображаешь, что в унреале изобрели что-то новое...
Вот ведь глупость...
Я просто констатировал факт того, что вот в халфе так, а тут эдак. А так-то конечно - длины ребер треугольников помнится еще некий Герон любил измерять задолго до появления унреала... %)
Цитата:
XaeroX писал: Если бы там было что-то новое, я бы, наверное, его изучал, а не кваки, логично же?
Хм, а что есть в кваках, чего нет в анриле?
Цитата:
XaeroX писал: VWinding::calcPlaneSide
С каких это пор ты пишешь имена функций вотВТакомСтиле?
Government-Man писал: Ну если только захардкоденные константы у них придумывает искуственный интеллект.
Тогда я не понимаю сути выпендрёжа. В любом компиляторе есть захардкоденные константы для балансировки дерева. См. тот же VHLT.
Цитата:
Government-Man писал: Я просто констатировал факт того, что вот в халфе так, а тут эдак.
Да ничего в халфе не так. Не проверяет она размеры после сплита - ни рёбра, ни площадь. Говорю же - любишь ты фантазировать.
Цитата:
Government-Man писал: Хм, а что есть в кваках, чего нет в анриле?
Простота кода. И вообще его наличие (если говорить про старые анрилы).
Цитата:
Government-Man писал: С каких это пор ты пишешь имена функций вотВТакомСтиле?
У меня нет единого стиля. Для каждого конкретного проекта и/или класса стиль выбирается в зависимости от того, что красивее будет смотреться. Программистам не чуждо чувство прекрасного. Хотя, конечно, есть и общие соображения - например, за "i++" в счётчике цикла мне иногда хочется убить.
XaeroX писал: Да ничего в халфе не так. Не проверяет она размеры после сплита - ни рёбра, ни площадь.
Гм, разве? Сейчас аж сорцы ZHLT скачал да глянул - а ведь и правда не проверяет! А на что там тогда Winding::getArea? Ах да, он же с его помощью фейсы брашей отбрасывает. Тьфу ты! Эх, всего на свете не запомнишь... =)
Ну почему же, я описал работу алгоритма на примере. Одним из входных параметров у него был тот самый Balance. А откуда он берется - от юзера или из константы - дело вторичное.
| IP: 
18-08-2014 20:56
