Как рендерят огромные карты?
От: Homunculus Удмуртия  
Дата: 02.07.20 02:44
Оценка:
У меня есть гигантская детализированная SVG карта города. Размером около 1.5 гигов.
Ясно, что и загрузка и рендеринг занимает кучу времени. Надо оптимизировать.

Как рендерят большие карты?

Какая мысль очевидно приходит в голову. Во-первых, сделать несколько растров под разные зумы. При уже более-менее большом растре — начать бить на клетки и погружать те части, которые видит пользователь в данный момент. Это как бы очевидный подход.
Но есть минусы, которые не нравятся. Во-первых, эти самые разные растры под разные зумы. Что-то дизайнерски некрасивое в этом есть. Во-вторых, перевод в растр сжирает преимущество наличия вектора.

Есть еще другая мысль. Мне собственно все преимущества SVG и не нужны. Нужны только контуры и на некоторых контурах заливка сплошным цветом. Все. То есть мысль перевести SVG в какой-то свой формат контуров и уже эти объекты раскидать по разным файлам и подгружать по мере необходимости.

Как делается обычно рендеринг карт или если не знаете, то как бы сделали вы?
Отредактировано 02.07.2020 2:54 Homunculus . Предыдущая версия .
Re: Как рендерят огромные карты?
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 02.07.20 02:58
Оценка:
Здравствуйте, Homunculus, Вы писали:

H>Как делается обычно рендеринг карт или если не знаете, то как бы сделали вы?


Никогда этим не занимался, но уверен, что для векторной графики просто должна быть сущность типа clip path — регион, внутри которого надо рендерить и который сам отсекает части, которых не надо касаться. Чем больше зум — тем больше отсекается лишнего.
https://elibrary.ru/author_counter.aspx?id=875549
Re[2]: Как рендерят огромные карты?
От: Homunculus Удмуртия  
Дата: 02.07.20 03:05
Оценка:
Здравствуйте, Nuzhny, Вы писали:

Так проблема не только в отрисовке, но перед отрисовкой еще и загрузка кучу времени занимает. Отсечь невидимое — одно. Но вот загрузить все контуры и всегда их держать в памяти — другое. Представь карту города, где даже листики деревьев — отдельные контура Там миллиарды объектов.
Re[3]: Как рендерят огромные карты?
От: sqrt  
Дата: 02.07.20 03:21
Оценка: 8 (1)
Здравствуйте, Homunculus, Вы писали:

H>Здравствуйте, Nuzhny, Вы писали:


H>Так проблема не только в отрисовке, но перед отрисовкой еще и загрузка кучу времени занимает. Отсечь невидимое — одно. Но вот загрузить все контуры и всегда их держать в памяти — другое. Представь карту города, где даже листики деревьев — отдельные контура Там миллиарды объектов.


Есть векторный формат тайлов Mapbox Vector Tiles.
Re[4]: Как рендерят огромные карты?
От: Homunculus Удмуртия  
Дата: 02.07.20 03:22
Оценка:
Здравствуйте, sqrt, Вы писали:

S>Есть векторный формат тайлов Mapbox Vector Tiles.


О, интересно, не знал. Спасибо.
Re: Как рендерят огромные карты?
От: swame  
Дата: 02.07.20 05:38
Оценка:
Здравствуйте, Homunculus, Вы писали:

H>У меня есть гигантская детализированная SVG карта города. Размером около 1.5 гигов.

H>Ясно, что и загрузка и рендеринг занимает кучу времени. Надо оптимизировать.

H>Как рендерят большие карты?


H>Какая мысль очевидно приходит в голову. Во-первых, сделать несколько растров под разные зумы. При уже более-менее большом растре — начать бить на клетки и погружать те части, которые видит пользователь в данный момент. Это как бы очевидный подход.

H>Но есть минусы, которые не нравятся. Во-первых, эти самые разные растры под разные зумы. Что-то дизайнерски некрасивое в этом есть. Во-вторых, перевод в растр сжирает преимущество наличия вектора.

