Критерий определения листа

Определять, является узел листом или нет, можно не только по количеству входящих в него примитивов, а и по размеру сторон куба узла. Если они меньше заданного, то лист, иначе не лист. Хотя, это не очень оптимальный вариант. Но в наборах ГИС, может случиться, что примитивы фактически находятся в одном месте, тогда алгоритм разбиения примитивов в иерархическую структуру может выйти в бесконечный цикл (или очень сильно разбить сцену на узлы). Поэтому, возможно стоит применять ограничение на длину ребра куба листа. Т. е. чтобы куб, который принадлежит листу, был не меньше заданного. Хотя, если применять разбиение дерева на слои, такого не должно случиться. И можно не применять условие ограничения длины ребра куба. Но в таком случае, необходимо проверять разбиваемый массив на наличие дублирующих примитивов, иначе алгоритм разбиения на дерево может зациклиться.

Но на самом деле, ГИС данные занимают достаточно большой объём, и нахождение среди них дубликатов займёт достаточно большое время. Поэтому, если нет возможности долго ждать построение дерева, лучше ввести ограничение на длину ребра куба в узле.

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