Поверхи: 3D-навігація на WebGL в 2gis.ru



У 2014 році 2ГІС випустив Поверхи — це фіча, що дозволяє подивитися схему поверхів будівлі і знайти на ній потрібну організацію. Довгий час вона існувала лише в мобільних додатках 2ГІС. Тепер ця можливість з'явилася і в онлайн-версії.

Поверхи для веба зроблені на технології WebGL: вони повністю тривимірні, їх можна крутити і наближати. Це перший проект компанії, зроблений на цієї технології, і  хотіли б поділитися досвідом реалізації.

Технологічний стек
Технологія WebGL, що дозволяє робити повноцінну тривимірну графіку з апаратним прискоренням в браузері, швидко набирає популярність у веб-картографії. У якості вдалих прикладів її застосування можна привести вже згадані тут Google Maps, а також бібліотеку Mapbox GL.

Перевага карт, зроблених на WebGL, більш плавних переходах і анімація, а також можливість гнучко управляти зовнішнім виглядом карти. Наприклад, гугл-карти вміють малювати на землі тіні від будинків, форма і розмір яких відповідають поточному часу доби. Очевидно, що в традиційних веб-картах, які працюють на тайлах, це неможливо: одного разу отрастрированные тайли вже ніяк не поміняєш, їх можна тільки показати як є.

Недолік WebGL   великої складності і високому порозі входження. Тому, незважаючи на те, що технології вже 5 років, популярність її до дотепер невисока. Ми давно хотіли випробувати WebGL на який-небудь не найскладнішої задачі, і Поверхи стали чудовою можливістю це зробити.

Наш проект складається з WebGL-додатки, вбудованого в онлайн-версію 2ГІС, і бекенду, який роздає йому дані. При заході в Поверхи додаток завантажує з бекенду дані і розмальовує ним будівлю.


Схема архітектури Поверхів

У вихідному вигляді дані представляють собою набір звичайних WKT-геометрій   площ-кімнат, ліній-стін і точок POI. У у такому вигляді для малювання у WebGL вони не годяться, тому їх потрібно спочатку підготувати: ми прибираємо з них все зайве, надаємо плоским геометриям обсяг і всі триангулируем. Всі ці операції виконуються на сервері. Для цього у нас написано окремий додаток конвертації.

Працювати з WebGL безпосередньо важко: це низькорівневий API, в якому для досягнення самих простих речей доводиться писати багато коду. У нашій вступної статті WebGL описується, як на чистому WebGL намалювати обертовий куб, і повний код отриманого прикладу займає більше 200 рядків. Тому на ранньому етапі розробки ми використовували популярний WebGL-фреймворк three.js.

Однак, three.js   великоваговий комбайн з величезною кількістю можливостей, які ми використовували лише малу частину. Тому в певний момент ми замінили його на власноручно написану бібліотеку 2gl, якою є тільки те, що нам потрібно.

Використання своєї бібліотеки зменшило розмір складання програми більш ніж в два рази і значно підвищило її продуктивність.

Як ми труднощі долали
Розробка WebGL-движка для малювання планів приміщень   далеко не сама стандартна завдання для фронтенд-розробника. У час роботи над Поверхами нам довелося вирішити безліч незвичайних, цікавих і часто несподіваних проблем, про деяких з яких ми вирішили написати в цієї статті.

Як зробити плоске об'ємним?
Коли ми почали роботу над поверхами і стали вивчати формат вихідних даних, виявилося, що вони навіть не тривимірні. Форма кожного поверху представляється набором двомірних площинних (кімнати) і лінійних (стіни) геометрій. Для плоского відображення поверхів у мобільної версії 2ГІС такого формату достатньо. Нам ж довелося придумати, як надати поверхах обсяг.

З площадниками проблем не виявилося: ми просто малюємо їх в площині підлоги. А з стінами довелося повозитися. Спочатку ми спробували просто брати лінії і робити з них плоскі стіни нульової товщини. Вийшло негарно:


