Основным преимуществом четырехъядерного дерева является то, что оно позволяет очень быстро отбросить целые группы сегментов из рассмотрения.
Например, предположим, что у меня есть четырехугольное дерево с шестью уровнями. На самом низком уровне это 32x32 коробки; 1024 коробки, содержащие этот самый нижний, самый подробный уровень. Для сравнения мы также рассмотрим «пространственный хеш» - плоскую сетку, которая также содержит 32x32 блока, всего 1024 блока. (в четырехугольном дереве более 1024 ящиков, так как оно также содержит большие ящики на своих более высоких уровнях)
Предположим, что в системе нет встречных объектов - все поля нашего четырехугольного дерева и нашей плоской сетки полностью пусты.
Если вы тестируете столкновения чего-то достаточно большого, чтобы его ограничивающая рамка пересекала все эти блоки, и вы используете плоскую сетку, вы должны проверить каждый из этих 1024 блоков, чтобы увидеть, есть ли что-нибудь в них. их.
Но если вы используете вложенное четырехугольное дерево, самый верхний уровень может сказать вам, что в системе нет других объектов, и поэтому вам нужно только взглянуть на этот единственный блок, чтобы понять, что вы не найдете коллизий. глубже в дереве - вы можете немедленно прекратить тестирование.
Точно так же, если объекты существуют только в определенных областях четырехугольного дерева, четырехугольное дерево, естественно, будет направлять ваш поиск только через потенциально релевантные поля, в то время как сетка требует, чтобы вы отметили каждый отдельный пересекаемый блок, поскольку у вас нет возможности узнать заранее какие квадраты сетки будут иметь объекты в них. Если большая часть вашего четырехугольного дерева пуста, и вы выполняете большие сложные запросы (скажем, огромные углы камеры вместо маленьких простых прямоугольников), то вы можете обнаружить, что вы выполняете итерации по гораздо меньшему количеству блоков, если вы делаете проверяет что-то, используя древовидную структуру, а не плоскую сетку. И это может иметь большое значение.
Разумеется, все это не означает, что древовидная структура всегда является правильным выбором. Плоские сетки идеально подходят для ситуации, которую вы имеете в своем примере - плотные облака объектов почти равномерно распределены по всему миру, и мы проводим простые и недорогие тесты на столкновение. Абсолютно сетка, вероятно, будет оптимальным подходом в этом случае!