Viewport culling

Viewport culling — один из ключевых механизмов оптимизации рендеринга в HERE Technologies Maps API, отвечающий за исключение из обработки всех объектов, которые не попадают в текущую область видимости карты. В условиях динамического взаимодействия пользователя с картой (панорамирование, зумирование, вращение) этот механизм становится критически важным для поддержания высокой производительности интерфейса.

Viewport culling основан на геометрическом пересечении объектов карты с текущим видимым прямоугольником экрана (viewport). Карта в браузере представляет собой проекцию географических координат в двумерное пространство, поэтому каждая сущность — будь то тайл, маркер или геометрия — может быть проверена на попадание в область видимости.

Основная идея заключается в том, что:

  • объекты вне viewport не рендерятся;
  • объекты частично пересекающие viewport рендерятся частично или полностью;
  • объекты внутри viewport проходят полный цикл отрисовки.

Геометрическая модель viewport

Viewport в HERE Maps API описывается прямоугольником в экранных координатах:

  • левый верхний угол: (xMin, yMin)
  • правый нижний угол: (xMax, yMax)

Каждый объект карты имеет собственный bounding box (ограничивающий прямоугольник), также выраженный в экранных координатах после проекции из географических координат.

Проверка пересечения сводится к классической задаче:

  • если bounding box объекта не пересекается с viewport — объект исключается;
  • если пересечение есть — объект проходит дальше в pipeline рендеринга.

Тайловая система и culling на уровне плиток

В основе отображения карт в HERE Technologies лежит тайловая система. Карта разбивается на квадратные тайлы фиксированного размера (обычно 256×256 пикселей).

Viewport culling на уровне тайлов работает следующим образом:

  1. Определяется набор тайлов, пересекающих текущий viewport.
  2. Загружаются только эти тайлы.
  3. Тайлы вне границ экрана игнорируются полностью.

Формально:

  • пусть z — уровень зума;
  • x, y — индексы тайла;
  • viewport преобразуется в диапазон тайлов;
  • выбирается множество T = {(x, y) | tile intersects viewport}.

Это позволяет резко сократить количество HTTP-запросов и операций декодирования изображений или векторных данных.

Culling маркеров и объектов слоя

Marker и object layer culling выполняется на уровне JavaScript runtime и WebGL (в зависимости от режима рендеринга).

Каждый объект имеет:

  • географические координаты (lat, lng);
  • экранную позицию (x, y), вычисленную через projection;
  • bounding radius или bounding box.

Алгоритм:

  1. Перевод координат в экранные.
  2. Построение bounding box объекта.
  3. Проверка пересечения с viewport.
  4. Исключение объектов вне области.

Особенность HERE Maps API заключается в том, что многие операции выполняются батчами, чтобы уменьшить количество пересечений в цикле рендера.

WebGL и аппаратный viewport culling

В векторном режиме рендеринга viewport culling частично переносится на GPU. Здесь применяется:

  • frustum culling (усечённая пирамида видимости);
  • clip-space отсечение;
  • vertex shader-based discard.

После проекции координат в clip space выполняется проверка:

  • x, y, z ∈ [-w, w] — внутри области видимости;
  • иначе вершина отбрасывается.

Таким образом GPU самостоятельно исключает значительную часть геометрии до rasterization.

Bounding box и его роль в оптимизации

Bounding box — базовая структура для всех уровней culling. Он используется:

  • для тайлов;
  • для POI (points of interest);
  • для полилиний и полигонов;
  • для кластеров маркеров.

Векторные объекты часто имеют предварительно вычисленный географический bounding box:

  • minLat, minLng
  • maxLat, maxLng

После проекции он преобразуется в экранные координаты и используется для проверки пересечения с viewport.

Кластеризация как форма viewport culling

При большом количестве объектов (например, тысячи маркеров) применяется кластеризация, которая фактически является расширенной формой culling:

  • объекты вне viewport исключаются;
  • внутри viewport объединяются в кластеры;
  • кластеры рендерятся вместо отдельных объектов.

Это снижает количество DOM- или WebGL-объектов, участвующих в отрисовке.

Инкрементальное обновление viewport

При перемещении карты viewport culling не пересчитывается с нуля. Вместо этого используется инкрементальный подход:

  • вычисляется delta смещения;
  • пересекающиеся тайлы добавляются/удаляются;
  • объекты, вошедшие в viewport, догружаются;
  • вышедшие удаляются из сцены.

Это особенно важно при плавном pan/zoom, где пересечения меняются постепенно.

Оптимизация через spatial indexing

Для ускорения viewport culling в HERE Technologies Maps API используются пространственные индексы:

  • R-tree для векторных объектов;
  • grid-based indexing для тайлов;
  • hierarchical tiling для зум-уровней.

R-tree позволяет выполнять запрос вида:

  • “найти все объекты, пересекающие viewport”

в логарифмическое время относительно количества объектов.

Сложные геометрии и частичное отсечение

Для полигонов и полилиний применяется более сложный culling:

  • сначала проверяется bounding box;
  • затем выполняется segment-level clipping;
  • при необходимости используется алгоритм Сазерленда–Ходжмана для отсечения по viewport.

Это позволяет корректно отображать объекты, частично выходящие за границы экрана.

Практическая схема pipeline viewport culling

Обобщённый pipeline выглядит так:

  1. Получение текущего viewport.
  2. Преобразование географических координат в экранные.
  3. Отбор тайлов по пересечению.
  4. Проверка bounding boxes объектов.
  5. Фильтрация через spatial index.
  6. Передача оставшихся объектов в renderer.
  7. GPU/DOM рендеринг с дополнительным отсечением.

Стоимость вычислений и влияние на производительность

Viewport culling снижает сложность рендеринга с:

  • O(n) по всем объектам сцены

до:

  • O(k log n), где k — количество объектов в viewport.

На практике это означает:

  • уменьшение количества DOM-элементов;
  • снижение нагрузки на WebGL контекст;
  • уменьшение количества draw calls;
  • сокращение сетевых запросов к тайлам.

Типичные ошибки при реализации culling-логики

В кастомных слоях поверх HERE Maps API часто встречаются проблемы:

  • использование только географического bounding box без учета проекции;
  • отсутствие padding зоны вокруг viewport (leading to flickering);
  • пересчёт всех объектов при каждом mousemove;
  • игнорирование z-index и overlap в marker layers.

Корректная реализация всегда учитывает:

  • padding viewport (buffer zone);
  • актуальный zoom level;
  • projection distortion near poles;
  • асинхронность загрузки тайлов.
Оглавление