2D вопрос пространственной индексации:
Что вы называете структурой данных, которая по сути является бесконечным * квадродеревом, узлы которого не содержат ни абсолютных координат, ни абсолютных масштабов - в котором система координат каждого узла нормализована к квадрату единицы (0,0) - ( 1,1), а в каком узле верхнего уровня не фиксируется абсолютно?
Это, конечно, quadtree - но что это за type of quadtree? (Есть ли общее имя? Я видел десятки типов квадриев, названных и определенных в литературе, но не этот конкретный.)
Для рендеринга сцены вам дается некоторый начальный узел (не обязательно корневой), его размер в пикселях и его местоположение на экране. Затем вы рисуете все объекты в узле, масштабируя их координаты, используя текущую матрицу преобразования, которую вы помещаете в стек и делите пополам, когда спускаетесь по дереву. Таким образом, абсолютные координаты узлов доступны только через временные рабочие переменные во время рендеринга и не содержатся в самой структуре данных.
Если объект внутри узла перемещается за пределы узла (например, за пределы квадрата единицы), вы передаете его родителю для переназначения другому узлу. Если объект становится фрагментированным (например, астероид, попавший в пулю), меньшие части передаются дочерним узлам, которые должны соответствующим образом масштабировать координаты для поддержания нормализации единичного квадрата в каждом узле.
Ключевое отличие здесь от традиционных реализаций дерева квадрантов, используемых в пространственной индексации, состоит в том, что координаты объектов всегда относительно системы координат узла, в котором они содержатся. Этот релятивизм относится не только к положению, но и к масштабу.
* Бесконечно из-за отсутствия абсолютных координат; даже координаты с плавающей запятой двойной точности дают ограничения по положению и размеру при использовании для абсолютного позиционирования.