В настоящее время я реализую иерархию ограниченных томов для трехмерных треугольников. К сожалению, все объяснения BVH не соответствуют той части, где вы сортируете объекты для расщепления. Для начала я хочу стремиться к сбалансированному дереву и использовать срединный разрез. Это потребовало бы сортировки либо треугольников, либо их ограничивающих прямоугольников (AABB) после пространственного критерия на оси разделения текущего узла. Я действительно не уверен, что максимальной или минимальной протяженности BB или треугольника достаточно для правильного разделения, поскольку некоторые треугольники могут быть больше. Я также не уверен, что лучше сравнить ограничительную рамку или треугольник.Как сортировать и сравнивать в иерархии точечного объема
Вторая часть проблемы заключается в том, что сортировка каждого шага кажется дорогой. Другие алгоритмы в компьютерной графике используют предварительно отсортированные списки, а затем разделяют их по критерию расщепления. Я не вижу способа эффективно сравнивать треугольники и уверять, что они принадлежат к списку. Означает ли это, что я должен сортировать список на каждом шагу?
Спасибо за ответ. Расчет бининга и стоимости, сделанный в документе, по-видимому, во многом зависит от того, что я хотел сделать. Я все еще не уверен, что выбрать. Центроиды кажутся хорошей идеей, но я не вижу недостатков или преимуществ по сравнению с сортировкой по min и max. Я также не понимаю, как помочь мне сохранить начальную/конечную точку. – funkysash
Использование центроидов. Min и max являются белки, если у вас общий случай длинных ориентированных треугольников, но не требуется специальная логика как min, так и max. Индексы start/end в отсортированный список представляют собой диапазон, который принадлежит одному ящику. Вы разделяете промежуток, когда вы рекурсируете. –