Построение оптимального набора AABB (2 стр)

Hybernaculum
в следующий раз уточняй что под гуманитариями и диванными теоретиками ты имеешь ввиду себя, а то тратишь только чужое время.

0xdeadc0de
Большое спасибо за содержательный ответ!
Идея построения дерева приходила в голову, однако была отброшена ввиду того, что получающиеся AABB не будут "идеально охватывающими". Вернее, это сильно зависит от выбора делящей плоскости. А мороки с её выбором ничуть не меньше, чем при построении bsp-деревьев, где собственный алгоритм выбора делящей плоскости только ленивый не придумал. :) SAH прекрасен для рейтрейсинга. Но тут условие сформулировать сложнее. Когда видишь модель - чётко понимаешь, что нужно. Вот человек - можно сделать AABB (а лучше OBB) для рук, ног, головы, торса. Вот какая-то машина - делаем боксы для её основных деталей. Но алгоритм-то всего этого "не видит".
Кроме того, авторы в статье много и со вкусом говорят про балансировку. Из условия моей задачи следует, что балансировка не важна вообще. На выходе нужен только список боксов, а эффективность дерева значения не имеет.
В общем, всё же попробую дерево по алгоритму Вегхорста. Ещё раз спасибо. :)
StiX
> Я не понимаю, как наличие ААВВ поможет тебе построить простую и эффективную
> физическую оболочку для модели?
Оболочка аппроксимируется набором AABB. Зачем делать сложную полигональную коллизию со, скажем, статуей, если 90% игроков даже не заметят аппроксимации боксами? А если и заметят, что "что-то не то", не поймут?
Понятное дело, что для колонн, bevel-ов и прочего коллизия нужна полигональная, где
> надо отдельно физ модель для коллизий.
И строить её будет левел-дизайнер. Но во многих случаях без этого можно обойтись.

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

Hybernaculum
Мне - подсказать решение задачи, сформулированной мной, а не придуманной в процессе обсуждения, пожалуйста. :)
Я нигде не написал, что мой алгоритм коллизий использует деревья. То есть он, конечно, их использует, но не BVH, и вообще, это к задаче отношения не имеет.
Эффективность дерева значения не имеет потому, что мне не нужно это самое дерево. Мне нужен набор ббоксов. Грубо говоря, на выходе алгоритма std::vector<bbox_t>, если так понятнее.

Моласар
> подсказать решение задачи, сформулированной мной
Говорят, что правильная постановка задачи - половина решения.

Hybernaculum
Ну вот мне и нужна была вторая половина решения.
Спасибо всем, кто помог.