H>Есть еще другая мысль. Мне собственно все преимущества SVG и не нужны. Нужны только контуры и на некоторых контурах заливка сплошным цветом. Все. То есть мысль перевести SVG в какой-то свой формат контуров и уже эти объекты раскидать по разным файлам и подгружать по мере необходимости.


H>Как делается обычно рендеринг карт или если не знаете, то как бы сделали вы?


В памяти набор примитивов (линия, точка, текст)+ нужные графические атрибуты.
Примитивы отсортированы по координатам, чтобы быстро отсортировывать те,что находятся в текущей области отрисовки.
Если карта занимает 1,Гб в SVG то ее легко поместить в несколько сотен метров оперативки.
Использовать языки, где не создается по объекту на каждый чих. И без этих ваших сборщиков мусора.
Отрисовывать в графическом движке с аппаратным ускорением, если нужна быстрая отрисовка с антиалиасингом.
Файл 1,5 Гб можно грузить и парсить за десятки секунд, в зависимости от скорости диска.
Но если нужно грузить быстро и часто, лучше переложить в что то более компактное, чем XML, и легко парсящееся.
Самое трудоемкое реализовать качественную отрисовку картинки.
Отредактировано 02.07.2020 6:09 swame . Предыдущая версия .
Re[3]: Как рендерят огромные карты?
От: swame  
Дата: 02.07.20 05:44
Оценка:
Здравствуйте, Homunculus, Вы писали:

H>Здравствуйте, Nuzhny, Вы писали:


H>Так проблема не только в отрисовке, но перед отрисовкой еще и загрузка кучу времени занимает. Отсечь невидимое — одно. Но вот загрузить все контуры и всегда их держать в памяти — другое. Представь карту города, где даже листики деревьев — отдельные контура Там миллиарды объектов.


Какие миллиарды? В 1,5 Гб SVG уместится максимум несколько десятков миллионов точек.
Re[4]: Как рендерят огромные карты?
От: Homunculus Удмуртия  
Дата: 02.07.20 05:50
Оценка:
Здравствуйте, swame, Вы писали:

S>Какие миллиарды? В 1,5 Гб SVG уместится максимум несколько десятков миллионов точек.


А город еще не целиком готов. Пока только три района. И уже 1.5 гига. Будет больше.
Re[5]: Как рендерят огромные карты?
От: swame  
Дата: 02.07.20 06:15
Оценка:
Здравствуйте, Homunculus, Вы писали:

H>Здравствуйте, swame, Вы писали:


S>>Какие миллиарды? В 1,5 Гб SVG уместится максимум несколько десятков миллионов точек.


H>А город еще не целиком готов. Пока только три района. И уже 1.5 гига. Будет больше.


Если карта не умещается в оперативке, то задача существенно усложняется и легче использовать готовую ГИС систему.
Re[6]: Как рендерят огромные карты?
От: Homunculus Удмуртия  
Дата: 02.07.20 06:56
Оценка: :)))
Здравствуйте, swame, Вы писали:
S>Если карта не умещается в оперативке, то задача существенно усложняется и легче использовать готовую ГИС систему.

Не, ГИС не прокатит. Это не реальный город, а из игрового проекта.
Re: Как рендерят огромные карты?
От: samius Россия http://sams-tricks.blogspot.com
Дата: 02.07.20 06:59
Оценка: +3
Здравствуйте, Homunculus, Вы писали:

H>Как делается обычно рендеринг карт или если не знаете, то как бы сделали вы?


Используется пространственный индекс объектов, который позволяет не перебирать те объекты, которые не попали в окно запроса и откидывать слишком мелкие объекты (типа контуров домов на общем плане города).

Грубо карта разрезается на клетки n*m, для каждой клетки составляется список пересекающихся с ней объектов. И так несколько раз для разных n и m. В момент рендеринга выбираются все клетки, пересекающиеся с областью рендеринга. Так получается список объектов для рендеринга, именно эти объекты читаются с диска при рендеринге. Смысла держать все в памяти нет, т.к. пользователь видит либо общий план без деталей, либо малую часть детализированной карты.
Re[2]: Как рендерят огромные карты?
От: Homunculus Удмуртия  
Дата: 02.07.20 07:03
Оценка:
Здравствуйте, samius, Вы писали:

Такой подход очевиден, но и он имеет подводные камни. Каждый объект надо сортировать не просто по положению на сетке города, но и что-то типа LOD, то есть рисовать его или нет в зависимости от зума. Растровый подход тут проще.
Re[3]: Как рендерят огромные карты?
От: samius Россия http://sams-tricks.blogspot.com
Дата: 02.07.20 07:06
Оценка:
Здравствуйте, Homunculus, Вы писали:

H>Здравствуйте, samius, Вы писали:


H>Такой подход очевиден, но и он имеет подводные камни. Каждый объект надо сортировать не просто по положению на сетке города, но и что-то типа LOD, то есть рисовать его или нет в зависимости от зума. Растровый подход тут проще.


Я отвечал на вопрос о том, как рендерят карты. Очевидно, что растровый подход — уже результат рендеринга огромной карты.
Re[2]: Как рендерят огромные карты?
От: Stanislav V. Zudin Россия  
Дата: 02.07.20 07:32
Оценка:
Здравствуйте, Homunculus, Вы писали:

H>>Как рендерят большие карты?


Дополню ответ камрада swame, расскажу, как рендерится дизайн печатной платы (или кристалл ИС).

S>В памяти набор примитивов (линия, точка, текст)+ нужные графические атрибуты.

S>Примитивы отсортированы по координатам, чтобы быстро отсортировывать те,что находятся в текущей области отрисовки.

Строится 2Д хеш, точнее несколько хешей под разные объекты. Хеш позволяет быстро найти объекты, попадающие в заданный прямоугольник, либо в окрестности точки (мы же потом захотим нарисованное потыкать мышой).

S>Если карта занимает 1,Гб в SVG то ее легко поместить в несколько сотен метров оперативки.

S>Использовать языки, где не создается по объекту на каждый чих. И без этих ваших сборщиков мусора.

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

Для пущей компактности каждый атрибут объекта хранится в своём массиве. Другими словами переходим к реляционной таблице, где в массивах лежат столбцы таблиц.

S>Отрисовывать в графическом движке с аппаратным ускорением, если нужна быстрая отрисовка с антиалиасингом.


+1
С использованием соответствующих техник для ускорения рисования (списки вершин, шейдеры и т.д.).

S>Файл 1,5 Гб можно грузить и парсить за десятки секунд, в зависимости от скорости диска.


Если не использовать какой-нибудь msxml парсер, а взять, к примеру, scanner нашего камрада c-smile'а, то скорость разбора xml будет ограничена скоростью чтения с диска. Хотя... любой sax-парсер должен дать близкие значения по скорости, структуры данных нужно выбрать правильные.

S>Но если нужно грузить быстро и часто, лучше переложить в что то более компактное, чем XML, и легко парсящееся.


Если использовать структуру данных, предложенную выше, то бинарная десериализация для нее сводится к двум операциям чтения на каждый массив — считал число элементов, выделил память, зачитал все данные в память. Для кэширования данных и быстрого подъема с диска самое то.

S>Самое трудоемкое реализовать качественную отрисовку картинки.


Угу.
Дизайнерские способности не помешают, чтобы красиво получилось.
_____________________
С уважением,
Stanislav V. Zudin
Re[3]: Как рендерят огромные карты?
От: Stanislav V. Zudin Россия  
Дата: 02.07.20 07:37
Оценка: 8 (1)
Здравствуйте, Homunculus, Вы писали:

H>Каждый объект надо сортировать не просто по положению на сетке города, но и что-то типа LOD, то есть рисовать его или нет в зависимости от зума.


Достаточно оценить размеры его bound rect'а в пикселях при текущем масштабе. Это недорого.
Мы так рисуем вспомогательную информацию. Надписи, к примеру.
_____________________
С уважением,
Stanislav V. Zudin
Re: Как рендерят огромные карты?
От: L.K. Марс  
Дата: 02.07.20 07:52
Оценка: 28 (3)
H>Ясно, что и загрузка и рендеринг занимает кучу времени. Надо оптимизировать.

Достаточно мощной машины. Процессора, оперативки. И не надо надо ничего оптимизировать.

А кучу времени занимало вот это:

