Процедурная оптимизация рендеринга графика: рисовать только видимую часть

Question

Фон

Допустим, у меня есть миллионы взаимосвязанных Node экземпляров, которые вместе образуют график. Каждый Node имеет 2D-позицию. Пользователь должен иметь возможность прокручивать процедурный рендер этого графика. У каждого Node есть метод draw, но если я draw всех Node с в каждом кадре, это очень медленно.

Поскольку пользователь обычно не хочет видеть весь график, а вместо этого увеличивает его, оптимизация находится в , а не в рисовании Node s, которые находятся вне экрана .

Мой подход

Разделите пространство двухмерного мира на прямоугольные Segment с. Присвойте каждому Node то, в чем они находятся Segment. При рисовании сначала выясните, с каким набором Segment s пересекается вид пользователя, и draw только Node s в этих Segment s.

Теперь к моему актуальному вопросу:

Как определить оптимальный размер Segment? (Сделать его слишком большим, и это то же самое, что нарисовать все. Сделать его слишком маленьким, и снова слишком много, чтобы перебрать.)

Answer 1

Я думаю, Четырехъядерные деревья здесь могут быть более полезными, чем деление на прямоугольники фиксированного размера.

Answer 2

Ну, вы всегда можете определить это методом проб и ошибок. Кстати, размер сегмента может зависеть от уровня масштабирования.

Другое возможное решение состоит в том, чтобы иметь два отсортированных массива узлов. Один массив Node[] ax отсортирован по позиции x, а другой Node[] ay по позиции y. Если вы хотите отобразить узлы в (x1, y1) - (x2, y2), вы создадите набор узлов, которые находятся на пересечении отсортированных массивов, отфильтрованных по границам.