Ранній прототип Поверхів з плоскими стінами

У реальному світі стіни мають товщину. То ж саме потрібно було зробити і в Поверхах.

Отже, потрібно по набору ламаних ліній отримати набір тривимірних геометрій стін. У загальному вигляді розв'язання цієї задачі нетривіально. Але  вирішили піти від простого і спочатку спробували реалізувати найпростіше і очевидне рішення «в лоб».

  1. Знаходимо точки перетину стін.
  2. Для кожної точки перетину перебираємо всі пари стін, що утворюють кути.
  3. Для кожної такої пари вимірюємо кут між ними.
  4. Проводимо биссектрису цього кута і відкладаємо на ній «кутову точку» — вона стане зовнішнім кордоном майбутньої потовщеною стіни.
  5. З'єднуємо всі кутові точки і отримуємо зовнішні контури стін.

Анімація роботи алгоритму для різної товщини стін

Цей простий алгоритм працює добре, тільки якщо потрібна маленька товщина стін. Якщо ж стіни потрібно розсунути далеко, а особливо, якщо в даних при цьому є перетинання під гострими кутами, результат вже буде некоректним:


При великій товщині з'являються артефакти

Однак, коли ми подивилися на результати його роботи, виявилося, що на наших даних він дає хороші результати в 100% випадків, тому придумувати щось більш складне виявилося зовсім не потрібно.

У ми отримали поверхах красиві, об'ємні стіни, вирішивши потенційно складну задачу сотнею рядків простого коду:


Стіни тепер матеріальні

Як запрограмувати інерцію?
Ні один сучасний картографічний движок не обходиться без інерційного руху під час перетягування карти. Завдяки інерції карта поводиться схоже на матеріальний об'єкт, рухати її стає інтуїтивно просто і приємно. Інерція — одна з перших речей, яку бачить і відчуває користувач, секунду тому відкрив карту і почав її рухати. Тому вона вносить особливо великий внесок у загальне враження від використання карти.

Про те, як в загальному влаштована інерція в картах, можна почитати  цієї статті. Описане в нею рішення має один недолік: в нім анімація уповільнення покладається на періодичний виклик спеціальної функції, яка на кожному кадрі зменшує швидкість карти в певне число разів. Така реалізація буде працювати коректно тільки при постійному FPS. Якщо ж FPS просяде, то ця функція буде викликатися рідше, і анімація триватиме довше, ніж потрібно.

Щоб прибрати залежність від FPS, положення карти необхідно обчислювати на основі часу, що пройшов з початку анімації. Обчислювати його потрібно по якоюсь формулою.

Що це має бути за формула? Перша відповідь, яка прийшла нам в голову   кинематическое рівняння равноускоренного руху з підручника фізики за восьмий клас. Ось воно:



Тут:
x0   початкове положення
v0   початкова швидкість
a   прискорення

Ідеально! x0 і v0 нам відомо, а підібравши значення константи a, ми зможемо налаштувати анімацію. А головне, що інерція, що працює за такою формулою, буде реалістичною і справляти гарне враження.

Так ми думали, поки не запрограмували цю формулу. Виявилося, що вона працює з рук геть погано. При малих модулю значеннях прискорення ТЦ неконтрольовано виїжджав за межі екрану після найменшого руху мишею, ніби машина на слизькому льоду, при великих   карта зупинялася майже миттєво після драга.

Обидва варіанти створювали однаково неприємне враження: в першому випадку втрачалося почуття контролю, в другому складалося враження погано змащеного механізму. Золоту середину знайти ніяк не виходило.

Втомившись від марних спроб підібрати оптимальне прискорення, ми спробували використовувати замість фізичного рівняння одну з easing-функцій Роберта Пеннера, які вже багато років використовуються для js-анімацій та вбудовані у багато бібліотек.