https://www.youtube.com/watch?v=L7SJVBX7jxo
http://mtdata.ru/u9/photoA8E5/20461312049-0/original.jpg
Re: Как рендерят огромные карты?
От: Zhendos  
Дата: 02.07.20 08:04
Оценка: +1
Здравствуйте, Homunculus, Вы писали:

H>Как делается обычно рендеринг карт или если не знаете, то как бы сделали вы?


Вот например как рендеряться векторные карты в "реальном" времени:
https://habr.com/ru/company/mailru/blog/262903/
Re: Как рендерят огромные карты?
От: kov_serg Россия  
Дата: 02.07.20 08:15
Оценка: 8 (1)
Здравствуйте, Homunculus, Вы писали:

H>У меня есть гигантская детализированная SVG карта города. Размером около 1.5 гигов.

H>Ясно, что и загрузка и рендеринг занимает кучу времени. Надо оптимизировать.

H>Как рендерят большие карты?

Очень просто.
1. svg для этого не пригоден (но можно использовать как исходник)
2. карту надо разбить на области, например прямоугольники. сперва на 4 шт затем каждую чаcть так же до нужной детализации. Для каждого прямоугольника в зависимости от масштаба строиться своя оптимизированная картинка(с выкидыванием лишних деталей).
3. карты как правило имеют разные слои, несущую разную информацию (улицы, номера домов, электросети, магистрали и т.п.) всё разбивается так же.
4. плюс индексы для поисков (но это не к отрисовке)
5. Ренедерится из ближайших блоков в подходящем масштабе.
Re: Как рендерят огромные карты?
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 02.07.20 08:40
Оценка: 9 (2)
Здравствуйте, Homunculus, Вы писали:

H>Как рендерят большие карты?


H>Какая мысль очевидно приходит в голову. Во-первых, сделать несколько растров под разные зумы. При уже более-менее большом растре — начать бить на клетки и погружать те части, которые видит пользователь в данный момент. Это как бы очевидный подход.

Это единственный поход, который может работать на минимальном зуме, когда нао отобразить всю карту или большую часть.

H>Но есть минусы, которые не нравятся. Во-первых, эти самые разные растры под разные зумы. Что-то дизайнерски некрасивое в этом есть. Во-вторых, перевод в растр сжирает преимущество наличия вектора.

Надо понять какие "преимущества вектора" надо сохранить и от этого плясать. Никто не мешает иметь несколько "слоев", где базовый — растр, а поверх накладываются векторные элементы. Причем на разных уровнях зума будут разные детализации разных слоев.

H>Есть еще другая мысль. Мне собственно все преимущества SVG и не нужны. Нужны только контуры и на некоторых контурах заливка сплошным цветом. Все. То есть мысль перевести SVG в какой-то свой формат контуров и уже эти объекты раскидать по разным файлам и подгружать по мере необходимости.

Вы все равно придете к растрам, когда надо будет отображать карту с минимальным зумом.
Re: Как рендерят огромные карты?
От: L_G Россия  
Дата: 02.07.20 19:52
Оценка: 9 (2)
H>Как рендерят большие карты?

Векторные карты для туристических GPS-навигаторов (приборчиков с не особо быстрыми процессорами, тем более в 2000-х годах) подготавливались из исходных (тоже векторных, конечно) так: задавалось несколько масштабных диапазонов (штук 5-8) и для каждого диапазона делалась по сути своя векторная карта, в которой 1) большие объекты разбивались на прямоугольники поменьше, по размеру как экран устройства для среднего для диапазона масштаба 2) на крупных масштабах удалялись ненужные на них мелкие объекты (при подготовке карты можно было каждому объекту "вручную" задать минимальный масштабный диапазон, на котором он еще должен быть виден, но обычно это делалось после автоматизированного присвоения всем объектам этого свойства исходя из их типа и/или их площади).
Естественно, все объекты из одного прямоугольника одного масштабного диапазона в файле хранятся рядом, ну а про индексы для поиска нужного прямоугольника можно сообразить самому, надеюсь.
И никаких растров! Но так "подготовленные" карты — это уже read-only-формат, редактировались они не в нем (обычно).
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.