Когда я должен найти минимальное и максимальное значения для BoundingBox, прикрепленного к модели

Question

Я работаю над реализацией ModelClass для любой 3D-модели в моем конвейере DirectX 11/12.

Моя конкретная проблема заключается в вычислении минимального и максимального значений для структуры BoundingBox, которую я хочу использовать в качестве члена ModelClass.

У меня есть два подхода к их вычислению.

Подход 1. Когда каждая вершина читается из файла, сохраните текущие minx, y, z и maxx, y, z и проверьте каждую вершину, когда она загружена, относительно текущего min / max x, y, z.

Подход 2. После загрузки всех вершин отсортируйте их по x, затем по y, затем по z, чтобы найти самое низкое и самое высокое значение в каждой точке.

Какой подход вы бы порекомендовали и почему?

Answer 1

Подход 1

Сложность времени в O (n), а сложность памяти - O (1).

Это просто реализовать.

Подход 2

Сложность по времени составляет O (nLogn). Сложность памяти потенциально, по крайней мере, линейна (если вы делаете копию массивов или если вы используете сортировку слиянием) или O (1), если вы используете алгоритм сортировки на месте, такой как быстрая сортировка.

Это должно быть сделано 3 раза по одному для каждого измерения.

В целом Подход 1 является лучшим во всех сценариях, которые я могу себе представить.

Answer 2

Сортировка, как правило, не дешевая операция, тем более что ваши модели становятся больше. Поэтому он, как и подход 1, более эффективен, но если я не уверен, я предлагаю измерить его и посмотреть, какой из них занимает больше времени.

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