Скорость алгоритма разделения пространства
Я разрабатываю 3D Game Engine как проект. Я хотел бы использовать алгоритмы разделения пространства для каждого треугольника / многоугольника в моей сцене, чтобы эффективно обнаруживать столкновения. Я просто хочу знать (перед тем как приступить к программированию), насколько быстрым является типичный алгоритм разделения пространства в современных компьютерных играх? У меня есть динамические объекты, поэтому я думаю, что мне, возможно, придется перераспределять мою сцену каждый кадр. Возможно ли это и все же достичь разумной частоты кадров? Было бы очень полезно, если бы ответ мог включать данные (например, FPS, количество полигонов и т. Д.). Если это слишком много проблем, просто скажите мне, возможно ли перераспределить каждый кадр.
Любая помощь будет оценена.
1 ответ
Сначала я бы предложил прочитать главу Обнаружение столкновений в широком диапазоне фаз с помощью CUDA. Это идет в сравнение различных алгоритмов столкновения с широкой фазой. Ваша производительность зависит от нескольких ключевых переменных. Первая переменная - это то, реализован ли ваш алгоритм с использованием ускорения графического процессора. Ранее цитируемая статья содержит некоторые ориентиры по частоте кадров и количеству объектов. По крайней мере, это должно дать вам хорошее представление о том, что достижимо.
Если вы не планируете ускорение графического процессора, развертка и сокращение будут одним из самых простых в реализации. Я не знаю точных цифр, но это хорошо работает, когда объектов мало, и ваши объекты не сильно различаются между кадрами. В этой ситуации у вас есть O(N) производительности. Это хороший вариант для начала, потому что его легко реализовать.
Если вы действительно серьезно, я рекомендую книгу Обнаружение столкновений в реальном времени. Я использовал этот, когда проводил исследование методов обнаружения столкновений. Это был отличный ресурс.