Результат виявився чудовим: після драга карта плавно і граціозно зупинялася, при цьому не їдучи надто далеко. І незважаючи на те, що рух її перестало бути «правильним» з точки зору фізики, сприйматися воно стало набагато краще.

Ми поекспериментували з різними easing функціями і в підсумку написали свою, яка працювала вже в точності так, як нам хотілося, але це вже не найважливіша частина історії. Найважливіше   простий урок, який ми засвоїли: реалістична анімація   не значить хороша анімація.

Як підписати кімнати?
Кімнати і об'єкти на поверхах ми позначаємо з допомогою маркерів і підписів до ним. Як намалювати маркери в рамках WebGL-програми? Найпростіше рішення   створити для кожної з нього за DOM-елементу і відображати їх поверх WebGL-кинувся. На кожному кадрі необхідно обчислювати нову позицію кожного маркера і пересувати відповідні їм DOM-вузли.

Нам довелося майже відразу відмовитися від цієї ідеї однієї простої причини: DOM — це занадто повільно. Необхідність оновлювати позиції великої кількості DOM-елементів на кожен кадр призводила до зростання часу відтворення кадру в десятки разів.

Вихід один   використовувати WebGL-спрайт. Досить намалювати прямокутник (а    два трикутника), натягнути на потрібну текстуру та помістити в 3D-сцену. Саме так, наприклад, малювалися монстри в старих 3D-шутерах:


Майже те, що нам потрібно

Від зомбі в Doom II маркери в поверхах відрізняються лише однією деталлю: їх розмір залежить від відстані до камери. Ця вимога легко реалізувати з допомогою кастомного вершинного шейдера: ми написали для маркерів спеціальний шейдер, який позиціонує вершини спрайту саме так, як потрібно для збереження постійного розміру в пікселях.

Побудова WebGL-спрайтів працює дуже швидко: можна нанести на мапу тисячі об'єктів без втрати продуктивності. Але коли карті занадто багато маркерів, з'являється наступна проблема: вони перекривають один одного.


Що буде, якщо одночасно підписати всі об'єкти поверху

Поширеним рішенням цієї проблеми є кластеризація маркерів. Цей підхід полягає в те, що серед безлічі всіх маркерів виділяються групи найбільш близькорозташованих (кластери), і при зменшенні масштабу кластер замінюється одним збірним маркером.

У поверхах ми використовуємо більш простий підхід, який ми назвали генералізацією: ми просто присвоюємо кожному маркеру деякий пріоритет і приховуємо маркери з низьким пріоритетом, якщо вони перекривають більш важливі маркери.

Для перевірки перетину маркерів потрібно представити їх в вигляді баундов   прямокутних областей, які вони займають на екрані. А пріоритети ми вибираємо на основі типу мітки: наприклад, об'єкти інфраструктури (ліфти, туалети тощо) мають найбільший пріоритет, тому вони завжди будуть видні навіть на самих дрібних масштабах.


Робота генералізації: залишаємо найважливіше

Наївна реалізація такого алгоритму має квадратичну трудомісткість: кожен маркер потрібно перевіряти на перетин з усіма іншими. Щоб він працював швидше, ми застосували прекрасну бібліотеку rbush, реалізуючу структуру даних R-дерево. R-дерево вміє зберігати прямокутні області та швидко виконувати пошук їх перетинів — це якраз те, що нам потрібно.

