Ограничивающие сферы, вероятно, помогут вам со многими движущимися объектами; вы вычисляете квадрат радиуса объекта и отслеживаете его от его центра. Если квадрат расстояния между центрами двух объектов меньше суммы квадратов радиусов двух объектов, то у вас есть потенциальное столкновение. Все сделано с квадратами расстояний; нет квадратных корней.
Вы можете отсортировать ближайших соседей по минимальному квадрату расстояния между вашими объектами. Обнаружение столкновений, конечно, может быть сложным, и с объектами несферической формы Bounding Spheres не обязательно предоставит вам информацию о столкновении, но может довольно хорошо обрезать ваше дерево объектов, которые вам нужно сравнивать на предмет столкновений.
Вам, конечно же, нужно будет отслеживать ЦЕНТР вашего объекта; и в идеале вы хотели бы, чтобы каждый объект был жестким, чтобы избежать необходимости пересчета размеров ограничивающей сферы (хотя пересчет не особенно сложен, особенно если вы используете дерево жестких объектов, каждый со своей ограничивающей сферой для объектов, которые нежесткие, но все усложняется).
По сути, чтобы ответить на ваш вопрос о структурах данных, вы можете сохранить все свои объекты в главном массиве; У меня был бы набор «региональных» массивов, которые состоят из ссылок на объекты в главном массиве, по которым вы можете быстро сортировать объекты на основе их декартовых координат; Массивы "региона" должны иметь перекрытие, определяемое как минимум в 2 раза больше самого большого радиуса объекта в вашем массиве основных объектов (если это возможно; очевидно, возникает вопрос о масштабировании ограничивающей сферы объекта и количестве объектов).
Как только у вас это получится, вы можете провести быстрый тест на столкновение, сравнив расстояния между всеми объектами в пределах региона друг от друга; опять же, именно здесь определение региона становится важным, потому что вы делаете значительный компромисс между количеством регионов и количеством сравнений. Однако это немного проще просто потому, что ваши сравнения расстояний сводятся к простым вычитаниям (и, конечно, операциям abs ()).
Конечно, тогда вам нужно будет выполнить фактическое обнаружение столкновений между вашими несферическими объектами, и это может быть нетривиально, но в этот момент вы очень резко сократили количество возможных сравнений.
По сути, это двухуровневая система; первый - это массив регионов, с помощью которого вы выполняете грубую сортировку сцены. Во-вторых, у вас есть сравнение расстояний внутри региона; в котором вы собираетесь выполнять базовое обнаружение столкновений и отмечать столкновения на объектах, которые столкнулись.
Вероятно, в таком алгоритме есть место для использования деревьев в динамическом определении региона, чтобы выровнять размеры вашего региона, чтобы гарантировать, что размер вашего региона не будет расти слишком быстро с «переполненными» регионами; такие вещи, однако, нетривиальны, потому что с объектами разных размеров ваша сортировка по плотности становится ... сложной, если не сказать больше.
person
Paul Sonier
schedule
25.10.2008