Как сортировать и сравнивать в иерархии ограничивающих объемов
В настоящее время я реализую иерархию ограничивающих объемов только для трехмерных треугольников. К сожалению, все объяснения BVH не соответствуют той части, где вы сортируете свои Объекты для разделения. Для начала я хочу стремиться к сбалансированному дереву и использовать срединный срез. Это потребовало бы от меня сортировки либо треугольников, либо их ограничивающих прямоугольников (AABB) после пространственного критерия на оси разделения текущего узла. Я действительно не уверен, достаточно ли максимального или минимального удлинения BB или треугольника для правильного разделения, так как некоторые треугольники могут быть больше. Я также не уверен, что лучше сравнить ограничивающую рамку или треугольник.
Вторая часть проблемы заключается в том, что сортировка каждого шага кажется дорогой. Другие алгоритмы в компьютерной графике используют предварительно отсортированные списки, а затем разделяют их в соответствии с критерием разделения. Я не вижу способа, как вы могли бы эффективно сравнить треугольники и убедиться, что они принадлежат списку. Значит ли это, что я должен сортировать список на каждом шагу?
2 ответа
У вас есть несколько вариантов, как вы обнаружили. Легче всего думать о том, чтобы использовать центроид ограничительной рамки. Вы также можете отсортировать по минимальной координате и отдельно по максимальной координате.
Вы можете сортировать по каждой оси в качестве предварительной обработки. Затем каждая итерация представляет собой разбиение, которое включает в себя выбор оси, на которую нужно разделить и где разделить, и сохранение начальной / конечной точек в отсортированном списке этой оси.
См. Статью Инго Уолда: http://www.sci.utah.edu/~wald/Publications/2007/FastBuild/download/fastbuild.pdf
Более быстрый подход с более низким качеством - это линеаризованный BVH - сопоставление каждого центроида с координатой на кривой заполнения пространства, такой как код Мортона, затем сортировка всех треугольников по их коду Мортона, а затем разбиение отрезков на блоки.
SAH (эвристика поверхности) является наиболее распространенным способом оценки того, где разделить набор треугольников в BVH, используемых для трассировки лучей. Вы можете найти хорошее объяснение в главе 4 книги PBRT ( http://www.pbrt.org/). Он доступен бесплатно здесь: http://pbrt.org/pbrt-2ed-chap4.pdf
Если у вас есть хоть какой-то смутный интерес к трассировке лучей, я предлагаю вам купить полную книгу.