Після застосування rbush трудомісткість стає n * log(n), і на поверхах Дубай Молла (до 1000 об'єктів на поверсі) алгоритм відпрацьовує за ~10 мс. Перемістивши його виконання в веб-воркер, ми повністю виключили його вплив на FPS.

Остання труднощі в креслення маркерів на WebGL   зробити їх клікабельними. У DOM-елементів є події (click, mouseover і т. д.), які досить просто підписатися; в світі WebGL такого немає. Тому необхідно навчитися координат курсору самостійно визначати, який маркер клікнув користувач.

Тут нам на допомогу знову приходить бібліотека rbush: досить побудувати R-дерево, що містить баунды усіх видимих даний момент маркерів, і для обробки кліка просто виконувати пошук нього. Пошук по R-дерева   логарифмічна операція, що виконується вона швидко, і можна без проблем виконувати її не тільки за кліку, але і  будь зміною положення курсору. Це дозволяє зробити маркери чутливими не тільки до кліку, але і наведення миші.

Як зробити изометрию красивою?
Неважко помітити, що в Поверхах використовується ізометрична проекція, що для веб-карт досить незвично.

Якщо для звичайних тривимірних карт краще підходить звична всім перспективна проекція, то схема приміщення набагато краще виглядає в ізометрії. У цієї проекції далекі об'єкти мають той же розмір, що і близькі, завдяки чому карта стає більш наочною і по-хорошому схемної. Більш того, це просто красиво.

У ізометричної проекції є один недолік: вона неоднаково добре виглядає при різних кутах повороту карти. Якщо повернути камеру так, щоб стіни розташувалися на екрані строго вертикально і горизонтально, вийде така картина:


Невдалий кут повороту

Це не дуже красиво: вертикальні стіни виявляються майже невидимими, карта читається погано.

Спочатку ми відкривали всі будівлі дефолтному стані «північ угорі», і торгові центри, у стіни яких розташовуються вздовж паралелей і меридіанів, виглядали саме так.

Якщо ж камеру трохи повернути і розташувати стіни саме так, як і покладено в ізометрії, виходить так:


Вдалий кут повороту

Набагато краще. Такий вид добре знайомий нам по великому числу олдскульних (і не дуже) ігор, в яких використовується ізометрія:




Fallout 2 і Theme Hospital

Таким чином, перед нами стояло завдання для кожного торгового центру обчислити найбільш оптимальний кут повороту, щоб при відкритті режиму поверхів уявити його в найкращому вигляді.

Якщо архітектура приміщень в ізометричних іграх, як правило, проста (всі стіни перпендикулярні), то з реальними будівлями все не так просто: в наших даних є торгові центри дуже химерних форм, де стіни перетинаються під самими дивними кутами.

Однак, ми зауважили, що навіть у найскладніших формі будівлях є якийсь напрям, в якій розташована переважна більшість стін.

Цим фактом ми і вирішили скористатися. У математики таке переважне частоті значення називається «модою». Ми спробували при підготовці даних вимірювати кути кожної стіни торгового центру і знаходити моду отриманого безлічі. Додаючи до знайденої моді PI / 4, ми отримували потрібний кут повороту камери.

Алгоритм показав прекрасні результати: він безпомилково визначає головний напрямок» стін і розгортає ним будівлю.


Правильно розгорнутий ТЦ «Мега Химки»

У математики, якщо множина містить більше однієї моди, воно називається мультимодальних. Відкриваючи різні будівлі на Поверхах в 2ГІС, можна побачити, що цей термін можна застосувати і до деяких торгових центрах:


ТЦ «Золотий Вавилон» з трьома модами

Незважаючи на те, що мод кілька, одна з них більш модна. &Nbsp;ній ми і розгортаємо план ТЦ. Математика часом виявляється в нашого життя в найнесподіваніших формах, і це, мабуть, один з таких випадків.

Висновки
Велику частину часу Поверхи розроблялися двома програмістами. Коли ми починали працювати над проектом, ніхто з нас нічого не знав ні про WebGL, ні про 3D-графіку взагалі, так і досвід веб-розробки у нас був досить скромний.

Перші версії Поверхів виглядали страшно і працювали в кращому випадку на 20FPS. У час розробки ми набили всі шишки, які тільки могли набити, не раз цілком переписували великі частини проекту. Але результат щоразу виходив трохи краще попереднього, і це надихало нас з самого першого прототипу, і надихає до дотепер.

Не бійтеся пробувати WebGL: ця технологія дозволяє робити дійсно фантастичні речі.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.